IMC 1999 · Day 2 · P12

Let $A = \{a_1, \dots, a_k\}$. Consider the $k$-tuples $$\left( \exp \frac{2\pi i a_1 t}{n}, \dots, \exp \frac{2\pi i a_k t}{n} \right) \in \mathbb{C}^k, \quad t = 0, 1, \dots, n-1.$$ Each component is in the unit circle $|z| = 1$. Split the circle into 6 equal arcs. This induces a decomposition of the $k$-tuples into $6^k$ classes. By the condition $k \le \frac{1}{100} \ln n$ we have $n > 6^k$, so there are two $k$-tuples in the same class say for $t_1 < t_2$. Set $r = t_2 - t_1$. Then $$\operatorname{Re} \exp \frac{2\pi i a_j r}{n} = \cos \left( \frac{2\pi a_j t_2}{n} - \frac{2\pi a_j t_1}{n} \right) \ge \cos \frac{\pi}{3} = \frac{1}{2}$$ for all $j$, so $$|f(r)| \ge \operatorname{Re} f(r) \ge \frac{k}{2}.$$