# On the density of sets avoiding parallelohedron distance 1

Christine Bachoc, Thomas Bellitto, Philippe Moustrou, Arnaud Pêcher

► To cite this version:

Christine Bachoc, Thomas Bellitto, Philippe Moustrou, Arnaud Pêcher. On the density of sets avoiding parallelohedron distance 1. 2017. hal-01567118

HAL Id: hal-01567118

https://hal.science/hal-01567118

Preprint submitted on 27 Jul 2017

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
# ON THE DENSITY OF SETS AVOIDING PARALLELOHEDRON DISTANCE 1

CHRISTINE BACHOC, THOMAS BELLITTO, PHILIPPE MOUSTROU, AND ARNAUD PÊCHER

ABSTRACT. The maximal density of a measurable subset of $\mathbb{R}^n$ avoiding Euclidean distance 1 is unknown except in the trivial case of dimension 1. In this paper, we consider the case of a distance associated to a polytope that tiles space, where it is likely that the sets avoiding distance 1 are of maximal density $2^{-n}$, as conjectured by Bachoc and Robins. We prove that this is true for $n = 2$, and for the Voronoï regions of the lattices $A_n$, $n \ge 2$.

## 1. INTRODUCTION

A set avoiding distance 1 is a set $A$ in a normed vector space $(\mathbb{R}^n, \| \cdot \|)$ such that $\|x-y\| \ne 1$ for every $x, y \in A$. The number $m_1(\mathbb{R}^n, \| \cdot \|)$ measures the highest proportion of space that can be filled by a set avoiding distance 1. More precisely, $m_1(\mathbb{R}^n, \| \cdot \|)$ is the supremum of the densities (see Subsection 2.1 for a precise definition) of Lebesgue measurable sets $A \subset \mathbb{R}^n$ avoiding distance 1.

The problem of determining $m_1(\mathbb{R}^n, \| \cdot \|)$ has been mostly studied in the Euclidean case. The number $m_1(\mathbb{R}^n) = m_1(\mathbb{R}^n, \| \cdot \|_2)$ was introduced by Larman and Rogers in [8] as a tool to study the measurable chromatic number $\chi_m(\mathbb{R}^n)$ of $\mathbb{R}^n$, which is the minimal number of colors required to color $\mathbb{R}^n$ in such a way that two points at Euclidean distance 1 have distinct colors, and that the color classes are measurable. Determining $\chi_m(\mathbb{R}^n)$ has turned out to be a very difficult problem, that has only been solved in dimension 1, and that is wide open in any other dimension, including the familiar dimension 2, where it is only known that $5 \le \chi_m(\mathbb{R}^2) \le 7$ (see [6], [13], and [12, Chapter 3] for a detailed historical account).

The connection between $m_1(\mathbb{R}^n)$ and $\chi_m(\mathbb{R}^n)$ lies in the following inequality:

$$ \chi_m(\mathbb{R}^n) \ge \frac{1}{m_1(\mathbb{R}^n)}, $$

so, from an upper bound for $m_1(\mathbb{R}^n)$, one obtains a lower bound for $\chi_m(\mathbb{R}^n)$.

A natural approach to build a set avoiding distance 1, that works for any norm, starts from a packing of unit balls. Let $\Lambda$ be a set such that if $x, y \in \Lambda$, then the unit open balls $B(x, 1)$ and $B(y, 1)$ do not overlap. Then the set $A = \cup_{\lambda \in \Lambda} B(\lambda, 1/2)$ of disjoint balls of radius $1/2$ is a set avoiding 1 and its density is $\frac{\delta}{2^n}$ where $n$ is the dimension of the space and $\delta$ is the density of the packing. This construction is illustrated in Figure 1.

In the Euclidean plane, the density of an optimal packing of discs of radius 1 is 0.9069 and this approach therefore provides a lower bound of $0.9069/4 = 0.2267$ for $m_1(\mathbb{R}^2, \| \cdot \|_2)$. The best known construction is not much better than that: by refining this idea, Croft

<footnote>Date: July 27, 2017.</footnote>

<footnote n="1991">1991 Mathematics Subject Classification. 52C10, 52B11, 11H06.</footnote>

<footnote>Key words and phrases. distance graphs, parallelohedra, lattices, chromatic number.</footnote>

<footnote>This study has been carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the frame of the "Investments for the future" Programme IdEx Bordeaux - CPU (ANR-10-IDEX-03-02).</footnote>
<figure><img src="image_2.png" /><figcaption>FIGURE 1. A set avoiding distance 1 built from a sphere packing.</figcaption></figure>

manages to build in [3] a set of density 0.2293, which is an arrangement of balls cut out by hexagons.

Regarding upper bounds, Erdős conjectured (see [13]) that

$$m_1(\mathbb{R}^2) < \frac{1}{4}.$$

The best upper bound up to now is due to Keleti, Matolcsi, de Oliveira Filho and Ruzsa [7], who have shown $m_1(\mathbb{R}^2) \le 0.258795$. Moser, Larman and Rogers (see [8]) generalized Erdős' conjecture to higher dimensions: for every $n \ge 2$,

$$m_1(\mathbb{R}^n) < \frac{1}{2^n}.$$

A weaker result has been proved in [7]: a set avoiding distance 1 necessarily has a density strictly smaller than $\frac{1}{2^n}$ if it has a block structure, i.e. if it may be decomposed as a disjoint union $A = \cup A_i$ such that if $x$ and $y$ are in the same block $A_i$ then $\|x - y\| < 1$ and if they are not, $\|x - y\| > 1$. However, without this assumption, the known upper bounds are pretty far from $2^{-n}$, even asymptotically: the best asymptotic bound is $m_1(\mathbb{R}^n) \le (1 + o(1))(1.2)^{-n}$ (see [8], [1]).

Going back to the general case of an arbitrary norm, we make the remark that if the unit ball tiles $\mathbb{R}^n$ by translation, the method described previously to build a set avoiding distance 1 from a packing provides a set of density exactly $1/2^n$, as illustrated in Figure 2. Moreover, it is likely that this construction of a set avoiding distance 1 is optimal, as conjectured by Bachoc and Robins:

<figure><img src="image_3.png" /><figcaption>FIGURE 2. The natural construction of density $1/2^n$.</figcaption></figure>

**Conjecture 1** (Bachoc, Robins). If $\| \cdot \|$ is a norm such that the unit ball tiles $\mathbb{R}^n$ by translation, then

$$m_1(\mathbb{R}^n, \| \cdot \|) = \frac{1}{2^n}.$$
In this paper, we prove Conjecture 1 in dimension 2:

**Theorem 1.** If $\|\cdot\|$ is a norm such that the unit ball tiles $\mathbb{R}^2$ by translation, then

$$m_1(\mathbb{R}^2, \|\cdot\|) = \frac{1}{4}.$$

Recall that the only convex bodies that tile space by translation are the *paralleohedra*, i.e. the polytopes that admit a face-to-face tiling by translation. For a given paralleohedron $\mathcal{P}$, we denote by $\|\cdot\|_{\mathcal{P}}$ the norm whose unit ball is $\mathcal{P}$.

The Voronoï region of a lattice is a parallelohedron. Conversely, Voronoï conjectured that all parallelohedra are, up to affine transformations, the Voronoï regions of lattices (see Subsection 2.2). On the other hand, $m_1(\mathbb{R}^n, \|\cdot\|)$ is clearly left unchanged under the action of a linear transformation applied to the norm. So, in the light of Voronoï’s conjecture, it is natural to consider in first place the polytopes that are Voronoï regions of lattices.

The most obvious family of lattices is the family of cubic lattices $\mathbb{Z}^n$, whose Voronoï regions are hypercubes. We will see that in this case, Conjecture 1 holds trivially. The next families of lattices to consider are arguably the root lattices $A_n$ and $D_n$, where

$$A_n = \{x \in \mathbb{Z}^{n+1} \mid \sum_{i=1}^{n+1} x_i = 0\} \quad (n \ge 2).$$

and

$$D_n = \{x \in \mathbb{Z}^n \mid \sum_{i=1}^{n} x_i \equiv 0 \mod 2\} \quad (n \ge 4).$$

We will prove Conjecture 1 for the Voronoï regions of the lattices $A_n$ in every dimensions $n \ge 2$. For the lattices $D_n$, we can only show the inequality

$$m_1(\mathbb{R}^n, \|\cdot\|_{\mathcal{P}}) \le \frac{1}{(3/4)2^n + n - 1}$$

which is however asymptotically of the order $O(\frac{1}{2^n})$.

Let us now give an idea of the method that we use to prove these results. The strategy is to transfer the study of sets avoiding distance 1 to a discrete setting, in which such sets can be decomposed as the disjoint union of small pieces (in other words they afford a kind of block structure). Computing the optimal density of a set avoiding distance 1 in the discrete setting amounts then to understanding how these blocks fit together locally.

To be more precise, we consider discrete subsets $V$ of $\mathbb{R}^n$, seen as induced subgraphs of the *unit distance graph* $G(\mathbb{R}^n, \|\cdot\|)$. This is the graph whose vertices are the points of $\mathbb{R}^n$ and whose edges connect the vertices $x$ and $y$ if and only if $\|x - y\| = 1$.

If $G = (V, E)$ is a finite induced subgraph of $G(\mathbb{R}^n, \|\cdot\|)$, then it is well known that (see [8])

$$m_1(\mathbb{R}^n, \|\cdot\|) \le \frac{\alpha(G)}{|V|},$$

where as usual $\alpha(G)$ denotes the *independence number* of $G$ and $|V|$ is the number of its vertices. We use a generalization of this inequality to discrete graphs (see Subsection 2.3). Of course, the most difficult task is to design an appropriate discrete subset $V$, i.e. one that provides a good upper bound of $m_1(\mathbb{R}^n, \|\cdot\|)$ and at the same time is easy to analyse.

For the regular hexagon in the plane, we follow an idea due to Dmitry Shiryaev [11] who proposed an auxiliary graph satisfying the following remarkable property: if two points $x$ and $y$ are at graph distance 2, then they are at polytope distance 1. This implies that a set avoiding polytope distance 1 is a union of cliques whose closed neighborhoods are disjoint.
The density of such a set is bounded by the supremum of the local densities of the cliques in their closed neighborhood. In the case of a general hexagonal Voronoï cell in the plane, this approach doesn't work straightforwardly and we need to introduce a different graph with a slightly weaker property. The construction of such an auxiliary graph is also a key ingredient of our proofs of the bounds for the Voronoï regions of $A_n$ and $D_n$.

The paper is organized as follows: Section 2 contains preliminaries. In Section 3, we prove Theorem 1. Section 4 is dedicated to the families of lattices $A_n$ (Theorem 4) and $D_n$ (Theorem 5). In Section 5, we discuss the chromatic number of the unit distance graph $G(\mathbb{R}^n, \|\cdot\|_P)$.

We provide in Appendix A, the rather technical proof of Lemma 1, which gives an alternate definition of the maximal density of an independent set of a discrete graph whose vertices have finite degrees.

## 2. PRELIMINARIES

**2.1. The density of a set avoiding polytope distance 1.** Let $\mathbb{R}^n$ be equipped with a norm $\|\cdot\|$. A set $S \subset \mathbb{R}^n$ is said to avoid 1 if for every $x, y \in S$, $d(x, y) = \|x - y\| \neq 1$. We define the density of a measurable set $A \subset \mathbb{R}^n$ with respect to Lebesgue measure as:

$$ \delta(A) = \limsup_{R \to \infty} \frac{\mathrm{Vol}(A \cap [-R, R]^n)}{\mathrm{Vol}([-R, R]^n)}, $$

and we denote by $m_1(\mathbb{R}^n, \|\cdot\|_P)$ the supremum of the densities achieved by measurable sets avoiding distance 1:

$$ m_1(\mathbb{R}^n, \|\cdot\|_P) = \sup_{S \subset \mathbb{R}^n \text{ measurable, avoiding 1}} \delta(S). $$

Let $\mathcal{P}$ be a convex symmetric polytope. The norm $\|\cdot\|_\mathcal{P}$ associated with $\mathcal{P}$ is defined by

$$ \|x\|_{\mathcal{P}} = \inf\{\lambda \in \mathbb{R}_+ | x \in \lambda \mathcal{P}\}, $$

and we call polytope distance the distance induced by $\|\cdot\|_\mathcal{P}$.

If $B_\mathcal{P}(r) = \{x \in \mathbb{R}^n | \|x\|_\mathcal{P} < r\}$, we have by definition:

$$ x \in B_{\mathcal{P}}(1) \Leftrightarrow x \in \mathcal{P} \text{ and } \|x\|_{\mathcal{P}} = 1 \Leftrightarrow x \in \partial \mathcal{P}, $$

where $\mathcal{P}$ denotes the interior of $\mathcal{P}$ and $\partial \mathcal{P}$ its boundary.

A polytope $\mathcal{P}$ tiles $\mathbb{R}^n$ by translations if there exists $\Lambda \subset \mathbb{R}^n$ such that $\bigcup_{\lambda \in \Lambda}(\lambda + \mathcal{P}) = \mathbb{R}^n$ and for every $\lambda \neq \lambda'$, $(\lambda + \mathcal{P}) \cap (\lambda' + \mathcal{P}) = \emptyset$. If $\mathcal{P}$ is such a polytope, the set

$$ A = \bigcup_{\lambda \in \Lambda} \left( \lambda + \frac{1}{2} \mathcal{P} \right) $$

avoids 1, and has density $\frac{1}{2^n}$. This set gives a lower bound for $m_1$:

**Proposition 1.** If $\mathcal{P}$ is a polytope tiling $\mathbb{R}^n$ by translation, and $\|\cdot\|_\mathcal{P}$ the norm associated with $\mathcal{P}$, then

$$ m_1(\mathbb{R}^n, \|\cdot\|_\mathcal{P}) \geq \frac{1}{2^n}. $$
2.2. **Parallelohedra and the Voronoï's Conjecture.** A $n$-dimensional *parallelohedron* is a polytope $\mathcal{P}$ that tiles *face-to-face* $\mathbb{R}^n$ by translation, i.e there is a tiling such that the intersection between two translates of $\mathcal{P}$, if non empty, is a common face of both of them. Works by Minkowski [10], Venkov [14], and McMullen [9] have led to a proof that the convex bodies tiling space by translation are exactly the parallelohedra, and moreover they tile $\mathbb{R}^n$ by a lattice.

Let us recall that a *lattice* $\Lambda \subset \mathbb{R}^n$ is a discrete subgroup of the form $\bigoplus_{i=1}^n \mathbb{Z}e_i$ where $\{e_1, \dots, e_n\}$ is a basis of $\mathbb{R}^n$ (for a general reference on lattices, see e.g [2]). The *Voronoï region* of $\Lambda$ is defined by

$$V = V_{\Lambda} = \{z \in \mathbb{R}^n, \forall x \in \Lambda, \langle z - x, z - x \rangle \ge \langle z, z \rangle\},$$

where $\langle \cdot, \cdot \rangle$ denotes the usual scalar product on $\mathbb{R}^n$. The Voronoï region of a lattice is a parallelohedron. Voronoï conjectured that the converse is also true, up to an affine transformation:

**Conjecture 2 (Voronoï's Conjecture).** If $\mathcal{P}$ is a *parallelohedron* in $\mathbb{R}^n$, then there is an affine map $\varphi : \mathbb{R}^n \to \mathbb{R}^n$ such that $\varphi(\mathcal{P})$ is the *Voronoï region* of a lattice $\Lambda \subset \mathbb{R}^n$.

This conjecture has been solved for several families of parallelohedra. For instance, Voronoï himself [15] proved it for *primitive parallelohedra*, and Erdahl [5] solved it for *zonotopal parallelohedra*. Moreover, Delone [4] has shown that Voronoï's conjecture is true in dimensions up to 4.

According to Voronoï's conjecture, we focus on polytopes that are Voronoï regions of lattices.

2.3. **Discretization of the problem.** A set avoiding distance 1 in $\mathbb{R}^n$ is exactly an independent set in $G(\mathbb{R}^n, \|\cdot\|)$, i.e. a subset $S$ of vertices such that, for all $x, y \in S$, $\|x-y\| \neq 1$. Therefore $m_1(\mathbb{R}^n, \|\cdot\|)$ is the supremum of the densities achieved by independent sets. It is the analogue of the *independence ratio* $\bar{\alpha}(G) = \frac{\alpha(G)}{|V|}$ of a finite graph $G$.

Let $G = (V, E)$ be a discrete induced subgraph of $G(\mathbb{R}^n, \|\cdot\|)$. For $A \subset V$, we define the density of $A$ in $G$:

$$(1) \qquad \delta_G(A) = \limsup_{R \to \infty} \frac{|A \cap V_R|}{|V_R|}$$

where $V_R = V \cap [-R, R]^n$. Based on this notion, we extend the definition of the independence ratio to discrete graphs:

$$\bar{\alpha}(G) = \sup_{A \text{ independent set}} \delta_G(A).$$

In this paper, we use the following equivalent formulation of $\bar{\alpha}(G)$:

**Lemma 1.** Let $G = (V, E)$ be a discrete graph with $V \subset \mathbb{R}^n$. If every $v \in V$ has finite degree, then

$$\bar{\alpha}(G) = \limsup_{R \to \infty} \bar{\alpha}(G_R),$$

where $G_R$ is the finite induced subgraph of $G$ whose set of vertices is $V_R = V \cap [-R, R]^n$.

*Proof.* This lemma is proved in Appendix A along with a discussion on the importance of the hypothesis that all the vertices of the graph have finite degree. $\square$

Discrete subgraphs induced by $G(\mathbb{R}^n, \|\cdot\|)$ provide upper bounds of $m_1(\mathbb{R}^n, \|\cdot\|)$ thanks to the following lemma:
**Lemma 2.** Let $G = (V, E)$ be a discrete subgraph induced by $G(\mathbb{R}^n, \|\cdot\|)$. Then

$$m_1(\mathbb{R}^n, \|\cdot\|) \le \bar{\alpha}(G).$$

*Proof.* By Lemma 1, we may assume without loss of generality that $G$ is finite. In this case the result is well known: the proof below is for the sake of completeness.

Let $R > 0$ be a real number, and let $X \in [-R, R]^n$ chosen uniformly at random. For $S \subset \mathbb{R}^n$, the probability that $X$ is in $S$ is $\mathbb{P}(X \in S) = \frac{\mathrm{Vol}(S \cap [-R, R]^n)}{\mathrm{Vol}([-R, R]^n)}$. Notice that $\limsup_{R \to \infty} \mathbb{P}(X \in S) = \delta(S)$.

Let $S \subset \mathbb{R}^n$ be a set avoiding 1. We define the random variable $N = |(X + V) \cap S|$. On one hand, we have:

$$\mathbb{E}\left[\frac{N}{|V|}\right] = \frac{1}{|V|}\mathbb{E}\left[\sum_{v \in V} \mathbb{1}_{\{X+v \in S\}}\right] = \frac{1}{|V|}\sum_{v \in V} \mathbb{P}(X \in S - v).$$

For every $v$, we have $\limsup_{R \to \infty} \mathbb{P}(X \in S - v) = \delta(S - v) = \delta(S)$.

On the other hand, since for $v_1, v_2 \in V$, $\|(X - v_1) - (X - v_2)\| = \|v_1 - v_2\|$, and $(X + V) \cap S \subset S$, we have, for any $R > 0$,

$$\frac{N}{|V|} \le \bar{\alpha}(G).$$

Thus we get,

$$\delta(S) \le \bar{\alpha}(G).$$

□

In order to give a first example, we consider the most natural lattice: the cubic lattice. The associated tiling and norm are respectively the cubic tiling and the well known sup norm $\|x\|_{\infty} = \sup_{1 \le i \le n} |x_i|$. More precisely, if $L = 2\mathbb{Z}^n$, the Voronoï region of $L$ is the cube whose vertices are the points of coordinates $(\pm 1, \pm 1, \dots, \pm 1)$.

**Proposition 2.** For every $n \ge 1$, we have:

$$m_1(\mathbb{R}^n, \|\cdot\|_{\infty}) = \frac{1}{2^n}$$

*Proof.* Let $V = \{0, 1\}^n \subset \mathbb{R}^n$ and let $G$ be the subgraph of $G(\mathbb{R}^n, \|\cdot\|)$ induced by $V$. Following the definition of $V$, for every $v, v' \in V$ with $v \ne v'$, we have $\|v - v'\|_{\infty} = 1$. So $G$ is a complete graph, thus its independence number is 1. Since it has $2^n$ vertices, applying Lemma 2, we get

$$m_1(\mathbb{R}^n, \|\cdot\|_{\infty}) \le \frac{\alpha(G)}{|V|} = \frac{1}{2^n}.$$

□

### 3. PARALLELOHEDRON NORMS IN THE PLANE

In this section, we prove Theorem 1. It is well known that the parallelohedra in dimension 2, are, up to an affine transformation, the Voronoï regions of a lattice, and that their combinatorial type is either that of a square or of a hexagon (see Figure 3).

We have already seen that $m_1(\mathbb{R}^2, \|\cdot\|_{\infty}) = \frac{1}{4}$, so it remains to deal with hexagons. Even though it is not true that every hexagonal Voronoï region is linearly equivalent to the
<figure><img src="image_4.png" /><figcaption>FIGURE 3. The two kinds of Voronoï regions of lattices in the plane.</figcaption></figure>

regular hexagon, we will first consider the regular hexagon in order to present in this basic case, the ideas that will be used in the general case.

3.1. **The regular hexagon.** The following result is due to Dmitry Shiryaev [11]:

**Theorem 2.** If $\mathcal{P}$ is the regular hexagon in the plane, then

$$m_1(\mathbb{R}^2, \| \cdot \|_{\mathcal{P}}) = \frac{1}{4}.$$

Let $\mathcal{P}$ be the regular hexagon in $\mathbb{R}^2$. We denote by $S$ its set of vertices and by $\partial \mathcal{P}$ its boundary. Thus, $\|x\|_{\mathcal{P}} = 1$ if and only if $x \in \partial \mathcal{P}$. We label the vertices of $\mathcal{P}$ modulo 6 as described in Figure 4.

The set $\frac{1}{2}S$ spans a lattice $V$. Let us consider $G_{\mathcal{P}}$, the subgraph of $G(\mathbb{R}^2, \| \cdot \|_{\mathcal{P}})$ induced by $\tilde{V}$. We shall prove that $\bar{\alpha}(G_{\mathcal{P}}) \le 1/4$. To do so, we introduce an auxiliary graph $\tilde{G} = (\tilde{V}, \tilde{E})$, which is the Cayley graph with the same set of vertices $\tilde{V} = V$ corresponding to the generating set $\frac{1}{2}S$. In other words, for $x, y \in V$, $(x, y) \in \tilde{E}$ if and only if $x - y \in \frac{1}{2}S$. This graph is drawn in Figure 4.

We denote by $\tilde{d}(x, y)$ the distance between two vertices $x$ and $y$ in the graph $\tilde{G}$, i.e. the minimal length of a path in $\tilde{G}$ between $x$ and $y$. We define the distance $\tilde{d}(A, B)$ in $\tilde{G}$ between two subsets of vertices $A$ and $B$ as the minimal distance between a vertex of $A$ and a vertex of $B$. The following lemma will be crucial for the proof of Theorem 2:

<figure><img src="image_5.png" /><figcaption>FIGURE 4. The regular hexagon and the Cayley graph $\tilde{G}$.</figcaption></figure>

**Lemma 3.** Let $u_1$ and $u_2$ be two vertices of $\tilde{G}$. Then:

$$ (\text{Property D}) \qquad \tilde{d}(u_1, u_2) = 2 \Rightarrow \|u_1 - u_2\|_{\mathcal{P}} = 1. $$

*Proof.* Since $\tilde{G}$ is vertex-transitive, we may assume without loss of generality that $u_1 = 0$. The vertices $u$ at graph distance 2 from 0 must be of the form $\frac{v_i}{2} + \frac{v_j}{2}$. It is not hard to check that if $u_2 = \frac{v_i+v_j}{2}$ is neither 0 nor another $\frac{v_k}{2}$ (in which case $\tilde{d}(0, u_2) < 2$), then it is a point of $\partial \mathcal{P}$ (see also Figure 4). □
**Remark 1.** It can be noted, although it will not be useful here, that the equivalence $\tilde{d}(u_1, u_2) = 2 \Leftrightarrow \|u_1 - u_2\|_P = 1$ holds.

For a set $A \subset \tilde{V}$, we define its closed neighborhood

$$N[A] = \{v \in \tilde{V} \text{ such that } \tilde{d}(v, A) \le 1\} = A + \left(\{0\} \cup \frac{1}{2}S\right).$$

Now we consider the cliques of $\tilde{G}$, that is the sets $C \subset \tilde{V}$ such that for every $u \neq v \in C$, $\tilde{d}(u, v) = 1$. We will use the following lemma several times: it shows that for any graph $\tilde{G}$ satisfying (Property D), if $A \subset \tilde{V}$ avoids polytope distance 1, then $A$ is a union of cliques whose closed neighborhoods are disjoint:

**Lemma 4.** Let $\|\cdot\|_P$ be a polytope norm in $\mathbb{R}^n$, and $G_P$ an induced subgraph of $G(\mathbb{R}^n, \|\cdot\|_P)$. Assume there exists an auxiliary graph $\tilde{G}$ with the same vertices $V$ as $G_P$ satisfying (Property D). Let $A \subset V$ avoiding polytope distance 1. Then $A$ may be written as a union of cliques of $\tilde{G}$

$$A = \bigcup_{C \in \mathcal{C}} C$$

such that if $C, C' \in \mathcal{C}$ with $C \neq C'$, then

$$N[C] \cap N[C'] = \emptyset.$$

*Proof.* Let us consider the decomposition of $A$ in connected components with respect to $\tilde{G}$. Following Lemma 3, since $A$ avoids polytope distance 1, a connected component $C$ cannot contain two vertices at graph distance 2 from each other. So $C$ must be a clique.

Assume that two different cliques $C$ and $C'$ of $A$ share a common neighbor. Thus $\tilde{d}(C, C') \le 2$. Since $C$ and $C'$ are two disjoint connected components, $\tilde{d}(C, C') > 1$. So $\tilde{d}(C, C') = 2$, which is impossible, since $A$ avoids polytope distance 1. $\square$

Now we define the local density of a clique $C$ of $\tilde{G}$: $\delta^0(C) = \frac{|C|}{|N[C]|}$. In the next lemma, we analyse the different possible cliques of the graph $\tilde{G}$ that we constructed for the regular hexagon, and determine their local density:

**Lemma 5.** For every clique $C \subset \tilde{G}$,

$$\delta^0(C) \le \frac{1}{4}$$

*Proof.* Let $C$ be a clique of $\tilde{G}$. Since $\tilde{G}$ is vertex transitive, we can assume without loss of generality that $0 \in C$. Up to the action of the dihedral group $D_3$ on $V$, there are only three possible cliques in $\tilde{G}$ containing 0, and one can easily determine their neighborhoods (see Figure 5):

* $C = \{0\}$: its neighborhood is $\{0\} \cup \frac{1}{2}S$. Thus $\delta^0(C) = \frac{1}{7}$.

* $C = \{0, \frac{v_0}{2}\}$, and $\delta^0(C) = \frac{2}{10} = \frac{1}{5}$.

* $C = \{0, \frac{v_0}{2}, \frac{v_1}{2}\}$, and $\delta^0(C) = \frac{3}{12} = \frac{1}{4}$.

$\square$

We have all the ingredients to prove that the density of a set avoiding 1 for the regular hexagon can not exceed $1/4$:
<figure><img src="image_6.png" /><figcaption>FIGURE 5. The possible cliques and their neighborhood.</figcaption></figure>

*Proof of Theorem 2.* Following Lemma 2, it is sufficient to prove $\bar{\alpha}(G_P) \le \frac{1}{4}$. If $A \subset V$ is a set avoiding 1, it may be written as the union of cliques in $\tilde{G}$, whose neighborhoods are disjoint (Lemma 4). So the density of $A$ is upper bounded by the maximum local density of a clique in $\tilde{G}$. So, from Lemma 5, $\bar{\alpha}(G_P) \le \frac{1}{4}$. □

3.2. **General hexagonal Voronoï regions.** In this subsection, we deal with a general hexagonal Voronoï region $\mathcal{P}$ of the plane, and prove:

**Theorem 3.** If $\mathcal{P}$ is an hexagonal Voronoï region in the plane, then

$$m_1(\mathbb{R}^2, \| \cdot \|_{\mathcal{P}}) = \frac{1}{4}.$$

Let $\mathcal{P}$ be the hexagonal Voronoï region of a lattice $L \subset \mathbb{R}^2$. Let $\{\beta_0, \beta_1\}$ be a basis of $L$ such that the vectors $\beta_0, \beta_1, \beta_2 = \beta_1 - \beta_0$, and their opposites define the faces of $\mathcal{P}$. We label the vertices $v_i$, for $0 \le i \le 5$, of $\mathcal{P}$ in such a way that $\beta_i = v_i + v_{i+1}$, where $i$ is defined modulo 6. This situation is depicted in Figure 6.

<figure><img src="image_7.png" /><figcaption>FIGURE 6. The vectors $\beta_i$ and the vertices of the hexagon.</figcaption></figure>

In order to prove Theorem 3, just like in the case of the regular hexagon, we shall construct a graph $G_P$ induced by $G(\mathbb{R}^2, \| \cdot \|_{\mathcal{P}})$, and prove that $\bar{\alpha}(G_P) \le 1/4$. Unfortunately, in general, the vertices of $\mathcal{P}$ do not span a lattice. We will use a different point of view in order to build $G_P$, together with an auxiliary graph $\tilde{G}$ that will satisfy a weaker version of (Property D).

For the set $V$ of vertices of $G_P$, we take the lattice $\frac{1}{2}L$, together with the translates of the vertices $V_P$ of $\mathcal{P}$ by $\frac{1}{2}L$. We set $A = \frac{1}{2}L$ and $B = V_P + \frac{1}{2}L$ so that $V = A \cup B$;
this construction is represented in Figure 7 where the vertices of A are depicted in red, and those of B in green.

<figure><img src="image_8.png" /><figcaption>FIGURE 7. Constructing the set of vertices of $G_P$</figcaption></figure>

Let us note that for every $i$, $v_{i+2} = v_i \mod L$. Indeed,

$$v_{i+2} - v_i = v_{i+2} + v_{i+1} - (v_i + v_{i+1}) = \beta_{i+1} - \beta_i = \beta_{i+2}.$$

As a consequence, we may write $V$ as the disjoint union of three sets:

$$V = \frac{1}{2}L \cup (\frac{1}{2}L + v_0) \cup (\frac{1}{2}L + v_1),$$

and this implies that the density of $B$ in $V$ is twice that of $A$.

Now, let us construct the auxiliary graph $\tilde{G} = (\tilde{V}, \tilde{E})$. It has the same vertices as $G_P$, i.e. $\tilde{V} = V$. Let us describe the edges of $\tilde{G}$. By construction, there are exactly 7 vertices of $V$ in the interior of $\tilde{P}$: the center $0 \in A$, and six points of $B$ denoted $s_0, \dots, s_5$, with

$$s_i = \frac{v_{i-1} + v_{i+1}}{2}.$$

For every point of $a \in A$, we define the edges $(a, a + s_i)$ and $(a + s_i, a + s_{i+1})$ for $i$ from 0 to 5. This is illustrated in Figure 8.

<figure><img src="image_9.png" /><figcaption>FIGURE 8. Constructing the edges of $\tilde{G}$.</figcaption></figure>

**Remark 2.** In the case of the regular hexagon, this construction leads to the same graph $\tilde{G}$ that we considered in Subsection 3.1.

Let us describe the neighborhood (with respect to $\tilde{G}$) of each type of point. By construction, a point in $A$ has 6 neighbors, and they all belong to $B$. A vertex $a + s_i$ of $B$ also has six neighbors. Three of them are elements of $A$, namely $a, a + \frac{\beta_i}{2}$ and $a + \frac{\beta_{i-1}}{2}$ and the other three are elements of $B$, namely, $a + s_{i-1}, a + s_{i+1}$ and $a + v_i$. Figure 9 illustrates the neighborhoods of the vertices of $\tilde{G}$.

It should be noted that (Property D) is not in general fulfilled by $\tilde{G}$: indeed, the vertices $s_0$ and $s_3$ are at graph distance 2 in $\tilde{G}$ but not (in general) at polytope distance 1. However,
<figure><img src="image_10.png" /><figcaption>FIGURE 9. The basic pattern in $\tilde{G}$.</figcaption></figure>

this property continues to hold for points that share a common neighbor in B. We prove this in the next lemma, which will play the role of Lemma 3 for this new graph $\tilde{G}$:

**Lemma 6.** If two vertices $x, y \in V$ are at distance 2 from each other in $\tilde{G}$ and have a common neighbor $z \in B$, then $\|x - y\|_P = 1$.

*Proof.* First suppose that at least one of the two vertices is in A. In this case we may assume $x = 0$. Then $z$ is one of the $s_i$, and following the analysis of the neighbors of $s_i$, $y$ must be in the set $\{0, s_{i-1}, s_{i+1}, \frac{\beta_i}{2}, \frac{\beta_{i-1}}{2}, v_i\}$. The first three are obviously not at graph distance 2 from 0, so $y$ is one of the last three vertices, and they all are in $\partial P$. Thus, $\|x - y\|_P = 1$.

Now suppose $x, y, z \in B$. Then we may assume without loss of generality $x = s_{i-1}$, and $z = s_i$. Since $z$ has only three neighbors in B, $y$ can be either $s_{i+1}$ or $v_i$. We have:

$$s_{i+1} - s_{i-1} = \frac{v_i + v_{i+2}}{2} - \frac{v_i + v_{i-2}}{2} = \frac{v_{i+2} - v_{i-2}}{2} = \frac{v_{i+2} + v_{i+1}}{2} = \frac{\beta_{i+1}}{2}$$

and

$$v_i - s_{i-1} = v_i - \frac{v_i + v_{i-2}}{2} = \frac{v_i - v_{i-2}}{2} = \frac{v_i + v_{i+1}}{2} = \frac{\beta_i}{2}.$$

In both cases $\|x - y\|_P = 1$. □

Let $U \subset V$ be a set of vertices avoiding polytope distance 1, let $C$ be a connected component of $U$ and let $N[C]$ be its closed neighborhood. We define:

$$N_B[C] = N[C] \cap B$$

and

$$\delta_B^0(C) = \frac{|C|}{|N_B[C]|}.$$

The following lemma is the analogue of Lemma 4 in this situation: we show that if $C$ and $C'$ are two different connected components, then $N_B[C]$ and $N_B[C']$ must be disjoint:

**Lemma 7.** Let $U \subset V$ be a set avoiding polytope distance 1. If $C \neq C'$ are two connected components of $U$, then

$$N_B[C] \cap N_B[C'] = \emptyset.$$

*Proof.* If a vertex $z \in B$ is in both $N_B[C]$ and $N_B[C']$, then there is $x \in C$, $y \in C'$ such that $\tilde{d}(x, z) = \tilde{d}(z, y) = 1$. Since $C$ and $C'$ are connected components of $U$, we have
$\tilde{d}(x, y) > 1$. Thus $\tilde{d}(x, y) = 2$ and by Lemma 6, $\|x - y\|_P = 1$, which is impossible, since $U$ avoids 1. $\square$

Now we study the different possible connected components:

**Lemma 8.** Let $U \subset V$ be a set avoiding polytope distance 1. If $C$ is a connected component of $U$, then

$$ \delta_B^0 \le \frac{3}{8}. $$

*Proof.* We enumerate the possible connected components. Let us start with the isolated points. Up to translations by $\frac{1}{2}L$, we have:

* $C = \{0\} \subset A$. Its neighborhood is made of six vectors from $B$. So $\delta_B^0(C) = 1/6$.

* $C = \{s_i\} \subset B$. We know that such a vertex has three neighbors in $B$, thus $\delta_B^0(C) = 1/4$.

<figure><img src="image_11.png" /><figcaption>FIGURE 10. The two possible types of connected component with one element. The circled vertices denote the elements of $C$ and the figure represents all their neighbors in $B$.</figcaption></figure>

We now focus on the connected components of size 2. Since a vertex in $A$ has all its neighbors in $B$, such a connected component can not contain two elements of $A$. Thus, up to translation, we only have:

* $C = \{0, s_i\}$, and the only neighbor in $B$ that is not a neighbor of 0 is $v_i$. Thus $\delta_B^0 = 2/7$.

* $C = \{s_i, s_{i+1}\}$ and the neighbors in $B$ are $s_{i-1}, v_i, s_{i+2}, v_{i+1}$. Thus $\delta_B^0 = 2/6 = 1/3$.

<figure><img src="image_12.png" /><figcaption>FIGURE 11. The two possible types of connected component with two elements.</figcaption></figure>

There are up to translations two kinds of connected components of size three:

* $C = \{0, s_i, s_{i+1}\}$. The only neighbor of $s_{i+1}$ in $B$ that is not a neighbor of $\{0, s_i\}$ is $v_{i+1}$. Thus $\delta_B^0 = 3/8$.
• $C = \{0, s_i, -s_i\}$. The only neighbor of $-s_i$ in $B$ that is not a neighbor of $\{0, s_i\}$ is $-v_i$. Thus $\delta_B^0 = 3/8$.

<figure><img src="image_13.png" /><figcaption>FIGURE 12. The two possible types of connected component with three elements.</figcaption></figure>

It is easy to check, applying Lemma 6, that we have enumerated all kind of connected components of $U$. □

Finally we can put everything together and complete the proof of Theorem 3:

*Proof of Theorem 3.* Let $U \subset V$ avoiding polytope distance 1. We define

$$ \delta_B(U) = \limsup_{R \to \infty} \frac{|U \cap V_R|}{|B \cap V_R|} $$

where as usual $V_R = V \cap [-R, R]^n$. We have:

$$ \delta_{G_P}(U) = \delta_B(U) \times \delta_{G_P}(B), $$

and since $V = A \cup B$ and $B$ is twice as dense as $A$ in $G_P$,

$$ \delta_{G_P}(U) = \frac{2}{3}\delta_B(U). $$

From Lemma 7, we have $\delta_B(U) \le \sup_{C \subset U} \delta_B^0(C)$ where $C$ runs over the connected components of $U$. Then Lemma 8 shows that

$$ \delta_B(U) \le \frac{3}{8} $$

and we get

$$ \delta_{G_P}(U) \le \frac{2}{3} \times \frac{3}{8} = \frac{1}{4}. $$

□

## 4. THE NORMS ASSOCIATED WITH THE VORONOÏ REGIONS OF THE LATTICES $A_n$ AND $D_n$

### 4.1. The lattice $A_n$. Here we consider for any $n \ge 2$, the lattice

$$ A_n = \mathbb{Z}^{n+1} \cap H, $$

where $H$ is the hyperplane $H = \{(x_1, \dots, x_{n+1}) \in \mathbb{R}^{n+1} \mid \sum_{i=1}^{n+1} x_i = 0\}$. Let $\mathcal{P}$ be the Voronoï region of $A_n$. We shall prove:

**Theorem 4.** For every dimension $n \ge 2$, if $\mathcal{P}$ is the Voronoï region of the lattice $A_n$, then

$$ m_1(\mathbb{R}^n, \| \cdot \|_{\mathcal{P}}) = \frac{1}{2^n}. $$
In fact, for $n = 2$, the Voronoï region of $A_2$ is nothing but the regular hexagon. We are going to generalize to all dimensions $n \ge 2$ the strategy that we used in subsection 3.1.

Let us recall the description of the Voronoï region $\mathcal{P}$ of $A_n$ given in [2, Chapter 21, section 3].

The orthogonal projection on $H$ is denoted by $p_H$. Let, for $1 \le i \le n$ and $j := (n+1)-i$,

$$ 
\begin{aligned}
v_i &= p_H((0, \dots, 0, \underbrace{1, \dots, 1}_{i \text{ times}})) \\
&= (0, \dots, 0, 1, \dots, 1) - \underbrace{\frac{j}{n+1}}_{i \text{ times}} (1, \dots, 1) \\
&= \underbrace{(\frac{-j}{n+1}, \dots, \frac{-j}{n+1}}_{i \text{ times}}, \underbrace{\frac{i}{n+1}, \dots, \frac{i}{n+1}}_{j \text{ times}}).
\end{aligned}
$$

Let $S$ be the simplex whose vertices are 0 and the vectors $v_i$. Then the vertices of $\mathcal{P}$ are the images of the non zero vertices of $S$ under the permutation group $\mathfrak{S}_{n+1}$. In other words, the set of vertices of $\mathcal{P}$ is

$$ V_{\mathcal{P}} = \{p_H(u) \mid u \in V_0\}, \text{ where } V_0 = \{0, 1\}^{n+1} \setminus \{(0, \dots, 0), (1, \dots, 1)\}. $$

We also analyze the boundary of $\mathcal{P}$, in order to understand the norm associated with $\mathcal{P}$. The non zero vertices of $S$ are supported by the hyperplane $H_{0,n}$ of $H$ defined by $H_{0,n} = \{x = (x_0, \dots, x_n) \in H \mid x_n - x_0 = 1\}$. Applying $\mathfrak{S}_{n+1}$, we find that the faces of $\mathcal{P}$ are supported by all the $H_{i,j} = \{x = (x_0, \dots, x_n) \in H \mid x_j - x_i = 1\}$, for $i \ne j$. So

$$ \left\{ \begin{array}{ll} x \in \mathcal{P} & \text{if and only if for all } i \neq j, x_j - x_i \le 1 \\ x \in \partial \mathcal{P} & \text{if and only if } \max_{i \neq j}(x_j - x_i) = \max_j x_j - \min_i x_i = 1, \end{array} \right. $$

and more generally the norm $\|x\|_{\mathcal{P}}$ of a vector $x \in H$ is given by

$$ \|x\|_{\mathcal{P}} = \max_j x_j - \min_i x_i. $$

Note that if $x = p_H(u)$, because $H^{\perp} = \mathbb{R}(1, \dots, 1)$, we have

$$ \max_j x_j - \min_i x_i = \max_j u_j - \min_i u_i. $$

The vertices of $\mathcal{P}$ generate a lattice, which is the dual lattice of $A_n$:

**Lemma 9.** The vertices of $\mathcal{P}$ span over $\mathbb{Z}$ the lattice $A_n^{\#} = p_H(\mathbb{Z}^{n+1})$.

*Proof.* Let $v \in V_{\mathcal{P}}$. There is $u \in V_0$ such that $v = p_H(u)$. Since $(u - p_H(u)) \in H^{\perp}$, we have, for every $x \in A_n = \mathbb{Z}^{n+1} \cap H$,

$$ \langle x, v \rangle = \langle x, p_H(u) \rangle = \langle x, u \rangle = \sum_{i, u_i=1}^{n} x_i \in \mathbb{Z}, $$

so $\mathrm{span}_{\mathbb{Z}}(V_{\mathcal{P}}) \subset A_n^{\#}$.

Now let us take $x \in A_n^{\#} = p_H(\mathbb{Z}^{n+1})$, so $x = p_H(z_0, \dots, z_n)$, with $z_i \in \mathbb{Z}$. Then

$$ x = p_H(z_0, \dots, z_n) = \sum_{i=0}^{n} z_i p_H(0, \dots, 0, \underbrace{1}_{i}, \dots, 0) \in \mathrm{span}_{\mathbb{Z}}(V_{\mathcal{P}}). $$

Thus $\mathrm{span}_{\mathbb{Z}}(V_{\mathcal{P}}) = A_n^{\#}$. $\square$
We consider the subgraph $G_P$ of $G(\mathbb{R}^n, \|\cdot\|_P)$ induced by the set of vertices $\frac{1}{2}A_n^\#$, and the auxiliary graph $\tilde{G}$ which is the Cayley graph on $\frac{1}{2}A_n^\#$ associated with the generating set $\frac{1}{2}V_P$. These graphs are the generalizations of the graphs that we considered in subsection 3.1. Here we show that $\tilde{G}$ satisfies the same remarkable property:

**Lemma 10.** The graph $\tilde{G}$ satisfies (Property D).

*Proof.* We follow the proof of Lemma 3. We may assume $x = 0$, and we need to show that, for $v, v' \in V_P$, if $\frac{v+v'}{2} \neq 0$ then it is either some $\frac{v''}{2} \in \frac{1}{2}V_P$, or an element of $\partial P$. Equivalently, we study $v + v'$ and show that one of the three following situations occurs:

$$ \left\{ \begin{array}{l} v + v' = 0, \\ v + v' = v'' \in V_P, \\ \|v + v'\|_P = 2. \end{array} \right. $$

Let $u$ and $u'$ be elements of $V_0 = \{0, 1\}^{n+1} \setminus \{(0, \dots, 0), (1, \dots, 1)\}$ such that $v = p_H(u)$ and $v' = p_H(u')$. The coordinates of the vector $u + u'$ belong to $\{0, 1, 2\}$, but cannot be all 0 nor all 2. We explore the possible cases:

* If $u + u' = (1, \dots, 1)$, then $p_H(u + u') = (0, \dots, 0)$, and $v + v' = 0$.

* If the coordinates of $u + u'$ are only 0's and 1's, then $u + u' \in V_0$, and thus $v + v' \in V_P$.

* If the coordinates of $u + u'$ are only 1's and 2's, we may decompose $u + u'$ as $u + u' = (1, \dots, 1) + w$, and $w$ must be an element of $V_0$. This implies that $v + v' = p_H(w) \in V_P$.

* The last remaining case is when both 0's and 2's appear in the coordinates of $U = u + u'$. Then, $\max_j U_j - \min_i U_i = 2$, that is $\|v + v'\|_P = 2$.

□

Because $\tilde{G}$ satisfies (Property D), Lemma 4 is satisfied by $\tilde{G}$. So we can proceed to analyze the cliques of $\tilde{G}$, and for each of them, determine its local density. Since $\tilde{G}$ is vertex transitive, we only describe the cliques containing 0. For $u \in V_0$, we define its support $I = \{i \in \{1, \dots, n+1\}, u_i = 1\}$.

**Lemma 11.** The cliques of $\tilde{G}$ containing 0 are the sets of the form

$$ \left\{ 0, \frac{p_H(u_1)}{2}, \dots, \frac{p_H(u_s)}{2} \right\} $$

such that if $I_i$ is the support of $u_i$, then

$$ I_1 \subset I_2 \subset \dots \subset I_s. $$

In particular, since $s \le n$, a clique can not contain more than $n+1$ vertices.

*Proof.* Let $C$ be a clique of $\tilde{G}$, and assume $0 \in C$. Then the other elements of $C$ must belong to $\frac{1}{2}V_P$ and since $C$ is a clique, they must be adjacent in the graph. In other words, if $\frac{v}{2}, \frac{v'}{2} \in C$, then $\frac{v-v'}{2} \in \frac{1}{2}V_P$. Let $v \neq v' \in V_P$, and $u, u' \in V_0$ such that $v = p_H(u)$ and $v' = p_H(u')$. We denote by $I$ and $I'$ the respective supports of $u$ and $u'$. For $i \in \{1, \dots, n+1\}$, the $i$th coordinate of $u - u'$ is:

$$ \left\{ \begin{array}{ll} 1 & \text{if } i \in I \setminus I', \\ -1 & \text{if } i \in I' \setminus I, \\ 0 & \text{otherwise.} \end{array} \right. $$
If both 1 and -1 appear in the coordinates of $u-u'$, then $\|v-v'\|_P = 2$, and $v-v' \notin V_P$. By definition of $V_0$ and since $v \neq v'$, the coordinates of $u-u'$ must take two different values. Two cases remain: if $u-u'$ contains only 0's and 1's, $u-u' \in V_0$ and $v-v' \in V_P$; and if it contains only 0's and -1's, then we can write $u-u' = w-(1, \dots, 1)$, with $w \in V_0$, so that $v-v' \in V_P$ as well.

To conclude, we find that $v - v' \in V_P$ if and only if $I \subset I'$ or $I' \subset I$.

□

**Lemma 12.** For every clique C of $\tilde{G}$,

$$ \delta^0(C) \leq \frac{1}{2^n}. $$

*Proof.* Let $\{0, \frac{p_H(u_1)}{2}, \dots, \frac{p_H(u_s)}{2}\}$ be a clique. By symmetry, we may assume that

$$ u_i = \underbrace{(1, \dots, 1, 0, \dots, 0)}_{w_i}, $$

where $w_i = |I_i|$. We want to count the vertices in

$$ N[C] = \frac{1}{2} (\{0, p_H(u_1), \dots, p_H(u_s)\} + V_P). $$

Since $0 \in C$, the set $(\{0, p_H(u_1), \dots, p_H(u_s)\} + V_P)$ must contain all the images of $V_0 \cup \{0\}$ by $p_H$: there are $2^{n+1} - 1$ such vertices. We count, for each $i = 1, \dots, s$, how many new neighbors are provided by $p_H(u_i) + V_P$. We find that

* The vector

$$ u_1 = \underbrace{(1, \dots, 1, 0, \dots, 0)}_{w_1}, $$

provides $(2^{w_1} - 1)(2^{n+1-w_1} - 1)$ new neighbors.

* The vector

$$ u_2 = \underbrace{(1, \dots, 1, 1, \dots, 1)}_{w_1} \underbrace{1, \dots, 1, 0, \dots, 0}_{w_2-w_1}, $$

provides $2^{w_1}(2^{w_2-w_1} - 1)(2^{n+1-w_2} - 1)$ new neighbors.

* For any $2 \leq i \leq s$, the vector $u_i$ will provide $2^{w_{i-1}}(2^{w_i-w_{i-1}} - 1)(2^{n+1-w_i} - 1)$ new neighbors.

By summing all the values, if we set $w_0 = 0$, we get:

$$ \begin{aligned} |N[C]| &= 2^{n+1} - 1 + \sum_{i=1}^{s} 2^{w_{i-1}}(2^{w_i-w_{i-1}} - 1)(2^{n+1-w_i} - 1) \\ &= (s+1)2^{n+1} - \left(\sum_{i=1}^{s} 2^{n+1-(w_i-w_{i-1})} + 2^{w_s}\right). \end{aligned} $$

Since $w_s \leq n$ and for every $i$, $(w_i - w_{i-1}) \geq 1$, we have

$$ 2^{w_s} + \sum_{i=1}^{s} 2^{n+1-(w_i-w_{i-1})} \leq (s+1)2^n, $$

and this implies

$$ |N[C]| \geq (s+1)2^{n+1} - (s+1)2^n = (s+1)2^n. $$
Finally, the local density of C satisfies:

$$ \delta^0(C) = \frac{|C|}{|N[C]|} = \frac{s+1}{|N[C]|} \le \frac{1}{2^n}, $$

and we may note that this bound is sharp if and only if $w_s = n$ and for every $i, w_i - w_{i-1} = 1$, that is when C is a maximal clique of the form

$$ \{0, (1, 0, \dots, 0), (1, 1, 0, \dots, 0), \dots, (1, \dots, 1, 0, 0), (1, \dots, 1, 0)\}. $$

□

Now we can conclude the proof of Theorem 4:

*Proof of Theorem 4.* Following Lemma 12 and Lemma 4, $\bar{\alpha}(G_P) \le \frac{1}{2^n}$, which leads to the theorem, following Lemma 2. □

4.2. **The lattice $D_n$, $n \ge 4$.** We apply the same method as for $A_n$ to another classical family of lattices. For $n \ge 4$, the lattice $D_n$ is defined by

$$ D_n = \{x = (x_1, \dots, x_n) \in \mathbb{Z}^n \mid \sum_{i=0}^{n} x_i = 0 \quad \mod 2\}. $$

The same construction provides again a graph that satisfies (Property D). Unfortunately, the analysis of the neighborhoods of the cliques does not lead to the wanted $\frac{1}{2^n}$ upper bound. Nevertheless, we can prove:

**Theorem 5.** For every dimension $n \ge 4$, if $\mathcal{P}$ is the Voronoï region of the lattice $D_n$, then

$$ m_1(\mathbb{R}^n, \| \cdot \|_{\mathcal{P}}) \le \frac{1}{(3/4)2^n + n - 1}. $$

Let us describe the Voronoï region of $D_n$. Again we refer to [2] for further details. Let $S$ be the simplex whose vertices are $0, (0, \dots, 0, 1), (\frac{1}{2}, \dots, \frac{1}{2})$, and the vectors $\left( \underbrace{0, \dots, 0}_{i}, \frac{1}{2}, \dots, \frac{1}{2} \right)$, for $2 \le i \le n-2$. Then the Voronoï region $\mathcal{P}$ of $D_n$ is the union of the images of $S$ by the group generated by all permutations of the coordinates and sign changes of evenly many coordinates. Note that some of the vertices of $S$ are not extreme points of $\mathcal{P}$ anymore. Actually, there are two types of vertices of $\mathcal{P}$:

$$ \left\{ \begin{array}{ll} 2n \text{ vectors of the form } (\pm 1, 0, \dots, 0) & \text{(type 1),} \\ 2^n \text{ vectors of the form } (\pm \frac{1}{2}, \dots, \pm \frac{1}{2}) & \text{(type 2).} \end{array} \right. $$

The non zero vectors of $S$ are contained in the hyperplane of $\mathbb{R}^n$ defined by the equation $x_{n-1} + x_n = 1$. The faces of $\mathcal{P}$ are supported by the images of this hyperplane under the action of the group i.e. the hyperplanes defined by the equations of the form $\pm x_i \pm x_j = 1$, with $i \ne j$. Thus,

$$ \left\{ \begin{array}{ll} x \in \mathcal{P} & \text{if and only if for all } i \ne j, |x_i| + |x_j| \le 1 \\ x \in \partial \mathcal{P} & \text{if and only if } \max_{i \ne j} (|x_i| + |x_j|) = 1, \end{array} \right. $$

and the norm $\|x\|_{\mathcal{P}}$ of a vector $x \in \mathbb{R}^n$ is

$$ \|x\|_{\mathcal{P}} = \max_{i \ne j} (|x_i| + |x_j|). $$

As in the case of $A_n$, the vertices of $\mathcal{P}$ span the dual lattice of $D_n$:

**Lemma 13.** The vertices of $\mathcal{P}$ span over $\mathbb{Z}$ the dual lattice $D_n^\#$.
*Proof.* It is immediate to check that for every $x \in D_n$ and $v \in V_P$, $\langle x, v \rangle \in \mathbb{Z}$, so $\text{span}_Z(V_P) \subset D_n^\#$. The converse follows directly from the following decomposition of $D_n^\#$:

$$D_n^\# = D_n \cup \left( \left( \frac{1}{2}, \dots, \frac{1}{2} \right) + D_n \right) \cup \left( \left( \frac{1}{2}, \dots, -\frac{1}{2} \right) + D_n \right) \cup \left( (0, \dots, 0, 1) + D_n \right).$$

□

Once again, let $G_P$ be the subgraph of $G(\mathbb{R}^n, \| \cdot \|_P)$ induced by $V = \frac{1}{2}D_n^\#$, and let $\tilde{G}$ be the auxiliary graph which is the Cayley graph on $V$ associated with the generating set $\frac{1}{2}V_P$. It also satisfies (Property D):

**Lemma 14.** The graph $\tilde{G}$ satisfies (Property D).

*Proof.* We follow the proof of Lemma 10. Let $v, v' \in V_P$. We distinguish three cases depending on the type of $v$ and $v'$:

* If both $v$ and $v'$ are of type 1, $v + v'$ is either 0, or, up to permutation of the coordinates, of the form $(\pm 2, 0, \dots, 0)$ or $(\pm 1, \pm 1, 0, \dots, 0)$, and $\|v + v'\|_P = 2$.

* If both $v$ and $v'$ are of type 2, the non zero coordinates of $v + v'$ are 1 or $-1$. If $v + v' \neq 0$, then either it is a vertex of $V_P$ of type 1, or it has at least two coordinates whose absolute values are equal to 1, and so $\|v + v'\|_P = 2$.

* If $v$ is of type 1 and $v'$ is of type 2, then $v + v'$ is either a vertex of $V_P$ of type 2, or, up to a permutation of coordinates, of the form $(\pm \frac{3}{2}, \pm \frac{1}{2}, \dots, \pm \frac{1}{2})$, and $\|v + v'\|_P = 2$.

□

It remains to analyze the neighborhoods of the cliques of $\tilde{G}$. We first determine the possible cliques of $\tilde{G}$. We may assume that they contain 0.

**Lemma 15.** Up to symmetry, a clique of $\tilde{G}$ containing 0 must be a subset of the maximal clique

$$C_{\max} = \left\{ 0, \frac{v_1}{2}, \frac{v_2}{2}, \frac{v_3}{2} \right\} \text{ where } \begin{cases} v_1 = (0, \dots, 0, 1) \\ v_2 = (\frac{1}{2}, \frac{1}{2}, \dots, \frac{1}{2}) \\ v_3 = (-\frac{1}{2}, \frac{1}{2}, \dots, \frac{1}{2}) \end{cases}.$$

*Proof.* Let $v, v' \in V_P$ such that $\frac{v-v'}{2} \in \frac{1}{2}V_P$. The conclusion follows from the following facts:

* Both $v$ and $v'$ can not be of type 1, because the difference of two such vectors, is either 0 or has polytope norm 2.

* If $v$ and $v'$ are both of type 2, then $v$ and $v'$ must differ by only one coordinate, otherwise $\|v - v'\|_P = 2$.

* If $v$ is of type 1, say $v = (0, \dots, 0, \underbrace{\pm 1}_{i}, 0, \dots, 0)$, if $v'$ is of type 2 and $\frac{v-v'}{2} \in \frac{1}{2}V_P$, then the $i$th coordinate of $v'$ must have the same sign as the $i$th coordinate of $v$.

□

Then, we analyze the local density of the cliques:
**Lemma 16.** For every clique of $\tilde{G}$,

$$ \delta^0(C) \le \frac{1}{(3/4)2^n + n - 1}. $$

*Proof.* By enumerating the neighbors of every element in $C_{max}$ and by counting the intersections of the different neighborhoods, we find that:

* If $C = \{0\}$, $\delta^0(C) = \frac{1}{1+2^n+n}$.

* If $C = \{0, \frac{v_1}{2}\}$,

$$ \delta^0(C) = \frac{2}{2^n + 2^{n-1} + 4n} = \frac{1}{(3/4)2^n + 2n}. $$

Note that for $n \ge 6$, this density is already greater than $\frac{1}{2^n}$.

* If $C$ is one of the two symmetric cliques $\{0, \frac{v_2}{2}\}$ and $\{0, \frac{v_3}{2}\}$,

$$ \delta^0(C) = \frac{2}{2 \times 2^n + 2n} = \frac{1}{2^n + n}. $$

* By symmetry, the cliques of the form $\{0, \frac{v_i}{2}, \frac{v_j}{2}\}$ have the same number of neighbors. If $C$ is one of them,

$$ \delta^0(C) = \frac{3}{2 \times 2^n + 2^{n-1} + 3n - 1} = \frac{1}{(5/6)2^n + n - 1/3}, $$

which is also greater than $\frac{1}{2^n}$.

* Finally,

$$ \delta^0(C_{max}) = \frac{4}{3 \times 2^n + 4n - 4} = \frac{1}{(3/4)2^n + n - 1}, $$

which is the highest possible value of $\delta^0(C)$.

□

## 5. THE CHROMATIC NUMBER OF $G(\mathbb{R}^n, \| \cdot \|_P)$

In this section, we discuss the chromatic number $\chi(\mathbb{R}^n, \| \cdot \|_P)$ of the unit distance graph associated with a paralleohedron. We start with the construction of a natural coloring of $\mathbb{R}^n$ with $2^n$ colors, leading to:

**Proposition 3.** Let $\mathcal{P}$ be a paralleohedron in $\mathbb{R}^n$. Then

$$ \chi(\mathbb{R}^n, \| \cdot \|_P) \le 2^n. $$

*Proof.* By assumption, there is a lattice $\Lambda$ such that $\mathbb{R}^n$ is the disjoint union $\cup_{\lambda \in \Lambda}(\lambda + \mathcal{P})$. We may also write $\mathbb{R}^n$ as the disjoint union

$$ \mathbb{R}^n = \bigcup_{\lambda \in \frac{1}{2}\Lambda} \left(\lambda + \frac{1}{2}\mathcal{P}\right) = \bigcup_{\lambda \in \frac{1}{2}\Lambda} B_{\mathcal{P}}\left(\lambda, \frac{1}{2}\right). $$

If $H$ is a coset of $\frac{1}{2}\Lambda/\Lambda$, then

$$ A_H = \bigcup_{\lambda \in H} B_{\mathcal{P}}\left(\lambda, \frac{1}{2}\right) $$

is a set avoiding distance 1. So the points in $A_H$ can receive the same color. This concludes the proof, since $\mathbb{R}^n$ is the disjoint union of all $A_H$ where $H$ runs through the $2^n$ cosets. □
<figure><img src="image_14.png" /><figcaption>FIGURE 13. $\chi(\mathbb{R}^n, \|\cdot\|_P) \le 2^n$.</figcaption></figure>

In order to lower bound $\chi(\mathbb{R}^n, \|\cdot\|_P)$, we can take advantage of the induced subgraphs that we have constructed in previous sections. In particular, whenever we have a discrete induced subgraph $G_P$ of $G(\mathbb{R}^n, \|\cdot\|_P)$ satisfying $\bar{\alpha}(G_P) = \frac{1}{2^n}$, we obtain as an immediate consequence that

$$\chi(\mathbb{R}^n, \|\cdot\|_P) \ge \chi(G_P) \ge \frac{1}{\bar{\alpha}(G_P)} = 2^n.$$

Thus we have proved:

**Corollary 1.** Let $\mathcal{P}$ be a parallelohedron in $\mathbb{R}^2$. Then

$$\chi(\mathbb{R}^2, \|\cdot\|_P) = 4.$$

**Corollary 2.** Let $\mathcal{P}$ be the Voronoi region of the lattice $A_n$ in $\mathbb{R}^n$. Then

$$\chi(\mathbb{R}^n, \|\cdot\|_P) = 2^n.$$

**Remark 3.** We want to point out the fact that in dimension 2, one can find a finite induced subgraph of $G(\mathbb{R}^n, \|\cdot\|_P)$ with chromatic number 4. Indeed, the induced subgraph of $G(\mathbb{R}^n, \|\cdot\|_P)$ whose vertices and edges are drawn in Figure 14 is easily seen to have chromatic number 4.

<figure><img src="image_15.png" /><figcaption>FIGURE 14. $\chi(\mathbb{R}^2, \|\cdot\|_P) \ge 4$.</figcaption></figure>

## APPENDIX A. THE PROOF OF LEMMA 1

This appendix is dedicated to the proof of Lemma 1, which gives two equivalent formulations of the independence ratio of a discrete graph whose vertices have finite degrees. The importance of the assumption on the degrees of the vertices will be discussed after the proof. The statement of the lemma is reproduced below:
**Lemma 1.** Let $G = (V, E)$ be a graph such that its vertex set $V$ is a discrete subset of $\mathbb{R}^n$, and such that every vertex has finite degree. Then

$$ \bar{\alpha}(G) = \limsup_{R \to \infty} \bar{\alpha}(G_R), $$

where $G_R$ is the finite induced subgraph of $G$ whose set of vertices is $V_R = V \cap [-R, R]^n$.

*Proof.* Let $G$ be a graph satisfying the assumptions of the lemma. First of all, we remark that if $G$ is finite, there exists $R$ such that $G_R = G$. Thus, $\bar{\alpha}(G) = \limsup_{R \to \infty} \bar{\alpha}(G_R)$ is obvious. From now on, we will assume that $G$ has infinitely many vertices.

The inequality $\bar{\alpha}(G) \le \limsup_{R \to \infty} \bar{\alpha}(G_R)$ clearly holds. Indeed, if $A$ is an independent set of $G$, then $A \cap V_R$ is an independent set of $G_R$ and so $\frac{|A \cap V_R|}{|V_R|} \le \bar{\alpha}(G_R)$, leading to $\delta_G(A) \le \limsup_{R \to \infty} \bar{\alpha}(G_R)$.

We will prove the reverse inequality by exhibiting a sequence of independent sets $S_k$ such that, for all $k \ge 1$, $\limsup_{R \to \infty} \frac{|S_k \cap V_R|}{|V_R|} \ge \limsup_{R \to \infty} \bar{\alpha}(G_R) - \frac{1}{k}$.

Let $r_\ell$ be a strictly increasing sequence of real numbers tending to infinity and such that $\lim_{\ell \to \infty} \bar{\alpha}(G_{r_\ell}) = \limsup_{R \to \infty} \bar{\alpha}(G_R)$, and let $A_{r_\ell}$ be an independent subset of $V_{r_\ell}$ of maximal cardinality. The set $S_k$ will be constructed from the sequence of independent sets $A_{r_\ell}$; however, we will need, for reasons that will appear more clearly later, that the successive rings $V_{r_\ell} \setminus V_{r_{\ell-1}}$ are sufficiently large. In view of that, we construct a convenient subsequence of $r_\ell$, with the help of a function $\varphi(\ell)$, in the following way.

Since the graph $G$ is discrete, we know that for all $R$, $V_R$ is finite and since all the vertices of the graph are of finite degree, we know that the neighborhood $N[V_R]$ is finite too. We call $b(R)$ the smallest real number such that $N[V_R] \subset V_{b(R)}$. Then, we set $\varphi(0) = 0$ and, inductively for $\ell \ge 0$,

$$ \varphi(\ell + 1) = \min \{i \mid r_i \ge b(r_{\varphi(\ell)}) \text{ and } |V_{r_i} \setminus V_{r_{\varphi(\ell)}}| \ge |V_{r_{\varphi(\ell)}} \setminus V_{r_{\varphi(\ell-1)}}|\}. $$

The existence of $\varphi(\ell+1)$ at each step of the recursion holds because $\lim_{\ell \to \infty} r_\ell = +\infty$ and $V_{r_{\varphi(\ell)}} \setminus V_{r_{\varphi(\ell-1)}}$ is finite (since $G$ is discrete). To keep the notations simple, we set $R_\ell = r_{\varphi(\ell)}$.

We will need the following property of the number of elements of the rings associated to the sequence $R_\ell$:

**Proposition 4.** For all $\ell \in \mathbb{N}$, for all $m \in \mathbb{N}^*$:

$$ |V_{R_{\ell+1}} \setminus V_{R_{\ell}}| \le \frac{1}{m} |V_{R_{\ell+m}} \setminus V_{R_{\ell}}| $$

*Proof.* We have $|V_{R_{\ell+m}} \setminus V_{R_{\ell}}| = \sum_{k=0}^{m-1} |V_{R_{\ell+k+1}} \setminus V_{R_{\ell+k}}|$ and each term of the sum is larger than $|V_{R_{\ell+1}} \setminus V_{R_{\ell}}|$, by definition of $\varphi$. $\square$

Now we are ready to define the sets $S_k$. We set, for $k \ge 0$,

$$ S_k := \{v \in V \mid \exists i \in \mathbb{N} \text{ such that } v \in A_{R_{ik}} \text{ and } \forall j < i, v \notin N[A_{R_{jk}}]\}. $$

It remains to prove that $S_k$ is an independent set and satisfies the inequality $\limsup_{R \to \infty} \bar{\alpha}(G_R) - \frac{1}{k} \ge \limsup_{R \to \infty} \bar{\alpha}(G_R)$.

**Proposition 5.** $S_k$ is independent.
**Proof.** Let $v_1$ and $v_2$ be two vertices of $S_k$ and let $i_1$ and $i_2$ be such that $v_1 \in A_{R_{i_1 k}}$, $v_2 \in A_{R_{i_2 k}}$ and for all $j < i_1$ (respectively $i_2$), $v_1$ (resp. $v_2 \notin N[A_{R_{j n}}]$). If $i_1 = i_2$, then $v_1$ and $v_2$ both belong to $A_{R_{i_1 k}}$ which is independent, consequently they are not connected. If say, $i_1 > i_2$, from the very definition of $S_k$, $v_2 \notin N[A_{R_{i_1 k}}]$, so $v_1$ and $v_2$ are not connected either. □

**Lemma 17.** For all $k \ge 1$, $i \ge 0$, $\frac{|S_k \cap V_{R_{ik}}|}{|V_{R_{ik}}|} \ge \frac{|A_{R_{ik}}|}{|V_{R_{ik}}|} - \frac{1}{k}$.

*Proof.* We prove the lemma by induction on $i$:

* The property holds for $i = 0$ since $S_k \cap V_{R_0}$ contains $A_{R_0}$.

* Let $i \in \mathbb{N}$ be such that the property holds. We have:

$$ (2) \qquad \frac{|S_k \cap V_{R_{(i+1)k}}|}{|V_{R_{(i+1)k}}|} = \frac{|S_k \cap V_{R_{ik}}|}{|V_{R_{(i+1)k}}|} + \frac{|S_k \cap (V_{R_{(i+1)k}} \setminus V_{R_{ik}})|}{|V_{R_{(i+1)k}}|}. $$

Let us lower bound the two terms of this sum one after the other.

► Since $A_{R_{ik}}$ is an independent set of maximal cardinality in $V_{R_{ik}}$, we know that $|A_{R_{ik}}| \ge |A_{R_{(i+1)k}} \cap V_{R_{ik}}|$. Combining with the induction hypothesis, we find

$$ \frac{|S_k \cap V_{R_{ik}}|}{|V_{R_{ik}}|} \ge \frac{|A_{R_{(i+1)k}} \cap V_{R_{ik}}|}{|V_{R_{ik}}|} - \frac{1}{k} $$

and thus:

$$ (3) \qquad \frac{|S_k \cap V_{R_{ik}}|}{|V_{R_{(i+1)k}}|} \ge \frac{|A_{R_{(i+1)k}} \cap V_{R_{ik}}|}{|V_{R_{(i+1)k}}|} - \frac{1}{k} \frac{|V_{R_{ik}}|}{|V_{R_{(i+1)k}}|}. $$

► By definition, $S_k$ contains all the vertices of $A_{R_{(i+1)k}}$ except those who are in the neighborhood of an $A_{R_{jk}}$ with $j < i + 1$. Since for all $j < i$, $N[A_{R_{jk}}] \subset V_{b(R_{ik})}$, the set $S_k \cap (V_{R_{(i+1)k}} \setminus V_{R_{ik}})$ contains $A_{R_{(i+1)k}} \setminus V_{b(R_{ik})}$. We also have by construction that $b(R_{ik}) \le R_{ik+1}$. Thus,

$$ |V_{b(R_{ik})} \setminus V_{R_{ik}}| \le |V_{R_{ik+1}} \setminus V_{R_{ik}}| \le \frac{1}{k} |V_{R_{(i+1)k}} \setminus V_{R_{ik}}| $$

where the second inequality follows from Proposition 4.

This leads to the following inequality:

$$ (4) \qquad \frac{|S_k \cap (V_{R_{(i+1)k}} \setminus V_{R_{ik}})|}{|V_{R_{(i+1)k}}|} \ge \frac{|A_{R_{(i+1)k}} \setminus V_{R_{ik}}|}{|V_{R_{(i+1)k}}|} - \frac{1}{k} \frac{|V_{R_{(i+1)k}} \setminus V_{R_{ik}}|}{|V_{R_{(i+1)k}}|} $$

By combining equations (2), (3) and (4), we find:

$$ \frac{|S_k \cap V_{R_{(i+1)k}}|}{|V_{R_{(i+1)k}}|} \ge \frac{|A_{R_{(i+1)k}}|}{|V_{R_{(i+1)k}}|} - \frac{1}{k} $$

which concludes the proof of Lemma 17. □

Now we are ready to conclude the proof of Lemma 1. Indeed, for all $k \ge 1$, we have
$$
\begin{align*}
\bar{\alpha}(G) &= \sup_S \limsup_{R \to +\infty} \frac{|S \cap V_R|}{|V_R|} &\ge& \limsup_{R \to +\infty} \frac{|S_n \cap V_R|}{|V_R|} \\
&\ge& \lim_{i \to \infty} \frac{|S_k \cap V_{R_{ik}}|}{|V_{R_{ik}}|} \\
&\ge& \lim_{i \to \infty} \frac{|A_{R_{ik}}|}{|V_{R_{ik}}|} - \frac{1}{k} \\
&\ge& \limsup_{R \to \infty} \bar{\alpha}(G_R) - \frac{1}{k}.
\end{align*}
$$

In the limit when $k \to \infty$, we obtain that $\bar{\alpha}(G) \ge \limsup_{R \to \infty} \bar{\alpha}(G_R)$. $\square$

To conclude our discussion of Lemma 1, we would like to point out that the inequality
$\bar{\alpha}(G) \le \limsup_{R \to \infty} \bar{\alpha}(G_R)$ does not necessarily hold if $G$ has vertices with infinite
degree, by bringing out a counterexample.

Let $G$ be the graph given by $V = \mathbb{Z}$ and $E = \{(a, b) | a < 0 \text{ and } b > -2a\}$.

Let $N \in \mathbb{N}$ and let $S_N = [-N, -\frac{N}{2}] \cup [0, N]$. One can see easily that $S_N$ is independent in $G$. Hence, $\limsup_{R \to \infty} \bar{\alpha}(G_R) \ge \lim_{N \to \infty} \frac{|S_N|}{|V_N|} = \frac{3}{4}$.

Let $S$ be an independent set of $G$. If $S$ contains a vertex indexed by a negative integer $-k$, it cannot contain any vertex indexed by $i > 2k$ and can therefore only contain finitely many vertices indexed by positive integers. Hence, $\lim_{N \to \infty} \frac{|S \cap V_N|}{|V_N|} \le \frac{1}{2}$. If $S$ does not contain any vertex indexed by a negative integer, the inequality $\lim_{N \to \infty} \frac{|A \cap V_N|}{|V_N|} \le \frac{1}{2}$ holds as well. Thus,

$$
\sup_S \limsup_{N \to +\infty} \frac{|S \cap V_N|}{|V_N|} \le \frac{1}{2}
$$

which proves that $\bar{\alpha}(G) \neq \limsup_{R \to \infty} \bar{\alpha}(G_R)$.

ACKNOWLEDGEMENTS

We would like to thank Sinai Robins for suggesting the polytopal norms as an alternative
to the standard Euclidean norm in the study of 1-avoiding sets, and for helpful discussions
on this subject.

REFERENCES

[1] Christine Bachoc, Alberto Passuello, and Alain Thiery. The density of sets avoiding distance 1 in Euclidean space. *Discrete Comput. Geom.*, 53(4):783–808, 2015.

[2] J. H. Conway and N. J. A. Sloane. *Sphere-packings, Lattices, and Groups*. Springer-Verlag New York, Inc., New York, NY, USA, 1987.

[3] H. T. Croft. Incidence incidents. *Eureka (Cambridge)*, 30:22–26, 1967.

[4] B. Delaunay. Sur la partition régulière de l'espace à 4 dimensions. I, II. *Bull. Acad. Sci. URSS*, 2:79-110, 1929.

[5] R. M. Erdahl. Zonotopes, dicings, and Voronoi's conjecture on parallelohedra. *European J. Combin.*, 20(6):527–549, 1999.

[6] K. J. Falconer. The realization of distances in measurable subsets covering rn. *Journal of Combinatorial Theory, Series A*, 31(2):184 – 189, 1981.

[7] Tamás Keleti, Máté Matolcsi, Fernando Mário de Oliveira Filho, and Imre Z. Rúzsa. Better bounds for planar sets avoiding unit distances. *Discrete Comput. Geom.*, 55(3):642–661, 2016.

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

[9] P. McMullen. Convex bodies which tile space by translation. *Mathematika*, 27(1):113–121, 1980.
[10] Hermann Minkowski. Allgemeine lehrsätze über die convexen polyeder. *Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse*, 1897:198–220, 1897.

[11] Dmitry Shiryaev. Personal communication.

[12] Alexander Soifer. *The mathematical coloring book: Mathematics of coloring and the colorful life of its creators*. Springer Science & Business Media, 2008.

[13] L. A. Székely. Erdős on unit distances and the Szemerédi-Trotter theorems. In *Paul Erdős and his mathematics, II (Budapest, 1999)*, volume 11 of *Bolyai Soc. Math. Stud.*, pages 649–666. János Bolyai Math. Soc., Budapest, 2002.

[14] B. A. Venkov. On a class of Euclidean polyhedra. *Vestnik Leningrad. Univ. Ser. Mat. Fiz. Him.*, 9(2):11–31, 1954.

[15] Georges Voronoi. Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs. *J. Reine Angew. Math.*, 134:198–287, 1908.

CHRISTINE BACHOC, INSTITUT DE MATHÉMATIQUES DE BORDEAUX, UMR 5251, UNIVERSITÉ DE BORDEAUX, 351 COURS DE LA LIBÉRATION, 33400 TALENCE, FRANCE.

*E-mail address:* christine.bachoc@u-bordeaux.fr

THOMAS BELLITTO, LABRI, UNIVERSITÉ DE BORDEAUX, 351 COURS DE LA LIBÉRATION, 33400 TALENCE, FRANCE.

*E-mail address:* thomas.bellitto@u-bordeaux.fr

PHILIPPE MOUSTROU, INSTITUT DE MATHÉMATIQUES DE BORDEAUX, UMR 5251, UNIVERSITÉ DE BORDEAUX, 351 COURS DE LA LIBÉRATION, 33400 TALENCE, FRANCE.

*E-mail address:* philippe.moustrou@u-bordeaux.fr

ARNAUD PÊCHER, LABRI, UNIVERSITÉ DE BORDEAUX, 351 COURS DE LA LIBÉRATION, 33400 TALENCE, FRANCE.

*E-mail address:* arnaud.pecher@u-bordeaux.fr