Conjecture 19 of Currie (EJC 33(3) #P3.31): complexity 2n+1 and critical exponent mu for the listed morphic images

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.

Status: proved -- text proof, computer-assisted in finitely many described places (all reproduced by verify.py), one independent model referee pass, not formalised. Both versions of the conjecture (journal Conjecture 19, arXiv v3 Conjecture 1) are covered.

Statement

Alphabet A={0,1,2}A=\{0,1,2\}. A morphism hh is written [h(0),h(1),h(2)][h(0),h(1),h(2)], and hR=[h(0)R,h(1)R,h(2)R]h^R=[h(0)^R,h(1)^R,h(2)^R]. Let

γ=[01,2,02],G=γω(0)=0120201020120102012⋯,γR=[10,2,20],G′=(γR)ω(2)=2010210202⋯.\gamma=[01,2,02],\qquad G=\gamma^\omega(0)=0120201020120102012\cdots,\qquad \gamma^R=[10,2,20],\qquad G'=(\gamma^R)^\omega(2)=2010210202\cdots .

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…,α:=μ−1=3−λ+2λ25=1.4808627161…\mu = 2+\frac{1}{\lambda^2-1}=2.4808627161\ldots,\qquad \alpha:=\mu-1=\frac{3-\lambda+2\lambda^2}{5}=1.4808627161\ldots

(the last identity holds in ℚ(λ)\mathbb Q(\lambda) and is checked exactly in verify.py).

Theorem. For every morphism hh of Figure 3 of [Cu-EJC] the word h(G)h(G), and for every morphism 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 is not attained). The same holds for the morphisms of Figures 1 and 2 of arXiv:2507.09387v3.

Figure 3 (applied to GG): a1=[210,20,21]a_1=[210,20,21], a2=[02,021,02121]a_2=[02,021,02121], a3=[2,0,1]a_3=[2,0,1], a4=[102,2,1]a_4=[102,2,1]. Figure 4 (applied to G′G'): b1=[2,0,1]b_1=[2,0,1], b2=[0,2,21]b_2=[0,2,21], b3=[1,0,2]b_3=[1,0,2], b4=[12,012,01012]b_4=[12,012,01012], b5=[201,21,01]b_5=[201,21,01], b6=[102,1,2]b_6=[102,1,2]. arXiv v3, Figure 1 (applied to GG): [1210202,12102,1210202102][1210202, 12102, 1210202102], [1210202102,1210202,121020210202][1210202102, 1210202, 121020210202], [021201212,0212012,021201212012][021201212, 0212012, 021201212012], [21021102211021102,2102110221102,2102110221102110221102][21021102211021102, 2102110221102, 2102110221102110221102]. arXiv v3, Figure 2 (applied to G′G'): [10212,0212,0210212][10212, 0212, 0210212], [2120210,20210,202120210][2120210, 20210, 202120210], [121201210,1201210,120121201210][121201210, 1201210, 120121201210], [1201212010,1212010,121201212010][1201212010, 1212010, 121201212010], [1212010,12010,1201212010][1212010, 12010, 1201212010], [221102210,21102210,2110221102210][221102210, 21102210, 2110221102210].

Both lists, the definitions of γ\gamma, GG, γR\gamma^R, G′G' and the wording of the conjecture were compared on 21 November 2026 with the text of the journal PDF (Section 7, Figures 3 and 4, Conjecture 19) and of the arXiv v3 HTML (Figures 1 and 2, Conjecture 1). The two lists are also consistent with each other in the strong sense of Section "Reduction", step R5 (each arXiv row is a conjugate of the corresponding journal row composed with a power of γ\gamma or γR\gamma^R).

For GG itself, pG(n)=2n+1p_G(n)=2n+1 and E(G)=μE(G)=\mu are Lemma 28 and Theorem 29 of Shallit and Shur [SS]†; we re-prove both below because the proof for the images needs the full list of bispecial factors of GG anyway.

Reduction

Notation. For an infinite word xx, ℒ(x)\mathcal L(x) is its set of factors, px(n)p_x(n) the number of factors of length nn, and E(x)=sup{|z|/q:z∈ℒ(x)\{ε},qa period ofz}E(x)=\sup\{|z|/q : z\in\mathcal L(x)\setminus\{\varepsilon\},\ q\ \text{a period of}\ z\} its critical exponent (a period of zz is an integer 1≤q≤|z|1\le q\le |z| with zi=zi+qz_i=z_{i+q} for 0≤i<|z|−q0\le i\lt |z|-q). For a set of words SS, Fact(S)\mathrm{Fact}(S) is the set of factors of elements of SS, and SR={sR:s∈S}S^R=\{s^R: s\in S\}.

R1 (invariance). pxp_x and E(x)E(x) depend only on ℒ(x)\mathcal L(x); they do not change if ℒ(x)\mathcal L(x) is replaced by π(ℒ(x))\pi(\mathcal L(x)) for a letter permutation π\pi, or by ℒ(x)R\mathcal L(x)^R (reversal is a length-preserving bijection of ℒ(x)\mathcal L(x) onto ℒ(x)R\mathcal L(x)^R and qq is a period of zz iff it is a period of zRz^R). For every morphism hh and every word xx, ℒ(h(x))=Fact(h(ℒ(x)))\mathcal L(h(x))=\mathrm{Fact}(h(\mathcal L(x))) (any factor of h(x)h(x) lies in the image of a factor of xx), and h(u)R=hR(uR)h(u)^R=h^R(u^R), hence Fact(h(S))R=Fact(hR(SR))\mathrm{Fact}(h(S))^R=\mathrm{Fact}(h^R(S^R)).

R2 (ℒ(G′)=ℒ(G)R\mathcal L(G')=\mathcal L(G)^R). γR(u)=(γ(uR))R\gamma^R(u)=(\gamma(u^R))^R, so (γR)n(2)=(γn(2))R(\gamma^R)^n(2)=(\gamma^n(2))^R. The incidence matrix of γ\gamma has positive cube (verify.py S2), so γ3(c)\gamma^3(c) contains every letter for every cc; hence ℒ(G)=⋃nFact(γn(0))=⋃nFact(γn(2))\mathcal L(G)=\bigcup_n\mathrm{Fact}(\gamma^n(0))=\bigcup_n\mathrm{Fact}(\gamma^n(2)), and ℒ(G′)=⋃nFact((γR)n(2))=ℒ(G)R\mathcal L(G')=\bigcup_n\mathrm{Fact}((\gamma^R)^n(2))=\mathcal L(G)^R.

R3 (two exact identities between GG and G′G'). Put c1=[0,2,01]c_1=[0,2,01], c2=[2,1,01]c_2=[2,1,01], τ=(01)\tau=(0\,1). Then c1c2=γc_1c_2=\gamma and c2c1=[2,01,21]=τγRτc_2c_1=[2,01,21]=\tau\gamma^R\tau. Since G=c1(c2(G))G=c_1(c_2(G)), the word c2(G)c_2(G) is a fixed point of c2c1=τγRτc_2c_1=\tau\gamma^R\tau beginning with c2(0)=2c_2(0)=2; a fixed point of τγRτ\tau\gamma^R\tau beginning with 22 is unique (its image of 22 is 2121, of length ≥2\ge 2), and τ(G′)\tau(G') is one; so c2(G)=τ(G′)c_2(G)=\tau(G'). Therefore

G′=τc2(G)=[2,0,10](G),G=c1(c2(G))=c1τ(G′)=[2,0,01](G′).G'=\tau c_2(G)=[2,0,10](G),\qquad G=c_1(c_2(G))=c_1\tau(G')=[2,0,01](G').

R4 (conjugate morphisms). Let h,h′h,h' be morphisms and uu a word with h′(c)u=uh(c)h'(c)\,u=u\,h(c) for every letter cc, such that uu is a prefix of every h′(c)h'(c) and a suffix of every h(c)h(c). Let ℒ\mathcal L be the language of a recurrent infinite word. Then Fact(h(ℒ))=Fact(h′(ℒ))\mathrm{Fact}(h(\mathcal L))=\mathrm{Fact}(h'(\mathcal L)). Proof. By induction h′(z)u=uh(z)h'(z)u=uh(z) for every word zz. For z∈ℒz\in\mathcal L pick letters d,ed,e with zd,ez∈ℒzd, ez\in\mathcal L (recurrence). h′(zd)=h′(z)h′(d)h'(zd)=h'(z)h'(d) has the prefix h′(z)u=uh(z)h'(z)u=uh(z), so h(z)∈Fact(h′(ℒ))h(z)\in\mathrm{Fact}(h'(\mathcal L)); h(ez)=h(e)h(z)h(ez)=h(e)h(z) has the suffix uh(z)=h′(z)uuh(z)=h'(z)u, so h′(z)∈Fact(h(ℒ))h'(z)\in\mathrm{Fact}(h(\mathcal L)). ▫\square

R5 (the list reduces to three words). Let σ=(02)\sigma=(0\,2), 𝜚=(12)\varrho=(1\,2) and π0=[2,0,1]\pi_0=[2,0,1] (as letter maps). The following identities of morphisms are checked character by character in verify.py S1:

a3=b1=π0,b3=τ,b6=𝜚∘a4R,b5=π0∘a1R,b4=π0∘a2R,b2=σ∘[2,0,01],a_3=b_1=\pi_0,\quad b_3=\tau,\quad b_6=\varrho\circ a_4^R,\quad b_5=\pi_0\circ a_1^R,\quad b_4=\pi_0\circ a_2^R,\quad b_2=\sigma\circ[2,0,01],

a2R∘[2,0,10]=[12120,20,12020],(τ∘a1)∘γ=[20121,20,20120],a_2^R\circ[2,0,10]=[12120,20,12020],\qquad (\tau\circ a_1)\circ\gamma=[20121,20,20120],

and [20121,20,20120][20121,20,20120], [12120,20,12020][12120,20,12020] satisfy the hypothesis of R4 with u=20u=20. Put U=a1(G)U=a_1(G) and V=a4(G)V=a_4(G). Using R1-R4:

  • a3(G)=π0(G)a_3(G)=\pi_0(G); b1(G′)=π0(G′)b_1(G')=\pi_0(G') and b3(G′)=τ(G′)b_3(G')=\tau(G') have the language π(ℒ(G)R)\pi(\mathcal L(G)^R); b2(G′)=σ([2,0,01](G′))=σ(G)b_2(G')=\sigma([2,0,01](G'))=\sigma(G).
  • ℒ(b6(G′))=𝜚(Fact(a4R(ℒ(G)R)))=𝜚(ℒ(V)R)\mathcal L(b_6(G'))=\varrho(\mathrm{Fact}(a_4^R(\mathcal L(G)^R)))=\varrho(\mathcal L(V)^R), and likewise ℒ(b5(G′))=π0(ℒ(U)R)\mathcal L(b_5(G'))=\pi_0(\mathcal L(U)^R).
  • ℒ(a2(G))R=Fact(a2R(ℒ(G′)))=Fact(a2R[2,0,10](ℒ(G)))=Fact(τa1γ(ℒ(G)))=τ(ℒ(U))\mathcal L(a_2(G))^R=\mathrm{Fact}(a_2^R(\mathcal L(G')))=\mathrm{Fact}(a_2^R[2,0,10](\mathcal L(G)))=\mathrm{Fact}(\tau a_1\gamma(\mathcal L(G)))=\tau(\mathcal L(U)), using R3, R4 and Fact(γ(ℒ(G)))=ℒ(G)\mathrm{Fact}(\gamma(\mathcal L(G)))=\mathcal L(G). Then ℒ(b4(G′))=π0(ℒ(a2(G))R)=π0τ(ℒ(U))\mathcal L(b_4(G'))=\pi_0(\mathcal L(a_2(G))^R)=\pi_0\tau(\mathcal L(U)).
  • arXiv v3: for each row hh of its Figure 1 (resp. 2), verify.py S1 finds a word uu such that hh and hj∘γkh_j\circ\gamma^k (resp. hj∘(γR)kh_j\circ(\gamma^R)^k) satisfy the hypothesis of R4 (in one of the two orders), with (j,k)=(1,2),(2,2),(3,4),(4,4)(j,k)=(1,2),(2,2),(3,4),(4,4) for Figure 1 (where hj=ajh_j=a_j) and (1,3),(2,3),(3,4),(4,2),(5,2),(6,3)(1,3),(2,3),(3,4),(4,2),(5,2),(6,3) for Figure 2 (where hj=bjh_j=b_j). Since γk(G)=G\gamma^k(G)=G and (γR)k(G′)=G′(\gamma^R)^k(G')=G', each arXiv word has the same language as the corresponding journal word.

Hence, by R1, the Theorem is equivalent to: GG, U=a1(G)U=a_1(G) and V=a4(G)V=a_4(G) have complexity 2n+12n+1 and critical exponent μ\mu (classes: GG: a3,b1,b2,b3a_3,b_1,b_2,b_3; UU: a1,a2,b4,b5a_1,a_2,b_4,b_5; VV: a4,b6a_4,b_6).

Elementary decompositions. For distinct letters a,ba,b let Lab\mathrm L_{ab} (left insertion) and Rab\mathrm R_{ab} (right insertion) be the morphisms

Lab:b↦ab,Rab:b↦ba,c↦c(c≠b),\mathrm L_{ab}:\ b\mapsto ab,\qquad \mathrm R_{ab}:\ b\mapsto ba,\qquad c\mapsto c\ \ (c\ne b),

and fab:A→Af_{ab}:A\to A the letter map b↦ab\mapsto a, c↦cc\mapsto c (c≠bc\ne b). Writing letter permutations as words [π(0)π(1)π(2)][\pi(0)\pi(1)\pi(2)], one checks directly (and verify.py S1):

γ=[120]∘L20∘R12,a4=[021]∘R10∘L20,a1=[021]∘L12∘R01∘L20.\gamma=[120]\circ\mathrm L_{20}\circ\mathrm R_{12},\qquad a_4=[021]\circ\mathrm R_{10}\circ\mathrm L_{20},\qquad a_1=[021]\circ\mathrm L_{12}\circ\mathrm R_{01}\circ\mathrm L_{20}.

Lemmas

Throughout, xx is a uniformly recurrent infinite word over AA in which all three letters occur, ℒ=ℒ(x)\mathcal L=\mathcal L(x). For w∈ℒw\in\mathcal L:

E−(w)={e:ew∈ℒ},E+(w)={d:wd∈ℒ},E(w)={(e,d):ewd∈ℒ},m(w)=|E(w)|−|E−(w)|−|E+(w)|+1.E^-(w)=\{e: ew\in\mathcal L\},\quad E^+(w)=\{d: wd\in\mathcal L\},\quad E(w)=\{(e,d): ewd\in\mathcal L\},\quad m(w)=|E(w)|-|E^-(w)|-|E^+(w)|+1 .

ww is bispecial if |E±(w)|≥2|E^\pm(w)|\ge 2; ordinary if moreover |E−(w)|=|E+(w)|=2|E^-(w)|=|E^+(w)|=2 and |E(w)|=3|E(w)|=3 (then m(w)=0m(w)=0). Bisp*(x)\mathrm{Bisp}^*(x) is the set of nonempty bispecial factors. A return word to ww is x[i,j)x[i,j) for two consecutive occurrences i<ji\lt j of ww in xx; equivalently, rr is a return word to ww iff rw∈ℒrw\in\mathcal L, ww is a prefix of rwrw and rwrw has exactly two occurrences of ww (so the set Ret(w)\mathrm{Ret}(w) depends only on ℒ\mathcal L; it is finite by uniform recurrence). Ψ(v)\Psi(v) denotes the Parikh vector (|v|0,|v|1,|v|2)T(|v|_0,|v|_1,|v|_2)^T, MhM_h the incidence matrix of hh (column cc is Ψ(h(c))\Psi(h(c))), so Ψ(h(v))=MhΨ(v)\Psi(h(v))=M_h\Psi(v).

Lemma 1 (Cassaigne's formula). Let s(n)=p(n+1)−p(n)s(n)=p(n+1)-p(n). Then s(n+1)−s(n)=∑|w|=nm(w)s(n+1)-s(n)=\sum_{|w|=n}m(w), and m(w)=0m(w)=0 unless ww is bispecial. Consequently, if all three letters occur and m(w)=0m(w)=0 for every bispecial ww (including ε\varepsilon), then p(n)=2n+1p(n)=2n+1 for all nn. Proof. Every factor of length n+1n+1 is uniquely wdwd with d∈E+(w)d\in E^+(w), so s(n)=∑|w|=n(|E+(w)|−1)s(n)=\sum_{|w|=n}(|E^+(w)|-1). Every factor of length n+1n+1 is uniquely ewew, e∈E−(w)e\in E^-(w), and E+(ew)={d:(e,d)∈E(w)}E^+(ew)=\{d:(e,d)\in E(w)\}; hence s(n+1)=∑|w|=n∑e∈E−(w)(|E+(ew)|−1)=∑|w|=n(|E(w)|−|E−(w)|)s(n+1)=\sum_{|w|=n}\sum_{e\in E^-(w)}(|E^+(ew)|-1)=\sum_{|w|=n}(|E(w)|-|E^-(w)|). Subtracting gives the formula. If |E−(w)|=1|E^-(w)|=1 then |E(w)|=|E+(w)||E(w)|=|E^+(w)|, so m(w)=0m(w)=0; symmetrically if |E+(w)|=1|E^+(w)|=1. Finally p(0)=1p(0)=1, p(1)=3p(1)=3, so s(0)=2s(0)=2 and s≡2s\equiv 2. ▫\square

Lemma 2 (exact factor sets, used by verify.py). Let n≥1n\ge 1 and let SS be a set of words of length nn such that (a) SS contains the length-nn factors of γk(0)\gamma^k(0) for every k≥0k\ge0 with k=0k=0 or |γk−1(0)|<n|\gamma^{k-1}(0)|\lt n, and (b) every length-nn factor of γ(v)\gamma(v), v∈Sv\in S, lies in SS. Then S⊇ℒn(G)S\supseteq\mathcal L_n(G); if SS is the set of length-nn factors of a prefix of GG, then S=ℒn(G)S=\mathcal L_n(G). Proof. A factor ff of length nn of GG is a factor of some γk(0)\gamma^k(0); induct on kk. If k=0k=0 or |γk−1(0)|<n|\gamma^{k-1}(0)|\lt n use (a). Otherwise ff lies in γ(t)\gamma(t) for a factor tt of γk−1(0)\gamma^{k-1}(0) with |t|≤n|t|\le n (each letter of tt contributes at least one letter to ff); extend tt inside γk−1(0)\gamma^{k-1}(0) to a factor t′t' of length exactly nn; t′∈St'\in S by induction and f∈Sf\in S by (b). ▫\square The factors of length nn of h(G)h(G) are the length-nn factors of h(v)h(v), v∈ℒn(G)v\in\mathcal L_n(G) (images are nonempty). By hand, n=2n=2: γ(01)=012\gamma(01)=012, γ(02)=0102\gamma(02)=0102, γ(10)=201\gamma(10)=201, γ(12)=202\gamma(12)=202, γ(20)=0201\gamma(20)=0201 give

ℒ2(G)={01,02,10,12,20},soE+(2)={0},E−(1)={0},E+(1)={2},E−(2)={0,1},E±(0)={1,2}.\mathcal L_2(G)=\{01,02,10,12,20\},\qquad\text{so}\quad E^+(2)=\{0\},\ E^-(1)=\{0\},\ E^+(1)=\{2\},\ E^-(2)=\{0,1\},\ E^\pm(0)=\{1,2\}.

Lemma 3 (critical exponent via bispecial factors; Dolce-Dvořáková-Pelantová [DDP, Thm 3]†). If xx is uniformly recurrent and not periodic,

E(x)=1+sup{|w||rw|:wbispecial factor ofx,rwa shortest return word tow}.E(x)=1+\sup\Big\{\frac{|w|}{|r_w|}:\ w\ \text{bispecial factor of}\ x,\ r_w\ \text{a shortest return word to}\ w\Big\}.

Proof (self-contained). (≥\ge) If rr is a shortest return word to ww, ww occurs at ii and i+|r|i+|r|, so z=x[i,i+|r|+|w|)z=x[i,i+|r|+|w|) has period |r||r| and |z|/|r|=1+|w|/|r||z|/|r|=1+|w|/|r|. (≤\le) Let z∈ℒ(x)z\in\mathcal L(x) have period qq, |z|>q|z|\gt q (if |z|≤q|z|\le q the ratio is ≤1\le 1). As xx is not periodic, there is i0i_0 with xi0≠xi0+qx_{i_0}\ne x_{i_0+q}. Take an occurrence of zz at a position i>i0+qi\gt i_0+q (recurrence) and the maximal interval [s,t)⊇[i,i+|z|)[s,t)\supseteq[i,i+|z|) on which xx has period qq. It is finite on the right: otherwise x[s,∞)x[s,\infty) has period qq; every prefix of xx occurs in x[s,∞)x[s,\infty) (recurrence), so every prefix of xx has period qq and xx is periodic. And s≥1s\ge 1: otherwise [0,t)∋i0,i0+q[0,t)\ni i_0,i_0+q. Put w=x[s,t−q)w=x[s,t-q). Then ww occurs at ss and at s+qs+q; by maximality xs−1≠xs−1+qx_{s-1}\ne x_{s-1+q} and xt−q≠xtx_{t-q}\ne x_t, so ww is left and right special. Occurrences at distance qq give |rw|≤q|r_w|\le q, so |z|/q≤(t−s)/q=1+|w|/q≤1+|w|/|rw||z|/q\le (t-s)/q=1+|w|/q\le 1+|w|/|r_w|. ▫\square

Lemma 4 (left insertion). Let a≠ba\ne b, h=Labh=\mathrm L_{ab}, f=fabf=f_{ab}, y=h(x)y=h(x), and assume

(H)Ex+(a)={a+}is a single letter.\text{(H)}\qquad E^+_x(a)=\{a^+\}\ \text{is a single letter.}

  1. The nonempty bispecial factors of yy are exactly the following words, and they are pairwise distinct:
  2. h(u)h(u), for u∈Bisp*(x)u\in\mathrm{Bisp}^*(x) with |f(E+(u))|≥2|f(E^+(u))|\ge 2; then Ey(h(u))={(e,f(d)):(e,d)∈Ex(u)}E_y(h(u))=\{(e,f(d)):(e,d)\in E_x(u)\};
  1. h(u)ah(u)a, for u∈ℒ(x)u\in\mathcal L(x) (possibly empty) with {a,b}⊆E+(u)\{a,b\}\subseteq E^+(u) and |E−(ua)∪E−(ub)|≥2|E^-(ua)\cup E^-(ub)|\ge 2; then

Ey(h(u)a)={(e,f(a+)):(e,a)∈Ex(u)}∪{(e,b):(e,b)∈Ex(u)}.E_y(h(u)a)=\{(e,f(a^+)):(e,a)\in E_x(u)\}\cup\{(e,b):(e,b)\in E_x(u)\}.

  1. Let u∈Bisp*(x)u\in\mathrm{Bisp}^*(x) be ordinary. Put Λh(u)=h(u)a\Lambda_h(u)=h(u)a if E+(u)={a,b}E^+(u)=\{a,b\} and Λh(u)=h(u)\Lambda_h(u)=h(u) otherwise. Then Λh(u)\Lambda_h(u) is the only one of h(u),h(u)ah(u),h(u)a that is bispecial in yy; it is ordinary, Ey−(Λh(u))=Ex−(u)E^-_y(\Lambda_h(u))=E^-_x(u), and Rety(Λh(u))=h(Retx(u))\mathrm{Ret}_y(\Lambda_h(u))=h(\mathrm{Ret}_x(u)) (bijectively). Moreover |u|≤|Λh(u)|≤2|u|+1|u|\le|\Lambda_h(u)|\le 2|u|+1, and Λh\Lambda_h is injective.

  2. If every non-ordinary word of Bisp*(x)\mathrm{Bisp}^*(x) has length ≤m\le m (m=0m=0 if there is none), then every v∈Bisp*(y)v\in\mathrm{Bisp}^*(y) that is not of the form Λh(u)\Lambda_h(u) with u∈Bisp*(x)u\in\mathrm{Bisp}^*(x) ordinary has length ≤2m+1\le 2m+1; for m=0m=0 the only possible such vv is the letter aa, and aa is bispecial in yy iff |Ex−(a)∪Ex−(b)|≥2|E^-_x(a)\cup E^-_x(b)|\ge 2.

Proof. Write y=h(x0)h(x1)⋯y=h(x_0)h(x_1)\cdots and call |h(x0⋯xi−1)||h(x_0\cdots x_{i-1})| (i≥0i\ge 0) the cuts. The blocks are aa, abab and cc (the third letter). Their first letters are never bb and their second letters are bb; hence a position pp is a cut iff yp≠by_p\ne b. Every block ends with the letter it codes (h(e)h(e) ends with ee), and the first letter of h(d)h(d) is f(d)f(d). hh is injective on words ({a,ab,c}\{a,ab,c\} is a suffix code).

Factors starting with bb. An occurrence of bb at p≥1p\ge 1 is preceded by aa; so a factor starting with bb has E−={a}E^-=\{a\} and is not left special.

Desubstitution. Let vv be a nonempty factor of yy not starting with bb, occurring at pp. Then pp is a cut. If vv does not end with aa, the position p+|v|p+|v| is a cut (the last letter of vv is bb, the end of a block abab, or the third letter, a whole block); so y[p,p+|v|)=h(x[i,j))y[p,p+|v|)=h(x[i,j)) and, by injectivity, v=h(u)v=h(u) with u=x[i,j)u=x[i,j) independent of the occurrence. Thus the occurrences of vv are exactly the positions |h(x[0,i))||h(x[0,i))|, ii an occurrence of uu (conversely h(u)h(u) occurs there). The letter before (when p≥1p\ge 1) is the last letter of h(xi−1)h(x_{i-1}), i.e. xi−1x_{i-1}, the letter after is f(xj)f(x_j). Hence Ey(h(u))={(e,f(d)):(e,d)∈Ex(u)}E_y(h(u))=\{(e,f(d)):(e,d)\in E_x(u)\}, using that every factor of xx has occurrences at positions ≥1\ge1 (recurrence). If vv ends with aa, that last aa is at a cut (it is not bb), so v=h(u)av=h(u)a where y[p,p+|v|−1)=h(x[i,j))y[p,p+|v|-1)=h(x[i,j)), u=x[i,j)u=x[i,j), and the block starting at p+|v|−1p+|v|-1 is aa or abab, i.e. xj∈{a,b}x_j\in\{a,b\}. So the occurrences of h(u)ah(u)a correspond to the occurrences of uaua and of ubub; the letter after is bb in the second case and f(xj+1)=f(a+)f(x_{j+1})=f(a^+) in the first case, by (H). This gives the formula in (ii); in particular Ey+(h(u)a)⊆{f(a+),b}E^+_y(h(u)a)\subseteq\{f(a^+),b\}, two distinct letters (bb is not in the image of ff).

(a). By the above a nonempty bispecial vv is either h(u)h(u) (vv not ending with aa) or h(u)ah(u)a. In the first case Ey−(v)=Ex−(u)E^-_y(v)=E^-_x(u) and Ey+(v)=f(Ex+(u))E^+_y(v)=f(E^+_x(u)), so vv is bispecial iff uu is left special and |f(E+(u))|≥2|f(E^+(u))|\ge 2 (which forces uu right special); u≠εu\ne\varepsilon since v≠εv\ne\varepsilon. In the second case vv is right special iff both uaua and ubub occur, and then left special iff |E−(ua)∪E−(ub)|≥2|E^-(ua)\cup E^-(ub)|\ge2. Conversely the words listed are factors with the stated graphs. Distinctness: by (H) a word ending with aa has the single right extension a+a^+, so a right special uu in (i) does not end with aa, hence h(u)h(u) does not end with aa, while the words in (ii) do; within each family use injectivity of λ\lambda.

(b). Let uu be ordinary, E+(u)={d1,d2}E^+(u)=\{d_1,d_2\}. If {d1,d2}≠{a,b}\{d_1,d_2\}\ne\{a,b\}, ff is injective on E+(u)E^+(u), so h(u)h(u) is bispecial with a graph isomorphic to E(u)E(u), and h(u)ah(u)a is not right special (ubub or uaua is missing). If E+(u)={a,b}E^+(u)=\{a,b\}, h(u)h(u) has |f(E+(u))|=1|f(E^+(u))|=1, while h(u)ah(u)a is bispecial: every e∈E−(u)e\in E^-(u) has an edge to aa or bb, so E−(ua)∪E−(ub)=E−(u)E^-(ua)\cup E^-(ub)=E^-(u), and its graph is E(u)E(u) with the right vertex aa renamed f(a+)f(a^+) (≠b\ne b), again isomorphic. In both cases E−E^- is unchanged. Return words: in both cases the occurrences of Λh(u)\Lambda_h(u) are exactly the positions |h(x[0,i))||h(x[0,i))| with ii an occurrence of uu (in case (ii) because every occurrence of uu is followed by aa or bb). This map is increasing, so consecutive occurrences correspond and the return word between them is h(x[i,i′))h(x[i,i')). Length bounds: |u|≤|h(u)|≤2|u||u|\le|h(u)|\le 2|u|. Injectivity: Λh(u)\Lambda_h(u) determines whether it ends with aa, and then uu.

(c). By (a), such a vv is h(u)h(u) or h(u)ah(u)a with u∈{ε}∪Bisp*(x)u\in\{\varepsilon\}\cup\mathrm{Bisp}^*(x) (uu in (ii) is left and right special or empty). If uu is ordinary and nonempty, (b) gives v=Λh(u)v=\Lambda_h(u). If u=εu=\varepsilon then v=av=a (the form (i) needs u≠εu\ne\varepsilon). Otherwise uu is non-ordinary, |u|≤m|u|\le m and |v|≤2m+1|v|\le 2m+1. The criterion for aa is (ii) with u=εu=\varepsilon. ▫\square

Lemma 5 (right insertion). Let a≠ba\ne b, h=Rabh=\mathrm R_{ab}, f=fabf=f_{ab}, y=h(x)y=h(x), and assume (H') Ex−(a)={a−}E^-_x(a)=\{a^-\} is a single letter. Then (a) the nonempty bispecial factors of yy are exactly, and pairwise distinct: (i) h(u)h(u), u∈Bisp*(x)u\in\mathrm{Bisp}^*(x), |f(E−(u))|≥2|f(E^-(u))|\ge2, with Ey(h(u))={(f(e),d):(e,d)∈Ex(u)}E_y(h(u))=\{(f(e),d):(e,d)\in E_x(u)\}; (ii) ah(u)a\,h(u), u∈ℒ(x)u\in\mathcal L(x), {a,b}⊆E−(u)\{a,b\}\subseteq E^-(u), |E+(au)∪E+(bu)|≥2|E^+(au)\cup E^+(bu)|\ge2, with

Ey(ah(u))={(f(a−),d):(a,d)∈Ex(u)}∪{(b,d):(b,d)∈Ex(u)}.E_y(a\,h(u))=\{(f(a^-),d):(a,d)\in E_x(u)\}\cup\{(b,d):(b,d)\in E_x(u)\}.

  1. For ordinary u∈Bisp*(x)u\in\mathrm{Bisp}^*(x) put Λh(u)=ah(u)\Lambda_h(u)=a\,h(u) if E−(u)={a,b}E^-(u)=\{a,b\}, else h(u)h(u). Λh(u)\Lambda_h(u) is the only bispecial one of the two, it is ordinary, Ey+(Λh(u))=Ex+(u)E^+_y(\Lambda_h(u))=E^+_x(u), |u|≤|Λh(u)|≤2|u|+1|u|\le|\Lambda_h(u)|\le 2|u|+1, Λh\Lambda_h is injective, and there is a bijection Retx(u)→Rety(Λh(u))\mathrm{Ret}_x(u)\to\mathrm{Ret}_y(\Lambda_h(u)), r↦r′r\mapsto r', with Ψ(r′)=MhΨ(r)\Psi(r')=M_h\Psi(r) (in fact r′r' is h(r)h(r) or a conjugate of it).
  2. As in Lemma 4(c), with aa bispecial in yy (when m=0m=0) iff |Ex+(a)∪Ex+(b)|≥2|E^+_x(a)\cup E^+_x(b)|\ge2.

Proof. By reversal. ℒR\mathcal L^R is factorial, extendable and uniformly recurrent, so it is the language of a uniformly recurrent word x̃\tilde x (take a right-infinite word all of whose prefixes lie in ℒR\mathcal L^R, König; its language is contained in ℒR\mathcal L^R and, by uniform recurrence, contains it). Since Rab(w)R=Lab(wR)\mathrm R_{ab}(w)^R=\mathrm L_{ab}(w^R), ℒ(y)R=Fact(Lab(ℒR))=ℒ(Lab(x̃))\mathcal L(y)^R=\mathrm{Fact}(\mathrm L_{ab}(\mathcal L^R))=\mathcal L(\mathrm L_{ab}(\tilde x)). Reversal exchanges E−E^- and E+E^+ (and transposes EE), preserves bispeciality and ordinarity, and maps the complete return words rwrw to ww bijectively onto the complete return words (rw)R(rw)^R to wRw^R, so the Parikh vectors of return words are preserved. (H') for xx is (H) for x̃\tilde x. Apply Lemma 4 to x̃\tilde x and reverse; note MRab=MLabM_{\mathrm R_{ab}}=M_{\mathrm L_{ab}}. ▫\square

Lemma 6 (letter permutations). For a permutation π\pi, Bisp*(π(x))=π(Bisp*(x))\mathrm{Bisp}^*(\pi(x))=\pi(\mathrm{Bisp}^*(x)) with E(π(w))=(π×π)(E(w))E(\pi(w))=(\pi\times\pi)(E(w)) and Ret(π(w))=π(Ret(w))\mathrm{Ret}(\pi(w))=\pi(\mathrm{Ret}(w)). (Obvious.)

Proof

Step 1: the bispecial factors of GG

Put x1=R12(G)x_1=\mathrm R_{12}(G), x2=L20(x1)x_2=\mathrm L_{20}(x_1), so that G=γ(G)=π1(x2)G=\gamma(G)=\pi_1(x_2) with π1=[120]\pi_1=[120] (0↦1,1↦2,2↦00\mapsto1,1\mapsto2,2\mapsto0). Hypotheses: (H') for R12\mathrm R_{12} on GG holds with 1−=01^-=0 (EG−(1)={0}E^-_G(1)=\{0\}, Lemma 2); (H) for L20\mathrm L_{20} on x1x_1 holds with 2+=12^+=1 (every 22 of x1x_1 lies in a block R12(2)=21\mathrm R_{12}(2)=21). From ℒ2(G)\mathcal L_2(G) one gets ℒ2(x1)={01,02,10,12,21}\mathcal L_2(x_1)=\{01,02,10,12,21\}.

For a nonempty ordinary bispecial factor ww of GG define Φ(w)=π1(ΛL20(ΛR12(w)))\Phi(w)=\pi_1(\Lambda_{\mathrm L_{20}}(\Lambda_{\mathrm R_{12}}(w))), where ΛR12\Lambda_{\mathrm R_{12}}, ΛL20\Lambda_{\mathrm L_{20}} are the maps of Lemma 5(b) (for R12\mathrm R_{12}) and Lemma 4(b) (for L20\mathrm L_{20}). Composing the two case distinctions (Lemma 5(b) leaves E+E^+ unchanged, Lemma 4(b) leaves E−E^- unchanged) and using π1L20R12=γ\pi_1\mathrm L_{20}\mathrm R_{12}=\gamma, π1(1)=2\pi_1(1)=2, π1(2)=0\pi_1(2)=0:

Φ(w)=sγ(w)t,s={2E−(w)={1,2}εotherwise,t={0E+(w)={0,2}εotherwise.\Phi(w)=s\,\gamma(w)\,t,\qquad s=\begin{cases}2&E^-(w)=\{1,2\}\\ \varepsilon&\text{otherwise}\end{cases},\qquad t=\begin{cases}0&E^+(w)=\{0,2\}\\ \varepsilon&\text{otherwise.}\end{cases}

The graphs transform by a relabelling E(Φ(w))={(ϕ−(e),ϕ+(d)):(e,d)∈E(w)}E(\Phi(w))=\{(\phi^-(e),\phi^+(d)):(e,d)\in E(w)\} where (from the formulas in Lemmas 4, 5 and π1\pi_1) ϕ−\phi^- is 1↦1,2↦01\mapsto1,2\mapsto0 if E−(w)={1,2}E^-(w)=\{1,2\}; 0↦1,1↦20\mapsto1,1\mapsto2 if E−(w)={0,1}E^-(w)=\{0,1\}; 0↦1,2↦20\mapsto1,2\mapsto2 if E−(w)={0,2}E^-(w)=\{0,2\}; and ϕ+\phi^+ is 0↦1,2↦20\mapsto1,2\mapsto2 if E+(w)={0,2}E^+(w)=\{0,2\}; 1↦2,2↦01\mapsto2,2\mapsto0 if E+(w)={1,2}E^+(w)=\{1,2\}; 0↦0,1↦20\mapsto0,1\mapsto2 if E+(w)={0,1}E^+(w)=\{0,1\}. The return words of Φ(w)\Phi(w) correspond bijectively to those of ww, with Ψ(r′)=MΨ(r)\Psi(r')=M\Psi(r), where

M=Mγ=(101100011),det(xI−M)=x3−2x2+x−1.M=M_\gamma=\begin{pmatrix}1&0&1\\1&0&0\\0&1&1\end{pmatrix},\qquad \det(xI-M)=x^3-2x^2+x-1 .

Proposition 1. (1) Every nonempty bispecial factor of GG is ordinary. (2) Bisp*(G)\mathrm{Bisp}^*(G) is the disjoint union of the two orbits {Φk(20):k≥0}\{\Phi^k(20):k\ge0\} ("orbit A") and {Φk(0):k≥0}\{\Phi^k(0):k\ge0\} ("orbit B"), with

E(20)={(0,1),(1,1),(1,2)},Ret(20)={20,201,2010};E(0)={(1,2),(2,1),(2,2)},Ret(0)={01,02,012}.E(20)=\{(0,1),(1,1),(1,2)\},\ \mathrm{Ret}(20)=\{20,201,2010\};\qquad E(0)=\{(1,2),(2,1),(2,2)\},\ \mathrm{Ret}(0)=\{01,02,012\}.

  1. Along orbit A the pair (E−,E+)(E^-,E^+) alternates ({0,1},{1,2})(\{0,1\},\{1,2\}) (k even) and ({1,2},{0,2})(\{1,2\},\{0,2\}) (k odd); along orbit B it alternates ({1,2},{1,2})(\{1,2\},\{1,2\}) and ({0,1},{0,2})(\{0,1\},\{0,2\}); E(Φk+4(s))=E(Φk(s))E(\Phi^{k+4}(s))=E(\Phi^k(s)). Hence Φ(w)=γ(w)\Phi(w)=\gamma(w), 2γ(w)02\gamma(w)0 (orbit A, k even/odd) and 2γ(w)2\gamma(w), γ(w)0\gamma(w)0 (orbit B, k even/odd).

Proof. Seeds. By Lemma 5(a)(ii) with u=εu=\varepsilon, 11 is bispecial in x1x_1 (EG+(1)∪EG+(2)={2,0}E^+_G(1)\cup E^+_G(2)=\{2,0\}) with Ex1(1)={(f12(0),d):(1,d)∈EG(ε)}∪{(2,d):(2,d)∈EG(ε)}={(0,0),(0,2),(2,0)}E_{x_1}(1)=\{(f_{12}(0),d):(1,d)\in E_G(\varepsilon)\}\cup\{(2,d):(2,d)\in E_G(\varepsilon)\}=\{(0,0),(0,2),(2,0)\} (ordinary). By Lemma 4(a)(ii), 22 is bispecial in x2x_2 with Ex2(2)={(e,f20(1)):(e,2)∈Ex1(ε)}∪{(e,0):(e,0)∈Ex1(ε)}={(0,1),(1,1),(1,0)}E_{x_2}(2)=\{(e,f_{20}(1)):(e,2)\in E_{x_1}(\varepsilon)\}\cup\{(e,0):(e,0)\in E_{x_1}(\varepsilon)\}=\{(0,1),(1,1),(1,0)\} (ordinary).

  1. Let ww be a shortest non-ordinary word of Bisp*(G)\mathrm{Bisp}^*(G). The bispecial factors of GG of length ≤2\le 2 are 00 and 2020 (enumeration of ℒ4(G)\mathcal L_4(G)), both ordinary, so |w|≥3|w|\ge3. v=π1−1(w)v=\pi_1^{-1}(w) is non-ordinary bispecial in x2x_2. By Lemma 4(a), v=L20(u)v=\mathrm L_{20}(u) or L20(u)2\mathrm L_{20}(u)2 with u∈{ε}∪Bisp*(x1)u\in\{\varepsilon\}\cup\mathrm{Bisp}^*(x_1); u=εu=\varepsilon gives |v|=1|v|=1, and an ordinary nonempty uu gives the ordinary v=ΛL20(u)v=\Lambda_{\mathrm L_{20}}(u) (Lemma 4(b)); so uu is non-ordinary, |u|≤|v||u|\le|v|. By Lemma 5(a), u=R12(t)u=\mathrm R_{12}(t) or 1R12(t)1\mathrm R_{12}(t) with t∈{ε}∪Bisp*(G)t\in\{\varepsilon\}\cup\mathrm{Bisp}^*(G); t=εt=\varepsilon gives u=1u=1, which is ordinary; an ordinary nonempty tt gives an ordinary uu. So t∈Bisp*(G)t\in\mathrm{Bisp}^*(G) is non-ordinary and |t|≤|u|≤|w||t|\le|u|\le|w|, whence |t|=|u|=|v|=|w||t|=|u|=|v|=|w| by minimality. The forms with an added letter are longer, so u=R12(t)u=\mathrm R_{12}(t) with no 22 in tt, and v=L20(u)v=\mathrm L_{20}(u) with no 00 in uu, so t∈1+t\in 1^+; as 11∉ℒ(G)11\notin\mathcal L(G), t=1t=1, which is not bispecial (E−(1)={0}E^-(1)=\{0\}). Contradiction.

  2. By (1) and Lemma 5(c) with m=0m=0: Bisp*(x1)=ΛR12(Bisp*(G))⊔{1}\mathrm{Bisp}^*(x_1)=\Lambda_{\mathrm R_{12}}(\mathrm{Bisp}^*(G))\sqcup\{1\}, all ordinary. By Lemma 4(c) with m=0m=0: Bisp*(x2)=ΛL20(Bisp*(x1))⊔{2}\mathrm{Bisp}^*(x_2)=\Lambda_{\mathrm L_{20}}(\mathrm{Bisp}^*(x_1))\sqcup\{2\}. Applying π1\pi_1 (Lemma 6):

Bisp*(G)=Φ(Bisp*(G))⊔{π1(ΛL20(1)),π1(2)}=Φ(Bisp*(G))⊔{20,0},\mathrm{Bisp}^*(G)=\Phi(\mathrm{Bisp}^*(G))\ \sqcup\ \{\pi_1(\Lambda_{\mathrm L_{20}}(1)),\ \pi_1(2)\}=\Phi(\mathrm{Bisp}^*(G))\sqcup\{20,\,0\},

since Ex1+(1)={0,2}E^+_{x_1}(1)=\{0,2\} gives ΛL20(1)=L20(1)2=12\Lambda_{\mathrm L_{20}}(1)=\mathrm L_{20}(1)2=12. Φ\Phi is injective. For w∈Bisp*(G)w\in\mathrm{Bisp}^*(G) we have w≠1w\ne1, so ww contains 00 or 22 and |Φ(w)|≥|γ(w)|=|w|+|w|0+|w|2>|w||\Phi(w)|\ge|\gamma(w)|=|w|+|w|_0+|w|_2\gt|w|. By induction on the length, every element of Bisp*(G)\mathrm{Bisp}^*(G) is Φk(s)\Phi^k(s) for a unique s∈{20,0}s\in\{20,0\} and k≥0k\ge0. The graphs of the seeds: E(20)E(20) is the image of Ex2(12)E_{x_2}(12), E(0)=π1(Ex2(2))E(0)=\pi_1(E_{x_2}(2)), as displayed. Return words: Ret(0)={01,02,012}\mathrm{Ret}(0)=\{01,02,012\} because after 00 comes 11 or 22, after 11 comes 00 or 22 and after 22 comes 00 (Lemma 2), and 010,0120,020010,0120,020 all occur in the prefix 01202010200120201020; Ret(20)\mathrm{Ret}(20) is obtained by Lemmas 4(b) and 6 as π1(L20(Retx1(1)))\pi_1(\mathrm L_{20}(\mathrm{Ret}_{x_1}(1))), where Retx1(1)\mathrm{Ret}_{x_1}(1) was enumerated from the exact factor set ℒ60(x1)\mathcal L_{60}(x_1) (verify.py S3); verify.py S4 compares the result with a direct enumeration in GG, and the three words are visible in the prefix 012020102012010201012020102012010201. (3) follows from (2) and the relabelling rules (finite check, verify.py S3). ▫\square

The first bispecial factors of GG (lengths 1,2,3,4,6,9,12,16,22,30,40,53,71,95,126,…1,2,3,4,6,9,12,16,22,30,40,53,71,95,126,\ldots), with the lengths of their three return words:

|w|\lvert w\rvert orbit, k E−E^- E+E^+ return-word lengths |w|/|rmin|\lvert w\rvert/\lvert r_{\min}\rvert ww
1 B,0 12 12 2,2,3 0.5 0
2 A,0 01 12 2,3,4 1 20
3 B,1 01 02 3,4,5 1 201
4 A,1 12 02 4,5,7 1 0201
6 B,2 12 12 5,7,9 1.2 020120
9 A,2 01 12 7,9,12 1.2857 201020120
12 B,3 01 02 9,12,16 1.3333 201020120201
16 A,3 12 02 12,16,21 1.3333 0201201020120201
22 B,4 12 12 16,21,28 1.375
30 A,4 01 12 21,28,37 1.4286
40 B,5 01 02 28,37,49 1.4286
53 A,5 12 02 37,49,65 1.4324
71 B,6 12 12 49,65,86 1.4490
95 A,6 01 12 65,86,114 1.4615

Step 2: the bispecial factors of V=a4(G)V=a_4(G) and U=a1(G)U=a_1(G)

Chain for VV: G→L20y1→R10y2→[021]VG\xrightarrow{\mathrm L_{20}}y_1\xrightarrow{\mathrm R_{10}}y_2\xrightarrow{[021]}V. Hypotheses: EG+(2)={0}E^+_G(2)=\{0\} ((H), 2+=02^+=0); in y1y_1 every 11 comes from a 11 of GG, which is preceded in GG by 00, whose image L20(0)=20\mathrm L_{20}(0)=20 ends with 00: Ey1−(1)={0}E^-_{y_1}(1)=\{0\} ((H'), 1−=01^-=0).

Chain for UU: G→L20y1→R01z2→L12z3→[021]UG\xrightarrow{\mathrm L_{20}}y_1\xrightarrow{\mathrm R_{01}}z_2\xrightarrow{\mathrm L_{12}}z_3\xrightarrow{[021]}U. Hypotheses: 2+=02^+=0 in GG; every 00 of y1y_1 lies in a block 2020, so Ey1−(0)={2}E^-_{y_1}(0)=\{2\}; every 11 of z2z_2 lies in a block R01(1)=10\mathrm R_{01}(1)=10, so Ez2+(1)={0}E^+_{z_2}(1)=\{0\}.

For w∈Bisp*(G)w\in\mathrm{Bisp}^*(G) let ΘV(w)\Theta_V(w), ΘU(w)\Theta_U(w) be the composites of the maps Λh\Lambda_h of Lemmas 4(b), 5(b), 6 along these chains (defined since all words involved are ordinary). We track the case distinctions of Lemmas 4(b) and 5(b); E−(w),E+(w)E^-(w),E^+(w) are 2-subsets of AA.

  • L20\mathrm L_{20} (a=2a=2, b=0b=0, 2+=02^+=0): it appends 22 iff E+(w)={0,2}E^+(w)=\{0,2\}. In that case the new right letters are f20(2+)=f20(0)=2f_{20}(2^+)=f_{20}(0)=2 and 00, so E+E^+ stays {0,2}\{0,2\}; otherwise E+E^+ becomes f20(E+(w))={1,2}f_{20}(E^+(w))=\{1,2\} (from {0,1}\{0,1\} or {1,2}\{1,2\}). E−E^- is unchanged.
  • VV: R10\mathrm R_{10} (a=1a=1, b=0b=0) prepends 11 iff the current E−E^-, i.e. E−(w)E^-(w), is {0,1}\{0,1\}. Then [021][021] maps the prepended 11 to 22 and the appended 22 to [021](R10(2))=1[021](\mathrm R_{10}(2))=1, and [021]∘R10∘L20=a4[021]\circ\mathrm R_{10}\circ\mathrm L_{20}=a_4.
  • UU: R01\mathrm R_{01} (a=0a=0, b=1b=1) prepends 00 iff E−(w)={0,1}E^-(w)=\{0,1\} and leaves E+E^+ unchanged. L12\mathrm L_{12} (a=1a=1, b=2b=2) appends 11 iff the current E+E^+ is {1,2}\{1,2\}, i.e. iff E+(w)≠{0,2}E^+(w)\ne\{0,2\}. Under [021]∘L12[021]\circ\mathrm L_{12} the prepended 00 stays 00, the 22 appended at the first step becomes [021](L12(R01(2)))=[021](12)=21[021](\mathrm L_{12}(\mathrm R_{01}(2)))=[021](12)=21, the 11 appended at the third step becomes 22, and [021]∘L12∘R01∘L20=a1[021]\circ\mathrm L_{12}\circ\mathrm R_{01}\circ\mathrm L_{20}=a_1. Exactly one of the two suffixes occurs.

This gives

ΘV(w)=[2ifE−(w)={0,1}]a4(w)[1ifE+(w)={0,2}],\Theta_V(w)=[2\ \text{if}\ E^-(w)=\{0,1\}]\ a_4(w)\ [1\ \text{if}\ E^+(w)=\{0,2\}],

ΘU(w)=[0ifE−(w)={0,1}]a1(w)[21ifE+(w)={0,2},else2],\Theta_U(w)=[0\ \text{if}\ E^-(w)=\{0,1\}]\ a_1(w)\ [21\ \text{if}\ E^+(w)=\{0,2\},\ \text{else}\ 2],

where [sifP][s\ \text{if}\ P] is ss or ε\varepsilon. The return words of Θh(w)\Theta_h(w) correspond bijectively to those of ww, with Parikh vectors multiplied by MhM_h (h=a4,a1h=a_4,a_1), because the product of the elementary incidence matrices along the chain is MhM_h.

Proposition 2.

Bisp*(V)=ΘV(Bisp*(G))⊔{1,2,21},Bisp*(U)=ΘU(Bisp*(G))⊔{2,02,21,021},\mathrm{Bisp}^*(V)=\Theta_V(\mathrm{Bisp}^*(G))\sqcup\{1,\,2,\,21\},\qquad \mathrm{Bisp}^*(U)=\Theta_U(\mathrm{Bisp}^*(G))\sqcup\{2,\,02,\,21,\,021\},

and all these bispecial factors are ordinary. The extra ones have

word factor of E(w)E(w) Parikh vectors of return words
1 V (1,0),(2,0),(2,1) (0,1,0),(1,1,1),(1,1,2)
2 V (0,1),(0,2),(2,1) (0,0,1),(1,1,1),(1,2,1)
21 V (0,1),(2,0),(2,1) (1,1,1),(1,2,1),(1,2,2)
2 U (0,0),(0,1),(1,1) (0,1,1),(1,0,1),(1,1,1)
02 U (1,0),(1,1),(2,1) (1,0,1),(1,1,1),(1,2,2)
21 U (0,0),(0,2),(1,0) (0,1,1),(1,1,1),(2,1,2)
021 U (1,2),(2,0),(2,2) (1,1,1),(1,2,2),(2,2,3)

Proof. By Proposition 1 all nonempty bispecial factors of GG are ordinary, so by Lemma 4(c) (m=0m=0) the only nonempty bispecial factor of y1=L20(G)y_1=\mathrm L_{20}(G) not of the form Λh(u)\Lambda_h(u) is the letter 22, with (Lemma 4(a)(ii), u=εu=\varepsilon) Ey1(2)={(e,f20(0)):(e,2)∈ℒ2(G)}∪{(e,0):(e,0)∈ℒ2(G)}={(0,2),(1,2),(1,0),(2,0)}E_{y_1}(2)=\{(e,f_{20}(0)):(e,2)\in\mathcal L_2(G)\}\cup\{(e,0):(e,0)\in\mathcal L_2(G)\}=\{(0,2),(1,2),(1,0),(2,0)\}; it is not ordinary (E−={0,1,2}E^-=\{0,1,2\}). Also ℒ2(y1)={01,02,12,20,22}\mathcal L_2(y_1)=\{01,02,12,20,22\}. By Lemma 5(a), with m=1m=1, the new bispecial factors after the next step come from u=εu=\varepsilon or u=2u=2:

  • VV, step R10\mathrm R_{10} (a=1a=1, b=0b=0, 1−=01^-=0, f10:0↦1f_{10}:0\mapsto1): case (i) for u=2u=2 gives 22 with graph {(1,2),(1,0),(2,0)}\{(1,2),(1,0),(2,0)\}; case (ii) for u=2u=2 gives 1212 with graph {(1,2),(1,0),(0,2)}\{(1,2),(1,0),(0,2)\} (here |E+(12)∪E+(02)|=2|E^+(12)\cup E^+(02)|=2); case (ii) for u=εu=\varepsilon gives 11 with graph {(f10(0),2)}∪{(0,1),(0,2)}={(1,2),(0,1),(0,2)}\{(f_{10}(0),2)\}\cup\{(0,1),(0,2)\}=\{(1,2),(0,1),(0,2)\}. All three are ordinary, and [021][021] turns them into 1,21,21,21,2 with the graphs of the table.
  • UU, step R01\mathrm R_{01} (a=0a=0, b=1b=1, 0−=20^-=2, f01:1↦0f_{01}:1\mapsto0): case (i) for u=2u=2 gives 22 with graph {(0,2),(0,0),(2,0)}\{(0,2),(0,0),(2,0)\}; case (ii) for u=2u=2 gives 0202 with graph {(2,2),(1,2),(1,0)}\{(2,2),(1,2),(1,0)\}; case (ii) for u=εu=\varepsilon gives 00 with graph {(2,1),(2,2),(1,2)}\{(2,1),(2,2),(1,2)\}. All are ordinary, so in z2z_2 every nonempty bispecial factor is ordinary. At the step L12\mathrm L_{12} (a=1a=1, b=2b=2, 1+=01^+=0), Lemma 4(b) maps these three to Λh(2)=12\Lambda_h(2)=12, Λh(0)=01\Lambda_h(0)=01, Λh(02)=012\Lambda_h(02)=012, and by Lemma 4(c) (m=0m=0) the only other new one is the letter 11, with graph {(0,0),(0,2),(2,2)}\{(0,0),(0,2),(2,2)\} (from ℒ2(z2)={01,10,02,20,22}\mathcal L_2(z_2)=\{01,10,02,20,22\}). [021][021] turns 12,01,012,112,01,012,1 into 21,02,021,221,02,021,2 with the graphs of the table.

The Parikh vectors of the return words of these seven short words were computed by enumeration from exact factor sets (verify.py S3); they are used only for the finite check in Step 4. Computer cross-check. Independently of this hand derivation, verify.py applies Lemmas 4-6 step by step, starting from GG where all nonempty bispecial factors are ordinary (Proposition 1). At each elementary step, Lemma 4(c)/5(c) says that the bispecial factors that are not images Λh(u)\Lambda_h(u) of ordinary ones have length ≤2m+1\le 2m+1, mm the maximal length of non-ordinary bispecial factors of the previous word, and the non-ordinary bispecial factors of the new word are among these (the Λh(u)\Lambda_h(u) are ordinary). The bound is propagated along the chain, and all bispecial factors of the intermediate words of length up to the bound (plus 2) were enumerated from exact factor sets (Lemma 2), separating the images Λh(u)\Lambda_h(u) from the new ones (verify.py S3, function walk_chain). Results: VV-chain: after L20\mathrm L_{20} the only new one is 22, non-ordinary with Ey1(2)={(0,2),(1,2),(1,0),(2,0)}E_{y_1}(2)=\{(0,2),(1,2),(1,0),(2,0)\} (as Lemma 4(a)(ii) predicts); after R10\mathrm R_{10} (bound 33) the new ones are 2,1,122,1,12, all ordinary; after [021][021]: 2,1,212,1,21. UU-chain: after L20\mathrm L_{20}: 22 (non-ordinary, as above); after R01\mathrm R_{01} (bound 3): 2,0,022,0,02, ordinary; after L12\mathrm L_{12} (bound 1): the new letter 11 and the images 12,01,01212,01,012 of the previous new ones; after [021][021]: 2,21,02,0212,21,02,021. Their graphs and return words were computed from exact factor sets. ▫\square

Every word of Propositions 1-2 of length ≤600\le 600 was also compared with an exhaustive enumeration of all bispecial factors of GG, UU, VV of length ≤600\le 600 (extension graphs and Parikh vectors of all return words agree; verify.py S4).

Step 3: complexity

In GG, UU, VV all three letters occur, |ℒ2|=5|\mathcal L_2|=5 so m(ε)=5−3−3+1=0m(\varepsilon)=5-3-3+1=0, and every nonempty bispecial factor is ordinary, hence m(w)=0m(w)=0 (Propositions 1, 2). By Lemma 1, pG(n)=pU(n)=pV(n)=2n+1p_G(n)=p_U(n)=p_V(n)=2n+1 for all nn. (For GG this is [SS, Lemma 28]†.) In particular the three words are not eventually periodic. They are uniformly recurrent: GG is the fixed point of the primitive morphism γ\gamma (M3>0M^3\gt0) — every factor ww of GG lies in some γn(0)\gamma^n(0), hence in every γn+3(c)\gamma^{n+3}(c), and GG is a concatenation of blocks γn+3(c)\gamma^{n+3}(c) — and nonerasing morphic images of uniformly recurrent words are uniformly recurrent. By the Reduction, all ten words of Figures 3-4 and all ten words of arXiv Figures 1-2 have complexity 2n+12n+1.

Step 4: critical exponent

By Lemma 3 it suffices to show, for x∈{G,U,V}x\in\{G,U,V\}:

(I)|w|<α|r|for every bispecialwand everyr∈Ret(w),(II)supw|w|/|rw|≥α.\text{(I)}\quad |w|\lt\alpha|r|\ \ \text{for every bispecial}\ w\ \text{and every}\ r\in\mathrm{Ret}(w),\qquad\text{(II)}\quad \sup_w |w|/|r_w|\ge\alpha .

Then E(x)=1+α=μE(x)=1+\alpha=\mu and the supremum is not attained. For w=εw=\varepsilon (I) is trivial; for the seven extra words of Proposition 2 it is a finite check (the largest ratio is 11). It remains to treat the families

wk=Φk(s)(x=G),Θh(Φk(s))(x=U,V),s∈{20,0},k≥0.w_k=\Phi^k(s)\ (x=G),\qquad \Theta_h(\Phi^k(s))\ (x=U,V),\qquad s\in\{20,0\},\ k\ge0 .

Linear recurrences. Let Pk=Ψ(Φk(s))P_k=\Psi(\Phi^k(s)) and, for a fixed return word rr of ss, Qk=MkΨ(r)Q_k=M^k\Psi(r) (the Parikh vector of the corresponding return word of Φk(s)\Phi^k(s)). By Proposition 1, Pk+1=MPk+ckP_{k+1}=MP_k+c_k with ck=Ψ(sk)+Ψ(tk)c_k=\Psi(s_k)+\Psi(t_k) depending only on kmod2k\bmod 2 (orbit A: 00, (1,0,1)T(1,0,1)^T; orbit B: (0,0,1)T(0,0,1)^T, (1,0,0)T(1,0,0)^T). Fix a residue ν∈{0,1,2,3}\nu\in\{0,1,2,3\} and set N=M4N=M^4, P′j=P4j+νP'_j=P_{4j+\nu}, Q′j=Q4j+νQ'_j=Q_{4j+\nu}; then P′j+1=NP′j+CP'_{j+1}=NP'_j+C, Q′j+1=NQ′jQ'_{j+1}=NQ'_j with a constant integer vector CC. The length of the bispecial factor and of the return word are g⋅P′j+κg\cdot P'_j+\kappa and g⋅Q′jg\cdot Q'_j, where g=(1,1,1)g=(1,1,1), κ=0\kappa=0 for GG, g=(1,1,1)Ma1=(3,2,2)g=(1,1,1)M_{a_1}=(3,2,2) for UU, g=(1,1,1)Ma4=(3,1,1)g=(1,1,1)M_{a_4}=(3,1,1) for VV, and κ=|s|+|t|\kappa=|s|+|t| from the explicit forms of ΘU,ΘV\Theta_U,\Theta_V. Since (E−(wk),E+(wk))(E^-(w_k),E^+(w_k)) depends only on kmod2k\bmod 2 (Proposition 1(3)), ckc_k and κ\kappa are in fact 2-periodic in kk; so CC, κ\kappa and m0m_0 below are the same for the residues ν\nu and ν+2\nu+2 (asserted in verify.py S6). We group by kmod4k\bmod 4 only because the graphs E(wk)E(w_k) are 4-periodic. So we must show Dj<0D_j\lt0 for all j≥0j\ge0, where

Dj=κ+g⋅P′j−αg⋅Q′j.D_j=\kappa+g\cdot P'_j-\alpha\,g\cdot Q'_j .

Closed form. 11 is not an eigenvalue of NN (the eigenvalues of MM are λ\lambda and β,β‾\beta,\bar\beta with ββ‾=1/λ\beta\bar\beta=1/\lambda), so X=(I−N)−1C∈ℚ3X=(I-N)^{-1}C\in\mathbb Q^3 exists and P′j=X+Nj(P′0−X)P'_j=X+N^j(P'_0-X). Hence

Dj=m0+gNjZ,m0=κ+g⋅X∈ℚ,Z=P′0−X−αQ′0∈ℚ(λ)3.D_j=m_0+g\,N^jZ,\qquad m_0=\kappa+g\cdot X\in\mathbb Q,\qquad Z=P'_0-X-\alpha Q'_0\in\mathbb Q(\lambda)^3 .

Over ℚ(λ)\mathbb Q(\lambda), x3−2x2+x−1=(x−λ)q(x)x^3-2x^2+x-1=(x-\lambda)q(x) with q(x)=x2−(2−λ)x+(λ−1)2q(x)=x^2-(2-\lambda)x+(\lambda-1)^2 (roots β,β‾\beta,\bar\beta). Let Zλ=q(M)Z/q(λ)Z_\lambda=q(M)Z/q(\lambda) (an eigenvector for λ\lambda; q(λ)=3λ2−4λ+1≠0q(\lambda)=3\lambda^2-4\lambda+1\ne0) and ZW=Z−Zλ∈kerq(M)Z_W=Z-Z_\lambda\in\ker q(M). Then

Dj=m0+θλ4j+ej,θ=g⋅Zλ∈ℚ(λ),ej=gNjZW=2Re(cβ4j),D_j=m_0+\theta\,\lambda^{4j}+e_j,\qquad \theta=g\cdot Z_\lambda\in\mathbb Q(\lambda),\qquad e_j=g\,N^jZ_W=2\,\mathrm{Re}(c\,\beta^{4j}),

and from e0,e1e_0,e_1 one gets 4|c|2=B:=e02+(e0Reβ4−e1)2/(Imβ4)2∈ℚ(λ)4|c|^2=B:=e_0^2+(e_0\,\mathrm{Re}\beta^4-e_1)^2/(\mathrm{Im}\beta^4)^2\in\mathbb Q(\lambda), hence ej2≤Bλ−4je_j^2\le B\,\lambda^{-4j}. Here β+β‾=2−λ\beta+\bar\beta=2-\lambda, ββ‾=(λ−1)2=1/λ\beta\bar\beta=(\lambda-1)^2=1/\lambda, β4+β‾4\beta^4+\bar\beta^4 and |β|8|\beta|^8 are polynomials in these, and (Imβ4)2=|β|8−(Reβ4)2>0(\mathrm{Im}\beta^4)^2=|\beta|^8-(\mathrm{Re}\beta^4)^2\gt0. If θ≤0\theta\le0, J≥0J\ge0, δJ:=−(m0+θλ4J)>0\delta_J:=-(m_0+\theta\lambda^{4J})\gt0 and δJ2>Bλ−4J\delta_J^2\gt B\lambda^{-4J}, then for all j≥Jj\ge J: −(m0+θλ4j)≥δJ>|ej|-(m_0+\theta\lambda^{4j})\ge\delta_J\gt|e_j|, i.e. Dj<0D_j\lt0.

Computation (exact; computer-assisted). verify.py S6 does all of this in exact arithmetic in ℚ(λ)=ℚ[x]/(x3−2x2+x−1)\mathbb Q(\lambda)=\mathbb Q[x]/(x^3-2x^2+x-1); signs of elements of ℚ(λ)\mathbb Q(\lambda) are decided with certified rational enclosures of λ\lambda obtained by bisection (the polynomial is increasing on [3/2,2][3/2,2]). For each of the 72 families (3 words, 2 orbits, 4 residues, and the 3 return words of Φν(s)\Phi^\nu(s), which correspond bijectively to the 3 return words of the seed ss by Proposition 1) it checks q(M)ZW=0q(M)Z_W=0, θ≤0\theta\le0, finds J≤1J\le1 with the two inequalities above (asserted; J=1J=1 occurs only for the family with θ=0\theta=0 in the classes (U,A,0)(U,A,0), (U,B,1)(U,B,1), (V,A,0)(V,A,0), (V,B,1)(V,B,1), otherwise J=0J=0), verifies Dj<0D_j\lt0 directly (exact sign of an element ℓ1−αℓ2\ell_1-\alpha\ell_2, ℓi∈ℤ\ell_i\in\mathbb Z) for j≤J+3j\le J+3, and checks that the closed form equals DjD_j exactly for these jj. This proves (I). In every one of the 24 (word, orbit, residue) classes exactly one of the three return-word families has θ=0\theta=0 (asserted in verify.py S6), namely the one coming from the return word 2020 of the seed 2020 (orbit A) resp. 0101 of the seed 00 (orbit B); for it Dj→m0D_j\to m_0, so |w|/|r|=α+Dj/|r|→α|w|/|r|=\alpha+D_j/|r|\to\alpha; as |rw|≤|r||r_w|\le|r|, (II) follows. The limits m0m_0 (for the return word with θ=0\theta=0) are:

word orbit A, k = 0,1,2,3 mod 4 orbit B, k = 0,1,2,3 mod 4
G -6/5, -9/5, -6/5, -9/5 -8/5, -7/5, -8/5, -7/5
U -4/5, -11/5, -4/5, -11/5 -12/5, -3/5, -12/5, -3/5
V -1, -2, -1, -2 -2, -1, -2, -1

So |w|−α|rw||w|-\alpha|r_w| tends to these negative constants along the respective subsequences (for UU the best gap is −3/5-3/5, for VV it is −1-1, for GG it is −6/5-6/5). Hence E(G)=E(U)=E(V)=μE(G)=E(U)=E(V)=\mu, not attained (for GG this is [SS, Theorem 29]†). With the Reduction this proves the Theorem. ◼\blacksquare

What is new

  • Conjecture 19 of [Cu-EJC] (equivalently Conjecture 1 of arXiv:2507.09387v3) is settled affirmatively for all twenty listed words: complexity 2n+12n+1 and critical exponent exactly μ\mu.
  • The twenty words fall into three language classes up to letter permutation and reversal: that of GG (a3,b1,b2,b3a_3,b_1,b_2,b_3), of U=a1(G)U=a_1(G) (a1,a2,b4,b5a_1,a_2,b_4,b_5) and of V=a4(G)V=a_4(G) (a4,b6a_4,b_6); each arXiv morphism is a conjugate of the corresponding journal morphism composed with γk\gamma^k or (γR)k(\gamma^R)^k.
  • Complete description of the bispecial factors of G,U,VG,U,V: two Φ\Phi-orbits with explicit forms sγ(w)ts\gamma(w)t, sa1(w)ts\,a_1(w)t, sa4(w)ts\,a_4(w)t, all ordinary (neutral), three return words each, and the exact asymptotic gaps |w|−α|rw|→m0∈15ℤ|w|-\alpha|r_w|\to m_0\in\frac15\mathbb Z.
  • The method (left/right insertion lemmas under the hypothesis "the inserted letter has a unique neighbour on the relevant side") is standard in spirit (S-adic descriptions of bispecial factors, as in work of Cassaigne, Labbé, Leroy and of Klouda); the self-contained Lemmas 4-5 are written for exactly the hypotheses used here.
  • The proof re-derives Lemma 28 and Theorem 29 of [SS] by a different route.

Verification

verify.py (Python 3, standard library only; python3 verify.py [NB], default NB = 300, 15 s on an idle core and about 50 s under load; NB = 600 about 2-5 min). All checks are assertions; it ends with ALL CHECKS PASSED.

  • S1: all morphism identities of the Reduction and the elementary decompositions; for each arXiv row, the conjugating word for R4.
  • S2: primitivity of γ\gamma (M3>0M^3\gt0); exact factor sets of GG by Lemma 2, asserting both condition (a) (the words γk(0)\gamma^k(0) concerned are prefixes of the prefix used) and the closure condition (b); ℒ2(G)\mathcal L_2(G).
  • S3: hypotheses (H)/(H') at every step of the three chains; the seeds 1∈x11\in x_1, 2∈x22\in x_2 and their data; Φ(w)=sγ(w)t\Phi(w)=s\gamma(w)t, ΘU\Theta_U, ΘV\Theta_V explicit forms; the extra short bispecial factors of UU, VV with the length bounds of Lemmas 4(c), 5(c).
  • S4: the lemma-generated lists of bispecial factors of G,U,VG,U,V (extension graphs, Parikh vectors of all return words) coincide with exhaustive enumeration for lengths ≤\le NB (run with NB = 600: 20 nonempty bispecial factors for GG, 21 each for UU and VV).
  • S5: brute-force complexity p(n)=2n+1p(n)=2n+1 for n≤n\le NB for GG, G′G' and all 20 images (exact factor sets).
  • S6: the certified inequality of Step 4 for all 72 families and the seven extra words, exact arithmetic in ℚ(λ)\mathbb Q(\lambda); asserts J≤1J\le1, exactly one family with θ=0\theta=0 in each of the 24 classes, and the 2-periodicity of m0m_0.
  • S7: independent brute force: largest repetition exponent with period ≤3000\le3000 in a prefix of length 60000 of each of the 20 images and of GG (bitset method); all are <μ\lt\mu, the largest found being 4919/1983=2.480585…4919/1983=2.480585\ldots (UU-class), 6233/2513=2.480302…6233/2513=2.480302\ldots (GG-class), 1255/506=2.480237…1255/506=2.480237\ldots (VV-class).

Referee pass. One independent referee pass was made by a separate model instance, which reviewed verify.py and wrote its own code from scratch (without reading the scratch scripts). It checked by hand every lemma and proposition (R1-R5, Lemmas 1-6, Propositions 1-2, Steps 3-4, including boundary cases and the six relabelling rules) and found no error. Its seven minor gaps (the derivation of ΘU,ΘV\Theta_U,\Theta_V, a hand proof of the extra bispecial factors of Proposition 2, the sentence on Ret(20)\mathrm{Ret}(20), the wording on the return words of the seed, and three assertions missing in verify.py) and its notation remarks are addressed in this version. Its independent numerical checks: all bispecial factors of G,U,VG,U,V of length ≤450\le450 (from exact factor sets of length 1500), compared with Propositions 1-2; all identities of the Reduction, and p(n)=2n+1p(n)=2n+1 for n≤1000n\le1000 for GG, G′G' and all 20 images; |w|<α|r||w|\lt\alpha|r| for k≤400k\le400 along every family, decided with a certified 1500-bit enclosure of λ\lambda, reproducing the table of m0m_0; a brute-force test of Lemmas 4(a)/5(a) and 4(b)/5(b) on words with many non-ordinary bispecial factors (a test, not a certificate); and repetitions with periods ≤5000\le5000 in prefixes of length 400000 (largest exponents found: 10939/441010939/4410 for the GG class, 5718/23055718/2305 for UU, 11597/467511597/4675 for VV, all <μ\lt\mu). Its standard-library scripts are in review/ and are run from that folder: common.py (helpers), reduction.py [NMAX] (default 400; 18 s with 1000), bisp.py [NB] [N] (default 400 1300; 10 s with 450 1500), crit.py [KMAX] (default 400; about 1 s), lemma_test.py (about 3 s). Its two other scripts, closed_form.py (numerical eigen-decomposition) and reps.py (the repetition search), need numpy and are not included.

Sources

  • [Cu-EJC] 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, definitions of γ,G,γR,G′\gamma,G,\gamma^R,G' (Section 7; read in the journal PDF).
  • [Cu-arXiv] J. D. Currie, same title, arXiv:2507.09387v3 (13 March 2026), Conjecture 1, Figures 1 and 2 (read in the HTML version; strings taken from its TeX annotations).
  • [SS] J. Shallit, A. M. Shur, Subword complexity and power avoidance, arXiv:1801.05376 (DOI 10.1016/j.tcs.2018.09.010), Lemma 28 (pG(n)=2n+1p_G(n)=2n+1) and Theorem 29 (E(G)=2+1/(λ2−1)E(G)=2+1/(\lambda^2-1)). † Only used as a cross-check; both results are re-proved here.
  • [DDP] F. Dolce, L. Dvořáková, E. Pelantová, On balanced sequences and their critical exponent, Theoret. Comput. Sci. 939 (2023), 18-47; arXiv:2108.07503. Theorem 3. † A self-contained proof of the statement used is given (Lemma 3).
  • [CLL] J. Cassaigne, S. Labbé, J. Leroy, Almost everywhere balanced sequences of complexity 2n+12n+1, arXiv:2102.10093, DOI 10.2140/moscow.2022.11.287. † Background only; not used.

† marks a source that we read only through a summarising web tool, not directly. No step of the proof depends on a source marked †.