### Introduction to the Nullstellensatz/Linear Algebra Method

#### by Derrick Stolee

We have spent a lot of time discussing how to *generate* objects, but in order for us to generate them they must exist! This idea of showing existence versus non-existence is central to the computational complexity classes of NP and coNP: the difference is whether you use an existential quantifier or a universal quantifier. So, nonexistence problems can be phrased as “All objects do not have this property” and are not suited well to *proof by certificate*. We can demonstrate existence by finding and presenting the object, but nonexistence is harder to prove.

Today, we discuss Computing Infeasibility Certificates for Combinatorial Problems through Hilbert’s Nullstellensatz by Jesús A. De Loera, Jon Lee, Peter N. Malkin, and Susan Margulies, where they develop what I will call the *Nullstellensatz/Linear Algebra Method*, or *NulLA* for short. Their method starts with a set of polynomials whose common roots correspond to the goal object and they build a *Nullstellensatz certificate* that demonstrates that a set of polynomials have no common root. The certificate is built by solving a set of linear equations. This method is greatly improved by using symmetry to reduce the size of the linear system. The authors’ main idea is to use these certificates to prove certain graphs are not 3-colorable, but I believe this can be used to prove nonexistence of combinatorial objects.

### Polynomials and Ideals

We will consider a set of polynomials over variables with coefficients in an algebraically-closed field . Frequently, we will let be the algebraic closure of a finite field , where is a prime power (and even more specific, let ). If you are unfamiliar with finite fields, think about how the complex numbers relate to the real numbers. Through the magic of linear algebra, we will be able to work over the closed field while only dealing with actual numbers from the base field.

A vector is a *root* of the system of polynomials if and only if for all .

**Example.** (*Complex Numbers*) Let be a graph with vertices and edges and let be an integer. Let the vertex set be . We build the following set of polynomials over , the complex numbers with variables .

, for all .

, for all .

Observe that if we consider the variable to take a value representing a color for the vertex , the polynomial equation implies that is a th root of unity. Once we can guarantee that all of the variables are th roots of unity, the equations imply that the edge is not monochromatic. Thus, the graph is -colorable if and only if the set of polynomials has a root. Moreover, there is a bijection from the proper colorings to the roots of this set of polynomials. **End Example.**

Working with real numbers can be messy, and roundoff error is not to be ignored, especially when dealing with complicated polynomial calculations. Instead, we will simplify the problem, use only 3 colors, and work over a finite field.

**Example.** (*3-Coloring with Finite Fields*) Let be a graph with vertices and edges. Let the vertex set be . We build the following set of polynomials over , the algebraic closure of the finite field with two elements, and variables .

, for all .

, for all .

Observe that if we consider the variable to take a value representing a color for the vertex , the polynomial equation implies that is a 3rd root of unity. In the world of , this means that each is a unit over . These elements can be thought of as . Once we can guarantee that all of the variables are among these three elements, the equations imply that the edge is not monochromatic. Thus, the graph is 3-colorable if and only if the set of polynomials has a root. Moreover, there is a bijection from the proper colorings to the roots of this set of polynomials. **End Example.**

Given a set of polynomials, the *ideal* generated by the polynomials, denoted , is the set of all linear combinations of the polynomials over the polynomial ring . That is, a polynomial is in the ideal if and only if there exist polynomials such that .

Given a set of polynomials, the *variety* generated by the polynomials, denoted is the set of all roots of the polynomials. So, is a set of points in .

One of the most fundamental tenets of algebraic geometry is the *ideal/variety exchange*. That is, if we take a set of polynomials , and consider the variety , then the set of polynomials where $h(x) = 0$ for all points forms an ideal. Even more importantly, *this ideal is the same as !* In some sense, this means that ideals and varieties are two different ways to describe the same mathematical object.

What is most important is that the variety is empty if and only if these polynomials have no common root. If a variety is the empty set, then the constant function (which is a polynomial) is equal to zero over all points in the variety (vacuously). This means that . This gives us our Nullstellensatz condition.

**Theorem (The Nullstellensatz).** A set of polynomials in has no common root if and only if there exist polynomials such that .

The set of polynomials in the above theorem is called a *Nullstellensatz certificate*. By demonstrating such a certificate, we have a proof that no common root exists. Here is our “evidence” of non-existence! All we need now is a way to find such a certificate, and this is where the linear algebra comes in.

### The Linear Algebra

Our goal is to compute a Nullstellensatz certificate for a given set of polynomials. We could use some complicated <a href="http://en.wikipedia.org/wiki/Gr%C3%B6bner_basis"Gróbner Basis algorithm (which requires sophisticated machinery to discuss) but instead we will use good-old linear algebra. However, the very first thing we must do is to restrict the problem.

Let be an integer. We will use to bound the maximum degree of our Nullstellensatz certificates. The Nullstellensatz provides no bound on the degree of the certificates, and in fact there exist low-degree polynomial systems that require very large degree Nullstellensatz certificates. However, we will see that the size of our linear system will grow exponentially with the parameter , so we will start with it being small and then let it grow.

If we restrict the polynomials to have degree at most , then each polynomial is actually a finite-dimensional vector over . For and with $\sum_{j=1}^n a_j \leq d$, let $c_{i,a}$ be the coefficient of in . These will be our variables in the linear system.

Now it is time to plug-and-chug: we want to find values for our variables such that . The way to form linear equations is to create one for every possible monomial (i.e. every combination where is one of our basis monomials and appears in some ). Then, we need to make sure that the coefficients of the non-constant monomials equal 0 and the constant coefficient equals 1.

**Example.** Suppose we have the three polynomials , , and . Let , so we have six variables. The possible monomials are , so we will have 10 equations. The equation for is

,

and the equation for is

.

Continuing in this fashion will construct the full set of equations. **End Example.**

One *very important* property of these equations is that we can use our base field! Since we are using linear algebra, we can use the following fact:

**Fact.** If a system of linear equations over a field has a solution using the algebraic closure if and only if there is a solution using the base field .

This means that if we are talking about complex numbers, our equations are entirely in the real numbers and we can use real arithmetic to solve the equations. Also, if we are talking about 3-coloring using the closure of , we can actually do all of our arithmetic over , which can be done very efficiently.

This use of linear algebra to simplify the situation cannot be understated. Observe that **even though the roots can take values in the algebraic closure, our linear algebra can take place in the base field!**

So, here is the algorithm: fix , build the linear equations, and solve. If you find a solution, then output the Nullstellensatz certificate. If you do not find a solution, increase and repeat.

### Symmetric Monomials

One of the main tenets of computational combinatorics is that we should always be aware of symmetry, especially when dealing with graphs. Since the current application of the NulLA method is to color graphs, we should consider what happens when the input graph has a non-trivial automorphism group, .

Since acts on , there is a natural action of on the variables . That is, for , we say if and only if . This action on the variables extends to an action on the ring . Finally, since the action of on preserves edges and non-edges, the action of on set-wise stabilizes the ideal .

Given a Nullstellensatz certificate , we can form a symmetric certificate by defining . Since , we end up with the equation

Thus, if is relatively prime to the characteristic of , then we have a *symmetric certificate* if and only if we have a standard certificate. In this case, we can greatly reduce the size of our system of linear equations by using orbits of monomials instead of the full list of monomials. The details get a bit complicated, so I’ll skip them and you can look them up in the paper.

### Other Optimizations

To find all sorts of interesting and detailed optimizations that can improve the search for a Nullstellensatz certificate, go read the original paper. However, one stood out in my mind as a particularly useful concept that can decrease the required degree of a Nullstellensatz certificate.

If you can tell *a priori* that a polynomial will be in the ideal , then you can use as a generating polynomial. This increases the size of your linear system, but also allows for more variables and possibly more solutions where previously none existed (for that degree value).

**Example.** Suppose we are trying to show non-3-colorability of a graph and there is a triangle . Then, all three vertices must receive distinct colors. This fact can be discovered by combining the three edge polynomials, but we can encode that information more compactly using a new polynomial. The equation

requires the values of , , and to be distinct values when already restricted within the units of . **End Example.**

### Open Problems

These authors used this technique to prove non-3-colorability of specific graphs. It would be interesting if the technique could be used to show the nonexistence of certain combinatorial objects. Here are some open problems.

**P1:** Build a sequence of non-3-colorable graphs where a Nullstellensatz certificate for has degree at least . (If , then such a sequence exists.)

**P2:** Use Nullstellensatz certificates to prove nonexistence of some combinatorial object, such as a projective plane of order 10 (or 12) or a strongly regular graph with small parameters. Perhaps lower bounds on cages or Ramsey numbers could be achieved in this way, too?

### A Brief Comparison to the Combinatorial Nullstellensatz

Since this technique has the word “Nullstellensatz” in it and discusses combinatorial objects, there is bound to be a confusion with the Combinatorial Nullstellensatz as popularized by Noga Alon. The methods are very different, though.

**Number of Polynomials.**The Combinatorial Nullstellensatz uses exactly one polynomial , while the NulLA method uses a set of polynomials .**Largest-Degree Versus Ideals.**Since the Combinatorial Nullstellensatz uses only one polynomial, it only needs to consider a largest-degree term. However, the NulLA method needs to consider more complicated ideal calculations.**Non-Zeroes Versus No Zeroes.**The Combinatorial Nullstellensatz uses the exponents of a largest-degree monomial to guarantee there exists a solution to , while the NulLA method proves that for some . Another way to phrase this is that for the Combinatorial Nullstellensatz, a “solution” is a point where , while for the NulLA method, a “solution” is a point where .**Adaptability to Lists.**One frequent place where the Combinatorial Nullstellensatz is used is for graph coloring problems, and that is the first application for the NulLA method. However, every theorem proved using the Combinatorial Nullstellensatz naturally extends to list-coloring, while the dependence on a field limits the domains of the NulLA method. If we wanted to use some specific lists of colors at each vertex, we would need to increase the size of the field to be the union of all lists and add more polynomials to the system that limit the values of the variables to be within the lists. This would increase the computation. (However, there may exist lower-degree Nullstellensatz certificates when using these lists.)

The most important thing to remember is that there are multiple Nullstellensatze out there, and you should keep them straight!

### References

Jesús A. De Loera, Jon Lee, Peter N. Malkin, Susan Margulies, Computing Infeasibility Certificates for Combinatorial Problems through Hilbert’s Nullstellensatz, *Journal of Symbolic Computation* **46**(11), pp. 1260-1283 (2011).

Jorg Arndt, FXT: A Library of Algorithms.

Great post on Nullstellensatz. In literature there is a more “dynamic” variant of Nullstellensatz proof method called Polynomial Calculus. It may be must faster in some cases (at least theoretically), and it is a strictly more powerful than Resolution.

http://dl.acm.org/citation.cfm?id=237860

Also, this proof methods is on of the most studied in proof complexity (after resolution and on the same level with cutting planes). There is a lot of literature on it.

It is open whether there is a degree lower bound for non-colorability proofs. If there is one strong enough, then such lower bound would imply also a running time lower bound.