Skip to content

Lonely Runner Conjecture—An Attack

February 4, 2012
tags: , , ,


A small idea on this conjecture

John Wheeler was one of the great physicists of the last century. One of his many famous quotes is:

No phenomenon is a real phenomenon until it is an observed phenomenon.

Let’s keep this in mind when we discuss quantum and anything else. Another relevant quote is from the eminent Freeman Dyson, who said:

It is characteristic of all deep human problems that they are not to be approached without some humor and some bewilderment.

Today I would like to turn from recent deep discussions of matrix product, quantum machines, time travel as in Groundhog Day, and look again at the lonely runner conjecture.

When I was in college I was very interested in track and field—I still follow it. Interested as a spectator, since my skills were non-existent. I did help at college track meets, setting up hurdles, moving equipment around, and generally being part of the team support system. I also had friends at other schools, ones that were very serious about track unlike where I went, and they could run sub-four-minute miles.

More Laps, Moral Lapse?

Helping the track team raised a moral dilemma years ago for me. Our school was in Division {\aleph_{0}}, that is, we were not competing against any teams had ever even seen Division III teams. One indication of this is that our outdoor track was oval—pretty standard—but was only a fifth of a mile around—not the standard quarter of a mile. Just to be clear: a mile race was now five laps not the almost universal four. A small difference, just {O(1)}, but a large difference when you are running a competitive mile race.

At one track meet I overheard two runners from another team discussing their race strategy:

One said: I am really going to kick hard on lap three, so I can win on the last lap. The other nodded that he would so the same.

Now this is a good strategy at most places, but might be a bit off at our track, since as they finished the “fourth and last lap” they still would have {1,056} feet to go.

My dilemma was, should I tell them that our track was a fifth of a mile, or should I keep silent and let them mess up? I was thinking about what to do and was about to say something to them when their coach came by and said: “remember it’s five laps, five.” Oh well.

I am still in awe of those who excel in this difficult sport. Perhaps that is why I decided to think about the famous lonely runner conjecture (LRC)—perhaps. It is another math disease so I am trying to be careful about what I do, so I will not be pulled in and spend all my resources on it.

Let’s take a look at the modest ideas that I have on this problem.

The Problem

I will for completeness re-state the problem, but recall I just talked about it here.

The best way to state the LRC is 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? This is open for {n\geq 7}, and not much is known about the general problem.

Special Cases

I have the disease, my doctor recommends drinking lots of fluids and getting ample rest, but I must share an idea. One of George Pólya’s principles in problem solving is to try and pick a version of your problem that seems to have all the main issues—yet is approachable. Here is my suggestion: Consider runners that run at the paces {1,2,\dots,n}. Then attempt to prove there is a time that none are with {\frac{c}{n+1}} of the start, where {c>0} is a constant. Of course the LRC states that {c=2} is possible, so our goal is to try to get a value of {c} that is close to {2} as possible.

Note that it is not hard to show, as pointed out in our first item’s comments beginning here, that this case is tight in that {c=2} is the best possible bound. I have no idea how to prove {c=2}, but I believe that we can prove that {c>1} is true and would like to outline the idea of how to prove this.

The proof is based on picking a random time {t} in the interval {[0,1]} and showing that with positive probability there will be no runners in the interval {I = [-\alpha,+\alpha]} for some {\alpha}. Note that the system is periodic according to when the slowest runner completes a lap, so it suffices to consider only {t}‘s in {[0,1]}. Our hope is that {\alpha} will be large enough so that {2\alpha} will yield a reasonable bound on the constant {c}.

The idea is to look at the events {E_{k}} defined as: the {k^{th}} runner is in the interval {I} that we wish to avoid. Thus, we need to get a good bound on

\displaystyle \mathsf{Prob}[E_{1} \vee \cdots \vee E_{n}],

and show that it is less than {1}. This will imply that there exists a time when no runner is in {I}. It is not hard to show that

\displaystyle \mathsf{Prob}[E_{k}] = 2\alpha.

Then by the union bound it follows that we need {2n\alpha < 1}, which implies that {I} is of length at most {1/n}. This is trivial and yields only {c=1}.

Beating The Union Bound

The problem is that the union bound is too weak. The events {\{E_{k}\}} are not very rare, so much information is lost in using the union bound. Let’s switch the runners speeds: for now let us assume that the speeds are {s_{1},\dots,s_{n}} again natural numbers. But we will assume that the speeds of runner {s_{i}} and {s_{i+1}} (for odd {i}) are in the ratio {1:2}. This requires {n} to be even, but that is fine for now. For example, the speeds could be:

\displaystyle 1,2,3,6,4,8,5,10.

We will now bound

\displaystyle \mathsf{Prob}[E_{1} \vee \cdots \vee E_{n}]

by

\displaystyle \mathsf{Prob}[E_{1} \vee E_{2}] + \cdots + \mathsf{Prob}[E_{n-1} \vee E_{n}].

And we will claim that for each pair,

\displaystyle \mathsf{Prob}[E_{k} \vee E_{k+1}] = 3\alpha.

Assume the claim for a moment. Then arguing as before we get that {\frac{n}{2}3\alpha < 1} is required, which shows that {I} is equal to {\frac{1.33}{n}}.

This is good and shows that for any set of paired runners the bound is not {c=2} but is {c=1.33}. Progress. Not a lot, but some progress.

Proving The Claim

By re-scaling we can assume the two runners move at speeds {1} and {2}. Call them “slow” and “fast”. We need to calculate the amount of time in {[0,1]} that both are in the {2\alpha} size interval {I} centered at the start, when one is in the interval {I}, and when none is. This is an inclusion-exclusion argument, albeit a very simple one. The fast and slow runner are each individually in the interval for {2\alpha} of the time, and share the interval for {\frac{\alpha}{2}} of the time at the start and again at the end. So the total time for either or both to occupy it is {4\alpha - \frac{\alpha}{2} - \frac{\alpha}{2} = 3\alpha}.

Open Problems

Can we do better than this bound? What does it imply for the original set of runners {1,2,\dots,n}? An easy application of the pairing idea to this set of speeds yields a {c>1}, but I am still checking what the best bound is. The idea is to pair as many runners as possible and use the pairing to get a better union bound. Any help is welcome.

Also, I like this partial union bound trick—it is very simple but yields a nice payoff. Are there any other applications that you can think of for this trick?

[fixed confusion in LRC statement between distance 1/(n+1) from start and gap of 2/(n+1) there overall]

from → People, Proofs
11 Comments leave one →
  1. Gilbert Bernstein permalink
    February 4, 2012 6:44 pm

    I may be misreading something here, but I think you might have gotten the distance from the starting line (1/(n+1)) and the size of the interval around the starting line (2/(n+1)) confused in the writing above.

    Reply
  2. Gilbert Bernstein permalink
    February 4, 2012 7:34 pm

    btw, in the case of n=2, your argument above gives the tight bound. It establishes that the length of I is 4/(3n), which is 4/6=2/(n+1) (for n=2), which is tight. As n increases, the bound gets looser, but never worse than c=1.33, as you pointed out.

    Reply
  3. mkatkov permalink
    February 5, 2012 8:48 am

    My apologies, I’m also confused by \frac{2}{n+1} it does not make sense for n=1, therefore I’ll assume you meant distance \frac{1}{n+1} from both sides of origin. The case of n runners with speed 1 .. n seems to be easy. Consider time (t= \frac{n-1}{n}+ \frac{1}{n(n+1)}) when the fastest runner (n) is on its last lap at the distance \frac{1}{n+1} from the origin. Than the slowest runner is at distance \frac{n}{n+1} or -\frac{1}{n+1} from the origin. The rest are between them. Therefore, at the time t all runners are at least \frac{1}{n+1} from the origin.

    Reply
  4. from permalink
    February 5, 2012 7:58 pm

    Can’t believe Terry Tao did not prove this already!!

    Reply
  5. mkatkov permalink
    February 6, 2012 7:55 am

    just an observation – if there are n+1 runners with integer speeds v_k for simplicity we can re-scale speeds that least common divisor of all v_k is 1 (there is at least one runner with odd speed), then at time \frac{1}{n+1} every runner will have position \frac{l_k}{n+1} plus different number of laps. Then either there is a lonely runner (like in the case of runners with speeds 1..n, where all of them are lonely), or all of them are at least paired.

    Reply
  6. Alex permalink
    February 9, 2012 12:49 pm

    This has been my morning coffee problem for the last week. FWIW, I came up with a function N(t) that gives the number of runners in the starting interval at any time, given speeds v_1,…,v_n. The function is a big Fourier series looking thing so it is hard to tell if it is ever zero. But I was able to determine that the average number of runners in the starting interval is 2n/(n+1), independent of the values of the speeds.

    Reply

Trackbacks

  1. 507- Problem list (IV) « Teaching blog
  2. Lonely Runner Conjecture—A Second Attack « Gödel’s Lost Letter and P=NP
  3. Fourteenth Linkfest
  4. 507- Problem list (IV) « A kind of library
  5. Open Problems That Might Be Easy | Gödel's Lost Letter and P=NP

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading