Finite-field character approximation
= Finite-field character approximation
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$.