Algebraic interpretation of a theorem of Clements and Lindström Susan Cooper and Leslie G. Roberts

1. Introduction

Let R = k[x_{1}, …, x_{n}], k a field, x_{i} indeterminates of degree 1, and I a homogeneous ideal in R. Let S = R/I. Then S = ⊕_{i≥0}S_{i} is a graded ring. The Hilbert function of S is defined by H_{S}(i) = dim_{k} S_{i}, i ≥ 0. By convention we take H_{S}(i) = 0 if i < 0. A sequence {c_{i}}_{i≥0} such that c_{i} = H_{S}(i), i ≥ 0 for some such S is called an O-sequence. In particular we have c_{0} = 1. It is convenient to take c_{i} = 0 for i < 0. Macaulay characterized O-sequences combinatorially. Macaulay’s characterization has been formulated by Stanley [5, Theorem 2.2 (i)⇔(iii)] in the form c_{0} = 1, c_{i} ≥ 0 for all i ≥ 0, and c_{i+1} ≤ c_{i}^{<i>} for i ≥ 1, where c_{i}^{<i>} is defined in terms of binomial expansions. It is well known to commutative algebraists that the paper [1] of Clements and Lindström generalizes Macaulay’s characterization of O-sequences. However [1] is written in a combinatorial language and it seems not to be as well understood how to interpret [1] algebraically. Greene and Kleitman give an exposition of the work of Clements and Lindström in [3] (also in a primarily combinatorial language). The purpose of this expository note is to describe our present understanding of how things work. In section 2 we recall the results of Macaulay (as presented in [5]). In section 3 we review the paper [1]. In section 4 we interpret [1] in terms of revlex-segments and order ideals, and in section 5 we count the number of elements in rev-lex-segments, obtaining binomial expansions given in [3] that are similar to those used by Stanley in [5] to describe Osequences. In section 6 we give examples to illustrate and clarify our discussion and in section 7 we indicate how Macaulay’s characterization of O-sequences follows from section 6.

2. Macaulay’s Theorem

As above let R = k[x_{1}, …, x_{n}].

Definition 2.1. [5, page 59] An order ideal of R is a non-empty set M of monomials in x_{1}, …, x_{n} such that if x ∈ M and y is a monomial dividing x then y ∈ M.

Note that if M is an order ideal then 1 ∈ M. One might also refer to the set of exponents of an order ideal of R as an order ideal in ℕ^{n} (ℕ = {0, 1, 2, …, }). Explicitly an order ideal in ℕ^{n} is a non-empty subset Λ of ℕ^{n} such that if α ∈ Λ and β <_{pr} α then β ∈ Λ (where β <_{pr} α means that α − β has all coordinates ≥ 0, with at least one coordinate > 0).

Let ℳ be the set of all monomials in x_{1}, …, x_{n}. Then M is an order ideal of R if and only if ℳ \M is the set of monomials in a monomial ideal I_{M} of R. If I is any homogeneous ideal of R then R/I has a kbasis which is (the canonical image of) an order ideal of R ([5, Theorem 2.1]). Therefore there is a monomial ideal J of R such that R/J has the same Hilbert function as R/I.

Of special interest in Macaulay’s Theorem is the rev-lex order ideal. First recall the definition of deg-rev-lex ordering on ℳ, as given in recent expositions, such as [2, Chapter 2, Definition 6 (p.56)] (there called Graded Reverse Lex Order, or grevlex). Let x^{α} = x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}} and x^{β} = x_{1}^{b_{1}}x_{2}^{b_{2}} ⋯ x_{n}^{b_{n}} where α = (a_{1}, a_{2}, ⋯, a_{n}) and β = (b_{1}, b_{2}, ⋯, b_{n}). Then x^{α} > x^{β} means that either ∑ a_{i} > ∑ b_{i} (i.e. deg x^{α} > deg x^{β}) or ∑ a_{i} = ∑ b_{i} and the last non-zero coordinate of α − β is negative. In this situation we will also say that deg α = ∑ a_{i}, deg β = ∑ b_{i} and α > β, thereby putting a corresponding deg-rev-lex order on ℕ^{n} as well. In the following > will always denote deg-rev-lex order. When comparing monomials of the same degree we will often simply write “rev-lex” order. Some consequences of the definition are

(a) x_{1} > x_{2} > ⋯ > x_{n}

(b) Any monomial containing only x_{1}, …, x_{i−1} is larger than any monomial of the same degree that contains x_{i} (where “contains” means that the variable in question occurs with a positive exponent), or more generally xx_{i}^{a} > yx_{i}^{b} if x and y are monomials in x_{1}, …, x_{i−1}, xx_{i}^{a} and yx_{i}^{b} have the same degree, and a < b.

A rev-lex segment of degree d is a collection 𝒮 of monomials of degree d such that if y ∈ 𝒮 and y_{1} is a monomial of degree d such that y_{1} > y then y_{1} ∈ 𝒮. That is 𝒮 consists of the largest |𝒮 | elements of degree d in rev-lex order (| ∗ | denoting cardinality). For example {x_{1}^{2}}, {x_{1}^{2}, x_{1}x_{2}} {x_{1}^{2}, x_{1}x_{2}, x_{2}^{2}}, {x_{1}^{2}, x_{1}x_{2}, x_{2}^{2}, x_{1}x_{3}} are all rev-lex segments, but {x_{1}^{2}, x_{1}x_{2}, x_{1}x_{3}} is not since x_{2}^{2} > x_{1}x_{3} and x_{2}^{2} ∉ {x_{1}^{2}, x_{1}x_{2}, x_{1}x_{3}}.

Definition 2.2. A rev-lex segment order ideal M is an order ideal such that for all d the monomials M_{d} ⊂ M of degree d are a rev-lex segment.

Macaulay’s Theorem can be stated in the following manner.

Theorem 2.3. There is a one-to-one correspondence between O-sequences (i.e. Hilbert functions of quotients k[x_{1}, …, x_{n}]/I, I a homogeneous ideal) and rev-lex segment order ideals, defined as follows: to the sequence 1, c_{1}, c_{2}, …, c_{i} …, (c_{1} ≤ n) define a set M by letting the degree d part M_{d} be the largest c_{d} monomials of degree d in x_{1}, …, x_{n}.

The only thing that one needs to establish in order to prove Theorem 2.3 is that the set M constructed in the statement of the Theorem is in fact an order ideal. The following definition will be needed:

Definition 2.4. Let M be any set of monomials in R, and let M_{d} be the set of elements of M in degree d. Then the compression CM of M is the set of monomials consisting of the largest |M_{d}| elements of degree d, for all d ≥ 0.

Given a bit of translation, [1, Corollary 2] says that the compression of an order ideal is an order ideal. This, together with Stanley’s observation [5, Theorem 2.1] that every Hilbert function comes from some order ideal, is exactly what we need to show that the set constructed in the statement of Theorem 2.3 is an order ideal. More details of the translation, will be described in the next two sections.

3. Review of Clements and Lindström.

In [1], Clements and Lindström prove a combinatorial theorem from which they state that Macaulay’s Theorem follows. In this section we recall the concepts and language used in [1]. In the next section we will see how we can apply their results.

We begin by recalling the definition given in [1] of lexicographic order on ℕ^{n} (n a positive integer). We will write <_{lex} (rather than < as used in [1]) to distinguish from our use of < for rev-lex order.

Definition 3.1. We say that (a_{1}, …, a_{n}) ∈ ℕ^{n} is less than (b_{1}, …, b_{n}) ∈ ℕ^{n} with respect to lexicographic order, and write (a_{1}, …, a_{n}) <_{lex} (b_{1}, …, b_{n}), if the leftmost non-zero entry of (b_{1} − a_{1}, …, b_{n} − a_{n}) is positive.

Fix integers 1 ≤ k_{1} ≤ ⋯ ≤ k_{n} and let F be the set of all vectors (a_{1}, …, a_{n}) ∈ ℕ^{n} for which 0 ≤ a_{i} ≤ k_{i} for i = 1, …, n. We put an ordering on F by restricting the lexicographic order of ℕ^{n} to F. We say that F is ordered lexicographically.

We will use the following notation from [1]:

Notation 3.2. With the k_{i} and F as above, let k = k_{1} + ⋯ + k_{n} and H be a subset of F.

(1) F_{v} := {(a_{1}, …, a_{n}) | a_{1}+⋯+a_{n} = v}∩F for each v = 0, …, k.

(2) H_{v} := H ∩ F_{v} for each v = 0, …, k.

Note that, for F and v as above, we will write down the elements of F_{v} from smallest to largest in lexicographic order. With this convention, we can speak of the first r elements as the smallest r elements of F_{v} and last s elements as the largest s elements of F_{v} for appropriate r, s ∈ ℕ.

Definition 3.3. With the above notation, let H be a subset of F and v ∈ {0, …, k}.

(1) The set of the |H_{v}| first elements of F_{v} in lexicographic order is the compression of H_{v}, and is denoted CH_{v}.

(2) CH := ∪_{v=0}^{k}CH_{v}.

(3) The set of the |H_{v}| last elements of F_{v} in lexicographic order will be called the last compression of H_{v}, and is denoted LH_{v}.

(4) Γ is the function from F to the set of all subsets of F which associates (a_{1}, …, a_{n}) to the subset

{(a_{1}−1, a_{2}, …, a_{n}), (a_{1}, a_{2}−1, a_{2}, …, a_{n}), …, (a_{1}, …, a_{n−1}, a_{n}−1)}∩F.

We extend the definition of Γ to Γ(H) by letting Γ(H) := ∪_{h∈H}Γ(h).

(5) If Γ(H) ⊆ H, then we say that H is closed.

(6) P is the function from F to the set of all subsets of F which associates (a_{1}, …, a_{n}) to the subset

{(a_{1}+1, a_{2}, …, a_{n}), (a_{1}, a_{2}+1, a_{2}, …, a_{n}), …, (a_{1}, …, a_{n−1}, a_{n}+1)}∩F.

We extend the definition of P to P (H) by letting P (H) := ∪_{h∈H}P (h).

Clements and Lindström show the following:

Theorem 3.4. [1, Theorem] Let k, H, F be as above. Then Γ(CH_{v}) ⊆ C(Γ(H_{v})) for each v ∈ {0, …, k}.

Corollary 3.5. [1, Corollary 1] Let k, H, F be as above. Then P (LH_{v}) ⊆ L(P (H_{v})) for each v ∈ {0, …, k}.

Corollary 3.6. [1, Corollary 2] With H and F as above, if H is closed then CH is closed.

We continue with k_{i}, k, and F as above and fix J := (x_{1}^{k_{1}+1}, x_{2}^{k_{2}+1}, …, x_{n}^{k_{n}+1}), an ideal in R = k[x_{1}, …, x_{n}]. The monomials of S := k[x_{1}, …, x_{n}]/(x_{1}^{k_{1}+1}, x_{2}^{k_{2}+1}, …, x_{n}^{k_{n}+1}) are of the form x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}}, where the a_{i} are elements of ℕ which satisfy 0 ≤ a_{i} ≤ k_{i} and by abuse of notation we use the symbol x_{i} for the canonical image in S of x_{i} ∈ R. With this observation, the monomials of S are in 1-1 correspondence with the set F, with x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}} corresponding to the exponent vector (a_{1}, a_{2}, …, a_{n}). As with F, we will list the monomials in S of degree t from smallest to largest in lexicographic order, where x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}} <_{lex} x_{1}^{b_{1}}x_{2}^{b_{2}} ⋯ x_{n}^{b_{n}} if and only if (a_{1}, …, a_{n}) <_{lex} (b_{1}, …, b_{n}) (and so x_{1} >_{lex} x_{2} >_{lex} ⋯ >_{lex} x_{n}). Thus, we can also speak of the first r and last s monomials of S_{t} for each degree t and appropriate r, s ∈ ℕ. With this convention, we can apply the results of Clements and Lindström to S.

4. Application of Clements and Lindström to truncated polynomial rings.

Suppose we have a sequence of integers \underline{e} = \{e_{1}, …, e_{n}\} where e_{1} ≥ e_{2} ≥ e_{3} ≥ ⋯ ≥ e_{n} ≥ 1. Let R\underline{e} = k[x_{1}, … x_{n}]/(x_{1}^{e_{1}+1}, … x_{n}^{e_{n}+1}). Let ℳ\underline{e} be the set of monomials of R\underline{e} These are monomials x^{α} with α ∈

ℕn ; \underline{e} = \{(a_{1}, a_{2}, ⋯, a_{n})|0 ≤ a_{i} ≤ e_{i} ∀i\}. If also β = (b_{1}, b_{2}, ⋯, b_{n}) ∈ ℕn ; \underline{e}

then we say that x^{β} divides x^{α} if b_{i} ≤ a_{i}, 1 ≤ i ≤ n. If x^{β} divides x^{α} we will define x^{α}/x^{β} to be x^{α−β}. We can regard ℳ\underline{e} as a subset of the monomials ℳ in R = k[x_{1}, … x_{n}]. The definitions of order ideal and deg-rev-lex order can be adapted to ℳ\underline{e} in a natural way.

Definition 4.1. An order ideal of ℳ\underline{e} (or R\underline{e}) is a non-empty set M ⊆ ℳ\underline{e} such that if x ∈ M and y is a monomial dividing x then y ∈ M. The exponent set {α|x^{α} ∈ M} of M will also be referred to as an order ideal (of ℕ^{n}).

Definition 4.2. Let x^{α}, x^{β} ∈ ℳ\underline{e}, where α = (a_{1}, a_{2}, ⋯, a_{n}) and β = (b_{1}, b_{2}, ⋯, b_{n}) with a_{i} ≤ e_{i}, b_{i} ≤ e_{i} for all i. Then x^{α} > x^{β} (in deg-rev-lex order of ℳ\underline{e}) means that either ∑ α_{i} > ∑ β_{i} (i.e. deg x^{α} > deg x^{β}) or ∑ α_{i} = ∑ β_{i} and the last non-zero coordinate of α − β is negative.

Definition 4.3. Let (ℳ\underline{e})_{d} be the set of all monomials of degree d in ℳ\underline{e}. A rev-lex segment of degree d in ℳ\underline{e} is a subset 𝒮 of (ℳ\underline{e})_{d} such that if M ∈ 𝒮 and M_{1} ∈ (ℳ\underline{e})_{d} with M_{1} > M then M_{1} ∈ 𝒮. A rev-lex segment order ideal M of ℳ\underline{e} is an order ideal of ℳ\underline{e} such that for all d the monomials M_{d} ⊂ M of degree d are a rev-lex segment of degree d. A final rev-lex segment of degree d in ℳ\underline{e} is a subset 𝒮′ of (ℳ\underline{e})_{d} such that if M ∈ 𝒮′ and M_{1} ∈ (ℳ\underline{e})_{d} with M_{1} < M then M_{1} ∈ 𝒮. The complement in (ℳ\underline{e})_{d} of a rev-lex-segment is a final rev-lex-segment and vice versa. (Perhaps rev-lex segments should be called initial rev-lex segments, but we skip the “initial” as we use them more frequently than final rev-lex segments.)

Note that a subset M ⊆ ℳ\underline{e} is an order ideal of R\underline{e} if and only if M is an order ideal of R and if x^{α}, x^{β} ∈ ℳ\underline{e} then x^{α} > x^{β} ∈ ℳ\underline{e} if and only if x^{α} > x^{β} ∈ ℳ. But a rev-lex-segment in ℳ\underline{e} need not be a rev-lex-segment in ℳ. As in the case of R and ℳ, the complement N = ℳ\underline{e}\M of an order ideal M ⊆ ℳ\underline{e} is the k-basis of a monomial ideal I_{M} of R\underline{e}.

As in the case of R we have

Theorem 4.4. Let I be a homogeneous ideal in R\underline{e}. Then there is an order ideal M in ℳ\underline{e} whose canonical image in R\underline{e}/I forms a k-basis of R\underline{e}/I.

Proof. The proof is the same as that of [5, Theorem 2.1]. (However we cannot just apply [5, Theorem 2.1] to the quotient of R with the same Hilbert function as R\underline{e}/I because an order ideal of ℳ need not be an order ideal of ℳ\underline{e}). □

Note that R\underline{e}/I_{M} has the same Hilbert function as R\underline{e}/I.

Definition 4.5. Let M be any set of monomials in ℳ\underline{e}, and let M_{d} be the set of elements of M in degree d. Then the compression C\underline{e}M of M (in ℳ\underline{e}) is the set of monomials consisting of the largest |M_{d}| elements in ℳ\underline{e} of degree d, for all d ≥ 0.

We now compare the notation of the present section with that of [1] introduced in the previous section. Let k_{1} ≤ k_{2} ≤ ⋯ ≤ k_{n}. If α ∈ ℕ^{n} denote by α^{r} the vector obtained by reversing the order of the coordinates. Then α > β if and only if the last non-zero coordinate of α − β is negative if and only if the last non-zero coordinate of β − α is positive if and only if the first non-zero coordinate of β^{r} − α^{r} is positive if and only if α^{r} <_{lex} β^{r}. Therefore reversing the order of the coordinates transforms > in our rev-lex into < in the lex of [1] (on vectors of the same degree) and also transforms our decreasing sequence of e_{i} into their increasing sequence of k_{i}. We have made this transformation from lex to rev-lex in order to be consistent with [3] and also because all the more recent literature that we are aware of works with lex-segment ideals (and hence rev-lex segment order ideals) rather than lex-segment order ideals.

If X is any subset of ℕ^{n} define X^{r} = {x^{r}|x ∈ X}. It is clear that X is the exponent set of an order ideal in R\underline{e} if and only if X^{r} is a closed subset of F = (ℕn ; \underline{e})^{r} (with F as in Definition 3.3). Furthermore if M is any set of elements of ℳ\underline{e} and C\underline{e}M is as defined in Definition 4.5 then (C\underline{e}M)^{r} = C(M^{r}) the latter as defined in Definition 3.3, part (2). Finally M is the exponent set of the monomial basis of a monomial ideal in R\underline{e} if and only if P (M^{r}) ⊆ M^{r}, where P is as in Definition 3.3 part (6). The following is now immediate from Corollary 3.6.

Theorem 4.6. If M is an order ideal in ℳ\underline{e} then so is C\underline{e}M (which is then a rev-lex-segment order ideal).

Putting Theorems 4.4 and 4.6 together we have

Theorem 4.7. There is a one-to-one correspondence between Hilbert functions H = \{c_{i}\}_{i≥0} of quotients of R\underline{e} by a homogeneous ideal, and rev-lex-segment order ideals of ℳ\underline{e}. The order ideal corresponding to H is obtained by taking the largest c_{i} monomials of ℳ\underline{e} in degree i for all i ≥ 0.

From [1, Theorem] and [1, Corollary 1] we will obtain growth conditions on the Hilbert function of a quotient of R\underline{e}.

Definition 4.8. If x^{α} is a monomial of degree d in ℳ\underline{e} define L(x^{α}) be the set of all monomials of degree d in ℳ\underline{e} that are greater than or equal to x^{α}.

Clearly every rev-lex-segment 𝒮 of degree d in ℳ\underline{e} equals L(x^{α}), where x^{α} is the smallest element of 𝒮.

Now we prove a couple of lemmas. These are perhaps implicit (explicit?) in [1], but they are crucial to our way of looking at things and have elementary proofs.

Lemma 4.9. Let 𝒮 = L(x^{α}) be a rev-lex-segment of degree d > 0 in ℳ\underline{e}, where α = (a_{1}, …, a_{n}). Suppose that r is the smallest index such that a_{r} > 0. Then the set 𝒯 (or 𝒯 (𝒮) if it is necessary to specify the starting rev-lex-segment) of all degree d − 1 monomial factors of elements of 𝒮 is equal to L(x^{α}/x_{r}). (In particular, 𝒯 is a rev-lex-segment.)

Proof. Suppose that α = (0, …, 0, a_{r}, a_{r+1}, …, a_{n}) and β = (0, …, 0, a_{r} − 1, a_{r+1}, …, a_{n}). Our Lemma is equivalent to the following two assertions: (1) if x^{α′} ∈ (ℳ\underline{e})_{d−1} and x^{α′} ≥ x^{β} then, for some i, x_{i}x^{α′} ∈ ℳ\underline{e} and x_{i}x^{α′} ≥ x^{α}. (2) if x^{α′} ∈ (ℳ\underline{e})_{d−1} and if x^{α′} < x^{β} then for all i such that x_{i}x^{α′} ∈ ℳ\underline{e} we have x_{i}x^{α′} < x^{α}. First we prove (1). Suppose x^{α′} ∈ (ℳ\underline{e})_{d−1} and x^{α′} ≥ x^{β}. If α′ = β then x_{r}x^{α′} = x^{α}. So suppose α′ > β and α′ = (a′_{1}, …, a′_{n}). Let s be the largest index in which the coordinates of α′ and β differ (necessarily with the s-coordinate of α′ being smaller). Since β is 0 in indices 1 through r − 1 we must have r ≤ s ≤ n. If r = s then x_{r}x^{α′} > x^{α}. Otherwise r < s and the coordinates of β in the range s through n are the a_{i}. If a′_{s} < a_{s} − 1 then x_{s}x^{α′} ∈ ℳ\underline{e} and x_{s}x^{α′} > x^{α}. If a′_{s} = a_{s} − 1 then ∑_{i=1}^{s−1} a′_{i} = ∑_{i=1}^{s−1} a_{i}. If a′_{i} = a_{i}, 1 ≤ i ≤ s − 1 then x_{s}x^{α′} = x^{α}. Otherwise a′_{i} < a_{i} for some i, 1 ≤ i ≤ s − 1 so x_{i}x^{α′} ∈ ℳ\underline{e} and x_{i}x^{α′} > x^{α}. This proves (1). Now we prove (2). Suppose x^{α′} ∈ (ℳ\underline{e})_{d−1} and x^{α′} < x^{β}. Let s be the largest index in which the coordinates of α′ and β differ (necessarily with that of α′ being larger). Since β is 0 in coordinates 1 through r − 1 and deg β = deg α′ = d − 1 we must have s > r. Then x_{i}x^{α′} < x^{α} for any i such that x_{i}x^{α′} ∈ ℳ\underline{e} because the coordinates of the exponent vector of x_{i}x^{α′} in the range s through n can only be the same or larger than those of x^{α′} and at least the s coordinate of the latter is already greater than a_{s}. □

Lemma 4.10. Let 𝒮 = L(x^{α}) be a rev-lex-segment of degree d in ℳ\underline{e}, where α = (a_{1}, a_{2}, … a_{n}). Let 𝒰 (or 𝒰 (𝒮) if it is necessary to specify the starting rev-lex-segment) be the set of all degree d + 1 monomials in ℳ\underline{e} all of whose degree d factors are in 𝒮. Suppose that r is the smallest index such that a_{r} ≠ 0 and let β = (0, …, 0, b_{r}, b_{r+1}, …, b_{n}) where b_{r} = a_{r} + 1 and b_{i} = a_{i} if r + 1 ≤ i ≤ n. If x^{β′} ∈ (ℳ\underline{e})_{d+1} then x^{β′} ∈ 𝒰 if and only if β′ ≥ β in the deg-rev-lex order of ℕ^{n}. (This implies that 𝒰 is a rev-lex-segment.) If a_{r} < e_{r} then x^{β} = x_{r}x^{α} ∈ (ℳ\underline{e})_{d+1} and 𝒰 = L(x_{r}x^{α}). If a_{r} = e_{r} then 𝒰 = L(x^{γ}) where γ = (c_{1}, …, c_{n}) is the smallest element of ℕ^{n} with (0 ≤ c_{i} ≤ e_{i}) that is larger than β.

Proof. We first show that if x^{β′} ∈ (ℳ\underline{e})_{d+1} and β′ ≥ β then x^{β′} ∈ 𝒰 . Of course, if a_{r} = e_{r} then x^{β} ∉ ℳ\underline{e}. If a_{r} < e_{r} then clearly x^{β} ∈ 𝒰 . Now suppose that x^{β′} ∈ ℳ\underline{e} is of degree d + 1 and β′ > β. We wish to show that if x^{α′} is any degree d factor of x^{β′} then α′ ≥ α. We have β′ = (…, b′_{r}, … b′_{s}, b′_{s+1} … b′_{n}) where b′_{s} < b_{s} and b_{i} = b′_{i} for s + 1 ≤ i ≤ n. We have r ≤ s ≤ n. If s > r then any degree d factor x^{α′} of x^{β′} is greater than x^{α} because the last non-zero coordinate of α′ − α (the t-th for r + 1 ≤ t ≤ n) is negative. If s = r then b′_{r} < b_{r}. If b′_{r} < b_{r} − 1 and x^{α′} is a degree d factor of x^{β′} then the last nonzero coordinate of α′ − α (the t-th for r ≤ t ≤ n) is negative so again x^{α′} > x^{α}. If b′_{r} = b_{r} − 1 then β′ = (∗, a_{r}, a_{r+1}, …, a_{n}) with exactly one non-zero coordinate (say the j-th) in the range 1 ≤ j ≤ r − 1, and this coordinate has value 1. Then x^{β′}/x_{j} = x^{α} and if r ≤ ℓ ≤ n then x^{β′}/x_{ℓ} > x^{α}. This shows in all cases that if β′ ≥ β then x^{β′} ∈ 𝒰 .

Now assume that deg β′ = d+1 and β′ < β. Then β′ = (…, b′_{r}, … b′_{s}, b′_{s+1} … b′_{n}) where b′_{s} > b_{s} and b_{i} = b′_{i} for s + 1 ≤ i ≤ n. We have r < s ≤ n, because otherwise the degree of β′ would be greater than d + 1. If b′_{j} ≠ 0 for some j < s then x^{β′}/x_{j} < x^{α}, i.e. x^{β′}/x_{j} ∉ 𝒮 so x^{β′} ∉ 𝒰 . If b′_{s} > b_{s} + 1 then x^{β′}/x_{s} < x^{α} so again x^{β′} ∉ 𝒰 . We can’t have both b′_{j} = 0 for j < s and b′_{s} = b_{s} + 1 because b_{r} ≥ 2. Hence always x^{β′} ∉ 𝒰 .

The final assertion of the Lemma is obvious. If a_{r} = e_{r}, so that β = (0, …, 0, a_{r}+1, a_{r+1}, …, a_{n}), then γ can be described as follows. If r > 1 then γ = (0, …, 0, 1, e_{r}, a_{r+1}, …, a_{n}). If r = 1 pick j, 2 < j ≤ n to be the smallest integer such that a_{j} > 0 and ∑_{i=2}^{j−1}(e_{i} − a_{i}) ≥ 2. Then γ = (0, …, 0, a, e_{s}, …, e_{j−1}, a_{j} − 1, a_{j} …, a_{n}) where a is chosen so that γ is of degree d + 1. The summation condition guarantees that such a γ exists. (We need the sum ≥ 2 so that each of e_{1} + 1 and a_{j} can be decreased by 1 without forcing some other coordinate to be greater than the corresponding value e_{i}.) If no such γ exists, then 𝒰 is empty. □

Remark 4.11. Lemma 4.10 can be interpreted as saying that the set of multiples by the x_{i} of elements of (ℳ\underline{e})_{d}\𝒮 (throwing away any monomials that become 0 in the ring structure of R\underline{e}) is a final rev-lex-segment of degree d + 1 (namely (ℳ\underline{e})_{d+1}\𝒰 ).

Theorem 4.12. Let R\underline{e}/I be a graded quotient of R\underline{e} with Hilbert function H. Suppose that H(i) = c. Let 𝒮 be the rev-lex-segment of degree i consisting of the c largest monomials of degree i in ℳ\underline{e}. Then H(i−1) must be at least the cardinality of the rev-lex-segment 𝒯 of degree i − 1 consisting of all degree i − 1 factors of elements of 𝒮.

Proof. That 𝒯 is a rev-lex-segment follows from Lemma 4.9. By Theorem 4.4 there is an order ideal M of ℳ\underline{e} which forms a k-basis of R\underline{e}/I. By definition of order ideal, M must contain all the degree d − 1 factors of elements of M_{d}. Now we translate our notation into the language of Theorem 3.4. Our M_{d} corresponds to H_{v} in Theorem 3.4, and the degree d − 1 factors of elements of M_{d} correspond to ΓH_{v}, so that H(i − 1) ≥ |ΓH_{v}| = |C(ΓH_{v})|. Our 𝒯 corresponds to Γ(CH_{v}). Our Theorem then follows from the conclusion Γ(CH_{v}) ⊂ C(ΓH_{v}) of Theorem 3.4. □

Theorem 4.13. Let R\underline{e}/I be a graded quotient of R\underline{e} with Hilbert function H. Suppose that H(i) = c. Let 𝒮 be the rev-lex-segment of degree i consisting of the c largest monomials of degree i in ℳ\underline{e}. Then H(i+1) can be at most the cardinality of the rev-lex-segment 𝒰 of degree i + 1 consisting of those degree i + 1 monomials in ℳ\underline{e} all of whose degree i factors are in 𝒮.

Proof. That 𝒰 is a rev-lex-segment follows from Lemma 4.10. Let M be some order ideal corresponding to R\underline{e}/I as in Theorem 4.4 and let I_{M} be the corresponding monomial ideal of R\underline{e}, which has k-basis N = ℳ\underline{e}\M. Then R/I_{M} also has Hilbert function H and N_{d+1} = (ℳ\underline{e})_{d+1}\M_{d+1} (the k-basis of (I_{M})_{d+1}) contains at least the set Ñ_{d+1} of multiples (that are non-zero in R\underline{e}) of elements of N_{d} = (ℳ\underline{e})_{d}\M_{d} by the x_{i} . We now translate our notation into that of Corollary 3.5. Our N_{d} is H_{v} in Corollary 3.5. Our (ℳ\underline{e})_{d}\𝒮 (which has the same cardinality as N_{d}) corresponds to LH_{v}. Our Ñ_{d+1} corresponds to P H_{v}. Taking into account Remark 4.11, our (ℳ\underline{e})_{d+1}\𝒰 corresponds to P (LH_{v}). The conclusion of Corollary 3.5 that P (LH_{v}) ⊂ L(P H_{v}) says that Ñ_{d+1} (and hence also the possibly larger set N_{d+1}) has cardinality at least as large as |(ℳ\underline{e})_{d+1}\𝒰 |, or taking complements in (ℳ\underline{e})_{d+1}, that |M_{d+1}| is at most as large as |𝒰 |, i.e. that H(i + 1) ≤ |𝒰 |, as claimed. □

Remark 4.14. The condition e_{1} ≥ e_{2} … ≥ e_{n} is necessary to apply [1] (as explained in the discussion before Theorem 4.6). The following example shows that without this condition the theory does not work at all. Let e_{1} = 1 and e_{2} = 3. Then R\underline{e} = k[x_{1}, x_{2}]/(x_{1}^{2}, x_{2}^{4}), which has Hilbert function 1, 2, 2, 2, 1, 0 →. The graded quotient ring R\underline{e}/(x_{1}x_{2}) has Hilbert function 1, 2, 1, 1, 0 →. But if we take the rev-lex segments of degrees 0,1,2,3 containing respectively the largest 1, 2, 1, 1 elements we get {1, x_{1}, x_{2}, x_{1}x_{2}, x_{1}x_{2}^{2}}, which is not an order ideal because x_{1}x_{2}^{2} has factor x_{2}^{2} which is not in the set. But if we take e_{1} = 3, e_{2} = 1 we get {1, x_{1}, x_{2}, x_{1}^{2}, x_{1}^{3}}, which is an order ideal.

Remark 4.15. Hilbert functions exhibiting the extreme behaviour in Theorems 4.12 and 4.13 in fact do exist. Suppose c > 0 is the proposed value of a Hilbert function in degree i. Let 𝒮 be the rev-lex-segment of degree i consisting of the c largest monomials of degree i in ℳ\underline{e}. Let M be the order ideal of all factors of elements of 𝒮 together with the set 𝒰 described in Theorem 4.13. Then R\underline{e}/I_{M} has Hilbert function H with H(i) = c, H(i − 1) the value given by Theorem 4.12 and H(i + 1) the value given by Theorem 4.13.

5. Binomial expansions

In this section \underline{e}, R\underline{e} and ℳ\underline{e} are as in the previous section. We will count the number of elements in the various rev-lex-segments discussed above, leading to binomial expansions similar to that used by Stanley in describing h^{<i>} in [5].

Now we count the number of elements in a deg-rev-lex segment. First a preliminary definition.

Definition 5.1. Let

\binom{e_{1}, …, e_{r}}{d}

denote the number of monomials of degree d in x_{1}, …, x_{r} in which the exponent of x_{i} does not exceed e_{i}. If d = 0 define the value to be 1.

We will refer to the \binom{e_{1},...,e_{r}}{d} as “binomials”, but note that \binom{e_{1}}{d} is not the usual binomial coefficient. It equals 1 if 0 ≤ d ≤ e_{1} and 0 if d > e_{1}. We will refer to d as the “denominator” of the binomial and e_{1}, …, e_{r} as the “numerator”. There does not seem to be a simple explicit expression for \binom{e_{1},e_{2},...,e_{r}}{d}. However there is a generating function, namely \binom{e_{1},e_{2},...,e_{r}}{d} is the coefficient of t^{d} in ∏_{i=1}^{r}(∑_{j=0}^{e_{i}} x^{j}).

Lemma 5.2. Let x^{α}(∈ ℳ\underline{e}) be a monomial of degree d in the x_{i} (1 ≤ i ≤ n), where α = (a_{1}, …, a_{s}, 0, …, 0), with 1 ≤ i ≤ s and a_{s} > 0 for some s satisfying 1 ≤ s ≤ n. Then the number of elements in L(x^{α}) is given by the following recursively defined binomial expansion.

(a)

\binom{e_{1}, …, e_{s}}{d}

if x^{α} is the smallest monomial in (ℳ\underline{e}′)_{d}, (\underline{e}′ = (e_{1}, …, e_{s})).

(b) otherwise

∑_{i=0}^{a_{s}−1} \binom{e_{0}, …, e_{s−1}}{d − i} + S

where S is the expansion for L(x^{β}) where β = (a_{1}, …, a_{s−1}, 0,

…, 0).

Definition 5.3. The expression given by Lemma 5.2 will be referred to as the degree d \underline{e}-binomial expansion of L(x^{α}) (or of the integer |L(x^{α})|).

Remark 5.4. If s = 1 we must have case (a) so the recursion terminates. If s > 1 then we have case (a) if and only if α = (0, …, 0, b_{i}, e_{i+1}, …, e_{s}, 0, …, 0) for some i, 1 ≤ i ≤ s with b_{i} +∑_{j=i+1}^{s} e_{j} = d. If e_{s} ≥ d then we have case (a) if and only if x^{α} = x_{s}^{d}.

Remark 5.5. The summation in (b) enumerates respectively the number of monomials in L(x^{α}) with no x_{s}, with x_{s} to the first power, the second power, respectively, up to exponent a_{s} − 1. The S term enumerates those monomials with factor x_{s}^{a_{s}}. We could also define the recursion in (b) as \binom{e_{0},...,e_{s−1}}{d} + S_{1} where S_{1} is the binomial expansion enumerating L(x^{α′}) where α′ = (a_{1}, …, a_{s} − 1, 0, …, 0). If we are given the cardinality a = |L(x^{α})| of the rev-lex-segment instead of its smallest element x^{α} we can obtain the same binomial expansion as follows. The sequence \{\binom{e_{1}}{d}, \binom{e_{1},e_{2}}{d}, \binom{e_{1},e_{2},e_{3}}{d}, …\} is strictly increasing once it becomes non-zero. If the n-th term is still 0 there are no monomials of degree d in x_{1}, …, x_{n} and L(x^{α}) is empty. Otherwise take the first term \binom{e_{1},...,e_{s}}{d} in the expansion to be the largest of \{\binom{e_{1}}{d}, \binom{e_{1},e_{2}}{d}, \binom{e_{1},e_{2},e_{3}}{d}, …, \binom{e_{1},e_{2},...,e_{n}}{d}\} that is less than or equal to a. If a = \binom{e_{1},...,e_{s}}{d} then we have case (a) of Lemma 5.2 and this is the entire binomial expansion. Otherwise repeat the process with a − \binom{e_{1},...,e_{s}}{d} using \{\binom{e_{1}}{d−1}, \binom{e_{1},e_{2}}{d−1}, \binom{e_{1},e_{2},e_{3}}{d−1}, …, \binom{e_{1},e_{2},...,e_{n}}{d−1}\}. We are done when the total of our expansion is a. (If the first non-zero value in \{\binom{e_{1}}{d}, \binom{e_{1},e_{2}}{d}, \binom{e_{1},e_{2},e_{3}}{d}, …, \binom{e_{1},e_{2},...,e_{n}}{d}\} is greater than a then, by Lemma 5.2 (b), take the first term in the expansion to be the last coefficient \binom{e_{1},...,e_{s}}{d} that has value 0).

Remark 5.6. Let a = |L(x^{α})| where α = (a_{1}, …, a_{r}, 0, …, 0) where r is the largest index such that a_{i} > 0. Then the degree d \underline{e}-binomial expansion of a has the following form. If x^{α} is the smallest monomial of degree d in x_{1}, …, x_{r} then there is one term (which we think of as 1 = a_{r+1} + 1) \binom{e_{1},e_{2},...,e_{r}}{d}. Otherwise there are a_{r} terms

∑_{i=0}^{a_{r}−1} \binom{e_{1}, e_{2}, …, e_{r−1}}{d − i}

then a_{r−1} terms

∑_{i=a_{r}}^{a_{r−1}+a_{r}−1} \binom{e_{1}, e_{2}, …, e_{r−2}}{d − i}

and so on, until the expansion terminates with case (a) of Lemma 5.2, in which case there is one extra term with the same numerator. The denominators are d, d − 1, …, successively decreasing by one, with the final denominator at least one. Each numerator e_{1}, …, e_{i−1} except the last occurs a_{i} ≤ e_{i} times. The final numerator e_{1}, …, e_{s} also occurs ≤ e_{s+1} times because if a_{s+1} = e_{s+1} we would have terminated earlier with case (a). Thus we obtain the expansion of [3, page 70]. (On our first reading of [3] we managed to misinterpret their expansion, and they have no explanation that we could have studied to clear up our confusion.) The form of the expansion is perhaps best understood with examples, which we give in the next section.

Remark 5.7. If in Lemma 5.2 some of the coordinates of α are greater than the corresponding e_{i} then the expansion described in the Lemma still gives the number of monomials in the rev-lex-segment consisting of all monomials in ℳ\underline{e} of degree d whose exponent vector is greater than α in the deg-rev-lex ordering of ℕ^{n}. Coordinates that are too large are taken into account automatically by the definition of the \binom{e_{1},...,e_{r}}{d}.

Definition 5.8. Let a, d ≥ 1. Then a<d> ; \underline{e} is the integer obtained by increasing by 1 all the denominators in the degree d \underline{e}-binomial expansion of a, and a\underline{e} ; <d> is the integer obtained by decreasing by 1 all the denominators in the degree d \underline{e}-binomial expansion of a.

Theorem 5.9. Let 𝒮 = L(x^{α}) be a rev-lex-segment of degree d as in Lemma 4.9. Suppose that the binomial expansion for c = |L(x^{α})| given by Lemma 5.2 is

\binom{e_{1}, …, e_{s}}{d} + ⋯ + \binom{e_{1}, …, e_{r}}{d − a}.

Then the rev-lex-segment 𝒯 (in degree d − 1) of Lemma 4.9 contains

c\underline{e} ; <d> = \binom{e_{1}, …, e_{s}}{d − 1} + ⋯ + \binom{e_{1}, …, e_{r}}{d − a − 1}

elements.

Proof. This follows from the definition of the expansion in Lemma 5.2 and the description of 𝒯 in Lemma 4.9. Each term in the expansion of L(x^{α}/x_{r}) enumerates monomials of degree one lower than the corresponding term for L(x^{α}) (involving the the same variables). □

Corollary 5.10. Suppose that the Hilbert function of a graded quotient of R\underline{e} has value c in degree d. Then the Hilbert function in degree d − 1 must have value at least c\underline{e} ; <d>.

Proof. This follows from Theorem 5.9 and Theorem 4.12. □

Theorem 5.11. Let 𝒮 = L(x^{α}) be a rev-lex-segment of degree d as in Lemma 4.10. Suppose that the binomial expansion for c = L(x^{α}) given by Lemma 5.2 is

\binom{e_{1}, …, e_{s}}{d} + ⋯ + \binom{e_{1}, …, e_{r}}{d − a}.

Then the rev-lex-segment 𝒰 (in degree d + 1) of Lemma 4.10 contains

c<d> ; \underline{e} = \binom{e_{1}, …, e_{s}}{d + 1} + ⋯ + \binom{e_{1}, …, e_{r}}{d − a + 1}

elements.

Proof. This follows from the definition of the expansion in Lemma 5.2 and the description of 𝒰 in Lemma 4.10 (together with Remark 5.7). Each term in the expansion of L(x_{r}x^{α}) enumerates monomials of degree one higher than the corresponding term for L(x^{α}) (involving the same variables). □

Corollary 5.12. Suppose that the Hilbert function of a graded quotient of R\underline{e} has value c in degree d. Then the Hilbert function in degree d + 1 can have value at most c<d> ; \underline{e}.

Proof. This follows from Theorem 5.11 and Theorem 4.13. □

Ben Richert and Sindi Sabourin have obtained [4] results which we think are essentially equivalent to Corollary 5.10 and Corollary 5.12, although the slides went by too fast to be sure. They also obtained the expansion method mentioned before Example 6.2. We believe that they used a different method of proof.

6. Examples

Example 6.1. Let \underline{e} be \{4, 3, 3, 2\} and x^{α} = x_{2}^{3}x_{3}^{2}x_{4}^{2} (so α = (0, 3, 2, 2)). Then x^{α} is not the smallest monomial of degree 7 in x_{1}, x_{2}, x_{3}, x_{4} so we are in case (b) of Theorem 5.2. The expansion starts out \binom{4,3,3}{7} enumerating monomials of degree 7 in x_{1}, x_{2}, x_{3} followed by \binom{4,3,3}{6} enumerating monomials of degree 6 in x_{1}, x_{2}, x_{3} (which are to be multiplied by x_{4}). Now we find the expansion of L(x_{2}^{3}x_{3}^{2}). Again we are in case (b), so we get 2 more terms \binom{4,3}{5} enumerating monomials of degree 5 in x_{1} and x_{2} (which are to be multiplied by x_{4}^{2}) and \binom{4,3}{4} enumerating monomials of degree 4 in x_{1} and x_{2} (which are to be multiplied by x_{3}x_{4}^{2}). We conclude with the expansion of L(x_{2}^{3}). This is the smallest monomial of degree 3 in x_{1} and x_{2} so we are in case (a) of Theorem 5.2, yielding the degree 7 \underline{e}-binomial expansion of x_{2}^{3}x_{3}^{2}x_{4}^{2} is

\binom{4, 3, 3}{7} + \binom{4, 3, 3}{6} + \binom{4, 3}{5} + \binom{4, 3}{4} + \binom{4, 3}{3} =

10+13+3+4+4. Note that indeed we have a_{4} = 2 terms with numerator 4 3 3, and a_{3} + 1 = 3 terms with numerator 4 3 (the extra term coming from the termination with case (a)) as observed in Remark 5.7. The total is 34, so x_{2}^{3}x_{3}^{2}x_{4}^{2} is the 34-th monomial in deg-rev-lex order, when powers are restricted to x_{1}^{4}, x_{2}^{3}, x_{3}^{3}, x_{4}^{2}.

Furthermore we have

34<7> ; \underline{e} = \binom{4, 3, 3}{8} + \binom{4, 3, 3}{7} + \binom{4, 3}{6} + \binom{4, 3}{5} + \binom{4, 3}{4} =

6 + 10 + 2 + 3 + 4 = 25 and

34\underline{e} ; <7> = \binom{4, 3, 3}{6} + \binom{4, 3, 3}{5} + \binom{4, 3}{4} + \binom{4, 3}{3} + \binom{4, 3}{2} =

13 + 14 + 4 + 4 + 3 = 38. Therefore if a graded quotient of k[x_{1}, x_{2}, x_{3}, x_{4}]/(x_{1}^{5}, x_{2}^{4}, x_{3}^{4}, x_{4}^{3}) has Hilbert function with value 34 in degree 7 then the Hilbert function has value at most 25 in degree 8 and at least value 38 in degree 6.

Here 𝒮 = L(x_{2}^{3}x_{3}^{2}x_{4}^{2}), 𝒯 = L(x_{2}^{2}x_{3}^{2}x_{4}^{2}) and 𝒰 can be enumerated as if formally 𝒰 = L(x_{2}^{4}x_{3}^{2}x_{4}^{2}). The terms of the binomial expansion of L(x_{2}^{2}x_{3}^{2}x_{4}^{2}) enumerate respectively monomials of degree 6 in x_{1}, x_{2}, x_{3}, degree 5 in x_{1}, x_{2}, x_{3}, degree 4 in x_{1}, x_{2}, degree 3 in x_{1}, x_{2}, and degree 2 in x_{1}, x_{2} (the last enumerating L(x_{2}^{2})), all of degree 1 lower than the corresponding term of expansion of L(x_{2}^{3}x_{3}^{2}x_{4}^{2}) illustrating the proof of Theorem 5.9. Similarly the terms in the binomial expansion of L(x_{2}^{4}x_{3}^{2}x_{4}^{2}) are of degree one higher than the corresponding terms in the expansion of L(x_{2}^{3}x_{3}^{2}x_{4}^{2}). Actually 𝒰 = L(x_{1}x_{2}^{3}x_{3}^{2}x_{4}^{2}), the enumeration of which gives the same expansion.

Note that the sequence \binom{e_{1},...,e_{r}}{i}, i ≥ 0 is the Hilbert function of R\underline{e} or equivalently of a complete intersection CI(e_{1} + 1, e_{2} + 1, …, e_{r} + 1) defined by a regular sequence consisting of r homogeneous polynomials of degrees e_{1}+1, …, e_{r}+1 in k[x_{1}, …, x_{r}]. This, together with the construction in Remark 5.5 starting from a = |L(x^{α})| suggests the following computation scheme for finding the degree d \underline{e}-binomial expansion of a. We illustrate it with Example 6.1 above, in which \underline{e} = \{4, 3, 3, 2\}. Make a table with rows CI(5), CI(5, 4), CI(5, 4, 4), CI(5, 4, 4, 3), the columns from left to right corresponding to degrees 0, 1, 2, . . ..

\begin{matrix}CI(5) & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ CI(5, 4) & 1 & 2 & 3 & \underline{4} & \underline{4} & \underline{3} & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ CI(5, 4, 4) & 1 & 3 & 6 & 10 & 13 & 14 & \underline{13} & \underline{10} & 6 & 3 & 1 & 0 & 0 \\ CI(5, 4, 4, 3) & 1 & 4 & 10 & 19 & 29 & 37 & 40 & 37 & 29 & 19 & 10 & 4 & 1 \end{matrix}

In finding the 7-binomial expansion of 34 we form the sequence \binom{4}{7}, \binom{4,3}{7}, \binom{4,3,3}{7}, \binom{4,3,3,2}{7} and select the largest which is less than or equal to 34. This is the degree 7 column 0 1 10 37, so start with 10 = \binom{4,3,3}{7}. Now subtract 34 − 10 = 24 and go down the degree 6 column, 0 2 13 40, selecting 13 = \binom{4,3,3}{6}, which is the largest which is less than or equal to 24. Now subtract 24 − 13 = 11 and go down the degree 5 column selecting 3 = \binom{4,3}{5}. Subtract 11 − 3 = 8 and go down the degree 4 column selecting 4 = \binom{4,3}{4}, subtract yielding 8 − 4 = 4, then the degree 3 column selecting 4 = \binom{4,3}{3} which completes the expansion. These entries in the table are underlined. To find 34<7> ; \underline{e} shift each number one unit to the right and add, yielding 34<7> ; \underline{e} = 6 + 10 + 2 + 3 + 4 = 25 as obtained in Example 6.1. To find 34\underline{e} ; <7> shift each number one unit to the left and add, obtaining 34\underline{e} ; <7> = 13 + 14 + 4 + 4 + 3 = 38, also as was obtained in Example 6.1. Now we work out a couple of other examples, using the table above.

Example 6.2. Let \underline{e} = \{4, 3, 3, 2\} as above, and x^{α} = x_{1}x_{4}^{2}. The degree 3 \underline{e}-binomial expansion of L(x^{α}) is \binom{4,3,3}{3} + \binom{4,3,3}{2} + \binom{4}{1} = 10 + 6 + 1 (the 10 from the degree 3 column (counting all monomials of degree 3 in x_{1}, x_{2}, x_{3}), the 6 from the degree 2 column (counting all monomials of degree 2 in x_{1}, x_{2}, x_{3} which are to be multiplied by x_{2}), and the 1 from the degree 1 column (counting x_{1}x_{4}^{2} itself). These entries are in bold in the table. This gives 17 = 10 + 6 + 1. Shifting left in the table gives 17\underline{e} ; <3> = 6 + 3 + 1 = \binom{4,3,3}{2} + \binom{4,3,3}{1} + \binom{4}{0}. Here 𝒯 = L(x_{4}^{2}) and L(x_{4}^{2}) has been enumerated as 6 monomials of degree 2 in x_{1}, x_{2}, x_{3}, three monomials of degree 1 in x_{1}, x_{2}, x_{3} (which are to be multiplied by x_{4}) and one monomial 1 of degree 0 (which is to be multiplied by x_{4}^{2}). This is not the “official” Lemma 5.2 expansion of L(x_{4}^{2}) which would be \binom{4,3,3}{2} = 10, but it is correct enumeration. If we shift right in the table we obtain 17<3> ; \underline{e} = 13 + 10 + 1 = \binom{4,3,3}{4} + \binom{4,3,3}{3} + \binom{4}{2}. The 13 enumerates all monomials of degree 4 in x_{1}, x_{2}, x_{3} of which there are only 13 because the exponent of x_{2} and x_{3} is at most 3, the 10 enumerates all monomials of degree 3 in x_{1}, x_{2}, x_{3} (which are to be multiplied by x_{4}) and the 1 enumerates x_{1}^{2}x_{4}^{2} itself (1 monomial of degree 2 in x_{1}, which is multiplied by x_{4}^{2}). Here 𝒰 = L(x_{1}^{2}x_{4}^{2}).

Example 6.3. Let \underline{e} = \{4, 3, 3, 2\} as above, and x^{α} = x_{1}^{4}x_{2}^{2}x_{4}. The degree 7 \underline{e}-binomial expansion of 𝒮 = L(x^{α}) is \binom{4,3,3}{7}+\binom{4}{6}+\binom{4}{5}+\binom{4}{4} = 10 + 0 + 0 + 1 = 11 (the 10 from the degree 7 column (counting all monomials of degree 7 in x_{1}, x_{2}, x_{3}), the first 0 from the degree 6 column (counting all monomials of degree 6 in x_{1}, of which there are none because e_{1} = 4, but if there were any they would be multiplied by x_{4}), the second 0 counting all monomials of degree 5 in x_{1} (again there are none, but if there were any they would be multiplied by x_{2}x_{4}), and the 1 counting all monomials of degree 4 in x_{1}, of which there is 1, namely x_{1}^{4} which when multiplied by x_{2}^{2}x_{4} yields x^{α}. Shifting left in the table gives 11\underline{e} ; <7> = 12 + 0 + 1 + 1 = \binom{4,3,3}{6} + \binom{4}{5} + \binom{4}{4} + \binom{4}{3}. Here 𝒯 = L(x_{1}^{3}x_{2}^{2}x_{4}) and L(x_{1}^{3}x_{2}^{2}x_{4}) has been enumerated as 13 monomials of degree 6 in x_{1}, x_{2}, x_{3}, zero monomials of degree 5 in x_{1} (which would be multiplied by x_{4} if there were any), one monomial x_{1}^{4} of degree 4 in x_{1} (which is to be multiplied by x_{2}x_{4}) and one monomial x_{1}^{3} of degree 3 in x_{1} (which is to be multiplied by x_{2}^{2}x_{4} yielding x_{1}^{3}x_{2}^{2}x_{4} itself). Note that we have to keep \binom{4}{6} and \binom{4}{5} in the degree 7 binomial expansion of 11 even though they are 0 in order to correctly compute 11\underline{e} ; <7> by lowering denominators (actually keeping \binom{4}{5} suffices here, but it seems preferable to keep \binom{4}{6} as well). If we shift right in the table we obtain 11<7> ; \underline{e} = 6 + 0 + 0 + 0 = \binom{4,3,3}{8} + \binom{4}{7} + \binom{4}{6} + \binom{4}{5} = 6. This is all monomials of degree 8 in x_{1}, x_{2}, x_{3}, the smallest of which is x_{1}^{2}x_{2}^{3}x_{3}^{3} so here 𝒰 = L(x_{1}^{2}x_{2}^{3}x_{3}^{3}). As noted in the proof of Lemma 4.10 and Remark 5.7 this expansion of 11<7> ; \underline{e} is obtained by enumerating the formal expression L(x_{1}^{5}x_{2}^{2}x_{4}) in the usual way. The three 0’s in the resulting expansion of 11<7> ; \underline{e} reflect the fact that there are no monomials of degree 7 in ℳ\underline{e} involving only x_{1} and x_{2} which are formally greater than or equal to x_{1}^{5}x_{2}^{2}. In fact the next monomial of degree 8 in ℳ\underline{e} smaller than x_{1}^{2}x_{2}^{3}x_{3}^{3} is x_{1}^{4}x_{2}^{3}x_{4} and this contains a degree 7 factor x_{1}^{3}x_{2}^{3}x_{4} that is not in L(x^{α}) so 𝒰 cannot be any larger than L(x_{1}^{2}x_{2}^{3}x_{3}^{3}). The official expansion of L(x_{1}^{2}x_{2}^{3}x_{3}^{3}) is just the single term \binom{4,3,3}{8} and we must use it if we go back down using Theorem 5.9, obtaining 𝒯 (𝒰 (L(x_{1}^{4}x_{2}^{2}x_{4}))) = 𝒯 (L(x_{1}^{2}x_{2}^{3}x_{3}^{3})) = L(x_{1}x_{2}^{3}x_{3}^{3}).

7. Recovering Macaulay’s Growth Conditions

If we make the e_{i} (which we will informally write ∞) larger than the degree under discussion we recover the usual form of Macaulay’s Theorem. Thus \binom{∞,...,∞}{d} (with n ∞’s in the numerator) means the number of monomials of degree d in n variables (without restriction on exponents) which is C(d + n − 1, n − 1), where we write the usual binomial coefficient \frac{a!}{b!(a−b)!} as C(a, b) to avoid conflict with the notation in Definition 5.1. The expansion of Lemma 5.2 becomes the usual binomial expansion mentioned in [5, page 60]. Theorems 5.9 and 5.11 [1] then become

Theorem 7.1. Let R be a graded algebra over a field k, generated by elements of degree 1. Suppose that the Hilbert function of R has value h in degree i. Suppose that h has binomial expansion

h = C(n_{i}, i) + C(n_{i−1}, i − 1) + ⋯ + C(n_{j}, j)

where n_{i} > n_{i−1} > ⋯ n_{i} ≥ j ≥ 1. Define

h^{<i>} = C(n_{i}, i + 1) + C(n_{i−1}, i) + ⋯ + C(n_{j}, j + 1)

and

h_{<i>} = C(n_{i}, i − 1) + C(n_{i−1}, i − 1) + ⋯ + C(n_{j}, j − 1).

Then (a) The Hilbert function of R in degree i+1 has value at most h^{<i>}.

(b) The Hilbert function of R in degree i−1 has value at least h_{<i>}. Furthermore the two extreme cases are realized by the quotient of a polynomial ring by a lex-segment ideal.

Part (a) of the Theorem is of course very well known and is stated explicitly in [5, Theorem 2.2(c)]. Part (b) is less often stated.

References

[1] G.F. Clements and B. Lindström. A Generalization of a Combinatorial Theorem of Macaulay. J. of Combinatorial Theory, 7:230–238, 1969.

[2] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties and Algorithms - An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer-Verlag, New York, second edition edition, 1997.

[3] C. Greene and D.J. Kleitman. Proof techniques in the theory of finite sets. In Gian-Carlo Rota, editor, Studies in Combinatorics, pages 22–79. The Mathematical Association of America, 1978.

[4] L. Sabourin. A Study of Lex Plus Powers Ideals, talk at Route 81 Conference, Syracuse, October 2003.

[5] R.P. Stanley. Hilbert Functions of Graded Algebras. Advances in Mathematics, 28:57 – 83, 1978.