Difference set

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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 difference set is a subset of size of a group of order such that every nonidentity element of can be expressed as a product of elements of in exactly ways. A difference set is said to be cyclic, abelian, non-abelian, etc., if the group has the corresponding property. A difference set with is sometimes called planar or simple.[1] If is an abelian group written in additive notation, the defining condition is that every nonzero element of can be written as a difference of elements of in exactly ways. The term "difference set" arises in this way.

Basic facts[edit]

  • A simple counting argument shows that there are exactly pairs of elements from that will yield nonidentity elements, so every difference set must satisfy the equation .
  • If is a difference set, and , then is also a difference set, and is called a translate of ( in additive notation).
  • The complement of a -difference set is a -difference set.[2]
  • The set of all translates of a difference set forms a symmetric block design, called the development of and denoted by . In such a design there are elements (usually called points) and blocks (subsets). Each block of the design consists of points, each point is contained in blocks. Any two blocks have exactly elements in common and any two points are simultaneously contained in exactly blocks. The group acts as an automorphism group of the design. It is sharply transitive on both points and blocks.[3]
    • In particular, if , then the difference set gives rise to a projective plane. An example of a (7,3,1) difference set in the group is the subset . 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.[4]
  • Not every symmetric design gives a difference set.[5]

Equivalent and isomorphic difference sets[edit]

Two difference sets in group and in group are equivalent if there is a group isomorphism between and such that for some . The two difference sets are isomorphic if the designs and 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[edit]

A multiplier of a difference set in group is a group automorphism of such that for some . If is abelian and is the automorphism that maps , then is called a numerical or Hall multiplier.[7]

It has been conjectured that if p is a prime dividing and not dividing v, then the group automorphism defined by fixes some translate of D (this is equivalent to being a multiplier). It is known to be true for when 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 is a -difference set in an abelian group of exponent (the least common multiple of the orders of every element), let be an integer coprime to . If there exists a divisor of such that for every prime p dividing m, there exists an integer i with , 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 in an abelian group fixes a translate of , but it can also be shown that there is a translate of which is fixed by all numerical multipliers of .[9]

Parameters[edit]

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

  • -difference set for some prime power and some positive integer . These are known as the classical parameters and there are many constructions of difference sets having these parameters.
  • -difference set for some positive integer . Difference sets with v = 4n - 1 are called Paley-type difference sets.
  • -difference set for some positive integer . A difference set with these parameters is a Hadamard difference set.
  • -difference set for some prime power and some positive integer . Known as the McFarland parameters.
  • -difference set for some positive integer . Known as the Spence parameters.
  • -difference set for some prime power and some positive integer . Difference sets with these parameters are called Davis-Jedwab-Chen difference sets.

Known difference sets[edit]

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, is the Galois field of order , where is a prime or prime power. The group under addition is denoted by , while is the multiplicative group of non-zero elements.

  • Paley -difference set:
Let be a prime power. In the group , let be the set of all non-zero squares.
  • Singer -difference set:
Let . Then the set is a -difference set, where is the trace function .
  • Twin prime power -difference set when and are both prime powers:
In the group , let [11]

History[edit]

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

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

A difference family is a set of subsets of a group such that the order of is , the size of is for all , and every nonidentity element of can be expressed as a product of elements of for some (i.e. both come from the same ) in exactly ways.

A difference set is a difference family with . The parameter equation above generalises to .[18] The development of a difference family is a 2-design. Every 2-design with a regular automorphism group is for some difference family .

See also[edit]

Notes[edit]

  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: 353–399, 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: 464–481, 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: 1079–1090, 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[edit]

Further reading[edit]

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. 
  • Zwillinger, Daniel (2003). CRC Standard Mathematical Tables and Formulae. CRC Press. p. 246. ISBN 1-58488-291-3.