2021-01-27

（線形代数・復習）基底の行き先を与えると対応する線形写像が一意に存在する

数学線形代数

最近、「リーマン面」の勉強が「微分形式」の章に差し掛かりました。接ベクトル空間という線形空間や、その双対空間が出てきてまさに線形代数になっています。そんなわけで線形代数の復習として、以下の事実を示したいと思います。

斎藤毅先生の「線形代数の世界」の命題2.13から。

命題2.13（斎藤「線形代数の世界」）

$V, W$ を $K$ -線形空間とする。 $\{x_1, \ldots, x_n\}$ を $V$ の基底とし、 $y_1, \ldots, y_n \in W$ とする。

このとき、線形写像 $f\colon V \to W$ で、 $f(x_1) = y_1, \ldots, f(x_n) = y_n$ を満たすものがただ一つ存在する。

まずは、主張の確認をしていこうと思います。 $V$ は線形空間なので、基底というベクトルの組 $\{x_1, \ldots, x_n\}$ がとれます。これによって、任意のベクトル $x \in V$ は

$x = a_1 x_1 + \cdots + a_n x_n$ （ $a_1, \ldots, a_n \in K$ ）

のように一意的に表せるわけですね。

さて、 $V$ から $W$ への線形写像というのは、任意の $V$ の元 $x$ に対してその値 $f(x)$ が定められていて、かつ、線形性なる条件を満たしているものです。

線形性とは、任意の $v, v_1, v_2 \in V$ と $k \in K$ に対して次が成り立つことを指します：

$f(v_1 + v_2) = f(v_1) + f(v_2)$
$f(k v) = k f(v)$

というわけで、本当はすべての $V$ の元に対して値が定まっていなければいけない。

しかしながら、線形性から

$\begin{align} f(x) &= f(a_1 x_1 + \cdots + a_n x_n) \\ &= f(a_1 x_1) + \cdots + f(a_n x_n) \\ &= a_1 f(x_1) + \cdots + a_n f(x_n) \end{align}$

が成り立ちますので、 $f$ は $x_1, \ldots, x_n$ というたった $n$ 個のベクトルに対してその行き先が決まっていれば、あとは自動的に決まってしまうのです。まさに線形性のマジックという感じがします。

ここで気になるのは、基底の行き先として $y_1, \cdots, y_n$ を予め与えたときに、対応する線形写像 $f$ は存在するのか、という問題です。存在すれば一意なので対応する線形写像が存在するかどうかが焦点となります。

f:id:tsujimotter:20210127142041p:plain:w500

もちろん、単に「写像」というだけであれば、行き先はいくらでも決められるので必ず存在します。一方で「線形写像」に限定したときに存在するかというのは明らかではありません。そのような線形写像が存在することを保証するのが命題2.13の主張なわけですね。単に存在するだけでなく、証明の中では対応する線形写像を実際に構成します。

2021.01.27修正：
主張の内容を思い切り勘違いしていましたので、記事公開後に修正しました。

元々は「線形写像は基底の行き先だけで決まる」という内容にしていたのですが、（もちろんそれも事実としては正しいのですが）命題2.13の主張としては「基底の行き先を任意に与えると、それに対応する線形写像が存在する」の方がポイントだったわけですね。

タイトルもミスリーディングなので変えます。

対応する線形写像が存在することの何が嬉しいのでしょうか。線形写像 $V$ から $W$ への $K$ -線形写像全体を具体的に考えるときに、この命題が助けになりそうです。実際、双対空間と呼ばれる「 $V$ から $\mathbb{C}$ への線形写像全体のなす $\mathbb{C}$ -線形空間」の基底を求めるのにこの命題を使うのですが、長くなりそうなのでまた別の機会に紹介したいと思います。

2021-01-23

UFD限定「オイラーの素数生成多項式」の証明

数学素数整数論素数と２次体の整数論オイラーの素数生成多項式

今日は「オイラーの素数生成多項式」についての話です。

f:id:tsujimotter:20210123230219p:plain:w400

この多項式に $X = 0, 1, \ldots, 39$ を代入した数はなんとすべて素数になることが知られています。

$f(0) = 0^2 + 0 + 41 = 41$ （素数）

$f(1) = 1^2 + 1 + 41 = 43$ （素数）

$f(2) = 2^2 + 2 + 41 = 47$ （素数）

$\vdots$

$f(39) = 39^2 + 39 + 41 = 1601$ （素数）

$X = 40$ を入れると $f(40) = 40^2 + 40 + 41 = 41^2$ となって合成数になってしまいます。しかしながら、それまでの実に $40$ 個もの間、素数が出続けるという驚異の多項式となっています。

この多項式の一般化として、 $q$ を $2$ 以上の自然数として

$f_q(X) = X^2 + X + q$

というものを考えます。

これが素数生成多項式であること、すなわち

整数 $0 \leq X < q-1$ に対して $f_q(X) = X^2 + X + q$ は素数

の必要十分条件は

$1-4q$ が平方因子を持たない
かつ
虚2次体 $\mathbb{Q}(\sqrt{1-4q})$ の類数が $1$ であること

であることが知られています。これは驚くべき事実ですね。

$1-4\cdot 41 = -163$ は平方因子を持たず、なおかつ、虚2次体 $\mathbb{Q}(\sqrt{-163})$ の類数が $1$ であることが知られているので、ここからただちにオイラーの多項式 $f_{41}(X) = X^2 + X + 41$ が素数を $40$ 連続で生成することがわかりますね。面白いです。

この一般的な事実の証明については、以前のブログ記事でもまとめたことがありました：
tsujimotter.hatenablog.com

しかしながら、証明はかなり難解であり、特にイデアルに慣れていない人にとってはアクセスしづらいものであったと思います。

一方で、主張の片側だけであれば、すなわち

$1-4q$ が平方因子を持たないかつ $\mathbb{Q}(\sqrt{1-4q})$ の類数が $1$
$\;\; \Longrightarrow \;\;$ 整数 $0 \leq X < q-1$ に対して $f(X) = X^2 + X + q$ は素数

に関して言えば、前提知識がかなり少なくても済みそうです。実際、イデアルをまったく使わなくても証明を行うことができます。

使うのは、2次体がUFD（一意分解整域）のときの「有理素数の素元分解法則」だけです。これだけ認めてしまえば、虚2次体についての少しの知識があれば、十分に証明を追うことができるようになります。

私は、オイラーの素数生成多項式は、もっと多くの人たちが興味を持ってもらえる対象だと思っていまして、ぜひ2次体の整数論への入り口として、この証明に興味を持っていただければと思います。

2021-01-22

mod mのべき乗余が何通りの値を取るかという話

数学整数論中国剰余定理

１つ前の記事に関連して「 $a^{k} \pmod{m}$ がどんな値をとるのか」という問題が気になりました。
tsujimotter.hatenablog.com

上の記事では

$k = \varphi(m)+1$ のとき $a^{\varphi(m)+1} \equiv a \pmod{m}$
$k = \lambda(m)+1$ のとき $a^{\lambda(m)+1} \equiv a \pmod{m}$

となる、つまり $a = 0, \ldots, m-1$ の全ての値を取ることを示しました。鯵坂もっちょさんの可視化の方法を用いるならば、右肩上がりの階段状になります。

f:id:tsujimotter:20210122201425p:plain:w400

（横軸が $a$ で、縦軸が $a^7 \pmod{42}$ となっています）

「 $a$ が $m$ と互いに素であるかどうかに関わらず」このようになるというのが面白かったわけですね。

一方で、 $k = \varphi(m)$ 乗した場合については、特に法則はなさそうに見えました。何か法則はあるのでしょうか。

そんなことを考えているうちに、青山学院大学の中川貴仁さんの卒論研究を見つけました。

整数のべき乗とオイラーの定理について
中川貴仁（西山研究室）
http://www.gem.aoyama.ac.jp/~kyo/sotsuken/2014/nakagawa_sotsuron_2014.pdf

中川さんの論文によると、 $m$ が相異なる $r$ 個の素数の積で表されるとき、すなわち

$m = p_1 p_2 \cdots p_r$

のとき、 $a^{\varphi(m)} \pmod{m}$ の値は $2^r$ 個通りの数をとるそうなのです。

$a$ が $m$ と互いに素のときは、オイラーの定理により $a^{\varphi(m)} \equiv 1 \pmod{m}$ ですから、常に $1$ の値をとります。上の話は、 $a$ が $m$ と互いに素とは限らないときも含めて、何パターンの値を取りうるかを教えてくれます。

そんなことが証明できるのですね。大変面白かったので、証明を紹介したいと思います。

2021-01-22

「互いに素でない場合」のオイラーの定理

数学整数論

$m$ を正の整数としたとき、 $a$ を $m$ と互いに素な任意の整数として

$a^{\varphi(m)} \equiv 1 \pmod{m}$

が成り立つことが知られています。 $\varphi(m)$ はオイラーのトーシェント関数といって、この合同式はオイラーの定理として知られています。

これは素数を使った有名な暗号の一つ「RSA暗号」の理論的背景に使われます。具体的には、 $m = pq$ として考えますが、 $\varphi(m) = (p-1)(q-1)$ となります。上の定理から

$a^{k(p-1)(q-1)+1} \equiv a \pmod{m}$

という合同式が成り立ちます。これを使うと、任意の $s$ に対して $t$ が存在して

$a^{st} \equiv a^{k(p-1)(q-1)+1} \equiv a \pmod{m}$

が成り立つ事が言えます（ユークリッドの互除法を使います）。したがって、 $s$ を暗号鍵、 $t$ を複合鍵とすれば、 $a$ を暗号化してまた戻してくる事ができるというわけですね。

以下の記事でより詳しく説明しました：
tsujimotter.hatenablog.com

ところで、意外にあまり明示的に書かれていない事実として、 $a$ が $m = pq$ と互いに素でなくても

$a^{\varphi(m)+1} \equiv a \pmod{m}$

は成り立ちます。つまり、暗号文を選ぶ時に、わざわざ $m$ と互いに素であるかどうか気にしなくて良いというわけですね。

ちなみに、上が成り立つからといって両辺を $a$ で割った

$a^{\varphi(m)} \equiv 1 \pmod{m}$

は一般に成り立ちません。両辺を割ることができない場合があるというのが、合同式の面白いところです。

2021-01-21

素数生成多項式と虚2次体の類数 (2)

数学素数整数論オイラーの素数生成多項式

昨日は、オイラーの素数生成多項式に関して「私の発見」を紹介させていただきました。
tsujimotter.hatenablog.com

執筆時は、この研究の先行研究にあたるものを発見できず、「先行研究はあるかわからないが独自にこんな発見をした」というスタンスを取っていました。しかしながら、やはり探せばあるものです。

このブログでも何度かお世話になっている木村巌先生より、2件ほど教えていただきました。私自身の力で見つけることができなかったので、大変ありがたいお話です！

[1]
On a lower bound for the class number of an imaginary quadratic field
[2]
An inequality between class numbers and Ono's numbers associated to imaginary quadratic fields

この様子だと他にも類似の研究はありそうです。勉強になります。

もちろん、私の記事と完全に同じ結果というわけではありません。私の記事と先行研究 [1][2] の違いをまとめると、次のようになります。

tsujimotter： $0\leq X \leq q-2$ の範囲において $f(X) = X^2 + X + q$ が素数を生成する確率に着目
先行研究[1][2]： $0\leq X \leq q-2$ の範囲において $f(X) = X^2 + X + q$ の素因数の個数（特に $0\leq X \leq q-2$ の範囲で個数が最大のもの）に着目

実は素因数の個数に着目すると、後半で示すように非常に明快な関係が得られるのです。この辺は問題の定式化のセンスを感じますね。私には思いつかないアイデアでした。

というわけで、この分野の考え方に親しむためにも、特に先行研究の考え方と結果についてまとめてみたいと思います。

オイラーの素数生成多項式について、より基本的な事項を知りたい方は、まずはこちらの記事を読むのをお勧めします：
tsujimotter.hatenablog.com

2021-01-20

（独自研究）素数生成多項式と虚2次体の類数

数学自由研究・独自研究整数論素数オイラーの素数生成多項式

今回の記事は、素数がたくさん登場する多項式

$f(X) = X^2 + X+ 41$

に関連する話題です。今回は私がこの式について考えているうちに、思いついて実施してみた独自研究について紹介したいと思います。どこかの本に書いてある話ではないので、誤りを含んでいる可能性も大いにあるかと思います。また、十分な調査ができているわけではないので、独自性もはっきりとしていません。その点をご了承の上で読んでください。

今回の記事は発展的な内容になっています。オイラーの素数生成多項式について、より基本的な事項を知りたい方は、まずはこちらの記事を読むのをお勧めします：
tsujimotter.hatenablog.com

今回は論文を意識したフォーマットで書いているため、普段のブログ記事より内容が難しく、堅めの書き振りになっている点をご了承ください。また、虚2次体に関する基本的な知識を前提とします。

追記：2020.01.21
やはりといいますか、当然と言いますか、先行研究として類似のアイデアの研究はありました。勉強も兼ねてブログにまとめていますので、次の記事もぜひご参照ください：
tsujimotter.hatenablog.com

追記：2020.01.22
Proposition 1.の証明におきまして、 $p = 2$ の場合を適切に考慮し忘れていたため、その点を修正しました。Proposition 2. の証明に影響はありません。

1. Introduction

1772年、EulerはBernoulliに宛てた手紙の中で、素数を生成する2次多項式について述べている。すなわち、素数 $q$ に対し、

$f_{q}(X) = X^2 + X + q \tag{1}$

と定義すると、素数 $q = 2, 3, 5, 11, 17, 41$ に対し $f_q(X)$ に整数 $X = 0, \ldots, q-2$ を代入した値がすべて素数になることを発見した。これをオイラーの素数生成多項式という。

Rabinovitch (1913)は $f_q(X)$ が素数生成多項式である条件と、対応する虚2次体の類数が1である条件の間の同値性を示した。すなわち、 $q$ を任意の素数であるとき、 $f_{q}(X)$ が $X = 0, \ldots, q-2$ においてすべて素数になるための必要十分条件は、虚2次体 $\mathbb{Q}(\sqrt{1-4q})$ の類数が1であることである。

さらに、Baker (1966)やStark (1967)により、類数が1である虚2次体が独立に決定されており、その系として上記の条件を満たす $q$ は $q = 2, 3, 5, 11, 17, 41$ のときに限られる。

ここで、任意の素数 $q$ に対し、2次多項式 $f_{q}$ を考えて

$\displaystyle P_1(q) = \frac{\# \{ X \in \mathbb{Z} \mid 0 \leq X\leq q-2 \;\; \text{s.t.}\;\; f_{q}(X)\colon \text{prime} \} }{q-1} \tag{2}$

とする。 $P_1(q)$ を素数生成確率と呼ぶことにする。名前の通り、 $0\leq X\leq q-2$ に対して $f_{q}(X)$ が素数になる割合を表す。

また、虚2次体 $K$ に対しその判別式を $d_K$ としたとき、対応する類数を $h_{d_K}$ と表すことにする。このとき、Rabinovitchの定理は次のように言い換えられる。

Theorem 1 (Rabinovitch, 1913)

$q$ を任意の素数とすると、次が成り立つ：

$P_1(q) = 1 \; \Longleftrightarrow \; h_{1-4q} = 1 \tag{3}$

上記の定理は類数1と $P_1(q) = 1$ が同値という主張であるが、類数が2以上については $P_1(q) < 1$ が成り立つ以上のことは言及されていない。先行研究においても、このような観点に基づく研究はないように思える。

そこで本研究では、計算機により虚2次体 $\mathbb{Q}(1-4q)$ の類数 $h_{1-4q}$ を計算し、特に類数 $2$ 以上のケースにおける $P_1(q)$ の振る舞いを観察する。 $P_1(q)$ が類数 $h_{1-4q}$ に反比例するというヒューリスティックな仮定に基づいて分析したところ、少なくとも $q < 100000$ においては $f_q$ は予想より素数になりやすいという「バイアス」が存在することを発見した。

2021-01-02

「数体の素元星座定理」に関するプレプリントについて

数学整数論素数おすすめの記事プレプリント紹介

2021年に入ってすぐに、とんでもないニュースが飛び込んできました。もちろん、数学のニュースです。

東北大学の研究チームによる論文のプレプリントがarXivで公開されました。タイトルは "Constellations in prime elements of number fields" で、こちらのリンクからアクセスできます：

Constellations in prime elements of number fields
Wataru Kai, Masato Mimura, Akihiro Munemasa, Shin-ichiro Seki, Kiyoto Yoshino
https://arxiv.org/abs/2012.15669

Wataru Kai, Masato Mimura, Akihiro Munemasa, Shin-ichiro Seki, Kiyoto Yoshinoの5名により発表されたプレプリントです。著者の一人であるShin-ichiro Seki（関真一朗）さんの名前は、今回の記事で何度か登場します。

上記の原稿はプレプリントですので、査読がなされたわけではありません。したがって、証明されたかどうかを確認するためには、自分で証明を読み込んで確認するほかありません。

普段、このようなプレプリントはなるべく紹介しないようにしているのですが、今回ばかりはどうしてもブログでご紹介したくなりました。というのも、証明されたとされる結果があまりにすごいからです！

英語で書かれた論文ですが、主定理の名称を日本語でいうなら

「数体の素元星座定理」

ということになります。いかにも興味をそそられる内容ですよね！

この「数体の素元星座定理」なる日本語訳については、関真一朗さんご自身のツイートから拝借させていただきました。