Szemerédi's theorem with random differences and arithmetic Kakeya
Abstract
We prove that there exists an absolute constant c > 0 such that the following holds for every k ≥ 3 and p ≥ n−c / log log k. Letting δ> 0 and D ∼ [n]p, with high probability every S ⊂ [n] with |S| ≥ δn contains a k-term arithmetic progression whose common difference lies in D. This improves the best known bounds for the threshold of Szemerédi's theorem with random differences for all sufficiently large k, previously of the form p ≥ n−2/k+o(1), due to Briët and Castro-Silva. We obtain our improvement via a small cover lemma, in the sense of Alon and Pham's work on random Cayley graphs, and its proof crucially relies on a construction of Green and Ruzsa in the context of the arithmetic Kakeya conjecture. The usage of the latter was suggested to us by GPT 6 Astra.
Related
- Sparse k-AP Covering Sets and the Arithmetic Kakeya Conjecture
- A Hajnal-Szemerédi Theorem for Skewed Colorings
- Further bounds in the polynomial Szemerédi theorem
- Multidimensional Szemerédi Theorem for Pairwise Independent Jointly Intersective Polynomials
- Two proofs and a tight Szemerédi--Trotter theorem
BibTeX
@misc{dahia2026szemerédis,
title = {{Szemerédi's theorem with random differences and arithmetic Kakeya}},
author = {Gabriel Dahia},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18859},
eprint = {2610.18859},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18859},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Szemerédi's theorem with random differences and arithmetic Kakeya
AU - Gabriel Dahia
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18859
UR - https://arxiv.org/abs/2610.18859
AB - We prove that there exists an absolute constant c > 0 such that the following holds for every k ≥ 3 and p ≥ n^−c / log log k. Letting δ> 0 and D ∼ [n]_p, with high probability every S ⊂ [n] with |S| ≥ δn contains a k-term arithmetic progression whose common difference lies in D. This improves the best known bounds for the threshold of Szemerédi's theorem with random differences for all sufficiently large k, previously of the form p ≥ n^−2/k+o(1), due to Briët and Castro-Silva. We obtain our improvement via a small cover lemma, in the sense of Alon and Pham's work on random Cayley graphs, and its proof crucially relies on a construction of Green and Ruzsa in the context of the arithmetic Kakeya conjecture. The usage of the latter was suggested to us by GPT 6 Astra.
ER -