Small-Support Uncertainty Principles on $\mathbb{Z}/p$ over Finite Fields

Abstract

We establish an uncertainty principle for functions $f:\mathbb{Z}/p\to {\mathbb{F}}_q$ with constant support (where $p\mid q-1$). In particular, we show that for any constant $S>0$, functions $f:\mathbb{Z}/p\to {\mathbb{F}}_q$ for which $|\text{supp}f|=S$ must satisfy $|\text{supp}\hat{f}|=(1-o(1))p$. The proof relies on an application of Szemeredi's theorem; the celebrated improvements by Gowers translate into slightly stronger statements permitting conclusions for functions possessing slowly growing support as a function of $p$.

3 pages

References in corpus (1)

• Simple proof of Chebotarev's theorem on roots of unity