Lower Bounds for the Maximum Number of Runs in a String

by W. Matsubara, K. Kusano, A. Ishino, H. Bannai, A. Shinohara

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.029n, 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 k copies of t, contains 56733k - 18 runs for any k ≥ 2. Since |t^k| = 60064k, it yields the new lower bound 56733/60064 as k -> ∞.

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.

Known lower bound

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

Current lower bound

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

References

[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