Perfect codes in the discrete simplex
We study the problem of existence of (nontrivial) perfect codes in the discrete \( n \)-simplex \( \Delta _{\ell }^n := \left\{ \left( \begin{array}{l} x_0, \ldots , x_n \end{array}\right) : x_i \in {\mathbb {Z}}_{+}, \sum _i x_i = \ell \right\} \) under \( \ell _1 \) metric. The problem is motivated by the so-called multiset codes, which have recently been introduced by the authors as appropriate constructs for error correction in the permutation channels. It is shown that \( e \)-perfect codes in the 1-simplex \( \Delta _{\ell }^1 \) exist for any \( \ell \ge 2e + 1 \), the 2-simplex \( \Delta _{\ell }^2\) admits an \( e \)-perfect code if and only if \( \ell = 3e + 1 \), while there are no perfect codes in higher-dimensional simplices. In other words, perfect multiset codes exist only over binary and ternary alphabets.
perfect codes discrete simplex multiset codes permutation channel sphere packing integer codes manhattan metric 94b25 05b40 52c17 05c12 68r99