Normalized Fourier analysis on a finite abelian group

For a finite abelian group $G$, use the normalized average ${\mathbb{E}}_x=|G{|}^{-1}{\sum }_x$, normalized convolutionand Fourier transform $\hat{f}(\gamma )={\mathbb{E}}_{x}f(x)\overline{\gamma (x)}$. Then Parseval's identity and the convolution identity take the forms

In a cyclic group of odd prime order, the normalized ordered three-term arithmetic progression count is ${\sum }_r\widehat{1_A}(r{)}^2\widehat{1_A}(-2r)$. The zero frequency contributes ${\alpha }^3$. If the count is less than ${\alpha }^3/2$, its nonzero-frequency contribution has magnitude greater than ${\alpha }^3/2$. The Parseval identity on a finite group bounds that magnitude by $\alpha {\max }_{r\ne 0}|\widehat{1_A-\alpha }(r)|$, proving the displayed estimate. The count includes progressions of zero common difference.

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 a scalar function on a finite abelian group, its coefficient at an additive character $\chi$ is the displayed uniform expectation. On ${\mathbb{F}}_3^d$, write ${\chi }_{\xi }(x)=e^{2\pi i\xi \cdot x/3}$. The coefficient at the constant character is the mean of $f$, and the Parseval identity on a finite group becomes ${\sum }_{\chi }|\hat{f}(\chi ){|}^2=\mathbb{E}|f{|}^2$ after relabelling characters to match the transform convention.

A linear phase on an abelian group is an additive character, such as $x\mapsto e(\theta x)$ on the integers or $x\mapsto {\omega }^{rx}$ on ${\mathbb{Z}}_N$.

For a linear phase $e^{2\pi i\theta x}$ on $[n]$, set $Q=\lfloor \sqrt{n}\rfloor$. The Dirichlet approximation theorem gives $1\le q\le Q$ with $\Vert q\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le Q^{-1}$. If $1\le L$ and $2L\le Q$, split each residue chain modulo $q$ into arithmetic progressions of lengths between $L$ and $2L-1$, merging the final remainder into the preceding block. Each chain has at least $Q$ points, so this is possible. On each resulting arithmetic progression, the linear phase varies from its first value by at most $4\pi L/Q$. This converts a large Fourier coefficient of a zero-sum real function into positive mean on one block: freezing the linear phase controls the weighted block sums, and their positive and negative total masses agree.

For $A$ in a finite abelian group and normalized Fourier transform $\widehat{1_A}$, the normalized number of sextuples satisfyingisThis follows by inserting orthogonality of complex exponentials for the displayed equation: the three variables on one side contribute $\widehat{1_A}(\gamma {)}^3$ and those on the other side contribute its complex conjugate.

For a set $A$ of density $\alpha$ in a finite abelian group,

Chang's theorem says that ${\mathrm{Spec}}_{\rho }(1_A)$ is contained in the span of a dissociated set of size $O({\rho }^{-2}\log ({\alpha }^{-1}))$.

A subset $\Lambda$ of an abelian group is dissociated when a relationforces every coefficient to vanish.