In number theory, specifically the study of Diophantine approximation, the lonely runner conjecture is a conjecture about the long-term behavior of runners on a circular track. It states that n {\displaystyle n} runners on a track of unit length, with constant speeds all distinct from one another, will each be lonely at some time—at least 1 / n {\displaystyle 1/n} units away from all others. The conjecture was first posed in 1967 by German mathematician Jörg Wills, in purely number-theoretic terms, and independently as a view-obstruction problem in 1974 by Thomas W. Cusick; its illustrative and now-popular formulation dates to 1998. The conjecture is known to be true for 13 {\displaystyle 13} runners or fewer, but the general case remains unsolved. Implications of the conjecture include solutions to view-obstruction problems and bounds on properties, related to chromatic numbers, of certain graphs.
Formulation
Consider n {\displaystyle n} runners on a circular track of unit length. At the initial time t = 0 {\displaystyle t=0} , all runners are at the same position and start to run; the runners' speeds are constant, all distinct, and may be negative. A runner is said to be lonely at time t {\displaystyle t} if they are at a distance (measured along the circle) of at least 1 / n {\displaystyle 1/n} from every other runner. The lonely runner conjecture states that each runner is lonely at some time, no matter the choice of speeds. This visual formulation of the conjecture was first published in 1998. In many formulations, including the original by Jörg M. Wills, some simplifications are made. The runner to be lonely is stationary at 0 (with zero speed), and therefore n − 1 {\displaystyle n-1} other runners, with nonzero speeds, are considered. The moving runners may be further restricted to positive speeds only: by symmetry, runners with speeds x {\displaystyle x} and − x {\displaystyle -x} have the same distance from 0 at all times, and so are essentially equivalent. Proving the result for any stationary runner implies the general result for all runners, since they can be made stationary by subtracting their speed from all runners, leaving them with zero speed. The conjecture then states that, for any collection v 1 , v 2 , … , v n − 1 {\displaystyle v_{1},v_{2},\dots ,v_{n-1}} of positive, distinct speeds, there exists some time t > 0 {\displaystyle t>0} such that
1 n ≤ frac ( v i t ) ≤ 1 − 1 n ( i = 1 , … , n − 1 ) , {\displaystyle {\frac {1}{n}}\leq \operatorname {frac} (v_{i}t)\leq 1-{\frac {1}{n}}\qquad (i=1,\dots ,n-1),}
where frac ( x ) {\displaystyle \operatorname {frac} (x)} denotes the fractional part of x {\displaystyle x} . Interpreted visually, if the runners are running counterclockwise, the middle term of the inequality is the distance from the origin to the i {\displaystyle i} th runner at time t {\displaystyle t} , measured counterclockwise. This convention is used for the rest of this article. Wills' conjecture was part of his work in Diophantine approximation, the study of how closely fractions can approximate irrational numbers: Dirichlet's approximation theorem (~1840) says that for every real number t {\displaystyle t} and positive integer n {\displaystyle n} , there exists an integer q ∈ { 1 , 2 , … , n − 1 } {\displaystyle q\in \{1,2,\dots ,n-1\}} such that the distance of t q {\displaystyle tq} to the nearest integer is ≤ 1 n {\displaystyle \leq {\frac {1}{n}}} . Wills asked if this result can be improved if one is allowed to replace { 1 , 2 , … , n − 1 } {\displaystyle \{1,2,\dots ,n-1\}} with another set of n − 1 {\displaystyle n-1} positive integers, and the lonely runner conjecture states that it cannot.
Implications
… excerpt ends here. Continue reading the full article.
