% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.55}{22(1)}{2015}

\usepackage{mathrsfs}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\newcommand{\eps}{\varepsilon} % the empty word
\newcommand{\N}{\mathbb{N}}
\newcommand{\shf}{\shuffle}
\newcommand{\pref}{\leq_p}
\newcommand{\suff}{\leq_s}


\title{\bf On shuffling of infinite square-free words} %Infinite square-free self-shuffling words}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Mike M\"uller\thanks{Supported in part by the DFG under grant 582014.}\\
\small Institut f\"ur Informatik\\[-0.8ex]
\small Christian-Albrechts-Universit{\"a}t zu Kiel, Germany\\
%\small Christian-Albrechts-Universit{\"a}t zu Kiel\\[-0.8ex]
%\small Kiel, Germany\\
\small\tt mimu@informatik.uni-kiel.de\\
\and Svetlana Puzynina\thanks{Supported by the LABEX MILYON
(ANR-10-LABX-0070) of Universit\'{e} de Lyon, within the program
``Investissements d'Avenir'' (ANR-11-IDEX-0007) operated by the
French National Research Agency (ANR).}  \\
\small LIP, ENS de Lyon\\[-0.8ex]
\small Universit\'e de Lyon, France\\
\small and Sobolev Institute of Mathematics \\[-0.8ex]
\small Novosibirsk, Russia\\[-0.8ex]
 \small\tt s.puzynina@gmail.com  \and
Micha\"el Rao\\
\small LIP, CNRS, ENS de Lyon\\[-0.8ex]
\small Universit\'e
de Lyon, France\\
\small\tt michael.rao@ens-lyon.fr }

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Nov 12, 2014}{Feb 14, 2015}{Mar 6, 2015}\\
\small Mathematics Subject Classifications: 68R15}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
In this paper we answer two recent questions from %\cite{CKPZ} 
Charlier et al.~(2014) and Harju (2013) %% CSG
 about self-shuffling words. An infinite word $w$ is
called self-shuffling, if $w=\prod_{i=0}^\infty
U_iV_i=\prod_{i=0}^\infty U_i=\prod_{i=0}^\infty V_i$ for some
finite words $U_i$, $V_i$. Harju recently asked
whether square-free self-shuffling words exist. We answer this
question affirmatively. Besides that, we build an infinite word
such that no word in its shift orbit closure is self-shuffling,
answering positively a question of Charlier et al.


  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} infinite words, shuffling,
 square-free words, shift orbit closure, self-shuffling words
\end{abstract}

\section{Introduction}
A self-shuffling word, a notion which was recently introduced by
Charlier et al. \cite{CKPZ}, is an infinite word that can be
reproduced by shuffling it with itself. More formally, given
two infinite words $x, y \in \Sigma^\omega$ over a finite alphabet
$\Sigma,$ we define ${\mathscr{S}}(x,y)\subseteq \Sigma^\omega$ to
be the collection of all infinite words $z$ for which there exists
a factorization
\[
z=\prod_{i=0}^\infty U_i V_i
\]
with each $U_i, V_i \in \Sigma^*$ and with $x=\prod_{i=0}^\infty
U_i$, $y=\prod_{i=0}^\infty V_i$. An infinite word $w\in
\Sigma^\omega$ is \emph{self-shuffling} if
$w\in{\mathscr{S}}(w,w)$. Various well-known words, e.g., the
Thue-Morse word or the Fibonacci word, were shown to be
self-shuffling.

Harju \cite{Harju} studied shuffles of both finite and infinite
square-free words, i.e., words that have no factor of the form
$uu$ for some non-empty factor $u$. More results on square-free
shuffles were obtained independently by Harju and M\"uller
\cite{HaMU13}, and Currie and Saari \cite{CuSa14}. However, the
question about the existence of an infinite square-free
self-shuffling word, posed in \cite{Harju}, remained open. We give
a positive answer to this question in Sections 2~and~3.

The \emph{shift orbit closure} $S_w$ of an infinite word $w$ can
be defined, e.g., as the set of infinite words  whose sets of
factors are contained in the set of factors of $w$. In \cite{CKPZ}
it has been proved that each word has a non-self-shuffling word
in its shift orbit closure, and the following question has been
asked: Does there exist a word for which no element of its shift
orbit closure is self-shuffling (Question 7.2)? In Section 4 we
provide a positive answer to the question.
%The \emph{ternary Thue-Morse} word is fixed point of the morphism
%$h(0) =012, h(1)= 02, h(2) =1$. It is well known that this word is
%square-free. We show that no word in the shift orbit closure of
%this word is self-shuffling.
More generally, we show the existence of a word such that for any
three words $x,y,z$ in its shift orbit closure, if $x$ is a
shuffle of $y$ and $z$, then the three words are pairwise
different. On the other hand, we show that for any infinite word
there exist three different words $x,y,z$ in its shift orbit closure such
that $x \in \mathscr{S} (y,z)$ (see Proposition~\ref{prop_xyz}).

Apart from the usual concepts in combinatorics on words, which can
be found for instance in the book of Lothaire \cite{Lothaire}, we
make use of the following notations: For every $k \geq 1$, we
denote the alphabet $\{0, 1, \ldots, k-1\}$ by $\Sigma_k$. For a
word $w = uvz$ we say that $u$ is a \emph{prefix} of $w$, $v$ is a
\emph{factor} of $w$, and $z$ is a \emph{suffix} of $w$. We denote
these prefix- and suffix relations by $u \pref w$ and $v \suff w$,
respectively.
By $w[i,j]$ we denote the factor of $w$ starting at position $i$ and
ending after position $j$.
Note that we start numbering the positions with $0$.

A \emph{prefix code} is a set of words with the property that none
of its elements is a prefix of another element. Similarly, a
\emph{suffix code} is a set of words where no element is a suffix
of another one. A \emph{bifix code} is a set that is both a prefix
code and a suffix code. %A word $w$ is \emph{square-free}, if it
%has no factor of the form $uu$, where $u$ is a non-empty finite
%word.
A morphism $h$ is \emph{square-free} if for all square-free words
$w$, the image $h(w)$ is square-free.

\section{A square-free self-shuffling word on four letters}
Let $g : \Sigma_4^* \rightarrow \Sigma_4^*$ be the morphism
defined as follows:
\begin{align*}
    g(0) &= 0121, \\
    g(1) &= 032, \\
    g(2) &= 013, \\
    g(3) &= 0302.
\end{align*}

We will show that the fixed point $w = g^\omega(0)$ is square-free
and self-shuffling. Note that $g$ is not a square-free morphism,
that is, it does not preserve square-freeness, as $g(23) =
0130302$ contains the square $3030$.


\begin{lemma}\label{no_3u1u3}
    The word $w = g^\omega(0)$ contains
    %the factor $23$ nor
    no factor of the form $3u1u3$ for any $u \in \Sigma_4^*$.
\end{lemma}
\begin{proof}
    %The fact that $w$ has no occurrence of the factor $23$ is easily observed from the definition of $g$.
    We assume that there exists a factor of the form $3u1u3$ in $w$, for some word $u \in \Sigma_4^*$.
    From the definition of $g$, we observe that $u$ can not be empty.
    Furthermore, we see that every $3$ in $w$ is preceded by either $0$ or $1$.
    If $1 \suff u$, then we had an occurrence of the factor $11$ in $w$, which is not possible by the definition of $g$, hence $0 \suff u$.
    Now, every $3$ is followed by either $0$ or $2$ in $w$ and $01$ is followed by either $2$ or $3$.
    Since both $3u$ and $01u$ are factors of $w$, we must have $2 \pref u$.
    This means that the factor $012$ appears at the center of $u1u$, which can only be followed by $1$ in $w$, thus $21 \pref u$.
    However, this results in the factor $321$ as a prefix of $3u1u3$, which does not appear in $w$, as seen from the definition of $g$.
\end{proof}

\begin{lemma}
    The word $w = g^\omega(0)$ is square-free.
\end{lemma}
\begin{proof}
    We first observe that $\{g(0), g(1), g(2), g(3)\}$ is a bifix code.
    Furthermore, we can verify that there are no squares $uu$ with $|u| \leq 3$ in $w$.
    Let us assume now, that the square $uu$ appears in $w$ and that $u$ is the shortest word with this property.
    If $u = 02u'$, then $u' = u''03$ must hold, since $02$ appears only as a factor of $g(3)$, and thus $uu$ is a suffix of the factor $g(3)u''g(3)u''03$ in $w$.
    As $w = g(w)$, also the shorter square $3g^{-1}(u'')3g^{-1}(u'')$ appears in $w$, a contradiction.
    The same desubstitution principle also leads to occurrences of shorter squares in $w$ if $u = xu'$ and $x \in \{01, 03, 10, 12, 13, 21, 30, 32\}$.

    If $u = 2u'$ then either $03 \suff u$ or $030 \suff u$ or $01 \suff u$, by the definition of $g$.
    In the last case, that is when $01 \suff u$, we must have $21 \pref u$, which is covered by the previous paragraph.
    If $u' = u''030$, then $uu$ is followed by $2$ in $w$ and we can desubstitute to obtain the shorter square $g^{-1}(u'')3g^{-1}(u'')3$ in $w$.
    If $u = 2u'$ and $u' = u''03$, and $uu$ is preceded by $03$ or followed by $2$ in $w$, we can desubstitute to $1g^{-1}(u'')1g^{-1}(u'')$ or $g^{-1}(u'')1g^{-1}(u'')1$, respectively.
    Therefore, assume that $u = 2u''03$ and as we already ruled out the case when $21 \pref u$, we can assume that $uu$ is preceded by $030$ and followed by $02$ in $w$.
    This however means that we can desubstitute to get an occurrence of the factor $3g^{-1}(u'')1g^{-1}(u'')3$ in $w$, a contradiction to Lemma \ref{no_3u1u3}.
\end{proof}

We now show that $w = g^\omega(0)$ can be written as
$w=\prod_{i=0}^\infty U_iV_i=\prod_{i=0}^\infty
U_i=\prod_{i=0}^\infty V_i$ with $U_i,V_i \in \Sigma_4^*$.

\begin{lemma}
    The word $w = g^\omega(0)$ is self-shuffling.
\end{lemma}
\begin{proof}
    We use the notation $x=v^{-1}u$ meaning that $u=v
    x$ for finite words $x, u, v$. We are going to show that the
    self-shuffle is given by the following:

    \small\begin{align*}& U_0=g^2(0),& &\hskip-9pt U_1=0,& &\hskip-10pt \dots,\hskip-8pt & &U_{6i+2}=g^i(0^{-1}g(0)0),&
    &\hskip-6pt U_{6i+3}=g^{i}(0^{-1}g(3)0),\\& & & & & &
    &U_{6i+4}=g^{i}(0^{-1}g(201)0),& & \hskip-6pt U_{6i+5}=g^{i}(30),
    \\& & & & & &
    &U_{6i+6}=g^{i}(2g(03)),& &
    \hskip-6pt U_{6i+7}=g^{i+1}(20), \\
    & V_0=g(0)03,& &\hskip-9pt V_1=2g(2)0,& &\hskip-10pt \dots,
    \hskip-8pt & &V_{6i+2}=g^{i}(0^{-1}g(1)0),& & \hskip-6pt
    V_{6i+3}=g^{i}(0^{-1}g(03)0),\\& & & & & & &V_{6i+4}=g^{i}(1),& &
    \hskip-6pt V_{6i+5}=g^{i}(3),\\& & & & & & &V_{6i+6}=g^{i+1}(0),&
    & \hskip-6pt V_{6i+7}=g^{i+1}(0^{-1}g(2)0).
    \end{align*}\normalsize
    Now we verify  that $$w=\prod_{i=0}^\infty U_i V_i
    =\prod_{i=0}^\infty U_i =\prod_{i=0}^\infty V_i,$$ from which it
    follows that $w$ is self-shuffling. It suffices to show that each
    of the above products is fixed by $g$. Indeed, straightforward
    computations show that

    $$\prod_{i=0}^\infty U_i = g^2(0) g^2(121) g^3(121) \cdots \, , $$

    which is fixed by $g$:

    \begin{align*} g\left(\prod_{i=0}^\infty U_i\right) &= g\left(g^2(0) g^2(121) g^3(121) \cdots \right) = g^3(0) g^3(121) g^4(121) \cdots \\
                                             &= g^2(0121) g^3(121) g^4 (121) \cdots = g^2(0) g^2(121) g^3(121) \cdots =\prod_{i=0}^\infty U_i, \end{align*}
    hence $\prod_{i=0}^\infty U_i$ is fixed by $g$ and thus
    $w=\prod_{i=0}^\infty U_i$. In a similar way we show that
    $w=\prod_{i=0}^\infty V_i=\prod_{i=0}^\infty U_i V_i$.
\end{proof}

\section{Square-free self-shuffling words on three letters}

We remark that we can immediately produce a square-free
self-shuffling word over $\Sigma_3$ from $g^\omega(0)$: Charlier
et al. \cite{CKPZ} noticed that the property of being
self-shuffling is preserved by the application of a morphism.
Furthermore, Brandenburg \cite{Brandenburg} showed that the
morphism $f : \Sigma_4^* \rightarrow \Sigma_3^*$, defined by
\begin{align*}
    f(0) &= 010201202101210212, \\
    f(1) &= 010201202102010212, \\
    f(2) &= 010201202120121012, \\
    f(3) &= 010201210201021012,
\end{align*}
is square-free. Therefore, the word $f(g^\omega(0))$ is a ternary
square-free self-shuffling word, from which we can produce a
multitude of others by applying square-free morphisms from
$\Sigma_3^*$ to $\Sigma_3^*$.

\section{A word with non self-shuffling shift orbit closure}
In this section we provide a positive answer to the question from
\cite{CKPZ} whether there exists a word for which no element of
its shift orbit closure is self-shuffling.

The \emph{Hall word} $\mathcal{H}=012021012102\cdots$ is defined
as the fixed point of the morphism $h(0) =012, h(1)= 02, h(2) =1$.
Sometimes it is referred to as a \emph{ternary Thue-Morse} word.
It is well known that this word is square-free. We show that no
word in the shift orbit closure $S_\mathcal{H}$ of the Hall word
is self-shuffling. More generally, we show that if  $x$ is a
shuffle of $y$ and $z$ for $x,y,z\in S_\mathcal{H}$, then they are
pairwise different.

\begin{proposition}\label{prop_xyy} There are no words $x, y$ in the shift orbit
closure of the Hall word such that $x \in \mathscr{S}
(y,y)$.\end{proposition}

\begin{proof}
Suppose the converse, i.e., there exist words $x, y\in
S_\mathcal{H}$ such that

$$ x = \prod_{i=0}^{\infty} U_i V_i, \qquad y= \prod_{i=0}^{\infty} U_i = \prod_{i=0}^{\infty} V_i.$$

Define the set $X$ of infinite words as follows:

$$X=\{x \in S_\mathcal{H} \, \mid \, x \in \mathscr{S} (y,y) \mbox{ for some } y\in S_\mathcal{H} \}.$$
In other words, $X$ consists of words in $S_\mathcal{H}$ which can
be introduced as a shuffle of some word $y$ in $S_\mathcal{H}$
with itself.
%Now we define the order in $X$
%relatively to the lexicographically minimal word on the alphabet
%of the lengths of blocks $|U_0|,|V_0|,|U_1|,|V_1|...$ (probably
%infinite alphabet). Now for $x\in S$, choose $y$ with the smallest
%$|U_0|,|V_0|,|U_1|,|V_1|...$ from the corresponding shuffle. We
%say that $x \leq \tilde{x}$ if $|U_0|,|V_0|,|U_1|,|V_1|...$ is
%lexicographically smaller than
%$|\tilde{U}_0|,|\tilde{V}_0|,|\tilde{U}_1|,|\tilde{V}_1|...$. Now
%let $x$ be a minimal word in $X$ with respect to this order and
%$y$ be the word giving this minimal factorization. We remark that
%$x$ itself is not necessarily unique, in principle there could be
%several words with the same corresponding word
%$|U_0|,|V_0|,|U_1|,|V_1|...$.
Now suppose, for the sake of contradiction, that $X$ is non empty, and
consider $x\in X$ with the first block $U_0$ of the smallest
possible positive length. We remark that such $x$ and
corresponding $y$ are not necessarily unique.

We can suppose without loss of generality that $y$ starts with $0$
or $10$. Otherwise, we exchange $0$ and $2$, consider the
morphism $0 \mapsto 1, 1 \mapsto 20, 2\mapsto 210$, and the
argument is symmetric.

It is not hard to see from the properties of the morphism $h$ that
removing every occurrence of $1$ from $x$ and $y$ results in
$(02)^\omega$. Hence the blocks in the factorizations of $y$ after
removal of $1$ are of the form $(02)^i$ for some integer $i$. Thus
the first letter of each block $U_i$ and $V_i$ that is different
from $1$ is $0$, and the last letter different from $1$ is $2$.

Then, $U_i$ and $V_i$ are images by the morphism $h$ of factors of
the fixed point of $h$. Therefore, there are words $x', y'\in
S_{\mathcal{H}}$ such that $x=h(x'), y=h(y'), U_i=h(U'_i),
V_i=h(V'_i),$ and $x'= \prod_{i=0}^\infty U'_i V'_i$, $y' = \prod_{i=0}^\infty U'_i =
\prod_{i=0}^\infty V'_i $.

Notice that the first block $U_0$ cannot be equal to $1$. Indeed,
otherwise $x$ starts with $11$, which is impossible, since $11$ is
not a factor of the fixed point of $h$.

Clearly, taking the preimage decreases the lengths of blocks in
the factorization (except for those equal to $1$), and since
$U_0\neq 1$, the length of the first block in the preimage is
smaller, i.e., $|U_0'|<|U_0|$. This is a contradiction with the minimality of
$|U_0|$.
\end{proof}

\begin{corollary} There are no self-shuffling words in the shift orbit
closure of $\mathcal{H}$. \end{corollary}

With a similar argument we can prove the following:

\begin{proposition}\label{prop_xxy} There are no words $x, y$ in the shift orbit
closure of $\mathcal{H}$ such that $x \in \mathscr{S} (x,y)$.
\end{proposition}

\begin{proof} First we introduce a notation $x\in \mathscr{S}_2
(y,z)$, meaning that there exists a shuffle starting with the word
$z$ (i.e., $U_0=\varepsilon$, $V_0 \neq \varepsilon$). Next, $x \in
\mathscr{S} (x,y)$ implies that there exists $z$ in the same shift
orbit closure such that $z \in \mathscr{S}_2 (z,y)$. Indeed, one
can remove the prefix $U_0$ of $x$ to get $z$, i.e., $z=(U_0)^{-1}x$, and
keep all the other blocks $U_i$, $V_i$ in the shuffle product.

Define the set $Z$ of infinite words as follows:

$$Z=\{z \in S_{\mathcal{H}} \, \mid \, z \in \mathscr{S}_2 (z,y) \mbox{ for some } y\in S_\mathcal{H} \}.$$
In other words, $Z$ consists of words in $S_\mathcal{H}$ which can
be introduced as a shuffle of some word $y$ in $S_\mathcal{H}$
with $z$ starting with the block $V_0$. Now consider $z\in Z$ with
the first block $V_0$ of the smallest possible length. We remark
that such $z$ and a corresponding $y$ are not necessarily unique.

As in the proof of Proposition \ref{prop_xyy}, the shuffle cannot
start with a block of length $1$. Again, if we remove every occurrence of $1$ in
$y$ (and in $z$), we get $(02)^\omega$ or $(20)^\omega$; moreover,
since $V_0$ contains letters different from $1$, the first letter different from $1$ is the same in $y$ and $z$.
So, without loss of generality we assume that
both $y$ and $z$ without $1$ are $(02)^\omega$, and the blocks
$U_i$ and $V_i$  without $1$ are integer powers of $02$. Then,
$U_i$ and $V_i$ are images by the morphism $h$ of factors of
$\mathcal{H}$. Therefore, there are words $z', y'\in
S_\mathcal{H}$ such that $z=h(z'), y=h(y'), U_i=h(U'_i),
V_i=h(V'_i),$ and $z'= \prod_{i=0}^\infty (U'_i V'_i) = \prod_{i=0}^\infty V'_i$, $y' = \prod_{i=0}^\infty
U'_i $ (i.e., $z'\in Z$).

As in the proof of Proposition \ref{prop_xyy}, since $V_0\neq 1$,
the length of the first block in the preimage is smaller, i.e.,
$|V_0'|<|V_0|$. This is again a contradiction with the minimality of $|V_0|$.
\end{proof}

So, we proved that if there are three words $x, y, z$ in the shift
orbit closure of the fixed point of $h$ such that $x \in
\mathscr{S} (y,z)$, then they should be pairwise distinct. Now we
are going to prove that for any infinite word there exist three
different words in its shift orbit closure such
that $x \in \mathscr{S} (y,z)$.

An infinite word $x$ is called \emph{recurrent}, if each of its
prefixes occurs infinitely many times in~it.

\begin{proposition}\label{prop_xyz} Let $x$ be a recurrent infinite word. Then there exist two words $y, z$ in the shift orbit
closure of $x$ such that $x \in \mathscr{S}
(y,z)$.\end{proposition}
\begin{proof} We build the shuffle inductively.

Start from any prefix $U_0$ of $x$. Since $x$ is recurrent, each
of its prefixes occurs infinitely many times in it. Find another
occurrence of $U_0$ in $x$ and denote its position by $i_1$. Put
$V_0= x[|U_0|, i_1+|U_0|-1]$.

%Find an occurrence of $V_0$ at some position $j_1>i_1$, put $U_1=
%x[|U_0|+|V_0|, \dots, j_1-1]$.

At step $k$, suppose that the shuffle of the prefix of $x$ is
built:
\begin{align*}
x[0, \Sigma_{l=0}^{k-1}(|U_l|+|V_l|)-1]&=\prod_{l=0}^{k-1} U_l V_l, \\
y[0, \Sigma_{l=0}^{k-1}|U_l|-1]&=\prod_{l=0}^{k-1} U_l, \\
z[0,\Sigma_{l=0}^{k-1} |V_l|-1]&=\prod_{l=0}^{k-1} V_l,
\end{align*}
such that
%$U_0 \cdots U_{k-1}$
$\prod_{l=0}^{k-1} U_l$ is the suffix of $x[0,
\Sigma_{l=0}^{k-1}(|U_l|+|V_l|)-1]=\prod_{i=0}^{k-1} U_l V_l$
starting at position $i_{k-1}$, and
%$V_0 \cdots V_{k-1}$
$\prod_{l=0}^{k-1} V_l$ is the suffix of $x[0,
\Sigma_{l=0}^{k-1}(|U_l|+|V_l|)-1]=\prod_{i=0}^{k-1} U_l V_l$
starting at position $j_{k-1}$.

Find another occurrence of $\prod_{l=0}^{k-1} V_l$ %$V_0 \cdots V_{k-1}$
in $x$ at some
position $j_k > j_{k-1}$. We can do it since $x$ is recurrent. Put
$U_k= x[\Sigma_{l=0}^{k-1}(|U_l|+|V_l|), %\dots,
j_k-1+\Sigma_{l=0}^{k-1}|V_l|]$. We note that
%$U_0 \cdots U_k$
$\prod_{l=0}^{k} U_l$ is a
factor of $x$ by the construction; more precisely, it occurs at
position $i_{k-1}$.

Find an occurrence of $\prod_{l=0}^{k} U_l$ at some position
$i_k>i_{k-1}$, put $V_k= x[\Sigma_{l=0}^{k-1}(|U_l|+|V_l|) +
|U_k|, i_k-1+\Sigma_{l=0}^{k}|U_l|]$. As above, $\prod_{l=0}^{k} V_l$
is a factor of $x$ by the construction since it occurs at
position $j_{k-1}$. Moreover, both $\prod_{l=0}^{k} U_l$  and $\prod_{l=0}^{k} V_l$
are suffixes of $x[0,
\Sigma_{l=0}^{k}(|U_l|+|V_l|)-1]=\prod_{i=0}^{k} U_l V_l$.

Continuing this line of reasoning, we build the required
factorization.
\end{proof}


Since each infinite word contains a recurrent (actually, even a
uniformly recurrent) word in its shift orbit closure, we obtain
the following corollary:
\begin{corollary}\label{col:xyz} Each infinite word $w$ contains words $x, y, z$ in its shift orbit
closure such that $x \in \mathscr{S} (y,z)$.
\end{corollary}

The following example shows that the recurrence condition in
Proposition \ref{prop_xyz} cannot be omitted:


\begin{example} Consider the word $3\mathcal{H} = 3012021\cdots$ which
is obtained from $\mathcal{H}$ by adding a letter $3$ in the
beginning. Then the shift orbit closure of $3\mathcal{H}$ consists
of the shift orbit closure of $\mathcal{H}$ and the word
$3\mathcal{H}$ itself. Assuming $3\mathcal{H}$ is a shuffle of two
words in its shift orbit closure, one of them is $3\mathcal{H}$
(there are no other $3$'s) and the other one is something in the
shift orbit closure of $\mathcal{H}$, we let $y$ denote this other
word. Clearly, the shuffle starts with $3$, and cutting the first
letter $3$, we get $\mathcal{H}\in \mathscr{S}(\mathcal{H},y)$, a
contradiction with Proposition~\ref{prop_xxy}.
\end{example}

There also exist examples where each letter occurs infinitely many
times:

\begin{example} The following word:
$$x=012001120001112\cdots0^k1^k2\cdots$$ does not have
two words $y,z$ in its shift orbit closure such that $x \in
\mathscr{S} (y,z)$. The idea of the proof is that the shift orbit
closure consists of words of the following form: $1^*20^{\omega}$,
$0^*1^{\omega}$, $x$ itself and all their right shifts. Shuffling
any two words of those types, it is not hard to see that there
exists a prefix of the shuffle which contains too many or too few
occurrences of some letter compare to the prefix of $x$. We leave
the details of the proof to the reader.
\end{example}

By Corollary~\ref{col:xyz}, there are $x,y,z$ in the shift
orbit closure of $\mathcal{H}$ such that $x\in \mathscr{S}(y,z)$.
To conclude this section, we give an explicit construction of two
words in the shift orbit closure of $\mathcal{H}$ which can be
shuffled to give $\mathcal{H}$. We remark though that this
construction gives a shuffle different from the one given by
Corollary~\ref{col:xyz}. Let:
$$h:\left\{
\begin{array}{lll}
0&\mapsto&012\\
1&\mapsto&02\\
2&\mapsto&1\\
\end{array}\right. \text{ and ~ }
h':\left\{
\begin{array}{lll}
0&\mapsto&210\\
1&\mapsto&20\\
2&\mapsto&1.\\
\end{array}\right.$$

By definition, the shift orbit closure of the Hall word is closed
under $h$. Moreover this shift orbit closure is also closed under
$h'$. One of the ways to see this is the following. It is well
known that the Thue-Morse word, which is a fixed point of the
morphism $0\mapsto 01$, $1\mapsto 10$ starting with $0$, is a
morphic image of $\mathcal{H}$ under a morphism $0\mapsto 011$,
$1\mapsto 01$, $2\mapsto 0$. Therefore, the set of factors of the
Hall word is closed under reversal: if $v\in F(\mathcal{H})$, then
$v^R\in F(\mathcal{H})$ (here for a word $v=v_1\cdots v_n$ its
reversal $v^R$ is given by $v^R=v_n\cdots v_1$). Now by induction
we prove that for each word $v$ one has $h'(v)= (h(v^R))^R$ (it is
enough to prove this equality for letters and for the
concatenation of two words). This implies that the shift orbit
closure of the Hall word is closed $h'$.
%, since the factors of the Hall word are closed under the
%morphism $0\to 2, 1\to 1, 2\to 0$.

The morphisms $h$ and $h'$ satisfy:

\small
$$
h'\circ h:\left\{
\begin{array}{lll}
0&\mapsto&210201\\
1&\mapsto&2101\\
2&\mapsto&20\\
\end{array}\right.
h\circ h':\left\{
\begin{array}{lll}
0&\mapsto&102012\\
1&\mapsto&1012\\
2&\mapsto&02\\
\end{array}\right.
$$
$$
h^2:\left\{
\begin{array}{lll}
0&\mapsto&012021\\
1&\mapsto&0121\\
2&\mapsto&02\\
\end{array}\right.
h'^2:\left\{
\begin{array}{lll}
0&\mapsto&120210\\
1&\mapsto&1210\\
2&\mapsto&20.\\
\end{array}\right.$$
\normalsize Note that if $w$ is an infinite word, then $2 (h\circ
h')(w) = (h'\circ h)(w)$ and $0h'^2(w)=h^2(w)$.

\def\prodi{\prod_{i=0}^\infty}

%\begin{claim}\end{claim}\begin{proof}\end{proof}


\begin{theorem}
$h^\omega(0) \in \mathscr{S}
(h^2((h'^2)^\omega(1)),h'^3(h^\omega(0)))$.
\end{theorem}
\begin{proof}
Let
$$U_0=01, \, U_1=h'(0), \, U_2=h'(1), \, V_0=h'(1),$$
and for every $i\ge 0$,
$$U_{i+3} = h'^2(h^i(1)) \text{ and } V_{i+1}=h'^2(h^i(1)).$$
Let furthermore
$$u=\prod_{i=0}^\infty U_i, \, v=\prod_{i=0}^\infty V_i, \text{ and } w=\prod_{i=0}^\infty U_i V_i \, .$$
%Let $v=\prod_{i=0}^\infty V_i = 20 \prod_{i=0}^\infty h'^2(h^i(1)) = h'^2 (\prod h^i(2))$.
We show that $w= h^\omega(0)$, $u=h^2((h'^2)^\omega(1))$ and
$v=h'^3(h^\omega(0))$.

Note that $2h(h'(h^\omega(0)))= h'(h^\omega(0))$, thus
$h'(h^\omega(0))=\prodi h^i(2)$. Then we have $$v=20
\prod_{i=0}^\infty h'^2(h^i(1)) = h'^2 \left (\prod_{i=0}^\infty
h^i(2)\right )= h'^3(h^\omega(0)).$$ Moreover,
\begin{align*}
    u  &= 01 210 20 \prod_{i=0}^\infty h'^2(h^i(1))= 01210h'^2\left (\prodi h^i(2)\right ) \\
       &= 01210h'^3\left(h^\omega(0)\right)= 01h'(0h'^2(h^\omega(0)))=
01h'(h^\omega(0))=0 h'(2h^\omega(0)).
\end{align*}
Since
$h'^2(2h^\omega(0)) = 20 h'^2(h^\omega(0))= 2 h^\omega(0)$,
the word $2h^\omega(0)$ is the fixed point
$(h'^2)^\omega(2)$ of $h'^2$, and then $h'(2h^\omega(0))$ is the fixed point
$(h'^2)^\omega(1)$. Thus $u  = 0 (h'^2)^\omega(1) =
h^2((h'^2)^\omega(1))$. Finally:
$$w=0120210121020\prod_{i=0}^\infty h'^2(h^i(021))
    =012 021 h(021) h^2\left (\prod_{i=0}^\infty h^i(021) \right)
=     012 \prod_{i=0}^\infty h^i(021).$$

Applying the morphism $h$ to the second expression for $w$, we get
$$h(w)=     012021 h\left (\prod_{i=0}^\infty h^i(021) \right ) = 012
\prod_{i=0}^\infty h^i(021).$$


%\begin{tabular}{rl}
%$h(w)$&$=h(0120210121020\prod_{i=0}^\infty h'^2(h^i(021)))$\\
%    &$=0120210121020 1202102012101 2 (h\circ h'^2)(\prod_{i=0}^\infty h^i(021))$\\
%&$=     0120210121020 h'(2101202) (h' \circ h \circ h')(\prod_{i=0}^\infty h^i(021))$\\
%&$=     0120210121020 h'(2101202 (h \circ h')(\prod_{i=0}^\infty h^i(021)))$\\
%&$=     0120210121020 h'(210120  (g \circ h)(\prod_{i=0}^\infty h^i(021)))$\\
%&$=     0120210121020 h'^2(021 h(\prod_{i=0}^\infty h^i(021)))$\\
%&$=     0120210121020 h'^2(\prod_{i=0}^\infty h^i(021)) = w.$\\
%\end{tabular}

Thus $w= h^\omega(0)$ since $h$ is injective.
\end{proof}


\section{Conclusions}
We showed that infinite square-free self-shuffling words exist.
The natural question that arises now is whether we can find
infinite self-shuffling words subject to even stronger
avoidability constraints: For this we recall the notion of
\emph{repetition threshold} $RT(k)$, which is defined as the least
real number such that an infinite word over $\Sigma_k$
exists, that does not contain repetitions of exponent greater than
$RT(k)$.
Due to the collective effort of many researchers%~\cite{Thue12,Dejean,Pansiot,Ollagnier,Mohammad-Noori,Carpi,CurrieR09,CurrieR092,
~(see \cite{CurrieR11,Rao11} and references therein), the
repetition threshold for all alphabet sizes is known and
characterized as follows:
$$RT(k) =
  \begin{cases}
   \frac{7}{4}       & \text{if } k=3 \\
   \frac{7}{5} & \text{if } k=4 \\
   \frac{k}{k-1} & \text{else}.
  \end{cases}
$$
A word $w \in \Sigma_k^\omega$ without factors of exponent greater
than $RT(k)$ is called a \emph{Dejean word}. Charlier et al.
showed that the Thue-Morse word, which is a binary Dejean word, is
self-shuffling \cite{CKPZ}.

\begin{question} Do there exist self-shuffling Dejean words over
non-binary alphabets? \end{question}


\bibliographystyle{abbrv}
%\bibliography{bib-small}
\begin{thebibliography}{10}
\bibitem{Brandenburg}F.-J. Brandenburg. Uniformly Growing $k$th Power-Free
Homomorphisms. \emph{Theor. Comput. Sci.} 23: 69--82, 1983.

\bibitem{CKPZ} E. Charlier, T. Kamae, S. Puzynina, L. Q. Zamboni. Infinite self-shuffling words.
\emph{J. Comb. Theory, Ser. A,} 128: 1--40, 2014.

\bibitem{CurrieR11} J. Currie, N. Rampersad. A proof of Dejean's conjecture.
\emph{Math. Comput.} 80(274): 1063--1070, 2011.

\bibitem{CuSa14} J. Currie, K. Saari. Square-free Words with Square-free
Self-shuffles. \emph{Electr. J. Comb.,} 21(1): \#P1.9 (2014).

\bibitem{Harju} T. Harju. A Note on Square-Free Shuffles of Words. \emph{LNCS} 8079 (WORDS 2013):
154--160.

\bibitem{HaMU13} T. Harju, M. M\"{u}ller. Square-Free Shuffles of Words. CoRR
abs/1309.2137 (2013)

\bibitem{Lothaire}
M. Lothaire. \emph{Algebraic combinatorics on words.} Cambridge
University Press, 2002.

\bibitem{Rao11} M. Rao. Last cases of Dejean's conjecture. \emph{Theor. Comput. Sci.}
412(27): 3010--3018, 2011.

\end{thebibliography}
\end{document}
