Conocer una función cuadrática con sólo 2 puntos

Polynomial determined by two inputs

by John on March 27, 2012

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 × 9³ + 4 ×9 + 3. This means me p(x) = 2 x³ + 4 x + 3.
Next suppose you tell me p(1) = 5 and p(5) = 625. Since 625 = 5⁴, p(x) = 5 x³.
Here’s a slightly more formal, algorithmic explanation. Suppose

p(x) = a₀ + a₁x + a₂x² + … a_nxⁿ.

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

q^m < p(q) ≤ q^m+1.

Then the quotient when p(q) is divided by q^m is the coefficient a_m. If p(q) = q^m+1, then a_m = q and we’re done. Otherwise,

p(q) = a_m q^m + r

where 0 < r < q^m. 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 a_m ≥ 1, all our subsequent coefficients must be less than q.