Difference set

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

In combinatorics, a (v,k,λ) 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 λ ways.

Basic facts

• A simple counting argument shows that there are exactly k² − k pairs of elements from D that will yield nonidentity elements, so every difference set must satisfy the equation k² − k = (v − 1)λ.
• 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 λ elements in common and any two points are "joined" by λ blocks. The group G then acts as an automorphism group of the design. It is sharply transitive on points and blocks.
  • In particular, if λ = 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 − λ 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 > λ, 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 > λ of k − λ. 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ⁿ − 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²,2n² − n,n² − n)-difference set for some positive integer n.
• (q^{n + 1}(1 + (q^{n + 1} − 1) / (q − 1)),qⁿ(q^{n + 1} − 1) / (q − 1),qⁿ(qⁿ − 1)(q − 1))-difference set for some prime power q and some positive integer n.
• (3^{n + 1}(3^{n + 1} − 1) / 2,3ⁿ(3^{n + 1} + 1) / 2,3ⁿ(3ⁿ + 1) / 2)-difference set for some positive integer n.
• (4q²ⁿ(q²ⁿ − 1) / (q − 1),q^{2n − 1}(1 + 2(q²ⁿ − 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 GF(q) are Galois fields of order q^{n + 2} and $q~$ respectively and ${\rm GF}(q^{n+2})^*\overline{}$ and 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ⁿ − 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,λ,s) difference family is a set of subsets B = {B₁,...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₁,d₂ come from the same B_i) in exactly λ ways.

A difference set is a difference family with s = 1. The parameter equation above generalises to s(k² − k) = (v − 1)λ.^[1] 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 devB for some difference family B

References

1. ^ Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried "Design theory", Cambridge University Press, Cambridge, 1986

• 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.