4
$\begingroup$

Consider the following game, played between Alice and Bob: Alice chooses a polynomial $p(x) \in \mathbb{Z}[x]$, where the coefficients are all greater than or equal to $-1$. Bob's goal is to determine the polynomial; to this end he may ask Alice to evaluate the polynomial on any rational point.

Is there a protocol Bob can follow s.t. he will eventually find $p(x)$ (i.e., find all its coefficients)? If so, what is the best bound on the number of steps required?

Background: This is a generalization of a riddle I heard from Sergiu Hart. The question is the same as above, but $p(x)$ is known to have non-negative integer coefficients (and not just greater than $-1$). With this additional constraint, Bob can find $p(x)$ with a surprisingly small number of queries.

Additional note: If Bob is allowed to ask for evaluations on real, rather than just rational, points it is almost trivial that he can find $p(x)$ with a single query (though this is arguably cheating).

$\endgroup$
  • 1
    $\begingroup$ Oh. Well, then. In that case I'd have to think a bit more. $\endgroup$ – Arthur Feb 4 at 8:52
  • 2
    $\begingroup$ @Priyatham The exact value of the polynomial on any trancendental number (like $\pi$ or $e$) would by definition of transcendental give you the exact polynomial; there cannot be two distinct integer polynomials with the same value at that point. It may be a pain to actually find the polynomial, but theoretically he has all the information he needs from Alice with that one evaluation. On the other hand, if you're limited to algebraic numbers, this is still interesting (both $x^2$ and $2$ gives $p(\sqrt 2) = 2$, for instance). $\endgroup$ – Arthur Feb 4 at 8:54
  • 2
    $\begingroup$ @Micapps She can give him a black box machine which can calculate and output any digit of $p(\pi)$ that is asked for. Don't know whether that's enough, though. But this is a concern on a different level, in my opinion. $\endgroup$ – Arthur Feb 4 at 9:03
  • 1
    $\begingroup$ Related, including the solution to the problem for nonnegative integer coefficients for the curious: math.stackexchange.com/questions/1693167/… $\endgroup$ – Eric Wofsey Feb 6 at 7:48
  • 2
    $\begingroup$ Small observation: it suffices to find an upper bound for the leading coefficient of $p$, since then you can let $q$ be a prime greater than the upper bound and query $p(1/q)$ to determine the degree. $\endgroup$ – Eric Wofsey Feb 6 at 8:11
1
$\begingroup$

Start by querying $p(2)$. Now I claim that the leading coefficient of $p$ is less than or equal to $M=\max(1,p(2)+1)$. Indeed, if $p(x)=a_nx^n+a_{n-1}x^{n-1}\dots+a_0$, then $$p(2)\geq a_n2^n-2^{n-1}-\dots-1=a_n2^n-2^n+1>(a_n-1)2^n$$ which is at least $a_n-1$ unless $a_n\leq 1$. It follows that $a_n\leq M$.

Now note that if $q$ is a prime which does not divide the leading coefficient of $p$, then the denominator of $p(1/q)$ in least terms will be $q^n$ where $n=\deg p$. So, let $q$ be a prime greater than $M$, and query $p(1/q)$ to determine the degree of $p$. Once we have the degree of $p$, we can determine $p$ with $\deg p+1$ queries.


This method generalizes to the case where there is any lower bound on the coefficients of $p$. Indeed, if the coefficients of $p$ are all at least $-N$, then we can query $p(N+1)$ first to similarly get an upper bound on the leading coefficient of $M$ (since the negative lower degree terms will not be able to catch up to the leading term). It makes crucial use of being able to query rational inputs, and not just integer inputs. I don't know if it's possible to do it with just integer inputs. I also don't know whether it's possible to do it with a bound (independent of $p$) on the number of queries.

$\endgroup$

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.