# Intuition for failure of strong Fourier sampling for the symmetric group

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?

• You might get some intuition from Moore’s presentation here. Commented Oct 19, 2023 at 1:24
• Awesome, thank you. Commented Oct 20, 2023 at 18:05