前回の記事:
2019年の阪大入試(理系)第4問(1)をめちゃくちゃ遠回りして解く その2
概要
今回は次の定理を証明します.
Stern-Brocotツリーの各頂点の分数は全て既約分数である.
さらに次回以降の準備のために次の定理を示します.
交点ベクトルツリーとStern-Brocotツリーの対応
交点ベクトルツリーの頂点を分数に置き換えたツリーはStern-Brocotツリーである.
Stern-Brocotツリーの定義に関しては
前々回の記事
,交点ベクトルツリーの定義に関しては
前回の記事
をどうぞ.
参考文献はいつものように[Gyo20]です.
辺の傾きと既約分数の定義
1点付きトーラスの三角形分割をとり,適当に歪めることでトーラスの普遍被覆上で次のような三角形分割を与えていると仮定します.
torusuniversal
ここで,横の辺,縦の辺,斜辺がそれぞれであるとします.
まず,三角形分割を構成する辺に対して傾きの概念を導入しましょう.次の図はからを取り除いたものです.
lattice
こうしてみると,2次元平面上の格子に見えますね.三角形分割の辺の傾きを,この格子における直線の傾きとして定義します.たとえば,
latticegrad
上の図の赤い直線に対応するトーラス上の辺の傾きはであるとします.また,図の縦軸に平行な直線に対応する三角形分割の辺(つまり)の傾きをと定めることにします.の傾きをで表すことにします.
さらに,既約分数の意味をここできちんと定義しておきましょう.
有理数の既約表示,既約分数
に対して, が次の条件を全て満たすとき,をの既約表示という:
さらにについてあるが存在して がの既約表示であるとき,を既約分数という.
加えて,ここではを既約表示をもつ数として定義しておきます.また,既約表示は任意の有理数またはに対して一意的であることに注意します.整数の既約表示はで与えられるところが少し普通の感覚とは異なるかもしれません.
また,の元の大小関係を,に対してはとの通常の有理数における大小関係,任意のとに対してはと定めます.
定理1の証明
さて,ここまでお膳立てが長々続きましたが,いよいよ定理1の証明に入ります.
まず次の補題を証明することから始めましょう.
を三角形分割,とする.このとき,次の2つの条件は同値である.
次のどちらかの不等式が成立する.
とが既約分数で,であるとき,である.
特に,任意の三角形分割に対してとが存在して,とが既約分数であって
となる.
1.を仮定して2.を証明する.のトーラスの普遍被覆上の線分としてとを結ぶ線分,とを結ぶ線分をとる.ここで,は既約であり,特にであることからこの2つの線分は第1象限または第4象限に含まれていることに注意する.が三角形分割であること,の傾きはの傾きとの傾きの中間であることから,トーラスの普遍被覆上で次の図の位置関係にあるようなに対応する線分を取ることができる(図はがいずれも第1象限にある場合である).
triangleijk
ここで,この図において3辺の左下の共有点の座標は,の以外の端点の座標はとである.このとき,の共有点以外の座標はである.よってが成立する.2.ならば1.は明らか.
さらに,次の事実が成立します.
を三角形分割,とする.
の辺の傾きについて
であるとき,が既約分数ならばは既約分数.
の辺の傾きについて
であるとき,が既約分数ならばかのどちらかは既約分数.
と仮定して一般性を失わない. (1)を示す.が既約でないと仮定する.であるから,である.このとき,とを結ぶ線分上にこの2点のどちらでもない格子点が存在する.の既約性より,とを結ぶ線分の間には格子点がない.よって,を通るに対応する直線は,に対応するとを結ぶ線分と格子点でない位置で交わる.これはが1点付きトーラスの三角形分割であることに矛盾する.
(2)について,であるとき,が既約分数であることが(1)と同様の方法で示される.であるときも同様にが既約分数であることが示される.であるとき,はトーラスの普遍被覆における縦軸に平行な直線に対応する.であるときは上と同様の議論からであることが示され,となってこれが既約分数となる.のときはに同じ議論を適用することで,が既約分数となる.
さて,これを踏まえて次の命題を証明しましょう.
を三角形分割,とする.
を仮定する.
を,をでフリップした三角形分割とする.このとき,次のどちらかの不等式が成立する.
を,をでフリップした三角形分割とする.このとき,このとき,次の不等式が成立する.
を,をでフリップした三角形分割とする.このとき,次の不等式が成立する.
この命題は,三角形分割を構成する辺のうち傾きの大きさが真ん中の辺をフリップすると,入れ替わった辺の傾きは最大または最小になり,逆に傾きの大きさが最大または最小の辺をフリップすると,入れ替わった辺の傾きは真ん中の大きさになることを意味しています.
(1)だけ証明する.他は同様.でが既約であるとする.補題3から,であり,は補題3の証明中の図の位置関係になっている(ただし傾きが大きい方がである).三角形分割をでフリップすると次のようになる.
flipping
このときの傾きはとなる.補題4から,の既約表示はかのどちらかである.が既約表示である場合,,と置き直すことでとなる.よって,補題3とから
を得る.一方,が既約表示である場合は同様にして
を得る.
さて,(定義は
前回の記事
を参照)のとのラベルがついた枝で繋がっている頂点をとして,を経由せずにへたどり着けるようなの頂点全体からなるの部分木を考えます.下の図からとにつながる枝を取り除いたものがです.
treeT3
に対応する三角形分割(定義は
前回の記事
)に対して,と定義します.そして,の各頂点にを対応させたツリーをと表すことにします.ただし,ここでは各成分は既約分数であると約束しておくことにします.
次の定理が示されればゴールはもうすぐです.
Fareyトリプルツリーの定義は
前々回の記事
をご覧ください.簡単のため,この定理の証明中,(ツリーのある頂点から)「右側,左側の頂点」という言葉を使用しますが,これらは全て下図のツリーにおける右側,左側を指すものとします.
treeT3
であるから,をでフリップしたについて,補題5からであり,さらに補題3からである.よってとなってFareyトリプルツリーの初期条件に一致する.ここで,次にの右側の頂点に移るためにフリップされるのはまたはであるが,これらの傾きはにおいて最大または最小であるため,補題5からフリップした後の三角形分割において,新しく入れ替えられた辺の傾きは真ん中の大きさとなる.これを繰り返すことで,の頂点における分数の3つ組において,左側に伸びている枝のラベルに対応する成分は常に真ん中の大きさであることと,左側の頂点から右側の頂点へ移るときに入れ替える分数の大きさは,常にその3つ組において最大か最小であることが示される.よって,の頂点においてが真ん中の大きさであれば,は右側の頂点に移るときにその成分のうちかのどちらかを入れ替えられ,さらに補題3からその値はとであり,さらに補題4からこれらは既約分数である.が真ん中の大きさの時も同様.これはFareyトリプルツリーの規則に一致している.よって示された.
この定理から直ちに定理1が証明されます.
定理1(Stern-Brocotツリーの頂点の分数の既約性)の証明
定理6からFarey tripleツリーに現れる分数は全て既約分数である.Stern-BrocotツリーはFarey tripleツリーの成分を取り出したものなので,定理が成立する.
定理2の証明
最後に,定理2を証明します.まず次の事実を確認しておきましょう.
定理6からの既約表示はStern-Brocotツリーのある頂点に一致する.Stern-Brocotツリーの構成法からがわかる.
定理2を示すためには,次の定理が本質的です.
を, を満たす三角形分割の辺とする.このとき,(ただしは既約分数)であることとであることは同値である.
ここで,は
前回の記事
で導入したのに対する交点ベクトルです.
トーラスの普遍被覆上において,に対応する線分で格子点を端点以外に含まないようなものを取る.このとき,は既約分数であり定理7からである.この線分はに対応する直線(横線)を回,に対応する直線(縦線)を回横切る.また,全部で個の格子を横切るが,これはに対応する直線を横切る回数に等しい.
さて,いよいよ定理2を証明します.
定理6から,Stern-Brocotツリーは三角形分割の傾きを使って以下のように記述できる.
treegrad
一方,交点ベクトルツリーはこの頂点のをに置き換えたものである.よって,定理8の対応を用いることで定理2が従う.
これで今回の主定理が全て示されました.次回はCalkin-WilfツリーとStern-Brocotツリーの双対性について説明します.そこで得られる双対性とこの2つの定理からCalkin-Wilfツリーの分数の既約性を従わせることができます.今回もここまでお読みいただき,ありがとうございました.
次の記事:
2019年の阪大入試(理系)第4問(1)をめちゃくちゃ遠回りして解く その4
参考文献
- [Gyo20] Y. Gyoda, Cluster duality between Calkin-Wilf tree and Stern-Brocot tree, 2020. preprint, arXiv:2009.06473 [math.NT]