8
$\begingroup$

Lonely Runner Conjecture is the following problem, and the conjecture was proven to be true for $k\leq 7$:

Let $V$ be the set of $k$ distinct positive integers with $v_1<v_2<...<v_k$ Then $$\exists t\in [0,1]\quad \forall v_i\in V\quad \|tv_i\|\geq \frac{1}{k+1}$$

where $||x||$ denotes the distance from $x$ to the nearest integer.

It is known that for $k+1$ runners, one can assume the following WLOG:

  • $\gcd(v_1,...,v_k)=1$
  • $(k+1)|v_1$
  • $V$ is neither the set of arithmetic/geometric progression nor prime numbers.

Although it wasn't stated in any paper, it is trivially verifiable that one can also assume the following WLOG:

  • $\forall r\in\mathbb{Z}$ s.t. $2\leq r\leq k+1$, $\exists v_i\in V$ s.t. $r|v_i$.
  • $\forall r\in\mathbb{Z}$ s.t. $k+2\leq r\leq 2k+1$ and $2|r$, $\exists v_i\in V$ s.t. $r|v_i$.

What can I further assume about $V$?

The first three assumptions were stated in View-obstruction: a shorter proof for 6 lonely runners by Jérôme Renault, which is also a nice introduction to LRC along with the corresponding Wikipedia page (Lonely runner conjecture). The lonely runner with seven runners by Barajas is also a relevant reference.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ You may wish to add a link to some background on the LRC, for readers not familiar with it $\endgroup$
    – Yemon Choi
    Commented May 12, 2015 at 22:54
  • 5
    $\begingroup$ It might be worth including in your list that we can assume the speeds are integers, which at least is not obvious to me. It is proved in Section 4 here: combinatorics.org/ojs/index.php/eljc/article/view/v8i2r3 $\endgroup$
    – Sam Hopkins
    Commented May 12, 2015 at 23:16
  • 3
    $\begingroup$ In response to @YemonChoi, this previous MO question has some references: Not-lonely runners. Will Sawin's answer establishes only "logarithmic distance between upper and lower bounds." $\endgroup$
    – Joseph O'Rourke
    Commented May 12, 2015 at 23:43
  • 1
    $\begingroup$ You are probably interested in this recent blog post of Terry Tao as well: terrytao.wordpress.com/2015/05/13/… $\endgroup$
    – Sam Hopkins
    Commented May 15, 2015 at 13:44
  • $\begingroup$ @Math.StackExchange I see that $k+1$ divides (w.l.o.g.) one the $v_i$'s, but why should it divide the smallest member $v_1$? $\endgroup$
    – Peter Mueller
    Commented Jul 3, 2018 at 14:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.