A Proof of Shur’s Conjecture on the Growth of Power-Free Languages over Large Alphabets

A square is a word of the form $uu$ where $u$ is a nonempty word. A square-free word is a word that does not contain a square as a factor. For instance, hotshots is a square, and minimize is a square-free word. In the seminal work [16], which is widely regarded as the starting point of combinatorics on words, Thue showed that there are infinite square-free words over the ternary alphabet as well as infinite cube-free words over the binary alphabet. This notion of powers and its generalizations have received a lot of attention.

One such generalization is the notion of fractional power. A word of the form $w=xx\mathrm{\dots }xy$ where $x$ is nonempty and $y$ is a prefix of $x$ is a power of exponent $\frac{|w|}{|x|}$ and of period $|x|$ (we also say that $w$ is a $\left(\frac{|w|}{|x|}\right)$-power). A square is a $2$-power, and a cube is a $3$-power. For any real $\beta >1$, we say that the word $w$ is $\beta$-free (resp. ${\beta }^{+}$-free) if it contains no $\alpha$-power as a factor with $\alpha \ge \beta$ (resp. $\alpha >\beta$). These notions were introduced by Dejean who conjectured in 1972 that for any $k\ge 5$, there exists a ${\left(\frac{k}{k-1}\right)}^{+}$-free infinite word over the $k$-ary alphabet, and proved that there exists no $\left(\frac{k}{k-1}\right)$-free infinite word over the same alphabet [5]. For $k=3$, she proved that there exists a ${\left(\frac{7}{4}\right)}^{+}$ free infinite word over the ternary alphabet [5], and also conjectured that there exists a ${\left(\frac{7}{5}\right)}^{+}$ free infinite word over the $4$-ary alphabet, which was later proven by Pansiot [10]. Different authors solved Dejean’s conjecture for the cases $k\le 11$ [9], $k\le 14$ [7], $k\ge 33$ [1], $k\ge 30$ [2], until the remaining cases were finally proven 40 years after the initial conjecture [3, 11]. This led to another conjecture about the number of ${\left(\frac{k}{k-1}\right)}^{+}$-free words over the $k$-ary alphabet. It is conjectured that for all $k\ge 3$, this language grows exponentially [8], and that as $k$ goes to infinity, the growth rate converges to a constant whose first digits are $1.242$ [3, 15]. For all but six cases, it has been proven that these languages grow exponentially [6, 17, 4]. The second part of the conjecture remains completely open.

Let $ℒ(k,p)$ denote the languages of $p$-free words over an alphabet of size $k$. The growth rate $\alpha (k,p)={lim}_{n\to \mathrm{\infty }}{|{ℒ}_n(k,p)|}^{1/n}$, where ${ℒ}_n(k,p)$ is the set of words with length $n$ in $ℒ(k,p)$, is usually hard to estimate and requires a large amount of computation. The previously mentioned conjecture asserts that $\underset{k\to \mathrm{\infty }}{lim}\alpha (k,{\left(\frac{k}{k-1}\right)}^{+})\approx 1.24$. Shur suggests an interesting problem: study the asymptotic order of $\alpha (k,p)$ when $k\to \mathrm{\infty }$ for fixed $p>1$. For an overview of progress on the problem, we refer the reader to the intensive survey of Shur [14]. In particular, Shur [13] settled the problem when the degree of the power is at least $2$ in Theorem 1 below.

We extend the strict total order over the reals to the numbers of the form $x^{+}$ in such a way that for all , we have . That is, $x^{+}$ is right after $x$ in this order.

However, the problem for powers with degree less than $2$ is still open and Shur [13] suggested the following conjecture.

Note that for all $k$ and for all $x,y\in ℝ\cup \{x^{+}:x\in ℝ\}$, if $x\le y$ then $ℒ(k,x)\subseteq ℒ(k,y)$. This implies that $\alpha (k,x)$ is a non-decreasing function of $x$. Moreover, if Shur’s conjecture holds then for every integer $n$ and $k$, we have

Shur’s conjecture implies that most of the jump between $\alpha (k,\frac{n}{n-1})$ and $\alpha (k,\frac{n+1}{n})$ is located between $\alpha (k,\frac{n}{n-1})$ and $\alpha (k,{\left(\frac{n}{n-1}\right)}^{+})$. It provides precise bounds on the asymptotic behavior of $\alpha (k,\beta )$ tight up to $\frac{1}{k}$ for every . In particular, if $p\in ℝ\cup \{x^{+}:x\in ℝ\}$ is such that , then $\alpha (k,{\left(\frac{n+1}{n}\right)}^{+})\le \alpha (k,p)\le \alpha (k,\frac{n}{n-1})$, which implies

That is, this conjecture provides for all $p$ a good estimate of the asymptotic behavior of $\alpha (k,p)$ as $k$ goes to infinity. This conjecture implies other similar empirical facts that also hold for $\beta >2$ and illustrate the particular behavior of $\alpha (k,\beta )$ ((1) and (2) are respectively called small variation and big jump in [13]).

Using a counting argument, the second author has established the lower bound in [12].

Shur has actually confirmed the other direction of the inequality for $n\le 9$ by a computer-assisted proof which settles the conjecture for these cases [13]. In this article, we settle Shur’s conjecture, by proving the upper bound for all $n\ge 2$.

Shur’s proof for $n\le 9$ considers a regular language that contains $ℒ(k,\frac{n}{n-1})$ (resp. $ℒ(k,{\left(\frac{n}{n-1}\right)}^{+})$) and uses standard tools from automata theory to upper bound the growth of this language. His proof technique allows him to work with all $k$, for one fixed $n$, by considering the automaton where states are taken up to isomorphism (that is, up to renaming of the letters). However, this technique needs to explicitly construct the automaton for each specific value $n$, which requires the use of computers. Proving the result for all $n$ asks for a different approach. Moreover, Shur’s approach is to explicitly construct the automata that avoid powers up to a given length. The states of these automata correspond to suffixes of certain lengths, hence the size of the automata grows exponentially. The main idea behind our proof is also to construct a sequence of automata for all $n$ that approximate the true automata. However, they must be simple enough to allow estimating the growth rates manually, and include all the words in the languages (to ensure that we obtain a proper upper bound), but do not include relatively too many forbidden words (to ensure that the upper bound on the growth rate is sharp).

In this section, we settle Inequality (5) for $\left(\frac{n}{n-1}\right)$-free words. Inequality (4) for ${\left(\frac{n}{n-1}\right)}^{+}$-free words can be proved similarly.

For any two integers $a\le b$, we write $[a..b]$ for the set of integers $\{a,\mathrm{\dots },b\}$, and we write $a\mathrm{\dots }b$ for the word $a\cdot (a+1)\cdot (a+2)\mathrm{\dots }(b-1)\cdot b$.

Fix $n,k\ge 2$. We denote by $ℒ$ the language of words over $k$ letters that avoid $p$-powers isomorphic to $1\mathrm{\dots }m1$ and $12\mathrm{\dots }m12$ for any $p\ge \left(\frac{n}{n-1}\right)$ and any $m$. Since $ℒ$ contains all $\left(\frac{n}{n-1}\right)$-free words, the following theorem directly implies Inequality (5) of Shur’s conjecture. This section is devoted to the proof of this theorem.

The following fact simply illustrates that two occurrences of the same letter cannot be too close, as it would cause the existence of a $p$-power isomorphic to $1\mathrm{\dots }m1$ with $p\ge \frac{n}{n-1}$.

It directly implies that the growth of $ℒ$ is at most $k+1-n$. The term $-\frac{n-1}{k}$ requires considering the powers isomorphic to $12\mathrm{\dots }m12$.

The idea is to construct an automaton whose language is a superset of $ℒ$. Shur noted in [13] that the size of the automaton recognizing $ℒ$ is exponential in $n$ and is really difficult to analyze. But by considering a slightly larger language, we can construct an automaton with a much smaller number of states that we will be able to analyze, but whose growth rate is really close to the original language (up to the $O\left(\frac{1}{k^2}\right)$ term).

For this, we define the following states for any long enough word $w$ (we require $|w|\ge 2n-1$):

• $\mathrm{■}$

  $\boxed{m}$ for $m\in [n..2n-2]$: if a suffix of $w$ is isomorphic to $m1\mathrm{\dots }m$.

• $\mathrm{■}$

  $\widehat{m}$ for $m\in [n..2n-2]$: if a suffix of $w$ is isomorphic to $x1\mathrm{\dots }m$ with $x$ satisfying

We provide some intuition about this definition. The number $m$ in the states $\widehat{m},\boxed{m}$ stands for the length of the longest suffix containing only distinct letters, hence the letter in front of that suffix should appear in the suffix (the only exception¹¹1It might be more natural to write this state as $\widehat{\ge 2n-2}$, but for the sake of notation it is more convenient to keep it as $\widehat{2n-2}$. being $\widehat{2n-2}$ as it actually covers all the lengths from $2n-2$ up to $k$). The states $\boxed{m}$ and $\widehat{m}$ differ based on whether this reoccurring letter is the last letter of the word. The states $\boxed{m}$ are distinguished from the other state, since when the word ends with $m1\mathrm{\dots }m$ and we know that the next letter cannot be $1$ (since this would create a power of the form $m1\mathrm{\dots }m1$), that is, we know that at least one more letter is forbidden in the next position. The length of this power actually suggests the choice of the seemingly-arbitrary number $2n-2$.

From here on, we assume

We now describe how appending a letter at the end of a word from $ℒ$ can alter the state. In particular, we need $T(s_1,s_2)$ such that for every states $s_1,s_2$ and for any $w\in ℒ$ in state $s_1$,

That is, there are at most $T(s_1,s_2)$ letters $\alpha \in [1..k]$ such that $w\alpha$ is in $ℒ$ and is in state $s_2$.

In the following lemmas, we provide such a $T$. For convenience, we use the following notation:

As mentioned in the introduction (see Equation (3)), our result provides for all $p$ a good estimate for $\alpha (k,p)$ up to an error term $1/k+O(1/k^2)$. When we only care about powers isomorphic to $1\mathrm{\dots }\mathrm{\ell }1$ and $12\mathrm{\dots }\mathrm{\ell }12$, the difference between $p$-powers for $p\ge \frac{n}{n-1}$ and for $p>\frac{n}{n-1}$ lies only in the range of $\mathrm{\ell }$. By varying the length $\mathrm{\ell }$, we might allow ourselves to address $p$-powers for a fraction $p$ that may be of more complicated nature than $\frac{n}{n-1}$. So applying our approach for all $p$ instead of only $p$ of the form $\frac{n}{n-1}$ or ${\left(\frac{n}{n-1}\right)}^{+}$ might be enough to replace this error term by $O(1/k^2)$.

On the other hand, as conjectured by Shur, and later by the second author, the behavior of the growth rate up to the $O(1/k^2)$ term is controlled by powers whose tail is of length $1$ or $2$. It seems natural to wonder whether increasing the precision up to the $O(1/k^3)$ term requires precisely the considerations of powers with tails of length $3$. Shall the degree of the order of precision grow linearly with respect to the length of the tails?