On the Lattice Tilings by Lee Balls: Q-Polynomials, Group-Ring Equations, and a Decision Algorithm

Source abstract

More than 50 years ago, Golomb and Welch conjectured that no tilings of $\mathbb{Z}^n$ by Lee balls of radius $r$ exist for $n \geq 3$ and $r \geq 2$. This conjecture remains open even under the additional assumption that the tiling is a lattice tiling. In general, there are two known effective approaches to the lattice case which are based on symmetric polynomials and on the arithmetic of group-ring equations, respectively. In this paper, we develop both approaches. First, we determine all coefficients of the Q-polynomials associated with Lee balls; previously, only leading coefficients and certain special cases were known. Second, for arbitrary radii, we give necessary and sufficient conditions for the existence of lattice tilings by Lee balls in terms of group-ring equations, extending earlier results for radii $r=2$ and $3$. We then derive new necessary conditions for such tilings. For every radius $3\le r\le 50$, we prove that the set of dimensions for which no lattice tiling exists has positive density in $\mathbb{Z}^+$. We also give an algorithm that combines the available necessary conditions and apply it to all pairs $(n,r)$ for which the corresponding Lee ball of radius $r$ and dimension $n$ has size less than $2^{30}$. Among these $1{,}358$ pairs, the combined method excludes $1{,}356$, leaving only $(n,r)=(35,3)$ and $(805,3)$.