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 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?

The reason this is called the “lonely runner conjecture” is that we can imagine that there really are 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 runners gets “lonely” at some time is equivalent to 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 . The best of these is , 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 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 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 :

An Approach?

I must admit to have fallen a bit for this disease, but I cannot imagine trying to solve 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 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 is the length of the interval. Before we prove the lemma let me give two interesting statements that follow.

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

Proof: The corollary follows by letting be the interval . The lemma shows there is a time so that

runners are in . But this quantity is .

Another corollary is this:

Corollary 3 For any and any runners, fix a runner . 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 to . 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 to be the indicator random variable so that it is when the runner is in the interval for a random time . I claim that

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

Now consider the summation

This is the number of runners that are in the interval at a random time . But the expectation of is . So there must be some time when , since is an integer valued random variable.

Building the Argument

Of course, having 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:

We think this shows loneliness in an interval of width about the origin for in case the speeds are in ratio . 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…