An upper bound of the number of distinct powers in binary words

2022/09/14 by Li, Shuo
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2209.06891

Abstract

A power is a word of the form \underbraceuu...u_{k times}, where u is a word and k is a positive integer and a square is a word of the form uu. Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a word is bounded by the length of the word. This conjecture was proven recently by Brlek and Li. Besides, there exists a stronger upper bound for binary words conjectured by Jonoska, Manea and Seki stating that for a word of length n over the alphabet \a, b\, if we let k be the least of the number of a's and the number of b's and k ≥ 2, then the number of distinct squares is upper bounded by (2k-1)/(2k+2)n. In this article, we prove this conjecture by giving a stronger statement on the number of distinct powers in a binary word.

Related

• A proof that a word of length n has less than 1.5n distinct squares
• On the number of k-powers in a finite word
• On the number of squares in a finite word
• New Bounds on Antipowers in Words
• Fewest repetitions in infinite binary words