广义$\left(n\times m,\left\{3,5\right\},1\right)$完美差族及相关几何正交码

Generalized $\left(n\times m,\left\{3,5\right\},1\right)$ Perfect Difference Families and Related Geometric Orthogonal Codes

摘要: DNA折纸技术在构造纳米材料中起着重要的作用。而几何正交码(GOCs)可以减少DNA折纸中宏键组的错位问题。本文通过确定(n,{3,5},1)完美差族的存在条件，并借助辅助设计与递归构造的方法，得到了广义(n×m,{3,5},1)完美差族的存在条件。又根据几何正交码与广义完美差族之间的等价关系，给出了对应的变重量的完美几何正交码的存在条件。

Abstract: DNA origami technology plays an important role in the construction of nanomaterials. Geometric Orthogonal Codes (GOCs) are used to design macro key groups in DNA origami to reduce its misalignment problems. In this paper, the existence conditions of generalized(n×m,{3,5},1)perfect difference families were determined with the aid of(n,{3,5},1)perfect difference families with auxiliary designs and recursive constructions. Then, the existence conditions of some variable-weight perfect geometric orthogonal codes were obtained from the equivalence relationship of geometric orthogonal codes and generalized perfect difference families.

1. 引言

纳米材料在信息、能源、医药、航空航天等领域具有广阔的应用前景。纳米材料的性能取决于它的结构。DNA折纸术是一种全新的DNA自组装方法，在构造纳米材料方面发挥着重要的作用，通过在DNA折纸技术中放置平头钝端，可以迫使一组DNA折纸通过碱基堆叠粘合以形成预期的排列。如果DNA折纸技术中的宏键组出现错位，将严重影响纳米材料的结构特性。Doty和Winslow [1]在2017年提出几何正交码的概念，介绍了如何使用这类编码设计DNA折纸技术，以此降低宏键组偏差带来的影响，并给出了一类几何正交码码字个数的上下界。Chee等[2]建立了几何正交码与光正交签名码之间的联系，改进了$n=m$ 时几何正交码码字个数的上界，给出了$k\le 5$ 时几类最优几何正交码码字容量的精确值。Wang等[3]进一步研究了$n\ne m,k=3$ 时几何正交码的容量，首次提出可以借助广义完美差填充对几何正交码进行构造。因此，研究广义完美差填充的存在性问题，对几何正交码进行进一步探究有理论意义。本文从$\left(n,\left\{3,5\right\},1\right)$ 完美差族的存在性问题入手，并借助辅助设计与递归构造，确定了部分广义$\left(n\times m,\left\{3,5\right\},1\right)$ 完美差族的存在条件。再根据几何正交码与广义完美差族之间的等价关系，给出了变重量的完美几何正交码的几个存在条件。

2. 预备知识

本节主要介绍广义完美差填充、广义完美差族的定义以及一些已知结果。

定义2.1 令N和M为两个包含0的整数集，且$a\in N$ (或$a\in M$ )时，$-a\in N$ (或$-a\in M$ )。令K为给定的正整数集。对于$N\times M$ 中的任意k元子集B，$k\in K$ ，定义B的差集为：

$\Delta \left(B\right)=\left\{\left(x_1-x_2,y_1-y_2\right):\left(x_1,y_1\right),\left(x_2,y_2\right)\in B,\left(x_1,y_1\right)\ne \left(x_2,y_2\right)\right\}$ .

定义2.2 令$ℬ$ 为$N\times M$ 中的一些大小为$k\left(k\in K\right)$ 的子集(称为基区组)族，若$\Delta ℬ={\displaystyle \underset{B\in ℬ}{\cup }\Delta B}$ 包含$N\times M$ 中的每个元素至多一次，则称$\left(N\times M,ℬ\right)$ 为广义$\left(N\times M,K,1\right)$ -完美差填充(perfect difference packings)，记作广义$\left(N\times M,K,1\right)$ -PDP。称$\left(N\times M\right)\backslash \Delta ℬ$ 为这个差填充的差剩余。若差剩余仅包含$\left(0,0\right)$ ，则称$\left(N\times M,ℬ\right)$ 为广义$\left(N\times M,K,1\right)$ -完美差族(perfect difference family)，记作广义$\left(N\times M,K,1\right)$ -PDF。

设$a,b$ 均为整数，且$a<b$ ，规定$\left[a,b\right]=\left\{a,a+1,\cdots ,b\right\}$ 。对于任意的奇数n，记$\left[n\right]=\left[-\frac{n-1}{2},\frac{n-1}{2}\right]$ 。通常将广义$\left(\left[n\right]\times \left[m\right],K,1\right)$ -PDP (或PDF)记为广义$\left(n\times m,K,1\right)$ -PDP (或PDF)。当$m=1$ 时，一个广义$(n\times m,K,1)$ -PDP (或PDF)记为$\left(n,K,1\right)$ -PDP (或PDF)。

$\left(n,K,1\right)$ -PDP的存在性问题最早由Bermond等[4]在可移动天线的问题中提出，并确定了$\left(n,3,1\right)$ -PDP的存在条件与$k=4,5$ 时，$\left(n,k,1\right)$ -PDP不存在的若干条件。文献[5] [6]给出了$\left(n,3,1\right)$ -PDF存在的充要条件与$k\ge 3$ 时，$\left(n,k,1\right)$ -PDF不存在的条件。文献[7] [8]利用加法置换序列与完美差矩阵，给出了$n\equiv 1\left(\mathrm{mod}12\right)$ 时，$\left(n,4,1\right)$ -PDF的存在条件与$t\le 1000$ 且$t\ne 2,3$ 时，$\left(12t+1,4,1\right)$ -PDF的存在条件。Wu等[9] [10]利用Langford序列讨论了$(n,K,1)$ -PDF不存在的条件及$K=\left\{3,s^{*}\right\},\left\{3,s_1^{*},s_2^{*}\right\}$ 时，$\left(n,K,1\right)$ -PDF的存在条件，其中$s_i^{*}(i=1,2)$ 表示$(n,\{k,s_1^{*},s_2^{*}\},1)$ -PDF中恰好有一个大小为$s_i\left(i=1,2\right)$ 的基区组，且大小为k的基区组的数量大于0。

下面列出几个完美差族的已知结果。

引理2.3 [5] [11]

1) $\left(n,3,1\right)$ -PDF存在当且仅当$n\equiv 1,7\left(\mathrm{mod}24\right)$ ；

2) 当$t=6,8,10$ 时，$\left(20t+1,5,1\right)$ -PDF存在；

3) 当$n\equiv 21\left(\mathrm{mod}40\right)$ 或$n=41,81$ 时，$\left(n,5,1\right)$ -PDF不存在。

引理2.4 [9] $\left(n,\left\{3,5^{*}\right\},1\right)$ -PDF存在当且仅当$n\equiv 9,15\left(\mathrm{mod}24\right)$ 且$n\ge 33$ 。

引理2.5 [3] $\left(n\times m,3,1\right)$ -PDF存在当且仅当$nm\equiv 1\left(\mathrm{mod}6\right)$ 且$n,m\equiv 1,7,17,23\left(\mathrm{mod}24\right)$ 。

2.1. 辅助设计

本节介绍了构造广义完美差族用到的辅助设计。

定义2.1.1 令K为给定的正整数集，若三元组$\left(X,\mathcal{G},ℬ\right)$ 满足：1) X是一个有限点集，X中的元素称为点；2) $\mathcal{G}$ 是X的一种划分，$\mathcal{G}$ 中的元素称为组；3) $ℬ$ 是X的子集(称为区组)族，$ℬ$ 中每个区组的大小均属于K，X中属于不同组的任意元素对恰好属于$ℬ$ 的唯一一个区组中，而属于同一个组的任意元素对不属于任何区组，则称$\left(X,\mathcal{G},ℬ\right)$ 是一个可分组设计(group divisible design)，记作K-GDD。当$K=\left\{k\right\}$ 时，简写为K-GDD。若组集$\mathcal{G}$ 有$u_i$ 个大小为$g_i$ 的组，其中$1\le i\le s$ ，且$\left|X\right|={\displaystyle \sum _{i=1}^s{u}_i{g}_i}$ ，则称$g_1^{u_1}{g}_2^{u_2}\cdots g_s^{u_s}$ 为该可分组设计的型。

定义2.1.2 令S是n阶整数集合，$X=S\times \left[m\right]$ ，$\mathcal{G}=\left\{\left\{i\right\}\times \left[m\right]:i\in S\right\}$ 。令$ℱ$ 为$S\times \left[m\right]$ 的子集(称为基区组)族。对于任意$i,j\in S$ ，$B\in ℱ$ ，定义差集：

${\Delta }_{ij}\left(B\right)=\left\{x-y:\left(i,x\right),\left(j,y\right)\in B,\left(i,x\right)\ne \left(j,y\right)\right\}$ .

若对于任意$i,j\in S$ ，

${\Delta }_{ij}\left(ℱ\right)={\displaystyle \underset{B\in ℱ}{\cup }{\Delta }_{ij}\left(B\right)}=\{\begin{array}{ll}\left[m\right],\hfill & i\ne j\hfill \\ \varnothing ,\hfill & i=j\hfill \end{array}$ ,

则一个点集为$X^{*}=S\times \left[0,m-1\right]$ ，组集为${\mathcal{G}}^{*}=\left\{\left\{i\right\}\times \left[0,m-1\right]:i\in S\right\}$ ，且型为$m^n$ 的K-GDD可以由$ℱ$ 生成，其中$K=\left\{\left|B\right|:B\in ℱ\right\}$ 。对$ℱ$ 中每个基区组中元素的第二个分量$+1\left(\mathrm{mod}m\right)$ 可得到上述型为$m^n$ 的K-GDD的区组集。称这样的设计$ℱ$ 是一个型为$m^n$ 的半完美可分组设计(semi-perfect group divisible design)，记作型为$m^n$ 的K-SPGDD。

定义2.1.3 令K为给定的正整数集，m、n为正整数。若四元组$\left(X,\mathscr{H},\mathcal{G},ℬ\right)$ 满足：1) X是有mn个点的有限点集，X中的元素称为点；2) $\mathcal{G}$ 是X的一种划分，将X划分为n个大小为m的子集，$\mathcal{G}$ 中的元素称为组；3) $\mathscr{H}$ 是X的另一种划分，将X划分为m个大小为n的子集，$\mathscr{H}$ 中的元素称为洞，使得对任意的$H\in \mathscr{H}$ ，$G\in \mathcal{G}$ ，满足$\left|H\cap G\right|=1$ ；4) $ℬ$ 是X的子集(称为区组)族，$ℬ$ 中每个区组的大小均属于K，使得X中取自同组或同洞的点对不出现在$ℬ$ 的任意区组中，X的其他点对恰好出现在$ℬ$ 的唯一一个区组中，则称$\left(X,\mathscr{H},\mathcal{G},ℬ\right)$ 是一个型为$m^n$ 的改进可分组设计(modified group divisible design)，简记为型为$m^n$ 的K-MGDD。

文献[12]-[14]中给出了部分MGDD的如下存在条件。

引理2.1.4 [12]-[14]

1) 型为$m^n$ 的3-MGDD存在当且仅当$n,m\ge 3$ ，$\left(n-1\right)\left(m-1\right)\equiv 0\left(\mathrm{mod}2\right)$ ，且$mn\left(n-1\right)\left(m-1\right)\equiv 0\left(\mathrm{mod}6\right)$ ；

2) 型为$m^n$ 的4-MGDD存在当且仅当$n,m\ge 4$ ，$\left(n-1\right)\left(m-1\right)\equiv 0\left(\mathrm{mod}3\right)$ ，且$\left(n,m\right)\ne \left(4,6\right)$ ；

3) 型为5⁵的5-MGDD存在。

定义2.1.5 令S为有n个点的整数集合，$X=S\times \left[m\right]$ ,$\mathcal{G}=\left\{\left\{i\right\}\times \left[m\right]:i\in S\right\}$ ，$\mathscr{H}=\left\{S\times \left\{x\right\}:x\in \left[m\right]\right\}$ 。令$ℱ$ 为$S\times \left[m\right]$ 的子集(称为基区组)族。对于任意$i,j\in S$ ，$B\in ℱ$ ，定义：

${\Delta }_{ij}\left(B\right)=\left\{x-y:\left(i,x\right),\left(j,y\right)\in B,\left(i,x\right)\ne \left(j,y\right)\right\}$ .

若对于任意$i,j\in S$ ，有：

${\Delta }_{ij}\left(ℱ\right)={\displaystyle \underset{B\in ℱ}{\cup }{\Delta }_{ij}\left(B\right)}=\{\begin{array}{ll}\left[m\right]\backslash \left\{0\right\},\hfill & i\ne j\hfill \\ \varnothing ,\hfill & i=j\hfill \end{array}$ ,

那么一个点集为$X^{*}=S\times \left[0,m-1\right]$ ，组集为${\mathcal{G}}^{*}=\left\{\left\{i\right\}\times \left[0,m-1\right]:i\in S\right\}$ ，洞为${\mathscr{H}}^{*}=\{S\times \left[x\right]:x\in \left[m\right]\}$ 的型为$m^n$ 的K-MGDD可以由$ℱ$ 生成。对$ℱ$ 的每个基区组中元素的第二个分量$+1\left(\mathrm{mod}m\right)$ 可得到上述型为$m^n$ 的K-MGDD的区组集。其中，$K=\left\{\left|B\right|:B\in ℱ\right\}$ 。称$ℱ$ 为型为$m^n$ 的半完美改进可分组设计(semi-perfect modified group divisible design)，简记为型为$m^n$ 的K-SPMGDD。

若$ℱ$ 是$S\times \left[m\right]$ 上型为$m^n$ 的K-SPMGDD，那么$ℱ\cup \left(S\times \left\{0\right\}\right)$ 是一个型为$m^n$ 的$\left(K\cup \left\{n\right\}\right)$ -SPGDD。

2.2. 递归构造

基于以上辅助设计，本节介绍了广义完美差族的主要构造方法。

定义2.2.1 令H₁和H₂为两个整数集合。对于任意的正整数r₁和r₂，定义：

$H_1^{r_1}\times H_2^{r_2}=\left\{\left(r_1{h}_1,r_2{h}_2\right):\left(h_1,h_2\right)\in H_1\times H_2\right\}$ .

对于某些奇正整数$h_i$ ，当$H_i=\left[h_i\right]$ 时，通常将$H_i^{r_i}$ 写作${\left[h_i\right]}^{r_i}$ ，$i=1,2$ 。一个广义$\left(N\times M,K,1\right)$ -PDF可以看作是一个差剩余为${\left[1\right]}^{r_1}\times {\left[1\right]}^{r_2}$ 的广义$\left(N\times M,K,1\right)$ -PDP，其中$r_1,r_2$ 为任意正整数。若存在一个差剩余为$H_1^{r_1}\times H_2^{r_2}$ 的广义$\left(N\times M,K,1\right)$ -PDP，则$H_i$ 中包含0，并且若$a\in H_i$ ，那么$-a\in H_i,i=1,2$ 。

构造2.2.2 [3] 如果存在一个差剩余为$H_1^{r_1}\times H_2^{r_2}$ 的广义$\left(n\times m,K,1\right)$ -PDP与一个差剩余为$T_1^{s_1}\times T_2^{s_2}$ 的广义$\left(H_1\times H_2,L,1\right)$ -PDP，那么存在一个差剩余为$T_1^{r_1{s}_1}\times T_2^{r_2{s}_2}$ 的广义$\left(n\times m,K\cup L,1\right)$ -PDP。并且，若广义$\left(n\times m,K,1\right)$ -PDP为PDF，则广义$\left(n\times m,K\cup L,1\right)$ -PDP是一个广义$\left(n\times m,K\cup L,1\right)$ -PDF。

构造2.2.3 [15] 如果存在一个差剩余为$H^r$ 的$\left(n,K,1\right)$ -PDP与一个型为$m^k$ 的L-SPGDD，其中每一个$k\in K$ ，存在一个差剩余为$H^r\times \left[m\right]$ 的广义$\left(n\times m,L,1\right)$ -PDP。若$\left(n,K,1\right)$ -PDP为PDF，那么$\left(n\times m,L,1\right)$ -PDP的差剩余为$\left\{0\right\}\times \left[m\right]$ 。

构造2.2.4 [15] 如果存在一个$\left(m,K,1\right)$ -PDF与一个型为$k^h$ 的L-MGDD，其中$k\in K$ ，那么存在一个型为$m^h$ 的L-SPMGDD。

3. $\left(n\times m,\left\{3,5\right\},1\right)$ -PDFs

本节将探究广义$\left(n\times m,\left\{3,5\right\},1\right)$ -PDFs的存在条件。首先考虑$m=1$ 的情况，那么$\left(n\times m,\left\{3,5\right\},1\right)$ -PDFs可以由$\left(n,\left\{3,5\right\},1\right)$ -PDFs得到。显然，一个广义$\left(n\times m,3,1\right)$ -PDF是一个广义$\left(n\times m,\left\{3,5\right\},1\right)$ -PDF。

引理3.1 若存在一个$\left(n,\left\{3,5\right\},1\right)$ -PDF，则$n\equiv 1\left(\mathrm{mod}2\right)$ 且$n\notin \left\{3,5,9,11,15,17,23,29,35\right\}$ 。

证 令$\mathcal{A}$ 为一个$\left(n,\left\{3,5\right\},1\right)$ -PDF的区组集，$\mathcal{A}$ 中区组长为3和5的区组的个数分别为x和y。则有：

$6x+20y=n-1.$ (1)

由此得$n\equiv 1\left(\mathrm{mod}2\right)$ 。当$n\in \left\{3,5,9,11,15,17,23,29,35\right\}$ 时，(1)式无非负整数解，对应的$\left(n,\left\{3,5\right\},1\right)$ -PDF不存在。而对于其余情况，等式(1)均存在非负整数解。综上，结论得证。

引理3.2 当$n\equiv 1,7,9,15\left(\mathrm{mod}24\right)$ 且$n\notin \left\{3,5,9,11,13,15,17,19,21,23,27,29,35,37,41,43\right\}$ 时，$(n,\left\{3,5\right\},1)$ -PDF存在。

证 由引理2.3，当$n\equiv 1,7\left(\mathrm{mod}24\right)$ 时，$\left(n,3,1\right)$ -PDF存在，因此$\left(n,\left\{3,5\right\},1\right)$ -PDF也存在。再由引理2.4知，当$n\equiv 9,15\left(\mathrm{mod}24\right)$ 且$n\ge 33$ 时，$\left(n,\left\{3,5^{*}\right\},1\right)$ -PDF存在，因此$\left(n,\left\{3,5\right\},1\right)$ -PDF也存在。当$n\in \left\{13,19,37,43\right\}$ 时，由引理3.1，(1)式都有唯一非负整数解，分别为$\left(2,0\right),\left(3,0\right),\left(6,0\right),\left(7,0\right)$ 。而由引理2.3，$\left(13,3,1\right)$ -PDF、$\left(19,3,1\right)$ -PDF、$\left(37,3,1\right)$ -PDF、$\left(43,3,1\right)$ -PDF均不存在；当$n=21,41$ 时，等式(1)有唯一非负整数解，分别为$\left(0,1\right)$ 和$\left(0,2\right)$ ，但$\left(21,5,1\right)$ -PDF、$\left(41,5,1\right)$ -PDF均不存在。当$n=27$ 时，等式(1)有唯一非负整数解$\left(1,1\right)$ ，但由引理2.4，$\left(27,\left\{3,5^{*}\right\},1\right)$ -PDF不存在。故结论得证。

在下文讨论中，令$Q=\{3,5,9,11,13,15,17,19,21,23,27,29,35,37,41,43\}$ 。

引理3.3 当$m\equiv 1,7,9,15\left(\mathrm{mod}24\right)$ 且$m\notin Q$ 时，型为$m^3$ 和型为$m^5$ 的$\left\{3,5\right\}$ -SPGDD存在。

证 由引理3.2，$m\equiv 1,7,9,15\left(\mathrm{mod}24\right)$ 且$m\notin Q$ 时，$\left(m,\left\{3,5\right\},1\right)$ -PDF存在。由引理2.1.4，$k\in \left\{3,5\right\}$ 时，型为$k^3$ 的$\left\{3,5\right\}$ -MGDD与型为$k^5$ 的$\left\{3,5\right\}$ -MGDD存在。

令$\mathcal{A}$ 为$\left[m\right]$ 上给定的$\left(m,\left\{3,5\right\},1\right)$ -PDF。对于$\mathcal{A}$ 的每一个基区组$A=\left\{x_1,x_2,\cdots ,x_k\right\}$ ，令${ℬ}_A$ 为$\left[0,h-1\right]\times A$ 上的型为$k^h$ 的$\left\{3,5\right\}$ -MGDD，组集为$\left\{\left\{i\right\}\times A:i\in \left[0,h-1\right]\right\}$ ，其中$k,h\in \left\{3,5\right\}$ 。对于每个$B\in {ℬ}_A$ ，令：

${\Delta }_{ij}\left(B\right)=\left\{x-y:\left(i,x\right),\left(j,y\right)\in B,i,j\in \left[0,h-1\right],i\ne j\right\}.$

记$ℬ={\displaystyle \underset{A\in \mathcal{A}}{\cup }{ℬ}_A}$ ，则有：

${\Delta }_{ij}\left(ℬ\right)={\displaystyle \underset{A\in \mathcal{A}}{\cup }{\Delta }_{ij}}\left({ℬ}_A\right)={\displaystyle \underset{A\in \mathcal{A}}{\cup }{\displaystyle \underset{B\in ℬ}{\cup }{\Delta }_{ij}\left(B\right)}=\left[m\right]\backslash \left\{0\right\}},$

其中，$i,j\in \left[0,h-1\right]$ 且$i\ne j$ 。显然，$ℬ$ 是$\left[0,h-1\right]\times \left[m\right]$ 上的型为$m^h$ 的$\left\{3,5\right\}$ -SPMGDD，那么$ℬ\cup \left\{\left[0,h-1\right]\times \left\{0\right\}\right\}$ 是一个型为$m^h$ 的$\left\{3,5\right\}$ -SPGDD，$h\in \left\{3,5\right\}$ 。

引理3.4 当$n,m\equiv 1,7,9,15\left(\mathrm{mod}24\right)$ 且$n,m\notin Q$ 时，差剩余为$\left\{\left\{0\right\}\times \left[m\right]\right\}$ 的广义$\left(n\times m,\left\{3,5\right\},1\right)$ -PDP存在。

证 由引理3.2，当$n\equiv 1,7,9,15\left(\mathrm{mod}24\right)$ 且$n\notin Q$ 时，$\left(n,\left\{3,5\right\},1\right)$ -PDF存在；当$m\equiv 1,7,9,15\left(\mathrm{mod}24\right)$ 且$m\notin Q$ 时，由引理3.3可知，型为$m^3$ 与$m^5$ 的$\left\{3,5\right\}$ -SPGDD存在。

令$\mathcal{A}$ 为$\left[n\right]$ 上给定的$\left(n,\left\{3,5\right\},1\right)$ -PDF。对于$\mathcal{A}$ 中任意一个基区组A，可以构造一个$A\times \left[m\right]$ 上的型为$m^k$ 的$\left\{3,5\right\}$ -SPGDD，组集为$\left\{\left\{i\right\}\times \left[m\right]:i\in A\right\}$ ，基区组集为${ℬ}_A$ ，其中$k\in \left\{3,5\right\}$ 。记$ℬ={\displaystyle \underset{A\in \mathcal{A}}{\cup }{ℬ}_A}$ ，那么：

$\Delta ℬ={\displaystyle \underset{A\in \mathcal{A}}{\cup }\Delta \left({ℬ}_A\right)}={\displaystyle \underset{A\in \mathcal{A}}{\cup }\left(\Delta A\times \left[m\right]\right)}=\left(\left[n\right]\backslash \left\{0\right\}\right)\times \left[m\right]=\left(\left[n\right]\times \left[m\right]\right)\backslash \left(\left\{0\right\}\times \left[m\right]\right)$ .

因此，$ℬ$ 是一个差剩余为$\left\{0\right\}\times \left[m\right]$ 的广义$\left(n\times m,\left\{3,5\right\},1\right)$ -PDP。

定理3.5 当$n,m\equiv 1,7,9,15\left(\mathrm{mod}24\right)$ 且$n,m\notin Q$ 时，广义$\left(n\times m,\left\{3,5\right\},1\right)$ -PDF存在。

证 由引理3.2，当$n,m\equiv 1,7,9,15\left(\mathrm{mod}24\right)$ 且$n,m\notin Q$ 时，$\left(m,\left\{3,5\right\},1\right)$ -PDF存在；由引理3.4，差剩余为$\left\{\left\{0\right\}\times \left[m\right]\right\}$ 的广义$\left(n\times m,\left\{3,5\right\},1\right)$ -PDP存在。

令$\mathcal{A}$ 为$\left[n\right]\times \left[m\right]$ 上差剩余为$\left\{\left\{0\right\}\times \left[m\right]\right\}$ 的广义$\left(n\times m,\left\{3,5\right\},1\right)$ -PDP，$ℬ$ 为给定的$\left(m,\left\{3,5\right\},1\right)$ -PDF。对于$ℬ$ 中的每一个基区组$B=\left\{\left(x_1,y_1\right),\left(x_2,y_2\right),\cdots ,\left(x_i,y_i\right)\right\},i\in \left\{3,5\right\}$ ，构造一个集合：

$C_B=\left\{\left(r_1{x}_1,r_2{y}_1\right),\left(r_1{x}_2,r_2{y}_2\right),\cdots ,\left(r_1{x}_i,r_2{y}_i\right)\right\}$ .

令$\mathcal{C}=\left\{C_B:B\in ℬ\right\}$ ，则：

$\Delta \mathcal{C}={\displaystyle \underset{B\in ℬ}{\cup }\Delta \left(C_B\right)}=\left[m\right]\backslash \left\{0\right\}$ ,

$\Delta \left(\mathcal{A}\cup \mathcal{C}\right)=\left(\Delta \mathcal{A}\cup \Delta \mathcal{C}\right)=\left\{\left(\left[n\right]\times \left[m\right]\right)\backslash \left(\left\{0\right\}\times \left[m\right]\right)\right\}\cup \left(\left[m\right]\backslash \left\{0\right\}\right)=\left(\left[n\right]\times \left[m\right]\right)\backslash \left\{\left(0,0\right)\right\}$ .

显然，$\mathcal{A}\cup \mathcal{C}$ 是一个广义$\left(n\times m,\left\{3,5\right\},1\right)$ -PDF。

定理3.6 当$n,m\equiv 9,15\left(\mathrm{mod}24\right)$ 且$n,m\ge 33$ 时，存在一个广义$\left(n\times m,\left\{3,5\right\},1\right)$ -PDF。

证 由引理2.4，当$n,m\equiv 9,15\left(\mathrm{mod}24\right)$ 且$n,m\ge 33$ 时，$\left(n,\left\{3,5\right\},1\right)$ -PDF与$(m,\left\{3,5\right\},1)$ -PDF存在。由引理3.3，型为$m^3$ 的$\left\{3,5\right\}$ -SPGDD与型为$m^5$ 的$\left\{3,5\right\}$ -SPGDD存在。由引理3.4，差剩余为$\left\{\left\{0\right\}\times \left[m\right]\right\}$ 的广义$\left(n\times m,\left\{3,5\right\},1\right)$ -PDP存在。再结合构造2.2.2，结论得证。

推论3.7 当$m\equiv 1\left(\mathrm{mod}2\right)$ 时，广义$\left(3\times m,\left\{3,5\right\},1\right)$ -PDF不存在。

证 令$m=2t+1$ ，t是整数且$t\ge 1$ 。设一个广义$\left(3\times m,\left\{3,5\right\},1\right)$ -PDF的基区组集为$ℬ$ 。记$ℬ$ 中大小为3的基区组集为${ℬ}_3$ ，大小为5的基区组集为${ℬ}_5$ ，且$\left|{ℬ}_3\right|=x_3$ ，$\left|{ℬ}_5\right|=x_5$ 。那么有：

$6x_3+20x_5=6t+2$ 。 (2)

对每个$B\in ℬ$ ，令$\Delta \left(B_0\right)=\left\{b:\left(0,b\right)\in \Delta B,b>0\right\}$ 。列举基区组的所有可能形式，当$B\in {ℬ}_3$ 时，$\left|\Delta \left(B_0\right)\right|=1$ 或3；当$B\in {ℬ}_5$ 时，$\left|\Delta \left(B_0\right)\right|=4,6$ 或10。记$\Delta \left({ℬ}_0\right)={\displaystyle \underset{B\in ℬ}{\cup }\Delta \left(B_0\right)}$ ，那么$\left|\Delta \left({ℬ}_0\right)\right|=t$ 。

当且仅当$x_5=1+3k,k\ge 0$ 时，等式(2)有非负整数解$\left(x_3,x_5\right)$ 。等式(2)有解时，其形式为$\left(x_3,x_5\right)=\left(\delta ,x_5\right)$ ，其中$\delta =\frac{6t+2-20x_5}{6}$ 。因为$B\in {ℬ}_3$ 时，$\left|\Delta \left(B_0\right)\right|\ge 1$ ；$B\in {ℬ}_5$ 时，$\left|\Delta \left(B_0\right)\right|\ge 4$ ，所以有：

$\left|\Delta \left({ℬ}_0\right)\right|\ge \delta \cdot 1+x_5\cdot 4=\frac{6t+2-20x_5}{6}+\frac{24x_5}{6}=t+\frac{1+2x_5}{3}>t$ ,

与$\left|\Delta \left({ℬ}_0\right)\right|=t$ 矛盾。因此，当$m\equiv 1\left(\mathrm{mod}2\right)$ 时，广义$\left(3\times m,\left\{3,5\right\},1\right)$ -PDF不存在。

推论3.8 当$m\in \left\{5,7,9,11\right\}$ 时，广义$\left(5\times m,\left\{3,5\right\},1\right)$ -PDF不存在。

证 若存在一个广义$\left(n\times m,K,1\right)$ -PDP，则$\left(nm,K,1\right)$ -PDP也存在。但由引理2.3，不存在$\left(35,\left\{3,5\right\},1\right)$ -PDF，故而也不存在广义$\left(5\times 7,\left\{3,5\right\},1\right)$ -PDF。

假设存在一个广义$\left(5\times m,\left\{3,5\right\},1\right)$ -PDF，$m\in \left\{5,11\right\}$ ，基区组集为$ℬ$ 。记$ℬ$ 中大小为3和5的基区组集分别记为${ℬ}_3$ 和${ℬ}_5$ ，且$\left|{ℬ}_3\right|=x_3$ ，$\left|{ℬ}_5\right|=x_5$ 。那么$6x_3+20x_5=5m-1$ 存在非负整数解$\left(x_3,x_5\right)$ 。当$m\in \left\{5,11\right\}$ 时，唯一非负整数解分别为$\left(4,0\right),\left(9,0\right)$ 。由引理2.5可知，$\left(5\times 5,3,1\right)$ -PDF与$\left(5\times 11,3,1\right)$ -PDF不存在，因此当$m\in \left\{5,11\right\}$ 时，广义$\left(5\times m,\left\{3,5\right\},1\right)$ -PDF不存在。

假设当$m=9$ 时存在一个广义$\left(5\times 9,\left\{3,5\right\},1\right)$ -PDF。定义：

$\Delta \left(B_{i,0}\right)=\left\{\left(0,y\right)\in \Delta B:B\in {ℬ}_i,y>0\right\},i=3,5$ ;

$\Delta \left(B_{i,j}\right)=\left\{\left(j,y\right)\in \Delta B:B\in {ℬ}_i\right\},i=3,5,j=1,2$ ;

$\Delta \left({ℱ}_j\right)={\displaystyle \underset{B\in ℬ}{\cup }\Delta }\left(B_{i,j}\right),i=3,5,j=0,1,2$ .

则有$\left|\Delta {\left(ℱ\right)}_0\right|=4$ ，$\left|\Delta {\left(ℱ\right)}_1\right|=\left|\Delta \left({ℱ}_2\right)\right|=9$ 。

通过列举基区组的所有可能形式，有$\left(\left|\Delta \left(B_{3,0}\right)\right|,\left|\Delta \left(B_{3,1}\right)\right|,\left|\Delta \left(B_{3,2}\right)\right|\right)=\left(3,0,0\right)$ 或$\left(1,2,0\right)$ 或$\left(1,0,2\right)$ 或$\left(0,2,1\right)$ ，$\left(\left|\Delta \left(B_{5,0}\right)\right|,\left|\Delta \left(B_{5,1}\right)\right|,\left|\Delta \left(B_{5,2}\right)\right|\right)=\left(10,0,0\right)$ 或$\left(6,4,0\right)$ 或$\left(4,6,0\right)$ 或$\left(4,0,6\right)$ 或$\left(3,4,3\right)$ 或$\left(3,6,1\right)$ 或$\left(2,6,2\right)$ 或$\left(2,4,4\right)$ 。因为$\Delta ℬ=6x_3+20x_5=44$ ，有唯一整数解$\left(x_3,x_5\right)=\left(4,1\right)$ 。又因为$\left|\Delta \left({ℬ}_{3,1}\right)\right|$ 与$\left|\Delta \left({ℬ}_{5,1}\right)\right|$ 均为偶数，与$\left|\Delta \left({ℱ}_1\right)\right|=9$ 矛盾，即整数解$\left(4,1\right)$ 不存在，因此不存在广义$(5\times 9,\left\{3,5\right\},1)$ -PDF。

4. 完美$\left(n\times m,\left\{3,5\right\},1\right)$ 几何正交码

定义4.1 设Z为整数集合，令$n,m,{\lambda }_a,{\lambda }_c$ 为正整数。一个$\left(n\times m,K,{\lambda }_a,{\lambda }_c\right)$ -几何正交码$\mathcal{C}$ ，是$\left[0,n-1\right]\times \left[0,m-1\right]$ 上的组长取自正整数集K的子集(称为码字)族，且满足如下条件：

1) (非周期自相关性)：对任意$B\in \mathcal{C}$ 和每个$\left(s,t\right)\in Z\times Z\backslash \left\{\left(0,0\right)\right\}$ ，$\left|B\cap \left(B+\left(s,t\right)\right)\right|\le {\lambda }_a$ ；

2) (非周期互相关性)：对任意$A,B\in \mathcal{C},A\ne B$ 和每个$\left(s,t\right)\in Z\times Z$ ，$\left|A\cap \left(B+\left(s,t\right)\right)\right|\le {\lambda }_c$ ，

其中，$B+\left(s,t\right)=\left\{\left(x+s,y+t\right):\left(x,y\right)\in B\right\}$ 。

定义4.2 当${\lambda }_a={\lambda }_c=\lambda$ 时，一个$\left(n\times m,K,{\lambda }_a,{\lambda }_c\right)$ -几何正交码(geometric orthogonal codes)，记作$\left(n\times m,K,\lambda \right)$ -GOC。当$\left|K\right|=1$ 时，称其为常重量的几何正交码；当$\left|K\right|>1$ 时，称其为变重量的几何正交码。

定义4.3 令$\mathcal{C}$ 为$\left[0,n-1\right]\times \left[0,m-1\right]$ 上$k\left(k\in K\right)$ 长的子集族。对于任意的$B\in \mathcal{C}$ ，令$\Delta \mathcal{C}={\displaystyle \underset{B\in \mathcal{C}}{\cup }\Delta B}$ 。若$\Delta \mathcal{C}$ 包含$\left[2n-1\right]\times \left[2m-1\right]$ 中每个元素至多一次，则称$\mathcal{C}$ 为一个$\left(n\times m,K,1\right)$ -GOC。当$\Delta \mathcal{C}=\left[2n-1\right]\times \left[2m-1\right]\backslash \left\{\left(0,0\right)\right\}$ 时，则称$\mathcal{C}$ 为一个完美$\left(n\times m,K,1\right)$ -GOC。

Wang等[3]首次提出了广义$\left(n\times m,k,1\right)$ -PDP的概念，借助辅助设计完美差矩阵与幂等正交阵列，确定了$n,m\equiv 17,23\left(\mathrm{mod}24\right)$ 时，广义$\left(n\times m,3,1\right)$ -PDF的存在性。Su等[15]借助半完美可分组设计与半完美改进可分组设计，除部分例外值，确定了$K=\left\{3,4\right\},\left\{3,4,5\right\}$ 时，广义$\left(n\times m,K,1\right)$ -PDF存在的充要条件，同时给出了广义完美差族与完美几何正交码之间的等价关系。

引理4.4 [15]一个完美$\left(n\times m,K,1\right)$ -GOC等价于一个广义$\left(\left(2n-1\right)\times \left(2m-1\right),K,1\right)$ -PDF。

由定理3.5~3.6，推论3.7~3.8及引理4.4，可以得到以下结论。

定理4.5 当$n,m\equiv 1,4,5,8,13,16,17,20\left(\mathrm{mod}24\right)$ 且$n,m\notin \left\{2,3,5,6,7,8,9,10,11,12,14,18,19,21,22\right\}$ 时，存在一个完美$\left(n\times m,\left\{3,5\right\},1\right)$ -GOC。

定理4.6 当$n,m\equiv 5,8,17,20\left(\mathrm{mod}24\right)$ 且$n,m\ge 17$ 时，存在一个完美$(n\times m,\left\{3,5\right\},1)$ -GOC。

定理4.7 当$m\equiv 0,1\left(\mathrm{mod}2\right)$ 时，完美$(2\times m,\left\{3,5\right\},1)$ -GOC不存在。

定理4.8 当$m\in \left\{3,4,5,6\right\}$ 时，完美$(3\times m,\left\{3,5\right\},1)$ -GOC不存在。

基金项目

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

NOTES

^*通讯作者。