Periodicity Lemma, very often called the "Fine and Wilf theorem":

If a word of length p+q-GCD(p,q) has periods p and q, then it has also a period GCD(p,q). Moreover, the value p+q-GCD(p,q) is optimal in the following sense: there is a word of length p+q-GCD(p,q)-1 with periods p and q, which has not a period GCD(p,q).

Reference:

Fine, N. J.; Wilf, H. S., Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 1965 109114.

-- StepanHolub - 10 Sep 2011

Topic revision: r1 - 2011-09-10 - StepanHolub
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2023 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback