On the Lonely Runner conjecture for prime number of runners

The formulation of the problem can be found here, here, or here.

Conjecture Suppose $p$ runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least $\frac{1}{p}$ (along the track) away from every other runner.

We consider $p$ being odd prime number of runners with distinct speeds $v_r \in \mathbb{Z}, r=1..p-1$ , and without loss of generality $v_p=0$ .

Consider speeds decomposition base p $v_r= \sum \limits_{n=0}^M v_{r,n} p^n, v_{r,n} \in \mathbb{Z}/p$ , with negative speeds being p-complement represented.

For each speed there is first non zero ‘digit’ base p, e.g. $n_r= \max k: v_{r, k'} = 0, \forall k' < k$ . We want to rearrange speeds that the positions of the first non zero digits in descending order – $n_r \geq n_{r'}, \forall r < r';$ .

For example, if $n_1=0$ than every runner has speeds $v_r \mod p \neq 0$ , and at time $t=\frac{1}{p}$ their positions on a lap are $\frac{v_{r,0}}{p}$ + whole number of laps – e.g. they all are distant from the origin – Lonely Runner conjecture is satisfied.

Some terminology for positions on the lap. Sector k – $S_k = \left( \frac{k}{p}, \frac{k+1}{p} \right)$ , beginning of the sector k $B_k= \frac{k}{p}$ . Origin – $B_0$ . Lonely Runner conjecture is satisfied when there are no runner sin $B_0, S_0, S_{p-1}$ . $B_k$ is occupied if at least one of the runner at position $B_k$ , and unoccupied (free) otherwise.

At time 0 all runners are at origin. If $n_1= n_{p-1}$ at time $\frac{1}{p^{n_1+1} }$ all runners are distant. Therefore, we consider the case when $n_1 > n_{p-1}$ .

At time $\frac{1}{p^{n_1+1} }$ none of the runners at the origin, runners with $n_r= n_1$ are in the beginning of sectors $v_{r, n_1}$ . Since there are at most $p-2$ such runners at least one $B_k, k \neq 0$ is unoccupied. Since multiplicative integer group modulo prime number is cyclic there is time $t_1= \frac{m_1}{p^{n_1+1}}, m_1 \in \mathbb{Z}/p$ when $B_{p-1}$ is free. At that time none of the runners in the last sector, none in the origin, but some may be at sector 0.

We need the following sequence of numbers $r_1 = 1, r_k = \min k': n_{k'} < n_{r_{k-1}}, k \geq 2$ , e.g. $r_k$ indexing the first runners with distinct $n_r$ .

Suppose we have runners at arbitrary positions $l_1, ..., l_n$ with speeds $v_1, .., v_n, v_k < p-1, \forall k$ . Consider times $\frac{m}{p}, m \in \{1..p-1\}$ . Since the multiplicative group of integers modulo prime p is cyclic there is at most 2 distinct $m$ when the runner is in the vicinity of origin. Therefore, if $n< \frac{p-1}{2}$ there is m when none of the runner in the vicinity of the origin.

From that it follows that if $r_{k+1} -r_k < \frac{p-1}{2}$ there is a time $t= \sum_k \frac{m_k}{p^{n_{r_k}+1}}$ , where $m_k$ is a sequence of numbers that guarantee that the first $r_k$ runners neither in the first nor in the last sectors by applying previous paragraph recurrently.

The difficult case that is left is when there are two or more $r_k$ , and $\exists k | r_{k+1} -r_k \geq \frac{p-1}{2}$ .

Update 28.Aug.2012

The idea to use group operations and time proportional to $\frac{1}{p^k}$ , where k is $\max \lceil log_p v_k \rceil$ does not work. For example, the time when no runners are near the origin for the runners with speeds 1 3 4 5 7 18 is $\frac{5}{11}$ and $\frac{6}{11}$ and for the times $\frac{m}{49}$ for all $m$ there is at least one runner in the vicinity of the origin. On the other hand, the time when closest runners are most distant from the origin is corresponding to the time when runners 4 and 7 are at the same distance from the origin on the opposite sides from the origin. e.g. the time for the maximum distance of closest runners from the origin is of the form $\frac{m}{v_k+v_i}$ for some $m, k, i$ , and the question here is to check if there are different runners close to the origin. Moreover, either all $m, v_k, v_i$ have common factor, or they are relatively prime (no pair have common factors).

About these ads

One Response to On the Lonely Runner conjecture for prime number of runners

manju says:

February 19, 2013 at 2:39 am

pls tell me how to find the lonely prime numbers am not understood aboue explanation pls tell me simple logic