A Note on the Lonely Runner Conjecture

Ram Krishna Pandey Département de Mathématiques Université Jean Monnet 23, rue Dr. Paul Michelon 42023 Saint-Etienne France

         ram.krishna.pandey@univ-st-etienne.fr

Abstract

Suppose n runners having nonzero distinct constant speeds run laps on a unit-length circular track. The Lonely Runner Conjecture states that there is a time at which all the n runners are simultaneously at least 1/(n + 1) units from their common starting point. The conjecture has been already settled up to six (n ≤ 6) runners and it is open for seven or more runners. In this paper the conjecture has been proved for two or more runners provided the speed of the (i + 1)th runner is more than double the speed of the ith runner for each i, arranged in an increasing order.

1 Introduction and Summary

The conjecture in its original form stated by Wills [10] and also independently by Cusick [6] is as follows:

For any n positive integers w_{1}, w_{2}, …, w_{n}, there is a real number x such that

∥w_{i}x∥ ≥ \frac{1}{n + 1},

for each i = 1, 2, …, n, where for a real number x, ∥x∥ is the distance of x from the nearest integer.

Due to the interpretation by Goddyn [4], the conjecture is now known as the “Lonely Runner Conjecture”.

Suppose n runners having nonzero distinct constant speeds run laps on a unitlength circular track. Then there is a time at which all the n runners are simultaneously at least 1/(n + 1) units from their common starting point.

The term “lonely runner” reflects an equivalent formulation in which there are n + 1 runners with distinct speeds.

Suppose n+1 runners having nonzero distinct constant speeds run laps on a unitlength circular track. A runner is called lonely if the distance (on the circular track) between him (or her) and every other runner is at least 1/(n + 1). The conjecture is equivalent to asserting that for each runner there is a time when he (or she) is lonely.

The case n = 2 is very simple. For n = 3, Betke and Wills [3] settled the conjecture while Wills was dealing with some Diophantine approximation problem and also independently by Cusick [6] while Cusick was considering n-dimensional “view-obstruction” problem. The case n = 4 was first proved by Cusick and Pomerence [7] with a proof that requires a work of electronic case checking. Later, Bienia et al. [4] gave a simpler proof for n = 4. The case n = 5 was proved by Bohman, Holzman and Kleitman [5]. A simpler proof for the case n = 5 was given by Renault [9]. Recently, Barajas and Serra ([1], [2]) proved the conjecture for n = 6. Goddyn and Wong [8] gave some tight instances of the lonely runner. For n ≥ 7 the conjecture is still open. We prove the conjecture for two or more runners provided the speed of the (i + 1)th runner is more than double the speed of the ith runner for each i, with the speeds arranged in an increasing order.

2 Main Result

Theorem 1. Let M = \{m_{1}, m_{2}, …, m_{n}\} where n ≥ 2, and (\frac{m_{j+1}}{m_{j}})(\frac{n−1}{n+1}) ≥ 2 for each j = 1, 2, …, n − 1. Then there exists a real number x such that

∥m_{j}x∥ ≥ \frac{1}{n + 1},

for each j = 1, 2, …, n.

Proof. Consider an interval I = [u, v] = [\frac{1}{m_{1}(n+1)}, \frac{n}{m_{1}(n+1)}]. Clearly, for x ∈ I, we have ∥m_{1}x∥ ≥ \frac{1}{n+1}, and v − u = \frac{1}{m_{1}} (\frac{n−1}{n+1}). Let us denote the interval I by I_{1}. We now construct the intervals I_{2}, I_{3}, … I_{n} satisfying the following properties:

(a) I_{1} ⊃ I_{2} ⊃ I_{3} ⊃ … ⊃ I_{n}

(b) For I_{j} = [u_{j}, v_{j}], v_{j} − u_{j} = \frac{1}{m_{j}} (\frac{n−1}{n+1})

(c) For each x ∈ I_{j} we have ∥m_{j}x∥ ≥ \frac{1}{n+1} Clearly, I_{1} satisfies (b) and (c). Inductively, we now define the jth interval I_{j} = [u_{j}, v_{j}]. We have

m_{j}v_{j−1} − m_{j}u_{j−1} = \frac{m_{j}}{m_{j−1}} (\frac{n − 1}{n + 1}) ≥ 2.

Therefore, there exists an integer ℓ(j) such that

m_{j}u_{j−1} ≤ ℓ(j) < ℓ(j) + 1 ≤ m_{j}v_{j−1} ⇒ u_{j−1} ≤ \frac{ℓ(j)}{m_{j}} < \frac{ℓ(j) + 1}{m_{j}} ≤ v_{j−1}.

Define,

I_{j} = [u_{j}, v_{j}] = [\frac{ℓ(j) + \frac{1}{n+1}}{m_{j}} , \frac{ℓ(j) + \frac{n}{n+1}}{m_{j}} ] .

It can be seen easily that the interval I_{j} satisfies all (a), (b) and (c). Since the intersection of the intervals I_{1}, I_{2}, … I_{n} is nonempty therefore, we have the theorem.

In the theorem we have seen that the n runners having their speeds r_{1}, r_{2}, …, r_{n} with (\frac{r_{j+1}}{r_{j}})(\frac{n−1}{n+1}) ≥ 2 satisfy the Lonely Runner Conjecture.

3 Acknowledgements

I am very much thankful to the referee for his/her useful suggestions to present the paper in a better form.

References

[1] J. Barajas and O. Serra, Regular chromatic number and the lonely runner problem, Electron. Notes Discrete Math., 29 (2007), 479–483.

[2] J. Barajas and O. Serra, The lonely runner with seven runners, Electron. J. Combin., 15 (2008), Paper # R48.

[3] U. Betke and J. M. Wills, Untere Schranken für zwei diophantische Approximations-Funktionen, Monatsh. Math., 76 (1972), 214–217.

[4] W. Bienia, L. Goddyn, P. Gvozdjak, A. Sebő and M. Tarsi, Flows, view obstructions and the lonely runner, J. Combin. Theory Ser. B, 72 (1998), 1–9.

[5] T. Bohman, R. Holzman and D. Kleitman, Six lonely runners, Electron. J. Combin., 8 (2001), Paper # R3.

[6] T. W. Cusick, View-obstruction problems in n-dimensional geometry, J. Combin. Theory Ser. A, 16 (1974), 1–11.

[7] T. W. Cusick and C. Pomerance, View-obstruction problems III, J. Number Theory , 19 (1984), 131–139.

[8] L. Goddyn and E. B. Wong, Tight instances of the lonely runner, Integers, 6 (2006), Paper A38.

[9] J. Renault, View-obstruction: a shorter proof for six lonely runners, Discrete Math., 287 (2004), 93–101.

[10] J. M. Wills, Zwei Sätze uber inhomogene diophantische Approximation von Irrationalzahlen, Monatsh. Math., 71 (1967), 263–269.

2000 Mathematics Subject Classification: Primary 11B50; Secondary 11B75, 11A99. Keywords: integers, distance from the nearest integer.

Received April 16 2009; revised version received June 4 2009. Published in Journal of Integer Sequences, June 5 2009.

Return to Journal of Integer Sequences home page.