可分集与几乎可分集的新构造_周君灵.pdf

中国科学:数学2023年第53卷第2期:407418SCIENTIA SINICA Mathematica论文英文引用格式:Zhou J L,Chang Y X.New constructions for partitionable sets and almost partitionable sets(in Chinese).SciSin Math,2023,53:407418,doi:10.1360/SSM-2022-0031c 2022中国科学 杂志社可分集与几乎可分集的新构造献给朱烈教授80华诞周君灵,常彦勋北京交通大学数学研究所,北京 100044E-mail:,收稿日期:2022-02-24;接受日期:2022-04-18;网络出版日期:2022-05-27;*通信作者国家自然科学基金(批准号:11971053 和 12171028)和北京市自然科学基金(批准号:1222013)资助项目摘要可分集(partitionable set,PS)与几乎可分集(almost partitionable set,APS)是组合设计理论中两类重要的组合构型,与许多其他组合结构具有密切联系,如Z-循环Whist竞赛图、循环差阵、不含邻点的循环平衡样本设计、不交差族及光正交码等.由于可分集与几乎可分集的要求比较严苛,其存在性问题迄今远未解决.本文针对p 7(mod 8)为素数的情形,建立p2阶可分集与p阶几乎可分集的新构造方法,给出两类组合构型存在性的若干新结果.特别地,对于p 7(mod 8)的素数p,本文确定p 30,000的绝大部分p2阶PS的存在性,给出特定条件下p阶APS的存在性和渐近存在性,并得到p 0,v1 1(mod 12).(3)(参见文献3,引理3.1)设APS(v,)存在.则当v 3(mod 12)时,22 2 v/3(mod v);当v 7,11(mod 12)时,22 2 0(mod v).可分集与几乎可分集的存在性问题是组合设计中亟待解决的理论问题,下面列出PS的已知结果以及APS在=时的主要结论(=时的结果非常零散).定理1.2对下列阶数v,PS(v)都存在.(1)(参见文献10)v是有限个模4余1素数的乘积.(2)(参见文献6,定理5.6)v 6 300,v 1,5(mod 12).(3)(参见文献7)v=p2,其中p为素数,3 p 3,500,p 3(mod 4).(4)(参见文献3,定理6.4)v=pq,其中p,q 3(mod 4)均为大于3的素数,q 200,(p 1)|(q 1).定理1.3(参见文献3,定理6.6)令v 3(mod 4),v 300,=0.APS(v,)存在当且仅当命题1.1(3)中的必要条件满足.408中国科学:数学第 53 卷第 2 期定理1.4(参见文献2,定理3.2)令u,v 1(mod 4).若PS(u)与PS(v)都存在,则PS(uv)也存在.定理1.4给出的乘积构造仅适用于u,v 1(mod 4)的情形.当u,v 3(mod 4)时,如何构造PS(uv)是长期以来一个棘手问题.文献7给出了p 3(mod 4)时PS(p2)的直接构造,其中假设首轮比赛由(p+1)/2或(p+1)/4个比赛在Zp2可逆元中所有2p或p次剩余作用下生成,借助计算机搜索,得到一系列可分集,结果见定理1.2(3).文献3建立了当素数p 7(mod 8)且满足特定条件时APS(p,2)的存在性(参见文献3,引理4.1),且对某些小素数p构造出PS(p2)(参见文献3,注7.11).本文将推广文献3针对可分集与几乎可分集的构造方法,扩展PS及APS的存在性范围.除了ZCPS-Wh(v),可分集和几乎可分集还与其他组合结构具有密切联系,如循环差阵、不含邻点的循环平衡样本设计和不交差族等.可分集与几乎可分集还可用于构造大容量的光正交码,从而在光码分多址系统具有重要应用.2构造可分集对于正整数n,用Zn表示模n的剩余类环,记Zn=Zn 0;用U(n)表示Zn中所有乘法可逆元做成的乘法群,显然U(n)由Zn中所有与n互素的成员构成,即|U(n)|=(n).特别地,当n为素数时,U(n)=Zn.现约定本节通用的记号.令p 7(mod 8)为素数,易知2在Zp与Zp2中均为平方元,记其在Zp2中的一个平方根为2.若不作特别说明,本节运算均默认在Zp2中进行.令=1+2.考虑与生成的乘法群H=.显然H是U(p2)的子群,且H是一个循环群,H=,其中若的乘法阶为偶数,则=;否则=.由于2|H|,|H|U(p2)|=p(p 1),故|H|2(mod 4).特别地,注意本节常用以下两个假定:(A1)假定在U(p2)中的阶(即|H|)为p的倍数并记|H|=ps(显然,s为偶数,s|p 1).这等价于p1=p1 1(mod p2).(A2)假定2 H.设2=b.由于2是平方元,故1=2p(p1)/2=bp(p1)/2,因此|H|bp(p1)2.注意到|H|2(mod 4),p 7(mod 8),则必有b为偶数.在H中2对的指数本节记为ind(2)=2a,1 6 a 6 ps/2 1.文献3曾讨论H=U(p2)情形下PS的构造,此时假定(A1)和(A2)自然满足.文献3给出了对于任意素数p 7(mod 8),p 2).设R=b0,b1,.,bt1为Hp在Zp中的陪集完全代表系,易知R也形成H在U(p2)中的陪集完全代表系.从而对于任意c U(p2),有Zp2=U(p2)p,2p,.,(p 1)p=(t1i=0biH)(t1i=0bicpHp)=t1i=0bi(H cpHp).(2.1)409周君灵等:可分集与几乎可分集的新构造构造2.1设p 7(mod 8)为素数且满足假定(A1).取定c U(p2),假设在区间0,ps/2 1)上存在3个整数x1 x2(p+3)s4或a(p+1)s4或a(p+3)s4时,在(2.4)中取x=0,l=1,y=3s2,z=a(p3)s4.显然x和z为偶数,y为奇数,且x y z ps2 1.取(x1,x2,x3)=(x,y,z),应用构造2.1与引理2.2即得PS(p2)存在.当a(p1)s4时,在(2.3)中取x=0,l=p12,y=(p1)s2,z=a+(p1)s4.显然x和y为偶数,z为奇数,且x z y(p+1)s4时,在(2.4)中取x=0,l=0,y=s2,z=a(p1)s4.显然x和z为偶数,y为奇数,且x y z ps2 1.取(x1,x2,x3)=(x,y,z),应用构造2.1与引理2.2即得PS(p2)存在.当a(p3)s4时,在(2.3)中取x=0,l=p32,y=(p3)s2,z=a+(p3)s4.显然x和y为偶数,z为奇数,且x z y ps21.取(x1,x2,x3)=(x,z,y),应用构造2.1与引理2.2即得PS(p2)存在.定理2.1设p 7(mod 8)为30,000以内的素数,除去p E的141个可能的例外值,都存在PS(p2),其中E中元素如下:3,5113,5593,9113,9674,1114,1594,3274,4474,4634,6634,8314,9034,9434,9514,9995,0395,2315,3515,5035,5275,5915,7435,8396,0076,3676,6796,7036,7916,8236,8717,1597,5837,5917,6877,7598,1918,2318,3118,5278,5998,6478,8879,1039,1279,1519,3119,3439,8719,967 10,039 10,151 10,27110,391 10,567 10,687 10,847 11,071 11,503 11,527 12,391 12,511 12,799 12,823 13,711 13,75913,831 13,903 13,999 14,551 14,831 14,983 15,319 15,511 15,607 15,671 15,823 15,991 16,18316,231 16,447 16,567 16,831 16,871 16,927 17,047 17,431 17,599 18,311 18,911 19,447 19,54319,727 20,023 20,071 20,431 21,031 21,191 21,751 22,063 22,159 22,303 22,727 22,751 22,80722,871 23,143 23,167 23,431 23,447 23,719 23,767 23,831 23,887 24,103 24,223 24,439 24,84724,919 25,183 25,303 25,423 25,447 25,999 26,711 26,839 27,271 27,487 27,791 27,919 27,94328,463 28,591 28,687 28,711 28,751 29,023 29,191 29,231 29,527 29,863 29,983.证明若p 7(mod 8)且p 3,500,则PS(p2)的存在性可由定理1.2得到.借助计算机可验证:除去E中成员,所有3,50030,000之间模8余7的素数p(共555个)同时满足假定(A1)和(A2)及推论2.1中条件,相关数据参见文献12,表I(包括3,5005,000之间数据,完整列表可联系作者).应用推论2.1可知存在PS(p2).注2.1除去上述定理证明中列举事实,借助计算机,还可验证30,000以内模8余7的总共817个素数中:412中国科学:数学第 53 卷第 2 期(1)只有唯一一例p=31不满足假定(A1);(2)只有唯一一例p=71满足假定(A1)和(A2),但不满足推论2.1中条件,具体地,2=414,=4,626,s=70,a=1,268;(3)3,500以内模8余7的素数中有23个不满足(A2),它们是31、79、103、199、239、487、599、607、751、1,031、1,151、1,279、1,447、1,471、1,879、2,111、2,311、2,647、2,671、2,719、2,887、3,079和3,191.由此可见,应用推论2.1的最大障碍来源于假定(A2).30,000以内模8余7的素数中约20%不满足假定(A2).比较而言,在假定(A2)成立的情形下,推论2.1对于ind(2)的限制条件较容易满足.3构造几乎可分集本节依然令p 7(mod 8)为素数,记2在Zp中的一个平方根为2.本节运算均默认在Zp中进行,并通用记号=1+2,H=,其中,若的乘法阶为偶数,则=;否则=.取定Zp的一个本原根及正整数t(t|p 1).记Zp的子群Ct0=it:0 6 i 6(p t 1)/t,用Cti表示Ct0在Zp中以i为代表元的陪集,即Cti=iCt0,0 6 i 6 t 1,这些称为t次分圆陪集或t次分圆类.显然,Zp的子群H=是一个分圆陪集Ct0,其中t=(p 1)/|H|.本节考虑的都是H对应的分圆类.文献3在只有一个分圆类即H=Zp时给出APS的构造.本节考虑分圆类个数t 1时APS的构造方法.由于p 7(mod 8),故|H|2(mod 4),t为奇数.引理3.1(参见文献3,引理4.1)令p 7(mod 8)为素数且H=Zp.则对于任意 Zp都存在APS(p,2).下述构造主要处理分圆类个数t 1(mod 4)的情形.构造3.1设p 7(mod 8)为素数.取H在Zp陪集的完全代表系R=b0,b1,.,bt1.假设存在,R,使得R可划分成满足以下两个条件的对子集S:(1)x,ySx,y=(R );(2)x,ySx y,x+y=2(R ),则存在APS(p,2).证明设S0=2i1,2i:1 6 i 6|H|24,则易证x,yS0 x,y=(|H|2)/4i=12i1,2i=H 1.由于 ,故1