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


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


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


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