Short··0:21·Combinatorics
Van der Waerden Numbers: OpenAI Claims Superexponential Growth
Watch on YouTubeAbout the problem →
About this video
The van der Waerden number W(k) is the shortest run of whole numbers 1, 2, …, n where every two-colouring must contain k evenly spaced numbers of the same colour: W(3) = 9, W(4) = 35, W(5) = 178. Erdős asked whether these numbers grow faster than any exponential, that is whether W(k)^(1/k) goes to infinity. OpenAI claims a yes with a quantitative bound: W_r(k) greater than k^(c·k·⌊log₂ r⌋) for every number of colours r ≥ 2 and all large k; this is OpenAI's preprint, not yet peer reviewed.
Paper (OpenAI, catalogue result 160):
- Quantitative Superexponential Bounds for van der Waerden Numbers: github.com/openai/math/blob/main/preprints/Quantitative-Super…
The colourings in the animation are real and checked: 1 to 8 with no 3 evenly spaced alike, 1 to 34 with no 4, and the 150-number tower with no 5. 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/160
About the problem
Combinatorics·OpenAI Math·Result 160
Superexponential van der Waerden numbers
Resolves Erdős's superexponential-growth question for van der Waerden numbers. If Wr(k) is the least interval length forcing a monochromatic k-term progression in every r-coloring, then Wr(k) > kck⌊log2 r⌋ for an absolute c > 0, all r ≥ 2 and sufficiently large k, uniformly in r. In particular, Wr(k)1/k → ∞ for each fixed r. (Lean)
Topics
van der Waerden numbersvan der Waerden theoremvan der WaerdenW(k)arithmetic progressionsRamsey theoryErdős problemsuperexponentialtwo colouringsmonochromatic progressioncombinatoricsadditive combinatoricsnumber theorySzemerédiOpenAIOpenAI mathAI mathematicsAI proofmathsmathematicsmath shorts3D animationErdos problemSzemeredi
