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.

Let $S$ be a finite set of positive integers and let $T={\sum }_{s\in S}s$. Every sum of a subset is an integer in $\{0,\dots ,T\}$. If $2^{|S|}>T+1$, the pigeonhole principle forces two distinct subsets to have equal sums. Thus $S$ cannot be a dissociated set.

Cancelling their common intersection even produces two disjoint subsets with the same sum. Positivity means neither remaining subset can be empty. Conversely, equality of two distinct subset sums gives a nonzero relation with coefficients in $\{-1,0,1\}$, exactly the obstruction to being a dissociated set.

For an $r$-element subset of $\{1,\dots ,n\}$, the largest possible $T$ is $r(2n-r+1)/2$. Thereforeis a sufficient condition forcing a collision for every such subset. This counting bound is sufficient rather than necessary. Powers of two show how a collision-free collection can instead use the binary representation to make all sums different.