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$.