Fine and Wilf’s theorem on words

Let $w$ be a word on an alphabet $A$ and let $|w|$ be its length.A period of $w$ is a value $p>0$such that $w_{i+p}=w_i$ for every $i\in \{1,2,\mathrm{\dots },|w|-p\}$.This is the same as saying that $w=u^{k}r$for some $u,r\in A^{\ast }$ and $k\in \mathbb{N}$such that $|u|=p$ and $r$ is a prefix of $u$.

Fine and Wilf’s theoremgives a condition on the length of the periods a word can have.

Theorem 1

Let $w$ be a word on an alphabet $A$ having periods $p$ and $q$.If $\mathrm{|}w\mathrm{|}\mathrm{\ge }p\mathrm{+}q\mathrm{-}\gcd \mathit{}\mathrm{(}p\mathrm{,}q\mathrm{)}$,then $w$ has period $\gcd \mathit{}\mathrm{(}p\mathrm{,}q\mathrm{)}$.The value $p\mathrm{+}q\mathrm{-}\gcd \mathit{}\mathrm{(}p\mathrm{,}q\mathrm{)}$is the smallest one that makes the theorem true.

As a counterexample showing that the condition on $|w|$ is necessary,the word $aaabaaa$ has periods $4$ and $6$, but not $2=\gcd (4,6)$.This can happen because its length is .

Observe that Theorem 1 can be restated as follows(cf. [1]).

Theorem 2

Let $u$ and $w$ be words over an alphabet $A$.Suppose $u^h$ and $w^k$, for some $h$ and $k$,have a common prefix of length$\mathrm{|}u\mathrm{|}\mathrm{+}\mathrm{|}w\mathrm{|}\mathrm{-}\gcd \mathit{}\mathrm{(}\mathrm{|}u\mathrm{|}\mathrm{,}\mathrm{|}w\mathrm{|}\mathrm{)}\mathrm{.}$Then there exists $z\mathrm{\in }{A}^{\mathrm{\ast }}$ of length $\gcd \mathit{}\mathrm{(}\mathrm{|}u\mathrm{|}\mathrm{,}\mathrm{|}w\mathrm{|}\mathrm{)}$such that $u\mathrm{,}w\mathrm{\in }{z}^{\mathrm{\ast }}$.The value$\mathrm{|}u\mathrm{|}\mathrm{+}\mathrm{|}w\mathrm{|}\mathrm{-}\gcd \mathit{}\mathrm{(}\mathrm{|}u\mathrm{|}\mathrm{,}\mathrm{|}w\mathrm{|}\mathrm{)}$is also the smallest one that makes the theorem true.

In fact, Theorem 1 clearly implies Theorem 2.Now, suppose Theorem 2 is true.Suppose $w$ has periods $p$ and $q$and length at least $p+q-\gcd (p,q)$:write $w=u^{k}r=v^{h}s$ with$|u|=p$, $|v|=q$, $r$ prefix of $u$, $s$ prefix of $v$.Let $M$ be a common multiple of $p$ and $q$ greater than $p$, $q$, and $|w|$:then $u^{M/p}$ and $v^{M/q}$ have the common prefix $w$,so they also have a common prefix of length $p+q-\gcd (u,v)$.Then $u$ and $v$ are powers of a word $z$ of length $\gcd (p,q)$,and it is easy to see that $w=z^{m}t$for some $m>0$ and some prefix $t$ of $z$.