THE CYCLIC SIEVING PHENOMENON

V. REINER, D. STANTON, AND D. WHITE

Abstract. The cyclic sieving phenomenon is defined for generating functions of a set affording a cyclic group action, generalizing Stembridge’s q = −1 phenomenon. The phenomenon is shown to appear in various situations, involving q-binomial coefficients, Pólya theory, polygon dissections, non-crossing partitions, finite reflection groups, and some finite field q-analogues.

1. Introduction

Stembridge’s q = −1 phenomenon [39, 40, 41] has proven to be a useful tool in organizing various enumerative results. This paper introduces the more general cyclic sieving phenomenon, which we now define.

Let X be a finite set, with an action of a cyclic group C of order n. Elements within a C-orbit share the same stabilizer subgroup, whose cardinality we will call the stabilizer-order for the orbit. Let X(q) be a polynomial in q having nonnegative integer coefficients, with the property that X(1) = |X|; we will think of X(q) as a q-enumerator or generating function for X. Fix an isomorphism ω of C with the complex n^{th} roots of unity, that is, an embedding ω : C ↪ ℂ^{×}. Definition-Proposition. The following are equivalent conditions for a triple (X, X(q), C) as above:

(i) For every c ∈ C,

[X(q)]_{q=ω(c)} = |{x ∈ X : c(x) = x}|.

(ii) The coefficient a_{ℓ} defined uniquely by the expansion

X(q) ≡ ∑_{ℓ=0}^{n−1} a_{ℓ}q^{ℓ} mod q^{n} − 1

Date: September 2003.

Key words and phrases. q-binomial coefficient, q-multinomial coefficient, rootsof-unity, principal specialization, Schur function, Kraśkiewicz-Weyman, Singer cycle, Springer regular element, polygon dissections, noncrossing partitions, hook formula, rooted plane tree.

First, second author supported by NSF grants DMS-0245379, DMS-0203282 respectively.

has the following interpretation: a_{ℓ} counts the number of C-orbits on X for which the stabilizer-order divides ℓ. In particular, a_{0} counts the total number of C-orbits on X, and a_{1} counts the number of free C-orbits on X

When either of these two conditions holds, we say that (X, X(q), C) exhibits the cyclic sieving phenomenon. The straightforward equivalence between conditions (i) and (ii) above is proven in Section 2, and related to a linear-algebraic/representation-theoretic paradigm for proving them.

When |C| = 2, condition (i) above is the q = −1 phenomenon. We observe many instances of the more general cyclic sieving phenomenon, beginning with the following result on q-binomial coefficients. It is wellknown [23, Ex. I.2.3], [35, §7.8] that the q-binomial coefficients

[\begin{matrix}N \\ k \end{matrix}]_{q} and [\begin{matrix}N + k − 1 \\ k \end{matrix}]_{q}

are generating functions for k-subsets and k-multisubsets of [N] := {1, 2, …, N} counted according to certain natural q-weights. Say that the cyclic group C of order n acts nearly freely on [N] if it is generated by an element c ∈ 𝔖_{N} whose cycle type is either

• a cycles of size n, so that N = an (and C_{n} acts freely), or

• a cycles of size n and one singleton cycle, so that N = an + 1 for some positive integer a. Theorem 1.1. Let the cyclic group C of order n act nearly freely on [N].

(a) Let X be the set of k-multisubsets of [N], and

X(q) := [\begin{matrix}N + k − 1 \\ k \end{matrix}]_{q} .

Then (X, X(q), C) exhibits the cyclic sieving phenomenon.

(b) Let X be the set of k-subsets of [N], and

X(q) := [\begin{matrix}N \\ k \end{matrix}]_{q} .

Then (X, X(q), C) exhibits the cyclic sieving phenomenon. Example 1.2. As an illustration, take k = n = 6, N = 12, and C the cyclic group generated by c = (1, 3, 5, 7, 9, 11)(2, 4, 6, 8, 10, 12) acting on the subsets of [12] of cardinality 6. Then

[\begin{matrix}12 \\ 6 \end{matrix}]_{q} ≡ 160 + 150q + 156q^{2} + 152q^{3} + 156q^{4} + 150q^{5} mod q^{6} − 1

reflecting the fact that there are 150 free orbits, and, respectively, 6, 2, 2 orbits having stabilizer-orders 2, 3, 6. For an example involving multisets, take k = n = 4 and N = 8, and consider the cyclic group C_{4} generated by c = (1357)(2468) acting on the multisubsets of [8] of cardinality 4. Then

[\begin{matrix}11 \\ 4 \end{matrix}]_{q} ≡ 86 + 80q + 84q^{2} + 80q^{3} mod q^{4} − 1

reflecting the fact that there are 80 free orbits, and, respectively, 4, 2 orbits having stabilizer-orders 2, 4.

Theorem 1.1 is not hard; it is deduced using the representation theory paradigm in Section 3, or via calculation of explicit formulae for the coefficients a_{ℓ} in Section 4.

Special cases of this theorem provide combinatorial proofs for several results in the literature. For example, at the end of the paper [12], the authors ask for a combinatorial explanation of the following corollary to Theorem 1.1. Corollary 1.3. Let a_{ℓ}(n, k) denote the coefficient of q^{ℓ} in

[\begin{matrix}n + k − 1 \\ k \end{matrix}]_{q} mod q^{n} − 1,

with the convention that a_{1}(1, k) = 1. Then

(1.1)  a_{ℓ}(n, k) = ∑_{d|n,k,ℓ} a_{1} (\frac{n}{d}, \frac{k}{d}) .

This corollary is immediate from Theorem 1.1(a), with C the cyclic group of order n acting freely on [n], and on its k-multisubsets: the left side of (1.1) counts orbits of multisets whose stabilizer-order is some d dividing ℓ; the number of such orbits for which the stabilizer-order is exactly d is the term a_{1}(\frac{n}{d}, \frac{k}{d}) on the right side of (1.1).

One of our original motivations was to understand the following fact observed by Chapoton [6], which we deduce in Section 5 from either part (a) or (b) of Theorem 1.1. Theorem 1.4. The constant term a_{0} in

[\begin{matrix}2n − 1 \\ n \end{matrix}]_{q} mod q^{n} − 1

counts rooted plane trees with n non-root vertices, up to cyclic rotation of subtrees about the root.

The two parts of Theorem 1.1 have interesting generalizations. Section 6 generalizes Theorem 1.1(a) to a result (Theorem 6.1) about principal specializations of weight enumerators from Pólya theory. A sample application of this result is the following result of Read [25]. Corollary 1.5. Let X(q) be the generating function counting unlabelled (isomorphism classes of) simple graphs on n vertices according to their number of edges. Then X(−1) counts the number of selfcomplementary unlabelled graphs on n vertices.

Section 8 generalizes Theorem 1.1(b) to a statement about finite Coxeter groups, and more generally, unitary reflection groups. The symmetric group 𝔖_{N} is a Coxeter group W of type A_{N−1}. The ksubsets of [N] correspond to cosets W/W_{J}, where W_{J} is the parabolic subgroup 𝔖_{k} × 𝔖_{N−k}. One then has

[\begin{matrix}N \\ k \end{matrix}]_{q} = W^{J}(q) := ∑_{w∈W^{J}} q^{ℓ(w)}

where W^{J} denotes the set of minimal length representatives for cosets of W_{J}. A cyclic subgroup C of W acts on the set of cosets W/W_{J} by left-multiplication. It turns out that C in 𝔖_{N} acts nearly freely on [N] exactly when it is generated by a regular element in the sense of Springer [33]. In Section 8, we deduce (a generalization of) the following statement, using Springer’s theory of regular elements as rephrased by Kraśkiewicz and Weyman [20]. Theorem 1.6. Let (W, S) be a finite Coxeter system and J ⊆ S. Let C be a cyclic subgroup generated by a regular element. Let X be the set of cosets W/W_{J}, and X(q) := W^{J}(q).

Then (X, X(q), C) exhibits the cyclic sieving phenomenon. Special cases of this result related to maximal parabolic subgroups for some of the other reflection groups are discussed in Section 8. It is also observed there that the longest element w_{0} in W is always a regular element, and thus specializing Theorem 1.6 to C = ⟨w_{0}⟩ gives the first case-free proof for all finite Coxeter groups of a theorem of Eng [13].

Section 7 proves two curious instances of the cyclic sieving phenomenon (Theorem 7.1), one involving dissections of a convex polygon, the other involving noncrossing partitions.

Section 9 deals with finite field q-analogues of Theorem 1.1(b). These relate to recent results of Drudge [11], counting orbits of k-dimensional subspaces in a finite vector space under the action of a Singer cycle, which is a q-version of an n-cycle. This turns out to be closely related to the invariant theory of GL_{n}(𝔽_{q}) and its parabolic subgroups, leading naturally to the cyclic sieving phenomenon for flags of subspaces and a newly defined (q, t)-multinomial coefficient.

Section 10 proves that these q-analogues counting cyclic orbits of subspaces are polynomials in q with integer coefficients, and conjectures that they have nonnegative coefficients. Some easy cases of this conjecture are discussed, generalizing a result due independently to Andrews [1] and Haiman [16]. In the process of our analysis, we abstract two general principles, one for proving polynomiality of a rational function, and one for proving polynomials have nonnegative coefficients. The latter comes from the methods of Andrews [1], and is applied to prove some old and new positivity results.

Contents

1. Introduction 1 2. Phenomen-ology 5 3. First proof of Theorem 1.1: representation theory 8 4. Second proof of Theorem 1.1: explicit formulae 9 5. Cyclically equivalent plane trees 13 6. The phenomenon in Pólya theory 14 7. The phenomenon in polygons: two instances 16 7.1. Polygon dissections 16 7.2. Noncrossing partitions 19 8. Springer’s theorem on regular elements 21 9. Counting cyclic orbits over finite fields 26 10. Polynomiality, nonnegativity, and a conjecture 29 Acknowledgments 34 References 34

2. Phenomen-ology

This section treats general facts about the cyclic sieving phenomenon. We begin by proving the equivalence of conditions (i) and (ii) in the Definition-Proposition of the introduction, relating them to a third, representation-theoretic condition. We then show how this third condition leads to a representation theory lemma (Lemma 2.3) useful for proving instances of the cyclic sieving phenomenon. For the purpose of stating this third equivalent condition, we introduce some notation.

As in the introduction, let C be a cyclic group of order n acting on a finite set X, and fix an embedding ω : C ↪ ℂ^{×}. Let a_{ℓ} be the coefficient uniquely defined by the expansion

X(q) ≡ ∑_{ℓ=0}^{n−1} a_{ℓ}q^{ℓ} mod q^{n} − 1.

Introduce a graded ℂ-vector space

A_{X} := ⨁_{i≥0} A_{X,i}

having ∑_{i≥0} dim_{ℂ} A_{X,i}q^{i} = X(q), and affording a representation of C in which each c ∈ C acts on the graded component A_{X,i} by the scalar ω(c)^{i}.

The following encompasses the Definition-Proposition from the introduction. Proposition 2.1. With the above notation, the following are equivalent phrasings of the cyclic sieving phenomenon:

(i) For every c ∈ C,

[X(q)]_{q=ω(c)} = |{x ∈ X : c(x) = x}|.

(ii) The coefficient a_{ℓ} counts the number of C-orbits on X for which the stabilizer-order divides ℓ.

(iii) As representations of C, the permutation representation ℂ[X] and A_{X} are isomorphic.

Proof. The equivalence of conditions (i) and (iii) is clear, as the left side of (i) is the character value for c in the representation A_{X}, while the right side of (i) is the character value for c in ℂ[X].

To prove the equivalence of (iii) and (ii), note that ℂ[X] and A_{X} are isomorphic if and only if for each of the irreducible (degree one) representations {ρ^{(ℓ)}}_{ℓ∈ℤ/nℤ} of C, defined by ρ^{(ℓ)}(c) = ω(c)^{ℓ}, one has equality of the intertwining numbers

(2.1)  ⟨ρ^{(ℓ)}, A_{X}⟩_{C} = ⟨ρ^{(ℓ)}, ℂ[X]⟩_{C}.

The coefficient a_{ℓ} of q^{ℓ} in X(q) mod q^{n} − 1 has the following wellknown expression in terms of n^{th} roots of unity:

(2.2)  a_{ℓ} = \frac{1}{n} ∑_{ω^{n}=1} ω^{−ℓ}X(ω).

Thus a_{ℓ} is exactly the left side of (2.1):

⟨ρ^{(ℓ)}, A_{X}⟩_{C} = \frac{1}{n} ∑_{c∈C} ω(c)^{−ℓ}X(ω(c)) = a_{ℓ}.

On the other hand, the right side of (2.1) can be computed using the fact that ℂ[X] is a permutation representation of C which decomposes into a sum over C-orbits O. Letting C_{O} denote the stabilizer subgroup within C of any element in the orbit O, one has

⟨ρ^{(ℓ)}, ℂ[X]⟩_{C} = ∑_{C− orbits O}⟨ρ^{(ℓ)}, Ind_{C_{O}}^{C}1⟩_{C}

= ∑_{C− orbits O}⟨Res_{C_{O}}^{C}ρ^{(ℓ)}, 1⟩_{C_{O}}

= ∑_{C− orbits O} \begin{cases}1 & if |C_{O}| divides ℓ \\ 0 & otherwise. \end{cases}\}

= |{C-orbits on X whose stabilizer-order divides ℓ}|.

Thus the equality (2.1) holds exactly when condition (iii) holds. □

Remark 2.2. The equivalence of conditions (i) and (ii) in Proposition 2.1 can also be proven easily via (number theoretic) Möbius inversion; see Proposition 4.1(ii).

Condition (iii) in Proposition 2.1 leads to the following representation theory paradigm, generalizing a paradigm for proving q = −1 phenomena followed in [39, 40]. Given a cyclic group C acting (faithfully) on the set [N], one obtains an embedding of C in GL_{N}(ℂ). Given a rational representation ρ : GL_{N}(ℂ) → GL(V), recall that its character χ_{ρ}(x_{1}, …, x_{N}) is defined to be the trace on V of any diagonalizable element in GL_{N}(ℂ) having eigenvalues x_{1}, …, x_{N}. Lemma 2.3. Let C be a cyclic group acting nearly freely on [N]. Let ρ : GL_{N}(ℂ) → GL(V) be a representation. Assume that there exists an integer m, and that V has a basis {v_{x}}_{x∈X} which is permuted (up to scalars) by C in the following way:

(2.3)  c(v_{x}) = ω(c)^{m} v_{c(x)} for all c ∈ C, x ∈ X.

Then the induced C-action on X and the (twisted) principal specialization

X(q) := q^{−m}χ_{ρ}(1, q, q^{2}, …, q^{N−1})

give rise to a triple (X, X(q), C) that exhibits the cyclic sieving phenomenon.

Proof. First note that when a cyclic subgroup C of order n acts freely on [N], the eigenvalues of any c in C are given by the multiset

1, ω(c), ω(c)^{2}, …, ω(c)^{N−1}.

Consequently, the character value of c acting in the representation ρ^{(−m)} ⊗ ρ will be

χ_{ρ^{(−m)}}(c) · χ_{ρ}(1, ω(c), ω(c)^{2}, …, ω(c)^{N−1}) = [X(q)]_{q=ω(c)} .

In other words, ρ^{(−m)} ⊗ ρ ≅ A_{X} as C-modules, as they have the same characters. On the other hand, the hypothesis (2.3) asserts an isomorphism ρ^{(−m)} ⊗ ρ ≅ ℂ[X] of C-modules, so the result follows from condition (iii) of Proposition 2.1. □

Remark 2.4. It should be noted that condition (i) of the Definition-Proposition of the introduction immediately implies the following: if (X, X(q), C) exhibits the cyclic sieving phenomenon, then (X, X(q), C′) exhibits the cyclic sieving phenomenon for any subgroup C′ of C.

3. First proof of Theorem 1.1: representation theory

The goal of this section is to give our first proof of Theorem 1.1, using the representation theory paradigm, Lemma 2.3.

First proof of Theorem 1.1. Let U = ℂ^{N} with standard basis {e_{i}}_{i=1}^{N}, affording the defining representation of GL_{N}(ℂ).

For part (a), let V be the k^{th} symmetric power Sym^{k}(U). This has an obvious basis of symmetric tensors indexed by k-multisubsets of [N]. As this basis is permuted by the cyclic group C, Lemma 2.3 applies with m = 0 to

X(q) = χ_{Sym^{k}(V)}(1, q, q^{2}, …, q^{N−1}) = [\begin{matrix}N + k − 1 \\ k \end{matrix}]_{q} ,

completing the proof.

For part (b), let V be the k^{th} exterior power ⋀^{k}(U), having an obvious basis of antisymmetric tensors ⋀_{i∈S} e_{i} indexed by k-subsets S of [N]. We claim that one can scale these basis elements so that the action of C obeys the hypotheses of Lemma 2.3 with m = \binom{k}{2}. Once this is established, one can apply the lemma to

X(q) = q^{−\binom{k}{2}}χ_{⋀^{k}(V)}(1, q, q^{2}, …, q^{N−1}) = [\begin{matrix}N \\ k \end{matrix}]_{q} ,

completing the proof.

It is easily seen that the claim reduces to following: for any k-subset S of [N] whose stabilizer subgroup within C ≅ C_{n} is the cyclic group C_{d}, the degree one representation of C_{d} acting on the 1-dimensional space spanned by ⋀_{i∈S} e_{i} coincides with Res_{C_{d}}^{C}ρ^{\binom{k}{2}}. To describe this degree one representation, uniquely decompose the subset S = ⊔_{i=0}^{b}S_{i} where S_{1}, …, S_{b} are the (non-empty) intersections of S with various n-cycles of a generator c for C in its action on [N], and S_{0} is either empty or possibly the singleton cycle of c. Note that either k = b · d or b · d + 1. Then the generator c^{\frac{n}{d}} of C_{d} acts on the span of ⋀_{i∈S} e_{i} by the scalar (−1)^{b(d−1)}. Letting ω := ω(c) be a primitive n^{th} root of unity, it then only remains to show that

ω^{\frac{n}{d} ·\binom{k}{2}} = (−1)^{b(d−1)}.

Note that

ω^{\frac{n}{d} ·\binom{k}{2}} = ω^{\frac{n}{d} ·\binom{bd}{2}}

since \binom{k}{2} is equal either to \binom{bd}{2} or \binom{bd}{2} + b · d, and (ω^{\frac{n}{d}})^{b·d} = 1. The result then follows from comparing the coefficient of x^{0} on the two sides of the identity

∏_{i=0}^{bd−1} (x − ω^{\frac{n}{d} i}) = (x^{d} − 1)^{b}.

□

4. Second proof of Theorem 1.1: explicit formulae

One can sometimes verify directly that the cyclic sieving phenomenon holds for a triple (X, X(q), C), by checking that both sides of condition (i) agree with an explicit formula. We use this method to give a second proof of Theorem 1.1.

Note that having done this, one gains explicit formulae for various other orbit-counts associated with the C-action on X. We collect some of these in Proposition 4.1 below, after recalling the Ramanujan sum [19, Th. 271, Th. 272]:

(4.1)  c_{d}(ℓ) := ∑_{ω a primitive d^{th} root of 1} ω^{ℓ} = ∑_{s|d,ℓ} μ (\frac{d}{s}) s,

where μ is the number-theoretic Möbius function. For example,

c_{d}(ℓ) := \begin{cases}ϕ(d) & if gcd(d, ℓ) = d, \\ μ(d) & if gcd(d, ℓ) = 1, \end{cases}

where ϕ is the classical Euler-phi function.

The proof of the following proposition is a straightforward exercise in (number-theoretic) Möbius inversion, which we omit. Proposition 4.1. Given a cyclic group C of order n acting on a finite set X, let

β(d) := |{x ∈ X : x is fixed by at least the subgroup C_{d} of C}|.

Then the number of C-orbits (i) in total is

\frac{1}{n} ∑_{d|n} ϕ(d)β(d).

(ii) whose stabilizer-order divides ℓ is

\frac{1}{n} ∑_{d|n} c_{d}(ℓ)β(d).

(iii) of size e, where n = de, is

\frac{1}{e} ∑_{s: d|s|n} μ (\frac{s}{d}) β(s).

The second proof of Theorem 1.1 requires some explicit evaluations of the q-binomial coefficient at roots for unity, such as may be found in [34, Problem 3.45(b)], and some of the other references^{1} cited in the following proposition. (NB: In the proposition below, and throughout the paper, a binomial coefficient containing any non-integer rational arguments is defined to be 0.) Proposition 4.2. Let n, k, a and d be positive integers, with d|n. Let ω be a primitive d^{th} root of unity. Then

(i) (see [12, 15, 24, 42])

[\begin{matrix}an + k − 1 \\ k \end{matrix}]_{q=ω} = \binom{\frac{an}{d} + \frac{k}{d} − 1}{\frac{k}{d}},

(ii)

[\begin{matrix}an \\ k \end{matrix}]_{q=ω} = (\frac{an}{d} ; \frac{k}{d}),

(iii) (see [5, Th. 3])

[\begin{matrix}an + k \\ k \end{matrix}]_{q=ω} = \binom{\frac{an}{d} + ⌊\frac{k}{d}⌋}{⌊\frac{k}{d}⌋},

(iv)

[\begin{matrix}an + 1 \\ k \end{matrix}]_{q=ω} = (\frac{an}{d} ; \frac{k}{d}) + ( \frac{an}{d} ; \frac{k−1}{d}).

1The authors thanks Matthias Beck for providing some of the references via [5].

Second proof of Theorem 1.1. Consider first the case where C acts freely on [N] for N = an. Then C acts also on the collection Ω of all k-multisets of [N]. Note that if c ∈ C has multiplicative order d, then it fixes exactly

β(d) = \binom{\frac{an}{d} + \frac{k}{d} − 1}{\frac{k}{d}}

k-multisubsets of [N]; those fixed by c come from a \frac{k}{d}-multiset of [\frac{an}{d}] by replacing occurrences of a single i with the set of d values in the same cycle of c as i. Comparing this with Proposition 4.2(i) verifies condition (i) of the Definition-Proposition from the introduction.

The other cases of the theorem are proven analogously; in each case condition (i) of the Definition-Proposition is easily verified since β(d) can be computed explicitly, and one then compares this with Proposition 4.2(ii), (iii), or (iv). □

Although not necessary for what follows, it is interesting to see how Proposition 4.2(i) and (ii) generalize to principal specializations of Schur functions. The generalization involves the notion of t-cores and t-quotients of a partition λ [23, Ex. I.1.8], [35, Exercise 7.59]. In a special case, it is implicit in [22, p. 128]; see also [23, Ex. I.3.17, Ex. I.5.24, Ex. I.7.8]. Theorem 4.3. Let t|N, and let q be a primitive t^{th} root of unity. Then s_{λ}(1, q, ⋯, q^{N−1}) is zero unless the t-core of λ is empty, in which case

s_{λ}(1, q, ⋯, q^{N−1}) = sgn(χ^{λ}(t^{k})) ∏_{i=0}^{t−1} s_{λ^{(i)}}(\underbrace{1, 1, ⋯, 1}_{\frac{N}{t}}),

where k = \frac{|λ|}{t}, the t-quotient of λ is (λ^{(0)}, λ^{(1)}, ⋯, λ^{(t−1)}), and χ^{λ} is the irreducible character of the symmetric group 𝔖_{kt} indexed by λ. Sketch of proof. The Schur function may be expanded in terms of the power sum symmetric functions p_{ρ} using characters of the symmetric group [23, §I.7]

(4.2)  s_{λ}(x) = ∑_{ρ} \frac{χ^{λ}(ρ)}{z_{ρ}}p_{ρ}(x).

Choosing x = (1, q, ⋯, q^{N−1}), where q is a primitive t^{th} root of unity gives p_{j}(x) = 0 unless t|j, in which case p_{j} = N. Thus in (4.2) we may assume that t divides each part of ρ. By the Murnaghan-Nakayama rule [23, Ex. I.7.4], if λ has non-empty t-core, then χ^{λ}(ρ) = 0, and thus s_{λ}(x) = 0. If λ does have empty t-core note that (4.2) implies the polynomial expansion

(4.3)  s_{λ}(1, q, ⋯, q^{N−1}) = N^{k} \frac{χ^{λ}(t^{k})}{t^{k}k!} + O(N^{k−1}).

We compare this with a different polynomial expansion in N. Suppose that λ has t-quotient (λ^{(0)}, λ^{(1)}, ⋯, λ^{(t−1)}) and empty t-core. By the hook-content formula [35, p. 374]

(4.4)  s_{λ}(1, q, ⋯, q^{N−1}) = q^{n(λ)} ∏_{x∈λ} \frac{1 − q^{N+c(x)}}{1 − q^{h(x)}} .

The hooks h(x) in λ which are divisible by t are t times the hooks of the t-quotients [23, Ex. I.1.8(d)], as are the contents.

Consequently

s_{λ}(1, q, ⋯, q^{N−1}) = R · ∏_{i=0}^{t−1} s_{λ^{(i)}}(\underbrace{1, 1, ⋯, 1}_{\frac{N}{t}})

where

R := q^{n(λ)} ∏_{\begin{matrix}x∈λ \\ c(x)≢0 mod t \end{matrix}}(1 − q^{c(x)})/ ∏_{\begin{matrix}x∈λ \\ h(x)≢0 mod t \end{matrix}}(1 − q^{h(x)})

is a quantity independent of N. Comparing this with (4.3) gives

R = χ^{λ}(t^{k}) \frac{∏_{i=0}^{t−1} ∏_{x∈λ^{(i)}} h(x)}{k!}.

From the results of [38], one has

χ^{λ}(t^{k}) = sgn(χ^{λ}(t^{k})) \frac{k!}{∏_{i=0}^{t−1} ∏_{x∈λ^{(i)}} h(x)}.

Thus R = sgn(χ^{λ}(t^{k})). □

The deduction of Proposition 4.2(i) from Theorem 4.3 with λ = k is immediate. To deduce Proposition 4.2(ii) from the case where λ = 1^{k} one needs

sgn (χ^{1^{k}}(t^{k/t})) = (−1)^{\frac{(t−1)k}{t}} .

We remark that Proposition 4.2(ii) generalizes easily to

(4.5)  [\begin{matrix}an \\ k_{1}, ⋯, k_{m} \end{matrix}]_{q=ω} = \binom{\frac{an}{d}}{\frac{k_{1}}{d} , ⋯, \frac{k_{m}}{d}}.

when ω is a primitive d^{th} root of unity and d|n. This then leads to a similar direct proof of the following proposition. When C acts on [N], it induces an action on k-flags of subsets

∅ ⊂ S^{k_{1}} ⊂ S^{k_{1}+k_{2}} ⊂ ⋯ ⊂ S^{k_{1}+···+k_{m−1}} ⊂ S^{k_{1}+···+k_{m−1}+k_{m}} = [N]

where |S^{k}| = k. Proposition 4.4. Let C = C_{n} act freely on [an]. Let X be the set of all k-flags of subsets with the induced C-action, and

X(q) = [\begin{matrix}an \\ k_{1}, ⋯, k_{m} \end{matrix}]_{q} .

Then (X, X(q), C) exhibits the cyclic sieving phenomenon. The previous proposition is the special case of Theorem 1.6 where W is a type A Weyl group W (A_{an−1}) = 𝔖_{an}. It turns out that Theorem 1.6 shows that the conclusion of Proposition 4.4 also holds when C acts only nearly freely but not freely; see the discussion following Theorem 8.2

A finite field analogue of Proposition 4.4 will be given in Theorem 9.4 below. Remark 4.5. In Proposition 4.2(i),(ii), if gcd(n, k) = 1, then the coefficients modulo q^{n}−1 in the sieved sums are constant (see the discussion following Conjecture 10.3 below). Necessary and sufficient conditions

for a general q-binomial coefficient [\begin{matrix}N \\ k \end{matrix}]_{q} to have constant coefficients

mod q^{m} − 1 have been given in [43], where a bijection between these classes is also given. An analogous bijection for the major index statistic on permutations [10] has been given in [4].

5. Cyclically equivalent plane trees

We return to Chapoton’s observation (Theorem 1.4) from the introduction, and strengthen it in Corollary 5.1 below.

Consider rooted plane trees having n non-root vertices. Two such trees will be considered cyclically equivalent if there is a cyclic rotation of the subtrees about the root taking one to the other. One can also speak of the symmetry group of such an equivalence class, namely the group of cyclic rotations of subtrees of the root which stabilizes any representative tree from the class. Corollary 5.1. The coefficient of q^{ℓ} in

[\begin{matrix}2n − 1 \\ n \end{matrix}]_{q} mod q^{n} − 1

is the number of cyclic equivalence classes of rooted plane trees with n non-root vertices whose symmetry group has order dividing ℓ.

For example, if n = 3, we have

[\begin{matrix}5 \\ 3 \end{matrix}]_{q} ≡ 4 + 3q + 3q^{2} mod q^{3} − 1.

The q^{0} coefficient of 4 above reflects the fact that among the 5 rooted plane trees with 3 non-root vertices, there are 4 cyclic equivalence classes, as two of the trees are cyclically equivalent. Furthermore, exactly one of these classes has a non-trivial C_{3} symmetry group.

Proof. We describe an encoding of rooted plane trees with n non-root vertices by n-multisubsets of [n]. Given such a plane tree, record a depth-first search by writing down a word w with n A’s and n B’s, recording moves along an edge away from (resp. toward) the root with an A (resp. B). Then let the multisubset of [n] have k_{i} occurrences of the letter i if there are k_{i} occurrences of the letter B between the i^{th} and (i + 1)^{st} occurrences of A.

It is easy to see that given an n-multisubset of [n], the corresponding word w encodes such a depth-first search of a plane tree if and only if w is a ballot sequence, that is, it has at least as many A’s as B’s in any initial segment. Furthermore, the ballot sequences corresponding to nmultisubsets of [n] in the same C_{n}-orbit correspond to cyclic rotations of the subtrees of the root.

Consequently, the result follows from Theorem 1.1(a) with k = n and N = 2n. □

Remark 5.2. It is also possible to deduce Theorem 1.4 from Theorem 1.1(b). Let k = n and N = 2n, with the generator of C_{n} acting by cyclically shifting by two the positions of a word w with n A’s and n B’s. The orbits consist of two copies of cyclically equivalent rooted plane trees, and

\frac{1}{n} ∑_{d|n} ϕ(d)\binom{2n/d}{n/d} = \frac{2}{n} ∑_{d|n} ϕ(d)\binom{2n/d − 1}{n/d} = 2a_{0}.

6. The phenomenon in Pólya theory

The goal of this section is to prove Theorem 6.1, an instance of the cyclic sieving phenomenon in Pólya theory that generalizes Theorem 1.1(a). The proof is a quick application of Lemma 2.3, generalizing the first proof of Theorem 1.1(a). We begin with some review of Pólya theory; see e.g. [35, §7.24].

Let G be a group of permutations acting on a finite set S. The Pólya cycle indicator for this action is the symmetric function

P_{G}(x_{1}, x_{2}, …) = \frac{1}{|G|} ∑_{g∈G} p_{λ(g)}

where λ(g) denotes the cycle type of g as it permutes S, and p_{λ} is the power-sum symmetric function corresponding to λ.

The action of G on S induces an action on the set [N]^{S} of N-colorings of S. Letting X = [N]^{S}/G denote the set of G-orbits of N-colorings, the cycle indicator has the following interpretation as the pattern inventory for these G-orbits:

(6.1)  P_{G}(x_{1}, x_{2}, …, x_{N}) = ∑_{G−orbits O} x^{O}

where x^{O} := ∏_{i=1}^{N} x_{i}^{m_{i}} if m_{i} denotes the number of occurrences of the color i in any representative of the orbit O. Theorem 6.1. With notation as above, assume C is a cyclic group acting nearly freely on the color set [N], and define

X(q) := P_{G}(1, q, q^{2}, …, q^{N−1}).

Then (X, X(q), C) exhibits the cyclic sieving phenomenon. Note that when |S| = k and G is the full symmetric group S_{k}, this theorem specializes to Theorem 1.1(a).

Proof. As in the proof of Theorem 1.1(a), let U := ℂ^{N} afford the defining representation of GL_{N}(ℂ). Consider the |S|-fold tensor power U^{⊗|S|}, with G acting on the tensor positions and GL_{N}(ℂ) acting diagonally. Let V = (U^{⊗|S|})^{G} be the G-invariant subspace for this action, which still affords a representation ρ of GL_{N}(ℂ). Then V has an obvious basis e_{O} of G-symmetrized basic tensors, indexed by the set of X = [N]^{S}/G of G-orbits O of N-colorings. Since such a basis element e_{O} is a GL_{N}(ℂ)-weight vector of weight x^{O}, equation (6.1) implies ρ has character χ_{ρ} = P_{G}. Since the cyclic group C permutes this basis, Lemma 2.3 with m = 0 implies the result. □

The N = 2 special case of the previous theorem is an interesting result of de Bruijn. Corollary 6.2. (de Bruijn [9]) Let G be a group permuting a finite set S, and X := 2^{S}/G the set of G-orbits on the subsets of S, Let X(q) be the generating function counting these G-orbits according to cardinality of any representative subset.

Then X(−1) counts the self-complementary G-orbits of subsets.

Proof. Identify a 2-coloring of S with the subset that receives the second color. Then P_{G}(1, q) = X(q) as defined in the corollary. Letting the cyclic group C of order 2 swap the colors amounts to swapping a subset S′ ⊂ S for its complement S − S′. □

Note that this corollary reduces to Theorem 1.5 from the introduction when S = \binom{[n]}{2} is the set of potential edges in a graph on vertex set [n], with S carrying an action of G = 𝔖_{n} induced from the action on the vertex set [n]. Here G-orbits of subsets of edges are identified with unlabelled graphs on n vertices.

Remark 6.3. Corollary 6.2 has a flavor very similar to that of Stembridge’s original examples [39]. In fact, the special case of Corollary 6.2 where S = [ab] and G = 𝔖_{a} ≀ 𝔖_{b} coincides with the (easy and wellknown) c = 1 special case of Stembridge’s observation concerning plane partitions inside an a × b × c box [39, §2.1].

7. The phenomenon in polygons: two instances

In this section we observe two instances of the cyclic sieving phenomenon involving convex polygons with cyclic actions by rotation; one for dissections of the polygon, the other for noncrossing partitions.

7.1. Polygon dissections. Consider dissections of a convex n-gon using k noncrossing diagonals. The formula for the number of such dissections has a long history; see [37]. It is given by

\begin{aligned}f(n, k) & = \frac{1}{n + k} \binom{n + k}{k + 1}\binom{n − 3}{k} \\ & = \frac{(n + k − 1)!}{k!(k + 1)!(n − k − 3)!(n − 1)(n − 2)}. \end{aligned}

It was noted by K. O’Hara and A. Zelevinsky that this last expression coincides with the number of standard Young tableaux of the shape (k + 1)^{2} 1^{n−k−3}, using the celebrated hook formula of Frame, Robinson and Thrall [35, Corollary 7.21.6].

A natural q-analogue of this formula is given by

(7.1)

f(n, k; q) := \frac{1}{[n + k]_{q}} [\begin{matrix}n + k \\ k + 1 \end{matrix}]_{q} [\begin{matrix}n − 3 \\ k \end{matrix}]_{q}

= \frac{[n + k − 1]!_{q}}{[k]!_{q}[k + 1]!_{q}[n − k − 3]!_{q}[n − 1]_{q}[n − 2]_{q}}

= q^{−\binom{n−k−1}{2}−k} ∑_{standard Young tableaux T of shape (k+1)^{2} 1^{n−k−3}} q^{maj(T)}

where the statistic maj(T) is the major index of T, defined to be the sum of values i for which i + 1 appears in a lower row of T than i. The last equality in (7.1) is a special case of a q-hook formula of Stanley [35, Corollary 7.21.5]. Here

\begin{aligned}[n]_{q} & := 1 + q + q^{2} + ⋯ + q^{n−1}, \\ [n]!_{q} & := [n]_{q}[n − 1]_{q} ⋯ [2]_{q}[1]_{q}. \end{aligned}

Theorem 7.1. Let X be the set of dissections of a convex n-gon using k noncrossing diagonals. Let the cyclic group C of order n act on X by cyclic rotations of the n-gon. Let X(q) := f(n, k; q).

Then (X, X(q), C) exhibits the cyclic sieving phenomenon.

Proof. We verify by direct calculation condition (i) of the Definition-Proposition from the introduction. Starting with the left side of condition (i), one must evaluate f(n, k; q) at q = ω, where ω is a primitive d^{th} root-of-unity for some divisor d of n. To do this, one examines the numerator and denominator factors in (7.1), and uses these facts:

• The factor [m]_{q} has a (simple) zero at q = ω if and only if d|m, d ≠ 1, and

• when m_{1} ≡ m_{2} mod d,

lim_{q→ω} \frac{[m_{1}]_{q}}{[m_{2}]_{q}} = \begin{cases}\frac{m_{1}}{m_{2}} & if m_{1} ≡ m_{2} ≡ 0 mod d \\ 1 & if m_{1} ≡ m_{2} ≢ 0 mod d. \end{cases}

The following computation is then a straightforward exercise (albeit somewhat tedious). For d ≥ 2 a divisor of n,

(7.2) [f(n, k; q)]_{q=ω} = \begin{cases}\frac{⌊ \frac{n+k−1}{2} ⌋!}{⌊ \frac{n−k−3}{2} ⌋!⌊ \frac{k}{2} ⌋!⌊ \frac{k+1}{2} ⌋! \frac{n−2}{2}} & if d = 2, \\ \frac{(\frac{n+k}{d} −1)!}{(\frac{n−k}{d} −1)!(\frac{k}{d})!^{2}} & if d ≥ 3 and d|k, \\ 0 & otherwise. \end{cases}

For the right side of condition (i), we must compute the number of dissections of the n-gon using k diagonals which are invariant under d-fold rotation. For this we utilize a result of Simion [31, Proposition 1] counting the number a_{n,p} of subdivisions of an n-gon, with n even, which are centrally symmetric, using p antipodal pairs of diagonals (and where a diameter of the n-gon is counted as one antipodal pair):

(7.3)  a_{n,p} = \binom{\frac{n}{2} − 1}{p}\binom{\frac{n}{2} + p − 1}{p}.

As one might expect from the formulae in (7.2), the calculation will proceed in two cases, d = 2 and d ≥ 3, with the case d = 2 broken into two subcases depending upon the parity of the number k of diagonals.

Case 1(a): d = 2 and k odd. In this case, a centrally symmetric subdivision with k diagonals will contain a unique diameter. This diameter can be chosen in \frac{n}{2} ways, and the rest of the subdivision is completely determined by the subdivision of the (\frac{n}{2} + 1)-gon using \frac{k−1}{2} diagonals on either side of the diameter. Hence the number of such subdivisions is

\frac{n}{2} · f (\frac{n}{2} + 1, \frac{k − 1}{2}) = \frac{\frac{n+k−1}{2}!}{\frac{n−k−3}{2}!\frac{k−1}{2}!\frac{k+1}{2}!\frac{n−2}{2}} ,

which agrees with (7.2) for d = 2 and k odd.

Case 1(b): d = 2 and k even. Here the set of subdivisions counted by a_{n, \frac{k}{2}} in (7.3) contains not only the subdivisions that we wish to count, but also those which have k −1 diagonals; since k −1 is odd, the latter can be enumerated as in Case 1(a). Hence the desired number of subdivisions with k diagonals is

a_{n, \frac{k}{2}} − \frac{n}{2} · f (\frac{n}{2} + 1, \frac{k − 2}{2})

= \binom{\frac{n}{2} − 1}{\frac{k}{2}}\binom{\frac{n}{2} + \frac{k}{2} − 1}{\frac{k}{2}} − \frac{\frac{n+k−2}{2}!}{(\frac{n−k}{2} − 1)! (\frac{k}{2} − 1)!\frac{k}{2}!\frac{n−2}{2}}

= \frac{\frac{n+k−2}{2}!}{\frac{n−k−4}{2}! (\frac{k}{2}!)^{2} \frac{n−2}{2}} ,

which agrees with (7.2) for d = 2 and k even.

Case 2: d ≥ 3. In the case d ≥ 3, it is easily seen that any diagonal in a subdivision with d-fold rotational symmetry lies in a free orbit under this action of C_{d}. Consequently k must be divisible by d, in agreement with (7.2).

When d divides k, the d-fold rotationally symmetric subdivisions using k diagonals decompose into two sets (similar in spirit to the cases of k odd and k even for d = 2): there are those for which the central polygon in the subdivision is a d-gon, and those for which it is not. In the former set, one can choose this central d-gon in \frac{n}{d} ways, and then the rest is completely determined by the subdivision of the (\frac{n}{d}+1)-gon using \frac{k}{d} −1 diagonals that lies in each \frac{2π}{d}-sector outside an edge of the central d-gon. Such subdivisions are therefore counted by \frac{n}{d} · f (\frac{n}{d} + 1, \frac{k}{d} − 1). In the latter set, one can employ an obvious bijection (described in the proof of [28, Proposition 4.2]) between subdivisions with d-fold rotational symmetry and those with central symmetry. This bijects the collection of d-fold symmetric subdivisions of an n-gon using k diagonals and no central d-gon to the collection of centrally symmetric subdivisions of a \frac{2n}{d}-gon using \frac{2k}{d} diagonals. The latter were counted in Case 1(b). Totalling the cardinalities of these two sets gives

\frac{n}{d} · f (\frac{n}{d} + 1, \frac{k}{d} − 1) + \frac{\frac{2n/d+2k/d−2}{2}!}{(\frac{2n/d−2k/d−4}{2})! (\frac{2k/d}{2}!)^{2} \frac{2n/d−2}{2}}

= \frac{(\frac{n+k}{d} − 1)!}{(\frac{n−k}{d} − 1)!\frac{k}{d}! (\frac{k}{d} − 1)! (\frac{n}{d} − 1)} + \frac{(\frac{n+k}{d} − 1)!}{(\frac{n−k}{d} − 2)! (\frac{k}{d}!)^{2} (\frac{n}{d} − 1)}

= \frac{(\frac{n+k}{d} − 1)!}{(\frac{n−k}{d} − 1)! (\frac{k}{d})!^{2}} ,

in agreement with (7.2) for d ≥ 3 and d dividing k. □

7.2. Noncrossing partitions. Kreweras defined noncrossing partitions in 1972, and they have been intensively studied since; see Simion [30] for a nice survey. To define them, number the vertices of a convex n-gon by 1, 2, …, n in a circular order. A partition of [n] is noncrossing if its blocks correspond to subsets of these vertices whose convex hulls are pairwise disjoint. Ordering the noncrossing partitions by refinement gives a ranked lattice called NC(n), in which a noncrossing partition having b blocks has rank n − b. The cardinality |NC(n)| is the Catalan number \frac{1}{n+1} \binom{2n}{n}, and the number of elements at rank k in NC(n) is the Narayana number [35, Exer. 6.36]:

N(n, k) = \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}.

A natural q-analogue of the Narayana number, introduced by Fürlinger and Hofbauer [14], is given by

(7.4)  N(n, k; q) := \frac{1}{[n]_{q}} [\begin{matrix}n \\ k \end{matrix}]_{q} [\begin{matrix}n \\ k + 1 \end{matrix}]_{q} q^{k(k+1)}.

This has many combinatorial interpretations; see Bränden [3]. Theorem 7.2. Let X be the set of noncrossing partitions in NC(n) with rank k. Let the cyclic group C of order n act on X by cyclic rotations of the n-gon. Let X(q) := N(n, k; q).

Then (X, X(q), C) exhibits the cyclic sieving phenomenon.

Proof. We proceed via direct calculation as in the proof of Theorem 7.1, starting with the left side of condition (i) in the Definition-Proposition from the introduction. A straightforward analysis of numerator and denominator factors in N(n, k; q) similarly shows that for d ≥ 2 dividing n,

(7.5)  [N(n, k; q)]_{q=ω} = \begin{cases}\frac{n−k}{n}(\frac{n}{d} ; \frac{k}{d})2 & if d|k, \\ \frac{k+1}{n}( \frac{n}{d} ; \frac{k+1}{d})2 & if d|k + 1, \\ 0 & otherwise. \end{cases}

For the right side of condition (i), we must compute the number of elements of NC(n) having rank k which are invariant under d-fold rotation. Note that when a noncrossing partition is d-fold rotationally symmetric, the cyclic group C_{d} acts freely on all blocks except possibly for the central block (if present). Thus the number of blocks b is congruent either to 0 or 1 modulo d. Since d|n and b = n − k, this means that there will be no such partitions unless d|k or d|k +1, in agreement with (7.5).

This leaves the two cases where d|k or d|k + 1. Here we will utilize a special case of a result of Athanasiadis and the first author [2, Lemma 4.4]: there are

• \binom{N}{p}^{2} centrally symmetric non-crossing partitions of [2N] that have p antipodal pairs of blocks (where a central block fixed under the antipodal map does not count as a pair),

and among these, • the fraction which have a central block is \frac{N−p}{N}, so

• the fraction with no central block is \frac{p}{N}.

Case 1: d|k, so that b ≡ 0 mod d. Here there is an obvious bijection [26, Proposition 1] to centrally symmetric noncrossing partitions of [\frac{2n}{d}] having \frac{2b}{d} blocks. The latter will have \frac{b}{d} antipodal pairs of blocks and no central block, and so are counted by the following formula with N = \frac{n}{d}, p = \frac{b}{d}:

\frac{p}{N} \binom{N}{p}^{2} = \frac{b/d}{n/d}(\frac{n}{d} ; \frac{b}{d})^{2} = \frac{n − k}{n} (\frac{n}{d} ; \frac{k}{d})^{2}.

This agrees with (7.5) for d|k.

Case 2: d|k + 1, so that b ≡ 1 mod d. As in Case 1, there is an obvious bijection to centrally symmetric noncrossing partitions of [\frac{2n}{d}] having \frac{2(b−1)}{d} + 1 blocks. The latter will have \frac{b−1}{d} antipodal pairs of non-central blocks and one central block, and so are counted by the following formula with N = \frac{n}{d}, p = \frac{b−1}{d}:

\frac{N − p}{N}\binom{N}{p}^{2} = \frac{\frac{n}{d} − \frac{b−1}{d}}{\frac{n}{d}} ( \frac{n}{d} ; \frac{b−1}{d})^{2} = \frac{k + 1}{n}( \frac{n}{d} ; \frac{k+1}{d})^{2}.

This agrees with (7.5) for d|k + 1. □

We remark that Theorems 7.1 and 7.2 are somewhat mysterious; it would be desirable to have a more illuminating or unified proof. It is perhaps worth mentioning that

• in both cases, the sets X are in bijection with lattice paths obeying various restrictions, and X(q) is a q-count by a major index statistic,

• in both cases, the cardinality |X| has a hook or hook-content formula, and X(q) has a q-hook or q-hook-content formula; see Bränden [3, Corollary 8],

• the cardinalities |X| = f(n, k) and |X| = N(n, k) give, respectively, the entries in the f-vector of the (n − 3)-dimensional associahedron and the h-vector of the (n − 1)-dimensional associahedron; see Simion [30].

8. Springer’s theorem on regular elements

In this section, we show how Theorem 1.1(b) generalizes to reflection groups.

Recall that an element of GL_{N}(ℂ) is a (pseudo-) reflection if it has finite order and fixes pointwise a (unique) hyperplane in ℂ^{N}, called its reflecting hyperplane. A finite reflection group is a subgroup W of GL_{N}(ℂ) generated by reflections. The theory of these groups is quite rich, including a classification by Shephard and Todd [32] and many results on their polynomials invariants. We introduce some terminology for the sake of stating a beautiful theorem of Springer [33] on regular elements, reformulated^{2} below in the fashion of Kraśkiewicz and Weyman [20].

Say that an element c in a finite reflection group W is a regular element if it has an eigenvector which does not lie on any of the reflecting hyperplanes for reflections in W. Let A denote the co-invariant algebra for W, that is, the quotient of the polynomial algebra ℂ[x_{1}, …, x_{n}] by the ideal generated the W -invariant polynomials of positive degree. Given a regular element c of order n, let C = ⟨c⟩ be the cyclic group that it generates, and ω a primitive n^{th} root of unity. We will regard A as a representation of W × C by having

• W act in the usual way on A (induced on the quotient from substitutions of variables), and

• C act by c(x_{i}) = ωx_{i}.

We will also regard the group algebra ℂ[W] as a representation of W × C by having W act by left-multiplication and C act by rightmultiplication.

Theorem 8.1. (Springer [33, Prop. 4.5], cf. [20]) The coinvariant algebra A and group algebra ℂ[W] are isomorphic as representations of W × C.

Given a graded ℂ-algebra R = ⨁_{d≥0} R_{d}, define its Hilbert series

Hilb(R, q) := ∑_{d≥0} dim_{ℂ} R_{d} q^{d}.

The following is the main result of this section, and generalizes Theorem 1.6 from the introduction.

Theorem 8.2. Let c be a regular element of order n in a finite reflection group W. Let C = ⟨c⟩, and let W′ be any subgroup of W. Let A^{W′} be the W′-invariant subalgebra of the coinvariant algebra A.

Then setting X := W/W′ and X(q) = Hilb(A^{W′}, q), one obtains a triple (X, X(q), C) that exhibits the cyclic sieving phenomenon.

2The result of Kraśkiewicz and Weyman [20] was stated and proved for the classical Weyl groups of types A,B,C,D. The authors thank A. Shepler for helping them to understand why Springer’s result implies that of [20] for reflection groups in general. They also thank F. Lübeck for checking via computer that the result of [20] holds for the exceptional irreducible finite reflection groups, before they had realized that this follows from Springer’s result!

To deduce Theorem 1.6 from this theorem, one needs the following fact [18, §IV.4]. For (W, S) a finite Coxeter system (i.e. a finite Euclidean reflection group) and any J ⊆ S, the minimum length coset representatives W^{J} for the parabolic subgroup W_{J} satisfy

W^{J}(q) := ∑_{w∈W^{J}} q^{ℓ(w)} = Hilb(A^{W_{J}} , q).

Proof of Theorem 8.2. Since Theorem 8.1 tells us that A and ℂ[W] are isomorphic as representations of W × C, restricting to their W′- invariant subspaces A^{W′} and ℂ[W]^{W′} gives isomorphic representations of C. By definition of the C-action on A^{W′} and the way we have defined X(q), one has that A^{W′} coincides with the C-representation A_{X} defined in Proposition 2.1. Meanwhile, ℂ[W]^{W′} is easily identified with the permutation representation on cosets ℂ[W/W′] ≅ ℂ[X]. Thus the result follows from Proposition 2.1 (iii). □

As mentioned in the introduction, Theorem 1.6 also gives the first case-free proof for all finite Coxeter groups of the following instance of the q = −1 phenomenon. It was originally proven via the classification of irreducible finite Coxeter systems by Eng [13], and later given a case-free proof for Weyl groups in [27]. Theorem 8.3. Let (W, S) be a finite Coxeter system, and J ⊆ S. Let w_{0} be the longest element in W. Then

[W^{J}(q)]_{q=−1} = |{cosets wW_{J} : w_{0}wW_{J} = wW_{J}}|.

In other words, setting X := W/W_{J}, X(q) := W^{J}(q), and C = ⟨w_{0}⟩ gives a triple (X, X(q), C) exhibiting the cyclic sieving phenomenon.

The theorem follows immediately from Theorem 1.6 and the following observation. Lemma 8.4. For any finite Coxeter system (W, S), the longest element w_{0} is a regular element in the sense of Springer.

Proof. Let V be the natural reflection representation for (W, S), and V^{+}, V^{−} the +1, −1 eigenspaces for w_{0} acting on V. Note that V^{+}, V^{−} are orthogonal complements of one another in V, because w_{0} acts as an orthogonal involution.

We will show that V^{−} contains a regular vector, that is, one which lies on no reflecting hyperplanes. Consider a typical reflecting hyperplane H, corresponding to some positive root α. Since w_{0}(α) is a negative root, we know that α is not fixed by w_{0}, so α ∉ V^{+} = (V^{−})^{⊥}. Thus V^{−} ⊄ α^{⊥} = H, and hence H ∩ V^{−} is a codimension one subspace inside V^{−}. As H ranges over all of the (finitely many) reflecting hyperplanes, these codimension one subspaces cannot exhaust V^{−}. Hence their complement within V^{−} consists of regular vectors, all of which are (−1)-eigenvectors for w_{0}. □

Springer conveniently classified all regular elements in the finite irreducible Coxeter groups [33, §5]. In type A, where W (A_{N−1}) = 𝔖_{N}, an element c is regular if and only if it acts nearly freely in the sense defined earlier. Thus Theorem 1.6 provides a third proof of Theorem 1.1(b), and also generalizes Proposition 4.4 to nearly free actions.

The Coxeter group W (B_{N}) of type B is the hyperoctahedral group, that is, the subgroup of GL_{N}(ℂ) consisting of monomial matrices in which the non-zero entries are all ±1. Springer’s classification shows that the only regular elements in W (B_{N}) are the powers of a Coxeter element. A Coxeter element in type B_{N} is conjugate to an element which cyclically permutes the N coordinates while introducing a sign change in one particular coordinate; call elements in this conjugacy class negative N-cycles. Say that an element conjugate in W (B_{N}) to a cyclic permutation of the N coordinates with no sign changes is a positive N-cycle. For each divisor n of 2N, there are regular elements in W (B_{N}) of order n, having form that depends upon the parity of n:

• For n an odd divisor of N, say N = an, a regular element of order n consists of a positive cycles each of size n.

• For n an even divisor of 2N, say 2N = an, a regular element of order n consists of a negative cycles each of size \frac{n}{2}. (When a = 1, such elements are the Coxeter elements for W (B_{n}).)

We will only consider here the maximal parabolic subgroups W_{J} of W (B_{N}). These have the form

W (A_{N−k−1}) × W (B_{k}) for k = 0, 1, …, N − 1.

One can identify their minimum length coset representatives W^{J} with the set of Q(N, k) all vectors in {+1, 0, −1}^{N} ⊂ ℂ^{N} having exactly k zero coordinates (see e.g. [36]). The actions of the appropriate cyclic groups C_{n} generated by regular elements turn out to be simply the restriction of their actions on ℂ^{N}. It is easily seen that

W^{J}(q) = [\begin{matrix}N \\ k \end{matrix}]_{q} (−q^{k+1}; q)_{N−k}

where we are using the the notation

(x; q)_{m} := (1 − x)(1 − qx)(1 − q^{2}x) ⋯ (1 − q^{m−1}x).

We immediately conclude the following from Theorem 1.6. Corollary 8.5. Let n be a divisor of 2N, and C the cyclic subgroup of W (B_{N}) generated by a regular element of order n. Let X := Q(N, k), and

X(q) := [\begin{matrix}N \\ k \end{matrix}]_{q} (−q^{k+1}; q)_{N−k}.

Then (X, X(q), C) exhibits the cyclic sieving phenomenon.

The previous discussion generalizes easily from W (B_{N}) to the reflection groups W = C_{m} ≀ 𝔖_{N}, consisting of the monomial matrices in GL_{N}(ℂ) whose non-zero entries are m^{th} roots of unity. Although these are not Coxeter groups, they do have distinguished sets of generators S coming from the fact that they are Shephard groups, that is the symmetry groups of regular complex polytopes [8].

Let W_{J} be a “maximal parabolic subgroup”, that is, J = S − {s} for some s ∈ S. This W_{J} will be isomorphic to W (A_{N−k−1}) × (C_{m} ≀ 𝔖_{k}) for some k = 0, 1, …, N − 1. One can check directly that the subring of W_{J}-invariants A^{W_{J}} in the coinvariant algebra has Hilbert series

Hilb(A^{W_{J}} , q) = [\begin{matrix}N \\ k \end{matrix}]_{q} \frac{(q^{(k+1)m}; q^{m})_{N−k}}{(q^{k+1}; q)_{N−k}} .

The role analogous to that of a Coxeter element is played here by an element c which cyclically permutes the N coordinates while introducing a scaling by ζ := e^{\frac{2πi}{m}} in one particular coordinate. It is easy to check that such an element c is regular of order mN, and hence any power of it is also regular. Thus for each divisor n of mN, there will be a cyclic subgroup C_{n} in C_{m} ≀ 𝔖_{N} generated by the regular element c^{\frac{mN}{n}}; although one could describe the cycle structure of these powers c^{\frac{mN}{n}}, as in type B_{N}, we omit these descriptions here.

One can check that the cosets W/W_{J} biject with the set Q^{(m)}(N, k) of vectors in ℂ^{N} having N −k coordinates which are m^{th} roots of unity, and k zero coordinates. One can also check that the C_{n}-action on cosets W/W_{J} coincides with the restriction of the action on ℂ^{N} to the vectors in Q^{(m)}(N, k). Corollary 8.6. Let n be a divisor of mN and C = C_{n} the cyclic subgroup of C_{m} ≀ 𝔖_{N} generated by c^{\frac{mN}{n}}. Let X := Q^{(m)}(N, k), and

X(q) := [\begin{matrix}N \\ k \end{matrix}]_{q} \frac{(q^{(k+1)m}; q^{m})_{N−k}}{(q^{k+1}; q)_{N−k}} .

Then (X, X(q), C) exhibits the cyclic sieving phenomenon.

As an example of Corollary 8.6 take

N = 4, m = 3, k = 0, n = 12,

so |Q^{(3)}(4, 0)| = 3^{4} = 81. Altering the notation slightly, one can identify the alphabet \{1, ζ, ζ^{2}\} where ζ = e^{\frac{2πi}{3}} with the alphabet \{0, 1, 2\} = ℤ/3ℤ. Then Q^{(3)}(4, 0) consists of words of length 4 in the alphabet ℤ/3ℤ, with the generator c of C_{12} acting as follows:

c(w_{1}, w_{2}, w_{3}, w_{4}) = (w_{4} + 1, w_{1}, w_{2}, w_{3}) mod 3.

It turns out that there are 6 free orbits of C_{12} on Q^{(3)}(4, 0), one orbit with stabilizer-order 2, namely {2200, 1220, 1122, 0112, 0011, 2001}, and one orbit with stabilizer-order 4, namely {2102, 0210, 1021}. This is reflected in the coefficients of the sieved polynomial

\begin{aligned}\frac{(q^{3}; q^{3})_{4}}{(q; q)_{4}} & ≡ 8 + 6q + 7q^{2} + 6q^{3} + 8q^{4} + 6q^{5} \\ & + 7q^{6} + 6q^{7} + 8q^{8} + 6q^{9} + 7q^{10} + 6q^{11} mod q^{12} − 1. \end{aligned}

9. Counting cyclic orbits over finite fields

In this section we propose q-analogues of some of the preceding formulae, involving orbit-counting of cyclic groups acting on (flags of) subspaces in finite vector spaces. We hope that the reader will forgive our re-use of the variable q in these new polynomials; since they have finite field interpretations when q is a prime power, we adhere to convention.

We first introduce some terminology for the finite field q-analogues of cyclic group actions. Let q be a prime power and let 𝔽_{q} denote the field with q elements. Consider the tower of extensions

𝔽_{q} ⊂ 𝔽_{q^{n}} ⊂ 𝔽_{q^{an}}

for positive integers a, n. The field extension 𝔽_{q^{an}} is in particular an 𝔽_{q}- vector space, in which the multiplicative group 𝔽_{q^{n}}^{×} of the subfield 𝔽_{q^{n}} acts 𝔽_{q}-linearly. Consequently, 𝔽_{q^{n}}^{×} acts on the set of all 𝔽_{q}-subspaces of 𝔽_{q^{an}}. In this action, the subgroup 𝔽_{q}^{×} acts trivially, so it descends to an action of the quotient group 𝔽_{q^{n}}^{×}/𝔽_{q}^{×}.

Note that 𝔽_{q^{n}}^{×}/𝔽_{q}^{×} is a cyclic group, since it is a quotient of the multiplicative group 𝔽_{q^{n}}^{×} (which is well-known to be cyclic). When a = 1, the cyclic permutation in 𝔖_{𝔽_{q^{n}}^{×}} corresponding to multiplication by a cyclic generator of 𝔽_{q^{n}}^{×} is called a Singer cycle (see e.g. [11]). Also note that the cardinality of 𝔽_{q^{n}}^{×}/𝔽_{q}^{×} is [n]_{q} = 1 + q + q^{2} + ⋯ + q^{n−1}, suggesting that 𝔽_{q^{n}}^{×}/𝔽_{q}^{×} is a natural q-analogue of the cyclic group C_{n}.

This analogy is tightened further by the following observation: just as every subgroup of C_{n} is of the form C_{d} for some d|n, the only subgroups of 𝔽_{q^{n}}^{×}/𝔽_{q}^{×} which can occur as the stabilizer of an 𝔽_{q}-subspace V in 𝔽_{q^{an}} are those of the form 𝔽_{q^{d}}^{×}/𝔽_{q}^{×} for some d|n. This is because the set {α ∈ 𝔽_{q^{n}} : αV ⊂ V } is easily seen to form a subfield of 𝔽_{q^{n}}, and every such subfield is of the form 𝔽_{q^{d}} for d|n. Note that the size of such a 𝔽_{q^{n}}^{×}/𝔽_{q}^{×}-orbit in which the stabilizer is 𝔽_{q^{d}}^{×}/𝔽_{q}^{×} will be

\frac{[n]_{q}}{[d]_{q}} = [e]_{q^{d}} where n = de.

Bearing this in mind, the following finite field analogue of Proposition 4.1 is also a straightforward exercise in Möbius inversion. Define q-analogues of the Euler-phi function and Ramanujan sum by

\begin{aligned}ϕ_{q}(m) & := ∑_{d|m} μ (\frac{m}{d}) [d]_{q} \\ c_{d}(ℓ; q) & := ∑_{s|d,ℓ} μ (\frac{d}{s}) [s]_{q}. \end{aligned}

Proposition 9.1. Let C = 𝔽_{q^{n}}^{×}/𝔽_{q}^{×} act on a finite set X of subspaces or flags of subspaces in 𝔽_{q^{n}}, and let

β_{q}(d) := |{x ∈ X : x is fixed by at least the subgroup 𝔽_{q^{d}}^{×}/𝔽_{q}^{×} of C}|.

Then the number of C-orbits (i) in total is

\frac{1}{[n]_{q}} ∑_{d|n} ϕ_{q}(d)β_{q}(d).

(ii) whose stabilizer-order divides [ℓ]_{q} is

\frac{1}{[n]_{q}} ∑_{d|n} c_{d}(ℓ; q)β_{q}(d).

(iii) of size [e]_{q^{d}}, where n = de, is

\frac{1}{[e]_{q^{d}}} ∑_{s: d|s|n} μ (\frac{s}{d}) β_{q}(s).

We now consider the case where X is the set of all k-flags of 𝔽_{q}- subspaces in 𝔽_{q^{an}}, for some composition k = (k_{1}, …, k_{m}) of an:

0 ⊂ V^{k_{1}} ⊂ V^{k_{1}+k_{2}} ⊂ ⋯ ⊂ V^{k_{1}+···+k_{m−1}} ⊂ V^{k_{1}+···+k_{m−1}+k_{m}} = 𝔽_{q^{an}} where dim_{𝔽_{q}} V^{k} = k. Note that such a k-flag is stabilized by the subgroup 𝔽_{q^{d}}^{×}/𝔽_{q}^{×} if and only if each 𝔽_{q}-subspace in the flag is actually an 𝔽_{q^{d}}-subspace. One concludes that in this situation

(9.1)  β_{q}(d) = [\frac{k_{1}}{d} , …, \frac{k_{m}}{d}^{\frac{an}{d}} ]_{q^{d}} .

From this and Proposition 9.1, we immediately deduce the following generalization of a recent result of Drudge [11], who proved the special case where a = 1, m = 2. Proposition 9.2. (cf. [11, Theorem 2.1]) When 𝔽_{q^{n}}^{×}/𝔽_{q}^{×} acts on the set of all k-flags of 𝔽_{q}-subspaces in 𝔽_{q^{an}}, the total number of 𝔽_{q^{n}}^{×}/𝔽_{q}^{×}-orbits is

(9.2)  O^{a,n,k}(q) := \frac{1}{[n]_{q}} ∑_{d| gcd(n,k)} ϕ_{q}(d) [\frac{k_{1}}{d} , ⋯, \frac{k_{m}}{d}^{\frac{an}{d}} ]_{q^{d}}

and the number of orbits of size [e]_{q^{d}} for n = de is

(9.3)  O_{d}^{a,n,k}(q) := \frac{1}{[e]_{q^{d}}} ∑_{s: d|s|n} μ (\frac{s}{d}) [\frac{k_{1}}{s} , ⋯, \frac{k_{m}}{s}^{\frac{an}{s}} ]_{q^{s}} .

The relevant cyclic sieving phenomenon that accompanies Proposition 9.2 requires the definition of an appropriate generating function^{3} X(t) for the set X of all k-flags in 𝔽_{q^{an}}. Definition 9.3. Given a composition k = (k_{1}, …, k_{m}) of N, let

σ_{s} := k_{1} + k_{2} + ⋯ + k_{s} for 1 ≤ s ≤ m

and define the (q, t)-multinomial coefficient

[\begin{matrix}N \\ k_{1}, …, k_{m} \end{matrix}]_{q,t} := \frac{∏_{i=1}^{N}(1 − t^{q^{N} −q^{N−i}})}{∏_{s=1}^{m} ∏_{i=1}^{k_{s}}(1 − t^{q^{σs}−q^{σs−i}})}.

Although not obvious at the moment, we will see that the (q, t)- multinomial coefficient is a polynomial in t with nonnegative integer coefficients, whose degree is a polynomial in q depending upon k. Also note that

lim_{t→1} [\begin{matrix}N \\ k_{1}, …, k_{m} \end{matrix}]_{q,t} = [\begin{matrix}N \\ k_{1}, …, k_{m} \end{matrix}]_{q} .

The (q, t)-multinomial with N = an is the appropriate choice to obtain the cyclic sieving phenomenon; see Theorem 9.4 below. The motivation for this choice was guided by the proof of Theorem 1.6, and results from invariant theory, as we now explain; we refer the reader to [29] for more details.

3The variable t is used in X(t) here rather than our previous variable q because the variable q is needed in its traditional role as the order of the field 𝔽_{q}.

Let G = GL_{N}(𝔽_{q}), which acts transitively on k-flags of 𝔽_{q}-subspaces in 𝔽_{q^{N}}. If P denotes the parabolic subgroup which fixes some particular k-flag, then X := G/P is identified with the set of k-flags. Letting S = 𝔽_{q^{n}}[x_{1}, …, x_{N}], a theorem of Hewett [17] describes the P -invariant polynomials S^{P} as a polynomial subalgebra of S with homogeneous generators of degree q^{σ_{s}} − q^{σ_{s}−i} for 1 ≤ s ≤ m, 1 ≤ i ≤ k_{s}. His result generalizes a well-known theorem of Dickson asserting that the G-invariant polynomials S^{G} form a polynomial subalgebra with homogeneous generators of degree q^{N} − q^{N−i} for 1 ≤ i ≤ N. A little commutative algebra of Cohen-Macaulay rings then implies that S^{P} is a free module over the polynomial subalgebra S^{G}. Consequently, the quotient ring S^{P} /(S_{+}^{G}), where (S_{+}^{G}) denotes the ideal in S^{P} generated by the G-invariants S_{+}^{G} of positive degree, has Hilbert series

Hilb(S^{P} /(S_{+}^{G}), t) = \frac{Hilb(S^{P} , t)}{Hilb(S^{G}, t)} = [\begin{matrix}N \\ k_{1}, …, k_{m} \end{matrix}]_{q,t} .

In [29], it is directly verified that if c ∈ 𝔽_{q^{n}}^{×} generates the subfield 𝔽_{q}(c) = 𝔽_{q^{d}}, and ω is a complex root of unity with the same multiplicative order as c, then

(9.4)  [\begin{matrix}N \\ k_{1}, …, k_{m} \end{matrix}]_{q,t=ω} = [\frac{k_{1}}{d} , …, \frac{k_{m}}{d}^{\frac{N}{d}} ]_{q^{d}} .

This can be used to prove the following. Theorem 9.4. Let C = 𝔽_{q^{n}}^{×} act on the set X of k-flags of 𝔽_{q}-subspaces

in 𝔽_{q^{an}}. Let X(t) = [\begin{matrix}an \\ k_{1}, …, k_{m} \end{matrix}]_{q,t}.

Then (X, X(t), C) exhibits the cyclic sieving phenomenon.

Proof. Let c ∈ C = 𝔽_{q^{n}}^{×} generate the extension 𝔽_{q}(c) = 𝔽_{q^{d}} ⊂ 𝔽_{q^{n}}. Then the k-flags stabilized by c are exactly those counted by β_{q}(d) in (9.1) above. Since the root of unity ω(c) has the same multiplicative order as c, comparing β_{q}(d) with (9.4) directly verifies condition (i) of the Definition-Proposition from the introduction. □

10. Polynomiality, nonnegativity, and a conjecture

In this section we examine the rational functions O_{d}^{a,n,k}(q) from Proposition 9.2 that count orbits of k-flags in 𝔽_{q^{an}}. We observe that they are actually polynomials in q with integer coefficients, and conjecture that these coefficients are nonnegative. We then discuss the easy special case where gcd(n, k) = 1, which is related to results of Haiman and Andrews.

Our main tool in this section is Proposition 10.1 below. Parts (i),(ii) give obvious criteria for a rational function in ℚ(q) to be a polynomial in ℚ[q] or ℤ[q]. Part (iii) abstracts an argument implicit in Andrews [1], giving a simple but useful criterion for a polynomial in ℤ[q] to lie in ℕ[q], that is, to have nonnegative coefficients. Proposition 10.1. Let f(q) ∈ ℚ(q).

(i) If f(N) ∈ ℤ for infinitely many N ∈ ℤ, then f(q) ∈ ℚ[q].

(ii) If furthermore f(q) = \frac{a(q)}{b(q)} where a(q), b(q) ∈ ℤ[q] and b(q) is

monic, then f(q) ∈ ℤ[q]. (iii) If furthermore f(q) = \frac{a(q)}{[n]_{q}} for some positive integer n, and

a(q) ∈ ℕ[q] has symmetric, unimodal coefficient sequence, then f(q) ∈ ℕ[q], and f(q) has symmetric coefficient sequence.

Proof. For (i), express f(q) = \frac{a(q)}{b(q)} with a(q), b(q) ∈ ℚ[q]. Divide b(q) into a(q) with quotient c(q) and remainder r(q). If D ∈ ℤ is a common denominator for the coefficients of c(q), then

Df(q) = Dc(q) + D\frac{r(q)}{b(q)}.

where Dc(q) ∈ ℤ[q]. Since Dc(N) ∈ ℤ for any integer N, we conclude that D\frac{r(N)}{b(N)} ∈ ℤ for infinitely many integers N. As r has lower degree

than b, one will have |D\frac{r(N)}{b(N)} | < 1 for |N| large, and hence D\frac{r(N)}{b(N)} = 0 for infinitely many N. Hence r(q) = 0, so f(q) = c(q) ∈ ℚ[q].

For (ii), note that when a(q), b(q) ∈ ℤ[q] and b(q) is monic, the quotient c(q) also lies in ℤ[q].

For (iii), since the polynomial f(q) = \frac{a(q)}{[n]_{q}} is a quotient of two polynomials with symmetric coefficients, it will also have symmetric coefficients. One has

deg(f) = deg(a) − n + 1 ≤ deg(a),

and hence by the symmetry of f(q), it suffices to show that the coefficient of q^{k} in f(q) is nonnegative for 0 ≤ k ≤ deg(a)/2. Rewrite

f(q) = (1 − q) a(q) · \frac{1}{1 − q^{n}} .

Since a(q) is symmetric and unimodal, the coefficient of q^{k} in (1−q) a(q) is nonnegative for 0 ≤ k ≤ deg(a)/2. Since \frac{1}{1−q^{n}} ∈ ℕ[[q]], the coefficient of q^{k} in f(q) is also nonnegative for 0 ≤ k ≤ deg(a)/2, as desired. □

Corollary 10.2. For any composition k of an,

O^{a,n,k}(q), O_{d}^{a,n,k}(q) ∈ ℤ[q].

Proof. Apply Proposition 10.1 (i),(ii) to Theorem 9.2. □

Conjecture 10.3. For any composition k of an,

O^{a,n,k}(q), O_{d}^{a,n,k}(q) ∈ ℕ[q].

Note that since

O^{a,n,k}(q) = ∑_{d|n} O_{d}^{a,n,k}(q), and

O_{d}^{a,n,k}(q) = O_{e}^{a,e, \frac{k}{d}} (q^{d}) if n = de,

this conjecture immediately reduces to the case d = 1, where O_{1}^{a,n,k}(q) counts free orbits.

Things simplify greatly, and Conjecture 10.3 is easy, when the action of 𝔽_{q^{n}}^{×}/𝔽_{q}^{×} is free. As in the discussion of Section 9, this will happen if and only if gcd(n, k) = 1: an element c ∈ 𝔽_{q^{n}}^{×} that generates the subfield 𝔽_{q}(c) = 𝔽_{q^{d}} for d|n will stabilize a k-flag if and only if it is actually a \frac{k}{d}-flag of 𝔽_{q^{d}}-subspaces, requiring d|k_{1}, …, k_{m}, n. So if gcd(n, k) = 1 this forces c to lie in 𝔽_{q}^{×}.

Thus when gcd(n, k) = 1, the 𝔽_{q^{n}}^{×}/𝔽_{q}^{×}-action is free, and every 𝔽_{q^{n}}^{×}/𝔽_{q}^{×}-orbit of k-flags has cardinality [n]_{q}. The number of 𝔽_{q^{n}}^{×}/𝔽_{q}^{×}- orbits of k-flags of 𝔽_{q}-subspaces in 𝔽_{q^{an}} is then

(10.1)  \frac{1}{[n]_{q}} [\begin{matrix}an \\ k_{1}, ⋯, k_{m} \end{matrix}]_{q} .

Since q-multinomial coefficients are known (see e.g. [36]) to have nonnegative, symmetric, and unimodal coefficient sequence (in q), Proposition 10.1(iii) immediately implies the following. Corollary 10.4. When gcd(n, k) = 1,

O^{a,n,k}(q) = O_{1}^{a,n,k}(q) = \frac{1}{[n]_{q}} [\begin{matrix}an \\ k_{1}, ⋯, k_{m} \end{matrix}]_{q} ∈ ℕ[q]

and has symmetric coefficient sequence. As O_{d}^{a,n,k}(q) is non-zero only for d = 1 when gcd(n, k) = 1, this verifies Conjecture 10.3 in this case. Question 10.5. What is a combinatorial interpretation for the nonnegative integer coefficients in (10.1) when gcd(n, k) = 1?

For m = 2 (i.e. the case of k-subspaces rather than k-flags), and a = 1, Corollary 10.4 becomes the assertion

(10.2)  \frac{1}{[n]_{q}} [\begin{matrix}n \\ k \end{matrix}]_{q} ∈ ℕ[q] if gcd(n, k) = 1.

This was proven by Andrews [1], where he implicitly introduced Proposition 10.1(iii). It also turns out to be a special case of the following result of Haiman, whose original proof is somewhat tricky. We deduce it here by Andrews’ method. Theorem 10.6. ([16, Prop. 2.5.1, 2.5.2, 2.5.3]) When gcd(n, |λ|) = 1,

\frac{1}{[n]_{q}} s_{λ}(1, q, ⋯, q^{n−1}) ∈ ℕ[q].

Proof. Nonnegativity, symmetry and unimodality of the coefficients of s_{λ}(1, q, ⋯, q^{n−1}) are well-known [23, Ex. I.8.4]. Polynomiality of the quotient is not hard: it is [16, Prop. 2.5.1] or can be established using n-cores as in the proof of Theorem 4.3, or as in [23, Ex. I.3.17(a)]). Now apply Proposition 10.1(iii). □

One can apply the same technique to generalize Corollary 10.4 to generating functions of the form \frac{W^{J} (q)}{[n]_{q}}. Recall that W^{J}(q) is the length generating function for minimal length coset representatives of a parabolic subgroup W_{J} in a finite Coxeter group W. Stanley [36] showed that when W is a Weyl group, W^{J}(q) always has symmetric, unimodal coefficient sequence. Thus Proposition 10.1(iii) applies to give the following. Corollary 10.7. Let (W, S) be a finite Weyl group, J ⊂ S, and n a positive integer.

If \frac{W^{J} (q)}{[n]_{q}} ∈ ℤ[q], then it is actually in ℕ[q]. In particular, for the classical Weyl groups of types B, D and their maximal parabolic subgroups W_{J}, one can check the conditions for polynomiality of \frac{W^{J} (q)}{[n]_{q}} case-by-case. One deduces the following.

Type B_{n}: If 0 ≤ k ≤ n − 1 and gcd(n, k) is a power of two, then

\frac{1}{[2n]_{q}} [\begin{matrix}n \\ k \end{matrix}]_{q} (−q^{k+1}; q)_{n−k} ∈ ℕ[q].

Type D_{n}: If 2 ≤ k ≤ n − 2 and both gcd(n − 1, k) and gcd(n − 1, k − 1) are powers of two, then

\frac{1}{[2(n − 1)]_{q}} [\begin{matrix}n \\ k \end{matrix}]_{q} (−q^{k}; q)_{n−k} ∈ ℕ[q].

We close with some remarks. Remark 10.8. An explicit statistic for the C_{n}-orbits on k-subsets of [n] with gcd(n, k) = 1 can be given to explain the nonnegativity of coefficients in (10.2) for k = 2, 3 or 4. We explain here such a statistic for k = 4 and comment on k = 2, 3 below.

Denote by (a, b, c, d) on a circle the spacing between the elements in the 4-subset of [n] when considered circularly modulo n. Then one may always rotate the circle to assume that a ≤ c and b < d (note that n − 4 = a + b + c + d must be odd, since gcd(n, 4) = 1), and this representation is unique. The statistic for this 4-tuple is a + 2b + 3c, that is, one can check that

∑_{\begin{matrix}0≤a≤c \\ 0≤b<d \\ a+b+c+d=n−4 \end{matrix}} q^{a+2b+3c} = \frac{1}{[n]_{q}} [\begin{matrix}n \\ 4 \end{matrix}]_{q} .

For k = 3, similarly denote by (a, b, c) the spacing between elements of the 3-subset of [n] (so a+b+c = n−3). Choose C_{n}-orbit representatives that have (a, b, c) first in lexicographic order in their orbit. Then the statistic a + 2b can be checked to work. For k = 2, the problem is trivial, since for n odd,

\frac{1}{[n]_{q}} [\begin{matrix}n \\ 2 \end{matrix}]_{q} = 1 + q^{2} + q^{4} + ⋯ + q^{n−3}.

Remark 10.9. Let a_{ℓ} be the coefficient of q^{ℓ} in [\begin{matrix}n \\ k \end{matrix}]_{q} mod q^{n} − 1.

Combining Theorem 1.1(b) with Propositions 4.1(ii), 4.2(ii) tells us that

(10.3)  a_{ℓ} = \frac{1}{n} ∑_{d|n} c_{d}(ℓ)(\frac{n}{d} ; \frac{k}{d}).

Note that this may be rephrased

(10.4)  a_{ℓ} = ⟨h_{(n−k,k)}, L_{n}^{(ℓ)}⟩

where h_{(n−k,k)} is the product h_{n−k}h_{k} of complete homogeneous symmetric functions, and

L_{n}^{(ℓ)} := \frac{1}{n} ∑_{d|n} c_{d}(ℓ)p_{d}^{n/d}

is the Frobenius characteristic of a representation of 𝔖_{n} induced from a character on an n-cycle [20], [21], [35, Exercise 7.88], generalizing the well-known Lie character when ℓ = 1.

Equation (10.4) also follows from results of Désarménien on q-Kostka polynomials, as we now explain. He proved [10, Theorem 2.2] that the coefficient of q^{ℓ} in

q^{n(λ)−n(λ′)}K_{λ,1^{n}}(q) mod q^{n} − 1

equals

\frac{1}{n} ∑_{d|n} χ^{λ}(d^{n/d})c_{d}(ℓ) = ⟨s_{λ}, L_{n}^{(ℓ)}⟩ .

Combining Désarménien’s result with the following facts

\begin{aligned}[\begin{matrix}n \\ j \end{matrix}]_{q} − [\begin{matrix}n \\ j − 1 \end{matrix}]_{q} & = q^{n((n−j,j))−n((n−j,j)′)}K_{(n−j,j),1^{n}}(q) \\ [\begin{matrix}n \\ k \end{matrix}]_{q} & = ∑_{j=0}^{k} ([\begin{matrix}n \\ j \end{matrix}]_{q} − [\begin{matrix}n \\ j − 1 \end{matrix}]_{q}) \\ h_{(n−k,k)} & = ∑_{j=0}^{k} s_{(n−j,j)} \end{aligned}

gives an alternate proof of (10.3).

The specialization a = 1, m = 2, ℓ = 0 in (9.2) is a q-version of the right side of (10.3). Perhaps an appropriate q-generalization of L_{n}^{(ℓ)} can be used to resolve Conjecture 10.3?

Acknowledgments

The authors thank Jay Goldman, Jon McCammond, and John Stembridge for useful comments and suggestions.

References

[1] G. Andrews, The Friedman-Joichi-Stanton monotonicity conjecture at primes. To appear, Amer. Math. Soc. DIMACS book series.

[2] C.A. Athanasiadis and V. Reiner, Noncrossing partitions for the group D_{n}.

   Preprint, 2003 (at www.math.umn.edu/ reiner/Papers/papers.html).

[3] P. Bränden, q-Narayana numbers and the flag h-vector of J(2 × n). ArXiv

   preprint math.CO/0211318, 2002.

[4] H. Barcelo, R. Maule, and S. Sundaram, On counting permutations by pairs of congruence classes of major index. Elec. J. Comb. 9 (2002), R21.

[5] M. Beck, A. Feingold, and M. Weiner, Arithmetic partition sums and orbits of Z_{n}^{k} under the symmetric group S_{k}. ArXiv preprint math.NT/0106267, 2001.

[6] F. Chapoton, http://www.lacim.uqam.ca/chapoton/arbres.html.

[7] C.W. Curtis and I. Reiner, Representation theory of finite groups and associative algebras. Pure and Applied Mathematics, Vol. XI. Wiley Interscience Publishers, New York, 1962.

[8] H.S.M. Coxeter, Regular complex polytopes, 2nd edition. Cambridge University Press, Cambridge, 1991.

[9] N.G. de Bruijn, Generalization of Pólya’s fundamental theorem in enumerative combinatorial analysis. Nederl. Akad. Wetensch. Proc. Ser. A 62 = Indag. Math. 21 (1959), 59–69.

[10] J. Désarménien, Étude modulo n des statistiques Mahoniennes. Sem. Loth. Comb. 22 (1990), 27–35.

[11] K. Drudge, On the orbits of Singer groups and their subgroups. Elec. J. Comb. 9 (2002), R15 (electronic).

[12] A. Elashvili, M. Jibladze, and D. Pataraia. Combinatorics of necklaces and “Hermite reciprocity”. J. Alg. Comb. 10 (1999), 173–186.

[13] O.D. Eng, Quotients of Poincaré polynomials evaluated at −1. J. Algebraic Combin. 13 (2001), 29–40.

[14] J. Fürlinger and J. Hofbauer, q-Catalan numbers. J. Combin. Theory Ser. A 40 (1985), 248–264.

[15] J. Fulman, Applications of the Brauer complex: card shuffling, permutation statistics, and dynamical systems. J. Algebra 243 (2001), 96–122.

[16] M. Haiman, Conjectures on the quotient ring by diagonal invariants. J. Alg. Comb. 3 (1994), 17–76.

[17] T.J. Hewett, Modular invariant theory of parabolic subgroups of GL_{n}(F_{q}) and the associated Steenrod modules. Duke Math. J. 82 (1996), 91–102.

[18] H. Hiller, Geometry of Coxeter groups. Research Notes in Mathematics 54, Pitman (Advanced Publishing Program), 1982.

[19] G. Hardy and E. Wright, An Introduction to the Theory of Numbers, 5th edition. Oxford, 1979.

[20] W. Kraśkiewicz and J. Weyman, Algebra of coinvariants and the action of a Coxeter element. Bayreuth Math. Schr. 63 (2001), 265–284.

[21] A. Lascoux, B. Leclerc, and J.-Y. Thibon, Ribbon tableaux, Hall-Littlewood functions, quantum affine algebras, and unipotent varieties. J. Math. Phys. 38 (1997), 1041–1068.

[22] D. Littlewood, The Theory of Group Characters. Oxford, 1940.

[23] I. G. Macdonald, Symmetric functions and Hall polynomials. Oxford University Press, Oxford, 1995.

[24] K. Ramanathan, Some applications of Ramanujan’s trigonometrical sum C_{m}(n). Indian Acad. Sci. Sect. A 20 (1944), 62–70.

[25] R.C. Read, On the number of self-complementary graphs and digraphs. J. London Math. Soc. 38 (1963), 99–104.

[26] V. Reiner, Non-crossing partitions for classical reflection groups, Disc. Math. 177 (1997), 195–222.

[27] V. Reiner, Note on a theorem of Eng. Ann. Comb. 6 (2002), 117–118.

[28] V. Reiner, Equivariant fiber polytopes. Doc. Math. 7 (2002), 113–132 (electronic).

[29] V. Reiner, D. Stanton, and P. Webb, Springer’s theorem for modular coinvariants of GL_{n}(𝔽_{q}). In preparation.

[30] R. Simion, Noncrossing partitions. Formal power series and algebraic combinatorics (Vienna, 1997). Discrete Math. 217 (2000), 367–409.

[31] R. Simion, A type-B associahedron. Adv. Appl. Math. 30 (2003), 2–25.

[32] G.C. Shephard and J.A. Todd, Finite unitary reflection groups. Canadian J. Math. 6 (1954), 274–304.

[33] T.A. Springer, Regular elements of finite reflection groups. Invent. Math. 25 (1974), 159–198.

[34] R. P. Stanley, Enumerative Combinatorics Volume 1. Wadsworth, Monterey, 1986.

[35] R. P. Stanley, Enumerative Combinatorics Volume 2. Cambridge University Press, Cambridge, 1999.

[36] R. P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property. SIAM J. Alg. Disc. Meth. 1 (1980), 168–184.

[37] R. P. Stanley, Polygon dissections and standard Young tableaux. J. Combin. Theory Ser. A 76 (1996), 175–177.

[38] D. Stanton and D. White, A Schensted algorithm for rim hook tableaux. J. Combin. Theory Ser. A 40 (1985), 211–247.

[39] J.R. Stembridge, Some hidden relations involving the ten symmetry classes of plane partitions. J. Combin. Theory Ser. A 68 (1994), 372–409.

[40] J.R. Stembridge, On minuscule representations, plane partitions and involutions in complex Lie groups. Duke Math. J. 73 (1994), 469–490.

[41] J.R. Stembridge, Canonical bases and self-evacuating tableaux. Duke Math. J. 82 (1996), 585–606.

[42] Von Sterneck, Sitzber. Akad. Wiss. Wien. Math. Naturw. Class 111 (1902), 1567–1901.

[43] S. Wagon and H. Wilf, When are subset sums equidistributed modulo m? Elec. J. Comb. 1 (1994), R3 (electronic).

  E-mail address: (reiner,stanton,white)@math.umn.edu

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA