# Real solutions to underdetermined system of polynomial equations

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?

-
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$. –  Wadim Zudilin Aug 3 '10 at 6:04
I think that the real Nullstellensatz is a theorem in real algebraic geometry. –  Tsuyoshi Ito Aug 3 '10 at 14:37

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://www.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.)

-
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? –  Raisa Aug 4 '10 at 22:37
@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. –  Pete L. Clark Aug 4 '10 at 23:09