The lonely runner conjecture is the following open problem:
Conjecture 1 Suppose one has runners on the unit circle , all starting at the origin and moving at different speeds. Then for each runner, there is at least one time for which that runner is “lonely” in the sense that it is separated by a distance at least from all other runners.
One can normalise the speed of the lonely runner to be zero, at which point the conjecture can be reformulated (after replacing by ) as follows:
Conjecture 2 Let be non-zero real numbers for some . Then there exists a real number such that the numbers are all a distance at least from the integers, thus where denotes the distance of to the nearest integer.
This conjecture has been proven for , but remains open for larger . The bound is optimal, as can be seen by looking at the case and applying the Dirichlet approximation theorem. Note that for each non-zero , the set has (Banach) density for any , and from this and the union bound we can easily find for which
for any , but it has proven to be quite challenging to remove the factor of to increase to . (As far as I know, even improving to for some absolute constant and sufficiently large remains open.)
The speeds in the above conjecture are arbitrary non-zero reals, but it has been known for some time that one can reduce without loss of generality to the case when the are rationals, or equivalently (by scaling) to the case where they are integers; see e.g. Section 4 of this paper of Bohman, Holzman, and Kleitman.
In this post I would like to remark on a slight refinement of this reduction, in which the speeds are integers of bounded size, where the bound depends on . More precisely:
Proposition 3 In order to prove the lonely runner conjecture, it suffices to do so under the additional assumption that the are integers of size at most , where is an (explicitly computable) absolute constant. (More precisely: if this restricted version of the lonely runner conjecture is true for all , then the original version of the conjecture is also true for all .)
In principle, this proposition allows one to verify the lonely runner conjecture for a given in finite time; however the number of cases to check with this proposition grows faster than exponentially in , and so this is unfortunately not a feasible approach to verifying the lonely runner conjecture for more values of than currently known.
One of the key tools needed to prove this proposition is the following additive combinatorics result. Recall that a generalised arithmetic progression (or ) in the reals is a set of the form
for some and ; the quantity is called the rank of the progression. If , the progression is said to be -proper if the sums with for are all distinct. We have
Lemma 4 (Progressions lie inside proper progressions) Let be a GAP of rank in the reals, and let . Then is contained in a -proper GAP of rank at most , with
Now let , and assume inductively that the lonely runner conjecture has been proven for all smaller values of , as well as for the current value of in the case that are integers of size at most for some sufficiently large . We will show that the lonely runner conjecture holds in general for this choice of .
let be non-zero real numbers. Let be a large absolute constant to be chosen later. From the above lemma applied to the GAP , one can find a -proper GAP of rank at most containing such that
in particular if is large enough depending on .
for some , , and . We thus have for , where is the linear map and are non-zero and lie in the box .
We now need an elementary lemma that allows us to create a “collision” between two of the via a linear projection, without making any of the collide with the origin:
Lemma 5 Let be non-zero vectors that are not all collinear with the origin. Then, after replacing one or more of the with their negatives if necessary, there exists a pair such that , and such that none of the is a scalar multiple of .
Proof: We may assume that , since the case is vacuous. Applying a generic linear projection to (which does not affect collinearity, or the property that a given is a scalar multiple of ), we may then reduce to the case .
By a rotation and relabeling, we may assume that lies on the negative -axis; by flipping signs as necessary we may then assume that all of the lie in the closed right half-plane. As the are not all collinear with the origin, one of the lies off of the -axis, by relabeling, we may assume that lies off of the axis and makes a minimal angle with the -axis. Then the angle of with the -axis is non-zero but smaller than any non-zero angle that any of the make with this axis, and so none of the are a scalar multiple of , and the claim follows.
We now return to the proof of the proposition. If the are all collinear with the origin, then lie in a one-dimensional arithmetic progression , and then by rescaling we may take the to be integers of magnitude at most , at which point we are done by hypothesis. Thus, we may assume that the are not all collinear with the origin, and so by the above lemma and relabeling we may assume that is non-zero, and that none of the are scalar multiples of .
with for ; by relabeling we may assume without loss of generality that is non-zero, and furthermore that
where is a natural number and have no common factor.
We now define a variant of by the map
where the are real numbers that are linearly independent over , whose precise value will not be of importance in our argument. This is a linear map with the property that , so that consists of at most distinct real numbers, which are non-zero since none of the are scalar multiples of , and the are linearly independent over . As we are assuming inductively that the lonely runner conjecture holds for , we conclude (after deleting duplicates) that there exists at least one real number such that
We would like to “approximate” by to then conclude that there is at least one real number such that
It turns out that we can do this by a Fourier-analytic argument taking advantage of the -proper nature of . Firstly, we see from the Dirichlet approximation theorem that one has
for a set of reals of (Banach) density . Thus, by the triangle inequality, we have
for a set of reals of density .
Applying a smooth Fourier multiplier of Littlewood-Paley type, one can find a trigonometric polynomial
which takes values in , is for , and is no larger than for . We then have
where denotes the mean value of a quasiperiodic function on the reals . We expand the left-hand side out as
From the genericity of , we see that the constraint
and is the Dirichlet series
By Fourier expansion and writing , we may write (4) as
In particular, there exists a such that
Since is bounded in magnitude by , and is bounded by , we thus have
for each , which by the size properties of implies that for all , giving the lonely runner conjecture for .