2
現代数学解説
文献あり

双対同型な結合構造の数え上げ

120
0

こんにちは。krutrです。 
今回は、ある組み合わせ対象の特殊なクラスの同型を除いた数え上げについて、解説します。 
前提知識として、対称群の共役類に関する知識や、群作用の理論(バーンサイドの補題など)を仮定します。
また、説明が煩雑になりすぎないため、議論を省略することがあります。予めご了承ください。
まずは、今回数え上げを行う「結合構造」という組み合わせ対象の説明をしていきます。

結合構造とは

結合構造(例)の図示 結合構造(例)の図示

I,Jを共通の元を持たない2つの(空でない)集合とし、Rを直積集合I×Jの部分集合とするとき、組(I,J,R)結合構造という。

結合構造の同型

結合構造の同型(例) 結合構造の同型(例)
2つの結合構造(I,J,R)(I,J,R)同型であるとは、次のときをいう。:
ある2つの全単射f:II,g:JJが存在して、
R={(f(i),g(j))I×J|(i,j)R)}である。

結合構造の双対

結合構造の双対(例) 結合構造の双対(例)
結合構造(I,J,R)の双対とは、R¯={(j,i)J×I|(i,j)R)}としたとき、(J,I,R¯)のことである。

結合構造が双対同型(self-dual)である

双対同型な結合構造(例) 双対同型な結合構造(例)
結合構造(I,J,R)が、その双対(J,I,R¯)と同型であるとき、(I,J,R)は、双対同型(self-dual)であるという。

双対同型な結合構造の有名な例

位数2の有限射影平面(左)と位数3の有限射影平面(右)の図示 位数2の有限射影平面(左)と位数3の有限射影平面(右)の図示

有名な、双対同型な結合構造の例として、デザルグな有限射影平面があります。図はそれぞれ、位数が2,3の有限射影平面を表しています。それぞれの点の集合をI、それぞれの曲線の集合をJとします。これまでのように図示する事も出来ます。興味のある方はぜひチャレンジしてみてください。

本題ー双対同型な結合構造の数え上げ

この記事では、互いに要素数nの、共通部分を持たない2つの集合I,Jに対し、I×Jに含まれる双対同型な結合構造の、同型を除いた(同一視した)数を数えていきます。
ここから先、I,Jはそれぞれ固定されたn点集合とし、I×Jの部分集合Rについて考察するので、結合構造(I,J,R)Rと同一視して、単にRを結合構造と呼びます。
まず、計算に必要な諸概念を定義します。

写像の演算(,

SIを、IからIへの全単射の全体、SJJからJへの全単射の全体とする。

  • α,βSIγ,δSJに対して、
    SI×SJ上の演算を、

(α,γ)(β,δ):=(αβ,γδ)

とする。

SIJを、IからJへの全単射の全体、SJIJからIへの全単射の全体とする。

  • κ,λSJIμ,νSIJに対して、
    演算:(SJI×SIJ)×(SJI×SIJ)(SI×SJ)を、

(κ,μ)(λ,ν):=(κν,μλ)

とする。

IJがどっちがどっちやら紛らわしいですが、ここはあまり重要ではないので、面倒なら飛ばしても全然大丈夫です。SI,SJはそれぞれ、I,J上の置換群と同一視できることを意識しておいてください。
次は重要です。

作用(,×
  • θ=(α,β)SI×SJ,r=(i,j)I×J に対して、
    SI×SJI×Jへの作用を、

θr:=(α(i),β(j))

とし、さらに、

  • θ=(α,β)SI×SJ,RP(I×J) に対して、
    SI×SJP(I×J)への作用を、

θR={θr|rR}:={(α(i),β(j))|(i,j)R}

とする。

  • ϕ=(τ,σ)SJI×SIJ,r=(i,j)I×J に対して、
    SJI×SIJI×Jへの()作用を、

ϕr:=(τ(j),σ(i))

とし、さらに、

  • ϕ=(τ,σ)SJI×SIJ,RP(I×J) に対して、
    SJI×SIJRP(I×J)への()作用を、

ϕR={ϕr|rR}:={(τ(j),σ(i))|(i,j)R}

とする。

これらは群作用ではない。ここでは作用の語を、「SJI×SIJの各元ϕに対して、ϕが、I×J,P(I×J)上の置換と同一視できる」意味で用いている。

演算をよく観察すると、これを用いて双対同型な結合構造のクラスが定義できそうだと分かりますね。

双対同型な結合構造のクラスDIJ

ある結合構造RP(I×J)が、

ϕSJI×SIJ,ϕR=R

を満たす時、Rは双対同型であるという。
また、その全体を、

DIJ:={RP(I×J)|ϕSJI×SIJ,ϕR=R}

で表し、双対同型な結合構造のクラスという。

DIJに対しても、(SI×SJ,),(SJI×SIJ,)は作用することは簡単に分かります。
今回は、このDIJの、同型を除いた数え上げ、すなわち、DIJ/(SI×SJ,)の大きさを求めます。
ここで、DIJ/(SJI×SIJ,)は考えられるのか、考えなくてよいのか、と思われるかもしれませんが、実はこれは考えられる上に、DIJ/(SI×SJ,)と一致します。
証明はしませんが、ここでは双対同型な結合構造全体を考えていて、どちらの作用も結合構造を本質的に変えないので、直感的には明らかです。
次の補題が、今回の数え上げの肝です。

|DIJ/(SI×SJ,)|(SJI×SIJ,)固定点表示

|DIJ/(SI×SJ,)|=1n!2ϕSJI×SIJ|DIJϕ|
=1n!2ϕSJI×SIJ{RDIJ|ϕR=R}

バーンサイドの補題より、
|DIJ/(SI×SJ,)|=1n!2θSI×SJ|DIJθ|
=1n!2θSI×SJ|{RDIJ|θR=R}|
=1n!2RDIJ|{θSI×SJ|θR=R}|
ここで、RDIJに対して、
|{θSI×SJ|θR=R}|=|{ϕSJI×SIJ|ϕR=R}|を示す。
左辺をA、右辺をBと置き、次のfは全単射であることを示す。

f:BA
ϕϕϕ1
(ただし、ϕ1ϕ1R=Rを満たすSJI×SIJの元)

まず、fが写像であること(ϕϕ1がきちんとAに入っていること)を確認します。
(ϕϕ1)R=ϕ(ϕ1R)=R
より、fは写像です。
また、fの単射性は明らかなので、全射性を示します。
θ=(α,β)SI×SJを任意にとり、ϕ1=(τ1,σ1)とすると、ϕ=(ασ11,βτ11)B ()
ϕϕ1=(ασ11,βτ11)(τ1,σ1)=θ

ϕR=(ασ11,βτ11)R
=(ασ11,βτ11)((τ1,σ1)R)
=((ασ11,βτ11)(τ1,σ1))R
=θR
=R
よって、
|DIJ/(SI×SJ,)|=1n!2RDIJ|{ϕSJI×SIJ|ϕR=R}|
=1n!2ϕSJI×SIJ{RDIJ|ϕR=R}

長かったですね。途中、やや特殊な計算を説明なしに行っています。
非常に申し訳ないのですが、ゆっくり行間を埋めればきちんと読めるようにはなっているはずですので、ここはこのまま進ませてください。
この計算によって、各ϕSJI×SIJに対して、ϕによって変化しないRDIJの数を求めればよいと分かります。
ここから先は、ϕSJI×SIJを任意に一つとって固定し、その固定点集合DIJϕの大きさを求めていきます。
まず、次のような考察をします。

ϕ固定点の構造

rI×Jに対し、列 r,ϕr,ϕ(ϕr),ϕ(ϕ(ϕr)),...は必ず巡回し、
[r]ϕ={r,ϕr,ϕ(ϕr),ϕ(ϕ(ϕr)),...}とすると、
(I×J)/ϕ:={[r]ϕ|rI×J}I×Jの分割となる。
また、
|DIJϕ|=|P((I×J)/ϕ)|=2|I×J/ϕ|
である。

直感的には、さほど難しい話ではないと思います。
証明はここも省きますが、具体的には、次の全単射を構成すればよいです。
f:P((I×J)/ϕ)DIJϕ
MM
ここから、(I×J)/ϕの元をここでは極小固定点と呼び、この極小固定点を任意にいくつか選んだ非交和が、固定点を尽くしているということですから、この数を調べます。この際、次のように考えます。
ϕ=(τ,σ)SJI×SIJの2回作用ϕ(ϕ)は、群の作用(ϕϕ)=(τσ,στ)となっていることを利用します。
次の項目から、厳密性に欠いた定義が出てきます。
私の技術的な問題で、厳密さを重視すると冗長になってしまうためです。
直感的には難しくないと思います。自信のある方は、厳密で綺麗な定義に直して進んで下されば幸いです。

I,Jの各元

ϕ=(τ,σ)SJI×SIJとする。
τσSIを、巡回置換の積として書く方法を、巡回置換の掛け順と各巡回置換の表示を完全に指定して適当に(好きに)1つ選び、それを、
τσ=(i01i11...)(i02i12...)...(i0ui1u...)...(i0mi1m...) (ただしm=|I/τσ|)
とする。(各uに対して、Iu:={i0u,i1u...}と定め、ikuの下添え字kは、Z/|Iu|Zの元であるとする。)
また、任意のu{1,2,...,m}に対し、
σ(Iu):=Juとし、さらに、任意のkZ/|Iu|Z=Z/|Ju|Zに対して、
σ(iku):=jku
とする。

i,jの動き

任意のjJに対し、j=jkuとなるu{1,2,...,m},kZ/|Ju|Z=Z/|Iu|Zが一意に存在し、
στ=(j01j11...)(j02j12...)...(j0uj1u...)...(j0mj1m...)(ただしm=|I/τσ|)
であり、さらに、
τ(jku)=ik+1u
である。

一行目は明らかとしてよい。
σ(iku)=jkuの両辺にτを作用させると、
τσ(iku)=τ(jku)より、
ik+1u=τ(jku)
さらに両辺にσを作用させると、
jk+1u=στ(jku)
これによってστ の表示が定まる。

次は、I×Jを、都合の良い大まかな固定点に分解していきます。

I×Jの固定点分解

I×J=(1um(Iu×Ju))(1u<vm((Iu×Jv)(Iv×Ju)))
と分解でき、それぞれのIu×Ju,(Iu×Jv)(Iv×Ju)は、ϕによる固定点となっている。

I,Jそれぞれの分解を考えれば、式自体は明らかです。
固定点になっていることも、ϕによって、(Iu×Ju)は動きませんし、(Iu×Jv)(Iv×Ju)と交換されることを考えれば分かります。
次は、これらの二種類の固定点が、いくつの極小固定点に分解されるか、をそれぞれ観察します。

分解された固定点に含まれる極小固定点の数

任意のu,v{1,2,...,m}(ただしm=|I/τσ|)に対し、
1.Iu×Juに含まれる極小固定点は、|Iu|2
2.(Iu×Jv)(Iv×Ju)(uv)に含まれる極小固定点は、gcd(|Iu|,|Iv|)

1.Iu×Juの場合
r=(i,j)Iu×Juを任意にとる。
[r]ϕ={r,ϕr,ϕ(ϕr),ϕ(ϕ(ϕr)),...}
あるk,lZ/|Iu|Zがそれぞれ一意に定まりr=(iku,jlu)であり、
[r]ϕ={(iku,jlu),(il+1u,jku),(ik+1u,jl+1u),(il+2u,jk+1u),...}
ここで、[r]ϕは第一成分がi0uである元を必ず持つことに注意すると、
[r]ϕ={(i0u,jlu),(il+1u,j0u),(i1u,jl+1u),(il+2u,j1u)...}
と書き直せる。新たに、r=(i0u,jlu)とおき、
次の二つの集合[r]ϕe,[r]ϕoを考える:
[r]ϕe={r,ϕ(ϕr),ϕ(ϕ(ϕ(ϕr)),...}
[r]ϕo={ϕr,ϕ(ϕ(ϕr)),ϕ(ϕ(ϕ(ϕ(ϕr))))...}
すると、[r]ϕe=[r]ϕo=[r]ϕまたは、[r]ϕe[r]ϕo=[r]ϕであり、また、
[r]ϕe={(i0u,jlu),(i1u,jl+1u),(i2u,jl+2u)...}
[r]ϕo={(il+1u,j0u),(il+2u,j1u),(il+3u,j2u)...}
より、|[r]ϕe|=|[r]ϕo|=|Iu|である。

[r]ϕe=[r]ϕo=[r]ϕを仮定する。
このとき、r[r]ϕoに入っていることが必要十分であり、
{0=l+1+hl=h
をみたすhZ/|Iu|Zがあればよいが、2h+1=0,2l+1=0より、|Iu|は奇数であるしかなく、さらにそのときh=l=|Iu|12より、このような極小固定点はただ一つ存在し、その大きさは|[r]ϕ|=|[r]ϕe|=|[r]ϕo|=|Iu|である。
それ以外の場合は自動的に[r]ϕe[r]ϕo=[r]ϕであり、極小固定点の大きさは
|[r]ϕ|=|[r]ϕe|+|[r]ϕo|=2|Iu|となるので、
|Iu|が奇数のとき、Iu×Juに含まれる極小固定点の数は、
|Iu×Ju||Iu|2|Iu|+1=|Iu|+12
|Iu|が偶数のとき、Iu×Juに含まれる極小固定点の数は、
|Iu×Ju|2|Iu|=|Iu|2

2,(Iu×Jv)(Iv×Ju)(uv)の場合
r=(i,j)(Iu×Jv)(Iv×Ju)(uv)を任意にとる。
rIu×JvまたはrIv×Juなので、
まずrIu×Jvの場合を考える。
[r]ϕ={r,ϕr,ϕ(ϕr),ϕ(ϕ(ϕr)),...}
ここで次の二つの集合[r]ϕe,[r]ϕoを考える:
[r]ϕe={r,ϕ(ϕr),ϕ(ϕ(ϕ(ϕr)),...}
[r]ϕo={ϕr,ϕ(ϕ(ϕr)),ϕ(ϕ(ϕ(ϕ(ϕr))))...}
あるkZ/|Iu|Z,lZ/|Iv|Zがそれぞれ一意に定まりr=(iku,jlv)であり、
[r]ϕe={(iku,jlv),(ik+1u,jl+1v),(ik+2u,jl+2v)...}
[r]ϕo={(il+1v,jku),(il+2v,jk+1u),(il+3v,jk+2u)...}
明らかに[r]ϕe[r]ϕo=[r]ϕであり、また、
|[r]ϕe|=|[r]ϕo|=lcm(|Iu|,|Iv|)
よって|[r]ϕ|=|[r]ϕe|+|[r]ϕo|=2lcm(|Iu|,|Iv|)
rIv×Juの場合も同様なので、
すべての極小固定点の大きさは等しく、2lcm(|Iu|,|Iv|)
よって、(Iu×Jv)(Iv×Ju)に含まれる極小固定点の数は、
|(Iu×Jv)(Iv×Ju)|2lcm(|Iu|,|Iv|)=gcd(|Iu|,|Iv|)

大変でしたね、、、
しかし、とても興味深い観察だったと思います。
さて、詰めです。
Iuたちの大きさは、ϕ=(τ,σ)として、τσの示すIの分割に依存していたことを思い出しましょう。

双対同型な結合構造の数|DIJ/(SI×SJ,)|

σSnに対し、σの示すnの分割をa1,a2,...amとするとき、
f(σ)=1umau2+1u<vmgcd(au,av)
とする。
|DIJ/(SI×SJ,)|=1n!σSn2f(σ)

|DIJ/(SI×SJ,)|
=1n!2ϕSJI×SIJ|DIJϕ|
=1n!2ϕSJI×SIJ2|I×J/ϕ|
=1n!2ϕSJI×SIJ2|((1um(Iu×Ju))(1u<vm((Iu×Jv)(Iv×Ju))))/ϕ|

=1n!2ϕSJI×SIJ2|(1um(Iu×Ju)/ϕ)|+|(1u<vm((Iu×Jv)(Iv×Ju))/ϕ)|
=1n!2τ,σSn2f(τσ)
=1n!σSn2f(σ)

これにて、証明終了となります。
この数列をDnとし、少し計算してみると、
D1=2,D2=5,D3=16,D4=67,D5=660,...と続きます。
この数列自体について考察してみるのも面白いかもしれませんね。

最後に、気になっている関連問題について書かせてください。

dualityとpolarity

RP(I×J)に対し、ϕSJI×SIJが、
ϕR=Rを満たすとき、ϕRのdualityという。
さらに、Rのdualityϕが、ϕϕ=e=(1I,1J)を満たすとき、
ϕRのpolarityという。

ここで疑問なのですが、「duarityを持つ結合構造Rは、必ずpolarityを持つ」のでしょうか?
これはおそらく偽であると私は考えているのですが、いまだに証明できていません。
また、「|I|=|J|=p(素数)であって、2-デザイン(※)の構造をもつ、I×Jそのものでなく、空でない結合構造がduarityを持つとき、それは必ずpolarityになる」でしょうか?
こちらは真な気がしていますが、まだ考え始めたばかりでなんとも言えません。

(※ある決まった程度の対称性をもった結合構造のこと。詳しくは、参考文献『群とデザイン』に解説されています。)

とても長く書きましたが、ここで終わります。
私の技術上、至らないところも多くあったと思います。
もし、お気付きの点や、改善点、疑問点などございましたら、ぜひ、コメントまでお願い致します。
最後までお読みいただき、本当にありがとうございました。

参考文献

[1]
永尾 汎, 群とデザイン, 数学選書, 岩波書店, 1974
投稿日:28日前
更新日:27日前
OptHub AI Competition

この記事を高評価した人

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

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

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

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

投稿者

krutr
krutr
18
1045
級数(複素,実解析における特殊値と代数)と、離散の有限数学(代数的組み合わせ論,根付き木)などに興味があります

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 結合構造とは
  2. 双対同型な結合構造の有名な例
  3. 本題ー双対同型な結合構造の数え上げ
  4. 参考文献