6
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ The plural of criterion is criteria. $\endgroup$
    – Chandan Singh Dalawat
    Dec 11, 2010 at 7:54
  • $\begingroup$ Yes - minor editing carried out. $\endgroup$
    – Gerry Myerson
    Dec 11, 2010 at 8:53
  • $\begingroup$ @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. $\endgroup$
    – Jose Arnaldo Bebita Dris
    Dec 11, 2010 at 9:17
  • 2
    $\begingroup$ 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). $\endgroup$
    – Igor Rivin
    Dec 11, 2010 at 16:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Dec 11, 2010 at 21:38

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Dec 11, 2010 at 5:19
  • $\begingroup$ @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. $\endgroup$
    – Thierry Zell
    Dec 11, 2010 at 5:43
  • $\begingroup$ @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. $\endgroup$
    – Gerry Myerson
    Dec 11, 2010 at 8:51
  • $\begingroup$ @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. $\endgroup$
    – Thierry Zell
    Dec 11, 2010 at 11:51
  • $\begingroup$ 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. $\endgroup$
    – Jiang
    Dec 11, 2010 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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