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

Given a system of multivariate, polynomial equations, is there a way to determine if it has a solution in a given field (for instance the set of all reals). I don't care what the solution is, I just want to know if one exists or not.

I understand that one approach would be to determine a Groebner Basis (or lack thereof), but it appears to be problematic over the reals.

The systems contain polynomials of two forms:

1) $(a-b)^2+(c-d)^2-1=0$
2) $z^2[(a-b)^2+(c-d)^2]-1=0$

share|improve this question
    
Seeing such equations, I'm tempted to ask whether your system is actually "the distance problem" on the plane. –  fedja Jun 3 '11 at 23:38
    
Yes, however I'd be also be interested in knowing if this is possible in general for any polynomial system over the reals. –  Dirge Jun 4 '11 at 1:37

1 Answer 1

up vote 8 down vote accepted

The answer over the reals is a resounding yes: not only can you decide if the system has solutions, but you can even produce them (over other fields, not so much, e.g. $\mathbb{Q}$).

The decision problem was solved by Tarski (and later Seidenberg). Though the proof gave a theoretical way of finding solutions, it was not a practical one.

If you want to produce solutions, and if your system is zero-dimensional (over the complexes), then your problem is simply to determine if one of the solutions is real. First find a Grobner basis for your ideal. Through the use of a separating element in the quotient ring $\mathbb{C}[X]/I$, you can reduce to a question to determining if a certain univariate polynomial has real roots, which can be done with a Sturm sequence.

The positive dimensional case can be tackled by a variation on this theme, by producing a zero-dimensional system contained in your variety (by taking the critical locus of suitable functions). It's easier said than done, but software solving these kinds of problem has now been around for almost 10 years. These algorithms can be modified to handle inequalities as well as equations.

Another approach to these problems is the Cylindrical Algebraic Decomposition which is much slower, has larger output, but has the added advantage handling inequalities without needing a different algorithm.

The best reference for this is the Springer book Algorithms in Real Algebraic Geometry by Saugata Basu, Richard Pollack, and Marie-Françoise Roy. It is freely downloadable from that link. Nowadays, even generalist Computer Algebra Systems such as Maple or Mathematica have decent implementations of these algorithms that can breeze through your example and others of the same caliber.

share|improve this answer

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.