No lattice tilings by Lee balls in three or more dimensions
The Golomb--Welch conjecture for lattice tilings
Information Theory
Summary
This paper shows that when you try to cover an infinite grid in three or more dimensions using copies of a certain shape called a Lee ball, you can’t do it perfectly with a repeating pattern if the ball’s radius is bigger than one. The authors proved this was impossible for all such cases, completing the understanding of when perfect lattice coverings by these shapes exist. This also tells us something about certain kinds of networks formed from mathematical groups, limiting how large these networks can get when they have given properties.
What this means in practice
- •For network designers: Design network topologies with known limits on size and topology for given node degree and diameter constraints based on the paper's proof.
- •For coding theory engineers: Understand limitations in constructing perfect codes related to Lee metric spaces informed by the proven nonexistence of certain lattice tilings.
A theory result. No direct application yet.
Authors
Bocong Chen, Jing Huang, Gaojun Luo
Abstract
We prove the Golomb--Welch conjecture for lattice tilings: for every $n\ge3$ and $r\ge2$, the integer lattice $\Z^n$ admits no lattice tiling by Lee balls $B_n(r)$ of radius $r$. Together with the classical constructions for $n\le2$ and for $r=1$, this determines all parameters for which a lattice Lee tiling exists. Equivalently, we show that every abelian Cayley graph of even degree $2n\ge6$ and diameter $r\ge2$ has strictly fewer than $|B_n(r)|$ vertices.