\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.58}{22(2)}{2015}

\usepackage{amsmath, amsthm, amssymb, tikz}
\usepackage{amsfonts}
%\usepackage{fullpage}
%\usepackage[enableskew]{youngtab}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\newcommand\beq{\begin{equation}}
\newcommand\eeq{\end{equation}}
\newcommand\bce{\begin{center}}
\newcommand\ece{\end{center}}
\newcommand\bea{\begin{eqnarray}}
\newcommand\eea{\end{eqnarray}}
\newcommand\ba{\begin{array}}
\newcommand\ea{\end{array}}
\newcommand\ben{\begin{enumerate}}
\newcommand\een{\end{enumerate}}
\newcommand\bit{\begin{itemize}}
\newcommand\eit{\end{itemize}}
\newcommand\brr{\begin{array}}
\newcommand\err{\end{array}}
\newcommand\bt{\begin{tabular}}
\newcommand\et{\end{tabular}}
\newcommand\nin{\noindent}
\newcommand\nn{\nonumber}
\newcommand\bs{\bigskip}
\newcommand\ms{\medskip}
\newcommand\ul{\underline}
\newcommand\ol{\overline}
\renewcommand\S{{\mathcal S}}
\newcommand\s{{\tt S}}
\newcommand\U{{\mathcal U}}
\newcommand\A{{\mathcal A}}
\newcommand\LL{{\mathcal L}}
\newcommand\Z{{\mathcal Z}}
\newcommand\T{{\mathcal T}}
\newcommand\G{{\mathcal G}}
\newcommand\LLL{{\mathcal Y}}
\newcommand\Sh{\G^{+^2}}
\newcommand\Shnj{{\mathcal Sh}_{n,j}}
%\DeclareMathOperator\Sh{Sh}
\DeclareMathOperator\maj{maj} \DeclareMathOperator\SYT{SYT}
\DeclareMathOperator\RSK{RSK}
\newcommand\x{{\mathbf x}}
\newcommand\ten{10}
\newcommand\eleven{11}
\newcommand\twelve{12}
\newcommand\blank{$ $}
\newcommand\hs{\hspace{2.6mm}}
\newcommand{\W}{{\rm{Weak}}}
\DeclareMathOperator\shape{shape}
\newcommand\ddom{{d_{\rm{dom}}}}
\newcommand\dXn{{d_{X_n}}}

\newcommand{\bbn}{\mathbb{N}}
\newcommand{\bbz}{\mathbb{Z}}
\newcommand{\bbq}{\mathbb{Q}}
\newcommand{\bbr}{\mathbb{R}}
\newcommand{\bbs}{\mathbb{S}}

\newcommand{\la}{\lambda}

\newcommand{\sym}{\mathfrak{S}}
\newcommand{\alt}{\mathfrak{A}}
\newcommand{\Sup}{{\rm{Supp}}}
\newcommand{\Sip}{A}
\DeclareMathOperator\sign{sign}
\newcommand{\Tr}{{\rm{Tr}}}
\newcommand{\tA}{{\widetilde{A}}}
\newcommand{\tC}{{\widetilde{C}}}
\newcommand{\diam}{{\rm{Diam}}}
\DeclareMathOperator\Des{Des} \DeclareMathOperator\des{des}
\DeclareMathOperator\cdes{cdes}
\newcommand{\invol}{\varphi}
\newcommand{\WW}{{\mathcal W}}
\newcommand\vv{\mathbf{v}}
\newcommand{\ww}{\mathbf{w}}
\newcommand{\enc}{\nu}

\newcommand{\forsingle}{\diagup}
\newcommand{\fordouble}{\diagup}
\newcommand{\backsingle}{\diagdown}
\newcommand{\backdouble}{\diagdown}
\newcommand{\vertsingle}{\vert}
\newcommand{\vertdouble}{\vert}
\newcommand{\horsingle}{-}
\newcommand{\hordouble}{-}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\sphere}{\mathbb{S}}

\newcommand{\BBB}{{\mathcal{B}}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\ch}{\operatorname{ch}}



\title{\bf On exponential growth of degrees}

\author{Yuval Roichman\\
\small Department of Mathematics\\[-0.8ex]
\small Bar-Ilan University\\[-0.8ex]
\small  Ramat-Gan 52900, Israel\\
\small\tt yuvalr@math.biu.ac.il}

\date{\dateline{May 4, 2015}{Jun 1, 2015}{Jun 22, 2015}}

\begin{document}

\maketitle

\begin{abstract}
A short proof to a recent theorem of Giambruno and Mishchenko is
given in this note.
\end{abstract}

\section{The theorem}

The following theorem was recently proved by Giambruno and
Mishchenko.

\begin{theorem}{{\cite[Theorem 1]{GM}}}\label{main}
For every $0<\alpha<1$, there exist $\beta>1$ and $n_0\in \NN$,
such that for every partition $\la$ of $n\ge n_0$ with
$\max\{\la_1,\la'_1\}<\alpha n$
\[
f^\la\ge \beta^n .
\]
\end{theorem}

The proof of Giambruno and Mishchenko is rather complicated and
applies a clever order on the cells of the Young diagram. It
should be noted that Theorem~\ref{main} is an immediate
consequence of Rasala's lower bounds on minimal
degrees~\cite[Theorems F and H]{Rasala}. The proof of Rasala is
very different and not less complicated; it relies heavily on his
theory of degree polynomials. In this short note we suggest a
short and relatively simple proof to Theorem~\ref{main}.

\bigskip

%Here we suggest a short proof of the theorem.
First, note that the following weak version is an immediate
consequence of the hook-length formula.

\begin{lemma}\label{lemma0}
The theorem holds for every $0<\alpha< \frac{1}{2e}$.
\end{lemma}

\begin{proof}
Under the assumption, for every $(i,j)\in [\la]$
\[
h_{i,j}\le h_{1,1}\le \la_1+\la_1'\le 2\alpha {n}.
\]
Hence, by the hook-length formula together with Stirling's
formula, for sufficiently large $n$
\[
f^\la={n!\over \prod\limits_{(i,j)\in [\la]}h_{i,j}}\ge {n!\over
({2\alpha n})^n}\ge {({n\over e})^n\over ({2\alpha n})^n}
%=({1\over 2e\alpha})^n
=\beta^n,
\]
where, by assumption, $\beta:={1\over 2e\alpha}>1$.
\end{proof}

\section{Two lemmas}

\begin{lemma}\label{lemma1}
For every $\la\vdash n$
\[
\prod\limits_{(i,j)\in [\la]\atop 1<i}h_{ij}\le (n-\la_1)!
\]
\end{lemma}

\begin{proof}
For $\la=(\la_1,\la_2,\dots,\la_t)\vdash n$ let
$\bar\la:=(\la_2,\dots,\la_t)\vdash n-\la_1$. Then
\[
1\le f^{\bar\la}={(n-\la_1)!\over \prod\limits_{(i,j)\in
[\la]\atop 1<i}h_{ij}}.
\]
\end{proof}

\begin{lemma}\label{lemma2}
For every $\la\vdash n$ and $1\le k\le \la_1$,
\[
\prod\limits_{(1,j)\in [\la]}h_{1j} \le {n\choose k}
\left(\la_1+\left\lfloor {n-\la_1\over k}\right\rfloor\right)! .
\]
\end{lemma}

\begin{proof}
%For every $1\le j<\la_1$, $h_{1,j}>h_{1,j+1}$.
Obviously, $h_{1,1}>h_{1,2}>\cdots>h_{1,\la_1}$. Since $h_{1,1}\le
n$ it follows that
\[
\prod\limits_{(1,j)\in [\la]\atop j\le k}h_{1j}\le (n)_k
\]
and
\[
\prod\limits_{(1,j)\in [\la]\atop k<j}h_{1j}\le
(h_{1,k})_{\la_1-k}.
\]
To complete the proof, notice that, by definition,
$\sum\limits_{i=1}^k \bar\la_i'\le n-\la_1$. Hence $\bar\la'_k\le
\lfloor {n-\la_1\over k}\rfloor$ and thus
\[
h_{1,k}=\la_1-k+\la'_k=\la_1-k+1+\bar\la_k'\le \la_1+\bar\la_k'\le
\la_1+\left\lfloor {n-\la_1\over k}\right\rfloor.
\]
We conclude that
\[
\prod\limits_{(1,j)\in [\la]\atop k<j}h_{1j}\le
(h_{1,k})_{\la_1-k}\le \left(\la_1+\left\lfloor{n-\la_1\over
k}\right\rfloor\right)_{\la_1-k}={(\la_1+\lfloor{n-\la_1\over k}\rfloor)!\over
(\lfloor{n-\la_1\over k}\rfloor+k)!}\le
{(\la_1+\lfloor{n-\la_1\over k}\rfloor)!\over k!}.
\]
Thus
\[
\prod\limits_{(1,j)\in [\la]}h_{1j}=\prod\limits_{(1,j)\in
[\la]\atop j\le k}h_{1j}\prod\limits_{(1,j)\in [\la]\atop
k<j}h_{1j} \le (n)_k {\la_1+\lfloor{n-\la_1\over k}\rfloor!\over
k!}= {n\choose k} \left(\la_1+\left\lfloor{n-\la_1\over k}\right\rfloor\right)!.
\]


\end{proof}

\section{Proof of Theorem~\ref{main}}

For the sake of simplicity the floor notation is omitted in this
section.

\bigskip

By Lemmas~\ref{lemma1} and~\ref{lemma2},
\begin{align*}
f^\la={n!\over \prod\limits_{(i,j)\in [\la]}h_{ij}}={n!\over
\prod\limits_{(1,j)\in [\la]}h_{1j}\prod\limits_{(i,j)\in
[\la]\atop 1<i}h_{ij}} &\ge {n!\over (n-\la_1)!{n\choose k} (\la_1+
{n-\la_1\over k})!} \\ &= {(n-k)!k!\over (n-\la_1)!
(\la_1+{n-\la_1\over k})!}.
\end{align*}
Denote $\gamma_n:={\la_1\over n}$. By Lemma~\ref{lemma0}, we may
assume that ${1\over 2e} < \gamma_n <\alpha$. Choose $k=\epsilon
n$ for a constant $\epsilon=\epsilon(\alpha)$ to be defined later.
Let $c_n:={1-\gamma_n\over \epsilon}$. Thus, by definition,
${1-\alpha\over \epsilon}<c_n<{2e-1\over 2e \epsilon}$. By the
Stirling's formula, the lower bound in the RHS asymptotically
equals to
\[
{((1-\epsilon)n)!(\epsilon n)! \over ((1-\gamma_n)n)! (\gamma_n
n+{1-\gamma_n\over \epsilon})!}\sim
\sqrt{\epsilon(1-\epsilon)\over (1-\gamma_n)(\gamma_n+{c_n\over
n})} \cdot {(1-\epsilon)^{(1-\epsilon)n}\epsilon^{\epsilon n}
\over (1-\gamma_n)^{(1-\gamma_n)n} (\gamma_n+{c_n\over
n})^{(\gamma_n+{c_n\over n})n}}\cdot \left(\frac{e}{n}\right)^{c_n}.
\]
%where $c_n:={1-\gamma_n\over \epsilon}$. Thus ${1-\alpha\over \epsilon}<c_n<{2e-1\over 2e \epsilon}$.
%%\bigskip
Hence, for sufficiently large $n$ %and appropriate $\epsilon$
\begin{align*}
& \lim_{n \rightarrow \infty} \inf (f^\la)^{1/n} \\
& \ge \lim_{n
\rightarrow \infty} \inf \left(\sqrt{\epsilon(1-\epsilon)\over
(1-\gamma_n)(\gamma_n+{c_n\over n})} \cdot
{(1-\epsilon)^{(1-\epsilon)n}\epsilon^{\epsilon n} \over
(1-\gamma_n)^{(1-\gamma_n)n} (\gamma_n+{c_n\over
n})^{(\gamma_n+{c_n\over n})n}}\cdot \left(\frac{e}{n}\right)^{c_n}\right)^{1/n}\\
&= \lim_{n \rightarrow \infty} \inf
{\epsilon^\epsilon(1-\epsilon)^{1-\epsilon}\over
\gamma_n^{\gamma_n} (1-\gamma_n)^{1-\gamma_n}}.
%\ge \min_{\gamma\in [{1\over 2e},\alpha]}{\epsilon^\epsilon(1-\epsilon)^{1-\epsilon}\over \gamma_n^{\gamma}(1-\gamma)^{1-\gamma} }.
\end{align*}
The function $f(x):=x^x (1-x)^{1-x}$ is differentiable in the open
interval $(0,1)$, symmetric around its minimum at $x={1\over 2}$,
decreasing in $(0,{1\over 2}]$, increasing in $[{1\over 2}, 1)$,
strictly less than 1 in this interval and tends to 1 at the
boundaries. Thus, for every $0<1-\beta\le x\le \beta<1$, $f(x)\le
f(\beta)=f(1-\beta)$.

\smallskip

Now, if $1-{1\over 2e}> \alpha$ then ${1\over 2e}<\gamma_n<\alpha<
1-{1\over 2e}$; hence $f(\gamma_n)< f(1-{1\over 2e})=f({1\over
2e})$. If $1-{1\over 2e}\le \alpha$ then $1-\alpha\le {1\over
2e}<\gamma_n<\alpha$; hence $f(\gamma_n)< f(\alpha)$.
%Since $\gamma_n\in ({1\over 2e},\alpha)\subseteq (0,1)$ it follows that $f(\gamma_n)\le f(\alpha)$ if $1-{1\over 2e}\le \alpha$ and $f(\gamma_n)\le f({1\over 2e})$ otherwise.
%%\[
%%\gamma_n^{\gamma_n}
%%(1-\gamma_n)^{1-\gamma_n}\le \alpha^\alpha (1-\alpha)^{1-\alpha}
%%\]
%\[
%f(\gamma_n)\le \max\{f({1\over 2e}), f(\alpha)\}
%\]
%Hence,
It follows that
\[
\lim_{n \rightarrow \infty} \inf (f^\la)^{1/n}\ge \lim_{n
\rightarrow \infty} \inf {f(\epsilon)\over f(\gamma_n)}>
\begin{cases}
{f(\epsilon)\over f(\alpha)},& 1-{1\over 2e}\le \alpha;\\
{f(\epsilon)\over f({1\over 2e})}, & \text{ otherwise. }
\end{cases}
%\ge {f(\epsilon)\over \max_{\gamma_n\in ({1\over
%2e},\alpha)}f(\gamma_n)}\ge {f(\epsilon)\over \max\{f({1\over 2e}),f(\alpha)\}}.
\]
Choosing %$\epsilon=\epsilon(\alpha)$ such that
$\epsilon:=
\delta\min\{1-\alpha,{1\over 2e}\}$ for some %very small
$0<\delta<1$ we conclude that
\[
\lim_{n \rightarrow \infty} \inf (f^\la)^{1/n}>
%%\min_{\gamma\in [{1\over 2e},\alpha]}{\epsilon^\epsilon(1-\epsilon)^{1-\epsilon}\over
%%\gamma^{\gamma} (1-\gamma)^{1-\gamma} } \ge
%\min\{ {f(\delta{1\over 2e})\over f({1\over 2e})},  {f(\delta (1-\alpha))\over f(1-\alpha)}\}
\begin{cases}
\frac{f(\delta(1-\alpha))}{f(\alpha)}=\frac{f(\delta(1-\alpha))}{f(1-\alpha)},& 1-\alpha\le \frac{1}{2e};\\[1ex]
\frac{f(\frac{\delta}{2e})}{ f(\frac{1}{2e})}, & \text{ otherwise. }
\end{cases}
%>1,
\]
Since the function $f$ is strictly decreasing in $(0,{1\over
2e}]$, the lower bound is greater than 1. The proof is complete.

\qed

%\bigskip

%\begin{remark}
%A careful analysis of the above proof shows that
%$(f^\la)^{1/n}>\beta$ for every $\beta<{1\over \alpha^\alpha
%(1-\alpha)^{1-\alpha}}$. This slightly improves the bound
%$\beta<{1\over \alpha}$ of~\cite{GM}.
%\end{remark}

\subsection*{Acknowledgements}
%\noindent{\bf Acknowledgements.}
Thanks to Amitai Regev for fruitful discussions and references.
Thanks also to Ron Adin, Nathan Keller  and the anonymous referee
for their comments.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{10}

\bibitem{GM} A.
Giambruno and S. Mishchenko, \newblock Irreducible characters of
the symmetric group and exponential growth. \arxiv{1406.1653}

\bibitem{Rasala} R.\ Rasala, \newblock On the minimal degrees of characters of $S_n$. \newblock {\em  J. Algebra}, 45:132--181,
1977.

\end{thebibliography}

\end{document}