Draft:Fine and Wilf's theorem

In combinatorics on words, Fine and Wilf’s theorem is a fundamental result describing what happens when a long-enough word has two different periods (i.e., distances at which its letters repeat). Informally, the conclusion is that such words $w$ have also a third, shorter period. If the periods and length of $w$ satisfy certain conditions, then this third period can equal $1$. In this case then, the theorem’s conclusion is that $w$ is a power of a single letter. The theorem was introduced in 1963 by Nathan Fine and Herbert Wilf. It is easy to prove, and has uses across theoretical computer science and symbolic dynamics.

Herbert Wilf, who introduced the theorem alongside Nathan Fine

Statement

The two most common phrasings of Fine and Wilf’s theorem are as follows:

Theorem — Let $w$ be a word with periods $p$ and $q$ (i.e., distances at which its letters repeat). If the length of $w$ is at least $p+q-\gcd(p,q)$, then $w$ also has period $\gcd(p,q)$.

Theorem — Let $u,v$ be nonempty words. If the infinite words $uuu\cdots$ and $vvv\cdots$ have a common prefix of length $\mid u\mid +\mid v\mid -\gcd(\mid u\mid ,\mid v\mid )$, then $u,v$ are powers of a common word.

It is folklore that an infinite sequence $(a_{n})_{n\in \mathbb {N} }$ having two periods $h$ and $k$ has also $\gcd(h,k)$ as a period. Indeed, by Bézout’s identity, there are integers $r,s\geq 0$ satisfying $rh-sk=\gcd(h,k)$ or $rk-sh=\gcd(h,k)$. In the first case, we always have $a_{n}=a_{n+rh}=a_{n+rh-sk}=a_{n+\gcd(h,k)}$. And in the second, we always have $a_{n}=a_{n+rk}=a_{n+rk-sh}=a_{n+\gcd(h,k)}$.

Fine and Wilf’s theorem refines this result only by bounding the length of the sequence $(a_{n})$ to some large-enough finite value such that the third period must still arise. The finite bound of Fine and Wilf is optimal. Indeed, consider $w:=aaabaaa$. Then $w$ has periods $4$ and $6$, since $w=aaab\cdot aaa=aaabaa\cdot a$. By Fine and Wilf’s theorem, $w$ would also have period $\gcd(4,6)=2$ if its length were at least $4+6-\gcd(4,6)=8$. In fact, the length of $w$ is $7$, only one short of this threshold, and $w$ fails to have this short period $2$.

Proof

We prove the second phrasing of the theorem above. The proof comes from , and is closely related to the extended Euclidean algorithm, much like the proof of Bézout’s identity.

Let $u,v$ be nonempty words over an alphabet $\Sigma$. We first reduce to the case $gcd(|u|,|v|)=1$: If instead we have $|u|=dp$ and $|v|=dq$, with $d>1$, $\gcd(p,q)=1$, we consider $u$ and $v$ as elements of $(\Sigma ^{d})^{+}$. That is, we view them as words over the alphabet $\Sigma ^{d}$ whose letters are words of length $d$ in the original alphabet $\Sigma$. With respect the larger alphabet $\gcd(|u|,|v|)=1$, and so proving the result for this case will suffice.

So let $p:=|u|$ and $q:=|v|$ with $\gcd(p,q)=1$. Suppose that $uuu\cdots$ and $vvv\cdots$ have a common prefix of length $p+q-1$. Assume further (by symmetry) that $p>q$, and consider the image shown below. Here the positions of the words $uuu\cdots$ and $vvv\cdots$ are numbered $1,2,..,p+q-1$. The vertical dashed line indicates how far the words $uuu\cdots$ and $vvv\cdots$ can be compared.

The procedure used in our proof of Fine and Wilf's theorem.

The arrow describes a procedure, the purpose of which is to fix the values of new positions to be the same as a given value of an initial position $i_{0}\in [1,..,q-1]$. By our premises, the value of the position computed as follows:$$i_{0}\mapsto i_{0}+p\mapsto i_{1}\equiv i_{0}+p{\pmod {q}},$$where $i_{1}$ is reduced to the interval $[1,...,q]$, gets the same value as that of $i_{0}$. So the procedure computes $i_{1}$ from the number $i_{0}$. Since $\gcd(p,q)=1$,  $i_{1}$ differs from $i_{0}$. If $i_{1}$ differs from $q$ as well, the procedure can be repeated. The claim is: The new positions obtained will always differ from all the previous ones. Indeed, if $$i_{0}+np\equiv i_{0}+mp{\pmod {q}}$$with $n,m\in [0,q-1]$, then necessarily $n=m$, since $\gcd(p,q)=1$.

Now, if the procedure can be repeated $q-1$ times, then every position in (the first repetition of) $v$ will get covered, meaning that these’ll all get the same letter as the initial one at position $i_{0}$. But this implies that $v$ is a power of a single letter, and thus so is $u$. Hence, this would complete the proof.

But the procedure can be repeated $q-1$ times if we choose $i_{0}$ such that $i_{0}+(q-1)p\equiv q{\pmod {q}}$.  If this holds, then all the values $i_{0}+jp{\pmod {q}}$ for $j=0,...,q-2$ differ from $q$. Clearly, such an $i_{0}$ can be found.

Variants

Often the following weakening of Fine and Wilf’s theorem is formulated:

Theorem — Let $u,v$ be nonempty words. If the infinite words $uuu\cdots$ and $vvv\cdots$ have a common prefix of length $\mid u\mid +\mid v\mid$, then $u,v$ are powers of a common word.

This variant can be proved using a simplified version of the above argument. It is often strong enough in application.

Another reformulation removes the emphasis on the words' "left-hand-sides" (i.e., the requirement for $uuu\cdots$ and $vvv\cdots$ to agree from the start). This statment therefore requires only that $uuu\cdots$ has a different periodic presentation than the trivial one as a repetition of $u$s. To write it down formally, let $\ell (w_{1},w_{2})$ denote the maximal length of a common factor of the words $w_{1}$ and $w_{2}$. Then

Theorem — Let $u,v$ be nonempty words. If $\ell (uuu\cdots ,vvv\cdots )\geq \mid u\mid +\mid v\mid -\gcd(\mid u\mid ,\mid v\mid )$, then the primitive roots of $u,v$ are conjugates.

Variants of the theorem have also been introduced that look at abelian periods (i.e., consecutive blocks in words that are not necessarily identical, but anagrams of each other). There are also ways to apply the theorem to continuous functions having multiple periods.

Generalisations

Fine and Wilf’s theorem has been generalised to work with words having more than two periods. For instance, for three periods $p_{1}<p_{2}<p_{3}$, the appropriate bound is$${\frac {1}{2}}\left(p_{1}+p_{2}+p_{3}-2\gcd(p_{1},p_{2},p_{3})+h(p_{1},p_{2},p_{3})\right),$$where $h$ is a function related to the Euclidean algorithm on three inputs.

The result has also been investigated with respect to “partial words”, which are allowed to contain “don’t care” positions called holes. Holes match each other and all other letters. More precisely,

Theorem — There exists a computable function $L(h,p,q)$ such that, if a word $w$ with $h$ holes and periods $p,q$ has length $\geq L(h,p,q)$, then $w$ also has period $\gcd(p,q)$.

Relation to Sturmian Words

Let $p,q$ be coprime. Fine and Wilf’s Theorem allows for words of length $p+q-2$ to have periods $p$ and $q$ without being a power of a single letter. In fact, given $p$ and $q$, such a word always exists. Moreover, it is binary and unique (up to renaming its letters).

The proof of this claim follows the proof given above. Indeed, in that proof, the letters in the positions of the shorter word were fixed using the procedure. The procedure could be applied in all but one case, namely when the position was $q$. Now there are two positions wherein the procedure cannot be applied, viz. $q$ and $q-1$. Accordingly, we are free to choose the letters occurring in two positions of the shorter word, but as soon as we do this, every other position is fixed. Since we want a word that’s not a power of a single letter, our only choice (modulo the letters’ names) is to put different letters in the two positions we have control over. Uniqueness follows from the fact that every other position is fixed.

The words so obtained are the finite Sturmian words. These words admit many characterisations; the above discourse gives a way to compute them.

Applications

One application of Fine and Wilf's theorem is to string-searching algorithms. For instance, the Knuth-Morris-Pratt algorithm finds all occurrences of a pattern $p$ in a text $t$ in time bounded by $O(|p|+|t|)$. It compares $p$ to a portion of $t$ beginning at a position $i$ and, if a mismatch is found, shifts $p$ rightward depending on where the mismatch occurred. The worst-case for the Knuth-Morris-Pratt algorithm comes from “almost-periodic” words, the idea being that – in this case – long sequences of matching letter can occur without a complete match. It turns out that such words are precisely the maximal “counterexamples” to Fine and Wilf’s theorem (i.e., the finite Sturmian words, described in the previous section).

Fine and Wilf’s theorem can also be used to reason about the solution sets of word equations.

References

This page will be placed in the following categories if it is moved to the article namespace.

Categories:

• Combinatorics on words