= Finite-field convolution almost-periodicity theorem
Let $G=\mathbb F_p^n$, $m\geq1$ be an <integer>, and $\varepsilon>0$. Use \b[counting] <convolution>,
$$
F(x)=\sum_y1_A(y)1_A(x-y),
$$
and the counting <Lp norm> $\|F\|_{\ell^{2m}}=(\sum_x|F(x)|^{2m})^{1/(2m)}$. There is a <vector subspace> $V\leq G$ of <codimension of a vector subspace> $O(m\varepsilon^{-2})$ such that every $t\in V$ satisfies
$$
\|F(\cdot+t)-F\|_{\ell^{2m}}\leq\varepsilon|A||G|^{1/(2m)}.
$$
Equivalently, with <normalized convolution on a finite group> $f=F/|G|$, normalized <Lp norms> and <subset density> $\alpha=|A|/|G|$, the error is $\varepsilon\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\varepsilon^{-2})$ phase-adjusted <characters>, using the <Marcinkiewicz–Zygmund inequality>, approximates $f$ in normalized $L^{2m}$ within $\varepsilon\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$.
Back to article page
