You are currently browsing the tag archive for the ‘lonely runner conjecture’ tag.
I’ve just uploaded to the arXiv my paper “Some remarks on the lonely runner conjecture“, submitted to Contributions to discrete mathematics. I had blogged about the lonely runner conjecture in this previous blog post, and I returned to the problem recently to see if I could obtain anything further. The results obtained were more modest than I had hoped, but they did at least seem to indicate a potential strategy to make further progress on the problem, and also highlight some of the difficulties of the problem.
One can rephrase the lonely runner conjecture as the following covering problem. Given any integer “velocity” and radius
, define the Bohr set
to be the subset of the unit circle
given by the formula
where denotes the distance of
to the nearest integer. Thus, for
positive,
is simply the union of the
intervals
for
, projected onto the unit circle
; in the language of the usual formulation of the lonely runner conjecture,
represents those times in which a runner moving at speed
returns to within
of his or her starting position. For any non-zero integers
, let
be the smallest radius
such that the
Bohr sets
cover the unit circle:
Then define to be the smallest value of
, as
ranges over tuples of distinct non-zero integers. The Dirichlet approximation theorem quickly gives that
and hence
for any . The lonely runner conjecture is equivalent to the assertion that this bound is in fact optimal:
Conjecture 1 (Lonely runner conjecture) For any
, one has
.
This conjecture is currently known for (see this paper of Barajas and Serra), but remains open for higher
.
It is natural to try to attack the problem by establishing lower bounds on the quantity . We have the following “trivial” bound, that gets within a factor of two of the conjecture:
Proposition 2 (Trivial bound) For any
, one has
.
Proof: It is not difficult to see that for any non-zero velocity and any
, the Bohr set
has Lebesgue measure
. In particular, by the union bound
we see that the covering (1) is only possible if , giving the claim.
So, in some sense, all the difficulty is coming from the need to improve upon the trivial union bound (2) by a factor of two.
Despite the crudeness of the union bound (2), it has proven surprisingly hard to make substantial improvements on the trivial bound . In 1994, Chen obtained the slight improvement
which was improved a little by Chen and Cusick in 1999 to
when was prime. In a recent paper of Perarnau and Serra, the bound
was obtained for arbitrary . These bounds only improve upon the trivial bound by a multiplicative factor of
. Heuristically, one reason for this is as follows. The union bound (2) would of course be sharp if the Bohr sets
were all disjoint. Strictly speaking, such disjointness is not possible, because all the Bohr sets
have to contain the origin as an interior point. However, it is possible to come up with a large number of Bohr sets
which are almost disjoint. For instance, suppose that we had velocities
that were all prime numbers between
and
, and that
was equal to
(and in particular was between
and
. Then each set
can be split into a “kernel” interval
, together with the “petal” intervals
. Roughly speaking, as the prime
varies, the kernel interval stays more or less fixed, but the petal intervals range over disjoint sets, and from this it is not difficult to show that
so that the union bound is within a multiplicative factor of of the truth in this case.
This does not imply that is within a multiplicative factor of
of
, though, because there are not enough primes between
and
to assign to
distinct velocities; indeed, by the prime number theorem, there are only about
such velocities that could be assigned to a prime. So, while the union bound could be close to tight for up to
Bohr sets, the above counterexamples don’t exclude improvements to the union bound for larger collections of Bohr sets. Following this train of thought, I was able to obtain a logarithmic improvement to previous lower bounds:
Theorem 3 For sufficiently large
, one has
for some absolute constant
.
The factors of in the denominator are for technical reasons and might perhaps be removable by a more careful argument. However it seems difficult to adapt the methods to improve the
in the numerator, basically because of the obstruction provided by the near-counterexample discussed above.
Roughly speaking, the idea of the proof of this theorem is as follows. If we have the covering (1) for very close to
, then the multiplicity function
will then be mostly equal to
, but occasionally be larger than
. On the other hand, one can compute that the
norm of this multiplicity function is significantly larger than
(in fact it is at least
). Because of this, the
norm must be very large, which means that the triple intersections
must be quite large for many triples
. Using some basic Fourier analysis and additive combinatorics, one can deduce from this that the velocities
must have a large structured component, in the sense that there exists an arithmetic progression of length
that contains
of these velocities. For simplicity let us take the arithmetic progression to be
, thus
of the velocities
lie in
. In particular, from the prime number theorem, most of these velocities will not be prime, and will in fact likely have a “medium-sized” prime factor (in the precise form of the argument, “medium-sized” is defined to be “between
and
“). Using these medium-sized prime factors, one can show that many of the
will have quite a large overlap with many of the other
, and this can be used after some elementary arguments to obtain a more noticeable improvement on the union bound (2) than was obtained previously.
A modification of the above argument also allows for the improved estimate
if one knows that all of the velocities are of size
.
In my previous blog post, I showed that in order to prove the lonely runner conjecture, it suffices to do so under the additional assumption that all of the velocities are of size
; I reproduce this argument (slightly cleaned up for publication) in the current preprint. There is unfortunately a huge gap between
and
, so the above bound (3) does not immediately give any new bounds for
. However, one could perhaps try to start attacking the lonely runner conjecture by increasing the range
for which one has good results, and by decreasing the range
that one can reduce to. For instance, in the current preprint I give an elementary argument (using a certain amount of case-checking) that shows that the lonely runner bound
holds if all the velocities are assumed to lie between
and
. This upper threshold of
is only a tiny improvement over the trivial threshold of
, but it seems to be an interesting sub-problem of the lonely runner conjecture to increase this threshold further. One key target would be to get up to
, as there are actually a number of
-tuples
in this range for which (4) holds with equality. The Dirichlet approximation theorem of course gives the tuple
, but there is also the double
of this tuple, and furthermore there is an additional construction of Goddyn and Wong that gives some further examples such as
, or more generally one can start with the standard tuple
and accelerate one of the velocities
to
; this turns out to work as long as
shares a common factor with every integer between
and
. There are a few more examples of this type in the paper of Goddyn and Wong, but all of them can be placed in an arithmetic progression of length
at most, so if one were very optimistic, one could perhaps envision a strategy in which the upper bound of
mentioned earlier was reduced all the way to something like
, and then a separate argument deployed to treat this remaining case, perhaps isolating the constructions of Goddyn and Wong (and possible variants thereof) as the only extreme cases.
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
Proof: See Theorem 2.1 of this paper of Bilu. (Very similar results can also be found in Theorem 3.40 of my book with Van Vu, or Theorem 1.10 of this paper of mine with Van Vu.)
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
.
We write
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
occurs if and only if is a scalar multiple of
, or equivalently (by (1), (2)) an integer multiple of
. Thus
and is the Dirichlet series
By Fourier expansion and writing , we may write (4) as
The support of the implies that
. Because of the
-properness of
, we see (for
large enough) that the equation
and conversely that (7) implies that (6) holds for some with
. From (3) we thus have
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
.
Recent Comments