2 Gowers Hatami theorem

2.1 Preliminaries

Definition 2.1.1 $\sigma $ inner product.

✓

The $\sigma $ inner product between matrices $A$ and $B$ is defined as

\begin{equation} \langle A, B \rangle _{\sigma } = {\rm Tr}(A^* B \sigma ), \end{equation}

where $\sigma \geq 0$ and $A^*$ denotes conjugate-transpose.

Definition 2.1.2 $(\epsilon , \sigma )$-representation.

✓

Given a finite group $G$, an integer $d \geq 1, \varepsilon \geq 0$, and a $d$-dimensional positive semidefinite matrix $\sigma $ with trace 1 , an $(\varepsilon , \sigma )$-representation of $G$ is a map $f: G \rightarrow U_{d}(\mathbb {C})$, to the $d \times d$ unitary matrices, such that

\begin{equation} \mathbb {E}_{x, y \in G} \Re \left(\left\langle f(x)^{*} f(y), f\left(x^{-1} y\right)\right\rangle _{\sigma }\right) \geq 1-\varepsilon , \end{equation}

where $\Re $ denotes taking real part of the inner product.

Proposition 2.1.3

Let $G$ be a finite group, and let $f, f_2 : G \to U(n)$ be functions into the unitary matrices. Then

\[ \mathbb {E}_{x \in G}\| f(x) - f_2(x)\| _\sigma ^2 \le 2\varepsilon \quad \Longleftrightarrow \quad \mathbb {E}_{x \in G} \Re \! \left(\langle f(x), f_2(x)\rangle _\sigma \right) \ge 1 - \varepsilon . \]

Proof ▶

For unitary matrices $A, B$, we have

\begin{equation} \| A- B\| _\sigma ^2 = 2 - 2 \Re \langle A, B \rangle _\sigma . \end{equation}

Since $\mathbb {E}$ is linear, this proves the proposition.

TODO:

Relation to classical BLR test

2.2 Representation theory

Definition 2.2.1 Unitary Representation

A unitary representation of $G$ is a representation to unitary matrices $\rho : G \to U(V)$.

Definition 2.2.2 Regular representation

Let $R: G \rightarrow \mathbb {C}[G]$ be a regular representation where $\{ \mbox{$ | g \rangle $}, g\in G\} $ forms a basis of $\mathbb {C}[G]$. The representation is given by

\begin{equation} R(x) \mbox{$ | g \rangle $} = \mbox{$ | xg \rangle $}. \end{equation}

It is possible to decompose any representation of a finite group into direct sums over irreps.

Theorem 2.2.3 Maschke’s theorem

Let $G$ be a finite group and let $\rho : G \to \mathrm{GL}(V)$ be a finite-dimensional representation over $\mathbb {C}$. Then $\rho $ is completely reducible. In particular, there exists a decomposition

\begin{equation} \rho \cong \bigoplus _{m} r_m \, \rho _m, \end{equation}

where $\{ \rho _m\} $ is a set of inequivalent irreducible representations of $G$, and $r_m \in \mathbb {Z}^+$ are the multiplicities.

Proof ▶

Maschke’s theorem is partially formalized in $\texttt{Mathlib.RepresentationTheory.Maschke}$ but incomplete. Jonathan’s team is formalizing this.

Proposition 2.2.4 Decomposition of the regular representation

Let $R : G \to \mathrm{GL}(\mathbb {C}[G])$ be the regular representation of a finite group $G$. Then

\begin{equation} R \cong \bigoplus _{\rho \in \widehat{G}} d_\rho \, \rho , \end{equation}

where $\widehat{G}$ is a complete set of inequivalent irreducible representations of $G$, and $d_\rho = \dim (V_\rho )$ is the dimension of $\rho $.

Proof ▶

This can be proven using Maschke’s theorem in 2.2.3 to decompose into irreps with multiplicity. Then use character orthogonality theorem in mathlib $\texttt{FDRep.char\_ orthonormal}$ to show the multiplicity equals irrep dimension. A more formal statement is given by the Peter-Weyl theorem.

Proposition 2.2.5 Character of regular representation.

Let $G$ be a finite group and $\sum _\rho $ denotes summing over the complete set of inequivalent irreps $\hat{G}$

\begin{equation} \label{eq:regular_repr_characterr} \sum _{\rho \in \hat{G}} d_{\rho } \operatorname {Tr}(\rho (x))=|G| \delta _{x, e}. \end{equation}

Proof ▶

The proof uses decomposition of regular representation and definition of character.

Definition 2.2.6 Group fourier transform

Let $f: G \rightarrow U_d(\mathbb {C})$ be a map and $\rho : G \rightarrow U_{d_{\rho }}(\mathbb {C})$ be a unitary irrep. The fourier transform of $f$ at the representation $\rho $ is denoted by $\hat{f}$:

\begin{equation} \hat{f}(\rho )=\mathbb {E}_{x \in G} f(x) \otimes \overline{\rho (x)}, \end{equation}

where $\overline{\rho (x)}$ denotes complex conjugate of $\rho (x)$.

2.3 Gowers Hatami Theorem

Theorem 2.3.1 Gowers-Hatami

Let $G$ be a finite group, $\varepsilon \geq 0$, and $f: G \rightarrow U_{d}(\mathbb {C})$ an $(\varepsilon , \sigma )$-representation of $G$. Then there exists a $d^{\prime } \geq d$, an isometry $V: \mathbb {C}^{d} \rightarrow \mathbb {C}^{d^{\prime }}$, and a representation $g: G \rightarrow U_{d^{\prime }}(\mathbb {C})$ such that

\begin{equation} \mathbb {E}_{x \in G}\left\| f(x)-V^{*} g(x) V\right\| _{\sigma }^{2} \leq 2 \varepsilon . \end{equation}

Proof ▶

The full proof can be found in the lecture notes Theorem 2.3 [ . In particular, the proof is constructive. The isometry is defined as $V: \mathbb {C}^{d} \rightarrow \mathbb {C}^{d} \otimes \left(\oplus _{\rho } \mathbb {C}^{d_{\rho }} \otimes \mathbb {C}^{d_{\rho }}\right)$ by

\begin{equation} \label{eq:isometry_V} V u = \bigoplus _{\rho } d_{\rho }^{1 / 2} \sum _{i=1}^{d_{\rho }}\left(\hat{f}(\rho )\left(u \otimes e_{i}\right)\right) \otimes e_{i}. \end{equation}

And the exact representation is defined as

\begin{equation} g(x)=\bigoplus _{\rho }\left(I_{d} \otimes I_{d_{\rho }} \otimes \rho (x)\right). \end{equation}

The proof requires the following two ingredients:

$V$ is an isometry:

\begin{equation} V^{*} V = \mathbb {I}_d \end{equation}
12
The isometry “averages” over group multiplication. For any $x \in G$,

\begin{equation} V^{*} g(x) V = \mathbb {E}_{z} f(z)^{*} f(z x). \end{equation}
13

Both ingredients follow from the key identity over the regular representation in Eq. ??.

Theorem 2.3.2 Gowers-Hatami-2

Let $G$ be a finite group, $\varepsilon \geq 0$, and $\rho : G \rightarrow U(\mathcal{H})$ an $(\varepsilon , \sigma )$-representation of $G$ on space $\mathcal{H}=\mathbb {C}^{d}$. Then there exists an isometry $V: \mathcal{H} \rightarrow \mathcal{H}^\prime $ to a different space $\mathcal{H}^\prime $, and a representation $\rho ^\prime : G \rightarrow \mathcal{H}^\prime $ such that

\begin{equation} \mathbb {E}_{x \in G}\left\| \rho (x)-V^{*} \rho ^\prime (x) V\right\| _{\sigma }^{2} \leq 2 \varepsilon . \end{equation}

Proof ▶

A different proof of the Gowers-Hatami theorem is given in M. de la Salle’s notes [ . Here $\mathcal{H}^\prime = L(G, \mathcal{H})$ is the space of functions $f: G \to \mathcal{H}$. The isometry is given by the action of the approximate representation on a state $u\in \mathcal{H}$ as

\begin{eqnarray} & V:& \mathcal{H} \to L(G, \mathcal{H}), \\ & V(u):& G \to \mathcal{H}, \quad x \mapsto \rho (x)(u), \forall x \in G. \end{eqnarray}

The inverse map $V^*$ is given by the group average

\begin{eqnarray} & V^*:& L(G, \mathcal{H}) \to \mathcal{H}, \\ & V^*(f)& = \mathbb {E}_{x \in G} \left[ \rho ^*(x) f(x) \right]. \end{eqnarray}

The exact representation is given by the right regular representation on $L(G, \mathcal{H})$:

\begin{eqnarray} & \rho ^\prime :& G \to \mathrm{End}(L(G, \mathcal{H})), \\ & (\rho ^\prime (x)f)(y)& = f(yx), \quad \forall x,y \in G. \end{eqnarray}

$V$ is an isometry because

\begin{equation} V^* V(u) = \mathbb {E}_{x \in G} \left[ \rho ^*(x) \rho (x)(u) \right] = u. \end{equation}

The isometry “averages” over group multiplication because

\begin{eqnarray} \label{eq:isometry_average} V^* \rho ^\prime (x) V(u) & = & \mathbb {E}_{y \in G} \left[ \rho ^*(y) (\rho ^\prime (x)\rho (y))(u) \right] \\ & = & \mathbb {E}_{y \in G} \left[ \rho ^*(y) (\rho (yx)(u)) \right].\nonumber \end{eqnarray}

The rest of the proof follows by expanding the $\sigma $-norm, bounding the norm of $\mathbb {E}_{x \in G} V^* \rho ^\prime (x) V$ and applying the definition of $(\varepsilon , \sigma )$-representation. In particular, we have

\begin{eqnarray} & & \mathbb {E}_{x \in G}\left\| \rho (x)-V^{*} \rho ^\prime (x) V\right\| _{\sigma }^{2} \\ & = & \mathbb {E}_{x \in G} \| \rho (x) \| _\sigma ^2 + \mathbb {E}_{x \in G} \| V^* \rho ^\prime (x) V\| _\sigma ^2 - 2 \mathbb {E}_{x \in G} \Re \langle \rho (x), V^* \rho ^\prime (x) V\rangle _\sigma \nonumber \end{eqnarray}

Because $\rho $ is unitary, $\mathbb {E}_{x \in G} \| \rho (x) \| _\sigma ^2 = 1$. For the second term, since $\rho ^\prime $ is unitary and $V$ is an isometry,

\begin{eqnarray} & & \mathbb {E}_{x \in G} \| V^* \rho ^\prime (x) V\| _\sigma ^2 \\ & = & \mathbb {E}_{x \in G} {\rm Tr}\left[V^* \rho ^{\prime *}(x) V V^* \rho ^\prime (x) V \sigma \right] \nonumber \\ & = & \mathbb {E}_{x, y, z \in G} {\rm Tr}\left[\rho ^*(yx)\rho (y) \rho ^*(z) \rho (zx) \sigma \right] \nonumber \end{eqnarray}

Because $\rho $ is unitary the product $U(x, y, z) := \rho ^*(yx)\rho (y) \rho ^*(z) \rho (zx)$ is again a unitary operator, the above expression is upper bounded by Holder’s inequality as

\begin{eqnarray} \label{eq:isometry_unitary_bound} & & \mathbb {E}_{x, y, z \in G} {\rm Tr}\left[U(x, y, z) \sigma \right] \\ \nonumber & \le & \mathbb {E}_{x, y, z \in G} \| U(x, y, z)\| _\infty \| \sigma \| _1 = 1. \end{eqnarray}

Finally, using the isometry average property in Eq. ?? and the definition of $(\varepsilon , \sigma )$-representation, we have

\begin{eqnarray} \label{eq:inner_product_bound} & & \mathbb {E}_{x \in G} \Re \langle \rho (x), V^* \rho ^\prime (x) V\rangle _\sigma , \\ \nonumber & = & \mathbb {E}_{x,y \in G} \Re \langle \rho (x), \rho ^*(y) \rho (yx) \rangle _\sigma , \\ \nonumber & \ge & 1 - \varepsilon . \end{eqnarray}

Therefore using the bounds in Eq. ?? and Eq. ??, we have

\begin{equation} \mathbb {E}_{x \in G}\left\| \rho (x)-V^{*} \rho ^\prime (x) V\right\| _{\sigma }^{2} \le 2 - 2(1 - \varepsilon ) = 2\varepsilon . \end{equation}

This completes the proof.