Difference set

From Wikipedia, the free encyclopedia

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.

Contents

[edit] Basic facts

  • A simple counting argument shows that there are exactly k2 − k pairs of elements from D that will yield nonidentity elements, so every difference set must satisfy the equation k2 − 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 (a special kind of combinatorial 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.
  • 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.

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 set {1,2,4}. The translates of this difference set gives the Fano plane.

[edit] Multipliers

It has been conjectured that if p is a prime dividing k − λ 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 > λ, 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, 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. For example, 2 is a multiplier of the (7,3,1) difference set mentioned above.

[edit] Parameters

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

  • ((qn + 2 − 1) / (q − 1),(qn + 1 − 1) / (q − 1),(qn − 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.
  • (4n2,2n2 − n,n2 − n)-difference set for some positive integer n.
  • (qn + 1(1 + (qn + 1 − 1) / (q − 1)),qn(qn + 1 − 1) / (q − 1),qn(qn − 1)(q − 1))-difference set for some prime power q and some positive integer n.
  • (3n + 1(3n + 1 − 1) / 2,3n(3n + 1 + 1) / 2,3n(3n + 1) / 2)-difference set for some positive integer n.
  • (4q2n(q2n − 1) / (q − 1),q2n − 1(1 + 2(q2n − 1) / (q + 1)),q2n − 1(q2n − 1 + 1)(q − 1) / (q + 1))-difference set for some prime power q and some positive integer n.

[edit] 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}}.

[edit] 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.

[edit] 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)
  • P. Xia, S. Zhou, and G. B. Giannakis, “Achieving the Welch Bound with Difference Sets,” IEEE Transactions on Information Theory, vol. 51, no. 5, pp. 1900-1907, May 2005.