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.