Lonely Runner Redux

Tweet

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.)

Fuzzchain

Tweet

In an earlier post, some 2 years ago, I thought out loud about how one might record the voluminous output of a computer assisted proof on a blockchain. It's a thought I've kept returning to and which I'm still developing, hopefully with the help of others (but if someone runs with this or some variation on it, that's okay too). I'm calling it Fuzzchain--and not just because its outlines are still fuzzy.

So I started sketching this out as a blog post, but quickly realized it would need to be an evolving document. I had begun with an outline:

• Scale/distribute computational bandwidth (minimize duplication)
• Reliably record the result of a long running computation
• Random access the state of a [completed] long running computation
• Compress the voluminous output of a long running computation (equivalent to previous bullet)
• Embue fuzz, the chain's native coin, with intrinsic (yet market driven) computational value.

The design of the proposed blockchain is discussed in parts.

• Overview of protocol philosophy, design elements
• hint-of-work (HoW)
• chain state hash
• work proposals
• falsification incentives
• block value function
• block payload data
• ecosystem evolution
• Outline of protocol
• programs written in a Turing-complete, but stack-based language
• format for serializing execution checkpoints of programs
• block elements
• existing technologies
• block linking rules
• Discussion

But that kind of exposition sounds too normative. So I abandoned using that outline, but am including it here because it hints at what it's about. Here's my working document. Hope it sparks some ideas.