Lonely runner conjecture: Difference between revisions

Revision as of 19:11, 22 May 2022

Revision as of 19:12, 22 May 2022

Line 44:

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 other example (up to shifts, scaling, and permutationscaling) is <math>\{0,1,3,4,7\}</math>; for <math>n=6</math> the only example is <math>\{0,1,3,4,5,9\}</math>; and for <math>n=8</math> the only example is <math>\{0,1,4,5,6,7,11,13\}</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 there exists an explicit infinite family of extremal examples.{{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.