Improving Behrend's construction: Sets without arithmetic progressions in integers and over finite fields

Abstract

We prove new lower bounds on the maximum size of subsets $A\subseteq \{1,\dots ,N\}$ or $A\subseteq {\mathbb{F}}_p^n$ not containing three-term arithmetic progressions. In the setting of $\{1,\dots ,N\}$, this is the first improvement upon a classical construction of Behrend from 1946 beyond lower-order factors (in particular, it is the first quasipolynomial improvement). In the setting of ${\mathbb{F}}_p^n$ for a fixed prime $p$ and large $n$, we prove a lower bound of $(cp{)}^n$ for some absolute constant $c>1/2$ (for $c=1/2$, such a bound can be obtained via classical constructions from the 1940s, but improving upon this has been a well-known open problem).

(15 pages). This manuscript replaces the two manuscripts arXiv:2401.12802 and arXiv:2401.16106