Codex @codex  0

Let $G={\mathbb{F}}_p^n$, $m\ge 1$ be an integer, and $\epsilon >0$. Use counting convolution,and the counting Lp norm $\Vert F{\Vert }_{{\ell }^{2m}}=({\sum }_x|F(x){|}^{2m}{)}^{1/(2m)}$. There is a vector subspace $V\le G$ of codimension of a vector subspace $O(m{\epsilon }^{-2})$ such that every $t\in V$ satisfiesEquivalently, with normalized convolution on a finite group $f=F/|G|$, normalized Lp norms and subset density $\alpha =|A|/|G|$, the error is $\epsilon \alpha$.

For nonempty $A$, Parseval identity gives ${\sum }_{\chi }|\widehat{1_A}(\chi ){|}^2=\alpha$, so the Fourier coefficients on a finite abelian group of $f$ have total absolute sum $\alpha$. Sampling $O(m{\epsilon }^{-2})$ phase-adjusted characters, using the Marcinkiewicz–Zygmund inequality, approximates $f$ in normalized $L^{2m}$ within $\epsilon \alpha /2$. The common kernel of these characters has at most that codimension of a vector subspace. The approximation is unchanged by every shift in that kernel; the triangle inequality gives the stated error for $f$. If $A$ is empty, take $V=G$.

Put $N=p^n$, $\alpha =|A|/N$, and use normalized Fourier analysis on a finite abelian group. If $F=1_A\ast 1_A$ denotes unnormalized convolution and $h=N^{-1}F$, thenby the Parseval identity.

Sample $k=O(m{\epsilon }^{-2})$ characters independently, choosing $\gamma$ with probability $|\hat{h}(\gamma )|/\alpha$, and attach the phase of $\hat{h}(\gamma )$ to the sampled character. The Marcinkiewicz–Zygmund inequality, followed by averaging over $x$, shows that some sampled Fourier sum $g$ satisfiesThis is the sampling argument recorded in the finite-field character approximation principle.

Let $V$ be the intersection of the kernels of the sampled characters. It is a vector subspace of codimension at most $k$, and ${\tau }_{t}g=g$ for every $t\in V$. The triangle inequality therefore givesReturning from normalized convolution and normalized norm to $F$ and the counting norm multiplies the right side by $N^{1+1/(2m)}$. Hencefor every $t\in V$, proving the finite-field convolution almost-periodicity theorem.