3
$\begingroup$

Which high-dimensional lattices (particularly $Z_n^*,D_n,D_n^*,A_n,A_n^*$), exhibit the following property shown in the attached diagram? Two 2D lattices are shown, with the lattice points in red, the Voronoi cells in black, and the origin cell in blue. The cells closest to the origin cell are shown in green. Shown in purple is a point that belongs to the origin cell, and is displaced a small distance to a different cell.

In the hexagonal lattice, we see that such a small displacement will only transport the purple dot to one of the closest neighboring cells (green). But in the cubic lattice, a small displacement can move the purple dot to a Voronoi cell which is not one of the closest neighbors. Which other high-dimensional lattices share this property with the cubic lattice? I have consulted Conway and Sloan's book, but this question did not appear to be addressed. If anyone knows the answer or can point me to helpful references, I'd really appreciate it.

Left: 2D hexagonal lattice. Right: 2D cubic latice

$\endgroup$
5
$\begingroup$

I always consider Voronoi cells of lattices as closed sets. Write $V(v)$ for the Voronoi cell around a lattice point $v$.

I assume that by two neighboring Voronoi cells you mean two Voronoi cells that share a common ($n-1$-dimensional) face.

So let me rephrase your question as follows:

Characterize the $n$-dimensional lattices $L$ with the following property:

(*) If two different Voronoi cells of $L$ share a common point, then they also share a common face.

$ $

The answer to this question is well known:

The lattices $L$ with property (*) are precisely the lattices where each coset $v + 2L$ with $v \in L \setminus 2L$ contains exactly two shortest vectors.

$ $

I am not aware of any published proof of this, so I'll sketch a proof here.

Lemma 1

$V(0)$ and $V(v)$ have a common point if and only if $v$ is a shortest vector in the coset $v + 2L$.

Proof

$V(0)$ is the intersection of all half spaces $\{x \in \mathbb{R}^n: \forall v \in L \setminus \{0\} \mid \left<x,v \right> \leq \left< v,v \right>/2\}$.

Assume $|w| < |v|$ for a $w \in v + 2L$. Put $t = (v+w)/2, u = (v-w)/2$. Since $t, u \in L$, we have $\left<x,v\right> = \left<x,t\right> + \left<x,u\right> \leq \left<t,t\right>/2 + \left<u,u\right>/2 \leq \left<v,v\right>/4 + \left<w,w\right>/4 < \left<v,v\right>/2$ for all $x \in V(0)$. Since $V(0)$ is symmetric, we also have $|\left<x,v\right>| < \left<v,v\right> / 2$. Since $V(v)$ is obtained from $V(0)$ by translation by $v$, we have $V(0) \cap V(v) = \emptyset$ if such a $w$ exists.

Assume $v/2 \not\in V(0) \cap V(v)$. Then there is a $w \in L$ with $|v/2 -w| < |v/2|$ and hence $|v -2w| < |v|$.

q.e.d.

$ $

By [1], Ch. 21, Theorem 10, $V(v)$ shares a face with $V(0)$ iff the coset $v + 2L$ contains exactly two shortest vectors. Together with Lemma 1 this characterizes the lattices with property (*).

$ $

[1] Conway and Sloane, Sphere Packings, Lattices and Groups, 3rd ed. (1998)

$\endgroup$
2
  • $\begingroup$ Thank you for the thoughtful answer. Do you know some lattices in particular (eg. $D_n, A_n$...) satisfy this property? $\endgroup$ Sep 19 '17 at 19:28
  • $\begingroup$ @user3433489 You just have to count the faces of the Voronoi cell around 0. The lattice has property $(*)$ iff there are $2^{n+1}-2$ of them. According to [1], Ch. 21, Corollary after Theorem 5, these faces are in 1:1 correspondence with the roots of a lattice for a root lattice $A_n$, $D_n$ or $E_n$. Counting roots you see that $A_2$ is the only of these lattices with property $(*)$. $\endgroup$ Sep 24 '17 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.