Improved Lower Bounds for the Hales-Jewett Numbers via Symmetric Colorings

Lorenz Halbeisen; Younes Mouhib

arxiv: 2606.22155 · v1 · pith:N3JDOOVYnew · submitted 2026-06-20 · 🧮 math.CO

Improved Lower Bounds for the Hales-Jewett Numbers via Symmetric Colorings

Younes Mouhib , Lorenz Halbeisen This is my paper

Pith reviewed 2026-06-26 11:43 UTC · model grok-4.3

classification 🧮 math.CO

keywords Hales-Jewett numberscombinatorial linessymmetric coloringslower boundsRamsey theorysimplex reductioncoordinate symmetry

0 comments

The pith

Coordinate-symmetric colorings establish HJ(3,3) at least 22 and HJ(4,2) at least 14.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves two new lower bounds on Hales-Jewett numbers by building explicit colorings of the cube that avoid monochromatic combinatorial lines. It shows that any r-coloring of the t-ary n-cube must contain such a line once n reaches HJ(t,r), and supplies concrete colorings for n=21 with t=3,r=3 and n=13 with t=4,r=2 that contain none. The construction uses coordinate-symmetric colorings that map each point to its vector of letter counts on a discrete simplex. This symmetry turns the global line-free condition into a local check on a small set of corner tuples. The resulting tables, each with fewer than 600 entries, are presented together with a mechanical verification that none of the relevant tuples is monochromatic.

Core claim

The Hales-Jewett number HJ(t,r) is the least n such that every r-coloring of [t]^n contains a monochromatic combinatorial line. The authors exhibit coordinate-symmetric colorings of [3]^21 and [4]^13 with no monochromatic line, thereby proving HJ(3,3)≥22 and HJ(4,2)≥14. A symmetric coloring is line-free precisely when no corner tuple on the simplex of letter-count vectors receives a single color; the published tables satisfy this condition under finite, dependency-free verification.

What carries the argument

Coordinate-symmetric colorings, which assign the same color to all points with the same letter-count vector and reduce line-freeness to the absence of monochromatic corner tuples on the simplex.

If this is right

HJ(3,3) exceeds the prior lower bound of 14 and HJ(4,2) exceeds the prior lower bound of 12.
The line-free condition for symmetric colorings reduces to a constraint-satisfaction problem whose size grows only polynomially with n.
Each new bound rests on an explicit table of color assignments that can be checked by finite enumeration of corner tuples.
The same symmetry reduces the search for larger lower bounds to a computational task whose correctness can be verified independently of any solver.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The simplex reduction may allow systematic search for symmetric colorings at still larger dimensions where brute-force enumeration of the full cube is impossible.
If the reduction lemma extends without change to other Ramsey-type problems on product spaces, similar compressions could apply to van der Waerden or Schur numbers.
The published tables supply concrete objects that later work could attempt to enlarge or combine with non-symmetric colorings to push the bounds further.

Load-bearing premise

A symmetric coloring contains no monochromatic combinatorial line if and only if none of its corner tuples on the letter-count simplex is monochromatic, and the given tables correctly encode colorings satisfying that condition.

What would settle it

Discovery of a monochromatic combinatorial line inside the published 3-coloring of [3]^21 or the published 2-coloring of [4]^13 would show the claimed bounds are false.

read the original abstract

The Hales-Jewett number $\mathrm{HJ}(t,r)$ is the least dimension $n$ in which every $r$-coloring of the cube $[t]^{n}$ contains a monochromatic combinatorial line. We prove $\mathrm{HJ}(3,3)\geq 22$ and $\mathrm{HJ}(4,2)\geq 14$, improving the previous records $\mathrm{HJ}(3,3)\geq 14$ (Farnsworth) and $\mathrm{HJ}(4,2)\geq 12$ (the van der Waerden bound). Both bounds are obtained from coordinate-symmetric colorings, which compress the cube onto the discrete simplex of letter-count vectors; a symmetric coloring is line-free if and only if no corner tuple on the simplex is monochromatic, an exact equivalence that turns line-freeness into a constraint-satisfaction problem of size polynomial in $n$. Each bound is certified by an explicit table of fewer than 600 cells together with a finite, mechanical check of the corner tuples; the SAT solver only finds the witness, while correctness rests on the published table, the reduction lemma, and a dependency-free verification that is in principle hand-auditable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper delivers two concrete lower bound improvements on Hales-Jewett numbers through an explicit symmetric-coloring construction that reduces to a small verifiable table.

read the letter

The punchline is that this work raises the known lower bound for HJ(3,3) from 14 to 22 and for HJ(4,2) from 12 to 14. Both come from coordinate-symmetric colorings of the simplex of letter-count vectors, together with a reduction lemma that equates line-freeness in the cube to the absence of monochromatic corner tuples.

What stands out is the method itself. The symmetry compresses the search space and turns the problem into a finite constraint check whose size is polynomial in the dimension. The authors publish the actual color tables (under 600 entries each) and note that correctness rests on those tables plus a mechanical enumeration of corner tuples, not on the SAT run that found them. That separation is useful: anyone can in principle audit the published data without re-running the solver.

The bounds are incremental rather than transformative, and the paper stays inside the narrow lane of explicit Ramsey numbers. No broader applications or connections to other theorems are developed. The reduction lemma is stated cleanly, but its proof is only sketched in the abstract; a referee would want the full argument written out with all cases.

This is the sort of paper that matters to people who track exact values in Hales-Jewett and van der Waerden territory. The explicit witnesses and the new reduction technique give it enough substance to justify referee time. I would send it out for review.

Referee Report

0 major / 3 minor

Summary. The manuscript proves new lower bounds HJ(3,3) ≥ 22 and HJ(4,2) ≥ 14 for the Hales-Jewett numbers. The bounds are obtained from explicit coordinate-symmetric colorings of the cube that compress to colorings of the letter-count simplex; a reduction lemma equates line-freeness in the cube with the absence of monochromatic corner tuples on the simplex. Each bound is witnessed by a published table of fewer than 600 color assignments together with a finite mechanical enumeration verifying that no corner tuple is monochromatic.

Significance. If the tables and reduction lemma hold, the results improve the previous records of 14 and 12 by a meaningful margin and supply the first explicit, auditable certificates for these values. The symmetric-coloring reduction converts an exponential search into a polynomial-size constraint-satisfaction problem whose correctness is independent of the SAT solver that discovered the tables; this verifiability is a clear methodological advance for constructive lower bounds in Ramsey theory.

minor comments (3)

The reduction lemma is stated in the abstract but its proof should appear in a dedicated subsection with an explicit statement of the corner-tuple definition and a short worked example for n=3 or n=4 so that the mechanical check can be followed by hand.
Tables 1 and 2 (or whichever contain the color assignments) should be accompanied by a machine-readable supplementary file or at least a clear row/column legend indicating the ordering of the simplex points; the current printed format makes independent verification unnecessarily tedious.
[Abstract] The sentence attributing the prior HJ(4,2) ≥ 12 bound to “the van der Waerden bound” would benefit from a precise citation to the relevant van der Waerden number or theorem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of the methodological advance in the symmetric-coloring reduction, and the recommendation of minor revision. No specific major comments were raised.

Circularity Check

0 steps flagged

No circularity; bounds rest on explicit tables and mechanical verification

full rationale

The derivation establishes lower bounds HJ(3,3)≥22 and HJ(4,2)≥14 via published explicit colorings of the simplex (fewer than 600 cells) together with a finite enumeration of corner tuples. The reduction lemma is stated as an exact if-and-only-if equivalence between line-freeness in the cube and absence of monochromatic corners on the simplex; this is a direct combinatorial identity, not a self-definition or fitted relation. No parameter is fitted and then renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no self-citation chain carries the central claim. The SAT solver is used only for discovery; correctness is certified by the published table and the dependency-free check, making the argument self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on one reduction lemma (symmetric coloring line-free iff no monochromatic corner tuple) and the correctness of two finite tables; no free parameters or invented entities are introduced.

axioms (1)

domain assumption A symmetric coloring of the cube is line-free if and only if no corner tuple on the letter-count simplex is monochromatic.
This equivalence is invoked to turn the exponential coloring problem into a polynomial constraint-satisfaction problem on the simplex.

pith-pipeline@v0.9.1-grok · 5744 in / 1331 out tokens · 26994 ms · 2026-06-26T11:43:09.757667+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

One-Weight Colorings, the Symmetric Class, and Lower Bounds for Hales--Jewett Numbers
math.CO 2026-07 unverdicted novelty 7.0

Symmetric colorings of Hales-Jewett cubes coincide with one-weight colorings, reducing the symmetric lower-bound problem to 1D Gallai homothety coloring and yielding HJ(3,3)≥22 and HJ(4,2)≥14.

Reference graph

Works this paper leans on

10 extracted references · 2 canonical work pages · cited by 1 Pith paper · 1 internal anchor

[1]

Regularityandpositionalgames,

A.W.HalesandR.I.Jewett,“Regularityandpositionalgames,”Trans- actions of the American Mathematical Society, vol. 106, no. 2, pp. 222– 229, 1963.doi:10.1090/S0002-9947-1963-0143712-1

work page doi:10.1090/s0002-9947-1963-0143712-1 1963
[2]

Primitive recursive bounds for van der waerden numbers,

S. Shelah, “Primitive recursive bounds for van der waerden numbers,” Journal of the American Mathematical Society, vol. 1, no. 3, pp. 683– 697, Jul. 1988,issn: 0894-0347.doi:10 . 1090 / S0894 - 0347 - 1988 - 0929498-X

1988
[3]

The first nontrivial Hales–Jewett number is four,

N. Hindman and E. Tressler, “The first nontrivial Hales–Jewett number is four,”Ars Combinatoria, vol. 113, pp. 385–390, 2014

2014
[4]

An upper bound for the Hales-Jewett number HJ(4,2)

M. Lavrov, “An upper bound for the Hales–Jewett number HJ(4,2),” SIAM Journal on Discrete Mathematics, vol. 30, no. 2, pp. 1333–1342, 2016, arXiv:1504.02753.doi:10.1137/15M1016485

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/15m1016485 2016
[5]

Farnsworth,A computational approach to improving bounds on the hales–jewett numbers, 2026

N. Farnsworth,A computational approach to improving bounds on the hales–jewett numbers, 2026. [Online]. Available:https://sites.math. rutgers.edu/~zeilberg/expmath/farnsworth26.pdf

2026
[6]

Mouhib,Improving lower bounds on hales–jewett numbers: Symmet- ric colorings, sat solvers, line-family variants, and forcing structures, 2026

Y. Mouhib,Improving lower bounds on hales–jewett numbers: Symmet- ric colorings, sat solvers, line-family variants, and forcing structures, 2026

2026
[7]

D. H. J. Polymath,Density hales-jewett and moser numbers, 2010. arXiv:1002 . 0374 [math.CO]. [Online]. Available:https : / / arxiv . org/abs/1002.0374

Pith/arXiv arXiv 2010
[8]

Hyper-optimistic conjecture

D.H.J. Polymath. “Hyper-optimistic conjecture.” Polymath1 project wiki page, Accessed: Jun. 12, 2026. [Online]. Available:https : / / michaelnielsen.org/polymath/index.php?title=Hyper-optimistic_ conjecture

2026
[9]

Beweis einer baudetschen vermutung,

B. L. van der Waerden, “Beweis einer baudetschen vermutung,” Ger- man,Nieuw Archief voor Wiskunde, vol. 15, pp. 212–216, 1927

1927
[10]

Some unknown van der Waerden numbers,

V. Chvátal, “Some unknown van der Waerden numbers,” inCombina- torial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, et al., Eds., MR 0266891, New York: Gordon and Breach, 1970, pp. 31– 33. REFERENCES 9 AppendixA.Verification Beyond the reduction lemma, the correctness of Theorems 4.1 and 4.2 rests only on a finite check of the corner tup...

1970

[1] [1]

Regularityandpositionalgames,

A.W.HalesandR.I.Jewett,“Regularityandpositionalgames,”Trans- actions of the American Mathematical Society, vol. 106, no. 2, pp. 222– 229, 1963.doi:10.1090/S0002-9947-1963-0143712-1

work page doi:10.1090/s0002-9947-1963-0143712-1 1963

[2] [2]

Primitive recursive bounds for van der waerden numbers,

S. Shelah, “Primitive recursive bounds for van der waerden numbers,” Journal of the American Mathematical Society, vol. 1, no. 3, pp. 683– 697, Jul. 1988,issn: 0894-0347.doi:10 . 1090 / S0894 - 0347 - 1988 - 0929498-X

1988

[3] [3]

The first nontrivial Hales–Jewett number is four,

N. Hindman and E. Tressler, “The first nontrivial Hales–Jewett number is four,”Ars Combinatoria, vol. 113, pp. 385–390, 2014

2014

[4] [4]

An upper bound for the Hales-Jewett number HJ(4,2)

M. Lavrov, “An upper bound for the Hales–Jewett number HJ(4,2),” SIAM Journal on Discrete Mathematics, vol. 30, no. 2, pp. 1333–1342, 2016, arXiv:1504.02753.doi:10.1137/15M1016485

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/15m1016485 2016

[5] [5]

Farnsworth,A computational approach to improving bounds on the hales–jewett numbers, 2026

N. Farnsworth,A computational approach to improving bounds on the hales–jewett numbers, 2026. [Online]. Available:https://sites.math. rutgers.edu/~zeilberg/expmath/farnsworth26.pdf

2026

[6] [6]

Mouhib,Improving lower bounds on hales–jewett numbers: Symmet- ric colorings, sat solvers, line-family variants, and forcing structures, 2026

Y. Mouhib,Improving lower bounds on hales–jewett numbers: Symmet- ric colorings, sat solvers, line-family variants, and forcing structures, 2026

2026

[7] [7]

D. H. J. Polymath,Density hales-jewett and moser numbers, 2010. arXiv:1002 . 0374 [math.CO]. [Online]. Available:https : / / arxiv . org/abs/1002.0374

Pith/arXiv arXiv 2010

[8] [8]

Hyper-optimistic conjecture

D.H.J. Polymath. “Hyper-optimistic conjecture.” Polymath1 project wiki page, Accessed: Jun. 12, 2026. [Online]. Available:https : / / michaelnielsen.org/polymath/index.php?title=Hyper-optimistic_ conjecture

2026

[9] [9]

Beweis einer baudetschen vermutung,

B. L. van der Waerden, “Beweis einer baudetschen vermutung,” Ger- man,Nieuw Archief voor Wiskunde, vol. 15, pp. 212–216, 1927

1927

[10] [10]

Some unknown van der Waerden numbers,

V. Chvátal, “Some unknown van der Waerden numbers,” inCombina- torial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, et al., Eds., MR 0266891, New York: Gordon and Breach, 1970, pp. 31– 33. REFERENCES 9 AppendixA.Verification Beyond the reduction lemma, the correctness of Theorems 4.1 and 4.2 rests only on a finite check of the corner tup...

1970