Two unrestricted extra speeds on a short interval

What Lean checks

Every p ≥ 3 and arbitrary positive integer speeds have a common witness in [1/(p+2),1/p] with clearance at least 1/(p+2). The unbounded branch, all small cases, interval-good base insertion, Goddyn–Wong acceleration criterion, common-dilation value bound, and literal three-insertion obstruction are proved.

This entry is a partial result on an open problem. It does not claim a solution of the general conjecture.

Write ||x|| for the distance from x to the nearest integer. For any integer p>=3 and any two positive integer speeds b<=c, the interval J=[1/(p+2),1/p] contains a time t with both ||bt|| and ||ct|| at least 1/(p+2). This gives a two-speed insertion for all base speed sets of size p-1 that maintain this separation on J, including every Goddyn–Wong multi-acceleration of 1,...,p-1. The added speeds have no upper bound.

Write q=p+2 and delta=1/q, so |J|=2/(pq). If any of the times 1/p, 1/(p+1), 1/q works, we are done. Otherwise each of p,p+1,q divides at least one of b,c, since a nonzero residue with denominator at most q already gives the required separation. One speed must be a multiple of two denominators, whence c>=pq/2 by the pairwise gcds.

Suppose first that p>=11. For b>=2p, the fraction of J on which at least one speed is bad is at most

4/q + p/b + p/c <= 1/2 + 6/q < 1.

Indeed a speed v occupies a bad length at most 2 delta |J| + 2 delta/v, by splitting into whole periods and one remainder. It remains to consider b<2p. The only possible divisors of b among the three denominators occur when b equals the denominator itself.

  • If b=p, then (p+1)q divides c. Take t=1/(p+1)+1/(qc), inside J. The c-phase moves from an integer to delta. The b-phase starts at 1-1/(p+1) and moves by at most 1/((p+1)q), so remains good.
  • Otherwise p divides c and p does not divide b. We claim c>=pb/2. For b=p+1 use c>=pq/2. For b=q use p(p+1) dividing c. When b equals none of the denominators use the same divisibility and b<2p. Now take t=1/p-1/(qc) in J. The c-phase is minus delta modulo one. The b-phase at 1/p had distance at least 1/p, and its displacement is at most 2/(pq)=1/p-delta. This proves the claim for p>=11.

For 3<=p<=10 the same measure estimate is strictly below one as soon as b>2pq/(p-2), since c>=b. For every remaining b, intersect J with its exact closed good arcs and choose a longest resulting interval, of length w. The finite loop in two_additions.py checks w>0 in every case. Any counterexample must satisfy c<2/(qw), because otherwise a single open bad arc for c is too short to contain that whole interval. All remaining integer c are checked by direct rational interval intersection. This treats equality endpoints explicitly and imposes no cutoff without a proof.

For the application, let p be the old total runner count and start with a Goddyn–Wong tight base of p-1 moving speeds. An unchanged speed r<=p-1 stays good throughout J. Consider an accelerated speed w=mr with m>=2, put s=p-r, and recall their criterion gcd(r,k)>1 for all s<=k<ms. The interval cannot contain 1, so s>=2. If s>=r, the interval contains at least r consecutive integers, including one coprime to r. Thus s<r. Since r-1 is coprime to r and is at least s, it cannot be in the interval. Hence ms<=r-1. We show (m-1)(p+2)<w<mp, or equivalently p-ms>2m-2 for the first of these inequalities. For m=2, p-ms>=s+1>=3 suffices. For m>=3 we have r/2-2>=s: from r>=ms+1 this follows if (m-2)s>=3, and the remaining case m=3,s=2 requires 2,3,5 all to divide r. Choose an integer coprime to r between r/2-2 and r/2, namely (r-1)/2 for r odd, r/2-1 for r divisible by 4, and r/2-2 otherwise. This integer cannot lie in [s,ms-1], so ms<=r/2. Hence p-ms>=r/2+s>=ms+s>2m-2. The two endpoint phases are strictly between the same consecutive integers and have denominators at most q. By linearity the entire interval J is good. Applying the two-speed result proves the ordinary Lonely Runner bound after insertion. A dilation of all the base and additional speeds preserves the conclusion. The conjecture for arbitrary speed sets remains open.

The tight base family and its gcd criterion are due to Goddyn and Wong. This note concerns extending it, not priority for its construction.

The corresponding three-speed interval assertion already fails. For p=3 take extra speeds 4,6,10. On [1/6,1/3] the first two leave just [7/36,5/24] and [7/24,11/36]. Multiplying the first by 10 puts it strictly inside (2-1/6,2+1/6), and multiplying the second by 10 puts it strictly inside (3-1/6,3+1/6). Both are therefore excluded. The ordinary five-speed tuple (1,2,4,6,10) succeeds elsewhere, for example at 3/8. Thus the two-speed lemma cannot simply be iterated with three arbitrary speeds on the corresponding prescribed interval. The verifier checks the two surviving intervals and the witness time using rational arithmetic.