Descents and cyclic descents

Submitted by Ron M. Adin and Yuval Roichman

The descent set of a permutation $\pi = [\pi_1, \ldots, \pi_n]$ in the symmetric group $\mathfrak{S}_n$ on $[n]:=\{1,2,\dots,n\}$ is

$\mathrm{Des}(\pi) := \{1 \le i \le n-1 \,:\, \pi_i > \pi_{i+1} \} \quad \subseteq [n-1]$ ,

whereas its cyclic descent set is

$\mathrm{cDes}(\pi) := \{1 \leq i \leq n \,:\, \pi_i > \pi_{i+1} \} \quad \subseteq [n]$ ,

with the convention $\pi_{n+1}:=\pi_1$ ; see, e.g., [3, 4].

The descent set of a standard Young tableau (SYT) $T$ is

$\mathrm{Des}(T) := \{1 \le i \le n-1 \,:\, i+1 \text{ appears in a lower row of }T\text{ than }i\}$ .

For a set $I \subseteq [n-1]$ let ${\bf x}^I := \prod_{i \in I} x_i$ and ${\bf y}^I := \prod_{i \in I} y_i$ . The Robinson-Schensted correspondence implies

$(*) \quad \quad \displaystyle \sum_{\pi \in \mathfrak{S}_n} {\bf x}^{\mathrm{Des}(\pi)} {\bf y}^{\mathrm{Des}(\pi^{-1})} = \sum_{\lambda \vdash n} \sum_{P,Q \in \mathrm{SYT}(\lambda)} {\bf x}^{\mathrm{Des}(Q)} {\bf y}^{\mathrm{Des}(P)}$ ,

where the first summation in the RHS is over all partitions of $n$ , and $\mathrm{SYT}(\lambda)$ denotes the set of all SYT of shape $\lambda$ .

OPAC-013. Find a cyclic analogue of Equation (*).

As a first step, note that Equation (*) implies

$(**) \quad \quad \displaystyle \sum_{\pi \in \mathfrak{S}_n} {\bf x}^{\mathrm{Des}(\pi)} = \sum_{\lambda \vdash n} \#\mathrm{SYT}(\lambda) \sum_{T \in \mathrm{SYT}(\lambda)} {\bf x}^{\mathrm{Des}(T)}$ .

Definition [1]. Let $n \ge 2$ , and let $\mathcal{T}$ be any finite set equipped with a descent map $\mathrm{Des}: \mathcal{T} \to 2^{[n-1]}$ . Consider the cyclic shift $\mathrm{sh}: [n] \to [n]$ , mapping $i$ to ${i+1 \pmod n}$ , extended naturally to $2^{[n]}$ . A cyclic extension of the descent map $\mathrm{Des}$ is a pair $(\mathrm{cDes},p)$ , where $\mathrm{cDes}: \mathcal{T} \to 2^{[n]}$ is a map and $p: \mathcal{T} \to \mathcal{T}$ is a bijection, satisfying the following axioms: for all $T \in \mathcal{T}$ ,

(extension) $\mathrm{cDes}(T) \cap [n-1] = \mathrm{Des}(T)$ ,
(equivariance) $\mathrm{cDes}(p(T)) = \mathrm{sh}(\mathrm{cDes}(T))$ ,
(non-Escher) $\varnothing \subsetneq \mathrm{cDes}(T) \subsetneq [n]$ .

For example, letting $\mathcal{T}=\mathfrak{S}_n$ be the symmetric group, the map $\mathrm{cDes}(\pi)$ defined above and the rotation $p([\pi_1,\pi_2,\ldots,\pi_{n-1},\pi_n]) := [\pi_n,\pi_1,\pi_2,\ldots,\pi_{n-1}]$ determine a cyclic extension of the map $\mathrm{Des}(\pi)$ defined above.

A cyclic extension of the tableaux descent map $\mathrm{Des}(T)$ defined above, for SYT of rectangular shapes, was introduced in [9]. In fact, this descent map on $\mathrm{SYT}(\lambda/\mu)$ has a cyclic extension if and only if the skew shape $\lambda/\mu$ is not a connected ribbon [1, Theorem 1.1]; a constructive proof of this result was recently given in [7]. All cyclic extensions of $\mathrm{Des}$ on $\mathrm{SYT}(\lambda/\mu)$ share the same distribution of $\mathrm{cDes}$ .

The following cyclic analogue of (**) was proved in [1, Theorem 1.2]:

$(***) \quad \quad \displaystyle \sum_{\pi \in \mathfrak{S}_n} {\bf x}^{\mathrm{cDes}(\pi)} = \hspace{-0.1cm} \displaystyle \sum_{\substack{\text{non-hook} \\ \lambda \vdash n}} \#\mathrm{SYT}(\lambda) \sum_{T \in \mathrm{SYT}(\lambda)} {\bf x}^{\mathrm{cDes}(T)} + \displaystyle \sum_{k=1}^{n-1} \binom{n-2}{k-1} \sum_{T \in \mathrm{SYT}((1^k) \oplus (n-k))} {\bf x}^{\mathrm{cDes}(T)}$

OPAC-014. Find a Robinson-Schensted-style bijective proof of Equation (***).

By a classical theorem of Gessel and Reutenauer [5, Theorem 2.1], there exists a collection of non-negative integers $\{m_{\lambda,\mu}\}_{\lambda, \mu \,\vdash n}$ such that for every conjugacy class $C_\mu$ of type $\mu$ in $\mathfrak{S}_n$

$(\dagger) \quad \quad \displaystyle \sum_{\pi \in C_\mu} {\bf x}^{\mathrm{Des}(\pi)} = \sum_{\lambda \vdash n} m_{\lambda,\mu} \sum_{T \in \mathrm{SYT}(\lambda)} {\bf x}^{\mathrm{Des}(T)}$ .

OPAC-015. Find a bijective proof of Equation (†).

A bijective proof of a cyclic extension of Equation (†), like the one given in [6, Theorem 6.2], is also desired.

Thrall [11] asked for a description of the coefficients of in Equation (†); for recent discussions see, e.g., [8, 2, 10]. Particularly appealing is a combinatorial interpretation of $m_{\lambda,\mu}$ as the cardinality of a nice set of objects. This has been done in some special cases – for example, when $\lambda$ is a hook-shaped partition:

$m_{(n-k,1^k),\mu} = \#\{\pi\in C_\mu \,:\, \mathrm{Des}(\pi)=[k]\} \qquad (0 \le k \le n-1)$ .

OPAC-016. For which partitions $\mu\vdash n$ is the sequence $\{m_{(n-k,1^k),\mu}\}_{k=0}^{n-1}$ unimodal?

It is known that this sequence is unimodal for $\mu=(n)$ , and conjecturally the same holds for all rectangular shapes $\mu=(r^s)$ ; see [6].

Unlike the full symmetric group, when restricted to a general conjugacy class the definition of $\mathrm{cDes}(\pi)$ given above does not yield a cyclic extension of $\mathrm{Des}$ . However, the following holds.

Theorem [6, Theorem 1.4]. The descent map $\mathrm{Des}$ on a conjugacy class $C_\mu$ of $\mathfrak{S}_n$ has a cyclic extension $(\mathrm{cDes},p)$ if and only if the partition $\mu$ is not of of the form $(r^s)$ for a square-free $r$ .

The proof involves higher Lie characters and does not provide an explicit description of the extension.

OPAC-017. Find an explicit combinatorial description for the cyclic extension of $\mathrm{Des}$ on a conjugacy class of $\mathfrak{S}_n$ , whenever such an extension exists.

References:

[1] R. M. Adin, V. Reiner and Y. Roichman, On cyclic descents of standard Young tableaux, Int. Math. Res. Not. IMRN, forthcoming (2018). DOI: 10.1093/imrn/rny280

[2] C. Ahlbach and J. P. Swanson, Cyclic sieving, necklaces, and branching rules related to Thrall’s problem, Electron. J. Combin. 25 (2018), no. 4, P4.42. DOI: 10.37236/8198

[3] P. Cellini, Cyclic Eulerian elements, Europ. J. Combin. 19 (1998), 545–552. DOI: 10.1006/eujc.1998.0218

[4] K. Dilks, K. Petersen and J. Stembridge, Affine descents and the Steinberg torus, Adv. in Applied Math. 42 (2009), 423–444. DOI: 10.1016/j.aam.2008.11.002

[5] I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Series A 64 (1993), 189–215. DOI: 10.1016/0097-3165(93)90095-P

[6] P. Hegedüs and Y. Roichman, Higher Lie characters and cyclic descent extension on conjugacy classes, prepint (2019). arXiv:1909.04460

[7] B. Huang, Cyclic descents for general skew tableaux, J. Combin. Theory Ser. A 169 (2020). DOI: 10.1016/j.jcta.2019.105120

[8] V. Reiner, Thrall’s problem and coarsenings, Banff workshop on positivity in algebraic combinatorics, lecture slides, 2015. Available online here.

[9] B. Rhoades, Cyclic sieving, promotion, and representation theory, J. Combin. Theory Ser. A 117 (2010), 38–76. DOI: 10.1016/j.jcta.2009.03.017

[10] S. Sundaram, On a variant of $\mathrm{Lie}_n$ , Sém. Lothar. Combin. 80B (2018), Art. 19. Available online here.

[11] R. Thrall, On symmetrized Kronecker powers and the structure of the free Lie ring, Amer. J. Math. 64 (1942), 371–388. DOI: 10.2307/2371691

One thought on “Descents and cyclic descents”

Amy Pang says:

April 28, 2020 at 12:11 pm

I just want to say that I may be looking at OPAC-017, the explicit construction of cyclic descent extensions of conjugacy classes of permutations, with some undergrads. I’d be interested to know if anyone else is working on this, so we don’t overlap. Thanks!

LikeLike

Share this:

Related

One thought on “Descents and cyclic descents”

Leave a comment Cancel reply