Coefficients of Mystery Polynomial

Question

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?

Answer 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.

Answer 2

There is a result in

Bettina Richmond (2010) On a Perplexing Polynomial Puzzle, The College Mathematics Journal, 41:5, 400-403, DOI: 10.4169/074683410X522017

that definitively answers the negative integer coefficients case.

A preprepint is also available here.

Summary below:

It seems rather surprising that any given polynomial $p(x)$ with nonnegative integer coefficients can be determined by just the two values $p(1)$ and $p(a)$, where a is any integer greater than $p(1)$. This result has become known as a “perplexing polynomial puzzle” in [2, 3]. Here, we address the natural question of what might be required to determine a polynomial with integer coefficients, if the condition that the coefficients be nonnegative is removed.

Let us analyze the original puzzle. Requiring that $p(x) = c_0 + c_1 x + \cdots + c_nx^n$ has nonnegative integer coefficients gives zero as a lower bound and $p(1) = c_0 + c_1 + \cdots + c_n$ as an upper bound for the coefficients. Then if $a > p(1)$, writing $p(a)$ as $c_0 + c_1 a + \cdots + c_n a^n$ gives the unique base $a$ representation of $p(a)$, so the nonnegative integer coefficients $c0, c1, \cdots , cn$ of $p(x)$ are completely determined by $p(a)$. The coefficients of $p(x)$, which serve as the base a digits, must fall in the appropriate set $\{0, 1, . . . , a − 1\}$, so we must choose $a$ to be an upper bound of the coefficients.

If we allow negative coefficients and find a bound $b$ on the coefficients so that $−b \le c_i \le b$ for all $i$, then we wonder whether the coefficients are uniquely determined by the value of $p(a) = c_0 + c_1 a + \cdots + c_n a^n$ for a suitable choice of $a$. Theorem 3 answers this question affirmatively, giving $a = 2b + 1$ as a suitable choice. In effect, we ask whether $p(a)$ has a unique base $a$ representation if the digits $c_i$ assume values from the set $\{−b, −b + 1, \cdots , 0, \cdots , b − 1, b\}$. Theorem 2 confirms the existence of such a representation.