1
$\begingroup$

I have the system of multi-variable polynomial (quadratic) equations with real coefficients. The number of equations is given scales as $K$ and the number of unknowns goes as $K^2$. So for for large $K$, this is an underdetermined system.

Can I conclude that I can always find $K$ large enough so that this system has at least one real solution or where should I look for counterexamples?

Improve this question
$\endgroup$
2
  • $\begingroup$ Where is algebraic geometry here? Consider any subsystem of $(2m)^2$ equations from the system $$x_{i_1}^2+\dots+x_{i_m}^2+1=0$$ where $\lbrace i_1,\dots,i_m\rbrace$ is any subset of the set $\lbrace 1,2,\dots,2m\rbrace$. $\endgroup$
    – Wadim Zudilin
    Commented Aug 3, 2010 at 6:04
  • 1
    $\begingroup$ I think that the real Nullstellensatz is a theorem in real algebraic geometry. $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 3, 2010 at 14:37

2 Answers 2

Reset to default
5
$\begingroup$

However large $n$ may be, the equation

$x_1^2 + \ldots + x_n^2 = -1$ has no real solution.

(Similarly, the homogeneous equation $x_1^2 + \ldots + x_n^2 = 0$ has no nontrivial solution.)

If you want to go there, the theorem which gives you a necessary and sufficient condition for a system of real polynomial equations to have a real solution is the Real Nullstellensatz. See for instance Section 3.9` of

http://alpha.math.uga.edu/~pete/modeltheory2010Chapter3.pdf

(Very roughly, this theorem says that the above is essentially the only way that a system of $n$ real polynomial equations in more than $n$ variables can fail to have a real solution.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. This was a very helpful answer. But now I have a related question. How practical is Real Nullstellensatz for analyzing large systems with e.g. 12 equations and 12-15 unknowns, 16 equations and 16-24 unknowns, etc. Or is using this theorem similar to computing Groebner Basis and quickly becomes infeasible? $\endgroup$
    – Raisa
    Commented Aug 4, 2010 at 22:37
  • $\begingroup$ @Raisa: you're welcome. Your followup is very interesting (and I can't answer it!). From the description of the Real Nullstellensatz I gave in my notes, it is not even clear that it is algorithmic, but it is: for instance, this follows from the decidability of real-closed fields. The algorithm that you would get by looking at it that way (e.g. via explicit quantifier elimination) is probably painfully slow. I am pretty sure that finding better algorithms for solving real polynomial systems is an active research field. I encourage you to ask another question about this. $\endgroup$
    – Pete L. Clark
    Commented Aug 4, 2010 at 23:09
2
$\begingroup$

If you're dealing with finding solutions to a specific system, the traditional method is cylindrical algebraic decomposition, described for instance in Algorithms in Real Algebraic Geometry by Saugata Basu, Richard Pollack, Marie-Françoise Roy downloadable HERE. This method is widely implemented in many computer algebra packages. An alternative method is the critical point method, which was implemented in Maple by Mohab Safey El Din (LINK). (Both methods eventually use Groebner bases b the way.)

This might let you experiment, but I doubt that these methods alone can give you all you need to know about a family of systems. Solving over the reals is harder than over the complexes (because the interplay between algebra and geometry is less straightforward). There is active research on the algorithmic aspects of the real Nullstellensatz, (e.g. M. Coste, H. Lombardi, M.-F. Roy. Dynamical method in algebra: efective Nullstellensatze, Annals of Pure and Applied Logic, 111, 203-256 (2001)), but the complexity is even worse than Groebner bases.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .