On the number of k-powers in a finite word

2022/03/31 by Shuo Li, Li, Shuo
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2203.16742

openalex publication_date 2022/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This note is an attempt to attack a conjecture of Fraenkel and Simpson stated in 1998 concerning the number of distinct squares in a finite word. By counting the number of (right-)special factors, we give an upper bound of the number of \em k-powers in a finite word for any integer k≥ 3. By \em k-power, we mean a word of the form \underbraceuu...u_{k times}.

Related

• A note on the maximum number of k-powers in a finite word
• On the number of squares in a finite word
• An upper bound of the number of distinct powers in binary words
• New Bounds on Antipowers in Words
• A proof that a word of length n has less than 1.5n distinct squares