Lonely runner conjecture: Difference between revisions

Browse history interactively

← Previous edit Next edit →

Content deleted Content added

VisualWikitext

Inline

Revision as of 07:27, 3 May 2022

Unsolved problem in mathematics:

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

(more unsolved problems in mathematics)

In number theory, the lonely runner conjecture is a conjecture about the long-term behavior of runners on a circular track. It states that $n$ runners, with nonzero 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; 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.

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 and all distinct. 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] the runner to be lonely is fixed at 0 (with zero speed), and therefore $n-1$ other runners are considered.^[a] The conjecture then states that, for any collection $v_{1},v_{2},...,v_{n-1}>0$ of distinct speeds, there exists $t>0$ such that $\{v_{i}t\}\in [1/n,(n-1)/n]\qquad (i=1,...,n-1),$ where $\{x\}$ denotes the fractional part of $x$ .^[5] Wills' conjecture was part of his work in Diophantine approximation.^[6]

Implications

Suppose $C$ is a closed convex body in $\mathbb {R} ^{n}$ ( $n\geq 2$ ) containing the origin, and infinitely many copies scaled by some factor $\alpha$ are placed at points at nonnegative half-integer coordinates. The view-obstruction problem for $C$ asks for the minimum $\alpha$ for which any ray from the origin into the positive orthant hits at least one copy of $C$ . Cusick (1973) made an independent formulation of the lonely runner conjecture in this context. The conjecture implies that if $C$ is a unit n-hypercube centered at the origin, then the solution is $\lambda (n)=(n-1)/(n+1)$ .^[7] For example, $\lambda (2)=1/3$ , as shown.

In graph theory, a distance graph $G(\mathbb {Z} ,D)$ on the vertex set $\mathbb {Z}$ of integers, and some finite set $D$ of positive integers, has an edge between $x,y\in \mathbb {Z}$ 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. The lonely runner conjecture implies that if $\gcd(D)=1$ , the chromatic number of the distance graph is at most $|D|+1$ .^[8]

Given an directed graph $G$ , a nowhere-zero flow network 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. If $f$ is further restricted to positive integers, the lonely runner conjecture implies that, if $f$ attains at most $k$ different values, then it takes on at least one value in $\{1,2,\ldots ,k\}$ . 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.^[9]

Known results

Let the gap of loneliness^[10] $\delta _{n}$ denote the smallest of the maximal gaps attained across all cases for $n$ runners. If correct, the upper bound $\delta _{n}=1/n$ is sharp. For example, if the lonely runner is fixed and speeds $v_{i}=i$ are chosen, then there is no time at which the lonely runner is strictly more than $1/n$ units away from all others.^[b] Alternatively, this conclusion is a corollary of the Dirichlet approximation theorem. A simple lower bound $\delta _{n}\geq 1/2n$ may be obtained via a covering argument.^[11]

The conjecture can be reduced to restricting the runners' speeds to positive integers: If the conjecture is true for $n-1$ runners with integer speeds, it is true for $n$ numbers with real speeds.^[12]

Tighter bounds

Slight improvements on the lower bound $1/2n$ 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}}+{\frac {c\log n}{n^{2}(\log \log n)^{2}}}$ for a 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 number of cases, but the number of cases grows too quickly.^[13]

The conjecture has been proven under specific assumptions on the runners' speeds. If $n\geq 33$ and ${\frac {v_{i+1}}{v_{i}}}\geq 1+{\frac {22\log(n-1)}{n-1}}.$ then the minimum gap of loneliness is $1/n$ . In other words, the conjecture holds true for $n\geq 33$ if the speeds grow quickly enough.^[14] A slightly stronger result for $n\geq 40$ only requires a similar assumption on the first $\lfloor n/21\rfloor$ speeds.^[13] In a similar fashion but unconditionally on $n$ , the conjecture is true if $v_{i+1}/v_{i}\geq 2$ .^[15]

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.^[16] 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. All have since been proved with elementary methods.^[17]

For some $n$ , there exist sporadic examples with a maximum separation of $1/n$ besides the example of $v_{i}=i$ given above.^[5] For $n=5$ , the only other example is $v_{i}=s(1,3,4,7)$ (omitting the stationary runner), where $s>0$ is an arbitrary scaling factor; for $n=6$ the only example is $v_{i}=s(1,3,4,5,9)$ ; and for $n=8$ the only example is $v_{i}=s(1,4,5,6,7,11,13)$ .^[18] All solutions for $n\leq 20$ are known through exhaustive computer search, and there exists an explicit infinite family of extremal examples.^[19]

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/(sn+1)$ for some positive integer $s$ , or $\delta \geq 1/(n-1)$ , where $\delta$ is the gap of loneliness. He confirmed this conjecture for $n\leq 3$ and a few special cases.

Other results

A much stronger result exists for randomly chosen speeds: if $n$ and $\varepsilon >0$ is fixed and the 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.^[20] 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.^[21] The conjecture has been generalized to an analog in algebraic function fields.^[22]

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)$ .^[4]
^ For the 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.^[5]

Citations

^ Bohman, Holzman & Kleitman 2001, p. 1.
^ Bienia et al. 1998, p. 3.
^ Wills 1967.
^ Tao 2018.
^ ^a ^b ^c Bohman, Holzman & Kleitman 2001, p. 2.
^ Wills 1967; Betke & Wills 1972.
^ Cusick 1974, p. 1.
^ Barajas & Serra 2008b.
^ 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.
——; —— (2008b). "Distance graphs with maximum chromatic number". Discrete Mathematics. 308 (8): 1355–1365. doi:10.1016/j.disc.2007.07.061.
——; —— (September 2009). "On the chromatic number of circulant graphs". Discrete Mathematics. 309 (18): 5687–5696. doi:10.1016/j.disc.2008.04.041.
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}.
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.
Bohman, Tom; Holzman, Ron; Kleitman, Dan (February 2001). "Six lonely runners". The Electronic Journal of Combinatorics: R3–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". Mathematika. 65 (3): 677–701. doi:10.1112/S002557931900007X.
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.
——; 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.
Czerwiński, Sebastian (May 2018). "The lonely runner problem for lacunary sequences". Discrete Mathematics. 341 (5): 1301–1306. doi:10.1016/j.disc.2018.02.002.
Dubickas, A. (2011). "The lonely runner problem for many runners". Glasnik Matematicki. 46: 25–30. doi:10.3336/gm.46.1.05.
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. doi:10.37236/5123.
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.
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.
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.

External links

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

[5] 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)$ .^[4]

[12] For the 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.^[5]

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

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

[FOOTNOTEWills1967-3] Wills 1967.

[FOOTNOTETao2018-4] Tao 2018.

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

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

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

[FOOTNOTEBarajasSerra2008b-9] Barajas & Serra 2008b.

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

[FOOTNOTEPerarnauSerra2016-11] Perarnau & Serra 2016.

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

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

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

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

[FOOTNOTEBarajasSerra2009-17] Barajas & Serra 2009.

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

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

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

[FOOTNOTEGoddynWong2006-21] Goddyn & Wong 2006.

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

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

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

[1]

[2]

[3]

[a]

[5]

[6]

[7]

[8]

[9]

[10]

[b]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[4]

@@ Line 16: / Line 16: @@
 [[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 <math>\lambda(2)=1/3</math> 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.]]
-Suppose <math>C</math> is a closed [[convex set|convex]] body in <math>\mathbb{R}^n</math> (<math>n \geq 2</math>) containing the origin, and infinitely many copies scaled by some factor <math>\alpha</math> are placed at points at nonnegative half-integer coordinates. The ''view-obstruction problem'' for <math>C</math> asks for the minimum <math>\alpha</math> for which any ray from the origin into the positive [[orthant]] hits at least one copy of <math>C</math>. {{harvtxt|Cusick|1973}} made an independent formulation of the lonely runner conjecture in this context. The conjecture implies that if <math>C</math> is a unit ''n''-hypercube centered at the origin, then the solution is <math>\lambda(n)=(n-1)/(n+1)</math>.{{Sfn|Cusick|1974|p=1}} For example, <math>\lambda(2)=1/3</math>, as shown.
+Suppose <math>C</math> is a closed [[convex set|convex]] body in <math>\mathbb{R}^n</math> (<math>n \geq 2</math>) containing the origin, and infinitely many copies scaled by some factor <math>\alpha</math> are placed at points at nonnegative half-integer coordinates. The ''view-obstruction problem'' for <math>C</math> asks for the minimum <math>\alpha</math> for which any ray from the origin into the positive [[orthant]] hits at least one copy of <math>C</math>. {{harvtxt|Cusick|1973}} made an independent formulation of the lonely runner conjecture in this context. The conjecture implies that if <math>C</math> is a unit ''n''-[[hypercube]] centered at the origin, then the solution is <math>\lambda(n)=(n-1)/(n+1)</math>.{{Sfn|Cusick|1974|p=1}} For example, <math>\lambda(2)=1/3</math>, as shown.
 In [[graph theory]], a distance graph <math>G(\mathbb{Z},D)</math> on the vertex set <math>\mathbb{Z}</math> of integers, and some finite set <math>D</math> of positive integers, 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. The lonely runner conjecture implies that if <math>\gcd(D)=1</math>, the [[chromatic number]] of the distance graph is at most <math>|D|+1</math>.{{sfn|Barajas|Serra|2008b}}