Difference set

For the concept of set difference, see complement (set theory), the set of differences of elements of a set ''X'', and [[:see Minkowski sum]].

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 symmetric block 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_{1}d_{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 $devB=\{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 $devB$ for some difference family $B$

See also

• Combinatorial design

References

• Storer, T. (1967). Cyclotomy and difference sets. Chicago: Markham Publishing Company. Zbl 0157.03301.
• Wallis, W.D. (1988). Combinatorial Designs. Marcel Dekker. ISBN 0-8247-7942-8. Zbl 0637.05004.
• Zwillinger, Daniel (2003). CRC Standard Mathematical Tables and Formulae. CRC Press. p. 246. ISBN 1-58488-291-3.
• Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2005). "Achieving the Welch Bound with Difference Sets" (PDF). IEEE Transactions on Information Theory. 51 (5): 1900–1907. doi:10.1109/TIT.2005.846411. ISSN 0018-9448. Zbl 1237.94007.. Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2006). "Correction to ``Achieving the Welch bound with difference sets"". IEEE Trans. Inf. Theory. 52 (7): 3359. Zbl 1237.94008.