On the number of \(k\)-powers in a finite word (Q2672960): Difference between revisions

In this short article, the first of a series, the author attempts to solve a conjecture by Fraenkel and Simpson concerning the number of different squares in a word. A (finite) word is a concatenation of symbols, each of them called a letter. A factor \(u\) of a word \(w\) is a contiguous concatenation of letters appearing in \(w\), e.g., \(na\) is a factor of \(ananas\). A square is a word of the form \(u^2 = uu\) with \(u\) a non-empty word, e.g., \(na^2 = nana\). Such a notion can be generalized to cubes, i.e., words of the form \(u^3 = uuu\), and to \(k\)-powers, i.e., words of the form \(u^k = uu \cdots u\), with \(u\) a non-empty word. It is also possible to define a \(k\)-power when \(k\) is a rational number by considering an entire power followed by a proper prefix of \(u\), e.g., \((an)^{5/2} = anana\). \textit{A. S. Fraenkel} and \textit{J. Simpson} [J. Comb. Theory, Ser. A 82, No. 1, 112--120 (1998; Zbl 0910.05001)] conjectured that, given a word \(w\), the number of distinct squares appearing as factors of \(w\) is bounded by \(|w|\), that is, the length of \(w\). The author considers several notions of combinatorics of words, mainly the ones of ``right-special factor'' and the so-called ``index'' (even though the author does not use this name in the paper). A factor \(u\) of \(w\) is right-special when there exist two distinct letters \(a\), \(b\) such that both \(ua\) and \(ub\) are factors of \(w\). The index of a word \(u\) in a word \(w\) is the maximal rational exponent \(i\) such that \(u^i\) is a factor of \(w\). Using these notions, the author proves his main result: The number of non-empty factors of a word \(w\) that are \(k\)-powers, denoted by \(N_k(w)\), is bounded by the ratio (\(w - |\operatorname{Alph}(w)|)/(k-2)\), where \(|\operatorname{Alph}(w)|\) denotes the number of distinct letters appearing in \(w\) (i.e., without their multiplicities). The boundary given in this note is not sharp. The author conjectures at the end of the contribution how it could be improved (and proves such a conjecture in a subsequent article). Nevertheless, the results given are a first step into the direction of solving Fraenkel and Simpson's conjecture.