We have a polynomial $p(x_1,\ldots,x_n)$ of degree $n$ whose coefficients are integers in $[-2^n,2^n]$. The polynomial is given to us as a ``black box'' - that is, we can ask someone what $p(r_1,\ldots, r_n)$ is and have the answer given to us, where $r_1, \ldots, r_n$ are rational numbers whose size is at most polynomial in $n$; say, for concreteness, that both numerator and denominator of each $r_i$ are at most $2^{n^{1000}}$. As a function of $n$, how many (deterministic) queries do we need to make to decide if $p$ is identically zero? Specifically, can we do with polynomially many queries?


  1. This is a followup to a previous question Deciding if a polynomial equals zero. The answers to that question noted that one query is sufficient if one does not require the numbers $r_1,\ldots,r_n$ to be rational or alternatively if one does not place a limit on their sizes.

  2. This seems to be part of a field called "polynomial identity testing." Googling these words brings up a large literature on the subject; most of it, however, appears to be over finite fields, and I wasn't able to find out if a solution to the above question (which is over the real numbers) is available.

  • $\begingroup$ There are, if my combinatorics aren't too rusty, $\binom{2n}{n}$ coefficients to determine, so if it was not for the bound on the coefficients' sizes, querying fewer points than that would certainly not be enough. Is your hope that the coefficient bounds will allow you to get by with fewer queries, or do you want a strategy for choosing $\binom{2n}{n}$ points to query? $\endgroup$ – Henning Makholm Mar 15 '12 at 0:43
  • $\begingroup$ Fewer queries, specifically polynomially many queries in $n$. $\endgroup$ – robinson Mar 15 '12 at 5:36
  • $\begingroup$ Given that your coefficients must be rather small, but you can test complicated rational numbers, you could do with fewer tries than necessary in the unbounded case. For instance, for a univariate polynomial of degree${}\leq n$ you'd need $n+1$ roots to prove it $0$. But if it vanishes in a rational number whose reduced expression involves numbers greater than $2^n$, then a root in that number cannot be produced while keeping coefficients in $[-2^n,2^n]$. I've no proof, but my guess would be that one sufficiently complicated rational vector could suffice to decide your polynomial is zero. $\endgroup$ – Marc van Leeuwen Mar 17 '12 at 20:31
  • $\begingroup$ Actually, I think the accepted answer, by Robert Isreal, to the other (previous) question (and the comments following it) points out examples of such sufficiently complicated vectors, where one test will suffice. $\endgroup$ – Marc van Leeuwen Mar 17 '12 at 20:40
  • $\begingroup$ @MarcvanLeeuwen - this is true, but those examples do not appear to satisfy my criterion that both numerator and denominator be below $2^{n^{1000}}$. $\endgroup$ – robinson Mar 17 '12 at 21:40

If the coefficients are nonnegative integers, it suffices to take all $x_i = 1$.

  • $\begingroup$ Indeed - I didn't mean for that to be the case. I edited the question so that it no longer forces them to be nonnegative. $\endgroup$ – robinson Mar 14 '12 at 0:10

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.