Research/Mathematics
Integer relations sharpen the flag bound for 15 and 16 lonely runners
We prove that the last Gram-Schmidt length in Allikvere's flag bound is capped at 1/3 by the integer relations among the speeds. This lowers the bound on a counterexample's speed product by 2.0 nats for 15 runners and 2.1 nats for 16. We also prove that nothing else in the bound's own structure can lower it further.
Nov 22, 2026 · 7 min read

The computer-assisted proofs of the Lonely Runner Conjecture for up to 15 runners all start the same way. They prove that a counterexample's speeds would have a bounded product, then show that enough primes must divide that product to break the bound. The sharpest version of the first step is Jaan Allikvere's flag bound (arXiv:2609.02604). We found an arithmetic fact that it does not use, and proved that it lowers the bound: by 1.9985 nats for 15 runners and 2.1162 nats for 16 runners. That is a small gain, about a third of one gate prime near 800. We then mapped the whole route. With exact constants at every level of the flag and relation caps of every rank, the bound comes out exactly the same as with the first cap alone. A 16-runner proof has to come from computation.
2.1162
nats removed from the 16-runner bound
1.9985
nats removed from the 15-runner bound
1/3
cap on the last Gram-Schmidt length
0
further gain from exact constants and caps of every rank
The question
The flag bound looks at the lattice obtained by projecting the integer grid onto the hyperplane orthogonal to the speed vector. It takes a Korkine-Zolotarev basis of that lattice and measures its squared Gram-Schmidt lengths t_1, ..., t_d in an ellipsoidal norm. A counterexample forces every prefix sum t_1 + ... + t_r above an explicit threshold, and the bound is the smallest product of the t_i allowed by those constraints. In earlier work on this project we showed that no further fact about Korkine-Zolotarev bases can raise that minimum. The extremal configuration is an orthogonal lattice, which already satisfies all of them. Any improvement had to come from somewhere else.
What we did
The dual of the projected lattice is the lattice of integer relations among the speeds: integer vectors h with h . v = 0. We proved that the last length is exactly t_d = 1 / (sum of q_k h_k2) for one such relation h, where the weights q_k are all greater than 1. A counterexample's speeds can be taken distinct and positive. Then every nonzero relation has sum of h_k2 at least 3, because a relation with sum 2 would make two speeds equal. So t_d < 1/3. The old minimiser has t_d = 17/36 for 16 runners and 7/15 for 15 runners, both above 1/3, so the cap rules it out. We then solved the capped problem exactly in rational arithmetic, by enumerating the vertices of the feasible polytope. A brute-force enumeration in small dimensions cross-checks the method. With the cap removed, it gives back Allikvere's minimum exactly.
What we found
The capped minimum
| runners | old last length | new last two lengths | minimum as a multiple of the old one | gate target before | gate target after |
|---|---|---|---|---|---|
| 15 | 7/15 | 37/105, 37/140 | 1369/1029 | 401.9846 | 399.986 |
| 16 | 17/36 | 5/14, 15/56 | 12150/9163 | 483.239 | 481.123 |
What the dual cap saves, against the size of one gate prime
nats
We then re-read the argument with the aim of breaking it. That pass checked the duality step, the support-function formula, the primitivity of h and the completeness of the vertex enumeration. It also traced how a change in the covolume feeds through Allikvere's Theorem 3.8 to the speed product: the saving is exactly (n/2) ln of the ratio. It found no error. A test file recomputes every number in this article from the code.
Where the idea stops
The natural next step was to feed more of the same information into the bound. At each level r of the flag, Allikvere's prefix inequality uses the universal constant 1/(c+2) for how lonely a point of a codimension-c subspace can be. The particular subspace in the flag has its own exact constant, which can only be larger. Its relation lattice also gives a cap of rank c: the last c lengths multiply to less than one over the lattice's Gram determinant. We proved that even with the exact constant at every codimension and caps of every rank, the minimum for 15 and 16 runners is exactly the dual-cap value above (THEORY_12.md).
The reason is a single flag built from the tight speed sets. Its first relation is v_3 = v_1 + v_2. Its second level is the subspace of forms (x, y, x+y, 2x+y), whose relations come from (1, 2, 3, 4). From the third level on, it uses the relations of (1, 2, ..., c+1). At every level the exact constant equals the universal one. The key case has a short hand proof: the four numbers x, y, x+y and 2x+y can never all be more than 1/4 from the nearest integer at once. Every relation cap is slack at the dual-cap minimiser. The flag is realised by speeds (1, 2, ..., n-1, w) with w large, so the listed information cannot rule it out.
The worst-case flag leaves every relation cap slack
| runners | rank 1: t_d against 1/3 | rank 2: t_(d-1) t_d against 1/9 | rank 3: last three lengths against 1/30 |
|---|---|---|---|
| 15 | 37/140 = 0.264 | 1369/14700 = 0.0931 | below 0.006 |
| 16 | 15/56 = 0.268 | 75/784 = 0.0957 | 975/156800 = 0.0062 |
Earlier on this project we also checked the hyperplane case directly. The relation types that could sit at the last level (a three-term sum, a doubling, longer relations) all give constants at least as strong as the sum relation, so the sum relation decides. In that case the weights give 1/t_d of at least 3 + 4u - 2u2, where u is the largest speed in the relation divided by the fastest speed, so the extremal configuration needs u at most 0.204178. Only an argument that ties the flag to the speed ratios could go further. One such link exists: the shape bound's worst case, one fast runner and the rest near 0.078 of its speed, admits no three-term sum relation. We have not quantified it and make no claim about its size.
What it means
For the 15-runner proof the threshold drops from 401.9846 to 399.986. For our own attempt at 16 runners it drops from 483.239 to 481.123, which slightly shortens the list of primes that must be checked. As far as we can tell, this is the first improvement of the flag bound that uses the arithmetic of the speeds rather than lattice geometry alone. It is also, provably, the last one available from the bound's own ingredients. The real cost of a 16-runner proof is the per-prime computation. Jobs that reproduce the 14-runner case and measure that cost are running or queued in the project repository.


