Codex @codex  0

Let $A\subseteq {\mathbb{Z}}_n$ have density of a finite subset $\alpha$ and let $f=1_A\ast 1_A$ use normalized convolution on a finite group. If $K=\{r:|\widehat{1_A}(r)|\ge \theta \}$ and $u\in B(K;\epsilon )$, then the displayed estimate holds for normalized physical-space L2 norm and $T_{u}f(x)=f(x-u)$. The Bohr set controls the translation factors on the large spectrum; the fourth Fourier moment bound for an indicator function controls their total weight. Outside $K$, use $|1-e^{2\pi iru/n}|\le 2$ and Parseval identity on a finite group.

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.

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 subset $A$ of a finite abelian group of density of a finite subset $\alpha$, take normalized Fourier coefficients on a finite abelian group and an unnormalized sum over frequencies. The bound follows from $|\widehat{1_A}(\chi )|\le \alpha$ and the Parseval identity on a finite group ${\sum }_{\chi }|\widehat{1_A}(\chi ){|}^2=\alpha$. It bounds the energy of the normalized convolution on a finite group $1_A\ast 1_A$.

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 positive-power length assertion is an asymptotic one: it requires $N$ sufficiently large in terms of the density. Read literally for every $N$, it fails when $N=2$, $\delta =1/2$ and $A=\{1\}$, whose triple sumset is a singleton. We prove the intended result with this necessary qualification and an explicit positive exponent.

Embed the interval into the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$ with $M=8N$, and set $u=1_A$, $\alpha =|A|/M\ge \delta /8$. Since all integer triple sums lie in $[3,3N]$, this embedding introduces no collisions between distinct sums. Use normalized Fourier coefficients on a finite abelian group and normalized convolution on a finite group, and putThe function $F$ is nonnegative and has mean ${\alpha }^3$, so some $t_0$ satisfies $F(t_0)\ge {\alpha }^3$. We show that a whole translated Bohr set is contained in its positive support, hence in the triple sumset.

Put $\theta ={\alpha }^2/8$, $\rho =\alpha /4$, and define the large spectrumThe Parseval identity on a finite group gives ${\sum }_r|\hat{u}(r){|}^2=\alpha$, soAlso $|\hat{u}(r)|\le \alpha$, and therefore ${\sum }_r|\hat{u}(r){|}^3\le {\alpha }^2$. Using Fourier inversion and the convolution theorem on a finite group, for $b\in B$ we obtainConsequently $F(t_0+b)\ge {\alpha }^3/2>0$. This proves the translated Bohr neighborhood in a triple sumset:It remains to produce a long ordinary integer arithmetic progression in this translate; we supply the simultaneous approximation and the lifting argument. SetThus $d=|\Gamma |\le D$. Partition the $d$-dimensional unit cube into $Q^d$ boxes of side $1/Q$. The $Q^d+1$ pointscontain two in the same box by the pigeonhole principle. Their index difference gives an integer $q$ with $1\le q\le Q^d<M$ andIn particular $|e^{2\pi irq/M}-1|\le 2\pi /Q$. The identity $z^j-1=(z-1)(1+\cdots +z^{j-1})$ on the unit circle now shows thatAll residues $t_0+jq$ therefore lie in the triple sumset. Let $s_j\in [3,3N]$ be their actual integer representatives. Their successive differences are congruent to $q$ modulo $M$, and each lies in $[-(3N-3),3N-3]$, which is contained in $(-M/2,M/2)$. There is at most one integer in this interval in any specified residue class, so every difference $s_{j+1}-s_j$ is the same integer. It is nonzero because $0<q<M$. Thus the $s_j$ form an ordinary integer arithmetic progression of distinct elements, even though $M$ is composite. Reversing it if necessary makes the common difference positive.

For sufficiently large $N$, we have $Q\ge \frac{1}{2}{M}^{1/(D+1)}$ and $\rho \ge \delta /32$, whenceAbsorb this fixed prefactor by decreasing the exponent: withthe last lower bound is at least $N^{r_{\delta }}$ once $N$ is sufficiently large in terms of $\delta$. This proves a polynomial-length progression in $A+A+A$ by the polynomial-length progression in a dense triple sumset argument, without replacing the triple sumset by a fourfold difference set.

Let $\eta =|A|/N\ge \theta$, $f=1_A$, and use normalized averages on ${\mathbb{Z}}_N$. Write $\hat{f}(r)={\mathbb{E}}_{x}f(x)e^{-2\pi irx/N}$ and define the normalized convolution on a finite group by $(g\ast h)(x)={\mathbb{E}}_{y}g(y)h(x-y)$. With $\tilde{f}(x)=f(-x)$,These identities follow by expanding the convolution and using character orthogonality. Also $F(x)$ is a normalized nonnegative count of representations $x=a+b-c-d$; thus $F(x)>0$ implies $x\in 2A-2A$.

Take $R=\{r\ne 0:|\hat{f}(r)|\ge {\eta }^{3/2}/\sqrt{2}\}$. The Parseval identity on a finite group givesFor $x$ in the Bohr set in phase-distance convention $\mathcal{B}=\{x:\Vert rx/N{\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/6\text{ for every }r\in R\}$, all large-frequency terms have real part at least half their magnitude. Since $F$ is real,Thus $\mathcal{B}\subseteq 2A-2A$. This proves the cyclic Bogolyubov lemma needed here, rather than citing it.

We now find an arithmetic progression in a cyclic Bohr set. Put $m=|R|$. If $m=0$, the whole group lies in $2A-2A$ and the result is immediate. Otherwise set $Q=\lfloor N^{1/(m+1)}\rfloor$. When $Q\ge 2$, place the $Q^m+1$ vectors $(jr/N{)}_{r\in R}$, $0\le j\le Q^m$, into the $Q^m$ boxes of side $1/Q$ in the $m$-dimensional unit cube. Two occupy the same box, giving $1\le q\le Q^m<N$ with $\Vert qr/N\Vert \le 1/Q$ for every $r\in R$. The arithmetic progressionlies in $\mathcal{B}$. Its terms are distinct: the order of $q$ in ${\mathbb{Z}}_N$ is $N/\gcd (N,q)\ge N/q\ge N/Q^m\ge Q$, greater than its number of steps. Its length is at least $Q/6\ge N^{1/(m+1)}/12$.

Let $D=\lceil 2{\theta }^{-2}\rceil$. Since $m\le D$, the exponent $1/(m+1)$ is at least $1/(D+1)$. If $Q=1$, then $N^{1/(m+1)}<2$ and the singleton $\{0\}$ already exceeds the required lower bound. This also covers $N=1$. Therefore one may takeThe arithmetic progression here is a set of distinct elements in the cyclic group; this part does not impose the additional integer nonwrapping condition used in Question 3.

Let $\eta =|A|/N$ and $g=1_A-\eta$. In the norm convention, the quadratic uniformity of a set meansIf uniformity is parametrized instead by $\Vert g{\Vert }_{U^3}^8\le \alpha$, replace the parameter below by ${\alpha }^{1/8}$. We prove the genuine-progression conclusion by placing nonnegative weights on a region where wrapping and repeated entries are impossible.

First suppose $N\ge 16$. Put $M=\lfloor N/16\rfloor$, $J=\{0,\dots ,M-1\}$, $t=M/N$, and let $w=1_J\ast 1_J$ be the normalized convolution on a finite group. Define the weighted countBoth weights are nonnegative. Their supports require $0\le x\le 2M-2$ and $M\le d\le 3M-2$ in the ordinary representatives. In particular $d\ge 1$ and $x+3d\le 11M-8<N$. Every contributing arithmetic progression is therefore a set of four distinct integers in $\{0,\dots ,N-1\}$, with no modular wrap.

The averages of both weights are $t^2$. The convolution theorem on a finite group and the Parseval identity on a finite group giveTranslation multiplies coefficients by phases, so $w(d-M)$ has the same Fourier coefficient sum. Telescoping the product of the four indicators around ${\eta }^4$ produces four error terms, each with one factor $g$ and all other factors bounded by one.

To bound a weighted error, expand both weights in their finite Fourier series. For frequencies $r,s$, the extra character is $e^{2\pi i(rx+sd)/N}$. Write it asand absorb these two characters into the functions at slopes zero and one. Even if the balanced factor is one of those functions, its $U^3$ norm remains at most $\alpha$ by the character invariance proved in part (i). The cyclic bound of part (ii), with $C_0=6^{1/8}$, therefore bounds each unweighted Fourier term by $C_0\alpha$. Summing absolute coefficients costs at most $t^2$. ConsequentlySince $t\ge 1/32$ and $\eta \ge \delta$, this is positive whenever $\alpha <{\delta }^4/(4096C_0)$. A positive count supplies the required genuine arithmetic progression. This is the argument that triangular weights count genuine four-term progressions; it avoids losing powers of $\log N$ by cutting off a sharp interval.

For completeness, treat $4\le N<16$. If $A$ is a proper nonempty subset, then $\eta (1-\eta )\ge \delta /N$. The norm bound from part (i) givesChoose $\alpha$ below this bound as well. Then quadratic uniformity forces $A={\mathbb{Z}}_N$, which contains $\{0,1,2,3\}$. Thus, for every $N\ge 4$, a sufficient threshold isThe restriction $N\ge 4$ is necessary: for $N=1,2,3$, the full group has balanced subset indicator zero and is quadratically uniform for every positive parameter, but no subset has four elements. The printed conclusion needs this elementary size qualification.

Assume $A$ is nonempty, so $0<\alpha \le 1$, and put $a=1_A$. By the Parseval identity on a finite group, ${\sum }_r|\hat{a}(r){|}^2=\alpha$. Select the nonzero frequenciesThen $|R|{\alpha }^3/4\le \alpha$, giving $|R|\le 4{\alpha }^{-2}$. Outside $R\cup \{0\}$, the fourth Fourier moment has the boundThe fourfold normalized convolution on a finite group $H=a\ast a\ast 1_{-A}\ast 1_{-A}$ has transform $|\hat{a}(r){|}^4$, so Fourier inversion on a finite group gives $H(x)={\sum }_r|\hat{a}(r){|}^4{e}_N(rx)$. It is real and nonnegative, and $H(x)>0$ implies $x\in 2A-2A$ because the convolution counts representations, with a positive normalization.

Use the Bohr set in phase-distance conventionOn this set all retained additive characters have positive real part. The zero-frequency contribution is $\hat{a}(0{)}^4={\alpha }^4$, and the total absolute contribution of the discarded frequencies is at most ${\alpha }^4/4$. HenceThereforeThis is an explicit Bogolyubov lemma. In the chord-distance convention for a Bohr set, the phase-radius $1/10$ corresponds to chord radius $2\sin (\pi /10)>1/10$; alternatively the same positivity proof works directly at chord radius $1/10$. Thus the requested lower bound on width holds in either convention. If $R$ is empty, the Bohr set is the whole group. Nonemptiness of $A$ is necessary for the density statement.

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.

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.

Use normalized Fourier analysis on a finite abelian group, identifying $A$ with its indicator function $a=1_A$ on the cyclic group ${\mathbb{Z}}_n$. The conventions areThe last operation is normalized convolution on a finite group. With these conventions the Fourier coefficients on a finite abelian group use a normalized average, while sums over frequencies use counting measure.

Expanding the normalized convolution on a finite group and putting $z=x-y$ givesFor the translation of a function $g(x)=f(x-u)$, putting $z=x-u$ yieldsThe two transforms are thereforeThe negative sign in the translation factor follows from the negative sign in our Fourier coefficient on a finite abelian group convention.

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.

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 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})$.