Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
I 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. –  joriki Mar 9 '12 at 19:29
    
Ah! 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.... –  Hurkyl Mar 9 '12 at 19:30
2  
How 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. –  GEdgar Mar 9 '12 at 19:47
4  
    
Google for: Polynomial identity testing. –  user2468 Mar 12 '12 at 0:53
add comment

4 Answers

up vote 8 down vote accepted

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.

share|improve this answer
    
Nice answer. +1 –  N. S. Mar 9 '12 at 19:50
    
Thanks. 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. –  robinson Mar 9 '12 at 22:07
    
...i.e., could you explain to pick $n_i$ so that this condition is satisfied? Thank you. –  robinson Mar 9 '12 at 22:07
    
$n_i = (d+1)^i$ will do (because base-$(d+1)$ representations of nonnegative integers are unique). –  Robert Israel Mar 9 '12 at 22:22
    
You could also use $x_i = p^{n_i}$. –  Robert Israel Mar 9 '12 at 22:28
add comment

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...

share|improve this answer
    
Are you thinking of the case $n=1$? –  Robert Israel Mar 9 '12 at 19:41
    
As far as I know the rational root test doesn't work for multiple variables... –  N. S. Mar 9 '12 at 19:43
    
You're absolutely right. Sorry, I didn't notice that this was multivariable. Should I delete my answer? –  minimalrho Mar 9 '12 at 19:44
    
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$? –  N. S. Mar 9 '12 at 19:46
add comment

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.

share|improve this answer
    
I feel silly that, when I made my comment, I didn't notice that the coefficients of the polynomial were integers. –  Hurkyl Mar 9 '12 at 22:14
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.