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 f_1, f_2,\dots, f_m over variables x_1,\dots,x_n with coefficients in an algebraically-closed field {\mathbb F}. Frequently, we will let {\mathbb F} be the algebraic closure of a finite field {\mathbb Z}_q, where q is a prime power (and even more specific, let q = 3). 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 x \in {\mathbb F}^n is a root of the system of polynomials f_1,\dots,f_m if and only if f_i(x) = 0 for all i \in \{1,\dots,n\}.

Example. (Complex Numbers) Let G be a graph with n vertices and m edges and let k \geq 2 be an integer. Let the vertex set be v_1,\dots,v_n. We build the following set of n + m polynomials over \mathbb{C}, the complex numbers with variables x_1,\dots,x_n.
f_i(x_1,\dots,x_n) = x_i^k + 1, for all v_i \in V(G).
g_{i,j}(x_1,\dots,x_n) = \sum_{\ell=0}^{k-1} x_i^{k-1-\ell}x_j^\ell, for all v_iv_j \in E(G).

Observe that if we consider the variable x_i to take a value representing a color for the vertex v_i, the polynomial equation f_i(x) = 0 implies that x_i is a kth root of unity. Once we can guarantee that all of the variables are kth roots of unity, the equations g_{i,j}(x) = 0 imply that the edge v_iv_j is not monochromatic. Thus, the graph G is k-colorable if and only if the set of polynomials \{ f_1,\dots,f_n\} \cup \{ g_{i,j} : v_iv_j \in E(G)\} has a root. Moreover, there is a bijection from the proper colorings c: V(G) \to [k] 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 G be a graph with n vertices and m edges. Let the vertex set be v_1,\dots,v_n. We build the following set of n + m polynomials over \overline{\mathbb{F}_2}, the algebraic closure of the finite field with two elements, and variables x_1,\dots,x_n.
f_i(x_1,\dots,x_n) = x_i^3 + 1, for all v_i \in V(G).
g_{i,j}(x_1,\dots,x_n) = x_i^2 + x_ix_j + x_j^2, for all v_iv_j \in E(G).

Observe that if we consider the variable x_i to take a value representing a color for the vertex v_i, the polynomial equation f_i(x) = 0 implies that x_i is a 3rd root of unity. In the world of {\mathbb F}_2, this means that each x_i is a unit over {\mathbb F}_4. These elements can be thought of as 1, \alpha, -\alpha. Once we can guarantee that all of the variables are among these three elements, the equations g_{i,j}(x) = 0 imply that the edge v_iv_j is not monochromatic. Thus, the graph G is 3-colorable if and only if the set of polynomials \{ f_1,\dots,f_n\} \cup \{ g_{i,j} : v_iv_j \in E(G)\} has a root. Moreover, there is a bijection from the proper colorings c: V(G) \to [3] to the roots of this set of polynomials. End Example.

Given a set f_1,\dots,f_m of polynomials, the ideal generated by the polynomials, denoted \langle f_1,\dots,f_m\rangle, is the set of all linear combinations of the polynomials f_1,\dots,f_m over the polynomial ring {\mathbb F}[x_1,\dots,x_n]. That is, a polynomial h(x) is in the ideal \langle f_1,\dots,f_m\rangle if and only if there exist polynomials \beta_1,\dots,\beta_m such that h = \sum_{i=1}^m \beta_if_i.

Given a set f_1,\dots,f_m of polynomials, the variety generated by the polynomials, denoted V(f_1,\dots,f_m) is the set of all roots of the polynomials. So, V(f_1,\dots,f_m) is a set of points in {\mathbb F}^n.

One of the most fundamental tenets of algebraic geometry is the ideal/variety exchange. That is, if we take a set of polynomials f_1,\dots,f_m, and consider the variety V(f_1,\dots,f_m), then the set of polynomials h where $h(x) = 0$ for all points x \in V(f_1,\dots,f_m) forms an ideal. Even more importantly, this ideal is the same as \langle f_1,\dots,f_m\rangle! 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 V(f_1,\dots,f_m) is empty if and only if these polynomials have no common root. If a variety is the empty set, then the constant function 1 (which is a polynomial) is equal to zero over all points in the variety (vacuously). This means that 1 \in \langle f_1,\dots,f_m\rangle. This gives us our Nullstellensatz condition.

Theorem (The Nullstellensatz). A set f_1,\dots,f_m of polynomials in {\mathbb F}[x_1,\dots,x_n] has no common root if and only if there exist polynomials \beta_1,\dots,\beta_m \in {\mathbb F}[x_1,\dots,x_n] such that \sum_{i=1}^m \beta_if_i = 1.

The set of polynomials \beta_1,\dots,\beta_m 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 d \geq 1 be an integer. We will use d 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 d, so we will start with it being small and then let it grow.

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

Now it is time to plug-and-chug: we want to find values for our c_{i,a} variables such that \beta_1f_1+\cdots+\beta_mf_m = 1. The way to form linear equations is to create one for every possible monomial (i.e. every combination x^ax^b where x^a is one of our basis monomials and x^b appears in some f_i). 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 f_1(x) = x_1^3+1, f_2(x) = x_2^3+1, and f_3(x) = x_1^2+x_1x_2+x_2^2. Let d = 1, so we have six variables. The possible monomials are 1, x_1, x_2, x_1^2, x_2^2, x_1x_2, x_1^2x_2, x_1x_2^2, x_1^3, x_2^3, so we will have 10 equations. The equation for x_1x_2^2 is
1c_{2,(1,0)}+1c_{3,(0,1)} = 0,
and the equation for 1 = x_1^0x_2^0 is
1c_{1,(0,0)} + 1c_{2,(0,0)} = 1.
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 {\mathbb F} has a solution using the algebraic closure \overline{\mathbb F} if and only if there is a solution using the base field \mathbb{F}.

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 \mathbb{Z}_2, we can actually do all of our arithmetic over \mathbb{Z}_2, 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 d \geq 1, build the linear equations, and solve. If you find a solution, then output the Nullstellensatz certificate. If you do not find a solution, increase d 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, \Gamma = \mathsf{Aut}(G).

Since \Gamma acts on V(G), there is a natural action of \Gamma on the variables x_1,\dots,x_n. That is, for \gamma\in \Gamma, we say \gamma x_i = x_j if and only if \gamma v_i = v_j. This action on the variables extends to an action on the ring \mathbb{F}[x_1,\dots,x_n]. Finally, since the action of \Gamma on G preserves edges and non-edges, the action of \Gamma on \mathbb{F}[x_1,\dots,x_n] set-wise stabilizes the ideal \langle f_1,\dots,f_n, g_{i,j} : v_iv_j \in E(G) \rangle.

Given a Nullstellensatz certificate \beta_1,\dots,\beta_m, we can form a symmetric certificate \overline{\beta}_1,\dots,\overline{\beta}_m by defining \overline{\beta}_i = \sum_{\gamma \in \Gamma} \gamma \beta_i. Since \gamma 1 = 1, we end up with the equation
\sum_{i=1}^m \overline{\beta}_i f_i = |\Gamma|
Thus, if |\Gamma| is relatively prime to the characteristic of \mathbb{F}, 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 g will be in the ideal \langle f_1,\dots,f_m\rangle, then you can use g 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 G and there is a triangle v_iv_jv_k. 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
x_i^2 + x_j^2 + x_k^2 = 0
requires the values of x_i, x_j, and x_k to be distinct values when already restricted within the units of \mathbb{F}_4. 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 \{ G_k\}_{k=1}^\infty of non-3-colorable graphs where a Nullstellensatz certificate for G_k has degree at least k. (If {\mathsf P} \neq {\mathsf{NP}}, 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.

  1. Number of Polynomials. The Combinatorial Nullstellensatz uses exactly one polynomial f(x), while the NulLA method uses a set of polynomials f_1(x),\dots, f_m(x).
  2. 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.
  3. Non-Zeroes Versus No Zeroes. The Combinatorial Nullstellensatz uses the exponents of a largest-degree monomial to guarantee there exists a solution to f(x) \neq 0, while the NulLA method proves that f_i(x) \neq 0 for some i. Another way to phrase this is that for the Combinatorial Nullstellensatz, a “solution” is a point where f(x) \neq 0, while for the NulLA method, a “solution” is a point where f_1(x) = \cdots = f_m(x) = 0.
  4. 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.

Advertisements