2019年を振り返って

カレンダー

1月

なぜか制御工学の勉強を始めた.あと大阪・京都へ旅行に行ったりした.他は何をやってたかまるで覚えてない.

2月

ひたすら数学をしていた記憶がある.AEC をテコに楕円曲線やその暗号理論への応用を勉強した.

3月

コンフェスに出て,優勝した.あとは……(何も思い出せない)

4月

進級.本を読んだり数学をしたりしていた.

5月,6月,7月

本を読んだり数学をしたりしていた.この辺本当に何もやっていない.

8月

東工大オープンキャンパスに行ったり,神保町行ってはしゃいだり,まあそんな感じだった.受験勉強はしていない(最悪)

9月

大阪と奈良に行ってはしゃいだ.相変わらず受験勉強は……

10月,11月

虚無

12月

虚無

 

反省しかない.

 

読んだ本

今年は昨年比でかなり読書量が減った.

こうして並べてみると,一つ一つの本を読んでいた当時のことを思い出して感慨深い.

今はアルベルト・アンジェラ『古代ローマ人の愛と性』と入江昭『日本の外交』をちょっとずつ読んでいる.

上に挙げた中では,丸山眞男超国家主義の論理と心理』,オーウェルオーウェル評論集(2)』,岡義武『近衛文麿』『山県有朋』,会田雄次『アーロン収容所』,ワイルド『ドリアン・グレイの肖像』あたりが面白かった.どれもよく知られた名著であり,自分がくどくど書くこともないと思う.岡義武についてはかつて岩波新書に入っていたものが最近文庫化されており,入手しやすくなっている.同氏の『近代日本の政治家』も購入してあり,読むのを楽しみにしつつ積んでいる.

それから今年は 4 月から『日経サイエンス』を購読しはじめた.理系の教養を身につけ,最近の研究情勢をある程度把握しておくためである.これがなかなか面白かった.非専門家でも分かるように書いてあり,ためになる.毎月 25 日が楽しみになった.学生は 1 冊 1000 円程度で購読できる.オススメしたい.

また,研究を通じて英語論文を読む機会が昨年と比して劇的に増えたように思う.アカデミックリーディングのスキルも多少鍛えられたのではないか.最近 TOEIC IP を受けたが,1 年前と比べて解ける問題が確実に増えていた.まだまだお恥ずかしいレベルではあるが,こうして実力の向上を体感できるのは嬉しい.

「害する」と「損なう」

以下の質問を見て考えた.

hinative.com

当該ページには「主客の違いである(要約)」という回答がついているが,これは正しくないと思われる.「過労で健康を害した」「不用意な発言で感情を損なう」はどちらも正しい(共に明鏡国語辞典第二版).

つづめて言えば「害する」と「損なう」の間に大した違いはない.日本語ネイティブでも両者を意識して使い分けている人間は稀ではないか*1

それでも一応,わずかな用法の違いはあるらしい.広辞苑第六版では,「害する」は

がい・する【害する】

〘他サ変〙

(文)害す(サ変)

①きずつける.そこなう.「健康を―・する」「感情を―・する」

②殺す.殺害する.今昔物語集(9)「虎を―・せむとする時に」

③じゃまをする.さまたげる.森鴎外大塩平八郎「北手の展望を―・する梅の木を伐(き)ること

となっている.一方の「損なう」については

そこな・う【損なう・害う】ソコナフ

〘他五〙

①物をいためる.傷つける.完全なものを不完全にする.土佐日記「けふいくか,はつか,みそかとかぞふれば,およびも―・はれぬべし」.仮名草子,伊曽保物語「いばらの中へおつこうで,手足をかやうに―・ふ事,何の戯れぞや」.「器物を―・う」

②危害を加える.殺傷する.神代紀(上)「性―・ひ害(やぶ)ることを好みたまふ」.源氏物語(須磨)「高潮といふ物になむ,取りあへず人―・はるるとは聞けど」

③物事を悪い状態にする.害する.源氏物語(柏木)「久しう煩ひ給ふ程よりは,殊にいたうも―・はれ給はざりけり」.源氏物語(常夏)「額のいと近やかなると,声のあはつけさとに―・はれたるなめり」.日葡辞書「イロヲソコナウ」「キゲンヲソコナウ」.「友好関係を―・う」

④(他の動詞の連用形に付いて)

 ア:…することに失敗する.間違えて…する.天草本平家物語三井寺には長僉議をして,夜を明かいて夜討ちをし―・うて」.「文字を書き―・う」「球を受け―う」

 イ:機会を逸する.「昼食を食べ―・う」

と書かれている*2

用法別にまとめてみると,

(感情・関係などの無形物を)傷つける,不完全にする 両方
(実体のある物を)傷つける 「損なう」のみ
(人・動物を)殺害する 両方
(人・動物を)傷つける 「損なう」のみ
じゃまをする 「害する」のみ
動詞の連用形について「…することに失敗する」などの意味を出す 「損なう」のみ

という感じか.国語辞典では不可避の相互参照が入っているのでなんとも言えないが…….

明鏡国語辞典では,「害する」の「じゃまをする」という意味について,「旱魃(かんばつ)が稲の生育を―」「権力の介入が構成な取引を―」などの例文を挙げている.こちらのほうが分かりやすいだろう.確かに「旱魃が稲の生育を損なう」とは言わない(気がする).既に稲が育っていて,それを傷つける,という意味なら「損なう」としてもよいだろうが.

 

また,意味や用法の違いの他に,言葉の雰囲気といった面での違いもある.冒頭に挙げたサイトには類似した質問があったのだが,

hinative.com

こちらでは "損なう is a little harder to use than 害する." という回答がついている.確かにこれはそうかもしれない.そもそも「損なう」より「損ねる」の方がよく使われるような気もする.

また,言葉のトーンについて言えば,「害する」は「損なう」よりも強い印象を与えるのではないか.「気分を害する」と「気分を損なう」では前者の方がより腹を立ててそう.

 

どうも途中から漠然とした感想ばかり書いて申し訳ないが,とにかく「害する」と「損なう」の違いはそんな感じである.

 

ちなみに,「損なう」は,上の広辞苑の定義からも分かる通り語幹が「そこな」である.したがって本来は「損う」と送るのが正しいが,それでは「損ねる」→「損る」と区別が付きづらいので,例外的に一文字送り仮名を増やすことになっている(この辺りのルールは内閣告示「送り仮名の付け方」を参照するとよい).

 

*1:ニュースピークが導入されたら真っ先に片方が無くなりそう.あるいは ungoodize で代用されて共に消えるか.

*2:例文が古典ベースなのは格調高くてかっこいいけど常用向きではないなあ.

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 を参照してください.

数学検定 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 次試験:

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

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

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

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

2 次試験:

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

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

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

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

所感

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

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

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

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

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

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:書かないかもしれません.

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

『大学編入試験問題 数学/徹底演習』の解答のちょっと怪しいとこ(別名:単位円ぐるぐる問題*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)があると事態が複雑になるというわけです.