The lonely runner conjecture holds for eight runners

Basic Information

• Paper ID: 2509.14111
• Title: The lonely runner conjecture holds for eight runners
• Author: Matthieu Rosenfeld (LIRMM, Univ Montpellier, CNRS, Montpellier, France)
• Classification: math.CO cs.DM math.NT
• Publication Date: October 17, 2025
• Paper Link: https://arxiv.org/abs/2509.14111

Abstract

This paper proves that the lonely runner conjecture holds for the case of eight runners. The proof relies on computer verification and recent results that allow bounding the size of minimal counterexamples. The author notes that the method applies equally to the known cases of 4, 5, 6, and 7 runners, and expects that minor improvements to the method would suffice to resolve the cases of 9 or 10 runners.

Research Background and Motivation

Problem Definition

The lonely runner conjecture is a famous open problem in combinatorial number theory and Diophantine approximation, originally proposed by Wills in 1965 in pure number-theoretic form. The runner interpretation of the conjecture is as follows: Consider k+1 runners with distinct constant velocities running on a unit-length circular track. The lonely runner conjecture asserts that for any runner, there exists a moment when that runner is at distance at least 1/(k+1) from all other runners.

Mathematical Formulation

Conjecture 1 (Lonely Runner Conjecture): For all integers k≥1, for every set of distinct integers v₁,...,vₖ₊₁, for all i, there exists a real number t such that for each j, $\|tv_i - tv_j\| \geq \frac{1}{k+1}$

where ‖x‖ denotes the distance from x to the nearest integer.

Research Significance

1. Theoretical Importance: The conjecture connects multiple branches of mathematics including combinatorial number theory, Diophantine approximation, and visibility obstruction problems
2. Computational Challenge: Verification difficulty grows exponentially with the number of runners
3. Applied Value: Has important applications in graph theory, number theory, and combinatorial optimization

Existing Research Progress

• k=2: Trivial case
• k=3: Solved by Betke and Wills, and by Cusick
• k=4: First proved via computer-assisted proof, later simplified
• k=5: Proved by Bohman, Holzman, and Kleitman
• k=6: Established by Barajas and Serra
• k=7: The case proved in this paper

Core Contributions

1. Main Result: Proves the lonely runner conjecture for eight runners (k=7)
2. Unified Method: Proposes a unified proof framework applicable to all cases k=4,5,6,7
3. Computational Techniques: Develops efficient computational verification algorithms using backtracking and pruning
4. Theoretical Tools: Establishes Lemma 6, providing a systematic method for finding prime factors in potential counterexamples
5. Extensibility: Provides a feasible technical path for resolving the k=8,9 cases

Detailed Methodology

Core Strategy

The proof employs proof by contradiction combined with computational verification:

1. Assume the existence of a counterexample for k=7
2. Use results by Malikiosis et al. to bound the product of velocities in the counterexample
3. Through computational verification, prove that the velocity product must be divisible by certain primes
4. Show that the product of these primes exceeds the upper bound, yielding a contradiction

Key Theoretical Results

Theorem 2 (Malikiosis-Santos-Schymura Bound): If the lonely runner conjecture holds for k, then for all k-tuples satisfying gcd(v₁,...,vₖ)=1 and $\sum_{S\subseteq\{1,...,k\}} \gcd(\{v_i : i \in S\}) > \binom{k+1}{2}^{k-1}$ the conjecture also holds for k+1.

Corollary 3: If the lonely runner conjecture holds for k, then for all k-tuples satisfying gcd(v₁,...,vₖ)=1 and $\prod_{i\in\{1,...,k\}} v_i \geq \left[\frac{\binom{k+1}{2}^{k-1}}{k}\right]^k$ the conjecture also holds for k+1.

Method for Finding Prime Factors

Lemma 4: If {v₁,...,vₖ} does not have the LR property, then lcm(2,...,k+1) divides ∏vᵢ.

Lemma 6 (Core Tool): Let k≥3 and assume the lonely runner conjecture holds for k-1. Let p∈ℕ be a positive integer. If for all v₁,...,vₖ∈{0,...,(k+1)p-1} satisfying certain conditions there exists a suitable t, then for any k-tuple {v₁,...,vₖ} without the LR property, p divides ∏vᵢ.

Computational Verification Algorithm

Problem Transformation: Convert the verification of Lemma 6 into a set cover problem:

• Define "coverage" relation: v covers j if and only if ‖jv/((k+1)p)‖ < 1/(k+1)
• Search for whether there exists a "bad" coverage violating the conditions of Lemma 6

Optimization Techniques:

1. Precompute coverage relations using bitsets for storage
2. Backtracking algorithm for constructing k-tuples with timely pruning
3. Exploit symmetry to reduce search space
4. Prioritize processing the most difficult-to-cover elements

Experimental Setup

Computational Verification Parameters

For the k=7 case:

• Upper bound: P ≤ 7.4×10⁵⁴
• Verification prime set S = {31, 37, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163}
• Verification for the largest prime p=163 requires approximately 32 hours of computation

Implementation Details

• Programming Language: C++
• Key Data Structure: Bitsets for efficient bitwise operations
• Algorithm: Backtracking search with pruning
• Computational Platform: Single processor core

Experimental Results

Main Results

Theorem 1: For all sets of integers {v₁,...,v₇} of size 7, there exists a real number t such that for all i, ‖tvᵢ‖ ≥ 1/8.

Proof Process

1. Upper Bound Calculation: From Corollary 3, P < 7.4×10⁵⁴
2. Lower Bound Construction:
   • From Lemma 4: P is divisible by lcm({2,3,4,5,6,7,8})
   • From computational verification: P is divisible by all primes in set S
   • Therefore P is divisible by lcm({2,3,4,5,6,7,8}∪S) ≈ 1.82×10⁵⁵
3. Contradiction: The lower bound exceeds the upper bound, so no counterexample exists

Extended Results

The author proves that the same method applies to cases k=3,4,5,6:

Related Work

Historical Development

1. Wills (1965): First proposed the number-theoretic form of the conjecture
2. Cusick: Proposed the equivalent formulation in terms of visibility obstruction
3. Goddyn: Provided the runner interpretation and current name
4. Tao (2019): Proved the existence of a computable constant such that finite verification suffices to determine the conjecture

Partial Results

• Gap Sequences: The conjecture holds for sequences with sufficiently large gaps
• Dubickas Result: The conjecture holds when vⱼ₊₁/vⱼ ≥ 1 + 8e log k/k
• Improvement in This Paper: Reduces the constant to 3e

Conclusions and Discussion

Main Conclusions

1. The lonely runner conjecture holds for eight runners
2. Provides a unified proof framework applicable to multiple cases
3. Develops scalable computational verification methods

Limitations

1. Computational Complexity: As k increases, the required primes p grow larger, and computation time increases exponentially
2. Computational Dependence: Key steps of the proof require extensive computational verification
3. Scalability Challenges: Cases k=8,9 require greater computational resources

Future Directions

1. Algorithm Optimization: Use more advanced solvers to replace the current backtracking algorithm
2. Theoretical Improvements: Seek variants of Lemma 6 or stronger pruning conditions
3. General Proof: Explore whether a theoretical proof exists that holds for all k

In-Depth Evaluation

Strengths

1. Important Breakthrough: First proof of the k=7 case, representing significant progress in the field
2. Methodological Innovation: Clever combination of theoretical bounds and computational verification
3. Solid Technique: Well-designed and thoroughly optimized computational verification algorithms
4. Unified Framework: Provides a general method for handling multiple cases
5. Open Source Implementation: Provides complete code implementation for verification and extension

Weaknesses

1. Computational Dependence: Proof heavily relies on computer verification, lacking the elegance of pure theoretical proof
2. Extension Limitations: Computational complexity of the method restricts extension to larger k values
3. Constant Optimization: Theoretical bounds may not be sufficiently tight, leaving room for improvement

Impact

1. Academic Contribution: Provides new approaches to solving a long-standing open problem
2. Computational Mathematics: Exemplifies the combination of theory and computation in solving difficult problems
3. Subsequent Research: Provides technical foundation for cases k≥8

Applicable Scenarios

This method is applicable to:

1. Similar problems in combinatorial number theory
2. Mathematical conjectures requiring finite verification
3. Problems in computational number theory and Diophantine approximation

References

The paper cites 23 related references, covering the historical development, theoretical progress, and computational methods of the lonely runner conjecture, providing readers with a complete research background.

Technical Assessment: This is a high-quality mathematics paper that successfully resolves a long-standing difficult open problem through innovative theoretical analysis and carefully designed computational verification. While dependent on computational verification, the method is rigorous and reliable, establishing an important foundation for further development in the field.