Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

When we work in $C[x_1,x_2,...,x_n]$,here $C$ denotes the complex field, we know that when polynomials $f_1,f_2,...,f_k$ have no common zeros, then there exists polynomials $g_1,...,g_k$ , such that the sum of $g_i\cdot f_i$ is $1$, (Nullstellensatz). However, this theorem doesn't seem to have any practical value, consider the following problem:

Is there any nontrivial criterion such that we can determine whether some polynomials (chosen randomly) have common zeros or not by using it? Of course, I don't want to use the Grobner base theory, what I need is just a criterion involving information on the algebraic properties of the given polynomials, something just like Eisensten's criterion on irreducibility.

share|improve this question
1  
The plural of criterion is criteria. –  Chandan Singh Dalawat Dec 11 '10 at 7:54
    
Yes - minor editing carried out. –  Gerry Myerson Dec 11 '10 at 8:53
    
@ougao, well naively speaking, if you consider the chance of a (random) polynomial $f(x)$ sharing a (particular) zero with (another random) polynomial $g(y)$ as being "equally likely" as the chance that these two (random) polynomials do not share any zeroes, then a "trivial" criterion (at least for me) would be: $h(0) = \frac{1}{2}$ where $h(z) = ABS(f(x) - g(y))$. I hope that trivial observation will get to help you with your problem somehow. –  Jose Arnaldo Dris Dec 11 '10 at 9:17
2  
I don't understand the statement "this theorem doesn't seem to have any practical value". There is an algorithm (the resultant algorithm, as pointed out by Myerson), which has many efficientimplementations and which is used in every known computer algebra system. As for the complexity issues, note that a general polynomial of degree $d$ in $n$ variables has a LOT of terms, so questions about such polynomials are sure to be very hard. If you restrict to SPARSE polynomials, the question becomes interesting. This is covered in the book by R. Zippel (Efficient Polynomial Computation). –  Igor Rivin Dec 11 '10 at 16:08
1  
OK, so it seems the question really is, how can I construct nontrivial examples of polynomials with no common zeros. That of course depends on what "nontrivial" means. Maybe this is trivial: let $f_1,\dots,f_{k-1}$ and $g_1,\dots,g_{k-1}$ be arbitrary, and let $f_k=f_1g_1+\cdots+f_{k-1}g_{k-1}+1$; then $f_1,\dots,f_k$ have no common zeros. –  Gerry Myerson Dec 11 '10 at 21:38
show 3 more comments

1 Answer

Not known. Your problem is $NP_\mathbf{C}$-complete in the Blum-Shub-Smale complexity model. So anything significantly simpler than Groebner basis would yield significant progress on the $P=NP$ question over $\mathbf{C}$ compared to the current state of the art.

share|improve this answer
    
Hmm. I thought this was what the resultant was for. Certainly works for $n=1$, $k=2$, and there is such a thing as the resultant in more general cases. –  Gerry Myerson Dec 11 '10 at 5:19
    
@Gerry: yes, resultants might be suitable depending on the OP's purpose, but it does not change anything to the complexity point of view. Deciding common zeroes is hard. –  Thierry Zell Dec 11 '10 at 5:43
    
@Thierry: I suppose that deciding whether a given real number is zero is hard, in some model. Yet in practice I rarely have any trouble with this. Perhaps we need ougao to give us a little more context; among other things, how does ougao propose to choose polynomials "randomly"? Reference to "algebraic properties" and Eisenstein criterion suggest maybe integer coefficients in mind. I'm tempted to vote to close as "not a real question" until/unless ougao comes up with the goods. –  Gerry Myerson Dec 11 '10 at 8:51
    
@Gerry: When I posted my answer, I was hoping that the OP would comment on my answer, and let us know if the complexity point of view was relevant to the original motivation. I wouldn't go as far as saying that we don't have a real question right now, but in the current state, it looks like a question with no definitive answer; the complexity point of view is only one possible angle, and it would be nice to see others. –  Thierry Zell Dec 11 '10 at 11:51
    
Sorry for my ambiguous words, I just want to say that when I write down some polynomials, I want to detect whether they have no common zeros, if not, then maybe I can go to search the coefficients $g_i$,or at least say something on them. –  Jiang Dec 11 '10 at 17:33
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.