A note on the maximum number of \(k\)-powers in a finite word

Shuo Li¹ ; Jakub Pachocki² ; Jakub Radoszewski³

¹Université du Québec à Montréal
²Open AI
³Institute of Informatics, University of Warsaw

The electronic journal of combinatorics, Tome 31 (2024) no. 3

Résumé

A power is a concatenation of $k$ copies of a word $u$, for a positive integer $k$; the power is also called a $k$-power and $k$ is its exponent. We prove that for any $k \ge 2$, the maximum number of different non-empty $k$-power factors in a word of length $n$ is between $\frac{n}{k-1}-\Theta(\sqrt{n})$ and $\frac{n-1}{k-1}$. We also show that the maximum number of different non-empty power factors of exponent at least 2 in a length-$n$ word is at most $n-1$. Both upper bounds generalize the recent upper bound of $n-1$ on the maximum number of different square factors in a length-$n$ word by Brlek and Li (2022).

Détail

DOI : 10.37236/11270

Classification : 68R15
Mots-clés : k-power, squares, finite words, exponent, Rauzy graph