A connection between the Nullstellensatz and definitions of injective maps

David Hilbert was one, if not the, greatest mathematicians whose career spanned the ${{19}^{th}}$ and ${{20}^{th}}$ 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; ${\dots }$ 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 ${\Delta}$.

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, ${\dots}$ She called the project Gamma. So much for my understanding of the Greek alphabet. Oh well.

Hilbert’s Nullstellensatz

In German, according to Wikipedia, “Nullstellensatz” means the “theorem of zeros,” or more literally, “zero-locus-theorem.”

Theorem: Suppose that ${p_{1},\dots,p_{m}}$ are polynomials in ${\mathbb{C}[x_{1},\dots,x_{n}]}$. Then, they have no common zero if and only if there are polynomials ${a_{1},\dots,a_{m}}$ also in ${\mathbb{C}[x_{1},\dots,x_{n}]}$ so

$\displaystyle a_{1}p_{1} + \cdots + a_{m}p_{m} = 1. \ \ \ \ \ (1)$

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

$\displaystyle p_{1} = 0, \dots, p_{m} = 0$

have a common zero, then

$\displaystyle a_{1}p_{1} + \cdots + a_{m}p_{m} = 0 = 1,$

a contradiction. The hard direction is: if the equations

$\displaystyle p_{1} = 0, \dots, p_{m} = 0$

have no common zero, why should the polynomials ${a_{1},\dots,a_{m}}$ exist? This is the core of the theorem, and works because ${\mathbb{C}}$ is an algebraically closed field.

Further, there are quantitative versions of the Nullstellensatz, where the degrees of the polynomials ${a_{1},\dots,a_{m}}$ are bounded by an explicit function of ${m}$, ${n}$, and the maximum degrees of the ${p_{i}}$‘s. These bounds are used in a moment.

An Application

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 ${f:\mathbb{C}^{n} \rightarrow \mathbb{C}^{n}}$. An important property the map ${f}$ may have is: it is an injective map. The definition of this property is simple:

$\displaystyle \forall x \forall y \ f(x) = f(y) \rightarrow x=y.$

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 ${f}$ is injective if and only if

$\displaystyle \exists \bold{a} \ \Delta_{f}{\bold{a}}$

where ${\Delta_{f}(\bold{a})}$ is a conjunction of polynomial equations that depend only on the variables ${\bold{a}}$.

I will explain the details of ${\Delta_{f}(\bold{a})}$, 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 ${\Delta}$ 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 ${\Delta_{1}^{\text{poly}}}$.

Proving—in 1975—that primality was unconditionally in ${\Delta_{1}^{\text{poly}}}$, by Vaughan Pratt, was a beautiful result. Proving—in the future?—that graph isomorphism is in ${\Delta_{1}^{\text{poly}}}$ would be another beautiful result.

How to Express Injective as an Existential Formula

I owe you the description of ${\Delta_{f}(\bold{a})}$. To avoid excessive notation let ${f}$ be the map

$\displaystyle f(x,y) = (g(x,y),h(x,y))$

where ${g}$ and ${h}$ are polynomials. Then, consider the following equations:

$\displaystyle g(x,y)-g(u,v) = 0$

$\displaystyle h(x,y)-h(u,v) = 0$

$\displaystyle z(x-u) -1 = 0$

They have a solution if and only if there are values so ${f(x,y) = f(u,v)}$ and ${x \neq u}$. There is a similar set of equations for the case where ${y \neq v}$.

Let’s restrict our attention to the first case: ${x \neq u}$. Then, by the Nullstellensatz the equations have no solution if and only if there are polynomials ${q(x,y,u,v,z)}$, ${r(x,y,u,v,z)}$, and ${s(x,y,u,v,z)}$ so that

$\displaystyle q\cdot (g(x,y)-g(u,v)) + r\cdot (h(x,y)-h(u,v)) + s\cdot (z(x-u) -1) = 1.$

The effective version of the Nullstellensatz allows us to write out this equation in terms of the coefficients of the polynomials ${q,r,s}$. 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, ${\Delta_{f}(\bold{a})}$.

Open Problems

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?

1. February 18, 2010 11:53 am

Is there a simpler, or at least just alternative way to characterize 1-1 complex polynomial maps existentially using formal differentiation?

2. February 18, 2010 11:57 am

Oh, also before I forget, delta testing would probably have been an unfortunate name, since there’s already a technique known as delta debugging. Besides, no-one would have published it. “It’s just another delta!”

February 18, 2010 12:16 pm

In the Blum-Shub-Smale model of computation over an arbitrary ring R, I believe the constructive version of the Nullstellensatz over R (in place of the complex numbers) is $NP_{R}$-complete, so it takes the place of SAT, as it were. This is useful as there isn’t a particularly nice formulation of SAT over an arbitrary ring (the usual formulation is over $F_{2}$).

Also, since $\Delta_{2}^{p}$ is $P^{NP}$ and not $\Sigma_{2}^{p} \cap \Pi_{2}^{p}$, shouldn’t $\Delta_{1}^{p}$ be defined as something other than $NP \cap coNP$ (maybe just $P$?)? (The description of PH in the Complexity Zoo agrees with me, but my mind is open.) In other areas such as logic and computability, the analogs of $P^{NP}$ and $\Sigma_{2}^{p} \cap \Pi_{2}^{p}$ are equal, but this is not known (nor believed to be true, according to the common wisdom) in the complexity world.

(PS: Can’t wait to see where you’re going with all this…Ax-Grothendieck, Nullstellensatz, … complexity?)

February 18, 2010 1:08 pm

Doesn’t the Nullstellensatz immediately give you a correspondence between universal and existential? Namely,
\forall x: p_1(x) \neq 0 or … or p_m(x) \neq 0
\exist a_1,…,a_m: a_1 p_1 + … + a_m p_m = 1

February 18, 2010 7:09 pm

Yes it does. If want to use first order theory need bounds on the degrees of the polynomials.

February 18, 2010 9:12 pm

Even though the Nullstellensatz is certainly very fundamental, I think there is a tendency to overly romanticize it (partly because it has remained fashionable to refer to it by its German name). In fact, it is a rather elementary fact of algebra (having little to with complex numbers or the property of being algebraic closed) — namely, it is a multivariate generalization of one of the first theorems one learns in abstract algebra, that “a ring extension k[x] over a field k, is a field if and only if it is algebraic” (k is any field not necessarily algebraically closed).

From the point of view of computational complexity theory (in the generalized Blum-Shub-Smale sense) with an appropriate degree bound it reduces questions about existence of solutions of polynomial equations over an algebraically closed field to linear algebra. Thus, it proves that one can decide satisfiability of (polynomial equations) over complex numbers in single exponential time (just as in complexity theory over finite fields).

6. February 22, 2010 2:54 pm

The angle I like, as someone with an early interest in formal logic, is that the Nullstellensatz functions as a kind of “completeness theorem” for polynomial arithmetic. Indeed in experimental work such as part of this paper, we code up lower bound conditions into polynomial equations, and then the Gro”bner basis algorithm grinds out the answer.

The interest for those who investigated Gro”bner proof systems is that they are “automatizable” to varying degrees, meaning that if a proof exists you get a relatively efficient algorithm for finding one. How efficient depends on the system and the application.

May as well mention here Pascal Koiran’s paper (and erratum) showing that under a generalized/extended Riemann hypothesis, the satisfiability problem over C is in the second level of the polynomial hierarchy, in fact in AM. And this lovely illustrated paper by Lenore Blum on the Blum-Shub-Smale theory—with application to numerical precision issues in Newton’s Method and linear programming. The paper includes a brief treatment of effectivity bounds on the Nullstellensatz and its issues over R, Q, and general rings.

March 16, 2010 5:55 pm

New guy here, I cravinged to make known to you of the Malware crap that is affluent beside the net. This power be a bit off matter but if things go well it whim relief folks get that crapy spyware off their PC.
Browser hijacking can make a balls-up of your well day and commit your turning point filled with malevolent thoughts toward the perpetrators. But there are other, faster methods to handle with it nearby tracking down and slaughtering notable ( uniform if they truthfully DO desperately quality it ) there are profuse advantage programs you can use to fix hijacks, some excel than others. Here we may question nigh the superiority ones.

For what it is good, the old saying that an oz Of pruniformtion is importance a hammer into of mend indubitably applies here and the strong of getting a browser hijack is explicitly cognate to your own dear browsing habits. So it stands to on account of that if you’re looking for something in one of those categories you are far more liable to run across a browser hijack than if you sustain to the untangle and narrow. But disinterested the get the better of of us can on bring on digress from the beaten haul and run into maladvirtuouseds. If you oblige been hijacked you pass on be to halt it from chance again and unfortunately adequacy, staying away from ‘those tolerant of sites’ is the rout way to do this.

And, as trite, you remarkably keep occasion for to run anti-virus and anti-malwarebytes programs in the presence of an copy comes up. But fair here and now you are faced with the difficult of ‘what to do to fix it?’

If your browser has been hijacked and you don’t already oblige state programs established you could be up against the wall. myriad hijackers actively defer you from visiting sites where you can download the pickle, which implies you whim oblige to get on another method, download the programs and establish them to the infected gang from a removable drive. And there’s also one named Hijack This. Each of these are wonderful programs and can surprise some, but very likely not all browser hijacks. ( a indispensable vow of caveat: diverse malevolent programs set as being anti-virus/anti-spyware programs. )

While leader this I couldn’t relief but reflect on of Robert Deniro and how a oddball he power fun would mete out with a browser hijack. It’s a abashment we can’t principled gun the people who do it down while saying, ‘Hijack this!!’ But at least there are some earnest-energy, workable options, such as those listed above.