§1. Some Bounds  Lecture XIII  Page 1

Lecture XIII Bounds in Polynomial Ideals

Let G(n, d) denote the minimum degree of Gröbner bases of ideals generated by polynomials of degree at most d in the ring R = ℚ[X_{1}, …, X_{n}] of rational polynomials. This lecture proves tight upper and lower bounds on G(n, d):

G(n, d) = d^{2^{βn}},  0.2 − O(n^{−1}) < β ≤ 1.  (1)

The upper bound proof here is from Dubé [3, 4]. Similar bounds are found in Guisti [5], and Möller and Mora [9]. See also Lazard [7]. The lower bound is from Yap [11], providing a simpler and more efficient alternative to the original construction of Mayr and Meyer [8]. It turns out that there is the close connection between G(n, d) and two other important bounds I(n, d) (ideal membership bound) and S(n, d) (syzygy basis bound) in the theory of polynomial ideals. Bayer and Stillman [2]) had already observed that the construction of Mayr-Meyer leads to lower bounds on S(n, d). Huynh [6] gives other applications of these lower bound constructions.

Unless otherwise noted, R refers to the ring K[X] = K[X_{1}, …, X_{n}]. For the lower bound proofs, we further assume K = ℚ. We normally assume the standard grading of K[X], so “homogeneous polynomials” have the standard sense (see §2).

§1. Some Bounds in Polynomial Ideal Theory

Three bounds arise naturally in the constructive theory of ideals in R:

I(n, d), S(n, d), D(n, d).

We call them (respectively) the ideal membership bound, syzygy basis bound and Gröbner basis bound. They are defined as follows: let f_{1}, …, f_{m} ∈ R = ℚ[X_{1}, …, X_{n}] with (total) degree deg f_{i} ≤ d. Then the ideal membership degree bound I(n, d) is the least value such that for all such f_{i}’s whenever f_{0} ∈ Ideal(f_{1}, …, f_{m}) then

f_{0} = ∑_{i=1}^{m} a_{i}f_{i}, a_{i} ∈ R, deg(a_{i}f_{i}) ≤ I(n, d) + deg(f_{0}).

The syzygy basis bound S(n, d) is the least value such that for all such f_{i}’s there exists a syzygy basis for the module of syzygies of (f_{1}, …, f_{m}), where each syzygy in the basis has degree at most S(n, d). The degree of a syzygy [h_{1}, …, h_{m}] is the maximum degree of the h_{i}’s. Finally, the Gröbner basis bound D(n, d) is the least value such that for all such f_{i}’s and any admissible ordering ≤_{A}, there is a

Gröbner basis with respect to ≤_{A} whose members are polynomials of degree at most D(n, d).

All the three bounds are closely related, and are essentially double exponential [11]. For instance, D(n, d) ≥ S(n, d). Lazard (1982,1991 [7]) has shown

S(n, d) ≤ d^{2^{βn}},
I(n, d) ≤ d^{2^{βn+O(log n)}},

§2. The Hilbert-Serre Theorem  Lecture XIII  Page 2

where β = log_{4} 3 < 0.79. Lazard indicated a similar upper bound for G(n, d), superceding the upper bound shown in this lecture. Nevertheless, the proof presented to be presented have independent interest. These bounds are all tight up to constant factors in the second exponent. Yap [11] shows that I(n, d), D(n, d) and S(n, d) are each lower-bounded by the function

d^{2^{βn}}, β ∼ 0.5.  (2)

The notation “β ∼ 0.5” means that the right-hand side has an implicit dependence on n and β approaches 0.5 as n → ∞. The lower bound was originally^{1} shown by Mayr-Meyer [8] with β ∼ 0.1 In this lecture, we give a simple construction to achieve β ∼ 0.2. This construction can be sharpened to the cited result.

Remarks.

1. Essentially all known double exponential lower bounds proofs in polynomial ideal theory use variants of the construction in the proof of (2). The construction allows us to simulate an exponential space Turing machine, and leads to this conclusion: any Turing machine for deciding the ideal membership problem must use space c^{n} for some c > 0 for infinitely many n. The reason is that such systems can simulate counter-machines with double-exponentially large counters, and this corresponds exactly to single-exponential space-bounded Turing machines. See [8] for details.

2. A double-exponential degree bound immediately leads to a double-exponential complexity bound on ideal membershop problem: to test if f_{0} belongs to the ideal generated by f_{1}, …, f_{m}, we can set up a suitable large linear system to be solved (Exercise). Similarly, this leads to a double exponential-time algorithm for computing Gröbner bases (Exercise).

Exercises

Exercise 1.1: By writing f_{0} = ∑_{i=1}^{m} a_{i}f_{i} as a linear system in the unknown coefficients of a_{i} ∈ R, show that ideal membership in ℚ[X] can be solved in double-exponential time. □

Exercise 1.2: Use the bound on G(n, d) to give a double-exponential bound on the bit-complexity of a suitable variation of Buchberger’s algorithm. HINT: let B = \binom{G(n,d)+n−1}{n−1}. Restrict the polynomials in the Gröbner basis H that is being constructed to satisfy: (1) |H| ≤ B, (2) each f ∈ H has degree at most B. Use an efficient normal form algorithm (see exercise, §XII.3). □

§2. The Hilbert-Serre Theorem

By way of proving the Hilbert-Serre theorem, we introduce the Hilbert polynomial for graded modules.

The concept of homogeneous elements can be generalized as follows. (These definitions are slightly more general than we strictly need.) Let (G, +, 0) be an Abelian semigroup (so + is associative, commutative and 0 is the identity for +). Typically, G = ℕ, G = ℤ or G = ℤ^{n}. A G-grading (or, simply grading) of a ring R is a (weak) direct sum decomposition of R,

R = ⨁_{d∈G} R_{d}

1More accurately, several authors (Bayer-Stillman, Lazard, etc) noted that the original Mayr-Meyer construction can be improved from using about 15n variables to using about 10n variables for counting up to d^{2^{n}}. This implies the stated bound.

where each R_{d} is an additive subgroup of R and R_{d}R_{e} ⊆ R_{d+e} for all d, e ∈ G. Here, the decomposition is weak because in the decomposition of an element u = ∑_{d} u_{d} ∈ R (u_{d} ∈ R_{d}) only finitely many of the u_{d}’s are non-zero. A graded ring is a ring together with a grading. A G-graded module M is an R-module with a weak direct sum decomposition, M = ⨁_{d∈G} M_{d} such that M_{d} is an additive subgroup of M and R_{d}M_{e} ⊆ M_{d+e}. Elements of M_{d} are said to be homogeneous of degree d. Note that 0 is homogeneous of every degree d. In fact, M_{d} ∩ M_{e} = {0} for all d ≠ e. If an element u ∈ M is decomposed as u = ∑_{d} u_{d}, then each non-zero u_{d} is called a homogeneous component of u. A graded submodule or homogeneous submodule N of M is a submodule N ⊆ M that is generated by homogeneous elements. Equivalently, for all u ∈ I, each homogeneous component of u is in I (cf. §XII.5). Note that all these terms (homogenous element, graded submodule, etc) for modules apply to the ring R, since we may view R as an R-module.

Example: (1) Let G = ℝ and w be a weight function on PP(X) (§XII.1). Say a polynomial f is w-homogeneous of degree d if each power product u in f has weight w(u) = d. Let R_{d} comprise all w-homogeneous polynomials of degree d. This gives rise to the w-grading of R. If w = (1, 1, …, 1) then we get the standard grading of R. In this case, elements of R_{d} is said to be homogeneous in the standard sense.

(2) Let G = ℕ^{n} and fix an admissible ordering on PP(X) (so that hterm(f) is defined for f ∈ R). Then f ∈ R_{e} iff log(hterm(f)) = e ∈ ℕ^{n} (see §XII.1 for definition of log(·)).

(3) (Matsumura) Let G = ℕ and M = R[X, Y, Z]/Ideal(f) where f = aX^{α} + bY^{β} + cZ^{γ}. Then the weight function w(\overline{X}) = βγ, w(\overline{Y}) = αγ and w(\overline{Z}) = αβ yields a grading on M.

(4) If I ⊆ R is an ideal, then gr_{I}(R) = ⨁_{n≥0} I^{n}/I^{n+1} is an ℕ-graded ring.

We introduce homomorphisms on graded modules. Given two G-graded R-modules M, M′, we say a module homomorphism

ϕ : M → M′

is homogeneous of degree d if ϕ(M_{e}) ⊆ M′_{e+d} for each e ∈ G. (By module homomorphism, we mean ϕ(u + v) = ϕ(u) + ϕ(v) and ϕ(au) = aϕ(u) where u, v ∈ M, a ∈ R.) In particular, if M = R and suppose M′ = R′ is another ring then ϕ becomes a homogeneous ring homomorphism of degree d. For instance, if R = R′ = K[X_{1}, …, X_{n}] with the standard grading, then the map ϕ defined by ϕ(u) = uX_{n} for all u ∈ M is homogeneous of degree 1. (This map will be used in the proof below.) The following is straightforward and left to an exercise.

Lemma 1 Let M = ⨁_{d∈G} M_{d} be a G-graded R-module.

(i) A homogeneous submodule N of M is a G-graded R-module with grading ⨁_{d∈G}(N ∩ M_{d}).

(ii) If N is homogeneous, the module difference M − N has grading ⨁_{d∈G}(M_{d} − N).

(iii) If ϕ : M → M′ is homogeneous, then the kernel of ϕ is a homogeneous submodule of M and the image of ϕ is a homogeneous submodule of M′.

(iv) Also, the co-kernel coKer ϕ = M′ − ϕ(M) (module difference) is a graded module.

We state the Hilbert-Serre theorem:

Theorem 2 Let R = K[X_{1}, …, X_{n}] have the standard grading, and M be a finitely generated graded module over R, M = ⨁_{d=−∞}^{+∞} M_{d}. Then M_{d} is a K-vector space of finite dimension dim_{K}(M_{d}), and there is a polynomial Φ_{M}(z) of degree ≤ n − 1 with integer coefficients and a constant d_{0} such that for all d ≥ d_{0}, Φ_{M}(d) = dim_{K}(M_{d}).

Remarks.

1. The polynomial Φ_{M}(z) is called the Hilbert polynomial of the graded module M. The smallest constant d_{0} for which the theorem holds is called the Hilbert constant of M and denoted h_{M}. This polynomial contains important geometric data as noted next. See Bayer-Stillman [1] for computations of this polynomial.

2. Let I be a homogeneous ideal of the polynomial ring R. Two main applications of this theorem are when M = I and when M = R/I. For M = I, each additive group M_{d} is the K-vector space I_{d} comprising the homogeneous polynomials in I of degree d. The degree of the Hilbert polynomial Φ_{M}(z) in this case is the dimension of the projective zero set Zero(I) ⊆ ℙ^{n−1}(K).

3. Again let M be an ideal I ⊆ R. The degree of the zero set Zero(I) is defined to be d! times the leading coefficient of Φ_{I}(z). The “degree” of a plane algebraic curve V_{1} is intuitively clear: it is the maximum number of points (multiplicity counted) obtainable by intersecting V_{1} with an arbitrary line L. In general, the degree of an algebraic set V_{d} ⊆ 𝔸^{n}(K) of dimension d ≤ n may be defined as the maximum number of points obtainable by intersecting V_{d} with an arbitrary (n−d)-dimensional hyperplane L. The precise definition here is complicated because of multiplicity; historically, there has been many erroneous definitions. The algebraic notion of degree via the Hilbert polynomial has no ambiguity although the geometric intuition is lost.

We make some preparatory remarks for the proof.

1. Every polynomial p(z) of degree ≤ d can be written in the form

p(z) = c_{0}\binom{z}{d} + c_{1}\binom{z}{d − 1} + ⋯ + c_{d−1}\binom{z}{1} + c_{d}  (3)

for suitable coefficients c_{i}. If p(z) has integer coefficients then each c_{i} is integer. This is clear for d = 0 or 1. For d > 1, we note that

z^{d} = d!\binom{z}{d} + l.o.t.

where ‘l.o.t.’ (lower order terms) refers to terms in z of degree less than d. Then, writing p(z) = a_{0}z^{d} + ⋯ + a_{d−1}z + a_{d}, we obtain at once

p(z) = a_{0}d!\binom{z}{d} + l.o.t.

So we can choose c_{0} = a_{0}d!. By induction, the polynomial in the l.o.t. of p(z) can be put in the desired form, giving the constants c_{1}, …, c_{d}. This proves that p(z) has the form in equation (3). Moreover, if p(z) has integer coefficients, then c_{0} is an integer and the l.o.t.’s of p(z) also has integer coefficients. By induction, we conclude that c_{1}, …, c_{d} are also integers.

2. If p(z) is a polynomial and p(z′) is an integer for all large enough integer z′, then p(z) has integer coefficents. The result is true for d = 0. We now apply the identity

\binom{n + 1}{d} − \binom{n}{d} = \binom{n}{d − 1}

to equation (3) to obtain

p(z + 1) − p(z) = c_{0}\binom{z}{d − 1} + c_{1}\binom{z}{d − 2} + ⋯ + c_{d−2}\binom{z}{1} + c_{d−1}.

But p(z + 1) − p(z) is a polynomial of degree less than d which evaluates to an integer for z large enough. By induction, therefore, c_{0}, …, c_{d−1} are integers. Pick z to be a large enough multiple of d! so that p(z) is integer. Then equation (3) shows that p(z) − c_{d} is an integer. We conclude that c_{d} is also integer.

3. Suppose N is a proper submodule of M. A composition series from N to M is a strictly increasing sequence of submodules of the form

N = M_{0} < ⋯ < M_{k} = M

which cannot be extended in the sense that there is no submodule M′ such that M_{i} < M′ < M_{i+1} for any i. We call k the length of this series. If N = {0}, we call it a composition series of M. By definition, composition series are finite, and some modules may have no composition series. For instance, the integers ℤ has no composition series (why?). By the Jordan theorem [13, p. 159], every composition series of M have the same length, which we define to be the length ℓ(M) of M. For instance, the module {0} has length zero. By definition, ℓ(M) = ∞ if M has no composition series. If N < M and ℓ(M) < ∞, it follows easily that

ℓ(M − N) = ℓ(M) − ℓ(N).

[Just as modules are generalizations of vector spaces, so dimension of vector spaces becomes length of modules.]

4. Let

0 ⟶^{f_{0}} E_{1} ⟶^{f_{1}} E_{2} ⟶^{f_{2}} ⋯ ⟶^{f_{n−1}} E_{n} ⟶^{f_{n}} 0

be an exact sequence of R-modules where each E_{i} has length ℓ(E_{i}). Then the alternating sum

ℓ(E_{1}) − ℓ(E_{2}) + ⋯ (−1)^{n−1}ℓ(E_{n})  (4)

is equal to zero. Note that Ker f_{i+1} = Imf_{i} because the sequence is exact at E_{i+1}. But Imf_{i} is isomorphic to E_{i}/Ker f_{i}, so ℓ(Imf_{i}) = ℓ(E_{i}) − ℓ(Ker f_{i}). Therefore

ℓ(E_{i}) = ℓ(Ker f_{i}) + ℓ(Ker f_{i+1}).

The desired sum (4) becomes

ℓ(Ker f_{1}) + ℓ(Ker f_{2}) − ℓ(Ker f_{2}) − ℓ(Ker f_{3}) + ⋯ + (−1)^{n−2}ℓ(Ker f_{n}) + (−1)^{n−1}ℓ(E_{n}).  (5)

The non-extreme terms of this sum cancels, so it is equal to ℓ(Ker f_{1}) + (−1)^{n−2}ℓ(Ker f_{n}) + (−1)^{n−1}ℓ(E_{n}). But Ker f_{n} = E_{n} and ℓ(Ker f_{1}) = 0 (since f_{1} is injective). Thus the entire sum is 0, as we wanted shown.

5. For any R-module M, we define its order or annihilator to be the set

Ann M = {a ∈ R : aM = {0}}.

Note that Ann M is a homogeneous ideal of R. Now let I be any subideal of Ann M and let \overline{R} = R/I. We view M as a \overline{R}-module in the natural way: if \overline{a} ∈ \overline{R}, u ∈ M, we define \overline{a}u as the element au, where a ∈ R and \overline{a} = a + I. (Check that this is well-defined.) Any R-submodules of M can be viewed as a \overline{R}-submodule of M, and vice-versa. Thus we can reduce the study of M as a R-module to the study of M as an \overline{R}-module. This important technique will be used in our proof. Typically, we take I = Ann M. See [13, p. 141].

Proof of the Hilbert-Serre Theorem. We first claim that each M_{d} has finite dimension as a K-vector space. Since M is finitely generated over R, let {y_{1}, …, y_{k}} be a basis for M. Since M is graded, each y_{i} may be assumed to be homogeneous (if not, we can replace y_{i} be its set of homogeneous components). Then every element of M_{d} has the form

∑_{i=1}^{k} u_{i}y_{i}, (u_{i} ∈ R)

where u_{i} ≠ 0 implies y_{i} has degree deg(y_{i}) ≤ d and u_{i} is a homogeneous polynomial of degree d − deg(y_{i}). Hence M_{d} can be generated as a K-vector space by elements of the form py where y ∈ {y_{1}, …, y_{k}} and p is a power product of degree d − deg(y). Our claim about M_{d} follows since there are only finitely many elements in this form py.

Now we prove the theorem by induction on the number n of variables. First, assume n = 0. We claim that the polynomial Φ_{M}(z) can be chosen to be identically zero. It suffices to show that dim_{K}(M_{d}) = 0 for all d sufficiently large. Again, let M be generated over R by a basis of homogeneous elements {y_{1}, …, y_{k}}. Let d_{0} be the maximum degree of these basis elements. Since every element u of M have the form u = ∑_{i=1}^{k} α_{i}y_{i}, α_{i} ∈ R = K, we see that deg(u) ≤ d_{0}. Thus if d > d_{0} then M_{d} = {0} and dim_{K}(M_{d}) = 0, as desired.

Now let n ≥ 1. Consider the homomorphism ϕ : M → M defined by

ϕ(u) = uX_{n}

for all u ∈ M. This homomophism is homogeneous of degree 1. Now consider the modules

N = Ker ϕ, P = coKer ϕ = M − ϕ(M)

where M − ϕ(M) denotes module difference. Note that X_{n} is in Ann N (since X_{n}N = {0}) and X_{n} is in Ann P (since X_{n} · (u + ϕ(M)) = 0 + ϕ(M) for any u ∈ M). Thus, by our preceding remarks, N and P can be regarded as modules over K[X_{1}, …, X_{n−1}, X_{n}]/(X_{n}) which is isomorphic to K[X_{1}, …, X_{n−1}]. Thus our induction hypothesis can be applied to N and P.

Now consider the sequence of homomorphisms:

0 ⟶ N ⟶^{i} M ⟶^{ϕ} M ⟶^{j} P ⟶ 0

where ϕ is as above, i is the inclusion map and j is the natural homomorphism from M to its difference module P. This is an exact sequence. By lemma 1, N = ⨁_{d} N_{d} is a graded module since it is the kernel of a homogeneous homomorphism ϕ, and P = ⨁_{d} P_{d} is also a graded module since it is the co-kernel of a ϕ. For each d, we may restrict the above sequence to the following:

0 ⟶ N_{d} ⟶^{i} M_{d} ⟶^{ϕ} M_{d+1} ⟶^{j} P_{d+1} ⟶ 0.

By the formula (4) for the alternating sum of module lengths, we get

dim(N_{d}) − dim(M_{d}) + dim(M_{d+1}) − dim(P_{d+1}) = 0
dim(M_{d+1}) − dim(M_{d}) = dim(P_{d+1}) − dim(N_{d})

But P and N are isomorphic to modules over K[X_{1}, …, X_{n−1}]. So by induction on n − 1, dim(P_{d}) (resp. dim(N_{d})) is a polynomial in d of degree ≤ n − 2 for all d ≥ d_{0} (for some d_{0}). [This remark holds even when n = 1 as the said polynomial is identically zero, which has degree −∞. The following argument is modified accordingly.] But this means that for d ≥ d_{0},

dim(M_{d+1}) − dim(M_{d}) = a_{0}\binom{d − 1}{n − 2} + a_{1}\binom{d − 1}{n − 3} + ⋯ + a_{n−2}

§3. Homogeneous Sets  Lecture XIII  Page 7

where a_{0}, …, a_{n−2} are integers. For d = 1, 2, …, d_{0} − 1, we may write

dim(M_{d+1}) − dim(M_{d}) = a_{0}\binom{d − 1}{n − 2} + a_{1}\binom{d − 1}{n − 3} + ⋯ + a_{n−2} + c_{d}

where c_{d} are integers. Also, we set

dim(M_{1}) = c_{1}.

Finally, using the binomial identity

\binom{d}{s} = ∑_{i=1}^{d−1} \binom{i}{s − 1},

we sum up the above expressions for dim(M_{i}) − dim(M_{i−1}) for i = 1, …, d and d ≥ d_{0}, giving

dim(M_{d}) = a_{0}\binom{d}{n − 1} + a_{1}\binom{d}{n − 2} + ⋯ + a_{n−2}\binom{d}{1} + a_{n−1}

for some integer a_{n−1}. This proves the Hilbert-Serre theorem.

Exercises

Exercise 2.1: Suppose I ⊆ R is an ideal where I = Ra_{1} + Ra_{2} + ⋯ + Ra_{k}. Let \overline{a}_{i} denote the image of a_{i} in I/I^{2}. Show that gr_{I}(R) = (R/I)[\overline{a}_{1}, …, \overline{a}_{k}]. □

Exercise 2.2: Verify lemma 1. □

§3. Homogeneous Sets

In the following, let X′ = {X_{0}, X_{1}, …, X_{n}} = {X_{0}} ∪ X. Some admissible ordering ≤_{A}

on PP(X) will be assumed.

Homogenization. Homogeneous ideals have nice combinatorial properties (somewhat akin to its well-known nice geometric motivations) which will be exploited in our proof. We first discuss the relation between general ideals and homogeneous ideals (in the standard sense). Given f ∈ K[X], there is a well-known procedure to obtain a homogeneous polynomial F ∈ K[X′]: if f has total degree d then F is obtained by multiplying each monomial of degree e in f by X_{0}^{d−e}. We shall denote the homogenized form F of f by f^{∧} and call X_{0} the homogenizing variable. For example,

f = 2X_{1}^{4}X_{2} − X_{2}^{2} + 3, f^{∧} = 2X_{1}^{4}X_{2} − X_{0}^{3}X_{2}^{2} + 3X_{0}^{5}.

There is a corresponding procedure to dehomogenize any polynomial F ∈ K[X′], simply by specializing X_{0} to 1. We denote the dehomogenized form of F by F^{∨}. If S ⊆ K[X] then S^{∧} = {f^{∧} : f ∈ S}, and similarly for S^{∨}. Clearly (f^{∧})^{∨} = f. It is also easy to check that

(f · g)^{∧} = f^{∧} · g^{∧},  (f · g)^{∨} = f^{∨} · g^{∨},  (f + g)^{∨} = f^{∨} + g^{∨}.

If I = Ideal(f_{1}, …, f_{m}) then clearly

Ideal(f_{1}^{∧}, …, f_{m}^{∧}) ⊆ Ideal(I^{∧}).

The reverse inclusion may be false: let f_{1} = X_{1}, f_{2} = X_{1}^{2} + X_{2}. Then I = Ideal(f_{1}, f_{2}) = Ideal(X_{1}, X_{2}) so Ideal(I^{∧}) = Ideal_{K[X_{0},X_{1},X_{2}]}(X_{1}, X_{2}), which properly contains Ideal(f_{1}^{∧}, f_{2}^{∧}) = Ideal(X_{1}, X_{1}^{2} + X_{0}X_{2}) = Ideal(X_{1}, X_{0}X_{2}). This situation cannot arise if {f_{1}, …, f_{m}} is a suitable Gröbner basis.

Let us say that an admissible ordering ≤_{A} is degree-compatible if it is induced by a weight matrix

\overline{W} whose first row is all 1. Thus, the total-degree ≤_{TOT} and reverse lexicographic ≤_{REV} orderings are

degree-compatible, but pure lexicographic ≤_{LEX} is not. For any admissible ordering ≤_{A} on PP(X), let

≤_{A}^{∧}

denote the admissible ordering on PP(X′) where u(≤_{A}^{∧})v iff deg(u) < deg(v) or else, (u^{∨}) ≤_{A}(v^{∨}).

Notice that ≤_{A}^{∧} is a degree-compatible admissible ordering. In fact, reverse lexicographic ordering

can be obtained by recursive application of this operator.

Lemma 3 Let ≤_{A} be an admissible ordering on PP(X).

(i) If G = {f_{1}, …, f_{m}} is a Gröbner basis for I ⊆ K[X] relative to ≤_{A}, and ≤_{A} is degree-compatible,

then Ideal(G^{∧}) = Ideal(I^{∧}). In particular, G^{∧} is a Gröbner basis.

(ii) If {F_{1}, …, F_{m}} is a Gröbner basis for Ideal(I^{∧}) ⊆ K[X′] relative to ≤_{A}^{∧}, then {F_{1}, …, F_{m}}^{∨}

is a Gröbner basis for I relative to ≤_{A}.

Proof. (i) The non-trivial inclusion is Ideal(I^{∧}) ⊆ Ideal(G^{∧}). For this, it suffices to show that if F ∈ I^{∧} then F ∈ Ideal(G^{∧}). We may assume that F = f^{∧} where f = ∑_{i} α_{i}f_{i}, f_{i} ∈ G, α_{i} ∈ K[X] and hterm(f) ≥_{A}hterm(α_{i}f_{i}). Hence deg(f) ≥ deg(α_{i}f_{i}). Then F = ∑_{i} α_{i}^{∧}f_{i}^{∧}X_{0}^{d−d_{i}}

where d = deg f and d_{i} = deg(α_{i}f_{i}). This shows F ∈ Ideal(G^{∧}). The fact that G^{∧} is a Gröbner basis follows from the standard characterization of Gröbner bases. (ii) Let f ∈ I. It is sufficient to show that f = ∑_{i=1}^{m} α_{i} · F_{i}^{∨} for some α_{i} ∈ K[X] and where hterm(f) ≥_{A}hterm(α_{i}·F_{i}^{∨}). Since the F_{i}’s form a Gröbner basis, we have f^{∧} = ∑_{i=1}^{m} β_{i}F_{i} where β_{i} ∈

K[X′] and hterm(f^{∧})(≥_{A}^{∧})hterm(β_{i}F_{i}). Applying the dehomogenizing operator to this expression for

f^{∧}, and letting β_{i}^{∨} = α_{i}, the result follows. In particular, we check that hterm(f^{∧})(≥_{A}^{∧})hterm(β_{i}F_{i})

and deg(f^{∧}) = deg(β_{i}F_{i}) implies hterm(f) ≥_{A}hterm(α_{i} · F_{i}^{∨}). Q.E.D.

Homogeneous Sets. A subset T ⊆ K[X] is a homogeneous set if T is a K-vector space and f ∈ T implies each homogeneous component of f belongs to T. Note that T is a K-vector space means that au + v ∈ T for all u, v ∈ T, a ∈ K. An important special case of homogeneous sets is where f ∈ T implies each monomial in f belongs to T; we call these monomial sets.

For instance, homogeneous ideals are homogeneous sets and monomial ideals are monomial sets. Gröbner bases theory provides other examples of such sets: for any ideal I ⊆ K[X] and f ∈ K[X], let nf_{I}(f) denote the unique normal form of f with respect to the Gröbner basis of I. Let

NF(I) :={nf_{I}(f) : f ∈ K[X]}

denote^{2} the set of all normal forms.

2This should not be confused with the notation NF_{G}(f) for the set of G-normal forms of f.

Lemma 4

(i) NF(I) is a monomial set. (ii) If H = Head(I) then NF(H) = NF(I).

Proof. (i) If f, g ∈ NF(I), then it is easy to see that af + g ∈ NF(I) for any a ∈ K. Thus NF(I) is a K-vector space. Also NF(I) is a monomial set because if m is a monomial in f ∈ NF(I) then m ∈ NF(I). (ii) Recall Head(I) = Ideal({hterm(f) : f ∈ I}). Clearly f is reducible by G iff f is reducible by hterm(G). But, by the standard characterization of Gröbner bases, G is a Gröbner basis for I iff hterm(G) is a Gröbner basis for H. Hence f ∈ NF(I) iff f ∈ NF(H). Q.E.D.

Hilbert Function of Homogeneous Sets. For each natural number z ∈ ℕ, let

T_{z}:={f ∈ T : f is homogeneous of degree z}.  (6)

Note that T_{z} is also a K-vector space, and so we may speak of its vector space dimension, denoted dim_{K}(T_{z}). The Hilbert function ϕ_{T} : ℕ → ℕ of T is defined by

ϕ_{T} (z) := dim_{K}(T_{z}).

As before, if the Hilbert function is equal to a polynomial f(z) for z sufficiently large, we shall call f(z) the Hilbert polynomial of T and denote it by Φ_{T} (z).

Example: The Hilbert function should be viewed combinatorially as a counting function. If T is a monomial set, then ϕ_{T} (z) just counts the number of power products of total degree z in T_{z}. In figure 1, we illustrate this for K[X, Y]: each lattice point corresponds to a power product in PP(X, Y), where moving to the north-east (resp., north-west) corresponds to increasing powers of Y (resp., X).

X^{3}X^{2} X 1 Y Y^{2} Y^{3}
Figure 1: Hilbert function of Ideal(X^{3}Y, X^{2}Y^{2}).

The origin corresponds to 1 = X^{0}Y^{0}. The three circled lattice points are X^{3}Y, X^{2}Y^{2} and X^{3}Y^{2}. The ideal I = Ideal(X^{3}Y, X^{2}Y^{2}) is represented in figure 1 by the set of lattice points lying above the solid curve. The Hilbert function ϕ_{I}(z) counts the number of monomials in I that are of total degree z; these are the monomials at level z in the figure. For instance, ϕ_{I}(z) = 0 for z ≤ 3, ϕ_{I}(4) = 2. In general, ϕ_{I}(z) = z − 2 for z ≥ 4.

If I is a homogeneous ideal, the Hilbert-Serre theorem shows that Hilbert function ϕ_{I}(z) is equal to the Hilbert polynomial Φ_{I}(z) for z larger than the Hilbert constant h_{I}. Note that with T = K[X] we have

ϕ_{T} (z) = \binom{z + n − 1}{n − 1},

a polynomial of degree n − 1 that counts the number of terms of total degree z. The set NF(I), being monomial, has a Hilbert function ϕ_{NF(I)}(z). It is easy to see that

ϕ_{I}(z) + ϕ_{NF(I)}(z) = \binom{z + n − 1}{n − 1}.  (7)

So we conclude from the Hilbert-Serre theorem:

Corollary 5 For any ideal I, the Hilbert function ϕ_{NF(I)}(z) of NF(I) is a polynomial of degree ≤ n−1 for z large enough.

Again, let Φ_{NF(I)}(z) denote the polynomial in this corollary. Note that for z ≥ h_{I} (the Hilbert constant), we also have

ϕ_{NF(I)}(z) = Φ_{NF(I)}(z).

Our immediate goal is to find an upper bound on h_{I}. It turns out that h_{I} yields an upper bound on the function G(n, d) (§1). Monomial sets has a key role in this development:

Lemma 6 Let I be a homogeneous ideal and H = Head(I). Then I and H have the same Hilbert functions:

ϕ_{I} = ϕ_{H}

Proof. We first show ϕ_{I}(z) ≤ ϕ_{H}(z). Let f_{1}, …, f_{m} ∈ I be homogeneous of degree z and suppose they are linearly independent over K. We must show that there exists h_{1}, …, h_{m} ∈ H of degree z and linearly independent over K. Suppose f′_{1} = f_{1} is the polynomial in {f_{1}, …, f_{m}} with the ≤_{A}-largest head term. Now use f′_{1} to reduce each polynomial in {f_{2}, …, f_{m}}. This just ensures

that the resulting polynomials have head terms distinct from h_{1} := hterm(f′_{1}). Also, note that none of reduced polynomials are zero – otherwise, we have found a linear dependence in {f_{1}, …, f_{m}}. Let f′_{2} be the polynomial with the ≤_{A}-largest headterm in the reduced set of polynomials and let

h_{2} := hterm(f′_{2}). Now repeat this process to find h_{3}, …, h_{m}. But h_{1}, …, h_{m}, being pairwise distinct, are linearly independent. Since they are of degree d and belong to H, this proves ϕ_{I}(z) ≤ ϕ_{H}(z).

To show ϕ_{I}(z) ≥ ϕ_{H}(z), suppose f_{1}, …, f_{m} ∈ I such that hterm(f_{1}), …, hterm(f_{m}) are distinct and of degree z. Then clearly the above process yields f′_{1}, …, f′_{m} ∈ I that are linearly independent over K. Q.E.D.

From (7), we obtain ϕ_{NF(I)} = ϕ_{NF(H)}, since NF(I) = NF(H). We are mainly interested in Hilbert functions ϕ_{T} where T has the form I or NF(I); by the last two lemmas, we may assume that T are monomial sets in these cases.

Homogeneous Decompositions. We want to decompose a homogeneous set T as a direct sum

T = S_{1} ⊕ S_{2} ⊕ ⋯ ⊕ S_{i} ⊕ ⋯  (8)

where the S_{i} ⊆ T are K-vector spaces. In case the S_{i}’s are homogeneous sets, we call the set {S_{1}, S_{2}, S_{3}, …} a homogeneous decomposition of T. An example of homogeneous decomposition is T = T_{0} ⊕ T_{1} ⊕ T_{2} ⊕ ⋯ where T_{z} is defined in (6). If equation (8) is a homogeneous decomposition, then

ϕ_{T} (z) = ∑_{i≥1} ϕ_{S_{i}}(z).  (9)

This is because each u ∈ T_{z} has a unique decomposition u = ∑_{i≥1} u_{i} where u_{i} ∈ (S_{i})_{z} = S_{i} ∩ T_{z}. Thus computing the Hilbert function of T is reduced to computing those of S_{i}.

Lemma 7 (Dubé)

(i) For any ideal I ⊆ K[X], we obtain the following direct decomposition:

K[X] = I ⊕ NF(I).

(ii) Let J be a proper subideal of I ∈ K[X] and I = Ideal(f_{0}, J) for some f_{0} ∈ K[X].

I = J ⊕ f_{0} · NF(J : f_{0}).

Proof.

(i) For f ∈ K[X], f = nf_{I}(f) + g where g ∈ I. But nf_{I}(f) is unique. (ii) First we show that J + f_{0} · NF(J : f_{0}) = I. Since J : f_{0} is the ideal {g ∈ R : g · f_{0} ∈ J}, the containment J + f_{0} · NF(J : f_{0}) ⊆ I is immediate. To show the reverse inclusion, note that I = Ideal(f_{0}, J) implies every f ∈ I has the form

f = αf_{0} + β

where α ∈ R, β ∈ J. But α = nf_{J:f_{0}}(α) + γ where γ ∈ J : f_{0}. Hence

f = f_{0} · nf_{J:f_{0}}(α) + (β + γf_{0}).

This shows f ∈ f_{0} · NF(J : f_{0}) + J. Finally, we must show that f_{0} · NF(J : f_{0}) + J is indeed a direct sum. Suppose f = αf_{0} + β = α′f_{0} + β′ where α, α′ ∈ NF(J : f_{0}) and β, β′ ∈ J. Then (α − α′)f_{0} = β′ − β ∈ J. This implies α − α′ ∈ J : f_{0}. But α − α′ ∈ NF(J : f_{0}). The last two assertions imply α − α′ = 0. Q.E.D.

Note that if I, J and f_{0} are homogeneous then the decompositions in the above lemma are homogeneous. Moreover, we can repeatedly apply the decomposition in part (ii), so that if I = Ideal(f_{1}, …, f_{m}) and I_{i} = Ideal(f_{1}, …, f_{i−1}) (i = 1, …, m) then

I = Ideal(f_{1}) ⊕ (⨁_{i=1}^{m} f_{i} · NF(I_{i} : f_{i})) .  (10)

Exercises

Exercise 3.1: Suppose that I, J are homogeneous ideals of a graded ring R.

(i) Show that I + J, I ∩ J, IJ, I : J and \sqrt{I} are each homogeneous.

(ii) Show that I is prime if and only if for all homogeneous elements u, v ∈ R, uv ∈ I implies u ∈ I or v ∈ I. (iii) Show that I is primary if and only if for all homogeneous elements u, v ∈ R, uv ∈ I implies u ∈ \sqrt{I} or v ∈ \sqrt{I}. □

§4. Cone Decomposition  Lecture XIII  Page 12

Exercise 3.2: What is the Hilbert function of Ideal(f) where deg(f) = d and n = 3? of Ideal(X^{2} + Y^{2} + Z^{2}, XY, Z)? □

Exercise 3.3: Show that ϕ_{T} (z) is the number of distinct power products of total degree z that appears as head terms of polynomials in T. (Thus ϕ_{T} (z) is independent of the admissible

order ≤_{A}.) □

Exercise 3.4: Carry out the preceding development for a general K-vector space T ⊆ K[X_{1}, …, X_{n}], not necessarily a homogeneous set. HINT: for the affine version of the Hilbert function, ϕ_{T} (z) = dim_{K}(T_{z}) let T_{z} be the set of polynomials of total degree at most z. □

Exercise 3.5: Given {f_{1}, …, f_{m}}, give an algorithm to test if Ideal(f_{1}, …, f_{m}) is homogeneous. HINT: reduce the problem to computing a Gröbner basis. □

§4. Cone Decomposition

Let f ∈ K[X] be homogeneous and Y ⊆ X be a set of variables. A cone C is a set of the form

Cone(f, Y) := f · K[Y].

For instance, Cone(1, X) = K[X]. A principal ideal is a cone: Ideal(f) = Cone(f, X). Define

deg(C) := deg(f), dim(C) := |Y|.

If f = 0 then Cone(f, Y) = {0} is the trivial cone; by definition, dim(C) = deg(C) = −∞ for the trivial cone. If T = C_{1} ⊕ ⋯ ⊕ C_{r} where C_{i} are cones, then we call D = {C_{1}, …, C_{r}} a cone decomposition of T. Note that the C_{i}’s are non-trivial unless T = {0}, in which case we have the trivial decomposition D = {Cone(0, ∅)}.

Figure 2 illustrates a cone decomposition for n = 2. The set

Cone(X^{2}Y^{2}, ∅), Cone(X^{3}Y, {X}), Cone(X^{3}Y^{2}, {X}), Cone(X^{2}, Y^{3}, {X, Y })

is a cone decomposition for the ideal Ideal(X^{3}Y, X^{2}Y^{2}).

Cones are homogeneous sets with very simple Hilbert functions:

dim(C) = 0 : ϕ_{C}(z) = \{ \begin{matrix}1 & if z = deg(C) \\ 0 & else \end{matrix}

dim(C) > 0 : ϕ_{C}(z) = \{ \begin{matrix}0 & if z < deg(C) \\ \binom{z−deg(C)+dim(C)−1}{dim(C)−1} & else \end{matrix}

Definition 1 We call a cone decomposition

D = {C_{1}, …, C_{r}, C_{r+1}, …, C_{r+s}}, (r, s ≥ 0)  (11)

C(X^{3}Y, {X}) C(X^{3}Y^{2}, {X})  C(X^{2}Y^{2}, ∅) C(X^{2}Y^{3}, {X, Y })
Figure 2: Cone decomposition for Ideal(X^{3}Y, X^{2}Y^{2}).

exact if, after relabelling, we have

dim(C_{1}) ≥ dim(C_{2}) ≥ ⋯ ≥ dim(C_{r}) > 0 = dim(C_{r+1}) = ⋯ = dim(C_{r+s})

and

deg(C_{1}) < deg(C_{2}) < ⋯ < deg(C_{r}) = deg(C_{1}) + r − 1.

The positive part of D be defined as

D^{+} :={C ∈ D : dim(C) > 0}.

Thus deg(C_{i+1}) = deg(C_{i}) + 1 for i = 1, …, r − 1. We provide some intuition for this definition using a graphic representation. In figure 3, we represent each cone as a lattice point in a deg-dim axes system.

A cone decomposition D is then represented by a multiset of lattice points, one lattice point for each cone in D. If D is exact, then only lattice points of dimension 0 can have multiplicity greater than 1. For any set D of cones, let

dim(D) := max{dim(C) : C ∈ D}

and

maxdeg(D) := max{deg(C) : C ∈ D}, mindeg(D) := min{deg(C) : C ∈ D}.

If D = ∅, we set maxdeg(D) = mindeg(D) = 0. For any cone decomposition D, we are mostly interested in the quantities maxdeg(D) and mindeg(D^{+}). Notice that if D and D′ are cone decompositions of a set T then dim(D) = dim(D′). Hence, we may speak of the cone dimension dim(T) of T.

Let D_{0} be the cone decomposition illustrated in figure 3. Then dim(D_{0}) = 8, maxdeg(D_{0}) = 15 and mindeg(D_{0}^{+}) = 5. Assuming no multiplicity of lattice points in this figure, we may verify that D_{0} is exact: this amounts to saying that the lattice points of D_{0}^{+} represent a discrete non-increasing function in the range from mindeg(D_{0}^{+}) to maxdeg(D_{0}^{+}).

Macaulay Constants. The Macaulay constants of the exact cone decomposition D in equation (11) is a set b_{0}, …, b_{n+1} of constants defined as follows: For i = 0, …, n, define b_{i} to be

b_{i}:= \{ \begin{matrix}1 + max\{deg(C) : C ∈ D, dim(C) ≥ i\}, & if dim(D) ≥ i \\ mindeg(D^{+}), & dim(D) < i. \end{matrix}

8 7 6 5 4 3 1 2 1 2  4 5 3  7 b_{8} b_{7} b_{6} b_{5} b_{4}  13 b_{3} b_{2} b^{1} b_{0} dim  6  15  deg

Figure 3: Illustrating exact decomposition

In particular, we always have the relation b_{n+1} = mindeg(D^{+}). Hence,

1 + maxdeg(D) = b_{0} ≥ b_{1} ≥ ⋯ ≥ b_{n} ≥ b_{n+1} = mindeg(D^{+}).

In the example D_{0} of figure 3, we have

b_{0} = 16, b_{1} = b_{2} = b_{3} = 14, b_{4} = 10, b_{5} = 8, b_{6} = b_{7} = 7, b_{8} = 5.

The following derivation motivates the definition of the Macaulay constants. First, there are exactly

b_{i} − b_{i+1}

cones of dimension i (i = 1, 2, …, n). In fact, these cones have degrees

b_{i+1}, b_{i+1} + 1, …, b_{i} − 1.

So for z ≥ b_{0}, by (9),

ϕ_{T} (z) = ∑_{C∈D} ϕ_{C}(z)
= ∑_{i=1}^{n} ∑_{d=b_{i+1}}^{b_{i}−1} \binom{z − d + i − 1}{i − 1}
= ∑_{i=1}^{n} [\binom{z − b_{i+1} + i}{i} − \binom{z − b_{i} + i}{i}]
= \binom{z − b_{n+1} + n}{n} + ∑_{i=1}^{n−1} [\binom{z − b_{i+1} + i}{i} − \binom{z − b_{i+1} + i + 1}{i + 1}] − \binom{z − b_{1} + 1}{1}

\begin{matrix}c \\ ◯ \end{matrix} Chee-Keng Yap October 4, 1995

§5. Exact Decomposition of NF(I)  Lecture XIII  Page 15

= \binom{z − b_{n+1} + n}{n} − ∑_{i=1}^{n−1} \binom{z − b_{i+1} + i}{i + 1} − \binom{z − b_{1}}{1} − 1

= \binom{z − b_{n+1} + n}{n} − ∑_{i=1}^{n} \binom{z − b_{i} + i − 1}{i} − 1.  (12)

This form of the Hilbert polynomial is due to Macaulay, and we will refer to it as the “Macaulay form” of the Hilbert polynomial of T. This polynomial is of at most degree n − 1 since the leading terms of \binom{z−b_{n+1}+n}{n} and \binom{z−b_{n}+n−1}{n} cancel. Also notice that b_{0} does not appear in the equation. Since these constants depend on the exact decomposition which is by no means unique, the following result is interesting.

Lemma 8 The Macaulay constants b_{0}, b_{1}, …, b_{n} for a homogeneous set T are uniquely determined once b_{n+1} is fixed.

Proof. As a homogeneous set, T has a Hilbert polynomial. Write this in the standard form

Φ_{T} (z) = ∑_{i=0}^{n−1} a_{i}z^{i}.  (13)

The constants a_{0}, …, a_{n−1} are unique in this form. Note that only b_{n+1} and b_{n} affect the term of degree n − 1 in equation (12). Equating the coefficients of z^{n−1} in the two forms, we express a_{n−1} in terms of b_{n+1} and b_{n}. Thus b_{n} is completely determined by b_{n+1} and a_{n−1}. In general, a_{i−1} can be expressed in terms of b_{i}, …, b_{n+1} for i = n, n − 1, …, 2, 1. Hence b_{i} is determined from a_{i−1}, b_{i+1}, …, b_{n+1}. By induction, b_{i+1}, …, b_{n+1} are been determined, so b_{i} is determined. So the Macaulay form of the polynomial is completely determined. What about the constant b_{0}? We claim that b_{0} is the smallest value z_{0} ≥ b_{1} such that for all z ≥ z_{0}, the expression 12 equals the Hilbert function ϕ_{T} (z). To see this, note that for z ≥ b_{1}, the Macaulay formula accurately counts the contribution of cones of positive dimension. So any error is due to cones of dimension zero; by definition of b_{0}, it is correct for z ≥ b_{0}. On the other hand, if b_{0} > b_{1} then the Macaulay formula is wrong at z = b_{0} − 1. Q.E.D.

We may also define the dimension dim(T) of T to be dim(D) for any cone decomposition D of T. It is clear that this definition does not depend on the choice of D.

Exercises

Exercise 4.1: If T ⊆ K[X] is a K-vector space, not necessarily homogeneous, define the affine version of the Hilbert function φ_{T} (z) to be the dimension of the set T_{≤z}:={u ∈ T : deg(u) ≤ z}. Carry out the analogous development. □

§5. Exact Decomposition of NF(I)

This section gives an exact decomposition of NF(I) where I is any ideal. We may assume that I is a monomial ideal. Note that if u is a monomial then I: u is a monomial ideal. We introduce the convenient if somewhat unusual notation

a: b = \frac{a}{GCD(a, b)}

where a, b ∈ K[X]. Note that a: b ∈ K if and only if a|b, and a: b, b: a are relatively prime. This notation is justified on the grounds that Ideal(a: b) = Ideal(a) : b, where the right-hand side refers to ideal quotient.

Lemma 9 Let u be a monomial. Then I: u = Ideal(u_{1} : u, u_{2} : u, …, u_{m}: u), where I is generated by the monomials u_{1}, …, u_{m}.

Proof. Let J = Ideal(u_{1} : u, u_{2} : u, …, u_{m}: u). To show I: u ⊆ J, let f ∈ I: u where f = ∑_{i} f_{i} and each f_{i} is a monomial. Then f · u = ∑_{i} f_{i}u ∈ I. Since I is a monomial ideal, each f_{i}u is in I. So f_{i}u is divisible by some u_{j}. This means f_{i} is divisible by u_{j} : u. We conclude that f ∈ J. Conversely, each u_{i}: u ∈ I: u, so (u_{i}: u) · u ∈ Ideal(u_{i}) ⊆ I. This shows u_{i}: u ∈ I: u. So J ⊆ I: u. Q.E.D.

The key idea of the decompositions is simple: let X_{0} ∈ Y and Y′ = Y \ {X_{0}}. Then we have the cone decomposition

Cone(u, Y) = Cone(uX_{0}, Y) ⊕ Cone(u, Y′)
= C_{1} ⊕ C_{2}  (14)

where C_{1}, C_{2} are implicitly defined here. We may call this the shift decomposition of Cone(u, Y). For example, let u = X^{2}Y, Y = {X, Z} and X_{0} = X. Then C_{1} = Cone(X^{3}Y, {X, Z}) and C_{2} = Cone(X^{2}Y, {Z}). Note that deg(C_{1}) is 1 more than deg(C) and dim(C_{2}) is 1 less than dim(C). This is illustrated in figure 4:

C_{2} dim  deg C  C_{1}

Figure 4: Shifting a cone.

We repeat this operation and obtain for any cone C the cone decomposition

C = ⨁_{i=0}^{d} C′_{i}  (15)

where d = dim C, dim C′_{i} = i (i = 0, …, d) and deg(C′_{i}) = deg(C) + 1 (i = 1, …, d). Let us call this the “complete shift decomposition”. We now describe an application of this. We will say that C is “violating” in a set D of cones if dim(C) > 0 and for some other C′ ∈ D, one of the following three conditions hold:

(I) deg C′ = deg C and dim C′ ≥ dim C.

(II) deg C′ > deg C and dim C′ > dim C.

(III) deg C′ > 1 + deg C but there does not exist C′′ ∈ D^{+} with deg C′′ = 1 + deg C.

We refer to these as violations of types (I), (II) and (III), respectively. For any cone decomposition D, it is easy to see that D is exact iff D contains no violating cones. The following is a procedure to remove violating cones:

Exact Conversion

Input: D, a cone decomposition of a set T.

Output: D, an exact cone decomposition of T.

Method:

while there exists a “violating” cone C ∈ D do Replace C by its “complete shift decomposition”, C_{0}, C_{1}, …, C_{d} as in equation (15).

If this procedure halts, it is clear that the result is correct.

Lemma 10 The exact conversion procedure halts.

Proof. We use induction on |D^{+}|. If |D^{+}| ≤ 1, the result is clear. So let |D^{+}| ≥ 2. Let d_{1} := mindeg{C ∈ D^{+} : dim C = dim D} and D_{1} :={C ∈ D^{+} : deg C ≤ d_{1}}. If D_{1} has no violating cones then |D_{1}| = 1 and D is exact iff D \ D_{1} is exact. By induction, the exact conversion applied to D \ D_{1} halts. The lemma holds in this case. Suppose D_{1} contains a violating cone. At each step, the procedure replaces a cone C by its complete shift decomposition. If C ∈ D_{1}, then this reduces the size of D_{1} and the procedure halts, by double induction on |D_{1}| and |D^{+}|. If C ∉ D_{1}, then the procedure can only choose C from D\D_{1}. Again by induction, it cannot do this indefinitely. This completes the proof. Q.E.D.

Now we describe a method to exactly decompose a set of the form

NF(I) ∩ Cone(u, Y)

where Y ⊆ X = {X_{1}, …, X_{n}} and u ∈ PP(X). This is a slight generalization of the original goal of exactly decomposing NF(I).

Exact Decomposition Algorithm

Input: (u, Y, F) where u ∈ PP(X),

Y ⊆ X a set of variables and F ⊆ PP(X) is a monomial basis for an ideal I.

Output: D, an exact cone decomposition for NF(I) ∩ Cone(u, Y).

Method:

1. (BASIS 1) For each v ∈ F do: if v: u ∈ PP(Y) then goto step 2.

Return D = {Cone(u, Y)}.

2. (BASIS 2) If v: u = 1 for any v ∈ F then return the trivial cone decomposition D = {Cone(0, ∅)}.

3. (DIVIDE) Let X_{0} ∈ Y such that X_{0}|v: u for some v ∈ F. Let Y′ = Y \ {X_{0}} and Cone(u, Y) = C_{1} ⊕ C_{2}

with C_{1} = Cone(uX_{0}, Y) and C_{2} = Cone(u, Y′), as in equation (14).

4. (RECURSE) Call the exact decomposition algorithm recursively (twice) to decompose NF(I) ∩ C_{1} and also NF(I) ∩ C_{2}.

5. (CONQUER) Let D_{i} (i = 1, 2) be the exact decomposition for NF(I) ∩ C_{i}. Return the “exact conversion” of D_{1} ∪ D_{2} using the procedure above.

Correctness. We justify each step in the algorithm.

Step 1: (BASIS 1) Suppose we returned in this step. This means for all v ∈ F, v: u ∉ PP(Y). We need to show that D = {Cone(u, Y)} is an the exact decomposition of NF(I) ∩ Cone(u, Y). This is equivalent to Cone(u, Y) ⊆ NF(I). The following characterization justifies this step.

Lemma 11 Cone(u, Y) ⊆ NF(I) iff (for all f ∈ F)f : u ∉ PP(Y).

Proof. (⇒) If f : u ∈ PP(Y) then there exists α ∈ PP(Y) such that f : u = α, i.e., f|uα, or equivalently, uα ∉ NF(I). This contradicts our assumption that Cone(u, Y) ⊆ NF(I). (⇐) If αu ∈ Cone(u, Y) then for all f ∈ F, f does not divide αu since f : u ∉ PP(Y). Hence αu ∈ NF(I). Q.E.D.

Step 2: (BASIS 2) Suppose we returned this step. Then clearly v|u and Cone(u, Y) ⊆ I. Hence Cone(u, Y) ∩ NF(I) = {0}. This justifies the output of the trivial decomposition.

Step 3: (DIVIDE) The choice X_{0} ∈ Y exists because we did not return in steps 1 and 2. For now, any choice of X_{0} will do. We describe later a more careful choice of X_{0} in order to ensure a certain property of the decomposition.

Step 4: (RECURSE) The recursive calls to decompose NF(I) ∩ C_{i} (i = 1, 2) must be shown to eventually return. To show this, we must indicate the sense in which the new arguments are “smaller” than the original inputs. Towards this end, we define the “size” of the input (u, Y, F) to be

|Y| + ∑_{v∈F} deg(v: u).

Note that we use deg(v: u) instead of deg(v). In the case of C_{1}, our arguments are (uX_{0}, Y, F). Note that

deg(v: uX_{0}) ≤ deg(v: u)

is always true; moreover, our choice of X_{0} ensures that the inequality is strict for some v ∈ F. Hence the size has gone down. In the case of C_{0}, the arguments are (u, Y′, F) clearly has reduced size by virtue of |Y′| < |Y|.

Step 5: (CONQUER) Notice that D_{1} ∪ D_{2} is a cone decomposition of Cone(u, Y) ∩ NF(I). Then applying the “exact conversion” procedure above to D_{1} ∪ D_{2} gives us the desired output. This concludes our justification of the algorithm.

Modified Exact Decomposition Algorithm. We wish to modify step 3 in the above algorithm. But we first develop some insights. Let D be the exact decomposition for NF(I) as returned by the above algorithm on input (u, Y, F) where F is a monomial basis for I. Let

T = Cone(u, Y) ∩ NF(I).

Note that for any w ∈ Cone(u, Y) and Y′ ⊆ Y,

Cone(w, Y′) ⊆ T iff Cone(u, Y′) ⊆ T.

Of course, dim(T) is equal to the largest subset Y′ ⊆ Y such that Cone(u′, Y′) ⊆ NF(I). The preceding remark implies that we can in fact take u = u′. For lack of a better name, let us call any subset Y′ ⊆ Y of maximal cardinality such that Cone(u, Y′) ⊆ T a “maximum set” relative to u, I. This is equivalent to saying Y′ has maximum cardinality subject to

Cone(u, Y′) ⊆ NF(I).  (16)

Example: Let Y = X = {W, X, Y, Z}, u = Y^{2} and F = {W^{2}XZ, X^{2}Y^{3}, Y^{4}Z, W Y^{3}}. Let F′ comprise the elements f : u for all f ∈ F. So F′ = {W^{2}XZ, X^{2}Y, Y^{2}Z, W Y }. Using the characterization in lemma 11, we see that the maximal (not maximum) sets that satisfy (16) are

{W, Z}, {W, X}, {X, Z}, {Y }.

The first three sets are maximum.

We want our algorithm on input (u, Y, F) to return a decomposition D that contains a cone of the form Cone(u, Y^{∗}) where Y^{∗} is a maximum set in the sense of (16). Note that D will always contain a cone of the form Cone(u′, Y^{∗}) — so what we seek is u = u′. To this end, we modify step 3 of the algorithm as follows:

3. (DIVIDE) Choose X_{0} such that Y′:= Y \ {X_{0}} contains a maximum set in the sense of (16). Let C_{1} = Cone(uX_{0}, Y) and C_{2} = Cone(u, Y′).

This choice of X_{0} exists since Y is not a maximum set by the time we reach step 3 in the algorithm. Furthermore, X_{0} still has the property that X_{0} divides f : u for some f ∈ F (this property ensures termination). To see this, let Y^{∗} ⊆ Y \ {X_{0}} be a maximum set. By the characterization in lemma 11, f : u ∉ PP(Y^{∗}) for all f ∈ F. If X_{0} does not divide f : u for all f ∈ F then {X_{0}} ∪ Y^{∗} has the C-property, contradicting the assumption that Y^{∗} is maximum.

Lemma 12 Consider the modified algorithm on input (u, Y, F). The output cone decomposition D, if non-trivial, contains a cone of the form Cone(u, Y^{∗}) where Y^{∗} is maximum and mindeg(D) = deg u.

Proof. The lemma is clearly true in case of “basis 1”, and by assumption, “basis 2” does not occur. So assume D is the “exact conversion” of D_{1} ∪D_{2}. Notice that D_{2} is nontrivial since some maximum set Y^{∗} is contained in Y′ = Y \ {X_{0}}. So by induction, D_{2} contains some cone C^{∗} = Cone(u, Y^{∗}). Such a cone is clearly unique (since u is given). If D_{1} is trivial, then D = D_{2} and the lemma is true. Otherwise, mindeg(D_{2}) = deg u and mindeg(D_{1}) = 1 + deg u. It follows that C^{∗} is non-violating and our exact conversion procedure will not replace C^{∗}. Hence C^{∗} ∈ D. Q.E.D.

Applying the modified algorithm to input (1, X, F), we conclude that for every monomial ideal I = Ideal(F) ≠ K[X], the set NF(I) has an exact cone decomposition D for which

mindeg(D^{+}) = 0.  (17)

(Recall that if D^{+} = ∅, then mindeg(D^{+}) = 0 by definition.)

Recall that the reduced basis of a monomial ideal is unique and consists of power products (§XII.5).

Lemma 13 Let F be a reduced monomial basis, and D be the output of the modified algorithm on input (u, Y, F), where Y ⊆ X, |Y| ≥ 1. If D is non-trivial then for each f ∈ F ∩ Cone(u, Y), there is some C ∈ D with deg C = deg(f) − 1.

Proof. Let f ∈ F ∩ Cone(u, Y). First note that deg(f : u) ≥ 1 since otherwise f|u and D is trivial. We now use double induction on deg(f : u) and |Y|. If deg(f : u) = 1 then f = uX_{0} for some X_{0} ∈ Y and by the previous lemma, D contains a cone of degree deg(u) = deg(f) − 1. If |Y| = 1 then it is easy to see that there is at most one element f in F ∩ Cone(u, Y). Moreover, if such an f exists, then f = uX_{0}^{k} for some k ≥ 1 where Y = {X_{0}}. Then clearly D contains the Cone(uX_{0}^{k−1}, ∅) which has degree deg(f) − 1. Finally, assume deg(f : u) ≥ 2 and |Y| ≥ 2. Then step 3 decomposes Cone(u, Y) into C_{1} ⊕ C_{2} where C_{1} = Cone(uX_{0}, Y) and C_{2} = Cone(u, Y \ {X_{0}}). The result then follows by inductive hypothesis. Q.E.D.

Here is a cone decomposition of NF(I) that does not have the property in this lemma: let I = Ideal(XY Z) and

D = {Cone(1, ∅), Cone(X, {X, Y }), Cone(Y, {Y, Z}), Cone(Z, {Z, X})}

Of course, this decomposition is not exact.

Corollary 14 Let F be a reduced basis for an arbitrary ideal I. If b_{0}, …, b_{n+1}, (b_{n+1} = 0), is a set of Macaulay constants for NF(I) then deg(hterm(f)) ≤ 1 + b_{0} for each f ∈ F.

Proof. The constants b_{0}, …, b_{n} are uniquely determined by the requirement b_{n+1} = 0. But we can also obtain b_{0} as maxdeg(D) where D is is an exact decomposition for NF(I) obtained by applying the algorithm to the input (1, X, hterm(F)), since hterm(F) is a basis for Head(I). For f ∈ F, the preceding lemma implies that maxdeg(D) ≥ deg(hterm(f)) − 1 Hence b_{0} ≥ deg(hterm(f)) − 1.

Q.E.D.

Remark: If the implicit admissible ordering here is degree-compatible, we can simplify the bound in this corollary to deg(f) ≤ 1 + b_{0}. It is interesting to note that the exact decomposition algorithm gives us a constructive proof of the Hilbert-Serre theorem.

Exercises

§6. Exact Decomposition of Ideals  Lecture XIII  Page 21

Exercise 5.1: Let I = Ideal(XY^{2}Z, X^{2}Y Z^{2}). Give an exact cone decomposition of NF(I), and determine its Macaulay constants, and Hilbert function. □

Exercise 5.2: Derive an expression for I:(u_{1}, …, u_{k}) involving I: u_{i}’s. Further, derive an expression involving LCM(v_{i}, v_{j})’s for suitable v_{i}, v_{j}’s. HINT: Ideal(u, u′) ∩ Ideal(v, v′) = Ideal(LCM(u, v), LCM(u, v′), LCM(u′, v), LCM(u′, v′)). □

Exercise 5.3: Derive a bound on the length of the exact conversion process. □

§6. Exact Decomposition of Ideals

We construct a cone decomposition of an arbitrary ideal I. Let

I = Ideal(f_{1}, …, f_{m})

and

d = max{deg(f_{i}) : i = 1, …, m}.

So I has the decomposition (§4)

I = S_{1} ⊕ S_{2} ⊕ ⋯ ⊕ S_{m}

where S_{1} = Ideal(f_{1}) and for i = 2, …, m,

I_{i} = Ideal(f_{1}, …, f_{i−1}), S_{i} = f_{i} · NF(I_{i}: f_{i}).

We describe exact cone decompositions D_{i} for S_{i}: we may choose D_{1} = {S_{1}}. For i = 2, …, m, we already know how to obtain an exact decomposition D̂_{i} of NF(I_{i}: f_{i}). Then

D_{i}:={f_{i}C : C ∈ D̂_{i}}

is an exact decomposition for S_{i}. Hence, mindeg(D_{i}^{+}) = deg f_{i} since we may assume mindeg(D̂_{i}^{+}) = 0. Let D be the result of applying the “exact conversion” procedure to the set

D_{2} ∪ D_{3} ∪ ⋯ ∪ D_{m}.

Note that the cones in D have the form Cone(f, Y) where f are no longer power products. We claim that

mindeg(D^{+}) ≤ d.  (18)

Before the exact conversion procedure, this is clearly true. In each step of the conversion, we replacement a violating cone C by its “complete shift decomposition”. If this is a violation of type (I), it will not affect mindeg(D^{+}). In case of a violation of type (II) or type (III), then deg(C) < d, and the replacement cones have degrees deg(C) + 1. Again the new mindeg(D^{+}) is bounded by d. This proves (18). It is easy to modify D so that we have equality in equation (18). We will assume this in the following.

The above decomposition applies for any ideal. But in the rest of the section, we assume f_{1}, …, f_{m} are homogeneous polynomials. Then D is an exact cone decomposition of some homogeneous set T ⊆ I. The corresponding Hilbert polynomial of T has the Macaulay form (cf. equation (12))

Φ_{T} (z) = \binom{z − d + n}{n} − 1 − ∑_{i=1}^{n} \binom{z − a_{i} + i − 1}{i}

§7. Bounding the Macaulay constants  Lecture XIII  Page 22

for suitable Macaulay constants

a_{0} ≥ a_{1} ≥ ⋯ ≥ a_{n} ≥ a_{n+1} = d.  (19)

In fact we claim that

a_{0} = a_{1}.  (20)

This claim amounts to saying that if C ∈ D is zero-dimensional then there exists C′ ∈ D with dim C′ > 0 and deg C′ ≥ deg C. This property holds vacuously for each D_{i} (i = 1, …, m) since D_{i} has no zero-dimensional cones. Next note that the conversion procedure applied to D_{1} ∪ ⋯ ∪ D_{m} preserves this property because for each zero-dimensional cone C that the procedure introduces, it also produces a cone C′ of positive dimension with deg C′ = deg C.

We have freedom in choosing the polynomial f_{1} for forming S_{1}, so we may assume deg f_{1} = d. Since I = S_{1} ⊕ T, its Hilbert polynomial can now be written as

Φ_{I}(z) = Φ_{S_{1}}(z) + Φ_{T} (z)
= \binom{z − d + n − 1}{n − 1} + \binom{z − d + n}{n} − 1 − ∑_{i=1}^{n} \binom{z − a_{i} + i − 1}{i}.  (21)

Exercises

Exercise 6.1: (i) Let I = Ideal(XY^{2}Z, X^{2}Y Z^{2}). Give an exact cone decomposition of I, and determine its Macaulay constants, and Hilbert function. (ii) Repeat part (i) for an ideal I that is generated by linear polynomials (d = 1). □

§7. Bounding the Macaulay constants

We now have exact decompositions for I = (f_{1}, …, f_{m}) and for NF(I), where I is homogeneous. Let the Macaulay constants for the exact decomposition of NF(I) be

b_{0} ≥ b_{1} ≥ ⋯ ≥ b_{n} ≥ b_{n+1} = 0

with

Φ_{NF(I)}(z) = \binom{z + n}{n} − 1 − ∑_{i=1}^{n} \binom{z − b_{i} + i − 1}{i}

We also have the expression for Φ_{I}(z) with associated constants a_{0}, …, a_{n+1} (equations (21) and (19)). Therefore,

\binom{z + n − 1}{n − 1} = Φ_{I}(z) + Φ_{NF(I)}(z)
= \binom{z − d + n − 1}{n − 1} + \binom{z − d + n}{n} + \binom{z + n}{n}

−2 − ∑_{i=1}^{n} \{\binom{z − a_{i} + i − 1}{i} + \binom{z − b_{i} + i − 1}{i}\} .  (22)

We now apply the “backwards difference operator” ∇, defined by its effect on real functions F (z),

∇F (z) := F (z) − F (z − 1).

For i ≥ 0, let ∇^{0}F = F and ∇^{i+1}F = ∇(∇^{i}F). It is easy to verify the identity ∇\binom{z−k}{n} = \binom{z−k−1}{n−1}. Applied i times,

∇^{i}\binom{z − k}{n} = \binom{z − k − i}{n − i}.

This formula applies for all values of i, recalling that by definition of the binomial coefficients,

\binom{z}{k} = \{ \begin{matrix}1 & if k = 0 \\ 0 & if k < 0. \end{matrix}

Clearly, ∇(F + G) = (∇F) + (∇G), and ∇C = 0 iff C is a constant. Applying ∇^{j} (j ≥ 0) to both sides of equation (22),

\binom{z + n − j − 1}{n − j − 1} = \binom{z − d + n − j − 1}{n − j − 1} + \binom{z − d + n − j}{n − j} + \binom{z + n − j}{n − j} − 2δ(j, 0)

− ∑_{i=j}^{n} \{\binom{z − a_{i} + i − j − 1}{i − j} + \binom{z − b_{i} + i − j − 1}{i − j}\} .  (23)

Here

δ(x, y) = \{ \begin{matrix}1 & if x = y, \\ 0 & else, \end{matrix}

denotes the Kronecker delta function. Setting z = 0 and using the identity

\binom{k}{n} = (−1)^{n}\binom{n − k − 1}{n}, k < 0,

equation (23) becomes

1 = (−1)^{n−j−1}\binom{d − 1}{n − j − 1} + (−1)^{n−j}\binom{d − 1}{n − j} + 1 − 2δ(j, 0) − ∑_{i=j}^{n}(−1)^{i−j} \{\binom{a_{i}}{i − j} + \binom{b_{i}}{i − j}\} .

(24)

For j = n − 1, this reduces to

a_{n} + b_{n} = d.

But we know a_{n} ≥ d, b_{n} ≥ 0. Hence a_{n} = d, b_{n} = 0. It is convenient to define

c_{j} = a_{j} + b_{j}, j = 0, …, n + 1.

Thus we have just shown c_{n} = d. Next we simplify equation (24) by extracting the terms \binom{a_{i}}{i−j}+\binom{b_{i}}{i−j} in the summation corresponding to i = j, i = j + 1 and i = n. These three terms (respectively) are

2, −c_{j+1}, (−1)^{n−j}\binom{d}{n − j}.

This gives us

c_{j+1} = 2(1−δ(j, 0))+2(−1)^{n−j}\binom{d − 1}{n − j − 1}+ ∑_{i=j+2}^{n−1}(−1)^{i−j} \{\binom{a_{i}}{i − j} + \binom{b_{i}}{i − j}\} , (j = 0, …, n−2).

(25)

For j = n − 2, this yields

c_{n−1} = 2d.

We now use the inequality

\binom{a_{i}}{k} + \binom{b_{i}}{k} ≤ \binom{c_{i}}{k}

(this is obvious from the combinatorial interpretation). Note that equation (25) (for j ≤ n − 3) contains the term

2 + (−1)^{n−j} \{2\binom{d − 1}{n − j − 1} − \binom{a_{n−1}}{n − j − 1} − \binom{b_{n−1}}{n − j − 1}\} .

If j = n − 3, this expression is bounded by 2 − 2\binom{d−1}{2} + \binom{2d}{2} = d(d + 2). From (25), we get

c_{n−2} ≤ d(d + 2).

But to get a general bound, proceed as follows. Extracting the term corresponding to i = j+2 in (25), and discarding the negative term corresponding to i = j +3 and also discarding the Kronecker-delta,

c_{j+1} ≤ 2 + 2\binom{d − 1}{n − j − 1} + \binom{c_{j+2}}{2} + ∑_{i=j+4}^{n−1} \binom{c_{i}}{i − j}.  (26)

In the following, we assume d ≥ 2 (see §6, Exercise, for d = 1).

Lemma 15 For d ≥ 2,

c_{j} < B_{j} := d^{2^{n−j}}, j = 1, …, n − 2.

Proof. The result is true for j = n − 2. We may also note that c_{n−1} ≤ B_{n−1} = d^{2}. So let j ≤ n − 3. For i = j + 4, …, n − 1, we have i − j ≤ 2^{i−j−2} and so

\binom{B_{i}}{i − j} < \frac{B_{i}^{i−j}}{(i − j)!} ≤ \frac{B_{i}^{2^{i−j−2}}}{(i − j)!} = \frac{B_{j+2}}{(i − j)!}.

Also, check that 2 + 2\binom{d−1}{n−j−1} ≤ 2B_{j+2}. Inductively, equation (26) yields

c_{j+1} ≤ 2B_{j+2} + \binom{B_{j+2}}{2} + ∑_{i=j+4}^{n−1} \binom{B_{i}}{i − j}

≤ 2B_{j+2} + \frac{B_{j+1}}{2} − \frac{B_{j+2}}{2} + ∑_{i≥j+4} \frac{B_{j+2}}{(i − j)!}

≤ \frac{B_{j+1}}{2} + B_{j+2} \{\frac{3}{2} + ∑_{i≥4} \frac{1}{i!}\}

< \frac{B_{j+1}}{2} + 2B_{j+2}
≤ B_{j+1}.

Q.E.D.

In particular, we have a_{1} + b_{1} = c_{1} ≤ B_{1} = d^{2^{n−1}}. We already know a_{0} = a_{1}. The remaining constant to be bounded is b_{0}.

Lemma 16

b_{0} ≤ max{a_{1}, b_{1}}.

§8. Term Rewriting Systems  Lecture XIII  Page 25

Proof. Let D be the cone decomposition for K[X], constructed relative to I as in the foregoing. The Hilbert function of K[X] can be expressed as

\{∑_{i≥0} W_{0,i}δ(z, i)\} + \{∑_{d=0}^{n} ∑_{i≥0} W_{d,i} · \binom{z − i + d − 1}{d − 1}_{i}\}

where W_{d,i} is the number of d-dimensional cones of degree i in D. Here, we attach a subscript “i” on the binomial coefficient \binom{z−i+d−1}{d−1}_{i} to indicate that the expression must be equated to zero for z < i. For z ≥ max{a_{1}, b_{1}}, these subscripts can be removed, giving

\{∑_{i≥0} W_{0,i}δ(z, i)\} + \{∑_{d=0}^{n} ∑_{i≥0} W_{d,i} · \binom{z − i + d − 1}{d − 1}\} = \binom{z + n − 1}{n − 1}.  (27)

Hence, for z ≥ max{a_{1}, b_{1}}, equation (27) shows that the expression ∑_{i≥0} W_{0,i}δ(z, i) is equal to a sum of binomial coefficients, and so is equal to some integer polynomial p(z). But for z ≥ max{a_{0}, b_{0}} (≥ max{a_{1}, b_{1}}) we know that p(z) = 0, so p(z) is the zero polynomial. This implies that b_{0} ≤ max{a_{1}, b_{1}}. Q.E.D.

To obtain our main result about general polynomials, we need to first homogenize the input polynomials (§3).

Theorem 17 Let f_{1}, …, f_{m} ⊆ K[X_{1}, …, X_{n}] be polynomials of degree at most d. Relative any admissible order ≤_{A}, there is a Gröbner basis G for I = Ideal(f_{1}, …, f_{m}) of degree at most d^{2^{n}}. In

other words,

G(n, d) ≤ d^{2^{n}}.

Proof. First we homogenize each f_{i} to F_{i} ∈ K[X_{0}, …, X_{n}] where X_{0} is a homogenizing variable. Let G be a reduced basis for J = Ideal(F_{1}, …, F_{m}) relative to ≤_{A}^{∧} (§3). We want an upper bound

on B = max{deg(g) : g ∈ G}. The set F = {hterm(f) : f ∈ G} is a reduced monomial basis for the head ideal H = Head(G). Applying the exact cone decomposition algorithm to (1, X, F), we obtain an exact decomposition for NF(H). But G is a Gröbner basis means NF(H) = NF(J). We similarly obtain an exact decomposition for J. As above, the associated Macaulay constants are b_{0}, …, b_{n+2} and a_{0}, …, a_{n+2}, respectively. (Note that there are n + 3 Macaulay constants for each decomposition since we have n + 1 variables.) By lemma 13 we know that B ≤ 1 + b_{0}. But

b_{0} ≤ max{a_{1}, b_{1}} ≤ c_{1} ≤ d^{2^{n}}.

Finally, dehomogenizing the polynomials in G yields a Gröbner basis for I (lemma 3). Q.E.D.

Exercises

Exercise 7.1: Obtain the sharpest bound you can on the above constants a_{j}, b_{j}. For instance, c_{n−3} ≤ \binom{2d}{3} + \binom{d^{2}+d}{2}. In general,

c_{j} ≤ 2 (\frac{d^{2}}{2} + d)^{2^{n−j−1}} .

□

§8. Term Rewriting Systems

The rest of this lecture proves a lower bound on G(n, d), I(n, d) and S(n, d). We now assume the coefficient field K is ℚ. The underlying set of variables will now be denoted Σ = {X_{1}, …, X_{n}}.

The context for the lower bound construction comes from the term-rewriting literature. We had a brief encounter with term-rewriting systems in §XII.3. Such systems normally deal with syntactic objects (“free terms”) and their behavior under a set of transformations. These transformations are governed by finitistic or local rules. For example, let the terms be words over an alphabet Σ. A simple rule might be the transposition of two adjacent variables occurring in a word: … XY … → … Y X . . .. This particular rule amounts to saying that the variables are commutative. If the rules are reversible, then this defines an equivalence relation among the terms. Questions of recognizing equivalence is an important issue, and, as in Gröbner bases, this can be studied via normal forms. Indeed, many general questions of interest in this subject are already reflected in our study of Gröbner bases: termination for a set of rules, normal forms, Church-Rosser property.

We will now study polynomial transformations from this “syntactic” view-point. In fact, the lower bound results use a very special class of polynomials which we call Thue polynomials, and the corresponding term-rewriting systems are called Thue systems. Many concepts of term-rewriting systems have analogues in polynomial rings. In such cases, it is a simple matter of introducing the corresponding vocabulary. Generally, we will try to adopt the new vocabulary.

Let Σ = {X_{1}, …, X_{n}} be a set of variables. In term-rewriting, Σ is a called alphabet and each X_{i} ∈ Σ is a commutative variable. Although commutativity of variables is the normal assumption in polynomial rings, the opposite assumption is more common in term-rewriting. In the following definitions, we put the qualification “commutative” in parenthesis when defining the appropriate concepts. However, we normally drop the ‘commutative’ qualifications in our usage, as this will be understood.

The set of power products PP(Σ) is also called the free commutative monoid generated by Σ. A power product w ∈ PP(Σ) is also called a (commutative) word. Because of commutativity, ww′ and w′w refers to the same word. Thus the empty word corresponds to “1”. If Γ ⊆ Σ and w, v ∈ PP(Σ), then deg_{Γ}(w) denotes the degree of w in the variables of Γ. For instance, we say w is linear in Γ if deg_{Γ}(w) = 1. If Γ = Σ, then deg_{Γ}(w) is the usual degree, deg(w). We say w is a subword of w′ if w|w′ (w divides w′).

A (commutative) semi-Thue system over Σ is a pair (S, Σ) where S is a finite set of pairs in PP(Σ). Each pair (α, β) ∈ S is called a rule. We call β and α (respectively) the precondition and postcondition of the rule (α, β). The reverse of a rule (α, β) is the rule (β, α). We say S is a (commutative) Thue system if (α, β) is in S implies its reverse (β, α) is in S. The degree of a rule (α, β) is max{deg(α), deg(β)}, and the degree of S is the maximum degree of its rules.

Derivations. Given words v, w, we write

v → w (mod S)

if for some (α, β) ∈ S and γ ∈ PP(Σ), we have v = γα and w = γβ. We also call “v → w” a transition (of S). The reflexive, transitive closure of → (mod S) is denoted ⟶_{∗} (mod S). A sequence

D = (w_{1}, w_{2}, …, w_{k})

(also written, D : w_{1} → ⋯ → w_{k}, or, D : w_{1} ⟶_{∗} w_{k}) where w_{i} ∈ PP(Σ) (k ≥ 1) is called a derivation of S from w_{1} to w_{k} if w_{i} → w_{i+1}(mod S) for i = 1, …, k − 1. The derivation has a repetition if w_{i} = w_{j} for some 1 ≤ i < j ≤ k; this instance of repetition is trivial if i = j − 2. A derivation is repetition-free if it has no repetition; it is simple if it has no trivial repetition. Thus simple derivations are allowed to have non-trivial repetitions. Clearly only simple derivations are of interest, and this is often implicit in our discussion. A repetition-free derivation D : w ⟶_{∗} w′ is said to be unique if it is the only repetition-free derivation from w to w′. We say D is strongly unique if for all repetition-free derivations D′ : w ⟶_{∗} u, if w′ | u then u = w′ and D′ = D. A word w is recursive if there is a non-trivial (i.e., at least one transition step) simple derivation from w to some w′ such that w | w′; otherwise it is non-recursive. Note that possibly w = w′ here.

We are often interested in derivations of a Thue system S from some distinguished word w_{0}. We call w_{0} the initial assertion of S and words derivable from the initial assertion are called assertions of S. (This terminology is from Post [10].)

Main Task. The main task before us (following [8]) involves constructing a Thue system S_{n,d} that “counts to d^{2^{n}}” in the following sense: there are distinguished variables Q_{0}, Q_{∞}, A ∈ Σ such that if D is any simple derivation

D : Q_{0} ⟶_{∗} Q_{∞}w (mod S_{n,d})

then w is equal to A^{d^{2^{n}}}. Here A is called an “accumulator” variable since it acts as a unary counter. Moreover, the derivation D is strongly unique. For the lower bound application, this construction needs to be “efficient” in the sense that S_{n,d} involves only O(n) variables and has degree O(n + d).

Connection to Polynomial Ideals. Such a construction has implications for polynomials because we can view each rule (α, β) as the polynomial α − β. Let us call a polynomial of this form a Thue polynomial and an ideal generated by a set of Thue polynomials is called a Thue ideal [11, 12]. Let

F_{S} :={α − β : (α, β) ∈ S}  (28)

be the set of Thue polynomials corresponding to rules of S. For w, w′ ∈ PP(Σ), notice that if w ⟶ w′(mod S) then w = αγ and w′ = βγ for some rule (α, β) ∈ S. Then w − w′ ∈ Ideal(S). This argument can be repeated for derivations of any length, giving:

Lemma 18 If w ⟶_{∗} w′(mod S) then w − w′ ∈ Ideal(F_{S}).

Let us now show a partial converse. For this, we need to assume that the field of coefficients is K = ℚ. For f ∈ K[Σ], define the support of f be the set support(f) ⊆ PP(Σ) comprising those words whose coefficients in f are non-zero.

Lemma 19 (Mayr-Meyer) Suppose w − w′ ∈ Ideal(F_{S}) where the ideal is generated over R =

ℚ[X_{1}, …, X_{n}] then w ⟶_{∗} w′(mod S).

Proof. Let w − w′ = ∑_{i=1}^{m} a_{i}f_{i} where a_{i} ∈ R and f_{i} ∈ F_{S}. We may assume that each a_{i} is a monomial. By multiplying both sides by a suitable positive integer d, we obtain an expression

d(w − w′) = ∑_{i=1}^{m} b_{i}f_{i}

§9. A Quadratic Counter  Lecture XIII  Page 28

where each b_{i} is now a power product. We want to construct a derivation

D : w = w_{0} ⟶ w_{1} ⟶ ⋯ ⟶ w_{k} = w′(mod S)

for some k ≤ m. This is done by induction on m. It is easiest to see the argument graphically. Let us construct a digraph G on the vertex set V = ∪_{i=1}^{m}support(b_{i}f_{i}), where we introduce an edge from u to v whenever b_{i}f_{i} = u − v (i = 1, …, m). Note that G may have multiple edges (i.e., there may be more than one edge going from any vertex u to any v). Let d_{G}(u) be equal to the number of outgoing edges from u minus the number of incoming edges into u. Clearly

d_{G}(u) = \{ \begin{matrix}0 & if u ∉ \{w, w′\}, \\ d & if u = w, \\ −d & if u = w′. \end{matrix}

It easily follows by induction on m that there exists a path from w to w′. This is immediate if m = 1. Otherwise, assume that we have constructed a path (w_{0}, w_{1}, …, w_{i}) where w_{i} ≠ w′ (i ≥ 0). Moreover, we have removed the edges of this path from G (so G now has m − i edges). Then it is easy to see that there remains an outgoing edge from w_{i}, and so this construction can proceed. We leave the formal argument to the reader. But any path from w to w′ corresponds to a derivation from w to w′. Q.E.D.

Exercises

Exercise 8.1: Let Σ = {Q_{0}, A, B, Q_{1}}. Construct a Thue system S such that for any w ∈ PP(A, B), we have Q_{0}w ⟶_{∗} Q_{1}A^{m}B^{n}(mod S) where m = deg_{A}(w) and n = deg_{B}(w). Moreover, this derivation is strongly unique. S may use a larger alphabet than Σ. □

Exercise 8.2: The reduced Gröbner basis (with respect to any admissible ordering) of a Thue ideal is comprised of Thue polynomials. HINT: Analyze Buchberger’s algorithm and note that the S-polynomial of two Thue polynomials is a Thue polynomial. □

§9. A Quadratic Counter

We construct a Thue system S_{0} that can be viewed as a “counter”.

Constants. Throughout this construction, we fix the integers n ≥ 1 and d ≥ 2. We also define e_{d}(k) = e(k) := d^{2^{k}} for all k ≥ 0. Observe that e(k + 1) = e(k)^{2}.

Variables. There are two types of variables.

1. Accumulator variables: A_{k}, B_{k},  (k = 0, 1, …, n)
2. Flag variables:  F_{k}[color] (k = 1, …, n; color ∈ {inc, dec, pass}).

Let Σ_{0} denote this set of 5n+2 variables. Each variable belongs to some level k (its subscript) which is an integer between 0 and n. The colors are read ‘increment’, ‘decrement’ and ‘pass’, respectively. We are mainly interested in commutative words of the following form:

w = A_{0}^{m_{0}}B_{0}^{n_{0}} ∏_{k=1}^{n} A_{k}^{m_{k}}B_{k}^{n_{k}}F_{k}[color_{k}]

where m_{0}, n_{0}, m_{k}, n_{k} ≥ 0 and m_{0} + n_{0} = d. We call such words well-formed.

So a well-formed word is linear in {F_{k}[inc], F_{k}[dec], F_{k}[pass]} for each k = 1, …, n.

For 1 ≤ k ≤ n and k ≤ ℓ ≤ n + 1, we use the abbreviation:

F_{k,ℓ}[color] ≡ ∏_{i=k}^{ℓ−1} F_{i}[color]

Thus F_{k,k}[color] = 1. The following well-formed word is designated the initial assertion

w_{0} := A_{0}^{d}F_{1,n+1}[inc].  (29)

We now present the rules, which naturally fall under two groups:

Start Rules. (k = 1, 2, …, n)

(S1)_{k} A_{0}  F_{1,k}[pass]F_{k}[inc] ; \overline{}B_{0}A_{k}^{d}  (“increment rule”)
(S2)_{k} A_{0}B_{k}^{d} F_{1,k}[pass]F_{k}[dec] ; \overline{}B_{0}  (“decrement rule”)

Finish Rules. (k = 1, 2, …, n − 1)

(F1)_{k} B_{0}^{d}F_{1,k}[dec]F_{k}[inc]  \overline{}A_{0}^{d}F_{1,k}[inc]F_{k}[pass]  (“inc ⇒ pass rule”)
(F2)_{k} B_{0}^{d}F_{1,k}[dec]A_{k}  F_{k}[pass] ; \overline{}A_{0}^{d}F_{1,k}[inc]B_{k}  (“pass ⇒ pass rule”)
(F3)_{k} B_{0}^{d}F_{1,k}[dec]F_{k}[pass]A_{k}  \overline{}A_{0}^{d}F_{1,k}[inc]F_{k}[dec]B_{k}  (“pass ⇒ dec rule”)

Let (S_{0}, Σ_{0}) denote the Thue system corresponding to these rules.

Remark: We write the rule (α, β) as α → β above to be suggestive of the “forward” direction of applying the rules. But one must remember that we are describing a Thue system, so the reverse rule β → α is also implied. A derivation that only uses the forward (resp. reverse) rules will be called a forward (resp. reverse) derivation; otherwise the derivation is mixed. Furthermore, a rule of the form αγ → βγ where GCD(α, β) = 1 may be written as

α ⟶ β^{γ}

as in the rules^{3} (S1) and (S2). Since γ is unchanged, we call it the “catalyst” for the rule. In this and the next section, all transitions → , →^{∗} are understood to be (mod S_{0}).

Example: We illustrate a derivation of S_{0}. Note that any word w ∈ PP(Σ_{0}) can be expressed as w = w_{0}w_{1} ⋯ w_{n} where w_{k} (k = 0, …, n) is the subword of w comprising all variables of level k. In the following derivation, we will represent w by stacking w_{k−1} above w_{k}. Here d = 2, n = 3.

w_{0} = ( \begin{matrix}A_{0}^{2} \\ F_{1}[inc] \\ F_{2}[inc] \\ F_{3}[inc] \end{matrix} ) rule(S1)_{1} ; \overline{}( \begin{matrix}A_{0}B_{0} \\ F_{1}[inc]A_{1}^{2} \\ F_{2}[inc] \\ F_{3}[inc] \end{matrix} ) rule(S1)_{1} ; \overline{}

3By a harmless abuse of language, we call, for instance, (S1) a ‘rule’ even though it is really a family of n rules parameterized by k.

[figure: ( \begin{matrix}B_{0}^{2} \\ F_{1}[inc]A_{1}^{4} \\ F_{2}[inc] \\ F_{3}[inc] \end{matrix} ); rule(F1)_{1}; ( \begin{matrix}A_{0}^{2} \\ F_{1}[pass]A_{1}^{4} \\ F_{2}[inc] \\ F_{3}[inc] \end{matrix} ); rule(S1)_{1}; ( \begin{matrix}A_{0}B_{0} \\ F_{1}[pass]A_{1}^{4} \\ F_{2}[inc]A_{2}^{2} \\ F_{3}[inc] \end{matrix} )]

\overline{}⋯ \overline{}( \begin{matrix}B_{0}^{2} \\ F_{1}[dec] \\ F_{2}[dec] \\ F_{3}[inc]A_{3}^{256} \end{matrix} ) .

The reader should try to see how to eventually derive the last indicated word.

Let us briefly comment on the rules: the forward start rules at level k are all dependent on the catalyst F_{1,k}[pass] and in each case converts an occurrence of A_{0} to B_{0}. Rule (S1), in the presense of the catalyst F_{k}[inc], increments the accumulator A_{k} by d: in this, we see that the pass flag F_{i}[pass] at levels i = 1 to i = k − 1 each signals that the accumulator A_{i} should be ignored. Rule (S2) is the counterpart of (S1) where the flag F_{k}[dec] signals the decrementing of accumulator A_{k} by d.

We similarly note some salient features of the forward finish rules: in each case, the subword B_{0}^{d} transforms to A_{0}^{d}. Furthermore, the initial block of “decrement flags” F_{1,k}[dec] is converted to F_{1,k}[inc]. Hence differences among the finish rules hinge on the flag at level k: in case of (F1), the flag is F_{k}[inc] and we convert it to F_{k}[pass]. In the case of (F2), the flag F_{k}[pass] acts only as a catalyst for converting an A_{k} into a B_{k}. In (F3), we convert F_{k}[pass] to F_{k}[dec], and at the same time convert an A_{k} to a B_{k}. Thus the flag variable at level k is transformed by these rules in a cyclic fashion

                           inc ⇒ pass ⇒ dec ⇒ inc ⇒ · · · .

More precisely: in any forward derivation, the flag variable at each level transforms cyclically as indicated.

Clearly the rules preserve well-formedness of words. In particular, all assertions are well-formed. To see these rules in action, it is best to follow the proof of the following lemma:

Lemma 20 (Standard Derivation) Let 1 ≤ k ≤ ℓ ≤ n and w be any commutative word.

(a)_{k,ℓ} (Increment) Let u_{1} = wA_{0}^{d}F_{1,k}[inc]F_{k,ℓ}[pass]F_{ℓ}[inc]. Then there is a forward derivation

u_{1} →^{∗} u′_{1} where

u′_{1} = wB_{0}^{d}A_{ℓ}^{e(k)}F_{1,k}[dec]F_{k,ℓ}[pass]F_{ℓ}[inc].

The first and last rules in this derivation are start rules.

(b)_{k,ℓ} (Decrement) Let v_{1} = wA_{0}^{d}B_{ℓ}^{e(k)}F_{1,k}[inc]F_{k,ℓ}[pass]F_{ℓ}[dec]. Then there is a forward deriva-

tion v_{1} →^{∗} v′_{1} where

v′_{1} = wB_{0}^{d}F_{1,k}[dec]F_{k,ℓ}[pass]F_{ℓ}[dec].

The first and last rules in this derivation are start rules.

Proof. Let k = 1. Part (a) consists of d applications of rule (S1)_{ℓ}, and part (b) consists of d applications of rule (S2)_{ℓ}. Now assume k > 1.

(a)_{k,ℓ}

wA_{0}^{d}F_{1,k}[inc]F_{k,ℓ}[pass]F_{ℓ}[inc]  = u_{1}

ind(a)_{k−1,k−1} ; \overline{} ; ∗ wB_{0}^{d}A_{k−1}^{e(k−1)}F_{1,k−1}[dec]F_{k−1}[inc]F_{k,ℓ}[pass]F_{ℓ}[inc]  = u_{2}
(F1) \overline{}wA_{0}^{d}A_{k−1}^{e(k−1)}F_{1,k−1}[inc]F_{k−1}[pass]F_{k,ℓ}[pass]F_{ℓ}[inc]  = u_{3}

ind(a)_{k−1,ℓ} ; \overline{} ; ∗  wB_{0}^{d}A_{k−1}^{e(k−1)}A_{ℓ}^{e(k−1)}F_{1,k−1}[dec]F_{k−1,ℓ}[pass]F_{ℓ}[inc]  = u_{4}
(F2) \overline{}wA_{0}^{d}A_{k−1}^{e(k−1)−1}B_{k−1}A_{ℓ}^{e(k−1)}F_{1,k−1}[inc]F_{k−1,ℓ}[pass]F_{ℓ}[inc] = u_{5}

ind(a)_{k−1,ℓ} ; \overline{} ; ∗  wB_{0}^{d}A_{k−1}^{e(k−1)−1}B_{k−1}A_{ℓ}^{2e(k−1)}F_{1,k−1}[dec]F_{k−1,ℓ}[pass]F_{ℓ}[inc] = u_{6}

⋮  (by e(k − 1) − 2 more applications of last 2 steps)
ind(a)_{k−1,ℓ} ; \overline{} ; ∗  wB_{0}^{d}A_{k−1}B_{k−1}^{e(k−1)−1}A_{ℓ}^{e(k)}F_{1,k−1}[dec]F_{k−1,ℓ}[pass]F_{ℓ}[inc]  = u_{7}
(F3) \overline{}wA_{0}^{d}B_{k−1}^{e(k−1)}A_{ℓ}^{e(k)}F_{1,k−1}[inc]F_{k−1}[dec]F_{k,ℓ}[pass]F_{ℓ}[inc]  = u_{8}

ind(b)_{k−1,k−1} ; \overline{} ; ∗ wB_{0}^{d}A_{ℓ}^{e(k)}F_{1,k−1}[dec]F_{k−1}[dec]F_{k,ℓ}[pass]F_{ℓ}[inc]  = u′_{1}

The inductive invocations of the lemma are labeled “ind(a)” or “ind(b)”.

(b)_{k,ℓ}: We omit the similar derivation. The only difference is that all the inductive invocations of “ind(a)_{k−1,ℓ}” are replaced by “ind(b)_{k−1,ℓ}”. Q.E.D.

We shall call any prefix of the derivations (a) or (b) in the proof of this lemma a standard derivation (at level k). To understand how the system may deviate from standard derivations, we consider the ‘ambiguities’ that arise when the precondition of a rule R subsumes the precondition of another rule R′. This would mean that whenever R is applicable, so is R′, causing non-determinism in derivations. In general, non-determinism arises even when the rules are not ambiguous in this sense. But in S_{0}, such ambiguities are the only cause of deviation from our intended or standard derivations. Of course, we must consider the reverse rules in describing ambiguities.

Forward Ambiguities Among the forward rules, the only source of ambiguity arises from the fact that both (F2) and (F3) have the same preconditions.

Reverse Ambiguities Among the reverse rules, the only ambiguity arises because the precondition of reverse (F2) subsumes the precondition of reverse (F1).

Mixed Ambiguities Finally, consider ambiguities involving a forward and a reverse rule. The problem here is essentially caused by the case k = 1. Thus the precondition for rule (S1)_{1} is subsumed by the postcondition of the finish rules (Fm)_{ℓ} (for m = 1, 2, 3 and ℓ ≥ 2). Similarly, the postcondition of rule (S2)_{1} is subsumed by the precondition of the finish rules (Fm)_{ℓ} (for m = 1, 2, 3 and ℓ ≥ 2). It turns out that these mixed ambiguities are harmless for our purposes.^{4}

4The fact that the postcondition of (Fm)_{ℓ} subsumes the precondition of (S1)_{1} means that following an application of (Fm)_{ℓ}, we can immediately apply rule (S1)_{1}. But the reader may check that in standard derivations, we always apply rule (S1)_{1} right after rule (Fm)_{ℓ}! Similarly, that the precondition of rule (Fm)_{ℓ} subsumes the postcondition

§10. Uniqueness Property  Lecture XIII  Page 32

The following properties of S_{0} may now be noted. Let w be any well-formed word.

• Rule (F2) is applicable to w if and only if rule (F3) is applicable to w. If both are applicable, then no other rules apply; if both are non-applicable, then there is at most one forward rule applicable to w.

• If reverse (F2) is applicable to w, then reverse (F1) (and no other reverse rules) is applicable to w. If reverse (F2) is not applicable, then there is at most one reverse rule applicable to w.

These properties will be assumed when we prove the Basic Lemma next.

§10. Uniqueness Property

If we apply lemma 20(a) to the initial assertion w_{0} with the parameters k = ℓ = n, we get the word

w_{∞}:= B_{0}^{d}A_{n}^{e(n)}F_{1,n}[dec]F_{n}[inc].  (30)

We call w_{∞} the final assertion. The next lemma shows that this derivation is unique.

For any word w, define the level of w to be the smallest k = 0, 1, …, n if Γ :={A_{k}, B_{k}, F_{k}[inc], F_{k}[pass], F_{k}[dec]} then deg_{Γ}(w) > 0.

Lemma 21 (Basic Lemma) Let 1 ≤ k ≤ ℓ ≤ n and let w_{1}, w′_{1} be commutative words of level at least k and the following are well-formed words:

u_{1} := w_{1}A_{0}^{d}F_{1,k}[inc], u′_{1} := w′_{1}B_{0}^{d}F_{1,k}[dec].

(a)_{k,ℓ} (Forward Derivation) Let

D_{1} : u_{1} →^{∗} u′_{1}

be a simple derivation such that the first transition in D_{1} is a forward one and u′_{1} is the only word in D_{1} divisible by B_{0}^{d}F_{1,k}[dec]. Then D_{1} is unique and a standard derivation, and moreover: (a.1)_{k,ℓ} If F_{k,ℓ}[pass]F_{ℓ}[inc] | w_{1} then w_{1}A_{ℓ}^{e(k)} = w′_{1}, i.e., the accumulator A_{ℓ} has increased by e(k).

(a.2)_{k,ℓ} If F_{k,ℓ}[pass]F_{ℓ}[dec] | w_{1} then w_{1} = w′_{1}B_{ℓ}^{e(k)}, i.e., the accumulator B_{ℓ} has decreased by e(k).

(b)_{k,ℓ} (Backward Derivation) Let

D_{2} : u′_{1} →^{∗} u_{1}

be a simple derivation such that the first transition in D_{2} is a reverse one and u_{1} is the only word in D_{2} divisible by A_{0}^{d}F_{1,k}[inc]. Then D_{2} is unique and the reverse of a standard derivation, and moreover:

(b.1)_{k,ℓ} If F_{k,ℓ}[pass]F_{ℓ}[inc] | w′_{1} then w′_{1} = w_{1}A_{ℓ}^{e(k)}, i.e., the accumulator A_{ℓ} has decreased by e(k).

(b.2)_{k,ℓ} If F_{k,ℓ}[pass]F_{ℓ}[dec] | w′_{1} then w′_{1}A_{ℓ}^{e(k)} = w_{1}, i.e., the accumulator B_{ℓ} has increased by e(k).

of (S2)_{1} means that, whenever rule (Fm)_{ℓ} is applicable, so is the reverse of (S2)_{1}. But in standard derivations, we only apply rule (Fm)_{ℓ} after an application of rule (S2)_{1}. Hence it is impossible to deviate from standard behavior using this ambiguity: it would mean that we apply reverse (S2)_{1} instead of (Fm)_{ℓ}. But this would give a non-simple derivation.

§11. Lower Bounds  Lecture XIII  Page 33

We defer the proof to an appendix. The following shows that S_{0} is (with some simple modifications) counting up to the double-exponential number e(n).

Corollary 22 If D : w_{0} →^{∗} w and B_{0}^{d}F_{1,n}[dec][inc] | w then D is unique and w = w_{∞}. Hence, the standard derivation w_{0} →^{∗} w_{∞} is strongly unique.

Proof. Only a forward rule can be applied to w_{0}, and there is a first word x in D such that B_{0}^{d}F_{1,n}[dec]F_{n}[inc] | x. By the basic lemma (a)_{1,n}, x has the form of the final assertion,

w_{∞} = B_{0}^{d}A_{n}^{e(n)}F_{1,n}[dec]F_{n}[inc].

Moreover, the derivation cannot be extended from x (recall that the finish rules does not include the case k = n). So x is indeed equal to w. The uniqueness of D follows from the uniqueness of standard derivations. Q.E.D.

Lemma 23 The initial assertion w_{0} = A_{0}^{d}F_{1,n+1}[inc] is non-recursive.

Again, the proof is technical and deferred to the appendix.

§11. Lower Bounds

Modified System S_{1}. Recall that S_{0} has a unique derivation from the initial assertion w_{0} (29) to the final assertion w_{∞} (30). Let us modify S_{0} to a new system S_{1} so that it has, instead, a unique derivation of the form:

Q_{0} ⟶_{∗} w_{∞} ⟶_{∗} Q_{∞}  (31)

where Q_{0} and Q_{∞} are new variables. Intuitively, the derivation from w_{∞} to Q_{∞} should be the reverse of the standard derivation. (So calling w_{∞} the “final assertion” is slightly misleading in this setting, but we stick to this terminology.)

More precisely, we first expand Σ_{0} to Σ_{1} by adding three new variables

Q_{0}, Q_{mid}, Q_{∞}.

We now treat Q_{0} as the initial assertion of S_{1}. Next, we augment the rules of S_{0} with three new rules.

Augmented Rules.

(S0) Q_{0}  \overline{}A_{0}F_{1,n+1}[inc] = w_{0}  (“initialization rule”)
(T0) 1  B_{0}^{d}F_{1,n}[dec]F_{n}[inc] ; \overline{}Q_{mid}  (“transition rule”)
(F0) Q_{mid}A_{0}^{d}F_{1,n+1}[inc]  \overline{}Q_{∞}  (“termination rule”)

Intended Derivation. We intend to use these rules as follows. The initialization rule (S0) simply converts Q_{0} to w_{0} in one step. Then the standard derivation takes w_{0} to w_{∞}. At this point, the only applicable rule that preserves simplicity is rule (T0), and this simply introduces the new variable Q_{mid}. At this point, the reverse standard derivation will take Q_{mid}w_{∞} back to Q_{mid}w_{0}. Now the final termination rule (F0) converts Q_{mid}w_{0} to Q_{∞}. To summarize:

Q_{0} ⟶^{(S0)} w_{0} ⟶_{∗}^{std} w_{∞} ⟶^{(T 0)} Q_{mid}w_{∞} ⟶_{∗}^{rstd} Q_{mid}w_{0} ⟶^{(F 0)} Q_{∞}.  (32)

It is clear that this derivation has all the properties we previously asserted for S_{0}:

Lemma 24 The derivation Q_{0} ⟶_{∗} Q_{∞} (mod S_{1}) is strongly unique. The initial assertion Q_{0} is non-recursive.

For any set G = \{g_{1}, …, g_{m}\} or sequence \overline{g} = (g_{1}, …, g_{m}) of polynomials, let deg(G) and deg(\overline{g}) be the maximum degree of a polynomial in G or \overline{g}. For instance, \overline{g} may represente a syzygy or a derivation.

Modified System S_{2}. We need to make one more modification. The degree of the rules of S_{1} can be as large as n + d + 2. We now modify them so that they are only d + O(1). Introduce n new “level” variables

L_{1}, …, L_{n}

and use these to simulate the rules of S_{1}. Thus the start rules (S0)-(S2) are now replaced by

Lower Lound on I(n, d).

Lemma 25 Ind The ideal membership problem in ℚ[X_{1}, …, X_{n}] has bound I(n, d) ≥ d^{2^{p}}, p ∼ n/5.

Proof. Let D_{∞} be the unique derivation of S_{1} from Q_{0} to Q_{∞}. Let F = {f_{1}, …, f_{m}} be the set of Thue polynomials corresponding to S_{1} and let f_{0} = Q_{0} − Q_{∞}. Then

deg(F) = d + n + 2,  deg(f_{0}) = 1,  deg(D_{∞}) ≥ e(n) + d + n + 2.

Suppose f_{0} = ∑_{i=1}^{m} a_{i}f_{i} (a_{i} ∈ ℚ[X_{1}, …, X_{n}]). By lemma 19, there is a derivation D′ from Q_{0} to Q_{∞} such that deg(D′) ≤ deg(a_{i}f_{i}) for all i = 1, …, m. After omitting repetitions from D′, we must get the unique derivation D_{∞}. Since deg(D_{∞}) ≤ deg(D′), we conclude that deg(a_{i}f_{i}) ≥ deg(D_{∞}) ≥ e(n) + d + n + 2. But by definition of I(n, d), we have

I(5n + 5, d + n + 2) + deg(f_{0}) ≥ deg(a_{i}f_{i}) ≥ e(n) + d + n + 2.

Hence I(n, d) ≥ e(n) + n + d + 1. Q.E.D.

If f_{0} = ∑_{i=1}^{m} α_{i}f_{i} then by lemma ?? deg({α_{1}, …, α_{m}}) ≥ deg(D_{∞}) − deg(F) ≥ e(n) − c_{1}. This proves that I(m, d + c_{1}) ≥ e(n) − n − 1 where m = 5n + 5 is the number of variables in Σ_{1}. Hence

I(n, d) ≥ d^{2^{p}}, p ∼ n/5.

Lower Lound on S(n, d). First we show a property of Thue polynomials. If f = ∑_{i=1}^{k} h_{i} where each h_{i} ∈ R satisfies support(h_{i}) ⊆ support(f) then we say that f is a non-canceling sum of h_{1}, …, h_{k}, and write

f = ⨁_{i=1}^{k} h_{i}.

Lemma 26 Let f_{1}, …, f_{m} be Thue polynomials and f = ∑_{i=1}^{m} α_{i}f_{i}, (α_{i} ∈ R) and d_{0} := max{deg(α_{i}f_{i}) : i = 1, …, m}. Then f = ⨁_{j=1}^{k} h_{j} (k ≥ 1) where h_{j} are Thue polynomials that can be expressed as

h_{j} = ∑_{i=1}^{m} α_{j,i}f_{i}

with α_{i,j} ∈ R and deg(α_{j,i}f_{i}) ≤ d_{0}.

Proof. First we rewrite f in the form

f = ∑_{i=1}^{ℓ} β_{i}g_{i}

where each β_{i} is a monomial, each g_{i} ∈ {f_{1}, …, f_{m}} (possibly repeated) and deg(β_{i}g_{i}) ≤ d_{0}. We use induction on ℓ. If ℓ = 1 then the result is immediate. Assume ℓ > 1. Without loss of generality, assume that support(β_{1}g_{1}) ∩ support(f) is non-empty. By induction, f′:= f − β_{1}g_{1} can be written as a non-canceling sum,

f′ = ⨁_{j=1}^{k} h_{j}

where h_{j} can be expressed as h_{j} = ∑_{i=1}^{m} α_{j,i}f_{i}, deg(α_{j,i}f_{i}) ≤ d_{0}.

There are two cases. Case 1: support(β_{1}g_{1}) ⊆ support(f). Then we can write f = ⨁_{j=0}^{k} h_{j} where h_{0} = β_{1}g_{1}. This satisfies the lemma. Case 2: there is a word w ∈ support(β_{1}g_{1}) − support(f). Now let c_{j} be the coefficient of w in h_{j} for j = 1, …, k, and let c be the coefficient of w in f′. Since w ∈ support(f′), c ≠ 0 and the sum of all the c_{j}’s is equal to c. Now consider the expression

f = f′ + β_{1}g_{1}
= ∑_{j=1}^{k} h_{j} + ∑_{j=1}^{k} \frac{c_{j}}{c} β_{1}g_{1}

= ∑_{j=1}^{k} h′_{j}

where h′_{j} := h_{j} + (c_{j}/c)β_{1}g_{1}. One verifies: h′_{j} is Thue: this is obvious if c_{j} = 0, and otherwise, the coefficient of w in h′_{j} is zero because the coefficient of w is β_{1}g_{1} is −c. Hence support(h′_{j}) ⊆ support(f), and h′_{j} can be expressed as a linear sum of the f_{1}, …, f_{m} with degree at most d_{0}.

Q.E.D.

Lemma 27 Let S be a Thue system with a strongly unique derivation D_{0} : w_{0} →^{∗} w_{∞} and w_{0} is nonrecursive. Let F = {f_{1}, …, f_{m}} be the set of Thue polynomials corresponding to S and f_{0} = w_{∞}−w_{0}. Then any syzygy basis for S = Syz(f_{0}, f_{1}, …, f_{m}) has degree at least deg(D_{0}) − deg(F).

Proof. Let B ⊆ S be a basis for S where each element of B has degree at most d_{0}. Note that S contains a syzygy (g_{0}, …, g_{m}) where g_{0} = 1. This implies that there is a basis element (h_{0}, …, h_{m}) ∈ B such that the constant term of h_{0} is non-zero; without loss of generality, assume the constant term is 1. Now we have that

h_{0}f_{0} = − ∑_{i=1}^{m} h_{i}f_{i}.

By lemma 26, h_{0}f_{0} can be written as a non-canceling sum h_{0}f_{0} = ⨁_{j=1}^{k} p_{j} where each p_{j} is Thue. Also we may assume that p_{1} = ∑_{i=1}^{m} α_{i}f_{i} where deg(α_{i}f_{i}) ≤ deg({h_{1}f_{1}, …, h_{m}f_{m}}) ≤ d_{0} + deg(F). Each monomial of h_{0}f_{0} is of the form w_{0}β or w_{∞}β where ±β is a monomial of h_{0}. In particular, w_{0} is a monomial of h_{0}f_{0}. Without loss of generality, assume −w_{0} is a monomial of p_{1}. If the other monomial in p_{1} is of the form w_{0}β, then p_{1} = w_{0}β − w_{0}. By lemma 19, there is a derivation from w_{0} to w_{0}β, contradicting the non-recursiveness of w_{0}. Hence p_{1} = w_{∞}β − w_{0}. So there is a simple derivation D from w_{0} to w_{∞}β such that deg(D) ≤ d_{0} + deg(F). By the strong uniqueness of D_{0}, β = 1 and D = D_{0}. Hence d_{0} ≥ deg(D_{0}) − deg(F). Q.E.D.

We apply Lemma B to the Thue system S_{1}, getting a lower bound for S(n, d) exactly as in the case of I(n, d).

Exercises

Exercise 11.1: Modify S_{1} to S_{2} so that

deg(S_{2}) = d + O(1)

and the number of variables used in 4n + O(1). HINT: for each k = 1, …, n, the set F_{k}:={F_{k}[inc], F_{k}[dec], F_{k}[pass]} has the property that all well-formed words w are linear in F_{k}. Show that these can be replaced two variables. □

Exercise 11.2:

(i) Let K ⊆ R be any set of polynomials and I ⊆ R be an ideal. We say I is of type K if for all f ∈ I, there are polynomials f_{1}, …, f_{m} ∈ I ∩ K (m ≥ 1) such that f = ⨁_{i=1}^{m} f_{i}. Show that an ideal is Thue iff it is generated by a finite subset of Thue polynomials. (ii) The reduced Gröbner basis of a Thue ideal is Thue. Remark: Monomial and homogeneous ideals exhibit similar properties. □

References

[1] D. Bayer and M. Stillman. Computation of hilbert functions. Journal of Symbolic Computation, 14(1):31–50, 1992.

[2] David Bayer and Michael Stillman. On the complexity of computing syzygies. Journal of Symbolic Computation, 6:135–147, 1988.

[3] Thomas W. Dubé. Quantitative analysis of problems in computer algebra: Gröbner bases and the Nullstellensatz. PhD thesis, Courant Institute, N.Y.U., 1989.

[4] Thomas W. Dubé. The structure of polynomial ideals and Gröbner bases. SIAM Journal Computing, 19(4):750–773, 1990.

§A. APPENDIX: Properties of S_{0}  Lecture XIII  Page 37

[5] Marc Giusti. Some effectivity problems in polynomial ideal theory. In Lecture Notes in Computer Science, volume 174, pages 159–171. Springer-Verlag, 1984.

[6] Dung T. Huynh. A superexponential lower bound for Gröbner bases and Church-Rosser commutative Thue systems. Information and Computation, 68:196–206, 1968.

[7] D. Lazard. A note on upper bounds for ideal theoretic problems. Journal of Symbolic Computation, 13:231–233, 1992.

[8] Ernst W. Mayr and Albert R. Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics, 46:305–329, 1982.

[9] H. Michael Möller and Ferdinando Mora. Upper and lower bounds for the degree of Gröbner bases. In Lecture Notes in Computer Science, volume 174, pages 172–183, 1984. (Eurosam 84).

[10] Emil L. Post. Recursive unsolvability of a problem of Thue. Journal of Symbolic Logic, 12:1–11, 1947.

[11] Chee Yap. A new lower bound construction for commutative Thue systems with applications. Journal of Symbolic Computation, 12:1–28, 1991.

[12] Chee Yap. A double exponential lower bound for degree-compatible Gröbner bases. Technical Report B-88-07, Fachbereich Mathematik, Institut fuer Informatik, Freie Universitaet Berlin, October 1988.

[13] Oscar Zariski and Pierre Samuel. Commutative Algebra, volume 1. Springer-Verlag, New York, 1975.

§A. APPENDIX: Properties of S_{0}

We prove two technical properties of the system S_{0}: the Basic Lemma (§10) and the non-recursiveness of w_{0} (lemma 23).

Proof of Basic Lemma. The result is easy to check for k = 1. So assume k > 1.

(a.1)_{k,ℓ} We shall be referring to the words u_{i} (i = 1, …, 8) defined in the standard derivation in the proof of lemma 1(a). By assumption, F_{k,ℓ}[pass]F_{ℓ}[inc] | w_{1}, and the word u_{1} in this lemma and u_{1} in lemma 1(a) are identified by assuming

w_{1} = wF_{k,ℓ}[pass]F_{ℓ}[inc].

Since B_{0}^{d}F_{1,k}[dec] | u′_{1}, there must be a first word x_{1} in the derivation D_{1} in which B_{0}^{d}F_{1,k−1}[dec] | x_{1}. By the induction hypothesis (a.1)_{k−1,k−1}, x_{1} has the form of u_{2}:

u_{2} = w_{1}B_{0}^{d}A_{k−1}^{e(k−1)}F_{1,k−1}[dec]F_{k−1}[inc].

So the prefix of D_{1} that derives u_{2} is standard and unique. In particular, the last rule applied to get u_{2} is a forward start rule. Now two rules are applicable to u_{2}: (F1)_{k−1} and some reverse start rule. But this reverse start rule is excluded since otherwise we get a non-simple derivation (it is easily checked: a forward start rule followed by a reverse start rule gives a non-simple derivation). Thus the word after u_{2} in D_{1} must be obtained by applying rule (F1)_{k−1}. This word is u_{3}. Since B_{0}^{d}F_{1,k−1}[dec] | u′_{1} but not u_{3}, there is a first word x_{2} after u_{3} in D_{1} such that B_{0}^{d}F_{1,k−1}[dec] | x_{2}. Also the rule applied to u_{3} must be a forward one. By induction hypothesis (a.1)_{k−1,ℓ}, we conclude that x_{2} is the same as u_{4}.

Now u_{4} = x_{3}(0) where

x_{3}(i) := w_{1}B_{0}^{d}A_{k−1}^{e(k−1)−i}B_{k−1}^{i}A_{ℓ}^{(i+1)e(k−1)}F_{1,k−1}[dec]F_{k−1}[pass],

i = 0, …, e(k − 1). Assume in general that x_{3}(i) has just been derived by a forward start transition. In that case, if i = e(k − 1) then there are no rules applicable to x_{3}(i), so assume i < e(k − 1). Then we could apply either rule (F2)_{k−1} or rule (F3)_{k−1} to x_{3}(i).

Case 1: If we apply (F3) to x_{3}(i) we get

x_{4} := w_{1}A_{0}^{d}A_{k−1}^{e(k−1)−i−1}B_{k−1}^{i+1}A_{ℓ}^{(i+1)e(k−1)}F_{1,k−1}[inc]F_{k−1}[dec].

But then we may apply induction (a.2)_{k−1,k−1} (since only a forward rule now applies to x_{4}) which implies B_{k−1}^{e(k−1)} | x_{4}. This implies i = e(k − 1) − 1.

Case 2: If we apply (F2) to x_{3}(i), we get

x_{5} := w_{1}A_{0}^{d}A_{k−1}^{e(k−1)−i−1}B_{k−1}^{i+1}A_{ℓ}^{(i+1)e(k−1)}F_{1,k−1}[inc]F_{k−1}[pass].

If the next rule applied is a forward rule, then by induction (a.1)_{k−1,ℓ}, we get x_{3}(i + 1). We claim that this is the only possibility. Suppose for the sake of contradiction that the rule applied to x_{5} is a reverse rule. Then it must be reverse (F1)_{k−1}, giving us

x_{6} := w_{1}B_{0}^{d}A_{k−1}^{e(k−1)−i−1}B_{k−1}^{i+1}A_{ℓ}^{(i+1)e(k−1)}F_{1,k−1}[dec]F_{k−1}[inc].

Observe that no forward rule is applicable to x_{6}. Since the flag F_{k−1}[inc] must subsequently change, and this can only occur as a result of applying a finish rule (Fm)_{j} or its reverse (for some m = 1, 2, 3 and j ≥ k − 1). This means that there is a first word x_{7} after x_{6} such that A_{0}^{d}F_{1,k−1}[inc] | x_{7}. By induction (b.1)_{k−1,k−1}, this means A_{k−1}^{e(k−1)} divides x_{6}. Clearly a contradiction.

We conclude from the analysis of these two cases that starting from u_{4} = x_{3}(0), we must repeatedly apply the sequence of rules,

[(F2)_{k−1}, induction (a.1)_{k−1,ℓ}]

for e(k − 1) − 1 times, yielding x_{3}(e(k − 1) − 1); finally, we apply rule (F3)_{k−1}, giving us u_{8}. From this, we can invoke induction (a.2)_{k−1,k−1} to get u′_{1}, exactly as in the standard derivation. Since all the steps are forced, this is unique.

(a.2)_{k,ℓ} Similar to part (a.1).

(b)_{k,ℓ} We only prove case (b.1)_{k,ℓ}. So F_{k,ℓ}[pass]F_{ℓ}[inc] | w′_{1}, and we will try to show that D_{2} is the reverse of the standard derivation in lemma 1. Instead of u_{1}, …, u_{8} of the proof in lemma 1, we define v_{1}, …, v_{8} by

v_{i}:= u_{i}w′_{1}(wA_{ℓ}^{e(k)}F_{k,ℓ}[pass]F_{ℓ}[inc])^{−1}.

For instance,

v_{8} = w′_{1}A_{0}^{d}B_{k−1}^{e(k−1)}F_{1,k−1}[inc]F_{k−1}[dec].

It is not clear that the v_{i}’s are well-defined words; they would all be clearly well-defined if

A_{ℓ}^{e(k)} | w′_{1},

which we will show. But v_{8}, v_{7} are well-defined in any case.

Starting from u′_{1} = w′_{1}B_{0}^{d}F_{1,k}[dec], we may invoke induction (b.2)_{k−1,k−1} to get to v_{8}. Then reverse (F3)_{k−1} is forced and we get to

v_{7} = w′_{1}B_{0}^{d}A_{k−1}B_{k−1}^{e(k−1)−1}F_{1,k−1}[dec]F_{k−1}[pass].

Now either rule (F2)_{k−1} or some reverse rule applies to v_{7}.

First assume that rule (F2)_{k−1} is applied to v_{7}, giving

x_{8} := w′_{1}A_{0}^{d}B_{k−1}^{e(k−1)}F_{1,k−1}[inc]F_{k−1}[pass].

If a reverse rule were applied to x_{8} then this is reverse (F1)_{k−1} giving us

x_{9} := w′_{1}B_{0}^{d}B_{k−1}^{e(k−1)}F_{1,k−1}[dec]F_{k−1}[inc].

Now only a reverse rule is applicable to x_{9}, and we can apply induction (b.1)_{k−1,k−1} which implies A_{k−1}^{e(k−1)} divides x_{9}, contradiction. So a forward rule is applied to x_{8}. Since F_{k−1}[pass] in x_{8} must change as some later point, we argue as before that B_{0}^{d}F_{1,k−1}[dec] divides some subsequent word x_{10}. But then induction (a.1)_{k−1,ℓ} implies that x_{8} leads to

x_{11} := w′_{1}B_{0}^{d}B_{k−1}^{e(k−1)}A_{ℓ}^{e(k−1)}F_{1,k−1}[dec]F_{k−1}[pass].

But now we are stuck.

Hence we can assume that some reverse rule is applied to v_{7}. Then by induction (b.1)_{k−1,ℓ} we know that A_{ℓ}^{e(k−1)} | v_{7} and we arrive at the word

x_{12} := w′_{1}A_{0}^{d}A_{k−1}B_{k−1}^{e(k−1)−1}A_{ℓ}^{−e(k−1)}F_{1,k−1}[inc]F_{k−1}[pass].

Note that x_{12} = x_{13}(1) where

x_{13}(i) := w′_{1}A_{0}^{d}A_{k−1}^{i}B_{k−1}^{e(k−1)−i}A_{ℓ}^{−i·e(k−1)}F_{1,k−1}[inc]F_{k−1}[pass].

In general assume that x_{13}(i) occurs in D_{2}. In particular, this means that A_{ℓ}^{i·e(k−1)} | w′_{1} (i.e., x_{13}(i) is well-defined). Further assume that x_{13}(i) had been obtained by applying a reverse start rule (this is true of x_{12} = x_{13}(1)). So the only rules applicable to x_{13}(i) are reverse (F1)_{k−1} or reverse (F2)_{k−1}.

(i) If it is known that reverse (F2)_{k−1} is next applied to x_{13}(i) then we can apply induction (b.1)_{k−1,ℓ} to conclude that x_{13}(i+1) occurs in D_{2}. But note that reverse (F2) cannot be applied to x_{13}(e(k−1)).

(ii) If reverse (F1)_{k−1} is applied to x_{13}(i) then we get to

x_{14}(i) := w′_{1}B_{0}^{d}A_{k−1}^{i}B_{k−1}^{e(k−1)−i}A_{ℓ}^{−i·e(k−1)}F_{1,k−1}[dec]F_{k−1}[inc].

Now only a reverse rule apply to x_{14}(i) and by induction (b.1)_{k−1,k−1}, we see that A_{k−1}^{e(k−1)} | x_{14}(i). This implies that i = e(k − 1). But x_{14}(e(k − 1)) is v_{2}.

From (i) and (ii), we conclude: starting from x_{13}(1) in D_{2}, we must repeatedly apply the sequence of reverse rules

[reverse (F2)_{k−1}, induction (b.1)_{k−1,ℓ}]

for e(k − 1) − 1 times, yielding x_{13}(e(k − 1)). Finally we apply reverse (F2) to give v_{2}. From v_{2}, we invoke induction (b.1)_{k−1,k−1} to get to v_{1}. This proves the basic lemma.

Proof of the non-recursiveness of w_{0}. Under the assumption that we have a non-trivial simple derivation D : w_{0} →^{∗} w̃ where w_{0}|w̃, we force D to trace through the computation path of a standard derivation and derive a contradiction. We will rely heavily on the analysis of the proof of the Basic Lemma (appendix). Invocations of parts of the Basic Lemma are denoted “ind(a.1)_{k,ℓ}”, etc, for appropriate k, ℓ. We also refer to the words u_{1}, …, u_{8}, x_{1}, …, x_{7} used in the proof of the Basic Lemma. We assume that u_{1} there is equal to w_{0}.

We proceed as follows. Any derivation starting from w_{0} begins with a forward rule. Suppose that k = 1, …, n is the smallest level such that D does not modify the flag at level k. It is clear that k ≥ 2. Since the flag at level k − 1 is initially F_{k−1}[inc], and the only rule that changes F_{k−1}[inc] is rule (F1)_{k−1}, we conclude that D must have a first word y_{1} such that B_{0}^{d}F_{1,k−1}[dec]F_{k−1}[inc] | y_{1}. By ind(a.1)_{k−1,k−1}, the prefix of D up to y_{1} is a standard derivation and y_{1} must be equal to u_{2}. After applying rule (F1)_{k−1}, we get u_{3}. Since the flag at level k − 1 of u_{3} must subsequently change (since F_{k−1}[inc] | w̃), some finish rule at level j ≥ k − 1 must be applied. This means some subsequent word is divisible by B_{0}^{d}F_{1,k−1}[dec]. Only a forward rule is applicable to u_{3}. So we may invoke ind(a.1)_{k−1,k} to get to u_{4} (assuming ℓ = k).

Now u_{4} has the general form of x_{3}(i). The two cases are again applicable: Case 1, where we apply (F3) to x_{3}(i) to get x_{4}. Since the flag at level k − 1 is not colored [inc], we can again invoke ind(a.2)_{k−1,k−1} which implies i = e(k − 1) − 1. Case 2, where we apply (F2) to x_{3}(i) to get x_{5}. If we next apply a backward rule to x_{5}, it must be reverse (F1), yielding x_{6}. Now only a backward rule apply to x_{6} and since we eventually must reach a word divisible by A_{0}^{d}F_{1,k}[inc], we may invoke ind(b.1)_{k−1,k−1} to get a contradiction. This means only a forward rule is applicable to x_{3}(i) and after invoking ind(a.1)_{k−1,k} we get to x_{3}(i + 1).

Again we conclude from cases 1 and 2 that we must eventually reach u_{8}. Only a forward rule is applies to u_{8}. Since the flag of u_{8} at level k − 1 must eventually change, we can again invoke ind(b.1)_{k−1,k−1} to yield u′_{1}. But note that from u′_{1} there is only rule (F1)_{k} that applies. But this rule modifies the flag at level k, a contradiction. This concludes the proof.