🔢 mathematics

The lonely runner conjecture holds for nine runners

This paper proves that the lonely runner conjecture is true for nine runners by refining the method previously used to establish the result for eight runners.

Original authors: Matthieu Rosenfeld

Published 2026-01-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matthieu Rosenfeld

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a circular running track. On this track, there are several runners, each with a different speed. Some run fast, some run slow, and none of them share the exact same speed.

The Lonely Runner Conjecture is a mathematical question about these runners. It asks: Is there ever a moment in time when every single runner is "lonely"?

In this context, "lonely" means that every runner is far away from everyone else. Specifically, if you imagine the track as a circle with a circumference of 1, a runner is lonely if they are at least $1/(k+1)$ distance away from every other runner (where $k$ is the number of runners). The conjecture claims that no matter how you choose the speeds, there will always be a specific moment in time when this happens for everyone simultaneously.

For a long time, mathematicians had proven this was true for groups of 3, 4, 5, 6, 7, and 8 runners. But for 9 runners, it remained a mystery.

The Breakthrough: Solving the Case for 9 Runners

In this paper, the author, Matthieu Rosenfeld, proves that the conjecture is indeed true for 9 runners.

Here is how he did it, explained through a simple analogy:

1. The "Impossible" Scenario

To prove the conjecture, the author uses a classic logic trick: Proof by Contradiction.
He starts by assuming the opposite: Suppose there is a group of 9 runners with specific speeds where they can never all be lonely at the same time.

If such a "bad" group of runners existed, their speeds would have to be very specific numbers. The paper uses a mathematical "fence" (a formula) to show that if this bad group exists, the product of their speeds cannot be too huge. It sets an upper limit on how big these numbers can be.

2. The "Divisibility" Detective Work

Next, the author acts like a detective looking for clues. He asks: If this "bad" group of runners exists, what numbers must their speeds be divisible by?

He uses a series of logical rules (called lemmas) to find that the speeds of these hypothetical runners must be divisible by a very long list of specific numbers (like 17, 19, 23, 29, etc., and even powers of numbers like 64 and 81).

Think of it like this: If you have a secret code (the product of the speeds), the author proves that this code must contain the "key" for 17, the "key" for 19, the "key" for 23, and so on.

3. The Contradiction

Here is where the magic happens.

The Upper Limit: The "fence" from step 1 says the total product of the speeds must be smaller than a certain huge number (let's call it $X$ ).
The Lower Limit: The "detective work" from step 2 says the product must be divisible by a list of numbers so large that their combined product is bigger than $X$ .

It's like saying: "This jar can only hold 100 marbles," but then proving that "The marbles inside must weigh enough to fill a jar that holds 200 marbles."

Since the product cannot be both smaller than $X$ and larger than $X$ at the same time, the initial assumption must be wrong. There is no such "bad" group of 9 runners. Therefore, the Lonely Runner Conjecture must be true for 9 runners.

The Role of Computers

You might wonder, "How did he check all those numbers?"
The paper admits that checking every possible combination of speeds by hand is impossible. The author wrote a specialized computer program to do the heavy lifting.

The Problem: The computer had to check if certain complex patterns of numbers could "cover" a track without leaving a gap (a "lonely" spot).
The Innovation: The author didn't just use standard computer solvers (which are like using a sledgehammer to crack a nut). He built a custom, highly efficient "backtracking" algorithm.
- Imagine trying to find a path through a maze. Instead of walking every single path, his program is smart enough to realize, "If I turn left here, I'll hit a dead end 10 steps later, so I won't even bother walking that far."
- This optimization made the computer run much faster than previous attempts, cutting the time for similar problems from 32 hours down to 50 minutes.

What About 10 Runners?

The paper briefly mentions that while the method could theoretically work for 10 runners, the math gets incredibly difficult. The "fence" gets much higher, and the computer would need to check numbers so large that it would take a single computer core about two years to finish the job.

The author notes that another researcher independently solved the 10-runner case using a slightly different, faster "sieving" method, but this paper focuses strictly on the proof for 9 runners and the specific improvements made to the logic and code to get there.

Summary

In short, this paper solves a decades-old puzzle for 9 runners by:

Assuming a "bad" group of runners exists.
Proving that such a group would require numbers that are mathematically impossible (too big to fit in the allowed space).
Using a clever, custom-built computer program to verify the mathematical rules that lead to this contradiction.

The result confirms that on any track with 9 runners of different speeds, there is always a moment when everyone is perfectly alone.

Technical Summary: The Lonely Runner Conjecture for Nine Runners

Problem Statement
The paper addresses the Lonely Runner Conjecture, a longstanding open problem in combinatorial number theory first proposed by Wills in 1967. The conjecture posits that for any integer $k \ge 1$ and any set of $k$ distinct integers (representing runner speeds) $v_1, \dots, v_k$ , there exists a real time $t$ such that every runner is "lonely." Mathematically, this means there exists a $t$ where the distance of each runner from the origin on a unit circle is at least $1/(k+1)$ , expressed as $\|t v_i\| \ge 1/(k+1)$ for all $i$ .

While the conjecture has been verified for small values of $k$ (up to $k=7$ ), it remains open in the general case. This paper specifically targets the case of nine runners ( $k=9$ ).

Methodology
The proof strategy builds upon the author's previous work establishing the conjecture for eight runners. The core argument relies on a proof by contradiction involving the properties of a hypothetical "minimal counterexample."

Reduction to Divisibility Constraints:
The proof utilizes a bound derived by Malikiosis, Santos, and Schymura (Theorem 1), which implies that if the conjecture holds for $k$ , it holds for $k+1$ provided the product of speeds in any minimal counterexample exceeds a specific threshold. Consequently, to prove the conjecture for $k+1$ , it suffices to show that no set of $k$ speeds exists that violates the "lonely runner property" (LR property) while satisfying the divisibility constraints imposed by the bound.
Generalized Lemma for Divisors:
The authors introduce Lemma 6, a strengthened and generalized version of a previous lemma (Lemma 3). This lemma establishes conditions under which a specific integer $d$ must divide the product of the speeds of any set of 8 integers that lacks the LR property.
- The lemma introduces a coefficient $c$ and considers speeds modulo $9cd$.
- It incorporates specific divisibility conditions regarding the number of speeds divisible by 3 and 9 (derived from Lemma 5).
- The condition requires verifying that for any set of 8 speeds satisfying specific GCD and divisibility constraints, there exists a time $t$ satisfying the LR property.
Computer-Assisted Verification (Set Cover Reformulation):
Verifying the conditions of Lemma 6 is computationally intensive. The authors reformulate the problem as a set cover problem (Lemma 7).
- An integer $v$ "covers" an integer $j$ if $\| \frac{jv}{9cd} \| < 1/8$ .
- The goal is to verify that no "bad" 8-tuple exists that covers all necessary integers while satisfying the divisibility constraints.
- The authors implemented a backtracking algorithm with significant optimizations over their previous work for $k=7$ $k = 7$ :
  - Precomputed bitsets for covered positions.
  - Pruning strategies based on the maximum number of new integers a candidate element can cover.
  - Memoization to eliminate redundant search paths.
- The authors also tested SAT-solver approaches (using Cardinality-CDCL and Minicard) but found them significantly slower than their custom backtracking implementation for this specific problem structure.

Key Contributions and Results

Proof for Nine Runners: The paper provides a complete proof that the Lonely Runner Conjecture holds for $k=9$ .
Identification of Divisors: By applying Lemma 6 with a computer program, the authors identified a set $S$ of integers (including prime powers like $64, 81, 25$ and primes up to 191) that must divide the product of speeds in any minimal counterexample for 9 runners.
Contradiction: The product of the elements in set $S$ (which are pairwise coprime) is approximately $9.09 \times 10^{79}$ . However, the theoretical upper bound for the product of speeds in a minimal counterexample (derived from Corollary 2) is approximately $8.47 \times 10^{79}$ . Since the required product of divisors exceeds the maximum possible product of speeds, no such counterexample can exist.
Algorithmic Improvements: The paper details specific implementation improvements that reduced the runtime for the $k=7$ verification case from 32 hours to 50 minutes, enabling the more complex $k=9$ verification.

Significance and Claims
The authors state that this result extends the known range of the Lonely Runner Conjecture from 7 to 9 runners. They note that the technique used is theoretically applicable to any specific number of runners, though the computational cost grows rapidly.

Independence: The authors acknowledge that Trakulthongchai independently announced proofs for $k=9$ and $k=10$ shortly before this submission. Trakulthongchai's work also builds on the $k=7$ proof and utilizes a "clever sieving approach" that appears to be roughly 100 times faster than the method presented here.
Future Outlook: The paper discusses the feasibility of extending this to $k=10$ . While the method is adaptable, the computational cost for verifying primes up to roughly 263 is estimated to take two years on a single core. The authors suggest that combining their improvements (such as considering powers of small primes) with Trakulthongchai's sieving approach could make the $k=10$ case more tractable, but they do not claim to have solved it themselves.

In summary, the paper successfully resolves the $k=9$ case through a combination of refined theoretical lemmas and highly optimized computer verification, while modestly positioning the work as a step forward that benefits from and contributes to the broader effort to solve the conjecture for higher $k$ .