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 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?
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.]