インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

岩波科学ライブラリー253『巨大数』〜アッカーマン関数に関する合同式について〜

9/6発売の書籍

鈴木真治著『巨大数』岩波科学ライブラリー253

を購入しました(岩波書店のページ)。


一切のネタバレを嫌う方はこれ以降は読まれた後にご覧になってください。


この本は巨大数史をまとめた初めての本であり、

  • かなり古い時代に考えられた巨大数
  • 自然科学に現れる巨大数
  • 数学に現れる巨大数

について、主に歴史的観点からそれらが解説されています。

「Graham数」は当然現れますが、「ふぃっしゅ数」などの最近の話までは書かれていません(今後、巨大数に関する後続の本が現れると期待します)。

「恒河沙」が「ガンジス河の砂」という意味であるということは初めて知りましたし、著者が数学史家であることから納得いくのですが、Stiglerの法則が成立してしまっている多数の事例を紹介していることが個人的には面白いです(Cantorの対角線論法を最初に用いたのはCantorではないなど)。また、科学者が発見した当時の年齢が書かれているのも嬉しいです。これから出版される全ての書物に真似して欲しいぐらいです。

つい先日書いた記事
integers.hatenablog.com
においてJones-Sato-Wada-Wiensの多項式の値が2になるような非負整数azを見つけましたが、そのcの値なんかは『巨大数』の第1、2章の観点で言えば、れっきとした巨大数です。

なお、この多項式のことをMatiyasevichの多項式と呼んでいるケースをいくつか見たのですが、Stiglerの法則と言えるでしょう(少なくともこの式自体を発見・証明したのはMatiyasevichではない)。


さて、この本に「インテジャーズ」の立場から見た非常に興味深い記述がありました。

Ackermann関数*1と呼ばれる関数から定義される或る数列A(n)について、n \geq 4ならばA(n)は必ず13の倍数になるということが92ページの「(例2)アッカーマン数*2の非素数性」に書かれています。

もう少し詳しく述べると、

\begin{align}&A(0)=1, \ A(1)=3, \ A(2)=7, \ A(3) = 61, \\ &A(n) \equiv 0 \pmod{13} \ \ (n \geq 4)\end{align}

が成り立ちます。

美しい。


A(n)を対角Ackermann数と呼ぶことにすれば、61は「最大対角Ackermann素数」という特徴を持つことになりますし、素数13の性質としても著しいです。

同書によれば水谷一氏という方から聴いたと書かれていますが、この事実がよく知られているかどうかについては私は知りません。Google検索で少し調べた限りでは文献は見つかりませんでした(しかし、93ページに書いてある通り証明は容易です)。


というわけで証明しましょう。

Ackermann関数

定義1 非負整数m, nに関する正整数値二変数関数\mathrm{Ack}(m, n)
\mathrm{Ack}(m, n) := \begin{cases}n+1 & m=0, \\ \mathrm{Ack}(m-1, 1) & n=0, \\ \mathrm{Ack}(m-1, \mathrm{Ack}(m, n-1)) & \text{その他}\end{cases}
によって二重帰納的に定義する。

補題1 非負整数nに対して
\begin{align}\mathrm{Ack}(1, n) &= n+2, \\ \mathrm{Ack}(2, n) &= 2n+3, \\ \mathrm{Ack}(3, n) &= 2^{n+3}-3\end{align}
が成り立つ。

証明. 順番に定義1を用いてnに関する帰納法で証明できる。 Q.E.D.

定義2> 非負整数nに対して、対角Ackermann数 A(n)\mathrm{Ack}(n, n)によって定義する。

A(1)=3, \ A(2)=7, \ A(3)=61は補題1から即座にわかります。

\displaystyle A(4) = 2^{2^{65536}}-3

を定義から確認してみましょう。

Knuthの矢印記号

非負整数a, b, n(ただし、a, n \geq 1)に対して、a \uparrow^n bを次のように定義します*3

定義3 a \uparrow b := a^bとし、n \geq 2に対するa \uparrow^n b
a \uparrow^n b:= \begin{cases} 1 & b=0, \\ a \uparrow^{n-1} (a \uparrow^n (b-1)) & \text{その他}\end{cases}
によって帰納的に定義する。

任意の正の整数nに対して

\begin{align}2\uparrow^n 0&=1, \\ 2\uparrow^n 1 &= 2, \\ 2\uparrow^n2 &= 4\end{align}

が成り立つことは定義から容易に確かめられます。

補題2 整数m, n(ただし、m \geq 3, n\geq 0)に対し、
\mathrm{Ack}(m, n) = 2\uparrow^{m-2}(n+3)-3
が成り立つ。

証明. m, nに関する二重帰納法で証明する。m=3のとき任意のn \geq 0で成立することは補題1より分かる。m-1 \geq 3のとき任意のn \geq 0で主張が成り立つと仮定する。このとき、

2\uparrow^{m-2}3 = 2\uparrow^{m-3}(2\uparrow^{m-2}2) = 2\uparrow^{m-3}4

より

\mathrm{Ack}(m, 0) = \mathrm{Ack}(m-1, 1)=2\uparrow^{m-3}4-3 = 2\uparrow^{m-2}3-3

が成り立つ。また、n \geq 1のとき\mathrm{Ack}(m, n-1)について主張が成り立つと仮定すると、

\begin{align}\mathrm{Ack}(m, n) &= \mathrm{Ack}(m-1, \mathrm{Ack}(m, n-1)) \\ &= \mathrm{Ack}(m-1, 2\uparrow^{m-2}(n+2)-3) \\ &= 2\uparrow^{m-3}(2\uparrow^{m-2}(n+2) )-3 \\ &= 2\uparrow^{m-2}(n+3)-3\end{align}

と計算され、\mathrm{Ack}(m, n)のときにも成立することが示された。 Q.E.D.

証明

補題2より、A(n) = 2\uparrow^{n-2}(n+3)-3が成り立つので、

 2\uparrow^nb \equiv 3 \pmod{13} \ \ \ (n \geq 2, b \geq 3) ー①

が成立することを示せば十分。

正整数kに対して2^{2^k} \equiv 4 \pmod{12}であることを帰納法で証明できる。また、b\geq 2ならば、矢印記号の定義から正の整数kが存在して2\uparrow \uparrow b = 2^{2^k}と書けるので、

2 \uparrow \uparrow b \equiv 4 \pmod{12} \ \ \ (b \geq 2) ー②

が成立する。

Fermatの小定理より、2^{12} \equiv 1 \pmod{13}なので、正整数a, ba \equiv b \pmod{12}を満たすならば

2^{a} \equiv 2^b \pmod{13}

すなわち

2 \uparrow a \equiv 2 \uparrow b \pmod{13}

が成り立つ。従って、b \geq 3であれば、②より

2 \uparrow \uparrow b = 2 \uparrow (2 \uparrow \uparrow (b-1) ) \equiv 2 \uparrow 4 = 2^{16} \equiv 2^4 = 16 \equiv 3 \pmod{13}

n=2の場合に①が示された。n \geq 3の場合はnに関する帰納法で示す。

2 \uparrow^n b = 2\uparrow^{n-1}(2\uparrow^n(b - 1) )

に注意すれば、2 \uparrow^n (b-1) \geq 3ならば帰納法の仮定から①が成り立つが、それはb \geq 3で成立する。 Q.E.D.

*1:と現今呼ばれているこの関数も、Ackermannによるオリジナルのものではない。

*2:"Ackermann number"と言えば普通は他の数列を表すそうなので、注意が必要です。

*3:参考記事: integers.hatenablog.com