CLR cover
Previous page

Regularities

Next page

The powers of a word $x$ are defined by $x^0=\mv$ and $x^i=x^{i-1}x$ for a positive integer $i$. The $k$th power of $x$ is $x^k$. It is a square if $k$ is a positive even integer and a cube if $k$ is a positive multiple of $3$.

The next lemma states a first consequence of the Periodicity lemma.

Lemma 2

For words $x$ and $y$, $xy=yx$ if and only if $x$ and $y$ are (integer) powers of the same word. The same conclusion holds when there exist two positive integers $k$ and $\ell$ for which $x^k=y^{\ell}$.

The proofs of the two parts of the lemma are essentially the same (in fact the conclusion derives from a more general statement on codes). For example, if $xy=yx$, both $x$ and $y$ are borders of the word and both $|x|$ and $|y|$ are periods of it, and then $\gcd(|x|,|y|)$ as well by the Periodicity lemma. Since $\gcd(|x|,|y|)$ divides also $|xy|$, the conclusion follows. The converse implication is straightforward.

The non-empty word $x$ is said to be primitive if it is not the power of any other word. That is to say, $x$ is primitive if $x=u^k$, for a word $u$ and a positive integer $k$, implies $k=1$ and then $u=x$.

It follows from Lemma 2 that a non-empty word has exactly one primitive word it is a power of. When $x=u^k$ and $u$ is primitive, $u$ is called the primitive root of $x$ and $k$ is its exponent, denoted by $\exp(x)$. More generally, the exponent of $x$ is the quantity $\exp(x)=|x|/\per(x)$, which is not necessarily an integer, and the word is said to be periodic if its exponent is at least $2$.

Note the number of conjugates of a word, the size of its conjugacy class, is the length of its (primitive) root.

Another consequence of the Periodicity lemma follows.

Lemma 2 (Primitivity lemma, Synchronisation lemma)

A non-empty word $x$ is primitive if and only if it is a factor of its square only as a prefix and as a suffix, or equivalently if and only if $\per(x^2)=|x|$.

The notion of run or maximal periodicity encompasses several types of regularities occurring in words. A run in the word $x$ is a maximal occurrence of a periodic factor. To say it more formally, it is an interval $[i\dd j]$ of positions on $x$ for which $\exp(x[i\dd j])\geq 2$ and both $x[i-1\dd j]$ and $x[i\dd j+1]$ have periods larger than that of $x[i\dd j]$ when they exist. In this situation, since the occurrence is identified by $i$ and $j$, we also say abusively that $x[i\dd j]$ is a run.

Another type of regularity consists in the appearance of reverse factors or of palindromes in words. The reverse or mirror image of the word $x$ is the word $x^\mathrm{R} = x[|x|-1] x[|x|-2]\cdots x[0]$. Associated with this operation is the notion of palindrome: a word $x$ for which $x^\mathrm{R}=x$.