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)=Tskm(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
