Cyclic Sieving for Noncrossing Partitions

Dipartimento di Matematica

Corso di Laurea Magistrale in Matematica

Cyclic Sieving Phenomenon

in Noncrossing Partitions

Tesi di Laurea Magistrale

Candidato

Alessandro Iraci

Relatore

Controrelatore

Prof. Giovanni Gai

Prof. Andrea Maei

Contents

Introduction 7

1 Introduction to cyclic sieving 11

1.1 Foundations . . . 11

1.2 Brute force approach . . . 12

1.2.1 The set {1, . . . , n} . . . 12 1.2.2 Subsets of {1, . . . , n} of cardinality k . . . 13 1.2.3 Multisets on {1, . . . , n} of cardinality k . . . 15 1.3 Algebraic approach . . . 16 1.3.1 Subsets of {1, . . . , n} of cardinality k . . . 16 1.3.2 Multisets on {1, . . . , n} of cardinality k . . . 18

1.4 Representation theory background . . . 20

1.4.1 Irreducible representations of Sn . . . 20

1.4.2 Young tableaux . . . 21

1.4.3 Increasing tableaux . . . 22

1.4.4 Operators on Young tableaux . . . 24

2 Noncrossing partitions 29 2.1 Partitions . . . 29

2.2 Kreweras complement . . . 30

2.3 Instances of cyclic sieving . . . 31

2.4 An action of the symmetric group . . . 33

2.4.1 Skein relations . . . 33

2.4.2 The skein action on V (n) . . . 37

2.5 Noncrossing resolution . . . 46 3

2.6 Representation structure . . . 50

2.7 q-enumerators evaluation . . . 54

2.8 Relations with tableaux . . . 58

2.9 Polygons dissections . . . 60

3 Generalizations of noncrossing partitions 67 3.1 Coxeter groups . . . 67

3.2 Poset structure and noncrossing partitions . . . 69

3.2.1 Word length . . . 69 3.2.2 Noncrossing partitions . . . 70 3.2.3 Catalan numbers . . . 71 3.3 Case A . . . 72 3.4 Case B . . . 73 3.5 Case D . . . 75

3.6 k-divisible noncrossing partitions . . . 76

3.7 Cyclic sieving instances . . . 80

3.8 Cluster complexes . . . 80

List of Figures

2.1 Set partitions . . . 30

2.2 The Kreweras complement . . . 31

2.3 The skein relation . . . 35

2.4 The noncrossing skein relation . . . 36

2.5 The rotation lemma . . . 48

2.6 The sliding corollary . . . 49

2.7 Tableau to NCP . . . 52

2.8 The skein basis element π0. . . 53

3.1 Coxeter diagrams for irreducible Coxeter groups . . . 68

3.2 Type B noncrossing partitions . . . 75

3.3 The type B Kreweras complement . . . 75

3.4 Type D noncrossing partitions . . . 76

3.5 The Hasse diagram of the poset NC(2)_{(3). . . 78}

3.6 A 3-divisible noncrossing partition of type D4. . . 79

Introduction

Purpose of this thesis is to introduce the cyclic sieving phenomenon and discuss in detail an instance of cyclic sieving in noncrossing partitions.

Let X be a nite set, let C = hci a nite cyclic group acting on X, and let ζ ∈ C be a root of unit having the same multiplicative order as c. Let X(q) ∈ Z[q] be a polynomial with nonnegative integer coecients. Then the triple (X, C, X(q)) is said to exhibit the cyclic sieving phenomenon (or CSP) if, for every integer d, #Xcd

= X(ζd_{). The cyclic sieving phenomenon was rst introduced by V.}

Reiner, D. Stanton, and D. White in 2004 and, since then, it has been ubiquitous in combinatorics.

The point of this denition is that the polynomial X(q) should be somehow naturally associated to the set X. This is done via q-analogs or statistics. We dene the q-analog of a positive integer n as [n]q = 1 + q +· · · + qn−1. It

is a polynomial with nonnegative integer coecients such that [n]1 = n. We

dene the q-factorial as product of q-analogs, and then the q-binomial in the natural way. It happens surprisingly often that, for a set X enumerated by an expression which is product of binomials on which we have a natural action of a cyclic group C, the triple (X, C, X(q)) exhibits the cyclic sieving phenomenon when X(q) is the q-analog of the enumerator for X.

In this thesis we focus on some instances of cyclic sieving in noncrossing par-titions. A partition of [n] := {1, . . . , n} is a collection of disjoint subsets such that the union covers [n]. A partition is said noncrossing if, drawing n points on a circle and labeling them clockwise from 1 to n, the convex hulls of vertices that are in the same set of the partition do not intersect each other. In the fol-lowing picture, the partition {{1, 2, 4}, {3, 5}, {6}} on the left is crossing, while the partition {{1, 6}, {2, 4, 5}, {3}} on the right is noncrossing.

1 2 4 3 5 6 6 1 2 4 5 3

Noncrossing partitions are enumerated by Catalan numbers. For a xed num-7

ber of blocks, they are enumerated by Narayana numbers. Noncrossing parti-tions with a xed number of blocks, all of size at least two, are enumerated by Kirkman-Cayley numbers. On noncrossing partitions we have a natural action of the cyclic group by rotation. It happens that all the sets described above exhibit the cyclic sieving phenomenon for this action, with the q-analogs of the just mentioned enumerators.

This result is absolutely not trivial, and it's related to various other topics. We denote as NC(n, k, s) the set of noncrossing partitions of [n] with a xed number k of blocks and exactly s singletons (blocks of size one). It happens that there is a bijection between the set NC(n, k, 0), the set SYT(k, k, 1n−2k_)of

standard Young tableaux of shape (k, k, 1n−2k_{), and the set Inc}

n(n−k, n−k) of

increasing tableaux of shape (n−k, n−k) with n as xed maximum entry. This bijection can be described explicitly, and it maps the counterclockwise rotation on NC(n, k, 0) into the K-promotion operator on Incn(n− k, n − k), so we also

have an instance of cyclic sieving for this set.

The cyclic sieving instance for noncrossing partitions was proved by O. Pechenik in 2013 by brute force enumeration. In 2015, B. Rhoades gave an action of Sn

on the vector space V (n) spanned by noncrossing partitions, so that the element (1, 2, . . . , n)acts by clockwise rotation. He then used representation theoretical tools to prove the instance of cyclic sieving. The core of his work was giving a way to "resolve" a generic partition as linear combination of noncrossing ones. In this thesis, we use a slightly modied resolution, so that the action of Sn is

exactly the signed permutation action.

We have that, up to ltrations and quotients, the vector space spanned by NC(n, k, 0) is an irreducible representation of Sn isomorphic to S(k,k,1

n−2k₎

, which is the vector space spanned by SYT(k, k, 1n−2k_{), so we can completely}

describe the Sn-module structure of V (n).

Our instance of cyclic sieving on noncrossing partitions have several possible insights.

The last chapter is a small survey about possible generalizations of noncrossing partitions. If we view Sn as complex reection group, we could dene a partial

ordering on it using lenghts of elements. Then NC(n) could be seen as the poset of elements that are lesser than or equal to a xed Coxeter element. This allows us to generalize the denition of noncrossing partitions to other reection groups. In this thesis, we'll look at the "type B" noncrossing partitions, with Bn

as reection group. They can be represented as noncrossing partitions on [2n] invariant with respect to the antipodal map, and also exhibit the cyclic sieving phenomenon with the rotation action of the cyclic group. Some instances were proved only by brute force enumeration by D. Bessis and V. Reiner in 2011, and then the result was rened by V. Reiner and E. Sommers in 2016. There is expected to be a representation theoretic proof too, but it's still to be found. We previously said that NC(n, k, 0) is enumerated by the Kirkman-Cayley num-ber. The same enumerator (and his q-analog) give an instance of cyclic sieving

for the action of another cyclic group on dissections of regular n − k + 2-agons with k −1 noncrossing diagonals. Kirkman-Cayley numbers also count the faces of some associahedra and several other objects, and moreover they are related to some problems about conguration spaces. At the moment it seems that there's no common approach to these problems, but it would be interesting to nd one.

Chapter 1

Introduction to cyclic sieving

1.1 Foundations

Let X be a nite set, let C = hci a nite cyclic group acting on X, and let ζ ∈ C be a root of unit having the same multiplicative order as c. Let X(q) ∈ Z[q] be a polynomial with nonnegative integer coecients.

Denition 1.1. The triple (X, C, X(q)) is said to exhibit the cyclic sieving phenomenon (or CSP) if, for every integer d,

#Xcd

= X(ζd_).

The cyclic sieving phenomenon was rst introduced by V. Reiner, D. Stanton, and D. White [18] in 2004.

Of course it's always possible, given a cyclic group C acting on a set X, to nd a polynomial X(q) that satises the cyclic sieving condition. Furthermore, via representation theoretic tools, one can show that such a polynomial can be taken with nonnegative integer coecients. The point of this denition is that the polynomial X(q) should be somehow naturally associated to the set X. Given a set of combinatorial objects, there are several ways to construct a polynomial associated with it. The most widespread involves q-analogs. Denition 1.2. A q-analog of an expression is any generalization involving a new parameter q that returns the original expression in the limit as q → 1. q-analogs are based on the fact that

lim

q→1

1_{− q}α

1− q = α

so, given n ∈ N, we dene a q-analog for it as [n]q = 1 + q +· · · + qn−1, which

is a polynomial with integer nonnegative coecients. 11

Despite this choice seems to be arbitrary, it arises spontaneously in several contexts. It also allows for a natural denition of q-factorial and q-binomial. Namely, given n, k ∈ N, we dene their q-factorial and q-binomial as

[n]q! = [n]q[n− 1]q. . . [1]q and n k  q = [n]q! [k]q![n− k]q! .

It's not hard to prove that the q-binomial is a polynomial with nonnegative in-teger coecients. This might not be true if we choose some dierent polynomial with nonnegative integer coecients as q-analog of a natural number.

Remark 1.3. If (X, C, X(q)) exhibits the cyclic sieving, then X(1) = #X, so X(1)is an enumerator for X. It follows that X(q) is a q-analog of an enumerator for the set X.

Another possibility to construct polynomials involves statistics. Denition 1.4. A statistic on a set X is a function s: X → N.

If X is a set of combinatorial objects, then there might be a natural statistic s on X which assume the same value at objects with the same combinatorial properties. Therefore, we may dene the polynomial

X(q) = X

x∈X

qs(x)

which is obviously a q-analog of an enumerator for the set X. This polynomial is said to be the generating funcion for the statistic s on the set X.

Although there's no theoretical reason to think that q-analogs and cyclic sieving are strictly related, there's a practical one: if X is a set of combinatorial objects with a natural action of some cyclic group C, and a natural q-enumerator X(q), then the triple (X, C, X(q)) has an uncanny tendency to exhibit the cyclic siev-ing phenomenon, and very often there's also some natural statistic s on X with X(q)as generating function.

1.2 Brute force approach

1.2.1 The set {1, . . . , n}

The most straightforward approach to prove that a given triple (X, C, X(q)) exhibits the CSP is by brute force evaluation. If the action of C on X is simple enough, one may directly compute the cardinalities of the xed point set Xcd

. Moreover, if it is also possible to evaluate the q-enumerator at the roots of unit, one can show that

#Xcd

= X(ζd_).

The following is a very simple instance of cyclic sieving, whose proof is totally straightforward.

Theorem 1.5. Let X = C = Cn be the cyclic group on n elements acting on

itself by permutation. Then the triple

(Cn, Cn, [n]q)

exhibits the cyclic sieving phenomenon.

Proof. The cardinality of the xed point set Xc _{is n if c = e, and 0 otherwise.}

The polynomial evaluation [n]ζ is n if ζ = 1, and 0 if ζ is a n-th root of unit

other than 1, so the CSP holds.

1.2.2 Subsets of {1, . . . , n} of cardinality k

Let's now introduce some notation. Let X be a set. Then we dene X

k 

:= {S ⊆ X | #S = k}.

We will now prove an instance of CSP for the set X = [n] k

_{, where [n] :=} {1, . . . , n}.

The group Sn acts naturally on {1, . . . , n}. This induces an action on X in this

way: if S = {i1, . . . , ik} then σS = {σ(i1), . . . , σ(ik)}. We may now take the

cyclic group generated by an n-cycle: take c = (1, . . . , n) and C = hci. We only need a q-enumerator for X. An obvious choice is X(q) = n

k



q.

Now we are ready to state our rst real cyclic sieving theorem, which is a special case of a more general result proved by Reiner, Stanton and White in their paper.

Theorem 1.6. The triple [n] k  ,h(1, . . . , n)i,n_k  q !

exhibits the cyclic sieving phenomenon.

Let's start by counting xed points. We need a lemma.

Lemma 1.7. Let σ ∈ Sn, S ⊆ [n]. Then σS = S if and only if S is a disjoint

union of cycles of σ.

Proof. If S is a disjoint union of cycles of σ, then clearly σS = S. Conversely, if S is not a disjoint union of cycles of σ, then there must be some cycle τ of σ, and some i, j ∈ [n] such that i ∈ S, j 6∈ S and τ(i) = j, so σS 6= S.

Corollary 1.8. If g ∈ C is such that ord(g) = d, then #Xg₌      n/d k/d  if d | k 0 otherwise.

Proof. Since g is a power of (1, . . . , n) of order d, then g's disjoint cycle decom-position consist of n/d cycles of length d. If d - k, then no subset of k elements can be a disjoint union of cycles of g, so there are no xed points. If d | k, then the xed points are the sets obtained by choosing k/d of the n/d cycles of g, which can be done in the number of ways stated above.

We now have to evaluate X(ζd), where ζd is a root of unit of order d. The

following lemma will be useful.

Lemma 1.9. Let m ≡ n (mod d), and let ζ = ζd. Then

[m]ζ [n]ζ =    m n if m ≡ n ≡ 0 (mod d) 1 otherwise.

Proof. Let m ≡ n ≡ r (mod d), with 0 ≤ r < d. Since 1+ζ+ζ2₊

· · ·+ζd−1_{= 0,}

we may delete any d consecutive terms in 1 + ζ + · · · + ζm−1 _{(or ζ}n−1_{), so}

[m]ζ = [n]ζ = 1 + ζ + ζ2+· · · + ζr−1.

It follows that if r 6= 0 then [m]ζ = [n]ζ = r, as desired.

Suppose r = 0. Then we can write n = hd and m = kd. Hence we have [m]q [n]q = (1 + q +· · · + q d−1_{)(1 + q}d₊ · · · + qd(k−1)₎ (1 + q +· · · + qd−1_{)(1 + q}d_{+· · · + q}d(h−1)₎

so canceling the 1 + q + · · · + qd−1 _{factor and recalling that ζ}d_{= 1, we have}

[m]ζ [n]ζ = k h = m n as desired.

Corollary 1.10. If ζ = ζdand d | n, then

n k  ζ =      n/d k/d  if d | k 0 otherwise.

Proof. In the equality above, consider the numerator and denominator of the LHS after canceling factorials. Since d | n, the product [n]ζ[n−1]ζ· · · [n−k+1]ζ

starts with a zero factor and has another zero exactly every d factors; the product [1]ζ[2]ζ· · · [k]ζ starts with d − 1 nonzero factors, and then has a zero every d

factors.

Since the number of factors is the same, it follows that the numerator has always at least as zero factors as the denominator, with equality if and only if d | k.

It follows that if d - k, the equality holds. If d | k we have n k  ζ = [n− k + 1]ζ [1]ζ · [n− k + 2]ζ [2]ζ · · · · · [n]ζ [k]ζ = 1_{· · · 1 ·}n− k + d d + 1· · · 1 · n_{− k + 2d} 2d · 1 · · · · n k = n/d− k/d + 1 1 · n/d− k/d + 2 2 · · · n/d k/d =n/d k/d  as desired.

Proof of Theorem 1.6. The thesis immediately follows comparing Corollary 1.8 and Corollary 1.10.

1.2.3 Multisets on {1, . . . , n} of cardinality k

With a similar argument, we can prove another instance of cyclic sieving. We have to introduce some concepts.

Denition 1.11. Let X be a set. A multiset on X in an unordered family M of elements of X, counted with multiplicity.

We write M v X to say that M is a multiset on X. A multiset may be explicitly listed as M = {xm(x)

| x ∈ X}, where x may be omitted if m(x) = 0. We also dene the cardinality of a multiset to be #M = P_x∈Xm(x).

For example, {12_{, 2}3_{, 4} } is a multiset on {1, 2, 3, 4} of cardinality 6. We dene _ X k  := {M v X | #M = k} to be the set of multisets on X of cardinality k.

Let's build the triple. Similarly as we did in the previous subsection, we take X = [n]_k

. The action of Sn on {1, . . . , n} induce an action on X exactly as it

did before. We also take C = h(1, . . . , n)i.

Now we need a q-enumerator for X. Since it's well known that # _[n] k  =n + k− 1 k  , the obvious choice is

n + k_{− 1} k



q

Theorem 1.12. The triple _[n] k  ,_{h(1, . . . , n)i,}n + k− 1 k  q !

exhibits the cyclic sieving phenomenon.

We omit the proof since it's analog to the previous one. The only dierence is that in Lemma 1.8, the cycles of which M should be a disjoint union need not to be distinct.

1.3 Algebraic approach

The other major approach used to prove that a triple (X, C, X(q)) exhibits the cyclic sieving phenomenon is algebraic, and it involves representation theory. Such kind of proofs tend to be more elegant, and they also give an insight into why a given triple should exhibit the CSP. Conversely, an instance of CSP may suggest various new results in representation theory.

In order to prove that a given triple (X, C, X(q)) exhibits the CSP via repre-sentation theory, we have to nd a vector space V with a distinguished basis B = {ex | x ∈ X} and a group G which acts on V . We also need an element

g _{∈ G whose action on V can be easily described in terms of the basis B and} the group C = hci.

For instance, if for every x ∈ X we have g · ex= ecx, then if χ: G → C is the

character of the G-module V , for every d ∈ Z we have #Xcd

= χ(gd_{). One}

then only needs to show that X(ζd_{) = χ(g}d_{), and this can be done using several}

tools from algebra.

However, things are not always that simple. For example, it could be possible only to show that g·ex= γecxfor some γ ∈ C, or even worse, that g·ex= γ(x)ecx

for some function γ : X → C. In these cases, if γ is simple enough, this algebraic approach may work anyhow.

We will now show an algebraic proof of the cyclic sieving instances we showed in the previous section.

1.3.1 Subsets of {1, . . . , n} of cardinality k

Let us restate the theorem. Theorem 1.6. The triple

[n] k  ,h(1, . . . , n)i,n_k  q !

At rst we need a vector space with a basis indexed by X = [n] k

. A quite natural choice is V = Λk

C[n], because not only it has the right dimension as C-vector space, but it also has a basisB = {eS | S ∈ X} indexed by X, where

eS =

^

i∈S

ei.

Remark 1.13. If M is a G-module, then Λk_{M is also a G-module, with the}

action dened by

g(v1∧ · · · ∧ vk) = g(v1)∧ · · · ∧ g(vk)

extended by linearity.

So our vector space V is a Sn module.

Let χ = χV. At rst we want to evaluate χ(cd), where c = (1, . . . , n). Since c

has order n, we know that its eigenvalues on C[n] are ζ, ζ2_{, . . . , ζ}n−1_{, 1. Now,}

let v1, . . . , vn be a basis of C[n] of eigenvectors for c. Then {vS | S ∈ X}, where

vS =

^

i∈S

vi,

is a basis of V of eigenvectors for c. The corresponding eigenvalues are ζΣS_,

where ΣS = P_i∈Si, therefore we have χ(cd) = X

S∈X

ζd(ΣS).

Now we need an important theorem about q-analogs.

Theorem 1.14 (The q-binomial Theorem). For all n ≥ 1 we have

n Y j=1 (1 + xqj) = n X k=0 q(k+12 )n k  q xk.

thesis holds for n. We have n+1 Y j=1 (1 + xqj) = (1 + xqn+1)· n Y j=1 (1 + xqj) = (1 + xqn+1)· n X k=0 q(k+12 )n k  q xk = n+1 X k=0 q(k+12 )n k  q + q(k2)+n+1  _n k_{− 1}  q ! xk = n+1 X k=0 q(k+12 ) n k  q + qn−k+1  _n k− 1  q ! xk = n+1 X k=0 q(k+12 )n + 1 k  q xk which is the formula for n + 1, so the thesis follows. The coecient of xk _{in the LHS is exactly P}

S∈XqΣS. It follows that

χ(cd_{) = ζ(}k+1₂ )n

k 

ζd

so we need to prove that, if cd_{S = S, then c}d

· eS = ζd(

k+1 2 )e

S. If this statement

holds, in fact, then ζ−d(k+1

2 )χ(cd) = #Xcd, because the trace is invariant by base

change. Since it agrees with the q-binomial evaluation, the thesis will follow. Let cd_{S = S. Then c}d _{is a product of d cycles of length r = n/d, and S is a}

disjoint union of b of these cycles, with k = br. We have cd

· eS = (−1)b(r−1)eS,

so we have to prove that (−1)b(r−1)_{= ζ}d₍k+1

2 ). It holds (xr− 1)b₌ k Y i=1 (x− ζdi₎

so, evaluating in x = 0, we have (−1)b _{= (}

−1)k_ζd₍k+1

2 ), and the thesis follows

immediately.

Notice that we also proved that, if s: X → N is the statistic given by s(S) = ΣS₋ k+1_{2
, which is the sum of its elements adjusted so that the subset with} smallest sum gives zero, then X(q) = PS∈Xqs(S), as we stated in the

founda-tions secfounda-tions.

1.3.2 Multisets on {1, . . . , n} of cardinality k

Theorem 1.12. The triple _[n] k  ,_{h(1, . . . , n)i,}n + k− 1 k  q !

exhibits the cyclic sieving phenomenon.

The idea to prove this via representation theory is very similar to the one for subsets. Let X = [n]

k

. As our vector space, we pick V = Sn

C[n], with the basis B = {eS| M ∈ X} indexed by X, where

eM =

O

i∈M

ei.

It is pretty obvious that, for σ ∈ Sn, σ · eM = eσM, so if χ = χV, then

χ(cd_{) = #X}cd

.

We need to prove that χ(cd_{) =}_n+k−1

k  ζd. Let hk(x1, . . . , xn) = X 1≤i1≤···≤ik≤n xi1xi2· · · xik.

Lemma 1.15. For n ≥ 1, k ≥ 0 we have hk(1, q . . . , qn−1) = n + k_{− 1} k  q .

Proof. Given that the equality holds for n = 1 and k = 0, we can prove the thesis by double induction. Assume both n ≥ 2 and k ≥ 1. By splitting the sum for hk(x1, . . . , xn)by isolating terms that contain xn, we have

hk(x1, . . . , xn) = hk(x1, . . . , xn−1) + xnhk−1(x1, . . . , xn−1).

Furthermore, it is well known that n k  q =n− 1 k  q + qn−kn− 1 k_{− 1}  q

hence specializing the rst recurrence for xi = qi−1 and substituting n with

n + k_{− 1 in the second, it follows that the two sides of the equality satisfy the} same recurrence, so they must coincide.

Now we must only show that χ(cd_{) = h}

k(ζd, ζ2d, . . . , ζd(n−1)), but this is obvious

taking a basis of C[n] of eigenvectors for c, looking at its eigenvalues, and then noticing that V has a basis whose eigenvalues for c are products of eigenvalues for c in C[n] indexed by k-multisets on [n], so the thesis follows immediately.

1.4 Representation theory background

In this section we'll introduce some results of representation theory, focusing on representations of the symmetric group Sn. We omit some proofs: the interested

reader may nd them in [10].

1.4.1 Irreducible representations of S

n

Denition 1.16. A partition of n is a weakly increasing sequence of positive integers λ = (λ1, λ2, . . . , λk)such that λ1+ λ2+· · · + λk = n. We write λ ` n

to mean that λ is a partition of n.

On partitions of n we have a natural involution dened as follows.

Denition 1.17. Given λ = (λ1, λ2, . . . , λk) ` n, we dene its conjugate (or

transpose) λ0_{= (λ}0

1, λ02, . . . , λ0h)by λ0i:= #{j | λj ≥ i}.

We may associate a partition λ ` n to a Ferrers diagram, which consists of a table with λi left justied boxes in row i.

Example 1.18. The Ferrers diagram of λ = (4, 4, 2, 1) ` 11 on the left, and its transpose λ0_{= (4, 3, 2, 2)on the right.}

Denition 1.19. We dene the dominance order on partitions of n declaring µ_{ λ if for all i we have µ}1+ µ2+· · · + µi≤ λ1+ λ2+· · · + λ1.

Denition 1.20. Given λ ` n, we dene the Young subgroup Sλ≤ Sn as

Sλ:= S{1,...,λ1}× S{λ1+1,...,λ1+λ2}× · · · × S{n−λk+1,...,n}.

We now consider the group algebra Q[Sn]. Our goal is to build irreducible

Q[Sn]-modules indexed by partitions λ ` n. Given λ ` n, we dene

aλ:= X s∈Sλ s, bλ:= X t∈Sλ0 sign(t)t, and cλ= bλaλ.

Remark 1.21. Notice that aλ=Qki=1aλi, where aλi is the sum of the elements

in Sλthat x everything but the row i. The analog factorization holds for bλ.

Moreover, if t ∈ Sλ is a transposition, then there exist at and bt such that

Theorem 1.22. The Q[Sn]-module Sλ = Q[Sn]cλ is irreducible. Moreover,

if λ 6= µ then Sλ

6∼ =Sn S

µ_{, and if V is any irreducible Q[S}

n]-module, then

V ∼=Sn S

λ _{for some λ ` n.}

Proposition 1.23. For any λ ` n, we have cλ2= (n!/ dim Sλ)· cλ.

The fact that a scalar multiple of cλis idempotent implies that Sλis irreducible,

and viceversa.

Lemma 1.24. Let λ, µ ` n. We have that aλSµ 6= 0 =⇒ λ  µ, and also

bλSµ6= 0 =⇒ µ  λ.

1.4.2 Young tableaux

Denition 1.25. Given a partition λ ` n, a Young tableau of shape λ is a bijective lling T : λ → [n] of the boxes of the Ferrers diagram of λ with the numbers 1, 2, . . . , n.

A tableau is told to be standard if its entries are strictly increasing down columns and across rows.

We denote with SYT(λ) the set of standard tableaux of shape λ. In this set, we dene the superstandard Young tableau to be the element Tλ such that the

image of each row is an interval. The superstandard Young tableau of shape λ is traditionally denoted by SSY T (λ), but I prefer the shorter expression Tλ.

Example 1.26. Let λ = (4, 4, 2, 1) ` 11. Then Tλ is the following tableau.

1 2 3 4 5 6 7 8 9 10 11

Given T a Young tableau of shape λ and s ∈ Sn, we dene sT := s ◦ T , so that

an entry of sT is i if and only if the corresponding entry of T is s−1_{(i). We will}

denote as T0 _{the transpose of T , dened in the obvious way.}

Next, we dene σT ∈ Sn to be the element such that σTTλ = T. We also

dene RT := σTSλσT−1 < Sn to be the subgroup that xes the rows of T , and

CT := RT0 to be the subgroup that xes the columns of T .

We nally dene aT := X s∈RT s and bT := X t∈CT sign(t)t.

Proposition 1.27. The set {T | T ∈ SYT(λ)} is a basis for Sλ, where

T :=

X

s∈CT

It follows that the dimension of Sλ _{as Q-vector space is exactly # SYT(λ). We}

now want to compute this dimension. Let (i, j) be a cell of the Ferrers diagram associated to λ. The hook Hλ(i, j)is the set of those cells (a, b) such that a = i

and b ≥ j, or a ≥ i and b = j. Let hλ(i, j) = #Hλ(i, j).

Theorem 1.28 (Hook length formula). For any λ ` n, we have # SYT(λ) = Q n!

i,jhλ(i, j)

.

This formula has a q-analog obtained by replacing n! with [n]q!and each hλ(i, j)

with [hλ(i, j)]q. There's no need to say that it will be a q-enumerator for an

instance of cyclic sieving, later.

Example 1.29. The following is the Ferrers diagram for λ = (4, 4, 2, 1), with each box lled with its hook length.

7 5 3 2 6 4 2 1 3 1 1

The construction of Sλ _{could be made in a dierent way.}

Denition 1.30. A tabloid is an equivalence class of Young tableaux, two being equivalent if their rows have the same entries.

We denote the equivalence class of a tableau T as [T ]. Notice that the group Sn acts on tabloids as s[T ] = [sT ], and the orbit of [T ] is isomorphic to Sn/RT

as a set with Sn-action.

Given a Young tableau T , the element aT previously dened depends only on

the class [T ], and the same does T. If we dene

0T :=

X

s∈CT

sign(s)[sT ] and take the Q-span of the set {0

T | T ∈ SYT(λ)} with the Sn-action previously

dened, we get a Sn-module isomorphic to Sλ.

1.4.3 Increasing tableaux

We could generalize the denition of Young tableau in several ways. For our purposes, we only need the following.

Denition 1.31. Given a partition λ ` n, an increasing tableau of shape λ is a surjective lling T : λ → [k] (for some k) of the boxes of the Ferrers diagram of λwith the numbers 1, 2, . . . , k, such that its entries are strictly increasing down columns and across rows.

We denote with Inck(λ)the set of increasing tableaux of shape λ and maximum

entry k. Notice that, if λ ` n, then Incn(λ) = SYT(λ).

The following proposition seems to have no point, but it will be back into play later.

Proposition 1.32. There is a bijective map between SYT(k, k, 1n−2k_{) and}

Incn(n− k, n − k).

Proof. One could simply count these sets and see that cardinalities agree, but we'll give an explicit bijection instead.

Let S ∈ SYT(λ). We build an increasing tableau T ∈ Incn(n− k, n − k) in the

following way.

The second row of T is made by the elements in [n] which do not appear in the rst row of S, arranged in the only way such that they're increasing. The rst row is made by the elements of the rst row of S, plus the elements in the second row of T such that the element at their immediate right was not in the rst two rows of S, once again arranged in the only possible way (see the example below). By construction, the rows are increasing, the shape is (n − k, n − k) and the maximum entry is n. We only need to prove that columns are increasing too, but it follows from the fact that S is standard.

Viceversa, let T ∈ Incn(n− k, n − k). We build a standard tableau S ∈ SYT(λ)

in the following way.

At rst, we remove from the rst row of T all the elements that also appear in its second row. Then, we remove from the second row of T the elements at the immediate right of those that we removed before. Finally, we add in these elements to the rst column, so that it's increasing. By construction, S_{∈ SYT(λ).}

It is obvious that these two constructions are inverse each other, so the thesis follows.

Notice that, for n = 2k, the sets SYT(λ) and Incn(n− k, n − k) coincide, and

Example 1.33. Consider the standard tableau 1 3 7 2 5 8 4 6

and build the corresponding increasing tableau. 1 3 7

2 5 8 4 6

→ 1 3 7_{2 4 5 6 8 →} 1 3 7_{2 4 5 6 8 →} 1 2 3 5 7_{2 4 5 6 8}

Then, consider the increasing tableau

1 2 3 5 7 2 4 5 6 8 and reverse the construction.

1 2 3 5 7 2 4 5 6 8 → 1 3 7 2 4 5 6 8 → 1 3 7 2 4 5 6 8 → 1 3 7 2 5 8 4 6 As predicted, we got the starting standard tableau.

1.4.4 Operators on Young tableaux

Denition 1.34. The Jeu-de-taquin promotion operator j : SYT(λ) → SYT(λ) is dened in the following way.

Let λ ` n, and let T ∈ SYT(λ). Replace 1 with a hole. Then, if there's a hole in position (i, j), look whichever between the boxes (i, j + 1) and (i + 1, j) has the lower value (if any of these exists), and then switch the hole with that value. Repeat until the hole gets in a corner (so none between the boxes (i, j + 1) and (i + 1, j) exist), replace the hole with n + 1, and then lower all the entries by one.

This operator is related to the structure of the cohomology ring of the Grass-mannian, but we won't go any further in this direction.

Before showing an example of jeu-de-taquin promotion, we will dene a gener-alization. The operator j extends to a K-promotion operator jK := Inck(λ)→

Inck(λ) which, as the name suggests, is related to the K-theory of the

jK is dened exactly as j, with the following exception: whenever the boxes

(i, j + 1) and (i + 1, j) have the same value, replace the hole with that value, and then replace both with a hole. If at any moment there is more than a hole, act on all of them simultaneously (it's easy to check that if (i, j) contains a hole, neither (i, j + 1) nor (i + 1, j) can).

It's easy to check that jK specializes to j if k = n.

Example 1.35. Let T ∈ Inc7(4, 4, 3)be the following increasing tableau.

1 2 3 5 2 3 4 7 5 6 7 Let's compute jK(T ). 1 2 3 5 2 3 4 7 5 6 7 → • 2 3 52 3 4 7 5 6 7 → 2 _{• 3 5} • 3 4 7 5 6 7 → 2 3 _{• 5} 3 • 4 7 5 6 7 → 2 3 4 5 3 4 • 7 5 6 7 → 2 3 4 5 3 4 7 • 5 6 _• → 2 3 4 5 3 4 7 8 5 6 8 → 1 2 3 4 2 3 6 7 4 5 7

It is not known what the order of the operator jK is, in general. However, there

are some positive results, as the following.

Proposition 1.36. For any T ∈ Incn(n− k, n − k), we have jKn(T ) = T.

In fact, we have a stronger result. Theorem 1.37. The triple

(Incn(n− k, n − k), hjKi, X(q))

exhibits the cyclic sieving phenomenon, where X(q) is the q-hook length formula for tableaux of shape (k, k, 1n−2k_).

We will prove this theorem later, as a corollary of another instance of cyclic sieving.

Denition 1.38. The Schützenberger involution S : SYT(λ) → SYT(λ) is an operator on Young tableaux dened as following.

Let λ ` n, and let T ∈ SYT(λ). Apply the jeu-de-taquin algorithm on T , but stop when the hole gets in a corner. Replace the hole with a redn. Decrease all

the black entries by 1. Repeat the process on the tableau composed by black entries only, completely ignoring red ones, until there are no more black entries. S(T ) is the resulting tableau with red entries.

The operator S could be extended to the K-evacuation operator SK: Inck(λ)→

Inck(λ), using jK instead of j to compute it. The reader will be glad to know

that there's a reason because this operator is called Schützenberger involution. Proposition 1.39. For each T ∈ Inck(λ), S2(T ) = T.

A proof of this fact can be found in [25], using the K-growth diagrams of these tableaux.

Example 1.40. Let T ∈ Inc7(4, 4, 3) be the following increasing tableau.

1 2 3 5 2 3 4 7 5 6 7 Let's compute SK(T ). 1 2 3 5 2 3 4 7 5 6 7 → 1 2 3 4 2 3 6 7 4 5 7 → 1 2 3 6 2 4 5 7 3 6 7 → 1 2 4 6 2 3 5 7 5 6 7 → 1 2 3 6 2 4 5 7 5 6 7 → 1 2 3 6 3 4 5 7 5 6 7 → 1 2 3 6 3 4 5 7 5 6 7 → 1 2 3 6 3 4 5 7 5 6 7 Now, we apply SK to SK(T ). 1 2 3 6 3 4 5 7 5 6 7 → 1 2 4 5 2 3 6 7 4 5 7 → 1 2 3 4 2 4 5 7 3 6 7 → 1 2 3 5 2 3 4 7 5 6 7 → 1 2 3 5 2 3 4 7 5 6 7 → 1 2 3 5 2 3 4 7 5 6 7 → 1 2 3 5 2 3 4 7 5 6 7 → 1 2 3 5 2 3 4 7 5 6 7 We got T , as expected.

Remark 1.41. For increasing tableaux in Incn(n− k, n − k) this involution can

be easily evaluated by rotating the tableau upside down and replacing each occurence of the entry i with n+1−i. Moreover, the bijection described in 1.32 commutes with the Schützenberger involution (but it does not commute with the jeu-de-taquin promotion).

Example 1.42. Consider the increasing tableau 1 2 3 5 7 2 4 5 6 8

Applying SK, we get 1 2 3 5 7 2 4 5 6 8 → 1 2 4 5 6 3 4 5 7 8 → 1 3 4 5 7 2 4 6 7 8 → 1 2 3 4 7 3 5 6 7 8 → _{2 4}1 2 3_{6 7 8}5 7 → ₃1 2_{4 6 7 8}4 5 7 → 1₂ 3 4 5 7_{4 6 7 8} → 1_{2 4 6 7 8}3 4 5 7

and nally get as result

1 3 4 5 7 2 4 6 7 8

Chapter 2

Noncrossing partitions

In this chapter we'll show an algebraic proof of an instance of cyclic sieving phe-nomenon for an action of the cyclic group of n elements on the set of noncrossing partitions of [n] := {1, . . . , n}.

2.1 Partitions

Denition 2.1. A partition of a set X is a set π = {Xα | α ∈ A} such that

Xα6= ∅, Xα⊆ X for all α ∈ A, Xα∩ Xβ=∅ for all α 6= β and

[

α∈A

Xα= X.

Elements of a partition π are said to be blocks. Elements in the same block are called blockmates. If a block has only one element, it's said to be a singleton. Note. We have now two concepts of partition, one dened as collection of subsets and one dened as weakly decreasing sequence of integers.

We may disambiguate using the expressions set partitions for the former and partitions of n for the latter, but sometimes we won't. However, the intended meaning should always be clear from the context.

In this chapter, we focus on set partitions of [n] := {1, . . . , n}.

Let n, k, s ≥ 0. We dene three collections of set partitions as follows. Π(n) :=_{{π ⊆ P([n]) | π partition of [n]},}

Π(n, k) :={π ∈ Π(n) | π has k blocks}, Π(n, k, s) :=_{{π ∈ Π(n, k) | π has s singletons}.}

Moreover, we have the disjoint union decompositions Π(n) = G k≤n Π(n, k) and Π(n, k) = G s≤k Π(n, k, s).

There is a convenient way to represent a partition π ∈ Π(n) on a disk, as follows. Draw n points on a circumference, label them clockwise, and then highlight the polygons whose vertices are labeled with elements in the same block of π. Example 2.2. Take, as an example, the partitions {{1, 2, 4}, {3, 5}, {6}} and {{1, 6}, {2, 4, 5}, {3}} in Π(6). These are represented below.

Figure 2.1: A crossing partition (left) and a noncrossing one (right).

1 2 4 3 5 6 6 1 2 4 5 3

Given π ∈ Π(n), let us denote as Bi(π)the block of π such that i ∈ Bi(π).

Denition 2.3. A partition π ∈ Π(n) is called noncrossing if, whenever we have 1 ≤ a < b < c < d ≤ n, then

Ba(π) = Bc(π), Bb(π) = Bd(π) =⇒ Ba(π) = Bb(π) = Bc(π) = Bd(π).

It's pretty easy to check that a partition is noncrossing if and only if its blocks do not intersect when represented on a disk (so the naming makes some sense). In example 2.2, the partition on the left is crossing, while the one on the right is noncrossing.

Let n, k, s ≥ 0. We dene three collections of set partitions as follows. NC(n) :=_{{π ∈ Π(n) | π is noncrossing},}

NC(n, k) :={π ∈ NC(n) | π has k blocks}, NC(n, k, s) :=_{{π ∈ NC(n, k) | π has s singletons}.} And once again, we have the disjoint union decompositions

NC(n) = G k≤n NC(n, k) and NC(n, k) = G s≤k NC(n, k, s).

2.2 Kreweras complement

Denition 2.4. Given π, π0 _{∈ NC(n), we say that π  π}0 _{if for each B ∈ π}

there exists B0_{∈ π}0 _{such that B ⊆ B}0_.

We could use this ordering to dene an operator on noncrossing partitions. Denition 2.5. Kreweras complement is an operator Kr: NC(n) → NC(n) dened as follows.

Given π ∈ NC(n), relabel the elements 1, . . . , n as 1, 3, . . . , 2n − 1. We get a noncrossing partition π0 _{∈ NC({1, 3, . . . , 2n − 1}) ,→ NC(2n). We dene}

π00∈ NC({2, 4, . . . , 2n}) ,→ NC(2n) as the coarsest element such that π0_{∪ π}00_∈

NC(2n). By construction, the vertices of π00 _{are all even, so we can relabel the}

elements 2, . . . , 2n as 1, . . . , n and dene Kr(π) := {B ⊆ [n] | 2B ∈ π00_}.

Figure 2.2: The Kreweras complement

1 8 12 2 3 5 6 4 7 9 11 10

→

1 15 23 3 5 9 11 7 13 17 21 19 2 4 12 14 6 8 10 16 22 18 20 24

→

1 2 6 7 3 4 5 8 11 9 10 12

Proposition 2.6. The operator Kr is bijective, it reverses the ordering, and #π + # Kr(π) = n + 1. Moreover, Kr2_{= c−1, where c is the clockwise rotation.}

Proof. It is pretty obvious that Kr2 _{= c−1, since up to relabeling it's an}

in-volution, and the new labels are one unit lower than the old ones (except, of course, for 1 which is relabeled as n). Since c−1_{is bijective, then Kr is bijective}

too.

It remains to prove that Kr reverses the ordering, but this is clear too, since if π1 is coarser than π2, then the coarsest element such that the union is still

noncrossing in NC(2n) is ner.

2.3 Instances of cyclic sieving

Through the representation of partitions on a disk, one may dene a natural action of the cyclic group Cn on the set of partitions, by rotation. There are

several known instances of cyclic sieving related to this action. Our goal is to proof the following three theorems.

The rst theorem states an instance of cyclic sieving for the whole set of non-crossing partitions.

Theorem 2.7 (Reiner, Stanton, White [18]). Let X = NC(n), and let C = Cn

acting on X by rotation. The triple (X, C, X(q)) exhibits the cyclic sieving phenomenon, where X(q) = Catq(n) := 1 [n + 1]q 2n n  q

is the q-Catalan number.

Since the action by rotation preserves the number of blocks, one may consider another instance of cyclic sieving.

Theorem 2.8 (Reiner, Stanton, White [18, Theorem 7.2]). Let X = NC(n, k), and let C = Cn acting on X by rotation. The triple (X, C, X(q)) exhibits the

cyclic sieving phenomenon, where X(q) = Narq(n, k) := 1 [n]q n k  q  n k_{− 1}  q

is the q-Narayana number.

And nally, since the number of singleton blocks is preserved too, one may consider this last instance of cyclic sieving.

Theorem 2.9 (Pechenik, [16, Theorem 1.4]). Let X = NC(n, k, 0), and let C = Cn acting on X by rotation. The triple (X, C, X(q)) exhibits the cyclic

sieving phenomenon, where

X(q) = Dq(n− k + 2, k − 1) := 1 [k]q  _n k_{− 1}  q n_{− k − 1} k_{− 1}  q

is the q-Kirkman-Cayley number.

The polynomial Dq(n− k + 2, k − 1) above appears in several contexts. It is

an instance of the q-hook length formula corresponding to the ag partition λ = (k, k, 1n−2k_{), which will be important later. It is also a q-enumerator for}

rectangular increasing Young tableaux of size 2×(n−k), with n as xed maximal entry (and that's why we were interested in those tableaux). Moreover, in [16] there is an explicit equivariant bijection between NC(n, k, 0) under the action by counterclockwise rotation and increasing Young tableaux under K-promotion, so this is related to K-theory. We will discuss some of these interesting links later.

The q-Kirkman-Cayley polynomial is also involved in another instance of cyclic sieving, discussed in [18].

Theorem 2.10 (Reiner, Stanton, White [18, Theorem 7.1]). Let X be the set of dissections of regular n-gons with k diagonals, let C = Cn acting on X by

rotation, and let X(q) = Dq(n, k). The triple (X, C, X(q)) exhibits the cyclic

Notice that the q-enumerator for noncrossing partitions of [n] with k blocks and no singletons is the same of that for dissections of n − k + 2-gons with k_{− 1 noncrossing diagonals. Despite this fact, these two actions seem not to be} related.

2.4 An action of the symmetric group

In order to give an algebraic proof of cyclic sieving, one may want to extend the action of the cyclic group on noncrossing partitions to an action of a bigger group, and hence have more structure. The most obvious candidate is the dihedral group Dn, but unfortunately it's still too small.

The goal is to nd an action of the symmetric group Sn on NC(n), since there

are lots of tools to describe its representations; however, noncrossing partitions are not closed under the natural action of Sn on Π(n). What Rhoades did

in [21] is to nd a way to "resolve" a generic partition and write it as linear combination of noncrossing ones, so that Q(NC(n)) gets a Sn-module structure.

Let

P (n) := Q(Π(n)), P (n, k) := Q(Π(n, k)), P (n, k, s) := Q(Π(n, k, s)) be the vector spaces spanned by partitions, and let

V (n) := Q(NC(n)), V (n, k) := Q(NC(n, k)), V (n, k, s) := Q(NC(n, k, s))

be the noncrossing subspaces, spanned by noncrossing partitions.

We now want to give P (n) and V (n) a Sn-module structure, and dene a

pro-jection P (n)  V (n) which is Sn-equivariant. Let s ∈ Sn. There is a natural

action on partitions given by

s(π) :={s(X) | X ∈ π}

where s(X) := {s(i) | i ∈ X}. We dene our action on the basis Π(n) as s∗ π = sign(s) · s(π).

In [21], Rhoades introduces a partially sign-twisted action of Sn to avoid some

issues while dealing with singletons, but our construction looks more natural.

2.4.1 Skein relations

Now we want to describe a resolution of generic partitions into a linear combi-nation of noncrossing ones. For 1 ≤ i ≤ n − 1, let ti= (i, i + 1)∈ Sn.

Denition 2.11. A partition π ∈ Π(n) is almost noncrossing if it is not non-crossing, but exists 1 ≤ i ≤ n − 1 such that ti(π)is noncrossing. In this case,

we say that π crosses at i.

Example 2.12. Take π1 = {{1, 2, 4}, {3, 5}, {6}}, π2 = {{1, 6}, {2, 4, 5}, {3}},

and π3={{1, 2, 4, 5}, {3, 6}} in Π(6). These are represented below.

1 2 4 3 5 6 6 1 2 4 5 3 1 2 4 5 3 6

π

1

π

2

π

3

π1is almost noncrossing, since it crosses at 3 and 4. π2is noncrossing, therefore

it's not almost noncrossing. π3 is neither noncrossing nor almost noncrossing.

Let n, k, s ≥ 0. We dene three collections of set partitions as follows. ANC(n) :=_{{π ∈ Π(n) | π is almost noncrossing},} ANC(n, k) :=_{{π ∈ ANC(n) | π has k blocks},} ANC(n, k, s) :={π ∈ ANC(n, k) | π has s singletons}.

The next denition is a slight modication of the skein relation introduced by Rhoades in [21], and it's the core of the whole construction.

Denition 2.13. Let π ∈ ANC(n), and suppose that π crosses at i. Let Bi= Bi(π), Bi+1= Bi+1(π). Let

π1= (π\ {Bi(π), Bi+1(π)}) ∪ {(Bi\ {i}) ∪ i + 1, (Bi+1\ {i + 1}) ∪ {i}}

π2= (π\ {Bi(π), Bi+1(π)}) ∪ {(Bi\ {i}) ∪ (Bi+1\ {i + 1}), {i, i + 1}}

π3= (π\ {Bi(π), Bi+1(π)}) ∪ {Bi\ {i}, Bi+1∪ {i}}

π4= (π\ {Bi(π), Bi+1(π)}) ∪ {Bi∪ {i + 1}, Bi+1\ {i + 1}}

π5= (π\ {Bi(π), Bi+1(π)}) ∪ {(Bi\ {i}) ∪ Bi+1,{i}}

π6= (π\ {Bi(π), Bi+1(π)}) ∪ {Bi∪ (Bi+1\ {i + 1}), {i + 1}}

π7= (π\ {Bi(π), Bi+1(π)}) ∪ {Bi∪ Bi+1}

and dene σ(π) := π1+ π2− π3− π4− π5− π6+ π7.

Since an almost noncrossing partition could cross at more than one index, the skein resolution is a priori ambiguous. But in fact, it is not.

Lemma 2.14 (Rhoades, [21]). The skein relation gives a well dened function σ : ANC(n) → V (n). Moreover, every set partition appearing in σ(π) has at most the same number of blocks and at least the same number of singleton blocks as π.

Figure 2.3: The skein relation

σ

i i + 1 a1 ak b1 bh

=

π1 i i + 1 a1 ak b1 bh

+

π2 i i + 1 a1 ak b1 bh

+

π7 i i + 1 a1 ak b1 bh

−

π3 i i + 1 a1 ak b1 bh

−

π4 i i + 1 a1 ak b1 bh

−

π5 i i + 1 a1 ak b1 bh

−

π6 i i + 1 a1 ak b1 bh

Proof. Let π ∈ ANC(n) that crosses at i. We need to prove that the six terms appearing in σ(π) computed at i are all noncrossing. It's clear from the picture, but we'll prove that anyway.

Let π0 _{be any of the terms that appear in σ(π). Suppose that π}0 _{is crossing.}

Then there exist 1 ≤ x1 < x2 < x3 < x4 ≤ n such that Bx1(π0) = Bx3(π0)and

Bx2(π0) = Bx4(π0). Since ti(π)is noncrossing, one of these blocks must be one

of the nonxed ones, and also it must be the one which gained elements. Up to rotation, we may suppose that it's the one containing x1 and x3, and it's quite

easy to check that x1 and x3 could be chosen to be in the same block of ti(π),

which is absurd since ti(π)is noncrossing.

Moreover, each term of σ(π) has at most the same number of blocks, and at least the same number of singletons. We now need to prove that the resolution does not depend on the index. If π crosses at only one index, the thesis is obvious. Suppose that π crosses at exactly two indices 1 ≤ i < j ≤ n − 1.

If j 6= i + 1, it follows from the fact that π is almost noncrossing that j ∈ Bi(π)

and j + 1 ∈ Bi+1(π). Moreover, the almost noncrossing condition implies that

none of these blocks may have more than two elements, so both {i, j} and {i + 1, j + 1} are blocks of π. It's pretty easy to check that the two resolutions coincide.

If j = i + 1, then i, i + 2 is a block of π. In fact, since Bi+1 can't be a singleton,

we can suppose up to rotation that 1 6= i + 1 and 1 ∈ Bi+1. The noncrossing

condition for ti(π) implies that all the elements of Bi(π) except i have to be

greater than i + 1, and the noncrossing condition for ti+1(π)imples that all the

elements of Bi(π)except possibly i+2 have to be smaller than i+1. Combining

these two conditions we get Bi(π) = i, i + 2. Given that, one could easily check

that the two resolutions give the same expression.

Suppose that π crosses at more than two indices. Then repeating the consid-erations we made for the previous cases, it follows that necessarily it crosses at three indices of the form i, i + 1, and i + 2, and also both i, i + 2 and i + 1, i + 3

are blocks of π. The previous case imples that the resolutions at i and i + 1 are equal, and the same holds for i + 1 and i + 2, so they all coincide.

Observation 2.15. Notice that if π is noncrossing, the skein resolution σ could be applied on ti(π)anyway, provided that i and i + 1 are not blockmates. In

this case, due to some deletions, we have σ(ti(π)) =−ti(π). This feature of our

resolution will be useful.

Example 2.16. Let π be as in Figure 2.3, but with no green vertices. We have that

Figure 2.4: The noncrossing skein relation

σ

i i + 1 a1 ak

=

π1 i i + 1 a1 ak

+

π2 i i + 1 a1 ak

+

π7 i i + 1 a1 ak

−

π3 i i + 1 a1 ak

−

π4 i i + 1 a1 ak

−

π5 i i + 1 a1 ak

−

π6 i i + 1 a1 ak

2.4.2 The skein action on V (n)

It is now moment to endow V (n) with a structure of Sn-module. It will be done

dening the action of adjacent transpositions via the skein resolution dened before.

For 1 ≤ i ≤ n − 1, let τi: V (n) → V (n) be the linear operator dened on the

basis NC(n) by

τi(π) =(−π

if Bi(π) = Bi+1(π)

σ(ti(π)) if Bi(π)6= Bi+1(π)

Notice that Observation 2.15 implies that τi(π) =−ti(π)if both π and ti(π)are

noncrossing. In fact, we will now prove that these operators dene an action of Sn on V (n).

Theorem 2.17. The linear operators {τi | 1 ≤ i ≤ n − 1} satisfy the Coxeter

relations (see 3.1). Therefore, ti∗ π = τi(π)denes an action of Sn on V (n).

Lemma 2.18. For 1 ≤ i ≤ n − 1, τi2= id.

Proof. Let π ∈ NC(n). If ti(π)is noncrossing, then

τi2(π) = τi(−ti(π)) =−τi(ti(π)) = ti2(π) = π. If ti(π)crosses at i, then τi2(π) = τi(σ(ti(π))) = τi(π1) + τi(π2)− τi(π3)− τi(π4)− τi(π5)− τi(π6) + τi(π7) = (π1+ π2− π3− π4− π5− π6+ π7)− π2+ π3+ π4− π6− π5− π7 = π1= π

Lemma 2.19. For 1 ≤ i < j ≤ n − 1 and j − i > 1, we have τiτj = τjτi.

Proof. Let π ∈ NC(n).

Case 1. If Bi(π) = Bi+1(π), by construction (see 2.13) the same holds for any

term that appears in τj(π). Then τiτj(π) = τjτi(π) =−τj(π), as desired. The

same argument holds if Bj(π) = Bj+1(π)

Case 2. If Bi(π), Bi+1(π), Bj(π), and Bj+1(π)are all distinct, then it's pretty

easy to check that the actions of τi and τj involve dierent blocks and so they

commute.

Case 3. If Bi(π) = Bj(π), then π is as below (blocks dierent from Bi(π),

Bi+1(π), Bj(π), and Bj+1(π)are not shown).

π =

j + 1 i i + 1 j a1 ap b1 bq c1 cr d1 ds

Case 4. If either Bi(π) = Bj+1(π)or Bj(π) = Bi+1(π), (but not both), then

without loss of generality π is as below.

π =

j + 1 i i + 1 j a1 ap b1 bq c1 cr d1 ds

Case 5. If Bi(π) = Bj+1(π)and Bj(π) = Bi+1(π), then π is as below.

π =

j + 1 i i + 1 j a1 ap b1 bq c1 cr d1 ds

Notice that the casistic is exhaustive, since if we have three or more coincident blocks, then we are in Case 1.

Proof of Case 3. Applying τi, we get

+

+

₋

₋

₋

₋

+

and applying τj, we get

+

+

₋

₋

₋

₋

+

+

+

−

−

−

−

+

−

−

+

+

+

+

₋

−

−

+

+

+

+

−

−

−

+

+

+

+

₋

−

−

+

+

+

+

₋

+

−

+

+

+

+

−

The whole sum is symmetrical in i and j (reecting each term with respect to the descending diagonal), and that's easy to check since the picture is also symmetric. It follows that we get the same result applying τj and τi in reverse

Proof of Case 4. Applying τi, we get

+

+

₋

₋

₋

₋

+

and applying τj, we get

+

+

₋

₋

₋

₋

+

+

+

−

−

−

−

+

−

−

+

+

+

+

₋

−

−

+

+

+

+

−

−

−

+

+

+

+

₋

−

−

+

+

+

+

₋

+

+

−

−

−

−

+

The whole sum is symmetrical in i and j (reecting each term with respect to the horizontal axis), and once again it's easy to check since the picture is symmetric with respect to the descending diagonal. It follows that τiτj(π) = τjτi(π).

Proof of Case 5. Applying τi, we get

+

+

₋

₋

₋

₋

+

and applying τj (at π1, π3 and π4 rst) we get

+

+

₋

₋

₋

₋

+

−

−

+

+

+

+

−

−

−

+

+

+

+

₋

−

+

+

−

The whole sum is symmetrical in i and j (with respect to both vertical and horizontal axis), and that's quite easy to check (but there's no global symmetry this time, I'm sorry). It follows that τiτj(π) = τjτi(π).

In each case the equality τiτj = τjτi holds. We don't need to worry about

degenerate cases (with no blue, green, red or yellow vertices) since our skein relation always works.

It remains one more relation to check, the one involving two noncommuting transpositions.

Lemma 2.20. For 1 ≤ i < n − 1 we have τiτi+1τi= τi+1τiτi+1.

Proof. Let π ∈ NC(n).

Case 1. Bi(π) = Bi+1(π) = Bi+2(π).

π =

i i + 1 i + 2 ap a1

Case 2. Bi(π) = Bi+2(π), but Bi+1 is dierent.

π =

i i + 1 i + 2 ap ap

Case 3. Bi(π) = Bi+1(π)or Bi+1(π) = Bi+2(π), and the third is dierent.

π =

i i + 1 i + 2 b1 bq a1 ap

Case 4. Bi(π), Bi+1(π), and Bi+2(π) are all distinct. π is represented below

(once again, blocks dierent from Bi(π), Bi+1(π), and Bi+2(π)are not shown).

π =

i i + 1 i + 2 a1 ap b1 bq c1 cr

Proof of Case 1. In this case the thesis is obvious, since τiτi+1τi(π) =

τi+1τiτi+1(π) =−π.

Proof of Case 2. In this case the thesis is also obvious, since once again τiτi+1τi(π) = τi+1τiτi+1(π) =−π.

Proof of Case 3. Without loss of generality, suppose Bi(π) = Bi+1(π). Since

iand i + 1 are blockmates, we have τi(π) =−π. Applying τi+1 we have

−

−

+

+

+

+

−

and applying τi again (at π2 and π4rst) we get

−

−

+

+

+

+

−

+

+

₋

₋

₋

₋

+

+

₋

₋

₋

+

=

+

−

−

−

−

+

We just evaluated τiτi+1τi(π) = −τiτi+1(π). Since in any of the terms of the

result i + 1 and i + 2 are blockmates, applying −τi+1 (which does nothing) to

the RHS, we have τiτi+1τi(π) = τi+1τiτi+1(π), as desired.

Notice that, if we treat i + 1, i + 2 as a singleton, the expression on the last line for τiτi+1τi(π)is a skein relation.

Proof of Case 4. Applying τi, we get

+

+

₋

₋

₋

₋

+

and applying τi+1 (at π6 last) we get

+

+

₋

₋

₋

₋

+

+

+

−

−

−

−

+

−

−

+

+

+

+

₋

−

−

+

+

+

+

−

−

−

+

+

+

+

₋

+

+

−

−

−

−

+

+

It's convenient to distinguish terms based on what does τido on them. Terms 3

and 10 are canceled by terms 24 and 31. Terms 1, 2, 4, 6, 7, 9, 16, 17, 23, 37, 38 and 43 became crossing, so we need to write their resolution via skein relations. Terms 8, 11, 13, 14, 15, 18, 20, 21, 22, 25, 27, 28, 36, 39, 41, and 42 simply change sign. Terms 5, 12, 19, 26, 29, 30, 31, 32, 33, 34, 35 and 40 change, but remain noncrossing. Let's start by computing τi on crossing terms.

+

+

₋

₋

₋

₋

+

+

+

₋

₋

₋

₋

+

−

−

+

+

+

+

₋

−

−

+

+

+

+

−

+

+

−

−

−

−

+

+

+

₋

₋

₋

₋

+

−

−

+

+

+

+

₋

+

+

−

−

−

−

+

−

−

+

+

+

+

−

+

+

₋

₋

₋

₋

+

−

−

+

+

+

+

₋

+

+

₋

₋

₋

₋

+

Now we compute τi on terms in which i and i+1 are blockmates, so they simply

change sign.

−

+

+

−

+

−

−

+

+

₋

₋

+

₋

+

+

₋

At last, we compute terms in which i and i+1 are in dierent blocks, but remain noncrossing.

+

+

−

−

+

+

−

−

−

+

+

And now the reader could take a pencil, an eraser, and a bag of chips, and check that the whole sum is symmetrical in i and i + 2 (reecting vertically), so the thesis follow.

With these three lemmas, the proof of the theorem is very straightforward. Proof of Theorem 2.17. Since the elements ti, for 1 ≤ i ≤ n − 1, generate

Sn, the thesis follows immediately from the lemmas.

2.5 Noncrossing resolution

We have built two Sn-modules P (n) and V (n), the former with the signed

per-mutation action on partitions and the latter with the skein action just dened. Since V (n) ⊆ P (n), for s ∈ Snand π ∈ V (n), the expression s ∗ π is ambiguous.

Let's temporarily use it for the skein action on V (n), since we have an explicit way to describe the signed permutation action. Nevertheless, these two actions are strictly related.

Theorem 2.21. The skein relation 2.13 induces a map σ : P (n)  V (n), de-ned on the basis as π 7→ sign(s) s−1_{∗ s(π)}

, where s ∈ Sn is chosen such that

s(π)is noncrossing. This map is well dened and Sn-equivariant.

Despite it looks obvious, proving this theorem requires some eort. This result allows us to write a noncrossing resolution for partitions, which means that we could think of NC(n) as a basis for the vector space spanned by Π(n) quotiented by all the skein relations. Moreover, the Sn-equivariance of the map implies

that the two actions we dened in the last section are, in fact, the same (so the expression s ∗ π is not ambiguous). It is a powerful result that will be the key of the proof of this instance of cyclic sieving.

A rst thing to notice is that the Snaction is, in some sense, local, meaning that

the action of ti on π only aects the blocks Bi(π)and Bi+1(π). The following

statement formalizes this property.

Proposition 2.22. Let π ∈ NC(n), let A ⊆ π be an union of blocks of π, let A =S Aand let m = #A.

Let ¯π ∈ NC(m) obtained by restricting π and decrementing indices accordingly. Let SA:= {s ∈ Sn | s(i) = i if i 6∈ A}. For s ∈ SA, let ¯s ∈ Smbe its restriction

to A, where m = #A.

For any term π0_{appearing in s∗π we have A ⊆ π}0 _{and π \A = π}0_{\A. Moreover,}

¯

π0 appears in ¯s ∗ ¯π with the same coecient as π0 in s ∗ π, so the two skein resolutions coincide on A.

Proof. It is obvious because of the way the skein relation 2.13 is dened. In fact, any s ∈ SA can be written as product of adjacent transpositions ti with

i, i + 16∈ A.

All the elements which don't belong to neither Bi(π)nor Bi+1(π)are xed by

τi, and also all the terms which appear in τi(π)have the same blocks as π except

at most Bi(π)and Bi+1(π). The thesis follows.

Now we have to nd a way to eciently compute the action of Snon V (n). The

following lemma is simple, but it has surprisingly strong consequences.

Lemma 2.23 (Rotation lemma). Let π = {{1, . . . , i}, {i + 1, . . . , n}} ∈ NC(n), and let s = (1, i + 1). Then s ∗ π = −s(π).

Proof. To evaluate s ∗ π, we need to write s as product of adjacent trans-positions. We have s = titi−1· · · t2t1t2· · · ti−1ti. Since none of the elements

in {i + 2, . . . , n} is aected, we could collapse that set to a singleton, so let's assume i = n − 2.

Figure 2.5: The rotation lemma

s

_∗

1 n− 2 n− 1 n

=

₋

1 n 2 n− 1

Our next goal is to evaluate tn−j· · · tn−1, for 1 ≤ j ≤ n − 1. We claim that the

result is (−1)j+1 _times

+

1 n− j n

−

1 n n− j

−

1 n− j n

+

1 n− j n

+

1 n

+

1 n n− j

−

1 n

By induction on j. The induction basis holds, since the relation above is the skein resolution of tn−1if j = 1. For the inductive step, we apply tn−j−1 on the

relation above, and get

+

1 n− j n

+

1 n n− j − 1 n− j

−

1 n− j − 1 n− j n

−

1 n− j n

−

1 n− j − 1

−

1 n n− j

+

1 n

−

1 n n− j

−

1 n n− j − 1 n− j

+

1 n n− j − 1 n− j

+

1 n− j n

+

1 n n− j − 1

+

1 n n− j

−

1 n

+

1 n− j n

−

1 n− j n

−

1 n

−

1 n n− j − 1

+

1 n

which is, after cancellations, exactly what we wanted. Now, for j = n − 2, we get (−1)n−1 _times

+

1 n

−

n 1

−

1 n

+

1 n

+

1 n

+

n 1

−

1 n

which is equal to (−1)n−1_{s(π). Applying t}

iti−1· · · t2, since each term simply

Putting toghether this lemma with Proposition 2.22, we have the following Corollary 2.24 (Sliding corollary). Let π ∈ NC(n) such that Bi(π) ={i, i +

1, . . . , j− 1} is an interval. If s = (i, j) then s ∗ π = −s(π). Figure 2.6: The sliding corollary

s

_∗

j i

=

−

j i

This corollary basically allows us to rearrange blocks in a noncrossing partition using the Sn action on V (n).

Let's see how to use this fact for our purposes. Given a partition of n λ = (λ1, λ2, . . . , λk)` n, let πλ denote the noncrossing set partition

πλ:= {{1, 2, . . . , λ1}, {λ1+ 1, λ1+ 2, . . . , λ1+ λ2}, . . . , {n − λk+ 1, . . . , n}}.

Notice that any set partition π ∈ Π(n) is conjugate under the action of Sn to a

unique partition of the form πλ for some λ ` n. In this case, we write π ∼ πλ.

We may now state another lemma.

Lemma 2.25. Let π ∈ NC(n), and let λ ` n such that π ∼ πλ. There exists

w∈ Sn such that w(πλ) = π and w ∗ πλ= sign(w)· w(πλ).

Proof. Let B be the block of π with lowest cardinality. Then its elements must be consecutive numbers, so let B = {i, i + 1, . . . , i + j}.

Let

w1= (n− j − 1, n)(n − j − 2, n − 1) · · · (i, i + j + 1).

Applying Corollary 2.24 to each transposition that appears in w1(starting from

the rightmost) we have that w1(π)is noncrossing, w1∗ (π) = sign(w1)· w1(π)

and w1(B) ={n − j, n − j + 1, . . . , n}.

Thanks to Lemma 2.22 we can restrict to w1(π)\ w1(B)and repeat the process,

chosing each time the smallest block. At last we have w1, . . . , wk such that

wk· · · w1(π) = πλ and wk· · · w1∗ π = sign(w1· · · wk)· πλ.

Let w = (wk· · · w1)−1: then w(πλ) = π, and acting with w on the equality

above we get w ∗ πλ= sign(w)· w(πλ), as desired.

We're almost done, but rst we need another couple of lemmas.

Lemma 2.26. stab(πλ) is generated by adjacent transpositions ti such that i

and i+1 are blockmates, and permutations that swap two consecutive blocks of the same size while preserving the relative order of the elements in each block.

Proof. Those elements lie in stab(πλ)and obviously generate.

Example 2.27. If λ = (4, 2, 2, 1), then πλ={{1, 2, 3, 4}, {5, 6}, {7, 8}}, therefore

stab(πλ)is generated by s1, s2, s3, s5, s7 and (57)(68) (which swaps the 2ndand

the 3rd _block).

Lemma 2.28. If s ∈ stab(πλ), then s ∗ πλ= sign(s)· πλ.

Proof. It is sucient to check that for the generators of stab(πλ). For adjacent

transpositions it obviously holds. For permutations of the other type, the thesis follows from Corollary 2.24.

With all these lemmas, proving Theorem 2.21 is piece of cake.

Proof. It is sucient to prove that the map π 7→ sign(s) s−1_{∗ s(π)}
is well dened, since then the Sn-equivariance is obvious.

Let s, t ∈ Sn such that both s(π) and t(π) are noncrossing. We need to prove

that

sign(s) s−1∗ s(π)
= sign(t) t−1_{∗ t(π)
.}

Let π ∈ Π(n), and let λ ` n such that π ∼ πλ. Then s(π) ∼ πλ and t(π) ∼ πλ

too. Let v, w ∈ Sn such that s(π) = v(πλ) and t(π) = w(πλ). We have

π = s−1_v(π

λ) = t−1w(πλ), so (t−1w)−1(s−1v)∈ stab(πλ).

By the previous lemma, we have

(t−1w)−1(s−1v)_{∗ π}λ= sign(stvw)· πλ.

Acting with t−1_{wwe get}

sign(sv) s−1v_{∗ π}λ
= sign(tw) t−1w∗ πλ
,

so from the relation v ∗ πλ = sign(v)· v(πλ) = sign(v)· s(π) and the analog

w∗ πλ= sign(w)· w(πλ) = sign(w)· t(π), we have

sign(s) s−1_{∗ s(π)}
= sign(t) t−1_{∗ t(π)
,}

as desired.

2.6 Representation structure

In order to prove our instance of cyclic sieving, we must be able to evaluate the character of this representation. It will require some work.

Let V (n,≤ k) :=M j≤k V (n, j), and V (n, k, ≥ s) :=M t≥s V (n, k, t). We have Sn-stable ltrations