素因数分解の一意性の何がありがたいのか?

この記事は 日曜数学 Advent Calendar 2015 21日目の記事です。

前回はtsunutさんの 食べられる「アレ」の製造シミュレーション(1) でした。

素因数分解の一意性について、ちょっとした発見があったので、その内容を書いてみようと思います。

素因数分解の一意性って?

まず、この定理の内容について簡単に紹介すると、「自然数の素因数分解の方法は、順序を入れ替えれば必ず1通りになるよ」という法則です。

順序を入れ替えれば1通りというのは、例えば 30 の場合

30 = 2 * 3 * 5 = 5 * 3 * 2 = 3 * 5 * 2

のように書けるけど、順番並べかえたらどれも一緒になるよね、ということです。

もう、まさに「自明」と言いたくなってしまうような定理の代表格です。

何がありがたいの?

直感的には当たり前に思えるのですが、「この性質が成り立たない世界」をイメージすると、ありがたさが少し分かるかもしれません。

これはほんの一例なのですが、偶数だけの集合Eに対して、和・差・積の計算をそのまま適用します。

すると、この集合に対する素数(みたいな存在)というのは、「自分以外では割れない数」を指すことになります。

こうしてできるE上の素数を試しに並べてみると

2, 6, 10, 14, 18, 22, 26, 30,

となりますが、この素数の組み合わせは

60 = 2 \times 30 = 6 \times 10

という2通りの分解が見つかってしまいます。(3通り、4通り、… の分解の組み合わせを持つ数字も出てきます)

 

このような、「素因数分解が1通りじゃない世界」があるってことを知っているだけでも、だいぶ見え方が変わります。

実際、この「素因数分解が何通りできるか」という、いわば「分解のしやすさ」が、数学の重要な要素の一つである「類数」と密接に関わっていたりします。難しい分野ですが、深掘ると面白い話題がたくさん出てくるところなので、そのあたりも別の機会に(思い出しながら)書ければと。

まとめ

日曜数学会は行きたいと思いながら一度も行けなかったので、来年こそは参加したいと思います。

グッドスタインの定理 – 数学による突然の裏切り

この記事は、Math Advent Calendar 2015 19日目の記事です。

前の記事は、リングさんの「今年のクリスマスはエキゾチックな球面を作ろう」です。

突然の裏切りとは?

数学をやるには直感が必要、とはよく言われますが、どうしても直感的に受け入れがたい結果というのは、いくつもあるものです。

例えば、誕生日の確率の問題については、聞いたことある方もいるのではないでしょうか。

これは、「クラスメイトが n 人いるとします。n 人の中で、誕生日がかぶるペアが存在する確率はいくらでしょう?」という問題です。あるいは、「誕生日がかぶるペアが存在する確率が50%を超えるのは、クラスが何人以上の時でしょうか?」という問い方をされることもあります。

「1年は365日あるので、直感的には50人とか100人ぐらいいないと50%は超えない気がする・・・」と思ってしまいそうなものですが(私もそうでしたが)、実際は23人の時点で50%を超えてしまいます

このような、直感からは導きにくい結果を返す場面を、数学の「裏切り」と(私が勝手に)呼んでいます。

そして、ときどき思い出したように突然裏切ってくれる数学が、私は大好きです。(Mではありません)

 

ここでは、私がこれまで学んだ中で、「裏切られた!」と感じた定理の一つである「グッドスタインの定理」(Goodstein’s Theorem)を紹介します。

はじめて定理の内容を聞いたとき、何を言っているのか、正直さっぱり分かりませんでした。

グッドスタインの定理とは?

定理の前に、「グッドスタイン列」なる数列G_nを定義します。

これは、初期値 G_1 ( > 0) に対して、以下のような操作を繰り返してできる数列を指します。

  • G_1を、底を2とした指数の和に展開します(このとき、指数部分も含めて展開します。例えば、131 = 2^7 + 2 + 1 の場合、展開した結果は 131 = 2^{2^2 + 2 + 1} + 2 + 1 となります。
  • G_1の展開式から、2を3に変換して、計算した値から1を引いたものをG_2とします。(上の例の場合、 G_2 = (3^{3^3 + 3 + 1} + 3 + 1) - 1 = 3^{31} + 3
  • G_2を、底を3とした指数の和に展開します( G_2 = 3^{3^3 + 3 + 1} + 3
  • G_2の展開式から、3を4に変換して、計算した値から1を引いたものをG_3とします。(上の例の場合、 G_3 = (4^{4^4 + 4 + 1} + 4) - 1 = 4^{261} + 3 )
  • 以下同様に、底を4から5に変換して1を引いてG_4、底を5から6に変換して1を引いてG_5 … と計算していきます。

初期値 131 の場合の例を見てもわかるように、この「グッドスタイン列」は、あっという間に大きな値になり、このまま爆発的に増えることが予想されますが。。。

ここで「グッドスタインの定理」を見てみます。

グッドスタインの定理

任意のグッドスタイン列は、0 に収束する。

 

…どうでしょうか?ちょっと何言ってるか分かりませんよね?

つまり、先ほどの計算をず〜〜っと進めていくと、どんな値から始めたとしても、最終的には必ず 0 に到達すると主張しているわけです。

G_1 = 131 から G_3 =4^{261} + 3 と一気に跳ね上がる数列であるにもかかわらずです。

(たった2項の差で、桁にして150桁以上も跳ね上がっていますw)

証明の着想

この定理、実は証明の着想に関しては、それほど難しくはありません。(厳密にはもう少しステップが要るようですが…)

先ほどのG_1 = 131 の例をもとに、各項の展開式における底をbとすると、以下のように並んでいます。

  • G_1 = b^{b^b + b + 1} + b + 1
  • G_2 = b^{b^b + b + 1} + b
  • G_3 = b^{b^b + b + 1} + 3
  • G_4 = b^{b^b + b + 1} + 2

これをbを変数とする多項式と見ると、この多項式は一般的な多項式の順序のもとで減少列になっています。

(一般的な多項式の順序とは、「次数が大きい方が、大きい多項式である」とか、「同じ次数なら係数の大きい方が、より大きい多項式である」といったルールに基づく順序を指します)

この列はこの後もずっと次数を下げつつ減少していきますが、 0 を下回ることはないため、最終的には 0 に収束する、というのが証明の概要です。

なんだか、わかったような、騙されたような、そんな気持ちにさせられます。

 

ちなみにこの定理、証明の着想自体はさほど難しくないにもかかわらず、ペアノ算術(一般的な数の計算)の範囲内では証明できないことも分かっているようです。どこまで裏切ってくれる気なんですしょうかね。

まとめ

数学は裏切らないと言いますが、たまにはこういう意外性を鑑賞して積極的に裏切られ、ギャップ萌えを味わうのもまた一興です。