Bounds on Powers in Strings

We show a i¾? ( n log n ) bound on the maximal number of occurrences of primitively-rooted k -th powers occurring in a string of length n for any integer k , k i¾? 2. We also show a i¾? ( n 2) bound on the maximal number of primitively-rooted powers with fractional exponent e , 1 e n . This result holds obviously for their maximal number of occurrences. The first result contrasts with the linear number of occurrences of maximal repetitions of exponent at least 2.