On the number of squares in a finite word

2022/04/21 by Brlek, Srečko, Li, Shuo · 2 citations
#68R10 #68R15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2204.10204

Abstract

A \em square is a word of the form uu. In this paper we prove that for a given finite word w, the number of distinct square factors of w is bounded by |w|-|\Alphabet(w)|+1, where |w| denotes the length of w and |\Alphabet(w)| denotes the number of distinct letters in w. This result answers a conjecture of Fraenkel and Simpson stated in 1998.

Cited by

• Fast Computation of k-Runs, Parameterized Squares, and Other Generalised Squares
• Counting Distinct Square Substrings in Sublinear Time

Related

• On the number of k-powers in a finite word
• An upper bound of the number of distinct powers in binary words
• A proof that a word of length n has less than 1.5n distinct squares
• Words with the Maximum Number of Abelian Squares
• On infinite words avoiding a finite set of squares