Lonely runner conjecture: Difference between revisions

Revision as of 04:28, 28 May 2022

Revision as of 23:20, 1 June 2022

Line 4:

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 <math>n</math> runners on a track of unit length, with constant speeds all distinct from one another, will each be ''lonely'' at some time—at least <math>1/n</math> 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 7 runners or less, but remains unsolved in the general case remains unsolved. Implications of the conjecture include solutions to view-obstruction problems and bounds on properties, related to [[chromatic number]]s, of certain graphs.

==Formulation==

Line 19:

Suppose <math>C</math> is a {{mvar|n}}-[[hypercube]] of side length <math>s</math> in {{mvar|n}}-dimensional space (<math>n\geq2</math>). Place a centered copy of <math>C</math> at every point with [[half-integer]] coordinates. A ray from the origin may either miss all of the copies of <math>C</math>, in which case there is a (infinitesimal) gap, or hit at least one copy. {{harvtxt|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 <math>s<(n-1)/(n+1)</math>, ignoring rays lying in one of the coordinate hyperplanes.{{Sfn|Cusick|1974|p=1}} For example, placed in 2-dimensional space, squares any smaller than <math>1/3</math> in side length will leave gaps, as shown, and squares with side length <math>1/3</math> 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 <math>G</math> on the set of integers, and using some finite set <math>D</math> of positive integer distances, has an edge between <math>x,y</math> if and only if <math>|x-y|\in D</math>. For example, if <math>D=\{2\}</math>, every consecutive pair of even integers, and of odd integers, is adjacent, all together forming two [[connected component (graph theory)|connected component]]s. A {{mvar|k}}-''regular coloring'' of the integers with step <math>\lambda\in\mathbb{R}</math> assigns to each integer <math>n</math> one of <math>k</math> colors based on the [[Modular arithmetic#Residue systems|residue]] of <math>\lfloor \lambda n\rfloor</math>modulo <math>k</math>. For example, if <math>\lambda=0.5</math>, the coloring repeats every <math>2k</math> integers and each pair of integers <math>2m, 2m+1</math> are the same color. Taking <math>k=|D|+1</math>, the lonely runner conjecture implies <math>G</math> admits a proper {{mvar|k}}-regular coloring (i.e., each node is colored differently than its adjacencies) for some step value.{{sfn|Barajas|Serra|2009|p=5688}} For example, <math>(k,\lambda)=(2,0.5)</math> generates a proper coloring on the distance graph generated by the example <math>D=\{2\}</math>. (<math>k</math> is known as the ''regular chromatic number'' of <math>D</math>.)

Given a [[directed graph]] <math>G</math>, a [[nowhere-zero flow]] on <math>G</math> associates a positive value <math>f(e)</math> to each edge <math>e</math>, such that the flow outward from each node is equal to the flow inward. The lonely runner conjecture implies that, if <math>G</math> has a nowhere-zero flow with at most <math>k</math> distinct integer values, then <math>G</math> has a nowhere-zero flow with values only in <math>\{1,2,\ldots,k\}</math>. This result was proven for <math>k\geq 5</math> with separate methods, and because the smaller cases of the lonely runner conjecture are settled, the full theorem is proven.{{sfn|Bienia|Goddyn|Gvozdjak|Sebő|1998}}

==Known results==

For a given setup of runners, let the ''gap of loneliness''{{sfn|Perarnau|Serra|2016}} <math>\delta</math> bedenote the smallest of the runners' maximum distances of loneliness, and the ''gap of loneliness''{{sfn|Perarnau|Serra|2016}} <math>\delta_n</math> denote the minimum <math>\delta</math> across all setups with <math>n</math> runners. In this notation, the conjecture asserts that <math>\delta_n\geq 1/n</math>, a bound which, if correct, cannot be improved. For example, if the runner to be lonely is stationary and speeds <math>v_i=i</math> are chosen, then there is no time at which they are strictly more than <math>1/n</math> units away from all others, showing that <math>\delta_n \leq 1/n</math>.{{efn|Let the lonely runner be fixed at 0. For sake of contradiction, suppose there exists <math>t</math> such that <math>\{v_it\}\in (1/n, 1-1/n)</math> for all <math>i</math>. By the pigeonhole principle, there exist distinct <math>i</math> and <math>j</math> such that <math>\{v_it\}\leq \{v_jt\} < \{v_it\}+1/n</math> But <math>\|v_j-v_i\|=v_k</math> for some <math>k</math>, so either <math>\{v_kt\}=\{v_jt\}-\{v_it\}<1/n</math> or <math>\{v_kt\}=1-(\{v_jt\}-\{v_it\})>1-1/n</math>, a contradiction.{{sfn|Bohman|Holzman|Kleitman|2001|p=2}} }} Alternatively, this conclusion can be quickly derived from the [[Dirichlet approximation theorem]]. AFor <math>n\geq 2</math> a simple lower bound <math>\delta_n\geq 1/(2n-2)</math> may be obtained via a covering argument.{{sfn|Tao|2018|pp=2–3}}

The conjecture can be reduced to restricting the runners' speeds to positive integers: If the conjecture is true for <math>n</math> runners with integer speeds, it is true for <math>n</math> numbers with real speeds.{{sfn|Bohman|Holzman|Kleitman|2001|pp=12–13}}

=== Tighter bounds ===

Slight improvements on the lower bound <math>1/(2n-2)</math> are known. {{harvtxt|Chen|Cusick|1999}} showed for <math>n\geq 5</math> that if <math>2n-5</math> is prime, then <math>\delta_n\geq \tfrac{1}{2n-5}</math>, and if <math>4n-9</math> is prime, then <math>\delta_n\geq \tfrac{2}{4n-9}</math>. {{harvtxt|Perarnau|Serra|2016}} showed unconditionally for sufficiently large <math>n</math> that

<math display=block>\delta_n\geq \frac{1}{2n-4+o(1)}.</math>

{{harvtxt|Tao|2018}} proved the current best known asymptotic result: for sufficiently large <math>n</math>,

<math display="block">\delta_n\geq \frac{1}{2n2(n-2)}+\frac{c\log n}{n^2(\log\log n)^2}</math>

for some constant <math>c>0</math>. He also showed that the full conjecture is implied by proving the conjecture for integer speeds of size <math>n^{O(n^2)}</math> (see [[big O notation]]). This implication theoretically allows proving the conjecture for a given <math>n</math> by checking a finite set of cases, but the number of cases grows too quickly to be practical.{{sfn|Czerwiński|2018|p=1302}}

The conjecture has been proven under specific assumptions on the runners' speeds. IfFor sufficiently large <math>n\geq 33</math>, it holds true andif

<math display="block">\frac{v_{i+1}}{v_i}\geq 1 + \frac{22\log(n-1)}{n-1} \qquad (i=1,...,n-1),.</math>

thenIn other words, the minimumconjecture gapholds oftrue lonelinessfor islarge <math>1/n</math> if the speeds grow quickly enough. InIf otherthe wordsconstant 22 is replaced with 33, then the conjecture holds true for <math> n\geq 3316343</math> if the speeds grow quickly enough.{{sfn|Dubickas|2011|p=27}} A slightly strongersimilar result for sufficiently large <math>n\geq 40</math> only requires a similar assumption on the firstfor <math> i =\lfloor n/2122 \rfloor,...,n-1</math> speeds.{{sfn|Czerwiński|2018|p=1302}} In a similar fashion but unconditionallyUnconditionally on <math>n</math>, the conjecture is true if <math>v_{i+1}/v_i\geq 2</math> for all <math> i</math>.{{sfn|Barajas|Serra|2009}}

=== For specific {{mvar|n}} ===

Line 45:

The conjecture is true for <math>n\leq 7</math> runners. The proofs for <math>n\leq 3</math> are elementary; the <math>n=4</math> case was established in 1972.{{sfnm|1a1=Betke|1a2=Wills|1y=1972|1pp=215–216|2a1=Cusick|2y=1974|2p=5|ps=. Cusick's paper independently proves this result.}} The <math>n=5</math>, <math>n=6</math>, and <math>n=7</math> cases were settled in 1984, 2001 and 2008, respectively. The first proof for <math>n=5</math> was computer-assisted. All have since been proved with elementary methods.{{sfnm|1a1=Cusick|1a2=Pomerance|1y=1984|1p=133|2a1=Bohman|2a2=Holzman|2a3=Kleitman|2y=2001|3a1=Barajas|3a2=Serra|3y=2008a|4a1=Renault|4y=2004|ps=. Renault gives an elementary proof for <math>n=6</math>.}}

For some <math>n</math>, there exist sporadic examples with a maximum separation of <math>1/n</math> besides the example of <math>v_i=i</math> given above.{{sfn|Bohman|Holzman|Kleitman|2001|p=2}} For <math>n=5</math>, the only otherknown example (up to shifts and scaling) is <math>\{0,1,3,4,7\}</math>; for <math>n=6</math> the only known example is <math>\{0,1,3,4,5,9\}</math>; and for <math>n=8</math> the onlyknown examples are <math>\{0,1,4,5,6,7,11,13\}</math> and <math>\{0,1,2,3,4,5,7,12\}</math>.{{sfn|Bohman|Holzman|Kleitman|2001|p=3}} All solutions for <math>n\leq 20</math> reaching exactly <math>1/n</math> in separation are known through exhaustive computer search, and thereThere exists an explicit infinite family of extremalsuch examplessporadic cases.{{sfn|Goddyn|Wong|2006}}

{{harvtxt|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 <math>v_i</math>, either <math>\delta = s/(sn+1)</math> for some positive integer <math>s</math>, or <math>\delta \geq 1/(n-1)</math>, where <math>\delta</math> is that setup's gap of loneliness. He confirmed this conjecture for <math>n\leq 3</math> and a few special cases.