ON SOME PARTIAL ORDERS ASSOCIATED TO GENERIC INITIAL IDEALS

JAN SNELLMAN

Abstract. We study two partial orders on [x_{1}, …, x_{n}], the free abelian monoid on {x_{1}, …, x_{n}}. These partial orders, which we call the “strongly stable” and the “stable” partial order, are defined by the property that their filters are precisely the strongly stable and the stable monoid ideals. These ideals arise in the study of generic initial ideals.

1. Introduction

So called strongly stable (or Borel) monomial ideals are of interest because they appear as generic initial ideals [9, 10, 14, 7]. They have been used to give new proofs of the Macaulay and Gotzmann theorems for the growth of Hilbert series, and to extend these results to related rings [4, 2, 11]. A related class of ideals, the so called stable monomial ideals, are also of interest [8].

A subset V ⊂ [x_{1}, …, x_{n}]_{d} (of the set of monomials of total degree d in n variables) is strongly stable (or Borel) if whenever a monomial m belongs to V, then \frac{x_{i}}{x_{j}} m ∈ V for all 1 ≤ i < j ≤ n such that x_{j} |m. A monoid ideal I ⊂ [x_{1}, …, x_{n}] in the free abelian monoid on n letters is strongly stable iff I_{d} is strongly stable for all d). The anti-symmetric binary relation on [x_{1}, …, x_{n}] which consists of all such pairs (\frac{x_{i}}{x_{j}} m, m) is usually called the relation of elementary moves. As observed in [16], V is strongly stable iff it is a filter wrt the poset A_{n,d} which is the reflexive and transitive closure of the elementary moves relation.

Also in [16], the problem of determining all Borel monomial ideals with the same h-vector as of certain Artinian algebras is considered. The authors show that the problem can be reduced to the enumeration of all Borel subsets of a fixed cardinality. Since Borel subsets are precisely the filters of A_{n,d}, one is interested in studying the poset of filters of A_{n,d}. We show that this latter poset is isomorphic to the poset of certain hyper-partitions. In particular, for n = 3, we obtain a bijection between Borel subsets of cardinality v of monomials of degree d and numerical partitions of v into distinct parts not exceeding d + 1.

Before arriving at this result, we must conduct a study of the poset A_{n,d} itself. We find that A_{n,d} is a distributive lattice, namely the lattice of Ferrer’s diagrams that fit into a (n−1)×d box. It is therefore self-dual, ranked with the rank function given by the q-binomial coefficients, rank-symmetric, et cetera.

Date: April 26, 2000.

1991 Mathematics Subject Classification. 06A07,05A17 (Primary) 13F20 (Secondary).

Key words and phrases. Generic initial ideals, Young lattice, Borel subsets.

The author was supported by a grant from Svenska institutet and by grant n. 231801F from Centre International des Etudiants et Stagiaires.

Next, we set out to make a partial order on [x_{1}, …, x_{n}] such that its filters are precisely the Borel monoid ideals. To accomplish this, one must involve the divisibility partial order D, since a monoid ideal in [x_{1}, …, x_{n}] is nothing but a filter wrt D. We denote by A_{n,·} the reflexive-transitive closure of the union of D and A_{n,d}, for all d. Since it has been obtained by “gluing” together all A_{n,d} by divisibility, this poset has exactly the Borel monoid ideals as its filters. It is a distributive lattice intimately related to the Young lattice. Somewhat surprisingly, it turns out that this poset is also the intersection of all term orders on [x_{1}, …, x_{n}] which restrict to the correct ordering of the variables. This result can be regarded as an marginal note to the well-known classification of termorders [18].

Clearly, A_{n,·} is in a natural way included in A_{n+1,·}. Passing to the inductive limit, we get yet another interesting poset, once again a distributive lattice, but this time not quite the same thing as the Young lattice; however, if we order our variables so that x_{1} is the smallest rather than the largest variable, and carry out the above construction, we do get the full Young lattice.

Similarly, one may consider the stable relation B_{n,d} on [x_{1}, …, x_{n}]_{d}. Here, only the smallest occurring variable in the monomial is allowed to be replaced with something larger. This seemingly inconsequential change yields a poset drastically different from the strongly stable poset: it is a lattice, which however is not distributive, not even modular, and which is probably not isomorphic to any of the classic posets. We give an explicit description of the meet operation on B_{n,d}.

As for the poset of filters of B_{n,d}, we do not obtain such a nice description as for the strongly stable case, but for the special case n = 3, d > v we show that the number of stable subsets of cardinality v is equal to the number of fountains of v coins.

1.1. Acknowledgement. The connection between A_{n,d} and the distributive lattice of Ferrer’s diagrams that fit inside an (n − 1) × d box was pointed out by Anders Björner.

2. Multiplicative relations and multiplicative partial orders

We denote by ℕ^{+} = {1, 2, … } the set of positive integers, and by ℕ = {0, 1, 2, … } the set of non-negative integers. For relations, partial orders, lattices, and commutative semigroups, we will endeavour to follow the terminology in [12, 6, 13].

We mean by a binary relation R on a set M a subset of M × M. If (a, b) ∈ R we sometimes write aRb, or say that a ≥ b with respect to R.

Definition 2.1. For any binary relation R, we denote by rtr(R) the reflexive and transitive closure of R.

Definition 2.2. If R is a binary relation on a set A, and if B ⊂ A, then we denote the restriction of R to B by R_{|_{B}}.

Definition 2.3. If M is a cancellative, torsion free, reduced abelian monoid, and R is an anti-symmetric binary relation on M, then R is said to be (strongly) multiplicative if the following condition holds:

∀m, m′, t ∈ M : (m, m′) ∈ R ⟹ (mt, m′t) ∈ R  (1)

A relation S on M which is contained in some strongly multiplicative relation is called weakly multiplicative.

We will need the following theorem, which follows immediately from [12, Corollary 3.5]

Theorem 2.4. Let M be a abelian, cancellative, torsion-free monoid, and let R be a strongly multiplicative partial order on M. Suppose that x, y ∈ M and that {x^{n}, y^{n}} is an antichain in M for all n ∈ ℕ^{+}. Then R can be extended to a multiplicative total order R̃ such that (x, y) ∈ R̃.

3. Definition of the stable and the strongly stable partial order

Let X = {x_{1}, x_{2}, x_{3}, … }, and let, for n ∈ ℕ^{+}, X^{n} = {x_{1}, …, x_{n}}. Denote by M the free abelian monoid on X, and by M^{n} or [x_{1}, …, x_{n}] the free abelian monoid on X^{n}. For d ∈ ℕ we denote by M_{d} and M_{d}^{n} the subsets consisting of elements of total degree d. We will occasionally use [x_{1}, …, x_{n}]_{d} as a synonym for M_{d}^{n}. If m ∈ M then we define Supp(m) = { i ∈ ℕ^{+} x_{i} |m }, and γ(m) = max(Supp(m)), with the convention that γ(1) = 0.

Definition 3.1. Let n, d ∈ ℕ. The strongly stable partial order A_{n,d} on M_{d}^{n} is the reflexive-transitive closure of the set of all pairs

A_{n,d}^{∘} = \{ (m, m′) ∈ M_{d}^{n} × M_{d}^{n} ∃i, j : i < j, m = \frac{x_{i}}{x_{j}} m′ \}  (2)

Definition 3.2. Let n, d ∈ ℕ. The stable partial order B_{n,d} on M_{d}^{n} is the reflexive-transitive closure of the set of all pairs

B_{n,d}^{∘} = \{ (m, m′) ∈ M_{d}^{n} × M_{d}^{n} ∃i : i < γ(m′), m = \frac{x_{i}}{x_{γ(m′)}} m′ \}  (3)

So x_{1}^{2}x_{3} ≥ x_{1}x_{2}x_{3} with respect to A_{3,3}^{∘}, but not with respect to B_{3,3}^{∘}.

Lemma 3.3. A_{n,d} and B_{n,d} are partial orders. B_{n,d} ⊂ A_{n,d}, and the inclusion is strict for n > 2, d > 2.

Proof. The last assertions are obvious, and hence it is enough to show that A_{n,d} is anti-symmetric. Let f : M_{d}^{n} → ℕ be defined by

f(x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}}) = α_{1} + 2α_{2} + ⋯ + nα_{n}.

Then every substitution

x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} → x_{1}^{α_{1}} ⋯ x_{i−1}^{1+α_{i−1}}x_{i}^{α_{i}−1} ⋯ x_{n}^{α_{n}}

strictly lowers the f-value. Hence, the reflexive-transitive closure of A_{n,d}^{∘} is anti-symmetric.

We observe that x_{1}^{d} and x_{n}^{d} are the unique maximal and minimal elements of both A_{n,d} and B_{n,d}.

Definition 3.4. We denote the divisibility partial order on M by D. Abusing our notations, we denote any restriction of D to a subset of M simply by D.

Thus m ≤ m′ with respect to D if and only if m |m′, that is, if and only if m′ = tm for some t.

Proposition 3.5. For d, n, n′ ∈ ℕ^{+}, n ≤ n′, we have that A_{n′,d}_{|_{M^{n}_{d}}} = A_{n,d}, and similarly for B.

Theorem 3.6. The sets

A_{·,·} := rtr(D ∪ ⋃_{n,d} A_{n,d})  (4)
B_{·,·} := rtr(D ∪ ⋃_{n,d} B_{n,d})  (5)

are partial orders on M; A_{·,·} is strongly multiplicative and contains B_{·,·}, which is therefore weakly multiplicative. We define the following restrictions:

A_{·,d} = A_{·,·}_{|_{M_{d}}} = ⋃_{n} A_{n,d} ⊂ M_{d} × M_{d}  (6)
B_{·,d} = B_{·,·}_{|_{M_{d}}} = ⋃_{n} B_{n,d} ⊂ M_{d} × M_{d}  (7)
A_{n,·} = A_{·,·}_{|_{M^{n}}} = D ∪ ⋃_{d} A_{n,d} ⊂ M^{n} × M^{n}  (8)
B_{n,·} = B_{·,·}_{|_{M^{n}}} = D ∪ ⋃_{d} B_{n,d} ⊂ M^{n} × M^{n}  (9)

Then A_{n,·} is strongly multiplicative, whereas B_{n,·} is weakly multiplicative.

Proof. It is enough to show that A_{·,·} and B_{·,·} are partial orders, and that A_{·,·} is strongly multiplicative. Define a function

g : M → ℤ × ℤ
g(x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}}) = (−α_{1} − ⋯ − α_{n}, α_{1} + 2α_{2} + ⋯ + nα_{n}),

and order ℤ × ℤ lexicographically. Then substitutions of the form

x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} ↦ x_{1}^{α_{1}} ⋯ x_{i−1}^{1+α_{i−1}}x_{i}^{α_{i}−1} ⋯ x_{n}^{α_{n}}
x_{1}^{α_{1}} ⋯ x_{i}^{α_{i}} ⋯ x_{n}^{α_{n}} ↦ x_{1}^{α_{1}} ⋯ x_{i}^{1+α_{i}} ⋯ x_{n}^{α_{n}}

leads to a g-value which is strictly smaller. Hence, A_{·,·} is anti-symmetric and therefore a partial order.

If (m, m′) ∈ A_{·,·} then there is a finite chain

m → m_{1} → m_{2} → ⋯ → m′

where each arrow is a substitution of one of the two types above. It is easily seen that both such substitutions remain valid after multiplication by an arbitrary element t ∈ M, hence (tm, tm′) ∈ A_{·,·}.

4. The râison d’être for the strongly stable and the stable partial orders: Borel ideals and stable ideals

4.1. Borel ideals and stable ideals.

Definition 4.1. Let n, d be positive integers. A subset U ⊂ M_{d} is called strongly stable or Borel iff

m ∈ U, x_{j} |m, 1 ≤ i ≤ j ≤ n ⟹ m\frac{x_{i}}{x_{j}} ∈ U.

A monoid ideal I ⊂ M is called a strongly stable monoid ideal or a Borel monoid ideal iff I ∩ M_{v} is Borel for all positive integers v.

Borel subsets of M_{d}^{n} and Borel ideals in M^{n} are defined analogously.

If K is a field, then a monomial ideal J ⊂ KM ≃ K[x_{1}, x_{2}, x_{3}, …] is called Borel (or strongly stable) if J ∩ M is a Borel monoid ideal, and similarly for monomial ideals in KM^{n} ≃ K[x_{1}, …, x_{n}].

A reason to study Borel ideals is following theorem (see [9, 10, 14, 7, 3]). Recall that a term order on M^{n} is a strongly multiplicative total order ≤ such that 1 is the smallest element. Given a term order ≤ and a polynomial f ∈ K[x_{1}, …, x_{n}], the initial monomial in_{≤}(f) is the largest ( wrt ≤) monomial occurring in f. If J ⊂ K[x_{1}, …, x_{n}] is an ideal, then the initial ideal in_{≤}(J) is the ideal generated by { in_{≤}(f) f ∈ J }. Finally, the general linear group GL_{n} acts on the n-dimensional K-vector space V spanned by the variables in K[x_{1}, …, x_{n}], and since K[x_{1}, …, x_{n}] is the symmetric algebra on V, this action can be extended to K[x_{1}, …, x_{n}]. Explicitly, if GL_{n} ∋ g = (g_{ij}) then g acts on the monomial x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} by

g (∏_{i=1}^{n} x_{i}^{α_{i}}) = ∏_{i=1}^{n} g(x_{i})^{α_{i}} = ∏_{i=1}^{n} (∑_{j=1}^{n} g_{ij}x_{j})^{α_{i}},

and this action is then extended K-linearly.

Theorem 4.2 (Galligo, Bayer-Stillman). Let ≥ be a term order with x_{1} ≥ ⋯ ≥ x_{n}, let K be a field of characteristic 0, let n be a positive integer, and let J ⊂ K[x_{1}, …, x_{n}] be a homogeneous ideal. Then there is a monomial ideal gin_{≥}(J), the generic initial ideal of J, and a Zariski-open subset U ⊂ GL_{n}, such that in(g(J)) = gin_{≥}(J) for all g ∈ U. Furthermore gin_{≥}(J) ∩ M^{n} is a Borel monoid ideal.

Definition 4.3. Let n, d be positive integers. A subset U ⊂ M_{d} is called stable iff

m ∈ U, i ≤ γ(m) ⟹ m\frac{x_{i}}{x_{γ(m)}} ∈ U.

A monoid ideal I ⊂ M is called a stable monoid ideal iff I ∩ M_{v} is Borel for all positive integers v.

Stable subsets of M_{d}^{n} and stable ideals in M^{n} are defined analogously.

If K is a field, then a monomial ideal J ⊂ KM ≃ K[x_{1}, x_{2}, x_{3}, …] is called stable if J ∩ M is a stable monoid ideal, and similarly for monomial ideals in KM^{n} ≃ K[x_{1}, …, x_{n}].

Stable ideals have minimal free resolutions of a particularly nice form [8], and are therefore interesting.

The following theorem motivates the study of the stable and strongly stable partial orders:

Theorem 4.4. Let d, n be positive integers.

(i) A subset I ⊂ M is a monoid ideal iff it is a filter wrt the partial order D. (ii) A subset I ⊂ M^{n} is a monoid ideal iff it is a filter wrt the partial order

D. (iii) A subset U ⊂ M_{d} is Borel iff it is a filter wrt the partial order A_{·,d}. (iv) A subset U ⊂ M_{d}^{n} is Borel iff it is a filter wrt the partial order A_{n,d}.

(v) A subset I ⊂ M is a Borel monoid ideal iff it is a filter wrt the partial order A_{·,·}.

(vi) A subset I ⊂ M^{n} is a Borel monoid ideal iff it is a filter wrt the partial

order A_{n,·}. (vii) A subset I ⊂ M is a stable monoid ideal iff it is a filter wrt the partial

order B_{·,·}. (viii) A subset I ⊂ M^{n} is a stable monoid ideal iff it is a filter wrt the partial

order B_{n,·}.

Proof. (i) and (ii) are well-known, and (iii) and (iv) is immediate from the definitions. (v), (vi), (vii), and (viii) are similar; we prove (v).

If I is a filter wrt A_{·,·}, then since D ⊂ A_{·,·}, it is a filter wrt D, hence I is a monoid ideal. For any d ∈ ℕ^{+} we have that I ∩ M_{d} is a filter wrt A_{·,d}, since A_{·,·}_{|_{M_{d}}} = A_{·,d}. This shows that I_{d} is Borel. Hence, I is a Borel monoid ideal.

Conversely, if I is a Borel monoid ideal, we want to show that I is a filter wrt A_{·,·}. Since it is a monoid ideal, it is a filter wrt D. By definition, for each d we have that I_{d} is a filter wrt A_{·,d}. Since A_{·,·} is the smallest partial order which contains D and all A_{·,d}, it follows that I is a filter wrt A_{·,·}.

5. Properties of the strongly stable partial order

5.1. Properties of infinite strongly stable partial orders. We denote the dual of any partial order P by P^{∗}.

Definition 5.1. For n, d ∈ ℕ we define

C_{n,d} = A_{n,d}^{∗}  (10)
C_{·,d} = ⋃_{n} C_{n,d} ⊂ M_{d} × M_{d}  (11)
C_{n,·} = rtr(D ∪ ⋃_{d} C_{n,d}) ⊂ M^{n} × M^{n}  (12)
C_{·,·} := rtr(D ∪ ⋃_{n,d} C_{n,d})  (13)

Clearly, C_{n,·} ≃ A_{n,·} for any n, because we can simply rename the variables according to the bijection x_{i} ↔ x_{n+1−i}. However, A_{·,·} ≄ C_{·,·}: C_{·,·} has a smallest element, 1, and an element covering it, x_{1}. A_{·,·}, on the other hand, has a smallest element, 1, but no element covering it.

We denote by Y the Young lattice of decreasing, eventually zero sequences of non-negative integers, ordered by component-wise inclusion (see [1] for a more thorough treatment).

Theorem 5.2. C_{·,·} ≃ Y.

Proof. To the monomial x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} we associate the Ferrers diagram consisting of α_{n} rows of length n, α_{n−1} rows of length n − 1, and so on. This is clearly a bijection between M and Y. We now show that it is isotone.

Consider all relations of the following two types:

1. x_{i}m ↦ x_{i+1}m,

2. m ↦ x_{i}m. These two relations generate the partial order. One sees that type 1 corresponds to enlarging the topmost row of the rows with i element with 1 element, and that type 2 corresponds to inserting a row with i elements. Therefore, the map is isotone. Furthermore, since these two types of operations on Ferrers diagrams generate the Young lattice, the inverse is isotone as well.

Corollary 5.3. C_{·,·} is a distributive lattice. For any n, d ∈ ℕ, the posets A_{n,·} ≃ C_{n,·}^{∗} and A_{n,d} ≃ C_{n,d}^{∗} are distributive lattices, isomorphic to the set of Ferrers diagrams with at most n columns, or with at most n columns and exactly d rows, respectively.

Proposition 5.4. For any positive integers v, w, the subset of all Ferrers diagrams with exactly v rows is a poset isomorphic to the set of all Ferrers diagrams with at most v rows. Furthermore, the subset of all Ferrers diagrams with at most w columns and exactly v rows is isomorphic to the set of all Ferrers diagrams which fit inside a v × (w − 1) box.

Proof. If a Ferrers diagram has exactly v rows, then its first column has length v. Removing this column, one gets a Ferrers diagrams with one less column, and with at most v rows. This establishes the desired bijections, which are isotone with isotone inverses.

The situation for A_{·,·} is different, but similar.

Theorem 5.5. The poset (M, A_{·,·}) is a distributive lattice, isomorphic to the set of all weakly increasing, eventually constant functions ℕ^{+} → ℕ, ordered by component-wise inclusion.

Sketch of proof. Use the map

Ξ : M → ℕ^{ℕ^{+}}
x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} ↦ (α_{1}, α_{1} + α_{2}, …, α_{1} + ⋯ + α_{n}, α_{1} + ⋯ + α_{n}, …)

It is not hard to see that Ξ is injective, and that its image is all weakly increasing sequences which are eventually constant. Furthermore, one can convince oneself that it is isotone: the operation m → x_{i}m maps to the operation of adding the sequence B[i] which is 1 from i and onward and zero before that, and the operation m → (x_{i}/x_{i+1})m maps to the operation of inserting a block of height and width 1, at position i + 1. Formally, the sequence (…, b_{i}, b_{i+1}, b_{i+2}, …), which is required to have a “jump” between i and i + 1, that is, b_{i} < b_{i+1}, is replaced with the sequence (…, 1 + b_{i}, b_{i+1}, b_{i+2}, …).

The hard part is showing that the inverse ξ is isotone. For this, one need to show that the two operations of adding sequences of the form B[i], and inserting a single block at a “jump”, generates the order relation for weakly increasing, eventually constant sequences. One can prove this by induction over the eventually constant value, and over the point from which it becomes constant.

Corollary 5.6. For any n, d ∈ ℕ, the posets A_{n,·} and A_{·,d} are distributive sublattice of the distributive lattice A_{·,·}. They are isomorphic to the following two subsets of the set of all weakly increasing, eventually constant functions ℕ^{+} → ℕ, ordered by point-wise comparison:

• The set Ξ(M^{n}) of such functions f with f(n) = lim_{t→+∞} f(t),

• The set Ξ(M_{d}) of such functions f with d = lim_{t→+∞} f(t).

Another result that follows immediately from the above description is the following:

Corollary 5.7. If x, y ∈ M and {x, y} is an antichain wrt A_{·,·} then so is {x^{n}, y^{n}}, for all n ∈ ℕ^{+}.

Proof. By the previous theorem this is translated into the following assertion: if f, g ∈ Ξ(M) are incomparable, then so is nf and ng. Now, f, g are incomparable iff there exists a, b ∈ ℕ^{+} with f(a) > g(a), f(b) < g(b), and this implies that nf(a) > ng(a), nf(b) < ng(b), showing that nf and ng are incomparable.

Proposition 5.8. For any positive integer v, (M^{v}, A_{v,·}) and (M_{v}, A_{·,v}) are dual posets.

Proof. It will suffice to give an antitone bijection τ with antitone inverse τ^{−1} between M^{v} and Ξ(M_{v}). This map is defined as follows. Take

â = (a_{1}, …, a_{v}, 0, 0, …) ∈ M^{v}.

Put ℓ = |â| = ∑_{i=1}^{v} a_{i}. Define

τ(â) = (b_{1}, …, b_{ℓ}, b_{ℓ}, …) ∈ Ξ(M_{v}),

with

b_{i} = \begin{cases}0 & i ≤ a_{1} \\ 1 & a_{1} < i ≤ a_{1} + a_{2} \\ ⋮ & ⋮ \\ v − 1 & a_{1} + ⋯ + a_{v−1} < i ≤ a_{1} + ⋯ + a_{v} \\ v & i > ℓ \end{cases}

That is, τ(â) has a_{1} zeroes, a_{2} ones, and so on, and takes on the constant value v at position ℓ and onward. It is easily seen that τ is bijective, and it is fact also antitone with antitone inverse.

For v = 2, the (beginning of) the Hasse diagrams for these two infinite posets are depicted in Figure 1.

[figure: 1; x_{2}; x_{1}; x_{2}^{2}; x_{1}x_{2}; x_{2}^{3}; (a) A_{2,·}.; x_{1}^{2}; x_{1}x_{2}; x_{2}^{2}; x_{1}x_{3}; x_{2}x_{3}; x_{1}x_{4}; (b) A_{·,2}]

Figure 1. The Hasse diagrams for the strongly stable order on 2 variables, or on monomials of degree 2.

5.2. Properties of finite strongly stable partial orders. We fix positive integers n, d, and study A_{n,d} and A_{n,d}^{∘}.

We note that A_{1,d} is a singleton for all d, and that A_{2,d} is a chain for all d. The relation A_{3,d}^{∘} and the Hasse diagrams of A_{3,d} looks as Figure 2.

We recall that C_{n,d} ≃ A_{n,d}, so that A_{n,d} is self-dual and isomorphic with the set of all Ferrers diagrams which fits inside a d × (n − 1) box, ordered by inclusion.

Definition 5.9. The q-binomial, or Gaussian polynomials are defined as

[ \begin{matrix}a + b \\ a \end{matrix} ]_{q} = \frac{(1 − q^{a+b})(1 − a^{a+b−1}) ⋯ (1 − q^{a+1})}{(1 − q^{b})(1 − q^{b−1}) ⋯ (1 − q)} =

= c_{0}^{(a,b)} + c_{1}^{(a,b)}q + ⋯ + c_{N}^{(a,b)}q^{N} ∈ ℤ[q]. (14)

The coefficients c_{i}^{(a,b)} are called the q-binomial coefficients.

We list some well-known properties of the poset F_{a,b} ≃ (M_{b}^{a+1}, rtr(A_{a+1,b})) of all Ferrers diagrams that fit inside an a × b rectangle. For the definition of the height, width and dimension of a finite partially ordered set, see [19].

• The poset F_{a,b} is a ranked distributive lattice, with rank function f(i) = c_{i}^{(a,b)}.

• The ranked poset F_{a,b} is rank unimodal, rank symmetric, and Sperner.

• F_{a,b} has dimension a, height ab, and width c_{v}^{(a,b)}, where v = ⌊ab/2⌋.

Corollary 5.10. For positive integers n, d ≥ 2, the poset A_{n,d} has dimension n − 1, height (n − 1)d, and width c_{w}^{(n−1,d)}, where w = ⌊(n − 1)d/2⌋.

[figure]
(a) The graph of A_{3,d}^{∘}. Multiplication with \frac{x_{1}}{x_{3}} is
→, multiplication with \frac{x_{2}}{x_{3}} is ↑, multiplication with
\frac{x_{1}}{x_{2}} is ↘.

[figure]

(b) The Hasse diagram of A_{3,d}.

Figure 2. The strongly stable relation and partial order for n = 3.

5.3. Relation to term orders. We mean by a term order a strongly multiplicative total order on M or on M^{n}, with 1 < m for all m ≠ 1.

Definition 5.11. Let n be a positive integer. Denote by 𝔗 the set of all term orders orders R on M such that x_{1} R x_{2} R x_{3} R · · ·. Similarly, denote by 𝔘 the set of all term orders S on M^{n} such that x_{1} S x_{2} S x_{3} S ⋯ Sx_{n}.

Theorem 5.12. Let n be a positive integer. Then we have that

\begin{aligned}A_{·,·} & = ⋂_{R∈𝔗}R \\ A_{n,·} & = ⋂_{S∈𝔘}S \end{aligned}  (15)

Proof. To start, note that ⋂_{R∈𝔗} R and ⋂_{S∈𝔘} S are posets. Take (m, m′) ∈ A_{·,·}^{∘}. If m′ |m then (m, m′) ∈ R for every R ∈ 𝔗, since such an R is multiplicative. If on the other hand (m, m′) ∈ A_{·,·}^{∘} but m′ |̸m then we may assume that m = \frac{x_{i}}{x_{j}} m′, with i < j. Any R ∈ 𝔗 may be extended to a multiplicative total order on the difference group of M, and it is clear that for this extension we have that (\frac{x_{i}}{x_{j}} , 1) ∈ R, hence (m′ \frac{x_{i}}{x_{j}} , m′) ∈ R, since R is multiplicative. Since D ⊂ R and A_{n,d} ⊂ R for all n, d, and since R is a strongly multiplicative total order, we have that A_{·,·} ⊂ R. Since R was arbitrary, we have proved that A_{·,·} ⊂ (⋂_{R∈𝔗} R) . Hence, every multiplicative total order on M extends rtr(A_{·,·}).

Suppose now that (m, m′) ∉ A_{·,·}. We must show that (m, m′) ∉ ⋂_{R∈𝔗} R. To do this, we show that there exist some term order R such that (m′, m) ∈ R. If (m′, m) ∈ A_{·,·} then the argument above shows that (m′, m) ∈ R for all R ∈ 𝔗. We address the remaining case, where m, m′ are incomparable. Then from Corollary 5.7 we have that m^{n} and m′^{n} are incomparable for all n ∈ ℕ^{+}, thus from Theorem 2.4 we get that A_{·,·} can be extended to a multiplicative total order R such that (m′, m) ∈ R.

So every term order > satisfying x_{1} > x_{2} > ⋯ refines the strongly stable partial order, and (m, m′) ∈ rtr(A_{·,·}) iff m ≥ m′ for all such admissible orders.

Corollary 5.13. Let R ∈ 𝔗 and let U ⊂ M be a filter wrt R. Then U is a filter wrt A_{·,·} (and is thus a Borel monoid ideal in M).

If n is a positive integer, if S ∈ 𝔘, and if V ⊂ M^{n} is a filter wrt S, then V is a filter wrt A_{n,·} (and is thus a Borel monoid ideal in M^{n}).

We call a term-order ≥ degree-compatible if it refines the partial order given by total degree: in other words, if |m| > |m′| ⟹ m > m′.

Definition 5.14. Let n be a positive integer. Denote by 𝔡𝔗 the set of all degree-compatible term orders R on M such that x_{1} R x_{2} R x_{3} R · · ·. Similarly, denote by 𝔡𝔘 the set of all degree-compatible term orders S on M^{n} such that x_{1} S x_{2} S x_{3} S ⋯ Sx_{n}.

Theorem 5.15. Let n be a positive integer. Then we have that

\begin{aligned}⨁_{d=0}^{∞} A_{·,d} & = ⋂_{R∈𝔡𝔗}R \\ ⨁_{d=0}^{∞} A_{n,d} & = ⋂_{S∈𝔡𝔘}S \end{aligned}  (16)

Here, ⨁ denotes the ordinal sum of posets (see [6, VIII,§10]).

Proof. Similar to Theorem 5.12, noting that there can be no antichain between monomials of different total degree.

The Hasse diagram for ⨁_{d=1}^{∞} A_{2,d} is the ordinal sum of chains, hence a chain. The Hasse diagram for ⨁_{d=1}^{∞} A_{3,d} is more interesting: it looks like figure 3.

6. A closer look at the stable partial order

We now study in more detail the relations B_{n,d}^{∘}, and their reflexive and transitive closures. We note that B_{2,d} is a chain. For n = 3 the relation B_{3,d}^{∘}, and the Hasse diagram for B_{3,d}, looks as Figure 4.

[figure]
Figure 3. Hasse diagram of ⨁_{d=1}^{∞} A_{3,d}.

[figure]
(a) The graph of B_{3,d}^{∘}. Multiplication with \frac{x_{1}}{x_{3}} is
→, multiplication with \frac{x_{2}}{x_{3}} is ↑, multiplication with
\frac{x_{1}}{x_{2}} is ↘.

[figure]

(b) The Hasse diagram of B_{3,d}.

Figure 4. The stable relation and partial order, for n = 3.

Definition 6.1. We define

E_{n−1,d} = { x_{1}^{α_{1}} ⋯ x_{n−1}^{α_{n−1}} ∃α_{n} : x_{1}^{α_{1}} ⋯ x_{n−1}^{α_{n−1}}x_{n}^{α_{n}} ∈ M_{d}^{n} } = ∪_{v=0}^{d}M_{v}^{n−1}.

As in Figure 4, we can draw the graph of B_{n,d} as a graph of the vertex set E_{n−1,d}. From this picture it can be seen that Lemma 6.2. M_{d}^{n} is the disjoint union of M_{d}^{n−1} and x_{n}M_{d−1}^{n}. We have that

(M_{d}^{n−1}, B_{n,d}_{|_{M{n−1 \atop d}}}) ≃ (M_{d}^{n−1}, B_{n−1,d})
(x_{n}M_{d−1}^{n}, B_{n,d}_{|_{xnM{n \atop d−1}}}) ≃ (E_{n−1,d}, D_{|_{E_{n−1,d}}})

If m ∈ M_{d}^{n−1}, m′ ∈ x_{n}M_{d−1}^{n} then (m′, m) ∉ B_{n,d}, and (m, m′) ∈ B_{n,d}^{∘} iff m = (x_{i}/x_{n})m′ for some 1 ≤ i < n.

Proof. We have that

(M_{d}^{n−1}, B_{n,d}_{|_{M{n−1 \atop d}}}) ≃ (M_{d}^{n−1}, B_{n−1,d}).

If (p, p′) ∈ B_{n,d} and p′ is divisible by x_{n}, then the relation between p and p′ must be a substitution x_{n} ↦ x_{i}; if p ≠ p′ then 1 ≤ i ≤ n − 1. This proves the last assertions.

Theorem 6.3. For any positive integers v, d, the poset (M_{d}, B_{·,d}) is a lattice, and the poset (M_{d}^{v}, B_{v,d}) is a sublattice.

Proof. It is clearly enough to show that (M_{d}^{n}, B_{n,d}) is a lattice for all n. We do this by induction on n, the case n = 2 is proved by the observation above that (M_{d}^{2}, B_{2,d}) is a chain. Suppose that (M_{d}^{w}, B_{w,d}) is a lattice for w < n, then clearly B_{i,d} is a sublattice of B_{j,d} for i ≤ j < n. Recall that a finite poset with a unique minimal and a unique maximal element is a lattice iff every pair of elements in M_{d}^{n} has an infimum [13]. So, to show that (M_{d}^{n}, B_{n,d}) is a lattice, we take m, m′ ∈ M_{d}^{n}, and want to define the infimum m ∧ m′ ∈ M_{d}^{n}. The following cases present themselves: (A) m, m′ ∈ M_{d}^{n−1}. Then we use the induction hypothesis to define m ∧ m′ ∈

M_{d}^{n−1} ⊂ M_{d}^{n}. (B) m, m′ ∈ M_{d}^{n} \ M_{d}^{n−1} = x_{n}M_{d−1}^{n}. Then we define the bijective map

f : M_{d}^{n} → E_{n−1,d}
x_{i} ↦ \begin{cases}x_{i} & if 1 ≤ i < n \\ 1 & if i = n \end{cases}

extended multiplicatively to all elements in M_{d}^{n}. We define

m ∧ m′ = f^{−1}(gcd(f(m), f(m′))),

the gcd denotes the ordinary greatest common divisor on M^{n−1}. From Lemma 6.2 it follows that this is indeed the greatest lower bound of m and m′ in

(x_{n}M_{d−1}^{n}, B_{n,d}_{|_{xnM{n \atop d−1}}}) ≃ (E_{n−1,d}, D_{|_{E_{n−1,d}}}).

(C) m ∈ M_{d}^{n−1}, m′ ∈ M_{d}^{n} \ M_{d}^{n−1}. In this case, first note that it is impossible that m′ is larger than m, because there is no transformation in B_{n,d} which introduces a x_{n}. Furthermore, if v = γ(m) < n then the element m′′ = \frac{x_{n}}{x_{v}} m is the largest element in M_{d}^{n} \ M_{d}^{n−1} which is smaller than m. Hence, the infimum of m′′ and m′ is also the infimum of m and m′.

Recall [6] that a lattice is non-modular iff it contains a copy of the nonmodular lattice N_{5}.

[figure] Figure 5. N^{5}

Theorem 6.4. The lattice (M_{d}^{n}, B_{n,d}) is non-modular for n ≥ 3, d ≥ 2.

Proof. (M_{d}^{n}, B_{n,d}) contains (M_{d}^{3}, B_{3,d}) which is non-modular for d ≥ 2, since its Hasse diagram contains a copy of N_{5}, as Figure 4 shows.

7. Filters in the strongly stable poset

7.1. On the number of Borel sets. We shall calculate the number of filters in A_{n,d} with a fixed cardinality v. Our motivation is the article by Marinari and Ramella [16], where the uniqueness of Borel subsets of cardinality v of A_{3,d}, for certain v, is used to determine the possible numerical resolutions of Borel ideals.

We start with the following simple observation:

Theorem 7.1. Let (T, ≥) be a finite poset. For any A ⊂ T and v ∈ ℕ, we denote by Φ(A, v) the number of filters of cardinality v in the sub-poset (A, ≥). For any x ∈ A we put I(x) = { y ∈ A y ≤ x } and F (x) = { y ∈ A y ≥ x }. Then the following recurrence relation holds:

∀x ∈ A : Φ(A, v) = Φ(A \ I(x), v) + Φ(A \ F (x), v − #F (x)).  (17)

Furthermore Φ(A, 0) = Φ(A, #A) = 1.

Denote by ϕ(A) the number of filters in (A, ≥), so that ϕ(A) = ∑_{v=0}^{#A} Φ(A, v). Then

∀x ∈ A : ϕ(A) = ϕ(A \ I(x)) + ϕ(A \ F (x)).  (18)

Proof. It suffices to prove (17). Let P be any filter in (A, ≥) of cardinality v. If x ∉ P then I(x) ∩ P = ∅, hence P is a filter in (A \ I(x), ≥), with cardinality v. There are Φ(A \ I(x), v) such filters.

If on the other hand x ∈ P then F (x) ⊂ P. Clearly P \ F (x) is a filter of cardinality v − #F (x) in A \ F (x), and conversely, if P′ is such a filter, then P′ ∪ F (x) is a filter of cardinality v in A. Thus there is a bijection between filters in A containing x and having cardinality v, and filters in A \ F (x) of cardinality v − #F (x). There are Φ(A \ F (x), v − #F (x)) such filters.

We now apply this to the poset (M_{d}^{n}, A_{n,d}). For n = 2, this is a chain with d + 1 elements, hence

Φ(M_{d}^{2}, v) = \begin{cases}1 & if 0 ≤ v ≤ d + 1 \\ 0 & otherwise. \end{cases}
ϕ(M_{d}^{2}) = d + 2

For n = 3, we get

Corollary 7.2. Denote by F (n, d, v) the number of filters of cardinality v in (M_{d}^{n}, A_{n,d}), and by f(n, d) the number of filters in (M_{d}^{n}, A_{n,d}). Then

F (3, d, v) = F (3, d − 1, v) + F (3, d − 1, v − (d + 1))
F (3, 1, v) = \begin{cases}1 & if 0 ≤ v ≤ 3 \\ 0 & otherwise \end{cases}
f(3, d) = 2f(3, d − 1)
f(3, 1) = 4

In fact, f(3, d) = 2^{d+1}.

Proof. We have that

M_{d}^{3} \ I(x_{2}^{d}) = x_{1}M_{d−1}^{3}
F (x_{2}^{d}) = M_{d}^{2}
#F (x_{2}^{d}) = d + 1
M_{d}^{3} \ F (x_{2}^{d}) = x_{3}M_{d−1}^{3}

We observe that there is a bijection between the filters in M_{d−1}^{n} of cardinality w and the filters in tM_{d−1}^{n} of cardinality w, for any t ∈ M_{1}^{n}; this bijection is given simply by multiplcation by t.

Hence, from Theorem 7.1 we get that

F (3, d, v) = Φ(M_{d}^{3}, v)
= Φ(M_{d}^{3} \ I(x_{2}^{d}), v) + Φ(M_{d}^{3} \ F (x_{2}^{d}), v − #F (x_{2}^{d})
= Φ(x_{1}M_{d−1}^{3}, v) + Φ(x_{3}M_{d−1}^{3}, v − d − 1)
= Φ(M_{d−1}^{3}, v) + Φ(M_{d−1}^{3}, v − d − 1)
= F (3, d − 1, v) + F (3, d − 1, v − d − 1)

This establishes the recurrence relation. Since M_{1}^{3} is a 3-element chain, it has exactly one chain of length v when v ∈ {0, 1, 2, 3}, and no longer chains. Hence, the boundary conditions are as stated in the theorem.

7.1.1. “Splicing the filters”. We can give a recursion formula that is more efficient than (17). To elaborate on this formula, let for the remainder of this subsection n ≥ 3.

Definition 7.3. For F ⊂ M^{n−1}, define the interior of F as

int(F) = { v ∈ F ∀i < j : x_{i} |v ⟹ v(x_{j}/x_{i}) ∈ F } ,

and the boundary of F as

∂F = { m ∈ F ∃t ∈ M^{n−1} \ F : ∃i < j : m = (x_{i}/x_{j})t } .

Theorem 7.4. Let F ⊂ M_{d}^{n}, define F_{d+1} = ∅, and

F_{i} := { m ∈ M_{d−i}^{n−1} x_{n}^{i}m ∈ F } for 0 ≤ i ≤ d,

Then F is a filter in (M_{d}^{n}, A_{n,d}) iff the following two conditions hold, for 0 ≤ i ≤ d:

1. F_{i} is a filter in (M_{d−i}^{n−1}, A_{n−1,d−i}),

2. int(F_{i}) ⊃ x_{1}F_{i+1}.

Proof. Suppose first that F is a filter in M_{d}^{n}. Let 0 ≤ i ≤ d. We prove that F_{i} is a filter in M_{d−i}^{n−1}. Namely, take a ∈ F_{i}, so that x_{n}^{i}a ∈ F, and let b ≥ a (wrt the strongly stable partial order) with b ∈ M_{d−i}^{n−1}. Then x_{n}^{i}b ∈ M_{d}^{n}, hence x_{n}^{i}b ≥ x_{n}^{i}a. Since F is a filter, it follows that x_{n}^{i}b ∈ F, hence that b ∈ F_{i}.

We must also show that int(F_{i}) ⊃ x_{1}F_{i+1}. This condition is trivially fulfilled for i = d, so suppose that 1 ≤ i < d. Take a = x_{1}b ∈ x_{1}F_{i+1}, so that x_{n}^{i+1}b ∈ F. To show that a ∈ int(F_{i}), take r > s such that x_{s} |b. We must prove that \frac{x_{r}}{x_{s}} a ∈ F_{i}, in other words, that

\frac{x_{r}}{x_{s}} ax_{n}^{i} = \frac{x_{r}}{x_{s}} x_{1}x_{n}^{i}b ∈ F.  (19)

Clearly, there is a chain of elementary moves

x_{s}x_{n} → x_{s}x_{r} → x_{1}x_{r}.

Hence x_{1}x_{r} ≥ x_{s}x_{n}, and hence \frac{x_{r}}{x_{s}} x_{1} ≥ x_{n} in the ordered difference group. Therefore, \frac{x_{r}}{x_{s}} x_{1}x_{n}^{i}b ≥ x_{n}^{i+1}b, and since F is a filter, and since we have established that x_{n}^{i+1}b ∈ F, (19) follows. The necessity of the conditions 1 and 2 is established.

To prove sufficiency, suppose that F ⊂ M_{d}^{n}, and that conditions 1 and 2 hold. Suppose furthermore that t ∈ F, and that y ≥ t. Without loss of generality, we can assume that y is obtained from t by a single elementary move, so that t = zx_{j}, y = zx_{i}, i < j. We distinguish between two cases: j < n and j = n.

If j < n we write z = z′x_{n}^{ℓ}, where x_{n} |̸z′. Since x_{j}z ∈ F it follows that x_{j}z′ ∈ F_{ℓ}. Using the fact that F_{ℓ} is a filter (condition 1), we get that x_{i}z′ ∈ F_{ℓ}, hence that y = x_{i}z ∈ F.

There remains the case when j = n. We write t = x_{n}z, y = x_{i}z, i < n. We also write z = z′x_{n}^{ℓ} with x_{n} |̸z′. Then t = x_{n}z = x_{n}^{ℓ+1}z′ ∈ F, hence z′ ∈ F_{ℓ+1}. From the assumptions (condition 2) we get that

x_{1}z′ ∈ x_{1}F_{ℓ+1} ⊂ int(F_{ℓ}),

hence

\frac{x_{r}}{x_{s}} x_{1}z′ ∈ F_{ℓ} for all r > s and x_{s} |x_{1}z′ .

In particular, \frac{x_{i}}{x_{1}} x_{1}z′ = x_{i}z′ ∈ F_{ℓ}, hence

F ∋ x_{n}^{ℓ}x_{i}z′ = x_{n}^{ℓ}z′x_{i} = zx_{i} = y.

Remark 7.5. Another characterisation is given in [5].

We can give a precise interpretation of the numbers F (3, d, v). A very similar reasoning is used in [16].

Proposition 7.6. F (3, d, v) is equal to the number of numerical partitions of v into distinct parts not exceeding d + 1.

Proof. Specialising Theorem 7.4 to the case n = 3 we get that a subset S ⊂ M_{d}^{3} is a filter iff the following two conditions hold:

1. ∀ 0 ≤ i ≤ d : (1/x_{3}^{i})(S ∩ x_{3}^{i}M_{d−i}^{2}) is a filter in M_{d−i}^{2}, and

2. ∀ 0 ≤ i < d : #(S ∩ x_{3}^{i}M_{d−i}^{2}) > #(S ∩ x_{3}^{i+1}M_{d−i−1}^{2}). Clearly, #(S ∩ x_{3}^{i}M_{d−i}^{2}) ≤ d + 1, and

#S = ∑_{i=0}^{d} #(S ∩ x_{3}^{i}M_{d−i}^{2}).

Hence, the filters in M_{d}^{3} of cardinality v are in bijective correspondence with the number of partitions of v into distinct parts not exceeding d + 1.

This correspondence is illustrated in Figure 6.

[figure: (a)]  (b)

Figure 6. A filter in (M_{d}^{3}, rtr A_{3,d}) and the associated numerical partition into distinct parts not exceeding d + 1.

7.2. The poset structure of filters in the strongly stable partial order.

7.2.1. The case n = 3. In fact, if we order the set of numerical partitions into distinct parts not exceeding d + 1 by inclusion of Young diagrams, and the filters in M_{d}^{3} by inclusion, then the above bijection is easily seen to be a poset isomorphism. There is yet another interpretation of this poset:

Theorem 7.7. The following three posets are isomorphic:

(i) The filters in (M_{d}^{3}, A_{3,d}), ordered by inclusion, (ii) The numerical partitions into distinct parts not exceeding d + 1, ordered

by inclusion of Young diagrams, (iii) The poset (E^{d+1}, A_{d+1,·}_{|_{E^{d+1}}})), where E ⊂ M denotes the set of all square-

free monomials. Furthermore, the following finite sets have the same cardinality:

• Filters in (M_{d}^{3}, A_{3,d}) of cardinality v,

• Numerical partitions of v into distinct parts not exceeding d + 1,

• Square-free monomials on {x_{1}, …, x_{d+1}} with weight v, when x_{i} is given weight d + 2 − i.

Proof. Letting the variable x_{i} correspond to the singleton set {d + 2 − i}, and a product of distinct variables to the corresponding union, we regard a square-free monomial m ∈ E^{d+1} as a subset of {1, 2, …, d + 1}. Summing the elements of this subset, we get a numerical partition into distinct parts not exceeding d+1. This establishes a bijection, which we must show is isotone with isotone inverse. If m′ = x_{j}m then the Young diagram of m′ has an extra row compared to that of m, and contains the latter; if m′ = \frac{x_{i}}{x_{i+1}} m then one row of the Young diagram of m′ is one unit longer than the corresponding row of the Young diagram of m. The converse holds also, so the correspondence is an isomorphism.

The Hasse diagram for the poset of square-free monomials in 4 variables is given in Figure 7.

It is clear that we can extend Theorem 4.4 as follows (with the same definition of strongly stable ideal)

Lemma 7.8. For any positive integer n, the strongly stable monoid ideals in E^{n} are precisely the filters in (E^{n}, A_{n,·}_{|_{E^{n}}}).

It is proved in [2] that Theorem 4.2 has a counterpart in the exterior algebra; that is, generic initial ideals in the exterior algebra ∧^{n} are strongly stable, hence their intersections with E^{n} are filters in (E^{n}, A_{n,·}_{|_{E^{n}}}). We can state this as follows:

Theorem 7.9. The sets of monomials of a generic initial ideals in the exterior algebra on n variables (with coefficients in ℂ) is a filter in the poset of filters of the poset A_{3,n−1}.

7.2.2. The case n > 3. It is straightforward to use Theorem 7.4 to give a description of the set of filters in (M_{d}^{n}, A_{n,d}) in terms of certain hyper-partitions (see [15]). In particular, for n = 4 we get

Proposition 7.10. The following two posets are isomorphic:

[figure: 1; x_{4}; x_{3}; x_{3}x_{4}; x_{2}; x_{1}; x_{2}x_{4}; x_{1}x_{4}; x_{2}x_{3}; x_{1}x_{3}; x_{2}x_{3}x_{4}; x_{1}x_{3}x_{4}; x_{1}x_{2}; x_{1}x_{2}x_{4}; x_{1}x_{2}x_{3}; x_{1}x_{2}x_{3}x_{4}]
Figure 7. The poset (E^{4}, A_{4,·}_{|_{E^{4}}}).

1. The poset of filters in (M_{d}^{4}, A_{4,d}), ordered by inclusion,

2. The poset of planar partitions which are contained in a (d + 1) × (d + 1) × (d + 1) box, and which have horizontal and vertical “steps” of length ≤ 1.

An explanation of the nomenclature is in order: we draw the solid Young diagram as a union of unit cubes [i, i + 1] × [j, j + 1] × [k, k + 1], with i, j, k nonnegative integers satisfying 0 ≤ k < π_{i,j}; the π_{i,j}’s are non-negative integers, almost all zero, such that for all x, y we have that π_{x+1,y} ≤ π_{x,y} and π_{x,y+1} ≤ π_{x,y}. Then we demand in addition that each “level” of cubes should represent a partition into distinct parts, and that each “level” should be contained in the interior of the one upon which it rests. It is easy to see that this implies that there can be no vertical steps of height 2 or greater. Similarly, each “level”, when drawn in this fashion has steps of height 1.

8. Filters in the stable poset

8.1. On the number of stable subsets of M_{d}^{3}. Let us briefly consider the question of how many filters there are (of a given cardinality) in (M_{d}^{n}, B_{n,d}). For n = 1, 2 the partial order is a chain, hence the enumeration of filters is trivial. For n = 3, the Hasse diagram looks like Figure 4. We apply Theorem 7.1, by partitioning the filters into two classes: those that contain x_{2}^{d}, and those that do not. We have that

F (x_{2}^{d}) = M_{d}^{2}
M_{d}^{3} \ F (x_{2}^{d}) = x_{3}M_{d−1}^{3}
M_{d}^{3} \ I(x_{2}^{d}) = x_{1}M_{d−1}^{3}

It is easy to see that

(x_{1}M_{d−1}^{3}, B_{3,d}_{|_{x_{1}M{3 \atop d−1}}}) ≃ (M_{d−1}^{3}, B_{3,d−1}).

Furthermore, in x_{3}M_{d−1}^{3} every monomial is divisible by x_{3}, hence the allowed substitutions are m ↦ x_{1}/x_{3} and m ↦ x_{2}/x_{3}. Hence (recall Definition 6.1)

(x_{3}M_{d−1}^{3}, B_{3,d}_{|_{x_{3}M{3 \atop d−1}}}) ≃ (E_{2,d−1}, D_{|_{E_{2,d−1}}})

The poset (E_{2,d}, D_{|_{E_{2,d}}}) is a sub-poset of ℕ^{2} with the natural divisibility order.

So, if we denote by G(d) the number of filters in (M_{d}^{3}, B_{3,d}), by GG(d, v) the number of such filters of cardinality v, by C(d) the number of filters in (E_{2,d}, D_{|_{E_{2,d}}}), and by CC(d, v) the number of such filters of cardinality v, we have that

G(d) = G(d − 1) + C(d − 1)  (20)
GG(d, v) = GG(d − 1, v − d − 1) + CC(d − 1, v)  (21)

We can give an illuminating interpretation of the numbers C(d) by observing that filters in (E_{2,d}, D_{|_{E_{2,d}}}) are in bijective correspondence with lattice walks in E_{2,d+2} from (0, d + 2) to (d + 2, 0), consisting of moves of unit length down and to the right. Namely, to such a walk we associate the filter in (E_{d}, D_{|_{E_{2,d}}}) which is generated by all lattice points in E_{2,d} which are visited during the walk. Thus, the empty filter corresponds to the walk

(0, d + 2) ↓ (0, d + 1) → (1, d + 1) ↓→ ⋯ ↓ (d + 1, 0) → (d + 2, 0)

whereas the filter E_{2,d} corresponds to the walk

(0, d + 2) ↓ (0, d + 1) ↓ ⋯ ↓ (0, 0) → (1, 0) → ⋯ → (d + 1, 0) → (d + 2, 0)

The correspondence for a general filter is illustrated in Figure 8. It is wellknown that the number of lattice walks in E_{2,N+1} is the N’th Catalan number C_{N} = (2N)!/(N!(N + 1)!). It follows that C(d) = C_{d−1}. Hence we can solve (20) and get

Proposition 8.1. The number of filters in (M_{d}^{3}, B_{3,d}) is ∑_{i=0}^{d+1} C_{i}, where C_{i} is the i’th Catalan number.

The following lemma shows that we can find an explicit, although complicated, recurrence relation for CC(d, v), and hence for GG(d, v).

[figure: (a); 0; 1; 2; 3; 1; 0; 0; 1; (b)]

Figure 8. A lattice walk in E_{2,8} and its associated filter in E_{2,6}.

Lemma 8.2. We label the horizontal edges connecting vertices in E_{2,d+2} with 0, and the vertical edges (a, b) → (a, b − 1) with d + 2 − a − b. For a path using only such edges, we define its weight to be the sum of the labels of the edges. Let S_{d}(a, b, w) be the number of such paths in E_{2,d+2} from (a, b) to (d + 2, 0) of weight w. Then CC(d, v) = S_{d}(0, d + 2, w), and S_{d}(a, b, w) is the unique solution to the following system of equations:

S_{d}(a, b, w) = \begin{cases}0 & (a, b) ∉ E_{2,d+2} \\ \begin{cases}1 & w = d − a + 1 \\ 0 & otherwise \end{cases} & b = 0 \\ \begin{cases}1 & w ≤ d + 1 − a \\ 0 & otherwise \end{cases} & b = 1 \\ ∑_{j=a}^{d+2−b} S_{d}(j, b − 1, w + j + b − d − 2) & otherwise \end{cases} (22)

Proof. It is easy to see that the weight of the path counts the cardinality of the associated filter in E_{2,d}. From (a, b), one can choose to descend from

(a, b), (a + 1, b), …, (d + 2 − b, b);

the corresponding vertical step (j, b) → (j, b−1) has weight d+2−b−j. Hence, S_{d}(a, b, w) = ∑_{j=a}^{d+2−b} S_{d}(j, b − 1, d + 2 − b − j). The boundary conditions are easily verified.

We illustrate the weighting of the edges in Figure 8.

In general, (22) seems hard to solve explicitly, but for the special case d > v we can indeed find the value of CC(d, v). Recall [17, Example 10.12] that an (n, k) fountain is an arrangement of n coins such that there are k coins in the bottom row, and such that each coin in a higher row rests on exactly two coins in the next lower row; a fountain of w coins is any (w, k).

Proposition 8.3. If d > w then the stable subsets of M_{d}^{3} of cardinality w are in bijective correspondence with the fountains of w coins.

Proof. Since the principal filter on x_{2}^{d} contains d+1 elements, it is clear that for w < d a filter F ⊂ M_{d}^{3}, #F = w wrt the stable partial order never contains an element ≤ x_{2}^{d}. Hence, such a filter can be identified with a filter in the inductive limit G = \underrightarrow{lim}_{v}(M_{v}^{3}, A_{3,v}), where the injections are given by

i : M_{v}^{3} → M_{v+1}^{3}
m ↦ x_{1}m

The infinite Hasse diagram of G looks like Figure 4(b), only extended infinitely downwards and to the right. A finite filter in G gives a fountain of coins by reading the successive diagonal rows from right to left, and conversely.

It is known [17](see Example 10.12) that if a_{w} denotes the number of wfountains, then a generating function is given by

f(z) = ∑_{n=0}^{∞} a_{n}z^{n} = \frac{1}{1 − \frac{z}{1 − \frac{z^{2}}{1 − \frac{z^{3}}{1 ⋯}}}}

References

[1] Martin Aigner. Combinatorial Theory, volume 234 of Grundlehren der mathematischen Wissenschaften. Springer, 1979.

[2] Anetta Aramova, Jürgen Herzog, and Takayuki Hibi. Gotzman theorems for exterior algebras and combinatorics. Journal of Algebra, 191:174–211, 1997.

[3] David Bayer and Michael Stillman. A theorem on refining division orders by the reverse lexicographic order. Duke Math. Journal, 55:321–328, 1987.

[4] A. M. Bigatti. Aspetti Combinatorici e Computazionali dell’Algebra Commutativa. PhD thesis, Università di Torino, 1995.

[5] A. M. Bigatti and L. Robbiano. Borel sets and sectional matrices. Annals of Combinatorics, 1(3):197–213, 1997.

[6] G Birkhoff. Lattice theory, volume XXV of Colloquium Publications. American Mathematical Society, 1967.

[7] David Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics. Springer Verlag, 1995.

[8] S. Eliahou and M. Kervaire. Minimal resolutions of some monomial ideals. J. Algebra, 129:1–25, 1990.

[9] A. Galligo. A propos du théorème de prèparation de Weirstrass. Lecture notes in Mathematics, 409:543–579, 1974.

[10] A. Galligo. Théoreme de division et stabilité en géométrie analytique local. Ann. Inst. Fourier, 29:107–184, 1979.

[11] Vesselin Gasharov. Green and Gotzmann theorems for polynomial rings with restricted powers of variables. Journal of Pure and Applied Algebra, 130:113–118, 1998.

[12] Robert Gilmer. Commutative Semigroup Rings. Chicago Lectures in Mathematics. The University of Chicago Press, 1984.

[13] George Grätzer. General lattice theory, volume 52 of Lehrbücher und Monographien aus dem Gebiete der exakten Wissenschaften: Mathematische Reihe. Birkhäuser Verlag Basel und Stuttgart, 1978.

[14] Mark L. Green. Generic initial ideals. In Proceedings of the Summer School on Commutative Algebra, volume 2, pages 16–85, CRM, Barcelona, 1996.

[15] Percy A. MacMahon. Combinatory Analysis. Cambridge University Press, 1915.

[16] Maria Grazia Marinari and Luciana Ramella. Some properties of Borel ideals. J. Pure Appl. Algebra, 139(1-3):183–200, 1999. Effective methods in algebraic geometry (Saint-Malo, 1998).

[17] A. M. Odlyzko. Asymptotic enumeration methods. In R. L. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, volume II, chapter 22, pages 1063–1229. North-Holland, 1995.

[18] Lorenzo Robbiano. Term orderings on the polynomial ring. Springer Lecture notes in Computer Science, 204:513–517, 1985.

[19] William M. Trotter. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins series in the mathematical sciences. The Johns Hopkins University Press, 1992.

Laboratorie GAGE, Ecole Polytechnique, 91128 Palaiseau Cedex, France

E-mail address: jans@matematik.su.se