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. Informally, the conclusion is that such words  have also a third, shorter period. If the periods and length of  satisfy certain conditions, then this third period can equal. In this case then, the theorem's conclusion is that  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.

Statement

The two most common phrasings of Fine and Wilf's theorem are as follows:
It is folklore that an infinite sequence having two periods  and  has also  as a period. Indeed, by Bézout's identity, there are integers  satisfying  or. In the first case, we always have. And in the second, we always have.
Fine and Wilf's theorem refines this result only by bounding the length of the sequence  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. Then  has periods  and, since. By Fine and Wilf's theorem,  would also have period  if its length were at least. In fact, the length of  is, only one short of this threshold, and  fails to have this short period.

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  be nonempty words over an alphabet. We first reduce to the case : If instead we have and, with,, we consider  and  as elements of. That is, we view them as words over the alphabet  whose letters are words of length  in the original alphabet. With respect the larger alphabet, and so proving the result for this case will suffice.
So let  and with. Suppose that  and  have a common prefix of length. Assume further that, and consider the image shown below. Here the positions of the words  and  are numbered. The vertical dashed line indicates how far the words  and  can be compared.
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. By our premises, the value of the position computed as follows:where  is reduced to the interval, gets the same value as that of. So the procedure computes  from the number. Since,   differs from. If differs from  as well, the procedure can be repeated. The claim is: The new positions obtained will always differ from all the previous ones. Indeed, if with, then necessarily, since.
Now, if the procedure can be repeated  times, then every position in  will get covered, meaning that these'll all get the same letter as the initial one at position. But this implies that  is a power of a single letter, and thus so is. Hence, this would complete the proof.
But the procedure can be repeated  times if we choose  such that.  If this holds, then all the values  for  differ from. Clearly, such an  can be found.

Variants

Often the following weakening of Fine and Wilf's theorem is formulated:
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". This statement therefore requires only that has a different periodic presentation than the trivial one as a repetition of s. To write it down formally, let denote the maximal length of a common factor of the words and. Then
Variants of the theorem have also been introduced that look at abelian periods.. 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, the appropriate bound iswhere  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. The following has been proved:

Relation to Sturmian Words

Let  be coprime. Fine and Wilf's Theorem allows for words of length  to have periods  and  without being a power of a single letter. In fact, given  and, such a word always exists. Moreover, it is binary and unique.
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. Now there are two positions wherein the procedure cannot be applied, viz.  and. 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 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  in a text  in time bounded by. It compares to a portion of  beginning at a position  and, if a mismatch is found, shifts  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
Fine and Wilf's theorem can also be used to reason about the solution sets of word equations.