# Why does the square root of n! grow exponentially faster than exponential functions?

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al.

In the proof of the theorem $6$ of the paper on page 632, the authors go on proving the difference between the probabilities of sampling all irreps, $|p - q|_1$ of a subgroup inside the symmetric group $S_n$.

\begin{align} |p - q|_1 &= \Sigma_{\rho} \mid p_{\rho} - q_{\rho} \mid \\ &\le \Sigma_{\rho} \frac{d_{\rho}}{n!} 2^{O(n)} \sqrt{n}^{n / 2} \\ &\le \Sigma_{\rho} \frac{\sqrt{n!}}{n!} 2^{O(n)} \sqrt{n}^{n / 2} \\ &\le \frac{2^{O(n)} \sqrt{n}^{n/2}}{\sqrt{n!}} \\ &= 2^{O(n)} \frac{\sqrt{\sqrt{n}^n}} {\sqrt{n!}} \\ &\le 2^{O(n)} \frac{1}{\sqrt{\left( n / 2 \right)!}} \lll 2^{-\Omega(n)} \end{align}

How is $2^{O(n)} \frac{1}{\sqrt{\left( n / 2 \right)!}} \lll 2^{-\Omega(n)}$?

• I strongly object to the haphazard mix of $=$, $\leq$ and $\lll$, whatever the latter is supposed to mean here. There are two components to this: 1) Agreeing on how to read these notation-abusive terms. 2) Showing that one term dominates the other.
– Raphael
Apr 21 '16 at 21:49
• @Raphael, I didn't mixed those symbols. It was from the proof by the authors I was referring to. Apr 21 '16 at 21:50
• This seems to be a purely mathematical question, with no computer science content. Apr 21 '16 at 21:54

Throwing away gutter, this is the claim:

$\qquad\frac{c^n}{\sqrt{(n/2)!}} \to 0$ with at least exponential rate as $n \to \infty$.

That is, the sqare root of $(n/2)!$ grow (at least) exponentially faster than exponential functions.

You can prove this by showing that

$\qquad\frac{c^n}{\sqrt{(n/2)!}} \sim 2^{-g(n)}$ for some $g \in \Omega(n)$.

Use Stirling's approximation.

$\log(n!)=\Theta(n\log n)$, (see Stirling's approximation), hence

$\frac{2^{O(n)}}{\sqrt{\left(\frac{n}{2}\right)!}}=2^{O(n)-\log\sqrt{\left(\frac{n}{2}\right)!}}=2^{O(n)-\Theta(n\log n)}=2^{-\left(\Theta(n\log n)-O(n)\right)}=2^{-\Omega(n)}$.

• Wow.... that is something I think should (can?) not be done with Landau terms.
– Raphael
Apr 21 '16 at 22:04
• Maybe in this context the Landau notation may be unnecessary. Still, I'm gonna leave this here for now (unless OP has any problems). Apr 21 '16 at 22:20

You don't need any approximations. Compare $c^n$ and $(n!)^{1/2}$: As soon as $n > c^2$, $(n!)^{1/2}$ grows exponentially faster because going from n to n+1, one grows by a factor c, and the other by a factor greater than c.