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

9/6発売の書籍

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

を購入しました。

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

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

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

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

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

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

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

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

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

Ackermann関数*1と呼ばれる関数から定義される或る数列 $A(n)$ について、 $n \geq 4$ ならば $A(n)$ は必ず $13$ の倍数になるということが92ページの「(例２）アッカーマン数*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関数

定義１ 非負整数 $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{otherwise})\end{cases}$

によって二重帰納的に定義する。

補題１ 非負整数 $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}$

が成り立つ。

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

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

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

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

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

Knuthの矢印記号

非負整数 $a, b, n$ (ただし、 $a, n \geq 1$ )に対して、 $a \uparrow^n b$ を次のように定義します*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{otherwise})\end{cases}$

によって帰納的に定義する。

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

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

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

補題２ 整数 $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$ で成立することは補題１より分かる。 $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}$