Catalogue · Proof · Certificates · Exact checks · Issue #109
Status: Written proof with machine-checkable certificates. The proof is conditional on the four loneliness-spectrum classifications of this repository (five, six, seven and eight speeds). Those classifications are themselves computer-assisted and unrefereed. The note is unrefereed.
Contributor: @aadrianvv. Proof, certificates, verifier, and result package submitted in PR #144.
Lean status: partial. The formalization uses the actual distance graph on the integers. Its unconditional results include the greedy upper bound, periodic-word transport, loop concatenation, integer base change, the four unbounded one-parameter coloring families, the full two-parameter family, and the exceptional chromatic numbers. Theorem A, the Oravcová–Soták clique conclusion, and the primitive triangle-free corollary retain the explicitly named propositions R5, R6, R7, and R8 as hypotheses. Those four real-loneliness classifications are not proved by this closure.
All nine new modules passed strict compilation with warnings treated as errors. The exact 28-module project closure passed an all-owned audit of 1239 declarations (1084 theorem declarations and 40 required endpoints) and independent stock-kernel replay. Only propext, Classical.choice, and Quot.sound are permitted. Receipt, source records, complete inventory.
The five initial source checks were repeated with complete contemporaneous records and reproduced the audited objects exactly. The combined repository gate and hosted validation remain separate. The original proof and certificates remain credited to @aadrianvv.
Primary source: J. Oravcová and R. Soták, On a problem concerning integer distance graphs, arXiv:2401.12347, Conjecture 2.7.
Result
For a set of positive integers, the distance graph on joins and when . Its chromatic number is at most . For and , the chromatic number equals exactly in the following cases:
Consequently, Conjecture 2.7 of Oravcová and Soták holds for five to eight distances (still relative to the four classifications). The conjecture says that forces , a member of their family , or a clique of order .
By Lemma 1, every set with is near-tight for the lonely runner problem, that is, . The 62 colourable sets in the spectrum tables are then handled by explicit periodic colourings. Four infinite one-parameter families are handled by "loops": proper colouring words whose lengths generate a numerical semigroup. The two-parameter six-speed family is handled by a base-change lemma that transfers periodic colourings between members of the family.
Verification
Run from the repository root with Python 3.10 or later and no other dependencies:
python3 results/oravcova-sotak/verify.pyThe script checks all six groups listed in the proof in about one second. Inside the repository it also compares the seven- and eight-speed tables with ../../results/*/sporadic.txt. It prints one line per group and exits with status 0 only if every check passes.
An independent brute-force scan, search/bruteforce_scan.py, uses neither the spectrum classifications nor the certificates. Its output is search/bruteforce_scan.txt. It decides the chromatic number of every primitive -set with maximum at most 80, 60, 48 and 42 for , using SAT. In that range it agrees with the theorem. It needs python-sat.
Files
PROOF.md: statement, lemmas, proof and sources.certificates.json: the 65 table sets with their exact , the 62 periodic colourings, the three shortest non-colourable intervals, the loop certificates for the families A5, A6, W2 and W3, and the base loops for the two-parameter family.verify.py: standard-library checker for everything in the certificate.search/: the SAT search scripts that produced the certificates, and the brute-force scan. None of them is needed to check the proof. Seesearch/NOTES.md.