## 2B Exercise 5: Convolutions

This exercise asks us to prove that if $P$ is a probability measure on the finite group $G$, then $P \star \bar{P} = U$ if and only if $P = U$. Here $\star$ is the convolution product, $U$ is the uniform probability on $G$ defined by $U(s) = 1/|G|$ for all $s \in G$ and $\bar{P}$ is defined by $\bar{P}(s) = P(s^{-1})$.

The if’ direction is easy: just note that $\bar{U} = U$ and $U \star U = U$.

The only if’ direction is a bit harder, and has a nice solution using the Fourier setup. The Fourier transform of $\bar{P}$ at the representation $\rho$ is

$\hat{\bar{P}}(\rho) = \sum_{s \in G} P(s^{-1}) \rho(s) = \sum_{s \in G} P(s) \rho(s^{-1})$.

If $\rho$ is unitary, then $\rho(s^{-1}) = \rho(s)^\star$ for all $s \in G$ (where $X^\star$ is the transposed complex conjugate of the matrix $X$). Hence

$\hat{\bar{P}}(\rho) = \hat{P}(\rho)^\star$.

Hence, taking the Fourier transform of $P \star \bar{P} = U$ at a non-trivial unitary irreducible representation $\rho$, we get

$\hat{P}(\rho) \hat{P}(\rho)^\star = \hat{U}(\rho) = 0$.

But if $X$ is a complex matrix such that $X X^\star = 0$ then $X = 0$. So we’ve shown that $\hat{P}(\rho) = 0$ for all unitary irreducible representations $\rho$. Moreover, since $P$ is a probability measure,

$\hat{P}(1) = \sum_{s \in G} P(s) = 1$.

So the Fourier transform of $P$ agrees with the Fourier transform of $U$ on all unitary irreducible representations. Any representation is equivalent to a direct sum of such representations, so by the Fourier Inversion Theorem, $P = U$.

### One Response to 2B Exercise 5: Convolutions

1. mwildon says:

I’m adding this comment to record a simpler way to do the exercise, suggested by Jon Barrett.

From $P \star \bar{P} = U$ we have

$\sum_{s \in G} P(s) P(g^{-1}s) = \frac{1}{|G|}$

for all $g \in G$. Putting $g=1$ gives

$\sum_{s \in G} P(s)^2 = \frac{1}{|G|}$.

The Cauchy–Schwarz inequality applied to the dot-product of the all ones vector and the vector with entries $P(s)$ for $s \in G$ shows that

$|G| \sum_{s \in G}P(s)^2 \ge \Bigl( \sum_{s\in G}P(s) \Bigr)^2 = 1.$

So we have equality in the Cauchy–Schwarz inequality, and so all the $P(s)$ must be equal.