Abstract: Let p be a prime integer, t and m positive integers, q=p^t. The Hamming graph H(n, q) is a graph on the set Σn of words of length n (n-words) over an alphabet Σ of size q; two n-words are adjacent if they differ in exactly one position. We define Σ to be the set of t-words over the field F_p. The elements of Σ^n can then be treated as nt-words over F_p, where each nt-word is the concatenation of n words of length t. With such treatment, two nt-words are adjacent in H(n,q) if and only if they differ in exactly one block (independently on the number of differing positions in that block). An additive code in H(n, q) is any subspace of Σn , treated as an nt-dimensional vector space over F_p. A μ-fold 1-perfect code in any graph is a set C of vertices such that every vertex of the graph is at distance not more than 1 from exactly μ elements of C. If q is prime, then multifold 1-perfect codes of all possible parameters can be obtained as the union of cosets of linear (over Fq ) multifold 1-perfect codes (which are easy to characterize). This does not hold if q is not prime. However, it becomes true if we replace “linear” by “additive”. The parameters of additive multifold 1-perfect codes are characterized by the following theorem. THEOREM. Let q=p^t for a prime p. An additive 1-perfect code in H(n,q) exists if and only if for some integer k and m=nt−k there hold (i) μq^n/(qn-n+1)=p^k, (ii) m≥t or p^{t−m} divides μ. Moreover, if (i) holds, then (ii) is equivalent to (ii’) n≡1 mod q.

Cite: Krotov D.S.
On multifold 1-perfect codes over non-prime fields
Международная конференция "МАЛЬЦЕВСКИЕ ЧТЕНИЯ" 14-18 Nov 2022