Currie's conjecture on complexity 2n+1 and critical exponent

What Lean checks

Written proof for all twenty words of the journal and arXiv versions, computer-assisted in finitely many described places, after one independent model referee pass. The standard-library verifier checks the morphism identities, exact factor sets, the hypotheses of the insertion lemmas, the short bispecial factors and the exact inequalities in Q(λ) for the 72 families; brute-force cross-checks cover bounded lengths and prefixes. No proof-assistant formalization is claimed.

Catalogue · Proof · Exact checks · Issue #148

Status: Written proof, computer-assisted in finitely many described places, all of which verify.py reproduces. It has been through one independent referee pass by a second model instance, which found no error; the minor gaps and notation remarks it raised are addressed in the note. The note is otherwise unrefereed.

Lean status: none. No Lean formalization is included.

Primary source: J. D. Currie, Words with factor complexity 2n+12n+1 and minimal critical exponent, Electron. J. Combin. 33(3) (2026), #P3.31, DOI 10.37236/14527, Conjecture 19 (Figures 3 and 4); the same conjecture is Conjecture 1 (Figures 1 and 2) of arXiv:2507.09387v3.

Result

Let γ=[01,2,02]\gamma=[01,2,02] be the morphism 0↦010\mapsto 01, 1↦21\mapsto 2, 2↦022\mapsto 02 on {0,1,2}\{0,1,2\}, let G=γω(0)G=\gamma^\omega(0) be its fixed point and G′=(γR)ω(2)G'=(\gamma^R)^\omega(2) the fixed point of the reversed morphism γR=[10,2,20]\gamma^R=[10,2,20]. Let λ=1.7548776662…\lambda=1.7548776662\ldots be the real root of x3−2x2+x−1x^3-2x^2+x-1 and

μ=2+1λ2−1=2.4808627161…\mu=2+\frac{1}{\lambda^2-1}=2.4808627161\ldots

Theorem. For each of the four morphisms hh of Figure 3 of the journal version the word h(G)h(G), and for each of the six morphisms hh of Figure 4 the word h(G′)h(G'), has factor complexity p(n)=2n+1p(n)=2n+1 for all n≥0n\ge 0 and critical exponent exactly μ\mu. The supremum defining the critical exponent is not attained. The same holds for the ten morphisms of Figures 1 and 2 of arXiv v3.

This settles Conjecture 19 of the journal version, equivalently Conjecture 1 of arXiv v3, affirmatively for all twenty listed words. Both lists and the wording of the conjecture were compared with the journal PDF and the arXiv v3 HTML on 21 November 2026.

Up to letter permutations, reversal and conjugation of morphisms, the twenty words have only three languages: those of GG, U=a1(G)U=a_1(G) and V=a4(G)V=a_4(G), where a1=[210,20,21]a_1=[210,20,21] and a4=[102,2,1]a_4=[102,2,1] are rows of Figure 3. Each arXiv morphism is a conjugate of the corresponding journal morphism composed with a power of γ\gamma or γR\gamma^R. The morphisms γ\gamma, a1a_1 and a4a_4 factor into letter permutations and elementary insertions b↦abb\mapsto ab or b↦bab\mapsto ba. Two self-contained lemmas describe how bispecial factors, their extension graphs and their return words change under one insertion. They show that every nonempty bispecial factor of GG, UU and VV is ordinary, lying in two explicit orbits or among seven short exceptions, so Cassaigne's formula gives complexity 2n+12n+1. For the critical exponent, the formula E(x)=1+supw|w|/|rw|E(x)=1+\sup_w|w|/|r_w| over bispecial factors ww and shortest return words rwr_w (Dolce, Dvořáková and Pelantová; a proof is included) reduces the claim to |w|<(μ−1)|r||w|\lt(\mu-1)|r| for every return word rr of every bispecial factor ww, with ratios tending to μ−1\mu-1. Along the orbits these lengths satisfy linear recurrences, and the inequality is proved for each of 72 families by exact arithmetic in ℚ(λ)\mathbb Q(\lambda).

For GG itself the complexity and the critical exponent are Lemma 28 and Theorem 29 of Shallit and Shur, re-proved in the note by a different route. The papers of Shallit and Shur and of Dolce, Dvořáková and Pelantová were read only through a summarising web tool; no step of the proof depends on them.

Verification

Run from the repository root with Python 3.10 or later and no other dependencies:

python3 results/currie-conjecture-19/verify.py

Every check is an assertion and the script ends with ALL CHECKS PASSED. It checks the morphism identities of the reduction and the conjugating words for the arXiv rows (S1); the primitivity of γ\gamma and exact factor sets of GG (S2); the hypotheses of the insertion lemmas along the three chains, the seeds, the explicit forms of the orbits and the short extra bispecial factors (S3); and the exact inequalities in ℚ(λ)\mathbb Q(\lambda) for the 72 families and the seven extra words (S6). As cross-checks, it compares the bispecial factors of GG, UU and VV given by the lemmas with an exhaustive enumeration up to length 300 (S4), checks p(n)=2n+1p(n)=2n+1 for n≤300n\le 300 for GG, G′G' and all twenty images (S5), and searches prefixes of length 60000 for repetitions with period at most 3000, all of exponent below μ\mu (S7). It takes about 15 seconds on an idle core and about 50 seconds under load. An optional argument raises the length bound 300 of S4 and S5; with 600 the script takes a few minutes.

The theorem rests on the written proof together with the finite computations listed in it, which verify.py reproduces. The brute-force sections cover bounded lengths and prefixes only.

Optional checks, not run by CI: review/ contains the standard-library scripts of the referee pass, which the referee wrote from scratch, independently of verify.py. They are run from that folder. reduction.py checks the identities of the reduction and the complexity of all twenty images; bisp.py compares all bispecial factors of GG, UU and VV of bounded length with the note's description; crit.py checks |w|<(μ−1)|r||w|\lt(\mu-1)|r| along every family with a certified enclosure of λ\lambda; lemma_test.py tests the insertion lemmas by brute force on fixed points of several primitive morphisms, including words with non-ordinary bispecial factors (a test, not a certificate); common.py holds shared helpers. Two further referee scripts need numpy and are not included.

Files

  • PROOF.md: statement, reduction to three words, lemmas, proof, verification summary, referee pass and sources.
  • verify.py: standard-library check of the computer-assisted steps, with brute-force cross-checks.
  • review/: the referee pass's independent scripts.