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 $1$ s 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$

This entry was posted on Saturday, August 20th, 2016 at 1:29 pm and is filed under math.CO, Papers. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

A kind of library