利用者:Loasa/執筆記録と下書き/下書き用

組合せ論においてシュタイナー系とは、ブロックデザインの一種である。特に、 $\ S(l,m,n)$ と書かれる $\ l$ - $(n,m,1)\$ -デザインである。ヤコブ・シュタイナー(Jakob Steiner)による研究の後に命名された。

定義

パラーメーター $\ l,m,n\$ を持つシュタイナー系は $\ S(l,m,n)\$ と書かれる。それは $\ n\$ 要素を持つ集合 $\ S\$ における $\ m\$ 要素を含む部分集合(ブロックと呼ばれる)からなる集合族であって、 $\ l\$ 個の要素からなる $\ S\$ の任意の部分集合がただ一つのブロックに含まれるようなものである。

$\ S(2,3,n)\$ はシュタイナー3つ組とも呼ばれ、そのブロックは3つ組とも呼ばれる。この3つ組の数は $\ n(n-1)/6.\$ である。 $\{a,b,c\}$ が3つ組なら、 $\ ab=c\$ 、またすべての $\ a\$ に対し、 $\ aa=a\$ と定義することで $\ S\$ 上に演算が定義できる。これは $\ S\$ の冪等かつ可換な準群になる。

$\ S(3,4,n)\$ はシュタイナー4つ組とも呼ばれる。 $\ m\$ がそれ以上大きいものは特別な名前では呼ばれない。

例

有限射影平面

位数 $\ q\$ の有限射影平面は、その「直線」をブロックと見なせば、 $\ S(2,q+1,,q^{2}+q+1)$ ,である。それは、 $\ q^{2}+q+1\$ 点を持ち、各直線は、 $\ q+1\$ 点を通過する。、そして各異なる点の対はただ一つの線に含まれる。詳細は有限幾何学を参照のこと。

性質

$\ S(l,m,n)\$ の定義より、 $\ 1<l<m<n\$ は明らかである。 $\ S(l,m,n)\$ が存在すれば、全てのブロックがある特定の要素を含みその特定要素を取り除くと、 $\ S(l-1,m-1,n-1)\$ が与えられることがいえる。従って、 $\ S(l-1,m-1,n-1)\$ の存在は $\ S(l,m,n)\$ の存在のための必要条件である。

$\ S\$ の $\ l\$ 要素部分集合の数は ${\tbinom {n}{l}}$ 個であり、それぞれのブロックにおける $\ l\$ 要素部分集合の数は ${\tbinom {m}{l}}$ 個である。それぞれの $\ l\$ 要素部分集合は厳密にただ一つのブロックに含まれるから ${\tbinom {n}{l}}=b{\tbinom {m}{l}}$ 、あるいは、 $b={\frac {\tbinom {n}{l}}{\tbinom {m}{l}}}$ となる。ただし $\ b\$ はブロックの数である。

同様の理由で、 $\ l\$ 要素部分集合が含む特定の要素の数は ${\tbinom {n-1}{l-1}}=r{\tbinom {m-1}{l-1}}$ あるいは $r={\frac {\tbinom {n-1}{l-1}}{\tbinom {m-1}{l-1}}}$ で与えられる。ただし $\ r\$ は任意の与えられた要素を含むブロックの数である。

これらの定義から $bm=rn$ が従う。この $\ b\$ と $\ r\$ が整数になることが、 $\ S(l,m,n)\$ が存在するための必要条件である。任意のブロックデザインと同様にフィッシャーの不等式 $b\geq n$ はシュタイナー系においても成り立つ。

1以上の素数冪 $\ m\$ に対して、シュタイナー系 $\ S(2,m,n)\$ , が存在するならば、 $\ n=1.\$ または $\ m(\mod m(m-1))$ であることが示せる。特にシュタイナー3つ組 $\ S(2,3,n)\$ は $\ n=6k+1\$ または $\ 6k+2\$ でなければならない。これは、シュタイナー3つ組のただ一つの制約条件であることが知られている。実際に、各自然数 $\ k\$ に対し、 $\ S(2,3,6k+1)\$ および $\ S(2,3,6k+3)\$ が存在する。

マシュー群との関連

いくつかのシュタイナー系は群論と深い関係がある。特にマシュー群という有限単純群はシュタイナー系の自己同型群として構成できる。

マシュー群 $\ M_{11}\$ は、シュタイナー系 $\ S(4,5,11)\$ の自己同型群。
マシュー群 $\ M_{12}\$ は、シュタイナー系 $\ S(5,6,12)\$ の自己同型群。(次節参照)
マシュー群 $\ M_{22}\$ は、シュタイナー系 $\ S(3,6,22)\$ の自己同型群の指数2であるような唯一の部分群。
マシュー群 $\ M_{23}\$ は、シュタイナー系 $\ S(4,7,23)\$ の自己同型群。
マシュー群 $\ M_{24}\$ は、シュタイナー系 $\ S(5,8,24)\$ の自己同型群。

特殊なシュタイナー系

この節ではいくつかの特徴的なシュタイナー系について解説する。これらの例は他の分野との重要な関連性を持っていて、興味深いものである。

シュタイナー系 S(5, 6, 12)

シュタイナー系 $\ S(5,6,12)\$ の自己同型群はマシュー群 $\ M_{12}\$ であり、この文脈では $\ W_{12}\$ と書かれることもある。

S(5, 6, 12) の構成

この構造として、12点集合をとり、体 $\ F_{11}\$ 上の射影平面として考える。すなわち、 $\mod 11$ の整数と「無限遠点」と呼ばれる点である。 $\mod 11$ の整数のうち、次の6個が完全平方である。

\{0,1,3,4,5,9\}.\

この集合は「ブロック」と呼ばれる。これからメビウス変換

z\mapsto {\frac {az+b}{cz+d}}.

により他のブロックを得ることができる。これらのブロックはシュタイナー系 $\ S(5,6,12)\$ を構成する。

$\ W_{12}\$ は、ベクトル空間 $F_{3}\times F_{3}$ 上のアフィン平面からも構成できる $\ S(2,3,9)\$ である。 $\ W_{12}\$ の交代的構造はR.T. Curtis.の「子猫」である(Curtis 1984)(Joyner & Casey 2006)。

シュタイナー系 S(5, 8, 24)

特記すべきものは、「ウイットのデザイン」または「ウイット幾何」としても知られるシュタイナー系 $\ S(5,8,24)\$ である。これは、ロバート・ダニエル・カーマイケル(Robert Daniel Carmichae)による1931年の論文(Carmichael 1931)とエルンスト・ウィット(Ernst Witt)による1938年発行の論文における再発見で論じられた(Witt 1938)。(Kantor 1981) この系は多くの散在単純群や、リーチ格子として知られる例外的24次元格子と結び付いている。

$\ S(5,8,24)\$ の自己同型群はマシュー群 $\ M_{24}\$ であり、この文脈では $\ W_{12}\$ と書かれる。

S(5, 8, 24)の構成

$\ S(5,8,24)\$ を構成するためには多くの方法がある。以下に説明する方法はおそらく考えられる限りもっとも簡単な方法であり、コンピュータープログラムに変換することも容易である。これは2進数の24ビット列を使う。最初にすべての24ビット列を辞書式順序で並べる。ビット列を一つの2進数と考えれば単に2進数を小さい方から並べていくことと同じである。最初の要素として

   000000000000000000000000

を選ぶ。次の要素として、最初の要素とは少なくとも8箇所以上のビットが異なるものを選ぶ。そのような最初の要素は

   000000000000000011111111

である。その次は最初の二つの要素のどちらとも8箇所以上のビットが異なるものを選ぶ。例えば

   000000000000011100011111

などは最初の要素とは8箇所異なるが、2番目の要素とは6箇所しか異ならないので採用しない。条件を満たすような最初の要素は、

   000000000000111100001111

である。以下同様に、それまでに選んだ要素のどれと比較しても8箇所以上のビットが異なるものを選んでいくと、次のような要素の列ができる。

   000000000000000000000000
   000000000000000011111111
   000000000000111100001111
   000000000000111111110000
   000000000011001100110011
   000000000011001111001100
   000000000011110000111100
   000000000011110011000011
   000000000101010101010101
   .
   . (この間4083要素省略)
   .
   111111111111000011110000
   111111111111111100000000
   111111111111111111111111

このリストは4096の要素を含む。それらはゴレイ符号の各符号語になっている。これら要素は1ビット演算(排他的論理和)のもとで群になる。この符号の集合には、すべてのビットが0および1であるような要素がそれぞれ1つ、8ビットが1である要素が759、12ビットの1を持つ要素が2576、16ビットの1を持つ要素が759含まれる。

そして、 $\ S(5,8,24)\$ の759個の8要素ブロックは、この符号語リストの中の8ビットが1である759個の要素によって与えられる。

24要素集合から同様の手続きで8要素部分集合の族を構成することにより、もっと直接的に構成することもできる。先の例と同様に、それまでに選んだ要素のどれと比較しても少なくとも4箇所の値が異なるものを選んでいく。

   01 02 03 04 05 06 07 08
   01 02 03 04 09 10 11 12
   01 02 03 04 13 14 15 16
   01 02 03 04 17 18 19 20
   01 02 03 04 21 22 23 24

   01 02 03 05 09 14 19 24
   01 02 03 05 13 18 23 12
   01 02 03 05 17 22 11 16
   01 02 03 05 21 10 15 20

   01 02 03 06 09 13 17 21
   01 02 03 06 14 18 22 10
   01 02 03 06 19 23 11 15
   01 02 03 06 24 12 16 20

   . 
   . 
   .
   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個のブロックに含まれる。任意の要素の2つ組はそれぞれ77回現れる。すなわち77個のブロックに含まれる。各3つ組は21回、各4つ組は5回、各5つ組は一回だけ現れる。6,7,8組については全て組が現れることはない。

脚注・参考文献

Joyner, David; Casey, Ann (2006-05-24) (PDF), Kittens, S(5, 6, 12), and Mathematical blackjack in SAGE, David Joyner 2010年12月10日閲覧。

Curtis, R.T. (1984), “The Steiner System S(5,6,12), the Mathieu Group M12 and the 'Kitten'”, in M.Atkinson, Computational Group Theory, Academic Press, pp. 353–358

Kirkman, Thomas P. (1847), “On a Problem in Combinations”, The Cambridge and Dublin Mathematical Journal (Macmillan, Barclay, and Macmillan) II: 191–204.

Steiner, Jakob (1853), “Combinatorische Aufgabe”, Journal für die Reine und Angewandte Mathematik 45: 181–182 .

[1]より検索可。

Witt, Ernst (1938), “Die 5-Fach transitiven Gruppen von Mathieu”, Abh. Math. Sem. Univ. Hamburg 12: 256–264, doi:10.1007/BF02948947

Carmichael, R. D. (1931), “Tactical Configurations of Rank Two”, American Journal of Mathematics 53 (1): 217-240

Kantor, William M. (1981), “BOOK REVIEWS "Permutation groups and combinatorial structures, by N. L. Biggs and A. T.White"”, Bulletin (New Series) of The American Mathematical Society 5 (2) 2010年12月10日閲覧。

Assmus, E. F., Jr.; Key, J. D. (1994), “8. Steiner Systems”, Designs and Their Codes, Cambridge University Press, pp. 295–316, ISBN 0-521-45839-0 .

Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1999), Design Theory (2 ed.), Cambridge: Cambridge University Press, ISBN 9780521444323.{{ISBN2}}のパラメータエラー: 無効なISBNです。 .

Hughes, D. R.; Piper, F. C. (1985), Design Theory, Cambridge University Press, pp. 173–176, ISBN 0-521-35872-8 .

ジョーンズ, G.A.; ジョーンズ, J.M. 一樂重雄, 河原正治, 河原雅子訳 (2006), “7.5 ゴーレイ符号”, 情報理論と符号理論, シュプリンガー・ジャパン, pp. 136-141, ISBN 443171216X

外部リンク

Joyner, David; Casey, Ann (2006-05-24), Kittens, S(5, 6, 12), and Mathematical blackjack in SAGE, David Joyner 2010年12月10日閲覧。

Rowland, Todd and Weisstein, Eric W. "Steiner System". mathworld.wolfram.com (英語).
Rumov, B.T. (2001), “Steiner system”, in Hazewinkel, Michiel, Encyclopaedia of Mathematics, Springer, ISBN 978-1-55608-010-4, http://eom.springer.de/s/s087670.htm
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
The Witt Design computed by Ashay Dharwadker

定義

例