差集偶与几乎差集偶的新构造

New Constructions of Difference Set Pairs and Almost Difference Set Pairs

摘要: 具有良好自相关性质的信号序列在众多领域中有广泛的应用。良好的自相关性质可以转化为集合作差后元素出现次数的问题，对此有独特要求的差集偶和几乎差集偶是构造良好的自相关性质信号序列的重要方法。本文使用有限域Z_p中八阶分圆类构造出参数为的(8f+1,2f,2f,0,f/2)差集偶与参数为(8f+1,2f,2f,0,f/2,(f+2)/2)的几乎差集偶，其中奇素数p=8f+1=a²+2b²=(2-a)²+4b²，f是偶数。

Abstract: Signal sequences with good autocorrelation properties are widely used in many fields. Good autocorrelation property can be transformed into the problem of the number of elements after subtraction of two sets. Difference set pairs and almost difference set pairs with the precisely requirements are important methods to construct good autocorrelation signal sequences. Difference set pairs with parameter (8f+1,2f,2f,0,f/2) and almost difference set pairs with parameter (8f+1,2f,2f,0,f/2,(f+2)/2) are constructed by using cyclotomic classes of order eight in finite field Z_p, where p=8f+1=a²+2b²=(2-a)²+4b², and f is an even number.

1. 引言

最佳序列偶因其良好的自相关特性在众多信号设计领域中应用广泛。在构造最佳序列偶的方法中，差集是一种相对简单直接的方法。但差集本身因性质要求强，限制多，构造新的差集往往较为困难。差集偶和几乎差集偶是群中一对特殊子集，因其差集相似多性质，使得其既能用来构造具有良好性质的序列偶，同时差集偶和几乎差集偶在构造时具有更大的灵活度，因而受到许多学者的关注 [1]。本文使用8阶分圆构造出了差集偶，并通过加零元素构造出几乎差集偶。

2. 差集

定义1 [1] 设 $Z_N=\left\{0,1,\cdots ,N-1\right\}$ 是模N的剩余类加群，其中 $U,V$ 是 $Z_N$ 的两个子集，k表示集合U的元素个数， $k^{\prime }$ 表示集合V的元素个数，e表示集合 $U\cap V$ 的元素个数，即 $\left|U\right|=k$， $\left|V\right|=k^{\prime }$， $\left|U\cap V\right|=e$。若对于任意非零元 $g\in Z_N$，方程 $x-y\equiv g\left(\mathrm{mod}N\right)$ 恰有 $\lambda$ 个解对 $\left(x,y\right)\in \left(U,V\right)$，则称 $\left(U,V\right)$ 是 $Z_N$ 上的一个差集偶(Differences set pairs, DSP)，记为 $\left(N,k,k^{\prime },e,\lambda \right)$ -DSP。

例1取 $N=10$， $U=\left\{2,7\right\}$， $V=\left\{2,4,5,6,8\right\}$，则 $\left(U,V\right)$ 是 $Z_{10}$ 上的一个 $\left(10,2,5,1,1\right)$ 差集偶。

3. 几乎差集偶

定义2 [2] 设 $Z_N=\left\{0,1,2,\cdots ,N-1\right\}$ 是模N的剩余类加群，其中 $U,V$ 是 $Z_N$ 的两个子集，k表示集合U的元素个数， $k^{\prime }$ 表示集合V的元素个数，e表示集合 $U\cap V$ 的元素个数，即 $\left|U\right|=k$， $\left|V\right|=k^{\prime }$， $\left|U\cap V\right|=e$。若对于t个非零元 $g\in Z_N$ 都满足 $x-y\equiv g\left(\mathrm{mod}N\right)$ 恰有 $\lambda$ 个解对 $\left(x,y\right)\in \left(U,V\right)$，而对剩余 $N-1-t$ 个非零元恰有 $\lambda +1$ 个解对 $\left(x,y\right)\in \left(U,V\right)$，则称 $\left(U,V\right)$ 是 $Z_N$ 上的一个几乎差集偶(Almost difference set pairs, ADSP)，其参数为 $\left(N,k,k^{\prime },e,\lambda \right)$，简记为 $\left(N,k,k^{\prime },e,\lambda \right)$ -ADSP。

例2取 $N=10$， $U=\left\{0,2,8\right\}$， $V=\left\{2,3,8,9\right\}$，则 $\left(U,V\right)$ 是 $Z_{10}$ 上的一个 $\left(10,3,4,2,1\right)$ 几乎差集偶。

4. 分圆类与分圆数

分圆的概念由Gauss [3] 首次提出，这类分圆称为Gauss经典分圆。之后有学者提出Whiteman-广义分圆 [4] 和Ding-Helleseth广义分圆 [5] 等广义分圆。下面介绍Gauss经典分圆的相关知识。

定义3设 $p=ef+1$，其中p为素数，e，f为正整数，记 $\theta$ 为有限域 $Z_p$ 的一个本原元，定义 $D_0=\langle {\theta }^e\rangle$ 是循环群 $Z_p^{\text{*}}$ 上由 ${\theta }^e$ 生成的f阶乘法子群，称 $D_0$ 及其陪集 $D_i={\theta }^i{D}_0=\left\{{\theta }^{et+i}:t=0,1,\cdots ,f-1\right\},i=0,1,\cdots ,e-1$ 是 $Z_p$ 中e阶分圆类。 $Z_p^{\text{*}}={\displaystyle {\cup }_{i=0}^{e-1}{D}_i}$， $Z_p=Z_p^{\text{*}}\cup \left\{0\right\}$。

设奇素数 $p=ef+1$，当 $e=8$，p满足 $p=x^2+4y^2=a^2+2b^2$，其中 $x\equiv a\equiv 1\left(\mathrm{mod}4\right)$。e阶分圆数定义为 $\left(i,j\right):=\left|D_i\cap \left(D_j+1\right)\right|$。当f取偶数时，共64个分圆数，由分圆数性质知至多有15个独立的分圆数 [6]。表1列出它们的关系。

Table 1. The cyclotomic numbers of order 8 [6]

表1. 八阶分圆数 [6]

表2给出当2是 $Z_p$ 中四次剩余时的15个分圆数的具体形式，表3给出当2是 $Z_p$ 中四次非剩余时的15个分圆数的具体形式。

Table 2. The 15 cyclotomic number when 2 is a quartic residue [6]

表2. 2为四次剩余时15个分圆数具体形式 [6]

Table 3. The 15 cyclotomic number when 2 is not a quartic residue [6]

表3. 2为四次非剩余时15个分圆数的具体形式 [6]

5. 主要结果

下面给出利用八阶分圆类构造的差集偶与几乎差集偶。

定理1设 $p=8f+1$ 为奇素数，f是偶数，且 $p=x^2+4y^2=a^2+2b^2$， $D_i$ 是 $Z_p$ 中的八阶分圆类。令 $U=D_0\cup D_1$， $W=D_4\cup D_5$，则当 $x=2-a,y=b$ 时， $\left(U,W\right)$ 构成了一个 $\left(8f+1,2f,2f,0,f/2\right)$ -DSP。

证明：已知 $\left|U\right|=2f$， $\left|W\right|=2f$，若 $\left(U,W\right)$ 为差集偶，则只需要求元素 ${\theta }^i\in D_i\left(i=0,1,\cdots ,7\right)$ 在 $U,W$ 作差后出现相同的次数，即 ${\Delta }_i=\left|U\cap \left(W+{\theta }^i\right)\right|=\left|\left(D_0\cup D_1\right)\cap \left(\left(D_4\cup D_5\right)+{\theta }^i\right)\right|,i=0,1,\cdots ,7$ 是同一值。

$\begin{array}{c}{\Delta }_i=\left|D_0\cap \left(D_4+{\theta }^i\right)\right|+\left|D_0\cap \left(D_5+{\theta }^i\right)\right|+\left|D_1\cap \left(D_4+{\theta }^i\right)\right|+\left|D_1\cap \left(D_5+{\theta }^i\right)\right|\\ =\left(-i,4-i\right)+\left(-i,5-i\right)+\left(1-i,4-i\right)+\left(1-i,5-i\right)\text{.}\end{array}$

当2是模p的四次剩余时， ${\Delta }_i$ 可作如下表示：

${\Delta }_0=\left(0,4\right)+\left(0,5\right)+\left(1,4\right)+\left(1,5\right)=\left(p+a+x+4y-4b-3\right)/16,$

${\Delta }_1=\left(7,3\right)+\left(1,5\right)+\left(0,3\right)+\left(0,4\right)=\left(p+a+x-4y+4b-3\right)/16,$

${\Delta }_2=\left(6,2\right)+\left(6,3\right)+\left(7,2\right)+\left(7,3\right)=\left(p-a-x+1\right)/16,$

${\Delta }_3=\left(5,1\right)+\left(5,2\right)+\left(6,1\right)+\left(6,2\right)=\left(p-a-x+1\right)/16,$

${\Delta }_4=\left(4,0\right)+\left(4,1\right)+\left(5,0\right)+\left(5,1\right)=\left(p+a+x+4y-4b-3\right)/16,$

${\Delta }_5=\left(3,7\right)+\left(3,0\right)+\left(4,7\right)+\left(4,0\right)=\left(p+a+x-4y+4b-3\right)/16,$

${\Delta }_6=\left(2,6\right)+\left(2,7\right)+\left(3,6\right)+\left(3,7\right)=\left(p-a-x+1\right)/16,$

${\Delta }_7=\left(1,5\right)+\left(1,6\right)+\left(2,5\right)+\left(2,6\right)=\left(p-a-x+1\right)/16.$

显然 ${\Delta }_0={\Delta }_4$， ${\Delta }_1={\Delta }_5$， ${\Delta }_2={\Delta }_3={\Delta }_6={\Delta }_7$。当 ${\Delta }_i\left(i=0,1,\cdots ,7\right)$ 为同一值，即

$\frac{p+a+x+4y-4b-3}{16}=\frac{p+a+x-4y+4b-3}{16}=\frac{p-a-x+1}{16}\text{.}$

时，满足构成差集偶的条件。解得 $x=2-a,y=b$。令 $p=8f+1$， $x=2-a$， $y=b$，带入 ${\Delta }_i$ 中解得 ${\Delta }_i=f/2\left(0\le i\le 7\right)$。令 $x=2-a,y=b$ 带入方程 $p=x^2+4y^2=a^2+2b^2$，解出相应的丢番图方程，得 $x=-2k^2+1$， $y=-2k$， $p=4k^4+12k^2+1$， $k\in Z$。

类似的，当2是模p的四次非剩余时， ${\Delta }_0={\Delta }_1={\Delta }_4={\Delta }_5=\left(p-a-x-3\right)/16$， ${\Delta }_2={\Delta }_6=\left(p+a-4b+x+4y\right)/16$， ${\Delta }_3={\Delta }_7=\left(p+a+4b+x-y+1\right)/16$。当 ${\Delta }_i\left(i=0,1,\cdots ,7\right)$ 为同一值即

$\frac{p-a-x-3}{16}=\frac{p+a-4b+x+4y+1}{16}=\frac{p+a+4b+x-4y+1}{16}\text{.}$

时，满足构成差集偶的条件。解方程得 $x=-2-a,y=b$。令 $p=8f+1$， $x=-2-a$， $y=b$，带入 ${\Delta }_i$ 中解得 ${\Delta }_i=f/2,\left(0\le i\le 7\right)$。令 $x=-2-a,y=b$ 带入方程 $p=x^2+4y^2=a^2+2b^2$，解出相应的丢番图方程得 $x=2k^2-1$， $y=-2k$， $p=4k^4+12k^2+1\left(k\in Z\right)$。

综上所述，当f是偶数， $U=D_0\cup D_1$， $W=D_4\cup D_5$， $\left(U,W\right)$ 构成 $\left(8f+1,2f,2f,0,f/2\right)$ -DSP。

例3当 $q=113,k=-2,x=-7,y=4,a=9,b=4$，此时2模p为四次剩余，3是 $Z_{113}$ 的本原元。

$\begin{array}{c}U=D_0\cup D_1\\ =\left\{7,49,4,28,83,16,112,106,64,109,85,30,97,1,21,34,12,84,23,48,110,92,79,101,29,90,65,3\right\},\end{array}$

$\begin{array}{c}W=D_4\cup D_5\\ =\left\{2,14,98,8,56,53,32,111,99,15,105,57,60,81,6,42,68,24,55,46,96,107,71,45,89,58,67,17\right\}\text{.}\end{array}$

则 $\left(U,W\right)$ 构成 $\left(113,28,28,0,7\right)$ -DSP。

例4当 $k=-5$ 时， $p=2801,x=49,y=-10,a=-51,b=-10$，此时2是四次非剩余，3是 $Z_{2801}$ 的本原元。 $U=D_0\cup D_1$， $W=D_4\cup D_5$。则 $\left(U,W\right)$ 构成 $\left(2801,700,700,0,175\right)$ -DSP。

推论1设 $p=8f+1$ 为奇素数，f是偶数， $p=x^2+4y^2=a^2+2b^2$，其中 $x=2-a$， $y=b$， $x,y,a,b\in Z$。令 $U=D_0\cup D_1\cup \left\{0\right\}$， $W=D_4\cup D_5$。则 $\left(U,W\right)$ 构成了一个 $\left(8f+1,2f+1,2f,0,f/2\right)$ -ADSP。

证明：证明 $\left(U,W\right)$ 为几乎差集偶的过程与定理1的证明过程类似。

$\begin{array}{c}{\Delta }_i=\left|D_0\cap \left(D_4+{\theta }^i\right)\right|+\left|D_0\cap \left(D_5+{\theta }^i\right)\right|+\left|D_1\cap \left(D_4+{\theta }^i\right)\right|+\left|D_1\cap \left(D_5+{\theta }^i\right)\right|+\left|\left\{0\right\}\cap \left(D_4+{\theta }^i\right)\right|+\left|\left\{0\right\}\cap \left(D_5+{\theta }^i\right)\right|\\ =\left(-i,4-i\right)+\left(-i,5-i\right)+\left(1-i,4-i\right)+\left(1-i,5-i\right)+\left|\left\{0\right\}\cap \left(D_{4-i}+1\right)\right|+\left|\left\{0\right\}\cap \left(D_{5-i}+1\right)\right|\text{.}\end{array}$

由f是偶数可知 $-1\in D_0$，故 $i=4$ 时， $\left|\left\{0\right\}\cap \left(D_{4-i}+1\right)\right|=1$， $i=5$ 时， $\left|\left\{0\right\}\cap \left(D_{5-i}+1\right)\right|=1$。

当2是模p的四次剩余时 ${\Delta }_i$ 可作如下表示：

${\Delta }_0=\left(0,4\right)+\left(0,5\right)+\left(1,4\right)+\left(1,5\right)=\left(p+a+x+4y-4b-3\right)/16,$

${\Delta }_1=\left(7,3\right)+\left(1,5\right)+\left(0,3\right)+\left(0,4\right)=\left(p+a+x-4y+4b-3\right)/16,$

${\Delta }_2=\left(6,2\right)+\left(6,3\right)+\left(7,2\right)+\left(7,3\right)=\left(p-a-x+1\right)/16,$

${\Delta }_3=\left(5,1\right)+\left(5,2\right)+\left(6,1\right)+\left(6,2\right)=\left(p-a-x+1\right)/16,$

${\Delta }_4=\left(4,0\right)+\left(4,1\right)+\left(5,0\right)+\left(5,1\right)+1=\left(p+a+x+4y-4b+13\right)/16,$

${\Delta }_5=\left(3,7\right)+\left(3,0\right)+\left(4,7\right)+\left(4,0\right)+1=\left(p+a+x-4y+4b+13\right)/16,$

${\Delta }_6=\left(2,6\right)+\left(2,7\right)+\left(3,6\right)+\left(3,7\right)=\left(p-a-x+1\right)/16,$

${\Delta }_7=\left(1,5\right)+\left(1,6\right)+\left(2,5\right)+\left(2,6\right)=\left(p-a-x+1\right)/16.$

可知当 ${\Delta }_0={\Delta }_1={\Delta }_2={\Delta }_3={\Delta }_4-1={\Delta }_5-1={\Delta }_6={\Delta }_7$。满足构成几乎差集偶的构造条件

$\frac{p+a+x+4y-4b-3}{16}=\frac{p+a+x-4y+4b-3}{16}=\frac{p-a-x+1}{16}\text{.}$

解方程得 $x=2-a,y=b$。令 $p=8f+1,x=2-a,y=b$，带入 ${\Delta }_i$ 中解得 ${\Delta }_i=f/2,\left(0\le i\le 7\right)$。令 $x=2-a,y=b$ 带入方程 $p=x^2+4y^2=a^2+2b^2$，解出相应丢番图方程得 $x=-2k^2+1$， $y=-2k$， $p=4k^4+12k^2+1$， $k\in Z$。

当2是模p的四次非剩余时，方程满足构成几乎差集偶的条件为

$\frac{p+a-4b+x+4y+1}{16}=\frac{p+a+4b+x-4y+1}{16}=\frac{p-a-x-3}{16}\text{.}$

解方程得 $x=2-a,y=b$。令 $p=8f+1,x=2-a,y=b$，带入 ${\Delta }_i$ 中解得 ${\Delta }_i=f/2,\left(0\le i\le 7\right)$，令 $x=-a-2,y=b$ 带入方程 $p=x^2+4y^2=a^2+2b^2$，解出相应丢番图方程得 $x=2k^2-1$， $y=-2k$， $p=4k^4+12k^2+1$， $k\in Z$。

综上所述，当f是偶数， $U=D_0\cup D_1\cup \left\{0\right\}$， $W=D_4\cup D_5$， $\left(U,W\right)$ 构成 $\left(8f+1,2f,2f,0,f/2\right)$ -ADSP。

例5当 $k=-2$ 时， $p=113$，2模p为四次剩余，3是 $Z_{113}$ 本原元。

$\begin{array}{c}U=D_0\cup D_1\cup \left\{0\right\}\\ =\left\{7,49,4,28,83,16,112,106,64,109,85,30,97,1,21,34,12,84,23,48,110,92,79,101,29,90,65,3,0\right\},\end{array}$

$\begin{array}{c}W=D_4\cup D_5\\ =\left\{2,14,98,8,56,53,32,111,99,15,105,57,60,81,6,42,68,24,55,46,96,107,71,45,89,58,67,17\right\}\text{.}\end{array}$

则 $\left(U,W\right)$ 构成 $\left(113,28,28,0,7\right)$ -ADSP。

例6当 $k=5$ 时， $p=2801$，2模p为四次非剩余，3是 $Z_{2801}$ 本原元。记 $U=D_0\cup D_1\cup \left\{0\right\}$， $W=D_4\cup D_5$。则 $\left(U,W\right)$ 构成 $\left(2801,700,700,0,175\right)$ -ADSP。

6. 结论

利用有限域中的8阶分圆类构造了新的差集偶和几乎差集偶，所采用的分圆类组合与 [7] 中不同。有关它的其他性质还需要进一步研究。另外尝试将其应用在最佳离散信号、序列偶等理想信号的构造中。

基金项目

国家自然科学基金(No. 61502217)，辽宁省教育厅科研项目(LQ2020020)。

NOTES

^*通讯作者E-mail: q [e-mail]