Steiner system

Steiner system

In combinatorial mathematics, a Steiner system (named after Jakob Steiner) is a type of block design.

A Steiner system with parameters "l", "m", "n", written S("l","m","n"), is an "n"-element set "S" together with a set of "m"-element subsets of "S" (called blocks) with the property that each "l"-element subset of "S" is contained in exactly one block. A Steiner system with parameters "l", "m", "n" is often called simply "an S("l","m","n")".

An S(2,3,"n") is called a Steiner triple system, and its blocks are called triples. The number of triples is "n"("n"-1)/6.We can define a multiplication on a Steiner triple system by setting "aa" = "a" for all "a" in "S", and "ab" = "c" if {"a","b","c"} is a triple. This makes "S" into an idempotent commutative quasigroup.

An S(3,4,"n") is sometimes called a Steiner quadruple system. Systems with higher values of "m" are not usually called by special names.

It can be shown that if there is a Steiner system S(2,"m","n"), where "m" is a prime power greater than 1, then "n" = 1 or "m" (mod "m"("m"−1)). In particular, a Steiner triple system S(2,3,"n") must have "n" = 6"k"+1 or 6"k"+3. It is known that this is the only restriction on Steiner triple systems, that is, for each natural number "k", systems S(2,3,6"k"+1) and S(2,3,6"k"+3) exist.

A finite projective plane of order "q", with the lines as blocks, is an S(2, "q"+1, "q"2+"q"+1), since it has "q"2+"q"+1 points, each line passes through "q"+1 points, and each pair of distinct points lies on exactly one line.

Several examples of Steiner systems are closely related to group theory.

The Steiner system S(5, 8, 24)

Particularly remarkable is the Steiner system S(5, 8, 24), also known as the Witt Design. It was discovered by [http://turnbull.mcs.st-and.ac.uk/~history/Mathematicians/Witt.html Ernst Witt] in 1938. This system is connected with many of the sporadic simple groups and with the exceptional 24-dimensional lattice known as the Leech lattice. There are many ways to construct the S(5,8,24). The method given here is perhaps the simplest to describe, and is easy to convert into a computer program. It uses sequences of 24 bits. The idea is to write these down in lexicographic order, missing out any one which differs from some earlier one in fewer than 8 positions. The result looks like this:

000000000000000000000000 000000000000000011111111 000000000000111100001111 000000000000111111110000 000000000011001100110011 000000000011001111001100 000000000011110000111100 000000000011110011000011 000000000101010101010101 000000000101010110101010 . . (next 4083 omitted) . 111111111111000011110000 111111111111111100000000 111111111111111111111111

The list contains 4096 items, which are each code words of the extended binary Golay code. They form a group under the XOR operation. One of them has zero 1-bits, 759 of them have eight 1-bits, 2576 of them have twelve 1-bits, 759 of them have sixteen 1-bits, and one has twenty-four 1-bits. The 759 8-element blocks of the S(5,8,24) (called "octads") are given by the patterns of 1's in the code words with eight 1-bits.

A still more direct approach is taken by running through all 8-element subsets of a 24-element set and skipping any such subset which differs from some octad already found in fewer than four positions.

Departing from 01, 02, 03, ..., 22, 23, 24 one obtains

01 02 03 04 05 06 07 08 01 02 03 04 09 10 11 12 01 02 03 04 13 14 15 16 . . (next 753 octads omitted) . 13 14 15 16 17 18 19 20 13 14 15 16 21 22 23 24 17 18 19 20 21 22 23 24

Each single element occurs 253 times somewhere in some octad. Each pair occurs 77 times. Each triple occurs 21 times. Each quadruple (tetrad) occurs 5 times. Each quintuple (pentad) occurs once. Not every hexad, heptad or octad occurs.

See also

* Kirkman's schoolgirl problem

External links

* [http://hilltop.bradley.edu/~delgado/gandg/SteinerApplet.html Implementation of S(5,8,24)] by Dr. Alberto Delgado, Gabe Hart, and Michael Kolkebeck
* [http://www.xs4all.nl/~jemebius/Steiner5824.htm S(5, 8, 24) Software and Listing] by Johan E. Mebius
* [http://www.geocities.com/dharwadker/witt.html The Witt Design] computed by Ashay Dharwadker

References

* J Steiner, "Combinatorische Aufgabe", Creelle Journal für die reine und angewandte Mathematik 45 (1853), pp 181-182.
* E.F. Assmus Jr and J.D. Key, "Designs and their codes", Cambridge University Press, ISBN 0-521-45839-0. Chap.8.
* D.R. Hughes and F.C. Piper, "Design theory", Cambridge University Press, ISBN 0-521-35872-8. Pp.173-176.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Steiner — is a German surname that is derived from the word Stein , meaning stone. It may refer to: *Adelbert Steiner, fictional character from the video game Final Fantasy IX *Ben Steiner (1921 1988), Major League Baseball player *Cecil C. Steiner,… …   Wikipedia

  • Steiner-Tripel-System — Ein Blockplan ist eine Inzidenzstruktur, die insbesondere in der endlichen Geometrie, der Kombinatorik, sowie der statistischen Versuchsplanung von Bedeutung ist. Inhaltsverzeichnis 1 Definition 2 Beispiele und Eigenschaften 2.1 Parallelismen und …   Deutsch Wikipedia

  • Steiner, Rudolf — (1861–1921)    Sect Founder.    Steiner was the son of a station master in Kaljevec, Yugoslavia, and he was educated at the University of Vienna. Initially he was attracted to Mme Blavatsky’s Theosophical Society, but he was unhappy with its… …   Who’s Who in Christianity

  • Steiner See — Hiltruper See Der nördliche Teil des Sees von Westen aus gesehen. Geographische Lage: Münsterl …   Deutsch Wikipedia

  • Steiner — Stei|ner, Ru|dolf (1861 1925) an Austrian ↑philosopher who believed that human beings can be trained to develop their ↑spiritual powers. He developed his own system for educating children, and started schools, called Steiner schools or Waldorf… …   Dictionary of contemporary English

  • Jakob Steiner — Infobox Scientist name = box width = image width =150px caption = birth date = 18 March , 1796 birth place = Utzenstorf, Canton of Bern death date = April 1, 1863 death place = Bern residence = citizenship = Swiss nationality = ethnicity = field …   Wikipedia

  • Steinersches Tripel-System — Ein Blockplan ist eine Inzidenzstruktur, die insbesondere in der endlichen Geometrie, der Kombinatorik, sowie der statistischen Versuchsplanung von Bedeutung ist. Inhaltsverzeichnis 1 Definition 2 Beispiele und Eigenschaften 2.1 Parallelismen und …   Deutsch Wikipedia

  • Rudolf Steiner — For other people named Rudolf Steiner, see Rudolf Steiner (disambiguation). Rudolf Joseph Lorenz Steiner Full name Rudolf Joseph Lorenz Steiner Born 25(27?) February 1861 Murakirály, Austria Hungary (now Donji Kraljevec, Croatia) …   Wikipedia

  • Pédagogie Steiner-Waldorf — Pour les articles homonymes, voir Steiner. École Waldorf en Allemagne La pédagogie Steiner Waldorf, fondée sur les théories éducatives de Rudolf Steiner, est une de …   Wikipédia en Français

  • Pedagogie Steiner-Waldorf — Pédagogie Steiner Waldorf Pour les articles homonymes, voir Steiner. École Waldorf en Allemagne La pédagogie Steiner Waldorf, fondée sur le …   Wikipédia en Français

Share the article and excerpts

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