組合せ数学において、シュタイナーシステムまたはシュタイナー系 (Steiner system, ヤコブ・シュタイナーに因んだ命名)はブロックデザインの一種で、とくにt-デザインにおいて λ = 1 であり t = 2 または (近年では) t ≥ 2 の場合を指す。
パラメータ t, k, n をもつシュタイナーシステムを S(t,k,n) と表記し、これは n 個の元からなる集合 S と、k 個の元をもつ S の部分集合（ブロックと呼ぶ）からなる集合で、t 個の元からなる S の部分集合すべてがそれぞれちょうど 1 個のブロックに含まれるという性質を持つものを指す。ブロックデザインの別記法を使えば S(t,k,n) は t-(n,k,1) デザインと呼ぶことができる。
この定義は比較的新しいものである。シュタイナーシステムの古典的定義では、これに加えて k = t + 1 という条件があった。S(2,3,n) はシュタイナー三元系 (Steiner triple system) またはシュタイナーの三つ組系 (Steiner triad system) と呼ばれており (現在でもそう呼ばれる)、S(3,4,n) はシュタイナー四元系 (Steiner quadruple system)と呼ばれ、以下同様に呼ばれる。定義が一般化されてからは、これらの呼び名を使わない場合が増えている。
デザイン理論における長年の問題として、非自明な (つまり、t < k < n である) シュタイナーシステムで t ≥ 6 のものが存在するかという問題と、t = 4, 5 のものが無限に存在するかという問題がある。どちらの問題も2014年ににより証明されたが、彼の証明は非構成的であり、2019年現在、大きな t の値を持つシュタイナーシステムの実例は知られていない。
シュタイナーシステムのタイプ
位数 の有限射影平面は、 のブロックを線と見なしたものである。なぜなら、全部で 個の点が存在し、どの線も 個の点を通り、どの異なる 2 点に対しても、それらを結ぶ線がちょうど 1 本だけ存在するからである。
位数 の有限アフィン平面は、 のブロックを線と見なしたものである。位数 のアフィン平面は、同じ位数の射影平面から１個のブロックと、そのブロックに含まれる点を全て取り除くことによって得られる。このようにして取り除くブロックが異なれば、同型でないアフィン平面が得られる。
S(3,4,n) はシュタイナー四元系と呼ばれる。S(3,4,n) が存在する必要十分条件は、n 2 または 4 (mod 6) であることである。これらのシステムの略称として、SQS(n) がしばしば用いられる。同型を除き、SQS(8) と SQS(10) はそれぞれ 1 種類のみ、SQS(14) は 4 種類、SQS(16) は 1,054,163 種類存在する。
S(4,5,n) はシュタイナー五元系と呼ばれる。そのようなシステムが存在することの必要条件として n 3 または 5 (mod 6) があるが、これは全ての古典的シュタイナーシステムに当てはまる考察に由来するものである。追加の必要条件として n 4 (mod 5) があり、これはブロックの個数が整数でなければならないという制約からくるものである。十分条件は知られていない。位数11のシュタイナー五元系は1種類のみ存在するが、位数15および17の五元系は存在しない。位数 23, 35, 47, 71, 83, 107, 131, 167, 243 のシステムの存在が知られている。(2011年現在) 存在するかどうかが不明な最小の位数は 21 である。
シュタイナー三元系 S(2,3,n) はシュタイナー三元系 (Steiner triple system) といい、そのブロックは 三元 (triples)と呼ばれる。位数 n のシュタイナー三元系を STS(n) と略する例はよく見られる。三元の中に現れる元のペアの総数は n(n-1)/2 なので、三元の総数は n(n−1)/6 となる。このことより、n は 6k+1 または 6k+3 (k は自然数) の形となる。n に対するこの条件は、S(2,3,n) が存在するための十分条件でもあることはとT. スコーレムT. Skolem. Some remarks on the triple systems of Steiner. Math. Scand. 6 (1958), 273–280.によって証明された。位数 2 の射影平面（ファノ平面) は STS(7) であり、位数 3 の は STS(9) である。同型を除いて、STS(7) および STS(9) はそれぞれ 1 種類、STS(13) は 2 種類、STS(15) は 80 種類、STS(19) は 11,084,874,829 種類存在する。
シュタイナー三元系の集合 S 上に、以下のようにして乗法を定義することができる: S に含まれる全ての a に対して aa = a とし、三元 {a,b,c} に対して ab = c と定義する。この演算の下で S は冪等で交換法則を満たす準群となる。それに加え、ab = c であれば bc = a および ca = b が成り立つ。逆に、これらの特性をもつ任意の（有限）準群はシュタイナー三元系の条件を満たす。この追加条件を満たす冪等で可換な準群をシュタイナー準群 (Steiner quasigroup) と呼ぶ。
分解可能なシュタイナーシステム S(2,3,n) システムの一部は、それらの三元からなる集合を、(n/3) 個の互いに素な三元からなる (n-1)/2 個の集合に分割することができる。この性質を分解可能 (resolvable) と呼び、分解可能なシュタイナーシステムは、この種のシステムをシュタイナー以前に研究していたトーマス・カークマンに因んでカークマン三元系 (Kirkman triple systems) と呼ばれる。Dale Mesner, Earl Kramer らは互いに交わりを持たないシュタイナーシステムの集まり（すなわち、その集まりに含まれるシュタイナーシステムが同一の三つ組を含まない）を研究した。9 個の元からなる集合に含まれる 84 個の三つ組すべてから、7 個の異なる S(2,3,9) システムを作成できる (Bays 1917, Kramer & Mesner 1974)。7 個の集合への分割方法は 15360 通りあり、ラベルの付け替えにより、重複度 6720 と 8640 の 2 種類の互いに非同型な解が得られることも知られている。
同様な問いとして、13 個の互いに素な S(2,3,15) システムを見つける問題は、の拡張としてジェームス・シルヴェスターにより、「カークマンの女学生たちは、13 週の全期間中、同じ 3 人組を組まずに行くことができるか」という形で提出された。この問題は、1974 年に R.H.F. Denniston により解決された。彼の解では、最初の 1 週間を以下のように割り当てる。
Day 1 ABJ CEM FKL HIN DGO Day 2 ACH DEI FGM JLN BKO Day 3 ADL BHM GIK CFN EJO Day 4 AEG BIL CJK DMN FHO Day 5 AFI BCD GHJ EKN LMO Day 6 AKM DFJ EHL BGN CIO Day 7 BEF CGL DHK IJM ANO
A から O のラベルの振られた少女たちに対し、残りの週の割り当ては、直前の週の A を B, B を C, … L を M のように順送りにし、M を A に置き換えつつ N と O を変えずに構成される。このルールに従って第 13 週の解のラベル貼り替えを行えば、第 1 週の解に戻る。Denniston は彼の論文の中で、レスター大学のElliott 4130コンピュータで探索に 7 時間かかり、解が唯一であることは未確認であることを報告している。シルヴェスターの問題の同型ではない解の個数は、2021 年現在未だ知られていない。
性質 の定義より、 であることは明らかである（定義上は等号も可能であり、その場合は自明なシステムとなる）。
もし が存在するならば、特定の元を含む全てのブロックを取ってそれらを捨て去れば、派生システム を得ることができる。それゆえ、 の存在は、 が存在するための必要条件である。
個の元からなる の部分集合の個数は であり、各ブロックに含まれる 個の元からなる部分集合の個数は である。あらゆる 個の元を含むあらゆる部分集合がちょうど 1 個ずつ含まれるので、ブロックの個数を とおくと であるので、 となる。また、任意の特定の元を含むブロックの個数を とおくと、特定の元を含む 元部分集合の個数についても、上と同様の議論から より、
が導かれる。これらの定義から等式 が従う。 と が整数であるためには、 の存在が必要条件である。他の任意のブロックデザインと同様に、 はシュタイナーシステムにおいても真である。
シュタイナーシステムのパラメータ と、サイズ で、少なくとも 1 個のブロックに含まれる部分集合が与えられたとき、その部分集合との共通元を指定された個数だけ含むブロックの個数は、パスカルの三角形を使って計算することができる。とくに、ある特定のブロックとの共通元を所定の個数だけ含むブロックの個数は、どの特定のブロックを選ぶかには依存しない。
i 個の点（元）からなる集合を含むブロックの個数は以下の通りである:
もし、シュタイナーシステム で、 が１より大きい素数冪であるものが存在するなら、 1 または が成り立つことが証明可能である。とくに、シュタイナー三元系 の元の個数は または でなければならない。既に述べたように、これはシュタイナー三元系における唯一の制約である。すなわち、任意の自然数 に対し、システム および が存在する。
歴史 シュタイナー三元系は、1844年に最初ににより、Lady's and Gentlemen's Diary の懸賞問題 #1733 において定義された。出題された問題は により解かれた。1850 年、カークマンはとして知られる問題の一バリエーションを出題した。その問題は、追加の性質（分解可能性）をもつ三元系の存在を問うものだった。カークマンの業績を知らずに、は三元系を再定義した。シュタイナーの業績のほうがより広く知られることとなり、彼がシステム命名の栄誉に浴することとなった。
1910年にがシュタイナー三元系のグラフ表現を与えた。
マシュー群 シュタイナーシステムの幾つかの実例は群論と深い関わりがある。とくに、と呼ばれる有限単純群は、以下のシュタイナーシステムの自己同型群として構成される:
はシュタイナーシステム S(4,5,11) の自己同型群である。 はシュタイナーシステム S(5,6,12) の自己同型群である。 はシュタイナーシステム S(3,6,12) の自己同型群の、唯一の指数 2 の部分群である。 はシュタイナーシステム S(4,7,23) の自己同型群である。 はシュタイナーシステム S(5,8,24) の自己同型群である。
シュタイナーシステム S(5, 6, 12) シュタイナーシステム S(5,6,12) はただ 1 通りのみ存在し、その自己同型群はマシュー群 M12 である。この文脈では、 W12 と表記される。
射影直線による構成法 この構成法は Carmichael (1937) による。
11 個の元からなる有限体 11（つまり、整数を mod 11 で同一視したもの）に、新たに一つの と呼ばれる元を付け加える。12 個の元からなるこの集合 は、11 上の射影直線を通る点の集合と形式的に同一視できる。以下のような 6 個の元からなる部分集合
を "ブロック" と呼ぶ（これには、 および 5 個の非ゼロの 11 上の平方数が含まれる)。このブロックから、一次分数変換
（ここで は 11 の元で を満たすもの）を繰り返し適用することにより、S(5,6,12) を得る。通常の慣習に従い および と定義すれば、これらの関数は をそれ自身に写像する。幾何学の言葉で言えば、これらは射影直線の射影変換である。これらは合成を演算として群をなし、その群は位数 660 の射影特殊線形群 PSL(2,11) である。この群には、開始ブロックを集合として固定する元がちょうど 5 個存在する。すなわち となる元および、 であるから となる元である。軌道-固定部分群定理より、このブロックには 660/5 = 132 個の像が存在することが分かる。集合 S に作用するこの群が多重推移的であることの帰結として、 の任意の 5 個の元からなる部分集合は、6 個の元からなるこれら 132 個の像のどれかにちょうど 1 度ずつ現れる。
「子猫」を用いた構成法 これとは異なる W12 の構成法が、一度に 1 個ずつブロックを書き下せる「手動計算機」として R.T. Curtis により発案された '子猫' を用いて得られる。子猫法は、3×3 マスの数字をあるパターンに従って並べることに基づいていて、このマス目がベクトル空間 F3×F3に、パターンがその空間上のアフィン幾何である S(2,3,9) システムに相当する。
K6 グラフの因子分解を用いた構成法 完全グラフ K6 の 同士の関係は S(5,6,12) を生成する。K6 グラフには 6 個の頂点、15 本の辺、15 個の完全被覆が含まれ、6 種の異なる 1-因子分解（グラフの辺を互いに素な完全被覆に分割する方法）が存在する。（123456 とラベル付けた）頂点集合と（ABCDEF とラベル付けた）因子分解の集合がそれぞれ 1 個ずつのブロックを提供する。因子分解のペア一つごとに、それらが共有している完全被覆はちょうど 1 個ずつ存在する。因子分解 A と B が辺 12, 34 と 56 を含む完全被覆を共有していると仮定しよう。完全被覆に含まれる各辺をそれぞれ因子分解のラベルで置き換えることにより、3 個の新しいブロック AB3456, 12AB56 および 1234AB が得られる。同様にして、因子分解のラベルを、それらが共有している被覆に含まれる対応する辺のラベルで置き換えることにより 12CDEF, 34CDEF および 56CDEF の３つが新たに得られる。これを因子分解の 15 個のペアの全てに対して行うことにより、90 個のブロックを新たに得ることができる。最後に、12 個の元から 6 個を選ぶ 通りの全組み合わせから、これまでに得た 92 個のブロックと、5 個以上の元を共有しているものを全て取り除く。ちょうど 40 個のブロックが残るので、その結果、S(5,6,12) に含まれる 個のブロックを得る。この手続きがうまくいくのは、が存在し、これが頂点を因子分解に、そして辺を分割に写像するからである。頂点の並べ替えは、外部自己同型に従って、異なる因子分解を引き起こす。
シュタイナーシステム S(5, 8, 24) シュタイナーシステム S(5, 8, 24)（別名ヴィットデザインやヴィットジオメトリとも呼ばれる）を最初に記載したのは であり、 により再発見された。このシステムは多数のと、と呼ばれるな 24 次元格子に関係している。S(5, 8, 24) の自己同型群はであり、この文脈ではこのデザインは W24（"W" は "Witt" の頭文字）と呼ばれる。
直接的な辞書順の生成 24 個の元からなる集合の、8 個の元からなる部分集合の全てを辞書順に生成し、先行する部分集合のどれかとの違いが4要素に満たないものを全て取り除く。
集合の元 01, 02, 03, ..., 22, 23, 24 から生成される八つ組 (octad) のリストは以下のようになる: :: 01 02 03 04 05 06 07 08 :: 01 02 03 04 09 10 11 12 :: 01 02 03 04 13 14 15 16 :: . :: .（途中 753 個の八つ組は省略） :: . :: 13 14 15 16 17 18 19 20 :: 13 14 15 16 21 22 23 24 :: 17 18 19 20 21 22 23 24 どの個別の元も、どれかの八つ組の中に 253 回現れる。どのペアも 77 回出現する。どの三元も 21 回出現する。どの四元（四つ組, tetrad）も 5 回出現する。どの五元 (五つ組, pentad）も 1 回ずつ出現する。六つ組、七つ組および八つ組は一部のものしか出現しない。
2 元ゴレイ符号からの構成法 24 ビット 2 元ゴレイ符号は 4096 個の符号語からなり、その中でハミング重みが 8 である 759 個の元が S(5,8,24) システムに対応する。
ゴレイ符号はさまざまな方法で構成することができるが、一例として、24 ビットの二進文字列を全て辞書順に生成し、その前のどれかとの違いが 8 ビットに満たないものを取り除く方法がある。その結果は以下のようになる: 000000000000000000000000 000000000000000011111111 000000000000111100001111 . . (残り 4090 個の 24 ビット列は省略) . 111111111111000011110000 111111111111111100000000 111111111111111111111111 これらの符号語は XOR 演算のもとに群をなす。
射影直線による構成法 この構成法は Carmichael (1931) による。
23 個の元からなる有限体 23（つまり、整数を mod 23 で同一視したもの）に、新たに一つの と呼ばれる元を付け加える。24 個の元からなるこの集合 は、23 上の射影直線を通る点の集合と形式的に同一視できる。以下のような 8 個の元からなる部分集合
を "ブロック" と呼ぶ（2 元ゴレイ符号 の符号語の八つ組を任意に取り、それを平方剰余符号と見なすことができる)。このブロックから、一次分数変換
（ここで は 23 の元で を満たすもの）を繰り返し適用することにより、S(5,8,24) システムの他のブロックを得る。通常の慣習に従い および と定義すれば、これらの関数は をそれ自身に写像する。幾何学の言葉で言えば、これらは射影直線の射影変換である。これらは合成を演算として群をなし、その群は位数 6072 の射影特殊線形群 PSL(2,23) である。この群には、開始ブロックを集合として固定する元がちょうど 8 個存在する。軌道-固定部分群定理より、このブロックには 6072/8 = 759 個の像が存在する。これらが S(5,8,24) の八つ組を構成する。
Miracle Octad Generator による構成法 (MOG) は、指定された部分集合を含むような八つ組 (octad) を生成するツールであり、行ごとに特定の重みが割り振られた 4×6 の配列で、とくに、8 元からなる部分集合が S(5,8,24) の八つ組となるように、以下の三つのルールに従った 35 個の図式からなる。まず、6 個の列のそれぞれは同じパリティを持っていなければならない。つまり、各列に含まれる奇数セルの個数が全て同じであるか、全てのセルが偶数でなければならない。二番目に、列のパリティだけではなく最上行のパリティも同じでなければならない。三番目に、各行は位数4の有限体上の演算でそれぞれウェイト 0,1,2,3 を掛けられ、6 列のそれぞれに対して、列ごとの和をの定義に従って求める。結果として得られた列和は (ここで a, b, c も位数4の有限体の元）の形の の語を構成することになる。列和のパリティが行和のパリティと一致しない場合や、正しい hexacode の語を形成する a, b, c の組合せが存在しない場合は、8個の元からなるその部分集合は S(5,8,24) の一員ではない。
MOG は、8 個の元からなる集合を 4 個の元からなる集合二つに分割する 35 通りの方法と、ファノ3次元空間 PG(3,2) 上の 35 本の直線の間の全単射 (Conwell 1910, "The three-space PG(3,2) and its group") に基づいている。幾何学的には、4 次元有限アフィン空間を表現する 4×4 の配列を各 4 個のセルから成る 4 個の異なるグループに分割し、各グループが平行な部分空間を成すようにする 35 通りの方法 (Cullinane, "Symmetry Invariance in a Diamond Ring", Notices of the AMS, pp A193-194, Feb 1979) にも関係している。
脚注
引用文献
参照文献
. 2nd ed. (1999) .
.
.
外部リンク
Steiner systems by Andries E. Brouwer Implementation of S(5,8,24) by Dr. Alberto Delgado, Gabe Hart, and Michael Kolkebeck S(5, 8, 24) Software and Listing by Johan E. Mebius