二分木にまつわる不思議な等式の話
序
二分木と呼ばれる構造を次のように定義します：
集合$\BT$は以下の条件を満たすものとする：
- $\BT$は非空であり、特に$*\in\BT$で表される要素が存在する。
- 任意の$t_1,t_2\in\BT$に対して、$(t_1,t_2)\in\BT$。
- 上記の2条件から帰納的に定まる集合が$\BT$である。すなわち、$B_0=\{*\},$ $B_{n+1}=B_n\cup\{(t_1,t_2)\mid t_1,t_2\in B_n\}$とするとき、$\BT=\bigcup_{n\in\mathbb{N}}B_n$である。
このとき、$\BT$の各要素を二分木という。
ふつう二分木といえばグラフ構造ですが、定義が簡単になるので項として定義しています。
定義から、二分木の集合$\BT$に対してカノニカルな同型$\varphi:1+\BT\times\BT\xrightarrow{\sim}\BT$が存在します。この同型の定義は
$$
\varphi(x)=
\begin{cases}
*& x\in 1\\
(t_1,t_2)& x=\langle t_1,t_2\rangle\in\BT\times\BT
\end{cases}
$$
で定義できますが、この同型はそれぞれの木の上側 (根の近く) のみを参照しており、枝葉部分の構造に依存していません。このような写像を非常に明示的 (very explicit) と呼ぶことにします (精確な定義は［Blass 1995］を参照してください)。
さて、突然ですが$\varphi$の構成から、$\BT$は等式$1+X^2=X$の解と見なすことにします。この等式を通常の整数係数多項式の等式$X^2-X+1=0$と同一視すると、この解は
\begin{align}
(X^2-X+1)(X+1)(X^2+X+1)(X-1)X
&=(X^3+1)(X^3-1)X\\
&=(X^6-1)X\\
&=X^7-X
\end{align}
より、等式$X^7=X$の解の1つでもあることがわかります。
ここで、二分木と等式$X^7=X$に関するとてもおもしろい定理を紹介します：
すべての二分木の集合$\BT$と二分木の7つ組すべての集合$\BT^7$の間には、非常に明示的な全単射が存在する。
この定理は、$X^2-X+1=0$から導かれる他の等式であっても一般には成立しません。例えば$X^6=1$や$X^3+1=0$では明らかに成立しません。
また、$\BT$は無限集合なので、$\mathbb{N}$係数で次数が1以上の多項式$P(X),Q(X)$に対して$P(\BT)\simeq Q(\BT)$を満たすような同型写像を無数に取れますが、非常に明示的な同型写像についてはこの限りではなく、例えば非常に明示的な$X^2\to X$の同型写像は存在しません。
このような現象はなにも二分木および等式$X^7=X$に限ったことではなく、集合の世界においてもある種の代数が存在して、集合の問題と代数の問題が同一視できる状況が存在するという事実によって発生します。本稿ではそのような集合の世界の不思議な等式と代数について見ていこうと思います。
「7つの木が1つに」
まずは実際に同型射$\BT^7\xrightarrow{\sim}\BT$を構成してみたいと思います。
$s=\langle t_1,\dots,t_7\rangle\in\BT^7$に対して、$f_0(s)\in\BT$を次のように定める：
- $t_4,t_5,t_6,t_7$のいずれかが$*$でない場合、$f_0(s)=((((((t_1,t_2),t_3),t_4),t_5),t_6),t_7)$
- $t_4=\cdots=t_7=*$かつ$t_3=(u,u')$の場合、$f_0(s)=((((*,t_1),t_2),u),u')$
- $t_3=\cdots=t_7=*$かつ$t_2\neq *$の場合、$f_0(s)=(((((t_1,t_2),*),*),*),*)$
- $t_2=\cdots=t_7=*$かつ$t_1=((((u_1,u_2),u_3),u_4),u_5)$とおける場合、$f_0(s)=(((((*,u_1),u_2),u_3),u_4),u_5)$
- それ以外の場合、$f_0(s)=t_1$
このとき$f$は全単射かつ非常に明示的である。
非常に明示的な全単射は1つではなく、他にも構成方法は存在します。
$s=\langle t_1,\dots,t_7\rangle\in\BT^7$に対して、以下で定める$f_1:\BT^7\to\BT$は全単射かつ非常に明示的である：
- $t_5,t_6,t_7$のいずれかが$*$でない場合、$f_1(s)=((((((t_1,t_2),t_3),t_4),t_5),t_6),t_7)$
- $t_5=t_6=t_7=*$かつ$t_4=(u,u')$のとき、$f_1(s)=(((((*,t_1),t_2),t_3),u),u')$
- $t_4=\cdots=t_7=*$かつ$t_3=(u,u')$のとき、$f_1(s)=((((((t_1,t_2),u),u'),*),*),*)$
- $t_3=\cdots=t_7=*$かつ$t_2=(u,u')$のとき、$f_1(s)=(((*,t_1),u),u')$
- $t_2=\cdots=t_7=*$かつ$t_1=(((u_1,u_2),u_3),u_4)$と書けるとき、$f_1(s)=((((*,u_1),u_2),u_3),u_4)$
- それ以外の場合、$f_1(s)=t_1$
$s=\langle t_1,\dots,t_7\rangle\in\BT^7$に対して、以下で定める$f_2:\BT^7\to\BT$は全単射かつ非常に明示的である：
- $t_5,t_6,t_7$のいずれかが$*$でない場合、$f_2(s)=((((((t_1,t_2),t_3),t_4),t_5),t_6),t_7)$
- $t_5=t_6=t_7=*$かつ$t_4=(u,u')$のとき、$f_2(s)=(((((*,t_1),t_2),t_3),u),u')$
- $t_4=\cdots=t_7=*$かつ$t_3=(u,u')$のとき、$f_2(s)=((((*,t_1),t_2),u),u')$
- $t_2=\cdots=t_7=*$かつ$t_1=(((u_1,u_2),u_3),u_4)$と書けるとき、$f_2(s)=((((t_1,*),*),*),*)$
- それ以外の場合、$f_2(s)=t_1$
集合たちの代数
等式$X^2+1=X$に立ち返ってみます。集合として解釈する場合、加法$+$とは集合の直和、乗法$\times$とは直積、それぞれの単位元$0,1$とは空集合およびシングルトンです。
集合としての解釈をする場合、加法の逆操作としての減法は存在しません (†)。そこで、係数に負数を使わない状態で$X^2+1=X$から等式をいろいろ変形させてみましょう。
$\BT$は$X=X^3+X+1$および$X^2=X^3+X^2+1$の解。すなわち、非常に明示的な同型$\BT\simeq \BT^3+\BT+1$および$\BT^2\simeq \BT^3+\BT^2+1$が存在する。
任意の木$t\in\BT$は、$((t_1,t_2),t_3),$ $(*,t'),$ $*$のいずれかちょうど1つの形で表せる。従って、このことから同型$\BT\simeq\BT^3+\BT+1$を得て、これは構成から非常に明示的である。
また、任意の木の組$\langle t,t'\rangle\in\BT^2$は、$\langle t,(u,u')\rangle,$ $\langle(u,u'),*\rangle,$ $\langle *,*\rangle$のいずれかちょうど1つの形で表せる。このことから同型$\BT^2\simeq\BT^3+\BT^2+1$を得て、これは構成から非常に明示的である。
$\BT$について、等式$X^3+1=X^4+X$を満たす非常に明示的な同型$\BT^3+1\simeq\BT^4+\BT$が存在する。
$r\geq 1$とする。このとき、任意の$k$に対して
- $X=X^2+1$ならば、$X^r=X^{k+3}+X^{k}+X^r$
- $\BT^r\simeq \BT^{k+3}+\BT^{k}+\BT^r$
$s\in\BT^3+1$とは、$s=*\in 1$または$s=\langle t_1,t_2,t_3\rangle\in\BT^3$のどちらかであることとする。$s\in\BT^3+1$に対して、$\varphi(s)\in\BT^4+\BT$を次のように定める：
- $s=\langle t_1,t_2,(t_3,t'_3)\rangle$のとき、$\varphi(s)=\langle t_1,t_2,t_3,t'_3\rangle\in\BT^4$
- $s=\langle t_1,t_2,*\rangle$のとき、$\varphi(s)=(t_1,t_2)\in\BT$
- $s=*\in 1$のとき、$\varphi(s)=*\in\BT$
写像$\varphi:\BT^3+1\to\BT^4+\BT$は定義から非常に明示的であり、さらに同型である。
(系の証明) $X=X^2+1$であるとき、等式$X=X^3+X+1$が成り立つことから、$m\geq 0$に対して
$$
X^{m+1}=X^{m+4}+X^{m+1}+X^m
$$
を得る。さらに$X^3+1=X^4+X$が成り立つため、$k$に関する帰納法を用いると$r\geq 1$と$k\geq 0$に対して
$$
X^r=X^{k+3}+X^k+X^r
$$
を得る。同様にして、非常に明示的な同型
$$
\BT^r=\BT^{k+3}+\BT^k+\BT^r
$$
の存在もわかる。
補題3の系を用いることで、等式$X^7=X$を次のように証明することができます：
$$
X^7=X^7+X^4+X=X
$$
これに対応する$\BT$についての同型は非常に明示的ですので、アドホックでない形で定理の証明を与えることもこれで可能になります。
加法の逆操作としての減法は存在しませんが、$X+1+X\simeq X$というような性質を満たす、ある意味で“負の単位集合”に相当する集合および代数を構成することは可能です。(cf. Shaunel 1990)
多項式半環
集合に関する代数は、結合的な加算と乗算を持ち、分配則が成り立つため、半環の構造を持っているとみなせます。$\BT$と非常に明示的な同型の場合は、剰余多項式半環$\mathbb{N}[X]/(X=X^2+1)$に関連付けられます。
2つの形式的な非負整数係数多項式$P(X),Q(X)\in\mathbb{N}[X]$について、$P(\BT)$と$Q(\BT)$の間に非常に明示的な同型が存在することと、剰余半環$\mathbb{N}[X]/(X=X^2+1)$において$P(X)=Q(X)$になることは同値。
$\mathbb{N}[X]/(X=X^2+1)$の世界では、$X^3+1=0$や$X^6-1=0$の代わりに、次のような等式が成り立ちます：
多項式$P(X)=a_NX^N+\cdots+a_1X+a_0$ ($a_N\neq 0$) に対して$N$を$P$の次数と呼ぶことにする。$P(X)$の次数が1より大きいとき、$\mathbb{N}[X]/(X=X^2+1)$において
- $X^3+P(X)+1=P(X)$
- $X^6+P(X)=P(X)+1$
可換半環の公理と$X=X^2+1$からこれらの等式を求める証明を辿ることで、その証明に対応する非常に明示的な同型(の1つ)を求めることができます。Blassの構成方法に対応する導出は次のようになります。
\begin{align} X^7 &=X^8+X^7+X^6+X^5+X^4+X^3+X^2+1\\ &=(X^8+X^7+X^6+X^5+X^3)+X^4+X^2+1\\ &=X^7+X^4+X^2+1\\ &=X^7+X^4+(X^5+X^3+X^2+X)+1\\ &=X^7+X^5+X^4+X^3+X^2+X+1\\ &=X \end{align}
発展
同じことを別の同値関係に行うことで、類似の命題を示すことができます。
項 (あるいは根つき木) の集合$P$を以下のように定める：
- $0\in P$
- $p\in P$ならば、$s(p)\in P$
- $p,q\in P$ならば、$(p+q)\in P$
- 以上の操作を繰り返して得られる項のみが$P$の要素である。
木構造として記述すると、すべての頂点で枝の数が高々2 (すなわち、出入りする辺の数が高々3) であるような木の集合が$P$であり、従って
$$
P\simeq 1+P+P\times P
$$
が非常に明示的な形で成り立つ。
$P$の5つ組$s=\langle p_1,p_2,p_3,p_4,p_5\rangle\in P^5$に対して、$f_P(s)\in P$を次のように定める：
- $p_5\neq 0$または$p_4\neq 0$のとき、$f_P(s)=((((p_1+p_2)+p_3)+p_4)+p_5)$
- $p_5=p_4=0$かつ$p_3=(q+q')$とおけるとき、$f_P(s)=(((s(p_1)+p_2)+q)+q')$
- $p_5=p_4=0$かつ$p_3=s(q)$とおけるとき、$f_P(s)=((s(p_1)+p_2)+q)$
- $p_5=p_4=p_3=0$かつ$p_2=(q+q')$とおけるとき、$f_P(s)=((((p_1+q)+q')+0)+0)$
- $p_5=p_4=p_3=0$かつ$p_2=s(q)$とおけるとき、$f_P(s)=(s(p_1)+q)$
- $p_5=\cdots=p_2=0$かつ$p_1=((q_1+q_2)+q_3)$とおけるとき、$f_P(s)=(((0+q_1)+q_2)+q_3)$
- $p_5=\cdots=p_2=0$かつ$p_1=(s(q)+q')$とおけるとき、$f_P(s)=((0+q)+q')$
- それ以外のとき、$f_P(s)=p_1$
これによって定まる$f_P:P^5\to P$は非常に明示的かつ同型である。
項 (あるいは根つき木) の集合$T$を
$$
T\simeq 1+T+T^3
$$
が非常に明示的に成り立つように定める。すなわち、定数項$\star$、単項演算子$\diamond(t)$、3項演算子$\sigma(t_1,t_2,t_3)$によって帰納的に構成される項の集合を$T$とする。
このとき、非常に明示的な同型$T\simeq T^7$が存在する。
まとめ
半環という馴染みのない構造にはなりますが、集合や木構造の間にもある種の代数が存在することと、それらの関係性をここまで見てきました。半環が比較的弱い代数構造であるがゆえに、この関係は代数構造と集合との間において一方を他方で実装するための強力なツールを与えます ([Fiore & Leinster, 2004], [Backhouse, Chen & Ferreira, 2013] など)。身の回りにあるデータ構造や代数構造にも、探してみたらおもしろい特性が見つかるかもしれませんね。
リンク
- [Backhouse, Chen & Ferreira, 2013] The algorithmics of solitaire-like games
- [Blass, 1995] Seven trees in one
- [Fiore & Leinster, 2004] An objective representation of the Gaussian integers
- [Lawvere 1990] Some thoughts on the future of category theory
- [Shaunel, 1990] Negative sets have Euler characteristic and dimension