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$.

enter image description here

I want to compute the same bound for the symmetric group $S_{2 n}$. Should I just replace the $n$ in $2^{-\Omega(n)}$ and make it $2^{-\Omega(2n)} = 2^{-\Omega(n)}$?

Or, do I have to work it out from the scratch as follows?

$$ | p - q|_1 = \sum_\rho | p_\rho - q_\rho| \nonumber\\ \le \sum_\rho \frac{d_\rho}{\left(2 n\right)!} 2^{O\left( n\right)} n^{\frac{n}{2}} \nonumber\\ \le \sum_\rho \frac{\sqrt{\left(2n\right)!}}{\left(2 n\right)!} 2^{O\left( n\right)} n^{\frac{n}{2}} \nonumber\\ \le \frac{2^{O\left( n\right)} n^{\frac{n}{2}}}{\sqrt{\left(2 n\right)!}} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{n}{2}}\sqrt{\left(2 n\right)!}}{\sqrt{\left(2 n\right)!}\sqrt{\left(2 n\right)!}} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{n}{2}}\sqrt{\left(2 n\right)!}}{\left(2 n\right)!} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{n}{2}}\sqrt{\left(2 n\right)^{2n}}}{\left(2 n\right)!} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{n}{2}}\left(2 n\right)^{n}}{\left(2 n\right)!} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{n}{2}}n^{n}}{\left(2 n\right)!} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{3n}{2}}}{\left(2 n\right)!} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{3n}{2}}}{\left(2 n\right)^{\left(2 n\right)}} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{3n}{2}}}{ n^{2 n}} \nonumber\\ = \frac{2^{O\left( n\right)} }{ n^{\frac{n}{2}}} \nonumber\\ = \frac{2^{O\left( n\right)} }{ 2^{-\frac{n}{2}} n^{\frac{n}{2}}} \nonumber\\ = \frac{2^{O\left( n\right)} }{ \frac{n}{2}^{\frac{n}{2}}} \nonumber\\ \le \frac{2^{O\left( n\right)} }{ \left(\frac{n}{2}\right)!} \nonumber\\ \lll 2^{-\Omega \left(n\right)} $$

  • $\begingroup$ Are you asking whether $\Omega(n) = \Omega(2n)$, or whether that ansatz is correct? $\endgroup$
    – Raphael
    Commented Apr 21, 2016 at 21:55
  • $\begingroup$ @Raphael, I know that $\Omega(n) = \Omega(2n)$. I would like to know if I can just put this in the asymptotic bound or I have to prove it from the scratch when $n$ is replaced by $2 n$. $\endgroup$ Commented Apr 21, 2016 at 21:57
  • $\begingroup$ The provided bound ignores exponential terms, so I don't think you'll gain anything by moving from $n$ to $2n$. $\endgroup$
    – Raphael
    Commented Apr 21, 2016 at 22:07
  • $\begingroup$ @Raphael, that's correct. But in my case, the input symmetric group is $S_{2n}$. So, I have to determine the bound for $2 n$. $\endgroup$ Commented Apr 21, 2016 at 22:09

1 Answer 1


In mathematics we have the substitution principle. If a certain statement is true, then it also holds if you replace all occurrences of $n$ by some other expression, as long as that other expression has the same type as $n$. In particular, you can substitute $2n$ for $n$ and deduce that $|p-q|_1 \lll 2^{-\Omega(2n)}$. You can then conclude that $|p-q|_1 \lll 2^{-\Omega(n)}$, using the definition of $\Omega$.

  • 1
    $\begingroup$ That can not possible hold for all statements. Take "$n$ is even", for instance. Flat (in)equalities should work out, though. I'm wary about equations involving Landau terms, though, since e.g. $(n-1)! \in o(n!)$, so one side of an "equality" may "simplify" (e.g. $2^{n-1} \in \Theta(2^n)$) but the other not. $\endgroup$
    – Raphael
    Commented Apr 22, 2016 at 9:36
  • $\begingroup$ That's right, if the (universally quantified) statement "$n$ is even" were true, so would "$n+1$ is even". For the proof, see here: mathoverflow.net/questions/14137/…. $\endgroup$ Commented Apr 22, 2016 at 9:39
  • $\begingroup$ Oh dear, my bad for commenting before breakfast. :D My concern about Landau terms stand, though. Maybe they are unfounded. $\endgroup$
    – Raphael
    Commented Apr 22, 2016 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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