Words with factor complexity $2n+1$ and minimal critical exponent
This resolves a specific conjecture in combinatorics on words, providing a precise minimal bound for critical exponents in this complexity class, which is incremental but definitive.
The paper confirms a conjecture by Shallit and Shur that the word G, defined by a specific morphism, has the minimal critical exponent of approximately 2.4808726 among all words with factor complexity 2n+1, using a computer-assisted proof with case analysis.
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.