A Survey of Difference Sets

 

Introduction

A difference set D in a group G is a set with the property that there is a constant, l, such that every nonidentity element g of G may be written in the form g=xy-1  using exactly l ordered pairs (x,y) of D.  Thus, using the members of D, every nonidentity element has exactly l representations as a quotient.

 

Difference sets were originally introduced in abelian groups, so that nonzero elements were written as ÒdifferencesÓ, g=x-y; this explains the name.

 

A difference set has parameters (v, k, l); v is the size of the group G; k is the size of the set D; l is described above.  A  (v, k, l) difference set is equivalent to a symmetric  (v, k, l) design with a sharply transitive automorphism group G acting on the set of points.  Difference sets are used to construct symmetric designs and a number of related (and useful) combinatorial objects, including Hadamard matrices.

 

Example: let G = <x : x7=1> and D = {x, x2, x4}.  D is a (7,3,1) difference set.  Its complement, G-D ={1, x3, x5, x6}, is a (7,4,2) difference set.

 

In the integral group ring Z[G], we may view the set D as a group ring element consisting of the sum of the elements of D.   It is customary to use the letter D to represent this sum, so that we ÒconfuseÓ the set D with the group ring element (sum) D.  For example, the group ring element D =x + x2 + x4   will be described as a  (7,3,1) difference set in G = <x : x7=1> and we will use the letter D to describe both D = {x, x2, x4} and D =x + x2 + x4 .

 

If D represents a sum of elements, then D(-1) will represent a sum of the inverses of those elements.  In the group ring, the difference set D then satisfies the fundamental equation

 

D D(-1) = (k)1G + l (G-1G) = (k-l) 1G + l (G).

 

(Here 1G is the identity of the group  G.  The group ring element G, appearing in this equation, is the sum of all the elements of the set G.)

 

Since D D(-1) = (k-l) 1G + l (G), then under any nonprincipal character c of G, c(D) is a cyclotomic integer dividing k-l.

For this reason, the integer  n:= k-l  is an important parameter of the design (possibly the most critical parameter.)  The parameter  n:= k-l  is called the order of the difference set.

 

If D is a difference set then, given any group element g and automorphism f of G then f(gD) is also a difference set, said to be ÒequivalentÓ to D.

 

Difference sets with order 15 or less:

Here is a list of all  difference sets with order less than or equal to 15, arranged by order n, prepared for GAP users.  (This list includes a (36,15,6) difference set missed in KiblerÕs survey.)

 

(96,20,4) difference sets:

We have determined the existence of (96,20,4) difference sets in all groups of order 96.  Here is a file listing approximately 2600 (96,20,4) difference sets, prepared for GAP users.  These are all the (96,20,4) difference sets known to me as of May 20, 2006.  This file contains an exhaustive list of difference sets in all groups of order 96 with the following exceptions:  the list may be incomplete for groups [96, cn] where cn is in {64, 70, 71, 72, 218, 220, 227, 230, 231}.  The groups [96,64], [96,70], [96,71], [96,72], [96,227] do not have normal subgroups of sizes 2 or 3 so OmarÕs search technique and KenÕs ÒBruteForceSieveÓ do not work.  Fortunately, Golemac and others found difference sets in these groups using a different (nonexhaustive) approach.

 

See the survey paper on (96,20,4) difference sets (pdf) for an introduction to most of these.  In that survey paper, we resolved the existence of (96,20,4) difference sets for all groups of order 96 except [96, cn ] where the GAP SmallGroup catalogue number cn is in the set {3, 65, 66, 67, 68, 69, 73, 74, 187, 189, 191, 192, 193, 198, 199, 200, 201, 202, 203, 204}.  The fundamental technique in that work was to concentrate on a normal subgroup of order 12, with subgroups of orders 3 and 4 which are also normal in the larger group of order 96.  The homomorphic images of sizes 24 and 32 placed enough restrictions that an exhaustive search could be made, to either rule out a difference set or find all of them.  This technique failed if there were not normal subgroups of sizes 3 and 4.

 

As of May 18, 2006, we have the following updates:

               The survey paper has two errors:  the group [96, 171] does have difference sets; several difference sets in the group [96, 225] are equivalent.  (These errors will be corrected in a revision of the paper.)

               An exhaustive search using the ÒBruteForceSieveÓ GAP program (below) has ruled out difference sets in:

                              [96, cn] where cn is 3, 65, 66, 67, 69, 73, 74, 187, 189, 192, 193, 198, 199, 200, 201, 203, 204.

               The same exhaustive search has found difference sets in:

                              [96, 191] and [96, 202].

               By different techniques, a difference set has been found in [96,68] (Anka Golemac, personal communication.)

               All the other nonexistence results from the survey paper above have been verified by an independent run, using a different technique (BruteForceSieve, below.)

 

In conclusion, the group [96, cn] has a (96,20,4) difference set if and only if cn is in the list

[ 10, 13, 14, 20, 41,   51, 52, 54, 64, 68,

  70, 71, 72, 75, 77,   78, 79, 83, 84, 85,

  86, 87, 88, 90, 91,   92, 94, 95, 96, 97,

  98, 99,101,103,105,   129,130,131,133,135,

 136,141,142,143,144,   145,146,147,151,152,

 159,160,161,162,164,   165,166,167,168,169,

 170,171,172,173,174,   175,177,185,186,188,

 190,191,194,195,196,   197,202,205,206,209,

 210,212,218,219,220,   221,223,225,226,227,

 228,229,230,231];

 

Updated May 20, 2006:  An exhaustive list of difference sets in [96,68] is provided (using BruteForceSieve), the exhaustive list for [96, 225] has been corrected and three more inequivalent difference sets have been found, 2 in [96,70] and 1 in [96,227].  These three sets were found by ÒmagicÓ – I tested the entire list of sets in the file to see if any of them could be difference sets in [96,70] or [96, 227] and Ògot lucky.Ó  (This technique did not work in [96,64], [96,71] or [96,72].)

 

Other results:

Here is a partial list of some difference sets with order greater than or equal to 16, arranged by order n, prepared for GAP users.

 

Some GAP programs:

I have written a collection of procedures to examine difference sets.  A file of them is saved here:

                DifSets.txt.

There is a documentation page of these programs.  And a demo file which requires that the following files be downloaded.

                test_1_1.txt.

                test_1_2.txt.

                test_1_3.txt.

                test_2_1.txt.

                test_2_2.txt.

                test_2_3.txt.

                test_2_4.txt.

                test_2_5.txt.

                test_2_6.txt.

                test_3_1.txt.

After downloading these test files, a master file will run these demos.

 

Another difference set program is

                AfterC9xC2xC2xC2xC2.txt

which uses procedures in

                ShiftProcedures_2007.txt.

 

Various other GAP programs: Lift.txt and BruteForceSieve_DS.txt (all still in beta form.)  A program AccessingBFS.txt will oversee the running of these difference set search files.   These will be updated soon.

 

Last modified on June 27, 2007.