シュタイナーシステム

組合せ 数学において、シュタイナーシステム（ヤコブ・シュタイナーにちなんで名付けられた）は、ブロック設計の一種であり、具体的には、λ = 1 かつt = 2 または（最近では）t ≥ 2 のt 設計です。

パラメータt、k、nを持つシュタイナーシステムはS( t、k、n ) と表記され、n要素の集合 Sと、 Sのk要素のサブセット(ブロックと呼ばれる)の集合で構成され、 Sのt要素の各サブセットが 1 つのブロックに含まれるという特性があります。ブロック設計の別の表記では、 S( t、k、n ) はt -( n、k、1) 設計になります。

この定義は比較的新しいものです。シュタイナーシステムの古典的な定義でも、k = t + 1 である必要がありました。S(2,3, n ) は (現在でも)シュタイナー三重(または三連)システムと呼ばれ、S(3,4, n ) はシュタイナー四重システムと呼ばれます。定義が一般化されたため、この命名システムは厳密には守られなくなりました。

設計理論における長年の問題は、 t ≥ 6となる非自明なシュタイナー系（非自明とはt < k < nを意味する）が存在するかどうか、またt = 4 または 5 となる系が無限に存在するかどうかであった。 ^{[1]両方の存在は 2014 年に}ピーター・キーヴァッシュによって証明された。彼の証明は非構成的であり、2019 年現在、 tの大きな値となる実際のシュタイナー系は知られていない。^{[2] [3] [4]}

直線をブロックとする、位数qの有限射影平面は、 q ² + q + 1個の点を持ち、各直線が q + 1 個の点を通り、異なる点の各ペアが正確に 1 本の直線上にあるため、S ( 2 , q + 1 , q ² + q + 1)です。

線をブロックとするq次数の有限アフィン平面はS(2,  q ,  q ² )です。q次数のアフィン平面は、同じ次数の射影平面から 1 つのブロックとそのブロック内のすべての点を削除することで得られます。 この方法で削除するブロックを変更すると、非同型アフィン平面が生成される可能性があります。

S(3,4, n )はシュタイナー四重極系と呼ばれる。S(3,4, n )が存在するための必要十分条件はnが2または4（6を法とする）であることである。これらの系にはSQS( n )という略語がよく使われる。同型性を除いて、SQS(8)とSQS(10)は一意であり、SQS(14)は4つ、SQS(16)は1,054,163個存在する。^[5]${\displaystyle \equiv}$

S(4,5, n ) はシュタイナー五重体システムと呼ばれる。このようなシステムが存在するための必要条件は、n 3 または 5 (mod 6) であり、これはすべての古典的なシュタイナーシステムに適用される考慮事項から来ている。追加の必要条件は n 4 (mod 5)であり、これはブロックの数が整数でなければならないという事実から来ている。十分な条件はわかっていない。次数 11 のシュタイナー五重体システムは唯一存在するが、次数 15 や次数 17 のシステムはない。^[6]次数 23、35、47、71、83、107、131、167、および 243 のシステムが知られている。存在が知られていない最小の次数 (2011 年現在) は 21 である。 ${\displaystyle \equiv}$ ${\displaystyle \not \equiv}$

S(2,3, n ) はシュタイナー三重系と呼ばれ、そのブロックは三重体と呼ばれます。 n次のシュタイナー三重系はSTS( n )と略されるのが一般的です。ペアの総数はn(n-1)/2で、そのうち 3 つが三重体に現れるので、三重体の総数はn ( n −1)/6 です。これは、あるkに対してn が6k+1または6k + 3の形式でなければならないことを示しています。 nに関するこの条件がS(2,3, n )の存在に十分であるという事実は、 Raj Chandra Bose ^[7]と T. Skolem ^[8]によって証明されました。次数 2 の射影平面 (ファノ平面) は STS(7) であり、次数 3 のアフィン平面は STS(9) です。同型性を除いて、STS(7)とSTS(9)は一意であり、STS(13)は2つ、STS​​(15)は80個、STS(19)は11,084,874,829個存在する。^[9]

シュタイナー三元系を使って集合S上の乗法を定義するには、 S内のすべての a に対してaa = aとし、{ a , b , c } が三元集合である場合にab = c と設定する。これにより、 S はべき等性、可換性の準群となる。また、 ab = cであればbc = aかつca = b となるという追加の特性も持つ。^{[注 1]} 逆に、これらの特性を持つ任意の（有限）準群はシュタイナー三元系から生じる。この追加特性を満たす可換べき等性準群はシュタイナー準群と呼ばれる。^[10]

S(2,3,n) システムの一部は、その 3 重項を (n-1)/2 セットに分割することができ、各セットは (n/3) 個の対で互いに素な 3 重項を持つ。これは分解可能と呼ばれ、そのようなシステムは、シュタイナーより前にそのような分解可能なシステムを研究したThomas Kirkmanにちなんで、カークマン 3 重項システムと呼ばれる。デール メスナー、アール クレイマー、およびその他の人々は、互いに素な (つまり、そのようなコレクション内の 2 つのシュタイナー システムが共通の 3 重項を共有しない) シュタイナー 3 重項システムのコレクションを調査した。9 セット上の 84 個の 3 重項すべてをカバーする 7 つの異なる S(2,3,9) システムを生成できることが知られている (Bays 1917、Kramer & Mesner 1974)。また、そのような 7 集合の解を見つけるには 15360 通りの方法があり、それらは再ラベル付けによって 2 つの非同型解に簡約され、重複度はそれぞれ 6720 と 8640 になることもわかっていました。

13の異なる互いに素なS(2,3,15)システムを見つけるための対応する問題は、カークマンの女子生徒問題の拡張として1860年にジェームズ・シルベスターによって出題されました。つまり、カークマンの女子生徒は、1学期全体で3人組の女子生徒が重複することなく、13週間の学期全体にわたって行進できるかどうかです。この問題は1974年にRHFデニストンによって解決され、^[11]彼は第1週を次のように構築しました。

1日目 ABJ CEM FKL HIN DGO
2日目 ACH DEI FGM JLN BKO
3日目 ADL BHM GIK CFN EJO
4日目 AEG BIL CJK DMN FHO
5日目 AFI BCD GHJ EKN LMO
6日目 AKM DFJ EHL BGN CIO
7日目 BEF CGL DHK IJM ANO

彼はAからOのラベルが付けられた女の子について、AをBに、BをCに、... LをMに、そしてMをAに戻して、各週の解を直前の解から構築したが、NとOは変更しなかった。第13週の解は、その再ラベル付けを受けると、第1週の解に戻る。デニストンは論文の中で、彼が採用した探索にはレスター大学のエリオット4130コンピューターで7時間かかったと報告し、上記の解を見つけた時点で、一意性の確立は求めず、直ちに探索を終了した。シルベスターの問題に対する同型でない解の数は、2021年現在不明である。

S( t , k , n )の定義から、次のことが明らかです。(等式は技術的には可能ですが、単純なシステムにつながります。) ${\displaystyle 1<t<k<n}$

S( t , k , n )が存在する場合、特定の要素を含むすべてのブロックを取り、その要素を破棄すると、派生システム S( t −1, k −1, n −1)が得られます。したがって、S( t −1, k −1 , n −1)の存在は、 S( t , k , n )の存在の必要条件です。

Sのt要素サブセットの数は であり、各ブロックのt要素サブセットの数はである。すべてのt要素サブセットは 1 つのブロックに含まれるため、 、または ${\displaystyle {\tbinom {n}{t}}}$${\displaystyle {\tbinom {k}{t}}}$${\displaystyle {\tbinom {n}{t}}=b{\tbinom {k}{t}}}$

${\displaystyle b={\frac {\tbinom {n}{t}}{\tbinom {k}{t}}}={\frac {n(n-1)\cdots (n-t+1)}{k(k-1)\cdots (k-t+1)}},}$

ここで、bはブロックの数です。特定の要素を含むt要素の部分集合についても同様の推論により、または ${\displaystyle {\tbinom {n-1}{t-1}}=r{\tbinom {k-1}{t-1}}}$

${\displaystyle r={\frac {\tbinom {n-1}{t-1}}{\tbinom {k-1}{t-1}}}$=${\displaystyle {\frac {(n-t+1)\cdots (n-2)(n-1)}{(k-t+1)\cdots (k-2)(k-1)}},}$

ここで、r は任意の要素を含むブロックの数です。これらの定義から、式が導かれます。S ( t , k , n )が存在するためには、 bとrが整数であることが必須条件です。あらゆるブロック設計と同様に、シュタイナー システムではフィッシャーの不等式が当てはまります。 ${\displaystyle bk=rn}$ ${\displaystyle b\geq n}$

シュタイナーシステムS( t,k,n )のパラメータと、少なくとも1つのブロックに含まれるサイズの部分集合が与えられれば、パスカルの三角形を構築することによって、その部分集合と固定数の要素で交差するブロックの数を計算できる。^[12] 特に、任意の数の要素で固定ブロックと交差するブロックの数は、選択されたブロックとは無関係である。 ${\displaystyle t'\leq t}$

i要素の点集合を含むブロックの数は次のようになります。

${\displaystyle \lambda _{i}=\left.{\binom {ni}{ti}}\right/{\binom {ki}{ti}}{\text{ for }}i=0,1,\ldots ,t,}$

シュタイナーシステムS(2, k , n )（k は1 より大きい素数累乗）が存在する場合、n ≒ 1 またはk (mod k ( k −1))であることが示されます。特に、シュタイナー三重システムS(2, 3, n )はn = 6 m + 1 または 6 m + 3でなければなりません。そして、すでに述べたように、これがシュタイナー三重システムに対する唯一の制約であり、つまり、各自然数mに対して、システムS(2, 3, 6 m + 1)とS(2, 3, 6 m + 3)が存在します。 ${\displaystyle \equiv}$

シュタイナーの三重システムは、1844年にウェズリー・SB・ウールハウスが『淑女と紳士の日記』の懸賞問題#1733で初めて定義した。 ^[13]提起された問題はトーマス・カークマン（1847）によって解決された。1850年にカークマンは、カークマンの女子高生問題 として知られる問題のバリエーションを提起した。これは、三重システムが追加の特性（解決可能性）を持つことを求めるものである。カークマンの研究を知らなかったヤコブ・シュタイナー （1853）は、三重システムを再導入し、この研究がより広く知られるようになったため、システムは彼にちなんで名付けられた。

1910年にジェフリー・トーマス・ベネットはシュタイナーの三重システムの図式表現を提示した。^{[14] [15] [16]}

シュタイナー系のいくつかの例は群論と密接に関係している。特に、マシュー群と呼ばれる有限単純群はシュタイナー系の自己同型群として生じる 。

• マシュー群M ₁₁はS(4,5,11)シュタイナー系の自己同型群である。
• マシュー群M ₁₂はS(5,6,12)シュタイナー系の自己同型群である。
• マシュー群M ₂₂は、S(3,6,22)シュタイナー系の自己同型群の唯一の指数2の部分群である。
• マシュー群M ₂₃はS(4,7,23)シュタイナー系の自己同型群である。
• マシュー群M24_はS(5,8,24)シュタイナー系の自己同型群である。

唯一のS(5,6,12)シュタイナー系が存在する。その自己同型群はマシュー群M ₁₂であり、その文脈ではW ₁₂と表記される。

この構築はカーマイケル（1937）によるものである。^[17]

有限体F ₁₁の 11 個の元(つまり 11 を法とする整数)に、新しい元∞を追加します。この 12 個の元の集合Sは、 F ₁₁上の射影直線の点と形式的に同一視できます。次のサイズ 6 の特定の部分集合を ∞ と呼びます。

${\displaystyle \{\infty ,1,3,4,5,9\},}$

「ブロック」（ F ₁₁の5つの非ゼロの正方形とともに∞を含む）。このブロックから、線形分数変換を繰り返し適用することで、S （5、6、12）システムの他のブロックを取得します。

${\displaystyle z'=f(z)={\frac {az+b}{cz+d}},}$

ここで、a、b、c、d はF ₁₁にあり、ad − bc = 1 である。通常の慣例に従い、f (− d / c ) = ∞およびf (∞) = a / cと定義すると、これらの関数は集合S をそれ自身に写像する。幾何学的な言葉で言えば、これらは射影直線の射影性である。これらは合成によって群を形成し、これは位数 660 の射影特殊線型群 PSL (2,11) である。この群には、開始ブロックを集合ごとに固定したままにする要素がちょうど 5 つあり、^[18]すなわち、b=c=0かつad =1となるような要素で、f(z) = a ² zとなる。したがって、そのブロックには 660/5 = 132 個の像があることになる。この集合に作用するこの群の乗法推移性の結果として、 Sの 5 個の要素の任意の部分集合は、サイズ 6 のこれらの 132 個の像のうちのちょうど 1 つに現れる。

_{W 12}の別の構成は、RT Curtis の「kitten」^[19]を使用することで得られます。これは、ブロックを 1 つずつ書き込む「手動計算機」として意図されていました。kitten 法は、3x3 の数字のグリッドでパターンを完成させることに基づいており、これはベクトル空間F ₃ xF ₃ 、つまり S(2,3,9) システム上のアフィン幾何学を表します。

完全グラフ K ₆のグラフ因子間の関係は、S(5,6,12) を生成します。^[20] AK ₆グラフには、6 つの頂点、15 の辺、15 の完全マッチング、および 6 つの異なる 1 因数分解 (辺を互いに素な完全マッチングに分割する方法) があります。頂点の集合 (ラベル 123456) と因数分解の集合 (ラベルABCDEF ) は、それぞれ 1 つのブロックを提供します。因数分解のすべてのペアには、正確に 1 つの完全マッチングが共通しています。因数分解AとB に、辺 12、34、および 56 との共通マッチングがあるとします。3 つの新しいブロックAB 3456、12 AB 56、および 1234 ABを追加し、共通マッチングの各辺を順に因数分解ラベルに置き換えます。同様に、さらに 3 つのブロック 12 CDEF、 34 CDEF、および 56 CDEFを追加し、因数分解ラベルを共通マッチングの対応するエッジ ラベルに置き換えます。これを 15 組の因数分解すべてに対して実行して、90 個の新しいブロックを追加します。最後に、12 個のうち 6 個のオブジェクトの組み合わせをすべて取り出し、これまでに生成された 92 個のブロックのいずれかと共通する 5 個以上のオブジェクトを持つ組み合わせを破棄します。ちょうど 40 個のブロックが残り、結果としてS(5,6,12) の2 + 90 + 40 = 132個のブロックが生成されます。この方法が機能するのは、対称群S ₆に外部自己同型があり、頂点を因数分解に、エッジをパーティションにマッピングするためです。頂点を並べ替えると、外部自己同型に従って因数分解が異なって並べ替えられます。 ${\displaystyle {\tbinom {12}{6}}=924}$

シュタイナー系 S(5, 8, 24) は、ウィット設計またはウィット幾何学としても知られ、カーマイケル (1931)によって最初に記述され、ウィット (1938) によって再発見されました。この系は、散在単純群の多くと、リーチ格子として知られる例外的な24 次元格子と関連しています。S(5, 8, 24) の自己同型群はマシュー群 M ₂₄であり、その文脈では設計は W ₂₄ (「W」は「ウィット」) と表記されます。

24 要素セットのすべての 8 要素サブセットは辞書式順序で生成され、4 位置未満で既に見つかったサブセットと異なるサブセットは破棄されます。

要素 01、02、03、...、22、23、24 のオクタッドのリストは次のようになります。

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 回出現します。各 3 要素は 21 回出現します。各 4 要素 (テトラッド) は 5 回出現します。各 5 要素 (ペンタッド) は 1 回出現します。すべての 6 要素、7 要素、または 8 要素が出現するわけではありません。

24ビットバイナリゴレイコードの4096コードワードが生成され、ハミング重みが8の759コードワードがS(5,8,24)システムに対応します。

Golay コードは、24 ビットのバイナリ文字列をすべて辞書順に生成し、前の文字列と 8 桁未満の差がある文字列を破棄するなど、さまざまな方法で構築できます。結果は次のようになります。

    000000000000000000000000
    000000000000000011111111
    000000000000111100001111
    。
    （次の4090個の24ビット文字列は省略）
    。
    111111111111000011110000
    111111111111111100000000
    111111111111111111111111

コードワードはXOR演算によってグループを形成します。

この構築はカーマイケル（1931）によるものである。^[21]

有限体F ₂₃の 23 個の元(つまり 23 を法とする整数)に、新しい元∞を追加します。この 24 個の元からなる集合Sは、 F ₂₃上の射影直線の点と形式的に同一視できます。次のサイズ 8 の特定の部分集合を ∞ と呼びます。

${\displaystyle \{\infty ,0,1,3,12,15,21,22\},}$

「ブロック」。（拡張バイナリゴレイコードの任意のオクタッドを、2乗剰余コードとして取ることができます。）このブロックから、線形分数変換を繰り返し適用することで、 S（5、8、24）システムの他のブロックを取得します。

${\displaystyle z'=f(z)={\frac {az+b}{cz+d}},}$

ここで、a、b、c、d はF ₂₃にあり、ad − bc = 1です。通常の慣例に従ってf (− d / c ) = ∞およびf (∞) = a / cと定義すると、これらの関数は集合S をそれ自身に写像します。幾何学的な言葉で言えば、これらは射影直線の射影性です。これらは合成によって、位数 6072 の射影特殊線型群PSL (2,23) を形成します。この群には、初期ブロックを固定した集合のままにする要素がちょうど 8 個あります。したがって、そのブロックの像は 6072/8 = 759 個あります。これらは S(5,8,24) のオクタッドを形成します。

ミラクルオクタッド ジェネレータ(MOG) は、指定されたサブセットを含むオクタッドなどを生成するツールです。これは、行に特定の重みが割り当てられた 4x6 配列で構成されます。特に、8 サブセットが S(5,8,24) のオクタッドになるためには、3 つのルールに従う必要があります。まず、6 つの列のそれぞれが同じパリティを持つ必要があります。つまり、すべて奇数のセルを持つか、すべて偶数のセルを持つ必要があります。次に、一番上の行は、各列と同じパリティを持つ必要があります。3 番目に、行はそれぞれ、次数 4 の有限体上の重み 0、1、2、および 3 で乗算され、有限体算術定義を使用した乗算と加算によって、6 つの列の列の合計が計算されます。結果の列の合計は、( a、b、c、a + b + c、3a + 2b + c、2a + 3b + c )の形式の有効な16 進コードワードを形成する必要があります。ここで、 a、 b、 cも 4 次有限体から得られます。列の合計のパリティが行の合計のパリティと一致しない場合、または列の合計が有効な 16 進コードワードを形成するa、 b、 c が存在しない場合、その 8 のサブセットは S(5,8,24) のオクタッドではありません。

MOG は、8 セットを 2 つの異なる 4 セットに分割する 35 通りの方法と、ファノの 3 空間 PG(3,2) の 35 直線との間の一対一関係 (Conwell 1910、「3 空間 PG(3,2) とそのグループ」) を作成することに基づいています。また、4x4 配列をそれぞれ 4 つのセルの 4 つの異なるグループに分割する 35 通りの方法と幾何学的に関連しています (Cullinane、「ダイヤモンド リングの対称性不変性」、Notices of the AMS、pp A193-194、1979 年 2 月)。つまり、4x4 配列が 4 次元の有限アフィン空間を表す場合、グループは平行なサブスペースのセットを形成します。

• 定重量コード
• カークマンの女子高生問題
• シルベスター・ガライ構成

• Assmus, EF; Key, JD (1992)、デザインとそのコード、ケンブリッジ：ケンブリッジ大学出版局、ISBN 978-0-521-41361-9
• ベス、トーマス、ユングニッケル、ディーター、レンツ、ハンフリード（1986）、デザイン理論、ケンブリッジ：ケンブリッジ大学出版局。第2版(1999) ISBN 978-0-521-44432-3。 
• カーマイケル、ロバート(1931)、「ランク 2 の戦術的構成」、アメリカ数学ジャーナル、53 (1): 217–240、doi :10.2307/2370885、JSTOR  2370885
• カーマイケル、ロバート・D. (1956) [1937]、有限順序群論入門、ドーバー、ISBN 978-0-486-60300-1
• コルボーン、チャールズ J.; ディニッツ、ジェフリー H. (1996)、コンビナトリアル デザイン ハンドブック、ボカラトン: チャップマン & ホール/CRC、ISBN 978-0-8493-8948-1、ZBL  0836.00010
• コルボーン、チャールズ J.、ディニッツ、ジェフリー H. (2007)、コンビナトリアル デザイン ハンドブック(第 2 版)、ボカラトン: チャップマン & ホール/CRC、ISBN 978-1-58488-506-1、ZBL  1101.05001
• カーティス、RT (1984)、「シュタイナーシステム S(5,6,12)、マシュー群 M _12、および「子猫」「アトキンソン、マイケル・D.編著『計算群論』（ダーラム、1982年）、ロンドン：アカデミック・プレス、pp. 353-358、ISBN 978-0-12-066270-8、MR  0760669
• ヒューズ, DR; パイパー, FC (1985)、デザイン理論、ケンブリッジ大学出版局、pp. 173–176、ISBN 978-0-521-35872-9。
• カークマン、トーマス・P.（1847）「組み合わせの問題について」、ケンブリッジ・アンド・ダブリン数学ジャーナル、II：191-204。
• リンドナー、CC; ロジャー、CA (1997)、デザイン理論、ボカラトン：CRCプレス、ISBN 978-0-8493-3986-8
• Östergard, Patric RJ; Pottonen, Olli (2008)、「シュタイナーシステム S(4,5,17) は存在しない」、Journal of Combinatorial Theory、シリーズ A、115 (8): 1570–1573、doi : 10.1016/j.jcta.2008.04.005
• Steiner, J. (1853)、「Combinatorische Aufgabe」、Journal für die reine und angewandte Mathematik、1853 (45): 181–182、doi :10.1515/crll.1853.45.181、S2CID  199547187。
• ウィット、エルンスト(1938)、「Die 5-Fach transitiven Gruppen von Mathieu」、Abh。数学。セム。大学ハンブルク、12 : 256–264、土井:10.1007/BF02948947、S2CID  123658601

ウィキメディア・コモンズには、シュタイナーシステムに関連するメディアがあります。

• ローランド、トッド & ワイスタイン、エリック W.「シュタイナー システム」。マスワールド。
• Rumov, BT (2001) [1994]、「シュタイナーシステム」、数学百科事典、EMS Press
• アンドリース・E・ブラウワーによるシュタイナーシステム
• アルベルト・デルガード博士、ゲイブ・ハート、マイケル・コルケベックによるS(5,8,24)の実装
• S(5, 8, 24) ソフトウェアとリスト (Johan E. Mebius 著)