A new approach towards the Golomb-Welch conjecture

DOI10.1016/J.EJC.2013.10.010MaRDI QIDQ2637233zbMATH OpenOpenAlexWikidataFDO

Publication date 10 February 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.4875

Lee metric Manhattan metric perfect code

Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (n) dimensions (aspects of discrete geometry) (52C22) Combinatorial codes (94B25)

Abstract: The Golomb-Welch conjecture deals with the existence of perfect

e

% -error correcting Lee codes of word length

n,

P L (n, e)

codes. Although there are many papers on the topic, the conjecture is still far from being solved. In this paper we initiate the study of an invariant connected to abelian groups that enables us to reformulate the conjecture, and then to prove the non-existence of linear PL(n,2) codes for

n l e q 12

. Using this new approach we also construct the first quasi-perfect Lee codes for dimension

n = 3,

and show that, for fixed

n

, there are only finitely many such codes over

Z^{n}

.

Review text

The Manhattan distance between two words, \(u=(u_1,u_2,\ldots,u_n)\) and \(v=(v_1,v_2,\ldots,v_n)\), in \(\mathbb{Z}^n\) is defined as \(d_M(u,v)=\sum_{i=1}^n |u_i-v_i|\). The Manhattan sphere of radius \(r\) around a codeword \(c\) is given by \(\{x \in \mathbb{Z}^n : d_M(x,c) \leq r\}\). A set of codewords whose Manhattan spheres of radius \(r\) are nonoverlapping is an \(r\)-error-correcting code. Moreover, if the spheres form a tiling of \(\mathbb{Z}^n\), then we have a perfect \(r\)-error-correcting code. The Lee distance between two words, \(u=(u_1,u_2,\ldots ,u_n)\) and \(v=(v_1,v_2,\ldots ,v_n)\), in \(\mathbb{Z}_q^n\) is defined as \(d_L(u,v) = \sum_{i=1}^n \min(|u_i-v_i|,q-|u_i-v_i|)\). A perfect \(r\)-error-correcting code in \(\mathbb{Z}_q^n\) under the Lee metric gives a (periodic) perfect \(r\)-error-correcting code in \(\mathbb{Z}^n\) under the Manhattan metric. In particular, this implication can used to prove nonexistence of the former type of codes via nonexistence of the letter. \textit{S. W. Golomb} and \textit{L. R. Welch} [SIAM J. Appl. Math. 18, 302--317 (1970; Zbl 0192.56302)]conjectured that there are no perfect \(r\)-error-correcting codes in \(\mathbb{Z}^n\) for \(n \geq 3\) and \(r \geq 2\). So far, this conjecture has been proved only in some special cases. In this work, the cases of \(n \leq 12\) and \(r=2\) are settled for \textit{linear} codes. Quasi-perfect codes in \(\mathbb{Z}^n\) are also studied.

Recommendations

Cites work

Cited in

(18)

This page was built for publication: A new approach towards the Golomb-Welch conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2637233)