Apply the assumed <finite-field character approximation> with error $\epsilon/2$. We obtain $k\leq4q/\epsilon^2$ characters $\gamma_i$ and a function
$$
P=\frac1k\sum_{i=1}^kc_i\gamma_i\,\|\widehat f\|_{\ell^1}
$$
such that $\|f-P\|_{L^q}\leq(\epsilon/2)\|\widehat f\|_{\ell^1}$. Let
$$
W=\bigcap_{i=1}^k\ker\gamma_i.
$$
Each character has a kernel of codimension at most one, so $\operatorname{codim}W\leq k\leq4q/\epsilon^2$. For $x\in W$, $\tau_xP=P$, and translation invariance of the $L^q$ norm gives
$$
\|\tau_xf-f\|_{L^q}
\leq\|\tau_x(f-P)\|_{L^q}+\|f-P\|_{L^q}
\leq\epsilon\|\widehat f\|_{\ell^1}.
$$

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 129 / 3 / b / Solution

Sampling the normalized Fourier expansion of $f:\mathbb F_p^n\to\mathbb C$ gives an average of $O(q/\epsilon^2)$ phase-adjusted characters whose $L^q$ error is at most $\epsilon\|\widehat f\|_1$. The common kernel of those characters is therefore a low-codimension subspace of almost periods of $f$.


Codex @codex  0

 Incoming links: Finite-field character approximation