2016-09-12

先越されちった〜☆

その他

$\zeta (2n)$ が有理数 $\times \pi^{2n}$ と表されるというEulerの公式が僕は大好きで、４年前と９か月前に二回オリジナル証明を与えたことがあるんです。

４年前は全く同じ証明を1994年にZagierが出版していることが分かってショックを受けたエピソードを
integers.hatenablog.com
に書きました。

９か月前に見つけた証明は直後に
integers.hatenablog.com
にまとめています。

論文にしていなかった理由は「論文にする程の価値はない」という勝手な判断、および当ブログのオリジナリティを高めたいという思いからでしたが、ついさっき図書館に行って新刊雑誌を読んでいたら全く同じ証明があって少し驚きました。

Brian D. Sittinger, "Computing $\zeta (2m)$ by Using Telescoping Sums", American Mathematical Monthly, Vol. 123. No. 7, Aug.-Sep. 2016.

全くもって同じ証明でした。

AMMならこの程度の内容でも載るというのは分かるのですが、どうせ他の人が載せるのなら出しておいてもよかったな〜と少し後悔したり。。どんなに簡単な結果でも出してしまえば世の中に残るので、今後「Sittingerによる証明」などと紹介されることもあると思えば悔しいですね笑。

と思って今検索してみたら彼のスライド原稿が見つかりました：

http://faculty.csuci.edu/brian.sittinger/2015Master_Zeta.pdf

なんと、2015 2/11となっていますから発見日で言っても少なくとも10か月負けてました。。ガビーン。

しかし、Chapmanをスライドの方で引用しておきながらMatsuoka(1961)を引用していないことや、 $\zeta^{\star}$ -値と $\zeta (2m)$ を結びつける公式についてZlobin(2005)を引用していないのは良くないのではないかと思います。

Daner(2012)というのを引用しているのですが、その証明法はMatsuoka(1961)と全く同じなのです。MatsuokaはAMMに出ているのに。。。

まあ、くよくよせず、小さな結果ではなく大きな結果を出せばよいだけのこと。

2016-09-12

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

整数整数-3 整数-7 整数-61 整数-13

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}$

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

証明

補題２より、 $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, b$ が $a \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

2016-09-10

Grahamの第一論文を読む -②

Grahamの定理

過去の記事を読むには上のカテゴリーをクリックしてください。

定義

定義１ $S$ を正の実数からなる数列とする。このとき、 $S$ が半完全であるとは、ある非負整数 $n_0$ が存在して、 $\mathbb{Z}_{\geq n_0} \subset P(S)$ が成り立つときにいう。

定義２ 正の実数からなる数列 $S$ が半完全であるとする。このとき、定義１における $n_0$ の役割を満たす最小の整数を $S$ の敷居という。 $S$ が半完全でなければ、敷居は $\infty$ と定義する。

$S$ が完全 $\Longleftrightarrow$ $S$ の敷居が $0$ .

定義３ 正の実数からなる数列 $S=\{a_n\}_{n=1}^{\infty}$ に対して、数列 $S^{-1}$ を $S^{-1} = \{ a_n^{-1}\}_{n=1}^{\infty}$ によって定義する。

定義４ $S=\{a_n\}_{n=1}^{\infty}$ を正の実数からなる数列とする。集合 $\Pi(S)$ を

$\displaystyle \Pi (s) := \left\{ \left. \prod_{i=1}^ma_{k_i} \right| m=1, 2, 3, \dots, \ \ \ k_1 < k_2 < \cdots < k_m \right\}$

と定める。このとき、 $\Pi (S)$ の元を小さい順に並べてできる単調増大数列を $M(S)$ と定義する。

主定理

主定理 $S=\{a_n\}_{n=1}^{\infty}$ を正の整数からなる数列であって、

$M(S)$ は半完全
$\{a_{n+1}/a_n\}_{n=1}^{\infty}$ は有界

を満たすようなものとする。このとき、正の有理数 $p/q\ \ ( (p, q)=1)$ が $P(M(S)^{-1})$ の元となるための必要十分条件は

$p/q$ は $M(S)^{-1}$ -近似可能
$q$ は $M(S)$ のある項を割り切る

が成り立つことである。

Grahamの第一論文を読むー③ - INTEGERSで次の定理を証明します：

定理１ $S=\{a_n\}_{n=1}^{\infty}$ を正の整数からなる数列であって、

$M(S)$ は半完全
$S$ は非有界
$\{a_{n+1}/a_n\}_{n=1}^{\infty}$ は有界

を満たすようなもの、 $p/q$ ( $p, q$ は $(p, q)=1$ を満たす正整数)を

$p/q$ は $M(S)^{-1}$ -近似可能
$q$ は $M(S)$ のある項を割り切る

を満たすような正の有理数とする。このとき、 $p/q \in P(M(S)^{-1})$ が成り立つ。

この記事では定理１から主結果を導きましょう。

まず、二つ目の仮定を次のように置き換えることができます：

定理２ $S=\{a_n\}_{n=1}^{\infty}$ を正の整数からなる数列であって、

$M(S)$ は半完全
$S$ は有界かつ $a_n > 1$ なる $n$ が無数に存在する
$\{a_{n+1}/a_n\}_{n=1}^{\infty}$ は有界

を満たすようなもの、 $p/q$ ( $p, q$ は $(p, q)=1$ を満たす正整数)を

$p/q$ は $M(S)^{-1}$ -近似可能
$q$ は $M(S)$ のある項を割り切る

を満たすような正の有理数とする。このとき、 $p/q \in P(M(S)^{-1})$ が成り立つ。

定理１を仮定した定理２の証明

正の整数 $k, n_1, n_2, n_3, \dots$ であって

$n_1 < n_2 < n_3< \cdots$

$1 < k = a_{n_1}=a_{n_2}=a_{n_3}=\cdots$

を満たすようなものが存在する(二つ目の仮定から分かる)。このとき、

$a_1, \ k, \ a_2, \ k, \ k^2, \ a_3, \ k, \ k^2, \ k^3, \ a_4, \dots$

という順に並べて得られる新しい非有界数列を $S^*$ とする。正の整数 $m$ に対していくらでも大きい $l$ をとって $k^m=a_{n_l}a_{n_{l+1}}\cdots a_{n_{l+m}}$ とできることに注意すれば

$M(S)=M(S^*)$

が成り立つことが分かる( $S^*$ の項を順番に有限個掛け合わせたときに、 $k$ のべきはまとめて一番右端に持っていって考えればよい)。よって、 $S^*=\{a_n^*\}_{n=1}^{\infty}$ が定理１の仮定を満たしていることを示せば証明が完了する。確認すべきは $\{a_{n+1}^*/a_n^*\}$ が有界であることであるが、