2018-02-12

5次方程式の解を巡る旅〜3次・4次方程式のresolvent編〜

Galois理論

前回の記事で $\mathbb{Q}$ 上の5次既約多項式のGalois群について調べた。本稿では実際に方程式を解くために必要となるresolventについて説明する。

本当に知りたいのは5次方程式についてだが、前準備としてより低次元の方程式が解ける仕組みを理解しておくことは有用なので、本稿では話のスコープを3次・4次方程式に絞ることにする。

Resolventを用いた方程式の解法

次元の高い方程式を扱うための方法の1つとして、問題をより次元の低い方程式に帰着させることが挙げられる。例えば、nを3以上の自然数として、あるn次方程式を解きたいとする。もし自然数m $(m < n)$ に対してm次方程式の解から元の方程式の解が導き出せるのであれば、解くべき問題をずっと簡単にすることができる。

Resolventは3次・4次方程式に対して、そのような次元削減の方法を与えてくれる。

3次方程式の場合

Resolvent invariant

$\mathbb{Q}$ 上の3次多項式 $f(x) = x^3 + a_2 x^2 + a_1 x + a_0$ に対して、方程式 $f(x)=0$ を解くことを考える。議論の流れに大きな影響はないので、f(x)はmonicとしている。

f(x)の根を $x_1,\ x_2,\ x_3$ としたとき、一部の根の置換に対して不変となるような $x_1,\ x_2,\ x_3$ の多項式を考える。「一部の根の置換」として3次交代群 $A_3$ を考えた場合、その作用に対して不変となる多項式を得るためには以下の式を利用する。

$\displaystyle{ U = x_1 + \omega x_2 + \omega^2 x_3 }$

ここで、 $\omega$ は1の原始3乗根である。すると、 $U^3$ は $A_3$ の作用に対して不変となる。

このように、対称群の部分群に対して不変となるような式のことをresolvent invariantと呼ぶ[1]。しかし、実のところresolventという用語は使う人によって指すものが異なっている場合があり、resolvent invariantのことを単にresolventと呼ぶこともあるようである。

Resolvent equation

話を続けよう。さらに以下の式を考える。

$\displaystyle{ V = x_1 + \omega^2 x_2 + \omega x_3 }$

$U^3$ は $A_3$ の作用に対しては不変だが、奇置換を作用させると $V^3$ に変化する。実は $V^3$ も同様の性質を持っており、 $A_3$ の作用に対しては不変、奇置換の作用に対しては $U^3$ に変化する。

ここで、 $U^3,\ V^3$ を解に持つ方程式を考えてみる。

$\displaystyle{ (t - U^3)(t - V^3) = 0 }$

左辺をg(x)とおく。ここまでの議論により、g(x)の係数に $S_3$ の元を作用させると、以下のどちらかになる。

$\displaystyle{ \begin{eqnarray} (t - U^3)(t - V^3) \\ (t - V^3)(t - U^3) \end{eqnarray} }$

結果はどちらも同じになっている。つまり、g(x)は $S_3$ の作用に対して不変になる。そのため、g(x)の係数は $x_1,\ x_2,\ x_3$ の対称式となる。対称式は基本対称式で表すことができるわけだが、解と係数の関係よりf(x)の係数が $x_1,\ x_2,\ x_3$ の基本対称式になることを考えると、これはg(x)の係数をf(x)の係数で表せることを意味する。ただし、計算は面倒なので割愛する。

このようして得られたg(x)を解けば $U^3,\ V^3$ が分かる。あとはここから $x_1,\ x_2,\ x_3$ を求めたいわけだが、これは以下のようして得られる。

$\displaystyle{ \begin{eqnarray} x_1 &=& \frac{U + V - a_2}{3} \\ x_2 &=& \frac{\omega^2 U + \omega V - a_2}{3} \\ x_3 &=& \frac{\omega U + \omega^2 V - a_2}{3} \end{eqnarray} }$

ただし、 $a_2 = -(x_1 + x_2 + x_3)$ に注意されたい。

このように、3次方程式を解くにはまず $g(x)=0$ という2次方程式を解き、その解を元に $f(x)=0$ の解を求める。そして、元の方程式を解くために利用される方程式 $g(x)=0$ のことをresolventと呼ぶ[1]。これに関しても用語の揺れがあって、resolvent equation、または日本語だと分解方程式とか分解式などと呼ばれることもある。

Resolvent invariantの条件

このようなことが成立するのは、こうなるようにresolvent invariantをうまく選んでいるからである。すなわち、resolvent invariantは以下の条件を満たすように選ばれていたのである。

対称群の作用に対してn個未満のパターンにしか変化しない｡
そこから元の方程式の解を導き出せる。

3次方程式についてはこのような都合の良い式が存在したので、解くことができたのである。

4次方程式の場合

4次方程式も基本的には同じ流れで解ける。 $\mathbb{Q}$ 上の4次多項式 $f(x) = x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0$ に対して、方程式 $f(x)=0$ を解くことを考える。やはりf(x)はmonicとしておく。

f(x)の根を $x_1,\ x_2,\ x_3,\ x_4$ としたとき、resolvent invariantとして以下の式を考えてみる。

$\displaystyle{ \tau_1 = x_1 x_2 + x_3 x_4 }$

$\tau_1$ は二面体群 $D_4 = \langle (1\ 2),\ (1\ 3\ 2\ 4) \rangle$ の作用に対しては不変であるが、それ以外の置換を作用させると以下のどちらかの式に変化する。

$\displaystyle{ \begin{eqnarray} \tau_2 &=& x_1 x_3 + x_2 x_4 \\ \tau_3 &=& x_1 x_4 + x_2 x_3 \end{eqnarray} }$

ここで1つ困ったことがある。3次方程式の場合は $U^3,\ V^3$ がどちらも $A_3$ の作用に対して不変となっていた。しかし、ここで得られた $\tau_2,\ \tau_3$ は $D_4$ に対して不変ではない。この違いをどう捉えたら良いだろうか？

実は、 $\tau_2,\ \tau_3$ はそれぞれ $D_4$ と共役な部分群 $D_4' = \langle(1\ 3),\ (1\ 2\ 3\ 4) \rangle$ 、 $D_4'' = \langle(1\ 4),\ (1\ 3\ 4\ 2) \rangle$ の作用に対して不変なのである。3次方程式の場合は $A_3$ がたまたま $S_3$ の正規部分群だったため、共役な部分群が $A_3$ だけだったのである。

あとは $\tau_2,\ \tau_3$ にそれぞれ $D_4',\ D_4''$ 以外の置換を作用させたときにどうなるかだが、 $\tau_2$ は $\tau_1,\ \tau_3$ のどちらかに、 $\tau_3$ は $\tau_1,\ \tau_2$ のどちらかに変化し、それ以外の変化のパターンはない。結局、 $\tau_1,\ \tau_2,\ \tau_3$ は $S_4$ の作用に対して変化しないか、互いに遷移し合うかのどちらかになる。

このとき、以下の方程式がresolvent equationとなる。

$\displaystyle{ (t - \tau_1)(t - \tau_2)(t - \tau_3) = 0 }$

左辺をg(x)とおく。先ほどの議論により、g(x)の係数に $S_4$ の元を作用させると根が互いに入れ替わるだけで、g(x)自体は不変となる。そのため、g(x)の係数は $x_1,\ x_2,\ x_3,\ x_4$ の対称式となり、解と係数の関係によりg(x)の係数をf(x)の係数で表すことができる。

このようして得られたg(x)を解けば $\tau_1,\ \tau_2,\ \tau_3$ が分かる。最後に、これらを用いて $x_1,\ x_2,\ x_3,\ x_4$ を求める必要があるが、これは可能である。具体的な式は複雑なので割愛するが、気になる方は[2]などを参照されたい。

これで4次方程式も解くことが出来た。

おまけ：Lagrange resolventとは

本筋とはあまり関係ないが、最後にLagrange resolventの話をしておこうと思う。私は本件の調査を始めるまで、高次方程式を解くにはLagrange resolventというすごいやつを使えば良いのだと思っていたが、実はそうではない。ここで今の私の理解を整理しておく。

あるn次多項式f(x)の根を $x_1,\ x_2,\ \cdots ,\ x_n$ とすると、Lagrange resolventとは以下のような式のことを言う。

$\displaystyle{ \sum_{i=1}^{n} \zeta_n^{i-1} x_i }$

ただし、 $\zeta_n$ は1の原始n乗根である。

Lagrange resolventには面白い性質がある。すなわち、 $\zeta_n$ で割ると根に巡回置換 $(1\ 2\cdots n)$ を作用すさせるのと同じ効果が得られるのである。すると、 $\frac{1}{\zeta_n}$ の作用により以下の異なるn個の式が得られる。

$\displaystyle{ \begin{eqnarray} \sum_{i=1}^{n} \zeta_n^{i-1} x_i &=& x_1 + \zeta_n x_2 + \zeta_n^2 x_3 + \cdots + \zeta_n^{n-1} x_n \\ \frac{1}{\zeta_n} \sum_{i=1}^{n} \zeta_n^{i-1} x_i &=& x_2 + \zeta_n x_3 + \zeta_n^2 x_4 + \cdots + \zeta_n^{n-1} x_1 \\ \frac{1}{\zeta_n^2} \sum_{i=1}^{n} \zeta_n^{i-1} x_i &=& x_3 + \zeta_n x_4 + \zeta_n^2 x_5 + \cdots + \zeta_n^{n-1} x_2 \\ \vdots \\ \frac{1}{\zeta_n^{n-1}} \sum_{i=1}^{n} \zeta_n^{i-1} x_i &=& x_n + \zeta_n x_1 + \zeta_n^2 x_2 + \cdots + \zeta_n^{n-1} x_{n-1} \end{eqnarray} }$

ここで、これらを全てn乗した式を考えると、全て一致することが分かる。つまり、n次多項式のLagrange resolventは、n乗することで巡回置換 $(1\ 2\cdots n)$ に対して不変となるのである。

それ以外の置換に対する変化を考えると、結局Lagrange resolventのn乗は $(n-1)!$ 通りに変化することが分かる。

実は3次方程式を解く際に登場したU, VはLagrange resolventになっている。そのため、これらを3乗すると $(3-1)!=2$ 通りの式に変化したと言うわけである。

一方、4次方程式ではLagrange resolventを利用していない。それは、変化のパターンが $(4-1)!=6$ 通りとなってしまい、4次方程式を解くために6次方程式を解かなければならなくなるからである。

そんなわけで、Lagrange resolventは面白いが、方程式を解くのに使える万能薬ではないのである。

まとめ

以上、resolventとは何かということについて説明した。書き始めてみると毎度長くなってしまい、なかなか核心に迫れないでいるが、次回こそ5次方程式の可解性の議論に入りたいと思う。

参考

[1] Resolvent (Galois theory) - Wikipedia
[2]

代数学2　環と体とガロア理論

作者: 雪江　明彦
出版社/メーカー: 日本評論社
発売日: 2010/12/07
メディア: 単行本（ソフトカバー）
購入: 2人クリック: 14回
この商品を含むブログを見る

2018-01-25

5次方程式の解を巡る旅〜既約多項式のGalois群編〜

Galois理論

前回の記事で $\mathbb{Q}$ 上の多項式の既約性を確実に判定できることが分かった。本稿からいよいよ本題である可解な5次方程式の話に入っていく。特に、本稿では既約な5次多項式のGalois群がどういう性質を持つのかについて記載しようと思う。

最小分解体とGalois群

f(x)を $\mathbb{Q}$ 上の既約多項式とする。 $\mathbb{Q}$ 上既約なので、f(x)は $\mathbb{Q}$ 上ではこれ以上因数分解できない。しかし、体を適切に拡大すれば因数分解できるようになる。例えば、思い切って $\mathbb{C}$ まで拡大すれば因数分解可能となる。

しかし、多くの場合そこまで体を拡大せずとも、もっと小さい体で因数分解できるようになる。実際、因数分解ができるようになる最小の拡大体というものが存在し、これをf(x)の最小分解体という。以下、これをLと表すことにする。

Lを具体的に得るのは簡単で、単にf(x)の根を全て $\mathbb{Q}$ に添加すればよい。すなわち、f(x)の根を $\alpha_1, \alpha_2, \cdots , \alpha_n$ とすれば、 $L = \mathbb{Q}(\alpha_1, \alpha_2, \cdots , \alpha_n)$ となる。

$\mathbb{Q}$ からLへの拡大はGalois拡大である。これは自明ではなく証明が必要と思われるが、ここでは割愛する。Galois拡大とその中間体には、Galois群とその部分群が1対1で対応し、これをGalois対応と呼ぶ。Galois群とはLの $\mathbb{Q}$ 自己同型群のことであり、これはf(x)の根の置換と捉えることができる。そのため、Galois群は対称群やその部分群と同型になる[1]。

一般の5次多項式の場合では、最小分解体に対応するGaloisが5次対称群 $S_5$ となる。これが可解群ではないために、根を代数的に表示することができないのであった。

推移的なGalois群

既約多項式のGalois群は1つ特徴的な性質を持っている。それは、作用が推移的になるということである。推移的な作用の定義を[2]より引用する。

推移的な作用

群Gが集合Xに作用するとする.
(中略)
$x \in X$ があり, $Gx = X$ となるとき, この作用は推移的であるという.

作用が推移的な群のことを可移群とかtransitive groupなどと呼ぶようである。

先ほど述べたように5次方程式のGalois群は5次対称群、もしくはその部分群と同型になるわけだが、そのうち作用が推移的なものはどれくらいあるのだろうか？実は、これは共役を除いて以下の5つしか存在しないことが知られている[3][4]。

名称	記号	位数	共役な部分群の数
対称群	$S_5$	120	1
交代群	$A_5$	60	1
Frobenius群	$F_{20}$	20	6
二面体群	$D_{5}$	10	6
巡回群	$C_5$	5	6

上に示した5つの群の性質を見てみよう。まず、以下の2つの正規列を作ることができる。

$\displaystyle{ \begin{eqnarray} && 1 \lhd A_5 \lhd S_5 \\ && 1 \lhd C_{5} \lhd D_5 \lhd F_{20} \end{eqnarray} }$

$S_5,\ A_5$ が可解群でないことは有名であるが、実は $F_{20},\ D_{5},\ C_5$ は可解群となる。これより、5次の既約多項式f(x)について、 $f(x)=0$ という方程式が代数的に解けるための必要十分条件は、Galois群が $F_{20}$ に含まれることだと言える。これについては次回以降詳しく述べることにする。

Frobenius群とは

上で挙げた5つの群のうち、Frobenius群 $F_{20}$ だけ馴染みがないという方は多いのではないだろうか？何を隠そう私自身も本件の調査をするまで知らなかった。そこで、本格的な可解性の議論に入る前に、Frobenius群の性質について調べてみたいと思う。

定義

まず、定義を[5]より引用する。

Frobenius群

Let G be a finite group acting transitively on a set X. We call G a Frobenius group if only the identity element fixes more than one point. In other words, if x,y are distinct elements, and if gx=x and gy=y then g=1. We assume that X has more than one element.

要するに、単位元以外の元はその作用によって高々1つの点しか固定しないということである。

重要な部分群

高々1つの点を固定するということは、点を1つ固定する元と1つも固定しない元があることを意味する。作用によって1つも点を固定しない元と単位元を合わせたものはFrobenius群の正規部分群となっており、これをFrobenius kernelと呼ぶ。また、作用によってある点 $x_0 \in X$ を固定する元と単位元を合わせたものは部分群となっており、これをFrobenius complementと呼ぶ。

一般にFrobenius群Gには常にFrobenius kernel KとFrobenius complement Hが存在し、 $G = HK$ となる。上で述べた事実と合わせると、結局GはKとHの半直積になる。すなわち、 $G = K \rtimes H$ である。

G, K, Hの成す短完全列

GとKは以下のような短完全列を成す。

$\displaystyle{ \{1\} \to K \xrightarrow{\nu} G \xrightarrow{\pi} G/K \to \{1\} }$

ここで、 $\nu$ は入射、 $\pi$ は自然な全射を表す。

Frobenius群Gに対してKとG/Kは常に巡回群になることが知られている。このような性質を持つ群をメタ巡回群と呼ぶ[6]。すなわち、Frobenius群はメタ巡回群であると言える。

実はさらに $G/K \cong H$ となる。G/KからHへの同型を $\phi$ とすると、結局以下の短完全列が得られる。

$\displaystyle{ \{1\} \to K \xrightarrow{\nu} G \xrightarrow{\phi \circ \pi} H \to \{1\} }$

$F_{20}$ の全体像

Frobenius群の一般論はこれくらいにして、以下に $F_{20}$ の構造を示す。

f:id:peng225:20180121162728p:plain

$F_{20}$ は2つの置換 $\sigma = (1, 2, 3, 4, 5),\ \tau = (2, 3, 5, 4)$ によって生成されるので、全ての元を $\sigma,\ \tau$ の積として表現している。エッジは生成元を左から掛ける操作を表しているが、一部省略している。各ノード下段の括弧で囲われた数字は、(1, 2, 3, 4, 5)という数字の列に対してその元を左作用させた結果を表している。その作用によって固定される点を赤で示している。

また、Frobenius kernelの元はノードに色を付けてある。具体的には $K = \{1, \sigma, \sigma^2, \sigma^3, \sigma^4\}$ であり、これは正規部分群かつ巡回群になっている。なお、念のため明示的に述べておくが $K = C_5$ となっている。

$F_{20}$ のFrobenius complementを得るために、例えば1を固定する元の集合を考えてみる。これは $H = \{1, \tau, \tau^2, \tau^3 \}$ であり、確かに部分群かつ巡回群になっている。

まとめ

以上、既約多項式のGalois群の性質について述べ、続いてFrobenius群の紹介をした。後半はほとんど余談であったが、このようにある群の持つ性質をあれこれ調べてみるのは結構面白いし、Frobenius群を身近に感じるよい機会であったと思う。

次回はいよいよ可解な5次方程式の核心に迫っていこうと思う。

参考

[1]

代数学2　環と体とガロア理論

作者: 雪江　明彦
出版社/メーカー: 日本評論社
発売日: 2010/12/07
メディア: 単行本（ソフトカバー）
購入: 2人クリック: 14回
この商品を含むブログを見る

[2]

代数学1　群論入門 (代数学シリーズ)

作者: 雪江明彦
出版社/メーカー: 日本評論社
発売日: 2010/11/17
メディア: 単行本（ソフトカバー）
購入: 1人クリック: 21回
この商品を含むブログを見る

[3] http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0848-01.pdf
[4] http://www.isc.meiji.ac.jp/~kurano/soturon/ronbun/08kurano.pdf
[5] Frobenius Groups
[6] Metacyclic group - Wikipedia

2018-01-09

5次方程式の解を巡る旅〜多項式の既約性判定編〜

Galois理論

Galois理論活用の難しさ

一般の5次方程式に代数的な解の公式が存在しないというのは有名な事実である。これはGalois理論に深く関連する話題であるが、これ自体はGaloisによって証明されたものではない[1]。Galois理論の面白さは、代数方程式が解けるための条件を与えてくれる点にある。すなわち、Kを体とし、f(x)をK上の多項式とする。f(x)の最小分解体をLとすれば、 $f(x)=0$ という方程式が代数的に解けるための必要十分条件は $\mathrm{Gal}(L/K)$ が可解群になることである。この事がGalois理論により導かれるのである[2]。

Galois理論はこのように興味深く重要な理論なのであるが、具体的な多項式を目の前にしてその可解性を論じようとすると、たちどころに手が止まってしまう。すなわち、理論としてGalois群と方程式の可解性の間に深い関係があることは分かったものの、それを具体的な問題にどう活用したら良いのかが自明でないのである。

そこで、本稿では考察の対象を $\mathbb{Q}$ 上5次の代数方程式に絞ってこの問題にアプローチしてみることにする。対象をこのように絞る理由は、あまり風呂敷を広げすぎても収集がつかなくなるのと、有理数体は素体であり、最も基本的かつ重要な体の1つと考えられるためである。

恐らく話が長くなるので、記事を何回かに分けることにする。今時点で頭に思い描いている全体のストーリーはあるが、深く考えていく中で書きたいことが変わる可能性があるので、目次は敢えて書かない。

Galois理論と多項式の既約性

ある具体的な多項式 $f(x) \in \mathbb{Q}[x]$ の可解性について考えるとき、多くの文献では $\mathbb{Q}$ 上既約な多項式を扱うことが多いように思う。その理由は、可約多項式であれば因数分解された次元の低い多項式の可解性をそれぞれ考えればよいためだと思われる。

これは確かに一理あるのだが、ちょっと待って欲しい。実際にある具体的な多項式を目の前にして、それが既約であるかどうかというのは簡単に判定できるものなのだろうか？代数学を勉強したことがある人であれば、すぐに「Eisensteinの既約判定法を使えばよいのでは？」と思うことだろう。これは確かに一つの手である。しかし、Eisensteinの既約判定法に述べられている条件は、多項式が既約であるための十分条件であって必要十分条件ではないのである。つまり、本当は既約多項式なのに、Eisensteinの既約判定法ではそれが判定できないものが存在する。

これは困った。なぜなら、多項式の既約性とGalois群の構造の間には密接な関係があり、既約性が正確に判定できないとGalois群の決定が難しくなるからである。

既約性判定アルゴリズム

これについていろいろと調べてみたところ、 $\mathbb{Q}$ 上の多項式であれば既約性を判定するアルゴリズムが存在することが分かった。そもそもsageにis_irreducible関数が実装されているのだから、当然と言えば当然である[3]。

しかし、これがなかなかに難解なのである。その全容を説明することは今の私にはできないし、また紙面の都合もある。そのため、本稿ではアルゴリズムの概観を紹介し、多項式の既約性を決定的に判定する方法が存在するのだという点について、可能な限り納得感を得られるように努めてみる。

前処理

この後に述べる既約性判定アルゴリズムでは、入力として $\mathbb{Z}$ 上のmonicな多項式を与える必要がある。そのため、 $f(x) \in \mathbb{Q}[x]$ に対して適切な前処理を施しておく必要がある。これについて $f(x) = \frac{3}{4}x^2 + \frac{3}{2}x - \frac{6}{5}$ を例に説明する。

やることは3つある。1つ目は分母の最小公倍数を括り出すことである。先ほどの例の場合、 $f(x) = \frac{1}{20}(15x^2 + 30x - 24)$ となる。2つ目は分子の最大公約数を括り出すことである。先ほどの例の場合、 $f(x) = \frac{3}{20}(5x^2 + 10x - 8)$ となる。

ここまでの操作で $f(x) = C g(x)\ (C \in \mathbb{Q},\ g(x) \in \mathbb{Z}[x])$ という形式に変換できた。あとはg(x)をmonicな多項式に変換できれば良い。そのためには、 $g(x) = \sum_{i=0}^{n} a_i x^i\ (a_n \neq 0)$ に対して $h(x) = a_n^{n-1} g\left(\frac{x}{a_n}\right)$ とすれば良い。先ほどの例の場合、 $h(x) = 5\left(5\left(\frac{x}{5}\right)^2 + 10\frac{x}{5} - 8\right) = x^2 + 10x - 40$ となる。

このようにして得られたh(x)に対して後述のアルゴリズム適用すると、 $\mathbb{Z}$ 上既約かどうか判定できる。 $\mathbb{Z}$ 上既約であればGaussの補題により $\mathbb{Q}$ 上既約となる[4]。さらに、f(x)からh(x)を得た操作では既約性は不変であるため、h(x)が $\mathbb{Q}$ 上既約であればf(x)も $\mathbb{Q}$ 上既約となる。

アルゴリズムの流れ

$f(x) \in \mathbb{Z}[x]$ をmonicな多項式とする。f(x)の $\mathbb{Z}$ 上での既約性を判定するアルゴリズムの流れは以下のようになる[5][6][7]。

f(x)がsquare freeであるかどうかを調べる。もしsquare freeでなければf(x)は可約なので処理を終える。
pを素数とする。f(x)の各係数をmod pで写して得られる多項式が $F_p$ 上でもsquare freeになるようなpを見つける。
f(x)を $F_p$ 上で因数分解する。つまり、 $f(x) \equiv f_{1, 1}(x)f_{1, 2}(x) \cdots f_{1, m}(x) \pmod{p}$ を求める。もしf(x)が $F_p$ 上既約ならば $\mathbb{Q}$ 上既約なので処理を終える。
$f_i(x)\ (i=1, 2, \cdots , m)$ にHensel liftingを繰り返し適用し、 $2B_{lm} < p^a\ (a \in \mathbb{N})$ を満たすような $p^a$ を法とした時の分解を求める。すなわち、 $f(x) \equiv f_{a, 1}(x)f_{a, 2}(x) \cdots f_{a, m}(x) \pmod{p^a}$ を求める。ただし、 $B_{lm}$ はLandau-Mignotte boundと呼ばれる値で、 $B_{lm}=2^{\mathrm{deg}(f)}\|f\|_2$ である。 $\|f\|_2$ はf(x)の係数の2乗和の平方根を表す。
$f_{a, i}(x)\ (i=1, 2, \cdots , m)$ からいくつかを選んで掛け合わせる。そうして得られた関数の各係数を $\bmod p^a$ で写す。このとき、もし値が $p^a/2$ より大きければ $p^a$ を引く。これが $\mathbb{Z}[x]$ でf(x)を割り切ればf(x)は可約である。もし (全部選ぶというパターンは除いて) 全ての $f_{a, i}(x)$ の組み合わせについてf(x)を割り切ることがなければf(x)は既約である。

ただし、これは多項式を因数分解するためのアルゴリズムであるBerlekamp-Zassenhausアルゴリズムを、私が既約性判定用にアレンジしたものであるのでご注意願いたい。

以下でそれぞれのステップのポイントについて説明する。

Square free判定

f(x)がsquare freeであるとは、 $f(x) = \{f_1(x)\}^{a_1}\{f_2(x)\}^{a_2} \cdots \{f_l(x)\}^{a_l}$ と既約多項式の積に分解したときに、 $a_1 = a_2 = \cdots = a_l= 1$ となることである。 $\mathbb{Q}$ 上の多項式がsquare freeかどうかを判定するのは簡単である。すなわち、 $\mathrm{GCD}(f(x), f'(x))$ が定数であればsquare freeである。

1つだけ例を上げよう。 $f(x) = x^3 - x^2 - 5x - 3$ がsquare freeかどうかを判定してみる。GCDを求めるにはEuclidの互除法を使えば良い。 $f'(x) = 3x^2 - 2x - 5$ なので、f(x)をf'(x)で割ると以下のようになる。

$\displaystyle{ x^3 - x^2 - 5x - 3 = (3x^2 - 2x - 5)\left(\frac{1}{3}x - \frac{1}{9} \right) - \frac{32}{9}(x + 1) }$

さらに $3x^2 - 2x - 5$ を $x + 1$ で割ると以下のようになる。

$\displaystyle{ 3x^2 - 2x - 5 = (x + 1)(3x + 5) }$

$\mathbb{Q}$ 上の多項式における互除法では定数倍に意味はないので、 $x + 1$ による割り算を行ったことに注意されたい[8]。以上により、 $\mathrm{GCD}(f(x), f'(x)) = x + 1$ である。これは定数ではないため、f(x)はsquare freeではないことが分かった。実際、 $f(x) = (x+1)^2(x-3)$ である。

なお、GCDの計算にさらっとEuclidの互除法を使ったが、これが可能なのは任意の体上の多項式環がEuclid整域となるからだという点を申し添えておく[9]。

既約性判定アルゴリズムでは $F_p$ 上でもsquare free判定をする必要があるが、これはちょっと工夫が要るようである。詳しくは[10]を参照されたい。

pの見つけ方

一般にf(x)がsquare freeであっても、それがmod pの世界でもsquare freeとは限らない。例えば、 $f(x) = x^2 + 2x + 6$ はEisensteinの判定法により既約なので、square freeである。しかし、 $f(x) \equiv x^2 + 2x + 1 \equiv (x+1)^2 \pmod{5}$ となり、これはsquare freeではない。

既約性判定アルゴリズムでは、f(x)がmod pの世界でもsquare freeになっていなければならないので、そのようなpを何とかして見つける必要がある。実は、これはそんなに悩む必要は無くて、有限個のpを除けばmod pの世界でもsquare freeとなるようである。証明はいまいち理解出来ていないが、[6]の命題6.36にヒントがある。

$F_p$ での因数分解

これについては検索すると山のように論文なりブログなりが出てくる。特に[10]に分かりやすくまとまっているようなので、興味のある方はそちらを参照されたい。

$\mathbb{Q}$ 上の既約性と $F_p$ 上の既約性の関係

一般に $F_p$ 上既約であれば $\mathbb{Q}$ 上既約となるが、逆は成り立たない。証明は[11]などを参照されたい。

Hensel lifting

Hensel liftingとは、Henselの補題を用いて $\bmod p^k$ における多項式の根から $\bmod p^{k+1}$ における根を帰納的に導出していく手続きである[12]。と、Wikipediaには記載されているが、実は多項式の因数分解に関係する別バージョンが存在する[5][13][14]。Henselの補題 (別バージョン) の内容を[5]より引用する。

Henselの補題 (別バージョン)

Fを整係数一変数多項式、pは $p \nmid lc(F)$ となる素数とし、 $G_1$ と $H_1$ はpを法とする有限体上の互いに素な多項式とするとき、

$\displaystyle{ F(x) \equiv G_1(x)H_1(x) \pmod{p} }$

であるならば、任意の正整数kに対して、

$\displaystyle{ \begin{eqnarray} && F(x) \equiv G_k(x)H_k(x) \pmod{p^k} \\ && G_k \equiv G_1,\ H_k \equiv H_1 \pmod{p} \end{eqnarray} }$

を満たす $G_k$ と $H_k$ が存在する。

ここで、（定義が書かれていないので推測だが） $lc(F)$ というのは多項式Fのleading coefficientを意味するのだと思われる。Leading coefficientというのは、要するに最高次の係数のことである。これがpで割りきれてしまうとmod pで写したときに次元が落ちてしまうので、そのようなケースを除外しているのである。もっとも、今考えているケースでは多項式はmonicであり、常に $lc(F)=1$ となるのであまり気にする必要はない。

別バージョンを利用することで、Hensel liftingもそれに沿った形で行うことができる。具体的な $G_k, H_k$ の求め方は[5]の証明や[15]が参考になる。この別バージョンのHensel liftingを無限に適用することで、 $F_p$ における多項式の因数分解をp進整数環 $\mathbb{Z}_p$ にまで持ち上げる事ができる。

p進整数の近似

最終ステップでは本来 $\mathbb{Z}_p$ 上でのf(x)の分解が必要なのだが、実際のコンピュータで計算する際にはHensel liftingを無限に行うことはできないし、p進整数を誤差なく扱うことも困難である。すなわち、実際に扱うことができるのはp進整数の近似値だけである。

しかし、実はある程度の精度で近似値が得られれば、そこから多項式の因数分解を厳密に行える事が知られている。この精度はLandau-Mignotte boundと呼ばれる値により規定されるようである。

組み合わせ計算複雑性

最終ステップでは $f_{a, i}(x)\ (i=1, 2, \cdots , m)$ の組み合わせを全て計算して係数を調べる必要があるが、これは時間計算量が $O(2^m)$ の処理であり、一般には極めて重いアルゴリズムである。しかし、これを多項式時間で行うことができるアルゴリズムも存在するようである[7]。私には難しくてとても理解出来なかったが、興味のある方はぜひチャレンジしてみて欲しい。

既約性判定の例

せっかくなので1つ例を見てみよう。ここでは以下の多項式の $\mathbb{Z}$ 上での既約性を判定してみる。

$\displaystyle{ f(x) = x^5 + 2x^4 - 7x^3 + 18x^2 + 2x - 4 }$

以下でアルゴリズムのステップを順に実行してみよう。

Step 1

計算は省略するが、 $\mathrm{GCD}(f(x), f'(x))$ が定数であることが簡単に確かめられる。よってf(x)はsquare freeである

Step 2

$p=5$ とすると、 $f(x) \equiv x^5 + 2x^4 + 3x^3 + 3x^2 + 2x + 1 \pmod{5}$ となる。詳細は省くが、f(x)は $F_5$ 上でもsqure freeとなる。

Step 3

f(x)を $F_5$ 上で因数分解すると以下のようになる。

$\displaystyle{ f(x) \equiv (x+1)(x+2)(x+3)(x^2+x+1) \pmod{5} }$

Step 4

f(x)のLandau-Mignotte boundを計算すると以下のようになる。

$\displaystyle{ \begin{eqnarray} B_{lm} &=& 2^5 \cdot \sqrt{1^2 + 2^2 + (-7)^2 + 18^2 + 2^2 + (-4)^2} \\ &=& 32 \sqrt{398} \end{eqnarray} }$

よってHensel liftingを行うべき回数は以下のようになる。

$\displaystyle{ \begin{eqnarray} 2 B_{lm} &<& 5^a \\ 64 \sqrt{398} &<& 5^a \\ 4 &<& a \end{eqnarray} }$

よって $\bmod 5^5$ の世界までHensel liftingで持ち上げれば十分である。詳細は割愛するが、Hensel liftingの結果は以下のようになる。

$\displaystyle{ \begin{eqnarray} x+1 &\equiv& x+1361 \pmod{5} \\ x+2 &\equiv& x+1162 \pmod{5} \\ x+3 &\equiv& x+1768 \pmod{5} \\ x^2+x+1 &\equiv& x^2+1961x+2571 \pmod{5} \\ f(x) &\equiv& (x+1361)(x+1162)(x+1768)(x^2+1961x+2571) \pmod{5^5} \end{eqnarray} }$

余談だが、Hensel liftingの計算はPARI/GPのAndroidアプリ版であるPariDroidを用いて行った[16]。スマホでこんな高度な計算ができるとは便利な世の中になったものだ。

Step 5

例えば以下の組み合わせについて考える。

$\displaystyle{ (x+1361)(x+1768) \equiv x^2+4x+3123 \pmod{5^5} }$

$\frac{5^5}{2}<3123$ であるため、 $5^5 = 3125$ を引いて $x^2+4x - 2$ とする。実はこれはf(x)を割り切るため、f(x)は可約である。

確認のために残りの因子についても計算してみる。

$\displaystyle{ (x+1162)(x^2+1961x+2571) \equiv x^3+3123x^2+3x+2 \pmod{5^5} }$

$\frac{5^5}{2}<3123$ であるため、 $5^5 = 3125$ を引いて $x^3-2x^2+3x+2$ とする。これもf(x)を割り切る。

結局、f(x)は以下のように因数分解出来ることが分かった。

$\displaystyle{ f(x) = (x^2 + 4x - 2)(x^3 - 2x^2 + 3x + 2) }$

まとめ

以上、5次方程式の解の様子を調べるための準備として、 $\mathbb{Q}$ 上の多項式の既約性を決定的に判定する方法が存在することについて述べた。今回はあまり深入りしなかったが、この辺りの話は数学とコンピュータが交差する世界であり、調べてみると非常に面白い。数学もコンピュータも好きな方にはぜひオススメしたい。

次回以降、本来の目的である5次方程式の調査を進めていきたいと思う。

参考

[1] アーベル–ルフィニの定理 - Wikipedia
[2]

代数学2　環と体とガロア理論

作者: 雪江　明彦
出版社/メーカー: 日本評論社
発売日: 2010/12/07
メディア: 単行本（ソフトカバー）
購入: 2人クリック: 14回
この商品を含むブログを見る

[3] Univariate Polynomial Base Class — Sage Reference Manual v8.1: Polynomials
[4] Gauss's lemma (polynomial) - Wikipedia
[5] http://www.e.ics.nara-wu.ac.jp/~kako/teaching/ca2005/chap6.pdf
[6] http://www.math.kobe-u.ac.jp/Asir/ca.pdf
[7] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.558.6168&rep=rep1&type=pdf
[8] https://en.m.wikipedia.org/wiki/Polynomial_greatest_common_divisor
[9] ユークリッド環 - Wikipedia
[10] http://blog.fkraiem.org/2013/04/09/polynomial-factorisation-over-finite-fields-part-0-overview/
[11] http://people.virginia.edu/~mve2x/7751_Fall2009/lecture24.pdf
[12] Hensel's lemma - Wikipedia
[13] https://math.usask.ca/~fvk/bookch9.pdf
[14] メモ: ヘンゼルの補題 - 再帰の反復
[15] http://hariharan-ramesh.com/ppts/polyfactoring.pdf
[16] PariDroid - Google Play の Android アプリ

2017-11-03

「リーマン積分＜ルベーグ積分」という感覚を味わう

ルベーグ積分

ルベーグ積分について調べていると、ルベーグ積分はリーマン積分より優れているという文面をよく見かける。これは恐らく事実なのだが、それを知るには両者を様々な観点から比較してみる必要があるだろう。

そこで、本稿では特に基本的な2つの観点、すなわち、積分可能条件と項別積分可能条件について両者を比較し、ルベーグ積分がいかに優れているかを味わってみようと思う。

積分可能条件

リーマン積分可能条件について学部の解析学の講義で習うのは以下のような事実であろう。すなわち、関数fの上ダルブー和と下ダルブー和の極限が一致するときfは積分可能と言い、その極限がfの積分となるのである[2]。これを一歩推し進めると、以下の定理が成立する[1]。

リーマン積分可能条件

有界関数 $f : [\alpha, \beta] \to \mathbb{R}$ について次が成立する：
fがリーマン積分可能であるための必要十分条件は, fがほとんど至るところで連続となることである。そしてこのときfはルベーグ積分可能で

$\displaystyle{ (R) \int_{\alpha}^{\beta} f(x) dx = (L) \int_{\alpha}^{\beta} f(x) dx }$

ただし、積分記号の前に(R)、(L)が付いているのはそれぞれリーマン積分、ルベーグ積分を表す。これを見ると分かるように、リーマン積分が扱えるのは有界関数に限定され、積分範囲についても有界閉区間しか許されない。

ルベーグ積分可能条件については以下が成立する[1]。

ルベーグ積分可能条件

E上の正値関数fに対して, 単純関数 $0 \le \phi(x) \le f(x)$ の積分

$\displaystyle{ \int_E \phi(x) dx }$

の上限が有限であるとき, それを

$\displaystyle{ \int_E f(x) dx }$

で表し, fをE上で積分可能とよぶ。
正値でない関数fに対しては

$\displaystyle{ f^{+}(x) = \max\{f(x), 0\},\ f^{-}(x) = \max\{-f(x), 0\} }$

が共に積分可能のとき積分可能と定め,

$\displaystyle{ \int_E f(x) dx = \int_E f^{+}(x) dx - \int_E f^{-}(x)dx }$

とする。

ただし、Eは可測集合である。

このように、ルベーグ積分は必ずしも有界でない関数に対しても行うことができる。また、積分区間は閉区間でも開区間でもよく、もっと言うと区間である必要もなければ有界である必要すらない。そのため、ルベーグ積分はリーマン積分と比べてより幅広く積分が可能となるのである。

広義積分の場合

リーマン積分は極限と組み合わせることで、積分可能な関数のクラスを拡張することができる。これを広義リーマン積分と呼ぶ。

実は、ルベーグ積分不可能だが、広義リーマン積分可能な関数が存在する。そう聞くと、「なんだ、ルベーグ積分がリーマン積分より優れているなんて嘘じゃないか」と思うかもしれない。しかし、広義リーマン積分は厳密にはリーマン積分とは異なるし、ルベーグ積分も同じように極限と組み合わせて広義ルベーグ積分に拡張することができる。その意味で、やはりルベーグ積分はリーマン積分より優れていると言えるだろう。

以下に各種積分が可能となる関数のクラスの包含関係を示す。

f:id:peng225:20171022145517p:plain

具体例

いくつかの関数について、それぞれリーマン積分とルベーグ積分を行うことができるか見てみよう。

例1：ディリクレ関数

ディリクレ関数の定義を以下に示す。

$\displaystyle{ \chi_{\mathbb{Q}}(x) = \begin{cases} 1 & (x \in \mathbb{Q}) \\ 0 & (otherwise) \end{cases} }$

これを区間[a, b]で積分することを考える。 $\mathbb{Q}$ は $\mathbb{R}$ の稠密な部分集合なので、ディリクレ関数はほとんど至るところで不連続となる。よってこれをリーマン積分することはできない。

一方、ディリクレ関数は0, 1という有限個の値を取り、かつルベーグ測度に対して可測関数であることが容易に示されるため、ルベーグ積分可能である。 $\mathbb{Q} \cap [a, b]$ の測度は0であるため、具体的に積分を実行した結果は以下のようになる。

$\displaystyle{ \int_a^b \chi_{\mathbb{Q}}(x) dx = 0 }$

例2： $f(x) = \frac{\sin x}{x}$

この関数のグラフを以下に示す。

f:id:peng225:20171023222812p:plain

この関数の区間 $[0, \infty)$ における積分を考える。積分区間が有界ではないため、これはリーマン積分不可能であるが、広義リーマン積分は可能である。

しかし、実はこれはルベーグ積分不可能である。理由は、 $\int_{0}^{\infty}f^{+}(x)$ も $\int_{0}^{\infty}f^{-}(x)$ も発散してしまうからである。広義リーマン積分の場合は正の部分と負の部分が絶妙なバランスを保って収束していたのだが、それぞれを個別に積分して差を取るというルベーグ積分の定義に従うと、無限大同士の引き算になってしまうのである。

ただし、ルベーグ積分に対しても広義積分を考えれば、この関数も積分することができる。詳しくは本[1]などを参照されたい。

項別積分可能条件

関数列 $\{f_n(x)\}$ に対してリーマン積分が項別積分可能な条件は以下のように表される[3]。

リーマン積分の項別積分可能条件

区間 $a \le x \le b$ において $f_n(x)$ が連続で, それが一様にf(x)に収束すれば,

$\displaystyle{ \int_{a}^{x} f_n(x) dx \to \int_{a}^{x} f(x) dx }$

両辺ともに連続で, 収束は一様.

一方、ルベーグ積分が項別積分可能な条件については、次の2つの定理が有名である[1]。

単調収束定理

積分可能関数 $f_1, f_2, \cdots, f_n, \cdots$ と定数Kが与えられ,

$\displaystyle{ \{f_n\}_n \nearrow a.e. }$ かつ $\displaystyle{ \int_E f_n(x) dx < K \mathrm{\ for\ all}\ n }$

か, または

$\displaystyle{ \{f_n\}_n \searrow a.e. }$ かつ $\displaystyle{ \int_E f_n(x) dx > K \mathrm{\ for\ all}\ n }$

であるなら, $\{f_n(x)\}_n$ はほとんどすべてのxに対して有限の値に収束する。そしてその値をf(x)と表すと, 関数fは積分可能で

$\displaystyle{ \int_E f(x) dx = \lim_{n \to \infty} \int_E f_n(x) dx }$

優収束定理

積分可能関数 $f_n$ , $g$ が与えられ,

$\displaystyle{ \lim_{n \to \infty} f_n(x) = f(x) \ a.e.}$ かつ $\displaystyle{ \left|f_n(x) \right| \le g(x) \ a.e.}$

であれば, fは積分可能で

$\displaystyle{ \int_E f(x) dx = \lim_{n \to \infty} \int_E f_n (x) dx }$

となる。

これら2つの定理の関係性については、調べてもいまいち情報が得られなかった。今のところは、どちらも同じくらい重要で、その時々によってどちらを使うべきか変わってくるのだと思っておくことにする。議論を簡略化するため、以下では主に優収束定理の方に着目する。

条件の厳しさの違いに関する疑問

リーマン積分は一様収束、ルベーグ積分は優収束定理により項別積分可能となるわけだが、実は優収束定理の方が緩い条件だと言われている。その理由は、優収束定理では関数列の各点収束しか求めていないからである。

しかし、これは簡単には納得できない。なぜなら、リーマン積分でもルベーグ積分でも、積分可能なのであれば結果は一致すべきだからだ。つまり、リーマン積分では項別積分すると計算結果が変わってしまうが、ルベーグ積分では変わらないなんてことがあってはならない。

この疑問の答えを探るために、以下の2つの例を考えてみよう。

例1： $f_n(x) = x^n$

この関数の区間[0, 1]での項別積分について考えてみよう。 $n \to \infty$ のとき、 $f_n(x)$ は以下の関数に各点収束する。

$\displaystyle{ f(x) = \begin{cases} 0 & (0 \le x \lt 1) \\ 1 & (x = 1) \end{cases} }$

しかし、x=1の付近でヤバい挙動をするため、一様収束とはならない。つまり、リーマン積分については項別積分可能とは言えない。

一方、ルベーグ積分については優収束定理の条件を満たすので、項別積分可能となる。積分可能なg(x)としては、例えば $g(x) = 1$ などとすればよい。

さて、これらの結論は一見すると矛盾しているように思える。一体、どちらが本当なのだろうか？

種明かしをすると、実はこれは項別積分可能である。実際、f(x)の積分は以下のようになる。

$\displaystyle{ \int_0^1 f(x) dx = 0 }$

また、 $f_n(x)$ の積分は以下のようになる。

$\displaystyle{ \int_0^1 x^n dx = \left[\frac{1}{n+1} x^{n+1} \right]_0^1 = \frac{1}{n+1} }$

$n \to \infty$ のときこれは0に収束するので、f(x)の積分と一致する。

結局のところ、リーマン積分における一様収束という条件は項別積分可能であるための十分条件に過ぎず、優収束定理はその条件をもっと精度良く広げていると言えるのだろう*1。

例2： $f_n(x) = \frac{n(n\chi_{\mathbb{Q}}(x) + 2)x}{n+1}$

この例は九州大学のあるpdf[4]から着想を得て、私が考えたものである。この関数を区間[0, 1]で積分することを考えてみよう。分子にディリクレ関数が含まれているので、実際には以下のように場合分けができる。

$\displaystyle{ f_n(x) = \begin{cases} \frac{n(n+2 )x}{n+1} & (x \in \mathbb{Q}) \\ \frac{2nx}{n+1} & (otherwise) \end{cases} }$

この関数はほとんど至るところで不連続なため、リーマン積分不可能である。しかし、ルベーグ積分は可能である。まず、 $[0, 1] \cap \mathbb{Q}$ の測度は0であるから、 $n \to \infty$ の極限は以下のようになる。

$\displaystyle{ \begin{eqnarray} \lim_{n \to \infty} f_n(x) &=& \lim_{n \to \infty} \frac{2nx}{n+1} \ a.e. \\ &=& 2x \ a.e. \end{eqnarray} }$

よって関数列 $f_n(x)$ は $f(x) = 2x$ に概収束する。ポイントは、 $x \in [0, 1] \cap \mathbb{Q}$ に対して $f_n(x) \to \infty$ となるが、それらの点は積分には影響を及ぼさないということである。

また、全てのnに対して $|f_n(x)| \le 2x\ a.e.$ なので、優収束定理により項別積分可能となる。

実際に確かめてみよう。まず、 $f_n(x)$ を積分してから極限を取ると以下のようになる。

$\displaystyle{ \begin{eqnarray} \lim_{n \to \infty} \int_0^1 f_n(x) dx &=& \lim_{n \to \infty} \left[\frac{nx^2}{n+1} \right]_0^1 \\ &=& \lim_{n \to \infty} \frac{n}{n+1} \\ &=& 1 \end{eqnarray} }$

次に、 $f_n(x)$ の極限値である $f(x) = 2x$ を積分すると以下のようになる。

$\displaystyle{ \begin{eqnarray} \int_0^1 f(x) dx &=& \left[x^2 \right]_0^1 \\ &=& 1 \end{eqnarray} }$

よって両者が一致することが分かった。

以上をまとめると、優収束定理はリーマン積分不可能な関数に対しても項別積分可能性を判定してくれることがあると言える。

まとめ

以上、リーマン積分とルベーグ積分を比較し、ルベーグ積分が優れているポイントをいくつか確認することができた。本稿の執筆を通して、ルベーグ積分は、測度の概念と"almost everywhere"の概念を組み合わせることで、さまざまな積分を簡単に扱えるようにしているのが感じられた。

正直に言って、ルベーグ積分にはそこまで興味がなかったが、勉強してみると案外面白かった。確率論への応用もあるようなので、そちらもいずれ勉強してみたい。

参考

[1]

はじめてのルベーグ積分

作者: 寺澤順
出版社/メーカー: 日本評論社
発売日: 2009/02/01
メディア: 単行本
クリック: 9回
この商品を含むブログ (1件) を見る

[2] 積分法 - Wikipedia
[3]

解析概論改訂第3版軽装版

作者: 高木貞治
出版社/メーカー: 岩波書店
発売日: 1983/09/27
メディア: 単行本
購入: 2人クリック: 138回
この商品を含むブログ (42件) を見る

[4] http://www2.math.kyushu-u.ac.jp/~taniguch/kogi/leb_t_last.pdf#search=%27%E5%84%AA%E5%8F%8E%E6%9D%9F%E5%AE%9A%E7%90%86+%E4%BE%8B%E9%A1%8C%27

*1:ただし、これを本当に主張するためには、一様収束はするが優収束定理の前提を満たさないケースは絶対に存在しないことの証明が必要となる。私はまだそれができていないため、あくまで推測であるという点にご注意頂きたい。

2017-10-15

被積分関数、下から見るか、横から見るか

ルベーグ積分

積分には大きく分けて2通りの方法がある。すなわち、リーマン積分とルベーグ積分である。リーマン積分は高校以来慣れ親しんでいる積分であり、また大学の初年度においてより厳密な取り扱いを学ぶ機会があるため、多くの方にとって積分と言えばリーマン積分を指すのだろう。

一方で、世の中にはルベーグ積分と呼ばれるものがある。これは、リーマン積分の持つ弱点を克服するために生まれたもので、より多くの関数を扱うことができる。

ルベーグ積分の議論で良く言われるのが、リーマン積分は定義域を分割するのに対して、ルベーグ積分では値域を分割するということである。このとき、誰もが疑問に思うことだろう。「なぜ定義域ではなく値域を分割すると、より柔軟な積分の定義になるのか？」と。

残念ながら、この疑問の答えは明に回答される事が少ないように思う。私自身、ルベーグ積分の学習を始めたときはちんぷんかんぷんだった。

そこで、本稿ではこの疑問に対して、私自身が考えた事について書いてみようと思う。

リーマン積分の問題

しばらくの間、簡単のために1変数実数値関数のうち定義域全体で値が0以上になるものに話を絞る。

リーマン積分では、積分区間を分割してx軸と被積分関数fで囲まれる部分の面積をたくさんの長方形を用いて近似する。長方形の高さの選び方には自由度があるが、各区間におけるfの最大値と最小値を高さにした場合の両方で計算を行い、分割を限りなく細かくしたときに両者が一致すればリーマン積分可能となる。

このやり方は連続関数なんかだと上手くいくのだが、fが積分区間においてほとんど至るところで不連続であったり*1、そもそも積分区間が無理数全体の集合のように不連続かつ稠密であったりすると、どんなに長方形の幅を狭めても面積をうまく近似できない。そもそも、そんな不可思議な関数の面積とは一体何だということも疑問である。

まず値域より始めよ

リーマン積分の問題は、どんなに細かく定義域を分割しても、ある区間内でのfの最大値と最小値が一向に近づいて行かないような関数を扱えないことにある。では、逆にfが取り得る全ての値に対して、その逆像*2の長さを求めてやるのはどうだろうか？そして、その値と逆像の長さを掛け合わせたものの総和を取るのである。

この方法に対しては、すぐに以下のような疑問が湧いてくる。

fの値の逆像は一点集合だったり離散的な点の集まりだったりするケースもある。その場合、fが取り得る全ての値の逆像は長さ0になってしまい、結局それらを足し合わせた積分値も不当に0になってしまうのではないか？
fの逆像の長さはいつでもうまく決めてやることができるのか？

1点目については、結論から言うとそうはならない。確かにfの1つの値の逆像は長さ0になることがあるが、例えばfが連続関数だったりすると、総和を取るところで非加算無限回の足し算が発生する。これは単純に0とは言い切れず、極限を用いた厳密な議論が必要となる。どうやら足し算の話が通用するのは加算無限までのようだ[2]。

ではどうするかと言うと、fに収束するような関数列を利用する。すなわち、値域を幅 $\frac{1}{2^n}$ 毎に等間隔に分割し、 $\frac{i}{2^n} \le f(x) \lt \frac{i+1}{2^n}$ となるようなxに対して値が $\frac{i}{2^n}$ となるような関数 $f_n$ を考える。当然、 $f_n \le f$ である。

誤解を恐れずに言えば、 $f_n$ はfを階段状に近似したものである。そのため、fと違って $f_n$ の値の逆像は区間であったり、区間の和集合であったりすることが多くなる。もちろん、それだけではなく、無理数全体の集合の部分集合のような扱い辛い集合になることもあり得るが、それも含めてざっくり階段状であると言えなくもない。fと $f_n$ のイメージを以下に示す。

f:id:peng225:20171014233445p:plain — 区間[a, b]においてfを階段状に近似するイメージ

そこで、そのような $f_n$ の逆像に長さの概念を定義することができたと仮定する。先ほどの2つ目の疑問でも述べたように、この逆像に対して長さを上手く定義できるかという問題はあるが、ここではそれはできるとして話を進める。

この時、その長さと $f_n$ の値を掛け合わせたものを取り得る全ての値について足し合わせてやることで、面積と呼ぶべき量が得られる。fを直接扱う場合との違いは、 $f_n$ は高々加算無限個の値しか取り得ないため、最後の総和を問題なく計算できるところにある。あとは $n \to \infty$ としてやれば、その極限としてfの積分が求まるというわけである。

測度、可測集合、可測関数

さて、上の議論を成立させるためには、先ほど仮定した長さに関する議論を明確にしておかなければならない。これは集合に対して測度の概念を導入することで解決される。

測度には様々な種類があるが、 $\mathbb{R}$ 上で最も良く使うのはルベーグ測度と呼ばれるものである。ルベーグ測度とは、いわゆる日常的な意味で言うところの長さの概念を厳密に定めたものである。本稿では深く触れないが、ルベーグ測度を用いれば無理数全体の集合と区間[0, 1]の交わりのように病的な集合に対しても、長さを決めることができる。

では、測度というのはあらゆる集合に対して定義できるのだろうか？そうだと嬉しいが、さすがにそういうわけにはいかない。測度を定める事ができる集合は可測集合と呼ばれる。

そうなると、問題は $f_n$ の逆像が可測集合になるかどうかであるが、これも常にそうなるとは言えない。逆像が可測集合になるような関数は可測関数と呼ばれ、ルベーグ積分はそういう関数に対してしか定義できない。(追記1参照)

ただし、可測でない集合というのは、普通に生活している分にはあまり出くわすことはない。それどころか、可測でない集合の構成例は1つしか知られていないようだ[1]。しかも、選択公理を用いるかなり技巧的なものである。つまり、集合や関数が可測であるかどうかを確かめることはもちろん重要だが、実際に可測でなくて困るケースというのは稀だと思われる。

定義域の柔軟性

これまでの議論では主に1変数実数値関数が主役だった。しかし、一般の関数の場合は変数の数も様々だし、そもそも定義域が $\mathbb{R}^n$ やその部分集合とは全く違う集合であることも考えられる。

しかし、例え定義域がどんな集合であろうとも、測度さえ定義できればルベーグ積分を考えることができる。積分における難しさは測度に押し付けて、積分自体はシンプルに実行する。これこそが、ルベーグ積分の非常にパワフルな点である。

例えば、世の中には確率空間に対して定められる確率測度と呼ばれる概念がある[3]。もし確率空間を定義域とした関数を積分したいと考えたとき、リーマン積分であれば「何をどうやって長方形に分割するんだ？」と悩まなければならない。これがルベーグ積分であれば、測度さえ決めてやればいつでも全く同じ方法で積分を行う事ができるのである。

このような事が成立するのは、被積分関数が常に実数値を取るからである*3。つまり、定義域はその時々によって姿を変えるが、値域はいつも $\mathbb{R}$ またはその部分集合なので、こちらに着目した方が積分の定式化がしやすいのである。

まとめ

以上、ルベーグ積分がなぜうまくいくのかについて、値域というキーワードから私なりの考察をしてみた。結論としては、以下の点が重要であることが分かった。

~~可測関数に対しては関数値の逆像に対して長さの概念、すなわち測度を与えることができるので、それを用いて積分を定義できる。~~(追記2を参照)
値域は常に数値なので、どんな空間においても同じ形式で積分が定義できる。代わりに測度の計算が複雑になるが、そこはブラックボックスと考えて良い。

プログラミングっぽくまとめると、測度インターフェースを引数に取るルベーグ積分なるfunctionが定義できて、測度の実装はポリモーフィズムによりその時々で変更可能、と言ったところか。考え方が分かると、ルベーグ積分はなかなか面白い。

追記1

とんでもない誤解をしていたが、可測関数の逆像は必ずしも可測集合とは限らないようだ[1]。区間の逆像は可測集合になるようだか、一般にはそうとは限らないらしい。

正確には、まず先に単純関数と呼ばれる関数を考える。単純関数の定義には「逆像が可測集合である」という条件が含まれる。一般の可測関数fに対しては、fに収束する単純関数の列 $f_n$ が存在することが知られている。

つまり、本文中の誤りを訂正すると、もし $f_n$ が単純関数ならば、その逆像は定義から必ず可測集合となる。また、fが可測関数でなければ、そもそもfに収束するするような単純関数の列 $f_n$ が存在するとは限らない、ということになるだろう。

追記2

修正を取りこぼしていた。こちらも追記1と同種の誤りである。

正しくは「可測関数fに対しては、単純関数の収束列が存在する。単純関数の逆像に対しては長さの概念、すなわち測度を与えることができるので、それを用いて積分を定義できる。このとき、ある種の条件を満たせば、その関数列の積分値の極限としてfの積分値を得ることができる。」となる。

ここで言うある種の条件については本文では触れていないが、これは結構重要である。詳細はまたの機会に書くつもりでいる。

参考

[1]

はじめてのルベーグ積分

作者: 寺澤順
出版社/メーカー: 日本評論社
発売日: 2009/02/01
メディア: 単行本
クリック: 9回
この商品を含むブログ (1件) を見る

[2] http://www.ma.noda.tus.ac.jp/u/sh/pdfdvi/ana1.pdf
[3] 確率測度 - Wikipedia

*1:「ほとんど至るところで」というのは歴とした数学用語である。ご存じない方は、さしあたり日本語の語感そのままの意味で捉えて頂いて構わない。

*2:逆像と逆写像の違いに注意。両者は全然違う。

*3:複素数の時もあるかもしれないが、難しいのでそれは忘れることにする。

2017-09-22

群が可解でないための位数の条件を炙り出す

群可解群

可解でない群は珍しい？

群論を勉強していると可解群という概念が登場する。これはガロア理論において大活躍する極めて重要な群であり、群がどんな時に可解になるかというのは興味ある問題である。

しかし、位数の小さい群を見ていると、どうにも可解でない群を見つける方が難しいように感じる。それはある意味当然で、位数59以下の群は全て可解群なのである。つまり、可解でない群を見つけようと思ったら、ある程度位数の大きい群に目を向けなければならない。

そこで、本稿では群がどのような位数のときに可解でなくなり得るのかという条件について調べてみることにする。

可解群の定義

まずは定義から始めよう。本[1]から定義を引用する。

Gを群とする. Gの部分群の列 $G = G_0 \supset G_1 \supset \cdots \supset G_n = \{ 1 \}$ があり, $i = 0, \cdots , n-1$ に対し, $G_{i+1} \lhd G_i$ で $G_i / G_{i+1}$ が可換群となるとき, Gを可解群という.

進め方

本稿では具体的なところから雰囲気を掴むために、以下の表を少しずつ埋めていくことを考える。

	0	1
0	-	○
10
20
30
40
50
60
70
80
90

各セルは、最左列と最上段の数値を足して得られる整数が位数となる群を表す。そのような群がどうあがいても可解群になってしまうときに○をつけることにする。そうして、最後まで空白のまま残ったセルが可解でなくなる可能性があるというわけである。

可解群になる位数いろいろ

群の位数を素因数分解したときのパターンと、群の可解性の関係について調べてみよう。以下ではp, q, rは相異なる素数とし、n, mは正の整数であるとする。

位数 $p$

位数pの群はp次巡回群 $C_p$ のみである。巡回群はアーベル群であり、アーベル群は可解群である。よって、位数pの群は可解群である。

これにより、以下のように表を更新できる。

	0	1	2	3	5	7	9
0	-	○	○	○	○	○
10		○		○		○	○
20				○			○
30		○				○
40		○		○		○
50				○			○
60		○				○
70		○		○			○
80				○			○
90						○

位数 $p^n$

これは上のケースの拡張である。位数 $p^n$ の群はp群と呼ばれる。p群は冪零群と呼ばれる群の一種であり、冪零群は可解群である。冪零群の定義を本[1]から引用する。

Gを群とする. Gの部分群の列 $G = G_0 \supset G_1 \supset \cdots \supset G_n = \{ 1 \}$ があり, $i = 0, \cdots , n-1$ に対し, $G_{i+1} \lhd G$ で $G_i / G_{i+1}$ が $G/G_{i+1}$ の中心に含まれるなら、Gをべき零群という.

p群が冪零群であることと、冪零群が可解群であることの証明は長くなるので割愛する。

これにより、以下のように表を更新できる。

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○		○	○	○
10		○		○			○	○		○
20				○		○		○		○
30		○	○					○
40		○		○				○		○
50				○						○
60		○			○			○
70		○		○						○
80		○		○						○
90								○

位数 $p^n q\ (q < p)$

この節では $q < p$ と仮定する。Sylowの定理より、この群Gは位数 $p^n$ の部分群Hを持つ。この時、Hの指数はqである。

ここで、以下の定理を利用する (Wikipedia[2]より引用) 。

p が G の位数を割り切る最小の素数である場合、指数 p の任意の部分群は正規部分群である。

証明は[3]等を参照されたい。

少々ややこしいが、上記定理における素数pは今考えているケースではqに相当する。これよりHは正規部分群となるため、剰余群 $G/H$ を考えることができる。

ここで、さらに以下の定理を利用する (Wikipedia[4]より引用) 。

Gが可解群であるのは、NとG/Nがともに可解群であるとき、およびその時に限る。

ただし、NはGの正規部分群である。

今のケースに当てはめて考えると、 $H$ と $G/H$ が共に可解群であれば、Gは可解群になるということである。

$H$ はp群なので可解群である。また、 $|G/H| = q$ であり、位数が素数なので $G/H$ は可解群である。よってGは可解群である。

これより、表は以下のようになる。

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○		○	○	○	○	○	○	○
20		○	○	○		○	○	○		○
30		○	○	○	○	○		○	○	○
40		○		○			○	○		○
50	○	○		○	○	○		○	○	○
60		○	○		○	○		○		○
70		○		○	○	○		○		○
80		○	○	○		○	○	○		○
90		○		○	○	○		○	○

位数 $pqr$

位数pqrの群Gは位数p、q、またはrの正規部分群Hを持つことが知られている[5]。Hは位数が素数なので可解群である。

どの場合でも同じなので、ここでは仮に $|H| = p$ だったとする。この時、剰余群 $G/H$ の位数はqrとなる。この位数の群が可解群であることは既に述べた。よって上の節で引用した定理により、Gは可解群である。

これにより、表は以下のようになる。

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○		○	○	○	○	○	○	○
20		○	○	○		○	○	○		○
30	○	○	○	○	○	○		○	○	○
40		○	○	○			○	○		○
50	○	○		○	○	○		○	○	○
60		○	○		○	○	○	○		○
70	○	○		○	○	○		○	○	○
80		○	○	○		○	○	○		○
90		○		○	○	○		○	○

位数がsquare freeの場合

これは上で示したケースの一般化である。位数がsquare freeであるとは、相異なる素数 $p_1, p_2, \cdots , p_k$ を用いて位数を $p_1 p_2 \cdots p_k$ と表せることを言う。このタイプの群が可解群であるこの証明は、例えば[6]から順にリンクを辿っていくと説明がある。

位数が99以下の群の場合、位数を4つ以上の素数の積で表すことができないため、今回は特に表の更新はない。

位数 $p^n q^m$

このタイプの群が可解群であることはBurnsideの定理と呼ばれている[7]。これの証明はかなり難しい。少なくとも、今の私のレベルでは説明できない。本稿では結果だけ拝借させて頂くことにし、以下のように表を更新する。

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○	○	○	○	○	○	○	○	○
20	○	○	○	○	○	○	○	○	○	○
30	○	○	○	○	○	○	○	○	○	○
40	○	○	○	○	○	○	○	○	○	○
50	○	○	○	○	○	○	○	○	○	○
60		○	○	○	○	○	○	○	○	○
70	○	○	○	○	○	○	○	○	○	○
80	○	○	○	○		○	○	○	○	○
90		○	○	○	○	○	○	○	○	○

位数が奇数の場合

驚くべきことに、位数が奇数の有限群は必ず可解群になる。これはFeit-Thompsonの定理と呼ばれており、証明は鬼ムズらしい[8]。今回の場合は、空白のセルはすでに偶数だけなので、特に更新はない。

さらに位数が大きい場合

以上、位数が99以下の群について、位数がどんなときに可解群にならざるを得なくなるのかを調べてみた。結局、可解でなくなる可能性がある位数はたった3つしかないことが分かった。しかも、これは必要条件なので、ひょっとしたらこれらも特殊な事情により必ず可解になったりするかもしれない。ただし、少なくとも位数60の群については、5次交代群 $A_5$ が可解群ではないことが知られている。

また、逆に群が可解にならないためには、以下の条件を満たす必要があることが分かった。

位数が偶数であること。
位数を素因数分解したときに相異なる3つ以上の素因数が含まれ、かつそのうち少なくとも1つは指数が2以上になること。

これらの条件を満たす位数というのはどれくらいの頻度で出現するのだろうか？それを調べるために、ある自然数nについて、n以下の自然数のうちそれを位数とする群が可解でなくなり得るものがいくつあるか調べる。そして、それがnと共にどのように変わっていくのかをグラフにして見てみよう。

まず、300までの位数について計算したものを以下に示す。
f:id:peng225:20170922003148p:plain

このグラフからも、位数59以下の群が全て可解群になることが見て取れる。

次に、10,000までの位数について計算したものを以下に示す。
f:id:peng225:20170922003202p:plain

なんだか線形に増えているように見えるが、よく見るとやや下に凸な形状をしているようだ。

これより、可解でない群というのは無数に存在する可能性があることが分かった。ただし、本当に無数に存在するかどうか知るには、証明が必要である。

まとめ

以上、群の可解性と位数の関係を調べ、どんな時に群が可解でなくなり得るのかを考察した。今回は私が調べた限りの情報を載せたが、まだ見ぬ定理があって、本当の姿はちょっと違うということもあるかもしれない。有限群と言えど、結構奥が深いものだ。

参考

[1]

代数学1　群論入門 (代数学シリーズ)

作者: 雪江明彦
出版社/メーカー: 日本評論社
発売日: 2010/11/17
メディア: 単行本（ソフトカバー）
購入: 1人クリック: 21回
この商品を含むブログを見る

[2] 正規部分群 - Wikipedia
[3] abstract algebra - Normal subgroup of prime index - Mathematics Stack Exchange
[4] 可解群 - Wikipedia
[5] A Group of Order $pqr$ Contains a Normal Subgroup of Order Either $p, q$, or $r$ – Problems in Mathematics
[6] Square-free implies solvability-forcing - Groupprops
[7] Burnside theorem - Wikipedia
[8] Feit–Thompson theorem - Wikipedia

	0	1	2	3	5	7	9
0	-	○	○	○	○	○
10		○		○		○	○
20				○			○
30		○				○
40		○		○		○
50				○			○
60		○				○
70		○		○			○
80				○			○
90						○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○		○	○	○
10		○		○			○	○		○
20				○		○		○		○
30		○	○					○
40		○		○				○		○
50				○						○
60		○			○			○
70		○		○						○
80		○		○						○
90								○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○		○	○	○	○	○	○	○
20		○	○	○		○	○	○		○
30		○	○	○	○	○		○	○	○
40		○		○			○	○		○
50	○	○		○	○	○		○	○	○
60		○	○		○	○		○		○
70		○		○	○	○		○		○
80		○	○	○		○	○	○		○
90		○		○	○	○		○	○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○		○	○	○	○	○	○	○
20		○	○	○		○	○	○		○
30	○	○	○	○	○	○		○	○	○
40		○	○	○			○	○		○
50	○	○		○	○	○		○	○	○
60		○	○		○	○	○	○		○
70	○	○		○	○	○		○	○	○
80		○	○	○		○	○	○		○
90		○		○	○	○		○	○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○	○	○	○	○	○	○	○	○
20	○	○	○	○	○	○	○	○	○	○
30	○	○	○	○	○	○	○	○	○	○
40	○	○	○	○	○	○	○	○	○	○
50	○	○	○	○	○	○	○	○	○	○
60		○	○	○	○	○	○	○	○	○
70	○	○	○	○	○	○	○	○	○	○
80	○	○	○	○		○	○	○	○	○
90		○	○	○	○	○	○	○	○	○

	0	1	2	3	5	7	9
0	-	○	○	○	○	○
10		○		○		○	○
20				○			○
30		○				○
40		○		○		○
50				○			○
60		○				○
70		○		○			○
80				○			○
90						○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○		○	○	○
10		○		○			○	○		○
20				○		○		○		○
30		○	○					○
40		○		○				○		○
50				○						○
60		○			○			○
70		○		○						○
80		○		○						○
90								○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○		○	○	○	○	○	○	○
20		○	○	○		○	○	○		○
30		○	○	○	○	○		○	○	○
40		○		○			○	○		○
50	○	○		○	○	○		○	○	○
60		○	○		○	○		○		○
70		○		○	○	○		○		○
80		○	○	○		○	○	○		○
90		○		○	○	○		○	○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○		○	○	○	○	○	○	○
20		○	○	○		○	○	○		○
30	○	○	○	○	○	○		○	○	○
40		○	○	○			○	○		○
50	○	○		○	○	○		○	○	○
60		○	○		○	○	○	○		○
70	○	○		○	○	○		○	○	○
80		○	○	○		○	○	○		○
90		○		○	○	○		○	○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○	○	○	○	○	○	○	○	○
20	○	○	○	○	○	○	○	○	○	○
30	○	○	○	○	○	○	○	○	○	○
40	○	○	○	○	○	○	○	○	○	○
50	○	○	○	○	○	○	○	○	○	○
60		○	○	○	○	○	○	○	○	○
70	○	○	○	○	○	○	○	○	○	○
80	○	○	○	○		○	○	○	○	○
90		○	○	○	○	○	○	○	○	○

Resolventを用いた方程式の解法

3次方程式の場合

Resolvent invariant

Resolvent equation

Resolvent invariantの条件

4次方程式の場合

おまけ：Lagrange resolventとは

まとめ

参考

最小分解体とGalois群

推移的なGalois群

Frobenius群とは

定義

重要な部分群

G, K, Hの成す短完全列

の全体像

まとめ

参考

Galois理論活用の難しさ

Galois理論と多項式の既約性

既約性判定アルゴリズム

前処理

アルゴリズムの流れ

Square free判定

pの見つけ方

での因数分解

上の既約性と上の既約性の関係

Hensel lifting

p進整数の近似

組み合わせ計算複雑性

既約性判定の例

Step 1

Step 2

Step 3

Step 4

Step 5

まとめ

参考

積分可能条件

広義積分の場合

具体例

例1：ディリクレ関数

例2：

項別積分可能条件

条件の厳しさの違いに関する疑問

例1：

例2：

まとめ

参考

リーマン積分の問題

まず値域より始めよ

測度、可測集合、可測関数

定義域の柔軟性

まとめ

追記1

追記2

参考

可解でない群は珍しい？

可解群の定義

進め方

可解群になる位数いろいろ

位数

位数

位数

位数

位数がsquare freeの場合

位数

位数が奇数の場合

さらに位数が大きい場合

まとめ

参考

$F_{20}$ の全体像

$F_p$ での因数分解

$\mathbb{Q}$ 上の既約性と $F_p$ 上の既約性の関係

例2： $f(x) = \frac{\sin x}{x}$

例1： $f_n(x) = x^n$

例2： $f_n(x) = \frac{n(n\chi_{\mathbb{Q}}(x) + 2)x}{n+1}$

位数 $p$

位数 $p^n$

位数 $p^n q\ (q < p)$

位数 $pqr$

位数 $p^n q^m$

	0	1	2	3	5	7	9
0	-	○	○	○	○	○
10		○		○		○	○
20				○			○
30		○				○
40		○		○		○
50				○			○
60		○				○
70		○		○			○
80				○			○
90						○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○		○	○	○
10		○		○			○	○		○
20				○		○		○		○
30		○	○					○
40		○		○				○		○
50				○						○
60		○			○			○
70		○		○						○
80		○		○						○
90								○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○		○	○	○	○	○	○	○
20		○	○	○		○	○	○		○
30		○	○	○	○	○		○	○	○
40		○		○			○	○		○
50	○	○		○	○	○		○	○	○
60		○	○		○	○		○		○
70		○		○	○	○		○		○
80		○	○	○		○	○	○		○
90		○		○	○	○		○	○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○		○	○	○	○	○	○	○
20		○	○	○		○	○	○		○
30	○	○	○	○	○	○		○	○	○
40		○	○	○			○	○		○
50	○	○		○	○	○		○	○	○
60		○	○		○	○	○	○		○
70	○	○		○	○	○		○	○	○
80		○	○	○		○	○	○		○
90		○		○	○	○		○	○

	0	1	2	3	4	5	6	7	8	9
0	-	○	○	○	○	○	○	○	○	○
10	○	○	○	○	○	○	○	○	○	○
20	○	○	○	○	○	○	○	○	○	○
30	○	○	○	○	○	○	○	○	○	○
40	○	○	○	○	○	○	○	○	○	○
50	○	○	○	○	○	○	○	○	○	○
60		○	○	○	○	○	○	○	○	○
70	○	○	○	○	○	○	○	○	○	○
80	○	○	○	○		○	○	○	○	○
90		○	○	○	○	○	○	○	○	○