ラマヌジャングラフの構成について

ラマヌジャングラフの構成について

教科教育専攻 数学教育専修 篠永小百合

平成

25

^年

2

^月

4

^日

目 次

1

序

2

1.1

グラフの隣接行列と固有値

. . . . 2

1.2

固有値の

gap

の不等式

. . . . 3

1.3 family of expanders

での固有値の近似的なふるまい

. . . . 4

1.4

近似的なふるまいの証明

. . . . 6

1.5

非隣接数と彩色数

. . . . 8

1.6

大きな

girth

と大きな彩色数

. . . . 9

2

整数論と

PSL ₂ p q q 14 2.1 2

つの平方数の和

. . . . 14

2.2

平方剰余の相互法則と

4

つの平方数の和

. . . . 16

2.3

四元数環

. . . . 17

2.4

整四元数環における整数論

. . . . 18

2.5 PGL 2 p q q

と

PSL 2 p q q . . . . 21

2.6

部分群の構造

. . . . 22

2.7

有限群の表現論

. . . . 24

3

グラフ

X ^p,q 32 3.1

ケーリーグラフ

. . . . 32

3.2 X ^p,q

の構成

. . . . 33

3.3 girth

と連結性

. . . . 36

3.4

固有値の評価

. . . . 41

4

グラフ

H z X ^p,q 50 4.1

商ケーリーグラフ

. . . . 50

4.2

グラフ

H z X ^p,q . . . . 51

4.3 H z X ^p,q

の固有値の評価

. . . . 53

4.4 H z X ^p,q

の

girth

と彩色数

. . . . 53

1

序

1.1

グラフの隣接行列と固有値

V

を頂点の集合，Eを辺の集合とし，グラフ

X p V, E q

を考える．特に断りのないときはグラフ

X

は 無向で，多くの場合有限グラフである．Xの頂点の集合を

V t v 1 , v 2 , u

とする．このときグラフ

X

の 隣接行列

A

は

A ij v i

と

v j

をつなげている辺の個数

とすると，A

p A ij q

である．X が単純であるとは隣接した頂点が多くとも

1

つの辺でつながっている，

すなわちすべての

v _i , v _j P V

に対し

A _ij P t 0, 1 u

となることをいう．Xが単純のときには

v _i , v _j P V

をつな いでいる辺を

t v i , v j u

と表す．隣接行列

A

によりグラフ

X

は完全に決定し，Xが無向のときは

A

は対称 行列である．グラフ

X

にループがないとは，すべての

v i P V

に対し，A

_ii 0

であることと必要十分であ る．2頂点

v i , v i 1 P V

が辺

e i P E

により隣接しているとき，列

v 1 e 1 v 2 e 2 v 3 v k

を

X

の経路という．特 に

X

が単純のときには

v 1 v 2 v k

とかく．グラフ

X

のすべての

2

頂点が経路によりつなぐことができた ら連結しているという．

定義

1.1.1. k © 2

を整数とする．すべての

v i P V

に対し，

¸

v

_jP

V

A ij k

が成り立つとき，Xは

k-正則と

いう．

X

にループがないとき，k-正則であることと，すべての頂点がちょうど

k

個の頂点と隣接していること は等しい．

X

を

n

頂点を持つ有限グラフとする．このとき隣接行列

A

は

n

行

n

列の対称行列であり，n個の実固 有値が存在する．重複も数に入れ，値が減少するように並べると，

µ 0 © µ 1 © © µ n 1

となる．Aの固有値の集合を

X

の固有値という．µ

₀

の重複度が

1

であることは，µ

₀ ¡ µ 1

であることと 必要十分である．

グラフ

X p V, E q

に対し，関数

f : V Ñ C

を考え，

l ² p V q t f : V Ñ C : ¸

v

P

V

| f p v q | ²   8u

を定義する．l

² p E q

も同様に定義する．

V

が有限のとき

| V | n

とすると，すべての関数

f : V Ñ C

は

l ² p V q

に含まれる．このような関数を

C ⁿ

上のベクトルと考える．これに隣接行列を作用させると，

Af

A ₁₁ A ₁₂ A _1n .. . .. . .. . A i1 A i2 A in

.. . .. . .. . A n1 A n2 A nn

f p v ₁ q f p v 2 q

.. . .. . f p v n q

A 11 f p v 1 q A 12 f p v 2 q A 1n f p v n q .. .

A i1 f p v 1 q A i2 f p v 2 q A in f p v n q .. .

A _n1 f p v ₁ q A _n2 f p v ₂ q A _nn f p v _n q

となる．したがって，

p Af qp v _i q

¸ n j 1

A _ij f p v _j q

となる．添字を頂点の組そのままにすると，Aは

p A _xy q x,y

P

V

によって表され，すべての

x P V

に対し，

p Af qp x q ¸

y

P

V

A _xy f p y q

となる．

命題

1.1.2. X

を有限で，n頂点を持つ

k-正則グラフとする．このとき次が成り立つ ;

p a q µ ₀ k．

p b q 1 ¨ i ¨ n 1

に対し，

| µ i |¨ k．

p c q µ ₀

の重複度が

1

であることと，X が連結であることは同値である.

定義

1.1.3.

グラフ

X p V, E q

はある頂点の分割

V V ∪ V

により

A xy 0

となるすべての

2

頂点

x, y

を

x P V p V

q

かつ

y P V

p V q

とすることができたならば，2彩色可能という．このグラフを

2

部グ ラフという．

言い換えると，どの

2

つの隣接する頂点も同じ色にならないように頂点を

2

色でぬることができたなら ば，グラフは

2

彩色可能である．

命題

1.1.4. X

を連結で

n

頂点を持つ

k-正則グラフとする．次は同値となる：

p i q X

は

2

彩色可能である

; p ii q X

の固有値は

0

で対称となる

; p iii q µ n 1 k.

すべての有限で連結な

k-正則グラフ X

は最大固有値

µ ₀ k

を持ち，2彩色可能ならば最小固有値は

µ n 1 k

となる．固有値

k， k

を

X

の自明な固有値という．差

k µ 1 µ 0 µ 1

を

X

の固有値の

gap

という．

1.2

固有値の

gap

の不等式

X p V, E q

をグラフとする．F

€ V

のとき，Fの境界

B F

を

F

と

V F

をつなぐ辺の集合とする．す なわち，

B F

は

F

と

V F

を連結している辺の集合である．

B F Bp V F q

である．

定義

1.2.1.

グラフ

X

の

expanding constant

を

h p X q inf

"

| B F |

min t| F | , | V F |u : F € V, 0  | F |  8

*

とする．Xが

n

頂点を持つ有限グラフのとき，h

p X q min

"

| B F |

| F | : F € V, 0  | F |¨ n 2

*

となる．

グラフ

X

を情報伝達ネットワークとすると，expanding constant

h p X q

は

X

の質を測定している．h

p X q

が大きいことは，情報伝達がよいことを意味している．

定義

1.2.2.

グラフ族

p X _m q m

©

1

が有限で連結していて

k-正則であり，m Ñ 8

のとき

| V _m |Ñ 8

をみ たすとする．このとき，

D

ε ¡ 0,

^@

m © 1 such that h p X m q © ε

をみたすならば，f amily of expandersという．

X m

が完全グラフ（すべての頂点が他のすべての頂点と隣接しているグラフ）ならば，確かに情報伝達 はよいがコストがかかることから，最小の辺によって最適な相互通信能力が与えられるグラフが最もよい．

定理

1.2.3. X p V, E q

を有限で連結していて，ループのない

k-正則グラフとする．µ ₁

を

X

の自明でな

い最大固有値とすると，

k µ ₁

2 ¨ h p X q ¨ a

2k p k µ ₁ q

が成り立つ．

定義

1.2.2

と定理

1.2.3

から次がわかる．

系

1.2.4. p X _m q m

©

1

を有限で連結していて，ループのない

k-正則グラフ族とし，m Ñ 8

のとき

| V _m |Ñ 8

をみたすとする．このとき，族

p X m q m

©

1

が

family of expanders

であることは，

D

ε ¡ 0,

^@

m © 1 such that k µ ₁ p X _m q © ε

をみたすことと，必要十分である．

系

1.2.4

から

k-正則なグラフ族が family of expanders

であることは固有値の

gap

に

0

から離れた下限が 存在することと必要十分であることがわかる．また，定理

1.2.3

から固有値の

gap

が大きいほど

expanding constant h p X q

が大きく，Xの質がよいことがわかる．

1.3 family of expanders

での固有値の近似的なふるまい

この節でのグラフはすべてループなしとする．次の定理より

k-正則グラフの固有値の gap

の大きさには 限りがあることがわかる．

定理

1.3.1. p X m q m

©

1

を有限で連結している

k-正則グラフ族とし，m Ñ 8

のとき

| V m |Ñ 8

をみた すとする．このとき，

lim inf

m

Ñ 8

µ 1 p X m q © 2 ? k 1

が成り立つ．

定理

1.3.1

より強い結果を

1.4

節で見ていく．

定義

1.3.2. X

を連結グラフとする．Xの

girth g p X q

を

X

の最小の閉路の長さとする．X が

tree

であ る，すなわち

X

に閉路がないとき，g

p X q 8

とする．

有限で連結している

k-正則グラフにおいて，µ p X q

を

X

の最小非自明固有値とする．

定理

1.3.3. p X _m q m

©

1

を有限で連結している

k-正則グラフ族とし，m Ñ 8

のとき

| V _m |Ñ 8

をみた すとする．このとき，

lim sup

m

Ñ 8

µ p X _m q ¨ 2 ?

k 1

が成り立つ．

定理

1.3.3

も同様に強い結果を

1.4

節で見ていく．定理

1.3.1

と定理

1.3.3

から主定義が導かれる．

定義

1.3.4. X

を有限で連結している

k-正則グラフとする．X

のすべての非自明固有値

µ

において，

| µ |¨ 2 ? k 1

が成り立つとき，Xをラマヌジャングラフという．

p X m q m

©

1

をループなしの

k-正則なラマヌジャングラフ族とし，m Ñ 8

のとき

| V m |Ñ 8

だとす る．このとき，X

_m

の固有値の

gap

は可能な限りの最大となり，family of expandersについて最適となる．

命題

1.3.5. X

を有限な

k-正則グラフとする．頂点 x 0

を固定し，自然数

r

を

r   g p X q

2

とする．Xに中 心

x 0

，半径

r

の円をかく．この円の中に頂点は

k pp k 1 q ^r 1 q

k 2 1

個ある．

証明. 中心

x ₀

，半径

r

の円をかくと，この円の内部にあるグラフの部分は

k-正則な tree

と同型である．よっ て，頂点の個数は

1 k k p k 1 q k p k 1 q ^r

¹ k pp k 1 q ^r 1 q

k 2 1

となる．

命題

1.3.6. k © 3

とする．

p X _m q m

©

1

を連結している

k-正則グラフ族とし，m Ñ 8

のとき

| V _m |Ñ 8

をみたすとする．このとき，

g p X _m q ¨ 2 2 log _k

₁ | V _m |

となる．

証明. 自然数

r _m

を

r _m   g p X _m q

2

とする．中心

x ₀

，半径

r _m

の円を考えると，命題

1.3.5

より

k pp k 1 q ^r

^m

1 q

k 2 1 ¨| V _m | , k pp k 1 q ^r

^m

1 q

k 1 ¨| V _m | , p k 1 q ^r

^m

¨| V m | ,

r m ¨ log _k

₁ | V m |

となる．

g p X _m q

2 1 ¨ r _m   g p X _m q

2

とできるので，

g p X _m q

2 1 ¨ log _k

₁ | V _m | ,

g p X _m q ¨ 2 2 log _k

₁ | V _m |

となる．

1.4

近似的なふるまいの証明

この節では定理

1.3.1

と定理

1.3.3

よりも強い結果を見ていく．

定理

1.3.1

の不等式は

k-正則グラフでの頂点 v

から

v

への長さが

m

になる経路の数は，k-正則な

tree

の

v

から

v

への経路の数以上であるということからきている．

X p V, E q

を

k-正則な単純グラフとする（ | V |

は無限でもよい）．x

_i P V p i 0, 1, , r q

に対し，x

_i

と

x _i

₁ p i 0, 1, , r 1 q

が隣接していて

x _{i 1} x _i

₁ p i 1, 2, , r 1 q

が成り立つとき，

e x 0 x 1 x r

を長さ

r

の後戻りのない経路という．eの始点は

x 0

は，終点は

x r

である．r

P N

に対し

A r

を

p A _r q xy

始点

x，終点 y

の後戻りなしの長さ

r

の経路の数

と定義する．このとき，A

₀ Id p A ⁰ q

と

A 1 A

が成り立つことは明らかである．

補題

1.4.1.

p a q A ² ₁ A ₂ k Id.

p b q r © 2

に対し，

A 1 A r A r A 1 A r 1 p k 1 q A r 1 .

補題

1.4.1

から

A r

の生成関数を計算することができる．すなわち，

A r

を係数の形式的べき級数にできる．

補題

1.4.2.

¸

8

r 0

A r t ^r 1 t ² 1 At p k 1 q t ²

が成り立つ．すなわち，

₈

¸

r 0

A r t ^r

p Id At p k 1 q t ² Id q p 1 t ² q Id

となる．

補題

1.4.2

の右辺の分子の

1 t ²

を消去するために多項式

T m

を

T _m ¸

0

¨

r

¨^m2

A _m

_2r p m P Nq

と定義する．T

_m

の生成関数は補題

1.4.3

で与えられる．

補題

1.4.3.

¸

8

m 0

T m t ^m 1

1 At p k 1 q t ² .

定義

1.4.4.

第

2

種のチェビシェフ多項式を

U _m p cos θ q sin p m 1 q θ

sin θ p m P Nq

と定義する．

U m

と

T m

の関係は命題

1.4.5

で与えられる．

命題

1.4.5. m P N

に対し，

T m p k 1 q

^m2

U m

A

2 ? k 1

が成り立つ．

X p V, E q

を有限で

n

頂点を持つ

k-正則グラフとする．X

の固有値を

µ 0 k © µ 1 © © µ n 1

で表す．x

P V

に対し，f

_l,x

を

X

の始点

x，終点 x

の後戻りなしの長さ

l

の経路の数とする．すなわち，

f l,x p A l q xx

である．T

_m

のトレースを

2

つの方法で考えることで，次の

trace formula

が成り立つことが わかる．

定理

1.4.6.

すべての

m P N

に対し，

¸

x

P

V

¸

0

¨

r

¨^m₂

f m 2r,x p k 1 q

^m2

n ¸ 1 j 0

U m

µ j

2 ? k 1

が成り立つ．

X

の自己同型群

Aut X

が頂点集合

V

上で推移的に動くとき，Xは頂点推移という．すなわち，すべて の頂点の組

x, y

に対し，ある

α P Aut X

が存在し，α

p x q y

が成り立つことをいう．頂点推移であると き，f

_l,x

は単に

f l

としてよい．

系

1.4.7. X

を頂点推移で有限で

n

頂点を持つ

k-正則グラフとする．このときすべての m P N

に対し，

n ¸

0

¨

r

¨^m₂

f m 2r p k 1 q

^m2

n ¸ 1 j 0

U m

µ j

2 ? k 1

が成り立つ．

定理

1.4.6

の右辺

p k 1 q

^m2

n ¸ 1 j 0

U m

µ j

2 ? k 1

からだけではこれが非負整数になるかはわからない．し かし，左辺が正となるということからこれが正になることがわかり，これより非自明な結果を得る．その ために，まずチェビシェフ多項式のテクニカルな結果を用意する．

命題

1.4.8. L © 2

と

ε ¡ 0

を実数とする．

r L, L s

上の任意の確率測度

ν

に対し，すべての

m P N

にお いて

» L L

U _m x

2 dν p x q © 0

となるならば

ν pr 2 ε, L sq © C

をみたす定数

C C p ε, L q ¡ 0

がある．（νは

C

以上の速度を

r 2 ε, L s

に与える．）

有限で連結な

k-正則グラフの固有値の話に戻り，定理 1.3.1

よりもよい定理を与える．定理

1.3.1

のよう に非自明でない最大の固有値

µ 1

が近似的に

2 ?

k 1

より大きいだけでなく，区間

rp 2 ε q ?

k 1, k s

にあ る正の固有値でもそうであることが次でわかる．

定理

1.4.9.

すべての

ε ¡ 0

に対し定数

C C p ε, k q ¡ 0

があり，すべての有限で連結な

n

頂点を持つ

k-

正則グラフ

X

の固有値は，区間

rp 2 ε q ?

k 1, k s

に少なくとも

C n

個存在する．

定理

1.4.9

に類似した定理

1.3.3

の改善を行っていく．Xをグラフとするとき，

| X |

をグラフの頂点数と する．

δ a

を

a P r L, L s

のディラック測度とする．これは

r L, L s

上の確率測度である．すなわち，

r L, L s

上の連続関数

f

に対し，

» L L

f p x q dδ a p x q f p a q

となる．

定理

1.4.10. p X m q m

©

1

を有限で連結な

k-正則グラフ族とし，m Ñ 8

のとき

g p X m q Ñ 8

をみたすとす る．ν

_m ν p X m q

を

ν m 1

| X m |

|

X ¸

m|

1 j 0

δ

µjpXmq

?k1

によって定義される

^?

_k ^k

₁ ,

?

^k k 1

上の測度とすると，

^?

_k ^k

₁ ,

?

^k k 1

上のすべての連続関数

f

について

lim

m

Ñ8

»

?^k k1

^?_k1^k

f p x q dν _m p x q

» 2 2

f p x q a

4 x ² dx 2π

となる．言い換えると，

^?

_k ^k

₁ ,

?

^k k 1

上の測度列

p ν m q m

©

1

は

dν p x q

? 4 x ²

2π dx

を与えることで

r 2, 2 s

上の測度

ν

に弱収束する．

系

1.4.11. p X m q m

©

1

を有限で連結な

k-正則なグラフ族とし，m Ñ 8

のとき

g p X m q Ñ 8

をみたすとす る．すべての

ε ¡ 0

に対し，定数

C C p ε q ¡ 0

が存在し，区間

r k, p 2 ε q ?

k 1 s

上の

X _m

の固有値 の数は少なくとも

C | X m |

である．

1.5

非隣接数と彩色数

X p V, E q

をループのない有限グラフとし，Xの隣接行列を

A

とする．

定義

1.5.1.

p a q

彩色数

χ p X q

をすべての

i 1, 2, , χ

に対し，すべての

x, y P V i

が

A xy 0

となるよう な分割

V V 1 ∪ V 2 ∪ ∪ V χ

の組の最小数とする.

p b q

非隣接数

i p X q

を すべての

x, y P F

に対し，A

_xy 0

となるような部分集合

F € V

の要 素の最大数とする．

補題

1.5.2. X

をループなしの

n

頂点を持つ有限グラフとする．このとき，n

¨ i p X q χ p X q

が成り立つ．

有限で連結している

k-正則グラフ X

の固有値

k µ 0 ¡ µ 1 © © µ n 1

と

i p X q

には次の関係がある．

命題

1.5.3. X

を有限で連結な

n

頂点を持つ

k-正則グラフとする．このとき， i p X q ¨ n

k max t| µ 1 | , | µ n 1 |u

が成り立つ．

補題

1.5.2，命題 1.5.3，命題 1.1.4，定義 1.3.4

から次がわかる．

系

1.5.4. X

を有限で連結な

n

頂点を持つループなしの

k-正則グラフとする．このとき

χ p X q © k

max t| µ ₁ | , | µ _n

₁ |u

が成り立つ．特に，X が

2

彩色可能でないラマヌジャングラフならば

χ p X q © k

2 ?

k 1

? k 2

となる．

1.6

大きな

girth

と大きな彩色数

一般に辺の数が増えると彩色数は増加し（少なくとも減少はしない），girthは減少する．大きな

girth

と大きな彩色数を同時に持つグラフの存在という問題には長い歴史がある．なぜなら大きな

girth

と大き な彩色数を同時に持つと通信効率の面でもコストの面でもよいからだ．次は

Erd¨ os

によって最初に示され たものである．

定理

1.6.1. k

と

c

を大きな数とする．g

p X q © k

と

χ p X q © c

をみたす単純なグラフ

X

が存在する．

証明.

n

を自然数とする．頂点数が

n，辺の数が m

のグラフの集合を考える．この集合を

X n,m

と表す．

0   ε   1

k

をみたす

ε

を固定し，m

r n ^{1 ε} s

と定める（

r s

はガウス記号）．

First Step.

まず，

X n,m

の元の個数を数える．頂点

n

個から辺は

n

2

本引くことができるので，m辺 を選ぶと

| X n,m | n

2

m

となる．

Second Step.

次に，

X n,m

の中で非隣接数が小さいものを考える．0

  η   ε

2

をみたす

η

を固定し，

p r n ¹

^η s

とする．Xの頂点集合から

p

個の元をもつ任意の部分集合をとる．その頂点で作った完全グラ フ

K p

の辺が

X

と

n

個（かなり大きい数）より多い辺と共有しているものを非隣接数が小さいとする．そ うでない悪いグラフとはある完全グラフ

K p

と共有している辺が少ししかないときであり，この悪いグラ フを考えていく．

p

個の元を固定して考える．K

_p

が

0 ¨ l ¨ n

をみたす

l

辺だけ共有している

X P X n,m

の数は

_p

2

l

_n

2

^p ₂ m l

となる．したがって

n

個以下の辺が

K p

と共有している

X P X n,m

の数を

N r p n, m q

とすると，

N r p n, m q

¸ n l 0

_p

2

l

_n

2

^p ₂ m l

となる．n

¨ N

2

かつ

0 ¨ l ¨ n

のとき，一般に

N

l

¨ N

n

となるので，大きな

n

と

0 ¨ l ¨ n

に対し，

p 2

l

¨ p

2

n

,

n 2

^p ₂ m l

¨ n

2

^p ₂ m

がわかる．よって

N r p n, m q ¨ p n 1 q _p

2

n

_n

2

^p ₂ m

¨ p n 1 q

p p p 1 q 2

n _n

2

^p ₂ m

¨ p ²ⁿ 2 ⁿ p n 1 q

_n

2

^p ₂ m

¨ p ²ⁿ _n

2

^p ₂ m

p ²ⁿ m!

n 2

p

2 n 2

p

2

1

n

2

p

2

m 1

となる．0

¨ l ¨ m

のとき

n 2

p

2

l ¨ n

2

l 1

p 2

n 2

より，

N r p n, m q ¨ p ²ⁿ m!

n 2

n 2

1

n

2

m 1 1

p 2

n 2

m

p ²ⁿ n

2

m 1

p 2

n 2

m

¨ p ²ⁿ n

2

m 1

p 1 n 1

2 m

となる．0

  x   1

のとき

p 1 x q ^m   e

^mx

となるので，First Stepより

N r p n, m q ¨ p ²ⁿ e

^m p

n^p11

q

²

| X n,m |

となる．

Third Step. N p n, m q

をある

K _p

と

n

辺以下の辺を共有している

X P X n,m

の数とする．K

_p

は

n

p

通 りあるので

N p n, m q ¨ n

p

N r p n, m q

となる．

Fourth Step. p r n ¹

^η s

より

n

p

¨ n ^p ¨ p ⁿ

であるので，Second Stepと

Third Step

より

N p n, m q ¨ p ³ⁿ e

^m p

n1^p1

q

²

| X n,m |

となる．

Fifth Step. 0   η   ε

2 , m r n ^{1 ε} s , p r n ¹

^η s

であることを使うと，

N p n, m q

| X n,m | ¨ p ³ⁿ e

^m p

n1^p1

q

²

e ^{3n log p}

^m p

^p1n1

q

²

となる．さらに

m

p 1 n 1

2

© p n ^{1 ε} 1 q

n ¹

^η 2 n

2

n ³

^{2η ε} 4n ²

^{η ε} 4n ^{1 ε} n ²

^2η 4n ¹

^η 4 n ²

n ¹

^{2η ε} p n

が大きいとき

q

であり，0

  ε

¹

  2η ε

により

log p ε

¹とできるので

3n log p m p 1

n 1 2

3nε

¹

n ¹

^{2η ε} Ñ 8 p n Ñ 8q

となる．よって

N p n, m q

| X n,m | Ñ e

⁸

0 p n Ñ 8q

が成り立つ．n

Ñ 8

のとき

A p n q o p B p n qq

とは，n

Ñ 8

のとき

A p n q

B p n q Ñ 0

が成り立つことと同値であ るので，n

Ñ 8

のとき

N p n, m q o p| X n,m |q

となる．これは

X n,m

の中ですべての

K _p

と

n

辺より多く共有しているグラフ

X

の割合が

n Ñ 8

のとき

1

となることを表している．すなわち，非隣接数が小さい

X

が存在することを表している．

Sixth Step.

これから

girth

について考える．今まで考えてきた

K p

と

n

辺より多く共有している

X

が

大きな

girth

をもつとは限らないからである．

X n,m

上の整数値関数

F

を定義する．最初に固定した

k

に対

し，長さ

l ¨ k

の

X

の閉路の数を

F p X q

とする．A

p n, k q

を

F

の値の平均とすると

A p n, k q 1

| X n,m |

¸

X

PXn,m

F p X q

となる．

Seventh Step. A p n, k q

を別の方法で計算していく．3

¨ l ¨ k

のとき，lを固定して

C l : x 1 Ñ x 2 Ñ Ñ x l Ñ x 1

となる長さ

l

の閉路を考える．C

_l

を含むグラフの個数は

n 2

l m l

個であり，

¸

X

PXn,m

F p X q

では

X P X n,m

の中でこの条件をみたすものは

1

個ずつ数えてある．n

p n 1 q p n l 1 q

は長さ

l

の閉 路の数である．したがって

A p n, k q 1

| X n,m |

¸ k l 3

n p n 1 q p n l 1 q _n

2

l m l

¨

¸ k l 3

n ^l n

2

l m l

_n

2

m

p First Step

より

q

¸ k l 3

n ^l m p m 1 q p m l 1 q

n 2

_n

2

1

ⁿ ₂

l 1

¨

¸ k l 3

n ^l m ^l

n 2

_n

2

1 ⁿ ₂

l 1

¸ k l 3

n ^l m ^l

n 2

l

1

_n

2

l n

2

_n

2

1 ⁿ ₂

l 1 1

となる．

p q

の項は

n Ñ 8

のとき

o p 1 q

となる．これより，m

r n ^{1 ε} s

と

ε   1 k

から

A p n, k q ¨ p 1 o p 1 qq

¸ k l 3

n ^l m ^l

n 2

l

p 1 o p 1 qq

¸ k l 3

2m n 1

l

¨ p 1 o p 1 qq k 2m

n 1 k

Ñ o p n q p n Ñ 8q

となる．

Eighth Step. n Ñ 8

のとき

1

| X n,m |

¸

X

PXn,m

:F

p

X

q©ⁿk

n

k ¨ 1

| X n,m |

¸

X

PXn,m

F p X q A p n, k q o p n q

が成り立つ．よって

n Ñ 8

のとき

| t X P X n,m : F p X q © ⁿ _k u |

| X n,m | o p 1 q

となる．

Coda. X P X n,m

に対し，次の

2

つの性質を考える：

(1) X

は

n

辺より多く，すべての

K p

と共有している；

(2) F p X q   n k .

Fifth Step

と

Eighth Step

より

n Ñ 8

のとき

X P X n,m

が

(1)，(2)

をみたす割合が

1

となる．そこで 十分大きな

n（k, ε, η

により決まる）に対し，(1)，(2)をみたす

X

を選ぶ．Xから長さが

l

以下の閉路を 作る辺すべてを消したものを

X

¹とする．明らかに

g p X

¹

q ¡ k

である．(2)より

X

から

X

¹にするのに消し た辺は

n

辺より少ないので，X¹は少なくとも

1

辺がすべての

K p

と共有しているので

i p X

¹

q ¨ p

が成り立 つ．補題

1.5.2

より

χ p X

¹

q © n

p

であり，

χ p X

¹

q © n n ¹

^η n ^η

となる．これは十分大きな

n

に対して

c

より大きくなる．よって

X

¹が必要な条件をみたすグラフであ る．

Erd¨ os

によって示された定理

1.6.1

は確率論的方法を使っている．この証明方法では大きな

girth

と大き な彩色数をもつグラフの存在は明らかとなるが，具体例を見つける手掛かりとはならない．p, qを異なる奇

素数としたとき，Lubotzkyと

Phillips

と

Sarnak

は

PGL 2 p q q

または

PSL 2 p q q

を頂点集合とし，S

_p,q

によ り辺を構成するグラフ

X ^p,q

がラマヌジャンであり，ルジャンドル記号

p q

1

のときは大きな

girth

と 大きな彩色数をもつことを示した．このことは

3

節にある．なお，この論文の

1

節から

3

節は参考文献

[2]

を基本的にまとめたものである．

この論文では部分群

H € PGL 2 p q q

による，

PGL 2 p q q

または

PSL 2 p q q

の剰余類を頂点集合とし，S

_p,q

によ り辺を構成するグラフ

H z X ^p,q

もラマヌジャンであることを示す．このグラフ

H z X ^p,q

はどの

h P H, s P S p,q

も共役でなく，mを任意の

h P H

に対し，h

^m 1

となる最小の自然数としたとき，X

^p,q

の

girth

が

2m

より大きいときにループがなく単純である．ループがなく単純のときには，H

z X ^p,q

は

X ^p,q

に比べ，頂点 数は少なくなるが

girth

はそれほど小さくはならないことがわかる．すなわち，H

z X ^p,q

は大きな

girth

を もつことがわかる．また，H

z X ^p,q

の彩色数は，X

^p,q

が

2

彩色可能でないときは同様の下限をもつことが わかる．特に，ルジャンドル記号

p q

1

のときは，X

^p,q

は

2

彩色可能となってしまったが，H

z X ^p,q

は部分群

H

をうまくとることで

2

彩色可能でなくなり，この場合も他の場合と同様の下限をもつことがわ かる．すなわち，大きな彩色数をもつことがわかる．これによりラマヌジャンで，ループがなく単純な大

きな

girth

と大きな彩色数をもつグラフの具体的な例を増やすことができる．

2

整数論と

PSL 2 p q q

2.1 2

つの平方数の和

この節ではガウスの整数環

Zr i s

と整四元数環

HpZq

の様々な性質を見ていく．特に，2.4節の

S _p

は

X ^p,q

や

H z X ^p,q

の構成に必須のものである．また，2.5節からは

X ^p,q

の頂点集合になる

PGL 2 p q q

や

PSL 2 p q q

について見ていく．

k © 2，n P Z

に対し，r

_k p n q

を

n

を

k

個の平方数の和で表す方法の個数とする．すなわちディオファン トス方程式

x ² ₀ x ² ₁ x ² _k

₁ n

の解の個数である：

r k p n q

#

p x 0 , , x k 1 q P Z ^k :

k ¸ 1 i 0

x ² _i n + .

i

を虚数単位とする，すなわち

i ² 1

をみたすとする．ガウスの整数環

Zr i s

を

Zr i s t a bi : a, b P Zu

と定義する．

Zr i s

が複素数体

C

の部分環であることはすぐわかる．ノルム

N p α q

を

N p α q αα | α | ² a ² b ²

とすると

N p α q

は有理整数であるから，有理整数が

2

つの平方数の和となることと，あるガウス整 数のノルムであることは同値である．ノルムは乗法について

N p αβ q N p α q N p β q p α, β P Zr i sq

となることから，2つの平方数の和の積が

2

つの平方数の和となることがわかる．α

P Zr i s t 0 u

とする．

α

¹ _α ¹ P Zr i s

のとき，αを単元という．1

N p α _α ¹ q N p α q N p _α ¹ q

かつ

N p α q , N p _α ¹ q P N ∪ t 0 u

より

α

が

Zr i s

の単元となることは

N p α q 1

であることと同値である．さらに

N p α q 1

は

α P t 1, 1, i, i u

と 同値である．

定義

2.1.1.

p a q 2

つのガウス整数

α, β

が同伴であるとは，ある単元

ε P Zr i s

があり

α εβ

が成り立つ ことである．

p b q

ガウス整数

π P Zr i s

が素元であるとは，πが

Zr i s

の単元でなく，すべての因数分解

π αβ P Zr i s

に対して

α

または

β

が

Zr i s

の単元であることである．

同伴である

2

つの元は

Zr i s

上で同値関係が成り立ち，逆元や素元の有無や整除性といった特性を保つ．

可換環では定義

2.1.1(b)

は普通既約の定義であり，素元の定義は命題

2.1.5

のものである．この

2

つが同値 であることを見ていく．

命題

2.1.2. α, β P Zr i s , β 0

とする．γ, δ

P Zr i s

があり，α

βγ δ

かつ

N p δ q   N p β q

とできる．

定義

2.1.3. α, β P Zr i s

を固定する．

p a q α

が

β

を割り切るとは，γ

P Zr i s

があり

β γα

となることである．

p b q δ P Zr i s

が

α

と

β

の最大公約数とは，δが

α

と

β

を割り切り，αと

β

を割り切るすべての

γ P Zr i s

が

δ

を割り切ることである．

p α, β q δ

とかく．

明らかに，最大公約数が存在するとき，同伴なものを無視すればただ

1

つである．

p α, β q 1, i

なら ば

α

と

β

を互いに素という．この場合は

p α, β q 1

とする．

命題

2.1.4. α, β P Zr i s t 0 u

に対し，最大公約数

p α, β q P Zr i s

が存在する．また，ベズーの等式が成り立 つ，すなわち

γ, δ P Zr i s

があり，

p α, β q αγ βδ

とできる．

命題

2.1.5. π P Zr i s

が素元であることは，πが積

αβ p α, β P Zr i sq

を割り切るとき，πが

α

または

β

を割 り切ることと同値である．

これから，

Zr i s

の因数分解の一意性が示される．

命題

2.1.6.

すべての

0

でない

Zr i s

の元は

Zr i s

の素元の積で単数倍を除いて一意的にかける．すなわ

ち

α P Zr i s t 0 u

とすると，素元

π 1 , , π k , σ 1 , , σ l P Zr i s

があり

α π 1 π k

とかけ，さらに

α π ₁ π _k σ ₁ σ _l

と

α

に素元による因数分解が

2

つあるならば，k

l

かつ

1 ¨ i ¨ k

に対して添 字を置換することで

π i

と

σ i

は同伴となる．

q

を素数のべき乗とする．

F q

を元を

q

個持つ有限体とする．q個の元を持つ有限体は

1

種類しかない．

F

q

は

F q

の

0

でない元の乗法群を意味する．

定理

2.1.7. p

を

N

上の奇素数とする．次は同値となる：

p i q p 1 p mod 4 q ;

p ii q 1

が

F q

で平方，すなわち

x ² 1 p mod p q

は

Z

に解をもつ

; p iii q p

は

2

つの平方数の和となる（r

₂ p p q ¡ 0

である）.

次は

Fermat

と

Euler

の有名な結果である．

系

2.1.8.

整数

n © 2

が

2

つの平方数の和でかける（r

₂ p n q ¡ 0）ことは，すべての p 3 p mod 4 q

となる 素数が

n

の素因数分解の中に偶数乗で現れることと同値である．

補題

2.1.9. n P Z , α P Zr i s

とする．

p m, α q 1

と

p m, N p α qq 1

は同値である．

命題

2.1.10.

ガウス整数

π P Zr i s

が素元であることは，次の

3

つのうちの

1

つが成り立つことと同値で

ある：

p i q N p π q 2（すなわち π t 1 i, 1 i u

）;

p ii q p

を

Z

の素元で

p 1 p mod 4 q

とする．N

p π q p

となる

; p iii q q

を

Z

の素元で

q 3 p mod 4 q

とする．πと

q

が同伴となる.

n P N

とし，次を定義する：

• d 1 p n q

を法

4

で

1

と合同になる

n

の約数の個数とする；

• d ₃ p n q

を法

4

で

3

と合同になる

n

の約数の個数とする；

• d p n q

を

n

の約数の個数とする．

定理

2.1.11. n P N , n ¡ 0

とする．r

₂ p n q 4 p d 1 p n q d 3 p n qq

が成り立つ．

ε ¡ 0

を固定する．n

P N

に対し，f

p n q O _ε p n ^ε q

であるとは，ある定数

C C p ε q ¡ 0

によりすべての

n P N

が

| f p n q |¨ Cn ^ε

となることである．これを使い，r

₂ p n q

と

r ₃ p n q

の増大度を求める．

系

2.1.12.

すべての

ε ¡ 0

に対し，r

₂ p n q O ε p n ^ε q

となる．

系

2.1.13.

すべての

ε ¡ 0

に対し，r

₃ p n q O _ε p n

¹²

^ε q

となる．