5
$\begingroup$

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)}$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Apr 21 '16 at 21:49
  • 1
    $\begingroup$ @Raphael, I didn't mixed those symbols. It was from the proof by the authors I was referring to. $\endgroup$ – Omar Shehab Apr 21 '16 at 21:50
  • 5
    $\begingroup$ This seems to be a purely mathematical question, with no computer science content. $\endgroup$ – David Richerby Apr 21 '16 at 21:54
9
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

$\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)}$.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.