The lonely runner conjecture states that for $M=\{m_1,...,m_n\}$ a set of distinct positive integers the quantity $$ \kappa(M):=\sup_{t \in \mathbb{R}} \min_i ||tm_i|| $$ satisfies $\kappa(M) \geq \frac{1}{n+1}$, where $||x||$ denotes the distance of $x$ from the nearest integer.

It is stated without proof in Remark 1 of this paper that $\kappa$ is a rational number whose denominator divides $m_i+m_j$ for some $i,j$. I have seen this property of the denominator mentioned in several other places, without a satisfying reference.

Is a proof of this property of the denominator published anywhere? Is there some simple proof I am overlooking?

  • $\begingroup$ There is a point $t$ such that attained the $\sup$ and for some $m_i$ and $m_j$ we have $\|t m_i\| = \|t m_j \| = \kappa$ $\endgroup$ – Mahdi May 25 '18 at 20:42
  • $\begingroup$ That hopefully gives the solution. $\endgroup$ – Mahdi May 25 '18 at 21:16
  • $\begingroup$ @Mahdi Indeed. The only extra information needed is that $tm_i$ and $tm_j$ are on the opposite sides from the corresponding nearest integers. $\endgroup$ – fedja May 25 '18 at 21:50

$\newcommand{mod}{\mathrm{mod} \ }$ Define $f_i(t) := \| t m_i \|$. We have

$$ f_i(t) = \begin{cases} m_i t - k, & \text{if } t\in[\frac{2k}{2m_i},\frac{2k+1}{2m_i})\\ -m_i t +(k+1), & \text{if } t \in [\frac{2k+1}{2m_i},\frac{2k+2}{2m_i}) \end{cases} \tag{1} $$ $f_i$ is a continuous piecewise linear function, which is $0$ at $\frac{2k}{2m_i}$ and is $\frac 12$ at $\frac{2k+1}{2m_i}$.

Now, consider the function $$f(t) := \min_i f_i(t)$$

$\hskip2in$ a typical graph of $f$

We want to find $\sup_{t >0} f(t)$. Since $f$ is periodic, it is enough to consider $\sup_{0<t<1} f(t)$. Moreover, for sufficiently small $\epsilon >0$, it is enough to consider $\sup_{\epsilon \leq t \leq1-\epsilon} f(t)$. Since $f$ is a continuous function attains its supremum on $\epsilon \leq t \leq1-\epsilon$ at some point, like $t_0$. There is two function, like $f_i$ and $f_j$, such that $$f_i(t_0)=f_j(t_0)=f(t_0)$$ Note that the rules of $f_i$ and $f_j$ at $t_0$ are different in (1), i.e. $\lfloor 2 m_it_0 \rfloor \not\equiv \lfloor 2 m_j t_0 \rfloor (\mod 2)$. (otherwise $f(t_0)$ can not be supremum). For example, let $f_i(t_0)= m_it_0-k_i$ and $f_j(t_0)=-m_j t_0 +(k_j+1)$, for some $k_i,k_j \geq 0$. Now the equality $f_i(t_0)=f_j(t_0)$ gives $$t_0 = \frac{k_i+k_j + 1}{m_i+m_j},\quad \kappa=f(t_0)= \frac{m_ik_j-k_im_j+m_i}{m_i+m_j}$$ Now, the result at hand.

This may be a reference to your question. Just click on the 'cite' link below!


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.