square-free sequence

A square-free sequence is a sequence which has no adjacent repeating subsequences of any length.

The name “square-free” comes from notation: Let $\{s\}$ be a sequence. Then $\{s,s\}$ is also a sequence, which we write “compactly” as $\{s^2\}$. In the rest of this entry we use a compact notation, lacking commas or braces. This notation is commonly used when dealing with sequences in the capacity of strings. Hence we can write $\{s,s\}=ss=s^2$.

Some examples:

• $xabcabcx=x{(abc)}^{2}x$, not a square-free sequence.

• $abcdabc$ cannot have any subsequence written in square notation, hence it is a square-free sequence.

• $ababab={(ab)}^3=ab{(ab)}^2$, not a square-free sequence.

Note that, while notationally similar to the number-theoretic sense of “square-free,” the two concepts are distinct. For example, for integers $a$ and $b$ the product $aba=a^{2}b$, a square. But as a sequence, $aba=\{a,b,a\}$; clearly lacking any commutativity that might allow us to shift elements. Hence, the sequence $aba$ is square-free.