I had occasion recently to look up the proof of Hilbert’s nullstellensatz, which I haven’t studied since cramming for my algebra qualifying exam as a graduate student. I was a little unsatisfied with the proofs I was able to locate – they were fairly abstract and used a certain amount of algebraic machinery, which I was terribly rusty on – so, as an exercise, I tried to find a more computational proof that avoided as much abstract machinery as possible. I found a proof which used only the extended Euclidean algorithm and high school algebra, together with an induction on dimension and the obvious observation that any non-zero polynomial of one variable on an algebraically closed field has at least one non-root. It probably isn’t new (in particular, it might be related to the standard model-theoretic proof of the nullstellensatz, with the Euclidean algorithm and high school algebra taking the place of quantifier elimination), but I thought I’d share it here anyway.

Throughout this post, F is going to be a fixed algebraically closed field (e.g. the complex numbers {\Bbb C}). I’d like to phrase the nullstellensatz in a fairly concrete fashion, in terms of the problem of solving a set of simultaneous polynomial equations P_1(x) = \ldots = P_m(x) = 0 in several variables x = (x_1,\ldots,x_d) \in F^d over F, thus P_1,\ldots,P_m \in F[x] are polynomials in d variables. One obvious obstruction to solvability of this system is if the equations one is trying to solve are inconsistent in the sense that they can be used to imply 1=0. In particular, if one can find polynomials Q_1,\ldots,Q_m \in F[x] such that P_1 Q_1 + \ldots + P_m Q_m = 1, then clearly one cannot solve P_1(x)=\ldots=P_m(x)=0. The weak nullstellensatz asserts that this is, in fact, the only obstruction:

Weak nullstellensatz. Let P_1,\ldots,P_m \in F[x] be polynomials. Then exactly one of the following statements holds:

  1. The system of equations P_1(x)=\ldots=P_m(x)=0 has a solution x \in F^d.
  2. There exist polynomials Q_1,\ldots,Q_m \in F[x] such that P_1 Q_1 + \ldots + P_m Q_m = 1.

Note that the hypothesis that F is algebraically closed is crucial; for instance, if F is the reals, then the equation x^2+1=0 has no solution, but there is no polynomial Q(x) such that (x^2+1) Q(x) = 1.

Like many results of the “The only obstructions are the obvious obstructions” type, the power of the nullstellensatz lies in the ability to take a hypothesis about non-existence (in this case, non-existence of solutions to P_1(x)=\ldots=P_m(x)=0) and deduce a conclusion about existence (in this case, existence of Q_1,\ldots,Q_m such that P_1 Q_1 + \ldots + P_m Q_m = 1). The ability to get “something from nothing” is clearly going to be both non-trivial and useful. In particular, the nullstellensatz offers an important correspondence between algebraic geometry (the conclusion 1 is an assertion that a certain algebraic variety is empty) and commutative algebra (the conclusion 2 is an assertion that a certain ideal is non-proper).

Now suppose one is trying to solve the more complicated system P_1(x)=\ldots=P_d(x)=0; R(x) \neq 0 for some polynomials P_1,\ldots,P_d, R. Again, any identity of the form P_1 Q_1 + \ldots + P_m Q_m = 1 will be an obstruction to solvability, but now more obstructions are possible: any identity of the form P_1 Q_1 + \ldots + P_m Q_m = R^r for some non-negative integer r will also obstruct solvability. The strong nullstellensatz asserts that this is the only obstruction:

Strong nullstellensatz. Let P_1,\ldots,P_m, R \in F[x] be polynomials. Then exactly one of the following statements holds:

  1. The system of equations P_1(x)=\ldots=P_m(x)=0, R(x) \neq 0 has a solution x \in F^d.
  2. There exist polynomials Q_1,\ldots,Q_m \in F[x] and a non-negative integer r such that P_1 Q_1 + \ldots + P_m Q_m = R^r.

Of course, the weak nullstellensatz corresponds to the special case in which R=1. The strong nullstellensatz is usually phrased instead in terms of ideals and radicals, but the above formulation is easily shown to be equivalent to the usual version (modulo Hilbert’s basis theorem).

One could consider generalising the nullstellensatz a little further by considering systems of the form P_1(x)=\ldots=P_m(x)=0, R_1(x),\ldots,R_n(x) \neq 0, but this is not a significant generalisation, since all the inequations R_1(x) \neq 0, \ldots, R_n(x) \neq 0 can be concatenated into a single inequation R_1(x) \ldots R_n(x) \neq 0. The presence of the exponent r in conclusion (2) is a little annoying; to get rid of it, one needs to generalise the notion of an algebraic variety to that of a scheme (which is worth doing for several other reasons too, in particular one can now work over much more general objects than just algebraically closed fields), but that is a whole story in itself (and one that I am not really qualified to tell).

[Update, Nov 26: It turns out that my approach is more complicated than I first thought, and so I had to revise the proof quite a bit to fix a certain gap, in particular making it significantly messier than my first version. On the plus side, I was able to at least eliminate any appeal to Hilbert’s basis theorem, so in particular the proof is now manifestly effective (but with terrible bounds). In any case, I am keeping the argument here in case it has some interest.]

— The base case d=1 —

I had initially posted here an attempted proof of the weak nullstellensatz by induction on dimension, and then deduced the strong nullstellensatz from the weak via a lifting trick of Zariski (the key observation being that the inequation x \neq 0 was equivalent to the solvability of the equation xy-1 = 0 for some y). But I realised that my proof of the weak nullstellensatz was incorrect (it required the strong nullstellensatz in one lower dimension as the inductive hypothesis), and so now I am proceeding by establishing the strong nullstellensatz directly.

We shall induct on the dimension d (i.e. the number of variables in the system of equations).

The case d=0 is trivial, so we use the d=1 case as the base case, thus P_1, \ldots, P_m, R are all polynomials of one variable. This case follows easily from the fundamental theorem of algebra, but it will be important for later purposes to instead use a more algorithmic proof in which the coefficients of the polynomials Q_1,\ldots,Q_m required for (2) are obtained from the coefficients of P_1, \ldots, P_m, R in an explicitly computable fashion (using only the operations of addition, subtraction, multiplication, division, and branching on whether a given field element is zero or non-zero). In particular, one does not need to locate roots of polynomials in order to construct Q_1,\ldots,Q_m (although one will of course need to do so to locate a solution x to (1)). [It is likely that one could get these sorts of computability properties on Q_1,\ldots,Q_m “for free” from Galois theory, but I have not attempted to do so.] It is however instructive to secretly apply the fundamental theorem of algebra throughout the proof which follows, to clarify what is going on.

Let us say that a collection (P_1,\ldots,P_m; R) of polynomials obeys the nullstellensatz if at least one of (1) and (2) is true. It is clear that (1) and (2) cannot both be true, so to prove the nullstellensatz it suffices to show that every collection (P_1,\ldots,P_m; R) obeys the nullstellensatz.

We can of course throw away any of the P_i that are identically zero, as this does not affect whether (P_1,\ldots,P_m;R) obeys the nullstellensatz. If none of the P_i remain, then we are in case (1), because the polynomial R has at most finitely many zeroes, and because an algebraically closed field must be infinite. So suppose that we have some non-zero P_i. We repeatedly use the extended Euclidean algorithm to locate the greatest common divisor D(x) of the remaining P_i. Note that this algorithm automatically supplies for us some polynomials Q_1(x),\ldots,Q_m(x) such that

P_1(x) Q_1(x) + \ldots + P_m(x) Q_m(x) = D(x).

Because of this, we see that (P_1,\ldots,P_m;R) obeys the nullstellensatz if and only if (D;R) obeys the nullstellensatz. So we have effectively reduced to the case m=1.

Now we apply the extended Euclidean algorithm again, this time to D and R, to express the gcd D’ of D and R as a combination D’ = D A + R B, and also to factor D = D’ S and R = D’ T for some polynomials A, B, S, T with AS + BT = 1. A little algebra then shows that one has a solution to the problem

D(x) = 0; R(x) \neq 0

whenever one has a solution to the problem

S(x) = 0; D'(x) \neq 0.

Also, if some power of D’ is a multiple of S, then some power of R is a multiple of D. Thus we see that if (S; D’) obeys the nullstellensatz, then (D; R) does also. But we see that the net degree of S and D’ is less than the net degree of D and R unless R is constant, so by infinite descent we may reduce to that case. If R is zero then we are clearly in case (2), so we may assume R is non-zero. If D is constant then we are again in case (2), so assume that D is non-constant. But then as the field is algebraically closed, D has at least one root, and so we are in case (1). This completes the proof of the d=1 case.

For the inductive step, it is important to remark that the above proof is algorithmic in the sense that a computer which was given the coefficients for P_1,\ldots,P_m,R as inputs could apply a finite number of arithmetic operations (addition, subtraction, multiplication, division), as well as a finite number of branching operations based on whether a given variable was zero or non-zero, in order to output either

  1. the coefficients of a non-constant polynomial D with the property that any root x of D would solve (1);
  2. the coefficients of a non-zero polynomial R with the property that any non-root x of R would solve (1); or
  3. the coefficients of polynomials Q_1,\ldots,Q_m which solved (2) for some specific r.

In most cases, the number of branching operations is rather large (see for instance the example of solving two linear equations below). There is however one simple case in which only one branching is involved, namely when m=2, R=1, and P_1, P_2 are monic. In this case, we have an identity of the form

P_1 S_1 + P_2 S_2 = \hbox{Res}(P_1,P_2)

where S_1,S_2 are polynomials (whose coefficients are polynomial combinations of the coefficients of P_1 and P_2 and \hbox{Res}(P_1,P_2) \in F is the resultant of P_1 and P_2, which is another polynomial combination of the coefficients of P_1 and P_2. If the resultant is non-zero then we have

\frac{1}{\hbox{Res}(P_1,P_2)} S_1 P_1 + \frac{1}{\hbox{Res}(P_1,P_2)} S_2 P_2 = 1

and so the system is unsolvable (we are in case (2)); otherwise, the system is solvable.

— The inductive case d>1 —

Now we do the inductive case, when d \geq 2 and the claim has already been proven for d-1. The basic idea is to view the system (1) not as a system of equations in d unknowns, but as a d-1-dimensional family of systems in one unknown. We will then apply the d=1 theory to each system in that family and use the algorithmic nature of that theory to glue everything together properly.

We write the variable x \in F^d as x = (y, t) for y \in F^{d-1} and t \in F. The ring F[x] of polynomials in d variables can thus be viewed as a ring F[y][t] of polynomials in one variable t, in which the coefficients lie in the ring F[y].

Let I be the ideal in F[x] generated by P_1,\ldots,P_m. We either need to solve the system

P_1(y,t) = \ldots = P_m(y,t) = 0; R(y,t) \neq 0 (1)

or show that

R^r = 0 \hbox{ mod } I for some r. (2)

We assume that no solution to (1) exists, and use this to synthesise a relation of the form (2).

Let y \in F^{d-1} be arbitrary. We can view the polynomials P_1(y,t),\ldots,P_m(y,t), R(y,t) as polynomials in F[t], whose coefficients lie in F but happen to depend in a polynomial fashion on y. To emphasise this, we write P_{j,y}(t) for P_j(y,t) and R_{y}(t) for R(y,t). Then by hypothesis, there is no t for which

P_{1,y}(t) = \ldots = P_{m,y}(t) = 0; R_{y}(t) \neq 0.

To motivate the strategy, let us consider the easy case when R = 1, m=2, and P_1, P_2 are monic polynomials in t. Then by our previous discussion, the above system is solvable for any fixed y precisely when \hbox{Res}(P_{1,y}, P_{2,y}) is zero. So either the equation \hbox{Res}(P_{1,y}, P_{2,y}) = 0 has a solution, in which case we are in case (1), or it does not. But in the latter case, by applying the nullstellensatz at one lower dimension we see that \hbox{Res}(P_{1,y}, P_{2,y}) must be constant in y. But recall that the resultant is a linear combination P_{1,y} S_{1,y} + P_{2,y} S_{2,y} of P_{1,y} and P_{2,y}, where the polynomials S_{1,y} and S_{2,y} depend polynomially on P_{1,y} and P_{2,y} and thus on y itself. Thus we end up in case (2), and the induction closes in this case.

Now we turn to the general case. Applying the d=1 analysis, we conclude that there exist polynomials Q_{1,y},\ldots,Q_{m,y} \in F[t] of t, and an r = r_{y} \geq 0, such that

P_{1,y}(t) Q_{1,y}(t) + \ldots + P_{m,y}(t) Q_{m,y}(t) = R^{r_{y}}_{y}(t). (3)

Now, if the exponent r_{y} was constant in y, and the coefficients of Q_{1,y},\ldots,Q_{m,y} depended polynomially on y, we would be in case (2) and therefore done.

It is not difficult to make r_{y} constant in y. Indeed, we observe that the degrees of P_{1,y}(t),\ldots,P_{m,y}(t) are bounded uniformly in y. Inspecting the d=1 analysis, we conclude that the exponent r_{y} returned by that algorithm is then also bounded uniformly in y. We can always raise the value of r_{y} by multiplying both sides of (3) by R_{y}, and so we can make r = r_{y} independent of y, thus

P_1(y,t) Q_{1,y}(t) + \ldots + P_m(y,t) Q_{m,y}(t) = R^r(y,t). (4)

Now we need to work on the Q’s. Unfortunately, the coefficients on Q are not polynomial in y; instead, they are piecewise rational in y. Indeed, by inspecting the algorithm used to prove the d=1 case, we see that the algorithm makes a finite number of branches, depending on whether certain polynomial expressions T(y) of y are zero or non-zero. At the end of each branching path, the algorithm returns polynomials Q_{1,y},\ldots,Q_{m,y} whose coefficients were rational combinations of the coefficients of P_{1,y},\ldots,P_{m,y} and are thus rational functions of x. Furthermore, all the division operations are by polynomials T(y) which were guaranteed to be non-zero by some stage of the branching process, and so the net denominator of any of these coefficients is some product of the T(y) that are guaranteed non-zero.

An example might help illustrate what’s going on here. Suppose m=2, that R = 1, and P_1(y,t), P_2(y,t) is linear in t, thus

P_{1,y}(t) = a(y) + t b(y); P_{2,y}(t) = c(y) + t d(y)

for some polynomials a,b,c,d \in F[y]. To find the gcd of P_{1,y} and P_{2,y} for a given y, which determines the solvability of the system P_{1,y}(t)=P_{2,y}(t)=0, the Euclidean algorithm branches as follows:

  1. If b(y) is zero, then
    1. If a(y) is zero, then
      1. If d(y) is non-zero, then 0 P_{1,y} + \frac{1}{d(y)} P_{2,y} is the gcd (and the system is solvable).
      2. Otherwise, if d(y) is zero, then
        1. If c(y) is non-zero, then 0 P_{1,y} + \frac{1}{c(y)} P_{2,y} = 1 is the gcd (and the system is unsolvable).
        2. Otherwise, if c(y) is zero, then 0 P_{1,y} + 0 P_{2,y} is the gcd (and the system is solvable).
    2. Otherwise, if a(y) is non-zero, then \frac{1}{a(y)} P_{1,y} + 0 P_{2,y} = 1 is the gcd (and the system is unsolvable).
  2. Otherwise, if b(y) is non-zero, then
    1. If a(y)d(y)-b(y)c(y) is non-zero, then \frac{d(y)}{a(y) d(y)-b(y)c(y)} P_{1,y} - \frac{b(y)}{a(y) d(y)-b(y)c(y)} P_{2,y} = 1 is the gcd (and the system is unsolvable).
    2. Otherwise, if a(y)d(y)-b(y)c(y) is zero, then \frac{1}{b(y)} P_{1,y} + 0 P_{2,y} is the gcd (and the system is solvable).

So we see that even in the rather simple case of solving two linear equations in one unknown, there is a moderately complicated branching tree involved. Nevertheless, there are only finitely many branching paths. Some of these paths may be infeasible, in the sense that there do not exist any y \in F^{d-1} which can follow these paths. But given any feasible path, say one in which the polynomials S_1(y),\ldots,S_a(y) are observed to be zero, and T_1(y),\ldots,T_b(y) are observed to be non-zero, we know (since we are assuming no solution to (1)) that the algorithm creates an identity of the form (4) in which the coefficients of Q_{1,y},\ldots,Q_{m,y} are rational polynomials in y, whose denominators are products of T_1,\ldots,T_b. We may thus clear denominators (enlarging r if necessary) and obtain an identity of the form

P_1(y,t) U_1(y,t) + \ldots + P_m(y,t) U_m(y,t) = (T_1(y) \ldots T_b(y) R(y))^r (5)

for some polynomials U_1,\ldots,U_m. This identity holds whenever y is such that S_1(y),\ldots,S_a(y) are zero and T_1(y),\ldots,T_b(y) are non-zero. But an inspection of the algorithm shows that the only reason we needed T_1(y),\ldots,T_b(y) to be non-zero was in order to divide by these numbers; if we clear denominators throughout, we thus see that we can remove these constraints and deduce that (5) holds whenever S_1(y),\ldots,S_a(y) are zero. Further inspection of the algorithm then shows that even if S_1(y),\ldots,S_a(y) are non-zero, this only introduces additional terms to (5) which are combinations (over F[y,t]) of S_1, \ldots, S_a. Thus, for any feasible path, we obtain an identity in F[y,t] of the form

P_1 U_1 + \ldots + P_m U_m = (T_1 \ldots T_b R)^r + S_1 V_1 + \ldots + S_a V_a

for some polynomials U_1,\ldots,U_m,V_1,\ldots,V_a \in F[y,t]. In other words, we see that

(T_1 \ldots T_b R)^r = 0 \hbox{ mod } I, S_1, \ldots, S_a (5)

for any feasible path.

Now what we need to do is fold up the branching tree and simplify the relations (5) until we obtain (2). More precisely, we claim that (5) holds (for some r) not only for complete feasible paths (in which we follow the branching tree all the way to the end), but for partial feasible paths, in which we branch some of the way and then stop in a place where at least one y \in F^{d-1} can solve all the constraints branched on so far. In particular, the empty feasible path will then give (2).

To prove this claim, we induct backwards on the length of the partial path. So suppose we have some partial feasible path, which required S_1(y),\ldots,S_a(y) to be zero and T_1(y),\ldots,T_b(y) to be non-zero in order to get here. If this path is complete, then we are already done, so suppose there is a further branching, say on a polynomial W(y). At least one of the cases W(y)=0 and W(y) \neq 0 must be feasible; and so we now divide into three cases.

Case 1: W(y)=0 is feasible and W(y) \neq 0 is infeasible. If we follow the W(y)=0 path and use the inductive hypothesis, we obtain a constraint

(T_1 \ldots T_b R)^r = 0 \hbox{ mod } I, S_1, \ldots, S_a, W (6)

for some r. On the other hand, since W(y) \neq 0 is infeasible, we see that the problem

S_1(y) = \ldots = S_a(y) = 0; T_1 \ldots T_b W(y) \neq 0

has no solution. Since the nullstellensatz is assumed to hold for dimension d-1, we conclude that

(T_1 \ldots T_b W)^{r'} = 0 \hbox{ mod } S_1,\ldots,S_a.

for some r’. If we then raise (6) to the power r’ by (T_1 \ldots T_b R)^{r'} to eliminate the role of W, we conclude (5) (for rr’+r’) as required.

Case 2: W(y)=0 is infeasible and W(y) \neq 0 is feasible. If we follow the W(y) \neq 0 path, we obtain a constraint

(T_1 \ldots T_b W R)^{r''} = 0 \hbox{ mod } I, S_1, \ldots, S_a (7)

for some r”, while the infeasibility of the W(y)=0 path means that there is no solution to

S_1(y) = \ldots = S_a(y) = W(y) = 0; T_1 \ldots T_b(y) \neq 0

and so by the nullstellensatz in dimension d-1 we have

(T_1 \ldots T_b)^{r'''} = W Z \hbox{ mod } S_1,\ldots,S_a

for some polynomial Z and some r”’. If we then multiply (7) by Z^{r''} to eliminate W, we obtain (5) as desired (for r”+r”’).

Case 3: W(y)=0 and W(y) \neq 0 are both feasible.

In this case we obtain the constraints (6) and (7). We rewrite (6) in the form

(T_1 \ldots T_b R)^{r} = W Z \hbox{ mod } S_1,\ldots,S_a

for some Z, and then multiply (7) by Z^r to eliminate W and obtain (5) as desired (for r + r”).

This inductively establishes (5) for all partial branching paths, leading eventually to (2) as desired.