2019-11-20

Mills の定理 ― floor(A^3^n) が常に素数となるような A が存在すること

数学

はじめに

気づいたら定期試験が始まっていました．
それは別にどうでもいいんですが，今回は Mills の定理という面白い定理を見つけたので，ステートメントと証明を紹介したいと思います．かんたんです．

ステートメント

すべての $n \in \mathbb{N}$ に対し $[A^{3^n}]$ が素数となるような $A \in \mathbb{R}$ が存在する．ここで $[ x ]$ は $x$ の切り捨て，すなわち $x$ 以下の最大の整数を示す．

証明

（以下は完全に Mills' Theorem - ProofWiki に依拠しています）

Mills の定理は初等的に証明できます．中学数学程度の知識があれば十分でしょう．

以下， $p_n$ を $n$ 番目の素数， $\mathbb{N}$ を正整数の全体， $\mathbb{P}$ を素数の全体とします．

さて，隣接する素数の差について，以下のような事実が知られています*1．
補題 1
ある $K \in \mathbb{N}$ が存在して，任意の $n \in \mathbb{N}$ に対し $p_{n + 1} - p_n \lt K {p_n}^{5/8}$ とできる*2．

これを用いて以下の補題を証明していきます．

補題 2
すべての $N \gt K^8$ に対し， $N^3 \lt p \lt (N+1)^3 - 1$ を満たすような $p \in \mathbb{P}$ が存在する．

証明
$p_n$ を $N^3$ より小さい最大の素数とします．

$\displaystyle{ \begin{eqnarray} N^3 &\lt& p_{n+1} \\ &\lt& p_n + K{p_n}^{5/8} \\ &\lt& N^3 + KN^{15/8} \\ &\lt& N^3 + N^2 \\ &\lt& N^3 + 3N^2 + 3N \\ &=& (N+1)^3 - 1 \end{eqnarray} }$

したがって，
$N^3 \lt p_{n+1} \lt (N+1)^3 - 1$
です．（証明終）

いま， $P_0 \gt K^8$ なる素数 $P_0$ をとります．補題 2 より，無限数列 $P_0, P_1, P_2, \ldots$ であって， $\forall n \in \mathbb{N}, \; {P_n}^3 \lt P_{n + 1} \lt (P_n + 1)^3 - 1$ を満たすようなものが存在します．

さらに，写像 $u, v : \mathbb{N} \to \mathbb{N}$ を以下のように定義します．
$u(n) = {P_n}^{3^{-n}}$
$v(n) = (P_n + 1)^{3^{-n}}$
$3^{-n} > 0$ より $u(n) \lt v(n)$ となることは大丈夫ですね．

こうして定義した $u(n), v(n)$ について，以下の補題が成り立ちます．
補題 3
任意の $n \in \mathbb{N}$ に対して， $u(n+1) \gt u(n)$ ．

証明
$\displaystyle{ \begin{eqnarray} u(n+1) &=& {P_{n+1}}^{3^{-(n+1)}} \\ &\gt& (P_n^3)^{3^{-n-1}} \\ &=& {P_n}^{3 \times 3^{-n-1}} \\ &=& {P_n}^{3^{-n}} \\ &=& u(n) \end{eqnarray} }$
（証明終）

補題 4
任意の $n \in \mathbb{N}$ に対して， $v(n+1) \lt v(n)$ ．

証明
$\displaystyle{ \begin{eqnarray} v(n+1) &=& (P_{n+1} + 1)^{3^{-(n+1)}} \\ &\lt& \left( \left( (P_n + 1)^3 - 1 \right) + 1 \right)^{3^{-n-1}} \\ &=& \left( (P_n + 1)^3 \right)^{3^{-n-1}} \\ &=& (P_n + 1)^{3^{-n}} \\ &=& v(n) \end{eqnarray} }$
（証明終）

補題 3 から $u(n)$ が狭義単調増加であることが従います．また， $u(n) \lt v(n)$ かつ $v(n)$ は狭義単調減少なので， $u(n)$ は上に有界であり，極限値を持ちます（Weierstrass の定理）．

いま， $A = \lim_{n \to \infty} u(n)$ とすると， $u(n) \lt A \lt v(n)$ であり，
${P_n}^{3^{-n}} \lt A \lt (P_n + 1)^{3^{-n}}$ ，
すなわち，
$P_n \lt A^{3^{n}} \lt P_n + 1$
であるため， $[A^{3^{n}}]$ は任意の $n \in \mathbb{N}$ について素数となります．

Mills 定数，Mills 素数

さて，上の証明で存在性を確認できた $A$ ですが，具体的な値はどのようになっているかというと，実は不明です．しかしながら，Riemann 予想が真であると仮定すると，
$A \simeq 1.30637788 \ldots$
であることがわかっています*3．これを Mills 定数といいます．

この $A$ に対して，実際に $[ A^{3^n}]$ を計算すると，
$[ A^{3^1}] = 2$
$[ A^{3^2}] = 11$
$[ A^{3^3}] = 1361$
$[ A^{3^4}] = 2521008887$ ……
となります．これらが全て素数であることは容易に確認できます．こうして出てくる素数を Mills 素数と呼ぶそうです．以降の値については A051254 - OEIS を参照してください．当たり前ですが，べき乗のべき乗なので $n$ の増加に従って $A^{3^n}$ は爆発的に増大します．

*1: Prime gap - Wikipedia などを参照してください．実際は $\theta = 5/8$ より精度の良い近似が判明していますが，今回はこれで十分です．

*2: $K$ の値は今のところ判明していないそうです．

*3:A051021 - OEIS を参照してください．

2019-11-14

数学検定 1 級を受けてきました

資格試験数学

はじめに

10/27（日）の第 344 回数学検定を受けてきました．結果は 1 次試験合格，2 次試験不合格でした．

勉強

前々日と前日に合わせて 15 時間ほど問題演習をやっただけです．1 次試験合格に 15 時間かかったので 2 次試験と合わせると 30 時間の勉強が必要ということですね（？）．

当日

列車で 2 時間半ほどかけて受検会場まで移動しました．こいつ資格試験の度に長時間移動してんな……．

1 級と準 1 級が同じ部屋で，1 級の受検者はぼくを含め 4 人だけだったと記憶しています．1 級の方は年上ばかりでしたが，準 1 級の方には小学生か中学生っぽい人もちらほらいてびっくりしました．

1 級の時間配分は 1 次が 60 分，2 次が 120 分です．途中に 20 分の休憩があります．そしてこれは本当に大事なんですが，腕時計の持ち込みが可能でした．Web サイトや受検票には持ち込みが可能だとも持ち込む必要があるとも一切書いていないのですが，受検時になってサラッと「腕時計をお持ちの方は机の上に置いてください」と言われます．罠すぎる．会場には時計がなかったので時間確認ができず死にました．

問題構成と概要・感想を書いておきます（長いので折りたたみ）．

1 次：

2 次：

対策

1 次試験：

時間が 60 分しかないため，1 問あたりおよそ 8 分で解かなければなりません．ボーダーは 7 割，つまり 5 問とれれば合格になります．

問題のレベルは，高専や大学般教である程度数学をやってきた人ならそこまででたらめに高いとも言えません．各問ごとにばらつきがあるため全てがそうではないのですが，たとえば今回なら行列のランクを求めさせるものとか，明らかに自明なものもある，くらいの難易度です．一方，まともに取り掛かっていては解けない問題もあります．今回でいうと 4 乗和の公式が必要な問題がそれでしょう．したがって，1 次をパスするためには，以下の 3 点が肝要になります．

時間内に正確に計算できること．計算ミスをしないこと．
ギリギリ解けるか解けないかレベルの問題をだいたい取れること．
時間内には解けない問題から潔く撤退できること．

今回は 1 問目を落とし，2 問目で複素 sinh と複素 sin を同一視するという最悪のミスをやらかしたんですが，他が全部取れてたようで通りました．リカバーを考えると，完全に捨てる問題は 1 問のみにすべきでしょう．

2 次試験：

敗軍の将兵を語らずと言いますが語ります．

2 次試験は 1 次と変わって 2 時間割りあたっています．問題数は 4 問（選択 2 + 必答 2）なので，1 問に 30 分かけられる計算です．ボーダーは 6 割なので，3 問 or 2 問 + 部分点で通るみたいです．

ここで要求されるのは，正確でよどみない証明を思いつく発想力，その証明をうまく解答用紙に収められる筆力，そしてわからない問題でもわからないなりに誤魔化せる部分点乞食力になります．

それと，選択問題にいくつかほとんど自明な問題が転がっているんですが，その分野の基礎知識がないと選択できずに憤死することになるので，ある程度広く浅く公式類を暗記しておくことをおすすめします．

所感

今回はまともに勉強していなかったのでまあ当然の結果だとは思います．2 次試験の採点がどんな感じなのか，詳細な結果通知を待ってまた考察する予定です．

情報処理技術者試験なんかとは違って 1 次試験の合格が引き継げるので，次回受けることがあれば 2 次試験対策を集中的にやって合格したいですね．

2019-11-05

区分求積法を使った極限計算

数学

こないだ，ある試験で以下の極限を求めさせる問題が出ました．

$\displaystyle{ \lim_{n \to \infty} \frac{n + 1}{(n!)^{1/n}} }$

解いたあと，「これはむずいやろ．解けた人少ないだろうし Twitter で話題になってるんじゃないかな」とか思ったんですが，仄聞するところによると Stirling の公式を使えば一発らしいです．でもそんな公式覚えてないですよね．
この問題は対数を取って巧妙に式変形することで区分求積に持ち込めます．

$\displaystyle{ \begin{eqnarray} \log \frac{n + 1}{(n!)^{1/n} } &=& \log (n+1) - \log (n!)^{\frac{1}{n}} \\ &=& \log(n+1) - \frac{1}{n} \log n! \\ &=& \log (n+1) - \frac{1}{n} \left\{ \log n (n - 1) \cdots 1 \right \} \\ &=& \log(n+1) - \frac{1}{n} \sum_{k = 1}^{n} \log k \\ &=& \log(n + 1) - \frac{1}{n} \sum_{k=1}^{n} \log \frac{k}{n} n \\ &=& \log(n+1) - \frac{1}{n} \sum_{k = 1}^{n} \left( \log \frac{k}{n} + \log n \right) \\ &=& \log(n+1) - \log n - \frac{1}{n} \sum_{k = 1}^{n} \log \frac{k}{n} \\ &=& \log \left( 1 + \frac{1}{n} \right) - \frac{1}{n} \sum_{k = 1}^{n} \log \frac{k}{n} \\ &\to& - \int_{0}^{1} \log x dx \; \; (n \to \infty) \end{eqnarray} }$

最後の積分は $0\log 0 = 0$ を認めたら（認めるというか l'Hôpital の定理とか使って計算したら） $-1$ になりますから，前に出てる負号と合わせて極限値は $1$ になります．

最初に対数を取っていたので戻すと，

$\displaystyle{ \lim_{n \to \infty} \frac{n + 1}{(n!)^{1/n}} = e }$

を得ます．う～ん，エレガント．

というわけで，Stirling の公式を覚えてなくてもこれは解けるよ，という話でした．こういうのを短い試験時間中に考えつくのは難しいかもしれませんが，類題をやっておけば思い浮かぶかもしれません．たとえば，階乗を見たらとりあえず対数を取ってみるというのは指針として有効だと思います．

2019-10-12

Schoof のアルゴリズム

数学情報技術

1. はじめに

今後書く予定の ECPP に関する記事*1の前準備としてしたためました．

2. 理論

有限体 $\mathbb{F}_q$ 上で定義される楕円曲線 $E: y^2 = x^3 + ax + b$ の Abel 群を考えます． $\# E(\mathbb{F}_q)$ ，すなわち $E$ の $\mathbb{F}_q$ -有理点の数をうまく数えるのが目標です．

Schoof のアルゴリズムは楕円曲線の位数計算アルゴリズムとしてよく使われるものになります．これは中国人剰余定理（CRT）に立脚しています．

Hasse の定理

$E/\mathbb{F}_q$ を $\mathbb{F}_q$ 上で定義された楕円曲線とすると， $\mid \#E - (q + 1) \mid \le 2 \sqrt{q}$

この定理は何を言っているかというと， $E$ はだいたい $q - 1$ 個くらいの点を持っており，誤差は $\pm 2 \sqrt{q}$ くらいに収まる，ということです．

しかしいまは $\# E$ を正確に求めたいので，この定理で満足するわけにはいきません．それでも，この Hasse の定理をテコにして考える，ということが楕円曲線関連ではよく行われます．

たとえば，Legendre の記号を使って考えると，

$\displaystyle{ \# E = 1 + \sum_{x \in \mathbb{F}_q} \left\{ 1 + \left( \frac{f(x)}{q} \right) \right\} = 1 + q + \sum_{x \in \mathbb{F}_q} \left( \frac{f(x)}{q} \right) }$

であり，

$\displaystyle{ \sum_{x \in \mathbb{F}_q} \left( \frac{f(x)}{q} \right) \le 2\sqrt{q}}$

が成り立ちます．そしてこのような総和は平方剰余の相互法則を使ってうまく計算できます．これは位数計算アルゴリズムとしてはもっとも簡単なものです．

もう一つ用語を導入しておきましょう．

Frobenius 写像

$\phi : (x, y) \to (x^q, y^q)$ を Frobenius 写像と呼ぶ．Frobenius 写像のトレースを $t = q + 1 - \# E(\mathbb{F}_q)$ によって定める．

この辺の議論も面白いんですがここに書くと脱線するので気になる人は AEC とかを読んでください．

Schoof のアルゴリズムのアイデアは小さな $l_1, l_2, \cdots , l_i, \cdots$ に対して $t \bmod l_i$ を計算し，CRT と Euclid の互除法から $t$ を復元することにあります．どのくらいの $l_i$ について見ればいいかというと，

$\displaystyle{ \prod_{2 \le l_i \le l_{\mathrm{max}}} l_i > 4\sqrt{q}}$

を満たすような最小の $l_{\mathrm{max}}$ まででよく，このとき用意すべき素数の個数は，素数定理より $\log q / \log \log q$ くらいで与えられます．

$t \bmod l_i$ を計算するさいのこまごまとしたテクニックにはここでは触れません．実装もやりません．

Schoof のアルゴリズムのすごい点は，これが初の多項式時間位数計算アルゴリズムであることです．時間計算量は $O( (\log q)^8 )$ だそうです．現在では $l_i$ を Elkies 素数と Atkins 素数に分類することで高速化を図った Schoof-Elkies-Atkin 法が使われます．

*1:書かないかもしれません．

2019-08-29

級数の収束判定について（『大学編入試験問題数学/徹底演習』）

数学

『大学編入試験問題数学/徹底演習』の解答のちょっと怪しいとこ（別名：単位円ぐるぐる問題*1）について書きます．

$\displaystyle{ \theta \in \mathbb{R} }$ に対して $\displaystyle{ f(x) = \sum_{n = 1}^{\infty} \frac{\sin n \theta}{n} x^n }$ とおく． $f(x)$ が $|x| \lt 1$ で収束することを示せ．

（埼玉大理学部，一部改変）

この問題に対し，上掲書では d'Alembert の収束判定法を利用しています．

$\displaystyle{ \begin{eqnarray} \lim_{n \to \infty } \left| \frac{ \sin n \theta}{n} \frac{n+1}{\sin (n + 1) \theta} \right| &=& \lim_{n \to \infty} \left| \frac{e^{in\theta} - e^{-in\theta}}{e^{i(n+1)\theta} - e^{-i(n+1)\theta} } \right| \frac{n+1}{n} \\ \\ &=& \lim_{n \to \infty} \left| \frac{e^{-i\theta} - e^{-i(2n+1)\theta}}{1 - e^{-2i(n+1)\theta} } \right| \left( 1 + \frac{1}{n} \right) \end{eqnarray} }$

ここまではまあよいでしょう．問題はこの次です．上掲書の解答ではここから直接

$\displaystyle{ = | e^{-i\theta} | \cdot 1 = 1}$

としています．これはちょっと（というか相当）怪しいです．おそらく $n \to \infty$ で $e^{-i(2n+1)\theta} \to 0$ とかを言いたかったのでしょうが， $e^{-i(2n+1)\theta}$ は単位円上の点なので， $n$ をどう動かそうとエンドレスに単位円をぐるぐるしつづけるだけで，収束しません*2．なにか約分っぽいことができたら話は別ですが．

対応

単純に上から抑えましょう．

$\displaystyle{ \begin{eqnarray} f(x) &=& \sum_{n = 1}^{\infty} \frac{\sin n \theta}{n} x^n \\ &\le& \sum_{n = 1}^{\infty} \left| \frac{\sin n \theta}{n} x^n \right| \\ &=& \sum_{n = 1}^{\infty} \left| \frac{\sin n \theta}{n} \right| \left| x^n \right| \\ &\le& \sum_{n = 1}^{\infty} \frac{1}{n} \left| x^n \right| \: \: (\because | \sin n \theta | \le 1, \: n > 0 ) \\ &\le& \sum_{n = 1}^{\infty} \left|x \right|^n \end{eqnarray} }$

$\sum |x|^n$ が $|x| < 1$ で収束することより， $f(x)$ も同様の範囲で収束すると言えます．

所感

ふつうこんなミスがあるとはちょっと考えづらいので，あるいは私の読み間違いかもしれません．だとしても記述不足かなーと思います（行間を読む限りでは上に述べたような解釈しかできないので）．
この問題について，最初に述べた（掲載されてた）解法で合ってるとか，もっといい解き方があるとか，何かしら知見のある方はコメントいただけるとうれしいです．

*1:自分が勝手に名付けました．

*2:~~愛（ $i$ ）があると事態が複雑になるというわけです．~~

2019-08-04

集合と位相 1: 有限集合

数学

これをやっていきます．今回は超あっさりです．

ある $n \in \mathbb{N}$ から定まる $\{1, 2, \ldots , n\}$ との間に全単射を持つ集合は有限集合と呼ばれます．この $n$ を集合の濃度と呼びます．濃度は unique かつ加法的です．

有限集合の濃度については鳩の巣原理という有名な事実が成り立ちます．2つの有限集合 $X, Y$ について， $\# X = \# Y$ ならば，任意の $F: X \to Y$ に対して $F$ が単射であることと $F$ が全射であることとは同値です．鳩の巣で言い換えるとこうなります：鳩の数と巣の数が等しいとき，どの巣にも鳩がいれば，たかだか1羽ずつしかいない．