We establish an uncertainty principle for functions $f: \mathbb{ Z}/p \rightarrow \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 \rightarrow \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$.
Categories: math.CO math.NT