Lonely runner conjecture

Unsolved problem in mathematics:

Is the lonely runner conjecture true for every number of runners?

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 runners on a track of unit length, with constant speeds all distinct from one another, will each be lonely at some time—at least units away from all others.

The conjecture was first posed in 1967 by German mathematician Jörg M. Wills, in purely number-theoretic terms, and independently in 1974 by T. W. Cusick; its illustrative and now-popular formulation dates to 1998. The conjecture is known to be true for seven 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 edit

 
Example of a case of the conjecture with n=6 runners. Runners colored black have not yet been lonely. The white arcs, of length 2/n, indicate that a runner is currently lonely. Yellow runners have experienced loneliness.

Consider   runners on a circular track of unit length. At the initial time  , 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   if they are at a distance (measured along the circle) of at least   from every other runner. The lonely runner conjecture states that each runner is lonely at some time, no matter the choice of speeds.[1]

This visual formulation of the conjecture was first published in 1998.[2] In many formulations, including the original by Jörg M. Wills,[3][4] some simplifications are made. The runner to be lonely is stationary at 0 (with zero speed), and therefore   other runners, with nonzero speeds, are considered.[a] The moving runners may be further restricted to positive speeds only: by symmetry, runners with speeds   and   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   of positive, distinct speeds, there exists some time   such that

 
where   denotes the fractional part of  .[6] Interpreted visually, if the runners are running counterclockwise, the middle term of the inequality is the distance from the origin to the  th runner at time  , measured counterclockwise.[b] This convention is used for the rest of this article. Wills' conjecture was part of his work in Diophantine approximation,[7] the study of how closely fractions can approximate irrational numbers.

Implications edit

 
Squares of side length 1/3 placed at every half-integer coordinate obstruct any ray from the origin (besides those lying on an axis). Any smaller side length will leave small gaps.

Suppose   is a n-hypercube of side length   in n-dimensional space ( ). Place a centered copy of   at every point with half-integer coordinates. A ray from the origin may either miss all of the copies of  , in which case there is a (infinitesimal) gap, or hit at least one copy. Cusick (1973) made an independent formulation of the lonely runner conjecture in this context; the conjecture implies that there are gaps if and only if  , ignoring rays lying in one of the coordinate hyperplanes.[8] For example, placed in 2-dimensional space, squares any smaller than   in side length will leave gaps, as shown, and squares with side length   or greater will obstruct every ray that is not parallel to an axis. The conjecture generalizes this observation into any number of dimensions.

In graph theory, a distance graph   on the set of integers, and using some finite set   of positive integer distances, has an edge between   if and only if  . For example, if  , every consecutive pair of even integers, and of odd integers, is adjacent, all together forming two connected components. A k-regular coloring of the integers with step   assigns to each integer   one of   colors based on the residue of  modulo  . For example, if  , the coloring repeats every   integers and each pair of integers   are the same color. Taking  , the lonely runner conjecture implies   admits a proper k-regular coloring (i.e., each node is colored differently than its adjacencies) for some step value.[9] For example,   generates a proper coloring on the distance graph generated by  . (  is known as the regular chromatic number of  .)

Given a directed graph  , a nowhere-zero flow on   associates a positive value   to each edge  , such that the flow outward from each node is equal to the flow inward. The lonely runner conjecture implies that, if   has a nowhere-zero flow with at most   distinct integer values, then   has a nowhere-zero flow with values only in   (possibly after reversing the directions of some arcs of  ). This result was proven for   with separate methods, and because the smaller cases of the lonely runner conjecture are settled, the full theorem is proven.[10]

Known results edit

For a given setup of runners, let   denote the smallest of the runners' maximum distances of loneliness, and the gap of loneliness[11]   denote the minimum   across all setups with   runners. In this notation, the conjecture asserts that  , a bound which, if correct, cannot be improved. For example, if the runner to be lonely is stationary and speeds   are chosen, then there is no time at which they are strictly more than   units away from all others, showing that  .[c] Alternatively, this conclusion can be quickly derived from the Dirichlet approximation theorem. For   a simple lower bound   may be obtained via a probability argument.[12]

The conjecture can be reduced to restricting the runners' speeds to positive integers: If the conjecture is true for   runners with integer speeds, it is true for   runners with real speeds.[13]

Tighter bounds edit

Slight improvements on the lower bound   are known. Chen & Cusick (1999) showed for   that if   is prime, then  , and if   is prime, then  . Perarnau & Serra (2016) showed unconditionally for sufficiently large   that

 

Tao (2018) proved the current best known asymptotic result: for sufficiently large  ,

 
for some constant  . He also showed that the full conjecture is implied by proving the conjecture for integer speeds of size   (see big O notation). This implication theoretically allows proving the conjecture for a given   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  , it holds true if

 
In other words, the conjecture holds true for large   if the speeds grow quickly enough. If the constant 22 is replaced with 33, then the conjecture holds true for  .[15] A similar result for sufficiently large   only requires a similar assumption for  .[14] Unconditionally on  , the conjecture is true if   for all  .[16]

For specific n edit

The conjecture is true for   runners. The proofs for   are elementary; the   case was established in 1972.[17] The  ,  , and   cases were settled in 1984, 2001 and 2008, respectively. The first proof for   was computer-assisted, but all cases have since been proved with elementary methods.[18]

For some  , there exist sporadic examples with a maximum separation of   besides the example of   given above.[6] For  , the only known example (up to shifts and scaling) is  ; for   the only known example is  ; and for   the known examples are   and  .[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  , either   for some positive integer  ,[d] or  , where   is that setup's gap of loneliness. He confirmed this conjecture for   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   there is a positive integer   such that for any collection   of positive, distinct speeds, there exists some time   such that   for   with

 
Rifford confirmed this conjecture for   and showed that the minimal   in each case is given by   for   and   for  . The latter result (  for  ) shows that if we consider six runners starting from   at time   with constant speeds   with   and   distinct and positive then the static runner is separated by a distance at least   from the others during the first two rounds of the slowest non-static runner (but not necessary during the first round).

Other results edit

A much stronger result exists for randomly chosen speeds: using the stationary-runner convention, if   and   are fixed and   runners with nonzero speeds are chosen uniformly at random from  , then   as  . In other words, runners with random speeds are likely at some point to be "very lonely"—nearly   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   of a given runner.[22] The conjecture has been generalized to an analog in algebraic function fields.[23]

Notes and references edit

Notes edit

  1. ^ Some authors use the convention that   is the number of non-stationary runners, and thus the conjecture is that the gap of loneliness is at most  .[5]
  2. ^ For example, if the origin is at a 6 o'clock position, a runner at the 9 o'clock position will have  .
  3. ^ Let the lonely runner be fixed at 0. For sake of contradiction, suppose there exists   such that   for all  . By the pigeonhole principle, there exist distinct   and   such that   But   for some  , so either   or  , a contradiction.[6]
  4. ^ Taking   yields the lonely runner conjecture.

Citations edit

Works cited edit

External links edit