2023-06-01

See the cyclic sieving phenomenon page for the definition and related theorems.

## Words and permutations

### Words

Let $X_n(\alpha)$ be the set of words of length $n$ and content $\alpha,$ that is, each word has $a_i$ entries equal to $i.$ The cyclic group $\grpc_n$ act on $X$ by cyclic shift, and let

\[ f_n(\alpha;q) \coloneqq \qbinom{n}{\alpha}_q = \sum_{w \in X_n(\alpha)} q^{\maj(w)} = \sum_{w \in X_n(\alpha)} q^{\inv(w)}. \]Then $(X_n,\grpc_n,f_n(\alpha;q))$ exhibits the CSP, see [RSW04].

### Multisets

Let $X_{n,k}$ be the set of $k$-multisets of $[n].$ Note that $|X_{n,k}| = \binom{n+k-1}{k}.$ For $n=3,$ $k=2$ we have

\[ X = \{11,12,13,22,23,33 \}. \]Let $\grpc_n = \langle g \rangle$ act on $X_{n,k}$ by the cycle $g=(123\dotsb n),$ so that $g\circ 23 = 31 = 13$ in the example above. Then

\[ \left( X_{n,k}, \grpc_n, \qbinom{n+k-1}{k}_q \right) \]exhibits the CSP, see [RSW04].

### Binary words with a twist

Let $X_n$ be the set of binary words and let $\eta$
act on $X_n$ by a *twisted cyclic shift*

which generates a cyclic group of order $2n,$ so $\langle \eta^2 \rangle$ is a cyclic group of order $n.$ Then

\[ \left(X_n, \langle \eta^2 \rangle, \prod_{j=0}^{n-1}(1+q^j) \right) \]exhibits the cyclic sieving phenomenon. This is proved in [ALP19].

By adjusting the $q$-analog a bit, one can show that

\[ \left(X_n, \langle \eta \rangle, \prod_{j=1}^{n}(1+q^j) \right) \]is an instance of CSP. Note that the $q$-binomial theorem implies that $\prod_{j=1}^{n}(1+q^j) = \sum_{k=0}^n q^{\binom{k+1}{2}} \qbinom{n}{k}.$

See also the example on subset-cyclic sieving, for restricting the set of words we act on.

It was pointed out to me by S. Hopkins that this also follows from [RS12], with cyclic sieving on minuscule posets of type $B$. The idea is to biject order ideals to binary words. This in turn is related to [Cor. 8.5, RSW04], by taking $k=0$ in their statement.

### General words with a twist

We can generalize the twisted binary words CSP.

**Definition.**

Let $W(n,k)$ denote the set of words of length $n$ with entries in $\{1,2,\dotsc,k\}.$ Given $w=(w_1,\dotsc,w_n) \in W(n,k),$ let $\phi(w) \coloneqq (w_n+1,w_1,w_2,\dotsc,w_{n-1}),$ where the addition is taken modulo $k.$ Note that $\phi^{\circ n}(w) = w+1$ and that it follows that $\phi^{\circ k}$ generate a cyclic group of order $n.$

**Conjecture (Alexandersson, 2022).**

For every $n,k\geq 1,$

\[ \left( W(n,k), \left\langle \phi \right\rangle, \prod_{j=1}^{n}\left(1+q^j+q^{2j}+q^{3j}+\dotsb+q^{(k-1)j}\right) \right) \]is a CSP-triple.

### Kreweras words

In this preprint, https://arxiv.org/pdf/2005.14031.pdf a CSP is conjectured on the set of Kreweras words of length $3n.$ These are in bijection with linear extensions of a certain poset, and also with so-called Kreweras webs. The group action is promotion in the linear extensions, which is equivalent with rotation of the webs.

### Lucas binary words

The following results are proved in [Gor19].

Let $LW_{n}$ be the set of binary words of length $n,$ such that there are no two consecutive ones, not even cyclically. We let $\grpc_n$ act on $LW_{n}$ by rotation. We note that $|LW_{n}|= L_n,$ a Lucas number, A000032. Define the $2\times 2$-matrix $A(x,t)$ with entries in $\setZ[q,t]$ as

\[ A(x,t)\coloneqq \begin{bmatrix} 1 & t \\ x & 0 \end{bmatrix} \]and let $|LW_{n}|_q \coloneqq \trace \left( A(q^{n-1},1) A(q^{n-2},1) \dotsm A(1,1) \right).$ This is a $q$-analog of $C_{n}.$ Then the following is a CSP-triple:

\[ \left( LW_n, \grpc_n, |LW_{n}|_q \right). \]This result can be refined in the following manner. Let $LW_{n,k}\subset LW_{n}$ be the subset of binary words with exactly $k$ ones. Let $|LW_{n,k}|_q \coloneqq [t^k] \trace \left( A(q^{n-1},t) A(q^{n-2},t) \dotsm A(1,t) \right).$ This is a $q$-analog of $LW_{n,k}$ and in fact,

\[ |LW_{n,k}|_q = \sum_{w \in LW_{n,k}} q^{\stat(w)} = q^{k^2-k}\qbinom{n-k+1}{k}_q - q^{n+(k-1)^2-k}\qbinom{n-k-1}{k-2}_q. \]where $\stat(w) = \sum_{i=1}^n [w_i=1] (n-i),$ using the Iverson bracket. We have the CSP-triple

\[ \left( LW_{n,k}, \grpc_n, |LW_{n,k}|_q \right). \]### Reduced words of $w_0$ in type B

Let $X_n$ be the set of all reduced words for the longest element in the type $B_n$ coxeter group. We can define major index on these. Let $C_{n^2}$ act on such reduced words by rotation. Then

\[ \left( X_n, C_{n^2}, q^{-n\binom{n}{2}}\sum_{w \in X_n} q^{\maj(w)} \right) \]is a CSP-triple. The proof in [PS10] is done via bijecting to $n\times n$-SYT and then using B. Rhoades result.

### Permutations of fixed type and exceedances

The following CSP is proved in [SSW11]. Let $S_{\lambda,j} \subseteq \symS_n$ be the set of permutations of cycle type $\lambda$ and exactly $j$ exceedances. Let $\grpc_n$ be generated by the long cycle $(1\,2\,3\,\dotsb\,n)$ and act on $S_{\lambda,j}$ by conjugation. Define

\[ f_{\lambda,j}(q) \coloneqq \sum_{\pi \in S_{\lambda,j} } q^{\maj(\pi) - \exc(\pi)}. \]Then $(S_{\lambda,j}, \grpc_n, f_{\lambda,j}(q))$ is a CSP-triple.

### Permutations

The following CSP is a special case of the CSP on binary matrices. Let $\symS_n$ be the set of permutations, seen as a list of pairs $\{i,\pi(i)\},$ $1 \leq i \leq n.$ We let $C_n = \langle g \rangle$ act on such pairs by $g \cdot \{i,\pi(i)\} = \{i+1,\pi(i)+1\},$ where addition is performed modulo $n.$

Then

\[ \left( \symS_n, C_n, \sum_{\lambda \vdash n} (f^{\lambda}(q))^2 \right) \]is a CSP-triple, where $f^{\lambda}(q)$ is the $q$-analog of the hook formula.

### Permutations of fixed shape

By using RSK, we have that the set $\SYT(\lambda) \times \SYT(\lambda)$ is in bijection with permutations in $\symS_n,$ which insert to a pair of Young tableaux of shape $\lambda.$ In [APRU20], we show that there exists a cyclic group action of order $n,$ such that for any $\lambda \vdash n,$

\[ \left( \SYT(\lambda) \times \SYT(\lambda), C_n, \left(f^{\lambda}(q)\right)^2 \right) \]is a CSP-triple. It is unclear what this group action might be.

Note that this refines the CSP on permutation matrices.

### Labelings of the path graph

The path graph $P_n$ on $n$ vertices has $n!$ labelings, using labels from $\setZ/n\setZ.$ The authors of [DMT23] study a version of promotion, named toric promotion. They introduce permutoric promotion which is an operator determined by a permutation $\pi$ in $\symS_n.$ The role of $\pi$ is to decide in which order to perform certain local toggles.

Permutoric promotion, $\mathrm{TPro}_{\pi},$ acts on labelings with order $d(n-d)$ where $d$ is the number of descents of $\pi^{-1}.$ They show that

\[ \left( \text{Labelings of $P_n$}, \mathrm{TPro}_{\pi}, n(d-1)!(n-d-1)! [n-d]_{q^d} \qbinom{n-1}{d-1}_q \right) \]is a CSP-triple.

## References

- [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.
- [APRU20] Per Alexandersson, Stephan Pfannerer, Martin Rubey and Joakim Uhlin. Skew characters and cyclic sieving. arXiv e-prints, 2020. To appear in SIGMA
- [DMT23] Colin Defant, Rachana Madhukara and Hugh Thomas. Permutoric promotion: gliding globs, sliding stones, and colliding coins. arXiv e-prints, 2023.
- [Gor19] Ofir Gorodetsky. $q$-congruences, with applications to supercongruences and the cyclic sieving phenomenon. International Journal of Number Theory, May 2019.
- [PS10] T. Kyle Petersen and Luis Serrano. Cyclic sieving for longest reduced words in the hyperoctahedral group. The Electronic Journal of Combinatorics, 17(1), April 2010.
- [RS12] David B. Rush and XiaoLin Shi. On orbits of order ideals of minuscule posets. Journal of Algebraic Combinatorics, 37(3):545–569, June 2012.
- [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.