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.
From: Younes Mouhib [view email]
[v1]
Sat, 20 Jun 2026 17:23:39 UTC (432 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。