0
大学数学基礎解説
文献あり

5次元超立方体とS(3,4,32)

ブロックデザイン,組合せ論
86
0

  1. フィッシャー不等式

  2. 算術三角形

  3. 自己同型群と拡大・縮小

  4. アフィン平面

    1. 相互直交ラテン方格


  5. シュタイナー三重系

    1. STSの直積


  6. マシュー群 M11とM12

    1. S(2,3,9)の性質

    2. S(3,4,10)の構成

    3. M11とM12


  7. 射影平面

    1. ブルック-ライサーの定理


  8. シュタイナー四重系

    1. 正測体とSQS


構成したシュタイナーシステム

(2,3,7) , (2,3,9) , (2,3,13) , (2,3,117)
(2,4,16) , (2,5,25)
(3,4,8) , (3,4,10) , (3,4,16)NEW, (3,4,32)NEW
(4,5,11)
(5,6,12)

本筋から逸れる証明は折畳んでいる場合があるが, クリックで開くことができる.

　本稿ではS5:=S(3,4,32)について,

  1. 二元体F2による構成
  2. アルゴリズム的な構成
  3. 5次元超立方体を用いた構成

を試みる. 今回の方法はSn:=S(3,4,2n)一般に通用するものだが, 適度なサイズのn=5をピックアップしている. 構成法も定理の証明も大部分は管見によるものゆえ冗長性を取り除けていない可能性があることに注意.

代数的な構成

　以下, 3つ組(α,β,γ)が含まれる唯一のブロックを(α,β,γ,α∘β∘γ)と表記する.

定理1
Γn={(i1,i2,i3,i1+i2+i3)|i1,i2,i3∈F2n,i1≠i2≠i3}
はシュタイナーシステムS(F2n,Γn)をなす.

[i] |F2n|=2n.
[ii] i1,i2,i3∈F2n,i1≠i2≠i3に対して,
i1+i2+i3=i3
を仮定すると,
i1+i2=0i1=i2
となるが, これはi1≠i2に矛盾. i1+i2+i3=i1,i2のときも同様のことが成り立つためi1+i2+i3≠i1,i2,i3.
したがって, 任意の3つ組(i1,i2,i3)に対して, (i1,i2,i3,i1+i2+i3)が存在して, これは一意である.
以上のことから,
Γn={(i1,i2,i3,i1+i2+i3)|i1,i2,i3∈F2n,i1≠i2≠i3}
はS(F2n,Γn)をなす.

定理2
n≥4, Sn−1=S(3,4,2n−1)=S(Ωn−1,Bn−1)とすると,
Ξn={((a1,x),(a2,y),(a3,z),(a4,w))a1,a2,a3,a4∈F2,a1+a2+a3+a4=0,(x,y,z,w)∈Bn−1((0,x),(0,y),(1,x),(1,y))x,y∈Ωn−1,x≠y
はシュタイナーシステムS(F2×Ωn−1,Ξn)をなす.

[i] |Sn−1|=2n−1であるから|F2×Ωn−1|=2n
[ii] 3つ組((a1,x),(a2,y),(a3,z))について
x≠y≠zならば((a1,x),(a2,y),(a3,z),(a1+a2+a3,x∘y∘z))が,
|F2|=2よりx=y=zはあり得ず, x=y≠zならば((a1,x),(a2,x),(a3,z),(a3+1,z))が一意に定まる.
これはx≠y=z,x=z≠yのときも同様であり, すべての3つ組があるブロックに一度だけ含まれることが示された.

補題3
S3=S(3,4,8)は同型を除いて一意に定まる.

S3=S(Ω3,B3)とする. B=(α1,α2,α3,α4)∈B3とα1,α2,α3,α4のいずれでもない点α5に対して, 6つの3つ組
(α1,α2,α5),(α1,α3,α5),(α1,α4,α5)(α2,α3,α5),(α2,α4,α5),(α3,α4,α5)
はすべて異なるブロックに属する. なぜなら, (α1,α2,α5)と(α1,α3,α5)が同じブロックに含まれていたとすると, それは(α1,α2,α3,α5)であり, 3つ組(α1,α2,α3)が異なる2つのブロックに属することになってしまう. 他も同様.
α1∘α2∘α5はα1,α2,α3,α4,α5のいずれとも等しくない.
α1∘α2∘α5=α6とおくと, 同様にして
α1∘α3∘α5=α7α1∘α4∘α5=α8(α6≠α7≠α8)
とする他ない.
以上でS3の8点すべてを網羅でき, 任意のS3に対して上記の操作が成り立つため, S3は同型を除いて一意に定まる.

定理4
定理2において, Ωn−1=F2n−1,Bn−1=Γn−1とすると,
S(F2×F2n−1,Ξn)≅S(F2n,Γn)

F2nの標準基底をu1,u2,⋯,unとして,
f:F2×F2n−1⟶F2n(a,v)⟼aun+v
と定める.
((a1,x),(a2,y),(a3,z),(a4,w))∈Ξn
を定立すれば,
[i] x≠y≠zのとき
f(a4,w)=a4un+w=(a1+a2+a3)un+x+y+z(∵(x,y,z,w)∈Γn−1)=(a1un+x)+(a2un+y)+(a3un+z)=f(a1,x)+f(a2,y)+f(a3,z)
より
(f(a1,x),f(a2,y),f(a3,z),f(a4,w))∈Γn
[ii] x=z,y=wのとき, a1=a2=0,a3=a4=1として
f(1,y)=un+y=x+y+un+x=f(0,x)+f(0,y)+f(1,x)
より
(f(0,x),f(0,y),f(1,x),f(1,y))∈Γn
以上の議論を逆に辿れば十分条件も同様に示すことができる.

　要するに,

　定理1　：　Fnに対してシュタイナーシステムの構造を定める
　定理2　：　Sn−1から帰納的にSnを定める

となっていて, 定理2の構成法をS3から始めてS3→S4→S5→⋯と順繰りに構成したものがすべて定理1の構成法と等価だと主張している. また, 補題3から, どのようなS3を起点としても再帰的な構成は一意であることが分かる.

アルゴリズム的な構成

　本記事の準目玉で, S3=S(3,4,8)を拡張し, S5を得ようという方針. S(5,8,24)の構成法として有名なカーティスのMOG[2]というアルゴリズムに感化されている部分が大きい. 構成法を一通り見た後で, 原理と定理2との関係について説明する.

S3と4×2ブリック

　まずは, 次のような8つの4×2のマスを考える.
12◼◼◻◼◼◼34◼◼◻◼◻◻56◻◻◻◼◼◼78◻◻◻◼◻◻◻◼◻◼◻◼◼◼◼◻◼◻◻◼◻◻◻◼◼◻◼◻◻◻◼◻◻◼◼◻◼◼
本家に倣い, それぞれの4×2の区域をブリック ( bricks ) と呼ぶ. この表を用いれば, 1から8までの任意の3つの数字からS3のブロックが決定できる.
例えば, 4,7,8を選んだとすると
12345678
となり, この3箇所が同じ色で塗られているブリックを探すと,
◼◼◻◻◼◼◻◻
が見つかる. 4,7,8が該当しているのは白マスの方で, 4マスある白マスのうち, もとのブリックで塗られていなかった数字を塗れば4つ組(3,4,7,8)が得られる.

12◼◼34◻◻56◼◼78◻◻

塗りつぶしのパターンは14通りあり,

12345678123456781234567812345678123456781234567812345678

S3={(1,2,3,4),(1,2,5,6),(1,3,5,7),(2,4,6,8),(3,4,7,8),(5,6,7,8),(1,2,7,8),(1,3,6,8),(3,4,5,6),(2,4,5,7),(1,4,5,8),(2,3,6,7),(1,4,6,7),(2,3,5,8)}
となる.

S4と4×4ブリック

　S3のブリックを拡張すると, 以下のような36個のブリックが得られる.
12910◼◼◯◯◻◼∙◯◼◼◯◯◻◼∙◯◻◼∙◯341112◼◼◯◯◻◼∙◯◻◻∙∙◼◻◯∙◼◻◯∙561314◻◻∙∙◻◼∙◯◼◼◯◯◻◼∙◯◼◻◯∙781516◻◻∙∙◻◼∙◯◻◻∙∙◼◻◯∙◻◼∙◯◻◼∙◯◼◼◯◯◼◼◯◯◻◼∙◯◼◼◯◯◻◼∙◯◻◼∙◯◻◻∙∙◯◯◼◼◻◼∙◯◻◻∙∙◼◻◯∙◼◻◯∙◻◻∙∙◻◻∙∙∙◯◻◼◯◯◼◼∙◯◻◼◼◻◯∙◼◼◯◯∙∙◻◻∙◯◻◼∙∙◻◻◯∙◼◻◻◼∙◯◻◼∙◯◼◼◻◻◼◯◯◼◻◼∙◯◼◯◯◼◼◻◯∙◻◼∙◯∙∙◯◯◼◯◯◼∙◯◻◼◻∙∙◻◯∙◼◻◯∙◼◻◯◯∙∙◻∙∙◻◻◼∙◯◼◯◯◼∙◯◻◼◯∙◼◻◻◻◼◼◻∙∙◻∙◯◻◼◻∙∙◻◻◼∙◯◼◯◯◼◻◼∙◯◻◼∙◯◻◼∙◯◼◯◯◼◯∙◼◻◯◼◼◯∙◯◻◼◯∙◼◻∙◯◻◼◻∙∙◻◻◼∙◯◻∙∙◻∙◯◻◼◯∙◼◻◯∙◼◻∙◻◻∙◯∙◼◻∙◻◻∙◻◼∙◯◻◼∙◯◼◻◯∙◯◼◼◯◼◯◯◼◻◼∙◯◼◼◼◼◻◼◻◼◼◯◼◯◼◯◼◯◻∙∙◻◯∙◼◻◻◻◻◻◼◻◼◻◻∙◻∙◻∙◻∙◯◼◼◯∙◯◻◼◯◯◯◯∙◯∙◯◻∙◻∙∙◻∙◻∙◻◻∙◼◻◯∙∙∙∙∙◯∙◯∙◼◯◼◯◯◼◯◼◻◼◻◼◼◯◼◯◼◯◼◯◼◻◯∙◼◻∙◯◼◻◻◼◻◼◻◼◻∙◻∙◻∙◻∙∙◯◻◼∙◯◼◻∙◯◯∙∙◯∙◯◼◯◼◯◯◼◯◼◻◼∙◯◻◼◯∙∙◯◯∙∙◯∙◯◻∙◻∙∙◻∙◻◯∙◼◻◯∙◻◼◼◻◻◼
下で利用する際に再度画像を貼る.

S5への拡張

1291017182526341112192027285613142122293078151623243132
　2つの数字のブリックをS4の35個のブリックに当てはめてS5のブロックを探す. 基本的なルールとして, 1つのブリックに数字は偶数個入る. 例えば, 10,20,32を選んだとして, 20,32は右のブリック, 10は左のブリックに入っているため, 残りひとつは左のブリックから決めることになる. 続けて, 数字を確定させる. まずは, 空の4×4ブリックを持ってきて, 左のブリックに重ね, 10の位置を塗る.
◻◻◻◼◻◻◻◻◻◻◻◻◻◻◻◻
右のブリックにも重ねて, 20,32の位置を塗る.
◻◻◻◼◻◼◻◻◻◻◻◻◻◻◻◼
この3箇所に同じ図形が配置されているS4のブリックを探すと,

◻◼∙◯∙◯◻◼∙◯◻◼◻◼∙◯
が見つかる. この場合塗った3マスは◯に対応していて, 塗られていなかったマスの位置は
◻◻◻◻◻◻◻◻◻◼◻◻◻◻◻◻
で, 10があったブリックから数字を選ぶことを思い出せば, この位置にある6が得られる.
1291017182526341112192027285613142122293078151623243132
次は9,14,25を選ぶ. 同じ要領で空のブリックに色を付けると
◻◻◼◻◻◻◻◻◻◻◻◼◻◻◻◻
と, 2箇所しか塗れないが, この場合はそのまま右のブリックに当てはめて25を得る.
1291017182526341112192027285613142122293078151623243132

　ブリックの数はS3では8個, S4では36個だったが, S5では156個のブリックが必要になってしまう.

原理

　この構成法は定理2を可視化したものになっている. 定理2を振り返りつつ, どのようにしてS3の7つのブリックを得るかを見ていく.

定理2(再掲)
n≥4, Sn−1=S(3,4,2n−1)=S(Ωn−1,Bn−1)とすると,
Ξn={((a1,x),(a2,y),(a3,z),(a4,w))a1,a2,a3,a4∈F2,a1+a2+a3+a4=0,(x,y,z,w)∈Bn−1((0,x),(0,y),(1,x),(1,y))x,y∈Ωn−1,x≠y
はシュタイナーシステムS(F2×Ωn−1,Ξn)をなす.

　S2=S(3,4,4)を単なる4つ組(1,2,3,4)とする. このとき, F2×S2は次のような4×2のマス目で表現できる.
(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)
a1+a2+a3+a4=0の条件を満たすようにマス目を塗ると

(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)

((0,x),(0,y),(1,x),(1,y))の形のブロックは

(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)

と14個のブロックを列挙できているが, 例えば
(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)(0,1)(1,1)(0,2)(1,2)(0,3)(1,3)(0,4)(1,4)

の2ブロックはF2×S2において, 互いに補集合の関係になっている. このような2ブロックを1ブリックにまとめると, 求めていた8ブリック
12◼◼◻◼◼◼34◼◼◻◼◻◻56◻◻◻◼◼◼78◻◻◻◼◻◻◻◼◻◼◻◼◼◼◼◻◼◻◻◼◻◻◻◼◼◻◼◻◻◻◼◻◻◼◼◻◼◼
が得られる. Γnのブロックの数は
|Γn|=2n(2n−1)(2n−2)4⋅3⋅2=2n−2(2n−1−1)(2n−1)3
だが, Γnのブリックの数Rnは
Rn=12n−2|Γn|=(2n−1−1)(2n−1)3
と, 相補的なブリックにすることで大分コンパクトになっている.

5次元超立方体を用いた構成

Fig.1　立方体

　上の方法と同様, まずはS3を立方体から構成し, それをS5へと拡張する.

S3と立方体

　Fig1. で1,5,7のように同一平面内にある3点を選んだときはその面の残りの点を選択する. これにより
(1,2,3,4),(1,2,5,6),(1,3,5,7),(2,4,6,8),(3,4,7,8),(5,6,7,8)
を得, 2,4,5のように2,4が辺で結ばれているときには, その辺と平行な辺で5を含む辺を選び, (2,4,5,7)とする. 立方体を二分する断面とも見れ, このタイプの4つ組を列挙すると
(1,2,7,8),(1,3,6,8),(3,4,5,6),(2,4,5,7),(1,4,5,8),(2,3,6,7)
最後にどの2点も辺上にないような1,6,7に対しては, その性質を保存する4を取る. これは2通り挙げられ,
(1,4,6,7),(2,3,5,8)
以上をまとめると
S3={(1,2,3,4),(1,2,5,6),(1,3,5,7),(2,4,6,8),(3,4,7,8),(5,6,7,8),(1,2,7,8),(1,3,6,8),(3,4,5,6),(2,4,5,7),(1,4,5,8),(2,3,6,7),(1,4,6,7),(2,3,5,8)}
と, (83)(43)=14個のブロックを列挙できた.
以下ではこの方法を5次元へと持ち込むことになる.

S5への拡張

　立方体を重ねた4次元多胞体が超立方体(テッセラクト, 正八胞体とも)であり, それをさらに重ねた5次元超立方体をT5とする. T5には10個のテッセラクト, 40個の立方体が含まれていて, 頂点数は32となっている.

Fig.2　T5のグラフ

ここで, 次のような辺彩色を施した2つのグラフを考える.

Fig.3　辺彩色C1

Fig.4　辺彩色C2

Fig5.

　このような彩色をする理由は後述するとして, 実際に3点から残り1点を決める過程を説明する. C1,C2をよく観察すると, すべての点が赤い辺か青い辺の上にあることが確認できる. 選んだ3点について, 赤い辺の上にあった場合はそのまま, 青い辺上にあった場合は青い辺をつたって赤い辺上の点まで移動する. 赤い辺は立方体になっているため, そこでS3のときと同じ操作で残り1点を得るが, これで確定というわけではなく, その点から青い辺をつたって移動できる場所4つが候補となる. これをC1,C2で行えば共通している1点が得られる.
　試しに19,21,23をFig5. から選んだときの残り1点を求めてみる.

1.　赤の辺に点を移す

　19,21,23をC1にプロットすると,

Fig6.

点19は青い辺によって18と10に接続されている. このうち, 18は赤い辺の上にあるため, 19を18へ移す. 23も同様にして5へ移し, 21に関しては20→9と辿って9へ移す.

2.　赤の立方体から4つの候補を得る

　赤い辺の立方体を書き直すと,

Fig7.

となり16を得るが, 9,18,5は青い辺を辿って見つけた数字であることを考慮する必要がある. よって, 候補は

Fig8.

緑の円で囲んである4,15,16,26となる.

3.　2つのグラフの共通部分を取る

　上の操作をC2でも行えば

Fig9.

と, 候補(2,4,10,32)を得る.
2つの候補(4,15,16,26),(2,4,10,32)に共通する4を取って, (4,19,21,23)が確定した. 以上の流れをまとめたのが下のGIF.

Fig10.　19,21,23から(4,19,21,23)を得る様子(25秒)

青い辺上に2点以上ある場合

　例外パターンとして, (3,19,28)が挙げられ, C1のグラフで候補を探すときに少し困ったことになる.

Fig11.

19,28が同じ青い辺上にあり, どちらも18に移ってしまう.
　ここで, 青い辺はすべて四角形をなしていることに着目する. 例えば, 10→19→18→28と辿ると, 必ず28→10と戻れるような辺が存在している. 19,28は互いに四角形の対角線上にあるため, 3がある四角形で同じく対角線上にある11を選べば(3,11,19,28)が得られる.
　3点が同じ青い経路上にある場合は, 残りの点を取る. 例えば, 20,21,31に対しては9を取り, (9,20,21,31)を得る.

原理

定理1(再掲)
Γn={(i1,i2,i3,i1+i2+i3)|i1,i2,i3∈F2n,i1≠i2≠i3}
はシュタイナーシステムS(F2n,Γn)をなす.
Fig12.　F23と立方体

　この構成法は定理1を可視化したものになっていて, F23の標準基底をi,j,kとすると, S3の3つ組からブロックを得る操作は, Fig12. のような立方体で平行四辺形を得る操作と捉えることができる.
　同様にF25の標準基底i,j,k,l,mをT5にプロットし, i,j,kが張る立方体を赤で彩色するとFig13. のようになる. 青い辺上の点を移動させる操作は, l,mの項を消してi,j,kの係数を確定させることを意味している. 上で扱った(19,21,23)は, Fig13. では(i+j+l,j+l+m,k+l)に対応していて, i,j,kの項のみ足し合わせると
(i+j)+j+k=i+k
となり, i+k+c1l+c2m(c1,c2∈F2)の4つが候補となる.

Fig13.　Span(i,j,k)と辺彩色C1

C2はi,l,mが張る立方体で

Fig14.　Span(i,l,m)と辺彩色C2

同様の操作によってl,mの係数を確定させる.
(i+l)+(l+m)+l=i+l+m
からi+c3j+c4k+l+m(c3,c4∈F2)が候補で, 先ほど得られた式と合わせて
i+k+c1l+c2m=i+c3j+c4k+l+mc1=1,c2=1,c3=0,c4=1
となり, これが共通部分を求める操作と対応している.
式の上では
(i+j+l)+(j+l+m)+(k+l)=i+k+l+m
と簡単に求まるが, この足し算を回りくどくすることで可視化をしている.

参考文献

投稿日：5月15日
更新日：6月28日
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

パトポス
パトポス
7
2066
有限群論　代数的組合せ論

コメント

他の人のコメント

コメントはありません。
読み込み中
パトポス
パトポス
5次元超立方体とS(3,4,32)
  1. 代数的な構成
  2. アルゴリズム的な構成
  3. S3と4×2ブリック
  4. S4と4×4ブリック
  5. S5への拡張
  6. 原理
  7. 5次元超立方体を用いた構成
  8. S3と立方体
  9. S5への拡張
  10. 原理
  11. 参考文献