There are More Than 2**(n/17) n-Letter Ternary Square-Free Words

Abstract

We prove that the `connective constant' for ternary square-free words is at least $2^{1/17}=\mathrm{1.0416...}$, improving on Brinkhuis and Brandenburg's lower bounds of $2^{1/24}=\mathrm{1.0293...}$ and $2^{1/22}=\mathrm{1.032...}$ respectively. This is the first improvement since 1983.

2 pages (plain TeX)