Alpha, Beta, Delta, and the Nullstellensatz
A connection between the Nullstellensatz and definitions of injective maps
David Hilbert was one, if not the, greatest mathematicians whose career spanned the and centuries. His famous 23 open problems shaped mathematics throughout the last century, and their effect is still felt today. The address where he presented the problems started:
Who of us would not be glad to lift the veil behind which the future lies hidden; to cast a glance at the next advances of our science and at the secrets of its development during future centuries? What particular goals will there be toward which the leading mathematical spirits of coming generations will strive? What new methods and new facts in the wide and rich field of mathematical thought will the new centuries disclose?
Today, most of our presentations are informal: we use powerpoint; we do not read from a written script, we get questions during the talk—it hard to imagine a talk like Hilbert’s ever again. What a beautiful opening: Who of us would not be glad to lift the veil behind which the future lies hidden; An impossible act to follow.
Today I want to talk about a famous theorem of Hilbert’s, called the Nullstellensatz. This theorem has played an important role in many aspects of complexity theory. However, I have a somewhat different view of why the theorem is important: it is all about the Greek letter .
I cannot resist telling you a story about the Greek alphabet. When I first got to Georgia Tech, I was working with Mary Jean Harrold on a program testing project. The project had a quite neat idea—all hers—but I was helping a bit. One thing I really did not like was the name of the project: it was not very catchy nor was it descriptive.
One day it occurred to me what to call the project: call it the delta project. My reasoning was there already was alpha testing and beta testing, so the natural next advance had to be delta testing. I sent an email to Mary Jean, with my suggested name and why it was the right name for the project. She sent back a short message: Dick, great idea on the name, but in the Greek alphabet it is: alpha, beta, gamma, She called the project Gamma. So much for my understanding of the Greek alphabet. Oh well.
In German, according to Wikipedia, “Nullstellensatz” means the “theorem of zeros,” or more literally, “zero-locus-theorem.”
As with many “if and only if” theorems one direction is easy and one is hard. The easy direction is: if the equation (1) has a solution, then there can be no common zero. For if
have a common zero, then
a contradiction. The hard direction is: if the equations
have no common zero, why should the polynomials exist? This is the core of the theorem, and works because is an algebraically closed field.
Further, there are quantitative versions of the Nullstellensatz, where the degrees of the polynomials are bounded by an explicit function of , , and the maximum degrees of the ‘s. These bounds are used in a moment.
Why is this theorem important? Usually a theorem is important if it has many applications. There are other reasons, but this is the main one. There are exceptions: Fermat’s Last Theorem is probably more important for the proof technology used by Andrew Wiles, than for applications of the theorem. Indeed, I believe that there are few applications of Fermat’s Last Theorem—of course it is still one of the great results of number theory.
Why is this theorem, the Nullstellensatz, important? It is because it has many applications. The application I will present in a moment is a complexity theory oriented one.
Consider a polynomial map . An important property the map may have is: it is an injective map. The definition of this property is simple:
Note, this is the usual definition of injective: a map is injective if any two distinct points map to distinct values.
In general there is not much more to say, but in the special case when the map is a polynomial mapping and the field is the complex numbers, one can say much more. Because of the Nullstellensatz, there is completely different different characterization of being injective. A mapping is injective if and only if
where is a conjunction of polynomial equations that depend only on the variables .
I will explain the details of , but the key is it uses only existential quantifiers. Thus, the notion of “injective” can be expressed both as a universal formula and as an existential formula. The former is the standard definition; the latter is only possible because we have access to the Nullstellensatz.
The ability to express a universal property by an existential one is very special, and helps me understand why the Nullstellensatz is so powerful. I hope it also helps you.
The Greek letter is used to denote the property of being representable as universal and existential formulas. In complexity theory, for example, problems in both NP and co-NP are special, and this complexity class is denoted by .
Proving—in 1975—that primality was unconditionally in , by Vaughan Pratt, was a beautiful result. Proving—in the future?—that graph isomorphism is in would be another beautiful result.
How to Express Injective as an Existential Formula
I owe you the description of . To avoid excessive notation let be the map
where and are polynomials. Then, consider the following equations:
They have a solution if and only if there are values so and . There is a similar set of equations for the case where .
Let’s restrict our attention to the first case: . Then, by the Nullstellensatz the equations have no solution if and only if there are polynomials , , and so that
The effective version of the Nullstellensatz allows us to write out this equation in terms of the coefficients of the polynomials . This finally yields a set of equations that have a solution if and only if the original 1-1 condition was true. This defines the formula, .
Did this example application help with the understanding of why the Nullstellensatz is important? What are other applications of the Nullstellensatz to problems relevant to complexity theory?