5 ms·

The lonely runner conjecture

141 points by xk3 4y ago

squaredot 4y ago
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).
- eru 4y ago
  Weaker versions have been proven, even for higher dimensions.
gweinberg 4y ago
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?
- tromp 4y ago
  That seems true, by induction on the number of runners. But the conjecture does allow for rational speed ratios.
  - deleted 4y ago
    [deleted]
- jameshart 4y ago
  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.
  - gweinberg 4y ago
    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.
    - eru 4y ago
      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.
  - karmakaze 4y ago
    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.
  - JadeNB 4y ago
    > > 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!
- impendia 4y ago
  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 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).
  - contravariant 4y ago
    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.
tromp 4y ago
This reminds me of an interesting puzzle about horsemen riding around a circular track: https://blog.tanyakhovanova.com/2011/03/the-horsemen-sequences/ https://blog.tanyakhovanova.com/2011/03/the-horsemen-sequenc...
- gcanyon 4y ago
  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)?"
deleted 4y ago
[deleted]
sanj 4y ago
Is the lonely runner a proxy for the overloaded server in a load balancer using consistent hashing? Or are the pictures just similar?
- eru 4y ago
  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 https://en.wikipedia.org/wiki/Rendezvous_hashing
chias 4y ago
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. :|
- ouid 4y ago
  n-hypercubes are very relevant and tangible. they model the state of your computer, for one.
  - sbf501 4y ago
    Please explain? Or link?
    - david_allison 4y ago
      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:Snake_in_the_box.svg https://en.wikipedia.org/wiki/Snake-in-the-box#/media/File:S...
      - sbf501 4y ago
        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.
        4y ago
euroderf 4y ago
Seems like it might have some relationship to the distribution of primes.

141 points by xk3 4y ago

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).

eru 4y ago
Weaker versions have been proven, even for higher dimensions.

gweinberg 4y ago

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?

tromp 4y ago
That seems true, by induction on the number of runners. But the conjecture does allow for rational speed ratios.
- deleted 4y ago
  [deleted]
jameshart 4y ago
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.
- gweinberg 4y ago
  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.
  - eru 4y ago
    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.
- karmakaze 4y ago
  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.
- JadeNB 4y ago
  > > 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!
impendia 4y ago
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 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).
- contravariant 4y ago
  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.

tromp 4y ago

This reminds me of an interesting puzzle about horsemen riding around a circular track: https://blog.tanyakhovanova.com/2011/03/the-horsemen-sequences/ https://blog.tanyakhovanova.com/2011/03/the-horsemen-sequenc...

gcanyon 4y ago
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)?"

deleted 4y ago

[deleted]

sanj 4y ago

Is the lonely runner a proxy for the overloaded server in a load balancer using consistent hashing? Or are the pictures just similar?

eru 4y ago
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 https://en.wikipedia.org/wiki/Rendezvous_hashing

chias 4y ago

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. :|

ouid 4y ago
n-hypercubes are very relevant and tangible. they model the state of your computer, for one.
- sbf501 4y ago
  Please explain? Or link?
  - david_allison 4y ago
    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:Snake_in_the_box.svg https://en.wikipedia.org/wiki/Snake-in-the-box#/media/File:S...
    - sbf501 4y ago
      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.
      - 4y ago

euroderf 4y ago

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