Difference set

complete difference set

A set $D$ consisting of $k$ residues $d_1,\dots,d_k$ modulo a certain natural number $v$ such that for each $a\in D$, $a\not\equiv0$ ($\bmod\,v$), there exist precisely $\lambda$ ordered pairs $(d_i,d_j)$ of elements from $D$ for which

$$a\equiv d_i-d_j\pmod v;$$

the numbers $v,k,\lambda$ are called the parameters of the difference set. For example, the set $D=\{1,3,4,5,9\}$ of residues modulo 11 is a difference set with $\lambda=2$.

Difference sets are closely connected with block designs (cf. Block design), namely: The existence of a difference set is equivalent to the existence of a symmetric block design with parameters $(v,k,\lambda)$ having a cyclic group of automorphisms of order $v$ (the blocks of such a design are the sets $\{d_1+i,\dots,d_k+i\}$, $i=0,\dots,v-1$). The notion of a difference set can be generalized in the following way: A set $D$ consisting of $k$ distinct elements $d_1,\dots,d_k$ of a group $G$ of order $v$ is called a $(v,k,\lambda)$-difference set in $G$ if for any $a\in G$, $a\neq1$, there exist precisely $\lambda$ ordered pairs $(d_i,d_j)$, $d_i,d_j\in G$, such that $d_id_j^{-1}=a$ (or, what is the same, $\lambda$ pairs $(d_i,d_j)$ with $d_i^{-1}d_j=a$). In this case a difference set as defined above is called a cyclic difference set (since the group of residue classes $\bmod\,v$ is a cyclic group). The existence of $(v,k,\lambda)$-difference sets in a group $G$ of order $v$ is equivalent to the existence of a symmetric block design with parameters $(v,k,\lambda)$ admitting $G$ as a regular (that is, without fixed points) group of automorphisms (this design is obtained by identifying the elements of the block design with the elements of the group and the blocks with the sets $\{d_1g,\dots,d_kg\}$, where $g$ runs over $G$).

The question of the existence and construction of a difference set with given parameters is fundamental in the theory of difference sets. For this question the concept of a multiplier of a difference set turns out to be useful: An automorphism of the group $G$ is a multiplier of a $(v,k,\lambda)$-difference set $D$ in $G$ if it is also an automorphism of the block design determined by $D$. For a cyclic difference set a multiplier is a number $t$ relatively prime with $v$ and with the property that

$$\{td_1,\dots,td_k\}=\{d_1+i,\dots,d_k+i\}$$

for a certain $i$, $0\leq i\leq v-1$. The multipliers of a cyclic difference set form a group. The following assertion is true: If $D$ is a cyclic $(v,k,\lambda)$-difference set and if $p$ is a prime number dividing $k-\lambda$ and such that $(p,v)=1$ and $p>\lambda$, then $p$ is a multiplier of $D$ (the multiplier theorem for difference sets). The following result is useful when constructing difference sets: For any multiplier of a $(v,k,\lambda)$-difference set $D$ in an Abelian group $G$ of order $v$ there exists a block in the block design determined by $D$ which is fixed by this multiplier; when $(v,k)=1$ there exists a block fixed by any multiplier.

Difference sets are usually constructed by direct methods, using the properties of finite fields and cyclotomic fields (see Cyclotomic field) as well as finite geometries. Several infinite families of difference sets are known, for example the following types $S$ and $Q$.

Type $S$ (Singer difference sets): These are hyperplanes in an $n$-dimensional projective geometry over a field of $q$ elements. The parameters are:

$$v=\frac{q^{n+1}-1}{q-1},\quad k=\frac{q^n-1}{q-1},\quad\lambda=\frac{q^{n-1}-1}{q-1}.$$

Type $Q$: Quadratic residues in the field $\operatorname{GF}(p^r)$ when $p^r\equiv3$ ($\bmod\,4$) ($p$ is a prime number). The parameters are:

$$v=p^r=4t-1,\quad k=2t-1,\quad\lambda=t-1.$$

For other infinite families of difference sets see [1]–[3]. Besides these difference sets, generalized difference sets are often considered. They are also called difference families and are sets $D_1,\dots,D_r$ consisting of residues $\bmod\,v$ such that for any $a\not\equiv0$ ($\bmod\,v$) there exist precisely $\lambda$ ordered pairs $(d_i,d_j)$, $d_i,d_j\in D_k$, with

$$a\equiv d_i-d_j\pmod v$$

for a certain $k$, $1\leq k\leq r$.

There are also other generalizations of difference sets.

References

[1]	M. Hall, "Combinatorial theory" , Blaisdell (1967)
[2]	L.D. Baumert, "Cyclic difference sets" , Springer (1971)
[3]	M. Hall, "Difference sets" , Combinatorics. 3 Combinatorial group theory. Proc. NATO, Breukelen , Math. Centre Tracts , 57 , CWI (1974) pp. 1–26