difference set


Definition. Let A be a finite abelian group of order n. A subset D of A is said to be a difference setMathworldPlanetmath (in A) if there is a positive integer m such that every non-zero element of A can be expressed as the difference of elements of D in exactly m ways.

If D has d elements, then we have the equation

m(n-1)=d(d-1).

In the equation, we are counting the number of pairs of distinct elements of D. On the left hand side, we are counting it by noting that there are m(n-1) pairs of elements of D such that their difference is non-zero. On the right hand side, we first count the number of elements in D2, which is d2, then subtracted by d, since there are d pairs of (x,y)D2 such that x=y.

A difference set with parameters n,m,d defined above is also called a (n,d,m)-difference set. A difference set is said to be non-trivial if 1<d<n-1. A difference set is said to be planar if m=1.

Difference sets versus square designs. Recall that a square design is a τ-(ν,κ,λ)-design (http://planetmath.org/Design) where τ=2 and the number ν of points is the same as the number b of blocks. In a general design, b is related to the other numbers by the equation

b(κτ)=λ(ντ).

So in a square design, the equation reduces to bκ(κ-1)=λν(ν-1), or

λ(ν-1)=κ(κ-1),

which is identical to the equation above for the difference set. A square design with parameters λ,ν,κ is called a square (ν,κ,λ)-design.

One can show that a subset D of an abelian groupMathworldPlanetmath A is an (n,d,m)-difference set iff it is a square (n,d,m)-design where A is the set of points and {D+aaA} is the set of blocks.

Title difference set
Canonical name DifferenceSet
Date of creation 2013-03-22 16:50:04
Last modified on 2013-03-22 16:50:04
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Definition
Classification msc 05B10
Defines non-trivial difference set
Defines planar difference set