5
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Seeing such equations, I'm tempted to ask whether your system is actually "the distance problem" on the plane. $\endgroup$
    – fedja
    Jun 3, 2011 at 23:38
  • $\begingroup$ Yes, however I'd be also be interested in knowing if this is possible in general for any polynomial system over the reals. $\endgroup$
    – Dirge
    Jun 4, 2011 at 1:37
  • $\begingroup$ Hi, I saw in the comment you made to the only answer of this post that you wanted to know how to find certain univariate polynomial. Did you eventually find such algorithm? $\endgroup$
    – Esteban G.
    Apr 17, 2023 at 15:06

1 Answer 1

14
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Quote: "First find a Grobner basis for your ideal. Through the use of a separating element in the quotient ring C[X]/I, you can reduce to a question to determining if a certain univariate polynomial has real roots". Can you elaborate a bit on the algorithm that gives me the univariate polynomial? $\endgroup$
    – image357
    Sep 18, 2017 at 13:19
  • 1
    $\begingroup$ @image357 - See Algorithm 12.11 here: perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.pdf $\endgroup$ Feb 10 at 23:04

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.