Completing the New Periodicity Lemma

Abstract

<p>The “Three Squares Lemma” (Crochemore and Rytter 1995) famously explored the consequences of supposing that three squares occur at the same position in a string. Essentially, it showed that this phenomenon could not occur unless the longest of the three squares was at least the sum of the lengths of the other two. More recently, several papers (Fan et al. 2006; Franek, Fuller, et al. 2012; Kopylova and Smyth 2012; Simpson 2007) have greatly extended this result to a “New Periodicity Lemma” (NPL) by supposing that only two of the squares occur at the same position, with a third occurring in a neighbourhood to the right. The proof of the NPL involves fourteen subcases, twelve of which have been proven over the last seven years. In this thesis, we prove the final two remaining.</p>