Difference set

Difference set

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

Basic facts

  • A simple counting argument shows that there are exactly k2k pairs of elements from D that will yield nonidentity elements, so every difference set must satisfy the equation k2k = (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. 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 \mathbb{Z}/7\mathbb{Z} 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 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, with coprime t and v, fixes some translate of D if for every prime p dividing m, there exists an integer i such that t\equiv p^i\ \pmod{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.

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,2n2n,n2n)-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 ((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 GF(q) are Galois fields of order qn + 2 and q~ respectively and {\rm GF}(q^{n+2})^*\overline{} and GF(q) * 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 ((qn + 2 − 1) / (q − 1),(qn + 1 − 1) / (q − 1),(qn − 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}}.

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 d_1d_2^{-1} 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(k2k) = (v − 1)λ.[1] 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 devB for some difference family B


References

  1. ^ Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried "Design theory", Cambridge University Press, Cambridge, 1986

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Difference — may refer to: Difference (album), a 2005 power metal album Difference (computer science), a concept in computer science Difference (heraldry), any systematic way of distinguishing similar coats of arms belonging to members of the same family… …   Wikipedia

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • Difference (philosophy) — Difference is a key concept of continental philosophy, denoting the process or set of properties by which one entity is distinguished from another within a relational field or a given conceptual system. In the Western philosophical system,… …   Wikipedia

  • Difference and Repetition —   …   Wikipedia

  • difference — mid 14c., from O.Fr. difference (12c.) difference, distinction; argument, dispute, from L. differentia diversity, difference, from differentem (nom. differens), prp. of differre to set apart (see DIFFER (Cf. differ)). Sense of a quarrel first… …   Etymology dictionary

  • difference — [n1] dissimilarity, distinctness aberration, alteration, anomaly, antithesis, asymmetry, change, characteristic, contrariety, contrariness, contrast, departure, deviation, digression, discongruity, discrepancy, disparity, dissemblance,… …   New thesaurus

  • Difference engine — For the novel by William Gibson and Bruce Sterling, see The Difference Engine. The London Science Museum s difference engine, built from Babbage s design. The design has the same precision on all columns, but when calculating converging… …   Wikipedia

  • Difference-map algorithm — Iterations 0, 100, 200, 300 and 400 in the difference map reconstruction of a grayscale image from its Fourier transform modulus The difference map algorithm is a search algorithm for general constraint satisfaction problems. It is a meta… …   Wikipedia

  • Set (mathematics) — This article gives an introduction to what mathematicians call intuitive or naive set theory; for a more detailed account see Naive set theory. For a rigorous modern axiomatic treatment of sets, see Set theory. The intersection of two sets is… …   Wikipedia

  • Difference map algorithm — The difference map algorithm is a search algorithm for general constraint satisfaction problems. It is a meta algorithm in the sense that it is built from more basic algorithms that perform projections onto constraint sets. From a mathematical… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”