\documentclass[submission]{FPSAC2017} \articlenumber{50} \addbibresource{50_Swanson.bib} % Packages \usepackage{amsmath} % provides \underset, etc. \usepackage{accents} % provides \accentset, etc.; must be loaded after amsmath \usepackage{amsopn,amssymb} % provides \DeclareMathOperator, \mathbb, etc. \usepackage{amsthm} \usepackage{bm} % provides \bm for math bold greek letters \usepackage{bbm} % provides \mathbbm, eg. for lower-case blackboard bold characters \usepackage{enumerate} % more powerful enumerate environments \usepackage{microtype} % nicer text spacing \usepackage[intoc,refpage]{nomencl} % make a symbol list \usepackage{multicol} % put lists with many short entries into multiple columns \usepackage{setspace} % \doublespacing, etc. \usepackage{shuffle} % provides \shuffle and \cshuffle \usepackage{soul} % multi-line underlines \usepackage{thmtools} % interface to amsthm \usepackage{tikz-cd} % nice commutative diagrams; see cd environment below \usetikzlibrary{calc} % allow \let's in tikzpicture environments \usetikzlibrary{positioning} % allow "above = 1" syntax \usepackage{xifthen} % \ifthenelse, \isempty, etc. \usepackage{subcaption} % provides subfigure environment, etc. % Math operators \DeclareMathOperator{\Ab}{Ab} \DeclareMathOperator{\alg}{-alg} \DeclareMathOperator{\Ann}{Ann} \DeclareMathOperator{\Ass}{Ass} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\cdes}{cdes} \DeclareMathOperator{\CDes}{CDes} \DeclareMathOperator{\CDT}{CDT} \DeclareMathOperator{\Ch}{ch} \DeclareMathOperator{\Char}{char} \DeclareMathOperator{\cHom}{\mathcal{H}\textit{om}} \DeclareMathOperator{\code}{code} \DeclareMathOperator{\codim}{codim} \DeclareMathOperator{\coker}{coker} \DeclareMathOperator{\col}{col} \DeclareMathOperator{\comaj}{comaj} \DeclareMathOperator{\cont}{cont} \DeclareMathOperator{\cmaj}{cmaj} \DeclareMathOperator{\CT}{CT} \DeclareMathOperator{\cycle}{cycle} \DeclareMathOperator{\des}{des} \DeclareMathOperator{\Des}{Des} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\End}{End} \DeclareMathOperator{\exc}{exc} \DeclareMathOperator{\Ext}{Ext} \DeclareMathOperator{\fin}{fin} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\Fl}{Fl} \DeclareMathOperator{\FP}{FP} \DeclareMathOperator{\Flags}{Flags} \DeclareMathOperator{\fl}{fl} \DeclareMathOperator{\flex}{flex} \DeclareMathOperator{\freq}{freq} \DeclareMathOperator{\id}{id} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\GKdim}{GKdim} \DeclareMathOperator{\gl}{gl} \DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\gldim}{gldim} \DeclareMathOperator{\gr}{gr} \DeclareMathOperator{\Gr}{Gr} \DeclareMathOperator{\GUD}{GUD} \DeclareMathOperator{\hgt}{ht} \DeclareMathOperator{\Hilb}{Hilb} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\injdim}{injdim} \DeclareMathOperator{\Int}{Int} \DeclareMathOperator{\Kdim}{Kdim} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\lex}{lex} \DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\mmaj}{mmaj} \DeclareMathOperator{\Mod}{mod} \DeclareMathOperator{\myst}{myst} \DeclareMathOperator{\nil}{nil} \DeclareMathOperator{\NSYM}{NSYM} \DeclareMathOperator{\op}{op} \DeclareMathOperator{\period}{period} \DeclareMathOperator{\Perm}{Perm} \DeclareMathOperator{\Perms}{Perms} \DeclareMathOperator{\Pre}{pre} \DeclareMathOperator{\projdim}{projdim} \DeclareMathOperator{\pt}{pt} \DeclareMathOperator{\QH}{QH} \DeclareMathOperator{\QSYM}{QSYM} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\Res}{Res} \DeclareMathOperator{\Rings}{Rings} \DeclareMathOperator{\row}{row} \DeclareMathOperator{\RSK}{RSK} \DeclareMathOperator{\rw}{rw} \DeclareMathOperator{\sd}{sd} \DeclareMathOperator{\Sets}{\textit{Sets}} \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\sh}{sh} \DeclareMathOperator{\Sh}{Sh} \DeclareMathOperator{\SIT}{SIT} \DeclareMathOperator{\SL}{SL} \DeclareMathOperator{\SO}{SO} \DeclareMathOperator{\sort}{sort} \DeclareMathOperator{\Sp}{Sp} \DeclareMathOperator{\Span}{Span} \DeclareMathOperator{\spec}{spec} \DeclareMathOperator{\spin}{spin} \DeclareMathOperator{\St}{St} \DeclareMathOperator{\Stab}{Stab} \DeclareMathOperator{\str}{str} \DeclareMathOperator{\Supp}{Supp} \DeclareMathOperator{\SST}{SST} \DeclareMathOperator{\SSYT}{SSYT} \DeclareMathOperator{\stat}{stat} \DeclareMathOperator{\std}{std} \DeclareMathOperator{\syt}{syt} \DeclareMathOperator{\SYT}{SYT} \DeclareMathOperator{\SYM}{SYM} \DeclareMathOperator{\Sym}{Sym} \DeclareMathOperator{\ssum}{ssum} \DeclareMathOperator{\Sum}{sum} \DeclareMathOperator{\TL}{TL} \DeclareMathOperator{\Tot}{Tot} \DeclareMathOperator{\Tr}{Tr} \DeclareMathOperator{\trdeg}{trdeg} \DeclareMathOperator{\triv}{triv} \DeclareMathOperator{\UD}{UD} \DeclareMathOperator{\wgt}{wgt} \DeclareMathOperator{\word}{word} \DeclareMathOperator{\Words}{Words} \DeclareMathOperator{\YUD}{YUD} % Named ``ilim'' for ``inverse limit'' to avoid conflicting with \lim \newcommand{\ilim}{\operatornamewithlimits{\underset{\longleftarrow}{lim}}} % ``dlim'' for ``direct limit'' \newcommand{\dlim}{\operatornamewithlimits{\underset{\longrightarrow}{lim}}} \newcommand{\mbinom}[2]{\left(\!\!\binom{#1}{#2}\!\!\right)} % Convenient shortcuts \newcommand{\bA}{\mathbb{A}} \newcommand{\bC}{\mathbb{C}} \newcommand{\bE}{\mathbb{E}} \newcommand{\bF}{\mathbb{F}} \newcommand{\bk}{\mathbbm{k}} \newcommand{\bN}{\mathbb{N}} \newcommand{\bP}{\mathbb{P}} \newcommand{\bQ}{\mathbb{Q}} \newcommand{\bR}{\mathbb{R}} \newcommand{\bZ}{\mathbb{Z}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cH}{\mathcal{H}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cO}{\mathcal{O}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cS}{\mathcal{S}} \newcommand{\fg}{\mathfrak{g}} \newcommand{\fm}{\mathfrak{m}} \newcommand{\fn}{\mathfrak{n}} \newcommand{\fp}{\mathfrak{p}} \newcommand{\fq}{\mathfrak{q}} \newcommand{\fS}{\mathfrak{S}} \newcommand{\fU}{\mathfrak{U}} \newcommand{\tsub}{\mathrel{\unlhd}} % Convenient general macros \newcommand{\mm}{\texttt{--}} \newcommand\numberthis{\addtocounter{equation}{1}\tag{\theequation}} \newcommand{\up}{\mathord{\uparrow}} \newcommand{\Ind}{\!\!\mathord{\uparrow}} \newcommand{\res}{\!\!\!\mathord{\downarrow}} \newcommand{\down}{\mathord{\downarrow}} \renewcommand{\star}{\mathord{*}} \newcommand{\too}[1]{\stackrel{#1}{\to}} \newcommand{\tooo}[2]{\underset{#2}{\overset{#1}{\to}}} \newcommand{\oo}[3]{\underset{#3}{\overset{#2}{#1}}} \newcommand{\sline}{\noindent\makebox[\linewidth]{\rule{\linewidth}{0.4pt}}} \newcommand{\mdy}[1]{\sline\vspace{0.19cm}\\\centering{\Large{\textbf{#1}}}\\\sline} \newcommand{\ind}{\!\!\uparrow} \renewcommand{\res}{\!\!\downarrow} \newcommand{\f}{\frac} \newcommand{\n}{\f{1}{n}} \newcommand{\lm}{\lambda} \newcommand{\lam}{\lambda} \newcommand{\pa}[1]{{\left( {#1}\right)}} \newcommand{\ha}{\f{1}{2}} \newcommand{\sub}{\subset} \newcommand{\al}{\alpha} \newcommand{\8}{\infty} \newcommand{\es}{\emptyset} \newcommand{\bs}{\bigskip} \newcommand{\D}{\Delta} \newcommand{\de}{\delta} \newcommand{\be}{\beta} \newcommand{\w}{\omega} \newcommand{\s}{\sigma} \newcommand{\si}{\sigma} \newcommand{\g}{\gamma} \newcommand{\dd}{\cdot} \newcommand{\inv}{^{-1}} \newcommand{\zhat}{\widehat{0}} \newcommand{\ohat}{\widehat{1}} \newcommand{\idd}{\accentset{\bullet}{\iota}} \newcommand{\nur}{\overset{\to}{\nu}} \newcommand{\nul}{\overset{\gets}{\nu}} \newcommand{\wt}[1]{\widetilde{#1}} \newcommand{\tx}{\text} \newcommand{\sm}{\setminus} \newcommand{\lp}{\left(} \newcommand{\rp}{\right)} \newcommand{\ch}{\binom} \newcommand{\imp}{\implies} \newcommand{\va}{\varphi} \newcommand{\mch}[2]{% \mathchoice% {\left(\kern-0.48em\ch{#1}{#2}\kern-0.48em\right)} {\left(\kern-0.30em\ch{\smash{#1}}{\smash{#2}}\kern-0.30em\right)} {\left(\kern-0.30em\ch{\smash{#1}}{\smash{#2}}\kern-0.30em\right)} {\left(\kern-0.30em\ch{\smash{#1}}{\smash{#2}}\kern-0.30em\right)} } % make subfigure caption identifier lower-case \captionsetup[subfigure]{labelfont=rm} % rc-graph macros \font\co=lcircle10 \def\petit#1{{\scriptstyle #1}} \def\pes#1#2{\hbox{\rlap{$\petit {#1}_{\scriptscriptstyle #2}$}} \phantom{\petit 1}} \def\plb{\smash{\lower2pt\hbox{\rlap{\vrule height12pt}} \raise2pt\hbox{\rlap{\hskip-4pt \vrule height.4pt depth0pt width14.7pt}}}} \def\py{\smash{\raise2pt\hbox{\co \rlap{\rlap{\char'005} \char'007}} \raise6pt\hbox{\rlap{\vrule height4.5pt}} \raise2pt\hbox{\rlap{\hskip4pt \vrule height0.4pt depth0pt width6.5pt}}}} \def\pe{\smash{\raise2pt\hbox{\co \rlap{\rlap{\char'005} \phantom{\char'007}}} \raise6pt\hbox{\rlap{\vrule height4.5pt}}}} % Mark Haiman's tableaux macro, modified to put dashed lines around empty boxes \setlength{\unitlength}{0.06em} \newlength{\cellsize} \setlength{\cellsize}{18\unitlength} \newsavebox{\cell} \sbox{\cell}{\begin{picture}(18,18) \put(0,0){\line(1,0){18}} \put(0,0){\line(0,1){18}} \put(18,0){\line(0,1){18}} \put(0,18){\line(1,0){18}} \end{picture}} \newsavebox{\dashedcell} \sbox{\dashedcell}{\begin{picture}(18,18) \multiput(0,0)(5,0){4}{\line(1,0){3}} \multiput(0,0)(0,5){4}{\line(0,1){3}} \multiput(18,0)(0,5){4}{\line(0,1){3}} \multiput(0,18)(5,0){4}{\line(1,0){3}} \end{picture}} \newcommand\cellify[1]{\def\thearg{#1}\def\nothing{}% \ifx\thearg\nothing \hbox to 0pt{\usebox{\dashedcell} \hss}\else% \hbox to 0pt{\usebox{\cell} \hss}\fi% \vbox to \cellsize{ \vss \hbox to \cellsize{\hss$#1$\hss} \vss}} \newcommand\tableau[1]{\vtop{\let\\\cr \baselineskip -16000pt \lineskiplimit 16000pt \lineskip 0pt \ialign{&\cellify{##}\cr#1\crcr}}} \newenvironment{cd}[1][] {\begin{center}\begin{tikzcd}[#1]} {\end{tikzcd}\end{center}} % Index/nomenclature configuration and macros \renewcommand\nomname{List of Symbols} \newcommand{\bu}[2][]{\framebox{#2}\ifthenelse{\isempty{#1}}{\index{#2}} {\index{#1@#2}}} \newcommand{\mbu}[3][]{\boxed{#2}\nomenclature[$#1$]{$#2$}{#3}} % Section macros \newcommand{\Section}[1]{\begin{samepage}\sline\vspace{-0.5cm}\section*{\centering{#1}}\vspace{-0.5cm}\sline \addcontentsline{toc}{subsection}{#1}\end{samepage}} \newcommand{\Subsection}[1]{\subsection*{\centering\color{teal}#1} \addcontentsline{toc}{subsection}{#1}} \newcommand{\Subsubsection}[1]{\subsubsection*{\centering\color{teal}#1} \addcontentsline{toc}{subsubsection}{#1}} \theoremstyle{plain} \newtheorem{Theorem}{Theorem}[section] \newtheorem{Lemma}[Theorem]{Lemma} \newtheorem{Proposition}[Theorem]{Proposition} \newtheorem{Corollary}[Theorem]{Corollary} \newtheorem{Fact}[Theorem]{Fact} \newtheorem{Conjecture}[Theorem]{Conjecture} \newtheorem{Question}[Theorem]{Question} \theoremstyle{definition} \newtheorem{Notation}[Theorem]{Notation} \declaretheorem[style=definition,sibling=Theorem]{Definition} \newtheorem{Example}[Theorem]{Example} \newtheorem{Remark}[Theorem]{Remark} \newtheorem{Aside}[Theorem]{Aside} \newtheorem*{Summary}{Summary} \newtheorem*{Outline}{Outline} \title{Standard Tableaux and Modular Major Index} \author{Joshua P. Swanson} \address{University of Washington, Seattle, USA\\} \received{November 13th, 2016} \abstract{ We provide simple necessary and sufficient conditions for the existence of a standard Young tableau of a given shape and major index $r$ mod $n$, for all $r$. Our result generalizes the $r=1$ case due essentially to Klyachko (1974) and proves a recent conjecture due to Sundaram (2016) for the $r=0$ case. A byproduct of the proof is an asymptotic equidistribution result for ``almost all'' shapes. The proof uses a representation-theoretic formula involving Ramanujan sums and normalized symmetric group character estimates. Further estimates involving ``opposite'' hook lengths are given which are well-adapted to classifying which partitions $\lambda \vdash n$ have $f^\lambda \leq n^d$ for fixed $d$. } \keywords{standard Young tableaux, symmetric group characters, major index, hook length formula} \begin{document} \maketitle \section{Introduction} \label{sec:intro} Let $\lambda \vdash n$ be an integer partition of size $n$, and let $\SYT(\lambda)$ denote the set of standard Young tableaux of shape $\lambda$. Let $\maj T$ denote the major index of $T \in \SYT(\lambda)$, namely the sum of all $i$ for which $i+1$ appears below $i$ (in English notation). We are chiefly interested in the counts \[ a_{\lambda, r} := \#\{T \in \SYT(\lambda) : \maj T \equiv_n r\} \] where $r$ is taken mod $n$. To avoid giving undue weight to trivial cases, we take $n \geq 1$ throughout. Work due to Klyachko and, later, Kraskiewicz-Weyman, gives the following: \begin{Theorem}[{\cite[Proposition 2]{klyachko74}}, {\cite{kw01}}] \label{thm:kly} Let $\lambda \vdash n$ and $n \geq 1$. Then $a_{\lambda, 1}$ is positive except in the following cases, when it is zero: \begin{itemize} \item $\lambda = (2, 2)$ or $\lambda = (2, 2, 2)$; \item $\lambda = (n)$ when $n > 1$; or $\lambda = (1^n)$ when $n > 2$. \end{itemize} \end{Theorem} Indeed, the $a_{\lambda, r}$ have a natural interpretation as irreducible multiplicities as follows, a result originally due to Kraskiewicz-Weyman. Let $C_n$ be the cyclic group of order $n$ generated by the long cycle $\sigma_n := (1 2 \cdots n) \in S_n$, let $S^\lambda$ be the Specht module of shape $\lambda \vdash n$, and let $\chi^r \colon C_n \to \bC^\times$ be the irreducible representation given by $\chi^r(\sigma_n^i) := \omega_n^{ri}$ where $\omega_n$ is a fixed primitive $n$th root of unity and $r \in \bZ/n$. Let $\langle -, -\rangle$ denote the standard scalar product for complex representations. \begin{Theorem}[see {\cite[Theorem~1]{kw01}}] \label{thm:mults} With the above notation, we have \[ \langle S^\lambda, \chi^r\ind_{C_n}^{S_n} \rangle = a_{\lambda, r} = \langle \chi^r, S^\lambda\res_{C_n}^{S_n} \rangle. \] Moreover, $a_{\lambda, r}$ depends only on $\lambda$ and $\gcd(n, r)$, i.e.~if $\gcd(n, r) = \gcd(n, s)$ then $a_{\lambda, r} = a_{\lambda, s}$. \end{Theorem} \begin{Remark} Kraskiewicz-Weyman gave the first equality in \Cref{thm:mults}, and the second follows by Frobenius reciprocity. Klyachko \cite[Proposition 2]{klyachko74} actually determined which $S^\lambda$ contain faithful representations of $C_n$ in agreement with \Cref{thm:kly}. One may see through a variety of methods that $\chi^r\ind_{C_n}^{S_n}$ depends up to isomorphism only on $\gcd(r, n)$. The manuscript \cite{kw01} was long-unpublished, the delay being largely due to Klyachko having already given a significantly more direct proof of their main application, relating $\chi^1\ind_{C_n}^{S_n}$ to free Lie algebras, though we have no need of this connection. For a more modern and unified account of these results, see \cite[Theorems~8.8-8.12]{reutenauer93}. \end{Remark} The following conjecture due to Sundaram was originally stated in terms of the multiplicity of $S^\lambda$ in $1\ind_{C_n}^{S_n}$. \begin{Conjecture}[\cite{sundaram16}] \label{conj:sundaram} Let $\lambda \vdash n$ and $n \geq 1$. Then $a_{\lambda, 0}$ is positive except in the following cases, when it is zero: $n > 1$ and \begin{itemize} \item $\lambda = (n-1, 1)$ \item $\lambda = (2, 1^{n-2})$ when $n$ is odd \item $\lambda = (1^n)$ when $n$ is even. \end{itemize} \end{Conjecture} \noindent \Cref{conj:sundaram} is the $r=0$ case of the following theorem, which is our main result. \begin{Theorem} \label{thm:main} Let $\lambda \vdash n$ and $n \geq 1$. Then $a_{\lambda, r}$ is positive except in the following cases, when it is zero: $n > 1$ and \begin{itemize} \item $\lambda = (2, 2)$, $r = 1, 3$; or $\lambda = (2, 2, 2)$, $r = 1, 5$; or $\lambda = (3, 3)$, $r = 2, 4$; \item $\lambda = (n-1, 1)$ and $r=0$; \item $\lambda = (2, 1^{n-2})$, $r = \begin{cases} 0 & \text{if $n$ is odd} \\ \frac{n}{2} & \text{if $n$ is even}; \end{cases}$ \item $\lambda = (n)$, $r \in \{1, \ldots, n-1\}$; \item $\lambda = (1^n)$, $r \in \begin{cases} \{1, \ldots, n-1\} & \text{if $n$ is odd} \\ \{0, \ldots, n-1\} - \{\frac{n}{2}\} & \text{if $n$ is even}. \end{cases}$ \end{itemize} Equivalently, using \Cref{thm:mults}, every irreducible representation appears in each $\chi^r\ind_{C_n}^{S_n}$ or $S^\lambda\res_{C_n}^{S_n}$ except in the noted exceptional cases. \end{Theorem} Our main tool is the following well-known representation-theoretic formula. See \Cref{sec:formula} for further discussion of its origins and a generalization. Let $\chi^\lambda(\mu)$ denote the character of $S^\lambda$ at a permutation of cycle type $\mu$. Write $f^\lambda := \chi^\lambda(1^n) = \dim S^\lambda = \#\SYT(\lambda)$. \begin{Theorem} \label{thm:formula} Let $\lambda \vdash n$ and $n \geq 1$. For all $r \in \bZ/n$, \[ \frac{a_{\lambda,r}}{f^\lambda} = \frac{1}{n} + \frac{1}{n} \sum_{\substack{\ell \mid n \\ \ell \neq 1}} \frac{\chi^\lambda(\ell^{n/\ell})}{f^\lambda} c_\ell(r) \] where \[ c_\ell(r) := \mu\left(\frac{\ell}{\gcd(\ell, r)}\right) \frac{\phi(\ell)}{\phi(\ell/\gcd(\ell, r))} \] is a Ramanujan sum, $\mu$ is the classical M\"obius function, and $\phi$ is Euler's totient function. \end{Theorem} We estimate the quotients in the preceding formula using the following result due to Fomin and Lulov. A \textit{ribbon} is a connected skew shape with no $2 \times 2$ rectangles. \begin{Theorem}[{\cite[Theorem~1.1]{fl95}}] \label{thm:fl_bound} Let $\lambda \vdash n$ where $n = \ell s$. Suppose $\lambda$ can be written as $s$ successive ribbons each of length $\ell$. Then \[ |\chi^\lambda(\ell^s)| \leq \frac{s! \ell^s}{(n!)^{1/\ell}} (f^\lambda)^{1/\ell}. \] \end{Theorem} \Cref{thm:fl_bound} is based on the following generalization of the hook length formula (the $\ell=1$ case), which seems less well-known than it deserves. For $\lambda \vdash n$, write $c \in \lambda$ to mean that $c$ is a cell in $\lambda$. Further write $h_c$ for the \textit{hook length} of $c$ and write $[n] := \{1, 2, \ldots, n\}$. \begin{Theorem}[{\cite[Corollary~2.2]{fl95}; see also \cite[2.7.32]{jk81}}] \label{thm:hook} Let $\lambda \vdash n$ where $n = \ell s$. Then \begin{equation} \label{eq:hook_prod} |\chi^\lambda(\ell^s)| = \frac{\prod\limits_{\substack{i \in [n] \\ i \equiv_\ell 0}} i} {\prod\limits_{\substack{c \in \lambda \\ h_c \equiv_\ell 0}} h_c} \end{equation} whenever $\lambda$ can be written as $s$ successive ribbons of length $\ell$, and $0$ otherwise. \end{Theorem} We also give the following asymptotic uniform distribution result which largely strengthens \Cref{thm:main}. \begin{Theorem} \label{thm:dist} Let $\lambda \vdash n$ be a partition where $f^\lambda \geq n^5 \geq 1$. Then for all $r$, \[ \left|\frac{a_{\lambda, r}}{f^\lambda} - \frac{1}{n}\right| < \frac{1}{n^2}. \] In particular, if $n \geq 81$, $\lambda_1 < n-7$, and $\lambda_1' < n-7$, then $f^\lambda \geq n^5$ and the inequality holds. \end{Theorem} Indeed, the upper bound in \Cref{thm:dist} is quite weak and is intended only to convey the flavor of the distribution of $(a_{\lambda, r})_{r=0}^{n-1}$ for fixed $\lambda$. One may use Roichman's asymptotic estimate \cite{roichman96} of $|\chi^\lambda(\ell^s)|/f^\lambda$ to prove exponential decay in many cases. Moreover, one typically expects $f^\lambda$ to grow super-exponentially, i.e.~like $(n!)^{\epsilon}$ for some $\epsilon > 0$ (see \cite{ls08} for some discussion and a more recent generalization of Roichman's result), which in turn would give a super-exponential decay rate in \Cref{thm:dist}. We have no need for such refined statements and so have not pursued them further. The rest of the paper is organized as follows. In \Cref{sec:formula} we discuss and generalize \Cref{thm:formula}. In \Cref{sec:thm_proofs}, we use symmetric group character estimates and a new estimate involving ``opposite hook products,'' \Cref{lem:h_op}, to deduce our main results, \Cref{thm:main} and \Cref{thm:dist}. We have omitted proofs from this extended abstract. They will appear in a forthcoming version of this article \cite{swanson16}. \section{Generalizing the Main Formula} \label{sec:formula} Variations on \Cref{thm:formula} have appeared in the literature numerous times in several guises, sometimes implicitly (see \cite[Th\'eor\`eme~2.2]{desarmenien90}, \cite[(7)]{klyachko74}, or \cite[7.88(a), p.~541]{ec2}). In this section we write out a precise and relatively general version of these results which explicitly connects \Cref{thm:formula} to the well-known corresponding symmetric function expansion due to H.~O.~Foulkes. Let $\Ch$ denote the Frobenius characteristic map, and let $p_\lambda$ denote the power symmetric function indexed by the partition $\lambda$. \begin{Theorem}[{\cite[Theorem 1]{foulkes72}}] \label{thm:chir_p} Suppose $\lambda \vdash n \geq 1$ and $r \in \bZ/n$. In this case, \begin{equation} \label{eq:chir_p} \Ch \chi^r\ind_{C_n}^{S_n} = \frac{1}{n} \sum_{\ell \mid n} c_\ell(r) p_{(\ell^{n/\ell})}. \end{equation} \end{Theorem} The following straightforward result connects and generalizes \Cref{thm:chir_p} and \Cref{thm:formula}. \begin{Theorem} \label{thm:ind_mults} Let $H$ be a subgroup of $S_n$, and let $M$ be a finite-dimensional $H$-module with character $\chi^M \colon H \to \bC$. Then \begin{equation} \label{eq:M_p} \Ch M\ind_H^{S_n} = \frac{1}{|H|} \sum_{\mu \vdash n} c_\mu p_\mu \end{equation} and, for all $\lambda \vdash n$, \begin{equation} \label{eq:M_mult} \langle M\ind_H^{S_n}, S^\lambda\rangle = \frac{1}{|H|} \sum_{\mu \vdash n} c_\mu \chi^\lambda(\mu), \end{equation} where \[ c_\mu := \sum_{\substack{h \in H\\\tau(h)=\mu}} \chi^M(h) \] and $\tau(\sigma)$ denotes the cycle type of the permutation $\sigma$. \end{Theorem} \Cref{thm:ind_mults} is an immediate consequence of the induced character formula. Note that \eqref{eq:M_p} specializes to \Cref{thm:chir_p} and \eqref{eq:M_mult} specializes to \Cref{thm:formula} when $M = \chi^r$. In that case, the only possibly non-zero $c_\mu$ arise from $\mu = (\ell^{n/\ell})$ for $\ell \mid n$. One may consider analogues of the counts $a_{\lambda, r}$ obtained by inducing other one-dimensional representations of subgroups of $S_n$. Motivated by the study of so-called higher Lie modules, there is a natural embedding of reflection groups $C_a \wr S_b \hookrightarrow S_{ab}$. A classification analogous to Klyachko's result, \Cref{thm:kly}, was asserted for $b=2$ by Schocker \cite[Theorem 3.4]{schocker03}, though the ``rather lengthy proof'' making ``extensive use of routine applications of the Littlewood-Richardson rule and some well-known results from the theory of plethysms'' was omitted. By contrast, our approach using \Cref{thm:ind_mults} may be pushed through in this case using an appropriate generalization of the Fomin-Lulov bound, \Cref{thm:fl_bound}, such as \cite[Theorem 1.1]{ls08}, resulting in analogues of \Cref{thm:main} and \Cref{thm:dist}. Our approach begins to break down when $b$ is large relative to $n=ab$ and \eqref{eq:M_mult} has many terms. However, we have no current need for such generalizations and so have not pursued them further. \section{Proof of the Main Result} \label{sec:thm_proofs} We now summarize our proof of \Cref{thm:main} and \Cref{thm:dist}. We begin by giving a sufficient condition in terms of upper bounds on symmetric group character ratios, \Cref{lem:phi_d}, which in turn reduces to a sufficient condition in terms of lower bounds on $f^\lambda$, \Cref{cor:n_cubed}. We then give an inequality between hook length products and ``opposite'' hook length products, \Cref{lem:h_op}, from which one can classify $\lambda$ for which $f^\lambda < n^3$. \Cref{thm:main} follows in almost all cases, with the remainder being handled by brute force and case-by-case analysis. \Cref{thm:dist} is similar, except the bound $f^\lambda < n^5$ is used. \begin{Lemma} \label{lem:phi_d} Let $\lambda \vdash n$ and $d \in \bR$. Suppose for all $1 \neq \ell \mid n$ where $\lambda$ may be written as $s := n/\ell$ successive ribbons each of length $\ell$ that \begin{equation} \label{eq:ratio_ub} \frac{|\chi^\lambda(\ell^s)|}{f^\lambda} \leq \frac{1}{n^d \phi(\ell)}. \end{equation} Then for all $r \in \bZ/n$, \[ \left|\frac{a_{\lambda, r}}{f^\lambda} - \frac{1}{n}\right| < \frac{1}{n^d}. \] \end{Lemma} \Cref{lem:phi_d} follows from \Cref{thm:formula}. The following corollary to \Cref{lem:phi_d} follows from \Cref{thm:fl_bound} and Stirling's approximation \cite[(1.53)]{spencer14}. \begin{Corollary} \label{cor:n_cubed} Let $\lambda \vdash n$. If $f^\lambda \geq n^3 \geq 1$, then $a_{\lambda,r} \neq 0$. \end{Corollary} We next summarize techniques that are well-adapted to classifying $\lambda \vdash n$ for which $f^\lambda < n^d$ for fixed $d$. We begin with a curious observation, \Cref{lem:h_op}, which we have not been able to locate in the literature (though contrast it with \cite[Theorem~2.3]{fl95}). \begin{Definition} Consider a partition $\lambda = (\lambda_1, \ldots, \lambda_m)$ with $\lambda_1 \geq \lambda_2 \geq \cdots \geq 0$ as a set of cells \[ \lambda = \{(a, b) \in \bZ \times \bZ : 1 \leq b \leq m, 1 \leq a \leq \lambda_b\}. \] Given a cell $c = (a, b) \in \lambda \subset \bN \times \bN$, the \textit{opposite hook length} $h_c^{\op}$ at $c$ is $a+b-1$. For instance, the unique cell in $\lambda = (1)$ has opposite hook length $1$, and the opposite hook length increases by $1$ for each north or east step (using French notation). \end{Definition} It is easy to see that $\sum_{c \in \lambda} h_c^{\op} = \sum_{c \in \lambda} h_c$. On the other hand, we have the following. \begin{Lemma} \label{lem:h_op} For all partitions $\lambda$, \[ \prod_{c \in \lambda} h_c^{\op} \geq \prod_{c \in \lambda} h_c. \] Moreover, equality holds if and only if $\lambda$ is a rectangle. \end{Lemma} Our proof of \Cref{lem:h_op} involves considering contributions of the (co-)arm and (co-)leg lengths of each cell. It would be interesting to find a more conceptual explanation for \Cref{lem:h_op}, perhaps using representation theory. The appearance of rectangles is particularly striking. Note, however, that $n!/\prod_{c \in \lambda} h_c^{\op}$ need not be an integer. In any case, we continue towards \Cref{thm:main}. \begin{Definition} Define the \textit{diagonal preorder} on partitions as follows. Declare $\lambda \lesssim^{\diag} \mu$ if and only if for all $i \in \bP$, \[ \#\{c \in \lambda : h_c^{\op} \geq i\} \leq \#\{d \in \mu : h_d^{\op} \geq i\}. \] \end{Definition} Note that $\lesssim^{\diag}$ is reflexive and transitive, though not anti-symmetric, so the diagonal preorder is not a partial order. A straightforward consequence of the definition is that \begin{equation} \label{eq:diag_preorder} \lambda \lesssim^{\diag} \mu \qquad \Rightarrow \qquad \prod_{c \in \lambda} h_c^{\op} \leq \prod_{d \in \mu} h_d^{\op}. \end{equation} Hooks are maximal elements of the diagonal preorder in a sense we next make precise. \begin{Definition} \label{def:diagonal_excess} Let $\lambda \vdash n$ for $n \geq 1$. The \textit{diagonal excess} of $\lambda$ is \[ N(\lambda) := |\lambda| - \#\{h_c^{\op} : c \in \lambda\}. \] \end{Definition} \noindent For instance, $\lambda = (3, 3)$ has opposite hook lengths ranging from $1$ to $4$, so $N((3, 3)) = 6 - 4 = 2$. \begin{Example} \label{ex:hook_diagonals} Let $\lambda \vdash n$ be a hook. Consider the sequence $(\#\{c \in \lambda : h_c^{\op} = i\})_{i=1}^\infty$ recording the number of cells with opposite hook lengths $1, 2, 3, \ldots$. This sequence is \[ (1, 2, 2, \ldots, 2, 1, \ldots, 1, 0, 0, \ldots) \] where there are $N(\lambda)$ two's and $n - N(\lambda)$ non-zero entries. In particular, $N(\lambda) + 1 \leq n - N(\lambda)$, i.e.~$2N(\lambda)+1 \leq n$. \end{Example} \begin{Proposition} \label{prop:h_op} Let $\lambda \vdash n$ for $n \geq 1$. Set \begin{equation} \label{eq:N} N := \begin{cases} N(\lambda) & \text{if }2N(\lambda)+1 \leq n \\ \left\lfloor\frac{n-1}{2}\right\rfloor & \text{if }2N(\lambda)+1 > n. \end{cases} \end{equation} Then \begin{equation} \label{eq:diag_hook} \lambda \lesssim^{\diag} (n-N, 1^N). \end{equation} In particular, if $2N(\lambda) + 1 \leq n$, then the hook $(n - N(\lambda), 1^{N(\lambda)})$ is maximal for the diagonal preorder on partitions of size $n$ with diagonal excess $N(\lambda)$. \end{Proposition} Our proof of \Cref{prop:h_op} is algorithmic. Each step of the algorithm goes up in the diagonal preorder and the algorithm terminates at an appropriate hook. The following corollary of \Cref{prop:h_op} and \Cref{lem:h_op} essentially gives a polynomial lower bound on $f^\lambda$ in terms of the diagonal excess. \begin{Corollary} \label{cor:h_op} Let $\lambda \vdash n$ for $n \geq 1$, and take $N$ as in \eqref{eq:N}. For any $0 \leq M \leq N$, we have \begin{equation} \label{eq:h_op_bound} \prod_{c \in \lambda} h_c^{\op} \leq (n-M)! (M+1)!. \end{equation} Indeed, \begin{equation} \label{eq:f_la_binom} f^\lambda \geq \frac{1}{M+1} \binom{n}{M}. \end{equation} \end{Corollary} We now sketch the proof of \Cref{thm:main}, the proof of \Cref{thm:dist} being similar. \Cref{thm:main} follows from \Cref{cor:n_cubed} except when $f^\lambda < n^3$. One may classify these exceptional $\lambda$ using the bound \eqref{eq:f_la_binom} from \Cref{cor:h_op} for $n$ sufficiently large as essentially those $\lambda$ with $N(\lambda) \leq 4$. The result is twelve pairs of infinite families, namely the concatenations $(n-M) \oplus \mu$ for $\mu \vdash M \leq 4$ and their conjugates. For example, one such pair is $\{(n-4, 3, 1)\}$ and its conjugate. The five pairs with $M=4$ all result in $f^\lambda \geq n^3$ for $n \geq 34$. The conclusion of \Cref{thm:main} may be verified by hand for the remaining seven families for $n \geq 15$. One must then verify the conclusion of \Cref{thm:main} for $n \leq 33$, which takes little time on modern computers. \acknowledgements{ The author would like to thank Sheila Sundaram for sharing a preprint of \cite{sundaram16} which motivated the present work. He would also like to thank his advisor, Sara Billey, for her support, insightful comments, and a careful reading of the manuscript; his partner, R.~Andrew Ohana, for numerous fruitful discussions and support, including an early observation which lead to an alternate proof of \Cref{thm:hook}; and Connor Ahlbach for valuable discussions on related work. } \printbibliography \end{document}