Perfect Lee codes beyond dimension two
For integers $n \ge 1$ and $r \ge 0$ let $$B(n,r) = \Bigl\{z \in \mathbb Z^n : \sum_{j=1}^n |z_j| \le r\Bigr\}$$ be the Lee ball of radius $r$. A perfect Lee code of radius $r$ in $\mathbb Z^n$ is a set $C \subseteq \mathbb Z^n$ whose translates $c + B(n,r)$, $c \in C$, partition $\mathbb Z^n$: every lattice point is within Lee distance $r$ of exactly one codeword. Golomb and Welch constructed such codes in dimensions one and two for every radius, and of radius one in every dimension. They showed that there is none for $n = 3$, $r = 2$, and that for $n = 3$ and each $n \ge 5$ there is none for all sufficiently large $r$; Horak and Kim note that the argument extends to $n = 4$ and give explicit ranges. For $3 \le n \le 5$ there is none for any $r \ge 2$ (Gravier, Mollard and Payan for $n = 3$; Špacapan for $n = 4$; Horak for $3 \le n \le 5$), and Horak excluded $n = 6$, $r = 2$. Leung and Zhou proved that for $r = 2$ and every $n \ge 3$ no such $C$ is a lattice, and deduced that there is none at all for $r = 2$ when $2n^2 + 2n + 1$ is prime.
Problem. Is it true that for every $n \ge 3$ and every $r \ge 2$ there is no set $C \subseteq \mathbb Z^n$ with $$\mathbb Z^n = \bigsqcup_{c \in C} \bigl(c + B(n,r)\bigr)?$$ The set $C$ is arbitrary: no linearity, lattice or periodicity is assumed.
Source: Golomb and Welch (1970), Section 7, first proposed in 1968; this is the strong form of the Golomb–Welch conjecture, Horak and Kim (2018), Conjecture 3.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- IT, MG
- Keywords
- AIM Open Applied Problems, Lee metric, perfect codes, tilings
References
@article{golomb1970,
author = {Golomb, Solomon W. and Welch, Lloyd R.},
title = {Perfect codes in the {L}ee metric and the packing of polyominoes},
journal = {SIAM J. Appl. Math.},
volume = {18},
number = {2},
year = {1970},
pages = {302--317},
doi = {10.1137/0118025},
}
@article{horak2018,
author = {Horak, Peter and Kim, Dongryul},
title = {50 years of the {G}olomb--{W}elch conjecture},
journal = {IEEE Trans. Inform. Theory},
volume = {64},
number = {4},
year = {2018},
pages = {3048--3061},
doi = {10.1109/TIT.2017.2786675},
eprint = {1706.03589},
archivePrefix = {arXiv},
}
@article{gravier1998,
author = {Gravier, Sylvain and Mollard, Michel and Payan, Charles},
title = {On the non-existence of 3-dimensional tiling in the {L}ee metric},
journal = {European J. Combin.},
volume = {19},
number = {5},
year = {1998},
pages = {567--572},
doi = {10.1006/eujc.1998.0211},
}
@article{spacapan2007,
author = {{\v{S}}pacapan, Simon},
title = {Nonexistence of face-to-face four-dimensional tilings in the {L}ee metric},
journal = {European J. Combin.},
volume = {28},
number = {1},
year = {2007},
pages = {127--133},
doi = {10.1016/j.ejc.2005.08.003},
}
@article{horak2009tilings,
author = {Horak, Peter},
title = {Tilings in {L}ee metric},
journal = {European J. Combin.},
volume = {30},
number = {2},
year = {2009},
pages = {480--489},
doi = {10.1016/j.ejc.2008.04.007},
}
@article{horak2009perfect,
author = {Horak, Peter},
title = {On perfect {L}ee codes},
journal = {Discrete Math.},
volume = {309},
number = {18},
year = {2009},
pages = {5551--5561},
doi = {10.1016/j.disc.2008.03.019},
}
@article{leung2020,
author = {Leung, Ka Hin and Zhou, Yue},
title = {No lattice tiling of $\mathbb{Z}^n$ by {L}ee sphere of radius 2},
journal = {J. Combin. Theory Ser. A},
volume = {171},
year = {2020},
pages = {105157},
doi = {10.1016/j.jcta.2019.105157},
eprint = {1808.08520},
archivePrefix = {arXiv},
}
@misc{aim-golomb-welch,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Perfect Lee codes beyond dimension two}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/567-golomb-welch.md},
note = {Entry 567 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00350, "Perfect Lee codes beyond dimension two", clopen.solutions.