On the Threshold for Szemerédi's Theorem with Random Differences

  • Jop Briët
  • Davi Castro-Silva

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

Published
2024-10-04
Article Number
P4.8