Given a finite set $A=\{a_1,\ldots , a_k\}$, consider the sequences of any length that can be constructed using the elements of $A$ and which contain no repetition, a repetition being a pair of consecutive subsequences (of any length) that are equal. Is it true that $k = 4$ is the minimum number of elements in $A$ that allows the construction of sequences of any length containing no repetition? Can anyone indicate a reference for this result, if true?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Wikipedia has some examples of square-free sequences of infinite length (and therefore square-free words of arbitrary length) over alphabets with 3 letters. https://en.wikipedia.org/wiki/Square-free_word
One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet {0,±1} obtained by taking the first difference of the Thue–Morse sequence.[6][7] That is, from the Thue–Morse sequence
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is
1, 0, −1, 1, −1, 0, 1, 0, −1, 0, 1, −1, 1, 0, −1, ... (sequence A029883 in the OEIS).
As there are no square-free sequences of length $4$ over an alphabet of size 2 (say the alphabet is $\{a, b\}$; then if the sequence WLOG starts with $a$, by the fact that it can't contain immediate repeats it must go $abab$, a contradiction), $3$ is the minimal alphabet size for infinite square-free sequences.
