The Existence Of Almost Difference Families

Ding introduced the definition of(q,k,λ,t)-almost difference set((q,k,λ,t)-ADS in short) in 2001,in which q,k,λ,t are all integers.The characteristic sequences of a cyclic ADS and its shifts form a collection of binary sequences with optimal autocorrelation,and hence they have many applications in communication and stream ciphering.(q,k,λ,t)-almost difference family((q,k,λ,t)-ADF in short)can be seen as an useful generalization of almost difference set and difference family.The definition of(q,k,λ,t)-ADF was introduced by Ding,and a few constructions on(q,k,λ,t)-ADF via finite fields were also presented in.Let G be an Abel group of order q,F={D1,D2,…,Dh}be a family of ki-subsets of G,in which Di={di1,di2,…,diki},1≤i≤h.Define the difference list△Di of Di to be the multi-set {a-b:a,b∈Di and a≠b},1≤i≤h. The union of the difference list△Di,1≤i≤h,is called the difference list of F,and is denoted by△F.We say that F is an almost difference family,(a(q,k,λ,t)-ADF in short), if some t nonzero elements of G occur exactlyλtimes each in the difference list△F,while the remaining q-1-t nonzero elements of G occur exactlyλ+1 times each in△F. Furthermore,if G is a cyclic group of order q,then we call the almost difference family a cyclic(q,k,λ,t)-ADF.The notation of A o B of two multi-sets A and B in G is defined to be the multi-set {ab:a∈A and b∈B).If B={b},then we can drop the braces for notational convenience. In this case,A o B coincides with Ab={ab:a∈A}.Suppose D is a k-subset of G,then one can find a subset D of G such that△D={1,-1}oD.In the sequel,the notion D will be used.The next construction of almost difference family was by Ding.Theorem 1.6 Suppose that q≡1(mod 2e)is an odd prime and 3≤k≤q is an integer.Letλ=[k(k-1)/2e] and 2r=k(k-1)-2λe.If there exists a k-subset D of G such that D covers exactlyλ+1 elements(counting multiplicities)in each of r cyclotomic classes of index e and exactlyλelements in each of the remaining e-r classes, then F={Dg:g∈U}is a cyclic(q,k,λ,t)-ADF,where t=(q-1)(e-r)／e and U is an arbitrary system of representatives for the multiplicative cosets of{1,-1}in C0e. Weil's theorem is very useful when one want to proof the existence of difference families. Chang et al.have given the theorem as follows:Theorem 1.10 Let q be a prime,q≡1(mod e)and q-[∑r=0s-2(?)(s-r-1)(e-1)s-r](?)-ses-1>0.Then,for any given s-tuple(i1,i2,…,is)∈{0,1,…,e-1}s and any given s-tuple(c1,c2,…,cs)of pairwise distinct elements of G,there exists an element x∈G* such that x+cr∈Ci(?)e for each r.In this paper,for our purpose,Lemma 1.10 is generalized to the following result.Theorem 1.11 Let q be a prime power,q≡1(mod e)and q-[∑r=2s(?)(r-1)(e-1)r+∑u=1t(?)(2u-1)(e-1)u+∑r=1s∑u=1t(?)(r+2u-1)(e-1)r+u](?)-stes+t-1>0. Then,for any given s-tuple(i1,i2,…,is)∈{0,1,…,e-1}s and t-tuple(h1,h2,…,ht)∈{0,1,…,e-1}t,any given s-tuple(c1,c2,…,cs)of pairwise distinct elements of GF(q), ((a1,b1),(a2,b2),…,(at,bt))∈(GF(q)×GF(q)*)t,there exists an element x∈GF(q)such that x+c(?)∈Ci(?)e,1≤r≤s,x2+aux+bu∈Chue,where x2+aux+bu are irreducible in GF(q)[x]and pairwise coprime,1≤u≤t.In this paper,the following conclusions are obtained by theorem 1.6,cyclotomic number, theorem 1.11 and computer searching.Theorem 1.12 For each odd prime q≡1(mod 8),there exist a cyclic(q,4,1,(q-1)/2)-ADF in G.Theorem 1.13 For each odd prime q=6f+1,there exists a cyclic(q,5,3,2(q-1)/3)-ADF in G.Theorem 1.14 For each odd prime q≡1(mod 8),there exists a cyclic(q,5,2,(q-1)/2)-ADF in G.Theorem 1.15 For each odd prime q≡1(mod 10),there exist a cyclic(q,4,1,4(q-1)/5)-ADF in G.Theorem 1.16 For each odd prime q≡1(mod 12),there exists a cyclic(q,5,1(q-1)/3)-ADF in G.Theorem 1.17 For each odd prime q≡1(mod 16),there exists a cyclic(q,5,1,3(q-1)/4)-ADF in G.Theorem 1.18 For each odd prime q≡1(mod 18),there exists a cyclic(q,5,1,8(q-1)/9)-ADF in G.Theorem 1.19 For each odd prime q≡1(mod 8),there exists a cyclic(q,6,3,(q-1)/4)-ADF in G.Theorem 1.20 Let q=12t+1 be a prime,and t(?)0(mod 3),then there exists a cyclic(q,6,2,(q-1)/2)-ADF in G.Theorem 1.21 Let q=18t+1 be a prime,and t(?)0(mod 3),then there exists a cyclic(q,6,1,(q-1)/3)-ADF in G. Theorem 1.22 Let q=24t+1 be a prime, and t(?)0 (mod 3), then there exists a cyclic (q,6,1,3(q-1)/4)-ADF in G.There are five chapters in this thesis. Some definitions, known results on almost differ-ence families and main results of this thesis are presented in chapter one and two. Chapter three to four give the proof of the main results. Further research problems are presented in Chapter five.