# Bounds for Characters of the Symmetric Group: A Hypercontractive Approach

Noam Lifshitz , and Avichai Marmor Einstein institute of Mathematics, Hebrew
University<EMAIL_ADDRESS>Supported by the Israel Science Foundation
(grant no. 1980/22).Department of Mathematics, Bar-Ilan University.
<EMAIL_ADDRESS>Partially supported by the Israel Science Foundation,
Grant No. 1970/18, and by the European Research Council under the ERC starting
grant agreement No. 757731 (LightCrypt).

###### Abstract

Finding upper bounds for character ratios is a fundamental problem in
asymptotic group theory. Previous bounds in the symmetric group have led to
remarkable applications in unexpected domains. The existing approaches
predominantly relied on algebraic methods, whereas our approach combines
analytic and algebraic tools. Specifically, we make use of a tool called
‘hypercontractivity for global functions’ from the theory of Boolean
functions. By establishing sharp upper bounds on the $L^{p}$-norms of
characters of the symmetric group, we improve existing results on character
ratios from the work of Larsen and Shalev [Larsen, M., Shalev, A. Characters
of symmetric groups: sharp bounds and applications. Invent. math. 174, 645–687
(2008)]. We use our norm bounds to bound Kronecker coefficients, Fourier
coefficients of class functions, product mixing of normal sets, and mixing
time of normal Cayley graphs. Our approach bypasses the need for the
$S_{n}$-specific Murnaghan–Nakayama rule. Instead we leverage more flexible
representation theoretic tools, such as Young’s branching rule, which
potentially extend the applicability of our method to groups beyond $S_{n}$.

##  1 Introduction

In this paper, we introduce tools from analysis of Boolean functions and apply
them to the study of character ratios in symmetric groups. Since the seminal
work of Diaconis and Shahshahani [3] from 1981, the problem of estimating the
character ratios $\frac{\chi(\sigma)}{\chi(1)}$ of a finite group became one
of the most prominent problems in asymptotic group theory. For instance,
according to Gurevich and Howe [12], it is the core open problem of harmonic
analysis over finite groups. The works of Roichman [25], Müller–Schlage-Puchta
[21], and Larsen–Shalev [19] each presented new bounds for character ratios,
and found applications in a wide variety of unexpected areas. These areas
include the theory of Fuchsian groups, Cayley graphs with random generators,
Waring type problems in finite simple groups, and mixing times and covering
numbers corresponding to sets closed under conjugation.

Our main result provides a new upper bound on the character ratios
$\left|\frac{\chi(\sigma)}{\chi(1)}\right|$ in $S_{n}$ in terms of the number
of cycles of $\sigma$ (see Theorem 1.7 below). We prove essentially the best
possible upper bounds on the character ratios in terms of a certain parameter
of $\chi$ that we call _level_ and the number of cycles of $\sigma$. Our
notion of level deviates slightly from the one introduced by Kleshchev, Larsen
and Tiep [18], which we refer to as _strict level_. It turns out that our
level parameter is better at capturing the true nature of the character ratios
compared to the dimension of the corresponding irreducible representations.

Our technique differs substantially from previous approaches which heavily
depended on explicit formulas for the characters, such as the
Murnaghan–Nakayama rule. In this paper, we demonstrate the power of a tool
from the theory of Boolean functions known as ‘hypercontractivity for global
functions’ [15, 17] in this context. A variant of the hypercontractivity
theorem for global functions over the symmetric group was first presented by
Filmus, Kindler, Lifshitz and Minzer [8], and reached its full power in a
recent work of Keevash and Lifshitz [14]. Hypercontractivity for global
functions is the main tool that enables our improved bounds, and it also has
an extra benefit: our method is much more versatile than the $S_{n}$-specific
Murnaghan–Nakayama rule. In order to obtain our character bounds the only tool
from the representation theory of $S_{n}$ that we apply is Young’s branching
rule, which allows us to decompose restricted representation into irreducible
constituents. While explicit formulas for the characters are rare in other
groups, the so called ‘branching problem’ is better understood.

Before delving into our results about character ratios in Section 1.2, we
first explore their applications to mixing times of Cayley graphs.

###  1.1 A sample application for mixing times of Cayley graphs

In 1984 Diaconis and Shahshahani [3] determined the mixing time of the lazy
random walk of the normal Cayley graph
$\mathrm{Cay}\left(S_{n},(ij)^{S_{n}}\right)$ corresponding to the
transpositions by computing their character ratios. Ever since, upper bounds
on character ratios played a key role in the analysis of the mixing times of
normal Cayley graphs over either $A_{n}$ or $S_{n}$ (see, e.g., Roichman [25],
Müller and Schlage-Puchta [21], and Larsen and Shalev [19]).

To avoid sign issues we restrict our attention to mixing times of normal
random walks on the alternating group $A_{n}$, but our result extends to
$S_{n}$. Let $\mu$ be a probability measure on the alternating group. We
associate to $\mu$ the function $f(\sigma)=\frac{n!}{2}\mu(\sigma)$ that
satisfies $\|f\|_{1}=1.$ The measure $\mu$ corresponds to a (right-invariant)
random walk, where a permutation $\sigma\in A_{n}$ walks to $\tau\sigma$ for a
random $\tau\sim\mu.$ The function corresponding to $\ell$ steps of the random
walk is given by the iterated self convolution $f^{*\ell},$ where the
convolution is given by

$f*g(\tau)=\mathbb{E}_{\sigma\sim A_{n}}[f(\sigma^{-1})g(\sigma\tau)].$

The $(\varepsilon,L^{p})$-_mixing time_ of the random walk is the minimal
$\ell$ such that $\|f^{*\ell}-1\|_{p}<\varepsilon.$ It is well known (and
follows from Young’s convolution inequality) that the $L^{p}$-mixing times are
monotonically increasing with respect to $p$ and that the $L^{\infty}$-mixing
time is at most twice the $L^{2}$-mixing time. It is therefore customary to
restrict the attention to the case where $p$ is either $1$ or $2.$ We remark
that in the special case where $\mu$ is the uniform measure on a set $A$, we
have $f=\frac{n!1_{A}}{2|A|}$ and the random walk corresponds to the simple
random walk on the Cayley graph $\mathrm{Cay}(A_{n},A)$. For brevity, we
sometimes refer to the mixing times of this random walk as the mixing time of
$A$.

Müller and Schlage-Puchta [21] computed the mixing time of
$\mathrm{Cay}(A_{n},\sigma^{S_{n}})$ up to a constant factor in terms of the
number of fixed points of $\sigma$, via character theoretic methods. This led
Larsen and Shalev [19] to investigate the more refined problem of
characterizing conjugacy classes of $S_{n}$ with mixing times $\leqslant\ell$.
When $\ell$ is fixed and $n$ goes to infinity, Larsen and Shalev [19] provided
a satisfying solution to this problem in terms of very complicated parameters
that they introduced. Then, to simplify their result, they upper bounded the
mixing time in terms of simpler functions of $\sigma$. One parameter of
particular interest is the density of $\sigma^{S_{n}}$. This related their
bound to a long line of works in the theory of growth in groups, which aims to
find conditions implying that the sizes of the sets $A^{i}:=\\{a_{1}\cdots
a_{i}:a_{1},\ldots,a_{i}\in A\\}$ grow rapidly with $i$ (see the survey [13]
for more details).

In particular, Larsen and Shalev posed the following problem:

######  Problem 1.1 ([19]).

Given positive integers $\ell,n$, what is the largest possible density of an
even normal set $A$ of $S_{n}$ which has $(1/e,L^{1})$-mixing time $>\ell$?

Suppose that $n$ is sufficiently large an let $m=\lfloor n^{1-1/\ell}\rfloor$
for some integer $\ell$, and consider the conjugacy class $A$ of all
permutations with $m$ fixed points and a single $(n-m)$-cycle (if the
conjugacy class $A$ is odd, replace $m$ with $m+1$). Müller and Schlage-Puchta
[21] showed that the mixing time of $A$ is larger than $\ell$. The density of
$A$ is given by:

$\frac{2|A|}{n!}=\frac{2}{m!(n-m)}\geqslant n^{-Cn^{1-1/\ell}}$

for some constant $C>0$. Larsen and Shalev were fairly close to showing that
the above construction is essentially optimal by showing the following.

######  Theorem 1.2 ([19, Theorem 6.8]).

For each $\varepsilon>0$ there exists $n_{0},$ such that the following holds.
Let $\ell$ be an integer and let $n>n_{0}.$ Suppose that $A\subseteq A_{n}$ is
a normal subset of $S_{n}$ of density $\geqslant
n^{-n^{1-1/\ell-\varepsilon}}$, then the $(\varepsilon,L^{2})$ mixing time of
$A$ is at most $\ell.$

Due to the $\varepsilon$ in the double exponent, Larsen and Shalev’s result
holds only when $\ell$ is constant. We improve their result and produce an
essentially optimal result when $\ell$ is up to logarithmic in $n$. Moreover,
our result is applicable to all normal subsets of $A_{n}$ and not only to even
normal subsets of $S_{n}$.

######  Theorem 1.3.

For each $\varepsilon>0$ there exists $c>0,$ such that the following holds.
Let $n\in\mathbb{N}$ and let $1<\ell<\frac{c\log n}{\log\log n}$ be integers.
Suppose that $A\subseteq A_{n}$ is a normal subset of $A_{n}$ of density
$\geqslant n^{-cn^{1-1/\ell}}$, then the $(\varepsilon,L^{2})$ mixing time of
$A$ is at most $\ell.$

Our result follows from the following more general version, which is
applicable for arbitrary class functions and not only for indicators of sets.

######  Theorem 1.4.

For each $\varepsilon>0$ there exist $c,C>0,$ such that the following holds.
Let $f_{1},\ldots f_{\ell}$ be nonnegative class functions over $A_{n}$ whose
$L^{1}$-norm is 1. Let
$\alpha_{1},\ldots\alpha_{\ell}\in\left(0,1-\frac{C\log\log n}{\log n}\right)$
be positive numbers with $\alpha_{1}+\cdots+\alpha_{\ell}\leqslant\ell-1$.
Suppose that $\|f_{i}\|_{2}\leqslant n^{c\alpha_{i}n^{\alpha_{i}}}$ for all
$i$. Then

$\|f_{1}*\cdots*f_{\ell}-1\|_{2}<\varepsilon.$

We also deduce the following interesting dichotomy. For each normal random
walk on $A_{n}$ that starts at the identity we either have an unproportional
probability of returning to the same place after two steps or we are mixed.
Since class functions on $A_{n}$ may have $f(\sigma)\neq f(\sigma^{-1})$, we
must assume that $f$ is _symmetric_ , i.e., that $f(\sigma)=f(\sigma^{-1}).$

######  Corollary 1.5.

For each $\varepsilon>0$ there exists $c>0$, such that the following holds.
Let $f\colon A_{n}\to\left[0,\infty\right)$ be a symmetric class function
having $L^{1}$-norm 1. Suppose $f*f(1)<n^{c\sqrt{n}}.$ Then
$\|f*f-1\|_{2}<\varepsilon$.

In Section 2 we present other application of our techniques to the study of
diameters, Kronecker coefficients, and products of normal sets.

###  1.2 Upper bounds on character ratios

In their seminal result, Larsen and Shalev [19] established a general,
complicated bound on the character ratios $\frac{\chi(\sigma)}{\chi(1)}$.
Then, they derived the following bound in terms of the number of cycles of
$\sigma$.

######  Theorem 1.6 ([19, Theorem 1.4], restated).

For all $\varepsilon>0$ there exists $n_{0}$, such that if $n>n_{0},$
$\alpha\in(0,1-\varepsilon)$ and a permutation $\sigma$ has at most
$n^{\alpha}$ cycles, then

$\left|\frac{\chi(\sigma)}{\chi(1)}\right|\leqslant\chi(1)^{\alpha-1+\varepsilon}$

for all irreducible characters $\chi.$

The result of Larsen and Shalev is sharp up to the $\varepsilon$ in the
exponent. However, this $\varepsilon$ in the exponent prevents their result
from providing meaningful estimates when $\sigma$ has more than $n^{1-o(1)}$
cycles. We get rid of the $\varepsilon$, thereby improving the bound and
getting effective results for permutations having up to
$\frac{n}{\log^{O(1)}n}$ cycles.

######  Theorem 1.7.

There exist absolute constants $c,C>0$ such that the following holds. Let
$\alpha\in(\frac{1}{c\log n},1-\frac{C\log\log n}{\log n})$. Suppose that
$\sigma\in S_{n}$ has at most $c\alpha n^{\alpha}$ cycles. Then

$\left|\frac{\chi(\sigma)}{\chi(1)}\right|\leqslant\chi(1)^{\alpha-1}$

for all irreducible characters $\chi$.

Clearly, this bound is not universally tight for all permutations, evident
from the inherent variability in character values among permutations sharing
the same cycle count. Nevertheless, for numerous combinations of $\chi$ and
the cycle count of $\sigma$, it turns out that Theorem 1.7 represents
approximately the best achievable bound based solely on the number of cycles:

######  Theorem 1.8.

For all $0<\varepsilon<1$ there exist $n_{0}\in\mathbb{N}$ and $c>0$ such that
the following holds for all $n>n_{0}$. Let $\alpha\in(0,1-\frac{\log\log
n}{\log n})$ and denote $\ell=\lceil\alpha n^{\alpha}\rceil$. Then there
exists a permutation $\sigma\in S_{n}$ with $\ell$ cycles, such that

$\left|\frac{\chi(\sigma)}{\chi(1)}\right|\geqslant\chi(1)^{\alpha-\varepsilon-1}.$

for every $d<\min(\frac{\ell}{200},cn^{\varepsilon})$ and every irreducible
character $\chi=\chi_{\lambda}$ with $\lambda_{1}=n-d$.

The notion of level of a character will play an important role in our paper.
Let $\lambda=(\lambda_{1},\lambda_{2},\cdots,\lambda_{\ell})\vdash n$ be a
partition of $n$. We make use of the convention that
$\lambda_{1}\geqslant\ldots\geqslant\lambda_{\ell}$ and we denote by
$\lambda^{\prime}$ the partition conjugate to $\lambda$ obtained by flipping
the corresponding Young diagram. The _level_ of a character $\chi_{\lambda}$
of $S_{n}$ is the minimum between $n-\lambda_{1}$ and
$n-\lambda_{1}^{\prime}$.

We derive Theorem 1.7 from Theorem 1.9 below, which shows that the character
ratios of level $d$ representations decay essentially like $n^{d(\alpha-1)}.$
This fits a philosophy of Gurevich and Howe [12], which states that the main
property of a character that governs the order of magnitude of its ratios is
its level. Theorem 1.9 also demonstrates the tight connection between the
theory of Boolean functions and the character theory of the symmetric group.
Arguably, the theory of the Boolean cube is centered around the so called
_noise operator_. One of the key properties of the noise operator is the fact
that its eigenvalues decay exponentially with respect to a certain parameter
called degree, which is analogous to the notion of level for characters. The
analogy between these notions was first observed by Ellis, Friedgut, and
Pilpel [5] and many works in the theory of Boolean function are devoted to
studying the analogy between Boolean functions and the harmonic analysis of
the symmetric group (see e.g. [2, 4]). Given a permutation $\sigma\in S_{n}$,
an analog to the noise operator on the Boolean cube is the operator
$T_{\sigma}$ corresponding to the simple random walk on the Cayley graph
$\mathrm{Cay}(A_{n},A)$, defined by

$f(\tau)\mapsto\mathbb{E}_{\pi\sim\sigma^{S_{n}}}[f(\pi\tau)].$

The operator $T_{\sigma}$ has the irreducible characters of $S_{n}$ as
eigenvectors, where each character $\chi$ corresponds to the eigenvalue
$\frac{\chi\left(\sigma\right)}{\chi(1)}.$ In this perspective, the following
theorem shows that for many permutations $\sigma$, $T_{\sigma}$ exhibits
exponential decay properties similar to the noise operator.

######  Theorem 1.9.

There exists an absolute constant $C>0,$ such that the following holds for all
$\alpha\in(0,1)$. Let $\sigma\in S_{n}$ be a permutation whose conjugacy class
has density $\geqslant n^{-2\alpha n^{\alpha}}$. Then for every character
$\chi$ of $S_{n}$ of level $d\leqslant\alpha n^{\alpha}\log n$ we have

$\left|\frac{\chi(\sigma)}{\chi(1)}\right|\leqslant
n^{d(\alpha-1)}\left(\frac{C\alpha\log n}{\log(\alpha n^{\alpha}\log n)-\log
d}\right)^{d}.$

It turns out that this bound is also very close to optimal:

######  Theorem 1.10.

There exists an absolute constant $c>0,$ such that for every $\alpha\in(0,1)$
there exists $n_{0}\in\mathbb{N}$ such that the following holds for every
$n\geqslant n_{0}$. There exists a permutation $\sigma\in S_{n}$ whose
conjugacy class has density $\geqslant n^{-2\alpha n^{\alpha}}$, such that for
every character $\chi$ of $S_{n}$ of level $d\leqslant 0.5\alpha n^{\alpha}$
we have

$\left|\frac{\chi(\sigma)}{\chi(1)}\right|\geqslant
n^{d(\alpha-1)}(c\alpha)^{d}.$

###  1.3 Computing the asymptotics of character norms

We now switch to a more analytic perspective, and study bounds on the
$L^{q}$-norms of the characters. We will mainly be interested in the linear
space of class functions, i.e., the functions that are constant on each
conjugacy class. The functions on the symmetric group $S_{n}$ are equipped
with the standard inner product

$\langle f,g\rangle=\mathbb{E}_{\sigma\sim
S_{n}}[f(\sigma)g(\sigma)]:=\frac{1}{n!}\sum_{\sigma\in
S_{n}}f(\sigma)g(\sigma),$

where the notation $\sigma\sim A$ denotes that $\sigma$ is chosen uniformly
out of $A$. We also use the $L^{p}$ norms

$\|f\|_{p}=\mathbb{E}^{1/p}[|f|^{p}].$

The irreducible characters of the symmetric group form an orthonormal basis
for the space of class functions with respect to the standard inner product.
The coefficients

$\hat{f}(\chi):=\langle f,\chi\rangle$

are known as the (nonabelian) _Fourier coefficients_ of $f$. Unlike the
abelian setting where the characters take values in the unit circle and their
$q$-norms are always 1, in the nonabelian setting estimating the $q$-norms of
the characters is highly non-trivial. On the other hand, it may reveal lots of
precious information about the character ratios, the conjugacy classes of the
group and its representations, as was demonstrated in the breakthrough result
of Guralnick, Larsen, and Tiep [11] for the case of groups of Lie type.
Therefore, consider the following problem.

######  Problem 1.11.

Given an irreducible character $\chi$ of the symmetric group and $q\geqslant
1$, find the best possible estimate on $\|\chi\|_{q}.$

When $q$ is an even integer, the $q$-norms of the characters have a simple
representation theoretic interpretation. The $q$-norm of the character
corresponding to a representation $V$ is the $q$th root of the multiplicity of
the trivial representation inside the representation $V^{\otimes q}$. We prove
the following upper bound on the $L^{q}$-norms of the characters.

######  Theorem 1.12.

There exists an absolute constant $C>0,$ such that the following holds. Let
$d$ be a positive integer, and let $q\geqslant 2$. Let $\chi$ be a character
of level $d.$ Then

$\|\chi\|_{q}\leqslant\left(\frac{Cq}{\log
q}\right)^{d}\left(\frac{d^{d}\chi(1)}{n^{d}}\right)^{1-2/q}.$

Note that when $q<2$, we always have $\|\chi\|_{q}\leqslant\|\chi\|_{2}=1$.

Theorem 1.12 is our main tool in this work, and it is applied in virtually all
our other results, including the character bounds of Theorems 1.7 and 1.9.

Our result is sharp up to the value of the implicit constant $C$ unless $d$ is
tremendously larger with respect to $q$, as implied in the following matching
lower bound.

######  Theorem 1.13.

There exists an absolute constant $c>0$, such that the following holds. Let
$q\geqslant 2$ and let $d<\min(e^{cq},\frac{n}{q+1})$ be an integer. Let
$\chi$ be a character of level $d$. Then

$\|\chi\|_{q}\geqslant\left(\frac{cq}{\log(qd)}\right)^{d}\left(\frac{d^{d}\chi(1)}{n^{d}}\right)^{1-2/q}.$

One of the common applications of upper bounds on the $q$-norms of random
variables $X$ is the following upper bounds on the probability that $X$ is
large:

$\Pr[|X|>t]<\frac{\mathbb{E}[|X|^{q}]}{t^{q}}.$

In the context of the symmetric group, this will allow us to deduce an upper
bound on $\chi(\sigma)$ for each permutation $\sigma$ that has few cycles (see
Theorem 1.7 below). This might seem surprising from a probabilistic point of
view, as the $q$-norm of a function $f$ typically does not provide tight upper
bounds for the value of $f(x)$ at a specific point $x$. The reason why we may
deduce good bounds in the symmetric group is based on two facts. Firstly, the
characters of the symmetric group are constant on each conjugacy class.
Secondly, the conjugacy classes of the symmetric group tend to be huge.
Therefore, a bound of the form $\Pr[\chi>t]\leqslant p(t,\chi)$ implies that
$|\chi(\sigma)|\leqslant t$ whenever the conjugacy class of $\sigma$ has more
than $p(t,\chi)\cdot n!$ elements. This simple idea will play a central role
in the proof of Theorem 1.7.

#### The special case $d=1$

To get a better intuition for our bound one may plug in the partition
$\lambda=(n-1,1)$ and the character $\chi_{\lambda}.$ This character has level
$1$ and $\chi(1)=n-1.$ Our result therefore yields

$\|\chi\|_{q}=\Theta\left(\frac{q}{\log q}\right).$

The value of $\chi$ on a permutation $\sigma$ is the number of fixed points of
$\sigma$ subtracted by one. Therefore, our bound corresponds to the fact that
the number of fixed points of a random permutation is well approximated by a
Poisson-distributed variable $X\sim\text{Pois}(1)$ with a mean of $1$ (as
shown by Montmort in 1708). Indeed, the Poisson distribution is known to
satisfy $\|X\|_{q}=\Theta(\frac{q}{\log q})$ for $q\geqslant 2$.

###  1.4 Methods: Globalness and hypercontractivity

Our approach to obtaining character bounds is to transcend the realms of class
functions and view the low level characters merely as special cases of low
degree functions on the symmetric group. The functions on the symmetric group
of the form $\sigma\mapsto 1_{\sigma(i)=j}$ are known as the _dictators_ and
are denoted by $x_{i\to j}$. The _degree_ of a function $f$ on the symmetric
group is the minimal $d,$ such that there exists a multivariate polynomial $P$
of degree $d$ in $n^{2}$ variables indexed by
$\\{(i,j)\\}_{i,j\in\\{1,\dots,n\\}}$, such that $f(\sigma)=P(x_{i\to
j}(\sigma))$ for all $\sigma$. For example the number of fixed points is a
function of degree $1$ and the number of 2-cycles can be easily seen to be of
degree $2$. It turns out that up to multiplication by sign, level $d$
characters of the symmetric group are functions of degree $d$ (See Ellis,
Friedgut, and Pilpel [5, Theorem 7]).

#### Hypercontractivity for global functions

The tool known as ‘hypercontractivity for global functions’ was recently
developed by Keevash, Long, Lifshitz, and Minzer [15], who were inspired by
the work of Khot, Minzer, and Safra [17]. They proved a hypercontractive
inequality and used it to show that low degree functions over independent
random variables have small $q$-norms, provided that they satisfy a certain
requirement known as globalness. Filmus, Kindler, Lifshitz, and Minzer [8]
were then able to obtain somewhat similar hypercontractivity for global
functions in the symmetric group, where polynomials in the dictators replace
the roles of polynomials in independent random variables. The lack of
independence makes the problem significantly harder in the symmetric group.
Recently, Keevash and Lifshitz [14], building on the work of Keller, Lifshitz,
and Marcus [16], obtained a sharp hypercontractivity theorem for global
functions on the symmetric group. This allowed them to provide an upper bound
on the $q$-norms of low degree functions in terms of an analogue notion of
globalness, which we shall now describe.

#### Globalness in the symmetric group

Let $m\leqslant n$ and let $I,J$ be $m$-tuples each having distinct
coordinates. We write $U_{I\to J}$ for the set of permutations sending the
elements of $I$ to the elements of $J$ in the same order. We denote the
restriction of $f$ to $U_{I\to J}$ as $f_{I\to J}$. When we write $\|f_{I\to
J}\|_{2}$, we are referring to the 2-norm within the set $U_{I\to J}$, i.e.,

$\|f_{I\to J}\|_{2}^{2}=\frac{1}{(n-m)!}\sum_{\sigma\in U_{I\to
J}}f(\sigma)^{2}.$

We say that a function $f$ is $(r,\gamma)$-_global_ if for all $m$ and all
pairs of $m$-tuples of distinct coordinates $I,J$ we have $\|f_{I\to
J}\|_{2}\leqslant r^{m}\gamma$.

The main ingredient in our proof for the bound on character norms (Theorem
1.12) is the following proposition, which may also be of independent interest.

######  Proposition 1.14.

There exists an absolute constant $C>0$ such that the following holds. Let $d$
be a positive integer and let $\chi$ be a character of level $d$. Set
$\gamma=\left(\frac{Cd}{n}\right)^{d}\chi(1)$. Then $\chi$ is
$(2,\gamma)$-global.

Before moving on to applications, we would like to express the hope that the
theory of degrees, globalness, and hypercontractivity, is generalizable to
various other transitive permutation groups. Some evidence for the generality
of the theory can be derived from the work of Ellis, Kindler, Lifshitz, and
Minzer [6] who proved hypercontractivity for many compact Lie groups.
Additionally, Evra, Kindler, and Lifshitz [7] proved a hypercontractivity
theorem for general linear groups over finite fields. While their current
results may not yet yield new character bounds, we see promising potential in
the hypercontractive approach that could lead to successful outcomes in the
future.

### Structure of the paper

In Section 2, we present the applications of our upper bound on character
norms (Theorem 1.12) to Kronecker coefficients, upper bounds on Fourier
coefficients, and product mixing. Section 3 is devoted to proving Theorem
1.12. Section 4 establishes its sharpness by proving a matching lower bound
(Theorem 1.13). In Section 5 we apply Theorem 1.12 to quickly deduce upper
bounds for the Kronecker coefficients. In Section 6 we first upper bound
Fourier coefficients of class functions (Theorem 2.4), and then simplify it to
bound character ratios (Theorem 1.7). In Section 7 we deduce applications for
mixing times. Finally, in Section 8 we prove applications to product mixing of
normal sets.

### Acknowledgement

We would like to thank Gil Kalai for encouraging us to connect the theory of
hypercontractivity for global functions with representation theory and Peter
Sarnak for encouraging us to find connections to mixing times over the
symmetric group. We would also like to thank Yotam Shomroni, Shai Evra, Dor
Minzer, Guy Kindler, Ohad Sheinfeld, Doron Puder, Peter Keevash, Gady Kozma,
and Yuval Filmus for many helpful suggestions. Finally, N. L. would like to
thank the Simons Institute for the Theory of Computing for hosting him while
the research was conducted.

##  2 Other applications of Theorem 1.12

In this section we present various applications of the upper bound to
character norms introduced in Theorem 1.12. These applications include
Kronecker coefficients, upper bounds on Fourier coefficients, mixing times,
and product mixing of normal sets.

###  2.1 Kronecker coefficients

The most obvious application of our work is related to the study of the
Kronecker coefficients. Given a group, the first goal of representation theory
is to determine the set of irreducible representations for the group and to
compute their dimension. Having done that, the remaining task is to understand
how naturally occurring representations decompose into irreducible components.
One such representation is the tensor product of two irreducible
representations. For compact groups, such as the unitary group, the task is
well-established due to the Littlewood-Richardson rule. However, in the
symmetric group this problem is much more difficult. In fact, from a
computational standpoint it is impossible to solve in general.

Given $\lambda,\mu,\nu\vdash n$, the multiplicity of the Specht module
$V_{\nu}$ inside the tensor product $V_{\lambda}\otimes V_{\mu}$ is known as
the _Kronecker coefficient_ corresponding to $\lambda,\mu$ and $\nu$. It is
given by the character formula:

$g(\lambda,\mu,\nu):=\mathbb{E}[\chi_{\lambda}\chi_{\mu}\chi_{\nu}]=\langle\chi_{\lambda}\chi_{\mu},\chi_{\nu}\rangle.$

The Kronecker coefficients are known to be $\\#\text{P}$-hard to compute, and
NP hard to decide whether they are zero or not. Therefore the main direction
of research concerning the Kronecker coefficients is computing them in the
special cases where it is possible or deriving general bounds.

The reader is referred to Panova’s survey [23] for additional properties and
known estimates of Kronecker coefficients, as well as her complementary survey
[24] which explores the remarkable connections between Kronecker coefficients
and computational complexity.

We may apply the upper bound

$\mathbb{E}[fgh]\leqslant\|f\|_{3}\|g\|_{3}\|h\|_{3}$

implied by the generalized Hölder’s inequality to obtain the following
immediate corollary of Theorem 1.12.

######  Corollary 2.1.

There exists an absolute constant $C>0,$ such that the following holds. Let
$d_{1},d_{2}$ and $d_{3}$ be positive integers. Let $\lambda,\mu$ and $\nu$ be
partitions of levels $d_{1},d_{2}$ and $d_{3}$ respectively. Then the
Kronecker coefficients satisfy

$g(\lambda,\mu,\nu)\leqslant\left(\frac{C^{d_{1}+d_{2}+d_{3}}d_{1}^{d_{1}}d_{2}^{d_{2}}d_{3}^{d_{3}}}{n^{d_{1}+d_{2}+d_{3}}}\right)^{1/3}\chi^{1/3}_{\lambda}(1)\chi^{1/3}_{\mu}(1)\chi^{1/3}_{\nu}(1).$

Similar non symmetric variants might be desirable when the dimensions of the
representations are far apart. Such variants also follow easily from Theorem
1.12 by choosing different parameters in the generalized Hölder inequality.
Using $\mathbb{E}[fgh]\leqslant\|f\|_{4}\|g\|_{4}\|h\|_{2}$ we obtain the
following.

######  Corollary 2.2.

There exists an absolute constant $C>0,$ such that the following holds. Let
$d_{1}$ and $d_{2}$ be positive integers. Let $\lambda$ and $\mu$ be
partitions of levels $d_{1}$ and $d_{2}$ respectively, and let $\nu$ be a
partition of an arbitrary level. Then

$g(\lambda,\mu,\nu)\leqslant\left(\frac{C^{d_{1}+d_{2}}d_{1}^{d_{1}}d_{2}^{d_{2}}}{n^{d_{1}+d_{2}}}\right)^{1/2}\chi^{1/2}_{\lambda}(1)\chi^{1/2}_{\mu}(1).$

Finally, we can be slightly trickier and obtain the following bound when only
$\lambda$ is assumed to have a low level.

######  Corollary 2.3.

There exists an absolute constant $C>0,$ such that the following holds. Let
$d$ be an integer, let $\lambda$ be a partition of level $d$, let $\mu,\nu$ be
partitions, and let $q=\frac{\log(\chi_{\mu}(1)\chi_{\nu}(1))}{d}.$ If
$q\geqslant 2$, then

$g(\lambda,\mu,\nu)\leqslant\left(\frac{Cq}{\log
q}\right)^{d}\left(\frac{\chi_{\lambda}(1)d^{d}}{n^{d}}\right)^{1-2/q}.$

###  2.2 Upper bounds on Fourier coefficients

In the Fourier analysis of finite abelian groups, a standard measure of
pseudorandomness for a set $A$ is the smallness of the Fourier coefficients of
the indicator function $1_{A}$. When these coefficients are small, the
behavior of the set $A$ resembles that of a random set in numerous aspects. In
the nonabelian setting, a similar phenomenon arises with conjugacy classes:
the pseudorandomness of the conjugacy class $\sigma^{S_{n}}$ corresponds to
the smallness of the Fourier coefficients of $1_{\sigma^{S_{n}}}$. It turns
out that all the large conjugacy classes of $A_{n}$ have small Fourier
coefficients, leading to desirable pseudorandomness properties. It follows
from the following bound on the Fourier coefficients of class functions $f$
with a small $\frac{\|f\|_{2}}{\|f\|_{1}}$.

######  Theorem 2.4.

There exists an absolute constant $C>0$, such that the following holds. Let
$f$ be a class function with $\frac{\|f\|_{2}}{\|f\|_{1}}\leqslant M$ for some
bound $M$, and let $\chi$ be a character of $S_{n}$ of level
$d\leqslant\log(M)$. Then

$|\langle f,\chi\rangle|\leqslant\chi(1)\|f\|_{1}\left(\frac{C\log
M}{n\log\left(\frac{\log M}{d}\right)}\right)^{d}.$

This result extends to $A_{n}$, see Theorem 6.6 below. The proofs for our
bounds on character ratios (presented in Theorems 1.7 and 1.9) are based on
Theorem 2.4, by considering the class function $1_{\sigma^{S_{n}}}$ in order
to bound $\chi(\sigma)$.

###  2.3 Product mixing

Another application of our result concerns product mixing. We say that a group
$G$ is an $\varepsilon$-_mixer_ if for all sets $A,B$ and $C$ of density
$\geqslant\varepsilon$ and independently chosen $a\sim A,b\sim B$ the
probability that $ab\in C$ is within a factor of $1.01$ of $\frac{|C|}{|G|}$.
Gowers [10] showed that there exists an absolute constant $C$, such that
$A_{n}$ is a $Cn^{-1/3}$-mixer. We say that $A_{n}$ is _normally an
$\varepsilon$-mixer_ if the same holds for all normal sets $A,B,C$. We show
that for normal sets Gowers’ result can be improved exponentially.

######  Theorem 2.5.

There exists an absolute constant $c>0$, such that $A_{n}$ is normally an
$n^{-cn^{1/3}}$-mixer.

We also demonstrate that our result is best possible, in the sense that there
exists an absolute constant $C$ such that $A_{n}$ is not normally an
$n^{-Cn^{1/3}}$-mixer. We show this by setting $m=\lfloor 10n^{1/3}\rfloor$and
then taking $A=B=C$ to be the conjugacy class of all permutations with $m$
fixed points and one $(n-m)$-cycle (see Proposition 8.1 below).

Combining Theorem 2.5 with an observation of Nikolov and Pyber [22], we obtain
the following.

######  Corollary 2.6.

There exists an absolute constant $c>0$, such that the following holds.
Suppose that $A\subseteq A_{n}$ is a normal set of density $\geqslant
n^{-cn^{1/3}},$ then $A^{3}=A_{n}$.

Larsen and Tiep [20] showed that for each $\varepsilon>0$ there exists
$n_{0}$, such that if $n>n_{0}$ and $A$ is a normal subset of $A_{n}$ with
$A=A^{-1}$ and density $\geqslant e^{-n^{1/4-\varepsilon}}$, then
$A^{2}=A_{n}.$ We conjecture that the same holds for sets $A$ of density at
least $n^{-cn}$.

Larsen and Shalev[19] settled the case when $2$ is replaced by $4$ in a very
strong sense. They showed that for every conjugacy class $A$ with at most
$n/5$ fixed points we have $A^{4}=A_{n}$. Garonzi and Maróti [9] showed (in an
equivalent formulation) that for each $\varepsilon>0$ there exists $n_{0}$,
such that if $n>n_{0}$ and $A,B,C,D$ are normal subsets of $A_{n}$ of density
$\geqslant|A_{n}|^{1/2+\varepsilon}$, then $ABCD=A_{n}$. They conjectured that
there exists $c>0$, such that if $A,B,C$ are normal subsets of $A_{n}$ of
density $\geqslant n^{-cn},$ then $ABC=A_{n}.$ This problem remains open.

##  3 Dimension and globalness of low level characters

In this section we first present well known bounds for the dimensions of
irreducible characters of $S_{n}$. We then prove Proposition 1.14, namely,
that irreducible characters are global. We combine it with a result of Keevash
and Lifshitz [14] (Theorem 3.5 below) to finish the proof of Theorem 1.12 and
bound character norms. Finally, we explain how to adapt our result for the
alternating group.

Throughout the paper we assume some familiarity with standard notions and
results from the representation theory of the symmetric group, such as Young’s
branching rule, standard Young tableaux and the Murnaghan–Nakayama rule. The
reader is referred to [26] for more information. In this section we show that
the properties of characters with a long first row or column can be computed
in terms of the properties of the smaller character obtained by deleting said
row or column.

Let $d$ be a positive integer. We say that $\tilde{\lambda}$ is the _partition
of $d$ corresponding to_ $\lambda$ if $\tilde{\lambda}$ is obtained from
$\lambda$ by deleting $\lambda_{1}$ in the case where $\lambda_{1}=n-d$ and by
deleting $\lambda_{1}^{\prime}$ from $\lambda^{\prime}$ in the case where
$\lambda_{1}^{\prime}=n-d$. Given a character $\chi$ of a group, we denote by
$\dim(\chi)$ the dimension of the corresponding representation. We also use
the standard notation $[n]:=\\{1,\dots,n\\}$ where $n$ is a positive integer.

###  3.1 Dimensions of low level characters

We make use of the following standard lower bound on the dimensions of
characters and we include its proof for completeness.

######  Lemma 3.1.

Let $d$ be a positive integer and let $\lambda\vdash n$ of level $d$. Denote
$\chi:=\chi_{\lambda}$ and $\tilde{\chi}:=\chi_{\tilde{\lambda}}$. Then
$\dim(\chi)\geqslant\binom{n-d}{d}\dim(\tilde{\chi})$.

###### Proof.

If $n<2d$ then the statement follows immediately, so we may assume that
$n\geqslant 2d$. Since the character $\chi_{\lambda}$ and the character
$\chi_{\lambda^{\prime}}=\chi_{\lambda}\otimes\text{sign}$ obtained by
transposing the corresponding Young diagram have the same dimension, we can
assume without loss of generality that $\lambda_{1}=n-d$. The dimension of
$\chi$ is the number of ways to fill the Young diagram of shape $\lambda$ with
the labels $1,\dots,n$, each appearing once, such that the rows and columns
are increasing. Some of these labelings are obtained as follows: First, we put
the labels $1,\ldots,d$ on the first $d$ boxes of the first row. Once we do
that, the set of labels appearing below the first row can be any
$S\subseteq[n]\setminus[d]$ with $|S|=d$. Moreover, for each set $S$, every
valid placing of its labels below the first row corresponds to a unique valid
placing of the labels of $[d]$ in the Young diagram of shape
$\tilde{\lambda}$, and the number of these placings is $\dim(\tilde{\chi})$.
Therefore, we have at least $\binom{n-d}{d}\dim(\tilde{\chi})$ valid ways to
fill the Young diagram of shape $\lambda$. ∎

######  Lemma 3.2.

Let $d$ be an integer and let $\lambda\vdash n$ of level $d$. Denote
$\chi:=\chi_{\lambda}$ and $\tilde{\chi}:=\chi_{\tilde{\lambda}}$. Then

$\dim(\chi)\leqslant\binom{n}{d}\dim(\tilde{\chi}).$

###### Proof.

Again we may assume without loss of generality that $\lambda_{1}=n-d.$ Every
filling of the Young diagram of shape $\lambda$ with increasing rows and
columns is obtained through the following process: First, choose a set
$S\subseteq[n]$ with $|S|=d$. Next, place the labels of $[n]\setminus S$ in
the first row in increasing order. Then, place the labels of $S$ in the other
rows so that re-labeling $S$ with $1,\ldots,d$ results in a valid labeling of
the Young diagram of shape $\tilde{\lambda}$. The number of fillings obtained
by this process is exactly $\binom{n}{d}\dim(\tilde{\chi})$. Since every valid
filling can be constructed using this process, the number of valid fillings of
shape $\lambda$ is at most $\binom{n}{d}\dim(\tilde{\chi})$. ∎

Lemma 3.2 may be applied to derive another lower bound which does not involve
$\dim(\tilde{\chi})$.

######  Corollary 3.3.

Let $\chi$ be an irreducible character of $S_{n}$, and let us denote its level
by $d$. Then

$\dim(\chi)\leqslant\frac{n^{d}}{\sqrt{d!}}.$

###### Proof.

Denote by $\lambda\vdash n$ the partition associated with $\chi$. We may
assume, without loss of generality, that $\lambda_{1}=n-d$. By Lemma 3.2 we
obtain that

$\dim(\chi)\leqslant\binom{n}{d}\dim(\tilde{\chi})\leqslant\frac{n^{d}}{d!}\dim(\tilde{\chi}),$

where $\tilde{\chi}$ is the character associated with the partition obtained
by removing the first row of $\lambda$. Since $\tilde{\chi}$ is an irreducible
character of $S_{d}$, and the sum of squares of the dimensions of the
irreducible representations of $S_{d}$ is $d!$, we obtain the trivial bound
$\dim(\tilde{\chi})\leqslant\sqrt{d!}$. This completes the proof of the
corollary. ∎

The following useful bound can be deduced from [5, Claim 1, Claim 2 and
Theorem 19]:

######  Theorem 3.4.

There exists $n_{0}>0$, such that the following holds. Let $n>n_{0},$
$d\leqslant n/200$ and suppose that $\chi$ is a character of $S_{n}$ of level
at least $d$. Then $\dim(\chi)\geqslant\left(\frac{n}{ed}\right)^{d}$.

###  3.2 Globalness of low level characters

Recall the definition of degree and the notations $U_{I\to J}$ and $f_{I\to
J}$ from Section 1.4. As noted earlier, up to multiplication by sign, level
$d$ characters of the symmetric group are functions of degree $d$.

We say that a function $f\colon S_{n}\to\mathbb{R}$ is $(r,\gamma)$-global if

$\|f_{I\to J}\|_{2}\leqslant r^{|I|}\gamma$

for all $I,J$ of the same size.

Keevash and Lifshitz [14, Theorem 1.10] proved the following theorem.

######  Theorem 3.5.

There exists an absolute constant $c>0$, such that the following holds. There
exists a family of operators $\\{T_{\rho}\\}_{\rho\in(0,1)}$ on
$L^{2}(S_{n})$, each of which commutes with the action of $S_{n}$ from both
sides, such that if $f\in L^{2}(S_{n})$ is $(r,\gamma)$ global, $q\geqslant 2$
and $0<\rho\leqslant\frac{c\log q}{qr}$, then

$\|T_{\rho}f\|_{q}\leqslant\gamma^{\frac{q-2}{q}}\|f\|_{2}^{2/q}.$

Moreover, if $d<cn$ and $f$ is a function of degree $d$, then

$\langle T_{\rho}f,f\rangle\geqslant\left(c\rho\right)^{d}\|f\|_{2}^{2}.$

In order to apply this theorem, let us show that irreducible characters are
global.

######  Lemma 3.6.

Let $d$ be a positive integer and let $\lambda\vdash n$ of level $d$. Denote
$\chi:=\chi_{\lambda}$ and $\tilde{\chi}:=\chi_{\tilde{\lambda}}$.Then $\chi$
is $(2,\tilde{\chi}(1))$-global.

In the proof of Lemma 3.6, we will use the following result of Avni and
Glazer.

######  Lemma 3.7 ([1, Lemma 2.7]).

Let $G$ be a finite group, let $\chi$ be an irreducible character of $G$, and
let $H\leqslant G$ be a subgroup. Then, for every $g\in G$,

$\frac{1}{|H|}\sum_{h\in
H}\chi(gh)\leqslant\langle\chi|_{H},\chi_{\text{triv}}\rangle_{H},$

where $\chi_{\text{triv}}$ is the trivial character of $H$.

###### Proof of Lemma 3.6.

Given $m$ and two $m$-tuples $I,J$ each having distinct coordinates, we need
to prove that

$\|\chi_{I\to J}\|_{2}\leqslant 2^{|I|}\tilde{\chi}(1).$ (1)

Since characters are invariant under conjugation, we may assume without loss
of generality that $I=(1,\dots,m)$. The $m$-umvirate $U_{I\to I}$ is a
subgroup of $S_{n}$ isomorphic to $S_{n-m}$. It has $U_{I\to J}$ as its coset.
Choose an arbitrary permutation $g$ sending $I$ to $J$ and write $U_{I\to
J}=gU_{I\to I}$.

We have

$\|\chi_{I\to J}\|_{2}^{2}=\frac{1}{|U_{I\to J}|}\sum_{\sigma\in U_{I\to
J}}\chi^{2}(\sigma)=\frac{1}{(n-m)!}\sum_{\sigma\in U_{I\to
I}}\chi^{2}(g\sigma).$

Recall that the function $\chi^{2}$ is a character of the symmetric group as
$\chi_{\lambda}^{2}$ is the trace of the tensor product $V_{\lambda}\otimes
V_{\lambda}$. Decomposing $\chi^{2}$ into irreducible characters and writing
$\chi^{2}=\sum_{i}\chi_{i}$ we may apply Lemma 3.7 to each $\chi_{i}$ to
obtain that

$\frac{1}{(n-m)!}\sum_{\sigma\in U_{I\to
I}}\chi_{i}(g\sigma)\leqslant\frac{1}{(n-m)!}\sum_{\sigma\in U_{I\to
I}}\chi_{i}(\sigma).$

Summing over all $i$ we obtain that $\|\chi_{I\to
J}\|_{2}^{2}\leqslant\|\chi_{I\to I}\|_{2}^{2}$.

Next, let us bound the $L^{2}(U_{I\to I})$-norm of $\chi_{I\to I}$. Clearly,
it is equal to the $L^{2}(S_{n-m})$-norm of $\chi|_{S_{n-m}}$. We can
decompose the restriction of $\chi$ to $S_{n-m}$ as a linear combination of
characters and write $\chi|_{S_{n-m}}=\sum_{\mu}c_{\mu}\chi_{\mu}$, where the
sum goes over all $\mu\vdash(n-m)$, and obtain that

$\|\chi_{I\to
J}\|_{2}^{2}\leqslant\sum_{\mu}c_{\mu}^{2}\leqslant\left(\sum_{\mu}c_{\mu}\right)^{2},$

which implies that $\|\chi_{I\to J}\|_{2}\leqslant\sum_{\mu}c_{\mu}.$ We will
prove that $\sum_{\mu}c_{\mu}\leqslant 2^{m}\tilde{\chi}(1)$ and our lemma
will follow.

Recall Young’s branching rule: Let $\lambda\vdash n$ and $\mu\vdash(n-m)$. The
multiplicity of $\chi_{\mu}$ in the restriction of $\chi_{\lambda}$ to
$S_{n-m}$ is equal to the number of valid removal processes from $\lambda$ to
$\mu$, where a valid removal process is a way to remove $m$ cells from the
Young diagram of shape $\lambda$ such that the resulting shape after removing
the cells is $\mu$, and any intermediate shapes that are created during the
removal process are also valid Young diagrams.

To bound the sum of the multiplicities of all $\mu$, we count all the valid
ways to remove $m$ cell from $\lambda$. We call the $i$th cell that we remove
the $i$th _step_. We begin counting the ways by separating them according to
the set of steps in which we remove a cell from the first row of $\lambda$.
There are at most $2^{m}$ such possible sets. Next, we fix the set $S$ of such
steps. All the other steps correspond to a removal process that removes
$m-|S|$ boxes from $\tilde{\lambda}$. The number of such valid ways of
removing $m-|S|$ boxes is upper bounded by the number of ways to remove all
the boxes of $\tilde{\lambda}$ while leaving a valid Young diagram at each
step. This is exactly the dimension of $\tilde{\chi}$. We therefore obtain
that $\sum_{\mu}c_{\mu}\leqslant 2^{m}\tilde{\chi}(1)$, as required.∎

###### Proof of Proposition 1.14.

If $d\geqslant\frac{n}{10}$, then we can take $C\geqslant 10$ and obtain that

$\gamma=\left(\frac{Cd}{n}\right)^{d}\chi(1)\geqslant\chi(1)=\|\chi\|_{\infty}.$

Therefore, We may use the fact that every function $f$ is
$(\|f\|_{\infty},2)$-global to complete the proof.

Next, suppose $d<\frac{n}{10}$. Proposition 1.14 follows as a direct
consequence of Lemma 3.1 together with Lemma 3.6. ∎

We may now apply the globalness of characters to upper bound their $q$-norms.

###### Proof of Theorem 1.12.

The statement obviously holds for $q=2$, so we may assume that $q>2$. Let
$c>0$ be the constant from Theorem 3.5. By increasing $C$ if necessary, we may
assume that $C^{\frac{1}{1-2/q}}>\frac{1}{c}$. If $d\geqslant cn$ then the
theorem follows from the ‘trivial’ upper bound

$\|\chi\|_{q}^{q}\leqslant\chi(1)^{q-2}\|\chi\|_{2}^{2}$

and the fact that we have
$\frac{C^{\frac{1}{1-2/q}}d}{n}>\frac{d}{cn}\geqslant 1$ and $\frac{q}{\log
q}>1$.

Next, let us assume that $d<cn$. For an arbitrary finite group $G$, it is
known that if an operator $T$ on $L^{2}(G)$ commutes with the action of $G$
from both sides, then the irreducible characters of $G$ are eigenvectors of
$T$. We therefore obtain that $T_{\rho}\chi=\langle
T_{\rho}\chi,\chi\rangle\chi$ for each irreducible character $\chi.$ Let
$\chi$ be a character of the symmetric group of level $d$. Our goal is to
upper bound $\|\chi\|_{q}.$ As a character and its conjugate differ only by
multiplication by the sign function, which does not affect the norm, we may
assume without loss of generality that $\lambda_{1}=n-d.$ By [5, Theorem 7],
the characters with $\lambda_{1}=n-d$ are polynomials of degree $d$ in the
dictators. By Proposition 1.14, $\chi$ is $(2,\gamma)$-global where
$\gamma=\left(\frac{C^{\prime}d}{n}\right)^{d}\chi(1)$ for some
$C^{\prime}>0$. By Theorem 3.5 we may use the fact that $\chi$ is a polynomial
of degree $d$ to obtain that there exists an absolute constant $C$, such that
$\langle T_{\rho}\chi,\chi\rangle\geqslant\left(\frac{\rho}{C}\right)^{d}$,
and therefore

$\left(\frac{\rho}{C}\right)^{d}\|\chi\|_{q}\leqslant\|T_{\rho}\chi\|_{q}\leqslant\gamma^{1-2/q}.$

The theorem now follows by picking $\rho=\frac{c\log q}{2q}$ and rearranging.
∎

###  3.3 Adaptation to $A_{n}$

Recall that the characters of $A_{n}$ are all obtained from characters of
$S_{n}$ by first restricting them to $A_{n}$ and then decomposing them into
irreducible characters when necessary. Let us denote by $\lambda^{\prime}$ the
partition conjugate to $\lambda$ and denote by $\chi^{R}$ the restriction of a
character $\chi$ from $S_{n}$ to $A_{n}$. We recall that when
$\lambda\neq\lambda^{\prime}$ the restricted character $\chi_{\lambda}^{R}$ is
irreducible. When $\lambda=\lambda^{\prime}$, the character
$\chi_{\lambda}^{R}$ is the sum of two irreducible characters, which we denote
by $\chi_{\lambda,1}$ and $\chi_{\lambda,2}$. The characters
$\chi_{\lambda,1}$ and $\chi_{\lambda,2}$ have equal dimensions and therefore

$\chi_{\lambda,1}(1)=\chi_{\lambda,2}(1)=\frac{\chi_{\lambda}(1)}{2}.$

In either case, we set the _level_ of the characters in the decomposition of
$\chi_{\lambda}^{R}$ to be the level of $\chi_{\lambda}$. We also say that the
characters in the decomposition of $\chi_{\lambda}^{R}$ are _characters
corresponding_ to $\lambda$. The following versions of Theorem 3.4 and
Corollary 3.3 follow immediately from the above discussion.

######  Lemma 3.8.

There exists $n_{0}>0$, such that the following holds. Let $n>n_{0},$
$d\leqslant n/200$ and suppose that $\chi$ is a character of $A_{n}$ of level
at least $d$. Then $\chi(1)\geqslant\frac{1}{2}\left(\frac{n}{ed}\right)^{d}$.

######  Corollary 3.9.

Let $d$ be an integer and let $\chi$ be a character of $A_{n}$ of level $d$.
Then

$\dim(\chi)\leqslant\frac{n^{d}}{\sqrt{d!}}.$

Finally, we give a version of Theorem 1.12 for $A_{n}$.

######  Corollary 3.10.

There exists an absolute constant $C>0,$ such that the following holds. Let
$d$ be a positive integer, and let $q\geqslant 2$. Let $\chi$ be a character
of $A_{n}$ of level $d.$ Then

$\|\chi\|_{q}\leqslant\left(\frac{Cq}{\log
q}\right)^{d}\left(\frac{d^{d}\chi(1)}{n^{d}}\right)^{1-2/q}.$

###### Proof.

Denote $\lambda^{\prime}$ for the transpose of $\lambda$. We first consider
characters of $A_{n}$ of type $\lambda$, where $\lambda\neq\lambda^{\prime}$.
For such $\chi$ we view $\chi^{R}$ also as a function on $S_{n}$ by extending
it by 0 outside of $S_{n}.$ We now have

$\|\chi^{R}\|_{L^{q}(A_{n})}^{q}=2\|\chi^{R}\|_{L^{q}(S_{n})}^{q}\leqslant
2\|\chi\|_{q}^{q}.$

We may now apply Theorem 1.12 to complete the proof of the case where
$\lambda\neq\lambda^{\prime}$. Note that we ignore the factor of $2$ since $C$
can be replaced by $2C$.

Consider now the case where $\lambda=\lambda^{\prime}$. Here the level of
characters of type $\lambda$ is at least $\frac{n-1}{2}$, and therefore the
theorem is trivially derived from the upper bound

$\|\chi\|_{q}^{q}\leqslant\|\chi\|_{2}^{2}\|\chi\|_{\infty}^{q-2}=\chi(1)^{q-2}.$

∎

##  4 Matching Lower bounds

In this section, we prove Theorems 1.8, 1.9 and 1.13, thereby establishing the
sharpness of Theorems 1.7, 1.10 and 1.12, respectively. First, let us prove a
simple consequence of the Murnaghan–Nakayama rule:

######  Lemma 4.1.

Let $\lambda\vdash n$ be a partition with $\lambda_{1}=n-d$, and let
$\ell\geqslant d+\lambda_{2}$. Let
$\mu=(\lambda_{1}-n+\ell,\lambda_{2},\ldots,\lambda_{r})$ be the partition
obtained from $\lambda$ by removing $n-\ell$ boxes from its first row. Let
$\sigma\in S_{n}$ be a permutation with a cycle structure
$1^{\ell}\alpha_{1}\cdots\alpha_{k}$ with $\alpha_{i}>d$. That is, $\sigma$
has $\ell$ fixed points, and the rest of the cycles of $\sigma$ have length at
least $d+1$. Then we have $\chi_{\lambda}(\sigma)=\chi_{\mu}(1)$.

###### Proof.

Recall the Murnaghan–Nakayama rule: Let $\tau\in S_{n-\alpha_{k}}$ be a
permutation with a cycle structure $1^{\ell}\alpha_{1}\cdots\alpha_{k-1}$.
Then we have

$\chi_{\lambda}(\sigma)=\sum_{\nu}(-1)^{\operatorname{ht}(\nu)}\chi_{\lambda\setminus\nu}(\tau),$

where the sum is over every rim hook (i.e., a connected part of the rim which
can be removed to leave a proper tableau) $\nu$ of length $\alpha_{k}$ in a
$\lambda$-tableau, $\lambda\setminus\nu$ is the tableau obtained by removing
the cells of $\nu$ from $\lambda$, and $\operatorname{ht}(\nu)=(\text{the
number of rows of $\nu$})-1$.

Since $\lambda_{1}=n-d$ and $\alpha_{k}>d$, every rim hook of length
$\alpha_{k}$ must contain at least one cell of the first row. Assume, by
contradiction, that a rim hook $\nu$ contains cells from both the first and
the second rows. This implies that the length of $\nu$ is at least
$\lambda_{1}-\lambda_{2}+1$. Therefore,
$\alpha_{k}\geqslant\lambda_{1}-\lambda_{2}+1>n-d-\lambda_{2}$. However,
$\alpha_{k}\leqslant n-\ell$ and $\ell\geqslant d+\lambda_{2}$, leading to a
contradiction.

Thus, there exists a unique rim hook of length $\alpha_{k}$ in a
$\lambda$-tableau, contained within the first row of $\lambda$. Consequently,
$\chi_{\lambda}(\sigma)=\chi_{\bar{\lambda}}(\tau)$, where
$\bar{\lambda}=(\lambda_{1}-\alpha_{k},\lambda_{2},\ldots,\lambda_{r})$. The
statement follows by induction on $k$. ∎

###  4.1 Proof of Theorem 1.8

###### .

Let $0<\varepsilon<1$, let $n_{0}\in\mathbb{N}$ and $c>0$ to be chosen later,
and let $n>n_{0}$. Let $\alpha\in(0,1-\frac{\log\log n}{\log n})$ and denote
$\ell=\lceil\alpha n^{\alpha}\rceil$. Denote $\ell^{\prime}=\ell-1$, and let
$\sigma\in S_{n}$ be a permutation with a cycle structure
$1^{\ell^{\prime}}(n-\ell^{\prime})$. Let
$d<\min(\frac{\ell}{200},cn^{\varepsilon})$ and let $\chi=\chi_{\lambda}$ be a
character with $\lambda_{1}=n-d$. We aim to prove

$\left|\frac{\chi(\sigma)}{\chi(1)}\right|\geqslant\chi(1)^{\alpha-\varepsilon-1}.$

Since $\alpha<1-\frac{\log\log n}{\log n}$, we have
$\ell<n^{\alpha}+1<\frac{n}{\log n}+1<\frac{n}{3}$ for large enough $n$.
Therefore we obtain that $n-\ell^{\prime}>\ell>200d>d$. Moreover, we have
$\ell^{\prime}\geqslant 200d>d+\lambda_{2}$. Therefore, we may apply Lemma 4.1
and obtain that $\chi(\sigma)=\chi_{\mu}(1)$, where $\mu\vdash\ell^{\prime}$
is the partition obtained from $\lambda$ by removing $n-\ell^{\prime}$ boxes
from its first row. We conclude that it suffices to show that

$\chi_{\mu}(1)\geqslant\chi(1)^{\alpha-\varepsilon}.$

Since the statement clearly holds for $\alpha\leqslant\varepsilon$, we may
assume that $\alpha>\varepsilon$. On one hand, by Corollary 3.3, we have

$\chi(1)\leqslant\frac{n^{d}}{\sqrt{d!}}\leqslant\left(\frac{n\sqrt{e}}{\sqrt{d}}\right)^{d}.$

One the other hand, we have $d<\frac{\ell}{200}$, implying that
$d\leqslant\frac{\ell^{\prime}}{200}$. In addition, since
$d=\ell^{\prime}-\mu_{1}$ and $d\leqslant\frac{\ell^{\prime}}{200}$, we deduce
that the level of $\chi_{\mu}$ is $d$. Moreover, since $\ell>\varepsilon
n^{\varepsilon}$, we may assume that $\ell^{\prime}=\ell-1$ is large enough by
increasing $n_{0}$ if necessary, so we may apply Theorem 3.4 and deduce that

$\chi_{\mu}(1)\geqslant\left(\frac{\ell^{\prime}}{ed}\right)^{d}.$

As we aim to prove that $\chi_{\mu}(1)\geqslant\chi(1)^{\alpha-\varepsilon}$,
let us bound
$\left(\frac{\chi_{\mu}(1)}{\chi(1)^{\alpha-\varepsilon}}\right)^{1/d}$:

$\left(\frac{\chi_{\mu}(1)}{\chi(1)^{\alpha-\varepsilon}}\right)^{1/d}\geqslant
d^{0.5(\alpha-\varepsilon)-1}e^{-0.5(\alpha-\varepsilon)-1}\frac{\ell^{\prime}}{n^{\alpha-\varepsilon}}\geqslant
e^{-2}\frac{n^{\varepsilon}}{d}\cdot\frac{\ell^{\prime}}{n^{\alpha}}.$

Notably, we have $\frac{n^{\varepsilon}}{d}>c^{-1}$. Moreover, we have
$\frac{\ell}{n^{\alpha}}\geqslant\alpha>\varepsilon$, implying that
$\frac{\ell^{\prime}}{n^{\alpha}}>\varepsilon-n^{-\varepsilon}$. For large
enough $n$, we obtain
$\frac{\ell^{\prime}}{n^{\alpha}}>\frac{\varepsilon}{2}$. Therefore we obtain

$\left(\frac{\chi_{\mu}(1)}{\chi(1)^{\alpha-\varepsilon}}\right)^{1/d}\geqslant
0.5e^{-2}c^{-1}\varepsilon=1$

for $c=0.5e^{-2}\varepsilon$, as required. ∎

###  4.2 Proof of Theorem 1.10

###### .

Let $c>0$ to be chosen later, let $\alpha\in(0,1)$, and let $n\in\mathbb{N}$
be a sufficiently large integer. We denote $\ell=\lceil\alpha
n^{\alpha}\rceil$, and pick a permutation $\sigma\in S_{n}$ to be a
permutation with a cycle structure $1^{\ell}(n-\ell)$. Notably, the size of
the centralizer of $\sigma$ is

$\ell!\cdot(n-\ell)\leqslant\ell^{\ell}\cdot n\leqslant n^{\alpha
n^{\alpha}+2}\leqslant n^{2\alpha n^{\alpha}}$

for sufficiently large $n$. By orbit-stabilizer theorem, we obtain that the
density of the conjugacy class of $\sigma$ is at least $n^{-2\alpha
n^{\alpha}}$.

Let $\chi$ be a character of level $d\leqslant 0.5\alpha n^{\alpha}$, and
denote by $\lambda\vdash n$ the corresponding partition.Let us bound its
character ratios. Clearly, $d\leqslant\ell/2$. Moreover, from
$\ell=\lceil\alpha n^{\alpha}\rceil$ and $\alpha<1$ we obtain that $\ell<n/2$
for sufficiently large $n$, implying that $n-\ell>\ell\geqslant d$. Therefore,
we may apply Lemma 4.1 and obtain $\chi(\sigma)=\chi_{\mu}(1)$, where $\mu$ is
the partition obtained from $\lambda$ by removing $n-\ell$ boxes from its
first row.

By Lemmas 3.1 and 3.2 we have

$\chi(\sigma)=\chi_{\mu}(1)\geqslant\binom{\ell-d}{d}\chi_{\tilde{\lambda}}(1)\geqslant\frac{\binom{\ell-d}{d}}{\binom{n}{d}}\chi(1)\geqslant\left(\frac{c\ell}{n}\right)^{d}\chi(1)$

for an absolute constant $c$. Therefore, we obtain

$\left|\frac{\chi(\sigma)}{\chi(1)}\right|\geqslant\left(\frac{c\ell}{n}\right)^{d}\geqslant\left(\frac{c\alpha
n^{\alpha}}{n}\right)^{d}=n^{d(\alpha-1)}\left(c\alpha\right)^{d}.$

∎

###  4.3 Proof of Theorem 1.13

First, we prove a probabilistic proposition that will be helpful later:

######  Proposition 4.2.

Let $d$ and let $r>d$. Let $F_{r,d}$ be the event that a random permutation
$\sigma\sim S_{r}$ has all its cycles of length $>d$. Then
$\Pr[F_{r,d}]\geqslant\frac{1}{10d}$.

###### Proof.

The distribution of the cycle decomposition of a random permutation in $S_{r}$
is identical to the distribution of a random sequence $(i_{1},i_{2},\dots)$
obtained by the following process: First choose a random $i_{1}\sim[r]$, then
repeat the process recursively with $r-i_{1}$ in place of $r$ to obtain
$(i_{2},\dots)$. This follows easily from the fact that the length of the
cycle of the element $r$ is uniform, and that when removing its cycle we get a
uniformly random permutation on the remaining elements. This yields the
recursive formula

$\Pr[F_{r,d}]=\frac{1}{r}+\sum_{i=d+1}^{r-d-1}\frac{1}{r}\Pr[F_{r-i,d}].$

We now show that $\Pr[F_{r,d}]\geqslant\frac{1}{10d}$ by induction on $r>d$
for a fixed $d$. For $d+1\leqslant r\leqslant 10d$ the claim is obvious, since
$\Pr[F_{r,d}]\geqslant\frac{1}{r}$ by the recursive formula. Let $r>10d$. We
may apply the induction hypothesis to obtain that

$\Pr[F_{r,d}]\geqslant\frac{1}{r}+\sum_{i=d+1}^{r-d-1}\frac{1}{10dr}=\frac{1}{r}+\frac{r-2d-1}{10dr}>\frac{1}{10d}.$

∎

###### Proof of Theorem 1.13.

Let $d<\min(e^{cq},\frac{n}{q+1})$ and let $\chi_{\lambda}$ be a character of
level $d$. As multiplication by sign does not affect the $q$-norm we may
assume without loss of generality that $\lambda_{1}=n-d$. Pick some positive
integer $\ell\geqslant 2d$ that will be determined later. Let $\sigma$ be a
permutation with $\ell$ fixed points such that rest of the cycles of $\sigma$
have length at least $d+1$. Let
$\mu=(\lambda_{1}-n+\ell,\lambda_{2},\ldots,\lambda_{r})$ be obtained from
$\lambda$ by removing $n-\ell$ boxes from its first row. As usual, let
$\tilde{\lambda}$ be obtained from $\lambda$ by deleting its first row. Since
$\lambda_{2}\leqslant d$, we may apply Lemma 4.1 and obtain
$\chi_{\lambda}(\sigma)=\chi_{\mu}(1)$. By Lemmas 3.1 and 3.2 we have

$\chi_{\mu}(1)\geqslant\binom{\ell-d}{d}\chi_{\tilde{\lambda}}(1)\geqslant\frac{\binom{\ell-d}{d}}{\binom{n}{d}}\chi_{\lambda}(1)\geqslant\left(\frac{c\ell}{n}\right)^{d}\chi_{\lambda}(1)$

for an absolute constant $c$. Let $E$ be the event that a random $\sigma\sim
S_{n}$ has $\ell$ fixed points and all other cycles of length $>d$. Then we
may obtain that

$\|\chi_{\lambda}\|_{q}^{q}\geqslant\Pr[E]\chi^{q}_{\mu}(1)\geqslant\Pr[E]\left(\frac{c\ell}{n}\right)^{dq}\chi^{q}_{\lambda}(1).$

Let $F_{r,d}$ be the event that a random permutation $\sigma\sim S_{r}$ has
all its cycles of length $>d$. Proposition 4.2 implies that whenever
$n-\ell>d$, we have $\Pr[F_{n-\ell,d}]\geqslant\frac{1}{10d}$. Therefore,

$\Pr[E]=\binom{n}{\ell}\frac{1}{n(n-1)\cdots(n-\ell+1)}\Pr[F_{n-\ell,d}]=\frac{1}{\ell!}\Pr[F_{n-\ell,d}]\geqslant\frac{1}{10d\ell!}\geqslant\frac{1}{(c\ell)^{\ell}d}$

for an absolute constant $c$.

Substituting $\ell=\frac{qd}{\log(qd)},$ while noting that $\ell\geqslant 2d$
and $n-\ell>d$ provided that $d<\min(e^{cq},\frac{n}{q+1})$, we obtain

$\|\chi_{\lambda}\|_{q}\geqslant\left(\frac{c^{2}qd}{\log(qd)}\right)^{d}\frac{\chi_{\lambda}(1)}{n^{d}}=\left(\frac{c^{2}q}{\log(qd)}\right)^{d}\frac{d^{d}\chi_{\lambda}(1)}{n^{d}}\geqslant\left(\frac{c^{\prime}q}{\log(qd)}\right)^{d}\left(\frac{d^{d}\chi_{\lambda}(1)}{n^{d}}\right)^{1-2/q},$

for an absolute constant $c^{\prime}$. The last inequality follows from the
fact that $\chi_{\lambda}(1)\geqslant\binom{n-d}{d},$ which yields
$\left(\left(\frac{d}{n}\right)^{d}\chi_{\lambda}(1)\right)^{2/q}\geqslant\left(\frac{1}{3}\right)^{d}$.
∎

##  5 Upper bounds on Kronecker coefficients

###### Proofs of Corollaries 2.1 ,2.2, and 2.3, .

The proofs of Corollaries 2.1 ,2.2, and 2.3 share a common framework, where we
make use of Theorem 1.12. By applying Theorem 1.12 in different ways, we can
establish the validity of each statement.

Corollary 2.1 follows directly from Theorem 1.12 by applying the generalized
Hölder inequality to obtain

$\mathbb{E}[\chi_{\lambda}\chi_{\mu}\chi_{\nu}]\leqslant\|\chi_{\lambda}\|_{3}\|\chi_{\mu}\|_{3}\|\chi_{\nu}\|_{3}.$

Corollary 2.2 follows similarly when applying the generalized Hölder
inequality with different parameters to obtain

$\mathbb{E}[\chi_{\lambda}\chi_{\mu}\chi_{\nu}]\leqslant\|\chi_{\nu}\|_{2}\|\chi_{\mu}\|_{4}\|\chi_{\lambda}\|_{4}.$

Finally, for Corollary 2.3 we apply the generalized Hölder inequality to
obtain that

$\mathbb{E}[\chi_{\lambda}\chi_{\mu}\chi_{\nu}]\leqslant\|\chi_{\lambda}\|_{q}\|\chi_{\mu}\|_{2/(1-1/q)}\|\chi_{\nu}\|_{2/(1-1/q)},$

where $q=\frac{\log(\chi_{\mu}(1)\chi_{\nu}(1))}{d}$. We may upper bound
$\|\chi_{\lambda}\|_{q}$ via Theorem 1.12. In order to bound
$\|\chi_{\mu}\|_{2/(1-1/q)}$, notice that

$\|\chi_{\mu}\|_{\frac{2}{1-1/q}}^{\frac{2}{1-1/q}}=\mathbb{E}\left[|\chi_{\mu}|^{\frac{2}{1-1/q}}\right]\leqslant\|\chi_{\mu}\|_{2}^{2}\chi_{\mu}(1)^{\frac{2}{1-1/q}-2}=\chi_{\mu}(1)^{\frac{2}{q-1}}.$

Therefore,
$\|\chi_{\mu}\|_{\frac{2}{1-1/q}}\leqslant\chi_{\mu}(1)^{\frac{1}{q}}\leqslant
e^{d}$. A similar bound holds for $\chi_{\nu}$. Combining these inequalities
completes the proof. ∎

##  6 Character ratios and Fourier coefficients

In this section we prove our upper bound on Fourier coefficients of functions
in terms of their $2$-norm and $1$-norm (Theorem 2.4). We then deduce our
upper bounds on the character ratios of conjugacy classes with few cycles
(Theorem 1.7).

###### Proof of Theorem 2.4.

Let $q\geqslant 2$ to be chosen later, and let $q^{\prime}$ be its Hölder
conjugate. Then we have $|\langle
f,\chi\rangle|\leqslant\|f\|_{q^{\prime}}\|\chi\|_{q}.$ We may then apply the
log-convexity of $L^{p}$-norms to obtain that

$\|f\|_{q^{\prime}}\leqslant\|f\|_{1}^{1-\theta}\|f\|_{2}^{\theta}=\|f\|_{1}\left(\frac{\|f\|_{2}}{\|f\|_{1}}\right)^{\theta}\leqslant\|f\|_{1}M^{\theta},$

where
$1-\frac{1}{q}=\frac{1}{q^{\prime}}=\frac{\theta}{2}+\frac{1-\theta}{1}.$
Rearranging, we obtain that $q=\frac{2}{\theta}.$ Choosing
$\theta=\frac{d}{\log M}$, we obtain that $M^{\theta}\leqslant e^{d}$ and
$q=\frac{2\log M}{d}\geqslant 2$. The theorem now follows by plugging in
Theorem 1.12 to obtain that

$\|\chi\|_{q}\leqslant\left(\frac{Cq}{\log
q}\right)^{d}\left(\frac{d^{d}\chi(1)}{n^{d}}\right)^{1-2/q}\leqslant\left(\frac{2Cq}{\log
q}\right)^{d}\left(\frac{d^{d}\chi(1)}{n^{d}}\right).$

Plugging everything together we obtain that

$\langle f,\chi\rangle\leqslant\chi(1)\|f\|_{1}\left(\frac{4eC\log
M}{n\log\left(\frac{2\log M}{d}\right)}\right)^{d},$

which completes the proof with $4eC$ instead of $C$. ∎

We now deduce Theorem 1.9.

###### Proof of Theorem 1.9.

Let $C$ be the conjugacy class of $\sigma,$ and write
$f=\frac{1_{C}}{\mu(C)}$. Since

$\frac{\|f\|_{2}}{\|f\|_{1}}=\frac{1}{\sqrt{\mu(C)}}\leqslant n^{\alpha
n^{\alpha}}$

and $d\leqslant\alpha n^{\alpha}\log n$, we may apply Theorem 2.4 with
$M=n^{\alpha n^{\alpha}}$ and obtain that

$|\chi(\sigma)|=|\langle f,\chi\rangle|\leqslant\chi(1)\left(\frac{C\alpha
n^{\alpha}\log n}{n\left(\log(\alpha n^{\alpha}\log n)-\log
d\right)}\right)^{d}$

for some constant $C>0$. This yields that

$\left|\frac{\chi(\sigma)}{\chi(1)}\right|\leqslant
n^{d(\alpha-1)}\left(\frac{C\alpha\log n}{\log(\alpha n^{\alpha}\log n)-\log
d}\right)^{d}.$

∎

We now present several technical lemmas that will be applied later to prove
Theorem 1.7 and to analyze mixing times. The following lemma simplifies
Theorem 2.4 by breaking it down into three regimes, making it easier to apply
later.

######  Lemma 6.1.

There exists an absolute constant $C$ such that the following holds. Let $G$
be either $A_{n}$ or $S_{n}$, and let $f\colon G\to\mathbb{R}$ be a function
with $\|f\|_{1}=1$. Suppose that $d$ is a positive integer and let $\chi$ be a
character of $G$ of level $d$. Then the following holds.

  1. 1.

If $d\leqslant\log^{0.9}\|f\|_{2}$ and $\|f\|_{2}>e$, then

$\frac{|\langle
f,\chi\rangle|}{\chi(1)}\leqslant\left(\frac{C\log\|f\|_{2}}{n\log\log\|f\|_{2}}\right)^{d}.$

  2. 2.

If $d\leqslant\log\|f\|_{2}$ then

$\frac{|\langle
f,\chi\rangle|}{\chi(1)}\leqslant\left(\frac{C\log\|f\|_{2}}{n}\right)^{d}.$

  3. 3.

Finally, if $d\geqslant\log\|f\|_{2}$ then

$\frac{|\langle f,\chi\rangle|}{\chi(1)}\leqslant\frac{\|f\|_{2}}{\chi(1)}.$

###### Proof.

The result for the first two regimes follows immediately from Theorem 2.4 with
$M=\|f\|_{2}$. The result for the third regime follows from Cauchy–Schwarz. ∎

In the third regime we obtain the following.

######  Lemma 6.2.

For each $\varepsilon>0$ there exist $c,C>0$ such that the following holds.
Let $\alpha\in\left(\frac{1}{c\log n},1-\frac{C\log\log n}{\log n}\right)$,
and let $f\colon S_{n}\to\mathbb{R}$ be a function with $\|f\|_{1}=1$ and

$\|f\|_{2}\leqslant n^{c\alpha n^{\alpha}}.$

Let $d\geqslant\log\|f\|_{2}$ be a positive integer, and let $\chi$ be a
character of level $d$. Then

$\frac{\left|\langle
f,\chi\rangle\right|}{\chi(1)}\leqslant\max(\varepsilon^{d},2^{-n^{3/5}})\chi(1)^{\alpha-1}.$

###### Proof.

By decreasing $c$ if necessary, we may assume that $n>n_{0},$ where $n_{0}$ is
sufficiently large.

Let $M=\log\|f\|_{2}$. Since $M<n/200$ for $n$ sufficiently large, we obtain
$\chi(1)\geqslant\left(\frac{n}{eM}\right)^{M}$ by Theorem 3.4. We also have
$\frac{\left|\langle
f,\chi\rangle\right|}{\chi(1)}\leqslant\frac{\|f\|_{2}}{\chi(1)},$ which shows
that

$\frac{\left|\langle
f,\chi\rangle\right|}{\chi(1)}\leqslant\chi(1)^{\alpha-1}\frac{\|f\|_{2}}{\chi(1)^{\alpha}}\leqslant\chi(1)^{\alpha-1}\frac{e^{M}}{e^{\frac{1}{2}\alpha
M\log(\frac{n}{eM})}\chi(1)^{\alpha/2}}.$

Now

$\chi(1)^{\alpha-1}\frac{e^{M}}{e^{\frac{1}{2}\alpha
M\log(\frac{n}{eM})}}\leqslant\chi(1)^{\alpha-1}\|f\|_{2}^{-\alpha/2\log\left(\frac{n}{e^{2/\alpha+1}M}\right)}\leqslant\chi(1)^{\alpha-1}.$

Moreover, for $d\leqslant n^{3/4}$ we may apply Theorem 3.4 and obtain that

$\chi(1)^{\alpha/2}\geqslant\left(\frac{n}{ed}\right)^{d\alpha/2}\geqslant
n^{d/9\alpha}\geqslant\left(e^{\frac{1}{9c}}\right)^{d}\geqslant\varepsilon^{-d},$

provided that $c$ is sufficiently small. For $d\geqslant n^{3/4}$, we apply
Theorem 3.4 with $n^{3/4}$ in place of $d$. We obtain that

$\chi(1)^{\alpha/2}\geqslant\left(\frac{n^{1/4}}{e}\right)^{n^{3/4}\alpha/2}\geqslant
2^{n^{3/5}},$

provided that $n$ is sufficiently large. This completes the proof of the
lemma. ∎

We now move on to the range where $d$ is small.

######  Lemma 6.3.

For each $\varepsilon>0$, there exists $c>0$, such that the following holds.
Let $f\colon S_{n}\to\mathbb{R}$ be a class function with $\|f\|_{1}=1$. Let
$d$ be a positive integer and let $\chi$ be a character of level $d$. Suppose
that $d\leqslant\log^{0.9}\|f\|_{2},$ and let $\alpha\in\left(\frac{1}{c\log
n},1-\frac{C\log\log n}{\log n}\right)$ be with $\|f\|_{2}\leqslant n^{c\alpha
n^{\alpha}}$. Then

$\frac{|\langle
f,\chi\rangle|}{\chi(1)}\leqslant\varepsilon^{d}\chi(1)^{\alpha-1}.$

###### Proof.

The statement holds for $\|f\|_{2}\leqslant e^{e}$, since we may apply the
bound $|\hat{f}(\chi)|\leqslant\|f\|_{2}$ and $\chi(1)\geqslant n-1$ for all
characters $\chi$ of positive level. We may therefore assume that
$\|f\|_{2}>e^{e}$. Write $M=\log\left((n^{c\alpha n^{\alpha}}\right))>e.$ By
corollary 6.1 we have

$\frac{|\langle
f,\chi\rangle|}{\chi(1)}\leqslant\left(\frac{C^{\prime}\log\|f\|_{2}}{n\log\log\|f\|_{2}}\right)^{d}\leqslant\left(\frac{C^{\prime}M}{\log
M}\right)^{d},$

by monotonicity of $x/\log x$ for $x>e$.

Since $\alpha>\frac{1}{c\log n}$ we have

$M=c\alpha n^{\alpha}\log n\geqslant n^{\alpha}.$

This shows that $\log M\geqslant\alpha\log n$ and hence,

$\frac{|\langle f,\chi\rangle|}{\chi(1)}\leqslant\left(\frac{C^{\prime}c\alpha
n^{\alpha}\log n}{\alpha n\log n}\right)^{d}\leqslant\left(\varepsilon
n^{\alpha-1}\right)^{d},$

provided that $c\leqslant\frac{\varepsilon}{C^{\prime}}$. We may now use
Corollary 3.3 to upper bound $\chi(1)\leqslant n^{d}$, which completes the
proof. ∎

Finally we move on to the remaining regime for the values of $d$.

######  Lemma 6.4.

For each $\varepsilon>0$ there exist $C,c>0$, such that the following holds.
Let $f\colon S_{n}\to\mathbb{R}$ be a class function with $\|f\|_{1}=1$. Let
$d$ be a natural number, $\alpha\in\left(\frac{1}{c\log n},1-\frac{C\log\log
n}{\log n}\right)$ and $\chi$ a character of level $d$. If

$\log^{0.9}\|f\|_{2}<d<\log\|f\|_{2},$

and $\|f\|_{2}\leqslant n^{c\alpha n^{\alpha}},$ then

$\frac{|\langle
f,\chi\rangle|}{\chi(1)}\leqslant\varepsilon^{d}\chi(1)^{\alpha-1}.$

###### Proof.

By decreasing $\alpha$ if necessary we may assume that either
$\|f\|_{2}=n^{c\alpha n^{\alpha}}$ or $\alpha=\frac{100\log\log n}{\log n}$.
By Corollary 6.1 we have

$\frac{|\langle
f,\chi\rangle|}{\chi(1)}\leqslant\left(\frac{C^{\prime}\log\|f\|_{2}}{n}\right)^{d}=\chi(1)^{\alpha-1}\left(\frac{C^{\prime}\log\|f\|_{2}}{n\log\log\|f\|_{2}}\right)^{d}n^{(1-\alpha)d}\cdot
A,$

where

$A=\left(\log\log\|f\|_{2}\right)^{d}\frac{\chi(1)^{1-\alpha}}{n^{(1-\alpha)d}}.$

Similarly to the proof of Lemma 6.3 we obtain that

$\frac{|\langle f,\chi\rangle|}{\chi(1)}\leqslant A\varepsilon^{\prime
d}\chi(1)^{\alpha-1}$

for an $\varepsilon^{\prime}>0$ of our choice. Therefore, our proof will be
completed once we show that $A\leqslant C^{\prime\prime d}$ for some
sufficiently large $C^{\prime\prime}$.

Now,

$\log\log\|f\|_{2}\leqslant\frac{\log d}{0.9}.$

Moreover, by Corollary 3.3,

$\chi(1)\leqslant\frac{n^{d}e^{d}}{d^{d/2}}.$

We will soon show that $\alpha<1-\frac{100\log\log d}{\log d}$. Combining with
the hypothesis, we obtain

$A\leqslant e^{d}\left(\frac{\log
d}{0.9}\right)^{d}d^{-\frac{1}{2}d(1-\alpha)}\leqslant C^{\prime\prime d}.$

We now show that

$\alpha<1-\frac{100\log\log d}{\log d}.$

If $\alpha<1/2$ we are done, so suppose that $\alpha\geqslant 1/2.$ We have
$\|f\|_{2}=n^{c\alpha n^{\alpha}}$. This implies that

$\log\|f\|_{2}=c\alpha n^{\alpha}\log n\geqslant n^{\alpha}$

and hence,

$\log\log\|f\|_{2}\geqslant\frac{1}{2}\log n.$

On the other hand, we have

$d>\log^{0.9}\|f\|_{2}$

and so

$\log d>0.9\log\log\|f\|_{2}\geqslant\frac{1}{20}\log n.$

By hypothesis we have

$\alpha<1-\frac{C\log\log n}{\log n}<1-\frac{100\log\log d}{\log d},$

provided that $C$ is sufficiently large. This completes the proof of the
lemma. ∎

Combining the above lemmas yields the following theorem.

######  Theorem 6.5.

For each $\varepsilon>0$ there exist $c,C>0$ such that the following holds.
Let

$\alpha\in\left(\frac{1}{c\log n},1-\frac{C\log\log n}{\log n}\right).$

Suppose that a class function $f\colon S_{n}\to\mathbb{R}$ satisfies
$\|f\|_{2}\leqslant n^{c\alpha n^{\alpha}}.$ Then for every $d>0$ and every
character $\chi$ of level $d$ we have

$\frac{\left|\langle
f,\chi\rangle\right|}{\chi(1)}\leqslant\max\left(\varepsilon^{d},2^{-n^{3/5}}\right)\chi(1)^{\alpha-1}.$

###### Proof.

The theorem follows immediately by combining Lemmas 6.2, 6.3, and 6.4. ∎

We are now ready to deduce our upper bound on the character ratios of
conjugacy classes with few cycles.

###### Proof of Theorem 1.7.

First we note that if a permutation $\sigma$ has at most $c\alpha n^{\alpha}$
cycles, then by the orbit-stabilizer theorem there exists a constant
$c^{\prime}=c^{\prime}(c)$, such that the conjugacy class of $\sigma$ has
density $\prod_{i=1}^{n}(f_{i}!i^{f_{i}})^{-1}\geqslant n^{-c^{\prime}\alpha
n^{\alpha}},$ where $f_{i}$ is the number of cycles of $\sigma$ of length $i$.
Theorem 1.7 now follows from Theorem 6.5 with $\varepsilon=1$. ∎

###  6.1 Adaptation to $A_{n}$

To adapt these results to the group $A_{n}$ instead of $S_{n}$, we observe
that most of the analysis applied in this section requires general arguments
on finite groups. The only properties of $S_{n}$ we used were Theorem 1.12,
Corollary 3.3 and Theorem 3.4. Therefore, if we replace the use of these
properties with the analogous statements Corollary 3.10, Corollary 3.9 and
Lemma 3.8, respectively, we obtain the following adapted results for $A_{n}$:

######  Theorem 6.6 (Adaptation of Theorem 2.4).

There exists an absolute constant $C>0$, such that the following holds. Let
$f$ be a class function with $\frac{\|f\|_{2}}{\|f\|_{1}}\leqslant M$ for some
bound $M$, and let $\chi$ be a character of $A_{n}$ of level
$d\leqslant\log(M)$. Then

$|\langle f,\chi\rangle|\leqslant\chi(1)\|f\|_{1}\left(\frac{C\log
M}{n\log\left(\frac{\log M}{d}\right)}\right)^{d}.$

######  Theorem 6.7 (Adaptation of Theorem 1.9).

There exists an absolute constant $C>0,$ such that the following holds for all
$\alpha\in(0,1)$. Let $\sigma\in A_{n}$ be a permutation whose conjugacy class
has density $\geqslant n^{-2\alpha n^{\alpha}}$. Then for every character
$\chi$ of $A_{n}$ of level $d\leqslant\alpha n^{\alpha}\log n$ we have

$\left|\frac{\chi(\sigma)}{\chi(1)}\right|\leqslant
n^{d(\alpha-1)}\left(\frac{C\alpha\log n}{\log(\alpha n^{\alpha}\log n)-\log
d}\right)^{d}.$

######  Theorem 6.8 (Adaptation of Theorem 6.5).

For each $\varepsilon>0$ there exist $c,C>0$ such that the following holds.
Let

$\alpha\in\left(\frac{1}{c\log n},1-\frac{C\log\log n}{\log n}\right).$

Suppose that a class function $f\colon A_{n}\to\mathbb{R}$ satisfies
$\|f\|_{2}\leqslant n^{c\alpha n^{\alpha}}.$ Then for every $d>0$ and every
character $\chi$ of level $d$ we have

$\frac{\left|\langle f,\chi\rangle\right|}{\chi(1)}\leqslant
2\max\left(\varepsilon^{d},2^{-n^{3/5}}\right)\chi(1)^{\alpha-1}.$

##  7 Mixing times

In this section we prove our mixing result, namely Theorem 1.4. Theorem 1.3
will then follow immediately as it consists of the special case where all the
functions are equal. We will then quickly deduce Corollary 1.5.

###  7.1 Proof of Theorem 1.4

The standard way to deduce mixing time results from character bounds of the
form $\frac{|\chi(\sigma)|}{\chi(1)}$ involves estimates of the Witten zeta
function $\sum_{\chi}\chi(1)^{-s}$ and is well known. This route works
smoothly when one is interested in rough estimates of the mixing time, but our
more precise estimates require a different approach.

###### Proof of Theorem 1.4.

We may assume that $n$ is sufficiently large by increasing $C$ if necessary.
It is well known that we have

$\langle
f_{1}*f_{2}*\cdots*f_{\ell},\chi\rangle=\frac{\hat{f_{1}}(\chi)\cdots\hat{f_{\ell}}(\chi)}{\chi(1)^{\ell-1}}.$

Since the characters form an orthonormal basis, we obtain

$\|f_{1}*f_{2}*\cdots*f_{\ell}-1\|_{2}^{2}=\sum_{\chi\neq
1}\frac{|\hat{f_{1}}(\chi)|^{2}\cdots|\hat{f_{\ell}}(\chi)|^{2}}{\chi(1)^{2\ell-2}}.$

Recall that $0\leqslant\alpha_{i}\leqslant 1-\frac{C\log\log n}{\log n}$ for
all $1\leqslant i\leqslant\ell$ and $\sum_{i}\alpha_{i}\leqslant\ell-1$. Let
$c>0$ be a sufficiently small constant to be chosen later. Since the statement
of the theorem gets weaker as $\alpha_{i}$ increases in the interval
$(0,1-\frac{2C\log\log n}{\log n}]$, we may increase the $\alpha_{i}$ in the
interval until either $\alpha_{i}\geqslant 1-\frac{2C\log\log n}{\log n}$ for
all $i$ or $\sum_{i}\alpha_{i}=\ell-1$. In either case, we have
$\alpha_{i}\geqslant\min((\ell-1)\frac{C\log\log n}{\log n},1-\frac{2C\log\log
n}{\log n})\geqslant\frac{1}{c\log n}$, provided that $C,n$ are sufficiently
large. By Theorem 6.8 with $\varepsilon/16$ we have

$\|f_{1}*f_{2}*\cdots*f_{\ell}-1\|_{2}^{2}\leqslant\sum_{d=1}^{n}\sum_{\chi\text{
of level }d}4\max((\varepsilon/16)^{d},2^{-n^{3/5}})^{2}<\varepsilon,$

provided that $n$ is sufficiently large and $c$ is sufficiently small. Indeed,
the number of characters of level $d$ is the same as the number of partitions
of $d$ which is easily upper bounded by $2^{d}$, and there are at most
$e^{O(\sqrt{n})}$ characters overall. ∎

###  7.2 Deducing Corollary 1.5

###### Proof of Corollary 1.5.

We have

$f*f(1)=\mathbb{E}_{\sigma\sim A_{n}}[f(\sigma)f(\sigma^{-1})]=\|f\|_{2},$

where the last equality follows from the fact that $f$ is real valued and
symmetric. The corollary now follows from Theorem 1.4. ∎

##  8 Product mixing

In this section we show that $A_{n}$ is normally an $n^{-cn^{1/3}}$-mixer when
$c$ is sufficiently small, but not normally an $n^{-Cn^{1/3}}$-mixer when $C$
is sufficiently large.

###### Proof of Theorem 2.5.

Let $A,B,C$ be subsets of $A_{n}$ of density $\geqslant n^{-cn^{1/3}}$. Write
$f=\frac{1_{A}}{\mu(A)},g=\frac{1_{B}}{\mu(B)}$ and $h=\frac{1_{C}}{\mu(C)}$.
Then we have

$\frac{\Pr_{a\sim A,b\sim B}[ab\in C]-\mu(C)}{\mu(C)}=\langle
f*g,h\rangle-1=\sum_{\chi\neq
1}\frac{\hat{f}(\chi)\hat{g}(\chi)\hat{h}(\chi)}{\chi(1)}.$

Applying Theorem 6.8 with $\alpha=1/3$ completes the proof in similar fashion
to the proof of Theorem 1.4. ∎

###### Proof of Corollary 2.6.

Let $\sigma\in A_{n}$, and set $B=A$ and $C=A^{-1}\sigma^{A_{n}}.$ Since both
$A,B$ and $C$ have density $\geqslant n^{-cn^{1/3}}$, we may apply Theorem 2.5
and obtain that $AB\cap C\neq\emptyset$. Therefore, there exists $a\in A$ such
that $a^{-1}\sigma\in A^{2}$, which implies that $\sigma\in A^{3}$. ∎

###  8.1 Sharpness example

Our sharpness example consists of the set of permutations with about $n^{1/3}$
fixed points and a single $(n-n^{1/3})$-cycle.

######  Proposition 8.1.

There exists an absolute constant $C>0,$ such that $A_{n}$ is not normally an
$n^{-Cn^{1/3}}$-mixer.

###### Proof.

We may assume that $n$ is sufficiently large by increasing $C$ if necessary.
Set $A$ to be the set of permutations with $t=\lceil 10n^{1/3}+1\rceil$ fixed
points and a single $(n-t)$-cycle. We will prove that

$\frac{\Pr_{a,b\sim A}[ab\in A]-\mu(A)}{\mu(A)}>1.01.$

Let $f=g=h=\frac{1_{A}}{\mu(A)}$. We have

$\langle f*g,h\rangle-1=\sum_{\chi\neq
1}\frac{\widehat{f}(\chi)^{3}}{\chi(1)}.$

Consider the partition $(n-1,1)$. Since $\chi_{n-1,1}(\sigma)$ counts the
fixed points of $\sigma$ minus 1, the term with the character $\chi_{n-1,1}$
contributes at least 1000 to the sum. Therefore, in order for the sum to be
$o(1)$, the other terms must cancel it out. However, by the Murnaghan–Nakayama
rule all the terms corresponding to characters of level $\leqslant n^{1/3}$
are positive. Indeed, when removing a rim hook of length $n-t$ from a Young
diagram of level at most $n^{1/3}$, the rim hook must be contained in the
first row. We now upper bound the sum of the absolute values of terms of level
$>n^{1/3}.$ For levels $d\geqslant n^{5/12}$ we may combine the following
facts to deduce that the sum over all characters of level $>n^{5/12}$ of
$\frac{|\hat{f}(\chi)^{3}|}{\chi(1)}$ is $\leqslant 1.$ Firstly, we have
$|\hat{f}(\chi)|\leqslant\|f\|_{2}\leqslant n^{Cn^{1/3}}$ for some absolute
constant $C>0$. Secondly, the number of irreducible characters of level $d$ is
the number of partitions of $d$, which is $e^{O(\sqrt{d})}$ and overall the
number of characters is $e^{O(\sqrt{n})}$. Finally, we have
$\chi(1)\geqslant\left(\frac{n}{ed}\right)^{d}$ when $d\leqslant n/200$ and at
least $e^{\Omega(n)}$ for $d>n/200$ by Theorem 3.4. To upper bound
$|\hat{f}(\chi)|$ for the remaining $\chi$, we fix a $t$-umvirate $U_{I}$.
Identifying $U_{I}$ with $S_{n-|I|}$ we let $\sigma$ be an $(n-|I|)$-cycle in
$U_{I}$. We then have $\hat{f}(\chi)=\chi_{I\to I}(\sigma).$ We may now use
Theorem 1.14 to upper bound

$\frac{1}{n}\chi_{I\to I}(\sigma)^{2}\leqslant\|\chi_{I\to
I}\|_{2}^{2}\leqslant 2^{d}\tilde{\chi}(1),$

where $\tilde{\chi}$ is obtained from $\chi$ by deleting its first row and
using the fact that the density of the $(n-|I|)$-cycles is
$\geqslant\frac{1}{n}$. We also have
$\chi(1)\geqslant\binom{n-d}{d}\tilde{\chi}(1)$ by Lemma 3.1. This shows that
we have

$\frac{|\hat{f}(\chi)|^{3}}{\chi(1)}\leqslant\frac{2^{3d/2}n^{3/2}\tilde{\chi}(1)^{2}}{\binom{n-d}{d}}.$

We may now upper bound $\tilde{\chi}(1)\leqslant\sqrt{d!}$ to obtain that

$\frac{|\hat{f}(\chi)^{3}|}{\chi(1)}\leqslant 2^{-d}.$

Summing over all $\chi$ of levels in the interval $(n^{1/3},n^{5/12})$
completes the proof as there are only $e^{O(\sqrt{d})}$ characters of level
$d$ for each $d$. ∎

## References

  * [1] Nir Avni and Itay Glazer.  On the Fourier coefficients of word maps on unitary groups.  arXiv preprint arXiv:2210.04164, 2022.
  * [2] Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, and Marc Vinyals.  Complexity measures on the symmetric group and beyond.  In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [3] Persi Diaconis and Mehrdad Shahshahani.  Generating a random permutation with random transpositions.  Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 57(2):159–179, 1981.
  * [4] David Ellis, Yuval Filmus, and Ehud Friedgut.  A stability result for balanced dictatorships in $S_{n}$.  Random Structures & Algorithms, 46(3):494–530, 2015.
  * [5] David Ellis, Ehud Friedgut, and Haran Pilpel.  Intersecting families of permutations.  Journal of the American Mathematical Society, 24(3):649–682, 2011\.
  * [6] David Ellis, Guy Kindler, Noam Lifshitz, and Dor Minzer.  Product mixing in compact Lie groups.  In preperation.
  * [7] Shai Evra, Guy Kindler, and Noam Lifshitz.  Polynomial Bogolyubobov for special linear groups via the eta correspondence.  In preparation.
  * [8] Yuval Filmus, Guy Kindler, Noam Lifshitz, and Dor Minzer.  Hypercontractivity on the symmetric group.  arXiv:2009.05503, 2020.
  * [9] Martino Garonzi and Attila Maróti.  Alternating groups as products of four conjugacy classes.  Archiv der Mathematik, 116:121–130, 2021.
  * [10] W. T. Gowers.  Quasirandom groups.  Combinatorics, Probability and Computing, 17(3):363–387, 2008.
  * [11] Robert M. Guralnick, Michael Larsen, and Pham Huu Tiep.  Character levels and character bounds.  In Forum of Mathematics, Pi, volume 8. Cambridge University Press, 2020.
  * [12] Shamgar Gurevich and Roger Howe.  Harmonic analysis on GL$(n)$ over finite fields.  arXiv preprint arXiv:2105.12369, 2021.
  * [13] Harald Helfgott.  Growth in groups: ideas and perspectives.  Bulletin of the American Mathematical Society, 52(3):357–413, 2015\.
  * [14] Peter Keevash and Noam Lifshitz.  Sharp hypercontractivity for symmetric groups and its applications.  arXiv preprint arXiv:2307.15030, 2023.
  * [15] Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer.  Global hypercontractivity and its applications.  Journal of the American Mathematical Society, 2023.  To appear.
  * [16] Nathan Keller, Noam Lifshitz, and Omri Marcus.  Sharp hypercontractivity for global functions.  arXiv preprint arXiv:2307.01356, 2023.
  * [17] Subhash Khot, Dor Minzer, and Muli Safra.  Pseudorandom sets in Grassmann graph have near-perfect expansion.  Annals of Mathematics, 198(1):1–92, 2023.
  * [18] Alexander Kleshchev, Michael Larsen, and Pham Huu Tiep.  Level, rank, and tensor growth of representations of symmetric groups.  arXiv preprint arXiv:2212.06256, 2022.
  * [19] Michael Larsen and Aner Shalev.  Characters of symmetric groups: sharp bounds and applications.  Inventiones Mathematicae, 174:645–687, 2008.
  * [20] Michael Larsen and Pham Huu Tiep.  Squares of conjugacy classes in alternating groups.  arXiv preprint arXiv:2305.04806, 2023.
  * [21] Thomas W. Müller and Jan-Christoph Schlage-Puchta.  Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks.  Advances in Mathematics, 213(2):919–982, 2007.
  * [22] Nikolay Nikolov and László Pyber.  Product decompositions of quasirandom groups and a jordan type theorem.  Journal of the European Mathematical Society, 13(4):1063–1077, 2011\.
  * [23] Greta Panova.  Complexity and asymptotics of structure constants.  arXiv preprint arXiv:2305.02553, 2023.
  * [24] Greta Panova.  Computational complexity in algebraic combinatorics.  arXiv preprint arXiv:2306.17511, 2023.
  * [25] Yuval Roichman.  Upper bound on the characters of the symmetric groups.  Inventiones Mathematicae, 125:451–485, 1996.
  * [26] Bruce E. Sagan.  The symmetric group: representations, combinatorial algorithms, and symmetric functions, volume 203.  Springer Science & Business Media, 2013.