# Replacing n with 2n in asymptotic bounds

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

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

• Are you asking whether $\Omega(n) = \Omega(2n)$, or whether that ansatz is correct? Commented Apr 21, 2016 at 21:55
• @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$. Commented Apr 21, 2016 at 21:57
• The provided bound ignores exponential terms, so I don't think you'll gain anything by moving from $n$ to $2n$. Commented Apr 21, 2016 at 22:07
• @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$. Commented Apr 21, 2016 at 22:09

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$.
• 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. Commented Apr 22, 2016 at 9:36
• 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/…. Commented Apr 22, 2016 at 9:39