 | ||
In number theory, and especially the study of diophantine approximation, the lonely runner conjecture is a conjecture originally due to J. M. Wills in 1967. Applications of the conjecture are widespread in mathematics; they include view obstruction problems and calculating the chromatic number of distance graphs and circulant graphs. The conjecture was given its picturesque name by L. Goddyn in 1998.
Contents
Formulation
Consider k runners on a circular track of unit length. At t = 0, all runners are at the same position and start to run; the runners' speeds are pairwise distinct. A runner is said to be lonely at time t if they are at a distance of at least 1/k from every other runner at time t. The lonely runner conjecture states that each runner is lonely at some time.
A convenient reformulation of the conjecture is to assume that the runners have integer speeds, not all divisible by the same prime; the runner to be lonely has zero speed. The conjecture then states that for any set D of k − 1 positive integers with greatest common divisor 1,
where ||x|| denotes the distance of real number x to the nearest integer.
Known results
Dubickas shows that for a sufficiently large number of runners for speeds