back
28 comments
I like very much this conjecture: easy to grasp, with some intuition you can understand why it is plausible to hold. No general method has been discovered to settle the matter, only proofs for specific cases (up to 7 runners apparently).
Weaker versions have been proven, even for higher dimensions.
This reminds me of an interesting puzzle about horsemen riding around a circular track: https://blog.tanyakhovanova.com/2011/03/the-horsemen-sequenc...
Is it just me? I really hate how the problem is phrased on that page. Here's the original:

"33 horsemen are riding in the same direction along a circular road. Their speeds are constant and pairwise distinct. There is a single point on the road where the horsemen can pass one another. Can they ride in this fashion for an arbitrarily long time?"

Here's a quick take on how I would rephrase it:

"33 horsemen are riding in the same direction along a circular road. There is just a single point on the road where any number of horsemen can pass each another; everywhere else, a faster rider coming up behind a slower rider will be stuck and have to slow down. Is there a set of pairwise distinct speeds the horsemen can ride at such that the riders can all start at the passing point, ride constantly at their given speed for an arbitrarily long time, and only meet each other at the passing point (thus never having to change speed)?"

Isn't it true that if the runners' speeds are all real numbers which are not rational multiples of each other, eventually you'll see every distribution of positions of the runners, or at least come arbitrarily close?
The challenge isn't to find sets of numbers that guarantee loneliness will occur- as you say, arbitrary reals that aren't rational multiples should accomplish that handily. The conjecture isn't that such sets can be found - it's much stronger: that if the runners have any set of distinct speeds, then they all experience loneliness.

And, according to the article, and perhaps surprisingly:

> The conjecture can be reduced to restricting the runners' speeds to positive integers: If the conjecture is true for n runners with integer speeds, it is true for n numbers (sic) with real speeds.

i.e., the conjecture is that n runners with speeds which are all rational multiples of one another will experience loneliness.

> > The conjecture can be reduced to restricting the runners' speeds to positive integers: If the conjecture is true for n runners with integer speeds, it is true for n numbers (sic) with real speeds.

No need for sic when quoting Wikipedia; you can (and I have) just fix it!

Yeah sure I understand that. Just wanted to verify that at the offset we can elimate an uncountable number of possibilities and so for each n there are only a countable number of cases that need to be considered.
Read on in the article. Someone even reduced it further, so you only need to check a finite number of cases for each fixed n.
The conjecture is stronger: real != rational

> This convention is used for the rest of this article. Wills' conjecture was part of his work in Diophantine approximation, the study of how closely fractions can approximate irrational numbers.

I couldn't have imagined that we might make a connection between integers and irrational/real numbers.

I believe that if the runners speeds are all real numbers which are linearly independent over the rationals, then the associated dynamical system will be ergodic

https://en.wikipedia.org/wiki/Ergodicity

and what you say is true.

But in addition to your example you have to worry about, e.g. sqrt(2), sqrt(3), and sqrt(2) + sqrt(3).

I agree that it's probably ergodic, but to show every distribution will definitely come about (approximately) you'll need a slightly stronger property than just ergodicity. Ergodicity guarantees it is almost always the case, but if you want it to always be the case you'll need it to be uniquely ergodic.

Since irrational rotations are uniquely ergodic I reckon this system will also be, but I think the proof won't be trivial.

That seems true, by induction on the number of runners. But the conjecture does allow for rational speed ratios.
Is the lonely runner a proxy for the overloaded server in a load balancer using consistent hashing?

Or are the pictures just similar?

The pictures are just similar.

You don't have any smooth movement in consistent hashing. And you can pick your inputs carefully, instead of worrying about the worst case like in the linked conjecture.

Btw, you might like https://en.wikipedia.org/wiki/Rendezvous_hashing

Seems like it might have some relationship to the distribution of primes.
Reading:

> n runners on a track of unit length, with constant speeds all distinct from one another, will each be lonely at some time—at least 1/n units away from all others.

Interesting conjecture! And okay, a lot of interesting problems end up being distilled into tangible if eccentrically named things. Like the "dining philosophers" in computer science to describe deadlock. I'm curious how this relates to a tangible problem.

> Implications

Nice, here we go!

> Suppose C is a n-hypercube of side length s in n-dimensional space.

:|

A hypercube is just the higher-dimensional analog of a cube. A 2-hypercube is a square, a 3-hypercube is a cube, and so on.

Edit: I know complaining about downvotes is against the rules, and I’m not complaining, because I really don’t care about my karma on this site — but I am really confused and curious how people could possibly be opposed to me explaining a mathematical concept to someone who expressed frustration at not knowing it.

chias knows what a hypercube is. Their complaint is it isn't the tangible/practical implication they were hoping for.
I didn't know what a hypercube was, I found the explanation helpful.
Mathematicians are generally interested in the implications to other bits of math.
Exactly why I had to leave the field.
It's like that in most fields though. A builder is interesting in applications to buildings. An economist is interested in applications to the economy. Few people see things all the way through, whatever that even means.
n-hypercubes are very relevant and tangible. they model the state of your computer, for one.
Please explain? Or link?
A vertex in the N-dimensional hypercube represents an N-bit number.

An edge in the hypercube is equivalent to a single bit flip.

image: https://en.wikipedia.org/wiki/Snake-in-the-box#/media/File:S...

The deterministic state of a computation block (aka, a computer) is 2^N where N is the total number of state-retaining elements plus inputs. Large portions of this space are inaccessible due to mutex conditions (e.g., two or more conditions that cannot be true at the same time).

How does an open curve on the edge of an N-dimensional hypercube (snake in the box, as you provided) describe the state of my computer? Your link said nothing about that.

Apologies, the link was intended to go to the image of the hypercube + binary representation (which is much more intuitive than the images Wikipedia displays on the hypercube page), but it failed on mobile: https://upload.wikimedia.org/wikipedia/commons/2/2c/Snake_in...

The Gray Code image is a lot more 'practical' from an engineering perspective, but I don't feel it's of the same quality: https://upload.wikimedia.org/wikipedia/commons/c/c2/Gray_cod...