9
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Also, it seems this approach (with a small fix) works even if you are allowed to query $f(x)$ for rational (not just integral) $x$. $\endgroup$ – Micapps Feb 6 at 8:40
  • 1
    $\begingroup$ Yeah, you can still add a polynomial that vanishes at all those values of $x$. In fact, this even works if $x$ can be algebraic. $\endgroup$ – Eric Wofsey Feb 6 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.