# Upper Bounds on Chromatic Number of $E^n$ in Low Dimensions

Andrii Arman, Andriy Bondarenko, Andriy Prymak, Danylo Radchenko

► To cite this version:

Andrii Arman, Andriy Bondarenko, Andriy Prymak, Danylo Radchenko. Upper Bounds on Chromatic Number of $E^n$ in Low Dimensions. The Electronic Journal of Combinatorics, 2024, 31 (2), pp.27. 10.37236/11794 . hal-04789024

HAL Id: hal-04789024

https://hal.science/hal-04789024v1

Submitted on 18 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Upper bounds on chromatic number of $\mathbb{E}^n$ in low dimensions

Andrii Arman<sup>a</sup>

Andriy Bondarenko<sup>b</sup>

Andriy Prymak<sup>a</sup>

Danylo Radchenko<sup>c</sup>

Submitted: Jan 13, 2023; Accepted: Apr 6, 2024; Published: May 31, 2024

© The authors. Released under the CC BY-ND license (International 4.0).

## Abstract

Let $\chi(\mathbb{E}^n)$ denote the chromatic number of the Euclidean space $\mathbb{E}^n$, i.e., the smallest number of colors that can be used to color $\mathbb{E}^n$ so that no two points unit distance apart are of the same color. We present explicit constructions of colorings of $\mathbb{E}^n$ based on sublattice coloring schemes that establish the following new bounds: $\chi(\mathbb{E}^5) \le 140$, $\chi(\mathbb{E}^n) \le 7^{n/2}$ for $n \in \{6, 8, 24\}$, $\chi(\mathbb{E}^7) \le 1372$, $\chi(\mathbb{E}^9) \le 17253$, and $\chi(\mathbb{E}^n) \le 3^n$ for all $n \le 38$ and $n \in \{48, 49\}$.

**Mathematics Subject Classifications:** 05C15, 11H31, 05B40, 52C17

## 1 Introduction

We denote by $\chi(A)$ the chromatic number of $A \subset \mathbb{E}^n$, which is the least number of colors needed to color $A$ so that any two points distance one apart receive different colors. Determining $\chi(\mathbb{E}^n)$ is a very challenging question, which is solved only for the trivial case $n=1$, where $\chi(\mathbb{E}^1) = 2$. For $n=2$ this problem is known as Hadwiger-Nelson problem. Using a hexagonal tiling, it is not hard to show $\chi(\mathbb{E}^2) \le 7$, and the current best lower bound $\chi(\mathbb{E}^2) \ge 5$ was obtained only relatively recently by de Grey [10].

There has been considerable attention paid to the lower estimates of $\chi(\mathbb{E}^n)$ for small $n$, see, e.g. [5, Sect. 5.9], [16] or [3], and the references therein. However, it appears that the upper estimates are almost unstudied. In this work we establish a number of new upper bounds on $\chi(\mathbb{E}^n)$ and hope to encourage further research in this direction.

Asymptotically as $n \to \infty$ the best known bounds on $\chi(\mathbb{E}^n)$ are

$$ (1.239 + o(1))^n \le \chi(\mathbb{E}^n) \le (3 + o(1))^n, $$

<footnote><sup>a</sup>Department of Mathematics, University of Manitoba, Winnipeg, MB, R3T 2N2, Canada (andrew0arman@gmail.com, prymak@gmail.com).</footnote>

<footnote><sup>b</sup>Department of Mathematical Sciences, Norwegian University of Science and Technology, NO-7491 Trondheim, Norway (andriybond@gmail.com).</footnote>

<footnote><sup>c</sup>Laboratoire Paul Painleve, University of Lille, F-59655 Villeneuve d'Ascq, France (danradchenko@gmail.com)</footnote>
obtained by Raigorodskii [19] and Larman and Rogers [13], respectively, where the $o(1)$ terms are not quantified. Based on the work of Prosanov [17] the $o(1)$ term in the upper bound can be specified to be $\chi(\mathbb{E}^n) \le (1 + o(1))n \ln n 3^n$, see Section 5.

Let us summarize the previously best known upper bounds on $\chi(\mathbb{E}^n)$ for small dimensions. The bound $\chi(\mathbb{E}^3) \le 15$ was established by Coulson [7] and, independently, by Radoičić and Tóth [18]. Both constructions were based on coloring the interiors of Voronoi cells of a certain lattice $\Lambda$ with the same color (for a brief background on lattices the reader may consult Section 2). The choice of the color, however, was performed differently: in [7], coset membership w.r.t. a sublattice $\Lambda'$ was used (sublattice coloring scheme), while in [18] a linear mapping from the lattice to $\mathbb{Z}_{15}$ was used (linear coloring scheme). Extensions to $n = 4$ were mentioned without proofs: $\chi(\mathbb{E}^4) \le 54$ in [18], and $\chi(\mathbb{E}^4) \le 49$ in [8]. We prove that $\chi(\mathbb{E}^4) \le 49$ in Theorem 3.

We note that the standard two-colouring of $\mathbb{E}^1$ and the hexagonal 7-colouring of $\mathbb{E}^2$ are both sublattice colouring schemes as well as they are examples of linear coloring schemes. Additionally, every linear coloring scheme is a sublattice coloring scheme. However, the sublattice coloring scheme according to $\Lambda' = 2\Lambda$ is not in general a linear coloring scheme.

The technique of Radoičić and Tóth [18], i.e. linear coloring schemes based on $A_n^*$ lattice, was studied with computer assistance for the cases $n = 5$ and $n = 6$ by the contributors "ag24ag24" (de Grey) and "Philip Gibbs" in Polymath 16 project discussion [15]. Namely, it was announced that $\chi(\mathbb{E}^5) \le 156$ and $\chi(\mathbb{E}^6) \le 448$.

Using computer assistance, we found sublattice coloring schemes for the lattices $A_5^*$, $E_7^*$ and $A_9^*$ yielding the following result.

**Theorem 1.** $\chi(\mathbb{E}^5) \le 140$, $\chi(\mathbb{E}^7) \le 1372$, $\chi(\mathbb{E}^9) \le 17253$.

Our next result relies on the following fact: if there exists a lattice $\Lambda$ in $\mathbb{E}^n$ with covering-packing ratio not exceeding 2 (see Section 2 for definitions), then a sublattice coloring scheme (with a sublattice $3\Lambda$) gives $\chi(\mathbb{E}^n) \le 3^n$. Using known results on laminated lattices and a certain inequality estimating the covering radius, we obtained the following.

**Theorem 2.** $\chi(\mathbb{E}^n) \le 3^n$ for any $n \le 38$ and for $n \in \{48, 49\}$.

For even dimensions where there exists a lattice with covering-packing ratio at most 3/2, and some additional properties are known, we can do much better using an appropriate representation of such a lattice as an Eisenstein lattice (a complex lattice over the ring $\mathbb{Z}[e^{2\pi i/3}]$). This approach also recovers the known bounds for $n = 2$ and $n = 4$ in a unified way.

**Theorem 3.** $\chi(\mathbb{E}^n) \le 7^{n/2}$ for $n \in \{2, 4, 6, 8, 24\}$.

We remark that the proofs of Theorems 2 and 3 do not require computer assistance. We also note, that Theorem 3 gives the upper bound $\chi(\mathbb{E}^{24}) \le 7^{12}$ which also implies the bounds $\chi(\mathbb{E}^n) \le 7^{12}$ for $n \in \{22, 23\}$. In these dimensions, $7^{12}$ is smaller than the upper bound $3^n$ that can be obtained from Theorem 2.
The current best known upper bounds on $\chi(\mathbb{E}^n)$ for small $n$, including the results obtained in this paper, are summarized in Table 1. Note that the gap between the lower (see, e.g. [16, Section “Best known results for the chromatic number in higher dimensions”]) or [3, Table 1]) and the upper bounds on chromatic number is large and grows very quickly, namely, for the first few $n$ the known estimates are: $6 \le \chi(\mathbb{E}^3) \le 15$, $9 \le \chi(\mathbb{E}^4) \le 49$, $9 \le \chi(\mathbb{E}^5) \le 140$, $12 \le \chi(\mathbb{E}^6) \le 343$, $16 \le \chi(\mathbb{E}^7) \le 1372$, $19 \le \chi(\mathbb{E}^8) \le 2401$.

<table><caption>Table 1: Upper bounds on $\chi(\mathbb{E}^n)$ for small $n$</caption><thead><tr><th>n</th><th>χ(ℝ<sup>n</sup>) ≤</th><th>references</th></tr></thead><tbody><tr><td>2</td><td>7</td><td>John Isbell, see [23, p. 29]</td></tr><tr><td>3</td><td>15</td><td>[7], [18]</td></tr><tr><td>4</td><td>49</td><td>mentioned in [8];<br>proof in Theorem 3</td></tr><tr><td>5</td><td>140</td><td>Theorem 1</td></tr><tr><td>6</td><td>343</td><td>Theorem 3</td></tr><tr><td>7</td><td>1372</td><td>Theorem 1</td></tr><tr><td>8</td><td>2401</td><td>Theorem 3</td></tr><tr><td>9</td><td>17253</td><td>Theorem 1</td></tr><tr><td>10 ≤ n ≤ 21</td><td>3<sup>n</sup></td><td>Theorem 2</td></tr><tr><td>22 ≤ n ≤ 24</td><td>7<sup>12</sup></td><td>Theorem 3</td></tr><tr><td>25 ≤ n ≤ 38, n = 48, 49</td><td>3<sup>n</sup></td><td>Theorem 2</td></tr></tbody></table>

We give the necessary preliminaries in the next section. Theorem 1 is proved in Section 3, Theorems 2 and 3 are proved in Section 4. In Section 5 we deduce an upper bound on $\chi(\mathbb{E}^n)$ valid in all dimensions $n$. The concluding Section 6 lists some open questions.

The code and the datasets used in the proof of Theorem 1 are available in the GitHub repository, https://github.com/andriyprm/ubcnessd/releases/tag/v1.

# 2 Preliminaries

For $x, y \in \mathbb{E}^n$, we denote by $x \cdot y$ the dot product in $\mathbb{E}^n$ and by $|x| := (x \cdot x)^{1/2}$ the Euclidean norm of $x$. For two sets $A, B \subset \mathbb{E}^n$ we set $\text{dist}(A, B) := \inf\{|x - y| : x \in A, y \in B\}$ and extend the notation to the one-point sets by $\text{dist}(A, b) := \text{dist}(A, \{b\})$. We also define $\mathcal{B}(R) := \{x \in \mathbb{E}^n : |x| < R\}$ and $\mathcal{B}[R] := \{x \in \mathbb{E}^n : |x| \le R\}$.

## 2.1 Lattices

For a real $m \times n$ matrix $M$ of rank $n$, a *lattice* $\Lambda$ generated by $M$ is the set $\Lambda = M\mathbb{Z}^n$. The *rank* of a lattice $\Lambda$ is $n$, and if $M$ is a full rank square matrix, then $\Lambda$ is said to be *full rank*.
A lattice $\Lambda \subset \mathbb{E}^m$ forms a discrete additive subgroup in $\mathbb{E}^m$. An additive subgroup of $\Lambda$ is called a sublattice. It is not hard to see that $\Lambda'$ is a sublattice of $\Lambda$ generated by $M$ if and only if $\Lambda' = MCZ^n$ for some $m \times m$ integer matrix $C$. The index of $\Lambda'$ (with respect to $\Lambda$) is an index of $\Lambda'$ as a subgroup of $\Lambda$. We use the notation $|\Lambda/\Lambda'|$ for the index and note that it is equal to $|\det C|$, provided $C$ is not singular.

For a lattice $\Lambda$ generated by a matrix $M$, a fundamental parallelepiped $P$ is an image of $[0, 1]^n$ under $M: \mathbb{E}^n \to \mathbb{E}^m$. If $M$ is a full rank square matrix, then $\Lambda + P$ tessellates $\mathbb{E}^n$.

The Voronoi cell of a lattice $\Lambda$ around the origin is the set

$$V = V(\Lambda) = \{x \in \mathbb{E}^m : |x| \le |x - z| \text{ for all } z \in \Lambda\}.$$

If $M$ is a full rank square matrix, then the Voronoi cell $V = V(\Lambda)$ is a convex centrally-symmetric body, such that $\Lambda + V$ tessellates $\mathbb{E}^m$. Since the inequalities $x \cdot z \le |z|^2/2$ and $|x| \le |x - z|$ are equivalent, $V$ can be represented as the intersection of half spaces

$$V = \bigcap_{z \in \Lambda \setminus \{0\}} \{x : |x| \le |x - z|\} = \bigcap_{z \in \Lambda \setminus \{0\}} \{x \in \mathbb{E}^m : x \cdot z \le |z|^2/2\}. \quad (1)$$

The norm of the lattice $\Lambda$ is the length of the shortest nonzero vector in $\Lambda$.

Let $\Lambda$ be a full rank lattice in $\mathbb{E}^n$. The packing radius of $\Lambda$ is the largest $r$ such that $\Lambda + \mathcal{B}(r)$ is a disjoint union of balls in $\mathbb{E}^n$, i.e. balls $\mathcal{B}(r)$ centered at points of $\Lambda$ pack into $\mathbb{E}^n$. The covering radius of $\Lambda$ is the minimum over all $R$ such that $\Lambda + \mathcal{B}[R] = \mathbb{E}^n$, i.e. the balls $\mathcal{B}[R]$ centered at points of $\Lambda$ cover the entire $\mathbb{E}^n$. The ratio between the covering and the packing radii of $\Lambda$ is called the covering-packing ratio of $\Lambda$.

If $V$ is the Voronoi cell of a full rank $\Lambda$, then the packing radius of $\Lambda$ is the largest radius of a ball that can be inscribed in $V$ and covering radius is the smallest radius of a ball that contains $V$. Packing radius of any lattice $\Lambda$ is equal to half of the norm of $\Lambda$.

An interested reader is referred to [6] for further background on lattices.

## 2.2 Coloring almost all of the space

First we prove that sets of measure zero have no effect on the chromatic number $\chi(\mathbb{E}^n)$. We include the proof of this folklore result for completeness.

**Proposition 4.** Let $A$ be a set of Lebesgue measure zero in $\mathbb{E}^n$, then $\chi(\mathbb{E}^n) = \chi(\mathbb{E}^n \setminus A)$.

*Proof.* Assume the contrary, namely that $\chi(\mathbb{E}^n) > \chi(\mathbb{E}^n \setminus A)$. According to de Bruijn-Erdős theorem [9], there exists a finite geometric graph $G$ (edges are pairs of points distance 1 apart), such that $\chi(G) = \chi(\mathbb{E}^n)$. Fix a geometric embedding of the set of vertices of $G$ into $\mathbb{E}^n$, to which we will simply refer as $G$. Let $c$ be a proper coloring of $\mathbb{E}^n \setminus A$ into $\chi(\mathbb{E}^n \setminus A)$ colors. Then for any $x \in \mathbb{E}^n$, $x + G$ contains a point of $A$, since otherwise $G$ can be properly colored according to $c$. In particular, for every $x \in \mathcal{B}(1)$ there is some $v \in G$, such that $x + v \in A$, which implies that $x \in (v + \mathcal{B}(1)) \cap A - v$. Consequently,

$$\mathcal{B}(1) \subset \bigcup_{v \in G} ((v + \mathcal{B}(1)) \cap A - v).$$
Now, the measure of $\mathcal{B}(1)$ is nonzero and the measure of each $(v+\mathcal{B}(1))\cap A-v$ is zero. Since $G$ is finite, we derive a contradiction with the assumption that $\chi(\mathbb{E}^n) > \chi(\mathbb{E}^n \setminus A)$. $\square$

## 2.3 Sublattice coloring schemes

Let $\Lambda$ be a full rank lattice in $\mathbb{E}^n$, $\Lambda'$ be a sublattice of $\Lambda$, $V$ be the Voronoi cell of $\Lambda$ about the origin and int $(V)$ be the interior of $V$. A sublattice coloring $c(\Lambda, \Lambda')$ is a coloring of almost all of $\mathbb{E}^n$ into $|\Lambda/\Lambda'|$ colors in which each point of $v + \text{int}(V)$, where $v \in \Lambda$, is colored according to the equivalence class of $v$ in $\Lambda/\Lambda'$. Note that $\cup_{v \in \Lambda} (v+V)$ tessellates $\mathbb{E}^n$, so the uncolored set $\cup_{v \in \Lambda} (v + \partial V)$, where $\partial V$ is the boundary of $V$, has Lebesgue measure zero in $\mathbb{E}^n$, which makes Proposition 4 applicable for sublattice colorings. More precisely, if we define the sublattice coloring chromatic number as

$$ \chi_s(\mathbb{E}^n, \Lambda, \Lambda', \ell) := \begin{cases} |\Lambda/\Lambda'|, & \text{if no two points distance } \ell \text{ apart receive the same colour} \\ \text{according to } c(\Lambda, \Lambda'), & \\ \infty, & \text{otherwise,} \end{cases} $$

then $\chi(\mathbb{E}^n) \le \chi_s(\mathbb{E}^n, \Lambda, \Lambda', \ell)$.

Coulson [7] used a weaker version of the following proposition to prove that $\chi(\mathbb{E}^3) \le 15$.

**Proposition 5.** Let $\Lambda$ be a full rank lattice in $\mathbb{E}^n$, $V$ be the Voronoi cell of $\Lambda$ about the origin and $R$ be the covering radius of $\Lambda$. If $\Lambda'$ is a sublattice of $\Lambda$ such that for any $v \in \Lambda' \setminus \{0\}$ we have $\text{dist}(V, v+V) \ge 2R$, then $\chi(\mathbb{E}^n) \le |\Lambda/\Lambda'|$.

*Proof.* We need to show that $\chi_s(\mathbb{E}^n, \Lambda, \Lambda', 2R) = |\Lambda/\Lambda'|$. Suppose to the contrary that according to $c(\Lambda, \Lambda')$ there exist monochromatic points $x$ and $y$ distance $2R$ apart. For each $v \in V$ we have that $v + \text{int}(V)$ is a subset of the ball $v + \mathcal{B}(R)$ of diameter $2R$. So for some different $v, u \in \Lambda$ we have $x \in v + \text{int}(V)$ and $y \in u + \text{int}(V)$. Then, according to the construction of $c(\Lambda, \Lambda')$, we must have $v-u \in \Lambda'$. We obtain a contradiction since $2R \le \text{dist}(V, v-u+V) = \text{dist}(v+V, u+V) < |x-y| = 2R$, where the last inequality is strict since $x$ belongs to $v+\text{int}(V)$. $\square$

**Proposition 6.** If there exists a full rank lattice $\Lambda$ in $\mathbb{E}^n$ with covering-packing ratio not exceeding 2, then $\chi(\mathbb{E}^n) \le 3^n$.

*Proof.* Without loss of generality, assume that the packing radius of $\Lambda$ is 1. Then the covering radius $R$ is at most 2. Let $V$ be the Voronoi cell of $\Lambda$ around the origin. For any $v \in \Lambda \setminus \{0\}$, we have $2V \subset \{t \in \mathbb{E}^n : t \cdot v/|v| \le |v|\}$ (see (1)). Therefore,

$$ \text{dist}(V, 3v + V) = \text{dist}(2V, 3v) \ge \text{dist}(\text{Proj}_v(3v), \text{Proj}_v(2V)) \ge \text{dist}(3v, v) = 2|v| \ge 4. $$

So $\text{dist}(V, 3v + V) \ge 2R$, and by Proposition 5 with $\Lambda' = 3\Lambda$ we get $\chi(\mathbb{E}^n) \le 3^n$. $\square$

**Remark 7.** It is well-known that in any dimension there exist lattices with covering-packing ratio less than 3 (see [2], [20]). In [12, Theorem 5.2.3] it was proved that lattices with covering-packing ratio not exceeding $\sqrt{21}/2 \approx 2.29$ exist in any dimension. By considering
such lattices, one can follow the lines of the proof of Proposition 6 (with $\Lambda' = 4\Lambda$) and show that in any dimension $\chi(E^n) \le 4^n$. This bound could be potentially better in small dimensions than the current best asymptotic upper bound $(3 + o(1))^n$.

Let $\omega = e^{2\pi i/3}$ be a primitive cubic root of unity, $\mathbb{E} = \mathbb{Z}[\omega]$ be the ring of Eisenstein integers. Recall [6, p. 54] that a $\mathbb{E}$-lattice (or Eisenstein lattice) is a set of the form

$$ \{\xi_1 v_1 + \dots + \xi_n v_n : \xi_1, \dots, \xi_n \in \mathbb{Z}[\omega]\} \subset \mathbb{C}^n, $$

where $v_1, \dots, v_n \in \mathbb{C}^n$ are some linearly independent vectors. Any $\mathbb{E}$-lattice can be regarded as a usual lattice of rank $2n$ in $\mathbb{E}^{2n}$ that has an automorphism of order 3 without nonzero fixed points, an automorphism given by the multiplication by $\omega$. Note that multiplication by a $a + b\omega$, where $a, b \in \mathbb{R}$, acts on a $\mathbb{E}$-lattice $\Lambda$ as a rotation followed by a homothety with the scaling factor $|a + b\omega| = \sqrt{a^2 - ab + b^2}$. Therefore if $\Lambda' = (a + b\omega)\Lambda$, then $|\Lambda/\Lambda'| = |a + b\omega|^{2n}$.

**Theorem 8.** If there exists a $\mathbb{E}$-lattice $\Lambda$ in $\mathbb{C}^n$ with covering-packing ratio not exceeding 3/2, then $\chi(E^{2n}) \le 7^n$.

*Proof.* Set $\Lambda' = \alpha\Lambda$, where $\alpha = 3 + \omega$. Let $V$ be the Voronoi cell of $\Lambda$ around the origin. Assume that the packing radius of $\Lambda$ is 1 and the covering radius of $\Lambda$ is $R \le 3/2$.

For $u, v \in \mathbb{C}^n$, let “·” denote the real inner product between vectors $u, v$ when those vectors are embedded in $\mathbb{E}^{2n}$. In other words, if $u, v$ are viewed as $1 \times n$ complex vectors, then $u \cdot v = \mathrm{Re}(u\bar{v}^T)$. With this notation, for any $v \in \Lambda \setminus \{0\}$, we have

$$ \begin{aligned} \mathrm{dist}(V, \alpha v + V) &= \mathrm{dist}(2V, \alpha v) \ge \mathrm{dist}(\mathrm{Proj}_v(\alpha v), \mathrm{Proj}_v(2V)) \\ &\ge \frac{(\alpha v) \cdot v}{|v|} - |v| = (\mathrm{Re}(\alpha) - 1)|v|. \end{aligned} $$

Recall that $\alpha = 3 + \omega$, so $\mathrm{dist}(V, \alpha v + V) \ge \frac{3}{2}|v| \ge 3 \ge 2R$. Since $\alpha = 3 + \omega$ has norm $\sqrt{7}$, we have $|\Lambda/\Lambda'| = 7^n$, and $\chi(E^{2n}) \le |\Lambda/\Lambda'| = 7^n$ by Proposition 5. $\square$

*Remark 9.* By using $2V \subset \{t \in \mathbb{E}^{2n} : t \cdot u \le |u|^2\}$ not only for $u = v$ but also for $u = -w^2v$, it is possible to prove the result of Theorem 8 under a slightly weaker assumption that the covering-packing ratio does not exceed $\sqrt{7}/3 \approx 1.5275$. We are not aware of any lattices that would utilize this strengthening, so we have chosen to present the weaker but simpler statement.

# 3 Computer assisted constructions for $n \in \{5, 7, 9\}$

In this section we prove Theorem 1 using sublattice coloring schemes by explicitly providing the required lattices and sublattices. The verification is computer assisted and will be described below together with the required mathematical content.

Proposition 5 is the main tool in our proof of Theorem 1. However, verifying the assumption “$\mathrm{dist}(v, v + V) \ge 2R$ for all $v \in \Lambda' \setminus \{0\}$” is computationally costly. Despite
this, if a symmetry group $G$ of lattice $\Lambda$ contains a family of reflections, then verification of the assumption “dist $(v, v+V) \ge 2R$ for all $v \in \Lambda' \setminus \{0\}$” can be reduced to taking $v$ only from a certain polyhedral convex cone $K$ generated by $G$. Moreover, the intersection $V_1$ of the Voronoi cell $V$ of $\Lambda$ with the cone $K$ is a polyhedron which may have significantly fewer faces than the Voronoi cell $V$ itself. So instead of verifying “dist $(v, v+V) \ge 2R$ for all $v \in \Lambda \setminus \{0\}$” we will verify a computationally cheaper assumption “dist $(v, v+V_1) \ge 2R$ for all $v \in K \cap \Lambda \setminus \{0\}$”. This approach is formally summarized in Lemma 10.

## 3.1 Verification and constructions

Working over the rational field allows us not to worry about precision in computations. However, to do that we sometimes need to consider rank $n$ lattices embedded in $\mathbb{E}^{n+1}$. We will consider lattices $A_5^*$, $E_7^*$, $A_9^*$ which, for a corresponding $n$, have only irrational bases in $\mathbb{E}^n$ but can be embedded with a rational basis in $\mathbb{E}^{n+1}$. For instance, a dilation of the triangular lattice $A_2^*$ can be embedded in $\mathbb{E}^3$ using a basis $(1, -1, 0)$, $(1, 0, -1)$, while in $\mathbb{E}^2$ it does not have a rational basis.

Let $\Lambda$ be a lattice of rank $n$ in $\mathbb{E}^m$, i.e. $\Lambda = M\mathbb{Z}^n$ for a $m \times n$ generator matrix $M$ of rank $n$. Let $X = M\mathbb{E}^n$ be the real subspace of $\mathbb{E}^m$ spanned by $\Lambda$, $V$ be the Voronoi cell of $\Lambda$ around the origin restricted to $X$ and $R$ be the covering radius of $\Lambda$.

We can extend (1) as follows:

$$V = \bigcap_{z \in \Lambda \setminus \{0\}} \{x \in X : x \cdot z \le |z|^2/2\} = \bigcap_{z \in \Lambda \setminus \{0\}, |z| \le 2R} \{x \in X : x \cdot z \le |z|^2/2\}. \quad (2)$$

We use certain symmetries available in the lattices under consideration. Suppose $H = \{x \in \mathbb{E}^m : x \cdot w = 0\}$, $|w| = 1$, is a hyperplane in $\mathbb{E}^m$ containing the origin. The reflection about $H$ is the isometry $R_w$ acting as $R_w(x) = x - 2(x \cdot w)w$.

**Lemma 10.** Suppose $W$ is a finite family of unit vectors in $\mathbb{E}^m$ such that $R_w(\Lambda) = \Lambda$ for any $w \in W$. Let $G$ be the group of isometries of $X$ generated by the reflections $\{R_w : w \in W\}$. Assume that the cone $K := \{x \in X : x \cdot w \ge 0 \forall w \in W\}$ has non-empty relative interior, and let $V_1 := K \cap V$. Then,

(i) for any $x \in X$ there exists $g \in G$ such that $g(x) \in K$ and $\text{dist}(V, x+V) = \text{dist}(V, g(x) + V)$.

(ii) for any $x \in K$ we have $\text{dist}(V, x+V) = 2 \text{dist}(V_1, x/2)$;

$$(iii) V_1 = \bigcap_{z \in K \cap \Lambda \setminus \{0\}, |z| \le 2R} \{x \in K : x \cdot z \le |z|^2/2\}.$$

*Proof.* We need the following facts, which are immediate by considering the squares of the required inequalities, and using the formula for $R_w(t)$:

(a) If $|w| = 1$, $z \cdot w > 0$ and $t \cdot w < 0$ (i.e. if $z$ and $t$ are on different sides of the hyperplane $\{x : x \cdot w = 0\}$), then $|z - t| > |z - R_w(t)|$.

(b) If $|w| = 1$, $z \cdot w \ge 0$ and $t \cdot w < 0$, then $|z - t| > |z - (R_w(t) + t)/2|$. (In geometric terms, $(R_w(t) + t)/2 = t - (t \cdot w)w$ is the projection of $t$ onto the hyperplane $\{x : x \cdot w = 0\}$.)
*Proof of (i).* Observe that $G$ is finite. Indeed, all elements of $G$ are isometries of $X$ (and of $\Lambda$). For any $R' > 0$, if $B(R')$ is the set of all bases of $\Lambda$ with maximal length of basis vectors not exceeding $R'$, then $B(R')$ is an invariant set under $G$. Now, since $B(R')$ is finite and every isometry is uniquely determined by the image of some fixed base, we may conclude that $G$ is finite. Similar arguments for establishing finiteness of $G$ can be found in the proof of [11, Lemma 4.3].

Let $z$ be any point in the relative interior of $K$, then $z \cdot w > 0$ for any $w \in W$. Given $x \in X$, let $g_0 \in G$ be such that $|z - g_0(x)| = \min\{|z - g(x)| : g \in G\}$. If $g_0(x) \in K$, we found the required $g = g_0$. Otherwise, there exists $w \in W$ such that $g_0(x) \cdot w < 0$. Then by (a), $|z - R_w(g_0(x))| < |z - g_0(x)|$, a contradiction with the choice of $g_0$. Hence, for $g = g_0$, we have $g(x) = g_0(x) \in K$.

Finally, since $V$ is origin-symmetric, $\text{dist}(V, x+V) = \text{dist}(2V, x)$. Moreover, $G$ is also a group of symmetries of $V$, so $\text{dist}(2V, x) = \text{dist}(g_0(2V), g_0(x)) = \text{dist}(2V, g_0(x))$, and so $\text{dist}(V, x+V) = \text{dist}(V, g_0(x) + V)$.

*Proof of (ii).* By symmetry and convexity of $V$, $\text{dist}(V, x+V) = \text{dist}(2V, x) = 2\text{dist}(V, x/2)$. It remains to show that $\text{dist}(V, x/2) = \text{dist}(V_1, x/2)$. Since $V_1 \subset V$, $\text{dist}(V, x/2) \le \text{dist}(V_1, x/2)$, so we are left with establishing the converse inequality.

Suppose to the contrary $\text{dist}(V, x/2) < \text{dist}(V_1, x/2)$ and let $t \in V \setminus K$ be such that $\text{dist}(V, x/2) = |x/2 - t|$. Since $t \notin K$, there is $w \in W$ such that $t \cdot w < 0$. Since $R_w$ is a symmetry of $\Lambda$, it is also a symmetry of $V$, and so $R_w(t) \in V$. Since $V$ is convex, we have $(R_w(t) + t)/2 \in V$, and so by (b)

$$ \text{dist}(V, x/2) \le |x/2 - (R_w(t) + t)/2| < |x/2 - t| = \text{dist}(V, x/2), $$

a contradiction to the assumption that $t \in V \setminus K$.

*Proof of (iii).* By (2), clearly

$$ V_1 = \bigcap_{z \in \Lambda \setminus \{0\}, |z| \le 2R} \{x \in K : |x| \le |x-z|\} \subset \bigcap_{z \in K \cap \Lambda \setminus \{0\}, |z| \le 2R} \{x \in K : |x| \le |x-z|\} =: V'_1, $$

so we only need to establish the converse inclusion $V'_1 \subset V_1$. We will show that if $x \in K \setminus V_1$, then $x \notin V'_1$.

Suppose that $x \in K \setminus V_1$, i.e. $x \in K$ and there is $t \in \Lambda \cap \mathcal{B}[2R]$, such that $\text{dist}(\Lambda \cap \mathcal{B}[2R], x) = |t-x|$ and $|t-x| < |x|$. Let $\varepsilon = (|x|-|t-x|)/3 > 0$. Since $x \in K$, by continuity there is $y$ from the relative interior of $K$, $|y-x| < \varepsilon$, such that $|y| > \text{dist}(\Lambda \cap \mathcal{B}[2R], y)$. Let $t' \in \Lambda$, $|t'| \le 2R$ be such that $|y - t'| = \text{dist}(\Lambda \cap \mathcal{B}[2R], y)$, then $t' \ne 0$.

We now show that $t' \in \Lambda \cap K$. Indeed, if this is not the case, there is $w \in W$ such that $t' \cdot w < 0$. But since $w \cdot y > 0$, by (a) we have $|y - t'| > |y - R_w(t')|$. Finally, $R_w(t') \in \Lambda$, $|R_w(t')| = |t'| \le 2R$, and $R_w(t')$ is closer to $y$ then $t'$ is, which contradicts the definition of $t'$. Therefore, $t' \in \Lambda \cap K$.

Now,

$$ |t' - x| \le |t' - y| + |y - x| \le |t - y| + |y - x| \le |t - x| + 2|y - x| \le |t - x| + 2\varepsilon. $$

Finally, we have $|x| - |t' - x| \ge |x| - |t - x| - 2\varepsilon = \varepsilon$. So for $t' \in K \cap \Lambda \setminus \{0\}$ we have $|x| > |t' - x|$. Since $|t'| \le 2R$ we conclude $x \notin V'_1$. $\square$
With the intention to apply Proposition 5 to some sublattice $\Lambda'$ of $\Lambda$, we need to be able to verify if $\Lambda' \subset \Lambda$ contains no elements of a forbidden set

$$F := \{x \in \Lambda \setminus \{0\} : \mathrm{dist}(V, x + V) < 2R\}. \qquad (3)$$

Due to (i),(ii) of Lemma 10, it suffices to compute the set

$$F_1 = \{x \in K \cap \Lambda \setminus \{0\} : \mathrm{dist}(V_1, x/2) < R\}. \qquad (4)$$

Then we have $F = \bigcup_{g \in G} g(F_1)$. Since the group $G$ will usually have a simple structure (e.g. consists of all permutations of the coordinates), computing $F$ as a union of $g(F_1)$ is faster than computing $F$ directly. It is also easy to observe that any $x$ in $F_1$ or in a forbidden set $F$ has norm less than $4R$, which allows to further restrict the initial candidates when $F_1$ is constructed.

Now let us describe how we compute the distance from a point $y$ to a polytope $P$ in $\mathbb{E}^m$. There are known algorithms for this, see, e.g [26], which might be faster, but we wanted to ensure exact computations and ease of implementation with the routines available in SageMath. Each $k$-dimensional face $f$ of $P$ is the intersection of a $k$-dimensional affine space $a(f) + A(f)\mathbb{E}^k$ with $P$, where $a(f) \in \mathbb{E}^m$ and $A(f)$ is the corresponding $m \times k$ matrix of rank $k$. If $A(f)^+$ denotes the Moore-Penrose inverse of $A(f)$ (see, e.g. [25]), then $B(f) = A(f)A(f)^+$ is the matrix of the projection operator on the range of $A(f)$, and so we have the following formula:

$$\mathrm{dist}(y, P) = \min\{|(I - B(f))(y - a(f))| : f \text{ is a face of } P \text{ and } a(f) + B(f)(y - a(f)) \in f\}.$$

If all vertices of $P$ have rational coordinates, then $A(f), A(F)^+$, and $B(f)$ have rational entries and can be computed precisely.

Finally, for a given sublattice $\Lambda' \subset \Lambda$, we would like to verify if $\Lambda' \cap F = \emptyset$, in which case $\chi(X) \le |\Lambda/\Lambda'|$ by Proposition 5 (recall that $X = M\mathbb{E}^n$ is a real $n$-dimensional space generated by $\Lambda$). This is performed using the following proposition that lists necessary and some sufficient conditions for $\Lambda' \cap F = \emptyset$. With slight abuse of notation, we denote by $M^{-1}$ the inverse map of the linear mapping from $\mathbb{E}^n$ to $X$ defined by $x \mapsto Mx$. The mapping $M^{-1}$ is well-defined as $X = M\mathbb{E}^n$ and the rank of $M$ equals to $n$. Set $\tilde{F} := M^{-1}F$.

**Proposition 11.** Suppose $\Lambda' = MC\mathbb{Z}^n$ for a non-singular $n \times n$ matrix $C$ with integer entries, and let $s$ be a positive integer. If $\Lambda' \cap F = \emptyset$, then necessarily:

(i) $C\lambda \notin \tilde{F}$ for any $\lambda = (\lambda_1, \dots, \lambda_n) \in \mathbb{Z}^n$ with $\lambda_1 + \dots + \lambda_n \ge 0$ and $|\lambda_j| \le s, 1 \le j \le n$. Further, we have $\Lambda' \cap F = \emptyset$ if and only if either (ii) or (iii) holds, where:

(ii) $C\lambda \notin \tilde{F}$ for any $\lambda \in \mathbb{Z}^n$ with $\lambda_1 + \dots + \lambda_n \ge 0$ and $|\lambda_j| \le m_j\gamma, 1 \le j \le n$, where $m_j$ is the (Euclidean) norm of the $j$-th row of $C^{-1}$ and $\gamma = \max\{|f| : f \in \tilde{F}\}$;

(iii) $C^{-1}f \notin \mathbb{Z}^n$ for any $f = (f_1, \dots, f_n) \in \tilde{F}$ with $f_1 + \dots + f_n \ge 0$.

*Proof.* Notice that $\Lambda' \cap F = \emptyset$ is equivalent to the statement that “for any $\lambda \in \mathbb{Z}^n$, $MC\lambda \notin F$”, and also to the statement “$C\lambda \notin \tilde{F}$ for all $\lambda \in \mathbb{Z}^n$”. So, necessity of (i) now follows.
For (ii) and (iii), origin-symmetry of $\Lambda'$, $F$ and $\tilde{F}$ allows to impose the conditions $\lambda_1 + \cdots + \lambda_n \ge 0$ and $f_1 + \cdots + f_n \ge 0$. Equivalence of $\Lambda' \cap F = \emptyset$ and (iii) is now clear.

For (ii), consider the equation $C\lambda = f$, for some $f \in \tilde{F}$, then $\lambda = C^{-1}f$. If $v_j$ is the $j$-th row of $C^{-1}$, then $\lambda_j = v_j \cdot f$ and by the Cauchy-Schwartz inequality $|\lambda_j| \le m_j|f| \le m_j\gamma$. So, in order to verify that $C\lambda \notin \tilde{F}$ for all $\lambda \in \mathbb{Z}^n$, it is sufficient to consider only $\lambda$ such that $|\lambda_j| \le m_j\gamma$, $1 \le j \le n$. Therefore (ii) is equivalent to $\Lambda' \cap F = \emptyset$. $\square$

Informally, if $\Lambda'$ has a vector in $F$, it is likely to have “small” coefficients of its representation, so it makes sense to begin verification with (i). We found that choosing $s = 2$ for $n = 5$ worked well, while for larger $n$ we usually selected $s = 1$. After (i) is verified and no vectors in $F$ is found, we choose to proceed with either (ii) or (iii) depending on the numbers of required evaluations of $C\lambda$ or of $C^{-1}f$.

*Proof of Theorem 1.* We will apply Proposition 5.

Suppose first that $n \in \{5, 9\}$. We consider a lattice $\Lambda$ which is an $(n+1)$-dilation of the lattice $A_n^*$, see [6, Sect. 4.6.6, p. 115]. Then the covering radius of $\Lambda$ is $R = \sqrt{\frac{n(n+1)(n+2)}{12}}$. More precisely, we set $\Lambda = M\mathbb{Z}^n \subset \mathbb{E}^{n+1}$, where

$$M = \begin{pmatrix} -n & 1 & \dots & 1 \\ 1 & -n & \dots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \dots & -n \\ 1 & 1 & \dots & 1 \end{pmatrix}.$$

The matrices $C_n$ generating required sublattices by $\Lambda' = MC_n\mathbb{Z}^n$ are given as follows:

$$C_5 = \begin{pmatrix} -2 & 1 & -2 & -1 & 0 \\ -3 & 1 & 0 & -1 & -2 \\ 0 & 1 & 1 & -1 & -3 \\ -2 & 0 & -2 & 2 & -2 \\ -2 & -2 & 0 & 0 & -2 \end{pmatrix},$$ $$C_9 = \begin{pmatrix} 0 & 0 & -3 & 1 & 0 & 0 & -1 & 1 & 0 \\ 1 & 0 & -3 & 1 & 1 & 0 & -1 & 4 & 1 \\ 0 & 0 & -2 & 1 & 0 & -1 & -1 & 1 & 3 \\ 0 & 0 & -3 & 4 & 0 & 0 & -1 & 1 & 0 \\ 0 & 3 & -3 & 1 & 0 & 0 & -1 & 1 & 0 \\ 3 & 0 & -3 & 1 & 0 & 0 & 2 & 1 & 0 \\ 0 & 0 & -4 & 2 & 0 & 3 & -1 & 2 & 0 \\ 0 & 0 & -3 & 1 & 3 & 0 & -1 & 1 & 0 \\ -1 & 0 & -3 & 1 & -1 & 1 & 1 & 1 & -1 \end{pmatrix}.$$

The verification of the hypothesis of Proposition 5 was performed on a computer. We generate the forbidden set $F$ (see (3)) by first generating $F_1$ (see (4)). We then use Lemma 10 with a group $G$ generated by all reflections that swap pairs of coordinates $x_i \leftrightarrow x_j$ where
$1 < i \le j < n$ and a reflection $x \mapsto (-x)$. Finally we use Proposition 11 (iii), to verify that obtained sublattice $\Lambda'$ has no forbidden nodes, see the “59dimAnstar” SageMath script at [1].

For $n = 7$, we use the $E_7^*$ lattice with $R = \sqrt{7}/8$, see [6, Sect. 4.8.2, p. 125]. Set $\Lambda = M\mathbb{Z}^7 \subset \mathbb{E}^8$, where

$$ M = \begin{pmatrix} -1 & 0 & 0 & 0 & 0 & 0 & -\frac{3}{4} \\ 1 & -1 & 0 & 0 & 0 & 0 & -\frac{3}{4} \\ 0 & 1 & -1 & 0 & 0 & 0 & \frac{1}{4} \\ 0 & 0 & 1 & -1 & 0 & 0 & \frac{1}{4} \\ 0 & 0 & 0 & 1 & -1 & 0 & \frac{1}{4} \\ 0 & 0 & 0 & 0 & 1 & -1 & \frac{1}{4} \\ 0 & 0 & 0 & 0 & 0 & 1 & \frac{1}{4} \\ 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{4} \end{pmatrix}. $$

A required sublattice is $\Lambda' = MC_7\mathbb{Z}^7$, where

$$ C_7 = \begin{pmatrix} 0 & -4 & -5 & -3 & -4 & -4 & -1 \\ -1 & -5 & -10 & -7 & -5 & -5 & -4 \\ -2 & -2 & -9 & -4 & -5 & -4 & -4 \\ -3 & -2 & -5 & -4 & -4 & -1 & -3 \\ -1 & -1 & -4 & -1 & -3 & 0 & -3 \\ -2 & 0 & -1 & 0 & 0 & 0 & 0 \\ 0 & 4 & 6 & 4 & 4 & 4 & 4 \end{pmatrix}. $$

The verification of the hypothesis of Proposition 5 was performed on a computer by first using Lemma 10 with a group $G$ generated by all reflection $x_i \leftrightarrow x_j$ when $1 \le i < j \le 6$ and two reflections $x_7 \leftrightarrow x_8$, $x \mapsto (-x)$, and then using Proposition 11 (iii), see the “7dimE7star” SageMath script at [1]. □

## 3.2 Sublattice search strategies

For a given lattice, when the dimension is relatively small (e.g. $n = 5$), it is computationally feasible to check all possible sublattices (of certain index) exhaustively, see Proposition 12. If the dimension is larger or we are interested in getting a result quickly, then we used a combination of the following two approaches (neither of which guarantees that the obtained $\Lambda'$ has the smallest possible index).

**Randomized search among short non-forbidden nodes.** Recall that the basis vectors of the desired sublattice are not elements of the forbidden set $F$. Since our goal is minimizing the index of the sublattice, which equals to the volume of the fundamental parallelepiped of the sublattice, it is natural to search for the basis among short vectors. To this end, we sort the non-zero lattice nodes which are not in $F$ in ascending order by length. Let $G$ be the set of $N$ smallest such non-forbidden nodes. Then we randomly and uniformly draw $n$ samples from $G$ to form a basis for the sublattice and check as outlined in Proposition 11 whether the resulting sublattice is suitable. The choice of the
parameter $N$ is performed in experimental manner: if $N$ is too small, there will not be a good sublattice basis among elements of $G$; while if $N$ is too large, then it may take too much time for the random samples to find a good sublattice.

**“Gradient” descent.** Once we have found a good sublattice $\Lambda'$, we take one of the vectors generating it and substitute it with other short non-forbidden nodes, choosing one that minimizes the index of the resulting $\Lambda'$ while satisfying $\Lambda' \cap F = \emptyset$. This is repeated for all vectors generating $\Lambda'$ (possibly multiple times) until no further improvement of the index is possible (using the short non-forbidden nodes).

### 3.3 Lower bounds in small dimensions

A general lower bound by Coulson [7, Th. 4.5] is $\chi_s(E^n, \Lambda, \Lambda', \ell) \ge 2^{n+1}-1$, so one cannot improve the inequality $\chi(E^3) \le 15$ using a sublattice coloring. The lower bounds on sublattice colorings we give below are for specific lattices $\Lambda$ and only for the case when the excluded distance $\ell$ is twice the covering radius of the lattice.

Existence of linear coloring using $A_4^*$ lattice yielding $\chi(E^4) \le 54$ was stated in [18]. A better bound $\chi(E^4) \le 49$ achieved by a sublattice coloring was stated in [8] without proof. We prove this bound in Theorem 8 using the $D_4$ lattice (see [6, p. 118]). We verified that one cannot do better, and we also perform similar analysis for $A_4^*$ and $A_5^*$.

**Proposition 12.** If $R$ is the covering radius of a lattice $\Lambda \in \{D_4, A_4^*, A_5^*\}$, then the smallest values of sublattice chromatic numbers (over all possible sublattices $\Lambda'$) are given in Table 2.

<table><caption>Table 2: Smallest values of sublattice chromatic numbers for $\Lambda \in \{D_4, A_4^*, A_5^*\}$.</caption><thead><tr><th>n</th><th>Λ</th><th>min<sub>Λ'</sub> χ<sub>s</sub>(E<sup>n</sup>, Λ, Λ', 2R)</th></tr></thead><tbody><tr><td>4</td><td>D<sub>4</sub></td><td>49</td></tr><tr><td>4</td><td>A<sub>4</sub><sup>*</sup></td><td>54</td></tr><tr><td>5</td><td>A<sub>5</sub><sup>*</sup></td><td>140</td></tr></tbody></table>

*Proof.* The proof is by computer search. For sublattice colorings, see the scripts “4dim exh sublattice ...” and “5dim exh sublattice A5star” at [1], with the outputs for each possible index value for the 5-dimensional case given in the “exh 5 results” folder at [1]. The main idea is that all possible sublattices of a given lattice can be obtained by $\Lambda' = C\Lambda$ where an integer matrix $C$ is in the Hermite normal form [24]. All such matrices $C$ of given determinant can be generated and the resulting sublattices tested using Lemma 10 and Proposition 11. We use a slightly modified version of the Hermite normal form where the entries above a pivot $l$ are from the set $-\lfloor l/2 \rfloor + \{0, \dots, l-1\}$ instead of $\{0, \dots, l-1\}$. This increases the chances that there is a “small” linear combination of the vectors from the sublattice basis (see (i) of Proposition 11) which belongs to the forbidden nodes, and speeds up the computations. □
We believe that in general the number $|F|$ of forbidden nodes is an indicator of how good a sublattice coloring scheme can be, the smaller the better. For instance, when $n=5$ we have $|F| = 3060$ for $D_5$, while $|F| = 1984$ for $A_5^*$. The sublattice schemes we found for $D_5$ are much worse than those for $A_5^*$.

Computer verification of the new upper bounds on $\chi(\mathbb{E}^n)$ for $n \in \{5, 7, 9\}$ takes less than two hours in a single thread mode on a modern personal computer. Generation of all forbidden nodes for $n=9$ takes about half an hour, but attempting this for $n=10$ would require significantly much more time and memory resources, and, in addition to that, we would then need to search for a good sublattice. It might be feasible to use our computational techniques (which are amenable to parallelization) for $n=10$ with a supercomputer to improve $\chi(\mathbb{E}^{10}) \le 3^{10}$. An exhaustive search for the best chromatic sublattice number for $A_5^*$ (Proposition 12) can be performed on a modern personal workstation, but is lengthy, taking about a month using 12 threads in parallel. One can refer to the file "running times.txt" in [1] for more details regarding running times of the scripts.

# 4 Constructions using covering-packing ratio

In this section we will prove Theorems 2 and 3 using Proposition 6 and Theorem 8, respectively, by describing certain appropriate lattices.

## 4.1 Laminated lattices and proof of Theorem 2

A laminated lattice $\Lambda_n$ is a full rank lattice in $\mathbb{E}^n$ that is obtained recursively in the following way. $\Lambda_1 = 2\mathbb{Z}$, and a laminated lattice $\Lambda_{n+1}$ is a full rank lattice in $\mathbb{E}^{n+1}$ containing some laminated $\Lambda_n$, such that the packing radius of $\Lambda_{n+1}$ is equal to 1 and the volume of Voronoi cell of $\Lambda_{n+1}$ is the smallest possible among all such lattices. Geometrically, one can think of $\Lambda_{n+1}$ as a lattice obtained by gluing layers of $\Lambda_n$ as "tightly" as possible while keeping the packing radius equal to 1.

Notice that the laminated lattice $\Lambda_n$ may not be unique, so $\Lambda_n$ formally is a collection of lattices. For example for $n \le 24$ laminated lattices $\Lambda_n$ are unique, except for $n = 11$ (2 lattices $\Lambda_{11}^{\min}, \Lambda_{11}^{\max}$), $n = 12$ ($\Lambda_{12}^{\min}, \Lambda_{12}^{\max}, \Lambda_{12}^{\max}$) and $n = 13$ ($\Lambda_{13}^{\min}, \Lambda_{13}^{\max}, \Lambda_{13}^{\max}$), see [6, Figure 6.1]. Moreover, $\Lambda_{14}$ does not contain $\Lambda_{13}^{\min}$ as a sublattice; however, $\Lambda_{14}$ can be constructed from either $\Lambda_{13}^{\min}$ or $\Lambda_{13}^{\max}$, so not every $\Lambda_n$ is a subset of the subsequent $\Lambda_{n+1}$.

Additionally, since the packing radius of any $\Lambda_n$ is equal to 1, the covering-packing ratio of any $\Lambda_n$ coincides with the covering radius. A comprehensive exposition on laminated lattices can be found in [6, Ch. 6].

**Proposition 13.** The covering-packing ratios of laminated lattices in dimensions $9 \le n \le 38$ satisfy the equalities or the upper bounds given in Table 3.

*Proof.* Let $\rho_n$ denote the greatest covering radius of any laminated lattice $\Lambda_n$. By [6, Th. 1, p. 164], we obtain the exact values of $\rho_n$ for $n \in \{9, 10, 11, 12, 16, 24, 25, 26, 27, 28, 32\}$ as listed in Table 3. More precisely, these values are equal to the so-called subcovering radius
<table><caption>Table 3: Covering-packing ratios of laminated lattices $\Lambda_n$. In the dimensions where $\Lambda_n$ is not unique the maximum possible covering ratio is listed. If covering radius is not known, an upper bound on the covering ratio is listed (blue values).</caption><thead><tr><th>n</th><th>covering-packing ratio</th><th>n</th><th>covering-packing ratio</th></tr></thead><tbody><tr><td>9</td><td>√5/2 ≈ 1.581138</td><td>24</td><td>√2 ≈ 1.414213</td></tr><tr><td>10</td><td>√8/3 ≈ 1.632993</td><td>25</td><td>√5/2 ≈ 1.581138</td></tr><tr><td>11</td><td>√3 ≈ 1.732050</td><td>26</td><td>√8/3 ≈ 1.632993</td></tr><tr><td>12</td><td>√3 ≈ 1.732050</td><td>27</td><td>√3 ≈ 1.732050</td></tr><tr><td>13</td><td>√13/2 ≈ 1.802776</td><td>28</td><td>√3 ≈ 1.732050</td></tr><tr><td>14</td><td>≤ √55/4 ≈ 1.854050</td><td>29</td><td>√13/2 ≈ 1.802776</td></tr><tr><td>15</td><td>≤ √173/48 ≈ 1.898465</td><td>30</td><td>≤ √55/4 ≈ 1.854050</td></tr><tr><td>16</td><td>√3 ≈ 1.732050</td><td>31</td><td>≤ √173/48 ≈ 1.898465</td></tr><tr><td>17</td><td>√13/2 ≈ 1.802776</td><td>32</td><td>√3 ≈ 1.732050</td></tr><tr><td>18</td><td>≤ √55/4 ≈ 1.854050</td><td>33</td><td>√13/2 ≈ 1.802776</td></tr><tr><td>19</td><td>≤ √173/48 ≈ 1.898465</td><td>34</td><td>≤ √55/4 ≈ 1.854050</td></tr><tr><td>20</td><td>≤ √179/48 ≈ 1.931106</td><td>35</td><td>≤ √173/48 ≈ 1.898465</td></tr><tr><td>21</td><td>≤ √185/48 ≈ 1.963204</td><td>36</td><td>≤ √179/48 ≈ 1.931106</td></tr><tr><td>22</td><td>≤ √379/96 ≈ 1.986937</td><td>37</td><td>≤ √185/48 ≈ 1.963204</td></tr><tr><td>23</td><td>≤ 1.936501</td><td>38</td><td>≤ √379/96 ≈ 1.986937</td></tr></tbody></table>

$h_n$ from [6, Table 6.1] provided $h_n \le \sqrt{3}$ (see the caption description of the Table 6.1 [6] and [6, Th. 1, p. 164] for more details).

Next we note (see [6, p. 163]) that each $\Lambda_n$ can be represented in $\mathbb{E}^n$ as $\cup_{j \in \mathbb{Z}} \Lambda_{n-1}^{(j)}$, where $\Lambda_{n-1}^{(j)}$ is a translate of a certain laminated lattice such that any point of $\Lambda_{n-1}^{(j)}$ has n-th coordinate equal to $j\sqrt{\pi_{n-1}}$. The values of $\pi_{n-1}$ are given in [6, Table 6.1]. Now for any point $x = (x_1, \dots, x_n) \in \mathbb{E}^n$ we can find $j$ minimizing $|x_n - j\sqrt{\pi_{n-1}}|$ and then a lattice node $y \in \Lambda_{n-1}^{(j)}$ with $|(x_1, \dots, x_{n-1}, j\sqrt{\pi_{n-1}}) - y| \le \rho_{n-1}$. This yields

$$ \rho_n \le \sqrt{\frac{\pi_{n-1}}{4} + \rho_{n-1}^2}. \qquad (5) $$

Starting with the already obtained values of $\rho_n$ for $n \in \{12, 16, 28, 32\}$, consecutive applications of (5) imply the upper bounds on $\rho_n$ for all the remaining values of $n$ in Table 3 except for $n = 23$. The equalities for $n \in \{13, 17, 29, 33\}$ follow from the lower bound $h_n \le \rho_n$ and the values of $h_n$ given in [6, Table 6.1].

Finally, the inequality for $n = 23$ is a consequence of the computational result [22, Table 2], where the covering density $\theta(\Lambda_{23}) = 7609.03133$ is listed. The formula for the covering density is $\theta(\Lambda_{23}) = \frac{(\rho_{23})^{23}|\mathcal{B}[1]|}{\det(\Lambda_{23})}$. Interestingly enough, the determinant $\det(\Lambda_{23})$ of a lattice in [22] is defined to be the determinant of the generating matrix $M$, while the determinant $\lambda_{23}$ of $\Lambda_{23}$ in [6] is defined to be the determinant of the Gram matrix
$MM^T$. So we have $det(\Lambda_{23}) = \sqrt{\lambda_{23}}$, and $\lambda_{23} = 4$ as listed in [6, Table 6.1]. Therefore, $\theta(\Lambda_{23}) = \frac{(\rho_{23})^{23}|\mathcal{B}[1]|}{2}$. Finally, using the formula for the volume of the unit ball $|\mathcal{B}[1]|$ in dimension 23, we get $\rho_{23} \le 1.936501$. $\square$

**Remark 14.** In [22], numerical values of $\rho_n$ appear to match $h_n$ for $n \in \{14, 15, 18, 23\}$, which suggests that possibly $\rho_n = h_n$ in these cases. However, it is not clear from [22] whether the computations were performed using exact arithmetic and the results were converted to numerical ones only at the end. Also, according to [22], the covering radius $\rho_{13}^{\text{mid}}$ of $\Lambda_{13}^{\text{mid}}$ satisfies $\rho_{13}^{\text{mid}} \approx \sqrt{3} < \rho_{13} = \sqrt{13}/2$. However, $\Lambda_{13}^{\text{mid}}$ is not contained in $\Lambda_{14}$ (see [6, Figure 6.1]), so (5) is not applicable when $n = 14$ and $\rho_{13}$ is replaced by $\rho_{13}^{\text{mid}}$.

Laminated lattices provide a recursive construction that allows us to obtain lattices with a small covering-packing ratio. We now will consider how the covering-packing ratio behaves when we take a sum of lattices.

First, one can consider a direct (orthogonal) sum of two lattices $\Lambda_1$ and $\Lambda_2$ defined by $\Lambda_1 \oplus \Lambda_2 = \{(v, u) : v \in \Lambda_1, u \in \Lambda_2\}$. If $\Lambda_1$ and $\Lambda_2$ are full rank lattices in $\mathbb{E}^n$ and $\mathbb{E}^m$ respectively, both with packing radius 1, then $\Lambda_1 \oplus \Lambda_2$ is a full rank lattice in $\mathbb{E}^{n+m}$ with packing radius 1. Moreover if covering radii of $\Lambda_1$, $\Lambda_2$ are $\rho_1$ and $\rho_2$ respectively, it can be easily seen that the covering radius of $\Lambda_1 \oplus \Lambda_2$ does not exceed $\sqrt{\rho_1^2 + \rho_2^2}$. This way, by using the Leech lattice $\Lambda_{24}$, we obtain a lattice $\Lambda_{24} \oplus \Lambda_{24}$ with covering-packing ratio at most 2 in dimension $n = 48$.

A slightly better direction would be to consider a $\pi/3$-sum of two lattices, instead of the direct sum (see (6) for the definition). We summarize this approach in the following proposition.

**Proposition 15.** For $i = 1, 2$ let $\Lambda_i$ be a full rank lattice in $\mathbb{E}^{n_i}$ with a covering-packing ratio $\rho_i$. Provided $n_1 \ge n_2$, there exists a full rank lattice $\Lambda$ in $\mathbb{E}^{n_1+n_2}$ with the covering-packing ratio not exceeding $\sqrt{\rho_1^2 + \frac{3}{4}\rho_2^2}$.

*Proof.* We write $(x, y) \in \mathbb{E}^{n_1+n_2}$ with $x \in \mathbb{E}^{n_1}$ and $y \in \mathbb{E}^{n_2}$. Define a lift operation $L: \mathbb{E}^{n_2} \to \mathbb{E}^{n_1}$ by $f(y) = (y, 0, \dots, 0)$.

Assume that packing radii of lattices $\Lambda_1$ and $\Lambda_2$ are equal to 1. Let $\Lambda$ be a $\pi/3$-sum of lattices $\Lambda_1$ and $\Lambda_2$ defined by

$$ \Lambda = \left\{ \left( x + \frac{Ly}{2}, \frac{\sqrt{3}}{2}y \right) : x \in \Lambda_1, y \in \Lambda_2 \right\}. \qquad (6) $$

It is easy to see that $\Lambda$ is a full rank lattice in $\mathbb{E}^{n_1+n_2}$.

Now we show that the packing radius of $\Lambda$ is equal to 1. It is enough to show that any nonzero vector $v = (x + \frac{Ly}{2}, \frac{\sqrt{3}}{2}y)$ of $\Lambda$ has length at least 2. We have

$$ |v|^2 = \left|x + \frac{Ly}{2}\right|^2 + \left|\frac{\sqrt{3}}{2}y\right|^2 = |x|^2 + x \cdot Ly + |y|^2 \ge |x|^2 - |x||y| + |y|^2. $$
Now, if one of $x$ or $y$ is a zero vector, then clearly $|v|^2 \ge 4$. If both $x$ and $y$ are non-zero, then $|x| \ge 2$, $|y| \ge 2$, and so

$$|v|^2 \ge \frac{1}{2} |x|^2 + \frac{1}{2} |y|^2 \ge 4.$$

To estimate the covering radius of $\Lambda$, let $(\hat{x}, \frac{\sqrt{3}}{2}\hat{y})$ be an arbitrary point of $\mathbb{E}^{n_1+n_2}$. Since the covering radius of $\Lambda_2$ is $\rho_2$, let $y \in \Lambda_2$ be such that $|\hat{y} - y| \le \rho_2$. Similarly let $x \in \Lambda_1$ be such that $|\hat{x} - x - \frac{Ly}{2}| \le \rho_1$. Then $(x + \frac{Ly}{2}, \frac{\sqrt{3}}{2}y) \in \Lambda$ and

$$\left| \left( \hat{x}, \frac{\sqrt{3}}{2} \hat{y} \right) - \left( x + \frac{Ly}{2}, \frac{\sqrt{3}}{2} y \right) \right| \le \sqrt{\rho_1^2 + \frac{3}{4} \rho_2^2}.$$

<figure><img src="image_2.png" /></figure>

Note that when $\Lambda_1 = \Lambda_2 = 2\mathbb{Z}$ and $\Lambda$ is a $\pi/3$-sum of $\Lambda_1$ and $\Lambda_2$, we can find copies of $\Lambda_1, \Lambda_2$ in $\Lambda$ (by taking $y = 0, x = 0$ respectively). Moreover, the angle between these copies of $\Lambda_1$ and $\Lambda_2$ in $\Lambda$ is $\pi/3$, which is why we say that $\Lambda$ is a $\pi/3$-sum of $\Lambda_1$ and $\Lambda_2$ (similarly to orthogonal sum $\Lambda_1 \oplus \Lambda_2$, where the corresponding angle is $\pi/2$). We remark that the smaller value of the angle (less than $\pi/3$) in the proof of Proposition 15 would violate the requirement for the packing radius of the resultant sum to be equal to 1, so $\pi/3$ is the optimal angle in this context.

*Proof of Theorem 2.* Due to Proposition 6, it suffices to show the existence of a lattice with covering-packing ratio at most 2 for each required dimension $n$.

For $n \le 8$ the lattices with the smallest known covering-packing ratio are listed in [21, Table 3, Table 4]; the ratios are strictly smaller than 2. For $9 \le n \le 38$, we use Proposition 13.

For $n = 48$, by Proposition 15 the $\pi/3$-sum $\Lambda = \Lambda_{24} \oplus_{\pi/3} \Lambda_{24}$ of two Leech lattices has the covering-packing ratio at most $\sqrt{\frac{7}{2}}$. (Note that $\Lambda = \Lambda_{24} \oplus \Lambda_{24}$ can also be used as it has the covering-packing ratio at most 2.)

Finally, for $n = 49$, by Proposition 15 the $\pi/3$-sum $\Lambda = \Lambda_{25} \oplus_{\pi/3} \Lambda_{24}$ of two laminated lattices has the covering-packing ratio not exceeding 2. $\square$

<figure><img src="image_3.png" /></figure>

## 4.2 Eisenstein lattices and proof of Theorem 3

*Proof of Theorem 3.* By Theorem 8, for each dimension in question we only need to find an Eisenstein lattice with covering-packing ratio at most 3/2. We list suitable lattices in Table 4. $\square$

<figure><img src="image_4.png" /></figure>

# 5 Upper bound on chromatic number in all dimensions

In his paper [17] Prosanov considered covering of $\mathbb{E}^n$ by translates of dilated Voronoi cells of an appropriately chosen multilattice. Prosanov considered the chromatic number of $\mathbb{E}^n$
<table><caption>Table 4: Eisenstein lattices with covering-packing ratio at most 3/2 for $n \in \{2, 4, 6, 8, 24\}$.</caption><thead><tr><th>n</th><th>lattice</th><th>covering-packing ratio</th><th>reference</th></tr></thead><tbody><tr><td>2</td><td>A<sub>2</sub></td><td>2/&radic;3</td><td>[6, p. 110]</td></tr><tr><td>4</td><td>D<sub>4</sub></td><td>&radic;2</td><td>[6, p. 119]</td></tr><tr><td>6</td><td>E<sub>6</sub><sup>*</sup></td><td>&radic;2</td><td>[6, p. 127]</td></tr><tr><td>8</td><td>E<sub>8</sub></td><td>&radic;2</td><td>[6, p. 121, p. 161]</td></tr><tr><td>24</td><td>&Lambda;<sub>24</sub></td><td>&radic;2</td><td>[6, p. 161]</td></tr></tbody></table>

with respect to a metric generated by a general convex centrally-symmetric body $K$. For our consideration, we take $K$ to be the unit ball, i.e. $K = \mathcal{B}[1]$.

Following the notation of [17], let $\Omega$ be a lattice and $\Phi$ be a multilattice obtained by $q$ shifts of $\Omega$, i.e. $\Phi = \bigcup_{i=1}^q x_i + \Omega$, where $x_1, \dots, x_q$ are some vectors in $\mathbb{E}^n$. A tilling $\Psi$ of $\mathbb{E}^n$ by convex polytopes is said to be associated with $\Phi$ if there is a bijection between $\Phi$ and $\Psi$ such that for every $x \in \Phi$ and a corresponding $\psi_x \in \Psi$ we have $x \in \psi_x$. Note that a natural choice of $\Psi$ associated to $\Phi$ are Voronoi cells of $\Phi$.

The tiling parameter is defined to be

$$ \gamma(\Phi, \Psi) = \inf \left\{ \frac{\beta}{\alpha} : \text{ for all } x \in \Phi, \alpha \mathcal{B}[1] + x \subset \psi_x \subset \beta \mathcal{B}[1] + x \right\}, $$

and

$$ \gamma(k) = \inf_{\Phi, \Psi, q(\Phi) \le k} \gamma(\Phi, \Psi). $$

Note, that $\gamma(\Phi, \Psi)$ corresponds to a covering-packing ratio of $\Phi$ when $\Psi$ are Voronoi cells of $\Phi$, and so $\gamma(k)$ is the smallest possible covering-packing ratio of a $k$-multilattice in $\mathbb{E}^n$.

Prosanov [17] proved that (for $n \ge 3$ and any $k$)

$$ \chi(\mathbb{E}^n) \le (1 + \gamma(k))^n \left(1 + \frac{2}{\ln n}\right) (1 + n \ln(4n \cdot \ln n \cdot \gamma(k)) + \ln k). \quad (7) $$

He then deduced that $\chi(\mathbb{E}^n) \le (3 + o(1))^n$ by:

* taking $\Omega = \mathbb{Z}^n$;

* taking $\Phi$ to be centers of unit spheres that pack into a unit torus and taking $\Psi$ to be Voronoi cells of $\Phi$, which gives $k = q(\Phi) \le n^{O(n)}$ and $\gamma(k) \le 2$;

* using inequality (7), the bound becomes $\chi(\mathbb{E}^n) \le 3^n(n + O(n)) \ln n$.

We note that one can get rid of the $O(n)$ term in Prosanov's bounds by choosing initial $\Omega$ to have a low covering-packing ratio. Recall that Butler [4] showed that there are lattices with covering packing ratio $2 + o(1)$. Let $\Omega$ be such a lattice and let $T$ be
a torus obtained by identifying the opposite sides of fundamental parallelepiped of $\Omega$. Consider a maximal packing of unit spheres into $T$ and let $x_1, \dots, x_q$ be the centers of these spheres. Since $\Omega$ has a covering-packing ratio $2 + o(1)$, the volume argument yields $q \le (2 + o(1))^n$. So for $\Phi = \bigcup_{i=1}^q \Omega + x_i$, $\Psi$ - Voronoi cells of $\Phi$, and $k = q(\Psi)$ we have $\gamma(k) \le 2$ and $k = (2 + o(1))^n$. Therefore inequality (7) yields

$$ \chi(\mathbb{E}^n) \le (1 + o(1))3^n n \ln n. $$

Note that one can get an explicit bound if $\Omega$ is taken to be a lattice with a covering-packing ratio at most $\sqrt{21}/2 \approx 2.2913$, existence of which in any dimension $n$ was established by Henk [12]. In this case for any $n$ we have

$$ \chi(\mathbb{E}^n) \le 3^n \left( 1 + \frac{2}{\ln n} \right) \left( 1 + n \ln(8n \cdot \ln n) + n \ln \frac{\sqrt{21}}{2} \right). $$

# 6 Open questions

**Question 16.** Do there exist better sublattice coloring schemes (perhaps for other lattices) than those in Theorems 1 and 3 for $4 \le n \le 9$?

We believe that the answer is negative for $n = 4, 5$, i.e. $\min \chi_s(\mathbb{E}^4, \Lambda, \Lambda', \ell) = 49$ and $\min \chi_s(\mathbb{E}^5, \Lambda, \Lambda', \ell) = 140$, where the minima are taken over all full rank lattices $\Lambda$, sublattices $\Lambda'$ and all $\ell > 0$.

**Question 17.** Is it possible to extend the result of Theorem 3 to other dimensions? In particular, does there exist an Eisenstein lattice with covering-packing ratio at most $3/2$ in dimension other than those listed in Theorem 3?

**Question 18.** Is it possible to obtain a new upper bound on $\chi(\mathbb{E}^n)$ for some $n$ using a modification of the technique of Theorem 8, perhaps using Hurwitz quaternionic integers [6, Sect.2.2.6, p. 53]?

Everywhere below in this section $R$ denotes the covering radius of a lattice $\Lambda$.

**Question 19.** Is it true that for every $n$ there exists a full rank lattice $\Lambda$ and a sublattice $\Lambda' \subset \Lambda$ such that $\chi_s(\mathbb{E}^n, \Lambda, \Lambda', 2R) < 3^n$?

An affirmative answer immediately implies $\chi(\mathbb{E}^n) < 3^n$. The results in this paper give an affirmative answer for $n \le 9$.

**Question 20.** Find all dimensions $n$ for which there exists a full rank lattice in $\mathbb{E}^n$ with covering/packing ratio at most 2.

For any such dimension we immediately have $\chi(\mathbb{E}^n) \le \chi_s(\mathbb{E}^n, \Lambda, 3\Lambda, 2R) = 3^n$ by Proposition 6. It is believed (see [21, Problem 4.1], [27, Problem 1.1, 1.2], [14, Question 3.2], [5, p.63 Problem 6]) that for a sufficiently large $n$ any lattice in $\mathbb{E}^n$ has covering/packing ratio at least 2, i.e. there are non-lattice packings of $\mathbb{E}^n$ which are denser
than lattice packings. Notice that discrete sets with covering-packing ratio at most 2
having non-lattice structure can be easily constructed in any dimension using maximal
separated sets on a torus. On the other hand, existence of a lattice Λ in Eⁿ with a
covering-packing ratio 2 + o(1) as n → ∞ was established by Butler [4].

**Question 21.** Find all *n* such that there exists a laminated lattice Λ*n* with covering radius at most 2.

We know that all dimensions *n* up to 38 satisfy this property.

Acknowledgements

The authors are grateful to the referees for the numerous useful suggestions that allowed
to improve the paper.

The first author was supported by NSERC of Canada Discovery Grant RGPIN-2020-05357, University of Manitoba Research Grant Program project “Covering problems with applications in Euclidean Ramsey theory and convex geometry”, and by the Pacific Institute for the Mathematical Sciences (PIMS).

The second author was supported by grant 334466 of the Research Council of Norway
“Fourier Methods and Multiplicative Analysis”.

The third author was supported by NSERC of Canada Discovery Grant RGPIN-2020-05357.

**References**

[1] A. Arman, A Bondarenko, A. Prymak, and D. Radchenko, *Scripts for upper bounds on chromatic number of Euclidean space in small dimensions*, available at https://github.com/andriyprm/ubcnessd/releases/tag/v1.

[2] W. Banaszczyk, *On the lattice packing–covering ratio of finite-dimensional normed spaces*, Colloq. Math. **59** (1990), no. 1, 31–33.

[3] L. I. Bogolyubskiǐ and A. M. Raǐgorodskiǐ, *A remark on lower bounds for the chromatic numbers of spaces of small dimension with metrics $\ell_1$ and $\ell_2$*, Mat. Zametki **105** (2019), no. 2, 187–213 (Russian, with Russian summary); English transl., Math. Notes **105** (2019), no. 1-2, 180–203.

[4] G. J. Butler, *Simultaneous packing and covering in euclidean space*, Proc. London Math. Soc. (3) **25** (1972), 721–735.

[5] P. Brass, W. Moser, and J. Pach, *Research problems in discrete geometry*, Springer, New York, 2005.

[6] J. H. Conway and N. J. A. Sloane, *Sphere packings, lattices and groups*, 3rd ed., Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 290, Springer-Verlag, New York, 1999. With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov.

[7] D. Coulson, A 15-colouring of 3-space omitting distance one, *Discrete Math.* **256** (2002), 83–90.

[8] D. Coulson and M. S. Payne, *A dense distance 1 excluding set in R³*, Austral. Math. Soc. Gaz. **34** (2007), no. 2, 97–102.

[9] N. G. de Bruijn and P. Erdős, *A colour problem for infinite graphs and a problem in the theory of relations*, Nederl. Akad. Wetensch. Proc. Ser. A. **54** = Indagationes Math. **13** (1951), 369–373.
[10] A. D. N. J. de Grey, *The chromatic number of the plane is at least 5*, Geombinatorics **28** (2018), no. 1, 18–31.

[11] N. P. Dolbilin, J. C. Lagarias, and M. Senechal, *Multiregular point systems*, Discrete Comput. Geom. **20** (1998), no. 4, 477–498.

[12] M. Henk, *Finite and infinite packings*, Habilitation Thesis, University of Siegen, 1994.

[13] D. G. Larman and C. A. Rogers, The realization of distances within sets in Euclidean space, *Mathematika* **19** (1972), 1–24.

[14] G. Muraz and J.-L. Verger-Gaugry, *On lower bounds of the density of Delone sets and holes in sequences of sphere packings*, Experiment. Math. **14** (2005), no. 1, 47–57.

[15] *Polymath16, fifth thread: Human-verifiable proofs*, available at https://dustingmixon.wordpress.com/2018/05/10/polymath16-fifth-thread-human-verifiable-proofs/.

[16] *Polymath wiki: Hadwiger-Nelson problem*, available at https://asone.ai/polymath/index.php?title=Hadwiger-Nelson Problem.

[17] R. Prosanov, *A new proof of the Larman-Rogers upper bound for the chromatic number of the Euclidean space*, Discrete Appl. Math. **276** (2020), 115–120.

[18] R. Radoičić and G. Tóth, Note on the chromatic number of the space, *Discrete and computational geometry*, Algorithms Combin., vol. 25, Springer, Berlin, 2003, pp. 695–698.

[19] A. M. Raigorodskii, On the chromatic number of a space, *Russ. Math. Surv.* **55**(N2) (2000), 351–352.

[20] C. A. Rogers, *A note on coverings and packings*, J. London Math. Soc. **25** (1950), 327–331.

[21] A. Schürmann and F. Vallentin, *Computational approaches to lattice packing and covering problems*, Discrete Comput. Geom. **35** (2006), no. 1, 73–116.

[22] M. Dutour Sikirić, A. Schürmann, and F. Vallentin, *Complexity and algorithms for computing Voronoi cells of lattices*, Math. Comp. **78** (2009), no. 267, 1713–1731.

[23] A. Soifer, *The mathematical coloring book*, Springer, New York, 2009. Mathematics of coloring and the colorful life of its creators; With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau.

[24] Wikipedia contributors, *Hermite normal form*, available at https://en.wikipedia.org/wiki/Hermite_normal_form. Accessed on November 25, 2021.

[25] Wikipedia contributors, *Moore-Penrose pseudoinverse*, available at https://en.wikipedia.org/wiki/Moore-Penrose_inverse. Accessed on November 29, 2021.

[26] P. Wolfe, *Finding the nearest point in a polytope*, Math. Programming **11** (1976), no. 2, 128–149.

[27] C. Zong, *From deep holes to free planes*, Bull. Amer. Math. Soc. (N.S.) **39** (2002), no. 4, 533–555.