square-free sequence

A square-free sequence is a sequence which has no adjacent repeating subsequencesMathworldPlanetmath 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 {s2}. 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=s2.

Some examples:

  • xabcabcx=x(abc)2x, 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=a2b, 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