ALMOST PERFECT LINEAR LEE CODES OF PACKING RADIUS 2ONLY EXIST FOR SMALL DIMENSIONS ZIJIAN ZHOU1AND YUE ZHOU1y_2

2025-04-30 0 0 521.6KB 29 页 10玖币

侵权投诉

ALMOST PERFECT LINEAR LEE CODES OF PACKING

RADIUS 2ONLY EXIST FOR SMALL DIMENSIONS

ZIJIAN ZHOU 1AND YUE ZHOU 1, †

Abstract. It is conjectured by Golomb and Welch around half a century ago

that there is no perfect Lee codes Cof packing radius rin Znfor r≥2

and n≥3. Recently, Leung and the second author proved this conjec-

ture for linear Lee codes with r= 2. A natural question is whether it is

possible to classify the second best, i.e., almost perfect linear Lee codes of

packing radius 2. We show that if such codes exist in Zn, then nmust be

1,2,11,29,47,56,67,79,104,121,134 or 191.

1. Introduction

Let Vbe a metric space. A code Cof Vis just a subset of points in V. The

code Cis a perfect code with radius r, if for any point xin V, there is exactly one

point in Cwith distance at most rfrom x. Usually, perfect codes yields beautiful

mathematical structures and they also have very important applications in the

associated metric spaces.

In this paper, we are interested in perfect and almost perfect codes with respect

to the Lee metric. For other interesting topics on perfect codes, we refer to the

monograph [4] by Etzion. Let Zdenote the ring of integers. For x= (x1,· · · , xn)

and y= (y1,· · · , yn)∈Zn, the Lee metric (also known as `1-norm, taxicab metric,

rectilinear distance or Manhattan distance) between them is deﬁned by

dL(x, y) =

i=1

|xi−yi|for x, y ∈Zn.

A Lee code Cis called linear, if Cis a lattice in Zn. The minimum distance d(C) of

a Lee code Ccontaining at least two elements is deﬁned to be min{dL(x, y) : x, y ∈

C, x 6=y}.

Lee codes have many practical applications such as interleaving schemes [2],

constrained and partial-response channels [13], and ﬂash memory [14].

By deﬁnition, a Lee code Cis perfect if and only if

Zn=˙

[c∈C(S(n, r) + c),

where

S(n, r) := ((x1,· · · , xn)∈Zn:

i=1

|xi| ≤ r)

is the Lee sphere of radius rcentered at the origin and S(n, r) + c:= {v+c:

v∈S(n, r)}. In another word, the existence of a perfect Lee code is equivalent

Date: October 11, 2022.

Key words and phrases. Lee metric, almost perfect code, Golomb-Wech conjecture.

arXiv:2210.04550v1 [math.CO] 10 Oct 2022

2 Z. ZHOU AND Y. ZHOU

to a tiling of Znby Lee spheres of radius r. The cardinality of S(n, r) has been

determined in [5, 15] as follows

|S(n, r)|=

min{n,r}

i=0

2in

ir

i.

It is worth pointing out that a perfect linear Lee code is also equivalent to an

abelian Cayley graph of degree 2nand diameter rwhose number of vertices meets

the so-called abelian Cayley Moore bound ; see [3, 19]. For more results about the

degree-diameter problems in graph theory, we refer to the survey [11].

It has been showed by Golomb and Welch [5] that perfect Lee codes exist for

n= 1,2 and every positive integer r, and for n≥3 and r= 1. In the same paper,

Golomb and Welch also proposed the conjecture that there are no more perfect Lee

codes for other choices of nand r. To the best of our knowledge, this conjecture

is still far from being solved, despite many eﬀorts and various approaches applied

on it. For more history and results about this conjecture, we refer to the survey [8]

and the references therein.

In recent years, there are some important progress on the existence of perfect

linear Lee code for small r. For r= 2, Leung and the second author [10] proved that

perfect linear Lee codes only exist for n= 1,2. For r≥2, Zhang and Ge [18], and

Qureshi [12] have obtained many nonexistence result by extending the symmetric

polynomial method introduced by Kim [9] for r= 2. It is worth pointing out that

by [16] the linearity assumption of a nonexistence result for perfect linear Lee codes

of radius rin Zncan be removed provided that the size of Lee sphere S(n, r) is a

prime number.

Obviously, a Lee code Cis perfect implies that the packing of Znby S(n, r) with

centers consisting of all the elements in Cis of packing density 1. As there is no

perfect linear Lee code for r= 2 and n≥3 by [10], one natural question is whether

the second best is possible. More precisely, one may ask the following question for

any r≥2.

Question 1.1. Does there exist a lattice packing of Znby S(n, r) with density

|S(n,r)|

|S(n,r)|+1 ?

If such a lattice packing exists, we call the associated linear Lee code almost

perfect. For convenience, we abbreviate the term almost perfect linear Lee code to

APLL code throughout the rest of this paper.

The packing radius (covering radius, resp.) of a Lee code Cis deﬁned to be the

largest (smallest resp.) integer r0such that for any element w∈Znthere exists at

most (at least, resp.) one codeword c∈Cwith dL(w, c)≤r0. It is clear that a Lee

code is perfect if and only if its packing radius and covering radius are the same.

For an APLL code with packing density |S(n,r)|

|S(n,r)|+1 , its packing radius and covering

radius are rand r+ 1, respectively.

It is easy to see that C={x(2r+2) : x∈Z}is the unique APLL code of packing

radius rin Zfor any r.

Let L(n, r) denote the union of n-cubes centered at each point of S(n, r) in Rn.

It is clear that each packing of Znby S(n, r) corresponds to a packing of Rnby

L(n, r). Figure 1 depicts the lattice packing of R2by L(2,2) associated with a lattice

generated by {(1,4),(3,−2)}in Z2. Clearly the packing density is |S(2,2)|

|S(2,2)|+1 =13

14 .

APLL CODES OF PACKING RADIUS 2 ONLY EXIST FOR SMALL DIMENSIONS 3

Figure 1. Packing of R2by L(2,2) associated with an APLL code

Therefore this lattice is an APLL code in Z2. It is not diﬃcult to show that the

minimum distance of an APLL code in Znis 2r+ 1 for n > 1 and 2r+ 2 for n= 1.

In [17], the following result on the nonexistence of APLL codes of packing radius

2 has been obtained.

Theorem 1.2. Let nbe a positive integer. If n≡0,3,4 (mod 6), then there exists

no almost perfect linear Lee code of packing radius 2.

In this paper, we consider the rest cases with n≡1,2,5 (mod 6). Together with

Theorem 1.2, we can prove the following result.

Theorem 1.3. There is no almost perfect linear Lee code of packing radius 2in Zn

for any positive integer nexcept for n= 1,2,11,29,47,56,67,79,104,121,134,191.

The rest part of this paper is organized as follows. In Section 2, we recall some

necessary and suﬃcient conditions of the existence of APLL codes of packing radius

2 in terms of group ring equations. In Section 3, we recall how to prove Theorem

1.2 in [17] and provide an outline of the proof of Theorem 1.3. As this proof is

very long, we separate it into several lemmas and theorems in Sections 4–7, which

tell us that nis bounded if there exist APLL codes of packing radius 2 in Znfor

n≡1,2,5 (mod 6). In Section 8, by two nonexistence results from [6] and [7], we

can exclude most of the rest small values of nand ﬁnish the proof of Theorem 1.3.

In Section 9, we conclude this paper with a conjecture and several remarks.

2. Preliminaries

Let Gbe a ﬁnite group. Let Z[G] denote the set of formal sums Pg∈Gagg, where

ag∈Zand Gis a ﬁnite multiplicative group. The addition and the multiplication

on Z[G] are deﬁned by

g∈G

agg+X

g∈G

bgg:= X

g∈G

(ag+bg)g,

and

g∈G

agg)·(X

g∈G

bgg) := X

g∈G

h∈G

ahbh−1g)·g,

4 Z. ZHOU AND Y. ZHOU

for Pg∈Gagg, Pg∈Gbgg∈Z[G]. Moreover,

λ·(X

g∈G

agg) := X

g∈G

(λag)g

for λ∈Zand Pg∈Gagg∈Z[G].

For an element A=Pg∈Gagg∈Z[G] and t∈Z, we deﬁne

A(t):= X

g∈G

aggt.

A multi-subset Dof Gcan be viewed as an element Pg∈Dg∈Z[G]. In the rest of

this paper, by abuse of notation, we will use the same symbol to denote a multi-

subset in Gand the associated element in Z[G]. Moreover, |D|denotes the number

of distinct elements in D. In another word, |D|is the cardinality of the support of

Dwhich is deﬁned by Supp(D) := {g∈G: the coeﬃcient of gin Dis positive}.

In [17, Section 3], Xu and the second author have proved the equivalence between

the existence of an APLL code of packing radius 2 and some group ring equations.

Lemma 2.1. There exists an APLL code of packing radius 2in Znif and only if

there is an abelian group Hof order n2+n+1 containing two inverse-closed subsets

T0and T1such that the identity element e∈T0, and the following two group ring

equations in Z[H]holds.

T0T1=H−e,(1)

0+T2

1= 2H−T(2)

0−T(2)

1+ 2ne.(2)

Example 2.2. The following examples of T0and T1satisfy (1) and (2).

(a) For n= 1,H=hhi∼

=C3. Let T0={e}and T1={h, h2}.

(b) For n= 2,H=hhi∼

=C7. Deﬁne

T0={e, h, h6}and T1={h2, h5}.

The following result is a collection of necessary conditions for T0and T1, which

is also proved in [17].

Lemma 2.3. Let Hbe an abelian group of order n2+n+ 1. Suppose T0, T1are

subsets of Hsatisfying e∈T0,T(−1)

i=Tifor i= 0,1,(1) and (2). Then the

following statements hold.

(a) e∈T0,e /∈T1;

(b) T0∩T1=∅and T(2)

0∩T(2)

1=∅;

0\ {e}) = T0∩T(2)

1=∅;

(d) {ab :a6=b, a, b ∈T0} ∩ T(2)

0={e};

(e) When nis odd, |T0|=nand |T1|=n+ 1;

(f) When nis even, |T0|=n+ 1 and |T1|=n;

(g) There is no common non-identity element in T2

0and T2

(h) T0∩T(3)

0={e}.

3. Outline of the method

First, let us take a look at the sketch of the proof of the nonexistence of APLL

codes of packing radius 2 with n≡0,3,4 (mod 6) in [17].

APLL CODES OF PACKING RADIUS 2 ONLY EXIST FOR SMALL DIMENSIONS 5

By Lemma 2.1, we only have to show there is no T0and T1in Hsatisfying the

necessary and suﬃcient conditions in it. Deﬁne ˆ

T=T0+T1∈Z[H], k0=|T0|and

k1=|T1|.

Multiplying T0and T1on both sides of (2), we get

0= (2k0−k1)H+ 2nT0+T1−T0ˆ

T(2) ,(3)

1= (2k1−k0)H+ 2nT1+T0−T1ˆ

T(2) .(4)

Consider the above two equations modulo 3

T(2)T0≡(2k0−k1)H+T1−T(3)

0+ 2nT0(mod 3),

T(2)T1≡(2k1−k0)H+T0−T(3)

1+ 2nT1(mod 3).

Note that T3

i≡T(3)

i(mod 3) for i= 0,1. If 3 -|H|, then T(3)

0and T(3)

1are both

subsets of H; for 3 | |H|, we can also show that there are at most 2 elements in

T(3)

iappearing twice for i= 0,1; see Lemma 4.1. Hence, by calculation, we can

derive some strong restrictions on the coeﬃcients of most of the elements in the

right-hand side of the above two equations. For instance, when n≡1 (mod 3) and

nis odd, the ﬁrst equation becomes

T(2)T0≡T1−T(3)

0+ 2T0(mod 3).

As T1,T(3)

0and T0are approximately of size n, most of the elements in Happear

in ˆ

T(2)T0for 3ktimes, k= 0,1,· · · .

Let Xi(Yi, resp.) be the subset of elements of Happearing in ˆ

T(2)T0(ˆ

T(2)T1,

resp.) exactly itimes for i= 0,1,· · · , M0(M1, resp.), which means Xi’s (Yi’s,

resp.) form a partition of the group H. In particular, we deﬁne M0and M1to be

the largest integers such that XM0and YM1are non-empty sets. Then

T(2)T0=

i=0

iXi,(5)

T(2)T1=

i=0

iYi.(6)

By (5) and (6), we have the following three conditions on the value of |Xi|’s and

|Yi|’s:

i=1

i|Xi|= (2n+ 1)k0,(7)

i=1

i|Yi|= (2n+ 1)k1,(8)

i=0

|Xi|=

i=0

|Yi|=n2+n+ 1.(9)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ALMOSTPERFECTLINEARLEECODESOFPACKINGRADIUS2ONLYEXISTFORSMALLDIMENSIONSZIJIANZHOU1ANDYUEZHOU1,yAbstract.ItisconjecturedbyGolombandWelcharoundhalfacenturyagothatthereisnoperfectLeecodesCofpackingradiusrinZnforr2andn3.Recently,Leungandthesecondauthorprovedthisconjec-tureforlinearLeecodeswithr=2.Anatu...

展开>> 收起<<

ALMOST PERFECT LINEAR LEE CODES OF PACKING RADIUS 2ONLY EXIST FOR SMALL DIMENSIONS ZIJIAN ZHOU1AND YUE ZHOU1y_2.pdf

共29页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

ALMOST PERFECT LINEAR LEE CODES OF PACKING RADIUS 2ONLY EXIST FOR SMALL DIMENSIONS ZIJIAN ZHOU1AND YUE ZHOU1y_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: