Lyndon Words, the Three Squares Lemma, and Primitive Squares

2020/06/24 by Bannai, Hideo, Mieno, Takuya, Nakashima, Yuto
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2006.13576

Abstract

We revisit the so-called "Three Squares Lemma" by Crochemore and Rytter [Algorithmica 1995] and, using arguments based on Lyndon words, derive a more general variant which considers three overlapping squares which do not necessarily share a common prefix. We also give an improved upper bound of nlog₂ n on the maximum number of (occurrences of) primitively rooted squares in a string of length n, also using arguments based on Lyndon words. To the best of our knowledge, the only known upper bound was n log_ϕn ≈ 1.441nlog₂ n, where ϕ is the golden ratio, reported by Fraenkel and Simpson [TCS 1999] obtained via the Three Squares Lemma.

Related

• Counting Lyndon Subsequences
• A proof that a word of length n has less than 1.5n distinct squares
• How many double squares can a string contain?
• The Simplest Binary Word with Only Three Squares
• Counting Lyndon factors