On the non-existence of linear perfect Lee codes: The Zhang-Ge condition and a new polynomial criterion

Abstract

The Golomb-Welch conjecture (1968) states that there are no $e$-perfect Lee codes in ${\mathbb{Z}}^n$ for $n\ge 3$ and $e\ge 2$. This conjecture remains open even for linear codes. A recent result of Zhang and Ge establishes the non-existence of linear $e$-perfect Lee codes in ${\mathbb{Z}}^n$ for infinitely many dimensions $n$, for $e=3$ and $4$. In this paper we extend this result in two ways. First, using the non-existence criterion of Zhang and Ge together with a generalized version of Lucas' theorem we extend the above result for almost all $e$ (i.e. a subset of positive integers with density $1$). Namely, if $e$ contains a digit $1$ in its base-$3$ representation which is not in the unit place (e.g. $e=3,4$) there are no linear $e$-perfect Lee codes in ${\mathbb{Z}}^n$ for infinitely many dimensions $n$. Next, based on a family of polynomials (the $Q$-polynomials), we present a new criterion for the non-existence of certain lattice tilings. This criterion depends on a prime $p$ and a tile $B$. For $p=3$ and $B$ being a Lee ball we recover the criterion of Zhang and Ge.