Lonely runner conjecture: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Inline

Latest revision as of 18:56, 19 December 2024

Unsolved problem in mathematics:

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

(more unsolved problems in mathematics)

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

Consider $n$ runners on a circular track of unit length. At the initial time $t=0$ , 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 $t$ if they are at a distance (measured along the circle) of at least $1/n$ 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 $n-1$ other runners, with nonzero speeds, are considered.^[a] The moving runners may be further restricted to positive speeds only: by symmetry, runners with speeds $x$ and $-x$ 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 $v_{1},v_{2},\dots ,v_{n-1}$ of positive, distinct speeds, there exists some time $t>0$ such that ${\frac {1}{n}}\leq \operatorname {frac} (v_{i}t)\leq 1-{\frac {1}{n}}\qquad (i=1,\dots ,n-1),$ where $\operatorname {frac} (x)$ denotes the fractional part of $x$ .^[6] Interpreted visually, if the runners are running counterclockwise, the middle term of the inequality is the distance from the origin to the $i$ th runner at time $t$ , 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

Suppose $C$ is a $n$ -hypercube of side length $s$ in $n$ -dimensional space ( $n\geq 2$ ). Place a centered copy of $C$ at every point with half-integer coordinates. A ray from the origin may either miss all of the copies of $C$ , 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 $s<(n-1)/(n+1)$ , ignoring rays lying in one of the coordinate hyperplanes.^[8] For example, placed in 2-dimensional space, squares any smaller than $1/3$ in side length will leave gaps, as shown, and squares with side length $1/3$ 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 $G$ on the set of integers, and using some finite set $D$ of positive integer distances, has an edge between $x,y$ if and only if $|x-y|\in D$ . For example, if $D=\{2\}$ , 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 $\lambda \in \mathbb {R}$ assigns to each integer $n$ one of $k$ colors based on the residue of $\lfloor \lambda n\rfloor$ modulo $k$ . For example, if $\lambda =0.5$ , the coloring repeats every $2k$ integers and each pair of integers $2m,2m+1$ are the same color. Taking $k=|D|+1$ , the lonely runner conjecture implies $G$ admits a proper $k$ -regular coloring (i.e., each node is colored differently than its adjacencies) for some step value.^[9] For example, $(k,\lambda )=(2,0.5)$ generates a proper coloring on the distance graph generated by $D=\{2\}$ . ( $k$ is known as the regular chromatic number of $D$ .)

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

Known results

For a given setup of runners, let $\delta$ denote the smallest of the runners' maximum distances of loneliness, and the gap of loneliness^[11] $\delta _{n}$ denote the minimum $\delta$ across all setups with $n$ runners. In this notation, the conjecture asserts that $\delta _{n}\geq 1/n$ , a bound which, if correct, cannot be improved. For example, if the runner to be lonely is stationary and speeds $v_{i}=i$ are chosen, then there is no time at which they are strictly more than $1/n$ units away from all others, showing that $\delta _{n}\leq 1/n$ .^[c] Alternatively, this conclusion can be quickly derived from the Dirichlet approximation theorem. For $n\geq 2$ a simple lower bound $\delta _{n}\geq 1/(2n-2)$ 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 $n$ runners with integer speeds, it is true for $n$ runners with real speeds.^[13]

Tighter bounds

Slight improvements on the lower bound $1/(2n-2)$ are known. Chen & Cusick (1999) showed for $n\geq 5$ that if $2n-5$ is prime, then $\delta _{n}\geq {\tfrac {1}{2n-5}}$ , and if $4n-9$ is prime, then $\delta _{n}\geq {\tfrac {2}{4n-9}}$ . Perarnau & Serra (2016) showed unconditionally for sufficiently large $n$ that $\delta _{n}\geq {\frac {1}{2n-4+o(1)}}.$

Tao (2018) proved the current best known asymptotic result: for sufficiently large $n$ , $\delta _{n}\geq {\frac {1}{2n-2}}+{\frac {c\log n}{n^{2}(\log \log n)^{2}}}$ for some constant $c>0$ . He also showed that the full conjecture is implied by proving the conjecture for integer speeds of size $n^{O(n^{2})}$ (see big O notation). This implication theoretically allows proving the conjecture for a given $n$ 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 $n$ , it holds true if ${\frac {v_{i+1}}{v_{i}}}\geq 1+{\frac {22\log(n-1)}{n-1}}\qquad (i=1,\dots ,n-2).$ In other words, the conjecture holds true for large $n$ if the speeds grow quickly enough. If the constant 22 is replaced with 33, then the conjecture holds true for $n\geq 16343$ .^[15] A similar result for sufficiently large $n$ only requires a similar assumption for $i=\lfloor n/22\rfloor -1,\dots ,n-2$ .^[14] Unconditionally on $n$ , the conjecture is true if $v_{i+1}/v_{i}\geq 2$ for all $i$ .^[16]

For specific $n$

The conjecture is true for $n\leq 7$ runners. The proofs for $n\leq 3$ are elementary; the $n=4$ case was established in 1972.^[17] The $n=5$ , $n=6$ , and $n=7$ cases were settled in 1984, 2001 and 2008, respectively. The first proof for $n=5$ was computer-assisted, but all cases have since been proved with elementary methods.^[18]

For some $n$ , there exist sporadic examples with a maximum separation of $1/n$ besides the example of $v_{i}=i$ given above.^[6] For $n=5$ , the only known example (up to shifts and scaling) is $\{0,1,3,4,7\}$ ; for $n=6$ the only known example is $\{0,1,3,4,5,9\}$ ; and for $n=8$ the known examples are $\{0,1,4,5,6,7,11,13\}$ and $\{0,1,2,3,4,5,7,12\}$ .^[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 $v_{i}$ , either $\delta =s/(s(n-1)+1)$ for some positive integer $s$ ,^[d] or $\delta \geq 1/(n-1)$ , where $\delta$ is that setup's gap of loneliness. He confirmed this conjecture for $n\leq 4$ 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 $n\geq 3$ there is a positive integer $N$ such that for any collection $v_{1},v_{2},\dots ,v_{n-1}$ of positive, distinct speeds, there exists some time $t>0$ such that $\operatorname {frac} (v_{i}t)\in [1/n,1-1/n]$ for $i=1,\dots ,n-1$ with $t\leq {\frac {N}{\operatorname {min} (v_{1},\dots ,v_{n-1})}}.$ Rifford confirmed this conjecture for $n=3,4,5,6$ and showed that the minimal $N$ in each case is given by $N=1$ for $n=3,4,5$ and $N=2$ for $n=6$ . The latter result ( $N=2$ for $n=6$ ) shows that if we consider six runners starting from $0$ at time $t=0$ with constant speeds $v_{0},v_{1},\dots ,v_{5}$ with $v_{0}=0$ and $v_{1},\dots ,v_{5}$ distinct and positive then the static runner is separated by a distance at least $1/6$ from the others during the first two rounds of the slowest non-static runner (but not necessary during the first round).

Other results

A much stronger result exists for randomly chosen speeds: using the stationary-runner convention, if $n$ and $\varepsilon >0$ are fixed and $n-1$ runners with nonzero speeds are chosen uniformly at random from $\{1,2,\ldots ,k\}$ , then $P(\delta \geq 1/2-\varepsilon )\to 1$ as $k\to \infty$ . In other words, runners with random speeds are likely at some point to be "very lonely"—nearly $1/2$ 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 $1/n$ of a given runner.^[22] The conjecture has been generalized to an analog in algebraic function fields.^[23]

Notes and references

Notes

^ Some authors use the convention that $n$ is the number of non-stationary runners, and thus the conjecture is that the gap of loneliness is at most $1/(n+1)$ .^[5]
^ For example, if the origin is at a 6 o'clock position, a runner at the 9 o'clock position will have $\operatorname {frac} (vt)=3/4$ .
^ Let the lonely runner be fixed at 0. For sake of contradiction, suppose there exists $t$ such that $\{v_{i}t\}\in (1/n,1-1/n)$ for all $i$ . By the pigeonhole principle, there exist distinct $i$ and $j$ such that $\{v_{i}t\}\leq \{v_{j}t\}<\{v_{i}t\}+1/n$ But $\|v_{j}-v_{i}\|=v_{k}$ for some $k$ , so either $\{v_{k}t\}=\{v_{j}t\}-\{v_{i}t\}<1/n$ or $\{v_{k}t\}=1-(\{v_{j}t\}-\{v_{i}t\})>1-1/n$ , a contradiction.^[6]
^ Taking $s=1$ yields the lonely runner conjecture.

Citations

^ Bohman, Holzman & Kleitman 2001, p. 1.
^ Bienia et al. 1998, p. 3.
^ Wills 1967; Bienia et al. 1998.
^ Wills 1967.
^ Tao 2018.
^ ^a ^b ^c Bohman, Holzman & Kleitman 2001, p. 2.
^ Wills 1967; Betke & Wills 1972.
^ Cusick 1974, p. 1.
^ Barajas & Serra 2009, p. 5688.
^ Bienia et al. 1998.
^ Perarnau & Serra 2016.
^ Tao 2018, pp. 2–3.
^ Bohman, Holzman & Kleitman 2001, pp. 12–13.
^ ^a ^b Czerwiński 2018, p. 1302.
^ Dubickas 2011, p. 27.
^ Barajas & Serra 2009.
^ Betke & Wills 1972, pp. 215–216; Cusick 1974, p. 5. Cusick's paper independently proves this result.
^ Cusick & Pomerance 1984, p. 133; Bohman, Holzman & Kleitman 2001; Barajas & Serra 2008a; Renault 2004. Renault gives an elementary proof for $n=6$ .
^ Bohman, Holzman & Kleitman 2001, p. 3.
^ Goddyn & Wong 2006.
^ Czerwiński 2012, p. 2.
^ Czerwiński & Grytczuk 2008.
^ Chow & Rimanić 2019.

Works cited

Barajas, Javier; Serra, Oriol (2008a). "The lonely runner with seven runners". The Electronic Journal of Combinatorics. 15 (1): R48. doi:10.37236/772.
——; —— (September 2009). "On the chromatic number of circulant graphs". Discrete Mathematics. 309 (18): 5687–5696. doi:10.1016/j.disc.2008.04.041.
Betke, U.; Wills, J. M. (1972). "Untere schranken für zwei diophantische approximations-funktionen". Monatshefte für Mathematik. 76 (3): 214. doi:10.1007/BF01322924. S2CID 122549668.
Bienia, Wojciech; Goddyn, Luis; Gvozdjak, Pavol; Sebő, András; Tarsi, Michael (January 1998). "Flows, view obstructions, and the lonely runner". Journal of Combinatorial Theory, Series B. 72 (1): 1–9. doi:10.1006/jctb.1997.1770.
Bohman, Tom; Holzman, Ron; Kleitman, Dan (February 2001). "Six lonely runners". The Electronic Journal of Combinatorics. 8 (2): R3. doi:10.37236/1602.
Chen, Yong-Gao; Cusick, T. W. (January 1999). "The view-obstruction problem for n-dimensional cubes". Journal of Number Theory. 74 (1): 126–133. doi:10.1006/jnth.1998.2309.
Chow, Sam; Rimanić, Luka (January 2019). "Lonely runners in function fields" (PDF). Mathematika. 65 (3): 677–701. doi:10.1112/S002557931900007X. S2CID 118621899.
Cusick, T. W. (1973). "View-obstruction problems". Aequationes Mathematicae. 9 (2–3): 165–170. doi:10.1007/BF01832623. S2CID 122050409.
—— (1974). "View-obstruction problems in n-dimensional geometry". Journal of Combinatorial Theory, Series A. 16 (1): 1–11. doi:10.1016/0097-3165(74)90066-1.
——; Pomerance, Carl (1984). "View-obstruction problems, III". Journal of Number Theory. 19 (2): 131–139. doi:10.1016/0022-314X(84)90097-0.
Czerwiński, Sebastian (2012). "Random runners are very lonely". Journal of Combinatorial Theory, Series A. 119 (6): 1194–1199. arXiv:1102.4464. doi:10.1016/j.jcta.2012.02.002. S2CID 26415692.
—— (May 2018). "The lonely runner problem for lacunary sequences". Discrete Mathematics. 341 (5): 1301–1306. doi:10.1016/j.disc.2018.02.002.
——; Grytczuk, Jarosław (September 2008). "Invisible runners in finite fields". Information Processing Letters. 108 (2): 64–67. doi:10.1016/j.ipl.2008.03.019.
Dubickas, A. (2011). "The lonely runner problem for many runners". Glasnik Matematicki. 46: 25–30. doi:10.3336/gm.46.1.05.
Goddyn, L.; Wong, Erick B. (2006). "Tight instances of the lonely runner" (PDF). Integers. 6 (A38). Retrieved 1 May 2022.
Kravitz, N. (2021). "Barely lonely runners and very lonely runners: a refined approach to the Lonely Runner Problem". Combinatorial Theory. 1. arXiv:1912.06034. doi:10.5070/C61055383. S2CID 245100000.
Perarnau, Guillem; Serra, Oriol (March 2016). "Correlation among runners and some results on the lonely runner conjecture". The Electronic Journal of Combinatorics. 23 (1): P1.50. arXiv:1407.3381. doi:10.37236/5123. S2CID 7039062.
Renault, J. (2004). "View-obstruction: A shorter proof for 6 lonely runners". Discrete Mathematics. 287 (1–3): 93–101. doi:10.1016/j.disc.2004.06.008.
Rifford, L. (2022). "On the time for a runner to get lonely" (PDF). Acta Applicandae Mathematicae. 180: Paper No. 15. doi:10.1007/s10440-022-00515-9.
Tao, Terence (31 December 2018). "Some remarks on the lonely runner conjecture". Contributions to Discrete Mathematics. 13: No 2 (2018). doi:10.11575/cdm.v13i2.62728.
Wills, Jörg M. (1967). "Zwei sätze über inhomogene diophantische approximation von irrationalzehlen". Monatshefte für Mathematik. 71 (3): 263–269. doi:10.1007/BF01298332. S2CID 122754182.

External links

Article in the Open Problem Garden no. 4, 551–562.

[6] Some authors use the convention that $n$ is the number of non-stationary runners, and thus the conjecture is that the gap of loneliness is at most $1/(n+1)$ .^[5]

[8] For example, if the origin is at a 6 o'clock position, a runner at the 9 o'clock position will have $\operatorname {frac} (vt)=3/4$ .

[14] Let the lonely runner be fixed at 0. For sake of contradiction, suppose there exists $t$ such that $\{v_{i}t\}\in (1/n,1-1/n)$ for all $i$ . By the pigeonhole principle, there exist distinct $i$ and $j$ such that $\{v_{i}t\}\leq \{v_{j}t\}<\{v_{i}t\}+1/n$ But $\|v_{j}-v_{i}\|=v_{k}$ for some $k$ , so either $\{v_{k}t\}=\{v_{j}t\}-\{v_{i}t\}<1/n$ or $\{v_{k}t\}=1-(\{v_{j}t\}-\{v_{i}t\})>1-1/n$ , a contradiction.^[6]

[24] Taking $s=1$ yields the lonely runner conjecture.

[FOOTNOTEBohmanHolzmanKleitman20011-1] Bohman, Holzman & Kleitman 2001, p. 1.

[FOOTNOTEBieniaGoddynGvozdjakSebő19983-2] Bienia et al. 1998, p. 3.

[FOOTNOTEWills1967BieniaGoddynGvozdjakSebő1998-3] Wills 1967; Bienia et al. 1998.

[FOOTNOTEWills1967-4] Wills 1967.

[FOOTNOTETao2018-5] Tao 2018.

[FOOTNOTEBohmanHolzmanKleitman20012-7] Bohman, Holzman & Kleitman 2001, p. 2.

[FOOTNOTEWills1967BetkeWills1972-9] Wills 1967; Betke & Wills 1972.

[FOOTNOTECusick19741-10] Cusick 1974, p. 1.

[FOOTNOTEBarajasSerra20095688-11] Barajas & Serra 2009, p. 5688.

[FOOTNOTEBieniaGoddynGvozdjakSebő1998-12] Bienia et al. 1998.

[FOOTNOTEPerarnauSerra2016-13] Perarnau & Serra 2016.

[FOOTNOTETao20182–3-15] Tao 2018, pp. 2–3.

[FOOTNOTEBohmanHolzmanKleitman200112–13-16] Bohman, Holzman & Kleitman 2001, pp. 12–13.

[FOOTNOTECzerwiński20181302-17] Czerwiński 2018, p. 1302.

[FOOTNOTEDubickas201127-18] Dubickas 2011, p. 27.

[FOOTNOTEBarajasSerra2009-19] Barajas & Serra 2009.

[FOOTNOTEBetkeWills1972215–216Cusick19745-20] Betke & Wills 1972, pp. 215–216; Cusick 1974, p. 5. Cusick's paper independently proves this result.

[FOOTNOTECusickPomerance1984133BohmanHolzmanKleitman2001BarajasSerra2008aRenault2004-21] Cusick & Pomerance 1984, p. 133; Bohman, Holzman & Kleitman 2001; Barajas & Serra 2008a; Renault 2004. Renault gives an elementary proof for $n=6$ .

[FOOTNOTEBohmanHolzmanKleitman20013-22] Bohman, Holzman & Kleitman 2001, p. 3.

[FOOTNOTEGoddynWong2006-23] Goddyn & Wong 2006.

[FOOTNOTECzerwiński20122-25] Czerwiński 2012, p. 2.

[FOOTNOTECzerwińskiGrytczuk2008-26] Czerwiński & Grytczuk 2008.

[FOOTNOTEChowRimanić2019-27] Chow & Rimanić 2019.

[1]

[2]

[3]

[4]

[a]

[6]

[b]

[7]

[8]

[9]

[10]

[11]

[c]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[d]

[21]

[22]

[23]

[5]

@@ Line 1: / Line 1: @@
+{{good article}}
 {{short description|Unsolved problem in mathematics}}
 {{unsolved|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 <math>n</math> runners, 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.
+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. Implications of the conjecture include solutions to view obstruction problems and bounds on the [[chromatic number]] of certain graphs.
+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 number]]s, of certain graphs.
 ==Formulation==
@@ Line 9: / 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. Proving the result for any stationary runner implies the general result for all runners, since she can be made stationary by subtracting her speed from all runners, leaving her with zero speed. The conjecture then states that, for any collection <math>v_1,v_2,...,v_{n-1}</math> of positive, distinct speeds, there exists some time <math>t>0</math> such that
+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,...,n-1),</math>
+<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 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>.}} 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. His conjecture concerns how well multiple real numbers could be simultaneously approximated with a single denominator.
+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.
 == Implications ==
-[[File:View-obstruction problem for squares.svg|thumb|alt=A series of red squares and a green line, with slope 2, narrowly hitting the squares.|Squares of side length 1/3 placed at every half-integer coordinate in the positive quadrant obstruct any ray from the origin in that direction. Any smaller side length will leave small gaps.]]
+[[File:View-obstruction problem for squares.svg|thumb|alt=A series of red squares and a green line, with slope 2, narrowly hitting the squares.|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 <math>C</math> is a {{mvar|n}}-[[hypercube]] in {{mvar|n}}-dimensional space (<math>n\geq2</math>). Infinitely many copies of <math>C</math>, all scaled by some factor <math>\alpha</math>, are placed at points at nonnegative half-integer coordinates. A ray from the origin into the positive [[orthant]] (in other words, directed positively in every dimension) may either miss all of the copies of <math>C</math> 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>\alpha<(n-1)/(n+1)</math>.{{Sfn|Cusick|1974|p=1}} For example, squares any smaller than <math>1/3</math> in side length will leave gaps, as shown.
+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\in\mathbb{Z}</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. The lonely runner conjecture implies that the minimum <math>k</math> for which <math>G</math> admits a proper {{mvar|k}}-regular coloring (i.e., each node is colored differently than its adjacencies) for ''some'' step value is at most <math>|D|+1</math>.{{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>.)
+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 <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. Suppose <math>f</math> is further restricted to positive integers. The lonely runner conjecture implies that, if <math>f</math> attains at most <math>k</math> different 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}}
+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> (possibly after reversing the directions of some arcs of <math>G</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> be the smallest of the runners' maximum distances of loneliness, and <math>\delta_n</math> denote the minimum <math>\delta</math> across all setups with <math>n</math> runners. The conjecture then 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 he is 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 is a corollary of the [[Dirichlet approximation theorem]]. A simple lower bound <math>\delta_n\geq 1/2n</math> may be obtained via a covering argument.{{sfn|Tao|2018|pp=2–3}}
+For a given setup of runners, let <math>\delta</math> denote 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]]. For <math>n\geq 2</math> a simple lower bound <math>\delta_n\geq 1/(2n-2)</math> may be obtained via a probability 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}}
+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> runners with real speeds.{{sfn|Bohman|Holzman|Kleitman|2001|pp=12–13}}
 === Tighter bounds ===
-Slight improvements on the lower bound <math>1/2n</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
+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}{2n}+\frac{c\log n}{n^2(\log\log n)^2}</math>
+<math display="block">\delta_n\geq \frac{1}{2n-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. If <math>n\geq 33</math> and
+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,...,n-1),</math>
+<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>
-then the minimum gap of loneliness is <math>1/n</math>. In other words, the conjecture holds true for <math>n\geq 33</math> if the speeds grow quickly enough.{{sfn|Dubickas|2011|p=27}} A slightly stronger result for <math>n\geq 40</math> only requires a similar assumption on the first <math>\lfloor n/21 \rfloor</math> speeds.{{sfn|Czerwiński|2018|p=1302}} In a similar fashion but unconditionally on <math>n</math>, the conjecture is true if <math>v_{i+1}/v_i\geq 2</math>.{{sfn|Barajas|Serra|2009}}
+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}} ===
 {{Anchor|For specific n}}
-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>.}}
+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, but all cases 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 and scaling) 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}}
+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 known 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 known 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}} There exists an explicit infinite family of such sporadic 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.
+{{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 61: / Line 67: @@
 {{Refbegin|30em}}
 * {{cite journal |last1=Barajas |first1=Javier |last2=Serra |first2=Oriol |title=The lonely runner with seven runners |journal=[[The Electronic Journal of Combinatorics]] |date=2008a |volume=15 |issue=1 |pages=R48 |doi=10.37236/772 |doi-access=free}}
-* {{cite journal |last1=Barajas |first1=Javier |last2=Serra |first2=Oriol |title=On the chromatic number of circulant graphs |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |date=September 2009 |volume=309 |issue=18 |pages=5687–5696 |doi=10.1016/j.disc.2008.04.041 |author1-mask=2 |author2-mask=2}}
+* {{cite journal |last1=Barajas |first1=Javier |last2=Serra |first2=Oriol |title=On the chromatic number of circulant graphs |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |date=September 2009 |volume=309 |issue=18 |pages=5687–5696 |doi=10.1016/j.disc.2008.04.041 |author1-mask=2 |author2-mask=2|doi-access=free }}
-* {{cite journal |last1=Bienia |first1=Wojciech |last2=Goddyn |first2=Luis |last3=Gvozdjak |first3=Pavol |last4=Sebő |first4=András |last5=Tarsi |first5=Michael |title=Flows, view obstructions, and the lonely runner |journal=[[Journal of Combinatorial Theory, Series B]] |date=January 1998 |volume=72 |issue=1 |pages=1–9 |doi=10.1006/jctb.1997.1770 |doi-access=free}}
 * {{Cite journal |last1=Betke |first1=U. |last2=Wills |first2=J. M. |doi=10.1007/BF01322924 |title=Untere schranken für zwei diophantische approximations-funktionen |journal=[[Monatshefte für Mathematik]] |volume=76 |issue=3 |pages=214 |year=1972 |s2cid=122549668}}
-* {{cite journal |last1=Bohman |first1=Tom |author-link1=Tom Bohman |last2=Holzman |first2=Ron |last3=Kleitman |first3=Dan |author-link3=Daniel Kleitman |title=Six lonely runners |journal=[[The Electronic Journal of Combinatorics]] |date=February 2001 |pages=R3–R3 |doi=10.37236/1602 |doi-access=free}}
+* {{cite journal |last1=Bienia |first1=Wojciech |last2=Goddyn |first2=Luis |last3=Gvozdjak |first3=Pavol |last4=Sebő |first4=András |last5=Tarsi |first5=Michael |title=Flows, view obstructions, and the lonely runner |journal=[[Journal of Combinatorial Theory, Series B]] |date=January 1998 |volume=72 |issue=1 |pages=1–9 |doi=10.1006/jctb.1997.1770 |doi-access=free}}
-* {{cite journal |last1=Chen |first1=Yong-Gao |last2=Cusick |first2=T. W. |title=The view-obstruction problem for n-dimensional cubes |journal=[[Journal of Number Theory]] |date=January 1999 |volume=74 |issue=1 |pages=126–133 |doi=10.1006/jnth.1998.2309 |url=https://zh.booksc.eu/book/1944302/9bd583}}
+* {{cite journal |last1=Bohman |first1=Tom |author-link1=Tom Bohman |last2=Holzman |first2=Ron |last3=Kleitman |first3=Dan |author-link3=Daniel Kleitman |title=Six lonely runners |journal=[[The Electronic Journal of Combinatorics]] |date=February 2001 |volume=8 |issue=2 |pages=R3 |doi=10.37236/1602 |doi-access=free}}
-* {{cite journal |last1=Chow |first1=Sam |last2=Rimanić |first2=Luka |title=Lonely runners in function fields |journal=[[Mathematika]] |date=January 2019 |volume=65 |issue=3 |pages=677–701 |doi=10.1112/S002557931900007X}}
+* {{cite journal |last1=Chen |first1=Yong-Gao |last2=Cusick |first2=T. W. |title=The view-obstruction problem for n-dimensional cubes |journal=[[Journal of Number Theory]] |date=January 1999 |volume=74 |issue=1 |pages=126–133 |doi=10.1006/jnth.1998.2309 |url=https://zh.booksc.eu/book/1944302/9bd583|doi-access=free }}
+* {{cite journal |last1=Chow |first1=Sam |last2=Rimanić |first2=Luka |title=Lonely runners in function fields |journal=[[Mathematika]] |date=January 2019 |volume=65 |issue=3 |pages=677–701 |doi=10.1112/S002557931900007X|s2cid=118621899 |url=http://wrap.warwick.ac.uk/125495/7/WRAP-lonely-runners-function-fields-Chow-2019.pdf }}
 * {{cite journal |last1=Cusick |first1=T. W. |title=View-obstruction problems |journal=[[Aequationes Mathematicae]] |volume=9 |pages=165–170 |year=1973 |doi=10.1007/BF01832623 |issue=2–3 |s2cid=122050409}}
 * {{cite journal |last=Cusick |first=T. W. |author-mask=2 |title=View-obstruction problems in n-dimensional geometry |journal=[[Journal of Combinatorial Theory, Series A]] |volume=16 |issue=1 |year=1974 |pages=1–11 |doi=10.1016/0097-3165(74)90066-1 |doi-access=free}}
 * {{Cite journal |last1=Cusick |first1=T. W. |author-mask=2 |last2=Pomerance |first2=Carl |author-link2=Carl Pomerance |title=View-obstruction problems, III |doi=10.1016/0022-314X(84)90097-0 |journal=[[Journal of Number Theory]] |volume=19 |issue=2 |pages=131–139 |year=1984 |doi-access=free}}
 * {{Cite journal |last1=Czerwiński |first1=Sebastian |doi=10.1016/j.jcta.2012.02.002 |title=Random runners are very lonely |journal=[[Journal of Combinatorial Theory, Series A]] |volume=119 |pages=1194–1199 |year=2012 |issue=6 |arxiv=1102.4464 |s2cid=26415692}}
+* {{cite journal |last1=Czerwiński |first1=Sebastian |title=The lonely runner problem for lacunary sequences |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |date=May 2018 |volume=341 |issue=5 |pages=1301–1306 |doi=10.1016/j.disc.2018.02.002|author1-mask=2|doi-access=free }}
 * {{cite journal |last1=Czerwiński |first1=Sebastian |author1-mask=2 |last2=Grytczuk |first2=Jarosław |title=Invisible runners in finite fields |journal=Information Processing Letters |date=September 2008 |volume=108 |issue=2 |pages=64–67 |doi=10.1016/j.ipl.2008.03.019}}
-* {{cite journal |last1=Czerwiński |first1=Sebastian |title=The lonely runner problem for lacunary sequences |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |date=May 2018 |volume=341 |issue=5 |pages=1301–1306 |doi=10.1016/j.disc.2018.02.002}}
 * {{Cite journal |last1=Dubickas |first1=A. |doi=10.3336/gm.46.1.05 |title=The lonely runner problem for many runners |journal=Glasnik Matematicki |volume=46 |pages=25–30 |year=2011 |url=http://hrcak.srce.hr/file/102788}}
-* {{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}}
 * {{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}}
+* {{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}}
 * {{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}}
+* {{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 }}
 {{refend}}
 == External links ==
-*[http://garden.irmacs.sfu.ca/?q=op/lonely_runner_conjecture Article in the Open Problem Garden] no. 4, 551–562.
+*[http://www.openproblemgarden.org//?q=op/lonely_runner_conjecture Article in the Open Problem Garden] no. 4, 551–562.
 {{DEFAULTSORT:Lonely Runner Conjecture}}