ABSTRACT

The characteristic sequences of a kind of difference families (DFs) or almost difference families (ADFs) form optical orthogonal codes which have many applications in a code division multiple access communication system. Moreover, either a DF or ADF corresponds to a kind of partially balanced incomplete block designs which arise in many combinatorial and statistical problems. In this paper, we obtain some new DFs and ADFs by cyclotomic classes of order 6.

Keywords:Difference Family, Almost Difference Family, Cyclotomic Classes, Cyclotomic Numbers

一些新的差族和几乎差族

刘永晴¹，孔庆欣²，陆俞先²，汤静¹，王天祎²，唐玲丽^1*

¹大连民族大学理学院预科教育学院，辽宁 大连

²大连民族大学计算机科学与工程学院，辽宁 大连

收稿日期：2020年3月4日；录用日期：2020年3月20日；发布日期：2020年3月27日

摘 要

差族和几乎差族的特征序列可以用来构造多分址码通信系统中的光正交码。另外，差族或几乎差族对应一种部分平衡不完全区块设计，在很多组合和统计问题中有重要应用。本文利用6阶分圆类构造了一些新的差族和几乎差族。

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

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. 引言

在利用光纤作为通道的多分址码通信系统中，光正交码具有广泛的应用，一类差族或几乎差族的特征序列可以用来构造光正交码 [1] [2] [3]。另外，差族或几乎差族作为一种部分平衡不完全区块设计，可以用来解决很多组合和统计问题。差族和几乎差族的概念可以分别看作是差集和几乎差集概念的推广 [4] [5]，几乎差族的概念由Ding等人 [5] 首次提出，他们还给出了一些构造几乎差族的方法。分圆类是一种重要的构造差集、几乎差集及差族的工具 [6] [7]。最近，Dang等人 [8] 又利用2阶和4阶分圆类构造了若干几乎差族。本文在以往学者的研究基础上，利用6阶分圆类构造了一些新的差族和几乎差族。

2. 基础知识

2.1. 差族和几乎差族的定义

设G是一个阶数为v的加法交换群， $B_i\subset G$，且 $\left|B_i\right|=k_i\left(1\le i\le s\right)$，多重集 $\Delta B_i=\left\{a-b:a,b\in B_i,且a\ne b\right\}$。 $\mathcal{F}=\left\{B_1,B_2,\cdots ,B_s\right\}$ 称为一个集族，多重集 $\Delta \mathcal{F}={\displaystyle {\cup }_{i=1}^s\Delta B_i}={\displaystyle {\cup }_{i=1}^s\left\{a-b:a,b\in B_i,且a\ne b\right\}}$。

定义1 [5]：称集族 $\mathcal{F}=\left\{B_1,B_2,\cdots ,B_s\right\}$ 为一个 $\left\{v,\left\{k_1,k_2,\cdots ,k_s\right\},\lambda ,t\right\}$ 几乎差族(Almost Difference Family, ADF)，如果G中有t个非零元素，这些元素中的每一个在 $\text{Δ}\mathcal{F}$ 中出现的次数为 $\lambda$，而对于剩下的 $v-1-t$ 个非零元素，每个元素在 $\text{Δ}\mathcal{F}$ 中出现的次数为 $\lambda +1$。如果 $t=v-1$，则称 $\mathcal{F}=\left\{B_1,B_2,\cdots ,B_s\right\}$ 为一个 $\left\{v,\left\{k_1,k_2,\cdots ,k_s\right\},\lambda \right\}$ 差族(Difference Family, DF)。

由以上定义，不难得到如下结论： $\mathcal{F}=\left\{B_1,B_2,\cdots ,B_s\right\}$ 是一个 $\left\{v,\left\{k_1,k_2,\cdots ,k_s\right\},\lambda ,t\right\}$ -ADF ( $\left\{v,\left\{k_1,k_2,\cdots ,k_s\right\},\lambda \right\}$ -DF)当且仅当对于G中的每一个非零元素g， ${\displaystyle {\sum }_{i=1}^s\left|\left(B_i+g\right)\cap B_i\right|}=\lambda +1$ 或 $\lambda$。

不难验证，当 $\mathcal{F}=\left\{B_1,B_2,\cdots ,B_s\right\}$ 是一个 $\left\{v,\left\{k_1,k_2,\cdots ,k_s\right\},\lambda ,t\right\}$ -ADF时， $t=\left(\lambda +1\right)\left(v-1\right)-{\displaystyle {\sum }_{i=1}^s{k}_i\times \left(k_i-1\right)}$。因此，当我们表示一个ADF时，常将参数t省略。

2.2. 分圆类的相关定义及性质

本文利用分圆类来构造差族和几乎差族，以下给出分圆类及分圆数的定义及性质。

设 $q=ef+1$ 为一个奇素数， $\theta$ 是 $\text{GF}\left(q\right)$ 的一个本原元， $\langle {\theta }^e\rangle =\left\{{\theta }^{ie}:0\le i\le f-1\right\}$ 是由 ${\theta }^e$ 生成的 ${\text{GF}}^{\text{*}}\left(q\right)$ 的乘法子群，它的陪集 $C_j^{\left(e,q\right)}={\theta }^j\langle {\theta }^e\rangle \left(0\le j\le e-1\right)$ 称为在 $\text{GF}\left(q\right)$ 中的e阶分圆类。定义分圆数 ${\left(j,k\right)}_e$ 为方程 $x+1=y,x\in C_j^{\left(e,q\right)},y\in C_k^{\left(e,q\right)}$ 解的个数，即

${\left(j,k\right)}_e=\left|\left(C_j^{\left(e,q\right)}+1\right)\cap C_k^{\left(e,q\right)}\right|.$

下面给出分圆数的性质。

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

2) ${\left(i,j\right)}_e={\left(e-i,j-i\right)}_e=\{\begin{array}{l}{\left(j,i\right)}_e,f为偶数,\\ {\left(j+\frac{e}{2},i+\frac{e}{2}\right)}_e,f为奇数.\end{array}$

3. 六阶分圆类构造差族或几乎差族

3.1. 六阶分圆数

对于每一个素数 $p=6f+1$，p可以被分解为 $p=a^2+3b^2$。设 $\theta$ 是 $\text{GF}\left(p\right)$ 的一个本原元，且 ${\theta }^m=2$。36个分圆数有10个不同的值，这10个值由 $a,b$ 的取值，本原元 $\theta$ 的选取及m的值唯一决定 [9]。以下 ${\left(i,j\right)}_6$ 简写为 $\left(i,j\right)$，$C_j^{\left(6,p\right)}$ 简写为 $C_j$。下面的表1给出了f为奇数时6阶分圆数之间的关系，表2给出了基本的6阶分圆数 [9]。

表1. f为奇数时6阶分圆数之间的关系

表2. f为奇数时10个基本6阶分圆数

3.2. 新的差族和几乎差族

下面我们给出利用6阶分圆类构造得到的差族和几乎差族的结论。

定理1：设奇素数 $p=6f+1=a^2+3b^2$，$a\equiv 1\left(\mathrm{mod}3\right)$，$\theta$ 是 $\text{GF}\left(p\right)$ 的一个本原元，且 ${\theta }^m=2$，则

①当f为奇数， $m\equiv 0\left(\mathrm{mod}3\right)$，且 $a-6b=-2$ 时，

$\left(C_0\cup C_1,C_3\cup C_5\right)$ 是一个 $\left(p,\left\{\frac{p-1}{3},\frac{p-1}{3}\right\},\frac{2p-8}{9}\right)$ -DF;

$\left(C_0\cup C_2,C_0\cup C_1\cup C_5\right)$ 是一个 $\left(p,\left\{\frac{p-1}{3},\frac{p-1}{2}\right\},\frac{13p-43}{36}\right)$ -DF.

②当f为奇数， $m\equiv 1\left(\mathrm{mod}3\right)$，且 $a+3b=7$ 时，

$\left(C_0\cup \left\{0\right\},C_1\cup C_2\right)$ 是一个 $\left(p,\left\{\frac{p+5}{6},\frac{p-1}{3}\right\},\frac{5p-11}{36}\right)$ -DF.

③当f为奇数， $m\equiv 1\left(\mathrm{mod}3\right)$，且 $a+3b=1$ 时，

$\left(C_0\cup \left\{0\right\},C_1\cup C_2\cup \left\{0\right\}\right)$ 是一个 $\left(p,\left\{\frac{p+5}{6},\frac{p+2}{3}\right\},\frac{5p+13}{36}\right)$ -DF.

证明：只证①，②和③类似可证。

设 $x\in C_i\left(0\le i\le 5\right)$，则

$\begin{array}{l}\left|\left(\left(C_0\cup C_1\right)+x\right)\cap \left(C_0\cup C_1\right)\right|\\ =\left|\left(C_0+x\right)\cap C_0\right|+\left|\left(C_0+x\right)\cap C_1\right|+\left|\left(C_1+x\right)\cap C_0\right|+\left|\left(C_1+x\right)\cap C_1\right|\\ =\left(-i,-i\right)+\left(-i,1-i\right)+\left(1-i,-i\right)+\left(1-i,1-i\right)\\ =\left(i,0\right)+\left(i,1\right)+\left(i-1,-1\right)+\left(i-1,0\right).\end{array}$

$\begin{array}{l}\left|\left(\left(C_3\cup C_5\right)+x\right)\cap \left(C_3\cup C_5\right)\right|\\ =\left|\left(C_3+x\right)\cap C_3\right|+\left|\left(C_3+x\right)\cap C_5\right|+\left|\left(C_5+x\right)\cap C_3\right|+\left|\left(C_5+x\right)\cap C_5\right|\\ =\left(3-i,3-i\right)+\left(3-i,5-i\right)+\left(5-i,3-i\right)+\left(5-i,5-i\right)\\ =\left(i-3,0\right)+\left(i-3,2\right)+\left(i-5,-2\right)+\left(i-5,0\right).\end{array}$

令

${\text{Δ}}_i=\left(i,0\right)+\left(i,1\right)+\left(i-1,-1\right)+\left(i-1,0\right)+\left(i-3,0\right)+\left(i-3,2\right)+\left(i-5,-2\right)+\left(i-5,0\right),$

则

$\text{Δ}\left(C_0\cup C_1,C_3\cup C_5\right)={\displaystyle {\cup }_{i=0}^5{\text{Δ}}_i{C}_i}.$

当f为奇数， $m\equiv 0\left(\mathrm{mod}3\right)$ 时，由表1和表2的数据可得

${\text{Δ}}_0={\text{Δ}}_3=-\frac{10}{9}-\frac{a}{9}+\frac{2b}{3}+\frac{2p}{9},$

${\text{Δ}}_1={\text{Δ}}_2={\text{Δ}}_4={\text{Δ}}_5=-\frac{7}{9}+\frac{a}{18}-\frac{b}{3}+\frac{2p}{9}.$

$\left(C_0\cup C_1,C_3\cup C_5\right)$ 为差族，当且仅当 ${\text{Δ}}_0={\text{Δ}}_1$，即 $-\frac{10}{9}-\frac{a}{9}+\frac{2b}{3}+\frac{2p}{9}=-\frac{7}{9}+\frac{a}{18}-\frac{b}{3}+\frac{2p}{9}$。化简，得 $a-6b=-2$，此时，参数 $\lambda =\frac{2p-8}{9}$，所以 $\left(C_0\cup C_1,C_3\cup C_5\right)$ 是一个 $\left(p,\left\{\frac{p-1}{3},\frac{p-1}{3}\right\},\frac{2p-8}{9}\right)$ -DF。

对于集族 $\left(C_0\cup C_2,C_0\cup C_1\cup C_5\right)$，仍然假设

$\text{Δ}\left(C_0\cup C_2,C_0\cup C_1\cup C_5\right)={\displaystyle {\cup }_{i=0}^5{\text{Δ}}_i{C}_i},$

与上面的计算过程类似，可得

${\text{Δ}}_0={\text{Δ}}_2={\text{Δ}}_3={\text{Δ}}_5=-\frac{47}{36}-\frac{a}{18}+\frac{b}{3}+\frac{13p}{36},$

${\text{Δ}}_1={\text{Δ}}_4=-\frac{35}{36}+\frac{a}{9}-\frac{2b}{3}+\frac{13p}{36}.$

要使 $\left(C_0\cup C_2,C_0\cup C_1\cup C_5\right)$ 是差族，当且仅当 ${\text{Δ}}_0={\text{Δ}}_1$，即

$-\frac{47}{36}-\frac{a}{18}+\frac{b}{3}+\frac{13p}{36}=-\frac{35}{36}+\frac{a}{9}-\frac{2b}{3}+\frac{13p}{36}.$

化简，得 $a-6b=-2$。此时，参数 $\lambda =\frac{13p-43}{36}$，所以 $\left(C_0\cup C_2,C_0\cup C_1\cup C_5\right)$ 是一个 $\left(p,\left\{\frac{p-1}{3},\frac{p-1}{2}\right\},\frac{13p-43}{36}\right)$ -DF。证毕。

例如当 $p=16699$，对应的 $a=124,b=21$，此时， $\left(C_0\cup C_1,C_3\cup C_5\right)$ 是一个 $\left(16699,\left\{5566,5566\right\},3710\right)$ -DF， $\left(C_0\cup C_2,C_0\cup C_1\cup C_5\right)$ 是一个 $\left(16699,\left\{5566,8349\right\},6029\right)$ -DF。

定理2：设奇素数 $p=6f+1=a^2+3b^2$，$a\equiv 1\left(\mathrm{mod}3\right)$，$\theta$ 是 $\text{GF}\left(p\right)$ 的一个本原元，且 ${\theta }^m=2$，则

①当f为奇数， $m\equiv 0\left(\mathrm{mod}3\right)$ 时，

若 $a=4$，则 $\left(C_0\cup \left\{0\right\},C_0\cup C_1\cup C_4\right)$ 是一个 $\left(p,\left\{\frac{p+5}{6},\frac{p-1}{2}\right\},\frac{5p-17}{18},\frac{2\left(p-1\right)}{3}\right)$ -ADF， $\left(C_0\cup C_3\cup \left\{0\right\},C_1\cup C_5\right)$ 是一个 $\left(p,\left\{\frac{p+2}{3},\frac{p-1}{3}\right\},\frac{2p-5}{9},\frac{2\left(p-1\right)}{3}\right)$ -ADF；

若 $a=16$，则 $\left(C_0\cup C_3\cup \left\{0\right\},C_1\cup C_5\right)$ 是一个 $\left(p,\left\{\frac{p+2}{3},\frac{p-1}{3}\right\},\frac{2p-8}{9},\frac{p-1}{3}\right)$ -ADF。

②当f为奇数， $m\equiv 1\left(\mathrm{mod}3\right)$ 时，若 $a=-2$，则 $\left(C_0\cup C_1\cup \left\{0\right\},C_1\cup C_5\right)$ 及 $\left(C_0\cup C_2\cup \left\{0\right\},C_0\cup C_3\right)$ 是 $\left(p,\left\{\frac{p+2}{3},\frac{p-1}{3}\right\},\frac{2p-5}{9},\frac{2\left(p-1\right)}{3}\right)$ -ADF；

若 $a=10$，则 $\left(C_0\cup C_2\cup \left\{0\right\},C_0\cup C_3\right)$ 是一个 $\left(p,\left\{\frac{p+2}{3},\frac{p-1}{3}\right\},\frac{2p-8}{9},\frac{p-1}{3}\right)$ -ADF。

③当f为奇数， $m\equiv 2\left(\mathrm{mod}3\right)$ 时，

若 $a-3b=-5$，则 $\left(C_0\cup C_2,C_0\cup C_1\cup C_3\right)$ 是一个 $\left(p,\left\{\frac{p-1}{3},\frac{p-1}{2}\right\},\frac{13p-55}{36},\frac{2\left(p-1\right)}{3}\right)$ -ADF；

若 $a-3b=1$，则 $\left(C_0\cup C_2,C_0\cup C_1\cup C_3\right)$ 是一个 $\left(p,\left\{\frac{p-1}{3},\frac{p-1}{2}\right\},\frac{13p-67}{36},\frac{p-1}{3}\right)$ -ADF；

若 $a=-2$，则 $\left(C_0\cup C_3,C_0\cup C_4\cup \left\{0\right\}\right)$ 是一个 $\left(p,\left\{\frac{p-1}{3},\frac{p+2}{3}\right\},\frac{2p-5}{9},\frac{2\left(p-1\right)}{3}\right)$ -ADF；

若 $a=10$，则 $\left(C_0\cup C_3,C_0\cup C_4\cup \left\{0\right\}\right)$ 是一个 $\left(p,\left\{\frac{p-1}{3},\frac{p+2}{3}\right\},\frac{2p-8}{9},\frac{p-1}{3}\right)$ -ADF。

证明：只证①。设 $x\in C_i\left(0\le i\le 5\right)$，则 $\left|\left(C_0+x\right)\cap C_0\right|=\left(-i,-i\right)=\left(i,0\right)$，所以 $\text{Δ}{C}_0={\displaystyle {\cup }_{i=0}^5\left(i,0\right)C_i}$。当f为奇数时，

$\text{Δ}\left(C_0\cup \left\{0\right\}\right)=\left(\left(0,0\right)+1\right)C_0\cup \left(1,0\right)C_1\cup \left(2,0\right)C_2\cup \left(\left(3,0\right)+1\right)C_3\cup \left(4,0\right)C_4\cup \left(5,0\right)C_5.$

$\begin{array}{l}\left|\left(\left(C_0\cup C_1\cup C_4\right)+x\right)\cap \left(C_0\cup C_1\cup C_4\right)\right|\\ =\left|\left(C_0+x\right)\cap C_0\right|+\left|\left(C_0+x\right)\cap C_1\right|+\left|\left(C_0+x\right)\cap C_4\right|\\ +\left|\left(C_1+x\right)\cap C_0\right|+\left|\left(C_1+x\right)\cap C_1\right|+\left|\left(C_1+x\right)\cap C_4\right|\\ +\left|\left(C_4+x\right)\cap C_0\right|+\left|\left(C_4+x\right)\cap C_1\right|+\left|\left(C_4+x\right)\cap C_4\right|\\ =\left(i,0\right)+\left(i,1\right)+\left(i,4\right)+\left(i-1,-1\right)+\left(i-1,0\right)\\ +\left(i-1,3\right)+\left(i-4,-4\right)+\left(i-4,-3\right)+\left(i-4,0\right).\end{array}$

$\begin{array}{c}\text{Δ}\left(C_0\cup C_1\cup C_4\right)={\displaystyle {\cup }_{i=0}^5(\left(i,0\right)+\left(i,1\right)+\left(i,4\right)+\left(i-1,-1\right)+\left(i-1,0\right)}\\ +\left(i-1,3\right)+\left(i-4,-4\right)+\left(i-4,-3\right)+\left(i-4,0\right))C_i.\end{array}$

令 $\text{Δ}\left(C_0\cup \left\{0\right\},C_0\cup C_1\cup C_4\right)={\displaystyle {\cup }_{i=0}^5{\text{Δ}}_i{C}_i}$，则

$\begin{array}{c}{\text{Δ}}_i=2\left(i,0\right)+\left(i,1\right)+\left(i,4\right)+\left(i-1,-1\right)+\left(i-1,0\right)+\left(i-1,3\right)\\ +\left(i-4,-4\right)+\left(i-4,-3\right)+\left(i-4,0\right)+{\delta }_i,\end{array}$

其中 ${\delta }_i=\{\begin{array}{l}0,i=1,2,4,5,\\ 1,i=0,3.\end{array}$ 由表1和表2，得

${\text{Δ}}_0={\text{Δ}}_3=-\frac{1}{18}-\frac{2a}{9}+\frac{5p}{18},$

${\text{Δ}}_1={\text{Δ}}_4=-\frac{25}{18}+\frac{a}{9}+\frac{5p}{18},$

${\text{Δ}}_2={\text{Δ}}_5=-\frac{7}{18}+\frac{a}{9}+\frac{5p}{18}.$

因为 ${\text{Δ}}_1-{\text{Δ}}_2=-1$，因此 $\left(C_0\cup \left\{0\right\},C_0\cup C_1\cup C_4\right)$ 为几乎差族，当且仅当 ${\text{Δ}}_0={\text{Δ}}_1$ 或 ${\text{Δ}}_0={\text{Δ}}_2$。由 ${\text{Δ}}_0={\text{Δ}}_1$，得 $a=4$。此时，参数 $\lambda =\frac{5p-17}{18},t=\frac{2\left(p-1\right)}{3}$。由 ${\text{Δ}}_0={\text{Δ}}_2$，得 $a=1$，此时 $a\equiv 1\left(\mathrm{mod}3\right)$，舍去。所以，当 $a=4$ 时， $\left(C_0\cup \left\{0\right\},C_0\cup C_1\cup C_4\right)$ 是一个

$\left(p,\left\{\frac{p+5}{6},\frac{p-1}{2}\right\},\frac{5p-17}{18},\frac{2\left(p-1\right)}{3}\right)$ -ADF.

对于集族 $\left(C_0\cup C_3\cup \left\{0\right\},C_1\cup C_5\right)$，仍然假设 $\text{Δ}\left(C_0\cup C_3\cup \left\{0\right\},C_1\cup C_5\right)={\displaystyle {\cup }_{i=0}^5{\text{Δ}}_i{C}_i}$。与上面得计算过程类似，可得

${\text{Δ}}_0={\text{Δ}}_3=\frac{8}{9}-\frac{a}{9}+\frac{2p}{9},$

${\text{Δ}}_1={\text{Δ}}_2={\text{Δ}}_4={\text{Δ}}_5=-\frac{7}{9}+\frac{a}{18}+\frac{2p}{9}.$

$\left(C_0\cup C_3\cup \left\{0\right\},C_1\cup C_5\right)$ 为几乎差族，当且仅当 $\left|{\text{Δ}}_0-{\text{Δ}}_1\right|=1$，即

$\left|\frac{8}{9}-\frac{a}{9}+\frac{2p}{9}+\frac{7}{9}-\frac{a}{18}-\frac{2p}{9}\right|=1.$

化简计算，得 $a=16$ 或 $a=4$。当 $a=4$ 时，参数 $\lambda =\frac{2p-5}{9},t=\frac{2\left(p-1\right)}{3}$，此时， $\left(C_0\cup C_3\cup \left\{0\right\},C_1\cup C_5\right)$ 是一个 $\left(p,\left\{\frac{p+2}{3},\frac{p-1}{3}\right\},\frac{2p-5}{9},\frac{2\left(p-1\right)}{3}\right)$ -ADF。当 $a=16$ 时，参数 $\lambda =\frac{2p-8}{9},t=\frac{p-1}{3}$，此时， $\left(C_0\cup C_3\cup \left\{0\right\},C_1\cup C_5\right)$ 是一个 $\left(p,\left\{\frac{p+2}{3},\frac{p-1}{3}\right\},\frac{2p-8}{9},\frac{p-1}{3}\right)$ -ADF。证毕。

例如，当 $a=4,b=63$ 时， $p=11923$。此时， $\left(C_0\cup \left\{0\right\},C_0\cup C_1\cup C_4\right)$ 是一个 $\left(11923,\left\{1988,5961\right\},3311,7948\right)$ -ADF， $\left(C_0\cup C_3\cup \left\{0\right\},C_1\cup C_5\right)$ 是一个 $\left(11923,\left\{3975,3974\right\},2649,7948\right)$ -ADF。当 $a=16,b=51$ 时， $p=8059$。此时， $\left(C_0\cup C_3\cup \left\{0\right\},C_1\cup C_5\right)$ 是一个 $\left(8059,\left\{2687,2686\right\},1790,2686\right)$ -ADF。

基金项目

大连民族大学校级大学生创新创业训练计划资助项目(201912026456)。

文章引用

刘永晴,孔庆欣,陆俞先,汤 静,王天祎,唐玲丽. 一些新的差族和几乎差族
Some New Difference Families and Almost Difference Families[J]. 应用数学进展, 2020, 09(03): 451-457. https://doi.org/10.12677/AAM.2020.93055

参考文献