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 improves the previous best bounds of $N^{1-\frac{1}{\lceil k/2 \rceil} + o(1)}$ for all odd $k$.