5

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

Micapps
  • 1,385
  • Well, almost trivially, he can find $p(x)$ with $\deg(p) + 1$ queries. Presumably you want something better than that. – Arthur Feb 04 '19 at 08:47
  • @Arthur Bob doesn't know the degree. I would be very happy with a protocol that Bob can follow allowing him to determine the degree. – Micapps Feb 04 '19 at 08:48
  • 1
    Oh. Well, then. In that case I'd have to think a bit more. – Arthur Feb 04 '19 at 08:52
  • I fail to see how one query on a real number is enough. – Priyatham Feb 04 '19 at 08:54
  • 3
    @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). – Arthur Feb 04 '19 at 08:54
  • @Arthur As a side comment, it's not entirely clear in what sense Alice can convey $p(\pi)$ (for example) to Bob, besides as a formal polynomial in $\pi$. – Micapps Feb 04 '19 at 09:00
  • 2
    @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. – Arthur Feb 04 '19 at 09:03
  • 1
    Related, including the solution to the problem for nonnegative integer coefficients for the curious: https://math.stackexchange.com/questions/1693167/coefficients-of-mystery-polynomial – Eric Wofsey Feb 06 '19 at 07:48
  • 2
    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. – Eric Wofsey Feb 06 '19 at 08:11
  • 1
    Haven't been able to make this idea work, but throwing it out there for others: after $n$ guesses $a_1/b_1,\dots,a_n/b_n$, either $p(x)$ has degree at most $n-1$ or not. If so, there's only one possibility $p_n(x)$. If not, then $p(x) = p_n(x) + q_n(x)(b_1x-a_1)\cdots(b_nx-a_n)$ for some $q_n(x)$. Is there a way of choosing the $(n+1)st$ guess to distinguish between these two possibilities?—making it large enough and/or nonintegral enough that $q_n(x)$ must definitely be nonzero if $p(x)$ is to have coefficients $\ge-1$? – Greg Martin Feb 06 '19 at 08:51

1 Answers1

1

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.

Eric Wofsey
  • 330,363