Shuffied Lyndon Words

The set of Lyndon words of length \(N\) is obtained by choosing those strings of length \(n\) over a finite alphabet which are lexicographically least in the aperiodic equivalence classes determined by cyclic permutation. We prove that interleaving two Lyndon words of length \(n\) produces a Lyndon word of length \(2n\). For the binary alphabet \(\{0, 1\}\) we represent the set of Lyndon words of length \(n\) as vertices of the \(n\)-cube. It is known that the set of Lyndon words of length \(n\) form a connected subset of the \(n\)-cube. A path of vertices in the \(n\)-cube is a list of strings of length \(n\) in which adjacent strings differ in a single bit. Using paths of Lyndon words in the \(n\)-cube we construct longer paths of Lyndon words in higher order cubes by shuffling and concatenation.