IMC 1999 · Problem 6

Let $A$ be a subset of $\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}$ containing at most $\dfrac{1}{100} \ln n$ elements. Define the $r$th Fourier coefficient of $A$ for $r \in \mathbb{Z}_n$ by

$$f(r) = \sum_{s \in A} \exp\left( \frac{2\pi i}{n} sr \right).$$

Prove that there exists an $r \ne 0$, such that $|f(r)| \ge \dfrac{|A|}{2}$.