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?
Deciding if a polynomial equals zero
-
1I don't see how randomization could help here. Each coin toss will lead to an average between two possible strategies we could have chosen, and it will always be better just to pick the better of the two than to pick the average. – 2012-03-09
-
0Ah! Having a bound on the coefficients makes things more interesting. If you had a lower bound on their magnitude too, I'm pretty sure the answer just 1.... – 2012-03-09
-
2How do you pick a point in $\mathbb R^n$ to get your answer? Without some explanation, I can say: just pick $n$ algebraically independent numbers, and ask "someone" to tell you the result. Since $p$ has integer coefficients, $p(x)=0$ will happen only for the zero polynomial. – 2012-03-09
-
4http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma – 2012-03-09
-
0Google for: Polynomial identity testing. – 2012-03-12
4 Answers
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.
-
0Nice answer. +1 – 2012-03-09
-
0Thanks. Could you provide some more details on how to pick such integers $n_i$? Its just that I'm especially interested in the case where you only evaluate the polynomial at rational points. – 2012-03-09
-
0...i.e., could you explain to pick $n_i$ so that this condition is satisfied? Thank you. – 2012-03-09
-
0$n_i = (d+1)^i$ will do (because base-$(d+1)$ representations of nonnegative integers are unique). – 2012-03-09
-
0You could also use $x_i = p^{n_i}$. – 2012-03-09
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...
-
0Are you thinking of the case $n=1$? – 2012-03-09
-
0As far as I know the rational root test doesn't work for multiple variables... – 2012-03-09
-
0You're absolutely right. Sorry, I didn't notice that this was multivariable. Should I delete my answer? – 2012-03-09
-
0Well, 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
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.
-
0I feel silly that, when I made my comment, I didn't notice that the coefficients of the polynomial were integers. – 2012-03-09
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$.