Single-speed modifications of the tight Lonely Runner instance: an effective bound and the complete classification for r = 2

Abstract

For a set V of n-1 distinct positive integers write LR(V) = max_t min_{v in V} ||v t||, where ||x|| is the distance from x to the nearest integer; V is tight if LR(V) = 1/n, the value predicted by the Lonely Runner Conjecture. Goddyn and Wong (Integers 6 (2006), #A38) classified the tight sets obtained from the baseline [n-1] by replacing one speed r with a multiple mr, and proved that for a fixed r only finitely many non-multiple replacements can be tight, remarking that this "partially explains" why the two sporadic tight sets {1,3,4,7} and {1,3,4,5,9}, in which the speed 2 is replaced by an odd number, have no analogues. We make their finiteness effective and settle the case they singled out. Let U(n,r) be the region left uncovered when speed r is deleted from the baseline. We compute the length of every connected component of U(n,r) exactly, in both regimes 2r > n-1 and 2r <= n-1, in terms of an arithmetic quantity I(n,r). Since a connected set on which the inserted speed w must stay 1/n-close to the integers cannot be longer than 2/(wn), this yields the explicit necessary bound w <= 4rI/(2s-I) with s = n-r, and hence: if ([n-1] minus {r}) union {w} is tight with 2r <= n-1, then n <= 6r. This improves the constant implicit in Goddyn and Wong's finiteness theorem from 12 to 6 and makes the classification of single-speed modifications a finite computation for each n. Carrying the computation out for r = 2 we obtain the complete classification: ([n-1] minus {2}) union {w} with w > n-1 is tight if and only if (n,w) = (5,7) or (6,9); the same method disposes of r = 3 entirely. We also report exhaustive censuses in exact rational arithmetic, and note that the natural guess that tight sets have all speeds below 2n is false, a counterexample being the Goddyn-Wong set {1,...,29,31,90} with n = 32.

10 pages. Code and data: https://doi.org/10.5281/zenodo.21695561