型为t^r的5-半循环可分组设计

Semi-Cyclic Group Divisible Design of Type t^r with Block Size 5

摘要: 半循环可分组设计在组合编码中有着广泛的应用。根据半循环可分组设计的定义，给出型为t^r，区组长度为5的半循环可分组设计存在的必要条件。再利用循环差阵、t-正则的循环填充及两种递归构造法，得到了型为tr，区组长度为5的半循环可分组设计存在的若干充分条件。

Abstract: Semi-cyclic group divisible design has many applications in combinatorial coding. The necessary condition of semi-cyclic group divisible design of type t^r with block size 5 was obtained from the definition. In addition, several spectrums of semi-cyclic group divisible design with block size 5 were obtained by employing cyclic difference matrix, t-regular cyclic packing with the aid of two recursive constructions.

1. 引言

设 $r,t$ 和k都是正整数， $I_r=\left\{0,1,2,\cdots ,r-1\right\}$ 且 $Z_t$ 表示模t剩余类加群。令 ${\mathcal{B}}^{*}$ 是点集 $X=I_r\times Z_t$ 的k元子集族(基区组集)。对 $I_r$ 中任意两个整数x和y及 ${\mathcal{B}}^{*}$ 中的k-子集B定义

则 ${\Delta }_{xy}{\mathcal{B}}^{*}=\underset{B\in {\mathcal{B}}^{*}}{\cup }{\Delta }_{xy}B$ ，其中减法模t计算。 ${\Delta }_{xy}{\mathcal{B}}^{*}$ 中的差称为 ${\mathcal{B}}^{*}$ 的 $\left(x,y\right)$ 差。若当 $x\ne y$ 时， ${\Delta }_{xy}{\mathcal{B}}^{*}=Z_t$ ，

否则 ${\Delta }_{xy}{\mathcal{B}}^{*}=\varnothing$ ，则称 $\left(X,\mathcal{G},{\mathcal{B}}^{*}\right)$ 是 $X=I_r\times Z_t$ 上，组集为的一个型为t^r的半循环可分组设计(semi-cyclic group divisible design)，简记为k-SCGDD。

例1 令 $X=I_5\times Z_7$ ， $\mathcal{G}=\left\{\left\{x\right\}\times Z_7:x\in I_5\right\}$ ，则下列7个区组构成型为7⁵的5-SCGDD的基区组：

$\left\{\left(0,0\right),\left(1,0\right),\left(2,0\right),\left(3,0\right),\left(4,0\right)\right\}$ , $\left\{\left(0,1\right),\left(1,2\right),\left(2,3\right),\left(3,4\right),\left(4,0\right)\right\}$ ,

$\left\{\left(0,2\right),\left(1,4\right),\left(2,6\right),\left(3,1\right),\left(4,0\right)\right\}$ , $\left\{\left(0,3\right),\left(1,6\right),\left(2,2\right),\left(3,5\right),\left(4,0\right)\right\}$ ,

$\left\{\left(0,4\right),\left(1,1\right),\left(2,5\right),\left(3,2\right),\left(4,0\right)\right\}$ , $\left\{\left(0,5\right),\left(1,3\right),\left(2,1\right),\left(3,6\right),\left(4,0\right)\right\}$ ,

$\left\{\left(0,6\right),\left(1,5\right),\left(2,4\right),\left(3,3\right),\left(4,0\right)\right\}$ ,

通过对以上七个基区组的每个元素的第二分量加1并模7运算就可以得到型为7⁵的5-SCGDD的所有区组。

半循环可分组设计的定义由Yin J. [1] 提出。半循环可分组设计在其它设计和光正交码的构造中有重要的应用，因此它的存在性和组合构造问题被进行了系统地研究。Gallant R. P.等 [2] 解决了3-SCGDD存在的充要条件。Wang J. [3] 和Wang K. [4] 等给出型为 $m^n$ 的k-SCGDD的递归构造方法，并解决了4-SCGDD

的存在问题。近期，Wang L.等 [5] 给出当p为奇素数，t为正整数时，型为 ${\left(p^r\right)}^{{\left(\frac{p+1}{2}\right)}^t}$ 的 $\frac{p+1}{2}$ -SCGDD的存在条件。

目前关于5-SCGDD还没有独立的研究结果，因此本文对5-SCGDD的存在谱和构造问题进行了研究。首先从半循环可分组设计的定义出发，给出了型为t^r的5-SCGDD存在的必要条件，再借助循环差阵和t-正则循环填充设计及递归构造方法得到了型为t^r的5-SCGDD存在的部分充分条件，所得结果丰富了半循环可分组设计的研究内容。

2. 辅助设计及构造方法

半循环可分组设计的结构与循环差阵、循环填充及平衡不完全区组设计等设计有密切联系，下面给出相关设计的定义。

设 $k,t$ 是正整数。一个循环差阵(CDM)是一个 $k\times t$ 阶矩阵 $A=\left(a_{ij}\right)$ ， $a_{ij}\in Z_t$ ，且任意两行都满足 $\left\{a_{mj}-a_{nj}\left(\mathrm{mod}t\right):0\le j\le t-1\right\}=Z_t$ ，其中 $0\le m$ ， $n\le k-1$ ， $m\ne n$ ，记作 $\left(k,t\right)$ -CDM。

令 $v=rt$ ， $X=Z_{rt}$ ， $\mathcal{A}$ 是X的s个k元子集(基区组)的集合。若 $\Delta \mathcal{A}=\left\{b-a\left(\mathrm{mod}v\right):A_i\in \mathcal{A},a,b\in A_i,a\ne b,1\le i\le s\right\}$ 包含 $Z_{rt}$ 中的每个非零元至多一次，则 $\left(X,\mathcal{A}\right)$ 称为一个循环填充设计，记作CP $\left(k,1;rt\right)$ 。特别地，若 $Z_{rt}\backslash \Delta \mathcal{A}$ 可构成 $Z_{rt}$ 的一个阶为t的加法子群，则CP $\left(k,1;rt\right)$ 又记作t-正则CP $\left(k,1;rt\right)$ 。在文献 [6] 中，t-正则CP $\left(k,1;v\right)$ 也被称作差族，简记为 $\left(v,t,k,1\right)$ -DF。

设 $v,k,\lambda$ 是正整数。一个平衡不完全区组设计，记作BIBD $\left(k,\lambda ;v\right)$ (或B $\left(k,\lambda ;v\right)$ )，是一个二元组 $\left(X,\mathcal{B}\right)$ ，需满足条件：1) $\left|X\right|=v$ ；2) 对任意的 $B\in \mathcal{B}$ ，都有 $\left|B\right|=k$ ；3) X中任意两个不同的元素都恰好包含在λ个区组B中。

半循环可分组设计与以上几个设计之间的关系有如下几个结论。

引理1 [3] 型为t^k的k-SCGDD与 $\left(k,t\right)$ -CDM等价。

引理2 [3] 若t-正则CP $\left(k,1;rt\right)$ 存在，则存在型为t^r的k-SCGDD。

以下是与半循环可分组设计有关的两个递归构造法。

构造法1 [3] 若型为t^r和型为m^k的k-SCGDD都存在，则存在型为 ${\left(tm\right)}^r$ 的k-SCGDD。

构造法2 [3] 若B $\left(k,1;v\right)$ 和型为t^k的k-SCGDD存在，则存在型为t^v的k-SCGDD。

以上两种构造方法具有一定的普适性，有助于我们得到更多类型的半循环可分组设计。

文献 [7] - [13] 中给出关于B $\left(\text{5},\text{1};v\right)$ 、 $\left(5,t\right)$ -CDM和t-正则CP $\left(5,1;rt\right)$ 的存在条件如下：

引理3 [7] 当 $v\equiv 1,5\left(\mathrm{mod}20\right)$ 且 $v\ge 5$ 时，B $\left(\text{5},\text{1};v\right)$ 存在。

引理4 [8] 当t是奇数， $t\ne 3$ 且 $\gcd \left(t,27\right)\ne 9$ 时， $\left(5,t\right)$ -CDM存在；当 $t=9p$ ， $p\in \left\{3,5,7,9,11,13,17,19,23,27,29,31,109\right\}$ 时， $\left(5,t\right)$ -CDM也存在。

引理5 [9] 当 $k\ge 3$ ，t为偶数时， $\left(k,t\right)$ -CDM不存在； $\left(4,9\right)$ -CDM也不存在。

推论1 $\left(5,9\right)$ -CDM不存在。

证明：设A是一个 $\left(k,t\right)$ -CDM。由循环差阵的定义，移除A 任意一行得到一个 $\left(k-1,t\right)$ -CDM；因此，若 $\left(k-1,t\right)$ -CDM不存在，则 $\left(k,t\right)$ -CDM也不存在。由引理5可知， $\left(4,9\right)$ -CDM不存在，故 $\left(5,9\right)$ -CDM也不存在。

引理6 [10] [11] [12] [13] 设 $t,r$ 是正整数，则对下列参数，t-正则CP $\left(5,1;rt\right)$ 存在：

1) 当 $t=5,15$ 或45， $r\equiv 1\left(\mathrm{mod}4\right)$ 是素数且 $r>5$ ；

2)当 $\left(t,r\right)\in \{\left(2,41\right),\left(2,61\right),\left(3,41\right),\left(3,61\right),\left(5,25\right),\left(8,16\right),\left(10,9\right),\left(10,13\right),\left(10,17\right),\left(12,16\right),\left(15,9\right),\left(20,11\right),$ $\left(25,9\right)\}$ ；

3) 当 $t=4$ 或20， $r\equiv 1\left(\mathrm{mod}10\right)$ 是素数且 $r\ne 11$ ；

4) 当 $t=8$ 或12， $r\equiv 11\left(\mathrm{mod}20\right)$ 是素数；

5) 当 $t=60$ ，r是素数且 $r>5$ 。

下面给出利用循环差阵、t-正则循环填充以及递归构造法构造半循环可分组设计的具体例子。

例2 型为5⁵的5-SCGDD存在。

证：一个(5,5)-CDM如矩阵A所示：

$A=\left[\begin{array}{ccccc}0& 2& 4& 3& 1\\ 0& 4& 3& 1& 2\\ 0& 3& 1& 2& 4\\ 0& 1& 2& 4& 3\\ 0& 0& 0& 0& 0\end{array}\right]$ .

可以验证，当 $0\le m$ ， $n\le 4$ ， $m\ne n$ 时，任意两行都满足 $\left\{a_{mj}-a_{nj}\left(\mathrm{mod}5\right):0\le j\le 4\right\}=Z_5$ ，符合循环差阵的定义。令 $I_5=\left\{0,1,2,3,4\right\}$ ， $B_j=\left\{\left(0,a_{0j}\right),\left(1,a_{1j}\right),\left(2,a_{2j}\right),\left(3,a_{3j}\right),\left(4,a_{4j}\right)\right\}$ ，其中 $j=0,1,2,3,4$ ，则 ${\mathcal{B}}^{*}=\left\{B_0,B_1,B_2,B_3,B_4\right\}$ 构成点集 $X=I_5\times Z_5$ 上，组集为的型为5⁵的5-SCGDD的基区组集。

例3 若存在10-正则CP $\left(5,1;9\times 10\right)$ ，则存在型为10⁹的5-SCGDD。

证明：文献 [10] 给出一个10-正则CP $\left(5,1;9\times 10\right)$ 的基区组集 $\mathcal{A}=\left\{A_1,A_2,A_3,A_4\right\}$ ，其中四个区组为 $A_1=\left\{0,1,3,8,58\right\}$ ， $A_2=\left\{0,4,21,51,70\right\}$ ， $A_3=\left\{0,6,16,29,44\right\}$ ， $A_4=\left\{0,11,25,37,59\right\}$ 。

对于任意的 $A=\left\{a_1,a_2,a_3,a_4,a_5\right\}\in \mathcal{A}$ ，令 $a_l=m_l+9n_l$ ， $0\le m_l\le 8$ ， $1\le l\le 5$ ，则得到对应的二元组 $B_A=\left\{\left(m_1,n_1\right),\left(m_2,n_2\right),\left(m_3,n_3\right),\left(m_4,n_4\right),\left(m_5,n_5\right)\right\}$ 。定义 $A^j=\left\{a_1+j,a_2+j,a_3+j,a_4+j,a_5+j\right\}$ 为A的平移，

$j=0,1,\cdots ,8$ 。对的四个区组及它们的平移做上述转换，则 $\mathcal{B}=\left\{B_{A_i^j}|i=1,2,3,4;j=0,1,\cdots ,8\right\}$ 构成点集

$X=I_9\times Z_{10}$ 上，组集为 $\mathcal{G}=\left\{\left\{x\right\}\times Z_{10}:x\in I_9\right\}$ 的型为10⁹的5-SCGDD的基区组集。

例4 若型为7⁵和型为5⁵的5-SCGDD都存在，则型为35⁵的5-SCGDD也存在。

证明：设型为7⁵的5-SCGDD的点集 $X=I_5\times Z_7$ ，组集 $\mathcal{G}=\left\{\left\{x\right\}\times Z_7:x\in I_5\right\}$ ，基区组集 ${\mathcal{B}}^{*}=\left\{B_i|i=1,\cdots ,7\right\}$ 。对任意 $B=\left\{\left(a_0,b_0\right),\left(a_1,b_1\right),\left(a_2,b_2\right),\left(a_3,b_3\right),\left(a_4,b_4\right)\right\}\in {\mathcal{B}}^{*}$ ，由例2，存在点集 $I_5\times Z_5$ 上，组集为，基区组集 ${\mathcal{C}}^{*}=\left\{C_i|i=1,\cdots ,5\right\}$ 的型为5⁵的5-SCGDD。利用构造1，对任意的 $C\in {\mathcal{C}}^{*}$ ， $C=\left\{\left(c_0,d_0\right),\left(c_1,d_1\right),\left(c_2,d_2\right),\left(c_3,d_3\right),\left(c_4,d_4\right)\right\}$ ，做

$D_B=\left\{\left(a_{c_0},b_{c_0}+7d_0\right),\left(a_{c_1},b_{c_1}+7d_1\right),\left(a_{c_2},b_{c_2}+7d_2\right),\left(a_{c_3},b_{c_3}+7d_3\right),\left(a_{c_4},b_{c_4}+7d_4\right)\right\}$ .

再令 ${\mathcal{D}}_B$ 表示这些 $D_B$ 构成的集合，其中 $\left\{\left(c_0,d_0\right),\left(c_1,d_1\right),\left(c_2,d_2\right),\left(c_3,d_3\right),\left(c_4,d_4\right)\right\}$ 取遍 ${\mathcal{C}}^{*}$ 中的5个基区组，则 ${\mathcal{D}}^{*}={\displaystyle {\cup }_{B\in {\mathcal{B}}^{*}}{\mathcal{D}}_B}$ 构成点集 $X=I_5\times Z_{35}$ 上，组集的型为35⁵的5-SCGDD的基区组集。

3. 型为t^r的5-SCGDD的存在条件

这一小节将讨论型为t^r的5-SCGDD的存在条件。

定理1 型为t^r的5-SCGDD存在的必要条件是 $r\ge 5$ ， $\left(r-1\right)t\equiv 0\left(\mathrm{mod}4\right)$ 且 $r\left(r-1\right)t\equiv 0\left(\mathrm{mod}20\right)$ 。

证明：设 $\left(X,\mathcal{G},{\mathcal{B}}^{*}\right)$ 是一个型为t^r的5-SCGDD。由可分组设计的定义，区组中的每个点取自不同的组，故 $r\ge 5$ ；而包含点集中任意一个点x的区组个数为 $r_x=\frac{t\left(r-1\right)}{4}$ ，又 $r_x$ 为正整数，所以 $\left(r-1\right)t\equiv 0\left(\mathrm{mod}4\right)$ 。因为共有rt个点，所有的区组个数为 $b=\frac{t^{2}r\left(r-1\right)}{20}$ ，而每个区组轨道的长为t，所以基区组的个数为 $b^{\ast }=\frac{tr\left(r-1\right)}{20}$ ，因此 $r\left(r-1\right)t\equiv 0\left(\mathrm{mod}20\right)$ 。

定理2 若t是奇数且 $t\ne 3,9$ 或9p，其中p是素数， $p\ge 37$ 且 $p\ne 109$ 时，型为t⁵的5-SCGDD存在。当 $t\in \left\{3,9\right\}$ 或为偶数时，型为t⁵的5-SCGDD不存在。

证明：当 $t=3$ 时， $\left(5,3\right)$ -CDM不存在，由引理1，型为3⁵的5-SCGDD不存在；由引理1、5和推论1，当 $t=9$ 或t是偶数时，型为t⁵的5-SCGDD不存在；当t是奇数且 $\gcd \left(t,27\right)\ne 9$ 以及 $t=9p$ ，p为素数， $3\le p\le 31$ 或 $p=109$ 时，由引理1、4可知，型为t⁵的5-SCGDD存在。下面只需考虑 $t=9p_1{p}_2\cdots p_m$ ， $m\ge 2$ ，其中 $p_i\ge 5$ ， $1\le i\le m$ 是素数的情况。由引理1、4，存在型为 ${\left(3p_1\right)}^5$ 的5-SCGDD和型为 ${\left(3p_2{p}_3\cdots p_m\right)}^5$ 的5-SCGDD，再由构造法1，型为 ${\left(9p_1{p}_2\cdots p_m\right)}^5$ 的5-SCGDD存在。综上，结论得证。

定理3 当t为奇数， $t\ne 3,9$ 或9p， $p\ge 37$ 为素数且 $p\ne 109$ ， $r\equiv 1,5\left(\mathrm{mod}20\right)$ ， $r>5$ 时，型为t^r的5-SCGDD存在。

证明：由引理3，当 $r\equiv 1,5\left(\mathrm{mod}20\right)$ 且 $r\ge 5$ 时，B $\left(5,1;r\right)$ 存在；又由定理2，当t是奇数， $t\ne 3,9$ 或9p， $p\ge 37$ 是素数且 $p\ne 109$ 时，型为t⁵的5-SCGDD存在；再利用构造法2，结论得证。

由引理2、6及定理3易得下面结论。

推论2 当 $t,r$ 满足下列条件之一时，型为t^r的5-SCGDD存在：

1) $\left(t,r\right)\in \left\{\left(3,41\right),\left(3,61\right),\left(15,9\right),\left(25,9\right)\right\}$ ；

2) $t=5,15$ 或45， $r\equiv 9,13,17\left(\mathrm{mod}20\right)$ 是素数。

推论3 当 $m,q$ 为奇数， $m,q\ne 3,9$ 或9p， $p\ge 37$ 为素数且 $p\ne 109$ ，t和r取值为以下情况时，型为 ${\left(tm\right)}^r$ 的5-SCGDD存在：

1) $t=2$ ， $r=41,61$ 且 $m\ne 5q$ ；

2) $t=4$ ， $r\equiv 1\left(\mathrm{mod}10\right)$ 是素数且 $r\ne 11$ ， $m\ne 5q$ ；

3) $t=8$ ， $r\equiv 11\left(\mathrm{mod}20\right)$ 是素数或 $r=16$ ；

4) $t=10$ ， $r=9,13,17,41,61$ ；

5) $t=12$ ， $r\equiv 11\left(\mathrm{mod}20\right)$ 是素数或 $r=16$ ， $m\ne \frac{1}{3}q,\frac{5}{3}q$ 和5q；

6) $t=20$ ， $r\equiv 1\left(\mathrm{mod}10\right)$ 是素数， $m\ne 3q$ ；

7) $t=60$ ， $r>5$ 是素数。

证明：利用构造法1，结合引理2、6和定理2，结论得证。

4. 小结

本文先确定了型为t^r的区组长度为5的半循环可分组设计存在的必要条件，再根据已知的辅助设计，如循环差阵，t-正则循环填充的部分存在条件及两个递归构造方法，给出型为t^r的5-SCGDD存在的若干充分条件，即得到了此半循环可分组设计的无穷类，所得结果对半循环可分组设计及带有AM-OPPTS/PW限制的光正交码的研究工作有一定的理论参考价值。

基金项目

国家自然科学基金青年基金项目(11401326)；无穷维哈密顿系统及其算法应用教育部重点实验室开放课题(2023KFZR03)；内蒙古自治区高等学校科学研究项目(NJZY19021，NJZY22599，NJZY22600)。

NOTES

^*通讯作者。