Deletion values of the lonely runner: an answer to Zhang's Question 8.4

What Lean checks

Lean proves the exact values in both ranges for every n≥3, 1≤r≤n−1, and the strict inequality for n≥4, using actual real distances and speeds. The small-deletion upper bound is proved internally via rational maximizers and the modular certificate; Liu's theorem is not assumed. The seven-module closure passed local kernel replay, and the theorem endpoints use only allowed axioms. Full repository gate pending.

Status. Complete elementary proof. Exact check for n≤40n\le40 in verify.py (standard library only). No Lean formalization. Unrefereed.

Statement

For a finite set VV of positive integers put LR(V)=maxtminv∈V∥vt∥LR(V)=\max_t\min_{v\in V}\|vt\|, where ∥x∥\|x\| is the distance to the nearest integer, and write [m]={1,…,m}[m]=\{1,\ldots,m\}. The Lonely Runner Conjecture predicts LR(V)≥1/(|V|+1)LR(V)\ge1/(|V|+1). For the n−2n-2 speeds [n−1]\{r}[n-1]\setminus\{r\} this prediction is 1/(n−1)1/(n-1), and Zhang asks whether it is ever attained. [Z26, Question 8.4]

Question 8.4 (Zhang). Is LR([n−1]\{r})>1n−1LR([n-1]\setminus\{r\})>\frac1{n-1} for all n≥5n\ge5 and all r≤n−2r\le n-2?

Zhang proves this when some integer in [n+r,2n−3][n+r,\,2n-3] is coprime to rr, in particular for r≤n−2−2nr\le n-2-2\sqrt n, and leaves the remaining rr open. [Z26, Theorem 2.9 and Corollary 2.10]

Theorem. Let n≥3n\ge3 and 1≤r≤n−11\le r\le n-1.

  1. If 2r>n−12r\gt n-1, then LR([n−1]\{r})=1rLR([n-1]\setminus\{r\})=\frac1r.
  2. If 2r≤n−12r\le n-1, let DrD_r be the least integer D≥n+rD\ge n+r with gcd(D,r)=1\gcd(D,r)=1. Then LR([n−1]\{r})≥2DrLR([n-1]\setminus\{r\})\ge\frac2{D_r} and Dr≤n+2r−1D_r\le n+2r-1. Moreover Dr≤2n−3D_r\le2n-3 unless (n,r)=(3,1)(n,r)=(3,1).

Consequently LR([n−1]\{r})>1n−1LR([n-1]\setminus\{r\})>\frac1{n-1} for all n≥4n\ge4 and all 1≤r≤n−21\le r\le n-2. The answer to Question 8.4 is yes.

By a theorem of Liu quoted by Zhang, equality LR([n−1]\{r})=2/DrLR([n-1]\setminus\{r\})=2/D_r holds in case 2. [Z26, Section 2.3, citing Liu] With case 1 this determines every deletion value:

LR([n−1]\{r})={2/Dr,2r≤n−1,1/r,2r>n−1.LR([n-1]\setminus\{r\})= \begin{cases} 2/D_r,& 2r\le n-1,\\ 1/r,& 2r\gt n-1. \end{cases}

Proof

Case 1. Here r≥2r\ge2, since r=1r=1 would force n≤2n\le2. Take t=1/rt=1/r. Every v∈[n−1]\{r}v\in[n-1]\setminus\{r\} satisfies 0<v<2r0\lt v\lt 2r and v≠rv\ne r, so r∤vr\nmid v and ∥v/r∥≥1/r\|v/r\|\ge1/r. Hence LR≥1/rLR\ge1/r. Conversely the set contains [r−1][r-1], and by Dirichlet's theorem every real tt has some i≤r−1i\le r-1 with ∥it∥≤1/r\|it\|\le1/r. Hence LR≤LR([r−1])=1/rLR\le LR([r-1])=1/r.

If also r≤n−2r\le n-2, then 1/r≥1/(n−2)>1/(n−1)1/r\ge1/(n-2)\gt1/(n-1).

Case 2. Let D≥n+rD\ge n+r be coprime to rr and choose jj with jr≡1(modD)jr\equiv1\pmod D. Put t=j/Dt=j/D and let v∈[n−1]\{r}v\in[n-1]\setminus\{r\}. Since jj is a unit modulo DD:

  • vj≡0vj\equiv0 would give D∣vD\mid v, impossible as 0<v<D0\lt v\lt D;
  • vj≡1≡rjvj\equiv1\equiv rj would give v≡rv\equiv r, hence v=rv=r, which is excluded;
  • vj≡−1≡−rjvj\equiv-1\equiv-rj would give v≡−rv\equiv-r, hence v=D−r≥nv=D-r\ge n, which is outside [n−1][n-1].

So vjmodD∉{0,1,D−1}vj\bmod D\notin\{0,1,D-1\} and ∥vt∥≥2/D\|vt\|\ge2/D for every such vv. This proves LR≥2/DLR\ge2/D; it is Zhang's Theorem 2.9, and the argument is included to keep the note self-contained.

Among the rr consecutive integers n+r,…,n+2r−1n+r,\ldots,n+2r-1 exactly one is congruent to 11 modulo rr, and it is coprime to rr. So Dr≤n+2r−1D_r\le n+2r-1. If 2r≤n−22r\le n-2 this gives Dr≤2n−3D_r\le2n-3. If 2r=n−12r=n-1, then n+r=3r+1n+r=3r+1 is itself coprime to rr, so Dr=3r+1D_r=3r+1, and 3r+1≤4r−1=2n−33r+1\le4r-1=2n-3 exactly when r≥2r\ge2, that is, when (n,r)≠(3,1)(n,r)\ne(3,1).

For n≥4n\ge4 we therefore get LR≥2/Dr≥2/(2n−3)>1/(n−1)LR\ge2/D_r\ge2/(2n-3)\gt1/(n-1).

Cases 1 and 2 cover all 1≤r≤n−21\le r\le n-2, which proves the consequence. For (n,r)=(3,1)(n,r)=(3,1) the set is {2}\{2\} with LR=1/2=1/(n−1)LR=1/2=1/(n-1), so the restriction n≥4n\ge4 cannot be dropped. ▫\square

Remarks

  • The upper range 2r>n−12r\gt n-1 is exactly the range not covered by Zhang's coprimality criterion when rr is close to nn: the interval [n+r,2n−3][n+r,2n-3] is then short or empty. There the time t=1/rt=1/r settles the matter at once. Zhang's proof of his Lemma 2.4 already evaluates the runners at t=1/rt=1/r for 2r>n−12r\gt n-1, for a different purpose.
  • In the lower range the pigeonhole choice D≡1(modr)D\equiv1\pmod r replaces the Jacobsthal-function bound and removes the restriction r≤n−2−2nr\le n-2-2\sqrt n.
  • The equality case r=n−1r=n-1 of the prediction is LR([n−2])=1/(n−1)LR([n-2])=1/(n-1), the consecutive tight set.

Verification

python3 verify.py        # n <= 40, 779 cases, about 15 seconds

The script computes LRLR exactly, in integers, from the candidate times a/(u+v)a/(u+v) with u,vu,v in the set, compares with the displayed formula for every 3≤n≤403\le n\le40 and 1≤r≤n−11\le r\le n-1, checks the strict inequality in all 740 cases with n≥4n\ge4 and r≤n−2r\le n-2, and checks the witness time t=j/Drt=j/D_r of case 2.

Sources

  • [Z26] Y. Zhang, Tight instances of the Lonely Runner Conjecture: complete classification of one-entry modifications, a new infinite family, and the growth bound, arXiv:2608.13599, version 3 (18 October 2026). Question 8.4; Lemma 2.1 (Dirichlet); Theorem 2.9; Corollary 2.10; Section 2.3 for the quoted theorem of Liu on κ([m]\{k,2k,…,sk})\kappa([m]\setminus\{k,2k,\ldots,sk\}).
  • The theorem of Liu is used only for the remark that equality holds in case 2. We did not consult the original and quote it through [Z26]. verify.py confirms the equality for n≤40n\le40.