5

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

290
0

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

概要

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

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

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

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

交点ベクトルツリーの頂点[xyz]を分数x+1y+1に置き換えたツリーはStern-Brocotツリーである.

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

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

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

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

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

qQに対して, n(q),d(q)Zが次の条件を全て満たすとき,n(q)d(q)q既約表示という:

  • q=n(q)d(q),
  • gcd(n(q),d(q))=1,
  • d(q)>0.

さらにabについてあるqQが存在してabqの既約表示であるとき,ab既約分数という.

加えて,ここではを既約表示10をもつ数として定義しておきます.また,既約表示は任意の有理数またはに対して一意的であることに注意します.整数nの既約表示はn1で与えられるところが少し普通の感覚とは異なるかもしれません.
また,Q{}の元の大小関係を,p,qQに対してはpqの通常の有理数における大小関係,任意のpQに対してはp<と定めます.

定理1の証明

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

M=(m1,m2,m3)を三角形分割,{i,j,k}={1,2,3}とする.このとき,次の2つの条件は同値である.

  1. 次のどちらかの不等式が成立する.
    gradL(mi)<gradL(mj)<gradL(mk)orgradL(mk)<gradL(mj)<gradL(mi).

  2. abcdが既約分数で,gradL(mi)=ab,gradL(mk)=cdであるとき,gradL(mj)=a+cb+dである.

特に,任意の三角形分割M=(m1,m2,m3)に対してa,cZb,dZ0が存在して,abcdが既約分数であって
{gradL(m1),gradL(m2),gradL(m3)}={ab,cd,a+cb+d}
となる.

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

さらに,次の事実が成立します.

M=(m1,m2,m3)を三角形分割,{i,j,k}={1,2,3}とする.

  1. Mの辺の傾きについて
    {gradL(m1),gradL(m2),gradL(m3)}={ab,cd,a+cb+d}
    であるとき,ab,cdが既約分数ならばa+cb+dは既約分数.

  2. Mの辺の傾きについて
    {gradL(m1),gradL(m2),gradL(m3)}={ab,cd,acbd}
    であるとき,ab,cdが既約分数ならばacbdcadbのどちらかは既約分数.

(gradL(m1),gradL(m2),gradL(m3))=(ab,cd,a+cb+d)と仮定して一般性を失わない. (1)を示す.a+cb+dが既約でないと仮定する.b+d>0であるから,gcd(a+c,b+d)=k>1である.このとき,(0,0)(b+da+c)を結ぶ線分上にこの2点のどちらでもない格子点(b+dk,a+ck)が存在する.abの既約性より,(b,a)(0,0)を結ぶ線分の間には格子点がない.よって,(b+dk,a+ck)を通るm2に対応する直線は,m1に対応する(b,a)(0,0)を結ぶ線分と格子点でない位置で交わる.これはMが1点付きトーラスの三角形分割であることに矛盾する.
(2)について,bd>0であるとき,acbdが既約分数であることが(1)と同様の方法で示される.bd<0であるときも同様にcadbが既約分数であることが示される.bd=0であるとき,m3はトーラスの普遍被覆における縦軸に平行な直線に対応する.ac1であるときは上と同様の議論からac=1であることが示され,acbd=10となってこれが既約分数となる.ac1のときはca1に同じ議論を適用することで,cadb=10が既約分数となる.

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

M=(m1,m2,m3)を三角形分割,{i,j,k}={1,2,3}とする.
gradL(mi)<gradL(mj)<gradL(mk)
を仮定する.

  1. M={mi,mj,mk}を,Mmjでフリップした三角形分割とする.このとき,次のどちらかの不等式が成立する.
    gradL(mj)<gradL(mi)<gradL(mk)orgradL(mi)<gradL(mk)<gradL(mj).

  2. M={mi,mj,mk}を,Mmiでフリップした三角形分割とする.このとき,このとき,次の不等式が成立する.
    gradL(mj)<gradL(mi)<gradL(mk).

  3. M={mi,mj,mk} を,Ltmkでフリップした三角形分割とする.このとき,次の不等式が成立する.
    gradL(mi)<gradL(mk)<gradL(mj).

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

(1)だけ証明する.他は同様.gradL(mi)=ab,gradL(mk)=cdでab,cdが既約であるとする.補題3から,gradL(mk)=a+cb+dであり,mi,mj,mkは補題3の証明中の図の位置関係になっている(ただし傾きが大きい方がmkである).三角形分割をmjでフリップすると次のようになる.
flipping flipping
このときmjの傾きはgradL(mk)=acbdとなる.補題4から,gradL(mk)の既約表示はacbdcadbのどちらかである.acbdが既約表示である場合,ac=e,bd=fと置き直すことでgradL(mi)=ab=c+ed+fとなる.よって,補題3とgradL(mi)<gradL(mk)から
gradL(mj)<gradL(mi)<gradL(mk)
を得る.一方,cadbが既約表示である場合は同様にして
gradL(mi)<gradL(mk)<gradL(mj)
を得る.

さて,T3(定義は 前回の記事 を参照)のt03のラベルがついた枝で繋がっている頂点をt1として,t0を経由せずにt1へたどり着けるようなT3の頂点全体からなるT3の部分木T3を考えます.下の図からt0t1につながる枝を取り除いたものがT3です.
treeT3 treeT3
tT3に対応する三角形分割Lt=(1;t,2;t,3;t)(定義は 前回の記事 )に対して,gradL(Lt):=(gradL(1;t),gradL(2;t),gradL(3;t))と定義します.そして,T3の各頂点にgradL(Lt)を対応させたツリーをTree(gradL)と表すことにします.ただし,ここでは各成分は既約分数であると約束しておくことにします.
次の定理が示されればゴールはもうすぐです.

Tree(gradL)はFareyトリプルツリーである.

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

gradL(L)=(01,10,11)であるから,L3でフリップしたLt1について,補題5から01<gradL(3;t)<10であり,さらに補題3からgradL(3;t)=0+11+0=11である.よってgradL(Lt1)=(01,10,11)となってFareyトリプルツリーの初期条件に一致する.ここで,次にT3の右側の頂点に移るためにフリップされるのは1;t1=1または2;t1=2であるが,これらの傾きはLt1において最大または最小であるため,補題5からフリップした後の三角形分割において,新しく入れ替えられた辺の傾きは真ん中の大きさとなる.これを繰り返すことで,Tree(gradL)の頂点における分数の3つ組において,左側に伸びている枝のラベルに対応する成分は常に真ん中の大きさであることと,左側の頂点から右側の頂点へ移るときに入れ替える分数の大きさは,常にその3つ組において最大か最小であることが示される.よって,Tree(gradL)の頂点(ab,cd,ef)においてabが真ん中の大きさであれば,(ab,cd,ef)は右側の頂点に移るときにその成分のうちcdefのどちらかを入れ替えられ,さらに補題3からその値はa+eb+fa+cb+dであり,さらに補題4からこれらは既約分数である.cd,efが真ん中の大きさの時も同様.これはFareyトリプルツリーの規則に一致している.よって示された.

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

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

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

定理2の証明

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

任意のtT3i{1,2,3}に対して,gradL(i;t)0.

定理6からgradL(i;t)の既約表示はStern-Brocotツリーのある頂点に一致する.Stern-Brocotツリーの構成法からgradL(i;t)0がわかる.

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

LttT, F(L,)0を満たす三角形分割Ltの辺とする.このとき,gradL()=ab(ただしabは既約分数)であることとF(L,)=[a1b1a+b1]であることは同値である.

ここで,F(L,) 前回の記事 で導入したLに対する交点ベクトルです.

トーラスの普遍被覆上において,に対応する線分で格子点を端点以外に含まないようなものを取る.このとき,abは既約分数であり定理7からa,b>0である.この線分は1に対応する直線(横線)をa1回,1に対応する直線(縦線)をb1回横切る.また,全部でa+b1個の格子を横切るが,これは3に対応する直線を横切る回数に等しい.

さて,いよいよ定理2を証明します.

定理6から,Stern-Brocotツリーは三角形分割の傾きを使って以下のように記述できる.
treegrad treegrad
一方,交点ベクトルツリーはこの頂点のgradL()F(L,)に置き換えたものである.よって,定理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]
投稿日:20201115
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

rodin_math
204
39795

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 概要
  2. 辺の傾きと既約分数の定義
  3. 定理1の証明
  4. 定理2の証明
  5. 参考文献