__1度量下三元常重码的新进展_魏歆.pdf

中国科学:数学2023年第53卷第2期:325338SCIENTIA SINICA Mathematica论文英文引用格式:Wei X,Zhang X D.New results on ternary constant weight codes under 1-metric(in Chinese).Sci Sin Math,2023,53:325338,doi:10.1360/SSM-2022-0051c 2022中国科学 杂志社1度量下三元常重码的新进展献给朱烈教授80华诞魏歆,张先得中国科学技术大学数学科学学院,合肥 230026E-mail:,收稿日期:2022-03-28;接受日期:2022-06-18;网络出版日期:2022-08-23;*通信作者国家自然科学基金(批准号:12171452 和 11771419)、科技创新 2030“量子通信与量子计算机”重大项目(批准号:2021ZD0302904)、国家重点研发计划(批准号:2020YFA0713100)和量子信息技术安徽省引导性项目(批准号:AHY150200)资助项目摘要1度量下的常重码在活体DNA存储技术中有非常重要的应用.本文研究长度为n、1权重为w、最小1距离为2w 4的最优三元常重码的大小.对一般的n和w,本文给出码字个数的上界.当w=6时,本文利用计算代价的方式改进了上界,并通过构造码类给出下界.从而对所有奇数n 9,13,17(mod 20)分情形确定了最大码字个数在渐近意义下的精确值或n的一阶、二阶系数.关键词常重码1度量填充超图分解DNA 存储MSC(2020)主题分类94B25,05B401引言常重码是编码理论中的经典研究对象,其任意一个码字在对应度量下有相同的权重.Hamming距离下的常重码由于其在诸多领域中的重要应用(参见文献7,14,23)以及与组合设计之间的紧密联系(参见文献24,29,30)而被广泛研究.然而非Hamming距离下常重码的研究非常稀少.关于1距离的研究之前多见于闪存的秩调制方案(rank modulation scheme)等领域(参见文献1,10,26,31).基于Jain等8关于活体DNA存储方案的研究,本文考虑1距离下的常重码.另外,在一些信息以多重集合的形式出现的交流信道里,1距离下的常重码也有广泛应用,具体参见文献15,16,24.记长度为n、最小1距离为d、每个码字1权重为w的q元常重码为(n,d,w)q码.一个(n,d,w)q码能达到的最大码字个数记为Aq(n,d,w),称取到极值情形的码为最优码.确定Aq(n,d,w)的值并构造相应的最优码是编码理论的核心问题之一.当q=2时,1距离和Hamming距离等价.当q 2时,两种距离不再等价,关于1距离上的常重码的结果十分稀少,据作者所知目前只有文献5,11,15,28.其中,Kova cevi c和Tan15用格(lattice)理论和Bh集研究了q w时的情形.给定最小距离,码长要魏歆等:1度量下的三元常重码的新进展么不变,要么随权重成比例变化给出一系列关于Aq(n,d,w)的渐近结果.他们的方法主要应用于码长和权重可比的情形,若权重是固定值,则结论还有较大的改进空间,其中一些小权重的情形被文献5改进.当q=3时,文献5,28研究了给定最小距离和权重下的1距离三元常重码的最大码字个数.在(n,d,w)3码中,若d为奇数,则A3(n,d,w)=A3(n,d+1,w);若d=2或d 2w,则A3(n,d,w)的结果平凡.从而只有d为4到2w 2之间的偶数的情形值得研究.当w=3,4时,文献5对几乎所有可能的n和d,用组合构造的方法确定了A3(n,d,w)的确切值.对于任意固定的w,当d=2w 2且n充分大时,文献28给出了A3(n,2w 2,w)的精确值.主要结论列举如下.定理1.15,28(i)A3(n,4,3)=n2+3n6;当n 102时,A3(n,6,4)=n(n+5)12.(ii)对于任意给定的w 5,当n充分大时,A3(n,2w 2,w)=n(n1(w1)(w2)w(w1)+n.(iii)A3(n,4,4)=D(n,4,3)+n(n1)2;其中若n 0(mod 6),则D(n,4,3)=n4n13n22,否则D(n,4,3)=n4(n13n22 1).基于以上结果,本文研究给定权重w 5且最小距离d=2w 4时三元常重码的构造,并估计渐近意义下A3(n,2w 4,w)的值.对于任意整数n和w,本文给出了A3(n,2w 4,w)的上界A3(n,2w 4,w)6n(n 1)(n 2)+w2n(n 1)w(w 1)(w 2),其中w2,3(w 1)+w221w21.当w=6且n为奇数时,引入码的代价的概念,并通过计算代价的方式,对某些情形下的上界进行改进,最终得到如下结论.定理1.2当n 1(mod 4)时,A3(n,8,6)6 n(n1)(n2)+17n(n1)120,Bn.对充分大的n,(1)若n 1,21,25,45(mod 60),则A3(n,8,6)=Bn;(2)若n 5,41(mod 60),则Bn 1 6 A3(n,8,6)6 Bn.当n 3(mod 4)时,A3(n,8,6)6 n(n1)(n2)+19n(n1)120,Bn.更进一步地,对充分大的n,(3)若n 3,31,43,51(mod 60),则A3(n,8,6)=Bn;(4)若n 11,23(mod 60),则Bn 13 6 A3(n,8,6)6 Bn 1;(5)对n 3(mod 4)的其他值,A3(n,8,6)=Bn+(n).本文余下内容结构如下.第2节简要介绍一些相关术语,将常重码的构造问题转换到超图的填充问题,并列出全文中反复用到的一些重要定理.第3节给出A3(n,2w 4,w)的一般上界和构造码的统一思路,并引入码的代价这一概念.第4和5节分别考虑n 3(mod 4)和n 1(mod 4)时码的构造和上界的改进,从而证明定理1.2.最后,第6节总结全文并列举一些公开问题.2预备工作任给两个整数n6 n,记n,n,n,n+1,.,n,其中1,n进一步简写为n.对整数q 2,记Iq:=0,q1,定义Inq为Iq上所有n长向量的集合.称Inq的一个子集C为n长q元码,称C的元素为码字.任给两个码字u=(ui)in和v=(vi)in,定义它们的1距离为d(u,v)=ni=1|uivi|.将码字v和全零向量0的距离称为v的1权重.如果C中所有码字的权重相同,则称C是常重码(constant weight code,CWC).进一步,若C中任意两个不同码字之间的1距离至少是d,则称C326中国科学:数学第 53 卷第 2 期是一个(n,d,w)q码.给定码长n、权重w和最小距离d,记所有(n,d,w)q码的码字个数的最大值为Aq(n,d,w).确定Aq(n,d,w)的值是编码理论的经典核心问题之一.本文主要研究q=3的情形,即三元码.当w固定时,d=2或d=2w是平凡的情形.当d=2w 2且n充分大或w比较小时,A3(n,2w 2,w)的值已经被完全确定(参见文献5,28).所以本文考虑d=2w 4的情形.假设C是一个(n,2w 4,w)3码,我们需要如下术语来刻画C的性质.任给码字u C,定义其支集supp(u)=i n,ui=0,即非零元的位置的集合.如果码字u的非零元中有a个1和b个2,则称u的型是1a2b,记作type(u)=1a2b.当a=0(或b=0)时,码字u的型简写为2b(或1a).依定义有a+b=|supp(u)|和a+2b=w.下面举例解释这些术语.例2.1当n=5时,码字12000、10200、11200和20200的支集分别为1,2、1,3、1,2,3和1,3.它们的型分别为1121、1121、1221和22.接下来给出一个码是(n,2w 4,w)3码的充分必要条件.引理2.1In3的子集C是一个(n,2w 4,w)3码,当且仅当如下两个条件满足:(c1)任取C中两个不同码字u和v,有|supp(u)supp(v)|6 2;(c2)任取两个不同的位置i,j n,C中至多存在一个码字u满足ui 1且uj 1.事实上,若C是一个(n,2w 4,w)3码,则两个条件(c1)和(c2)显然满足.反之,如果C不是(n,2w 4,w)3码,则存在两个码字u,v C使得d(u,v)2w 4.易证这两个码字至少违反(c1)或(c2)中的一条.接下来用超图填充的语言重写这个充分必要条件.2.1从码到图填充任给有限集合V,记P(V)为V的幂集,记Pr(V)P(V)为V的所有r元子集的全体.一个超图G=(V,E)由点集V和边集E两部分组成,满足E P(V),其中V中的元素称为顶点,E中的元素被称为超边.若两个超图G=(V,E)和G=(V,E)之间存在一一映射:V V且满足e E当且仅当(v):v e E,则称G和G同构.如果V V且E E,则称G是G的子超图.这时,记剩余的子超图(V,E E)为G G或G E.若G=(V,E)满足E Pr(V),则称G是一个r-图,其边称为r-边.若E=Pr(V),则称G是完全r-图.记q点完全r-图为K(r)q.任给r-图G=(V,E)和子集S V满足0 6|S|1,uj 1.引理2.2In3的子集C是一个(n,2w 4,w)3码,当且仅当满足如下两个条件:(c1)集合K(3)u,u C构成超图K(3)n的填充;(c2)集合Du,u C构成Kn的有向图填充.下面介绍超图分解存在的必要条件.若r-图G=(V,E)满足对于任意i 0,r 1以及任意i元子集S V,都有G(S)的边数是(qiri)的倍数,则称G是K(r)q-可整除的(K(r)q-divisible).容易看出,“r-图G是K(r)q-可整除的”是“r-图G有K(r)q-分解”的必要条件.Keevash12证明了这个必要条件在某些条件下也是充分的.对于任意n点r-图G,定义G的边密度d(G)=|E(G)|(nr)1.如果存在非负实数c,使得大小不超过h的元素为V(G)中(r 1)-子集的任意集合系A,都满足(1|A|c)d(G)|A|n 6|SAE(G(S)|6(1+|A|c)d(G)|A|n,则称G是(c,h)-典型的(c,h)-typical).定理2.1(参见文献12,定理1.4)对于任意q r 1,存在b0,0以及正整数h和n0,使得对于任意b 0,当n n0时,任意K(r)q-可整除的(b,h)-典型的r-图G,若满足d(G)n以及b r 2,存在c 0以及正整数n0,使得当n n0时,任意K(r)q-可整除的n点r-图G,若对于任意r 1元顶点集S都有|E(G(S)|n(1 c),则G有K(r)q-分解.证明在定理2.1中,取b=12b0d(G)h2.令c=minb2,12h.下面证明r-图G满足定理2.1中所有条件.由于任意r 1元顶点集S都满足|E(G(S)|n(1 c),故由双计数法可得r|E(G)|(nr1)n(1 c),所以d(G)=|E(G)|(nr)1nnr+1(1 c)1 c.由于 0且n充分大,所以d(G)1c n.接下来只用验证G是(b,h)-典型的.设A是某些r1元顶点集组成的集合系,且|A|=a 6 h.一方面,由于ca 6 ch 612,所以(1+ab)d(G)an (1+2ac)(1c)an n|SAE(G(S)|.其中“n”是因为(1+2ac)(1c)a(1+2ac)(1ac)=1+ac2a2c2,并由ac 612得1+ac2a2c2 1.另一方面,|SAE(G(S)|(1ac)n,而(1ab)d(G)an 6(1ab)n 6(12ac)n 6(1ac)n.从而,G是(b,h)-典型的.由定理2.2容易得到如下推论.推论2.1固定一个非负整数m.任意给定q r 2,存在正整数n0,使得当n n0时,任意K(r)q-可整除的n点r-图G,若满足对于任意r 1元顶点集S都有(nr+1)|E(G(S)|6 m,则G有K(r)q-