固有値の評価

命題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である．

注意 3.4.1. mが偶数またはp1 pmod 4qとする．法4で考えると前の定義からわかることは現れるす べての4つ組px0, x1, x2, x3qはx0が奇数でx1, x2, x3が偶数となる．2次形式を導入する：

Q¹px0, x1, x2, x3q x²₀ 4q²px²₁ x²₂ x²₃q.

mが偶数またはp1 pmod 4qのときs_Qpp^mqはちょうど2次形式Q¹によるp^mの表現と同じになる．

一般のpに戻る．

補題3.4.2. mPNに対し，s_Qpp^mq 2 ¸

0¨r¨^m2

fm2rとなる．

証明. 定理3.3.6よりX^p,qとY^p,qは同一視できる．x₀1, x₁, , x_l1, x_l1を後戻りなしの始点，終点が 1の長さlのY^p,qの経路とする．命題3.3.4の証明より，t1, , tlPTp,qがあり，xit1t2 tip1¨i¨lq とできる．αPS_ppi1, , lqによりt_iΠ_qprα_isqと一意的にかける．rα₁srα₂s rα_lsは後戻りなしの 経路であるから，Λ上の長さlの既約語となり，Π_qprα1srα2s rαlsq xl1となるからrα1srα2s rαls はΛpqqに属する．これからflはΛpqqに属する長さl のΛでの既約語の数となる．

px₀, x₁, x₂, x₃q PZ⁴がs_Qpp^mqの条件をみたすとする．αx₀ qpx₁i x₂j x₃kqとすると，この四 元数αはΛ¹に属し，補題3.3.2より同値類はΛpqqに入る．これから次となる；

s_Qpp^mq | tαa₀ a₁i a₂j a₃kPΛ¹ : Npαq p^m, q|a₁, a₂, a₃u |. (3) αが（3）の右辺の条件をみたすとする．系2.4.14よりαは一意分解α p^lωm2lをもつ，ただし ωm2lはSpの長さm2lの既約語である．類rαsはΛ上で長さm2lの既約語となりΛpqqに属する．

反対にΛpqqに属する長さm2lの既約語ωからα p^lωのように2つの四元数を生成できる．これは

| tαPΛ¹ : Npαq p^m,rαs PΛpqqu |2 ¸

0¨r¨^m₂

fm2r

を意味し，すなわち

s_Qpp^mq 2 ¸

0¨r¨^m2

f_m2r

となる．

X^p,qのtrace formulaはすべてのmPNに対し，

s_Qpp^mq 2 np^m2

n¸1 j0

Um

µj

2?p

となる．ここでCの部分集合Θ_pを導入する：

Θp rilog?

p,0s∪r0, πs∪rπ, π ilog? ps. 複素数zPCのコサインとサインは

cosz1z² 2!

z⁴ 4! z⁶

6! ¸⁸

n0

p1qⁿ z²ⁿ

p2nq! e^iz e^iz 2 sinzzz³

3!

z⁵ 5! z⁷

7! ¸⁸

n0

p1qⁿ z^{2n 1}

p2n 1q! e^ize^iz 2i

と定義された．変数変換zÑ2?pcoszの写像はΘpからrpp 1q, p 1sへの全単射となる．特に，この変数 変換はr0, πsをr2?

p,2?

psに移すのでr0, πsをラマヌジャン区間とみることができる．j0,1, , n1 に対しθjPΘpをΘpの一意的な元でµj2?pcosθj となるものとする．特にθ0ilog?pで，

p q

1 のとき：

θn1π ilog?

p p系3.3.7よりq. チェビシェフ多項式Umの定義より

s_Qpp^mq 2 n p^m2

n¸1 j0

sinpm 1qθ_j sinθj

となる．

X^p,qがラマヌジャンであることを示すためにはθ0ilog?pと，

p q

1のときはθn1π ilog?p を除いたら，すべてのθjが実数であることを示す必要がある．これは最初に注意3.4.7の方法で示された．

初等的な方法では今のところできないが，その代わり十分大きなqに対しθ_jの虚数部分がpだけに依存し て決まることで十分だということを示す．これによりX^p,qがfamily of expandersであることがわかる．

trace formulaからθ_jの重複度は固有値の重複度に一致することがわかる．

命題3.4.3. µをX^p,qの非自明な固有値，すなわち|µ|p 1とし，その重複度をMpµq とする，この ときMpµq © q1

2 となる．

証明. V_µをµに対応する固有空間とする．命題3.1.3からベクトル空間V_µはX^p,qを構成している群の表 現空間である．この群は常にPSL2pqqを含んでいることからVµはPSL2pqqの表現空間である．定理2.7.31 からPSL2pqqの表現の次数は少なくともq1

2 である．|µ|p 1のときVµ上のPSL2pqqの表現が非自 明であることを示せばよい．背理法で示す．V _µ上のPSL2pqqの表現が自明とする．2つの場合にわける．

p q

1のとき，表現が自明ならばfpg¹xq λ_PSL2pqqpgqfpxq fpxqよりfpxqは定数である．

µfpxq Afpxq ¸

sPSp,q

fpxsq pp 1qfpxqからµp 1となる．

p q

1のとき，0でない関数f PV_µはPGL₂pqqのPSL₂pqqによる2つの剰余類となり，それぞれ 定数となる，すなわち

fpxq

$&

%

a pxPPSL2pqqのときq

a pxPPGL₂pqq, xRPSL₂pqqのときq とできる．fはX^p,qの隣接行列の固有関数であるので

µfpxq Afpxq ¸

sPS_p,q

fpxsq

$&

%

pp 1qa pxPPSL2pqqのときq

pp 1qa pxPPGL2pqq, xRPSL2pqqのときq から

$&

%

µa pp 1qa µa pp 1qa

となる．fは0ではないのでµ² pp 1q²，すなわち|µ|p 1となり，2つの場合とも矛盾となる．

以上からMpµq © q1

2 となる．

定理3.4.4. 実数εを0 ε 1

6 に固定する．十分大きなqに対し，X^p,qのすべての非自明な固有値µは

|µ|¨p^{56 ε} p^16ε をみたす．特にX^p,qはfamily of expandersである．

証明. X^p,qのtrace formulaから始める：すべてのmPNに対し，

s_Qpp^mq 2 n p^m2

n¸1 j0

sinpm 1qθj

sinθj

となった．ここでµj2?pcosθjとする．µ_jがラマヌジャンの範囲r2?p,2?psにないとき

$&

%

θjiψj p2?p µj ¨p 1のときq θjπ iψj ppp 1q ¨µj  2?pのときq となり，どちらも0 ψ_j¨log?pである．

今後，mを偶数とする．複素数zのハイパボリックサインとハイパボリックコサインを sinhz e^ze^z

2 isinpizq, coshz e^z e^z

2 cospizq

と定義する．µ_j R r2?p,2?psのとき，どちらの場合もmは偶数だから sinpm 1qθ_j

sinθj

sinipm 1qψ_j siniψj

sinhpm 1qψ_j sinhψj

©0 となる．このとき自明な固有値µ_kR r2?p,2?psを固定すると

s_Qpp^mq 2

np^m2Mpµkqsinhpm 1qψk

sinhψk

2

np^m2 ¸

j:µjµ_k

sinhpm 1qθj

sinhθj

© 2

np^m2Mpµ_kqsinhpm 1qψ_k sinhψk

2

np^m2 ¸

j:|µj|¨2?p

sinhpm 1qθ_j sinhθj

となる．実数θに対し，

sinpm 1qθ sinθ

sinpmθqcosθ cospmθqsinθ sinθ

¨

sinpmθqcosθ sinθ

|cospmθq |

¨

sinpmθqcosθ sinθ

1

¨m 1 となるので

s_Qpp^mq © 2

np^m2Mpµkqsinhpm 1qψ_k

sinhψk 2p^m2pm 1q (4)

となる．注意3.4.1よりs_Qpp^mqを評価する．mが偶数よりs_Qpp^mqは x²₀ 4q²px²₁ x²₂ x²₃q p^m

の整数解の個数である．まずx₀の選び方の個数を評価する．|x₀|¨p^m2 であり，x²₀p^m pmodq²qより 補題3.3.3を使うと

x0 p^m2 pmodq²q となる．x₀とpは共に奇数だから

x0 p^m2 pmod 2q²q となる．これよりx0の選び方は多くて

p^m2 q² 1

通りとなる．いったんx0を固定し，

x²₁ x²₂ x²₃ p^mx²₀ 4q² を整数解で解く．2.1節の記号を使うとr₃

p^mx²₀ 4q²

通りである．系2.1.13より，すべてのε¡0に対し

r3

p^mx²₀ 4q²

Oε

p^m q²

¹₂ ε

となる．このとき

s_Qpp^mq Oε

p^{m2 εm} q^{1 2ε}

p^m2 q² 1

O_ε

p^{mp1 εq} q^{3 2ε}

p^{m2p1 2εq} q^{1 2ε}

Oε

p^{mp1 εq} q³

p^{m2p1 2εq} q

となる．

したがって，ある定数Cε¡0により（4）は Mpµkq

n p^m2 sinhpm 1qψk

sinhψ_k ¨Cε

p^{mp1 εq} q³

p^{m2p1 2εq} q

p^m2pm 1q となる．p^m2 を消して，n¨q³を使うと，

Mpµkqsinhpm 1qψk

sinhψ_k ¨Cε

p^{mp12 εq} q²p^mε

q³pm 1q となる．mをp^m2 ¨q³となるように選んだとする．このとき

Mpµkqsinhpm 1qψk

sinhψk ¨Cε

q^{3 6ε} q^{2 6ε}

q³p1 6 log_pqq となる．sinhψk ¨sinh log?pから

Mpµ_kqsinhpm 1qψ_k O_ε q^{3 6ε}

となる．mをp^m2 ¨q³をみたす1番大きな偶数とする．十分大きなqに対し，

sinhpm 1qψ_k © e^{pm 1qψk}

3 ©e^{p1 6 logpqqψk} 3 ©p¹²

3 e^{6 logpqψk}

となる．最後の不等式はψk ¨log?pを使っている．このとき Mpµ_kq O_ε

q^{3 6εlog6ψkp} となる．µ_kは非自明な固有値なので命題3.4.3より

Mpµkq ©q1 2 となる．十分大きなqに対して

3 6ε 6ψ_k logp©1, すなわち

ψk ¨ 1

3 ε

logp となる．

このとき，θ_k iψ_kまたはθ_kπ iψ_kとµ_k2?pcosθ_kから，qが十分大きいとき

|µ_k | 2?

p|cospiψ_kq | 2?

pcoshψ_k

¨?

ppe^{p13 εqlogp} e^{p13 εqlogp}q p^{56 ε} p^16ε

となる．これからεP

0,1 6

を固定する．十分大きなqに対し，定理1.2.3より

hpX^p,qq ©p 1p^{56 ε}p^16ε 2

となる．よってX^p,qはfamily of expandersである．

系 3.4.5. 実数εを0 ε  1

6 に固定する．

p q

1のときµn1 pp 1qよりqが十分大きいとき，

系1.5.4より

χpX^p,qq © p 1 p^{56 ε} p^16ε となる．

次の系により，大きなgirthと大きな彩色数を持つ有限なグラフ族の構成がわかる．これは1.6節の確率 論的証明では解決できなかったことだ．

系 3.4.6. NPNを固定する．十分大きな素数qに対し，

gpX^p,qq ©N かつ χpX^p,qq ©N となる奇素数pが存在する．

証明. pを p 1

p¹¹¹² p¹²¹ ©N をみたすよう十分大きく選ぶ．このとき，qを次の4条件を同時にみたすよう に十分大きく選ぶ：

paqq©p⁸; pbq2 log_pq©N; pcq

p q

1;

pdqχpX^p,qq © p 1 p¹¹¹² p¹²¹ . これから命題3.3.4と定理3.3.6より

mintgpX^p,qq, χpX^p,qqu ©N をえる．

注意3.4.7. グラフX^p,qがラマヌジャンであることの証明の概略を記していく．

ラマヌジャン予想はモジュラー尖点形式の係数の増大度についての予想で，重さ2でのこの予想はEichler によって証明された．

2次形式のQ¹のθ-関数は

θpzq ¸

xPZ⁴

e^2πiQ1pxqz ¸⁸

k0

r_Q1pkqe^2πikz

により与えられる；ここでr_Q1pkqは整数kの形式Q¹による整数表現の個数である．このときθは重さ2 のモジュラー形式で；θをアイゼンシュタイン級数と尖点形式の和として分解すると，Eichlerの結果を偶 数mに対しr_Q1pp^mq s_Qpp^mqと得ることができる．特にすべてのε¡0に対し

s_Qpp^mq 4 qpq²1q

p^{m 1}1 p1 O_ε

p^{m2p1 εq}

となる．この結果と初等的な証明であった定理3.4.4に含まれている評価を比べることは興味深い．

X^p,qのtrace formulaは

s_Qpp^mq 2 n p^m2

n¸1 j0

sinpm 1qθj

sinθj

であった．主要な項 4 qpq²1q

p^{m 1}1

p1 は自明な固有値，すなわち

$' '&

''

%

θ₀ilog?p p

p q

1のときq θ0ilog?

p, θn1π ilog? p p

p q

1のときq により与えられる．まず，sinpm 1qθ0

sinθ0 p^m2 p^{m 1}1

p1 を示す．

sinpm 1qθ0

sinθ0 sinhpm 1qplog?pq sinhplog?pq

e^{pm 1qplog?pq}e^{pm 1qlog?p} e^plog?pqe^log?p p^{12pm 1q}p^{12pm 1q}

p¹² p¹² p^{m2 1}p^m2

p1 p^m2 p^{m 1}1

p1

となる．sinpm 1qθn1

sinθn1 p^m2 p^{m 1}1

p1 も同様である．

p q

1のときn qpq²1q

2 であるので，

s_Qpp^mq 4

qpq²1qp^m2 p^m2 p^{m 1}1 p1

2 n p^m2

n¸1 j1

sinpm 1qθ_j sinθj

4

qpq²1q

p^{m 1}1 p1

2 n p^m2

n¸1 j1

sinpm 1qθj

sinθ_j となる．

p q

1のときnqpq²1qであるので，

s_Qpp^mq 2

qpq²1qp^m2 2p^m2 p^{m 1}1 p1

2 n p^m2

n¸2 j1

sinpm 1qθ_j sinθj

4

qpq²1q

p^{m 1}1 p1

2 n p^m2

n¸2 j1

sinpm 1qθj

sinθ_j となる．これから

p q

1のときを考える．

p q

1のときも同様である．ラマヌジャン-アイヒラー の評価より

2 n

n¸1 j1

sinpm 1qθj

sinθj Oε p^εm2 となることがわかる．これより

2 n

n¸1 j1

sinpm 1qθj

sinθ_j

¨Cεp^εm2 (5)

となる．θ_jが実数でないものがあるとする．定理3.4.4のようにθj iψjまたはθjπ iψj p0 ψj¨ log?

pqとすると，mが偶数から 2 n

sinpm 1qθj

sinθ_j 2 n

sinhpm 1qψj

sinhψ_j ¡0 となる．また，

2 n

¸

i:θiが実数

sinpm 1qθ_i sinθi

¨2pm 1q である．これらから

2 n

n¸1 j1

sinpm 1qθj

sinθj

2

n

¸

i:θ_iが実数

sinpm 1qθi

sinθi

2 n

¸

j:θ_jが虚数

sinhpm 1qψj

sinhψj

© 2 n

¸

i:θiが実数

sinpm 1qθ_i sinθi

2

n

¸

j:θjが虚数

sinhpm 1qψ_j sinhψj

© 2pm 1q 2 n

¸

j:θjが虚数

2e^mψj

3 (6)

となる．(5),(6)より

Cεp^εm2 © 2pm 1q 2 n

¸

j:θ_jが虚数

2e^mψj 3 となる．ε

2  ψjとし，mを偶数で十分大きくとると，これは矛盾する．よってθj はすべて実数であり，

グラフX^p,qはラマヌジャンであることがわかる．

4 グラフ H z X

^p,q

4.1 商ケーリーグラフ

この節でいよいよHzX^p,qを定義する．まず，この節で商ケーリーグラフの基本的な性質を示し，4.2節 でHzX^p,qの性質を示す．ラマヌジャングラフであることを4.3節で示し，4.4節でgirthや彩色数につい て議論する．

定義4.1.1. GpG, Sqをケーリーグラフとする（Gは群，Sは空でないGの有限集合で対称であった）．G

を部分群Hで左から割った剰余類HzGを頂点集合とする．Hx, HyPHzG, sPSによりHyHxsと なるときHxとHyを結ぶ辺があるものとする．s¹PSによりHxHys¹となるときs¹ s¹ならばこ れは1つの辺とする．s₁, s2 PS, s1 s2によりHy Hxs1, Hy Hxs2となるとき，どちらもHxと Hyに辺を与えるが，これらは異なる辺とする．すなわち，多重辺となる．これらの頂点集合と辺集合に よるグラフをHzGpG, Sqとかき，商ケーリーグラフという．

商ケーリーグラフHzGpG, Sqは|S |kとすると明らかにk-正則グラフである．まず，HzGpG, Sqが 連結である条件を示す．

命題4.1.2. xSyをSの元が生成する群とする．商ケーリーグラフHzGpG, Sqが連結となることは，HxSy Gとなることと必要十分である．

証明.

pùñqHzGpG, Sqが連結とする．任意のxPGをとるとHxは辺をたどることでHとつながっている．す なわち，s₁, , siPSが存在し，HxHs1 siとなる．このときhPHがありxhs1 si となる．

よってHxSy Gとなる．

pðùqHxSy Gとすると，任意のxPGはhPH, s₁, , s_iPSが存在し，xhs₁ s_iとかける．こ れによりHxHs1 siとなるのでHxは辺をたどることでHとつながっている．よって任意のHxは Hとつながっているので連結である．

GpG, Sqは命題3.1.2(a),(b)のとき，ループをもたず，単純であった．しかし，HzGpG, SqはGpG, Sqが ループをもたず，単純であっても，ループがあったり，多重辺が存在したりする．HzGpG, Sqがループを もたない条件は次の補題である．

補題4.1.3. HzGpG, Sqがループをもたないことは，どのhPH, sPSも共役でない，すなわちxhx¹s となるxPGがないことと必要十分である．

証明. 明らか．

次の命題がHzGpG, Sqが単純である条件である．

命題 4.1.4. mを任意のhPHに対し，h^m1となる最小の自然数とする．GpG, Sqのgirthが2mより 大きいとき，HzGpG, Sqは単純である．

証明. 背理法で示す．単純でない，すなわち多重辺があるとすると，あるHxPHzGに対しs1, s2PS, s1 s2が存在しHxs1Hxs2となる．このときhPHがあり

xs1hxs2

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