スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

サイダックによる素数が無限にあることの証明に関して

フィリップ・サイダック氏による、素数が無限にあることの別証があるということを先日ツイッターで知った。

読んでいるうちに、別証とはいいつつも、実質的にはユークリッドの証明とほとんど違わない気がしてきたので、そのことについて書くことにする。

と書くと氏の証明を読まれて感動した方の気分を害してしまうかもしれないので言っておくと。ある証明と別の証明がどの程度似ているか、というのを定量的に表す方法は私の知る限りまだ確立されていないので、「主観の問題」ということになる。

ここでは、なぜ私がそう感じたかの道筋を示し、皆さんがどう感じるかはそれぞれにお任せしよう。似ている、似ていないの結論にこだわるよりも、少なくとも一段この定理に関する理解は深まるはずである。

それではまず、ユークリッドとサイダックの両証明で共通して用いられている、
A: 「自然数NとN+1は互いに素である」という事実について確認しておく。

「互いに素」とは、1より大きい共通の因数を持たないということだ。因数というのは、ある数を割り切る数、ということで、例えば

6 = 2 * 3 (* は掛け算の記号)

だから、2や3は6の因数である。なお、因数のうち、素数であるものを素因数という。だからこの例で言うと2や3は6の素因数である。

12 = 2 * 2 * 3

の例で言うと、やはり2や3は12の素因数である。4や6は、12の素因数ではないが、因数ではある。


さて、A: に戻って、NとN+1が共通の因数mを持つとどうなるか考えてみる。すると、NもN+1も、mを因数として

N = m * 整数
N + 1 = m * 別の整数

という形に書けるわけである。下の式から上の式を引くと、

(N + 1) - N = m * 別の整数 - m * 整数 = m * (別の整数 - 整数)

という形になるわけだが、「別の整数 - 整数」というのも結局整数であるので、右辺はmを整数倍した形になっている。しかしこれはもともと、N + 1 と N の差を計算しているのであって、1に決まっている。ということは、mも、「別の整数 - 整数」の部分も両方1に取るしか可能性はない。これでN + 1とNの共通の因数mが1より大きい可能性はなくなった。

大事なので一回まとめよう。
A: 自然数N と N + 1は1より大きい共通の因数を持つことはない。このことをNとN+1は互いに素であるという。

サイダックの証明とユークリッドの証明は、見かけ上の大きな違いは、ユークリッドが背理法に依っているのに対し、サイダックの証明はある程度構成的に次々と素数を見つける手続きを与えていることだ。だが、いずれも根本は実はA:の事実によっており、背理法を使うかどうかは本質的ではない。

A:の意味するところをよく考えよう。N と N + 1は互いに素である…もしここで、Nが既知の素数全部を因数として含んでいたとしたらどうだろう?すると、N+1にはそれらの素因数は含まれないのだから、N+1には必ず新しい素数が因数として含まれることになる。

具体例でちょっと考える。適当に、N = 6とすると、N + 1 = 7である。

6 = 2 * 3
7 = 7

であり、6に含まれている素因数2, 3とは違う新しい素因数7が7には(この場合かなり自明な形で)含まれている。

より両者の類似を明確にし、背理法は本質ではないことを示すために、ユークリッドの方法を、背理法ではなくサイダックと同じ手続き的な形で述べてみる。

ステップ0. 最初は素数p(1) = 2からスタートする。
ステップ1. ここまでで判明しているすべての素数(p(1), p(2), ... p(k)としよう)を掛け算し、それに1を足す。できた数をMと呼ぶことにしよう。
ステップ2. A: で分かったように、p(1)*p(2)*...*p(k) と p(1)*p(2)*...*p(k) + 1 = Mは共通の因数を1以外に持たない。つまりMを素数の積に分解すると、かならずp(1)、N(2)...p(k)とは違った新しい素数が因数として(最低でも一個、うまくいけば複数個)得られる。これらを既知の素数のリストに追加する。
ステップ3. ステップ1に戻る。

このようにして、無限個の素数が得られていく。実際にステップ0から少し試してみよう。無限に続くので、感じがつかめたら読むのをやめて構わない。

ステップ0; p(1) = 2
ステップ1: M = 2 + 1 = 3
ステップ2: 3はそのままで素数、新しく1個の素数が見つかった!
ステップ3: ステップ1に戻る
ステップ1: 既知の素数は2と3なので、M = 2 * 3 + 1 = 7
ステップ2: 7はそのままで素数、新しく1個の素数が見つかった!
ステップ3: ステップ1に戻る
ステップ1: 既知の素数は2、3、7なので、M = 2 * 3 * 7 + 1 = 43
ステップ2: 43はそのままで素数、新しく1個の素数が見つかった!
ステップ3: ステップ1に戻る
ステップ1: 既知の素数は2、3、7、43なので、M = 2 * 3 * 7 * 43 + 1 = 1807
ステップ2: 1807は 1807 = 13 * 139と分解できて、この二つの因数は素因数、新しく2個の素数が見つかった!
ステップ3: ステップ1に戻る
ステップ1: 既知の素数は2、3、7、13, 43, 139なので、M = 2 * 3 * 7 * 13 * 43 * 139 + 1 = 3263443
ステップ2: 3263443はそのままで素数、新しく1個の素数が見つかった!
...

この手続きを実行するのに大変なところは、新しく得られたMを素数の積に分解するところである。上の例でもすでに最後の方は数式処理ソフトMaximaのお世話になった。数が大きくなるにつれてここが極めて困難になっていくので、手続き的とは言いつつも、実行するのは容易ではない。

もともとの形のユークリッドの証明は、このステップが有限回でおしまいになったとすると矛盾が生じるということを背理法の形で言ったものにすぎない。なぜ背理法で述べたかといえば、上のように手続き的な形で述べると、ある人にはわかりやすいかもしれないが、どうしても多少長くなる。結論だけを最短で示すことを考えると背理法の方が字面でいえば短くなるのでそういう形にしたのであろう。

一方のサイダックの証明であるが、ユークリッドの証明において、ステップ1の計算で出てきた既知の素数の積p(1)*p(2)*...p(k)をN(k)と呼んだらどうなるだろう?ユークリッドの証明をこれを使って書き換えてみる。といっても当たり前であるがほとんど変わっていない。

ステップ0: 最初は既知の素数はp(1) = 2 だけなので、N(1) はこれ1個の積 2そのものである。
ステップ1: N(k) + 1 をMとする。
ステップ2: MはN(k)と互いに素なので、Mを素因数の積に分解すれば既知のリストに含まれない新しい素数が得られる、これらを既知の素数のリストに追加する。
ステップ3: 新しく得られた素数をすべて、今までの既知の素数の積N(k)に掛けたものをN(k+1)として、ステップ1に戻る。

さて、既に述べたように、このステップで実行が一番大変なのはMを素因数の積に分解するところである。しかし実際にこの分解操作をすることが必要だろうか?

上の手続きでは、新しく得られた素数は、それまでの既知の素数と一緒に使って、積を計算するわけである。結局必要なのは積だけだとしたら、わざわざ一回Mを素因数の積に分解しなくても、そのままN(k)に掛けてやったらどうだろう。

そのように考えて上の手続きを少しだけ変更したものが次の手続きである。
ステップ0: 最初は既知の素数はp(1) = 2 だけなので、N(1)もこれに等しくとる。
ステップ1: N(k) + 1 をMとする。
ステップ2: Mには既知の素数以外の新しい素数が因数として含まれている。このMをそのまま既知の素数すべての積であるN(k)に掛け算してやり、これをN(k + 1)とする。N(k+1)は新しい素数も含めた既知の素数すべての積になっている。(ただしユークリッドの方法との違いは、重複を取り除いていないので同じ素因数が複数回含まれるかもしれない。だが、それはこの手続きにおいては問題にはならない。)
ステップ3: 1に戻る。

…そしてこれは、冒頭で紹介したサイダックの証明そのものである! 先ほどと同じく、具体的に実行してみよう。

ステップ0: N(1) = 2
ステップ1: M = 2 + 1 = 3
ステップ2: Mには(もし素因数の積に分解してみれば)新たな素数3が含まれている。新しい素数が得られた! また次回の実行のため、N(2) = N(1) * M = 2 * 3 = 6 とする。
ステップ3: ステップ1に戻る。
ステップ1: M = 6 + 1 = 7
ステップ2: Mには(もし素因数の積に分解してみれば)新たな素数7が含まれている。新しい素数が得られた! また次回の実行のため、N(2) = N(1) * 7 = 6 * 7 = 42 とする。
ステップ3: ステップ1に戻る。
ステップ1: M = 42 + 1 = 43
ステップ2: Mには(もし素因数の積に分解してみれば)新たな素数43が含まれている。新しい素数が得られた! また次回の実行のため、N(3) = N(2) * M = 42 * 43 = 1806とする。
ステップ3: ステップ1に戻る。
ステップ1: M = 1806 + 1 = 1807
ステップ2: Mには(もし素因数の積に分解してみれば)新たな素数13と139が含まれている。新しい素数が得られた! しかしサイダック的には実際は素因数分解はしないで、あくまで「もし素因数分解してみれば、そこには新しい素因数が含まれている」点がポイントである。また次回の実行のため、N(3) = N(2) * M = 1806 * 1807 = 3263442とする。


どうであろうか。ここまでの範囲では、両者とも結局まったく同じことをやっている。違いが出てくるのは、手続き中で得られたMに、ある素因数mがmの二乗(か三乗以上か)の形で含まれる場合である。ユークリッドの方はmを一個分だけカウントするのに対して、サイダック方式ではmが二乗や三乗の形のまま積として使われることになる。

サイダック方式の方が、頭の中で「素因数分解を実行する」というステップを省略している分は確かに簡略化されていると言えるが、背理法と手続的方法という表面上の違いを別にすれば、両者の違いはその一点だけだということもお分かりいただけるのではないだろうか。後はそれぞれの読者の感想に委ねたい。

以下は余談ではあるが、数学において、ある定理についてどのような証明が「良い証明」とされるかについては、基準は必ずしも一つではない。すぐ思いつくだけでも以下のような基準があり得る。これらは互いに関連していたり、逆に相反する要素だったりする。


1. 短い
2. 理解が容易である
3. 初等的な事実のみを前提としている
4. 構成的である
5. 他の定理や分野との関係が見てとりやすい

1.と2.は誰でも納得できる基準だろう。3.は、たとえば近年証明されたある分野の難解な大定理を用いると明らか、というようなものだと、一行で済んだとしてもその分野の専門家にしか分からないことになるので、万人向けとは言い難くなる。

4.に関しては、数学を道具として使う物理学、工学、情報などの分野では重要である。単に「~が存在する」とだけ言われるよりは、「ここで示す手続きにしたがえば、具体的に~が構成できる」ことを示される方が、多少長くなったとしても実用上ははるかに有益である。

5.も似ているが、特に数学の専門家同士で重要な観点かもしれない。数学の中の二つの異なるサブジャンルを結びつけるような成果は大きな仕事として評価されるだろう。

これは、証明を、結論という山頂まで山岳ガイドに連れていってもらうことに例えると、どのようなルートが「良いルート」なのか?という話と似ている。

最短で薮の中を突っ切り、後で一人では絶対来られないようなルートを連れていかれ、いきなり視界が開けたと思ったらすでに山頂にいた、というのが良いのか、いろいろと途中で見どころを訪ねながらじっくりと味わいながら行くのがいいか、面白みはないがメジャーな道標のある大きな道筋を辿り、後から一人でも来られるようになるのが良いか。それぞれに長所、短所があり、どれがベストか一概に言えないことはお分かりだろう。

追記 2014/04/01
数学における証明の方法として、背理法や数学的帰納法というのがある。注意しておきたいのは、しばしばこれらの方法自体は証明の本質、あるいは示されている事項の本質ではないことだ。

背理法に関して言うと、背理法に頼らずに証明できる問題ならば、どちらかといえば背理法を用いない方が望ましい。それは、背理法は言ってみればマンガにおける夢オチみたいなもので、証明の途中で作り上げた補助的な事実も、最後は「ハイ矛盾出ました~、最初の仮定が違ってたからですね~、だから途中で示したこともすべて実は成り立ってませんでしたあ~!」ということになり、結論だけは示されるが、証明した事項が成り立つ背景の構造といった、「次につながる」、あるいは「広がりを持たせる」副産物が得にくいからである。

だから、結論だけをとにかく最短で示したい場合や、証明したい結論が非常に難しく、ギリギリ背理法に頼ってなんとか示すことができる、という場合を除くと、あまり背理法を濫用しない方がよい。
スポンサーサイト

Ubuntu 13.04 日本語TeXまわりの設定メモ

ここ何年もプレゼンやら資料作成に縁のない生活を送っていたが、久々にそういったことが必要になり、Ubuntu 13.04にLaTeX環境をインストールした。何も独自性があるわけではないが、例によって忘れないようメモしておく。

Ubuntu 13.04でLaTeX環境を整える | Kubuntuにっき(仮):にしたがって、texlive-lang-cjkパッケージをインストール。

emacsからの編集作業のために、yatexパッケージをインストール。

日本語dviファイルのプレビューがこのままではできなかったので、xdvik-jaパッケージをインストール

これだけで、最低限日本語でLaTeX文書を作成できるようにはなった。

どうも他のブログなどを見るとまだいろいろ細かい設定があるようだが、ミニマルにはこれでよしとする。

さらに、プレゼン資料はLibreOffice Impressで作ることにした。数式を扱う標準のツールとして提供されているLibreOffice Mathも、まあ慣れればある程度使えるが、数式ならやはりTeXベースで入力できればそれにこしたことはない。探すと、かりぐらしのshunbo: LibreOfficeにLatexの数式を埋め込む:
でLibreOffice用のTexMathなるプラグインがあることが紹介されている。

さっそくこれをこの記事ににしたがって提供元からダウンロード、インストールしたところ、大変使い勝手が良く、もうよほどのことがなければLibreOffice Mathを使う必要はないだろうと感じた。

標準では定義されていないベクトルのブラケット記法などを使うために以下の設定を行った。

LibreOfficeアプリケーションウィンドウの左上隅に表示される「π」アイコンをクリックし、TexMathsウィンドウを開く。
このウィンドウ右下にあるボタンのうち、「Preamble」をクリックすると、サブウィンドウが開く。
このサブウィンドウ内に、必要な\usepackage{}コマンドを追加する。あるいは、直接コマンド定義をここに追加することもできる。もちろんパッケージ自体がまだシステムにインストールされていなければapt-getなりでインストールする。
「Save」をクリックして設定完了。


テーマ : ツール・ソフトウェア
ジャンル : title="コンピュータ">コンピュータ

プロフィール

GM3D

Author:GM3D
FC2ブログへようこそ!

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
FC2カウンター
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。