What is the maximum length of a non-repeating word on $n$ letters?

Question

Let $X$ denote a set and $F_{\mathbf{Mon}}X$ denote the free monoid on $X$.

Call a word $w \in F_{\mathbf{Mon}}X$ non-repeating iff for all words $x,y,z \in F_{\mathbf{Mon}}X,$ we have:

$$w = xy^2 z \rightarrow y = 1$$

For example, if $X = \{a,b\}$, then the non-repeating words in $F_{\mathbf{Mon}}X$ are:

$$\{1,a,b,ab,ba,aba,bab\}$$

It turns out that if $X$ is finite, then $F_{\mathbf{Mon}}X$ has only finitely-many non-repeating words. Therefore, it has one or more non-repeating words of maximum length.

Question. Suppose $X$ is a finite set, $n$ is a natural number, and $|X|=n.$ In terms of $n$, what is the maximum length of a non-repeating word in $F_{\mathbf{Mon}}X$?

More briefly: what is the maximum length of a non-repeating word on $n$ letters?

Eric Tressler · Accepted Answer · 2015-10-12T23:33:18.980

3

These are commonly called squarefree words (https://en.wikipedia.org/wiki/Square-free_word). With three letters, they can be arbitrarily long. One source for this result is a paper of Baake, Elser, and Grimm: The Entropy of Square-Free Words (http://arxiv.org/abs/math-ph/9809010). From this paper, you can track down the original proof if you like, but I believe it may be due to Thue, and in German.

A construction that I found in Avoiding and Enforcing Repetitive Structures on Words, the 2014 dissertation of Mike Müller:

Let $h(0) = 0121$, $h(1) = 032$, $h(2) = 013$, and $h(3) = 0302$. Then $h^{(n)}(0)$ is squarefree for all $n$.

This is over four letters, but you can track down similar constructions for three letters from these sources (maybe even in Müller — I didn't read his entire dissertation).

edited Oct 12 '15 at 23:33

answered Oct 12 '15 at 23:15

Eric Tressler

4,309

It's hard for me to square (pun intended) what you're saying here with what I already know. In particular, the free band on $n$ generators is finite. But isn't there a natural bijection between squarefree non-empty words in $X$ and elements of the free band on $X$? (A band is an idempotent semigroup.) – goblin GONE Oct 12 '15 at 23:49
See here also. – goblin GONE Oct 13 '15 at 00:00
The existence of square-free words on a three-letter alphabet was proved by Axel Thue in the early 1900s. There is no contradiction with the fact that the free band on three generators is finite. See Free idempotent semigroup with 3 generators for more details. – J.-E. Pin Oct 13 '15 at 08:09
@J.-E.Pin Thank you for the link and clarification. – Eric Tressler Oct 13 '15 at 10:48
@eric-tressler You're welcome. – J.-E. Pin Oct 13 '15 at 10:54

What is the maximum length of a non-repeating word on $n$ letters?

1 Answers1

Linked