The chromatic number of ℝ 8 \mathbb{R}^{8} is at least 25

Jaan Parts · 2026

Read The chromatic number of ℝ 8 \mathbb{R}^{8} is at least 25 by Jaan Parts (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14581.txt.

Introduction

Parts raises the lower bound for the chromatic number of eight-dimensional space to 25. The chromatic number counts the fewest colors for a space coloring. In such a coloring, points one unit apart must never share a color. A bound of 25 means every valid coloring of R^8 needs at least 25 colors. No coloring with 24 colors can exist. The new floor improves the best known value for dimension eight. It tightens the known range for this classic geometry problem.

Catalog record

CREATORJaan Parts
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23985
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14581

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The chromatic number of ℝ 8 \mathbb{R}^{8} is at least 25 Jaan Parts Abstract The lower bound for the chromatic number of the Euclidean space of dimension 8 is increased to 25. 1 We came in A good way to understand something is to try to improve it. Armed with this motto, I attempted to tackle the problem of proper coloring of Euclidean spaces in dimensions greater than two. 1 1 1 A coloring is called proper if any pair of points at (unit) forbidden distance from each other takes two different colors. We want to find the minimum possible number of colors, which is called the chromatic number \chi . There are many variations of this problem, but the simplest and most natural one is to consider it in spaces \mathbb{R}^{n} of different dimensions n . Here, we restrict ourselves to the case n=8 . Before this, I somehow got my bearings in three-dimensional space, but I still cannot imagine four-dimensional space, etc. The beauty of mathematics is that you don’t even need to imagine anything to work with it. And once you start working with it, it becomes familiar and not so scary. And this is a good step towards finally being able to imagine and understand it. Four years ago, I raised the lower bound of the chromatic number \chi(\mathbb{R}^{8}) by one. For a number of reasons (mainly laziness), this result remained unpublished. The previous record \chi(\mathbb{R}^{8})\geq 19 was obtained by Matthew Kahle and Birra Taha [ 5 ] . They started with the graph, constructed on 240 vertices of the Gosset polytope 4_{21} and having an independence number \alpha=16 . The idea was to add as many additional vertices to this graph as possible while maintaining the same \alpha . Recently, Aubrey de Grey reminded me of my research in connection with the development of his conjecture (see the Polymath16 project blog [ 9 ] ), and I promised to publish it. Upon checking my previous results, I discovered that I could make further progress. As a result, the hunt for graphs yielding record-breaking bounds for \chi(\mathbb{R}^{8}) dragged on for a month (and it took about the same amount of time to write this article). 2 Preliminaries Approach. The lower bound for the chromatic number of a Euclidean space of dimension 8 (and higher) is usually estimated using a finite graph with v vertices and independence number \alpha : \displaystyle\chi\geq\lceil v/\alpha\rceil This relation follows directly from Dirichlet’s (pigeonhole) principle: since \alpha is the maximum number of vertices in a graph that can be properly colored with a single color, it is clear that to color the entire graph, one must take at least \lceil v/\alpha\rceil sets of vertices of different colors. Clearly, this estimate of \chi is quite weak, but we currently lack stronger estimates. All that is required to obtain a lower bound for \chi(\mathbb{R}^{n}) is a graph for which one can calculate the exact value of the independence number \alpha or at least estimate its upper bound. An essential element of the approach under consideration is a solver , that is, a computer program that calculates the value of \alpha for a graph. On the one hand, the presence of a solver allows us to somewhat improve the estimates of \chi(\mathbb{R}^{n}) . On the other hand, it apparently limits the applicability of this approach to low-dimensional spaces, say n\leq 10 . The resulting graphs with relatively large v/\alpha are asymmetric, making their manual analysis difficult. To construct such a (good) graph, a promising symmetric core with a sufficiently large number of vertices v and a presumably high \chi is selected, to which, using a good strategy, the vertices are added to maximize the v/\alpha ratio. Apparently, the added vertices do not so much influence the actual \chi value of the graph, as they fill vacant places (by lengthening short independent sets) at a fixed \alpha . Unfortunately, we don’t know how to do all these good things. All we can do is try to guess a slightly better solution based on general considerations and experience gained from sifting through a large number of graphs. Tools. To calculate the independence number \alpha , we used exact solvers that determine the size of the maximum clique of the graph complement: cliquer [ 8 ] , mcqd [ 6 , 11 ] , and clisat [ 10 ] . To speed up the calculations of \alpha on large graphs, we used the suboptimal solver kamis [ 7 ] , after which we verified the obtained values using exact solvers. The upper bound for the chromatic number \chi was determined using the SAT-solver yalsat [ 1 ] . Notation. One of our goals was to provide a simple description of the resulting graphs, so that they demonstrate structure rather than just a jumble of coordinates. We partially succeeded. The forbidden distance is set to 4, which excludes fractional values. The coordinates of individual vertices are specified in full. To denote sets of vertices with coordinates that differ in sign and sequence, we use a shorthand notation common to all vertices in the set. We have slightly modified the notation used in the excellent book [ 3 ] by John Conway and Neil Sloane to better reflect the peculiarities of our graphs. In our shorthand notation, the superscript indicates the number of repeating values and the subscript indicates fixed coordinate positions, which are listed without commas. For some values, the superscript may be omitted if it can be unambiguously reconstructed from the context. If the subscript is omitted, all coordinate permutations that do not contradict the fixed positions are used. The signs are specified explicitly. The \pm sign indicates that both signs are used. The prefixes e and o denote an even and odd number of minus signs. The number of vertices in the set is indicated in parentheses. For example, the coordinates of all 240 vertices of the Gosset polytope 4_{21} in the even coordinate system of the E_{8} lattice are written as follows: \pm 2^{2}\,0^{6} (112), e1^{8} (128). The additional 49 vertices of 289-vertex Kahle-Taha graph [ 5 ] have the form \pm 2^{4}\,0^{4} (40), e1^{4}\,0^{4} (6), +3^{1}\,o1^{7} (3). For our purposes, it is convenient to replace the first coordinate x_{1} with (2-x_{1}) . In this case, the vertices of the Gosset polytope are 0_{1}\!\pm\!2^{1}\,0^{6} (14), +2_{1}\!\pm\!2^{2}\,0^{5} (84), +4_{1}\!\pm\!2^{1}\,0^{6} (14), +1_{1}\,e1^{7} (64), +3_{1}\,o1^{7} (64). The same notation can be used for individual vertices. For example, (+2_{1}\,0^{7})=(+2_{1}^{1}\,0^{7})=(2,0,0,0,0,0,0,0);\;\;(+2_{468}\,0^{5})=(+2_{468}^{3}\,0^{5})=(0,0,0,2,0,2,0,2) . 3 Why dont’t we do it in the road? \chi(\mathbb{Q}^{8})\geq 20 . Following Kahle and Taha, we started with the base graph G_{240} , constructed on the vertices of the Gosset polytope 4_{21} . Without changing \alpha=16 , we were able to increase the number of additional vertices to 64 (while remaining in the E_{8} lattice). However, this did not lead to an increase in the lower bound for the chromatic number \chi(\mathbb{Q}^{8})\geq\lceil 304/16\rceil=19 . The breakthrough was just one vertex away (and this motive haunted us later, driving us to continue the search). We made progress when we dropped the constraint on \alpha being fixed. With \alpha=17 , we obtained a 327-vertex graph G_{327} (leaving the E_{8} lattice). This

Read the complete text