### a polynomial problem

The latest problem from fakalin. Took some wrong turns and hints to solve it…

Given a polynomial $$f: \mathbb{Z}\to \mathbb{Z}$$ with positive integer coefficients, how many evaluations of $$f$$ does it take to obtain the polynomial?

(An $$f: \mathbb{R}\to \mathbb{R}$$ polynomial with real coefficients would take the number of degrees plus 1 to specify, which, if it held in this case, would render the answer unbounded. But the correct answer in this case is surprisingly small.)

It takes only 2 evaluations. Suppose in the following that $$b>0$$. Let us note that a polynomial $$f(b) = a_n b^n + … + a_0 b^0$$ specifies essentially a base $$b$$ representation of the number $$f(b)$$, in that $$a_n a_{n-1} … a_0$$ is an expansion of $$f(b)$$ in base $$b$$. The only problem is this expansion is non-unique, as it is possible for any $$a_j \ge b$$.

However, it is not possible for any $$a_j \ge f(b) + 1$$, since for all $$j$$, $$f(b) \ge a_j$$ by the problem statement and assumption on $$b$$. Then take $$B = f(b) + 1$$. Now we are guaranteed that $$a_n a_{n-1} … a_0$$ is the unique (and canonical) base $$B$$ expansion of $$f(B)$$, from which the polynomial coefficients immediately obtain.

So the two evaluations are at $$f(b)$$ and $$f(B=f(b)+1)$$.

Example: $$f(b) = 3b^2 + 2b + 1$$. Evaluate at, e.g., $$b=1$$ to get $$f(1) = 6$$. Then evaluate at $$B=f(1)+1=7$$ to get $$f(7)=162=321_{7}$$.