Non-abelian additive combinatorics

Non-abelian additive combinatorics studies product sets and configuration counts in noncommutative groups. Fourier analysis on a finite group and quasirandom groups connect small-dimensional group representations with multiplicative mixing.

For $f:G\to M_n(\mathbb{C})$ on a finite group, use uniform expectation over the solutions of $x{y}^{-1}z{w}^{-1}=e$ and the ordinary, unnormalized trace to define the displayed fourth-order quantity. If $T_{\rho }$ is its matrix Fourier block, this quantity equals ${\sum }_{\rho }{d}_{\rho }\mathrm{Tr}((T_{\rho }{T}_{\rho }^{\ast }{)}^2)$, so it is real and nonnegative. For a scalar function on an abelian group, it reduces to the usual fourth power of the Gowers uniformity norm of order two. The unnormalized trace means a unitary matrix-valued function can have fourth-order quantity as large as $n$.

If $\Vert f(x){\Vert }_{\mathrm{op}}\le 1$ and $\Vert f{\Vert }_{U^2}^4\ge cn>0$, select the singular values ${\lambda }_p\ge \sqrt{c/2}$ of the matrix Fourier blocks. Their weighted count $m={\sum }_p{d}_{{\rho }_p}$ lies between $cn/2$ and $2n/c$. Scaling unit right singular vectors and their corresponding unit left singular vectors by $\sqrt{d_{{\rho }_p}}$ gives matrices $U(p),V(p)$ satisfying ${\mathbb{E}}_{x}f(x)U(p){\rho }_p(x{)}^{\ast }={\lambda }_{p}V(p)$ and Hilbert-Schmidt inner product orthogonality within each chosen irreducible representation. The Schur averaging of rectangular matrices then gives ${\mathbb{E}}_x\Vert UP(x{)}^{\ast }b{\Vert }_2^2=\Vert b{\Vert }_2^2$ for the concatenated $U$ and the corresponding block diagonal matrix $P(x)$.

For $f:G\to M_n(\mathbb{C})$ and a degree-$d_{\rho }$ unitary irreducible representation, the matrix Fourier block is the operator $T_{\rho }$ on $M_{n\times d_{\rho }}(\mathbb{C})$ defined in the title. Its singular values ${\lambda }_{\rho ,j}$ satisfyPointwise operator norm at most one implies $\Vert T_{\rho }{\Vert }_{\mathrm{op}}\le 1$. These blocks are operators on a matrix space, rather than simply the entrywise scalar Fourier transform on a finite group without any reshaping.

A finite group is $m$-quasirandom if every nontrivial irreducible representation over the complex numbers has degree at least $m$. The trivial representation is excluded. Large $m$ suppresses correlations of products of arbitrary subsets, through product mixing in a quasirandom group.

For an $m$-quasirandom group, uniform expectations, and the normalized convolution on a finite group, a scalar mean-zero function $f$ satisfiesThe Fourier analysis on a finite group proof bounds each nontrivial matrix component of $f$ in operator norm using its weighted Hilbert-Schmidt norm. For subsets of subset density values $a,b,c$, the error in their normalized product count is at most $\sqrt{a(1-a)b(1-b)c(1-c)/m}$. In particular $abc>1/m$ guarantees a solution of $xy=z$ in the three subsets.

For a finite group, choose one unitary irreducible representation $\rho$ of degree $d_{\rho }$ from each equivalence class. One consistent normalized Fourier transform on a finite group convention is $\hat{f}(\rho )={\mathbb{E}}_{x}f(x)\rho (x)$. The Schur orthogonality relations giveThe normalized convolution on a finite group satisfies $\widehat{f\ast g}(\rho )=\hat{f}(\rho )\hat{g}(\rho )$ in this convention. Using $\rho (x{)}^{\ast }$ in the transform instead reverses that product order for scalar functions with the same normalized convolution on a finite group convention. The Fourier transform on a finite group has matrix-valued components even when the original function is scalar-valued.

For a scalar function on a group, use $(R_{a}f)(x)=f(xa)$ as the right-translation convention. For Fourier analysis on a finite group this gives $\widehat{R_{a}f}(\rho )=\hat{f}(\rho )\rho (a{)}^{\ast }$. Specifying whether $a$ or $a^{-1}$ appears in the definition avoids sign and multiplication-order ambiguity.

For a scalar function on a group, left translation by $a$ is $(L_{a}f)(x)=f(a^{-1}x)$. With the positive-representation convention for Fourier analysis on a finite group, $\widehat{L_{a}f}(\rho )=\rho (a)\hat{f}(\rho )$.

For a scalar function on a finite group, one normalized transform convention assigns the matrix ${\mathbb{E}}_{x}f(x)\rho (x)$ to each chosen unitary irreducible representation. This map is a weighted Hilbert space isomorphism by the Parseval identity on a finite group. Another common convention uses $\rho (x{)}^{\ast }$; the corresponding convolution theorem on a finite group then reverses the matrix product order for $(f\ast g)(x)={\mathbb{E}}_{y}f(y)g(y^{-1}x)$.

For the Fourier transform on a finite group, the displayed identity uses uniform expectation in the original function space and a weighted Hilbert-Schmidt inner product in the matrix components. In particular $\Vert f{\Vert }_2^2={\sum }_{\rho }{d}_{\rho }\Vert \hat{f}(\rho ){\Vert }_{\mathrm{HS}}^2$. For an abelian group, all $d_{\rho }=1$, and the identity becomes a sum of squared scalar coefficients.

The Fourier transform on a finite group convention $\hat{f}(\rho )={\mathbb{E}}_{x}f(x)\rho (x)$ has the displayed inversion formula. The sum is over one representative from each equivalence class of unitary irreducible representations. It follows from the Schur orthogonality relations and the regular representation decomposition, and holds at every group element without a limiting argument.

For scalar functions on a finite group, normalized convolution on a finite group is $(f\ast g)(x)=|G{|}^{-1}{\sum }_{y}f(y)g(y^{-1}x)$. It is associative and need not commute. Its identity is $|G|1_{\{e\}}$, rather than the unscaled indicator function of the identity element. The Fourier analysis on a finite group convention $\hat{f}(\rho )=\mathbb{E}f(x)\rho (x)$ turns it into matrix multiplication in the same order.

The normalized convolution on a finite group and the Fourier transform on a finite group convention with $\rho (x)$ satisfy the displayed identity. Substitute $x=yz$ in the defining expectation and use $\rho (yz)=\rho (y)\rho (z)$. With the convention using $\rho (x{)}^{\ast }$ instead, the scalar convolution has transform $\hat{g}(\rho )\hat{f}(\rho )$; multiplication order matters for noncommutative groups.