The seventh ternary density Hales–Jewett number

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Peter Graham ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

Let cn,3c_{n,3} be the largest size of a subset of {0,1,2}n\{0,1,2\}^n containing no combinatorial line, a triple obtained by varying a nonempty set of coordinates through the same letter while fixing the rest. We give a computer-assisted proof that c7,3=1302c_{7,3}=1302, confirming Polymath1's tentative conjecture and closing its bounds 1302≤c7,3≤13481302\leq c_{7,3}\leq1348, recorded by Tao in 2009 and O'Bryant in 2015. The witness realizes Polymath1's known lower bound. Three auxiliary SAT bounds, slicing and global alphabet symmetry give sixteen main slice obligations. Refutations of all nineteen formulas were accepted by FRAT-rs, and in a separate earlier production campaign by drat-trim's lrat-check. Formal verification applies to certificate checking: cake_lpr, verified in HOL4 and compiled with CakeML, accepted refutations of all nineteen formulas across two regeneration campaigns. The SAT encodings, cap induction, symmetry reduction, case cover and counting interpretation are justified by the written proof and separate executable checks; they are outside that formal verification.

Author comments: Zenodo archive: https://doi.org/10.5281/zenodo.23752609. Paper text license: CC BY 4.0. The published code and data are governed by the licenses in the tagged release. Release archive folders: checks, data.

Provenance statement

The proofs, the search code, the certificate checkers and the text were produced by AI models, working under the author's direction. Human understanding (author): I follow the statements, not every proof step.

References

  1. H. Furstenberg and Y. Katznelson, A density version of the Hales--Jewett theorem , J. Anal. Math. 57 (1991), 64--119.
  2. D.H.J. Polymath, A new proof of the density Hales--Jewett theorem , Ann. of Math. 175 (2012), 1283--1327, doi:10.4007/annals.2012.175.3.6 (https://doi.org/10.4007/annals.2012.175.3.6).DOI
  3. D.H.J. Polymath, Density Hales--Jewett and Moser numbers , in An Irregular Mind, Bolyai Society Mathematical Studies 21, Springer, 2010, pp. 689--753, arXiv:1002.0374v2 (https://arxiv.org/abs/1002.0374v2); doi:10.1007/978-3-642-14444-8_22 (https://doi.org/10.1007/978-3-642-14444-8_22).arXivDOI
  4. T. Tao, DHJ(3): 900--999 (Density Hales-Jewett type numbers) , Polymath discussion post, March 4, 2009, https://terrytao.wordpress.com/2009/03/04/dhj3-900-999-density-hales-jewett-type-numbers/.link
  5. K. O'Bryant, Sets of Natural Numbers with Proscribed Subsets , J. Integer Seq. 18 (2015), Article 15.7.7, https://cs.uwaterloo.ca/journals/JIS/VOL18/OBryant/obr3.pdf.link
  6. OEIS Foundation, A156989: density Hales--Jewett numbers for an alphabet of size 3 (https://oeis.org/A156989).link
  7. Y. Mouhib, Lower Bounds for the Hales--Jewett Numbers via Symmetric and One-Weight Colorings , arXiv:2606.22155v2 (https://arxiv.org/abs/2606.22155v2), 2026.arXiv
  8. N. Conlon, N. Farnsworth and A. Robertson, On Hales--Jewett and Related Numbers , arXiv:2607.18111v1 (https://arxiv.org/abs/2607.18111v1), 2026.arXiv
  9. S. Shelah, HJ numbers revisited , arXiv:2607.14732v3 (https://arxiv.org/abs/2607.14732v3), 2026.arXiv
  10. G. Dahia, DensityHalesJewett , formalization of the Dodos--Kanellopoulos--Tyros proof, https://github.com/gdahia/DensityHalesJewett, 2026.link
Show all 20 referencesShow fewer references
  1. P. Graham, The seventh ternary density Hales--Jewett number , version 1, posted October 20, 2026, doi:10.5281/zenodo.23491269 (https://doi.org/10.5281/zenodo.23491269).DOI
  2. P. Graham, The seventh ternary density Hales--Jewett number , version 2, posted October 20, 2026, doi:10.5281/zenodo.23509560 (https://doi.org/10.5281/zenodo.23509560).DOI
  3. P. Graham, The seventh ternary density Hales--Jewett number , version 3, posted October 21, 2026, doi:10.5281/zenodo.23532529 (https://doi.org/10.5281/zenodo.23532529).DOI
  4. P. Graham, The seventh ternary density Hales--Jewett number , version 4, posted October 22, 2026, doi:10.5281/zenodo.23572685 (https://doi.org/10.5281/zenodo.23572685).DOI
  5. A. Biere, T. Faller, K. Fazekas, M. Fleury, N. Froleyks and F. Pollitt, CaDiCaL 2.0 , CAV 2024, LNCS 14681, pp. 133--152, doi:10.1007/978-3-031-65627-9_7 (https://doi.org/10.1007/978-3-031-65627-9_7).DOI
  6. L. Cruz-Filipe, M. J. H. Heule, W. A. Hunt Jr., M. Kaufmann and P. Schneider-Kamp, Efficient Certified RAT Verification , CADE 2017, LNCS 10395, pp. 220--236, doi:10.1007/978-3-319-63046-5_14 (https://doi.org/10.1007/978-3-319-63046-5_14).DOI
  7. N. Wetzler, M. J. H. Heule and W. A. Hunt Jr., DRAT-trim: Efficient Checking and Trimming Using Expressive Clausal Proofs , SAT 2014, LNCS 8561, pp. 422--429, doi:10.1007/978-3-319-09284-3_31 (https://doi.org/10.1007/978-3-319-09284-3_31).DOI
  8. S. Baek, M. Carneiro and M. J. H. Heule, A Flexible Proof Format for SAT Solver-Elaborator Communication , TACAS 2021, LNCS 12651, doi:10.1007/978-3-030-72016-2_4 (https://doi.org/10.1007/978-3-030-72016-2_4).DOI
  9. Y. K. Tan, M. J. H. Heule and M. O. Myreen, cake_lpr: Verified Propagation Redundancy Checking in CakeML , TACAS 2021, doi:10.1007/978-3-030-72013-1_12 (https://doi.org/10.1007/978-3-030-72013-1_12).DOI
  10. R. Kumar, M. O. Myreen, M. Norrish and S. Owens, CakeML: A Verified Implementation of ML , POPL 2014, pp. 179--191, doi:10.1145/2535838.2535841 (https://doi.org/10.1145/2535838.2535841).DOI

Version history

  1. v1 · 7 pagesSubmitted by P. GrahamZenodo archive: https://doi.org/10.5281/zenodo.23752609. Paper text license: CC BY 4.0. The published code and data are governed by the licenses in the tagged release. Release archive folders: checks, data.CurrentNov 21, 2026