I am trying to read and understand the following two papers:
The Symmetric Group Defies Strong Fourier Sampling: Part I
The Symmetric Group Defies Strong Fourier Sampling: Part II
I have a pretty good understanding of representations of the symmetric group and the Fourier transform for non-abelian groups, in particular $S_n$.
I'd like to understand Theorem 8 of part I. The key estimates seem to come from bounding the expectation and variance as $m$ varies over the set of all involutions in eq. 4.1 and eq. 4.2 on pg. 9.
$$\displaystyle \Pi_m \textbf{v}=\frac{\textbf{v}+m\textbf{v}}{2}$$ $$P_m(\textbf{b})=P(S^\lambda,\textbf{b})=\frac{||\Pi_m\textbf{b}||^2}{\textbf{rk}\,\Pi_m}$$
where $\textbf{b}$ is a vector in an orthonormal basis $B$ of an irreducible representation $S^\lambda$.
The theorem states that $||P_m-U||_1 < e^{-\delta n}$ where $U$ is the uniform distribution.
So essentially, if we're looking for the hidden subgroup $\{1,m\}$, we first measure the irrep $\lambda$, then we want to measure a column vector of a the matrix $\rho_\lambda$, but the distribution on $\textbf{b}$ is so close to uniform that we really learn much from one measurement - we need an exponential number.
I guess I'm wondering why this happens for the symmetric group? Is it the structure of the representations, like how their dimension varies over $\lambda$? I mean, there are a lot of irreps, but also their dimensions get pretty big as well. I don't know what goes on for other groups, but is there something uniquely difficult about the symmetric group? I believe it fails for the dihedral group as well. Are there any groups for which strong Fourier sampling does work?
