一对正交的不完全拉丁方完备大集_李栋梁.pdf
《一对正交的不完全拉丁方完备大集_李栋梁.pdf》由会员分享,可在线阅读,更多相关《一对正交的不完全拉丁方完备大集_李栋梁.pdf(18页珍藏版)》请在咨信网上搜索。
1、中国科学:数学2023年第53卷第2期:261278SCIENTIA SINICA Mathematica论文英文引用格式:Li D L,Cao H T.Orthogonal complete large sets of disjoint incomplete Latin squares(in Chinese).Sci Sin Math,2023,53:261278,doi:10.1360/SSM-2022-0003c 2022中国科学 杂志社一对正交的不完全拉丁方完备大集献给朱烈教授80华诞李栋梁,曹海涛南京师范大学数学科学学院,南京 210023E-mail:,收稿日期:2022-01-0
2、4;接受日期:2022-03-01;网络出版日期:2022-04-11;*通信作者国家自然科学基金(批准号:12071226 和 11931006)资助项目摘要不完全拉丁方完备大集,记作LDILS+(n+a,a),由两两不交的n个不完全拉丁方ILS(n+a,a)和a个拉丁方LS(n)构成.正交的不完全拉丁方完备大集,记作OLDILS+(n+a,a),由一对正交的LDILS+(n+a,a)构成.本文研究OLDILS+(n+a,a)的存在性问题,利用有限域上的直接构造以及引入辅助设计OLS+n(n)进行积构造,得到若干OLDILS+(n+a,a)的无穷类.关键词不完全拉丁方正交拉丁方大集正交阵列M
3、SC(2020)主题分类05B05,05B151引言设n为正整数,记In=1,2,3,.,n.设a为非负整数,0 a n,集合X和Y满足|X|=n,|Y|=a,X Y=.令Z=X Y.设L为点集Z上的n+a阶方阵,其行标和列标都用Z中的元素表示.用L(i,j)表示L中位于第i行、第j列的元素.若L满足:(1)(i,j)Y Y(将Y Y称为洞),L(i,j)为空;(2)(i,j)(Z Z)(Y Y),L(i,j)Z;(3)i X,jZL(i,j)=jZL(j,i)=Z;(4)i Y,jZYL(i,j)=jZYL(j,i)=X,则称L为集合Z上的n+a阶带洞Y Y的不完全拉丁方,记作ILS(n+a
4、,a).为方便起见,有时也用三元组的集合来表示ILS(n+a,a),即ILS(n+a,a)=(i,j,L(i,j):(i,j)(Z Z)(Y Y).李栋梁等:一对正交的不完全拉丁方完备大集ILS(n+0,0)就是众所周知的n阶拉丁方,简记为LS(n).一个n阶拉丁方的截态是位于不同行、不同列的n个位置的集合,并且这n个位置上的元素组成的集合恰好为X.截态T的(i,j)位置上元素用T(i,j)表示.设L1和L2均为Z上的ILS(n+a,a).若对于任意(i,j)(ZZ)(Y Y),都有L1(i,j)=L2(i,j),则称L1和L2是不相交的.由ILS(n+a,a)的定义中条件(4)可知两两不相交
5、的ILS(n+a,a)的个数最多是n,并称n个两两不相交的ILS(n+a,a)构成Z上的n+a阶不完全拉丁方大集,记为LDILS(n+a,a).n阶拉丁方大集简记为LDLS(n).LDILS(n+a,a)的存在性问题先后由Wu和Zhu8以及Lei等5完全解决,结果如下.定理1.15,8设n为正整数,a为非负整数,0 a n.LDILS(n+a,a)存在的充分必要条件为(n,a)=(2,1),(6,5).由ILS(n+a,a)的定义中条件(3)可知,当i X且j Z Y时,L(i,j)有n+a个元素可以用,但n个两两不相交的ILS(n+a,a)中只覆盖了其中的n个.因此,Shen和Cao7定义了
6、完备的不完全拉丁方大集.对于Z上的n个ILS(n+a,a)和X上的a个LS(n)中的任意两个不完全拉丁方L1和L2,若对于任意(i,j)(Z Z)(Y Y),都有L1(i,j)=L2(i,j),则称这n+a个不完全拉丁方构成不完全拉丁方完备大集,记为LDILS+(n+a,a).显然,LDILS+(n+a,a)是比LDILS(n+a,a)更强的组合结构,后者是前者的一部分.LDILS+(n+a,a)的存在性问题已经完全解决,结果如下.定理1.27设n为正整数,a为非负整数,0 a n.LDILS+(n+a,a)存在的充分必要条件为(n,a)=(2,1),(6,5).设L1和L2都是Z上的ILS(
7、n+a,a).若(L1(i,j),L2(i,j):(i,j)(Z Z)(Y Y)=(Z Z)(Y Y),则称L1和L2正交,记为OILS(n+a,a).L1和L2正交也可理解为将它们叠加后所有不属于Y Y的二元有序元素对都恰好出现一次.1977年,Zhu10研究了OILS(p+3,3)的存在性问题,得到如下结果.定理1.310对于任意素数p 7,存在OILS(p+3,3).1991年,Heinrich(参见文献2)完全解决了OILS(n+a,a)的存在性问题.定理1.42对于任意正整数n 2k,且(n,k)=(5,1),存在OILS(n+k,k).设Li:i In+a和Mi:i In+a都是L
8、DILS+(n+a,a).若对于任意i In+a,均有Li与Mi正交,则称这两个不完全拉丁方完备大集正交,记为OLDILS+(n+a,a).不作特别说明,默认Li和Mi(1 i n)都是ILS(n+a,a),Li和Mi(n+1 i n+a)都是LS(n).显然,当a=0时,OLDILS+(n+0,0)是一对正交的n阶拉丁方大集,简记为OLDLS(n).因为一对正交的n阶拉丁方存在当且仅当n=2,6,且一对正交的n阶拉丁方经过元素置换可得n对正交的n阶拉丁方,所以OLDLS(n)存在当且仅当n=2,6.正交拉丁方和大集是组合设计的两个重要研究对象.本文将二者结合起来,主要研究OLDILS+(n+
9、a,a)的存在性问题.下面分析OLDILS+(n+a,a)存在的必要条件.设x X,令Rx(L1)=L1(x,j):j Z,Rx(M1)=M1(x,j):j Z.由ILS(n+a,a)的定义可知,Y L1(x,j):j X Rx(L1),Y M1(x,j):j X Rx(M1).262中国科学:数学第 53 卷第 2 期又因L1和M1正交,故(y,y)(L1(i,j),L2(i,j):(i,j)(Z Z)(Y Y),所以由鸽笼原理可得n 2a.再由定理1.2知,OLDILS+(n+a,a)存在的必要条件是n 2a,且n=2,6.目前,关于OLDILS+(n+a,a)的已知结果很少.定理1.56
10、,9(1)存在OLDILS+(n+n2,n2),其中n=4,5,7.(2)存在OLDILS+(35x a)+a,a),其中a=2,3,4,x 1(mod 2).本文将利用有限域给出OLDILS+(n+a,a)的一系列直接构造,同时利用辅助设计OLS+n(n)给出OLDILS+(n+a,a)的积构造,并由它们得到OLDILS+(n+a,a)的一些无穷类.主要结果如下.定理1.6(1)对于任意素数p 5,存在OLDILS+(p+2u,2u),其中1 u p4.(2)对于任意素数p 7,存在OLDILS+(p+3,3).(3)对于任意素数p 11且p 1(mod 6),存在OLDILS+(p+5,5
11、).定理1.7设q 3是奇素数幂,t 3是奇数,且q 1(mod 2t),则存在OLDILS+(q+kt,kt),其中1 k q12t.定理1.8设n 3是正整数,若gcd(n,4)=2,且gcd(n,18)=3,则(1)对于任意素数p 7,p 1(mod 4),存在OLDILS+(np+w,w),w 2,(p1)(n1)2+3 m:(p1)(n1)2+4 m(p1)n2,m为偶数.(2)对于任意素数p 7,p 3(mod 4),存在OLDILS+(np+w,w),2 w(p1)n2.(3)存在OLDILS+(5n+w,w),2 w 2n,w为偶数.(4)存在OLDILS+(4n+w,w),2
12、 w 2n,w为偶数.2有限域上的直接构造本节将推广文献10中构造一对正交拉丁方的方法,并进一步给出OLDILS+(q+t,t)的构造方法.首先给出一些记号.设q是奇素数幂,Fq为q元有限域,Fq 0,1,1.下文中涉及有限域中元素的运算均按照其所在域中的加法和乘法运算规则进行.令K=(k1,k2,.,kt)T,km Fq,且km=kn,1 m n t,As(i,j)=i+j+s,i,j,s Fq,Tskm=(i,j,As(i,j):i j=km+s,s Fq,m It,Cm=sFqTskm,m It.引理2.1As:s Fq是一个q阶拉丁方大集.证明根据定义直接验证即可.引理2.2Tskm是
13、As的截态.证明对于给定的s和m,满足i j=km+s的(i,j)显然有q个,且这些位置在不同的行和不同的列.下面利用反证法证明这q个位置上的元素也是两两不同的.若存在i=i,j=j,使得As(i,j)=As(i,j),则i+j+s=i+j+s,于是i i=(j j).又因为i j=km+s,i j=km+s,所以i i=j j,故=1,与As的定义矛盾.因此,Tskm是As的截态.263李栋梁等:一对正交的不完全拉丁方完备大集注2.1根据Tskm的定义可得Tskm(j+km+s,j)=2s+(+1)j+km,j Fq,Tskm(i,i km s)=(+1)i km+(1 )s,i Fq.引理
14、2.3Cm是一个q阶拉丁方.证明首先证明(i,j):(i,j,As(i,j)Tskm (i,j):(i,j,As(i,j)Tskm=,其中s,s Fq,s=s.设(i,j)和(i,j)分别来自这两个集合,由ij=km+s和ij=km+s可知ij=ij,所以(i,j)=(i,j).对于任意i Fq,下面证明Cm(i,j)=Cm(i,j),j=j.由上面证明可知,(i,j)和(i,j)分别来自不同的截态,不妨设为Tskm和Tskm,s=s.于是i j=km+s,i j=km+s.从而i+j+s=i+j+i j km=i+j+i j i+j+s=i+(1)j+j+s.又因为=1,j=j,所以i+(1
15、)j+j+s=i+(1)j+j+s=i+j+s,故i+j+s=i+j+s.因此,Cm(i,j)=Cm(i,j).同理,对于任意j Fq,有Cm(i,j)=Cm(i,j),i=i.再结合引理2.2可知Cm是一个q阶拉丁方.注2.2根据Cm的定义可得Cm(i,j)=2i+(1)j km,i,j Fq,m It.令Z=X Y,其中X=Fq,Y=m:m It,|X Y|=.下面构造Z上的LDILS+(q+t,t),它的第s个ILS(q+t,t)是由As扩充而成,记为A+s.为方便起见,下面将A+s中行标和列标均在X中的全部位置定义为它的左上角,行标在X中且列标在Y中的全部位置定义为它的右上角,行标在Y
16、中且列标在X中的全部位置定义为它的左下角.A+s中,不属于t个截态Tsk1,Tsk2,.,Tskt的位置上的元素与As的元素相同,截态Tskm中的元素变为m.A+s左下角行标为m、列标为j的元素是原截态Tskm中位于第j列的元素.为定义A+s右上角的元素,我们需要以下记号.设M=(a1,a2,.,an)T是一个元素来自Fq的列向量,用E(M)表示M中元素的集合,即E(M)=a1,a2,.,an.设K=(k1,k2,.,kt)T满足E(K)=E(K)=k1,k2,.,kt.A+s右上角列标为m、行标为i的元素是原截态Tskm中位于第i行的元素.A+s(i,j)的公式如下:A+s(i,j)=Tsk
17、m(j+km+s,j),j X,i=m,m It,Tskm(i,i km s),i X,j=m,m It,m,j X,i=km+s+j,m It,As(i,j),j X,i Fq km+s+j:m It.(2.1)根据上述构造过程以及ILS的定义可得以下引理.引理2.4A+s是一个ILS(q+t,t).引理2.5A+s:s Fq Cm:m It构成Z上的LDILS+(q+t,t).证明由引理2.3和2.4可知,A+s(i,j)是ILS(q+t,t),Cm是LS(q).下面分3种情形证明它们是不相交的.264中国科学:数学第 53 卷第 2 期(1)(i,j)Y X,不妨设i=m.若s=s,因为
18、q为奇素数幂,故km+(+1)j+2s=km+(+1)j+2s,即A+s(i,j)=A+s(i,j).(2)(i,j)X Y,不妨设j=m.若s=s,因为=1,故(1+)ikm+(1)s=(1+)ikm+(1)s,即A+s(i,j)=A+s(i,j).(3)(i,j)X X.分3种情形证明.(i)A+s(i,j)=A+s(i,j),s=s.由引理2.1及A+s(i,j)的定义可知,我们仅需说明m不可能出现在两个ILS的同一个位置上,而这是由引理2.3保证的.(ii)A+s(i,j)=Cm(i,j).当i kn+s+j:n It时,A+s(i,j)Y,所以A+s(i,j)=Cm(i,j);当i
19、kn+s+j:n It时,A+s(i,j)=As(i,j)=i+j+s,Cm(i,j)=2i+(1)j km.若A+s(i,j)=Cm(i,j),则i j=km+s,与i kn+s+j:n It矛盾.(iii)Cm(i,j)=Cn(i,j).由Cm(i,j)=2i+(1)j km及km=kn即证.为构造OLDILS+(q+t,t),利用上述方法,选取不同的参数再构造一个Z上的LDILS+(q+t,t).设 Fq 0,1,1,令L=(l1,l2,.,lt)T,lm Fq,且lm=ln,1 m n t,L=(l1,l2,.,lt)T,E(L)=E(L),Bs(i,j)=i+j+s,i,j,s Fq
20、,Vslm=(i,j,Bs(i,j):i j=lm+s,s Fq,m It,Dm=sFqVslm,m It.进而令B+s(i,j)=Vslm(j+lm+s,j),j X,i=m,m It,Vslm(i,i lm s),i X,j=m,m It,m,j X,i=lm+s+j,m It,Bs(i,j),j X,i Fq lm+s+j:m It,(2.2)其中,=,E(K)E(L)=.注2.3Vslm(j+lm+s,j)=2s+(+1)j+lm,j Fq;Vslm(i,ilms)=(+1)ilm+(1)s,i Fq;Dm(i,j)=2i+(1)j lm,i,j Fq,m It.类似引理2.12.5的
21、证明可得以下结论.引理2.6B+s:s X Dm:m It构成Z上的LDILS+(q+t,t).引理2.7设q是大于3的奇素数幂,t是正整数,且2t 7,则取 Zp,满足3=10.令=3,=1323,K=K=(0,1,)T,L=(a,b,c)T,L=(a,c,b)T,H=(,0,1,b,a,c)T,其中b=1+2,a=+32b,=b,c=1+ab.容易验证=0,1,1,=0,1,1,=,且K、K、L、L和H满足方程组(2.3),故由引理2.7可知存在OLDILS+(p+3,3).定理2.3设q 3是奇素数幂,t 3是奇数,且q 1(mod 2t),则存在OLDILS+(q+kt,kt),其中1
22、 k q12t.证明设q=2te+1.故e=q12t,从而1 k e.设x是Fq的生成元,则xet=1.对于给定的k,取Fq的分圆类Ci=xes+i:s=0,1,.,2t 1,0 i k 1.因为t 3,(x2e)t=1,故可设x2e=1,12.取=x2e1x2e,=x2ex2e1.令K=K=(K0,K1,.,Kk1)T,L=(L0,L1,.,Lk1)T,L=(L0,L1,.,Lk1)T,H=(H0,H1,.,Hk1)T,其中,Ki=Ki=xi(1,x2e,.,(x2e)t1)T,Li=x2eKi,Li=1x2eKi,Hi=(x2e)2Ki,Li)T,0 i k 1.由于x2e=1,12,故=
23、0,1,1,=0,1,1,=.因为t是奇数,所以x(t+2)e/.又因为E(Ki)=xi,Li=x2eKi=x(t+2)eKi,所以E(Ki)E(Li)=.因为E(Ki)E(Li)=xi(x(t+2)e)=xiC0=Ci,Ci Ci=,故E(Ki)E(Li)=.显然E(Ki)=E(Ki),下面证明E(Li)=E(Li),E(Hi)=E(Ki)E(Li).因为E(Li)=1x2eE(Ki)=xe(3t2)E(Ki),E(Li)=x2eKi=x(t+2)eE(Ki),xe(3t2)x(t+2)e=x2e(t2),故E(Li)=E(Li).由于H=(x2e)2Ki,Li)T,E(Ki)=(x2e)2
24、E(Ki),故E(Hi)=E(Ki)E(Li).由于E(Ki)E(Li)=,因此|E(Hi)|=|E(Ki)|+|E(Li)|=2t.269李栋梁等:一对正交的不完全拉丁方完备大集对于方程组(2.3),即(1+)KiKi(1+)LiLi=()(x2e)2KiLi,经过计算,该方程组成立.于是K、K、L、L和H满足引理2.7的条件,所以存在OLDILS+(q+kt,kt).为证明本节的最后一个结论,需要以下已知结论.引理2.933是素数p=6k+1的平方剩余.定理2.4对于素数p 11且p 1(mod 6),存在OLDILS+(p+5,5).证明在引理2.7中,取=132,=1+32(由引理2.
25、9可知,和的取法是有意义的),K=(a,b,c,d,e)T,K=(d,a,b,c,e)T,L=K,L=K,H=(c,b,e,a,d,c,b,e,a,d)T,其中,a=31 2e,b=21 2e,c=3 31 2e,d=31 2e,e是一个非零元.不难验证,当p 11时,H中的元素是两两互异的,并且经过计算化简可知,方程组(2.3)成立当且仅当方程组(1+)abcde(1+)dabce=()cbead(2.4)成立.直接验证可知方程组(2.4)成立,从而根据引理2.7可知,存在OLDILS+(p+5,5).3积构造首先介绍积构造中用到的辅助设计.定义3.1设m和n为正整数,m n,X为n元集.若
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一对 正交 不完全 拉丁 完备 栋梁
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。