Lonely Runner Conjecture—An Attack
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 , 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 , 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 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.
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 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 from the start? This is open for , and not much is known about the general problem.
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 . Then attempt to prove there is a time that none are with of the start, where is a constant. Of course the LRC states that is possible, so our goal is to try to get a value of that is close to 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 is the best possible bound. I have no idea how to prove , but I believe that we can prove that is true and would like to outline the idea of how to prove this.
The proof is based on picking a random time in the interval and showing that with positive probability there will be no runners in the interval for some . Note that the system is periodic according to when the slowest runner completes a lap, so it suffices to consider only ‘s in . Our hope is that will be large enough so that will yield a reasonable bound on the constant .
The idea is to look at the events defined as: the runner is in the interval that we wish to avoid. Thus, we need to get a good bound on
and show that it is less than . This will imply that there exists a time when no runner is in . It is not hard to show that
Then by the union bound it follows that we need , which implies that is of length at most . This is trivial and yields only .
Beating The Union Bound
The problem is that the union bound is too weak. The events 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 again natural numbers. But we will assume that the speeds of runner and (for odd ) are in the ratio . This requires to be even, but that is fine for now. For example, the speeds could be:
We will now bound
And we will claim that for each pair,
Assume the claim for a moment. Then arguing as before we get that is required, which shows that is equal to .
This is good and shows that for any set of paired runners the bound is not but is . Progress. Not a lot, but some progress.
Proving The Claim
By re-scaling we can assume the two runners move at speeds and . Call them “slow” and “fast”. We need to calculate the amount of time in that both are in the size interval centered at the start, when one is in the interval , 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 of the time, and share the interval for of the time at the start and again at the end. So the total time for either or both to occupy it is .
Can we do better than this bound? What does it imply for the original set of runners ? An easy application of the pairing idea to this set of speeds yields a , 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]