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

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

$\endgroup$
  • $\begingroup$ Are you asking whether $\Omega(n) = \Omega(2n)$, or whether that ansatz is correct? $\endgroup$ – Raphael Apr 21 '16 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$ – Omar Shehab Apr 21 '16 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 Apr 21 '16 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$ – Omar Shehab Apr 21 '16 at 22:09
1
$\begingroup$

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

$\endgroup$
  • 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 Apr 22 '16 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$ – Yuval Filmus Apr 22 '16 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 Apr 22 '16 at 11:02

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.