Abstract
Orbit harmonics is a tool in combinatorial representation theory which promotes the (ungraded) action of a linear group G on a finite set X to a graded action of G on a polynomial ring quotient by viewing X as a G-stable point locus in \({\mathbb {C}}^n\). The cyclic sieving phenomenon is a notion in enumerative combinatorics which encapsulates the fixed-point structure of the action of a finite cyclic group C on a finite set X in terms of root-of-unity evaluations of an auxiliary polynomial X(q). We apply orbit harmonics to prove cyclic sieving results.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let X be a finite set with an action of a finite cyclic group \(C = \langle c \rangle \) and let \(\omega = \exp (2 \pi i / |C|)\). Let \(X(q) \in {\mathbb {Z}}_{\ge 0}[q]\) be a polynomial with nonnegative integer coefficients. The triple (X, C, X(q)) exhibits the cyclic sieving phenomenon [17] if for all \(r \ge 0\) we have
More generally, if X carries an action of a product \(C_1 \times C_2 = \langle c_1 \rangle \times \langle c_2 \rangle \) of two finite cyclic groups and \(X(q,t) \in {\mathbb {Z}}_{\ge 0}[q,t]\), the triple \((X, C_1 \times C_2, X(q,t))\) exhibits the bicyclic sieving phenomenon [2] if for all \(r, s \ge 0\) we have
where \(\omega _1 = \exp (2 \pi i / |C_1|)\) and \(\omega _2 = \exp (2 \pi i / |C_2|)\). In typical sieving results, X is a set of combinatorial objects, the operators \(c, c'\) act on X by natural combinatorial actions, and X(q) or X(q, t) are generating functions for natural (bi)statistics on the set X.
Although ostensibly in the domain of enumerative combinatorics, the most desired proofs CSPs are algebraic. One seeks a representation-theoretic model for the action of C on X by finding a \({\mathbb {C}}\)-vector space V carrying an action of a group G and possessing a distinguished basis \(\{ e_x \,:\, x \in X \}\) indexed by elements of the set X. The action of the generator \(c \in C\) on X is modeled by a group element \(g \in G\) which satisfies \(g \cdot e_x = e_{c \cdot x}\) for all \(x \in X\). If \(\chi : G \rightarrow {\mathbb {C}}\) is the character of the G-module V, then
for all \(r \ge 0\), transferring the enumerative problem of counting \(|X^{c^r}|\) to the algebraic problem of calculating \(\chi (g^r)\). These algebraic proofs are desired over brute force enumerative proofs because they give representation-theoretic insight about why a sieving result should hold.
In this article we use the orbit harmonics method of zero-dimensional algebraic geometry to prove CSPs. The results proven in this fashion will have the ‘nice’ representation-theoretic proofs as outlined above. This approach unifies various CSPs coming from actions on word-like objects and ‘quotients’ thereof. The idea is to model the set X geometrically as a finite point locus in \({\mathbb {C}}^n\). The relevant algebra has roots in (at least) the work of Kostant [12] and goes as follows.
The polynomial ring \({\mathbb {C}}[{\mathbf {x}}_n] := {\mathbb {C}}[x_1, \dots , x_n]\) may be naturally viewed as the coordinate ring of polynomial functions \(f: {\mathbb {C}}^n \rightarrow {\mathbb {C}}\). This identification gives rise to an action of the general linear group \({\mathrm {GL}}_n({\mathbb {C}})\) on \({\mathbb {C}}[{\mathbf {x}}_n]\) by linear substitutions:
By restriction, any subgroup of \({\mathrm {GL}}_n({\mathbb {C}})\) also acts on \({\mathbb {C}}[{\mathbf {x}}_n]\).
Let \(X \subseteq {\mathbb {C}}^n\) be a finite set of points which is closed under the action of \(W \times C\) where
-
\(W \subseteq {\mathrm {GL}}_n({\mathbb {C}})\) is a (finite) complex reflection group and
-
C is a finite cyclic group acting on \({\mathbb {C}}^n\) by root-of-unity scaling.
Let
be the ideal of polynomials in \({\mathbb {C}}[{\mathbf {x}}_n]\) which vanish on X. Since X is finite, Lagrange Interpolation affords a \({\mathbb {C}}\)-algebra isomorphism
where \({\mathbb {C}}[X]\) is the algebra of all functions \(X \rightarrow {\mathbb {C}}\). Since X is \(W \times C\)-stable, (5) is also an isomorphism of ungraded \(W \times C\)-modules.
For any nonzero polynomial \(f \in {\mathbb {C}}[{\mathbf {x}}_n]\), let \(\tau (f)\) be the highest degree component of f. That is, if \(f = f_d + \cdots + f_1 + f_0\) with \(f_i\) homogeneous of degree i and \(f_d \ne 0\), we set \(\tau (f) := f_d\). Given our locus X with ideal \({\mathbf {I}}(X)\) as above, we define a homogeneous ideal \({\mathbf {T}}(X)\) by
The ideal \({\mathbf {T}}(X)\) is the associated graded ideal of \({\mathbf {I}}(X)\) and is often denoted \(\mathrm {gr \,} {\mathbf {I}}(X)\). By construction \({\mathbf {T}}(X)\) is homogeneous and stable under \(W \times C\). The isomorphism (5) extends to an isomorphism of \(W \times C\)-modules
where \({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X)\) has the additional structure of a graded \(W \times C\)-module on which C acts by scaling in each fixed degree.
The action of \(W \times C\) on X coincidesFootnote 1 with the \(W \times C\)-action on the natural basis \(\{ e_x \,:\, x \in X \}\) of \({\mathbb {C}}[X]\) of indicator functions \(e_x: X \rightarrow {\mathbb {C}}\) given by
If the graded W-isomorphism type of \({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X)\) is known, the isomorphism (7) and Springer’s theorem on regular elements [20] (see Theorem 1) give bicyclic sieving results for the set X under product groups of the form \(C' \times C\) where \(C' \subseteq W\) is the subgroup generated by a regular element in W. Furthermore, if \(G \subseteq W\) is any subgroup, the set X/G of G-orbits in X carries a residual action of C, and the Hilbert series of the G-invariant subspace \(({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X))^G\) is a cyclic sieving polynomial for the action of C on X/G. By varying
-
the choice of point locus X and
-
the choice of subgroup G of W
a variety of CSPs can be obtained. This method has been used [1, 7] to prove CSPs before; the purpose of this paper is to make its approach and utility explicit.
The procedure \(X \leadsto {\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X)\) which promotes the (ungraded) locus X to the graded module \({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X)\) is known as orbit harmonics. Generators for the ideal \({\mathbf {T}}(X)\) may be found by computer from the point set X as follows. The ideal \({\mathbf {I}}(X)\) may be expressed as either an intersection or a product
of ideals corresponding to the points \((\alpha _1, \dots , \alpha _n)\) belonging to \(X \subseteq {\mathbb {C}}^n\) . If \(\{ g_1, g_2, \dots , g_r \}\) is a Gröbner basis for \({\mathbf {I}}(X)\) with respect to any graded monomial order \(\prec \) (i.e. we have \(m \prec m'\) whenever \(m, m'\) are monomials in \({\mathbb {C}}[{\mathbf {x}}_n]\) with \(\deg m < \deg m'\)), then \({\mathbf {T}}(X)\) will be generated by \(\{ \tau (g_1), \tau (g_2), \dots , \tau (g_r) \}\). While this facilitates the investigation by computer of a graded quotient \({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X)\) corresponding to a point locus X, a generating set of \({\mathbf {T}}(X)\) obtained in this way can be messy and not so enlightening. Finding a nice generating set of \({\mathbf {T}}(X)\) is often necessary to understand the graded W-isomorphism type of \({\mathbb {C}}[X]/{\mathbf {T}}(X)\).
In this paper we will focus mostly on the reflection group \(W = {\mathfrak {S}}_n\) acting by coordinate permutation on \({\mathbb {C}}^n\). This setting has received substantial attention in algebraic combinatorics. By making an appropriate choice of an \({\mathfrak {S}}_n\)-stable locus X, orbit harmonics has produced graded \({\mathfrak {S}}_n\)-modules which give algebraic models for various intricate objects in symmetric function theory [9,10,11]. It is our hope that this article inspires future connections between orbit harmonics and cyclic sieving.
We use orbit harmonics to reprove and unify a variety of known cyclic sieving results [1,2,3, 17, 18], prove some cyclic sieving results which seem to have escaped notice, and give new proofs of some results [15, 20] which are not per se in the field of cyclic sieving. It would be interesting to see if our methods apply to the notion of dihedral sieving due to Swanson [22] (see also [16]).
The remainder of this paper is organized as follows. In Sect. 2 we give background on complex reflection groups and the representation theory of \({\mathfrak {S}}_n\). In Sect. 3 we describe how orbit harmonics gives a new perspective on classical results of Springer and Morita–Nakajima. We also state our main tool for proving sieving results from point loci (Theorem 3). In Sect. 4 we apply Theorem 3 to point loci corresponding to arbitrary, injective, and surjective functions between finite sets. In Sect. 5 we apply Theorem 3 to other combinatorial loci and conclude in Sect. 6 with possible future directions.
2 Background
2.1 Combinatorics
A weak composition of n is a finite sequence \(\mu = (\mu _1, \mu _2, \dots )\) of nonnegative integers which sum to n. We write \(\mu \models _0 n\) to indicate that \(\mu \) is a weak composition of n and denote by \(m_i(\mu )\) the multiplicity of i as a part of \(\mu \). A composition of n is a weak composition which contains only positive parts; we write \(\mu \models n\) to mean that \(\mu \) is a composition of n.
A partition of n is a composition \(\lambda \) of n consisting of weakly decreasing positive parts. We write \(\lambda \vdash n\) to indicate that \(\lambda \) is a partition of n and \(|\lambda | = n\) for the sum of the parts of \(\lambda \). We also write \(\ell (\lambda )\) for the number of parts of \(\lambda \) and define the number \(b(\lambda ) := \sum _{i \ge 1} (i-1) \cdot \lambda _i\).
Given a partition \(\lambda = (\lambda _1, \lambda _2, \dots )\), the Young diagram of \(\lambda \) consists of \(\lambda _i\) left-justified cells in row i. The Ferrers diagram of \((3,2,2) \vdash 7\) is shown on the left below. A tableau T of shape \(\lambda \) is a filling \(T: \lambda \rightarrow {\mathbb {Z}}_{> 0}\) of these boxes with positive integers. The content of a tableau T is the weak composition \((\mu _1, \mu _2, \dots )\) where \(\mu _i\) is the multiplicity of i in T and the shape \({\mathrm {shape}}(T)\) of T is the partition \(\lambda \). A tableau T is semistandard if its entries increase weakly across rows and strictly down columns. A semistandard tableau of shape (3, 2, 2) and content (2, 0, 2, 2, 1) is shown in the middle below. The Kostka number \(K_{\lambda ,\mu }\) is the number of semistandard tableaux of shape \(\lambda \) with content \(\mu \). A standard tableau is a semistandard tableau with content \((1, 1, \dots )\). A standard tableau of shape (3, 2, 2) is shown on the right below.
A descent in a word \(w = w_1 \dots w_n\) over the positive integers is an index i with \(w_i > w_{i+1}\). The descent number \({\mathrm {des}}(w)\) is the number of descents in w and the major index \({\mathrm {maj}}(w)\) is the sum of the descents in w. Analogously, if T is a standard tableau with n boxes, an index \(1 \le i \le n-1\) is a descent of T if i appears in a strictly higher row than \(i+1\) in T. The descent number \({\mathrm {des}}(T)\) is the number of descents in T and the major index \({\mathrm {maj}}(T)\) be the sum of the descents in T. The standard tableau T shown above has descents 2, 3, 5, and 6 so that \({\mathrm {des}}(T) = 4\) and \({\mathrm {maj}}(T) = 2 + 3 + 5 + 6 = 16\).
The fake degree polynomial \(f^{\lambda }(q)\) corresponding to a partition \(\lambda \vdash n\) is the generating function for major index over the set \({\mathrm {SYT}}(\lambda )\) of standard tableaux of shape \(\lambda \):
The polynomial \(f^{\lambda }(q)\) may be efficiently computed using the q-hook formula
where the product is over the cells c in the Young diagram of \(\lambda \) and \(h_c\) is the hook length at the cell c. Here and throughout we use the standard q-analogs of numbers, factorials, binomial, and multinomial coefficients:
where \(\mu = (\mu _1, \dots , \mu _r)\) is a weak composition of n.
2.2 Symmetric functions
We denote by \(\Lambda = \bigoplus _{d \ge 0} \Lambda _d\) the graded ring of symmetric functions in an infinite variable set \({\mathbf {x}}= (x_1, x_2, \dots )\) over the ground field \({\mathbb {C}}(q)\). Here \(\Lambda _d\) denotes the subspace of \(\Lambda \) consisting of homogeneous symmetric functions of degree d. Two important elements of \(\Lambda _d\) are the homogeneous and elementary symmetric functions
By restricting \(h_d({\mathbf {x}})\) and \(e_d({\mathbf {x}})\) to a finite variable set \({\mathbf {x}}_n = \{x_1, \dots , x_n \}\), we obtain the homogeneous and elementary symmetric polynomials \(h_d({\mathbf {x}}_n)\) and \(e_d({\mathbf {x}}_n)\).
Bases of \(\Lambda _n\) are indexed by partitions of n. For a partition \(\lambda \vdash n\), we let
denote the associated homogeneous symmetric function, elementary symmetric function, Schur function, and Hall–Littlewood symmetric function. For any partition \(\lambda = (\lambda _1 \ge \lambda _2 \ge \ldots )\) the h- and e-functions are defined by
and the Schur function is given by
where the sum is over all semistandard tableaux T of shape \(\lambda \) and \({\mathbf {x}}^T\) is shorthand for the monomial \(x_1^{\alpha _1} x_2^{\alpha _2} \ldots \) where \(\alpha _i\) is the number of i’s in the tableau T. The \(\widetilde{H}_{\lambda }({\mathbf {x}};q)\) may be defined as
where \(\widetilde{K}_{\nu ,\lambda }(q)\) is the (modified) Kostka-Foulkes polynomial which is the generating function of the cocharge statistic on the semistandard tableaux of shape \(\nu \) and content \(\lambda \). We will not use the (somewhat involved) cocharge statistic explicitly in this paper; see e.g. [18] for its definition.
2.3 Representation theory of \({\mathfrak {S}}_n\)
A class function on a finite group G is a map \(\varphi : G \rightarrow {\mathbb {C}}\) which is constant on conjugacy classes. The set R(G) of all class functions \(G \rightarrow {\mathbb {C}}\) forms a \({\mathbb {C}}\)-algebra under pointwise addition and multiplication. We let \(\langle -, - \rangle _G\) be the standard inner product on these class functions:
If V, W are finite-dimensional G-modules with characters \(\chi _V, \chi _W: G \rightarrow {\mathbb {C}}\), we extend this notation by setting \(\langle V, W \rangle _G := \langle \chi _V, \chi _W \rangle _G\).
Irreducible representations of the symmetric group \({\mathfrak {S}}_n\) are in one-to-one correspondence with partitions \(\lambda \vdash n\). If \(\lambda \) is a partition, we let \(S^{\lambda }\) be the corresponding irreducible module. If V is any finite-dimensional \({\mathfrak {S}}_n\)-module, there are unique multiplicities \(c_{\lambda }\) so that \(V \cong \bigoplus _{\lambda \vdash n} c_{\lambda } S^{\lambda }\). The Frobenius image of V is the symmetric function
For example, if \(\mu \vdash n\) and \({\mathfrak {S}}_{\mu } := {\mathfrak {S}}_{\mu _1} \times {\mathfrak {S}}_{\mu _2} \times \cdots \) is the corresponding parabolic subgroup of \({\mathfrak {S}}_n\), the coset representation
has Frobenius image \(h_{\mu }({\mathbf {x}})\).
We will consider graded vector spaces and representations. If \(V = \bigoplus _{d \ge 0} V_d\) is any graded vector space, its Hilbert series is
If \(V = \bigoplus _{d \ge 0} V_d\) is a graded \({\mathfrak {S}}_n\)-module, its graded Frobenius image is
2.4 Complex reflection groups
The general linear group \({\mathrm {GL}}_n({\mathbb {C}})\) acts naturally on \(V := {\mathbb {C}}^n\). An element \(t \in {\mathrm {GL}}_n({\mathbb {C}})\) is a reflection if its fixed space \(V^t := \{v \in V \,:\, t \cdot v = v \}\) has codimension one in V. A finite subgroup \(W \subseteq {\mathrm {GL}}_n({\mathbb {C}})\) is a reflection group if it is generated by reflections.
Let \(W \subseteq {\mathrm {GL}}_n({\mathbb {C}})\) be a complex reflection group. The full general linear group \({\mathrm {GL}}_n({\mathbb {C}})\) acts on the polynomial ring \({\mathbb {C}}[{\mathbf {x}}_n] := {\mathbb {C}}[x_1, \dots , x_n]\) by linear substitutions, and by restriction \({\mathbb {C}}[{\mathbf {x}}_n]\) is a graded W-module. Let \({\mathbb {C}}[{\mathbf {x}}_n]^W_+ \subseteq {\mathbb {C}}[{\mathbf {x}}_n]\) be the subspace of W-invariants with vanishing constant term and let \(\langle {\mathbb {C}}[{\mathbf {x}}_n]^W_+ \rangle \subseteq {\mathbb {C}}[{\mathbf {x}}_n]\) be the ideal generated by this subspace. The coinvariant ring attached to W is the quotient
This is a graded W-module.
For any irreducible W-module U, the fake degree polynomial \(f^U(q)\) is the graded multiplicity of U in the coinvariant ring. That is, we have
where \(m_{U,d}\) is the multiplicity of U in the W-module given by the degree d piece \((R_W)_d\) of \(R_W\). When \(W = {\mathfrak {S}}_n\) is the symmetric group of \(n \times n\) permutation matrices, the irreducible representations of W correspond to partitions \(\lambda \vdash n\), and \(f^{S^{\lambda }}(q) = f^{\lambda }(q)\) specializes to our earlier definition.
Let \(W \subseteq {\mathrm {GL}}_n({\mathbb {C}})\) be a complex reflection group acting on \(V = {\mathbb {C}}^n\). An element \(c \in W\) is a regular element if it possesses an eigenvector \(v \in V\) which has full W-orbit, or equivalently the stabilizer \(W_v := \{ w \in W \,:\, w \cdot v = v \}\) consists of the identity \(e \in W\) alone. Such an eigenvector v is called a regular eigenvector and if \(\omega \in {\mathbb {C}}^{\times }\) is such that \(w \cdot v = \omega v\), the order of \(w \in W\) will equal the order of \(\omega \) in the multiplicative group \({\mathbb {C}}^{\times }\). For example, when \(W = {\mathfrak {S}}_n\) a permutation \(w \in W\) is a regular element if and only if it is a power of an n-cycle or an \((n-1)\)-cycle.
2.5 Regular sequences
A length n sequence of polynomials \(f_1, \dots , f_n \in {\mathbb {C}}[{\mathbf {x}}_n]\) is a regular sequence if for all \(1 \le i \le n\), the map \((-) \times f_i: {\mathbb {C}}[{\mathbf {x}}_n]/\langle f_1, \dots f_{i-1} \rangle \rightarrow {\mathbb {C}}[{\mathbf {x}}_n]/\langle f_1, \dots , f_{i-1} \rangle \) of multiplication by \(f_i\) is injective. If \(f_1, \dots , f_n\) is a regular sequence, we have a short exact sequence
for all i. If the \(f_i\) are homogeneous, this implies that
and in particular \(\dim ({\mathbb {C}}[{\mathbf {x}}_n]/\langle f_1, \dots , f_n \rangle ) = \deg f_1 \cdots \deg f_n\).
A useful criterion [8, Proposition 5.1] for deciding whether a sequence of polynomials is regular is as follows. Let \(f_1, \dots , f_n \in {\mathbb {C}}[{\mathbf {x}}_n]\) be length n sequence of homogeneous polynomials of positive degree. This sequence is regular if and only if the locus in \({\mathbb {C}}^n\) cut out by \(f_1 = \cdots = f_n = 0\) consists of the origin \(\{0\}\) alone.
3 Theorems of Springer and Morita–Nakajima
3.1 Springer’s theorem on regular elements
Before applying orbit harmonics to prove sieving results, we state representation-theoretic results of Springer [20] and Morita–Nakajima [15]. which will be useful in our combinatorial work. We explain how orbit harmonics may be used to prove these results.
Let \(W \subseteq {\mathrm {GL}}_n({\mathbb {C}})\) be a complex reflection group and let \(c \in W\) be a regular element with regular eigenvector \(v \in {\mathbb {C}}^n\) whose eigenvalue is \(\omega \in {\mathbb {C}}^{\times }\). Let \(C = \langle c \rangle \) be the cyclic subgroup of W generated by c. We regard the coinvariant ring \(R_W\) is a graded \(W \times C\)-module, where W acts by linear substitutions and the generator \(c \in C\) sends each variable \(x_i\) to \(\omega x_i\).
Theorem 1
(Springer [20]) Consider the action of \(W \times C\) on W given by \((u, c^r) \cdot w := uwc^{-r}\). The corresponding permutation representation \({\mathbb {C}}[W]\) is isomorphic to \(R_W\) as an ungraded \(W \times C\)-module.
Remark 1
Theorem 1 gives a way to compute the irreducible characters of W on the subgroup C generated by c. As explained in [20, Prop. 4.5], if U is an irreducible W-module with character \(\chi : W \rightarrow {\mathbb {C}}\), then
where \(f^{U^*}(q) \in {\mathbb {C}}[q]\) is the fake degree polynomial attached to the dual \(U^* = \mathrm {Hom}_{{\mathbb {C}}}(U, {\mathbb {C}})\) of the representation U.
We describe an argument of Kostant [12] which proves Theorem 1 using orbit harmonics. This argument will be used to give an orbit harmonics proof of a result [2, Thm. 1.4] of Barcelo, Reiner, and Stanton (see Theorem 10).
We let C act on \({\mathbb {C}}^n\) by the rule \(c \circ v' := \omega ^{-1} v'\) for all \(v' \in V\). The corresponding action of C on \({\mathbb {C}}[{\mathbf {x}}_n]\) by linear substitutions sends \(x_i\) to \(\omega x_i\) for all i, just like the C-action on \(R_W\) in Theorem 1. Furthermore, this action of C on \({\mathbb {C}}^n\) commutes with the natural action \((w, v') \mapsto w \cdot v'\) of W, so we may regard \({\mathbb {C}}^n\) as a \(W \times C\)-module in this way.
Define the Springer locus to be the W-orbit of the regular eigenvector v of c:
The locus \(W \cdot v\) is certainly closed under the action of W; we claim that \(W \cdot v\) is also closed under the \(\circ \)-action of C. Indeed, for any \(w \in W\) we have
Since the \(\circ \) action of C and the \(\cdot \) action of W on \({\mathbb {C}}^n\) commute, we may regard \(W \cdot v\) as a \(W \times C\)-set. An inspection of the above chain of equalities and the regularity of v shows that the map \(w \mapsto w \cdot v\) furnishes a \(W \times C\)-equivariant bijection
where the action of \(W \times C\) on W is as in Theorem 1.
Chevalley [5] proved that there exist algebraically independent W-invariant polynomials \(f_1, \dots , f_n\) of homogeneous positive degree such that \({\mathbb {C}}[{\mathbf {x}}_n]^W = {\mathbb {C}}[f_1, \dots , f_n]\). Furthermore, we have isomorphisms of ungraded W-modules
We claim that the invariant polynomials \(f_1, \dots , f_n\) generate the ideal \({\mathbf {T}}(W \cdot v)\). Indeed, for any \(1 \le i \le n\), let \(f_i(v) \in {\mathbb {C}}\) be the value of \(f_i\) on the regular eigenvector \(v \in {\mathbb {C}}^n\). The W-invariance of \(f_i\) implies that \(f_i - f_i(v) \in {\mathbf {I}}(W \cdot v)\), and taking the top degree component gives \(f_i \in {\mathbf {T}}(W \cdot v)\), so that \(\langle f_1, \dots , f_n \rangle \subseteq {\mathbf {T}}(W \cdot v)\). On the other hand,
so that
We use the ideal equality (32) to prove Theorem 1. Since the defining ideal \(\langle {\mathbb {C}}[{\mathbf {x}}_n]^W_+ \rangle \) of the coinvariant ring \(R_W\) is generated by \(f_1, \dots , f_n\), orbit harmonics furnishes isomorphisms of ungraded \(W \times C\)-modules
where the last isomorphism used the \(W \times C\)-equivariant bijection (29). This completes the orbit harmonics proof of Theorem 1.
3.2 A theorem of Morita–Nakajima via Orbit Harmonics
In this section we consider the case of the symmetric \(W = {\mathfrak {S}}_n\). Throughout this section, we fix a weak composition \(\mu = (\mu _1, \dots , \mu _k)\) of n with k parts which has cyclic symmetry of order a for some \(a \mid k\). That is, we have \(\mu _i = \mu _{i+a}\) for all i with subscripts interpreted modulo k. Let c be an arbitrary but fixed generator of the cyclic group \({\mathbb {Z}}_{k/a}\). Morita and Nakajima proved [15] a variant of Springer’s Theorem 1 as follows.
Let \(W_{\mu }\) be the family of length n words \(w_1 \dots w_n\) over the alphabet [k] in which the letter i appears \(\mu _i\) times. The set \(W_{\mu }\) carries an action of \({\mathfrak {S}}_n \times {\mathbb {Z}}_{k/a}\) where \({\mathfrak {S}}_n\) acts by subscript permutation and \({\mathbb {Z}}_{k/a}\) acts by \(c: w_1 \dots w_n \mapsto (w_1 + a) \cdots (w_n + a)\) where letter values are interpreted modulo k. Extending by linearity, the space \({\mathbb {C}}[W_{\mu }]\) is a \({\mathfrak {S}}_n \times {\mathbb {Z}}_{k/a}\)-module.
Let \(I_{\mu } \subseteq {\mathbb {C}}[{\mathbf {x}}_n]\) be the Tanisaki ideal attached to the composition \(\mu \) and let \(R_{\mu } := {\mathbb {C}}[{\mathbf {x}}_n]/I_{\mu }\) be the corresponding Tanisaki quotient ring. The ring \(R_{\mu }\) is a graded \({\mathfrak {S}}_n\)-module which may be described in three equivalent ways.
-
1.
Let \(\mathcal {F \ell }_n\) be the variety of complete flags \(V_{\bullet } = (0 = V_0 \subset V_1 \subset \cdots \subset V_n = {\mathbb {C}}^n)\) of subspaces of \({\mathbb {C}}^n\). If \(X_{\mu } \in {\mathrm {GL}}_n({\mathbb {C}})\) is a unipotent operator of Jordan type \(\mu \), The Springer fiber \(\mathcal {B}_{\mu }\) is the closed subvariety of \(\mathcal {F \ell }_n\) consisting of flags \(V_{\bullet }\) which satisfy \(X_{\mu } V_i = V_i\) for all i. The cohomology of \(\mathcal {B}_{\mu }\) may be presented [23] as
$$\begin{aligned} H^{\bullet }(\mathcal {B}_{\mu }; {\mathbb {C}}) = R_{\mu }. \end{aligned}$$Although the variety \(\mathcal {B}_{\mu }\) is not stable under the action of \({\mathfrak {S}}_n \subseteq {\mathrm {GL}}_n({\mathbb {C}})\), there is a Springer representation of \({\mathfrak {S}}_n\) on the cohomology ring \(H^{\bullet }(\mathcal {B}_{\mu }; {\mathbb {C}})\).
-
2.
Tanisaki [23] and Garsia–Procesi [9] gave explicit generators for the defining ideal \(I_{\mu }\) of \(R_{\mu }\). These generators are certain elementary symmetric polynomials \(e_d(S)\) in subsets S of the variable set \(\{x_1, \dots , x_n\}\) which depend on \(\mu \). This presentation makes it clear that \(R_{\mu }\) is closed under the action of \({\mathfrak {S}}_n\); we will make no explicit use of it here. Garsia and Procesi used this presentation to show that the graded Frobenius image of \(R_{\mu }\) is a Hall–Littlewood function:
$$\begin{aligned} {\mathrm {grFrob}}(R_{\mu }; q) = \widetilde{H}_{\mu }({\mathbf {x}};q). \end{aligned}$$(34)Here we interpret \(\widetilde{H}_{\mu }({\mathbf {x}};q) := \widetilde{H}_{\mathrm {sort}(\mu )}({\mathbf {x}};q)\) where \(\mathrm {sort}(\mu )\) is the partition obtained by sorting \(\mu \) into weakly decreasing order.
-
3.
Let \(\alpha _1, \dots , \alpha _k \in {\mathbb {C}}\) be distinct complex numbers. We may consider the set \(W_{\mu } \subseteq {\mathbb {C}}^n\) as a point locus by identifying
$$\begin{aligned} w_1 \dots w_n \leftrightarrow (\alpha _{w_1}, \dots , \alpha _{w_n}). \end{aligned}$$We have \(I_{\mu } = {\mathbf {T}}(W_{\mu })\) as ideals in \({\mathbb {C}}[{\mathbf {x}}_n]\). Since \(W_{\mu }\) is closed under the coordinate permuting action of \({\mathfrak {S}}_n\), this makes it clear that \(R_{\mu } = {\mathbb {C}}[{\mathbf {x}}_n]/I_{\mu } = {\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(W_{\mu })\) is \({\mathfrak {S}}_n\)-stable.
The orbit harmonics interpretation (3) of \(R_{\mu }\) was used by Garsia and Procesi [9] to derive Eq. (34).
Let \(\omega := \exp (2 a \pi i / k)\) be a primitive \((k/a)^{th}\) root-of-unity. We extend the graded \({\mathfrak {S}}_n\)-action on \(R_{\mu }\) to a graded \({\mathfrak {S}}_n \times {\mathbb {Z}}_{k/a}\)-action by letting the distinguished generator \(c \in {\mathbb {Z}}_{k/a}\) scale by \(\omega ^d\) in homogeneous degree d.
Theorem 2
(Morita–Nakajima [15, Theorem 13]) We have an isomorphism of ungraded \({\mathfrak {S}}_n \times {\mathbb {Z}}_{k/a}\)-modules
When \(\mu = (1^n)\), Theorem 2 reduces to Theorem 1 when \(W = {\mathfrak {S}}_n\) at the regular element \((1, 2, \dots , n) \in {\mathfrak {S}}_n\). The proof of Theorem 2 given in [15] involves tricky symmetric function manipulations involving the Hall–Littlewood polynomials \(\widetilde{H}_{\mu }({\mathbf {x}};q)\) when q is specialized to a root of unity. The work of [15] relies on further intricate symmetric function identities due to Lascoux–Leclerc–Thibon [14]. Orbit harmonics gives an easier and more conceptual proof.
Proof
Let \(\zeta := \exp (2 \pi i / k)\) be a primitive \(k^{th}\) root-of-unity with \(\zeta ^a = \omega \). In the interpretation (3) of \(R_{\mu }\) described above, take the parameters \(\alpha _1, \dots , \alpha _k\) defining the point locus \(W_{\mu } \subseteq {\mathbb {C}}^n\) to be \(\alpha _j := \zeta ^j\). If we let our distinguished generator c of \({\mathbb {Z}}_{k/a}\) act on \({\mathbb {C}}^n\) as scaling by \(\omega \), the set \(W_{\mu }\) is closed under the action of the linear group \({\mathfrak {S}}_n \times {\mathbb {Z}}_{k/a}\). As discussed above, Garsia and Procesi [9] used orbit harmonics to give an isomorphism
of ungraded \({\mathfrak {S}}_n \times {\mathbb {Z}}_{k/a}\)-modules.
3.3 Loci and Sieving
Our main ‘generating theorem’ for sieving results is as follows. For any group W, write \(\mathrm {Irr}(W)\) for the family of (isomorphism classes of) irreducible W-modules.
Theorem 3
Let \(W \subseteq {\mathrm {GL}}_n({\mathbb {C}})\) be a complex reflection group, let \(c' \in W\) be a regular element, let \(C' = \langle c' \rangle \) be the subgroup of W generated by \(c'\), and let \(\omega := \exp (2 \pi i / k) \in {\mathbb {C}}^{\times }\). Let \(C = \langle c \rangle \cong {\mathbb {Z}}_k\) be a cyclic group of order k and consider the action of \(W \times C\) on \({\mathbb {C}}^n\) where c scales by \(\omega \) and W acts by left multiplication.
Let \(X \subseteq {\mathbb {C}}^n\) be a finite point set which is closed under the action of \(W \times C\).
-
1.
Suppose that for \(d \ge 0\), the isomorphism type of the degree d piece of \({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X)\) is given by
$$\begin{aligned} ( {\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X) )_d \cong \bigoplus _{U \in \mathrm {Irr}(W)} U^{\oplus m_{U,d}}. \end{aligned}$$The triple \((X, C \times C', X(q,t))\) exhibits the bicyclic sieving phenomenon where
$$\begin{aligned} X(q,t) = \sum _{U \in \mathrm {Irr}(W)} m_U(q) \cdot f^{U^*}(t). \end{aligned}$$where \(m_U(q) := \sum _{d \ge 0} m_{U,d} \cdot q^d\).
-
2.
Let \(G \subseteq W\) be a subgroup. The set X/G of G-orbits in X carries a natural C-action and the triple (X/G, C, X(q)) exhibits the cyclic sieving phenomenon where
$$\begin{aligned} X(q) = {\mathrm {Hilb}}( ({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X))^G; q). \end{aligned}$$
Proof
Applying orbit harmonics to the action of \(W \times C\) on X yields an isomorphism of ungraded \(W \times C\)-modules
Let \(\zeta := \exp (2 \pi i / n)\). To prove (1), apply Theorem 1 (and Remark 1) to get that for any \(r, s \ge 0\), the trace of \((c^r, (c')^s) \in C \times C'\) acting on \({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X)\) is \(\sum _{U \in \mathrm {Irr}(W)} m_U(\omega ^r) \cdot f^{U^*}(\zeta ^s) = X(\omega ^r, \zeta ^s)\). By the isomorphism (36), this coincides with the number of fixed points of \((c^r, (c')^s)\) acting on X, completing the proof of (1).
For (2), we take G-invariants of both sides of the isomorphism (36) to get an isomorphism of C-modules
Since C acts on the graded vector space \(({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X))^G\) by root-of-unity scaling, we see that the trace of \(c^r\) on (37) is \([{\mathrm {Hilb}}( ({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X))^G; q)]_{q = \omega ^r} = X(\omega ^r)\) (for the right-hand side) or the number of orbits in X/G fixed by \(c^s\) (for the left-hand side), finishing the proof.
Remark 2
We will mostly apply Theorem 3 in the case \(W = {\mathfrak {S}}_n\). In this context \(\mathrm {Irr}(W)\) coincides with the family of partitions \(\lambda \vdash n\) and the \(f^{U^*}(t)\) appearing in Theorem 3 (1) may be replaced by \(f^{\lambda }(t)\).
In order to use Theorem 3 to prove a sieving result involving a set X, we must
-
realize the relevant action on X in terms of an action on a point locus in \({\mathbb {C}}^n\), or a quotient thereof, and
-
calculate the graded isomorphism type of \({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X)\), or the Hilbert series of \(({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X))^G\).
As we shall see, this program varies in difficulty depending on the combinatorial action in question.
4 The functional loci
Rota’s Twelvefold Way is a foundational result in enumeration and involves counting functions between finite sets which are arbitrary, injective, or surjective. Inspired by this, the loci considered in this section correspond to arbitrary, injective, and surjective functions between finite sets.
Definition 4
Given integers n and k, set \(\omega := \exp (2 \pi i / k)\). We define the following three point sets in \({\mathbb {C}}^n\):
Observe that \(Y_{n,k} = \varnothing \) if \(k < n\) and \(Z_{n,k} = \varnothing \) if \(n < k\). When \(n = k\), we have the identification of \(Y_{n,k} = Z_{n,k}\) with permutations in \({\mathfrak {S}}_n\). Each of these sets is closed under the action of \({\mathfrak {S}}_n \times {\mathbb {Z}}_k\), where \({\mathbb {Z}}_k\) scales by \(\omega \).
4.1 The quotient rings
In this section we give describe generating sets for the homogeneous ideals \({\mathbf {T}}(X)\) corresponding to the quotients in Definition 4 and describe the graded \({\mathfrak {S}}_n\)-isomorphism types of the quotients \({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X)\). This is easiest for the case of \(X_{n,k}\) corresponding to arbitrary functions \([n] \rightarrow [k]\).
Proposition 1
Let \(n, k \ge 0\). The quotient ring \({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X_{n,k})\) has presentation
and we have
where the sum is over all partitions \(\lambda \) with largest part size \({<} k\) and length \(\le n\). Here \(m(\lambda )\) is the partition obtained by rearranging the nonzero elements of \((n-\ell (\lambda ), m_1(\lambda ), m_2(\lambda ), \dots , m_{k-1}(\lambda ))\) into weakly decreasing order.
Proof
Let \(1 \le i \le n\). For any \((a_1, \dots , a_n) \in X_{n,k}\) we have \(a_i \in \{ \omega , \omega ^2, \dots , \omega ^k\}\) which means that \((x_i - \omega )(x_i - \omega ^2) \cdots (x_i - \omega ^k) \in {\mathbf {I}}(X_{n,k})\). Taking the highest degree component, we have \(x_i^k \in {\mathbf {T}}(X_{n,k})\). We conclude that \(\langle x_1^k, \dots , x_n^k \rangle \subseteq {\mathbf {T}}(X_{n,k})\). On the other hand, we know that
and since \(\dim {\mathbb {C}}[{\mathbf {x}}_n] / \langle x_1^k, \dots , x_n^k \rangle = k^n\), this proves the first assertion.
For the second assertion, observe that \(\{ x_1^{b_1} \cdots x_n^{b_n} \,:\, 0 \le b_i < k \}\) is a basis for the quotient \({\mathbb {C}}[{\mathbf {x}}_n] / \langle x_1^k, \dots , x_n^k \rangle \). The action of \({\mathfrak {S}}_n\) on these monomials decomposes this set into orbits indexed by the partitions appearing in the sum. For each partition \(\lambda \), the corresponding orbit lies in degree \(|\lambda |\) and has Frobenius image \(h_{m(\lambda )}\).
We turn our attention to the locus \(Y_{n,k}\) corresponding to injective functions \([n] \rightarrow [k]\). The idea is to use regular sequences to reduce to the case where \(k = n\).
Proposition 2
For any \(n \le k\) we have
and
where the sum is over all standard tableaux T with n boxes.
Proof
We first show that \(h_d({\mathbf {x}}_n) \in {\mathbf {T}}(Y_{n,k})\) for any \(d > k-n\). Indeed, introduce a new variable t and consider the quotient
Whenever \((x_1, \dots , x_n) \in Y_{n,k}\), the n factors in the denominator will cancel with n factors in the numerator, yielding a polynomial in t of degree \(k-n\). If \(d > k-n\), taking the coefficient of \(t^d\) on both sides yields \(\sum _{a + b = d} (-1)^a \cdot e_a(\omega , \omega ^2, \dots , \omega ^k) \cdot h_b({\mathbf {x}}_n) \in {\mathbf {I}}(Y_{n,k})\) so that \(h_d({\mathbf {x}}_n) \in {\mathbf {T}}(Y_{n,k})\).
It is known that the sequence \(h_{k-n+1}({\mathbf {x}}_n), \dots , h_{k-1}({\mathbf {x}}_n), h_k({\mathbf {x}}_n)\) of polynomials in \({\mathbb {C}}[{\mathbf {x}}_n]\) is regular. One way to see this is to check that the locus in \({\mathbb {C}}^n\) cut out by these polynomials consists only of the origin \(\{ 0 \}\). Indeed, the identities
mean that the system
is equivalent to the system
The latter system is triangular and may be solved to yield the solution set \(\{0\}\).
Since \(h_{k-n+1}({\mathbf {x}}_n), \dots , h_{k-1}({\mathbf {x}}_n), h_k({\mathbf {x}}_n)\) is a regular sequence, we see that
which forces \(\langle h_{k-n+1}({\mathbf {x}}_n), \dots , h_{k-1}({\mathbf {x}}_n), h_k({\mathbf {x}}_n) \rangle = {\mathbf {T}}(Y_{n,k})\). Furthermore, since the exact sequences
involve \({\mathfrak {S}}_n\)-equivariant maps, we see that
for all \(k \ge n\) and in particular
where the final equality is due to Lusztig (unpublished) and Stanley [21].
The surjective locus \(Z_{n,k}\) was studied by Haglund, Rhoades, and Shimozono [11] and is the most difficult functional locus to analyze. We quote their results here.
Proposition 3
(Haglund–Rhoades–Shimozono [11]) For any \(k \le n\) we have
and
All known proofs of Proposition 3 involve intricate arguments such as Gröbner theory, a variant of Lehmer codes attached to points in \(Z_{n,k}\), and somewhat involved symmetric function theory.
4.2 Bicyclic sieving
We describe the bicyclic sieving phenomena obtained by applying Theorem 3 (1) to the loci \(X_{n,k}, Y_{n,k},\) and \(Z_{n,k}\). Rather than actions on point sets, we phrase the result in terms of actions on words.
Theorem 5
Let n and k be positive integers. The following triples exhibit the bicyclic sieving phenomenon.
-
1.
The triple \((X_{n,k}, {\mathbb {Z}}_n \times {\mathbb {Z}}_k, X_{n,k}(q,t))\) where \(X_{n,k}\) is the set of all length n words \(w_1 w_2 \dots w_n\) over the alphabet [k], the cyclic group \({\mathbb {Z}}_n\) acts by rotating positions \(w_1 w_2 \dots w_n \mapsto w_2 \dots w_n w_1\), the cyclic group \({\mathbb {Z}}_k\) acts by rotating values \(w_1 w_2 \dots w_n \mapsto (w_1 + 1)(w_2 + 1) \cdots (w_n + 1)\) (interpreted modulo k), and
$$\begin{aligned} X_{n,k}(q,t) = \sum _{\begin{array}{c} \mu \text { a partition} \\ \ell (\mu ) \le n, \, \, \mu _1 < k \end{array}} q^{|\mu |} \cdot {n \brack n - \ell (\mu ), m_1(\mu ), m_2(\mu ), \dots }_t. \end{aligned}$$(55) -
2.
The triple \((Y_{n,k}, {\mathbb {Z}}_n \times {\mathbb {Z}}_k, Y_{n,k}(q,t))\) where \(Y_{n,k} \subseteq X_{n,k}\) is the subset of words with distinct letters, the group \({\mathbb {Z}}_n \times {\mathbb {Z}}_k\) acts by restricting its action on \(X_{n,k}\), and
$$\begin{aligned} Y_{n,k}(q,t) = {k \brack n}_q \cdot \sum _{\lambda \vdash n} f^{\lambda }(q) \cdot f^{\lambda }(t). \end{aligned}$$(56) -
3.
The triple \((Z_{n,k}, {\mathbb {Z}}_n \times {\mathbb {Z}}_k, Z_{n,k}(q,t))\) where \(Z_{n,k} \subseteq X_{n,k}\) is the subset of words in which every letter in [k] appears, the group \({\mathbb {Z}}_n \times {\mathbb {Z}}_k\) acts by restricting its action on \(X_{n,k}\), and
$$\begin{aligned} Z_{n,k}(q,t) = \sum _{T \in {\mathrm {SYT}}(n)} q^{{\mathrm {maj}}(T)} \cdot {n - {\mathrm {des}}(T) - 1 \brack n-k}_q \cdot f^{{\mathrm {shape}}(T)}(t). \end{aligned}$$(57)
Proof
We prove these items in reverse order: (3), then (2), then (1). Item (3) follows immediately by combining Theorem 3 (1) and Proposition 3.
If we apply Theorem 3 (1) to the locus \(Y_{n,k}\) and use Proposition 2, we obtain a bicyclic sieving result with polynomial
this proves item (2) of this theorem.
Finally, if we apply Theorem 3 (1) to the locus \(X_{n,k}\) and use Proposition 1, we obtain a bicyclic sieving result with polynomial
where we applied Young’s Rule: for \(\mu \vdash n\) we have \(h_{\mu } = \sum _{\lambda \vdash n} K_{\lambda ,\mu } s_{\lambda }\). For fixed \(\mu \), we claim that
Indeed, the left-hand side of Eq. (60) is the generating function for the major index statistic over the set of words \(w = w_1 \dots w_n\) with \(m_i(\mu )\) copies of i. The Schensted correspondence bijects such words w with ordered pairs (P, Q) of tableaux of the same shape with n boxes such that
-
P is semistandard and Q is standard, and
-
if \(w \mapsto (P, Q)\) then \({\mathrm {maj}}(w) = {\mathrm {maj}}(Q)\).
Since \(f^{\lambda }(t)\) is the generating function for major index on standard tableaux of shape \(\lambda \), Eq. (60) follows. Applying Eq. (60), we see that the expression (59) equals the formula for \(X_{n,k}(q,t)\) in the statement of the theorem.
4.3 The subgroup \(G = {\mathfrak {S}}_n\)
For our first application of Theorem 3 (2), we consider the case where \(W = {\mathfrak {S}}_n\) and the subgroup \(G = {\mathfrak {S}}_n\) is the full symmetric group. We phrase our sieving results in terms of compositions.
Let \({\mathrm {WComp}}_{n,k}\) be the family of weak compositions of n of length k and \({\mathrm {Comp}}_{n,k}\) be the set of compositions of n of length k. We have natural identifications of orbit sets
where \({[k] \atopwithdelims ()n}\) is the family of n-element subsets of [k]. The relevant sieving result reads as follows.
Theorem 6
Let n and k be positive integers. The following triples exhibit the cyclic sieving phenomenon.
-
1.
The triple \(({\mathrm {WComp}}_{n,k}, {\mathbb {Z}}_k, {n+k-1 \brack n}_q)\) where \({\mathbb {Z}}_k\) acts by rotation \((\alpha _1, \alpha _2, \dots , \alpha _k) \mapsto (\alpha _2, \dots , \alpha _k, \alpha _1)\).
-
2.
The triple \(\left( {[k] \atopwithdelims ()n}, {\mathbb {Z}}_k, {k \brack n}_q \right) \) where \({\mathbb {Z}}_k\) acts on \({ [k] \atopwithdelims ()n}\) by increasing entries by 1 modulo k.
-
3.
The triple \(({\mathrm {Comp}}_{n,k}, {\mathbb {Z}}_k, {n-1 \brack k-1}_q)\) where \({\mathbb {Z}}_k\) acts by rotation.
Theorem 6 (2) is the ‘first example’ of the CSP of Reiner et al. [17]. Theorem 6 (1) and (3) seem to have not been explicitly stated in the literature so far.
Proof
For any graded \({\mathfrak {S}}_n\)-module V, the Hilbert series \({\mathrm {Hilb}}( V^{{\mathfrak {S}}_n}; q)\) of the \({\mathfrak {S}}_n\)-invariant subspace of V is the coefficient of \(s_{(n)}\) in \({\mathrm {grFrob}}(V;q)\). Since the coefficient of \(s_{(n)}\) in \(h_{\mu }\) is 1 for any partition \(\mu \vdash n\), Proposition 1 yields
and Theorem 3 (2) finishes the proof of item (1). For item (2), we extract the coefficient of \(s_{(n)}\) in Proposition 2 to get
and apply Theorem 3 (2). For item (3), extracting the coefficient of \(s_{(n)}\) in Theorem 3 yields
and Theorem 3 (2) finishes the proof.
4.4 The subgroup \(G = C_n\)
In this section we consider the subgroup \(C_n\) of \({\mathfrak {S}}_n\) generated by the long cycle \((1, 2, \dots , n)\). Recall that a necklace of length n over the bead set [k] is an equivalence class of length n sequences \((b_1, b_2, \dots , b_n)\) of beads in [k] where two such sequences are considered equivalent if they differ by a cyclic shift. We have the following three families of necklaces over the bead set [k].
Each of the sets \(N^X_{n,k}, N^Y_{n,k}, N^Z_{n,k}\) carries an action of \({\mathbb {Z}}_k\) by bead color rotation:
and we have the orbit set identifications
Theorem 7
Let n and k be positive integers. The following triples exhibit the cyclic sieving phenomenon.
-
1.
The triple \((N^X_{n,k}, {\mathbb {Z}}_k, N^X_{n,k}(q))\) where
$$\begin{aligned} N^X_{n,k}(q) = \sum _{\begin{array}{c} \mu \,\text { a partition }\\ \ell (\mu ) \le n, \, \, \mu _1 < k \end{array}} q^{|\mu |} \cdot b_{\mu } \end{aligned}$$where \(b_{\mu }\) is the number of length n words \(w = w_1 \dots w_n\) satisfying \(n \mid {\mathrm {maj}}(w)\) containing \(n - \ell (\mu )\) copies of 0 and \(m_i(\mu )\) copies of i for each \(i > 0\).
-
2.
The triple \((N^Y_{n,k}, {\mathbb {Z}}_k, N^Y_{n,k}(q))\) where
$$\begin{aligned} N^Y_{n,k}(q) = {k \brack n}_q \cdot \sum _{\lambda \vdash n} a_{\lambda , n} \cdot f^{\lambda }(q) \end{aligned}$$where \(a_{\lambda , n}\) is the number of standard Young tableaux T of shape \(\lambda \) with \(n \mid {\mathrm {maj}}(T)\).
-
3.
The triple \((N^Z_{n,k}, {\mathbb {Z}}_k, N^Z_{n,k}(q))\) where
$$\begin{aligned} N^Z_{n,k}(q) = \sum _{T \in {\mathrm {SYT}}(n)} q^{{\mathrm {maj}}(T)} \cdot {n - {\mathrm {des}}(T) - 1 \brack n - k}_q \cdot a_{\mathrm {shape}(T),n}. \end{aligned}$$
Proof
For \(0 \le j \le n-1\), let \(V_j\) be the linear representation of \(C_n\) on which \((1, 2, \dots , n)\) acts by \(\exp (2 \pi i j / n)\). Kraśkiewicz and Weyman proved [13] that the induction of \(V_j\) from \(C_n\) to \({\mathfrak {S}}_n\) may be written
where the direct sum is over all standard tableaux T with n boxes such that \({\mathrm {maj}}(T) \equiv j\) modulo n. Specializing at \(j = 0\), we see that the dimension of the \(C_n\)-fixed space of the \({\mathfrak {S}}_n\)-irreducible \(S^{\lambda }\) is
which proves (2) and (3). For (1), apply the RSK bijection to see that
4.5 The subgroup \(G = H_r\)
In this section we assume \(n = 2r\) is even and let \(H_r \subseteq {\mathfrak {S}}_n\) be the subgroup generated by the permutations
The group \(H_r\) is isomorphic to the hyperoctohedral group of signed permutations of an r-element set.
We consider undirected graphs on the vertex set [k] in which multiple edges and loops are allowed. An isolated vertex in such a graph is an element \(i \in [k]\) which is not incident to any edge (so that a vertex which has a loop is not isolated). We have the following families of graphs on the vertex set [k].
Observe that when \(k = n\), the set \(Gr^Y_{n,n}\) may be identified with the family of perfect matchings on [n].
Each of the three sets \(Gr^X_{n,k}, Gr^Y_{n,k},\) and \(Gr^Z_{n,k}\) carries an action of \({\mathbb {Z}}_k\) by the vertex-rotating cycle \((1, 2, \dots , k)\). This \({\mathbb {Z}}_k\)-action is compatible with the orbit-set identifications
In the following theorem, a partition \(\lambda \) is called even if each of its parts \(\lambda _1, \lambda _2, \dots \) is even.
Theorem 8
We have the following cyclic sieving triples.
-
1.
The triple \((Gr_{n,k}^X, {\mathbb {Z}}_k, Gr_{n,k}^X(q))\) exhibits the cyclic sieving phenomenon, where
$$\begin{aligned} Gr_{n,k}^X(q) = \sum _{\begin{array}{c} \text {partitions}\,\mu \\ \mu \subseteq ({(k-1)}^n) \end{array}} \sum _{\lambda \vdash n \text { even}} K_{\lambda , m(\mu )} \cdot q^{|\mu |} \cdot f^{\lambda }(q). \end{aligned}$$Here \(m(\mu ) \vdash n\) is the partition obtained by rearranging the nonzero elements of \((n-\ell (\mu ), m_1(\mu ), m_2(\mu ),\) \(\dots , m_{k-1}(\mu ))\) in weakly decreasing order and \(K_{\lambda , m(\mu )}\) is the Kotska number.
-
2.
The triple \((Gr_{n,k}^Y, {\mathbb {Z}}_k, Gr_{n,k}^Y(q))\) exhibits the cyclic sieving phenomenon, where
$$\begin{aligned} Gr_{n,k}^Y(q) = {k \brack n}_q \cdot \sum _{\begin{array}{c} \lambda \vdash n \\ \lambda \text { even} \end{array}} f^{\lambda }(q). \end{aligned}$$ -
3.
The triple \((Gr_{n,k}^Z, {\mathbb {Z}}_k, Gr_{n,k}^Z(q))\) exhibits the cyclic sieving phenomenon, where
$$\begin{aligned} Gr_{n,k}^Z(q) = \sum _{\begin{array}{c} T \in {\mathrm {SYT}}(n) \\ \mathrm {shape}(T) \text { even} \end{array}} q^{{\mathrm {maj}}(T)} \cdot {n - {\mathrm {des}}(T) - 1 \brack n - k}_q. \end{aligned}$$
This result should be compared with a result of Berget, Eu, and Reiner. In [3, Theorem 5 (i)] they prove a result equivalent to Theorem 8 (1). Their proof, like ours, uses the symmetric function operation of plethysm.
Proof
For any value of d, the wreath product \({\mathfrak {S}}_d \wr {\mathfrak {S}}_r\) embeds naturally inside the larger symmetric group \({\mathfrak {S}}_{dr}\). The Frobenius image of the corresponding coset representation may be expressed using plethysm as
Finding the Schur expansion of \(h_d[h_r]\) is difficult in general, and is closely related to Thrall’s Problem. In the special case \(d = 2\), we may identify \(H_r \cong {\mathfrak {S}}_2 \wr {\mathfrak {S}}_r\) and we have
where \(n = 2r\). Applying Frobenius Reciprocity, for any \(\lambda \vdash n\) the dimension of the \(H_r\)-fixed subspace of the \({\mathfrak {S}}_n\)-irreducible \(S^{\lambda }\) is given by the character inner product:
where we use \(\mathbf{1}\) for the trivial character of \(H_r\). Correspondingly, if V is any graded \({\mathfrak {S}}_n\)-module with graded Frobenius image
the Hilbert series of the \(H_r\)-fixed subspace will be
The polynomials \(Gr^X_{n,k}(q), Gr^Y_{n,k}(q), Gr^Z_{n,k}(q)\) are obtained in this way from Propositions 1, 2, and 3.
5 Other combinatorial loci
5.1 The Tanisaki locus
Throughout this section, we fix a weak composition \(\mu = (\mu _1, \dots , \mu _k) \models _0 n\) of n into k parts which satisfies \(\mu _i = \mu _{i+a}\) for all i, where indices are interpreted modulo k. If \(\omega := \exp (2 \pi i/k)\), define the Tanisaki locus \(X_{\mu } \subseteq {\mathbb {C}}^n\) by
As discussed in Sect. 3.2, Garsia–Procesi [9] proved that \({\mathbf {T}}(X_{\mu }) = I_{\mu }\) (the Tanisaki ideal) and \({\mathrm {grFrob}}({\mathbb {C}}[{\mathbf {x}}_n]/{\mathbf {T}}(X_{\mu }); q) = \widetilde{H}_{\mu }({\mathbf {x}};q)\) (the Hall–Littlewood symmetric function). We have the following bicyclic sieving result.
Theorem 9
Let \(W_{\mu }\) be the set of length n words \(w_1 \dots w_n\) which contain \(\mu _i\) copies of the letter i for each \(i = 1, 2, \dots k\). The set \(W_{\mu }\) carries an action of \({\mathbb {Z}}_n \times {\mathbb {Z}}_{k/a}\), where \({\mathbb {Z}}_n\) acts by word rotation \(w_1 w_2 \dots w_n \mapsto w_2 \dots w_n w_1\) and \({\mathbb {Z}}_{k/a}\) acts by \(w_1 \dots w_n \mapsto (w_1 + a) \cdots (w_n + a)\) where letter values are interpreted modulo k. The triple \((W_{\mu }, {\mathbb {Z}}_n \times {\mathbb {Z}}_{k/a}, X(q,t))\) exhibits the bicyclic sieving phenomenon, where
and \(\mathrm {sort}(\mu )\) is the partition obtained by sorting the parts of \(\mu \) into weakly decreasing order.
Proof
Apply Theorem 3 (1) to the point locus \(X_{\mu }\) and use the Schur expansion
of the Hall–Littlewood polynomials.
Theorem 9 was proven in unpublished work of Reiner and White. A proof of Theorem 9 using Theorem 2 may by found in [18].
Given a subgroup \(G \subseteq {\mathfrak {S}}_n\), what happens when we apply Theorem 3 (2) to \(X_{\mu }\)? By reasoning analogous to that in Sect. 4 we obtain the following CSPs.
Example 1
When \(G = {\mathfrak {S}}_n\), the locus \(X_{\mu }\) is a single G-orbit. The \({\mathfrak {S}}_n\)-invariant part of \(R_{\mu }\) is simply the ground field in degree 0, so we get the trivial CSP \(( \{ * \}, {\mathbb {Z}}_{k/a}, 1)\) for the action of \({\mathbb {Z}}_k\) on a one-point set.
Example 2
When \(G = C_n\), we may identify \(X_{\mu }/G\) with the family of n-bead necklaces \((b_1, \dots , b_n)\) with \(\mu _i\) copies of the bead of color i. The cyclic group \({\mathbb {Z}}_{k/a}\) acts on these necklaces by a-fold color rotation \(b_i \mapsto b_i + a\) and we get a CSP \((X_{\mu }/G, {\mathbb {Z}}_{k/a}, X(q))\) where
and \(a_{\lambda ,n}\) is the number of standard tableaux T of shape \(\lambda \) with \(n \mid {\mathrm {maj}}(T)\).
Example 3
When \(n = 2r\) is even and \(G = H_r\), we may identify \(X_{\mu }/G\) with the family of graphs (loops and multiple edges permitted) on the vertex set [k] where the vertex i has degree \(\mu _i\) (here a loop contributes two to the degree of its vertex). The orbit set \(X_{\mu }/G\) is acted upon by \({\mathbb {Z}}_{k/a}\) by a-fold vertex rotation, and the triple \((X_{\mu }/G, {\mathbb {Z}}_{k/a}, X(q))\) exhibits the CSP where
5.2 The Springer locus
In this section we return to the setting of an arbitrary complex reflection group \(W \subseteq {\mathrm {GL}}_n({\mathbb {C}})\) acting on \(V := {\mathbb {C}}^n\). We fix a regular element \(c \in W\) with regular eigenvector \(v \in V\) and corresponding regular eigenvalue \(\omega \in {\mathbb {C}}\), so that \(c \cdot v = \omega v\). We also let \(C := \langle c \rangle \) be the subgroup of W generated by c.
Recall that the Springer locus is the W-orbit \(W \cdot v = \{ w \cdot v \,:\, w \in W \} \subseteq V\). Sect. 3.1 shows that the Springer locus is closed under the action of the group \(W \times C\), where W acts by its natural action on V and C acts by the rule \(c: v' \mapsto \omega v'\) for all \(v' \in V\). (Note that this is different from the \(\circ \)-action \(c \circ v' := \omega ^{-1} v'\) of C considered in Sect. 3.1.)
Theorem 10
Let \(c, c' \in W\) be regular elements and let \(C = \langle c \rangle , C' = \langle c' \rangle \) be the cyclic subgroups which they generate. The product of cyclic groups \(C \times C'\) acts on W by the rule \((c, c') \cdot w := c' w c\). The triple \((W, C \times C', W(q,t))\) exhibits the bicyclic sieving phenomenon where
and the sum is over all (isomorphism classes of) irreducible W-modules U.
Proof
The discussion in Sect. 3.1 shows that the homogeneous quotient \({\mathbb {C}}[V]/{\mathbf {T}}(W \cdot v)\) attached to the Springer locus \(W \cdot v \subseteq V\) is given by the coinvariant ring
The map \(W \rightarrow W \cdot v\) given by \(w \mapsto w \cdot v\) is a \(W \times C\)-equivariant bijection. Indeed, the generator c of the group C acts on \(w \cdot v \in W \cdot v\) by
which agrees with the action of C on W. By definition, the fake degree polynomial \(f^{U}(q)\) is the graded multiplicity of U in the W-module \(R_W\). Now apply Theorem 3 (1).
Theorem 10 is a result of Barcelo, Reiner, and Stanton [2, Thm. 1.4]. In [2] the polynomial W(q, t) is referred to as a bimahonian distribution. More generally, Barcelo, Reiner, and Stanton consider ‘Galois twisted’ actions of \(C \times C'\) on W as follows. Let d be the order of the regular element \(c' \in W\) and let s be an integer coprime to d. The group \(C \times C'\) acts on W by the rule
If we let \(\zeta := \exp (2 \pi i / d)\), there is a unique Galois automorphism \(\sigma \in \mathrm {Gal}({\mathbb {Q}}[\zeta ]/{\mathbb {Q}})\) satisfying \(\sigma (\zeta ) = \zeta ^s\). Furthermore, if U is any W-module, there is a W-module \(\sigma (U)\) obtained by applying \(\sigma \) entrywise to the matrices representing group elements in the action of W on U. The operation \(U \mapsto \sigma (U)\) preserves the irreducibility of W-modules.
In [2, Thm. 1.4] Barcelo, Reiner, and Stanton prove that \((W, C \times C', W^{\sigma }(q,t))\) exhibits the biCSP where \(C \times C'\) acts by the Galois-twisted action of (85) and \(W^{\sigma }(q,t)\) is the \(\sigma \)-bimahonian distribution given by
where U runs over all isomorphism classes of irreducible W modules. This more general biCSP can also be proven using orbit harmonics; one observes that \((c')^s \in C'\) is a regular element in W with regular eigenvalue \(\zeta ^s\) and applies Theorem 10 with \(c' \mapsto (c')^s\). See [2] for detail.
6 Conclusion
In this paper we described the orbit harmonics method of proving CSPs by modeling the set X in question as a point locus in a \({\mathbb {C}}\)-vector space V. We applied our results to the functional loci, the Springer Locus, and the Tanisaki Locus.
The orbit harmonics method has implicitly been used to prove CSPs before; we refer the reader to [1] for all undefined terms in what follows. Let W be an irreducible real reflection group acting on its (complexified) reflection representation V. In [1], Armstrong, Reiner, and Rhoades define a parking locus \(V^{\Theta } \subseteq V\) of degree \((h+1)^{\dim V}\) which carries an action of \(W \times {\mathbb {Z}}_h\) where h is the Coxeter number of W and \({\mathbb {Z}}_h\) acts on V by root-of-unity scaling. The locus \(V^{\Theta }\) depends on a choice of homogeneous system of parameters \(\Theta \) of degree \(h+1\) carrying \(V^*\).
In [1, 19], the orbit harmonics method is (implicitly) applied to the parking locus \(V^{\Theta }\) to prove the following CSP of Bessis and Reiner. Let \(\mathrm {NC}_W\) be the set of W-noncrossing partitions with its cyclic action of \({\mathbb {Z}}_h\) by generalized rotation. (In type A\(_{n-1}\), this is simply the set of noncrossing set partitions of [n] with the rotation action of \({\mathbb {Z}}_n\).) Bessis and Reiner proved [4] that the triple \((\mathrm {NC}_W, {\mathbb {Z}}_h, \mathrm {Cat}_q(W))\) exhibits the CSP where \(\mathrm {Cat}_q(W)\) is the q-W-Catalan number given by \(\mathrm {Cat}_q(W) = \prod _{i = 1}^{\dim V} \frac{[d_i + h]_q}{[d_i]_q}\) where \(d_1, d_2, \dots \) are the invariant degrees of W. On the level of orbit harmonics, this corresponds to looking at the W-orbits \(V^{\Theta }/W\) in the parking locus \(V^{\Theta }\). Whereas the proof of Bessis-Reiner was a brute force enumration, the proof in [1, 19] is algebraic (since it uses orbit harmonics).
There are many interesting point loci \(X \subseteq V\) to which the method of orbit harmonics has been applied to study the quotient \({\mathbb {C}}[V]/{\mathbf {T}}(X)\). This paper describes a technique for obtaining sieving results in any such situation. One interesting recent locus which we did not consider in this paper is due to Griffin [10]. This locus X is in bijection with a certain family of ordered set partitions and is a common generalization of the Tanisaki locus studied in [9, 23] and the surjective functional locus studied in [11]. We leave the sieving study of this and other interesting combinatorial loci to future work.
Notes
up to duality, but permutation representations are self-dual
References
Armstrong, D., Rhoades, B., Reiner, V.: Parking spaces. Adv. Math. 269, 647–706 (2015)
Barcelo, H., Reiner, V., Stanton, D.: Bimahonian distributions. J. Lond. Math. Soc. 77(3), 627–646 (2008)
Berget, A., Eu, S.-P., Reiner, V.: Constructions for cyclic sieving phenomena. SIAM J. Discrete Math 25, 1297–1314 (2011)
Bessis, D., Reiner, V.: Cyclic sieving of noncrossing partitions. Ann. Combin. 15, 197–222 (2011)
Chevalley, C.: Invariants of finite groups generated by reflections. Am. J. Math. 77(4), 778–782 (1955)
Chmutova, T., Etingof, P.: On some representations of the rational Cherednik algebra. Represent. Theory 7, 641–650 (2003)
Douvropoulos, T.: Cyclic sieving for reduced reflection factorizations of the Coxeter element. Sém. Loth. Comb. 80B, 12 (2018) (Article # 86)
Fukukawa, Y., Harada, M., Masuda, M.: The equivariant cohomology rings of Peterson varieties. J. Math. Soc. Jpn. 67(3), 1147–1159 (2015)
Garsia, A.M., Procesi, C.: On certain graded \(S_n\)-modules and the \(q\)-Kostka polynomials. Adv. Math. 94, 82–138 (1992)
Griffin, S.: Ordered set partitions, Garsia–Procesi modules, and rank varieties. Trans. Am. Math. Soc. 374(4), 2609–2660 (2021)
Haglund, J., Rhoades, B., Shimozono, M.: Ordered set partitions, generalized coinvariant algebras, and the Delta Conjecture. Adv. Math. 329, 851–915 (2018)
Kostant, B.: Lie group representations on polynomial rings. Bull. Am. Math. Soc. 69(4), 518–526 (1963)
Kraśkiewicz, W., Weyman, J.: Algebra of coinvariants and the action of a Coxeter element. Bayreuth. Math. Schr. 63, 265–284 (2001)
Lascoux, A., Leclerc, B., Thibon, J.-Y.: Green polynomials and Hall-Littlewood functions at roots of unity. Eur. J. Combin. 15, 173–180 (1994)
Morita, H., Nakajima, T.: A formula of Lascoux–Leclerc–Thibon and representations of symmetric groups. J. Algebraic Comb. 24(1), 45–60 (2006)
Rao, S., Suk, J.: Dihedral sieving phenomena. Discrete Math. 343(6), 111849 (2020)
Reiner, V., Stanton, D., White, D.: The cyclic sieving phenomenon. J. Comb. Theory Ser. A 108, 17–50 (2004)
Rhoades, B.: Hall-Littlewood polynomials and fixed point enumeration. Discrete Math. 310(4), 869–876 (2010)
Rhoades, B.: Evidence for parking conjectures. J. Comb. Theory Ser. A 146, 81–127 (2017)
Springer, T.A.: Regular elements of finite reflection groups. Invent. Math. 29, 159–198 (1974)
Stanley, R.P.: Invariants of finite groups and their applications to combinatorics. Bull. Am. Math. Soc. 1, 475–511 (1979)
Swanson, J.: The dihedral sieving phenomenon (2021) (In preparation)
Tanisaki, T.: Defining ideals of the closures of conjugacy classes and representations of the Weyl groups. Tohoku J. Math. 34, 575–585 (1982)
Acknowledgements
J. Oh was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2020R1A6A3A13076804). B. Rhoades was partially supported by NSF Grant DMS-1500838 and DMS-1953781. The authors are grateful to Soichi Okada, Vic Reiner, and Josh Swanson for helpful conversations. The authors also thank referees for careful reading and helpful comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Oh, J., Rhoades, B. Cyclic sieving and orbit harmonics. Math. Z. 300, 639–660 (2022). https://doi.org/10.1007/s00209-021-02800-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00209-021-02800-z