Lonely Runner Conjecture. General case.


We consider (LRC) .

Conjecture Suppose n>1 runners having distinct constant speeds v_k > 0 start at a common point (origin) and run laps on a circular track with circumference 1. Then, there is a time when no runner is closer than \frac{1}{n+1} from the origin.

W.l.o.g. we can assume v_k > v_m \forall k>m.

One can formulate LRC as follows. Suppose l_k \in \mathbb{N}_0 is the number of whole laps (including 0) runner k passed on a track, than \exists t \in \mathbb{R}_+ and \exists l_k | l_k+\frac{ 1 }{n+1} \leq v_k t \leq l_k+ \frac{n}{n+1}.

Case n=1, two runners is trivial. At time t=\frac{1}{2 v_1} runner 1 is exactly distance \frac{1}{2} (l_1= 0).

Case n=2, three runners is a special case.

We start with 4 inequalities
\left\{ \begin{array}{ll}  \frac{l_1+1/3}{v_1} \leq t, &  t \leq \frac{l_1+2/3}{v_1} \\  \frac{l_2+1/3}{v_2} \leq t, & t \leq \frac{l_2+2/3}{v_2}  \end{array} \right.

Since t \in \mathbb{R}_+ we can eliminate it if all combination of left parts on the left columns are smaller than any right parts in the right column of the table. e.g.
\left\{ \begin{array}{l}  \frac{l_1+1/3}{v_1} \leq \frac{l_1+2/3}{v_1} \\  \frac{l_1+1/3}{v_1} \leq \frac{l_2+2/3}{v_2} \\  \frac{l_2+1/3}{v_2} \leq \frac{l_1+2/3}{v_1}\\  \frac{l_2+1/3}{v_2} \leq \frac{l_2+2/3}{v_2}  \end{array} \right.

The first and the last inequality are trivially correct. From the second and third inequality we would like to express l_2
\frac{v_2}{v_1} \left( l_1 + \frac{1}{3} \right) -\frac{2}{3} \leq l_2 \leq  \frac{v_2}{v_1} \left( l_1 + \frac{2}{3} \right) -\frac{1}{3}.
In other words,
\frac{v_2}{v_1} \left( l_1 + \frac{1}{3} \right) -\frac{2}{3} \leq l_2 \leq  \frac{v_2}{v_1} \left( l_1 + \frac{1}{3} \right) -\frac{2}{3} + \frac{1}{3}\frac{v_2}{v_1} +\frac{1}{3}.

There are 2 sub-cases.

  1. Sub-case \frac{v_2}{v_1} \geq 2.
    \frac{1}{3}\frac{v_2}{v_1} +\frac{1}{3} \geq 1 and \exists l_2 \in \mathbb{N}_0 satisfying inequality
  2. Sub-case \frac{v_2}{v_1} < 2 .
    In this case l_1=l_2=0 lead to (remeber that \frac{v_2}{v_1} > 1 )
    \frac{1}{3} \frac{ v_2}{v_1} - \frac{2}{3} \leq 0 \leq \frac{2}{3} \frac{v_2}{v_1} - \frac{1}{3}.

Case n=3, four runners is an illustration for a general case.

We start with 6 inequalities
\left\{ \begin{array}{ll} \frac{l_1+1/4}{v_1} \leq t, &  t \leq \frac{l_1+3/4}{v_1} \\  \frac{l_2+1/4}{v_2} \leq t, &  t \leq \frac{l_2+3/4}{v_2} \\  \frac{l_3+1/3}{v_3} \leq t, &  t \leq \frac{l_3+3/4}{v_3}  \end{array} \right.

Let’s express l_2 in terms of l_1
\frac{v_2}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} \leq l_2 \leq \frac{v_2}{v_1} \left( l_1 + \frac{3}{4} \right) -\frac{1}{4}.
Rewriting it we obtain
\frac{v_2}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} \leq l_2 \leq  \frac{v_2}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} + \frac{1}{2}\frac{v_2}{v_1} +\frac{1}{2}.
\frac{1}{2}\frac{v_2}{v_1} +\frac{1}{2} >1, since \frac{v_2}{v_1} > 1. In other words, \forall l_1 \exists l_2 \in \mathbb{N}_0 satisfying inequality.

Now, let express l_3 in terms of l_1 and l_2
\left\{ \begin{array}{l}  \frac{v_3}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} \leq l_3 \leq  \frac{v_3}{v_1} \left( l_1 + \frac{3}{4} \right) -\frac{1}{4} \\  \frac{v_3}{v_2} \left( l_2 + \frac{1}{4} \right) -\frac{3}{4} \leq l_3 \leq  \frac{v_3}{v_2} \left( l_2 + \frac{3}{4} \right) -\frac{1}{4}. \end{array}\right.

We can express l_2 with inequalities obtained earlier
\left\{ \begin{array}{l}  \frac{v_3}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} \leq l_3 \leq  \frac{v_3}{v_1} \left( l_1 + \frac{3}{4} \right) -\frac{1}{4} \\ \frac{v_3}{v_2} \left( \frac{v_2}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} + \frac{1}{4} \right) -\frac{3}{4} \leq l_3 \leq  \frac{v_3}{v_2} \left( \frac{v_2}{v_1} \left( l_1 + \frac{3}{4} \right) -\frac{1}{4} + \frac{3}{4} \right) -\frac{1}{4}.  \end{array}\right.
Collecting terms we obtain
\left\{ \begin{array}{l} \frac{v_3}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} \leq l_3 \leq  \frac{v_3}{v_1} \left( l_1 + \frac{3}{4} \right) -\frac{1}{4} \\  \frac{v_3}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} -\frac{1}{2} \frac{v_3}{v_2} \leq l_3 \leq  \frac{v_3}{v_1} \left( l_1 + \frac{3}{4} \right)-\frac{1}{4}+ \frac{1}{2} \frac{v_3}{v_2}.  \end{array}\right.

We can see that first inequality is always stronger that the second one (meaning that if l_3 satisfies first inequalities it will satisfy second inequalities). But the first inequalities are the same as previous inequalities for l_2 with relabelling. Therefore, \forall l_1 \exists l_2, l_3 \in \mathbb{N}_0 satisfying initial inequalities and LRC holds.

General case

We start with 2 n inequalities

\left\{ \begin{array}{lll}  \frac{l_k+\frac{1}{n+1}}{v_k} \leq t, &  t \leq \frac{l_k+\frac{n}{n+1}}{v_k} &  k=1..n  \end{array} \right.

Now we expressing l_{k+m_1}, m_1 \geq 1 in terms of l_k and l_{k+m_2}, m_2 > m_1 in terms of l_{k+m_1} and l_{k}.
\frac{v_{k+m_1}}{v_k} \left( l_k + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k+m_1} \leq  \frac{v_{k+m_1}}{v_k} \left( l_k + \frac{n}{n+1} \right) -\frac{1}{n+1}.
\frac{v_{k+m_2}}{v_{k+m_1}} \left( l_{k+m_1} + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k+m_2} \leq  \frac{v_{k+m_2}}{v_{k+m_1}} \left( l_{k+m_1} + \frac{n}{n+1} \right) -\frac{1}{n+1}.
\frac{v_{k+m_2}}{v_k} \left( l_k + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k+m_2} \leq  \frac{v_{k+m_2}}{v_k} \left( l_k + \frac{n}{n+1} \right) -\frac{1}{n+1}.

Now we can substitute first inequalities into the second ones.
\frac{v_{k+m_2}}{v_{k+m_1}} \left( \frac{v_{k+m_1}}{v_k} \left( l_k + \frac{1}{n+1} \right) -\frac{n}{n+1} + \frac{1}{n+1} \right) -\frac{n}{n+1}  \leq l_{k+m_2} \leq  \frac{v_{k+m_2}}{v_{k+m_1}} \left(\frac{v_{k+m_1}}{v_k} \left( l_k + \frac{n}{n+1} \right) -\frac{1}{n+1} + \frac{n}{n+1} \right) -\frac{1}{n+1}.
Rearranging terms we obtain
\frac{v_{k+m_2}}{v_k} \left( l_k + \frac{1}{n+1} \right) -\frac{n}{n+1}  - \frac{n-1}{n+1} \frac{v_{k+m_2}}{v_{k+m_1}}  \leq l_{k+m_2} \leq  \frac{v_{k+m_2}}{v_k} \left( l_k + \frac{n}{n+1} \right) -\frac{1}{n+1}  +\frac{n-1}{n+1} \frac{v_{k+m_2}}{v_{k+m_1}}.
Compare it to
\frac{v_{k+m_2}}{v_k} \left( l_k + \frac{1}{n+1} \right) -\frac{n}{n+1}  \leq l_{k+m_2} \leq  \frac{v_{k+m_2}}{v_k} \left( l_k + \frac{n}{n+1} \right) -\frac{1}{n+1}.
The second inequality is always stronger.

Therefore, we left with the set of inequalities (when they are satisfied LRC holds when LRC holds they are satisfied!!! )
\frac{v_{k}}{v_1} \left( l_1 + \frac{1}{n+1} \right) -\frac{n}{n+1}  \leq l_{k} \leq \frac{v_{k}}{v_1} \left( l_1 + \frac{n}{n+1} \right) -\frac{1}{n+1},\ \forall k=2..n.

Lets rewrite it again
\frac{v_{k}}{v_1} \left( l_1 + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k} \leq \frac{v_{k}}{v_1} \left( l_1 + \frac{1}{n+1} \right) -\frac{n}{n+1} + \frac{n-1}{n+1} \left( \frac{v_k}{v_1} +1 \right)

\frac{n-1}{n+1} \left( \frac{v_k}{v_1} +1 \right) > 2 \frac{n-1}{n+1} = 1+ \frac{n-3}{n+1} \geq 1 if n \geq 3 .


It is not clear from this why \frac{1}{n+1} is tight distance.


11.2.2016
It is clear why it is not clear. The above just tell that with speed ratio more the one we can always find a lap for faster runner. The tightness comes from from ratios less than one. Most probably from the interactions or the ratios coming from the same pairs.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s