Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.09387 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915860460863488 |
|---|---|
| author | Currie, James D. |
| author_facet | Currie, James D. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09387 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Words with factor complexity $2n+1$ and minimal critical exponent Currie, James D. Combinatorics Formal Languages and Automata Theory 68R15 G.2.1 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. |
| title | Words with factor complexity $2n+1$ and minimal critical exponent |
| topic | Combinatorics Formal Languages and Automata Theory 68R15 G.2.1 |
| url | https://arxiv.org/abs/2507.09387 |