# A few more Lonely Runners

Avinash Bhardwaj  Avinash Bhardwaj,Indian Institute of Technology Bombay,
Mumbai, India 400076<EMAIL_ADDRESS>,  Vishnu Narayanan  Vishnu
Narayanan, Indian Institute of Technology Bombay, Mumbai, India 400076
<EMAIL_ADDRESS>and  Hrishikesh Venkataraman  Hrishikesh Venkataraman,
Indian Institute of Science Education and Research, Pune, India 411008
<EMAIL_ADDRESS>
###### Abstract.

_Lonely Runner Conjecture_ , proposed by Jörg M. Wills and so nomenclatured by
Luis Goddyn, has been an object of interest since it was first conceived in
1967 : Given positive integers $k$ and $n_{1},n_{2},\ldots,n_{k}$ there exists
a positive real number $t$ such that the distance of $t\cdot n_{j}$ to the
nearest integer is at least $\frac{1}{k+1}$, $\forall~{}~{}1\leq j\leq k$. In
a recent article Beck, Hosten and Schymura described the Lonely Runner
polyhedron and provided a polyhedral approach to identifying families of
lonely runner instances. We revisit the Lonely Runner polyhedron and highlight
some new families of instances satisfying the conjecture.

##  1\. Introduction

The following was conjectured independently by Wills [17] and Cusick [10].

######  Conjecture 1.

Consider $k+1$ pairwise-distinct real numbers $n_{0},n_{1},...,n_{k}$. For any
$0\leq i\leq k$, there is a real number $t$ such that the distance of
$t(n_{j}-n_{i})$ to the nearest integer is at least $\dfrac{1}{k+1}$, for all
$0\leq j\leq k$, $j\neq i$.

Goddyn [4] termed the above as the ‘Lonely Runner conjecture’, where he
considered the above real numbers to be the speeds of runners on a unit length
circular track, all of whom start at the same time and at the same point on
the track. Note that it is the $(n_{j}-n_{i})$’s that matter and not the
$n_{i}$’s themselves. Consequently, the speed of a runner can be subtracted
from all the speeds. This leaves a runner stationary and possibly, some
runners with negative speeds. However, running with a negative speed is
equivalent to running in the opposite direction, with the same magnitude of
speed. Combining the stationarity of a runner with the symmetry of the track,
all resultant speeds can be assumed to be positive. A similar argument can be
made for the time $t$ as well. Thus, an equivalent version of the conjecture
is:

######  Conjecture 2.

(Lonely Runner Conjecture) Given $k$ positive real numbers
$n_{1},n_{2},...,n_{k}$, there is a non-negative real number $t$ such that the
distance of each $tn_{i},~{}1\leq i\leq k$ to its nearest integer is at least
$\dfrac{1}{k+1}$.

In the remainder of this paper, we refer to the lonely runner conjecture in
the form described in 2. Furthermore, we refer to any
$\mathbf{n}=(n_{1},n_{2},...,n_{k})$ as a _lonely runner instance_ if
$\mathbf{n}$ satisfies the conjecture.

With minimal effort, the conjecture can be proven to be true for $k=1$. The
$k=2$ case was proven in the context of Diophantine approximation by Wills
[17]. Using a similar approach, the $k=3$ case was proven, first by Betke and
Wills [3], and then by Cusick [10]. The first proof for $k=4$ was given using
a view-obstruction problem approach, by Cusick and Pomerance [11]. A simpler
proof was then given by Bienia et al [4]. Thinking of the conjecture as a
covering problem, the $k=5$ case was proven by Bohman, Holzman and Kleitman
[6]. Later, Renault [14] gave a simpler proof for this case. And finally, a
study of the regular chromatic number of distance graphs, by Barajas and Serra
[1], led to a proof for $k=6$. The conjecture remains open for $k\geq 7$.

Henze and Malikiosis [12] were among the first ones to study the conjecture
from a polyhedral theory perspective. They made use of the equivalence of -
(i) well-known geometric problems such as motion of billards balls in a cube
avoiding an inner cube and (ii) determining the covering radii of lattice
zonotopes. Furthermore, they establish, as the first unconditional proof, that
it suffices to prove the conjecture for positive integral speeds.

An alternative approach to fixing $k$ and attacking the problem, is to
identify families of sets that are lonely runner instances. Such an endeavor
was taken by Beck, Hosten and Schymura [2]. They first constructed the ‘Lonely
runner polyhedron’ and provided a family of lonely runner instances in terms
of the parities of the runners’ speeds. Subsequently, by considering the
intersection of the polyhedron with the first one and two coordinates, they
give families of lonely runner instances by relating the speeds of the second
and third fastest runners with the slowest.

Very recently, Rifford [15] employed a new method to approach the conjecture.
In particular, he explored the problem of determining an upper bound on $t$,
in terms of the number of rounds covered by the slowest runner, and described
this in terms of a covering problem. A conjecture was proposed for the
covering problem and it was proven to be true for all $2\leq k\leq 5$.

One related quantity, to 2, that has been well studied in the past is the ‘gap
of loneliness’ and several efforts have been made in getting the quantity
closer to $\frac{1}{k+1}$ in [7], [8], [13],[15] and [16], among others. In
[16], Tao shows that the lonely runner conjecture is true if all speeds are at
most $1.2k$. Furthermore, it was noted that a desired goal is to increase
multiplier $1.2$ to $2$, establishing it as a sufficient condition to prove
the conjecture. Recently, Bohman and Peng [5] showed that it is possible to
get the multiplier arbitrarily close to $2$ when the number of runners is
sufficiently large.

Apart from the various approaches mentioned above, work has been done to study
a modification of the conjecture and generalizing results to the version that
we study here. The modified version allows the runners to have arbitrary
starting points on the track. This has been subject of interest in, for
example, [9] and [15].

###  1.1. Preliminaries

In this work, $\mathbb{N}$, $\mathbb{N}^{+}$, $\mathbb{Z}$, $\mathbb{R}$ and
$\mathbb{R}^{+}$ represent the set of all non-negative integers, positive
integers, integers, real numbers and positive real numbers respectively. Their
analogues in $n$-dimensions are $\mathbb{N}^{n}$, $(\mathbb{N}^{+})^{n}$,
$\mathbb{Z}^{n}$, $\mathbb{R}^{n}$ and $(\mathbb{R}^{+})^{n}$. Additionally,
$\mathbf{e}_{k}\in\mathbb{R}^{n}$ denotes the $k$th standard basis vector for
$\mathbb{R}^{n}$. In particular, $\mathbf{e}_{k}=(\ldots,0,1,0,0,\ldots)$
where $k$th entry is 1 and the rest are all zeroes. We also denote the index
set $\\{1,2,\ldots,n\\}$ by $[n]$.

Everytime the modulo operation is used, with modulus $m$, we assume that the
equivalence class is $[0,m)$. This is equal to the remainder on division by
$m$. With the above, the fractional-part operation,
$\\{\cdot\\}:\mathbb{R}^{+}\cup\\{0\\}\mapsto[0,1)$, is defined as the
remainder on division by $1$. In particular, $\\{a\\}$ denotes the fraction
part of $a\in\mathbb{R}^{+}\cup\\{0\\}$.

We now present a result on convex sets in $\mathbb{R}^{2}$ that will be
crucial in proving our main results.

######  Lemma 3.

Consider the convex sets ${S}_{1},{S}_{2}\in\mathbb{R}^{2}$ and the strip
$\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\ {l\leq x_{2}\leq u}\right\\}$. If

${S}_{1}\cap{S}_{2}\cap\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=a}\right\\}\neq\emptyset~{}~{}~{}~{}\forall~{}~{}a\in[l,u]$

then $({S}_{1}\cup{S}_{2})\cap\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\ {l\leq
x_{2}\leq u}\right\\}$ is a convex set.

###### Proof.

Let ${U}=({S}_{1}\cup{S}_{2})\cap\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{l\leq x_{2}\leq u}\right\\}$. Assume that ${U}$ is non-convex. Thus, there
exists points $\mathbf{x},\mathbf{y}\in{U}$ such that a point in their convex
hull (line segment joining $\mathbf{x},\mathbf{y}$), is not contained in
${U}$. In particular,
$\exists~{}~{}\tilde{\mathbf{x}}=(\tilde{x},a)\in\textup{conv}(\mathbf{x},\mathbf{y})$
and $\tilde{\mathbf{x}}\not\in{U}$.

Since $\mathbf{x},\mathbf{y}\in{U}$ and
$\tilde{\mathbf{x}}=(\tilde{x},a)\in\textup{conv}(\mathbf{x},\mathbf{y})$, it
follows that $a\in[l,u]$. Furthermore, consider three additional points
$(x_{{S}_{1}},a)\in{S}_{1}\setminus{S}_{2}$,
$(x_{{S}_{2}},a)\in{S}_{2}\setminus{S}_{1}$ and
$(x_{\cap},a)\in{S}_{1}\cap{S}_{2}$ such that either
$x_{{S}_{1}}<\tilde{x}<x_{\cap}$ or $x_{\cap}<\tilde{x}<x_{{S}_{2}}$ (these
points will exist because of our assumptions). If
$x_{{S}_{1}}<\tilde{x}<x_{\cap}$, then since both
$(x_{{S}_{1}},a),(x_{\cap},a)\in{S}_{1}$, their convex combination
$(\tilde{x},a)\in{S}_{1}$ (since ${S}_{1}$ is convex), and consequently
$(\tilde{x},a)\in{U}$, which poses a contradiction. Alternatively, if
$x_{\cap}<\tilde{x}<x_{{S}_{2}}$, then since both
$(x_{\cap},a),(x_{{S}_{2}},a)\in{S}_{2}$, their convex combination
$(\tilde{x},a)\in{S}_{2}$ (since ${S}_{2}$ is convex), and consequently
$(\tilde{x},a)\in{U}$, which also poses a contradiction. The result follows. ∎

${S}_{2}$$x_{2}=u$$x_{2}=l$$x_{2}=a$${S}_{1}$$\mathbf{x}$$\mathbf{y}$••••••$(\tilde{x},a)$$(x_{{S}_{1}},a)$$(x_{\cap},a)$$(x_{{S}_{2}},a)$
Figure 1. Depicting contradiction for Lemma 3 when either ${S}_{1}$ or
${S}_{2}$ is non-convex.

Since it suffices to prove the conjecture for integral speed vectors [12], we
will restrict our attention to the speed vectors
$\mathbf{n}=(n_{1},n_{2},...,n_{k})\in(\mathbb{N}^{+})^{k}$. We shall assume
throughout that $n_{i}\geq n_{j}$ $\forall~{}~{}1\leq i<j\leq k$.

Consider a vector of speeds $\mathbf{n}\in(\mathbb{N}^{+})^{k}$. Then, using
the view-obstruction version of the conjecture, the _Lonely Runner polyhedron_
, ${P}(\mathbf{n})$ defined by Beck et al. [2] is

${P}(\mathbf{n}):=\left\\{\textbf{x}\in\mathbb{R}^{k}:\dfrac{n_{i}-kn_{j}}{k+1}\leq
n_{j}x_{i}-n_{i}x_{j}\leq\dfrac{kn_{i}-n_{j}}{k+1}~{}\text{for}~{}1\leq
i<j\leq k\right\\}\ .$

With respect to ${P}(\mathbf{n})$ and any projection thereof considered in
this work, we define the width of the set along a direction in the following.

######  Definition 1.

Consider ${S}\subseteq\mathbb{R}^{n}$ and $\mathbf{a}\in\mathbb{R}^{n}$. The
width of ${S}$ in the direction of $\mathbf{a}$ is defined as
$w_{S}(\mathbf{a})=\underset{\mathbf{x}\in{S}}{\max}~{}\mathbf{a}\cdot\mathbf{x}-\underset{\mathbf{x}\in{S}}{\min}~{}\mathbf{a}\cdot\mathbf{x}$.

######  Theorem 4.

[2] $\mathbf{n}\in(\mathbb{N}^{+})^{k}$ is a lonely runner instance if and
only if ${P}(\mathbf{n})\cap\mathbb{Z}^{k}\neq\emptyset$.

The intuition for the above is that, if an integer point
$\mathbf{m}=(m_{1},...,m_{k})$ lies in ${P}(\mathbf{n})$, then there is a time
$t$ when the $i^{\text{th}}$ runner has completed exactly $m_{i}$ rounds and
all the runners are in the region
$\left[\dfrac{1}{k+1},\dfrac{k}{k+1}\right]$.

######  Definition 2.

A time $t$ is a _suitable time_ for $\mathbf{n}$ if all runners are in the
region $\left[\dfrac{1}{k+1},\dfrac{k}{k+1}\right]$ at time $t$.

##  2\. Our contributions

Apart from the families of lonely runner instances proposed in [2], we propose
two new families of instances satisfying 2. We highlight these families of
lonely runner instances in Theorem 5 and Theorem 6. The proofs of these two
results are in Section 4. Polyhedral properties of suitable projections of
${P}(\mathbf{n})$ are crucial ingredients in the proofs of the main results
and are illustrated in Section 3.

######  Theorem 5.

If $\mathbf{n}$ satisfies $k\geq 4$ and
$n_{2}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)\geq k+1$, then it is a
lonely runner instance.

######  Remark.

Examples of speed vectors that are lonely runner instances due to Theorem 5
and not due to previous known results are:

$(17,16,7,6,5,4,2),(18,16,7,6,5,4,3,2)\text{ and }(20,18,8,7,6,5,4,3,2).$

######  Theorem 6.

If $n_{2}\leq kn_{k}$ and
$n_{1}~{}\textit{{mod}}((k+1)n_{k})\in[n_{k},kn_{k}]$, then $\mathbf{n}$ is a
lonely runner instance.

######  Remark.

Examples of vectors of speeds that are lonely runner instances due to Theorem
6 and not due to previous known results are:

$(20,14,8,6,5,4,2),(24,14,10,9,8,6,5,2)\text{ and }(23,18,15,10,8,7,6,4,2).$

Furthermore, we provide an alternate proof for establishing the set of speeds
satisfying $n_{1}\leq kn_{k}$ as lonely runner instances [2]. In particular,
we provide an explicit time at which these speed vectors become lonely runner
instances.

######  Theorem 7.

$t=\dfrac{k}{(k+1)n_{1}}$ is a suitable time for $\mathbf{n}$ if and only if
$\mathbf{n}$ satisfies $n_{1}\leq kn_{k}$.

It is known that $\mathbf{n}$ is a lonely runner instance if and only if there
is a suitable time $t$ that is at most $1$ [4, 16, 13]. Intuitively, this
makes sense because, at exactly unit time, each of the runners would be back
at the start position. Thus, the combined motion of all the runners is
periodic, with periodicity $1$. We strengthen the condition on $t$ and show
the following.

######  Theorem 8.

$\mathbf{n}$ is a lonely runner instance if and only if there is a suitable
time $t\leq\dfrac{1}{2}$.

We prove Theorems 7 and 8 in Section 5. As a continuation to characterization
of families of lonely runner instances through characterization of respective
suitable times, as in Theorem 7 and Theorem 8, we propose the following.

######  Conjecture 9.

For any $\mathbf{n}$ with $gcd(\mathbf{n})=1$, there is always a suitable time
of the form

$\displaystyle\frac{m}{2^{\lceil\ln_{2}{(n_{1})}+1\rceil}(k+1)n_{1}}$

for some natural number $m$, where $\lceil{\cdot}\rceil$ denotes the ceiling
function.

There are two reasons for why we believe Conjecture 9 to be true: First,
considering $m=k2^{\lceil\ln_{2}{(n_{1})}+1\rceil}$ yields a suitable time for
the family of vectors satisfying $n_{1}\leq kn_{k}$. Additionally, we have
computationally verified the existence of a suitable time given by Conjecture
9 for all possible $(\mathbf{n},k)$ such that $n_{1}\leq 32$, and
gcd($\mathbf{n}$) = 1. In particular, we have $2^{32}-1=4294967295$ speed
vectors, $\mathbf{n}$, with $n_{1}\leq 32$. Of these, $4294900694$ are co-
prime vectors (satisfying $\textit{gcd}(\mathbf{n})=1$). Further among these,
$2646877074~{}(\approx 61.62\%)$ different $\mathbf{n}$ are characterized
lonely runner instances due to the known results, including theorems 5 and 6.
Conjecture 9 thus, if true, yields a characterization for the remaining
$38.38\%$ of speed vectors.

##  3\. Some Properties of Lonely Runner Polyhedra

The major construct in the proofs of Theorems 5 and 6 is the _Lonely Runner
Polyhedron_ , ${P}(\mathbf{n})$, as defined in Section 1.1. In particular,

${P}(\mathbf{n}):=\left\\{\textbf{x}\in\mathbb{R}^{k}:\dfrac{n_{i}-kn_{j}}{k+1}\leq
n_{j}x_{i}-n_{i}x_{j}\leq\dfrac{kn_{i}-n_{j}}{k+1}~{}\text{for}~{}1\leq
i<j\leq k\right\\}$

A very important fact that we use to prove our main results is that any
integer translate of a polyhedron, say ${P}+\mathbf{v}$,
$\mathbf{v}\in\mathbb{Z}^{k}$, contains the same number of integer points as
the original polyhedron, ${P}$. To observe this, first note that
$\mathbf{a}\cdot\mathbf{x}=b$ is a face of ${P}$ if and only if
$\mathbf{a}\cdot(\mathbf{x}-\mathbf{v})=b$ is a face of ${P}+\mathbf{v}$.
Then, $\mathbf{l}\in\mathbb{Z}^{k}$ satisfies $\mathbf{a}\cdot\mathbf{x}=b$ if
and only if $\mathbf{l}+\mathbf{v}$ satisfies
$\mathbf{a}\cdot(\mathbf{x}-\mathbf{v})=b$. Due to this bijection between
${P}$ and ${P}+\mathbf{v}$, the number of integer points in ${P}$ and
${P}+\mathbf{v}$ are equal. We also utilize projection arguments to prove some
of the results. Consider the projection of ${P}(\mathbf{n})$ on to the first
$m$ coordinates, ${P}_{m}(\mathbf{n})$. If $\mathbf{n}$ satisfies $n_{m+1}\leq
kn_{k}$, it suffices to show that the ${P}_{m}(\mathbf{n})$ contains an
integer point $p=(p_{1},...,p_{m})$ instead of proving that ${P}(\mathbf{n})$
is not integer lattice-free. This is because,
$p^{\prime}=(p_{1},...,p_{m},0,...,0)$ would lie in ${P}(\mathbf{n})$.

Consider the projection of ${P}(\mathbf{n})$ on to the first two coordinates,
${P}_{2}(\mathbf{n})$. Indeed ${P}_{2}(\mathbf{n})$ is a polyhedron as well
[18]. For notational brevity, we shall henceforth refer to
${P}_{2}(\mathbf{n})$ as ${Q}$. The generating inequalities of ${Q}$ are:

$\displaystyle\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}\leq
x_{1}\leq\dfrac{kn_{1}}{(k+1)n_{3}}-\dfrac{1}{k+1}$
$\displaystyle\dfrac{n_{2}}{(k+1)n_{k}}-\dfrac{k}{k+1}\leq
x_{2}\leq\dfrac{kn_{2}}{(k+1)n_{3}}-\dfrac{1}{k+1}$
$\displaystyle\dfrac{n_{1}-kn_{2}}{k+1}\leq
n_{2}x_{1}-n_{1}x_{2}\leq\dfrac{kn_{1}-n_{2}}{k+1}$

In addition to the generating inequalities of ${Q}$, consider the following
lines (Figures 2(a) and 2(b))

$\displaystyle l_{1}:n_{2}x_{1}-n_{1}x_{2}=\dfrac{kn_{1}-n_{2}}{k+1}$
$\displaystyle l_{2}:n_{2}x_{1}-n_{1}x_{2}=\dfrac{n_{1}-kn_{2}}{k+1}$
$\displaystyle L_{1}:x_{2}=\alpha=\dfrac{n_{2}}{(k+1)n_{k}}+\dfrac{1}{k+1}$
$\displaystyle
L_{2}:x_{2}=\beta=\dfrac{n_{2}}{(k+1)n_{k}}+\dfrac{2n_{2}}{(k+1)n_{1}}-\dfrac{k}{k+1}$
$\displaystyle
L_{3}:x_{2}=\gamma=\dfrac{kn_{2}}{(k+1)n_{3}}-\dfrac{2n_{2}}{(k+1)n_{1}}-\dfrac{1}{k+1}$
$\displaystyle
L_{4}:x_{2}=\delta=\dfrac{1}{k+1}\left(\dfrac{n_{2}}{n_{k}}-1\right)$
$\displaystyle
L_{5}:x_{2}=\zeta=\dfrac{k}{k+1}\left(\dfrac{n_{2}}{n_{3}}-1\right)$
$\displaystyle L_{6}:x_{1}=\kappa=\dfrac{n_{1}}{(k+1)n_{k}}+\dfrac{1}{k+1}$

••••••$l_{1}$$l_{2}$$L_{3}$$L_{1}$$L_{2}$$L_{5}$$L_{4}$$x_{2}=\gamma$$x_{2}=\beta$$x_{2}=\delta$$x_{2}=\zeta$$x_{2}=\alpha$$x_{1}=\kappa$${Q}$$L_{6}$$\frac{k-1}{k+1}$$\frac{k-1}{k+1}$$1$$1$
(a)

••••••$l_{2}$$l_{1}$$L_{1}$$x_{2}=\alpha$${Q}_{1}$${Q}_{2}$$1$ (b)

Figure 2. Polyhedron $Q$ under the assumption
$n_{2}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)\geq k+1$

######  Lemma 10.

If $\mathbf{n}$ satisfies
$n_{2}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)\geq k+1$, then
$w_{Q}(\mathbf{e}_{1})\geq 1$ and $w_{Q}(\mathbf{e}_{2})\geq 1$.

###### Proof.

The lines $x_{2}=\zeta+\dfrac{k-1}{k+1}$ and $x_{2}=\delta-\dfrac{k-1}{k+1}$
represent diametrically opposite facets (top and bottom edges respectively) of
${Q}$. Then, $w_{Q}(\mathbf{e}_{2})$ is the distance between these facets of
${Q}$.

$\displaystyle w_{Q}(\mathbf{e}_{2})$
$\displaystyle=\left(\dfrac{kn_{2}}{(k+1)n_{3}}-\dfrac{1}{k+1}\right)-\left(\dfrac{n_{2}}{(k+1)n_{k}}-\dfrac{k}{k+1}\right)$
$\displaystyle=\dfrac{n_{2}}{k+1}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)+\dfrac{k-1}{k+1}$
(1) $\displaystyle\geq\dfrac{k+1}{k+1}+\dfrac{k-1}{k+1}$ $\displaystyle\geq 1$

where the first inequality follows from our assumption and the latter follows
from $k\geq 1$. The lines $x_{1}=\dfrac{kn_{1}}{(k+1)n_{3}}-\dfrac{1}{k+1}$
and $x_{1}=\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}$ represent diametrically
opposite facets (right and left edges respectively) of ${Q}$.
$w_{Q}(\mathbf{e}_{1})$ is the distance between these facets and it can be
expressed as

$\displaystyle w_{Q}(\mathbf{e}_{1})$
$\displaystyle=\left(\dfrac{kn_{1}}{(k+1)n_{3}}-\dfrac{1}{k+1}\right)-\left(\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}\right)$
$\displaystyle=\dfrac{n_{1}}{k+1}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)+\dfrac{k-1}{k+1}$
$\displaystyle\geq\dfrac{n_{2}}{k+1}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)+\dfrac{k-1}{k+1}$
$\displaystyle=w_{Q}(\mathbf{e}_{2})$ $\displaystyle\geq 1$

where the first inequality follows from $n_{1}\geq n_{2}$, the following
equality from (1) and the last inequality from $w_{Q}(\mathbf{e}_{2})\geq 1$.
The result follows. ∎

10 suggests that
${Q}_{1}\,:=\,{Q}\cap\left\\{\mathbf{x}\in\mathbb{R}^{2}:x_{2}\leq\alpha\right\\}\neq\emptyset$
and
${Q}_{2}\,:=\,{Q}\cap\left\\{\mathbf{x}\in\mathbb{R}^{2}:x_{2}\geq\alpha\right\\}\neq\emptyset$.
Consider ${Q}_{3}:={Q}_{2}-\mathbf{e}_{2}$ and ${Q}_{4}:={Q}_{1}\cup{Q}_{3}$.
Observe that, by definition, $w_{{Q}_{1}}(\mathbf{e}_{2})=1$ (Figure 2(b)).

######  Lemma 11.

If $\mathbf{n}$ satisfies
$n_{2}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)\geq k+1$, then
$w_{{Q}_{3}}(\mathbf{e}_{2})\geq\dfrac{k-1}{k+1}$.

###### Proof.

${Q}_{3}$ is a translate of ${Q}_{2}$. Thus, it suffices to show that
$w_{{Q}_{2}}(\mathbf{e}_{2})\geq\dfrac{k-1}{k+1}$. We have,

$\displaystyle w_{{Q}_{2}}(\mathbf{e}_{2})$
$\displaystyle=\left(\zeta+\dfrac{k-1}{k+1}\right)-\alpha$
$\displaystyle=\left(\dfrac{kn_{2}}{(k+1)n_{3}}-\dfrac{1}{k+1}\right)-\left(\dfrac{n_{2}}{(k+1)n_{k}}+\dfrac{1}{k+1}\right)$
$\displaystyle=\dfrac{n_{2}}{k+1}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)-\dfrac{2}{k+1}$
$\displaystyle\geq\dfrac{k+1}{k+1}-\dfrac{2}{k+1}$
$\displaystyle=\dfrac{k-1}{k+1}$

where the inequality follows from our assumption. The result follows. ∎

######  Lemma 12.

If $\mathbf{n}$ satisfies $2n_{1}\leq(k-1)n_{2}$ and
$n_{2}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)\geq k+1$, then

$\\{\mathbf{x}\in\mathbb{R}^{2}:x_{2}=a\\}\cap{Q}_{1}\cap{Q}_{3}\neq\emptyset\hskip
14.22636pt\forall~{}~{}a\in[\alpha-1,\delta].$

###### Proof.

Consider $a\in[\alpha-1,\delta]$, and the line $x_{2}=a$. From 11 and the fact
that $w_{{Q}_{1}}(\mathbf{e}_{2})=1$, we have
$\\{\mathbf{x}\in\mathbb{R}^{2}:x_{2}=a\\}\cap{Q}_{1}\neq\emptyset$ and
$\\{\mathbf{x}\in\mathbb{R}^{2}:x_{2}=a\\}\cap{Q}_{3}\neq\emptyset$.

Since $\alpha-1\leq a\leq\delta<\zeta$, the lines $x_{2}=a$ and $l_{1}$ will
intersect. Let $A$ be the point of intersection of these lines. Specifically,

$A=\left(\dfrac{kn_{1}-n_{2}}{(k+1)n_{2}}+\dfrac{n_{1}a}{n_{2}},a\right)$

By definition, $A\in{Q}_{1}$. Additionally, any point on the line $x_{2}=a$,
such that $\kappa-1\leq
x_{1}\leq\dfrac{kn_{1}-n_{2}}{(k+1)n_{2}}+\dfrac{n_{1}a}{n_{2}}$ will be in
${Q}_{1}$ as well.

Let $B$ be the point of intersection of $x_{2}=a+1$ with $l_{2}$. Observe that
$B\in{Q}_{2}$. In particular,

$B=\left(\dfrac{n_{1}-kn_{2}}{(k+1)n_{2}}+\dfrac{n_{1}(a+1)}{n_{2}},a+1\right)$

Since ${Q}_{3}={Q}_{2}-\mathbf{e}_{2}$, $\exists~{}~{}B^{\prime}\in{Q}_{3}$
such that $B^{\prime}=B-\mathbf{e}_{2}$. In particular,

$B^{\prime}=\left(\dfrac{n_{1}-kn_{2}}{(k+1)n_{2}}+\dfrac{n_{1}(a+1)}{n_{2}},a\right)$

As noted earlier, to prove $B^{\prime}\in{Q}_{1}$ it suffices to show that

$\kappa-1\leq\dfrac{n_{1}-kn_{2}}{(k+1)n_{2}}+\dfrac{n_{1}(a+1)}{n_{2}}\leq\dfrac{kn_{1}-n_{2}}{(k+1)n_{2}}+\dfrac{n_{1}a}{n_{2}}.$

We have,

$\displaystyle\left(\dfrac{n_{1}-kn_{2}}{(k+1)n_{2}}+\dfrac{n_{1}(a+1)}{n_{2}}\right)-\left(\dfrac{kn_{1}-n_{2}}{(k+1)n_{2}}+\dfrac{n_{1}a}{n_{2}}\right)$
$\displaystyle=\dfrac{n_{1}}{n_{2}}\left(\dfrac{2}{k+1}\right)-\dfrac{k-1}{k+1}$
$\displaystyle=\dfrac{1}{k+1}\left(\dfrac{2n_{1}}{n_{2}}-(k-1)\right)$
$\displaystyle\leq 0$ (2)

where the last inequality follows from our assumption. Additionally, note that

$\displaystyle\left(\dfrac{n_{1}-kn_{2}}{(k+1)n_{2}}+\dfrac{n_{1}(a+1)}{n_{2}}\right)-(\kappa-1)$
$\displaystyle=\left(\dfrac{n_{1}-kn_{2}}{(k+1)n_{2}}+\dfrac{n_{1}(a+1)}{n_{2}}\right)-\left(\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}\right)$
$\displaystyle\geq\left(\dfrac{n_{1}-kn_{2}}{(k+1)n_{2}}+\dfrac{n_{1}\alpha}{n_{2}}\right)-\left(\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}\right)$
$\displaystyle=\left(\dfrac{n_{1}}{(k+1)n_{2}}+\dfrac{n_{1}}{(k+1)n_{k}}+\dfrac{n_{1}}{(k+1)n_{2}}\right)-\dfrac{n_{1}}{(k+1)n_{k}}$
$\displaystyle=\dfrac{2n_{1}}{(k+1)n_{2}}$ $\displaystyle>0$ (3)

where the second inequality is immediate from $\alpha-1\leq a$ and the last
inequality follows from the positivity of $n_{1},n_{2}$ and $k$. From (2) and
(3) it follows that $B^{\prime}\in{Q}_{1}$. Combining with
$B^{\prime}\in\\{\mathbf{x}\in\mathbb{R}^{2}:x_{2}=a\\}$ and
$B^{\prime}\in{Q}_{3}$ yields the result. ∎

######  Lemma 13.

If $\mathbf{n}$ satisfies $k\geq 3$, $2n_{1}\leq(k-1)n_{2}$ and
$n_{2}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)\geq k+1$, then

$w_{\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=a}\right\\}\cap{Q}_{4}}(\mathbf{e}_{1})\geq
1~{}~{}~{}~{}~{}~{}\forall~{}~{}a\in[\alpha-1,\alpha].$

###### Proof.

First, consider $a\in[\delta,\alpha]$. Then,
$w_{\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=a}\right\\}\cap{Q}_{4}}(\mathbf{e}_{1})$ is at least as much as the
distance between $l_{1}$ and $l_{2}$ in the $x_{1}$-direction.

$\displaystyle w_{\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=a}\right\\}\cap{Q}_{4}}(\mathbf{e}_{1})$
$\displaystyle=\dfrac{1}{n_{2}}\left(\dfrac{kn_{1}-n_{2}}{k+1}-\dfrac{n_{1}-kn_{2}}{k+1}\right)$
$\displaystyle=\dfrac{k-1}{k+1}\dfrac{n_{1}+n_{2}}{n_{2}}$ $\displaystyle\geq
2\dfrac{k-1}{k+1}$ $\displaystyle\geq 1.$ (4)

where the first inequality follows from $n_{1}\geq n_{2}$ while the latter
follows from $k\geq 3$.

Now, consider $a\in[\alpha-1,\delta]$. Since ${Q}_{1}$ and ${Q}_{3}$ are
convex, as a result of 12 and 3,
${Q}_{4}\cap\\{\mathbf{x}\in\mathbb{R}^{2}:\alpha-1\leq x_{2}\leq\delta\\}$ is
convex.

Since $l_{1}$ is a facet of ${Q}_{2}$ and ${Q}_{3}={Q}_{2}-\mathbf{e}_{2}$, it
follows that $l_{1}^{\prime}:=l_{1}-\mathbf{e}_{2}$ is a facet of ${Q}_{3}$.
In particular, we have
$l_{1}^{\prime}:n_{2}x_{1}-n_{1}(x_{2}+1)=\dfrac{kn_{1}-n_{2}}{k+1}$.

Let $C$ be the point of intersection of $l_{1}^{\prime}$ and $x_{2}=\alpha-1$.
Then:

$C=\left(\dfrac{n_{1}}{n_{2}}+\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{1}{k+1},\dfrac{n_{2}}{(k+1)n_{k}}-\dfrac{k}{k+1}\right)$

It follows that $\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=\alpha-1}\right\\}\cap{Q}_{4}=[(\kappa-1,\alpha-1),C]$. We, thus, have

$\displaystyle w_{\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=\alpha-1}\right\\}\cap{Q}_{4}}(\mathbf{e}_{1})$
$\displaystyle=\left(\dfrac{n_{1}}{n_{2}}+\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{1}{k+1}\right)-\left(\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}\right)$
$\displaystyle=\dfrac{n_{1}}{n_{2}}+\dfrac{k-1}{k+1}$ $\displaystyle>1.$ (5)

where the inequality follows from $n_{1}\geq n_{2}$ and $\dfrac{k-1}{k+1}>0$.

In case $\zeta-\alpha\geq\dfrac{k-1}{k+1}$, $l_{1}^{\prime}$ would intersect
$x_{2}=\delta$. This point, say $D$, would be given by:

$D=\left(\dfrac{2kn_{1}}{(k+1)n_{2}}+\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{1}{k+1},\dfrac{1}{k+1}\left(\dfrac{n_{2}}{n_{k}}-1\right)\right)$

Consequently, $\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=\delta}\right\\}\cap{Q}_{4}=[(\kappa-1,\delta),D]$. We, then, have:

$\displaystyle w_{\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=\delta}\right\\}\cap{Q}_{4}}(\mathbf{e}_{1})$
$\displaystyle=\left(\dfrac{2kn_{1}}{(k+1)n_{2}}+\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{1}{k+1}\right)-\left(\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}\right)$
$\displaystyle=\dfrac{2kn_{1}}{(k+1)n_{2}}+\dfrac{k-1}{k+1}$
$\displaystyle>1.$ (6)

where the inequality follows from $n_{1}\geq n_{2}$ and $k\geq 3$. If
$\zeta<\alpha+\dfrac{k-1}{k+1}$, then $l_{1}^{\prime}$ would not intersect
$x_{2}=\delta$. Consequently, we have

$\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=\delta}\right\\}\cap{Q}_{4}=\left[(\kappa-1,\delta),\left(\dfrac{kn_{1}}{(k+1)n_{3}}-\dfrac{1}{k+1},\delta\right)\right].$

Combining this with 10, we have:

$\displaystyle w_{\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=\delta}\right\\}\cap{Q}_{4}}(\mathbf{e}_{1})=w_{{Q}_{4}}(\mathbf{e}_{1})=w_{{Q}}(\mathbf{e}_{1})>1$
(7)

Since ${Q}_{4}\cap\\{\mathbf{x}\in\mathbb{R}^{2}:\alpha-1\leq
x_{2}\leq\delta\\}$ is convex, it follows from (5), (6) and (7) that

$\displaystyle w_{\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=a}\right\\}\cap{Q}_{4}}(\mathbf{e}_{1})>1~{}~{}\forall
a\in[\alpha-1,\delta]$ (8)

The result follows from (4) and (8). ∎

######  Lemma 14.

Define ${Q}_{5}\,:=\,{Q}\cap\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{\beta\leq x_{2}\leq\gamma}\right\\}.$ If $\mathbf{n}$ satisfies $k\geq 4$,
$2n_{1}>(k-1)n_{2}$ and
$n_{2}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)\geq k+1$, then
$w_{{Q}_{5}}(\mathbf{e}_{2})>1$.

###### Proof.

It is immediate from the definition of ${Q}_{5}$ that
$w_{{Q}_{5}}(\mathbf{e}_{2})=\gamma-\beta$.

$\displaystyle w_{{Q}_{5}}(\mathbf{e}_{2})$
$\displaystyle=\left(\dfrac{kn_{2}}{(k+1)n_{3}}-\dfrac{2n_{2}}{(k+1)n_{1}}-\dfrac{1}{k+1}\right)-\left(\dfrac{n_{2}}{(k+1)n_{k}}+\dfrac{2n_{2}}{(k+1)n_{1}}-\dfrac{k}{k+1}\right)$
$\displaystyle=\dfrac{kn_{2}}{(k+1)n_{3}}-\dfrac{n_{2}}{(k+1)n_{k}}-\dfrac{4n_{2}}{(k+1)n_{1}}+\dfrac{k-1}{k+1}$
$\displaystyle>\dfrac{kn_{2}}{(k+1)n_{3}}-\dfrac{n_{2}}{(k+1)n_{k}}-\dfrac{8}{(k-1)(k+1)}+\dfrac{k-1}{k+1}$
$\displaystyle=\dfrac{kn_{2}}{(k+1)n_{3}}-\dfrac{n_{2}}{(k+1)n_{k}}-\dfrac{8}{(k-1)(k+1)}+1-\dfrac{2}{k+1}$
$\displaystyle=\dfrac{1}{k+1}\left(\dfrac{kn_{2}}{n_{3}}-\dfrac{n_{2}}{n_{k}}-2\right)+1-\dfrac{8}{(k-1)(k+1)}$
$\displaystyle\geq\dfrac{k-1}{k+1}+1-\dfrac{8}{(k-1)(k+1)}$
$\displaystyle=1+\dfrac{(k-1)^{2}-8}{(k-1)(k+1)}$ $\displaystyle>1.$

where the first inequality follows from the assumption $2n_{1}>(k-1)n_{2}$,
the second follows from
$n_{2}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)\geq k+1$ and the final
follows from $k\geq 4$. The result follows. ∎

##  4\. Proofs of Theorems 5 and 6

######  Theorem 5.

$\mathbf{n}$ is a lonely runner instance if it satisfies $k\geq 4$ and
$n_{2}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)\geq k+1$.

###### Proof.

Combining $n_{2}\left(\dfrac{k}{n_{3}}-\dfrac{1}{n_{k}}\right)\geq k+1$ with
the positivity of $n_{2},n_{k}$ and $k$ immediately yields that
$n_{3}<kn_{k}$. Thus, it suffices to show that ${Q}={P}_{2}(\mathbf{n})$ is
not integer lattice-free.. In particular, if there exists an integer point in
${Q}$ then $\mathbf{n}$ is a lonely runner instance.

Assume that $2n_{1}\leq(k-1)n_{2}$. By definition of $L_{1}$, we have
$w_{{Q}_{4}}(\mathbf{e}_{2})=1$. Thus, $\exists~{}~{}a\in\mathbb{Z}$ such that
$\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=a}\right\\}\cap{Q}_{4}\neq\emptyset$. Lemma 13 suggests
$w_{\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=a}\right\\}\cap{Q}_{4}}(\mathbf{e}_{1})\geq 1$. It follows that there
exists an integer point in ${Q}_{4}$ and consequently in ${Q}$.

Conversely, assume that $2n_{1}>(k-1)n_{2}$. 14 yields that
$w_{{Q}_{5}}(\mathbf{e}_{2})>1$. Thus, $\exists~{}~{}a\in\mathbb{Z}$ such that
$\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=a}\right\\}\cap{Q}_{5}\neq\emptyset$. Furthermore, by definition of
$L_{2}$, $L_{3}$ and ${Q}_{5}$, we have
$w_{\left\\{{\mathbf{x}\in\mathbb{R}^{2}}\ :\
{x_{2}=a}\right\\}\cap{Q}_{5}}(\mathbf{e}_{1})\geq 1$. It follows that
${Q}_{5}$ and thus ${Q}$ contains an integer point. ∎

######  Theorem 6.

If $\mathbf{n}$ satisfies $n_{2}\leq kn_{k}$ and
$n_{1}~{}\textit{{mod}}((k+1)n_{k})\in[n_{k},kn_{k}]$, then it is a lonely
runner instance.

###### Proof.

Since it has been assumed that $n_{2}\leq kn_{k}$, it suffices to show the
existence of an integral point in the projection of ${P}(\mathbf{n})$ on to
the first coordinate, for the existence of an integral point in
${P}(\mathbf{n})$. Consider the projection, ${P}_{1}(\mathbf{n})$, of
${P}(\textbf{n})$ on $x_{1}$. In particular, ${P}_{1}(\mathbf{n})$ can be
described as,

$\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}\leq
x_{1}\leq\dfrac{kn_{1}}{(k+1)n_{2}}-\dfrac{1}{k+1}$

The length, $l$, of the interval is,

$\displaystyle l$
$\displaystyle=\left(\dfrac{kn_{1}}{(k+1)n_{2}}-\dfrac{1}{k+1}\right)-\left(\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}\right)$
$\displaystyle=\dfrac{n_{1}}{k+1}\left(\dfrac{k}{n_{2}}-\dfrac{1}{n_{k}}\right)+\dfrac{k-1}{k+1}$
$\displaystyle=\dfrac{n_{1}}{k+1}\dfrac{kn_{k}-n_{2}}{n_{2}n_{k}}+\dfrac{k-1}{k+1}$
$\displaystyle\geq\dfrac{k-1}{k+1}.$ (9)

where the above inequality follows from $n_{2}\leq kn_{k}$ and positivity of
$n_{1}$ and $k$.

Assume that $n_{1}=a(k+1)n_{k}+b$, where $a\in\mathbb{N}$ and $0\leq
b<(k+1)n_{k}$. Specifically, $n_{k}\leq b\leq kn_{k}$ since
$n_{1}~{}\textit{{mod}}((k+1)n_{k})\in[n_{k},kn_{k}]$. With this assumption,
we have

$\displaystyle\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}$
$\displaystyle=\dfrac{a(k+1)n_{k}+b}{(k+1)n_{k}}-\dfrac{k}{k+1}$
$\displaystyle=a+\dfrac{b-kn_{k}}{(k+1)n_{k}}$
$\displaystyle=a-1+\dfrac{b+n_{k}}{(k+1)n_{k}}$ $\displaystyle\leq
a-1+\dfrac{kn_{k}+n_{k}}{(k+1)n_{k}}$ $\displaystyle=a.$ (10)

Additionally, using (9) we obtain

$\displaystyle\dfrac{kn_{1}}{(k+1)n_{2}}-\dfrac{1}{k+1}$
$\displaystyle\geq\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}+\dfrac{k-1}{k+1}$
$\displaystyle=\dfrac{a(k+1)n_{k}+b}{(k+1)n_{k}}-\dfrac{k}{k+1}+\dfrac{k-1}{k+1}$
$\displaystyle=a+\dfrac{b-kn_{k}}{(k+1)n_{k}}+\dfrac{k-1}{k+1}$
$\displaystyle\geq a+\dfrac{n_{k}-kn_{k}}{(k+1)n_{k}}+\dfrac{k-1}{k+1}$
$\displaystyle=a.$ (11)

From (10) and (11), we have $\dfrac{n_{1}}{(k+1)n_{k}}-\dfrac{k}{k+1}\leq
a\leq\dfrac{kn_{1}}{(k+1)n_{2}}-\dfrac{1}{k+1}$. The result follows. ∎

##  5\. Proofs of Theorems 7 and 8

######  Theorem 7.

$t=\dfrac{k}{(k+1)n_{1}}$ is a suitable time for $\mathbf{n}$ if and only if
$\mathbf{n}$ satisfies $n_{1}\leq kn_{k}$.

###### Proof.

Assume that $n_{1}\leq kn_{k}$. Then for all $i\in[k]$

$\displaystyle\dfrac{1}{k}\leq\dfrac{n_{i}}{n_{1}}\leq 1$
$\displaystyle\dfrac{1}{k+1}\leq\dfrac{k}{(k+1)n_{1}}n_{i}\leq\dfrac{k}{k+1}$
$\displaystyle\left\\{\dfrac{1}{k+1}\right\\}\leq\left\\{\dfrac{k}{(k+1)n_{1}}n_{i}\right\\}\leq\left\\{\dfrac{k}{k+1}\right\\}$

Thus, $\dfrac{k}{(k+1)n_{1}}$ is a suitable time.

Conversely, assume that $n_{1}>kn_{k}$. We have,

$\displaystyle 0<\dfrac{k}{(k+1)n_{1}}n_{k}<\dfrac{1}{k+1}$ $\displaystyle
0<\left\\{\dfrac{k}{(k+1)n_{1}}n_{k}\right\\}<\left\\{\dfrac{1}{k+1}\right\\}$

It follows that
$\left\\{\dfrac{k}{(k+1)n_{1}}n_{k}\right\\}\notin\left[\dfrac{1}{k+1},\dfrac{k}{k+1}\right]$
and, consequently, $\dfrac{k}{(k+1)n_{1}}$ is not a suitable time. ∎

######  Lemma 15.

Given any $\mathbf{n}$, $t\in[0,1]$ is a suitable time iff $1-t$ is.

###### Proof.

Let $t$ be a suitable time. It follows that $\\{n_{i}t\\}=b_{i}$ for some
$b_{i}\in\left[\dfrac{1}{k+1},\dfrac{k}{k+1}\right]$, $i\in[k]$.

Observe that, since $t\leq 1$, for $i\in[k]$, the $i^{th}$ runner will have
covered at most $n_{i}-1$ rounds. Thus, $n_{i}t=a_{i}+b_{i}$ where
$a_{i}\in\mathbb{N}$ and $a_{i}\leq n_{i}-1$. Now, consider the position of
the $i^{th}$ runner at time $1-t$.

$\displaystyle
n_{i}(1-t)=n_{i}-n_{i}t=n_{i}-(a_{i}+b_{i})=(n_{i}-a_{i}-1)+(1-b_{i})$
$\displaystyle\\{n_{i}(1-t)\\}=\\{(n_{i}-a_{i}-1)+(1-b_{i})\\}=\\{1-b_{i}\\}.$

Furthermore, for $i\in[k]$,
$b_{i}\in\left[\dfrac{1}{k+1},\dfrac{k}{k+1}\right]$ implies that
$1-b_{i}\in\left[\dfrac{1}{k+1},\dfrac{k}{k+1}\right]$.

We have, $\\{n_{i}(1-t)\\}\in\left[\dfrac{1}{k+1},\dfrac{k}{k+1}\right]$ for
all $i\in[k]$. Thus $1-t$ is a suitable time as well.

A similar argument can be made by assuming $1-t$ to be a suitable time, which
shows $1-(1-t)=t$ is a suitable time as well. The result follows. ∎

######  Theorem 8.

$\mathbf{n}$ is a lonely runner instance iff there is a suitable time
$t\leq\dfrac{1}{2}$.

###### Proof.

The sufficiency follows from the definition of suitable time. To see the
necessity, assume that $\mathbf{n}$ is a lonely runner instance. Thus there is
a suitable time $s\in[0,1]$. Consider the function

$t=\begin{cases}s&\text{if }s\leq\dfrac{1}{2}\\\
1-s&\text{otherwise}\end{cases}$

15 yields that both $s$ and $1-s$ are suitable times, implying that at least
one of $s$ and $1-s$ is at most $\dfrac{1}{2}$. The result follows. ∎

## References

  * Barajas and Serra [2008] Javier Barajas and Oriol Serra.  The lonely runner with seven runners.  _The Electronic Journal of Combinatorics_ , 15(1):R48, 2008.
  * Beck et al. [2019] Matthias Beck, Serkan Hosten, and Matthias Schymura.  Lonely runner polyhedra.  _INTEGERS_ , 19(2):1, 2019.
  * Betke and Wills [1972] Ulrich Betke and Jörg M Wills.  Untere schranken für zwei diophantische approximations-funktionen.  _Monatshefte für Mathematik_ , 76(3):214–217, 1972.
  * Bienia et al. [1998] Wojciech Bienia, Luis Goddyn, Pavol Gvozdjak, András Sebő, and Michael Tarsi.  Flows, view obstructions, and the lonely runner.  _Journal of Combinatorial Theory, Series B_ , 72(1):1–9, 1998.
  * Bohman and Peng [2022] Tom Bohman and Fei Peng.  Coprime mappings and lonely runners.  _Mathematika_ , 68(3):784–804, 2022.
  * Bohman et al. [2001] Tom Bohman, Ron Holzman, and Dan Kleitman.  Six lonely runners.  _The Electronic Journal of Combinatorics_ , pages R3–R3, 2001.
  * Chen [1994] Yong Gao Chen.  View-obstruction problems in n-dimensional euclidean space and a generalization of them.  _Acta Math. Sinica_ , 37(4):551–562, 1994.
  * Chen and Cusick [1999] Yong-Gao Chen and TW Cusick.  The view-obstruction problem forn-dimensional cubes.  _Journal of Number Theory_ , 74(1):126–133, 1999\.
  * Cslovjecsek et al. [2022] Jana Cslovjecsek, Romanos Diogenes Malikiosis, Márton Naszódi, and Matthias Schymura.  Computing the covering radius of a polytope with an application to lonely runners.  _Combinatorica_ , pages 1–28, 2022.
  * Cusick [1974] Thomas W. Cusick.  View-obstruction problems in n-dimensional geometry.  _Journal of Combinatorial Theory, Series A_ , 16(1):1–11, 1974.
  * Cusick and Pomerance [1984] Thomas W Cusick and Carl Pomerance.  View-obstruction problems, iii.  _Journal of Number Theory_ , 19(2):131–139, 1984\.
  * Henze and Malikiosis [2017] Matthias Henze and Romanos-Diogenes Malikiosis.  On the covering radius of lattice zonotopes and its relation to view-obstructions and the lonely runner conjecture.  _Aequationes mathematicae_ , 91(2):331–352, 2017\.
  * Perarnau Llobet and Serra Albó [2016] Guillem Perarnau Llobet and Oriol Serra Albó.  Correlation among runners and some results on the lonely runner conjecture.  _The Electronic Journal of Combinatorics_ , 23(1):1–22, 2016.
  * Renault [2004] Jérôme Renault.  View-obstruction: a shorter proof for 6 lonely runners.  _Discrete mathematics_ , 287(1-3):93–101, 2004\.
  * Rifford [2022] Ludovic Rifford.  On the time for a runner to get lonely.  _Acta Applicandae Mathematicae_ , 180(1):1–66, 2022.
  * Tao [2018] Terence Tao.  Some remarks on the lonely runner conjecture.  _Contributions to Discrete Mathematics_ , 13(2), 2018.
  * Wills [1967] Jörg M Wills.  Zwei sätze über inhomogene diophantische approximation von irrationalzehlen.  _Monatshefte für Mathematik_ , 71(3):263–269, 1967.
  * Ziegler [2012] Günter M Ziegler.  _Lectures on polytopes_ , volume 152.  Springer Science & Business Media, 2012.