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 wi+p=wi for every i{1,2,,|w|-p}. This is the same as saying that w=ukr for some u,rA and k 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 |w|p+q-gcd(p,q), then w has period gcd(p,q). The value p+q-gcd(p,q) is the smallest one that makes the theorem true.

As a counterexampleMathworldPlanetmath showing that the condition on |w| is necessary, the word aaabaaa has periods 4 and 6, but not 2=gcd(4,6). This can happen because its length is 7<4+6-2=8.

Observe that Theorem 1 can be restated as follows (cf. [1]).

Theorem 2

Let u and w be words over an alphabet A. Suppose uh and wk, for some h and k, have a common prefix of length |u|+|w|-gcd(|u|,|w|). Then there exists zA of length gcd(|u|,|w|) such that u,wz. The value |u|+|w|-gcd(|u|,|w|) 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-gcd(p,q): write w=ukr=vhs 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 uM/p and vM/q have the common prefix w, so they also have a common prefix of length p+q-gcd(u,v). Then u and v are powers of a word z of length gcd(p,q), and it is easy to see that w=zmt 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