Difference set

For the concept of set difference, see complement (set theory).

In combinatorics, a $(v,k,\lambda )$ difference set is a subset $D$ of a group $G$ such that the order of $G$ is $v$, the size of $D$ is $k$, and every nonidentity element of $G$ can be expressed as a product $d_{1}d_{2}^{-1}$ of elements of $D$ in exactly $\lambda$ ways.

Basic facts

• A simple counting argument shows that there are exactly $k^{2}-k$ pairs of elements from $D$ that will yield nonidentity elements, so every difference set must satisfy the equation $k^{2}-k=(v-1)\lambda$.
• If $D$ is a difference set, and $g\in G$, then $gD=\{gd:d\in D\}$ is also a difference set, and is called a translate of $D$.
• The set of all translates of a difference set $D$ forms a combinatorial design. Each block of the design has $k$ elements, and any two blocks have exactly $\lambda$ elements in common. In particular, if $\lambda =1$, then the difference set gives rise to a projective plane.
• Since every difference set gives a combinatorial design, the parameter set must satisfy the Bruck-Chowla-Ryser theorem.
• Not every combinatorial design gives a difference set.

An example of a (7,3,1) difference set in the group $\mathbb {Z} /7\mathbb {Z}$ is the set $\{1,2,4\}$. The translates of this difference set gives the Fano plane.

Multipliers

It has been conjectured that if $p$ is a prime dividing $k-\lambda$ and does not divide $v$, then the group automorphism defined by $g\mapsto g^{p}$ fixes some translate of $D$. It is known to be true for $p>\lambda$, and this is known as the First Multiplier Theorem. A more general known result, the Second Multiplier Theorem, first says to choose a divisor $m>\lambda$ of $k-\lambda$. Then $g\mapsto g^{t}$, $t$ coprime with $v$, fixes some translate of $D$ if for every prime $p$ dividing $m$, there exists an integer $i$ such that $t\equiv p^{i}{\bmod {v}}^{*}$, where $v^{*}$ is the exponent (the least common multiple of the orders of every element) of the group.

Parameters

Every difference set known to mankind to this day has one of the following parameters or their complements:

• $((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))$-difference set for some prime power $q$ and some positive integer $n$.
• $(4n-1,2n-1,n-1)$-difference set for some positive integer $n$.
• $(4n^{2},2n^{2}-n,n^{2}-n)$-difference set for some positive integer $n$.
• $(q^{n+1}(1+(q^{n+1}-1)/(q-1)),q^{n}(q^{n+1}-1)/(q-1),q^{n}(q^{n}-1)(q-1))$-difference set for some prime power $q$ and some positive integer $n$.
• $(3^{n+1}(3^{n+1}-1)/2,3^{n}(3^{n+1}+1)/2,3^{n}(3^{n}+1)/2)$-difference set for some positive integer $n$.
• $(4q^{2n}(q^{2n}-1)/(q-1),q^{2n-1}(1+2(q^{2n}-1)/(q+1)),q^{2n-1}(q^{2n-1}+1)(q-1)/(q+1))$-difference set for some prime power $q$ and some positive integer $n$.

Known difference sets

• Singer $((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1)){\overline {}}$-Difference Set:

Let $G={\rm {GF}}(q^{n+2})^{*}/{\rm {GF}}(q)^{*}=\{{\overline {x}}~|~x\in {\rm {GF}}(q^{n+2})^{*}\}$, where ${\rm {GF}}(q^{n+2}){\overline {}}$ and ${\rm {GF}}(q){\overline {}}$ are Galois fiels of order $q^{n+2}{\overline {}}$ and $q{\overline {}}$ respectively and ${\rm {GF}}(q^{n+2})^{*}{\overline {}}$ and ${\rm {GF}}(q)^{*}{\overline {}}$ are their respective multiplicative groups of non-zero elements. Then the set $D=\{{\overline {x}}\in G~|~{\rm {Tr}}_{q^{n+2}/q}(x)=0\}$ is a $((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1)){\overline {}}$-difference set, where ${\rm {Tr}}_{q^{n+2}/q}:{\rm {GF}}(q^{n+2})\rightarrow {\rm {GF}}(q)$ is the trace function ${\rm {Tr}}_{q^{n+2}/q}(x)=x+x^{q}+\cdots +x^{q^{n+1}}$.

References

• W D Wallis, Combinatorial Designs, Marcel Dekker, 1988. ISBN 0-8247-7942-8.
• Daniel Zwillinger, CRC Standard Mathematical Tables and Formulae, CRC Press, 2003. ISBN 1-58488-291-3 (page 246)