COMPLEXITY OF POSITIVSTELLENSATZ PROOFS FOR THE KNAPSACK

D.Grigoriev

Abstract. A lower bound is established on degrees of Positivstellensatz calculus refutations (over a real field) introduced in (Grigoriev & Vorobjov 1999; Grigoriev 1999), for the knapsack problem. The bound depends on the values of coefficients of an instance of the knapsack problem: for certain values the lower bound is linear and for certain values the upper bound is constant, while in the polynomial calculus the degree is always linear (regardless of the values of coefficients) (Impagliazzo et al. 1997). This shows that the Positivstellensatz calculus can be strictly stronger than the polynomial calculus from the point of view of the complexity of the proofs. Keywords. polynomial calculus, Positivstellensatz proofs, complexity of the knapsack Subject classification. 68Q25

Introduction

In recent years there has been an intensive activity in the research of algebraic proof systems (Beame et al. (1996); Buss et al. (1999, 1996/1997); Clegg et al. (1996); Grigoriev (1998); Impagliazzo et al. (1999); Razborov (1998) ). The approach relies on Hilbert’s Nullstellensatz and treats the problem of feasibility of a system of polynomial equations

f_{1} = ⋯ = f_{k} = 0,

where among the polynomials f_{1}, …, f_{k} ∈ F [X_{1}, …, X_{n}], there appear the polynomials X_{1}^{2} − X_{1}, …, X_{n}^{2} − X_{n} (the so-called, Boolean case). Note that this problem is, in general, NP -complete.

The Nullstellensatz proof system (NS) was first considered in (Beame et al. 1996). The aim of the system is to find the polynomials g_{1}, …, g_{k} ∈ F [X_{1}, …, X_{n}] such that 1 = g_{1}f_{1}+⋯+g_{k}f_{k}. The latter representation is sometimes called a Nullstellensatz refutation. The number max_{1≤i≤k}{deg(g_{i}f_{i})} is called the Nullstellensatz degree. A linear upper bound O(n) on the Nullstellensatz degree is evident, in (Beame et al. 1996) a non-constant lower bound was proved, while after a series of improvements in (Grigoriev 1998) a linear (and thus sharp) lower bound was proved.

In (Clegg et al. 1996) a stronger proof system — polynomial calculus (PC) was introduced. Starting from axioms f_{1}, …, f_{k}, PC allows one to derive new polynomials from two given polynomials a, b ∈ F [X_{1}, …, X_{n}], according to the following two rules:

1. (additive) a, b ⊢ αa + βb, where α, β ∈ F;

2. (multiplicative) a ⊢ X_{i}a for 1 ≤ i ≤ n.

The aim of a derivation is to achieve 1.

The degree of a PC derivation is defined as the maximum of the degrees of all intermediately derived polynomials. The first lower bound on the degrees of PC derivations was obtained in (Razborov 1998) (see also (Impagliazzo et al. 1999) and (Buss et al. 1996/1997)). A linear lower bound for PC for Tseitin’s tautologies was proved in Buss et al. (1999, 2001). Note that the latter bound is sharp.

In (Grigoriev & Vorobjov 2001), for the case of input polynomials f_{1}, …, f_{k} ∈ R[X_{1}, …, X_{n}] with real coefficients, derivations of inequalities as well as equalities were considered. The case of linear inequalities with added conditions X_{i}^{2} = X_{i} (Boolean programming) was widely studied by means of cutting planes proofs, for which an exponential lower bound on the length was obtained (a survey and references can be found in (Pudlák 1999)). Another approach to systems of linear inequalities was undertaken in Lovász (1994); Lovász & Schrijver (1991); Stephen & Tunçel (1999), where a derivation system was introduced which, given any linear polynomial e, allows one to derive e^{2} ≥ 0, given any already derived linear inequalities a_{1} ≥ 0, a_{2} ≥ 0, allows one to derive a_{1} + a_{2} ≥ 0, a_{1}a_{2} ≥ 0, and, given any already derived quadratic inequalities p_{1} ≥ 0, p_{2} ≥ 0, allows one to derive p_{1} + p_{2} ≥ 0. In (Pudlák 1999) one can find some remarks on the complexity of this (called Lovász-Schrijver) procedure, in particular, an upper bound for the Pigeon Hole Principle (written as a system of linear inequalities).

More precisely, following (Grigoriev & Vorobjov 2001), let a system of equations and inequalities

f_{1} = ⋯ f_{k} = 0, h_{1} ≥ 0, …, h_{m} ≥ 0. (0.1)

Positivstellensatz proofs for the Knapsack 3

be given. Dealing with systems of inequalities one could get profit from using the axiom that any square is non-negative, and the rules of adding or multiplying inequalities. This is formalized in the following notion of the cone (which replaces the role of ideals for systems of equations) and in two proof systems described below for refuting systems of inequalities, they extend the systems NS and PC, respectively.

Definition 0.2. The cone c(h_{1}, …, h_{m}) generated by polynomials h_{1}, …, h_{m} ∈ R[X_{1}, …, X_{n}] is the smallest family of polynomials containing h_{1}, …, h_{m} and satisfying the following rules:

(a) e^{2} ∈ c(h_{1}, …, h_{m}) for any e ∈ R[X_{1}, …, X_{n}];

if a, b ∈ c(h_{1}, …, h_{m}), then

(b) a + b ∈ c(h_{1}, …, h_{m});

(c) ab ∈ c(h_{1}, …, h_{m}).

Remark 0.3. The minimal cone c(∅) consists of all sums of squares of polynomials.

Remark 0.4. Any element of c(h_{1}, …, h_{m}) can be represented in a form

∑_{I⊂{1,... ,m}}(∏_{i∈I} h_{i})(∑_{j} e_{I,j}^{2})

for some polynomials e_{I,j} ∈ R[X_{1}, …, X_{n}].

The two proof systems introduced in (Grigoriev & Vorobjov 2001) (which could be viewed as static and dynamic, respectively), rely on the following Positivestellensatz (see Bochnak et al. (1998); Stengle (1974)).

Positivstellensatz. A system (0.1) has no common solutions in R^{n} if and only if for a suitable polynomial f ∈ R[X_{1}, …, X_{n}] from the ideal (f_{1}, …, f_{k}) and a polynomial h ∈ c(h_{1}, …, h_{m}) we have: f + h = −1.

The first (static) proof system is stronger than NS refutations and could be viewed as its Positivstellensatz analogue.

Definition 0.5. A pair of polynomials

(f, h) = ( ∑_{1≤s≤k} f_{s}g_{s}, ∑_{I⊂{1,... ,m}}(∏_{i∈I} h_{i})(∑_{j} e_{I,j}^{2}))

with f + h = −1 where g_{i}, e_{I,j} ∈ R[X_{1}, …, X_{n}] we call a Positivstellensatz refutation for (0.1) (we denote it by P S_{>}). The degree of the refutation is

max_{s,I,j}{deg(f_{s}g_{s}), deg(e_{I,j}^{2} ∏_{i∈I} h_{i})}.

The second (dynamic) proof system is stronger than PC and could be viewed as its Positivstellensatz analogue.

Definition 0.6. Let a polynomial f ∈ (f_{1}, …, f_{k}) be derived in PC from the axioms f_{1}, …, f_{k}, and let a polynomial h ∈ c(h_{1}, …, h_{m}) be derived, applying the rules (a), (b), (c) from Definition 0.2, from the axioms h_{1}, …, h_{m}. Suppose that f + h = −1. This pair of derivations we call a Positivstellensatz calculus refutation for (0.1) (we denote it by P C_{>}). By its degree we mean the maximum of the degrees of intermediate polynomials from both derivations. The length of the refutation we define as the total number of steps in both derivations.

In the present paper we consider just the systems of equations f_{1} = ⋯ = f_{n} = 0 (the polynomials h_{1}, …, h_{m} are absent). In this case a polynomial h is just a sum of squares ∑_{j} h_{j}^{2} (cf. Remark 0.3).

In (Grigoriev & Vorobjov 2001) a so-called telescopic system of equations due to Lazard-Mora-Philippon is considered and an exponential lower bound on the degree of any its P S_{>} refutation (see Definition 0.5) is proved. On the other hand it is shown a linear upper bound for the telescopic system on the degree of PC, being sharp because a linear lower bound is proved in (Grigoriev & Vorobjov 2001) for the stronger system of the P C_{>} refutations (see Definition 0.6), and for the latter one also an exponential lower bound on the lengths of proofs is established.

However, the telescopic system is not Boolean, whereas the main interest in the proof theory is just in the Boolean systems. In (Grigoriev 2001) a linear lower bound on the degree of P C_{>} refutations is established for the Tseitin’s tautologies and for the parity principle, the proofs extend the argument from Buss et al. (1999, 2001) and similar lower bounds for PC.

In the present paper as in (Impagliazzo et al. 1999) we consider the following system which is a particular case of the knapsack problem

f_{i} = X_{i}^{2} − X_{i} = 0, 1 ≤ i ≤ n, f = X_{1} + ⋯ + X_{n} − r = 0 (0.7)

We note that throughout the paper r ∈ R denotes a real number.

The P S_{>} (see Definition 0.5) and P C_{>} (see Definition 0.6) degrees of (0.7) depend essentially on the value of r. If either r < 0 or r > n then the following obvious identities

−f_{1} − ⋯ − f_{n} − f + X_{1}^{2} + ⋯ + X_{n}^{2} = r

and respectively,

−f_{1} − ⋯ − f_{n} + f + (X_{1} − 1)^{2} + ⋯ + (X_{n} − 1)^{2} = n − r

show that both P S_{>} and P C_{>} degrees of (0.7) are 2. On the other hand, theorem 5.1 of Impagliazzo et al. (1999) establishes a lower bound of ⌈n/2⌉ + 1 on the PC degree of (0.7) regardless of the value of r. Thus, P C_{>} can be strictly stronger than PC and P S_{>} can be strictly stronger than PS. The main result of the present paper is the following lower bound on the P S_{>} and P C_{>} degrees of (0.7).

Theorem. Let k be a non-negative integer and suppose that k < r < n − k.

(i) When 0 ≤ k ≤ (n − 3)/2 the Positivstellensatz refutation degree of (0.7) is greater or equal to 2k + 4. For k ≥ (n − 2)/2 the degree is greater or equal to n + 1;

(ii) when 0 ≤ k ≤ ⌈n/4⌉ − 2 the Positivstellensatz calculus refutation degree of (0.7) is greater or equal to 2k + 4. For k > ⌈n/4⌉ − 2 the degree is greater or equal to ⌈n/2⌉ + 1.

Remark 0.8. Actually one could rephrase the theorem invoking the following stairs-form function δ which equals to 2 outside the interval (0, n) and which equals to 2k + 4 on the intervals (k, k + 1) and (n − k − 1, n − k) for all integers 0 ≤ k < n/2. Then the bound in a) on the degree is min{δ, n + 1} and the bound in b) is min{δ, ⌈n/2⌉ + 1}. The values of the function δ at the integer points 0, …, n does not matter since system (0.7) has a solution at precisely these values of r. Observe also that both degrees in the theorem as functions in m are symmetric with respect to the point n/2, taking into account the transformation X_{i} → 1 − X_{i}, 1 ≤ i ≤ n.

In section 1 we show how to reduce the proof of the theorem to the nonnegativity of a relevant quadratic form which in its turn is proved in section 2.

In the theorem we establish lower bounds on the degrees of P S_{>} and P C_{>} refutations. It would be interesting to learn how close are they to upper bounds (we know this for r < 0 or r > n due to the identities above and also when k ≥ (n − 2)/2 in case (i) and when k > ⌈n/4⌉ − 2 in case (ii)).

1. Reduction to the non-negativity of a quadratic form

As in Impagliazzo et al. (1999) we consider a factor-algebra

A = R[X_{1}, …, X_{n}]/(X_{1}^{2} − X_{1}, …, X_{n}^{2} − X_{n})

which has a canonical basis of the multilinear monomials {X^{I}} where I ⊂ \{1, … n\}. For a polynomial g ∈ R[X_{1}, …, X_{n}] denote by \overline{g} ∈ A the multilinear polynomial that is the canonical image of g in A.

Lemma 5.2 of Impagliazzo et al. (1999) states that deg(\overline{fg}) = deg(\overline{g}) + 1, provided that deg(\overline{g}) < ⌈n/2⌉. This implies (theorem 5.1 of Impagliazzo et al. (1999)) the lower bound ⌈n/2⌉ on the degree of PC refutations of (0.7). This bound is sharp (theorem 4.2 Impagliazzo et al. (1999)). Moreover, it is claimed in the proof of theorem 5.1 of Impagliazzo et al. (1999) that if a polynomial h is deducible in PC from (0.7) with a degree of the refutation at most ⌈n/2⌉ then h = f_{1}g_{1} + ⋯ + f_{n}g_{n} + fg for suitable g_{1}, …, g_{n}, g such that \overline{g} = g, deg(\overline{h}) = deg(g) + 1 and deg(f_{i}g_{i}) ≤ deg(h), 1 ≤ i ≤ n (this claim is verified in Impagliazzo et al. (1999) by induction along a deduction of h in PC relying on lemma 5.2 of Impagliazzo et al. (1999)). For a weaker system of NS one can prove a better (also sharp) lower bound (which holds, in fact, over any field of characteristic either zero or greater than n).

Proposition 1.1. The Nullstellensatz degree of (0.7) equals to n + 1.

Proof. The upper bound n+1 on the degree was established in Beame et al. (1996). Indeed, there is a polynomial g such that \overline{g} = g and \overline{fg} = 1. Then the polynomial fg − 1 belongs to the ideal generated by f_{1}, …, f_{n}. Now we proceed to the lower bound.

Denote by S = \frac{1}{n!} ∑_{σ∈S_{n}} σ the operator of symmetrization. Fix an NS refutation 1 = f_{1}g_{1} + ⋯ f_{n}g_{n} + fg, one can assume without loss of generality that g = \overline{g} and so deg(\overline{fg}) = deg(g) + 1, provided that deg(g) < n. After applying S to the NS refutation one could assume that S(g) = g, indeed, S(g) is a linear combination of elementary symmetric functions s_{0} = 1, s_{1} = X_{1}+⋯+X_{n}, …, s_{n} = X_{1} ⋯ X_{n}, assuming that k = deg(g) < n, for the highest terms in the product \overline{fg} we have \overline{s_{1}s_{k}} = (k + 1)s_{k+1} + ks_{k} since f = s_{1} − r. □

Now we proceed to the proof of the theorem. Suppose that there is a P S_{>} refutation of (0.7) in case (i) and a P C_{>} refutation of (0.7) in case (ii), respectively, of degree d being less than a respective bound in the theorem. Note that d ≤ n in case (i) and d ≤ ⌈n/2⌉ in case (ii) (see also the Remark 0.8 after the theorem). Definitions Definition 0.5, Definition 0.6, respectively, imply that for appropriate polynomials h_{j} we have an equality

1 + ∑_{j} h_{j}^{2} = f_{1}g_{1} + ⋯ + f_{n}g_{n} + fg (1.2)

where deg(f_{i}g_{i}), deg(fg) ≤ d, 1 ≤ i ≤ n in case (i), and in case (ii) the right-hand side is deducible in the PC within the degree d. Observe that deg(h_{j}^{2}) ≤ deg(f_{1}g_{1} + ⋯ + f_{n}g_{n} + fg) ≤ d. Indeed, consider among all the monomials occurring in all h_{j} the highest one with respect to the deglex monomial ordering, then the coefficient of the square of this monomial in the sum 1 + ∑_{j} h_{j}^{2} should be positive. In case (ii) the (already mentioned at the beginning of the section) claim in the proof of theorem 5.1 of Impagliazzo et al. (1999) states that deg(fg), deg(f_{i}g_{i}) ≤ d, 1 ≤ i ≤ n for g, g_{1}, …, g_{n} chosen in a suitable way.

Define a linear mapping B : A → R by letting B(X^{I}) = B_{k} = \frac{r(r−1)···(r−k+1)}{n(n−1)···(n−k+1)} for the basis elements X^{I} of A corresponding to any set I with |I| = k and extending linearly. Further, extend B to all of R[X_{1}, …, X_{n}] by defining B(g) = B(\overline{g}). Observe that the mapping B is symmetric and that B(1) = B_{0} = 1.

Lemma 1.3. For a polynomial g_{0} ∈ R[X_{1}, …, X_{n}] with deg(g_{0}) < n we have B(fg_{0}) = 0.

Proof. It suffices for a multilinear monomial X^{I} with |I| = k < n to verify that B(fX^{I}) = 0, which is valid since B(fX^{I}) = (n − k)B_{k+1} + (k − r)B_{k}. □

Denote by P_{k} ⊂ A, 0 ≤ k ≤ n the linear hull of all the monomials X^{I} of degree |I| = k. Then A = ⊕_{0≤k≤n}P_{k}.

We introduce a quadratic form Q in the space ⊕_{0≤k≤⌊n/2⌋}P_{k} with the entry in the place (X^{I}, X^{J}) being equal to B(X^{I}X^{J}). By Q_{l}, l ≤ ⌊n/2⌋ we denote the restriction of Q onto the subspace ⊕_{0≤k≤l}P_{k}, in particular, Q_{⌊n/2⌋} = Q. In the sequel we often identify a quadratic form with the symmetric matrix of its coefficients and we identify a polynomial with the vector of its coefficients.

Lemma 1.4. The quadratic form Q_{l} is non-negative when l−1 < r < n−l+1.

The proof of the Lemma 1.4 is contained in the next section, and now we show how to deduce the theorem from the Lemma 1.4.

End of the proof of the theorem. We apply the mapping B to both sides of (1.2). In the right-hand side we obtain B(fg) = 0 due to Lemma 1.3 because deg(fg) ≤ d ≤ n in both cases (i), (ii). On the other hand let h_{j} = ∑_{I} h_{j}^{(I)}X^{I}, then B(h_{j}^{2}) = ∑_{I,J} h_{j}^{(I)}h_{j}^{(J)}B(X^{I}X^{J}) = h_{j}Q_{⌊d/2⌋}h_{j}^{T} ≥ 0 according to Lemma 1.4, taking into the account that deg(h_{j}^{2}) ≤ d (see above) and that in case (i) when 0 ≤ k ≤ (n − 3)/2 or in case (ii) when 0 ≤ k ≤ ⌈n/4⌉ − 2 we have ⌊d/2⌋ ≤ k + 1 by the adopted supposition that the theorem is wrong, and in case (i) when k ≥ (n − 2)/2 we have k + 1 ≥ n/2 ≥ d/2, and finally in case (ii) when k > ⌈n/4⌉ − 2 we have k + 1 ≥ ⌊\frac{⌈n/2⌉}{2}⌋ ≥ ⌊d/2⌋ (here h_{j}^{T} denotes the transposed vector of coefficients of h_{j}). Since B(1) = 1 we get a contradiction. □

Note that one can obtain another proof of the Proposition 1.1 just applying the mapping B to any NS refutation and making use of Lemma 1.3.

2. Non-negativity of the quadratic form Q

Now we proceed to the proof of Lemma 1.4. The plan is to describe the kernel of Q_{l} and its eigenspaces, and to prove that non-zero eigenvalues are positive.

First observe that the vector fX^{I}, |I| ≤ l − 1 belongs to the kernel ker Q_{l}. Indeed, the product of the row of the matrix Q_{l} which corresponds to a monomial X^{J} by the vector fX^{I}, equals to B(fX^{I}X^{J}) = B(fX^{I∪J}) which vanishes since |J| ≤ l, hence |I ∪J| ≤ 2l −1 ≤ n−1 and we apply Lemma 1.3. Actually, we’ll show in the sequel that ker Q_{l} is the linear hull of these vectors.

In the sequel for a vector v ∈ P_{k} we utilize a notation v = (v_{I}) where v_{I} is I-component of v, i.e. the coefficient of X^{I} in v. Consider a linear mapping C_{k} : P_{k} → P_{k+1} where for a vector v = (v_{I}) ∈ P_{k} its image (C_{k}(v))_{J} = ∑_{I⊂J} v_{I}, here and below I, J ⊂ {1, …, n}; |J| = k + 1, |I| = k. Also consider a linear mapping D_{k} : P_{k+1} → P_{k} under which the image of a vector w = (w_{J}) ∈ P_{k+1} is a vector whose I-component equals to (D_{k}(w))_{I} = ∑_{J⊃I} w_{J}.

Denote by P_{k+1}^{(0)} ⊂ P_{k+1} a subspace {(u_{J}) : ∀|I| = k (∑_{J⊃I} u_{J} = 0)}. For t > k denote a subspace P_{k+1}^{(t−k)} = C_{t} · C_{t−1} ⋯ C_{k+1}(P_{k+1}^{(0)}) ⊂ P_{t+1} and besides, for any vector w = (w_{J}) ∈ P_{k+1} and any L ⊂ {1, …, n}; |L| = t + 1 we have

((C_{t} · C_{t−1} ⋯ C_{k+1})(w))_{L} = (t − k)!(∑_{J⊂L} w_{J}) (2.1)

For a vector u ∈ P_{k+1}^{(0)} one can represent (in algebra A defined in section 1 above) the polynomial

\overline{s_{1}^{t} ∑_{J} u_{J}X^{J}} = ∑_{|K|=k+t+1}(C_{k+t} ⋯ C_{k+1}(u))_{K}X^{K} + (2.2)

η_{k,t}^{(k+t)} ∑_{|K|=k+t}(∑_{J⊂K} u_{J})X^{K} + ⋯ + η_{k,t}^{(k+1)} ∑_{|K|=k+1} u_{K}X^{K}

for appropriate constants η_{k,t}^{(p)}, by means of opening the parenthesis in s_{1}^{t} and taking into the account (2.1), provided that k + t + 1 ≤ n (in fact, this equality holds for any vector w ∈ P_{k+1}). The vectors of coefficients of the polynomials \overline{s_{1} − r}, \overline{s_{1}(s_{1} − r)}, \overline{s_{1}^{2}(s_{1} − r)}, …, \overline{s_{1}^{l−1}(s_{1} − r)} (of the degrees 1, 2, …, l, respectively) belong to the ker Q_{l} (see the beginning of the present section), the same holds for the polynomials (or more precisely, the elements of A)

\overline{(s_{1} − r) ∑_{J} u_{J}X^{J}}, \overline{s_{1}(s_{1} − r) ∑_{J} u_{J}X^{J}}, (2.3)

\overline{s_{1}^{2}(s_{1} − r) ∑_{J} u_{J}X^{J}}, …, \overline{s_{1}^{l−k−2}(s_{1} − r) ∑_{J} u_{J}X^{J}}

Thus, using (2.2) we summarize the properties of the polynomials (2.3) in the following proposition.

Proposition 2.4. The vectors of coefficients of polynomials (2.3) belong to the kernel ker Q_{l} and the leading homogeneous forms of (2.3) are

C_{k+1}(u), C_{k+2} · C_{k+1}(u), …, C_{l−1} ⋯ C_{k+2} · C_{k+1}(u)

of the degrees k + 2, k + 3, …, l, respectively. The polynomials (2.3) lie in (l − k)-dimensional subspace P (u) with the basis

u^{(k+1)} = (u), u^{(k+2)} = C_{k+1}(u), u^{(k+3)} = \frac{1}{2!}C_{k+2} · C_{k+1}(u), …, (2.5)

u^{(l)} = \frac{1}{(l − k − 1)!}C_{l−1} ⋯ C_{k+2} · C_{k+1}(u) ∈ P_{k+1} ⊕ P_{k+2} ⊕ ⋯ ⊕ P_{l}

Due to (2.1) for |K| = t the coordinate of the vector (u^{(t)})_{K} = ∑_{J⊂K} u_{J}. For a subset T′ ⊆ {1, …, n}, |T′| ≤ k we have (recall that |J| = k + 1)

10 D.Grigoriev

∑_{J⊃T′} u_{J} = 0 (2.6)

because up to a constant (positive) factor it equals to ∑_{I⊇T′,|I|=k} ∑_{J⊃I} u_{J} = 0.

For fixed subsets K ⊆ {1, …, n}, |K| = i and T ⊆ K, |T | ≤ k + 1 we prove the following identity:

∑_{J∩K=T} u_{J} = (−1)^{k+1−|T |} ∑_{T ⊆J⊆K} u_{J} (2.7)

The proof goes by induction on k + 1 − |T |. The base when i ≥ k + 1 for |T | = k + 1 is trivial since both sides of (2.7) in this case equal to u_{T}. Respectively, when i ≤ k we put for the base T = K , then the both sides of (2.7) in this case vanish due to (2.6). For the inductive step from (2.6) we get

0 = ∑_{J⊃T} u_{J} = ∑_{J∩K=T} u_{J} +

∑_{J⊃T,|J∩K|=|T |+1} u_{J} + ∑_{J⊃T,|J∩K|=|T |+2} u_{J} + ⋯ + ∑_{J⊃T,|J∩K|=k+1} u_{J} =

(in case when i ≤ k all the sums in the latter line vanish by the inductive hypothesis, hence the sum ∑_{J∩K=T} u_{J} = 0 vanishes as well, which proves the inductive step, thus we continue the chain of equalities assumming that i ≥ k + 1)

= ∑_{J∩K=T} u_{J} + ∑_{H⊃T,|H|=|T |+1}(−1)^{k+1−(|T |+1)} ∑_{H⊆J⊆K} u_{J} +

∑_{H⊃T,|H|=|T |+2}(−1)^{k+1−(|T |+2)} ∑_{H⊆J⊆K} u_{J} + ⋯ + ∑_{H⊃T,|H|=k+1} u_{H} =

due to the inductive hypothesis (where in the double sums the external summation ranges over H while the internal one ranges over J); in its turn continuing the chain of equalities we get

= ∑_{J∩K=T} u_{J} + ∑_{T ⊆J⊆K}(1 − \binom{k + 1 − |T |}{1} + \binom{k + 1 − |T |}{2} − ⋯ +

(−1)^{k−|T |}\binom{k + 1 − |T |}{k − |T |})u_{J} = ∑_{J∩K=T} u_{J} − (−1)^{k+1−|T |} ∑_{T ⊆J⊆K} u_{J}

that proves (2.7).

Next we prove the following proposition.

Proposition 2.8. The composition of the operators D_{t} · C_{t} restricted on the subspace C_{t−1} ⋯ C_{k+1}(P_{k+1}^{(0)}) equals to a multiple (n − t − k − 1)(t − k)E of the identity operator E, provided that n − t − k − 1 > 0.

Proof of the proposition. Let M ⊆ {1, …, n}; |M| = t and u ∈ P_{k+1}^{(0)}, we obtain the following chain of inequalities

\frac{1}{(t − k)!}(D_{t}C_{t} ⋯ C_{k+1}(u))_{M} = ∑_{L⊃M,|L|=t+1} ∑_{J⊆L} u_{J} =

(due to (2.1))

= (n − t) ∑_{J⊆M} u_{J} + ∑_{|J∩M|=k} u_{J} = (n − t) ∑_{J⊆M} u_{J} − ∑_{I⊂M,|I|=k} ∑_{I⊂J⊆M} u_{J} =

(see (2.7))

= (n − t) ∑_{J⊆M} u_{J} − (k + 1) ∑_{J⊆M} u_{J} = (n − t − k − 1) ∑_{J⊆M} u_{J} =

\frac{n − t − k − 1}{(t − k − 1)!}(C_{t−1} ⋯ C_{k+1}(u))_{M}

(again due to (2.1)). This proves Proposition 2.8. □

We prove by induction on t that P_{t} is the direct sum of its subspaces

P_{t}^{(0)} ⊕ C_{t−1}P_{t−1}^{(0)} ⊕ C_{t−1} · C_{t−2}P_{t−2}^{(0)} ⊕ ⋯ ⊕ C_{t−1} · C_{t−2} ⋯ C_{0}P_{0}^{(0)} (2.9)

The base case for t = 0 is obvious. Assuming (2.9) as the inductive hypothesis, we obtain that the image under the operator C_{t} of (2.9) is also a direct sum (due to Proposition 2.8 applied to each item of the direct sum (2.9), observe that n − 2t − 1 > 0 since t < l ≤ ⌊n/2⌋):

C_{t}P_{t} = C_{t}P_{t}^{(0)}⊕C_{t}·C_{t−1}P_{t−1}^{(0)}⊕C_{t}·C_{t−1}·C_{t−2}P_{t−2}^{(0)}⊕⋯⊕C_{t}·C_{t−1} ⋯ C_{0}P_{0}^{(0)} ⊂ P_{t+1}

and D_{t} · C_{t}P_{t} = P_{t}, moreover D_{t} · C_{t} is an automorphism of P_{t}. Apart from that, the kernel ker D_{t} = P_{t+1}^{(0)}. Therefore, P_{t+1} = P_{t+1}^{(0)} ⊕ C_{t}P_{t} that proves the inductive hypothesis and (2.9).

Partition the matrix Q_{l} into the blocks Q^{(i,j)} : P_{j} → P_{i}, 0 ≤ i, j ≤ l. Our next purpose is to calculate the vector Q^{(i,k+1)}(u) ∈ P_{i}, recall that u ∈ P_{k+1}^{(0)}, |J| = k + 1. Let |K| = i, we have using the definition of the mapping B from section 1

(Q^{(i,k+1)}(u))_{K} = ∑_{T,T ⊆K} ∑_{J,K∩J=T} B(X^{K}X^{J})u_{J} = ∑_{T ⊆K} B_{i+k+1−|T |} ∑_{K∩J=T} u_{J}

The latter sum vanishes when i ≤ k since ∑_{K∩J=T} u_{J} = 0 due to (2.7). Now when i ≥ k + 1 we obtain using (2.7)

(Q^{(i,k+1)}(u))_{K} (2.10)

= B_{i} ∑_{J⊆K} u_{J} + B_{i+1} ∑_{|J∩K|=k} u_{J}

+B_{i+2} ∑_{|J∩K|=k−1} u_{J} + ⋯ + B_{i+k+1} ∑_{|J∩K|=0} u_{J}

= B_{i} ∑_{J⊆K} u_{J} − B_{i+1}\binom{k + 1}{k} ∑_{J⊆K} u_{J} + B_{i+2}\binom{k + 1}{k − 1} ∑_{J⊆K} u_{J} − ⋯

+(−1)^{k+1}B_{i+k+1}\binom{k + 1}{0} ∑_{J⊆K} u_{J}

= (B_{i} − B_{i+1}\binom{k + 1}{k} + B_{i+2}\binom{k + 1}{k − 1} − ⋯

+(−1)^{k+1}B_{i+k+1}\binom{k + 1}{0}) ∑_{J⊆K} u_{J}

Thus, (Q^{(i,k+1)}(u)) = μ_{i,k+1}u^{(i)} (see (2.5)) where

μ_{i,k+1} = ∑_{i≤j≤i+k+1}(−1)^{j−i}\binom{k + 1}{j − i}B_{j}, l ≥ i ≥ k + 1 (2.11)

(we recall that k + 1 is fixed for the time being). In particular, for i = k + 1 the vector u^{(k+1)} = u is an eigenvector of the operator Q^{(k+1,k+1)}.

Because

0 = (Q^{(i,k+1)} Q^{(i,k+2)}) · \overline{(s_{1} − r) ∑_{J} u_{J}X^{J}}

for all i ≤ l, taking into the account Proposition 2.4, we get that Q^{(i,k+2)} · u^{(k+2)} = μ_{i,k+2}u^{(i)} for appropriate constant μ_{i,k+2} when i ≥ k + 1 and Q^{(i,k+2)} · u^{(k+2)} = 0 when i ≤ k. In a similar way,

0 = (Q^{(i,k+1)} Q^{(i,k+2)} Q^{(i,k+3)}) · \overline{s_{1}(s_{1} − r) ∑_{J} u_{J}X^{J}},

this implies that Q^{(i,k+3)} · u^{(k+3)} = μ_{i,k+3}u^{(i)} for appropriate constants μ_{i,k+3} when i ≥ k+1 and Q^{(i,k+3)}·u^{(k+3)} = 0 when i ≤ k and so on. Thus, the operator Q_{l} acts on the subspace P (u) (see (2.5)), in other words P (u) is invariant under Q_{l}, and (μ_{i,j}) is the matrix of its action with respect to the basis (2.5) if in addition we set μ_{i,j} = 0 when j < k + 1. Since the polynomials (2.3) belong to ker Q_{l} due to Proposition 2.4, the rank of (μ_{i,j}) is at most 1. We have already calculated the first (possibly) non-zero column of the matrix (μ_{i,j}), 0 ≤ i, j ≤ l (the index of this column is k + 1).

Our next purpose is to calculate the first (possibly) non-zero row of this matrix (its index is also k + 1 as was just proved).

So, we need to calculate the coordinate of the vector (Q^{(k+1,i)}u^{(i)})_{J_{0}} for a fixed |J_{0}| = k + 1. This coordinate equals to

∑_{i≤j≤i+k+1} B_{j} ∑_{|K∩J_{0}|=k+1−j+i} ∑_{J⊆K} u_{J} (2.12)

where the second summation ranges over K and the third (internal) one ranges over J.

Now we transform one item of the sum (2.12):

∑_{|K∩J_{0}|=k+1−j+i} ∑_{J⊆K} u_{J} =

∑_{0≤t≤k+1−j+i} \binom{k + 1 − t}{k + 1 − t − j + i}\binom{n − 2k − 2 + t}{j − 2k − 2 + t}( ∑_{|J∩J_{0}|=t} u_{J}) (2.13)

where the first binomial coefficient \binom{k+1−t}{k+1−t−j+i} counts the number of possibilities (for fixed J, J_{0}) to choose a subset (J_{0} − J) ∩ K in the set J_{0} − J (note that |J_{0} − J| = k + 1 − t, |(J_{0} − J) ∩ K| = k + 1 − t − j + i); while the second binomial coefficient \binom{n−2k−2+t}{j−2k−2+t} counts the number of possibilities to choose a subset K − J − J_{0} in the set {1, …, n} − J − J_{0} (note that |K − J − J_{0}| = j − 2k − 2 + t, |{1, …, n} − J − J_{0}| = n − 2k − 2 + t). Thereby, the product of these two binomial coefficients provides the numbers of possibilities for K from the left-hand side.

Because of (2.7) we obtain that ∑_{|J∩J_{0}|=t} u_{J} = (−1)^{k+1−t}\binom{k+1}{t}u_{J_{0}}. Therefore, (2.13) equals to

( ∑_{0≤t≤k+1−j+i}(−1)^{k+1−t}\binom{k + 1}{t}\binom{k + 1 − t}{k + 1 − t − j + i}\binom{n − 2k − 2 + t}{n − j})u_{J_{0}} =

( ∑_{0≤t≤k+1−j+i}(−1)^{k+1−t} \frac{(k + 1)!}{t!(k + 1 − t − j + i)!(j − i)!}\binom{n − 2k − 2 + t}{n − j})u_{J_{0}} =

\binom{k + 1}{j − i}( ∑_{0≤t≤k+1−j+i}(−1)^{k+1−t}\binom{k + 1 − j + i}{t}\binom{n − 2k − 2 + t}{n − j})u_{J_{0}} =

(−1)^{j−i}\binom{k + 1}{j − i}\binom{n − 2k − 2}{i − k − 1}u_{J_{0}}

. To prove the latter equality denote by Ξ, Υ some sets of the cardinalities k + 1 − j + i, n − 2k − 2, respectively. Observe that the sum in the second-to-last line in the chain of the equalities

∑_{0≤t≤k+1−j+i}(−1)^{k+1−t}\binom{k + 1 − j + i}{t}\binom{n − 2k − 2 + t}{n − j}

coincides with the weighted sum of the number of choices of first, a subset Λ of Ξ of the cardinality t and subsequently a subset Δ of the cardinality n − j of the union Λ ∪ Υ, taken with the weight (−1)^{k+1−t}. On the other hand, if Δ does not contain Ξ the contribution of Δ into the weighted sum vanishes since this contribution equals the weighted sum of occurances of Λ, i.e.

∑_{Ξ∩Δ⊆Λ⊆Ξ}(−1)^{k+1−|Λ|} = ∑_{0≤τ≤τ_{0}}(−1)^{τ} \binom{τ_{0}}{τ}

where τ_{0} = |Ξ − Δ|. Else when Δ contains Ξ, the contribution (for the unique Λ = Ξ) equals (−1)^{j−i}. In order to finish this proof notice that the number of such Δ equals the number of subsets Δ∩Υ of the cardinality (n−j)−(k+1−j+i) of the set Υ, i.e. \binom{n−2k−2}{n−k−i−1}.

Thus, (2.12) equals to

\binom{n − 2k − 2}{i − k − 1}( ∑_{i≤j≤i+k+1}(−1)^{j−i}\binom{k + 1}{j − i}B_{j})u_{J_{0}},

hence

μ_{k+1,i} (2.14)

= \binom{n − 2k − 2}{i − k − 1}( ∑_{i≤j≤i+k+1}(−1)^{j−i}\binom{k + 1}{j − i}B_{j}) = \binom{n − 2k − 2}{i − k − 1}μ_{i,k+1}

Therefore, the matrix (μ_{i,j}) (being of the rank at most 1) is non-negative if and only if its entry μ_{k+1,k+1} > 0, provided that μ_{k+1,k+1} ≠ 0. Indeed, each diagonal entry μ_{i,i} of the matrix (μ_{i,j}) is non-negative (respectively, each one is non-positive) if and only if μ_{k+1,k+1} > 0 (respectively, μ_{k+1,k+1} < 0) since due to (2.14) the signs of μ_{k+1,i} and μ_{i,k+1} coincide and taking into account that μ_{i,i}μ_{k+1,k+1} = μ_{i,k+1}μ_{k+1,i}; furthermore, the only non-zero eigenvalue of the rank 1 matrix (μ_{i,j}) equals to its trace, the latter is thereby positive if and only if μ_{k+1,k+1} > 0.

Suppose that we have proved already that the matrices (μ_{i,j}) (let us underline that the matrix (μ_{i,j}) was defined for a fixed k + 1) are non-negative for all 0 ≤ k + 1 ≤ l. This would imply that the matrix Q_{l} is non-negative as well since (μ_{i,j}) is the action of Q_{l} on the subspace P (u) (see above), hence the unique non-zero eigenvalue of the matrix (μ_{i,j}) is the eigenvalue of Q_{l} as well, actually, this eigenvalue depends only on k + 1 and does not depend on a particular vector u ∈ P_{k+1}^{(0)}. Moreover, these eigenvalues for all 0 ≤ k + 1 ≤ l exhaust all the eigenvalues of Q_{l}. Indeed, the subspace

P_{k+1}^{(0)} ⊕ C_{k+1}P_{k+1}^{(0)} ⊕ C_{k+2}C_{k+1}P_{k+1}^{(0)} ⊕ ⋯ ⊕ C_{l−1} ⋯ C_{k+1}P_{k+1}^{(0)} (2.15)

equals the direct sum of subspaces of the form P (u) where u ranges over the elements of an arbitrary basis of the subspace P_{k+1}^{(0)}, and on the other hand, the direct sum of all these subspaces of the form (2.15) for 0 ≤ k + 1 ≤ l coincides with the whole space P_{0} ⊕ ⋯ ⊕ P_{l} due to (2.9). Thus, Q_{l} is non-negative.

So, to complete the proof of Lemma 1.4 it remains to verify that μ_{k+1,k+1} > 0 for all 0 ≤ k + 1 ≤ l.

Denote B_{i}^{(k+1)} = μ_{i,k+1}, l ≥ i ≥ k + 1 where μ_{i,k+1} is taken from (2.11). We prove by induction on k that

B_{i}^{(k+1)} = \frac{(∏_{1≤j≤i}(r + 1 − j))(∏_{0≤t≤k}(n − r + t))}{n(n − 1) ⋯ (n − i − k)} (2.16)

For the base of induction k = −1 we have B_{i}^{(0)} = B_{i} (see section 1).

For the inductive step we observe that B_{i}^{(k+1)} = B_{i}^{(k)} − B_{i+1}^{(k)} and apply the inductive hypothesis, that proves (2.16).

Finally, the diagonal entry μ_{k+1,k+1} = B_{k+1}^{(k+1)} is positive for k < r < n − k because of (2.16), that proves Lemma 1.4 since k + 1 ≤ l. □

Acknowledgements

The author would like to take this opportunity to thank anonymous referees whose remarks have conduced to improve the exposition.

References

P. Beame, R. Impagliazzo, J. Krajíček, T. Pitassi & P. Pudlák (1996). Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. Proc. London Math. Soc. 73, 1–26.

J. Bochnak, M. Coste & M.-F.Roy (1998). Real algebraic geometry. Springer-Verlag.

S. Buss, D. Grigoriev, R. Impagliazzo & T. Pitassi (1999). Linear gaps between degrees for polynomial calculus modulo distinct primes. In 31st Ann. ACM Symp. on Theory of Computing, 547–556.

S. Buss, D. Grigoriev, R. Impagliazzo & T. Pitassi (2001). Linear gaps between degrees for polynomial calculus modulo distinct primes. J. Comput. Syst. Sci. 62, 267–289.

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

M. Clegg, J. Edmonds & R. Impagliazzo (1996). Using the Groebner basis algorithm to find proofs of unsatisfiability. In 28th Ann. ACM Symp. on Theory of Computing,, 174–183.

D. Grigoriev (1998). Nullstellensatz lower bounds for Tseitin tautologies. In 39th Ann. IEEE Symp. on Foundations of Computer Science, 648–652.

D. Grigoriev (2001). Linear Lower Bound on Degrees of Positivstellensatz Calculus Proofs for the Parity. Theor. Comput. Sci 259, 613–622.

D. Grigoriev & N. Vorobjov (2001). Complexity of Null- and Positivstellensatz proofs. Ann. Pure Appl. Logic .

Impagliazzo, P. Pudlák & J. Sgall (1999). Lower bounds for polynomial calculus and the Groebner basis algorithm. Computational Complexity 8, 127–144.

L. Lovász (1994). Stable sets and polynomials. Discrete Mathematics 124, 137–153.

L. Lovász & A. Schrijver (1991). Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optimization 1, 166–190.

P. Pudlák (1999). On the complexity of the propositional calculus. In Proceedings of Logic Colloquium ’97, 197–218. Cambridge Univ.Press.

A. Razborov (1998). Lower bounds for the polynomial calculus. Computational Complexity 7, 291–324.

G. Stengle (1974). A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Math. Ann. 207, 87–97.

T. Stephen & L. Tunçel (1999). On representation of the matching polytope via semidefinite liftings. Mathematics of Operations Research 24, 1–7.

Manuscript received

D.Grigoriev IRM Université de Rennes-1 Campus de Beaulieu, 35042 Rennes France

dima@maths.univ-rennes1.fr
http://www.maths.univ-rennes1.fr