Lonely Runner Conjecture Question

[Unity+]

So, I saw the definition of the conjecture:

 

A runner is said to be lonely at time t if he is at a distance of at least 1/k from every other runner at time t. The lonely runner conjecture states that each runner is lonely at some time.

 

And then it asks "Can the Lonely runner conjecture be proved for k≥8?"

 

What confuses me about the statement is it seems it is asking if it can be proven for smaller distances. Why would that be difficult to prove? I thought it would be more trivial that way(not saying it's a simple problem). Would it not be harder to prove it for larger distances?

Edited June 11, 2015 by Unity+

[Spyman]

"Consider k runners on a circular track of unit length. At t = 0, all runners are at the same position and start to run; the runners' speeds are pairwise distinct. A runner is said to be lonely at time t if he is at a distance of at least 1/k from every other runner at time t. The lonely runner conjecture states that each runner is lonely at some time."

http://en.wikipedia.org/wiki/Lonely_runner_conjecture#The_conjecture

 

Doesn't a larger k mean more runners on a longer track?

(EDIT: Or that the distance between them is allowed to be shorter with more runners.)

Edited June 11, 2015 by Spyman

[imatfaal]

"Consider k runners on a circular track of unit length. At t = 0, all runners are at the same position and start to run; the runners' speeds are pairwise distinct. A runner is said to be lonely at time t if he is at a distance of at least 1/k from every other runner at time t. The lonely runner conjecture states that each runner is lonely at some time."

http://en.wikipedia.org/wiki/Lonely_runner_conjecture#The_conjecture

 

Doesn't a larger k mean more runners on a longer track?

(EDIT: Or that the distance between them is allowed to be shorter with more runners.)

 

"Doesn't a larger k mean more runners on a longer track?" - No: track is unit length. The higher k the smaller the portion of the track that will cause the runner to feel lonely eg k=3 then at some point the runner will have 1/3 of the track empty both in front and behind him (ie the other two runnerscould be closed together and on the opposite side of the track). k=7 - there are 7 runners and a runner is lonely when there is a clear 1/7 of the track both behind and in front; this has been proved to occur. k=8 - it is not yet proven.

[tar]

imatfaal,

 

I am not offering a proof, but offering an indication that it should be provable for even higher than 8.

 

I have often commented to my wife, while driving long distances on heavily populated interstates, during the day, that I drove a speed that caused me to, from time to time, be a lonely runner.

I have a rule that I should not drive more than 7 miles an hour, over the speed limit, and often drive 71 in a 65. This speed causes slower drivers to not catch up to me, and faster drivers to pass me.

In any case, there have been times where I have estimated a 1/4 mile between the "pack" in front of me, and 1/4 mile between me and the "pack" behind. As I spend the majority of my time on such populated highways actually in a pack, or being passed by a pack, or in passing a slower driver, I would say the k is higher than 8, considering the average number of cars that would pass a particular point on that highway, in 30 seconds (1/2 mile) at that time, on that day.

 

Perhaps the solution can be found in terms of probability. As in, what is the longest possible time you can stand on the side of a busy interstate, moving at highway speeds, far from exits and entrances, without a car passing you.

 

Regards, TAR

Or perhaps a NASCAR track. The tracks are of a particular length, and the cars still in the race is going to be around 30 so the k could be figured. A long time after a caution, when the leader is lapping cars, what is the longest possible period of time you can sit in the stands, without a car passing?

Edited June 11, 2015 by tar

[Spyman]

"Doesn't a larger k mean more runners on a longer track?" - No: track is unit length. The higher k the smaller the portion of the track that will cause the runner to feel lonely eg k=3 then at some point the runner will have 1/3 of the track empty both in front and behind him (ie the other two runnerscould be closed together and on the opposite side of the track). k=7 - there are 7 runners and a runner is lonely when there is a clear 1/7 of the track both behind and in front; this has been proved to occur. k=8 - it is not yet proven.

Thank you, that was what I meant with my edit. And if the track length would increase proportionally with the numbers of runners then the distance when a runner would feel lonely would be constant. So the problem doesn't get more difficult with increasing or decreasing distance, it's the increasing number of runners covering parts of the track that makes the problem more complicated and harder to prove.

 

If the distance wouldn't be proportionally decreasing with increasing numbers of runners then two runners would never feel lonely.

[imatfaal]

Sorry Tar - but your comments are not really pertinent. This is a strict mathematical problem in highly artificial circumstances - really it is the quest for a mathematical proof for the easily acceptable notion that the different rotations of the runners will eventually leave one runner isolated. But with primes and common divisors etc. (which is intimately wrapped up in this) you cannot assume that obvious things actually happen.

[tar]

Imatfaal,

 

Yes, I am sorry to. I don't really thrive in those highly artificial circumstances. I will leave it up to the mathematicians to prove the thing, to their satisfaction.

 

Regards, TAR

[imatfaal]

Thank you, that was what I meant with my edit. And if the track length would increase proportionally with the numbers of runners then the distance when a runner would feel lonely would be constant. So the problem doesn't get more difficult with increasing or decreasing distance, it's the increasing number of runners covering parts of the track that makes the problem more complicated and harder to prove.

 

If the distance wouldn't be proportionally decreasing with increasing numbers of runners then two runners would never feel lonely.

 

Yep. It is a modular arithmetic and GCD problem I guess

Unity - just reading up about the conjecture at Open Problem Garden and I noticed this which might help stop you feeling down if you are struggling

 

Recomm. for undergrads: no

[Sato]

I don't think the matter is the size of the distance, but coordinating the property for more and more runners. It might be trivial for numbers that have trivial properties, such as the smaller ones, but maybe this triviality breaks at eight. Here are some ideas, could it have something to do with 8's being

• The smallest perfect cube greater than 1
• The number of vertices of a cube;
  • The number of vertices of a cubical graph, the 3-D case of a hypercube graph
• The first composite number that's not a multiple of two primes
• The base of the octonions, the largest generalization of complex numbers (after quaternions)

According to the proof for the case of 7, the problem lies within graph theory, specifically related to graph colouring; maybe the bottleneck lies in the properties related to this.

[Unity+]

 

Yep. It is a modular arithmetic and GCD problem I guess

Unity - just reading up about the conjecture at Open Problem Garden and I noticed this which might help stop you feeling down if you are struggling

 

I am struggling somewhat with the problem. Thanks for the reassurance.

 

I think the modularity comes from how the problem can be represented:

 

 

I guess you could represent this as a clock with six hands and differently-sized gears. Question is will there be any time when the gear rotations will allow such conditions to have the point on each hand to be a certain distance from the other hands.

[Unity+]

I took a whack at the conjecture, and here is a function I developed, though it could be unhelpful:

 

[math]H_{k}(\theta)=\left \{ f(\theta),... \right \}\begin{pmatrix} 0 & \phi _{1,0} &\cdots \\ \phi _{0,1}& 0 & \cdots \\ \vdots & \vdots & \ddots \end{pmatrix},\{t=u\}[/math]

Now what I did was take the unit circle and apply a unit second to each section of the unit circle:

Each function with the H(theta) function represents the angular position of each "runner." In the matrix, each non-zero value is the distance between each player based on the position of each runner during time t(positive value). Now, what I did is I took the determinant of the matrix containing the angular distance between each runner at t=1 when the position functions for 3 runners is f(theta) = theta, g(theta) = 2theta, and k(theta) = 3theta, since each runner has to have a distinct velocity.

[math]H_{3}\left ( \frac{\pi }{6} \right )=\left \{ \theta, 2\theta, 3\theta \right \}\begin{pmatrix} 0 & \frac{\pi }{6} & \frac{2\pi }{6}\\ \frac{\pi }{6} & 0 &\frac{\pi }{6} \\ \frac{2\pi }{6} &\frac{\pi }{6} & 0 \end{pmatrix},\left \{ t=1 \right \}=\frac{\pi ^{3}}{54}[/math]

I then subtract that determinant by 1/k, which is 1/3. I get the value [math]\frac{\pi^3 - 18}{54}[/math], which is less than 1/3.

My conjecture about this is that if the difference between the determinant and 1/3 always remains smaller than or equal to 1/k, then it shows that each runner will be lonely at least once. However, this is not proven. However, it might be something.

The reasoning I have for this conclusion, however, is that if it was not lower than or equal to 1/3, then there will always be 1 or more runners who are met up by one of the other runners and it will always occur. I can see that it would occur if acceleration was a factor involved in the problem.

Here is the mathematical statement:

[math]\lim_{k \to \infty } H_{k}(\theta)-\frac{1}{k} \leq \frac{1}{k}[/math]

Or

[math]\lim_{k \to \infty } \frac{H_{k}(\theta)}{2}\leq \frac{1}{k}[/math]

EDIT: the other unit circle was just too big.

Edited June 12, 2015 by Unity+