Infinite Self-Shuffling Words

Abstract

In this paper we introduce and study a new property of infinite words: An infinite word $x\in A^{\mathbb{N}}$, with values in a finite set $A$, is said to be $k$-self-shuffling $(k\ge 2)$ if $x$ admits factorizations: $x={\prod }_{i=0}^{\infty }{U}_i^{(1)}\cdots U_i^{(k)}={\prod }_{i=0}^{\infty }{U}_i^{(1)}=\cdots ={\prod }_{i=0}^{\infty }{U}_i^{(k)}$. In other words, there exists a shuffle of $k$-copies of $x$ which produces $x$. We are particularly interested in the case $k=2$, in which case we say $x$ is self-shuffling. This property of infinite words is shown to be an intrinsic property of the word and not of its language (set of factors). For instance, every aperiodic word contains a non self-shuffling word in its shift orbit closure. While the property of being self-shuffling is a relatively strong condition, many important words arising in the area of symbolic dynamics are verified to be self-shuffling. They include for instance the Thue-Morse word and all Sturmian words of intercept $0<\rho <1$ (while those of intercept $\rho =0$ are not self-shuffling). Our characterization of self-shuffling Sturmian words can be interpreted arithmetically in terms of a dynamical embedding and defines an arithmetic process we call the {\it stepping stone model}. One important feature of self-shuffling words stems from its morphic invariance, which provides a useful tool for showing that one word is not the morphic image of another. The notion of self-shuffling has other unexpected applications particularly in the area of substitutive dynamical systems. For example, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic.

References in corpus (2)

• Shuffling and Unshuffling
• Unshuffling a Square is NP-Hard

Cited by in corpus (2)

• Aperiodic pseudorandom number generators based on infinite words
• Abelian Combinatorics on Words: a Survey