1
$\begingroup$

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?

Notes:

  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.

  • 0
    @MarcvanLeeuwen - this is true, but those examples do not appear to satisfy my criterion that both numerator and denominator be below $2^{n^{1000}}$.2012-03-17

1 Answers 1

1

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

  • 0
    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.2012-03-14