Lean status: the complete relative deduction and all explicit coloring certificates are now formalized and kernel-replayed. The four spectrum hypotheses remain explicit and unproved by this closure. See the landing page for exact scope and evidence.
Status. Written proof with machine-checkable certificates and a partial Lean formalization. Unrefereed. The main theorem is proved relative to four classification theorems of this repository (the loneliness spectra below for speeds), which are themselves computer-assisted and unrefereed. Every other step is proved below or checked by verify.py, which needs only the Python standard library.
Statement
For a finite set of positive integers, the integer distance graph has vertex set , and are adjacent when . Write for its chromatic number and for its clique number. Multiplying by a positive integer replaces by disjoint copies of itself, so we may assume . Always : colour the integers greedily in the order , so that each integer has at most coloured neighbours when its turn comes. [W90] [CCH97]
Zhu conjectured that a triangle-free with has [Zhu02, Conjecture 4.1, as quoted in OS24]. A stronger statement, attributed to Zhu in [BS05] and formulated by Liu and Zhu [LZ04, Conjecture 5.3, as quoted in OS24], asks whether forces a clique of order . Oravcová and Soták disproved the stronger statement by an infinite family with and , and proposed the following replacement [OS24].
Conjecture (Oravcová and Soták, Conjecture 2.7). Let and . Then , or for some , or .
The conjecture is known for . For three distances, exactly for and for with [V99] [Zhu02]. For four distances, exactly for and for with even and odd [KM01a] [BS05] [BS08]. All of these sets have .
For more distances only bounded evidence was available. Oravcová and Soták report a computer check of all sets with and , where , and they announce related work on distance sets with and tight lonely-runner vectors [OS24] [OS07]. Theorem A removes the bound on for five to eight distances.
Theorem A (relative to the spectrum classifications R5–R8 below). Let and let be a set of positive integers with . Then if and only if is one of the following sets.
- for an integer .
- and or .
- and .
Every other primitive with has . The "if" direction does not depend on R5–R8; only the "only if" direction does.
Corollary. Relative to R5–R8, Conjecture 2.7 holds for . Indeed the sets in item 1 contain the clique , so , and the sets in items 2 and 3 are and the members of the Oravcová–Soták family. Zhu's triangle conjecture for five to eight distances, already recorded in this repository (in the five-, seven- and eight-speed notes; the six-distance case is in the seven-speed note), also follows, since every set in the theorem contains a triangle.
The four inputs are the following theorems of this repository. Write , where is the distance to the nearest integer, and call a primitive -set near-tight when .
- R5 (five-speed spectrum). A near-tight primitive 5-set contains a dilation of or of , or is one of twelve listed sets.
- R6 (six-speed spectrum). A near-tight primitive 6-set is, up to order and signs, of the form , or , or is one of nine listed sets.
- R7 (seven-speed spectrum). The near-tight primitive 7-sets are , , and 27 listed sets.
- R8 (eight-speed spectrum). Every near-tight primitive 8-set is one of 17 listed sets or has the form , , with .
The 65 listed sets are reproduced, with their values of , in certificates.json.
Two remarks make these statements usable below. First, if a primitive 5-set contains with and , then is an integer, so with , and because . Second, in R6 a primitive tuple on a family is, up to order and signs, the value of the parameterization at real . Since and are themselves coordinates up to sign, they are integers, and every coordinate is an integer combination of them, so . Thus the two product families of R6 are with , coprime, and the third family consists exactly of the sets with coprime integers and six distinct nonzero values.
Lemmas
Lemma 1 (colouring from a lonely time). If then .
Choose with for every , and colour by . If and have the same colour, the fractional parts of and lie in one half-open interval of length , so and . This is the standard link between the lonely runner parameter and distance graphs [BS08] [Cz12, §3] [PS25, §3.5]. The same colouring gives the triangle-conjecture corollaries recorded with R5, R7 and R8.
Consequently every primitive -set with is near-tight. This reduces Theorem A to the sets named in R5–R8.
Lemma 2 (the clique family). For and , .
The upper bound is the general one. Suppose is a proper -colouring. Any consecutive integers are pairwise adjacent, so they receive all colours. Comparing the windows and gives for every . Then , although . This is well known; the case is in [KM01a].
Lemma 3 (product families). Let , let be a set of positive integers none of which is divisible by , and let be coprime integers. If or , then .
Put , so for . If and , the time works. If , consider the times for . Every speed has phase modulo one. The phases run over a full coset of because . Such a coset meets the closed arc of length centred at , which gives a time with . The same averaging over the times is used for product planes in the eight-speed note.
Lemma 4 (loops). Fix a number of colours and a finite set of positive integers with . A word over is -proper if whenever and . Let be a word of length . A loop of length at is an -proper word of length whose first letters and last letters both spell .
- If is a loop of length at , then is a proper -colouring of of period .
- If and are loops at the same of lengths and , then is a loop of length at .
Hence the set of loop lengths at a fixed is closed under addition, and each of its elements is the period of a proper -colouring of .
Proof. (1) The last letters repeat the first , that is for . By induction for all . Given and , put . Then , so .
- Let be the concatenated word, of length . Since begins with , which is also the end of , the word agrees with on positions and with on positions . A pair of positions with lies in the second window if and in the first window otherwise. So is -proper. It begins with the first letters of and ends with the last letters of , both equal to .
Lemma 5 (one extra distance). Let be a proper colouring of with period . If or , then is a proper colouring of .
Indeed .
Corollary 5′. Suppose that, for and colours, every integer greater than is a loop length at some fixed word . Then for every integer : use a colouring of period .
A finite list of periods can never handle all , since may be divisible by every period on the list. Loops remove this obstruction by supplying every large period.
Lemma 6 (base change). Let be finite and put . Let be coprime integers and , with and , and put . Suppose and has a proper -colouring of period , that is, for all . Then .
Proof. Every integer is for some integers , and the other representations are . Define . Changing the representation changes the argument by , a multiple of , so is well defined. If , then with and , and because .
In words: since , the map identifies with , so is the quotient of the Cayley graph of with connection set by the subgroup generated by . A colouring of one such quotient that is periodic with the right period descends to another.
Proof of Theorem A
The listed sets have . Item 1 is Lemma 2. For items 2 and 3, Oravcová and Soták prove and [OS24, Theorems 2.1 and 2.2]. Independently, verify.py checks by exhaustive search that the subgraph of induced on has no proper -colouring for
These are the shortest such intervals: the intervals one shorter are colourable. The searches are tiny. Colouring the vertices in increasing order and introducing new colours in increasing order, the verifier makes 36, 171 and 102 colour assignments.
All other sets have . Let be a primitive -set with . By Lemma 1 it is near-tight. We go through R5–R8.
Listed sets. Of the listed sets, three are the sets of items 2 and 3. For each of the other 62, certificates.json contains a word such that is a proper -colouring of . The periods range from 8 to 28. verify.py checks every word.
Product families. In the product families of R5 and R6 the set has the form with , where is or for , and or for . No element of these is divisible by . By Lemma 3 and near-tightness, and . In R7 and R8 the families are stated in this form already. If this is item 1. Four families remain:
| Name | auxiliary | certified loop lengths (generators of ) | largest gap of | needing a direct colouring | ||
|---|---|---|---|---|---|---|
| A5 | 5 | 15 | 16, 19, 24, 27, 30, 33, 34, 36, 37, 41, 42, 44, 45, 47 | 39 | 5, 10 | |
| A6 | 6 | 7 | 8, 10, 14, 21, 23, 27 | 25 | 6, 12, 18 | |
| W2 | 8 | 10 | 8, 14, 23, 43 | 49 | 8, 16 | |
| W3 | 8 | 8 | 21, 24, 26, 30, 33, 36, 38, 39, 40, 41, 43, 44, 46 | 58 | 8, 24 |
For each row the certificate gives a word of length and one loop at , for and colours, of each listed length. verify.py checks the loops and computes the numerical semigroup they generate. Its largest gap is . By Lemma 4 every positive element of is a loop length. By Corollary 5′, for all . For the finitely many , Lemma 5 applies with or whenever one of these lies in . No element of is divisible by , so is never in . The few remaining are in the last column, and for each the certificate contains an explicit periodic proper -colouring of . So every member of these four families has .
The two-parameter family for . Let , so that the third family of R6 consists of the sets with coprime integers and six distinct nonzero values . The six vectors
all satisfy . For and six colours, the certificate contains loops of lengths 6, 10, 29 and 43 at the word :
6 05123405123405
10 051234051205123405
29 0512340534052134213054203451205123405
43 051234051405231403140523152340154015234023405123405
The semigroup generated by 6, 10, 29, 43 contains every integer , and 37 is its largest gap. By Lemma 4, has a proper 6-colouring of period for every in this semigroup. Apply Lemma 6 with , where , and with , where . If either number is at least 38, then . Otherwise and , which forces and . Since and , we may take . There are 334 such coprime pairs with six distinct nonzero values. For each of them verify.py finds one of the six vectors above for which lies in the semigroup, and also builds the resulting colouring and checks it directly. So every member of the family is 6-colourable.
This exhausts R5–R8 and proves the theorem.
Verification
Run from this directory, or from the repository root with the path adjusted:
python3 verify.pyThe verifier reads certificates.json and checks the following, using integers and exact fractions only.
- Tables. Each of the 65 listed sets is sorted, primitive and of the right size, and the exact value of , recomputed from the candidate times , equals the listed value and is below . When run inside the repository, the seven- and eight-speed tables are compared with
sporadic.txtof the corresponding results. - Sporadic colourings. Each of the 62 periodic words is a proper -colouring.
- Exceptional sets. Exhaustive search on the three intervals above finds no proper -colouring, and finds one on each interval one shorter.
- One-parameter families. For A5, A6, W2, W3: every loop is -proper with the stated prefix and suffix; the semigroup has the stated largest gap; every is covered by or in , or by a valid direct colouring; no element of is divisible by . For every covered the verifier also assembles the loop by concatenation and checks the periodic colouring of directly.
- Two-parameter family. The six base vectors give ; the four loops are valid; the semigroup contains ; all 334 pairs in the finite region are covered, and for each the colouring of Lemma 6 is built and checked directly.
- Lemma 2 on small cases. A brute-force sanity check that has no proper -colouring on a short interval, for and small .
The loops and colourings were found with a SAT solver. The search scripts are in search/ and need python-sat. They are not needed to check the proof.
Independent evidence
A separate scan, search/bruteforce_scan.py, uses neither R5–R8 nor the certificates. For every primitive -set with it either exhibits a periodic proper -colouring, checked directly, or obtains from a SAT solver that some interval has no proper -colouring. Its output is search/bruteforce_scan.txt.
| primitive -sets | not coloured by a rotation word | not -colourable | ||
|---|---|---|---|---|
| 5 | 80 | 23,312,716 | 44 | 18 |
| 6 | 60 | 49,430,584 | 118 | 10 |
| 7 | 48 | 73,271,500 | 28 | 7 |
| 8 | 42 | 117,823,691 | 29 | 5 |
In every row the non-colourable sets are exactly those of Theorem A in that range: the sets with and the three exceptional sets. A rotation word is the colouring of Lemma 1 at a rational time, so the fourth column counts the near-tight sets in range. Each of them is a family member or a table row of R5–R8, which is an independent check of those classifications in these ranges. The same scan confirms the quoted classifications for three distances () and four distances (). The scan trusts the SAT solver's negative answers; the three exceptional sets are also covered by the solver-free search of verify.py.
What is new and what is used
New here, to our knowledge: the complete classification of Theorem A for with no bound on (relative to R5–R8), hence Conjecture 2.7 in these cases; and the loop and base-change certificates, which settle four infinite one-parameter families and one two-parameter family that no finite list of periods can cover. Not new: within the ranges the conjecture had been checked by computer in [OS24], so colourings of the listed sets in those ranges were known to exist.
Used from the literature and from this repository: the conjecture and the chromatic numbers of the exceptional sets [OS24]; the bound [W90] [CCH97]; the colouring of Lemma 1 [BS08] [Cz12]; Lemma 2 (folklore; [KM01a] for ); the classifications R5–R8 and the averaging over the times in Lemma 3 (this repository, which builds on Cordella, on Yi, Gill and Bu, on Kravitz, on Fan and Sun, and on Jain and Kravitz, as cited there). Lemmas 4–6 are elementary; we do not know a reference for them in this form. The Cayley-graph viewpoint behind Lemma 6 is related to that of [CK23], which we did not use.
The next case, nine distances, needs a classification of the near-tight 9-sets. Lemma 2 and [OS24, Theorem 2.2] give for and for ; Conjecture 2.7 says that every other primitive 9-set with has a clique of order nine.
Sources
Entries marked † were not consulted directly; their content is quoted through the source named in the entry.
- [OS24] J. Oravcová and R. Soták, On a problem concerning integer distance graphs, arXiv:2401.12347 (2024). Question A; Conjecture 2.7; Theorems 2.1 and 2.2; the computer check for ; the survey of the cases .
- [W90] † H. Walther, Über eine spezielle Klasse unendlicher Graphen, in K. Wagner and R. Bodendiek (eds.), Graphentheorie, Bd. 2, Bibl. Inst., Mannheim, 1990, 268–295. The bound . Through [OS24].
- [CCH97] J.-J. Chen, G. J. Chang and K.-C. Huang, Integral distance graphs, J. Graph Theory 25 (1997), 287–294. Also proves (abstract).
- [V99] † M. Voigt, Colouring of distance graphs, Ars Combin. 52 (1999), 3–12. Three distances. Through [OS24].
- [Zhu02] † X. Zhu, Circular chromatic number of distance graphs with distance sets of cardinality 3, J. Graph Theory 41 (2002), 195–207. Three distances; the triangle conjecture (Conjecture 4.1). Through [OS24] and [BS05].
- [KM01a] † A. Kemnitz and M. Marangio, Chromatic numbers of integer distance graphs, Discrete Math. 233 (2001), 239–246. for and with odd. Through [OS24].
- [KM01b] † A. Kemnitz and M. Marangio, Colorings and list colorings of integer distance graphs, Congr. Numer. 151 (2001), 75–84. Characterization of the sets with (not needed for the proof). Through [OS24].
- [LZ04] † D. D.-F. Liu and X. Zhu, Fractional chromatic number and circular chromatic number for distance graphs with large clique size, J. Graph Theory 47 (2004), 129–146. The clique form of the conjecture (Conjecture 5.3). Through [OS24].
- [OS07] J. Oravcová (joint work with R. Soták), Integer distance graphs and Lonely runners: tight sets and tight vectors, abstract of a talk, Workshop Cycles and Colourings, Tatranská Štrba, September 2007, umv.science.upjs.sk/preprints/dokumenty/A8-2007.pdf. Relates sets with to tight lonely-runner vectors; cited as a preprint in [OS24]. We found only the abstract.
- [BS05] J. Barajas and O. Serra, Distance graphs with maximum chromatic number, EuroComb 2005, DMTCS Proc. AE (2005), 171–174, dmtcs.episciences.org/3391. Abstract: the clique form of Zhu's conjecture and the classification for four distances.
- [BS08] † J. Barajas and O. Serra, Distance graphs with maximum chromatic number, Discrete Math. 308 (2008), 1355–1365, doi:10.1016/j.disc.2007.07.061. Journal version; the lonely runner method. Through [BS05] and this repository.
- [Cz12] S. Czerwiński, Random runners are very lonely, J. Combin. Theory Ser. A 119 (2012), 1194–1199, arXiv:1102.4464. Section 3 states the colouring of Lemma 1.
- [PS25] G. Perarnau and O. Serra, The Lonely Runner Conjecture turns 60, arXiv:2409.20160. Survey; Section 3.5 on chromatic numbers of distance graphs.
- [CK23] J. Cervantes and M. Krebs, A generalization of Zhu's theorem on six-valent integer distance graphs, arXiv:2303.06276; the arXiv page lists a journal DOI, 10.1016/j.disc.2025.114496 (not checked further). Related Cayley-graph viewpoint; not used.
- [R5]–[R8] This repository: five-speed, six-speed, seven-speed and eight-speed spectrum classifications, with the sources cited there (Cordella, arXiv:2609.03444; Yi, Gill and Bu, arXiv:2610.40694; Kravitz; Fan and Sun; Jain and Kravitz).