On the Number of Rational Power Factors in a Finite Word

Abstract

Let $w$ be a finite word of length $n$. In this paper, we study the maximum possible number of distinct rational power factors in a finite word. A rational power is a word of the form $u=p^k{p}^{\prime }$, where $p$ is a nonempty finite word, $k$ is an integer larger than $1$, $p^k$ is a concatenation of $k$ copies of $p$ and $p^{\prime }$ is a prefix of $p$. The rational powers can be recognized as a generalization of $k$-powers, and it is proved in [Li,Pachocki,Radoszewski 24] that, the number $C_k(w)$ of distinct $k$-powers in $w$ satisfies $C_k(w)\le \frac{n-1}{k-1}$. However, the number of rational powers has not been studied in the literature. In this article, we prove that the number $\mathrm{RP}(w)$ of distinct rational power factors of $w$ satisfies $\mathrm{RP}(w)\le \frac{1}{8}{n}^2+O(n)$. We also illustrate a novel approach to study pattern-counting problems: using a graph-theoretic representation of words and a few word equations, we transform the traditional pattern-counting problems into a constrained extremal problem.

15 pages, comments are welcome