A remark on the lonely runner conjecture

13 May, 2015 in expository, math.CA, question | Tags: arithmetic progressions, lonely runner conjecture | by Terence Tao

The lonely runner conjecture is the following open problem:

Conjecture 1 Suppose one has ${n \geq 1}$ runners on the unit circle ${{\bf R}/{\bf Z}}$ , all starting at the origin and moving at different speeds. Then for each runner, there is at least one time ${t}$ for which that runner is “lonely” in the sense that it is separated by a distance at least ${1/n}$ 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 ${n}$ by ${n+1}$ ) as follows:

Conjecture 2 Let ${v_1,\dots,v_n}$ be non-zero real numbers for some ${n \geq 1}$ . Then there exists a real number ${t}$ such that the numbers ${tv_1,\dots,tv_n}$ are all a distance at least ${\frac{1}{n+1}}$ from the integers, thus ${\|tv_1\|_{{\bf R}/{\bf Z}},\dots,\|tv_n\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}}$ where ${\|x\|_{{\bf R}/{\bf Z}}}$ denotes the distance of ${x}$ to the nearest integer.

This conjecture has been proven for ${n \leq 7}$ , but remains open for larger ${n}$ . The bound ${\frac{1}{n+1}}$ is optimal, as can be seen by looking at the case ${v_i=i}$ and applying the Dirichlet approximation theorem. Note that for each non-zero ${v}$ , the set ${\{ t \in {\bf R}: \|vt\|_{{\bf R}/{\bf Z}} \leq r \}}$ has (Banach) density ${2r}$ for any ${0 < r < 1/2}$ , and from this and the union bound we can easily find ${t \in {\bf R}}$ for which

$\displaystyle \|tv_1\|_{{\bf R}/{\bf Z}},\dots,\|tv_n\|_{{\bf R}/{\bf Z}} \geq \frac{1}{2n}-\varepsilon$

for any ${\varepsilon>0}$ , but it has proven to be quite challenging to remove the factor of ${2}$ to increase ${\frac{1}{2n}}$ to ${\frac{1}{n+1}}$ . (As far as I know, even improving ${\frac{1}{2n}}$ to ${\frac{1+c}{2n}}$ for some absolute constant ${c>0}$ and sufficiently large ${n}$ remains open.)

The speeds ${v_1,\dots,v_n}$ 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 ${v_1,\dots,v_n}$ 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 ${v_1,\dots,v_n}$ are integers of bounded size, where the bound depends on ${n}$ . More precisely:

Proposition 3 In order to prove the lonely runner conjecture, it suffices to do so under the additional assumption that the ${v_1,\dots,v_n}$ are integers of size at most ${n^{Cn^2}}$ , where ${C}$ is an (explicitly computable) absolute constant. (More precisely: if this restricted version of the lonely runner conjecture is true for all ${n \leq n_0}$ , then the original version of the conjecture is also true for all ${n \leq n_0}$ .)

In principle, this proposition allows one to verify the lonely runner conjecture for a given ${n}$ in finite time; however the number of cases to check with this proposition grows faster than exponentially in ${n}$ , and so this is unfortunately not a feasible approach to verifying the lonely runner conjecture for more values of ${n}$ 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 ${GAP}$ ) in the reals ${{\bf R}}$ is a set of the form

$\displaystyle P = \{ n_1 v_1 + \dots + n_d v_d: n_1,\dots,n_d \in {\bf Z}; |n_1| \leq N_1, \dots, |n_d| \leq N_d \}$

for some ${v_1,\dots,v_d \in {\bf R}}$ and ${N_1,\dots,N_d > 0}$ ; the quantity ${d}$ is called the rank of the progression. If ${t>0}$ , the progression ${P}$ is said to be ${t}$ -proper if the sums ${n_1 v_1 + \dots + n_d v_d}$ with ${|n_i| \leq t N_i}$ for ${i=1,\dots,d}$ are all distinct. We have

Lemma 4 (Progressions lie inside proper progressions) Let ${P}$ be a GAP of rank ${d}$ in the reals, and let ${t \geq 1}$ . Then ${P}$ is contained in a ${t}$ -proper GAP ${Q}$ of rank at most ${d}$ , with

$\displaystyle |Q| \leq (2t)^d d^{6d^2} \prod_{i=1}^d (2N_i+1).$

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.) $\Box$

Now let ${n \geq 1}$ , and assume inductively that the lonely runner conjecture has been proven for all smaller values of ${n}$ , as well as for the current value of ${n}$ in the case that ${v_1,\dots,v_n}$ are integers of size at most ${n^{Cn^2}}$ for some sufficiently large ${C}$ . We will show that the lonely runner conjecture holds in general for this choice of ${n}$ .

let ${v_1,\dots,v_n}$ be non-zero real numbers. Let ${C_0}$ be a large absolute constant to be chosen later. From the above lemma applied to the GAP ${\{ n_1 v_1 + \dots + n_d v_d: n_1,\dots,n_d \in \{-1,0,1\}\}}$ , one can find a ${n^{C_0n}}$ -proper GAP ${Q}$ of rank at most ${n}$ containing ${\{v_1,\dots,v_n\}}$ such that

$\displaystyle |Q| \leq (6n^{C_0 n})^n n^{6n^2};$

in particular ${|Q| \leq n^{Cn^2}}$ if ${C}$ is large enough depending on ${C_0}$ .

We write

$\displaystyle Q = \{ n_1 w_1 + \dots + n_d w_d: n_1,\dots,n_d \in {\bf Z}; |n_1| \leq N_1,\dots,|n_d| \leq N_d \}$

for some ${d \leq n}$ , ${w_1,\dots,w_d}$ , and ${N_1,\dots,N_d \geq 0}$ . We thus have ${v_i = \phi(a_i)}$ for ${i=1,\dots,n}$ , where ${\phi: {\bf R}^d \rightarrow {\bf R}}$ is the linear map ${\phi(n_1,\dots,n_d) := n_1 w_1 + \dots + n_d w_d}$ and ${a_1,\dots,a_n \in {\bf Z}^d}$ are non-zero and lie in the box ${\{ (n_1,\dots,n_d) \in {\bf R}^d: |n_1| \leq N_1,\dots,|n_d| \leq N_d \}}$ .

We now need an elementary lemma that allows us to create a “collision” between two of the ${a_1,\dots,a_n}$ via a linear projection, without making any of the ${a_i}$ collide with the origin:

Lemma 5 Let ${a_1,\dots,a_n \in {\bf R}^d}$ be non-zero vectors that are not all collinear with the origin. Then, after replacing one or more of the ${a_i}$ with their negatives ${-a_i}$ if necessary, there exists a pair ${a_i,a_j}$ such that ${a_i-a_j \neq 0}$ , and such that none of the ${a_1,\dots,a_n}$ is a scalar multiple of ${a_i-a_j}$ .

Proof: We may assume that ${d \geq 2}$ , since the ${d \leq 1}$ case is vacuous. Applying a generic linear projection to ${{\bf R}^2}$ (which does not affect collinearity, or the property that a given ${a_k}$ is a scalar multiple of ${a_i-a_j}$ ), we may then reduce to the case ${d=2}$ .

By a rotation and relabeling, we may assume that ${a_1}$ lies on the negative ${x}$ -axis; by flipping signs as necessary we may then assume that all of the ${a_2,\dots,a_n}$ lie in the closed right half-plane. As the ${a_i}$ are not all collinear with the origin, one of the ${a_i}$ lies off of the ${x}$ -axis, by relabeling, we may assume that ${a_2}$ lies off of the ${x}$ axis and makes a minimal angle with the ${x}$ -axis. Then the angle of ${a_2-a_1}$ with the ${x}$ -axis is non-zero but smaller than any non-zero angle that any of the ${a_i}$ make with this axis, and so none of the ${a_i}$ are a scalar multiple of ${a_2-a_1}$ , and the claim follows. $\Box$

We now return to the proof of the proposition. If the ${a_1,\dots,a_n}$ are all collinear with the origin, then ${\phi(a_1),\dots,\phi(a_n)}$ lie in a one-dimensional arithmetic progression ${\{ mv: |m| \leq |Q| \}}$ , and then by rescaling we may take the ${v_1,\dots,v_n}$ to be integers of magnitude at most ${|Q| \leq n^{Cn}}$ , at which point we are done by hypothesis. Thus, we may assume that the ${a_1,\dots,a_n}$ are not all collinear with the origin, and so by the above lemma and relabeling we may assume that ${a_n-a_1}$ is non-zero, and that none of the ${a_i}$ are scalar multiples of ${a_n-a_1}$ .

We write

$\displaystyle a_n-a_1 = (c_1,\dots,c_d) \ \ \ \ \ (1)$

with ${|c_i| \leq 2 N_i}$ for ${i=1,\dots,d}$ ; by relabeling we may assume without loss of generality that ${c_d}$ is non-zero, and furthermore that

$\displaystyle \frac{|c_i|}{N_i} \leq \frac{|c_d|}{N_d}$

for ${i=1,\dots,d}$ . We can also factor

$\displaystyle (c_1,\dots,c_d) = q (c'_1,\dots,c'_d) \ \ \ \ \ (2)$

where ${q}$ is a natural number and ${c'_1,\dots,c'_d}$ have no common factor.

We now define a variant ${\tilde \phi: {\bf R}^d \rightarrow {\bf R}}$ of ${\phi: {\bf R}^d \rightarrow {\bf R}}$ by the map

$\displaystyle \tilde \phi(n_1,\dots,n_d) := n_1 \tilde w_1 + \dots + n_{d-1} \tilde w_{d-1} - \frac{n_d}{c_d} (c_1 \tilde w_1 + \dots + c_{d-1} \tilde w_{d-1}),$

where the ${\tilde w_1,\dots,\tilde w_{d-1}}$ are real numbers that are linearly independent over ${{\bf Q}}$ , whose precise value will not be of importance in our argument. This is a linear map with the property that ${\tilde \phi(a_n-a_1)=0}$ , so that ${\tilde \phi(a_1),\dots,\tilde \phi(a_n)}$ consists of at most ${n-1}$ distinct real numbers, which are non-zero since none of the ${a_i}$ are scalar multiples of ${a_n-a_1}$ , and the ${\tilde w_i}$ are linearly independent over ${{\bf Q}}$ . As we are assuming inductively that the lonely runner conjecture holds for ${n-1}$ , we conclude (after deleting duplicates) that there exists at least one real number ${\tilde t}$ such that

$\displaystyle \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n}.$

We would like to “approximate” ${\phi}$ by ${\tilde \phi}$ to then conclude that there is at least one real number ${t}$ such that

$\displaystyle \| t \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| t \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}.$

It turns out that we can do this by a Fourier-analytic argument taking advantage of the ${n^{C_0 n}}$ -proper nature of ${Q}$ . Firstly, we see from the Dirichlet approximation theorem that one has

$\displaystyle \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \leq \frac{1}{10 n^2}$

for a set ${\tilde t}$ of reals of (Banach) density ${\gg n^{-O(n)}}$ . Thus, by the triangle inequality, we have

$\displaystyle \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n} - \frac{1}{10n^2}$

for a set ${\tilde t}$ of reals of density ${\gg n^{-O(n)}}$ .

Applying a smooth Fourier multiplier of Littlewood-Paley type, one can find a trigonometric polynomial

$\displaystyle \eta(x) = \sum_{m: |m| \leq n^{C_0 n/10}} b_m e^{2\pi i mx}$

which takes values in ${[0,1]}$ , is ${\gg 1}$ for ${\|x\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n} - \frac{1}{10n^2}}$ , and is no larger than ${O( n^{-100 C_0n} )}$ for ${\|x\|_{{\bf R}/{\bf Z}} \leq \frac{1}{n+1}}$ . We then have

$\displaystyle \mathop{\bf E}_t \prod_{j=1}^n \eta( t \tilde \phi(a_j) ) \gg n^{-O(n)}$

where ${\mathop{\bf E}_t f(t)}$ denotes the mean value of a quasiperiodic function ${f}$ on the reals ${{\bf R}}$ . We expand the left-hand side out as

$\displaystyle \sum_{m_1,\dots,m_n: m_1 \tilde \phi(a_1) + \dots + m_n \tilde \phi(a_n) = 0} b_{m_1} \dots b_{m_n}.$

From the genericity of ${\tilde w_1,\dots,\tilde w_n}$ , we see that the constraint

$\displaystyle m_1 \tilde \phi(a_1) + \dots + m_n \tilde \phi(a_n) = 0$

occurs if and only if ${m_1 a_1 + \dots + m_n a_n}$ is a scalar multiple of ${a_n-a_1}$ , or equivalently (by (1), (2)) an integer multiple of ${(c'_1,\dots,c'_d)}$ . Thus

$\displaystyle \sum_{m_1,\dots,m_n: m_1 a_1 + \dots + m_n a_n \in {\bf Z} (c'_1,\dots,c'_d)} b_{m_1} \dots b_{m_n} \gg n^{-O(n)}. \ \ \ \ \ (3)$

Next, we consider the average

$\displaystyle \mathop{\bf E}_t \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \ \ \ \ \ (4)$

where

$\displaystyle \xi := c'_1 w_1 + \dots + c'_d w_d. \ \ \ \ \ (5)$

and ${\varphi}$ is the Dirichlet series

$\displaystyle \varphi(x) := \sum_{m: |m| \leq n^{C_0 n/2}} e^{2\pi i mx}.$

By Fourier expansion and writing ${v_j = \phi(a_j)}$ , we may write (4) as

$\displaystyle \sum_{m,m_1,\dots,m_n: |m| \leq n^{C_0n/2}; m_1 \phi(a_1) + \dots + m_n \phi(a_n) = m \xi} b_{m_1} \dots b_{m_n}.$

The support of the ${b_{m_i}}$ implies that ${|m_i| \leq n^{C_0n/10}}$ . Because of the ${n^{C_0 n}}$ -properness of ${Q}$ , we see (for ${n}$ large enough) that the equation

$\displaystyle m_1 \phi(a_1) + \dots + m_n \phi(a_n) = m \xi \ \ \ \ \ (6)$

implies that

$\displaystyle m_1 a_1 + \dots + m_n a_n \in {\bf Z} (c'_1,\dots,c'_d) \ \ \ \ \ (7)$

and conversely that (7) implies that (6) holds for some ${m}$ with ${|m| \leq n^{C_0 n/2}}$ . From (3) we thus have

$\displaystyle \mathop{\bf E}_t \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \gg n^{-O(1)}.$

In particular, there exists a ${t}$ such that

$\displaystyle \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \gg n^{-O(1)}.$

Since ${\varphi}$ is bounded in magnitude by ${n^{C_0n/2}}$ , and ${\eta}$ is bounded by ${1}$ , we thus have

$\displaystyle \eta(t v_j) \gg n^{-C_0 n/2 - O(1)}$

for each ${1 \leq j \leq n}$ , which by the size properties of ${\eta}$ implies that ${\|tv_j\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}}$ for all ${1 \leq j \leq n}$ , giving the lonely runner conjecture for ${n}$ .

58 comments

Comments feed for this article

13 May, 2015 at 10:27 pm

domotorp

I’m in a hurry, but we have also investigated results similar to Lemma 4: http://arxiv.org/abs/0912.0424. One can show that a single exponential bound in d is not sufficient using this result of Alon and Vu: http://www.math.tau.ac.il/~nogaa/PDFS/av1.pdf.

14 May, 2015 at 8:54 pm

domotorp

I’m sorry, now after taking a proper look, our results seem unrelated, they just contain similar words and bounds.

14 May, 2015 at 1:24 am

Anonymous

In conjecture 2, it seems that “the origin” should be “the integers”.

[Corrected, thanks – T.]

14 May, 2015 at 4:42 am

Bogdan

You proved that if the conjecture is false for a given n, then it false for SOME v_1, …, v_n of size n^(Cn^2). Can similar methods to be extended to prove a stronger result, that if the conjecture is false for a given n, then it false for MANY v_1, …, v_n of size n^(Cn^2), say, for a positive proportion (independent of n) of all tuples v_1, …, v_n of this size. Then, for the first unproved case n=8, we could check the conjecture for some RANDOM tuples bouded by 8^64C (if C is not too lagre), and, if true, confirm the original conjecture for n=8, with probability, arbitrary closed to 1.

14 May, 2015 at 10:28 am

Terence Tao

One can certainly establish the conjecture for “most” choices of $v_1,\dots,v_n$ ; for instance, if the $v_1,\dots,v_n$ are linearly independent over ${\bf Q}$ (which occurs for almost every choice of reals $v_1,\dots,v_n$ ), then the $\|tv_i\|_{{\bf R}/{\bf Z}}$ behave as independent random variables and the claim is quite easy to show in this case. However, all of the difficulty of the problem is concentrated in “special” choices of $v_1,\dots,v_n$ , and knowing that the conjecture is true for “most” choices doesn’t make much impact on this most difficult case. (An analogy is with Fermat’s last theorem: it is easy to show that the equation $a^n+b^n=c^n$ is false for “most” choices of $a,b,c,n$, for just about any notion of “most”, but this does not really make a dent in solving the problem.)

15 May, 2015 at 2:22 am

Bogdan

You completely misundersood my comment :) I wil try again.
Your theorem is: If there is at least one counterexample for ANY v_1, …, v_n, then there is at least ONE counterexample for bounded v_1, …, v_n.
Now, assume we have a stronger result, namely:
Statement A: If there is at least one counterexample for any v_1, …, v_n, then positive proportion of ALL bounded v_1, …, v_n are all counterexamples.
Then, trying at random, we could rule out a possibility that positive proportion of ALL bounded v_1, …, v_n are all counterexamples, and
use statement A to prove the result in full.

Example how this may work.

Statement B: If there is at least one counterexample N to odd Goldbach’s conjecture, then at least N/log N even numbers in the region from 2 to N are ALL counterexamples to even Goldbach’s conjecture.

Proof is trivial. If N is a counterexample to odd Goldbach’s conjecture, then N-p is a counterexample to the even Goldbach’s conjecture for any odd p less than N.

Now, we can check even Goldbach’s conjecture for sufficiently many random numbers below exp(3100), and the odd Goldbach’s conjecture for numbers below exp(3100) follows from statement B. See https://rjlipton.wordpress.com/2014/06/06/is-this-a-proof-2/ for a variant of this argument.

15 May, 2015 at 7:25 am

Terence Tao

Ah, I see what you are saying now. I doubt that this sort of “counterexample dispersion” effect is present in this problem; roughly speaking, the only symmetry we have available in this problem to convert one counterexample into many counterexamples are Freiman homomorphisms. (There is a technicality here in that there is some loss in the lower bound on runner separation every time one applies such a homomorphism, based on the quality of that homomorphism, but let me ignore this technicality for sake of current discussions.) There are enough homomorphisms present to “rectify” any finite set of speeds into a set of bounded integers, but not enough to obtain a positive proportion of such sets. As mentioned in my previous comment, for randomly selected sets of speeds (which all lie, more or less, in a single Freiman isomorphism class) the claim is trivial to prove, but this does not have much bearing on all the other Freiman isomorphism classes (and if the conjecture is to fail, it is likely to come from a very special, carefully constructed, Freiman isomorphism class, which will not be detectable by random search).

14 May, 2015 at 6:39 am

Anonymous

It seems that the (closely related) Littlewood conjecture complements this conjecture for $n=2$ (where $t$ is constrained to be an integer.)

15 May, 2015 at 12:21 am

Anonymous

Correction: In conjecture 1 (to be exactly equivalent to conjecture 2), it seems that “different speeds” should be interpreted as “there is at least one runner whose speed is different from the speeds of the other runners”.

[The formulations are equivalent, as can be seen by replacing multiple runners with the same speed with a single runner of that speed. -T.]

15 May, 2015 at 8:05 am

Anonymous

The simple identity $\sin (\pi || x ||) = | \sin (\pi x)|$ implies that conjecture 2 has the following analytic formulation

$\max_{t \in \mathbb R} \min_{1\leq j \leq n} |sin(\pi t v_j)| \geq \sin \frac {\pi}{n+1}$

It is easy to verify that the (outer) maximum is attained at an intersection point of two sine curves (with corresponding velocities $v_i, v_j$ ), i.e.

$|\sin (\pi t v_i)| = |\sin(\pi t v_j)|$ for some $v_i, v_j$

Implying that $t$ is rational (a multiple of $1/(v_i - v_j)$ or $1/(v_i + v_j)$ ).

Therefore (without loss of generality) $t$ may be assumed to be rational (with denominator being the sum or difference of two integer velocities).

15 May, 2015 at 3:01 pm

arch1

Is Conjecture 2 equivalent to asking whether one can see infinitely far from the origin in an n-space occupied by opaque n-cubes of side length (n-1)/(n+1) centered at half-integer coordinates?

..and no fair peeking down a coordinate axis:-)

17 May, 2015 at 12:15 am

Terence Tao

Yes; indeed, the original literature on the lonely runner conjecture was motivated by such “view-obstruction” formulations of the problem.

17 May, 2015 at 9:06 am

arch1

Thanks. As a layperson this motivates me to try understand more of this posting. At first blush, it’s very surprising to me that such a basic view obstruction question, in such an apparently simple, symmetrical, static setting, is so hard.

16 May, 2015 at 9:18 am

Drive by shooting

Would you buy this argument?

We can generalize the $n$ velocities to be arbitrary real numbers, for example by choosing a frame of reference traveling with an arbitrary runner. The system then satisfies the constraints of the Poincare recurrence theorem, for the $n$ positions, and the $n$ velocities. But any group of $n-1$ runners must then also fulfill the constraints of the Poincare recurrence theorem. Thus, fix a reference frame to an arbitrary runner, and consider a volume of the position space of the remaining $n-1$ runners, of length $\epsilon \in (0, \frac{1}{2})$ for each of the $n-1$ runners, and exactly opposite to the origin of the chosen runner. By the Poincare recurrence theorem the $n-1$ runners must revisit this volume infinitely often. We then have for any $\epsilon \in (0, \frac{1}{2})$ each runner is separated from all the other runners by that amount infinitely often.

17 May, 2015 at 12:15 am

Terence Tao

In order to apply the Poincare recurrence theorem, the region of space considered must be visited at least once before one can conclude that it is visited infinitely often. (With stronger hypotheses on the dynamical system, such as minimality, one does not need this additional hypothesis, however the system will only be minimal in the easy case when the relative velocities are linearly independent over the rationals.)

17 May, 2015 at 1:42 am

James Smith

A small thing that confused me: you say in your definition of the problem that all the runners start at the origin. To say they start at the same place might be a little clearer. And I wonder now I come to think of it if the circle were indeed replaced with a disc how the problem would unfold.

[ ${\mathbf R}/{\mathbf Z}$ denotes the additive unit circle, rather than the multiplicative (or geometric) unit circle $S^1$ – one can think of it as the geometric unit circle transformed by a logarithmic change of variables. In particular, the identity element 1 of the multiplicative unit circle becomes the identity element 0 of the additive unit circle. -T.]

17 May, 2015 at 1:18 pm

James Smith

I never made the distinction before. Thanks for clearing it up!

17 May, 2015 at 7:33 pm

victor

What if the velocities are random, ie, the velocity of the $i$th runner is $v_0 \exp( \mu t + \sigma B^i_t)$ where $B^i_t$ is standard Brownian Motion and is independent across the runners? The deterministic problem is the limiting case where $\mu = 0$ and $\sigma= \infty$. Would it make sense to solve the stochastic problem first?

18 May, 2015 at 9:14 am

Terence Tao

This is an irreducible Markov process (where the state space tracks both position and velocity) and so the stochastic runners will almost surely traverse a dense set of states, which amongst other things establishes the lonely runner property for such a set of runners. The difficulty in this conjecture lies not with such “generic” situations, but rather with very special “arithmetically structured” situations in which the runner velocities all have a rigid relationship with each other (e.g. they are all rational multiples of each other with small height).

18 May, 2015 at 9:22 am

victor

Thanks for clarifying Prof Tao.

27 October, 2015 at 6:23 am

Antoine

Hello, with all my respect, Dr. Tao, your point of the optimal $\dfrac{1}{n+1}$ and relation to the Dirichlet approximation theorem. well i haven’t seen that, from the stated theorem at wiki, $v_i$ is what precisely in the theorem? thanks.

[The $v_i$ would correspond to the “ $q$ ” in the Wikipedia formulation of the theorem (and the time $t$ would correspond to $\alpha$ , and $n$ to $N$ ). -T]</I<

20 November, 2015 at 3:37 am

Antoine

Thanks sorry i didn’t expect a reply!, anyway the $q$ depends on $\alpha $ in the theorem no, so for a fixed $q$ maybe there exist $\alpha$ such that the less or equal is bigger or equal, did i miss something? t.y.

20 November, 2015 at 3:39 am

Antoine

No Tex sorry.

20 November, 2015 at 8:36 am

Terence Tao

The Dirichlet approximation theorem (with the substitutions indicated) tells us that for any real $t$ , there exists a $q$ between $1$ and $n$ (depending on $t$ ) such that $\| qt\|_{{\bf R}/{\bf Z}} \leq \frac{1}{n+1}$ . Setting $v_q := q$ for $q = 1,\dots, n$ , we conclude that Conjecture 2 fails if the quantity $1/(n+1)$ is replaced by any smaller quantity.

20 November, 2015 at 8:47 am

Anonymous

Thank you.

19 December, 2015 at 8:20 am

Antoine

Thanks

12 January, 2016 at 12:08 pm

Elliott

Prof. Tao, can’t the bound 1/(n+1) be seen to be optimal without referring to the Dirichlet approximation theorem? For speeds 1,…,n let t = 1/(n+1). Then ||1/(n+1)|| and ||n/(n+1)|| both equal 1/(n+1).

12 January, 2016 at 4:16 pm

Terence Tao

This doesn’t immediately preclude Conjecture 2 holding with 1/(n+1) replaced by a larger bound, because there could be a different value of t (other than t = 1/(n+1)) in which the numbers t, 2t, …, nt are further away from the origin than in your example. (But this scenario is ruled out by the Dirichlet approximation theorem.)

25 April, 2019 at 2:52 am

Stephen Mc Guire

Dirichlet’s theorem tells us that $|| qt||_{\mathbf{R}/\mathbf{Z}} \leq \frac{1}{n}$ not that $|| qt||_{\mathbf{R}/\mathbf{Z}} \leq \frac{1}{n+1}$ . So we can, at best, conclude that all runners are within $\frac{1}{n}$ of the lonely runner i.e. the runner stationary at 0. Perhaps I’m misunderstanding something?

26 April, 2019 at 1:32 pm

Terence Tao

The Dirichlet approximation theorem does indeed show that $\inf_{1 \leq q \leq n} \|qt\|_{{\bf R}/{\bf Z}} \leq \frac{1}{n+1}$ for all $t$ and all natural numbers $n \geq 1$ . (For some reason the Wikipedia entry only gives the weaker estimate $\inf_{1 \leq q \leq n} \|qt\|_{{\bf R}/{\bf Z}} < \frac{1}{n}$ , but the stronger bound is what actually comes out of carefully optimising the proof, and in particular observing that some pair amongst $0, t, 2t, \dots, n t$ must be at a distance at most $\frac{1}{n+1}$ from each other.)

20 November, 2015 at 12:14 am

koza3301

Could you explain how to prove that “ $\displaystyle \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n} - \frac{1}{10n^2}$ for a set ${\tilde t}$ of reals of (Banach) density ${\gg n^{-O(n)}}$ ” from the Dirichlet approximation theorem?

20 November, 2015 at 8:35 am

Terence Tao

Cover the n-torus by $O(n^{O(n)})$ boxes of sidelength $1/20n^2$ . By the Dirichlet box principle (pigeonhole principle), one of these boxes will contain $(\tilde t \tilde \phi(a_1), \dots, \tilde t \phi(a_n))$ for a set of $\tilde t$ of positive density. Now subtract to get the claim. (This argument is identical to the one used to prove the usual Dirichlet approximation theorem. There are some technical issues regarding the nature of density used here, but by using some equidistribution theory one can show that all the usual notions of density (lower Banach, upper Banach, etc.) agree for the sets in question.)

20 November, 2015 at 8:43 am

koza3301

Thanks :)

19 December, 2015 at 8:32 am

Antoine

Hi, I’ve got another question Prof. Tao if no bother; a result such as: their exist infinite times when say the $k$ runners are all distant from each other by at least $a\dfrac{1}{k}$ with $a$ less than $1,$ can be bigger than $\dfrac{1}{2}$ and it depends on the speed of the $k$ runners, Where it stands on a crowded scale for this problem, thanks all respect.

23 March, 2016 at 9:53 pm

David R

What do you think of this argument Prof. Tao? Suppose we use the following three lemmas to prove the slowest runner $j$ becomes lonely:

Lemma 1: Let $s_j < s_1 < \ldots < s_{k - 1}$ for $k \geq 3$ . Then $j$ becomes lonely if and only if there exists $n_1, n_2, \ldots n_{k - 1} \in \mathbb{N}$ such that $\bigcap_{i = 1}^{k - 1} \bigg [\frac{n_i + \frac{1}{k}}{s_i - s_j}, \frac{n_i + \frac{k - 1}{k}}{s_i - s_j}\bigg ] \neq \emptyset$

Proof:: Straightforward in both directions.

Lemma 2: Let $a_i, b_i \in \mathbb{R}$ and $a_i < b_i$ . Then $\bigcap_{i = 1}^{k} [a_i, b_i] \neq \emptyset$ if and only if $b_i \geq a_i$ for all $1 \leq i,j \leq k, j \neq i$ ..

Proof: ( $\Rightarrow$ ). Proof by contradiction.
( $\Leftarrow$ ). Proof by contrapositive.

Lemma 3: Let $s_j < s_1 < \ldots < s_{k - 1}$ for $k \geq 3$ .Then there exists $n_1, n_2, \ldots n_{k - 1} \in \mathbb{N}$ such that

$\frac{s_m - s_j}{s_i - s_j} \ge \frac{kn_m + 1}{kn_i + k - 1}$

for $1 \le i, m \le k - 1$ , $m \ne i$ .

Proof: Try a proof by induction. Proving the base case $P(3)$ follows easily from the fact that the LRC has been proven for $k =3$ . Proving that $P(k) \Rightarrow P(k + 1)$ looks to be quite difficult though.

We can then make the following argument:

Theorem 1: Let $s_j < s_1 < s_2 < \ldots < s_{k - 1}, k\ge 3$ . Then $j$ becomes lonely.

Proof: By Lemma 3, there exists $n_1, n_2, \ldots n_{k - 1} \in \mathbb{N}$ such that

$\frac{s_m - s_j}{s_i - s_j} \ge \frac{kn_m + 1}{kn_i + k - 1}$

for all $1 \le i, m \le k - 1$ , $m \ne i$ . Hence, there exists $n_1, n_2, \ldots n_{k - 1} \in \mathbb{N}$ such that

$\frac{n_i + \frac{k - 1}{k}}{s_i - s_j} \geq \frac{n_m + \frac{1}{k}}{s_m - s_j}$

for all $1 \le i, m \le k - 1$ , $m \ne i$ . By setting

$a_i = \frac{n_i + \frac{1}{k}}{s_i - s_j}, b_i = \frac{n_i + \frac{k - 1}{k}}{s_i - s_j}$

and because $b_i \geq a_m$ for $1 \leq i, m \leq k - 1, i \ne m$ we have from Lemma 2,

$\bigcap_{i = 1}^{k - 1} \bigg [\frac{n_i + \frac{1}{k}}{s_i - s_j}, \frac{n_i + \frac{k - 1}{k}}{s_i - s_j}\bigg ] \neq \emptyset$ .

By Lemma 1, $j$ becomes lonely for all T in the intersection.

The thing that’s interesting about this argument is that if we can prove Lemma 3, then we can repeat essentially the same argument to prove that runners with some intermediate speed as well as runners with the fastest speed become lonely. The argument for proving that the fastest runner becomes lonely would be almost identical to the argument for the slowest runner.

7 June, 2016 at 5:48 am

Klaus85

Dear Terry, I have just found this arxiv-paper (http://arxiv.org/abs/1606.01783) claiming to proof the lonely-runner conjecture. It is the highest-rated paper of today on scirate, thus i thought it might be serios; but i would love to hear more details by an expert. Does it investigate the same question as mentioned here, or is it a weaker variation? Thanks so much!

7 June, 2016 at 4:33 pm

Terence Tao

The paper has been withdrawn due to an error on the last line.

7 June, 2016 at 4:58 pm

anthonyquas

Can you say in more detail where the error was?

7 June, 2016 at 5:38 pm

Terence Tao

The final inequality is not true in the $n=0$ case.

7 June, 2016 at 8:50 pm

David Lui

do you think this is an easily fixable problem, or would it require significant effort to fix, or is the proof outright wrong?

8 June, 2016 at 8:22 am

Terence Tao

Probably the author is the best person to answer this. But one test can come from the observation that the lonely runner conjecture is only barely true in the case $v_i=i$ (as pointed out in above in the blog post) or permutations or affine transformations thereof. As such, any proof of the lonely runner conjecture should also only barely work in this case (in particular, any key inequality in the proof should hold with equality in this case). This did not seem to be the case in this most recent attempt to prove the conjecture, which suggests at minimum that a significant modification of the argument would be required.

7 June, 2016 at 4:31 pm

anthonyquas

I have read through the Beck paper once without finding any problems in it. It does indeed address the full Lonely Runner Conjecture as described in this blog post. I am about to re-read.

7 June, 2016 at 8:41 pm

Curious Party

What time was the mistake found? A wager was placed on this result being false.

7 June, 2016 at 11:07 pm

Mike Miller

I find this to be in extremely poor taste.

8 June, 2016 at 7:42 am

David Lui

is it asking when it was found, or the wager part that you find to be in poor taste?

8 June, 2016 at 2:38 pm

Classy Mofo

Perhaps it is your own taste that is poor?

29 August, 2016 at 2:52 am

giorgi

Hello terence tao. (1,2…m-1 and i are indexes ) i just proof what conjecture is equivalent to this conjecture (i mean if we proof “”this” then lonely runner conjecture is true too): q1, q2, …qm-1 is any positive numbers , if q1, q2, …qm-1
we can Multiplicate some number k (k>0) and get this type of similar proportion numbers: C1+N1, C2+N2 , …. Cm-1+Nm-1 , were Ci are numbers between 1/m<=Ci<=(m-1)/m and Ni are natural numbers then "lonely runner" is true too. what you think about it?

p.s. im just lover of mathematics and sorry for my english and "latex"

7 September, 2016 at 8:44 am

একেলা দৌড়বিদের কনজেকচার (The Lonely Runner Conjecture) - বিজ্ঞান স্কুল

[…] আরও পড়ার জন্য দেখতে পারেন এখানে https://terrytao.wordpress.com/2015/05/13/a-remark-on-the-lonely-runner-conjecture/ […]

10 January, 2017 at 1:40 pm

Some remarks on the lonely runner conjecture | What's new

[…] 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 […]

22 October, 2018 at 11:30 am

dsp

This will probably turn out to be a very stupid question, but anyway: I have been thinking about what happens when you replace the Euclidean distance in the lonely runner conjecture with the p-adic one, i. e., what can one say about the set of vectors of distances $(|(e^{\pi i v_1})^t - 1|_p, \dots, |(e^{\pi i v_n})^t - 1|_p)$ , where $v_1,\dots,v_n$ are fixed rational numbers, $t$ ranges over $\mathbb{R}$ and $|x|_p$ denotes the p-adic absolute value of $x$ ? I’ve come up with something I can’t understand. I guess my (as I said, probably stupid) question boils down to this:

1) For an algebraic number $x$ , the product of all the p-adic absolute values of $x$ equals $\frac{1}{|x|}$ .

2) For any $p,x,y$ , $|x+y|_p \leq \max (|x|_p,|y|_p)$

So if $n$ is a sufficiently large positive integer, since the Euclidean distance between, say, 1 and $e^{\frac{\pi i}{n}}$ is smaller than 1, for at least one $p$ , we must have that the p-adic distance between the two numbers is $> 1$ by 1). But by 2), this distance is at most $\max (|1|_p,|e^{\frac{\pi i}{n}}|_p)$ , and $|e^{\frac{\pi i}{n}}|_p = 1$ since it is a root of unity.

I hope this isn’t too far off topic.

24 October, 2018 at 9:40 am

Terence Tao

I’m not sure one can make sense p-adically of $(e^{\pi i v_n})^t$ if $t$ is real, since $(e^{\pi i v_n})^t$ will then in general just be a transcendental complex number. However, there is some work on studying function field analogues of the lonely runner conjecture which you may be interested in: https://arxiv.org/abs/1711.01207

1 December, 2019 at 5:17 am

Florent L. B. Périat

Hi, Prof. Tao, I found one iterative algorithm which seems to make the times for the different runners to be lonely converge. So proving its completeness, would also proves the conjecture ? But, the program does not always converge to a solution, especially when the speeds are only integers. Would a kind of ghost decimal speed value that does not increment k help ?

PS : Sorry for my English

29 December, 2021 at 11:11 pm

Aditya Guha Roy

Prof. Tao are you aware of any literature where the authors have tried to approach this problem probabilistically.
(This problem seems to scream “use probability” in my ears, but that might be due to my lack of experience in mathematics or my obsession with probability.)

29 December, 2021 at 11:15 pm

Aditya Guha Roy

Reblogged this on Aditya Guha Roy's weblog.

7 November, 2022 at 12:42 am

martin

Has the opposite problem been considered in the literature (or elsewhere)? I would be interested whether ALL runners need to be close (how close?) to the integers at some point in time. Obviously we would need to remove the condition of start at the origin at t=0.

8 November, 2022 at 1:28 am

martin

Oh I see this is in a sense equivalent to the original problem because close to the integers means far away from the half-integers.
However for the removal of the start condition I did not find anything except a comment by Wills to a 2012 talk in Siegen by Goddyn that maybe Hans-Gill or Dumir did work on this. So the question still stands: what about removing the start condition – is there some literature?

9 November, 2022 at 1:43 am

martin

After more search, there is https://arxiv.org/abs/2009.12080 which calls the generalization the “shifted lonely runner conjecture” and proves it for 4 runners (i.e one stationary and n=3 non-stationary ones).

7 November, 2022 at 12:21 pm

Anonymous

Is it possible to show that that the conjecture is true for “almost every runners velocities” (in some sense) the conjecture is true?

	Anonymous on Erratum for “An inverse…
	Anonymous on Pointwise ergodic theorems for…
	Anonymous on 275A, Notes 3: The weak and st…
	Terence Tao on Pointwise ergodic theorems for…
	Terence Tao on Erratum for “An inverse…
	Anonymous on Notes on the B+B+t theore…
	Anonymous on Pointwise ergodic theorems for…
	Anonymous on Erratum for “An inverse…
	Erratum for “A… on An inverse theorem for the Gow…
	Anonymous on Analysis II
	Anonymous on Notes on the B+B+t theore…
	Anonymous on Twisted convolution and the se…
	Anonymous on A generalized Cauchy-Schwarz i…
	Notes on the B+B+t t… on Ultrafilters, nonstandard anal…
	Notes on the B+B+t t… on Soft analysis, hard analysis,…

A remark on the lonely runner conjecture

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

58 comments

Leave a comment Cancel reply

For commenters

A remark on the lonely runner conjecture

Share this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

58 comments

Leave a comment Cancel reply

For commenters