Difference set explained

In combinatorics, a

(v,k,λ)

difference set is a subset

of size

of a group

of order

such that every non-identity element of

can be expressed as a product

d_1d

	-1

	2

of elements of

in exactly

ways. A difference set

is said to be cyclic, abelian, non-abelian, etc., if the group

has the corresponding property. A difference set with

λ=1

is sometimes called planar or simple. If

is an abelian group written in additive notation, the defining condition is that every non-zero element of

can be written as a difference of elements of

in exactly

ways. The term "difference set" arises in this way.

Basic facts

A simple counting argument shows that there are exactly

k^2-k

pairs of elements from

that will yield nonidentity elements, so every difference set must satisfy the equation

k^2-k=(v-1)λ.

is a difference set and

g\inG,

then

gD=\{gd:d\inD\}

is also a difference set, and is called a translate of

(

D+g

in additive notation).

The complement of a

(v,k,λ)

-difference set is a

(v,v-k,v-2k+λ)

-difference set.

The set of all translates of a difference set

forms a symmetric block design, called the development of

and denoted by

dev(D).

In such a design there are

elements (usually called points) and

blocks (subsets). Each block of the design consists of

points, each point is contained in

blocks. Any two blocks have exactly

elements in common and any two points are simultaneously contained in exactly

blocks. The group

acts as an automorphism group of the design. It is sharply transitive on both points and blocks.^[1]

- In particular, if

λ=1

, then the difference set gives rise to a projective plane. An example of a (7,3,1) difference set in the group

Z/7Z

is the subset

\{1,2,4\}

. The translates of this difference set form the Fano plane.

Since every difference set gives a symmetric design, the parameter set must satisfy the Bruck–Ryser–Chowla theorem.
Not every symmetric design gives a difference set.

Equivalent and isomorphic difference sets

Two difference sets

D₁

in group

G₁

and

D₂

in group

G₂

are equivalent if there is a group isomorphism

\psi

between

G₁

and

G₂

such that

	\psi
D
	1

=\{d^\psi\colond\inD₁\}=gD₂

for some

g\inG_2.

The two difference sets are isomorphic if the designs

dev(D₁₎

and

dev(D₂₎

are isomorphic as block designs.

Equivalent difference sets are isomorphic, but there exist examples of isomorphic difference sets which are not equivalent. In the cyclic difference set case, all known isomorphic difference sets are equivalent.

Multipliers

A multiplier of a difference set

in group

is a group automorphism

\phi

such that

D^\phi=gD

for some

g\inG.

is abelian and

\phi

is the automorphism that maps

h\mapstoh^t

, then

is called a numerical or Hall multiplier.

It has been conjectured that if p is a prime dividing

k-λ

and not dividing v, then the group automorphism defined by

g\mapstog^p

fixes some translate of D (this is equivalent to being a multiplier). It is known to be true for

p>λ

when

is an abelian group, and this is known as the First Multiplier Theorem. A more general known result, the Second Multiplier Theorem, says that if

is a

(v,k,λ)

-difference set in an abelian group

of exponent

v^*

(the least common multiple of the orders of every element), let

be an integer coprime to

. If there exists a divisor

m>λ

k-λ

such that for every prime p dividing m, there exists an integer i with

t\equivp^i \pmod{v^*}

, then t is a numerical divisor.

For example, 2 is a multiplier of the (7,3,1)-difference set mentioned above.

It has been mentioned that a numerical multiplier of a difference set

in an abelian group

fixes a translate of

, but it can also be shown that there is a translate of

which is fixed by all numerical multipliers of

Parameters

The known difference sets or their complements have one of the following parameter sets:

((qⁿ⁺²-1)/(q-1),(qⁿ⁺¹-1)/(q-1),(q^n-1)/(q-1))

-difference set for some prime power

and some positive integer

. These are known as the classical parameters and there are many constructions of difference sets having these parameters.

(4n-1,2n-1,n-1)

-difference set for some positive integer Difference sets with are called Paley-type difference sets.

(4n^2,2n^2-n,n^2-n)

-difference set for some positive integer A difference set with these parameters is a Hadamard difference set.

(qⁿ⁺¹(1+(qⁿ⁺¹-1)/(q-1)),q^n(qⁿ⁺¹-1)/(q-1),q^n(q^n-1)/(q-1))

-difference set for some prime power

and some positive integer Known as the McFarland parameters.

(3ⁿ⁺¹(3ⁿ⁺¹-1)/2,3ⁿ⁽³ⁿ⁺¹+1)/2,3ⁿ⁽³^n+1)/2)

-difference set for some positive integer Known as the Spence parameters.

(4q²ⁿ(q²ⁿ-1)/(q-1),q^2n-1(1+2(q²ⁿ-1)/(q+1)),q^2n-1(q^2n-1+1)(q-1)/(q+1))

-difference set for some prime power

and some positive integer Difference sets with these parameters are called Davis-Jedwab-Chen difference sets.

Known difference sets

In many constructions of difference sets, the groups that are used are related to the additive and multiplicative groups of finite fields. The notation used to denote these fields differs according to discipline. In this section,

{\rmGF}(q)

is the Galois field of order

where

is a prime or prime power. The group under addition is denoted by

G=({\rmGF}(q),+)

, while

{\rmGF}(q)^*

is the multiplicative group of non-zero elements.

Paley

(4n-1,2n-1,n-1)

-difference set:

Let

q=4n-1

be a prime power. In the group

G=({\rmGF}(q),+)

, let

be the set of all non-zero squares.

Singer

((qⁿ⁺²-1)/(q-1),(qⁿ⁺¹-1)/(q-1),(q^n-1)/(q-1))

-difference set:

Let

G={\rmGF}(qⁿ⁺²)^*/{\rmGF}(q)^*

. Then the set

D=\{x\inG~|~{\rm

Tr}
	qⁿ⁺²/q

(x)=0\}

is a

((qⁿ⁺²-1)/(q-1),(qⁿ⁺¹-1)/(q-1),(q^n-1)/(q-1))

-difference set, where

{\rm

Tr}
	qⁿ⁺²/q

:{\rmGF}(qⁿ⁺²) → {\rmGF}(q)

is the trace function

\rm{Tr}
	qⁿ⁺²/q

(x)=x+x^{q+ … +x}

	qⁿ⁺¹

Twin prime power

\left(q²+2q,

	q²+2q-1
	2

	q^2+2q-3
	4

\right)

-difference set when

and

q+2

are both prime powers:

In the group

G=({\rmGF}(q),+) ⊕ ({\rmGF}(q+2),+)

, let

D=\{(x,y)\colony=0orxandyarenon-zeroandbotharesquaresorbotharenon-squares\}.

History

The systematic use of cyclic difference sets and methods for the construction of symmetric block designs dates back to R. C. Bose and a seminal paper of his in 1939. However, various examples appeared earlier than this, such as the "Paley Difference Sets" which date back to 1933. The generalization of the cyclic difference set concept to more general groups is due to R.H. Bruck in 1955. Multipliers were introduced by Marshall Hall Jr. in 1947.

Application

It is found by Xia, Zhou and Giannakis that difference sets can be used to construct a complex vector codebook that achieves the difficult Welch bound on maximum cross correlation amplitude. The so-constructed codebook also forms the so-called Grassmannian manifold.

Generalisations

(v,k,λ,s)

difference family is a set of subsets

B=\{B_1,\ldots,B_s\}

of a group

such that the order of

, the size of

B_i

for all

, and every non-identity element of

can be expressed as a product

d_1d

	-1

	2

of elements of

B_i

for some

(i.e. both

d_1,d₂

come from the same

B_i

) in exactly

ways.

A difference set is a difference family with

s=1.

The parameter equation above generalises to

s(k^{2-k)=(v-1)λ.}

The development

dev(B)=\{B_i+g:i=1,\ldots,s,g\inG\}

of a difference family is a 2-design.Every 2-design with a regular automorphism group is

dev(B)

for some difference family

References

- - - Book: Wallis, W.D. . Combinatorial Designs . registration . Marcel Dekker . 1988 . 0-8247-7942-8 . 0637.05004 .

Notes and References

. The theorem only states point transitivity, but block transitivity follows from this by the second corollary on p. 330.

Difference set explained

Basic facts

Equivalent and isomorphic difference sets

Multipliers

Parameters

Known difference sets

History

Application

Generalisations

See also

References

Further reading

Notes and References