Intuition for Model Theoretic Proof of the Nullstellensatz

I recently read the model-theoretic proof of the Nullstellensatz using quantifier elimination (see www.msri.org/publications/books/Book39/files/marker.pdf). I'm convinced that the Nullstellensatz is true, i.e. by showing that $\exists y_1 \cdots \exists y_n (\bigwedge_{i} (f_i(y) = 0)$ is equivalent to a quantifier free formula, hence if it is true in an algebraically closed extension, it is true in the original algebraically closed field. However, I don't have any intuition for how this formal sequence of steps leads to the truth of the Nullstellensatz. In particular, what I don't see is what the quantifier-free formulas are that these are equivalent to. For example, what is a quantifier-free formula in $a,b,c,d,e,f,g,h,i,j,k,l$ which is equivalent to the system $ax^2+bxy+cy^2+dx+ey+f=gx^2+hxy+iy^2+jx+ky+l=0$ having a non-trivial solution? And generalizations?

Can one simplify the model-theoretic proof by showing more directly that the existence of solutions to systems of equations (or non-equations) in algebraically closed fields are equivalent to polynomial conditions on the coefficients? I.e. apply essentially the same argument but restrict to the case of algebraically closed fields and avoid general results like Godel's Completeness Theorem to make the argument more clear. My expectation is that this might involve proving an algorithm for determining the quantifier-free formula from the formula with quantifiers.

-
Note that I have answered my request for an algorithmic proof of the Nullstellensatz in my answer below. – David Corwin Jul 28 '10 at 9:32
Elimination theory was very well understood and algorithmic back in the 19th century. The early 20th century moved away from these concerns, which is a loss, however legitimate the move. In section 21 of his Historical Ramblings in Algebraic Geometry and Related Algebra, Abhyankar famously quotes Weil: "The device that follows, which, it may be hoped, ﬁnally eliminates from algebraic geometry the last traces of elimination theory [...]". This passage has been quoted many times since by those who wholeheartedly agree that elimination was put to rest prematurely. – Thierry Zell Dec 11 '10 at 14:35

Your example is not an illuminating one, because you used two equations in two variables. You would therefore expect there, generically, to be a solution for most values of $(a,b,\ldots, l)$. I'll get back to your example, but let's start with the more informative case of two equations in one variable. Then I'll use this as an excuse to talk about properness.

Starting very small, when do $ax+b=0$ and $cx+d=0$ have a common root? Answer: We must have $ad-bc =0$. In addition, we must either have $a$ and $c \neq 0$, or else $a=b=0$, or else $c=d=0$. So, there is a polynomial $ad-bc$ which basically cuts out the location where the two polynomials have a common root, but we then have to remove some smaller strata by inequalities.

More generally, when do $f_m x^m + f_{m-1} x^{m-1} + \cdots + f_0=0$ and $g_n x^n + g_{n-1} x^{n-1} + \cdots + g_0=0$ have a common root? The polynomial which plays the role of $ad-bc$ is the determinant $$R(f,g) := \det \left( \begin{matrix} f_m & f_{m-1} & \cdots & f_0 & 0 & \cdots & 0 \\ 0 & f_m & f_{m-1} & \cdots & f_0 & \cdots & 0 \\ \ddots \\ 0 & \cdots & 0 & f_m & f_{m-1} & \cdots & f_0 \\ g_n & g_{n-1} & \cdots & g_0 & 0 & \cdots & 0 \\ 0 & g_n & g_{n-1} & \cdots & g_0 & \cdots & 0 \\ \ddots \\ 0 & \cdots & 0 & g_m & g_{m-1} & \cdots & g_0 \end{matrix} \right)$$

There are $n$ rows in the first block and $m$ in the second block. The determinant $R(f,g)$ vanishes if and only if there are polynomials $a$ and $b$, of degree $n-1$ and $m-1$, so that $af+bg=0$. It is easy to see that this is true if and only if either (1) $f$ and $g$ have a common root or (2) $f_m = g_n =0$. The little nuisance terms come up in ruling out case (2).

The polynomial $R$ is called the resultant. If you wnat to learn more about this, including generalizations to more polynomials in more variables, the terms to search for are "resultant" and "elimination theory". Standard references are Using Algebraic Geometry by Cox, Little and O'Shea and Discriminants, resultants, and multidimensional determinants by Gelfand, Kapranov and Zelevinsky.

The awkward thing about your chosen example is that the analogue of the resultant is $0$, and you only have correction terms. I don't really feel like working it out.

The theory looks much prettier if we use homogeneous polynomials. For example, $ax+by$ and $cx+dy$ have a common nonzero root if and only if $ad-bc=0$, with no special cases. Two homogeneous quadratics in three variables always have a common root.

Here is the big result about homogeneous polynomials: Let $S$ be the ring $\mathbb{C}[t_1, \ldots, t_k, x_0, x_1, \ldots, x_n]$. We think of the $t$'s as parameters and the $x$'s as the homogeneous coordinates. Let $F_1(x, t)$, ..., $F_N(x, t)$ be any collection of polynomials, homogeneous in the $x$'s. Then there are polynomials $G_1(t)$, ..., $G_M(t)$ such that, given a point $(s_1, \ldots, s_k) \in \mathbb{C}^k$, there is a nonzero common root of the $F_i(s, x)$ if and only if $G_1(s) = \cdots = G_M(s)=0$.

This theorem is better phrased in the language of the Zariski topology. I don't know how much algebraic geometry you've taken. A subset of $\mathbb{C}^k$ is called Zariski closed if it is the zero locus of a set of polynomials. So the statement here is the following:

If we have a Zariski closed subset of $\mathbb{CP}^n \times \mathbb{C}^k$, then its projection to $\mathbb{C}^k$ is Zariski closed.

In other words,

The mapping $\mathbb{CP}^n \times \mathbb{C}^k \to \mathbb{C}^k$ is closed.

The corresponding statement is NOT true for $\mathbb{C}^n$. Consider the subset of $\mathbb{C} \times \mathbb{C}$ cut out by $xy=1$. This hyperbola is closed. But the projection onto one of the coordinates is $\{ x \neq 0 \}$, which is not closed.

Now, in fact, a stronger statement is true:

For any variety $B$, the mapping $\mathbb{CP}^N \times B \to B$ is closed.

We express this by saying that $\mathbb{CP}^N$ is universally closed.

If you get far enough in algebraic geometry, you'll run across the theorem that projective space is proper. The definition of proper is universally closed, plus some other conditions which we can ignore for now. So this theorem is the highly abstract way of making the statement about $F$'s and $G$'s above. Hopefully, I have given you something to look forward to as you continue in algebraic geometry!

-

The problem you are asking about is called elimination theory ( http://en.wikipedia.org/wiki/Elimination_theory ), which shows how to eliminate unknown variables x, y, ... from sets of polynomial equations. One of the major tools for doing this explicitly is the resultant ( http://en.wikipedia.org/wiki/Resultant ) of 2 polynomials, that gives polynomial conditions on their coefficients for them to have a common root.

Carrying out these calculations is too messy to do by hand except for small examples, though some computer algebra systems are now quite good at it.

-

After some more searching, I found the notes written by Ford for an REU. These notes prove the Nullstellensatz using model theory, though the presentation is a little bit more concrete than that in Marker's notes.

On page 7, in Theorem 4.3, the notes prove quantifier elimination for ACF without reference to any preceding lemmas. The basic idea is this: First note that we only need consider formulas of the form $\exists x \phi(\bar{v},x)$. In other words, if our system of equations has $n$ variables, we need to first find quantifier-free conditions on $x_1,\cdots,x_{n-1}$ which will give the system of equations a solution in $x_n$. (In general, we will be dealing with a system of equations and inequations joined by and/or, but I ignore that for simplicity). Next, we find conditions which will make those conditions have a solution in $x_{n-1}$, etc. Repeating this process, we have a series of algebraic equations and inequations in the coefficients of the polynomials joined by and/or which gives a necessary and sufficient condition for the equation to have solutions.

Thus the problem is to find an algebraic condition (i.e. a sequence of expressions of the form $p(x)=0$ and $p(x) \neq 0$ joined by and/or operators) on the coefficients $\bar{v}$ of a system of $m$ equations in one variable $x$ which will ensure that the equations have a solution over an algebraically closed field.

To give a rough sketch, assume our system contains at least two non-constant polynomials in $x$, with degrees $1 \le d_1 \le d_2$ and leading coefficients $a_i(\bar{v})$. Then our new condition is $$(a_1(\bar{v})=0 \wedge p_1(x)-a_1(\bar{v})x^{d_1}=0 \wedge p_2(x)=0 \wedge\cdots \wedge p_m(x)=0) \vee (a_1(\bar{v}) \neq 0 \wedge p_1(x)=0 \wedge a_1(\bar{v})p_2(x)-a_2(\bar{v}) x^{d_2-d_1} p_1(x) = 0 \wedge p_3(x)=0 \wedge \cdots \wedge p_m(x)=0)$$ The sums of the degrees of the polynomials is smaller than before, and we can repeat this process until we don't have at least two non-constant polynomials. Then we use the Euclidean algorithm to deal with the $\neq$, and we are done.

What's nice is that this actually gives an elementary and algorithmic proof of the Nullstellensatz: first reduce the existence of a solution over an algebraically closed field to a system of equations and inequations in the coefficients. Next, note that there is a solution over some algebraically closed extension. Therefore, the coefficients satisfy the necessary conditions, so there is a solution over our original algebraically closed field, and we are done. I believe this is correct and much simpler than the one which Terry Tao provides.

Now we tackle the example which I give (again, a relatively rough sketch). We want to find conditions on $a,b,c,d,e,f,g,h,i,j,k,l,x$ which ensure that the equations have a solution in $y$.

Let the first equation be $p_1$, the second $p_2$. We thus reduce it to either $c=0$ and $(e+bx)y+ax^2+dx+f=iy^2+(hx+k)y+gx^2+jx+l=0$ (Case 1) or $c \neq 0$ and $cy^2+(e+bx)y+ax^2+dx+f= (chx+ck-ie-ibx)y+cgx^2+cjx+cl-iax^2-idx-if=0$ (Case 2).

In Case 1, the first polynomial is $p_1$, the second is $p_2$, and if $e+bx=0$, the equation having a solution is equivalent to $ax^2+dx+f=0$ and either $i \neq 0$ or $hx+k \neq 0$ or $gx^2+jx+l=0$. If $e+bx \neq 0$, we subtract $iy$ times the first polynomial from $e+bx$ times the first to get $(e+bx)(iy^2+(hx+k)y+gx^2+jx+l)-iy((e+bx)y+ax^2+dx+f)=$ $bx gx^2 + e gx^2 + bx hx + e hx - ax^2 iy - bx iy - dx iy - e iy - f iy + bx iy^2 + e iy^2 + bx jx + e jx + bx k + e k + bx l + e l$ We now have a system of simultaneous linear equations, so to check whether there's a solution, we only need to check whether each has a solution and, degenerate cases aside, whether a certain determinant is $0$, i.e. an algebraic condition.

In Case 2, the first polynomial is $p_2$, the second is $p_1$. If $chx+ck-ie-ibx=0$, then the existence of a solution is equivalent to $cgx^2+cjx+cl-iax^2-idx-if=0$ and either $c \neq 0$, $e+bx \neq 0$, or $ax^2+dx+f=0$. If $chx+ck-ie-ibx \neq 0$, then we compute $(chx+ck-ie-ibx)(cy^2+(e+bx)y+ax^2+dx+f)-cy((chx+ck-ie-ibx)y+cgx^2+cjx+cl-iax^2-idx-if)=$ $ax^2 chx + ax^2 ck - cgx^2 cy - cjx cy - cl cy + chx cy^2 + ck cy^2 + chx dx + ck dx + chx f + ck f + cy iax^2 - ax^2 ibx - cy^2 ibx - dx ibx - f ibx + cy idx - ax^2 ie - cy^2 ie - dx ie - f ie + cy if$. We then proceed as in Case 1.

-
I am currently teaching a short summer course on basic model theory and its applications, and just yesterday I proved elimination of quantifiers for ACF. So I just now looked at Ford's notes with a critical eye and: two thumbs up. This is a very nice exposition. – Pete L. Clark Jul 28 '10 at 8:06
Not really on-topic here, but is it just me or does Ford mess up some notation in his (otherwise quite nice) paper? It seems to me that his mistake is to go with the satisfiability semantics for $\models$ shortly before Definition 2.2 ("Finally, if $\phi\left(\overline{v}\right)$ is a formula, then we say $T\models\phi\left(\overline{v}\right)$ if for every model $A$ of $T$, there is a sequence $\overline{a}$ of elements of $A$ such that $A\models \left(\overline{a}\right)$."). As a consequence of this, $T\models \left(\phi\leftrightarrow\phi^{\prime}\right)$ in Definition 3.4 doesn't ... – darij grinberg Dec 6 '11 at 18:46
... mean what it is supposed to mean: instead of actual equivalence between $\phi$ and $\phi^{\prime}$, it just guarantees the existence of some assignment of free variables for which either both $\phi$ and $\phi^{\prime}$ hold or none does. – darij grinberg Dec 6 '11 at 18:47