Skip to content

The Lonely Runner Conjecture

January 28, 2012


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 {n} runners going around a circular track of unit length, and they are very steady runners: they each have their own distinct paces. They all start together from the same starting spot and continue running at their own unique pace forever. Unlike real runners they never vary their speeds, they never get tired, and they never interfere with each other—even as faster runners pass slower runners.

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 {\frac{1}{n+1}} from the start?

The reason this is called the “lonely runner conjecture” is that we can imagine that there really are {n+1} runners, but one runner has pace zero—that’s me. So I stay at the start and become lonely when no one else is near me, either behind or in front. If you think I should try walking, just subtract my walking speed from everyone else’s and we’re back in the case where I stand still. If you get Patrick Makau to run instead, then subtracting his speed is the same as using me and having the others run in the opposite direction. Thus the originally stated conjecture that each of {n+1} runners gets “lonely” at some time is equivalent to {n} runners and just me being lonely.

Results

There are two types of partial results that are known. There are results that show that the problem holds for small values of {n}. The best of these is {n=6}, I believe. Again because I’m in every race, the paper’s title refers to seven “runners.” The other results treat the general case of {n} runners but restrict the speeds of the runners. For example, if the runners initially select random paces, then it is possible to prove very strong separation results. Other restrictions assume that the paces of the runners are sufficiently different, i.e. that the ratios of paces are relatively large.

The proofs of the conjecture even for small values of {n} can be quite intricate. If you like hard case-analysis proofs, then these are for you. Take a look. It is hard to imagine how difficult these proofs were to find, and how difficult they are to check for correctness—especially when computer searches are employed.

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 {n=5}:

An Approach?

I must admit to have fallen a bit for this disease, but I cannot imagine trying to solve {n=7} by even more complex case analysis. That is beyond what I can do. But it did occur to me that there might be a different approach to the problem. My approach does not work yet, and may never work. But it could yield some new insights.

The idea is simple: apply the probabilistic method to the problem. Let’s start with a simple lemma:

Lemma 1 For any collection of {n} runners with non-zero paces that need not be distinct, and any interval {I} that includes the starting point, there is at least one time so that at most

\displaystyle  \lfloor n|I| \rfloor

runners are in the interval {I}.

Here {|I|} is the length of the interval. Before we prove the lemma let me give two interesting statements that follow.

Corollary 2 For any {n} and any runners with distinct non-zero paces, there is at least one time so that at most one runner is within {\frac{1}{n+1}} of the starting point.

Proof: The corollary follows by letting {I} be the interval {[-\frac{1}{n+1},+\frac{1}{n+1}]}. The lemma shows there is a time so that

\displaystyle  \lfloor n \cdot \frac{2}{n+1} \rfloor

runners are in {I}. But this quantity is {1}. \Box

Another corollary is this:

Corollary 3 For any {n} and any runners, fix a runner {r}. Then there is at least one time so that at most one runner {r' \neq r} is within {\frac{1}{n+2}} of the starting point.

Note that the interval is slightly smaller than before: the denominator has changed from {n+1} to {n+2}. But now we can “control” slightly which runner is allowed to be near the start.

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 {X_{i}} to be the indicator random variable so that it is {1} when the {i^{th}} runner is in the interval {I} for a random time {t}. I claim that

\displaystyle  E[X_{i}] = |I|,

for all {i}. The claim follows by noting that as time {t} varies uniformly so does the runner’s position.

Now consider the summation

\displaystyle  S = \sum_{i=1}^{n} X_{i}.

This is the number of runners that are in the interval {I} at a random time {t}. But the expectation of {S} is {w = n|I|}. So there must be some time when {S \le \lfloor w \rfloor}, since {S} is an integer valued random variable. \Box

Building the Argument

Of course, having {1} runner near the start is not loneliness for me. But we can ask, what about the times when this runner enters, or leaves?

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}].

We think this shows loneliness in an interval of width {\frac{c}{n+1}} about the origin for {c = \frac{4}{3}} in case the speeds are in ratio {1:2:\cdots:n}. We don’t know which such special cases have been analyzed—we wonder if this is a good subject for a computer repository or PolyMath project.

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…

20 Comments leave one →
  1. January 29, 2012 4:12 am

    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.

  2. January 29, 2012 8:24 am

    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

    • rjlipton permalink*
      January 29, 2012 9:09 am

      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.

  3. January 29, 2012 9:53 am

    I am probably wrong, but is this the opposite of a monster(/rogue) wave?

  4. Dave Parker permalink
    January 29, 2012 11:49 am

    “Actually unlike some of the other diseases the lonely runner conjecture” WAT

    “Unlike many diseases it has nontrivial consequences” WAT

    Crank.

  5. January 29, 2012 10:36 pm

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

  6. January 30, 2012 10:36 am

    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.

  7. Alex permalink
    February 5, 2012 1:47 pm

    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?

    • Ørjan Johansen permalink
      February 5, 2012 4:19 pm

      All possible combinations of distinct speeds, yes. Apparently it’s a known theorem that it’s enough to consider integer (or equivalently, rational) speeds.

      • Alex permalink
        February 6, 2012 10:34 am

        Thanks!

  8. matt permalink
    February 11, 2012 10:27 am

    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.

  9. Poincare permalink
    May 15, 2015 12:12 am

    Is there a simple proof for n=2?

  10. Farbod permalink
    June 6, 2016 10:07 pm

    “Every Runner is Sometimes Lonely”
    Matthias Beck
    http://arxiv.org/abs/1606.01783

    • Farbod permalink
      June 7, 2016 7:49 pm

      [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.”

      • June 7, 2016 8:22 pm

        Farbod, thanks for letting us know! (And move your Knights less than you want to…:)

Trackbacks

  1. Lonely Runner Conjecture—An Attack « Gödel’s Lost Letter and P=NP
  2. Open Problems That Might Be Easy | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s