Absolutely Sensational Morning News – Zander Kelley and Raghu Meka proved Behrend-type bounds for 3APs

Combinatorics and more 2023-02-14

ultimate-roth

What is the density of a subset $A$ of $\{1,2,\dots , n \}$ that guarantees that $A$ contains a 3-term arithmetic progression? And, more generally, if the density of $A$ is $\delta$ what is the minimum number of 3-terms AP that $A$ contains?

These problems and the more general problems for $k$ -term AP, are very exciting and mathematicians worked on them extensively in the last century. (We devoted several posts to earlier breakthroughs.)

This morning. a striking new paper by Zander Kelley and Raghu Meka appeared on the arXiv describing an absolutely amazing breakthrough. (I am thankful to Ryan Alweiss for telling me about it.) Here is the link to the paper

Strong Bounds for 3-Progressions, by Zander Kelley and Raghu Meka

Abstract: We show that for some constant β>0, any subset A of integers {1,…,N} of size at least

$2^{-O((\log N)^\beta)} \cdot N$

contains a non-trivial three-term arithmetic progression. Previously, three-term arithmetic progressions were known to exist only for sets of size at least $N/(\log N)^{1 + c}$ for a constant $c>0$ .

Our approach is first to develop new analytic techniques for addressing some related questions in the finite-field setting and then to apply some analogous variants of these same techniques, suitably adapted for the more complicated setting of integers.

Huge congratulations to Zander Kelley and Raghu Meka, and to the mathematical community.

3-term AP

AI generated image showing arithmetic progression by shutterstock.

An earlier 2020 post on 3-term AP and related problems with much bacground on the problem: To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth’s theorem!;