The Hales–Jewett Explorer

A combinatorial line is generated by a root τ ∈ ([t] ∪ {∗})ⁿ with at least one ∗: the line L_τ = {τ(1), …, τ(t)} replaces every ∗ by the letter a. Over [4], the root 2∗1∗ generates {2111, 2212, 2313, 2414}. Its active set I(τ) is the set of starred coordinates; the all-active line is the diagonal.

Chapter 6 relaxes the rigid ascent. Identify [t] with ℤ_t (letter t ↔ 0) and take cosets L = a + ⟨v⟩ of order-t cyclic subgroups: cyclic lines use any valid direction v ∈ (ℤ_t^× ∪ {0})ⁿ \ {0}; unit lines restrict to v ∈ {0,1}ⁿ; geometric lines to v ∈ {−1,0,1}ⁿ — the ±-roots where ∗ ascends and ∗̄ descends, i.e. the tic-tac-toe lines. The containments (6.1) hold: comb ⊆ unit, geom ⊆ cyclic, and for t ≥ 3 unit and geometric are incomparable.

The explorer enumerates each family from the definition and checks the count against the formula on every parameter change. Already at (3, 2) the four numbers separate completely: HJ_cyc(3,2) = 2 < HJ_unit = HJ_geom(3,2) = 3 < HJ(3,2) = 4 — try t = 3, n = 2, family cyclic, then Find line-free: the search proves none exists, and Min # mono lines returns 2 (Prop. 7.9).

A colouring invariant under all coordinate permutations factors through the type map w ↦ (a₁, …, a_t), the letter counts, onto the simplex T⁽ᵗ⁾ₙ of size C(n+t−1, t−1) — polynomial against the tⁿ words (Lemma 2.4). On the simplex, a line with k active coordinates and inactive type v becomes the corner tuple C_k,v = {v + k·e₁, …, v + k·e_t}, and Lemma 3.1 says: the symmetric colouring is line-free iff no corner tuple is monochromatic. The simplex panel above performs exactly this check and stays in sync with the grid.

A one-weight colouring reads a single integer weight, c_ω,χ(w) = χ(⟨ω, type(w)⟩); sum-type is ω = (1, …, t), where the level is σ(w). Under it a line carries the homothet b + k·S_ω of the weight set (Lemma 2.14) — the level strip shows this. By the radix argument (Theorem 3.5) one-weight colourings realise the entire symmetric class in every fixed dimension: the hierarchy sum ⊆ ow ⊆ sym is flat above ow.

The quantitative payoff of the thesis: single explicit weights give the records HJ(3,3) ≥ 22 via ω = (0, 1, 29) and HJ(4,2) ≥ 14 via ω = (0, 2, 3, 5) with a 26-periodic palette. Load the presets Record palette mod 26 (t = 4) and ω=(0,5,7), ψ mod 13 (t = 3): both are line-free on every grid this page can show, and the second avoids monochromatic lines with ≤ 12 active coordinates in every dimension (Thm 4.10).

The preset Record slice (Table A.1) restricts that 253-cell witness to [3]³ by the monotonicity shift of Lemma 3.3.

Under a one-weight colouring, a line with k active coordinates and inactive type v carries the homothet ⟨ω,v⟩ + k·S_ω of the weight set (Lemma 2.14) — line-freeness on the grid is homothety-avoidance on ℤ. Proposition 2.19 gives the algebraic form: for S = {s₁ < … < s_t} there is a homogeneous system E_s of t − 2 equations, each with coefficient sum zero — hence partition regular by Rado's criterion — whose integer solutions are exactly a·1 + d·s. The injective ones (d ≠ 0) are, as sets, the homothets of S for d ≥ 1 and of the reflected −S for d ≤ −1.

Example 2.20. For S = {0,1,3} the system is the single equation z + 2x = 3y, whose injective solutions are the triples {a, a+d, a+3d}. Since the grid realises only positive scales, the search for a line-free one-weight colouring at ω = (0,1,3) is homothety-avoidance for {0,1,3} alone, whereas the Rado number of the equation demands avoiding the reflected pattern {0,2,3} as well. The live panel above counts both on the current palette — the two can genuinely differ.

Remark 2.24 (a correction). An explicit 4-colouring of 56 consecutive integers is free of monochromatic injective solutions of z + 2x = 3y — both patterns at once — giving R₄(z + 2x = 3y) ≥ 57 and refuting the reported values R₄ = 44 and N_max(3,4) = 43 of Dumitru–Prunescu. The window certificate for {0,1,3}-avoidance alone reaches length 93 (G₄({0,1,3}) ≥ 94), yet its grid bound of 31 is weaker than the van der Waerden shadow HJ(3,4) ≥ 38 — the two thresholds are distinct.

Through Theorem 2.15 every pattern carries a lower bound, HJ(t, r) ≥ ⌈(G_r(S) − 1)/D_S⌉, with van der Waerden as the arithmetic case; the panel matches your current S₀ against the Gallai numbers computed in the thesis (Table 2.1): G₃({0,1,3}) = 42, G₃({0,1,4}) = 57, G₃({0,2,5}) ≥ 77, G₂({0,2,3,5}) = 67, G₂({0,1,5,6}) = 80.

For t = 2 the responsible structure is a clique: G₂(n) is the comparability graph of the Boolean lattice, its cliques are the chains, and Mirsky's theorem gives χ = n+1, whence HJ(2,r) = r (Prop. 7.1) — set t = 2 above to see the pigeonhole chain. For t ≥ 3 vertices are the lines and each edge carries its unique intersection word (linearity, Lemma 7.3); a colouring of the grid induces the edge colouring c̃(e) = c(x_e), and a line is monochromatic iff its star is (Lemma 7.5) — hover a vertex to watch the dictionary verify itself. Hovering an edge shows its coherence class: edges sharing a word must share a colour, and Prop. 7.6 shows this constraint is the entire content — random non-coherent edge colourings avoid monochromatic stars in abundance. No pigeonhole certificate survives at t ≥ 3: the line hypergraph has no K⁽ᵗ⁾_t+1 (Prop. 7.7) and, over 𝔽₃, no Fano plane (Prop. 7.8) — forcing families are large asymmetric cores (67 lines on 52 words already at [3]⁴, Prop. 7.10).

Quotienting by the coordinate action turns the symmetric problem into the corner hypergraph C⁽ᵗ⁾ₙ: cells of the simplex as vertices, corner tuples as edges — a linear t-uniform hypergraph in which every cell lies in exactly n edges and each pencil is a complete Kₙ (Lemma 7.19); for t = 3 it is exactly the corners configuration of Ajtai–Szemerédi. Its weak chromatic threshold is the symmetric Hales–Jewett number (Thm 7.21 ii). The toggle exhibits Prop. 7.26: a loopless, cell-rainbow K_t+1 persisting in every dimension — while globally, any clean graph model is degree-starved above n = 2 (Prop. 7.27).

The reformulation pays asymptotically: the Lovász Local Lemma on C⁽ᵗ⁾ₙ gives HJ_sym(t, r) ≥ 2 + ⌊(r^t−1/e − 1)/t⌋ = Ω(r^t−1/t) in two lines (Thm 7.28) — — and the quasipolynomial corners theorem transfers to e^c·log²r ≤ HJ_sym(3, r) ≤ e^{(log r)^C} (Thm 7.31), making the extremality conjecture falsifiable on the asymptotic axis (Cor. 7.32).

L^[K] keeps the lines with at most K active coordinates, L^(q) those whose active set is a union of ≤ q subintervals of [n] (for the coset families, "active set" = support of the direction). The parity colouring σ mod 2 kills every line of L^[1] in any dimension (Prop. 4.1) — load the Parity preset and set the restriction to K = 1. The bracket ceilings are known exactly at small parameters: κ_sum(3,3) = 11, κ_sum(4,2) = 10, κ_sum(4,3) = 96, and non-arithmetic periodic weights pass the van der Waerden ceiling: HJ^[12](3,3) = HJ^[12](4,2) = ∞ (Thms 4.10, 4.11 — both loadable above).

The interval axis is transverse: symmetric colourings are provably blind to it, HJ^(q)_sym = HJ_sym for every q (Prop. 4.15) — the Count symmetric line-free tool therefore ignores an interval restriction and says why. The ceiling λ(3, r) equals r − 1 for odd and r − 2 for even r (Prop. 4.19), and the first nontrivial exact interval value is HJ⁽¹⁾(3) = 5 against HJ(3) = 4 (Thm 4.20).

At t = 3, n = 3, r = 2: Count all line-free returns 1644 and Count symmetric line-free returns 36, exactly — both by backtracking from the definitions, no solver. The verdict banner names the stabiliser class of whatever colouring is on screen, in the vocabulary of the census. Find diagonal-only produces a witness whose unique monochromatic line is the diagonal (Conjecture 4.23's objects).

Table 6.1: the cyclic numbers are logarithmic in r while the classical ones grow at least linearly — a cyclic lower-bound colouring can never transfer. Try t = 2: any two distinct points of ℤ₂ⁿ form a unit line, so line-free = injective and the threshold is ⌈log₂(r+1)⌉ (Prop. 6.1). The rainbow counter in the dossier is the anti-Ramsey side: ah(3, 4) ≥ 25 (Prop. 5.9).