Correlation among runners and some results

on the Lonely Runner Conjecture∗

Guillem Perarnau
School of Mathematics
University of Birmingham
Birmingham, B15 2TT, UK.
g.perarnau@bham.ac.uk

Oriol Serra
Departament de Matemàtiques, Universitat Politècnica de Catalunya, and
Barcelona Graduate School of Mathematics
Barcelona, Spain
oriol.serra@upc.edu

Submitted: Mar 21, 2015; Accepted: Feb 28, 2016; Published: Mar 18, 2016
Mathematics Subject Classifications: 11B75, 11J13, 11J71.

Abstract
The Lonely Runner Conjecture, posed independently by Wills and by Cusick,
states that for any set of runners running along the unit circle with constant different
speeds and starting at the same point, there is a time where all of them are far
enough from the origin. We study the correlation among the time that runners
spend close to the origin. By means of these correlations, we improve a result of
Chen on the gap of loneliness. In the last part, we introduce dynamic interval graphs
to deal with a weak version of the conjecture thus providing a new result related to
the invisible runner theorem of Czerwiński and Grytczuk.

1 Introduction
The Lonely Runner Conjecture was posed independently by Wills [22] in 1967 and Cu-
sick [10] in 1982. Its picturesque name comes from the following interpretation due to
Goddyn [5]. Consider a set of k runners on the unit circle running with different constant
∗
The authors would like to thank Jarek Grytczuk for suggesting the use of dynamic graphs in the
last part of the paper. This research was supported by the Spanish Research Council under project
MTM2014-54745-P and by the Catalan Research Council under grant 2014 SGR 1147.

the electronic journal of combinatorics 23(1) (2016), #P1.50 1

speeds and starting at the origin. The conjecture states that, for each runner, there is a
time where she is at distance at least 1/k on the circle from all the other runners.
For any real number x, denote by kxk, the distance from x to the closest integer

kxk = min{x − bxc, dxe − x} ,

and by
{x} = x − bxc,
its fractional part.
By assuming that one of the runners has zero speed, the conjecture can be easily seen
to be equivalent to the following one.

Conjecture 1 (Lonely Runner Conjecture). For every n > 1 and every set of nonzero
speeds v1 , . . . , vn , there exists a time t ∈ R such that
1
ktvi k > ,
n+1
for every i ∈ [n].

If true, the Lonely Runner Conjecture is best possible: for the set of speeds,

vi = i for every i ∈ [n] , (1)

1
there is no time for which all the runners are further away from the origin than n+1 . An
infinite family of additional extremal sets for the conjecture can be found in [17].
The conjecture is obviously true for n = 1, since at some point ktv1 k = 1/2, and it is
also easy to show that it holds for n = 2. Many proofs for n = 3 are given in the context
of diophantine approximation (see [4, 10]). A computer–assisted proof for n = 4 was given
by Cusick and Pomerance motivated by a view-obstruction problem in geometry [11], and
later Biena et al. [5] provided a simpler proof by connecting it to nowhere zero flows
in regular matroids. The conjecture was proved for n = 5 by Bohmann, Holzmann and
Kleitman [6]. Barajas and Serra [3] showed that the conjecture holds for n = 6 by studying
the regular chromatic number of distance graphs.
In [6], the authors also showed that the conjecture can be reduced to the case where
all speeds are positive integers and in the sequel we will assume this to be the case. In
particular, we also may assume that t takes values on the (0, 1) unit interval, since if
t ∈ Z, then ktvi k = 0 for all i ∈ [n].
Czerwiński [12] proved a strengthening of the conjecture if all the speeds are chosen
uniformly at random among all the n-subsets of [N ]. In particular, Czerwiński’s result
implies that, for almost all sets of runners, as N → ∞ there is a time where all the runners
are arbitrarily close to 1/2. The dependence of N with respect to n for which this result
is valid was improved by Alon [1] in the context of colorings of Cayley graphs.

the electronic journal of combinatorics 23(1) (2016), #P1.50 2

 Dubickas [14] used a result of Peres and Schlag [20] in lacunary integer sequences to
prove that the conjecture holds if the sequence of increasing speeds grows fast enough; in
particular, for n sufficiently large, if
vi+1 22 log n
>1+ , (2)
vi n
for every 1 6 i < n. These results introduce the use of the Lovász Local Lemma to deal
with the dependencies among the runners. Recently, Tao showed in his blog [21], how to
2
reduce the problem to the case where no speed is larger than ncn , for some c > 0.
Another approach to the conjecture is to reduce the gap of loneliness. That is, to show
1
that, for some fixed δ 6 n+1 and every set of nonzero speeds, there exists a time t ∈ [0, 1)
such that

ktvi k > δ for every i ∈ [n] . (3)

For this approach it is particularly useful to define the following sets,

Ai = {t ∈ [0, 1) : ktvi k < δ} .

For every t ∈ Ai , we will say that the i–th runner is δ–close to the origin at time t.
Otherwise, we will say that the runner is δ–far from the origin at time t.
The set Ai can be thought of as an event in the probability space [0, 1) with the
uniform distribution. Notice that we have Pr(Ai ) = 2δ independently from the value of
vi . In this setting, if
n
!
\
Pr Ai > 0 , (4)
i=1

then, there exists a time t for which (3) holds.

Here it is also
Pconvenient to consider the indicator random variables Xi for the events
n
Ai . Let X = i=1 Xi count the number of runners which are δ–close to the origin
at a time t ∈ (0, 1) chosen uniformly at random. Then, condition (4) is equivalent to
Pr(X = 0) > 0.
A first straightforward result in this direction is obtained by using the union bound
1
in (4). For any δ < 2n , we have
n
! n
\ X
Pr Ai > 1 − Pr(Ai ) = 1 − 2δn > 0 .
i=1 i=1

This result was improved by Chen [7] who showed that, for every set of n nonzero
speeds, there exists a time t ∈ R such that
1
ktvi k > 1 , (5)
2n − 1 + 2n−3

the electronic journal of combinatorics 23(1) (2016), #P1.50 3

for every i ∈ [n].
If 2n − 3 is a prime number, then the previous result was extended by Chen and
Cusick [8]. In this case, these authors proved that, for every set of n speeds, there exists
a time t ∈ R such that
1
ktvi k > ,
2n − 3
for every i ∈ [n]. We give a seemingly simpler proof of this result in Section 4. Unfortu-
nately, both proofs strongly use the fact that 2n − 3 is a prime.
In order to improve (5), we exactly compute the pairwise join probabilities Pr(Ai ∩Aj ),
the amount of time that two runners spend close to the origin at the same time. As a
corollary, we give the following lower bound on E(X 2 ).

Proposition 2. For every δ such that δ → 0 when n → +∞, we have

    
2 1
E(X ) > 2δn δ 1 + Ω n+1 .
log δ −1

Then, we are able to improve Chen’s result on the gap of loneliness around the origin.

Theorem 3. For every sufficiently large n and every set v1 , . . . , vn of nonzero speeds there
exists a time t ∈ [0, 1) such that
1
ktvi k > ,
2n − 2 + o(1)

for each i ∈ [n].

The proof of Theorem 3 uses a Bonferroni–type inequality due to Hunter [19] (see
Lemma 13) that improves the union bound with the knowledge of pairwise intersections.
While the improvement of Theorem 3 is modest, we point out that this is the best result
up to date on the Lonely Runner Conjecture for a general sequence of speeds (provided
that n is large).
The bound on δ in Theorem 3 can be substantially improved in the case of sets of
speeds taken from a sequence with divergent sum of inverses. More precisely the following
result is proven.

Theorem 4. For every set v1 , . . . , vn of nonzero speeds there exists a time t ∈ [0, 1) such
that
1
ktvi k >  Pn 1  ,
2 n − i=2 vi

for each i ∈ [n].

The condition (2) of Dubickas [14] implies that the conjecture is true if the speeds grow
sufficiently fast. Theorem 4 is interesting in the sense that it provides meaningful bounds
for the opposite case, that is when the speeds grow slowly. In particular, if vi , 1 6 i 6 n

the electronic journal of combinatorics 23(1) (2016), #P1.50 4

 Pn 1
is a sequence of speeds satisfying i=1 vi = ω(1), then there exists a time t ∈ [0, 1) such
that
1
ktvi k > ,
2n − ω(1)
for every i ∈ [n]. The last inequality holds under a natural density condition on the set
of speeds which covers the more difficult cases where the speeds grow slowly.
Another interesting result on the Lonely Runner Conjecture, was given by Czerwiński
and Grytczuk [13]. Given a set of n runners, we say that a runner k ∈ [n] is almost alone
at time t if there exists a j 6= k such that
1
kt(vi − vk )k > ,
n+1
for every i 6= j, k. If this case we say that j leaves k almost alone. We do a slight abuse of
notation by saying that a point x ∈ [0, 1) is almost alone at time t if there exists a j 6= k
1
such that kt(vi − x)k > n+1 , for every i 6= j, k.
In [13], the authors showed that every runner is almost alone at some time. This
means that Conjecture 1 is true if we are allowed to make one runner invisible, that is,
there exists a time when all runners but one are far enough from the origin.
Theorem 5 ([13]). For every n > 1 and every set of nonzero speeds v1 , . . . , vn , there exist
a time t ∈ [0, 1) such that the origin is almost alone at time t.
A similar result can be derived by using a model of dynamic circular interval graphs.
By using this model we can show that either there is a runner alone at some time or at
least four runners are almost alone at the same time.
Theorem 6. For every set of different speeds v1 , . . . , vn+1 , there exist a time t ∈ (0, 1)
such that, at time t, either there is a runner alone or four different runners are almost
alone.
The paper is organized as follows. In Section 2 we compute the pairwise join probabil-
ities for the events Ai and give a proof for Proposition 2. As a corollary of these results,
we also prove Theorem 3 and Theorem 4 (Subsection 2.1). In Section 3 we introduce an
approach on the problem based on dynamic circular interval graphs and prove Theorem 6.
Finally, in Section 4 we give some conclusions, discuss some open questions and give a
proof of the improved bound 1/(2n − 3) when 2n − 3 is a prime which uses a combination
of the ideas presented in this paper and a technique from [3].

2 Correlation among runners

In this section we want to study the pairwise join probabilities Pr(Ai ∩ Aj ), for every
i, j ∈ [n]. Notice first, that, if Ai and Aj were independent events, then we would have
Pr(Ai ∩ Aj ) = 4δ 2 , since Pr(Ai ) = 2δ for every i ∈ [n]. This is not true in the general
case, but, as we will see later on, some of these pairwise probabilities can be shown to be
large enough.

the electronic journal of combinatorics 23(1) (2016), #P1.50 5

 For each ordered pair (i, j) with i, j ∈ [n], we define
 
vi
εij = δ , (6)
gcd(vi , vj )
where gcd(vi , vj ) denotes the greatest common divisor of vi and vj and {·} is the fractional
part.
Let us also consider the function f : [0, 1)2 → R, defined by
f (x, y) = min(x, y) + max(x + y − 1, 0) − 2xy . (7)
The proofs of Propositions 7 and 8 below are based on the proofs of lemmas 3.4 and 3.5
in Alon and Ruzsa [2]. Let us start by studying the case when the speeds vi and vj are
coprime.
Proposition 7. Let vi and vj be coprime positive integers and 0 < δ < 1/4. Then
2f (εij , εji )
Pr(Ai ∩ Aj ) = 4δ 2 + .
vi vj
Proof. Observe that Ai and Aj can be expressed as the disjoint unions of intervals
v[i −1   vj −1  
k k [ l l
Ai = − α, + α Aj = − β, + β
k=0
vi vi l=0
vj vj

where α = δ/vi and β = δ/vj and we consider the elements in [0, 1) modulo 1. We observe
that α + β = δ(vi + vj )/vi vj < 1/2 since δ < 1/4.
Denote by I = (−α, α) and J = (−β, β). We have
 
[
Pr(Ai ∩ Aj ) = Pr  (I + k/vi ) ∩ (J + l/vj )
k6vi ,l6vj
X
= Pr((I + k/vi ) ∩ (J + l/vj ))
k6vi ,l6vj
X
= Pr(I ∩ (J + l/vj − k/vi ))
k6vi ,l6vj
vi vj −1
X
= Pr (I ∩ (J + k/vj vi )) ,
k=0

where in the last equality we used the fact that gcd(vi , vj ) = 1.

For each −1/2 < x < 1/2, define d(x) = Pr(I ∩ (J + x)). Let us assume that vj < vi .
We can write d(x) as follows (see Figure 1):


 β + α + x, x ∈ [−(β + α), −(β − α)]
2α, x ∈ [−(β − α), β − α]

d(x) =

 β + α − x, x ∈ [β − α, β + α]
0 otherwise


the electronic journal of combinatorics 23(1) (2016), #P1.50 6

 Figure 1: Plot of d(x) in (−1/2, 1/2).

By symmetry, we have
   
Pr(Ai ∩ Aj ) d(0) X k X k
= + d = α+ min 2α, β + α − .
2 2 vi vj vi vj
16k6(β+α)vi vj 16k6(β+α)vi vj

Write αvi vj = p+εji and βvi vj = q+εij , where p and q are integers and 0 6 εji , εij < 1.
Observe that
  
q−p 2(p + εji ), if εji 6 εij
d vi vj = = 2p + εji + min(εji , εij ) ,
vi vj 2p + εji + εij , if εji > εij

and that
  
q+p+1 0, if εji + εij 6 1
d vi vj = = max(0, εji + εij − 1) .
vi vj εji + εij − 1, if εji + εij > 1

Therefore,
Pr(Ai ∩ Aj ) X
vi vj = p + εji + min(2(p + εji ), q + p + εji + εij − k)
2 16k6p+q+ε ji +εij

q−p−1
X
= p + εji + 2(p + εji ) + 2p + εji + min(εji , εij )
k=1
p+q
X
+ (q + p + εji + εij − k) + max(0, εji + εij − 1)
k=q−p+1

= 2(p + εji )(q + εij ) + f (εji , εij ) .

Thus,
2 2f (εji , εij )
Pr(Ai ∩ Aj ) = (2(p + εji )(q + εij ) + f (εji , εij )) = 4δ 2 + .
vi vj vi vj
Proposition 7 can be easily generalized to pairs of speeds that are not coprime.

the electronic journal of combinatorics 23(1) (2016), #P1.50 7

Proposition 8. Let vi and vj be positive integers and 0 < δ < 1/4. Then
2(gcd(vi , vj ))2 f (εji , εij )
Pr(Ai ∩ Aj ) = 4δ 2 + .
vi vj
v
Proof. Consider vi0 = gcd(vvii ,vj ) and vj0 = gcd(vji ,vj ) . Define A0i = {t ∈ [0, 1) : ktvi0 k < δ} and
A0j = {t ∈ [0, 1) : ktvj0 k < δ}. Observe that
Pr(Ai ∩ Aj ) = Pr(A0i ∩ A0j ) .
The proof follows by applying Proposition 7 to vi0 and vj0 , which are coprime.
Corollary 9. Let vi and vj be positive integers and 0 < δ < 1/4. Then,
Pr(Ai ∩ Aj ) > 2δ 2 . (8)
Moreover, if vj < vi , then
gcd(vi , vj )
Pr(Ai ∩ Aj ) > 2δ . (9)
vi
Proof. We observe that, for x, y 6 1, we have that min(x, y) > xy and thus f (x, y) > −xy.
Therefore Proposition 8 leads to the following lower bound,
2(gcd(vi , vj ))2 f (εij , εji ) 2(gcd(vi , vj ))2 εij εji
Pr(Ai ∩ Aj ) = 4δ 2 + > 4δ 2 − > 2δ 2 .
vi vj vi vj
Moreover, if vj < vi , from the proof of Proposition 7 with vi0 = vi / gcd(vi , vj ),
2δ 2 gcd(vi , vj )δ
Pr(Ai ∩ Aj ) > d(0) = 0
= .
vi vi
By using (8), we can provide a first lower bound on the second moment of X,
X n
X
E(X 2 ) = Pr(Ai ∩ Aj ) + Pr(Ai ) > 2δ 2 n(n − 1) + 2δn > 2δn(δ(n − 1) + 1) . (10)
i6=j i=1

We devote the rest of this section to improve (10). Let us first show for which values is f
nonnegative.
Lemma 10. The function f (x, y) is nonnegative in [0, 1/2]2 and in [1/2, 1)2 .
Proof. If 0 6 x, y 6 1/2, then min(x, y) > 2xy, which implies f (x, y) > 0.
Moreover,
f (1 − x, 1 − y) = min(1 − x, 1 − y) + max(1 − x − y, 0) − 2(1 − x − y + xy)
= min(y, x) + max(0, x + y − 1) − 2xy
= f (x, y) .
Therefore, we also have f (x, y) > 0 for all 1/2 6 x, y < 1.

the electronic journal of combinatorics 23(1) (2016), #P1.50 8

 The following lemma shows that the error term of Pr(Ai ∩Aj ) provided in Proposition 8,
cannot be too negative if vi and vj are either close or far enough from each other.

Lemma 11. Let M > 3 be an integer, γ = M −1 > 0 and vj < vi . If either (1 − γ)vi 6 vj
or γδvi > vj , then
(gcd(vi , vj ))2 f (εij , εji )
> −γδ 2 .
vi vj
Proof. For the sake of simplicity, let us write vi / gcd(vi , vj ) = kδ −1 +x and vj / gcd(vi , vj ) =
lδ −1 +y with k and l being nonnegative integers and 0 6 x, y < δ −1 . In particular, observe
that εij = xδ and εji = yδ. Moreover, we can assume that vi and vj are such that f (εij , εji )
is negative, otherwise, there is nothing to prove.
We split the proof in the two different cases each consisting of some other subcases.
Figure 2 illustrates the subcase considered in each situation.
vi
Case A: ( gcd(v i ,vj )
> (γδ)−1 ): This case covers the case when γδvi > vj , since
vj / gcd(vi , vj ) > 1 and also the case when (1 − γ)vi 6 vj and gcd(vvii ,vj ) > (γδ)−1 .

Subcase A.1 (y 6 x): We have,

(gcd(vi , vj ))2 f (εij , εji ) (gcd(vi , vj ))2 (εji − 2εij εji )

>
vi vj vi vj
(gcd(vi , vj ))2 (yδ − 2xyδ 2 )
=
vi vj
gcd(vi , vj )(1 − 2xδ)
> ·δ ,
vi
where the last inequality holds from the fact that f (εij , εji ) < 0 and y 6 vj / gcd(vi , vj ).
Recall that vi / gcd(vi , vj ) > (γδ)−1 = M δ −1 . Observe also that, since y 6 x and
f (εij , εji ) is negative, by Lemma 10 we have δ −1 /2 6 x < δ −1 . Therefore,

(gcd(vi , vj ))2 f (εij , εji ) gcd(vi , vj )(1 − 2xδ) 1 − 2xδ 2

> δ> δ > −γδ 2 .
vi vj vi M

Subcase A.2 (y > x): Here,

(gcd(vi , vj ))2 f (εij , εji ) (gcd(vi , vj ))2 (εij − 2εij εji )

>
vi vj vi vj
(gcd(vi , vj ))2 x(1 − 2yδ)
= δ
vi vj
gcd(vi , vj )(1 − 2yδ) δ
> · ,
vj M

the electronic journal of combinatorics 23(1) (2016), #P1.50 9

where the last inequality holds from the fact that, in this subcase, M x 6 M δ −1 6
vi / gcd(vi , vj ).
As before, since f (εij , εji ) is negative, by Lemma 10 we have δ −1 /2 6 y < δ −1 and
vj / gcd(vi , vj ) > y. Therefore,

(gcd(vi , vj ))2 f (εij , εji ) gcd(vi , vj )(1 − 2yδ) δ 1 − 2yδ δ

> · > · > −γδ 2 .
vi vj vj M y M

vi
Case B ((1 − γ)vi 6 vj and gcd(v i ,vj )
6 (γδ)−1 ): By Lemma 10 and since
vi
gcd(vi ,vj )
6 (γδ)−1 , we can assume that either k = l, y < δ −1 /2 and x > δ −1 /2 (Subcases
B.1 and B.2) or k = l + 1, y > δ −1 /2 and x < δ −1 /2 (Subcases B.3 and B.4). In all these
cases, (1 − γ)vi 6 vj implies
y > (1 − γ)x − γkδ −1 . (11)

Subcase B.1 (k = l and x+y 6 δ −1 ): Since x+y 6 δ −1 , then max(0, εij +εji −1) =
0.
By using vi / gcd(vi , vj ) = kδ −1 + x, vj / gcd(vi , vj ) = kδ −1 + y > y and the fact that
f (εij , εji ) < 0 we have

(gcd(vi , vj ))2 f (εij , εji ) (gcd(vi , vj ))2 (εji − 2εij εji )

=
vi vj vi vj
(gcd(vi , vj ))2 y(1 − 2xδ)
= δ
vi vj
1 − 2xδ 2
> δ .
k + xδ
1+γk −1
By combining (11) with x + y 6 δ −1 , we get x 6 2−γ
δ . Thus,

2(1+γk)
(gcd(vi , vj ))2 f (εij , εji ) 1 − 2xδ 2 1 − 2−γ 2
> δ > 1+γk
δ = −γδ 2 ,
vi vj k + xδ k + 2−γ

for each k > 0.

Subcase B.2 (k = l and x + y > δ −1 ): Now, max(0, εij + εji − 1) = (x + y)δ − 1.
Then,

(gcd(vi , vj ))2 f (εij , εji ) (gcd(vi , vj ))2 (yδ + (x + y)δ − 1 − 2xyδ 2 )

=
vi vj vi vj
(1 − 2yδ)(xδ − 1)
= δ := g(x, y) .
(kδ −1 + x)(lδ −1 + y)

the electronic journal of combinatorics 23(1) (2016), #P1.50 10

It remains to lower bound g(x, y) in the corresponding area. Observe that ∂x g(x, y) =
(1−2yδ)(k+1)
(kδ −1 +x)2 (lδ −1 +y)
> 0 for every y 6 δ −1 /2. Thus, the local minimum of g(x, y) is attained
in the line x + y = δ −1 . Observe that this case is covered by Case B.1. Following the
steps of the previous case,

(gcd(vi , vj ))2 f (εij , εji )

> −γδ 2 .
vi vj

Subcase B.3 (k = l + 1 and x + y 6 δ −1 ): Now we have max(0, εij + εji − 1) = 0

and min(εij , εji ) = εij . Note that vj > (1 − γ)vi implies that y > (1 − γ)x − (γk − 1)δ −1 .
Then,

(gcd(vi , vj ))2 f (εij , εji ) (gcd(vi , vj ))2 xδ(1 − 2yδ) xδ(1 − 2yδ)
= = := g(x, y) .
vi vj vi vj (kδ + x)(lδ −1 + y)
−1

We aim to lower bound g(x, y) in the corresponding area. We have that ∂x g(x, y) =
(1−2yδ)k
(kδ −1 +x)2 (lδ −1 +y)
6 0 for every y > δ −1 /2. Again, the local minimum of g(x, y) is attained
in the line x + y = δ −1 . A straightforward computation gives,

(4xδ − 1)k 2 − x2 δ 2 3
∂g(x, δ −1 − x) = δ
(k 2 − x2 δ 2 )2
p
√ 0 in x0 = (1 −
which equals 1 − 1/4k 2 )2k 2 δ −1 . Therefore, for every k > 1, we have
x0 6 (2 − 3)δ −1 .
Subcase B.3.1 (k 6 γ −1 /3): In this case, since x0 < 1/3 for every k > 1, the pair
(x0 , δ −1 − x0 ) does not lie in the corresponding area. Thus, the minimum is attained
when x is maximized, that is in the point where the two lines x + y = δ −1 and y =
(1 − γ)x − (γk − 1)δ −1 meet. We obtain
 
γk −1 2 − (k + 1)γ −1 1 (2k + 1)γ − 2
g(x, y) > g δ , δ = −1 −1
· γk .
2−γ 2−γ (kδ + x)(lδ + y) (2 − γ)2

Since x > 0 and l + δy > k − 1/2,

(gcd(vi , vj ))2 f (εij , εji ) 2 − (2k + 1)γ 2 2(2 − 3γ) 2

>− γδ > − γδ > −γδ 2 .
vi vj (2 − γ)2 (k − 1/2) (2 − γ)2

where we used that k > 1.

Subcase
p B.3.2 (k > γ −1 /3): Using the global maximum of g(x, δ −1 − x) in x0 =
(1 − 1 − 1/4k 2 )δ −1 , we have that for any (x, y) in the corresponding area

x0 (2x0 δ − 1) 3 −x0 3 p
g(x, y) > g(x0 , δ −1 − x0 ) = 2 2 2
δ = 2
δ = ( 1 − 1/4k 2 − 1)δ 2 .
k − x0 δ 2k

the electronic journal of combinatorics 23(1) (2016), #P1.50 11

 √
where we used that x20 δ 2 = (4x0 δ − 1)k 2 . Since k > γ −1 /3 and using 1 − x > 1 − x, for
x ∈ (0, 1) we obtain
r !
(gcd(vi , vj ))2 f (εij , εji ) 9γ 2 9γ 2 2
> 1− − 1 δ2 > − δ > −γδ 2 ,
vi vj 4 4

since γ = M −1 6 1/3.
Subcase B.4 (k = l+1 and x+y > δ −1 ): We have max(0, εij +εji −1) = (x+y)δ−1
and min(εij , εji ) = x. Then,

(gcd(vi , vj ))2 f (εij , εji ) (gcd(vi , vj ))2 (2xδ − 1)(1 − yδ)

=
vi vj vi vj
(2xδ − 1)(1 − yδ)
= := g(x, y) .
(kδ −1 + x)(lδ −1 + y)

Now ∂x g(x, y) = (kδ(1−yδ)(2k+1)

−1 +x)2 (lδ −1 +y) > 0 for every δ
−1
/2 6 y 6 δ −1 . As usual, the local
minimum of g(x, y) is attained in the line x + y = δ −1 . Since this case is already covered
by Case B.3, we have

(gcd(vi , vj ))2 f (εij , εji )

> −γδ 2 .
vi vj

The following lemma shows that among a large set of positive numbers, there should
be a pair of numbers satisfying that they are either close or far enough from each other.

Lemma 12. For every c > 1, T > c and every set x1 > . . . > xm+1 > 0 of nonnegative
numbers, with m > logc T , there is a pair i, j ∈ [m + 1], i < j, such that
xi xi
either 6 c or >T .
xj xj

Proof. Suppose that for each pair i < j we have xi > cxj . In particular, for each i 6 m,
we have xi > cxi+1 and x1 > cm xm+1 > T xm+1 . Hence the second possibility holds for
i = 1 and j = m + 1.
For any fixed ε > 0, we call a pair i, j ∈ [n] ε–good if Pr(Ai ∩ Aj ) > (1 − ε)4δ 2 . Now
we are able to improve the lower bound on the second moment of X given in (10).

 (8), for any pair i, j ∈ [n], we have Pr(Ai ∩ Aj ) >

Proof of Proposition 2. Recall that by
2δ 2 . We will show that at least a Ω log1δ−1 fraction of the pairs are ε–good.
Lemma 11 with M = γ −1 = d(2ε)−1 e implies that every pair vj < vi with either
vi /vj 6 (1 − γ)−1 or vi /vj > (γδ)−1 is a (γ/2)–good pair, and thus, also an ε–good pair.
Consider the graph H on the vertex set V (H) = [n], where ij is an edge if and only
if ij is ε–good. Using Lemma 12, with c = (1 − γ)−1 and T = (γδ)−1 we know that there

the electronic journal of combinatorics 23(1) (2016), #P1.50 12

Figure 2: Different cases in the proof of Lemma 11. Grey areas correspond to positive
values of f (εij , εji ) according to Lemma 10.

−1
are no independent sets of size larger than m = dlogc (T )e = d loglogδ c + logc γ −1 e. Since
δ → 0 when n → +∞, if n is large enough, there exists some constant c0ε that depends
−1
only on ε such that m > logcδ0 + 1. Thus, the complement of H, H, has no clique of size
ε
m−2 n 2
m. By the Erdős–Stone theorem (see [15]), |E(H)| 6 (1 + o(1)) m−1 2
, which implies that
there are
n2 c0 n 2
|E(H)| > (1 + o(1)) = (1 + o(1)) ε −1 ,
2(m − 1) 2 log δ
ε–good unordered pairs.

the electronic journal of combinatorics 23(1) (2016), #P1.50 13

 Now, we are able to give a lower bound on the second moment,
X X n
X
2
E(X ) = Pr(Ai ∩ Aj ) + Pr(Ai ∩ Aj ) + Pr(Ai )
ij ε–good ij non ε–good i=1

c0ε n2 c0ε n2
 
2 2
> (1 − ε)4δ + 2δ n(n − 1) − + 2δn
log δ −1 log δ −1
0 2
c0ε
 
2 cε n 2 1
= (1 − ε)4δ + 2δ 1 − − n2 + 2δn
log δ −1 log δ −1 n
   
cε
> 2δn δ 1 + n+1 ,
log δ −1
for some cε that depends only on ε.

Next, we show some applications of our bounds that extend some known results.

2.1 Improving the gap of loneliness

In this subsection we show how to use the result of Proposition 8 on the pairwise join
probabilities to prove Theorem 3. To this end we will use the following Bonferroni–type
inequality due to Hunter [19] (see also Galambos and Simonelli [16]) that slightly improves
the union bound in the case where the events are not pairwise disjoint.
Lemma 13 (Hunter [19]). For any tree T with vertex set V (T ) = [n], we have
n
! n
\ X X
Pr Ai > 1 − Pr(Ai ) + Pr(Ai ∩ Aj ) . (12)
i=1 i=1 ij∈E(T )

As we have
P already mentioned, Pr(Ai ) = 2δ. Thus, it remains to select a tree T that
maximizes ij∈E(T ) Pr(Ai ∩ Aj ).

Lemma 14. For every ε0 > 0 and 0 < δ < 1/4, there exists a tree T on the set of vertices
[n] such that X
Pr(Ai ∩ Aj ) > (1 − ε0 )4δ 2 n .
ij∈E(T )

Proof. Recall that Proposition 8 states that if 0 < δ < 1/4, then

2(vi , vj )2 f (εij , εji )

Pr(Ai ∩ Aj ) = 4δ 2 + .
vi vj

Set M to be the largest integer satisfying M = γ −1 < d(2ε0 )−1 e. We will construct a
large forest F on the set of vertices [n], where all the edges ij ∈ E(F ) are ε0 –good. In
particular they will satisfy,

Pr(Ai ∩ Aj ) > (4 − 2γ)δ 2 > (1 − ε0 )4δ 2 .

the electronic journal of combinatorics 23(1) (2016), #P1.50 14

 Let us show how to select the edges of the forest by a procedure. Set S0 = [n] and
E0 = ∅. In the k-th step, we select different i, j ∈ Sk−1 such that either vi /vj 6 (1 − γ)−1
or vi /vj > (γδ)−1 , and set Ek = Ek−1 ∪ {ij}, Sk = Sk−1 \ {i}. If no such pair exists, we
stop the procedure.
Let τ be the number of steps that the procedure runs before being halted. By
Lemma 12 with c = (1 − γ)−1 and T = (γδ)−1 we can always find such an edge ij,
provided that the set Sk has size at least logc (γδ −1 ). Thus τ > n − logc T . Since the
size of the sets Ek increases exactly by one at each step, we have |Eτ | > n − logc T =
n − O(log δ −1 ) = (1 − o(1))n. Besides, by construction Eτ is an acyclic set of edges:
since we delete one of the endpoints of each selected edge from the set Sk , Eτ induces a
1-degenerate graph or equivalently, a forest.
By Lemma 11, for each edge ij in Eτ we have

Pr(Ai ∩ Aj ) > (4 − 2γ)δ 2 .

Therefore we can construct a spanning tree T on the vertex set [n], that contains the
forest F and thus satisfies
X
Pr(Ai ∩ Aj ) > (1 − o(1)) (4 − 2γ)δ 2 n > (1 − ε0 )4δ 2 n ,
ij∈E(T )

if n is large enough.
Let us proceed to prove Theorem 3.
Proof of Theorem 3. Given an ε > 0, by Lemma 12 and Lemma 14 with ε0 = ε/2 and
0 < δ < 1/4, we have
n
! n
\ X X
Pr Ai > 1 − Pr(Ai ) + Pr(Ai ∩ Aj )
i=1 i=1 ij∈E(T )

> 1 − 2δn(1 − 2(1 − ε0 )δ) .

The expression above is strictly positive for

1 1
δ6 0
= ,
2n − 2 + 2ε 2n − 2 + ε
and the theorem follows if n is large enough.
Theorem 4 follows from the following Corollary.
Corollary 15. For every c > 0, every sufficiently large n and every set of nonzero speeds
v1 , . . . , vn for which there exists a tree T satisfying
X gcd(vi , vj )
>c, (13)
max(vi , vj )
ij∈E(T )

the electronic journal of combinatorics 23(1) (2016), #P1.50 15

then there exists a time t ∈ [0, 1) such that
1
ktvi k > ,
2(n − c)
Pn 1
for every i ∈ [n]. In particular, if i=2 vi = c the same conclusion follows.
Proof. By using inequality (9) we have
X X gcd(vi , vj )
Pr(Ai ∩ Aj ) > 2δ > 2cδ
max(vi , vj )
ij∈E(T ) ij∈E(T )

Using
T Lemma
12 in a similar way as in the proof of Theorem 3, we can obtain that
Pr ni=1 Ai > 0 for every δ < 2(n−c)
1
.
The last part of the corollary follows by considering T to be the star with center in
the smallest of the speeds.

3 Weaker conjectures and interval graphs

In this section we give a proof for Theorem 6. The following weaker conjecture has been
proposed by Spencer1 .
Conjecture 16 (Weak Lonely Runner Conjecture). For every n > 1 and every set of
different speeds v1 , . . . , vn , there exist a time t ∈ R and a runner j ∈ [n], such that
1
kt(vi − vj )k >
n
for every i 6= j.
For every set S ⊆ [n], we say that S is isolated at time t if,
1
kt(vi − vj )k > for each i ∈ S, j ∈ V \ S. (14)
n
Observe that S = {i} is isolated at time t, if and only if, vi is lonely at time t.
To study the appearance of isolated sets, it is convenient to define a dynamic graph
G(t), whose connected components are sets of isolated runners at time t. For each 1 6
i 6 n and t ∈ [0, 1), define the following dynamic interval in [0, 1) associated to the i-th
runner,  
1
Ii (t) = x ∈ [0, 1) : {x − tvi } < .
n
In other words, Ii (t) is the interval that starts at the position of the i-th runner at time
t and has length n1 .
Now we can define the following dynamic circular interval graph G(t) = (V (t), E(t)).
The vertex set V (t) is composed by n vertices ui that correspond to the set of runners,
and two vertices ui and uj are connected if and only if Ii (t) ∩ Ij (t) 6= ∅ (see Figure 3).
1
Transmitted to the authors by Jarek Grytczuk.

the electronic journal of combinatorics 23(1) (2016), #P1.50 16

 Figure 3: An instance of the graph G(t).

Observation 17. The graph G(t) satisfies the following properties,

1. G(0) = Kn .

2. Each connected component of G(t) corresponds to an isolated set of runners at time

t.

3. If ui is isolated in G(t), then vi is alone at time t.

4. All the intervals have the same size, |Ii (t)| = 1/n, and thus, G(t) is a unit circular
interval graph.

We can restate the Lonely Runner Conjecture in terms of the dynamic interval graph
G(t).

Conjecture 18 (Lonely Runner Conjecture). For every i 6 n there exists a time t such
that ui is isolated in G(t).

Let µ be the uniform measure in the unit circle. For every subgraph H ⊆ G(t) we define
µ(H) = µ(∪ui ∈V (H) Ii (t)), the length of the arc occupied by the intervals corresponding to
H. Notice that, if H contains an edge, then

|V (H)|
µ(H) < , (15)
n
since the intervals Ii (t) are closed in one extreme but open in the other one. If H consists
of isolated vertices, then (15) does not hold.
The dynamic interval graph G(t) allows us to prove a very weak version of the con-
jecture. Let us assume that v1 < v2 < · · · < vn .

the electronic journal of combinatorics 23(1) (2016), #P1.50 17

Proposition 19. There exist a time t ∈ R and a nonempty subset S ⊂ [n] such that S is
isolated at time t.
Proof. Let t be the number for which the equation tvn − 1 = tv1 − 1/n holds. This is
the first time that the slowest runner v1 is at distance exactly 1/n ahead from the fastest
runner vn .
For the sake of contradiction, assume that there is just one connected component of
order n. Note that u1 un ∈ / E(G(t)) and since G(t) is connected, there exists a path in
G(t) connecting u1 and un . By (15), we have µ(G) < 1. Thus, there is a point x ∈ [0, 1)
such that x ∈ / Ii (t) for every i ∈ [n].
Observe that, at time t, all the intervals Ii (t) are sorted in increasing order around
[0, 1). Let ` ∈ [n] be such that x > {tv` } and x < {tv`+1 }. Then, {u1 , . . . , u` } and
{u`+1 , . . . , un } are in different connected components since u1 un , u` u`+1 ∈
/ E(G(t)).
Observe that, if one of the parts in Proposition 19 consists of a singleton, say S = {i},
then Conjecture 16 would be true.
Let us show how to use the dynamic graph to prove an invisible lonely runner theorem,
similar to Theorem 5.
Proposition 20. There exists t ∈ [0, 1) such that G(t) has either at least one isolated
vertex or at least four vertices of degree one.
Proof. Define Y : [0, 1) → N by,
Y (t) = |E(G(t))| .

 t ∈ [0,n
1) be chosen uniformly at random. Then Y (t) is a random variable over

Let
0, 1, . . . , 2 . We will show that E(Y (t)) = n − 1. If we are able to do so, since Y (t) is
not constant, by a first moment argument, we know that there exists a time t0 for which
Y (t0 ) 6 n − 2. Then, denoting by di the degree of ui , we have
n
X
di 6 2(n − 2) .
i=1

Suppose that there are no isolated vertices. Then di > 0 for all i and this ensures the
existence of at least 4 vertices of degree one, concluding the proof of the P proposition.
Now, let us show that E(Y (t)) = (n − 1). We can write Y (t) = i<j Yij (t), where
Y
Pij (t) = 1 if ui and
P uj are connected at time t and Yij (t) = 0 otherwise. Then E(Y (t)) =
i<j E(Yij ) = i<j Pr(Ii (t) ∩ Ij (t) 6= ∅). For the sake of simplicity when computing
Pr(Ii (t) ∩ Ij (t) 6= ∅), we can assume that vi = 0. Since the intervals are half open, half
closed, we have Pr(Ii (t) ∩ Ij (t) 6= ∅) = 2/n, no matter the value of vj .
Finally,
X 2 n 2
E(Y (t)) = = =n−1.
i<j
n 2 n

In the dynamic interval graph setting, an invisible runner is equivalent to a vertex u

with a neighbor of degree one, say v. If u is removed, then v becomes isolated in G(t) and
thus, alone in the runner setting. Thus, Theorem 6 is a direct corollary of Proposition 20.

the electronic journal of combinatorics 23(1) (2016), #P1.50 18

4 Concluding remarks and open questions
1. In Proposition 2 we gave a lower bound for E(X 2 ). We believe that this proof can be
adapted to show that E(X 2 ) is larger.

Conjecture 21. For every set of different speeds v1 , . . . , vn , and every δ < 1, we have

E(X 2 ) > (1 + o(1))4δ 2 n2 + 2δn .

The proof of this conjecture relies on showing that either most pairs are ε–good or
the contribution of the positive error terms is larger than the contribution of the negative
ones. On the other hand, notice that it is not true that E(X 2 ) is O(δ 2 n2 ). For the set of
speeds in (1), Cilleruelo [9] has shown that
12
E(X 2 ) = (1 + o(1)) δn log n , (16)
π2
which is a logarithmic factor away from the lower bound in Proposition 2, when δ =
Θ(n−1 ). It is an open question whether (16) also holds as an upper bound for E(X 2 ).
2. Ideally, we would like to estimate the probabilities Pr(∩i∈S Ai ), for every set S ⊆ [n]
of size k. In general, it is not easy to compute such probability. As in (16), the sum of the
k–wise join probabilities are not always of the form O(δ k nk ). However it seems reasonable
to think that, for every set S, we have

Pr(∩i∈S Ai ) > ck δ k ,

where ck depends only on k. Moreover, we know that ck 6 2k , since this is the case when
the speeds {vi }i∈S are rationally independent and the conjecture holds (see e.g. Horvat
and Stoffregen [18].)
The inequality (8) shows that c2 = 2. In general, we also conjecture that

ck = (1 + ok (1))2k .

3. Below we give a short proof of the result by Chen and Cusick [8] improving the
bound on the lonely runner problem with n runners when p = 2n − 3 is a prime number.

Proposition 22. If 2n − 3 is a prime number then, for every set of n speeds, there exists
a time t ∈ R such that
1
ktvi k > ,
2n − 3
for every i ∈ [n].

Proof. Let p = 2n−3. We may assume p > 7. For a positive integer x let νp (x) denote the
smallest power of p in the p–adic expansion of x. Set m = maxi νp (vi ) and N = pm+1 . We
consider the problem in the cyclic group ZN . We will show that there is t ∈ ZN such that
ktvi kN := min{tvi (mod N ), −tvi (mod N )}, that is, the circular distance in ZN from tvi

the electronic journal of combinatorics 23(1) (2016), #P1.50 19

to 0, satisfies ktvi kN > pm = N/p. This clearly implies that ktvi k > 1/p and proves the
Proposition.
If m = 0 then we have kvi kp > 1 for each i and there is nothing to prove, so assume
m > 0.
For each positive integer x we denote by πj (x) the coefficient of pj in the p–adic
expansion of the representative in {0, 1, . . . , N − 1} of x modulo N . We seek a certain t
such that, for each i, πm (tvi ) does not belong to {0, p − 1}. This implies that ktvi kN > pm
for each i, which is our goal.
Partition the set V = {v1 , . . . , vn } of speeds into the sets Vj = {vi : νp (vi ) = j},
j = 0, 1, . . . , m. Since gcd(V ) = 1 we have V0 6= ∅. By the definition of m, we also have
Vm 6= ∅. We consider two cases:
Case 1. |V0 | < n − 1. This implies |Vj | < n − 1 for each j.
For each λ ∈ {1, . . . , p − 1} and each vi ∈ Vm we have πm (λvi ) = λπm (vi ) (mod p),
which is nonzero. By pigeonhole, there is λ such that πm (λvi ) 6∈ {0, p − 1} for each
vi ∈ Vm . (Actually, for speeds in Vm it is enough that πm (λvi ) 6= 0.)
Suppose that there is λj+1 ∈ {0, 1, . . . , p − 1} such that πm (λj+1 vi ) 6∈ {0, p − 1} for
each vi ∈ Vj+1 ∪ Vj+2 ∪ · · · ∪ Vm and some j + 1 6 m. Since |Vj | < n − 1, there is
µ ∈ {0, 1, . . . , p − 1} such that

πm ((1 + µpm−j )vi ) = πm (vi ) + µπj (vi ) (mod p)

does not belong to {0, p − 1} for each vi ∈ Vj . Moreover, for each vi ∈ ∪l>j Vl ,

πm ((1 + µpm−j )λj+1 vi ) = πm (λj+1 vi ).

Therefore, by setting λj = (1 + µpm−j )λj+1 , we have πm (λj vi ) not in {0, p − 1} for each
vi ∈ ∪l>j Vl . Hence the sought multiplier is t = λ0 .
Case 2. |V0 | = n − 1. Thus V = V0 ∪ Vm with |Vm | = 1, say Vm = {vn }. For each
λ ∈ Z∗N we have kλvn kN > pm . We may assume that v1 = 1 (mod N ). Let

Ai = {λ ∈ Z∗N : kλvi kN < pm }

denote the set of bad multipliers for vi . By choosing a multiplier in Z∗N uniformly at
random we have
Pr(Ai ) = 2pm−1 (p − 1)/pm (p − 1) = 2/p.
If we show that Pr(A1 ∩ Ai ) > 2/p(p − 1) for each i = 2, . . . , n − 1 then, by using
Hunter’s inequality 13,

Pr(∩n−1 n
i=1 Ai ) > 1 − Pr(∪i=1 Ai )
n−1 n−1
!
X X
>1− Pr(Ai ) − Pr(A1 ∩ Aj )
 i=1 i=2

1 p−1 2
>1− 1+ − = 0,
p 2 p(p − 1)

the electronic journal of combinatorics 23(1) (2016), #P1.50 20

which implies that there is λ ∈ Z∗N such that kλvi kN > pm for all i, concluding the proof.
Suppose m > 2. Consider the set C = [0, pm ] ∩ Z∗N , so that λ ∈ Ai if and only if
λvi ∈ C ∪ (−C). The pairwise disjoint sets

Cj = {jp + 1, 2(jp + 1), . . . , (p − 1)(jp + 1)}, j = 0, 1, . . . , pm−2 + 1,

satisfy

Cj ⊂ C, (Cj − Cj ) \ {0} = Cj ∪ (−Cj ) and (Cj − Cj ) ∩ (Cj 0 − Cj 0 ) = {0}, j 6= j 0 .

The first inclusion holds because no two elements in Cj are congruent modulo p and the
largest element in Cj is at most (p − 1)(pm−1 + p + 1) = pm − pm−1 + p2 − 1 < pm if m > 3
and (p − 1)(p + 1) = p2 − 1 if m = 2. The last two equalities clearly hold.
Fix i ∈ {2, . . . n − 1}. We have λvi ∈ Z∗N for each λ ∈ Cj and each Cj . By pigeonhole,
if λvi 6∈ C ∪ (−C) for each λ ∈ Cj then there are distinct λ, λ0 ∈ Cj such that λvi , λ0 vi ∈
C + kpm for some k ∈ {1, 2, . . . , p − 2}. Therefore (λ − λ0 )vi ∈ C ∪ (−C). Thus,
for each j there is µ ∈ (Cj − Cj ) \ {0} such that both µvi , −µvi ∈ C ∪ (−C). Since
(Cj − Cj ) ∩ (Cj 0 − Cj 0 ) = {0}, we have

2(pm−2 + 2) 2
Pr(B1 ∩ Bi ) > m−1
> .
p (p − 1) p(p − 1)
It remains to consider the case m = 1. In this case the same argument as above with
an only C0 = {1, 2, . . . , p − 1} suffices to give Pr(B1 ∩ Bi ) > 1/(p − 1).

References
[1] N. Alon. The chromatic number of random Cayley graphs. European J. Combin.,
34(8):1232 – 1243, 2013.
[2] N. Alon and I. Z. Ruzsa. Non-averaging subsets and non-vanishing transversals. J.
Comb. Theory, Ser. A, 86(1):1–13, 1999.
[3] J. Barajas and O. Serra. The lonely runner with seven runners. Electron. J. Combin.,
15(1):#R48, 18 pp., 2008.
[4] U. Betke and J. M. Wills. Untere Schranken für zwei diophantische Approximations-
Funktionen. Monatsh. Math., 76:214–217, 1972.
[5] W. Bienia, L. Goddyn, P. Gvozdjak, A. Sebő, and M. Tarsi. Flows, view obstructions,
and the lonely runner. J. Combin. Theory Ser. B, 72(1):1–9, 1998.
[6] T. Bohman, R. Holzman, and D. Kleitman. Six lonely runners. Electron. J. Combin.,
8(2):Paper 3, 49 pp., 2001.
[7] Y. G. Chen. View-obstruction problems in n-dimensional Euclidean space and a
generalization of them. Acta Math. Sinica, 37(4):551–562, 1994.
[8] Y. G. Chen and T. W. Cusick. The view-obstruction problem for n-dimensional
cubes. J. Number Theory, 74(1):126–133, 1999.

the electronic journal of combinatorics 23(1) (2016), #P1.50 21

 [9] J. Cilleruelo. personal communication, 2012.
[10] T. W. Cusick. View-obstruction problems. II. Proc. Amer. Math. Soc., 84(1):25–28,
1982.
[11] T. W. Cusick and C. Pomerance. View-obstruction problems. III. J. Number Theory,
19(2):131–139, 1984.
[12] S. Czerwiński. Random runners are very lonely. Journal of Combinatorial Theory,
Series A, 119(6):1194–1199, 2012.
[13] S. Czerwiński and J. Grytczuk. Invisible runners in finite fields. Inform. Process.
Lett., 108(2):64–67, 2008.
[14] A. Dubickas. The lonely runner problem for many runners. Glas. Matem., 46(1),
2011.
[15] P. Erdős and A. H. Stone. On the structure of linear graphs. Bull. Amer. Math. Soc,
52:1087–1091, 1946.
[16] J. Galambos and I. Simonelli. Bonferroni-type inequalities with applications. Proba-
bility and its Applications (New York). Springer-Verlag, New York, 1996.
[17] L. Goddyn and E. B. Wong. Tight instances of the lonely runner. Integers, 6:A38,
2006.
[18] C. H. Horvat and M. Stoffregen. A solution to the lonely runner conjecture for almost
all points. arXiv:1103.1662v1, 2011.
[19] D. Hunter. An upper bound for the probability of a union. Journal of Applied
Probability, 13:597–603, 1976.
[20] Y. Peres and W. Schlag. Two Erdős problems on lacunary sequences: chromatic
number and Diophantine approximation. Bull. Lond. Math. Soc., 42(2):295–300,
2010.
[21] T. Tao. https://terrytao.wordpress.com/2015/05/13/a-remark-on-the-lonely-runner-
conjecture. Accessed: 2016-02-15.
[22] J. M. Wills. Zwei Sätze über inhomogene diophantische Approximation von Irra-
tionalzahlen. Monatsh. Math., 71:263–269, 1967.

the electronic journal of combinatorics 23(1) (2016), #P1.50 22