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 morphism is written , and . Let
Let be the real root of and
(the last identity holds in and is checked exactly in verify.py).
Theorem. For every morphism of Figure 3 of [Cu-EJC] the word , and for every morphism of Figure 4 the word , has factor complexity for all and critical exponent exactly (the supremum is not attained). The same holds for the morphisms of Figures 1 and 2 of arXiv:2507.09387v3.
Figure 3 (applied to ): , , , . Figure 4 (applied to ): , , , , , . arXiv v3, Figure 1 (applied to ): , , , . arXiv v3, Figure 2 (applied to ): , , , , , .
Both lists, the definitions of , , , 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 or ).
For itself, and 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 anyway.
Reduction
Notation. For an infinite word , is its set of factors, the number of factors of length , and its critical exponent (a period of is an integer with for ). For a set of words , is the set of factors of elements of , and .
R1 (invariance). and depend only on ; they do not change if is replaced by for a letter permutation , or by (reversal is a length-preserving bijection of onto and is a period of iff it is a period of ). For every morphism and every word , (any factor of lies in the image of a factor of ), and , hence .
R2 (). , so . The incidence matrix of has positive cube (verify.py S2), so contains every letter for every ; hence , and .
R3 (two exact identities between and ). Put , , . Then and . Since , the word is a fixed point of beginning with ; a fixed point of beginning with is unique (its image of is , of length ), and is one; so . Therefore
R4 (conjugate morphisms). Let be morphisms and a word with for every letter , such that is a prefix of every and a suffix of every . Let be the language of a recurrent infinite word. Then . Proof. By induction for every word . For pick letters with (recurrence). has the prefix , so ; has the suffix , so .
R5 (the list reduces to three words). Let , and (as letter maps). The following identities of morphisms are checked character by character in verify.py S1:
and , satisfy the hypothesis of R4 with . Put and . Using R1-R4:
- ; and have the language ; .
- , and likewise .
- , using R3, R4 and . Then .
- arXiv v3: for each row of its Figure 1 (resp. 2),
verify.pyS1 finds a word such that and (resp. ) satisfy the hypothesis of R4 (in one of the two orders), with for Figure 1 (where ) and for Figure 2 (where ). Since and , each arXiv word has the same language as the corresponding journal word.
Hence, by R1, the Theorem is equivalent to: , and have complexity and critical exponent (classes: : ; : ; : ).
Elementary decompositions. For distinct letters let (left insertion) and (right insertion) be the morphisms
and the letter map , (). Writing letter permutations as words , one checks directly (and verify.py S1):
Lemmas
Throughout, is a uniformly recurrent infinite word over in which all three letters occur, . For :
is bispecial if ; ordinary if moreover and (then ). is the set of nonempty bispecial factors. A return word to is for two consecutive occurrences of in ; equivalently, is a return word to iff , is a prefix of and has exactly two occurrences of (so the set depends only on ; it is finite by uniform recurrence). denotes the Parikh vector , the incidence matrix of (column is ), so .
Lemma 1 (Cassaigne's formula). Let . Then , and unless is bispecial. Consequently, if all three letters occur and for every bispecial (including ), then for all . Proof. Every factor of length is uniquely with , so . Every factor of length is uniquely , , and ; hence . Subtracting gives the formula. If then , so ; symmetrically if . Finally , , so and .
Lemma 2 (exact factor sets, used by verify.py). Let and let be a set of words of length such that (a) contains the length- factors of for every with or , and (b) every length- factor of , , lies in . Then ; if is the set of length- factors of a prefix of , then . Proof. A factor of length of is a factor of some ; induct on . If or use (a). Otherwise lies in for a factor of with (each letter of contributes at least one letter to ); extend inside to a factor of length exactly ; by induction and by (b). The factors of length of are the length- factors of , (images are nonempty). By hand, : , , , , give
Lemma 3 (critical exponent via bispecial factors; Dolce-Dvořáková-Pelantová [DDP, Thm 3]†). If is uniformly recurrent and not periodic,
Proof (self-contained). () If is a shortest return word to , occurs at and , so has period and . () Let have period , (if the ratio is ). As is not periodic, there is with . Take an occurrence of at a position (recurrence) and the maximal interval on which has period . It is finite on the right: otherwise has period ; every prefix of occurs in (recurrence), so every prefix of has period and is periodic. And : otherwise . Put . Then occurs at and at ; by maximality and , so is left and right special. Occurrences at distance give , so .
Lemma 4 (left insertion). Let , , , , and assume
- The nonempty bispecial factors of are exactly the following words, and they are pairwise distinct:
- , for with ; then ;
- , for (possibly empty) with and ; then
Let be ordinary. Put if and otherwise. Then is the only one of that is bispecial in ; it is ordinary, , and (bijectively). Moreover , and is injective.
If every non-ordinary word of has length ( if there is none), then every that is not of the form with ordinary has length ; for the only possible such is the letter , and is bispecial in iff .
Proof. Write and call () the cuts. The blocks are , and (the third letter). Their first letters are never and their second letters are ; hence a position is a cut iff . Every block ends with the letter it codes ( ends with ), and the first letter of is . is injective on words ( is a suffix code).
Factors starting with . An occurrence of at is preceded by ; so a factor starting with has and is not left special.
Desubstitution. Let be a nonempty factor of not starting with , occurring at . Then is a cut. If does not end with , the position is a cut (the last letter of is , the end of a block , or the third letter, a whole block); so and, by injectivity, with independent of the occurrence. Thus the occurrences of are exactly the positions , an occurrence of (conversely occurs there). The letter before (when ) is the last letter of , i.e. , the letter after is . Hence , using that every factor of has occurrences at positions (recurrence). If ends with , that last is at a cut (it is not ), so where , , and the block starting at is or , i.e. . So the occurrences of correspond to the occurrences of and of ; the letter after is in the second case and in the first case, by (H). This gives the formula in (ii); in particular , two distinct letters ( is not in the image of ).
(a). By the above a nonempty bispecial is either ( not ending with ) or . In the first case and , so is bispecial iff is left special and (which forces right special); since . In the second case is right special iff both and occur, and then left special iff . Conversely the words listed are factors with the stated graphs. Distinctness: by (H) a word ending with has the single right extension , so a right special in (i) does not end with , hence does not end with , while the words in (ii) do; within each family use injectivity of .
(b). Let be ordinary, . If , is injective on , so is bispecial with a graph isomorphic to , and is not right special ( or is missing). If , has , while is bispecial: every has an edge to or , so , and its graph is with the right vertex renamed (), again isomorphic. In both cases is unchanged. Return words: in both cases the occurrences of are exactly the positions with an occurrence of (in case (ii) because every occurrence of is followed by or ). This map is increasing, so consecutive occurrences correspond and the return word between them is . Length bounds: . Injectivity: determines whether it ends with , and then .
(c). By (a), such a is or with ( in (ii) is left and right special or empty). If is ordinary and nonempty, (b) gives . If then (the form (i) needs ). Otherwise is non-ordinary, and . The criterion for is (ii) with .
Lemma 5 (right insertion). Let , , , , and assume (H') is a single letter. Then (a) the nonempty bispecial factors of are exactly, and pairwise distinct: (i) , , , with ; (ii) , , , , with
- For ordinary put if , else . is the only bispecial one of the two, it is ordinary, , , is injective, and there is a bijection , , with (in fact is or a conjugate of it).
- As in Lemma 4(c), with bispecial in (when ) iff .
Proof. By reversal. is factorial, extendable and uniformly recurrent, so it is the language of a uniformly recurrent word (take a right-infinite word all of whose prefixes lie in , König; its language is contained in and, by uniform recurrence, contains it). Since , . Reversal exchanges and (and transposes ), preserves bispeciality and ordinarity, and maps the complete return words to bijectively onto the complete return words to , so the Parikh vectors of return words are preserved. (H') for is (H) for . Apply Lemma 4 to and reverse; note .
Lemma 6 (letter permutations). For a permutation , with and . (Obvious.)
Proof
Step 1: the bispecial factors of
Put , , so that with (). Hypotheses: (H') for on holds with (, Lemma 2); (H) for on holds with (every of lies in a block ). From one gets .
For a nonempty ordinary bispecial factor of define , where , are the maps of Lemma 5(b) (for ) and Lemma 4(b) (for ). Composing the two case distinctions (Lemma 5(b) leaves unchanged, Lemma 4(b) leaves unchanged) and using , , :
The graphs transform by a relabelling where (from the formulas in Lemmas 4, 5 and ) is if ; if ; if ; and is if ; if ; if . The return words of correspond bijectively to those of , with , where
Proposition 1. (1) Every nonempty bispecial factor of is ordinary. (2) is the disjoint union of the two orbits ("orbit A") and ("orbit B"), with
- Along orbit A the pair alternates (k even) and (k odd); along orbit B it alternates and ; . Hence , (orbit A, k even/odd) and , (orbit B, k even/odd).
Proof. Seeds. By Lemma 5(a)(ii) with , is bispecial in () with (ordinary). By Lemma 4(a)(ii), is bispecial in with (ordinary).
Let be a shortest non-ordinary word of . The bispecial factors of of length are and (enumeration of ), both ordinary, so . is non-ordinary bispecial in . By Lemma 4(a), or with ; gives , and an ordinary nonempty gives the ordinary (Lemma 4(b)); so is non-ordinary, . By Lemma 5(a), or with ; gives , which is ordinary; an ordinary nonempty gives an ordinary . So is non-ordinary and , whence by minimality. The forms with an added letter are longer, so with no in , and with no in , so ; as , , which is not bispecial (). Contradiction.
By (1) and Lemma 5(c) with : , all ordinary. By Lemma 4(c) with : . Applying (Lemma 6):
since gives . is injective. For we have , so contains or and . By induction on the length, every element of is for a unique and . The graphs of the seeds: is the image of , , as displayed. Return words: because after comes or , after comes or and after comes (Lemma 2), and all occur in the prefix ; is obtained by Lemmas 4(b) and 6 as , where was enumerated from the exact factor set (verify.py S3); verify.py S4 compares the result with a direct enumeration in , and the three words are visible in the prefix . (3) follows from (2) and the relabelling rules (finite check, verify.py S3).
The first bispecial factors of (lengths ), with the lengths of their three return words:
| orbit, k | return-word lengths | |||||
|---|---|---|---|---|---|---|
| 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 and
Chain for : . Hypotheses: ((H), ); in every comes from a of , which is preceded in by , whose image ends with : ((H'), ).
Chain for : . Hypotheses: in ; every of lies in a block , so ; every of lies in a block , so .
For let , be the composites of the maps 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); are 2-subsets of .
- (, , ): it appends iff . In that case the new right letters are and , so stays ; otherwise becomes (from or ). is unchanged.
- : (, ) prepends iff the current , i.e. , is . Then maps the prepended to and the appended to , and .
- : (, ) prepends iff and leaves unchanged. (, ) appends iff the current is , i.e. iff . Under the prepended stays , the appended at the first step becomes , the appended at the third step becomes , and . Exactly one of the two suffixes occurs.
This gives
where is or . The return words of correspond bijectively to those of , with Parikh vectors multiplied by (), because the product of the elementary incidence matrices along the chain is .
Proposition 2.
and all these bispecial factors are ordinary. The extra ones have
| word | factor of | 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 are ordinary, so by Lemma 4(c) () the only nonempty bispecial factor of not of the form is the letter , with (Lemma 4(a)(ii), ) ; it is not ordinary (). Also . By Lemma 5(a), with , the new bispecial factors after the next step come from or :
- , step (, , , ): case (i) for gives with graph ; case (ii) for gives with graph (here ); case (ii) for gives with graph . All three are ordinary, and turns them into with the graphs of the table.
- , step (, , , ): case (i) for gives with graph ; case (ii) for gives with graph ; case (ii) for gives with graph . All are ordinary, so in every nonempty bispecial factor is ordinary. At the step (, , ), Lemma 4(b) maps these three to , , , and by Lemma 4(c) () the only other new one is the letter , with graph (from ). turns into 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 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 of ordinary ones have length , 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 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 from the new ones (verify.py S3, function walk_chain). Results: -chain: after the only new one is , non-ordinary with (as Lemma 4(a)(ii) predicts); after (bound ) the new ones are , all ordinary; after : . -chain: after : (non-ordinary, as above); after (bound 3): , ordinary; after (bound 1): the new letter and the images of the previous new ones; after : . Their graphs and return words were computed from exact factor sets.
Every word of Propositions 1-2 of length was also compared with an exhaustive enumeration of all bispecial factors of , , of length (extension graphs and Parikh vectors of all return words agree; verify.py S4).
Step 3: complexity
In , , all three letters occur, so , and every nonempty bispecial factor is ordinary, hence (Propositions 1, 2). By Lemma 1, for all . (For this is [SS, Lemma 28]†.) In particular the three words are not eventually periodic. They are uniformly recurrent: is the fixed point of the primitive morphism () — every factor of lies in some , hence in every , and is a concatenation of blocks — 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 .
Step 4: critical exponent
By Lemma 3 it suffices to show, for :
Then and the supremum is not attained. For (I) is trivial; for the seven extra words of Proposition 2 it is a finite check (the largest ratio is ). It remains to treat the families
Linear recurrences. Let and, for a fixed return word of , (the Parikh vector of the corresponding return word of ). By Proposition 1, with depending only on (orbit A: , ; orbit B: , ). Fix a residue and set , , ; then , with a constant integer vector . The length of the bispecial factor and of the return word are and , where , for , for , for , and from the explicit forms of . Since depends only on (Proposition 1(3)), and are in fact 2-periodic in ; so , and below are the same for the residues and (asserted in verify.py S6). We group by only because the graphs are 4-periodic. So we must show for all , where
Closed form. is not an eigenvalue of (the eigenvalues of are and with ), so exists and . Hence
Over , with (roots ). Let (an eigenvector for ; ) and . Then
and from one gets , hence . Here , , and are polynomials in these, and . If , , and , then for all : , i.e. .
Computation (exact; computer-assisted). verify.py S6 does all of this in exact arithmetic in ; signs of elements of are decided with certified rational enclosures of obtained by bisection (the polynomial is increasing on ). For each of the 72 families (3 words, 2 orbits, 4 residues, and the 3 return words of , which correspond bijectively to the 3 return words of the seed by Proposition 1) it checks , , finds with the two inequalities above (asserted; occurs only for the family with in the classes , , , , otherwise ), verifies directly (exact sign of an element , ) for , and checks that the closed form equals exactly for these . This proves (I). In every one of the 24 (word, orbit, residue) classes exactly one of the three return-word families has (asserted in verify.py S6), namely the one coming from the return word of the seed (orbit A) resp. of the seed (orbit B); for it , so ; as , (II) follows. The limits (for the return word with ) 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 tends to these negative constants along the respective subsequences (for the best gap is , for it is , for it is ). Hence , not attained (for this is [SS, Theorem 29]†). With the Reduction this proves the Theorem.
What is new
- Conjecture 19 of [Cu-EJC] (equivalently Conjecture 1 of arXiv:2507.09387v3) is settled affirmatively for all twenty listed words: complexity and critical exponent exactly .
- The twenty words fall into three language classes up to letter permutation and reversal: that of (), of () and of (); each arXiv morphism is a conjugate of the corresponding journal morphism composed with or .
- Complete description of the bispecial factors of : two -orbits with explicit forms , , , all ordinary (neutral), three return words each, and the exact asymptotic gaps .
- 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 (); exact factor sets of by Lemma 2, asserting both condition (a) (the words concerned are prefixes of the prefix used) and the closure condition (b); .
- S3: hypotheses (H)/(H') at every step of the three chains; the seeds , and their data; , , explicit forms; the extra short bispecial factors of , with the length bounds of Lemmas 4(c), 5(c).
- S4: the lemma-generated lists of bispecial factors of (extension graphs, Parikh vectors of all return words) coincide with exhaustive enumeration for lengths NB (run with NB = 600: 20 nonempty bispecial factors for , 21 each for and ).
- S5: brute-force complexity for NB for , 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 ; asserts , exactly one family with in each of the 24 classes, and the 2-periodicity of .
- S7: independent brute force: largest repetition exponent with period in a prefix of length 60000 of each of the 20 images and of (bitset method); all are , the largest found being (-class), (-class), (-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 , a hand proof of the extra bispecial factors of Proposition 2, the sentence on , 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 of length (from exact factor sets of length 1500), compared with Propositions 1-2; all identities of the Reduction, and for for , and all 20 images; for along every family, decided with a certified 1500-bit enclosure of , reproducing the table of ; 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 in prefixes of length 400000 (largest exponents found: for the class, for , for , all ). 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 and minimal critical exponent, Electron. J. Combin. 33(3) (2026), #P3.31, DOI 10.37236/14527. Conjecture 19, Figures 3 and 4, definitions of (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 () and Theorem 29 (). † 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 , 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 †.