Nesting Nonpartitions

Joshua Marsh and Nathan Williams Department of Mathematical Sciences 800 W. Campbell Road Richardson, TX 75080 USA

                    joshuawmarsh@gmail.com
                 nathan.williams1@utdallas.edu

Abstract

Antichains of root posets associated with simple complex Lie algebras are a wellstudied combinatorial object, famously counted by the Coxeter-Catalan numbers. In this paper, we study chains in root posets using standard enumerative techniques. The factorizations of the zeta polynomials of these root posets gives rise to sequences that have similar numerological properties as the exponents of the Weyl group.

1 Introduction

Call an interval [a, b] n-integral if a and b are integers 1 ≤ a < b ≤ n. We say that two n-integral intervals are nesting if one is contained in the other. In this language, nonnesting partitions may be defined as sets of distinct n-integral intervals with no pair of intervals nesting. Nonnesting partitions are a classical Catalan object—they are counted by the ubiquitous Catalan numbers, which appear as Sequence \underline{A000108} in Sloane’s On-Line Encyclopedia of Integer Sequences [?]:

Cat(n) = ∏_{i=1}^{n−1} \frac{n + i + 1}{i + 1}.  (\underline{A000108})

We may ask instead about nesting nonpartitions on n points: sets of distinct n-integral intervals such that every pair of intervals nests. For example, there are 1, 2, 6, 20, 68, and 232 nesting nonpartitions on 1, 2, 3, 4, 5, and 6 points. The 20 nesting nonpartitions on four points are illustrated in Figure 1.

Figure 1: The 20 nesting nonpartitions on n = 4 points, ordered by inclusion.

It is not difficult to show that the number of nesting nonpartitions on n + 1 points is given by

∑_{k=0}^{n} ∑_{i=0}^{k} \binom{n}{2i}\binom{n − i}{k − i} = \frac{(2 + \sqrt{2})^{n} + (2 − \sqrt{2})^{n}}{2} .  (\underline{A006012})

Define a k-multinesting nonpartition to be a set of k n-integral intervals such that every pair of intervals nests (intervals may now appear with multiplicity). As we show in Section ??, the number of k-multinesting nonpartitions is given by the compact expression

ζ_{A_{n}}(k) = ∏_{i=1}^{n−1} \frac{2k + i}{i}.  (1)

Nesting nonpartitions on n+1 points are naturally interpreted as chains in the root poset of type A_{n}—we will review root systems and root posets in Section 2. This phrasing allows us to define the k-multinesting nonpartitions for a general irreducible root system Φ as the multichains of length k in the restriction of the root poset to the short roots, and state a root-theoretic generalization of Equation 1.

Theorem 1. Let Φ be an irreducible crystallographic root system. Then the number of k-multinesting nonpartitions is given by

ζ_{Φ_{s}^{+}}(k) = ∏_{i=1}^{g−2} \frac{2k + δ_{i}}{δ_{i}} ,

for the sequence of positive integers δ_{1} ≤ δ_{2} ≤ ⋯ ≤ δ_{g−2} = h − 2 given in Table 1, where h is the Coxeter number of Φ, and g is the dual Coxeter number of the dual root system Φ^{∨}.

Our proofs are case-by-case, and—although we show in Proposition ?? that the sequences (δ_{i})_{i=1}^{g−2} have connections to the numerology of the root system—we have been unable to find a representation-theoretic interpretation of these numbers.

\begin{matrix}W & ϵ_{1}, ϵ_{2}, …, ϵ_{g−1} \\ A_{n} & 1 2 … n \\ B_{n} & 1 3 … 2n−1 \\ C_{n} & \begin{aligned}1 & 3 & 5 & … & 2n−3 & 2n−1 \\ & 3 & 5 & … & 2n−3 \end{aligned} \\ D_{n} & \begin{aligned}1 & 3 & 5 & … & 2n−5 & 2n−3 \\ & & & n−1 \\ & 3 & 5 & … & 2n−5 \end{aligned} \\ E_{6} & 1  4 5  7 8  11 3  5  7  9 6 \\ E_{7} & 1  5 7 9 11 13  17 3 5 7 9 11 13 15 7 9 11 \\ E_{8} & 1  7  11 13  17 19  23  29 3 5 7 9 11 13 15 17 19 21 23 25 27 9 11 13 15 17 19 21 15 \\ F_{4} & 1  5 7  11 3 5 7 9 \\ G_{2} & 1  5 3 \end{matrix}

Table 1: The sequences (ϵ_{i})_{i=1}^{g−1} for the irreducible crystallographic root systems, arranged to illustrate their symmetry, where ϵ_{i+1} = δ_{i} + 1 for 1 ≤ i ≤ g − 2 and ϵ_{1} = 1. The top line for each root system consists of its exponents.

2 Background

2.1 Root systems

Let E be a finite-dimensional vector space with inner product ⟨· , ·⟩ and let α, β ∈ E. The reflection σ_{α} through the hyperplane perpendicular to α sends any vector parallel to α to its negative while leaving any vector perpendicular to α unchanged. By linearity, we see that

σ_{α}(β) = −\frac{⟨α, β⟩}{⟨α, α⟩}α + β − \frac{⟨α, β⟩}{⟨α, α⟩}α = β − 2\frac{⟨α, β⟩}{⟨α, α⟩}α.

Definition 2. A (crystallographic) root system is a finite set Φ ⊆ E of nonzero vectors spanning E such that for α, β ∈ Φ we have

• span(α) ∩ Φ = {α, −α},

• σ_{α}(Φ) = Φ, and

• 2\frac{⟨α,β⟩}{⟨α,α⟩} is an integer.

The Weyl group W associated with a root system Φ is the subgroup of O(E) generated by the reflections σ_{α} for α ∈ Φ.

The condition that 2\frac{⟨α,β⟩}{⟨α,α⟩} is an integer, is the crystallographic condition—it may be restated as “σ_{α}(β) may be obtained from β by adding an integer multiple of α.” A root system is reducible if it is the union of two disjoint root systems, each of which spans one of a pair of orthogonal subspaces of E. Thus, a reducible root system can be viewed as the union of these two independent root systems. A root system which has no such decomposition is called irreducible.

By the well-known classification of irreducible root systems [?], there can be at most two different root lengths. If there are two different lengths, we call the corresponding sets of roots the short roots and long roots. A root system for which there is only one length of roots is called simply laced. The root systems A_{n}, D_{n}, E_{6}, E_{7}, and E_{8} are simply laced, while B_{n}, C_{n}, F_{4}, and G_{2} are not.

Example 3. Let E be the n-dimensional space of vectors in ℝ^{n+1} whose entries sum to zero, and let e_{i} be the standard basis vectors of ℝ^{n+1}. Define α_{i} = e_{i} − e_{i+1}, so that Δ = {α_{1}, α_{2}, …, α_{n}} is a basis for E. This set generates (by reflecting in these roots) the full root system of type A_{n}:

Φ_{A_{n}} = {e_{i} − e_{j} : 1 ≤ i, j ≤ n + 1}.

Reflections in the hyperplane orthogonal to e_{i} − e_{j} exchange the ith and jth coordinates, so that the Weyl group associated with the A_{n} root system is isomorphic to the symmetric group S_{n+1} (acting on E by permuting coordinates).

The root system A_{n} is often the first example of a root system, and combinatorics done in this context is often referred to as “Type A,” in contrast to combinatorics done in the context of general root systems. More precisely, many classical combinatorial objects can be interpreted as arising from the symmetric group or Φ_{A_{n}} in some way, and—once phrased in that language—can often be generalized by passing to other root systems. In this spirit, this paper interprets nesting nonpartitions in the context of type A root systems and extends their definition to other root systems.

2.2 Root posets

By choosing a generic hyperplane in E that does not contain any root, we can divide a root system Φ into positive and negative roots. The roots closest to the hyperplane form a basis for E, which allows us to partially order the positive roots.

Definition 4. A simple system is a subset Δ = {α_{1}, α_{2}, …, α_{n}} ⊆ Φ such that

• the elements of Δ are linearly independent, and

• every element of Φ can be written as a linear combination of elements of Δ, either with all nonnegative or all nonpositive coefficients.

Definition 5. A set of positive roots is a choice of roots Φ^{+} ⊆ Φ such that

• for α ∈ Φ, exactly one of α and −α is in Φ^{+}, and

• if a root is the sum of two roots in Φ^{+}, it is also in Φ^{+}.

We call the roots in the simple system the simple roots. The notions of positive roots and simple systems are closely related. It is easy to see that any choice of a simple system determines a set of positive roots; the roots which can be obtained from a nonnegative linear combination of simple roots may be designated as positive roots, and the rest negative. Conversely, any choice of positive roots uniquely determines a simple system [?, Section 1.3]. In particular, this means that a simple system exists, since we may choose a total order on E that is compatible with the vector space operations (for example, the lexicographic order), and this order determines a positive set and therefore a simple system. Moreover, all simple systems are essentially the same, differing only by the action of the Weyl group [?, Section 1.4]. More precisely, for any two simple systems Δ and Δ′, there is some w ∈ W, the Weyl group of the root system, so that Δ′ = wΔ. Since W ⊆ O(E), the simple systems are orthogonal transformations of each other and have the same geometry. Thus, this choice is immaterial and we will make convenient choices of simple systems.

The choice of positive roots, along with vector space operations, allows us to define a partial order on the positive roots.