What is Difference Set of a Group
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].
- inv[0] = 0
- inv[1] = 12
- inv[2] = 11
- inv[3] = 10
- inv[4] = 9
- inv[5] = 8
- inv[6] = 7
- inv[7] = 6
- inv[8] = 5
- inv[9] = 4
- inv[10] = 3
- inv[11] = 2
- inv[12] = 1
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)
- 1 = 1 ⊕ inv[0] = 1 ⊕ 0
- 2 = 3 ⊕ inv[1] = 3 ⊕ 12
- 3 = 3 ⊕ inv[0] = 3 ⊕ 0
- 4 = 0 ⊕ inv[9] = 0 ⊕ 4
- 5 = 1 ⊕ inv[9] = 1 ⊕ 4
- 6 = 9 ⊕ inv[3] = 9 ⊕ 10
- 7 = 3 ⊕ inv[9] = 3 ⊕ 4
- 8 = 9 ⊕ inv[1] = 9 ⊕ 12
- 9 = 9 ⊕ inv[0] = 9 ⊕ 0
- 10 = 0 ⊕ inv[3] = 0 ⊕ 10
- 11 = 1 ⊕ inv[3] = 1 ⊕ 10
- 12 = 0 ⊕ inv[1] = 0 ⊕ 12
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”.
Reference
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
(i haven't read this book)