The symmetric functions catalog

An overview of symmetric functions and related topics

2023-07-14

The cyclic sieving phenomenon

See below for the definition of the cyclic sieving phenomenon, (CSP). There are many instances of the CSP, which I have put into different categories based roughly on the type of combinatorial object it concerns.

CSP Icon Word Words & permutations
CSP Icon Path Paths
CSP Icon Catalan Catalan objects
CSP Icon Match Matchings & crossings
CSP Icon Young Tableaux & fillings
CSP Icon Misc Miscellaneous

Definition

The cyclic sieving phenomenon (CSP) was introduced by V. Reiner, D. Stanton and D. White in [RSW04]. A nice survey by B. Sagan is given in [Sag11].

Let $X$ be a set of combinatorial objects, $\grpc_n = \langle g \rangle$ be a finite cyclic group of size $n,$ and $f(q) \in \setN[q].$ Then the triple $(X,\grpc_n,f(q))$ is said to exhibit the cyclic sieving phenomenon if for all $d \in \setN,$ we have

\[ |\{x \in X : g^d \circ x =x \}| = f\left(\exp\left(2\pi i \frac{d}{n}\right)\right). \]

In words, $f(q)$ evaluated at certain roots of unity gives the number of elements in $X$ fixed by powers of $g.$ Note that $f(1) = |X|,$ so in many instances, $f(q)$ is a $q$-analog(or $q$-enumeration) of the set $X.$

Proposition.

Let $\xi$ is a primitive $n^\thsup$ root of unity, and suppose that $f \in \setN[q]$ such that $f(\xi^j) \in \setZ$ for all $j \in \setZ.$ Then for all $j \in \setZ,$ $f(\xi^j) = f( \xi^{\gcd(j,n)}).$

Proof.

In [Dés89] and [Lem. 2.2, AA19b], it is proved that $f$ (up to mod $q^n-1$) is a linear combination of

\[ h_d(q) \coloneqq \sum_{j=0}^{n/d-1} q^{dj} = \frac{[n]_q}{[d]_q} \qquad \text{ where } d \mid n. \]

It then suffices to verify that

\[ h_d(\xi^j) = h_d( \xi^{\gcd(j,n)}) = \begin{cases} \frac{n}{d} &\text{ if } n \mid j d \\ 0 &\text{ otherwise} \end{cases} \]

for all $d \mid n,$ $j\in \setZ,$ which is straightforward.

This proposition is very handy: Suppose we know that $f$ is an integer at $n^\thsup$ roots of unity. Then it suffices to verify that for all $d \mid n,$ we have that

\[ |\{x \in X : g^d \circ x =x \}| = f\left(\exp\left(2\pi i \frac{d}{n}\right)\right) \]

in order to prove CSP.

Theorem (From [RSW04]).

Given $X$ and $\grpc_n$ acting on $X$ and $f(q) \in \setN[q],$ then $(X,\grpc_n,f(q))$ exhibits the CSP if and only if

\[ f(q) \equiv \sum_{O \in Orb_{\grpc_n}(X)} \frac{q^n-1}{ q^{n/|O|} - 1} \mod (q^n-1), \]

where $Orb_\grpc(X)$ is the set of orbits of $X$ under $\grpc.$

In other words, in a CSP triple $(X,\grpc_n,f(q))$ the polynomial $f(q)$ is essentially uniquely determined by $\grpc_n$ acting on $X.$

There is a converse to the above theorem.

Theorem (From [AA19b]).

Let $\xi$ be a primitive $n$th root of unity, and suppose $f(q) \in \setN[q]$ has the property that $f(\xi^j) \in \setN$ for all $j\in \setN.$ Let $S_k$ be defined as

\[ S_k \coloneqq \sum_{j|k} \mu(k/j) f(\xi^j). \]

Then there is a group action $\grpc_n$ acting on some $X$ with cardinality $f(1)$ and $(X,\grpc_n,f(q))$ exhibits the CSP if and only if all $S_k$ are non-negative.

In other words, these are necessary and sufficient conditions on $f(q) \in \setN[q]$ for there to be a CSP involving $f(q).$

Research situation: You have your favorite set $X$ and a $q$-analog $f(q).$ The previous theorem allows you to check (by computer, preferably) if there is some CSP phenomenon on $X,$ involving $f(q).$ Note that it is not sufficient for $f(q)$ to evaluate to non-negative integers at roots of unity!

The number of orbits of size $k$ is determined by $\frac{1}{k}\sum_{j|k} \mu(k/j) f(\xi^j),$ and it follows that the total number of orbits is

\[ \sum_{k|n} \frac{1}{k}\sum_{j|k} \mu(k/j) f(\xi^j). \]
Example (Example 2.10 from [AA19b]).

Take $f(q)=q^5+3q^3+q+10.$ At any $6^\thsup$ roots of unity, $f(\xi^j)$ is a positive integer. However, for $k=3,$ the sum $\sum_{d|k} \mu(k/d) f(\xi^d)$ is $-3.$ This sum represents the number of elements in an orbit of size $3$ under the cyclic group, and this number is not allowed to be negative. Hence, there is no set $X$ of size $15$ with a cyclic group action $C_6$ of order $6,$ such that $(X,C_6,f(q))$ is a CSP-triple.

Connection with representation theory

We can prove cyclic sieving using representation theory.

Suppose $G$ (in this case the cyclic group $C_n$) act on the set $X.$ We can form the $|X|$-dimensional vector space

\[ V = \setC X = \{a_1 x_1 + a_2x_2+\dotsb + a_M x_M : a_1,\dotsc,a_m \in \setC \}, \]

and note that $G$ act on $V.$ We can compute the character $\chi(g)$ for $g\in G,$ as a certain type of trace. Since $G$ in our case act via permutations, $\chi(g)$ is simply the number of elements in $X$ fixed by $g.$

One then wish to find a different basis $B$ for $V$ (perhaps starting with the diagonal matrix with entries $(1,\zeta,\zeta^2,\dotsc,\zeta^{n-1})$ representing a generator of $C_n$) such that the action of $G$ on $B$ is diagonal. It is then easy to compute the trace, expressed in terms of roots of unity. If this trace of $g^d$ is exactly $f(\zeta^d)$ for our polynomial $f$(q), we have proved an instance of CSP.

Several examples are given in [Sag11]. One can also construct new CSP from existing ones by using representation theory, see [BER11RSW04].

Universal CSP statistics

The noition of universal statistics was introduced in [AS18a].

Suppose $(X,\grpc_n,f(q))$ exhibits the CSP, where $f(q) = \sum_{x\in X} q^{\tau(x)}$ for some combinatorial statistic $\tau:X \to \setN.$ Then $\tau$ is said to be universal if for every $\grpc_n$-orbit $O \subseteq X,$ we have that $(O,\grpc_n,\sum_{x\in O} q^{\tau(x)})$ exhibits the CSP.

The usual major index on words is not universal. The authors of [AS18a] introduce a new (universal) statistic on words equidistributed with $\maj$ on words of length $n$ with fixed content $\alpha.$

Proper statistic

The following definition has not been defined in any journal to my knowledge. This is possibly related/equivalent with the notion of a universal CSP statistic.

Suppose $X$ is a combinatorial family with a statistic $\sigma:X \to \setN,$ that defines the $q$-analog $f(q)$ of $X,$ and that $(X, \grpc_n, f(q))$ is a CSP-triple.

Then the statistic is called proper if whenever $d|n,$ we have that

\[ g^{d}(x) = x \implies \sigma(x) \equiv_{n/d} 0 \text{ for all } x \in X. \]
Example.

Let $n=2$ and suppose $g$ generate a $\grpc_2$-action on $X.$ If $\sigma$ is a proper statistic on $X,$ and $X^g \subseteq X$ are the elements fixed under $g,$ then there should (in principle) exist an involution $\psi : X\setminus X^g \to X\setminus X^g,$ such that $(-1)^{\sigma(x)}+(-1)^{\sigma(\psi(x))} = 0,$ which would provide a proof of CSP.

Subset cyclic sieving

There is a natural generalization of the cyclic sieving phenomenon described in [ALP19]. Let $X$ be a set of combinatorial objects and $Y \subseteq X.$ Let $\grpc_n = \langle g \rangle$ be a finite cyclic group of size $n,$ and $f(q) \in \setN[q].$ Then the triple $(Y\subseteq X,\grpc,f(q))$ is said to exhibit the subset cyclic sieving phenomenon if for all $d \in \setN,$ we have

\[ |\{y \in Y : g^d \circ y = y \}| = f\left(\exp\left(2\pi i \frac{d}{n}\right)\right). \]

Note that in particular, $f(1)=|Y|.$

The subset CSP can be thought of as a CSP on $Y,$ but where the group action is allowed to leave $Y.$ By using the main theorem in [AA19b], one can show that if $Y\subset X$ admits a subset CSP, then $Y$ also admits a proper CSP, with some cyclic group action that does not leave $Y.$

Example (Taken from [ALP19]).

Let $X_n$ be the set of binary words, and let $Y_n \subseteq X_n$ be the set of words ending with a $1.$ Furthermore, let $\eta$ act on $X_n$ by a twisted two-step cyclic shift

\[ \eta(b_1,b_2,\dotsc,b_{n-1},b_n) = (1-b_{n-1},1-b_n,b_1,b_2,\dotsc,b_{n-2}). \]

It is easy to show that $\langle \eta \rangle$ is a cyclic group of order $n.$ The polynomial we shall use is $f_n(q) = \prod_{j=1}^{n-1}(1+q^j).$ Then

\[ (Y_n \subseteq X_n, \langle \eta \rangle, f_n(q)) \]

exhibits the subset cyclic sieving phenomenon. Note that $(X_n, \langle \eta \rangle, 2f_n(q))$ is an instance of the classical CSP.

Lyndon-like cyclic sieving

In [ALP19], we consider a special type of cyclic sieving phenomenon, on a family $\{X_n\}_{n=1}^\infty$ of combinatorial objects. This idea captures the case where fixed points in $X_n$ under the group action are in bijection with smaller members of the family.

Definition.

Let $\{(X_n, C_n, f_n(q))\}_{n=1}^\infty$ be a family of instances of CSP. The family is Lyndon-like if for all $n\geq 1,$

\[ f_{n/m}(1) = f_n\left( e^{\tfrac{2 \pi i}{m}} \right), \text{ whenever } m|n. \]

By the definition of CSP, we have that

\[ f_n\left( e^{\tfrac{2 \pi i}{m}} \right) = |\{ x \in X_n : g^{n/m}(x) = x \}|, \]

where $\langle g \rangle = C_n.$ The family is therefore Lyndon-like if and only if for every $d|n$ the number of elements in $X_n$ fixed under $g^{d}$ is equal to $|X_{d}|.$

The connection with counting fixed-points under iterations of a map is also discussed in the earlier work [Zar08], where many related notions are discussed.

There are several examples of Lyndon-like families of CSP. For example, Cyclic sieving on words, CSP on circular Dyck paths and (conjecturally) CSP on non-attacking filling.

Notice that it is easy to gather computer evidence for a sequence of $q$-analogs $\{f_n(q)\}_{n=1}^\infty$ to be Lyndon-like. Such evidence should give strong hints about possible corresponding cyclic group actions, as it should in principle behave as a type of cyclic shift on words.

$q$-Gauß congruences

In [Gor19], O. Gorodetsky introduces the notion of $q$-Gauß congruences. A sequence of polynomials $\{ a_n(q) \}_{n=1}^\infty$ is said to satisfy $q$-Gauß congruences if for every $n \in \setP,$ we have

\[ \sum_{d|n} \mu(d) a_{n/d}(q^d) \equiv 0 \mod [n]_q. \]

It can be verified that this condition on the family is equivalent with being Lyndon-like, that is $a_{n/m}(1) = a_n(\xi)$ where $\xi$ is an $n$th root of unity with order $m,$ see [Cor. 2.5, Gor19].

Orbital harmonics

In this FPSAC abstract, Jaeseong Oh gives an introduction to a representation-theoretical approach to proving cyclic sieving results.

Dilateral Sieving

It is possible to extend the cyclic sieving phenomenon to other groups, see [RS17]. The next natural example is the dilateral group, $D_n.$ This group is presented as $\langle r,s : r^n=s^2=e, rs=sr^{-1} \rangle.$ We can interpret this as $r$ being a one-step rotation of an $n$-gon and $s$ being a reflection. Several examples of dilateral sieving is given in [RS17].

Homomesy

The term homomesy introduced by J. Propp and T. Roby in [PR13] is defined as follows. Let $X$ be some combinatorial set and let $\langle g \rangle$ act on $X$ such that every orbit is finite, and let $\sigma : X \to \setZ$ be statistic on $X.$ Then the triple $(X,\langle g \rangle,\sigma)$ is said to exhibit homomesy if for every orbit $O \subseteq X,$ we have

\[ \frac{1}{|O|} \sum_{x \in O} \sigma(x) = \frac{1}{|X|} \sum_{x \in X} \sigma(x). \]

In other words, the average value of $\sigma$ is the same on every orbit.

The first instance of the homomesy phenomenon was observed by D. Panyushev in [Pan09], when studying an action on antichains of positive roots. Since then, many more instances have been found.

For homomesy on miniscule posets, see [Oka21], and for the Foata map, see [LR20]. Spectral theory approach to homomesy, see [Pro21].

An action is homometric if the total sum of the statistic on orbits of the same size, is the same. For example, for all orbits of size 4, the sum of the statisic on each orbit must be the same. This notion was introduced by Elizalde, Roby, Plante and Sagan.

Homomesy and homometry for promotion on rooted trees is considered in [PDS23].

References