Lonely runner conjecture: Difference between revisions

Revision as of 10:36, 15 July 2023

Latest revision as of 16:01, 24 March 2025

(4 intermediate revisions by 4 users not shown)

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 7seven runners or lessfewer, but 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 10:

Consider <math>n</math> runners on a circular track of unit length. At the initial time <math>t=0</math>, 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 <math>t</math> if they are at a distance (measured along the circle) of at least <math>1/n</math> from every other runner. The lonely runner conjecture states that each runner is lonely at some time, no matter the choice of speeds.{{sfn|Bohman|Holzman|Kleitman|2001|p=1}}

This visual formulation of the conjecture was first published in 1998.{{sfn|Bienia|Goddyn|Gvozdjak|Sebő|1998|p=3}} In many formulations, including the original by Jörg M. Wills,{{Sfnm|1a1=Wills|1y=1967|2a1=Bienia|2a2=Goddyn|2a3=Gvozdjak|2a4=Sebő|2y=1998}}{{sfn|Wills|1967}} some simplifications are made. The runner to be lonely is stationary at 0 (with zero speed), and therefore <math>n-1</math> other runners, with nonzero speeds, are considered.{{efn|Some authors use the convention that <math>n</math> is the number of non-stationary runners, and thus the conjecture is that the gap of loneliness is at most <math>1/(n+1)</math>.{{sfn|Tao|2018}} }} The moving runners may be further restricted to ''positive'' speeds only: by symmetry, runners with speeds <math>x</math> and <math>-x</math> 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 <math>v_1,v_2,...\dots,v_{n-1}</math> of positive, distinct speeds, there exists some time <math>t>0</math> such that

<math display="block">\frac{1}{n}\leq \operatorname{frac}(v_it)\leq 1-\frac{1}{n}\qquad (i=1,...\dots,n-1),</math>

where <math>\operatorname{frac}(x)</math> denotes the [[fractional part]] of <math>x</math>.{{sfn|Bohman|Holzman|Kleitman|2001|p=2}} Interpreted visually, if the runners are running counterclockwise, the middle term of the inequality is the distance from the origin to the <math>i</math>th runner at time <math>t</math>, measured counterclockwise.{{Efn|For example, if the origin is at a 6 o'clock position, a runner at the 9 o'clock position will have <math>\operatorname{frac}(vt)=3/4</math>.}} This convention is used for the rest of this article. Wills' conjecture was part of his work in [[Diophantine approximation]],{{sfnm|1a1=Wills|1y=1967|2a1=Betke|2a2=Wills|2y=1972}} the study of how closely fractions can approximate irrational numbers.

Line 37:

The conjecture has been proven under specific assumptions on the runners' speeds. For sufficiently large <math>n</math>, it holds true if

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

In other words, the conjecture holds true for large <math>n</math> if the speeds grow quickly enough. If the constant 22 is replaced with 33, then the conjecture holds true for <math> n\geq 16343</math>.{{sfn|Dubickas|2011|p=27}} A similar result for sufficiently large <math>n</math> only requires a similar assumption for <math> i =\lfloor n/22 \rfloor-1,...\dots,n-2</math>.{{sfn|Czerwiński|2018|p=1302}} Unconditionally 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 49:

{{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/(s(n-1)+1)</math> for some positive integer <math>s</math>,{{efn|Taking <math>s=1</math> yields the lonely runner conjecture.}} 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 4</math> and a few special cases.

{{harvtxt|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 <math>n \geq 3</math> there is a positive integer <math>N</math> such that for any collection <math>v_1,v_2,...\dots,v_{n-1}</math> of positive, distinct speeds, there exists some time <math>t>0</math> such that <math>\operatorname{frac}(v_it)\in [1/n,1-1/n]</math> for <math>i=1, ...\dots,n-1</math> with

<math display="block">t \leq \frac{N}{\operatorname{min} (v_1,...\dots, v_{n-1})}.</math>

Rifford confirmed this conjecture for <math>n=3,4,5,6</math> and showed that the minimal <math>N</math> in each case is given by <math>N=1</math> for <math>n=3,4,5</math> and <math>N=2</math> for <math>n=6</math>. The latter result (<math>N=2</math> for <math>n=6</math>) shows that if we consider six runners starting from <math>0</math> at time <math>t=0</math> with constant speeds <math>v_0,v_1,...\dots,v_{5}</math> with <math>v_0=0</math>

and <math>v_1,...\dots,v_{5}</math> distinct and positive then the static runner is separated by a distance at least <math>1/6</math> from the others during the first two rounds of the slowest non-static runner (but not necessary during the first round).

=== Other results ===

Line 82:

* {{cite journal |last1=Goddyn |first1=L. |last2=Wong |first2=Erick B. |title=Tight instances of the lonely runner |url=http://people.math.sfu.ca/~goddyn/Papers/063tight_lonely_runner.pdf |access-date=1 May 2022 |date=2006 |journal=Integers |volume=6 |issue=A38}}

* {{Cite journal |last1=Kravitz |first1=N. |doi=10.5070/C61055383 |title=Barely lonely runners and very lonely runners: a refined approach to the Lonely Runner Problem |journal=Combinatorial Theory |volume=1 |year=2021 |arxiv=1912.06034|s2cid=245100000 }}

* {{cite journal |last1=Perarnau |first1=Guillem |last2=Serra |first2=Oriol |title=Correlation among runners and some results on the lonely runner conjecture |journal=[[The Electronic Journal of Combinatorics]] |date=March 2016 |volume=23 |issue=1 |pages=P1.50 |doi=10.37236/5123|s2cid=7039062 |doi-access=free |arxiv=1407.3381 }}

* {{Cite journal |last1=Renault |first1=J. |doi=10.1016/j.disc.2004.06.008 |title=View-obstruction: A shorter proof for 6 lonely runners |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |volume=287 |pages=93–101 |year=2004 |issue=1–3 |url=https://basepub.dauphine.fr/handle/123456789/6201 |doi-access=free}}

* {{Cite journal |last1=Rifford |first1=L. |title=On the time for a runner to get lonely | url = https://arxiv.org/pdf/2111.13688.pdf |journal=Acta Applicandae Mathematicae |volume=180 |pages= Paper No. 15 | year=2022 |doi=10.1007/s10440-022-00515-9|arxiv=2111.13688 }}

* {{cite journal |last1=Tao |first1=Terence |author-link1=Terence Tao |title=Some remarks on the lonely runner conjecture |journal=Contributions to Discrete Mathematics |date=31 December 2018 |volume=13 |pages=No 2 (2018) |doi=10.11575/cdm.v13i2.62728 |doi-access=free}}

* {{cite journal |last1=Wills |first1=Jörg M. |title=Zwei sätze über inhomogene diophantische approximation von irrationalzehlen |journal=[[Monatshefte für Mathematik]] |date=1967 |volume=71 |issue=3 |pages=263–269 |doi=10.1007/BF01298332|s2cid=122754182 }}