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
    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?2012-03-15
  • 0
    Fewer queries, specifically polynomially many queries in $n$.2012-03-15
  • 0
    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.2012-03-17
  • 0
    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.2012-03-17
  • 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