Suppose p(x) is a polynomial with integer coefficients. If all the coefficients are non-negative, I can tell you what p(x) is if you’ll tell me the value of p(x) at just two points.
This sounds too good to be true. Don’t you need n+1 points to determine an nth degree polynomial? Not in this case. The trick is that first I ask for p(1). Call your answer q. Next I ask you for the value of p(q). That’s enough information to find all the coefficients.
I ran across this in the answer to a question on Math Overflow. Aeryk said
If you know that the coefficients are non-negative and also integral, then the polynomial can be completely determined by the values of p(1) and p(p(1)).
I suppose this is a well-known theorem, but I’d never seen it before.
ARupinksi added this explanation.
q=p(1) gives the sum of the coefficients. Now think of p(p(1))=p(q) written in base q; one sees that the “digits” are exactly the coefficients of p. The only possible ambiguity comes if p(q)=q^n for some n, but since the coefficients sum to q, one sees that p=qx^n−1 in this case.
This explanation is correct, but terse, so I’ll expand on it a bit. First a couple examples.
Suppose you tell me that p(1) = 9 and p(9) = 1497. I need to write 1497 in base 9. A little work shows 1497 = 2 × 93 + 4 ×9 + 3. This means me p(x) = 2 x3 + 4 x + 3.
Next suppose you tell me p(1) = 5 and p(5) = 625. Since 625 = 54, p(x) = 5 x3.
Here’s a slightly more formal, algorithmic explanation. Suppose
p(x) = a0 + a1x + a2x2 + … anxn.
We can recover the coefficients of p(x) from highest to lowest by repeatedly pulling out the largest powers of q we can. First we find the largest power of q less than p(x), say
qm < p(q) ≤ qm+1.
Then the quotient when p(q) is divided by qm is the coefficient am. If p(q) = qm+1, then am = q and we’re done. Otherwise,
p(q) = am qm + r
where 0 < r < qm. We repeat our process, pulling out the highest power of q out of r that we can to find the next coefficient. Since the coefficients sum to q, and we first found am ≥ 1, all our subsequent coefficients must be less than q.
Don’t you mean “I need to write 1497 in base *9*”?
Thanks. I first came up with an example with p(1) = 6, but then I changed it and missed an edit.
I think it’s not vivid to use p(1) as the second point to ask. I’d prefer 10^ceiling(lg(p(1) + 1))
For example if p(x) = 2 x^3 + 4 x + 5 , p(1) = 11. Then use 100 as the second point. p(100) = 2000405, or to make it obvious: 02 00 04 05, so no need to make base conversions.
This might be easier to explain by pointing out that p(10) determines the coefficients directly, but only works if all the coefficients are all less than 10. Calculating p(1) is just a way of determining a base that is at least as large as the largest coefficient.
Beautiful result!
Wow.
Delightful! And with exposition so simple, even this poor statistician can understand it. Thanks.
Obviously, part of the trick (not the most important as jk pointed), is that the second input is “asked” depending on the first input. I wonder if that trick helps for the case of *real* coefficients; that is, if the input is asked in sequence (and depeding in the previous answer), if one can determine the real polynomial with less than `n’ inputs.
(Probably it doesn’t help, maybe it does help if one has rational coefficients?)
alfC, I believe the answer to your question about real or rational coefficients is no.
Look at the step:
“Then the quotient when p(q) is divided by q^m is the coefficient a_m”
If we allow (non-integer) real or rational coefficients, then the first quotient (the coefficient a_m) is always the real or rational number p(q)/q^m and the remainder (r) is always zero… and the algorithm fails.
Note: I’m sure this could be explained in a much more elegant manner with references to math theorems and such, but I’m too tired to do that right now… Someone else feel free to do that (or correct me if I’m wrong) :)
for polynomials like p(x)=x^n the trick does not work as p(1)=1,
therefore p(p(1)) remains 1, and p(x) can not be determined.
one more thing, in your 2nd example:
i.e p(x)=5x^3
here p(1)=5
and p(p(1))=p(5)=64=5^4
according to your first example
p(x) would be x^4
but as the sum of the coefficients is 5 so
you have intuitively said p(x) is 5x^3.
I worked out and found that it would work better
if the two inputs are
1.maximum of all coefficients say m .
and
2.p(m +1)
then it would work for all polynomials
with positive integer coefficients.
for example:
p(x)=x^4
here maximum coefficient is 1
and p(1+1)=2^4=16
now apply your trick i.e
expressing 16 in base m+1 i.e 1+1=2.
another example:
let,p(x)=2x^3+4x+3
here m=4
so p(4+1)=2*5^3+4*5+3=273
now express 273 in base m+1=5.
last example:
p(x)=5x^3
here m=5
m+1=6
p(6)=5*6^3=1080
again express 1080 in base 6.
It is easier to calculate p(max coefficient) rather than
calculating p(sum of all coefficients) because sum of all
coefficients may be very large.
ANY COUNTER EXAMPLE HIGHLY APPRECIATED.
@sukanta sen, Does p(x) = x^n qualify as a polynomial with +ve coefficients? I don’t think so.. Also, what you have said is a slightly different version of Ivan Bachtin’s procedure which I think is very elegant.
@HB: The article says “non-negative coefficients”, not “positive coefficients”. So Sukanta’s question is valid. I guess the author has taken care of it now.
I imagined the “hidden answer” to be p(x) = (3, 2, 1) = $3x^2 + 2x + 1$. How would I know? p(1) = 3 + 2 + 1 = 6. And then the “digits” come out quite clearly in p(6): 3 • 36 + 2 • 6 + 1 • 1. I could verify with
bc -lthat121; ibase=10; obase=6does turn out to be 321 but you can already see it will.Related MO question – http://mathoverflow.net/questions/39733/how-to-tell-if-two-random-polynomials-are-identical/39747#39747
1. You can query just once at a point b > 2c + 1 , where all coefficients are in [-c.c]
2. Works for negative integral coefficients.
What is the role of p(1) here? Wont you know the co-efficient if you knew any p(x), by writing it in base x form, where x>maximum of all coefficient? for example p(6)=3x^2+2x+1, then p(6)=121, which can be written in base 6 as 321. It wont be true if you were using p(3), p(2) or p(1).
Sure. But how do you know the maximum coefficient? You have to query the polynomial once for that. p(1) is just an obvious way to do that.
when written completely 16 to the power of 2011 has m digits and 625 to power of 2011 has n digits find m+n
To be correct for any polynomial, your second query must be strictly larger than p(1). I.e., if you use p(x) = x^n then querying 1 and p(1) is just querying 1 twice and does not allow you to distinguish from p(x) = x^m for any other m.
Use Principle of Mathematical induction to show that the
polynomial P(X) = X3
– X, is divisible by 6, where X is a
non-negative integer.