%Revised version to be sent to JCTB Friday March 21, 97 %Typset via latex2e. \documentstyle[twoside,titlepage,11pt,amsfonts]{article} %\documentstyle[titlepage,11pt,amsfonts]{article} \setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in} \setlength{\textwidth}{6.5in} \setlength{\topmargin}{-1.0 cm} \setlength{\textheight}{8.75in} \def\qed{\hfill$\Box$} %letters \newcommand{\Hs}{{\cal H}} \newcommand{\As}{{\cal K}} \newcommand{\Ks}{{\cal K}} \newcommand{\Qs}{{\cal Q}} \newcommand{\res}[1]{{\langle #1 \rangle}} %\def\Nset{\hbox{I\hskip-0.20em I\hskip-0.35em N}} %\def\Qset{\hbox{\hbox{Q\hskip-0.525em\lower-0.097ex % \hbox{\vrule height1.47ex width0.07em}}\hskip0.50em}} %\def\Rset{\hbox{I\hskip-0.23em R}} %\def\Zset{\hbox{Z\hskip-0.38em Z}} %\def\Nset{{ \cal N}} %\def\Zset{{ \cal Z}} %\def\Qset{{ \cal Q}} %\def\Rset{{ \cal R}} \def\Nset{{ \mathbb N}} \def\Zset{{ \mathbb Z}} \def\Qset{{ \mathbb Q}} \def\Rset{{ \mathbb R}} \newtheorem{thm}{Theorem}[section] \newtheorem{lm}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{conj}[thm]{Conjecture} \newenvironment{case}[1] {\[ #1 \left\{\begin{array}{ll}}{\end{array}\right.\]} \def\leftv{\left\vert} \def\rightv{\right\vert} %*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*% % 5. NON-ITALIC LETTERS IN FORMULAS % %*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*% % things like \arccos in PLAIN TeX \def\aff{\mathop{\rm aff}} \def\cone{\mathop{\rm cone}} \def\conv{\mathop{\rm conv}} \def\dim{\mathop{\rm dim}} \def\lin{\mathop{\rm lin}} \def\mod{\mathop{\rm mod}} \def\lat{\mathop{\rm lat}} \def\pr{\mathop{\rm par}} \def\gcd{\mathop{\rm g.c.d}} %*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*% % 8 THEOREMS AND SUCH % %*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*% % print #1 bold and use slanted typestyle until reaching \endtheorem \def\theorem#1{\par\vskip 5pt\noindent{\bf #1}\quad\bgroup\sl} \def\endtheorem{\egroup} \def\proof{\par\vskip 3pt\noindent \hbox{\bf Proof.}\quad} \def\qed{\hfill$\Box$\vskip 0.05cm} %*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*% \begin{document} \renewcommand{\baselinestretch}{1.2}\small\normalsize \title{ % {\Large Technical Report}\\ \ \\ % {\huge Flows, Jumps and the Lonely Runner}} {\huge Flows, View-Obstructions and the Lonely Runner}} \author{Wojciech Bienia \thanks{ENSIMAG, Laboratoire Leibniz-IMAG, France}\\ Luis Goddyn \thanks{Simon Fraser University, Vancouver, Canada. Research supported by NSERC of Canada}\\ Pavol Gvozdjak \thanks{Simon Fraser University, Vancouver, Canada. }\\ Andr\'as Seb\H o \thanks{CNRS, Laboratoire Leibniz-IMAG, France. Research supported by W.~Cunningham's grant of NSERC of Canada }\\ Michael Tarsi\thanks{Tel Aviv University, Israel. Research supported in part by a grant from the Israel Science Foundation.}} \date{ March 21, 1997} \maketitle \begin{abstract} We prove the following result. \begin{quote} {\sl Let $G$ be an undirected graph. If $G$ has a nowhere zero flow with at most $k$ different values, then it also has one with values from the set $\{1,\ldots ,k\}$.} \end{quote} When $k \ge 5$, this is a trivial consequence of Seymour's ``six-flow theorem''. When $k\le 4$ our proof is based on a lovely number theoretic problem which we call the ``Lonely Runner Conjecture''. \begin{quote} {\sl Suppose $k$ runners having nonzero constant speeds run laps on a unit-length circular track. Then there is a time at which all runners are at least $1/(k+1)$ from their common starting point.} \end{quote} This conjecture appears to have been formulated by J.\ Wills ({\it Montash.\ Math.\/} {\bf 71} (1967)) %regarding diophantine approximation) and independently by T.~Cusick ({\it Aequationes Math.\/} {\bf 9} (1973)). %regarding view obstruction theory) Fortunately for our purposes, this conjecture has been verified for $k\le 4$ by Cusick and Pomerance ({\it J.\ Number Theory\/} {\bf 19} (1984)) in a complicated argument involving exponential sums and electronic case checking. A major part of this paper is an elementary self-contained proof of the case $k=4$ of the Lonely Runner Conjecture. %\end{abstract} %\pagebreak %\thispagestyle{empty} \vspace{9ex} \noindent {\bf AMS Classifications (1991): } 11J13, (05B35, 05C15, 05C50, 11J71, 11K60, 52C07, 90B10) \vspace{3ex} \noindent {\bf Keywords: } Nowhere zero flow, regular matroid, diophantine approximation, view obstruction. \vspace{3ex} \noindent {\bf Short title: } Flows and View Obstructions \end{abstract} %\vspace{3ex} \noindent %{\bf Running head: } %Flows, Jumps and the Lonely Runner %\vspace{3ex} \noindent %{\bf Contact addresses: } %\begin{center} %\parbox[t]{6.5cm}{ % Luis Goddyn or Pavol Gvozdjak \\ % Dept.\ of Math.\ and Stats. \\ % Simon Fraser University \\ % Burnaby BC V5A 1S6 \\ % CANADA \vspace{1ex}\\ % {\tt goddyn@math.sfu.ca \\ % gvozdjak@math.sfu.ca } %} %\parbox[t]{7cm}{ % Wojciech Bienia or Andr\'as Seb\H{o} \\ % Laboratoire Leibniz-IMAG \\ % Universit\'e Fourier, BP 53 \\ % 38041 Grenoble, Cedex 09 \\ % FRANCE \vspace{1ex}\\ % {\tt bienia@imag.fr \\ % sebo@imag.fr } %} %\\ %\vspace{6ex} %\parbox[t]{6.5cm}{ % Michael Tarsi \\ % School of Mathematical Sciences, \\ % Department of Computer Science, \\ % Tel-Aviv University \\ % Tel-Aviv 69978 \\ % ISRAEL \vspace{1ex}\\ % {\tt tarsi@math.tau.ac.il } %} %\end{center} \newpage %\def\baselinestretch{1.2}\small\normalsize \pagestyle{myheadings} %\pagestyle{myheadings}\markright{Flows, Jumps and the Lonely Runner} \setcounter{page}{1} \section{Introduction} Let $G=(V,E)$ be an undirected graph. A {\it nowhere zero flow\/} of $G$ is an orientation of $G$ supplied with a vector $f=(f_e)$ of positive integers indexed by $E(G)$, such that for every $v\in V(G)$ the sum of $f_e$ on edges entering $v$ is the same as that on edges leaving $v$. The number $f_e$ is called the {\em value} of the edge $e$. %We often view $f$ as a vector $(f_e)$ indexed by $E(G)$. The theory of nowhere zero flows is a major topic in combinatorics related to graph coloring and %the four color conjecture the cycle double cover conjecture; see~\cite{J2,S3,TU}. The main result of this paper is the following. \begin{thm}\label{flow} Let $G$ be an undirected graph. If $G$ has a nowhere zero flow with at most $k$ distinct values, then it also has one with all values from the set $\{1,\ldots ,k\}$. \end{thm} In view of the matroid duality~\cite{TU,T,J2,O,S3} between vertex colorings and nowhere zero flows there is a cographic analogue to Theorem \ref{flow}. A {\em coloring} of $G$ %or {\it assignment of potentials\/} is a function $c : V(G) \rightarrow \Rset$, so that %and the {\it potential difference\/} for all $xy \in E$, $c(x) \ne c(y)$. \begin{thm} \label{col} If $G$ has a coloring with real numbers so that the set $\{|c(x)-c(y)| : xy\in E\}$ has at most $k$ distinct values, then $G$ has a $(k+1)$-coloring (and thus one where $|c(x)-c(y)|\in \{1,\ldots,k\}$ for all $xy\in E$.) \end{thm} Theorem \ref{col} is easy to prove: By orienting each edge toward the endpoint with the larger color and identifying the color classes, one obtains an acyclic digraph having maximum out-degree $k$. An easy greedy algorithm results in a ($k+1$)-coloring of $G$. %We actually get more in this way: %the $k$-coloration one gets ... Theorem~\ref{flow} is more difficult. Our proof relies on Seymour's {\it six-flow theorem\/} \cite{S2} and a number theoretic result of Cusick and Pomerance \cite{CP} to which we give a short proof. We state here the six-flow theorem. A graph is called {\em bridgeless}, if it has no bridge, where $e\in E$ is a {\em bridge} if $G-e$ has more components than $G$. \begin{thm}\label{flow6} Every bridgeless graph has a nowhere zero flow with values from the set $\{1,\ldots ,5\}$. \end{thm} There is a common generalization of Theorems \ref{flow} and \ref{col} regarding flows in regular matroids (see \cite{O,T}) which is strongly suggested by Seymour's {\it regular matroid decomposition theorem\/}~\cite{S1}. A matrix is {\it totally unimodular\/} if every subdeterminant belongs to $\{0,\pm 1\}$. \begin{conj}\label{matroid} Let $A$ be a totally unimodular matrix and suppose that $Af=0$ has a real solution $f=(f_e)$ where each $f_e$ is nonzero and where $|\{|f_e| : e\in E(G) \}| \le k$. Then there exists a solution $f'=(f'_e)$ with each $|f'_e| \in \{1, 2,\ldots, k\}$. \end{conj} %Similar questions regarding {\it group-valued flows\/}~\cite{TU,J2} %can also be formulated. The analogous statement concerning {\it group-valued flows\/}~\cite{TU,J2} is false. For example, the graph with two vertices and three parallel edges has a flow with range $\{1\}$ in $Z_3$, but not in the integers. The paper is organized as follows. In Section 2, Conjecture~\ref{matroid} is reduced to the ``Lonely Runner Problem''; in particular Theorem~\ref{flow} is reduced to the special case $k\le 4$. A general proof technique for this problem is introduced in Section 3, and applied to the case $k=4$ in Section 4. \section{Runners and Flows} \noindent Let us informally state the {\it Lonely Runner Problem\/}: At time zero, $k$ participants depart from the origin of a unit length circular track to run repeated laps. Each runner maintains a constant nonzero speed. Is it true that regardless of what the speeds are, there exists a time at which the $k$ runners are simultaneously at least $1/(k+1)$ units from the starting point? The term ``lonely runner'' reflects an equivalent %`projective' formulation in which there are $k+1$ runners with distinct speeds. %one of which acts as a moving reference. Is there a time at which a given runner is `lonely', that is, at distance at least $1/(k+1)$ from the others? This poetic title (given by the second author) made its way through an internet inquiry (of the second and last author) up to the cover page of a public relation booklet for the Weissman Institute in Israel~\cite{WI}. We introduce some notation. The sets of real numbers and positive integers are denoted $\Rset$ and $\Nset$ respectively. The residue class of $a\in \Rset$ modulo 1 (called the {\it fractional part\/} of $a$) is denoted by $\res{a}$. We view the unit-length circle $C$ as the set $\{ \res{a}: a\in\Rset\}$, which we frequently identify with the real interval $[0,1)$. An instance of the lonely runner problem consists of a set of {\it runners\/} $R:=\{1,2,\ldots , k\}$ and a {\it speed vector\/} $v:= (v_1,\ldots , v_k )$ having nonzero real entries. At time $t=0$, each $r\in R$ begins running on $C$ from the point $0$ maintaining the constant speed $v_r$. The {\it position\/} of runner $r$ on $C$ at time $t$ is $\res{tv_r}$. The {\it position\/} of $R$ at time $t$ is the vector $\res{tv}:=(\res{tv_1},\ldots,\res{tv_k}) \in [0,1)^k$. A vector $x=(x_1,\ldots,x_k) \in [0,1)^k$ is {\it a position\/} (for the speed vector $v$) if there exists $t\in \Rset$ with $x=\res{tv}$. The set of all positions is denoted $X = X(v) \subseteq [0,1)^k$. The distance between two points on $C$ is the length of the shorter of the two (arc) intervals between them. We say that $r\in R$ is {\it distant\/} (from $0$) {\it in $x\in X$\/} or {\it at time $t$\/} if $x_r = \res{tv_r} \in [\frac{1}{k+1},\frac{k}{k+1}]$. A subset $R'\subseteq R$ is {\it distant\/} (in some position $x$) if each $r\in R'$ is distant in $x$. (here, $k$ is understood by context to equal $|R|$, not $|R'|$). The aforementioned internet inquiry led us to the following assertion, which we call the {\it Lonely Runner Conjecture\/}. This conjecture appears to have been introduced by J.\ Wills \cite{W0} and again, independently by T.~Cusick~\cite{C1}. \begin{conj} For all $k\in \Nset$ and $v\in(\Rset - \{0\})^k$, there exists a position where $R$ is distant. \end{conj} %This problem has been stated in different terms in various papers. This problem appears in two different contexts. Cusick~\cite{C1,C2,C3,CP} was motivated by a beautiful application in $n$ dimensional geometry --- {\it view obstruction problems}. Our statement of the problem is closer to the diophantine approximation approach of Wills~\cite{BW,W0,W1,W2,W3,W4}. A more general conjecture appears in \cite{CYG}. The cases $k=2,3,4$ were first proved in \cite{W0},\cite{BW},\cite{CP} respectively. \begin{thm}\label{runners4} If $k\le 4$, then for any $v\in (\Rset - \{0\})^k$ there exists a time at which $R$ is distant. \end{thm} The proof by Cusick and Pomerance~\cite{CP} of the case $k=4$ is not easy, and requires a computer check. In sections~3 and~4 we provide a simple self-contained proof. Section~3 also contains a very short proof for the case $k= 3$. We now prove Theorem~\ref{flow} using Theorems~\ref{runners4} and~\ref{flow6}. %We begin by proving Theorem~\ref{flow} using Theorem~\ref{runners4}: \noindent {\bf Proof of Theorem \ref{flow}.} Let $f$ be a nowhere zero flow with $k$ different values. If $k\ge 5$, then the result is a trivial consequence of Theorem~\ref{flow6} since any graph having a nowhere zero flow must be bridgeless. If $k\le 4$, then by Theorem~\ref{runners4} there exists $t\in\Rset$ such that the fractional part of each entry of $tf$ is in the interval $[\frac{1}{k+1},\frac{k}{k+1}]$. The flow $tf$ is a feasible flow in the edge-capacitated network $(G,l,u)$ where $l=\lfloor tf \rfloor$ and $u=\lceil tf \rceil$ (we take floors and ceilings componentwise). But then %network flow theory there also exists a feasible integer-valued flow for $(G,l,u)$ (Ford and Fulkerson \cite{FF}), in which each edge $e$ has value either $\lfloor tf_e \rfloor$ or $\lceil tf_e \rceil$. Let us denote this flow by $\lfloor tf \rceil$. Thus $tf - \lfloor tf \rceil $ is a flow with all entries in $[\frac{-k}{k+1},\frac{-1}{k+1}]\cup [\frac{1}{k+1},\frac{k}{k+1}]$. Multiplying this flow by $k+1$ and reorienting the edges corresponding to negative entries yields a flow with values in $[1,k]$. Again, there also exists then an integer flow with values in $[1,k]$. $\Box$ Note: we may loosely denote the final flow in the proof of Theorem 1.1 as $\lfloor(k+1)(f-\lfloor tf\rceil)\rceil$. We remark that this proof can be directly generalized to flows in regular matroids by applying Hoffman's theorem \cite{H} in order to define $f' = \lfloor(k+1)(f-\lfloor tf\rceil)\rceil$. Thus, Conjecture \ref{matroid} is a weak form of the Lonely Runner Conjecture. \begin{thm}\label{matroid_flow} For any $k\in \Nset$, if the Lonely Runner Conjecture holds true for $k$ runners, then the statement of Conjecture \ref{matroid} holds true for that particular value of $k$. \end{thm} \vspace{1.5ex} The remainder of this paper is devoted to the Lonely Runner Conjecture. Wills~\cite{W0} reduced the Lonely Runner Conjecture from the case of irrational speeds to the rational case. So when proving any case $k\ge1$, one can assume without loss of generality that $v\in \Nset ^k$, whence the speeds express the number of laps the runners make in unit time. One can further assume that $t\in [0,1)$, although there is usually no advantage in doing so. \noindent {\bf Proof of Theorem \ref{runners4} when \boldmath $k\le2$.} The case $k=1$ is trivial. In case $k=2$ we prove a stronger statement: \begin{quote} {\sl Suppose $v_1,v_2 \in \Nset$ are relatively prime speeds. At any time $t$, the nearer runner has distance at most $\left\lfloor \frac{v_1+v_2}{2} \right\rfloor / (v_1+v_2)$. Moreover, this bound is achieved at time $t = \frac{\tau}{v_1+v_2}$ for some $\tau \in \Nset$.\/} %then both runners are at distance %$\left\lfloor \frac{v_1+v_2}{2} \right\rfloor / (v_1+v_2) \ge 1/3$ %at time $\frac{\tau}{v_1+v_2}$ for some $\tau \in \Nset$. Furthermore, %this distance cannot be replaced by a larger number. \/} \end{quote} Whenever the distance from 0 to the nearer runner is maximum, we have $\res{tv_1} = 1-\res{tv_2}$. This equality holds if and only if $t$ is an integer multiple of $1/(v_1+v_2)$. For such $t$, both runners are at distance $a/(v_1+v_2)$ for some integer $a \le \lfloor \frac{v_1+v_2}{2} \rfloor$. Since gcd$(v_1,v_1+v_2)=1$ we can solve the congruence $v_1\tau \equiv \lfloor (v_1+v_2)/2\rfloor \bmod v_1+v_2$, to obtain a time at which the bound on $a$ is achieved, proving the statement.\qed \vfil\eject \section{Pre-jumps} We state the fact that {\em the set $X$ of positions is closed under addition modulo 1} in a particular form suggesting a technique used by all the proofs hereafter. \noindent \begin{description}\item[(1)] {\sl If $x_1 ,x_2\in X$ and $\alpha \in\Zset$, then the vector $x = \res{x_1+\alpha x_2 } \in [0,1)^k$ is also in $X$. If moreover, $x_1=\res{t_1v}$, $x_2=\res{t_2v}$, and $t\equiv t_1+\alpha t_2\mod 1$, then $x=\res{tv}$. \/} \end{description} Our use of (1) is as follows. We first note the existence of certain ``key'' positions in $X$ which we call {\it pre-jumps\/}. In the proof of our main result, it sometimes becomes convenient to add one of these pre-jumps to a position that has already been constructed, thereby obtaining a position in which all runners are distant. Our first example of pre-jumps will be used in a short proof of the case $k=3$. (Compare with the proofs in \cite{BW} and \cite{C1}.) \vskip 0.15cm \noindent \begin{description}\item[(2)] {\sl Let $v \in \Nset^k$, $k\ge 3$. If {\rm gcd}$(v_1,\ldots,v_{k-1})$ does not divide $v_k$, then there exists a time when $R$ is distant if and only if there exists a time when $R\setminus\{k\}$ is distant.} %that is, in the interval $[1/(k+1),k/(k+1)]$.} \end{description} \noindent \proof Let $d\ge 2$ be the greatest common divisor defined in the statement, and suppose without loss of generality that gcd$(d,v_k)=1$. Then \begin{eqnarray*}& \res{\frac{ 0}{d}v_r}=\res{\frac{1}{d}v_r}=\cdots= \res{\frac{d-1}{d}v_r}=0\; \mbox{ for }r = 1,\ldots,k-1 \mbox{, whereas } &\\& \{\res{\frac{0}{d}v_k},\res{\frac{1}{d}v_k},\ldots,\res{\frac{d-1}{d}v_k}\} =\{ \frac{0}{d} , \frac{1}{d} ,\ldots, \frac{d-1}{d} \}. &\end{eqnarray*} % Let now $x=\res{tv}$ be a position where $R\setminus\{k\}$ is distant. Since $R\setminus\{k\}$ is also distant in each of the $d$ positions $\res{x+\frac{j}{d}v}$ $(j=0,1,\ldots ,d-1)$, it suffices to show that $k$ is distant in one of these positions. However, this follows from the fact that $1/d$ is at most the length $1-2/(k+1)$ of the interval of distant positions since $k\ge 3$ and $d \ge 2$. %In case $k=2$ and $d=2$, we have that $v_1=d=2$, and so %both runners are distant either at time %$2/3 + 1/(2v_2)$ or at $2/3$ %(depending on whether or not 3 divides $v_2$). \qed \noindent {\bf Proof of Theorem \ref{runners4} when \boldmath $k\le 3$.} We assume that the speeds $v_1,v_2,v_3$ are distinct positive integers having no common factor. If all three speeds are odd, then $\res{\frac12v} = (\frac12,\frac12,\frac12)$, so we may assume that $v_2$ is even. By (2) we may further assume that $v_1$ and $v_3$ are odd. So $\res{\frac12v} = (\frac12 ,0,\frac12 )$, and this will provide our pre-jump $x_1=\res{t_1v}$, $t_1:=\frac12$. Consider the time interval $T:=[\frac{1}{4v_2},\frac{3}{4v_2}]$, during which runner $2$ is for the first time in the distant region $[\frac14,\frac34]$. % For $r=1,3$, let $T_r =\{t\in [0,1) :\res{tv_r}\in[\frac14,\frac34]\}$. %Each $T_r$ is comprised of $v_r$ closed intervals. If $T\setminus (T_1\cup T_3)\ne\emptyset$, then use (1) with the defined pre-jump $x_1$, an arbitrary $t_2\in T\setminus (T_1\cup T_3)$, and $\alpha =1$: $\res{(t_1+t_2)v}=(\frac12 ,0,\frac12 ) + \res{t_2v}$. Since $2$ is the only distant runner at time $t_2$, $\{1,2,3\}$ is distant at time $t_1+t_2$. %We can now assume $T\subseteq T_1\cup T_3$. %It is not possible that $T\subseteq T_i$ for some $i\in\{1,3\}$, because %then $i$ is distant at time $\frac{1}{4v_2}$, when $2$ %becomes distant for the first time. So $v_i\ge v_1$, and the equality %must be satisfied, because $i$ is still distant at time %$\frac{3}{4v_2}$. But this contradicts $v_i\ne v_2$. % We may now assume $T \subseteq T_1 \cup T_3$. Suppose that $T \subseteq T_i$, for some $i \in \{1,3\}$. Then $T$ is contained in one of the closed intervals comprising $T_i$, which implies $v_2 \ge v_i$. Furthermore, $i$ first becomes distant no later than $2$ does, so $v_2 \le v_i$ which contradicts $v_2 \neq v_i$. Thus $T\subseteq T_1\cup T_3$, $T\cap T_i\ne\emptyset$ $(i=1,3)$. Both $T\cap T_1$ and $T\cap T_3$ consist of disjoint closed intervals and their union is $T$. Hence $\emptyset\ne (T\cap T_1)\cap (T\cap T_3)=T\cap T_1\cap T_3$, and we are done. % If $T \subseteq T_2 \cup T_3$, then either %$T \subseteq T_2$, $T \subseteq T_3$ or %$T \cap T_2 \cap T_3 \neq \emptyset$. %The first two cases contradict that the speeds are distinct, %whereas in the third case we are done. %We therefore assume that there is a time $t_0 \in T$ at which %$1$ is the only distant runner. % %We claim that at some time $t_0 \in T$, $1$ is the only runner in $F$. %If not then, say, $2$ is in $F$ at time $\frac{1}{4v_1}$, so $v_2 > v_1$. %If during $T$, $v_3$ enters $F$ when or before $v_1$ first leaves $F$, %then we are done. %Thus there is a time $t_0$ just after $v_1$ leaves $F$, %at which $v_2$ is the only runner in $F$, as claimed. %It is now easy to check that $\{1,2,3\}$ is distant at time $t_0+\frac12$. \qed \section{The case $k=4$} Before completing the proof of Theorem~\ref{runners4}, we set some notation and present two more pre-jump facts which hold true whenever $k+1$ is prime. The notation $a|b$ means that $a$ evenly divides $b$. For fixed $k \ge 2$ we partition the circle $C = [0,1)$ as $\{0\} \cup C_1 \cup C_2$ where \begin{eqnarray*} C_1&:= (0,\frac{1}{k+1}) \cup (\frac{k}{k+1},1) \cup \{\frac{1}{k+1},\frac{2}{k+1},\ldots,\frac{k}{k+1}\} &\mbox{ and } \\ C_2&:=(\frac{ 1}{k+1},\frac{2}{k+1}) \cup (\frac{ 2}{k+1},\frac{3}{k+1}) \cup \cdots \cup (\frac{k-1}{k+1},\frac{k}{k+1}). &\end{eqnarray*} Given a speed vector~$v\in\Nset^k$ and a position $x \in X=X(v)$ we define $D:=\{r \in R: (k+1) | v_r \}$ and partition the runners~$R$ as $R_0(x) \cup R_1(x) \cup R_2(x)$ where \begin{eqnarray*} R_0(x)&:=&D \cup \{r\in R: x_r=0\}, \\ R_1(x)&:=&\{r\in R\setminus D: x_r \in C_1 \}, \\ R_2(x)&:=&\{r\in R\setminus D: x_r \in C_2 \}. \end{eqnarray*} % \begin{description}\item[(3)] {\sl Let $k+1$ be prime, and suppose there exists $x\in X$ in which $D$ is distant, and $|R_2(x)|<|R_0(x)|$. Then there exists a time when $R$ is distant.} \end{description} %\vskip 0.08cm % \noindent \proof We consider the list of $k$ positions $\res{x+\frac{j}{k+1}v}$ $(j=1,2,\ldots,k)$. Since $k+1$ is prime, we have \begin{eqnarray*}& \res{\frac{1}{k+1}v_r}=\cdots=\res{\frac{k}{k+1}v_r}=0 &\mbox{ if $r \in D$,} \\& \{\res{\frac{1}{k+1}v_r},\ldots,\res{\frac{k}{k+1}v_r}\} =\{ \frac{1}{k+1} ,\ldots, \frac{k}{k+1} \} &\mbox{ if $r \in R\setminus D$.} \end{eqnarray*} Using this, it is straightforward to check that, for $m=0,1,2$, each runner in $R_m(x)$ is distant in exactly $k-m$ of the listed positions. Thus, there are at most $|R_1(x)|+2|R_2(x)|$ positions in the list in which $R$ is not distant. If $|R_2(x)|<|R_0(x)|$, then $|R_1(x)|+2|R_2(x)| \frac{k}{2}=|R|/2$, whence $|R_0(x)| > |R_2(x)|$. Since $D=\{2\}$ is distant, we are done by (3). \qed \vskip 0.15cm \noindent {\bf Proof of Theorem~\ref{runners4}}. We assume $k=4$, $R=\{1,2,3,4\}$, all speeds are distinct and have no common prime factor. Consider the (proper) subset $D = \{r \in R: 5|v_r\}$. If $|D| = 0$, then $R$ is distant at time $\frac15$. Suppose $2 \le |D| \le 3$. By induction on $k$ there exists a position $y$ where $D$ is distant. Either we are done at $y$, or some runner in $R\setminus D$ is not distant, whence $|R_0(y)|+|R_1(y)|\ge |D|+1 \ge 3$, so $|R_2(y)|\le 1$ whereas $|R_0(y)| \ge |D| \ge 2 > 1 \ge |R_2(y)|$ and we are done by (3). We henceforth assume $D=\{2\}$, whence $2\in R_0(x)$ for every position $x$. If no runner is faster than $2$, then at time $\frac{1}{5v_2}$, $2$ is the only distant runner, whence $|R_2(\frac{v}{5v_2})|=0$, $|R_0(\frac{v}{5v_2})|=1$, and we are again done by (3). We thus assume $v_1 > v_2,v_3,v_4$. At least one of $v_3, v_4$, say $v_3$, is not equal to $v_1-v_2$. Since $v_2, v_3$ are distinct and less than $v_1$, the assumptions $v_3\ne v_2$ and $v_3\ne v_1 -v_2$ imply $v_3 \not\equiv\pm v_2\bmod v_1$. If $d:=$gcd$(v_1,v_3)>1$, then if $d$ divides $v_2$, we are done by (2); if it does not, we are done by (4). Thus we can assume gcd$(v_1,v_3)=1$. Then there exists $\alpha\in\Nset$, $\alpha v_3\equiv 1$ mod $v_1$. Let $x$ be the position at time $\frac{\alpha}{v_1}$. We have $x_1 = 0$ and $x_3 = 1/v_1 < 1/v_2 \le 1/5$, so $1,2 \in R_0(x)$ and $3 \in R_1(x)$. If $D=\{2\}$ is distant in $x$, then we are done by (3) since $1,2 \in R_0(x)$ whereas $3\in R_1(x)$ so $|R_2(x)| \le 1$. So we may assume $2$ is not distant in $x$. We notice two facts. First, the distance of $x_2$ from $0$ is at least twice that of $x_3$ (this follows from $v_2 \not\equiv 0,\pm v_3 \bmod v_1$ and gcd$(\alpha,v_1)=1$, which implies $x_2 = \res{\frac{\alpha}{v_1} v_2} \neq 0,\pm 1/v_1$ whence $x_2 \in [2/v_1, 1-2/v_1]$.) Second, if a runner has distance $\delta \le 1/4$ from $0$ in some position $z \in X$, then it has distance $2\delta$ in position $\res{2z}$. Let $x'$ be the first position in the sequence $\res{2x},\res{4x},\res{8x},\ldots$ in which $2$ is distant. As before, $1,2 \in R_0(x')$ whereas, by the two facts and the minimality in the choice of $x'$, $x'_3 \in (0,1/5)$ so $3\in R_1(x')$, and we are again done by (3). \qed \vspace{2ex} \noindent {\bf Acknowledgement.} The authors would like to thank Andrew Odlyzko, for directing them to the papers of J\"ung Wills and Thomas Cusick; and they thank Martin Loebl, for helpful discussions. %and for the paper of %Jaeger, Vertigan and Welsh. The fourth author would like to thank the stimulating environment of the University of Waterloo. \newpage \begin{thebibliography}{99999} \bibitem{BW} {\sc U.~Betke, J.~M.~Wills}, Untere Schranken f\"ur zwei diophantische Approximations-Funktionen, {\it Monatsch.\ Math.\/} {\bf 76} (1972), 214--217. \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{FF}{\sc L. R. Ford, D. R. Fulkerson}, Network flow and systems of representatives, {\it Canad.\ J.~Math.\/} {\bf10} (1958), 78--84. \bibitem{H}{\sc A.~J.~Hoffman}, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, {\it Proc.\ Sympos.\ Appl.\ Math., Vol.\ 10,\/} {\sc R. Bellman, M. Hall Jr.}, eds., American Mathematical Society, Providence, RI\ 1960, pp.\ 113-127. %\bibitem{J1}{\sc F.~Jaeger}, %A survey of the cycle double cover conjecture, %{\it Annals Discrete Math.\/} {\bf 27} (1985), 1--12. \bibitem{J2}{\sc F.~Jaeger}, Nowhere-zero flow problems, {\it Selected Topics in Graph Theory\/} {\bf 3} (1988), 71--95, {\sc L.~W.~Beineke and R.~Wilson}, eds., Academic Press, San Diego, CA, 1988. \bibitem{J3}{\sc F.~Jaeger}, Flows and generalized coloring theorems in graphs, {\it J.~Combin.\ Theory Ser.~B\/} {\bf 26} (1979), 205--216. %\bibitem{JVW}{\sc F.~Jaeger, D.~Vertigan, D.~Welsh}, %Computational Complexity of Polynomials, %Math. Proc. Camb. Phil. Soc., (1990), 35--108. % \bibitem{O} {\sc James G.~Oxley}, {\it Matroid Theory\/}, Oxford University Press, Oxford, 1992. \bibitem{S1} {\sc P.~D.~Seymour}, Decomposition of regular matroids, {\it J.~Combin.\ Theory Ser.~B\/} {\bf 28} (1980), 305--359. \bibitem{S2} {\sc P.~D.~Seymour}, Nowhere-zero 6-flows, {\it J.~Combin.\ Theory Ser.~B\/} {\bf 30} (1981), 130--135. \bibitem{S3} {\sc P.~D.~Seymour}, Nowhere-zero flows. Appendix: Colouring, stable sets and perfect graphs. {\it Handbook of Combinatorics, Vol.\ 1,\/} {\sc R.~Graham, M.~Gr\"otschel, L.~Lov\'asz}, eds., Elsevier, Amsterdam, 1995, pp.\ 289--299. \bibitem{T}{\sc M.~Tarsi}, Nowhere zero flow and circuit covering in regular matroids, {\it J.~Combin.\ Theory Ser.~B\/} {\bf 39} (1985), 346--352. \bibitem{TU}{\sc W.T.~Tutte}, A contribution to the theory of chromatic polynomials, {\it Canad.\ J.~Math.\/} {\bf 6} (1954), 80--91. \bibitem{W0}{\sc J.~M.~Wills}, Zwei S\"atze \"uber inhomogene diophantische Approximation von Irrationalzahlen. {\it Monatsch.\ Math.\/} {\bf 71} (1967) 263--269. \bibitem{W1}{\sc J.~M.~Wills}, Zur simultanen homogenen diophantischen Approximation.~I, {\it Monatsch.\ Math.\/} {\bf 72} (1968) 254--263. \bibitem{W2}{\sc J.~M.~Wills}, Zur simultanen homogenen diophantischen Approximation.~II, {\it Monatsch.\ 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. \bibitem{WI}Weissman Institute public relations booklet, 1994. \end{thebibliography} \newpage \vspace{3ex} \noindent {\bf Contact addresses: } \begin{center} \parbox[t]{6.5cm}{ Luis Goddyn or Pavol Gvozdjak \\ Dept.\ of Math.\ and Stats. \\ Simon Fraser University \\ Burnaby BC V5A 1S6 \\ CANADA \vspace{1ex}\\ {\tt goddyn@math.sfu.ca \\ gvozdjak@math.sfu.ca } } \parbox[t]{7cm}{ Wojtech Bienia or Andr\'as Seb\H{o} \\ Laboratoire Leibniz-IMAG \\ Universit\'e Fourier, BP 53 \\ 38041 Grenoble, Cedex 09 \\ FRANCE \vspace{1ex}\\ {\tt bienia@imag.fr \\ sebo@imag.fr } } \\ \vspace{6ex} \parbox[t]{6.5cm}{ Michael Tarsi \\ School of Mathematical Sciences, \\ Department of Computer Science, \\ Tel-Aviv University \\ Tel-Aviv 69978 \\ ISRAEL \vspace{1ex}\\ {\tt tarsi@math.tau.ac.il } } \end{center} \end{document}