The lonely runner conjecture holds for nine runners

Matthieu Rosenfeld · 2025

Read The lonely runner conjecture holds for nine runners by Matthieu Rosenfeld (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-01912.txt.

Introduction

The lonely runner conjecture is a puzzle from 1967 about runners on a circular track, each moving at a constant, different speed. It claims every runner eventually gets a clear gap from all the others. Matthieu Rosenfeld's 2025 paper proves the claim holds when there are nine runners.

The conjecture, first stated by Jörg Wills, is a known open problem in combinatorial number theory with several equivalent forms. Rosenfeld's proof sharpens the method he previously used to settle the eight-runner case, adding a couple of key improvements. Each new case brings the full conjecture, still unproven in general, a step closer.

Catalog record

CREATORMatthieu Rosenfeld
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-01912

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The lonely runner conjecture holds for nine runners Matthieu Rosenfeld Abstract We prove that the lonely runner conjecture holds for nine runners. Our proof is based on a couple of improvements of the method we used to prove the conjecture for eight runners. 1 Introduction The lonely runner conjecture, first stated by Wills in 1967 [ 21 , 22 ] , is a well-known open problem in combinatorial number theory with several applications and equivalent formulations [ 14 ] . The conjecture can be stated as follows. Conjecture 1 (Lonely Runner Conjecture) . For all integer k\geq 1 , every set of distinct integers v_{1},\ldots,v_{k+1} , and for all i , there exists a real number t such that for every j , we have \|tv_{i}-tv_{j}\|\geq\frac{1}{k+1}. This conjecture is still wide open in general, but has been established for small values of k : • k=3 the first non-trivial value [ 2 , 7 , 8 , 9 ] , • k=4 first resolved with computer aid [ 10 ] and later simplified [ 3 ] , • k=5 [ 6 , 16 ] , • k=6 [ 1 ] , • k=7 was recently solved with computer assistance by the author of the current article [ 18 ] . For a more detailed introduction to the lonely runner conjecture, we refer the reader to our previous article [ 18 ] or the recent survey by Perarnau [ 14 ] . In the current article we adapt our techniques from [ 18 ] to prove the case of nine runners. Note that a couple of days before the submission of the current article as a preprint, Trakulthongchai independently announced a proof for the cases of nine and ten runners [ 20 ] . The result of [ 20 ] also adapts the proof from [ 18 ] . The organization of the article is as follows. In Section 2, we recall the core of the argument from [ 18 ] . In Section 3, we provide our main lemma and use it to prove the lonely runner conjecture for nine runners. We discuss in Section 4 some implementation details of the computer verification. Finally, in the conclusion, we discuss possible improvement, we discuss an attempt of using Sat-solver, and we provide a short comparison with [ 20 ] . 2 The core of the argument from [ 18 ] The core of our argument relies on the following bound by Malikiosis, Santos and Schymura [ 13 ] . Theorem 1 ( [ 13 , Theorem A] ) . If the lonely runner conjecture holds for k , then it holds for k+1 for all k -tuple v_{1},\ldots,v_{k} such that \gcd(v_{1},\ldots,v_{k})=1 , and \sum_{S\subseteq\{1,\ldots,k\}}\gcd(\{v_{i}:i\in S\})>\binom{k+1}{2}^{k-1}. In [ 18 ] , we used the following corollary to bounds the product of the speeds in any minimal counter-example for k runners. Corollary 2 ( [ 18 ] ) . If the lonely runner conjecture holds for k , then it holds for k+1 for all k -tuple v_{1},\ldots,v_{k} such that \gcd(v_{1},\ldots,v_{k})=1 , and \prod_{i\in\{1,\ldots,k\}}v_{i}\geq\left[\frac{\binom{k+1}{2}^{k-1}}{k}\right]^{k}\,. Now the proof relies on finding many small prime divisors of the product of the speeds in any minimal counterexample for k runners. With enough such divisors, we get a lower bound on the product that is larger than the upper bound given in Corollary 2 , implying that there is no such counterexample. The following lemmas from [ 18 ] allow to find such divisors. Lemma 3 ( [ 18 ] ) . Let k\geq 3 be an integer such that the lonely runner conjecture holds for k-1 . Let p\in\mathbb{N} be a positive integer such that for all v_{1},\ldots,v_{k}\in\{0,\ldots,(k+1)p-1\} with (i) for all subset S\in\{v_{1},\ldots,v_{k}\} of size k-1 , we have \gcd(S\cup\{(k+1)p\})=1 , (ii) for all i , v_{i} is not divisible by p , there exists t\in\{0,\ldots,(k+1)p-1\} such that for all i , \left\|\frac{tv_{i}}{(k+1)p}\right\|\geq\frac{1}{k+1}\,. Then for any set of k distinct integers \{v_{1},\ldots,v_{k}\} that does not have the LR property, we have p\text{ divides }\prod_{i\in\{1,\ldots,k\}}v_{i}. For each prime p , a finite computation can be used to verify the condition of this lemma. Since, many primes happen to satisfy this condition when k=7 , we can verify the existence of many prime that must divide the produce of the speed of a minimal counterexample. With enough such primes, one can contradict the upper bound on the product of the speeds given by Corollary 2 and prove the lonely runner conjecture for k+1 runners. This proof of this lemma relied on the following lemma (the same idea was already used in [ 3 ] ). Lemma 4 ( [ 18 ] ) . Let k\geq 3 be an integer such that the lonely runner conjecture holds for k-1 . Let v_{1},\ldots,v_{k} be a set of integers with \gcd(\{v_{1},\ldots,v_{k}\})=1 but \gcd(v_{1},\ldots,v_{k-1})\not=1 . Then v_{1},\ldots,v_{k} has the LR property. For the current article, we will use a stronger version of Lemma 5 given in Lemma 6 . For this, we provide a version of Lemma 4 tailored for the case k=8 with more general conditions. Hence, Lemma 6 is also tailored to the case k=8 which allows a weaker condition (i.e., we have fewer k -uples to verify). At the same time, we also generalize a bit the conditions of the lemma by adding a coefficient c that allows to apply our lemma to powers of small primes as well. 3 Proof of the lonely runner conjecture for nine runners We now provide our version of Lemma 4 tailored for k=8 . The proof is similar to the proof of Lemma 4 given in [ 18 ] . Lemma 5 . Let k\geq 3 be an integer such that the lonely runner conjecture holds for all k^{\prime}<k . Let v_{1},\ldots,v_{8} be a set of integers with \gcd(\{v_{1},\ldots,v_{8}\})=1 then • if at least 6 of the v_{i} are divisible by 3 , then \{v_{1},\ldots,v_{9}\} has the LR property, • if at least 5 of the v_{i} are divisible by 9 , then \{v_{1},\ldots,v_{9}\} has the LR property. Proof. We start with the first item, and we assume that at least 6 of the v_{i} are divisible by 3 . By the \gcd condition at least one of the v_{i} is not divisible by 3 and by Lemma 4 , if exactly one of them is not divisible by 3 then the set has the LR property, so the only remaining case is when exactly 6 of the v_{i} are divisible by 3 . By reordering the v_{i} , we can assume that v_{1},\ldots,v_{6} are divisible by 3 and v_{7} and v_{8} are not divisible by 3 . Let t be a lonely runner solution for \{v_{1},\ldots,v_{6}\} , that is, for all i\in\{1,\ldots,6\} , \left\|v_{i}\cdot t\right\|\geq\frac{1}{7}>\frac{1}{9}\,. Hence, for all t^{\prime}\in\{t,t+1/3,t+2/3\} and for all i\in\{1,\ldots,6\}, \left\|v_{i}\cdot t^{\prime}\right\|=\left\|v_{i}\cdot t\right\|>\frac{1}{k+1}\,. On the other hand, for i\in\{7,8\} , \gcd(v_{i},3)=1 , and we have \left\{\left\|v_{i}\cdot(t+j/3)\right\|:j\in\{0,1,2\}\right\}=\left\{\left\|v_{i}\cdot t+j/3\right\|:j\in\{0,1,2\}\right\}\,. For each i\in\{7,8\} , this set corresponds to 3 points evenly spaced out in the unit circle, hence for each i\in\{7,8\} at most one of this point is such that \left\|v_{i}\cdot(t+j/3)\right\|<1/9 (this corresponds to an interval of size 2/9<1/3 ). That is at most two of the three choices of

Read the complete text