The Least Self-Shuffle of the Thue-Morse Sequence

James D. Currie^{1} Department of Mathematics & Statistics University of Winnipeg Winnipeg, MB R3B 2E9 Canada

                     j.currie@uwinnipeg.ca

Abstract

We show that the self-shuffle of Thue-Morse given by Charlier et al. is optimal/canonical in the sense that among self-shuffles of Thue-Morse, it has the lexicographically least directive sequence starting with 1.

1 Introduction

Henshall et al. [3] initiated the topic of self-shuffles of finite words. They considered, in particular, closure properties of languages under self-shuffles, proving several results as well as posing open problems.

No non-empty finite word can be equal to one of its self-shuffles, but for infinite words, the question of whether a word can be written as a self-shuffle is interesting. Charlier et al. [1] exhibited a self-shuffle of the Thue-Morse word. The Thue-Morse word is the fixed point of a morphism, so that we can immediately get other shuffles; the image of any selfshuffle under the morphism gives a different self-shuffle. Endrullis and Hendriks [2] proved that there are in fact other self-shuffles; in particular, they showed that a shuffle distinct from that of Charlier et al. is optimal — it switches back and forth between shuffled copies as quickly as possible. The Thue-Morse word thus allows at least two distinct families of self-shuffles.

1The author is supported by an NSERC Discovery grant.

In this note, we show that the self-shuffle of Thue-Morse given by Charlier et al. is optimal/canonical in a different sense: among self-shuffles of Thue-Morse, it has the lexicographically least directive sequence starting with 1.

2 Notation

We follow Lothaire [4] as a standard notational reference for combinatorics on words. Thus |x| is the length of word x, |x|_{0} the number of 0’s in x, etc. If x is a non-empty word, let x′ denote the word obtained by deleting the last letter of x. Thus, (12341234)′ = 1234123, for example. Let u, v, w be finite words, and let d be a word over {0, 1} such that |w| = |d| = |u| + |v|. We define recursively what it means for w to be the shuffle of u and v directed by d, written w = u ⊕_{d} v:

1. If d = ϵ, then w = u ⊕_{d} v

2. If the last letter of d is 0 then w = u ⊕_{d} v if

(a) w′ = u′ ⊕_{d′} v

(b) The last letter of w is the same as the last letter of u

3. If the last letter of d is 1 then w = u ⊕_{d} v if

(a) w′ = u ⊕_{d′} v′

(b) The last letter of w is the same as the last letter of v

In other words, each letter of w is read from either u or v, and d determines whether we read it from u (0) or from v (1). We call d the directive word of the shuffle.

By ω-word we mean a 1-sided infinite word. For ω-words u, v, w, d, we extend the definition above and write w = u ⊕_{d} v if there are arbitrarily long prefixes û, v̂, ŵ, d̂ of u, v, w, d, respectively, such that û ⊕d̂ v̂ = ŵ.

Remark 1. Suppose that d_{0} ∈ {0, 1}^{∗} is a finite prefix of d and write d = d_{0}d_{1}.

• Let w_{0} be the prefix of w of length |d_{0}| and write w = w_{0}w_{1}.

• Let u_{0} be the prefix of u of length |d_{0}|_{0} and write u = u_{0}u_{1}.

• Let v_{0} be the prefix of v of length |d_{0}|_{1} and write v = v_{0}v_{1}.

Then

w = u ⊕_{d} v ⇔ (w_{0} = u_{0} ⊕_{d_{0}} v_{0} and w_{1} = u_{1} ⊕_{d_{1}} v_{1})

We say that an ω-word w allows a non-trivial self-shuffle if we can write w = w ⊕_{d} w for some non-constant ω-word d. Evidently, for any ω-word w, w = w ⊕_{0^{ω}} w = w ⊕_{1^{ω}} w; we call these the trivial self-shuffles of w. Write x ⪯ y (resp., x ≺ y) to say that word x is no greater than (resp., less than) y in the natural lexicographic order where 0 precedes 1. Because we have the trivial self-shuffles, the lexicographically least ω-word d such that w = w ⊕_{d} w is just d = 0^{ω}. Seeking the lexicographically least directive sequence starting with 1 is a reasonable attempt to force non-trivial shuffling. Thus, if ω-word w allows a non-trivial self-shuffle, a natural question is

What is the lexicographically least ω-word d with prefix 1 such that w = w⊕_{d}w?

3 Lexicographically least shuffles

In this section, u, v, w will be arbitrary but fixed effectively given ω-words.

Lemma 2. Let a word d_{0} ∈ {0, 1}^{∗} be specified. Let

D = {d ∈ {0, 1}^{ω} : w = u ⊕_{d} v}.

If D ∩ d_{0}{0, 1}^{ω} is non-empty, then it has a lexicographically least element.

Proof. For a positive integer n, suppose that d_{n−1} has been defined and D ∩ d_{n−1}{0, 1}^{ω} is non-empty. It follows that at least one of D ∩ d_{n−1}0{0, 1}^{ω} and D ∩ d_{n−1}1{0, 1}^{ω} is nonempty. We can thus define an infinite sequence of words {d_{n}}_{n=0}^{∞}, each d_{n} an extension of d_{n−1}, by

d_{n} = \begin{cases}d_{n−1}0, & if D ∩ d_{n−1}0\{0, 1\}^{ω} is non-empty; \\ d_{n−1}1, & otherwise. \end{cases}

Let d̄ = lim_{n→∞} d_{n}. We claim that d̄ is the lexicographically least element of D ∩ d_{0}{0, 1}^{ω}. Each finite prefix d_{n} of d̄ has been chosen to be the prefix of a word of D, so that w = u⊕d̄v. On the other hand, if for some d̂ ∈ D ∩ d_{0}{0, 1}^{ω}, d̂ ≺ d̄, consider the shortest prefix p of d̂ which is not a prefix of d̄. For some positive n, p = d_{n−1}0, while d_{n} = d_{n−1}1. However, this implies that D ∩ d_{n−1}0{0, 1}^{ω} is empty, and d̂ ∉ D ∩ d_{0}{0, 1}^{ω}. This is a contradiction.

Remark 3. Suppose that

w = u ⊕_{d} v

has solutions d ∈ 1{0, 1}^{∗}. For a fixed prefix w_{0} of w, we can effectively determine the lexicographically least element d_{0} of 1{0, 1}^{∗} such that there exist prefixes u_{0} and v_{0} of u and v, respectively, such that

w_{0} = u_{0} ⊕_{d_{0}} v_{0}.  (1)

There are only 2^{|w_{0}|−1} candidates for d_{0}. We can check for each candidate d_{0}, and the corresponding prefixes u_{0}, v_{0} of u, v, with lengths |d_{0}|_{0}, |d_{0}|_{1}, whether (1) is satisfied. Note that the lengths of prefixes u_{0}, v_{0} are always at most |w_{0}|.

Lemma 4. Suppose that d is the lexicographically least element of 1{0, 1}^{ω} such that

w = u ⊕_{d} v.

Let w_{0} be a fixed non-empty prefix of w. Let d_{0} be the lexicographically least element of 1{0, 1}^{∗} such that there exist prefixes u_{0} and v_{0} of u and v, respectively, such that

w_{0} = u_{0} ⊕_{d_{0}} v_{0}.

Suppose d_{0} ∈ {0, 1}^{∗}1; write w = w′_{0}W, u = u_{0}U, v = v′_{0}V (so that w′_{0} = u_{0} ⊕_{d′_{0}} v′_{0}). Suppose that there exists an element δ ∈ 1{0, 1}^{ω} such that

W = U ⊕_{δ} V.

Then

d = d′_{0}Δ,

where Δ is the lexicographically least such δ. In particular, d_{0} is a prefix of d.

Proof. Since w′_{0} = u_{0} ⊕_{d′_{0}} v′_{0} and W = U ⊕_{δ} V, by Remark 1, we have

w = u ⊕_{d′_{0}Δ} v.

Let d be the length |w_{0}| prefix of d. By the minimality of d, d ⪯ d′_{0}1.

Since

w = u ⊕_{d} v,

it follows from Remark 1 that

w_{0} = û_{0} ⊕_{d} v̂_{0},

where û_{0} is the length |d|_{0} prefix of u, and v̂_{0} is the length |d|_{1} prefix of v. By the lexicographic minimality of d_{0}, d′_{0}1 = d_{0} ⪯ d, so that d_{0} = d.

Therefore, write d = d′_{0}Δ̂, where Δ̂ ∈ 1{0, 1}^{ω}. By Remark 1,

W = U ⊕Δ̂ V.

By the minimality of Δ, Δ ⪯ Δ̂. However, by the minimality of d, d′_{0}Δ̂ = d ⪯ d′_{0}Δ. Thus Δ = Δ̂, so that d = d′_{0}Δ.

Corollary 5. Let d be the lexicographically least element of 1{0, 1}^{ω} such that

w = u ⊕_{d} v.

Suppose that for each positive integer i there are finite words W_{i}, U_{i} and V_{i}, and ω-words w_{i}, u_{i} and v_{i}, where • w_{1} = w, u_{1} = u and v_{1} = v,

• W_{i}, U_{i}, V_{i} are prefixes of length 2 or more of w_{i}, u_{i}, v_{i}, respectively,

• w_{i+1} = (W′_{i})^{−1}w_{i}, u_{i+1} = (U′_{i})^{−1}u_{i}, v_{i+1} = (V′_{i})^{−1}v_{i}.

so that, for each i,

w_{i} = ∏_{j=i}^{∞} W′_{j}

u_{i} = ∏_{j=i}^{∞} U′_{j}

v_{i} = ∏_{j=i}^{∞} V′_{j}.

For each i, let D_{i} be the lexicographically least word starting with 1 such that

W_{i} = û_{i} ⊕_{D_{i}} v̂_{i}

for some prefixes û_{i} of u_{i} and v̂_{i} of v_{i}. Suppose that, for each i, D_{i} ends in a 1, û_{i} = U_{i} and v̂_{i} = V_{i}. Then

d = ∏_{i=1}^{∞} D′_{i}.

Proof. This follows from the previous lemma by induction.

4 The Thue-Morse word

Consider the binary version of the Thue-Morse word (\underline{A001285}), namely, t = μ^{ω}(0) where μ(0) = 01, μ(1) = 10. Thus

t = 0110100110010110 ⋯

The length 2 factors of the Thue-Morse word are 00, 01, 10, 11. If t[j..j + 1] = ab, a, b ∈ {0, 1}, then

t[8j..8j + 15] = μ^{3}(ab)

and

t[16j..16j + 31] = μ^{4}(ab).

It follows that

⟨t[8j + 1..8j + 8], t[8j + 5..8j + 13], t[16j + 6..16j + 22]⟩

takes on one of 4 possible values:

If t[j..j + 1] = 00, then

t[8j..8j + 15] = 0\underline{1101\overline{0010}}\overline{11010}01
t[16j16j + 31] = 011010\underline{01100101100110100}110010110

so that

⟨t[8j + 1..8j + 8], t[8j + 5..8j + 13], t[16j + 6..16j + 22]⟩
= ⟨11010010, 001011010, 01100101100110100⟩.

Arguing similarly in the other three cases, we find that

⟨t[8j + 1..8j + 8], t[8j + 5..8j + 13], t[16j + 6..16j + 22]⟩ ∈ ⟨U_{i}, V_{i}, W_{i}⟩

where the values of the U_{i}, V_{i}, W_{i} are as follows:

\begin{matrix}i & U_{i} & V_{i} & W_{i} \\ 1 & 11010010 & 001011010 & 01100101100110100 \\ 2 & 11010011 & 001100101 & 01100101101001011 \\ 3 & 00101100 & 110011010 & 10011010010110100 \\ 4 & 00101101 & 110100101 & 10011010011001011 \end{matrix}

For each non-negative integer j, let i_{j} ∈ {1, 2, 3, 4} be the unique value such that

t[8j + 1..8j + 8] = U_{i_{j}}.

Let D_{1} = 10001110100011101, D_{2} = 10001001100111101.

One checks that

W_{1} = U_{1} ⊕_{D_{1}} V_{1}
W_{2} = U_{2} ⊕_{D_{2}} V_{2}
W_{3} = U_{3} ⊕_{D_{2}} V_{3}
W_{4} = U_{4} ⊕_{D_{1}} V_{4}.

For a given value of j, consider the ω-words U = t[8j + 1..∞], V = t[8j + 5..∞], W = t[16j + 6..∞]. Let the length 17 prefix of W be W_{0}. Thus W_{0} ∈ {W_{1}, W_{2}, W_{3}, W_{4}}. As per Remark 3, one can determine the lexicographically least D_{0} with prefix 1 such that W_{0} = U_{0} ⊕_{D_{0}} V_{0} for some prefixes U_{0} of U and V_{0} of V; we need only consider prefixes of U and V of lengths at most 17. It is therefore a finite computation to show that whenever W_{0} ∈ {W_{1}, W_{4}}, then D_{0} = D_{1} and when W_{0} ∈ {W_{2}, W_{3}}, then D_{0} = D_{2}. For convenience, define δ : {1, 2, 3, 4} → {1, 2} by δ(1) = δ(4) = 1, δ(2) = δ(3) = 2.

Let T_{0} = 0110100, the length 7 prefix of the Thue-Morse word t. A short computation (feasible by hand) shows that the lexicographically least word Δ_{0} with prefix 1 such that T_{0} = T_{1} ⊕_{Δ_{0}} T_{2} for prefixes T_{1}, T_{2} of t is Δ_{0} = 1111101.

We remark that each of D_{1}, D_{2} and Δ_{0} ends in a 1.

Theorem 6. The lexicographically least word d with prefix 1 such that t = t ⊕_{d} t is

d = 111110 ∏_{j=0}^{∞}(D_{δ(i_{j})})′.

Proof. Note that

t = 011010 ∏_{j=0}^{∞} W′_{i_{j}} = 0 ∏_{j=0}^{∞} U′_{i_{j}} = 01101 ∏_{j=0}^{∞} V′_{i_{j}}.

The result thus follows from Corollary 5.

Remark 7. One verifies that this is the shuffle given by Charlier et al. in [1].

5 Acknowledgments

Thanks to the anonymous and thorough referee, and to Narad Rampersad, for their comments.

References

[1] E. Charlier, T. Kamae, S. Puzynina, and L. Q. Zamboni, Self-shuffling words, J. Combin. Theory Ser. A 128 (2014), 1–40.

[2] J. Endrullis and D. Hendriks, The optimal self-shuffle of the Thue-Morse word, preprint

   available at http://www.cs.vu.nl/~diem/publication/pdf/self-shuffle.pdf,

2014.

[3] D. Henshall, N. Rampersad, and J. Shallit, Shuffling and unshuffling, Bull. Europ. Assoc. Theoret. Comput. Sci. No. 107 (June 2012), 131–142.

[4] M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002.

[5] Axel Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana 1 (1912), 1–67. Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 413–478.

2010 Mathematics Subject Classification: Primary 68R15. Keywords: Word shuffling, Thue-Morse word, lexicographical order.

(Concerned with sequence \underline{A001285}).

Received September 12 2014; revised versions received October 11 2014; October 12 2014. Published in Journal of Integer Sequences, November 2 2014.

Return to Journal of Integer Sequences home page.