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_1d_2^{-1} of elements of D in exactly \lambda ways. A difference set D is said to be cyclic, abelian, non-abelian, etc., if the group G has the corresponding property. A difference set with \lambda = 1 is sometimes called planar or simple.[1] If G is an abelian group 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 term "difference set" arises in this way.

Basic facts

Equivalent and isomorphic difference sets

Two difference sets D_1 in group G_1 and D_2 in group G_2 are equivalent if there is a group isomorphism \psi between G_1 and G_2 such that D_1^{\psi} = \{d^{\psi}\colon d \in D_1 \} = g D_2 for some g \in G_2. The two difference sets are isomorphic if the designs dev(D_1) and dev(D_2) are isomorphic as block designs.

Equivalent difference sets are isomorphic, but there exist examples of isomorphic difference sets which are not equivalent. In the cyclic difference set case, all known isomorphic difference sets are equivalent.[6]

Multipliers

A multiplier of a difference set D in group G is a group automorphism \phi of G such that D^{\phi} = gD for some g \in G. If G is abelian and \phi is the automorphism that maps h \mapsto h^t, then t is called a numerical or Hall multiplier.[7]

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 (this is equivalent to being a multiplier). It is known to be true for p>\lambda when G is an abelian group, and this is known as the First Multiplier Theorem. A more general known result, the Second Multiplier Theorem, says that if D is a (v,k,\lambda)-difference set in an abelian group G of exponent v^* (the least common multiple of the orders of every element), let t be an integer coprime to v. If there exists a divisor m>\lambda of k-\lambda such that for every prime p dividing m, there exists an integer i with t\equiv p^i\ \pmod{v^*}, then t is a numerical divisor.[8]

For example, 2 is a multiplier of the (7,3,1)-difference set mentioned above.

It has been mentioned that a numerical multiplier of a difference set D in an abelian group G fixes a translate of D, but it can also be shown that there is a translate of D which is fixed by all numerical multipliers of D.[9]

Parameters

The known difference sets or their complements have one of the following parameter sets:[10]

Known difference sets

In many constructions of difference sets the groups that are used are related to the additive and multiplicative groups of finite fields. The notation used to denote these fields differs according to discipline. In this section, {\rm GF}(q) is the Galois field of order q, where q is a prime or prime power. The group under addition is denoted by G = ({\rm GF}(q), +), while {\rm GF}(q)^* is the multiplicative group of non-zero elements.

Let q = 4n -1 be a prime power. In the group G = ({\rm GF}(q), +), let D be the set of all non-zero squares.
Let G={\rm GF}(q^{n+2})^*/{\rm GF}(q)^*. 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}}.
In the group G = ({\rm GF}(q), +) \oplus ({\rm GF}(q+2), +), let D = \{(x,y) \colon y = 0 \text{ or } x \text{ and } y \text{ are non-zero and both are squares or both are non-squares} \}.[11]

History

The systematic use of cyclic difference sets and methods for the construction of symmetric block designs dates back to R. C. Bose and a seminal paper of his in 1939.[12] However, various examples appeared earlier than this, such as the "Paley Difference Sets" which date back to 1933.[13] The generalization of the cyclic difference set concept to more general groups is due to R.H. Bruck[14] in 1955.[15] Multipliers were introduced by Marshall Hall Jr.[16] in 1947.[17]

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_1d_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.[18] 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

Notes

  1. van Lint & Wilson 1992, p. 331
  2. Wallis 1988, p. 61 - Theorem 4.5
  3. van Lint & Wilson 1992, p. 331 - Theorem 27.2. The theorem only states point transitivity, but block transitivity follows from this by the second corollary on p. 330.
  4. Colbourn & Dinitz 2007, p. 420 (18.7 Remark 2)
  5. Colbourn & Dinitz 2007, p. 420 (18.7 Remark 1)
  6. Colbourn & Diniz 2007, p. 420 (Remark 18.9)
  7. van Lint & Wilson 1992, p. 345
  8. van Lint & Wilson 1992, p. 349 (Theorem 28.7)
  9. Beth, Jungnickel & Lenz 1986, p. 280 (Theorem 4.6)
  10. Colburn & Dinitz 2007, pp. 422-425
  11. Colbourn & Dinitz 2007, p. 425 (Construction 18.49)
  12. Bose, R.C. (1939), "On the construction of balanced incomplete block designs", Annals of Eugenics 9: 353399, doi:10.1111/j.1469-1809.1939.tb02219.x, JFM 65.1110.04, Zbl 0023.00102
  13. Wallis 1988, p. 69
  14. Bruck, R.H. (1955), "Difference sets in a finite group", Transactions of the American Mathematical Society 78: 464481, doi:10.2307/1993074, Zbl 0065.13302
  15. van Lint & Wilson 1992, p. 340
  16. Hall Jr., Marshall (1947), "Cyclic projective planes", Duke Journal of Mathematics 14: 10791090, doi:10.1215/s0012-7094-47-01482-8, Zbl 0029.22502
  17. Beth, Jungnickel & Lenz 1986, p. 275
  18. Beth, Jungnickel & Lenz 1986, p. 310 (2.8.a)

References

Further reading

Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2006). "Correction to ``Achieving the Welch bound with difference sets"". IEEE Trans. Inf. Theory 52 (7): 3359. doi:10.1109/tit.2006.876214. Zbl 1237.94008. 
This article is issued from Wikipedia - version of the Saturday, March 12, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.