2021-09-30

## 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.

### 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,f(q))$ is said to *exhibit the cyclic sieving phenomenon* if for all $d \in \setN,$ we have

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

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*

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}|.$

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.

## References

- [AA19b] Per Alexandersson and Nima Amini. The cone of cyclic sieving phenomena. Discrete Mathematics, 342(6):1581–1601, 2019.
- [ALP19] Per Alexandersson, Svante Linusson and Samu Potka. The cyclic sieving phenomenon on circular Dyck paths. The Electronic Journal of Combinatorics, 26:1–32, October 2019.
- [AS18a] Connor Ahlbach and Joshua P. Swanson. Refined cyclic sieving on words for the major index statistic. European Journal of Combinatorics, 73:37–60, October 2018.
- [BER11] Andrew Berget, Sen-Peng Eu and Victor Reiner. Constructions for cyclic sieving phenomena. SIAM Journal of Discrete Mathematics, 25(3):1297–1314, 2011.
- [BR11] David Bessis and Victor Reiner. Cyclic sieving of noncrossing partitions for complex reflection groups. Annals of Combinatorics, 15(2):197–222, May 2011.
- [Dés89] Jacques Désarménien. Étude modulo n des statistiques mahoniennes. Séminaire Lotharingien de Combinatoire, 22(B22a):27–35, 1989.
- [Gor19] Ofir Gorodetsky. $q$-congruences, with applications to supercongruences and the cyclic sieving phenomenon. International Journal of Number Theory, May 2019.
- [Pan09] Dmitri I. Panyushev. On orbits of antichains of positive roots. European Journal of Combinatorics, 30(2):586–594, February 2009.
- [PR13] James Propp and Tom Roby. Homomesy in products of two chains. arXiv e-prints, 2013.
- [RS17] Sujit Rao and Joe Suk. Dihedral sieving phenomena. arXiv e-prints, 2017.
- [RSW04] Victor Reiner, Dennis Stanton and Dennis E. White. The cyclic sieving phenomenon. Journal of Combinatorial Theory, Series A, 108(1):17–50, October 2004.
- [Sag11] Bruce E. Sagan. The cyclic sieving phenomenon: a survey. In Surveys in Combinatorics 2011. Cambridge University Press, 2011.