几乎差集是由Ding等人^[1]提出的, 利用它可以构造具有3级自相关性的二元序列(binary sequence with three-level auto-correlation)^[2], 而且有好的自相关性的二元序列有十分广泛的应用^[3].本文将几乎差集的定义推广到几乎差集偶, 并讨论其部分性质.

定义1  设$Z_N=\{0, 1, \cdots, N-1\}$为模$N$剩余类环, $U, V$分别为$Z_N$的$k_1, k_2$元子集, $h$为$U, V$中公共元素的个数.称$(U, V)$为一个$(N, k_1, k_2, h, \lambda, t)$几乎差集偶(almost difference set pair):如果对$t$个非零元$a\in Z_N$, 同余方程$x-y\equiv a({\rm mod} \ N), x, y\in U\times V$恰有$\lambda$个解, 而对于其它$N-1-t$个非零元恰有$\lambda+1$个解.

以下把$(N, k_1, k_2, h, \lambda, t)$几乎差集偶记为$(N, k_1, k_2, h, \lambda, t)$-ADSP.

几乎差集偶的另一个等价定义为:

定义2  设$Z_N=\{0, 1, \cdots, N-1\}$为模$N$剩余类环, $U, V$分别为$Z_N$的$k_1, k_2$元子集, $h$为$U, V$中公共元素的个数.称$(U, V)$为一个$(N, k_1, k_2, h, \lambda, t)$几乎差集偶(almost difference set pair):当非零元$a \in A$时, $|(U+a)\bigcap V|=\lambda$; 当非零元$a \in B$时, $|(U+a)\bigcap V|=\lambda +1$, 其中$Z_N=\{0 \} \bigcup A\bigcup B, |A|=t, |B|=N-1-t$.

当$U=V$时, 几乎差集偶为几乎差集^[2].

从几乎差集偶的定义容易得到以下性质：

性质1  若存在$(N, k_1, k_2, h, \lambda, t)$-ADSP, 则$k_1 k_2=h+\lambda t+(\lambda +1)(N-1-t).$

设$U=\{u_1, u_2, \cdots, u_{k_1} \}$, $V=\{v_1, v_2, \cdots, v_{k_2} \}$, 令$H_U(x)={\sum\limits_{i\in U} }x^i$, $H_V(x)={\sum\limits_{i\in V}} x^i$, 称$H_U(x), H_V(x)$分别为$U, V$的Hall多项式.

性质2  设$U=\{u_1, u_2, \cdots, u_{k_1} \}$, $V=\{v_1, v_2, \cdots, v_{k_2} \}$, 则$(U, V)$构成$(N, k_1, k_2, h, \lambda, t)$-ADSP当且仅当

$ H_U(x)H_V(x^{-1})=h+ \lambda{\sum\limits_{i\in A}}x^i+(\lambda+1){\sum\limits_{i\in B}}x^i~~ ({\rm mod} \ {x^N}-1), $

其中$A\cup B=Z_N\setminus \{0\}, \mid A \mid =t, \mid B \mid =N-1-t$.

性质3  设$(U, V)$构成$(N, k_1, k_2, h, \lambda, t)$-ADSP, 则

(1) $(U+\tau, V+\tau), (qU, qV)$为$(N, k_1, k_2, h, \lambda, t)$-ADSP, 其中$\tau, q\in Z_N$且$(q, N)=1$.

(2) $\overline{U}=Z_N\setminus U, \overline{V}=Z_N\setminus V, (\overline{U}, \overline{V})$构成$(N, N-k_1, N-k_2, N-k_1-k_2+h, \lambda, t)$-ADSP.

构造几乎差集常用分圆方法, 下面是有关分圆的一些基本概念^[4].

设$N=ef+1$是一个奇素数, 此时$Z_N$构成域.设$\theta$是$Z_N$的一个本原元, $D_0=\langle\theta^e\rangle$为由${\theta^e}$生成的${Z_N}^*$的$f$阶乘法子群, 则${Z_N}^*$有以下陪集分解

$ {Z_N}^*={\bigcup\limits_{i=0}^{e-1}}D_i, $

其中$D_i=\theta ^i D_0, 0\leq i\leq e-1$, 称陪集$D_i$为分圆类.把方程$y-x\equiv 1({\rm mod} N)$, $(x, y)\in D_l\times D_m$的解的个数记为$(l, m)_e$, 即$(l, m)_e=\mid (D_l+1)\cap D_m\mid$称$(l, m)_e$为$e$阶分圆数.

下面先介绍分圆数的性质, 方便后面计算.

(1)$(i^{'}, j^{'})=(i, j)$, 其中$i^{'}\equiv i({\rm mod} \ e)$, $j^{'}\equiv j({\rm mod} \ e)$.

(2)$(i, j)=(e-i, j-i)$.

(3)$(i, j)=\left\{ \begin{array}{ll} (j, i), & 2\mid f, \\ (j+\frac {e}{2}, i+\frac {e} {2}), & 2\nmid f. \end{array}\right.$

(4)$\sum\limits_{j=0}^{e-1}(i, j)=\left\{ \begin{array}{ll} f-1, & i=0 {\hbox且}2\mid f {\hbox {或者}} i=\frac{e}{2} {\hbox且}2\nmid f, \\ f, & 2\nmid f {\hbox{其他}}. \end{array}\right.$

(5) $\sum\limits_{i=0}^{e-1}(i, j)=\left\{ \begin{array}{ll} f-1, & j=0, \\ f, & j\neq {0}. \end{array}\right.$

定理1  设$N=ef+1$为奇素数, $U=D_0\cup D_1\cup D_2\cup \cdots \cup D_ {e-1}, V=D_j(0\leq j \leq {e-1})$, 则$U, V$构成$(ef+1, ef, f, f, f-1, f)$-ADSP.

证  记$\Delta _i=\mid (U+\theta ^i)\cap V \mid, 0\leq i \leq {e-1}$, 则

$ \begin{eqnarray*}\Delta_i&=&\mid (D_0+\theta^i)\cap D_j \mid +\mid (D_1+\theta^i)\cap D_j \mid+\cdots+\mid (D_ {e-1}+\theta^i)\cap D_j \mid\\ &=&\mid (D_{-i}+1)\cap D_ {j-i} \mid+\mid (D_{1-i}+1)\cap D_ {j-i} \mid+\cdots+\mid (D_{e-1-i}+1)\cap D_ {j-i} \mid. \end{eqnarray*} $

注意到$(l, m)_e=\mid (D_l+1)\cap D_m\mid$, 从而

$ \Delta _i=\sum\limits_{k=0}^{e-1}(k-i, j-i)=\left\{ \begin{array}{ll} f-1, &i=j, \\ f,&i\neq {j}, \end{array}\right. $

所以$(U, V)$构成$(ef+1, ef, f, f, f-1, f)$-ADSP.

以下考虑利用4阶分圆类构造几乎差集偶.先给出4阶分圆数, 这些分圆数由$N=4f+1$的分解式$N=x^2 +4y^2, x\equiv1({\rm mod} \ 4)$唯一决定^[4].

(1) 当$f$是偶数时, 这些分圆数关系由表 1给出

其中$A=\frac{1}{16}(N-11-6x), $ $B=\frac{1}{16}(N-3+2x+8y), $ $C=\frac{1}{16}(N-3+2x), $ $D=\frac{1}{16}(N-3+2x-8y), $ $E=\frac{1}{16}(N+1-2x)$.

(2) 当$f$是奇数时, 这些分圆数关系由表 2给出

其中$A=\frac{1}{16}(N-7+2x), $ $B=\frac{1}{16}(N+1+2x-8y), $ $C=\frac{1}{16}(N+1-6x), $ $D=\frac{1}{16}(N+1+2x+8y), $ $E=\frac{1}{16}(N-3-2x)$.

定理2  设奇素数$N=4f+1=x^2+4y^2, x\equiv1({\rm mod} \ 4), U=D_0, V=D_2. $

(1) 当$f$为偶数时, $(U, V)$构成$(4f+1, f, f, 0, \frac{f-2}{4}, 2f)$-ADSP, 当且仅当$\mid x-1 \mid=4 $.

(2) 当$f$为奇数时, 仅当$x=1, y=\pm 1$, $(U, V)$构成$(5, 1, 1, 0, 0, 3)$-ADSP.

证  记$\Delta _i=\mid (D_0+\theta ^i)\cap D_2 \mid, 0\leq i \leq 3$, 注意到$(l, m)_e=\mid (D_l+1)\cap D_m\mid$, 从而

$ \Delta _i=\mid (D_{-i}+1)\cap D_{2-i} \mid=(-i, 2-i)=(i, 2), \quad i=0, 1, 2, 3. $

(1) 当$f$为偶数时, 由表 1可得

$ \begin{eqnarray*}&&\Delta _{0}=(0, 2)=\frac{1}{16}(N-3+2x), \ \ \Delta_{1}=(1, 2)=\frac{1}{16}(N+1-2x), \\ && \Delta _{2}=(2, 2)=\frac{1}{16}(N-3+2x), \ \ \Delta_{3}=(3, 2)=\frac{1}{16}(N+1-2x).\end{eqnarray*} $

即$\Delta_{0}=\Delta_{2}, \Delta_{1}=\Delta_{3}$, 从而$(U, V)$构成一个几乎差集偶且$\mid \Delta _{0}-\Delta _{1} \mid=1$即$\mid x-1 \mid=4$.仔细计算参数后可知$(U, V)$构成$(4f+1, f, f, 0, \frac{f-2}{4}, 2f)$-ADSP.

(2) 当$f$为奇数时, 由表 2可得

$ \begin{eqnarray*}&&\Delta_{0}=(0, 2)=\frac{1}{16}(N+1-6x), \ \ \Delta_{1}=(1, 2)=\frac{1}{16}(N+1+2x+8y), \\ &&\Delta_{2}=(2, 2)=\frac{1}{16}(N-7+2x), \Delta_{3}=(3, 2)=\frac{1}{16}(N+1+2x-8y), \end{eqnarray*} $

因而$\Delta_{1} \neq \Delta_{3}, $否则$y=0$与$N$为奇素数矛盾.如果$\Delta_{0}=\Delta_{1}$且$\Delta_{2}=\Delta_{3}$, 经计算没有合适$x, y$, 因此$(U, V)$不构成几乎差集.如果$\Delta_{0}=\Delta_{1}=\Delta_{2}$得$(N+1-6x)=(N+1+2x+8y)=(N-7+2x)$, 解得$x=1, y=-1$.此时, $(U, V)$构成$(5, 1, 1, 0, 0, 3)$-ADSP.如果$\Delta_{0}=\Delta_{2}=\Delta_{3}$得$(N+1-6x)=(N-7+2x)=(N+1+2x-8y)$, 解得$x=1, y=1$.此时, $(U, V)$构成$(5, 1, 1, 0, 0, 3)$-ADSP.

例1  当$x=5, y=2$时, $N=41, U=D_0=\{ \pm1, \pm4, \pm10, \pm16, \pm18 \}, V=D_2=\{ \pm2, \pm5, \pm8, \pm9, \pm20 \}$构成$(41, 10, 10, 0, 2, 20)$-ADSP.

定理3  设奇素数$N=4f+1=x^2+4y^2, x\equiv1(\rm mod \ 4)$, $U=D_0\cup D_1\cup D_3, V=D_0.$

(1) 当$f$为偶数时,

(a)$(U, V)$构成$(4f+1, 3f, f, f, \frac{3f-2}{4}, 3f)$-ADSP, 当且仅当$x=-3$.

(b) $(U, V)$构成$(4f+1, 3f, f, f, \frac{3f-4}{4}, 3f)$-ADSP, 当且仅当$x=1 $.

(2) 当$f$为奇数时, $(U, V)$不构成几乎差集.

证  记$\Delta _i=\mid ((D_0\cup D_1\cup D_3)+\theta ^i)\cap D_0 \mid, 0\leq i \leq 3$, 注意到$(l, m)_e=\mid (D_l+1)\cap D_m\mid$, 从而

$ \begin{eqnarray*}\Delta _i&=&\mid (D_0+\theta ^i)\cap D_0\mid+\mid (D_1+\theta ^i)\cap D_0\mid+\mid (D_3+\theta ^i)\cap D_0\mid\\ &=&\mid (D_{-i}+1)\cap D_{-i}\mid+\mid (D_{1-i}+1)\cap D_{-i}\mid+\mid (D_{3-i}+1)\cap D_{-i}\mid\\ &=&(-i, -i)+(1-i, -i)+(3-i, -i)\\ &=&(i, 0)+(3+i, 3)+(1+i, 1).\end{eqnarray*} $

(1) 当$f$为偶数时, 由表 1可得

$ \begin{eqnarray*}&&\Delta _{0}=(0, 0)+(3, 3)+(1, 1)=\frac{1}{16}(3N-17-2x), \\ &&\Delta _{1}=(1, 0)+(0, 3)+(2, 1)=\frac{1}{16}(3N-5+2x), \\ &&\Delta _{2}=(2, 0)+(1, 3)+(3, 1)=\frac{1}{16}(3N-1-2x), \\ &&\Delta _{3}=(3, 0)+(2, 3)+(0, 1)=\frac{1}{16}(3N-5+2x).\end{eqnarray*} $

即$\Delta_1=\Delta_3, \Delta_0-\Delta_2=-1.$

(a)如果$\Delta_0=\Delta_1$即$(3N-17-2x)=(3N-5+2x)$, 可得$x=-3$.因此$(U, V)$构成几乎差集偶, 只需$\lambda$取值$\Delta_0$.经计算可知$(U, V)$构成$(4f+1, 3f, f, f, \frac{3f-2}{4}, 3f)$-ADSP.

(b)如果$\Delta_1=\Delta_2$即$(3N-5+2x)=(3N-1-2x)$, 可得$x=1$.因此$(U, V)$构成几乎差集偶, 只需$\lambda$取值$\Delta_0$.经计算可知$(U, V)$构成$(4f+1, 3f, f, f, \frac{3f-4}{4}, f)$-ADSP.

(2) 当$f$为奇数时, 由表 2可得

$ \begin{eqnarray*}&&\Delta _{0}=(0, 0)+(3, 3)+(1, 1)=\frac{1}{16}(3N-13-2x), \\ &&\Delta _{1}=(1, 0)+(0, 3)+(2, 1)=\frac{1}{16}(3N-5-2x+8y), \\ &&\Delta _{2}=(2, 0)+(1, 3)+(3, 1)=\frac{1}{16}(3N-5+6x), \\ &&\Delta _{3}=(3, 0)+(2, 3)+(0, 1)=\frac{1}{16}(3N-5-2x-8y).\end{eqnarray*} $

因而$\Delta_1\neq \Delta_3$, 否则$y=0$与$N$为奇素数矛盾.

计算后可知$(U, V)$不构成几乎差集偶, 具体计算从略.

例2   当$x=1, y=2$时, $N=17, U=D_0\cup D_1\cup D_3=\{ \pm1, \pm3, \pm4, \pm5, \pm6, \pm7 \}, V=D_2=\{ \pm1, \pm4 \}$构成$(17, 12, 4, 4, 2, 4)$-ADSP.

另外, 笔者还讨论了其他4阶分圆类的情况, 虽然没有得到几乎差集偶的无穷类, 但仍然可以得到一些零星的结果, 如: $N=4f+1=x^2+4y^2, x\equiv1 ({\rm mod }\ 4).$当$f$为偶数时$ U=D_0\cup D_1, V=D_0, (U, V)$构成$(17, 8, 4, 4, 1, 3)$-ADSP; 当$f$为奇数时$U=D_0\cup D_1, V=D_0, (U, V)$构成$(13, 6, 3, 3, 1, 9)$-ADSP等等.

以下利用6阶分圆类构造几乎差集偶.先给出6阶分圆数^[5], 设$N=6f+1$是素数, $\theta^m=2 ({\rm mod} \ N)$, 则存在整数$A, B$使得$N=6f+1=A^2+3B^2$且$A\equiv 1({\rm mod} \ 3), B\equiv -m({\rm mod} \ 3)$.

(1) 当$f$为偶数时, $6$阶分圆数由表 3和表 4给出

(2) 当$f$为奇数时, $6$阶分圆数由表 5和表 6给出

定理4  设奇素数$N=6f+1=A^2+3B^2, A\equiv1({\rm mod} \ 3), B\equiv-m({\rm mod} \ 3), U=D_0, V=D_3.$

(1) 当$f$为偶数时,

(a)当$m\equiv0({\rm mod} \ 3)$时, $(U, V)$构成$(6f+1, f, f, 0, \frac{f-2}{6}, 4f)$-ADSP当且仅当$A=7, B=0({\rm mod} \ 3) $; 或$(U, V)$构成$(6f+1, f, f, 0, \frac{f-4}{6}, 2f)$-ADSP, 当且仅当$A=-5, B=0({\rm mod} \ 3) $.

(b)当$m\equiv1({\rm mod} \ 3)$时: $A=1, B=2, (U, V)$构成$(13, 2, 2, 0, 0, 8)$-ADSP, 或$A=7, B=2, (U, V)$构成$(61, 10, 10, 0, 1, 40)$-ADSP.

(c)当$m\equiv2({\rm mod} \ 3)$时: $A=1, B=-2, (U, V)$构成$(13, 2, 2, 0, 0, 8)$-ADSP, 或$A=7, B=-2, (U, V)$构成$(61, 10, 10, 0, 1, 40)$-ADSP.

(2) 当$f$为奇数时, $(U, V)$不构成几乎差集.

证  记$\Delta _i=\mid (D_0+\theta ^i)\cap D_3 \mid, 0\leq i \leq 5$, 注意到$(l, m)_e=\mid (D_l+1)\cap D_m\mid$, 从而

$ \Delta _i=\mid (D_{-i}+1) \cap D_{3-i} \mid=(-i, 3-i)=(i, 3), i=0, 1, 2, 3, 4, 5. $

(1) 当$f$为偶数时, 由表 3和表 4可得

(a)当$m=0({\rm mod} \ 3)$时, $\Delta_0=\Delta_3, \Delta_1=\Delta_2=\Delta_4=\Delta_5$, 令$\mid\Delta_0-\Delta_1\mid=1$即$A=7$或$A=-5$, 因此$(U, V)$构成一个几乎差集偶, 只需$\lambda$取值$\Delta_0$或$\Delta_1$.计算后可知, 当$A=7, B=0({\rm mod} \ 3)$时, $(U, V)$构成$(6f+1, f, f, 0, \frac{f-2}{6}, 4f)$-ADSP.当$A=-5, B=0({\rm mod} \ 3)$时, $(U, V)$构成$(6f+1, f, f, 0, \frac{f-4}{6}, 2f)$-ADSP.

(b)当$m=1({\rm mod} \ 3)$时, $\Delta_1 \neq \Delta_2$, 否则$B=0$与$N$为奇素数矛盾.如果$\Delta_0=\Delta_1$, 得$A=1$, 令$\mid\Delta_1-\Delta_2\mid=1$得$B=2$.因此$(U, V)$构成$(13, 2, 2, 0, 0, 8)$-ADSP.如果$\Delta_0=\Delta_2$, 得$-1+A-3B=0$, 令$\mid\Delta_0-\Delta_1\mid=1$得$B=2$, 解得$A=7$.因此$(U, V)$构成$(61, 10, 10, 0, 1, 40)$-ADSP.

(c)当$m=2({\rm mod} \ 3)$时, 情况与$m=1({\rm mod} \ 3)$时相类似.

(2) 当$f$为奇数时, 由表 5和表 6可得

计算后可知, $(U, V)$不构成几乎差集偶, 具体计算从略.