The lonely runner conjecture for a discrete or uncertain universe

The lonely runner conjecture has been around since the 1960s. It imagines $n$ runners on a circular track of unit circumference, all starting at the same point (considered to be 0), and each running at some constant speed $v_i \in \mathbb{R}$. A runner is said to be "lonely" at some time $t$ if it is a distance of at least 1/n from all the other runners. The conjecture states that, for any set of runner speeds, any of the runners will eventually be lonely at some future finite time.

We can start by simplifying the problem a little:

• Firstly, picking some runner that we want to show will eventually be lonely, let's subtract that runner's speed from all runners. This means that runner will now be stationary at 0. Now we can imagine there are only n-1 runners and try to show that at some future time, all runners are at least 1/n away from 0.
• Secondly, if any runner has a negative speed, we can replace it with the same positive speed. This is because regardless of which direction a runner goes around the circle, its distance from 0 is always the same.

Without loss of generality, let's imagine the case of three runners just so we can visualise the configuration space. Since one runner is fixed at 0, the space of configurations is the torus $T^2 = S^1 \times S^1$. The loneliness set is a connected "rectangle" on the torus.

Why would we expect the conjecture to be true? I think we expect that the simulation will evolve in a highly random way, such that any possible configuration of the runners should eventually arise by chance. Therefore, it seems reasonable to propose that a trajectory should always intersect the loneliness set if we wait long enough. Unfortunately, this intuition isn't entirely correct. Patterns in rational numbers mean that some trajectories are periodic and never achieve all possible configurations. As we'll see though, this heuristic "randomness" argument does work for irrational speeds, however, and speeds whose ratios are irrational numbers.

As we'll demonstrate shortly, the problem actually splits into two cases, based on the properties of the set of speeds chosen:

1. If all ratios of runner speeds $v_i/v_j$ are rational numbers (which is in particular true when the speeds themselves are rational), the trajectory of the runners is periodic. Furthermore, we can convert the problem into an equivalent one where all speeds are integers.
2. In all other cases, the solution is not periodic, and in fact is dense in the space of runner configurations. This means that the trajectory must intersect any set containing an open ball, in particular it must intersect the loneliness set. This means that we only need to worry about proving case 1.

Terry Tao had a look at the conjecture, and managed to find an upper bound on the size of the integer speeds that need to be considered for case 1. This reduces the problem to a finite (though huge) number of speed sets that need to be checked, which has allowed the conjecture to be proven up to 10 runners using computers. Of course, the number of cases to be checked is only finite for a fixed number of runners - we will not be able to show the conjecture for any number of runners using this approach. Since Terry Tao is familiar with a huge number of techniques in number theory, and only got so far as a bound, it probably means there isn't an obvious way to prove the conjecture using known methods.

Now we explain why we need only consider integer speeds for case 1.  If the speeds are all rational numbers, or at least all the ratios $v_i/v_j$ of the speeds are rational numbers, then we can find a common denominator $q$ for all of those rational numbers. We may multiply all speeds by $q$ without changing the problem (we are just changing how fast the simulation plays out, or scaling time). And this results in all speeds being integers.

What about the case where the speeds are not rational and their ratios are not rational? This case corresponds to our initial intuition that the trajectory should be random enough to eventually fill the space of all possibilities. 

While seeming intuitively plausible that irrational numbers lack the structure to prevent the trajectory from filling the whole space, the formal argument is based on the theory of subgroups of the torus, and I will add it here when I find time.

This also means that the conjecture holds for "almost all" sets of speeds, since irrational numbers are dense in the reals.

So we know that the conjecture holds for the "irrational" case, and the remaining "rational" cases are periodic. So the conjecture is claiming that, even though the periodic trajectories do not fill the space, perhaps they still wrap around "sufficiently tightly" as to always cross the loneliness set. Or that there is some other reason why they always cross that one particular set.

In mathematics, we often search for a "reason" why a theorem should hold for all cases. But in number theory, the natural numbers sometimes appear to be a "discrete" or "statistical" approximation of a more perfect continuous phenomenon, particularly before the numbers become very large. In such a situation, there may be no way to prove some theorems outside of checking many cases one by one, and there may be no deeper meaning behind a theorem than that it "just happened" to hold for each case by chance, where it might not have done.

We've seen that the conjecture holds for irrational speeds and speeds which are related by irrational ratios, but it's much harder to prove (and still unresolved) whether the conjecture holds for rational and rationally-related speeds. This mathematical idealisation is all very well, but in the real world we can't set an object's speed to be an irrational or irrational number since that requires infinite precision. So to what extent would the conjecture hold in real world simulations?

It's interesting to note that, if we assume that the universe is discrete in terms of positions and speeds, in practice all lonely runner simulations would correspond to the rational, periodic case. But if the discrete units are sufficiently small, the period might be so large that the orbit behaves more like the irrational, dense case.

Next we could consider the uncertainty principle, where both the position and the speed of the runners are probability distributions. Small uncertainty in speed accumulates over time. So after enough time, phase uncertainty smears the trajectory around the torus. That makes the system behave like the irrational, dense case.

Finally, even without discrete spacetime or quantum uncertainty, the concept of objects moving at constant speeds of unlimited accuracy is not achievable in the real world. If we assume that the speeds fluctuate slightly about any real initial values, according perhaps to a tight normal distribution, it's easy to see that the trajectory will be dense again, and the lonely runner property will hold.