Anyone interested in improving the state-of-the-art result for the lonely runner conjecture?

Lonely runner conjecture states that if k+1 runners start a race running on a circle of unit length with distinct speeds v_1, v_2, ..., v_{k+1} then for each index i there exists time t such that at time t the i-th runner is at least 1/(k+1) far away from all other runners. By substracting the speed of the i-th runner this can be formulated as:

Given non-zero real numbers v_1, ..., v_k there exists t such that t*v_j is at least 1/(k+1) far away from any integer for all j.

This conjecture remains wide open but it was resolved for 2, 3, 4, 5, 6, 7, and, very recently, for 8 runner. The result for 8 runners is in [1]. Here is the outline of the proof:

First, if speeds are just some generic real numbers, then conjecture is easy since one can ensure that all runners have fractional part close to 1/2 simultaneously. Thinking about this carefully one ends up showing that one only needs to show this conjecture for rational speeds which we can then scale to get integer speeds. Moreover, if speeds are super large, then we can sort of treat them as generic reals easily solving the problem again. This line of thoughts leads to the claim that the Lonely runner conjecture for n runners is true as long it is true for integer speeds not exceeding some value f(n). Doing this more carefully leads to a n^{Cn^2} bound, see this post by Terry Tao [2]. This was subsequently improved and made explicit with the bound (roughly for the sum of speeds) of (k+1 \choose 2)^{k-1}.

Of course, checking all possible speeds summing to something less than (k+1 \choose 2)^{k-1} is infeasible even for k=5, so one should be smarter. An outline of the proof for 8 runners (k=7) from [1] is as follows. If a counterexmaple exists, sum of speeds v_1+...+v_7 should be at most 28^6. Now, if none of v_j are divisible by 6, say, then at time t=1/6 all runners are 1/6 far from the origin. Hence, we have v_1*v_2*...*v_7 divisible by lcm{2, 3, 4, 5, 6, 7 ,8}. We now want to show that this product must also be divisible by larger primes, once we find many primes with product exceeding (28^6/7)^7/lcm{2, 3, 4, 5, 6, 7 ,8} we get a contradiction.

For a fixed prime p, assuming none of v_j's are divisible by p we can essentially argue that one of the times j/(p*(k+1)) works for some j\in \Z/p(k+1)\Z. To show this claim it suffices to do some finite check depending on the set of speeds modulo p*(k+1). This discretized version of lonely runner, see Lemma 6 [1], is roughly equivalent to some cover problem: Given several subsets of the ground set, find the smallest collection of subsets which union covers the whole ground set. This is known to be NP complete but for the problem at hand we have not so large of numbers: it is enough to check primes up to 163 (of which all numbers from 31 work except for 41), so our ground set is of size at most 8*163=1304. Moreover, it's not surprizing that if the Lonely runner conjecture is true then its discretized version with prime p should also work with few exceptions.

The author of [1] implements some backtracking algorithm for solving this cover problem, which takes 32 hours, but he himself says that SAT solvers should do better, and likely even be enough to cover the k=8 case (i.e. 9 runners). I did some back of the envelope computation for the number of clauses and it seems that SAT solvers should basically solve this problem instantly for k=9 if they are as good as they are advertized.

Maybe ask chatGPT to write the code and then boast about how AI solved a math problem?..

By the way, there is a nice recent overview, "The Lonely Runner Conjecture turns 60" [4] which discusses the results concerning the lonely runner conjecture and gives several elegant reformulations of the conjecture, mostly in geometric terms, which look somewhat similar to the Bang's conjecture about covering a convex polytope with planks.

At the end, let me mention that I believe lonely runner conjecture to be wrong with a huge margin. Taking a random time it's easy to see that a gap of 1/(2k) always exists and I believe that for large k, even the bound of 1/(1.99*k) is wrong. See also this post [3] of Tao where he explains how to improve 1/(2k) by something of the order of log{k}/k^2.

[1] https://www.arxiv.org/pdf/2509.14111
[2] https://terrytao.wordpress.com/2015/05/13/a-remark-on-the-lonely-runner-conjecture/
[3] https://terrytao.wordpress.com/2017/01/10/some-remarks-on-the-lonely-runner-conjecture/
[4] https://arxiv.org/pdf/2409.20160

Here is one interesting fact.

When you have a Markov chain (think of a random walk on a finite graph) an important quantity to look at is mixing time: How many steps does one need to take so that the distribution becomes close to the stationary distribution of the Markov chain? One instance of this problem is: How many shuffles are required to mix a deck of card?

There are several ways to measure closeness but people typically use total variation distance, and define close to be “TV distance at most 1/4” (any smaller constant changes mixing time by at most a constant factor and usually even less).

Often one wants to sample from the stationary distribution by running the Markov chain. A natural question then arises: can we define a stopping time (a decision process for deciding when to stop the Markov chain, possibly depending on its trajectory) so that the end point distribution is approximating stationary measure much better than naive stopping at deterministic time T?

There may be periodicity issues (like random walk on a bipartite graph) when the measure coming from stopping at time T just does not converge. So one would rather want to stop and random time, let’s say uniformly random from 1 to T (from T/2 to T would also work).

Turns out, you cannot do much better: if you have a stopping time which, in expectation, is at most \eps*T, then the distance to the stationary measure you can get is at least the one from the Uniform(1…T) stopping time minus \eps. Meaning that up to constant factors, stopping at uniformly random time is at least as good as stopping at some carefully chosen time which depends on the trajectory.

Here is a proof: suppose some stopping time S achieves very small distance to the stationary. Let’s run additional Uniform(1..T) steps on top of S steps. The measure of the end point is still very close to stationary since running a fixed number of steps from the stationary measure still gives you a stationary measure. Now, we claim that the end point after S+Uniform(1…T) steps can be coupled with the end point after Uniform(1…T) steps with error at most O(eps) (recall that \E[S]<=eps*T). This would solve the problem as coupling with probability 1-eps means that TV distance is at most eps hence ensuring that Uniform(1..T) stopping time is almost as good.

For the coupling first sample an infinite trajectory and run S steps (the number S depends on the trajectory) and then Uniform(1..T) steps. For fixed number k at most eps*T it’s easy to couple k+Uniform(1..T) with Uniform(1..T) with error eps (explicit construction: take k+Uniform(T) modulo T) and so we use this coupling to construct Uniform(1..T) stopping time on the same trajectory.

Here we pretended that S is at most eps*T a.s. But carefully looking at the argument one realises that it works for \E[S]<=eps*T as well.

Here is a surprising neat connection between communication complexity and additive combinatorics.

Communication complexity problem: suppose Alice, Bob, and Charlie each have a number written on their hat: a, b, c, all three from 1 to N; so that each knowns the other two numbers. Sending bits of information between each other, they want to decide whether a+b+c=N. How many bits do they need to send?

Trivially, having log N bits of communication suffices: Alice can send the number b to Bob and then Bob knows everything and can decide on whether a+b+c=N or not. But can they do significantly better?

Additive combinatorics: What is the largest size of a subset of [N]^2 which does not contain a “corner”, i.e. a triple of points (x, y), (x+d, y), (x, y+d)? This problem can be thought of as a more difficult version of no-3AP problem which asks for the largest subset of [1…N] without a three term arithmetic progression. Indeed, given any set B\subset [1…N] without 3APs, the preimage of B under the map f:[N]^2—>\Z sending (x, y) to x+2y-N has no corners and almost the same density.

Now, what’s the connection? If for the corner problem one considers a colouring version (i.e. what is the smallest number of colours needed to colour [N]^2 so that we avoid monochromatic corner), then it turns out that the communication complexity is more or less equal to the logarithm of the number of colours needed. Before showing the reductions in both directions, let me mention that the upper bound on the density of the set without corners immediately implies a lower bound on the number of colours and in the opposite direction, given a corner-free set of size \alpha*N^2, taking roughly log(N)/\alpha random shifts of this set with cover [N]^2 with high probability which, upon easing intersections, leads to a colouring with log(N)/\alpha colours.

So, reduction. First, suppose a colouring of [N]^2 with C colours that avoids monochromatic corners exists. At the preprocessing step, Alice and Bob using 2 bits of communication make sure that both b+c and a+c are at most N (if not then clearly a+b+c>N). Then Charlie sends log_2(C) bits that encode the colour of (a, b)\in [N]^2. Finally, Alice checks that (N-b-c, b) \in [N]^2 has the colour that Charlie announced, and Bob checks that (a, N-a-c) \in [N]^2 has the colour that Charlie announced. All three claim that a+b+c=N iff the colours match both for Alice and Bob. In total, 4+log_2(C) bits of communication are used. Why does this work?

In the YES case, when a+b+c=N, the points (a, b), (N-b-c, b), and (a, N-a-c) coincide and hence have the same colour. Otherwise, if a+b+c is not equal to N, these three points are distinct and form a corner, hence they cannot be of the same colour!

This reduction together with a construction of Behrend already gives a communication protocol with just log(N)^{1/2} bits (recall that the density of a set in Behrend construction is of the order exp(-log(N)^{1/2}).

What about the opposite direction. Given a communication protocol, how can me convert it into a colouring?! Well, suppose a communication protocol with log_2(C) bits of communication exists. Then there are at most \Omega(C) different transcripts of the communication possible. Let’s colour a point (x, y)\in [N/2]^2 into the colour corresponding to the transcript of the communication with input (x, y, N-x-y), which is clearly a YES instance. What would it mean to have a monochromatic corner? This would mean that (x, y), (x+d, y), and (x, y+d) are all coloured in the same colour and so transcripts for

(x, y, N-x-y)
(x+d, y, N-x-y-d)
(x, y+d, N-x-y-d)

are all the same. We claim that then the transcript for (x+d, y+d, N-x-y-d) is also the same. Indeed, if, say, Alice speaks first then she cannot distinguish between instance (x+d, y+d, N-x-y-d) and the third instance above so she will send the same bit. If, say, Bob speaks next, he cannot differentiate between (x+d, y+d, N-x-y-d) and the second instance above since he sees x+d, N-x-y-d in both cases and also heard the same message from Alice.

Proceeding further following the transcript we see that Alice, Bob, and Charlie must also identify (x+d, y+d, N-x-y-d) as a YES instance, leading to a contradiction!

Now, what can be said about an upper bound for the size of a set avoiding corners and hence a lower bound for the number of colours needed which implies a lower bound on the communication complexity? Even the bound of o(N^2), which translates into super constant commutation lower bound, is nontrivial. The original proof uses triangle removal lemma and hence leads to a N^2/log^*N bound at best.

The first quantitatively reasonable bound was obtained by Shkredov (in 2006, it was his PhD thesis if I’m not mistaken), who proved an N^2/(loglogN)^c upper bound. Surprisingly, unlike in the case of 3AP, no improvements were obtained until this year when a quasi-polynomial bound of N^2*exp(-(logN)^{1/600}) was obtained [https://arxiv.org/pdf/2504.07006 ] which almost matches the Behrend’s construction and leads to a (logN)^{1/600} lower bound for the communication complexity.

This work builds on the ideas from the breakthrough of Kelley and Meka who proved a similar N*exp(-(logN)^{1/12}) upper bound for the size of a subset of [N] avoiding 3APs. The work of Kelley and Meka, in turn, is, apparently, inspired by the amazing (2.76)^n upper bound for the cap set size (a subset of \F_3^n avoiding three points on a line) due to Ellenberg and Gijswijt improving the polynomial method of Croot, Lev, Pach.

Looking again at the article about the Lonely Runner Conjecture for 8 runners [2], I noticed that the author also proves an improved version of the statement "if the set of speeds forms a lacunary (enough) sequence then there exists a time when the runner whose speed is set to zero is lonely". Lacunary sequence in general means that v_{j+1}/v_j>1+\eps for some \eps>0 and all j, and in this particular setting \eps is of the order of 3e*log(k)/k for k+1 runners.

Though I don't think this statement sheds light on the LR conjecture in general (again, I believe the general conjecture to be false for large k), this line of works is interesting in its own way. The proof relies on a recent paper by the author and A. Shen [1], which gives nice proofs and improved bounds for some related results. The general pattern of the proofs is the use of the following lemma about a game between Alice and Bob.

Given an infinite k-ary rooted tree, consider the following game. Initially Bob is at the root of the tree. At each step Alice adds some vertices of the tree to a forbidden set \F, and then Bob moves to one of the children of the current vertex. Alice wins if Bob is forced to step onto a forbidden vertex and Bob wins if this never happens. Of course, some restriction is needed on how many vertices Alice is allowed to add to \F, as otherwise she would always be winning.

To formulate the restriction, consider a weight function on a tree given by \beta^{-t} for the vertices at level t, i.e. the root has weight 1, its children have weight 1/beta, etc. Here \beta \in (1, k). The restriction for Alice is as follows: for every move the total weight of the newly forbidden vertices, measured in the current subtree, does not exceed some constant \omega. For all practiacal purposes let's assume further that Alice cannot add the current vertex where Bob is to the forbidden set. Note that we may assume that Alice is only adding vertices in the subtree of the Bob's current position. So here is the lemma:

Lemma: Assume that for some integer k > 1, some \beta\in (1,k) and some \omega > 0, the inequality \beta*(1+\omega) <= k holds. Then Bob has a winning strategy in the (β,ω,k)-game.

Proof: Bob simply maintains an invariant "total weight of all currently forbidden vertices in a subtree is less than 1". Initially it's true, as the total weight is zero, and when Alice adds some forbidden vertices the total weight in the current subtree becomes smaller than 1+\omega. Choosing a child as to minimize the invariant, Bob can find one with the total wight smaller than (1+\omega)/k*beta (1/k factor comes from having k children and \beta comes from the fact that in the new subtree all weights are larger by a factor of \beta). By assumption we have (1+\omega)/k*beta<=1 and so the invariant remains smaller than 1. It remains to note that invariant being smaller than 1 ensures that Bob is not stepping on a forbidden vertex.

Many problems can be solved with ease using this game and, in fact, may examples are given in [1] (the article is in general very easy to read). Let me state two of these problems which admit strengthenings which are conjectured to be true but still open:

Problem 1: We say that a string of symbols w (over some alphabet S) is square-free if it does not contain substrings uu for non-empty strings u.

Theorem: Let S be an alphabet with at least 4 letters, possibly infinite one. Given a function f: \N --> S\choose 4, which assigns to each positive integer a set of 4 letters allowed at the corresponding position, it is possible to choose one letter (out of the allowed four) for each position to form a square-free sequence.

The same is believed to be true when each position only has 3 allowed letters. The case when the function f is constant (i.e. we just work over an alphabet with three letters) was resolved by Thue who constructed an infinite sequence over {1, 2, 3} which is square -free.

Problem 2: This is a problem from Erdös. Let n_k be a lacunary sequence of positive integers, i.e., n_{k+1} > (1 + \eps)*n_k for some \eps>0. Can we find a real \theta such that all distances from n_k*\theta to the nearest integer are separated from 0 (exceed some positive \delta for all k)?

This question has been answered positively, the bound for \delta in terms of \eps has been improving over time with the best known bound of the form delta=\Omega(\eps/\log (1/\eps)), the result originally proved in [3]. In [1], again using the game described above, the authors provide a simplier proof which also leads to a better implied constant in the bound. As shown in [3], it's not possible to take \delta larger than \Omega(\eps) but it remains an open problem as to whether \delta=c*\eps with some absolute constant c>0 works.


[1] Local obstructions in sequences revisited, https://arxiv.org/pdf/2503.20529
[2] The lonely runner conjecture holds for eight runners, https://arxiv.org/pdf/2509.14111
[3] https://arxiv.org/pdf/0706.0223

Let A be a triangle. Suppose points of a circle are coloured in two colours, is it always possible to find a monochromatic triangle similar to A? Turns out, that the answer is yes if and only if A has angles (pi/7, 2pi/7, 4pi/7).

More generally, Stromquist conjectures that for any two-colouring of a circle with unit circumference, one can find a monochromatic d-gon with arc-length equal to 1/(2^k-1), 2/(2^k-1), \dots, 2^{k-1}/(2^k-1) in some order. It's not difficult to see that this conjecture is equivalent to the same assertion for a two-colouring of the vertices of a regular polygon with 2^k-1 vertices. This conjecture is known for k=1, 2, .., 7 but is open in general, the case k=7 was resolved in [1] using a SAT solver.

Remarkably, in a recent paper [1], it is proved that no other k-tuple of numbers satisfies the same property, i.e. for any other k-tuple of positive real numbers (d_1, ..., d_k) summing to one, it is possible to construct a two-colouring of a circle avoiding a monochromatic polygon with arcs of lengths d_1, ..., d_k in some order.

If I understood correctly, in the case when the colouring is given by alternating white and black arcs of fixed length 1/2t, the conjecture of Stromquist is equivalent to the following statement, see Conjecture 3.1. in [1]:

Let -1< x_1, x_2, \dots x_k < 1 be a sequence of real numbers satisfying x_{j+1}=2x_j mod 2 for each j=1, 2, ..., k with cyclic indexing, i.e. x_{k+1}:=x_1. Then it's possible to rearrange the sequence in such a way that the sum of all prefixes is in [0, 1).

Note that x_1+...+x_k=0 for any such sequence.

[1] https://arxiv.org/pdf/2504.10687

Denote by s(n) the size of the largest subset of {1, 2, ..., n} not containing two distinct elements differing by a square.

Strangely, back when I was writing the quoted post, as far as I can remember, the best upper bound I knew was of the form N*(\log N)^{-c\log\log\log N}, which is better than "classical" bounds for the 3-AP problem, i.e. the problem of estimating the size of the largest subset of {1, 2, ..., n} without a three-term arithmetic progression. Recall, that before the breakthrough of Kelley and Meka people were fighting to get to the N/log{N} bound in the 3-AP problem.

Yet, since the work of Kelly and Meka the bound for the 3-AP problem was pushed to N*exp(-c*(log N)^\alpha) with \alpha=1/12+o(1) in their original paper and \alpha=1/9+o(1) in the improved version by Bloom and Sisask.

Anyhow, turns out, there has been some progress in the square-difference-free set problem in the last year. Namely, Ben Green and Mehtaab Sawhney [1] proved a lower bound of N*exp(-c*(log N)^\alpha) with \alpha=1/4+o(1) and then in a more recent version of the preprint with \alpha=1/2+o(1), which is, perhaps superficially, the same as the (upper) bound in the 3-AP problem coming from the Behrend construction.

Anyhow, as I wrote back in March, in the square-difference-free set problem nothing like Behrend construction exists and the best lower bound is still \Omega(N^\alpha) with alpha=0.7334 coming from the base b=205 construction. Moreover, the authors of [1] speculate that an upper bound of n^{1-c} with some fixed c>0 should hold.

I have not read the paper in any deatail but noticed that one ingredient of the proof is the hypercontractive inequality of sort. This more often appers in computer science, though found many other applications (KKL inequality is one famous consequence, used both in CS and in combinatorics). Hypercontractivity is the following fenomenon. Let f: {0, 1}^n --> \R be a function. For \rho> 0, we define the noise operator as multiplication by \rho^|S| in the Fourier spectrum. This is sort of a local averaging, for \rho=0 this does nothing but for larger \rho it averages f over "weighted neighbourhoods" somehow. Hypercontractivity says that the L^p norm of the noisy function T_{\rho}f can be controlled by the L^q norm of f itself even if p>q, provided that the noise \rho is sufficiently large.

[1] https://arxiv.org/abs/2411.17448

Multiplication table, more than you wanted to know!