Repetitions in strings is an important element in the analysis and processing of strings. It was shown in [Kolpakov and Kucherov, 1999] that when considering maximal repetitions, or runs, the maximum number of runs *RUNS*(*n*) in any string of length n is *O*(*n*), leading to a linear time algorithm for computing all the runs in a string. Although they were not able to give bounds for the constant factor, there have been several works to this end. The currently known best upper bound is *RUNS*(*n*) ≤ 1.029*n*, obtained by calculations based on the proof technique of [Crochemore and Ilie, 2007] and [Crochemore et al., 2008].

On the other hand, an asymptotic lower bound on *RUNS*(*n*) is presented in [Franek and Yang, 2006], where it is shown that for any *ε* > 0, there exists an integer *N* > 0 such that for any *n* > *N*, *RUNS*(*n*) ≥ (*α* - *ε*)*n*, where *α* = 3 / (1+√5) ≈ 0.927. It was conjectured in [Franek, et al., 2003] that this bound is optimal.

We proved that the conjecture was false, by showing a new lower bound *α* = 56733/60064 ≈ 0.944542. First we show a concrete string *t* of length 60064, which contains 56714 runs in it. It immediately disproves the conjecture, since 56714/60064 ≈ 0.944226 is already higher than the previous bound 0.927. Then we prove that the string *t** ^{k}*, which is the string obtained by concatenating

You can see the details in the conference paper:

Wataru Matsubara, Kazuhiko Kusano, Akira Ishino, Hideo Bannai and Ayumi Shinohara: New Lower Bounds for the Maximum Number of Runs in a string, Prague Stringology Conference 2008.

- Franek, Simpson, and Smyth 2003:
*RUNS*(*n*) ≥ 0.927*n*

- (t125),
*run*(*t*) = 110,*run*(*t*^{2}) = 227,*run*(*t*^{3}) = 343:*RUNS*(*n*) ≥ 0.928*n* - (t1558),
*run*(*t*) = 1455,*run*(*t*^{2}) = 2915,*run*(*t*^{3}) = 4374:*RUNS*(*n*) ≥ 0.93645*n* - (t60064),
*run*(*t*) = 56714,*run*(*t*^{2}) = 113448,*run*(*t*^{3}) = 170181:*RUNS*(*n*) ≥ 0.944542*n* - (t79568),
*run*(*t*) = 75136,*run*(*t*^{2}) = 150293,*run*(*t*^{3}) = 225449:*RUNS*(*n*) ≥ 0.944551*n* - (t105405),
*run*(*t*) = 99541,*run*(*t*^{2}) = 199103,*run*(*t*^{3}) = 298664:*RUNS*(*n*) ≥ 0.944557*n* - (t176583),
*run*(*t*) = 166772,*run*(*t*^{2}) = 333566,*run*(*t*^{3}) = 500359:*RUNS*(*n*) ≥ 0.944559*n* - (t139632),
*run*(*t*) = 131869,*run*(*t*^{2}) = 263761,*run*(*t*^{3}) = 395652:*RUNS*(*n*) ≥ 0.944561*n* - (t184973),
*run*(*t*) = 174697,*run*(*t*^{2}) = 349417,*run*(*t*^{3}) = 524136:*RUNS*(*n*) ≥ 0.944565*n* - (t29196442),
*run*(*t*) = 27578213,*run*(*t*^{2}) = 55156462,*run*(*t*^{3}) = 82734710:*RUNS*(*n*) ≥ 0.944575*n*[Puglisi and Simpson]

[Kolpakov and Kucherov, 1999] Kolpakov, R., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: Proc. 40th Annual Symposium on Foundations of Computer Science (FOCS'99). (1999) 596-604

[Crochemore and Ilie, 2007] Crochemore, M., Ilie, L.: Maximal repetitions in strings. J. Comput. Syst. Sci. 74 (2008) 796-807

[Crochemore, et al., 2008] Crochemore, M., Ilie, L., and Tinta, L.:Towards a Solution to the ''Runs'' Conjecture. In Proc. 19th Annual Symposium on Combinatorial Pattern Matching (CPM'08). (2008) 290-302

[Franek and Yang, 2006] Franek, F., Yang, Q.: A asymptotic lower bound for the maximal-number-of-runs functions. In Proc. Prague Stringology Conference (PSC'06). (2006) 3-8

[Franek, et al., 2003] Franek, F., Simpson, R., Smyth, W.: The maximum number of runs in a string. In: Proc. 14th Australasian Workshop on Combinatorial Algorithms (AWOCA2003). (2003) 26-35