Quasipolynomial Bounds for Arithmetic Progressions
Source: github.com/openai/math/tree/main/preprints/Quasipolynomial-…
We prove Erdős's conjecture that every set of positive integers with divergent reciprocal sum contains arithmetic progressions of every finite length. More quantitatively, for every fixed k ≥ 3, we show $\displaystyle r_k(N)\le C_kN\exp\bigl(-c_k(\log N)^{\varepsilon_k}\bigr)$ with $C_k,c_k,\varepsilon_k\gt 0$, where $r_k(N)$ is the largest size of a subset of $\{1,\ldots,N\}$ with no nonconstant k -term arithmetic progression.
Comments and reviews
No comments yet.
Discussed elsewhere
any set of positive integers with divergent reciprocal sum contains arbitrarily long arithmetic progressions, with quasipolynomial quantitative bounds in Szemerédi’s theorem. Sidorenko’s conjecture. I described Sidorenko’s conjecture , which predicts that a fixed bipartite graph has at least the…
— Andrew Lott (@AndrewLott1331) Oct 8, 2026
— Thomas Bloom (@thomasfbloom) Oct 8, 2026
API
curl /api/v1/records/openai-math/Quasipolynomial-Bounds-for-Arithmetic-Progressions
curl -X POST /api/v1/records/openai-math/Quasipolynomial-Bounds-for-Arithmetic-Progressions/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Quasipolynomial-Bounds-for-Arithmetic-Progressions/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
Conjectures that I thought would not be proved in my lifetime....wereblog.computationalcomplexity.orgBill Gasarch
What was known? In 2020, Bloom and Sisask showed that \(A\) contains a 3-term arithmetic progression. See here . The general result for 4-term progressions was open. OpenAI proved the entire conjecture . Lean-formalized . This is widely considered a very hard problem. I didn't think this…