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.

1 Basic facts
2 Multipliers
3 Parameters
4 Known difference sets
5 References

[edit] 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)λ$ .
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 combinatorial design. Each block of the design has $k$ elements, and any two blocks have exactly $λ$ elements in common. In particular, if $λ = 1$ , then the difference set gives rise to a projective plane.
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.

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.

[edit] 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$ .
$(4 n - 1,2 n - 1, n - 1)$ -difference set for some positive integer $n$ .
$(4 n 2,2 n 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$ .
$(4 q 2 n (q 2 n - 1) / (q - 1), q 2 n - 1 (1 + 2(q 2 n - 1) / (q + 1)), q 2 n - 1 (q 2 n - 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] 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)

Retrieved from "http://en.wikipedia.org../../../d/i/f/Difference_set.html"

Category: Combinatorics