Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes

Sam Buss^{1,2}

Department of Mathematics Univ. of Calif., San Diego La Jolla, CA 92093-0112 sbuss@ucsd.edu

Dima Grigoriev Computer Science and Engineering Pennsylvania State University University Park, PA 16802-6106 dima@cse.psu.edu

Russell Impagliazzo^{1,3} Computer Science and Engineering

Univ. of Calif., San Diego La Jolla, CA 92093-0114

russell@cs.ucsd.edu Toniann Pitassi^{1,4} Computer Science University of Arizona Tucson, AZ 85721-0077 toni@cs.arizona.edu

Abstract

This paper gives nearly optimal lower bounds on the minimum degree of polynomial calculus refutations of Tseitin’s graph tautologies and the mod p counting principles, p ≥ 2. The lower bounds apply to the polynomial calculus over fields or rings. These are the first linear lower bounds for polynomial calculus; moreover, they distinguish linearly between proofs over fields of characteristic q and r, q ≠ r, and more generally distinguish linearly the rings Z_{q} and Z_{r} where q and r do not have the identical prime factors.

1Supported in part by international grant INT-9600919/ME-103 from the NSF (USA)

and the MŠMT (Czech republic)

2Supported in part by NSF grant DMS-9803515 3Supported in part by NSF grant CCR-9734911, Sloan Research Fellowship BR-3311, and US-Israel BSF grant 97-00188.

4Supported in part by NSF grant CCR-9457783 and US-Israel BSF grant 95-00238.

1 Introduction

The problem of recognizing when a proposition formula is a tautology is dual to the satisfiability problem and is therefore central to computer science. A principal method of establishing that a formula is a tautology is to find a proof of it in a formal system such as resolution or (extended) Frege systems. In fact, many algorithms for establishing propositional validity are essentially a search for a proof in a particular formal system. In recent years, several algebraic proof systems, including the Nullstellensatz system and the polynomial calculus (also called the ‘Gröbner’ system) have been proposed: these systems are motivated in part by the desire to identify powerful proof systems which support efficient search algorithms and in part by the desire to extend lower bounds on proposition proof complexity to stronger proof systems.

The Nullstellensatz proof system is a propositional proof system based on Hilbert’s Nullstellensatz and was introduced in [1]. The polynomial calculus (PC) is a stronger propositional proof system introduced first by [4]. (See [7] and [3] for subsequent, more general treatments of algebraic proof systems.) In the polynomial calculus, one begins with an initial set of polynomials and the goal is to prove that they cannot be simultaneously equal to zero over a field F. A polynomial calculus (PC) derivation of P_{l} from a set of polynomials Q is a sequence of polynomials P_{1}, …, P_{l} such that each polynomial is either an initial polynomial from Q, or follows from one of the following two rules: (i) If P_{i} and P_{j} are previous polynomials, then cP_{i} + dP_{j} can be derived, where c, d ∈ F; (ii) if P_{i} is a previous polynomial, then xP_{i} can be derived. The degree of a PC derivation is the maximum degree of the P_{i}’s. We identify polynomials P_{i} with the equations P_{i} = 0 and a PC refutation of Q (a proof that the equations Q = 0 are not solvable over F) is simply a PC derivation of 1 (i.e., of 1 = 0).

The definition of the polynomial calculus depends implicitly on the choice of a field F such that all polynomials are over the field F. A number of authors also consider the polynomial calculus over rings ([3, 2]). The only difference in the definition of the PC system is that a PC refutation over a ring is a derivation of r (i.e., of r = 0) for some non-zero r in the ring. Our main results apply to both fields and rings.

The mod p counting principle can be formulated as a set MOD_{p}^{n} of constantdegree polynomials expressing the negation of the counting principle, and the present paper gives linear lower bounds on the degree of polynomial calculus refutations of MOD_{p}^{n} over fields of characteristic q ≠ p. A couple lower bounds on the degree of Nullstellensatz proofs of the mod p counting principles have been given in prior work: [1] gave non-constant lower bounds and [3] gave lower bounds of the form n^{ϵ}. For the polynomial calculus, the best lower bound on the degree of PC refutations of MOD_{p}^{n} was Krajíček’s Ω(log log n) lower bound based on a general lower bound for symmetrically specified polynomials [6].

A couple polynomial calculus lower bounds have been obtained for other families of tautologies. Razborov [8] established \sqrt{n} lower bounds on the degree of polynomial calculus proofs of the pigeon-hole principle. Krajíček [6] proves log log n lower bounds for a wide variety of symmetric tautologies.

Recently, Grigoriev [5] succeeded in giving very simple linear lower bounds on the degree of Nullstellensatz refutations of the Tseitin mod 2 graph tautologies. The present work is motivated by this paper, and in particular by the idea of working in the Fourier basis which greatly simplifies the argument.

The present paper establishes linear lower bounds to the polynomial calculus by proving that over a field of characteristic q ∤ p, any PC refutation of the MOD_{p}^{n} polynomials requires degree δ · n, for a constant δ which depends on p and q. In section 8 we generalize this linear lower bound to the polynomial calculus over rings Z_{q} provided p and q are relatively prime.

As it is well-known to be easy to give constant degree polynomial calculus (and even Nullstellensatz) refutations of the MOD_{p}^{n} polynomials over F_{p}, our results imply that the MOD_{p}^{n} polynomials have a linear gap between proof complexity for the polynomial calculus over F_{p} and over F_{q}.

It follows from a result of Krajíček [?] that our linear lower bounds on the degree of PC refutations imply exponential lower bounds of AC^{0}[q]-Frege proofs of the mod p principles when Mod-q gates are present only at the top (root) of formulas.

2 Tseitin tautologies: polynomial version

Tseitin’s (mod 2) graph tautologies are based on the following idea. Let G_{n} be a connected undirected graph on n vertices, where each node in the graph has an associated charge of either 0 or 1, and where the total sum of the charges is odd. Then it is impossible to choose a subset of the edges E′ from E so that for every vertex v ∈ V, the number of E′-edges incident to v is equal mod 2 to the charge of v. This impossibility follows from a simple parity argument, since summing the degrees of all vertices in the subgraph counts each edge twice, and so is even, whereas it should also be the sum of all the charges, which is odd.

For an r-regular graph G_{n} with n odd, and charges all 1, we can express this principle as the inconsistency of the following system of polynomials over a finite field F of characteristic different from 2: There will be rn/2 underlying variables, one for each edge of G_{n}. We will denote the variable corresponding to the edge e = {i, j} from i to j by y_{e} = y_{{i,j}}. For each variable y_{e}, we have the equation y_{e}^{2} − 1 = 0; this forces the variables to take on values of either 1 or −1, with y_{e} = −1 corresponding to the presence of e in the subgraph E′. Secondly, corresponding to each vertex i in G_{n}, we will have the equation 1 + y_{{i,j1}}y_{{i,j2}} ⋯ y_{{i,jr}} = 0, where j1, …, jr are the neighbors of i in G_{n}. This corresponds to saying that the degree of i in the subgraph E′ is odd. This set of equations, representing the Tseitin mod 2 graph formula, will be denoted by TS_{n}(2).

For any prime p, we can generalize the above principle to obtain a mod p version as follows. Again, we fix an underlying r-regular, undirected graph G_{n}, and then let G′_{n} be the corresponding directed graph where each undirected edge is replaced by two directed edges. Each vertex in G′_{n} will have an associated label, or charge in [0, p − 1] such that the sum of the vertex charges is congruent to 1 mod p. The mod p principle states that it is impossible to assign values in [0, p−1] to each of the directed edges so that: (i) for any pair of complementary edges ⟨i, j⟩ and ⟨j, i⟩, v(⟨i, j⟩) + v(⟨j, i⟩) ≡ 0 (mod p), and (ii) for every vertex i, the sum of the edge values coming out of vertex i is congruent to the charge of that vertex mod p. Again, this is impossible since if we sum the edges in pairs, we obtain 0 mod p, but summing them by vertices gives the total charge of 1 mod p.

Let F be a finite field with characteristic q ≠ p that contains a primitive p-th root of unity ω. Assume all charges of vertices are 1, and that n ≡ 1 (mod p). We can express the mod p Tseitin principle for G′_{n} as the unsatisfiability of the following system of polynomials over F: We have rn underlying variables y_{e}, one for every directed edge e. For each variable y_{e} we have the equation y_{e}^{p} − 1 = 0; this forces variables to take on values in 1, ω, ω^{2}, …, ω^{p−1}. (The power of ω corresponds to the value assigned to e.) Secondly, for each vertex i in G′_{n}, we will have the equation y_{⟨i,j1⟩}y_{⟨i,j2⟩}, …, y_{⟨i,jr⟩} − ω = 0, where j1, …, jr are the neighbors of i. Third, for each edge e = ⟨i, j⟩ we have the equation y_{⟨i,j⟩}y_{⟨j,i⟩} − 1 = 0. This set of equations, representing the Tseitin mod p formula, will be denoted by TS_{n}(p).

We can also express the Tseitin and generalized Tseitin tautologies as CNF formulas. For the Tseitin tautology, we have a Boolean variable x_{e} for each edge. For each node, we express the constraint that ⊕_{u∈N(v)}x_{{u,v}} = 1 as a CNF. Since the graph has bounded degree, this is a k − CNF formula for some fixed k.

For the generalized Tseitin tautologies, we have a Boolean variable for each directed edge and each residue modulo q, x_{e,i} signifying that the charge of edge e is i. We write that each edge has a unique charge, the charge of an edge is the negative of the charge of its reverse, and that the sum of the charges of edges from any one node is 1 modulo q as k-CNFs, for a constant k that depends on q and the degree of the graph.

3 The mod p principle and low degree reductions

A related principle is the mod p counting principle. Intuitively, it states that it is not possible to partition a set of size n into groups of size p, if n is congruent to 1 mod p. We will express this by polynomial equations as follows. The underlying variables are x_{e}, where e ranges over all p element subsets of [1, n]. The degree 2 equations expressing the negation of the principle are: (1) x_{e}^{2} − x_{e} = 0 for each e; (2) x_{e}x_{f} = 0, for each e, f such that e ∩ f ≠ ∅ and e ≠ f; (3) 1 − ∑_{e,i∈e} x_{e} = 0, for each i ∈ [1, n]. Let the above set of equations be denoted by MOD_{p}^{n}.

We want to show that a low degree PC refutation of the mod p counting principle implies a low degree PC refutation of the Tseitin mod p graph equations. To do this, we define the following general notion of a low degree reduction.

Definition. Let P (\overline{x}), Q(\overline{y}) be two sets of polynomials over a field F. Then P is (d_{1}, d_{2})-reducible to Q if: (1) For every y_{i}, there is a degree d_{1} definition of y_{i} in terms of the x’s. That is, for every i, there exists a degree d_{1} polynomial r_{i} where y_{i} will be viewed as being defined by r_{i}(x_{1}, …, x_{n}); (2) there exists a degree d_{2} PC derivation of the polynomials Q(\overline{r}(x_{1}, …, x_{n})) from the polynomials P (\overline{x}).

Lemma 1 Suppose that P (x) is (d_{1}, d_{2})-reducible to Q(y). Then if there is a degree d_{3} PC refutation of Q(y), then there is a degree max(d_{2}, d_{3}d_{1}) PC refutation of P (x).

First, the CNF and algebraic formulations of the Tseitin and generalized Tseitin principles are inter-reducible.

Lemma 2 The Boolean and algebraic formulations of the Tseitin graph tautologies are inter-reducible via constant degree reductions, over any finite field that contains a primitive q’th root of unity .

Proof For the normal graph tautologies, the reductions are given by : y_{e} = 1 − 2x_{e} and x_{e} = (1 − y_{e})/2 respectively. For the generalized tautologies, let ω be a primitive qth root of unity. Then the reductions are given by: y_{e} =_{i} (x_{e,i}(ω)^{i} and x_{e,i} = 1 − (y_{e} − ω^{i})^{|F |−1} respectively. □

Lemma 3 For all n and p, and for any field F of characteristic q, where q ∤ p, and F includes the primitive p-th root of unity, TS_{n}(p) is (d_{1}, d_{2})-reducible to MOD_{p}^{m} over F, where m = n + nrp, d_{1} = 2pr and d_{2} = 2pr.

Proof of Lemma 3. Let G′_{n} be a directed Tseitin graph on n vertices, where n ≡ 1 (mod p). That is, the underlying G′_{n} is an r-regular graph; each vertex of G′_{n} has a charge of 1, and the edges of G′_{n} are labeled with values from [0, p−1]. Thus, the total number of directed edges of G′_{n} is rn. From G we will define a universe U of size m, and a corresponding p-partition of this universe, where m = n + nrp. In U, there will be one element corresponding to each vertex of G′_{n}, and there will also be p elements corresponding to each directed edge of G′_{n}. We will denote the element of U corresponding to vertex i in G′_{n} by (i), and the vector of p elements of U corresponding to the edge ⟨i, j⟩ in G′_{n} will be denoted by (i, j, ∗) = ⟨(i, j, 1), (i, j, 2), …, (i, j, p)⟩.

Definition. The elements in U associated with node i will be (i), plus all elements (i, k, ∗). (That is, the rp elements corresponding to outgoing edges from i plus the element corresponding to node i.) The elements in U associated with the pair of nodes i, j will be the rp elements corresponding to the directed edge ⟨i, j⟩ plus the rp elements corresponding to the directed edge ⟨j, i⟩.

The partition of U is defined as follows. We will consider node i in G′_{n}, and the r labeled edges, (i, j_{1}), (i, j_{2}), …, (i, j_{r}), leading out of i, where j_{1} < j_{2} < ⋯ < j_{r}. Suppose that the values of these edges are: a_{1}, a_{2},…,a_{r}. Then for each ℓ, 1 ≤ ℓ ≤ r, we take the first a_{ℓ} elements in U from (i, j_{ℓ}, ∗), and group them with the first (p − a_{ℓ}) elements in U from (j_{ℓ}, i, ∗). (This gives us r p-partitions so far.) Note that the number of remaining, ungrouped elements associated with node i is (p − a_{1}) + (p − a_{2}) + ⋯ + (p − a_{r}) + 1, which is congruent to 0 mod p as long as (a_{1} + ⋯ + a_{r}) mod p = 1.

We then group these remaining, ungrouped elements associated with i, p at a time, in accordance with the following ordering. Ungrouped elements from (i, j_{1}, ∗) are first, followed by ungrouped elements from (i, j_{2}, ∗), and so on until we get to the ungrouped elements from (i, j_{r}, ∗), and lastly the element (i).

It should be intuitively clear that if the values y_{i,j} satisfy TS_{n}(p), that is, if they are set so that the mod p sum coming out of each vertex in G′_{n} is congruent to 1 mod p, and y_{i,j}y_{j,i} = 1 and y_{i,j}^{p} = 1, then the corresponding partition of U is a proper p partition. We want to prove this now formally, with small-degree PC refutations. There are two steps to this reduction. First, for each variable x_{e} underlying MOD_{p}^{m}, we want to define a degree at most rp polynomial, call it r_{e}(\overline{y}), in the y_{i,j} variables that corresponds to the above reduction. Secondly, we want to show that there is a small degree PC derivation of MOD_{p}^{m}(\overline{r}_{e}) from TS_{n}(p).

Step 1: Defining r_{e}. We will first describe the defining polynomial r_{e} for x_{e}. Recall that e is a particular p-set from U. In the above reduction, the valid p-partitions are of two types: (i) where the elements of e are a subset of the elements associated with a pair of nodes i, j in G′_{n}; (ii) where the elements of e are a subset of the elements associated with a node i. Thus, if the underlying p elements from e are not one of these two types, then x_{e} is just set to 0.

Now consider case (i); that is, the elements of e are a subset of the elements associated with the pair of nodes i, j. Suppose that e is the set {(i, j, 1), (i, j, 2), …, (i, j, a_{1}), (j, i, 1), …, (j, i, p − a_{1})}. That is, e consists of an initial segment of size a_{1} of the p elements associated with directed edge ⟨i, j⟩ and an initial segment of size p − a_{1} of the p elements associated with ⟨j, i⟩. (If e is not of this form, then again x_{e} is just 0.) Then x_{e} should be 1 if y_{i,j} = ω^{a_{1}}, y_{j,i} = ω^{p−a_{1}} and should be 0 otherwise. This is defined by the following polynomial:

∏_{a≠a_{1}}(ω^{a_{1}} − ω^{a})^{−1}(y_{i,j} − ω^{a}) × ∏_{b≠p−a_{1}}(ω^{p−a_{1}} − ω^{b})^{−1}(y_{j,i} − ω^{b})  (1)

More generally, suppose that we want to define a 0-1 valued variable x so that x = 1 if y_{1} = ω^{p_{1}} and y_{2} = ω^{p_{2}} and ... and y_{k} = ω^{p_{k}}, and otherwise x = 0. Then this is accomplished by the following degree kp polynomial:

∏_{i} ∏_{p≠p_{i}}(ω^{p_{i}} − ω^{p})^{−1}(y_{i} − ω^{p})  (2)

Case (ii) is handled similarly but is somewhat more complicated. Now the elements of e are a subset of elements associated with i, and moreover we can assume without loss of generality that they must be end-segments of (i, j_{l1}, ∗), (i, j_{l2}, ∗), …, (i, j_{ll}, ∗) plus possibly either (i) or a consecutive segment of (i, j_{ll+1}, ∗). (Otherwise, x_{e} is just set to zero.) Then x_{e} should be 1 if and only if there exists values a_{1}, …, a_{r} assigned to the outgoing edges (i, j_{1}), …, (i, j_{r}) such that the partition described in the reduction above groups the elements of e together. This is a big OR (translated as a sum) (of size at most p^{r}) over the good values of a_{1}, …, a_{r} that group e together. Thus, it is expressible by a polynomial in the variables y_{i,j_{1}}, y_{i,j_{2}}, …, y_{i,j_{r}} of degree at most pr.

Step 2: Deriving MOD_{p}^{m}(r_{e}) from TS_{n}(p). We will now describe how to give small degree PC derivations of the equations MOD_{p}^{m}(r_{e}) from TS_{n}(p). Recall that the equations in MOD_{p}^{m}(r_{e}) are as follows.

1. r_{e}^{2} − r_{e} = 0 for all p-sets e

2. r_{e}r_{f} = 0 for all e, f such that e ∩ f ≠ 0, e ≠ f

3. ∑_{e,u∈e} r_{e} − 1 = 0, for all u ∈ [m].

We want to show that for every equation E that we need to derive as described above, that E is a tautological consequence of a small, constant number of equations from TS_{n}(p). Then, since each equation of TS_{n}(p) involves only a constant number of variables, by completeness of PC it will follow that there is a small-degree derivation of each equation E.

Definition. Let f_{1} = 0, …, f_{k} = 0, g = 0 be polynomial equations over a field F with underlying variables x_{1}, …, x_{n}. Then g is a tautological consequence of f_{1}, …, f_{k} if for every assignment α to the underlying variables, if all of the equations f_{1}, …, f_{k} are satisfied by α, then g = 0 is also satisfied by α.

By generalizing slightly the completeness result in [3], (Theorem 5.2 part 2), it can be shown that if g is a tautological consequence of f_{1}, …, f_{k}, all with underlying variables x_{1}, …, x_{n}, and if f_{1}, …, f_{k} includes the equations x_{i}^{p} = 1 for all variables x, then there is a degree pn derivation of g from f_{1}, …, f_{k}.

In light of the above, it is just a matter of verifying that each of the above equations E is a tautological consequence of a small number of equations from TS_{n}(p) involving a small number of variables. In particular, equations of type (1) require degree pr and equations of type (2) and (3) each require degree at most 2pr.

This completes the proof of Lemma 3. □.

4 Intuition and an upper bound

In order to first give some intuition behind the lower bound for the Tseitin tautologies, it is helpful to think about the natural PC refutation for these equations. To be concrete, we consider the mod 2 case; the others are similar.

Initially, the equations say that the number of edges out of a single vertex v is odd. These equations have degree r. Then in degree at most 2r, one can combine two of these equations to say that the number of edges out of a set of vertices of size 2 is even. Continuing in this way, if S ⊂ V, then one can derive an equation saying that the number of edges out of S, E(S), has the same parity as the size of S. This equation is most naturally expressed as m−1 = 0 if |S| is even, and m + 1 = 0 if |S| is odd, where m is the product of the variables corresponding to edges E(S), that cross between S and its complement. Thus, the degree of this polynomial is equal to the size of E(S). Proceeding this way, we eventually obtain two equations, one saying that the number of edges out of a set S_{1} is odd, and the other one saying that the number of edges out of a set S_{2} is even, where S_{1} and S_{2} are disjoint, and S_{1} ∪ S_{2} = V. This will lead to a derivation of 1, since we have now derived m + 1 and m − 1 for some monomial m. If G_{n} is highly expanding, the degree of this refutation will be large since at some point we must pass through a relatively large set, and thus the polynomial expressing that the number of edges out of this set must have the same parity as the size of the set, will be large due to expansion.

We want to show that the above almost completely characterizes what can be done with the initial equations. Suppose we have derived m − 1 = 0, where m is the set of edges E(S), such that |E(S)| = d, and |S| is even. (Or similarly, we have derived m + 1 = 0 when m is the set of edges of E(S) but now |S| is odd.) However, now it is possible to rewrite this equation in a slightly different form so that it has smaller degree. In particular, we can divide up the edges of m into two halves, m_{1} and m_{2} and rewrite the equation m − 1 = 0 instead as m_{1} − m_{2} = 0. This is derived from m − 1 in degree d by multiplying m − 1 by edges of m_{2}, one at a time, thus transferring the edges of m_{2} over to the second term, one at a time. This new equation, m_{1} − m_{2} = 0 has degree d′ = ⌈d/2⌉, and in general is not derivable by a degree d′ PC refutation. The (degree d) equations that interest us are this larger set of equations, which express the fact that the edges coming out of a set S are even (or odd) by a pair of monomials.

There are two key steps to making this intuition a proof. First, we must show that, although the PC proof can contain arbitrary polynomials, the important lines are equalities as above, or binomials if viewed as a difference. This is made formal in a very general way in section 5. Secondly, that the set of degree d equations described above, although not all provable with degree d proofs, is more natural and thus easier to understand, and they span all of the degree d derivable PC polynomials. In contrast, an explicit construction of the exact set of degree d derivable PC polynomials (as done by Razborov [8] for pigeonhole principle) seems much more difficult.

5 Binomial systems and bounds for PC

In the previous section, we reduced the problem of proving lower bounds for the mod counting principles to that of proving lower bounds for the Tseitin graph tautologies. The reason this is progress is that the Tseitin graph tautologies are expressed as a system of polynomials of a very simple form: each polynomial is a binomial, the difference of two terms (i.e., the weighted sum of two monomials with coefficients over the field.) (This fact was earlier used by Grigoriev [5] in giving lower bounds for Nullstellensatz.) A binomial a_{1}m_{1} − a_{2}m_{2} can be viewed as the equation between two terms, a_{1}m_{1} = a_{2}m_{2}. Intuitively, an algebraic proof for a binomial system should be expressible as a sequence of such equations. In the final paper, we shall formalize this intuition by giving a formal definition of the Laurent proof system on such equations, and showing equivalence to PC for binomial systems. However, we will only present the consequences of this characterization that we need for the lower bound in this version.

We use a general characterization of things provable in PC, and then show that this characterization can be refined for binomial systems. This characterization is from [4].

Definition. A degree d pseudo-ideal I is a vector space of degree at most d polynomials so that if p ∈ I and p has degree ≤ d − 1, then xp ∈ I for every variable x.

Theorem 4 [4] Let P be a system of polynomials, and let I_{d}(P) be the set of all polynomials q that have a degree d PC proof from P. Then I_{d}(P) is a d-pseudo-ideal, and for any d-pseudo-ideal I containing P, I_{d}(P) ⊆ I.

So pseudo-ideals capture provability in polynomial calculus. If equational reasoning is complete for polynomial calculus for binomial systems, it should follow that the pseudo-ideals for such systems are determined by which terms are “provably equal” from the system. In other words, pseudo-ideals should be determined by an equivalence relation on degree d terms with certain closure properties. This is formalized below.

Definition. Let R be a ring and R^{∗} a multiplicative subgroup of R, and let x_{1}, …, x_{n} be variables. (i.e., R^{∗} consists only of invertible elements and is closed under products and inverses). An R^{∗}-term is a term whose coefficient is from R^{∗}. An R^{∗}-binomial is the difference of two R^{∗}-terms. A d-Laurent relation over R^{∗}-terms is an equivalence relation ≡_{d} on R^{∗}-terms of degree at most d with the following properties: Let t_{1}, t_{2}, be R^{∗}-terms of degree at most d and let r ∈ R^{∗}.

(a) t_{1} ≡_{d} t_{2} iff rt_{1} ≡_{d} rt_{2}; and

(b) If t_{1} and t_{2} are degree at most d − 1, and t_{1} ≡_{d} t_{2} then x_{i}t_{1} ≡_{d} x_{i}t_{2} for any variable x_{i}.

If ≡_{d} is a d-Laurent relation, we define a corresponding set of binomials B_{≡_{d}} = {t_{1} − t_{2}|t_{1} ≡_{d} t_{2}} and a set of polynomials S_{≡_{d}} = SPAN_{R}(B_{≡_{d}}), the set of linear combinations of binomials in B_{≡_{d}}.

R will usually be a field, but in section 8 we will need the more general version. Intuitively, ≡_{d} represents the set of pairs of terms that can be proved equal using equational-type reasoning, where we are allowed to multiply both sides of a known equation by a constant or variable, as long as we don’t exceed degree d.

We now show that lower bounds on polynomial calculus proofs can be established by exhibiting a non-trivial d-Laurent relation.

Theorem 5 Let Q be a set of R^{∗} binomials. If ≡_{d} is a d-Laurent relation with Q ⊆ B_{≡_{d}} and 1 ≢_{d} a for any a ∈ R^{∗}, a ≠ 1, then Q has no degree d polynomial calculus refutation over R.

The proof of this theorem follows from a sequence of lemmas that take up the rest of this section. Lemma 6 is the main technical lemma, and the other lemmas describe how to use it to prove the theorem.

Lemma 6 Assume ≡_{d} is d-Laurent. Suppose f ∈ S_{≡_{d}}. Then f can be rewritten as a linear combination f = ∑_{j=1}^{T} a_{j}(t_{j} − t′_{j}) of binomials from B_{≡_{d}} such that no monomial completely cancels out, i.e., every monomial t_{j}, t′_{j} in the linear combination appears in f with non-zero coefficient.

Proof. Let f = ∑_{j} a_{j}(t_{j} − t′_{j}), where each pair of monomials in the above sum is a polynomial from B_{≡_{d}}. We prove the lemma by induction on the number of distinct monomials in the above sum. At each step, if cancellation of a monomial occurs, we will rewrite f by an equivalent sum of elements of R_{d} such that the number of monomials in the new sum is strictly smaller.

Assume m appears in the sum, without loss of generality in exactly the first T′ differences, but has zero coefficient in f. Because each element a_{j} ∈ R^{∗}, and so has an inverse, by factoring out the coefficient of m in each term, we can rewrite any elements that m appears in: c_{k}(a_{k}m − a′_{k}m′_{k}) = c_{k}a_{k}(m − a′_{k}a_{k}^{−1}m′_{k}) = d_{k}(m − t_{k}) for some R^{∗} term t_{k}. Also, by the closure properties of ≡_{d} for multiplication by constants from R^{∗}, m ≡_{d} t_{k}. Now, since m has coefficient 0 in f, ∑_{k} d_{k} = 0.

We claim that the sum of binomials containing m, ∑_{k=1}^{T′} d_{k}(m − t_{k}), can be rewritten as ∑_{k=2}^{T′} d_{k}(t_{1} − t_{k}). This is because ∑_{k=2}^{T′} d_{k}(t_{1} − t_{k}) = (∑_{k=2}^{T′} d_{k})(t_{1}) − ∑_{k=2}^{T′} d_{k}t_{k} = −d_{1}(t_{1}) − ∑_{k=2}^{T′} d_{k}t_{k} = − ∑_{k=1}^{T′} d_{k}t_{k} = (∑_{k=1}^{T′} d_{k})m − ∑_{k=1}^{T′} d_{k}t_{k} = ∑_{k=1}^{T′} d_{k}(m − t_{k}).

Since ≡_{d} is transitive, t_{1} ≡ t_{k} for all k. So this substitution rewrites f as a weighted sum of members of B_{≡_{d}}. The new sum is without m and without any monomial not in the previous sum, so contains one fewer monomial. □

Lemma 7 If ≡_{d} is d-Laurent, and there is a c ∈ R, c ≠ 0 with c ∈ S_{≡_{d}}, then there is an a ∈ R^{∗}, a ≠ 1 with 1 ≡_{d} a.

Proof. If c ∈ S_{≡_{d}}, by Lemma 6, c can be written as a sum of equivalent terms which only have monomials that appear in c, i.e, are constants. Thus, at least two distinct constants a ≡_{d} a′, and then 1 ≡_{d} a′a^{−1}. □

Lemma 8 If ≡_{d} is d-Laurent, then S_{≡_{d}} is a degree d pseudo-ideal.

Proof. By definition, S_{≡_{d}} is a vector space of polynomials of degree at most d, so we just need to show closure under multiplication by a variable, provided the total degree is at most d. Assume f ∈ S_{≡_{d}} has degree at most d − 1. By Lemma 6, we can write f = ∑_{i=1}^{T} c_{i}(t_{i} −t′_{i}), where t_{i} ≡_{d} t′_{i} and each t_{i}, t′_{i} comes from a monomial with non-zero coefficient in f. In particular, each t_{i}, t′_{i} has degree at most d − 1. Therefore, xt_{i} ≡ xt′_{i} by the second closure property in the definition of d-Laurent relation. So xf = ∑_{i=1}^{T} c_{i}(xt_{i} − xt′_{i}) ∈ S_{≡_{d}}. □

Proof (of Theorem 5). Let ≡_{d} be a d-Laurent relation with Q ⊆ B_{≡_{d}}, and that 1 ≢_{d} a for any 1 ≠ a ∈ R^{∗}. Assume Q has a polynomial calculus refutation of degree d over R, i.e., proves some c ≠ 0, c ∈ R. Then c ∈ S_{≡_{d}}, since the latter is a pseudo-ideal containing Q. But then 1 ≡_{d} a for some a ≠ 1, a ∈ R^{∗}. This contradiction proves the theorem. □.

6 PC lower bound for mod 2

We first prove linear lower bounds for the Tseitin principle TS_{n}(2) for polynomial calculus over fields of characteristic q > 2, provided the underlying graph is an expander graph.

Definition. Let G = (V, E) be an undirected graph. G has expansion ϵ if for any subset S of vertices with |S| ≤ |V |/2, |N(S)| ≥ (1 + ϵ)|S|, where N(S) is the set of nodes adjacent to nodes in S.

Theorem 9 Let F be a field and let G_{n} have expansion ϵ. For all d < ϵn/8, there is no degree d PC refutation of TS_{n}(2) over F.

Note that there is no restriction on the characteristic q of the field F. When q is an odd prime or zero, then the T S_{n}(2) polynomials are unsatisfiable and therefore have a PC refutation over F, of degree which is necessarily linear by the theorem. When q = 2, then the T S_{n}(2) polynomials are easily seen to be satisfiable (trivially, since 1 = −1), and there is no PC-refutation of T S_{n}(2) at all.

It is an easy corollary of Theorem 9 and Lemmas 1 and 3 that over a field of characteristic q ≠ 2, PC-refutations of the MOD_{2}^{n} polynomials require size linear in n: this is established as Corollary 19 below for general p in place of 2.

Preparatory to proving Theorem 9, we establish some definitions and lemmas. In what follows, we will reduce all polynomials by y_{i,j}^{2} = 1 for all variables, thus obtaining only multilinear polynomials.

Definition. For a monomial m = ∏_{i} y_{i}^{f_{i}}, define the multilinearization \overline{m} of m to be ∏_{i} y_{i}^{f_{i} mod 2}. For a multilinear monomial m we define E_{m} to be the set of edges e such that y_{e} is a factor of m.

Definition. For two sets A, B, A +_{2} B denotes the disjoint union of A and B.

Definition. Let S ⊆ V, where V is the set of vertices in G_{n}. Then E(S) is defined to be the set of edges with exactly one endpoint in S and one endpoint outside of S.

Proposition 10 Let G_{n} be an expander graph with expansion ϵ. If S ⊆ V, |S| ≤ n/2, then |E(S)| ≥ ϵ|S|.

Proof Since |S| ≤ n/2, |N(S)| ≥ (1 + ϵ)|S| by the definition of expansion. Then |N(S) − S| ≥ ϵ|S|, and each node in N(S) − S is the endpoint of at least one edge in E(S).

We shall prove Theorem 9 as a corollary to Theorem 5: for this, we let R = F and R^{∗} = {−1, 1}. The R^{∗}-terms are thus just the terms m and −m where m is a monomial.

Definition. We define an equivalence relation ≡_{d} on the R^{∗}-terms of degree at most d multilinear monomial, as follows. Let b_{1}, b_{2} ∈ {0, 1}, (−1)^{b_{1}}m_{1} ≡_{d} (−1)^{b_{2}}m_{2} if there exists a set S ⊂ V such that

1. E\overline{m_{1}m_{2}} = E(S).

2. |S| < n/2; and

3. |S| ≡ b_{2} − b_{1} (mod 2).

We will show that there is no degree d < ϵn/8 PC refutation of TS_{n}(2) by showing that that ≡_{d} is a d-Laurent relation.

Lemma 11 If d < ϵn/8, then the relation ≡_{d} is an equivalence relation.

Proof. It is easy to see from the definitions that (−1)^{b}m ≡_{d} (−1)^{b}m and that (−1)^{b_{1}}m_{1} ≡_{d} (−1)^{b_{2}}m_{2} iff (−1)^{b_{2}}m_{2} ≡_{d} (−1)^{b_{1}}m_{1}. We need to show that if (−1)^{b_{1}}m_{1} ≡_{d} (−1)^{b_{2}}m_{2} and (−1)^{b_{2}}m_{2} ≡_{d} (−1)^{b_{3}}m_{3}, then (−1)^{b_{1}}m_{1} ≡_{d} (−1)^{b_{3}}m_{3}. Let S_{1} be the set of vertices such that E(S_{1}) = E\overline{m_{1}m_{2}}, |S_{1}| ≡ b_{2} − b_{1} (mod 2), |S_{1}| < n/2, and similarly let S_{2} be the set of vertices such that E(S_{2}) = E\overline{m_{2}m_{3}}, |S_{2}| ≡ b_{3} − b_{2} (mod 2), |S_{2}| < n/2. We want to show that S′ = S_{1} +_{2} S_{2} is a set of vertices such that E(S′) = E\overline{m_{1}m_{3}}, |S′| = b_{3} − b_{1}, and |S′| < n/2. Intuitively, this is saying that if S_{1} has parity b_{2} − b_{1} which equals the parity of |E(S_{1})|, and S_{2} has parity b_{3} − b_{2}, which equals the parity of |E(S_{2})|, then S_{1}+_{2}S_{2} has parity b_{3}−b_{1}, which equals the parity of |E(S_{1}+_{2}S_{2})|. And furthermore, |S_{1} +_{2} S_{2}| is not too large.

Clearly, |S′| mod 2 = |S_{1}| mod 2 + |S_{2}| mod 2 = b_{2} − b_{1} + b_{3} − b_{2} = b_{3} − b_{1}. Also we have: E(S_{1} +_{2} S_{2}) = E(S_{1}) +_{2} E(S_{2}) = E\overline{m_{1}m_{2}m_{2}m_{3}} = E\overline{m_{1}m_{3}}.

It is left to show that |S′| < n/2. Since |m_{1}|, |m_{2}| ≤ d, it follows that |E(S_{1})| ≤ |m_{1}m_{2}| ≤ 2d. Since G_{n} is an expander graph, Proposition 10 implies that |E(S_{1})| ≥ ϵ|S_{1}|, and thus it follows that |S_{1}| ≤ 2d/ϵ < n/4. Similarly, |S_{2}| ≤ n/4. Thus, |S′| ≤ |S_{1}|+|S_{2}| < n/2. In fact, since |E(S′)| ≤ |m_{1}m_{3}| ≤ 2d, Proposition 10 further implies that |S′| ≤ n/4. □

Lemma 12 For d ≤ ϵn/8, ≡_{d} is a d-Laurent relation.

Proof. Let d ≤ ϵn/8. We just established that ≡_{d} is an equivalence relation. Condition (a) of the definition of d-Laurent is trivially satisfied from the definition of ≡_{d}. Also, the fact that (−1)^{b_{1}}m_{1} ≡_{d} (−1)^{b_{2}}m_{2} is defined in terms of the linearization of m_{1}m_{2} means that condition (b) of the definition of d-Laurent is also satisfied. □.

Lemma 13 Every polynomial of T S_{n}(2) is a binomial from B_{≡_{d}}.

Proof. There are two kinds of polynomials in T S_{n}(2). For the equations y_{e}^{2} −1, we must show that y_{e}^{2} ≡_{d} 1. This is easily done by taking S = ∅ and noting that since \overline{y_{e}^{2}1} = 1, the three conditions of the definition of ≡_{d} are trivially satisfied. For the equations of the form 1 + y_{{i,j1}}y_{{i,j2}} ⋯ y_{{i,jr}} = 0, we must show that 1 ≡_{d} (−1)y_{{i,j1}}y_{{i,j2}} ⋯ y_{{i,jr}}. This is easily seen to hold with S = {i}. □

Proof of Theorem 9. This is a consequence of Theorem 5. First, Lemma 12 shows ≡_{d} is d-Laurent. Second, Lemma 13 shows T S_{n}(2) ⊂ B_{≡_{d}}. It remains to show that 1 ≢_{d} (−1). To prove this suppose 1 ≡_{d} (−1) holds with some set S satisfying the conditions of the definition ≡_{d}. Now we must have E(S) = ∅. But on the other hand, |S| < n/2, so Lemma 10 implies E(S) is non-empty — a contradiction. Therefore, the hypotheses of Theorem 5 hold, and there is no PC refutation of T S_{n}(2) over F of degree d. □

7 PC lower bound for the general case

This section proves the following theorem giving linear lower bounds on the degree of PC refutations of TS_{n}(p) over a field F of characteristic q.

Theorem 14 Let F be a field of characteristic q, and let G_{n} be an r-regular graph with expansion ϵ. Then, for all d < ϵn/8, there is no degree d PC refutation of TS_{n}(p) over F.

As a corollary to this theorem and Lemmas 1 and 3, we shall prove (as Corollary 19) that when q ∤ p, any PC refutation of the MOD_{p}^{n} polynomials over F requires linear degree.

In order to express the T S_{n}(p) polynomials, F must contain a p-th primitive root of unity, ω. We let R = F and R^{∗} be the powers of the root of unity, i.e., R^{∗} = {1, ω, ω^{2}, …, ω^{p−1}}. For the rest of this section, it is sufficient to assume only that R is a ring (rather than a field). See section 8 for more explanation of what it means for a ring to have a p-th root of unity.

Definition. Let A and B be two multisets sets. Then A +_{p} B denotes the multiset, where if x occurs in A with multiplicity a mod p, and in B with multiplicity b mod p, then x occurs in A +_{p} B with multiplicity (a + b) mod p. Note that when A and B are ordinary sets and p = 2, then A +_{2} B is simply the disjoint union of A and B.

Definition. Let S = {s_{1}, …, s_{n}}, where each s_{i} ∈ [0, p − 1]. We will think of S as a multiset over the vertices V in G, where vertex i occurs in the set with multiplicity s_{i}. E(S) will denote a multiset of edges from G′_{n} as follows. Edge ⟨i, j⟩ occurs with multiplicity 0 if s_{i} − s_{j} is negative, and occurs with multiplicity s_{i} − s_{j} otherwise.

The size of S, |S|, will be k if and only if the number of nonzero elements in S is k. In other words, the size of a multiset is the number of elements that appear at least once in the multiset. The size of E(S) is defined similarly.

Proposition 15 Let G_{n} be an expander graph with expansion ϵ. If |S| ≤ n/2, then |E(S)| ≥ ϵ|S|.

Proof. Even though S and E(S) are multisets and the definition of ‘size’ is correspondingly modified, the proof of Proposition 10 still applies word-for-word. (In fact, when members of S have different non-zero multiplicities, it only makes the size of E(S) increase.) □

Definition. We define the binary relation ≡_{d} on the R^{∗}-terms ω^{b}m where m is a degree at most d monomial and 0 ≤ b < p. ω^{b_{1}}m_{1} ≡_{d} ω^{b_{2}}m_{2} if there exists a multiset S of vertices such that (i) The multiset of edges in m_{1}m_{2}^{−1} (after applying y_{i,j}^{p} = 1, and y_{i,j}y_{j,i} = 1) equals E(S); (ii) |S| < n/2; and (iii) ∑_{i} s_{i} ≡ b_{2} − b_{1} (mod p).

The next three lemmas are proved exactly analogously to Lemmas 11-13.

Lemma 16 For d ≤ ϵn/8, the relation ≡_{d} is an equivalence relation.

Lemma 17 For d ≤ ϵn/8, ≡_{d} is a d-Laurent relation.

Lemma 18 Every polynomial of T S_{n}(2) is a binomial from B_{≡_{d}}.

Proof of Theorem 14. Exactly as argued in the proof of Theorem 9, we have that 1 ≢_{d} a for any a ∈ R^{∗} distinct from 1, i.e., 1 ≢_{d} ω^{i} for all 0 < i < p − 1. Thus Theorem 14 follows from Theorem 5 using Lemmas 17 and 18. □

Corollary 19 Let q ≥ 2 be a prime such that q ∤ p and let F be a field of characteristic q. Any PC-refutation of the MOD_{p}^{n} polynomials requires degree > δn, for some constant δ > 0.

Proof. Choose constants ϵ and r so that there are r-regular graphs G_{n} of expansion ϵ for all n. Let d_{1} = d_{2} = 2pr. Suppose MOD_{p}^{m} has a degree d_{3} PC refutation, where m = n+nrp. By Lemmas 1 and 3 TS_{n}(p) has a degree d_{3}d_{1} PC refutation, so by Theorem 14, d_{3}d_{1} > ϵn/(8pr). Thus, d_{3} > ϵm/(16p^{2}r^{2}(1+rp)). Since ϵ, r, p, d are constants, this proves the Corollary. □

8 Polynomial calculus over rings

We now consider the polynomial calculus over rings instead of over fields. For this, we consider a fixed ring R and the polynomials have coefficients from R. (By ‘ring’ we always mean ‘commutative ring’.) Since the definition of the polynomial calculus did not use any field-specific properties, e.g., since the definition did not depend on the existence of inverses, it is completely natural to consider the polynomial calculus over rings. As before, we define a PC derivation to be a sequence of polynomials ⟨P_{i}⟩_{i} with the same rules of addition and multiplication. However, we modify the definition of a PC refutation of Q to be a PC derivation that ends with a constant polynomial m where m ∈ R is non-zero (and its derivation thus corresponds to a derivation of the contradiction m = 0).

It is known that the polynomial calculus over rings is complete with respect to Boolean reasoning, i.e., if the initial polynomials include x^{2} − x = 0 for each variable x then any unsatisfiable set of polynomials has a PC refutation. However, the polynomial calculus over rings is not complete for general derivations, see the examples in [2]. In this respect the polynomial calculus over a field is stronger than the polynomial calculus over a ring. On the other hand, if the ring R is ℤ_{m} where m = p_{1} · p_{2} for distinct primes p_{1}, p_{2}, then it is well-known that there are constant-degree polynomial calculus proofs of MOD_{p_{1}}^{n} and MOD_{p_{2}}^{n}. But Theorem 14 implies that there is no single field for which the polynomial calculus has constant degree proofs of both these principles.

The situation is a little analogous to an important open problem in circuit complexity. Namely, Smolensky [9] showed that polynomial size constant-depth circuits with mod-q gates cannot compute the mod-p function for distinct primes p, q. However, it is open whether this is true for composite values of q where p ∤ q.

We prove below that if p and q are relatively prime, then over the ring Z_{q}, any PC refutation of MOD_{p}^{n} requires degree ≥ δn for some constant δ. The general outline of the proof is similar to the approach used for the proof of Theorem 14.

In the next section, we do some preliminary work introducing rings with roots of unity. Following that, we discuss the reduction of the Tseitin principle to the mod p counting principle and then discuss the lower bound for Tseitin principle.

8.1 Rings with roots of unity

We are mostly interested in lower bounds on the degree of polynomial calculus refutations over rings R = ℤ_{q}; however, our method of proof depends strongly on the use of p-th roots of unity, and on the existence of inverses of certain terms involving the p-th root of unity. In this section, we prove that there exist rings containing ℤ_{q} with the desired p-th roots of unity.

Theorem 20 Let p, q > 1 be relatively prime. Then there is a finite ring R ⊃ Z_{q} which contains a p-th root of unity ω such that

(a) p is the least positive integer i such that ω^{i} = 1,

(b) For all 0 ≤ j < k < p, (ω^{k} − ω^{j}) has an inverse in R.

Proof. First we shall give a simple proof for the case where q is a product of distinct primes q = r_{1} · r_{2} ⋯ r_{m}. For this, let GF_{r} be the field of order r and let F_{i} = GF_{r}[ ^{p} \sqrt{1}] be the extension of GF_{r} obtained by adjoining a p-th root of unity. We use ω_{i} to denote a p-th root of unity in F_{i}. Define R to be the ring with domain ∏_{i} F_{i} and component-wise addition and multiplication. An element of R is an m-tuple ⟨a_{1}, …, a_{m}⟩ with a_{i} ∈ F_{i}. By the Chinese remainder theorem, a copy of Z_{q} is embedded in R by n ↦ ⟨n mod r_{1}, …, n mod r_{m}⟩. The element ⟨a_{1}, …, a_{m}⟩ has an inverse in R iff each a_{i} ≠ 0. Letting ω = ⟨ω_{1}, …, ω_{m}⟩, it is easy to see that ω is a p-th root of unity in R and satisfies property (a). Likewise, ω_{i}^{k} − ω_{i}^{j} ∈ F_{i} is non-zero for all i and thus (ω^{k} − ω^{j})^{−1} exists in R.

Now consider the general case, where q is not a product of distinct primes. (We don’t use any special properties of Z_{q} beyond the fact that p^{−1} exists in Z_{q}, which follows from the fact that p and q are relatively prime.) Consider a primitive p-th root of unity, ν, over the field of rationals. As a root of unity, ν is a root of the polynomial x^{p−1} + x^{p−2} + ⋯ + x^{2} + x + 1. Likewise, for any ℓ < p dividing p, ν^{ℓ} is a primitive (p/ℓ)-th root of unity, so ν is a root of x^{(ℓ−1)p/ℓ} + x^{(ℓ−2)p/ℓ} + ⋯ + x^{p/ℓ} + 1. It follows that there is a non-constant polynomial Q(x) which is the greatest common divisor of each of these polynomials which has ν as a root. Furthermore, by Gauss’s lemma, we may choose the polynomial Q(x) with leading coefficient 1 and integer coefficients. We define R to be the extension ring Z_{q}[ω]/(Q(ω)). Formally, this means we define an equivalence relation on the set Z_{q}[ω] of univariate polynomials over Z_{q} by

f ∼ g ↔ ∃h ∈ Z_{q}[ω], f(ω) − g(ω) = h(ω) · Q(ω).

Clearly this is an equivalence relation, and addition and multiplication respect ∼. The ring R = Z_{q}[ω]/(Q(ω)) =_{df} Z_{q}[ω]/ ∼ has domain the set of ∼-equivalence classes (but we generally abuse notation by writing f ∈ R instead of [f] ∈ R, etc.) Clearly R is a ring. In R, each polynomial x^{(ℓ−1)p/ℓ} + x^{(ℓ−2)}p/ℓ + ⋯ + x^{p/ℓ} + 1 is equal to zero, since it is a multiple of Q. Therefore ω^{p} = 1 in R (i.e., w^{p} ∼ 1) since

(ω − 1) · (ω^{p−1} + ω^{p−2} + ⋯ + ω + 1) = ω^{p} − 1.

Also note that no constant of Z_{q} becomes equal to zero in R: this is immediate from the fact that Q is a non-constant, monic polynomial over Z_{q}.

It remains to prove that if k ≠ ℓ, 0 ≤ k, ℓ < p, then (ω^{k} − ω^{ℓ}) has a (multiplicative) inverse in R. Since (ω^{k} − ω^{l}) = ω^{ℓ}(ω^{k−ℓ} − 1) and ω^{ℓ} has inverse in R, it will suffice to prove that (ω^{k} − 1) has an inverse in R for all 1 ≤ k < p.

Define i_{0} = 0 and i_{n+1} = i_{n} + k mod p. Let ℓ be the least value such that i_{ℓ} = 0; of course ℓ divides p. Therefore the values i_{0}, …, i_{ℓ−1} are distinct and enumerate all the values in {0, p/ℓ, 2p/ℓ, …, (ℓ − 1)p/ℓ}. For 0 ≤ j < ℓ, let v(j) be the value such that i_{v(j)} = j, 0 ≤ v(j) < ℓ. Define

f(ω) = ∑_{j=0}^{ℓ−1} v(j)ω^{j} = ∑_{n=0}^{ℓ−1} n · ω^{i_{n}}.

Claim: (ω^{k} − 1)f(ω) = ℓ holds in R.

Since ℓ has an inverse in Z_{q}, the claim immediately implies that (ω^{k} − 1) has in inverse in R, namely, ℓ^{−1}f(ω).

In R we have

(ω^{k} − 1) · f(ω) = ∑_{n=0}^{ℓ−1} nω^{i_{n}+k} − ∑_{n=0}^{ℓ−1} nω^{i_{n}}

= ∑_{n=1}^{ℓ}(n − 1)ω^{i_{n}} − ∑_{n=1}^{ℓ−1} nω^{i_{n}}

= (ℓ − 1) · ω^{i_{ℓ}} − ∑_{n=1}^{ℓ−1} ω^{i_{n}}

= (ℓ − 1) · 1 + 1 − ∑_{n=0}^{ℓ−1} ω^{i_{n}}

= ℓ − ∑_{n=0}^{ℓ−1} ω^{i_{n}} = ℓ − ∑_{n=0}^{ℓ−1} ω^{np/ℓ}
= ℓ − 0 = ℓ.

That completes the proof of the claim and of Theorem 20 □

For the next two sections, we shall consider p and q to be fixed and let R be as in Theorem 20

8.2 Low degree reductions

Lemma 1 clearly still applies to the polynomial calculus over rings, but Lemma 3 needs to be reproved for rings. Let q, p, R be as in the previous theorem.

Lemma 21 Over the ring R, TS_{n}(p) is (d_{1}, d_{2}) reducible to MOD_{p}^{m}, where m = n + nrp, d_{1} = 2pr and d_{2} = 2pr.

Proof. The reduction is exactly the same as the reduction used for the proof of Lemma 3. Examination of the definition of r_{e} in Step 1 of that proof reveals that the only place where inverses were used was in the polynomials (1) and (2) and these were inverses of elements of the form ω^{a_{1}} − ω^{a} which do exist in R. So it remains to re-do Step 2 of the proof of Lemma 3.

Recall that we must find small degree PC derivations of MOD_{p}^{m}(r_{e}) equations:

1. r_{e}^{2} − r_{e} = 0 for all p-sets e

2. r_{e}r_{f} = 0 for all e, f such that e ∩ f ≠ 0, e ≠ f

3. ∑_{e,u∈e} r_{e} − 1 = 0, for all u ∈ [m].

As discussed before, each single equation is a tautological consequence of a constant number of equations of TS_{n}(p). We now need to extend the completeness theorem of [3], Theorem 5.2, to apply to the polynomial calculus over R.

Lemma 22 Let z_{1}, …, z_{k} be variables, and f(z⃗) be a polynomial. Suppose that in the ring R, f(z_{1}, …, z_{k}) = 0 for all values of z_{1}, …, z_{k} ∈ {1, ω, ω^{2}, …, ω^{p−1}}. Then there is PC derivation of f(z⃗) from the polynomials z_{i}^{p} − 1, of degree ≤ pk · deg(f).

Proof. We give the proof for the case k = 1 and leave it the reader to formulate the proof by induction for the case k > 1. (All the essential difficulties arise already in the case k = 1.) Let P_{a} be the polynomial

(z_{1} − ω^{0})(z_{1} − ω^{1}) ⋯ (z_{1} − ω^{a−1})(z_{1} − ω^{a+1}) ⋯ (z_{1} − ω^{p−1}).

Note that P_{a} · (z_{1} − ω^{a}) is the polynomial z_{1}^{p} − 1 (this is immediate from the fact that they are the same polynomial in each field F_{q_{i}}).

Claim: Let c = f(ω^{a}) ∈ R. The polynomial P_{a} · (f(z_{1}) − c) is PC derivable from z_{i}^{p} − 1 in degree (p − 1) · deg(f).

The claim is proved by induction on the size of the polynomial f. The base case where f is a constant is trivial. The second base case where f(z_{1}) is just z_{1} is immediate from the observation above that P_{a} · (z_{1} − ω^{a}) = z_{1}^{p} − 1. The induction steps of addition and multiplication are handled by the following two constructions:

\frac{P_{a} · (f − c) P_{a} · (g − d)}{P_{a} · ((f + g) − (c + d))}

and

\frac{\frac{P_{a} · (f − c)}{P_{a} · (fg − cg)} \frac{P_{a} · (g − d)}{P_{a} · (cg − cd)}}{P_{a} · (fg − cd)}

and this proves the claim.

Now let P_{a}^{ℓ} be the polynomial ∏_{{i≥ℓ \atop i≠a}} (z_{1} − ω^{i}). We only use this polynomial when a ≥ ℓ.

Claim: Let ℓ ≥ 0 and let c = f(ω^{a}) ∈ R. The polynomial P_{a}^{ℓ} · f(z_{1}) is PC derivable from z_{i}^{p} − 1 in degree (p − 1) deg(f).

The second claim is proved by induction on ℓ. The base case, where ℓ = 0 is already established by the first claim, since P_{a}^{0} = P_{a}. For the induction step, let a ≥ ℓ + 1. The induction hypothesis tells us that P_{ℓ}^{ℓ}f(z_{1}) and P_{a}^{ℓ} · f(z_{1}) are both PC derivable. Subtracting these gives

(ω^{ℓ} − ω^{a})P_{a}^{ℓ+1} · f(z_{1}).

Since (ω^{ℓ} − ω^{a}) is invertible in R, we may multiply by (ω^{ℓ} − ω^{a})^{−1} to derive P_{a}^{ℓ+1} · f(z_{1}), and the claim is proved.

The base case k = 1 of Lemma 21 is immediate from the second claim, with ℓ = p. The argument for the induction step is similar and is left to the reader. □

8.3 PC lower bound for rings

We now prove the main theorems giving lower bounds the degrees of of PC derivations over ℤ_{q}. Fix p, q,R as above.

Theorem 23 Let G_{n} be an r-regular graph with expansion ϵ. Then, for all d < ϵn/4, there is no degree d PC refutation of TS_{n}(p) over R.

This plus Lemmas 1 and 21 immediately imply:

Corollary 24 Let p, q ≥ 2 be relatively prime. Any PC-refutation over Z_{q} of the MOD_{p}^{n} polynomials requires degree > δn, for some constant δ > 0.

The constant δ depends on p and q. To prove Theorem 23, we need merely note that the proof of Theorem 14 still applies: We take R^{∗} = {1, ω, ω^{2}, …, ω^{p−1}} and then, as already noted near the beginning of section 7, the proof of Theorem 14 establishes Theorem 23.

Acknowledgement. We thank A. Wadsworth for discussions about ring extensions.

References

[1] P. Beame, R. Impagliazzo, J. Krajíček, T. Pitassi, and P. Pudlák, Lower bounds on Hilbert’s Nullstellensatz and propositional proofs, Proceedings of the London Mathematical Society, 73 (1996), pp. 1–26.

[2] S. R. Buss, Lower bounds on nullstellensatz proofs via designs, in Proof Complexity and Feasible Arithmetics, P. Beame and S. Buss, eds., American Mathematical Society, 1998, pp. 59–71.

[3] S. R. Buss, R. Impagliazzo, J. Krajíček, P. Pudlák, A. A. Razborov, and J. Sgall, Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, Computational Complexity, 6 (1996/1997), pp. 256–298.

[4] M. Clegg, J. Edmonds, and R. Impagliazzo, Using the Groebner basis algorithm to find proofs of unsatisfiability, in Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, 1996, pp. 174–183.

[5] D. Grigoriev, Nullstellensatz lower bounds for Tseitin tautologies. To appear, 39th Annual ACM Symp. on Theory of Computing, 1998.

[6] J. Krajíček, On the degree of ideal membership proofs from uniform families of polynomials over a finite field. Typeset manuscript, 1998.

[7] T. Pitassi, Algebraic propositional proof systems, in Descriptive Complexity and Finite Models, N. Immerman and P. Kolaitis, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science #31, American Mathematics Society, 1996, pp. 215–244.

[8] A. A. Razborov, Lower bounds for the polynomial calculus. Typeset manuscript, 1996.

[9] R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proceedings of the Nineteenth Annual ACM Symposium on the Theory of Computing, ACM Press, 1987, pp. 77–82.