0
$\begingroup$

We have a polynomial $p(x_1,\ldots,x_n)$ of degree $d$ whose coefficients are integers in $[-B,B]$. The polynomial is given to us as a "black box'' - we pick a point $x \in \mathbb{R}^n$ and someone tells us what $p(x)$ is. My questions are: how many queries do we need to decide if $p(x)$ is identically zero? What strategy should we use? How does the answer change if we are allowed randomization, i.e., we can toss a coin which lands on heads/tails with probability 1/2?

  • 0
    Google for: Polynomial iden$t$ity testing.2012-03-12

4 Answers 4

8

Choose $x_i$ to be algebraically independent over the rationals. For example, by the Lindemann-Weierstrass theorem $x_i = e^{\alpha_i}$ will work where $\alpha_i$ are algebraic and linearly independent over the rationals.

Alternatively, you can take $p$ to be a prime greater than $B$, and $x_i = 1/p^{n_i}$ where positive integers $n_i$ are chosen so all the numbers $\sum_i d_i n_i$ for nonnegative integers $d_i$ with $\sum_i d_i \le d$ are distinct.

  • 0
    You could also use $x_i = p^{n_i}$.2012-03-09
1

The answer to your question is 1, but I don't know if the computational effort to get that is worthwhile.

By the rational root test, you have that the only possible rational roots are $p/q$ where $p$ divides of the constant term (thus must divide $B!$) and $q$ divides the leading coefficient (must divide $B!$ again).

Choose a rational number that is not in that finite list. If it evaluates to 0, the polynomial must be 0.

EDIT (see below): This only works for $n=1$. I thought I came up with a workaround, but I think it was mistaken. I'll try to fix it...

  • 0
    Well, here is a hint: $P(0,0,...,0, x_n)$ is a polynomial of the type you want. Can you modify your answer? What does it mean now that this is identically zero as a polynomial in $x_n$?2012-03-09
0

Lemma: Let $f$ be a polynomial of degree $d$ whose non-zero coefficients have magnitude in the range $[A, B]$ with $0 < A < B$. Then there exists an integer $a$ and bounds $0 < M < N$ such that either $f=0$ or $|f(a)| \in [M,N]$.

Proof: just pick $a$ so large that, if $f$ is nonzero, the leading term must dominate the formula.


$p(x, 0, 0, \ldots)$ is a polynomial satisfying the conditions of the lemma. Choose $a_0$ to satisfy the conclusion.

$p(a_0, x, 0, \ldots)$ is a polynomial satisfying the conditions of the lemma. Choose $a_0$ to satisfy the conclusion.

$p(a_0, a_1, x, \ldots)$ is ....

Now, ask the black box to compute $p(a_0, a_1, \ldots, a_{n-1})$. This is zero if and only if $p=0$.

This is the same basic idea of the lemma: plug in something so very large that the leading term cannot be cancelled out by the smaller terms. Therefore, you get zero if and only if there isn't a leading term -- i.e. the polynomial is zero.

  • 0
    I feel silly that, when I made my comment, I didn't notice that the coefficients of the polynomial were integers.2012-03-09
0

Picking any $n$ transcendental numbers as Robert Israel pointed out is just fine theoretically. However, if you want to do it on the computer, where the precision is limited, a randomized approach will probably be fine or even better. If you have a set $S$ you choose your values from, probability that a random tuple will hit a root of $p$ is less or equal $\frac{n|S|^{n-1}}{|S|^n} = \frac{n}{|S|}$ since there is $|S|^n$ tuples total and for any of $n$ variables if you fix it to be the root, you can set others in $|S|^{n-1}$ ways. So if you pick any $S$ of size twice as large as $n$ (e.g. integers from 0 to $2n-1$), then the expected number of tries is just $2$.