The unique tight speed set for nine lonely runners

What Lean checks

The consecutive set has global value 1/9. Uniqueness remains open.

For eight distinct positive integer speeds relative to a stationary runner, write L(v)=maxtmini∥tvi∥L(v)=\max_t\min_i\|t v_i\|, where the norm denotes distance to the nearest integer.

Theorem. If L(v)≤1/9L(v)\le1/9, then vv is a dilation of {1,2,3,4,5,6,7,8}\{1,2,3,4,5,6,7,8\}. Conversely every such dilation has L(v)=1/9L(v)=1/9.

The nine-runner lonely runner bound was previously proved. Goddyn and Wong found only the consecutive speeds in their finite nine-runner census. Here we establish the equality classification without a speed cutoff. Our argument uses the established lower bounds for smaller numbers of runners. Trakulthongchai · Goddyn and Wong, §1

Product bound

Divide by the gcd and suppose vv is primitive. The prefix bound for successive minima used in the eight-runner proof gives

∥v∥2≤B=36⋅28⋅21⋅15⋅10⋅6⋅3=57,153,600. \|v\|_2\le B=36\cdot28\cdot21\cdot15\cdot10\cdot6\cdot3=57{,}153{,}600.

Here are the details in this dimension. On the projection of ℤ8\mathbb Z^8 to v⊥v^\perp, let λi\lambda_i be the successive minima of the central section of the unit sup-norm ball. Its seven-dimensional volume is at least 272^7 by Vaaler's theorem, and the projected lattice has covolume 1/∥v∥21/\|v\|_2. Hence ∏λi≤1/∥v∥2\prod\lambda_i\le1/\|v\|_2 by Minkowski's second theorem. The circle of vv comes within 12∑i=1rλi\tfrac12\sum_{i=1}^r\lambda_i of every point of the torus obtained by lifting the first rr independent minimum vectors. This follows by rounding the lift coefficients and absorbing the components parallel to vv into its circle parameter. This torus is coordinate-free. Successive coalescence of coordinates gives it loneliness at least 1/(9−r)1/(9-r) from the known lower-dimensional bounds. Thus the prefix sums of the minima dominate the prefix sums of

(1/36,1/28,1/21,1/15,1/10,1/6,1/3). (1/36,1/28,1/21,1/15,1/10,1/6,1/3).

Indeed the latter are 2(1/(9−r)−1/9)2(1/(9-r)-1/9). For these entries yiy_i, sum logλi−logyi≥(λi−yi)/λi\log\lambda_i-\log y_i\ge(\lambda_i-y_i)/\lambda_i by parts using the nonincreasing weights 1/λi1/\lambda_i. This gives ∏λi≥∏yi=1/B\prod\lambda_i\ge\prod y_i=1/B. Eight-runner argument · Yi, Gill and Bu, §11 · Prior prefix bounds for speed products, Remark 3.9

Write D=∏viD=\prod v_i. By the arithmetic-geometric mean inequality, D≤(B/8)8D\le(B/\sqrt8)^8. Every d=2,…,8d=2,\ldots,8 divides some speed: otherwise t=1/dt=1/d gives loneliness at least 1/d>1/91/d>1/9. Thus 840=lcm(2,…,8)840=\mathop{\mathrm{lcm}}(2,\ldots,8) divides DD. This is the strict-witness version of Rosenfeld's forced-divisor observation. Lemma 3.10 and references

A mixed-modulus assertion

For each of the following 26 primes pp, a primitive tuple with p∤Dp\nmid D either has a strict 1/91/9 witness on the 6p6p-grid or is a signed permuted unit multiple of (1,…,8)(1,\ldots,8) modulo 6p6p:

71,89,97,101,107,113,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233.71,89,97,101,107,113,131,137,139,149,151,157,163,167,173,179, 181,191,193,197,199,211,223,227,229,233.

To verify the assertion, fold nonzero residues modulo pp to [x]p=min(xmodp,(−x)modp)[x]_p=\min(x\bmod p,(-x)\bmod p). Enumerate every eight-element set with no strict witness on the pp-grid up to multiplication by a nonzero scalar. For completeness, normalize a pair with least folded quotient over both orders to 1,b1,b; all remaining members exceed bb. Enumerate completions in increasing order with every folded pair quotient at least bb, intersecting the witness masks of the chosen speeds. Remove a possible last speed whenever a multiplier witnesses the whole set. Modular enumerator

A smaller witnessless support extends to a witnessless eight-element set, since adding a speed can only remove witnessing times. Check every nonempty subset of each enumerated set; if it has no witness, try all positive multiplicities giving a total of eight entries. This includes every folded multiset, up to the same symmetries. For each resulting tuple xx:

  1. For q=2,3q=2,3, enumerate the vectors cc modulo qq with gcd(q,c1,…,c8)=1\gcd(q,c_1,\ldots,c_8)=1. Exclude cc if some pair 0≤t<p0\le t\lt p, 0≤k<q0\le k\lt q satisfies 9[qxit+pcik]pq>pq9[qx_i t+pc_i k]_{pq}>pq for all ii. This gives a strict witness at time t/p+k/qt/p+k/q. Coordinate signs act on both residues, and a common unit modulo pp merely reindexes tt.
  2. Combine each surviving pair amod2a\bmod2, bmod3b\bmod3 into c=3a+4bmod6c=3a+4b\bmod6 and run the same test with q=6q=6. The two smaller grids are contained in this larger one.
  3. For every survivor explicitly find a signed permutation ww of (1,…,8)(1,\dots,8) and units up,u6u_p,u_6 such that xi=upwimodpx_i=u_p w_i\bmod p and ci=u6wimod6c_i=u_6 w_i\bmod6 for every ii. To do so, try all up=1,…,p−1u_p=1,\ldots,p-1, determine the possible index and sign for each folded entry, require that all eight different indices are used, and try both units modulo six. Each sign and index is uniquely determined for fixed upu_p when it exists, since p>16p>16. The Chinese remainder theorem provides a common unit modulo 6p6p. Undoing the initial normalization modulo pp just changes this unit.

The program verifies the assertion for every listed prime. The integer comparison (840∏p)288>B16(840\prod p)^2 8^8>B^{16} ensures at least one of them does not divide DD. Lift checker · Prime and product verifier

Lifting the direction

For this prime our tuple has no strict witness, so there is a signed permutation ww of the consecutive speeds with w≡bv(mod6p)w\equiv b v\pmod{6p} for an integer bb. Set m=6pm=6p. If v,wv,w are independent, z=(w−bv)/mz=(w-bv)/m is an integer vector and v,zv,z generate a rational plane. Its torus has loneliness at least 1/81/8 by coordinate coalescence and the known bound in at most seven speeds. Every phase on this plane can be represented by sv+tzsv+tz with |t|≤1/2|t|\le1/2, since zz is integral. The phase (s−tb/m)v(s-tb/m)v differs from it by tw/mtw/m, of sup norm at most 8/(2m)8/(2m). The loneliness function is 1-Lipschitz. Consequently

1/8≤L(span(v,w))≤1/9+8/(2m)<1/8, 1/8\le L(\mathop{\mathrm{span}}(v,w))\le 1/9+8/(2m)<1/8,

where the last inequality follows from m=6p>288m=6p>288. This contradiction forces parallelism. Primitivity and positivity yield the consecutive speeds. At t=1/9t=1/9 these speeds attain 1/91/9, and among 0,t,…,8t0,t,\ldots,8t two are always at circular distance at most 1/91/9. This proves both directions.

The classification is an unrefereed computer-assisted result without a Lean formalization. Run the verifier with Python 3.10 or later and a C++20 compiler from the repository root.

python3 results/tight-eight-speeds/verify.py