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 3For 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 LewkoYou’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 TaoThat’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

alsobe 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

AnonymousIs 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 TaoYes; 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

anonShouldn’t the second term on the RHS in Theorem 3 be instead of ?

[Corrected, thanks – T.]11 January, 2017 at 10:02 am

MatjazGI 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'BryantStatements 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 TaoYes, 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

chr0538Why 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

Anonymouschr0538: 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

chr0538OK

14 January, 2017 at 2:45 am

chr0538Thanks.

25 February, 2017 at 6:25 pm

Terry ChengThank you.

13 January, 2017 at 9:05 am

Eulogio Garciathe conjecture of the solitary runner with the Dirichelet aproximation theorem is correct if and the time is .

aproximation theorem:

; 1 < a < n;

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 RenaultHello Prof. Tao,

I am not sure whether you are aware of, or have noticed, the 2004 paper giving a short proof for : “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.

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 .

Claim: if the conjecture is false for these speeds, that is if is strictly lower than , then there exists …, and …, such that time

(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

anthonyquasHi 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

anthonyquasI’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 TaoOops; 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

anthonyquasGood 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

MaggerIt 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

MaggerIs 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 ChengDear 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 SiktarIn 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 howlettHere 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 FarhangMy 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 Farhang1st 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 FarhangNever 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 FarhangAn 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. […]