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.

Title	square-free sequence
Canonical name	SquarefreeSequence
Date of creation	2013-03-22 11:55:36
Last modified on	2013-03-22 11:55:36
Owner	akrowne (2)
Last modified by	akrowne (2)
Numerical id	12
Author	akrowne (2)
Entry type	Definition
Classification	msc 11B83
Synonym	square free sequence