HILBERT FUNCTIONS OF LADDER DETERMINANTAL VARIETIES

SUDHIR R. GHORPADE

Abstract. We consider algebraic varieties defined by the vanishing of all minors of a fixed size of a rectangular matrix with indeterminate entries such that the indeterminates in these minors are restricted to lie in a ladder shaped region of the rectangular array. Explicit formulae for the Hilbert function of such varieties are known in (i) the rectangular case [Abhyankar, 1984], and (ii) the case of 2 × 2 minors in one-sided ladders [Kulkarni, 1985]. More recently, Krattenthaler and Prohaska (1999) have proved a ‘remarkable formula’, conjectured by Conca and Herzog (1994) for the Hilbert series in the case of arbitrary sized minors in one-sided ladders. We describe here an explicit, albeit complicated, formula for the Hilbert function and the Hilbert series in the case of arbitrary sized minors in two-sided ladders. From a combinatorial viewpoint, this is equivalent to the enumeration of certain sets of ‘indexed monomials’.

Introduction

Let K be a field and X = (X_{ij}) be an m(1) × m(2) matrix whose entries are variables over K. Given a subset Y of the integral rectangle

[1, m(1)] × [1, m(2)] = {(i, j) ∈ ℤ^{2} : 1 ≤ i ≤ m(1) and 1 ≤ j ≤ m(2)},

let K[Y] denote the ring of all polynomials in {X_{ij} : (i, j) ∈ Y } with coefficients in K. Also, let I_{p}(Y) denote the ideal of K[Y] generated by all p × p minors of X with entries in Y and V_{p}(Y) denote the projective variety corresponding to I_{p}(Y). We call Y a generalized ladder or a saturated set if

(i_{1}, i_{2}), (j_{1}, j_{2}) ∈ Y with i_{1} < j_{1}, i_{2} < j_{2} ⟹ (i_{1}, j_{2}) ∈ Y and (i_{2}, j_{1}) ∈ Y.

In effect, a generalized ladder looks like a ladder (see Fig. 1) or a biladder with or without overlap (see Fig. 2 (a) and Fig. 2(b)). In the literature, generalized ladders, ladders and biladders are sometimes referred to as ladders, one-sided ladders and two-sided ladders, respectively.

If L is a generalized ladder, then I_{p}(L) is called a ladder determinantal ideal and V_{p}(L) a ladder determinantal variety. These varieties were introduced by Abhyankar [2] in connection with his study of singularities of Schubert varieties in flag manifolds. Viewed as affine varieties (i.e., as cones over V_{p}(L)), these are essentially the “opposite big cells” of Schubert varieties in flag manifolds (see [27] or [28] for details). Using the connection with Schubert varieties or otherwise, it is now known that ladder determinantal varieties have a number of nice properties such as irreducibility, Cohen-Macaulayness, normality, etc.; we refer to [2], [6], [7], [8], [16], [17], [25], [26] and [29] as well as [4], [14], [15], [19], [23], [24], [30], [31] and [32] for details.

In this paper, we consider the problem of finding an explicit formula for the Hilbert function of V_{p}(L) or equivalently, of K[L]/I_{p}(L), where p is any positive integer and L is any biladder. A formula in the first nontrivial case of p = 2 and L a (one-sided) ladder was obtained by Kulkarni in his 1985 thesis [21] (see also [22]). Subsequently, in 1989 it was shown by Abhyankar and Kulkarni [3] that the ideals I_{p}(L) are hilbertian (which means that the Hilbert function of K[L]/I_{p}(L) coincides with its Hilbert polynomial at all nonnegative integers), for any p > 1 and any generalized ladder L. Hilbertianness of I_{p}(L) also follows from the later work of Herzog and Trung [17], who showed that the Hilbert function of K[L]/I_{p}(L) can be described in terms of the f-vector of an associated simplicial complex. Nevertheless, there still remains the problem of finding explicitly the Hilbert function of K[L]/I_{p}(L). To this end, Conca and Herzog [5] conjectured a ‘remarkable formula’ for the Hilbert series in the case of (one-sided) ladders and any p > 1. Recently, Krattenthaler and Prohaska [20] have established this Conjecture using the so called ‘two-rowed arrays’. It may be noted that in the degenerate case when L is is the entire rectangle [1, m(1)] × [1, m(2)], the ideal I_{p}(L) reduces to the classical determinantal ideal I_{p}(X) and its Hilbert function is explicitly known from the work of Abhyankar [2] (see also [10]). Short proofs of Abhyankar’s formula as well as formulae for the Hilbert series of I_{p}(X) are described in [5] and [12].

Date: September 15, 2000.

1991 Mathematics Subject Classification. Primary 05A15, 13C40, 13D40, 14M12; Secondary 05A19, 05E10, 14M15.

A part of this work was supported by research grant No. 93-106/RG/MATHS/AS from the Third World Academy of Sciences, Italy. Currently, the author is partially supported by a ‘Career Award’ grant from AICTE, New Delhi and an IRCC grant from IIT Bombay.

In this paper we aim at giving an explicit formula for the Hilbert function of K[L]/I_{p}(L) for any biladder L and any p > 1. This result was announced in [10] and an outline of the proof was described in [13]. In this paper we also show that even though this “explicit” formula is complicated, it can be used to derive fairly simple estimates for some useful geometric invariants such as the degree of the Hilbert polynomial.

Our starting point, as in Kulkarni [21], is a theorem of Abhyankar [2], which describes bases for the graded components of K[L]/I_{p+1}(L) in terms of monomials of “index” ≤ p. [With this in view, we shall find it convenient to consider I_{p+1}(L) rather than I_{p}(L) and henceforth we shall do so.] In [21] (see also [22]), Kulkarni enumerated the monomials of index ≤ 1 in a (one-sided) ladder L by counting certain related objects, called radicals and skeletons. Roughly speaking, a radical is like a subset of a lattice path in L whereas a skeleton is like a set of nodes (or South-West corners) in a radical. The main idea behind our formula in the general case is simply as follows. First, generalize Kulkarni’s computation of radicals and skeletons from ladders to biladders, and then use induction! The technical details, however, seem rather long and tedious. This is partly due to the fact that for a smooth passage in the inductive step, it is necessary to consider biladders with possible horizontal and/or vertical overlap (see Fig. 2(b)). With such configurations in the fray, it was felt prudent that we give complete (and seemingly pedantic) proofs of the auxiliary results needed for the main result even though in some cases it appears tempting to dismiss them as (pictorially) obvious. An overview of the main steps in the proof is given in [13] and it may be advisable to read that before proceeding with the details given here.

This paper is organized as follows. In the next section we describe most of the notation and terminology used in the paper, and also some preliminary results. The relation between radicals and skeletons is established in Section 2. In Section 3, we give a formula to enumerate the skeletons in a biladder. Next, in Section 4, we take up the enumeration of p-fold radicals as well as of monomials of index ≤ p in a biladder L. This enables us to determine the Hilbert function of V_{p+1}(L). Finally, in Section 5, we describe some applications to the computation of the Hilbert series as well as the dimension of ladder determinantal varieties.

I would like to thank Devadatta Kulkarni for some helpful discussions several years ago concerning the results in his thesis. I am also grateful to him as well as to Swatee Naik for prodding and encouraging me from time to time for about a decade (!) to write up this paper.

1. Preliminaries

The notation and terminology introduced in this section will be used throughout this paper.

Intervals and Matrices: By ℚ, ℤ, ℕ, and ℕ^{+} we denote the sets of all rational numbers, integers, nonnegative integers, and positive integers respectively. Given any α, β ∈ ℤ, we let

[α, β] = {γ ∈ ℤ : α ≤ γ ≤ β};

and we also let

[α, β) = {γ ∈ ℤ : α ≤ γ < β} and (α, β] = {γ ∈ ℤ : α < γ ≤ β}.

The corresponding notation for open integral intervals will never be used so as to avoid confusion with the elements (e.g., (a, b)) of the direct product of two sets (e.g., A × B). The cardinality of a set A will be denoted by |A|. Let h and h′ be any positive integers. For any nonnegative integer l, we let

M_{h h′}(ℕ, l) = the set of all h × h′ matrices α = (α_{kk′}) such that

α_{kk′} ∈ ℕ for 1 ≤ k ≤ h and 1 ≤ k′ ≤ h′ and ∑_{k=1}^{h} ∑_{k′=1}^{h′} α_{kk′} = l.

Note that M_{h h′}(ℕ, l) is a finite set. We can define the set M_{h h′}(ℕ) of all ℕ–valued h × h′ matrices by putting

M_{h h′}(ℕ) = ∐_{l∈ℕ} M_{h h′}(ℕ, l)

where ∐ denotes disjoint union. Given any ℕ–valued h × h′ matrix α = (α_{kk′}) and any p ∈ [1, h] and q ∈ [1, h′], we define

σ_{p}(α) = ∑_{k=1}^{p} ∑_{k′=1}^{h′} α_{kk′} and τ_{q}(α) = ∑_{k=1}^{h} ∑_{k′=q}^{h′} α_{kk′}.

Note that for any α ∈ M_{h h′}(ℕ) and l ∈ ℕ we have

α ∈ M_{h h′}(ℕ, l) ⟺ σ_{h}(α) = τ_{1}(α) = l.

Given any α, β in M_{h h′}(ℕ) we define

σ(β) ≤ σ(α) to mean that σ_{p}(β) ≤ σ_{p}(α) for all p ∈ [1, h]

and

τ(β) ≤ τ(α) to mean that τ_{q}(β) ≤ τ_{q}(α) for all q ∈ [1, h′].

Index and Monomials: A field K, a pair m = (m(1), m(2)) ∈ ℕ^{+} × ℕ^{+} of positive integers, and a set X = {X_{ij} : 1 ≤ i ≤ m(1), 1 ≤ j ≤ m(2)} of m(1)m(2) independent indeterminates over K will be kept fixed throughout this paper.

Let Y be a subset of the rectangle [1, m(1)] × [1, m(2)]. As in the Introduction, let K[Y] denote the ring of polynomials in the variables {X_{ij} : (i, j) ∈ Y } with coefficients in K, and for any V ∈ ℕ, let K[Y]_{V} denote its V^{th} graded component, i.e., the set of all homogeneous polynomials in K[Y] of degree V including the zero polynomial. Given any p ∈ ℕ^{+}, we let I_{p}(Y) denote the ideal of K[Y] generated by all p × p minors of Y, and let V_{p}(Y) denote the corresponding projective variety.

By a monomial on Y we mean a map θ : Y → ℕ, and we let

mon(Y) = the set of all monomials on Y.

Note that we have a natural injective map θ ↦ X^{θ} of mon(Y) → K[Y], where

X^{θ} = ∏_{(i,j)∈Y} X_{ij}^{θ(i,j)}, for any θ ∈ mon(Y).

The support of a monomial θ ∈ mon(Y) will be denoted by supp(θ); thus,

supp(θ) = {(i, j) ∈ Y : θ((i, j)) ≠ 0}.

To any subset T of [1, m(1)]×[1, m(2)] we associate the index of T which we denote by ind(T) and which we define by

ind(T) = max{p ∈ ℕ : ∃ (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{p}, j_{p}) in T with
i_{1} < i_{2} < ⋯ < i_{p} and j_{1} < j_{2} < ⋯ < j_{p}}.

Notice that ind(T) = 0 ⟺ T is empty. The index of a monomial θ ∈ mon(Y) is defined by putting

ind(θ) = ind(supp(θ)).

For every p ∈ ℕ we let

mon(Y, p) = {θ ∈ mon(Y) : ind(θ) ≤ p}

and, restricting attention to monomials of a specified degree, for every p ∈ ℕ and V ∈ ℕ we let

mon(Y, p, V) = {θ ∈ mon(Y, p) : ∑_{y∈Y} θ(y) = V }.

Radicals and Skeletons: Let p ∈ ℕ and Y be a subset of [1, m(1)] × [1, m(2)]. Define

rad^{p}(Y) = {R : R ⊆ Y and ind(Y) ≤ p} and rad(Y) = rad^{1}(Y).

Elements of rad^{p}(Y) may be called the p–fold radicals in Y whereas elements of rad(Y) are simply called the radicals in Y. The cardinality of a radical R in Y may be called the size of R. Given any d ∈ ℕ, we define

rad(Y, d) = {R ∈ rad(Y) : |R| = d}.

A subset E of Y is said to be a skeleton in Y if the elements of E can be arranged on an antidiagonal, i.e., for any two distinct elements (x_{1}, y_{1}) and (x_{2}, y_{2}) of E, we have

either: x_{1} < x_{2} and y_{1} > y_{2} or: x_{1} > x_{2} and y_{1} < y_{2}.

Let skel(Y) denote the set of all skeletons in Y. Note that skel(Y) ⊆ rad(Y). The cardinality of a skeleton E in Y may be called the length of E. Given any l ∈ ℕ, we define

skel(Y, l) = {E ∈ skel(Y) : |E| = l}.

Ladders and Biladders: Recall that we have fixed a pair m = (m(1), m(2)) of positive integers. Given any h ∈ ℕ^{+}, by a ladder generating bisequence of length h, we mean a map S : [1, 2] × [0, h] → ℕ such that

1 = S(1, 0) ≤ S(1, 1) < S(1, 2) < ⋯ < S(1, h) = m(1)

and

m(2) = S(2, 0) > S(2, 1) > ⋯ > S(2, h − 1) ≥ S(2, h) = 1.

The positive integer h, called the length of S, is denoted by len(S). We shall find it convenient to also consider the empty bisequence, which we declare to be the unique ladder generating bisequence of length 0. Define

lad[m, h] = the set of all ladder generating bisequences of length h

and

lad(m) = ⋃_{h∈ℕ} lad[m, h].

Let S ∈ lad(m). We define the ladder L(S) corresponding to S by

L(S) = ⋃_{k=1}^{len(S)}[S(1, k − 1), S(1, k)] × [1, S(2, k − 1)],

and we define its interior L(S)^{o} by

L(S)^{o} = ⋃_{k=1}^{len(S)}[S(1, k − 1), S(1, k)) × [1, S(2, k − 1)).

Note that if len(S) = 0, then L(S) = L(S)^{0} = ∅ and if len(S) ≠ 0 then

L(S)^{o} ⊂ L(S) ⊆ [1, m(1)] × [1, m(2)]

where the first inclusion is proper. Also note that if len(S) = 1, then L(S) is the full rectangle [1, m(1)]×[1, m(2)]. The boundary of S or of the ladder L(S), denoted by ∂S or by ∂L(S), is defined by

∂S = L(S) \ L(S)^{o}.

Points (S(1, k), S(2, k)) for 1 ≤ k ≤ h − 1 are called the nodes of S, and we let

N (S) = {(S(1, k), S(2, k)) : 1 ≤ k ≤ h − 1}

denote the set of all nodes of S. It may be noted that N (S) ⊆ ∂S.

Pictorially, a ladder looks as in Fig. 1 below. In this picture, we adopt the “matrix notation” rather than that of Co-ordinate Geometry to represent the points. Thus the bullet in top left hand corner indicates the point (1, 1) while the other bullets indicate the nodes of this ladder.

• •  • •  • •  •

Figure 1

For any S′, S ∈ lad(m), we define

S′ ≤ S iff L(S′) ⊆ L(S)

and we note that this defines a partial order on lad(m). Given any S′, S ∈ lad(m) such that S′ ≤ S and len(S) ≠ 0, we define the biladder L(S′, S) corresponding to (S′, S) by

L(S′, S) = L(S) \ L(S′)

and its interior L(S′, S)^{o} by

L(S′, S)^{o} = L(S)^{o} \ L(S′).

The common intersection of the boundaries of S and S′ will be denoted by Δ(S′, S). Note that if S′ ≤ S, then

Δ(S′, S) = ∂S ∩ ∂S′ = ∂S ∩ L(S′).

Typically, a biladder looks as in Fig. 2 (a) below. But there can also be some boundary overlaps and in this case, a biladder looks as in Fig. 2 (b) below. In these pictures, we continue to adopt the “matrix notation” as in Fig. 1.

•  •  •  •

Figure 2 (a) Figure 2 (b)

We shall now record several elementary observations concerning ladders and biladders. The reader is invited to supply formal and/or pictorial proofs so as to get a better feel of some of the definitions above. We will tacitly use the following observations in the succeeding sections. OBSERVATIONS: Let h ∈ ℕ and S ∈ lad[m, h]. Let i, j, p, q denote positive integers. Then we have the following. (1.1) The ladder L(S) and its interior L(S)^{o} can be alternatively described as

L(S) = ⋃_{k=1}^{h}[1, S(1, k)] × [1, S(2, k − 1)]

and

L(S)^{o} = ⋃_{k=1}^{h}[1, S(1, k)) × [1, S(2, k − 1)).

(1.2) If h = len(S) ≠ 0, then ∂S = L(S) \ L(S)^{o} = L_{0} ∐ L_{1} ∐ L_{2}, where

L_{0} = {(S(1, 0), S(2, 0))}, L_{1} = ∐_{k=1}^{h}(S(1, k − 1), S(1, k)] × {S(2, k − 1)},

and

L_{2} = ∐_{k=1}^{h}{S(1, k)} × [S(2, k), S(2, k − 1)).

In particular, |∂S| = m(1) + m(2) − 1. (1.3) (p, q) ∈ L(S), 1 ≤ i ≤ p, 1 ≤ j ≤ q ⇒ (i, j) ∈ L(S). (1.4) (p, q) ∈ L(S)^{o}, 1 ≤ i ≤ p, 1 ≤ j ≤ q ⇒ (i, j) ∈ L(S)^{o}. (1.5) (p, q) ∈ L(S), 1 ≤ i < p, 1 ≤ j < q ⇒ (i, j) ∈ L(S)^{o}. (1.6) (p, q) ∈ ∂S, i > p, j > q ⇒ (i, j) ∉ L(S). (1.7) ∂S ∈ rad(L(S)). (1.8) (p, q) ∈ L(S)^{o} ⇒ (p + 1, q + 1) ∈ L(S). (1.9) (p, q) ∈ L(S)^{o} ⇒ 1 ≤ p < m(1) and 1 ≤ q < m(2). (1.10) If (p, q) = (S(1, k), S(2, k)) for some k ∈ [1, h], 1 ≤ i ≤ p, 1 ≤ j ≤ q and

(i, j) ≠ (p, q), then (i, j) ∈ L(S)^{o}.

Proof. The identities in (1.1) follow from the fact that the S(1, k) ’s increase with k whereas the S(2, k) ’s decrease with k. Next, (1.2) follows just from the definitions of L(S) and L(S)^{o}. The assertions (1.3), (1.4), (1.5), (1.8) and (1.9) are easy consequences of (1.1). From (1.5) we get (1.6). And (1.7) follows from (1.5) and (1.6). Finally, (1.10) follows from (1.1) by noting that if 1 ≤ i < p, then k ≠ 0 and (i, j) ∈ [1, S(1, k)) × [1, S(2, k − 1)), whereas if 1 ≤ j < q, then k ≠ h and (i, j) ∈ [1, S(1, k + 1)) × [1, S(2, k)).

Binomials and Monomials: Following Abhyankar [3], we define a variant of the ordinary binomial coefficient, called the twisted binomial coefficient, as follows.

\left[{V \atop A}\right] = \binom{V + A}{A} = \frac{(V + 1)(V + 2) ⋯ (V + A)}{A!}.

Here A ∈ ℤ and V can be an integer or an indeterminate over ℚ. For A < 0, we follow the usual convention that 1/A! = 0 so that

\left[{V \atop A}\right] = \binom{V + A}{A} = 0 if A < 0.

We now record some elementary properties of binomial coefficients in the lemma below. Proofs are fairly straightforward, and hence omitted. If necessary, the reader is referred to [2] or [11] for details. Lemma (1.11). Given any integers d, e, f, and V, we have the following.

(i) \binom{d}{V − 1} + \binom{d}{V} = \binom{d + 1}{V}; and \left[{d \atop V − 1}\right] + \left[{d − 1 \atop V}\right] = \left[{d \atop V}\right].

(ii) ∑_{j=0}^{V} \left[{d − 1 \atop j}\right] = \left[{d \atop V}\right].

(iii) \binom{d}{e}\binom{e}{f} = \binom{d}{f}\binom{d − f}{f − e}; and \left[{d \atop e}\right]\left[{e \atop f}\right] = \left[{d \atop f}\right]\left[{d − f \atop f − e}\right].

(iv) ∑_{i∈ℤ} \binom{d}{f + i}\binom{e}{V − i} = \binom{d + e}{f + V}; and ∑_{i∈ℤ} \left[{d \atop f + i}\right]\left[{e \atop V − i}\right] = \left[{d + e + 1 \atop f + V}\right].

More generally, given any a_{1}, …, a_{p} in an overfield of ℚ and any integers f_{1}, …, f_{p}, we have

∑ ∏_{i=1}^{p} \binom{a_{i}}{f_{i} + d_{i}} = \binom{a}{f + d} and ∑ ∏_{i=1}^{p} \left[{a_{i} \atop f_{i} + d_{i}}\right] = \left[{a + p − 1 \atop f + d}\right]

where a = a_{1} + ⋯ + a_{p}, f = f_{1} + ⋯ + f_{p}, and each of the sum above is taken over all p-tuples (d_{1}, …, d_{p}) of integers such that d_{1} + ⋯ + d_{p} = d.

(v) \binom{d}{e} = 0 iff e < 0 or e > d ≥ 0; and \left[{d \atop e}\right] = 0 iff e < 0 or e > (d + e) ≥ 0.

(vi) \binom{d}{e} = \binom{d}{d − e} iff d ≥ 0 or d < e < 0; and \left[{d \atop e}\right] = \left[{e \atop d}\right] iff (d+e) ≥ 0 or d < 0

and e < 0.

(vii) \binom{d}{e} = (−1)^{e}\left[{−d − 1 \atop e}\right] and \left[{d \atop e}\right] = (−1)^{e}\binom{−d − 1}{e}.

It may be remarked that the summations in (iv) above are essentially finite, by which we mean that all except finitely many summands are zero. Lemma (1.12). Let Y be a finite set and R be a subset of Y. Let e = |Y | and d = |R|. Given any V ∈ ℕ, let

M_{V} (Y) = {θ ∈ mon(Y) : ∑_{y∈Y} θ(y) = V }

and

M_{V} [Y, R] = {θ ∈ M_{V} (Y) : supp(θ) = R}.

Then

|M_{V} (Y)| = \left[{e − 1 \atop V}\right] and |M_{V} [Y, R]| = \left[{d − 1 \atop V − d}\right].

Proof. The first asserted equality is a well-known formula for the number of monomials of a fixed degree. The second assertion follows from the first by noting that the map θ ↦ θ̃, where θ̃(y) = θ(y) − 1 for y ∈ R, defines a bijection of M_{V} [Y, R] onto M_{V −d}(R).

Lemma (1.13). Let M be a finite set and E be a subset of M. Let m = |M| and e = |E|. Then for any d ∈ ℕ, we have

|\{R : E ⊆ R ⊆ M and |R| = d\}| = \binom{m − e}{d − e}.

Proof. The map R ↦ R \ E clearly sets up a bijection of the set whose cardinality is desired onto the set of all subsets of M \ E of cardinality d − e.

Generalized Ladders and Abhyankar’s Theorem: As in the Introduction, we call a subset Y of [1, m(1)] × [1, m(2)] a generalized ladder or a saturated set if

(i_{1}, i_{2}), (j_{1}, j_{2}) ∈ Y with i_{1} < j_{1}, i_{2} < j_{2} ⟹ (i_{1}, j_{2}) ∈ Y and (i_{2}, j_{1}) ∈ Y.

Observe that from (1.3) it is easily seen that any ladder as well as any biladder is a generalized ladder. We now recall a basic result of Abhyankar [2, Thm. 20.10] (see also [10, Thm. 6.7]), which was alluded to in the Introduction. Theorem (1.14). Let p ∈ ℕ and Y ⊆ [1, m(1)] × [1, m(2)] be any generalized ladder. Given any V ∈ ℕ, the set (of residue classes of the elements of) {X^{θ} : θ ∈ mon(Y, p, V)} forms a free K-basis of the V -th homogeneous component K[Y]_{V} /I_{p+1}(Y)_{V} of the residue class ring K[Y]/I_{p+1}(Y). Consequently, the Hilbert function of the residue class ring K[Y]/I_{p+1}(Y) or of the corresponding projective variety V_{p+1}(Y) is given by

H(V) = |mon(Y, p, V)| (V ∈ ℕ).

2. Correspondence Between Radicals and Skeletons in a Biladder

Let S′, S ∈ lad(m) be such that len(S) ≠ 0 and S′ ≤ S. Let L and L^{0} denote the ladder L(S) and its interior L(S)^{0} respectively, and let L and L^{o} denote the biladder L(S′, S) and its interior L(S′, S)^{0} respectively. We may denote the boundary ∂S of L(S) by ∂L. The assumption that L is not the empty ladder will be tacitly used in proving some of the results in this section.

Our aim in this section is to prove that there exists a surjective map λ : rad(L) → skel(L^{o}) which is bijective when restricted to the subset marad(L) of all maximal radicals in rad(L). Here by a maximal radical we mean a radical which is not strictly contained in another radical. Thus we would obtain the inverse map μ : skel(L^{o}) →marad(L). We shall use this correspondence to reduce the problem of counting the radicals in L to that of counting the skeletons in L^{o}. These maps may be viewed as variants of Viennot’s ‘light and shadow procedure” (cf. [33]); however, the definitions given below are self-contained.

Given any radical R in the biladder L, or more generally, any subset R of L, we successively find points (i_{1}, j_{1}), (i_{2}, j_{2}), … in R ∩ L^{o} which lie on the corners as we trace the points of R ∩ L^{o} starting from the top right hand corner of the integral rectangle [1, m(1)] × [1, m(2)] traveling left and descending down only if no point of R ∩ L^{o} occurs further to the left; λ(R) is then defined as the set {(i_{1}, j_{1}), (i_{2}, j_{2}), … } consisting of the “corners”, and it is easily seen to be a well defined member of skel(L^{o}).

Construction of the map λ may be illustrated by the figures 3 (a) and 3 (b) drawn below. The set R, which happens to be a radical here, is described by hollow circles in Fig. 3 (a), while λ(R) is described by bullets or thick circles in Fig. 3 (b).

∘ ; ∘ ; ∘ ; ∘ ; ∘ ; ∘ ; ∘ ; ∘ ; ∘ ; ∘ ; ∘ ; ∘ ; ∘  ∘ ; ∘ ; • ; ∘ ; ∘ ; • ; ∘ ; ∘ ; ∘ ; • ; ∘ ; • ; ∘

Figure 3 (a) Figure 3 (b)

More precisely, we make the following definition. Definition (2.1). For any R ⊆ L, we define

λ(R) = {(i_{1}, j_{1}), (i_{2}, j_{2}), … (i_{l}, j_{l})},

where l ∈ ℕ and (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{l}, j_{l}) in R ∩ L^{o} are the unique elements such that upon letting i_{0} = 0 and j_{0} = m(2) we have

i_{s} = min{i ∈ (i_{s−1}, m(1)] : (i, j) ∈ R ∩ L^{o} for some j ∈ [1, j_{s−1})}, and
j_{s} = min{j ∈ [1, j_{s−1}) : (i_{s}, j) ∈ R ∩ L^{o}}; for s ∈ [1, l], and
{i ∈ (i_{l}, m(1)] : (i, j) ∈ R ∩ L^{o} for some j ∈ [1, j_{l})} = ∅.

Analogously, for any T ⊆ L, we define

λ̂(T) = {(i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{l}, j_{l})}

where l ∈ ℕ and (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{l}, j_{l}) in T ∩ L^{0} are the unique elements obtained by replacing R, L and L^{o} by T, L and L^{0} respectively in Definition (2.1).

We record below some elementary observations concerning the above definitions. Lemma (2.2). Given any R ⊆ L and T ⊆ L we have the following.

(i) λ(R) ∈ skel(L^{o}) and λ̂(T) ∈ skel(L^{0}). (ii) λ(R) = ∅ ⟺ R ∩ L^{o} = ∅ and λ̂(T) = ∅ ⟺ T ∩ L^{0} = ∅. (iii) λ(R) ⊆ R ∩ L^{o} and λ̂(T) ⊆ T ∩ L^{0}. (iv) λ(R) = R if R ∈ skel(L^{o}) and λ̂(T) = T if T ∈ skel(L^{0}).

(v) λ(R) = λ(R ∪ L^{∗}) for any L^{∗} ⊆ L \ L^{o} and λ̂(T) = λ̂(T ∪ L^{∗∗}) for any L^{∗∗} ⊆ ∂L.

(vi) λ̂(R) = λ(R)

Proof. Obvious.

In this section we are mainly interested in λ(R) and λ̂(T) when R ∈ rad(L) and T ∈ rad(L). At any rate we have defined the maps λ : rad(L) → skel(L^{o}), and λ̂ : rad(L) → skel(L^{0}) which equal the identity maps when restricted to the subsets skel(L^{o}) and skel(L^{0}) respectively. Hence in particular, both of these maps are surjective. We will now proceed to see how far these maps are injective and whether we can somehow obtain their inverses.

First we define the map μ on skel(L^{0}) which, vaguely speaking, would give the “inverse” of λ. The definition of μ will be given using that of the map μ̂ on skel(L^{0}). The construction for μ̂ may be briefly described as follows.

Given a skeleton E in the interior L^{0} of L, we can canonically associate a (maximal) radical μ̂(E) in L by drawing a path in L, with the points of E as its “corners”, traveling in a manner analogous to that described in the discussion before defining λ and λ̂. It may be necessary to include additional points in ∂L so that the path remains within L; these points can be characterized as those nodes of L such that no point of E lies in the rectangles having these as their bottom rightmost corner points. In the case of skeletons E in the interior of the biladder L, we shall obtain a radical μ(E) by considering the intersection of μ̂(E) with L.

Construction of the maps μ̂ and μ can be illustrated by the two figures below. Here we consider a skeleton E in the interior of a biladder, which is marked by bullets in Fig. 4 (a). The corresponding maximal radical μ̂(E) is given by the dotted path in Fig. 4 (b). Note that the points marked by a cross in Fig. 4 (b) are the “additional points” on the boundary, which are needed for the path to remain within the corresponding ladder.

• ; • ; • ; •  • • • •  × ×  ··················································· ····························· ··················· ········ ·················· ···················

Figure 4 (a) Figure 4 (b)

More precisely, we make the following definition. Definition (2.3). Given any E ∈ skel(L^{0}), we define

Ẽ = E ∪ {(p, q) ∈ N (S) : E ∩ ([1, p] × [1, q]) = ∅}

and, upon letting t and (α_{0}, β_{0}), (α_{1}, β_{1}), …, (α_{t+1}, β_{t+1}) be the unique elements such that t ∈ ℕ and Ẽ = {(α_{1}, β_{1}), …, (α_{t}, β_{t})} with

0 = α_{0} < α_{1} < ⋯ < α_{t} ≤ α_{t+1} = m(1)

and

m(2) = β_{0} ≥ β_{1} > β_{2} > ⋯ > β_{t} ≥ β_{t+1} = 1,

we define

μ̂(E) = ⋃_{r=1}^{t+1} ((α_{r−1}, α_{r}] × {β_{r−1}}) ∪ ({α_{r}} × [β_{r}, β_{r−1})) .

Lastly, given any E ∈ skel(L^{0}), we define

μ(E) = μ̂(E) ∩ L.

Now pictorially, it may appear obvious that μ̂(E) is a maximal radical in L for any E ∈ skel(L^{0}); to prove it formally however, seems to require a somewhat lengthy argument which we present below. The reader may wish to skip it depending upon his or her belief in pictures. Lemma (2.4). For any E ∈ skel(L^{0}), we have μ̂(E) ∈ marad(L) and |μ̂(E)| = m(1) + m(2) − 1.

Proof. Let E ∈ skel(L^{0}) and t ∈ ℕ. Let (α_{0}, β_{0}), (α_{1}, β_{1}), …, (α_{t+1}, β_{t+1}) in L be the unique elements corresponding to E as in Definition (2.3).

We shall first show that μ̂(E) ⊆ L. To this effect, for every r ∈ [1, t + 1] we will find some k^{∗} ∈ [1, len(S)] such that

S(1, k^{∗} − 1) ≤ α_{r−1} ≤ α_{r} ≤ S(1, k^{∗}) and β_{r} ≤ β_{r−1} ≤ S(2, k^{∗} − 1) (1)

thus showing that

(u, β_{r−1}) ∈ [S(1, k^{∗} − 1), S(1, k^{∗})] × [1, S(2, k^{∗} − 1)] ⊆ L ∀ u ∈ (α_{r−1}, α_{r}]

and

(α_{r}, v) ∈ [S(1, k^{∗} − 1), S(1, k^{∗})] × [1, S(2, k^{∗} − 1)] ⊆ L ∀ v ∈ [β_{r}, β_{r−1}).

For r = 1, we see that if α_{1} > S(1, 1) then 1 < len(S) and, since α_{i} ≥ α_{1} for i ≥ 1, we have

E ∩ ([1, S(1, 1)] × [1, S(2, 1)]) ⊆ Ẽ ∩ ([1, S(1, 1)] × [1, S(2, 1)]) = ∅,

which contradicts the definition of Ẽ. Thus α_{1} ≤ S(1, 1), also we have β_{0} = S(2, 0) = m(2), and therefore (1) holds with k^{∗} = 1 in the case r = 1.

Now let us suppose that r ∈ [2, t + 1]. Then there exists a unique k ∈ [1, len(S)] such that α_{r−1} ∈ [S(1, k − 1), S(1, k)) and β_{r−1} ∈ [1, S(2, k − 1)]. If k = len(S) then clearly α_{r} ≤ S(1, k), also we have β_{r−1} ≤ S(2, k − 1), and therefore (1) holds with k^{∗} = k. Thus we will now assume that k ∈ [1, len(S) − 1] and prove (1) by considering separately the two cases below. \underline{Case (i)}. β_{r−1} > S(2, k): In this case if α_{r} > S(1, k) then, in view of the fact that α_{r+i} ≥ α_{r} > S(1, k) and β_{r−i} ≥ β_{r−1} > S(2, k) for i ≥ 1, we find that

E ∩ ([1, S(1, k)] × [1, S(2, k)]) ⊆ Ẽ ∩ ([1, S(1, k)] × [1, S(2, k)]) = ∅,

which contradicts the definition of Ẽ. Thus α_{r} ≤ S(1, k), also we have β_{r−1} ≤ S(2, k − 1), and therefore (1) holds with k^{∗} = k. \underline{Case (ii)}. β_{r−1} ≤ S(2, k): In this case we let k′ to be the greatest integer such that β_{r−1} ≤ S(2, k′). Then k′ ≤ k < len(S) and S(2, k′ + 1) < β_{r−1} ≤ S(2, k′). Now using the same arguments as in Case (i) with k′ replacing k, we can show that α_{r} ≤ S(1, k′) and consequently (1) holds with k^{∗} = k′.

Having shown that μ̂(E) ⊆ L we will now prove that ind(μ̂(E)) ≤ 1. Suppose we are given any (i, j), (p, q) in μ̂(E) such that i < p and j < q. Then either (I) i = α_{r} for some r ∈ [1, t + 1] or (II) j = β_{r−1} for some r ∈ [1, t + 1]. In the first case, β_{r} ≤ j < β_{r−1} and, since j < q, we can find r′ ∈ [1, t + 1] such that r′ ≤ r and β_{r′} ≤ q < β_{r′−1}; but then we must have p ≤ α_{r′} ≤ α_{r} = i, which is a contradiction. In the second case, α_{r−1} < i ≤ α_{r} and, since i < p, we can find r′ ∈ [1, t + 1] such that r′ ≥ r and α_{r′−1} < p ≤ α_{r′}; but then we must have q ≤ β_{r′−1} ≤ β_{r−1} = j, which is a contradiction. Thus we have proved that μ̂(E) ∈ rad(L).

Now we show that μ̂(E) is maximal in rad(L). Thus suppose (p, q) ∈ L \ μ̂(E) is such that μ̂(E) ∪ {(p, q)} is in rad(L). We will arrive at a contradiction by exhibiting an element (i, j) ∈ μ̂(E) such that i < p and j < q. First we find the unique r ∈ [1, t+1] such that α_{r−1} < p ≤ α_{r}. Since μ̂(E)∪{(p, q)} is in rad(L) and (p, q) ∉ μ̂(E), we obtain that q < β_{r−1}. Now the desired (i, j) ∈ μ̂(E) is obtained by noting that (p, q) ≠ (α_{r}, β_{r}), and that r ≠ t + 1 if q < β_{r}, and by taking

(i, j) = \{ \begin{matrix}(α_{r}, β_{r−1}) & if p < α_{r} \\ (α_{r+1}, β_{r}) & if p = α_{r} and q < β_{r} \\ (α_{r−1}, β_{r}) & if p = α_{r} and q > β_{r} and r > 1 \\ (1, β_{r}) & if p = α_{r} and q > β_{r} and r = 1. \end{matrix}

Lastly, by the definition of μ̂(E), we clearly have that

|μ̂(E)| = ∑_{r=1}^{t+1}(α_{r} − α_{r−1}) + (β_{r−1} − β_{r}) = α_{t+1} − α_{0} + β_{0} − β_{t+1} = m(1) + m(2) − 1.

Thus we have defined the map μ̂ : skel(L^{0}) → marad(L). We describe its relation to the map λ̂ in the following two lemmas. Lemma (2.5). Given any T ∈ rad(L), we have T ⊆ μ̂(λ̂(T)), and moreover,

T ∈ marad(L) ⟺ T = μ̂(λ̂(T)) ⟺ |T | = m(1) + m(2) − 1.

Proof. First, in view of (2.4) and (i) of (2.2) , we see that λ̂(T) ∈ skel(L^{0}) and that μ̂(λ̂(T)) is a well defined member of marad(L). Let l, t, (i_{0}, j_{0}), …, (i_{l+1}, j_{l+1}), (α_{0}, β_{0}), …, (α_{t+1}, β_{t+1}) be the unique elements such that l, t ∈ ℕ and

\{ \begin{matrix}i_{0} < i_{1} < ⋯ < i_{l} < i_{l+1} = m(1), α_{0} < α_{1} < ⋯ < α_{t} < α_{t+1}, \\ j_{0} ≥ j_{1} > ⋯ > j_{l} ≥ j_{l+1} = 1, β_{0} ≥ β_{1} > ⋯ > β_{t} ≥ β_{t+1}, and \\ \{(i_{1}, j_{1}), …, (i_{l}, j_{l})\} = λ̂(T) ⊆ { \atop λ̂(T)} = \{(α_{1}, β_{1}), …, (α_{t}, β_{t})\}, \end{matrix} (2)

where, by convention

(i_{0}, j_{0}) = (α_{0}, β_{0}) = (0, m(2)) and (i_{l+1}, j_{l+1}) = (α_{t+1}, β_{t+1}) = (m(1), 1).

Let (i, j) ∈ T. Then there exist unique integers r ∈ [1, t + 1] and s ∈ [1, l + 1] such that α_{r−1} < i ≤ α_{r} and i_{s−1} < i ≤ i_{s}; further, in view of (2), it follows that

i_{s−1} ≤ α_{r−1} < i ≤ α_{r} ≤ i_{s} and j_{s−1} ≥ β_{r−1} ≥ β_{r} ≥ j_{s}. (3)

Now if j > β_{r−1} then r > 1 and (α_{r−1}, β_{r−1}) cannot be in λ̂(T) ⊆ T (because i > α_{r−1} and T ∈ rad(L)) and consequently (α_{r−1}, β_{r−1}) = (S(1, k), S(2, k)) for some k ∈ [1, len(S)]; but then, by observation (1.6), we find that (i, j) ∉ L, which is a contradiction. Thus j ≤ β_{r−1}; moreover, if j = β_{r−1} then

(i, j) ∈ (α_{r−1}, α_{r}] × {β_{r−1}} ⊆ μ̂(λ̂(T)). (4)

We shall now assume that j < β_{r−1} and prove that

(i, j) ∈ {α_{r}} × [β_{r}, β_{r−1}) ⊆ μ̂(λ̂(T)) (5)

by reaching at a contradiction in each of the remaining cases considered below. \underline{Case (i)}. i = α_{r} and j < β_{r}: Since (α_{r}, β_{r}) is either in L^{0} or equals (S(1, k), S(2, k)) for some k ∈ [1, len(S)], it follows from observation (1.10) that (i, j) ∈ T ∩ L^{0}. Now by (3), i > i_{s−1} and hence, by the definition of i_{s}, we see that i ≥ i_{s} which, using (3) once again, implies that i = i_{s} = α_{r}, and consequently β_{r} = j_{s}. But then (i_{s}, j) = (i, j) ∈ T ∩ L^{0} and j < β_{r−1} ≤ j_{s−1}, and so, by the definition of j_{s}, we find that j ≥ j_{s} = β_{r}, which is a contradiction. \underline{Case (ii)}. i < α_{r} and j ≤ β_{r}: As in Case (i), it follows from observation (1.10) that (i, j) ∈ T ∩ L^{0}, and that i ≥ i_{s}, implying that i = i_{s} = α_{r}, which is a contradiction. \underline{Case (iii)}. i < α_{r} and j > β_{r}: If (i, j) ∈ T ∩ L^{0}, then as in the two cases above, we would get i ≥ i_{s}, implying that i = i_{s} = α_{r}, which is a contradiction. Hence (i, j) ∈ L \ L^{0}, and so either i = S(1, k) for some k ∈ [1, len(S)] or j = S(2, k − 1) for some k ∈ [1, len(S)].

If i = S(1, k) for some k ∈ [1, len(S)] then S(2, k) ≤ j ≤ S(2, k − 1) and we see that λ̂(T) ∩ ([1, S(1, k)] × [1, S(2, k)]) = ∅, because if (u, v) is in this intersection then (u, v) = (α_{q}, β_{q}) for some q ∈ [1, t] and we have

α_{q} = u ≤ S(1, k) = i < α_{r} ⇒ q ≤ r − 1

and

β_{q} = v ≤ S(2, k) ≤ j < β_{r−1} ⇒ q ≥ r,

which is a contradiction. Moreover, since i < α_{r}, we have k < len(S), and hence

(S(1, k), S(2, k)) ∈ { \atop λ̂(T)} so that (S(1, k), S(2, k)) = (α_{q}, β_{q}) for some q ∈ [1, t], which is again seen to yield a contradiction. On the other hand, if j = S(2, k − 1) for some k ∈ [1, len(S)] then S(1, k − 1) ≤ i ≤ S(1, k), and in an analogous manner

we would find that k > 1 and (S(1, k − 1), S(2, k − 1)) ∈ { \atop λ̂(T)}, which would again lead to a contradiction.

This completes the proof that T ⊆ μ̂(λ̂(T)). Now, in view of (2.4), we can also conclude that

T ∈ marad(L) ⟺ T = μ̂(λ̂(T)) ⟺ |E| = m(1) + m(2) − 1.

Lemma (2.6). Given any E ∈ skel(L^{0}) and T ⊆ L we have

T ∈ rad(L) and λ̂(T) = E ⟺ E ⊆ T ⊆ μ̂(E).

In particular, λ̂(μ̂(E)) = E and μ̂(E) is the unique maximal element of the set λ̂^{−1}(E) = {T′ ∈ rad(L) : λ̂(T′) = E}.

Proof. If T ∈ rad(L) and λ̂(T) = E then, by (2.5) and (iii) of (2.2) we see that E = λ̂(T) ⊆ T ⊆ μ̂(λ̂(T)) = μ̂(E).

Conversely, suppose E ⊆ T ⊆ μ̂(E). Then, by (2.4), we see that μ̂(E) ∈ rad(L) and therefore T ∈ rad(L). We will now show that λ̂(T) ⊆ E and E ⊆ λ̂(T) to complete the proof. Let l, t, (i_{0}, j_{0}), …, (i_{l+1}, j_{l+1}), (α_{0}, β_{0}), …, (α_{t+1}, β_{t+1}) be the unique elements such that l ∈ ℕ, t ∈ ℕ, and

\{ \begin{matrix}0 = i_{0} < i_{1} < ⋯ < i_{l} < i_{l+1} = m(1), 0 = α_{0} < α_{1} < ⋯ < α_{t} < α_{t+1} = m(1), \\ m(2) = j_{0} ≥ j_{1} > ⋯ > j_{l} ≥ j_{l+1} = 1, m(2) = β_{0} ≥ β_{1} > ⋯ > β_{t} ≥ β_{t+1} = 1, \\ λ̂(μ̂(E)) = \{(i_{1}, j_{1}), …, (i_{l}, j_{l})\}, Ẽ = \{(α_{1}, β_{1}), …, (α_{t}, β_{t})\}, and \\ μ̂(E) = ⋃_{r=1}^{t+1} ((α_{r−1}, α_{r}] × \{β_{r−1}\}) ∪ (\{α_{r}\} × [β_{r}, β_{r−1})) . \end{matrix}

Note that {(α_{1}, β_{1}), …, (α_{t}, β_{t})} ∩ L^{0} = Ẽ ∩ L^{0} = E ⊆ T ∩ L^{0}. Also recall that, by observation (1.9), whenever (i, j) ∈ L^{0} we have i < m(1) and j < m(2). We shall use these facts tacitly in the proof below.

Given s ∈ [1, l], since T ⊆ μ̂(E), we can find a unique r ∈ [1, t + 1] such that either (I) i_{s} = α_{r} and β_{r} ≤ j_{s} < β_{r−1}, or (II) α_{r−1} < i_{s} ≤ α_{r} and j_{s} = β_{r−1}.

In the first case, since α_{r} = i_{s} < m(1) and (i_{s}, j_{s}) ∈ L^{0}, we see that r ≠ t + 1 and (α_{r}, β_{r}) ∈ T ∩ L^{0}, which contradicts the definition of j_{s} unless j_{s} = β_{r}. Thus if (I) holds then (i_{s}, j_{s}) = (α_{r}, β_{r}) ∈ E.

In the second case we note that the r, corresponding to each s ∈ [1, l], is always different from 1 since β_{r−1} = j_{s} < m(2).

We will now prove that (i_{s}, j_{s}) ∈ E by induction on s ∈ [1, l]. If s = 1 and if (II) holds then (α_{r−1}, β_{r−1}) ∈ T ∩ L^{0} and 0 = i_{0} < α_{r−1}, which contradicts the definition of i_{1}. Thus (i_{1}, j_{1}) ∈ E. Next, assume that s > 1 and that the assertion is true for all values of s smaller than the given one. If (II) holds and if i_{s−1} < α_{r−1} then (α_{r−1}, β_{r−1}) ∈ T ∩ L^{0} and the definition of i_{s} would be contradicted. So let us suppose that (II) holds and that i_{s−1} ≥ α_{r−1}. Then, since r ≠ 1 and α_{r−1} ≤ i_{s−1} < i_{s} ≤ α_{r}, we have that s ≠ 1 and, by the induction hypothesis, (i_{s−1}, j_{s−1}) = (α_{r−1}, β_{r−1}). But this contradicts the fact that β_{r−1} = j_{s} > j_{s−1}. Hence (i_{s}, j_{s}) ∈ E.

Thus we have proved that λ̂(T) ⊆ E. Suppose for some r ∈ [0, t + 1], (α_{r}, β_{r}) ∈ E ⊆ T ∩ L^{0}. Then r ∈ [1, t] and we can find a unique s ∈ [1, l + 1] such that i_{s−1} < α_{r} ≤ i_{s}. Since μ̂(E) ∈ rad(L) we must have β_{r} ≤ j_{s−1}. Now if α_{r} = i_{s} then s ≤ l, and since λ̂(T) ⊆ E, it follows that j_{s} = β_{r}. Whereas if α_{r} < i_{s} then the definition of i_{s} is contradicted unless β_{r} = j_{s−1} in which case s > 1, and using λ̂(T) ⊆ E once again, it follows that i_{s−1} = α_{r}. Hence in any case (α_{r}, β_{r}) ∈ λ̂(T). We thus conclude that λ̂(T) = E.

Theorem (2.7). Let λ̂^{∗} denote the restriction of λ̂ to the subset marad(L) of rad(L). Then λ̂^{∗} is a bijection of marad(L) onto skel(L^{0}) and its inverse is given by μ̂.

Proof. Follows from (2.4), (2.5), and (2.6).

We now turn to the case of biladders and obtain an analogue of the above theorem. In the rest of this section, we shall denote Δ(S′, S) simply by Δ. Thus

Δ = Δ(S′, S) = ∂S ∩ ∂S′ = ∂S ∩ L(S′).

First we will need the following basic lemma. Lemma (2.8). For any R ∈ rad(L), we have the following.

(i) R ∪ Δ ∈ rad(L). (ii) R ∈ marad(L) ⟺ R ∪ Δ ∈ marad(L) .

Proof. Let R ∈ rad(L). Note that clearly R ∪ Δ ⊆ L and R ∩ Δ = ∅; also note that by observation (1.7), Δ ∈ rad(L). Given any (i, j) ∈ R and (p, q) ∈ Δ, by observations (1.3) and (1.6), we have that

i < p, j < q ⇒ (i, j) ∈ L(S′), and i > p, j > q ⇒ (i, j) ∉ L(S)

yielding a contradiction in both the cases. Coupled with the fact that both R and Δ are in rad(L), this shows that R ∪ Δ ∈ rad(L) thus proving (i).

Now suppose R ∈ marad(L) and there exists some (i, j) ∈ L(S) such that (i, j) ∉ R∪Δ and R∪Δ∪{(i, j)} ∈ rad(L). Then (i, j) ∈ L(S′) lest the maximality of R is contradicted. Also since (i, j) ∉ Δ, it follows that (i, j) ∈ L(S)^{0} ∩ L(S′). Now let k be the least positive integer such that (i + k, j + k) ∉ L(S′). Then (i + k − 1, j + k − 1) is in L(S′) ⊆ L(S) and if it is not in L(S)^{0} then k > 1 and (i+k−1, j+k−1) ∈ Δ, which contradicts the fact that Δ∪{(i, j)} ∈ rad(L). Hence (i + k − 1, j + k − 1) ∈ L(S)^{0}, and consequently (i + k, j + k) ∈ L(S) \ L(S′) = L. Moreover for any (p, q) ∈ L, in view of observation (1.3) we see that

p < i + k, q < i + k ⇒ p ≤ i + k − 1, q ≤ i + k − 1 ⇒ (p, q) ∈ L(S′) ⇒ (p, q) ∉ L

and

p > i + k, q > i + k ⇒ p > i, q > i ⇒ (p, q) ∉ R,

where the last implication follows from the fact that R ∪ {(i, j)} ∈ rad(L). This shows that R∪{(i+k, j+k)} ∈ rad(L) contradicting the maximality of R in rad(L).

Conversely if for some R ∈ rad(L) we have that R ∪ Δ ∈ marad(L), then R is also maximal in rad(L), owing to (i) and the fact that L ∩ Δ = ∅.

Lemma (2.9). Given any E ∈ skel(L^{0}), we have μ(E) ∈ marad(L) and μ̂(E) = μ(E) ∪ Δ. Consequently, if we let M = m(1) + m(2) − 1 and δ_{0} = |Δ(S′, S)|, then we have |μ(E)| = M − δ_{0}.

Proof. Let E ∈ skel(L^{o}). Since μ(E) = μ̂(E) ∩ L it follows from (2.4) that μ(E) ∈ rad(L). We shall now show that μ̂(E) ⊆ μ(E) ∪ Δ. To this effect, let there be given any (i, j) ∈ μ̂(E). If (i, j) ∉ L and (i, j) ∉ Δ then (i, j) ∈ L(S′) ∩ L^{0}; suppose this is the case. Let t, (α_{0}, β_{0}), (α_{1}, β_{1}), …, (α_{t+1}, β_{t+1}) be the unique elements corresponding to E = E as in Definition (2.3). Now there exists a unique r ∈ [1, t + 1] such that either (I) i = α_{r} and β_{r} ≤ j < β_{r−1} or (II) α_{r−1} < i ≤ α_{r} and j = β_{r−1}. In the first case, since (i, j) ∈ L^{0}, it follows that i < m(1) so that r ≠ t+1 and (α_{r}, β_{r}) ∈ Ẽ ∩L^{0} = E ⊆ L; whereas, since (i, j) ∈ L(S′) and r ≠ t+1, it follows that (α_{r}, β_{r}) ∈ L(S′) yielding a contradiction. In the second case, we can similarly conclude that r ≠ 1 and (α_{r−1}, β_{r−1}) ∈ L and (α_{r−1}, β_{r−1}) ∈ L(S′) yielding a contradiction once again. Thus μ̂(E) ⊆ μ(E) ∪ Δ. Now, by (i) of (2.8), μ(E) ∪ Δ ∈ rad(L) and hence, by the maximality of μ̂(E) in rad(L), we must have μ̂(E) = μ(E) ∪ Δ. The remaining assertions follow readily from (2.4) and (2.8).

Thus we obtain the map μ : skel(L^{o}) → marad(L). As in the case of ladders, we now find out more about μ as well as λ. The results are described in the following two lemmas. Lemma (2.10). For any R ∈ rad(L), we have R ⊆ μ(λ(R)), and moreover,

R ∈ marad(L) ⟺ R = μ(λ(R)) ⟺ |R| = m(1) + m(2) − 1 − |Δ|.

Proof. Let R ∈ rad(L). Then R ∈ rad(L) and by (2.5) and (vi) of (2.2) it follows that R ⊆ μ̂(λ̂(R)) ∩ L = μ̂(λ(R)) ∩ L = μ(λ(R)), and moreover, in view of the fact that Δ ∩ L = ∅, we see that

R ∈ marad(L)
⟺ R ∪ Δ ∈ marad(L)  by (2.8)
⟺ R ∪ Δ = μ̂(λ̂(R ∪ Δ))  by (2.5) and (2.8)
⟺ R = (R ∪ Δ) ∩ L = μ̂(λ̂(R ∪ Δ)) ∩ L  by (2.5) and (2.8)
⟺ R = μ̂(λ(R)) ∩ L  by (2.8) and (v), (vi) of (2.2)
⟺ R = μ(λ(R)).

Finally, since R ∩ Δ = ∅, it follows from (2.5) and (2.8) that

R ∈ marad(L) ⟺ R ∪ Δ ∈ marad(L) ⟺ |R| = m(1) + m(2) − 1 − |Δ|.

Lemma (2.11). Given any E ∈ skel(L^{0}) and R ⊆ L we have that

R ∈ rad(L) and λ(R) = E ⟺ E ⊆ R ⊆ μ(E).

In particular, λ(μ(E)) = E and μ(E) is the unique maximal element of the set λ^{−1}(E) = {R′ ∈ rad(L) : λ(R′) = E}.

Proof. If R ∈ rad(L) and λ(R) = E then, by (2.9) and (iii) of (2.2), we see that E = λ(R) ⊆ R ⊆ μ(λ(R)) = μ(E). Conversely, if E ⊆ R ⊆ μ(E) then, by (2.9), R ∈ rad(L), and, in view of (2.5) and (vi) of (2.2), it follows that λ(R) = λ̂(R) = E. This proves the desired equivalence. The remaining assertions are now evident.

We are now ready to prove the main result of this section. Theorem (2.12). Let λ^{∗} denote the restriction of λ to the subset marad(L) of rad(L). Then λ^{∗} is a bijection of marad(L) onto skel(L^{0}) and its inverse is given by μ.

Proof. Follows from (2.9), (2.10) and (2.11).

Finally in this section we obtain an enumerative consequence of the correspondence described in the above theorem. Recall that for any l ∈ ℕ, skel(L^{o}, l) denotes the set of all skeletons E in L^{o} of “size” l, i.e., |E| = l, and that for any d ∈ ℕ, rad(L, d) denotes the set of all radicals R in L of “size” d, i.e., |R| = d. Theorem (2.13). Let M = m(1) + m(2) − 1 and δ_{0} = |Δ(S′, S)|. Then for any d ∈ ℕ we have

|rad(L, d)| = ∑_{l∈ℕ} |skel(L^{o}, l)|\binom{M − δ_{0} − l}{d − l}

where the summation on the right is essentially finite.

Proof. Let d ∈ ℕ. Since λ : rad(L) → skel(L^{o}) is onto, we have

rad(L, d) = ∐_{E∈skel(L^{o})} λ^{−1}(E) ∩ rad(L, d) = ∐_{l∈ℕ} ∐_{E∈skel(L^{o},l)} λ^{−1}(E) ∩ rad(L, d).

By (2.11), we see that λ^{−1}(E) = {R : E ⊆ R ⊆ μ(E)}, and consequently,

λ^{−1}(E) ∩ rad(L, d) = {R : E ⊆ R ⊆ μ(E) and |R| = d}.

The desired formula now follows from the above equalities by applying (1.14) and (2.9). The essential finiteness follows, for example, by noting that the binomial coefficient in the above summation vanishes if l > d.

3. Enumeration of Skeletons in a Biladder

Let S′ and S be in lad(m) with S′ ≤ S. Let h = len(S) and h′ = len(S′). Let L and L^{o} denote the biladder L(S′, S) and its interior L(S′, S)^{0} respectively. Let l ∈ ℕ. We will continue to assume that h = len(S) ≠ 0. Further, we shall assume that h′ = len(S′) ≠ 0. These assumptions will be tacitly used in some of the results proved in this section.

Our aim in this section is to count the set skel(L^{o}, l) of all skeletons in L^{o} of size l. Now an element of skel(L^{o}, l) can be represented by a pair of sequences of length l, one of which is (strictly) increasing and the other one is (strictly) decreasing. Thus if L^{o} were the entire rectangle [1, m(1)] × [1, m(2)], then |skel(L^{o}, l)| would simply equal \binom{m(1)}{l}\binom{m(2)}{l}. However, the problem of finding |skel(L^{o}, l)| appears increasingly difficult even if L^{o} were the set obtained by cutting off a corner each from the top left hand side and the bottom right hand side of the above rectangle. Naturally, in order to find |skel(L^{o}, l)|, the condition for a pair of “increasing– decreasing” sequences to correspond to a skeleton within L^{o} needs to be expressed in a more suitable manner. We do this by decomposing the set skel(L^{o}, l) into smaller and smaller disjoint subsets. Finding the cardinalities of the “components” along with some manipulation, then results into a concrete (but complicated!) formula for |skel(L^{o}, l)|.

We begin by introducing some notation which will be used in the rest of this paper. Given any h^{∗} ∈ ℕ, we let ℕ(h^{∗}) denote the set of all sequences of length h^{∗} whose terms are nonnegative integers, i.e.,

ℕ(h^{∗}) = {u = (u(1), u(2), …, u(h^{∗})) : u(k) ∈ ℕ for all k ∈ [1, h^{∗}]}.

Given any u ∈ ℕ(h^{∗}) and k ∈ [1, h^{∗}], we may sometimes write u_{k} to mean u(k). Next, given any m^{∗} ∈ ℕ^{+} and l^{∗} ∈ ℕ, we let

inc(m^{∗}, l^{∗}) = {a ∈ ℕ(l^{∗}) : 0 < a(1) < a(2) < ⋯ < a(l^{∗}) < m^{∗}}, and
dec(m^{∗}, l^{∗}) = {b ∈ ℕ(l^{∗}) : m^{∗} > b(1) > b(2) > ⋯ > b(l^{∗}) > 0}.

Finally, a note concerning notation. Given any two sets X and Y and a map f : X → Y, by im(f) we denote the image of f, i.e., im(f) is the subset {f(x) : x ∈ X} of Y; for any y ∈ Y, by f^{−1}(y) or f^{−1}{y} we denote the set {x ∈ X : f(x) = y}. Observe that if Z is any set with im(f) ⊆ Z ⊆ Y, then we have

X = ∐_{z∈Z} f^{−1}(z), where ∐ denotes disjoint union as usual .

Now the desired decomposition of skel(L^{o}, l) will be achieved by using, among other things, the maps defined below. Definition (3.1).

(i) Given any E ∈ skel(L^{o}, l), define E^{1} and E^{2} to be the unique elements in inc(m(1), l) and dec(m(2), l) respectively such that

E = {(E^{1}(i), E^{2}(i)) : i ∈ [1, l]}.

(ii) Define the “projection map” π : skel(L^{o}, l) → inc(m(1), l) by

π(E) = E^{1}, for E ∈ skel(L^{o}, l).

(iii) Define the map ρ : inc(m(1), l) → ℕ(h) × ℕ(h′) by putting,

ρ(a) = (e, e′), for a ∈ inc(m(1), l),

where we have temporarily let e and e′ denote the unique elements of ℕ(h) and ℕ(h′) respectively, given by

e(k) = |{i ∈ [1, l] : a(i) < S(1, k)}| for all k ∈ [1, h]

and

e′(k′) = |{i ∈ [1, l] : a(i) < S′(1, k′)}| for all k′ ∈ [1, h′].

Lemma (3.2). Let (e, e′) ∈ ℕ(h) × ℕ(h′). Then we have the following. (i) ρ^{−1}{(e, e′)} is equal to

\begin{matrix}\{a ∈ inc(m(1), l) : \{i ∈ [1, l] : a(i) < S(1, k)\} = [1, e(k)] ∀ k ∈ [1, h], \\ and \{i ∈ [1, l] : a(i) < S′(1, k′)\} = [1, e′(k′)] ∀ k ∈ [1, h′]\}. \end{matrix}

(ii) If (e, e′) ∈ im(ρ) then we have

(3.2.1)  0 ≤ e(1) ≤ ⋯ ≤ e(h) = l and 0 ≤ e′(1) ≤ ⋯ ≤ e′(h′) = l.

Proof. Let a ∈ ρ^{−1}{(e, e′)}. For k ∈ [1, h], if we let

i_{k} = max{i ∈ [1, l] : a(i) < S(1, k)}

then, in view of the fact that a ∈ inc(m(1), l), it follows that

{i ∈ [1, l] : a(i) < S(1, k)} = [1, i_{k}];

therefore i_{k} = e(k). It is now evident that ρ^{−1}{(e, e′)} ⊆ [RHS of (i)]. The other inclusion being obvious, this proves (i).

Given any (e, e′) ∈ im(ρ), we can find some a ∈ inc(m(1), l) such that ρ(a) = (e, e′). Now for any k ∈ [1, h − 1] and k′ ∈ [1, h′ − 1], since S(1, k) < S(1, k + 1) and S′(1, k′) < S′(1, k′ + 1), we have e(k) ≤ e(k + 1) and e′(k′) ≤ e′(k′ + 1). Moreover, since S(1, h) = S′(1, h′) = m(1) and a(i) < m(1) for all i ∈ [1, l], we have e(h) = e′(h′) = l. This proves (ii).

Lemma (3.3). For any a ∈ ℕ(l), let ā denote the set {a(1), a(2), …, a(l)}. For any (e, e′) ∈ ℕ(h) × ℕ(h′), let e(0) = 0 = e′(0), and let A(e, e′) denote the set

\begin{aligned}\{a ∈ inc(m(1), l) : & |ā ∩ [S(1, k − 1), S(1, k))| = e(k) − e(k − 1) ∀ k ∈ [1, h] and \\ & |ā ∩ [S′(1, k′ − 1), S′(1, k′))| = e′(k′) − e′(k′ − 1) ∀ k′ ∈ [1, h′]\}. \end{aligned}

Then we have the following.

(i) ρ^{−1}{(e, e′)} = A(e, e′) for all (e, e′) ∈ ℕ(h) × ℕ(h′).

(ii) The set skel(L^{o}, l) decomposes as

skel(L^{o}, l) = ∐_{a∈inc(m(1),l)} π^{−1}(a) = ∐_{(e,e′)} ∐_{a∈A(e,e′)} π^{−1}(a),

where (e, e′) range over all elements of ℕ(h) × ℕ(h′) satisfying (3.2.1).

Proof. Follows from (3.2).

Now let us fix (until Lemma (3.8)) some (e, e′) ∈ ℕ(h) × ℕ(h′) satisfying (3.2.1), and also let us fix some a ∈ ρ^{−1}{(e, e′)}. We now proceed to find |π^{−1}(a)|. To this effect we first decompose the set π^{−1}(a) by using the map defined below. Definition (3.4). Define the map θ : π^{−1}(a) → ℕ(h) × ℕ(h′) by putting, for any E ∈ π^{−1}(a), θ(E) = (f, f′), where we have temporarily let f and f′ to be the unique elements of ℕ(h) and ℕ(h′) respectively such that

f(k) = |{j ∈ [1, l] : E^{2}(j) ≥ S(2, k)}|, for all k ∈ [1, h]

and

f′(k′) = |{j ∈ [1, l] : E^{2}(j) > S′(2, k′ − 1)}|, for all k′ ∈ [1, h′].

Lemma (3.5). Let (f, f′) ∈ ℕ(h) × ℕ(h′). Then we have the following. (i) θ^{−1}{(f, f′)} equals

{E ∈ skel(L^{o}, l) : E^{1} = a, {j ∈ [1, l] : E^{2}(j) ≥ S(2, k)} = [1, f(k)],
{j ∈ [1, l] : E^{2}(j) > S′(2, k′ − 1)} = [1, f′(k′)]
for all k ∈ [1, h] and k′ ∈ [1, h′]}.

(ii) If (f, f′) ∈ im(θ), then we have

(3.5.1)  \{ \begin{matrix}0 ≤ f(1) ≤ ⋯ ≤ f(h) = l, 0 ≤ f′(1) ≤ ⋯ ≤ f′(h′) = l, \\ f(k) ≤ e(k) ∀ k ∈ [1, h] and f′(k′) ≥ e′(k′) ∀ k′ ∈ [1, h′]. \end{matrix}

Proof. If E ∈ θ^{−1}(f, f′) then, in view of the fact that E^{2} ∈ dec(m(2), l), it follows that

{j ∈ [1, l] : E^{2}(j) ≥ S(2, k)} = [1, f(k)] for all k ∈ [1, h], and
{j ∈ [1, l] : E^{2}(j) > S′(2, k′ − 1)} = [1, f′(k′)] for all k′ ∈ [1, h′].

This shows that θ^{−1}(f, f′) is contained in the set on the right hand side of the equality asserted in (i). The other inclusion being obvious, this proves (i).

Now let us assume that (f, f′) ∈ im(θ). Fix some E ∈ skel(L^{o}, l) such that θ(E) = (f, f′). For all k ∈ [1, h − 1] and k′ ∈ [1, h′ − 1] we have S(2, k) ≥ S(2, k + 1) and S′(2, k′ − 1) ≥ S′(2, k′), and therefore it follows that f(k) ≤ f(k + 1) and f′(k′) ≤ f′(k′ + 1). Moreover, since S(2, h) = 1, we see that f(h) = l, and since E ∩ L(S′) = ∅ and [1, m(1)] × [1, S′(2, h′ − 1)] ⊆ L(S′), we also see that f′(h′) = l.

Now, by (3.2) we have that

{i ∈ [1, l] : E^{1}(i) < S(1, k)} = [1, e(k)] for all k ∈ [1, h], and
{i ∈ [1, l] : E^{1}(i) < S′(1, k′)} = [1, e′(k′)] for all k′ ∈ [1, h′].

Consequently, if for some k ∈ [1, h], we have f(k) > e(k), then 1 ≤ f(k) ≤ l and E^{1}(f(k)) ≥ S(1, k). Also by (i) we have E^{2}(f(k)) ≥ S(2, k). Thus

E^{1}(f(k)) ∈ [S(1, k), m(1)) and E^{2}(f(k)) ∉ [1, S(2, k)).

This is a contradiction since ([S(1, k), m(1)) × [S(2, k), m(2)]) ∩ L(S)^{0} = ∅. Similarly, if for some k′ ∈ [1, h′] we have f′(k′) < e′(k′), then it can be seen that we have 1 ≤ e′(k′) ≤ l and

E^{2}(e′(k′)) ∈ [1, S′(2, k′ − 1)] and E^{1}(e′(k′)) ∈ [1, S′(1, k′)),

which is contradiction since [1, S′(1, k′)) × [1, S′(2, k′ − 1)] ⊆ L(S′). This proves Lemma (3.6). Let (f, f′) ∈ ℕ(h) × ℕ(h′) be such that (3.5.1) holds. Let B(f, f′) denote the set

{b ∈ dec(m(2), l) : |{j ∈ [1, l] : b(j) ≥ S(2, k)}| = f(k), for all k ∈ [1, h] and
|{j ∈ [1, l] : b(j) > S′(2, k′ − 1)}| = f′(k′) for all k′ ∈ [1, h′]}.

Then we have the following.

(i) There exists a one-to-one correspondence between θ^{−1}{(f, f′)} and B(f, f′). In particular, |θ^{−1}{(f, f′)}| = |B(f, f′)|.

(ii) Given any b ∈ ℕ(l), let b̄ = {b(1), b(2), …, b(l)}. Also, let f(0) = 0 and f′(h′ + 1) = l. Then B(f, f′) equals

\begin{matrix}\{b ∈ dec(m(2), l) : |b̄ ∩ [S(2, k), S(2, k − 1))| = f(k) − f(k − 1) ∀ k ∈ [1, h], \\ and |b̄ ∩ (S′(2, k′), S′(2, k′ − 1)]| = f′(k′ + 1) − f′(k′) ∀ k′ ∈ [1, h′]\}. \end{matrix}

Proof. Consider the map E ↦ E^{2} of θ^{−1}{(f, f′)} → B(f, f′). By (3.4) we see that this map is well defined; moreover it is clearly injective. To show that it is surjective as well, let there be given any b ∈ B(f, f′). Let E ∈ skel([1, m(1)] × [1, m(2)], l) be the unique element such that E^{1} = a and E^{2} = b. It suffices to show that E ⊆ L^{o} = L(S)^{0} \ L(S′). Given any i ∈ [1, l], we have a(i) < m(1), and hence there exists a unique k ∈ [1, h] such that S(1, k − 1) ≤ a(i) < S(1, k); consequently i > e(k − 1) (because e(0) = 0 and for k > 1, {i′ ∈ [1, l] : a(i′) < S(1, k − 1)} = [1, e(k − 1)]), and therefore i > f(k − 1), so that b(i) < S(2, k − 1). Also S(2, 0) = m(2) > b(i) for all i ∈ [1, l]. Thus we have

(a(i), b(i)) ∈ [S(1, k − 1), S(1, k)) × [1, S(2, k − 1)) ⊆ L(S) for all i ∈ [1, l].

Similarly, given any j ∈ [1, l], there exists a unique k′ ∈ [1, h′] with the property that S′(1, k′ −1) ≤ a(j) < S′(1, k′); consequently, j ≤ e′(k′) ≤ f′(k′), and therefore b(j) > S′(2, k′ − 1) (because {j ∈ [1, l] : b(j) > S′(2, k′ − 1)} = [1, f′(k′)]). Thus for any j ∈ [1, l], we have

(a(j), b(j)) ∉ ∐_{k′∈[1,h′]} [S′(1, k′ − 1), S′(1, k′]) × [1, S′(2, k′ − 1)] = L(S′).

This proves the first assertion. The second assertion is evident in view of the fact that f′(1) = 0 = f(0).

Having characterized θ^{−1}{(f, f′)} as above, it is now a relatively easy matter to find its cardinality. The cardinality of ρ^{−1}{(e, e′)} can also be found in an analogous manner in view of (3.3). We separate the essential enumerative argument in the general proposition below. Proposition (3.7). Let C be a finite set. Suppose {C_{k} : 1 ≤ k ≤ h} and {C′_{k′} : 1 ≤ k′ ≤ h′} are two families of subsets of C, and {w_{k} : 1 ≤ k ≤ h} and {w′_{k′} : 1 ≤ k′ ≤ h′} are two families of nonnegative integers such that

C = ∐_{k=1}^{h} C_{k} = ∐_{k′=1}^{h′} C′_{k′} and l = ∑_{k=1}^{h} w_{k} = ∑_{k′=1}^{h′} w′_{k′}.

Let 𝒫(C, l) denote the set of all subsets of C of cardinality l, and let

S = {E ∈ 𝒫(C, l) : |E ∩ C_{k}| = w_{k} ∀ k ∈ [1, h] and |E ∩ C′_{k′}| = w′_{k′} ∀k′ ∈ [1, h′]}.

Then, upon letting C_{k,k′} = C_{k} ∩ C′_{k′} for all k ∈ [1, h] and k′ ∈ [1, h′], we have

|S| = ∑_{α=(α_{kk′})} ∏_{\begin{matrix}1 ≤ k ≤ h \\ 1 ≤ k′ ≤ h′ \end{matrix}} \binom{|C_{k,k′}|}{α_{kk′}},

where the sum is taken over all h × h′ matrices α = (α_{kk′}) ∈ M_{h h′}(ℕ, l) such that

∑_{k=1}^{h} α_{kk′} = w′_{k′} ∀ k′ ∈ [1, h′] and ∑_{k′=1}^{h′} α_{kk′} = w_{k} ∀ k ∈ [1, h].

Proof. Follows by noting that C = ∐ C_{k,k′}, where the disjoint union is taken over all (k, k′) ∈ [1, h] × [1, h′], and that the map E ↦ (E ∩ C_{k,k′})_{(k,k′)∈[1,h]×[1,h′]} sets up a one-to-one correspondence:

S ⟷ ∐_{α} ∏_{(k,k′)} {E^{∗} : E^{∗} ⊆ C_{k,k′} and |E^{∗}| = α_{kk′}} ,

where the direct product of sets is taken over all (k, k′) ∈ [1, h] × [1, h′], and the disjoint union is taken over all α = (α_{kk′}) ∈ M_{h h′}(ℕ, l) such that ∑_{k=1}^{h} α_{kk′} = w′_{k′} ∀ k′ ∈ [1, h′] and ∑_{k′=1}^{h′} α_{kk′} = w_{k} ∀ k ∈ [1, h].

Notation: Given a ladder L = L(S′, S), where S′ ∈ lad[m′, h′] and S ∈ lad[m, h] are such that S′ ≤ S, and (k, k′) ∈ [1, h] × [1, h′] we let

μ_{L}(k, k′) = |[S(1, k − 1), S(1, k)) ∩ [S′(1, k′ − 1), S′(1, k′))|

and

ν_{L}(k, k′) = |[S(2, k), S(2, k − 1)) ∩ (S′(2, k′), S′(2, k′ − 1)]|.

Lemma (3.8). Given any (e, e′) ∈ ℕ(h) × ℕ(h′) satisfying (3.2.1) [in particular, any (e, e′) ∈ im(ρ)], we have that

|ρ^{−1}\{(e, e′)\}| = ∑_{α=(α_{kk′})} ∏_{\begin{matrix}1 ≤ k ≤ h \\ 1 ≤ k′ ≤ h′ \end{matrix}} \binom{μ_{L}(k, k′)}{α_{kk′}},

where the sum is taken over all h × h′ matrices α = (α_{kk′}) ∈ M_{h h′}(ℕ, l) such that

(3.8.1)  \{ \begin{matrix}∑_{k=1}^{h} α_{kk′} = e′(k′) − e′(k′ − 1) ∀ k′ ∈ [1, h′], \\ ∑_{k′=1}^{h′} α_{kk′} = e(k) − e(k − 1) ∀ k ∈ [1, h], \\ where, by convention, e(0) = e′(0) = 0. \end{matrix}

Proof. Let (e, e′) ∈ ℕ(h) × ℕ(h′) be such that (3.2.1) holds. Further, let C = [1, m(1)) and for 1 ≤ k ≤ h and 1 ≤ k′ ≤ h′, let

\begin{matrix}C_{k} = [S(1, k − 1), S(1, k)) & and & C′_{k′} = [S′(1, k′ − 1), S′(1, k′)), \\ w_{k} = e(k) − e(k − 1) & and & w′_{k′} = e′(k′) − e′(k′ − 1). \end{matrix}

Then in view of (3.2) we clearly see that

C = ∐_{k=1}^{h} C_{k} = ∐_{k′=1}^{h′} C′_{k′} and l = ∑_{k=1}^{h} w_{k} = ∑_{k′=1}^{h′} w′_{k′}.

Now the assertion readily follows from (3.2), (3.3), and (3.7) by noting that the map a ↦ ā sets up a natural one-to-one correspondence between inc(m(1), l) and the set consisting of all subsets E of [1, m(1)) with |E| = l.

Using arguments similar to those used in the proof of the above lemma, we can easily obtain a formula for |θ^{−1}{(f, f′)}| as given below. This time we leave the details to the reader. Lemma (3.9). Given any (f, f′) ∈ ℕ(h) × ℕ(h′) satisfying (3.5.1) [in particular, any (f, f′) ∈ im(θ)], we have that

|θ^{−1}\{(e, e′)\}| = ∑_{β=(β_{kk′})} ∏_{\begin{matrix}1 ≤ k ≤ h \\ 1 ≤ k′ ≤ h′ \end{matrix}} \binom{ν_{L}(k, k′)}{β_{kk′}},

where the sum is taken over all h × h′ matrices β = (β_{kk′}) ∈ M_{h h′}(ℕ, l) such that

(3.9.1)  \{ \begin{matrix}∑_{k=1}^{h} β_{kk′} = f′(k′) − f′(k′ − 1) ∀ k′ ∈ [1, h′], \\ ∑_{k′=1}^{h′} β_{kk′} = f(k) − f(k − 1) ∀ k ∈ [1, h], \\ where, by convention, f(0) = 0 and f′(h′ + 1) = l. \end{matrix}

Proof. Follows from (3.5), (3.6), and (3.7).

Let us define

S(L^{o}, l) = ∑_{\begin{matrix}α, β ∈ M_{h h′} (ℕ, l) \\ σ(β) ≤ σ(α), τ(β) ≤ τ(α) \end{matrix}} ∏_{\begin{matrix}1 ≤ k ≤ h \\ 1 ≤ k′ ≤ h′ \end{matrix}} \binom{μ_{L}(k, k′)}{α_{kk′}}\binom{ν_{L}(k, k′)}{β_{kk′}}.

With this notation, some of the results obtained in this section can be combined into the following theorem. Theorem (3.10). Given any l ∈ ℕ, we have

|skel(L^{o}, l)| = S(L^{o}, l).

Proof. By (3.3) we have

skel(L^{o}, l) = ∐_{(e,e′)} ∐_{a∈ρ^{−1}{(e,e′)}} π^{−1}(a),

where the first disjoint union is taken over all (e, e′) ∈ ℕ(h) × ℕ(h′) satisfying (3.2.1). Now for any a ∈ ρ^{−1}{(e, e′)},

π^{−1}(a) = ∐_{(f,f′)} θ^{−1}{(f, f′)}

where the disjoint union is taken over all (f, f′) ∈ ℕ(h) × ℕ(h′) satisfying (3.5.1); hence by (3.9) we see that |π^{−1}(a)| depends only on the pair (e, e′) and not on the choice of a ∈ ρ^{−1}{(e, e′)}. Consequently,

|skel(L^{o}, l)| = ∑_{(e,e′)} |ρ^{−1}{(e, e′)}| ∑_{(f,f′)} |θ^{−1}{(f, f′)}|

where (e, e′) and (f, f′) range over all elements of ℕ(h) × ℕ(h′) satisfying (3.2.1) and (3.5.1) respectively. Now by applying (3.8) and (3.9) we find that |skel(L^{o}, l)| is given by

∑_{(e,e′)} ∑_{α=(α_{kk′})} ∏_{\begin{matrix}1 ≤ k ≤ h \\ 1 ≤ k′ ≤ h′ \end{matrix}} \binom{μ_{L}(k, k′)}{α_{kk′}} ∑_{(f,f′)} ∑_{β=(β_{kk′})} ∏_{\begin{matrix}1 ≤ k ≤ h \\ 1 ≤ k′ ≤ h′ \end{matrix}} \binom{ν_{L}(k, k′)}{β_{kk′}},

where α = (α_{kk′}) and β = (β_{kk′}) range over all elements of M_{h h′}(ℕ, l) satisfying (3.8.1) and (3.9.1) respectively.

Fix (e, e′) ∈ ℕ(h)×ℕ(h′) satisfying (3.2.1) and α = (α_{kk′}) ∈ M_{h h′}(ℕ, l) satisfying (3.8.1). Then the union

\begin{aligned}⋃_{(f,f′)}\{β = (β_{kk′}) ∈ M_{h h′}(ℕ, l) : & ∑_{k=1}^{h} β_{kk′} = f′(k′ + 1) − f′(k′) ∀ k′ ∈ [1, h′] and \\ & ∑_{k′=1}^{h′} β_{kk′} = f(k + 1) − f(k) ∀ k ∈ [1, h]\} \end{aligned}

taken over all (f, f′) ∈ ℕ(h) × ℕ(h′) satisfying (3.5.1), can be easily seen to be disjoint and to equal the set

\begin{aligned}\{β = (β_{kk′}) ∈ M_{h h′}(ℕ, l) : & σ_{p}(β) ≤ e(p) = σ_{p}(α) ∀ p ∈ [1, h] and \\ & τ_{q}(β) ≤ l − e(q) = τ_{q}(α) ∀ q ∈ [1, h′]\} \end{aligned}

where it may be recalled that for β = (β_{kk′}) ∈ M_{h h′}(ℕ, l), p ∈ [1, h] and q ∈ [1, h′] we have put

σ_{p}(β) = ∑_{k=1}^{p} ∑_{k′=1}^{h′} β_{kk′} and τ_{q}(β) = ∑_{k′=q}^{h′} ∑_{k=1}^{h} β_{kk′}.

Finally we note that the union

\begin{aligned}⋃_{(e,e′)}\{α = (α_{kk′}) ∈ M_{h h′}(ℕ, l) : & ∑_{k=1}^{h} α_{kk′} = e′(k′) − e′(k − 1′) ∀ k′ ∈ [1, h′] and \\ & ∑_{k′=1}^{h′} α_{kk′} = e(k) − e(k − 1) ∀ k ∈ [1, h]\} \end{aligned}

taken over all (e, e′) ∈ ℕ(h) × ℕ(h′) satisfying (3.2.1), is also easily seen to be disjoint and to equal the set M_{h h′}(N, l). It follows that the above formula for |skel(L^{o}, l)| can be written as

∑_{α∈M_{h h′} (ℕ,l)} ∑_{\begin{matrix}β ∈ M_{h h′} (ℕ, l) \\ σ(β) ≤ σ(α), τ(β) ≤ τ(α) \end{matrix}} ∏_{\begin{matrix}1 ≤ k ≤ h \\ 1 ≤ k′ ≤ h′ \end{matrix}} \binom{μ_{L}(k, k′)}{α_{kk′}}\binom{ν_{L}(k, k′)}{β_{kk′}}.

This proves the theorem.

Remark (3.11). Since we have assumed in the beginning of this section that h′ ≠ 0, the above result seems to apply only to ‘proper’ biladders L = L(S) \ L(S′) with L(S′) ≠ ∅ . To cover the important special case when L = L = L(S) is a ladder (so that h′ = 0), we note that Kulkarni [21] (see also [22, Thm. 4] and [20, Prop. 4]) has already proved that |skel(L^{o}, l)| = S(L^{o}, l), where

S(L^{o}, l) = ∑_{e} ∑_{f} \binom{μ_{L}(k)}{e_{k}}\binom{ν_{L}(k)}{f_{k}},

where

μ_{L}(k) = |[S(1, k − 1), S(1, k))| = S(1, k) − S(1, k − 1) for 1 ≤ k ≤ h

and

ν_{L}(k) = |[S(2, k), S(2, k − 1))| = S(2, k − 1) − S(2, k) for 1 ≤ k ≤ h

and where the first summation is over all e = (e_{1}, …, e_{h}) ∈ ℕ(h) such that

0 ≤ e_{i} ≤ l for 1 ≤ i ≤ h and e_{h} = l

while the second summation is over all f = (f_{1}, …, f_{h}) ∈ ℕ(h) such that

0 ≤ f_{i} ≤ e_{i} for 1 ≤ i ≤ h and f_{h} = l.

It may be noted that this formula follows from our Theorem (3.10) by an obvious extension of L(S) to a larger rectangle [1, m(1) + 1] × [1, m(2) + 1] and taking L(S′) to be the top hook of this enlarged rectangle, i.e., letting S′ be the unique ladder generating bisequence of length 2 such that (S′(1, 1), S′(2, 1)) = (1, 1). At any rate, we have a formula |skel(L^{o}, l)| also in the case h′ = 0 and in this way S(L^{o}, l) is defined and Theorem (3.10) holds for any biladder L.

4. Enumeration of Indexed Monomials

Let S′, S ∈ lad(m) be such that len(S) ≠ 0 and S′ ≤ S. Let L and L^{o} denote the biladder L(S′, S) and its interior L(S′, S)^{0} respectively.

In this section we shall use the results obtained so far to find a formula for the Hilbert function of K[L]/I_{p+1}(L) for the given biladder L and any p ∈ ℕ^{+}. As remarked in the Introduction, by Theorem (1.14), it suffices to find a formula for the cardinality of the set mon(L, V, p) of monomials in L of degree V and index ≤ p. To this end we first notice that the latter problem can be easily reduced to the problem of finding a formula for the number of the so-called p–fold radicals in L of a given length. Then comes one of the main steps, namely that a p–fold radical is split into a radical and a (p − 1)–fold radical in a smaller biladder. Such splitting is unique in some sense and it allows us to obtain the desired formula recursively. It may be remarked that the above splitting can be viewed as a refinement of the superskeleton decomposition used in [3]. Lemma (4.1). Given any V ∈ ℕ and p ∈ ℕ^{+}, we have

|mon(L, V, p)| = ∑_{d=0}^{V} \binom{V − 1}{V − d}|rad^{p}(L, d)|.

Proof. It is clear that if θ ∈ mon(L, p, V), then |supp(θ)| ≤ V. Now consider the map

Φ : mon(L, p, V) → ∐_{d=0}^{V} rad^{p}(L, d)

defined by θ ↦^{Φ} supp(θ). Given any d ∈ [0, V] and R ∈ rad^{p}(L, d), by (1.12) we have

|Φ^{−1}(R)| = \left[{d − 1 \atop V − d}\right] = \binom{V − 1}{V − d}.

Since the RHS above is independent of the choice of R within rad^{p}(L, d), the desired equality is immediate.

As a corollary of this lemma and the theorem proved in the previous section we can obtain a formula for the number of monomials of degree V and index ≤ 1 as follows. It may be noted that this generalizes the result of Kulkarni [21] which gives such a formula in the case of a ladder. Theorem (4.2). Let M = m(1) + m(2) − 1 and δ_{0} = |Δ(S′, S)|. Then for any d ∈ ℕ and any V ∈ ℕ, we have

|mon(L, V, 1)| = ∑_{ℓ=0}^{V} \left[{V − ℓ \atop M − δ_{0} − 1}\right]S(L^{o}, ℓ).

Consequently, the Hilbert function as well as the Hilbert polynomial of K[L]/I_{2}(L) is given by the formula above. Moreover, if L is nonempty, then this formula is a polynomial in the parameter V with coefficients in ℚ, of degree M − δ_{0} − 1 and leading coefficient \frac{1}{(M−δ_{0}−1)!} ∑_{ℓ∈ℕ} S(L^{o}, ℓ).

Proof. Note that if L = ∅, then δ_{0} = M, and thus the desired result clearly holds. Now assume that L ≠ ∅. By (4.1) and (2.13) we see that

|mon(L, V, 1)| = ∑_{d=0}^{V} \binom{V − 1}{V − d} ∑_{ℓ=0}^{d} \binom{M − δ_{0} − l}{d − ℓ}|skel(L^{o}, ℓ)|.

Interchanging the summations, we can write the RHS as

∑_{ℓ=0}^{V} \{∑_{d=ℓ}^{V} \binom{V − 1}{V − d}\binom{M − δ_{0} − ℓ}{d − ℓ}\} |skel(L^{o}, ℓ)|

= ∑_{ℓ∈ℕ} \left[{M − δ_{0} − 1 \atop V − ℓ}\right]|skel(L^{o}, ℓ)|

where the last step follows from (iv) of (1.11). Finally we note that since L ≠ ∅, we have M − δ_{0} − 1 ≥ 1, and hence in view of (v) and (vi) of (1.11) as well as (3.10) and (3.11), we get the formula for |mon(L, V, 1)| as asserted. From (1.14) it follows that this formula gives the Hilbert function of K[L]/I_{2}(L). It is also the Hilbert polynomial since the binomial coefficients appearing in this formula are evidently polynomials in V. It is clear that the degree in V of this polynomial is M − δ_{0} − 1 and the coefficient of V^{M−δ_{0}−1} is equal to \frac{1}{(M−δ_{0}−1)!} ∑_{ℓ∈ℕ} S(L^{o}, ℓ), which is nonzero since L is nonempty.

We shall now attempt to generalize the above result by first finding |rad^{p}(L, d)| for any nonnegative integer d. The splitting discussed in the beginning of this section is achieved by means of the map Γ obtained from the following definition. Definition (4.3). Given any p ∈ ℕ^{+} and R ∈ rad^{p}(L), we define

γ(R) = μ(λ(R)) ∩ R and Γ(R) = (γ(R), R \ γ(R)).

The construction of γ(R) (and hence of Γ(R)) can be illustrated by figures 5 (a) and (b) drawn below. Here, we consider a 3-fold radical R, which is indicated by the hollow circles in Fig. 5 (a), and the corresponding radical γ(R) is given by the bullets or thick circles in Fig. 5 (b).

∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘  ∘ ∘ ∘ ∘  ∘ • • • • • ∘ ∘ ∘ • • • • ∘ ∘ ∘ •  ∘ • ∘ ∘

Figure 5 (a) Figure 5 (b)

Lemma (4.4). For any p ∈ ℕ^{+} and R ∈ rad^{p}(L), we have

ind(γ(R)) ≤ 1 and ind(R \ γ(R)) ≤ p − 1.

Proof. By (2.9) we see that ind(γ(R)) ≤ 1 since γ(R) ⊆ μ(λ(R)). Now if R = ∅, then both the assertions are trivially true and thus we assume that R ≠ ∅. Hence λ(R) ≠ ∅, and we can find l ∈ ℕ^{+}, and integers i_{1} < ⋯ < i_{l} and j_{1} < ⋯ < j_{l} such that λ(R) = {(i_{1}, j_{1}), …, (i_{l}, j_{l})}. Recall that we take i_{0} = 0, i_{l+1} = m(1), j_{0} = m(2), j_{l+1} = 1, and for s ∈ [1, l],

(6) i_{s} = min{i ∈ (i_{s−1}, m(1)] : (i, j) ∈ R ∩ L^{o} for some j ∈ [1, j_{s−1})}

and

j_{s} = min{j ∈ [1, j_{s−1}) : (i_{s}, j) ∈ R ∩ L^{o}}. (7)

If p = 1 then R ∈ rad(L), and hence by (2.10), R ⊆ μ(λ(R)) so that γ(R) = R and ind(R \ γ(R)) = 0. Thus we shall now assume that p > 1. Suppose, if possible, ind(R \ γ(R)) ≥ p. Then we can find (a_{1}, b_{1}), (a_{2}, b_{2}), … (a_{p}, b_{p}) in R \ γ(R) such that a_{1} < a_{2} < ⋯ < a_{p} and b_{1} < b_{2} < ⋯ < b_{p}. Since p > 1, it follows from (1.5) that (a_{1}, b_{1}) ∈ R ∩ L^{o}, and so by (5) we see that i_{1} ≤ a_{1}. Further, if i_{1} = a_{1}, then by (6), we have j_{1} ≤ b_{1}, and thus (a_{1}, b_{1}) ∈ {i_{1}} × [j_{1}, j_{0}) ⊆ μ(λ(R)), which is a contradiction. Hence i_{1} < a_{1}, and so there exists a unique k ∈ [1, l] such that i_{k} < a_{1} ≤ i_{k+1}. Now if b_{1} < j_{k} then by (5), a_{1} = i_{k+1}, and hence by (6), b_{1} ≥ j_{k+1}. Consequently, k + 1 ≤ l and (a_{1}, b_{1}) ∈ {i_{k+1}} × [j_{k+1}, j_{k}) ⊆ μ(λ(R)), which is a contradiction. Also if b_{1} = j_{k}, then (a_{1}, b_{1}) ∈ (i_{k}, i_{k+1}] × {j_{k}} ⊆ μ(λ(R)), again yielding a contradiction. Thus we must have j_{k} < b_{1}, which gives us the sequence (i_{k}, j_{k}), (a_{1}, b_{1}), … (a_{p}, b_{p}) of elements of R such that i_{k} < a_{1} < ⋯ < a_{p} and j_{k} < b_{1} < ⋯ < b_{p}, contrary to the assumption that ind(R) ≤ p.

Thus Γ defines a map of rad^{p}(L) into rad(L)×rad^{p−1}(L). This map is obviously injective. A characterization of the image of Γ is given by the lemma below. Lemma (4.5). Let p ∈ ℕ^{+} and R ∈ rad^{p}(L). Then there exists a unique S_{R} ∈ lad(m) with

(8) len(S_{R}) ≠ 0, S′ ≤ S_{R} ≤ S and Δ(S′, S_{R}) = Δ(S′, S),

such that

γ(R) ⊆ ∂S_{R}, R \ γ(R) ⊆ L(S_{R}, S) and { \atop λ(R)} = { \atop λ(γ(R))} = N (S_{R}).

Conversely, given any S^{∗} ∈ lad(m) with

(9) len(S^{∗}) ≠ 0, S′ ≤ S^{∗} ≤ S and Δ(S′, S^{∗}) = Δ(S′, S),

and any (U, U^{∗}) ∈ rad(L) × rad^{p−1}(L) such that

U ⊆ ∂S^{∗}, U^{∗} ⊆ L(S^{∗}, S) and { \atop λ(U)} = N (S^{∗}), (10)

there exists a unique S_{R} ∈ lad(m) such that Γ(R) = (U, U^{∗}) and S_{R} = S^{∗}.

Proof. Let R ∈ rad^{p}(L). Let t ∈ ℕ and (α_{0}, β_{0}), (α_{1}, β_{1}), …, (α_{t+1}, β_{t+1}) be the unique elements such that { \atop λ(R)} = \{(α_{1}, β_{1}), …, (α_{t}, β_{t})\} with

0 = α_{0} < α_{1} < ⋯ < α_{t} ≤ α_{t+1} = m(1)

and

m(2) = β_{0} ≥ β_{1} > β_{2} > ⋯ > β_{t} ≥ β_{t+1} = 1.

Define S_{R} ∈ lad[m, t + 1] by S_{R}(1, 0) = 1, S_{R}(2, 0) = m(2), S_{R}(1, k) = α_{k} and S_{R}(2, k) = β_{k} for all k ∈ [1, t + 1]. It is clear that len(S_{R}) ≠ 0 and S_{R} is uniquely determined by R. Further, by (1.2) and (2.9), we have

∂S_{R} = μ̂(λ(R)) = μ(λ(R)) ∪ Δ(S′, S) ⊆ L(S).

Hence, in view of (1.4) and (1.8), it follows that L(S_{R}) ⊆ L(S), i.e., S_{R} ≤ S. To see that S′ ≤ S_{R}, let there be given any (i, j) ∈ L(S′). Then we can find a unique r ∈ [1, t + 1] such that α_{r−1} < i ≤ α_{r}. Suppose if possible j > β_{r−1}. Then we must have r > 1, and by (1.5), we have (α_{r−1}, β_{r−1}) ∈ L(S′)^{o}. Moreover, since r − 1 ∈ [1, t], it follows that either (α_{r−1}, β_{r−1}) ∈ λ(R) ⊆ L or (α_{r−1}, β_{r−1}) ∈ ∂S. In any case, this is a contradiction because in view of (1.4) and (1.8) we have L(S′)^{o} ⊆ L(S)^{o}. This shows that (i, j) ∈ (α_{r−1}, α_{r}] × [1, β_{r−1}] ⊆ L(S_{R}). Thus, S′ ≤ S_{R}. Also, since μ(λ(R)) ⊆ L, we have

Δ(S′, S_{R}) = ∂S_{R} ∩ L(S′) = Δ(S′, S) ∩ L(S′) = Δ(S′, S).

This proves (7). Further, since ∂S_{R} = μ̂(λ(R)), we have

γ(R) = μ(λ(R)) ∩ R = μ̂(λ(R)) = ∂S_{R}.

We now proceed to show that R \ γ(R) ⊆ L(S_{R}, S) = L(S) \ L(S_{R}). To this end, let (i, j) ∈ R \ γ(R). Since R ⊆ L, we have γ(R) = μ̂(λ(R)) ∩ R, and hence (i, j) ∉ μ̂(λ(R)) = ∂S_{R}. So, it suffices to show that (i, j) ∉ L(S_{R})^{o}. Now write λ(R) = {(i_{1}, j_{1}), …, (i_{l}, j_{l})} where (i_{1}, j_{1}), …, (i_{l}, j_{l}) are as in (2.1). Now if (i, j) ∈ L(S_{R})^{o}, then (i, j) ∈ R ∩ L, and therefore i_{1} ≤ i < m(1). Hence we can find a unique s ∈ [1, l] such that i_{s} ≤ i < i_{s+1}, where by convention, i_{l+1} = m(1). Now if i = i_{s}, then by (2.1), we have j ≥ j_{s}. Also, if i > i_{s}, and if we had j < j_{s}, then s + 1 ≤ l and i_{s+1} ≤ i, which is a contradiction. Thus in any case j ≥ j_{s}. Since λ(R) ⊆ λ̂(R) = N (S_{R}), can find k^{∗} ∈ [1, t] such that (i_{s}, j_{s}) = (S_{R}(1, k^{∗}), S_{R}(2, k^{∗})). Moreover, since (i, j) ∈ L(S_{R})^{o}, there exists a unique k ∈ [1, t + 1] such that

S_{R}(1, k − 1) ≤ i < S_{R}(1, k) and 1 ≤ j < S_{R}(2, k − 1).

In particular, S_{R}(1, k^{∗}) = i_{s} ≤ i < S_{R}(1, k), and hence k^{∗} ≤ k − 1. Consequently, j_{s} = S_{R}(2, k^{∗}) ≥ S_{R}(2, k − 1) > j, which is a contradiction. This proves that R \ γ(R) ⊆ L(S_{R}, S). The equality { \atop λ(R)} = N (S_{R}) is obvious whereas the equality { \atop λ(R)} = { \atop λ(γ(R))} follows from (2.11) in view of the fact that λ(R) ⊆ γ(R) ⊆ μ(λ(R)).

To prove the converse, let there be given any S^{∗} ∈ lad(m) satisfying (9) and (U, U^{∗}) ∈ rad(L)×rad^{p−1}(L) satisfying (10). Put R = U ∪U^{∗}. Since U and U^{∗} are disjoint, it follows that ind(R) ≤ p. Thus R ∈ rad^{p}(L). All the remaining assertions will readily follow if we show that U = γ(R). To this end, we first show that λ(R) = λ(U). Write λ(R) = {(i_{1}, j_{1}), …, (i_{l}, j_{l})} where (i_{1}, j_{1}), …, (i_{l}, j_{l}) and (i_{0}, j_{0}) are as in (2.1). Suppose λ(R) ⊈ λ(U). Then we can find s which is the least integer in [1, l] with the property that (i_{s}, j_{s}) ∉ λ(U). Now (i_{s}, j_{s}) ∈ L(S)^{o}, and so in view of (1.9), we can find some k ∈ [1, len(S^{∗})] such that S^{∗}(1, k − 1) ≤ i_{s} < S^{∗}(1, k). Further, since (i_{s}, j_{s}) ∈ U ∪U^{∗}, it follows that (i_{s}, j_{s}) ∉ L(S^{∗})^{o}, and hence j_{s} ≥ S^{∗}(2, k −1). In particular, k > 1. Also, by (1.4), (S^{∗}(1, k − 1), S^{∗}(2, k − 1)) is in L(S)^{o}; in fact it is in L^{o} because if it were in L(S′), then it would be in Δ(S′, S^{∗}) = Δ(S′, S), and hence in ∂S, which is a contradiction. Further, if i_{s−1} ≥ S^{∗}(1, k − 1), then s > 1 and since j_{s−1} > j_{s} ≥ S^{∗}(2, k − 1), it follows that (i_{s−1}, j_{s−1}) ∉ L(S^{∗}). This contradicts the minimality of s because λ(U) ⊆ { \atop λ(U)} ⊆ L(S^{∗}). Therefore, i_{s−1} < S^{∗}(1, k − 1) ≤ i_{s}. It follows that

(S^{∗}(1, k − 1), S^{∗}(2, k − 1)) ∈ { \atop λ(U)} ∩ L^{o} ⊆ λ(U) ∩ L^{o} ⊆ R ∩ L^{o}

Now, in view of (2.1), we obtain that S^{∗}(1, k − 1) = i_{s} and S^{∗}(2, k − 1) = j_{s}. Consequently, (i_{s}, j_{s}) ∈ { \atop λ(U)} ∩ L^{o} ⊆ λ(U), which is contrary to our assumption. Thus we have shown that λ(R) ⊆ λ(U). To prove the reverse inclusion, we note that λ(U) ⊆ N (S^{∗}), and let k ∈ [1, len(S^{∗}) − 1] be such that (S^{∗}(1, k), S^{∗}(2, k)) ∈ λ(U). Let (i_{0}, j_{0}), (i_{1}, j_{1}), …, (i_{l}, j_{l}) be as above so that λ(R) = {(i_{1}, j_{1}), …, (i_{l}, j_{l})}. Since λ(U) ⊆ U ∩ L^{o} ⊆ R ∩ L^{o}, we can find s ∈ [1, l] such that i_{s−1} < S^{∗}(1, k) ≤ i_{s}. We claim that S^{∗}(2, k − 1) < j_{s−1}. This claim is obvious if s = 1. Moreover, if s > 1, then using the inclusion λ(R) ⊆ λ(U), we get (i_{s−1}, j_{s−1}) = (S^{∗}(1, k′), S^{∗}(2, k′)) for some k′ ∈ [1, len(S^{∗}) − 1]. Now clearly, k′ < k, and hence S^{∗}(2, k) < S^{∗}(2, k′) = j_{s−1}. This proves our claim. Next, in view of (2.1), we obtain that i_{s} = S^{∗}(1, k). Using the inclusion λ(R) ⊆ λ(U) once again, we can deduce that (S^{∗}(1, k), S^{∗}(2, k)) = (i_{s}, j_{s}). Thus λ(R) = λ(U). Hence,

{ \atop λ(R)} = { \atop λ(U)} = N (S^{∗})

and therefore, μ̂(λ(R)) = ∂S^{∗}. Consequently,

U ⊆ ∂S^{∗} ∩ R ⊆ μ̂(λ(R)) ∩ R = μ(λ(R)) ∩ R = γ(R).

Moreover, γ(R) = μ̂(λ(R)) ∩ R ⊆ ∂S^{∗}, and hence γ(R) ∩ U^{∗} = ∅, as desired. The remaining assertions are now evident.

Lemma (4.6). Let M = m(1) + m(2) − 1 and δ_{0} = |Δ(S′, S)|. Then for any d ∈ ℕ and p ∈ ℕ^{+}, we have

|rad^{p}(L, d)| = ∑_{S^{∗}} ∑_{d_{1}+d_{2}=d} \binom{M − δ_{0} − ν^{∗}}{d_{1} − ν^{∗}}|rad^{p−1}(L^{∗}, d_{2})|,

where the first sum is over all S^{∗} ∈ lad(m) satisfying (9), and the second sum is over all (d_{1}, d_{2}) ∈ ℕ×ℕ such that d_{1}+d_{2} = d, and where ν^{∗} = |N (S^{∗})\[N (S) ∩ N (S^{∗})] | and L^{∗} denotes the biladder L(S^{∗}, S).

Proof. In view of (4.5), we see that rad^{p}(L, d) is in one-to-one correspondence with

∐_{S^{∗}} ∐_{d_{1}+d_{2}=d} \left\{{(U, U^{∗}) : U ⊆ ∂S^{∗} ∩ rad(L, d_{1}), { \atop λ(U)} = N (S^{∗}), \atop and U^{∗} ∈ rad^{p−1}(L^{∗}, d_{2})}\right\} ,

where the first disjoint union is taken over all S^{∗} ∈ lad(m) satisfying (9). Note that in each of the components in the decomposition above, U and U^{∗} vary independently. Moreover, we claim that the condition on U is equivalent to asserting that

U ⊆ ∂S^{∗} ∩ L, |U| = d_{1} and U ⊇ λ(U) = N (S^{∗}) \ [N (S) ∩ N (S^{∗})] . (11)

To verify this claim, suppose U ⊆ ∂S^{∗} ∩ rad(L, d_{1}) and { \atop λ(U)} = N (S^{∗}). Then clearly U ⊆ ∂S^{∗} ∩ L, and

λ(U) ⊆ { \atop λ(U)} ∩ L(S)^{o} = N (S^{∗}) ∩ L(S)^{o} ⊆ N (S^{∗}) \ [N (S) ∩ N (S^{∗})] .

Moreover, since N (S^{∗})\λ(U) = { \atop λ(U)}\λ(U) ⊆ N (S), we have N (S^{∗})\N (S) ⊆ λ(U). This proves (10). Conversely, if (10) holds, then in view of (1.7), we see that U ⊆ ∂S^{∗} ∩ rad(L, d_{1}). Further, if (α, β) ∈ { \atop λ(U)} \ λ(U), then (α, β) = (S(1, k), S(2, k)) for some k ∈ [1, len(S) − 1]. Now let k^{∗} ∈ [1, len(S^{∗}) − 1] be the unique integer such that S^{∗}(1, k^{∗}) ≤ α < S^{∗}(1, k^{∗} + 1). We must have S^{∗}(2, k^{∗}) ≤ S(2, k) because otherwise S(2, k) ∈ [1, S^{∗}(2, k^{∗})) so that (S(1, k), S(2, k)) ∈ L(S^{∗})^{o} ⊆ L(S)^{o}, which is a contradiction. Thus (S^{∗}(1, k^{∗}), S^{∗}(2, k^{∗})) is in [1, α] × [1, β], and since the intersection of the latter with λ(U) is empty, it follows that

(S^{∗}(1, k^{∗}), S^{∗}(2, k^{∗})) ∉ λ(U) = N (S^{∗}) \ [N (S) ∩ N (S^{∗})] .

Thus (S^{∗}(1, k^{∗}), S^{∗}(2, k^{∗})) ∈ N (S), and this forces that (S^{∗}(1, k^{∗}), S^{∗}(2, k^{∗})) = (S(1, k), S(2, k)). Thus (α, β) ∈ N (S^{∗}). Thus { \atop λ(U)} ⊆ N (S^{∗}). Further, if (α, β) ∈ N (S)∩N (S^{∗}), then ([1, α] × [1, β])∩N (S^{∗}) = \{(α, β)\}, and therefore (α, β) ∈ { \atop λ(U)}. This proves our claim. Lastly, observe that if U satisfies (10), then ∂S^{∗} ∩ L = μ(λ(U)), and thus in view of (2.9), we have |∂S^{∗} ∩ L| = M − δ_{0}. Now applying (1.13), we see that

| {U : |U| = d_{1} and N (S^{∗}) \ [N (S) ∩ N (S^{∗})] ⊆ U ⊆ ∂S^{∗} ∩ L } |
= \binom{M − δ_{0} − ν^{∗}}{d_{1} − ν^{∗}}.

This yields the desired formula.

We are now ready to state and prove the main results of this paper. First, we need some notation, which will be useful in the sequel. Notation: Given any p ∈ ℕ^{+}, we let D_{p}(L) denote the set of all (p − 1)-tuples S = (S_{1}, …, S_{p−1}) of elements of lad(m) such that

len(S_{i}) ≠ 0 and Δ(S_{i−1}, S_{i}) = Δ(S_{i−1}, S), for 1 ≤ i ≤ p − 1,

and

S′ ≤ S_{1} ≤ ⋯ ≤ S_{p−1} ≤ S.

Given any S = (S_{1}, …, S_{p−1}) ∈ D_{p}(L), we let S_{0} = S′ and

δ(S) = ∑_{i=0}^{p−1} δ_{i}, where δ_{i} = |∂S_{i−1} ∩ ∂S|, for 0 ≤ i ≤ p − 1;

further, we let L_{p−1} = L(S_{p−1}, S), and

ν(S) = ∑_{i=1}^{p−1} ν_{i}, where ν_{i} = |N (S_{i}) \ (N (S_{i}) ∩ N (S))|, for 1 ≤ i ≤ p − 1.

Given S = (S_{1}, …, S_{p−1}) ∈ D_{p}(L) and u ∈ ℕ, we let

F_{u}(S) = ∑_{ℓ≥0} \binom{ν(S) + ℓ}{u}S(L_{p−1}^{o}, ℓ).

Note that since S(L_{p−1}^{o}, ℓ) vanishes for all large enough ℓ, the summation above is essentially finite. Finally, we let, as before, M = m(1) + m(2) − 1.

Observe that D_{p}(L) is nonempty since it always contains the (p − 1)-tuple (S, …, S). If p = 1, D_{p}(L) is the nonempty set containing the empty tuple S (say), and in this case δ(S) = δ_{0}, ν(S) = 0 and L_{p−1} = L.

Lemma (4.7). If the biladder L is nonempty, then for any p ∈ ℕ^{+} and S = (S_{1}, …, S_{p−1}) ∈ D_{p}(L), we have

pM − δ(S) − ν(S) − 1 ≥ 0.

Proof. Let i ∈ [1, p − 1]. Then S_{i} ≤ S. We claim that

N (S_{i}) ∩ ∂S ⊆ N (S).

To see this, suppose a node P = (S_{i}(1, l), S_{i}(2, l)) of S_{i} is in ∂S. Then by (1.2), we have either P = (α, S(2, k − 1)) with S(1, k − 1) < α ≤ S(1, k) or P = (S(1, k), β) with S(2, k) ≤ β < S(2, k − 1), for some k ∈ [1, h]. Now S(2, l − 1) > S(2, l) and thus in the first case, we have

(α, S(2, k − 1) + 1) = (S_{i}(1, l), S_{i}(2, l) + 1) ∈ L(S_{i}) ⊆ L(S)

which is a contradiction since α > S(1, k − 1). Similarly, in the second case

(S(1, k) + 1, β) = (S_{i}(1, l) + 1, S_{i}(2, l)) ∈ L(S_{i}) ⊆ L(S)

which is a contradiction unless β = S(2, k). Thus P = (S(1, k), S(2, k)). Moreover k ≠ h since P ∈ N (S_{i}). This proves the Claim. As a consequence, ∂S ∩ ∂S_{i} and N (S_{i}) \ (N (S_{i}) ∩ N (S)) are disjoint and their union is contained in ∂S_{i}. Therefore,

δ_{i} + ν_{i} ≤ |∂S_{i}| = M, for 1 ≤ i ≤ p − 1.

Further, since L ≠ ∅, we have M − δ_{0} − 1 ≥ 0, and hence

pM − δ(S) − ν(S) − 1 = (M − δ_{0} − 1) + ∑_{i=1}^{p−1} (M − (δ_{i} + ν_{i})) ≥ 0.

Theorem (4.8). Given any p ∈ ℕ^{+} and d ∈ ℕ, we have

|rad^{p}(L, d)| = ∑_{S∈D_{p}(L)} ∑_{ℓ≥0} \binom{pM − δ(S) − ν(S) − ℓ}{d − ν(S) − ℓ}S(L_{p−1}^{0}, ℓ).

where the summation on the right is essentially finite.

Proof. If p = 1, then the result follows from (2.13). If p > 1, we see from (4.6) using induction on p that |rad^{p}(L, d)| is equal to

∑_{S∈D_{p}(L)} ∑_{d_{1}+···+d_{p}=d} ∏_{i=1}^{p−1} \binom{M − δ_{i} − ν_{i}}{d_{i} − ν_{i}}|rad(L_{p−1}, d_{p})|.

Now the desired result follows from (2.13) using (iv) and (vii) of (1.11). The essential finiteness is evident since S(L_{p−1}^{o}, ℓ) vanishes for all large enough ℓ.

Theorem (4.9). Given any any p ∈ ℕ^{+} and V ∈ ℕ, we have

|mon(L, V, p)| = F (V).

where

F (V) = ∑_{u≥0} ∑_{S∈D_{p}(L)}(−1)^{u}F_{u}(S)\binom{V + pM − δ(S) − 1 − u}{pM − δ(S) − 1 − u}.

Consequently, the Hilbert function as well as the Hilbert polynomial of the ring K[L]/I_{p+1}(L) is given by F (V).

Proof. Consider first the trivial case when L = ∅; here we have |mon(L, V, p)| = 0, for any V ∈ ℕ. Now L = ∅ corresponds to taking S′ = S. Hence in this case

S = (S_{1}, …, S_{p−1}) ∈ D_{p}(L) ⟺ S_{i} = S ∀i ⟹ ν(S) = 0 and δ(S) = pM.

Further, L_{p−1} = ∅, and so S(L_{p−1}^{0}, ℓ) = 1 if ℓ = 0, and 0 otherwise. Hence,

F_{u}(S) = ∑_{ℓ≥0} \binom{l}{u}S(L_{p−1}^{0}, ℓ) = \{ \begin{matrix}1 & if u = 0 \\ 0 & if u > 0. \end{matrix}

Consequently, for any V ∈ ℕ, we have

F (V) = \binom{V + pM − δ(S) − 1}{pM − δ(S) − 1} = \binom{V − 1}{−1} = 0.

Thus we shall now assume that L is nonempty. Fix some V ∈ ℕ. By (4.1) and (4.8), we can write |mon(L, V, p)| as

∑_{d=0}^{V} ∑_{S∈D_{p}(L)} ∑_{ℓ≥0} \binom{V − 1}{V − d}\binom{pM − δ(S) − ν(S) − ℓ}{d − ν(S) − ℓ}S(L_{p−1}^{0}, ℓ).

Interchanging summations and using (iv) of (1.11) together with (4.7) and (vi) of (1.11), we can write the above expression as

∑_{S∈D_{p}(L)} ∑_{ℓ≥0} \left[{V − ν(S) − ℓ \atop pM − δ(S) − 1}\right]S(L_{p−1}^{0}, ℓ). (12)

Now, in view of (iv) and (vii) of (1.11), we have

\left[{V − ν(S) − ℓ \atop pM − δ(S) − 1}\right] = ∑_{u≥0} (−1)^{u}\left[{V \atop pM − δ(S) − 1 − u}\right]\binom{ν(S) + ℓ}{u}.

Using this we obtain the desired expression for |mon(L, V, p)| by interchanging summations once again. The remaining assertions follow from (1.14) and the fact that the binomial coefficients appearing in F (V) are polynomials in V while the coefficients (−1)^{u}F_{u}(S) are independent of V.

Corollary (4.10). For any p ∈ ℕ^{+}, I_{p+1}(L) is a Hilbertian ideal.

Proof. Follows from (4.9).

Remarks (4.11). 1. Lemmas (4.5) and (4.6) may motivate the use of biladders although one may only be interested in (one-sided) ladders. Indeed, even if L were a ladder to begin with, the L^{∗} that one obtains in (4.6) is necessarily a biladder. Thus it makes sense to have the results of Sections 2 and 3 in the general case of biladders.

2. The formulae in (4.8) and (4.9) are no doubt complicated and perhaps they may seem unworthy of being called ‘explicit’, in view of the rather unwieldy summation over D_{p}(L). Indeed, from this viewpoint, only the formula in the case of p = 1 is truly explicit. Nevertheless, these formulae are much more explicit than any of the known formulae (e.g., those given by [3, Sec. 4] or [17, Cor. 4.3]) in the general case of biladder, and to illustrate this we will show that our formulae can be used to deduce some interesting information about the variety associated to I_{p+1}(L). For example, it is shown in the next section that one can derive fairly simple estimates for the degree of the Hilbert polynomial. It may also be observed that, as Krattenthaler and Prohaska [20, Sec. 7] seem to suggest, it appears unlikely that an elegant and simple formula for the Hilbert function of I_{p+1}(L) can be found.

5. Applications

It is well-known that if H(V) is the Hilbert polynomial of a projective variety, and if

H(V) = \frac{e}{d!}V^{d} + c_{1}V^{d−1} + ⋯ + c_{d} with e, c_{1}, …, c_{d} ∈ ℤ and e ≠ 0,

then the degree d of H(V) is the dimension of that projective variety and the ‘normalized leading coefficient’ e is its order or the multiplicity. Note that the dimension d can also be read off from the Hilbert series; indeed, we have

∑_{V =0}^{∞} H(V) t^{V} = \frac{P(t)}{(1 − t)^{d+1}} , where P(t) ∈ ℤ[t] with P(1) ≠ 0.

Moreover, d + 1 is the (Krull) dimension of the corresponding homogeneous coordinate ring. The polynomial P(t) is sometimes called the h-polynomial (and its coefficient vector is referred to as an h-vector) of the vanishing ideal of that variety,

With this in view, we now attempt to extract some information about the degree as well as the leading coefficient of the Hilbert polynomial F (V) of the ladder determinantal variety V_{p+1}(L), and the corresponding Hilbert series. First, we need some notation.

Fix some p ∈ ℕ^{+} and a biladder L = L(S′, S). Let M, D_{p}(L), δ(S), L_{p−1}, F_{u}(S) and F (V) be as defined in Section 4. Further, we let

δ^{∗}(L) = min{δ(S) : S ∈ D_{p}(L)}

and

D_{p}^{∗}(L) = {S ∈ D_{p}(L) : δ(S) = δ^{∗}(L)}.

Proposition (5.1). The degree of the Hilbert polynomial F (V) of V_{p+1}(L) equals

pM − δ^{∗}(L) − 1 = p(m(1) + m(2) − 1) − δ^{∗}(L) − 1

and the normalized leading coefficient equals

∑_{S∈D_{p}^{∗}(L)} |skel(L_{p−1}^{o})| = ∑_{S∈D_{p}^{∗}(L)} ∑_{ℓ≥0} S(L_{p−1}^{o}, ℓ).

Proof. From (4.9), we see that F (V) is a sum of terms of the form

(−1)^{u}F_{u}(S)\binom{V + pM − δ(S) − 1 − u}{pM − δ(S) − 1 − u}

where the coefficients (−1)^{u}F_{u}(S) are independent of V. Clearly, the binomial coefficient above is a polynomial in V of degree pM − δ(S) − 1 − u, and this degree is maximum when u = 0 and δ(S) = δ^{∗}(L). The corresponding leading coefficient

\frac{1}{(pM − δ^{∗}(L) − 1)!} ∑_{S∈D_{p}^{∗}(L)} F_{0}(S) = ∑_{S∈D_{p}^{∗}(L)} ∑_{ℓ≥0} S(L_{p−1}^{o}, ℓ)

is clearly positive since D_{p}(L) is nonempty.

Theorem (5.2). Let t be an indeterminate over ℚ and let

P_{L}(t) = ∑_{S∈D_{p}^{∗}(L)} ℏ_{S}(t) t^{ν(S)}(1 − t)^{δ(S)−δ^{∗}(L)}, where ℏ_{S}(t) = ∑_{ℓ≥0} S(L_{p−1}^{o}, ℓ)t^{ℓ}.

Then the Hilbert series of I_{p+1}(L) is given by

\frac{P_{L}(t)}{(1 − t)^{pM−δ^{∗}(L)}} .

In particular P_{L}(t) gives the h-polynomial of I_{p+1}(L).

Proof. From the expression (12) in the proof of (4.9), we see that the Hilbert series is given by

∑_{V ≥0} ∑_{S∈D_{p}(L)} ∑_{ℓ≥0} \left[{V − ν(S) − ℓ \atop pM − δ(S) − 1}\right]S(L_{p−1}^{0}, ℓ)t^{V} . (13)

Given any S ∈ D_{p}(L) and ℓ ≥ 0, by (4.7) and (vi) and (vii) of (1.11), we have

\left[{V − ν(S) − ℓ \atop pM − δ(S) − 1}\right] = (−1)^{V −ν(S)−ℓ}\binom{δ(S) − pM}{V − ν(S) − ℓ}.

Thus, by interchanging summations and using (v) of (1.11), we can write (13) as

∑_{S∈D_{p}(L)} ∑_{ℓ≥0} S(L_{p−1}^{0}, ℓ) t^{ν(S)+ℓ} ∑_{V =ν(S)+ℓ}^{∞} \binom{δ(S) − pM}{V − ν(S) − ℓ}(−t)^{V −ν(S)−ℓ}

Therefore, by Binomial Theorem, we see that the Hilbert series is given by

∑_{S∈D_{p}(L)} \frac{ℏ_{S}(t) t^{ν(S)}}{(1 − t)^{pM−δ(S)}}

and in view of (5.1), this implies the desired result.

In general, it does not appear very easy to compute more explicitly the coefficients of the h-polynomial described above or for that matter, even the degree of the denominator. However, it is not difficult to get a simple upper bound for this degree. We shall make use of the following elementary observations concerning the boundary of a ladder.

Proposition (5.3). If S^{∗} ∈ lad(m) with len(S^{∗}) ≠ 0, then

|∂S^{∗}| = M = m(1) + m(2) − 1 (14)

and moreover, we can write ∂S^{∗} = {P_{1}, P_{2}, …, P_{M}} where

P_{1} = (1, m(2)), P_{M} = (m(1), 1), and

P_{j} − P_{j−1} = (1, 0) or (0, 1) for 1 < j ≤ M. (15)

Proof. Follows from (1.2).

Lemma (5.4). Given any S = (S_{1}, …, S_{p−1}) ∈ D_{p}(L), we have

δ_{i} = |∂S_{i} ∩ ∂S| ≥ min{δ_{0} + 2i, M}, for 1 ≤ i ≤ p − 1, (16)

and consequently, if t = max{i ∈ [1, p] : δ_{0} + 2(i − 1) ≤ M}, then

δ(S) = ∑_{i=0}^{p−1} δ_{i} ≥ tδ_{0} + t(t − 1) + (p − t)M. (17)

Further, if we assume that p < (M − δ_{0} + 1)/2, then we have

\begin{matrix}δ^{∗}(L) ≥ pδ_{0} + p(p − 1) and \\ dim V_{p+1}(L) ≤ p(m(1) + m(2) − p − δ_{0}) − 1. \end{matrix} (18)

Proof. We prove (16) by induction on i. The case of i = 0 being trivial, assume that i ≥ 1 and that δ_{i−1} ≥ min{δ_{0} + 2i − 2, M}. Now since ∂S_{i} ∩ ∂S_{i−1} = ∂S_{i−1} ∩ ∂S, we have ∂S_{i} ∩ ∂S ⊇ ∂S_{i−1} ∩ ∂S, and so δ_{i} ≥ δ_{i−1}. Thus in case δ_{i−1} ≥ M, we have δ_{i} ≥ M ≥ min{δ_{0} + 2i, M}. Suppose δ_{i−1} ≤ M − 1. Then, by (14), |∂S_{i} ∩∂S_{i−1}| ≤ |∂S_{i−1}|−1, and so we can write ∂S_{i} = {P_{1}, P_{2}, …, P_{M}} where P_{j}’s are as in (15), and further, we can find r ∈ [1, M] such that

P_{r} ∉ ∂S_{i−1} but P_{j} ∈ ∂S_{i−1} for 1 ≤ j < r. (19)

Also, let us write

∂S_{i−1} = {Q_{1}, Q_{2}, …, Q_{M}} and ∂S = {R_{1}, R_{2}, …, R_{M}}.

where Q_{j} and R_{j} satisfy the conditions in (15). Using (15) and (19), we see that P_{j} = Q_{j} for 1 ≤ j < r. Moreover, since ∂S_{i} ∩ ∂S_{i−1} = ∂S_{i−1} ∩ ∂S, we have P_{j} = R_{j} for 1 ≤ j < r. Now P_{r} ≠ Q_{r} and P_{r−1} = R_{r−1}, and thus in view of (15), we have that P_{r} ∉ ∂S_{i−1} and further, R_{r} = P_{r} or R_{r} = Q_{r}. But if R_{r} = Q_{r}, then Q_{r} ∈ ∂S_{i−1} ∩ ∂S ⊆ ∂S_{i}, and this forces that Q_{r} = P_{r}, which is a contradiction. Thus R_{r} = P_{r} and so

δ_{i} = |∂S_{i} ∩ ∂S| ≥ |∂S_{i−1} ∩ ∂S| + |{P_{r}}| = δ_{i−1} + 1.

In particular, if δ_{i−1} = M − 1, then δ_{i} ≥ M, and hence (16) holds. Now suppose δ_{i−1} < M − 1. Then we can also find some s ∈ [1, M] such that r < s < M and

P_{s} ∉ ∂S_{i−1} but P_{j} ∈ ∂S_{i−1} for s < j ≤ M.

Arguing as in the case of P_{r}, we obtain that P_{s} = R_{s}, and thus

δ_{i} = |∂S_{i} ∩ ∂S| ≥ |∂S_{i−1} ∩ ∂S| + |{P_{r}, P_{s}}| = δ_{i−1} + 2.

Hence, using the induction hypothesis, we obtain δ_{i} ≥ δ_{0} + 2i. This proves (16). Next, if t is as defined in the Lemma, then by (16), we have

δ(S) = ∑_{i=0}^{p−1} δ_{i} ≥ ∑_{i=0}^{t−1}(δ_{0} + 2i) + ∑_{i=t}^{p−1} M = tδ_{0} + t(t − 1) + (p − t)M.

Thus (17) is proved. To prove (18) consider the quadratic function

q(t) = tδ_{0} + t(t − 1) + (p − t)M.

Its derivative with respect to t equals 2(t − t_{0}), where t_{0} = (M − δ_{0} + 1)/2. Hence q(t) is strictly decreasing for t < t_{0}, and thus if p < t_{0}, then we have q(t) ≥ q(p) for all t ∈ [1, p]. This yields (18).

Remark (5.5). It may be noted that the condition p < (M − δ_{0} + 1)/2 in (5.4) is not restrictive. Indeed, the intersection ∂S′ ∩ ∂S of the boundaries of L(S) and L(S′) can be split into ‘horizontal overlaps’ and ‘vertical overlaps’ (see Fig. 2 (b)); if δ_{h} is the cardinality of the former and δ_{v} is the cardinality of the latter, then we have δ_{0} = |∂S′ ∩ ∂S| ≤ δ_{h} + δ_{v}. Moreover, in order that a (p + 1) × (p + 1) minor of X has its entries in L = L(S) \ L(S′), the columns should avoid the horizontal overlaps and the rows should avoid the vertical overlaps. Thus p+1 ≤ m(2)−δ_{h} and p+1 ≤ m(1)−δ_{v}. This implies that 2p < m(1)+m(2)−(δ_{h}+δ_{v}) ≤ m(1)+m(2)−δ_{0}, and so p < (M − δ_{0} + 1)/2. Corollary (5.6). Let L = L(S) be the ladder corresponding to S. Assume that p + 1 ≤ min{m(1), m(2)}. Then dim V_{p+1}(L) ≤ p(m(1) + m(2) − p) − 1.

Proof. Apply (5.4) with S′ as the empty ladder generating bisequence, and note that in this case δ_{0} = 0 and t = p.

Remark (5.7). The upper bound for dim V_{p+1}(L) in the Corollary above is, in fact, the dimension of the classical determinantal variety corresponding to the ideal I_{p+1}(X) generated by the (p + 1) × (p + 1) minors of X (see, e.g., [2, Thm. 20.15]). In this particular case of (one-sided) ladders, the same bound also follows from the expression for the Hilbert series in [20, Thm. 2]. However, this bound need not be attained, in general. For instance, in the Example considered in [20, p. 1022], the (projective) dimension is seen to be 103 whereas the value predicted by the above bound as well as by [20, Thm. 2] is 124. Notice that this shows that the numerator of the Hilbert series as it appears in [20, Thm. 2] does not give the true h-polynomial of I_{p+1}(L).

Finally in this section, we illustrate how in some cases the actual value of dim V_{p+1}(L) can be determined. Examples (5.8). 1. Suppose L is the full rectangle [1, m(1)] × [1, m(2)], which corresponds to the case when L(S′) is empty and S is the unique element of lad(m) of length 1; also suppose p < min{m(1), m(2)}. More generally, let L be a ladder L(S) (so that S′ is the empty ladder generating bisequence) where S ∈ lad(m) is of length h > 0 with S(1, 1) ≥ p and S(2, h − 1) ≥ p. In this case, by (17), we have

δ^{∗}(L) = min{δ(S) : S ∈ D_{p}(L)} ≥ p(p − 1).

Moreover, if we take S = (S_{1}, …, S_{p−1}), where S_{i}’s are the ‘hook-like’ ladder generating bisequences determined by the conditions

len(S_{i}) = 2 and (S_{i}(1, 1), S_{i}(2, 1)) = (i, i), for 1 ≤ i ≤ p − 1,

then it is easy to see that for 1 ≤ i ≤ p − 1, we have

∂S_{i}∩∂S_{i−1} = {(1, m(2)), …, (i−1, m(2)), (m(1), 1), …, (m(1), i−1)} = ∂S_{i−1}∩∂S, and therefore S ∈ D_{p}(L) and δ_{i} = |∂S_{i} ∩ ∂S| = 2i for 0 ≤ i ≤ p − 1; hence δ(S) = p(p − 1). It follows that δ^{∗}(L) = p(p − 1), and therefore,

dim V_{p+1}(L) = p(m(1) + m(2) − p) − 1.

2. Let L be a ladder with one corner missing, i.e, L(S′) is the empty and L = L(S), where S ∈ lad[m] is of length 2. Assume that p < min{m(1), m(2)}. Let (S(1, 1), S(2, 1)) = (a, b). Then we have

(20) δ^{∗}(L) = \{ \begin{matrix}p(p − 1) & if a ≥ p and b ≥ p \\ p(p − 1) + (p − a)(m(2) − b) & if a < p and b ≥ p \\ p(p − 1) + (p − b)(m(1) − a) & if a ≥ p and b < p \\ m(1)(p − b) + m(2)(p − a) + ab − p & if a < p and b < p \end{matrix}

and consequently,

(21) dim V_{p+1}(L) = \{ \begin{matrix}p(m(1) + m(2) − p) − 1 & if a ≥ p and b ≥ p \\ pM − 1 + (a − p)(m(2) − b) & if a < p and b ≥ p \\ pM − 1 + (b − p)(m(1) − a) & if a ≥ p and b < p \\ bm(1) + am(2) − ab & if a < p and b < p. \end{matrix}

To see this, note that when a ≥ p and b ≥ p, the result follows from the preceding example. In the remaining cases, we can argue as in the proof of (5.4) and the preceding example. Thus, for instance, if a < p and b ≥ p, then for any S ∈ D_{p}(L), we must have

δ_{i} ≥ 2i for 0 ≤ i < a and δ_{i} ≥ 2i + (m(2) − b) for a ≤ i ≤ p − 1.

Moreover, there exists a configuration S ∈ D_{p}(L) for which the above inequalities are equalities. Alternatively, we can directly prove (21) in the last three cases from the following simple observations. If a < p and b ≥ p, then V_{p+1}(L) is a cylinder over the determinantal variety V_{p+1}(Y), where Y is the m(1) × b rectangular submatrix of X obtained by taking the first b columns of X. The case when a ≥ p and b < p is similar. Lastly, when a < p and b < p, we have I_{p+1}(L) = (0). Remarks (5.8). 1. The observation about the dimension of dim V_{p+1}(L) in the first example above may perhaps explain why in Kulkarni’s formula for the Hilbert function of V_{2}(L), the degree is the same as that in the case of V_{2}(X). Indeed, when p = 1, the conditions S(1, 1) ≥ p and S(2, h − 1) ≥ p always hold.

2. In the case L is the full rectangle [1, m(1)] × [1, m(2)], Proposition (5.1) gives a curious formula for the multiplicity of the classical determinantal ideal I_{p+1}(X). It may be interesting to compare this with the more elegant formulae described in [17, p. 17].

References

[1] S. S. Abhyankar, Combinatoire des tableaux de Young, varietes determinantielles et calcul de fonctions de Hilbert, Rend. Sem. Mat. Univers. Politecn. Torino, 42 (1984), 65–88.

[2] S. S. Abhyankar, “Enumerative Combinatorics of Young Tableaux”, Marcel Dekker, New York, 1988.

[3] S. S. Abhyankar and D. M. Kulkarni, On hilbertian ideals, Linear Algebra Appl., 116 (1989), 53–79

[4] H. H. Andersen, Schubert varieties and Demazure’s character formula, Invent. Math., 79 (1985), 611–618.

[5] A. Conca and J. Herzog, On the Hilbert function of determinantal rings and their canonical module, Proc. Amer. Math. Soc., 122 (1994), 677–681.

[6] A. Conca, Ladder determinantal rings, J. Pure Appl. Algebra, 98 (1995), 119–134.

[7] A. Conca, Gorenstein ladder determinantal rings, J. London Math. Soc., 54 (1996), 453– 474.

[8] A. Conca and J. Herzog, Ladder determinantal rings have rational singularities, Adv. Math., 132 (1997), 120–147.

[9] E. De Negri, Pfaffian ideals of ladders, J. Pure Appl. Algebra, 125 (1998), 141–153.

[10] S. R. Ghorpade, Abhyankar’s work on Young tableaux and some recent developments, in “Algebraic Geometry and its Applications” (C. Bajaj, Ed.), pp. 235–265, Springer-Verlag, New York, 1994.

[11] S. R. Ghorpade, Young multitableaux and higher dimensional determinants, Adv. Math., 121 (1996), 167–195.

[12] S. R. Ghorpade, Young bitableaux, lattice paths and Hilbert functions, J. Statist. Plann. Inference, 54 (1996), 55–66.

[13] S. R. Ghorpade, On the enumeration of indexed monomials and the computation of Hilbert functions of ladder determinantal varieties, in “Formal Power Series and Algebraic Combinatorics, FPSAC’99” (C. Martinez, M. Noy and O. Serra, Eds.), pp. 225– 232, Universitat Politécnica de Catalunya, Barcelona, 1999. [Revised version available at:

http://www.math.iitb.ac.in/∼srg/Preprints.html]

[14] N. Gonciulea and V. Lakshmibai, Schubert varieties, toric varieties and ladder determinantal varieties, Ann. Inst. Fourier, 47 (1997), 1013–1064.

[15] N. Gonciulea and V. Lakshmibai, Singular loci of ladder determinantal varieties and Schubert varieties, J. Algebra, 229 (2000), 463–497.

[16] D. Glassbrenner and K. E. Smith, Singularities of certain ladder determinantal varieties, J. Pure Appl. Algebra, 101 (1995), 59–75.

[17] J. Herzog and N. V. Trung, Gröbner bases and multiplicity of determinantal and pfaffian ideals, Adv. Math., 96 (1992), 1–37.

[18] W. V. D. Hodge, Some enumerative results in the theory of forms, Proc. Camb. Phil. Soc., 39 (1943), 22–30.

[19] C. Huneke and V. Lakshmibai, On the normality of Schubert varieties, Proc. Indian Acad. Sci. 91 (1982), 65–71.

[20] C. Krattenthaler and M. Prohaska, A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns, Trans. Amer. Math. Soc., 351 (1999), 1015–1042.

[21] D. M. Kulkarni, Semigroup of ordinary multiple point, analysis of straightening formula and counting monomials, Ph.D. Thesis, Purdue Univ., West Lafayette, USA, 1985.

[22] D. M. Kulkarni, Hilbert polynomial of a certain ladder determinantal ideal, J. Algebraic Combin., 2 (1993), 57–71.

[23] V. B. Mehta and V. Srinivas, Normality of Schubert varieties, Amer. J. Math., 109 (1987), 987–989.

[24] V. B. Mehta and V. Srinivas, A note on Schubert varieties in G/B, Math. Ann., 284 (1989), 1–5.

[25] J. Motwani and M. Sohoni, Normality of ladder determinantal rings, J. Algebra, 186 (1996), 323–337.

[26] J. Motwani and M. Sohoni, Divisor class group of ladder determinantal varieties, J. Algebra, 186 (1996), 338–367.

[27] S. B. Mulay, Determinantal loci and the flag variety, Adv. Math., 74 (1989), 1–30.

[28] C. Musili, Applications of standard monomial theory, in “Proceedings of the Hyderabad Conference on Algebraic Groups”, (S. Ramanan, Ed.), pp. 381–406, Manoj Prakashan, Madras (Distributed outside India by the American Math. Society, Providence), 1991.

[29] H. Narasimhan, Irreducibility of ladder determinantal varieties, J. Algebra, 102 (1986), 162–185.

[30] S. Ramanan and A. Ramanathan, Projective normality of flag varieties and Schubert varieties, Invent. Math., 79 (1985), 217–224.

[31] A. Ramanathan, Schubert varieties are arithmetically Cohen-Macaulay, Invent. Math., 80 (1985), 283–294.

[32] C. S. Seshadri, Line bundles on Schubert varieties, in “Vector Bundles on Algebraic Varieties” (Papers presented at the Bombay Colloquium, 1984), pp. 495–528, Oxford Univ. Press, Bombay, 1987.

[33] X. G. Viennot, Une forme géometrique de la correspondence de Robinson-Schensted, in “Combinatoire et Représentation du Groupe Symétrique” (D. Foata, Ed.), pp. 29–58, Lecture Notes in Math., Vol. 579, Springer-Verlag, New York, 1977.

Department of Mathematics Indian Institute of Technology, Bombay Powai, Mumbai 400076, India

E-mail address: srg@math.iitb.ac.in