MathDB

IMC 1999 Problem 12

Source: IMC 1999 Day 2 Problem 6

October 27, 2020

fourier seriescomplex numberspigeonhole principleIMC

Problem Statement

Let

A

be a subset of

\mathbb{Z}/n\mathbb{Z}

with at most

\frac{\ln(n)}{100}

elements. Define

f(r)=\sum_{s\in A} e^{\dfrac{2 \pi i r s}{n}}

. Show that for some

r \ne 0

we have

|f(r)| \geq \frac{|A|}{2}