Fine and Wilf’s theorem on words
Let be a word on an alphabet and let be its length. A period of is a value such that for every . This is the same as saying that for some and such that and is a prefix of .
Fine and Wilf’s theorem gives a condition on the length of the periods a word can have.
Let be a word on an alphabet having periods and . If , then has period . The value is the smallest one that makes the theorem true.
As a counterexample showing that the condition on is necessary, the word has periods and , but not . This can happen because its length is .
Let and be words over an alphabet . Suppose and , for some and , have a common prefix of length Then there exists of length such that . The value 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 has periods and and length at least : write with , , prefix of , prefix of . Let be a common multiple of and greater than , , and : then and have the common prefix , so they also have a common prefix of length . Then and are powers of a word of length , and it is easy to see that for some and some prefix of .
- 1 M. Lothaire. Combinatorics on words. Cambridge University Press 1997.
|Title||Fine and Wilf’s theorem on words|
|Date of creation||2013-03-22 18:00:39|
|Last modified on||2013-03-22 18:00:39|
|Last modified by||Ziosilvio (18733)|