# Lonely Runner Conjecture—A Second Attack

* A simple question related to the lonely runner conjecture. *

Dan Kleitman is one of the great applied mathematicians of the world. I say this knowing that much of his work is on basic questions from many areas of mathematics, including graph theory, number theory, combinatorics, and more. The “applied” word is based on his being part of the MIT applied math department—where the word “applied” is arguably a bit different from the normal meaning.

Today I just want to ask a simple question that is related to the lonely runner conjecture.

Dan, with his coauthors Tom Bohman and Ron Holzman, solved the case of six runners. Their paper is a quite clever case-analysis of the problem. As they say:

The same methods may be used to attack the problem for , but the amount of work involved seems to grow so fast with as to make this approach impractical.

Dan is also famous for his technical help on the movie, “Good Will Hunting.” See the review by Mark Saul and an extra set of comments directly from Dan on his “role” in the movie.

** The Lonely Runner Problem **

In a recent post I sketched an approach to prove better bounds on the lonely runner conjecture. Recall the conjecture can be stated as: A set of runners start together on a unit length circular track. They run at speeds , which are integers. Is there a time when they are all not within of the start?

I suggested that we might be able via the the probabilistic method to at least prove there is a so that they are not within of the start. I was unable to do that, but did find a way that could prove such bounds for some sets of runners—we identify each runner with a different speed. One interesting special case is when the speeds are:

Here the previous method could prove a that was non-trivial. See that discussion for all the details. What I wish to raise today is the possibility that the proof method may prove a larger value of provided a simple question can be answered.

** The Question **

The question is quite simple. Consider the set . Let us say that and can be **paired**. Say two disjoint sets and are *admissible* provided the sets ,, form a partition of . Note, this means that every in is in exactly one of the following forms: where is in , where is in , and where is in .

The quality of the partition is measured by how large is. The goal is to get as many integers into and make as small as possible. The ratio , or rather , determines indirectly the constant —the larger the ratio, the better the constant.

Here is what I used before. Take all the odd integers below and let them form a set . Then set to be . Let be the remaining integers. It is each to see that they are admissible, and the ratio is about .

One can do better. Note that in the above construction no integer of the form is used. So an obvious idea—well one that is obvious now—is to apply the same method to those integers of this form. Ignoring floors and ceilings, the method will yield a bound of

This sums to , which is a nice improvement over the initial method. The question then is: *What is the best ratio that is possible?* Is the right answer ? Is there a lower bound that shows this recursive construction is optimal, or is there a better one?

** Open Problems **

Two final points. One of my students has run the greedy algorithm in a computer simulation and found that for equal to one hundred million the answer is about . Note, the recursive construction is not the greedy algorithm, but it seems cool that both methods get about the same answer.

The other question is: what happens for other rules? What if we can match and ? Or what if we allow to match either or ? Then what is the best that one can do? All would help improve the bounds on the lonely runner conjecture.

[fixed problem of 2x displaying as 46, 3x as 56; clarified 2|B|/n vs. |B|/n.]

Certainly , since half of the largest half of the numbers are odd, and thus must be in . Being more careful, does in fact appear to be the best you can do asymptotically. Let be vertices of a graph in which and are adjacent if one is double the other. We want a maximum matching on this graph, and would be the unmatched vertices. Lucky for our analysis, this graph is a disjoint union of paths. In fact, of the paths have length , have length , have length , etc. Maximum matchings on paths might as well be greedy, but odd paths will have one unmatched vertex—this will make the difference between and . I'm having diffuculty with WolframAlpha, but the following Mathematica script gives a convincing plot of the optimal in the case where is a power of : DiscretePlot[2*(Sum[Floor[(m+ 1)/2]*2^(k-2-m), {m,1,k-2}]+Floor[(k+ 1)/2])/(2^k),{k,1,100}]

When is a power of , the proof that this optimal expression for goes to is a straightforward application of the geometric series.

If 1/2 of the paths have length 1, 1/4 have length 2,then this is already a total of 1…

But I think your approach works, 1/4 of paths have length 1 (starting at odd numbers from n/2 to n), 1/8 of paths have length 2 (starting at odds from n/4 to n/2) and so on.

There is no need for Mathematica here, just for math: (1/8-1/32)+2(1/32-1/128)+…=3/32(1+1/4+1/16+..+1/4+1/16+..)=3/32(4/3)(1+1/4+..)=3/32(4/3)^2=2/3.

Oops, maybe there is need for mathematica, the previous formulas are pretty bad… But the point is that the approach works and an elementary calculation (that beats me) gives the optimal limit for any pairing.

I don’t know if anyone else has the same problem but my computer displays {2x} as 46. I am not kidding, for me the sentence read “What does the sentence “Let us say that x and 46 can be paired.” If I hover over 46, then it shows {2x}. Similarly, {3x} is 56.

Also, instead of the ratio {|B|/n}, you mean ratio {2|B|/n}.

Have the same problem, seeing 46 et cetera. Your comment finally helped me to make sense of it.

Here is something to consider. I haven’t checked everything but its worth sharing. If I have n runners running at unique integer speeds r and they all start at the same point then they will all be back at the same point after completely the number of cycles equal to the product of their speeds.

d = r_1 x r_2 x … x r_n

This will be some large integer number.

If you take and spread out the race on a number line equal to d and take the d mod r_n for each racer along the number line then the zero’s will spread symmetrically about the midpoint d/2.

If all the r’s are odd integers then the midpoint will be half integer (or half way around the track). If the r’s are all even integers then the midpoint will be an integer.

If there is a mix of even and odd integers then there is some 1/x cycle point where there is a half integer alignment where x is an integer determined by the number of even integers; These alignment points occur infinitely often over an infinitely long race.

Now for the real case I would leave this thought. Suppose one assumes that the start point can move at some rate. We know that there is some number of cycles d which is product of the rates for which there is a point where they are all aligned. if we set the rate at 1/2d then when all the runners are aligned at d the start point should be opposite of them.

Will have to think on this some more…

Just another note…”if all the r’s are odd integers” should include a note about them being prime. I was thinking about primes in realtion to the half integer note. If the odd number is factorable, then then one will need to divide through some additional times to get to the half integer point. Will take a look again later

“determined by the number of even integers” should be determined by some function of the number of even integers also

“completely the number” should be completing the number

Isn’t it easy to prove that the greedy algorithm is optimal? The problem is equivalent to picking the largest subset

$B$ of integers in [1,n/2] that is disjoint with $2B$. Any integer can be written as $2^a \cdot b$ for some odd $b$. Partition $[1,n]$ into equivalence classes of

integers having the same $b$; each class is of the form {b, 2b, 4b,…}. The only constraints (“picking x implies not

picking 2x”) are among elements of the same class; in fact if we sort the elements of each class, the only constraint is

that if you pick $x <= n / 2$, then you cannot pick the element in the very next position. So inside any given class,

the greedy algorithm is obviously optimal.

In sort, the optimal solution is to pick all $x = 2^a \cdot b$ where $x <= n / 2$ and $a$ is even.

Just to clarify: as argued above, the optimal solution is to let $B$ be all $x = 2^a \cdot b$ where $x <= n / 2$, $a$ is even and $b$ is odd. Then $2 B$ is all $x = 2^a \cdot b$ with $x n / 2$ of the form $x = 2^a \cdot b$ with $a$ even, and $b$ odd. That is, $A$ is all $x >= n / 2$ with an even number of trailing zeroes in their binary representation.

As one in every $2^t$ integers has $t$ trailing zeroes, the size of $A$ relative to $n/2$ is roughly $1/2*(1+1/4+1/16+…) = 2/3$, so the size of $A$ is roughly $2/3 * (n/2) = n / 3$. Maybe it is even possible to write an explicit bijection to argue that $B$ and $A$ have the same size up to +- 1.

Just to clarify: as argued above, the optimal solution is to let $B$ all $x = 2^a \cdot b$ where $x <= n / 2$, $a$ is even and $b$ is odd. Then $2 B$ is all $x = 2^a \cdot b$ with $x n / 2$ of the form $x = 2^a \cdot b$ with $a$ even, and $b$ odd. That is, $A$ is all $x >= n / 2$ with an even number of trailing zeroes in their binary representation.

As one in every $2^t$ integers has $t$ trailing zeroes, the size of $A$ relative to $n/2$ is roughly $1/2*(1+1/4+1/16+…) = 2/3$, so the size of $A$ is roughly $2/3 * (n/2) = n / 3$. Maybe it is even possible to write an explicit bijection to argue that $B$ and $A$ have the same size up to +- 1.

Somehow the ‘larger than’ symbols mess up with the previous comments.

Just to clarify: as argued above, the optimal solution is to let $B$ all $x = 2^a \cdot b$ where $x <= n / 2$, $a$ is even and $b$ is odd. Then $2 B$ is all $x = 2^a \cdot b$ with $x 'at most' n$ and both $a, b$ odd. Finally, $A$ is the set of all

$x 'larger than' n / 2$ of the form $x = 2^a \cdot b$ with $a$ even, and $b$ odd. That is, $A$ is all $x 'larger than' n / 2$ with an even number of trailing zeroes in their binary representation.

As one in every $2^t$ integers has $t$ trailing zeroes, the size of $A$ relative to $n/2$ is roughly $1/2*(1+1/4+1/16+…) = 2/3$, so the size of $A$ is roughly $2/3 * (n/2) = n / 3$. Maybe it is even possible to write an explicit bijection to argue that $B$ and $A$ have the same size up to +- 1.

Hi Dick,

Just to clarify, by partition you meant that any x in [1..n] can be in B or 2B, but not both?

So for example, if n=4, then A={1,3} or A={3,4} ?

Paul.

“What is the best ratio that is possible?”

Isn’t that n=2 ?

Let me emphasize the following. Let speeds be . We can split track into n+1 sectors, than at time all runners will be in the beggining of the sector number . Violation of the lonely runner conjecture at time t happens only when one of the runner is in the beginning of sector 0 (where we have standing runner). Therefore, only non-trivial case is when at least one of the speeds is divisible by the n+1. My limited simulation of this case show that in that non-trivial case the measure of time lonely runner conjecture holds is non-zero. And than your probability approach may be working well, but you need to use the fact that at least one of the speeds is divisible by n+1, and at least one of the speeds is not divisible by n+1. I do not know how to use it, but it seems that the only interesting times is when one of the runners enters sector 1 and sector n.

Just some additional notes while I have a moment.

Since we are dealing with unitary circles we can represent a runner as a complex number

EXP((i*2pi*y)(1/r_n))

Here we assume the fastest runner will complete 1 turn for each integer value of y, and all other runners complete some fraction of turn for each integer value of y.

We at this point think of each r as being a basis of some number system. Since the r’s can be different we have to take the product of the r’s in order to find the basis for the entire system.

d = r_1 x r_2 x … x r_n

or

EXP((i*2pi*y)(1/d)) = EXP((i*2pi*y)(1/r_1)) x EXP((i*2pi*y)(1/r_2)) x … x EXP((i*2pi*y)(1/r_n))

If the r’s are all prime numbers, the product space d representing the basis of the system is not reducible except by removing one of the r’s.

If the r’s contain composite numbers the product space d is reducible to some smaller system basis b. The extent of the reduction is dependent on whether numbers are coprime.(?)

In any case, it is in the reduced basis where one would look to see for which values of y the phase values (1/r) are not equal to integer values in the series:

Sum = EXP((i*2pi*y)(1/r_1)) + EXP((i*2pi*y)(1/r_2)) + … + EXP((i*2pi*y)(1/r_n))

It should be noted that while above we inferred that y is an integer, it need not be. When the r’s are real numbers whether the r’s are factorable is highly dependent on whether the number is a repeating decimal.

inferred should be implied

Just a minor note, in this expression:

EXP((i*2pi*y)(1/d)) = EXP((i*2pi*y)(1/r_1)) x EXP((i*2pi*y)(1/r_2)) x … x EXP((i*2pi*y)(1/r_n))

One should include a normalizing constant (1/EXP(r_1 + r_2 +…+ r_n)) on the RHS, bad habit to drop those.

Disregard…long day at work

LHS = EXP((i*2pi*y)(k/d))

k=(Sum((1/r_i)(r_1 x r_2 x … x r_n))

Just a thought. I cannot prove it. Suppose we have sorted positive integer speeds . At the moment we have the first runner and the last runner at equal distance form origin, and none in the origin. Let's look at positions of all runners at that time. More precisely we are interested what happening at points . If speeds are 1..n all points are occupied except the origin, and Lonely runner conjecture is satisfied. Suppose we have runners 1..k-1, k+1.. n+1, than all points except the origin and are occupied. We are now interested in finding the time when runner if was in unoccupied place reach the origin. Since the time symmetry we can look only at . At the time "would be runner" k is at the origin, and the rest runners are at least from the origin. e.g. Lonely runner conjecture is again satisfied. Therefore, a conjecture – At the time when all "would be runners" meet at the origin, and none of the real runners are at the origin Lonely runner conjecture is satisfied. By the "would be runners" we mean all runners with the speed .

The counter example to previous post is speeds 1 3 4, and the problem is would be runner 2 that have real runner 4 which is twice faster. In this case the time when conjecture is satisfied is with positions, say, which is in the vicinity of proposed time . The interesting approach can be to use the induction in the following sense. For a given set of speeds start with runners , which satisfy Lonely Runner conjecture for runners at time and than remove runners one by one, say, starting from the highest speed, and show, that after removing one runner, the conjecture is still satisfied, e.g. induction step would be – given m runners with , where still k untouched runners, and some real runners from the original problem, with LR conjecture satisfied for m runners. Than the conjecture is still satisfied for m-1 runners after removing one of the first k runners. That seems to be easy for the first virtual runners, and the only care is needed when being removed runner has real runner counterpart with speed equal to integer multiples of being removed runner. There are actually can be more than one runner. This seems to be more controllable approach in terms of the time and the positions of runners when LR conjecture is satisfied.

Another thought. Consider sequence of times . Observe that , Next observation is that the position for the runner with speed at time is , i.e. by changing we can control the fraction of the track gained by the runners with speed , i.e. if LR conjecture holds than it is possible to design sequence to form time sequence that at time LR conjecture holds. As an example, consider speeds , than , and .

A slight reformulation of LR conjecture – we define neighboring runners at time t as the runner that is less than 1/(n+1) distance from the origin at time t. We start with the time and find the neighboring runner with smallest speed (first neighbor). If none, LR is satisfied at . Next, we decrease time until the first neighbor becomes non-neighbor (say at ). Than, we repeat this procedure until there is no neighboring runner, or until time . In the first case we get the time when LR is satisfied, in the later case we get a counterexample. Consider speeds 1..5, than we have . Then, given n we need to find a set of n speeds that minimize . It is obvious that by rearranging speeds is even, and it seems that the best – it gives shortest . Then, we can try greedy procedure by creating different rational (actually real) speeds that will maximize time spent in the vicinity of the origin by the next runner. In general that gives reformulation of LR in terms of optimization problem, with no case analysis.

I do not know whether greedy runners is the best strategy, for speeds 1..n it gives minimal time 1/(n+1) among different speeds.

below is a Matlab(TM) code to produce time when LR satisfied for n=2..250 greedy runners.

% greedy Lonely Runner

for n=2:250;

t= [0 ] ;

v= [1 ];

while sum(t)<1,

% finding neighboring runner

tt= sum(t);

r= v*sum(t); % positions of runners

nb= abs(r- round(r))*(n+1)-1 abs(t_),

t(end+1)= sum(t)*eps*2;

else

t(end+1)= t_*(1);

end

% now we need to introduce new greedy runner that is at position 1/n+1

% at current time t= sum(t), its speed v_= 1/(n+1)/t

if (numel(v)< n) && (ii== numel(v)),

v_= (n)/(n+1)/sum(t);

v(end+1)= v_*(1+10*eps);

end

else

% found time t= sum(t)

break;

disp( [v; r] );

end

end

r= v*sum(t); % positions of runners

nb= abs(r- round(r))*(n+1)<1;

%disp( [v; r; nb;] );

%disp(sum(t))

t1= linspace(tt-.01, tt+.01, 10000); plot( t1, abs( v'*(t1)- round(v'*(t1)))*(n+1)-1, [0 1], [0 0], 'k')

tAll(n)= tt;

drawnow

end

t1=linspace( 5, 250, 1000);

plot((2:250), (tAll(2:end)), '.:', t1, t1.^( -sqrt(3)/2)*exp( sqrt(2) ) );

Code did not went well. Let me do greedy analysis for n=7, i.e. 8 runners by hands. We need to consider only positive speeds due to time symmetry coupled with the flip of the track.

We start with v1=1, at time 0. At t1=1/8, the time when runner 1 leave neighborhood of the origin, we need to introduce a new runner at position 7/8+, otherwise LR is satisfied. The slowest runner (that will cover the neighborhood of the origin for the longest time) satisfying this condition is v2=7. t2= 0.1607…, and positions of runners are 0.1607 1.1250, since no runners are in the vicinity of the origin, we need to introduce another runner. Below is the table

tn, v(new), positions

0.1250 7 0.1250 0.8750

0.1607 5.4444 0.1607 1.1250 0.8750

0.2066 4.2346 0.2066 1.4464 1.1250 0.8750

0.2657 3.2936 0.2657 1.8597 1.4464 1.1250 0.8750

0.3416 2.5617 0.3416 2.3910 1.8597 1.4464 1.1250 0.8750

0.4392 ——— 0.4392 *3.0742* 2.3910 1.8597 1.4464 1.1250

0.4464 ——– 0.4464 3.1250 2.4306 *1.8904* 1.4703 1.1436

0.5018 1.7436 0.5018 3.5128 2.7321 2.1250 1.6528 1.2855 0.8750

0.6452 ******* 0.6452 4.5164 3.5128 2.7321 2.1250 1.6528 1.1250

Can someone do better?

There is an idea. For prime n+1 the positions at time k/(n+1) induce multiplicative group modulo prime number, which is cyclic group. So, considering speeds written base n+1, for each position there are 2 possibilities. One is that there is no 0 at this position among all runners, and another one is that there is 0, but then one number is missing. If there is 0 than adding time to the time accumulator we can always set all runners at positions 1..p-2, and no runner at position p-1. If there is no runner with speed 0 we are done and need carefully combine times from all scales, i.e. there are whole number of turns due-to m_k that need to be added for the initial position for the next scale.

Ok, guys, since no one is interested in this topic, I will be short (experts will get the triviality in a fraction of minute). There is geometrical interpretation of LR conjecture, and algebraic one.

The geometric interpretation tells that runners have positions . Than in this log domain the there are linear stripes with appropriate boundaries. The LR conjecture says that for any set of speeds there is a moment in time when none of the points representing runners are inside the stripes. The limiting case is when speeds are 1..n where there is only finite number of points on the boundary of stripes. In other words, stripes cover the whole space (except countable number of boundaries) when speeds are 1..n, and have holes otherwise.

The algebraic one tells that representing speeds base n+1 and multiplying them to time represented base n+1, it is possible to find the time that no digit in the first “decimal” place are 0 or n, except it is exactly c.n . From this taking for simplicity n+1 prime, the situation is approximately the following. Suppose that there is maximal k that one of the speeds is then the time when LR conjecture is satisfied is of the form , where m is the member of multiplicative integers modulo . And from this point of view should be accessible for experts in the group theory. For n=9 it is also easy to visualize for everyone. It says that for any 9 numbers represented base ten, or in a usual way, there is time t also represented in decimal form, that tenth place after multiplication all 9 numbers by t are neither 0 nor 9, except when it is exactly c.9 . and that case (10 runners) is still open.

Dear Dick, there is small addition to your pairings, although not exactly along your ideas. We need to consider two cases.

Case 1. speeds are 1, 2, … n. At time all runners are distance at least . Done.

Case 2. At least one of the runner has speed different from 2,3,…,n. Take m equal to smallest missing speed. Then at times All runners except mod m = 0 are at distance (and many of them are paired), and there are many intervals when those runners are away from origin.

If m is prime, and more than half of the runners are at the origin it is easy to show that LRC holds. The rest may be a subject of your probability argument.

Case 3. Only runner with speed 1 is missing. Then this runner has speed k(n+1), i.e. it is fastest runner. Then start at time and run time backward. The fastest runner will be at distance faster than runner with speed 2. Therefore, LRC holds.

Here is the intuition. suppose n runners are sorted by speed . we start with slowest ones. They are equal distance from the origin at times . (I’m ignoring here they can have common multiplier) For example, . At time they are from the origin. If Any different speeds will lead to higher distance. Now introduce . if , the largest distance will be little bit smaller than the largest distance from 2 runners at time . The best case with distance . If we have beating, and it largest distance is not much better than general case, and worse than optimal case. Those of you with mathematical type may fill the details. Also it is quite possible this way of analysis can be done using computers.

There is a short paper “VIEW-OBSTRUCHON PROBLEMS. II” by T. W. CUSICK (PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 84, Number 1, January 1982, http://www.jstor.org/stable/2043801?origin=JSTOR-pdf ), proving case of 4 runners. My question is whether http://mkatkov.wordpress.com/2013/08/28/on-the-lonely-runner-conjecture-ii/ is of any interest to publishing, and if yes, would anyone care to help converting it to publishable form?

It once has been suggested to run poly-math projects, where everybody gets “nomial” contribution. The most common way to solve poly-“nomial” math system of constraints is Bushberger algorithm, and there one needs to compute sPoly (single out of poly), and then perform reduction with respect to the interested population. Frequently it is not useful, because sPoly is reduced to already existing opinion (constraint). So, let me put my sPoly here, although there is no official start of poly-opinion at this place.

Pairing is very important!!! Consider prime number of runners – p – it is easier. Then either all speeds are not equal mod p, and at time 1/p every one paired away from origin or some of the runners have speed equal kp. If there are too many of them, say all exept 1, then solve the problem of placing runners away from the origin for all those having speed kp, and then add 1/p. that does not change position of kp runners but move along the track the last unlucky runner :). Suppose there is runners with speeds kp (it is different k for every runner). Then the rest half will visit (because p is prime) vicinity of the origin twice, on the left and right side, in total p-1 times, therefore there is one moment of time when all of then will be distant. So, we need only consider the cases when less than runners have speed kp. For example, when p=5, the only difficult case is when exactly one runner has speed 5p; p=7 – when one or two runners have speed 7p. That is opens nice possibility to break the problem into cases, which breaks into sub-cases – highly parralelizable problem. Also, next open number is not prime, which adds complexity, but add another line of research.

Now about subcases. It seems that some of the subcases require different strategy in controlling positions. For example, if everything is paired, except, say, runners with speed kp and we can move those runners away from origin. There is a hole (actually in the number of runners), like in previous example, which can be placed to the origin adding time m/p. Since paired runners stay paired, and others does not move. Other subcases require analysis of continuous motion, e.g. if fastest runner is 1/p from the origin, it cannot reach runner with speed kp on the right (forward in time) and the left side (bacward in time) close to origin at the same time (meaning for any speed of above condition the runner 1 mod p and runner 0 mod p will be both away from the origin either on the left side or on the right side of distance vs time graph related to m/p times ).

I’m not the one to run the polymath project, but it may have success in solving either 8 or 11 (next open prime) runners, or anything in between. And it may give sufficient strategies to solve it in general. The question is how important is the question for someone to take the lead.