9
$\begingroup$

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?

$\endgroup$
0
17
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy