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 construct almost difference set pairs. In this paper, several new almost difference set pairs are constructed by using cyclotomic classes of order eight.

Keywords:Almost Difference Set Pairs, Cyclotomic Class, Cyclotomic Number

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

荀雅昕，亓万锋

辽宁师范大学数学学院，辽宁 大连

收稿日期：2020年1月25日；录用日期：2020年2月7日；发布日期：2020年2月14日

摘 要

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

关键词 :几乎差集偶，分圆类，分圆数

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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}$ ；

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

表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}$。

文章引用

荀雅昕,亓万锋. 8阶分圆类构造几乎差集偶
Constructions of Almost Difference Set Pairs by Cyclotomic Classes of Order Eight[J]. 应用数学进展, 2020, 09(02): 172-177. https://doi.org/10.12677/AAM.2020.92020

参考文献