girth と連結性

のでZ^p,qの固有値はX^p,qの固有値の一部となる．すなわち，Z^p,qの自明でない固有値はラマヌジャンの 範囲r2?

p,2?

psに入る．

p q

1のときも同様である．よってZ^p,qはラマヌジャングラフである．

3.2節のように法qで考える．

τq :HpZq ÑHpFqq

はΛ¹からHpFqqの可逆元の群HpFqqへの写像を作る．Z_qをHpFqqの中心とする：

Z_q tαPHpFqq :ααu.

α, βPΛ¹とするとαβのときτ_qpαq¹τ_qpβq PZ_qとなる．これはτ_q : Λ¹ÑHpFqqがwell-definedな 群準同型

Π_q : ΛÑHpFqq{Z_q

を作ることを意味する．Π_qの核をΛpqqとするとΠ_qの像は商群Λ{Λpqqだとわかる．T_p,q pΠ_qQqpS_pq とする．

補題3.2.1よりqをpに対して十分大きな数とすると（例えばq¡2?p），|Tp,q |p 1となる．グラ フY^p,qをTp,qによるΛ{Λpqqのケーリーグラフとする：

Y^p,q GpΛ{Λpqq, T_p,qq.

ΛはQpSp,qqにより生成されるから（命題3.3.1の証明より），命題3.1.2よりq¡2?pのときグラフ Y^p,qはpp 1q-正則で連結となる．

命題2.3.2の前の同型写像ψ :HpFqqÑGL2pqqはZqをGL2pqqの部分群であるスカラー行列に送り，

スカラー行列はφ : GL₂pqq ÑPGL₂pqqの核となる．したがって同型写像 β :HpFqq{Zq ÑPGL2pqq を定義できる．

これによりX^p,qとY^p,qを可換図式により比較できる．

τq ψq

Sp€Λ¹ ÝÑ HpFqq ÝÑ GL2pqq

ÓQ Ó Óφ

Λ ÝÑ HpFqq{Z_q ÝÑ PGL₂pqq

Πq β

（これらの縦矢印はすべて商写像である．）グラフX^p,qはφψqτqにより定義され，Y^p,qはΠqQによ り定義される．X^p,qが連結かどうかはまだ分からないがどの群からなるかは知っていて，pが法qで平方 かどうかによりPGL2pqqかPSL2pqqからである．対称的にY^p,qは定義より連結だが，群Λ{Λpqqはよく わからない．しかし，βpT_p,qq S_p,qからY^p,qがX^p,qの一部となることがわかる．両方の構成は互いに 反していることからゆくゆくはX^p,qはq¡p⁸のとき連結であり，X^p,qとY^p,qは同型であることを示し ていく．

補題3.3.2.

Λpqq trαs PΛ :αa0 a1i a2j a3k, q|a1, a2, a3u. 証明.

rαs PΛpqq ôτ_qpαq PZ_q

ôqはa₀を割り切らず，q|a₁, a₂, a₃ ôq|a₁, a₂, a₃.

2行目から3行目の同値はNpαqはpのべき乗でpqであることからわかる．

補題 3.3.3. qを奇素数とする．a, bをqで割り切れず，a²b² pmodq²qとなる整数とする．このとき，

a b pmodq²qとなる．

証明. a²b² pmodq²qよりa²b²0 pmodq²q，すなわちpa bqpabq 0 pmodq²qとなる．このと きa b0 pmodqqまたはab0 pmodqqが成り立つ．a b0 pmodqqのときab0 pmodqq も成り立つとするとab0 pmodqqとなり仮定に矛盾する．よってab0 pmodqqからa b0 pmodq²qがわかる．ab0 pmodqqのときも同様である．よってa b pmodq²qとなる．

Y^p,qのgirthの下限を与える．

命題3.3.4. gpY^p,qq ©2 log_pqとなる．

p q

1のときはgpY^p,qq ©4 log_pqlog_p4となる．

証明. 簡単のため gpY^p,qq gとする．x₀, x₁, , x_g1, x_g x₀ をY^p,q での長さ g の閉路の頂点と する．Y^p,q の頂点推移よりΛ{Λpqqでx0 xg 1としてよい．Y^p,q はケーリーグラフであるから，

t₁, t₂, , t_gPT_p,qがあり

xi t1t2 ti p1¨i¨gq

とできる．t_i Πqprγisqはγi P Sppi 1, , gqにより一意的に表される．α γ1γ2 γg P Λ¹を αa₀ a₁i a₂j a₃kとする．αはS_p 上の既約語であるので命題3.3.1(b)よりrαs rγ₁srγ₂s rγ_gs はΛでr1sと異なる．すなわち，αはΛ¹で1と同値でなく，a₁, a2, a3の中の少なくとも1つが0でない ことを意味する．一方，

Πqprαsq t1t2 tgxg1

よりrαs PΛpqqである．補題3.3.2より素数qはa1, a2, a3 を割り切る．これらの中の少なくとも1つは0 でないから

p^gNpαq a²₀ a²₁ a²₂ a²₃©q² となる．pを底にして対数をとるとgpY^p,qq ©2 log_pqとなる．

p q

1とする．p^ga²₀ pmodq²qより

1 p^g

q

p

q g

p1q^g, となる．すなわち，gは偶数となり，g2hといえ，

p^2ha²₀ pmodq²q と表され，補題3.3.3から

p^h a₀ pmodq²q (1)

となる．一方，a²₀¨p^g，すなわち|a0|¨p^hである．背理法で示していく．g 4 log_pqlog_p4log_pq⁴ 4 とするとp^h   q²

2 となる．このとき，|p^h a0 | q²となり，(1)よりp^h a0となる．p^g a²₀から a₁a₂a₃0となり矛盾する．よってgpY^p,qq ©4 log_pqlog_p4となる．

注意3.3.5. 命題1.3.6からp©3のとき

gpY^p,qq ¨2 2 log_p|Y^p,q| であり，命題3.3.4から

|Y^p,q |© q p となる．また，

p q

1のときは

|Y^p,q|© q² 2p

となる．これは|Y^p,q||Λ{Λpqq |が少なくともqの1次式となることを示している．

定理3.3.6. p©3とする．q¡p⁸に対し，グラフX^p,qは連結である．したがってX^p,qとY^p,qは同型で ある．

証明. 命題3.1.2(c)よりSp,qは p

q

1のときPSL2pqqを生成し，

p q

1のときPGL2pqqを生成 することを示したい．同型写像β:HpFqq{Z_q ÑPGL₂pqqがあり，βpT_p,qq S_p,qとなった．これから

βpΛ{Λpqqq

$' '&

''

%

PSL₂pqq

p q

1のとき

PGL2pqq p

q

1のとき

を示せばよい．2番目の場合，S_p,q € PGL2pqq, Sp,q ∩PSL2pqq ∅ であることはすでに述べている．

H_p,q PSL₂pqq∩βpΛ{Λpqqqとする．どちらの場合も H_p,q PSL₂pqq

をいえばよい．そのために| H_p,q |¡ 60かつH_p,q がメタアーベルでないことを示す．このとき，もし Hp,q ˆSL2pqqならこれは定理2.6.5に反する．よってHp,q PSL2pqqがいえる．

|H_p,q |¡60であることはq¡p⁸かつp©3から，注意3.3.5より

|Λ{Λpqq |© q p ¡p⁸

p p⁷©3⁷¡120, すなわち|βpΛ{Λpqqq |¡120より|Hp,q |¡60となる．

Hp,qがメタアーベルでないことは命題2.6.13より，あるg1, g2, g3, g4PHp,qに対し，

rrg1, g2s,rg3, g4ss 1 を示せばよい．それぞれの場合で考える．

（a）

p q

1のとき，S_p,qの元の中から次のようにg_iを選ぶ．g₁PS_p,qを任意とし，g₂R tg₁¹u, g₃g₁ とし，g₄R tg₁¹, g₂¹uとする．このように選ぶとrrg1, g2s,rg3, g4ssはSp,qの長さ16の既約語となる．

命題3.3.4よりY^p,qのgirthは

gpY^p,qq ©2 log_pq

¡2 log_pp⁸16

をみたし，S_p,qの長さ16の既約語はHp,qで1と等しくなれない．

（b）

p q

1のとき，h₁, h2, h3をSp,qから次のように選ぶ．h₁PSp,qを任意とし，h₂R th₁¹u, h₃R th₁¹, h₂¹uとする．このときg₁h₁h₃, g₂h₂h₃, g₃h₁h₂, g₄h₃h₂とすると，これらは Hp,qの元となる．このように選ぶとrg1, g2s h1h3h2h₁¹h₃¹h₂¹,rg3, g4s h1h2h3h₁¹h₂¹h₃¹より

rrg₁, g₂s,rg₃, g₄ssはS_p,qの長さ24の既約語となる．命題3.3.4よりY^p,qのgirthは gpY^p,qq ©4 log_pqlog_p4

¡4 log_pp⁸log_p4 32log_p4¡24 をみたし，S_p,qの長さ24の既約語はHp,qで1と等しくなれない．

よってHp,qはメタアーベルではなく，H_p,q PSL2pqqがいえた．S_p,q が生成元となるのでX^p,qは連結 で，グラフY^p,qはグラフX^p,qと等しくなることがわかった．

系 3.3.7. q¡p⁸とする. X^p,qはpp 1q-正則で連結グラフである．

paq p

q

1のとき，X^p,qは2彩色可能でなく，girthは

gpX^p,qq ©2

3log_p|X^p,q| となる．

pbq p

q

1のとき，X^p,qは2彩色可能で，girthは

gpX^p,qq © 4

3log_p|X^p,q| log_p4 となる．

証明. 連結性は定理3.3.6で示された．girthの評価は命題3.3.4と命題2.5.1からのq³¡|X^p,q |よりわか る．（

p q

1のときはgpX^p,qq ©2 log_pq¡2 log_p |X^p,q |¹³ 2

3log_p |X^p,q |で，

p q

1のときは gpX^p,qq ©4 log_pqlog_p4¡4 log_p|X^p,q |¹³ log_p4 4

3log_p|X^p,q| log_p4となる．） p

q

1とする．命題3.1.2(d)とX^p,q の連結性から，X^p,q が2彩色可能でないことは定理2.5.5の PSL2pqqが単純であることを使うとわかる．

p q

1のとき，X^p,q が2彩色可能であることは注意 3.2.3(c)でわかっている．

注意3.3.8. 族pXmqm©1を有限で連結なk-正則グラフで，mÑ 8のとき|Xm|Ñ 8をみたすとする．

C ¡0が存在し，gpXmq © pC op1qqlog_k1|Xm|のとき大きなgirthをもつという．命題1.3.6より C¨2となる．Erd¨osとSachsは構成的でない方法でC1をみたす族があることを示した．

p q

1 のとき，グラフX^p,qはpp 1q-正則で大きなgirthを持つ，すなわちC 4

3をみたす族となった．これは，

構成的な方法が構成的でない方法よりも良い結果となる，グラフ理論での数少ない例の1つである．

補題3.3.9. p1 pmod 4qとする．Λpqq trαs PΛ :αa₀ a₁i a₂j a₃k, 2q|a₁, a₂, a₃uとなる．

証明. p1 pmod 4qからSpの定義よりa1, a2, a3は偶数である．

命題3.3.10. p1 pmod 4qで p

q

1のとき，gpY^p,qq ©4 log_pqとなる．

証明. p1 pmod 4qで p

q

1とする．p^ga²₀ pmodq²qより

1 p^g

q

p

q g

p1q^g となる．すなわち，gは偶数となりg2hがいえ，

p^2ha²₀ pmodq²q と表され，補題3.3.3から

p^h a²₀ pmodq²q となり，a₀はS_pの定義より奇数なので

p^h a²₀ pmod 2q²q (2)

となる．一方a²₀¨p^gすなわち|a₀|¨p^hである．背理法で示していく．q 4 log_pqとするとp^h q²と なる．このとき|p^h a0| 2q²となり(2)よりp^h a0となる．p^ga²₀からa1a2a30となり 矛盾する．よってgpY^p,qq ©4 log_pqである．

ドキュメント内 ラマヌジャングラフの構成について (ページ 37-42)