COMPUTATION OF THE a-INVARIANT OF LADDER DETERMINANTAL RINGS

Sudhir R. Ghorpade^{∗} and Christian Krattenthaler^{†}

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

                       URL: http://www.math.iitb.ac.in/~srg/

Fakultät für Mathematik, Universität Wien Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria.

                      URL: http://www.mat.univie.ac.at/~kratt

Abstract. We solve the problem of effectively computing the a-invariant of ladder determinantal rings. In the case of a one-sided ladder, we provide a compact formula, while, for a large family of two-sided ladders, we provide an algorithmic solution.

1. Introduction

Ladder determinantal rings are rings of polynomials in variables X_{i,j}, 0 ≤ i ≤ A, 0 ≤ j ≤ B, modulo ideals generated by certain minors formed from these variables (see Section 2 for the precise definition). Ladder determinantal rings arose originally in the study of singularities of Schubert varieties of flag manifolds by Abhyankar [1]. His work showed that ladder determinantal rings are a natural generalization of determinantal rings corresponding to classical determinantal ideals, and that they possess several nice properties; for example, these rings are integral domains and are rational in the sense that the quotient field is a purely transcendental extension of the ground field. See also Narasimhan [17] for the former result. Ladder determinantal rings were further studied by Herzog and Trung [12] who proved that these rings are Cohen–Macaulay, using an explicit determination of the Gröbner basis of the corresponding ladder determinantal ideal, and then showing that the simplicial complex associated to its initial ideal is shellable. Abhyankar and Kulkarni [2] have shown that the Hilbert function of ladder determinantal rings coincides with the Hilbert polynomial at all nonnegative integers. For more work on ladder determinantal rings, see [4, 6, 7, 9, 13, 14, 15, 16, 20].

2010 Mathematics Subject Classification. Primary 05A15, 13C40; Secondary 05A19, 13F50, 13H10.

Key words and phrases. a-invariant, ladder determinantal ring, Hilbert series, lattice path.

∗ Research partially supported by the Indo-Russian project INT/RFBR/P-114 from the Department of Science & Technology, Govt. of India and the IRCC Award grant 12IRAWD009 from IIT Bombay.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S50-N15, the latter in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics”.

The purpose of the present paper is to provide methods for computing the so-called ainvariant of ladder determinantal rings. The a-invariant a(R) is an important quantity associated with a standard graded Cohen–Macaulay algebra R over a field. It was introduced by Goto and Watanabe [10] as the negative of the least degree of a generator of the graded canonical module of R. See [5, p. 48] for a summary of its various implications. In particular, it is argued there that it follows from work of Stanley [19] that a(R) = s − d, given that the Hilbert series of R has the form H(t)/(1 − t)^{d}, where H(t) ∈ ℤ[t] with H(1) ≠ 0 and d is the Krull dimension of R, while s is the degree of H(t). It is a classical result of Gräbe [11] that, if X = (X_{i,j}) is an (A+1)×(B+1)matrix of variables, and R the quotient of the corresponding polynomial ring by the ideal generated by all (n+1)×(n+1) minors of X, then a(R) = − max{A+1, B +1}n. This result has been extended to weighted determinantal ideals and Pfaffian ideals by Bruns and Herzog [3] and to ideals cogenerated by a minor (and thus generated by minors of different sizes) of a rectangular matrix by Conca [5] (see also [8, Theorem 4]). The most general result appears to be that of Conca [5] on determinantal rings (without ladder restriction). The case of ladder determinantal rings appears to have been open and we take it up in this paper.

Our first main result, consisting of Theorem 7 and Corollary 9, provides a formula for the a-invariant of one-sided ladder determinantal rings. It does not reduce to Conca’s formula in the special case where there is no ladder restriction. Even in that case, our formula is simpler, as is the proof of our formula. To explain the difference: our proof follows Conca’s in its first step, consisting of a reduction of the problem to a problem of finding the largest set of integer points in the plane satisfying certain properties (here, this is hidden in the proof of Theorem 1; see [18, Theorem 3.1]), but differs fundamentally from there on. While we translate these point sets into families of non-intersecting lattice paths (see Theorem 1), Conca uses a version of the Robinson–Schensted–Knuth correspondence in order to translate the point sets into pairs of semistandard tableaux. As a matter of fact, the required analysis of the families of non-intersecting lattice paths is much simpler than the corresponding analysis of the pairs of tableaux. Moreover, the tableau approach does not work in the presence of the ladder restriction.

Our second main result, consisting of Theorem 16 and Corollary 17, provides an algorithm for computing the a-invariant for a large family of two-sided ladder determinantal rings. The idea behind this algorithm stems from our result for the one-sided ladder case in Theorem 7.

The next section gives all necessary definitions and provides relevant background. In particular, it explains how the computation of the a-invariant of ladder determinantal rings can be transformed into the problem of counting non-intersecting lattice paths in ladder-shaped regions with a maximal total number of NE-turns, see Theorem 1. In Section 3 we then solve the latter problem for one-sided ladder regions. The resulting formula for the a-invariant of one-sided ladder determinantal rings is presented in Section 4. The purpose of Section 5 is to solve the problem of counting non-intersecting lattice paths with a maximal total number of NE-turns in two-sided ladder regions. The corresponding result for the a-invariant of two-sided ladder determinantal rings, which assumes a mild restriction on the involved ladder region, is presented in Section 6.

2. Preliminaries

We start by recalling the definition of a ladder determinantal ring. Let K be a field and X = (X_{i,j})_{0≤i≤A, 0≤j≤B} be an (A+1)×(B+1) matrix whose entries are independent indeterminates over K. Let Y = (Y_{i,j})_{0≤i≤A, 0≤j≤B} be another (A + 1) × (B + 1) matrix with the property that Y_{i,j} = X_{i,j} or 0, and if Y_{i,j} = X_{i,j} and Y_{i′j′} = X_{i′j′}, where i ≤ i′ and j ≤ j′, then Y_{s,t} = X_{s,t} for all s, t with i ≤ s ≤ i′ and j ≤ t ≤ j′. An example of such a matrix Y, with A = 15 and B = 13, is displayed in Figure 1. Such a “submatrix” Y of X is called a ladder. This terminology is motivated by the identification of such a matrix Y with the set of all points (j, A − i) in the plane for which Y_{i,j} = X_{i,j}. For example, the set of all such points for the special matrix in Figure 1 is shown in Figure 2. (It should be apparent from comparison of Figures 1 and 2 that the reason for taking (j, A − i) instead of (i, j) is to take care of the difference in “orientation” of row and column indexing of a matrix versus coordinates in the plane.) In general, this set of points looks like a (two-sided) ladder-shaped region. If, on the other hand, we have either Y_{0,0} = X_{0,0} or Y_{a,b} = X_{a,b} then we call Y a one-sided ladder. In the first case we call Y a lower ladder, in the second an upper ladder. Thus, the matrix in Figure 3 is an upper ladder region (i.e., corresponds to a matrix Y which is an upper ladder).

( X_{15,0} X_{15,1} X_{15,2} X_{15,3} X_{15,4} X_{15,5} X_{15,6} X_{15,7} X_{15,8} 0 0 0 0 0 X_{14,0} X_{14,1} X_{14,2} X_{14,3} X_{14,4} X_{14,5} X_{14,6} X_{14,7} X_{14,8} 0 0 0 0 0 X_{13,0} X_{13,1} X_{13,2} X_{13,3} X_{13,4} X_{13,5} X_{13,6} X_{13,7} X_{13,8} X_{13,9} X_{13,10} 0 0 0 X_{12,0} X_{12,1} X_{12,2} X_{12,3} X_{12,4} X_{12,5} X_{12,6} X_{12,7} X_{12,8} X_{12,9} X_{12,10} 0 0 0 X_{11,0} X_{11,1} X_{11,2} X_{11,3} X_{11,4} X_{11,5} X_{11,6} X_{11,7} X_{11,8} X_{11,9} X_{11,10}X_{11,11} 0 0 X_{10,0} X_{10,1} X_{10,2} X_{10,3} X_{10,4} X_{10,5} X_{10,6} X_{10,7} X_{10,8} X_{10,9} X_{10,10}X_{10,11}X_{10,12} 0 X_{9,0} X_{9,1} X_{9,2} X_{9,3} X_{9,4} X_{9,5} X_{9,6} X_{9,7} X_{9,8} X_{9,9} X_{9,10} X_{9,11} X_{9,12} X_{9,13} 0 0 0 0 X_{8,4} X_{8,5} X_{8,6} X_{8,7} X_{8,8} X_{8,9} X_{8,10} X_{8,11} X_{8,12} X_{8,13} 0 0 0 0 X_{7,4} X_{7,5} X_{7,6} X_{7,7} X_{7,8} X_{7,9} X_{7,10} X_{7,11} X_{7,12} X_{7,13} 0 0 0 0 X_{6,4} X_{6,5} X_{6,6} X_{6,7} X_{6,8} X_{6,9} X_{6,10} X_{6,11} X_{6,12} X_{6,13} 0 0 0 0 0 X_{5,5} X_{5,6} X_{5,7} X_{5,8} X_{5,9} X_{5,10} X_{5,11} X_{5,12} X_{5,13} 0 0 0 0 0 0 X_{4,6} X_{4,7} X_{4,8} X_{4,9} X_{4,10} X_{4,11} X_{4,12} X_{4,13} 0 0 0 0 0 0 0 X_{3,7} X_{3,8} X_{3,9} X_{3,10} X_{3,11} X_{3,12} X_{3,13} 0 0 0 0 0 0 0 0 X_{2,8} X_{2,9} X_{2,10} X_{2,11} X_{2,12} X_{2,13} 0 0 0 0 0 0 0 0 X_{1,8} X_{1,9} X_{1,10} X_{1,11} X_{1,12} X_{1,13} 0 0 0 0 0 0 0 0 X_{0,8} X_{0,9} X_{0,10} X_{0,11} X_{0,12} X_{0,13} )

Figure 1. A two-sided ladder

Now fix a “bivector” M = [u_{1}, u_{2}, …, u_{n} | v_{1}, v_{2}, …, v_{n}] of positive integers with u_{1} < u_{2} < ⋯ < u_{n} ≤ A + 1 and v_{1} < v_{2} < ⋯ < v_{n} ≤ B + 1. Let K[Y] denote the ring

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8} _{9} _{10} _{11} _{12} _{13}^{1}^{2}^{3}^{4}^{5}^{6}^{7}^{8}^{9}^{10}^{11}^{12}^{13}^{14}^{15}

Figure 2. A two-sided ladder region

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8} _{9} _{10} _{11} _{12} _{13}^{1}^{2}^{3}^{4}^{5}^{6}^{7}^{8}^{9}^{10}^{11}^{12}^{13}^{14}^{15}

Figure 3. An upper ladder region

of all polynomials over the field K in the Y_{i,j}’s, 0 ≤ i ≤ A, 0 ≤ j ≤ B, and let I_{M}(Y) be the ideal of K[Y] generated by those t×t minors of Y that contain only nonzero entries, whose rows form a subset of the last u_{t} − 1 rows, or whose columns form a subset of the last v_{t} − 1 columns, t = 1, 2, …, n + 1. Here, by convention, u_{n+1} is set equal to A + 2, and v_{n+1} is set equal to B + 2. (Thus, for t = n + 1 the rows and columns of minors are unrestricted.) The ideal I_{M}(Y) is called a ladder determinantal ideal cogenerated by the minor M. (That one speaks of ‘the minor M’ has its explanation in the identification of the bivector M with a particular minor of Y, cf. [12, Sec. 2]. It should be pointed out that our conventions here deviate slightly from the ones in [12]. In particular, we defined the ideal I_{M}(Y) by restricting rows and columns of minors to a certain number of last rows or columns, while in [12] it is first rows, respectively columns. Clearly, a rotation of the matrix by 180^{∘} transforms one convention into the other.) The associated ladder determinantal ring cogenerated by M is R_{M}(Y) := K[Y]/I_{M}(Y). (We point out that the definition of ladder is more general in [1, 2, 4, 12]. However, there is in effect no loss of generality since the ladders of [1, 2, 4, 12] can always be reduced to our definition by discarding superfluous 0’s.)

Generalising results of Abhyankar and Kulkarni [1, 2], Herzog and Trung [12] provided a way to express the Hilbert series of the ladder determinantal ring R_{M}(Y) in combinatorial terms. Before we can state the corresponding result, as derived by Rubey [18], we need to introduce a few more terms.

When we say lattice path we always mean a lattice path in the plane consisting of unit horizontal and vertical steps in the positive direction. In other words, a lattice path is a finite sequence A_{0}, A_{1}, …, A_{m} of points in ℤ^{2} such that A_{i} − A_{i−1} = (1, 0) or (0, 1) for all i = 1, …, m. Such a sequence is sometimes called a lattice path from A_{0} to A_{m}. In case the successive differences A_{i} − A_{i−1} always alternate between (1, 0) and (0, 1), then we refer to it as a zig-zag path. See Figure 4 for an illustration of a lattice path from (1, −1) to (6, 6). This is not a zig-zag path, but its part from (4, 3) to (6, 5) is.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} •  •

Figure 4. A lattice path

A family (P_{1}, P_{2}, …, P_{n}) of lattice paths P_{i}, i = 1, 2, …, n, is said to be non-intersecting if no two lattice paths of this family have a point in common.

A point in a lattice path P which is the end point of a vertical step and at the same time the starting point of a horizontal step will be called a north-east turn (NE-turn for short) of the lattice path P. The NE-turns of the lattice path in Figure 4 are (1, 1), (2, 3), and (5, 4). We write NE(P) for the number of NE-turns of P. Also, given a family P = (P_{1}, P_{2}, …, P_{n}) of paths P_{i}, we write NE(P) for the number ∑_{i=1}^{n} NE(P_{i}) of all NE-turns in the family.

We shall say that a lattice path P stays (or passes) weakly south-east of a lattice point S = (s_{1}, s_{2}) if each point (x, y) of P satisfies either x ≥ s_{1} (“the point (x, y) lies weakly east of S”) or y ≤ s_{2} (“the point (x, y) lies weakly south of S”), or both. Sometimes, this may be expressed by saying that the point S lies weakly north-west of P. To stay (or pass) weakly north-east of a lattice point and to stay (or pass) weakly north-west of a lattice point will have an analogous meaning.

Finally, given any weight function w defined on a finite set M and taking values in a commutative ring, by the generating function GF(M; w) we mean ∑_{x∈M} w(x).

We are now in the position to state the theorem which connects the computation of the Hilbert series of a ladder determinantal ring with the enumeration of (certain) non-intersecting lattice paths. For a proof, the reader is referred to [18, Theorem 3.1].

Theorem 1. Let Y = (Y_{i,j})_{0≤i≤A, 0≤j≤B} be a two-sided ladder, and let L be the associated ladder region. Let M = [u_{1}, u_{2}, …, u_{n} | v_{1}, v_{2}, …, v_{n}] be a bivector of positive integers with u_{1} < u_{2} < ⋯ < u_{n} and v_{1} < v_{2} < ⋯ < v_{n}. Furthermore, let A^{(i)} = (0, u_{n−i+1} − 1) and E^{(i)} = (B − v_{n−i+1} + 1, A), i = 1, 2, …, n. Recursively, define the regions L^{(i)}, i = n, n − 1, …, 1, by L^{(n)} = L and

L^{(i)} = {(x, y) ∈ L^{(i+1)} : x ≤ E_{1}^{(i)}, y ≥ A_{2}^{(i)}, and (x + 1, y − 1) ∈ L^{(i+1)}}.

Finally, for i = 1, 2, …, n let

B^{(i)} = {(x, y) ∈ L^{(i)} : (x + 1, y − 1) ∉ L^{(i)}},

and let d be the cardinality of ⋃_{i=1}^{n} B^{(i)}.

Then, under the assumption that all of the points A^{(i)} and E^{(i)}, i = 1, 2, …, n, lie inside the ladder region L, the Hilbert series of the ladder determinantal ring R_{M}(Y) = K[Y]/I_{M}(Y) equals

∑_{ℓ=0}^{∞} dim_{K} R_{M}(Y)_{ℓ} z^{ℓ} = \frac{GF(P_{L}^{+}(A → E); z^{NE(.)})}{(1 − z)^{d}},  (2.1)

where R_{M}(Y)_{ℓ} denotes the homogeneous component of degree ℓ in R_{M}(Y), and where GF(P_{L}^{+}(A → E); z^{NE(.)}) denotes the generating function ∑_{P} z^{NE(P)} for all families P = (P_{1}, P_{2}, …, P_{n}) of non-intersecting lattice paths, P_{i} running from A^{(i)} to E^{(i)} with all its NE-turns lying in L^{(i)}\B^{(i)}.

Remarks 2. (1) The condition that all of the points A^{(i)} and E^{(i)} lie inside the ladder region L restricts the choice of ladders. In particular, for an upper ladder it means that Y_{A−u_{n}+1,0} = X_{A−u_{n}+1,0} and Y_{0,B−v_{n}+1} = X_{0,B−v_{n}+1}. Still, one could prove an analogous result even if this condition is dropped. In that case, however, the points A^{(i)} and E^{(i)} have to be modified in order to lie inside L so as to make the right-hand side of Formula (2.1) meaningful.

(2) The sets B^{(i)}, i = 1, 2, …, n, can be visualized as being the lower-right boundary of L^{(i)}. Viewed as a path, there are exactly E_{1}^{(i)} − A_{1}^{(i)} + E_{2}^{(i)} − A_{2}^{(i)} + 1 lattice points on B^{(i)}, but not all of them are necessarily in L (see [18, Figures 2 and 3] for an example). However, if they are, then

d = ∑_{i=1}^{n} (E_{1}^{(i)} − A_{1}^{(i)} + E_{2}^{(i)} − A_{2}^{(i)} + 1)

= ∑_{i=1}^{n} ((B − v_{n−i+1} + 1) + A − (u_{n−i+1} − 1) + 1)

= (A + B + 3)n − ∑_{i=1}^{n}(u_{i} + v_{i}).

(3) In the case of a one-sided ladder, all the B^{(i)}’s are completely contained in L so that the above remark on d applies. Furthermore, if the one-sided ladder should be an upper ladder, then it is easy to see that the technical condition in Theorem 1 involving the L^{(i)}’s and B^{(i)}’s reduces to the much simpler (and much more intuitive) condition that all the P_{i}’s should completely lie in L.

(4) It should be observed that the condition imposed on the paths P_{i} that all of its NE-turns lie in L^{(i)} (and, thus, in L) does not imply that P_{i} lies completely in L (namely, it may run below the lower boundary of L); see [18, Figure 4] for an example.

If we combine the formula for the Hilbert series of R_{M}(Y) in Theorem 1 with the observation made in the introduction on how to extract the a-invariant out of such a formula, then we obtain immediately the following corollary.

Corollary 3. Under the assumptions and the notation of Theorem 1, the a-invariant of the ladder determinantal ring R_{M}(Y) = K[Y]/I_{M}(Y) is given by

deg (GF(P_{L}^{+}(A → E); z^{NE(.)})) − d.

Hence, if we want to express the a-invariant of R_{M}(Y) in terms of M and the ladder Y, then we must determine the degree of the polynomial GF(P_{L}^{+}(A → E); z^{NE(.)}). This amounts to determining the maximum number of NE-turns a family of non-intersecting lattice paths as described in Theorem 1 can attain. This is what we shall do in the following sections.

3. How to achieve the maximum number of NE-turns: the one-sided case

We start with the consideration of upper ladders, see Figure 3 for an example. By Remark 2.(3), in that case we do not have to worry about the technical condition involving the L^{(i)}’s and the B^{(i)}’s as long as we make sure that all the paths P^{(i)} lie completely in L.

We begin with the task of maximising the number of NE-turns of a single path in an upper ladder. In this and the following section, we formulate the ladder restriction as the restriction that paths should stay south-east of some given lattice points. Clearly, the restriction imposed by an upper ladder can be formulated in that way: one chooses the points S_{1}, S_{2}, … in Lemmas 4 and 6 as the “inwards” corners of the upper boundary of L, that is, the elements (x, y) ∈ L for which both (x − 1, y) and (x, y + 1) are in L but (x − 1, y + 1) is not. For example, the inwards corners of the ladder region in Figure 3 are (4, 6), (8, 9), and (10, 13).

Lemma 4. Let A = (a, b), B = (c, d), and S_{i} = (x_{i}, y_{i}) be lattice points with a ≤ x_{i} ≤ c and b ≤ y_{i} ≤ d, for i = 1, 2, …, m. The number of NE-turns of a lattice path from A to B which stays weakly south-east of S_{i}, for i = 1, 2, …, m, is at most

min{c − a, d − b, c − b − max{x_{i} − y_{i} : 1 ≤ i ≤ m}}.  (3.1)

The maximum is for instance realised by the path which consists of a zig-zag path which passes through one of the points S_{j} for which x_{j} − y_{j} equals max{x_{i} − y_{i} : 1 ≤ i ≤ m}, supplemented by a straight horizontal piece at the beginning and a straight vertical piece at the end, as is necessary to connect A with B; cf. Figure 6.

Remark 5. The expression in (3.1) could be further economised to

c − b − max{x_{i} − y_{i} : 0 ≤ i ≤ m + 1},

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} •  • ∘ ∘ ∘ ∘ ∘^{A}  ^{B}

Figure 5. A lattice path with maximal number of NE-turns

by including (a, b) and (c, d) in the restriction points S_{i}, that is, by setting S_{0} = (a, b) and S_{m+1} = (c, d).

Proof of Lemma 4. We discuss the case where d − b ≤ c − a, the other case being completely analogous. If m = 0, that is, if the set of points S_{j} is empty, then the path which starts with a straight horizontal piece from A to (b + c − d, b) and then continues with a zig-zag path until B (starting with an up-step and terminating with a right-step; see the example in Figure 5, where a = 0, b = 1, c = 7, and d = 6) attains the maximal possible number of NE-turns for paths between A and B, namely d − b.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} •  • •  • • • ∘ ∘ ∘^{A}  ^{B}^{S_{1}}  ^{S_{2}}^{S_{3}} ^{S_{4}}

Figure 6. A lattice path with maximal number of NE-turns south-east of the S_{i}’s

Now let m ≥ 1. Clearly, as long as all points S_{j} lie weakly north-west of the path constructed above (and exemplified in Figure 5), the maximal possible number of NEturns will still equal d − b. This is well in accordance with (3.1). In symbols, this case is characterised by the property that x_{j} − y_{j} ≤ c − d for all j.

On the other hand, let S_{j} be a point for which x_{j} −y_{j} equals max{x_{i}−y_{i} : 1 ≤ i ≤ m} and x_{j} − y_{j} > c − d. It is then obvious (see also the example in Figure 6, where m = 4, A = (0, 1), B = (7, 6), S_{1} = (3, 2), S_{2} = (6, 3), S_{3} = (6, 5), S_{4} = (7, 5)) that any path between A and S_{j} cannot have more than y_{j} −b NE-turns, of which one possible path is the one which starts with a straight horizontal piece between A and (b + x_{j} − y_{j}, b), and then continues with a zig-zag path until S_{j} (beginning with an up-step and terminating with a right-step); see again Figure 6, with j = 2. Similarly, any path between S_{j} and B cannot have more than c − x_{j} NE-turns, of which one possible path is the one which starts with a zig-zag path between S_{j} and (c, c − x_{j} + y_{j}) (beginning with an up-step and terminating with a right-step), and then continues with a straight vertical piece between (c, c − x_{j} + y_{j}) and B; Figure 6 provides again an illustration. It is also clear that all other S_{i}’s will lie weakly north-west of these path portions. If we add the number of these NE-turns, then we obtain

(y_{j} − b) + (c − x_{j}) = c − b − x_{j} + y_{j}.

This agrees indeed with (3.1). □

We move on to the case of families of non-intersecting lattice paths. The next lemma tells us the restriction that an upper ladder imposes on the i-th path in a family of nonintersecting lattice paths, allowing us to break the problem of finding the maximum total number of NE-turns in families of non-intersecting lattice paths down to independent maximisation problems for single paths (with the solution to the latter problem being provided for by Lemma 4).

Lemma 6. Let A^{(i)} = (0, a_{i}), E^{(i)} = (B − b_{i}, A), i = 1, 2, …, n, and S_{i} = (x_{i}, y_{i}), i = 1, 2, …, m, be lattice points in the plane with a_{1} > a_{2} > ⋯ > a_{n} and b_{1} > b_{2} > ⋯ > b_{n}, 0 ≤ x_{i} ≤ B−b_{n} and a_{n} ≤ y_{i} ≤ A. Then, in any family (P_{1}, P_{2}, …, P_{n}) of nonintersecting lattice paths, where P_{i} runs from A^{(i)} to E^{(i)} and stays weakly south-east of S_{k}, for k = 1, 2, …, m, the path P_{i} has to stay weakly south-east of all points

{(i − j, a_{j} − i + j) : j = 1, 2, …, i} ∪ {(B − b_{j} + i − j, A − i + j) : j = 1, 2, …, i} ∪ {S_{k} + (i − 1, −i + 1) : k = 1, 2, …, m} (3.2)

Proof. Since the paths P_{1}, P_{2}, …, P_{n} are non-intersecting, the paths P_{j+1}, P_{j+2}, …, P_{i−1} must stay between P_{j} and P_{i}, for all j < i. The point A_{j} = (0, a_{j}) belongs to the path P_{j}, whereas the path P_{j+1} must stay strictly south-east of P_{j}. In particular, it must stay weakly south-east of (1, a_{j} − 1). The same argument is repeated with P_{j+1} and P_{j+2}, etc. The claimed conclusion then follows without difficulty. □

4. The main theorem for one-sided ladder regions

We now apply the findings of the previous section to obtain our first main result.

Theorem 7. Let A^{(i)} = (0, a_{i}), E^{(i)} = (B − b_{i}, A), i = 1, 2, …, n, and S_{i} = (x_{i}, y_{i}), i = 1, 2, …, m, be lattice points in the plane with a_{1} > a_{2} > ⋯ > a_{n} and b_{1} > b_{2} > ⋯ > b_{n}, 0 ≤ x_{i} ≤ B − b_{n} and a_{n} ≤ y_{i} ≤ A. The maximum number of NE-turns which a family (P_{1}, P_{2}, …, P_{n}) of non-intersecting lattice paths, where P_{i} runs from A^{(i)} to E^{(i)} and stays weakly south-east of S_{k}, for k = 1, 2, …, m, can attain is

∑_{i=1}^{n} t_{i},

where

t_{i} = B − a_{i} − b_{i} − max ({−a_{j} + 2(i − j), B − A − b_{j} + 2(i − j) : 1 ≤ j ≤ i}

∪ {x_{k} − y_{k} + 2(i − 1) : 1 ≤ k ≤ m}).

Proof. This follows immediately if Lemma 6 is combined with Lemma 4 (with a = 0, b = a_{i}, c = B − b_{i}, d = A, and the points S_{i} being the points in (3.2)), by also taking Remark 5 into account. □

Example 8. In order to illustrate Theorem 7, we choose A = 15, B = 13, n = 3, a_{1} = 5, a_{2} = 4, a_{3} = 2, b_{1} = 3, b_{2} = 1, b_{3} = 0 (so that A^{(1)} = (0, 5), A^{(2)} = (0, 4), A^{(3)} = (0, 2), B^{(1)} = (10, 15), B^{(2)} = (12, 15), B^{(3)} = (13, 15)), S_{1} = (4, 6), S_{2} = (8, 9), and S_{3} = (10, 13).

∘ ∘ ∘  ∘ ∘ ∘_{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•}_{0}  _{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8} _{9} _{10} _{11} _{12} _{13}^{1}^{2}^{3}^{4}^{5}^{6}^{7}^{8}^{9}^{10}^{11}^{12}^{13}^{14}^{15} ^{A^{(1)}}^{A^{(2)}}^{A^{(3)}}  ^{E^{(1)}} ^{E^{(2)}}^{E^{(3)}} Figure 7

According to Theorem 7, we have

t_{1} = 13 − 5 − 3 − max ({−5, 13 − 15 − 3} ∪ {4 − 6, 8 − 9, 10 − 13}) = 6,
t_{2} = 13 − 4 − 1 − max ({−5 + 2, 13 − 15 − 3 + 2, −4, 13 − 15 − 1}
∪ {4 − 6 + 2, 8 − 9 + 2, 10 − 13 + 2}) = 7,
t_{3} = 13 − 2 − 0 − max ({−5 + 4, 13 − 15 − 3 + 4, −4 + 2, 13 − 15 − 1 + 2,

− 2, 13 − 15 − 0} ∪ {4 − 6 + 4, 8 − 9 + 4, 10 − 13 + 4}) = 8.

Thus, the maximum number of NE-turns a family (P_{1}, P_{2}, P_{3}) of non-intersecting lattice paths, where P_{i} runs from A^{(i)} to E^{(i)}, i = 1, 2, 3, can have is 6 + 7 + 8 = 21, with the individual paths having at most 6, 7, 8 NE-turns, respectively. An example of such a family is shown in Figure 7.

In view of Remark 2.(2), Corollary 3 and Theorem 7, after little simplification, we obtain the following formula for the a-invariant of one-sided ladder determinantal rings.

Corollary 9. Let Y = (Y_{i,j})_{0≤i≤A, 0≤j≤B} be an upper ladder, and let L be the associated ladder region. Let M = [u_{1}, u_{2}, …, u_{n} | v_{1}, v_{2}, …, v_{n}] be a bivector of positive integers with u_{1} < u_{2} < ⋯ < u_{n} and v_{1} < v_{2} < ⋯ < v_{n}. Then the a-invariant of the ladder determinantal ring R_{M}(Y) = K[Y]/I_{M}(Y) is given by

∑_{i=1}^{n} t_{i} − (A + B + 1)n,

where

t_{i} = min ({B + u_{n−j+1} − 1 − 2(i − j), A + v_{n−j+1} − 1 − 2(i − j) : 1 ≤ j ≤ i}

∪ {B − x_{k} + y_{k} − 2(i − 1) : 1 ≤ k ≤ m}),

where S_{k} = (x_{k}, y_{k}), k = 1, 2, …, m, runs through the inwards corners of the upper ladder L.

Example 10. Let A = 15, B = 13, n = 3, L the ladder region indicated by the dots in Figure 7, and M = [3, 5, 6 | 1, 2, 4]. (The reader should observe that L is also the ladder region in Figure 3.) The ladder can be “described” by the inwards corners S_{1} = (4, 6), S_{2} = (8, 9), and S_{3} = (10, 13). (The reader should observe that the above choice of parameters leads to the maximisation problem of Example 8.) We have

t_{1} = min ({13 + 6 − 1, 15 + 4 − 1}
∪ {13 − 4 + 6, 13 − 8 + 9, 13 − 10 + 13}) = 14,
t_{2} = min ({13 + 6 − 1 − 2, 15 + 4 − 1 − 2, 13 + 5 − 1, 15 + 2 − 1 − 2}

∪ {13 − 4 + 6 − 2, 13 − 8 + 9 − 2, 13 − 10 + 13 − 2}) = 12,

t_{3} = min ({13 + 6 − 1 − 4, 15 + 4 − 1 − 4, 13 + 5 − 1 − 2, 15 + 2 − 1 − 2,

13 + 3 − 1, 15 + 1 − 1} ∪ {13 − 4 + 6 − 4, 13 − 8 + 9 − 4, 13 − 10 + 13 − 4})

= 10.

Hence, the a-invariant of the corresponding ladder determinantal ring R_{M}(Y) equals

(14 + 12 + 10) − (15 + 13 + 1) · 3 = −51.

For the sake of comparison with Conca’s formula [5] for the a-invariant of determinantal rings cogenerated by a given minor (without ladder restriction), we provide the specialisation of our result to that case separately.

Corollary 11. Let M = [u_{1}, u_{2}, …, u_{n} | v_{1}, v_{2}, …, v_{n}] be a bivector of positive integers with u_{1} < u_{2} < ⋯ < u_{n} and v_{1} < v_{2} < ⋯ < v_{n}. Then the a-invariant of the determinantal ring R_{M}(X) = K[X]/I_{M}(X) is given by

∑_{i=1}^{n} t_{i} − (A + B + 1)n,

where

t_{i} = min{B + u_{n−j+1} − 1 − 2(i − j), A + v_{n−j+1} − 1 − 2(i − j) : 1 ≤ j ≤ i}.

Example 12. We let B ≤ A and choose M = [1, 2, …, n | 1, 2, …, n]. (For comparison, see [4, Ex. 2.8].) Then we obtain

t_{i} = min{B + n − 2i + j, A + n − 2i + j : 1 ≤ j ≤ i}
= B + n − 2i + 1.

Hence, the a-invariant of R_{M}(X) equals

∑_{i=1}^{n}(B + n − 2i + 1) − (A + B + 1)n = Bn − (A + B + 1)n = −(A + 1)n,

which is in accordance with [11] and [3, Cor. 1.5 with f_{i} = 0 and e_{i} = 1 for all i].

Example 13. We choose M = [u_{1}, u_{2}, …, u_{n} | 1, 2, …, n] with u_{i} + 1 < u_{i+1} for i = 1, 2, …, n − 1, and with A − u_{n} ≥ B − n. (For comparison, see [4, Ex. 2.9].) Then we obtain

t_{i} = min{B + u_{n−j+1} − 1 − 2(i − j), A + n − 2i + j : 1 ≤ j ≤ i}
= min{B + u_{n−i+1} − 1, A + n − 2i + 1}.

By our assumptions, we have

A + n − 2i + 1 ≥ B + u_{n} − 2i + 1 ≥ B + u_{n−i+1} + 2(i − 1) − 2i + 1 = B + u_{n−i+1} − 1.

Hence, we have t_{i} = B + u_{n−i+1} − 1, and the a-invariant of R_{M}(X) equals

∑_{i=1}^{n}(B + u_{n−i+1} − 1) − (A + B + 1)n = Bn + ∑_{i=1}^{n} u_{i} − (A + B + 2)n

= ∑_{i=1}^{n} u_{i} − (A + 2)n,

which is in accordance with the result in [4, Ex. 2.9].

5. How to achieve the maximum number of NE-turns: the two-sided case

We now turn our attention to the two-sided case. We restrict our attention to the case where all B^{(i)}’s lie completely in L, in order to avoid technical difficulties resulting from the condition involving the B^{(i)}’s in Theorem 1.

Again, we begin with the task of maximising the number of NE-turns of a single path in a given ladder region, which is now two-sided. The next lemma provides an algorithmic solution to the problem of finding the maximum number of NE-turns of paths from a given starting point to a given end point staying in a two-sided ladder region. While, in view of Remark 2.(4), the set of lattice paths that we have to consider may actually be larger (namely, it may include some paths which do not lie completely in the ladder region), we will see later that it suffices to consider those paths which do stay in the ladder.

The reader is advised to read the statement below in parallel with the proof sketch that follows the statement. Only then the motivation and meaning of the individual steps of the algorithm will become apparent. While a formal proof could be given, it would be unenlightening. This is the reason we chose to provide a proof sketch, emphasising the (geometric) ideas behind the construction.

Lemma 14. Let A = (a, b), B = (c, d), and S_{i} = (x_{i}, y_{i}) and T_{j} = (z_{j}, w_{j}) be lattice points with a ≤ x_{i}, z_{i} ≤ c and b ≤ y_{i}, w_{i} ≤ d, for i = 1, 2, …, p and j = 1, 2, …, q. The maximum number of NE-turns which a lattice path from A to B which stays weakly south-east of S_{i}, for i = 1, 2, …, p, and weakly north-west of T_{j}, for j = 1, 2, …, q, the NE-turns being different from any of the points T_{j}, j = 1, 2, …, q, can attain can be computed in the following manner:

(1) Form the point set

P_{1} = {A, B} ∪ {S_{i} : 1 ≤ i ≤ p} ∪ {T_{j} : 1 ≤ j ≤ q}.

(2) Replace each point (x, y) ∈ P_{1} by (x + y, x − y). Call the new point set P_{2}.

(3) Order the points in P_{2} according to the size of their first coordinates, from smallest to largest. In the case of ties, order the corresponding points arbitrarily. Let the result of this ordering be

P_{2} = {Â, U_{1}, U_{2}, …, U_{p+q}, B̂}.

Each U_{i} is labelled S or T, depending on whether it came from a point S_{j} or a point T_{j}, respectively. The last point, B̂, which came from B is labelled by S and T.

(4) Successively, form a new point set P_{3}. Initialise P_{3} = {Â}. Scan through U_{1}, U_{2}, … until a point labelled by S is found with larger second coordinate than Â, or until a point labelled by T is found with smaller second coordinate. If such a point is found, add it to P_{3}. If the added point was B̂, continue with (6), otherwise continue with (5).

(5) If the last point added to P_{3} was a point labelled with S, say C = U_{i}, then continue to scan through U_{i+1}, U_{i+2}, …, looking for a point labelled by S with larger second coordinate or for a point labelled by T with smaller second coordinate. If such a point is found, then, in the first case, replace C by this point, while, in the second case, add the point found to P_{3}. If the added point was B̂, continue with (6), otherwise continue with (5).

If the last point added to P_{3} was a point labelled with T, say C = U_{i}, then continue to scan through U_{i+1}, U_{i+2}, …, looking for a point labelled by S with larger second coordinate or for a point labelled by T with smaller second coordinate. If such a point is found, then, in the first case, add this point to P_{3}, while, in the second case, replace C by the point found. If the added point was B̂, continue with (6), otherwise continue with (5).

(6) Let

P_{3} = {V^{(0)} = Â, V^{(1)}, …, V^{(s)}, V^{(s+1)} = B̂}.

Compute the sum

\frac{1}{2} ∑_{i=0}^{s} min \{V_{1}^{(i+1)} + V_{2}^{(i+1)} − V_{1}^{(i)} − V_{2}^{(i)}, V_{1}^{(i+1)} − V_{2}^{(i+1)} − V_{1}^{(i)} + V_{2}^{(i)}\} .  (5.1)

The maximum is for instance realised by the path which connects the points S_{i} and T_{j} corresponding to the points in P_{3} by zig-zag paths prepended by a horizontal or vertical straight piece, as is necessary. More precisely, given two successive points in P_{3}, the corresponding points S_{i} and T_{j} (respectively T_{j} and S_{i}) are connected by a horizontal or vertical straight piece (which may have length 0) followed by a zig-zag path (which may also be empty) with a horizontal step at its end; cf. Figure 8.

Sketch of proof. While explaining what is behind the individual steps of the above algorithm, we illustrate each of them by the running example in which A = (0, 1), S_{1} = (2, 2), S_{2} = (4, 3), S_{3} = (2, 5), S_{4} = (8, 9), S_{5} = (10, 10), S_{6} = (11, 11), T_{1} = (4, 1), T_{2} = (5, 1), T_{3} = (6, 1), T_{4} = (5, 2), T_{5} = (5, 5), T_{6} = (5, 6), T_{7} = (8, 7), T_{8} = (11, 9), T_{9} = (13, 10), B = (12, 14); see Figure 8. Clearly, there is nothing to be said about Step (1) of the algorithm.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{.....}^{.....}. . . . .^{.....}. . . . .^{.....}. . . . .. . . . .. . . . .^{.....}^{.....}. . . . .^{.....}. . . . .^{.....}. . . . .^{.....}. . . . .^{.....}. . . . .^{.....}. . . . .. . . . .. . . . .^{.....} •  • • • •  • • •  • •  • • • • • • • A  T^{1} T^{2} T^{3} S_{1}  T_{4} S_{2} S_{3}  T_{5} T_{6} S_{4} T_{7} S_{5} S_{6} T_{8} T_{9} B

Figure 8. A lattice path with maximal number of NE-turns between the S_{i}’s and the T_{i}’s

From the arguments which proved Lemma 4, we know that a lattice path which will attain the maximum number of NE-turns should be as close as possible to a zig-zag path. So, the “preferred” (rough) direction for our path is north-east, that is, the direction given by the vector (1, 1). What may prevent us from going into that direction from the very beginning until the very end is, first, the location of starting and end point (A and B may not lie on a line parallel to (1, 1)), and, second, the points S_{i}, i = 1, 2, …, p, and T_{i}, i = 1, 2, …, q. If we imagine that we look into the direction (1, 1) and imagine that we move into that direction, then the situation that we encounter is as the one of a skier in a slalom: there are some “gates” which have to be passed on the right (the points S_{i}) and some other “gates” which have to be passed on the left (the points T_{i}).

If we are on a particular line of the form x + y = C (where C is a fixed integer), then along this line we may find some points S_{i} and some points T_{i}. Since the S_{i}’s have to be passed on the right and the T_{i}’s on the left, along this fixed line it is clearly only the right-most among the S_{i}’s and the left-most among the T_{i}’s which are relevant. For example, if we consider the line x + y = 7 in our running example, then along this line we find S_{2}, S_{3}, T_{3}, T_{4}, of which only S_{2} (to be passed on the right) and T_{4} (to be passed on the left) are really relevant, the other points along this line can be disregarded.

In order to find a path from A = (a, b) to B = (c, d) which passes weakly south-east (“to the right”) of the points S_{i} and weakly north-west (“to the left”) of the points T_{i}, we would start at A — which is on the line x + y = a + b, and then proceed to some point on the line x + y = a + b + 1, then to some point on the line x + y = a + b + 2, …, and finally to B — which is on the line x + y = c + d, and on each of these antidiagonal lines we will take care that we pass to the right of the right-most point S_{i} and to the left of the left-most point T_{i} on the line.

Given these observations, we can now understand what the meaning of Step (2) of the algorithm is. Upon replacement of a point (x, y) by (x + y, x − y), the first coordinate, x+y, tells us on which antidigonal line this point lies, and the second coordinate, x−y, tells us how far right or left on that line the point lies. The ordering of the points in P_{2} performed in Step (3) is then done so that first come the points which are on the antidiagonal line x + y = a + b, then the ones on x + y = a + b + 1, …, and finally the ones on x + y = c + d. This is exactly the order in which we have to consider these “gates” as we are advancing during our “slalom run.” In our running example, we would obtain

P_{2} = {(1, −1), (4, 0)_{S}, (5, 3)_{T} , (6, 4)_{T} , (7, 1)_{S}, (7, −3)_{S}, (7, 5)_{T} , (7, 3)_{T} , (10, 0)_{T} , (11, −1)_{T} , (15, 1)_{T} , (17, −1)_{S}, (20, 2)_{T} , (20, 0)_{S}, (22, 0)_{S}, (23, 3)_{T} , (26, −2)_{S,T} }.

(The labelling is indicated by subscripts.)

Steps (4) and (5) take care that only “gates” are kept which are relevant. The relevant ones are stored in the set P_{3}, while the rest of them is disregarded. In addition to the above observation that along a line x + y = C it is only the right-most S_{i} and the leftmost T_{i} which are relevant, there may be more redundant points. Namely, in the proof of Lemma 4 for the one-sided ladder case, we observed that only points S_{i} = (x_{i}, y_{i}) with maximal x_{i} − y_{i} are relevant, the other points can be ignored (cf. (3.1)). The same argument holds here. As a consequence, if the last point added to P_{3} (= the last “relevant” point) was a point corresponding to some S_{i} (“a point labelled by S”), then in Step (5) we search for some S_{j} which is more north-east than S_{i}, and, if we find such an S_{j}, we may replace S_{i} by S_{j}. This is analogous for the points T_{i}.

However, since we have a two-sided ladder region, while advancing we must consider both sides. As in a real slalom, we may be forced to “correct” our direction of movement if we encounter a T -point which is more to the left than the last S-point, and vice versa. This is also reflected in the instructions in Step (5).

For example, returning to our running example in Figure 8, when we start our “slalom run” in A, then our first obstacle which prevents us from doing a zig-zag path starting in A is the point S_{1}, which has to be passed on the right. Indeed, when we apply Step (4) of the algorithm to our example, then, after initialisation P_{3} = {(1, −1)}, we encounter (4, 0)_{S} (which corresponds to S_{1}) which has larger second coordinate than (1, −1) and is labelled by S, and which consequently is added to P_{3}, so that we arrive at P_{3} = {(1, −1), (4, 0)}. The points T_{1} and T_{2} are no obstacles, and, indeed, the corresponding points (5, 3)_{T} and (6, 4)_{T} in P_{2}, which are considered next during the execution of Step (5), do not have smaller second coordinate than (4, 0) and are therefore disregarded. Next comes (7, 1)_{S}, corresponding to S_{2}. It has larger second coordinate than (4, 0) and, according to Step (5), replaces (4, 0) in P_{3}, so that we obtain P_{3} = {(1, −1), (7, 1)}. Indeed, once we include the restriction that S_{2} has to be passed on the right, the restriction imposed by S_{1} becomes obsolete (see the dotted path; no other path between A and S_{2} can have more NE-turns). Continuing the execution of Step (5), the points (7, −3)_{S}, (7, 5)_{T} , (7, 3)_{T} are all ignored. Then comes (10, 0)_{T} which has a smaller second coordinate than (7, 1) and is labelled by T. According to the algorithm, we have to add this point to P_{3}, so that we obtain P_{3} = {(1, −1), (7, 1), (10, 0)}. Indeed, the corresponding point T_{5} prevents us from continuing a zig-zag path emanating from S_{2}, we must “correct” our move slightly to the left. Further continuation of the application of Step (5) will lead to a replacement of (10, 0) by (11, −1), the addition of (20, 0) and finally (26, −2). In other words, after application of Step (5) we arrive at

P_{3} = {(1, −1), (7, 1), (11, −1), (20, 0), (26, −2)}.

After we have found the relevant “gates” — in form of a sequence of points (which alternatingly correspond to points labelled by S and T), by Lemma 4 with n = 0, we must now connect these points by as long as possible zig-zag pieces, supplemented by some straight horizontal respectively vertical pieces as is necessary to connect the zigzag pieces. By the formula (3.1) with n = 0, this leads directly to (5.1), once we recall that the inverse of the mapping (x, y) ↦ (x+y, x−y) is given by (x, y) ↦ \frac{1}{2}(x+y, x−y). In our running example we obtain

\frac{1}{2} (min \{8, 4\} + min \{2, 6\} + min \{10, 8\} + min \{4, 8\}) = 2 + 1 + 4 + 2 = 9.

A path which achieves 9 NE-turns is the dotted path in Figure 8. □

The analogue of Lemma 6 in the two-sided case is the following.

Lemma 15. Let A^{(i)} = (0, a_{i}), E^{(i)} = (B − b_{i}, A), i = 1, 2, …, n, and C_{i} = (x_{i}, y_{i}) and D_{j} = (z_{j}, w_{j}) be lattice points with a_{1} > a_{2} > ⋯ > a_{n} and b_{1} > b_{2} > ⋯ > b_{n}, 0 ≤ x_{i}, z_{i} ≤ B − b_{n} and a_{n} ≤ y_{i}, w_{i} ≤ A, for i = 1, 2, …, p and j = 1, 2, …, q. Then, in any family (P_{1}, P_{2}, …, P_{n}) of non-intersecting lattice paths, where P_{i} runs from A^{(i)} to E^{(i)} and stays weakly south-east of C_{k} and weakly north-west of D_{j}, for k = 1, 2, …, p and j = 1, 2, …, q, the path P_{i} has to pass weakly south-east of all points

{(i − j, a_{j} − i + j) : j = 1, 2, …, i − 1} ∪ {(B − b_{j} + i − j, A − i + j) : j = 1, 2, …, i − 1} ∪ {C_{k} + (i − 1, −i + 1) : k = 1, 2, …, p} (5.2)

and weakly north-west of all points

{D_{k} + (−n + i, n − i) : k = 1, 2, …, q}.  (5.3)

Proof. This is seen in the same way as in the proof of Lemma 6. □

6. The main theorem for two-sided ladder regions

We now apply the findings of the previous section to obtain our second main result.

Theorem 16. Let A^{(i)} = (0, a_{i}), E^{(i)} = (B − b_{i}, A), i = 1, 2, …, n, and S_{i} = (x_{i}, y_{i}) and T_{j} = (z_{j}, w_{j}) be lattice points with a_{1} > a_{2} > ⋯ > a_{n} and b_{1} > b_{2} > ⋯ > b_{n}, 0 ≤ x_{i}, z_{i} ≤ B − b_{n} and a_{n} ≤ y_{i}, w_{i} ≤ A, for i = 1, 2, …, p and j = 1, 2, …, q. The maximum number of NE-turns which a family (P_{1}, P_{2}, …, P_{n}) of non-intersecting lattice paths, where P_{i} runs from A^{(i)} to E^{(i)} and stays weakly south-east of S_{k} and weakly north-west of T_{j}, for k = 1, 2, …, p and j = 1, 2, …, q, can attain, where a NE-turn of P_{i} in a point T_{k} + (−n + i, n − i) is not counted, is

∑_{i=1}^{n} t_{i},

where t_{i} is the outcome of the algorithm described in Lemma 14 when applied to the special case where A = A^{(i)}, B = E^{(i)}, the S_{i}’s being the points in (5.2), and the T_{i}’s being the points in (5.3).

In view of Remark 2.(2), Corollary 3 and Theorem 7, the computation of the ainvariant of two-sided ladder determinantal rings can be accomplished in the following way. In the statement of the following corollary we need an extended meaning of the notion of inwards corners: inwards corners along the upper boundary of a two-sided ladder are defined in the same way as inwards corners of upper ladders, while inwards corners along the lower boundary of a two-sided ladder L are points (x, y) ∈ L for which both (x + 1, y) and (x, y − 1) are in L but (x + 1, y − 1) is not. For example, the inwards corners along the lower boundary of the ladder region in Figure 2 are (6, 8) and (10, 11).

Corollary 17. Let Y = (Y_{i,j})_{0≤i≤A, 0≤j≤B} be a two-sided ladder, and let L be the associated ladder region. Let M = [u_{1}, u_{2}, …, u_{n} | v_{1}, v_{2}, …, v_{n}] be a bivector of positive integers with u_{1} < u_{2} < ⋯ < u_{n} and v_{1} < v_{2} < ⋯ < v_{n}. Furthermore, let A^{(i)} = (0, u_{n−i+1} − 1) and E^{(i)} = (B − v_{n−i+1} + 1, A), i = 1, 2, …, n. We assume that all sets B^{(i)} described in Theorem 1 are completely contained in L, i.e., there exists at least one family P = (P_{1}, P_{2}, …, P_{n}) of non-intersecting lattice paths, P_{i} running from A^{(i)} to E^{(i)}, which are completely contained in L. Then the a-invariant of the ladder determinantal ring R_{M}(Y) = K[Y]/I_{M}(Y) is given by

∑_{i=1}^{n}(t_{i} + u_{i} + v_{i}) − (A + B + 3)n,

where t_{i} is the outcome of the algorithm described in Lemma 14 when applied to the special case where A = A^{(i)}, B = E^{(i)}, the S_{i}’s being the points in (5.2) with C_{k} running through all inwards corners of the upper boundary of L, and the T_{i}’s being the points in (5.3) with D_{k} running through all inwards corners of the lower boundary of L.

Proof. Given Theorem 16, this would be obvious, if there were not the subtle difference between the conditions imposed on the non-intersecting lattice paths in Theorem 16 and the ones in Theorem 1: in the latter theorem, lattice paths are allowed to leave the ladder region L (cf. Remark 2.(4)), while this is not the case if we apply Theorem 16 with the C_{k}’s and the D_{k}’s the inward corners of L. However, it is easy to see that families of non-intersecting lattice paths, where some of the paths protrude outside of L, all of its paths having their NE-turns in L^{(i)}\B^{(i)}, cannot achieve a higher total number of NE-turns than families (P_{1}, P_{2}, …, P_{n}) of paths which stay completely inside L, even if

• _{•} _{•}^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • •  • • •^{P_{n}}^{P_{n−1}}^{P_{n−2}}  _{V}  ^{W}  _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • •  • • •^{P′_{n}}^{P′_{n−1}}^{P′_{n−2}}  _{V}  ^{W}

a. non-intersecting lattice paths b. after push-up of paths not entirely in L

Figure 9. Illustration of the “push-up” of lattice paths in the proof of Corollary 17

one does not count the NE-turns of P_{i} which lie in B^{(i)}. Indeed, let us consider a family of non-intersecting lattice paths, where some its paths run below the lower boundary of L; see the example on the left of Figure 9. There, the ladder region L is indicated by thin dots, and NE-turns of paths are indicated by bold dots. Clearly, this means in particular that the lowest path, P_{n}, has to run below L. Let V be the lattice point in L which is the last point before P_{n} leaves L, and let W be the lattice point in L where P_{n} reenters L after its “excursion”; see Figure 9. We replace the portion of P_{n} lying outside of L by the path between V and W travelling along the lower boundary of L. Since the paths in the family should remain non-intersecting, we may have to “push up” P_{n−1}, P_{n−2}, etc., at the same time; see the right half of Figure 9. These operations do not change the number of NE-turns of P_{i} outside the set B^{(i)}, i = n, n − 1, . . .. Moreover, it should be observed that the points T_{k} + (−n + i, n − i) that would not be counted as NE-turns in Theorem 16 are points lying in B^{(i)}, so that this corresponds well with the previous observation. We do this “push-up” for all portions of paths which lie below L. In principle, these “push-ups” may push up P_{1} beyond the upper boundary of L. However, since we assumed that all sets B^{(i)} are completely contained in L, this cannot happen.

This completes the proof. □

Example 18. We illustrate Corollary 17 by choosing A = 15, B = 13, n = 3, L the ladder region indicated by the dots in Figure 10, and M = [3, 5, 6 | 3, 4, 6]. (The reader should observe that L is also the ladder region in Figure 2.) The ladder can be “described” by the inwards corners C_{1} = (4, 6), C_{2} = (7, 11), and C_{3} = (8, 12) along the upper boundary of L, and by the inwards corners D_{1} = (6, 8) and D_{2} = (10, 11) along the lower boundary of L.

We now have to compute the quantities t_{i}, i = 1, 2, 3. First, we have to apply the algorithm of Lemma 14 with A = A^{(1)} = (0, 5), E = E^{(1)} = (8, 15), S_{1} = (4, 6), S_{2} = (7, 11), S_{3} = (8, 12), T_{1} = (4, 10), and T_{2} = (8, 13). The point set in Step (1) is

P_{1} = {(0, 5), (8, 15), (4, 6), (7, 11), (8, 12), (4, 10), (8, 13)}.

• _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ∘ ∘ ∘  ∘ ∘ ∘_{0}  _{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8} _{9} _{10} _{11} _{12} _{13}^{1}^{2}^{3}^{4}^{5}^{6}^{7}^{8}^{9}^{10}^{11}^{12}^{13}^{14}^{15} ^{A^{(1)}}^{A^{(2)}}^{A^{(3)}}  ^{E^{(1)}} ^{E^{(2)}}^{E^{(3)}} •  • • •  • • • • •  • • • Figure 10

Next, the point set in Step (2) is

P_{2} = {(5, −5), (23, −7), (10, −2), (18, −4), (20, −4), (14, −6), (21, −5)},

while, after the ordering and labelling in Step (3), it is

P_{2} = {(5, −5), (10, −2)_{S}, (14, −6)_{T} , (18, −4)_{S}, (20, −4)_{S}, (21, −5)_{T} , (23, −7)_{S,T} }.

The point set obtained in Step (4) is

P_{3} = {(5, −5), (10, −2)_{S}, (14, −6)_{T} , (18, −4)_{S}, (23, −7)_{S,T} }.

Hence, we have

t_{1} = \frac{1}{2}( min\{8, 2\} + min\{0, 8\} + min\{6, 2\} + min\{2, 8\}) = 3.

The first path in Figure 10 is a path with that number of (valid) NE-turns. In the figure, the (valid) NE-turns are indicated as thick dots. The point (4, 10) is not a valid NE-turn since it lies in the set B^{(1)} (cf. the statement of Theorem 1).

In order to perform the same computation for obtaining t_{2}, we have to apply the algorithm of Lemma 14 with A = A^{(2)} = (0, 4), E = E^{(1)} = (10, 15), S_{1} = (5, 5), S_{2} = (8, 10), S_{3} = (9, 11), T_{1} = (5, 9), and T_{2} = (9, 12). We get

P_{3} = {(4, −4), (10, 0)_{S}, (14, −4)_{T} , (18, −2)_{S}, (25, −5)_{S,T} },

so that

t_{2} = \frac{1}{2}( min\{10, 2\} + min\{0, 8\} + min\{6, 2\} + min\{4, 10\}) = 4.

The second path in Figure 10 is a path with that number of (valid) NE-turns. Finally, in order to perform the computation for obtaining t_{3}, we get

P_{3} = {(2, −2), (10, 2)_{S}, (14, −2)_{T} , (18, 0)_{S}, (26, −4)_{S,T} },

so that

t_{3} = \frac{1}{2}( min\{12, 4\} + min\{0, 8\} + min\{6, 2\} + min\{4, 12\}) = 5.

The third path in Figure 10 is a path with that number of (valid) NE-turns. Consequently, the a-invariant of R_{M}(Y) equals

(3 + 4 + 5 + 3 + 5 + 6 + 3 + 4 + 6) − (15 + 13 + 3) · 3 = −54.

References

[1] S. S. Abhyankar, Enumerative combinatorics of Young tableaux, Marcel Dekker, New York, Basel, 1988.

[2] S. S. Abhyankar and D. M. Kulkarni, On Hilbertian ideals, Linear Alg. Appl. 116 (1989), 53–76.

[3] W. Bruns and J. Herzog, On the computation of a-invariants, manuscripta math. 77 (1992), 201–213.

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

[5] A. Conca, The a-invariant of determinantal ideals, Math. J. Toyama Univ. 18 (1995), 47–63.

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

[7] S. R. Ghorpade, Abhyankar’s work on Young tableaux and some recent developments, in: Proc. Conf. on Algebraic Geometry and Its Applications (Purdue Univ., June 1990), Springer–Verlag, New York, 1994, pp. 215–249.

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

[9] S. R. Ghorpade, Hilbert functions of ladder determinantal varieties, Discrete Math. 246 (2002), 131–175.

[10] S. Goto and K. Watanabe, On graded rings I, J. Math. Soc. Japan 30 (1978), 179–213.

[11] H. G. Gräbe, Streckungsringe, Dissertation B, Pädagogische Hochschule “Dr. Theodor Neubauer”, Erfurt, DDR, 1988.

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

[13] A. Knutson and E. Miller, Gröbner geometry of Schubert polynomials, Ann. Math. (2) 161 (2005), 1245–1318.

[14] 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.

[15] C. Krattenthaler and M. Rubey, A determinantal formula for the Hilbert series of one-sided ladder determinantal rings, in: Algebra, Arithmetic and Geometry with Applications, (C. Christensen, G. Sundaram, A. Sathaye and C. Bajaj, eds.), Springer–Verlag, New York, (2004), pp. 337–356.

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

[17] H. Narasimhan, The irreducibility of ladder determinantal varieties, J. Algebra 102 (1986), 162– 185.

[18] M. Rubey, The h-vector of a ladder determinantal ring cogenerated by 2×2 minors is log-concave, J. Algebra 292 (2005), 303–323.

[19] R. P. Stanley, Hilbert functions of graded algebras, Adv. Math. 28 (1978), 57–83.

[20] H.-J. Wang, A determinantal formula for the Hilbert series of determinantal rings of one-sided ladder, J. Algebra 265 (2003), 79-99.