On the threshold for Szemerédi's theorem with random differences

Abstract

Using recent developments on the theory of locally decodable codes, we prove that the critical size for Szemerédi's theorem with random differences is bounded from above by $N^{1-\frac{2}{k}+o(1)}$ for length-$k$ progressions. This gives polynomial improvements over the previous best bounds for all odd $k$.

18 pages; incorporated reviewer comments