二次形式の類数を求めるプログラム - tsujimotterのノートブック

今回お話ししたいのは「正定値二次形式の判別式 $D$ に対して，類数 $h(D)$ を計算する Ruby のプログラムを作った！」という話です。

なのですが，この分野を知らない人にとっては上の文章はサッパリですね。「二次形式ってなに？」「判別式ってなに？」「類数って・・・？」と，疑問でいっぱいになってしまうかもしれません。ちょっと高度な整数論のお話ですが，でもとても興味深いお話なんですよ。

本記事では，上の背景を知ってもらうために冒頭から４分の３までに「二次形式」の解説をします。そして，残り４分の１で本題のプログラムの紹介をする，という構成にしたいと思います。

上から順に読んでいただいても構いませんし，前提知識は持っていて結論のプログラムだけに興味がある方は，もちろん飛ばして読んでも構いません。その場合は，【本題】と書いてある箇所まで飛ばしてみてください。

では，ちょっと長い文章になりますが，最後までお付き合い頂けると幸いです。

目次

経緯

二次形式とその変換（１／４）

二次形式の判別式とその類数（２／４）

reduced form による同値類の全列挙（３／４）

【本題】類数を求めるプログラム（４／４）

まとめ

経緯 *

本文に入る前に経緯をちょっとだけお話しておきます。最近，私のとあるブログ記事をきっかけとして，すろさんという方（数論がご専門の方）とお知り合いになりました。縁あって，その方のツイキャスにて，以下の本の勉強をさせていただけることになりました。（感謝！）

Primes of the Form x2+ny2: Fermat, Class Field Theory, and Complex Multiplication (Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts)

作者:Cox, David A.
発売日: 2013/04/29
メディア: ペーパーバック

この本の第２章から第３章の前半では，今回のテーマである二次形式の話を議論していまして，その中で類数の計算を求める箇所が私の琴線に触れたのです。せっかくなので勉強の成果をまとめようと，この記事を書くことにしました。すろさんに私の理解の度合いを伝えることも兼ねて。

まさに勉強過程の中でこの記事を書いていますので，記述に誤りがあるかもしれませんが，その場合はおそらく私の理解不足と思われます。もし，おかしなところがありましたら指摘して頂けると嬉しいです。

あと，参考文献が英語の本のため，日本語訳していない用語がいくつか使われていますが，その点はご容赦ください。

二次形式とその変換（１／４）*

これまで私のブログでは，

$f(x, y) = x^2 + y^2$ 　や　 $f(x, y) = 6x^2 + xy + y^2$

のような式の形で表すことができる素数は，いったいどんな素数であるかについて思いを馳せてきました。この話を一般化したものが，今回お話したい二次形式の理論です。

二次形式とは，

$f(x, y) = ax^2 + bxy + cy^2$

の形で表される二変数関数のことです。

すべての項の変数 $x, y$ の次数が，あわせて２となっているので「二次」なのです。

今回は，変数 $x,y$ ，定数 $a, b, c$ がそれぞれ整数の場合を考えます。あと，後のためにひとまず $a > 0$ としておきましょう。

また，二次形式 $f(x, y)$ によって整数 $m$ が表わせるとき，すなわち，整数 $m$ に対して，

$m = f(x, y)$

となるような整数 $x, y$ が存在するとき「二次形式 $f$ は $m$ を表現する」といいます。主語を入れ替えて「整数 $m$ は二次形式 $f$ によって表現される」とも言うこともあります。

また， $a, b, c$ を同時に割り切る素数が存在しないとき，その二次形式は primitive である，といいます。素数を表現するためには， primitive な二次形式であることが必要です。私たちが興味あるのは「素数を生み出す二次形式」なので，この条件も大事です。

＊　＊　＊

いくつか具体的な二次形式の例を挙げてみましょう。

たとえば， $a = 1, b = 0, c = 1$ とすれば，二次形式は

$f(x, y) = x^2 + y^2$

となり冒頭の式と一致します。この二次形式によって表現される奇素数は，

$5, 13, 17, 29, \ldots$

となり 4n+1 型 に限られます。この例は，以下の記事で示した事実の言い換えとなっています。
tsujimotter.hatenablog.com

また， $a = 6, b = 1, c = 1$ とすれば，二次形式は

$f(x, y) = 6x^2 + xy + y^2$

と書けますが，この二次形式で表現される素数は「特徴的な性質をもった数」であったことは，以下の記事で示したとおりです。
tsujimotter.hatenablog.com

＊　＊　＊

さて唐突ですが，二次形式に以下のような変換を適用することを考えてみましょう。

$x, y$ から $x', y'$ への変換を考える。

$\left\{ \begin{array}{l} x = px' + qy' \\ y = rx' + sy' \end{array} \right.$

ただし， $p, q, r, s$ は整数で，かつ，
$ps - qr = 1$
を満たす。

上の式で表せる変換のことを，行列を用いて「変換 $\begin{pmatrix} p & q \\ r & s \end{pmatrix}$ 」と呼ぶことにしましょう。行列を使った理由はあとで分かります。

変換 $\begin{pmatrix} p & q \\ r & s \end{pmatrix}$ によって得られる式は， $x', y'$ を変数とみると二次形式になります。さらに，この新しく得られた二次形式は，元の二次形式によって表現できる数をすべて表現できることが分かります。

＊　＊　＊

具体的な例を挙げて検証してみましょう。

変換 $\begin{pmatrix} 3 & 5 \\ 1 & 2 \end{pmatrix}$ を，二次形式 $f(x,y) = x^2 + y^2$ に適用することを考えます。

$x, y$ に代入すると，

$f(3x'+5y', x'+2y') = (3x'+5y')^2 + (x'+2y')^2$

となって，これをガチャガチャと計算していくと，最終的に

$= 10 x'^2 + 34x'y' + 29 y'^2$

が得られます。これはたしかに二次形式になっていますね。

得られた二次形式を $g$ とおきましょう。つまり，

$g(x, y) = 10 x^2 + 34xy + 29 y^2$

です。

このとき，元の二次形式 $f$ に対して，

$f(3x + 5y, x + 2y) = g(x, y)$

が成り立っていることに注意しましょう。

＊　＊　＊

さてここで，元の式に $x = 2, y = 3$ を代入すると $f(2, 3) = 2^2 + 3^2 = 13$ ですから， $13$ は二次形式 $f$ によって表現できます。一方，上に挙げた変換の性質により， $13$ は二次形式 $g$ によっても表現できるのです。これを確認しましょう。

定義から，変換の式は

$\left\{ \begin{array}{l} x = 3x' + 5y' \\ y = x' + 2y' \end{array} \right.$

であったので， $x = 2, y = 3$ として，連立方程式

$\left\{ \begin{array}{l} 2 = 3x' + 5y' \\ 3 = x' + 2y' \end{array} \right.$

を解きましょう。この解 $x' = -11, y' = 7$ を $g$ に代入すると， $g(-11, 7) = 13$ が得られるはずです。

このように「変換 $\begin{pmatrix} p & q \\ r & s \end{pmatrix}$ によって得られた二次形式同士は，互いに同じ数を表現することができる」のです。この事実は非常に重要なので，覚えておいてください。

このことから，「同じ数を表現できる」という意味において，変換によって移り変われる２つの二次形式 $f, g$ は「同じものである」とみなすことができます。数学的には「 $f, g$ は proper に同値である*1」と言います。

＊　＊　＊

ところで，線形代数の講義を思い出しつつ，先ほどの連立方程式をみると，

$\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} p & q \\ r & s \end{pmatrix} \begin{pmatrix} x' \\ y' \end{pmatrix}$

のように行列の一次変換になっていることがわかります。逆行列をとって左からかけてあげると，

$\begin{pmatrix} p & q \\ r & s \end{pmatrix}^{-1} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} x' \\ y' \end{pmatrix}$

となって， $x', y'$ が得られます。

逆行列が存在する条件は，「行列式が０でないこと」，つまり $ps - qr \neq 0$ です。今回の場合， $ps - qr = \pm 1$ ですので，必ず逆行列が存在する，つまり連立方程式に解が存在します。

もっというと， $ps - qr = \pm 1$ は，連立方程式に整数解がある必要十分条件になっています。

二次正方行列の逆行列は，

$\displaystyle \begin{pmatrix} p & q \\ r & s \end{pmatrix}^{-1} = \frac{1}{ps-qr}\begin{pmatrix} s & -q \\ -r & p \end{pmatrix}$

ですから，この行列の係数がすべて整数になるためには，分母の行列式が $1$ または $(-1)$ のときに限られる，というわけです。

専門的にいうと，このような条件を持つ行列の集合を特殊線形群 $SL(2, \mathbb{Z})$ といいます。このブログでもときおり登場しますね。

$SL(2, \mathbb{Z}) = \left\{ \begin{pmatrix} p & q \\ r & s \end{pmatrix} \middle| \;\; p, q, r, s \in \mathbb{Z}, \; ps - qr = 1 \right\}$

さてさて，これにて本記事の４分の１の説明が終わりました。まだまだ続きます。

二次形式の判別式とその類数（２／４）*

二次方程式に判別式があったように，二次形式にも「判別式」が存在します。その定義は二次方程式の場合とほぼ同じです。

《定義》
二次形式 $ax^2 + bxy + cy^2$ の係数 $a, b, c$ を使って得られる式を「判別式」とよび， $D$ を使って表す。
$D = b^2 - 4ac$

この定義に従って計算すると，

$x^2 + y^2$ の判別式は， $D = -4$
$6x^2 + xy + y^2$ の判別式は， $D = -23$

となります。

判別式が，負の例ばかり挙げていますが，その理由は「二次形式の表現できる値を正としたい」からです。 $D < 0$ かつ $a > 0$ の二次形式は，すべて正の値しかとらないことが知られています。このような二次形式のことを「正定値二次形式」と呼びます。今回考えたいのは正定値二次形式です。

ところで，先ほどの変換によって二次形式 $f$ が $g$ に変換されるとき，判別式は変換 $\begin{pmatrix} p & q \\ r & s \end{pmatrix}$ に対して不変です。

つまり， $f(x, y) = ax^2 + bxy + cy^2$ に変換 $\begin{pmatrix} p & q \\ r & s \end{pmatrix}$ を適用して得られた二次形式を $g(x, y) = a'x^2 + b'xy + c'y^2$ としたとき，それぞれの判別式は一致します。

実際，先の例で言うと，二次形式 $x^2 + y^2$ と $10x^2 + 34xy + 29y^2$ の判別式はともに $-4$ となって一致します。

変換に対して判別式が不変であることから，同じ判別式をもつ二次形式は無数に存在することがわかります。たとえば，判別式 $D = -4$ をもつ二次形式は，以下のようにいくらでも列挙可能です。

$x^2 + y^2$

$10x^2 + 34xy + 29y^2$

$x^2 + 4xy + 5y^2$

$2x^2 + 6xy + 5y^2$

$x^2 + 12xy + 37y^2$

$5x^2 + 14xy + 10y^2$

・・・

上に挙げた二次形式は，すべて $x^2 + y^2$ に proper に同値です。このように，同値な元をすべてまとめた集合のことを「同値類」と呼びます。 $x^2 + y^2$ に同値であるような同値類を

$[x^2 + y^2]$

のように表記します。このときの，二次形式 $x^2 + y^2$ は同値類 $[x^2 + y^2]$ の代表といえますから，これを同値類 $[x^2 + y^2]$ の「代表元」と呼びます。

＊　＊　＊

一方で，判別式が等しい二次形式のすべてが，１つの同値類にまとめられるかというと，必ずしもそうではありません。

$D = -20$ のときを考えましょう。判別式 $D = -20$ をもつ二次形式として，

$\left\{ \begin{matrix} x^2 + 5y^2 \\ 2x^2 + 2xy + 3y^2\end{matrix} \right.$

の２つが例として挙げられますが，この２つは proper に同値ではありません。

したがって，判別式 $D = -20$ をもつすべての二次形式の中には，

$x^2 + 5y^2$ を代表元とする同値類 $[x^2+5y^2]$
$2x^2 + 2xy + 3y^2$ を代表元とする同値類 $[2x^2 + 2xy + 3y^2]$

の２つが存在するというわけです。図示するとこんな感じです。

後に示しますが $D=-20$ のすべての二次形式は， $\left\{ [x^2 + 5y^2], \; [2x^2 + 2xy + 3y^2] \right\}$ のいずれかに分類され，これ以外の同値類に属する二次形式は存在しません。

ここで，同値類の数のことを「類数」といいます。判別式が $D$ であるような二次形式の類数を $h(D)$ と表すことにすると， $D=-20$ の場合の類数は $h(D) = 2$ です。

さて，ここで元の問題に立ち返ってみましょう。判別式 $D = -20$ をもつ二次形式のそれぞれの同値類に，整数 $x, y$ を入れたときにどんな数が表現されるでしょうか。

実験してみると，それぞれの同値類は異なる数を表現することがわかります。

具体的に計算すると， $[x^2 + 5y^2]$ の元が表現できる奇素数 $p$ には，

$29, 41, 61, 89, 101, 109, \ldots$

がありますが，これらはすべて $20$ で割って $1$ または $9$ 余る素数です。一方で， $[2x^2 + 2xy + 3y^2]$ の元が表現できる奇素数 $p$ は，

$3, 7, 23, 43, 47, 67, \ldots$

で，これらはすべて $20$ で割って $3$ または $7$ 余る奇素数です。以上に該当しない奇素数は，一部の例外を除き，判別式が $-20$ の二次形式によって表すことが出来ません。

$[x^2 + 5y^2]$ の元と $[2x^2 + 2xy + 3y^2]$ の元は proper に同値ではありませんから，異なる数を表現するのは当然ですね。しかし「どちらの二次形式がどの素数を分担するか」については，自明ではありません。特に $D = -20$ の場合は， $20$ で割った余りがその分担に関係しているように見えます。これは興味深いですね。

もう少しだけ例を挙げましょう。判別式が $D = -4$ のときは，同値類は $[x^2 + y^2]$ の１つだけです。したがって，類数 $h(D) = 1$ です。この例では， $4$ で割って $1$ 余る奇素数はすべて $[x^2 + y^2]$ の元によって表現できて，それ以外の奇素数は判別式 $D = -4$ の二次形式では表現することが出来ません。類数１の場合は，表現できる素数は１つの同値類が表現できる数に限られますから，分かりやすくていいですね。

以上の例からわかるように，二次形式の理論において，同値類や類数は重要な概念です。一方その計算はというと，定義から考えて容易ではないように見えます。さらっと「 $D = -20$ の類数は２である」や「 $D = -4$ の類数は１である」などと言い切っていますが，いったいどのように計算したらよいのでしょう。

実は，判別式 $D$ における同値類を簡単に列挙する方法が知られています。それが次の項で登場する "reduced form" を用いる方法です。

reduced form による同値類の全列挙（３／４）*

まず，reduced form の定義からいきましょう。

《定義》
以下の３つの条件を同時に満たす正定値二次形式 $ax^2 + bxy + cy^2$ を reduced form という。

primitive である（ $a, b, c$ を同時に割り切る素数が存在しない）

$\left|b\right| \leq a \leq c$

$\left|b\right| = a$ または $a = c$ ならば $b \geq 0$

判別式 $D = -20$ の場合，

$\left\{ \begin{matrix} x^2 + 5y^2 \\ 2x^2 + 2xy + 3y^2\end{matrix} \right.$

の２つが reduced form の条件を満たしており，これ以外に上の条件を満たす二次形式は存在しません。

なぜこんな「変な条件」を持った二次形式を考えるのでしょう。それは，次の 《重要な定理》 があるためです。

《重要な定理》
任意の primitive な正定値二次形式は，ただ１つの reduced form と proper に同値である

言い換えると，すべての二次形式は reduced form を代表元とする同値類のいずれかに必ず所属し，しかも，どの同値類にも必ず１つだけの reduced form が存在するということです。

つまり，reduced form の数を数えるだけで，類数が求められるというわけです！

なんと便利な！！

これがどれほど便利なことであるかは，実際に計算してみれば分かります。まずは，reduced form の定義に乗っ取って，具体的に列挙する方法を考えましょう。以下では，ある数 $D$ （ただし， $D < 0$ ）が与えられたときに，判別式 $D$ に対する reduced form を求める方法を示します。

まず， $D = b^2 - 4ac$ にマイナスをかけて， $-D = 4ac - b^2$ とします。

reduced form の条件２（ $\left|b\right| \leq a \leq c$ ）より，

$-D = 4ac - b^2 \geq 4a^2 - a^2 = 3a^2$

したがって， $a$ は

$\displaystyle a \leq \sqrt{\frac{-D}{3}}$

の不等式を満たします。また，正定値の条件 $a > 0$ より

$\displaystyle 0 < a \leq \sqrt{\frac{-D}{3}}$

となります。 $D$ は与えられているので， $a$ の候補が有限個に絞れました。

同様に $0 \leq \left|b\right| \leq a$ から， $a$ を上限として， $\left|b\right|$ の候補が決まります。

$a, b$ の候補それぞれに対して，判別式の定義から $c$ を決定します。

$\displaystyle c = \frac{b^2 - D}{4a}$

ただし， $c$ は整数より，分母の $4a$ は分子 $(b^2 - D)$ を割り切る必要があります。

次に 条件３（ $\left|b\right| = a$ または $a = c$ ならば $b \geq 0$ ）を確認します。 $b < 0$ の場合は，「 $\left|b\right| = a$ または $a = c$ 」かどうか確認して，真であれば reduced form の候補から外します。

最後に，条件１（ $a, b, c$ を同時に割り切る素数が存在しない）を確認して，共通の約数をもつ場合は reduced form の候補から外します。

以上により，候補として残ったすべて $a, b, c$ の組が reduced form の係数となります。

＊　＊　＊

$D = -20$ の場合について，具体的に計算してみましょう。

まず， $a$ の候補は，

$\displaystyle 0 < a \leq \sqrt{\frac{20}{3}} = 2.58\ldots$

より， $a = 1, 2$ のいずれかです。それぞれについて， $b, c$ を考えてみましょう。

$a = 2$ の場合

$0 \leq \left|b\right| \leq 2$ から， $b = 0, \pm 1, \pm 2$ が候補です。

$b = \pm 2$ のとき， $\left|b\right| = a$ ですから， $b>0$ となる $b = 2$ だけが候補として残ります。

この場合の $c$ を計算すると，

$\displaystyle c = \frac{2^2 - (-20)}{4\cdot 2} = 3$

となり， $c$ は整数で，かつ， $a, b, c$ を同時に割り切る素数が存在しないので，これは reduced form です。

１つめの reduced form である $2x^2 + 2xy + 3y^2$ が見つかりました。

一方の， $b = 0, \pm 1$ の場合は，いずれも $c$ の分母が分子を割り切らないため不適です。

$a = 1$ の場合

$0 \leq \left|b\right| \leq 1$ から， $b = 0, \pm 1$ が候補です。

$b = \pm 1$ のとき， $\left|b\right| = a$ ですから， $b>0$ となる $b = 1$ だけが候補として残ります。

この場合の $c$ を計算すると，

$\displaystyle c = \frac{1^2 - (-20)}{4\cdot 1}$

となりますが，分母が分子を割り切らないため不適。

一方の， $b = 0$ のときは，

$\displaystyle c = \frac{0^2 - (-20)}{4\cdot 1} = 5$

となって， $c$ が整数になりますから，これも reduced form です。

結果，２つめの reduced form である $x^2 + 5y^2$ が見つかりました。

これにて，条件はすべて出尽くしました。 $D = -20$ の二次形式の同値類は，

$\left\{[2x^2 + 2xy + 3y^2], \; [x^2 + 5y^2] \right\}$

となって，類数が２であることが分かりました。

めでたしめでたし。

【本題】類数を求めるプログラム（４／４）*

お待たせしました。ここからはプログラミングの時間です。

ここまでの知識があると，判別式が $D$ であるような正定値二次形式の類数を決定するプログラムを作ることが出来ます。ここでは，単に類数を求めるだけでなく，同値類の代表元として reduced form を列挙することにしましょう。

以下のページに，Ruby で書かれたソースコードを置いておきました。（ Ruby を使っているのは，単なる趣味です。）

正定値二次形式の類数を計算する Ruby スクリプト

実行方法は，以下の通りです。

リンク先からソースコードをコピーしてきて，"class_number.rb" というファイルとして保存します。ターミナル上で保存先のディレクトリに移動し，次のコマンドを実行すれば，結果が標準出力に表示されます。

$ ruby class_number.rb

出力結果のうち，冒頭の 12 行を紹介すると，以下のようになります。

D, h(D), C(D)
-3, 1, [x^2+xy+y^2]
-4, 1, [x^2+y^2]
-7, 1, [x^2+xy+2y^2]
-8, 1, [x^2+2y^2]
-11, 1, [x^2+xy+3y^2]
-12, 1, [x^2+3y^2]
-15, 2, [x^2+xy+4y^2],[2x^2+xy+2y^2]
-16, 1, [x^2+4y^2]
-19, 1, [x^2+xy+5y^2]
-20, 2, [x^2+5y^2],[2x^2+2xy+3y^2]
-23, 3, [x^2+xy+6y^2],[2x^2+xy+3y^2],[2x^2-xy+3y^2]
...

CSV 形式になっていて，カンマで区切ると左から，

判別式 $D$ （ただし， $D<0, D\equiv 0,1 \pmod{4}$ ），
その判別式に対する類数 $h(D)$ ，
対応する同値類の群 $C(D)$

が得られます。

上の結果から，判別式 $D = -20$ のとき，類数は $h(D) = 2$ で，そのときの同値類は $\left\{[2x^2 + 2xy + 3y^2], \; [x^2 + 5y^2] \right\}$ の２つであることが確認できますね。

標準出力に出すのが不便であれば，以下のように CSV ファイルにリダイレクトしてもいいでしょう。

$ ruby class_number.rb > class_number.csv

こうすれば，CSVファイルがエクセルで開けて便利です。

＊　＊　＊

アルゴリズムは，上の項で述べた手順をそのままなぞるだけです。ソースコードの以下の関数が，判別式 $D$ の正定値二次形式の同値類を列挙する配列を出力する関数です。

def classesOfDiscriminant d 
...
end

関数の中では， $a, b$ が取りうる値を while ループで探索して，条件に合う組だけを classes という配列に追加しています。

さまざまな判別式 $D$ に対する計算を，ループによって実行しているのが以下の箇所です。

# 判別式が -3 から -163 までの間の類数を計算する
(1..163).each do |i|
...
end

現状のプログラムでは，判別式が -163 までの類数を計算できます。この 163 の部分を 10000 に変えると，10000 までの判別式が計算できるようになります。

以下のページに，判別式 $-10000$ までのリストを，CSV 形式で用意してみました。

List on class number of positive definite form of discriminant D ( from -3 to -10000 )

少し調べてみた限りですが，ここまでそろった類数の表は，ネット上にはそうそうないように思います。

唯一気がかりなのは，プログラムにバグがあって値が間違っている可能性が否定できないことです。笑
一応，冒頭で紹介した方と一緒に，少なくとも $D = -1000$ までは互いに計算して確認しましたので，たぶんあっていると思われます。

ともかく，これによって $-3$ から $-10000$ までの判別式に対して，類数を計算することが出来ました。

まとめ *

ここまで読んでくれた方はありがとうございます。

今回は，reduced form を使って，判別式が $D$ であるような正定値二次形式の同値類をすべて列挙する方法について紹介しました。同値類が列挙できれば，その数を数えれば類数が求まります。

reduced form 面白いですね。同値類を求める計算は，一見途方もない計算が必要なように思いますが，今回の方法であれば有限の範囲の探索で行えたのです。そして，この方法はきわめてプログラム向きです。

せっかく類数が計算できるようになったので，日曜数学的にはいろいろ遊んでみたくなります。たとえば， $D$ と $h(D)$ の関係はどんなグラフになっているかとか。

ところで，類数を計算してみると，類数が $1$ になる判別式は $D = -163$ が最後となっていることがわかります。そう，終わりがあるのですね。そういえば， $D = -163$ の類数が $1$ であることは，以下の記事で書いた話とも関連があり，興味深い現象だったりします。
tsujimotter.hatenablog.com

また，reduced form は，単に類数が計算できるだけでなく，具体的な同値類を列挙できるのも良いですね。具体的に $x, y$ に値を入れれば，どんな素数が表現できるか容易に調べることが出来ます。今回行った実験によって，どうやら判別式 $D$ の二次形式が表現する素数 $p$ と， $p \mod (-D)$ が関係していることも分かりました。