Coefficients of Mystery Polynomial

Let's play a game. I have a polynomial $f(x)$ which has nonnegative integer coefficients. You can ask me for the value of $f(n)$, where $n$ is a nonnegative integer. In how many $n$ can you determine the coefficients of my polynomial?

This problem isn't so bad. First you can ask for $f(1)$, which is greater than or equal to each individual coefficient of my polynomial. Then you can ask for $f(f(1))$ and express it in base $f(1)$, which works because we've already determined that $f(1)$ is at least as large as each coefficient, so at each digit there is no "bleed-over" into the next digit.

Quick example, just to confirm I'm not crazy:

$$f(x) = 2x^3 + 2x + 3$$ $$f(1) = 7$$ $$f(7) = 703$$ $$703_7 = 2023$$

My question is this: one of our assumptions is that $f$ has nonnegative coefficients. What happens if we relax this restraint to say the coefficients can be any integer?

My intuition is that we should still be able to guess the polynomial in finitely many steps, but we can't use the method outlined above because we have no guarantee $f(1)$ will be larger than each coefficient - in fact, $f(1)$ may be zero.

What happens if we relax the constraint to be nonnegative rational coefficients, instead?

Solution 1:

It is not possible to determine $f$ in finitely many queries if its coefficients are allowed to be arbitrary integers. Indeed, suppose you have queried the values of $f(n_1),\dots,f(n_k)$ so far. Then the polynomial $g(x)=f(x)+(x-n_1)(x-n_2)\dots(x-n_k)$ is another polynomial with integer coefficients with $g(n_1)=f(n_1),\dots,g(n_k)=f(n_k)$. So, you cannot yet determine $f$ uniquely.