ON ALMOST PERFECT LINEAR LEE CODES OF PACKING RADIUS 2 XIAODONG XU1AND YUE ZHOU2y

2025-05-02 0 0 691.75KB 26 页 10玖币

侵权投诉

ON ALMOST PERFECT LINEAR LEE CODES OF PACKING

RADIUS 2

XIAODONG XU 1AND YUE ZHOU 2, †

Abstract. More than 50 years ago, Golomb and Welch conjectured that there

is no perfect Lee codes Cof packing radius rin Znfor r≥2 and n≥3.

Recently, Leung and the second author proved that if Cis linear, then the

Golomb-Welch conjecture is valid for r= 2 and n≥3. In this paper, we

consider the classiﬁcation of linear Lee codes with the second-best possibility,

that is the density of the lattice packing of Znby Lee spheres S(n, r) equals

|S(n,r)|

|S(n,r)|+1 . We show that, for r= 2 and n≡0,3,4 (mod 6), this packing

density can never be achieved.

1. Introduction

Let Zdenote the ring of integers. For two words x= (x1,··· , xn) and y=

(y1,··· , yn)∈Zn, the Lee distance (also known as `1-norm, taxicab metric, recti-

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

dL(x, y) =

i=1 |xi−yi|for x, y ∈Zn.

ALee code Cis just a subset of Znendowed with the Lee distance. If Cfurther

has the structure of an additive group, i.e. Cis a lattice in Zn, then we call Calinear

Lee code. Lee codes have many practical applications, for example, constrained and

partial-response channels [20], ﬂash memory [21] and interleaving schemes [3].

The minimum distance between any two distinct elements in Cis called the

minimum distance of C. Given a Lee code of minimum distance 2r+ 1, for any

x∈Zn, if one can always ﬁnd a unique c∈Csuch that dL(x, c)≤r, then Cis

called a perfect code. This is equivalent to

Zn=˙

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

where

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

i=1 |xi| ≤ r)

and S(n, r) + c:= {v+c:v∈S(n, r)}. Thus, the existence of a perfect Lee code

implies a tiling of Znby Lee spheres of radius r.

Perfect Lee codes exist for n= 1,2 and any r, and for n≥3 and r= 1. Golomb

and Welch [7] conjectured that there are no more perfect Lee codes for other choices

of nand r. This conjecture is still far from being solved, despite many eﬀorts and

Date: October 10, 2022.

Key words and phrases. Lee metric, perfect code, Golomb-Welch conjecture, Cayley graph.

The extended abstract [23] of an earlier version of this paper was presented in the 12th Inter-

national Workshop on Coding and Cryptography (WCC) 2022.

arXiv:2210.03361v1 [math.CO] 7 Oct 2022

2 X. XU AND Y. ZHOU

various approaches applied on it. We refer the reader to the recent survey [11] and

the references therein. For perfect codes with respect to other metrics, see the very

recent monograph [6] by Etzion.

Figure 1. Tiling of R2by L(2,2)

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

It is not diﬃcult to see that there is a tiling of Znby S(n, r) if and only if there is

a tiling of Rnby L(n, r). Figure 1 shows a (lattice) tiling of R2by L(2,2). As the

shape of L(n, r) is close to a cross-polytope when ris large enough, one can use

the cross-polytope packing density to prove the Golomb-Welch conjecture provided

that ris large enough compared with n. In fact, this idea was ﬁrst applied by

Golomb and Welch themselves in [7]. There are some other geometric approaches,

including the analysis of some local conﬁgurations of the boundary of Lee spheres

in a tiling by Post [17], and the density trick by Astola [2] and Lepist¨o [13].

However, it seems that the geometric approaches do not work for small rand

large n. In the past several years, algebraic approaches have been proposed and

applied on the existence of perfect linear Lee code for small r. In [12], Kim in-

troduced a symmetric polynomial method to study this problem for sphere radius

r= 2. This approach has been extended by Zhang and Ge [24], and Qureshi [18]

for r≥3. See [10, 11, 19, 25] for other related results. In particular, Leung and the

second author [14] succeeded in getting a complete solution to the case with r= 2:

there is no perfect linear Lee code of minimum distance 5 in Znfor n≥3.

It is worth pointing out that the existence of a perfect linear Lee code of minimum

distance 2r+ 1 in Znis equivalent to an abelian Cayley graph of degree 2nand

diameter rwhose number of vertices meets the so-called abelian Cayley Moore

bound; see [4, 25]. For more results about the degree-diameter problems in graph

theory, we refer to the survey [16].

It is clear that a perfect Lee code Cmeans the packing density of Znby S(n, r)

with centers consisting of all the elements in Cis 1. If there is no perfect linear

Lee code for r≥2 and n≥3, one may wonder whether the second best is possible,

which is about the existence of a lattice packing of Znby S(n, r) with density

ON ALMOST PERFECT LINEAR LEE CODES OF PACKING RADIUS 2 3

|S(n,r)|

|S(n,r)|+1 . We call such a linear Lee code almost perfect. In Figure 2, we present

a lattice packing of Z2by S(2,2), and its packing density is |S(2,2)|

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

14 . This

example and the numbers labeled on the cubes will be explained later in Example

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

APLL code.

Figure 2. An almost perfect linear Lee code in Z2

The packing radius of a Lee code Cis deﬁned to be the largest integer r0such that

for any element w∈Znthere exists at most one codeword c∈Cwith dL(w, c)≤r0.

The covering radius of a Lee code Cis the smallest integer r00 such that for any

element w∈Znthere exists at least one codeword c∈Cwith dL(w, c)≤r00. 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, and its minimum distance is 2r+1

for n > 1 and 2r+ 2 for n= 1.

A Lee code is called t-quasi-perfect if its packing radius and covering radius are

tand t+1, respectively. Note that an APLL code is a quasi-perfect Lee code, but a

quasi-perfect Lee code is not necessarily almost perfect. For instance, two families

of 2-quasi-perfect codes in Znare constructed in [4] and the packing density equals

2n2+2n+1

(2n±1)2, where n= 2[p

4] for a prime psatisfying p≥7 and p≡ ±5 (mod 12). In

particular, the packing density equals 41

49 when n= 4, and it tends to 1

2for big n.

We refer to [1, 4, 15] for more constructions and other results on quasi-perfect Lee

codes.

About the existence of APLL codes of packing radius 2, one can apply the

symmetric polynomial method in [12] and the algebraic number theory approach

in [25] to derive some partial results. For n≤105, one can exclude the existence of

APLL codes of minimum distance 5 for 76,573 choices of n. For more details, see

[8].

The main result of this paper is the following one.

Theorem 1.1. 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.

4 X. XU AND Y. ZHOU

As in [14], our proof is given by investigating group ring equations in Z[G] where

Gis of order |S(n, 2)|+ 1 = 2(n2+n+ 1). However, the situation here is diﬀerent

from the one appeared in [14]. We consider a special subset T⊆Gand show that

Tsplits into two disjoint subsets T0⊆Hand fT1⊆fH where His the unique

subgroup of Gof index 2 and fis the unique involution in G. Then, we analyze

the elements appearing in (T(2)

0+T(2)

1)T0and (T(2)

0+T(2)

1)T1. Unfortunately, we

could not get any contradiction when n≡1,2,5 (mod 6). But we conjecture that

there is no APLL code for this case when n > 2.

The rest part of this paper consists of three sections. In Section 2, we convert

the existence of an almost perfect linear Lee code of packing radius 2 into some

conditions in group ring. Then we prove Theorem 1.1 in Section 3. In Section 4,

we conclude this paper with several remarks and research problems.

2. Necessary and sufficient conditions in group ring

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,

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 of Gand the associated element in Z[G]. Moreover, |D|denotes the number

of distinct elements in D.

The following result converts the existence of APLL codes into an algebraic

combinatorics problem on abelian groups. Its proof is not diﬃcult, and more or

less the same as the proof of Theorem 6 in [9].

Lemma 2.1. There is an APLL code of packing radius rin Znif and only if there

is an abelian group Gand a homomorphism ϕ:Zn→Gsuch that the restriction

of ϕto S(n, r)is injective and G\ϕ(S(n, r)) has only one element.

Proof. First, let us prove the necessary part of the condition. Assume that Cis an

APLL code of packing radius rand w∈Znis an arbitrary element which is not

covered by the lattice packing ˙

Sc∈C(S(n, r) + c). Then, by the deﬁnition of APLL

codes, Cis a subgroup of Znand

(1) Zn=˙

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

∪(w+C).

ON ALMOST PERFECT LINEAR LEE CODES OF PACKING RADIUS 2 5

Consider the quotient group G=Zn/C and take ϕto be the canonical homo-

morphism from Znto G. If there are x, y ∈S(n, r), such that ϕ(x) = ϕ(y), then

z=x−y∈C. Since S(n, r) contains y,x∈S(n, r) +z. This means xis covered by

both S(n, r) + zand S(n, r). By (1), zmust be 0 which implies x=y. Therefore,

ϕis injective and ϕ(w) is the unique element not in ϕ(S(n, r)).

To prove the suﬃcient part, one only has to deﬁne C= ker(ϕ). The veriﬁcation

of the almost perfect property of Cis straightforward. 

The number of elements in a Lee sphere is

|S(n, r)|=

min{n,r}

i=0

2in

ir

i,

which can be found in [7] and [22]. In particular, when r= 2, |S(n, r)|= 2n2+2n+1

and the group Gconsidered in Lemma 2.1 is of order 2n2+ 2n+ 2.

The next result translates the existence of an APLL code into a group ring

condition. The same result has been proved in [8] in the context of the existence

of abelian Moore Cayley graphs with excess one. For completeness, we include a

proof here.

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

if there is an abelian group Gof order 2(n2+n+ 1) and an inverse-closed subset

T⊆Gcontaining ewith |T|= 2n+ 1 such that

(2) T2= 2(G−f)−T(2) + 2ne,

where eis the identity element in Gand fis the unique element of order 2in G.

Proof. The proof of (2) is similar to the proof of Lemma 2.3 in [25]. Suppose

that there exists an APLL code of packing radius 2. By Lemma 2.1, we have a

homomorphism ϕ:Zn→G. Deﬁne ai=ϕ(ei) for i= 1,··· , n. As the radius

equals 2, by deﬁnition, Ghas the following partition

G={e, f}˙

[{a±1

i, a±2

i:i= 1,··· , n}˙

[{a±1

ia±1

j: 1 ≤i<j≤n},

where fis the unique element of Gnot in ϕ(S(n, 2)).

Let T=e+Pn

i=1 ai+Pn

i=1 a−1

i. Hence |T|= 2n+ 1. Moreover,

T2=e+ 2

i=1

ai+ 2

i=1

a−1

i+ n

i=1

ai!2

+ n

i=1

a−1

i!2

+ 2 n

i=1

ai! n

i=1

a−1

= (2n+ 1)e+ 2 n

i=1

ai+

i=1

a−1

i!+

i=1

(a2

i+a−2

i)+2 X

1≤i<j≤n

a±1

ia±1

= 2ne + 2(G−f)−T(2).

Therefore (2) is proved.

Applying the map x7→ x(−1) on the both sides of (2), we get

T2= 2(G−f−1)−T(2) + 2ne,

because Tis inverse-closed. By comparing this equation with (2), we see f=f−1.

As n2+n+ 1 is always odd, there is only one involution in Gwhich is f.

Next we prove the suﬃciency part. Given an inverse-closed subset T⊆Gcon-

taining ewith |T|= 2n+ 1 satisfying (2), we deﬁne a homomorphism ϕ:Zn→G

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

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

10 玖币 0人已下载

立即下载

摘要：

ONALMOSTPERFECTLINEARLEECODESOFPACKINGRADIUS2XIAODONGXU1ANDYUEZHOU2,yAbstract.Morethan50yearsago,GolombandWelchconjecturedthatthereisnoperfectLeecodesCofpackingradiusrinZnforr2andn3.Recently,LeungandthesecondauthorprovedthatifCislinear,thentheGolomb-Welchconjectureisvalidforr=2andn3.Inthispaper,w...

展开>> 收起<<

ON ALMOST PERFECT LINEAR LEE CODES OF PACKING RADIUS 2 XIAODONG XU1AND YUE ZHOU2y.pdf

共26页,预览5页

还剩页未读，继续阅读

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

ON ALMOST PERFECT LINEAR LEE CODES OF PACKING RADIUS 2 XIAODONG XU1AND YUE ZHOU2y

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: