2025-12-22

位数が素数でない有限体に関する基本的なことが分かっていなかったので調べた

有限体

有限体のことを分かったつもりでいました

有限体には位数が素数のものとそうでないもの、つまり位数が素数冪となるものがある。前者は素数 $p$ を用いて $\mathbb{Z}/p\mathbb{Z}$ を考えればよいので簡単だが、後者はちょっとだけややこしい。とは言っても、位数が $q=p^n$ なら適当に $\mathbb{F}_p$ 上の $n$ 次既約多項式 $f(x)$ を持ってきて $\mathbb{F}_q = \mathbb{F}_p[x]/(f(x))$ とすればいいんでしょ？と、その程度の認識だった。それで、 $f(\alpha)=0$ となるような $\alpha$ によって具体的な元が $\sum_{i=0}^{n-1} c_i \alpha^{i} (c_i \in \mathbb{F}_p )$ みたいに書けるんでしょ？と、それで分かったつもりになっていた。

ところが、最近になっていろいろと分かっていないことがあることに気づいた。それは具体的には以下の3点である。

既約多項式の選択の仕方によらず $\alpha$ は $\mathbb{F}_q^{\times}$ の生成元になると思っていたが、その理解は正しいのか？
既約多項式の根として適当に $\alpha$ を選んでいるが、既約多項式の根は一つとは限らない。これまで根の選択方法について考えたことがなかったが、適当に選んでしまって大丈夫なのか？
$\mathbb{F}_q$ の元の $\mathbb{F}_p$ 上の最小多項式の次数はどうなるのか？特に、次数が $n$ より大きくなることはあり得るのか？

本稿ではこれらの疑問の答えを順に解き明かしていく。以下では $q=p^n$ であるとする。

疑問1：既約多項式の根は常に $\mathbb{F}_q^{\times}$ の生成元になるのか？

必ずしもそうなるとは限らない。そのような性質を満たす多項式を原始多項式と呼ぶ。逆に言えば、 $f(x)$ が原始多項式なら $f(x)$ の根 $\alpha$ が $\mathbb{F}_q^{\times}$ の生成元になる。これは実際に例を見れば一目瞭然なので、以下で見てみよう。なお、例に使った多項式は[1]を参考にした。

原始多項式の例

Sageで $\mathbb{F}_{16}$ を特別な引数なしで生成すると、既約多項式として $x^4 + x + 1$ が選ばれる。これは原始多項式である。実際、多項式の根aの冪を順番に計算すると15乗して初めて1になることが分かる。

sage: F.<a> = GF(16)
sage: F.modulus()
x^4 + x + 1
sage: F.modulus().is_primitive()
True
sage: for i in range(1, len(F)):
....:     print(f"{i:<2}: {a**i}")
....:
1 : a
2 : a^2
3 : a^3
4 : a + 1
5 : a^2 + a
6 : a^3 + a^2
7 : a^3 + a + 1
8 : a^2 + 1
9 : a^3 + a
10: a^2 + a + 1
11: a^3 + a^2 + a
12: a^3 + a^2 + a + 1
13: a^3 + a^2 + 1
14: a^3 + 1
15: 1
sage:

原始多項式ではない既約多項式の例

今度は $\mathbb{F}_{16}$ を $x^4 + x^3 + x^2 + x + 1$ を指定して生成してみる。これは原始多項式ではない。実際、多項式の根aの冪を順番に計算すると5乗した時点で1になることが分かる。

sage: P.<x> = GF(2)[]
sage: F.<a> = GF(16, modulus=x^4 + x^3 + x^2 + x + 1)
sage: F.modulus()
x^4 + x^3 + x^2 + x + 1
sage: F.modulus().is_primitive()
False
sage: for i in range(1, len(F)):
....:     print(f"{i:<2}: {a**i}")
....:
1 : a
2 : a^2
3 : a^3
4 : a^3 + a^2 + a + 1
5 : 1
6 : a
7 : a^2
8 : a^3
9 : a^3 + a^2 + a + 1
10: 1
11: a
12: a^2
13: a^3
14: a^3 + a^2 + a + 1
15: 1
sage:

疑問2：既約多項式の根の選び方はどうすればよいのか？

これは適当でよい。 $n$ 次既約多項式 $f(x)$ の根は全て $\mathbb{F}_q$ に含まれており、かつどれを選んでも本質的には同じ有限体が得られる。

なぜそうなるのかをもう少し説明してみる。簡単に言えば以下の定理が成り立つからということになる[2]。

最小多項式の根の間の関係

$L/K$ が体の代数拡大とし, $\alpha \in L$ の $K$ 上の最小多項式を $f(x) = x^n + a_1 x^{n-1} + \cdots + a_n$ とする. このとき, $\beta \in L$ が $f(x)$ の根なら, 次の(1)－(3)が成り立つ.
(1) 割愛
(2) $f(x)$ は $\beta$ の最小多項式でもあり, $K$ 上の同型 $K(\alpha) \cong K(\beta)$ で $\alpha$ が $\beta$ に対応するものが存在する.
(3) 割愛

これより、拡大 $L/K$ は正規拡大だと言える。今はあまり関係ないが、有限体の拡大は必ず分離拡大になるので、結局ガロア拡大になる。

例

理論的には分かった気持ちになったが、例も見ておこう。以下では $f(x) = x^2 + 1$ によって生成される有限体 $\mathbb{F}_9 = \mathbb{F}_3[x]/(f(x))$ を考える。 $f(x)$ が $\mathbb{F}_3$ 上既約であることは0, 1, 2を代入して0にならないことから分かる。

根の一つを $\alpha$ と名付けると、この多項式は $(x - \alpha)(x - \alpha^3)$ と因数分解できる。と、いきなり言われてもホンマかいなという気持ちになるかもしれないので、以下で確かめておく。

$\displaystyle{ \begin{eqnarray} (x - \alpha)(x - \alpha^3) &=& x^2 - (\alpha^3 + \alpha) + \alpha^4 \\ &=& x^2 - \alpha(\alpha^2 + 1) + (\alpha^2 + 1)(\alpha^2 - 1) + 1 \\ &=& x^2 + 1 \end{eqnarray} }$

このようにして構成した $\mathbb{F}_9$ の元を具体的に書き出してみると以下のようになる。

$0$
$1$
$2$
$\alpha$
$\alpha+1$
$\alpha+2$
$2\alpha$
$2\alpha+1$
$2\alpha+2$

ここで $\beta = \alpha^3 = 2\alpha$ と置く。すると、 $\mathbb{F}_9$ の元は以下のように書ける（分かりやすさのために並びは上述のものと対応するようにした）。

$0$
$1$
$2$
$2\beta$
$2\beta+1$
$2\beta+2$
$\beta$
$\beta+1$
$\beta+2$

このように $\beta$ を使った表現は単に $\alpha$ を使った表現の記号を $\beta$ に置き換えただけという形になっており、明らかに体として同じ構造を持っていることが分かる。

また、実は $\alpha= \beta^3$ であるため、 $f(x) = (x-\beta)(x-\beta^3)$ と書いても同じである。これも形式的には記号を置き換えただけになっていて、 $\alpha$ と $\beta$ の綺麗な対称性が見て取れる。

疑問3：有限体の元の最小多項式の次数はどうなるのか？

これは $n$ 次以下になる。もっと言うと、任意の $\alpha \in \mathbb{F}_q$ について $\mathbb{F}_p$ 上の最小多項式の次数は $n$ を割り切るような整数となる。

この事実に関してはスパッと証明を書いてくれている文献を見つけられなかったので、AIの助けを借りつつ自分で考えてみた。

まず、 $\alpha$ を $\mathbb{F}_p$ に添加した体 $\mathbb{F}_p(\alpha)$ を考える。このとき、体の拡大 $\mathbb{F}_p(\alpha)/\mathbb{F}_p$ および $\mathbb{F}_q/\mathbb{F}_p$ の拡大次数の間には以下のような関係がある。

$\displaystyle{ [\mathbb{F}_p(\alpha) : \mathbb{F}_p] \mid [\mathbb{F}_q : \mathbb{F}_p] }$

ここで、 $[\mathbb{F}_q : \mathbb{F}_p] = n$ なのは良いだろう。問題は $[\mathbb{F}_p(\alpha) : \mathbb{F}_p]$ の方だが、これは $\alpha$ の $\mathbb{F}_p$ 上の最小多項式 $m_{\alpha}(x)$ の次数に等しくなる。この点さえ納得できれば冒頭で述べた結果を得られるので、この点について詳しく見ていく。

$\phi: \mathbb{F}_p[x] \to \mathbb{F}_p(\alpha), f(x) \mapsto f(\alpha)$ という準同型を考える。 $\mathrm{Ker}\phi = \{f(x) \mid f(\alpha) = 0\} = (m_{\alpha}(x))$ となるので、準同型定理より以下が成り立つ。

$\displaystyle{ \mathbb{F}_p[x]/(m_{\alpha}(x)) \cong \mathrm{Im}\phi = \mathbb{F}_p[\alpha] }$

体の有限次拡大は代数拡大になるので、拡大 $\mathbb{F}_p(\alpha)/\mathbb{F}_p$ は代数拡大である（この事実の証明は本[2]などを参照）。これより $\alpha$ は $\mathbb{F}_p$ 上代数的なので $\mathbb{F}_p[\alpha] = \mathbb{F}_p(\alpha)$ となる（この事実の証明も本[2]などを参照）。よって以下の式が成り立つ。

$\displaystyle{ \mathbb{F}_p[x]/(m_{\alpha}(x)) \cong \mathbb{F}_p(\alpha) }$

$m_{\alpha}(x)$ の次数を $k$ とすると、 $\mathbb{F}_p[x]/(m_{\alpha}(x))$ は $1, x, \cdots, x^{k-1}$ を基底とする $\mathbb{F}_p$ 上の $k$ 次ベクトル空間になるので、結局 $[\mathbb{F}_p(\alpha) : \mathbb{F}_p] = k$ となる。よって $k \mid n$ となる。証明終わり。

例

例として $\mathbb{F}_{16}$ の各元の最小多項式を以下に示す。次数が1, 2, 4のいずれかになっており、ここまで説明してきた内容と合致することが分かる。

sage: F.<a>=GF(16)
sage: for i in range(1, len(F)):
....:     print(f"{str(a**i):<20}: {(a**i).minpoly()}")
....:
a                   : x^4 + x + 1
a^2                 : x^4 + x + 1
a^3                 : x^4 + x^3 + x^2 + x + 1
a + 1               : x^4 + x + 1
a^2 + a             : x^2 + x + 1
a^3 + a^2           : x^4 + x^3 + x^2 + x + 1
a^3 + a + 1         : x^4 + x^3 + 1
a^2 + 1             : x^4 + x + 1
a^3 + a             : x^4 + x^3 + x^2 + x + 1
a^2 + a + 1         : x^2 + x + 1
a^3 + a^2 + a       : x^4 + x^3 + 1
a^3 + a^2 + a + 1   : x^4 + x^3 + x^2 + x + 1
a^3 + a^2 + 1       : x^4 + x^3 + 1
a^3 + 1             : x^4 + x^3 + 1
1                   : x + 1
sage:

まとめ

本稿では私が有限体について理解が甘かった部分について調べ直した結果を紹介した。基本的なことほど分かったつもりになっていると怖いということを久々に思い出した。

参考

[1] qiita.com
[2] www.nippyo.co.jp ※今から購入される場合は第2版を買われるのが良いだろう。

2025-10-09

Erasure codingの実装としてのReed–Solomon符号～符号化から復号まで

たまには技術っぽい話をしよう

いつもは数学のことばかり書いているのだが、私の本業はストレージエンジニアである。ストレージエンジニアってなんだ？と聞かれると私も良く分からないが、そう名乗ることにしている。そんなわけで、たまにはストレージ関連技術について書いてみようと思う。もちろん、多少なりとも数学っぽい話題を選んだつもりである。

分散ストレージにおけるデータ冗長化

近年では企業が扱うデータの量はどんどん増えていると思うのだが、それに伴ってデータ管理に関していろいろと頭の痛い問題が出てくる。例えばデータをいかに失わずに保持し続けるか？というのは最重要課題の一つだろう。データを保存しているメディアやサーバーはいずれ故障する運命にあることを考えると、失って困るデータというのは冗長化しておくのが普通である。

データ冗長化にはいくつかのやり方がある。一つは単純なレプリケーションを行う方法である。レプリケーションとは読んで字のごとくデータを複製する手法である。例えば2ノードの同時障害に耐えたいのであれば（オリジナルデータも含めて）3つ以上のコピーを異なるノードに分散配置することになる。ただ、レプリケーションによりノード障害への耐性が向上するのはよいのだが、これには非常にコストがかかる。レプリケーションの場合、データを $n$ 重化したい場合はコストもざっくり $n$ 倍になってしまう。

コストを低減しつつデータ冗長度を高めたい場合、erasure codingを使うという方法がある。Erasure codingではデータをシンボルと呼ばれるまとまりで扱う。 $k$ 個のシンボルを $n$ 個の冗長なシンボルに変換することで、 $n-k$ 個までのデータ消失があっても元のデータが復元できるという性質を持つ。ただし、 $n, k \in \mathbb{N}, k < n$ である。例えば $n=10, k=6$ として10個のシンボルをそれぞれ異なるノードに配置した場合、4ノードまでの障害が起きてもデータの読み出しが可能となる。

このように、erasure codingではデータの冗長度やストレージにかかるコストをきめ細やかにコントロールすることが可能であり、安心でありながらお財布的には嬉しい。ただし、障害発生時に失ったデータを復元するのにそれなりの通信コスト・計算コストがかかることは覚悟しなければならないというトレードオフがある。

ところで、このような素晴らしい性質を持ったerasure codingはどのように実現されているのだろうか？その実現方法の一つにReed-Solomon符号というものがある。前置きが長くなったが、本稿ではこのReed-Solomon符号（以下、RS符号と呼ぶ）の符号化と復号について、erasure codingへの応用を念頭に置きつつ説明する。

RS符号

RS符号にはいくつか符号化のやり方にバリエーションがある。私が全てを理解できているわけではないが、可能な限りそれらについて説明したいと思う。以降で説明していることはだいたいWikipedia[1]を参考にしている。

本稿の主眼はRS符号をerasure codingの実装として利用することである。分散ストレージへの応用を考えた場合、通常は障害が発生したノードからはデータが読み出せないわけであるから、以下ではデータが欠けているシンボルがどれであるかは特定できることを前提とする。RS符号を誤り訂正符号として見た場合には通常どのシンボルに誤りがあるかを特定するところから始める必要があるが、本稿では誤り訂正については考えないことにする。

誤り訂正について考えないのだとすると、データ化けが発生したらどうするんだというのが気になるかもしれない。それについてはファイルシステムの機能に頼るなりチェックサムを別途計算して突き合わせるなり、他の方法を採用する必要があるだろう。

準備

シンボル

RS符号ではデータのシンボルとして有限体の元を使う。RS符号では符号化や復号の際にシンボルの四則演算を行う必要があるため、シンボルは体の元でなければ困る。私の理解では体でありさえすれば理論的には何でもよいと思うのだが、実用を考えると無限体をコンピューターで扱うのは難しいので、有限体を使っているものと思われる。

以下では有限体の位数は $q$ とする。当然、 $q$ は素数冪である（さもなければ体にならない）。

シンボルとビット列のマッピング

有限体の元はそのままではコンピューターで扱いづらいのだが、 $q$ が2のべき乗である場合はビット列と対応づけることで簡単に扱えるようになる。例として $q = 2^3 = 8$ のケースを考えてみよう。このとき、 $\mathbb{F}_8$ と3ビットのビット列を一対一に対応づけることができる。これは $\mathbb{F}_8$ の元を原始元 $\alpha$ の多項式として表したときの係数を対応するビット列と考えればよい。具体的には以下のようになる。

$\mathbb{F}_8$	ビット列
0	000
1	001
$\alpha$	010
$\alpha+1$	011
$\alpha^2$	100
$\alpha^2 + 1$	101
$\alpha^2 + \alpha$	110
$\alpha^2 + \alpha + 1$	111

このような対応を与えることで、2つのシンボルの和は対応するビット列のXOR演算となるのでコンピューターで簡単に計算できる。積は簡単に計算というわけにはいかないが、例えば計算結果をあらかじめテーブルに保存しておくなどの方法で高速に計算結果を得ることができる。

さらに、 $\mathbb{F}_q^{\times}$ は巡回群になるので、 $\mathbb{F}_q$ の0以外の元は $\alpha$ の冪乗で表すことができる。例えば $\mathbb{F}_8$ の具体的な構成方法として $\mathbb{F}_2[x] / (x^3 + x + 1)$ という剰余を取る場合、 $\mathbb{F}_8$ の元は以下のように表すことができる。

$\mathbb{F}_8$	$\alpha$ の冪乗で表した場合
1	$\alpha^7$
$\alpha$	$\alpha$
$\alpha+1$	$\alpha^3$
$\alpha^2$	$\alpha^2$
$\alpha^2 + 1$	$\alpha^6$
$\alpha^2 + \alpha$	$\alpha^4$
$\alpha^2 + \alpha + 1$	$\alpha^5$

評価点による方法

まずは最も基本的な方法から説明する。符号化したい $k$ 個のシンボルを多項式の係数と捉えて、データを多項式として表現することを考える。具体的には $m_0, m_1, \cdots, m_{k-1} \in \mathbb{F}_q$ という $k$ 個のシンボルがあったときに、これを以下のように表す。

$\displaystyle{ m(x) = \sum_{i=0}^{k-1} m_i x^i }$

このとき、 $\mathbb{F}_q$ の相異なる $n$ 個の元 $a_0, a_1, \cdots, a_{n-1}$ をそれぞれ $m(x)$ に代入して得られる $n$ 個のシンボル $(m(a_0), m(a_1), \cdots, m(a_{n-1}))$ がRS符号となる。

ずいぶんとあっけないが、これでちゃんと $n-k$ 個までのデータの消失に耐えられるのである。理由は簡単で、 $m(x)$ の係数は全部で $k$ 個あるので、 $k$ 本の式があれば連立方程式を解くことで $m(x)$ を復元できるというわけである。

基本的にはこれだけのことであるが、ここで気を付けないといけないことが2つある。一つは $\mathbb{F}_q$ にちゃんと $n$ 個以上の元が含まれていなければならないということである。さもなければ相異なる $n$ 個の点を選ぶことができない。これより、 $n \le q$ である必要がある。

もう一つは $a_i$ として0を選ぶと良くないことが起き得るということである。例えばいくつかのデータが欠けた状態で $m(0) = m_0$ を含む連立方程式から元データを復元したい場合、もし $m_0$ が欠けずに残っているデータだった場合にはこれは恒等式になってしまい、情報が増えない。結果としてデータを復元するための評価点が不足してしまう。そのため、結局 $n < q$ である必要がある。

組織符号

先ほど述べた方法で符号化と復号はできるのだが、これには一つ問題がある。それは復号のために毎回複数のデータの読み出しと連立方程式を解くための計算が必要ということである。分散ストレージに応用することを考えると、これはデータを一つ読むたびに複数ノードに通信をしてデータをk個かき集める必要があることを意味し、レスポンスの悪化を招く要因となり得る。

そこで、RS符号を組織符号にすることを考えてみる。組織符号とは符号化されたシンボル列の中に元のデータが直接埋め込まれるような符号である。RS符号を組織符号にするためには、符号化したい $k$ 個のシンボルを $m(x)$ の係数にするのではなく、 $m_i = f(a_i) (i=0, 1, \cdots, k-1)$ となるような $f(x)$ を求めればよいことになる。こうすれば、データ消失が起きない限りは単純に符号化された最初の $k$ 個のデータがそのまま元データになる。また、 $i$ 番目のデータが消失した場合は先ほどと同じように残っているデータから $f(x)$ の係数を導き出し、 $f(a_i)$ の値を求めればよい。

生成行列による方法

理論的にはこれでおしまいなのだが、ここまでの話をコンピューターで扱おうとすると結構めんどくさい。RS符号をコンピューターで扱いやすくするために、ここまでの話を行列とベクトルの言葉で書き直してみよう。

まずは組織符号ではない通常のRS符号の方から考える。 $k$ 個のシンボル $m_0, m_1, \cdots, m_{k-1}$ の符号化は以下のように書ける。

$\displaystyle{ \begin{pmatrix} 1 & a_0 & \cdots & a_0^{k-1} \\ 1 & a_1 & \cdots & a_1^{k-1} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & a_{n-1} & \cdots & a_{n-1}^{k-1} \\ \end{pmatrix} \begin{pmatrix} m_0 \\ m_1 \\ \vdots \\ m_{k-1} \end{pmatrix} }$

上式で符号化対象のシンボルのベクトルに左からかけている行列のことを生成行列と呼ぶ。記載の簡略化のために、以降では生成行列のことを $G$ と書く。

データの復号の際には失われていない符号の中から $k$ 個を選び、それに対応する $G$ の行を $k$ 個集めた行列 $G_k$ を作る。そして、生き残っている符号を縦に並べた列ベクトルに $G_k^{-1}$ を掛けることで元のデータが復元できる。

一点だけ補足しておくと、この議論は $G_k$ が正則でなければ成り立たない。今、 $G$ および $G_k$ はヴァンデルモンド行列と呼ばれる形になっており、特に $G_k$ は正方行列である。詳細はWikipedia[2]を見て欲しいが、 $a_0, a_1, \cdots, a_{n-1}$ が相異なることから $G_k$ は正則になるので問題ないと言える。

組織符号

続いて組織符号バージョンのRS符号を行列とベクトルの言葉で書き直してみよう。そのためには何らかの方法で生成行列を以下の形式に変換できればよい。

$\displaystyle{ G' = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \\ g_{k, 0} & g_{k, 1} & \cdots & g_{k, k-1} \\ \vdots & \vdots & & \vdots \\ g_{n-1, 0} & g_{n-1, 1} & \cdots & g_{n-1, k-1} \\ \end{pmatrix} }$

ここで示した行列 $G'$ はWikipedia[1]に書いてあるものと異なる。Wikipediaの方は生成行列の行と列の数が明らかにおかしいので、普通に間違っているように見える。ただ、どうも符号理論の世界では符号を横ベクトルとして行列の左から掛ける流儀が主流らしく、そう思えばあながち間違っているとも言えない。少なくとも一つのセクションの中で記法が混在しているのは良くないだろう。

このような行列を作るためには元の生成行列 $G$ の左から以下のような行列を掛ければよい。

$\displaystyle{ \begin{pmatrix} S^{-1} & O_{k, n-k} \\ O_{n-k, k} & E_{n-k} \\ \end{pmatrix} }$

ただし、 $S$ は $G$ の最初の $k$ 行を取ってきた行列（このような行列は先ほど説明した通り正則）、 $O_{m, n}$ は $m$ 行 $n$ 列の零行列、そして $E_n$ は $n$ 次単位行列である。

いきなり $G$ にこんな行列を掛けてしまって大丈夫なのか？というのが気になるところである。実はこの行列を掛けることで「任意の $k$ 行を選んで作られる行列が正則になる」という性質が壊れるケースがある。それは評価点として0を含めてしまうケースである。実際にやってみると問題となるケースが分かるのだが、ここでは細かい説明は割愛し、とにかく0は選ばない方がよいということだけ述べるに留める。

また、ここでやっていることは評価点による方法の組織符号バージョンと微妙に異なる。最初の $k$ 個の符号は組織符号であることから当然一致するが、残り $n-k$ 個の符号の作り方が異なっている。ただ、そこはあまり重要ではなく、とにかく $n-k$ までのデータを失ってもデータが復号できるという性質が担保されていればよいということで、計算しやすい方法を取った。

生成多項式による方法

最後に生成多項式と呼ばれる多項式を使った符号化法について説明する。 $m(x) = \sum_{i=0}^{k-1} m_i x^i$ とし、 $a_0, a_1, \cdots, a_{n-k-1}$ を $\mathbb{F}_q$ の相異なる元とする。このとき以下のような多項式 $g(x)$ を考える。

$\displaystyle{ g(x) = \prod_{i=0}^{n-k-1} (x - a_i) }$

これを用いて以下のような多項式 $c(x)$ を考える。

$\displaystyle{ c(x) = m(x)g(x) }$

$c(x)$ の係数並べたものが求める符号である。復号の際には $c(x)/g(x)$ を計算すればよい。また、 $c(a_i) = 0 (i=0, 1, \cdots, n-k-1)$ であることから $n-k$ 元の連立方程式を立てられるので、符号のシンボルを $n-k$ 個まで失っても $c(x)$ を復元できる。

ただし、 $a_i$ として0を含めてしまうと復号できないケースがあるので注意が必要である。例えば $c(x)$ の定数項に相当する符号シンボルが欠けていないケースを考える。このとき、 $c(0) = 0$ なので $c(x)$ の定数項が0だということが初めから分かっていることになる。そのため $c(0) = 0$ という式は恒等式となり、ここからは欠けているシンボルの情報が得られない。

他の節でも似たようなことを述べたが、 $a_i$ として0は選ぶべきではない。

組織符号

$m(x)x^{n-k}$ という式を考える。これを $g(x)$ で割った余りを $r(x)$ とすると、 $m(x)x^{n-k} - r(x)$ は $g(x)$ で割り切れる。 $r(x)$ の次元は高々 $n-k-1$ なので、 $c(x)$ の $n-1$ 次から $n-k$ 次までの項の係数はそのまま $m(x)$ の係数（つまり元のデータ）に一致する。復号は組織符号でない場合と同様に $c(x)$ の係数を計算してから最初の $k$ 個のシンボルを選択すればよい。

計算例

ここまでに説明した符号化方法を用いて実際にRS符号を求めてみよう。以下では $q=8, n=6, k=3$ のケースを考える。また、符号化したいデータは一律で $\alpha, \alpha^4, \alpha^6$ とする。記事が無用に長くなるのを避けるために、ここでは組織符号バージョンの例だけを示す。

評価点による方法の例

多項式 $f(x) = f_0 + f_1 x + f_2 x^2$ として、 $\mathbb{F}_8$ の相異なる3つの点を適当に選んで代入すると値がそれぞれ $\alpha, \alpha^4, \alpha^6$ になるようなものを探す。ここでは $1, \alpha, \alpha^2$ を取ることにすると、以下のような連立方程式が得られる。

$\displaystyle{ \begin{eqnarray} \alpha &=& f_0 + f_1 + f_2 \\ \alpha^4 &=& f_0 + \alpha f_1 + \alpha^2 f_2 \\ \alpha^6 &=& f_0 + \alpha^2 f_1 + \alpha^4 f_2 \end{eqnarray} }$

これを解くことで $f(x) = \alpha^5 + \alpha^6 x$ となる。2次の係数が0になってしまったが、そういうこともある。全部で6つの評価点が欲しいので、適当にもう3つの点 $\alpha^3, \alpha^5, \alpha^6$ での値も計算しておくと、それぞれ $\alpha^3, 1, 0$ となる。これより符号は以下のようになる。

$\displaystyle{ (\alpha, \alpha^4, \alpha^6, \alpha^3, 1, 0) }$

続いて復号をしてみよう。ここでは0, 1, 4番目のデータが欠損している状況を考える。符号としては以下のような状況である。

$\displaystyle{ (\_, \_, \alpha^6, \alpha^3, \_, 0) }$

3つある元データのシンボルのうち（0始まりで数えて）2番目のものは欠損せずに残っているので、残りの2つのシンボルを復元したい。そのためには $f(x)$ の係数 $f_0, f_1, f_2$ を取得できればよい。残っている2, 3, 5番目のデータはそれぞれ $\alpha^2, \alpha^3, \alpha^6$ を代入することで得られたものだったので、以下の連立方程式を解けばよい。

$\displaystyle{ \begin{eqnarray} \alpha^6 &=& f_0 + \alpha^2 f_1 + \alpha^4 f_2 \\ \alpha^3 &=& f_0 + \alpha^3 f_1 + \alpha^6 f_2 \\ 0 &=& f_0 + \alpha^6 f_1 + \alpha^5 f_2 \end{eqnarray} }$

ただし、 $\alpha^{12} = \alpha^5$ を使った。これを解くと $f(x)$ が復元できるので、あとは0, 1番目の符号の生成に使った $1, \alpha$ を用いて $f(1), f(\alpha)$ を計算すれば元のデータが復元できる。

生成行列による方法の例

評価点として $1, \alpha, \alpha^2, \alpha^3, \alpha^5, \alpha^6$ を選んだ場合、組織符号でない場合の生成行列 $G$ は以下のようになる。

$\displaystyle{ \begin{pmatrix} 1 & 1 & 1 \\ 1 & \alpha & \alpha^2 \\ 1 & \alpha^2 & \alpha^4 \\ 1 & \alpha^3 & \alpha^6 \\ 1 & \alpha^5 & \alpha^3 \\ 1 & \alpha^6 & \alpha^5 \end{pmatrix} }$

$S$ は $G$ の最初の3行を取ったものなので、 $S^{-1}$ は以下のようになる。

$\displaystyle{ \begin{pmatrix} \alpha & \alpha^2 & \alpha^5 \\ \alpha^2 & \alpha^6 & 1 \\ \alpha^5 & 1 & \alpha^4 \end{pmatrix} }$

よって組織符号版の生成行列 $G'$ は以下のようにして得られる。

$\displaystyle{ \begin{eqnarray} G' &=& \begin{pmatrix} \alpha & \alpha^2 & \alpha^5 & 0 & 0 & 0 \\ \alpha^2 & \alpha^6 & 1 & 0 & 0 & 0 \\ \alpha^5 & 1 & \alpha^4 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} G \\ &=& \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & \alpha^3 & \alpha^6 \\ 1 & \alpha^5 & \alpha^3 \\ 1 & \alpha^6 & \alpha^5 \end{pmatrix} \end{eqnarray} }$

よって符号は以下のようになる。

$\displaystyle{ G' \begin{pmatrix} \alpha \\ \alpha^4 \\ \alpha^6 \end{pmatrix} = \begin{pmatrix} \alpha \\ \alpha^4 \\ \alpha^6 \\ \alpha^2 \\ \alpha \\ \alpha^5 \end{pmatrix} }$

続いて復号をしてみよう。先ほどと同じように0, 1, 4番目のデータが欠損している状況を考える。このとき、 $G'$ の残っている2, 3, 5行目をかき集めた行列に元データのシンボル列を掛けたものが残っている2, 3, 5番目の符号シンボルになることを考えると、以下のように復号できる。

$\displaystyle{ \begin{eqnarray} \begin{pmatrix} 0 & 0 & 1 \\ 1 & \alpha^3 & \alpha^6 \\ 1 & \alpha^6 & \alpha^5 \end{pmatrix} \begin{pmatrix} m_0 \\ m_1 \\ m_2 \end{pmatrix} &=& \begin{pmatrix} \alpha^6 \\ \alpha^2 \\ \alpha^5 \end{pmatrix} \\ \begin{pmatrix} m_0 \\ m_1 \\ m_2 \end{pmatrix} &=& \begin{pmatrix} 0 & 0 & 1 \\ 1 & \alpha^3 & \alpha^6 \\ 1 & \alpha^6 & \alpha^5 \end{pmatrix}^{-1} \begin{pmatrix} \alpha^6 \\ \alpha^2 \\ \alpha^5 \end{pmatrix} \\ \begin{pmatrix} m_0 \\ m_1 \\ m_2 \end{pmatrix} &=& \begin{pmatrix} \alpha^2 & \alpha^2 & \alpha^4 \\ \alpha^4 & \alpha^3 & \alpha^3 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} \alpha^6 \\ \alpha^2 \\ \alpha^5 \end{pmatrix} \\ \begin{pmatrix} m_0 \\ m_1 \\ m_2 \end{pmatrix} &=& \begin{pmatrix} \alpha \\ \alpha^4 \\ \alpha^6 \end{pmatrix} \end{eqnarray} }$

生成多項式による方法の例

元データを表す多項式は以下のようになる。
$\displaystyle{ m(x) = \alpha x^2 + \alpha^4 x + \alpha^6 }$

他の例に倣うのであれば $m(x) = \alpha + \alpha^4 x + \alpha^6 x^2$ とすべきところだが、こうすると $x^{n-k}$ を掛けた後の項の並びがややこしくなるのであえてこうしている。符号の並びを逆にしても復号できないということはないため問題ない。

$\mathbb{F}_8$ から $n-k$ 個（つまり3個）サンプリングする元として $1, \alpha, \alpha^2$ を使った場合、生成多項式 $g(x)$ は以下のようになる。

$\displaystyle{ g(x) = (x - 1)(x - \alpha)(x - \alpha^2) }$

このとき、 $r(x)$ は以下のようになる。

$\displaystyle{ \begin{eqnarray} r(x) &=& m(x)x^3 \bmod g(x) \\ &=& \alpha^4 x^2 + \alpha^4 x + 1 \end{eqnarray} }$

これより $c(x)$ は以下のようになる。

$\displaystyle{ \begin{eqnarray} c(x) &=& m(x)x^3 + \alpha^4 x^2 + \alpha^4 x + 1 \\ &=& \alpha x^5 + \alpha^4 x^4 + \alpha^6 x^3 + \alpha^4 x^2 + \alpha^4 x + 1 \end{eqnarray} }$

よって符号は $(\alpha, \alpha^4, \alpha^6, \alpha^4, \alpha^4, 1)$ となる。

続いて復号をしてみよう。先ほどと同じように0, 1, 4番目のデータが欠損している状況を考える。 $c(x)$ が $g(x)$ で割り切れることから、 $g(x)$ の根 $1, \alpha, \alpha^2$ を代入すると0になるはずである。このことから以下のような連立方程式が得られる。

$\displaystyle{ \begin{eqnarray} c_5 + c_4 + \alpha^6 + \alpha^4 + c_1 + 1 &=& 0 \\ \alpha^5 c_5 + \alpha^4 c_4 + \alpha^2 + \alpha^6 + \alpha c_1 + 1 &=& 0 \\ \alpha^3 c_5 + \alpha c_4 + \alpha^5 + \alpha + \alpha^2 c_1 + 1 &=& 0 \end{eqnarray} }$

これを解くことで欠損していた符号シンボルが得られる。

異なる符号化方法によって得られる符号の間の関係

計算例を見ると分かるのだが、符号化方法を変えると同じデータに対して全く異なる符号が得られる。にも拘わらず、本稿で紹介した手法によって得られる符号を全てRS符号と呼ぶのはいかがなものだろうか？

調査の結果、符号に関して「等価」という概念があるらしいことが分かった[4].

等価な符号

2つの符号において，それらの生成行列が基本行操作の下に同一のとき，これら2つの符号は等価(equivalent)であるという．

実際に確かめるところまではやれなかったが、本稿で紹介した手法はそれぞれ互いに等価になっているということなのかもしれない。生成多項式による方法については行列なんか出てこないのにどうやって等価であると言えるのか？という疑問が湧くかもしれないが、[1][4]などを見ると生成多項式を用いた方法も行列で表すことができるらしく、その行列表現と他の方法が等価ということではないかと推測している。

ちなみに、ある符号（正確には線形符号）を組織符号に変換したものは元の符号と等価であるらしい[4]。

評価点の選び方

ここまでの説明を読んで、もしかすると私の $\mathbb{F}_q$ からの元の選び方に疑問を持たれた方がいるかもしれない。実際、今回参考にしたWikipedia[1]を見ると、いずれの方法でも $\mathbb{F}_q$ の元を $n$ 個選ぶステップにおいては原始元を $\alpha$ として $1, \alpha, \alpha^2, \cdots, \alpha^{n-1}$ を選択している。暗にこの選択が必須であるような書き方をしている文書もある[5]。

なぜ私がここまでの説明で頑なに $1, \alpha, \alpha^2, \cdots, \alpha^{n-1}$ を使わなかったのかというと、そうしなくても話が成り立ちそうだと思ったからである。実際、先ほどの計算例でも問題なくerasure codingとしての機能を果たせていた。

では $\mathbb{F}_q$ の元の選び方として原始元の連続した冪を取ることが無意味かというと、少なくとも実装上の嬉しさはある。というのも、原始元の冪を順番に使うことにすれば評価点を覚えておく必要がなくなるのである。適当に $n$ 個の評価点を選ぶ場合、どれを使ったのかを覚えておかないと復号できないが、原始元の冪を先頭から順に $n$ 個使うことにするならば、 $n$ と原始元さえ分かればいつでも評価点が導き出せる。というわけで、私のようにひねくれたことはせず、素直に原始元の冪を先頭から順番に使うべきだろう。

RS符号と巡回符号

生成多項式による方法を調べてみると $g(x)$ が $x^n - 1$ を割り切るという条件を課している場合がある。実はこうすることで生成される符号を巡回符号にできるという利点がある[4]。

ただ、巡回符号であることの利点は最後まで良く分からなかった。もしかするとRS符号を誤り訂正符号として使ったときの誤り訂正の計算で意味があるのかもしれないが、少なくともerasure codingとして使う分には $g(x)$ が $x^n - 1$ を割り切るという条件は $n$ を選ぶ自由度が下がる足枷でしかないように思える。

まとめ

本稿ではRS符号をerasure codingの実装として利用する場合の符号化と復号の方式についていくつか説明した。また、各種方式について計算例を示した。符号理論の理解が浅いところが露呈して疑問を払拭しきれないところはあったものの、RS符号の雰囲気はつかめたような気持ちになった。

符号化とか暗号化などの分野は数学が実用に活きてくるという意味で面白い分野だと思う。機会があればまた何か勉強してみたい。

参考

[1] Reed–Solomon error correction - Wikipedia
[2] Vandermonde matrix - Wikipedia
[3] Cyclic code - Wikipedia
[4] https://www.hirasa.mgmt.waseda.ac.jp/lab/ct.pdf
[5] https://www.jstage.jst.go.jp/article/itej/70/7/70_571/_pdf

2025-09-15

円分体のすごさを体感する

整数論

前回の記事では素数 $p$ （正確には $p$ から生成される素イデアル $(p)$ ）が二次体の整数環でさらに分解するかどうかは、適当な自然数 $N$ に対して $p \bmod N$ の値を調べることで分かるという話をした。しかし、 $N$ をどうやって決めればよいのか、また具体的に $p \bmod N$ の値が何だったら分解するのかという点について触れていなかった。

実はこれには円分体が関係している。本稿ではこれらの疑問の答えを解き明かしつつ、円分体のすごさを体感してみたいと思う。

円分体

円分体とは有理数体 $\mathbb{Q}$ に1の原始 $N$ 乗根を添加した体である。定義から明らかなように円分体は代数体である。また、体の拡大 $\mathbb{Q}(\zeta_N)/\mathbb{Q}$ はガロア拡大である。標数が0なので分離拡大なのは良くて、正規拡大であることが示せればよい。この証明は本[1]などを参考にして欲しいが、ざっくり言うと $\zeta_N$ は $x^N -1$ の根であり、 $\zeta_N$ の最小多項式は $x^N -1$ を割り切る。よって最小多項式の根は全て $\zeta_N$ の冪となり、正規拡大であると言える。

$\mathrm{Gal}(\mathbb{Q}(\zeta_N)/\mathbb{Q})$ の特徴

以降は $G_N = \mathrm{Gal}(\mathbb{Q}(\zeta_N)/\mathbb{Q})$ と書くことにする。 $G_N$ は $(\mathbb{Z}/N\mathbb{Z})^{\times}$ と同型である。具体的には $\sigma \in G_N$ に対して $\sigma(\zeta_N) = \zeta_N^n$ であったとすると、 $G_N \ni \sigma \mapsto n \bmod N \in (\mathbb{Z}/N\mathbb{Z})^{\times}$ という対応がある。

$(\mathbb{Z}/N\mathbb{Z})^{\times}$ はアーベル群であるから、円分体は $\mathbb{Q}$ のアーベル拡大である。

円分体と $\mathbb{Q}$ のアーベル拡大の関係

円分体に関して以下の驚くべき定理が知られている[2]。

Kroneckerの定理

次の(i), (ii)は同値である.
(i) $L$ は $\mathbb{Q}$ のAbel拡大である.
(ii) $L \subset \mathbb{Q}(\zeta_N)$ となる自然数 $N$ が存在する.

円分体すごい！なんというパワフルな定理だろうか。これで $\mathbb{Q}$ のアーベル拡大について考えたいときは円分体の部分体だけを気にしておけばよいことになった。

二次体を含む円分体

$\mathbb{Q}$ から二次体への拡大はアーベル拡大であった。よってKroneckerの定理により二次体はある $N$ について円分体 $\mathbb{Q}(\zeta_N)$ の部分体となる。

では、ある二次体 $\mathbb{Q}(\sqrt{m})$ が与えられたときにそれを含む円分体の $N$ を知る方法はあるのだろうか？実はこれには以下に示すような非常にシンプルな法則がある[2]。

$\displaystyle{ N = \begin{cases} |m| & m \equiv 1 \mod 4 のとき \\ 4|m| & m \equiv 2, 3 \mod 4 のとき \end{cases} }$

しかもこの $\mathbb{Q}(\zeta_N)$ は $\mathbb{Q}(\sqrt{m})$ を含む最小の円分体となるらしい。これで冒頭に掲げた2つの疑問のうち1つ目が解決した。

円分体の部分体としての二次体とガロア対応

素イデアル $(p)$ が二次体で相異なる2つの素イデアルの積に分解するかどうかは $G_N$ の部分群と深い関係がある。ガロア対応により $\mathbb{Q}(\zeta_N)$ に部分体として含まれる二次体 $\mathbb{Q}(\sqrt{m})$ に対応する $G_N$ の部分群を $H$ とする。先ほど述べた通り $G_N \cong (\mathbb{Z}/N\mathbb{Z})^{\times}$ なので、この同型により $H$ の元を $(\mathbb{Z}/N\mathbb{Z})^{\times}$ の元と同一視できる。

このとき、 $p$ が $N$ を割り切らずかつ $p \bmod N \in H$ であれば、 $(p)$ は $\mathbb{Q}(\sqrt{m})$ において相異なる素イデアルの積に分解することが知られている。これが2つ目の疑問の答えである。まさか円分体のガロア群と関係があるとは驚きである。円分体すごい！

計算してみよう

いくつかの円分体について、その部分体としての二次体に対応するガロア群の部分群を $G_N \cong (\mathbb{Z}/N\mathbb{Z})^{\times}$ の元として求めてみよう。計算に使ったsageのスクリプトはGitHubに公開した。

以下に実行結果を示す。

sage@c299abb8d2c9:/workspaces/blog/2025$ for m in $(seq -10 10); do echo "== m: ${m} =="; sage -python quad_in_cyclo.py ${m}; done
== m: -10 ==
N: 40
Galois subgroup: Subgroup generated by [(1,3)(2,4)(5,7)(6,8)(9,11)(10,12)(13,15)(14,16), (1,8,3,6)(2,5,4,7)(9,16,11,14)(10,13,12,15), (1,10,3,12)(2,11,4,9)(5,14,7,16)(6,15,8,13)] of (Galois group of x^16 - x^12 + x^8 - x^4 + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 7, 9, 11, 13, 19, 23, 37]
== m: -9 ==
-9 is not square free.
== m: -8 ==
-8 is not square free.
== m: -7 ==
N: 7
Galois subgroup: Subgroup generated by [(1,3,5)(2,4,6)] of (Galois group 6T1 (3[x]2) with order 6 of x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 2, 4]
== m: -6 ==
N: 24
Galois subgroup: Subgroup generated by [(1,2)(3,4)(5,6)(7,8), (1,7)(2,8)(3,5)(4,6)] of (Galois group 8T3 (2[x]2[x]2) with order 8 of x^8 - x^4 + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 5, 7, 11]
== m: -5 ==
N: 20
Galois subgroup: Subgroup generated by [(1,3)(2,4)(5,7)(6,8), (1,6,3,8)(2,7,4,5)] of (Galois group 8T2 (4[x]2) with order 8 of x^8 - x^6 + x^4 - x^2 + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 3, 7, 9]
== m: -4 ==
-4 is not square free.
== m: -3 ==
N: 3
Galois subgroup: Subgroup generated by [()] of (Galois group 2T1 (S2) with order 2 of x^2 + x + 1)
Corresponding element(s) in (Z/NZ)^x: [1]
== m: -2 ==
N: 8
Galois subgroup: Subgroup generated by [(1,4)(2,3)] of (Galois group 4T2 (2[x]2) with order 4 of x^4 + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 3]
== m: -1 ==
N: 4
Galois subgroup: Subgroup generated by [()] of (Galois group 2T1 (S2) with order 2 of x^2 + 1)
Corresponding element(s) in (Z/NZ)^x: [1]
== m: 0 ==
0 is not square free.
== m: 1 ==
m should not be 1 by definition of quadratic field.
== m: 2 ==
N: 8
Galois subgroup: Subgroup generated by [(1,2)(3,4)] of (Galois group 4T2 (2[x]2) with order 4 of x^4 + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 7]
== m: 3 ==
N: 12
Galois subgroup: Subgroup generated by [(1,4)(2,3)] of (Galois group 4T2 (2[x]2) with order 4 of x^4 - x^2 + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 11]
== m: 4 ==
4 is not square free.
== m: 5 ==
N: 5
Galois subgroup: Subgroup generated by [(1,3)(2,4)] of (Galois group 4T1 (4) with order 4 of x^4 + x^3 + x^2 + x + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 4]
== m: 6 ==
N: 24
Galois subgroup: Subgroup generated by [(1,4)(2,3)(5,8)(6,7), (1,6)(2,5)(3,8)(4,7)] of (Galois group 8T3 (2[x]2[x]2) with order 8 of x^8 - x^4 + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 5, 19, 23]
== m: 7 ==
N: 28
Galois subgroup: Subgroup generated by [(1,3,5)(2,4,6)(7,9,11)(8,10,12), (1,8,3,10,5,12)(2,9,4,11,6,7)] of (Galois group of x^12 - x^10 + x^8 - x^6 + x^4 - x^2 + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 3, 9, 19, 25, 27]
== m: 8 ==
8 is not square free.
== m: 9 ==
9 is not square free.
== m: 10 ==
N: 40
Galois subgroup: Subgroup generated by [(1,3)(2,4)(5,7)(6,8)(9,11)(10,12)(13,15)(14,16), (1,5)(2,6)(3,7)(4,8)(9,13)(10,14)(11,15)(12,16), (1,10,3,12)(2,11,4,9)(5,14,7,16)(6,15,8,13)] of (Galois group of x^16 - x^12 + x^8 - x^4 + 1)
Corresponding element(s) in (Z/NZ)^x: [1, 3, 9, 13, 27, 31, 37, 39]
sage@c299abb8d2c9:/workspaces/blog/2025$

例えば $m = -1$ のケースを見てみよう。まず、 $-1 \equiv 3 \mod 4$ なので $N = 4$ である。プログラムの出力が"Corresponding element(s) in (Z/NZ)^x: [1]"となっており、 $p \equiv 1 \mod 4$ のときに $(p)$ が分解することが分かる。これは前回の記事で説明した内容と一致している。

また、 $m = -5$ のケースでは $N = 20$ かつ"Corresponding element(s) in (Z/NZ)^x: [1, 3, 7, 9]"となっている。試しに素イデアルの分解を試みると以下のようになる。

sage: K = QuadraticField(-5)
sage: OK = K.ring_of_integers()
sage: for p in [2, 5, 41, 3, 7, 29, 11, 13, 17, 19]:
....:     print("p: {}".format(p))
....:     I = OK.ideal(p)
....:     I.factor()
....: 
p: 2
(Fractional ideal (2, a + 1))^2
p: 5
(Fractional ideal (a))^2
p: 41
(Fractional ideal (a + 6)) * (Fractional ideal (a - 6))
p: 3
(Fractional ideal (3, a + 1)) * (Fractional ideal (3, a + 2))
p: 7
(Fractional ideal (7, a + 3)) * (Fractional ideal (7, a + 4))
p: 29
(Fractional ideal (-2*a + 3)) * (Fractional ideal (2*a + 3))
p: 11
Fractional ideal (11)
p: 13
Fractional ideal (13)
p: 17
Fractional ideal (17)
p: 19
Fractional ideal (19)
sage:

2, 5は $N=20$ を割り切るため事情が異なるが、それ以外の素数に関しては確かに $p \equiv 1, 3, 7, 9 \mod 20$ のときだけ相異なる素イデアルの積に分解していることが分かる。

ちなみに、2, 5についてはよく見ると素イデアルの2乗の形になっているが、これは偶然ではない。一般に $N$ を割り切る素数に関してはこういう現象が起こる。詳しいことは本[2]などを参照されたい。

まとめ

本稿では前回の記事で積み残していた $N$ の決め方と $p \bmod N$ の値がどうなっていれば素イデアル $(p)$ が二次体の整数環で分解するのかについて述べた。これには円分体とそのガロア群が密接に関わっていることが分かった。

ガロア理論はそれ自体がすでに面白いと思うのだが、それがさらに整数論において重要な役割を担うというのは驚くべきことである。正直ガロア理論を勉強したのが大昔で結構忘れていることが多かったのだが、いろいろ復習しつつsageで実際にプログラムを書いてみたことで理解が深まったのは良かった。

また、これまで円分体というのは「なんかそういう体があるのね」くらいにしか思っていなかったが、アーベル拡大に関して極めて重要な存在であることが分かった。今後は「円分体様～」と慕う気持ちで生きていこうと思う。

参考

[1] 代数学2 環と体とガロア理論｜日本評論社
(第2版が出ているので、もし購入される場合はそちらが良いだろう。）
[2] 数論I／加藤和也, 黒川信重, 斎藤毅｜岩波オンデマンドブックス - 岩波書店

2025-09-07

素数が複素数の範囲で分解することの背後にある理論に触れる

整数論

整数論に再チャレンジ中

ここのところ整数論の勉強に再チャレンジしている。自分のXでの投稿を見返すと、どうやら2016年から2017年頃に一度整数論の勉強をしようとしていたようだ。しかし、当時は整数論のあまりの難しさに途中で諦めてしまった。

時は流れて2025年、世はまさに大AI時代である。ありがたいことにChatGPTなどのAIに聞けば数学でも何でも分からないことはだいたい教えてくれる。AIのおかげで自分の整数論の再チャレンジは以前よりスムーズに進んでいる。

一方、AIに聞けば何でも分かってしまうので、人々がブログを読むモチベーションはもしかしたら失われつつあるかもしれない。ブログを書く側の心境としては勉強のアウトプットという側面もあるのだが、そこに読者への配慮が不在ならばわざわざ公開する意義は薄かろう。

私が思うに、こんな時代にブログを読む動機があるとするならば、それは恐らく情報の最新性か、あるいは読み物としての面白さのいずれかによるものではなかろうか。数学の世界で、まして素人である自分が前者のメリットをもたらすのは難しいことであるから、多少なりとも後者のメリットを出せるよう、日々の勉強の記録を今後もブログに書き記していきたいと思う。

というわけで、本稿では複素数の範囲で分解する素数というありふれた題材の背後にある理論について紹介してみようと思う。

分解する素数と分解しない素数

5は素数である。これは整数環 $\mathbb{Z}$ における話なのだが、複素数の中にも $\mathbb{Z}$ の類似物がある。それはガウス整数環と呼ばれ、 $\mathbb{Z}[\sqrt{-1}] = \{a + b\sqrt{-1} \mid a, b \in \mathbb{Z} \}$ という集合である。 $b=0$ の場合を考えると容易に分かるように、 $\mathbb{Z}$ は $\mathbb{Z}[\sqrt{-1}]$ の中に自然に埋め込まれる。では、素数5が $\mathbb{Z}[\sqrt{-1}]$ に埋め込まれたとき、果たしてまだ「素数としての性質」を持ち続けることができるだろうか？

ここで言う「素数としての性質」をちゃんと定義すると、それは環論で言うところの素元というものになる（素元の定義は適当な環論の教科書を参照して欲しい）。5に関して言うと、 $5 = (1+2\sqrt{-1})(1-2\sqrt{-1})$ という分解が存在する。既約元でなければ素元ではないため、5は $\mathbb{Z}[\sqrt{-1}]$ では素元ではない。一方、5の因数となっている $1\pm 2\sqrt{-1}$ は $\mathbb{Z}[\sqrt{-1}]$ における素元となっている。

では他の素数はどうだろうか？例えば3, 7, 11は $\mathbb{Z}[\sqrt{-1}]$ でも素元となっている。従って既約元なのでこれ以上の単元でない元同士の積には分解できない。一方、13は $13 = (2+3\sqrt{-1})(2-3\sqrt{-1})$ という分解が存在するため $\mathbb{Z}[\sqrt{-1}]$ の素元ではない。

良く知られている事実として、素数 $p$ が $\mathbb{Z}[\sqrt{-1}]$ における素元となるかどうかは $p \bmod 4$ の値で決まる。これが1ならばさらなる分解が存在するし、3ならば $p$ は $\mathbb{Z}[\sqrt{-1}]$ でも素元である。なお、 $p \equiv 0 \mod 4$ の場合は当然素数にならないので無視してよい。 $p \equiv 2 \mod 4$ となる素数は2だけだが、 $2=(1+\sqrt{-1})(1-\sqrt{-1})$ となるのでこれは素元ではない（※追記1も参照）。

2はさておき、奇素数に関してはこのようにシンプルなルールが存在するというのは何とも神秘的である。これは偶然なのだろうか？以下でそれを解き明かしていこう。

二次体

さきほどは $\mathbb{Z}$ を $\mathbb{Z}[\sqrt{-1}]$ に広げたときの分解について考えた。では、他の拡大の仕方についてはどうなるだろうか？

この疑問に答える前に必要な用語の説明をする。有理数体 $\mathbb{Q}$ の有限次拡大体は代数体と呼ばれる。 $K$ を代数体とすると、 $K$ において整数っぽい性質を持つような環は代数体の整数環と呼ばれ、これを $O_K$ と書く。「整数っぽい」という言い方はあまりにあいまいなので、代数体の整数環の正式な定義を本[1]から引用する。

代数体の整数環

$O_K$ は, $K$ の元 $\alpha$ で, ある $n \ge 1$ と $c_1, \cdots , c_n \in \mathbb{Z}$ についての
$\displaystyle{ \alpha^n + c_1 \alpha^{n-1} + \cdots + c_n = 0 }$
の形の式をみたすもの全体である.（ここでのポイントは, この式の最高次（ $n$ 次）の係数が1になっていることである.）

例えば $\mathbb{Q}$ に $\sqrt{-1}$ を添加した体 $\mathbb{Q}(\sqrt{-1})$ における整数環はガウス整数環 $\mathbb{Z}[\sqrt{-1}]$ となる。より一般に $\mathbb{Q}(\sqrt{m})$ ( $m$ は1以外の平方数では割れず、かつ1ではない) という形の拡大体を考えると、その整数環は以下のようになる[1]。

$\displaystyle{ O_K = \begin{cases} \mathbb{Z}[\sqrt{m}] = \{a+b\sqrt{m} ; a, b \in \mathbb{Z}\} & m \equiv 2, 3 \mod 4のとき \\ \mathbb{Z}\left[\frac{1+\sqrt{m}}{2} \right] = \left\{ a + b\frac{1+\sqrt{m}}{2} ; a, b \in \mathbb{Z} \right\} & m \equiv 1 \mod 4のとき \end{cases} }$

$\mathbb{Q}(\sqrt{m})$ は拡大次数が2であるため二次体と呼ばれている。

二次体の整数環における素数の分解（うまくいく場合）

ガウス整数環で見たような素数の分解の議論は二次体の整数環に対しても行うことができる。いくつか例を見てみよう。

$\mathbb{Q}(\sqrt{3})$ の場合

$p \equiv 1, 11 \mod 12$ のとき、 $p$ は $O_{\mathbb{Q}(\sqrt{3})}$ で相異なる素元の積に分解する。以下に例を示す。

$\displaystyle{ \begin{eqnarray} 13 &=& -(\sqrt{3} - 4)(\sqrt{3} + 4) \\ 23 &=& (3 \sqrt{3} + 2)(3 \sqrt{3} - 2) \end{eqnarray} }$

$p \equiv 5, 7 \mod 12$ のとき、 $p$ は $O_{\mathbb{Q}(\sqrt{3})}$ でも素元となる。また、 $p = 3$ のときは $3 = \sqrt{3}^2$ となり、素元の二乗となる。 $p = 2$ のときは $2 = (-\sqrt{3} + 2)(\sqrt{3} + 1)^2$ となり、素元の二乗に単元を掛けた形になる。

$\mathbb{Q}(\sqrt{5})$ の場合

$p \equiv 1, 4 \mod 5$ のとき、 $p$ は $O_{\mathbb{Q}(\sqrt{5})}$ で相異なる素元の積に分解する。以下に例を示す。ただし、 $\omega = \frac{1+\sqrt{5}}{2}$ , $\overline{\omega} = 1 - \omega = \frac{1 - \sqrt{5}}{2}$ とする。

$\displaystyle{ \begin{eqnarray} 11 &=& -(1 - 3\omega)(1 - 3\overline{\omega}) \\ 19 &=& -(1-4\omega)(1 - 4 \overline{\omega}) \end{eqnarray} }$

$p \equiv 2, 3 \mod 5$ のとき、 $p$ は $O_{\mathbb{Q}(\sqrt{5})}$ でも素元となる。また、 $p = 5$ のときは $5 = \sqrt{2\omega-1}^2$ となり、素元の二乗となる。

$\mathbb{Q}(\sqrt{-3})$ の場合

$p \equiv 1 \mod 3$ のとき、 $p$ は $O_{\mathbb{Q}(\sqrt{-3})}$ で相異なる素元の積に分解する。以下に例を示す。ただし、 $\omega = \frac{1+\sqrt{-3}}{2}$ , $\overline{\omega} = 1 - \omega = \frac{1 - \sqrt{-3}}{2}$ とする。

$\displaystyle{ \begin{eqnarray} 7 &=& (3 \omega - 1)(3\overline{\omega} - 1) \\ 13 &=& (\omega + 3)(\overline{\omega} + 3) \end{eqnarray} }$

$p \equiv 2 \mod 3$ のとき、 $p$ は $O_{\mathbb{Q}(\sqrt{-3})}$ でも素元となる（奇素数だけでなく2でも同様）。また、 $p = 3$ のときは $3 = -(2\omega-1)^2$ となり、素元の二乗に単元を掛けた形になる。

二次体の整数環における素数の分解（うまくいかない場合）

ここまでの例を見る限り、どんな二次体の整数環でも、適当な自然数 $N$ に対して $p \bmod N$ の値を調べれば、 $p$ が分解するかどうかが分かりそうに思えてくる。

しかし、残念ながらそういうことにはならない。例えば $m=-5$ の場合を考えると、実は $\mathbb{Q}(\sqrt{-5})$ の整数環は一意分解整域になっておらず、一意な素元分解が成り立たない（一意分解整域の説明は適当な環論の教科書を参照して欲しいが、ざっくり言うと環の0でない任意の元を素元の積として一意に表せるというもの）。

例えば、6の分解の仕方は以下のように2通りある。

$\displaystyle{ 6 = 2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5}) }$

イデアル類群と単数群

こうなると一気に世界が汚く思えてくるが、悲観するのはまだ早い。実は素元分解を考える代わりに、素数 $p$ によって生成されるイデアルの素イデアル分解というものを考えると、これは代数体の整数環に対しては常に一意な分解が行えることが知られている。

こう聞くと「でも結局それって素数そのものを分解してるわけじゃないじゃん」という気持ちになる。それはそうなのだが、話をより建設的な方向に向けるために、イデアルと数の様子がどれくらい異なるかを表す指標を作ることを考えてみる。

イデアルと数（正確には代数体の元）というのは全く異質のものであるように見えるわけだが、数からイデアルへの写像を構成することで両者の元の対応付けができる。それらが互いにどれくらい似通っているかはその写像の核と余核を見ることで大体分かる。核も余核も自明に近ければ近いほどイデアルと数の様子は似通ってくるというわけである。

しかし、ここで1つ困ったことがある。代数体の整数環のイデアル全体の集合には積の演算を定めることができるものの、逆元が必ずしも存在しないため群になっていない。このままでは剰余を考えることができず、余核を定められない。

そこで、イデアルの概念を拡張した分数イデアルというものを考える。定義を本[1]から引用する。

分数イデアル

$K$ を代数体とする. $K$ の部分集合 ${\bf a}$ が $O_K$ の分数イデアル (fractional ideal) であるとは, 次の同値な条件(i), (ii)のうちの1つ（したがって両方）をみたすことである.
(i) $O_K$ の0でない元 $c$ があって, $c{\bf a}$ は $O_K$ の0でないイデアルになる.
(ii) ${\bf a}$ は $K$ の0でない有限生成部分 $O_K$ 加群である.
$K^{\times}$ の元 $\alpha$ に対し, 分数イデアル $\alpha O_K$ を $(\alpha)$ と書く. $(\alpha) (\alpha \in K^{\times})$ の形の分数イデアルを主分数イデアル (principal fractional ideal) という.

代数体の整数環における分数イデアル全体の集合は群を成す（申し訳ないが積の演算と逆元の定め方については本[1]やWikipedia[2]などを参照のこと）。さらに素晴らしいことに、分数イデアルに対しても素イデアル分解が成り立つのである。このことを示す定理を本[1]より引用する。

分数イデアルの素イデアル分解

$K$ を代数体とし, ${\bf a}$ を $O_K$ の分数イデアルとする. ${\bf a}$ は
$\displaystyle{ {\bf a} = \prod_{\bf p} {\bf p}^{e_{\bf p}} }$
ここに, ${\bf p}$ は $O_K$ のすべての0でない素イデアルを走り, $e_{\bf p} \in \mathbb{Z}$ で, 有限個の ${\bf p}$ を除いて $e_{\bf p} = 0$ , の形にただひととおりにあらわされる.

ここで、 $\alpha \mapsto (\alpha)$ という写像を考えると、これが先ほど述べた数から（分数）イデアルへの写像となる。この写像の核を単数群、余核をイデアル類群と呼ぶ。さらにイデアル類群の位数を代数体の類数と呼ぶ。

類数が1の場合は数とイデアルの差がとても小さいと言える。実際、類数が1であることと代数体の整数環が一意分解整域であることは同値であることが知られており、数の世界においても一意な分解が行える。

素数の分解の様子が $p \bmod N$ の値によって判定できるための条件

代数体の整数環のイデアルが素イデアルの積に一意に分解できることは分かった。次に気になるのは素数 $p \in \mathbb{Z}$ によって生成されるイデアル $(p)$ （正確には $(p) O_K$ のようにして $O_K$ のイデアルに昇格させたもの）がどのように素イデアル分解されるか？であろう。果たして $(p)$ の分解の様子はいつでも適当な自然数 $N$ に対して $p \bmod N$ の値によって決まるのだろうか？

残念ながらそうはならない。しかし、そうなるための条件は知られている。ちゃんと説明するには私の実力がまだ足りないのだが、ざっくり言うと代数体が $\mathbb{Q}$ のアーベル拡大であれば素数の分解の様子が $p \bmod N$ の値によって決まることが知られている。アーベル拡大とは、ガロア拡大であり、かつガロア群がアーベル群になるような体の拡大である。

ところで二次体 $K$ に対して $\mathrm{Gal}(K/\mathbb{Q})$ は必ず $\mathbb{Z}/2\mathbb{Z}$ と同型になる。これはアーベル群であるから二次体は $\mathbb{Q}$ のアーベル拡大である。これより二次体においては素数（から生成されたイデアル）の分解の仕方が必ず $p \bmod N$ の値によって決まる。

素数 $p$ がガウス整数環の素元かどうかを $p \bmod 4$ の値によって判定できた理由

以上の議論により、ある素数 $p$ がガウス整数環の素元かどうかを $p \bmod 4$ の値によって判定できた理由は「 $\mathbb{Q}(\sqrt{-1})$ が $\mathbb{Q}$ のアーベル拡大であり、かつ類数が1、すなわちガウス整数環 $O_{\mathbb{Q}(\sqrt{-1})}$ が一意分解整域であるため」ということが分かった。

まとめ

本稿では素数がガウス整数環においても分解するか？という話から始まり、どういうときに素数 $p$ やイデアル $(p)$ の分解の様子が $p \bmod N$ の値によって決まるのか？について説明した。素数がガウス整数環で分解する条件はずっと以前から知っていたが、その背景にこのような豊かな理論があったとは恐れ入った。

本稿では $N$ がどのようにして決まるのか？という話ができなかった。これについても非常に面白い話があるのでまたの機会に記事を書いてみたい。また、二次体以外の拡大体だとどうなるのかとか、 $\mathbb{Q} \subset K \subset L$ のような体 $K, L$ について、 $K$ の素イデアルが $L$ でどのように分解するのかという話もある。ここまで行くともはや類体論そものの話になってくるので、本[1]などを読まれると良いだろう。

おまけ：sageによる二次体の計算

いろいろな二次体の類数、イデアル類群、および単数群をsageで計算してみた。プログラムは以下の通り。

for n in range(-19, 20):
    if n == 1:
        continue
    if not Integer(n).is_squarefree():
        continue
    print("n: {}".format(n))
    K.<a> = QuadraticField(n)
    print("class number: {}".format(K.class_number()))
    print("class group: {}".format(K.class_group()))
    print("unit group: {}".format(K.unit_group()))

実行結果を以下に示す。

n: -19
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 + 19 with a = 4.358898943540674?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 19 with a = 4.358898943540674?*I
n: -17
class number: 4
class group: Class group of order 4 with structure C4 of Number Field in a with defining polynomial x^2 + 17 with a = 4.123105625617660?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 17 with a = 4.123105625617660?*I
n: -15
class number: 2
class group: Class group of order 2 with structure C2 of Number Field in a with defining polynomial x^2 + 15 with a = 3.872983346207417?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 15 with a = 3.872983346207417?*I
n: -14
class number: 4
class group: Class group of order 4 with structure C4 of Number Field in a with defining polynomial x^2 + 14 with a = 3.741657386773942?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 14 with a = 3.741657386773942?*I
n: -13
class number: 2
class group: Class group of order 2 with structure C2 of Number Field in a with defining polynomial x^2 + 13 with a = 3.605551275463990?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 13 with a = 3.605551275463990?*I
n: -11
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 + 11 with a = 3.316624790355400?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 11 with a = 3.316624790355400?*I
n: -10
class number: 2
class group: Class group of order 2 with structure C2 of Number Field in a with defining polynomial x^2 + 10 with a = 3.162277660168380?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 10 with a = 3.162277660168380?*I
n: -7
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 + 7 with a = 2.645751311064591?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 7 with a = 2.645751311064591?*I
n: -6
class number: 2
class group: Class group of order 2 with structure C2 of Number Field in a with defining polynomial x^2 + 6 with a = 2.449489742783178?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 6 with a = 2.449489742783178?*I
n: -5
class number: 2
class group: Class group of order 2 with structure C2 of Number Field in a with defining polynomial x^2 + 5 with a = 2.236067977499790?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 5 with a = 2.236067977499790?*I
n: -3
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 + 3 with a = 1.732050807568878?*I
unit group: Unit group with structure C6 of Number Field in a with defining polynomial x^2 + 3 with a = 1.732050807568878?*I
n: -2
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 + 2 with a = 1.414213562373095?*I
unit group: Unit group with structure C2 of Number Field in a with defining polynomial x^2 + 2 with a = 1.414213562373095?*I
n: -1
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 + 1 with a = 1*I
unit group: Unit group with structure C4 of Number Field in a with defining polynomial x^2 + 1 with a = 1*I
n: 2
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?
n: 3
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 - 3 with a = 1.732050807568878?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 3 with a = 1.732050807568878?
n: 5
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 - 5 with a = 2.236067977499790?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 5 with a = 2.236067977499790?
n: 6
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 - 6 with a = 2.449489742783178?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 6 with a = 2.449489742783178?
n: 7
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 - 7 with a = 2.645751311064591?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 7 with a = 2.645751311064591?
n: 10
class number: 2
class group: Class group of order 2 with structure C2 of Number Field in a with defining polynomial x^2 - 10 with a = 3.162277660168380?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 10 with a = 3.162277660168380?
n: 11
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 - 11 with a = 3.316624790355400?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 11 with a = 3.316624790355400?
n: 13
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 - 13 with a = 3.605551275463990?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 13 with a = 3.605551275463990?
n: 14
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 - 14 with a = 3.741657386773942?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 14 with a = 3.741657386773942?
n: 15
class number: 2
class group: Class group of order 2 with structure C2 of Number Field in a with defining polynomial x^2 - 15 with a = 3.872983346207417?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 15 with a = 3.872983346207417?
n: 17
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 - 17 with a = 4.123105625617660?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 17 with a = 4.123105625617660?
n: 19
class number: 1
class group: Class group of order 1 of Number Field in a with defining polynomial x^2 - 19 with a = 4.358898943540674?
unit group: Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 19 with a = 4.358898943540674?

追記1

$2=(1+\sqrt{-1})(1-\sqrt{-1})$ というのは間違ってはいないのだが、さらに $1 = -\sqrt{-1}^2$ を掛けて $\sqrt{-1}(1-\sqrt{-1})^2$ と書ける。これは素元の2乗に単元を掛けた形となっている。この形に表しておいた方が次回の記事と話のつながりが良かった。つまり、2は $N=4$ を割り切る素数なので素元の2乗の形が現れるというわけである。

参考

[1] 数論I／加藤和也, 黒川信重, 斎藤毅｜岩波オンデマンドブックス - 岩波書店
[2] 分数イデアル - Wikipedia

2025-04-06

ラドン・ニコディムの定理を使って確率空間上での確率変数の平均値を具体的に求めてみる

確率論

前回の記事に続いて本稿でも確率論の話題を取り上げる。前回、連続確率測度についてラドン・ニコディムの定理を適用する例を示すことができなかった。今回はそれがなぜ難しかったのか？というところから始めて、ラドン・ニコディムの定理がうまく使えるケースについて紹介したい。

前回悩んだこと

ある可測空間 $(\Omega, \mathcal{B})$ 上に定義された2つの連続確率測度 ${\bf P}, {\bf Q}$ について考える。もし ${\bf Q} \ll {\bf P}$ だったとするとすると、ラドン・ニコディムの定理よりラドン・ニコディム微分が存在する。これを具体的に求めることはできるのだろうか？離散型の確率測度と異なり、定義から愚直に求めることは難しく、前回はここで詰まってしまった。

今回考えたこと

そもそも標本空間を $\mathbb{R}$ やその部分集合に限っていない一般的な状況では、ラドン・ニコディム微分を具体的な式で表示することはできないように思われる。仮に何らかの式が得られたとして、一般の確率測度上で表されたその式はいったい何に使えるのか？そのまま積分が実行できるわけでもあるまい。

思うに、ラドン・ニコディムの定理が活きる場面というのは、ルベーグ測度との変換をすることで積分を具体的に実行できるようにすることではないか？しかし、ラドン・ニコディムの定理を適用する前提条件として2つの確率測度を考える可測空間が一致している必要がある。これだと一般の確率測度に対しては使いづらく、あまり意義を感じられない。

ではラドン・ニコディムの定理は実用上あまり役に立たない定理なのかというと、そんなことはない。ラドン・ニコディムの定理がバッチリ活きてくる場面というのは存在する。以下では私が学んだ事例の1つを紹介したい。

確率変数の分布

まずは確率変数の分布という概念について説明する。定義を本[1]から引用する。

確率変数の分布

$X$ を確率空間 $(\Omega, \mathcal{B}, {\bf P})$ 上の確率変数とする. このとき $\mathbb{R}$ の任意のボレル部分集合 $A$ について, 確率変数の定義から $X^{-1}(A) \in \mathcal{B}$ である. そこで

$\displaystyle{ \mu_X (A) = {\bf P}(X^{-1}(A)) \left( = {\bf P}(\omega \in \Omega : X(\omega) \in A) \right), A \in {\bf B}_1 }$

と定義すると $\mu_X$ は $(\mathbb{R}, {\bf B}_1)$ 上の確率測度となる. (中略) この確率測度 $\mu_X$ を確率変数 $X$ の分布（または法則）といい, 確率変数 $X$ は分布（または法則） $\mu_X$ に従うともいう.

少々ややこしいが、元の空間が何であれ $\mu_X$ の標本空間が $\mathbb{R}$ になるのがポイントである。これによって最終的にルベーグ測度への橋渡しがうまくいくようになる。以下で詳しく見ていこう。

分布を用いた平均値の計算

確率変数 $X$ の平均値は以下のように表される。

$\displaystyle{ E[X] = \int_{\Omega} X d{\bf P} }$

この積分を具体的に実行することは難しい。実は分布 $\mu_X$ を用いると $X$ の平均値を以下のように求めることができる（証明は本[1]の定理8.1などを参照）。

$\displaystyle{ E[X] = \int_{\mathbb{R}} x d\mu_X(x) }$

これで一歩前進したが、これだとまだ具体的な計算は難しい。結局、我々がまともに計算を行えるのはルベーグ測度の上だけなので、何とか上記の積分をルベーグ測度上での積分に持ち込みたい。

そこで登場するのがラドン・ニコディムの定理である。前回の記事では2つの確率測度の間で成立するラドン・ニコディムの定理について説明したが、実はこれは $\sigma$ -有限測度であれば同様に成り立つ[2]。

ルベーグ測度と $\mu_X$ の間でラドン・ニコディムの定理が成立するかを考えてみよう。そのためには確率測度の場合と同様に $\mu_X$ がルベーグ測度に関して絶対連続である必要がある。これは常に成り立つというわけにはいかず、分布による。もし絶対連続であればラドン・ニコディムの定理より以下の式が成り立つ。

$\displaystyle{ \mu_X(A) = \int_A \frac{d\mu_X(x)}{dx} dx }$

この式をよく見ると、ラドン・ニコディム微分 $\frac{d\mu_X(x)}{dx}$ は良く見慣れた密度関数そのものであることに気づく。以下では密度関数を $p_X(x)$ と書くことにする。先ほどの平均値の式を密度関数を用いて書くと以下のようになる。

$\displaystyle{ \begin{eqnarray} E[X] &=& \int_{\mathbb{R}} x d\mu_X(x) \\ &=& \int_{\mathbb{R}} x \frac{d\mu_X(x)}{dx} dx \\ &=& \int_{\mathbb{R}} x p_X(x) dx \end{eqnarray} }$

1番目から2番目の式への変形はまるでリーマン積分における変数置換のようになっている。ルベーグ積分においてもラドン・ニコディム微分を用いることでこのような式変形が可能である（詳細は本[1]の演習問題7.1などを参照のこと）。

これで確率変数 $X$ の平均値を具体的に求めるための式が得られた。

例

確率空間 $(\Omega, {\bf B}_1, {\bf P})$ 上の確率変数 $X$ が平均0、分散1のガウス分布に従うとする。このとき $E[X : [0, \infty)]$ がどうなるか計算してみよう。今は $X$ が従う分布が明らかになっているので、その背後にある確率空間がどうなっていようが知ったことではない。素直に先ほど紹介した式を用いればよい。結果を以下に示す。

$\displaystyle{ \begin{eqnarray} E[X : [0, \infty)] &=& \int_0^{\infty} x p_X(x) dx \\ &=& \frac{1}{\sqrt{2\pi}} \int_0^{\infty} x e^{-\frac{x^2}{2}} dx \\ &=& \frac{1}{\sqrt{2\pi}} \end{eqnarray} }$

最後の計算が面倒だったので流行りのAI[3]というやつにぶん投げたが、うまく計算してくれて便利だった。

まとめ

本稿では連続確率測度に対してラドン・ニコディムの定理が活きてくる事例について紹介した。個人的にはラドン・ニコディムの定理の強力さが感じられてよかったと思う。

実は先日ずっと読んでいた確率論の本[1]をついに読み終えた（最後の方は証明を飛ばしてしまったが・・・）。というわけで確率論についてはいったんこれで切り上げようと思う。コロナ前からずっとうまく勉強が進められなくて悶々としていたが、理解の程はともかくとして区切りをつけられてよかった。

なお、勉強が進まなかったのは自分のモチベーションコントロールの問題であり、本[1]は感動するほど良い本だったのでめちゃくちゃおすすめしたい（本ブログではアフィリエイトはやっていないので、純粋な気持ちとして）。

次は整数論か圏論に再チャレンジしようかと思っているが、手元に整数論の本があるのでそちらからやるかもしれない。

参考

[1] www.kyoritsu-pub.co.jp
[2] ラドン＝ニコディムの定理 - Wikipedia
[3] ChatGPT - 積分計算方法

2025-04-04

ラドン・ニコディム微分の簡単な例について考える

確率論

測度論的確率論を勉強しようと思ったら5年くらい経っていた

何年か前に測度論的確率論の本[1]を買った。これは大変面白い本で、通勤途中の電車で楽しく読んでいたものだ。ところが、その後コロナ禍に見舞われて在宅勤務が基本となり、めっきり本を読む時間が無くなってしまった。（不思議なことに、通勤に使っていた時間が読書に充てられることはなく、やらなければならない他のことに使われてしまった。）

これではいけないと何度か本の続きを読もうと思ったが、その後は業務が大炎上を繰り返して休職したり、そのあとに転職をしたりしてなかなか気持ちを落ち着けて本を読む時間が取れなかった。また、少々言い訳がましくなるが、転職後は業務で成果を出すために本業関連の勉強に時間を割いていたりしたため、結局最近まで確率論の本を読むことができなかった。

そんな状況が最近まで続いていたが、ここのところまた数学の勉強をしようという気持ちが蘇ってきた。そこで何度目かの確率論の勉強に挑戦している。以前チャレンジしたときはラドン・ニコディム微分が良く分からないと思ったところで終わってしまったので、今日はそこから歩みを進めるためにラドン・ニコディム微分を簡単な例を通して理解してみようと思う。

確率論の基本

まずは確率論の基本的な概念についてざっくり説明する。どこから話を始めるか悩ましいのだが、可測空間は既知とさせてほしい。以下では可測空間を $(\Omega, \mathcal{B})$ のように表す。ここで、 $\Omega$ は標本空間、 $\mathcal{B}$ は $\sigma$ -集合体（あるいは完全加法族）である。

確率空間

まずは確率測度の定義を本[1]から引用する。

確率測度

$(\Omega, \mathcal{B})$ を可測空間とする. $\mathcal{B}$ 上に定義された関数 ${\bf P}$ でつぎの条件(P.1), (P.2), (P.3)を満たすものを $(\Omega, \mathcal{B})$ 上の確率測度または単に確率という.
(P.1) 任意の $A \in \mathcal{B}$ に対して $0 \le {\bf P}(A) \le 1$ .
(P.2) ${\bf P}(\Omega) = 1$ .
(P.3) (可算加法性) $A_k \in \mathcal{B}, A_k \cap A_l = \emptyset (k \ne l),\ k, l \in \mathbb{N}$ であれば
$\displaystyle{ {\bf P}\left(\bigcup_{k=1}^{\infty} A_k \right) = \sum_{k=1}^{\infty} {\bf P}(A_k) }$

続いて確率空間の定義を同じく本[1]から引用する。

確率空間

可測空間 $(\Omega, \mathcal{B})$ とその上に定義された確率測度 ${\bf P}$ の組 $(\Omega, \mathcal{B}, {\bf P})$ を確率空間という.

確率変数

確率論の最初の驚きポイントと言えば確率変数の正体であろう。これは変数と名がついているが、その実態は関数である。本[1]から定義を引用する。

確率変数

$X$ が確率空間 $(\Omega, \mathcal{B}, {\bf P})$ 上の確率変数であるとは $X$ が可測空間 $(\Omega, \mathcal{B})$ 上の可測関数であることをいう.

確率変数の平均値

確率変数の平均値（あるいは期待値）については高校数学をやった方であれば概ねご存じだと思うが、今の文脈に沿って改めて定義を述べておく。

そのためにまずは記号を一つ定義しておく。 $A \subset \Omega$ に対して ${\bf I}_A(\omega)$ を以下のように定める。

$\displaystyle{ {\bf I}_A(\omega) = \begin{cases} 1, & \omega \in A \\ 0, & \omega \notin A \end{cases} }$

これを集合 $A$ の定義関数という。これをもとにまず非負単関数の平均値を以下のように定める[1]。

非負単関数の平均値

$X$ を非負単関数とする. (中略)
$\displaystyle{ X(\omega) = \sum_{k=1}^n a_k {\bf I}_{A_k} (\omega),\ \omega \in \Omega }$
$a_k \ge 0$ , $A_k \in \mathcal{B}$ , $A_k \cap A_l = \emptyset,\ k, l = 1, 2, \cdots, n$ , $\cup_{k=1}^n A_k = \Omega$ としてよい. このとき $X$ の平均値を
$\displaystyle{ {\bf E}[X] = \sum_{k=1}^n a_k {\bf P}(A_k) }$
と定義する.

非負単関数も少し工夫すれば似たような定義ができる。また、一般の確率変数は単関数列の極限として表すことができるので、平均値は単関数の平均値の極限として表すことができる。確率変数を単関数列の極限として表す方法は一通りではないため、どのような単関数列を用いても同じ値に収束することの証明が必要だが、細かいことは本[1]などを参考にしてほしい。

絶対連続

ラドン・ニコディム微分を理解する上で確率測度が絶対連続であるとはどういうことか理解しておくことは必須となる。絶対連続の定義を本[1]から引用する。

絶対連続

可測空間 $(\Omega, \mathcal{B})$ 上に二つの確率測度 ${\bf P}$ と ${\bf Q}$ が定義されているとする. このとき ${\bf Q}$ が ${\bf P}$ に関して絶対連続であるとは
$\displaystyle{ N \in \mathcal{B}, {\bf P}(N) = 0 \Rightarrow {\bf Q}(N) = 0 }$
の成り立つことである. これを ${\bf Q} \ll {\bf P}$ と表す.

ラドン・ニコディム微分

準備が長かったが、この章が本題である。まずはラドン・ニコディムの定理とラドン・ニコディム微分について本[1]から引用する。

ラドン・ニコディムの定理

可測空間 $(\Omega, \mathcal{B})$ 上に二つの確率測度 ${\bf P}$ と ${\bf Q}$ が定義されており, $Q \ll P$ とする. このとき確率空間 $(\Omega, \mathcal{B}, {\bf P})$ 上の非負平均可能な確率変数 $Y$ で
$\displaystyle{ (\#\#)\ \ \ {\bf Q}(A) = {\bf E}[Y:A], A \in \mathcal{B} }$
となるものが存在して, つぎの意味で一意. すなわち(##)を満たすような別の $Y'$ があるとすると $Y=Y', a.e.({\bf P})$ である。

この $Y$ をラドン・ニコディム微分といい $\frac{d{\bf Q}}{d{\bf P}}$ と書く.

ここで、 ${\bf E}[Y:A] = {\bf E}[Y I_{A}]$ であり、これを $Y$ の $A$ での平均という。また、平均可能というのは平均値が有限な値を持つことを指す。

簡単な例

離散的な場合

突然だが、カイジという漫画をご存じだろうか？その漫画には456賽というサイコロが登場する。これは本来1, 2, 3の目が存在するはずの面が代わりに4, 5, 6となっているようなサイコロである。結局、このサイコロを振ると4, 5, 6がそれぞれ1/3の確率で出ることになる。

今、 $\Omega = \{1, 2, 3, 4, 5, 6\}, \mathcal{B} = 2^{\Omega}$ とし、通常のサイコロを振るときの確率測度を ${\bf P}$ 、456賽を振るときの確率測度を ${\bf Q}$ とする。このとき、 ${\bf P}(N) = 0$ となるような $N \subset \mathcal{B}$ は空集合だけであるが、当然 ${\bf Q}(\emptyset) = 0$ なので $Q \ll P$ となっている。よって、ラドン・ニコディムの定理よりラドン・ニコディム微分が存在する。

このラドン・ニコディム微分は具体的には以下のようになる。

$\displaystyle{ \frac{d{\bf Q}}{d{\bf P}}(\omega) = \begin{cases} 0, & \omega \in \{1, 2, 3\} \\ 2, & \omega \in \{4, 5, 6\} \end{cases} }$

いくつか ${\bf Q}$ の値を具体的に計算してみると以下のようになる。

$\displaystyle{ \begin{eqnarray} Q(\{1\}) &=& \frac{d{\bf Q}}{d{\bf P}}(1) \cdot {\bf P}(\{1\}) = 0 \cdot \frac{1}{6} = 0 \\ Q(\{4\}) &=& 2 \cdot \frac{1}{6} = \frac{1}{3} \\ Q(\{2, 5\}) &=& 0 \cdot \frac{1}{6} + 2 \cdot \frac{1}{6} = \frac{1}{3} \\ Q(\{4, 6\}) &=& 2 \cdot \frac{1}{3} = \frac{2}{3} \end{eqnarray} }$

ところで、 ${\bf Q}(\{1\}) = 0$ なのに対して ${\bf P}(\{1\}) = \frac{1}{6} \ne 0$ となるため、 ${\bf P}$ は ${\bf Q}$ に関して絶対連続ではない。上の例を見ながら考えてみると当たり前に思えてくるが、結局ラドン・ニコディム微分とは2つの確率測度の間の変化の割合みたいなものなので、変換元が0だとどう頑張っても0でない値にすることはできないのである。これが絶対連続性が必要になる定性的な理由だと私は解釈した。

連続的な場合

どうやら一般の確率空間上で確率変数の平均値を求めるためには分布関数などの別の概念を持ち出す必要がありそうだった。本稿ではパスして、また別の機会に考えてみたい。

まとめ

本稿ではラドン・ニコディム微分について説明し、具体例を紹介した。ラドン・ニコディム微分を初めて見たときにはサッパリ分からなくて悩んだものだが、いくつか具体例を考えてみたことでやっと理解できたように思う。余談だが、どうにも具体例というやつは自分で考え出したものの方が理解が捗るような気がする。今後も悩んだら例を考えるというのを徹底していきたい。

参考

[1] www.kyoritsu-pub.co.jp

有限体のことを分かったつもりでいました

疑問1：既約多項式の根は常にの生成元になるのか？

原始多項式の例

原始多項式ではない既約多項式の例

疑問2：既約多項式の根の選び方はどうすればよいのか？

例

疑問3：有限体の元の最小多項式の次数はどうなるのか？

例

まとめ

参考

たまには技術っぽい話をしよう

分散ストレージにおけるデータ冗長化

RS符号

準備

シンボル

シンボルとビット列のマッピング

評価点による方法

組織符号

生成行列による方法

組織符号

生成多項式による方法

組織符号

計算例

評価点による方法の例

生成行列による方法の例

生成多項式による方法の例

異なる符号化方法によって得られる符号の間の関係

評価点の選び方

RS符号と巡回符号

まとめ

参考

円分体

の特徴

円分体とのアーベル拡大の関係

二次体を含む円分体

円分体の部分体としての二次体とガロア対応

計算してみよう

まとめ

参考

整数論に再チャレンジ中

分解する素数と分解しない素数

二次体

二次体の整数環における素数の分解（うまくいく場合）

の場合

の場合

の場合

二次体の整数環における素数の分解（うまくいかない場合）

イデアル類群と単数群

素数の分解の様子がの値によって判定できるための条件

素数がガウス整数環の素元かどうかをの値によって判定できた理由

まとめ

おまけ：sageによる二次体の計算

追記1

参考

前回悩んだこと

今回考えたこと

確率変数の分布

分布を用いた平均値の計算

例

まとめ

参考

測度論的確率論を勉強しようと思ったら5年くらい経っていた

確率論の基本

確率空間

確率変数

確率変数の平均値

絶対連続

ラドン・ニコディム微分

簡単な例

離散的な場合

連続的な場合

まとめ

参考

疑問1：既約多項式の根は常に $\mathbb{F}_q^{\times}$ の生成元になるのか？

$\mathrm{Gal}(\mathbb{Q}(\zeta_N)/\mathbb{Q})$ の特徴

円分体と $\mathbb{Q}$ のアーベル拡大の関係

$\mathbb{Q}(\sqrt{3})$ の場合

$\mathbb{Q}(\sqrt{5})$ の場合

$\mathbb{Q}(\sqrt{-3})$ の場合

素数の分解の様子が $p \bmod N$ の値によって判定できるための条件

素数 $p$ がガウス整数環の素元かどうかを $p \bmod 4$ の値によって判定できた理由