Lonely Runner Redux

Tweet

July 18, 2025

An update:

Before I move on from this topic, I have some parting ideas..

First consider some of the symmetries of the problem. Picture a movie of the runners running on a unit length merry-go-round. In particular, if we add a constant to each runner's speed, then it's the same problem; if we multiply each runner's speed by the same constant then it's equivalent to the same problem with a time-parameter adjustment (playing the movie faster/slower). So the configuration-space of the n-runner problem is a field.

Second, it may help to consider the opposite problem: the times when all but one of the runners (n - 1) are at the same location. Suppose we can do this for any runner (leave them out). Let these n - 1 runners lump together with period T. Consider their distance with the one left out. This distance moves at times 2T, 3T, and so on. In the most coarse case, the left-out runner flips across 2 opposite points on the circle (with the cluster fixed in the rotating reference frame). So in the worst case, I would expect the distance to be 1/4, i.e. >= 1/4. Sounds too good to be true.

 So the challenge is a constructive argument for why its always possible to find n - 1 runners at the same location while leaving a given runner out.

 

~Babak 

 

The other day I attempted to prove under rather lax conditions that

There exists a time t s.t. all the moving runners are exactly at a distance 1/2 from the still runner.

Turns out, I can't (and I think my claim is provably false). The trouble is with any runner who's speed is a factor of 2. But I think I can show that the strategy works absent such a runner. So let me update the claim.

If the runners' speeds are odd relative primes then there exists a time t s.t. all the moving runners are exactly at a distance 1/2 from the still runner.

August 31, 2019

(The words "relative primes" in the claim above were thus crossed-out.)

Proof. At time t = 1/2 any runner with odd speed is directly across the starting point on the circle of unit circumference.

February 26, 2020

Note to self: The strategy mentioned at the bottom of this post might still work for cases with an even-speed runner in the mix. So that I don't forget (and maybe encourage myself to give it another go when I find the time), here's how I think you can approach it:

We might be able to approximate an even-speed runner as an odd-speed runner on a different time scale. For example, if we multiply all the runners' speeds by 99 (an odd number), then the timescale becomes 1/99th of before, and the odd-speed runners remain odd. To make the even-speed runners odd we add one to the result of multiplying their speeds by by 99.

(You can skip the rest below.)

In fact, let us describe an algorithm for calculating this time. As before, we consider time in discrete steps. Consider pmax, the maximum runner speed in the set {p1, p2, .., pn}.

Scale the track to be of length 2pmax. while keeping the runners' speeds constant. (You can think of this as our changing the units of time.) Consider the track to consist of 2pmax bins of length 1.

As before, label the bins from 0 to 2pmax -1. The position (bin) bi of any runner with speed pi at time t is

bi = t pi  mod 2pmax

Observe at time t = 1, and every odd time thereafter, the fastest runner (with speed pmax) is directly across the starting point (at bin pmax).

Similarly, for each runner i, find the smallest positive solution to

 pmax = ti pi  mod 2pmax

  
Because the pi's are odd coprimes there always exist solutions for ti . And these ti 's are always odd. Note as with the fastest runner, any odd multiple of ti is also a solution.

The time t1/2 when all runners are directly across the starting point then is

t1/2 = ∏ ti             ; ti ≠ ti-1, ti ≠ ti-2, ..

where the product is taken over distinct ti's. And after renormalizing our track length to 1

T1/2 = (1/ 2pmax) ∏ ti

Examples:

1. {3, 5, 7, 11} gives T1/2 = 11/22 =  1/2

(Here, the distinct ti's are 1 and 11.)


2. {7, 11, 13, 15} gives T1/2 = (13 . 15) / (2 . 15) =  13/2


~

So the runner with speed 2 is special.

Now one thing to note is that if this argument is correct, then we can arrive at approximate solutions for the case where there is an even speed runner, by scaling the speeds to a high odd factor and then tweaking these values to be odd coprimes.

Addenda:

August 15, 2019

The claim can be relaxed so that the only requirement is that the runners' speeds be odd. This is because adding a runner to the race whose speed divides the speed of any the original runners does not change the method of calculating T1/2 . So the updated claim is

If the runners' speeds are odd relative primes then there exists a time t s.t. all the moving runners are exactly at a distance 1/2 from the still runner.

August 29, 2019

Not so sure about this last claim that they just be odd. The argument hinges on the fastest runner's speed pmax not being divisible by any of the other runners' speeds the pi 's.

PS I risk making a fool of myself posting thoughts on line. (I've decided it doesn't matter.) Anyway, I must be getting this whole problem wrong, because for any runner with odd speed at time t=1/2  they're directly across the starting point on the circle of unit circumference. So all this calculation, much a do about nothing.

Proving the Lonely Runner Problem Discretely

Tweet

The other day I came across the Lonely Runner Conjecture from Tamás Görbe's tweet. Here's my attempt at an outline of a proof. In fact, I'm attempting a stronger result that is hinted by Czerwiński, S. (2012). "Random runners are very lonely". Journal of Combinatorial Theory, Series A. 119: 1194–1199 (arXiv.org)


Addenda:

August 12, 2019
This article contains numerous errors. Here's an update.


August 10, 2019
This is wrong. I know why it's wrong, but don't why it's wrong [sic]. I'll post an update. 

Consider the discrete [re]formulation of the problem where the runner's speeds take on distinct integral values and one of the runners stays still. We aim to prove

There exists a time t s.t. all the moving runners are exactly at a distance 1/2 from the still runner.

Now in addition to quantizing the speed of our runners, let us restrict t to discrete values also. In this view then, the circle consists of a ring of bins, and at each step (incrementing t by 1) each runner hops as many bins forward as their integral speed.

(Observe in the original formulation of the problem, we are free to scale t (as in to whatever units) as we wish. Thus it is important to keep in mind that it is only the relative magnitudes of the speeds of the runners that matters.)

Let us have N = ∏pi bins in the ring where the pi's in the product are the distinct integral values of the runners' speeds. (It makes the argument seem clearer if you think of these pi's as co-prime, but our argument here doesn't hinge on it.)

Label the bins in the ring with numerals, starting with 0 (zero) for the starting bin (whence the race began). At any given time t, the bin bi for the i'th runner with speed pi is given by

bi = tpi  mod N

The runners then meet at bin 0 the starting point every N steps. Without loss of generality, assume N is divisible by 2. (There are multiple ways we can transform the case where N is odd, to an even one--but conceptually the simplest way is to just throw in another runner with speed 2.)

Now consider modulo N/2. Notice the runners also meet at bin N/2 at every time t = N(k+1/2)  (for all k in Z). Thus, the distance to the still runner at such times, after normalizing the ring's length to 1 is 1/2.

Also, note not all runners need to be running in the same direction for this result to hold. (Which in turn means the result holds from any runner's perspective.)

So this gives exact solutions for distance 1/2 as

t =  (k + 1/2)∏pi ,  k any integer

Note, at this point, t can be loosened to taken on fractional values.
~

What do you think? (This seems too easy. I must be missing something.)

Recording Computer Generated Proofs Using Blockchain Technologies

Tweet

It seems every day we break a new record for the longest computer generated mathematical proof. The other day I was imagining soon there will be ever larger proofs that might not fit comfortably on a single computer. Perhaps such proofs should be saved in compressed form, I wondered. This line of thinking led me to ponder what to publish and where to publish. I have some rough ideas.

What to Publish

An obvious (and very effective) compression technique here would be to just record the program that generated the proof. That is, the size of the program should come close to Kolmogorov-Chaitin entropy of its output (the symbolic proof). The downside to this approach is that it may work too well: it may take a lot of computing time to decompress. Indeed, it's easy to imagine a (large) proof being the product of a massively parallel, perhaps distributed, computing infrastructure. In that event, once the validity of such a proof was settled, the result, that is the theorem and the program that proves it, would be historically recorded (in peer review math journals), and the proof itself would not be revisited until computing resources became cheap and plentiful enough to repeat the exercise.

What makes a theorem worthwhile or interesting, by the way? I don't know what the criteria are, but one, generality certainly helps (a statement that cuts across a class of objects rather than a few instances, for example) and two, the statement of the theorem (the conjecture) ought to be compact--that is, it ought to be a low entropy statement. From the perspective of this second point, I note in passing, for a lengthy proof, the statement of the theorem itself can be viewed as a compression of its proof (so long as we consider all valid proofs of a same proposition to be equivalent).

What if a researcher doesn't want the entire proof, but just parts of it? In other words, can we devise a way to random access the text of such a large proof? e.g. jump from the billionth line to the trillionth line? In many cases, yes. To be precise, if the program outputting the proof is memory efficient, then a snapshot of its state can be efficiently recorded at any point along its execution path. If that is the case, we can annotate the program with separate, relatively small checkpoint data that would allow us to restore the call stack to the checkpoint (breakpoint, in debugger terminology) and from there see the program execute to completion. In general, the less each part of a proof depends on the intermediate results before it, the more memory efficient the program that generates it can be. Most of the computer assisted proofs I read about today appear to fall into this category. (For a counter example, if the nth part of a proof depends on results (data) from the n-1 parts before it, then it can't be memory efficient, and this strategy won't work.)

Diagram: Annotated proof generating program. With this scheme, you publish both the program (blue) and annotations (green), not the much larger output (yellow). Each annotation contains data allowing the program to output the remainder of the proof starting at the execution point that annotation represents. So n annotations partition the proof into n+1 chunks.


Why might reading a proof piecemeal be worthwhile? For one, math proofs are often developed by introducing and proving sub-theorems which when combined yield the desired final result. It may be the proof of these lemmas and sub-theorems that a researcher (human or machine) may want to revisit. And many of these "sub-theorems" may have, relatively, much smaller proofs. So there is possible value in being able to random access a very large proof. But I have another motivation..

I'm imagining you have lots of these very large computer generated theorems (I mean their proofs, of course), and they're piling up at an ever faster rate. Maybe some of these build on other ones, whatever. Regardless, if there are many of these, it would be nice, if once a theorem were proven, we would have an unimpeachable record of it that would obviate the need to verify the long proof again at a future date. So here's a stab at a trustworthy, if not unimpeachable, record keeping system.

Consider dividing the program's output (proof) into contiguous chunks as outlined above. We consider the coordinates of each chunk to be the (self-delimited) annotation data that allows us to rebuild the call stack to the checkpoint. And we define a given chunk to be the program's output from the start of its checkpoint (coordinates) to the next recorded checkpoint. Now, in addition to publishing the program, the coordinates of the chunks, and possibly the chunks themselves, we also publish a cryptographic hash of each chunk. We then construct a Merkle tree with these hashes as its leaf nodes and publish that tree too. Or perhaps we just publish the root hash the Merkle tree (?). The idea here is you can sample the proof and reliably demonstrate that it's part of the published whole.

 Diagram: Proof generating program, chunk checkpoints, chunk Merkle tree

Where to Publish

Now if in our imaginary future ecosystem we're piling on a lot of these proofs at an ever faster pace, we should also consider where they'll be published. These computer generated proofs are not being peer reviewed directly by humans; rather, this peer review has been mechanized to a point where the entire publishing process proceeds unimpeded without human intervention. Where to publish?

How about borrowing some design elements from Bitcoin's blockchain? Here's a simplified [re]view of its basic design.

The chain depicted above started on the right and ended with the most recent block on the left. Each block consists of 2 parts (white and blue, above): one, a linking mechanism connecting the block with its predecessor, and two, a payload that is app-specific. Structurally, the block chain is a singly linked list (left to right), or if you prefer, a stack that is only ever appended; "physically", the head of the linked list (the latest block), or again, top of the stack, is located at the end of the file. The role of this linking, however, is not for navigating the blocks during read access. Rather, it's role is syntactic: it enforces the form a block must take in order for it to be eligible for inclusion at the end of the chain (i.e. what can be appended to the head of the linked list).

The linking mechanism itself is interesting. It involves writing a nonce which when combined with the  block's cargo data yields a [cryptographic] hash that is very close to a hash of the entirety of previous block. Finding such a nonce for a cryptographically secure hash is computationally hard: an algorithm can do no better than trial and error. So hard, that you need a network of incentivized computing nodes competing to find the first eligible block that may be appended to the end of the chain. This nonce is the so-called proof of work. The protocol adjusts the difficulty level (the maximum allowed difference in the above hashes) so that on average blocks are appended to the chain at a steady rate.

How do we know who's first to find an eligible new block? We don't. However, the protocol values the longest known chain the greatest. Thus once a new eligible block is discovered and it's existence is broadcasted across the network, there's little incentive for a computing node to work on the older, shorter chain.

Note we glossed over the application-specific payload data in each block. In Bitcoin, this part of the block records [cryptographically secured] transactions of bitcoins across individuals. Naturally, in order for a Bitcoin block to be well formed, it must also satisfy certain constraints that define (and validate) such transactions. The reason why it was glossed over, as you've probably already guessed, is that I want to explore swapping out bitcoin transactions for math proofs, instead.

Now while the Bitcoin blockchain is computationally hard to construct, it is computationally easy to verify. In its entirety. That is, verifying a file of the entire blockchain is as simple as playing the file from the beginning, the first block in the chain, and then verifying that each subsequent block properly matches the one before it. This involves checking both each block's nonce and the app-specific payload (the transaction signatures must match the public keys of the coins involved). The motivation behind the approach I'm exploring, however, is to store computational work (math proofs, here) in the app-specific section of each block. And, generally, the only way to verify a computational result is to redo it. So it would appear that Bitcoin's principle of quick verifiability would be in opposition to the strategy I have in mind.

A Layered Goldilocks Approach

How about a layered approach? What if some [computationally hard] properties of a blockchain (the linking/chaining mechanism) are easy to verify but verifying some of its other properties are more time consuming (such as verifying the recorded hash of a chunk of a proof as discussed above)? Suppose the latest 10 blocks can be verified in a reasonable amount of time, but verifying the entire blockchain takes an unreasonable amount of computing resources. If someone gave you a blockchain of math proofs so recorded, how confident would you be that it was valid and not just some made up chain? Let us outline the verification steps that we can reasonably perform:

1. Verify that the current, existing distributed blockchain is a longer, appended version of the one you were given.
2. Verify the proof-of-work chaining mechanism is intact.
3. Sample the blocks to ensure they record valid hashes of the computations they represent.

Suppose further this blockchain network contains a built-in falsification protocol (that is seldom, if ever, meant to be exercised): if the hash of the result of a single computational chunk recorded in a block does not match the actual output of the computation, then this falsification can be broadcast to alert the nodes that that block and every block after it are invalid and that the chain must be pruned. If the game the computational nodes are playing still rewards the longest blockchain, then the expected behavior of the nodes will be to try to poke holes in and falsify newer blocks than the old, since the older blocks have likely been checked many times before by other participants in the network.

So, to recap, our proposed computation-recording blockchain has the following attributes:

1. It allows for programs to be recorded in it and later referenced (identified) by their hash.
2. It allows for the chunks of a so-recorded program's output to be parameterized as chunk coordinates.
3. It supports a format to record the hash of a chunk so described.
4. It supports an explicit block falsification protocol (that is only likely ever exercised on blocks at the tail end of the chain).

Taken together, I'm inclined to think such an approach might just work. The underlying hidden force holding this together is history. This suggestion, I think, is not as preposterous as it sounds. Indeed, observe what happens to the Bitcoin blockchain as computational resources become ever more powerful and plentiful: the nonces of the blocks in the early parts of the chain are ever easier to reproduce. Here too proof-of-work, then, is a time-sensitive concept. A more extreme example would be if a vulnerability were later found that necessitated a change in hash function. It is doubtful we'd throw away the historical blockchain: we'd likely find a way to recognize it as a historical artifact and secure the chain with a better function going forward.

A Concluding Thought

A longstanding principle of science has been repeatability. Experimental results are supposed to be repeatable. The modern laboratories of science are big and expensive. Be they planetary science or particle physics, because these experiments are expensive to duplicate, we compensate by bearing witness to them in large numbers. Years from now, we won't be worried about the veracity of pictures New Horizons snapped of Pluto even if we haven't been there since. Same for data collected from the LHC: if it's later shutdown, we'll still trust the recorded data was not doctored, since there were so many witnesses when the experiments took place. From this perspective, the present discussion is about bearing witness in numbers (the number of computing nodes on the network, that is) to math proofs we might not have the resources to revisit again and again. In this sense, mathematics may have already entered the realm of big science.

Differential equation estimating the distribution of primes

Tweet

Let me begin with this disclaimer, first: though mathematically trained (physics background), I am not a mathematician. OK, got that out of the way.

*

I have found a simple way to derive Gauss's estimate of the prime density function using probability heuristics, alone.

Background

Excerpt From MathWorld: http://mathworld.wolfram.com/PrimeNumberTheorem.html

..
In 1792, when only 15 years old, Gauss proposed that , the prime density function

Gauss later refined his estimate to

where

..

I have not seen a simple derivation for this estimate, and if it exists, I am surprised why it is not more widely used in expositions on the subject of the distribution of primes. What follows is a very short argument based on a probability model. According to this model, we'll find that the distribution of primes is governed by a delay differential equation of the form

Q'(x) = - Q(x) Q( √x ) / x

which has a solution

Q(x) = 1 / 2 ln x

Anyway, to me, what's interesting is how using some specious probability arguments about the distribution primes I was able to set up the equation and try a test function inspired by Gauss's estimate to solve it. This hints at something more meaningful in my Clouseau-esque accident.

The setup

The setup, I have come to find, is similar in spirit to Harald Cramer's probabilistic, heuristic arguments for estimating of the distribution primes (the difference here being that we don't use any other results from number theory). Here it is..


Equ. 1:
The joint probability of a randomly chosen positive number n not
being divisible by two relative primes p and k is (1 - 1/p)(1 - 1/k).

Equ. 2:
Define Q(x) = ∏(1 - 1/p)
taken over all primes p ≤ x.

Equ. 2a:
The joint probability of a randomly chosen positive number n not being divisible by any prime p ≤ x is Q(x).

Using Equ. 2a, vigorous hand waving, and a pinch of salt, we can say

Equ. 3:
The probability that a randomly chosen positive number x is a prime is Q( √x ).

What we're saying here is that for x to be prime, it suffices to show that it is not divisible by any prime less than the square root of x. Equ. 3 says that in the neighborhood of x, the 'average' distance between primes is 1 / Q( √x ).

Now the d.d.e. above comes from trying to approximate Q(x) using this probabilistic model. The idea is to use that approximation in order to estimate a prime counting function:

∫ Q (√x) dx

But we don't have an analytic expression that approximates Q, yet. Instead of setting up an integral equation, we try a differential approach. Consider the change in Q as x passes over 2 very large consecutive primes p₁ < p₂:

ΔQ = -Q(p₁) / p₂ ~ -Q(x) / x
Δx ~ 1 / Q( √x )

Dividing the top equation by the bottom one, you get

Q'(x) = - Q(x) Q( √x ) / x

the d.d.e. I described above.


The solution

I had read somewhere how the 15 year old Gauss had been able to come up with his logarithmic integral for estimating the number of primes less than n. Was his integral inspired by a similar probabilistic argument? Maybe, but googling it, I couldn't find much. So, I plugged in C / ln x and solved for the constant C (=1/2).

Q(x) = 1 / 2 ln x


Does it mean anything?

I suspect it might, which is why I posted it. I did a bit of cursory reading on the topic, but alas, I'm an amateur. My claim that

Q(x) = ∏( 1 - 1/p) ~ 1 / 2 ln x

does not agree with Mertens' asymptotic formula (1874)

∏( 1 - 1/p) ~ exp(-C) / ln x,

where C is Euler's constant.

Still, there's something here that piques my nose. My result, when plugged into the prime counting integral, agrees exactly with Gauss's estimate:

∫ Q (√x) dx ~ ∫ (1 / ln x) dx
What do you think? Is this interesting, or is this old?


7-09 Addendum: Interestingly, if we adjusted the model so that Q'(x) = - Q(x) Q( x^1/n ) / x

then Gauss's estimate would still hold for most n. It's as if the forward distribution constrains that back distribution.