Fine and Wilf's theorem

{{Short description|Result on periodic sequences}}

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).{{Cite book |url=https://www.cambridge.org/core/product/identifier/9780511566097/type/book |title=Combinatorics on Words |series=Cambridge Mathematical Library |date=1997-05-29 |publisher=Cambridge University Press |isbn=978-0-521-59924-5 |editor-last=Lothaire |editor-first=M. |edition=2 |doi=10.1017/cbo9780511566097}}{{Cite web |last=Karhumäki |first=Juhani |title=Combinatorics of Words |url=https://www.math.utu.fi/en/home/karhumak/pdf/combwo.pdf |access-date=23 November 2024}} 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.{{Cite journal |last1=Fine |first1=N. J. |last2=Wilf |first2=H. S. |date=1965 |title=Uniqueness theorems for periodic functions |url=https://www.ams.org/journals/proc/1965-016-01/S0002-9939-1965-0174934-9/ |journal=Proceedings of the American Mathematical Society |language=en |volume=16 |issue=1 |pages=109–114 |doi=10.1090/S0002-9939-1965-0174934-9 |issn=0002-9939}} It is easy to prove, and has uses across theoretical computer science and symbolic dynamics.{{Cite book |url=https://link.springer.com/book/10.1007/978-3-642-59136-5 |title=Handbook of Formal Languages |date=1997 |language=en |doi=10.1007/978-3-642-59136-5 |isbn=978-3-642-63863-3 |editor-last1=Rozenberg |editor-last2=Salomaa |editor-first1=Grzegorz |editor-first2=Arto }}

File:Herbert Wilf.jpg

Statement

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

{{Math theorem

| math_statement = 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).

}}{{Math theorem

| math_statement = 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.{{Cite web |last=Shallit |first=Jeffrey |title=Fifty Years of Fine and Wilf |url=https://cs.uwaterloo.ca/~shallit/Talks/vu3.pdf |access-date=23 November 2024}} Indeed, by Bézout's identity, there are integers r,s \ge 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.

File:FineAndWilfProcedure.png

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 qwith 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:

{{Math theorem

| math_statement = 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 statement therefore requires only that uuu\cdots has a different periodic presentation than the trivial one as a repetition of us. 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

{{Math theorem

| math_statement = Let u,v be nonempty words. If \ell (uuu\cdots,vvv\cdots)\ge \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.{{Cite book |last1=Karhumäki |first1=Juhani |last2=Puzynina |first2=Svetlana |last3=Saarela |first3=Aleksi |chapter=Fine and Wilf's Theorem for k-Abelian Periods |series=Lecture Notes in Computer Science |date=2012 |volume=7410 |editor-last=Yen |editor-first=Hsu-Chun |editor2-last=Ibarra |editor2-first=Oscar H. |title=Developments in Language Theory |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-31653-1_27 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=296–307 |doi=10.1007/978-3-642-31653-1_27 |isbn=978-3-642-31653-1}} (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.{{Cite journal |last1=Constantinescu |first1=Sorin |last2=Ilie |first2=Lucian |date=2005-06-11 |title=Generalised fine and Wilf's theorem for arbitrary number of periods |url=https://linkinghub.elsevier.com/retrieve/pii/S030439750500023X |journal=Theoretical Computer Science |series=Combinatorics on Words |volume=339 |issue=1 |pages=49–60 |doi=10.1016/j.tcs.2005.01.007 |issn=0304-3975}} 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{{Citation |title=Sturmian Words |date=2002 |work=Algebraic Combinatorics on Words |pages=45–110 |editor-last=Lothaire |editor-first=M. |url=https://www.cambridge.org/core/books/abs/algebraic-combinatorics-on-words/sturmian-words/D7AD019B0546AE7258C6B38B13F14CAE |access-date=2024-11-23 |series=Encyclopedia of Mathematics and its Applications |place=Cambridge |publisher=Cambridge University Press |doi=10.1017/cbo9781107326019.003 |isbn=978-0-521-81220-7|url-access=subscription }}

The result has also been investigated with respect to "partial words",{{Cite journal |last1=Berstel |first1=Jean |last2=Boasson |first2=Luc |date=1999-04-28 |title=Partial words and a theorem of Fine and Wilf |url=https://linkinghub.elsevier.com/retrieve/pii/S0304397598002552 |journal=Theoretical Computer Science |volume=218 |issue=1 |pages=135–141 |doi=10.1016/S0304-3975(98)00255-2 |issn=0304-3975}} which are allowed to contain "don't care" positions called holes. Holes match each other and all other letters. The following has been proved:

{{Math theorem

| math_statement = There exists a computable function L(h,p,q) such that, if a word w with h holes and periods p,q has length \ge 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.{{Cite book |last1=Cormen |first1=Thomas H. |title=Introduction to algorithms |last2=Leiserson |first2=Charles Eric |last3=Rivest |first3=Ronald Linn |last4=Stein |first4=Clifford |date=2022 |publisher=The MIT Press |isbn=978-0-262-04630-5 |edition=4th |location=Cambridge, Massachusetts London, England}} 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