Not-lonely runners

Question

The 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).

Answer 1

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.

Answer 2

This is more a comment than an answer, but it's getting a bit too long.

We will not be able to do this with a universal (= $n$ independent) $\epsilon>0$: Given any $\epsilon>0$, we can assign speeds and initial positions to (sufficiently many) runners so that they will never be in a common $(1-\epsilon)$ circle.

We can just assign the speed $j$ to runner $j$. Then we'd have to find a time $t\in [0,1]$ (my circle has length $1$) by periodicity. However, for any given $(1-\delta)$ circle, runner $1$ contributes an interval of length $\delta$ of forbidden times. Then runner $2$ contributes a union of two intervals of length $\delta/2$ each that have to be avoided, and by adjusting the initial position of runner 2, we can move one of these to where the first runner's interval ended. Continuing in this way, we can cover all of $[0,1]$ with finitely many runners since $\sum (1/j)=\infty$. (In fact, I have a lot of overlap.)

So far, we've only avoided one fixed $(1-\delta)$ circle, but any $(1-\epsilon)$ circle contains one of finitely many suitably chosen $(1-\epsilon/2)$ circles, so by adding runners in the way described, we can be sure that they will never cluster in a $(1-\epsilon)$ circle.

So the real question is: what can we say about $\epsilon=\epsilon_n$?

Update: Will in his answer has given a considerably more careful quantitative version of this argument, which shows that $\epsilon_n\lesssim \ln n/n$. Together with the trivial bound $\epsilon_n\ge 1/n$, this seems to settle the original question (unless we want a very precise answer).

Answer 3

Thinking about the negative side, you can't guarantee arbitrarily many runners to reside in a common $1/2-\epsilon$ of the circle for any $\epsilon>0$.

Take $N$ to be a sufficiently large polynomial of $n$, and let $F$ denote the first $n$ columns of the $N\times N$ discrete Fourier transform matrix with unit-modulus entries. Next, let $D$ be an $n\times n$ diagonal matrix whose diagonal entries are drawn iid uniformly from the complex unit circle. Interpret each row of the matrix product $FD$ to be the locations of the runners at time $t\equiv 0,\ldots,N-1 \bmod N$. (We took $N$ much larger than $n$ in order to sample the running paths so much that we wouldn't "miss" a cluster.)

Using a complex version of Hoeffding's inequality, there is a positive probability that for every $t$, the sum of the runners' locations (as complex numbers) has modulus smaller than

$$\sqrt{4n\log 4N}=O(\sqrt{n\log n})=o(n),$$

whereas the modulus would need to be $\Omega_\epsilon(n)$ if the runners resided in a common $1/2-\epsilon$ of the circle.