\documentclass[12pt]{article} \usepackage{amsfonts} \usepackage{graphicx} \usepackage{epsf} %\makeatletter %\def\@begintheorem#1#2{\trivlist \item[\hskip \labelsep{\sc\bf #2\ #1}]\it} %\def\@opargbegintheorem#1#2#3{\trivlist % \item[\hskip \labelsep{\sc\bf #2\ #1\ (#3)}]\it} %\makeatother \let\labl=\label % comment out following long line to remove marginal refs. %\renewcommand{\label}[1]{\labl{#1} \ifinner\parbox{1cm}{\scriptsize{[#1]}}\fi \ifmmode\parbox{2cm}{{\scriptsize[#1]}} \else \marginpar{\scriptsize{#1}}\fi} \newtheorem{theorem} {Theorem}[section] \newtheorem{lemma} [theorem] {Lemma} \newtheorem{corollary}[theorem] {Corollary} \newcommand{\dt}{{\Delta t}} \newcommand{\GCD}{{\mbox{\rm GCD}}} \newcommand{\LCM}{{\mbox{\rm LCM}}} \newcommand{\es}{{\emptyset}} \newcommand{\R}{{\mathbb R}} \newcommand{\N}{{\mathbb N}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\Q}{{\mathbb Q}} \newcommand{\e}{{\epsilon}} \newcommand{\norm}[1]{\left\|{#1}\right\|} %\newcommand{\vv}{\mbox{\boldmath$v$}} \newcommand{\vv}{\mbox{\sf\bf v}} \newcommand{\mm}{\mbox{\sf\bf m}} \newcommand{\m}[3]{\mbox{$[{#1}]_{{#2} \mapsto {#3}}$}} \newcommand{\smod}[1]{\mbox{~(mod~}{#1}\mbox{)}} % pmod with small spacing \newcommand{\modeq}[2]{\equiv #1 \smod{#2}} % == a (mod b) (handy!) \newcommand{\qed}{\hspace*{\fill}\rule{1ex}{1ex}} %\setlength{\textwidth}{6.5in} %\setlength{\textheight}{8.6in} %\setlength{\topmargin}{-1.0 cm} %\setlength{\oddsidemargin}{0in} %\setlength{\evensidemargin}{0in} %%%%%%%%%%%%%%%%%%%%%%%%% % INTEGERS Journal compatible headings are used %%%%%%%%%%%%%%%%%%%%%%%%% \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 %\abovecaptionskip=0pt \begin{document} \begin{center} {\bf TIGHT INSTANCES OF THE LONELY RUNNER} \vskip 20pt {\bf Luis Goddyn\footnote{The first author would like to thank Laboratoire Leibniz -- IMAG and NSERC Canada for support during the course of this research.}}\\ {\smallit Department of Mathematics, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada}\\ {\tt goddyn@math.sfu.ca}\\ \vskip 10pt {\bf Erick B.~Wong}\\ {\smallit Department of Mathematics, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada}\\ {\tt erick@sfu.ca}\\ \end{center} \vskip 30pt \centerline{\smallit Received: , Accepted: , Published: } \vskip 30pt \centerline{\bf Abstract} \noindent The {\it Lonely Runner Conjecture\/} of J.~Wills asserts the following. % \begin{quote}\noindent {\it For any vector $\vv\in (\R - \{0\})^{n-1}$ there exists $t\in \R$ such that every component of $t\vv$ has distance at least $1/n$ to the nearest integer.} \end{quote} % We study those vectors $\vv$ for which the bound of this conjecture is attained. In particular, we construct an infinite family of such \emph{tight vectors}. This family, plus three sporadic examples, constitute all known tight vectors. We completely characterize a subfamily: those tight vectors obtained from $\vv = \langle 1,2,\dots,n-1\rangle$ by scaling one entry by a positive integer. The characterization motivates the problem of finding the least positive integer which has a common factor with every integer in the interval $[a,b]$. We solve this problem when $b \ge 2a$. %following problem. %% %\begin{quote}\noindent %{\it %Find the least positive integer having a common factor with every integer %in the interval $[a,b]$.} %\end{quote} %% %We solve this problem when $b \ge 2a$. % %\medskip %\noindent\textit{Keywords: %view-obstruction, diophantine approximation, products of primes, %common factors with consecutive integers} % %\noindent\textit{MR Subjects Classification (2000): %11B75 (11J71)} \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt x (200x), \#Axx\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt %%%%%%%%%%%%%%%%%% % \newpage %%%%%%%%%%%%%%%%%% %\section{Introduction} \section*{\normalsize 1. Introduction} \refstepcounter{section} The {\it Lonely Runner Conjecture\/} of Wills \cite{W1} asserts the following. \begin{quote}\noindent {\it For any vector $\vv = \langle v_1,\dots,v_{n-1}\rangle \in (\R - \{0\})^{n-1}$ there exists $t\in \R$ such that every component of $t\vv$ has its fractional part in $\left[\frac1n,\frac{n-1}n\right]$.} \end{quote} % This conjecture has relevance to Diophantine approximation \cite{BW,CYG,W0,W1,W2,W3,W4}, view-obstruction theory \cite{C1,C2,C3,CP}, and flows in graphs and matroids \cite{B}. A physical interpretation has $n-1$ runners on a circular track of unit length, with $\vv$ being the vector of angular {\it speeds\/}. The fractional part of $v_r t$ is the {\it position\/} of runner $r$ at {\it time\/} $t$. The {\it distance\/} from $r$ to the origin at time $t$ is $\norm{v_r t} := \min\{v_r t - \lfloor v_r t\rfloor, \lceil v_r t \rceil - v_r t\}$. We write $$ LR(\vv) := \sup_{t\in\R} \min_r \norm{v_r t} $$ and $$ LR(n) := \inf \{ LR(\vv): \vv \in (\R - \{0\})^{n-1}\}. $$ Thus Wills's conjecture is that $LR(n) \ge 1/n$ for $n \ge 2$. An easy argument \cite{C1} shows $LR(\langle 1,2,\ldots,n-1 \rangle )=1/n$ so the conjectured bound is best possible. It is known that $LR(n)=1/n$ for $2\le n \le 6$ \cite{CP,B,BHK,R}, and that $LR(n) > \frac1{2(n-1)}$ for $n\ge3$ \cite{W1}. The original formulation of Wills's conjecture is actually for the special case that %It is further known \cite{W0} that it is enough to show $LR(\vv) \ge n$ for any $\vv$ such that % \begin{equation}\labl{wlog} \parbox{12cm}{\it $\vv$ is an $(n-1)$-vector whose entries are distinct positive integers in increasing order and having no common divisor.} \end{equation} Bohman et al.~\cite{BHK} have shown that this formulation is sufficient to imply the general conjecture, and that in fact $LR(\vv) \ge LR(n-1)$ unless $\vv$ is a scalar multiple of a vector of rationals. We henceforth limit our discussion to integral speed vectors. In an attempt to understand the extremal instances of the conjecture, we strive to classify those $(n-1)$-vectors $\vv$ for which $LR(\vv) = 1/n$. Such vectors $\vv$ are said to be {\it tight\/}. % We use the notation $[k] := \langle 1,2,\ldots,k \rangle$. As mentioned above, $[n-1]$ is tight for $n\ge2$. It is known \cite{CP} that, for $2\le n\le4$, % \begin{equation}\labl{n4} \parbox{12cm}{\it $\vv = [n-1]$ is the unique tight vector satisfying {\rm (\ref{wlog})}. } \end{equation} % Statement~(\ref{n4}) is false for $n\in\{5,6,8\}$, but is probably true for $n=7$. A computer experiment reveals the following tight vectors which are different from $[n-1]$. % \begin{center} %\scriptsize \footnotesize %\normalsize % time lonelytight -a 20 40 \begin{verbatim} All non-trivial tight speed vectors with n <= 20 and maximum speed <= 40 T1: n= 5: 1 3 4 7 T2: n= 6: 1 3 4 5 9 T3: n= 8: 1 4 5 6 7 11 13 T4: n= 8: 1 2 3 4 5 7 12 T5: n=14: 1 2 3 4 5 6 7 8 9 10 11 13 24 T6: n=20: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 36 \end{verbatim} %26635.3u 4.3s 1:37:35.43 45.5% 0+0k 1+0io 7pf+0w \end{center} The first three of these tight speed vectors appear to be sporadic. However, there is a pattern to the last three; each is obtained from $[n-1]$ by doubling the speed of the second-fastest runner. Further tests reveal other tight vectors, but all are of a similar form: each is obtained from $[n-1]$ by multiplying some of the fastest speeds by small positive integers. In Section~\ref{single} we determine exactly when accelerating a single runner in this fashion yields a tight speed vector. The characterization involves a %curious number-theoretic condition that we have not seen before. The condition typically requires large values of $n$, whose minimum value is determined by an instance of the optimization problem described in the abstract. This problem is solved (for the case $b \ge 2a$) in Section~\ref{mintight}. We treat the case of accelerating more than one runner in Section~\ref{many}, where we present only a sufficiency condition for a vector of the form $\langle m_1, 2m_2, \dots, (n-1)m_{n-1}\rangle$ (where each $m_i$ is a positive integer) to be a tight vector. \vskip 30pt %\section{Accelerating a single runner} \section*{\normalsize 2. Accelerating a single runner} \refstepcounter{section} \labl{single} We denote by \m{n-1}{r}{r'} the speed vector obtained from $[n-1]$ by replacing the speed $r$ by $r'$. In this section, we characterize those integer triples $(n,r,m)$ for which the speed vector \m{n-1}{r}{mr} is tight. The substitution $r \mapsto mr$ is called an \emph{acceleration} (of $r$). A runner with speed $mr$ where $r \in [n-1]$ is called an \emph{accelerated runner}, and $mr$ is \emph{properly accelerated} if $m \ge 2$. % If $X=\{x_1,\ldots,x_{n-1}\}$ is a set of real numbers, then $LR(X)$ is well defined to equal $LR(\langle x_1,\ldots,x_{n-1} \rangle)$. Accordingly, $[n-1]$ denotes either the vector $\langle 1,2,\dots,n-1\rangle$ or the set $\{ 1,2,\ldots,n-1\}$, depending on the context. We denote by $\N$ the set of positive integers. We use $[a,b]$ and $[a,b)$ to denote closed and semi-closed real intervals. % %%%%%%%%%Not Needed%%%%% %We sometimes refer to the following observation. %% %\begin{equation} \labl{triv} %|y| \le 1/2 \textrm{ implies } \norm{y} = |y|. %\end{equation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5 \begin{lemma}\labl{coplem} If $r \in \N$, then any set of $\lfloor r/2 \rfloor + 1$ consecutive integers contains a number relatively prime to~$r$. \end{lemma} %\noindent{\bf Proof: } {\it Proof.} The lemma is easily verified for $r < 6$, and we assume $r \ge 6$. If $r=2p$ for some prime $p$, then any run of $4$ consecutive integers contains an odd number not divisible by $p$, so we may assume $r/2$ is not prime. Now, consider the moduli $1,\ldots,r-1$ with respect to $r$. By Bertrand's postulate, there exists a prime $p \in \left [\, \lfloor r/3 \rfloor+1 \,,\, 2\lfloor r/3 \rfloor+1\, \right ]$. Since $r \neq 2p$ and $p < r < 3p$, the integers $p$ and $r-p$ are both relatively prime to $r$. The set $\{0,1,\dots,r-1\} -\{1,p,r-p,r-1\}$ contains no interval of $\lfloor r/2 \rfloor$ consecutive moduli, proving the lemma. \qed \newpage \begin{lemma}\labl{looselem} If $X$ is a proper subset of $[n-1]$, then $LR(X) > 1/n.$ \end{lemma} %\noindent{\bf Proof: } {\it Proof.} We may assume without loss of generality that $X = [n-1] - \{x\}$ for some $x \in [n-1]$. If $2x \ge n$, then no speed in $X$ is divisible by $x$. By considering the time $t=1/x$, we find $LR(X) \ge 1/x > 1/n$. We may assume that $2x < n$. We claim that at time $t_0 := \frac{1}{x} + \frac{1}{2xn}$, exactly one runner in $X$ has distance $1/n$, and all other runners have distance $>1/n$. It then follows that at some time sufficiently close to $t_0$, all runners have distance $>1/n$. % Let $r$ be a speed in $X$. If $r = kx$ for some $k\in \N$, then $2 \le k < n$, so $$\norm{rt_0} = \norm{\frac k{2n}} \ge \frac 1n,$$ with equality achieved if and only if $k=2$. Now suppose $r$ is not divisible by $x$. Then at time $1/x$, the runner $r$ has distance $\ge 1/x$, so $$ \norm{rt_0} \ge \norm{\frac rx} - \left|r\left(t_0-\frac 1x\right)\right| \ge \frac 1x - \frac{r}{2xn} > \frac 1{2x} > \frac 1n. $$ Thus, the runner of speed $2x$ has distance exactly $1/n$, and all other runners have distance $>1/n$ at time $t$, as claimed. \qed %%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}\labl{mainthm} For integers $n\ge2$, $r\in [n-1]$ and $m\ge1$, we have $$LR(\m{n-1}{r}{mr}) \ge 1/n$$ with equality holding if and only if either $n$=2, or $(n,r,m) = (3,1,4)$, %or $\mbox{GCD}(r,b)>1$ for or $\GCD (r,b)>1$ for every $b \in \{n-r, n-r+1, \ldots ,m(n-r)-1\}$. \end{theorem} %\noindent{\bf Proof: } {\it Proof.} Let $X := \m{n-1}{r}{mr}$. We first treat some special cases. The theorem is trivially true when $m=1$. The cases $n \in \{ 2,3,4\}$ follow from (\ref{n4}). We assume $m\ge 2$ and $n \ge 5$. For the case $r=1$, we claim that $X = \{m,2,3,\ldots,n-1\}$ is never a tight speed set. At all times in the open interval $T:= \left(\frac1{2n} , \frac1n \right)$, every runner in $\{2,3,\ldots,n-1\}$ is at distance $>1/n$. Supposing that $X$ is tight, we have $m\ge n$ (by Lemma~\ref{looselem}) and $\norm{mt} \le 1/n$ for all $t\in T$. Since $T$ has length $\frac1{2n}$, the integer $m$ is bounded above by $\frac2n / \frac1{2n} =4$. Therefore $n \le 4$, a contradiction proving the claim. We henceforth assume $r \ge 2$. Under these assumptions, we first demonstrate the necessity of the GCD conditions. Define $$s := n-r.$$ Suppose that $\GCD (r,b)=1$ for some $b \in \{ s, s+1, \ldots , ms-1\}$. Without loss of generality let $b$ be the smallest such value. % As %$\mbox{GCD}(r,b)=1$, $\GCD (r,b)=1$, there exists $a \in \N$ such that $ab\equiv 1 \smod{r}$. Let $$t_\e := \frac{a}{r} - \frac{\e}{nr}.$$ % We aim to show that for some $\e \in \{1/m\} \cup [1/2, 2/3]$, all runners in $X$ at time $t_\e$ have distance $\ge 1/n$, and at most one runner has distance exactly $1/n$. At some time sufficiently close to $t_\e$, all runners will have distance $>1/n$, thus proving the necessity of $\GCD(r,b) > 1$. We partition $X$ into three sets according to the residues modulo $r$. \begin{itemize} \item $X_0 = \{ x \in X \mid x \modeq{0}{r} \}$ \item $X_1 = \{ x \in X \mid x \modeq{b}{r} \}$ \item $X_2 = \{ x \in X \mid x \not\equiv{0,b}\smod{r} \}$ \end{itemize} If $x \in X_2$, then $x 1/n$. If $x \in X_1$, then runner $x$ is at position $1/r$ at time $t_0$. Now $x \modeq{b}{r}$ and $x < s+r \le b+r$ together imply $x \le b$. So, provided $\e < s/b$, we have $$ \norm{xt_\e} \ge \norm{\frac{ab}{r} - \frac{b\e}{nr}} = \norm{\frac{1}{r} - \frac{b\e}{nr}} > \norm{\frac{1}{r} - \frac{s}{nr}} = \frac{1}{n}\,. $$ % We have shown the following. \begin{equation}\labl{eps-cond1}\parbox{14.5cm}{\it For any $\e \in \left[\,0,\frac{s}{b}\right)$, every runner in $X_1 \cup X_2$ has distance $>\frac 1 n$ at time $t_\e$.} \end{equation} We consider those runners in $X_0$ under two cases. \noindent{\em Case 1:} $s \le r$ Here we have $n \le 2r$, so $X_0$ contains only the properly accelerated runner $mr$. At time $t_{1/m}$ this runner has distance $1/n$. Since $b < ms$, we have $1/m < s/b$, so $\e=1/m$ satisfies the condition in~(\ref{eps-cond1}). Therefore every runner in $X - \{mr\}$ has distance $>1/n$ at time $t_{1/m}$. \noindent{\em Case 2:} $s > r$ By the choice of $b$ and Lemma~\ref{coplem} we have $b \le s + \lfloor r/2 \rfloor < 3s/2$, so $s/b > 2/3$. We may assume $m \ge 3$, for otherwise $mr \in [n-1]$ and $X$ is not tight by Lemma~\ref{looselem}. We have $$ X_0 = \left\{ mr, 2r, 3r, \ldots, \left\lfloor \frac{n-1}{r} \right\rfloor r \right\}. $$ % At the time $t_\e$, a runner of speed $kr$ is at distance $\norm{k\e/n}$. For the non-properly accelerated runners in $X_0$ we have $2 \le k < n/2$, so for any $\e \in [1/2, 2/3]$ we have $$ \frac 1n \le \frac{k\e}{n} < 1/3. $$ %By (\ref{triv}) we have This implies $\norm{k\e/n} \ge 1/n$ with equality only when $\e=1/2$ and $k=2$. In view of $\e \le 2/3 < s/b$ and~(\ref{eps-cond1}), we have shown that, throughout the time interval $[t_{2/3}, t_{1/2}]$, all runners in $X - \{mr\}$ have distance $\ge 1/n$ with equality holding only for runner $2r$ at time~$t_{1/2}$. It remains to show that for some $\e \in [1/2, 2/3]$, runner $mr$ has distance $\ge 1/n$ at time~$t_\e$, with strict inequality holding if $\e = 1/2$. At time $t_\e$, runner $mr$ has distance $\norm{\e m/n}$. If $m < 2n-2$, then $\e = 1/2$ suffices since $$ \frac1n < \frac{m}{2n} < \frac{n-1}{n}\,.$$ We therefore assume $m \ge 2n-2$. If $m \ge 12$, then runner $mr$ traverses an interval of length $m/6n \ge 2/n$ during the time interval $[t_{2/3}, t_{1/2}]$. Thus, for some $\e \in (1/2,2/3]$, runner $mr$ will have distance $\ge 1/n$ at time~$t_\e$, as required. Suppose instead that $m < 12$, whence $5 \le n \le \lfloor m/2\rfloor+1 \le 6$. In particular, either $n=5$ and $8 \le m \le 11$, or else $n=6$ and $10 \le m \le 11$. Since $r 1/5$ and $LR(X_6) > 1/6$, hence $X$ cannot be a tight speed set. To see this, observe that $X_5$ reduces modulo $19$ to the set $\{\pm 1, \pm 3, 4\}$ and that all runners in $X_5$ have distance at least $\frac{5}{19} > \frac{1}{4}$ at time $t=\frac{8}{19}$; similarly, $X_6$ reduces modulo $25$ to $\{1, \pm 3, 4, \pm 5\}$ and all runners in $X_6$ have distance at least $\frac{1}{5}$ at time $t=\frac{11}{25}$ (these bounds are actually tight). This completes Case~2 and proves the GCD condition to be necessary. For the proof of sufficiency, we refer the reader to Theorem~\ref{manythm} where a more general result is proved. \qed In the above proof, we identified explicit intervals in which the runner of speed $r$ is the sole runner at distance $\le 1/n$ (such intervals must exist by Lemma~\ref{looselem}). As we saw in Case~2, an accelerated runner with speed at least $12r$ must have distance $\ge 1/n$ at some point in these intervals. This observation holds even if the speed is not an integer multiple of $r$; we can use it to prove the following: % \begin{theorem} \labl{main-cor} For any fixed speed $r$ there are only finitely many pairs $(n,r')$ such that $\m{n-1}{r}{r'}$ is tight. \end{theorem} {\it Proof.} Let $r$ be fixed. Suppose $\m{n-1}{r}{r'}$ is tight with $n \ge 12r$. Then we have $s > r$ which is Case~2 in the proof of Theorem~\ref{mainthm}. %thus $r' < 12r$ by the preceding argument, By the argument in Case~2 we have $r' < 12r$, so $\m{n-1}{r}{r'}$ is a proper subset of $[n-1]$, contradicting Lemma~\ref{looselem}. Thus there are only finitely many $n$ such that $\m{n-1}{r}{r'}$ is tight. For any $n < 12r$, there exists by Lemma~\ref{looselem} an interval of positive length in which all runners in $[n-1]-\{r\}$ have distance $> 1/n$, so again the speed set $\m{n-1}{r}{r'}$ cannot be tight for sufficiently large $r'$ depending on $n$. \qed We believe Theorem~\ref{main-cor} partially explains why there are no further sporadic speed sets resembling T1 and T2 where the speed $2$ is replaced by an odd integer. \vskip 30pt %\section{Accelerating several runners} \section*{\normalsize 3. Accelerating several runners} \refstepcounter{section} \labl{many} Theorem~\ref{mainthm} gives a necessary and sufficient ``GCD condition'' for a single-runner-ac\-cel\-erated speed set $\m{n-1}{r}{mr}$ to be tight. We deferred the proof of ``sufficiency'' to this section, because we prove something more general here. We show that, %if several runners $r \in [n-1]$ are properly accelerated if each of several runners are properly accelerated $r \mapsto m_r r$ and each individual acceleration $\m{n-1}{r}{m_r r}$ satisfies the GCD condition, then accelerating all of these runners simultaneously also results in a tight speed set. % For example, each of $\m{73}{70}{140}$ and $\m{73}{72}{144}$ is a tight speed set, therefore accelerating both runners also results in a tight speed set. Later we demonstrate that tight speed sets exist where arbitrarily many runners have been properly accelerated in this way. We also discuss the missing converse to Theorem~\ref{manythm} (when there is more than one properly accelerated runner). Let $\mm = \langle m_1, m_2,\ldots,m_{n-1} \rangle$ be a vector of ``speed multipliers''. Then $[n-1]_{\mm}$ denotes the vector (or set) of accelerated speeds $\langle m_1,2m_2,\ldots,(n-1)m_{n-1} \rangle$. %%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}\labl{manythm} Let $m_1, m_2,\ldots,m_{n-1} \in \N$. Then $LR([n-1]_{\mm}) = 1/n$ if the following condition holds: For each $r \in [n-1]$ and $b \in \{n-r, n-r+1,\ldots, m_r(n-r)-1\}$, we have $\GCD (r,b)>1$. \end{theorem} % Note that the condition of Theorem~\ref{manythm} is vacuously true for those non-properly accelerated $r$ with $m_r = 1$. We shall use the following lemma. Althought it holds true for any $n>1$, we shall only use the case $n = |X|+1$. % \begin{lemma}\labl{manylem} Let $X$ be a speed set satisfying (\ref{wlog}) such that $LR(X) \le 1/n$. Let $r \in X$ and let $X'$ be obtained from $X$ by replacing $r$ with $mr$, where $m$ is an integer greater than 1. Then $LR(X') \le 1/n$ provided the following hold. \vspace{-1ex} \begin{enumerate} \item For each prime divisor $p$ of $r$, we have $\frac{r}{p} \in X'$. \item For each integer $q$ relatively prime to $r$, there exists $b \in X'$ such that $m(n-r) \le b \le r+n$ and $b \equiv q \smod{r}$. \end{enumerate} \end{lemma} %\noindent{\bf Proof: } {\it Proof. } For each $a \in \Z$ we consider the following union of two time intervals, centered about $a/r$. % \begin{equation}\labl{T1} T_{a} :=\left\{ \frac ar + \dt : \frac1{nmr} < |\dt | \le \frac1{nr} \right\}. \end{equation} % Thus $\bigcup\{T_{a} : a\in \Z \}$ is the set of times at which the accelerated runner having speed $mr$ has distance more than $1/n$, but would have had distance at most $1/n$ were he to have speed $r$ instead. As $LR(X) \le 1/n$, we have only to prove the following statement for each $a \in \Z$. % \begin{equation}\labl{cond1} \parbox{12cm}{\it For every $t\in T_{a}$, there exists $x \in X'$ such that $\norm{xt} \le \frac 1n$.} \end{equation} Given $a\in \Z$ and $t\in T_{a}$, we write $t = a/r + \dt$ where $\frac1{nmr} < |\dt | \le \frac1{nr}$. Let $d=\GCD (a,r)$. We first suppose $d>1$. Let $p$ be a prime divisor of $d$, and set $x = r/p$. By the hypothesis, $x \in X'$. Now $x$ satisfies~(\ref{cond1}) according to the following calculation. $$ \norm{xt} = \norm{\frac{r}{p}\!\cdot\!\frac{a}{r} + \frac{r}{p} \dt} = \norm{ \frac{r}{p} \dt} \le \frac{r}{p}\!\cdot\!\frac1{nr} < \frac1n. $$ We now assume $d = \GCD (a,r)=\GCD (-a,r)=1$. There exist by hypothesis $b,b' \in X$ such that $mn - mr \le b,b' \le n+r$ and $ab \equiv -ab' \equiv 1 \smod{r}$. We claim that setting $x$ to equal to either $b$ or $b'$, according to the sign of $\dt$, satisfies~(\ref{cond1}). If $\dt <0$, then for some $q \in \N$ we have the following. $$bt \in \left[\frac {ab}r - \frac b{nr} ,\, \frac {ab}r - \frac b {nmr}\right] = \left[q + \frac 1r- \frac b{nr} ,\, q + \frac 1r - \frac b {nmr}\right].$$ Since $\frac1r - \frac b{nr} \ge -\frac1n$ and $$\frac1r - \frac b{nmr} = \frac{nm-b}{nmr} \le \frac{mr}{nmr} = \frac1n,$$ we have $\norm{bt} \le \frac1n$. If $\dt > 0$, then a nearly identical calculation shows that $x=b'$ satisfies (\ref{cond1}), as claimed. This completes the proof of Lemma~\ref{manylem}. \qed \vspace{5ex} %\noindent %{\bf Proof of Theorem~\ref{manythm}:} {\it Proof of Theorem~\ref{manythm}.} Suppose that $\mm = \langle m_1,m_2,\dots,m_{n-1}\rangle$ satisfies the hypothesis. Let $r \in [n-1]$ be such that $m_r \ge 2$. We have $n-r \ge 2$ since no integer has a common factor with $1$. Also $r$ is even, since there is always a power of $2$ in $[\,n-r\,,\,2(n-r)-1\,]$. Since $r$ is not relatively prime to any integer in $[\,n-r\,,\, m_r(n-r)\,)$, we have by Lemma~\ref{coplem} that $r/2 \ge (m_r-1)(n-r) \ge n-r$, so $2n/3 \le r < n$. % We have established the following. \begin{equation}\labl{cond2} \textit{If $r, r' \in [n-1]$ are distinct and $m_r, m_{r'} \ge 2$, then $1 < \GCD (r,r') < r'$.} \end{equation} Let us define the sequence of speed vectors $X_0, X_1, \ldots, X_{n-1}$, where $X_0 := [n-1]$, and each $X_i$ is equal to $X_{i-1}$ with its $i$th entry replaced by $m_ii$. We will show inductively that $LR(X_{r}) \le 1/n$, for $r=0,1,\dots,n-1$. We have that $LR(X_0) = 1/n$. Assume that $LR(X_{r-1}) \le 1/n$ for some $r \in [n-1]$. If $m_r =1$, then $X_r = X_{r-1}$ and the induction step is trivial. % We assume that $m_r \ge 2$. We shall apply Lemma~\ref{manylem} with $X=X_{r-1}$ and $X' = X_r$. Let $p$ be a prime divisor of $r$. Putting $r' = \frac rp$ in~(\ref{cond2}) shows that $m_{\frac rp} = 1$, so $\frac rp \in X_r$. This establishes the first condition of Lemma~\ref{manylem}. Now suppose $q$ is relatively prime to $r$. Then $q$ is congruent modulo $r$ to a unique representative $b$ in $\{n-r, n-r+1, \ldots, n-1\} \subset X_0$. Since $\GCD(r,b)=1$, we have by~(\ref{cond2}) that $m_b = 1$, so $b \in X_r$. Thus both conditions of Lemma~\ref{manylem} are satisfied, completing the induction step. We have proved $LR([n-1]_{\mm}) = LR(X_{n-1}) \le 1/n$. To prove that $LR([n-1]_{\mm}) \ge 1/n$, we show that, at time $1/n$, every runner $m_r r \in [n-1]_{\mm}$ has distance at least $1/n$. It suffices to show that $m_r r$ is not divisible by $n$, since this implies $\norm{m_r r \frac1n} \in \left\{\frac1n, \frac2n, \dots, \frac{n-1}n \right\}$. This is clearly true if $m_r=1$, since $1 \le m_r r < n$. Suppose that $m_r \ge 2$. Again by Lemma~\ref{coplem} we have $(m_r-1)(n-r) \le r/2$. In particular $1 \le m_r(n-r) \le r/2 + (n-r) < n$, so $n$ does not divide $m_r(n-r)$. Therefore $n$ does not divide $m_r r$. This completes the proof of Theorem~\ref{manythm}. \qed One naturally wonders whether %the sufficient condition of Theorem~\ref{manythm} is also necessary. the converse of Theorem~\ref{manythm} is true (when more than one runner is properly accelerated). In the most general sense, this is certainly not the case: given an arbitrary rational speed vector $\vv \in (\Q - \{0\})^{n-1}$, it is easy to choose $\mm$ so that $[n-1]_{\mm}$ is a scalar multiple of $\vv$. Thus, in order to obtain a necessary condition one might need to restrict $\mm$ such that the entries of $[n-1]_{\mm}$ are relatively prime as in (\ref{wlog}), or perhaps bound the cardinality of $\{r \in [n-1] : m_r \ge 2 \}$ by a suitable function of $n$. The status of either of these formulations is currently open. It is not obvious that the GCD conditions of Theorem~\ref{manythm} can be simultaneously satisfied by several properly accelerated runners. We conclude this section by showing that tight speed sets can indeed be constructed in which the set of properly accelerated speeds is arbitrarily large. %%%%%%%%%%%%%%%%%%% \begin{corollary} \labl{flex} Let $(a_1,a_2,\dots,a_k)$ be a sequence of positive integers. Then there are infinitely many tight speed vectors of the form $[n-1]_{\mm}$ where $(a_k,a_{k-1},\dots,a_1)$ is a subsequence of the sequence $( m_1, m_2,\dots,m_{n-1} )$ of entries in $\mm$. \end{corollary} %\noindent {\bf Proof: } {\it Proof.} Let $r(m,s)$ be any function such that $r(m,s)$ is a positive integer having a common factor with every element of $\{s, \ldots, ms-1\}$. There is considerable freedom in the choice of $r(m,s)$ --- in Section~\ref{mintight} we determine the smallest possible value of $r$ --- but here we may simply take $r(m,s)$ to be any multiple of $(ms-1)!$. Let~$s_1$ be any integer greater than one, and define $s_2,\dots,s_{k+1}$ as follows. $$ s_{i+1} = s_i + \LCM (\,r(a_1,s_1),\ldots,r(a_i,s_i)\,) \quad ( i=1,2,\dots,k ). $$ % Now take $n = s_{k+1}$, and define $\mm = \langle m_1,\dots,m_{n-1}\rangle$ by $$ m_i = \left\{\begin{array}{ll} a_j &\textrm{if } i=n-s_j \textrm{ for some } j\in\{1,2,\dots,k\} \\ 1 & \textrm{otherwise.}\end{array} \right. $$ By construction, we have for each $j \in \{1,\dots,k\}$ that $n = s_{k+1} \modeq{s_j}{r(a_j,s_j)}$, so $n - s_j$ is divisible by $r(a_j,s_j)$ and thereby satisfies the condition of Theorem~\ref{manythm}. Therefore $[n-1]_{\mm}$ is a tight speed vector. By varying the choice of $s_1$ and the choice of the function $r(m,s)$, we obtain infinitely many different sequences $\{s_i\}$ and thus infinitely many distinct tight speed vectors. \qed In this construction, $n$ grows very quickly with $k$. For example, using $s_1=2$ and values of $r(m,s)$ provided in Section~\ref{mintight} we find: if $[n-1]_{\mm}$ is tight and $\mm$ contains the subsequence $(2,3)$, then the construction requires that $$ n \ge 2 + 2\cdot3\cdot5 + 2\cdot3\cdot5\cdot7\cdot37\cdot41\cdot43\cdot47\cdot53\cdot59\cdot61 \approx 1.2 \cdot 10^{14}. $$ % Applying the above construction with the prescribed subsequence $(2,2)$ requires that $n \ge 2 + 2\cdot3 + 2\cdot3\cdot11\cdot13 = 866$. At the start of this section, we described the tight speed vector $[n-1]_{\mm}$ where $n=74$ and $\mm = \langle1,1,\dots,1,1,2,1,2,1\rangle$. Thus the values of $n$ provided by this construction are likely far from optimal. \vskip 30pt %\section{Optimization} \section*{\normalsize 4. Optimization} \refstepcounter{section} \labl{mintight} The arithmetic condition in the statements of Theorems \ref{mainthm} and \ref{manythm} gives rise to an optimization problem which is of independent interest. If a speed set of the form \m{n-1}{r}{mr} is tight, then $r$ (and thus $n$) must be quite large compared to integers $m$ and $s:=n-r$. %Precisely, the integer $r$ must be large enough to %have a common factor with each integer %in the interval $[s, s+1, \dots, ms-1]$. We solve here the problem of finding, for a given pair $m,s$, the least possible value of~$r$. %We briefly considered the problem %of finding a smallest tight speed set of the form %$[n-1]_{\mm}$ where $\mm$ contains a prespecified subsequence %$(a_k, a_{k-1}, \dots, a_1)$. %The value of $n$ and the %positions of the entries $a_2, a_3,\dots,a_k$ within $\mm$ are %somewhat constrained by the function $r(m,s)$ referred to in %the proof of Corollary~\ref{flex}. %Only the position of~$a_1$ %(which equals $n-s_1$) %is flexible. %More precisely, %$s_1$ can be prespecified %to be any integer greater than one. %This motivates the question ``How does $n$ depend on $s_1$ and $a_1$?'' %We now investigate this for the case of one accelerated runner, $k=1$. We say a triple $(r,m,s)$ is {\it tight} if \m{r+s-1}{r}{mr} satisfies the condition of Theorem~\ref{mainthm}. That is, $(r,m,s)$ is tight if $r$ has a common factor with each integer in $\{s, s+1, \dots, ms-1\}$. For example, $(30, 3, 2)$ is tight since $30$ has a common factor with each of $2,3,4,5$; and hence $\langle 1,2,\ldots,29,90,31 \rangle$ is a tight speed vector. % It is clear that if $(r,m,s)$ is tight then so is $(dr,m,s)$ for any $d\in \N$. We say $(r,m,s)$ is {\it minimally tight} if it is tight, but $(r/d,m,s)$ is not tight for any prime divisor $d$ of $r$. Table~\ref{tabl} gives all minimal tight triples $(r,m,s)$ for some small values of $m$ and $s$. Also listed are those integers $s, s+1, \dots, ms-1$, required to have a common factor with $r$. Notice that for some pairs $(m,s)$, such as $(2,10)$ and $(2,11)$, there is more than one value of $r$ for which $(r,m,s)$ is minimally tight. Such values of $r$ are easy to construct for a given $(m,s)$ by considering the possible prime factorizations of $r$. \begin{table} %\small \footnotesize \begin{verbatim} m s | all r st (r,m,s) is minimally tight| s s+1 s+2 ... ms-1 ---- 2 2 | 6 = 2*3 | 2 3 2 3 | 30 = 2*3*5 | 3 4 5 2 4 | 70 = 2 *5*7 | 4 5 6 7 2 5 | 210 = 2*3*5*7 | 5 6 7 8 9 2 6 | 462 = 2*3 *7*11 | 6 7 8 9 10 11 2 7 | 6006 = 2*3 *7*11*13 | 7 8 9 10 11 12 13 2 8 | 858 = 2*3 *11*13 | 8 9 10 11 12 13 14 15 2 9 | 14595 = 2*3 *11*13*17 | 9 10 11 12 13 14 15 16 17 2 10 | a 277134 = 2*3 *11*13*17*19 | 10 11 12 13 14 15 16 17 18 19 | b 461890 = 2 *5 *11*13*17*19 | 2 11 | a 277134 = 2*3 *11*13*17*19 | 11 12 13 14 15 16 17 18 19 20 21 | b 3233230 = 2 *5*7*11*13*17*19 | ---- 3 2 | 30 = 2*3*5 | 2 3 4 5 3 3 | 210 = 2*3*5*7 | 3 4 5 6 7 8 3 4 | 2310 = 2*3*5*7*11 | 4 5 6 7 8 9 10 11 3 5 | 30030 = 2*3*5*7*11*13 | 5 6 7 8 9 10 11 12 13 14 3 6 | 102102 = 2*3 *7*11*13*17 | 6 7 8 9 10 11 12 13 14 15 16 17 3 7 | 1939938 = 2*3 *7*11*13*17*19 | 7 8 9 10 11 12 13 14 15 16 17 18 19 20 3 8 | 6374082 = 2*3 *11*13*17*19*23 | 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 \end{verbatim} %---- %4 2 | 210 = 2*3*5*7 | 2 3 4 5 6 7 %4 3 | 2310 = 2*3*5*7*11 | 3 4 5 6 7 8 9 10 11 %4 4 | 30030 = 2*3*5*7*11*13 | 4 5 6 7 8 9 10 11 12 13 14 15 %4 5 | 9699690 = 2*3*5*7*11*13*17*19 | 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 %---- %5 2 | 210 = 2*3*5*7 | 2 3 4 5 6 7 8 9 %5 3 | 30030 = 2*3*5*7*11*13 | 3 4 5 6 7 8 9 10 11 12 13 14 %5 4 | 9699690 = 2*3*5*7*11*13*17*19 | 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 \caption{Factorizations of $r$ such that $(r,m,s)$ is minimally tight } \labl{tabl} \end{table} For integers $m,s \ge 2$, we let $r(m,s)$ denote the least positive integer $r$ such that $(r,m,s)$ is tight. Since any integer in $\{ s, s+1,\dots,ms-1\}$ which is not prime has a prime factor less than $\sqrt{ms}$, we have that $r(m,s)$ is at most the product of all the primes in the two half-open intervals $[2,\sqrt{ms}) \cup [s,ms)$. Table \ref{tabl} shows that, for small values of $s$ and $m$, $r(m,s)$ is exactly equal to the product of these primes. In fact $r(m,s)$ is exactly equal to this upper bound, with just two exceptions: $r(2,26)$ and $r(2,27)$ are smaller than this bound by a factor of five. Indeed we can prove a more general result. If $S$ is a set of real numbers then we denote by by ${\cal P} S$ the set of primes in $S$. Thus $\prod{\cal P} [\alpha, \beta)$ is the product of all primes $p$ with $\alpha \le p < \beta$. %%%%%%%%%%%%%%%%%%% \begin{theorem} \labl{interval} Let $s,t$ be positive integers with $s\ge 2$ and $t/s \ge 2$. If $(s,t) \not\in \{ (26,52)$, $(26,53)$, $(26,54)$, $(26,55)$, $(27,54)$, $(27,55)\}$ then the smallest integer having a prime factor in common with each integer in $[s,t)$ equals $\prod{\cal P} (\,[2,\sqrt{t}) \cup [s,t)\,)$. \end{theorem} %%%%%%%%%%%%%%%%%% %\newpage %%%%%%%%%%%%%%%%%% %\noindent{\bf Proof:} {\it Proof.} Let $s,t$ be as in the hypothesis. Let $r$ be the smallest integer having a common prime factor with each integer in $[s,t)$. Let $R$ be the set of primes dividing $r$ so by minimality $r = \prod R$. As in the above discussion, each integer in $[s,t)$ has a prime divisor in ${\cal P} (\,[2,\sqrt{t}) \cup [s,t) \,)$. We aim to show that, aside from the listed exceptions, we have ${\cal P} (\,[2,\sqrt{t}) \cup [s,t) \,) \subseteq R$. % Each prime $p \in {\mathcal P}[2,t/s]$ must divide~$r$ since some power of $p$ lies in $[s,t)$. Also, each prime in $[s,t)$ or whose square belongs to $[s,t)$ must divide $r$. We have established that $ {\cal P}(\,[2,t/s] \cup [\sqrt{s}, \sqrt{t}) \cup [s,t)\,) \subseteq R. $ % We define $$X = {\mathcal P}(t/s,\sqrt{s}) - R.$$ Our plan is to show that $X = \es$ if $\sqrt{t} \ge 90$, and to use a computer search for the case $\sqrt{t} < 90$. Suppose that $X\ne\es$. We define the non-empty finite union of intervals % $$ I = \bigcup_{x\in X} I_x \quad\textrm{where}\quad I_x = [s/x, t/x). %I_x = \left [\frac {s}{x}, \frac{t}{x}\right). $$ % From $X \subseteq (t/s,\sqrt{s})$ we have that $ I \subseteq (\sqrt{s},s)$. % Let $x\in X$. By considering those multiples of $x$ lying in $[s,t)$, we see that each prime in $I_x$ must divide $r$. This implies $ {\cal P}I \subseteq R.$ % Let $I'$ be the maximal interval contained in $I$ and satisfying $\sup I' = \sup I$. Let $$ X' = \{ x \in X : I_x \subseteq I'\} $$ % and let $\alpha = \min X' (= \min X)$ and $ \beta = \max X'$. % Figure \ref{numlin} may help the reader with these definitions. % \begin{figure} \begin{center} \includegraphics{numline.epsi} \end{center} \caption{A log-scale diagram for the proof of Theorem~\ref{interval}. The relative positions of $\sqrt{t}$ and $s/\beta$ may be reversed.} \labl{numlin} \end{figure} % Let $$ R' = R \cup X' - {\cal P} ( \, I' \cap [\sqrt{t},s) \, ) $$ and let $r' = \prod R'$. %We consider the integer %$$ %r' = r \prod X' / \prod{\cal P} ( \, I' \cap [\sqrt{t},s) \, ). %$$ Our goal is to establish two claims: first, that $r'$ has a common factor with every integer in $[s,t)$; second, if $\sqrt{t} \ge 90$, then $r' < r$, contradicting the choice of $r$. Suppose, for contradiction, that some integer $w \in [s,t)$ has no prime factor in $R'$. Then $w$ has a prime factor $p \in {\cal P} ( \, I' \cap [\sqrt{t},s) \, )$. As $\sqrt{w} < p < w$, the integer $w$ has another prime factor, say $q < \sqrt{w}$. % Because $p \in I'$, we have that $p \in I_x$, for some $x \in X'$. In particular $s/x \le p$, so % \begin{equation} \labl{q-ineq} %q \le w/p < t/p \le t x/s \le t \beta/s. q \le \frac wp < \frac tp \le \frac {tx}s \le \frac {t \beta}s. \end{equation} % Since $q \notin R'$, we have that $q \in X-X'$, so $I_q \subseteq I - I'$. By the definition of $I'$, we have $\sup I_q < \min I'$, so $t/q < s / \beta$. This contradicts~(\ref{q-ineq}) %$q \le t \beta /s$ and establishes the first claim. \smallskip For the second claim, we aim to show that $\ln\prod X' < \ln\prod {\cal P} (\, I' \cap [\sqrt{t},s) \, )$ for $\sqrt{t} \ge 90$. % Using the facts $X' \subseteq {\cal P}[\alpha,\beta]$ and $ I'\cap \, [\sqrt{t},s) \supseteq [\,\max\{s/\beta,\sqrt{t}\},\,t/\alpha\,)$, it is sufficient to establish that \begin{equation}\labl{ineq1} \ln\prod {\cal P[\alpha,\beta]} < \ln\prod {\cal P} [\,\max\{s/\beta,\sqrt{t}\}\,,\,t/\alpha ). \end{equation} We will make use of the following estimates for the Prime Number Theorem which are readily verified using the effective bounds given by Rosser and Schoenfeld \cite{RS}. % \begin{equation} \labl{RSthm}\textit{ \parbox{13cm}{ For any real $\ell < 1$ there exists $z_0$ such that, for all real $z \ge z_0$, we have $ \ell z < \ln \prod {\cal P}[2,z] < 1.017 z$. }} \end{equation} % Some pairs $(\ell,z_0)$ which are valid for~(\ref{RSthm}) are given in the following table. % \begin{equation} \labl{ptable} \!\!\!\!\!\! \begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c} $\ell$&.485&.595&.662&.703&.722&.761&.792&.807&.816&.828&.843&.849 \\ \hline $z_0$ & 5 & 11 & 17 & 29 & 37 & 41 & 59 & 67 & 71 & 97 &101 &127 \end{tabular} \end{equation} The following estimates use the hypothesized bound $t/s \ge 2$ and assume $\sqrt{t} \ge 90$. We have that $t/\alpha > t/\sqrt{s} \ge \sqrt{2t} > 127$, so $\ln\prod{\cal P}[2,t/\alpha) \ge .849 t/\alpha$ by~(\ref{ptable}). Thus the right hand side of (\ref{ineq1}) is bounded below by % \begin{equation}\labl{rbound} .849\, \frac t{\alpha} - 1.017\,\max\!\left\{\sqrt{t}\,,\frac s{\beta}\right\}. \end{equation} If $\sqrt{t} \le s/\beta$, then using the fact $\alpha \le \beta < \sqrt{s}$ we may bound (\ref{rbound}) from below. % \begin{eqnarray*} .849 \,\frac t{\alpha} - 1.017 \frac s{\beta} &\ge& .849 \,\frac{2s}{\beta} - 1.017 \frac s{\beta} = .681 \frac s{\beta} \ge .681 \sqrt{t} \\ &\ge& 1.362 \, \frac s{\sqrt{t}} \ge 1.362 \, \beta > \ln\prod {\cal P} [2,\beta]. \end{eqnarray*} % We have proved (\ref{ineq1}) in this case. We henceforth assume $\sqrt{t} > s/\beta$. The left hand side of (\ref{ineq1}) is bounded above by \begin{equation}\labl{lbound} \left\{\begin{array}{ll} 1.017 \beta - .761 \alpha & \mbox{if }\alpha \ge 41\\ 1.017 \beta & \mbox{if }\alpha < 41. \end{array}\right. \end{equation} % Since (\ref{lbound}) is increasing with $\beta$, and (\ref{rbound}) is independent of $\beta$, we may assume that $\beta = \sqrt{s}$. Suppose first that $\alpha \ge 41$. Then the difference of (\ref{rbound}) and (\ref{lbound}) is bounded below by % \begin{eqnarray*} .849\, \frac t{\alpha} - 1.017 \sqrt{t} - 1.017 \sqrt{s} + .761 \alpha &\ge& .849 \, \frac t{\alpha} + .761 \alpha - 1.017 \left (1 + \frac 1{\sqrt{2}}\right) \!\sqrt{t} \\ &\ge& \left(.849\sqrt{2} + \frac{.761}{\sqrt{2}} - 1.737\right) \sqrt{t} > .001 \sqrt{t} > 0. \end{eqnarray*} % (We have used the fact $.849\,t/\alpha + .761\alpha$ is decreasing in $\alpha$ for $\alpha \le \sqrt{t}$, and that $\alpha \le \sqrt{t/2}\,$.) Therefore~(\ref{ineq1}) holds for $\alpha \ge 41$. Now suppose $\alpha < 41$ and $\sqrt{t} \ge 90$. Then (\ref{rbound}) is bounded below as follows. % \begin{eqnarray*} .849\,\frac t{\alpha} - 1.017 \sqrt{t} &\ge& .849\,\frac{90}{41}\sqrt{t} - 1.017\sqrt{t} \ge .846\sqrt{t} \\ &\ge& 1.196\sqrt{s} > \ln\prod{\cal P}[2,\sqrt{s}\,] \ge \ln\prod {\cal P} [\alpha,\beta]. \end{eqnarray*} We have established the theorem for all but a finite number of pairs $(s,t)$. We now outline an efficient computational method to verify the remaining cases in which $2s \le t < 8100$ and $\alpha, \beta \in {\mathcal P} (t/s, \sqrt{s}) \subseteq {\mathcal P} [3,61]$. We select pairs $\alpha \le \beta$ from ${\mathcal P} [3,61]$ and verify (\ref{ineq1}) for all integers $t \in [\,2 \beta^2 + 2\,, \,8100\,]$ and where $s = \lfloor t/2 \rfloor$. It suffices to test this single value of $s$ since the right hand side of (\ref{ineq1}) increases as $s$ decreases. The search is further accelerated by observing that a short interval of primes contained as terms in the right hand side of (\ref{ineq1}) can serve to simultaneously check several values of $t$. The resulting computation reveals the six exceptions in the statement of the theorem, where $\alpha = \beta = 5$ and $52 \le t \le 55$. \qed It is easy to see that Theorem~\ref{interval} remains true, with a finite number of exceptions, when the bound $t/s \ge 2$ in the statement is replaced by $t/s \ge 1+\e$, for any $\e >0$. Finding these exceptions becomes computationally expensive for small values of $\e$, since the bound $\sqrt{t} \ge 90$ in the proof would have to be substantially increased. \vskip 30pt \renewcommand{\refname}{{\normalsize References}} \begin{thebibliography}{99} \bibitem{BW} {\sc U.~Betke, J.~M.~Wills}, Untere Schranken f\"ur zwei diophantische Approximations-Funktionen, {\it Monatsh.\ Math.\/} {\bf 76} (1972), 214--217. \bibitem{B} {\sc W.~Bienia, L.~Goddyn, P.~Gvozdjak, A.~Seb\H{o}, M.~Tarsi}, Flows, view-obstructions, and the lonely runner, {\it J. Combin. Theory Ser. B} {\bf 72} (1998), 1--9. \bibitem{BHK} {\sc T.~Bohman, R.~Holzman, D.~Kleitman}, Six lonely runners, {\it Electron.\ J.~Combin.\/} {\bf 8}(2) (2001), R3. \bibitem{CYG} {\sc Y.~G.~Chen}, On a conjecture about diophantine approximations.~I. (Chinese), {\it Acta Math.\ Sinica\/} {\bf 33} (1990), 712--717. \bibitem{C1} {\sc T.~W.~Cusick}, View-obstruction problems, {\it Aequationes Math.\/} {\bf 9} (1973), 165--170. \bibitem{C2} {\sc T.~W.~Cusick}, View-obstruction problems in $n$-dimensional geometry, {\it J.~Combin.\ Theory Ser.~A} {\bf 16} (1974), 1--11. \bibitem{C3} {\sc T.~W.~Cusick}, View-obstruction problems.~II, {\it Proc.\ Amer.\ Math.\ Soc.\/} {\bf 84} (1982) 25--28. \bibitem{CP} {\sc T.~W.~Cusick, C.~Pomerance}, View-obstruction problems.~III, {\it J.~Number Theory\/} {\bf 19} (1984) 131--139. \bibitem{R} {\sc J.~Renault}, View-obstruction: a shorter proof for 6 lonely runners, {\it Discrete Math.\/} {\bf 287} (2004), 93--101. \bibitem{RS} {\sc J.~B.~Rosser, L.~Schoenfeld}, Approximate formulas for some functions of prime numbers, {\it Illinois J.~Math.\/} {\bf 6} (1962), 64--94. \bibitem{W0}{\sc J.~M.~Wills}, Zwei S\"atze \"uber inhomogene diophantische Approximation von Irrationalzahlen. {\it Monatsh.\ Math.\/} {\bf 71} (1967) 263--269. \bibitem{W1}{\sc J.~M.~Wills}, Zur simultanen homogenen diophantischen Approximation.~I, {\it Monatsh.\ Math.\/} {\bf 72} (1968) 254--263. \bibitem{W2}{\sc J.~M.~Wills}, Zur simultanen homogenen diophantischen Approximation.~II, {\it Monatsh.\ Math.\/} {\bf 72} (1968) 268--281. \bibitem{W3}{\sc J.~M.~Wills}, Zur simultanen homogenen diophantischen Approximation.~III, {\it Monatsch.\ Math.\/} {\bf 74} (1970) 166--171. \bibitem{W4}{\sc J.~M.~Wills}, Zur simultanen diophantischen Approximation., {\it Zahlentheorie (Tagung, Math. Forschungsinst. Oberwolfach, 1970)\/} Ber. Math. Forschungsinst., Oberwolfach, No.~5, Bibliographisches Inst., Mannheim, 1971, pp.\ 223--227. \end{thebibliography} \end{document}