How Loose Is 14.7? Measuring the Slack in Square-Free Counting Proofs

A word is square-free if no block of letters ever appears twice in a row. "abcab" is fine; "abab" contains the square "ab·ab". Such a word is extremal if inserting any letter at any position creates a square. Extremal square-free words exist over three letters, and Grytczuk et al. conjectured that none exist over four or more. The best proof, No extremal square-free words over large alphabets, gets only as far as $k \ge 17$ letters. It shows that any square-free word of length $n$ has fewer than $14.7n$ ways in which a single insertion completes a square. Blocking every insertion slot needs roughly $(k-2)n$ such completions, so the counting fails for large $k$. The gap from 4 to 16 comes down to one constant, 14.7, and nobody has measured how far it sits above the truth.

This note proposes to measure it. We will search for square-free words that pack in as many square completions per letter as possible. Each word we find is an explicit, independently checkable witness that no counting proof of this kind can use a constant below the density that word achieves. Collected across alphabet sizes, the witnesses give certified ceilings on what the counting method can ever prove. They tell theorists whether shrinking 14.7 is a viable route to the conjecture or a dead end, and they point at the alphabet sizes where a direct search for extremal words is worth running. We package these results, plus reproductions of neighbouring published computational claims, as an executable ledger of claims. When a published number fails to reproduce, the ledger raises a correction instead of letting the error persist silently.

Core Claim

Let $Q(w)$ be the number of square-completing quadruples in a square-free word $w$. Hong and Zhang define a quadruple $(a,\ell,b,c)$ as the event that inserting letter $c$ at slot $b$ creates a square of half-length $\ell$ starting at position $a$. For words over $k$ letters, define the best achievable density as

$$c^*_k = \limsup_{n\to\infty} \max_{|w|=n} \frac{Q(w)}{n},$$

where the maximum runs over square-free words of length $n$ on $k$ letters. The Hong–Zhang argument proves non-existence of extremal words whenever its upper bound on $c^*_k$ falls below about $k-2$. Two letters per slot are excluded because inserting a copy of either neighbour creates a trivial square of length 2. Any explicit word $w$ gives the rigorous inequality $c^*_k \ge Q(w)/|w|$.

Our claim is that a well-designed search can pin $c^*_k$ down from below tightly enough to split the open range $4 \le k \le 16$ into two regions:

  • In one region, witnesses show that $c^*_k \ge k-2$. Pure counting therefore cannot settle the conjecture there, and a different idea is required.
  • In the other region, the empirical densities sit well below $k-2$. A sharper counting proof is plausible, and the search tells the prover which local configurations drive the count.

The lower bounds are proofs, since each one comes with a witness word. The claim that the densities are "well below" rests on search evidence, and we will label it as heuristic throughout.

This is different from the closest existing work in kind, not only in scale. Hong and Zhang supply the counting technique and the constant 14.7, but report no computation on actual words. Repetitions in Infinite Palindrome-Rich Words uses computation the classical way, as backtracking to certify a bound: its longest rich binary word with critical exponent below 2.700 has length 1339. Nobody has used computation to measure the slack in a counting proof, that is, to test whether the constant being tightened can in principle be tightened enough.

Research Program

The first component is a quadruple counter with a certificate. Given a word, it lists every insertion slot and every letter, and records each square the insertion creates. It checks square-freeness of the original word with a standard linear-time square detector. It counts each completion once per (slot, letter) pair, and separately counts all quadruples, because Hong and Zhang count every square a single insertion completes. We will write two independent implementations and require them to agree on every reported witness. This gives each number its own replication check, which is the "continuous integration for claims" idea from Treat societally impactful scientific insights as open-source software artifacts. That paper tested the idea with students on the Alexandria prototype; we apply it to a live combinatorial constant.

The second component is density-maximizing search, run for $k = 4,\dots,17$. For small $n$, roughly up to 30–40 depending on $k$, we will run exhaustive branch-and-bound over square-free words modulo letter renaming, to get the exact finite-$n$ maxima. For larger $n$ we will use three methods:

  • beam search that extends words one letter at a time, scored by quadruple density;
  • simulated annealing over edits that preserve square-freeness;
  • a structured family: words built by repeating a high-density exact optimum through morphisms and checking square-freeness. This is the fixed-point construction the rich-word paper uses to go from finite search to infinite words.

Structured witnesses matter because, if they are square-free for every length, they bound the lim sup itself and not only a finite-$n$ maximum.

The third component distinguishes total count from coverage. An extremal word needs every slot blocked, not just a high total. For each witness we will therefore also record the fraction of slots at which all $k-2$ non-neighbour letters complete a square. We will also record the distribution of completions per slot. This shows whether an obstruction lives in the total, which is what the counting proof bounds, or in how completions are spread, which a finer argument would need to exploit.

The fourth component is the claims ledger. The quadruple witnesses become versioned entries: a word, a script, a claimed value, and an independent checker. Neighbouring published computational claims are added as regression tests:

A failure to reproduce produces a signed discrepancy report rather than a silent fix. The retraction literature shows why such reports matter: Retractions relevant to COVID-19 found over 30% of retraction notices gave no clear reason, and a report that states exactly which computation failed avoids that opacity.

Baselines

The naive reference point is the density of typical square-free words. We will generate them by uniformly random extension with backtracking, at the same lengths and on the same compute as our search. If the optimized search barely beats random words, the constant is determined by generic structure, and the search adds little.

The second baseline is nonchalant words: greedy words that always append the earliest valid letter. Hong and Zhang prove these never get stuck for $k \ge 17$, so they are the one construction the source paper itself singles out. We will measure their density at each $k$.

The strongest existing reference is the published bound: fewer than $14.7n$ quadruples, giving non-existence for $k \ge 17$ (No extremal square-free words over large alphabets). This is an upper bound, not a measured density. We searched Lacuna for any reported empirical quadruple density and found none, so there is no measured baseline beyond this bound.

The proposal succeeds in either of two ways. We beat the naive references if the optimized witnesses show clearly higher densities than random and nonchalant words at matched $n$. We produce a decisive result if the witnesses either cross $k-2$ for some $k \le 16$, or leave a gap large enough to name a target constant, which would need to be below 2 to reach $k=4$.

The key ablation is the search objective. We will compare density-maximizing search against search that maximizes the number of fully blocked slots, with identical budgets. This tells us whether total density is the right quantity to chase at all.

Why not just…?

Why not just search directly for extremal square-free words over 4 to 16 letters? This is the most serious alternative, and we will run it: the coverage objective in the ablation is exactly that search. The limitation is that such a search either finds a counterexample, which ends the question immediately, or finds nothing, which proves nothing about infinitely many lengths. Density witnesses turn a null result into information: they say whether a counting proof could ever close the case. The two searches share infrastructure, so doing both costs little extra.

Why not just prove it with Walnut? Walnut decides first-order statements about automatic sequences. That is why it worked for the balanced-word and rich-word thresholds, where the objects are fixed points of morphisms. Hong and Zhang's bound quantifies over all square-free words, which do not form an automatic family. Walnut can verify our structured witnesses, and we will use it that way, but it cannot compute $c^*_k$.

Why not just ask a language-model verifier to audit the proof and flag the slack? The best evidence says current models cannot judge whether a mathematical argument actually does what it claims. On AutoSupervision, GPT-5.5 reaches only 0.501 verification accuracy on deciding whether revisions resolve reviewer concerns. An explicit witness word is checkable by a short program, with no judgment involved.

Why not just tighten the spacing lemmas analytically? Theorists may well do this. Without measurements, though, they cannot know whether they are chasing a target that exists, and the search tells them which configurations to attack.

Proposed Experiments

The first experiment establishes exact small-$n$ maxima of $Q(w)/n$ for $k=4,\dots,17$. Heuristic search and morphic witnesses then extend these to $n$ in the tens of thousands. The results are reported against the $k-2$ threshold and the 14.7 bound, alongside the random and nonchalant densities. The decisive check is whether any certified witness has density at least $k-2$ for some $k \le 16$. If one does, counting alone cannot finish that case. If none does, the largest certified density becomes the new target constant for provers.

The second experiment is the coverage ablation described in the Baselines section.

The third experiment is the ledger regression suite. It re-runs the 1339-length rich-word search, the $RT(3)\ge 9/4$ backtracking, the balanced-word threshold of 3/2, and the small-$n$ period-set counts. Each is reported as reproduced or discrepant, with the exact failing step.

The outcome that would falsify the value of this program is a simple one: optimized densities that are indistinguishable from random square-free words. That would mean the slack in 14.7 is generic rather than structural, so measuring witnesses would have little to teach the next proof.