Example
\(
\def\sa#1{\tt{#1}}
\def\mv{\varepsilon}
\def\gcd{\mathit{gcd}}
\def\per{\mathit{per}}
\def\exp{\mathit{exp}}
\def\dd{\dot{}\dot{}}
\)
$\sa{abaab}$ is
primitive, while $\mv$ and $\sa{bababa}=(\sa{ba})^3$ are not.
The picture above illustrates the result of the Primitivity lemma.
The word $\sa{abbaba}$ is
primitive and there are only two occurrences of it in its square, while
$\sa{ababab}$ is not primitive and has four occurrences in its square.
$\sa{noon}$ and $\sa{testset}$ are English palindromes.
The first is an even palindrome of the form $uu^\mathrm{R}$ while
the second is an odd palindrome of the form $uau^\mathrm{R}$ with
a letter $a$.
The letter $a$ can be replaced by a short word, leading to the
notion of gapped palindromes as useful when related to folding
operations like those occurring in sequences of biological molecules.
As another example, integers whose decimal expansion
is an even palindrome are multiples of $11$, such as $1661=11\times151$ or
$175571=11\times15961$.
|
Regularities
|
|
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$.
