← All problems

Szemerédi’s theorem with random differences

For fixed k≥3k\ge 3 and δ>0\delta>0, let D∼[n]pD\sim [n]_p be the random subset of [n]={1,…,n}[n]=\{1,\ldots,n\} obtained by including each integer independently with probability pp. Determine the threshold for the property that, with high probability as n→∞n\to\infty, every set S⊆[n]S\subseteq [n] with ∣S∣≥δn|S|\ge \delta n contains a kk-term arithmetic progression x,x+d,…,x+(k−1)d⊆Sx,x+d,\ldots,x+(k-1)d\subseteq S whose common difference dd belongs to DD.

References

Progress summary

Refreshed
Open · progress reported

A new preprint claims a stronger threshold for random differences, but the advance has not been independently verified and the problem remains open.

The problem asks for the threshold at which random allowed differences force arithmetic progressions in every dense set. Earlier work established substantial upper and lower bounds, while a new preprint claims a much stronger upper-bound range.

Known results

  • Altman (2019) related the integer threshold to approximation of dual functions by nilsequences and distinguished the finite-field setting.
  • Briët and Castro-Silva (2023; revised 2024) proved mk∗(N)≪N1−2/k+o(1)m_k^*(N)\ll N^{1-2/k+o(1)}, improving the preceding bound for odd kk.
  • Their finite-group theorem gives mt,ε∗(G)≤C(t,ε)(log⁡∣G∣)2t+3∣G∣1−2/(t+1)m_{t,\varepsilon}^*(G)\le C(t,\varepsilon)(\log |G|)^{2t+3}|G|^{1-2/(t+1)} under a coprimality condition.
  • A 2025 finite-field result supplied improved lower bounds using analytic-rank and partition-rank estimates.

October 2026 claimed threshold improvement

Gabriel Dahia’s preprint claims to improve the threshold from about n−2/k+o(1)n^{-2/k+o(1)} to n−c/log⁡log⁡kn^{-c/\log\log k} for sufficiently large kk, using a small-cover lemma and arithmetic-Kakeya constructions. The claim is unverified; the preprint credits GPT 6 Astra only with suggesting a prior construction, not with proving the theorem.

Current status (as of October 2026): Earlier bounds are established, while the claimed n−c/log⁡log⁡kn^{-c/\log\log k} improvement remains unverified and the exact threshold problem is open.

Sources

Solutions 0

No solutions have been posted yet.