On the number of $k$-powers in a finite word

Given a finite word, the problem of counting the number of distinct squares was introduced by Fraenkel and Simpson. In [4] they conjectured that the number of distinct squares in a finite word $w$ is bounded by its length $|w|$ and they proved that this number is bounded by $2|w|$. After that Ilie [5] strengthened this bound to $2|w|-\Theta(n)$; Lam [6] improved this result to $\frac{95}{48}|w|$; Deza, Franek and Thierry [2] achieved a bound of $\frac{11}{6}|w|$; Thierry [7] refined this bound to $\frac{3}{2}n$. A basic fact about the square-counting problem is that no more than two squares can have their last occurrence starting at the same position, this fact is proved in [4] using the three squares lemma of Crochemore and Rytter [1]. After that, the ideas of improving the bound of distinct squares in a finite word are about counting the number of positions at which there exist two different squares having their last occurrence starting. In this article, instead of studying the same motif, we propose to consider the number of special factors. The idea is from the fact that (almost) every occurrent factor can be associated with a (right-)special factor. Even though we can not achieve an injection from the set of squares to the set of special factors in the finite word. This correspondence leads an upper bound of the number of $k$-powers in the given word. The main result of this note is announced as follows:

Let us recall the basic terminology about words. By word we mean a finite concatenation of symbols $w=w_{1}w_{2}\cdots w_{n}$, with $n\in\mathbb{N}$. The length of $w$, denoted $|w|$, is $n$ and we say that the symbol $w_{i}$ is at position $i$. The set $\hbox{\rm Alph}(w)=\left\{w_{i}|1\leq i\leq n\right\}$ is called the alphabet of $w$ and its elements are called letters. Let $|\hbox{\rm Alph}(w)|$ denote the cardinality of $\hbox{\rm Alph}(w)$. A word of length $0$ is called the empty word and it is denoted by $\varepsilon$. For any word $u$, we have $u=\varepsilon u=u\varepsilon$. Let $u,v$ be two different words, we say $a$ is shorter (resp. longer) than $b$ if $|a|<|b|$ (resp. $|a|>|b|$).

A word $u$ is called a factor of $w$ if $w=pus$ for some words $p,s$. When $p=\varepsilon$ (resp. $s=\varepsilon$) $u$ is called a prefix (resp. suffix) of $w$. The set of all factors (resp. prefixes, resp. suffixes) of $w$ is denoted by $\hbox{\rm Fac}(w)$ (resp. $\hbox{\rm Pref}(w)$, resp. $\hbox{\rm Suff}(w)$). For any integer $i$ satisfying $1\leq i\leq|w|$, let $C_{w}(i)$ denote the number of distinct factors of length $i$ in $w$.

A factor $u$ of $w$ is called right-special if there exist two different letters $a,b\in\hbox{\rm Alph}(w)$ such that $ua$ and $ub$ are both factors of $w$. $ua,ub$ are called right-extensions of $u$.

For any natural number $k$, the $k$-th power of a finite word $u$ is denoted by $u^{k}=uu\cdots u$ and consists of the concatenation of $k$ copies of $u$. A finite word $w$ is said to be primitive if it is not a power of another word, that is if $w=u^{k}$ implies $k=1$. Let $\hbox{\rm Prim}(w)$ denote the set of all primitive factors of $w$. A $k$-power is a word $w$ satisfying $w=\underbrace{uu...u}_{k\;\text{tilmes}}$ for a certain $u\in\hbox{\rm Fac}(w)$ and for a $k\geq 2$. Let $N_{k}(w)$ denote the number of its distinct non-empty $k$-powers. For a given word $w$ and two positive integers $a,b$ satisfying $a\leq b=|w|$, let us define $w^{\frac{a}{b}}$ to be the prefix of $w$ of length $a$. Now we can define the rational power a word: let $w$ be a finite word and let $\frac{a}{b}\in\mathbb{Q}^{+}$ be a positive rational number, $w^{\frac{a}{b}}$ is well defined only if $b=|w|$, and in this case, there is a couple of non-negative integers $(c,d)$ satisfying $a=c|w|+d$, we define $w^{\frac{a}{b}}$ to be $w^{c}w^{\frac{d}{b}}$. For a given word $w$ and a given integer $k$, we say that $w$ is of period $k$ if there exists a word $u$ of length $k$ such that $w=u^{\frac{|w|}{k}}$.

Here we recall a basic lemma concerning the repetitions:

Let $w$ be a finite word. In this section, we consider the word $w^{*}$ obtained by concatenating a special letter $*$ at the end of $w$, with the condition that $*\not\in\hbox{\rm Alph}(w)$.

For any $u\in\hbox{\rm Fac}(w)$, let us define $m_{w}(u)=\max\left\{i|u^{i}\in\hbox{\rm Fac}(w),i\in\mathbb{Q}^{+}\right\}$, and similarly, let us define $m_{w^{*}}(u)=\max\left\{i|u^{i}\in\hbox{\rm Fac}(w^{*}),i\in\mathbb{Q}^{+}\right\}$. There are the following facts between $m_{w}(u)$ and $m_{w^{*}}(u)$:

1) For any factor $u\in\hbox{\rm Fac}(w)$, $m_{w}(u)=m_{w^{*}}(u)\geq 1$;

2) If $u\in\hbox{\rm Fac}(w^{*})$ but $u\not\in\hbox{\rm Fac}(w)$, $m_{w^{*}}(u)=1$.

For any factor $u\in\hbox{\rm Fac}(w)$, let us define $m(u)=m_{w}(u)=m_{w^{*}}(u)$. For any integer $i$ satisfying $1\leq i\leq m(u)$, let us define $u(i)$ to be the shortest suffix of $u^{m(u)}$ containing $u^{i}$ as a prefix.

The result obtained in the main theorem is not sharp. Let us consider the word $w=aaa$, it is easy to check that $N_{3}(w)=1$ while the bound given in Theorem 1 is $2$. The author believes that the problem is from the way we count the number of right-special factors. From Lemme 4 we prove that for a given primitive $u$, all $u(i)$ are right-special if $1\leq i\leq m(u)-1$. However, in Lemma 6 we count just the $u(i)$ for $2\leq i\leq m(u)-1$. In fact, we can only prove that the words of the form $u(i)$ are pairwisely different when $i\geq 2$. Meanwhile, we can have two different primitives $u,v$ such that $u(1)=v(i)$ for some positive integer $i$. Thus, further work to to be done to investigate that

If the previous inequality holds, we may expect to prove