大学数学基礎解説

2019年の阪大入試（理系）第4問（1）をめちゃくちゃ遠回りして解くその2

代数学,入試数学

560

前回の記事： 2019年の阪大入試（理系）第4問（1）をめちゃくちゃ遠回りして解くその1

概要

今回は次の定理の準備を行います（説明が結構大変で証明に入る前に力つきました）．

Stern-Brocotツリーの各頂点の分数は全て既約分数である．

さらに，この定理の証明中に出てくる事実を用いて次の定理が与えられます．

交点ベクトルツリーとStern-Brocotツリーの対応

交点ベクトルツリーの頂点 $[\begin{matrix} x \\ y \\ z \end{matrix}]$ を分数 $\frac{x + 1}{y + 1}$ に置き換えたツリーはStern-Brocotツリーである．

交点ベクトルツリーとはなんぞや？と思われると思いますので，今回はそこら辺を説明していくことにします．2つの定理の証明は次回行います．

今回の内容も全て[Gyo20]に基づいています．

1点付きトーラスの三角形分割

証明のために準備をしていきます．まずは前回記事の最後で唐突に出てきたこいつについてちゃんと説明をします.
torus torus
これはトーラスに1点の印をつけて，これを頂点とした三角形分割を一つ与えた図です．このままだとあんまり三角形分割って感じがしないので縦の辺と横の辺に沿ってハサミを入れてみましょう．
expandedtorus
これだと確かに三角形分割になってるのがわかるかと思います．四隅の点はトーラス上では全て同じ点であり，上下の辺の組や左右の辺の組はそれぞれトーラス上で同じ辺であることに注意しましょう．
さて，このトーラスの三角形分割を，辺を1個変えて別の三角形分割になるようにしてみましょう．
expandedtorus2
これを思い浮かべたそこのあなた，ご名答です．
torus2 torus2
ちょうどこんなのに対応します．
このように，三角形分割に対して一つの辺を入れ替えて新しい三角形分割を与えることを，「（辺を）フリップする」といいます．
さて，実はフリップできるのは斜辺だけではありません．
triangulated
これ本当に1辺を入れ替えた三角形分割？と思われるかもしれませんが，左右にあった辺や上下にあった辺を入れ替えることも可能なんですね．一番長い対角線に沿ってこれらの紙を切り，点線のところでピタッと張り合わせると，ちゃんと三角形分割になっていることがみて取れます（これらに対応するトーラスはめんどくさくて描く気が起きませんでしたのでトーラスの図は省略します）．しかしこれらの図はぱっと見でちゃんと1点付きトーラスの三角形分割になっているかわかりにくいですね．どんな分割の仕方であっても一発でそれとわかるような図の書き方が欲しいところです．そこで，こんな図を使います．
torusuniversal
この図において，頂点の黒丸は全てトーラス上の1点であり，平行な辺は全てトーラス上の同じ線分です．これならさっきの三角形分割が全部見やすくなりますね．もうトーラスの絵はこれ以降は描かず，これをトーラスの三角形分割と言い張ることにします．この平面のことをトーラスの普遍被覆と呼びますが，今回は別に覚える必要はありません．
triangulated3
上の図は横の辺，縦の辺，斜辺のフリップにそれぞれ対応しています．明らかなことではありますが，一回フリップした辺でもう一回フリップすると，元の三角形分割に戻ってきます．

交点ベクトルツリーとStern-Brocotツリー

さて，トーラス上の三角形分割を任意に一つ取ります．三角形分割を構成する辺を用いて $L = (ℓ_{1}, ℓ_{2}, ℓ_{3})$ と書くことにします．どんな三角形分割をとってきても，トーラスの普遍被覆を適当に歪めることでさっきと同じ下の図の状態とみなすことができるので，予めこの形にしておきます．
torusuniversal
特に，上の図において，横線を $ℓ_{1}$ ，縦線を $ℓ_{2}$ ，左上から右下にかけての斜線を $ℓ_{3}$ であると仮定します．ここで改めてフリップの操作を以下のように定義します．

フリップ

$k \in {1, 2, 3}$ とする． $L = {ℓ_{1}, ℓ_{2}, ℓ_{3}}$ の $k$ 方向のフリップを， $L$ を $ℓ_{k}$ を入れ替えて得ることができる一意的な三角形分割 $φ_{k} (L)$ に移す変換と定める．

このフリップ操作を，最初にとってきた三角形分割 $L$ をスタート地点として，繰り返し行っていくことを考えます．これらの三角形分割に添字を振りましょう． $T_{3}$ を各頂点から3本の枝が伸びている，サイクルのないツリーとします．ここで，一つの頂点から出る3本の枝には，それぞれ $1, 2, 3$ のラベルが振られているとします． $T_{3}$ のある頂点 $t_{0}$ に三角形分割 $L$ を置き， $t_{0}$ とラベル $k$ の枝で繋がっている頂点に三角形分割 $φ_{k} (L)$ を配置します．これを帰納的に行っていき， $T_{3}$ の全ての頂点に三角形分割を配置します．頂点 $t \in T_{3}$ に配置される三角形分割を $L_{t} = (ℓ_{1; t}, ℓ_{2; t}, ℓ_{3; t})$ と表示することにします．特に， $L = L_{t_{0}}$ です．これで $L$ からフリップを繰り返して得られる全ての三角形分割に添字を振ることができました．日本語だけではわかりにくいと思うので，図示もしておきます．
treeT3 treeT3
上図は $T_{3}$ において $t_{0}$ から $3$ のラベルがついている枝から伸びている部分を切り取ったものであり，便宜的に各頂点に番号を振ってあります．ここへ三角形分割を配置します．
treeT3triangle
ここで，例えば $L_{t_{6}}$ は $L_{t_{3}}$ と $1$ のラベルがついた枝で繋がっているので， $L_{t_{6}} = φ_{1} (L_{t_{3}})$ です．

さて，次に交点ベクトルというベクトルを定義します．

交点ベクトル

$L = (ℓ_{1}, ℓ_{2}, ℓ_{3})$ を三角形分割， $ℓ$ をある三角形分割の辺とする． $ℓ$ が $ℓ_{1}, ℓ_{2}, ℓ_{3}$ とそれぞれトーラス上の点を除いて $f_{1}, f_{2}, f_{3}$ 回交わるとき，
$F (L, ℓ) = [\begin{matrix} f_{1} \\ f_{2} \\ f_{3} \end{matrix}]$
を $ℓ$ の $L$ に対する交点ベクトルという．

交点ベクトルを使って，次のような樹形図を考えましょう．まず，初期状態の三角形分割 $L$ から斜辺である $ℓ_{3}$ をフリップします．そして，新しく現れた辺 $ℓ_{3}^{'}$ の $L$ における交点数を求めます．
triangulatedfliped
上の図の赤い線が $ℓ_{3}^{'}$ です（本当は平行にいくつも連なっていますが一本だけ取り出しました）．この図の点はトーラス上では全て同じ点なので，点から点への線分がトーラス上の辺に対応しています．この線分と他の3辺との交点の数が交点ベクトルの成分となります．この場合だと， $ℓ_{1}$ （横の辺）とは点以外の場所で0回， $ℓ_{2}$ （縦の辺）とも0回， $ℓ_{3}$ （左斜めの辺）とは1回交わっているので，
$F (L, ℓ_{3}^{'}) = [\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}]$
を得ます．ここをスタート地点として， $L_{t_{1}} = (ℓ_{1}, ℓ_{2}, ℓ_{3}^{'})$ の状態から次に続けて $ℓ_{1}$ または $ℓ_{2}$ でフリップすることを考えます．まず $ℓ_{1}$ をフリップした場合は
triangle5
となるので，これによって新しく得た辺 $ℓ_{1}^{″}$ の一番最初の三角形分割 $L$ に対する交点ベクトルを考えると，
triangulated6
上の図の点から点への赤線の線分との交点の数を数えて
$F (L, ℓ_{1}^{″}) = [\begin{matrix} 1 \\ 0 \\ 2 \end{matrix}] .$
同様に， $ℓ_{2}$ でフリップした場合は，
triangulated4
となるので，これによって新しく得た辺 $ℓ_{2}^{″}$ の一番最初の三角形分割 $L$ に対する交点ベクトルを考えると，
triangulated7
$F (L, ℓ_{2}^{″}) = [\begin{matrix} 0 \\ 1 \\ 2 \end{matrix}]$
を得ます．最初に得たベクトル $[\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}]$ からこの2つの交点ベクトル $[\begin{matrix} 1 \\ 0 \\ 2 \end{matrix}], [\begin{matrix} 0 \\ 1 \\ 2 \end{matrix}]$ に枝を伸ばします．枝にはフリップした成分の番号をラベルします．
subtree1
以下同様に，三角形分割をフリップして新しい辺を得るごとに最初の三角形分割 $L$ との交点ベクトルを計算してツリーを右の方へ伸ばしていきます．先ほどの添字づけられた三角形分割の記号を使って書くとこんな感じ．
treeintersectionvector
このツリーのことを，交点ベクトルツリーと呼ぶことにしましょう．最初の7つのベクトルは以下のようになっています．
subtree2
定理2をもう一度眺めてみましょう．

再掲

交点ベクトルツリーの頂点 $[\begin{matrix} x \\ y \\ z \end{matrix}]$ を分数 $\frac{x + 1}{y + 1}$ に置き換えたツリーはStern-Brocotツリーである．

実際に上の交点ベクトルから第1成分と第2成分を取り出してそれぞれ1を足して分数にしたものを書き下してみると， tree3 tree3 となって，確かにStern-Brocotツリーと一致していることがわかります（なってないじゃんと思った方，ここでのStern-Brocotツリーは一般的な定義とは少し異なる形で定義されているので，定義については前回の記事をご覧ください）．