大学数学基礎解説

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

代数学,入試数学

267

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

概要

今回は次の定理を証明します．

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

さらに次回以降の準備のために次の定理を示します．

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

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

Stern-Brocotツリーの定義に関しては前々回の記事，交点ベクトルツリーの定義に関しては前回の記事をどうぞ．

参考文献はいつものように[Gyo20]です．

辺の傾きと既約分数の定義

1点付きトーラスの三角形分割$L=(\ell_1,\ell_2,\ell_3)$をとり，適当に歪めることでトーラスの普遍被覆上で次のような三角形分割を与えていると仮定します．
torusuniversal
ここで，横の辺，縦の辺，斜辺がそれぞれ$\ell_1,\ell_2,\ell_3$であるとします．
まず，三角形分割を構成する辺に対して傾きの概念を導入しましょう．次の図は$L$から$\ell_3$を取り除いたものです．
lattice lattice
こうしてみると，2次元平面上の格子に見えますね．三角形分割の辺の傾きを，この格子における直線の傾きとして定義します．たとえば，
latticegrad
上の図の赤い直線に対応するトーラス上の辺$\ell$の傾きは$2$であるとします．また，図の縦軸に平行な直線に対応する三角形分割の辺（つまり$\ell_2$）の傾きを$\infty$と定めることにします．$\ell$の傾きを$\mathrm{grad}_L(\ell)$で表すことにします．
さらに，既約分数の意味をここできちんと定義しておきましょう．

有理数の既約表示，既約分数

$q\in\mathbb{Q}$に対して， $n(q),d(q)\in\mathbb{Z}$が次の条件を全て満たすとき，$\dfrac{n(q)}{d(q)}$を$q$の既約表示という：

$q=\dfrac{n(q)}{d(q)}$,
$\gcd (n(q),d(q))=1$,
$d(q)> 0$.

さらに$\dfrac{a}{b}$についてある$q\in\mathbb{Q}$が存在して$\dfrac{a}{b}$ が$q$の既約表示であるとき，$\dfrac{a}{b}$を既約分数という．

加えて，ここでは$\infty$を既約表示$\dfrac{1}{0}$をもつ数として定義しておきます．また，既約表示は任意の有理数または$\infty$に対して一意的であることに注意します．整数$n$の既約表示は$\dfrac{n}{1}$で与えられるところが少し普通の感覚とは異なるかもしれません．
また，$\mathbb{Q}\cup\{\infty\}$の元の大小関係を，$p,q\in\mathbb{Q}$に対しては$p$と$q$の通常の有理数における大小関係，任意の$p\in\mathbb{Q}$と$\infty$に対しては$p<\infty$と定めます．

定理1の証明

さて，ここまでお膳立てが長々続きましたが，いよいよ定理1の証明に入ります．
まず次の補題を証明することから始めましょう．

$M=(m_{1},m_{2},m_{3})$を三角形分割，$\{i,j,k\}=\{1,2,3\}$とする．このとき，次の2つの条件は同値である．

次のどちらかの不等式が成立する．
\begin{align} \mathrm{grad}_L(m_{i})<\mathrm{grad}_L(m_{j})<\mathrm{grad}_L(m_{k})\quad \text{or}\quad \mathrm{grad}_L(m_{k})<\mathrm{grad}_L(m_{j})<\mathrm{grad}_L(m_{i}). \end{align}
$\dfrac{a}{b}$と$\dfrac{c}{d}$が既約分数で，$\mathrm{grad}_L(m_{i})=\dfrac{a}{b},\mathrm{grad}_L(m_{k})=\dfrac{c}{d}$であるとき，$\mathrm{grad}_L(m_{j})=\dfrac{a+c}{b+d}$である．

特に，任意の三角形分割$M=(m_{1},m_{2},m_{3})$に対して$a,c\in\mathbb Z$と$b,d\in\mathbb Z_{\geq0}$が存在して，$\dfrac{a}{b}$と$\dfrac{c}{d}$が既約分数であって
$$\left\{\mathrm{grad}_L(m_{1}),\mathrm{grad}_L(m_{2}),\mathrm{grad}_L({m_{3}})\right\}=\left\{\dfrac{a}{b},\dfrac{c}{d},\dfrac{a+c}{b+d}\right\}$$
となる．

1.を仮定して2.を証明する．$m_i,m_k$のトーラスの普遍被覆上の線分として$(0,0)$と$(b,a)$を結ぶ線分，$(0,0)$と$(d,c)$を結ぶ線分をとる．ここで，$\dfrac{a}{b},\dfrac{c}{d}$は既約であり，特に$b,d\geq 0$であることからこの2つの線分は第1象限または第4象限に含まれていることに注意する．$M$が三角形分割であること，$m_j$の傾きは$m_i$の傾きと$m_k$の傾きの中間であることから，トーラスの普遍被覆上で次の図の位置関係にあるような$m_j$に対応する線分を取ることができる（図は$m_i,m_k$がいずれも第1象限にある場合である）．
triangleijk
ここで，この図において3辺の左下の共有点の座標は$(0,0)$，$m_i,m_k$の$(0,0)$以外の端点の座標は$(b,a)$と$(d,c)$である．このとき，$m_j$の共有点以外の座標は$(b+d,a+c)$である．よって$\mathrm{grad}_L(m_{j})=\dfrac{a+c}{b+d}$が成立する．2.ならば1.は明らか．

さらに，次の事実が成立します．

$M=(m_{1},m_{2},m_{3})$を三角形分割，$\{i,j,k\}=\{1,2,3\}$とする．

$M$の辺の傾きについて
$$\left\{\mathrm{grad}_L(m_{1}),\mathrm{grad}_L(m_{2}),\mathrm{grad}_L({m_{3}})\right\}=\left\{\dfrac{a}{b},\dfrac{c}{d},\dfrac{a+c}{b+d}\right\}$$
であるとき，$\dfrac{a}{b},\dfrac{c}{d}$が既約分数ならば$\dfrac{a+c}{b+d}$は既約分数．
$M$の辺の傾きについて
$$\left\{\mathrm{grad}_L(m_{1}),\mathrm{grad}_L(m_{2}),\mathrm{grad}_L({m_{3}})\right\}=\left\{\dfrac{a}{b},\dfrac{c}{d},\dfrac{a-c}{b-d}\right\}$$
であるとき，$\dfrac{a}{b},\dfrac{c}{d}$が既約分数ならば$\dfrac{a-c}{b-d}$か$\dfrac{c-a}{d-b}$のどちらかは既約分数．

$\left(\mathrm{grad}_L(m_{1}),\mathrm{grad}_L(m_{2}),\mathrm{grad}_L({m_{3}})\right)=\left(\dfrac{a}{b},\dfrac{c}{d},\dfrac{a+c}{b+d}\right)$と仮定して一般性を失わない． (1)を示す．$\dfrac{a+c}{b+d}$が既約でないと仮定する．$b+d>0$であるから，$\gcd(a+c,b+d)=k>1$である．このとき，$(0,0)$と$(b+d，a+c)$を結ぶ線分上にこの2点のどちらでもない格子点$\left(\dfrac{b+d}{k},\dfrac{a+c}{k}\right)$が存在する．$\dfrac{a}{b}$の既約性より，$(b,a)$と$(0,0)$を結ぶ線分の間には格子点がない.よって，$\left(\dfrac{b+d}{k},\dfrac{a+c}{k}\right)$を通る$m_2$に対応する直線は，$m_1$に対応する$(b,a)$と$(0,0)$を結ぶ線分と格子点でない位置で交わる．これは$M$が1点付きトーラスの三角形分割であることに矛盾する．
(2)について，$b-d>0$であるとき，$\dfrac{a-c}{b-d}$が既約分数であることが(1)と同様の方法で示される．$b-d<0$であるときも同様に$\dfrac{c-a}{d-b}$が既約分数であることが示される．$b-d=0$であるとき，$m_3$はトーラスの普遍被覆における縦軸に平行な直線に対応する．$a-c\geq1$であるときは上と同様の議論から$a-c=1$であることが示され，$\dfrac{a-c}{b-d}=\dfrac{1}{0}$となってこれが既約分数となる．$a-c\leq-1$のときは$c-a\geq1$に同じ議論を適用することで，$\dfrac{c-a}{d-b}=\dfrac{1}{0}$が既約分数となる．

さて，これを踏まえて次の命題を証明しましょう．

$M=(m_1,m_2,m_3)$を三角形分割，$\{i,j,k\}=\{1,2,3\}$とする.
\begin{align} \mathrm{grad}_L(m_i)<\mathrm{grad}_L(m_j)<\mathrm{grad}_L(m_k) \end{align}
を仮定する．

$M'=\{m_{i},m'_{j},m_{k}\}$を，$M$を$m_j$でフリップした三角形分割とする．このとき，次のどちらかの不等式が成立する．
\begin{align} \mathrm{grad}_L(m'_{j})<\mathrm{grad}_L(m_{i})<\mathrm{grad}_L(m_{k})\quad \text{or}\quad \mathrm{grad}_L(m_{i})<\mathrm{grad}_L(m_{k})<\mathrm{grad}_L(m'_{j}). \end{align}
$M''=\{m''_{i},m_{j},m_{k}\}$を，$M$を$m_i$でフリップした三角形分割とする．このとき，このとき，次の不等式が成立する．
\begin{align} \mathrm{grad}_L(m_{j})<\mathrm{grad}_L(m''_{i})<\mathrm{grad}_L(m_{k}). \end{align}
$M'''=\{m_{i},m_{j},m'''_{k}\}$ を，$L_t$を$m_k$でフリップした三角形分割とする．このとき，次の不等式が成立する．
\begin{align} \mathrm{grad}_L(m_{i})<\mathrm{grad}_L(m'''_{k})<\mathrm{grad}_L(m_{j}). \end{align}

この命題は，三角形分割を構成する辺のうち傾きの大きさが真ん中の辺をフリップすると，入れ替わった辺の傾きは最大または最小になり，逆に傾きの大きさが最大または最小の辺をフリップすると，入れ替わった辺の傾きは真ん中の大きさになることを意味しています．

(1)だけ証明する．他は同様．$\mathrm{grad}_L(m_{i})=\dfrac{a}{b},\mathrm{grad}_L(m_{k})=\dfrac{c}{d}$で$\dfrac{a}{b},\dfrac{c}{d}$が既約であるとする．補題3から，$\mathrm{grad}_L(m_{k})=\dfrac{a+c}{b+d}$であり，$m_i,m_j,m_k$は補題3の証明中の図の位置関係になっている（ただし傾きが大きい方が$m_k$である）．三角形分割を$m_j$でフリップすると次のようになる．
flipping
このとき$m'_j$の傾きは$\mathrm{grad}_L(m_{k})=\dfrac{a-c}{b-d}$となる．補題4から，$\mathrm{grad}_L(m_{k})$の既約表示は$\dfrac{a-c}{b-d}$か$\dfrac{c-a}{d-b}$のどちらかである．$\dfrac{a-c}{b-d}$が既約表示である場合，$a-c=e$,$b-d=f$と置き直すことで$\mathrm{grad}_L(m_{i})=\dfrac{a}{b}=\dfrac{c+e}{d+f}$となる．よって，補題3と$\mathrm{grad}_L(m_i)<\mathrm{grad}_L(m_k)$から
\begin{align} \mathrm{grad}_L(m'_{j})<\mathrm{grad}_L(m_{i})<\mathrm{grad}_L(m_{k}) \end{align}
を得る．一方，$\dfrac{c-a}{d-b}$が既約表示である場合は同様にして
\begin{align} \mathrm{grad}_L(m_{i})<\mathrm{grad}_L(m_{k})<\mathrm{grad}_L(m'_{j}) \end{align}
を得る．

さて，$\TT_3$（定義は前回の記事を参照）の$t_0$と$3$のラベルがついた枝で繋がっている頂点を$t_1$として，$t_0$を経由せずに$t_1$へたどり着けるような$\TT_3$の頂点全体からなる$\TT_3$の部分木$\TT'_3$を考えます．下の図から$t_0$と$t_1$につながる枝を取り除いたものが$\TT'_3$です．
treeT3 treeT3
$t\in\TT_3$に対応する三角形分割$L_t=(\ell_{1;t},\ell_{2;t},\ell_{3;t})$（定義は前回の記事）に対して，$\mathrm{grad}_L(L_t):=(\mathrm{grad}_L(\ell_{1;t}),\mathrm{grad}_L(\ell_{2;t}),\mathrm{grad}_L(\ell_{3;t}))$と定義します．そして，$\TT'_3$の各頂点に$\mathrm{grad}_L(L_t)$を対応させたツリーを$\mathrm{Tree}(\mathrm{grad}_L)$と表すことにします．ただし，ここでは各成分は既約分数であると約束しておくことにします．
次の定理が示されればゴールはもうすぐです．

$\mathrm{Tree}(\mathrm{grad}_L)$はFareyトリプルツリーである．

Fareyトリプルツリーの定義は前々回の記事をご覧ください．簡単のため，この定理の証明中，(ツリーのある頂点から)「右側，左側の頂点」という言葉を使用しますが，これらは全て下図のツリーにおける右側，左側を指すものとします．
treeT3 treeT3

$\mathrm{grad}_L(L)=\left(\dfrac{0}{1},\dfrac{1}{0},\dfrac{-1}{1}\right)$であるから，$L$を$\ell_3$でフリップした$L_{t_1}$について，補題5から$\dfrac{0}{1}<\mathrm{grad}_L(\ell_{3;t})<\dfrac{1}{0}$であり，さらに補題3から$\mathrm{grad}_L(\ell_{3;t})=\dfrac{0+1}{1+0}=\dfrac{1}{1}$である．よって$\mathrm{grad}_L(L_{t_1})=\left(\dfrac{0}{1},\dfrac{1}{0},\dfrac{1}{1}\right)$となってFareyトリプルツリーの初期条件に一致する．ここで，次に$\TT'_3$の右側の頂点に移るためにフリップされるのは$\ell_{1;t_1}=\ell_1$または$\ell_{2;t_1}=\ell_2$であるが，これらの傾きは$L_{t_1}$において最大または最小であるため，補題5からフリップした後の三角形分割において，新しく入れ替えられた辺の傾きは真ん中の大きさとなる．これを繰り返すことで，$\mathrm{Tree}(\mathrm{grad}_L)$の頂点における分数の3つ組において，左側に伸びている枝のラベルに対応する成分は常に真ん中の大きさであることと，左側の頂点から右側の頂点へ移るときに入れ替える分数の大きさは，常にその3つ組において最大か最小であることが示される．よって，$\mathrm{Tree}(\mathrm{grad}_L)$の頂点$\left(\dfrac{a}{b},\dfrac{c}{d},\dfrac{e}{f}\right)$において$\dfrac{a}{b}$が真ん中の大きさであれば，$\left(\dfrac{a}{b},\dfrac{c}{d},\dfrac{e}{f}\right)$は右側の頂点に移るときにその成分のうち$\dfrac{c}{d}$か$\dfrac{e}{f}$のどちらかを入れ替えられ，さらに補題3からその値は$\dfrac{a+e}{b+f}$と$\dfrac{a+c}{b+d}$であり，さらに補題4からこれらは既約分数である．$\dfrac{c}{d},\dfrac{e}{f}$が真ん中の大きさの時も同様．これはFareyトリプルツリーの規則に一致している．よって示された．

この定理から直ちに定理1が証明されます．

定理1（Stern-Brocotツリーの頂点の分数の既約性）の証明

定理6からFarey tripleツリーに現れる分数は全て既約分数である．Stern-BrocotツリーはFarey tripleツリーの成分を取り出したものなので，定理が成立する．

定理2の証明

最後に，定理2を証明します．まず次の事実を確認しておきましょう．

任意の$t\in\TT'_3$と$i\in\{1,2,3\}$に対して，$\mathrm{grad}_L(\ell_{i;t})\geq0$.

定理6から$\mathrm{grad}_L(\ell_{i;t})$の既約表示はStern-Brocotツリーのある頂点に一致する．Stern-Brocotツリーの構成法から$\mathrm{grad}_L(\ell_{i;t})\geq0$がわかる．

定理2を示すためには，次の定理が本質的です．

$\ell\in L_t$を$t\in\TT'$, $F(L,\ell)\neq0$を満たす三角形分割$L_t$の辺とする．このとき，$\mathrm{grad}_L(\ell)=\dfrac{a}{b}$（ただし$\dfrac{a}{b}$は既約分数)であることと$F(L,\ell)=\begin{bmatrix}a-1\\b-1\\a+b-1\end{bmatrix}$であることは同値である．

ここで，$F(L,\ell)$は前回の記事で導入した$\ell$の$L$に対する交点ベクトルです．

トーラスの普遍被覆上において，$\ell$に対応する線分で格子点を端点以外に含まないようなものを取る．このとき，$\dfrac{a}{b}$は既約分数であり定理7から$a,b>0$である．この線分は$\ell_1$に対応する直線（横線）を$a-1$回，$\ell_1$に対応する直線（縦線）を$b-1$回横切る．また，全部で$a+b-1$個の格子を横切るが，これは$\ell_3$に対応する直線を横切る回数に等しい．