数学検定 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)があると事態が複雑になるというわけです.

集合と位相 1: 有限集合

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

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

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

次回以降で扱う無限集合では,この鳩の巣原理をテコにして話を進めます.

数学の基礎に入門したい

1月にやった制御工学が(自分としては)結構はかどったので,同様の形式で,都度学習内容をブログにまとめつつ,数学の基礎的なところをやってみようと思います.幸い試験も終わったし.

教科書には『数理基礎論講義―論理・集合・位相』を使います.

扱う内容は教科書だと「第10章 無限集合論」から「第17章 一様位相と収束」までに相当します.これより前の述語論理とかにも手を出してみたいんですが.まあ時間と相談しつつ考えます.

パラパラとめくってみた感じだと前回ほどテンポよく行かなそうですね.いつまでかかるかちょっと不透明です.夏休みいっぱい使うかもしれないし,(ぼくのことなので)途中で更新が途絶えてしまうという可能性も大いにあります.まあ頑張っていきましょう.

この記事はとりあえずやるぞーっという宣言だけして終わりです.明日から本気出す.

「晩年のエジョフが妻を粛清した」という誤解について

そもそも

ニコライ・エジョフ(Nikolai Yezhov)はソ連の政治家です.スターリン大粛清を行った時期(1937年前後)に NKVD(内務人民委員部)のトップとして絶大な権力を握り,大粛清の実行役を務めました.

彼は大粛清の暗鬱で陰惨なイメージと常にセットで語られます.1937~1938年はエジョフシチナ(エジョフ時代)と呼ばれ,嫌悪されています.しかしながら,大粛清の究極的な責任はあくまでスターリンにあることが研究を通してかなり明らかになってきています.

エジョフが言及されるときの頻出エピソードが,「晩年は疑心暗鬼が高まり自分の妻をも粛清した」というものです.たとえば,Wikipedia 日本語版には,

連日のように粛清を繰り返したエジョフは、晩年には疑心暗鬼となって側近や家族まで疑うようになり、自身の妻までも粛清している。

― ニコライ・エジョフ - Wikipedia 日本語版(閲覧:2019年8月2日)

とあります.しかしながら,「疑心暗鬼となって……自分の妻までも粛清している」というのはほとんど嘘です.にもかかわらず,「大粛清を実行した狂気の人間」というイメージとうまく合致するためか,(少なくとも日本のインターネットにおいては)かなり多く言及されています.この誤解を解くため,晩年のエジョフとその妻について記しておきます.なお,以下の記述はほぼサイモン・セバーグ・モンテフィオーリ『スターリン―赤い皇帝と廷臣たち』に依拠しています.

いきさつ

先述した通り,エジョフは大粛清の実行役でした.しかしながら,1938年に入ったころ,「反動分子の摘発があまりにも雑すぎて国家運営に支障を来している」といった理由から,スターリンの不評を買うようになってきます.これには,そろそろ大粛清をやめたいと考えていたスターリンの意向や,エジョフの地位を狙っていたベリヤ(Lavrentiy Beria)の根回しも関係しています.

ともかく,エジョフは1938年中旬以降ほとんど失脚します.同時に,エジョフの妻であるエヴゲーニャ(Yevgenia Yezhova)もきわめて危険な地位に追い込まれました.エヴゲーニャは性的に奔放な女性で,ソ連の文学サロンに出入りしては男遊びを繰り返していました.ちなみに,彼女と性的関係のあった作家や詩人はこの後ほとんど死にます.

エヴゲーニャにはロンドン滞在の経験がありました.これを利用し,彼女をイギリスのスパイとして告発しようと策動したのが先述のベリヤです.エジョフはこの工作を知り,エヴゲーニャに離婚を申し出ました.注記しておきたいんですが,これはエジョフの利己的な考えから出た行動ではありません.当時,離婚によって夫婦セットでの粛清を避けるのは有効な防衛手段だったからです.

しかしながら,エヴゲーニャはこれらの政治的危機に耐えられず,精神を病んでいきます.妻を粛清の魔の手から守ろうとするエジョフの工作もあり,彼女はクリミアへ休養に出かけることとなります.このとき彼女がエジョフに書き送った手紙が残っています.

コリューシェンカ![引用者注:エジョフの愛称.「コーリャ」も同じ] ……私の心からの願いは……自分の人生の主人公でありたいということです。愛しいコーリャ! ……自分が犯してもいない罪の疑いをかけられては,到底生きていかれません……

エジョフの友人や秘書たちが続々と逮捕され,エジョフとエヴゲーニャにかけられた首縄が徐々に締まりつつあるなか,エヴゲーニャはうつ病の診断を受け,モスクワ近郊のサナトリウムに入院しました.彼女はスターリンに絶望的な調子の手紙を書きます.

私は生きる屍のような気持ちです.一体どうすればいいのでしょう?

しかし,スターリンからの返事はありませんでした.そうしているうちにも,エジョフとエヴゲーニャはどんどん危険な地位に追いやられていきます.政治局はエジョフの膝下であった NKVD について「きわめて重大な欠陥があった」と非難する決議を採択しました.

絶望したエヴゲーニャはついに自殺を決意し,エジョフに睡眠薬を送ってほしいと懇願します.エジョフは妻の頼みを聞き入れ,致死量の睡眠薬を病院に送り届けました.エヴゲーニャが睡眠薬を過剰摂取して昏睡に陥ったのは1938年11月19日,死去したのは11月21日のことです.

 

このエヴゲーニャの最期から分かることはなんでしょうか.

少なくとも,エジョフがエヴゲーニャを粛清したとは到底言えません.エジョフに「性的スキャンダルのつきまとう妻を生かしておくと自分の身も危うい」みたいな保身的考えが無かったと断言することはできません.しかし,エジョフが妻を explicit に粛清したと見ることは不可能です.生きる望みを失ったエヴゲーニャの頼みを聞き入れ,睡眠薬を送ったエジョフの行為は,優しさとか愛とかの表れでこそあれ,疑心暗鬼の発露ではないはずです.

由来

そもそも「晩年のエジョフが妻を粛清した」という情報はどこ由来なのでしょうか.先に引用した Wikipedia の記述にはソースが明記されていません.ちょっと謎です.1991年以前の史料が入手困難な時代にこういう推測がなされていたという可能性はありますね.とにかく気になるところです.どなたかご存知ありませんか.