Lonely runner conjecture

Slight improvements on the lower bound ${\displaystyle 1/(2n-2)}$ are known. Chen & Cusick (1999) showed for ${\displaystyle n\geq 5}$ that if ${\displaystyle 2n-5}$ is prime, then ${\displaystyle \delta _{n}\geq {\tfrac {1}{2n-5}}}$, and if ${\displaystyle 4n-9}$ is prime, then ${\displaystyle \delta _{n}\geq {\tfrac {2}{4n-9}}}$. Perarnau & Serra (2016) showed unconditionally for sufficiently large ${\displaystyle n}$ that

$${\displaystyle \delta _{n}\geq {\frac {1}{2n-4+o(1)}}.}$$

Tao (2018) proved the current best known asymptotic result: for sufficiently large ${\displaystyle n}$,

$${\displaystyle \delta _{n}\geq {\frac {1}{2n-2}}+{\frac {c\log n}{n^{2}(\log \log n)^{2}}}}$$

for some constant ${\displaystyle c>0}$. He also showed that the full conjecture is implied by proving the conjecture for integer speeds of size ${\displaystyle n^{O(n^{2})}}$ (see big O notation). This implication theoretically allows proving the conjecture for a given ${\displaystyle n}$ by checking a finite set of cases, but the number of cases grows too quickly to be practical.[14]

The conjecture has been proven under specific assumptions on the runners' speeds. For sufficiently large ${\displaystyle n}$, it holds true if

$${\displaystyle {\frac {v_{i+1}}{v_{i}}}\geq 1+{\frac {22\log(n-1)}{n-1}}\qquad (i=1,...,n-2).}$$

In other words, the conjecture holds true for large ${\displaystyle n}$ if the speeds grow quickly enough. If the constant 22 is replaced with 33, then the conjecture holds true for ${\displaystyle n\geq 16343}$.[15] A similar result for sufficiently large ${\displaystyle n}$ only requires a similar assumption for ${\displaystyle i=\lfloor n/22\rfloor -1,...,n-2}$.[14] Unconditionally on ${\displaystyle n}$, the conjecture is true if ${\displaystyle v_{i+1}/v_{i}\geq 2}$ for all ${\displaystyle i}$.[16]

The conjecture is true for ${\displaystyle n\leq 7}$ runners. The proofs for ${\displaystyle n\leq 3}$ are elementary; the ${\displaystyle n=4}$ case was established in 1972.[17] The ${\displaystyle n=5}$, ${\displaystyle n=6}$, and ${\displaystyle n=7}$ cases were settled in 1984, 2001 and 2008, respectively. The first proof for ${\displaystyle n=5}$ was computer-assisted, but all cases have since been proved with elementary methods.[18]

For some ${\displaystyle n}$, there exist sporadic examples with a maximum separation of ${\displaystyle 1/n}$ besides the example of ${\displaystyle v_{i}=i}$ given above.[6] For ${\displaystyle n=5}$, the only known example (up to shifts and scaling) is ${\displaystyle \{0,1,3,4,7\}}$; for ${\displaystyle n=6}$ the only known example is ${\displaystyle \{0,1,3,4,5,9\}}$; and for ${\displaystyle n=8}$ the known examples are ${\displaystyle \{0,1,4,5,6,7,11,13\}}$ and ${\displaystyle \{0,1,2,3,4,5,7,12\}}$.[19] There exists an explicit infinite family of such sporadic cases.[20]

Kravitz (2021) formulated a sharper version of the conjecture that addresses near-equality cases. More specifically, he conjectures that for a given set of speeds ${\displaystyle v_{i}}$, either ${\displaystyle \delta =s/(s(n-1)+1)}$ for some positive integer ${\displaystyle s}$,[lower-alpha 4] or ${\displaystyle \delta \geq 1/(n-1)}$, where ${\displaystyle \delta }$ is that setup's gap of loneliness. He confirmed this conjecture for ${\displaystyle n\leq 4}$ and a few special cases.

Rifford (2022) addressed the question of the size of the time required for a runner to get lonely. He formulated a stronger conjecture stating that for every integer ${\displaystyle n\geq 3}$ there is a positive integer ${\displaystyle N}$ such that for any collection ${\displaystyle v_{1},v_{2},...,v_{n-1}}$ of positive, distinct speeds, there exists some time ${\displaystyle t>0}$ such that ${\displaystyle \operatorname {frac} (v_{i}t)\in [1/n,1-1/n]}$ for ${\displaystyle i=1,...n-1}$ with

$${\displaystyle t\leq {\frac {N}{\operatorname {min} (v_{1},...,v_{n-1})}}.}$$

Rifford confirmed this conjecture for ${\displaystyle n=3,4,5,6}$ and showed that the minimal ${\displaystyle N}$ in each case is given by ${\displaystyle N=1}$ for ${\displaystyle n=3,4,5}$ and ${\displaystyle N=2}$ for ${\displaystyle n=6}$. The latter result (${\displaystyle N=2}$ for ${\displaystyle n=6}$) shows that if we consider six runners starting from ${\displaystyle 0}$ at time ${\displaystyle t=0}$ with constant speeds ${\displaystyle v_{0},v_{1},...,v_{5}}$ with ${\displaystyle v_{0}=0}$ and ${\displaystyle v_{1},...,v_{5}}$ distinct and positive then the static runner is separated by a distance at least ${\displaystyle 1/6}$ from the others during the first two rounds of the slowest non-static runner (but not necessary during the first round).

A much stronger result exists for randomly chosen speeds: using the stationary-runner convention, if ${\displaystyle n}$ and ${\displaystyle \varepsilon >0}$ are fixed and ${\displaystyle n-1}$ runners with nonzero speeds are chosen uniformly at random from ${\displaystyle \{1,2,\ldots ,k\}}$, then ${\displaystyle P(\delta \geq 1/2-\varepsilon )\to 1}$ as ${\displaystyle k\to \infty }$. In other words, runners with random speeds are likely at some point to be "very lonely"—nearly ${\displaystyle 1/2}$ units from the nearest other runner.[21] The full conjecture is true if "loneliness" is replaced with "almost aloneness", meaning at most one other runner is within ${\displaystyle 1/n}$ of a given runner.[22] The conjecture has been generalized to an analog in algebraic function fields.[23]