Difference set

For the set of elements in one set but not another, see relative complement. For the set of differences of pairs of elements, see Minkowski difference.

In combinatorics, a $(v,k,\lambda )$ difference set is a subset $D$ of size $k$ of a group $G$ of order $v$ such that every nonidentity element of $G$ can be expressed as a product $d_{1}d_{2}^{-1}$ of elements of $D$ in exactly $\lambda$ ways. If $G$ is an abelian group and written in additive notation, the defining condition is that every nonzero element of $G$ can be written as a difference of elements of $D$ in exactly $\lambda$ ways. The terminology arises from this setting.

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</math(<math>D+g$ in additive notation).
• The complement of a $(v,k,\lambda )$-difference set is a $(v,v-k,v-2k+\lambda )$-difference set.
• The set of all translates of a difference set $D$ forms a symmetric block design. In such a design there are $v$ elements (usually called points) and $v$ blocks (subsets). 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 simultaneously contained in exactly $\lambda$ blocks. The group $G$ acts as an automorphism group of the design. It is sharply transitive on both 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 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.

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

The known difference sets have 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)^{*}$, where ${\rm {GF}}(q^{n+2})$ and ${\rm {GF}}(q)$ are Galois fields of orders $q^{n+2}$ and $q~$ respectively and ${\rm {GF}}(q^{n+2})^{*}$ and ${\rm {GF}}(q)^{*}$ are their respective multiplicative groups of non-zero elements. Then the set $D=\{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 $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$.

See also

• Combinatorial design

References

• Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), Design Theory, Cambridge: Cambridge University Press, ISBN 0521333342
• Storer, T. (1967). Cyclotomy and difference sets. Chicago: Markham Publishing Company. Zbl 0157.03301.
• van Lint, J.H.; Wilson, R.M. (1992), A Course in Combinatorics, Cambridge: Cambridge University Press, ISBN 0-521-42260-4
• 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.