cjerdonek / Critical Factorization Theorem 59ddb16d0bf4b5a237d52812983ea74a7199a8ac

The Critical Factorization Theorem is a fundamental result in combinatorics on words that relates the presence of local repetitions within a word to the overall periodicity of the word.

The Critical Factorization Theorem is a fundamental result in combinatorics on words that relates the presence of local repetitions within a word to the overall periodicity of the word.

The theorem was first proven in 1978 by Césari and Vincent [CV]. For more recent treatments, see [CP] and [HN].

Before stating the theorem, we define some preliminaries.

Definitions

Given a word $w$, we let $|w|$ denote the length of the word. If $i$ is an integer $1\leq i\leq|w|$, we let $w[i]$ denote the $i$-th letter (i.e. $i$ is a $1$-based index). We say an integer $d>0$ is a period of $w$ if $w[i] = w[i + d]$ for all $i$ when both sides are defined. Observe that if $d$ is a period of $w$, then $w$ takes the form of multiple copies of a word of length $d$ concatenated together (possibly with the last copy of the word cut short). We define the global period of $w$ to be the smallest possible $d$ that is a period.

Given a word, we define a point or position $p$ to be the location between letters that is immediately after the $p$-th letter and before the $p+1$-th letter. For example, the position $p=1$ means the location between the first and second letters.

Given a position $p$ of a word $w$, we say an integer $r>0$ is a local period at $p$ if $w[i]=w[i+r]$ for all $i$ with $p-r+1\leq i \leq p$, and when both are sides defined. An equivalent formulation is as follows. An integer $r>0$ is a local period at $p$ if there is a word $u$ of length $r$ such that $p$ is both immediately preceded by and immediately followed by $u$ (but allowing $u$ to be truncated at the beginning and/or end if the beginning and/or end of $w$ is reached). In this case, we say $u$ is a repetition word at $p$.

Finally, we say that a point $p$ is a critical point of $w$ if the local period at $p$ equals the global period of $w$. Roughly speaking, a critical point represents a transition to a point in the word of least possible local repetition.

Statement of the Theorem

We can now state the theorem:

Critical Factorization Theorem. Let $w$ be a word with $|w|\geq 2$ and global period $d$. Then there exists a critical point $p$ of $w$ satisfying $1\leq p < d$.

One way of looking at the theorem is as follows. Say the global period $d$ of a word $w$ is known to be bounded above by some integer $d^{\prime}$ (i.e. so $d\leq d^{\prime}$). For example, $d^{\prime}$ can be a period that isn't necessarily global, or it can be $|w|$. Further assume there is an integer $k$ with $k<d^{\prime}$ such that the local period of $w$ at $p$ is less than or equal to $k$ for all points $p<d^{\prime}$. Then the Critical Factorization Theorem says the global period $d$ satisfies $d\leq k$. In other words, the theorem lets us "patch together" the local periods to get a global one; we can draw a global conclusion from a local property that holds everywhere.

References

• [CV] Y. Césari and M. Vincent, "Une caractérisation des mots périodiques," Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences, 286 Ser. A, 1978, 175–1177.
• [CP] M. Crochemore and D. Perrin, "Two-way string-matching," Journal of the Association for Computing Machinery, Vol. 38, No. 1, July 1991, 651–675.
• [HN] T. Harju and D. Nowotka, "Density of Critical Factorizations," RAIRO - Theoretical Informatics and Applications, Vol. 36, No. 3, July/Sept 2002, 315-327.