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_1d_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 symmetric design. In such a design there are $v$ elements (mostly called points) and $v$ blocks. Each block of the design consists of $k$ points, each point is contained in $k$ blocks. Any two blocks have exactly $\lambda$ elements in common and any two points are "joined" by $\lambda$ blocks. The group $G$ then acts as an automorphism group of the design. It is sharply transitive on points and blocks.
  • In particular, if $\lambda=1$, then the difference set gives rise to a projective plane. An example of a (7,3,1) difference set in the group $\mathbb{Z}/7\mathbb{Z}$ is the subset $\{1,2,4\}$. The translates of this difference set gives the Fano plane.
• Since every difference set gives a symmetric design, the parameter set must satisfy the Bruck–Chowla–Ryser theorem.
• Not every symmetric design gives a difference set.

Multipliers

It has been conjectured that if p is a prime dividing $k-\lambda$ and not dividing 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$, with coprime t and v, fixes some translate of $D$ if for every prime p dividing m, there exists an integer i such that $t\equiv p^i\ \pmod{v^*}$, where $v^*$ is the exponent (the least common multiple of the orders of every element) of the group.

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

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)$ are Galois fields of order $q^{n+2}$ and $q~$ respectively and ${\rm GF}(q^{n+2})^*\overline{}$ and ${\rm GF}(q)^*$ 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))$-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}}$.

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

A $(v,k,\lambda,s)$ difference family is a set of subsets $B=\{B_1,...B_s\}$ of a group $G$ such that the order of $G$ is $v$, the size of $B_i$ is $k$ for all $i$, and every nonidentity element of $G$ can be expressed as a product $d_1d_2^{-1}$ of elements of $B_i$ for some $i$ (i.e. both $d_1,d_2$ come from the same $B_i$) in exactly $\lambda$ ways.

A difference set is a difference family with $s=1$. The parameter equation above generalises to $s(k^2-k)=(v-1)\lambda$. The development $dev B = \{B_i+g: i=1,...,s, g \in G\}$ of a difference family is a 2-design. Every 2-design with a regular automorphism group is $dev B$ for some difference family $B$

References

• W. D. Wallis (1988). Combinatorial Designs. Marcel Dekker. ISBN 0-8247-7942-8. 
• Daniel Zwillinger (2003). CRC Standard Mathematical Tables and Formulae. CRC Press. p. 246. ISBN 1-58488-291-3. 
• P. Xia, S. Zhou, G. B. Giannakis (2005). "Achieving the Welch Bound with Difference Sets". IEEE Transactions on Information Theory 51 (5): 1900–1907. doi:10.1109/TIT.2005.846411. http://www.engr.uconn.edu/~shengli/papers/conf05/05icassp.pdf.