All equality cases for eleven through fourteen lonely runners

What Lean checks

The displayed equality directions have their exact global values. Norm cutoffs and prime selection are checked under explicit smaller-dimensional runner bounds. Those bounds, modular exhaustiveness and uniqueness remain open.

Let L(v)=maxt∈ℝmini∥tvi∥L(v)=\max_{t\in\mathbb R}\min_i\|t v_i\| for kk distinct positive integer speeds. The stationary runner gives k+1k+1 runners in total. Divide the speeds by their gcd and sort them to obtain the primitive set.

Theorem. The primitive speed sets satisfying L(v)≤1/(k+1)L(v)\le1/(k+1) for 10≤k≤1310\le k\le13 are as follows. Each listed set attains equality.

Runners All primitive speed sets
11 {1,…,10}\{1,\ldots,10\}
12 {1,…,11}\{1,\ldots,11\}
13 {1,…,12}\{1,\ldots,12\}
14 {1,…,13}\{1,\ldots,13\} and {1,…,11,13,24}\{1,\ldots,11,13,24\}

The first three rows settle the prediction stated by Sungkawichai and Trakulthongchai in §7.1. The second fourteen-runner example was found by Goddyn and Wong. The new conclusion is exhaustiveness over arbitrary integer speeds. The proof uses the earlier authors’ finite modular sieves, together with a geometric argument and an additional finite computation to determine the integer directions. Sungkawichai and Trakulthongchai, §§5–7 · Goddyn and Wong · Allikvere, §§4–7

Size and separation bounds

Use L(E)=maxx∈Emini∥xi∥L(E)=\max_{x\in E}\min_i\|x_i\| for a rational subspace EE. Assume vv primitive and L(v)≤1/(k+1)L(v)\le1/(k+1). Every rational subspace containing vv is contained in no coordinate hyperplane. If its dimension is r+1r+1, it has loneliness at least 1/(k+1−r)1/(k+1-r) by coordinate coalescence and the already proved lower-dimensional lonely runner bounds. In particular every rational plane containing vv has loneliness at least 1/k1/k. Allikvere, Lemma 3.3

Project the integer lattice orthogonally onto v⊥v^\perp with its ordinary Euclidean metric. Its covolume is 1/|v|21/|v|_2. Let tit_i be the squared Gram–Schmidt lengths of a Korkine–Zolotarev basis. For the space spanned by vv and integer lifts of the first rr basis vectors, subtract integer multiples of the lifts in reverse basis order. Each remaining projected Gram–Schmidt coefficient has absolute value at most 1/21/2. The component parallel to vv can be absorbed into the circle parameter. Every point of that torus is consequently within Euclidean distance 12∑i≤rti\tfrac12\sqrt{\sum_{i\le r}t_i} of the speed circle, hence within this sup distance as well. Since loneliness is 1-Lipschitz in sup distance,

∑i≤rti≥Br=4(1k+1−r−1k+1)2.\sum_{i\le r}t_i\ge B_r=4\left(\frac1{k+1-r}-\frac1{k+1}\right)^2.

Set B0=0B_0=0, ci=Bi−Bi−1c_i=B_i-B_{i-1} and K=∏i=1k−1ciK=\prod_{i=1}^{k-1}c_i. The verifier checks ci+1/ci>4/3c_{i+1}/c_i>4/3 exactly. The KZ basis satisfies ti+1≥3ti/4t_{i+1}\ge3t_i/4. Allikvere’s product minimization lemma therefore gives 1/|v|22=∏iti≥K1/|v|_2^2=\prod_i t_i\ge K. In particular D=∏ivi≤(kK)−k/2D=\prod_i v_i\le(kK)^{-k/2} by AM–GM. This argument allows equality in the prefix bounds. Allikvere, Lemmas 3.5–3.6

For 2≤d≤k2\le d\le k, if no speed were divisible by dd, time 1/d1/d would give L(v)≥1/d>1/(k+1)L(v)\ge1/d>1/(k+1). Thus F=lcm(2,…,k)F=\mathop{\mathrm{lcm}}(2,\ldots,k) divides DD. For the prime set of each row below, with product PP, the verifier checks that FF and PP are coprime and that

(FP)2(kK)k>1.(FP)^2(kK)^k>1.

Consequently one of the listed primes divides no speed. These four comparisons use rational arithmetic. Verifier and exact prime lists

Short vector lemma. If 0≠w≡av(modm)0\ne w\equiv av\pmod m and k(k+1)∥w∥∞<2mk(k+1)\|w\|_\infty<2m, then ww is parallel to vv. Otherwise z=(w−av)/mz=(w-av)/m is integral and independent of vv. Represent any phase on their plane by sv+tzsv+tz with |t|≤1/2|t|\le1/2 modulo one. It is within ∥w∥∞/(2m)\|w\|_\infty/(2m) of (s−ta/m)v(s-ta/m)v. Therefore the plane has loneliness strictly less than 1/(k+1)+1/(k(k+1))=1/k1/(k+1)+1/(k(k+1))=1/k, a contradiction. A recorded short vector thus determines the primitive integer direction by its sorted absolute coordinates divided by their gcd.

Which modular orbits an equality case can occupy

Fix a prime pp dividing no coordinate. Consider binary lifts, with moduli m=2jpm=2^j p. In every row of our proof k+1k+1 has an odd prime factor different from pp, so k+1k+1 does not divide mm. A grid distance at least 1/(k+1)1/(k+1) on these grids is automatically strictly greater. Hence a tuple with L(v)≤1/(k+1)L(v)\le1/(k+1) has no witness on any such grid. At binary levels the gcd deletion in the earlier sieves can only mean that all entries, or all but one, are even. All-even entries contradict primitivity. With exactly one odd speed, the even speeds have a time of loneliness at least 1/k1/k by the lower-dimensional theorem. They keep their phases half a turn later, and in one of the two positions the odd speed has distance at least 1/41/4. Thus this deletion also gives a strict witness. The complete binary searches cited below therefore cover an actual equality case up to permutation, individual signs and multiplication by a unit.

  • Ten and twelve speeds. For k=10k=10 use the 61 primes in Table 1 of Sungkawichai and Trakulthongchai, and for k=12k=12 use the corresponding 91. Their binary sieve through 8p8p, projected back to pp, leaves only the orbit of (1,…,k)(1,\ldots,k). We use the result of the binary phase before their polynomial argument. For k=12k=12, Allikvere separately audited all 1,092 residual tuples. Binary sieve and prime lists · Audit of the twelve-speed residuals
  • Thirteen speeds. For each of Allikvere’s 111 archived primes, the binary sieve leaves only the two orbits represented by A=(1,…,13)A=(1,\ldots,13) and B=(1,…,11,13,24)B=(1,\ldots,11,13,24) modulo pp. We need 62 of those primes, namely the 61 primes in the second fourteen-runner proof together with 557. We use the binary result through 32p32p, before the final factor-seven lift. Binary survivors · Original 111-prime table

Eleven speeds. Here the published final sieve uses a modulus divisible by twelve. We instead extract an earlier count from the authors’ original log. For the 44 primes listed as TWELVE in our verifier, the first lift from pp to 2p2p yields exactly (p−1)/2(p-1)/2 rows. The original implementation expands all common-unit rescalings modulo pp, folds the signs there and retains distinct sorted lifts. These counts determine every row at 2p2p. Original log at its fixed commit · Normalizer and lift representation

Indeed, for each unit uu modulo 2p2p, start with (u,2u,…,11u)(u,2u,\ldots,11u), choose each sign to put its residue modulo pp in [1,(p−1)/2][1,(p-1)/2], reduce modulo 2p2p, and sort. Each such tuple must be retained. It has six odd coordinates, and a grid witness would be strict, contradicting the elementary equality L(1,…,11)=1/12L(1,\ldots,11)=1/12. The verifier explicitly constructs these representatives and counts exactly (p−1)/2(p-1)/2 distinct rows for each of the 44 primes. They exhaust the logged first-lift count, so any equality case has the consecutive orbit as its reduction modulo pp. The optional source-log check and CI compare the extracted counts against the hash-pinned original file.

From residue classes to integer sets

The preceding results restrict vv to one or two possible orbits modulo the prime dividing no speed. A single modular match alone would allow infinitely many integer sets. We now apply the short vector lemma to all binary descendants of each permitted root.

At a node xmodmx\bmod m enumerate all children yi=xi+mϵiy_i=x_i+m\epsilon_i modulo 2m2m. A parent unit lifts to a child unit, so the original choice of representative is harmless. At even mm the unit 1+m1+m flips the lift bits at every odd entry at once. Fixing the bit at the first odd entry preserves at least one representative. Exclude all-even and single-odd children as above. At each remaining child and each odd 1≤t≤m1\le t\le m, form the absolute centered coordinates wi=min(tyimod2m,−tyimod2m)w_i=\min(ty_i\bmod 2m,-ty_i\bmod 2m).

  1. If (k+1)wi>2m(k+1)w_i>2m for every ii, discard the child by its strict witness.
  2. If k(k+1)maxiwi<4mk(k+1)\max_i w_i<4m, the signed centered residues are a short vector as in the lemma. For an actual primitive tuple the residue vector has order 2m2m; hence this multiplier produces a nonzero vector. A zero coordinate or equal absolute coordinates exclude a distinct positive primitive tuple. Otherwise record the normalized direction.
  3. Recurse on all other children. An unresolved node at depth ten causes the verifier to fail.

Every one of the 258 prime searches terminates. In every search the recorded directions are exactly the integer sets in the theorem for its respective number of speeds. Finally, their exact maxima can be computed at t=j/(a+b)t=j/(a+b) for two distinct speeds. They contain 1 and 2, so their maximum is below 1/21/2. Every positive local maximum below 1/21/2 has two active slopes of opposite signs, which forces such a denominator. The verifier obtains precisely 1/(k+1)1/(k+1) in all five cases. Binary lift code · Arithmetic and exact maxima

This is an unrefereed computer-assisted proof. Its new verifier replays the deductions from the prior modular sieve results. The cited papers and their archives supply the underlying exhaustive prime-level calculations.