- 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 of elements of D in exactly λ ways.
Contents
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 , then 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 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 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 , with coprime t and v, fixes some translate of D if for every prime p dividing m, there exists an integer i such that , 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:
- ((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.
Known difference sets
- Singer -difference set:
- Let , where and GF(q) are Galois fields of order qn + 2 and respectively and and GF(q) * are their respective multiplicative groups of non-zero elements. Then the set is a ((qn + 2 − 1) / (q − 1),(qn + 1 − 1) / (q − 1),(qn − 1) / (q − 1))-difference set, where is the trace function .
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 = {B1,...Bs} of a group G such that the order of G is v, the size of Bi is k for all i, and every nonidentity element of G can be expressed as a product of elements of Bi for some i (i.e. both d1,d2 come from the same Bi) in exactly λ ways.
A difference set is a difference family with s = 1. The parameter equation above generalises to s(k2 − k) = (v − 1)λ.[1] The development of a difference family is a 2-design. Every 2-design with a regular automorphism group is devB for some difference family B
References
- ^ 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.
Categories:
Wikimedia Foundation. 2010.