こんにちは。krutrです。
今回は、ある組み合わせ対象の特殊なクラスの同型を除いた数え上げについて、解説します。
前提知識として、対称群の共役類に関する知識や、群作用の理論(バーンサイドの補題など)を仮定します。
また、説明が煩雑になりすぎないため、議論を省略することがあります。予めご了承ください。
まずは、今回数え上げを行う「結合構造」という組み合わせ対象の説明をしていきます。
結合構造(例)の図示
$I,J$を共通の元を持たない2つの(空でない)集合とし、Rを直積集合$I\times J$の部分集合とするとき、組$(I,J,R)$を結合構造という。
結合構造の同型(例)
2つの結合構造$(I,J,R)$と$(I',J',R')$が同型であるとは、次のときをいう。:
ある2つの全単射$f:I\rightarrow I',g:J\rightarrow J'$が存在して、
$R'=\{\,(f(i),g(j))\in I'\times J'\,|\,(i,j)\in R\,)\}$である。
結合構造の双対(例)
結合構造$(I,J,R)$の双対とは、$\bar{R}=\{\,(j,i)\in J\times I\,|\,(i,j)\in R\,)\}$としたとき、$(J,I,\bar{R})$のことである。
双対同型な結合構造(例)
結合構造$(I,J,R)$が、その双対$(J,I,\bar{R})$と同型であるとき、$(I,J,R)$は、双対同型(self-dual)であるという。
位数2の有限射影平面(左)と位数3の有限射影平面(右)の図示
有名な、双対同型な結合構造の例として、デザルグな有限射影平面があります。図はそれぞれ、位数が2,3の有限射影平面を表しています。それぞれの点の集合を$I$、それぞれの曲線の集合を$J$とします。これまでのように図示する事も出来ます。興味のある方はぜひチャレンジしてみてください。
この記事では、互いに要素数$n$の、共通部分を持たない2つの集合$I,J$に対し、$I\times J$に含まれる双対同型な結合構造の、同型を除いた(同一視した)数を数えていきます。
ここから先、$I,J$はそれぞれ固定された$n$点集合とし、$I\times J$の部分集合$R$について考察するので、結合構造$(I,J,R)$を$R$と同一視して、単に$R$を結合構造と呼びます。
まず、計算に必要な諸概念を定義します。
$S_{I}$を、$I$から$I$への全単射の全体、$S_{J}$を$J$から$J$への全単射の全体とする。
$\quad(\alpha,\gamma)\cdot(\beta,\delta):=(\alpha\beta,\gamma\delta)$
とする。
$ $
$S_{IJ}$を、$I$から$J$への全単射の全体、$S_{JI}$を$J$から$I$への全単射の全体とする。
$\quad(\kappa,\mu)*(\lambda,\nu):=(\kappa\nu,\mu\lambda)$
とする。
$I$と$J$がどっちがどっちやら紛らわしいですが、ここはあまり重要ではないので、面倒なら飛ばしても全然大丈夫です。$S_I,S_J$はそれぞれ、$I,J$上の置換群と同一視できることを意識しておいてください。
次は重要です。
$\quad\theta\cdot r:=(\alpha(i),\beta(j))$
とし、さらに、
$\quad\theta\cdot R=\{\,\theta\cdot r\,|\,r\in R\}:=\{\,(\alpha(i),\beta(j))\,|\,(i,j)\in R\}$
とする。
$ $
$\quad\phi * r:=(\tau(j),\sigma(i))$
とし、さらに、
$\quad\phi* R=\{\,\phi* r\,|\,r\in R\}:=\{\,(\tau(j),\sigma(i))\,|\,(i,j)\in R\}$
とする。
※これらは群作用ではない。ここでは作用の語を、「$S_{JI}\times S_{IJ}$の各元$\phi$に対して、$\phi\,*$が、$I\times J, \mathcal{P}(I\times J)$上の置換と同一視できる」意味で用いている。
演算$*$をよく観察すると、これを用いて双対同型な結合構造のクラスが定義できそうだと分かりますね。
ある結合構造$R\in\mathcal{P}(I\times J)$が、
$\exists\phi\in S_{JI}\times S_{IJ},\,\,\,\phi*R=R$
を満たす時、$R$は双対同型であるという。
また、その全体を、
$D_{IJ}:=\{R\in\mathcal{P}(I\times J)\,|\,\exists\phi\in S_{JI}\times S_{IJ},\,\,\,\phi*R=R\}$
で表し、双対同型な結合構造のクラスという。
$D_{IJ}$に対しても、$(S_I\times S_J,\cdot),(S_{JI}\times S_{IJ},*) $は作用することは簡単に分かります。
今回は、この$D_{IJ}$の、同型を除いた数え上げ、すなわち、$D_{IJ}/(S_I\times S_J,\cdot\,)$の大きさを求めます。
ここで、$D_{IJ}/(S_{JI}\times S_{IJ},*)$は考えられるのか、考えなくてよいのか、と思われるかもしれませんが、実はこれは考えられる上に、$D_{IJ}/(S_I\times S_J,\cdot\,)$と一致します。
証明はしませんが、ここでは双対同型な結合構造全体を考えていて、どちらの作用も結合構造を本質的に変えないので、直感的には明らかです。
次の補題が、今回の数え上げの肝です。
$|D_{IJ}/(S_I\times S_J,\cdot\,)|=\displaystyle\frac{1}{n!^2} \displaystyle\sum_{\phi\in S_{JI}\times S_{IJ}}|D_{IJ}^{\phi*}|$
$\qquad\qquad\qquad\qquad\,=\displaystyle\frac{1}{n!^2}\displaystyle\sum_{\phi\in S_{JI}\times S_{IJ}}\{R\in D_{IJ}\,|\,\,\phi*R=R\} $
バーンサイドの補題より、
$|D_{IJ}/(S_I\times S_J,\cdot\,)|=\displaystyle\frac{1}{n!^2} \displaystyle\sum_{\theta\in S_I\times S_J}|D_{IJ}^{\theta\,\cdot}|$
$\qquad\qquad\qquad\qquad\,=\displaystyle\frac{1}{n!^2}\displaystyle\sum_{\theta\in S_{I}\times S_{J}}|\{R\in D_{IJ}\,|\,\,\theta\cdot R=R\}| $
$\qquad\qquad\qquad\qquad\,=\displaystyle\frac{1}{n!^2} \sum_{R\in D_{IJ}} |\{\theta\in S_I\times S_J\,|\,\,\theta\cdot R=R\}|$
ここで、$R\in D_{IJ}$に対して、
$|\{\theta\in S_I\times S_J\,|\,\,\theta\cdot R=R\}|=|\{\phi\in S_{JI}\times S_{IJ}\,|\,\,\phi* R=R\}|$を示す。
左辺を$A$、右辺を$B$と置き、次の$f$は全単射であることを示す。
$f:B\rightarrow A$
$\quad\,\,\phi\,\mapsto\phi*\phi_1$
(ただし、$\phi_1$は$\phi_1*R=R$を満たす$S_{JI}\times S_{IJ}$の元)
まず、$f$が写像であること($\phi*\phi_1$がきちんと$A$に入っていること)を確認します。
$(\phi*\phi_1)\cdot R=\phi*(\phi_1*R)=R$
より、$f$は写像です。
また、$f$の単射性は明らかなので、全射性を示します。
$\theta=(\alpha,\beta)\in S_I\times S_J $を任意にとり、$\phi_1=(\tau_1,\sigma_1)$とすると、$\phi=(\alpha\sigma_1^{-1},\beta\tau_1^{-1})\in B$ (※)
$\phi*\phi_1=(\alpha\sigma_1^{-1},\beta\tau_1^{-1})*(\tau_1,\sigma_1)=\theta$
※$\phi*R=(\alpha\sigma_1^{-1},\beta\tau_1^{-1})*R$
$\qquad\quad\,\,\,=(\alpha\sigma_1^{-1},\beta\tau_1^{-1})*((\tau_1,\sigma_1)*R)$
$\qquad\quad\,\,\,=((\alpha\sigma_1^{-1},\beta\tau_1^{-1})*(\tau_1,\sigma_1))\cdot R$
$\qquad\quad\,\,\,=\theta\cdot R$
$\qquad\quad\,\,\,= R$
よって、
$|D_{IJ}/(S_I\times S_J,\cdot\,)|=\displaystyle\frac{1}{n!^2} \sum_{R\in D_{IJ}} |\{\phi\in S_{JI}\times S_{IJ}\,|\,\,\phi* R=R\}|$
$\qquad\qquad\qquad\qquad\,=\displaystyle\frac{1}{n!^2}\displaystyle\sum_{\phi\in S_{JI}\times S_{IJ}}\{R\in D_{IJ}\,|\,\,\phi*R=R\} $
長かったですね。途中、やや特殊な計算を説明なしに行っています。
非常に申し訳ないのですが、ゆっくり行間を埋めればきちんと読めるようにはなっているはずですので、ここはこのまま進ませてください。
この計算によって、各$\phi\in S_{JI}\times S_{IJ} $に対して、$\phi\,*$によって変化しない$R\in D_{IJ}$の数を求めればよいと分かります。
ここから先は、$ \phi\in S_{JI}\times S_{IJ}$を任意に一つとって固定し、その固定点集合$D_{IJ}^{\phi*}$の大きさを求めていきます。
まず、次のような考察をします。
$r\in I\times J$に対し、列 $r,\,\phi*r,\,\phi*(\phi*r),\,\phi*(\phi*(\phi*r)),\,...$は必ず巡回し、
$[r]_\phi=\{r,\,\phi*r,\,\phi*(\phi*r),\,\phi*(\phi*(\phi*r)),\,...\}$とすると、
$(I\times J)/\langle\phi\rangle:=\{\,[r]_\phi\,|\,r\in I\times J\}$は$I\times J$の分割となる。
また、
$|D_{IJ}^{\phi*}|=|\mathcal{P}((I\times J)/\langle\phi\rangle)|=2^{|I\times J/\langle\phi\rangle|}$
である。
直感的には、さほど難しい話ではないと思います。
証明はここも省きますが、具体的には、次の全単射を構成すればよいです。
$f:\mathcal{P}((I\times J)/\langle\phi\rangle)\rightarrow D_{IJ}^{\phi*}$
$\qquad\qquad\,\,\,\,\mathcal{M}\quad\longmapsto\bigsqcup \mathcal{M}$
ここから、$(I\times J)/\langle\phi\rangle $の元をここでは極小固定点と呼び、この極小固定点を任意にいくつか選んだ非交和が、固定点を尽くしているということですから、この数を調べます。この際、次のように考えます。
$\phi=(\tau,\sigma)\in S_{JI}\times S_{IJ}$の2回作用$\phi*(\phi\,*\,\,\,\,)$は、群の作用$(\phi*\phi)\,\,\cdot=(\tau\sigma,\sigma\tau)\,\,\cdot$となっていることを利用します。
次の項目から、厳密性に欠いた定義が出てきます。
私の技術的な問題で、厳密さを重視すると冗長になってしまうためです。
直感的には難しくないと思います。自信のある方は、厳密で綺麗な定義に直して進んで下されば幸いです。
$\phi=(\tau,\sigma)\in S_{JI}\times S_{IJ}$とする。
$\tau\sigma\in S_I$を、巡回置換の積として書く方法を、巡回置換の掛け順と各巡回置換の表示を完全に指定して適当に(好きに)1つ選び、それを、
$\tau\sigma=(i_0^1i_1^1...)(i_0^2i_1^2...)...(i_0^ui_1^u...)...(i_0^mi_1^m...)$ $\quad $(ただし$m=|I/\langle\tau\sigma\rangle|$)
とする。(各$u$に対して、$I^u:=\{i_0^u,i_1^u...\}$と定め、$i_k^u$の下添え字$k$は、$\mathbb{Z}/\!|I^u| \mathbb{Z}$の元であるとする。)
また、任意の$u\in\{1,2,...,m\}$に対し、
$\sigma(I^u):=J^u$とし、さらに、任意の$k\in\mathbb{Z}/\!|I^u| \mathbb{Z}=\mathbb{Z}/\!|J^u| \mathbb{Z}$に対して、
$\sigma(i_k^u):=j_k^u$
とする。
任意の$j\in J$に対し、$j=j_k^u$となる$u\in\{1,2,...,m\},\,\,k\in\mathbb{Z}/\!|J^u| \mathbb{Z}=\mathbb{Z}/\!|I^u| \mathbb{Z}$が一意に存在し、
$\sigma\tau=(j_0^1j_1^1...)(j_0^2j_1^2...)...(j_0^uj_1^u...)...(j_0^mj_1^m...)$$\quad$(ただし$m=|I/\langle\tau\sigma\rangle|$)
であり、さらに、
$\tau(j_k^u)=i_{k+1}^u$
である。
一行目は明らかとしてよい。
$ \sigma(i_k^u)=j_k^u$の両辺に$\tau$を作用させると、
$ \tau\sigma(i_k^u)=\tau (j_k^u)$より、
$i_{k+1}^u=\tau (j_k^u)$
さらに両辺に$\sigma$を作用させると、
$j_{k+1}^u=\sigma\tau (j_k^u)$
これによって$\sigma\tau$ の表示が定まる。
次は、$I\times J$を、都合の良い大まかな固定点に分解していきます。
$I\times J=\left(\displaystyle\bigsqcup_{1\leq u\leq m}(I^u\times J^u)\right)\sqcup\left(\displaystyle\bigsqcup_{1\leq u< v\leq m}((I^u\times J^v)\sqcup(I^v\times J^u))\right) $
と分解でき、それぞれの$I^u\times J^u,\,\,(I^u\times J^v)\sqcup(I^v\times J^u)$は、$\phi\,*$による固定点となっている。
$I,J$それぞれの分解を考えれば、式自体は明らかです。
固定点になっていることも、$\phi\,*$によって、$ (I^u\times J^u)$は動きませんし、$ (I^u\times J^v)$は$(I^v\times J^u)$と交換されることを考えれば分かります。
次は、これらの二種類の固定点が、いくつの極小固定点に分解されるか、をそれぞれ観察します。
任意の$u,v\in\{1,2,...,m\}$$\,$(ただし$m=|I/\langle\tau\sigma\rangle|$)に対し、
1.$I^u\times J^u$に含まれる極小固定点は、$\left\lceil \displaystyle\frac{|I^u|}{2} \right\rceil$個
2.$(I^u\times J^v)\sqcup(I^v\times J^u)\quad(u\neq v)$に含まれる極小固定点は、$\gcd(|I^u|,|I^v|)$個
$1.\,\,I^u\times J^u$の場合
$r=(i,j)\in I^u\times J^u$を任意にとる。
$[r]_\phi=\{r,\phi*r,\phi*(\phi*r),\phi*(\phi*(\phi*r)),...\}$
ある$k,l\in\mathbb{Z}/\!|I^u| \mathbb{Z}$がそれぞれ一意に定まり$r=(i_k^u,j_l^u)$であり、
$[r]_\phi=\{(i_k^u,j_l^u),(i_{l+1}^u,j_k^u),(i_{k+1}^u,j_{l+1}^u),(i_{l+2}^u,j_{k+1}^u),...\}$
ここで、$[r]_\phi$は第一成分が$i_0^u$である元を必ず持つことに注意すると、
$[r]_\phi=\{(i_0^u,j_{l'}^u),(i_{l'+1}^u,j_0^u), (i_{1}^u,j_{l'+1}^u),(i_{l'+2}^u,j_{1}^u)...\} $
と書き直せる。新たに、$r'=(i_0^u,j_{l'}^u)$とおき、
次の二つの集合$[r’]_\phi^e,[r’]_\phi^o$を考える:
$[r’]_\phi^e=\{r’,\phi*(\phi*r’),\phi*(\phi*(\phi*(\phi*r’)),...\}$
$[r’]_\phi^o=\{\phi*r’,\phi*(\phi*(\phi*r’)),\phi*(\phi*(\phi*(\phi*(\phi*r’))))...\} $
すると、$[r’]_\phi^e=[r’]_\phi^o=[r’]_\phi $または、$[r’]_\phi^e\sqcup[r’]_\phi^o=[r’]_\phi $であり、また、
$[r’]_\phi^e=\{(i_0^u,j_{l'}^u),(i_{1}^u,j_{l'+1}^u),(i_{2}^u,j_{l’+2}^u)...\}$
$[r’]_\phi^o=\{(i_{l'+1}^u,j_0^u),(i_{l'+2}^u,j_{1}^u),(i_{l'+3}^u,j_{2}^u)...\}$
より、$|[r’]_\phi^e|=|[r’]_\phi^o|=|I^u|$である。
$[r’]_\phi^e=[r’]_\phi^o=[r’]_\phi $を仮定する。
このとき、$r'$が$[r’]_\phi^o$に入っていることが必要十分であり、
$$
\begin{eqnarray}
\left\{
\begin{array}{l}
0=l'+1+h \\
l'=h
\end{array}
\right.
\end{eqnarray}
$$
をみたす$h\in\mathbb{Z}/\!|I^u| \mathbb{Z}$があればよいが、$2h+1=0,2l'+1=0$より、$|I^u|$は奇数であるしかなく、さらにそのとき$h=l'= \frac{|I^u|-1}{2} $より、このような極小固定点はただ一つ存在し、その大きさは$|[r’]_\phi |=|[r’]_\phi^e|=|[r’]_\phi^o|=|I^u|$である。
それ以外の場合は自動的に$[r’]_\phi^e\sqcup[r’]_\phi^o=[r’]_\phi $であり、極小固定点の大きさは
$|[r’]_\phi|=|[r’]_\phi^e|+|[r’]_\phi^o|=2|I^u|$となるので、
$|I^u|$が奇数のとき、$I^u\times J^u$に含まれる極小固定点の数は、
$\frac{|I^u\times J^u|-|I^u|}{2|I^u|} +1= \frac{|I^u|+1}{2}$
$|I^u|$が偶数のとき、$I^u\times J^u$に含まれる極小固定点の数は、
$\frac{|I^u\times J^u|}{2|I^u|}= \frac{|I^u|}{2}$
$2,\,\,(I^u\times J^v)\sqcup(I^v\times J^u)\quad(u\neq v)$の場合
$r=(i,j)\in (I^u\times J^v)\sqcup(I^v\times J^u)\quad(u\neq v)$を任意にとる。
$r\in I^u\times J^v$または$r\in I^v\times J^u$なので、
まず$r\in I^u\times J^v$の場合を考える。
$[r]_\phi=\{r,\phi*r,\phi*(\phi*r),\phi*(\phi*(\phi*r)),...\}$
ここで次の二つの集合$[r]_\phi^e,[r]_\phi^o$を考える:
$[r]_\phi^e=\{r,\phi*(\phi*r),\phi*(\phi*(\phi*(\phi*r)),...\}$
$[r]_\phi^o=\{\phi*r,\phi*(\phi*(\phi*r)),\phi*(\phi*(\phi*(\phi*(\phi*r))))...\} $
ある$k\in\mathbb{Z}/\!|I^u| \mathbb{Z},l\in\mathbb{Z}/\!|I^v| \mathbb{Z}$がそれぞれ一意に定まり$r=(i_k^u,j_l^v)$であり、
$[r]_\phi^e=\{(i_k^u,j_l^v),(i_{k+1}^u,j_{l+1}^v),(i_{k+2}^u,j_{l+2}^v)...\}$
$[r]_\phi^o=\{(i_{l+1}^v,j_k^u),(i_{l+2}^v,j_{k+1}^u),(i_{l+3}^v,j_{k+2}^u)...\}$
明らかに$[r]_\phi^e\sqcup[r]_\phi^o=[r]_\phi $であり、また、
$|[r]_\phi^e|=|[r]_\phi^o|=\mathrm{lcm}(|I^u|,|I^v|)$
よって$|[r]_\phi|=|[r]_\phi^e|+|[r]_\phi^o|=2\mathrm{lcm}(|I^u|,|I^v|)$
$r\in I^v\times J^u$の場合も同様なので、
すべての極小固定点の大きさは等しく、$2\mathrm{lcm}(|I^u|,|I^v|) $
よって、$(I^u\times J^v)\sqcup(I^v\times J^u)$に含まれる極小固定点の数は、
$ \frac{|(I^u\times J^v)\sqcup(I^v\times J^u)|}{2\mathrm{lcm}(|I^u|,|I^v|)} =\gcd(|I^u|,|I^v|)$
大変でしたね、、、
しかし、とても興味深い観察だったと思います。
さて、詰めです。
$I^u$たちの大きさは、$\phi=(\tau,\sigma)$として、$\tau\sigma$の示す$I$の分割に依存していたことを思い出しましょう。
$\sigma\in S_n$に対し、$\sigma$の示す$n$の分割を$a_1,a_2,...a_m$とするとき、
$f(\sigma)= \displaystyle\sum_{1\leq u\leq m}\left\lceil \displaystyle\frac{a_u}{2} \right\rceil+\displaystyle\sum_{1\leq u< v\leq m}\gcd(a_u,a_v)$
とする。
$|D_{IJ}/(S_I\times S_J,\cdot\,)|=\displaystyle\frac{1}{n!} \displaystyle\sum_{\sigma\in S_n}2^{f(\sigma)}$
$\quad|D_{IJ}/(S_I\times S_J,\cdot\,)|$
$=\displaystyle\frac{1}{n!^2} \displaystyle\sum_{\phi\in S_{JI}\times S_{IJ}}|D_{IJ}^{\phi*}|$
$=\displaystyle\frac{1}{n!^2} \displaystyle\sum_{\phi\in S_{JI}\times S_{IJ}}2^{|I\times J/\langle\phi\rangle|}$
$=\displaystyle\frac{1}{n!^2} \displaystyle\sum_{\phi\in S_{JI}\times S_{IJ}}2^{|\left(\left(\bigsqcup_{1\leq u\leq m}(I^u\times J^u)\right)\sqcup\left(\bigsqcup_{1\leq u< v\leq m}((I^u\times J^v)\sqcup(I^v\times J^u))\right)\right)/\langle\phi\rangle|}$
$=\displaystyle\frac{1}{n!^2} \displaystyle\sum_{\phi\in S_{JI}\times S_{IJ}}2^{|\left(\bigsqcup_{1\leq u\leq m}(I^u\times J^u)/\langle\phi\rangle\right)|+|\left(\bigsqcup_{1\leq u< v\leq m}((I^u\times J^v)\sqcup(I^v\times J^u))/\langle\phi\rangle\right)|}$
$=\displaystyle\frac{1}{n!^2} \displaystyle\sum_{\tau,\sigma\in S_n}2^{f(\tau\sigma)}$
$=\displaystyle\frac{1}{n!} \displaystyle\sum_{\sigma\in S_n}2^{f(\sigma)}$
これにて、証明終了となります。
この数列を$D_n$とし、少し計算してみると、
$D_1=2,D_2=5,D_3=16,D_4=67,D_5=660,... $と続きます。
この数列自体について考察してみるのも面白いかもしれませんね。
最後に、気になっている関連問題について書かせてください。
$R\in\mathcal{P}(I\times J)$に対し、$\phi\in S_{JI}\times S_{IJ}$が、
$\phi*R=R$を満たすとき、$\phi$を$R$のdualityという。
さらに、$R$のduality$\phi$が、$\phi*\phi=e=(1_I,1_J)$を満たすとき、
$\phi$を$R$のpolarityという。
ここで疑問なのですが、「duarityを持つ結合構造$R$は、必ずpolarityを持つ」のでしょうか?
これはおそらく偽であると私は考えているのですが、いまだに証明できていません。
また、「$|I|=|J|=p$(素数)であって、2-デザイン(※)の構造をもつ、$I\times J$そのものでなく、空でない結合構造がduarityを持つとき、それは必ずpolarityになる」でしょうか?
こちらは真な気がしていますが、まだ考え始めたばかりでなんとも言えません。
(※ある決まった程度の対称性をもった結合構造のこと。詳しくは、参考文献『群とデザイン』に解説されています。)
とても長く書きましたが、ここで終わります。
私の技術上、至らないところも多くあったと思います。
もし、お気付きの点や、改善点、疑問点などございましたら、ぜひ、コメントまでお願い致します。
最後までお読みいただき、本当にありがとうございました。