1 Introduction
Give a set
$\mathbb{A}$
, let
$\mathbb{A}^{+}$
denote the free semigroup generated by
$\mathbb{A}$
consisting of all finite words
$u_{1}u_{2}\ldots u_{n}$
with
$u_{i}\in \mathbb{A}$
, and
$\mathbb{A}^{\mathbb{N}}$
the set of all infinite words
$x=x_{1}x_{2}x_{3}\ldots$
with
$x_{i}\in \mathbb{A}$
. We say
$x\in \mathbb{A}^{\mathbb{N}}$
is periodic if
$x=u^{\unicode[STIX]{x1D714}}=uuu\ldots$
for some
$u\in \mathbb{A}^{+}$
. The following question was independently posed by Brown in [Reference Brown3] and by the second author in [Reference Zamboni19]Footnote
1
:
Question 1. Let
$x\in \mathbb{A}^{\mathbb{N}}$
be non-periodic. Does there exist a finite colouring
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\,\rightarrow \,C$
relative to which
$x$
does not admit a
$\unicode[STIX]{x1D711}$
-monochromatic factorization, i.e. a factorization of the form
$x=u_{1}u_{2}u_{3}\ldots$
with
$\unicode[STIX]{x1D711}(u_{i})=\unicode[STIX]{x1D711}(u_{\!j})$
for all
$i,j\,\geqslant \,1$
?
The term finite here means that
$\text{Card}(C)<+\infty$
. A finite colouring
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow C$
is called a separating colouring for
$x$
(or a separating
$|C|$
-colouring for
$x$
) if for all factorizations
$x=u_{1}u_{2}u_{3}\ldots$
there exist
$i,j\geqslant 1$
such that
$\unicode[STIX]{x1D711}(u_{i})\neq \unicode[STIX]{x1D711}(u_{\!j})$
. While Brown originally stated it as a question, Question 1 has evolved into a conjecture which states that every non-periodic word admits a separating colouring. We begin by illustrating Question 1 with an example: consider the Thue–Morse infinite word
$$\begin{eqnarray}x=011010011001011010010\ldots ,\end{eqnarray}$$
where the
$n$
th term of
$x$
(starting from
$n=0$
) is defined as the sum modulo
$2$
of the digits in the binary expansion of
$n$
. The origins of this word go back to the beginning of the last century with the works of Thue [Reference Thue17, Reference Thue18] in which he proves amongst other things that
$x$
is overlap-free i.e.
$x$
contains no factor of the form
$uuu^{\prime }$
where
$u^{\prime }$
is a non-empty prefix of
$u$
.
Consider the
$3$
colouring
$\unicode[STIX]{x1D711}:\{0,1\}^{+}\rightarrow \{0,1,2\}$
defined by
$$\begin{eqnarray}\unicode[STIX]{x1D711}(u)=\left\{\begin{array}{@{}ll@{}}0\quad & \text{if }u\text{ is a prefix of }x\text{ ending with }0,\\ 1\quad & \text{if }u\text{ is a prefix of }x\text{ ending with }1,\\ 2\quad & \text{if }u\text{ is not a prefix of }x.\end{array}\right.\end{eqnarray}$$
We claim that no factorization of
$x$
is
$\unicode[STIX]{x1D711}$
-monochromatic. In fact, suppose to the contrary that
$x=u_{1}u_{2}u_{3}\ldots$
is a
$\unicode[STIX]{x1D711}$
-monochromatic factorization of
$x$
. Since
$u_{1}$
is a prefix of
$x$
, it follows that
$\unicode[STIX]{x1D711}(u_{1})\in \{0,1\}$
, i.e. there exists
$a\in \{0,1\}$
such that each
$u_{i}$
is a prefix of
$x$
terminating with
$a$
. Pick
$i\geqslant 2$
such that
$|u_{i}|\leqslant |u_{i+1}|$
. Then as each
$u_{i}$
is a prefix of
$x$
, it follows that
$u_{i}$
is a prefix of
$u_{i+1}$
and hence
$au_{i}u_{i}$
is a factor of
$x$
. Writing
$u_{i}=va$
(with
$v$
empty or in
$\{0,1\}^{+}$
), we have
$au_{i}u_{i}=avava$
which is an overlap, contradicting that
$x$
is overlap-free. This proves that there exists a separating
$3$
-colouring for the Thue–Morse word. Recently Avgustinovich and Parshina [Reference Avgustinovich and Parshina1] proved that it is possible to colour
$\{0,1\}^{+}$
using only
$2$
colours in such a way that no factorization of the Thue–Morse word is monochromatic.
Let us remark in the example above that since the Thue–Morse word
$x$
is not periodic, each proper suffix of
$x$
begins in some factor which is not a prefix of
$x$
. This means that each proper suffix
$x^{\prime }$
of
$x$
may be written as an infinite concatenation
$x^{\prime }=u_{1}u_{2}u_{3}\ldots$
with
$\unicode[STIX]{x1D711}(u_{i})=2$
for all
$i\geqslant 1$
, where
$\unicode[STIX]{x1D711}$
is the
$3$
-colouring of
$\{0,1\}^{+}$
defined above. Moreover, this monochromatic factorization of
$x^{\prime }$
has an even stronger monochromatic property: the set
$\{u_{n}:n\geqslant 1\}^{+}$
is also
$\unicode[STIX]{x1D711}$
-monochromatic (each element has
$\unicode[STIX]{x1D711}$
colour equal to
$2$
). This is because each element of
$\{u_{n}:n\geqslant 1\}$
is a non-prefix of
$x$
and hence the same is true of any concatenation formed by elements from this set. It turns out that a weaker version of this phenomenon is true in greater generality: given any
$x\in A^{\mathbb{N}}$
and any finite colouring
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow C$
, one can always find a suffix
$x^{\prime }$
of
$x$
which admits a factorization
$x^{\prime }=u_{1}u_{2}u_{3}\ldots$
where
$\unicode[STIX]{x1D711}(u_{i}\ldots u_{\!j})=\unicode[STIX]{x1D711}(u_{1})$
for all
$1\leqslant i\leqslant j$
. This fact may be obtained via a straightforward application of the infinite Ramsey theorem [Reference Ramsey13] (see [Reference Brown3, Reference de Luca and Zamboni10] or see [Reference Schützenberger15] for a proof by Schützenberger which does not use Ramsey’s theorem).
Thus Question 1 belongs to the class of Ramsey type problems in which one tries to show that some abstract form of Ramsey’s theorem does not hold in certain settings. For instance, the infinite version of Ramsey’s theorem [Reference Ramsey13] (for colouring of pairs) states that whenever the set
$\unicode[STIX]{x1D6F4}_{2}(\mathbb{N})$
of all
$2$
-element subsets of
$\mathbb{N}$
is finitely coloured, there exists an infinite set
$X\subseteq \mathbb{N}$
with
$\unicode[STIX]{x1D6F4}_{2}(X)$
monochromatic. Hence the same applies when
$\mathbb{N}$
is replaced by
$\mathbb{R}$
. On the other hand, Sierpiński [Reference Sierpiński16] showed that there exists a finite colouring of
$\unicode[STIX]{x1D6F4}_{2}(\mathbb{R})$
such that there does not exist an uncountable set
$X$
with
$\unicode[STIX]{x1D6F4}_{2}(X)$
monochromatic. In other words, Ramsey’s theorem does not extend to the uncountable setting in
$\mathbb{R}$
. Similarly, by a straightforward application of Ramsey’s theorem, one deduces that given any finite colouring of
$\mathbb{N}$
, there exists an infinite
$X\subseteq \mathbb{N}$
all of whose pairwise sums
$\{n+m:n,m\in X,n\neq m\}$
is monochromatic. Again it follows the same is true with
$\mathbb{N}$
replaced by
$\mathbb{R}$
. On the other hand, Hindman et al [Reference Hindman, Leader and Strauss6] recently exhibited (using the Continuum Hypothesis CH) the existence of a finite colouring of
$\mathbb{R}$
such that there does not exist an uncountable set with all its pairwise sums monochromatic. In other words, this additive formulation of Ramsey’s theorem also fails in the uncountable setting in
$\mathbb{R}$
. A related question in these sorts of problems concerns the least number of colours necessary to avoid the presence of monochromatic subsets of a certain kind. For instance Hindman [Reference Hindman5] showed that there exists a
$3$
-colouring of
$\mathbb{N}$
such that there does not exist an infinite subset
$X$
with
$X+X$
monochromatic, and it is an open question of Owings [Reference Owings12] whether the same result may be obtained with only
$2$
colours. Again, using CH and a few more colours (
$288$
to be precise), it is possible to extend Hindman’s result to the reals (see [Reference Hindman, Leader and Strauss6, Theorem 2.8]). But again it is not known whether the same result can be obtained with only
$2$
colours [Reference Leader8]. Thus a stronger version of Question 1 would read: Does every non-periodic word admit a separating
$2$
-colouring?
Various partial results in support of an affirmative answer to Question 1 were obtained in [Reference Bernardino, Pacheco and Silva2, Reference de Luca, Pribavkina and Zamboni9–Reference de Luca and Zamboni11, Reference Salo and Törmä14]. For instance in [Reference de Luca, Pribavkina and Zamboni9], it is shown that Question 1 admits an affirmative answer for all non-uniformly recurrent words and various classes of uniformly recurrent words including Sturmian words. In [Reference Salo and Törmä14], Salo and Törmä proved that for every aperiodic linearly recurrent word
$x\in \mathbb{A}^{\mathbb{N}}$
there exists a finite colouring of
$\mathbb{A}^{+}$
relative to which
$x$
does not admit a monochromatic factorization into factors of increasing lengths. And recently Bernardino et al [Reference Bernardino, Pacheco and Silva2] proved that Question 1 admits an affirmative answer for fixed points of strongly recognizable primitive substitutions. In addition to the fact that these partial results apply only to a restricted class of non-periodic words (e.g. Sturmian words or fixed points of certain primitive substitutions), in most cases the number of colours required to colour
$\mathbb{A}^{+}$
to avoid a monochromatic factorization of
$x$
is determined to be quite large. For instance in [Reference Salo and Törmä14], the authors proved that if
$x\in \mathbb{A}^{\mathbb{N}}$
is an aperiodic linearly recurrent word, then there exists a constant
$K\geqslant 2$
and a colouring
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow C$
with
$\text{Card}(C)=2+\sum _{i=0}^{K^{5}-1}2K^{i}(K+1)^{2i}$
, such that no factorization of
$x=u_{1}u_{2}u_{3}\ldots$
, verifying the additional constraint that
$|u_{i}|\leqslant |u_{i+1}|$
for each
$i\geqslant 1$
, is
$\unicode[STIX]{x1D711}$
-monochromatic. The constant
$K$
above is chosen such that for every factor
$u$
of
$x$
, every first return
$w$
to
$u$
satisfies
$|w|\leqslant K|u|$
(see for instance [Reference Durand, Host and Skau4]). A similar large bound depending on the recognizability index of a substitution is obtained in [Reference Bernardino, Pacheco and Silva2] in the context of fixed points of strongly recognizable substitutions. In contrast, it is shown in [Reference de Luca, Pribavkina and Zamboni9] that every Sturmian word admits a separating
$3$
-colouring.
In this paper we give a complete and optimal affirmative answer to Question 1 by showing that for every non-periodic word
$x=x_{1}x_{2}x_{3}\ldots \in \mathbb{A}^{\mathbb{N}}$
, there exists a
$2$
-colouring
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow \{0,1\}$
relative to which no factorization of
$x$
is
$\unicode[STIX]{x1D711}$
-monochromatic. Moreover, this is a characterization of periodicity of infinite words.
Theorem 1. Let
$x=x_{1}x_{2}x_{3}\ldots \in \mathbb{A}^{\mathbb{N}}$
be an infinite word. Then
$x$
is periodic if and only if for every
$2$
-colouring
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow \{0,1\}$
there exists a
$\unicode[STIX]{x1D711}$
-monochromatic factorization of
$x$
, i.e. a factorization
$x=u_{1}u_{2}u_{3}\ldots$
such that
$\unicode[STIX]{x1D711}(u_{i})=\unicode[STIX]{x1D711}(u_{\!j})$
for all
$i,j\geqslant 1$
.
Theorem 1 has several immediate consequences: for instance, fix a symbol
$a\in \mathbb{A}$
and suppose an infinite word
$x\in \mathbb{A}^{\mathbb{N}}$
admits a factorization
$x=u_{1}u_{2}u_{3}\ldots$
where each
$u_{i}$
is a prefix of
$x$
rich in the symbol
$a\in \mathbb{A}$
, meaning that for each
$i\geqslant 1$
and for each factor
$v$
of
$x$
with
$|v|=|u_{i}|$
we have
$f_{a}(u_{i})\geqslant f_{a}(v)$
, where
$f_{a}(u_{i})$
denotes the frequency of
$a$
in
$u_{i}$
. Then
$\{n\in \mathbb{N}:x_{n}=a\}$
is a finite union of arithmetic progressions. As another application of Theorem 1 we show that if
$u_{1},u_{2},u_{3},\ldots ,u_{2k+1}\in A^{+}$
(with
$k$
a positive integer), then any
$x\in \mathbb{A}^{\mathbb{N}}$
belonging to
$\{u_{1},u_{2}\}^{\mathbb{N}}\cap \{u_{2},u_{3}\}^{\mathbb{N}}\cap \cdots \cap \{u_{2k},u_{2k+1}\}^{\mathbb{N}}\cap \{u_{2k+1},u_{1}\}^{\mathbb{N}}$
is periodic.
Theorem 1 may be reformulated in the language of ultrafilters as follows: let
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
denote the Stone–Čech compactification of the discrete semigroup
$\mathbb{A}^{+}$
which we regard as the set of all ultrafilters on
$\mathbb{A}^{+}$
, identifying the points of
$\mathbb{A}^{+}$
with the principal ultrafilters. As is well known, the operation of concatenation on
$\mathbb{A}^{+}$
extends uniquely to
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
making
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
a compact right topological semigroup with
$\mathbb{A}^{+}$
contained in its topological centre (see for instance [Reference Hindman and Strauss7]). In particular by the Ellis–Numakura lemma,
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
contains an idempotent element i.e. an element
$p$
verifying
$p\cdot p=p$
. We show that an infinite word
$x=x_{1}x_{2}x_{3}\ldots \in \mathbb{A}^{\mathbb{N}}$
is periodic if and only if there exists
$p\in \unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
such that for each
$A\in p$
there exists a factorization
$x=u_{1}u_{2}u_{3}\ldots$
with each
$u_{i}\in A$
. Moreover
$p$
as above may be taken to be an idempotent element of
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
.
2 Proof of Theorem 1 and applications
Before embarking on the proof of Theorem 1, we introduce some notation which will be relevant in what follows. Let
$\mathbb{A}$
be a set (the alphabet). We do not assume that the cardinality of
$\mathbb{A}$
is finite. Let
$\mathbb{A}^{\ast }$
denote the set of all finite words
$u=u_{1}u_{2}\ldots u_{n}$
with
$u_{i}\in \mathbb{A}$
. We call
$n$
the length of
$u$
and denote it
$|u|$
. The empty word is denoted
$\unicode[STIX]{x1D700}$
and by convention
$|\unicode[STIX]{x1D700}|=0$
. We put
$\mathbb{A}^{+}=\mathbb{A}^{\ast }\setminus \{\unicode[STIX]{x1D700}\}$
. For
$u\in \mathbb{A}^{+}$
and
$a\in \mathbb{A}$
, we let
$|u|_{a}$
denote the number of occurrences of
$a$
in
$u$
. Let
$\mathbb{A}^{\mathbb{N}}$
denote the set of all right sided infinite words
$x=x_{1}x_{2}x_{3}\ldots$
with values in
$\mathbb{A}$
. More generally, for
$x\in \mathbb{A}^{\mathbb{N}}$
and
$A\subseteq \mathbb{A}^{+}$
, we write
$x\in A^{\mathbb{N}}$
if
$x=u_{1}u_{2}u_{3}\ldots$
with
$u_{i}\in A$
for all
$i\geqslant 1$
, that is in case
$x$
factors over the set
$A$
. We say
$x$
is periodic if
$x\in \{u\}^{\mathbb{N}}$
for some
$u\in \mathbb{A}^{+}$
.
Proof of Theorem 1.
First assume
$x=x_{0}x_{1}x_{2}\ldots \in \mathbb{A}^{\mathbb{N}}$
is periodic, i.e.
$x\in \{u\}^{\mathbb{N}}$
for some
$u\in \mathbb{A}^{+}$
. Then the factorization
$x=u_{1}u_{2}u_{3}\ldots$
with each
$u_{i}=u$
is
$\unicode[STIX]{x1D711}$
-monochromatic for any choice of
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow \{0,1\}$
. Next assume
$x$
is not periodic. We will define a
$2$
-colouring
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow \{0,1\}$
with the property that no factorization of
$x$
is
$\unicode[STIX]{x1D711}$
-monochromatic. Pick any total order on the set
$\mathbb{A}$
and let
$\prec$
denote the induced lexicographic order on
$\mathbb{A}^{+}$
and
$\mathbb{A}^{\mathbb{N}}$
. For
$u,v\in \mathbb{A}^{+}$
with
$|u|=|v|$
, we write
$u\preccurlyeq v$
if either
$u\prec v$
or
$u=v$
. For each
$n\geqslant 1$
, let
$P_{x}(n)$
denote the prefix of
$x$
of length
$n$
, and for each
$y\in \mathbb{A}^{\mathbb{N}}$
, let
$x\wedge y$
denote the longest common prefix of
$x$
and
$y$
. Define
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow \{0,1\}$
by the following rules.
If
$u$
is not a prefix of
$x$
, then set
$$\begin{eqnarray}\unicode[STIX]{x1D711}(u)=\left\{\begin{array}{@{}ll@{}}0\quad & \text{if }u\prec P_{x}(|u|),\\ 1\quad & \text{if }P_{x}(|u|)\prec u.\end{array}\right.\end{eqnarray}$$
If
$u$
is a prefix of
$x$
, say
$x=uy$
with
$y\in \mathbb{A}^{\mathbb{N}}$
, then set
$$\begin{eqnarray}\unicode[STIX]{x1D711}(u)=\left\{\begin{array}{@{}ll@{}}0\quad & \text{if }x\prec y,\\ 1\quad & \text{if }y\prec x.\end{array}\right.\end{eqnarray}$$
Since
$x$
is not periodic, for every proper suffix
$y$
of
$x$
we have either
$x\prec y$
or
$y\prec x$
, whence
$\unicode[STIX]{x1D711}$
is well defined. We observe that
$\unicode[STIX]{x1D711}$
has the following key property: if
$u$
is any non-empty prefix of
$x$
, say
$x=uy$
with
$y\in \mathbb{A}^{\mathbb{N}}$
, then there exists
$N\geqslant 0$
such that
$\unicode[STIX]{x1D711}(u)\neq \unicode[STIX]{x1D711}(v)$
for every prefix
$v$
of
$y$
with
$|v|>N$
. In fact, let
$N=|x\wedge y|$
. Then if
$v$
is a prefix of
$y$
with
$|v|>N$
, then
$v\neq P_{x}(|v|)$
. So if
$\unicode[STIX]{x1D711}(u)=0$
, then
$x\prec y$
and hence
$P_{x}(|v|)\prec v$
, whence
$\unicode[STIX]{x1D711}(v)=1$
. Similarly if
$\unicode[STIX]{x1D711}(u)=1$
, then
$y\prec x$
and hence
$v\prec P_{x}(|v|)$
, whence
$\unicode[STIX]{x1D711}(v)=0$
. The other key property of
$\unicode[STIX]{x1D711}$
is given by the following lemma.
Lemma 2. For all
$u\in \mathbb{A}^{+}$
, if
$u=u_{1}u_{2}\ldots u_{k}$
with
$u_{i}\in \mathbb{A}^{+}$
, then there exists
$1\leqslant i\leqslant k$
such that
$\unicode[STIX]{x1D711}(u_{i})=\unicode[STIX]{x1D711}(u)$
.
Proof. Fix
$a\in \{0,1\}$
. We will prove by induction on
$k$
that if
$u=u_{1}u_{2}\ldots u_{k}$
and
$\unicode[STIX]{x1D711}(u_{i})=a$
for all
$1\leqslant i\leqslant k$
, then
$\unicode[STIX]{x1D711}(u)=a$
. Without loss of generality we may assume
$a=0$
for otherwise we could replace
$\prec$
by the reverse order. For
$k=1$
the result is immediate. Next we consider the case
$k=2$
, i.e. we assume
$u=u_{1}u_{2}$
and
$\unicode[STIX]{x1D711}(u_{1})=\unicode[STIX]{x1D711}(u_{2})=0$
and we will show that
$\unicode[STIX]{x1D711}(u)=0$
. If
$u_{1}$
is not a prefix of
$x$
, then
$u_{1}\prec P_{x}(|u_{1}|)$
and hence
$u\prec P_{x}(|u|)$
, whence
$\unicode[STIX]{x1D711}(u)=0$
. Thus we may suppose that
$u_{1}$
is a prefix of
$x$
. Let
$u_{2}^{\prime }$
be such that
$u_{1}u_{2}^{\prime }$
is a prefix of
$x$
and
$|u_{2}|=|u_{2}^{\prime }|$
. If
$u_{2}\prec u_{2}^{\prime }$
, then
$u=u_{1}u_{2}\prec u_{1}u_{2}^{\prime }=P_{x}(|u|)$
, whence
$\unicode[STIX]{x1D711}(u)=0$
. Thus we may suppose that
$u_{2}^{\prime }\preccurlyeq u_{2}$
. Also since
$\unicode[STIX]{x1D711}(u_{1})=0$
it follows that
$P_{x}(|u_{2}^{\prime }|)\preccurlyeq u_{2}^{\prime }$
, whence
$P_{x}(|u_{2}^{\prime }|)\preccurlyeq u_{2}^{\prime }\preccurlyeq u_{2}$
. If any one of these two inequalities were strict, then
$P_{x}(|u_{2}|)\prec u_{2}$
which would imply that
$\unicode[STIX]{x1D711}(u_{2})=1$
, a contradiction. Thus we must have
$u_{2}=u_{2}^{\prime }=P_{x}(|u_{2}|)$
, i.e. both
$u$
and
$u_{2}$
are prefixes of
$x$
. Let
$x^{\prime }\in \mathbb{A}^{\mathbb{N}}$
be such that
$x=u_{1}x^{\prime }$
and let
$w\in \mathbb{A}^{+}$
denote the longest common prefix between
$x$
and
$x^{\prime }$
. Since
$\unicode[STIX]{x1D711}(u_{1})=0$
, there exist symbols
$a,b\in \mathbb{A}$
with
$a\prec b$
such that
$u_{1}wb$
and
$wa$
are each a prefix of
$x$
. Also since
$u_{2}$
is a prefix of both
$x$
and
$x^{\prime }$
we have
$|u_{2}|\leqslant |w|$
and hence we can write
$w=u_{2}v$
for some
$v\in \mathbb{A}^{\ast }$
. So each of
$u_{1}u_{2}vb=uvb$
and
$u_{2}va$
is a prefix of
$x$
. Finally since
$\unicode[STIX]{x1D711}(u_{2})=0$
, we have that
$P_{x}(|va|)\preccurlyeq va\prec vb$
, whence
$\unicode[STIX]{x1D711}(u)=0$
. This completes the case
$k=2$
. Now, let
$n>2$
and suppose the result of the lemma holds for all
$k<n$
, and suppose
$u=u_{1}u_{2}\ldots u_{n}$
with
$\unicode[STIX]{x1D711}(u_{i})=a$
for all
$1\leqslant i\leqslant n.$
Then by considering the factorization
$u=(u_{1}u_{2})u_{3}\ldots u_{n}$
of length
$n-1$
and the fact that
$\unicode[STIX]{x1D711}(u_{1}u_{2})=a$
(which comes from the case
$k=2$
), we deduce by induction hypothesis that
$\unicode[STIX]{x1D711}(u)=a$
as required.◻
To complete the proof of Theorem 1, we will show that no factorization of
$x$
is
$\unicode[STIX]{x1D711}$
-monochromatic. Let
$x=u_{1}u_{2}u_{3}\ldots$
with
$u_{i}\in \mathbb{A}^{+}$
. Pick
$N\geqslant 0$
such that
$\unicode[STIX]{x1D711}(v)\neq \unicode[STIX]{x1D711}(u_{1})$
for all prefixes
$v$
of
$u_{2}u_{3}\ldots$
with
$|v|>N$
. Pick
$k\geqslant 2$
such that
$|u_{2}\ldots u_{k}|>N$
. By the previous lemma, there exists
$2\leqslant i\leqslant k$
such that
$\unicode[STIX]{x1D711}(u_{i})=\unicode[STIX]{x1D711}(u_{2}\ldots u_{k})$
. Hence
$\unicode[STIX]{x1D711}(u_{i})=\unicode[STIX]{x1D711}(u_{2}\ldots u_{k})\neq \unicode[STIX]{x1D711}(u_{1})$
.◻
We end this section with some applications of Theorem 1 or its proof. An infinite word
$x\in \mathbb{A}^{\mathbb{N}}$
is called Lyndon if there exists an order on
$\mathbb{A}$
relative to which
$x$
is strictly smaller than each of its proper suffixes. Our first application is the following result originally proved in [Reference de Luca, Pribavkina and Zamboni9].
Corollary 3. A Lyndon word
$x\in \mathbb{A}^{\mathbb{N}}$
does not admit a prefixal factorization, i.e. a factorization of the form
$x=u_{1}u_{2}u_{3}\ldots$
where each
$u_{i}$
is a prefix of
$x$
.
Proof. Suppose to the contrary that
$x=u_{1}u_{2}u_{3}\ldots$
is a prefixal factorization of
$x$
. Let
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow \{0,1\}$
be the separating
$2$
-colouring for
$x$
defined in (1) and (2). Note that
$x$
being Lyndon is not-periodic. Since
$x$
is Lyndon we have that
$\unicode[STIX]{x1D711}(u_{i})=0$
for all
$i\geqslant 1$
, contradicting that
$\unicode[STIX]{x1D711}$
is a separating
$2$
-colouring for
$x$
.◻
Let
$x\in \mathbb{A}^{\mathbb{N}}$
and
$a\in \mathbb{A}$
. A factor
$u$
of
$x$
is said to be rich in
$a$
if
$|u|_{a}\geqslant |v|_{a}$
for all factors
$v$
of
$x$
with
$|v|=|u|$
. Theorem 6.7 in [Reference de Luca, Pribavkina and Zamboni9] states that a Sturmian word
$x\in \{0,1\}^{\mathbb{N}}$
does not admit a factorization of the form
$x=u_{1}u_{2}u_{3}\ldots$
where each
$u_{i}$
is a prefix of
$x$
rich in the same letter
$a\in \{0,1\}$
. The following generalizes this result to all binary non-periodic words.
Corollary 4. Let
$x\in \{0,1\}^{\mathbb{N}}$
and
$a\in \{0,1\}$
. Suppose
$x$
admits a prefixal factorization
$x=u_{1}u_{2}u_{3}\ldots$
with each
$u_{i}$
rich in
$a$
. Then
$x$
is periodic.
Proof. Suppose to the contrary that
$x$
is not periodic. Let
$\unicode[STIX]{x1D711}:\{0,1\}^{+}\rightarrow \{0,1\}$
be the separating
$2$
-colouring for
$x$
defined in (1) and (2) relative to the order on
$\{0,1\}$
where
$a$
is taken to be the least element. For each
$i\geqslant 1$
, writing
$x=u_{i}y_{i}$
with
$y_{i}\in \{0,1\}^{\mathbb{N}}$
, we claim that
$x\prec y_{i}$
. Otherwise if
$y_{i}\prec x$
, then we can write
$x=zbx^{\prime }=u_{i}zay^{\prime }$
for some
$z\in \{0,1\}^{\ast }$
,
$x^{\prime },y^{\prime }\in \{0,1\}^{\mathbb{N}}$
and where
$\{a,b\}=\{0,1\}$
. But then the factor
$u_{i}^{\prime }$
of length
$|u_{i}|$
immediately preceding the suffix
$y^{\prime }$
of
$x$
would contain one more occurrence of the symbol
$a$
than
$u_{i}$
, contradicting that
$u_{i}$
was rich in
$a$
. Having established that
$x\prec y_{i}$
, it follows that
$\unicode[STIX]{x1D711}(u_{i})=0$
for all
$i\geqslant 1$
contradicting that
$\unicode[STIX]{x1D711}$
is a separating
$2$
-colouring for
$x$
.◻
Corollary 5. Let
$\mathbb{A}$
be an arbitrary set,
$x\in \mathbb{A}^{\mathbb{N}}$
and
$a\in \mathbb{A}$
. Suppose
$x$
admits a prefixal factorization
$x=u_{1}u_{2}u_{3}\ldots$
with each
$u_{i}$
rich in
$a$
. Then
$\{n\in \mathbb{N}:x_{n}=a\}$
is a finite union of (infinite) arithmetic progressions.
Proof. Consider the morphism
$\unicode[STIX]{x1D719}:\mathbb{A}\rightarrow \{0,1\}$
given by
$\unicode[STIX]{x1D719}(a)=1$
and
$\unicode[STIX]{x1D719}(b)=0$
for all
$b\in \mathbb{A}\setminus \{a\}$
. Then applying
$\unicode[STIX]{x1D719}$
to the prefixal factorization
$x=u_{1}u_{2}u_{3}\ldots$
gives a prefixal factorization of
$\unicode[STIX]{x1D719}(x)$
in which each
$\unicode[STIX]{x1D719}(u_{i})$
is rich in
$1$
. Hence by Corollary 4 we have that
$\unicode[STIX]{x1D719}(x)$
is periodic and hence the set of occurrences of
$1$
in
$\unicode[STIX]{x1D719}(x)$
, which is equal to the set of occurrences of
$a$
in
$x$
, is a finite union of arithmetic progressions.◻
Corollary 6. Let
$x=x_{1}x_{2}x_{3}\ldots \in \mathbb{A}^{\mathbb{N}}$
and
$k$
be a positive integer. Let
$B\subseteq \mathbb{A}^{+}$
with
$\text{Card}(B)\geqslant 2k-1$
. Suppose that
$x\in A^{\mathbb{N}}$
for every
$k$
-element subset
$A$
of
$B$
. Then
$x$
is periodic.
Proof. Let us assume to the contrary that
$x$
is not periodic. By Theorem 1 there exists a
$2$
-colouring
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\,\rightarrow \,\{0,1\}$
relative to which no factorization of
$x$
is
$\unicode[STIX]{x1D711}$
-monochromatic. Let
$\unicode[STIX]{x1D6F4}_{k}(B)$
denote the set of all
$k$
-element subsets of
$B$
. By assumption
$x$
factors over each
$A\in \unicode[STIX]{x1D6F4}_{k}(B)$
. On the other hand, since
$\text{Card}(B)\geqslant 2k-1$
, it follows that there exists a
$\unicode[STIX]{x1D711}$
-monochromatic subset
$A\in \unicode[STIX]{x1D6F4}_{k}(B)$
. This gives rise to a
$\unicode[STIX]{x1D711}$
-monochromatic factorization of
$x$
, a contradiction.◻
Corollary 7. Let
$x=x_{1}x_{2}x_{3}\ldots \in \mathbb{A}^{\mathbb{N}}$
and
$k$
be a positive integer. Let
$u_{1},u_{2},u_{3},\ldots ,u_{2k+1}\in A^{+}$
and suppose
$x\in \{u_{1},u_{2}\}^{\mathbb{N}}\cap \{u_{2},u_{3}\}^{\mathbb{N}}\cap \cdots \cap \{u_{2k},u_{2k+1}\}^{\mathbb{N}}\cap \{u_{2k+1},u_{1}\}^{\mathbb{N}}$
. Then
$x$
is periodic.
Proof. Suppose to the contrary that
$x$
is not periodic. Pick any separating
$2$
-colouring
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow \{0,1\}$
for
$x$
. Then
$\unicode[STIX]{x1D711}(1)=\unicode[STIX]{x1D711}(2i+1)$
for each
$1\leqslant i\leqslant k$
. Thus
$x\notin \{u_{2k+1},u_{1}\}^{\mathbb{N}}$
, a contradiction.◻
3 A reformulation of Theorem 1 in the language of ultrafilters
In this section we give a reformulation of Theorem 1 in the language of ultrafilters. Given a set
$S$
, let
$\unicode[STIX]{x1D6FD}S$
denote the Stone–Čech compactification of
$S$
(relative to the discrete topology on
$S$
) which we regard as the collection of all ultrafilters
$p$
on
$S$
. Theorem 1 may be reformulated in the language of ultrafilters as follows.
Theorem 8. Let
$x=x_{1}x_{2}x_{3}\ldots \in \mathbb{A}^{\mathbb{N}}$
be an infinite word. Then
$x$
is periodic if and only if there exists
$p\in \unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
such that for each
$A\in p$
there exists a factorization
$x=u_{1}u_{2}u_{3}\ldots$
with each
$u_{i}\in A$
.
Proof. Suppose
$x$
is periodic, i.e.
$x\in \{u\}^{\mathbb{N}}$
for some
$u\in \mathbb{A}^{+}.$
Then clearly
$x$
factors over each set
$A$
belonging to the principal ultrafilter
$e(u)=\{A\subseteq \mathbb{A}^{+}:u\in A\}$
. Conversely, suppose there exists
$p\in \unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
such that for each
$A\in p$
there exists a factorization
$x=u_{1}u_{2}u_{3}\ldots$
with each
$u_{i}\in A$
. Let
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow \{0,1\}$
be any
$2$
-colouring of
$\mathbb{A}^{+}$
and consider the partition
$\mathbb{A}^{+}=\unicode[STIX]{x1D711}^{-1}(0)\cup \unicode[STIX]{x1D711}^{-1}(1)$
. Since
$\mathbb{A}^{+}\in p$
, it follows that
$\unicode[STIX]{x1D711}^{-1}(a)\in p$
for some
$a\in \{0,1\}$
. Thus there exists a factorization
$x=u_{1}u_{2}u_{3}\ldots$
with each
$u_{i}\in \unicode[STIX]{x1D711}^{-1}(a)$
. In other words,
$x$
admits a
$\unicode[STIX]{x1D711}$
-monochromatic factorization. By Theorem 1 we conclude that
$x$
is periodic. ◻
Remark 9. It can be shown that Theorem 8 is actually an equivalent reformulation of Theorem 1. More precisely, given an infinite word
$x=x_{1}x_{2}x_{3}\ldots \in \mathbb{A}^{\mathbb{N}}$
, the following statements are easily seen to be equivalent:
-
(a) there exists
$p\in \unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
such that for each
$A\in p$
we can write
$x=u_{1}u_{2}u_{3}\ldots$
with each
$u_{i}\in A$
; -
(b) for each finite colouring
$\unicode[STIX]{x1D711}:\mathbb{A}^{+}\rightarrow C$
there exists a
$\unicode[STIX]{x1D711}$
-monochromatic factorization of
$x$
.
The operation of concatenation on
$\mathbb{A}^{+}$
extends uniquely to
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
making
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
a compact right topological semigroup with
$\mathbb{A}^{+}$
contained in its topological centre (see for instance [Reference Hindman and Strauss7]). The operation
$\cdot$
on
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
is defined as follows: for
$p,q\in \unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
$$\begin{eqnarray}p\cdot q=\{A\subseteq \mathbb{A}^{+}:\{u\in \mathbb{A}^{+}:u^{-1}A\in q\}\in p\},\end{eqnarray}$$
where
$u^{-1}A=\{v\in \mathbb{A}^{+}:uv\in A\}$
. As a consequence of the Ellis–Numakura lemma,
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
contains an idempotent element, i.e. an element
$p$
verifying
$p\cdot p=p$
. We now show that
$p$
in Theorem 8 may be taken to be an idempotent element of
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
. For
$x=x_{1}x_{2}x_{3}\ldots \in \mathbb{A}^{\mathbb{N}}$
, we set
$$\begin{eqnarray}\mathscr{F}(x)=\{A\subseteq \mathbb{A}^{+}:x\in A^{\mathbb{N}}\}\end{eqnarray}$$
and
$$\begin{eqnarray}{\mathcal{U}}(x)=\{p\in \unicode[STIX]{x1D6FD}\mathbb{A}^{+}:p\subseteq \mathscr{F}(x)\}.\end{eqnarray}$$
Thus
$p\in {\mathcal{U}}(x)$
if and only if
$x$
factors over every
$A\subseteq \mathbb{A}^{+}$
belonging to
$p$
.
Theorem 10. Let
$x=x_{0}x_{1}x_{2}\ldots \in \mathbb{A}^{\mathbb{N}}$
. Then the following are equivalent:
-
(i)
$x$
is periodic; -
(ii)
${\mathcal{U}}(x)$
is a closed sub-semigroup of
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+};$
-
(iii)
${\mathcal{U}}(x)$
contains an idempotent element; -
(iv) and the set
$\text{Pref}(x)$
consisting of all prefixes of
$x$
is an IP-set.
Proof. We first note that for each infinite word
$x$
, the set
${\mathcal{U}}(x)$
is a closed subset of
$\unicode[STIX]{x1D6FD}\mathbb{A}^{+}$
. In fact, suppose
$p\in \unicode[STIX]{x1D6FD}\mathbb{A}^{+}\setminus {\mathcal{U}}(x)$
, then there exists
$A\in p$
with
$A\notin \mathscr{F}(x)$
. Then
$\overline{A}$
is an open neighbourhood of
$p$
and any
$q\in \overline{A}$
contains the set
$A$
and hence is not in
${\mathcal{U}}(x)$
. To see that (i)
$\Longrightarrow$
(ii), suppose that
$x$
is periodic. By Theorem 8 we have
${\mathcal{U}}(x)\neq \emptyset$
. It remains to show that
$p\cdot q\in {\mathcal{U}}(x)$
whenever
$p,q\in {\mathcal{U}}(x)$
. Pick the shortest
$u\in \mathbb{A}^{+}$
such that
$x\in \{u\}^{\mathbb{N}}$
and set
${\mathcal{A}}=\{u^{j}:j\in \mathbb{N}\}$
. Then
$p\in {\mathcal{U}}(x)$
if and only if
${\mathcal{A}}\in p$
. Let
$A\in p\cdot q$
with
$p,q\in {\mathcal{U}}(x)$
. Then by (3) we have
$\{s\in \mathbb{A}^{+}:s^{-1}A\in q\}\in p$
. Since
$p\in {\mathcal{U}}(x)$
it follows that
$\{s\in \mathbb{A}^{+}:s^{-1}A\in q\}\cap {\mathcal{A}}\neq \emptyset$
. Pick
$n\in \mathbb{N}$
such that
$u^{n}\in \{s\in \mathbb{A}^{+}:s^{-1}A\in q\}$
. Then
$\{t\in \mathbb{A}^{+}:u^{n}t\in A\}\in q$
and since
$q\in {\mathcal{U}}(x)$
it follows that there exists
$m\in \mathbb{N}$
with
$u^{m}\in \{t\in \mathbb{A}^{+}:u^{n}t\in A\}$
. In other words
$u^{n+m}\in A$
and hence
$x$
factors over
$A$
. Thus
$p\cdot q\in {\mathcal{U}}(x)$
. The implication (ii)
$\Longrightarrow$
(iii) follows from the Ellis–Numakura lemma. To see (iii)
$\Longrightarrow$
(iv) pick an idempotent element
$p\in {\mathcal{U}}(x)$
. We note that
$\text{Pref}(x)$
belongs to every
$q\in {\mathcal{U}}(x)$
. In fact, suppose that
$\text{Pref}(x)\notin q$
, for some
$q\in {\mathcal{U}}(x)$
. Then
$\mathbb{A}^{+}\setminus \text{Pref}(x)\in q$
which implies that
$x$
factors over
$\mathbb{A}^{+}\setminus \text{Pref}(x)$
. But this is a contradiction since in any factorization of
$x$
, the first term occurring in the factorization belongs to
$\text{Pref}(x)$
. Thus in particular
$\text{Pref}(x)\in p$
. Since
$p$
is an idempotent, it follows that
$\text{Pref}(x)$
is an IP-set. Finally, to see that (iv)
$\Longrightarrow$
(i) assume that
$\text{Pref}(x)$
is an IP-set. Then
$\text{Pref}(x)$
contains
$FP\left(\langle s_{n}\rangle _{n\in \mathbb{N}}\right)$
for some infinite sequence
$\langle s_{n}\rangle _{n\in \mathbb{N}}$
of prefixes of
$x$
. This means that for each
$n\geqslant 2$
, both
$s_{1}s_{2}\ldots s_{n}$
and
$s_{2}\ldots s_{n}$
are prefixes of
$x$
. Thus
$x=s_{1}x$
which implies that
$x$
is periodic.◻
Acknowledgement
We are extremely grateful to the anonymous referee for suggestions on improving the exposition of this paper.
