HEXAGONbeta

Succinct Rabung certificates and recurrence-closed lower bounds for van der Waerden numbers

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatoricsmath.NT — Number Theory

Contributed by Brice Pouly ↗

Version 1 / Oct 20, 2026 / CC BY 4.0

Abstract

Rabung's power-residue construction describes a large progression-free colouring by a prime, a colour count and a target length. We give six additional primitive certificates, checked by full ordinary CPU scans, which yield fourteen direct lower bounds. In colour-first notation, these include W(3,17)>33 166 190 897W(3,17)>33\,166\,190\,897, W(3,18)>100 289 348 022W(3,18)>100\,289\,348\,022, W(3,19)>259 446 988 783W(3,19)>259\,446\,988\,783 and W(3,20)>326 368 775 450W(3,20)>326\,368\,775\,450. The larger ternary primes lie outside the complete census below 2322^{32}. We prove the equivalence of the run and boundary tests with Rabung's criterion and separate pointwise verification from discovery. A finite closure of explicitly identified earlier constructions places the new bounds in context: direct ternary certificates win through length 2323; Berlekamp and binary recurrence inputs win thereafter. Exact-modulus cyclic witnesses also give six-colour product bounds. The previously published thirteen-claim evidence and its closed empirical analyses are retained separately. Comparisons refer to the stated source catalogue, without an exhaustive global priority or optimality claim.

Provenance statement

The following declaration describes the research and the published source edition: Artificial-intelligence systems assisted with method and proof development, computational code, campaign planning and analysis, literature and source checking, and drafting and revision. The work used Anthropic's Claude and OpenAI Codex in ChatGPT Work, including GPT-6 Astra. Under the author's direction, these systems created or substantially developed the project's original computational code. Pre-existing code consulted from Daniel Monroe's project is attributed to its source and is not claimed as original work or redistributed here. For this Hexagon deposit, OpenAI Codex assisted source packaging, compilation checks and the preparation of submission metadata. This preparation does not constitute independent mathematical peer review. The published edition used for this deposit, including its supplementary source material, is available at https://doi.org/10.5281/zenodo.23337824. At the time of preparation for Hexagon, the submitter declares the text primarily AI-generated and declares that no part of the contribution has been checked and understood by a human.

References

  1. Elwyn R. Berlekamp. A construction for partitions which avoid long arithmetic progressions. Canadian Mathematical Bulletin , 11 0 (3): 0 409--414, 1968. 10.4153/CMB-1968-047-7.DOI
  2. Thomas Blankenship, Jay Cummings, and Vladislav Taranchuk. A new lower bound for van der W aerden numbers. European Journal of Combinatorics , 69: 0 163--168, 2018. 10.1016/j.ejc.2017.10.007.DOI
  3. Marcelo Campos, Jacob Fox, and Carl Schildkraut. A new lower bound for two-color van der W aerden numbers. arXiv:2608.20824v1, August 2026. URL https://arxiv.org/abs/2608.20824v1. Version 1, 21 August 2026.arXiv
  4. Jacob Fox and Zach Hunter. Three-color van der W aerden numbers grow super-exponentially. arXiv:2606.02541v1, June 2026. URL https://arxiv.org/abs/2606.02541v1. Version 1, 1 June 2026.arXiv
  5. William Gasarch and Bernhard Haeupler. Lower bounds on van der Waerden numbers: randomized- and deterministic-constructive. The Electronic Journal of Combinatorics , 18 0 (1): 0 P64, 2011. 10.37236/551.DOI
  6. P. R. Herwig, M. J. H. Heule, P. M. van Lambalgen, and H. van Maaren. A new method to construct lower bounds for van der W aerden numbers. The Electronic Journal of Combinatorics , 14 0 (1): 0 R6, 2007. 10.37236/925.DOI
  7. Zach Hunter. Lower bounds for multicolor van der Waerden numbers. Israel Journal of Mathematics , 267: 0 783--795, 2025. 10.1007/s11856-025-2735-0. Published online 17 February 2025.DOI
  8. Karen R. Johannson. Variations on a theorem by van der Waerden . Master's thesis, University of Manitoba, Winnipeg, Manitoba, May 2007. URL https://hdl.handle.net/1993/321. Master of Science thesis.link
  9. Jakub Kozik and Dmitry Shabanov. Improved algorithms for colorings of simple hypergraphs and applications. Journal of Combinatorial Theory, Series B , 116: 0 312--332, 2016. 10.1016/j.jctb.2015.09.004. URL https://arxiv.org/abs/1409.6921v1. Theorem numbering cited from arXiv:1409.6921v1, 24 September 2014.arXivDOI
  10. Bruce M. Landman and Aaron Robertson. Ramsey Theory on the Integers , volume 24 of Student Mathematical Library . American Mathematical Society, Providence, RI, 2004. 10.1090/stml/024.DOI
Show all 24 referencesShow fewer references
  1. Bruce M. Landman and Aaron Robertson. Ramsey Theory on the Integers , volume 73 of Student Mathematical Library . American Mathematical Society, Providence, RI, 2 edition, 2014. 10.1090/stml/073.DOI
  2. Meilian Liang, Xiaodong Xu, Zehui Shao, and Baoxin Xiu. Lower bounds on some van der W aerden numbers based on quadratic residues. Journal of Combinatorial Mathematics and Combinatorial Computing , 83: 0 23--31, 2012. URL https://combinatorialpress.com/jcmcc-articles/volume-083/lower-bounds-on-some-van-der-waerden-numbers-based-on-quadratic-residues/.link
  3. Daniel Monroe. New lower bounds for van der Waerden numbers using distributed computing. arXiv:1603.03301v1, March 2016. URL https://arxiv.org/abs/1603.03301v1. Version 1, 9 March 2016.arXiv
  4. Daniel Monroe. New lower bounds for van der Waerden numbers using distributed computing. arXiv:1603.03301v4, November 2017. URL https://arxiv.org/abs/1603.03301v4. Version 4, 6 November 2017.arXiv
  5. Daniel Monroe. Direct Rabung tally distributed with the van der Waerden search code. Versioned project data file, 2019. URL https://github.com/hmonroe/vdw/blob/7000ad7d99cb779ae82b495d709f4a4e23fa7eef/output.txt. Immutable file revision introduced 6 March 2019; detailed provenance in the accompanying registry.link
  6. Daniel Monroe. BOINC phase-2 bounds table. Internet Archive capture of http://vdwnumbers.org/bounds.txt, 2021. URL https://web.archive.org/web/20220428101631id_/http://vdwnumbers.org/bounds.txt. Source header dated 18 August 2021; surviving final capture of 28 April 2022; detailed chronology and hashes in the accompanying registry.link
  7. Daniel Monroe. Projects. Personal website, https://daniel-monroe.github.io/projects.html, 2025. URL https://github.com/daniel-monroe/daniel-monroe.github.io/blob/825778cca5e669cbf60140e35170113603010076/projects.html. Immutable revision of 28 March 2026; accessed 29 August 2026.link
  8. Daniel Monroe. New lower bounds for Van der Waerden numbers using distributed computing. Journal of Combinatorial Mathematics and Combinatorial Computing , 128: 0 305--315, 2026. 10.61091/jcmcc128-19. Published online 4 December 2025.DOI
  9. Tom á s Oliveira e Silva. Tables of values of π(x)\pi(x) and of π2(x)\pi_2(x). University of Aveiro; data file https://sweet.ua.pt/tos/primes/1d09.txt.gz, 2005. URL https://web.archive.org/web/20160704031247id_/http://sweet.ua.pt/tos/primes/1d09.txt.gz. Table of π(k⋅109)\pi(k\cdot10^9) last updated 23 January 2005; accessed 28 August 2026.link
  10. John Rabung and Mark Lotts. Improving the use of cyclic zippers in finding lower bounds for van der W aerden numbers. The Electronic Journal of Combinatorics , 19 0 (2): 0 P35, 2012. 10.37236/2363.DOI
  11. John R. Rabung. Some progression-free partitions constructed using Folkman's method. Canadian Mathematical Bulletin , 22 0 (1): 0 87--91, 1979. 10.4153/CMB-1979-012-1.DOI
  12. Jonathan Sorenson and Jonathan Webster. Strong pseudoprimes to twelve prime bases. Mathematics of Computation , 86 0 (304): 0 985--1003, 2017. 10.1090/mcom/3134.DOI
  13. Xiaodong Xu. A generalization of sets without long arithmetic progressions based on Szekeres algorithm. Journal of Number Theory , 133 0 (11): 0 3670--3677, 2013. 10.1016/j.jnt.2013.05.008.DOI
  14. B. Pouly. Succinct Rabung certificates and recurrence-closed lower bounds for van der Waerden numbers , published edition v1.0.0, 2026. doi:10.5281/zenodo.22980965 (https://doi.org/10.5281/zenodo.22980965).DOI

Version history

  1. v1Submitted by Brice PoulyInitial depositCurrentOct 18, 2026