Words with factor complexity $2n+1$ and minimal critical exponent
Word ${\mathbf G}$ is the fixed point of the morphism $γ=[01,2,02]$. In 2019, Shallit and Shur showed that ${\mathbf G}$ has factor complexity $2n+1$. They also showed that ${\mathbf G}$ has critical exponent $μ=2+\frac{1}{λ^2-1}= 2.4808726\cdots$, where $λ=1.7548777$ is the real zero of $x^3-2x+x-1=0$. They conjectured that this was the least possible critical exponent among words with factor complexity $2n+1$. We confirm their conjecture. The proof, using an intricate case analysis, is by computer. The relevant program generates a `human readable' proof.
Institutions
- The University of Winnipeg (CA)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2025-07-12
- Primary Topic
- semigroups and automata theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00