Codes in the q-ary Lee Hypercube

Let F_q = {0, 1, . . ., q − 1} be an alphabet of size q, so that F_qⁿ is the q-ary hypercube of dimension n. Let x = (x₁, . . ., x_n) and y = (y₁, . . ., y_n) be two elements in F_qⁿ. The Lee distance between x and y is equal to ^Pn_i=1 min(|x_i − y_i|, q − |x_i − y_i|). Let C ⊆ F_qⁿ; C is called a code. Given an integer radius r > 1, we consider three types of codes with respect to the Lee distance: an r-dominating code C (also called an r-covering code) is such that any element x ∈ F_qⁿ is within distance r from at least one codeword c ∈ C (then c r-dominates x); an r-locating-dominating code C is (i) r-dominating and (ii) such that any two vertices x, y in F_qⁿ \ C are r-dominated by distinct sets of codewords; an r-identifying code C is (i) r-dominating and (ii) such that any two vertices x, y in F_qⁿ are r-dominated by distinct sets of codewords. We look for minimum such codes. For the above three types of codes, we give tables of upper bounds on their smallest cardinalities, for alphabet size q ∈ {4, 5, 6}, dimension n up to 7, and radius r up to 5. These bounds are obtained mainly by using different heuristics (greedy, descent, noising). We conclude with conjectures and open problems.