Short··0:21·Combinatorics
Erdős Conjecture on Arithmetic Progressions: OpenAI Claims a Proof
Watch on YouTubeAbout the problem →
About this video
Erdős conjectured that any set of whole numbers whose reciprocals add up to infinity, like the primes, must contain equally spaced runs (arithmetic progressions) of every finite length. OpenAI claims a proof, with a quantitative Szemerédi-type bound: for each fixed k ≥ 3, a subset of {1, ..., N} with no k-term progression has at most C·N·exp(−c(log N)^ε) elements. This is OpenAI's preprint, not yet peer reviewed. In the animation the numbers 1 to 1050 are steps of a spiral staircase, 30 per turn, so progressions with a step that is a multiple of 30 stand as straight vertical lines.
Paper (OpenAI, catalogue result 159):
- Quasipolynomial Bounds for Arithmetic Progressions: github.com/openai/math/blob/main/preprints/Quasipolynomial-Bo…
The animation illustrates the result; it is not a proof.
Gradient Damage: mathematics you can see, equations you can hear.
youtube.com/@gradientdamage
Every result explained: gradientdamage.com/p/159
About the problem
Combinatorics·OpenAI Math·Result 159
Erdős’s reciprocal-sum conjecture and quasipolynomial Szemerédi bounds
Proves Erdős's conjecture that every set of positive integers with divergent reciprocal sum contains arithmetic progressions of every finite length. Quantitatively, for each fixed k ≥ 3, every subset of {1,…,N} with no nonconstant k-term progression has size at most CkN exp[-ck(log N)εk], with positive constants depending only on k. (Lean)
Topics
Erdős conjecture on arithmetic progressionsErdős reciprocal sum conjectureErdős–Turán conjecturearithmetic progressionsSzemerédi theoremSzemerédi boundsquasipolynomial boundsGreen–Tao theoremprimes in arithmetic progressionsum of reciprocals of primesadditive combinatoricsnumber theoryPaul ErdőscombinatoricsOpenAIOpenAI mathAI proofErdos conjecture on arithmetic progressionsErdos reciprocal sum conjectureErdos-Turan conjectureSzemeredi
