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).
satisfy certain conditions, then this third period can equal
The theorem was introduced in 1963 by Nathan Fine and Herbert Wilf.
[3] It is easy to prove, and has uses across theoretical computer science and symbolic dynamics.
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.
, and so proving the result for this case will suffice.
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:
The claim is: The new positions obtained will always differ from all the previous ones.
will get covered, meaning that these'll all get the same letter as the initial one at position
This variant can be proved using a simplified version of the above argument.
[2] Another reformulation removes the emphasis on the words' "left-hand-sides" (i.e., the requirement for
has a different periodic presentation than the trivial one as a repetition of
denote the maximal length of a common factor of the words
Variants of the theorem have also been introduced that look at abelian periods.
[6] (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[3][5] Fine and Wilf's theorem has been generalised to work with words having more than two periods.
is a function related to the Euclidean algorithm on three inputs[8][5] The result has also been investigated with respect to "partial words",[9] which are allowed to contain "don't care" positions called holes.
The following has been proved:[5] Theorem — There exists a computable function
Fine and Wilf's Theorem allows for words of length
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
[2] These words admit many characterisations;[1][8] the above discourse gives a way to compute them.
One application of Fine and Wilf's theorem is to string-searching algorithms.
[5] For instance, the Knuth-Morris-Pratt algorithm finds all occurrences of a pattern
rightward depending on where the mismatch occurred.
[10] 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)[5] Fine and Wilf's theorem can also be used to reason about the solution sets of word equations.
