8阶分圆类构造几乎差集偶

Constructions of Almost Difference Set Pairs by Cyclotomic Classes of Order Eight

摘要: 几乎差集偶因与几乎最佳二元有序偶紧密相关，在众多问题中应用广泛。分圆类方法是构造几乎差集偶的一种重要方法，本文主要利用8阶分圆类构造几类新的几乎差集偶。

Abstract: Almost difference set pairs are widely used in many problems because they are closely related to almost optimal binary sequence pairs. Cyclotomic classes method is an important method to con-struct almost difference set pairs. In this paper, several new almost difference set pairs are con-structed by using cyclotomic classes of order eight.

1. 引言

具有良好自相关性的序列在雷达、扩频通信、CDMA等众多领域中应用广泛。构造自相关序列可运用差集、差集偶、几乎差集等重要方法。类似于差集、几乎差集的研究，郑鹭亮等人 [1] 提出了几乎差集偶的概念，并研究了几乎差集偶的性质。构造几乎差集偶的一个重要方法是采用分圆类。已有学者利用分圆类构造了许多种类的几乎差集偶，采用二阶分圆类构造几乎差集偶的有申颖 [2]，采用4阶和6阶分圆类构造几乎差集偶的有 [1] [2] [3]，采用8阶分圆类构造了几乎差集偶的有 [4] [5]，采用奇数阶分圆类构造几乎差集偶的有 [6] [7]。黄丹芸 [8] 利用二阶分圆类构造了 $GF\left(q\right)\times GF\left(q\right)$ 上的几乎差集偶。本文利用8阶分圆类构造出几类新的几乎差集偶。

2. 基础知识

我们首先介绍郑鹭亮等人[1]提出的几乎差集偶的概念。

定义1 [1] ：设 $Z_q=\left\{0,1,\cdots ,q-1\right\}$ 为模q剩余类环，U，W分别为 $Z_q$ 的 $k_1$， $k_2$ 元子集，e为U，W中的公共元素的个数。称 $\left(U,W\right)$ 为一个 $\left(q,k_1,k_2,e,\lambda ,t\right)$ 几乎差集偶(almost difference set pairs, ADSP)：如果对t个非零元 $a\in Z_q$，同余方程 $x-y\equiv a\left(\mathrm{mod}q\right)$， $\left(x,y\right)\in U\times W$ 恰有 $\lambda$ 个解，而对于其他 $q-1-t$ 个非零元恰有 $\lambda +1$ 个解。以下把 $\left(q,k_1,k_2,e,\lambda ,t\right)$ 几乎差集偶记为 $\left(q,k_1,k_2,e,\lambda ,t\right)-\text{ADSP}$。

构造几乎差集偶常用分圆方法，下面是有关分圆的基本概念。

定义2 [9] ：设 $q=ef+1$ 是一个奇素数，此时 $Z_q$ 是域。设 $\theta$ 是 $Z_q$ 的一个本原元， $C_0=\langle {\theta }^e\rangle$ 为由 ${\theta }^e$ 生成的 $Z_q^{*}$ 的f阶乘法子群，则 $Z_q^{*}$ 有以下陪集分解

$Z_q^{*}={\displaystyle {\cup }_{i=0}^{e-1}{C}_i}$，

其中 $C_i={\theta }^i{C}_0$， $0\le i\le e-1$，称陪集 $C_i$ 为分圆类。把方程 $y-x\equiv 1\left(\mathrm{mod}q\right)$， $\left(x,y\right)\in C_l\times C_m$ 的解的个数记为 ${\left(l,m\right)}_e$，即 ${\left(l,m\right)}_e=\left|\left(C_l+1\right)\cap C_m\right|$ 称 ${\left(l,m\right)}_e$ 为e阶分圆数，简记为 $\left(l,m\right)$。

3. 8阶分圆类构造几乎差集偶

对有限域 $Z_q$，当 $q=8f+1$ 时，q可分解为 $q=x^2+4y^2=a^2+2b^2$， $x\equiv a\equiv 1\left(\mathrm{mod}4\right)$ [9]。Lehmer [9]指出64个8阶分圆数最多有15个不同的值，称为基本分圆数。表1给出了当f是偶数时64个分圆数与基本分圆数的关系，f是奇数时见 [9]。这15个基本分圆数可以用 $q,x,y,a,b$ 表示，具体依据f是否是偶数以及2是否是 $Z_q$ 中的四次剩余共分为四种情况，本文用到了f是偶数且2不是四次剩余的情况(见表2)，其余请参见 [9]。

黄丹芸 [4] 利用8阶分圆类 $C_0,C_4,C_0\cup \left\{0\right\},C_4\cup \left\{0\right\}$ 、刘晓惠和王金华 [5] 利用8阶分圆类中的 $C_0$ 和 $C_0\cup \left\{0\right\}$ 分别构造了若干几乎差集偶。下面采用8阶分圆类中的四个分圆类或其与{0}的并集构造新的几乎差集偶。

定理1：设奇素数 $q=8f+1=x^2+4y^2=a^2+2b^2$， $x\equiv a\equiv 1\left(\mathrm{mod}4\right)$。令 $U=C_0\cup C_4\cup C_5\cup C_6$， $W=C_0\cup C_1\cup C_2\cup C_4$。 $U^{\prime }=U\cup \left\{0\right\}$， $W^{\prime }=W\cup \left\{0\right\}$，则

1) 当f为偶数且2不是4次剩余，且 $b=-y,x-a=4$ 时，

1、 $\left(U,W\right)$ 构成 $\left(8f+1,4f,4f,2f,2f-1,2f\right)-\text{ADSP}$ ；

Table 1. Relations of cyclotomic numbers of order 8 for even f

表1. f为偶数时8阶分圆数关系 [9]

Table 2. The fifteen basic cyclotomic numbers of order 8 when f is even and 2 is not a quartic residue

表2. f为偶数且2不是四次剩余时8阶分圆数中的15个基本分圆数 [9]

2、 $\left(U^{\prime },W\right)$ 构成 $\left(8f+1,4f+1,4f,2f,2f,6f\right)-\text{ADSP}$ ；

3、 $\left(U,W^{\prime }\right)$ 构成 $\left(8f+1,4f,4f+1,2f,2f,6f\right)-\text{ADSP}$ ；

4、 $\left(U^{\prime },W^{\prime }\right)$ 构成 $\left(8f+1,4f,4f+1,2f+1,2f,2f\right)-\text{ADSP}$。

2) 当f为偶数且2不是4次剩余，且 $b=4-y,x-a=4$ 时， $\left(U,W\right)$ 构成 $\left(8f+1,4f,4f,2f,2f-1,2f\right)-\text{ADSP}$。

证：我们以 $\left(U,W\right)$ 为例进行证明，其余情况类似。

首先易知属于同一个等价类 $C_i$ 中的两个元素 $a_1,a_2$，对应的两个同余方程 $x-y\equiv a_1\left(\mathrm{mod}q\right)$， $x-y\equiv a_2\left(\mathrm{mod}q\right)$ 解的个数一致，因此 $C_i$ 中元素对应的解的个数为 ${\text{Δ}}_i=\left|\left(W+{\theta }^i\right)\cap U\right|=\left|\left(C_0\cup C_1\cup C_2\cup C_4\right)+{\theta }^i\cap \left(C_0\cup C_4\cup C_5\cup C_6\right)\right|,0\le i\le 7$，其中 ${\left(i,j\right)}_e=\left|\left(C_i+1\right)\cap C_j\right|$。从而

$\begin{array}{c}{\text{Δ}}_i=\left|\left(C_0+{\theta }^i\right)\cap C_0\right|+\left|\left(C_0+{\theta }^i\right)\cap C_4\right|+\left|\left(C_0+{\theta }^i\right)\cap C_5\right|+\left|\left(C_0+{\theta }^i\right)\cap C_6\right|\\ +\left|\left(C_1+{\theta }^i\right)\cap C_0\right|+\left|\left(C_1+{\theta }^i\right)\cap C_4\right|+\left|\left(C_1+{\theta }^i\right)\cap C_5\right|+\left|\left(C_1+{\theta }^i\right)\cap C_6\right|\\ +\left|\left(C_2+{\theta }^i\right)\cap C_0\right|+\left|\left(C_2+{\theta }^i\right)\cap C_4\right|+\left|\left(C_2+{\theta }^i\right)\cap C_5\right|+\left|\left(C_2+{\theta }^i\right)\cap C_6\right|\\ +\left|\left(C_4+{\theta }^i\right)\cap C_0\right|+\left|\left(C_4+{\theta }^i\right)\cap C_4\right|+\left|\left(C_4+{\theta }^i\right)\cap C_5\right|+\left|\left(C_4+{\theta }^i\right)\cap C_6\right|\end{array}$

$\begin{array}{l}=\left(-i,-i\right)+\left(-i,4-i\right)+\left(-i,5-i\right)+\left(-i,6-i\right)+\left(1-i,-i\right)+\left(1-i,4-i\right)\\ +\left(1-i,6-i\right)+\left(1-i,5-i\right)+\left(2-i,-i\right)+\left(2-i,4-i\right)+\left(2-i,5-i\right)\\ +\left(2-i,6-i\right)+\left(4-i,-i\right)+\left(4-i,4-i\right)+\left(4-i,5-i\right)+\left(4-i,6-i\right)\end{array}$

当f为偶数且2不是4次剩余时，利用表1和表2可算得：

${\Delta }_0={\Delta }_4=\frac{16q-4x+16y+4a+16b-64}{64}$

${\Delta }_1={\Delta }_5={\Delta }_2={\Delta }_6=\frac{16q+4x-4a-32}{64}$

${\Delta }_3={\Delta }_7=\frac{16q-4x-16y+4a-16b}{64}$

因此 $\left(U,W\right)$ 构成几乎差集偶当且仅当以下3种情况：

① ${\Delta }_0={\Delta }_1,\left|{\Delta }_1-{\Delta }_3\right|=1$，即要满足

$\frac{16q-4x+16y+4a+16b-64}{64}=\frac{16q+4x-4a-32}{64}$

$\left|\frac{16q+4x-4a-32}{64}-\frac{16q-4x-16y+4a-16b}{64}\right|=1$

计算得 $b=-y$， $x=a-4$ 或 $b=4-y$， $x=a+4$。当 $b=-y$， $x=a-4$ 时，由 $x^2+4y^2=a^2+2b^2$ 得 $b^2=4\left(a-2\right)$，则 $a-2$ 应为正，又由 $a=4k+1\left(k\in Z\right)$ 得 $a-2=4\left(k-1\right)+3\left(k\in Z\right)$，所以 $a-2$ 为非完全平方数，与b为整数矛盾，故舍。当 $b=4-y$， $x=a+4$ 时， ${\Delta }_0={\Delta }_1={\Delta }_2={\Delta }_4={\Delta }_5={\Delta }_6=2f$ 且 ${\Delta }_3={\Delta }_7=2f-1$，所以此时 $\left(U,W\right)$ 构成 $\left(8f+1,4f,4f,2f,2f-1,2f\right)-\text{ADSP}$。

② ${\Delta }_0={\Delta }_3,\left|{\Delta }_1-{\Delta }_3\right|=1$，即

$\frac{16q-4x+16y+4a+16b-64}{64}=\frac{16q-4x-16y+4a-16b}{64}$

$\left|\frac{16q+4x-4a-32}{64}-\frac{16q-4x-16y+4a-16b}{64}\right|=1$

计算后可知 $\left(U,W\right)$ 不构成几乎差集偶，具体计算从略。

③ ${\Delta }_1={\Delta }_3,\left|{\Delta }_0-{\Delta }_1\right|=1$，即

$\frac{16q+4x-4a-32}{64}=\frac{16q-4x-16y+4a-16b}{64}$

$\left|\frac{16q-4x+16y+4a+16b-64}{64}-\frac{16q+4x-4a-32}{64}\right|=1$

计算得 $b=-y$ 且 $x=a+4$ 或 $b=4-y$ 且 $x=a-4$。当 $b=4-y$ 且 $x=a-4$ 时， ${\Delta }_1$ 不是整数，故舍去。当 $b=-y$ 且 $x=a+4$ 时， ${\Delta }_1={\Delta }_2={\Delta }_3={\Delta }_5={\Delta }_6={\Delta }_7=2f$ 且 ${\Delta }_0={\Delta }_4=2f-1$，此时 $\left(U,W\right)$ 构成 $\left(8f+1,4f,4f,2f,2f-1,2f\right)-\text{ADSP}$。

用类似定理1的方法，还得到以下结论：

定理2：设奇素数 $q=8f+1=x^2+4y^2=a^2+2b^2$， $x=a\equiv 1\left(\mathrm{mod}4\right)$。令 $U=C_0\cup C_2\cup C_3\cup C_4$， $W=C_0\cup C_4\cup C_6\cup C_7$， $U^{\prime }=U\cup \left\{0\right\}$， $W^{\prime }=W\cup \left\{0\right\}$，则

1) 当f为偶数且2不是4次剩余，且 $b=-y,x-a=4$ 时，

1、 $\left(U,W\right)$ 构成 $\left(8f+1,4f,4f,2f,2f-1,2f\right)-\text{ADSP}$ ；

2、 $\left(U^{\prime },W\right)$ 构成 $\left(8f+1,4f+1,4f,2f,2f,6f\right)-\text{ADSP}$ ；

3、 $\left(U,W^{\prime }\right)$ 构成 $\left(8f+1,4f,4f+1,2f,2f,6f\right)-\text{ADSP}$ ；

4、 $\left(U^{\prime },W^{\prime }\right)$ 构成 $\left(8f+1,4f+1,4f+1,2f+1,2f,2f\right)-\text{ADSP}$。

2) 当f为偶数且2不是4次剩余，且 $b=4-y,x-a=4$ 时， $\left(U^{\prime },W^{\prime }\right)$ 构成 $\left(8f+1,4f+1,4f+1,2f+1,2f,2f\right)-\text{ADSP}$。

定理3：设奇素数 $q=8f+1=x^2+4y^2=a^2+2b^2$， $x\equiv a\equiv 1\left(\mathrm{mod}4\right)$。令 $U=C_0\cup C_1\cup C_2\cup C_6$， $W=C_0\cup C_1\cup C_3\cup C_7$， $U^{\prime }=U\cup \left\{0\right\}$， $W^{\prime }=W\cup \left\{0\right\}$，则

1) 当f为偶数且2不是4次剩余，且 $b=-y,x-a=4$ 时，

1、 $\left(U,W\right)$ 构成 $\left(8f+1,4f,4f,2f,2f-1,2f\right)-\text{ADSP}$ ；

2、 $\left(U^{\prime },W\right)$ 构成 $\left(8f+1,4f+1,4f,2f,2f,6f\right)-\text{ADSP}$ ；

3、 $\left(U,W^{\prime }\right)$ 构成 $\left(8f+1,4f,4f+1,2f,2f,6f\right)-\text{ADSP}$ ；

4、 $\left(U^{\prime },W^{\prime }\right)$ 构成 $\left(8f+1,4f+1,4f+1,2f+1,2f,2f\right)-\text{ADSP}$。

2) 当f为偶数且2不是4次剩余，且 $b=4-y,x-a=4$ 时， $\left(U^{\prime },W\right)$ 构成 $\left(8f+1,4f+1,4f,2f,2f,6f\right)-\text{ADSP}$。

定理4：设奇素数 $q=8f+1=x^2+4y^2=a^2+2b^2$， $x\equiv a\equiv 1\left(\mathrm{mod}4\right)$。令 $U=C_0\cup C_1\cup C_3\cup C_5$， $W=C_0\cup C_2\cup C_3\cup C_6$， $U^{\prime }=U\cup \left\{0\right\}$， $W^{\prime }=W\cup \left\{0\right\}$，则

1) 当f为偶数且2不是4次剩余，且 $b=y,x-a=4$ 时，

1、 $\left(U,W\right)$ 构成 $\left(8f+1,4f,4f,2f,2f-1,2f\right)-\text{ADSP}$ ；

2、 $\left(U^{\prime },W\right)$ 构成 $\left(8f+1,4f+1,4f,2f,2f,6f\right)-\text{ADSP}$ ；

3、 $\left(U,W^{\prime }\right)$ 构成 $\left(8f+1,4f,4f+1,2f,2f,6f\right)-\text{ADSP}$ ；

4、 $\left(U^{\prime },W^{\prime }\right)$ 构成 $\left(8f+1,4f+1,4f+1,2f+1,2f,2f\right)-\text{ADSP}$。

2) 当f为偶数且2不是4次剩余类，且 $b=y-4,x-a=4$ 时， $\left(U^{\prime },W\right)$ 构成。

定理5：设奇素数 $q=8f+1=x^2+4y^2=a^2+2b^2$， $x\equiv a\equiv 1\left(\mathrm{mod}4\right)$。令 $U=C_0\cup C_1\cup C_4\cup C_6$， $W=C_0\cup C_2\cup C_4\cup C_5$， $U^{\prime }=U\cup \left\{0\right\}$， $W^{\prime }=W\cup \left\{0\right\}$，则

1) 当f为偶数且2不是4次剩余， $b=y,x-a=4$ 时，

1、 $\left(U,W\right)$ 构成 $\left(8f+1,4f,4f,2f,2f-1,2f\right)-\text{ADSP}$ ；

2、 $\left(U^{\prime },W\right)$ 构成 $\left(8f+1,4f+1,4f,2f,2f,6f\right)-\text{ADSP}$ ；

3、 $\left(U,W^{\prime }\right)$ 构成 $\left(8f+1,4f,4f+1,2f,2f,6f\right)-\text{ADSP}$ ；

4、 $\left(U^{\prime },W^{\prime }\right)$ 构成 $\left(8f+1,4f+1,4f+1,2f+1,2f,2f\right)-\text{ADSP}$。

2) 当f为偶数且2不是4次剩余，且 $b=y-4,x-a=4$ 时， $\left(U,W\right)$ 构成 $\left(8f+1,4f,4f,2f,2f-1,2f\right)-\text{ADSP}$。

定理6. 设奇素数 $q=8f+1=x^2+4y^2=a^2+2b^2$， $x\equiv a\equiv 1\left(\mathrm{mod}4\right)$。令 $U=C_0\cup C_2\cup C_4\cup C_7$， $W=C_0\cup C_3\cup C_4\cup C_6$， $U^{\prime }=U\cup \left\{0\right\}$， $W^{\prime }=W\cup \left\{0\right\}$，则

1) 当f为偶数且2不是4次剩余，且 $b=y,x-a=4$ 时，

1、 $\left(U,W\right)$ 构成 $\left(8f+1,4f,4f,2f,2f-1,2f\right)-\text{ADSP}$ ；

2、 $\left(U^{\prime },W\right)$ 构成 $\left(8f+1,4f+1,4f,2f,2f,6f\right)-\text{ADSP}$ ；

3、 $\left(U,W^{\prime }\right)$ 构成 $\left(8f+1,4f,4f+1,2f,2f,6f\right)-\text{ADSP}$ ；

4、 $\left(U^{\prime },W^{\prime }\right)$ 构成 $\left(8f+1,4f+1,4f+1,2f+1,2f,2f\right)-\text{ADSP}$。

2) 当f为偶数且2不是4次剩余类，且 $b=y-4,x-a=4$ 时， $\left(U^{\prime },W^{\prime }\right)$ 构成 $\left(8f+1,4f+1,4f+1,2f+1,2f,2f\right)-\text{ADSP}$。

定理1~定理6所列出的ADSP均不能表达为2阶、4阶分圆类的形式，因而是新的。

例1：当 $q=193$ 时，选5作为 $Z_{193}$ 的本原元。 $U=C_0\cup C_4\cup C_5\cup C_6$， $W=C_0\cup C_1\cup C_2\cup C_4$，计算可得 $x=-7,y=6,a=-11,b=-6$， $\left(U,W\right)$ 构成 $\left(193,96,96,48,47,48\right)-\text{ADSP}$。

例2：当 $q=929$ 时，选3作为 $Z_{929}$ 的本原元。 $U=C_0\cup C_1\cup C_3\cup C_5$， $W=C_0\cup C_2\cup C_3\cup C_6$，计算可得 $x=-23,y=-10,a=-27,b=-10$， $\left(U,W\right)$ 构成 $\left(929,464,464,232,231,232\right)-\text{ADSP}$。