基于分圆类方法差集偶和几乎差集偶的构造

Construction of Difference Set Pairs and Almost Difference Set Pairs Based on Cyclotomic Class Method

摘要: 在通信系统研究中，性能良好的信号序列具有较强的应用价值。利用差集偶和几乎差集偶理论，设计理想序列是一种有效的数学方式。本文利用有限域F_q中8阶经典分圆类的方法，构造出新的差集偶和几乎差集偶。

Abstract: In the research of communication system, signal sequences with good performances have strong application value. Using the theory of difference set pair and almost difference set pair to design the ideal sequence is an effective mathematical method. In this paper, we construct new difference set pairs and almost difference set pairs by using the method of classical cyclotomic class of order eight in finite fields.

1. 引言

现如今，社会各领域对最佳离散信号需求量大幅增加。理想序列作为具有良好自相关特性的离散信号，在近几年受到了广泛的关注，差集偶和几乎差集偶对理想序列的研究设计，也成为了该领域的一个重要突破方向。但由于差集偶和几乎差集偶的现有数量无法满足实际工程需求，学者们则主要通过特征多项式法 [1] [2]、基于乘子定理与乘子猜想理论推导法 [3] 以及分圆类组合法 [4] [5] 对二者进行了构造。本文在Gauss经典分圆相关内容的基础上，利用基本分圆数算出各组合中的差函数列表，结合计算机编程求出q的取值并验证，最终得到了 $\left(8f+1,2f,2f,0,f/2\right)$ -DSP、 $\left(8f+1,2f+1,2f,0,f/2,6f\right)$ -ADSP。

2. 基本概念和主要定理

分圆是一个具有多年研究历史的基础数学问题，《算术研究》 [6] 这本书首次提出了Gauss经典分圆的内容，随后学者们为构造差集又提出了Whiteman广义分圆类 [7] 和Ding-2阶广义分圆 [8] 等。下面只给出经典分圆的相关定义。

定义1 (分圆类) [9] 设 $q=ef+1\left(e\ge 2,f\ge 2\right)$ 为素数幂， $F_q$ 是以 $\theta$ 为本原元的q阶有限域， $\omega ={\theta }^i$，令

$D_i^e=\left\{{\theta }^i,{\theta }^i\omega ,{\theta }^i{\omega }^2,\cdots ,{\theta }^i{\omega }^{f-1}\right\}$， $0\le i\le e-1$，

则称 $D_0^e,D_1^e,\cdots ,D_{e-1}^e$ 为 $F_q$ 上的e阶分圆类。

注：本文在书写过程中将8阶经典分圆类简记为 $D_0,D_1,\cdots ,D_7$。

定义2 (分圆数)设 $q=ef+1\left(e\ge 2,f\ge 2\right)$ 为素数幂，方程 $y-x\equiv 1\left(\mathrm{mod}q\right)$， $\left(x,y\right)\in D_l\times D_m$， $0\le l,m\le e-1$ 解的个数记为 ${\left(l,m\right)}_e$，即 ${\left(l,m\right)}_e=\left|\left(D_l^e+1\right)\cap D_m^e\right|$，称 ${\left(l,m\right)}_e$ 为e阶分圆数。

分圆数的相关性质如下 [9] ：

1) ${\left(l,m\right)}_e={\left(l^{\prime },m^{\prime }\right)}_e$，其中 $l^{\prime }\equiv l\left(\mathrm{mod}e\right)$， $m^{\prime }\equiv m\left(\mathrm{mod}e\right)$，

2) ${\left(l,m\right)}_e={\left(e-l,m-l\right)}_e$，

3) ${\left(l,m\right)}_e=\{\begin{array}{l}{\left(l,m\right)}_e,当f为偶数,\\ \left(m+e/2,l+e/2\right),当f为奇数;\end{array}$

4) ${\displaystyle {\sum }_{m=0}^{e-1}{\left(l,m\right)}_e}=\{\begin{array}{l}f-1,当-1\in D_l^e,\\ f,其他;\end{array}$

5) ${\displaystyle {\sum }_{m=0}^{e-1}\left(l,m\right)}=\{\begin{array}{l}f-1,当m=0,\\ f,当m\ne 0;\end{array}$

6) 令 $g\in D_m^e$，当f为偶数时， $\left|\left\{0\right\}\cap \left(D_l^e+g\right)\right|=\{\begin{array}{l}1,l=m,\\ 0,其他;\end{array}$

7) 令 $g\in D_m^e$，当f为奇数时， $\left|\left\{0\right\}\cap \left(D_l^e+g\right)\right|=\{\begin{array}{l}1,l=\left(m+\frac{e}{2}\right)\left(\mathrm{mod}e\right),\\ 0,其他.\end{array}$

本文主要通过8阶分圆类对差集偶和几乎差集偶进行构造。当 $q=8f+1$ 为奇素数，且 $q=x^2+4y^2=a^2+2b^2$， $x,y,a,b\in Z$， $x\equiv a\equiv 1\left(\mathrm{mod}4\right)$ 时，结合分圆数的运算性质得到8阶分圆类下的15个基本分圆数。随着2模p是否为四次剩余和f奇偶性的不同情况，8阶分圆类下的15个基本分圆数则以变量 $q,x,y,a,b$ 的不同形式表达。

表1是当f为偶数时的8阶分圆数值，表2是2为模p的四次剩余和非四次剩余时基本分圆数的表示情况，其余情况见Lehmer [10] 文章中作详细叙述。

Table 1. When f is an even number, the 8th order cyclotomic number ( l , m ) 8

表1. 当f为偶数，8阶分圆数 ${\left(l,m\right)}_8$

Table 2. When f is an even number, the 8th order basic cyclotomic number

表2. 当f为偶数，8阶基本分圆数

定义3 (差函数)设 $\left(G,+\right)$ 是N阶Abel群，D是群G的K阶子集，称 $d_{D\left(\omega \right)}=\left|D\cap \left(D+\omega \right)\right|$ 为G中的差函数，其中 $D+\omega =\left\{x+\omega :x\in D\right\}$。

定义4 (差集偶)设 $U,W$ 分别是有限域 $F_q$ 的两个子集，且 $\left|U\right|=k_1$， $\left|W\right|=k_2$， $U,W$ 中共有e个公共元素，若对 $F_q$ 中任意一个非零元a，方程 $x-y\equiv a\left(\mathrm{mod}q\right)$， $\left(x,y\right)\in \left(U,W\right)$ 恰有 $\lambda$ 个解，则称 $\left(U,W\right)$ 为 $F_q$ 上的一个 $\left(q,k_1,k_2,e,\lambda \right)$ 差集偶，简记 $\left(q,k_1,k_2,e,\lambda \right)$ -DSP。

显然，当 $\left(q,k_1,k_2,e,\lambda \right)$ -DSP存在时， $q,k_1,k_2,e,\lambda$ 各参数之间有如下等式

$k_1\cdot k_2=\lambda \left(q-1\right)+e.$

令 $\bar{U}=F_q-U$, $\bar{W}=F_q-W$，则有：

$\left(\bar{U},V\right)$ 构成 $\left(q,q-k_1,k_2,k_2-e,k_2-\lambda \right)$ -DSP；

$\left(U,\bar{V}\right)$ 构成 $\left(q,k_1,k_2,k_1-e,k_1-\lambda \right)$ -DSP；

$\left(\bar{U},\bar{V}\right)$ 构成 $\left(q,q-k_1,q-k_2,q-k_1-k_2+e,q-k_1-k_2+\lambda \right)$ -DSP。

定义5 (几乎差集偶)设 $U,W$ 分别是 $F_q$ 的两个子集，且 $\left|U\right|=k_1$， $\left|W\right|=k_2$， $U,W$ 中共有e个公共元素,若对 $F_q$ 中任意一个非零元a，方程 $x-y\equiv a\left(\mathrm{mod}q\right)$， $\left(x,y\right)\in \left(U,W\right)$ 恰有 $\lambda$ 个解，对其他 $\left(q-1-t\right)$ 个非零元有 $\lambda +1$ 个解，则称 $\left(U,W\right)$ 为 $F_q$ 上的一个 $\left(q,k_1,k_2,e,\lambda ,t\right)$ 几乎差集偶，简记 $\left(q,k_1,k_2,e,\lambda ,t\right)$ -ADSP。

显然，当 $\left(q,k_1,k_2,e,\lambda ,t\right)$ -ADSP存在时， $q,k_1,k_2,e,\lambda$ 各参数之间有如下等式

$k_1{k}_2=\lambda t+\left(\lambda +1\right)\left(q-1-t\right)+e.$

令 $\bar{U}=F_q\backslash U$， $\bar{W}=F_q\backslash W$，则有：

$\left(U,\bar{V}\right)$ 构成 $\left(q,q-k_1,q-k_2,k_1-e,\lambda ,t\right)$ -ADSP；

$\left(\bar{U},\bar{V}\right)$ 构成 $\left(q,q-k_1,q-k_2,q-k_1-k_2-e,\lambda ,t\right)$ -ADSP；

$\left(\bar{U},V\right)$ 构成 $\left(q,q-k_1,q-k_2,k_2-e,\lambda ,t\right)$ -ADSP。

3. 利用8阶分圆类构造新的差集偶与几乎差集偶

就目前研究情况来看，已有学者利用分圆类方法构造了部分差集偶和几乎差集偶。孙彩锋 [4]、许成谦 [11]、李建周 [12] 等人利用2阶分圆类构造出了性能较好的差集偶，如 $\left(4f+2,2f+1,2f,f,f\right)$ 、 $\left(4f+1,2f,2f,0,f\right)$ 等；段晓贝 [13]、杨小红 [14]、申颖 [15] 等人利用4阶和6阶分圆类得到了多种不同参数形式的差集偶和几乎差集偶，如 $\left(4f+1,f+1,f+1,1,\left(f+2\right)/4\right)$ 、 $\left(4f+1,2f,2f+1,0,f,2f\right)$ 、 $\left(6f+1,3f,3f+1,0,3f/2,3f\right)$ 等；贾国彦 [16]、张立超 [17] 等人利用8阶分圆类构造了几类效能较高的差集偶，如 $\left(8f+1,6f,2f+1,2f,\left(3f+1\right)/2\right)$ 、 $\left(8f+1,6f+1,2f,2f,3f/2\right)$ 等。利用分圆类法构造差集偶与几乎差集偶普遍以2阶、4阶、6阶为主，基于8阶分圆类构造研究成果相对较少，鉴于此本文将展开对8阶分圆类构造差集偶的研究。

定理1设 $q=8f+1$ 为奇素数，且 $q=x^2+4y^2=a^2+2b^2$，其中 $x\equiv a\equiv 1\left(\mathrm{mod}4\right)$， $x,y,a,b\in Z$， $D_i\left(0\le i\le 7且i\in Z\right)$ 是 $F_q$ 上的8阶分圆类。令 $U=D_0\cup D_3$， $W=D_4\cup D_7$，则 $\left(U,W\right)$ 构成了一个 $\left(8f+1,2f,2f,0,f/2\right)$ -DSP。

证明：奇素数 $q=8f+1$，对 $F_q$ 中任意非零元 $\alpha ={\theta }^k$ 在 $D_l,D_m\left(0\le l,m\le 7\right)$ 两集合中以差形式出现的次数可用 $\left|\left(D_l+{\theta }^k\right)\cap D_m\right|$ 表示，方程 $y-x\equiv {\theta }^i\left(\mathrm{mod}q\right)$， $x\in U$， $y\in W$ 解的个数则可以记为 ${\Delta }_i=\left|\left(W+{\theta }^i\right)\cap U\right|$。显然有 $k_1=\left|U\right|=2f$， $k_2=\left|W\right|=2f$，要证明 $\left(U,W\right)$ 为差集偶,则需要证明任意元素 $a\in D_i\in F_q$，在 $\left(U,W\right)$ 中出现的次数相同，即 ${\Delta }_i=\left|\left(W+{\theta }^i\right)\cap U\right|=\left|\left(D_4\cup D_7\right)+{\theta }^i\cap \left(D_0\cup D_3\right)\right|$ 的值相同，从而有：

$\begin{array}{c}{\Delta }_i=\left|\left(D_4+{\theta }^i\right)\cap D_0\right|+\left|\left(D_4+{\theta }^i\right)\cap D_3\right|+\left|\left(D_7+{\theta }^i\right)\cap D_0\right|+\left|\left(D_7+{\theta }^i\right)\cap D_3\right|\\ =\left(4-i,-i\right)+\left(4-i,3-i\right)+\left(7-i,-i\right)+\left(7-i,3-i\right).\end{array}$

结合8阶分圆数表1和表2，当2不是四次剩余时 ${\Delta }_i$ 可作如下表示：

${\Delta }_0=\left(0,4\right)+\left(1,5\right)+\left(0,7\right)+\left(1,4\right)=\left(4q-4a-4x-12\right)/64,$

${\Delta }_1=\left(1,4\right)+\left(1,6\right)+\left(1,2\right)+\left(2,4\right)=\left(4q+4a+4x+16y+16b+4\right)/64,$

${\Delta }_2=\left(2,4\right)+\left(1,2\right)+\left(1,3\right)+\left(1,5\right)=\left(4q+4a+4x-16b-16y+4\right)/64,$

${\Delta }_3=\left(1,5\right)+\left(0,1\right)+\left(1,4\right)+\left(0,4\right)=\left(4q-4a-4x-12\right)/64,$

${\Delta }_4=\left(0,4\right)+\left(0,7\right)+\left(1,5\right)+\left(1,4\right)=\left(4q-4a-4x-12\right)/64,$

${\Delta }_5=\left(1,4\right)+\left(1,2\right)+\left(1,6\right)+\left(2,4\right)=\left(4q+4a+4x+16y+16b+4\right)/64,$

${\Delta }_6=\left(2,4\right)+\left(1,3\right)+\left(1,2\right)+\left(1,5\right)=\left(4q+4a+4x-16b-16y+4\right)/64,$

${\Delta }_7=\left(1,5\right)+\left(1,4\right)+\left(0,1\right)+\left(0,4\right)=\left(4q-4a-4x-12\right)/64,$

可知 ${\Delta }_0={\Delta }_3={\Delta }_4={\Delta }_7,{\Delta }_1={\Delta }_5,{\Delta }_2={\Delta }_6$。

若使 $\left(U,W\right)$ 构成 $F_q$ 中的差集偶，则要求 ${\Delta }_0={\Delta }_1={\Delta }_2$，即：

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

结合 $q=x^2+4y^2=a^2+2b^2$ 计算可得 $b=-y$， $x=-a-2$，其中 $x=8k^2+8k+1$， $y=4k+2$， $\left(k\in Z\right)$， ${\Delta }_i=f/2$， $\left(0\le i\le 7且i\in Z\right)$。因此， $\left(U,W\right)$ 构成 $\left(8f+1,2f,2f,0,f/2\right)$ -DSP。

推论1设 $q=8f+1$ 为奇素数， $D_i\left(0\le i\le 7且i\in Z\right)$ 是 $F_q$ 上的8阶剩余类，令 $U^{\prime }=D_0\cup D_3\cup \left\{0\right\}$， $W=D_4\cup D_7$。则 $\left(U^{\prime },W\right)$ 构成了一个 $\left(8f+1,2f+1,2f,0,f/2,6f\right)$ -ADSP。

例1 设 $q=8f+1$， $U=D_0\cup D_3$， $W=D_4\cup D_7$，取 $b=-y$， $x=-a-2$ 且 $x=8k^2+8k+1$， $y=4k+2\left(k\in Z\right)$。当计算当 $k=1$ 时， $x=17$， $y=6$， $a=-19$， $b=-6$， $q=433$ 时，10是 $F_{433}$ 的本原元，则 $U,W$ 可分别表示为

$\begin{array}{c}U=D_0\cup D_3\\ =\{9,16,17,20,21,22,26,27,29,31,48,50,51,59,60,63,66,76,78,81,83,87,93,94,424,417,350,\\ 97,98,107,112,113,119,134,137,139,142,144,150,151,153,154,161,164,172,177,426,416,\\ 1,180,182,184,189,190,198,199,205,228,234,235,243,244,249,251,253,256,261,269,430,\\ 3,272,279,280,282,283,289,291,294,296,299,314,320,321,326,335,336,339,340,346,432,\\ 7,352,355,357,367,370,373,374,382,383,385,402,404,406,407,411,412,413\},\end{array}$

$\begin{array}{c}W=D_4\cup D_7\\ =\{4,5,12,15,19,28,36,41,43,45,46,57,61,64,68,70,74,80,84,85,88,101,103,104,106,108,109,\\ 110,115,116,121,123,124,129,130,135,138,143,146,158,167,169,171,178,179,181,183,192,\\ 193,197,200,204,210,211,222,223,229,233,236,240,241,250,252,254,255,262,264,266,\\ 275,287,290,295,298,303,304,309,310,312,317,318,323,324,325,327,329,330,332,345,\\ 348,349,353,359,363,365,369,372,376,387,388,390,392,397,405,414,418,421,428,429\}.\end{array}$

$\left(U,W\right)$ 构成了 $\left(433,108,108,0,27\right)$ -DSP。

4. 结束语

本文对8阶分圆类构造差集偶和几乎差集偶所产生的大量组合进行筛选，整理出符合要求的新组合形式。利用8阶基本分圆数计算出各组差函数列表，结合理论知识证明得到了参数为 $\left(8f+1,2f,2f,0,f/2\right)$ 的差集偶，并给出例证及推论。文章研究结果对差集偶和几乎差集偶的现存实例进行了扩充，对理想序列和序列偶的构造提供了基础有效的数学工具。

基金项目

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

NOTES

^*通讯作者。