一些新的差族和几乎差族
Some New Difference Families and Almost Difference Families

作者: 刘永晴 , 汤 静 , 唐玲丽 :大连民族大学理学院预科教育学院,辽宁 大连; 孔庆欣 , 陆俞先 , 王天祎 :大连民族大学计算机科学与工程学院,辽宁 大连;

关键词: 差族几乎差族分圆类分圆数Difference Family Almost Difference Family Cyclotomic Classes Cyclotomic Numbers

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

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.

1. 引言

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

2. 基础知识

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

设G是一个阶数为v的加法交换群, B i G ,且 | B i | = k i ( 1 i s ) ,多重集 Δ B i = { a b : a , b B i , a b } F = { B 1 , B 2 , , B s } 称为一个集族,多重集 Δ F = i = 1 s Δ B i = i = 1 s { a b : a , b B i , a b }

定义1 [5]:称集族 F = { B 1 , B 2 , , B s } 为一个 { v , { k 1 , k 2 , , k s } , λ , t } 几乎差族(Almost Difference Family, ADF),如果G中有t个非零元素,这些元素中的每一个在 Δ F 中出现的次数为 λ ,而对于剩下的 v 1 t 个非零元素,每个元素在 Δ F 中出现的次数为 λ + 1 。如果 t = v 1 ,则称 F = { B 1 , B 2 , , B s } 为一个 { v , { k 1 , k 2 , , k s } , λ } 差族(Difference Family, DF)。

由以上定义,不难得到如下结论: F = { B 1 , B 2 , , B s } 是一个 { v , { k 1 , k 2 , , k s } , λ , t } -ADF ( { v , { k 1 , k 2 , , k s } , λ } -DF)当且仅当对于G中的每一个非零元素g, i = 1 s | ( B i + g ) B i | = λ + 1 λ

不难验证,当 F = { B 1 , B 2 , , B s } 是一个 { v , { k 1 , k 2 , , k s } , λ , t } -ADF时, t = ( λ + 1 ) ( v 1 ) i = 1 s k i × ( k i 1 ) 。因此,当我们表示一个ADF时,常将参数t省略。

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

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

q = e f + 1 为一个奇素数, θ GF ( q ) 的一个本原元, θ e = { θ i e : 0 i f 1 } 是由 θ e 生成的 GF * ( q ) 的乘法子群,它的陪集 C j ( e , q ) = θ j θ e ( 0 j e 1 ) 称为在 GF ( q ) 中的e阶分圆类。定义分圆数 ( j , k ) e 为方程 x + 1 = y , x C j ( e , q ) , y C k ( e , q ) 解的个数,即

( j , k ) e = | ( C j ( e , q ) + 1 ) C k ( e , q ) | .

下面给出分圆数的性质。

1) ( i , j ) e = ( i , j ) e ,其中 i i ( mod e ) , j j ( mod e )

2) ( i , j ) e = ( e i , j i ) e = { ( j , i ) e , f , ( j + e 2 , i + e 2 ) e , f .

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

3.1. 六阶分圆数

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

Table 1. The relations of the cyclotomic numbers of order 6 when f is odd [9]

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

Table 2. The ten basic cyclotomic numbers of order 6 when f is odd [9]

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

3.2. 新的差族和几乎差族

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

定理1:设奇素数 p = 6 f + 1 = a 2 + 3 b 2 a 1 ( mod 3 ) θ GF ( p ) 的一个本原元,且 θ m = 2 ,则

①当f为奇数, m 0 ( mod 3 ) ,且 a 6 b = 2 时,

( C 0 C 1 , C 3 C 5 ) 是一个 ( p , { p 1 3 , p 1 3 } , 2 p 8 9 ) -DF;

( C 0 C 2 , C 0 C 1 C 5 ) 是一个 ( p , { p 1 3 , p 1 2 } , 13 p 43 36 ) -DF.

②当f为奇数, m 1 ( mod 3 ) ,且 a + 3 b = 7 时,

( C 0 { 0 } , C 1 C 2 ) 是一个 ( p , { p + 5 6 , p 1 3 } , 5 p 11 36 ) -DF.

③当f为奇数, m 1 ( mod 3 ) ,且 a + 3 b = 1 时,

( C 0 { 0 } , C 1 C 2 { 0 } ) 是一个 ( p , { p + 5 6 , p + 2 3 } , 5 p + 13 36 ) -DF.

证明:只证①,②和③类似可证。

x C i ( 0 i 5 ) ,则

| ( ( C 0 C 1 ) + x ) ( C 0 C 1 ) | = | ( C 0 + x ) C 0 | + | ( C 0 + x ) C 1 | + | ( C 1 + x ) C 0 | + | ( C 1 + x ) C 1 | = ( i , i ) + ( i , 1 i ) + ( 1 i , i ) + ( 1 i , 1 i ) = ( i , 0 ) + ( i , 1 ) + ( i 1 , 1 ) + ( i 1 , 0 ) .

| ( ( C 3 C 5 ) + x ) ( C 3 C 5 ) | = | ( C 3 + x ) C 3 | + | ( C 3 + x ) C 5 | + | ( C 5 + x ) C 3 | + | ( C 5 + x ) C 5 | = ( 3 i , 3 i ) + ( 3 i , 5 i ) + ( 5 i , 3 i ) + ( 5 i , 5 i ) = ( i 3 , 0 ) + ( i 3 , 2 ) + ( i 5 , 2 ) + ( i 5 , 0 ) .

Δ i = ( i , 0 ) + ( i , 1 ) + ( i 1 , 1 ) + ( i 1 , 0 ) + ( i 3 , 0 ) + ( i 3 , 2 ) + ( i 5 , 2 ) + ( i 5 , 0 ) ,

Δ ( C 0 C 1 , C 3 C 5 ) = i = 0 5 Δ i C i .

当f为奇数, m 0 ( mod 3 ) 时,由表1表2的数据可得

Δ 0 = Δ 3 = 10 9 a 9 + 2 b 3 + 2 p 9 ,

Δ 1 = Δ 2 = Δ 4 = Δ 5 = 7 9 + a 18 b 3 + 2 p 9 .

( C 0 C 1 , C 3 C 5 ) 为差族,当且仅当 Δ 0 = Δ 1 ,即 10 9 a 9 + 2 b 3 + 2 p 9 = 7 9 + a 18 b 3 + 2 p 9 。化简,得 a 6 b = 2 ,此时,参数 λ = 2 p 8 9 ,所以 ( C 0 C 1 , C 3 C 5 ) 是一个 ( p , { p 1 3 , p 1 3 } , 2 p 8 9 ) -DF。

对于集族 ( C 0 C 2 , C 0 C 1 C 5 ) ,仍然假设

Δ ( C 0 C 2 , C 0 C 1 C 5 ) = i = 0 5 Δ i C i ,

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

Δ 0 = Δ 2 = Δ 3 = Δ 5 = 47 36 a 18 + b 3 + 13 p 36 ,

Δ 1 = Δ 4 = 35 36 + a 9 2 b 3 + 13 p 36 .

要使 ( C 0 C 2 , C 0 C 1 C 5 ) 是差族,当且仅当 Δ 0 = Δ 1 ,即

47 36 a 18 + b 3 + 13 p 36 = 35 36 + a 9 2 b 3 + 13 p 36 .

化简,得 a 6 b = 2 。此时,参数 λ = 13 p 43 36 ,所以 ( C 0 C 2 , C 0 C 1 C 5 ) 是一个 ( p , { p 1 3 , p 1 2 } , 13 p 43 36 ) -DF。证毕。

例如当 p = 16699 ,对应的 a = 124 , b = 21 ,此时, ( C 0 C 1 , C 3 C 5 ) 是一个 ( 16699 , { 5566 , 5566 } , 3710 ) -DF, ( C 0 C 2 , C 0 C 1 C 5 ) 是一个 ( 16699 , { 5566 , 8349 } , 6029 ) -DF。

定理2:设奇素数 p = 6 f + 1 = a 2 + 3 b 2 a 1 ( mod 3 ) θ GF ( p ) 的一个本原元,且 θ m = 2 ,则

①当f为奇数, m 0 ( mod 3 ) 时,

a = 4 ,则 ( C 0 { 0 } , C 0 C 1 C 4 ) 是一个 ( p , { p + 5 6 , p 1 2 } , 5 p 17 18 , 2 ( p 1 ) 3 ) -ADF, ( C 0 C 3 { 0 } , C 1 C 5 ) 是一个 ( p , { p + 2 3 , p 1 3 } , 2 p 5 9 , 2 ( p 1 ) 3 ) -ADF;

a = 16 ,则 ( C 0 C 3 { 0 } , C 1 C 5 ) 是一个 ( p , { p + 2 3 , p 1 3 } , 2 p 8 9 , p 1 3 ) -ADF。

②当f为奇数, m 1 ( mod 3 ) 时,若 a = 2 ,则 ( C 0 C 1 { 0 } , C 1 C 5 ) ( C 0 C 2 { 0 } , C 0 C 3 ) ( p , { p + 2 3 , p 1 3 } , 2 p 5 9 , 2 ( p 1 ) 3 ) -ADF;

a = 10 ,则 ( C 0 C 2 { 0 } , C 0 C 3 ) 是一个 ( p , { p + 2 3 , p 1 3 } , 2 p 8 9 , p 1 3 ) -ADF。

③当f为奇数, m 2 ( mod 3 ) 时,

a 3 b = 5 ,则 ( C 0 C 2 , C 0 C 1 C 3 ) 是一个 ( p , { p 1 3 , p 1 2 } , 13 p 55 36 , 2 ( p 1 ) 3 ) -ADF;

a 3 b = 1 ,则 ( C 0 C 2 , C 0 C 1 C 3 ) 是一个 ( p , { p 1 3 , p 1 2 } , 13 p 67 36 , p 1 3 ) -ADF;

a = 2 ,则 ( C 0 C 3 , C 0 C 4 { 0 } ) 是一个 ( p , { p 1 3 , p + 2 3 } , 2 p 5 9 , 2 ( p 1 ) 3 ) -ADF;

a = 10 ,则 ( C 0 C 3 , C 0 C 4 { 0 } ) 是一个 ( p , { p 1 3 , p + 2 3 } , 2 p 8 9 , p 1 3 ) -ADF。

证明:只证①。设 x C i ( 0 i 5 ) ,则 | ( C 0 + x ) C 0 | = ( i , i ) = ( i , 0 ) ,所以 Δ C 0 = i = 0 5 ( i , 0 ) C i 。当f为奇数时,

Δ ( C 0 { 0 } ) = ( ( 0 , 0 ) + 1 ) C 0 ( 1 , 0 ) C 1 ( 2 , 0 ) C 2 ( ( 3 , 0 ) + 1 ) C 3 ( 4 , 0 ) C 4 ( 5 , 0 ) C 5 .

| ( ( C 0 C 1 C 4 ) + x ) ( C 0 C 1 C 4 ) | = | ( C 0 + x ) C 0 | + | ( C 0 + x ) C 1 | + | ( C 0 + x ) C 4 | + | ( C 1 + x ) C 0 | + | ( C 1 + x ) C 1 | + | ( C 1 + x ) C 4 | + | ( C 4 + x ) C 0 | + | ( C 4 + x ) C 1 | + | ( C 4 + x ) C 4 | = ( i , 0 ) + ( i , 1 ) + ( i , 4 ) + ( i 1 , 1 ) + ( i 1 , 0 ) + ( i 1 , 3 ) + ( i 4 , 4 ) + ( i 4 , 3 ) + ( i 4 , 0 ) .

Δ ( C 0 C 1 C 4 ) = i = 0 5 ( ( i , 0 ) + ( i , 1 ) + ( i , 4 ) + ( i 1 , 1 ) + ( i 1 , 0 ) + ( i 1 , 3 ) + ( i 4 , 4 ) + ( i 4 , 3 ) + ( i 4 , 0 ) ) C i .

Δ ( C 0 { 0 } , C 0 C 1 C 4 ) = i = 0 5 Δ i C i ,则

Δ i = 2 ( i , 0 ) + ( i , 1 ) + ( i , 4 ) + ( i 1 , 1 ) + ( i 1 , 0 ) + ( i 1 , 3 ) + ( i 4 , 4 ) + ( i 4 , 3 ) + ( i 4 , 0 ) + δ i ,

其中 δ i = { 0 , i = 1 , 2 , 4 , 5 , 1 , i = 0 , 3. 表1表2,得

Δ 0 = Δ 3 = 1 18 2 a 9 + 5 p 18 ,

Δ 1 = Δ 4 = 25 18 + a 9 + 5 p 18 ,

Δ 2 = Δ 5 = 7 18 + a 9 + 5 p 18 .

因为 Δ 1 Δ 2 = 1 ,因此 ( C 0 { 0 } , C 0 C 1 C 4 ) 为几乎差族,当且仅当 Δ 0 = Δ 1 Δ 0 = Δ 2 。由 Δ 0 = Δ 1 ,得 a = 4 。此时,参数 λ = 5 p 17 18 , t = 2 ( p 1 ) 3 。由 Δ 0 = Δ 2 ,得 a = 1 ,此时 a 1 ( mod 3 ) ,舍去。所以,当 a = 4 时, ( C 0 { 0 } , C 0 C 1 C 4 ) 是一个

( p , { p + 5 6 , p 1 2 } , 5 p 17 18 , 2 ( p 1 ) 3 ) -ADF.

对于集族 ( C 0 C 3 { 0 } , C 1 C 5 ) ,仍然假设 Δ ( C 0 C 3 { 0 } , C 1 C 5 ) = i = 0 5 Δ i C i 。与上面得计算过程类似,可得

Δ 0 = Δ 3 = 8 9 a 9 + 2 p 9 ,

Δ 1 = Δ 2 = Δ 4 = Δ 5 = 7 9 + a 18 + 2 p 9 .

( C 0 C 3 { 0 } , C 1 C 5 ) 为几乎差族,当且仅当 | Δ 0 Δ 1 | = 1 ,即

| 8 9 a 9 + 2 p 9 + 7 9 a 18 2 p 9 | = 1.

化简计算,得 a = 16 a = 4 。当 a = 4 时,参数 λ = 2 p 5 9 , t = 2 ( p 1 ) 3 ,此时, ( C 0 C 3 { 0 } , C 1 C 5 ) 是一个 ( p , { p + 2 3 , p 1 3 } , 2 p 5 9 , 2 ( p 1 ) 3 ) -ADF。当 a = 16 时,参数 λ = 2 p 8 9 , t = p 1 3 ,此时, ( C 0 C 3 { 0 } , C 1 C 5 ) 是一个 ( p , { p + 2 3 , p 1 3 } , 2 p 8 9 , p 1 3 ) -ADF。证毕。

例如,当 a = 4 , b = 63 时, p = 11923 。此时, ( C 0 { 0 } , C 0 C 1 C 4 ) 是一个 ( 11923 , { 1988 , 5961 } , 3311 , 7948 ) -ADF, ( C 0 C 3 { 0 } , C 1 C 5 ) 是一个 ( 11923 , { 3975 , 3974 } , 2649 , 7948 ) -ADF。当 a = 16 , b = 51 时, p = 8059 。此时, ( C 0 C 3 { 0 } , C 1 C 5 ) 是一个 ( 8059 , { 2687 , 2686 } , 1790 , 2686 ) -ADF。

基金项目

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

文章引用: 刘永晴 , 孔庆欣 , 陆俞先 , 汤 静 , 王天祎 , 唐玲丽 (2020) 一些新的差族和几乎差族。 应用数学进展, 9, 451-457. doi: 10.12677/AAM.2020.93055

参考文献

[1] Chung, F.R., Salehi, J.A. and Wei, V.K. (1989) Optical Orthogonal Codes: Design, Analysis and Applications. IEEE Transactions on Information Theory, 35, 595-604.
https://doi.org/10.1109/18.30982

[2] Gu, F.R. and Wu, J. (2005) Construction of Two-Dimensional Wavelength/Time Optical Orthogonal Codes Using Difference Family. Journal of Lightwave Technology, 23, 3642.
https://doi.org/10.1109/JLT.2005.855860

[3] Buratti, M. (2002) Cyclic Designs with Block Size 4 and Related Optimal Optical Orthogonal Codes. Designs, Codes and Cryptography, 26, 111-125.
https://doi.org/10.1109/JLT.2005.855860

[4] Colbourn, C.J. and Dinitz, J.H. (2006) Handbook of Combinatorial Designs. CRC Press, Boca Raton, Florida.
https://doi.org/10.1201/9781420010541

[5] Ding, C. and Yin, J. (2008) Constructions of Almost Difference Families, Discrete Mathematics, 308, 4941-4954.
https://doi.org/10.1016/j.disc.2007.09.017

[6] Storer, T. (1967) Cyclotomy and Difference Sets. Markham Pub-lishing Company, Chicago.

[7] Wilson, R.M. (1972) Cyclotomy and Difference Families in Elementary Abelian Groups. Journal of Number Theory, 4, 17-47.
https://doi.org/10.1016/0022-314X(72)90009-1

[8] Dang, S., Qiu, L. and Wu, D. (2017) New -ADFs via Cyclotomy. Discrete Mathematics, 340, 704-707.
https://doi.org/10.1016/0022-314X(72)90009-1

[9] Dickson, L.E. (1935) Cyclotomy, Higher Congruences, and Waring’s Problem. American Journal of Mathematics, 57, 391-424.
https://doi.org/10.2307/2371217

分享
Top