Summary: 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 \leq n\), then \(x\) has also period \(d\), where \(d = \gcd(p,q)\). Here we study the case of long periods, namely \(p+q-d > n\), for which we construct recursively a sequence of integers \(p = p_1 > p_2 > \dots > p_{j-1} \geq 2\), such that \(x_1\), up to a certain prefix of \(x_1\), has these numbers as periods. 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 \(A\).
For the entire collection see [Zbl 0968.00055].