THE LONELY RUNNER CONJECTURE
Wishing Everyone A Joyful National Mathematics Day!
Introduction
You and your friend Bob are a notorious duo. As a punishment for your latest mischief, you have been asked to run laps around a circular track. You and Bob start running with constant but different velocities. For a while it is bearable as you guys can chat and crack jokes while running, but then there comes a time when Bob is halfway across the track from you and you are all alone. This happens several times during the laps and you begin to wonder if there is any way to circumvent since this issue. After the laps you bring this up to your friend. Bob thinks for a while and then remarks that this is a rather troublesome problem as even if you somehow convinced your entire friend group to take part in the punishment with you, that still might not solve the issue. Perplexed, you decide to get to the bottom of things.
The Problem
Consider n runners on a circular track of unit length. At the initial time t=0 all runners are at the same position and start to run; the runners' speeds are constant, all distinct, some of them may be running in opposite directions though. A runner is said to be lonely at time t if they are at a distance (measured along the circle) of at least 1/n from every other runner. THE LONELY RUNNER CONJECTURE states that each runner is lonely at some time, no matter the choice of speeds. Let us check the validity of the argument in this conjecture.
Note: All the runners do not necessarily have to be lonely simultaneously, it is enough if each of them is lonely at individual instances in time.
https://observablehq.com/@theredpea/lonely-runner
Do check out the above link for a visual simulation of the problem and try to play around with it a little bit, toggling the values of speeds to get an intuitive idea of what exactly is going around in the system.
Analysis
The fun thing about this problem is that, it is simple enough to be understood by almost everyone and yet one can keep peeling away its layers for a lifetime, discovering a bit of wonderful and intriguing math each time.
We can start to look at this problem through so many different Mathematical Lenses. It involves Geometry, Number Theory, Graph Theory, and a field called Diophantine Approximation.
For example, one might think that the analysis could become overly complex if the initial speeds include a mix of integers, fractions, and irrational numbers. This is where Diophantine Approximation theory simplifies things for us.
It turns out that we can focus solely on integer speeds, (this might be a good time to take a moment and try to convince yourself why this might be true) If all the speeds were rational numbers (i.e., fractions), we could choose an integer N (for example, the product of all the denominators) to multiply each speed by N, transforming the problem into one with integer speeds. However, to extend this reasoning to real numbers, we need an argument regarding how real numbers can be approximated by fractions, which is the essence of Diophantine Approximation.
https://en.wikipedia.org/wiki/Diophantine_approximation
Now with this out of the way, the next question might be how can we keep track of positions on a circular track. Now, luckily for us since it is a track with unit length and we are measuring distances along the length of the track, we can simply consider the fractional part of the actual distance covered by a runner to be their position. For example, if a runner runs at a speed 2, then after 2.4 seconds, they would cover a distance of 4.8 and their position on the track would be 0.8 from the start.
Note: We’re considering signed distances here with the convention that distance measured along the counterclockwise direction is positive and the distance measured along the clockwise direction is negative.
But in general, the tool used for such situations when integers are involved is modular arithmetic. https://www.geeksforgeeks.org/modular-arithmetic/
To compute the difference in position of two runners who have covered a distance of x1 and x2
d (x1, x2) :=min({|x1-x2|}, 1-{|x1-x2|})where {x} denotes the fractional part of x.
This captures both directions around the circle:
Calculate the direct difference and extract the fractional part: {∣x1−x2∣}.
Wrap around the track: Calculate: 1−{∣x1−x2∣}.
Take the minimum of the two to find the true difference in position.
The Final Point
I would like to mention that we can reframe the problem by treating one of the runners as stationary, focusing on the relative speeds rather than the actual speeds. For example, if one runner has a speed of 2 and another has a speed of 4, this is equivalent to having speeds of 0 and 2, respectively. By subtracting the speed of the i’th runner from all runners' speeds, the i’th runner can be considered stationary. So, the loneliness condition for the i’th runner can be reframed as saying that the other (n-1) runners, all moving at different speeds, will all simultaneously be at least 1/n distance away from the starting point at some point in time. This is due to the fact that if two scenarios have the same relative speeds, a particular runner will reach the point of loneliness at the same time in both situations. Essentially, when we subtract a constant value a from the speeds and compute the distances between two runners, we find that (v−a) t−(w−a) t=(v−w) t, meaning that the distances remain unchanged.
At this point in the article, many people might expect all the observations to neatly come together and form a brilliant solution. Something that lurks just out of reach, waiting for the right logical leaps to connect the dots. Unfortunately, as simple as this problem sounds, no general proof of the problem exists. The conjecture has only been proven for n < 8. In fact, the proofs of the cases which have been resolved are also way beyond the scope of this article. (Or shall we say, as authors often like to do in mathematics textbooks, ‘The proof has been left as an exercise for the reader’)
Also, if a proof is ever found, it would open up a whole new world where we can consider the same problem in higher dimensions. (Just take a moment to let that sink in. People running on the surface of spheres and hyperspheres…)
Conclusion
It might seem counterintuitive to invest time in studying a problem with no general proof. However, the true value of the Lonely Runner Conjecture lies not just in its eventual resolution but in the mathematics and practical tools it inspires along the way. Specific cases of the conjecture (example , for n<8) have already been proven and these results can be directly applied in real world scenarios. The conjecture’s insights find application in diverse domains from robotics and scheduling to astronomy and signal processing.
For instance, consider a scenario where multiple devices transmit data simultaneously. Each device’s signal is analogous to a runner on a circular track. Ensuring that a device’s signal becomes ‘lonely’ guarantees that it can be uniquely distinguished from others, allowing for clear data decoding.
Even if a full proof eludes us, the conjecture provides a universal language for understanding isolation in complex systems.