Source-linked AI summary
The "Runs" Theorem
Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta
TL;DR
The runs conjecture asks whether the maximum number of runs in a length-n string is less than n, a question about a basic string characteristic with theoretical and practical applications. The paper connects run L-roots with the longest Lyndon word starting at each string position to characterize runs. The paper proves the runs conjecture and establishes σ(n) < 3n for the maximum sum of exponents of runs in a string of length n, improving the previous best bound of 4.1n.
Problem
Method
The paper connects run L-roots with the longest Lyndon word starting at each string position to characterize runs.
Source: §1 · p. 2Results
The paper proves the runs conjecture and establishes σ(n) < 3n for the maximum sum of exponents of runs in a string of length n, improving the previous best bound of 4.1n.
Source: §6 · p. 8Takeaways & Limitations
The characterization clarifies how runs occur and supports a linear-time algorithm for finding them and an optimal 2-Period Query solution.
Source: §1 · p. 2, §6 · p. 8The exact value of lim n→∞ ρ(n)/n remains unknown, although the limit is known to exist and is never reached.
Source: §6 · p. 8
Abstract
from arXiv · showhide
We give a new characterization of maximal repetitions (or runs) in strings based on Lyndon words. The characterization leads to a proof of what was known as the "runs" conjecture (Kolpakov \& Kucherov (FOCS '99)), which states that the maximum number of runs $\rho(n)$ in a string of length $n$ is less than $n$. The proof is remarkably simple, considering the numerous endeavors to tackle this problem in the last 15 years, and significantly improves our understanding of how runs can occur in strings. In addition, we obtain an upper bound of $3n$ for the maximum sum of exponents $\sigma(n)$ of runs in a string of length $n$, improving on the best known bound of $4.1n$ by Crochemore et al. (JDA 2012), as well as other improved bounds on related problems. The characterization also gives rise to a new, conceptually simple linear-time algorithm for computing all the runs in a string. A notable characteristic of our algorithm is that, unlike all existing linear-time algorithms, it does not utilize the Lempel-Ziv factorization of the string. We also establish a relationship between runs and nodes of the Lyndon tree, which gives a simple optimal solution to the 2-Period Query problem that was recently solved by Kociumaka et al. (SODA 2015).
1 Introduction
The paper uses Lyndon-word structure to prove the runs conjecture and derive tighter bounds on runs and their exponents. It also presents a linear-time algorithm that avoids Lempel–Ziv parsing and an optimal solution to the 2-Period Query problem.
1 Introduction
- Runs are maximal periodic intervals at least twice their smallest period, and the paper addresses how to extend Lyndon-based reasoning from cubic runs to general runs.Prior work’s argument for cubic runs relied on two consecutive L-root occurrences, a condition not guaranteed for general runs.Source: §1 · pp. 1–2
- The paper connects run L-roots to the longest Lyndon word starting at each position, yielding a simple proof that ρ(n)<n.Earlier bounds had not proved the conjecture, and previous analyses could require many cases.Source: §1 · pp. 1–2
- σ(n)<3n improves the previous best bound of 4.1n for the maximum sum of run exponents.Using ρ(n)<n in the earlier proof would only give a 4n bound.Source: §1 · p. 2
- For runs with exponent at least k≥2, ρk(n)<n/(k−1) and σk(n)<n(k+1)/(k−1); for k=3, σ3(n)<2n.The k=3 bound improves the previous 2.5n bound.Source: §1 · p. 2
- For strings with d distinct symbols, the paper proves ρ(n,d)≤n−d and, when n>2d, ρ(n,d)≤n−d−1.Here ρ(n,d) is the maximum number of runs in a length-n string containing exactly d distinct symbols.Source: §1 · p. 2
- The Lyndon-based characterization yields a conceptually simple linear-time algorithm for finding all runs without Lempel–Ziv parsing.Earlier linear-time algorithms relied on that parsing, which was their bottleneck.Source: §1 · p. 2
- The paper relates run L-roots to Lyndon-tree nodes and gives an optimal 2-Period Query solution with constant-time queries after O(n) preprocessing.A query returns the smallest period no greater than half the interval length, if one exists.Source: §1 · p. 2
2 Preliminaries
The preliminaries define runs through minimal-period repetition that cannot extend, then introduce their exponent and the paper’s counting measures. They also establish Lyndon words and L-roots as the structural objects used later.
Runs and periods
- A run has a smallest period p, length at least 2p, and periodicity that cannot extend left or right; its exponent is its length divided by p.A period requires characters p positions apart to match.Source: §2 · p. 3
Run measures
- ρ(n) is the maximum number of runs in a length-n string, while σ(n) is the maximum sum of their exponents.Source: §2 · p. 3
Lyndon words
- A Lyndon word is lexicographically smaller than each of its non-empty proper suffixes, and it cannot have a period shorter than its length.Source: §2 · p. 3
L-roots
- An L-root is a length-p Lyndon substring contained in a run of period p, and every run has at least one for any chosen lexicographic order.Source: §2 · p. 3
3 The Runs Theorem
Using Lyndon-word roots and two opposite lexicographic orders, the paper assigns disjoint starting positions to runs. This yields a strict linear bound on run counts and sharper bounds for high-exponent runs and strings with a fixed alphabet size.
3 The Runs Theorem
- ρ(n) < n: each run’s associated L-root starting positions are disjoint from those of every other run.The construction associates at least one such position with each run.Source: §3 · pp. 3–4
3.1 Higher Exponent Runs
- For runs with exponent at least k, σ_k(n) < n(k + 1)/(k −1), giving σ_3(n) < 2n.The passage identifies the earlier σ_3(n) bound as 2.5n.Source: §3.1 · p. 4
3.2 Runs with d distinct symbols
- With exactly d distinct symbols, ρ(n, d) ≤ n − d, and when n > 2d, ρ(n, d) ≤ n − d − 1.The latter yields ρ(n) ≤ n − 3 for n > 4.Source: §3.2 · pp. 4–5
4 New Linear-Time Algorithm for Computing All Runs
The paper gives a linear-time algorithm for finding all runs by computing Lyndon intervals under two orders and testing each candidate interval. Its stack-based computation and constant-time extension checks keep the overall procedure linear.
4 New Linear-Time Algorithm for Computing All Runs
- The algorithm computes all candidate Lyndon intervals in linear time, then tests each one in constant time to determine whether it identifies a run.Every run has an L-root among the computed intervals.Source: §4 · p. 5
4.1 Linear-Time Computation of lℓ(i)
- A right-to-left stack scan computes lℓ(i); the stack maintains the Lyndon factorization of the remaining suffix, whose first factor is the longest Lyndon word starting at i.Suffix-array ranks support the lexicographic comparisons in constant time.Source: §4.1 · p. 5
4.2 Computing All Runs of w from lℓ(i)
- For each candidate interval, longest common suffix and prefix queries determine its maximal extension, allowing the algorithm to test the run conditions in constant time per candidate.The passage specifies linear-time preprocessing for these queries.Source: §4 · p. 5, §4.2 · p. 6
5 Runs and Lyndon Trees
The paper relates runs to nodes in two Lyndon trees: for a suitable one of the two orders, each run’s L-root is a right node. This structure also yields a linear-space, constant-time 2-Period Query data structure.
5 Runs and Lyndon Trees
- For each run, an L-root under the appropriate one of two orders is a right node in that order’s Lyndon tree.A non-root interval is a right node exactly when it is the longest Lyndon word starting at its position.Source: §5 · p. 7
5.1 Application to 2-Period Queries
- 2-Period Queries can be answered in O(1) time using O(n) space after O(n) preprocessing by checking the right children of two lowest common ancestors.The queried period is the smallest period no greater than half the interval length, when one exists.Source: §5.1 · pp. 7–8
6 Conclusion
The paper connects runs to Lyndon words to prove the runs conjecture and establish bounds and algorithms for related problems. The exact limiting ratio of the maximum number of runs to string length remains unresolved.
6 Conclusion
- The Lyndon-word characterization proves the runs conjecture, ρ(n) < n, through a connection between runs’ L-roots and the longest Lyndon word starting at each position.Source: §6 · p. 8
- The maximum sum of run exponents satisfies σ(n) < 3n, improving the previous best bound of 4.1n.Source: §6 · p. 8
- The paper proposes a simple linear-time algorithm for computing all runs in a string.Source: §6 · p. 8
- The longest Lyndon word starting at each position corresponds to a right node in the Lyndon tree, yielding a simple optimal solution to the 2-Period Query problem.Source: §6 · p. 8
- The exact value of lim ρ(n)/n remains an open question, although the limit is known to exist and is never reached.Source: §6 · p. 8