Lonely runner conjecture
Encyclopedia
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 graph
s. The conjecture was given its picturesque name by L. Goddyn in 1998.
A convenient reformulation of the problem 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 positive integers with gcd
1, there exists a real t such that
where ||x|| denotes the distance of real number x to the nearest integer.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, and especially the study of diophantine approximation
Diophantine approximation
In number theory, the field of Diophantine approximation, named after Diophantus of Alexandria, deals with the approximation of real numbers by rational numbers....
, the lonely runner conjecture is a conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
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 graph
Circulant graph
In graph theory, a circulant graph is an undirected graph that has a cyclic group of symmetries that includes a symmetry taking any vertex to any other vertex.-Equivalent definitions:Circulant graphs can be described in several equivalent ways:...
s. The conjecture was given its picturesque name by L. Goddyn in 1998.
The conjecture
Consider k + 1 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 if at distance of at least 1/(k + 1) from each other runner. The lonely runner conjecture states that every runner gets lonely at some time.A convenient reformulation of the problem 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 positive integers with gcd
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
1, there exists a real t such that
where ||x|| denotes the distance of real number x to the nearest integer.
Known results
| k | year proved | proved by |
|---|---|---|
| 3 | 1972 | Betke and Wills; Cusick |
| 4 | 1984 | Cusick and Pomerance; Bienia et al. |
| 5 | 2001 | Bohman, Holzman, Kleitman; Renault |
| 6 | 2008 | Barajas and Serra |