# 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{-}\mathrm{gcd}\mathit{}\mathrm{(}p\mathrm{,}q\mathrm{)}$, then $w$ has period $\mathrm{gcd}\mathit{}\mathrm{(}p\mathrm{,}q\mathrm{)}$. The value $p\mathrm{+}q\mathrm{-}\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=\mathrm{gcd}(4,6)$.
This can happen because its length is $$.

###### 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{-}\mathrm{gcd}\mathit{}\mathrm{(}\mathrm{|}u\mathrm{|}\mathrm{,}\mathrm{|}w\mathrm{|}\mathrm{)}\mathrm{.}$ Then there exists $z\mathrm{\in}{A}^{\mathrm{\ast}}$ of length $\mathrm{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{-}\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-\mathrm{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-\mathrm{gcd}(u,v)$. Then $u$ and $v$ are powers of a word $z$ of length $\mathrm{gcd}(p,q)$, and it is easy to see that $w={z}^{m}t$ for some $m>0$ and some prefix $t$ of $z$.

## References

- 1 M. Lothaire. Combinatorics on words. Cambridge University Press 1997.

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 |