この章では,十 型,一 型以外の残 りの型の2次形式 ∫に対 し,∫ と整数 ηが与えられた ときに∫が ηという値をとり得 るかを調べるための, ト
ポグラフを用いた有限アルゴリズムについて述べる。またその際
,そ
れ ぞれの型における2次 形式の トポグラフのもつ性質 も明 らかにする。5.1 +― 型の2次形式のトポグラフ
定理 5.1.1∫ を十一型の整数係数 2次形式 とする。 この ∫でラベル付け された トポグラフにおいて
1正
の値をとる面 と負の値をとる面に挟まれた辺がある。2そ
のような辺の全体は無限の長さの道を成す。(これを川 という。) 証明1∫
でラベル付けされた トポグラフにおいて頂点 SとTを
とつて
,Sの
周 りには少な くとも1つの正の面が,Tの
周 りには少な くとも1つ の負の面があるとする。∫は十一型なので, このような2 頂点は存在する。系
448よ
り,Sか
らTへ
到る道がある。(図 51を参照
)い
ま,Sの
周 りに負の値の面があれば証明すべきことはな い。Tの
周 りには負の値をとる面があるので,Sか
らTへ
到る道の途中で正の値の面 と負の値の面を周 りにもつ頂点
Pが
存在する。よって
,Pに
接続する辺に題意の辺が存在する。2∫
でラベル付けされた トポグラフにおいて,正
と負の面で挟まれた 辺をe。 とし,cOの
両端の頂点をP。,Plと する。この ときまず,互
いに異なる辺 θ
2(o=1,2, )が
存在 して,辺
c.の両側は正の値の 面 と負の値の面であることと,辺
ceは辺 θz̲1に隣接することを数 学的帰納法で示す。第5章
+型
以外 の2次形式の トポグラフ図
51定
理511の
1の証明(a)辺elについては頂点 ■ の周 りの面の正負を考 えると,図 52の
ようにいずれの場合 について も正,負の面 に挟 まれ る
el=PIP2
が とれ る。
+
P2
図52 elの とき
(b)辺 θz̲1まで存在 す る とき
,同
様 に頂点Rの
周 りの面 の正負 に 応 じて正,負
の面 に挟 まれたce=鳥
鳥+1が とれ る。P:+1
+
Pl+1
図
53e2̲1の
ときPOと PIを入れか えて考 えれ ば θ。,c̲1,α2,θ
3,
とい う辺 の69
P2
第5章
十型以外の2次形式の トポグラフ
列で
,各 t=‑1,‑2,‑3,…
.に ついて C̀+1,C̀が隣接 す る C,+1≠ θθこの両側が正̲̀1
,負
の面であるとなるもの も とれ る。 この とき, トポグラフは閉路 を もたない こ とか ら(… .c̲lθoθl… 。)は 無限の長 さの道 とな る。
次 に
,正
と負の面 に挟 まれた辺 は上述 の(.… こl Coel… 。)以 外 には存在 しない ことを示す。いま
,トポグラフの正と負の面で挟まれた辺の
1つを
Eとする。系
4.4.8より,川 をなす辺θ 。から Eへ 到る道″がある。仮に ,Eが
{cjlづ∈
Z}以外の辺だとすると,道 ″ は途中で
{ctlに Z}から外れていく。
(図5.4参照
)/｀ し
/・
・・・ ・・・
図 5.4:定 理5.1.1の証明
その部分 を ■ ,め,… .,EⅣ
=E(辺
の列)と す る。す る と,Elの
両側の面の値 は"と もに正"力」 ともに負"であ る。 それが ともに正で あ る として 民 の ラベル は 島+1に向か う方向に正で,民の両側 の面 の値 は正
70
第5章
+型
以外 の2次形式の トポグラフ で あることを数学 的帰納法で示 す。1■
につ いて は明 らか に正 しい。2民
につ いて主張が正 しい と仮定す ると,補
題431よ
り民 の辺の向か う先 の面 は正の値 で あ り
,か
つ,鳥
+1の ラベル も 鳥+2に向か う 方向に正であ る。 よつて図55のように 昆+1の両側 の面の値 は正 とな り
,a+1に
ついて も正 しい。図
55民
+1の ときよって
,帰
納法 によ りE=ENの
両側が正の値 を とる面 とな り矛盾。また,■ の両側の面の値が負であった場合 にも同様 にして コNの両側 の面が負の
値をとることを示すことができて矛盾となる。したがつてEは
{c.10∈ Z}の1つの辺 で あ る。
□
ここで
,川
が周期 的で あ る こ とを述 べ る。補題 5。1.2+― 型 の整 数 係 数2次形 式 で ラベ ル付 けされ た トポ グ ラ フ内 の川 にお いて
,川
全 体 の 向 きを定 め,辺
の ラベル は川 の 向 きを正 として 考 え る。 (逆 向 きの辺 の ラベル は負 と考 え る。)そ
して,川
の各 辺 θzの ラ ベル を ん。,両
側 の面 の値 を α。,b2と す る。(ただ し,αz>0>b。
とす る。)この とき,
ん 2=ち
,αz=%,bz=し
とな るo,′(o<′)が存在 す る。
所 誓 こ 碓窪 ξ r」 F1014精 ダ 誠 ξ 募属 で あ 乙
Q仇<0で
71
綱 >ウ Lか 2回 >岡
(51)第5章
十型 以外 の2次形 式の トポグラフ 72 である。
一方,
とな る ものが存在 す る。
□
定理 5。1.3+― 型 の整 数 係数2次形 式 で ラベ ル付 けされ た トポ グ ラ フに おいて
,川
を( c̲lco Cl )と す る。川全体 に向 きを定 めて,川
の 向 きを各辺 の 向 き とし,ceの ラベ ル を ん2,両側 の面 の値 を α2,Lと す る。(た だ し,α
2>0>れ
とす る。)こ の とき,あ
る自然数 ν が存在 して,任
意の整 数 oに 対 して
が成 り立つ。
証明 補題
512よ
りとな るo,′
て
,o=0
0,1,2,3,
==αん
=bた
=んん
(52)
を たにつ いて の
1た
=0の
と2
た=η の とき(52)が正 しい,つ
まりある
限で は有 方
曜
びり ぼ
お
︐ こ