《__1度量下三元常重码的新进展_魏歆》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
中国科学:数学2023年第53卷第2期:325∼338SCIENTIASINICAMathematica论文ℓ1度量下三元常重码的新进展献给朱烈教授80华诞魏歆,张先得∗中国科学技术大学数学科学学院,合肥230026E-mail:weixinma@mail.ustc.edu.cn,drzhangx@ustc.edu.cn收稿日期:2022-03-28;接受日期:2022-06-18;网络出版日期:2022-08-23;*通信作者国家自然科学基金(批准号:12171452和11771419)、科技创新2030—“量子通信与量子计算机”重大项目(批准号:2021ZD0302904)、国家重点研发计划(批准号:2020YFA0713100)和量子信息技术安徽省引导性项目(批准号:AHY150200)资助项目摘要ℓ1度量下的常重码在活体DNA存储技术中有非常重要的应用.本文研究长度为n、ℓ1权重为w、最小ℓ1距离为2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4的最优三元常重码的大小.对一般的n和w,本文给出码字个数的上界.当w=6时,本文利用计算代价的方式改进了上界,并通过构造码类给出下界.从而对所有奇数n≠≡9,13,17(mod20)分情形确定了最大码字个数在渐近意义下的精确值或n的一阶、二阶系数.关键词常重码ℓ1度量填充超图分解DNA存储MSC(2020)主题分类94B25,05B401引言常重码是编码理论中的经典研究对象,其任意一个码字在对应度量下有相同的权重.Hamming距离下的常重码由于其在诸多领域中的重要应用(参见文献[7,14,23])以及与组合设计之间的紧密联系(参见文献[2–4,29,30])而被广泛研究.然而非Hamming距离下常重码的研究非常稀少.关于ℓ1距离的研究之前多见于闪存的秩调制方案(rankmodulationscheme)等领域(参见文献[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和Tan[15]用格(lattice)理论和B集研究了q>w时的情形.给定最小距离,码长要h英文引用格式:WeiX,ZhangXD.Newresultsonternaryconstantweightcodesunderℓ1-metric(inChinese).SciSinMath,2023,53:325–338,doi:10.1360/SSM-2022-0051©c2022《中国科学》杂志社www.scichina.commathcn.scichina.com
1魏歆等:ℓ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√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2之间的偶数的情形值得研究.当w=3,4时,文献[5]对几乎所有可能的n和d,用组合构造的方法确定了A3(n,d,w)的确切值.对于任意固定的w,当d=2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2且n充分大时,文献[28]给出了A3(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2,w)的精确值.主要结论列举如下.[5,28]n2+3nn(n+5)定理1.1(i)A3(n,4,3)=⌊6⌋;当n>102时,A3(n,6,4)=⌊12⌋.n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2))(ii)对于任意给定的w>5,当n充分大时,A3(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2,w)=⌊w(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)⌋+n.(iii)A(n,4,4)=D(n,4,3)+n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1);其中若n≠≡0(mod6),则D(n,4,3)=⌊n⌊n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1⌊n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2⌋⌋⌋,否则32432D(n,4,3)=⌊n(⌊n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1⌊n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2⌋⌋√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)⌋.432基于以上结果,本文研究给定权重w>5且最小距离d=2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4时三元常重码的构造,并估计渐近意义下A3(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)的值.对于任意整数n和w,本文给出了A3(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)的上界■■n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)+ϵ⌊w⌋n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)A(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)62,3w(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)⌊w⌋2√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−12其中ϵ⌊w⌋,3(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)+⌈w⌉√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1.22当w=6且n为奇数时,引入码的代价的概念,并通过计算代价的方式,对某些情形下的上界进行改进,最终得到如下结论.定理1.2当n≡1(mod4)时,A(n,8,6)6⌊n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+17n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)⌋,B′.对充分大的n,3120n(1)若n≡1,21,25,45(mod60),则A(n,8,6)=B′;3n(2)若n≡5,41(mod60),则B′√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−16A(n,8,6)6B′.n3nn(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+19n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)当n≡3(mod4)时,A3(n,8,6)6⌊120⌋,Bn.更进一步地,对充分大的n,(3)若n≡3,31,43,51(mod60),则A3(n,8,6)=Bn;(4)若n≡11,23(mod60),则Bn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−136A3(n,8,6)6Bn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1;(5)对n≡3(mod4)的其他值,A3(n,8,6)=Bn+Θ(n).本文余下内容结构如下.第2节简要介绍一些相关术语,将常重码的构造问题转换到超图的填充问题,并列出全文中反复用到的一些重要定理.第3节给出A3(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)的一般上界和构造码的统一思路,并引入码的代价这一概念.第4和5节分别考虑n≡3(mod4)和n≡1(mod4)时码的构造和上界的改进,从而证明定理1.2.最后,第6节总结全文并列举一些公开问题.2预备工作任给两个整数n′6n,记[n′,n],{n′,n′+1,...,n},其中[1,n]进一步简写为[n].对整数q>2,记I:=[0,q√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1],定义In为I上所有n长向量的集合.称In的一个子集C为n长q元码,称C的元qqqq∑n素为码字.任给两个码字u=(ui)i∈[n]和v=(vi)i∈[n],定义它们的ℓ1距离为d(u,v)=i=1|ui√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−vi|.将码字v和全零向量0的距离称为v的ℓ1权重.如果C中所有码字的权重相同,则称C是常重码(constantweightcode,CWC).进一步,若C中任意两个不同码字之间的ℓ1距离至少是d,则称C326
2中国科学:数学第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√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2且n充分大或w比较小时,A3(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2,w)的值已经被完全确定(参见文献[5,28]).所以本文考虑d=2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4的情形.假设C是一个(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−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√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)3码的充分必要条件.引理2.1In的子集C是一个(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)码,当且仅当如下两个条件满足:33(c1)任取C中两个不同码字u和v,有|supp(u)∩supp(v)|62;(c2)任取两个不同的位置i,j∈[n],C中至多存在一个码字u满足ui>1且uj>1.事实上,若C是一个(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)3码,则两个条件(c1)和(c2)显然满足.反之,如果C不是(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)3码,则存在两个码字u,v∈C使得d(u,v)<2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−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√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−E′)为G√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−G′或G√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−E′.若G=(V,E)满足E⊂Pr(V),则称G是一个r-图,其边称为r-边.若E=Pr(V),则称G是(r)完全r-图.记q点完全r-图为Kq.任给r-图G=(V,E)和子集S⊂V满足06|S| 3魏歆等:ℓ1度量下的三元常重码的新进展填充和图分解以及填充的余图.为了给出引理2.1的超图填充版本,对于任意元素u∈In,定义K(3)3u为点集supp(u)上的完全3-图,并定义Du为点集supp(u)上的有向图,其中(i,j)是一条有向边当且仅当ui>1,uj>1.引理2.2In的子集C是一个(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)码,当且仅当满足如下两个条件:33(c1′)集合{K(3)(3)u,u∈C}构成超图Kn的填充;(c2′)集合{D,u∈C}构成K的有向图填充.un下面介绍超图分解存在的必要条件.若r-图G=(V,E)满足对于任意i∈[0,r√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1]以及任意i∑∩∪∑■■■■■■)()()元子集S⊂V,都有G(S)的边数是q√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−i的倍数,则称G是K(r)(r)r√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−iq-可整除的(Kq-divisible).容易看出,“r-图G是K(r)(r)[12]证明了这个q-可整除的”是“r-图G有Kq-分解”的必要条件.Keevash∑∩∪∑■■■■■■)()(n)√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1必要条件在某些条件下也是充分的.对于任意n点r-图G,定义G的边密度d(G)=|E(G)|.r如果存在非负实数c,使得大小不超过h的元素为V(G)中(r√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)-子集的任意集合系A,都满足∩(1√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−|A|c)d(G)|A|n6|E(G(S))|6(1+|A|c)d(G)|A|n,则称G是(c,h)-典型的((c,h)-typical).S∈A定理2.1(参见文献[12,定理1.4])对于任意q>r>1,存在b0,α>0以及正整数h和n0,使得对于任意b>0,当n>n时,任意K(r)√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−α以0q-可整除的(b,h)-典型的r-图G,若满足d(G)>nh2(r)及b 4中国科学:数学第53卷第2期一个(2,3)-填充等价于一个完全图的K3-填充.余图为空图的(2,3)-填充被称为Steiner三元系(Steinertriplesystem,STS).阶为n的Steiner三元系简记为STS(n).已知STS(n)存在当且仅当n≡1,3(mod6)[6].两个(2,3)-填充(X,B)和(X,B)不交,是指B∩B=∅.多个(2,3)-填充不交1212指相互之间两两不交.n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2个不交的STS(n)被称为STS的大集(largeset),简记为LSTS(n).关于LSTS的存在性问题在20世纪七八十年代被我国著名组合学专家陆家羲基本解决[17–22],完整证明于1991年由Teirlinck[27]补全.作为大集工作的延伸,Keevash[13]最近给出了一般设计的大集的渐近存在性.定理2.3(陆氏定律[17–22,27])对于任意正整数n≡1,3(mod6)且n≠=7,存在LSTS(n).3普适上界设C是一个(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)码,w>3.记y是C中1w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2i2i型码字的个数,i∈[⌊w⌋].由引3i2理2.2(c1′)可得()()()()ww√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1⌈w⌉n2y0+y1+···+y⌊w⌋6.(3.1)33233记p为一个1w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2i2i型码字u诱导的有向图D中有向边的个数,则p=(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2i)i+i(i√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1).由引iui理2.2(c2′)可得p1y1+p2y2+···+p⌊w⌋y⌊w⌋6n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1).(3.2)22w(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−i)(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−i√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−i√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)给定w,记ϵi=p.将pi的表达式代入并简单计算得ϵi=3(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)i+(i+1)(i√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1),在i∈[⌊w⌋]下关于i的取值单调递增.因此,w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−i√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−12w(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)|C|=w(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)(y0+y1+···+y⌊w⌋)2⌊w⌋∑2=w(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)y0+[(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−i)(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−i√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−i√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)+ϵipi]yii=1⌊w⌋∑26w(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)y0+[(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−i)(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−i√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−i√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)+ϵ⌊w⌋pi]yi2i=1⌊w⌋()⌊w⌋∑2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−i∑2=6yi+ϵ⌊w⌋piyi32i=0i=16n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)+ϵ⌊w⌋n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1).(由(3.1)和(3.2))2从而,得到如下码C大小的上界.n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+ϵ■w■n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)⌊w⌋2√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−122定理3.1A3(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)6⌊w(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)⌋,其中ϵ⌊w⌋,3(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)+⌈w⌉√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1.223在给定w时,总有A(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)=n+Θ(n2).事实上,可以令n′为比n小且满足3w(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)n′≡w(modw(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2))的最大的正整数.由推论2.1可以说明当n充分大时K(3)(3)n′存在Kw-分解.如果将这个K(3)(3)w型码字n′看作某个Kn的子图,并将这个分解中每一个子图的点集对应成一个1∑∩∪∑■■■■■■)()(′)∑∩∪∑■■■■■■)()()nw的支集,则生成的大小为3/3的码自然满足引理2.2的两个条件,从而此码是(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)3码.为了进一步确定A(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)的值,需要考虑其他型的码字.由引理2.2(c2′)可知,所有1w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2i2i3(i>0)型的码字个数不会超过n的平方阶.这说明在一个最优的(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)码中,1w型码字总3329 5魏歆等:ℓ1度量下的三元常重码的新进展是占据绝大多数.我们的构造思路如下:先将1w√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2i2i(i>0)型的码字全部确定好,然后在余超图中(3)搜索最优的Kw-填充.对于任意正整数k>3,给定V上完全图的一个Kk-填充P,定义∂(P),{e∈P3(V):∃H∈Ps.t.e⊂H}.特别地,对K3-填充,有∂(P)=P.以上构造思想体现在下面引理中.(3)引理3.1考虑[n]上的完全图Kn和完全3-图Kn.给定正偶数w和正整数m,存在n0=n0(w,m),使得当n>n0时,若存在Kn上的一个Kw-填2充P以及集合ε⊂P3([n])满足如下条件:(1)∂(P)∩ε=∅;(2)对于任意二元子集S⊂[n],ε中含S的3-边的个数不超过m;(3)(3)(3)Kn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−(∂(P)∪ε)是Kw-可整除的,∑∩∪∑■■■■■■)()()∑∩∪∑■■■■■■)()()nw则存在大小为(3√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−|∂(P)|√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−|ε|)/3+|P|的(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)3码.证明由于P是Kn上的填充,对于任意二元子集S,含S的区组个数小于等于1.从而∂(P)中含S的3-边的个数小于等于w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2.在3-图G=K(3)w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2.2n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−(∂(P)∪ε)上,n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−|E(G(S))|6m+2∑∩∪∑■■■■■■)()()∑∩∪∑■■■■■■)()()nw(3)利用推论2.1可知,G存在大小为(3√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−|∂(P)|√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−|ε|)/3的Kw-分解D.ww考虑n长码C={u|supp(u)∈P,type(u)=22}∪{v|supp(v)∈D,type(v)=1}.引理2.2保∑∩∪∑■■■■■■)()()∑∩∪∑■■■■■■)()()nw证了C是大小为(3√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−|∂(P)|√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−|ε|)/3+|P|的(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)3码.本文重点考虑w=6的情形,定理3.1给出如下的上界.n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+19n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)推论3.1A3(n,8,6)6⌊120⌋,Bn.为方便起见,称推论3.1中的上界Bn为A3(n,8,6)的普适上界.在(n,8,6)3码里,码字类型只有4种,分别是16、1421、1222和23.为了进一步分析最优码的结构,给出如下定义.定义3.1给定(n,8,6)3码C以及二元对e={i,j}⊂[n],定义参数τk(e)和νk(e)(k∈[3])如下.(1)考虑两条有向边(i,j)和(j,i)被{Du,u∈C}覆盖的情形:有τ1(e)条有向边没有被覆盖;有τ(e)条有向边被某个D覆盖,且type(u)=1421;有τ(e)条有向边被某个D覆盖,且2u3utype(u)=1222.(3)(2)考虑集合{B⊂[n]:e⊂B,|B|=3}中的3-边被{Ku,u∈C}覆盖的情形:有ν1(e)条3-边没有被覆盖;有3ν(e)条3-边被某个K(3)421和u=u=1;有2ν(e)条3-边2u覆盖,且type(u)=1ij3被某个K(3)222和u=u=1.后面两者的定义,即C中有ν(e)个码字的型为u覆盖,且type(u)=1ij21421且u=u=1,以及有ν(e)个码字的型为1222且u=u=1.ij3ij依定义知,τ(e)+τ(e)+τ(e)等于0或2,等于0当且仅当C中存在唯一一个23型码字u使得123e⊂supp(u).参数νk(e)都是介于0和n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2之间的整数.下面举例阐述这些参数,此例中码字采用带下标的支集来表示.例如,五长码字(0,1,0,0,0)和(1,2,2,0,0)可分别表示成{21}和{11,22,32}.例3.1取n=17,e={1,2}.某(n,8,6)3码C中所有支集含e的码字只有如下5个:a={12,21,31,41,51},b={11,22,62,71},c={11,21,81,91,102},d={11,21,112,122},e={11,21,132,142}.则有向边(1,2)被Db覆盖,有向边(2,1)被Da覆盖.依定义知,(τ1(e),τ2(e),τ3(e))=(0,1,1).考虑集合{B⊂[17]:e⊂B,|B|=3}={{1,2,i}:i∈[3,17]}.其中只有3条3-边{1,2,15}、{1,2,16}330 6中国科学:数学第53卷第2期(3)和{1,2,17}不含在这5个码字诱导的Ku中,从而ν1(e)=3.在满足u1=u2=1的所有3个码字c、d和e中,有一个型为1421,有两个型为1222.从而ν(e)=1,ν(e)=2.总之,23(τ1(e),τ2(e),τ3(e),ν1(e),ν2(e),ν3(e))=(0,1,1,3,1,2).在给定的码C下,定义3.1中6个参数的某种加权和能反映码C的大小与普适上界之间的差距,其值越大代表差距越大.称此加权和为e的代价,正式定义如下.定义3.2给定(n,8,6)码C,一个二元对e⊂[n]的代价定义为χ(e),19τ(e)+τ(e)+9τ(e)31243∑+2ν(e)+2ν(e)+9ν(e).定义码C的代价为χ(C)=χ(e).1223e∈P2([n])上述定义中,当e明确时,可以将括号中的e省去.n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+19n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−χ(C)引理3.2给定一个(n,8,6)3码C,有|C|=120.∑证明我们可以改进(3.1)和(3.2).为叙述方便,此证明中e均是[n]中的二元对,求和式中的e均跑遍[n]中所有的二元对.对于任意u∈C且type(u)=1421,D有4条有向边,有6u∑∑个e使得u在e中两个位置上取值都是1.由双计数法得eτ2(e)=4y1和eν2(e)=6y1,从而∑16y=(τ+2ν).同理,对于任意u∈C且type(u)=1222,D有6条有向边,仅有一个e使得u1e22u∑∑∑在两个位置上取值都是1.从而τ(e)=6y和ν(e)=y.进一步有18y=(9τ+9ν).由e32e322e4323τ1和ν1的定义可得∑120y0+60y1+24y2+6y3=n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2ν1(e),(3.3)e∑4y1+6y2+6y3=n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−τ1(e).(3.4)e∑∑计算(3.3)+19×(3.4),可得120|C|+16y1+18y2=n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)+19n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−19eτ1√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2eν1.∑∑将16y=(τ+2ν)和18y=(9τ+9ν)代入即得结论.1e222e4323接下来利用引理3.2改进A3(n,8,6)的普适上界,当n分布在不同的同余类时表现不尽相同.4n3(mod4)时的渐近结果本节主要证明以下结果,此结果说明了推论3.1中的普适上界给出了准确的二次项系数.32n+16n+Θ(n)定理4.1当n≡3(mod4)时,A3(n,8,6)=120.证明过程主要分为3部分:首先当n≡3,31,43,51(mod60)时,证明普适上界在n充分大时是紧的;其次当n≡11,23(mod60)时,证明普适上界不紧,但仍能给出一对相差只有12的渐近上下界;最后补全剩余的情形.4.1当n3,31,43,51(mod60)时的情形引理4.1当n≡3,31,43,51(mod60)且n足够大时,有A3(n,8,6)=Bn.证明由于条件n≡1,3(mod6),从而存在一个STS(n),记作B.在引理3.1中,令P=B,ε=∅.(3)(3)只需要再验证G=Kn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−∂(P)是K6-可整除的,即•n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)≡0(mod120);•(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)≡0(mod20);•(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1≡0(mod4).331 7魏歆等:ℓ1度量下的三元常重码的新进展注意到n≡3,31,43,51(mod60)是以上三者的公共解,从而满足可整除性.由引理3.1知,当n足够n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−3)n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+19n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)大时,存在大小为6+120=120的(n,8,6)3码,达到普适上界.4.2当n11,23(mod60)时的情形引理4.2当n≡11,23(mod60)时,A3(n,8,6)6Bn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1.∑证明参考引理3.2的证明,求和式中的e均跑遍[n]中所有的二元对.我们采用反证法.假设存在(n,8,6)3码C满足|C|=Bn.由于n≡11,23(mod60),所以引理3.2给出了16y1+18y2∑∑+19eτ1+2eν1=χ(C)=80.需用该等式推导出矛盾,根据y1和y2是否为0分成三种情形.∑∑∑(3)(3)若y1=y2=0,则19eτ1+2eν1=80.由双计数法(eν1)/3是Kn中没被任何Ku∑∑∑(u∈C)覆盖的3-边数,从而2eν1≡0(mod6).其唯一可能解为eτ1=2,(eν1)/3=7.由于∑y1=y2=0,所以Kn的填充{Du,u∈C}事实上是K3-填充,且余图中恰有eτ1/2=1条边e.但这与Kn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−e非K3-可整除相矛盾.若y>1,则C中存在一个1421型码字u,记supp(u)={i,j,j,j,j},其中,u=2,u=1,11234ijkk∈[4].令F={(i,j),k∈[4]}为有向边集合,则E(D)∩F=∅.由引理2.2(c1′)知,对于任意kuv∈C,有|E(D)∩F|61.由引理2.2(c2′)知,若存在两不同码字v和w使得E(D)∩F≠=∅和vvE(D)∩F≠=∅,则E(D)∩F≠=E(D)∩F.设|{v∈C:E(D)∩F≠=∅}|=t,则t64.由1421型wvwv22∑∑4和12型码字对应的有向图的结构,分析可得y1+y2>1+t且eτ1>k=1τ1({i,jk})=4√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−t.从∑∑而80>16(1+t)+19(4√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−t)=92√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−3t,此时只有唯一解t=4,且y1=5,y2=eτ1=eν1=0.对应到K的有向图填充中,说明恰好存在5个1421型码字使得其诱导的有向图刚好覆盖完10条无向n边,这表示其中必有两个码字违反引理2.2(c1′),与引理2.2(c1′)相矛盾.最后,若y=0,y>1,类似考虑C中某1222型码字u,记supp(u)={i,i,j,j},其中121212u=u=2.记F′={(i,j):k,l∈[2]},则E(D)∩F′=∅.对于任意v∈C,|E(D)∩F′|61.若i1i2kluv存在两不同码字v和w使得E(D)∩F′≠=∅和E(D)∩F′≠=∅,则E(D)∩F′≠=E(D)∩F′.同样vwvw∑设|{v∈C:E(D)∩F′≠=∅}|=t,则y>t+1且τ>4√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−t.从而80>18(1+t)+19(4√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−t)>80,v2e1矛盾.接下来给出对应的下界构造.本节余下内容中都令L是一个完全二部图,两个部分分别为{ι1,ι2}和{c,c,...,c}.在之后的构造中,L将用于充当引理2.2(c2′)中有向图填充的余图.1220引理4.3当n≡11,23(mod60)且n充分大时,A3(n,8,6)>Bn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−13.证明当n充分大时,可自然地将L嵌入Kn中.由推论2.2可知,Kn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−L有一个K3-填充,记为P.应用引理3.1.令ε={{ι1,ι2,ct},t∈[20]}.易验证∂(P)∩ε=∅且对于任意e∈P2([n]),ε中含(3)(3)e的3-边数小于等于20.余下只需证明G=Kn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−∂(P)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−ε是K6-可整除的.对于任意e∈P2([n]),若e={ι1,ι2},则|E(G(e))|=n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−23,否则|E(G(e))|=n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−3,均是4的倍数.对于任意u∈[n],有■()■■n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−21■√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−20√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−,u∈{ι1,ι2},22|E(G({u}))|=()■■n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1■√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−,其他.22332 8中国科学:数学第53卷第2期∑∩∪∑■■■■■■)()()(n)√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−40两者全是10的倍数.最后,|E(G)|=n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−20,是20的倍数,从而满足可整除性.当n充分33|E(G)|大时,由引理3.1知,存在大小为20+|∂(P)|=Bn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−13的(n,8,6)3码.4.3其余情形本小节说明当n≡7,15,19(mod20)时,A3(n,8,6)的普适上界中的二阶系数是紧的.结合前两小节的结论,可以推导出定理4.1.不同同余类的证明方法相似,所以详细阐述n≡7(mod20)的情形,余下两类着重说明差别,相同的部分略去.证明过程中多次用到可分组设计(groupdivisibledesign,GDD)的存在性.一个可分组设计GDD(t,k,v)是一个三元对(X,G,B),满足:(1)X是v元集,集合中的每个元素称作点;(2)G={U1,U2,...}是X的一个划分,每个部分(称作组)非空;(3)(X,B)是一个(t,k)-填充,且每个区组和每个组之间至多交于一个点;(4)从任意t个组中各挑一个点组成的t元子集恰含在一个区组中.若一个GDD(X,G,B)中点集和组集明确,则简记为B.若一个GDD中G由n1个阶为g1的组,n个阶为g的组,...,n个阶为g的组组成,则称这个GDD的型是gn1gn2···gns.22ss12sn(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+19n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−624n引理4.4对满足n≡7,27(mod60)的充分大的n,有A3(n,8,6)>120.证明对于任意充分大的n,由B´ezout引理知,存在一对非负整数a和b使得n=7a+27b.首先说明存在一个型为7a27b的GDD(2,3,n).这是因为K、K和K都是K-可整除的,而型为n72737a27b的GDD(2,3,n)等价于完全图K挖掉a+b个两两点不交的完全子图K或K后的一个三n727角形分解,从而由推论2.2推导出存在性.设(X,G,B)是型为7a27b的GDD(2,3,n),其中,X=[n],G={U,U,...,U,U,...,U},12aa+1a+b这里当i∈[a]时,|Ui|=7;当i∈[a+1,a+b]时,|Ui|=27.对每个i∈[a+b],在组Ui上构造一个STS(7)或STS(27)(取决于组的大小),记区组集为Bi,并令B¯i=P3(Ui)\Bi.∪∪令ε=i∈[a+b]B¯i和P=(i∈[a+b]Bi)∪B.不难发现,P是X上的一个STS(n),且∂(P)∩ε=∅,(3)ε含每个二元组S⊂[n]的次数不超过27.记G=Kn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−∂(P)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−ε.为应用引理3.1,只需要验证G是(3)K6-可整除的.对于任意u∈[n],记T(u)为u所在组的B¯i中含u的3-边数,即,若|Ui|=7,则T(u)=12;若∑∩∪∑■■■■■■)()()|U|=27,则T(u)=312.从而给定位置u之后,G中含u的边共有n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−T(u)条,恒是10i22的倍数.对于任意两个不同的位置u和v,若两者在同一个组Ui中,i∈[a]或i∈[a+1,a+b],或者在不同的组中,则G中同时含这两点的边的个数分别为n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−7、n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−27和n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−3,均为4的倍数.最后,∑∑∩∪∑■■■■■■)()()(n)T(u)G中的边的个数是20的倍数,这是因为|E(G)|=n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−u∈[n]≡0(mod20).333E(G)n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+19n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−624n由引理3.1可知,当n足够大时,存在大小至少是+>的206120(n,8,6)3码.引理4.5对满足n≡47(mod60)的充分大的n,有n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)+19n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−624n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−80A3(n,8,6)>√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−13.120证明同引理4.4,用B´ezout引理将n个点拆分成a个7长的组U1,...,Ua和b个27长的组Ua+1,...,Ua+b,并定义Bi和B¯i.但当n≡47(mod60)时,Kn不是K3-可整除的,因此以这些组为组集的GDD不存在.令Gn是以Ui(i∈[a+b])为部分构成的完全多部图,我们需要在Gn中333 9魏歆等:ℓ1度量下的三元常重码的新进展表1当n15;19(mod20)时的参数类比同余类|E(G(e))|,e∈P2([n])|E(G({u}))|,u∈[n]n≡15,55,19,e⊂Ui,i6ae⊂Ui,i>a不同组中(n 1)n 1√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−T(u)2239(mod60)n√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−15n√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−19n√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−3e⊂Ui,i6ae⊂Ui,i>ae={ι1,ι2}其余不同组中u∈{ι1,ι2}u∉∈{ι1,ι2}()()n≡35,59n 1√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−n 21n 1√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−n 12222n√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−15n√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−19n√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−23n√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−3(mod60)√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−T(u)√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−20√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−T(u)同余类|E(G)|码大小()n≡15,55,19,()n∑n2u∈[n]T(u)n(n 1)(n 2)+19n(n 1) 288n√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−≡0(mod20)>12039(mod60)333()n≡35,59()n∑ 40n(n 1)(n 2)+19n(n 1) 288n 80n√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−2√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−u∈[n]T(u)√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−20≡0(mod20)>√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−13(mod60)333120去掉一些边使得其满足可整除条件.当n充分大时,a+b>22.在[n]上挑出22个两两不同组的点{ι1,ι2,c1,c2,...,c20},并构造完全二部图L.易知L是Gn的子图.令G′=G√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−L,则G′是K-可整除的.由推论2.2可知G′有K-分解,记作B.记Pnnn3n3∪∪=(i∈[a+b]Bi)∪B,记ε=(i∈[a+b]B¯i)∪{{ι1,ι2,ct},t∈[20]}.不难发现,P是[n]上完全图的K3-填(3)充,且∂(P)∩ε=∅,ε含每个二元组S⊂[n]的次数不超过27.令G=Kn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−∂(P)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−ε.下面验证G(3)是K6-可整除的.对于任意二元组e⊂[n],若e={ι1,ι2},则G中含e的边数为n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−23;否则,若e的两点分别落在同一个组Ui中,i∈[a]或i∈[a+1,a+b],或不同的组中时,G中含e的边数分别为n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−7、n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−27和n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−3;这四者均是4的倍数.同引理4.4证明中定义T(u),若u∈{ι1,ι2},则G中含u的边数为∑∩∪∑■■■■■■)()()∑∩∪∑■■■■■■)()()n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−21√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−T(u)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−20条;否则,G中含u的边数为n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−T(u)条,两者都是10的倍数.22∑22∑∩∪∑■■■■■■)()()(n)√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−40T(u)最后,G中一共有n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−u∈[n]√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−20条边,也是20的倍数.333(n)应用引理E(G)2√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−40n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+19n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−624n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−803.1,当n足够大时,得到大小至少是+>√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−13203120的(n,8,6)3码.接下来简要叙述当n≡15,19(mod20)时的构造.首先将n分成a个15长的组U1,...,Ua和b个19长的组Ua+1,...,Ua+b.同理,定义Bi和B¯i(i∈[a+b]),以及T(u)(u∈[n]).对于任意u∈[n],若|Ui|=15,则T(u)=84;若|Ui|=19,则T(u)=144.然后分两种情形讨论,当n≡15,55,19,39(mod60)时,证明过程同引理4.4;当n≡35,59(mod60)时,处理方法同引理4.5.表1列出上面两种情形证明过程中的主要参数.综上所述,可以得到定理4.1.5n1(mod4)的渐近结果本节考虑n≡1(mod4)时的情形.首先用计算代价的方法改进A3(n,8,6)的上界,说明普适上界给出的二次项系数并非最优;接着给出构造,确定当n≡1,21,25,45(mod60)时A3(n,8,6)渐近意义下的值,并给出当n≡5,41(mod60)时距上界仅差1的渐近下界.遗憾的是,本节结果仅覆盖了n≡1,5(mod20)的情形.定理5.1当n≡1(mod4)时,A(n,8,6)6⌊n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+17n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)⌋,B′.3120n334 10中国科学:数学第53卷第2期证明只需证明对于任意给定的(n,8,6)3码C和任意二元组e⊂[n],都有χ(e)>4.若此成立,∑则χ(C)=χ(e)>2n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1).由引理3.2可得上界.e∈P2([n])用反证法证明.若存在e使得χ(e)=19τ(e)+τ(e)+9τ(e)+2ν(e)+2ν(e)+9ν(e)<4,则12431223(3)τ1=ν3=0.令S={B⊂[n]:e⊂B,|B|=3}为所有含e的3-边的集合,令T={Ku,u∈C}.由于τ1+τ2+τ3等于0或2,下面分两种情形讨论.当τ1+τ2+τ3=0时,χ(e)=2ν1+2ν2是2的倍数.由τk(k∈[3])的定义知,C中存在唯一一个23型码字u使得e⊂supp(u).若χ(e)=0,则ν=0,即集合S中的所有3-边都被T覆盖.同1时在C中除了23型码字u,所有支集含e的码字全是16型的.这推导出(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1≡0(mod4),与n≡1(mod4)矛盾.从而χ(e)=2.若ν1=1,ν2=0,则在C中除了u之外,所有支集含e的码字全是16型的,同时集合S中仅有一条3-边没有被T覆盖.这推导出(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2≡0(mod4),与n≡1(mod4)矛盾.若ν=0,ν=1,则在C中除了u和另一个1421型码字,所有支集含e的码字12全是16型的,集合S中的所有3-边都被T覆盖.这推导出(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4≡0(mod4),与n≡1(mod4)矛盾.当τ1+τ2+τ3=2时,同理分析在χ(e)<4的限制下τ1=ν1=ν2=ν3=0.所以只有τ2=2或者τ=τ=1两种可能,没有23型码字支集含e.若τ=2,则C中除了两个不同的1421型码字外,232所有支集含e的码字全是16型的;若τ=τ=1,则C中除了一个1421型码字和一个1222型码字23外,所有支集含e的码字也全是16型的.这两种情形下均有S中的所有3-边都被T覆盖,因此,前者要求n≡0(mod4)和后者要求n≡3(mod4)均不满足引理条件.综上,对所有e都有χ(e)>4.引理5.1当n≡1,21,25,45(mod60)且充分大时,A(n,8,6)=B′.3n证明首先指出,任意的n≡1,21,25,45(mod60)同时属于3个同余类:n≡1(mod4),nn(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+17n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)≡0,1(mod5)和n≡1,3(mod6).这保证了是整数,同时定理2.3也保证了1203个不交的STS(n)的存在性,不妨记区组集分别为B1、B2和B3.令P=B1,ε=B2∪B3.应(3)∪3(3)用引理3.1,只需证明G=Kn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−i=1Bi的K6-可整除性.任意两个不同u,v∈[n]共同出现在∑∩∪∑■■■■■■)()()∑∩∪∑■■■■■■)()()∑∩∪∑■■■■■■)()()G的(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−3条边中,任意位置u出现在G的n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−3n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1条边中,G一共有n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−n条边.2232对于引理给定的参数n,这3个值分别是4、10和20的倍数,满足可整除性.从而存在码字个数为(n)n3√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−(2)n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−2)+17n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)20+6=120的(n,8,6)3码.引理5.1的证明中用到3个不交的STS(n).当n≡5(mod6)时,不存在STS(n),这时最优(2,3)-填充的大小为⌊n(n√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)⌋√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1,余图是4长圈[25].为了保证引理3.1中的K(3)-可整除性,需要构造3个66特殊的不交的最优(2,3)-填充.首先给出n=11时的构造.令X=[0,8]∪{∞1,∞2}.表2列出X上3个不交的最优(2,3)-填充的区组集和余图,其中余图(a,b,c,d)指边集为{{a,b},{b,c},{c,d},{d,a}}的一个4长圈.下面分析表2中3个余图的性质.定义三元组:∆1={3,8,∞2}、∆2={3,5,0}、∆3={3,5,1}和∆={0,1,∞}.易验证这4个三元组均不在A⋆∪A⋆∪A⋆中.同时对任意二元组e⊂[n],e在3个42123余图中出现的次数等于e在∆1、∆2、∆3和∆4中出现的次数(如图1),即{∆i:i∈[4]}构成3个4圈的并的一个三角形分解.表2中的结构可以推广到一般的参数n=6k+5.任给k>3,在n元集Y上总存在3个组集相同的不交的16(k√\|⟩⟨}{⌉⌈⌋⌊WTSPMKHFCBA⊥⊤̸∈∞′→⊆∗×·−1)111型GDD(2,3,n),记为B、B和B(参见文献[9,引理11]).不妨设长组为123X=[0,8]∪{∞1,∞2}.将表2中的3个11阶的最优(2,3)-填充和4个三元组∆1、∆2、∆3和∆4自然嵌入到X上.令A=B∪A⋆、A=B∪A⋆和A=B∪A⋆.则3个填充A(i∈[3])均是Y上111222333i335 11魏歆等:ℓ1度量下的三元常重码的新进展表23个不交的最优的11阶(2;3)-填充填充区组集余图A⋆:174,18∞1,105,612,782,70∞1,(8,3,1,∞2)1765,73∞2,806,845,034,02∞2,63∞1,64∞2,235,24∞1,5∞1∞2A⋆:170,03∞1,028,046,136,12∞1,(3,5,0,∞2)2148,15∞2,234,378,257,26∞2,45∞1,47∞2,568,67∞1,8∞1∞2A⋆:026,047,058,0∞1∞2,123,14∞1,(1,5,3,0)316∞2,178,245,27∞1,28∞2,34∞2,367,38∞1,468,56∞1,57∞2∞2∞2∞2图13个不交最优填充的余图和对应的4个三元组的最优(2,3)-填充,并且继承了X上的3个余图,从而∆1、∆2、∆3和∆4依然满足类似性质.引理5.2当n≡5,41(mod60)且充分大时,A(n,8,6)>B′√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1.3n证明当n≡5,41(mod60)时,如上构造[n]上3个不交的最优(2,3)-填充A1、A2和A3和4(3)个三元组∆1、∆2、∆3和∆4.令P=A1,ε=A2∪A3∪{∆i:i∈[4]}.可验证图G=Kn√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−∂(P)√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−ε是K(3)-可整除的.从而由引理3.1知,存在大小是B′√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1的(n,8,6)码.6n3(3)当n≡1,5(mod20)时,引理5.1和5.2利用了3个不交的最优K3-填充构造出合适的K6-可整除的3-图.我们猜测类似的方法可以解决n≡9,13,17(mod20)的情形.其中一个思路是证明3个不交的GDD的存在性:给定两个互素的正整数g1和g2,存在正整数n0=n0(g1,g2),使得当n>n0时,如果K3-可整除的n点完全多部图G的每部大小只能是g1或g2,那么存在3个以G为公共组集的不交的GDD(2,3,n),其中G是G的组划分.若该结构存在,则可以类似于引理4.4和4.5确定当n≡1(mod4)时A3(n,8,6)的二阶系数.但遗憾的是,目前无法证明所需的3个不交的GDD的存在性.6结论本文研究了ℓ1距离下的(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)3码,给出了最优(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)3码的码字个数的一般上界.当w=6时,我们引进了码的代价的概念,并利用这个概念改进了普适上界.进一步,当n为奇数且n≠≡9,13,17(mod20)时,我们利用图分解定理给出了接近最优的码(至少达到二次项系数)的构造.336 12中国科学:数学第53卷第2期下面列举需要进一步研究的问题.32n+14n+Θ(n)问题6.1当n≡1(mod4)时,证明A3(n,8,6)=120.当n为偶数时,用计算代价χ(C)的方法也可以适当改进普适上界(证明从略):■■■n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)+18n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)■,n≡0(mod4),120A3(n,8,6)653■■n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−2)+n(n√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−1)■3,n≡2(mod4).120我们将继续寻找与这个上界足够接近的下界构造.问题6.2当n为偶数时,确定A3(n,8,6)的二阶系数.本文给出了两个离上界只相差常数的下界构造(引理4.5和5.2),如果能通过分析进一步消除这些情况的上下界差从而得到这些情况的确定值,这将是非常有意义的.普适上界在w=6时取到的n在均匀分布的全体正整数轴上拥有正密度,然而当w>6时此上界的表现未知.能否给出在一般情形下更好的上界估计?问题6.3当w>6时,改进A3(n,2w√\∥|⟩⟨}{⌉⌈⌋⌊∨∩∪WVUTSRQPONMLKHGFεDCBA⊥∅∃∀≠∈∞⇒↓→≺≪⊂≈∼⊆≡•⊗⊕±∗×·−4,w)的上界.致谢感谢审稿人为本文提出的建设性意见.参考文献1BargA,MazumdarA.Codesinpermutationsanderrorcorrectionforrankmodulation.IEEETransInformTheory,2010,56:3158–31652CheeYM,GeGN,ZhangH,etal.Hananitriplepackingsandoptimalq-arycodesofconstantweightthree.DesCodesCryptogr,2015,75:387–4033CheeYM,KiahHM,ZhangH,etal.Constructionsofoptimalandnear-optimalmultiplyconstant-weightcodes.IEEETransInformTheory,2017,63:3621–36294CheeYM,ZhangXD.Linearsizeconstant-compositioncodesmeetingtheJohnsonbound.IEEETransInformTheory,2018,64:909–9175ChenTT,MaYM,ZhangXD.Optimalcodeswithsmallconstantweightinl1-metric.IEEETransInformTheory,2021,67:4239–42546ColbournCJ.Triplesystems.In:ColbournCJ,DinitzJH,eds.CRCHandbookofCombinatorialDesigns.London:CRCPress,2006,58–717CostelloDJ,ForneyGD.Channelcoding:Theroadtochannelcapacity.ProcIEEE,2007,95:1150–11778JainS,HassanzadehFF,SchwartzM,etal.Duplication-correctingcodesfordatastorageintheDNAoflivingorganisms.IEEETransInformTheory,2017,63:4996–50109JiLJ.Partitionoftriplesoforder6k+5into6k+3optimalpackingsandonepackingofsize8k+4.GraphsCombin,2006,22:251–26010JiangAA,LiH,WangY.Errorscrubbingcodesforflashmemories.In:Proceedingsofthe11thCanadianWorkshoponInformationTheory.Ottawa:IEEE,2009,32–3511JinushiH,SakaniwaK.Aconstructionmethodformultilevelerror-correctingcodesbasedonabsolutesummationweight.In:Proceedingsofthe1990IEEEInternationalSymposiumonInformationTheory.SanDiego:IEEE,1990,8712KeevashP.Theexistenceofdesigns.arXiv:1401.3665v3,201913KeevashP.TheexistenceofdesignsII.arXiv:1802.05900,201814KingOD.BoundsforDNAcodeswithconstantGC-content.ElectronJCombin,2003,10:3315Kovaˇcevi´cM,TanVYF.Codesinthespaceofmultisets—Codingforpermutationchannelswithimpairments.IEEETransInformTheory,2018,64:5156–516916Kovaˇcevi´cM,Vukobratovi´cD.Perfectcodesinthediscretesimplex.DesCodesCryptogr,2015,75:81–9517LuJX.OnlargesetsofdisjointSteinertriplesystemsI.JCombinTheorySerA,1983,34:140–14618LuJX.OnlargesetsofdisjointSteinertriplesystemsII.JCombinTheorySerA,1983,34:147–15519LuJX.OnlargesetsofdisjointSteinertriplesystemsIII.JCombinTheorySerA,1983,34:156–182337 13魏歆等:ℓ1度量下的三元常重码的新进展20LuJX.OnlargesetsofdisjointSteinertriplesystems,IV.JCombinTheorySerA,1984,37:136–16321LuJX.OnlargesetsofdisjointSteinertriplesystems,V.JCombinTheorySerA,1984,37:164–18822LuJX.OnlargesetsofdisjointSteinertriplesystems,VI.JCombinTheorySerA,1984,37:189–19223MilenkovicO,KashyapN.OnthedesignofcodesforDNAcomputing.In:ProceedingsoftheInternationalWorkshoponCodingandCryptography.Heidelberg:Springer-Verlag,2005,100–11924ShomoronyI,HeckelR.DNA-basedstorage:Modelsandfundamentallimits.IEEETransInformTheory,2021,67:3675–368925SpencerJ.Maximalconsistentfamiliesoftriples.JCombinTheory,1968,5:1–826TalliniLG,BoseB.Onl1-distanceerrorcontrolcodes.In:Proceedingsofthe2011IEEEInternationalSymposiumonInformationTheory.St.Petersburg:IEEE,2011,1061–106527TeirlinckL.AcompletionofLu’sdeterminationofthespectrumforlargesetsofdisjointSteinertriplesystems.JCombinTheorySerA,1991,57:302–30528WeiX,ChenTT,ZhangXD.Optimalternarycodeswithweightwanddistance2w√|}{⌉⌈WCBA∉∈∞⊂≡∗×·−2inl1-metric.IEEETransInformTheory,2021,67:7221–723129ZhangH,GeGN.Optimalternaryconstant-weightcodesofweightfouranddistancesix.IEEETransInformTheory,2010,56:2188–220330ZhangH,ZhangXD,GeGN.Optimalternaryconstant-weightcodeswithweight4anddistance5.IEEETransInformTheory,2012,58:2706–271831ZhouHC,SchwartzM,JiangAA,etal.Systematicerror-correctingcodesforrankmodulation.IEEETransInformTheory,2015,61:17–32Newresultsonternaryconstantweightcodesunderℓ1-metricXinWei&XiandeZhangAbstractConstantweightcodesunderℓ1-metricareimportantinthetechnologyofstorageinliveDNA.Inthispaper,westudythesizeofoptimalternaryconstantweightcodeswithgivenlengthn,ℓ1-weightwandminimumℓ1-distance2w∇∥|}{⌉⌈∪SPMF■∈∞⇓⇑⇒↓→⊂∼≡±·−4.Forgeneralnandw,wegiveanupperboundonthenumberofcodewordsinsuchacode.Whenw=6,wefurtherimprovetheupperboundbycomputingthecost,andgivelowerboundsbyconstructions.Inparticularforalloddn■≡9,13,17(mod20),wedeterminethemaximumnumberofcodewords,ordeterminethefirst-orthesecond-ordercoefficientsofnasymptoticallyinthemaximumnumberformula.Keywordsconstantweightcode,ℓ1-metric,packing,hypergraphdecomposition,DNAstorageMSC(2020)94B25,05B40doi:10.1360/SSM-2022-0051338
此文档下载收益归作者所有
