Limits found for perfect error correction shapes in high dimensions
On the Existence of Complete Coverings of Lee Spheres
Information Theory
Summary
Perfect error-correcting codes help detect and fix mistakes in data, using special shapes called Lee spheres to represent error limits. The authors study a complex pattern called complete coverings that must exist for perfect Lee codes to work, showing that many such coverings cannot exist in higher dimensions or with larger error limits. They also provide cases where nearly complete coverings are nearly perfect for large dimensions. This helps clarify when perfect Lee error-correcting codes can or cannot exist.
What this means in practice
- •For coding engineers: Avoid search for certain perfect Lee error-correcting codes in high-dimensional data due to proven nonexistence conditions.
- •For digital communication system designers: Use refined bounds on error-correcting code structures to guide design of robust communication protocols with Lee metric constraints.
A theory result. No direct application yet.
Authors
Jing Zhang, Yue Zhou
Abstract
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.