The Lonely Runner Conjecture
Another elusive open problem
Jörg Wills is a mathematician who has done many interesting things in geometry and related areas. But he is probably best known for a paper he wrote in 1967, “Zwei Sätze über inhomogene diophantische Approximation von Irrationalzahlen.” In this he created a conjecture, that was later independently discovered by Thomas Cusick, and finally named by Luis Goddyn as the lonely runner conjecture.
Today I (Dick) want to talk about this elusive conjecture that is another disease along with graph or group isomorphism and all the others and others.
So beware: read on only if you are prepared to spent hours thinking about a problem that is simple to state, has been open for forty-five years, and has resisted the efforts of some of the top researchers in the world. You have been warned.
The Problem
Actually unlike some of the other diseases the lonely runner conjecture (LRC) is really an important question in Diophantine approximation theory. Unlike many diseases it has nontrivial consequences and is related to important open questions in, for example, graph theory.
However, the best way to state the LRC is probably with the beautiful language of runners on a circular track rather than fractional parts of numbers. There are 
The question is, will there be a time when no runner will be near the start? More precisely, when each runner will be distance at least 
The reason this is called the “lonely runner conjecture” is that we can imagine that there really are 
Results
There are two types of partial results that are known. There are results that show that the problem holds for small values of 
The proofs of the conjecture even for small values of
In order to give a bit of the flavor of the complex case analysis used, here is a diagram from the paper by Tom Bohman, Dan Kleitman, and Ron Holzman that proved the case 
An Approach?
I must admit to have fallen a bit for this disease, but I cannot imagine trying to solve 
The idea is simple: apply the probabilistic method to the problem. Let’s start with a simple lemma:
Lemma 1 For any collection of
runners with non-zero paces that need not be distinct, and any interval
that includes the starting point, there is at least one time so that at most
runners are in the interval
Here 
Corollary 2 For any
of the starting point.
Proof: The corollary follows by letting 
![{[-\frac{1}{n+1},+\frac{1}{n+1}]}](https://s0.wp.com/latex.php?latex=%7B%5B-%5Cfrac%7B1%7D%7Bn%2B1%7D%2C%2B%5Cfrac%7B1%7D%7Bn%2B1%7D%5D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
runners are in 
Another corollary is this:
Corollary 3 For any
. Then there is at least one time so that at most one runner
is within
of the starting point.
Note that the interval is slightly smaller than before: the denominator has changed from 
Proof: The proof of the lemma is a simple probabilistic method argument. I cannot find a reference for it, but it must be well-known. In any case let’s go over the proof for completeness.
Define 
![\displaystyle E[X_{i}] = |I|,](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++E%5BX_%7Bi%7D%5D+%3D+%7CI%7C%2C+&bg=ffffff&fg=000000&s=0&c=20201002)
for all 
Now consider the summation
This is the number of runners that are in the interval 
Building the Argument
Of course, having
If it is not the case that two other runners were in the interval while he was, then I really was lonely at one of those times. One of those two must have been in the interval while he entered, exiting while he was still in the middle, and the other must have entered before he left. Since the probabilistic argument not only shows there exists a time but gives a set of times with positive measure, we can isolate a block of time when the runner was alone.
Can we apply probabilistic arguments in a compound manner to find times when there are not three runners in this kind proximity? Alas this may still require breaking into cases according to their speed relative to the single runner. One idea Ken and I have explored is cases where some slower runners can be paired with ones moving at (or about?) twice the speed, and using this form of the union bound:
![\displaystyle \mathsf{Prob}[E_{1} \vee \cdots \vee E_{n}] \leq \mathsf{Prob}[E_{1} \vee E_{2}] + \cdots + \mathsf{Prob}[E_{n-1} \vee E_{n}].](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathsf%7BProb%7D%5BE_%7B1%7D+%5Cvee+%5Ccdots+%5Cvee+E_%7Bn%7D%5D+%5Cleq+%5Cmathsf%7BProb%7D%5BE_%7B1%7D+%5Cvee+E_%7B2%7D%5D+%2B+%5Ccdots+%2B+%5Cmathsf%7BProb%7D%5BE_%7Bn-1%7D+%5Cvee+E_%7Bn%7D%5D.+&bg=ffffff&fg=000000&s=0&c=20201002)
We think this shows loneliness in an interval of width 
Open Problems
My suggestion is to move on and forget this problem. Yet it seems like the probabilistic idea might be improved just a bit to get the existence of a time when no runners are near the start. Can we use more clever probabilistic ideas? What about higher moments? or using the Local Lemma, or…?
Wait—I see an idea…
Huh. Sounds a bit like this (http://jaguilar.posterous.com/got-a-math-problem-for-ya). Not the same of course, and maybe this thing I was wondering about is already solved, but it reminded me of it.
Of course strictly speaking “random time” is not defined, but uniformly picking from a long interval the expected values are close to I. Let me add that this also belongs to my favorite conjectures, mainly because of the name that (I am sure) originates from here and deserves to be mentioned:
http://en.wikipedia.org/wiki/The_Loneliness_of_the_Long_Distance_Runner
iitdelhireport,
Yes we to be careful. If the paces are integers then it comes from a finite interval and is exact. This follows since the positions are then periodic. If there are arbitrary times, then yes pick long interval and get approximation.
I am probably wrong, but is this the opposite of a monster(/rogue) wave?
“Actually unlike some of the other diseases the lonely runner conjecture” WAT
“Unlike many diseases it has nontrivial consequences” WAT
Crank.
I just looked at the case where you have n runners running at speeds 1,2, … n for n=2,3,5. In all three of those cases, the set of times during which no runners are within 1/(n+1) of the starting line is a set of measure 0. Maybe I’ve misunderstood something about the problem, but if this phenomenon generalizes, then I would expect that your probabilistic approach would likely not work. (although perhaps the sets of relative weights where this is a problem are themselves rare.)
For what it’s worth, it does generalize, as it’s mentioned in the Six lonely runners paper that this case for general n has sharp bounds.
Thanks for the info Ørjan!
In a recent paper with a coauthor (http://arxiv.org/abs/1110.0080 ) we considered a topological/discrete variant of the lonely runner conjecture, which we called the “Interval Game”. The data for the game consists of a finite collection of orientation-preserving homeomorphisms of the circle f_1, f_2, . . . f_m (the “enemies”) and g. An interval J in the circle *wins* the game if there is some positive integer n so that g^i(J) is disjoint from f_j(J) for all j and all 0\le i \le n, and if g^n(J^+) is in J, where J^+ denotes the rightmost point of J.
One might think the nonlinearity of the game (the fact that the f_i are homeomorphisms, and not rigid rotations) might make the game hard to win, but actually the “hardest” games are when all the f_i, g are rigid rotations. For example, in the case of a single enemy f_1=f, if the rotation number of g is irrational, and g preserves a probability measure mu, then if f does not preserve mu, there is a winning interval. So the “hardest case” is a pair of commuting rotations, in which case the subset of the unit square (of pair of rotation numbers) with no winning interval is a nowhere dense attractor of an interesting IFS.
Anyway, thanks for blogging about this interesting conjecture.
I have a question about the statement of the conjecture (actually a few). It seems possible that there are some combinations of speeds that will yield a lonely runner and some that won’t. For example, if all the speeds are really fast, just wait until the fastest one has completed half a turn and you can make the minimum distance from the start arbitrarily close to 1/2. Is the conjecture that all possible combinations of speeds will yield a lonely runner?
All possible combinations of distinct speeds, yes. Apparently it’s a known theorem that it’s enough to consider integer (or equivalently, rational) speeds.
Thanks!
Are there results on a weaker case where we change the distance 1/(n+1) to some smaller number? For example, is anything proven for 1/(2*(n+1))? I would guess that some randomized arguments might succeed in proving such weaker results.
Here is my 5 cents.
https://mkatkov.wordpress.com/2014/08/06/lonely-runner-conjecture-general-case/
Is there a simple proof for n=2?
“Every Runner is Sometimes Lonely”
Matthias Beck
http://arxiv.org/abs/1606.01783
[v2] “Comments: The paper has been withdrawn due to a mistake in the last line of the proof–it does not hold for n=0. Thanks to Terry Tao for pointing out this crucial gap.”
Farbod, thanks for letting us know! (And move your Knights less than you want to…:)
Haha! very interesting note, appreciation!