2026/07/23 by Mladen Kovačević
#math.CO #cs.IT #math.IT
The root lattice An, equipped with its graph distance (equivalently, one half of the ambient ℓ1 metric), is isometric to ℤn with the asymmetric Manhattan metric. We study two extremal problems in this space -- the isodiametric problem, i.e., determining the maximum anticode cardinality, and the (non)existence of linear diameter-perfect codes, i.e., lattice tilings by optimal anticodes -- and solve them in dimension 3. We show that, for every integer D≥ 0, the largest cardinality of a diameter-D subset of A3 is \binomD+33+(D+1)\lfloor D2/4\rfloor, and this value is attained by the balanced difference of two discrete simplices. We then prove an integrality-refined simplex-packing obstruction: a sublattice of ℤn of asymmetric Manhattan distance greater than D induces a lattice packing by (D+1)Δn in ℝn. Combining this observation with the exact lattice-packing density of the tetrahedron yields a complete classification in dimension 3: lattice diameter-perfect codes in A3 exist precisely for D=1 and D=2. We also give the equivalent statement for perfect Bh sets of cardinality four. Finally, we formulate a conjecture regarding optimal anticodes in arbitrary dimension, and restate it as an intersection problem for uniform multisets.