Characters of symmetric groups: sharp bounds on virtual degrees and the Witten zeta function

Representation theory has been used to solve various problems in different areas of mathematics. A striking example is the pioneering work of Diaconis and Shahshahani on a random process called the random transposition shuffle [DS81]. They used character estimates to prove a sharp phase transition – now known as the cutoff phenomenon – concerning the minimum number of random transpositions whose product yields an almost uniform random permutation. This was the starting point of the field of mixing times, whose goal is to understand how long it takes for a random process to approach stationarity.

Other techniques to study mixing times were developed in the following years, notably by Aldous and Diaconis [Ald83, AD86], and mixing properties of emblematic card shufflings were precisely understood, also for small decks of cards [BD92]. We refer to [LP17] for an introduction to mixing times and to [DF23] for the mathematics of card shuffling.

A natural way to generalize Diaconis and Shahshahani’s random transposition shuffle on the symmetric group ${\mathfrak{S}}_{n}$ is to replace the conjugacy class of transpositions – from which we pick uniform elements – by another conjugacy class. In specific cases, a similar cutoff phenomenon was proved ; for $k$-cycles (where $k>n/2$) in [LP02] ; for $k$-cycles (where $k$ is fixed) in [BSZ11] ; for $k$-cycles (where $k=o(n)$) in [Hou16] ; and for all conjugacy classes whose support has size $o(n)$ in [BŞ19] (the support of a permutation is the set of its non-fixed points). Most of these results rely on representation theory. However, interestingly, the proof of [BSZ11] follows the cycle structure of the permutation obtained after several multiplications via probabilistic arguments, and that of [BŞ19], which is currently the best result for conjugacy classes with small support, relies on a curvature argument.

For conjugacy classes with cycle type $[r^{n/r}]$, Lulov [Lul96] proved that the mixing time is $3$ when $r=2$ and $2$ when $r\geq 3$. Lulov and Pak later conjectured in [LP02, Conjecture 4.1] that the mixing time is at most 3 for all fixed-point free conjugacy classes (i.e., without fixed points), and Larsen and Shalev [LS08] proved that conjecture.

In recent years, results were obtained concerning the cutoff profile of such processes, that is, what happens within the cutoff window (when we zoom in, around the phase transition). The cutoff profile of the random transposition shuffle was determined by the first author in [Tey20], and this was later generalized to $k$-cycles (for $k=o(n)$) by Nestoridi and Olesker-Taylor [NOT21]. Recently, another proof of the cutoff profile for transpositions was obtained by Jain and Sawhney [JS24], using a hybrid technique that combines probabilistic and representation theoretic arguments.

Motivated by various problems, including the study of mixing times of Markov chains, uniform bounds on characters have been established and sharpened over the past few decades. Roichman [Roi96] proved bounds that led to the correct order of the mixing time of conjugacy class walks on $\mathfrak{S}_{n}$ that have a number of fixed points of order $n$. This result was later strengthened by Müller and Schlage-Puchta [MSP07], who obtained results that are uniform over all conjugacy classes.

Sharp bounds for characters of permutations with few fixed points were proved in the landmark paper [LS08] of Larsen and Shalev. They proved several conjectures, among which the Lulov–Pak conjecture as discussed earlier. The bounds that we obtain here build on this paper ; see Section 1.2 for a more detailed description of their character bounds.

An important tool to estimate characters of ${\mathfrak{S}}_{n}$ is the Murnaghan–Nakayama rule (see e.g. Theorem 3.10 in [Mé17]), which is a key element in the proofs of [Roi96, MSP07, LS08]. On the other hand, other techniques have been proved to be more powerful for certain diagrams. Féray and Śniady [FS11] found uniform bounds on characters that are especially good for diagrams that do not have a long first line or column, using a reformulation of Stanley’s conjectured character formula. More precisely, [Fé10] proves Conjecture 3 from [Sta06], while the reformulation of Stanley’s formula appears as Theorem 2 in [FS11].

In a different direction, Lifschitz and Marmor [LM23] recently used a new technique called hypercontractivity to establish character bounds. They obtain uniform bounds on characters for permutations with at most a given number of cycles (instead of considering the full cycle structure, as done in the previously mentioned works). This allows them to consider permutations having up to $n/(\ln n)^{O(1)}$ cycles, thus covering new cases.

Bounds on characters play a crucial role in the broader context of finite groups, and were notably used to prove a conjecture due to Ore [LOST10]. General bounds on characters of finite classical groups were recently obtained by Guralnick, Larsen and Tiep [GLT20, GLT24], and uniform bounds on characters for all finite quasisimple groups of Lie type were established by Larsen and Tiep [LT24].

A canonical tool used to convert character bounds for a group $G$ into practical estimates for applications is the Witten zeta function. It is defined as $\zeta(s)=\sum_{\alpha}(d_{\alpha})^{-s}$ for $s>0$, where the sum is taken over all irreducible representations $\alpha$ of $G$, and $d_{\alpha}$ is the dimension of $\alpha$. Such a zeta function initially appeared in the computation of volumes of moduli spaces in Witten’s work [Wit91] (see Equation (4.72) there). Liebeck and Shalev proved bounds for the symmetric group [LS04] and for Fuchsian groups [LS05], which were useful for a variety of applications, including mixing times and covering numbers [LS08, LST24, KLS24]. We refer to [LS08], [LT24], and the survey article [Lie17] for further applications of characters bounds.

Throughout the paper, $\mathfrak{S}_{n}$ denotes the symmetric group of order $n$, and $\widehat{\mathfrak{S}_{n}}$ the set of its irreducible representations. For a permutation $\sigma$ and $i\in\{1,\ldots,n\}$, $f_{i}(\sigma)$ denotes the number of cycles of length $i$ in $\sigma$. By extension, for a conjugacy class ${\mathcal{C}}$, we denote by $f_{i}({\mathcal{C}})$ the number of cycles of length $i$ in any permutation $\sigma\in{\mathcal{C}}$. In addition, we will use the convenient notation $f=\max(f_{1},1)$. For convenience, we will use $\lambda$ to simultaneously denote a representation, the associated integer partition, and the associated Young diagram (see Section 2.1 for definitions). If $E$ is a finite set, we denote by $\operatorname{\mathrm{Unif}}_{E}$ the uniform probability measure on $E$.

We describe here the results of Larsen and Shalev [LS08], whose improvement is the main purpose of the paper. We assume familiarity with the representation theory of symmetric groups and will follow the notation from the textbook [Mé17]: we denote by $d_{\lambda}$ the dimension of a representation $\lambda$, $\operatorname{\mathrm{ch}}^{\lambda}(\sigma)$ the character of $\lambda$ evaluated at a permutation $\sigma\in\mathfrak{S}_{n}$, and $\chi^{\lambda}(\sigma)=\frac{\operatorname{\mathrm{ch}}^{\lambda}(\sigma)}{d_{\lambda}}$ the associated normalized character.

Larsen and Shalev obtained character bounds by introducing and studying new objects. One of them is called the virtual degree $D(\lambda)$ of a representation $\lambda$. It is defined as

where $a_{i}=\lambda_{i}-i$ and $b_{i}=\lambda^{\prime}_{i}-i$. Here $\lambda_{i}$ (resp. $\lambda^{\prime}_{i}$) denotes the size of the $i$-th row (resp. $i$-th column) of the Young diagram associated to $\lambda$ (see Section 2.1 for precise definitions). The virtual degree is a convenient substitute for the dimension $d_{\lambda}$, which allows for easier computations. See Section 2.3 for more details.

Another object introduced in [LS08] is the orbit growth exponent $E(\sigma)$. Let $n\geq 1$ and $\sigma\in\mathfrak{S}_{n}$. Denote by $f_{i}(\sigma)$ the number of cycles of length $i\geq 1$ of $\sigma$, and for $k\geq 1$, set $\Sigma_{k}=\Sigma_{k}(\sigma):=\sum_{1\leq i\leq k}if_{i}(\sigma)$. We define the orbit growth sequence $(e_{i})_{i\geq 1}$ by $n^{e_{1}+\ldots+e_{i}}=\max\left(\Sigma_{i},1\right)$ for all $i\geq 1$, and set

A key intermediate result that Larsen and Shalev proved is the following, which we will refer to as a theorem.

This is proved via an elegant induction in the proof of their main theorem (for reference, the induction hypothesis is [LS08, Eq. (17)]), where the orbit growth exponent $E(\sigma)$ naturally appears. They also showed that $D(\lambda)$ cannot be much larger than $d_{\lambda}$.

Combining Theorem 1.1, Theorem 1.2 and the fact that $E(\sigma)\leq 1$ for all $\sigma$, they obtain the following character bound.

The orbit growth exponent $E(\sigma)$ defined in (1.2) looks complicated at first glance, but it is actually simple to compute and appears to lead to the best possible character bounds in different regimes such as in (1.6) below.

Let us give a few important examples of values of $E(\sigma)$. We always denote by $f_{1}$ the number of fixed points of a permutation $\sigma$ and set $f=\max(f_{1},1)$.

Combining Theorem 1.3 with Example 1.4 (b), Larsen and Shalev obtained the following bound as $n\to\infty$, uniform over fixed-point free permutations $\sigma\in\mathfrak{S}_{n}$ and irreducible representations $\lambda\in\widehat{\mathfrak{S}_{n}}$,

This allowed them to prove the abovementioned conjecture of Lulov and Pak, and even extend it (in Theorem 1.8) to the mixing time of conjugacy classes that have a small number of fixed points.

We present here our main contributions: the main result, Theorem 1.5, which improves on Theorem 1.2, provides uniform bounds on virtual degrees and allows us to obtain refined character bounds (Theorem 1.6). Proposition 1.8 provides bounds on the Witten zeta function, which we apply together with Theorem 1.6 to characterize fixed-point free conjugacy classes that mix in 2 steps (Theorem 1.9). We also deduce from our bounds that conjugacy classes with $o(\sqrt{n})$ cycles mix fast (Theorem 1.10), and finally that there is a cutoff whenever the conjugacy class has a large support and no short cycles (Theorem 1.12).

We will show in Section 4.4 that Theorem 1.5 is sharp for different shapes of diagrams.

Plugging this into Theorem 1.1, we get the following character bound.

In Proposition 5.1 we prove that $E(\sigma)\leq\frac{\ln\left(\max(\operatorname{\mathrm{cyc}}(\sigma),2)\right)}{\ln n}$, where $\operatorname{\mathrm{cyc}}(\sigma)$ is the number of cycles of $\sigma$. This allows us to deduce the following character bound, which improves on [LS08, Theorem 1.4] and [LM23, Theorem 1.7].

We now define the Witten zeta function. For $n\geq 1$, $A\subset\widehat{\mathfrak{S}_{n}}$ and $s\geq 0$,

Note that compared to the usual definition where the sum is over all irreducible representations, we add the subset of representations $A$ on which we sum as a parameter of the function $\zeta_{n}$.

In [LS04], Liebeck and Shalev proved that $\zeta_{n}(\widehat{\mathfrak{S}_{n}}^{**},s)=O(n^{-s})$, if $s>0$ is fixed and $n\to\infty$, where $\widehat{\mathfrak{S}_{n}}^{**}=\widehat{\mathfrak{S}_{n}}\backslash\left\{[n],[1^{n}]\right\}$. We improve their result to allow the argument $s$ to tend to 0.

In Section 6, we will also prove variants of Proposition 1.8, for other subsets $A\subset\widehat{{\mathfrak{S}}_{n}}$, and when $s_{n}$ is of order $\frac{1}{\ln n}$.

As an application of our bounds on characters and on the Witten zeta function, we are able to characterize which fixed-point free conjugacy classes mix in 2 steps. We recall that the convolution product of two measures $\mu,\nu$ on a group $G$ is defined by $\mu\ast\nu(g)=\sum_{x\in G}\mu(x)\nu(gx^{-1})$ for $g\in G$. As such, if $S\subset G$, then $\operatorname{\mathrm{Unif}}_{S}^{*t}$ is the distribution of the simple random walk (started at the neutral element) on the Cayley graph $\operatorname{\mathrm{Cay}}(G,S)$ after $t$ steps.

We also prove that conjugacy classes with few cycles mix fast.

We believe that the only parts of the cycle structure that affect mixing times are the number of fixed points and the number of transpositions. We make the following conjecture.

As a third application, we finally show that conjugacy classes with a large support and no short cycles exhibit cutoff. If ${\mathcal{C}}$ is a conjugacy class on ${\mathfrak{S}}_{n}$ and $t\geq 0$, we denote $\mathfrak{E}({\mathcal{C}},t)$ the set $\mathfrak{S}_{n}\backslash\mathfrak{A}_{n}$ if ${\mathcal{C}}\subset\mathfrak{S}_{n}\backslash\mathfrak{A}_{n}$ and $t$ is odd, and $\mathfrak{A}_{n}$ otherwise.

Section 2 is devoted to preliminaries on Young diagrams and some elementary results. We recall there in particular the celebrated hook length formula.

In Section 3.1, we introduce the sliced hook products. This generalizes the idea of replacing the whole hook product of a diagram by a simpler product to any set partition of a diagram. In Section 3.2, we study sliced hook products and obtain precise approximations of (classical) hook products. A key result is the bound $d_{\lambda}\geq\binom{n}{|c|}d_{s}d_{c}e^{6\sqrt{|c|}}$ presented in Proposition 3.8 (b), which improves on [LS08, Lemma 2.1]. Here, $s$ denotes the external hook of $\lambda$ and $c=\lambda\backslash s$ is the center of $\lambda$ (as drawn in Section 2.3). In Section 3.3, we introduce the notion of augmented dimension $d_{\lambda}^{+}$ and consider some of its useful properties.

In Section 4 we use the results of Section 3.2 to prove Theorem 1.5 in two steps. We first show in Section 4.2 that the virtual degree $D(\lambda)$ and the augmented dimension $d_{\lambda}^{+}$ are close to each other. We then prove in Section 4.3, by induction, slicing the external hooks of diagrams $\lambda$, that $d_{\lambda}^{+}=d_{\lambda}^{1+O(1/\ln|\lambda|)}$. Finally, in Section 4.4 we provide examples that show that Theorem 1.5 is sharp up to the value of the constant.

Section 5 is devoted to the proof of Theorem 1.7, which shows character bounds in terms of the number of cycles.

In Section 6, we improve the bounds from Liebeck and Shalev [LS04] on the Witten zeta function and prove Proposition 1.8.

In Section 7, we apply the previous results and characterize which fixed-point free conjugacy classes mix in 2 steps, proving Theorem 1.9.

Finally, we prove in Section 8 Theorems 1.10 and 1.12 about mixing time estimates for specific conjugacy classes.

We say that $\lambda:=[\lambda_{1},\ldots,\lambda_{k}]$ is a partition of the integer $n$ if $\lambda_{i}\in\mathbb{Z}_{\geq 1}:=\{1,2,\ldots\}$ for all $1\leq i\leq k$, $\lambda_{i}\geq\lambda_{i+1}$ for all $i\leq k-1$, and $\sum_{i=1}^{k}\lambda_{i}=n$. We write $\lambda\vdash n$ if $\lambda$ is a partition of $n$. It turns out that integers partitions of $n$ are in bijection with irreducible representations of ${\mathfrak{S}}_{n}$, which makes it a good tool to study characters.

A common and useful way to code an integer partition (and thus a representation of ${\mathfrak{S}}_{n}$) is through Young diagrams. The Young diagram of shape $\lambda:=\left[\lambda_{1},\ldots,\lambda_{k}\right]$ (where $\lambda$ is a partition of an integer $n$) is a table of boxes, whose $i$-th line is made of $\lambda_{i}$ boxes, see Fig. 1 for an example.

We also denote by $\lambda$ this Young diagram, and say that $n$ is its size.

Let $\lambda$ be a Young diagram. If $u\in\lambda$, the hook of $u$ in $\lambda$ is the set of boxes on the right or above $u$, including $u$. We call hook length the size of this set and denote it by $H(\lambda,u)$. See Fig. 2 for an example.

Let us now consider a subset of boxes $E\subset\lambda$. We define

the hook-product of $E$ in $\lambda$. See Fig. 3 for an example.

We can now state the hook-length formula. Let $\lambda$ be a Young diagram and $n:=|\lambda|$ its number of boxes. A standard tableau of $\lambda$ is a filling of $\lambda$ with the numbers from 1 to $n$ such that the numbers are increasing on each line and column. We denote by $\operatorname{ST}(\lambda)$ the set of standard tableaux of $\lambda$, and $d_{\lambda}:=|\operatorname{ST}(\lambda)|$, see Fig. 4. It is well-known that $d_{\lambda}$ is the dimension of the irreducible representation of the symmetric group associated to $\lambda$.

The hook-length formula was discovered in 1953 by Frame, Robinson, and Thrall [FRT54], and allows to compute the number of standard tableaux of a diagram looking only at its hook lengths: for any diagram $\lambda$ of size $n$, we have

Let us define some notation that we will use for diagrams. To keep the notation light, we will usually use the same pieces of notation for both the diagrams and their lengths. For example we will say the first line of $\lambda$ is $\lambda_{1}$ and has length $\lambda_{1}$. If we want to emphasize that we are considering a diagram or a size, we will add brackets or absolute values. For example we can say that the first line $\left[\lambda_{1}\right]$ has length $\left|\lambda_{1}\right|$.

Fig. 5 illustrates these definitions on diagrams.

We collect here standard or elementary results that we will us throughout the paper. We give proofs for completeness.

Despite being elegant, the hook-length formula may be tricky to use, because of how hard it is to estimate hook products. The idea is to take into account only part of the hook lengths, making the resulting product easier to compute and to use.

We first extend the definition of hook lengths to any set of boxes. We represent boxes by the coordinates of their top right corner in the plane ${\mathbb{Z}}^{2}$. As such a box can be seen as an element of ${\mathbb{Z}}^{2}$ and a set of boxes is a subset $S\subset{\mathbb{Z}}^{2}$, see Fig. 6.

Let us give some examples of slicings. We will each time provide an example where the $\nu_{i}$ are represented in different colors, and the boxes of the diagrams $\lambda$ are filled with their sliced hook lengths.

Let us define, for any Young diagrams $\mu\subset\lambda$ and any set partition $P$ of $\lambda$, the ratio

If $P$ is the $ab\delta$-(resp. $\lambda_{1}$-, $\lambda^{1}$-)slicing, we denote the corresponding ratio by $R_{ab\delta}$ (resp. $R_{\lambda_{1}}$, $R_{\lambda^{1}}$).

We start with rewriting the ratio, in the case of a slicing with respect to the first line.

Let us now prove various bounds on $\lambda_{1}$-slicings. To ease notations, we set as before $r:=\lambda_{\geq 2}$. We start with a lemma which will be useful at several places.