Pseudo-lonely runner conjecture with $\frac{1}{k+1}$ and generalizations

75 Views Asked by At

I was reading about the unsolved lonely runner conjecture on Wikipedia, which states "[c]onsider $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 they are at a distance of at least $\frac{1}{k}$ from every other runner at time $t$. The lonely runner conjecture states that each runner is lonely at some time."

My question is as follows:

Does there exist a solution for a sort of pseudo-lonely runner conjecture with a weaker condition than $\frac{1}{k}$, such as conditions of $\frac{1}{k+1}$, $\frac{1}{k+o(1)}$, $\frac{1}{k^{o(1)}}$, or something similar?

I'm not very well-versed in the sort of math this type of problem might require, so I don't know how I would do this even were I confident enough in myself to attempt something connected so closely to such a difficult problem. Any help you could give or relevant resources you could find would be greatly appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

With $\frac1k$ replaced by $\frac1{2k}$, there is a relatively short solution.

Choose a time $t$ uniformly at random from $[0,N]$, where $N$ is very large: much larger than $\frac1{|v_i - v_j|}$ for any $i \ne j$. For this value of $t$, the relative positions of the runners are also nearly uniform (with the approximation getting better and better as $N \to \infty$). So the probability that runner $i$ and $j$ are within $\frac1{2k}$ of each other at time $t$ approaches $\frac1k$. By the union bound, the probability that runner $i$ is within $\frac1{2k}$ of anyone at time $t$ approaches a limit of at most $\frac{k-1}{k} < 1$ as $N \to \infty$. Therefore there must be a time $t$ at which runner $i$ is at least $\frac1{2k}$ from everyone.

With the same argument, we can replace $\frac1{2k}$ by $\frac1{2(k-1)+\epsilon}$ for any $\epsilon>0$. When the speeds are integers, we can even reach $\frac1{2(k-1)}$ exactly: in this case, when we choose $$N = \operatorname{lcm}(v_1 - v_i, \dots, v_n - v_i)$$ the distance from runner $i$ to any other runner is actually exactly uniformly random. The integer case is actually fully general, but that's not obvious.

Doing significantly better than $\frac1{2(k-1)}$ seems hard.