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
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to On the Lonely Runner conjecture for prime number of runners

  1. manju says:

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

  2. Pingback: On the lonely runner conjecture III | Crackpot Trisector Notes

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