A Four Colorings Theorem

Abstract

Let $\mathrm{\Sigma }$ be a totally ordered set. We work on finite strings $b=b_1{b}_2\dots b_m$ of $b_i$ elements from $\mathrm{\Sigma }$. Such a $b$ is a Lyndon word (Lyn) if $m\ge 1$, and $b$ is the unique first in lexicographic order among the $m$ rows of the $m\times m$ circulant matrix with $b$ as the first row.A classic result is that every string $b$ has a unique maximal factorization $umf(b)$ into Lyndon words, each Lyndon word of the maximum possible size in $b$.In 1983, J. P. Duval $[6]$ published Algorithm 1, which finds $umf(b)$. It was studied in 1991 by A. Apostolico and M. Crochemore $[1]$. Their work was then studied in 1994 by J.W. Daykin, C.S. Iliopoulos, and W.F. Smyth $[5]$.Since Duval used a programming language, we start by giving a new simple account of his Algorithm 1. Our Algorithm 2 modifies Duval’s Algorithm 1 to find $umf(a)$, when $a$ is a string $a=A_1{A}_2\dots A_p$ of Lyndon words $A_i$.Our Algorithm 3 is also for a string $a=A_1{A}_2\dots A_p$ of Lyndon words $A_i$. It is completely different from Algorithms 1 and 2. It snakes right, left, right, and so on. It revealed that Lyndon words have a special structure. We give an example where Algorithm 3 needs almost $2m$ tests; we think that is the most needed, but cannot give a rigorous proof.