What is Difference Set of a Group

By Xah Lee. Date:

A difference set of a group is a subset of the group that satisfies some properties.

Let there be a group (G,⊕). The difference set of the group is a subset of G, such that, for any non-identity element of G, it can be expressed as α⊕β^-1 in exactly λ ways, where α and β are elements of D.

A difference set is said to be (v,k,λ) difference set, where v is the size of G, k is the size of D, and λ.

Example of a Difference Set

suppose we have ℤ13, the cyclic group of order 13. That is, with elements 0 to 12, and modular arithmetic as operation.

the set D = {0,1,3,9} is a (13,4,1) difference set of the group ℤ13.

first, let's get a table of ℤ13's inverse elements.

(Reminder: two elements {x,y} are inverse to each other if x⊕y=y⊕x=0, where 0 is the identity element. (a identity element is a element (let's denote it “0”) such that z⊕0=0⊕z=z for any element z.))

Let's denote the inverse of a element x as inv[x].

Here is a table, showing that every non-identity element of ℤ13, is expressed as α⊕inv[β] in 1 way, where α and β are in D. (and it's the only way)

Note: it's called “difference set” because, if we denote group operator by “+”, then, we might also denote inverse of β by by convention, thus α + inv[β] is written as α + -β or just α - β, thus “difference”.


Difference set

the example is from Bill Cherowitzo http://www-math.ucdenver.edu/~wcherowi/'s file at http://www-math.ucdenver.edu/~wcherowi/courses/m6406/diffsets.pdf

difference sets  Emily H Moore  book cover 2014-02-13
Difference Sets Connecting Combinatorics Mathematical by Emily H Moore. Buy at amazon

(i haven't read this book)