ad-NILPOTENT 𝔟-IDEALS IN sl(n) HAVING A FIXED CLASS OF

NILPOTENCE: COMBINATORICS AND ENUMERATION

George E. Andrews^{1} Christian Krattenthaler^{2} Luigi Orsina Paolo Papi

Abstract. We study the combinatorics of ad-nilpotent ideals of a Borel subalgebra of sl(n+1, ℂ). We provide an inductive method for calculating the class of nilpotence of these ideals and formulas for the number of ideals having a given class of nilpotence. We study the relationships between these results and the combinatorics of Dyck paths, based upon a remarkable bijection between ad-nilpotent ideals and Dyck paths. Finally, we propose a (q, t)-analogue of the Catalan number C_{n}. These (q, t)-Catalan numbers count on the one hand ad-nilpotent ideals with respect to dimension and class of nilpotence, and on the other hand admit interpretations in terms of natural statistics on Dyck paths.

§1 Introduction

Let 𝔤 be a complex simple Lie algebra of rank n. Let 𝔥 ⊂ 𝔤 be a fixed Cartan subalgebra, Δ the corresponding root system of 𝔤. Fix a positive system Δ^{+} in Δ, and let Π = {α_{1}, …, α_{n}} be the corresponding basis of simple roots. For each α ∈ Δ^{+} let 𝔤_{α} be the root space of 𝔤 relative to α, 𝔫 = ⨁_{α∈Δ^{+}} 𝔤_{α}, and 𝔟 be the Borel

subalgebra 𝔟 = 𝔥 ⊕ 𝔫.

Let I^{n} denote the set of ad-nilpotent ideals (i.e., consisting of ad-nilpotent elements) of 𝔟. These ideals, together with the subclass I_{ab}^{n} of Abelian ideals, have been studied in [6]. In that paper, Kostant stated a useful equivalence criterion for certain decomposably-generated simple K-submodules of Λ(𝔤) in terms of I^{n} (here, K is a compact semi-simple Lie group, and 𝔤 is the complexification of its Lie algebra). Moreover, he used the set of Abelian ideals to describe the eigenspace relative to the maximal eigenvalue of the Laplace-Beltrami operator of K.

The subclass I_{ab}^{n} has been studied much more recently in [7] in connection with discrete series representations. The latter paper was partly motivated by a striking enumerative result due to D. Peterson: the Abelian ideals are 2^{n} in number, independently of the type of 𝔤. (In contrast, the cardinality of I^{n} depends on the

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary: 17B20; Secondary: 05A15 05A19 05E15 17B30.

Key words and phrases. ad-nilpotent ideal, Lie algebra, order ideal, Dyck path, Catalan number, Chebyshev polynomial.

1Partially supported by National Science Foundation Grant DMS 9870060.

2Partially supported by the Austrian Science Foundation FWF, grant P13190-MAT.

type; see [1, Th. 3.1]). Even more surprising is the proof of Peterson’s result, which involves the affine Weyl group Ŵ of 𝔤. In [1], the encoding of the ideals through certain elements of the affine Weyl group has been generalized from I_{ab}^{n} to the entire set I^{n} of ad-nilpotent ideals. There it was shown that any such ideal determines in a combinatorial way the set of “inversions” of a unique element in Ŵ.

The combinatorial methods used in [1] entailed the problem of enumerating the ideals of I^{n} with respect to class of nilpotence. By definition, the class of nilpotence of an ideal 𝔦, which we denote here by n(𝔦), is the smallest number m such that m-fold bracketing of 𝔦 with itself gives the zero ideal. (Thus, the Abelian ideals are exactly those with class of nilpotence at most 1.) A solution to the problem, for 𝔤 of type A_{n}, was obtained in [11], where it was shown that the number of ideals in I^{n} with class of nilpotence k is given by

∑_{0=i_{0}<i_{1}<···<i_{k}<i_{k+1}=n+1} ∏_{j=0}^{k−1} \binom{i_{j+2} − i_{j} − 1}{i_{j+1} − i_{j}}.  (1.1)

(The solution to the problem for 𝔤 of any other classical or exceptional type is given in the forthcoming paper [8].)

The purpose of this paper is to deepen and enhance the understanding of the enumerative properties of ad-nilpotent ideals of a fixed Borel subalgebra of sl(n + 1, ℂ). First of all, after having recalled the algebraic preliminaries in Section 2, we describe in Section 3 a fast combinatorial algorithm for the computation of the class of nilpotence of a given ideal (see Proposition 3.2). (We remark that it is based on a “slow” algorithm, see Proposition 3.1, which has interesting relations to the elements of the affine symmetric group that are obtained by the main result of [1] mentioned earlier; see the remarks at the end of Section 3.)

This algorithm implies naturally a partition into subintervals of the interval [(0, …, 0), (n, n − 1, …, 1)] in the Young lattice, see Proposition 4.1 in Section 4. From this partition, the formula (1.1) follows immediately, thus providing a proof different from the one in [1] (see Theorem 4.2).

However, formula (1.1) gives much more. Since expressions like the one in (1.1) occur in the theory of Dyck paths, it links the enumeration of ad-nilpotent ideals to the enumeration of Dyck paths. To be precise, we prove that there are as many ad-nilpotent ideals of a fixed subalgebra of sl(n + 1, ℂ) with class of nilpotence k as there are Dyck paths of length 2n + 2 with height k + 1 (see Theorem 4.4). As there are numerous formulas available for the number of these Dyck paths, we obtain immediately alternative expressions for the number of these ad-nilpotent ideals, see Theorem 4.5 in Section 4. In particular, formula (4.6) must be preferred over formula (1.1), as it is much simpler and computationally superior. Curious outcomes of these results are, for example, the observation that the number of adnilpotent ideals with class of nilpotence at most 2 (instead of 1, as in Peterson’s result) is a Fibonacci number, as well as the observation that the number of adnilpotent ideals with class of nilpotence at most 3 is essentially a power of 3, see Corollary 4.7.

In Section 5 we make the connection between ad-nilpotent ideals and Dyck paths completely explicit, by exhibiting a bijection between ad-nilpotent ideals in sl(n + 1, ℂ) with class of nilpotence k and Dyck paths of length 2n + 2 with height k + 1.

ad-NILPOTENT 𝔟-IDEALS IN sl(n) 3

The subject of Section 6 is an apparently new (q, t)-analogue of Catalan numbers. (In particular, it is unrelated to the (q, t)-Catalan numbers of Garsia and Haiman [4].) It counts ad-nilpotent ideals in sl(n + 1, ℂ) simultaneously with respect to dimension and class of nilpotence. As it results directly from the earlier mentioned interval decomposition, it is composed out of a rather straightforward (q, t)-extension of formula (1.1), see Theorem 6.1. In terms of combinatorics, for q = 1 this (q, t)-Catalan number reduces to the generating function for Dyck paths counted with respect to height, whereas for t = 1 it reduces to the generating function for Dyck paths counted with respect to area.

Our combinatorial analysis allows us to provide precise results concerning the minimal and maximal dimension of an ideal with fixed class of nilpotence, and the minimal and maximal class of nilpotence of an ideal with fixed dimension. In terms of our (q, t)-analogue of the Catalan number this amounts to determining the minimal and maximal degree in the variable q once the degree in t is fixed, and vice versa. All this is also found in Section 6, see Theorems 6.2 and 6.3.

We now fix the notation that will be used throughout the paper. As usual, we denote the set of integers by ℤ. For binomial coefficients, we will use the following convention: Given integers m and n, we let

\binom{m}{n} = \{ \begin{matrix}\frac{m!}{(m−n)! n!} & if m ≥ n > 0, \\ 1 & if n = 0, \\ 0 & in any other case. \end{matrix}

Similarly, we define the t-binomial coefficient by

[ \begin{matrix}m \\ n \end{matrix} ]_{t} = \{ \begin{matrix}\frac{[m]!}{[m−n]! [n]!} & if m ≥ n > 0, \\ 1 & if n = 0, \\ 0 & in any other case, \end{matrix}

where the t-factorial [m]! is defined by [m]! = [m][m − 1] ⋯ [1], [0]! = 1, with [i] = (t^{i} − 1)/(t − 1).

Finally, for a partition λ = (λ_{1}, …, λ_{n}), λ_{1} ≥ ⋯ ≥ λ_{n} ≥ 0, we write |λ| for the size ∑_{i=1}^{n} λ_{i} of λ. We will identify a partition λ = (λ_{1}, …, λ_{n}) with its Ferrers diagram, which is the array of cells with n left-justified rows, the ith row being of length λ_{i}. For example, Figure 1 shows the (Ferrers diagrams of the) partitions (3, 2, 1) and (3, 1). The cell in the ith row and jth column will be always identified with the pair (i, j).

• •_{Figure 1}

We call a cell of a diagram a corner cell, if there are no cells to the right and to the bottom. For example, the corner cells of the diagram (corresponding to the partition) (3, 1) are the cells labelled (1, 3) and (2, 1) (which are marked by bullets in Figure 1).

§2 Algebraic preliminaries

Let 𝔦 ∈ I^{n}, i.e., 𝔦 is an ad-nilpotent ideal of our fixed Borel subalgebra 𝔟. Clearly, we can write 𝔦 as 𝔦 = ⨁_{α∈Φ} 𝔤_{α}, for some collection Φ of positive roots. The collection

Φ encodes an ideal 𝔦 ∈ I^{n} if and only if for all α ∈ Φ and β ∈ Δ^{+} such that α + β is a root, we have α + β ∈ Φ. If one endows Δ^{+} with the (restriction of the) usual partial order on the root lattice, that is, for α, β ∈ Δ^{+} we let α ≤ β if and only if β − α = ∑_{γ∈Δ^{+}} c_{γ}γ, for some nonnegative integers c_{γ}, then this can be phrased differently as follows: Φ encodes an ideal if and only if it is a dual order ideal in Δ^{+}.

In the rest of the paper we will exclusively deal with 𝔤 of type A_{n}, i.e., the Lie algebra sl(n + 1, ℂ) of (n + 1) × (n + 1) traceless matrices. The last observation of the previous paragraph allows us to represent ad-nilpotent ideals conveniently in a geometric fashion, which will be crucial in all subsequent considerations (see also [1, Sec. 3]). Clearly, any positive root in A_{n} can be written as a sum of simple roots. Explicitly, let us write τ_{ij} = α_{i} + ⋯ + α_{n−j+1}, 1 ≤ i ≤ n, 1 ≤ j ≤ n − i + 1. If we place the roots τ_{ij}, j = 1, 2, …, n−i+1, in the ith row of a diagram, then this defines an arrangement of the positive roots in a staircase fashion. For example, for A_{3} we obtain the arrangement

α_{1} + α_{2} + α_{3} α_{1} + α_{2} α_{1}
α_{2} + α_{3}  α_{2}
α_{3}

Obviously, the above defines an identification of positive roots with cells of the staircase diagram (n, n − 1, …, 1), in which the root τ_{ij} is identified with the cell (i, j). For example, for A_{3}, the root α_{1} + α_{2} is identified with cell (1, 2) in the diagram (3, 2, 1), shown on the left in Figure 1.

Given an ad-nilpotent ideal 𝔦, written as 𝔦 = ⨁_{α∈Φ} 𝔤_{α}, for some collection Φ of

positive roots, we can use the above identification to represent 𝔦 as the set of cells that correspond to the roots in Φ. Since, as we noted above, 𝔦 is a dual order ideal, the set of cells obtained forms a (Ferrers diagram of a) partition. For example, the ideal 𝔤_{α_{1}+α_{2}+α_{3}} ⊕ 𝔤_{α_{1}+α_{2}} ⊕ 𝔤_{α_{1}} ⊕ 𝔤_{α_{2}+α_{3}} corresponds to the partition (3, 1, 0), shown on the right in Figure 1. Clearly, this correspondence is reversible as long as the partition is contained in (n, n − 1, …, 1). Thus, we have defined a bijection between ad-nilpotent ideals in sl(n + 1, ℂ) and subdiagrams of (n, n − 1, …, 1). In particular, as it is well-known that the number of the latter subdiagrams is C_{n+1}, C_{n} = \frac{1}{n+1} \binom{2n}{n} being the n-th Catalan number, the number of ad-nilpotent ideals is equal to the (n + 1)st Catalan number (see [13, Sec. 2] and also [1, Sec. 3]).

§3 Calculating the class of nilpotence

The goal of this section is to describe a fast algorithm to determine the class of nilpotence for any given ad-nilpotent ideal 𝔦. As a first step, we describe a tableau algorithm which computes the descending central series of 𝔦 (i.e., the mfold bracketings of 𝔦 with itself, for any m). More precisely, let t_{i,j} be the maximal number m such that the root space 𝔤_{τ_{ij}} occurs in

𝔦^{m} := \underbrace{[⋯ [𝔦, 𝔦], …]}_{m occurrences of 𝔦} .

Then we claim that the numbers t_{i,j} can be obtained as follows. Let λ be the subdiagram of (n, n − 1, …, 1) that corresponds to 𝔦 according to the identification explained in Section 2. Define a filling (t_{i,j})_{1≤i≤n, 1≤j≤n−i+1} of the cells of (n, n − 1, …, 1) by recursively setting

t_{i,j} = \{ \begin{matrix}0 & if (i, j) ∉ λ, \\ 1 & if (i, j) is a corner cell of λ, \\ max_{j<k≤n−i+1} \{t_{i,k} + t_{n−k+2,j}\} & otherwise. \end{matrix}  (3.1)

It is easy to see that the above rule uniquely defines a filling of (n, n − 1, …, 1), whose nonzero entries are precisely those corresponding to the cells of λ. E.g., when n = 4, the fillings corresponding to (2, 1, 0, 0), (3, 3, 2, 1), (4, 3, 2, 1) are respectively

1 1 0 0 1 0 0 0 0 0  3 2 1 0 3 2 1 2 1 1  4 3 2 1 3 2 1 2 1 1

For the verification of our claim it suffices to observe that if 𝔤_{α} ⊆ 𝔦^{a} and 𝔤_{β} ⊆ 𝔦^{b} then, under the assumption that α + β is a root, 𝔤_{α+β} ⊆ 𝔦^{a+b}. For, with our labelling of positive roots, a sum τ_{i,k} + τ_{l,j} is a root if and only if l = n − k + 2 (or i = n−j +2, which, however, is the same case by symmetry), in which case we have τ_{i,k} +τ_{n−k+2,j} = τ_{i,j}. Thus, if, for some k with j < k ≤ n−i+1, we know that 𝔤_{τ_{i,k}} occurs in 𝔦^{t_{i,k}} and that 𝔤_{τ_{n−k+2,j}} occurs in 𝔦^{t_{n−k+2,j}}, then it follows that 𝔤_{τ_{i,j}} occurs in 𝔦^{t_{i,k}+t_{n−k+2,j}}. Clearly, the maximum of all possible numbers t_{i,k} + t_{n−k+2,j}, is equal to the maximal possible exponent m such that 𝔤_{τ_{ij}} ⊆ 𝔦^{m}. This is exactly the content of (3.1).

Let us summarize our findings so far in the proposition below.

Proposition 3.1. Let 𝔦 ∈ I^{n}. Then, for any (i, j) with 1 ≤ i ≤ n and 1 ≤ j ≤ n − i + 1, the maximal number t_{i,j} such that 𝔤_{τ_{ij}} ⊆ 𝔦^{t_{i,j}} can be determined by the tableau algorithm given in (3.1). In particular, the class of nilpotence of 𝔦 is equal to t_{1,1}, the entry in the top-left cell.

In view of the second statement of Proposition 3.1, this tableau algorithm provides an algorithm for the determination of the class of nilpotence, which, however, is rather slow, as it involves the determination of all the entries in the filling (t_{i,j}). We will now show that, if one is only interested in the determination of t_{1,1} (which, by the second statement of Proposition 3.1 gives exactly the class of nilpotence), then a considerable speedup can be achieved. For a convenient statement of the result, we write, in abuse of notation, n(λ_{1}, λ_{2}, …, λ_{n}) for n(𝔦), given that the partition corresponding to 𝔦 according to the construction in Section 2 is (λ_{1}, λ_{2}, …, λ_{n}).

Proposition 3.2. Let 𝔦 ∈ I^{n} and let λ = (λ_{1}, …, λ_{n}) be the corresponding partition. If λ ≠ (0, 0, …, 0) then

n(λ_{1}, λ_{2}, …, λ_{n}) = n(λ_{n+2−λ_{1}}, …, λ_{n}) + 1.  (3.2)

It should be noted that on the left-hand side of (3.2) appears the class of nilpotence of an ideal in I^{n}, whereas on the right-hand side there appears the class of nilpotence of an ideal in I^{λ_{1}−1} (with corresponding partition (λ_{n+2−λ_{1}}, …, λ_{n})). The computation, however, can be carried out completely formally, without reference to ideals, which we now demonstrate by an example.

Example. Let 𝔦 ∈ I^{13} be the ideal which corresponds to the partition (10, 10, 9, 6, 5, 4, 4, 3, 1, 1, 1, 1, 0). (This is the partition in Figure 2. At this point, all dotted lines should be ignored.) Then, by applying Proposition 3.2 iteratively, we obtain for the class of nilpotence of 𝔦

n(𝔦) = n(10, 10, 9, 6, 5, 4, 4, 3, 1, 1, 1, 1, 0)
= n(5, 4, 4, 3, 1, 1, 1, 1, 0) + 1
= n(1, 1, 1, 0) + 2
= 3.

As is obvious from the example, iterated application of Proposition 3.2 provides a very efficient algorithm of determining the class of nilpotence of a given ideal 𝔦.

Before we move on to the proof, we wish to point out that this algorithm has a very nice geometric rendering. Let, as before, λ = (λ_{1}, λ_{2}, …, λ_{n}) be the partition corresponding to 𝔦. Consider the Ferrers diagram of λ. As it is contained in the staircase diagram (n, n − 1, …, 1), it must not cross the antidiagonal line x + y = n + 1. We draw a zig-zag line as follows (see Figure 2, where n = 13 and λ = (10, 10, 9, 6, 5, 4, 4, 3, 1, 1, 1, 1, 0)): we start on the vertical edge on the right of cell (1, λ_{1}), and move downward until we touch the antidiagonal x + y = n + 1. At the touching point we turn direction from vertical-down to horizontal-left, and move on until we touch a vertical part of the Ferrers diagram. At the touching point we turn direction from horizontal-left to vertical-down. Now the procedure is iterated, until we reach the line x = 0. The class of nilpotence of the ideal 𝔦 is equal to the number of touching points on x + y = n + 1. In Figure 2, the resulting zig-zag line is the dotted line outside the Ferrers diagram of (10, 10, 9, 6, 5, 4, 4, 3, 1, 1, 1, 1, 0). There are three touching points on x + y = n + 1 = 14. (At this point, the dotted lines inside the diagram should still be ignored.)

[figure: .....; . . . . .; . . . . .; . . . . .; ^{.....}; ^{.....}; ^{.....}; ^{.....}; . . . . .; . . . . .; . . . . .; . . . . .; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; ^{.....}; . . . . .; . . . . .; . . . . .; . . . . .; ^{.....}; ^{.....}; ^{.....}; ^{.....}; . . . . .; . . . . .; . . . . .; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; x + y = n + 1; •; •; •]_{Figure 2}

Since we need it in the proof of Proposition 3.2, and also later, let us express this geometric rendering in formal terms. Obviously, the zig-zag line describes the shape of a partition

(i_{k}^{n−i_{k}+1}, i_{k−1}^{i_{k}−i_{k−1}}, …, i_{1}^{i_{2}−i_{1}}, 0^{i_{1}−1}) ,  (3.3)

where i_{k} = λ_{1}, i_{k−1} = λ_{n−i_{k}+2}, i_{k−2} = λ_{n−i_{k−1}+2}, …, i_{1} = λ_{n−i_{2}+2}. Clearly we have 0 < i_{1} < ⋯ < i_{k} < n + 1. (In Figure 2, we have k = 3 and i_{3} = 10, i_{2} = 5, i_{1} = 1.) Any partition λ which gives rise to this zig-zag line must necessarily contain the cells (1, i_{k}), (n − i_{k} + 2, i_{k−1}), (n − i_{k−1} + 2, i_{k−2}), …, (n − i_{2} + 2, i_{1}). (In Figure 2, these are the cells (1, 10), (5, 5), (10, 1).) The “minimal” partition (in the sense of inclusion of diagrams) which contains these cells is

(i_{k}, i_{k−1}^{n−i_{k}+1}, i_{k−2}^{i_{k}−i_{k−1}}, …, i_{1}^{i_{3}−i_{2}}, 0^{i_{2}−2}) .  (3.4)

(In Figure 2, this “minimal” partition is indicated by the dotted lines inside the Ferrers diagram of (10, 10, 9, 6, 5, 4, 4, 3, 1, 1, 1, 1, 0).) For later use, let us denote the partition in (3.3) by λ_{i_{1},... ,i_{k}}^{M}, and the partition in (3.4) by λ_{i_{1},... ,i_{k}}^{m}.

Proof of Proposition 3.2. We first show that the class of nilpotence is at least as large as the number, k say, which is typed out by the algorithm, in its geometric rendering. Let i_{1}, …, i_{k} be as above, 0 < i_{1} < ⋯ < i_{k} < n + 1. As we already noted, the partition λ contains the cells (1, i_{k}), (n−i_{k} +2, i_{k−1}), (n−i_{k−1} +2, i_{k−2}), …, (n−i_{2}+2, i_{1}). In view of the correspondence of Section 2, these cells correspond to the root spaces 𝔤_{τ_{1,i_{k}}}, 𝔤_{τ_{n−i_{k}+2,i_{k−1}}} , …, 𝔤_{τ_{n−i_{2}+2,i_{1}}} contained in the ideal 𝔦. The bracket of

[⋯ [𝔤_{τ_{1,i_{k}}} , 𝔤_{τ_{n−i_{k}+2,i_{k−1}}} ], …, 𝔤_{τ_{n−i_{2}+2,i_{1}}} ]

is simply 𝔤_{τ_{1,i_{1}}} . (In particular, it is nontrivial.) Hence, the class of nilpotence of 𝔦 is at least k, as was claimed.

In order to see that the class of nilpotence does not exceed k, we consider the ideal, 𝔦^{M} say, which corresponds to the partition λ_{i_{1},... ,i_{k}}^{M} (see (3.3)). Clearly, this ideal contains 𝔦. Hence, its class of nilpotence is an upper bound for the class of nilpotence of 𝔦. However, as is seen by inspection, the tableau algorithm (3.1) yields the following for λ_{i_{1},... ,i_{k}}^{M}: the entry t_{i,j}, where n − i_{s} + 2 ≤ i < n − i_{s−1} + 2 and i_{r−1} < j ≤ i_{r}, is given by s − r. (Here, by convention, we have put i_{0} := 0 and i_{k+1} := n + 1.) In particular, the top-left entry, t_{1,1}, which by Proposition 3.2 yields the class of nilpotence of 𝔦^{M}, is equal to (k + 1) − 1 = k. Hence, the class of nilpotence of 𝔦 cannot exceed k, and thus must be equal to k. □

At the end of this section, we want to relate Proposition 3.1 to the main result from [1], the latter setting up a connection between ad-nilpotent ideals and elements of the affine Weyl group for any type of 𝔤.

Let Δ̂ and Ŵ be the affine real root system and the affine Weyl group associated to Δ [5]. Having fixed a positive system Δ^{+} in Δ, we have a corresponding positive system Δ̂^{+} = (Δ^{+} + ℕδ) ∪ (−Δ^{+} + ℤ^{+}δ) in Δ̂ (δ is the ”imaginary root”).

For Φ ⊆ Δ^{+}, set Φ^{k} = (Φ^{k−1} + Φ) ∩ Δ. If moreover Φ is a dual order ideal in Δ^{+} (cf. the first paragraph of Section 2), define

𝔤_{Φ} = ⋃_{k∈ℤ^{+}}(−Φ^{k} + kδ).

Set N(w) = {α ∈ Δ̂^{+} | w^{−1}(α) ∈ Δ̂^{−}}, where Δ̂^{−} = −Δ̂^{+}. It is well known that N(w) determines w uniquely. The main result of [1] is the following theorem, which holds for any simple Lie algebra.

Theorem 3.3. Consider the ideal 𝔦_{Φ} ∈ I^{n} defined by 𝔦_{Φ} = ⨁_{α∈Φ} 𝔤_{α}, where Φ is

a dual order ideal in Δ^{+}. Then there exists a unique w_{Φ} ∈ Ŵ such that 𝔤_{Φ} = N(w_{Φ}). Moreover 𝔤_{Φ} is the minimal set of the form N(v), v ∈ Ŵ (w.r.t. inclusion) containing −Φ + δ.

Proposition 3.4. Let 𝔦_{Φ} ∈ I^{n} be as in Theorem 3.3 and let (t_{i,j}) be the corresponding filling of (n, n − 1, …, 1) (cf. Section 3). Then

N(w_{Φ}) = ⋃_{1≤i≤j≤n} {−τ_{ij} + hδ | 1 ≤ h ≤ t_{i,j}} .

Proof. This is immediate from Proposition 3.1. □

This result admits the following interpretation. Recall that, in type Ã_{n}, Ŵ can be realized as the group of affine permutations [9]:

Ŵ ≅ {w : ℤ ↔ ℤ |w(t + n + 1) = w(t) + n + 1 ∀ t ∈ ℤ,

∑_{t=1}^{n+1} w(t) = \frac{(n + 2)(n + 1)}{2}\}.

Proposition 3.4, together with [12, Th. 1] or [14, Th. 3.2], shows that the filling (t_{i,j}) determines the inversion table [2, Sec. 8] of w_{Φ}, thought of as an affine permutation. In different terms,

⌊\frac{w_{Φ}^{−1}(j) − w_{Φ}^{−1}(i)}{n + 1}⌋ = t_{i,n−j+2}, 1 ≤ i < j ≤ n + 1.

One can be even more explicit by using [14, Th. 5.2]. Namely, for 1 ≤ i ≤ n + 1, we have

w_{Φ}^{−1}(i) = i + ∑_{j=1}^{i−1} t_{j,n−i+2} − ∑_{j=i+1}^{n+1} t_{i,n−j+2}.

Problem. Find a combinatorial characterization of the affine permutations w_{Φ} that correspond, as described above, to ad-nilpotent ideals.

§4 Enumeration of ad-nilpotent ideals

In this section we provide several formulae for the number of ad-nilpotent ideals having a fixed class of nilpotence. The point of departure is a remarkable partition of the interval [(1, …, 0), (n, n−1, …, 1)] in the Young lattice that is implied by the fast algorithm for the determination of class of nilpotence given in Proposition 3.2.

Proposition 4.1. (a) The interval I = [(0, …, 0), (n, n − 1, …, 1)] in the Young lattice can be decomposed into disjoint subintervals as

I = ⋃_{k=0}^{n} ⋃_{0=i_{0}<i_{1}<···<i_{k}<i_{k+1}=n+1}[λ_{i_{1},...,i_{k}}^{m}, λ_{i_{1},...,i_{k}}^{M}],

where λ_{i_{1},...,i_{k}}^{m} and λ_{i_{1},...,i_{k}}^{M} are defined by (3.4) and (3.3), respectively.

(b) Let 𝔦 be an ideal with corresponding partition λ. If λ ∈ [λ_{i_{1},...,i_{k}}^{m}, λ_{i_{1},...,i_{k}}^{M}], then the class of nilpotence of 𝔦 is equal to k.

Proof. This follows immediately from the geometric rendering of Proposition 3.2 (see the remarks after the statement of Proposition 3.2) and the arguments given in the proof of Proposition 3.2. □

Theorem 4.2. The number of ideals in I^{n} with class of nilpotence k is equal to

∑_{0=i_{0}<i_{1}<···<i_{k}<i_{k+1}=n+1} ∏_{j=0}^{k−1} \binom{i_{j+2} − i_{j} − 1}{i_{j+1} − i_{j}}.  (4.1)

Proof. By Proposition 4.1 we have to count the number of partitions λ with λ_{i_{1},... ,i_{k}}^{m} ⊆ λ ⊆ λ_{i_{1},... ,i_{k}}^{M}, when i_{1}, …, i_{k} vary. For fixed i_{1}, …, i_{k} the corresponding number is easily determined: the interval [λ_{i_{1},... ,i_{k}}^{m}, λ_{i_{1},... ,i_{k}}^{M}] decomposes into the product of k Young lattices as follows,

[∅, ((i_{k} − i_{k−1})^{n−i_{k}})] × [∅, ((i_{k−1} − i_{k−2})^{i_{k}−i_{k−1}−1})]

× [∅, ((i_{k−2} − i_{k−3})^{i_{k−1}−i_{k−2}−1})] × ⋯ × [∅, (i_{1}^{i_{2}−i_{1}−1})] . (4.2)

(Here, ∅ stands for the empty partition.) This decomposition is most obvious from Figure 2. There, the dotted lines mark the partitions λ_{i_{1},... ,i_{k}}^{m} and λ_{i_{1},... ,i_{k}}^{M} (with k = 3, i_{3} = 10, i_{2} = 5, i_{1} = 1). As is obvious from the picture, the dotted lines determine k (in Figure 2, we have k = 3) “independent” rectangles. So, if λ ∈ [λ_{i_{1},... ,i_{k}}^{m}, λ_{i_{1},... ,i_{k}}^{M}], there is only freedom within the rectangles, which is expressed by the decomposition (4.2). As the number of partitions which are contained in a rectangle (a^{b}) is equal to the binomial coefficient \binom{a+b}{a}, the result follows. □

Corollary 4.3. The number of ideals in I^{n} with class of nilpotence at most h is equal to

∑_{0=i_{0}≤i_{1}≤···≤i_{h}≤i_{h+1}=n+1} ∏_{j=0}^{h−1} \binom{i_{j+2} − i_{j} − 1}{i_{j+1} − i_{j}}.  (4.3)

Proof. According to Theorem 4.2, we have to sum the expression (4.1) over k from 0 to h. Because of our convention for binomial coefficients (cf. the introduction), this does indeed yield (4.3). For, if in (4.3) we encounter i_{j} and i_{j+1} with i_{j} = i_{j+1} and j ≥ 1, then the binomial coefficient \binom{i_{j+1}−i_{j−1}−1}{i_{j}−i_{j−1}}, which occurs in the summand, vanishes. Hence, the only nonzero contributions in (4.3) are by indices 0 = i_{0} = i_{1} = ⋯ = i_{h−k} < i_{h−k+1} < ⋯ < i_{h} < i_{h+1} = n + 1, for some k.

Because of our convention that \binom{−1}{0} = 1, the corresponding summand reduces to a term which appears in the sum (4.1), upon replacement of i_{j} by i_{j−h+k}, j = h − k, h − k + 1, …, h + 1. □

This corollary makes the link of the enumeration of ad-nilpotent ideals in sl(n + 1, ℂ) to the enumeration of Dyck paths. Recall that a Dyck path is a lattice path from (0, 0) to (2n, 0) with diagonal step vectors (1, 1) and (1, −1) which does not pass below the x-axis. We define the height of a Dyck path to be the maximum ordinate of its peaks.

Theorem 4.4. The number of ideals in I^{n} with class of nilpotence k is exactly the same as the number of Dyck paths from (0, 0) to (2n + 2, 0) with height k + 1.

Proof. The expression (4.3) occurs in [3, Proposition 3.B]. (There, replace n by n + 1, n_{j} by i_{h−j+1} − i_{h−j}, a_{j}b_{j+1} by x, j = 0, 1, …, h, and extract the coefficient of x^{n+1}.) If this is combined with Corollary 2 in [3], then it follows that the expression (4.3) is equal to the number of Dyck paths from (0, 0) to (2n + 2, 0) with height at most h + 1. Clearly, since by Corollary 4.3 we know that it also equals the number of ideals in I^{n} with class of nilpotence at most h, this implies the result. □

An immediate question is, of course, whether it is possible to provide an explicit bijection between the ideals and Dyck paths in Theorem 4.4. We are going to construct such a bijection in Section 5. (It should be noted that the obvious correspondence between ideals and partitions that we described in Section 2 cannot serve this purpose. Although the border of a partition contained in (n, n − 1, …, 1) can be viewed as a Dyck path if the Ferrers diagram is rotated by 45^{∘} in the negative direction, this correspondence does not convert class of nilpotence of the ideal into height of Dyck paths. For example, under this correspondence, the zero ideal, the unique ideal with class of nilpotence 0, translates into the unique Dyck path with height n + 1, i.e., the Dyck path with n + 1 up-steps followed by n + 1 down-steps.)

The enumeration of Dyck paths (and of lattice paths in general) is a well-explored territory, where many explicit results exist. In view of Theorem 4.4, these may now be used to obtain results for ideals with a given class of nilpotence.

Theorem 4.5. The number of ideals in I^{n} with class of nilpotence at most h is (aside from (4.3)) equal to any of the following expressions:

det (\binom{i − max\{0, j − h\} + 1}{j − i + 1})_{1≤i,j≤n}  (4.4)
= det (\binom{i − j + h + 1}{j − i + 1})_{1≤i,j≤n}  (4.5)
= ∑_{k∈ℤ} \frac{2k(h + 3) + 1}{2n + 3}\binom{2n + 3}{n + 1 − k(h + 3)}.  (4.6)

Proof. We observe that, instead of counting Dyck paths, we may equivalently count lattice paths from (0, 0) to (n + 1, n + 1) with step vectors (1, 0), (0, 1) which do not touch the lines y = x − 1 and y = x + h + 2. Then the determinantal expressions follow from [10, Ch. 2, Th. 1], while (4.6) results from [10, Ch. 1, Th. 2] upon little simplification. □

Generating function results for Dyck paths translate into the following result for ideals with a given class of nilpotence.

Theorem 4.6. Let U_{n}(x) denote the nth Chebyshev polynomial of the second kind, U_{n}(cos t) = sin((n + 1)t)/ sin t, or, explicitly,

U_{n}(x) = ∑_{j≥0}(−1)^{j}\binom{n − j}{j}(2x)^{n−2j}.

Let α_{n}(h) denote the number of ideals in I^{n} with class of nilpotence at most h. Then

1 + ∑_{n=0}^{∞} α_{n}(h)x^{n+1} = \frac{U_{h+1} (1/2\sqrt{x})}{\sqrt{x} U_{h+2} (1/2\sqrt{x})}

= \frac{1}{1 − \frac{x}{1 − \frac{x}{\frac{...}{1 − x}}}} .

(In the continued fraction there are h + 1 occurrences of x.)

Proof. The expression in terms of a quotient of Chebyshev polynomials follows, for example, from [3, Prop. 12], while the continued fraction follows from Flajolet’s continued fraction [3, Th. 1]. □

By specializing this generating function result to h = 1, we recover Peterson’s result (in type A_{n}) that the number of Abelian ideals (i.e., the ideals with class of nilpotence at most 1) in I^{n} is 2^{n}. If we specialize Theorem 4.6 to h = 2 and h = 3, we may obtain further enumeration results, which are equally remarkable.

Corollary 4.7. The number of ad-nilpotent ideals in I^{n} with class of nilpotence at most 2 is the Fibonacci number F_{2n}. The number of ad-nilpotent ideals in I^{n} with class of nilpotence at most 3 is (3^{n} + 1)/2.

§5 A bijection between ad-nilpotent ideals and Dyck paths

Now we describe a bijection between ideals in I^{n} with class of nilpotence k and Dyck paths from (0, 0) to (2n + 2, 0) with height k + 1.

Let 𝔦 ∈ I^{n}, and let λ be the corresponding partition contained in (n, n−1, …, 1), according to the correspondence described in Section 2. The first step consists of determining the interval, according to the decomposition of Proposition 4.1, the partition λ is in. I.e., we determine the integers i_{k}, i_{k−1}, …, i_{1} such that λ ∈ [λ_{i_{1},...,i_{k}}^{m}, λ_{i_{1},...,i_{k}}^{M}]. To use the example of Section 3, λ = (10, 10, 9, 6, 5, 4, 4, 3, 1, 1, 1, 1, 0) (with n = 13), we have k = 3, i_{3} = 10, i_{2} = 5, i_{1} = 1. Figure 2 shows this partition. The dotted line outside indicates the partition λ_{i_{1},...,i_{k}}^{M} = λ_{1,5,10}^{M}, the dotted line inside indicates λ_{i_{1},...,i_{k}}^{m} = λ_{1,5,10}^{m}.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

a.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

b.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

c. Figure 3

Now one generates a Dyck path step by step. One starts with n+1−i_{k} up-down pieces (in our example: k = 3 and n + 1 − i_{k} = n + 1 − i_{3} = 4; see Figure 3.a).

In order to explain the next steps, we need to observe (as we did already earlier) that the interval [λ_{i_{1},...,i_{k}}^{m}, λ_{i_{1},...,i_{k}}^{M}] pictorially decomposes into k independent rectangles. In the example of Figure 2, these are the rectangles formed by the dotted lines, the top-most rectangle being a 3 × 5 rectangle, the next a 4 × 4 rectangle, and the bottom-most a 3 × 1 rectangle (see Figure 2).

Now, in the top-most rectangle, we follow the shape of λ inside the rectangle, from top-right to bottom-left. In our example of Figure 2, this shape is dldllldl, the letter d indicating a down-step in the shape, the letter l indicating a leftstep. Thus, to the portion of the shape contained in the rectangle corresponds a word l^{a_{0}}d l^{a_{1}}d … d l^{a_{i_{k}−i_{k−1}}} . We insert a_{0} up-down pieces into the first peak of the already existing Dyck path (which, by now, is just a zig-zag line; see Figure 3.a), a_{1} up-down pieces into the second peak, etc. In our example this generates the Dyck path in Figure 3.b.

This procedure is now repeated, by considering the remaining rectangles oneby-one, from top to bottom. From now on, up-down pieces are only inserted into highest peaks. To continue our example, the next shape portion to be considered (the one contained in the 4 × 4 rectangle) is lddldlld. Hence, 1 up-down piece is inserted into the first peak (of height 2, since only highest peaks are considered for insertions) in Figure 3.b, 0 up-down pieces into the second peak, etc.

The final result of this procedure, applied to the partition in Figure 2, is shown in Figure 3.c (i.e., after also having considered the bottom-most rectangle).

It is obvious that the result of this mapping is a Dyck path with height k + 1. Conversely, given a Dyck path with height k + 1, it is obvious how to reverse the mapping and obtain the corresponding partition λ, and, thus, the corresponding ideal 𝔦 with n(𝔦) = k. Therefore we have found the desired bijection.

§6 A (q, t)-analogue of the Catalan number

As we said in the introduction, the total number of ad-nilpotent ideals of a Borel subalgebra of sl(n+1, ℂ) is the Catalan number C_{n+1}. Let α_{n}(h, k) be the number of such ideals with dimension h and class of nilpotence k. Then the generating function

C_{n}(q, t) = ∑_{h,k≥0} α_{n}(h, k)t^{h}q^{k}

is a (q, t)-analogue of the Catalan number C_{n+1}. (It is unrelated to the Garsia-Haiman (q, t)-Catalan number [4]. This can be seen, for example, by recalling that the Garsia-Haiman (q, t)-Catalan number is symmetric in q and t, whereas our (q, t)-Catalan number is highly nonsymmetric.)

Define the area A(P) of a Dyck path P as the area of the region between P and the x-axis. Our (q, t)-Catalan number has the following properties.

Theorem 6.1. We have

C_{n}(q, t) = ∑_{k=0}^{n} ( ∑_{0=i_{0}<i_{1}<···<i_{k}<i_{k+1}=n+1} ∏_{j=0}^{k−1} t^{i_{j+1}(i_{j+3}−i_{j+2})} [ \begin{matrix}i_{j+2} − i_{j} − 1 \\ i_{j+1} − i_{j} \end{matrix} ]_{t}) q^{k},

(6.1)

with i_{k+2} = n + 2. C_{n}(q, 1) is the generating function for Dyck paths from (0, 0) to (2n + 2, 0) counted with respect to height. C_{n}(1, t) is the generating function for the same set of Dyck paths with respect to the weight function (n + 1)^{2}/2 − A(·).

Proof. The expression (6.1) is obtained by following along the arguments of the proof of Theorem 4.2. That is, for fixed class of nilpotence, we use the decomposition (4.2) (see also Figure 2). This reduces the problem to the problem of finding the generating function ∑_{λ} t^{|λ|} summed over all partitions λ which are contained in an a × b rectangle. As is well-known (cf., e.g., [15, Prop. 1.3.19]), this is the t-binomial coefficient [ \begin{matrix}a+b \\ b \end{matrix} ]_{t}. Thus, we obtain the expression (6.1).

The claim about C_{n}(q, 1) is the content of Theorem 4.4. For the proof of the claim about C_{n}(1, t) we use the correspondence of Section 2 between ideals 𝔦 and partitions λ contained in (n, n−1, …, 1). Under this correspondence, the dimension of the ideal 𝔦 is converted into the size |λ| of the partition. If we rotate the Ferrers diagram of λ by 45^{∘} in the negative direction, then the border of the Ferrers diagram forms a Dyck path, the area of which is exactly equal to (n + 1)^{2}/2 − |λ|. □

We are now going to investigate extremal properties, with respect to dimension and class of nilpotence, of ad-nilpotent ideals. First, we fix the class of nilpotence to k, say, and ask what the possible dimensions of ideals with class of nilpotence k is. I.e., the task is to determine the minimal and maximal possible dimension of an ideal under the assumption that its class of nilpotence is k. Let us denote the minimal possible dimension by θ_{n}^{min}(k) and the maximal possible dimension by θ_{n}^{max}(k). In terms of our (q, t)-Catalan number C_{n}(q, t), we ask for the minimal and maximal degree in the variable t among the terms which have degree k in q.

Theorem 6.2. We have

θ_{n}^{min}(k) = \binom{k + 1}{2} + (k − 1)(n − k) ,  (6.2)

and

θ_{n}^{max}(k) = \binom{n + 1}{2} − (n + 1) ⌊\frac{n + 1}{k + 1}⌋ + (k + 1)\binom{⌊(n + 1)/(k + 1)⌋ + 1}{2}. (6.3)

Proof. In view of the correspondence between ideals and partitions given in Section 2, determining θ_{n}^{min}(k) amounts to finding the partitions λ = (λ_{1}, λ_{2}, …, λ_{n}) contained in the staircase (n, n − 1, …, 1) with minimal size |λ| under the condition that n(λ) = k (i.e., under the condition that the algorithm of Proposition 3.2 outputs k for λ). It is easily seen that under this assumption we must have λ_{1} ≥ k.

Formula (6.2) yields θ_{n}^{min}(1) = 1. On the other hand, we have n(1, 0, …, 0) = 1 independent of the number of zeroes, since the dimension of the ideal associated to (1, 0, …, 0) is always 1. Let us now prove the formula by induction on k. We begin by observing that if λ = (λ_{1}, λ_{2}, …, λ_{n}) is a partition with n(λ) = k + 1 and |λ| minimal, then, applying Proposition 3.2, one deduces that |(λ_{n+2−λ_{1}}, …, λ_{n})| has to be minimal, too. Thus, we have to fix λ_{1} between k + 1 and n, and then take a partition η which realizes θ_{n+2−λ_{1}}^{min}(k), which we then complete to a partition realizing θ_{n}^{min}(k + 1) in the following way: if η = (s, …), then we take λ as (λ_{1}, s^{n−λ_{1}}, …). We thus have

θ_{n}^{min}(k + 1) = min_{k+1≤r≤n} min_{k≤s≤r−1}{r + (n − r)s + θ_{r−1}^{min}(k)} .

By induction, θ_{s}^{min}(k) = \binom{k+1}{2} + (s − 1)(k − 1), and so

θ_{n}^{min}(k + 1) = min_{k+1≤r≤n} min_{k≤s≤r−1} \{r + (n − r)s + \frac{k(k+1)}{2} + (r − 1 − k)(k − 1)\} .

Since n ≥ r and k ≥ 1, the minimum on s is reached for s = k, and so

θ_{n}^{min}(k + 1) = min_{k+1≤r≤n} \{r + nk − rk + \frac{k(k+1)}{2} + r(k − 1) − (k^{2} − 1)\} .

Thus,

θ_{n}^{min}(k + 1) = min_{k+1≤r≤n} \{nk + \frac{k(k+1)}{2} − k^{2} + 1\} = \binom{k + 2}{2} + k(n − k − 1) ,

which is what we wanted to prove.

Now we consider the case of the maximum. We want to find partitions λ, contained in the staircase (n, n − 1, …, 1), with exactly k outer corners on the antidiagonal x + y = n + 1, such that their size |λ| is maximal.

Let us consider such a partition λ, see Figure 4 for an example, in which n = 9 and k = 3, the partition being (6, 6, 6, 6, 5, 2, 2, 2, 0). Let us write μ_{0} = n + 1 − λ_{1}, μ_{1} = λ_{1} − λ_{2}, …, μ_{k−1} = λ_{k−1} − λ_{k}, and μ_{k} = λ_{k}. See Figure 4 for the geometric meaning of these quantities, where μ_{0} = 4, μ_{1} = 1, μ_{2} = 3, μ_{3} = 2. Clearly,

[figure: . . . . .; . . . . .; ^{.....}; ^{.....}; ^{.....}; ^{.....}; μ_{0}; μ_{0}; μ_{1}; μ_{1}; μ_{2}; μ_{2}; μ_{3}; μ_{3}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; x + y = n + 1; •; •; •]_{Figure 4}

n + 1 = μ_{0} + μ_{1} + ⋯ + μ_{k}, i.e., μ = (μ_{0}, μ_{1}, …, μ_{k}) is a composition of n + 1 with exactly k + 1 parts. Moreover, the composition μ determines the partition λ uniquely. Therefore we may as well encode a partition with all its outer corners on the antidiagonal x + y = n + 1 by the corresponding composition μ.

We will base our argument on the following two easily verified facts:

Fact 1. Let λ be a partition (with all outer corners on x + y = n + 1) with corresponding composition μ. Let μ′ be a composition which arose from μ by permuting the parts. Then the partition corresponding to μ′ has the same size as λ.

Fact 2. Let λ be a partition with exactly k outer corners, all of them on x + y = n + 1, such that its size is maximal with respect to such partitions. Then, in the corresponding composition μ = (μ_{0}, μ_{1}, …, μ_{k}), we have |μ_{i−1} − μ_{i}| ≤ 1 for i = 1, 2, …, k.

Both facts combined say that, in order to find a partition with exactly k outer corners, all of them on x + y = n + 1, such that its size is maximal, we are looking for a partition whose corresponding composition μ has the property that any two of its parts differ by at most 1. Thus, μ is a composition with at most two different parts, one being ⌊(n + 1)/(k + 1)⌋, and the other being ⌈(n + 1)/(k + 1)⌉. Clearly, the latter must appear n + 1 − (k + 1) ⌊(n + 1)/(k + 1)⌋ times, whereas the former must appear (k − n + (k + 1) ⌊(n + 1)/(k + 1)⌋) times. If one does the required algebra, then one obtains that the size of such a partition is exactly the expression on the right hand side of (6.3). □

Now we fix the dimension to A, say, and ask what the possible classes of nilpotence of ideals with dimension A is. I.e., now the task is to determine the minimal and maximal possible classes of nilpotence of an ideal under the assumption that its dimension is A. Let us denote the minimal possible class of nilpotence by Θ_{n}^{min}(k) and the maximal possible class of nilpotence by Θ_{n}^{max}(k). In terms of our (q, t)- Catalan number C_{n}(q, t), we ask for the minimal and maximal degree in the variable q among the terms which have degree A in t.

Theorem 6.3. We have

Θ_{n}^{min}(A) = min \{k : \binom{n + 1}{2}−(n+1) ⌊\frac{n + 1}{k + 1}⌋+(k+1)\binom{⌊\frac{n+1}{k+1}⌋ + 1}{2} ≥ A\} , (6.4)

and

Θ_{n}^{max}(A) = ⌊n + \frac{3}{2} − \frac{1}{2} \sqrt{4n^{2} + 4n + 9 − 8A}⌋ .  (6.5)

Proof. Let us first consider the maximum. We denote the expression on the right hand side of (6.2) by m(k). Furthermore let K_{0} = max{k : m(k) ≤ A}. Equivalently, we have

m(K_{0}) ≤ A < m(K_{0} + 1).  (6.6)

It is obvious that Θ_{n}^{max}(A) ≤ K_{0}. We would like to prove equality, because that yields immediately (6.5) upon a straightforward calculation.

In order to establish Θ_{n}^{max}(A) = K_{0}, we consider the partition λ_{0} = (K_{0}, (K_{0} − 1)^{n−K_{0}+1}, K_{0} − 2, …, 2, 1), which realizes the minimum in (6.2) (with k = K_{0}), i.e., |λ_{0}| = m(K_{0}). It is the lower bound of the interval

[(K_{0}, (K_{0} − 1)^{n−K_{0}+1}, K_{0} − 2, …, 2, 1), (K_{0}^{n+1−K_{0}}, K_{0} − 1, K_{0} − 2, …, 2, 1)]

= [λ_{1,2,...,K_{0}}^{m}, λ_{1,2,...,K_{0}}^{M}] (6.7)

in the decomposition guaranteed by Proposition 4.1. Recall that all partitions λ in this interval satisfy n(λ) = K_{0}. The size of λ_{1,2,...,K_{0}}^{M} is equal to \binom{K_{0}}{2} + (n + K_{0} − 1)K_{0}, which is exactly m(K_{0} + 1) − 1. Hence, because of (6.6), we will be able to find a partition in the interval (6.7) with size A. This establishes (6.5).

Now we turn to the minimum. Although the idea is analogous, the details are more elaborate.

We denote the expression on the right hand side of (6.3) by M(k). Furthermore let K_{1} = min{k : M(k) ≥ A}. Equivalently, we have

M(K_{1}) ≥ A > M(K_{1} − 1).  (6.8)

It is obvious that Θ_{n}^{min}(A) ≥ K_{1}. We would like to prove equality.

In order to establish Θ_{n}^{min}(A) = K_{1}, we consider the partition

λ_{1} = ( (n + 1 − ⌈\frac{n+1}{K_{1}+1}⌉)^{⌈(n+1)/(K_{1}+1)⌉} , (n + 1 − 2 ⌈\frac{n+1}{K_{1}+1}⌉)^{⌈(n+1)/(K_{1}+1)⌉} ,

…, (2 ⌊\frac{n+1}{K_{1}+1}⌋)^{⌊(n+1)/(K_{1}+1)⌋} , (⌊\frac{n+1}{K_{1}+1}⌋)^{⌊(n+1)/(K_{1}+1)⌋} ), (6.9)

(to be precise, the partition corresponding to the composition (⌈\frac{n+1}{K_{1}+1}⌉^{a}, ⌊\frac{n+1}{K_{1}+1}⌋^{b}), where we have abbreviated a = n + 1 − (K_{1} + 1)⌊\frac{n+1}{K_{1}+1}⌋ and b = K_{1} − n + (K_{1} + 1)⌊\frac{n+1}{K_{1}+1}⌋; see the second part of the proof of Theorem 6.2), which realizes the maximum in (6.3) (with k = K_{1}), i.e., |λ_{1}| = M(K_{1}). It is the upper bound of the interval

[λ_{(i_{1},...,i_{K_{1}} )}^{m}, λ_{(i_{1},...,i_{K_{1}} )}^{M}],  (6.10)

where

(i_{1}, …, i_{K_{1}}) = ( ⌊\frac{n+1}{K_{1}+1}⌋ , 2 ⌊\frac{n+1}{K_{1}+1}⌋ , …, n + 1 − 2 ⌈\frac{n+1}{K_{1}+1}⌉ , n + 1 − ⌈\frac{n+1}{K_{1}+1}⌉ ),

in the decomposition guaranteed by Proposition 4.1. Recall that all partitions λ in this interval satisfy n(λ) = K_{1}. As a moderately tedious computation shows, the size of λ_{(i_{1},...,i_{K_{1}} )}^{m} is equal to

\{ \begin{matrix}\binom{n+1}{2} − (3n + 4) ⌊\frac{n+1}{K_{1}+1}⌋ + (3K_{1} + 5)\binom{⌊(n+1)/(K_{1}+1)⌋+1}{2} & if (K_{1} + 1) ∤ (n + 1), \\ \binom{n+1}{2} − (3n + 5)\frac{n+1}{K_{1}+1} + (3K_{1} + 5)\binom{(n+1)/(K_{1}+1)+1}{2} & if (K_{1} + 1) | (n + 1). \end{matrix}

(6.11)

If we are able to establish that this value is less than or equal to M(K_{1} − 1) + 1, then, because of (6.8), we will be able to find a partition in the interval (6.10) with size A. This would establish (6.4).

In fact, it turns out that the preceding claim is only true for K_{1} > 1. Hence, we will treat the case of K_{1} = 1 separately at the end of the proof.

Let K_{1} > 1. First, the claim is easily verified directly for K_{1} = n (in which case the expression in the second line of (6.11) has to be used). Second, we verify our claim for n = 1, 2, …, 6. This is readily done with the help of a computer. (It can even be done by hand.) Thus, in the sequel, we may assume that K_{1} ≤ n − 1 and n ≥ 7.

Since the expression in the second line in (6.11) is smaller than the expression in the first line, it suffices to prove that the expression in first line is less or equal to M(K_{1} − 1) + 1. That is, we must show

\binom{n + 1}{2} − (3n + 4) ⌊\frac{n + 1}{K_{1} + 1}⌋ + (3K_{1} + 5)\binom{⌊(n + 1)/(K_{1} + 1)⌋ + 1}{2}

≤ \binom{n + 1}{2} − (n + 1) ⌊\frac{n + 1}{K_{1}}⌋ + K_{1}\binom{⌊(n + 1)/K_{1}⌋ + 1}{2} + 1

This inequality is equivalent to

0 ≤ (3n + 4) ⌊\frac{n + 1}{K_{1} + 1}⌋ − (3K_{1} + 5)\binom{⌊(n + 1)/(K_{1} + 1)⌋ + 1}{2}

+ K_{1}\binom{⌊(n + 1)/K_{1}⌋ + 1}{2} − (n + 1) ⌊\frac{n + 1}{K_{1}}⌋ + 1. (6.12)

It should be observed that, as long as K_{1} is between n/2 + 1 and n − 1, the right hand side of (6.12) is linear and monotone decreasing in K_{1}. On the other hand, it is trivially true for K_{1} = n − 1. Hence, it is true for all K_{1} ≥ n/2 + 1. This allows us to assume K_{1} ≤ (n + 1)/2 from now on.

The expression on the right hand side of (6.12) is quadratic in ⌊(n + 1)/K_{1}⌋, with the minimum of the quadratic polynomial at (n + 1)/K_{1} − 1/2. Thus, if we would be able to prove (6.12) with ⌊(n + 1)/K_{1}⌋ replaced by (n+1)/K_{1} −1/2, the original inequality would be established. Similarly, the right hand side of (6.12) is quadratic in ⌊(n + 1)/(K_{1} + 1)⌋. Therefore, depending on whether ⌊(n + 1)/(K_{1} + 1)⌋ is to the right or to the left of the maximum of the corresponding quadratic polynomial, it suffices to prove (6.12) with ⌊(n + 1)/(K_{1} + 1)⌋ replaced by (n + 1)/(K_{1} + 1), respectively (n − K_{1} + 1)/(K_{1} + 1).

In summary, we will be done once we have established the inequalities

0 ≤ \frac{\begin{matrix}(−8n − 12K_{1} − 9K_{1}^{2} − 4n^{2} − 4 − 4K_{1}n^{2} \\ − 16K_{1}n + 8K_{1}^{2}n^{2} − 8K_{1}^{3}n − 10K_{1}^{3} − K_{1}^{4}) \end{matrix}}{8K_{1}(K_{1} + 1)^{2}} ,

(6.13)

corresponding to replacing ⌊(n + 1)/K_{1}⌋ by (n+1)/K_{1}−1/2 and ⌊(n + 1)/(K_{1} + 1)⌋ by (n + 1)/(K_{1} + 1) in (6.12), and

0 ≤ \frac{\begin{matrix}(−8n − 12K_{1} + 19K_{1}^{2} − 4n^{2} − 4 − 4K_{1}n^{2} − 16K_{1}n \\ + 8K_{1}^{2}n^{2} + 16K_{1}^{2}n − 8K_{1}^{3}n − 6K_{1}^{3} − K_{1}^{4}) \end{matrix}}{8K_{1}(K_{1} + 1)^{2}} ,

(6.14)

corresponding to replacing ⌊(n + 1)/K_{1}⌋ by (n+1)/K_{1}−1/2 and ⌊(n + 1)/(K_{1} + 1)⌋ by (n − K_{1} + 1)/(K_{1} + 1) in (6.12).

We concentrate on the proof of (6.13). The proof of (6.14) is similar.

First of all, it can be verified directly that (6.13) is true for K_{1} = 2 and n ≥ 7. Therefore, from now on, we may assume K_{1} ≥ 3. Next we differentiate the expression on the right hand side of (6.13) with respect to K_{1}, thus obtaining

− \frac{\begin{matrix}(n^{2}(8K_{1}^{3} − 16K_{1}^{2} − 12K_{1} − 4) + n(16K_{1}^{3} − 32K_{1}^{2} − 24K_{1} − 8) \\ + K_{1}^{5} + 3K_{1}^{4} + 11K_{1}^{3} − 15K_{1}^{2} − 12K_{1}) \end{matrix}}{8K_{1}^{2}(K_{1} + 1)^{3}} .

This is most evidently negative for K_{1} ≥ 3. Hence, the right hand side of (6.13) is monotone decreasing for K_{1} ≥ 3. Thus, if we are able to verify (6.13) for the maximal K_{1} that we are considering, i.e., K_{1} = (n+1)/2, then (6.13) is established for all K_{1} between 3 and (n + 1)/2. Now, if we substitute K_{1} = (n + 1)/2 into (6.13), we obtain

\frac{(n + 1)(15n^{2} − 70n − 217)}{16(n + 3)^{2}},

which is positive for n ≥ 7, as desired.

Finally, we treat the case K_{1} = 1. In that case, because of (6.8), our given size A must satisfy 1 ≤ A ≤ ⌊(n + 1)/2⌋ ⌈(n + 1)/2⌉. If A ≥ n, then there is a partition in the interval [I_{⌊(n+1)/2⌋}^{m}, I_{⌊(n+1)/2⌋}^{M}] with size A. Otherwise, there is a partition in the interval [I_{1}^{m}, I_{1}^{M}] with size A.

This completes the proof of the theorem. □

References

[1] P. Cellini, P. Papi, ad-nilpotent ideals of a Borel subalgebra, J. Algebra 225 (2000), 130–141.

[2] H. Eriksson, K. Eriksson, Affine Weyl groups as infinite permutations, Electron. J. Combin. 5 (1998).

[3] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.

[4] A. M. Garsia and M. Haiman, A remarkable q, t-Catalan sequence and q-Lagrange inversion, J. Alg. Combin. 5 (1996), 191–244.

[5] V.G. Kac, Infinite Dimensional Lie Algebras, Cambridge University Press, 1990.

[6] B. Kostant, Eigenvalues of a Laplacian and commutative Lie subalgebras, Topology 3, suppl. 2 (1965), 147–159.

[7] B. Kostant, The Set of Abelian ideals of a Borel Subalgebra, Cartan Decompositions, and Discrete Series Representations, Internat. Math. Res. Notices 5 (1998), 225–252.

[8] C. Krattenthaler, L. Orsina and P. Papi, Enumeration of ad-nilpotent 𝔟-ideals for simple Lie algebras, in preparation.

[9] G. Lusztig, Some examples of square integrable representations of semisimple p-adic groups, Trans. Amer. Math. Soc. 277 (1983), 623–653.

[10] G. Mohanty, Lattice path counting and applications, Academic Press, 1979.

[11] L. Orsina, P. Papi, Enumeration of ad-nilpotent ideals of a Borel subalgebra in type A by class of nilpotence, Comptes Rendus Acad. Sciences Paris Ser. I Math. (to appear).

[12] P. Papi, Inversion tables and minimal left coset representatives for Weyl groups of classical type, J. Pure Appl. Algebra 161 (2001), 219–234.

[13] J. Shi, The number of ⊕-sign types, Quart. J. Math. Oxford 48 (1997), 93–105.

[14] J. Shi, On two presentations of the affine Weyl groups of classical types, J. Algebra 221 (1999), 360–383.

[15] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986, reprinted by Cambridge University Press, Cambridge, 1998.

Department of Mathematics The Pennsylvania State University 215 McAllister Building University Park PA 16802, USA e-mail: andrews@math.psu.edu

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail:KRATT@Ap.Univie.Ac.At

Dipartimento di Matematica, Istituto G. Castelnuovo Università di Roma “La Sapienza” Piazzale Aldo Moro 5 00185 Rome — ITALY e-mail: orsina@mat.uniroma1.it, papi@mat.uniroma1.it