Codex @codex  0

Put $e_N(t)=e^{2\pi it/N}$ and use normalized averages ${\mathbb{E}}_x=N^{-1}{\sum }_{x\in \mathbb{Z}/N\mathbb{Z}}$. Our convention for Fourier coefficients on a finite abelian group isThe underlying orthogonality of complex exponentials is ${\mathbb{E}}_x{e}_N(rx)=1$ for $r=0$ and zero otherwise. For nonzero $r$ this is the finite geometric series with ratio $e_N(r)\ne 1$; its sum vanishes because that ratio has $N$th power one. The identical orthogonality statement holds when averaging over $r$ instead of $x$.

Using this orthogonality to sum the definition over $r$ proves Fourier inversion on a finite group:Indeed $\mathbb{E}f\overline{g}={\sum }_r\overline{\hat{g}(r)}{\mathbb{E}}_{x}f(x)e_N(-rx)={\sum }_r\hat{f}(r)\overline{\hat{g}(r)}$. This proves the Parseval identity on a finite group and its squared-norm case:For normalized convolution on a finite group, write $(f\ast g)(x)={\mathbb{E}}_{y}f(y)g(x-y)$. Changing variables $x=y+z$ in its transform givesthe convolution theorem on a finite group. Linearity of the transform follows directly from its definition. Translation ${\tau }_{t}f(x)=f(x+t)$ gives $\widehat{{\tau }_{t}f}(r)=e_N(rt)\hat{f}(r)$ by changing variables. Complex conjugation gives $\hat{\overline{f}}(r)=\overline{\hat{f}(-r)}$; for $\tilde{f}(x)=\overline{f(-x)}$, the corresponding identity is $\hat{\tilde{f}}(r)=\overline{\hat{f}(r)}$. Finally $\hat{f}(0)=\mathbb{E}f$ and $|\hat{f}(r)|\le \mathbb{E}|f|$ by the triangle inequality. These identities establish the basic normalized Fourier analysis on a finite abelian group needed below, with all normalizations fixed.

For completeness, pointwise multiplication has the dual convolution formula $\widehat{fg}(r)={\sum }_s\hat{f}(s)\hat{g}(r-s)$: insert the inversion formula for $g$ into the defining average and collect its frequencies. If $c\ne 0$ modulo $N$, the change of variables $u=cx$ gives $\widehat{f(c\cdot )}(r)=\hat{f}(r{c}^{-1})$. These also follow directly from the same additive character orthogonality.

In this part identify $\mathbb{T}$ with the complex unit circle by $t\mapsto e^{it}$. Write the finite abelian group $G$ additively and let $\hat{G}=\mathrm{Hom}(G,\mathbb{T})$, with pointwise multiplication, be the character group of a finite abelian group of $G$. A linear character has modulus one, since its values have finite order. We first prove the extension and counting facts needed for Fourier analysis on a finite abelian group.

If $H\le G$, $\chi \in \hat{H}$, and $x\notin H$, let $d$ be the least positive integer with $dx\in H$. Choose $z\in \mathbb{T}$ with $z^d=\chi (dx)$ and defineThis is well-defined: two representations differ by $j-j^{\prime }=qd$ and $h-h^{\prime }=-qdx$, whose contributions cancel. It is a group homomorphism and extends $\chi$. Conversely every extension has this form, and the equation for $z$ has exactly $d$ distinct roots. Since $[H+⟨x⟩:H]=d$, successive adjunctions prove that each linear character of $H$ has exactly $[G:H]$ extensions. Taking $H=\{0\}$ gives $\boxed{|\hat{G}|=|G|}$. This is the extension of a character across a cyclic quotient, proved here without a structure theorem. Extending the linear character sending a nonzero element $g$ of order $d$ to $e^{2\pi i/d}$ also proves that linear characters separate points of $G$.

Use the normalized inner product $⟨f,g⟩=|G{|}^{-1}{\sum }_{x\in G}f(x)\overline{g(x)}$. For a nontrivial linear character $\chi$, choose $a$ with $\chi (a)\ne 1$. Translation of the sum gives ${\sum }_x\chi (x)=\chi (a){\sum }_x\chi (x)$, so that sum is zero. Applying this to $\chi \overline{\psi }$ givesThere are $|G|$ such orthonormal vectors in the $|G|$-dimensional space ${\mathbb{C}}^G$, so they form an orthonormal basis. Define the Fourier coefficients by $\hat{f}(\chi )=|G{|}^{-1}{\sum }_{x}f(x)\overline{\chi (x)}$. Expanding in that basis proves Fourier inversion on a finite group and the Parseval identity on a finite group:For normalized convolution $(f\ast g)(x)=|G{|}^{-1}{\sum }_{y}f(y)g(x-y)$, changing the finite summation variables yields $\widehat{f\ast g}(\chi )=\hat{f}(\chi )\hat{g}(\chi )$. Translation $f(x)\mapsto f(x+a)$ multiplies its Fourier coefficient by $\chi (a)$. These formulas fix all normalization and conjugation conventions.

The PDF's double-hat identification is canonical Pontryagin duality: define $e:G\to \hat{\hat{G}}$ by $e_x(\chi )=\chi (x)$. This is a group homomorphism and is injective because linear characters separate points. Applying the already proved character-counting result to $\hat{G}$ shows that both groups have size $|G|$, soThe TeX loses one hat. For completeness, the single-dual isomorphism $\hat{G}\cong G$ also holds, but is generally noncanonical. Here is a proof including the needed finite cyclic decomposition. Choose an element $a$ of maximal order $d$. Every element order divides $d$: for two elements, extract their prime-power components by integer multiples: if an element has order $d$ and $p^{\alpha }$ is the exact power of $p$ in $d$, multiplying it by $d/p^{\alpha }$ gives order $p^{\alpha }$. Then combine the components with the larger order for each prime. Components of coprime orders have a sum of product order, because their cyclic subgroups have trivial intersection. This constructs an element of order the least common multiple of the two original orders, which cannot exceed maximal $d$; hence each order divides $d$.

Extend the primitive linear character of $⟨a⟩$ to $\chi :G\to \mathbb{T}$. All its values are $d$th roots because all element orders divide $d$. Define $\rho (g)=ja$ when $\chi (g)=e^{2\pi ij/d}$. This is a group homomorphism fixing $⟨a⟩$, and $g=\rho (g)+(g-\rho (g))$ shows $G=⟨a⟩\oplus \ker \rho$. Induction on group size decomposes $G$ into finite cyclic groups. A cyclic group of order $d_j$ has precisely the linear characters $j\mapsto e^{2\pi imj/d_j}$ and hence a character group of a finite abelian group isomorphic to itself. The dual of a finite direct product of groups is the product of its factor duals, since a linear character is determined by its restrictions. This proves $\hat{G}\cong G$ after choices of cyclic factors and generators, without using an unproved finite-abelian-group structure theorem.

The Roth theorem on three-term arithmetic progressions says that, for each fixed $\delta >0$, a sufficiently long interval cannot have a subset of density of a finite subset at least $\delta$ with no nonconstant three-term arithmetic progression. Equivalently, the maximum size of a three-term-progression-free subset of $[N]=\{1,\dots ,N\}$ is $o(N)$. Here is a density increment proof, including its analytic ingredients.

Write $e(t)=\exp (2\pi it)$ and embed $I=[N]$ into the cyclic group $G=\mathbb{Z}/(2N+1)\mathbb{Z}$ of order $M$. For normalized Fourier analysis on a finite abelian group take $\hat{h}(r)=M^{-1}{\sum }_{x}h(x)e(-rx/M)$. The orthogonality of complex exponentials follows from a finite geometric series: its average is zero for a nonzero frequency and one for frequency zero. Expanding in these linear phases consequently proves both Fourier inversion on a finite group and the Parseval identity on a finite group. In particular,The second identity follows by summing the frequency expansion over $x,d$: the two constraints leave precisely the frequencies $(r,-2r,r)$. Since $M$ is odd, multiplication by two permutes the frequencies. Also a congruence $x+z=2y$ with $x,y,z\in I$ is an equality in the integers, since $|x+z-2y|<M$.

Let $A\subseteq I$ have subset density $\alpha =|A|/N\ge \delta$, and suppose it contains no nonconstant three-term arithmetic progression. Its balanced indicator function of a finite subset is $f=1_A-\alpha 1_I$, extended by zero outside $I$. Then $\hat{f}(0)=0$. Counting endpoints with the same parity givesIf $N\ge 4{\alpha }^{-2}$, their difference in absolute value is at least ${\alpha }^3{N}^2/(4M^2)$. Telescope the difference of the products into three terms, each containing $f$ and two factors chosen from $1_A,\alpha 1_I$. Put $s={\max }_r|\hat{f}(r)|$. The Cauchy-Schwarz inequality and the Parseval identity on a finite group bound each term by $s\alpha N/M$, since the squared normalized $L^2$ norm of either other factor is at most $\alpha N/M$. Therefore some nonzero frequency $r$ satisfiesThis is the Fourier detection of a progression-free subset of an interval step; it has just been proved rather than assumed.

We now turn this Fourier coefficient on a finite abelian group into a density increment. Set $Q=\lfloor \sqrt{N}\rfloor$. Partition the unit interval into $Q$ equal pieces and place the $Q+1$ fractional parts of $0,r/M,\dots ,Qr/M$ in them. The pigeonhole principle gives $1\le q\le Q$ with $\Vert qr/M\Vert \le 1/Q$. This proves the particular Dirichlet approximation theorem needed here. Put $\kappa ={\alpha }^2/(1000\pi )$ and $L=\lfloor \kappa Q\rfloor$. For sufficiently large $N$ depending only on $\delta$, $L\ge \kappa Q/2$ and $2L\le Q$. Each residue chain modulo $q$ in $I$ has at least $Q$ elements. Split each such chain into arithmetic progressions with between $L$ and $2L-1$ elements, absorbing its final short remainder into the previous block.

The linear phase changes by at most $4\pi L/Q\le {\alpha }^2/250$ within any block. Freezing the linear phase at the first element of each block therefore changes the preceding correlation by at most ${\alpha }^{2}N/250$, because $|f|\le 1$. The triangle inequality givesThe block sums of the balanced indicator function of a finite subset add to zero, so their positive total is half their absolute total. Some block consequently satisfiesHere $c>0$ is absolute, and shrinking it absorbs the floors. An affine parametrization of $P$ identifies $A\cap P$ with a subset of $[|P|]$ and preserves arithmetic progressions.

Repeat this Roth density-increment step. Every step raises the subset density by at least ${\delta }^2/144$, so fewer than $T=\lceil 144/{\delta }^2\rceil +1$ steps are possible. All the lengths satisfy $N_{j+1}\ge c{\delta }^2\sqrt{N_j}$ while above a threshold depending only on $\delta$. Choose the initial $N$ so large that this lower recursion stays above that threshold for $T$ steps; this is possible by working backwards through finitely many squarings. We would then force a subset density greater than one. Thus every fixed positive density eventually forces a nonconstant three-term arithmetic progression. For an infinite subset of the positive integers with positive upper asymptotic density, apply the finite conclusion along initial intervals whose subset density is bounded away from zero; this gives the usual infinite formulation as well.

We will prove a polynomial progression in a high-energy fourfold difference set. The route is to extract a large subset with a small difference set, construct a dense Freiman s-isomorphism model, and use the Bogolyubov lemma and the pigeonhole principle. To respect the proof requirement, every ingredient beyond the elementary rules for Freiman homomorphisms is established below.

Assume $n\ge 1$. Since three entries of an additive quadruple determine the fourth, $E(A)\le n^3$, so a nonvacuous hypothesis has $0<\theta \le 1$. Let $r(t)=|\{(a,b)\in A^2:a+b=t\}|$. Then $E(A)={\sum }_{t}r(t{)}^2$ and ${\sum }_{t}r(t)=n^2$. Define the popular sum set $S=\{t:r(t)\ge \theta n/2\}$. The contribution to additive energy from its complement is at most $\theta n^3/2$. Since $r(t)\le n$, the bipartite graph on two copies of $A$ whose edges have sums in $S$ has at least $\theta n^2/2$ edges. Moreover $|S|\le 2n/\theta$.

Put $\delta =\theta /2$ and $\tau ={\delta }^2/16$. Here is a dependent random choice argument producing the small difference set. Independently choose two right vertices, allowing repetition, and let $X$ be their common left neighbourhood. The Cauchy-Schwarz inequality gives $\mathbb{E}|X|\ge {\delta }^{2}n$. Call an ordered pair of left vertices bad if its common right neighbourhood has fewer than $\tau n$ elements. The expected number $b(X)$ of bad ordered pairs in $X$ is at most ${\tau }^2{n}^2$, because a fixed bad pair survives both random choices with probability at most ${\tau }^2$. ThusChoose a realization attaining at least this expectation. Then $|X|\ge 3{\delta }^{2}n/4$, and $b(X)\le {\delta }^{2}n|X|/64\le |X{|}^2/48$. Remove from $X$ every vertex having more than $|X|/4$ bad partners in $X$. At most $|X|/12$ vertices are removed. The remaining set $B$ has $|B|\ge {\delta }^{2}n/2$, and any $a,b\in B$ have at least $|X|/2$ vertices $z\in X$ for which both $(a,z)$ and $(z,b)$ are good.

For such a $z$, there are at least $\tau n$ right vertices $y$ adjacent to $a,z$, and at least $\tau n$ right vertices $y^{\prime }$ adjacent to $z,b$. These paths givea representation with four members of $S$. For fixed $a,b$, the tuple of four sums determines $y,z,y^{\prime }$ uniquely, so there are at least $|X|{\tau }^2{n}^2/2$ distinct tuples. Select one ordered pair $a,b$ for each member of $B-B$. Tuples belonging to different differences are disjoint. Counting all possible tuples in $S^4$ provesIn particular, with $m=|B|$, we have $m\ge {\theta }^{2}n/8$ and $|B-B|\le Km$ for $K=2^{25}{\theta }^{-12}$. This is the required small-difference set form of the Balog-Szemerédi-Gowers theorem, proved by counting paths rather than cited.

We next control higher iterated sumsets. Choose a nonempty $X\subseteq B$ minimizing $\rho =|X-B|/|X|$, so $\rho \le K$. We prove the Petridis minimal-growth lemma in the form $|X-B+C|\le \rho |X+C|$ for finite $C$. Order $C=\{c_1,\dots ,c_t\}$, and let $X_i$ consist of those $x\in X$ for which $x+c_i$ is new in the union of the translates $X+c_j$. Then ${\sum }_i|X_i|=|X+C|$. Every member of $(X\setminus X_i)-B+c_i$ already occurs in an earlier translate of $X-B$. By minimality, $|(X\setminus X_i)-B|\ge \rho |X\setminus X_i|$, also when the complement is empty. Thus the new contribution from $X-B+c_i$ is at most $\rho |X_i|$. Sum over $i$ to prove the lemma. Iterating with $C=-(j-1)B$ gives $|X-jB|\le K^j|X|$.

For completeness, the Ruzsa triangle inequality in the needed form isFor each $d\in U-W$, fix $d=u_d-w_d$. The map $(d,v)\mapsto (u_d-v,v-w_d)$ is injective: adding the coordinates recovers $d$, and then $v$. Take $U=kB$, $W=\ell B$, $V=X$ and apply the preceding bounds. We obtain the Plünnecke-Ruzsa inequalityIn particular $T=8B-8B$ has at most $K^{16}m$ elements.

We now prove a slightly wasteful version of the Ruzsa modeling lemma, avoiding any assumption about the diameter of $B$. Set $q=8|T|$. Choose a prime $p$ larger than all $|t|$, $t\in T$, and much larger than $q$. Arbitrarily large primes exist by the elementary argument that a prime divisor of one plus the product of all primes up to a given bound exceeds that bound. For a uniformly chosen nonzero multiplier $r$ modulo $p$, each nonzero $t\in T$ has $rt$ uniform among the nonzero residues. Call a multiplier forbidden if some such $rt$ agrees modulo $p$ with $jq$, where $|jq|<p$. There are at most $2p/q+1\le 3p/q$ such residues. For $p\ge 4$, a union bound therefore makes the probability of being forbidden less thanChoose a nonforbidden $r$. Represent $rB$ by integers in $[0,p-1]$ and partition that interval into sixteen consecutive pieces of diameter less than $p/16$. One piece contains the images of a subset $B^{\prime }\subseteq B$ with $|B^{\prime }|\ge m/16$. Let $\varphi (b)$ be the integer representative of $rb$ in that piece, reduced modulo $q$.

A difference of eight sums of these representatives has absolute value less than $p/2$. If its original difference in $B$ is zero, it is a multiple of $p$, hence zero. Conversely, if its reduction modulo $q$ is zero, it equals $jq$ with $|jq|<p$; our choice of $r$ forces its original difference to be zero. This proves that $\varphi$ is a Freiman s-isomorphism of order eight. Injectivity follows by padding a one-term equality to eight terms with a fixed element. Consequently $D=\varphi (B^{\prime })\subseteq G=\mathbb{Z}/q\mathbb{Z}$ has subset densityNo primality of $q$ is needed.

Here is the cyclic Bogolyubov lemma with all its Fourier analysis on a finite abelian group details. Use $\hat{f}(r)={\mathbb{E}}_{x}f(x)e(-rx/q)$, $f=1_D$, and normalized convolution on a finite group. A finite geometric series proves orthogonality, and expanding the finite sums proves the Parseval identity on a finite group, Fourier inversion on a finite group, and $\widehat{f\ast g}=\hat{f}\hat{g}$. For $\tilde{f}(x)=f(-x)$, the nonnegative functionhas support exactly $2D-2D$ and Fourier coefficients on a finite abelian group $|\hat{f}(r){|}^4$. Put $\Gamma =\{r\ne 0:|\hat{f}(r)|\ge {\alpha }^{3/2}/\sqrt{8}\}$. The Parseval identity on a finite group gives $|\Gamma |\le 8{\alpha }^{-2}$. The total fourth moment of the frequencies outside $\Gamma \cup \{0\}$ is at most ${\alpha }^4/8$.

If $\Vert rx/q\Vert \le 1/16$ for every $r\in \Gamma$, then $\mathrm{Re}e(rx/q)\ge \cos (\pi /8)>3/4$. The zero frequency contributes ${\alpha }^4$ with no loss. Separating the large and small frequencies in Fourier inversion on a finite group yieldsThus $2D-2D$ contains the Bohr set expressed in distance coordinates by $\Vert rx/q\Vert \le 1/16$. This is consistent with the existing character-distance convention for a Bohr set: here it is enough that each character lies in the corresponding short arc around one.

We finally prove the needed nonwrapping progression in a cyclic Bohr set, including for composite $q$. Write $d=|\Gamma |$ and $Q=\lfloor q^{1/(d+1)}\rfloor$. Partition the $d$-dimensional unit cube into $Q^d$ boxes. The $Q^d+1$ points with coordinates $jr/q$ modulo one, $0\le j\le Q^d$, give by the pigeonhole principle an integer $1\le t\le Q^d$ with $\Vert rt/q\Vert \le 1/Q$ for all $r\in \Gamma$. ThenThese points are distinct modulo $q$, since their integer representatives lie between zero and $Q^{d+1}/16\le q/16$. Their number is at least $q^{1/(d+1)}/32$. For $d=0$ the same argument simply chooses $t=1$.

The Freiman s-isomorphism induces a bijection $\Phi :2B^{\prime }-2B^{\prime }\to 2D-2D$: define it on a representation by taking the same two positive and two negative images. Equality of representations uses an order-four relation, and injectivity uses the converse relation. If three consecutive members $y_{j-1},y_j,y_{j+1}$ of $P$ satisfy $y_{j-1}+y_{j+1}=2y_j$, their preimages satisfy the same equality, since its expansion is an equality of eight-term sums in $B^{\prime }$. Hence the inverse image of $P$ is an ordinary arithmetic progression in $2B^{\prime }-2B^{\prime }\subseteq 2A-2A$, with distinct terms.

To remove the multiplicative constant from the length bound, let $R=\lceil 8{\alpha }_0^{-2}\rceil$ and $\beta =1/(R+1)$. The length just proved is at least $c_{\theta }{n}^{\beta }$, where $c_{\theta }={\theta }^{2\beta }/32>0$. Choose $N_0\ge 3$ so that $c_{\theta }{n}^{\beta }\ge n^{\beta /2}$ for $n\ge N_0$, and set $\gamma =\min \{\beta /2,\log 3/\log N_0\}$. For $2\le n<N_0$, two distinct members of $A$ give a nonzero $u\in A-A$, and $\{-u,0,u\}\subseteq 2A-2A$ has length three, at least $n^{\gamma }$. For $n=1$, the singleton $\{0\}$ suffices. In every nonempty case,with $\gamma >0$ depending only on $\theta$. If empty sets are permitted, the required length is zero and there is no substantive assertion.

For the physical-space L2 norm use $\Vert h{\Vert }_2^2={\mathbb{E}}_x|h(x){|}^2$. By part (i) and the Parseval identity on a finite group,Split this sum into the large spectrum $K$ and its complement. Because $u$ belongs to the Bohr set in the question, for $r\in K$,Consequently the contribution from $K$ is at most ${\epsilon }^2{\sum }_r|\hat{a}(r){|}^4\le {\epsilon }^2{\alpha }^3$ by part (ii). Outside $K$, $|\hat{a}(r)|<\theta$, and $|1-{\omega }^{-ru}|\le 2$. Thus that contribution is at mostAdding the estimates provesThe argument also covers empty $A$ or empty $K$. As usual the radius and threshold are nonnegative; a negative radius makes the premise empty whenever $K$ is nonempty. The estimate expresses Bohr-set almost periodicity of a convolution: a translation of a function by an element of the Bohr set barely changes the large Fourier coefficients on a finite abelian group, while the small ones have little total energy.

Since $a$ is an indicator function of density of a finite subset $\alpha$, the triangle inequality gives $|\hat{a}(r)|\le {\mathbb{E}}_{x}a(x)=\alpha$ for every frequency. Also, character orthogonality and the Parseval identity on a finite group giveFor completeness, the character orthogonality used here iswhich follows by summing a finite geometric series. Expanding the squared Fourier coefficients on a finite abelian group and using this identity proves the displayed Parseval identity on a finite group directly.

Combining the uniform bound with that identity gives the fourth-moment boundIn particular, the Lp norm on the frequency side here is a sum, not a normalized average. This is the fourth Fourier moment bound for an indicator function.

A sufficient absolute constant is $\boxed{C=16}$. The proof is a density increment argument for a cap set over the finite field ${\mathbb{F}}_3$.

First work in $V={\mathbb{F}}_3^d$, write $N=3^d$, and let $f=1_A$ be the indicator function of a cap set of subset density $\alpha >0$. All expectations below are uniform. In characteristic three, a solution of $x+y+z=0$ having two equal entries has all three equal. Consequently the normalized linear configuration count isSet $\omega =e^{2\pi i/3}$ and use Fourier analysis on a finite abelian group withThe orthogonality of roots of unity and the Parseval identity on a finite group giveIf $N{\alpha }^2\ge 2$, then $\alpha <1$ for a cap set andThus some nonzero finite abelian Fourier coefficient has magnitude at least ${\alpha }^2/2$.

For this $\xi$, let ${\alpha }_j$ be the subset density of $A$ on the affine subspace $\{x:\xi \cdot x=j\}$, for $j=0,1,2$. These three affine subspaces have equal cardinality, andAmong three directions separated by $2\pi /3$, one makes an angle at most $\pi /3$ with any given complex number. Hence ${\max }_j({\alpha }_j-\alpha )\ge |\hat{f}(\xi )|$. Restricting to that hyperplane gives the hyperplane density increment for cap setsTranslate the affine subspace to its underlying vector space. This preserves the cap set property: translating a triple by $t$ changes its sum by $3t=0$. The same argument can therefore be iterated.

For completeness, the density increment iteration gives an explicit uniform bound. If $n<16$, the hypothesis $\alpha \ge 16/n$ is impossible. Suppose $n\ge 16$ and a cap set has ${\alpha }_0\ge 16/n$. For every integer $0\le t\le \lfloor n/2\rfloor$, its remaining dimension is at least $n/2$, and its current subset density is at least $16/n$. ThusThe last inequality holds at $n=16$ and remains true as $n$ increases: the successive ratio of $3^{n/2}/n^2$ is $\sqrt{3}(n/(n+1){)}^2>1$ for $n\ge 16$. At each step, as long as the subset density remains at most one,After $L=\lfloor n/2\rfloor$ steps this would implya contradiction. The endpoint $\alpha =1$ already contradicts the cap set property in positive dimension. This proves the claimed existence of three distinct points and the Meshulam bound for cap sets.

Use the following normalization for Fourier analysis on a finite group. Choose one unitary irreducible representation $\rho :G\to U(d_{\rho })$ from each equivalence class, including the trivial representation. For a scalar function $f:G\to \mathbb{C}$, putThis convention uses $\rho (x)$, rather than $\rho (x{)}^{\ast }$, in the Fourier transform on a finite group; it makes the normalized convolution on a finite group preserve multiplication order.

The needed representation theory consists of Maschke's theorem and unitarization of a finite-group representation, together with the Schur orthogonality relations:The regular representation contains $d_{\rho }$ copies of each $\rho$, so ${\sum }_{\rho }{d}_{\rho }^2=|G|$. Thus the scaled matrix coefficients $\sqrt{d_{\rho }}\rho (x{)}_{ij}$, and also their complex conjugates, form an orthonormal basis of all scalar functions on $G$. These facts imply Fourier inversion on a finite group and the Parseval identity on a finite group in the formsand henceIn particular, the transform is an isomorphism onto the direct sum of the matrix algebras $M_{d_{\rho }}(\mathbb{C})$, with the displayed weighted Hilbert-Schmidt inner product.

Define the normalized convolution on a finite group bySubstituting $x=yz$ and using the group representation identity yields the convolution theorem on a finite groupUnlike normalized convolution on a finite group on an abelian group, this product need not commute. If $\tilde{f}(x)=\overline{f(x^{-1})}$, then $\hat{\tilde{f}}(\rho )=\hat{f}(\rho {)}^{\ast }$. For left translation of a group function and right translation of a group function $L_{a}f(x)=f(a^{-1}x)$ and $R_{a}f(x)=f(xa)$,For an abelian group, every irreducible representation is one-dimensional; this reduces to Fourier analysis on a finite abelian group with characters relabelled by their inverses. These formulas establish the basic scalar theory, with all normalizations and multiplication orders fixed.

Now suppose every nontrivial irreducible representation has $d_{\rho }\ge m$. If $f$ is a mean-zero function, its component at the trivial representation is zero. The Parseval identity on a finite group gives, for each other $\rho$,Using the convolution theorem on a finite group, the Hilbert-Schmidt norm inequality $\Vert AB{\Vert }_{\mathrm{HS}}\le \Vert A{\Vert }_{\mathrm{op}}\Vert B{\Vert }_{\mathrm{HS}}$, and the Parseval identity on a finite group once more gives the product mixing in a quasirandom group estimateWrite $a,b,c$ for the subset density values of $A,B,C$, respectively, and let $f=1_A-a$, $g=1_B-b$ be balanced subset indicators. Since both are mean-zero functions, $1_A\ast 1_B=ab+f\ast g$. Their squared norms are $a(1-a)$ and $b(1-b)$. Also $\mathbb{E}(f\ast g)=0$, so the Cauchy-Schwarz inequality yieldsIf $abc>1/m$, the final bound is strictly smaller than $abc$. Thus the normalized number of pairs $(x,y)\in A\times B$ with $xy\in C$ is positive. Equivalently,This is the desired conclusion for a quasirandom group; the strict inequality ensures positivity rather than merely a nonnegative lower bound.

Use the unnormalized Fourier transform and $|f|\le 1$. Normalize each derivative correlation by $N$ and align its phase. Their absolute sum is at least $\alpha N$. One Cauchy-Schwarz inequality, expansion by shift/frequency differences, and a second Cauchy-Schwarz inequality bound its fourth power by $N$ times the additive energy of a frequency graph. Parseval identity on a finite group supplies the factor $N$; exact equality of both shift sums and frequency sums is retained.

For a subset $A$ of density $\alpha$ in a finite cyclic group, put $F=1_A\ast 1_A\ast 1_A$ using normalized convolution on a finite group. Its average is ${\alpha }^3$, so choose $t_0$ with $F(t_0)\ge {\alpha }^3$. Retain the large spectrum where $|\widehat{1_A}|\ge {\alpha }^2/8$. The Parseval identity on a finite group gives at most $64{\alpha }^{-3}$ frequencies. Their phases change by at most $\alpha /4$ on the associated Bohr set, contributing at most ${\alpha }^3/4$ to the change of $F$. The discarded frequencies contribute at most another ${\alpha }^3/4$, since $\sum |\widehat{1_A}{|}^2=\alpha$. Therefore $F(t_0+b)\ge {\alpha }^3/2>0$ on the Bohr set, proving the containment.

For $A\subseteq {\mathbb{Z}}_N$, $N\ge 16$, put $\eta =|A|/N$, $M=\lfloor N/16\rfloor$, $J=\{0,\dots ,M-1\}$, and $w=1_J\ast 1_J$ using normalized convolution on a finite group. The weights $w(x)w(d-M)$ are supported where $0\le x\le 2M-2$ and $M\le d\le 3M-2$, so $x,x+d,x+2d,x+3d$ are distinct integer points below $N$. If $t=M/N$, then $\mathbb{E}w=t^2$ and the sum of absolute values of its Fourier coefficients is $t$, by Parseval identity on a finite group. Expanding the four indicators around their subset density leaves four terms with one balanced factor. Expand both weights in Fourier series and absorb each character $e(rx+sd)$ into the factors at $x$ and $x+d$. Character multiplication preserves the Gowers U3 norm, and the cyclic four-term progression bound with torsion factors bounds every error by $6^{1/8}\alpha$. Thus the weighted count is at least ${\eta }^4{t}^4-4\cdot 6^{1/8}\alpha t^2$. Since $t\ge 1/32$, positivity follows from $\alpha <{\eta }^4/(4096\cdot 6^{1/8})$.