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)}$?
Asked By : Omar Shehab
Answered By : Raphael
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/56318
0 comments:
Post a Comment
Let us know your responses and feedback