Quantitative Hales-Jewett bounds and exact binary calibration

Definitions and mathematical statement

For integers $q\ge2$ and $n\ge1$, let $[q]^n$ be the words of length $n$ over the alphabet $[q]=\{1,\ldots,q\}$. A combinatorial line is obtained by choosing a nonempty set of coordinate positions $I$, fixing one letter at every position outside $I$, and making all coordinates in $I$ equal to the same variable letter. Letting that letter run through $[q]$ gives the $q$ words of the line. The variable positions need not be consecutive.

Define $\operatorname{HJ}(q,r)$, for $r\ge2$, as the least $n$ such that every coloring $[q]^n\to[r]$ contains a monochromatic combinatorial line. For $0<\delta\le1$, define $\operatorname{DHJ}(q,\delta)$ as the least $n$ such that every $A\subseteq[q]^n$ satisfying $|A|\ge\delta q^n$ contains a combinatorial line. These are respectively the coloring and density Hales--Jewett thresholds.

The workshop asks for substantially improved, explicit quantitative bounds for both thresholds, ideally approaching their correct growth in the alphabet size and coloring or density parameter. In particular, fixed $q$ with $r\to\infty$, and fixed $q$ with $\delta\downarrow0$, are meaningful asymptotic regimes. Mere finiteness does not answer the quantitative question. The source's word "reasonable" specifies no particular numerical conjecture, so no arbitrary growth bound is inserted here. A density line must contain all $q$ words, not merely two words agreeing on some coordinates.

Short English statement

Obtain sharp usable quantitative bounds for both the coloring and density forms of the Hales–Jewett theorem.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001094 (AIM-COMBINATORICS-0219), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Recent trends in additive combinatorics, item 1.13. Original workshop question underlying AIM-COMBINATORICS-0219. https://aimath.org/WWN/additivecomb/additivecomb.pdf.