The [lonely runner conjecture](http://en.wikipedia.org/wiki/Lonely_runner_conjecture)
has several formulations.
They all involve a number $n$ runners running on a circular track,
each with a different speeds, and the conjecture is that each runner is eventually
"lonely" in a technical sense.


My question is essentially the obverse,
and hopefully much easier; and so perhaps already answered:



> 
> **Q**. Let $n$ runners start at random positions on a circular track,
>  running at different speeds.
>  Is it the case that at some time $t$, it is *guaranteed*
>  that all the runners will lie within 
>  some semicircle? Or within some three-quarters circle?
>  Or within some $(1-\epsilon)$ of a circle for $\epsilon > 0$?
> 
> 
> 


Informally, will the runners eventually cluster?
Surely they will "cluster" within 99% of the track length?


---


(**Added** *23Jul14*). I see now that a version of this question is posed as an open 
problem by A. Dumitrescu and C.D. Toth in *SIGACT News* **45**(2) p.71 ([ACM link](http://www.sigact.org/SIGACT_News/)).



Not-lonely runners
I'll use Christian Remling's notation: We want to show that we can always find an empty interval of size $\epsilon\_n$ among any set of $n$ runners. 


The Masked Avenger gives an argument for $\epsilon\_n =1/n$, and suggests that $\epsilon\_n=2/n$ may be close to optimal by an argument I can't follow.


Assuming the lonely runner conjecture for $n+1$, we get an argument for $\epsilon\_n =2/n+1$ - just add one more runner, randomly placed, and wait until they're lonely.


In terms of actually provable statements, I was only able to get a very slight improvement - $\epsilon\_n = 1/n + c/n^{3/2}$ for some $c$. For this argument, we may assume without loss of generality that the speeds are integers. Consider each runner's position on the circle as a unit complex number function of time, and add them up. This gives a periodic function whose Fourier series $\hat{f}(n)$ is $0$ if $n$ is not the speed of the runner and, if $n$ is the speed of a runner, the starting position of that runner. So $\hat{f}(n)$ has $L\_2$ norm $\sqrt{n}$, and $f(t)$ has $L\_2$ norm $\sqrt{n}$. This means at some time it must take a value at least $\sqrt{n}$. We can easily see that if all the gaps are at most $1/n+\delta$, each runner can be no further than $n/\delta$ from a perfectly even position, meaning summing over the runners gives $\sqrt{n}\geq n^2/\delta$, with some constant thrown in there, which gives our result.


On the other hand we get $\epsilon\_n < 2/\sqrt{\log n}$ from Christian Remling's argument. So we have an exponential gap to close.


EDIT: I might be able to improve Christian Remling's argument by the probabilistic method. Let the runners have speeds $1$ through $n$, with random start times. We need to rule out the gaps of size $\epsilon$ starting at the point $x$ and the time $y$ for $x,y$ in the unit square. Cover the unit square in $a \times b$ bricks. What is the probability of the runner of speed $i$ ruling out a whole brick? To rule it out at a given time they need to be in an area of size $\epsilon-a$, which they are in for a time of $(\epsilon-a)/i$ on $i$ different occasions in the unit interval. Each of these occasions has a probability of $(\epsilon-a)/i-b$ of filling the whole brick, for a probability of $\epsilon-a-bi \geq \epsilon-a-bn$. Let $p=\epsilon-a-bn$. Then each runner has probability of $p$ of covering the whole brick, so each brick has a probability of $(1-p)^n$ of going uncovered. To have a positive probability of all bricks covered, we need:


$$(1-p)^n a^{-1} b^{-1} <1$$


$$ n (\log ( 1-p) ) < \log a + \log b$$


$\log(1-p)$ is about $- p$ so we have


$$ p< \frac {- \log a - \log b}{ n} $$


$$ \epsilon -a - nb < \frac{ - \log a - \log b }{n} $$


Putting $a=1/n$, $b=1/n^2$ we get $\epsilon\_n < 3 \log n/n+ 2/n = (3 + o(1) )\log n/n$.


This gives only a logarithmic distance between upper and lower bounds.


