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 theorem gives 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$.

Title	Fine and Wilf’s theorem on words
Canonical name	FineAndWilfsTheoremOnWords
Date of creation	2013-03-22 18:00:39
Last modified on	2013-03-22 18:00:39
Owner	Ziosilvio (18733)
Last modified by	Ziosilvio (18733)
Numerical id	18
Author	Ziosilvio (18733)
Entry type	Theorem
Classification	msc 68Q70
Classification	msc 68Q45
Classification	msc 68R15