On the decay of the Fourier transform and three term arithmetic progressions

Abstract

Let ${\mathbb{F}}_2^n$ be the finite field of cardinality $2^n$. For all large $n$, any subset $A\subset {\mathbb{F}}_2^n\times {\mathbb{F}}_2^n$ of cardinality
$$|A|\gtrsim \frac{4^n\log \log n}{\log n},$$
must contain three points $\{(x,y),(x+d,y),(x,y+d)\}$ for $x,y,d\in {\mathbb{F}}_2^n$ and $d\ne 0$. Our argument is an elaboration of an argument of Shkredov [14], building upon the finite field analog of Ben Green [10]. The interest in our result is in the exponent on $\log n$, which is larger than has been obtained previously.