On the Existence of Complete Coverings of Lee Spheres

Overview & Synopsis

Every perfect $r$-error-correcting Lee code in $\mathbb{Z}^n$ induces a finite configuration around each codeword: a family of pairwise disjoint radius-$r$ Lee spheres, all disjoint from the central sphere, that covers every lattice point at Lee distance $r+1$ from the codeword. We call such a configuration a complete covering. Under projection onto a suitable Cartesian product of cycles, a complete covering corresponds to an optimal local structure in the sense of Špacapan. The existence of a complete covering is necessary but, in general, not sufficient for the existence of a perfect Lee code, as our construction for $(n,r)=(3,2)$ shows. We prove that no complete covering exists whenever $n\ge 8$ and $r^2+\lfloor 25r/34\rfloor-3\ge 2n$. For the corresponding Cartesian products of cycles, this strengthens Špacapan's nonexistence theorem by replacing the linear radius condition $r\ge n$ with a threshold of order $\sqrt{2n}$. We also obtain an improved large-radius nonexistence bound for perfect Lee codes, strengthening the bound of Horak and Kim. Furthermore, we show that, for every $\varepsilon>0$, no complete covering exists when $n\ge 3$, $r$ is sufficiently large, and $r^2+(2/\mathrm{e}-\varepsilon)r\ge 2n$. On the positive side, we use near-optimal ternary constant-weight codes to construct almost complete coverings whose pairwise disjoint shadows cover a $1-o(1)$ proportion of the first outer Lee shell as the dimension tends to infinity, for every fixed radius.