Monochromatic colorings

Caïus Wojcik and Luca Zamboni recently posted a paper on the arXiv solving an interesting problem in combinatorics on words.

http://arxiv.org/abs/1608.03519
Monochromatic factorisations of words and periodicity.
Caïus Wojcik, Luca Q. Zamboni.

I had recently learned of the problem through another paper by Zamboni and a collaborator,

MR3425965
Aldo de Luca, Luca Q. Zamboni
On prefixal factorizations of words.
European J. Combin. 52 (2016), part A, 59–73.

It is a nice result and I think it may be enjoyable to work through the argument here. Everything that follows is either straightforward, standard, or comes from these papers.

1. The problem

To make the post reasonably self-contained, I begin by recalling some conventions, not all of which we need here.

By an alphabet we simply mean a set A, whose elements we refer to as letters. A word w is a sequence w:N\to A of letters from A where N is a (not necessarily non-empty, not necessarily proper) initial segment of \mathbb N. If we denote w_i=w(i) for all i\in N, it is customary to write the word simply as

w_0w_1\dots

and we will follow the convention. The empty word is typically denoted by \Lambda or \varepsilon. By A^* we denote the collection of all finite words from A, and A^+=A^*\setminus \{\varepsilon\}. By |x| we denote the length of the word x (that is, the size of the domain of the corresponding function).

We define concatenation of words in the obvious way, and denote by x_0x_1 the word resulting from concatenating the words x_0 and x_1, where x_0\in A^*. This operation is associative, and we extend it as well to infinite concatenations.

If a word w can be written as the concatenation of words x_0,x_1,\dots,

w=x_0x_1\dots,

we refer to the right-hand side as a factorization of w. If w=xy and x is non-empty, we say that x is a prefix of w. Similarly, if y is non-empty, it is a suffix of w. By x^n for n\in\mathbb N we denote the word resulting form concatenating n copies of x. Similarly, x^{\mathbb N} is the result of concatenating infinitely many copies.

By a coloring we mean here a function c:A^+\to C where C is a finite set of “colors”.

Apparently the problem I want to discuss was first considered by T.C. Brown around 2006 and, independently, by Zamboni around 2010. It is a question about monochromatic factorizations of infinite words. To motivate it, let me begin with a cute observation.

Fact. Suppose w=w_0w_1\dots is an infinite word, and c is a coloring. There is then a factorization 

w=px_0x_1\dots 

where all the x_i\in A^+ have the same color.

Proof. The proof is a straightforward application of Ramsey’s theorem: Assign to c the coloring of the set [\mathbb N]^2 of 2-sized subsets of \mathbb N given by d(\{i,j\})=c(w_iw_{i+1}\dots w_{j-1}) whenever i<j. Ramsey’s theorem ensures that there is an infinite set I=\{n_0<n_1<\dots\} such that all w_{n_i}w_{n_i+1}\dots w_{n_j-1} with i<j have the same color. We can then take p=w_0\dots w_{n_0-1} and x_i=w_{n_i}\dots w_{n_{i+1}-1} for all i. \Box

In the fact above, the word w was arbitrary, and we obtained a monochromatic factorization of a suffix of w. However, without additional assumptions, it is not possible to improve this to a monochromatic factorization of w itself. For example, consider the word w=01^{\mathbb N} and the coloring

c(x)=\left\{\begin{array}{cl}0&\mbox{if }0\mbox{ appears in }x,\\ 1&\mbox{otherwise.}\end{array}\right.

If nothing else, it follows that if w is an infinite word that admits a monochromatic factorization for any coloring, then the first letter of w must appear infinitely often. The same idea shows that each letter in w must appear infinitely often.

Actually, significantly more should be true. For example, consider the word

w=010110111\dots 01^n0 1^{n+1}\dots,

and the coloring

c(x)=\left\{\begin{array}{cl}0&\mbox{if }x\mbox{ is a prefix of }w,\\1&\mbox{otherwise.}\end{array}\right.

This example shows that in fact any such w must admit a prefixal factorization, a factorization

w=x_0x_1\dots

where each x_i is a prefix of w.

Problem. Characterize those infinite words w with the property P that given any coloring, there is a monochromatic factorization of w.

The above shows that any word with property P admits a prefixal factorization. But it is easy to see that this is not enough. For a simple example, consider

w=010^210^31\dots0^n10^{n+1}1\dots

Consider the coloring c where c(x)=0 if x is not a prefix of w, c(0)=1, and c(x)=2 otherwise. If

w=x_0x_1\dots

is a monochromatic factorization of w, then x_0=01\dots so c(x_0)=2 and each x_i must be a prefix of w of length at least 2. But it is easy to see that w admits no such factorization: For any n>2, consider the first appearance in w of 0^{n+1} and note that none of the first n zeros can be the beginning of an x_i, so for some j we must have x_j=01\dots 10^n and since n>2, in fact x_j=01\dots 10^n10^n, but this string only appears once in w, so actually j=0. Since n was arbitrary, we are done.

Here is a more interesting example: The Thue-Morse word

t=0110100110010110\dots

was defined by Axel Thue in 1906 and became known through the work of Marston Morse in the 1920s. It is defined as the limit (in the natural sense) of the sequence x_0,x_1,\dots of finite words given by x_0=0 and x_{n+1}=x_n\bar{x_n} where, for x\in\{0,1\}^*, \bar x is the result of replacing each letter i in x with 1-i.

This word admits a prefixal factorization, namely

t=(011)(01)0(011)0(01)(011)(01)0(01)(011)0(011)(01)0\dots

To see this, note that the sequence of letters of t can be defined recursively by t_0=0, t_{2n}=t_n and t_{2n+1}=1-t_n. To see this, note in turn that the sequence given by this recursive definition actually satisfies that t_n is the parity of the number of 1s in the binary expansion of n, from which the recursive description above as the limit of the x_n should be clear. The relevance of this observation is that no three consecutive letters in t can be the same (since t_{2n+1}=1-t_{2n} for all n), and from this it is clear that t can be factored using only the words 0, 01, and 011.

But it is not so straightforward as in the previous example to check whether t admits a factorization into prefixes of length larger than 1.

Instead, I recall a basic property of t and use it to exhibit an explicit coloring for which t admits no monochromatic factorization.

The basic property is the following:

Lemma. t contains no overlaps, that is, no words of the form axaxa where a is a letter. In particular, no non-empty factor of t is a cube.

Proof. Proceed by contradiction. Suppose axaxa is an overlap present in t say t_k=a and, letting m=|ax|, then t_{k+i}=t_{k+i+m} for 0\le i\le m, so

axaxa=t_kt_{k+1}\dots t_{k+m}t_{k+m+1}\dots t_{k+2m}.

Assume further that m is minimal with this property.

It follows that m must be odd. In fact, if m=2m' is even, consider the word

t_kt_{k+2}t_{k+4}\dots t_{k+m}t_{k+m+2}t_{k+m+4}\dots t_{k+2m}.

If k=2k' is even, then (by the recursive definition of the t_i) this is also the word

t_{k'}t_{k'+1}t_{k'+2}\dots t_{k'+m'}t_{k'+m'+1}t_{k'+m'+2}\dots t_{k'+2m'},

which is an overlap ax'ax'a that is a factor of t with m'=|ax'|, contradicting the minimality of m.

Similarly, if k=2k'+1, then (again, by the recursive definition of the t_i) the word

t_{k'}t_{k'+1}t_{k'+2}\dots t_{k'+m'}t_{k'+m'+1}t_{k'+m'+2}\dots t_{k'+2m'}

is an overlap in t of the form (1-a)x'(1-a)x'(1-a) (where x'=\bar y for y=t_{k+2}t_{k+4}\dots t_{k+m-2}) with m'=|(1-a)x'|, again contradicting the minimality of m.

We reach a contradiction by arguing that m cannot be odd either. First, we note that m< 4. Otherwise, for some i with 0\le i<4\le m, we see that k+i\equiv1\pmod4. This means that t_{k+i}=t_{k+i+1} (by the description of the t_n in terms of the binary expansion of n). This means that we must also have that t_{k+i+m}=t_{k+i+1+m}, but this is impossible, since m is odd, so k+i+m is even.

We proceed to rule out the two remaining cases. We already know that m=1 is not possible. So, suppose m=3. This means the overlap has the form abcabca where b,c are also letters. By parity considerations, one of the two occurrences of ca must have c=t_i for odd i, so c=1-a. Similarly, b=1-(1-a)=a and, we have a contradiction since, for the same reason, we must also have a=1-b=1-a\Box

Now that we know that t admits no overlaps, it is easy to produce a coloring for which t admits no monochromatic factorization. Indeed, define c by setting c(x)=2 if x is not a prefix of t, and c(x)=i (for i=0 or i=1) if x is a prefix of t that ends in i.

Suppose that t=x_0x_1\dots is a monochromatic factorization of t. Each x_i is then a prefix of t, and all end in the same latter, say a. Now note that, for some i>0, we must have  |x_i|\le |x_{i+1}|. Since x_i and x_{i+1} are prefixes of t, it follows that x_i is also a prefix of x_{i+1}. And, since i>0, this means that x_{i-1} is defined, and ends in a, so we find in t the word ax_ix_i, that is, axaxa where x_i=xa. This is an overlap, contradicting what we just showed.

This seems a good moment to point out the obvious remark that there are words with property P: Any constant word has this property. In fact, any periodic word (any word of the form x^{\mathbb N}) has this property.

The main result of the Wojcik-Zamboni paper is that these are all the examples.

Theorem. A word has property P iff it is periodic.

The rest of this post is devoted to the proof of this theorem.

2. Ensuring periodicity

What Wojcik and Zamboni prove in their note is actually stronger than stated. They show that it is enough to consider colorings with range \{0,1\}: If w admits monochromatic factorizations for all such colorings, then w is periodic. That in itself is worthy of mention. All prior attempts on the problem that I am aware of took advantage of the fact that the colorings could use any (finite) number of colors. The idea was to exploit the following easy observation:

Observation. Suppose w has property P. Let \Phi be a property of finite words, and suppose that there is a coloring c such that for any monochromatic factorization

w=x_0x_1\dots

of w with respect to c, at least one of the x_i has property \Phi. There is then a coloring c' such that any monochromatic factorization

w=y_0y_1\dots

of w with respect to c' is also monochromatic with respect to $c$, and moreover all the y_i have property \Phi.

Proof. Suppose c takes the values 0,\dots,k-1. Consider the coloring c':A^*\to \{0,\dots,2k-1\} where c'(w)=2i if c(x)=i and x does not have property \Phi, and c'(x)=2i+1 if c(x)=i and x has property \Phi. Now note that by design any monochromatic factorization

w=z_0z_1\dots

of w with respect to c' is monochromatic with respect to c, and therefore at least one of the z_i has property \Phi. By definition of c', this means that all z_i have property \Phi. \Box

(For instance, we may assume that all the factors in w are prefixes, that every letter that ever appears in w appears in all of them, that they all end in the same letter and coincide on their first 7 symbols, that their lengths are all congruent modulo 258, etc.)

We now proceed with the proof of the theorem.

Begin by fixing a linear ordering < of A. Assume that w is not periodic. We describe a coloring c:A^+\to\{0,1\} for which w admits no monochromatic factorization. Given distinct words u,v of the same length, write u\prec v if u precedes v lexicographically (with respect to the ordering < we fixed on A), that is if u=u_0u_1\dots and v=v_0v_1\dots, and i is least such that u_i\ne v_i, then in fact u_i<v_i. For not necessarily distinct words of the same length,write u\preceq v iff either u\prec v, or u=v. Finally, for any n, denote by P_w(n) the prefix of w of length n. Clearly, x\preceq y implies x'\preceq y' for any prefixes x' and y' of x and y, respectively, of the same length. Similarly, if x\prec y and x,y are prefixes of x',y', respectively, with x',y' of the same length, then x'\prec y'.

Definition. For x\in A^+, set c(x)=0 if x\prec P_w(|x|) or if x=P_w(|x|) and w\prec w', where w=xw'. Also, set c(x)=1 if P_w(|x|)\prec x or if P_w(|x|)=x and w'\prec w, where w=xw'

Note that c is well defined since if x=P_w(|x|) and w=xw', then either w=x^{\mathbb N}, (which cannot be by assumption) or else w\ne w'.

Fix  a factorization w=x_0x_1\dots We proceed to argue that it cannot be monochromatic with respect to c. The argument will be by contradiction. So, assume that all x_i have the same color. First note that we may as well assume that c(x_i)=0 for all i. Indeed, if this is not the case, replace the ordering < of A with its inverse >, and note that now c(x_i)=0 for all i.

We proceed to check that each x_i is a prefix of w, and a bit more. Given i, if w=x_0\dots x_i w', It is convenient to define w_i as the longest common prefix of w and w'.

Lemma 1. c(x_0\dots x_i)=0 for all i.

Proof. We argue by induction on i. Suppose c(x_0\dots x_i)=0. By definition of c, this means that if w=x_0\dots x_i w', then there are letters a<b in A and infinite words w'', w''' with w=w_i a w'' and w'=w_i b w'''. The key observation is that this implies that x_{i+1} is a prefix of w_i. Indeed, otherwise w_i b is a prefix of x_{i+1}, while w=w_i a\dots, so P_w(|x_{i+1}|)\prec x_{i+1} and therefore c(x_{i+1})=1.

Since x_{i+1} is a prefix of w_i (and therefore also of w), we can write w_i=x_{i+1}v for some v, so that w=(x_0\dots x_{i+1})vbw'''. On the other hand, c(x_{i+1})=0 and, since x_{i+1} is a prefix of w, then we must have w=x_{i+1}z where w\prec z. But w=w_ia\dots=x_{i+1}va\dots, so w\prec z implies in particular that P_w(|va|)\preceq va. But then P_w(|vb|)\prec vb, since

P_w(|vb|)=P_w(|va|)\preceq va\prec vb.

From this we conclude that w\prec vbw''', so that c(x_0\dots x_ix_{i+1})=0, as wanted. \Box

We are almost done. With notation as in the lemma, we have that w=x_0\dots x_i w_i b w''' and also w_i= x_{i+1} v, so that w=(x_0\dots x_{i+1}) vb w'''. It follows that w_{i+1} is a prefix of v. Otherwise, vb is a prefix of w_{i+1}, which is in turn a prefix of w, so vb is a prefix of w=x_{i+1}va\dots. Since a<b, this gives us that va\prec vb=P_w(|va|), so that va\dots\prec w, and c(x_{i+1})=1, a contradiction.

Lemma 2. Define

S_i=|x_0|+\dots+|x_i|+|w_i|

for all i. Then S_i\to_i \infty and S_{i+1}\le S_i for all i.

Clearly, the two conclusions of Lemma 2 contradict one another, and we are done. It remains to prove Lemma 2.

Proof. With notation as above, w_i=x_{i+1}w_{i+1}v' for some v', so that |x_{i+1}|+|w_{i+1}|\le|w_i|, and S_{i+1}\le S_i. On the other hand, S_i\ge |x_0|+\dots|x_i|\ge i+1\to\infty. \Box

The result follows. \Box

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: