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.
29 comments
Comments feed for this article
10 January, 2017 at 2:22 pm
Mark Lewko
You’re probably well aware of this but the lonely runner conjecture is just one of a surprisingly large collection of questions arising from different areas of mathematics that can be formulated in the following manner: Let
be a mean-zero function. Obtain an estimate from below for the following quantity in terms of only the cardinality of $B$:
In the case of the lonely runner conjecture one has
and one seeks an estimate for sets of size
. The trivial result from your post can be seen from applying mean value theorem to $(*)$ with
.
Perhaps the best-known problem of this form is Chowla’s cosine problem which asks for a lower estimate on (*) when
. Indeed, proving that (*) tends to infinity with B was a long-standing problem solved by Cohen as a corollary to his work on the the Littlewood problem. However the state of things here is still quite unsatisfactory. While the true lower bound is probably near $|B|^{1/2}$, no lower bound of polynomial strength is known.
If one considers
, then the problem of showing that (*) tends to infinity with
is open and would imply progress on the problem of finding large sum-free subsets within arbitrary sets of the integers. Indeed, in this case Bourgain expended a fair amount of effort “just” to show that (*) exceeded the constant
for all large sets.
Years ago, I attempt to apply a variant of Bourgain’s approach to the lonely runner problem. If I recall correctly, this leads to estimates of the form (*)
(or
in the lonely runner problem as stated here) for marginally non-trivial values of
. The idea is to slightly decrease the size of the interval defining
and then do some painful case analysis using the non-constant terms in the Fourier series defining $F$ to obtain a small gain.
Bourgain also considered (*) with the function
. In this case, he was able to obtain a lower bound of the order
, which has implications for solution free subsets of a linear equation in four variables. I recall hoping that one might be able to adapt this approach here to the LRC (although the relevant $F$’s for the LRC are symmetric which is the main obstruction to applying these arguments in the prior setting). Curiously, if one could succeed here then one might expect this to produce a result of similar strength to what you obtain here. On the other hand, your ideas might be circumventing the symmetry obstruction previously mentioned.
Another problem of this form occurs when one takes
. This is equivalent to a question of Erdos and Szekeres from 1950. While this looks very similar to the function arising from the sum-free subset problem from the Fourier analytic point of view, there is a simple but clever argument due to Erdos and Szekeres exploiting algebraic properties of this particular
, which appears to have no analog in other cases, which leads to a lower bound of the order
. Improving even the constant here has been open for over a half a century. There us also some interest in the case of sets within short APs here, with a result somewhat analogous to your Proposition 1.7 being obtained in a recent paper of Bourgain and Chang.
Yet another problem, having implications to an old question of Bohr regarding the convergence of Dirichlet series, occurs by taking
. This is slightly different since Parseval gives a lower bound of the order
and one seeks further asymptotic improvements. Here Konyagin has improved this by a factor of
. The truth is probably of the order
.
It might be worth considering if your ideas have any applications to these other problems.
10 January, 2017 at 6:57 pm
Terence Tao
That’s a nice perspective on this family of problems! Unfortunately it seems my methods don’t apply easily to the other problems. In all of the problems you mentioned, the “trivial” bound is basically what comes out of the pigeonhole principle (or integral variants thereof). Certainly the trivial bound for the lonely runner conjecture can also be established this way, but what sets this problem apart from the others you mentioned is that the trivial bound for lonely runner can also be obtained from the union bound, whereas I don’t see any good way to do so for the other problems. All of the methods in my paper are focused on trying to wring a bit of improvement over the union bound, but it doesn’t look to me like they have much chance of being able to improve upon more general applications of the pigeonhole principle (in which the average number of pigeons per pigeonhole is not close to one, but is instead much larger, or if the number of pigeons is allowed to be non-integral).
It’s certainly good to publicise these other problems though. The one about sum-free sets, in particular, definitely feels like one should be able to improve upon Bourgain’s result, or at least reprove it with a simpler proof…
11 January, 2017 at 1:55 am
Anonymous
Is it possible to make the method more flexible by relaxing the uniform(!) upper bound constraint in (3) on all the velocities to a more general constraint given by a function
dominating their distribution function and than optimize (over all permissible such functions
) the resulting lower bound for
(as a functional of
)?
11 January, 2017 at 7:51 pm
Terence Tao
Yes; actually for (3) to hold it would be enough for
of the velocities to be
. I’ll add a remark to this effect in the next revision of the ms.
11 January, 2017 at 3:36 am
anon
Shouldn’t the second term on the RHS in Theorem 3 be
instead of
?
[Corrected, thanks – T.]
11 January, 2017 at 10:02 am
MatjazG
I believe it should be; at least it is written thus in the preprint abstract. In any case, as it’s written in the blog post right now the lower bound in Theorem 3 divided by upper bound of
would diverge to infinity as
, so there is clearly something wrong!
11 January, 2017 at 9:53 pm
Kevin O'Bryant
Statements like Theorem 1.4 (from page 5-6 of the paper on arXiv, but not this blog post) make me uncomfortable. The more I think about them, the more vacuous they seem (the statement, not the proof), in the sense I describe in the next paragraph. I’m definitely cheating, in that the computation of
will terminate only if LRC is false, but then again that’s the only case in which we care about the Theorem.
The LRC is either true or false, if true then clearly (i) and (ii) are both true. If the LRC is false, there’s a smallest n’ for which there is a counterexample. If
, then again clearly (i) and (ii) are both true. If
, then (i) is false and we can compute
so as to make (ii) false in the following explicit manner: exhaustively examine every set of speeds with maximum 1, then 2, then 3, and so on, to find a counterexample. Take
large enough to capture this counterexample and make (ii) false.
The content of the theorem, imho, is that you are able to compute
without producing a counterexample, but the statement of the theorem doesn't draw attention to that. How much work would it be to actually compute a value?
12 January, 2017 at 9:20 am
Terence Tao
Yes, you’re right that the theorem is trivial if the constant
is allowed to be ineffective (not a priori bounded from above by any explicitly computable function). I did say in Theorem 1.4 that the constant
is effectively computable; actually, now that I look again at the proof, I think I can improve
to
for some explicitly computable but large
(something like
, perhaps, if one makes everything explicit). I’ll emphasise this point more and put in the improved bound in the next revision of the ms.
12 January, 2017 at 11:17 pm
chr0538
Why Goldbach conjecture was not people crack, really no idea? I do not think so, or some, there must be trouble you help me look at my proof, do not ignore me, a person is not recorded by history.
13 January, 2017 at 12:23 pm
Anonymous
chr0538: Please read https://terrytao.wordpress.com/about/ and stop posting such comments to Terry’s blog. It is very impolite to do so.
14 January, 2017 at 2:45 am
chr0538
OK
14 January, 2017 at 2:45 am
chr0538
Thanks.
25 February, 2017 at 6:25 pm
Terry Cheng
Thank you.
13 January, 2017 at 9:05 am
Eulogio Garcia
the conjecture of the solitary runner with the Dirichelet aproximation theorem is correct if
and the time is
.
aproximation theorem:
and
We know that:
latex ; 1 < a < n < m
.
ie:
(1)
; m = N = nk; a bk; n = 1
Thus there are infinitely many values
to teplace thim in equation (1).
Generally.
With these of dedutions and remembering the statement: any runner will be at least a distance
from another runner.
We have:
However observing equation (1) we see that it does not admit
; ie for such a group of runner the equality is not possible.
1 February, 2017 at 8:12 am
Jérôme Renault
Hello Prof. Tao,
: “View Obstruction: a shorter proof for 6 lonely runners”, Discrete Maths. (I am much more into game theory than into number theory and did not come back to the lonely runner since then, but I find this conjecture very interesting). It suggests the following elementary but systematic and general approach.
I am not sure whether you are aware of, or have noticed, the 2004 paper giving a short proof for
We assume the conjecture holds for
, are given positive integer speeds
,…,
, and want to show the existence of
such that :
for each
=1,…,
. W.l.o.g. we assume that
is a multiple of
, and that
…,
. (it is not difficult to see that one can also restrict attention to speeds such that for each
…,
there is at least one, and at most
, speeds which are multiple of
).
The simple idea is the following: consider a time
maximizing
among the times
where the other runners
,…,
, are all in the safe region
.
is strictly lower than
, then there exists
…,
and
…,
such that time
Claim: if the conjecture is false for these speeds, that is if
(possibly + or – small
) contradicts the definition of
. This claim is fully correct and give elementary proofs for
, (to my knowledge, much simpler than the other existing ones, see the appendix in the above paper) and was mainly used to prove the case
(where a different argument was used to tackle the case of 3 even speeds, but I believe it was just a short cut and the claim is likely to be also correct for
). I am not saying the claim will be surely correct for all
, but I believe the approach may be interesting and help simplifying the problem by restricting, to some extent, the study of the different speeds to the study of their congruence classes modulo
. (the approach could also be possibly improved by looking at times of the form
, with
…,
Do you have any ideas whether the claim could be be correct in general, and/or do you think there is any hope to prove the conjecture for larger
using such an approach ?
2 February, 2017 at 5:10 pm
anthonyquas
Hi Terry,
I’m looking at your ArXiv preprint and think there’s something missing in the statement of statement of Proposition 2.1. Presumably $Q$ is meant to be $P(w_1′,\ldots,w_{r’}’;N_1′,\ldots,N_{r’}’)$ (not $Q$ of those same parameters) and also $Q$ should be required to be $t$-proper?
[Thanks, this will be added to the next revision of the ms. -T.]
5 February, 2017 at 8:07 pm
anthonyquas
I’ve reached a point in the ArXiv ms where I’m not understanding something, and worse: there’s a fallacious way to derive the thing I’m not understanding. Between (3.13) and (3.14) you’re applying the pigeonhole principle to
to deduce that there are two elements
apart. You showed in (3.13) that there are
values of
such that
. I *can* see that there are two
‘s that are
apart, but I don’t see why you can say that for each
, there are two terms of
that are that distance apart (in particular, this would imply a bound on
). Can you enlighten me?
9 February, 2017 at 9:51 pm
Terence Tao
Oops; many of the occurrences of
here should be
(because
has length about
, and
has density about
in this progression). For the argument the important thing is that this quantity is
. Also the
‘s in the proof of Proposition 3 should be
. I’ll correct these typos in the next version of the ms.
10 February, 2017 at 8:35 am
anthonyquas
Good to know – would it be possible to email me a copy of the next version of the ms when it’s ready?
10 February, 2017 at 4:48 am
Magger
It seems that ${\|x\|_{{\bf R/{\bf Z}} \geq \frac{1} {n+1}}$ should be ${\|x\|_{{\bf R/{\bf Z}} \leq \frac{1} {n+1}}$ in Lemma 4.3?
[Thanks, this will be corrected in the next revision of the ms. -T.]
18 February, 2017 at 2:47 am
Magger
Is it true that argument about the disjointness of petal sets also holds for pairwise coprime velocities?
[Yes – T.]
7 October, 2017 at 12:55 am
Terry Cheng
Dear MR.Tao,I am so sorry to do that.I will study harder and carefully .I will be modest and never be arrogant.I will do mathematics in the future , that is my dream.I hope you can understand me.
I am sorry.
4 March, 2019 at 5:03 am
Joshua Siktar
In Theorem 3 here (or Theorem 1.2 using the paper’s numbering), the constant is not explicitly chosen to be optimal. I was wondering if part of the reason for this is that it is anticipated better bounds altogether will be found so quickly that a specific value of the constants would be moot. Or is the explicit value of the constant just not of general interest whatsoever?
From what I’ve read on the problem it’s clear there are numerous types of approaches on the problem, some very geometric in nature. Best of luck on all of this.
3 August, 2019 at 5:56 pm
phil howlett
Here is a matlab program that checks the bounds
clear all
%define the speed difference vector with at least two entries
%v = [1,2,3,4]
%v = [1,3,4,7]
%v = [1,2,3,4,5]
%v = [1,3,4,5,9]
%v = [1,2,3,4,5,6]
%v = [1,2,3,4,5,6,7]
%v = [1,2,3,4,5,7,12]
%v = [1,4,5,6,7,11,13]
%v = [1,2,3,4,5,6,7,8]
%v = [1,2,3,4,5,6,7,8,9]
%v = [1,2,3,4,5,6,7,8,9,10]
%v = [1,2,3,4,5,6,7,8,9,10,11]
%v = [1,2,3,4,5,6,7,8,9,10,11,12]
%v = [1,2,3,4,5,6,7,8,9,10,11,12,13]
%v = [1,2,3,4,5,6,7,8,9,10,11,13,24]
%v = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
%v = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,36]
%v = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,25,48]
%v = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,31,60]
%v = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,…
% 32,33,34,35,37,72]
% Goddyn and Wong example
v = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,…
32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,…
61,62,63,64,65,66,67,68,69,71,73,140,144]
%define the corresponding separation functions
x = 0:0.000001:1;
y=(@(x)min(v’*x – floor(v’*x),ones(size(v’*x)) – (v’*x – floor(v’*x))));
ymin = min(y(x));
ymax = max(ymin’)
%plot selected separation functions
figure(1)
axis([0 1 0 0.5])
hold on
plot([0 1],[1/2 1/2],’k’,’Linewidth’,0.5)
plot([1 1],[0 1/2],’k’,’Linewidth’,0.5)
plot(x,y(x),’c’,’Linewidth’,2)
plot(x,ymin,’k’,’Linewidth’,2)
plot([0,1],[ymax,ymax],’–k’,’Linewidth’,1)
hold off
5 August, 2019 at 3:55 pm
Babak Farhang
My naive approach (I don’t have a solution, thinking/writing out loud) would be to quantize the problem. Suppose our track is a ring with
v1 x v2 x v3 x ..
slots. (The v’s are still relative primes.) Consider a state machine S that moves peg1 by v1 slots, peg2 by v2 slots,.. at each transition. So let’s quantize t over the natural numbers and call each transition an increment by 1. Prove the mapping t -> S is cyclic. (I’m thinking you do this by proving any peg/runner ends up in the same position after a fixed multiple of steps, multiply these fixed multiples for each peg, and..)
If this approach works (o, I doubt I’m not being naive), then it can be proved that the pegs all meet at any arbitrary slot and hence that 1/k becomes 1/2 (?)
5 August, 2019 at 4:48 pm
Babak Farhang
1st correction: the ring must have v1 x v2 x v3 + 1 slots. (We want each peg/runner to eventually visit every slot.)
8 August, 2019 at 2:03 pm
Babak Farhang
Never mind that correction.. And for thinking out loud. Here’s my attempt using the discrete approach I mention above. https://babaksjournal.blogspot.com/2019/08/proving-lonely-runner-problem-discretely.html
13 August, 2019 at 9:23 am
Babak Farhang
An update: I have an argument (and an algorithm) for calculating the time when the runners are exactly at 1/2 from the origin if their speeds are all odd and relative primes. http://babaksjournal.blogspot.com/2019/08/lonely-runner-redux_12.html
16 September, 2019 at 10:59 pm
El problema del corredor solitario – Blog del Instituto de Matemáticas de la Universidad de Sevilla
[…] Tao tiene una entrada en su blog sobre el problema. […]