The New Periodicity Lemma revisited

In 2006, the New Periodicity Lemma (NPL) was published, showing that the occurrence of two squares starting at a position i in a string necessarily precludes the occurrence of other squares of specified period in a specified neighbourhood of i. The proof of this lemma was complex, breaking down into 14 subcases, and requiring that the shorter of the two squares be regular. In this paper we significantly relax the conditions required by the NPL …