Fabian Arevalo

Computational research note · combinatorics on words · Currie–Mol conjecture

A sharp extremal length for undirected repetition thresholds

k = 22 still openlower bound, elementary proofsharp length n+3
Theorem T1: for every alphabet size n ≥ 5, the longest word over n letters avoiding an undirected repetition of exponent ≥ (n−1)/(n−2) has length exactly n+3, and that longest word is unique.
August 18, 2026 · produced in a Claude Code research session · code, data and certificates in the companion repository.

Start here: no maths required

Pick an alphabet: some fixed number of symbols, say twenty-two of them. Write down the longest string you can using only those symbols, under one rule: no stretch of it is allowed to repeat a pattern too aggressively, not a plain copy glued right after itself, and not a mirror-image copy either. How long can you get before you are forced into a repeat?

"Too aggressively" has a precise meaning. Compare the length of a repeated stretch to the length of just one copy inside it: gluing a block directly against a second copy of itself (ratio close to 2) is the most severe kind of repeat; a copy separated by a long gap (ratio close to 1) barely counts as one. For every alphabet size there ought to be one particular ratio, the threshold, such that repeats less severe than it can be avoided forever, and repeats at least that severe cannot.

Currie and Mol conjectured the exact value of that ratio in 2019: for an alphabet of k symbols, k ≥ 4, it should be exactly (k−1)/(k−2). They proved the easy direction (nothing survives above the ratio) for every k, and by 2021 the hard direction (something survives right at the ratio) had been checked, by hand and by machine, for every alphabet from 4 up to 21 symbols. Above that, at 22 symbols and up, nobody has settled it either way. It is a genuinely open problem, and this session went after the smallest open case, k = 22.

It did not settle it. What came out instead is a smaller, sharp fact that sits one level below the open conjecture and can be nailed down completely: exactly how long a string can survive once you forbid the boundary ratio outright, for every alphabet size at once. And, remarkably, there turns out to be only one longest string, not a family of them.

Alphabet size
The two-sided threshold. Both bars share one log-scaled axis of word length. The upper bar forbids the boundary ratio (k−1)/(k−2) outright, exhaustively, by computer search; the lower bar forbids only ratios strictly above it, allowing the exact boundary value. That one-word difference in the rule, equality permitted or not, is the entire gap between the two bars. Toggle k to see the same cliff at every alphabet size checked.

What this note adds

Before this session: Currie and Mol's own theorem already forces the lower bound (nothing survives above the ratio) for every k ≥ 4; that part was proved in the source papers, not here. Equality had been confirmed for k from 4 to 21. This is the first attempt in this repository at k = 22, and here is what actually came out of it, plainly, with the real numbers (all of it re-checked independently while this page was written; see the technical sections for what that means).

  1. Alphabet size 22 itself is not resolved. No construction of an infinite surviving string was found, and no proof that none exists. That was the actual target, and it is still open.
  2. An exact rule for how long you can go, for every alphabet size at once. Forbidding the boundary ratio outright, the longest possible string has length exactly three more than the alphabet size (n+3), and there is only one such longest string, up to renaming the symbols. At n = 22 that is a string of length 25.
  3. The rule was found by brute force first, then proved by hand. An exhaustive computer search found the same "dies at alphabet-size-plus-three" answer independently at four alphabet sizes (22 through 25), fully exploring search trees of 451, 483, 516 and 550 branches (all four in under a second combined) before the general proof, for every size at once, was written down.
  4. One hairline relaxation and the picture flips completely. Allow the string to touch the boundary ratio exactly, rather than forbidding it outright, and the same alphabet supports a string of length 20,000 with no violation anywhere in it (5,000 at the three neighbouring alphabet sizes); see the figure above.
  5. The obvious shortcut does not exist. A classical two-choice coding trick, used for the ordinary (non-mirrored) version of this kind of threshold, turns out to be completely empty here: at every alphabet size checked, no coded string longer than 4 bits exists. Any real construction has to work in a genuinely three-choice setting instead.
  6. A checklist for finding a real infinite example, proved but not yet satisfied by anything. If you build an infinite string by repeating a fixed substitution rule on blocks of symbols, and that rule passes three checkable tests, the whole infinite string is automatically guaranteed safe. Nobody has yet found a rule that passes all three tests. That is the sharpest open thread this session leaves behind.

Everything below is the technical version: definitions, the theorem and its proof, the certificates behind it, and everything that was tried and failed, kept deliberately, not hidden.

AbstractSummary of results

An undirected r-power is a word xyx′ with x nonempty, x′ ∈ {x, xᴿ} (an exact or mirror-reversed copy of x), and |xyx′|/|xy| = r. The undirected repetition threshold URT(k) is the infimum of the r above which undirected r-powers cannot be avoided forever over an alphabet of k letters. Currie and Mol proved URT(k) ≥ (k−1)/(k−2) for every k ≥ 4, conjectured equality, and confirmed it for 4 ≤ k ≤ 21; it is open for every k ≥ 22 (all secondary: see §1, and §8 for what that label means here). This session attacked k = 22. It did not settle it. It produced: a theorem (T1) that for every n ≥ 5 the longest word over n letters avoiding undirected exponent ≥ (n−1)/(n−2) has length exactly n+3 with a unique extremal word, found first as exhaustive certificates at k = 22..25 and then proved for all n ≥ 5 from the shape of the certificate's case tree; certified U-(21/20)⁺-free words over 22 letters of length 20,000 (and 5,000 at k = 23, 24, 25); a proof that the classical binary Pansiot coding is empty at every alphabet size 20–23 checked; exact reversal-transfer identities for that code; a proved finite-check descent criterion (Theorem D) for uniform-morphic constructions; and certified emptiness of the affine sub-ansatz at k = 22, 23, 24 for all ten admissible multipliers. The general uniform-morphic search remains open and is the sharpest next step.

Section 1Setting

Alphabet Σn = {0, …, n−1}. A word w over Σn is indexed from 0; wᴿ is its reversal.

Definition 1: undirected offender

Fix a rational α = num/den > 1. An undirected offender in w is an occurrence (i, ℓ, g, type) with ℓ ≥ 1, g ≥ 0, and den·(2ℓ+g) > num·(ℓ+g), of either

  • ordinary: w[i .. i+ℓ) = w[i+ℓ+g .. i+2ℓ+g), or
  • reversed: w[i .. i+ℓ) = ( w[i+ℓ+g .. i+2ℓ+g) )ᴿ.

w is U-α⁺-free if it has no undirected offender (exponent exactly α is allowed). Replacing the strict inequality with den·(2ℓ+g) ≥ num·(ℓ+g) defines U-α-free (exponent α itself also forbidden). This matches the factor picture: xyx′ with x′ ∈ {x, xᴿ} has exponent |xyx′|/|xy| = (2ℓ+g)/(ℓ+g).

URT(k) is the infimum of the r such that some infinite word over Σk has no undirected offender of exponent ≥ r secondary. The statements below are phrased to not depend on whether "avoids r-powers" means > r or ≥ r: an infinite U-α⁺-free word shows URT(k) ≤ α either way, and unavoidability of exponent ≥ α shows URT(k) ≥ α either way.

Known, all secondary: taken from search-engine snippets of arXiv:1904.10029, arXiv:2006.07474 (Theoretical Computer Science, 2021), and Shur (Theory of Computing Systems, 2024); the session's sandbox had web access blocked for the actual papers, and none of this has been checked against them: URT(3) = 7/4; URT(k) ≥ (k−1)/(k−2) for k ≥ 4; equality conjectured for all k ≥ 4 and confirmed for 4 ≤ k ≤ 21; open for k ≥ 22; Shur's entropy-compression bounds are asymptotic and decide no individual k.

Four elementary facts follow directly from Definition 1 and are used throughout (fix k = n, α = (n−1)/(n−2), w a U-α⁺-free word over Σn):

LemmaStatementWhy (one line)
L1: gapsequal letters in w sit at distance ≥ n−2distance d gives an ℓ=1 offender of exponent (d+1)/d, which exceeds α exactly when d < n−2
L2: no palindromesw has no palindromic factor of length ≥ 2an even palindrome is a reversed offender with g=0 (exponent 2); an odd one has g=1, and ℓ(n−3) > 1 holds for every ℓ ≥ 1, n ≥ 5
L3: reversed pairsif w[i]w[i+1] = ab and w[j]w[j+1] = ba with j ≥ i+2, then j−i ≥ 2(n−3)+2 (= 40 at n = 22)arm length 2 and gap g = j−i−2 form a reversed offender exactly when g < 2(n−3)
L4: aperiodicityno eventually periodic infinite word is U-α⁺-free, for any finite αa periodic tail of period Q contains ordinary offenders of exponent (Q+ℓ)/Q → ∞

All of the certificates below rest on four independently written checkers of Definition 1 (brute triple loop; run-scan per period/mirror-centre; a vectorized numpy batch version; and an incremental push/pop engine used inside every search), cross-checked against each other on 4,000 random words at five thresholds, against 300 randomized push/pop replays, and against a sibling repository's independent Pansiot-code implementation on 500 random instances. That control suite was re-run in full while building this page; it still reports full agreement.

Section 2The sharp extremal length

For k = 22, 23, 24, 25 and α = (k−1)/(k−2), an exhaustive canonical search (letters renamed by first occurrence, which loses nothing since Definition 1 is renaming-invariant) over every word of Σk finds that the maximal U-α-free length is exactly k+3:

kαmax U-α-free lengthsearch-tree nodes (exhaustive)
2221/2025 (= k+3)451
2322/2126 (= k+3)483
2423/2227 (= k+3)516
2524/2328 (= k+3)550

Reproduced independently for this page with a separately written brute-force checker (no code shared with the search above): identical four lengths, identical four node counts, and, going further, an exhaustive check that the single longest word found at each of ten further sizes (n = 5, 6, 7, 8, 10, 15, plus 22–25) is exactly the word given in Theorem T1 below, and that it is the only one.

Every one of these four rows is, on its own, a certificate of the lower-bound half of the conjecture at that k: if every word of length k+4 contains an offender of exponent ≥ (k−1)/(k−2), no infinite word can avoid exponent ≥ (k−1)/(k−2) either, so URT(k) ≥ (k−1)/(k−2). That re-derives, for these four k, the lower-bound theorem Currie and Mol already proved for every k ≥ 4 secondary: the value added here is that the certificate is primary, in-repository, and tiny. The same "k+3" pattern across four consecutive alphabet sizes is exactly what turned into the theorem below.

Theorem T1

For every n ≥ 5, the maximal length of a word over Σn containing no undirected repetition of exponent ≥ (n−1)/(n−2) is exactly n+3, and the extremal word of length n+3 is unique up to renaming the letters:

w*  =  0 1 2 ⋯ (n−2)   0   (n−1)   1   3

(a head of n−1 distinct letters, then the letter at back-distance n−1, then the one remaining fresh letter, then the letters at back-distances n and n−1). Consequently URT(n) ≥ (n−1)/(n−2) for every n ≥ 5, by an elementary, self-contained proof.

Proof. Write α = (n−1)/(n−2). Three exact integer facts follow directly from Definition 1: (i) equal letters at distance d ≤ n−2 are forbidden (Lemma L1); (ii) an ordinary two-letter match w[i]w[i+1] = w[i+p]w[i+p+1] at period p ≤ 2n−4 is forbidden ((p+2)/p ≥ α ⟺ p ≤ 2(n−2)); (iii) a reversed pair w[i]w[i+1] = ab, w[j]w[j+1] = ba with j−i ≤ 2n−4 is forbidden (Lemma L3).

Upper bound. Take a U-α-free word of length n+4. By (i) its first n−1 letters are distinct; rename them 0, …, n−2. From here every later letter is constrained to the n−2 letters immediately behind it, so at each of the next four positions the only candidates are the letters at back-distances n−1, n, n+1, n+2 (call them A, B, C, D) or the single unused letter F. The candidate tree closes in four steps (the same tree, shape for shape, at every n):

tail so farcandidatekilled by
εA or Fboth possible
AA′ (pairs (0,n−1),(1,n) adjacent at distance n−1)(ii)
AB (repeats the letter one step back)(i)
A → only F survivesn/an/a
AF, FA or Bboth survive this step
FAC (reverses w[0]w[1], gap n ≤ 2n−4)(iii)
FAA (adjacent pairs at distance n−1)(ii)
FBB (adjacent pairs at distance n)(ii)
FB → A survivesn/an/a
AFA, FBAC (reverses the previous two letters)(iii)
AFA, AFB, FBAA or B (adjacent pairs at distance n−1 or n)(ii)
AFBAC (reverses w[2]w[3])(iii)
AFBAA (adjacent pairs at distance n−1)(ii)

D never enters: at every node the back-distance-(n+2) letter is already inside the forbidden window or coincides with a candidate already killed, and F is unavailable once used. Every branch dies by tail length ≤ 4, giving total length ≤ n+3 and contradicting length n+4. The tree shows the only tail reaching length 4 is A·F·B·A, which is the uniqueness claim.

Lower bound. w* has equal-letter pairs (0, n−1) at distance n−1, (1, n+1) at distance n, and (3, n+2) at distance n−1; every other letter occurs once. Arm-1 offenders need distance ≤ n−2: none present. An ordinary arm-≥2 offender needs two equal pairs at the same distance with adjacent left endpoints; the three left endpoints are 0, 1, 3 at distances n−1, n, n−1. No adjacent pair matches (0 and 1 are adjacent but their distances differ; 1 and 3 are not adjacent). A reversed arm-≥2 offender needs pairs (a,b) and (a+1,b−1); checking the three pairs against each other, none is a mirror of another. Palindromic factors of length 2 or 3 would need equal letters at distance 1 or 2, and there are none. So w* is U-α-free of length n+3. ∎

The bound URT(n) ≥ (n−1)/(n−2) is Currie and Mol's own theorem secondary; the new content here is the elementary proof and the sharp length n+3 with its uniqueness. Whether that sharp statement is itself new is also only a secondary claim: this session could not check the primary literature, so rediscovery of a known fact is entirely possible and is not ruled out by anything here.

Tap a filled letter to trace its pair.
The one word that reaches n+3 and no further. Computed live from the formula in Theorem T1 at n = 22 (25 cells; single characters a–l stand for the values 10–21, so every cell stays one character wide). Outlined cells are letters that occur once; the six filled cells are the word's only three repeats. Tap a filled letter to see the exact distance to its pair: every one is n−1 or n positions, the closest Definition 1 allows at this alphabet size.

Section 3Above the threshold, the language is thick

Allow the boundary exponent itself (forbid only exponent strictly above (k−1)/(k−2), the "+" reading of Definition 1) and the picture changes completely. The lexicographically least canonical U-(21/20)⁺-free word over 22 letters was searched for directly and reaches length 20,000 with no violation anywhere in it (committed as data/witness_n22_L20000.txt), and the same construction reaches length 5,000 at k = 23, 24, 25. A greedy lexicographic search needed only 22 backtracks to get to length 20,000; the language is not thin.

Re-checked in full for this page with an independently written checker (not the repository's own), scanning every ordinary and every reversed offender condition across the entire word, not a sample of it: zero offenders in all four committed witnesses, at their full lengths of 20,000 and 5,000×3.

Witness
Where a real witness reuses its letters. Computed live from the actual committed witness word (not a formula, not a sample): for every letter, the distance to its next occurrence, bucketed and counted. Bar height is square-root scaled so the rarer gaps stay visible; the exact count is printed above each bar. Every single gap in the word falls in a band just six values wide, starting at k−2 (the smallest distance Lemma L1 allows), which is exactly why the classical two-choice code in the next section cannot carry these words: it needs gaps of at least k−1, one more than this language ever settles for.

A weaker, still-certified fact about how many such words there are: over Σ22 at exponent > 21/20 there are at least 1,606,755 canonical U-free words of length 55. Two independent 50-million-node searches both hit the same node cap at that identical count (a deterministic traversal, not a coincidence), so the depth-55 tree is not exhausted and the true count is strictly larger; this is a certified lower bound only, not the true count. A smaller, independent 3-million-node re-run for this page found 90,941 such words, still climbing when it hit that smaller cap, consistent with, though not a reproduction of, the committed figure.

Put together with the previous section: at exponent cutoff ≥ 21/20 every word dies by length 25; at cutoff > 21/20 the language is thick past length 20,000. If the Currie–Mol conjecture holds at k = 22, the threshold can only be attained in the "+" sense, exactly as in Dejean's theorem for ordinary repetition thresholds.

Section 4The binary route is empty

For ordinary (non-mirrored) Dejean-threshold words, a classical trick (Pansiot) recodes a word whose every window of n−1 letters is "rainbow" (all distinct) as one bit per letter: bit 0 means "repeat the letter leaving the window", bit 1 means "emit the one letter currently absent". That rainbow-window condition is a strict subclass of U-α⁺-free: Lemma L1 only forces gaps ≥ n−2, one less than the n−1 this class needs.

An exhaustive search over binary codewords, decoding each one and checking the result against Definition 1, finds that this class is empty almost immediately at every alphabet size checked:

nαmax in-class U-α⁺-free codeword lengthsearch-tree nodeslongest codeword
2019/18420includes 0110
2120/19420includes 0110
2221/20420includes 0110
2322/21420includes 0110

Reproduced independently for this page: the decode rule was re-derived from its plain-language description (not copied from the repository's implementation) and re-run over all binary strings up to length 7 at each n, with the same result every time: dies at length 4, longest codeword 0110.

The mechanism is two short lemmas: two consecutive 0-bits force an ordinary offender of exponent (n+1)/(n−1) (too severe), and three consecutive 1-bits force one of exponent (n+2)/n (also too severe) once the window has fully turned over. The two-choice code simply cannot dodge both forever.

Consequence. Any word witnessing the undirected threshold must contain equal letters at distance exactly n−2 (the boundary case itself, with unit arms); it cannot live in the rainbow-(n−1) class where the classical binary code operates. A real construction needs a three-choice-per-step automaton for the gap-≥-(n−2) class instead. This also closes off an opening hypothesis of the session: whatever binary construction Currie and Mol actually use in their proof secondary, its output cannot be a Pansiot codeword of a threshold witness in this sense, because the class is empty even at alphabet sizes where their theorem proves witnesses exist (20 and 21), so the emptiness says nothing about why their proof works, only that witnesses must be built a different way.

Section 5Reversal identities, and a descent criterion

The binary route is dead, but the reversal-transfer machinery built for it is correct, reusable, and is recorded here for whatever construction eventually works. Conventions: window-and-absent-letter states are elements of Sym(n); bits act on the right by generators τ0, τ1; monodromy g(V) = τV₁ ∘ ⋯ ∘ τVL; r is the window-reversal permutation.

LemmaStatement
R1r τb r = τb⁻¹ for b ∈ {0,1}
R2if w is in-class with |w| ≥ n−1, then wᴿ is in-class and code(wᴿ) = code(w)ᴿ
R3g(Vᴿ) = r · g(V)⁻¹ · r (a direct consequence of R1)
R4a reversed letter-match of arm length ≥ n−1 in the decode corresponds exactly to an "anti-gid" pair of prefix monodromies plus a mirrored bit-agreement run sketch

R1–R3 have machine-checked proofs; R4 is recorded at sketch level in the source note. All four, plus the code-reversal identity and a pattern-preservation check, were re-run for this page against a sibling repository's independent implementation and against 200–500 random instances per check at five alphabet sizes: full agreement, both times.

With the binary class empty, the natural remaining route is a fixed point W = φ(W) of a k-uniform morphism φ on Σ22, with blocks Bx := φ(x). The theorem below reduces U-freeness of such a W to three finite, checkable conditions.

Theorem D: descent criterion

Let W = φ(W) be the fixed point of a k-uniform morphism φ, prolongable on W[0], and suppose:

  • (D1) x ↦ Bx[0] and x ↦ Bx[k−1] are each injective on the letters occurring in W;
  • (D2) for every factor xz of length 2 in W and every letter y of W, By does not occur in BxBz at any offset 0 < o < k;
  • (D3) for every such xz and y, (By)ᴿ does not occur in BxBz at any offset 0 ≤ o ≤ k;
  • (D4) every factor of W of length ≤ L₀ := 42k−20 is U-(21/20)⁺-free.

Then W is U-(21/20)⁺-free.

Proof (condensed; the full case bookkeeping is in the companion note). Suppose W has an offender; take one of minimal total span S = 2ℓ+g.

Reversed case. If the arm length ℓ is at least 2k−1, one arm contains a φ-aligned block By, and its mirror image inside the other arm is a length-k window that must sit inside two consecutive aligned blocks BxBz, so (By)ᴿ occurs in BxBz, contradicting (D3). So ℓ ≤ 2k−2, which forces S < 42k−42 < L₀, contradicting minimality via (D4).

Ordinary case. With period p = ℓ+g: if p ≤ 40k−20, the minimal-arm occurrence at that period already has span ≤ L₀, contradicting (D4) directly. If p ≥ 40k−19, the arm contains an aligned block whose p-shifted image is forced by (D2) to sit at block offset 0 (i.e. k divides p), and then (D1) forces letter-level equality W[s] = W[s+p/k] across a whole run of parent positions, giving an ordinary offender pattern in W itself, at period p/k and a correspondingly smaller arm, of strictly smaller span than S. That contradicts minimality of S. Either way, no minimal offender can exist. ∎

Status of the hypothesis space, all searches certified emptiness, none yet a construction. The affine family φ(x) = m·x + B₀ (mod 22), whose fixed point generalizes Thue–Morse and for which (D1) holds automatically, was searched exhaustively in canonical space with symbolic linear-algebra pruning over GF(2)×GF(11). At k = 22, 23, 24, all ten multipliers m in (ℤ/22)× die by depth ≤ 3k with zero survivors, exhausted.

Nine of those ten multipliers are backed by a committed scan log; the tenth, m = 1, was missing from every committed log specifically at k = 21 and k = 22, and was re-run for this page at the same parameters used elsewhere in the scan: k = 21 exhausted at 22,352 nodes, k = 22 exhausted at 161,425 nodes, both zero survivors, closing that gap. Extending m = 1 further: exhausted, zero survivors, at every k from 21 to 36 except k = 25 and k = 26, both of which hit a 800,000-node cap without a survivor and are genuinely inconclusive. (The source note's log attributes k = 26's exhaustion to "earlier session runs"; a re-run for this page at the same cap used elsewhere in the same scan did not exhaust it, so k = 26 is downgraded to inconclusive here, alongside the already-inconclusive k = 25, until a larger cap or the original log turns up.)

The fully general k-uniform search (canonical DFS with union-find block-class forcing, subsuming every uniform ansatz at once) is inconclusive: at k = 21, 22 it hits a hard forcing wall at depth exactly 20k (where the first parent-letter repetition forces the first block reuse), and four-million-node runs neither pass it nor exhaust the tree. This is not evidence toward or against the conjecture; it is simply where the search currently runs out of budget.

Section 6What failed

Kept in full, on purpose: a negative result that is checked and written down is worth more than a positive one that might not survive a second look.

Section 7Open questions

  1. Find a φ satisfying (D1)–(D4) at k = 22 (or any k), or prove the whole uniform-morphic ansatz empty. The depth-20k wall in the general search is where the actual difficulty lives; a solver-grade search (conflict-driven, or a SAT encoding of the class-forcing plus incremental U-constraints) is the concrete next step.
  2. Prove that the maximal U-α-free length is exactly k+3 for every k. Resolved the same day this was written down as an open question: that is now Theorem T1 above.
  3. Build the three-choice automaton for the true gap-≥-(n−2) class (the correct home of threshold witnesses, per section 4) and redo the reversal-transfer machinery of section 5 there, where it actually applies.
  4. Non-uniform morphisms (images of ternary squarefree words, say) are entirely unexplored here.

Section 8Caveats