An extension of the periodicity lemma to longer periods

The well-known Periodicity Lemma of Fine and Wilf states that if the word x of length n has periods p,q satisfying p+q-d⩽n, then x has also period d, where d=gcd(p,q). Here we study the structure of long periods, namely p+q-d>n. In particular, we construct recursively a sequence of integers p=p1>p2>⋯>pt-1⩾2, and show that such x is covered with periods pi by a basic kernel factor. We further compute the maximum alphabet size |A|=p+q-n of A over which a word with long periods can exist, and compute the subword complexity of x over this A.