SSブログ
前の10件 | -

有限体の勉強 〜リード・ソロモン符号のシミュレーション〜 [数学]

 有限体の勉強を始めてちょっとわかった気になってきましたが、ここで有限体の応用の一つである「誤り訂正符号」、その中でも誤り訂正能力が高い方式である「リード・ソロモン符号」について、その原理をシミュレートしてみたいと思います。

 リード・ソロモン符号については、Wikipediaの記事にその原理が記述されていたり、他にも書籍を含めてたくさんの解説がありますが、数式を眺めてもなかなか理解できるものではありません。そこで実際に手を動かして、符号化と復号の推移を見てみることにします。

 リード・ソロモン符号は有限体を係数とする多項式を本格的に使います。まずはその有限体を定めますが、8ビットで表現できる $F_{2^8} (= F_{256})$ を使うことが多いようなので、本記事でも $F_{256}$ を使います。

 例によって $F_{256}$ の乗法群 $F_{256}^\times$ の原始元を見つけることから始めなければいけませんが、そこからするのはもうしんどいのでWikipediaから答えを頂きます。次の多項式
\[ X^8+X^4+X^3+X^2+1 \]
は $F_2$ 上で既約で、その根$\alpha$が $F_{256}^\times$ の原始元を与えます。これさえわかれば、スプレッドシートを使って $F_{256}$ の全ての元について $\alpha$ の指数表現と $(\alpha^7, \alpha^6, \cdots , \alpha, 1)$ を基底とするベクトル表現との対応づけをすることができます。スプレッドシート上は単純な縦長の表になりますが、全体を見やすくするためベクトル表現を$16$進で表してここに掲載します。

$F_{256}$ の変換表(ベクトル表現16進 → 指数表現)

0 1 2 3 4 5 6 7 8 9 A B C D E F
0x * 0 1 25 2 50 26 198 3 223 51 238 27 104 199 75
1x 4 100 224 14 52 141 239 129 28 193 105 248 200 8 76 113
2x 5 138 101 47 225 36 15 33 53 147 142 218 240 18 130 69
3x 29 181 194 125 106 39 249 185 201 154 9 120 77 228 114 166
4x 6 191 139 98 102 221 48 253 226 152 37 179 16 145 34 136
5x 54 208 148 206 143 150 219 189 241 210 19 92 131 56 70 64
6x 30 66 182 163 195 72 126 110 107 58 40 84 250 133 186 61
7x 202 94 155 159 10 21 121 43 78 212 229 172 115 243 167 87
8x 7 112 192 247 140 128 99 13 103 74 222 237 49 197 254 24
9x 227 165 153 119 38 184 180 124 17 68 146 217 35 32 137 46
Ax 55 63 209 91 149 188 207 205 144 135 151 178 220 252 190 97
Bx 242 86 211 171 20 42 93 158 132 60 57 83 71 109 65 162
Cx 31 45 67 216 183 123 164 118 196 23 73 236 127 12 111 246
Dx 108 161 59 82 41 157 85 170 251 96 134 177 187 204 62 90
Ex 203 89 95 176 156 169 160 81 11 245 22 235 122 117 44 215
Fx 79 174 213 233 230 231 173 232 116 214 244 234 168 80 88 175


$F_{256}$ の変換表(指数表現 → ベクトル表現16進)

0 1 2 3 4 5 6 7 8 9
0x 01 02 04 08 10 20 40 80 1D 3A
1x 74 E8 CD 87 13 26 4C 98 2D 5A
2x B4 75 EA C9 8F 03 06 0C 18 30
3x 60 C0 9D 27 4E 9C 25 4A 94 35
4x 6A D4 B5 77 EE C1 9F 23 46 8C
5x 05 0A 14 28 50 A0 5D BA 69 D2
6x B9 6F DE A1 5F BE 61 C2 99 2F
7x 5E BC 65 CA 89 0F 1E 3C 78 F0
8x FD E7 D3 BB 6B D6 B1 7F FE E1
9x DF A3 5B B6 71 E2 D9 AF 43 86
10x 11 22 44 88 0D 1A 34 68 D0 BD
11x 67 CE 81 1F 3E 7C F8 ED C7 93
12x 3B 76 EC C5 97 33 66 CC 85 17
13x 2E 5C B8 6D DA A9 4F 9E 21 42
14x 84 15 2A 54 A8 4D 9A 29 52 A4
15x 55 AA 49 92 39 72 E4 D5 B7 73
16x E6 D1 BF 63 C6 91 3F 7E FC E5
17x D7 B3 7B F6 F1 FF E3 DB AB 4B
18x 96 31 62 C4 95 37 6E DC A5 57
19x AE 41 82 19 32 64 C8 8D 07 0E
20x 1C 38 70 E0 DD A7 53 A6 51 A2
21x 59 B2 79 F2 F9 EF C3 9B 2B 56
22x AC 45 8A 09 12 24 48 90 3D 7A
23x F4 F5 F7 F3 FB EB CB 8B 0B 16
24x 2C 58 B0 7D FA E9 CF 83 1B 36
25x 6C D8 AD 47 8E


 本記事では $F_{256}$ の元は指数表現で扱うことを基本とするので、乗法演算は指数を足し合わせて$\mod 255$ をとることで行えます。加法演算はちょっと手間ですが、変換表を用いてベクトル表現にしてから各ビット毎にXORを取って、再び変換表を用いて指数表現にすれば求まります。実際にはこれらの計算は全部スプレッドシート上で関数を駆使して行いました。

 では、実際に文字列 "Hello!" をリード・ソロモン符号で符号化し、通信路上で生じた誤りが受信側で復元できることを見てみましょう。以下ではWikipediaの記事の方法に従ってシミュレートします。

 リード・ソロモン符号では、符号を $F_{256}$ の元を係数とする多項式で表します。"Hello!" の6文字をASCIIコード16進で表すと、
48, 65, 6C, 6C, 6F, 21

となりますが、これを $F_{256}$ の元のベクトル表現とみなして指数表現に変換すると、
\[ \alpha^{226}, \ \alpha^{72}, \ \alpha^{250}, \ \alpha^{250}, \ \alpha^{61}, \ \alpha^{138} \]
となり、これを表す情報多項式 $I(X)$ は、
\[ I(X) = \alpha^{226}X^5 + \alpha^{72}X^4 + \alpha^{250}X^3 + \alpha^{250}X^2 + \alpha^{61}X + \alpha^{138} \]
という$5$次多項式になります。
 これに誤り検出と訂正のための冗長化符号を追加します。ここでは最大 $t = 2$ 個のシンボルの誤りが訂正できるようにします。このため、生成多項式 $G(X)$ は
\[ G(X) = (X-\alpha^0)(X-\alpha^1)(X-\alpha^2)(X-\alpha^3) = X^4+\alpha^{75}X^3+\alpha^{249}X^2+\alpha^{78}X+\alpha^6 \]
によって定めればよく、これを使うと冗長多項式 $P(X)$ は
\[ P(X) = I(X) \times X^4 \mod G(X) = \alpha^{189}X^3 + \alpha^{19}X^2 + \alpha^{42}X + \alpha^{177} \]
となって、実際に送信する符号多項式 $C(X)$ は
\begin{eqnarray*}
C(X) &=& I(X) \times X^4 + P(X) \\
&=& \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 + \alpha^{61}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 + \alpha^{19}X^2 + \alpha^{42}X + \alpha^{177}
\end{eqnarray*}
となります。この上位$6$つの項の係数が送りたい文字列 "Hello!" を表しています。

 さて、この送信符号に通信路上で誤りが混入し、受信側では
\[ Y(X) = \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 + \alpha^{138}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 + \alpha^{43}X^2 + \alpha^{42}X + \alpha^{177} \]
となったとしましょう。つまり受信側では $X^5$ の係数が $\alpha^{61}$ から $\alpha^{138}$ に化け、さらに冗長化で追加した部分も $X^2$ の係数が $\alpha^{19}$ から $\alpha^{43}$ に化けて伝わったと想定します。これでは情報部分が文字列 "Hell!!" を表すことになり、そのまま受け止めるとコミュニケーション上大変な問題が生じてしまいます。
 そこで、この受信符号から誤りを見つけ出し、訂正する必要があります。これもWikipediaの記事に従って実際に行ってみます。

 まず、シンドロームと呼ばれる $t \times 2 = 4$ 個の $F_{256}$ の値を次によって計算します。
\begin{eqnarray*}
S_1 &=& Y(\alpha^0) &=& \alpha^{163} \\
S_2 &=& Y(\alpha^1) &=& \alpha^{112} \\
S_3 &=& Y(\alpha^2) &=& \alpha^{2} \\
S_4 &=& Y(\alpha^3) &=& \alpha^{25}
\end{eqnarray*}
$C(X)$ が $G(X)$ で整除されるので、もし誤りがなければこれらは全て$0$になるはずのものですが、誤りが生じているためどれも$0$以外の値となっています。

 次にこれらの値を使って誤り数 $k$ を求めます。次の行列式を計算します。
\begin{equation*}
\begin{vmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{vmatrix}
= S_2^2 - S_1S_3 = \alpha^{247}
\end{equation*}
これは$0$ではないので、$k = 2$ すなわち誤りのあるシンボル数は$2$個です($3$個以上の誤りは想定しないものとします)。

 続いて、誤りがどの位置にあるのかを特定します。$k=2$ なので、誤り位置多項式 $\sigma(X)$ は次の形の$2$次多項式になります。
\[ \sigma(X) = \sigma_2X^2 +\sigma_1X+1 \]
ここで係数 $\sigma_1, \sigma_2$ は、
\begin{equation*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
=
\begin{bmatrix}
S_3 \\
S_4 \\
\end{bmatrix}
\end{equation*}
をみたすので、これを解くと $\sigma_1 = \alpha^{225}, \ \sigma_2 = \alpha^{7}$ が得られ、
\[ \sigma(X) = \alpha^{7}X^2 +\alpha^{225}X+1 \]
となります。
 この $\sigma(X)$ に $\alpha^0, \alpha^{-1}, \cdots , \alpha^{-9}$ を次々に代入すると、$\sigma(\alpha^{-2})$ と $\sigma(\alpha^{-5})$ だけが$0$となり、他は$0$ではないので、$Y(X)$ の $X^2$ と $X^5$ の係数が誤りを含んでいると特定されました。

 最後に誤りの値を計算します。誤り多項式 $E(X) = Y(X) - C(X)$ は
\[ E(X) = e_1X^5 + e_2X^2 \]
の形になることがわかりましたので、これに $\alpha^0, \alpha^1$ を代入することにより、
\begin{eqnarray*}
e_1 &+& e_2 &=& S_1 &=& \alpha^{163} \\
e_1\alpha^5 &+& e_2\alpha^2 &=& S_2 &=& \alpha^{112}
\end{eqnarray*}
これを解くと $e_1 = \alpha^{34}, \ e_2 = \alpha^{18}$ が得られるので、
\begin{eqnarray*}
C(X) &=& Y(X) + E(X) \\
&=& \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 &+& \alpha^{138}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 &+& \alpha^{43}X^2 + \alpha^{42}X + \alpha^{177} \\
&& &+& \alpha^{34}X^5 &+& \alpha^{18}X^2\\
&=& \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 &+& \alpha^{61}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 &+& \alpha^{19}X^2 + \alpha^{42}X + \alpha^{177}
\end{eqnarray*}
となって、無事に送信符号と同じもの、情報部分の文字列 "Hello!" が復元されました。

 このシミュレーションを行ったスプレッドシートをそのままここにアップロードしておきます。ダウンロードしてEXCELなどで開き、2箇所の黄色のセルに$0$から$254$までのどのような数字を入れても、復号した緑のセルは元の青いセルの値が正しく表示されることが確認できると思います。

 有限体の四則演算が自由自在にできることを利用した巧妙な符号化方式であることが実感できました。考えた人(リードさんとソロモンさん)は天才ですね。

nice!(0)  コメント(0) 
共通テーマ:学問

有限体の勉強 〜位数64の有限体の構造を探る〜 [数学]

 前回の記事で、有限体に関する一般的な性質をいくつか確認しました。今回はそれを使って、もう少し大きな位数の有限体である $F_{64}$ の構造を調べることにします。

 なぜ $F_{64}$ なのかというと、$64 = 2^6$ なので標数は$2$で、前回の【定理2】より、
\begin{eqnarray*}
F_2 \subset F_4 \subset F_{64} \\
F_2 \subset F_8 \subset F_{64}
\end{eqnarray*}
という$2$つの異なった部分体の系列を持つから、その様子を見たいという理由です。元の数が$64$だったらなんとか手作業で頑張れる範囲だろうという目論見もあります。実際、今回の作業はスプレッドシート(EXCEL が代表的ですが実際に使ったのは LibreOffice)を使ってあまり苦労せずに実施できました。

 まず、前回の【定理1】より、$F_{64}$ は $F_2$ 上の多項式 $X^{64}-X$ の最小分解体なので、$X^{64}-X$ を $F_2$ 上で既約因子に分解することを考えます。これは前回の【定理2】より、$F_2$ 上の$6$次の既約多項式を全て見出せばよいことになります(次数$1,2,3$の既約多項式は前々回で全て分かっています)。

 前回の【定理3】の後の考察によって、$F_2$ 上の$6$次の既約多項式は全部で$9$つあります。多項式の既約性の確認は一般に面倒な作業ですが、今回の場合はちょっと発想を変えることによってそれほど苦労せずにこの$9$つを特定できました。以下その手順です。

 $F_2$ 上の多項式なので係数は$0,1$のみを考えればよろしい。そして、
① $X$ を因子に持たないことから、$X$ に$0$を代入した結果は$0$ではない。従って定数項は$1$。
② $X-1$ を因子に持たないことから、$X$ に$1$を代入した結果は$0$ではない。従って係数$1$の項は奇数個。
の$2$つの条件を満たすものが候補になります。これらをみたす$6$次多項式は以下の$16$個です。
\begin{eqnarray*}
(A) &\quad& X^6+X^5+X^4+X^3+X^2+X+1 \\
(B) &\quad& X^6+X^5+X^4+X^3+1 \\
(C) &\quad& X^6+X^5+X^4+X^2+1 \\
(D) &\quad& X^6+X^5+X^4+X+1 \\
(E) &\quad& X^6+X^5+X^3+X^2+1 \\
(F) &\quad& X^6+X^5+X^3+X+1 \\
(G) &\quad& X^6+X^5+X^2+X+1 \\
(H) &\quad& X^6+X^4+X^3+X^2+1 \\
(I) &\quad& X^6+X^4+X^3+X+1 \\
(J) &\quad& X^6+X^4+X^2+X+1 \\
(K) &\quad& X^6+X^3+X^2+X+1 \\
(L) &\quad& X^6+X^5+1 \\
(M) &\quad& X^6+X^4+1 \\
(N) &\quad& X^6+X^3+1 \\
(O) &\quad& X^6+X^2+1 \\
(P) &\quad& X^6+X+1
\end{eqnarray*}
 次に、これらの中から$2$次以上の既約因子に分解できるものを除きます。次数が$6$なので分解のパターンは、$2$次×$2$次×$2$次、$2$次×$4$次、$3$次×$3$次 の$3$とおりしかありません。そして前々回の記事より、$2$次の既約多項式は
\begin{equation*}
X^2+X+1
\end{equation*}
の$1$つだけ、$3$次の既約多項式は
\begin{eqnarray*}
&& X^3+X^2+1 \\
&& X^3+X+1
\end{eqnarray*}
の$2$つ、$4$次の既約多項式は
\begin{eqnarray*}
&& X^4+X^3+X^2+X+1 \\
&& X^4+X^3+1 \\
&& X^4+X+1
\end{eqnarray*}
の$3$つであることがわかっているので、これらの組み合わせとなる$6$次多項式を候補から除けばよいわけです。実際に計算すると、
\begin{eqnarray*}
(X^2+X+1)^3 &=& X^6+X^5+X^3+X+1 \quad &\cdots& \quad (F)\\
(X^2+X+1)(X^4+X^3+X^2+X+1) &=& X^6+X^4+X^3+X^2+1 \quad &\cdots& \quad (H)\\
(X^2+X+1)(X^4+X^3+1) &=& X^6+X^3+X^2+X+1 \quad &\cdots& \quad (K)\\
(X^2+X+1)(X^4+X+1) &=& X^6+X^5+X^4+X^3+1 \quad &\cdots& \quad (B)\\
(X^3+X^2+1)^2 &=& X^6+X^4+1 \quad &\cdots& \quad (M)\\
(X^3+X+1)^2 &=& X^6+X^2+1 \quad &\cdots& \quad (O)\\
(X^3+X^2+1)(X^3+X+1) &=& X^6+X^5+X^4+X^3+X^2+X+1 \quad &\cdots& \quad (A)
\end{eqnarray*}
となりますので、これらを除くことにより、結局次の$9$つが $F_2$ 上の$6$次の既約多項式の全てであることがわかりました。
\begin{eqnarray*}
(C) &\quad& X^6+X^5+X^4+X^2+1 \\
(D) &\quad& X^6+X^5+X^4+X+1 \\
(E) &\quad& X^6+X^5+X^3+X^2+1 \\
(G) &\quad& X^6+X^5+X^2+X+1 \\
(I) &\quad& X^6+X^4+X^3+X+1 \\
(J) &\quad& X^6+X^4+X^2+X+1 \\
(L) &\quad& X^6+X^5+1 \\
(N) &\quad& X^6+X^3+1 \\
(P) &\quad& X^6+X+1
\end{eqnarray*}

従って、多項式 $X^{64}-X$ は $F_2$ 上で次のように既約因子に分解されます。
\begin{eqnarray*}
X^{64}-X &=& X(X-1)(X^2+X+1)(X^3+X^2+1)(X^3+X+1) \\
&& \cdot (X^6+X^5+X^4+X^2+1)(X^6+X^5+X^4+X+1)(X^6+X^5+X^3+X^2+1) \\
&& \cdot (X^6+X^5+X^2+X+1)(X^6+X^4+X^3+X+1)(X^6+X^4+X^2+X+1) \\
&& \cdot (X^6+X^5+1)(X^6+X^3+1)(X^6+X+1)
\end{eqnarray*}
この分解が正しいことを手作業で確認することはさすがにやめました。前回の【定理3】を信じます。

 さて、これら$9$つの$6$次の既約多項式のうち、どの多項式の根を $F_2$ に添加しても同じ $F_{64}$ が構成できますが、乗算表を楽に作るためには前々回でみたように 、根が$F_{64}$ の乗法群 $F_{64}^\times$ の原始元になるような多項式を探す必要があります(原始元が必ず存在することは証明されています)。この作業はある意味試行錯誤ですが、スプレッドシートの力を借りて計算することにより、
\begin{equation*}
(D) \quad X^6+X^5+X^4+X+1
\end{equation*}
の根が原始元になることがわかりました。以下$(D)$の根を$\alpha$とおき、これを基本にします。$\alpha^{63} = 1$ なので、
\[ F_{64} = \{ \, 0, \, \alpha^0(=1), \, \alpha^1, \, \alpha^2, \cdots , \alpha^{61} , \alpha^{62} \, \} \]
であり、$F_{64}^\times$ の全ての元を$\alpha$の指数と $(\alpha^5, \alpha^4, \alpha^3, \alpha^2, \alpha, 1)$ を基底とするベクトル表現との対応づけができます。これが次の表です。

指数 負指数 ベクトル表現 最小多項式
0 -63 000001 $X-1$(または $X+1$)
1 -62 000010 $X^6+X^5+X^4+X+1$
2 -61 000100 $X^6+X^5+X^4+X+1$
3 -60 001000 $X^6+X^4+X^2+X+1$
4 -59 010000 $X^6+X^5+X^4+X+1$
5 -58 100000 $X^6+X^4+X^3+X+1$
6 -57 110011 $X^6+X^4+X^2+X+1$
7 -56 010101 $X^6+X^3+1$
8 -55 101010 $X^6+X^5+X^4+X+1$
9 -54 100111 $X^3+X^2+1$
10 -53 111101 $X^6+X^4+X^3+X+1$
11 -52 001001 $X^6+X+1$
12 -51 010010 $X^6+X^4+X^2+X+1$
13 -50 100100 $X^6+X^5+1$
14 -49 111011 $X^6+X^3+1$
15 -48 000101 $X^6+X^5+X^4+X^2+1$
16 -47 001010 $X^6+X^5+X^4+X+1$
17 -46 010100 $X^6+X^4+X^3+X+1$
18 -45 101000 $X^3+X^2+1$
19 -44 100011 $X^6+X^5+1$
20 -43 110101 $X^6+X^4+X^3+X+1$
21 -42 011001 $X^2+X+1$
22 -41 110010 $X^6+X+1$
23 -40 010111 $X^6+X^5+X^3+X^2+1$
24 -39 101110 $X^6+X^4+X^2+X+1$
25 -38 101111 $X^6+X+1$
26 -37 101101 $X^6+X^5+1$
27 -36 101001 $X^3+X+1$
28 -35 100001 $X^6+X^3+1$
29 -34 110001 $X^6+X^5+X^3+X^2+1$
30 -33 010001 $X^6+X^5+X^4+X^2+1$
31 -32 100010 $X^6+X^5+X^2+X+1$
32 -31 110111 $X^6+X^5+X^4+X+1$
33 -30 011101 $X^6+X^4+X^2+X+1$
34 -29 111010 $X^6+X^4+X^3+X+1$
35 -28 000111 $X^6+X^3+1$
36 -27 001110 $X^3+X^2+1$
37 -26 011100 $X^6+X+1$
38 -25 111000 $X^6+X^5+1$
39 -24 000011 $X^6+X^5+X^4+X^2+1$
40 -23 000110 $X^6+X^4+X^3+X+1$
41 -22 001100 $X^6+X^5+1$
42 -21 011000 $X^2+X+1$
43 -20 110000 $X^6+X^5+X^3+X^2+1$
44 -19 010011 $X^6+X+1$
45 -18 100110 $X^3+X+1$
46 -17 111111 $X^6+X^5+X^3+X^2+1$
47 -16 001101 $X^6+X^5+X^2+X+1$
48 -15 011010 $X^6+X^4+X^2+X+1$
49 -14 110100 $X^6+X^3+1$
50 -13 011011 $X^6+X+1$
51 -12 110110 $X^6+X^5+X^4+X^2+1$
52 -11 011111 $X^6+X^5+1$
53 -10 111110 $X^6+X^5+X^3+X^2+1$
54 -9 001111 $X^3+X+1$
55 -8 011110 $X^6+X^5+X^2+X+1$
56 -7 111100 $X^6+X^3+1$
57 -6 001011 $X^6+X^5+X^4+X^2+1$
58 -5 010110 $X^6+X^5+X^3+X^2+1$
59 -4 101100 $X^6+X^5+X^2+X+1$
60 -3 101011 $X^6+X^5+X^4+X^2+1$
61 -2 100101 $X^6+X^5+X^2+X+1$
62 -1 111001 $X^6+X^5+X^2+X+1$


この表の見方は、例えば上から8行目を見ると、
\[ \alpha^7 = \alpha^{-56} = \alpha^4+\alpha^2+1 \]
であって、さらにその $F_2$ における最小多項式が $X^6+X^3+1$ である、ということです。
 この対応表の作成も、スプレッドシートを使って1ビットずつ計算式を入れることにより簡単にできました。最小多項式の欄については、前回の【定理4】より指数が2倍になっても同じ最小多項式になることを使い、負の指数もうまく使うことによって簡単に埋まりました。

 ここまでくると、スプレッドシートを使って $F_{64}$ の加算表と乗算表が機械的に作成できます。加算表はベクトル表現を、乗算表は指数表現を使って作成し、それぞれを変換表を用いて他の表現に置き換えると、次のようにベクトル表現と指数表現による加算表と乗算表ができあがります(リンクをクリックすると別ページで表示されます。なお指数表現では$0$が表現できないので * であらわしています。)。

・$F_{64}$の加算表(ベクトル表現)
・$F_{64}$の加算表(指数表現)
・$F_{64}$の乗算表(ベクトル表現)
・$F_{64}$の乗算表(指数表現)

 これらの表では部分体も色付けによって表現しています。ピンクは $F_2$、黄色は $F_4 \setminus F_2$、緑は $F_8 \setminus F_2$ に相当する部分です。これら部分体を見出すのも上の対応表を使えば簡単にできます。$F_2 = \{ \, 0, \, \alpha^0 \, \}$ は当然として、$F_4$ は最小多項式が$2$次になるものを取り出せばよいので、
\[ F_4 = \{ \, 0, \, \alpha^0 \, \alpha^{21} \, \alpha^{42} \, \} \]
と指数が$21$の倍数になるもので構成されることがわかり、同様に $F_8$ は最小多項式が$3$次になるものを取り出せばよいので、
\[ F_8 = \{ \, 0, \, \alpha^0 \, \alpha^9 \, \alpha^{18} \, \alpha^{27} \, \alpha^{36} \, \alpha^{45} \, \alpha^{54} \, \} \]
と指数が$9$の倍数になるもので構成されることがわかり、これらの場所を各表に色付けすればよいわけです。蛇足ながら $F_4$ が $F_8$ の部分体にならないことも一目瞭然です。

 さらに蛇足ながら、乗法群 $F_{64}^\times$ の原始元になることは、位数が$63$になること、すなわち$\alpha$の指数が$63$と互いに素であることと同値なので、原始元はオイラーの$\varphi$関数を用いて $\varphi(63) = 36$ 個あることになります。上の表で指数が$63$と互いに素なものに対応する最小多項式を全て拾い出すと、
\begin{eqnarray*}
(D) &\quad& X^6+X^5+X^4+X+1 \\
(E) &\quad& X^6+X^5+X^3+X^2+1 \\
(G) &\quad& X^6+X^5+X^2+X+1 \\
(I) &\quad& X^6+X^4+X^3+X+1 \\
(L) &\quad& X^6+X^5+1 \\
(P) &\quad& X^6+X+1
\end{eqnarray*}
の$6$つです。これらの多項式の根は全て $F_{64}^\times$ の原始元になるというわけです。このような多項式を原始多項式といいます。
 これら以外の$6$次の既約多項式$3$つ
\begin{eqnarray*}
(C) &\quad& X^6+X^5+X^4+X^2+1 \\
(J) &\quad& X^6+X^4+X^2+X+1 \\
(N) &\quad& X^6+X^3+1
\end{eqnarray*}
については、その根が $F_{64}^\times$ の原始元にならないので、原始多項式ではありません。既約多項式が原始多項式かどうかを係数から簡単に見分ける方法があるのかないのか、今の僕はその知見を持っていません。

nice!(0)  コメント(0) 
共通テーマ:学問

有限体の勉強 〜素体上の既約多項式への分解〜 [数学]

 有限体のことを何も知らないので勉強を始めました。前回は標数2の有限体のうち、$F_2$ から $F_{16}$ までの加算乗算表を作るところまでやってみました。

 この過程で見えてきたことを一つずつ検証してみます。

 まず単純な話ですが、$F_2$ 上の多項式には次数$n$が何であっても必ず$n$次の既約多項式がある、という事実があります。$2$次ならば $X^2+X+1$ がそうですし、$3$次でも$4$次でもありました。これは標数が一般の素数$p$に対して成り立ちます。

 このことを証明するために、有限体の位数(元の数)に関する基本的な定理をまず書いておきます。

【定理1】有限体の位数はある素数$p$と正整数$n$に対して $p^n$ と表されるものに限る。逆に、任意の素数$p$と正整数$n$に対して位数 $p^n$ の有限体が同形を除いて一意に存在し、それは素体 $F_p$ 上の多項式 $X^{p^n}-X$ の最小分解体である。

(証明)$K$を有限体とすると、$\mathbb{Q}$が無限集合だから$K$の標数は$0$ではなく、素数$p$である。$K$は素体 $F_p$ 上の有限次元ベクトル空間なので、次元を$n$とすると$K$の位数は $p^n$ になる。従って有限体の位数は $p^n$ と表されるものに限られる。
 素数$p$と正整数$n$に対して $q = p^n$ とし、$F_p$ 上で$q$次の多項式 $f(X) = X^q-X$ を考えると、体の拡大の一般論によって、$f(X)$ の $F_p$ 上の最小分解体が同形を除いて一意に存在する。また $f(X)$ の形式微分は $f'(X) = -1$ なので $f(X)$ は重根を持たず、従って最小分解体上で $f(X)$ は異なる$q$個の根を持つ。$\alpha, \beta$ を $f(X)$ の根とすると、フロベニウス写像が環準同型であることと $\alpha^q = \alpha, \, \beta^q = \beta$ より、
\begin{eqnarray*}
f(\alpha+\beta) &=& (\alpha+\beta)^{p^n} - (\alpha+\beta) = \alpha^{p^n} +\beta^{p^n} - \alpha - \beta = \alpha^q +\beta^q - \alpha - \beta = \alpha + \beta - \alpha - \beta = 0 \\
f(\alpha\beta) &=& (\alpha\beta)^q - \alpha\beta = \alpha^q \beta^q - \alpha\beta = \alpha \beta - \alpha\beta = 0 \\
f(\alpha^{-1}) &=& (\alpha^{-1})^q - \alpha^{-1} = (\alpha^q)^{-1} - \alpha^{-1} = \alpha^{-1} - \alpha^{-1} = 0
\end{eqnarray*}
となるから、$f(X)$ の$q$個の根の集合は体を構成する。従って最小分解体はちょうど$q$個の元を持ち、位数$q$の有限体は存在する。
 位数$q$の体$K$の乗法群 $K^\times$ は位数 $q-1$ なので、任意の $K^\times$ の元$\alpha$は $\alpha^{q-1} = 1$ をみたし、従って$K$の$q$個の元は$0$を含め全て $\alpha^q = \alpha$ をみたすから、$f(X)$ の根である。従って $f(X)$ は$K$上$q$個の$1$次式に分解されるから、$K$は $F_p$ 上の $f(X)$ の最小分解体である。従って位数$q$の有限体は同形を除いて一意に定まる。□

 平たくいうと、位数 $q = p^n$ の有限体は、$F_p$ の拡大体で多項式 $X^q-X$ の$q$個の根を元に持つものとして特徴付けられることになります。

 さて、位数 $q = p^n$ の有限体 $F_q$ は素体 $F_p$ 上の$n$次元ベクトル空間ですから、体の拡大の一般論によって、ある $F_q$ の元$\alpha$があって $F_q = F_p(\alpha)$ と表され(つまり $F_q$ は$\alpha$を $F_p$ に添加した体であり)、$\alpha$の $F_p$ 上の最小多項式の次数が$n$になります。 この最小多項式は $F_p$ 上で既約なので、これで $F_p$ 上の$n$次の既約多項式の存在が示されました。

 ここまでの知識を持って前回の記事を見返し、特に $F_{16}$ について $X^{16}-X$ を $F_2$ 上で既約多項式に分解した結果を再度見直してみます。
\[ X^{16}-X = X(X-1)(X^2+X+1)(X^4+X+1)(X^4+X^3+1)(X^4+X^3+X^2+X+1) \tag{1} \]
$16=2^4$ なので因子に$4$次多項式が含まれることはわかるのですが、そのほかに$1$次と$2$次の多項式も因子に含まれています。そして、
\begin{eqnarray*}
X^4-X &=& X(X-1)(X^2+X+1) \\
X^2-X &=& X(X-1)
\end{eqnarray*}
であり、$F_4$ は $F_2$ 上の $X^4-X$ の最小分解体、$F_{16}$ は $F_2$ 上の $X^{16}-X$ の最小分解体であることを考えると、$X^{16}-X$ が $X^4-X$ を因子に持ち、また $X^4-X$ が $X^2-X$ を因子に持つことから、
\[ F_2 \subset F_4 \subset F_{16} \]
という拡大体の系列ができていることがわかります。
 これは一般に次の形で成り立ちます。

【定理2】有限体 $F_{p^m}$ と $F_{p^n}$ について、$F_{p^m} \subseteq F_{p^n}$ であることと $m \mid n$ であることは同値である。

(証明)$F_{p^m} \subseteq F_{p^n}$ ならば、$F_{p^n}$ の $F_{p^m}$ 上の拡大次数を$k$とすると、$(p^m)^k = p^n$ より $mk=n$ すなわち $m \mid n$ である。
 逆に $m \mid n$ ならば、$mk=n$ とすると、
\[ p^n-1 = (p^m)^k-1 = (p^m-1)((p^m)^{k-1} + \cdots + p^m +1) \]
なので、$\ell = (p^m)^{k-1} + \cdots + p^m +1$ とおくと、$F_p$ 上で
\begin{eqnarray*}
X^{p^n}-X &=& X(X^{p^n-1}-1) \\
&=& X((X^{p^m-1})^\ell -1) \\
&=& X(X^{p^m-1} -1)((X^{p^m-1})^{\ell-1} + \cdots + X^{p^m-1} + 1) \\
&=& (X^{p^m}-X)((X^{p^m-1})^{\ell-1} + \cdots + X^{p^m-1} + 1)
\end{eqnarray*}
が成り立つ。よって $F_{p^n}$ 上で $X^{p^m}-X$ の根が $p^m$ 個存在し、それらは体 $F_{p^m}$ を構成するから $F_{p^m} \subseteq F_{p^n}$ である。□

 このことから、$F_p$ 上の多項式 $X^{p^n}-X$ の分解については、次の特徴でまとめられることがわかります。

【定理3】$F_p$ 上の多項式 $X^{p^n}-X$ について次が成り立つ。
 ① $n$の全ての約数$m$に対し、$X^{p^n}-X$ は $X^{p^m}-X$ を因子に持つ。
 ② $n$の全ての約数$m$に対し、$X^{p^n}-X$ は次数$m$の全ての既約多項式を因子に持つ。
 ③ $m$が$n$の約数でなければ、$X^{p^n}-X$ は次数$m$の既約多項式を因子に持たない。

(証明)①は【定理2】で示したとおり。
 ②は、$X^{p^m}-X$ が次数$m$の全ての既約多項式を因子に持つことを示せば、①から従う。もし $X^{p^m}-X$ の因子にない次数$m$の既約多項式が存在すると仮定すると、その既約多項式を使って $F_p$ を $F_{p^m}$ に拡大することができ、$X^{p^m}-X$ の別の分解ができてしまうので、多項式環 $F_p[X]$ の一意分解性に矛盾する。
 ③を示すため、$m \nmid n$ なる$m$に対して、$F_p$ 上既約な次数$m$の多項式 $f(X)$ が $X^{p^n}-X$ の因子に含まれると仮定する。$F_p$ の拡大体 $F_{p^m}$ を考えると、②より $f(X)$ は $X^{p^m}-X$ の因子にも含まれ、$f(X)$ の全ての根は $F_{p^n}$ と $F_{p^m}$ の両方に属する。$K = F_{p^m} \cap F_{p^n}$ とおくと、$K$は加法、乗法と乗法逆元に対して閉じているので $F_{p^m}$ と $F_{p^n}$ の共通の部分体である。よって【定理2】より、ある正整数$k$があって $K = F_{p^k}$ かつ $k \mid m$ かつ $k \mid n$ であるが、一方で $f(X)$ の全ての根が$K$に属することから $X^{p^k}-X$ は $f(X)$ を因子に持ち、$f(X)$ は $F_p$ 上既約で次数$m$だから $k \ge m$ である。従って $k=m$ となるしかなく、$m \mid n$ が従うが、仮定より $m \nmid n$ なので矛盾である。□

 $X^{16}-X$ を $F_2$ 上で分解した式$(1)$を見ると、実際に①と③が成り立っていることがわかり、さらに②の事実から、

 $F_2$ 上の$1$次の既約多項式は $X, \ X-1$(あるいは $X, \ X+1$ )の$2$個
 $F_2$ 上の$2$次の既約多項式は $X^2+X+1$ の$1$個
 $F_2$ 上の$4$次の既約多項式は $X^4+X+1, \ X^4+X^3+1, \ X^4+X^3+X^2+X+1$ の$3$個

であることがわかります。次数をみると、
\[ 1 \times 2 + 2 \times 1 + 4 \times 3 = 16 \]
となるので、計算が合いますね。

 一般に素数$p$と正整数$n$に対して、$F_p$ 上の$n$次の既約多項式の個数を $\sigma(p,n)$ とおくと、$X^{p^n}-X$ の $F_p$ 上の既約因子への分解を考え、【定理3】を使ってその次数を比較することにより、
\[ p^n = \sum_{d \mid n} d \sigma(p,d) \tag{2} \]
であることがわかります。ここで右辺は$n$の全ての約数$d$にわたって和を取ることを意味します。明らかに $\sigma(p,1)=p$ なので、これを用いて再帰的に $\sigma(p,n)$ が計算できます。$p=2, 3$ のときに実際に計算すると、
\begin{eqnarray*}
\sigma(2,1) && &=& 2 \\
\sigma(2,2) &=& (2^2 - \sigma(2,1))/2 &=& 1 \\
\sigma(2,3) &=& (2^3 - \sigma(2,1))/3 &=& 2 \\
\sigma(2,4) &=& (2^4 - \sigma(2,1) - 2\sigma(2,2))/4 &=& 3 \\
\sigma(2,5) &=& (2^5 - \sigma(2,1))/5 &=& 6 \\
\sigma(2,6) &=& (2^6 - \sigma(2,1)- 2\sigma(2,2)- 3\sigma(2,3))/6 &=& 9 \\
&\cdots& \\
\\
\sigma(3,1) && &=& 3 \\
\sigma(3,2) &=& (3^2 - \sigma(3,1))/2 &=& 3 \\
\sigma(3,3) &=& (3^3 - \sigma(3,1))/3 &=& 8 \\
\sigma(3,4) &=& (3^4 - \sigma(3,1) - 2\sigma(3,2))/4 &=& 18 \\
\sigma(3,5) &=& (3^5 - \sigma(3,1))/5 &=& 48 \\
\sigma(3,6) &=& (3^6 - \sigma(3,1)- 2\sigma(3,2)- 3\sigma(3,3))/6 &=& 116 \\
&\cdots&
\end{eqnarray*}
となります。

 もう一つ、前回の記事において、$F_2$ においては既約多項式の根は2乗しても同じ既約多項式の根になる、という現象を見ました。これは一般の標数$p$に対して次のように証明できます(既約多項式でなくても成立します)。

【定理4】$f(X)$ を $F_p$ 上の多項式とし、$\alpha$を $F_p$ の拡大体$K$における $f(X)$ の根とすると、$\alpha^p$ も $f(X)$ の根である。従って任意の正整数$n$に対し $\alpha^{p^n}$ も $f(X)$ の根である。

(証明)$F_p$ の拡大体$K$上で $f(\alpha) = 0$ なので、$(f(\alpha))^p = 0$ である。$\displaystyle f(X) = \sum_{i=0}^mc_iX^i$ とすると、標数が$p$だからフロベニウス写像が環準同型であることより、
\[ (f(\alpha))^p = \left( \sum_{i=0}^mc_i \alpha^i \right)^p = \sum_{i=0}^m(c_i)^p (\alpha^i)^p = \sum_{i=0}^m(c_i)^p (\alpha^p)^i \]
ここで係数 $c_i$ は $F_p$ の元だから $0^p=0$ とフェルマーの小定理によって $(c_i)^p = c_i$ である。よって、
\[ f(\alpha^p) = (f(\alpha))^p = 0 \]
が従い、$\alpha^p$ も $f(X)$ の根である。□

 これより、$q = p^n$ のとき $F_q$ の$q$個の元は、$F_p$ 上の $X^q-X$ の既約因子のどれに所属するかに基づき、それぞれの既約因子の次数$d$ずつ組になって$p$乗の繰り返しによって巡回します。具体的には、例えば$d$次の既約多項式 $f(X)$ が $X^q-X$ の因子とし、その$1$つの根を$\alpha$とすると、
\[ \alpha, \alpha^p, \alpha^{p^2}, \cdots , \alpha^{p^{d-1}} \]
の$d$個の $F_q$ の元がどれも $f(X)$ の根となり、$f(X)$ の根は$d$個なので、$p$乗の繰り返しによってこれら$d$個の間で巡回します。

 もう一度前回の記事の、$F_8$ や $F_{16}$ の原始元のべき表現と既約因子の根との対応を見ると、上の内容がよくわかります。例えば $F_{16}$ では、既約多項式 $X^4+X+1$ の一つの根を $\alpha$ とすると、各既約因子と根との対応は、
\begin{eqnarray*}
X \ &:& \ 0 \\
X-1 \ &:& \ \alpha^0 \\
X^2+X+1 \ &:& \ \alpha^5, \alpha^{10} \\
X^4+X+1 \ &:& \ \alpha^1, \alpha^2, \alpha^4, \alpha^8 \\
X^4+X^3+1 \ &:& \ \alpha^{14}, \alpha^{13}, \alpha^{11}, \alpha^7 \\
X^4+X^3+X^2+X+1 \ &:& \ \alpha^3, \alpha^6, \alpha^{12}, \alpha^9
\end{eqnarray*}
のようになりました。$\alpha^{15}=1$ なので、これらの根を$2$乗すること、すなわち指数で見ると$2$をかけて$\mod 15$ をとることによって、
\begin{eqnarray*}
X-1 \ &:& 0 \to 0\\
X^2+X+1 \ &:& 5 \to 10 \to 5\\
X^4+X+1 \ &:& 1 \to 2 \to 4 \to 8 \to 1\\
X^4+X^3+1 \ &:& 14 \to 13 \to 11 \to 7 \to 14\\
X^4+X^3+X^2+X+1 \ &:& 3 \to 6 \to 12 \to 9 \to 3
\end{eqnarray*}
のようにそれぞれの既約多項式の中で巡回することがわかります。

 これでとりあえず前回の記事に関する検証ができたし、これ以上書くとボロが出るので、この辺までにしておきます。

nice!(0)  コメント(0) 
共通テーマ:学問

RICOH THETA を使って360度写真を撮ってみた [日常生活]

 今更ながら、360度パノラマ写真が撮れるカメラ(RICOH THETA SC2)を買ったので、テスト的に何か広い場所で景色を撮ろうと出かけてきました。
 というわけで、雨の淀川河川敷の風景です。PCだとマウスでつかんでグリグリ回せます。スマホだと自分がグルグル回れば画像もグルグル回るのでより臨場感があります。





 このブログへの埋め込みのためには、THETAの公式サイトにアップロードしてもよいのですが、公開範囲がより細かく設定できてスマホのグルグル機能?もある「ハコスコストア」を使うことにしました。
 また、下の方には撮影者の姿と指が写っていて不恰好ですが、一応ボカシを入れてちょっとは見やすくしました。360度写真といってもデータは普通のJPEGファイルなので、フリーの画像編集ソフトで加工できます。

 全体の雰囲気が手軽に記録できるので、これからちょくちょく使おうかと。

nice!(0)  コメント(0) 
共通テーマ:日記・雑感

有限体の勉強 〜標数2の有限体の加算乗算表を作る〜 [数学]

 自分が有限体についてあまりに無知なので、改めて勉強してみました。

 有限体とは文字どおり、有限個の元で構成される体(四則演算が定義された代数系)のことですが、これについては、
 ① 有限体の位数(元の数)$q$は、ある素数$p$と正整数$n$によって $q=p^n$ で表されるものに限る。
 ② 位数 $p^n$ の有限体は同型を除いて唯一存在し、その標数は$p$である。
ということがどの本にも書いてあります。以下では位数$q$の有限体を $F_q$ で表します。
 では、例えば標数$2$の有限体を考えると、小さい方から $F_2, F_4, F_8, F_{16}, \cdots$ という有限体が存在することになりますが、これらがどのような構造をしているかについてはなかなかピンときません。なので、自分で手を動かして考えてみました。

(1) $F_2$ の構造

 まず一番簡単な $F_2$ から始めます。これは単に整数環 $\mathbb{Z}$ をイデアル $2\mathbb{Z}$ で割った剰余環がそのまま体になったもの、すなわち $F_2 = \mathbb{Z}/2\mathbb{Z}$ なので、その加算表と乗算表は次のようになります。

+ 0 1
0 0 1
1 1 0


× 0 1
0 0 0
1 0 1


(2) $F_4$ の構造

 $F_2$ に係数をもつ多項式環 $F_2[X]$ を考えます。$F_2$ 上の$2$次の多項式は、
\[ X^2, \quad X^2+1, \quad X^2+X, \quad X^2+X+1 \]
の$4$通りですが、このうち $X^2+X+1$ は$0$も$1$も根にならないので、$1$次の因子で分解できない既約多項式です(他の$3$つが可約であることはすぐわかります)。従って、$F_2[X]$ をイデアル $(X^2+X+1)$ で割った剰余環 $F_2[X]/(X^2+X+1)$ は体になり、拡大次数$2$の $F_2$ の拡大体です。これは位数 $2^2=4$ をもつので、これが $F_4$ に他ならないことになります。
 もっと直感的に考えると、$X^2+X+1$ の$1$つの根 $\alpha$ を考え、それを $F_2$ に添加した根体 $F_2(\alpha)$ が $F_4$ である、ということになります。
 この $\alpha$ を使うと、$F_4$ は基底 $(\alpha, 1)$ を持つ $F_2$ 上の$2$次元ベクトル空間なので、$F_4$ の元は、
\[ 0, \quad 1, \quad \alpha, \quad \alpha+1 \]
の$4$つになります。これらを簡単に
\[ 00, \quad 01, \quad 10, \quad 11 \]
と表し、「ベクトル表現」と呼びます。このベクトル表現を用いて加算表、乗算表を作ると、次のようになります。

+ 00 01 10 11
00 00 01 10 11
01 01 00 11 10
10 10 11 00 01
11 11 10 01 00


× 00 01 10 11
00 00 00 00 00
01 00 01 10 11
10 00 10 11 01
11 00 11 01 10


 ここで加算表を作るのは、単にベクトル空間における加算なので、それぞれの係数を $F_2$上で加算すればいいだけです。問題は乗算表ですが、普通に $\alpha$ 混じりの多項式と考えて乗算し、
\[ \alpha^2 = \alpha + 1 \]
を使って $\alpha^2$ の項を消せば答えが出ます(標数$2$なのでマイナスとプラスの違いはないことに注意)。少し面倒ですがここまでくらいは何とかなります。
 黄色で塗った部分は $F_2$ に相当し、$F_2$ が $F_4$ の部分体であることがわかります。
 ところで、$F_4$ 上の多項式として、
\begin{eqnarray*}
X^4-X &=& X(X-1)(X^2+X+1) \\
&=& X(X-1)(X-\alpha)(X-(\alpha+1))
\end{eqnarray*}
が成り立つので、$F_4$ は $F_2$ 上の多項式 $X^4-X$ の最小分解体として特徴づけられます。これは実際には一般の有限体 $F_q \ (q=p^n)$ についても成立し、$F_q$ は $F_p$ 上の多項式 $X^q-X$ の最小分解体となります。


(3) $F_8$ の構造

 $F_4$ でやったことと同じようにして $F_2$ から $F_8$ を構成します。$F_2$ 上の多項式 $X^8-X$ は、
\[ X^8-X = X(X-1)(X^3+X+1)(X^3+X^2+1) \]
と既約多項式に分解されるので、このうち$3$次の既約多項式の$1$つ $X^3+X+1$ をとります(これが既約になることは、もし可約ならば$1$次の因子を持つので、$X$に$0$または$1$を代入すると$0$になるはずですが、そうはならないことからわかります)。この多項式の$1$つの根 $\alpha$ を $F_2$ に添加した拡大体 $F_2(\alpha)$ を考えると、これは拡大次数$3$の $F_2$ の拡大体ですから位数が $2^3=8$ となって、$F_8$ と同型になります。
 $F_4$ と同じように、基底を $(\alpha^2, \alpha, 1)$ としたベクトル表現で加算表と乗算表を作ることを考えます。加算表は簡単で、次のようになります。

+ 000 001 010 011 100 101 110 111
000 000 001 010 011 100 101 110 111
001 001 000 011 010 101 100 111 110
010 010 011 000 001 110 111 100 101
011 011 010 001 000 111 110 101 100
100 100 101 110 111 000 001 010 011
101 101 100 111 110 001 000 011 010
110 110 111 100 101 010 011 000 001
111 111 110 101 100 011 010 001 000


 乗算表についても地道に計算して $\alpha^3 = \alpha+1$ を使って $\alpha$ の$3$次以上の項を消せばよいのですが、なにぶん埋めるべきマスの数が多いのでとても面倒です。もうちょっと楽をすることを考えます。
 実は $F_8$ の元のうち$0$を除いた$7$個については、$\alpha$ のべき乗との間に次の関係があります。

べき表現 ベクトル表現
$\alpha^0$ 001
$\alpha^1$ 010
$\alpha^3$ 011
$\alpha^2$ 100
$\alpha^6$ 101
$\alpha^4$ 110
$\alpha^5$ 111


これくらいの計算はまだ頑張る気になる範囲です。これを見ると、$\alpha$ は $F_8$ の乗法群 $F_8^\times$ の原始元になっていることがわかります。$F_8^\times$ の位数は$7$なので $\alpha^7 = 1 = \alpha^0$ です。すなわち $\alpha$ の指数は $\mod 7$ で計算すればよいわけです。
 べき表現だと $F_8^\times$ の乗算表はEXCELなどのスプレッドシートで簡単に作れます。指数を足し算して $\mod 7$ を取ればいいのです。指数だけ記載すると次の表になります。

× 0 1 3 2 6 4 5
0 0 1 3 2 6 4 5
1 1 2 4 3 0 5 6
3 3 4 6 5 2 0 1
2 2 3 5 4 1 6 0
6 6 0 2 1 5 3 4
4 4 5 0 6 3 1 2
5 5 6 1 0 4 2 3


 これをベクトル表現に置き換えて、$0$の行と列を付け加えると、次の乗算表が出来上がります。

× 000 001 010 011 100 101 110 111
000 000 000 000 000 000 000 000 000
001 000 001 010 011 100 101 110 111
010 000 010 100 110 011 001 111 101
011 000 011 110 101 111 100 001 010
100 000 100 011 111 110 010 101 001
101 000 101 001 100 010 111 011 110
110 000 110 111 001 101 011 010 100
111 000 111 101 010 001 110 100 011


 これで $F_8$ 加算表と乗算表が書けました。黄色で塗った部分は $F_2$ に相当し、$F_2$ が $F_8$ の部分体であることがわかります。一方で $F_4$ は $F_8$ の部分体にはなりません。なぜなら $4^n=8$ となる正整数$n$が存在しないからです。
 ところで、$F_2$ 上の多項式 $X^8-X$ の各既約因子の根をべき表現で表すと、
\begin{eqnarray*}
X \ &:& \ 0 \\
X-1 \ &:& \ \alpha^0 \\
X^3+X+1 \ &:& \ \alpha^1, \alpha^2, \alpha^4 \\
X^3+X^2+1 \ &:& \ \alpha^3, \alpha^6, \alpha^5
\end{eqnarray*}
となります。この場合、$2$つの$3$次の既約多項式のどちらをとっても、その根は $F_8^\times$ の原始元になり、同様な $F_8$ の加算表と乗算表が作れます。また既約多項式の根は$2$乗しても同じ既約多項式の根になっていることがわかります。これは偶然ではなく、比較的簡単に証明できる事実です。


(4) $F_{16}$ の構造

 $F_{16}$ の加算表と乗算表の作り方も、$F_8$ のやり方を踏襲できます。$F_2$ 上の多項式 $X^{16}-X$ は、
\[ X^{16}-X = X(X-1)(X^2+X+1)(X^4+X+1)(X^4+X^3+1)(X^4+X^3+X^2+X+1) \]
と既約多項式に分解されるので、このうち$4$次の既約多項式の$1$つ $X^4+X+1$ をとります(既約性の確認は$3$次と違って一手間かかります)。この多項式の$1$つの根 $\alpha$ を $F_2$ に添加した拡大体 $F_2(\alpha)$ を考えると、これは拡大次数$4$の $F_2$ の拡大体ですから位数が $2^4=16$ となって、$F_{16}$ と同型になります。
 基底を $(\alpha^3, \alpha^2, \alpha, 1)$ としたベクトル表現で、まず加算表を作ると次のようになります。

+ 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0000 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0001 0001 0000 0011 0010 0101 0100 0111 0110 1001 1000 1011 1010 1101 1100 1111 1110
0010 0010 0011 0000 0001 0110 0111 0100 0101 1010 1011 1000 1001 1110 1111 1100 1101
0011 0011 0010 0001 0000 0111 0110 0101 0100 1011 1010 1001 1000 1111 1110 1101 1100
0100 0100 0101 0110 0111 0000 0001 0010 0011 1100 1101 1110 1111 1000 1001 1010 1011
0101 0101 0100 0111 0110 0001 0000 0011 0010 1101 1100 1111 1110 1001 1000 1011 1010
0110 0110 0111 0100 0101 0010 0011 0000 0001 1110 1111 1100 1101 1010 1011 1000 1001
0111 0111 0110 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000
1000 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111
1001 1001 1000 1011 1010 1101 1100 1111 1110 0001 0000 0011 0010 0101 0100 0111 0110
1010 1010 1011 1000 1001 1110 1111 1100 1101 0010 0011 0000 0001 0110 0111 0100 0101
1011 1011 1010 1001 1000 1111 1110 1101 1100 0011 0010 0001 0000 0111 0110 0101 0100
1100 1100 1101 1110 1111 1000 1001 1010 1011 0100 0101 0110 0111 0000 0001 0010 0011
1101 1101 1100 1111 1110 1001 1000 1011 1010 0101 0100 0111 0110 0001 0000 0011 0010
1110 1110 1111 1100 1101 1010 1011 1000 1001 0110 0111 0100 0101 0010 0011 0000 0001
1111 1111 1110 1101 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001 0000


 乗算表を作るために、$F_8$ でやったのと同様に、$\alpha$ のべき表現とベクトル表現との対応表を作ります。

べき表現 ベクトル表現
$\alpha^0$ 0001
$\alpha^1$ 0010
$\alpha^4$ 0011
$\alpha^2$ 0100
$\alpha^8$ 0101
$\alpha^5$ 0110
$\alpha^{10}$ 0111
$\alpha^3$ 1000
$\alpha^{14}$ 1001
$\alpha^9$ 1010
$\alpha^7$ 1011
$\alpha^6$ 1100
$\alpha^{13}$ 1101
$\alpha^{11}$ 1110
$\alpha^{12}$ 1111


 $F_{16}^\times$ の位数は$15$なので $\alpha^{15} = 1 = \alpha^0$ です。すなわち $\alpha$ の指数は $\mod 15$ で計算すればよいわけです。$F_8$ でやったのと同様にべき表現での乗算表をEXCELなどのスプレッドシートで作り、それをベクトル表現に置き換えて$0$の行と列を追加すると、次のように $F_{16}$ の乗算表が出来上がります。

× 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
0001 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0010 0000 0010 0100 0110 1000 1010 1100 1110 0011 0001 0111 0101 1011 1001 1111 1101
0011 0000 0011 0110 0101 1100 1111 1010 1001 1011 1000 1001 1110 0111 0100 0001 0010
0100 0000 0100 1000 1100 0011 0111 1011 1111 0110 0010 1110 1010 0101 0001 1101 1001
0101 0000 0101 1010 1111 0111 0010 1101 1000 1110 1011 0100 0001 1001 1100 0011 0110
0110 0000 0110 1100 1010 1011 1101 0111 0001 0101 0011 1001 1111 1110 1000 0010 0100
0111 0000 0111 1110 1001 1111 1000 0001 0110 1101 1010 0011 0100 0010 0101 1100 1011
1000 0000 1000 0011 1011 0110 1110 0101 1101 1100 0100 1111 0111 1010 0010 1001 0001
1001 0000 1001 0001 1000 0010 1011 0011 1010 0100 1101 0101 1100 0110 1111 0111 1110
1010 0000 1010 0111 1001 1110 0100 1001 0011 1111 0101 1000 0010 0001 1011 0110 1100
1011 0000 1011 0101 1110 1010 0001 1111 0100 0111 1100 0010 1001 1101 0110 1000 0011
1100 0000 1100 1011 0111 0101 1001 1110 0010 1010 0110 0001 1101 1111 0011 0100 1000
1101 0000 1101 1001 0100 0001 1100 1000 0101 0010 1111 1011 0110 0011 1110 1010 0111
1110 0000 1110 1111 0001 1101 0011 0010 1100 1001 0111 0110 1000 0100 1010 1011 0101
1111 0000 1111 1101 0010 1001 0110 0100 1011 0001 1110 1100 0011 1000 0111 0101 1010


 これで $F_{16}$ の加算表と乗算表が書けました。黄色で塗ったのは $F_4$ に相当する部分で、$F_4$ が $F_{16}$ の部分体になることがわかります。もちろん $F_2$ も $F_{16}$ の部分体ですが、$F_8$ は $F_{16}$ の部分体にはなりません。
 ところで、$F_2$ 上の多項式 $X^{16}-X$ の各既約因子の根をべき表現で表すと、
\begin{eqnarray*}
X \ &:& \ 0 \\
X-1 \ &:& \ \alpha^0 \\
X^2+X+1 \ &:& \ \alpha^5, \alpha^{10} \\
X^4+X+1 \ &:& \ \alpha^1, \alpha^2, \alpha^4, \alpha^8 \\
X^4+X^3+1 \ &:& \ \alpha^{14}, \alpha^{13}, \alpha^{11}, \alpha^7 \\
X^4+X^3+X^2+X+1 \ &:& \ \alpha^3, \alpha^6, \alpha^{12}, \alpha^9
\end{eqnarray*}
となります。この場合、$3$つの$4$次の既約多項式のうち、$X^4+X+1$ と $X^4+X^3+1$ の根は $F_{16}^\times$ の原始元になりますが、$X^4+X^3+X^2+X+1$ の根は原始元にはなりません(もちろん $X^2+X+1$ の根も原始元にはなりません)。$X^4+X^3+X^2+X+1$ の根をもとにベクトル表現を考えると、乗算表を作るときに上での方法が使えずに苦労する羽目になります。
 既約多項式の根が$2$乗しても同じ既約多項式の根になっているのは、$F_8$ や $F_4$ など他の標数2の有限体と同様です。

 とりあえずここまで。

(本記事の加算表と乗算表は、LibreOfficeで作成したものをこのサイトを使用してHTMLに変換したものです。サイトの作成者様に感謝いたします。)

nice!(0)  コメント(0) 
共通テーマ:学問

平日のみ運行のバス乗り継ぎで桜満開の和歌山県を縦断 [バス]

 年度末が近づき年休がまた流れるので、消化のため先日休みを取り、かねてから乗りたかった平日のみ運行するバスを乗り継いで紀伊半島の奥まで行ってきました。
 ちょうど桜が満開で、天気も良く絶好の乗りバス日和です。



 今回乗ったのは3路線。和歌山市駅から有田川町金屋を通って日高川町の川原河までを結ぶ有田鉄道バス、川原河から田辺市旧龍神村の西まで結ぶ田辺市住民バス、それと旧龍神村と紀伊田辺駅を結ぶ龍神バスです。このうち前者の2路線は平日のみの運転です。有田川町から日高川町を経由して旧龍神村へは国道424号線で結ばれていますが、路線バスでこのルートを通り抜けるためには平日に休みを取る必要があります。

 最近駅舎が綺麗になった南海和歌山市駅からスタートです。

2021-03-26 10.15.19.jpg

 駅前広場も綺麗になりましたが、案の定ここは和歌山バスが独占していて、有田鉄道バスの乗り場がありません。

2021-03-26 10.29.13.jpg

2021-03-26 10.17.45.jpg

 バスの案内所に尋ねて、ようやくちょっと外れた場所にある有田鉄道バスの乗り場に行き着きました。これはとてもわかりにくいです。

2021-03-26 10.26.32.jpg

2021-03-26 10.23.47.jpg

 平日1日2本しか走らない有田鉄道バスに乗ります。意外なことに PayPay 対応でした。

2021-03-26 10.38.44.jpg

2021-03-26 10.45.23.jpg

 和歌山市駅から海南駅までは市街地を走ります。途中2箇所の病院の前を通り、乗客を拾っています。この病院需要があるので生き残っているのかもしれません。

2021-03-26 10.56.10.jpg

2021-03-26 11.12.52.jpg

2021-03-26 11.33.56.jpg

 海南駅を出ると海南ICから有田ICまで阪和自動車道でワープします。ちゃんとシートベルト着用のアナウンスが流れます。

2021-03-26 11.38.51.jpg

2021-03-26 11.42.13.jpg

2021-03-26 11.49.08.jpg

 高速を降りると、かつて走っていた有田鉄道の線路跡と平行する県道22号線の旧道に沿って、集落が連続する風景の中を走ります。

2021-03-26 11.58.46.jpg

 旧有田鉄道の車両などが動態保存されている有田川鉄道公園の脇を通り過ぎると、間も無く旧金屋口駅跡にある有田鉄道金屋口の営業所に着きます。

2021-03-26 11.59.47.jpg

2021-03-26 12.00.39.jpg

 金屋口を出ると金屋の集落を少し巡ったのち、有田川に沿って南に向かいます。
 ところどころ桜が綺麗に咲いていました。

2021-03-26 12.06.28.jpg

2021-03-26 12.09.49.jpg

 有田川を離れてトンネルを抜けると、水系が変わって日高川町に入ります。

2021-03-26 12.18.19.jpg

2021-03-26 12.19.49.jpg

 山から降りてきて日高川に合流すると、間もなく終点の旧美山村の中心地の川原河に到着です。

2021-03-26 12.24.23.jpg

2021-03-26 12.30.21.jpg

2021-03-26 12.32.21.jpg

 川原河は地域のバス路線の乗換拠点になっており、日高川町美山支所に併設された真新しい乗り場が整備されています。待合室には充電ができるコンセントもあります。周囲にはJAのストアもあり便利ですが、飲食ができる店は無いようです。

2021-03-26 12.35.01.jpg

2021-03-26 12.36.13.jpg

2021-03-26 12.36.29.jpg

 待ち時間があるので周囲を散策しました。日高川と桜がとても綺麗でした。

2021-03-26 12.37.28.jpg

2021-03-26 12.45.17.jpg

2021-03-26 12.42.08.jpg

 少し歩くと地元の食堂があったので、カツ丼で昼食にしました。

2021-03-26 13.10.03.jpg

 バス乗り場に戻ると、熊野御坊南海バスと日高川町コミュニティーバス、それとこれから乗る田辺市住民バスが並んでいました。田辺市住民バスに乗り龍神へ向けて出発します。

2021-03-26 14.04.13.jpg

2021-03-26 14.19.56.jpg

 龍神までずっと同じ日高川に沿って走りますが、コミュニティーバスらしく所々狭い道に入り、小さな集落に立ち寄りながら進みます。
 この間もずっとあちこちに綺麗な桜が咲いていました。

2021-03-26 14.25.32.jpg

2021-03-26 14.56.26.jpg

2021-03-26 15.09.12.jpg

2021-03-26 15.17.47.jpg

 旧龍神村の中心地の西に到着です。地元のスーパーの駐車場がバス乗り場と回転場になっています。

2021-03-26 15.30.00.jpg

2021-03-26 15.32.55.jpg

2021-03-26 15.33.01.jpg

 龍神温泉はバスを乗り継いでもう少し先になりますが、今回は時間がないので温泉は諦めて、周囲を散歩しながら紀伊田辺駅行のバスを待つことにしました。

 建物に特徴がある旧龍神村役場(現田辺市行政局)です。

2021-03-26 15.41.38.jpg

 ここの日高川の眺めもなかなか良いです。

2021-03-26 15.45.07.jpg

 少し上流側に歩くと、川沿いに桜の綺麗な場所があり、そこに中垣内のバス停があったので桜を眺めながらバスを待つことにしました。

2021-03-26 16.57.42.jpg

2021-03-26 17.01.29.jpg

2021-03-26 17.01.59.jpg

 紀伊田辺駅行の龍神バスが来たので乗ります。普段乗る客のいないバス停だからか運転手さんが驚いていました。

2021-03-26 17.09.20.jpg

 この龍神バスも PayPay が使えました。調べると和歌山県では去年あたりから、有田鉄道バス、熊野御坊南海バスと龍神バスで PayPay が使えるようになったそうです。

2021-03-26 17.46.39.jpg

 すぐに日高川を離れ、虎ヶ峰トンネルを抜けると風景がガラッと変わり、遠くの峰々が見渡せる山岳地帯になります。
 この地形の変化は、以前に訪れた四国の吉野川水系から仁淀川水系への変化と似ています。紀伊半島と四国とは地形的には繋がっていることが実感できました。

2021-03-26 17.31.01.jpg

2021-03-26 17.32.06.jpg

 山を降りてきて会津川に沿ってしばらく走ると、渓谷美で有名な奇絶峡を通ります。

2021-03-26 17.36.32.jpg

2021-03-26 17.48.45.jpg

2021-03-26 17.50.25.jpg

 田辺の市街地に入ると、間も無く紀伊田辺駅に到着です。

2021-03-26 17.58.07.jpg

2021-03-26 18.10.28.jpg

 川と山並みが美しい紀伊半島内陸部を、満開の桜を満喫しながら路線バスを乗り継いで縦断するという、有意義な年休の一日になりました。

「路線バス歩き」のすすめ(目次)へ


nice!(0)  コメント(0) 
共通テーマ:旅行

南河内の行き止まり集落に2Wayアクセスの金剛バスで訪問 [バス]

 2度目の緊急事態宣言も明けた大阪府。寒さも緩んできたので、乗りバス活動再開です。
 とはいえ不要不急の外出はまだ憚られる状況下なので、今回は府内の範囲で行ってきました。南河内郡3町村に路線を持つ金剛バスです。



 金剛バスの路線の中でも、河南町の平石に行く路線は特に本数が少なく、平日に富田林駅とを結ぶ路線が1日2往復、土休日にはそれに加えて上ノ太子駅とを結ぶ路線が1日2往復走っているだけです。この上ノ太子駅系統は昨年6月から走り出した新規路線です。
 そういうわけで、平石は山の中の行き止まりの集落にもかかわらず、土休日だけですが2つの鉄道駅とを結ぶ「2Wayアクセス」が実現しました。上ノ太子駅→平石→富田林駅 と結ぶと乗り継ぎもうまく行くので、このルートで乗ってきました。

 近鉄南大阪線の上ノ太子駅からスタートです。太子町への玄関口になる駅ですが羽曳野市内にあり、コンビニもなく少々寂しい駅前です。

2021-03-07 15.24.42.jpg

 太子町の交通施策によって、2020年6月から町内向けに多くのバス便ができました。今回の目的地の平石へは土休日のみ2本あります。

2021-03-07 15.25.26.jpg

 昔から変わらない淡緑色の金剛バスが来ました。

2021-03-07 15.32.38-1.jpg

 駅を出るとすぐ、太子町内の聖和台ニュータウンを通り抜けます。

2021-03-07 15.40.38.jpg

 ニュータウンを抜けると太子町の中心部の旧市街を通ります。

2021-03-07 15.45.34.jpg

2021-03-07 15.49.01.jpg

 旧市街を抜けると、左手に葛城山系を見ながら南河内グリーンロードを南下します。途中で分岐する太子カントリー倶楽部前へは平日、休日ともに数本の便がありますが、このバスはまっすぐ平石を目指します。

2021-03-07 15.51.32.jpg

2021-03-07 15.56.26.jpg

 終点の平石に到着です。道路上で下車し、バックで回転場に入ります。
 運転手さんに「この路線で平石まで乗られたお客さんは初めてです」と言われました。

2021-03-07 15.58.48.jpg

2021-03-07 15.58.59.jpg

2021-03-07 16.01.15.jpg

 平石は河南町に位置し、アクセスする府道は徒歩ならば平石峠を通じて奈良県葛城市へ抜けられますが、車両は通り抜けできない行き止まりの集落です。

2021-03-07 16.00.01.jpg

 岩橋山への登山道が整備されていて、ハイキングには良さそうです。

2021-03-07 16.00.07.jpg

 富田林駅行のバスまでほぼ30分なので、周辺の散策にちょうどいい待ち時間です。河内平野が見下ろせる静かな集落で、ところどころ梅も咲いていました。

2021-03-07 16.01.56.jpg

2021-03-07 16.06.48.jpg

2021-03-07 16.08.11.jpg

 富田林駅行のバスが来たので、これに乗って帰ります。

2021-03-07 16.24.15.jpg

 集落を縫って下っていき、河南町の中心部を通り抜けます。

2021-03-07 16.31.10.jpg

2021-03-07 16.34.24.jpg

2021-03-07 16.34.56.jpg

2021-03-07 16.38.10.jpg

 PLの大平和祈念塔が見えると、石川を越えて間もなく富田林駅に到着です。

2021-03-07 16.41.41.jpg

2021-03-07 16.44.34.jpg

2021-03-07 16.50.08.jpg

 富田林駅からは各方面に金剛バスの路線があり、路線図も賑やかです。

2021-03-07 16.50.37.jpg

 大阪府内でも田園風景が広がる南河内郡3町村。乗客も年々減って厳しい中、域内にくまなく路線を走らせ続ける金剛バスですが、今後も時々乗って応援したいと思います。

「路線バス歩き」のすすめ(目次)へ


nice!(0)  コメント(0) 
共通テーマ:旅行

非可換な順序環の例 [数学]

 以前の記事「アルキメデス的な順序環は可換であることについて」で、
「アルキメデス的でない非可換な順序環の存在を例示したくなりますが、これが今のところなかなか思いつきません。」
と書きました。ところが10年以上前のノートを漁ったらこんな例を考えついていたようなので、紹介します。昔の僕は今よりは頭が冴えていたようです。

 $R$ を可換な順序環で零因子を持たないものとします。$\mathbb{Z}$ でも $\mathbb{R}$ でも何でも構いません。
 $R$ の元を成分にもつ次の形の$6$次正方行列を考えます。
\begin{equation*}
\left(
\begin{array}{cccccc}
x_1 & x_2 & x_4 & 0 & 0 & 0 \\
0 & x_1 & x_2 & 0 & 0 & 0 \\
0 & 0 & x_1 & 0 & 0 & 0 \\
0 & 0 & 0 & x_1 & x_2 & x_5 \\
0 & 0 & 0 & 0 & x_1 & x_3 \\
0 & 0 & 0 & 0 & 0 & x_1
\end{array}
\right)
\end{equation*}
これを簡単に $\langle x_1, \, x_2, \, x_3, \, x_4, \, x_5 \rangle$ と書くこととし、このような形をもつ行列全体を $S$ とおきます。$S$ は容易にわかるように、行列の演算に関して $M_6(R)$ の部分環になり、
\begin{eqnarray*}
&& \langle a_1, \, a_2, \, a_3, \, a_4, \, a_5 \rangle + \langle b_1, \, b_2, \, b_3, \, b_4, \, b_5 \rangle \\
&& \quad = \langle a_1+b_1, \, a_2+b_2, \, a_3+b_3, \, a_4+b_4, \, a_5+b_5 \rangle \\
&& \langle a_1, \, a_2, \, a_3, \, a_4, \, a_5 \rangle \langle b_1, \, b_2, \, b_3, \, b_4, \, b_5 \rangle \\
&& \quad = \langle a_1b_1, \, a_1b_2+a_2b_1, \, a_1b_3+a_3b_1, \, a_1b_4+a_2b_2+a_4b_1, \, a_1b_5+a_2b_3+a_5b_1 \rangle
\end{eqnarray*}
と表されます。

 そこで $S$ に次のように順序を定めます。$A = \langle a_1, \, a_2, \, a_3, \, a_4, \, a_5 \rangle, \ B = \langle b_1, \, b_2, \, b_3, \, b_4, \, b_5 \rangle$ に対して、
\begin{eqnarray*}
A < B \quad &\Leftrightarrow& \quad a_1 < b_1 \ \lor \\
&& \quad (a_1 = b_1 \land a_2 < b_2) \ \lor \\
&& \quad (a_1 = b_1 \land a_2 = b_2 \land a_3 < b_3) \ \lor \\
&& \quad (a_1 = b_1 \land a_2 = b_2 \land a_3 = b_3 \land a_4 < b_4) \ \lor \\
&& \quad (a_1 = b_1 \land a_2 = b_2 \land a_3 = b_3 \land a_4 = b_4 \land a_5 < b_5)
\end{eqnarray*}
と辞書式順序を定めると、これは $S$ の全順序になり、加法演算について
\begin{equation*}
A \le B \to A+C \le B+C
\end{equation*}
が成り立つことまではすぐにわかります。

 これがさらに乗法演算について
\begin{equation*}
A \ge 0 \land B \ge 0 \to AB \ge 0
\end{equation*}
をみたすことを確かめます($0$は零行列で、$S$ の環としての零元)。$A = \langle a_1, \, a_2, \, a_3, \, a_4, \, a_5 \rangle, \ B = \langle b_1, \, b_2, \, b_3, \, b_4, \, b_5 \rangle$ に対して $A \ge 0 \land B \ge 0$ が成り立つものとします。このとき、$R$ が零因子を持たないので、次のように場合分けをして $AB \ge 0$ が確認できます。

 ① $a_1 > 0, b_1 > 0$ のとき、$AB = \langle a_1b_1, \, *, \, *, \, *, \, * \rangle > 0$
 ② $a_1 > 0, b_1 = 0, b_2 > 0$ のとき、$AB = \langle 0, \, a_1b_2, \, *, \, *, \, * \rangle > 0$
 ③ $a_1 > 0, b_1 = b_2 = 0, b_3 > 0$ のとき、$AB = \langle 0, \, 0, \, a_1b_3, \, *, \, * \rangle > 0$
 ④ $a_1 > 0, b_1 = b_2 = b_3 = 0, b_4 > 0$ のとき、$AB = \langle 0, \, 0, \, 0, \, a_1b_4, \, * \rangle > 0$
 ⑤ $a_1 > 0, b_1 = b_2 = b_3 = b_4 = 0, b_5 > 0$ のとき、$AB = \langle 0, \, 0, \, 0, \, 0, \, a_1b_5 \rangle > 0$
 ⑥ $a_1 > 0, b_1 = b_2 = b_3 = b_4 = b_5 = 0$ のとき、$AB = \langle 0, \, 0, \, 0, \, 0, \, 0 \rangle = 0$
 ⑦ $a_1 = 0, a_2 > 0, b_1 > 0$ のとき、$AB = \langle 0, \, a_2b_1, \, *, \, *, \, * \rangle > 0$
 ⑧ $a_1 = 0, a_2 > 0, b_1 = 0, b_2 > 0$ のとき、$AB = \langle 0, \, 0, \, 0, \, a_2b_2, \, * \rangle > 0$
 ⑨ $a_1 = 0, a_2 > 0, b_1 = b_2 = 0, b_3 > 0$ のとき、$AB = \langle 0, \, 0, \, 0, \, 0, \, a_2b_3 \rangle > 0$
 ⑩ $a_1 = b_1 = b_2 = b_3 = 0$ のとき、$AB = \langle 0, \, 0, \, 0, \, 0, \, 0 \rangle = 0$
 ⑪ $a_1 = a_2 = 0, a_3 > 0, b_1 > 0$ のとき、$AB = \langle 0, \, 0, \, a_3b_1, \, *, \, * \rangle > 0$
 ⑫ $a_1 = a_2 = b_1 = 0$ のとき、$AB = \langle 0, \, 0, \, 0, \, 0, \, 0 \rangle = 0$
 ⑬ $a_1 = a_2 = a_3 = 0, a_4 > 0, b_1 > 0$ のとき、$AB = \langle 0, \, 0, \, 0, \, a_4b_1, \, * \rangle > 0$
 ⑭ $a_1 = a_2 = a_3 = a_4 = 0, a_5 > 0, b_1 > 0$ のとき、$AB = \langle 0, \, 0, \, 0, \, 0, \, a_5b_1 \rangle > 0$
 ⑮ $a_1 = a_2 = a_3 = a_4 = a_5 = 0, b_1 > 0$ のとき、$AB = \langle 0, \, 0, \, 0, \, 0, \, 0 \rangle = 0$

従って $S$ は順序環となります。

 $S$ が非可換であることは、$A = \langle 0, \, 1, \, 0, \, 0, \, 0 \rangle, \ B = \langle 0, \, 0, \, 1, \, 0, \, 0 \rangle$ とすると、
\begin{eqnarray*}
AB &=& \langle 0, \, 0, \, 0, \, 0, \, 1 \rangle \\
BA &=& \langle 0, \, 0, \, 0, \, 0, \, 0 \rangle
\end{eqnarray*}
より $AB \neq BA$ となることからわかります。

 というわけで、この $S$ が非可換な順序環の例になります。

 なかなか巧妙で面白い例ですが、もう少し簡単にはできないでしょうか?例えばこの形で$6$次正方行列ではなく、左上または右下の$3$次の小行列を取って同じように辞書式順序を定めたらどうなるでしょうか。
 左上の小行列をとって、
\begin{equation*}
\left(
\begin{array}{ccc}
x_1 & x_2 & x_4 \\
0 & x_1 & x_2 \\
0 & 0 & x_1
\end{array}
\right)
\end{equation*}
の形の $M_3(R)$ の部分集合を考え、これを $\langle x_1, \, x_2, \, x_4 \rangle$ と書き、その全体を $S_1$ とします。これは上三角行列なので $M_3(R)$ の部分環です。この乗法演算については
\begin{equation*}
\langle a_1, \, a_2, \, a_4 \rangle \langle b_1, \, b_2, \, b_4 \rangle = \langle a_1b_1, \, a_1b_2+a_2b_1, \, a_1b_4+a_2b_2+a_4b_1 \rangle
\end{equation*}
となりますから、同じように辞書式順序を定めると簡単な検証によって $S_1$ は順序環になることがわかります。しかし残念なことにこれは乗法演算について可換、すなわち可換環なので、非可換な順序環の例にはなりません。
 また、右下の小行列をとって、
\begin{equation*}
\left(
\begin{array}{ccc}
x_1 & x_2 & x_5 \\
0 & x_1 & x_3 \\
0 & 0 & x_1
\end{array}
\right)
\end{equation*}
の形の $M_3(R)$ の部分集合を考え、これを $\langle x_1, \, x_2, \, x_3, \, x_5 \rangle$ と書き、その全体を $S_2$ とします。これも上三角行列なので $M_3(R)$ の部分環です。この乗法演算については
\begin{equation*}
\langle a_1, \, a_2, \, a_3, \, a_5 \rangle \langle b_1, \, b_2, \, b_3, \, b_5 \rangle = \langle a_1b_1, \, a_1b_2+a_2b_1, \, a_1b_3+a_3b_1, \, a_1b_5+a_2b_3+a_5b_1 \rangle
\end{equation*}
となりますから、今度は $S_2$ は非可換環です。しかし同じように辞書式順序を定めると、$A = \langle 0, \, 1, \, *, \, * \rangle, \ B = \langle 0, \, 1, \, -1, \, * \rangle$ に対して $A > 0, B > 0$ かつ
\begin{equation*}
AB = \langle 0, \, 0, \, 0, \, -1 \rangle < 0
\end{equation*}
となりますから、$S_2$ は順序環の条件をみたしません。
 なかなか難しいものです。

nice!(0)  コメント(0) 
共通テーマ:学問

アカンポのアイデアに基づく実数体の構成法(自分なりのアレンジ) [数学]

 以前の記事 「アカンポ( Norbert A'Campo )の実数論について」発表レポート」 で紹介した、‘‘A natural construction for the real numbers’’ (2003年1月3日 arXiv投稿)ですが、本記事ではこのアイデアに基づいて実際に実数体を構成してみます。

 とはいっても、オリジナルのペーパーに載っている実数体の各性質の証明は、僕にとってはちょっと細かいテクニックが多くて難解だったので、アカンポのアイデアだけパクり、証明は自分なりのやり方で組んでみました。結果、「イデアルによる同値類」など馴染みのある手法を使って構成できて、もっとも面倒な完備性の証明も割と理解しやすいものになったと思います。少々長いですが、以下順を追って説明します。


(1) $\mathbb{R}$の構成

 $\mathbb{N}$を0を含む自然数の全体、$\mathbb{Z}$を整数の全体とし、これらの性質は既知とします。また、$\mathbb{N}_+ = \mathbb{N} \setminus \{0\}$ とします。
 最初に次の定義をおきます。

【定義1】$\mathbb{Z}$から$\mathbb{Z}$への奇関数$\alpha$について、集合 \begin{equation*} \{ \, \alpha(m+n)-\alpha(m)-\alpha(n) \, \mid \, m,n \in \mathbb{Z} \, \} \end{equation*} が有限、すなわち \begin{equation} \label{equ:スロープ} \left| \{ \, \alpha(m+n)-\alpha(m)-\alpha(n) \, \mid \, m,n \in \mathbb{Z} \, \} \right| < \omega \end{equation} をみたすとき、スロープと呼ぶ。スロープの全体を$\mathcal{S}$とおく。

 ここで$\omega$は最小の無限基数を表します。従って、集合$A$に対して $\left| A \right| < \omega$ とは$A$が有限集合であることを意味し、また、$\left| A \right| \ge \omega$ とは$A$が無限集合であることを意味します。$A \subseteq \mathbb{Z}$ に対して、$A$が有限集合であることと、有界であることとは同値です。
 アカンポの元の定義ではスロープは奇関数に限っていませんが、議論を簡単にするため本記事ではスロープとして奇関数のみを考えます。$\mathbb{Z}$から$\mathbb{Z}$への奇関数$\alpha$に対し、$\alpha$がスロープであることと次は同値になります。
\begin{equation}
\left| \{ \, \alpha(m+n)-\alpha(m)-\alpha(n) \, \mid \, m,n \in \mathbb{N} \, \} \right| < \omega \tag{1}
\end{equation}
この証明は $m, n, m+n$ の符号で場合分けすることにより簡単に得られます。

 次に、スロープの全体$\mathcal{S}$上に加法と乗法の演算を定めます。

【定義2】$\alpha, \beta \in \mathcal{S}$ に対し、 \begin{equation*} (\alpha + \beta)(n) = \alpha(n) + \beta(n) \end{equation*} によって$\mathcal{S}$上の加法演算$+$を定める。また、 \begin{equation*} (\alpha \cdot \beta)(n) = \alpha(\beta(n)) \end{equation*} によって$\mathcal{S}$上の乗法演算$\cdot$を定める。乗法演算記号は通常省略する。

 加法は関数の和、乗法は関数の合成と、どこかでよく見る演算の定義です。まずはこれらの演算が$\mathcal{S}$で閉じていることを示さなければなりません。

【定理1】演算 $+, \cdot$ は$\mathcal{S}$で閉じている。
(証明)$\alpha, \beta \in \mathcal{S}$ とする。$\alpha + \beta, \alpha \beta$ がともに奇関数であることは明らかである。
\begin{equation*}
E_\alpha = \{ \, \alpha(m+n)-\alpha(m)-\alpha(n) \, \mid \, m,n \in \mathbb{Z} \, \}, \ E_\beta = \{ \, \beta(m+n)-\beta(m)-\beta(n) \, \mid \, m,n \in \mathbb{Z} \, \}
\end{equation*}
とおくと、スロープの定義より $E_\alpha, E_\beta$ は有限集合である。
 まず加法について、任意の $m,n \in \mathbb{Z}$ に対し $u \in E_\alpha, v \in E_\beta$ が存在して、
\begin{eqnarray*}
\alpha(m+n) - \alpha(m) - \alpha(n) &=& u \\
\beta(m+n) - \beta(m) - \beta(n) &=& v
\end{eqnarray*}
とできる。これより
\begin{eqnarray*}
&& (\alpha + \beta)(m+n) - (\alpha + \beta)(m) - (\alpha + \beta)(n) \\
&=& (\alpha(m+n) - \alpha(m) - \alpha(n)) + (\beta(m+n) - \beta(m) - \beta(n)) \\
&=& u + v
\end{eqnarray*}
であるから、
\begin{eqnarray*}
&& \left| \{ \, (\alpha + \beta)(m+n)-(\alpha + \beta)(m)-(\alpha + \beta)(n) \, \mid \, m,n \in \mathbb{Z} \, \} \right| \\
&\le& \left| \{ \, u + v \, \mid \, u \in E_\alpha, v \in E_\beta \, \} \right| \\
&\le& \left| E_\alpha \right| \times \left| E_\beta \right| < \omega
\end{eqnarray*}
となり、従ってスロープの定義より $\alpha + \beta \in \mathcal{S}$ である。
 次に乗法について。任意の $m,n \in \mathbb{Z}$ に対し $u,u' \in E_\alpha, v \in E_\beta$ が存在して、
\begin{eqnarray*}
\alpha(\beta(m)+\beta(n)) - \alpha(\beta(m)) - \alpha(\beta(n)) &=& u \\
\beta(m+n) - \beta(m) - \beta(n) &=& v \\
\alpha(\beta(m)+\beta(n)+v) - \alpha(\beta(m)+\beta(n)) - \alpha(v) &=& u'
\end{eqnarray*}
とできる。これより
\begin{eqnarray*}
&& \alpha \beta(m+n) - \alpha \beta(m) - \alpha \beta(n) \\
&=& \alpha(\beta(m+n)) - \alpha(\beta(m)) - \alpha(\beta(n)) \\
&=& \alpha(\beta(m)+\beta(n)+v) - \alpha(\beta(m)+\beta(n)) + u \\
&=& \alpha(\beta(m)+\beta(n)) + \alpha(v) + u' - \alpha(\beta(m)+\beta(n)) + u \\
&=& \alpha(v) + u' + u
\end{eqnarray*}
であるから、
\begin{eqnarray*}
&& \left| \{ \, \alpha \beta(m+n)-\alpha \beta(m)-\alpha \beta(n) \, \mid \, m,n \in \mathbb{Z} \, \} \right| \\
&\le& \left| \{ \, \alpha(v) + u' + u \, \mid \, u, u' \in E_\alpha, v \in E_\beta \, \} \right| \\
&\le& \left| E_\beta \right| \times \left| E_\alpha \right| \times \left| E_\alpha \right| < \omega
\end{eqnarray*}
となり、従ってスロープの定義より $\alpha \beta \in \mathcal{S}$ である。□

 この演算によって$\mathcal{S}$で成り立つ法則は、次のようになります。

【定理2】$\mathcal{S}$上の演算において、次が成立する。
 i) 加法について可換群(加法単位元を$\bar{0}$とかき、$\alpha$の加法逆元を$-\alpha$とかく)
 ii) 乗法の結合則 $\quad (\alpha \beta) \gamma = \alpha (\beta \gamma)$
 iii) 乗法単位元の存在($\bar{1}$とかく)。
 iv) 加法と乗法の右分配則 $\quad (\alpha + \beta) \gamma = \alpha \gamma + \beta \gamma$

 証明はほとんど明らかなので省略します。加法単位元 $\bar{0}$ は定数値$0$をとる関数であり、乗法単位元 $\bar{1}$ は恒等関数です。$\mathcal{S}$においては、乗法の交換則と、左分配則は一般に成立しないことに注意します。

 次に、スロープの一部として「零スロープ」を定義します。

【定義3】$\alpha \in \mathcal{S}$ のうち \begin{equation} \left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \, \} \right| < \omega \tag{2} \end{equation} をみたすものを零スロープと呼び、その全体を$\mathcal{I}$とおく。

 これはつまり、値域が有限集合すなわち有界であるようなスロープのことです。奇関数なので上の条件は$\mathbb{N}$を$\mathbb{Z}$に置き換えても同じです。
 こう定めた零スロープの全体$\mathcal{I}$について、次が成り立ちます。

【定理3】$\mathcal{I}$は加法に関して$\mathcal{S}$の部分群であり、さらに
\begin{equation*}
\forall \alpha \in \mathcal{I} \, \forall \beta \in \mathcal{S} \, (\alpha \beta \in \mathcal{I} \land \beta \alpha \in \mathcal{I})
\end{equation*}
が成り立つ。すなわち$\mathcal{I}$は$\mathcal{S}$の両側イデアルである。

(証明)前半は明らかなので後半を示す。$\alpha \in \mathcal{I}, \beta \in \mathcal{S}$ とすると、
\begin{eqnarray*}
\left| \{ \, (\alpha \beta)(n) \, \mid \, n \in \mathbb{N} \, \} \right| &=& \left| \{ \, \alpha(\beta(n)) \, \mid \, n \in \mathbb{N} \, \} \right| \\
&\le& \left| \{ \, \alpha(m) \, \mid \, m \in \mathbb{Z} \, \} \right| \\
&<& \omega
\end{eqnarray*}
であるから$(2)$より $\alpha \beta \in \mathcal{I}$ であり、また
\begin{eqnarray*}
\left| \{ \, (\beta \alpha)(n) \, \mid \, n \in \mathbb{N} \, \} \right| &=& \left| \{ \, \beta(\alpha(n)) \, \mid \, n \in \mathbb{N} \, \} \right| \\
&\le& \left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \, \} \right| \\
&<& \omega
\end{eqnarray*}
であるから$(2)$より $\beta \alpha \in \mathcal{I}$ である。□

 ここで実数の定義です。

【定義4】$\alpha, \alpha' \in \mathcal{S}$ に対し、 \begin{equation*} \alpha \sim \alpha' \quad \Leftrightarrow \quad \alpha - \alpha' \in \mathcal{I} \end{equation*} によって$\mathcal{S}$上の関係 $\sim$ を定める。これは明らかに同値関係だから、$\mathcal{S}$の $\sim$ による同値類を実数と呼び、その全体を$\mathbb{R}$とかく。

 このように定義した実数の全体$\mathbb{R}$が、実数体の性質を持つ(完備性をもつ順序体である)ことを証明することが目標です。


(2) 可換環であること

 $\mathbb{R}$には次によって自然に加法演算$+$と乗法演算 $\cdot$ が定まります。以下、$\mathbb{R}$において代表元を$\alpha$とする同値類(実数)を $[\alpha]$ で表すこととします。

【定義5】$a,b \in \mathbb{R}, a=[\alpha], b=[\beta] \ (\alpha, \beta \in \mathcal{S})$ に対し、次によって加法演算と乗法演算を定める。 \begin{eqnarray*} a+b &=& [\alpha + \beta] \\ a \cdot b &=& [\alpha \cdot \beta] \end{eqnarray*} 乗法演算記号は通常省略する。

 $\mathcal{S}$が環ならば、環の両側イデアルによる剰余環としてすぐさま$\mathbb{R}$は環になるのですが、$\mathcal{S}$が左分配則をみたさないのですぐにはうまくいきません。でもこれは次の補題によって解決されます。

【補題4】$\alpha, \beta \in \mathcal{S}$ に対して次が成立する。
\begin{equation*}
\alpha \beta - \beta \alpha \in \mathcal{I}
\end{equation*}

 この補題は次の補題を用いて証明できます。

【補題5】$\alpha \in \mathcal{S}$ ならば、
\begin{equation*}
\forall m,n \in \mathbb{Z} \, ( \left| \alpha(m+n) - \alpha(m) - \alpha(n) \right| \le M )
\end{equation*}
をみたす $M \in \mathbb{N}$ が存在して、
\begin{equation}
\forall k,n \in \mathbb{Z} \, ( \left| \alpha(kn) - k\alpha(n) \right| \le \left| k \right| M ) \tag{3}
\end{equation}
が成り立つ。

(証明)スロープの定義より、条件をみたす $M \in \mathbb{N}$ が存在することは明らかである。この$M$に対して$(3)$を示す。$k \ge 0$ に対しては$k$に関する帰納法で証明する。$k=0$ のときは$\alpha$が奇関数だから明らか。$k$のときに成り立つならば、任意の $n \in \mathbb{Z}$ に対して
\begin{eqnarray*}
\left| \alpha((k+1)n) - (k+1)\alpha(n) \right| &\le& \left| \alpha(kn+n) - \alpha(kn) - \alpha(n) \right| + \left| \alpha(kn) - k\alpha(n) \right| \\
&\le& M + kM \\
&=& (k+1)M
\end{eqnarray*}
より、$k+1$のときにも成り立つ。よって帰納法により $k \ge 0$ のときは示された。$k < 0$ のときは、$\alpha$が奇関数だから任意の $n \in \mathbb{Z}$ に対して、
\begin{equation*}
\left| \alpha(kn) - k\alpha(n) \right| = \left| -\alpha((-k)n) + (-k)\alpha(n) \right| = \left| \alpha((-k)n) - (-k)\alpha(n) \right| \le (-k)M
\end{equation*}
となるから、$(3)$が成立する。□

(【補題4】の証明)【補題5】より $M_\alpha, M_\beta \in \mathbb{N}$ が存在して、
\begin{equation*}
\forall k,n \in \mathbb{Z} \, ( \left| \alpha(kn) - k\alpha(n) \right| \le \left| k \right| M_\alpha \land \left| \beta(kn) - k\beta(n) \right| \le \left| k \right| M_\beta )
\end{equation*}
が成り立つ。これらに対し、$n \in \mathbb{N}_+$ として、
\begin{eqnarray*}
\left| n\alpha(\beta(n)) - \beta(n)\alpha(n) \right| &\le& \left| n\alpha(\beta(n)) - \alpha(n\beta(n)) \right| + \left| \alpha(n\beta(n)) - \beta(n)\alpha(n) \right| \\
&\le& nM_\alpha + \left| \beta(n) \right| M_\alpha \\
&\le& (n + \left| \beta(n) - n\beta(1) \right| + \left| n\beta(1) \right|) M_\alpha \\
&\le& n(1 + M_\beta + \left| \beta(1) \right|) M_\alpha
\end{eqnarray*}
同様に、
\begin{equation*}
\left| n\beta(\alpha(n)) - \alpha(n)\beta(n) \right| \le n(1 + M_\alpha + \left| \alpha(1) \right|) M_\beta
\end{equation*}
これらより、
\begin{eqnarray*}
n \left| \alpha(\beta(n)) - \beta(\alpha(n)) \right| &\le& \left| n\alpha(\beta(n)) - \beta(n)\alpha(n) \right| + \left| \alpha(n)\beta(n) - n\beta(\alpha(n)) \right| \\
&\le& n(1 + M_\beta + \left| \beta(1) \right|) M_\alpha + n(1 + M_\alpha + \left| \alpha(1) \right|) M_\beta
\end{eqnarray*}
$n \ge 1$ だから両辺を$n$で割って、
\begin{equation*}
\left| \alpha(\beta(n)) - \beta(\alpha(n)) \right| \le (1 + M_\beta + \left| \beta(1) \right|) M_\alpha + (1 + M_\alpha + \left| \alpha(1) \right|) M_\beta
\end{equation*}
これより
\begin{equation}
\left| \{ \, \alpha(\beta(n)) - \beta(\alpha(n)) \, \mid \, n \in \mathbb{N} \, \} \right| < \omega
\end{equation}
が従うから、$\alpha \beta - \beta \alpha \in \mathcal{I}$ である。□

 これで、無事に$\mathbb{R}$が可換環であることを示すことができます。

【定理6】演算 $+, \cdot$ は正しく定義されており、これによって$\mathbb{R}$は可換環となる。
(証明)まず、演算が正しく定義されていることを示す。$\alpha, \alpha', \beta, \beta' \in \mathcal{S}, \alpha \sim \alpha', \beta \sim \beta'$ とする。このとき $\alpha - \alpha' \in \mathcal{I}, \beta - \beta' \in \mathcal{I}$ である。
 加法については、$\mathcal{I}$が$\mathcal{S}$の両側イデアルであることより、
\begin{equation*}
(\alpha + \beta) - (\alpha' + \beta') = (\alpha - \alpha') + (\beta - \beta') \in \mathcal{I}
\end{equation*}
となるから正しく定義されている。
 乗法については、$\mathcal{I}$が$\mathcal{S}$の両側イデアルであることと【補題4】より、
\begin{eqnarray*}
\alpha \beta - \alpha' \beta' &=& \alpha \beta - \beta \alpha + \beta \alpha - \beta' \alpha + \beta' \alpha - \alpha \beta' + \alpha \beta' - \alpha' \beta' \\
&=& (\alpha \beta - \beta \alpha) + (\beta - \beta') \alpha + (\beta' \alpha - \alpha \beta') + (\alpha - \alpha') \beta' \\
&\in& \mathcal{I}
\end{eqnarray*}
となるから正しく定義されている。
 続いて$\mathbb{R}$が可換環となることを示す。演算の定義より、【定理2】で示された$\mathcal{S}$と同じ演算法則が$\mathbb{R}$でも成立する。さらに【補題4】より乗法交換則が成り立ち、従って左分配則も成り立つ。従って$\mathbb{R}$は可換環である。□

 これ以降、$\mathbb{R}$の加法単位元を$0$で、乗法単位元を$1$で表します。$\mathbb{Z}$のそれらと同じですが混乱はしないはずです。
 $\mathbb{R}$が体であること、すなわち$0$以外の元に対する乗法逆元の存在を示すことは、少し複雑になるので後に回します。


(3) 順序環であること

 続いて$\mathbb{R}$に順序を定義し、順序環となることを示します。このため、スロープの一部として「非負スロープ」を定義します。

【定義6】$\alpha \in \mathcal{S}$ のうち \begin{equation} \label{equ:非負スロープ} \left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \land \alpha(n) < 0 \, \} \right| < \omega \end{equation} をみたすものを非負スロープと呼び、その全体を$\mathcal{P}$とおく。

 非負スロープとはつまり、引数と符号が異なる値はたかだか有限個であるようなスロープのことです。

【定理7】$\mathcal{P}$に関して次が成立する。
 i) $\alpha \in \mathcal{S} \to \alpha \in \mathcal{P} \lor -\alpha \in \mathcal{P}$
 ii) $\alpha \in \mathcal{P} \land -\alpha \in \mathcal{P} \leftrightarrow \alpha \in \mathcal{I}$
 iii) $\alpha \in \mathcal{P} \land \beta \in \mathcal{P} \to \alpha + \beta \in \mathcal{P}$
 iv) $\alpha \in \mathcal{P} \land \beta \in \mathcal{P} \to \alpha \beta \in \mathcal{P}$

(証明)
 はじめに、$-\alpha \in \mathcal{P}$ であるための条件は
\begin{equation*}
\left| \{ \, -\alpha(n) \, \mid \, n \in \mathbb{N} \land -\alpha(n) < 0 \, \} \right| < \omega
\end{equation*}
であり、これは
\begin{equation*}
\left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \land \alpha(n) > 0 \, \} \right| < \omega
\end{equation*}
と同値であることに注意しておく。

i) $\alpha \in \mathcal{S} \land \alpha \notin \mathcal{P} \land -\alpha \notin \mathcal{P}$ と仮定して矛盾を導く。スロープの定義よりある $M \in \mathbb{N}$ が存在して、
\begin{equation*}
\forall m,n \in \mathbb{Z} \, (-M \le \alpha(m+n) - \alpha(m) - \alpha(n) \le M)
\end{equation*}
が成り立つ。一方、仮定より、
\begin{equation}
\left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \land \alpha(n) < 0 \, \} \right| \ge \omega \ \land \ \left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \land \alpha(n) > 0 \, \} \right| \ge \omega \tag{4}
\end{equation}
が成り立つから、$\left| \alpha(p) \right| > M$ をみたす最小の $p \in \mathbb{N}_+$ が存在する。
 $\alpha(p) > M$ の場合を考える。任意の $n \in \mathbb{N}_+$ に対し $n=qp+r \quad (q,r \in \mathbb{N} \land 0 \le r < p)$ とすることができて、【補題5】より
\begin{equation*}
\alpha(n) = \alpha(qp+r) \ge \alpha(qp) + \alpha(r) - M \ge q\alpha(p) - qM - M -M \ge -2M
\end{equation*}
となる。これは、
\begin{equation*}
\left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \land \alpha(n) < 0 \, \} \right| < \omega
\end{equation*}
を意味するから$(4)$に矛盾する。
 $\alpha(p) < -M$ の場合も同様に、任意の $n \in \mathbb{N}_+$ に対し $n=qp+r \quad (q,r \in \mathbb{N} \land 0 \le r < p)$ とすることができて、
\begin{equation*}
\alpha(n) = \alpha(qp+r) \le \alpha(qp) + \alpha(r) + M \le q\alpha(p) + qM + M + M \le 2M
\end{equation*}
となってやはり$(4)$に矛盾するから、仮定が誤りである。

ii) $\alpha \in \mathcal{P} \land -\alpha \in \mathcal{P}$ とすると、
\begin{equation*}
\left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \land \alpha(n) < 0 \, \} \right| < \omega \land \left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \land \alpha(n) > 0 \, \} \right| < \omega
\end{equation*}
である。これより
\begin{equation*}
\left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \, \} \right| < \omega
\end{equation*}
が成り立つから、$\alpha \in \mathcal{I}$ である。逆は明らか。

iii) $\alpha \in \mathcal{P} \land \beta \in \mathcal{P}$ とすると、ある $M \in \mathbb{N}$ が存在して
\begin{equation*}
\forall n \in \mathbb{N} \, (-M \le \alpha(n) \land -M \le \beta(n))
\end{equation*}
が成り立つ。これより
\begin{equation*}
\forall n \in \mathbb{N} \, (-2M \le \alpha(n) + \beta(n))
\end{equation*}
となるから $\alpha + \beta \in \mathcal{P}$ である。

iv) $\alpha \in \mathcal{P} \land \beta \in \mathcal{P}$ とすると、同様にある $M \in \mathbb{N}$ が存在して
\begin{equation*}
\forall n \in \mathbb{N} \, (-M \le \alpha(n) \land -M \le \beta(n))
\end{equation*}
が成り立つ。このとき、
\begin{equation*}
\{ \, \alpha(\beta(n)) \, \mid \, n \in \mathbb{N} \land -M \le \beta(n) < 0 \, \}
\end{equation*}
は有限集合だから、最小値$N$がとれる。従って、
\begin{equation*}
\forall n \in \mathbb{N} \, (\min \{ -M, N \} \le \alpha(\beta(n)))
\end{equation*}
が成り立ち、従って $\alpha \beta \in \mathcal{P}$ である。□

 この$\mathcal{P}$を用いて、$\mathbb{R}$に順序関係を定義します。

【定義7】$a,b \in \mathbb{R}, a=[\alpha], b=[\beta] \ (\alpha, \beta \in \mathcal{S})$ に対し、次によって関係 $a \le b$ を定める。 \begin{equation*} a \le b \ \Leftrightarrow \ \beta - \alpha \in \mathcal{P} \end{equation*} また、関係 $\ge, <, >$ は $\le$ を元に周知の通り定まるものとする。


【定理8】関係$\le$は正しく定義されており、これによって$\mathbb{R}$は順序環になる。すなわち任意の $a,b,c \in \mathbb{R}$ に対して次が成立する。
 i) $a \le a$
 ii) $a \le b \land b \le a \to a = b$
 iii) $a \le b \land b \le c \to a \le c$
 iv) $a \le b \lor b \le a$
 v) $a \le b \to a + c \le b + c$
 vi) $a \ge 0 \land b \ge 0 \to ab \ge 0$

 この証明は【定理7】を使えば機械的にできますので、省略します。以上で$\mathbb{R}$が順序環であることが示されました。


(4) 順序体であることとアルキメデス性

 この段階で、$\mathbb{R}$が体になることを証明します。少し長くなりますが、スロープの正負の性質や【補題5】を使って、乗法逆元のもとになるスロープを構成します。

【定理9】$\mathbb{R}$は体である。すなわち任意の $a \in \mathbb{R}, a \neq 0$ に対して乗法逆元 $a^{-1}$ が存在する。

(証明)$a > 0$ のときに証明できれば、$a < 0$ のときは $(-a)^{-1}$ が存在して $a(-(-a)^{-1}) = (-a)(-a)^{-1} = 1$ となるから、$a \neq 0$ に対する証明が終わる。よって以下 $a > 0$ とする。
 $a = [\alpha], \alpha \in \mathcal{S}$ とすると、$\lnot (a \le 0)$ より $-\alpha \notin \mathcal{P}$ であり、これより
\begin{equation}
\left| \{ \, \alpha(n) \, \mid \, n \in \mathbb{N} \land \alpha(n) > 0 \, \} \right| \ge \omega \tag{5}
\end{equation}
が従う。これは左辺の集合が上に有界でないことを意味するから、$\mathbb{Z}$ から $\mathbb{Z}$ への関数 $\beta$ として
\begin{equation*}
\forall n \in \mathbb{N} \, ( \beta(n) = \min \{ \, k \in \mathbb{N} \, \mid \, \alpha(k) > n \, \} - 1 )
\end{equation*}
をみたす奇関数が作れて、
\begin{equation}
\forall n \in \mathbb{N} \, ( \alpha(\beta(n)) \le n < \alpha(\beta(n)+1) ) \tag{6}
\end{equation}
が成り立つ。一方$\alpha$がスロープだから、ある $M \in \mathbb{N}$ が存在して
\begin{equation}
\forall m,n \in \mathbb{Z} \, (-M \le \alpha(m+n) - \alpha(m) - \alpha(n) \le M) \tag{7}
\end{equation}
をみたす。これと$(6)$より任意の $n \in \mathbb{N}$ に対して
\begin{equation*}
\alpha(\beta(n)) \le n < \alpha(\beta(n)+1) \le \alpha(\beta(n)) + \alpha(1) + M
\end{equation*}
これより
\begin{equation*}
\forall n \in \mathbb{N} \, (-\alpha(1) - M < \alpha(\beta(n)) - n \le 0)
\end{equation*}
が成り立ち、$\alpha, \beta$ とも奇関数だから、
\begin{equation}
\forall n \in \mathbb{Z} \, (-\alpha(1) - M < \alpha(\beta(n)) - n < \alpha(1) + M) \tag{8}
\end{equation}
が成り立つ。ここで $\beta$ がスロープであることが示されれば、$b = [\beta]$ として実数$b$を定めると、$(8)$より
\begin{equation*}
\alpha \beta - \bar{1} \in \mathcal{I}
\end{equation*}
が成り立つから、$ab = 1$ すなわち$b$は$a$の乗法逆元であることが示されて証明が終わる。そこで以下 $\beta$ がスロープであることを示す。このためには
\begin{equation*}
E_\beta = \{ \, \beta(m+n)-\beta(m)-\beta(n) \, \mid \, m,n \in \mathbb{Z} \, \}
\end{equation*}
で定まる $E_\beta$ が有界であることを示せばよい。
 任意の $m,n \in \mathbb{Z}$ に対して、$(7)$と$(8)$より
\begin{eqnarray*}
\alpha(\beta(m+n) - \beta(m) - \beta(m)) &\le& \alpha(\beta(m+n)) - \alpha(\beta(m) + \beta(n)) + M \\
&\le& \alpha(\beta(m+n)) - \alpha(\beta(m)) - \alpha(\beta(n)) + 2M \\
&<& (m+n) -m -n + 3\alpha(1) + 5M \\
&=& 3\alpha(1) + 5M
\end{eqnarray*}
であり、同様に
\begin{eqnarray*}
\alpha(\beta(m+n) - \beta(m) - \beta(m)) &\ge& \alpha(\beta(m+n)) - \alpha(\beta(m) + \beta(n)) - M \\
&\ge& \alpha(\beta(m+n)) - \alpha(\beta(m)) - \alpha(\beta(n)) - 2M \\
&>& (m+n) - m - n - 3\alpha(1) - 5M \\
&=& - 3\alpha(1) - 5M
\end{eqnarray*}
であるから、$N \ge 3\alpha(1) + 5M$ をみたす $N \in \mathbb{N}_+$ をとると、
\begin{equation}
\forall m,n \in \mathbb{Z} \, (-N \le \alpha(\beta(m+n) - \beta(m) - \beta(m)) \le N) \tag{9}
\end{equation}
が成り立つ。
 ここで $E_\beta$ が上に有界でないと仮定すると、$(5)$より $\alpha(p) > M + N$ をみたす $p \in \mathbb{N}$ が存在するから、これに対して
\begin{equation*}
L = \min \{ \, \alpha(r) \, \mid \, r \in \mathbb{Z}, 0 \le r < p \, \}
\end{equation*}
とおくと、仮定より $qN \ge N - L + M$ となるような十分大きな $q \in \mathbb{Z}, q > 0$ に対して
\begin{equation*}
\beta(m+n)-\beta(m)-\beta(n) = qp + r \quad (0 \le r < p)
\end{equation*}
とかけるような $m,n \in \mathbb{Z}$ が存在する。このとき【補題5】より
\begin{eqnarray*}
\alpha(\beta(m+n)-\beta(m)-\beta(n)) &=& \alpha(qp+r) \\
&\ge& \alpha(qp) + \alpha(r) - M \\
&\ge& \alpha(qp) + L - M \\
&\ge& q\alpha(p) - qM + L - M \\
&>& qN + L - M\\
&\ge& N
\end{eqnarray*}
より$(9)$と矛盾する。
 $E_\beta$ が下に有界でないと仮定すると、$p$を同じものとして、
\begin{equation*}
L = \max \{ \, \alpha(r) \, \mid \, r \in \mathbb{Z}, -p < r \le 0 \, \}
\end{equation*}
とおくと、仮定より $qN \le -N - L - M$ となるような十分小さな $q \in \mathbb{Z}, q < 0$ に対して
\begin{equation*}
\beta(m+n)-\beta(m)-\beta(n) = qp + r \quad (-p < r \le 0)
\end{equation*}
とかけるような $m,n \in \mathbb{Z}$ が存在する。同様に( $q < 0$ に注意して)、
\begin{eqnarray*}
\alpha(\beta(m+n)-\beta(m)-\beta(n)) &=& \alpha(qp+r) \\
&\le& \alpha(qp) + \alpha(r) + M \\
&\le& \alpha(qp) + L + M \\
&\le& q\alpha(p) - qM + L + M \\
&<& qN + L + M\\
&\le& -N
\end{eqnarray*}
より、やはり$(9)$と矛盾する。
 以上より $E_\beta$ は有界集合であり、従って$\beta$はスロープである。以上で証明は完了した。□

 $\mathbb{R}$が順序体であることが示されたので、これは次の手順によって$\mathbb{Q}$と同型な順序体を含むことがわかります。任意の $j \in \mathbb{Z}$ に対して、
\begin{equation}
\bar{j}(n) = jn
\end{equation}
で定まる$\mathbb{Z}$から$\mathbb{Z}$への関数 $\bar{j}$ はスロープであり、整数$j$に同値類 $[\bar{j}]$ を対応させる写像によって$\mathbb{Z}$は$\mathbb{R}$に埋め込まれます。以下$j$と $[\bar{j}]$ を同一視し$\mathbb{Z}$を$\mathbb{R}$の部分順序環とみなします。さらに$\mathbb{R}$における $j \in \mathbb{Z}, j \neq 0$ の乗法逆元を考えることにより、$\mathbb{R}$の部分順序体としての有理数体$\mathbb{Q}$を構成することができます。

 続いて、$\mathbb{R}$がアルキメデス的順序体であることを示します。

【補題10】$a \in \mathbb{R}$ ならば、$j > a$ をみたす $j \in \mathbb{N}_+$ が存在する。
(証明)$a = [\alpha]$ とする。【補題5】より
\begin{equation*}
\forall k \in \mathbb{N}_+ \, ( \left| \alpha(k) - k\alpha(1) \right| < kM )
\end{equation*}
となる $M \in \mathbb{N}_+$ がとれる。$i > \alpha(1) + M$ となる $i \in \mathbb{N}_+$ をとると、任意の $k \in \mathbb{N}_+$ に対し、
\begin{equation*}
\alpha(k) < k(\alpha(1) + M) < ik
\end{equation*}
であるから $\bar{i} - \alpha \in \mathcal{P}$ より $a \le i$ であり、$j = i+1$ とおくと $a < j$ である。□

【定理11】順序体$\mathbb{R}$はアルキメデス的である。すなわち次が成り立つ。
\begin{equation*}
\forall a,b \in \mathbb{R} \, (a > 0 \to \exists j \in \mathbb{N} \, (ja > b))
\end{equation*}
(証明)任意に $a,b \in \mathbb{R} \ (a > 0)$ をとる。【補題10】より $b/a < j $ をみたす $j \in \mathbb{N}$ がとれ、これに対して $ja > b$ が成り立つ。□

 アルキメデス的順序体で次が成立することは一般論です。

【定理12】$\mathbb{Q}$は$\mathbb{R}$において稠密である。すなわち次が成り立つ。
\begin{equation*}
\forall a,b \in \mathbb{R} \, (a < b \to \exists c \in \mathbb{Q} \, (a < c < b))
\end{equation*}
従って、特に$\mathbb{R}$は自己稠密である。
(証明)任意に $a < b$ をみたす $a,b \in \mathbb{R}$ をとる。【定理11】より $1 < j(b - a) $ をみたす $j \in \mathbb{N}_+$ がとれ、これに対して $1/j < b - a$ である。さらに【補題10】より $ja < i$ となる最小の $i \in \mathbb{Z}$ がとれるから、$i - 1 \le ja$ より、
\begin{equation*}
i/j \le a + 1/j < a + (b - a) = b
\end{equation*}
よって $a < i/j < b$ かつ $i/j \in \mathbb{Q}$ となるから、$\mathbb{Q}$は$\mathbb{R}$において稠密である。□

 以上で、$\mathbb{R}$がアルキメデス的順序体であることと、$\mathbb{R}$における$\mathbb{Q}$の稠密性が示されました。$\mathbb{R}$が完備であることの証明にはこれらの事実を使います。


(5) 完備性

 最後にいよいよ$\mathbb{R}$の完備性の証明です。$\mathbb{R}$に埋め込まれた$\mathbb{Z}$を使ってスロープを構成し、それを用いて上限の存在を証明する、という少々チートな方法を使います。

【定理13】順序環$\mathbb{R}$は完備である。すなわち$\mathbb{R}$の空でなく上に有界な部分集合は上限をもつ。
(証明)$A$を空でなく上に有界な$\mathbb{R}$の部分集合とする。【定理11】より$\mathbb{R}$はアルキメデス的だから、$A$はある $M \in \mathbb{Z}$ を上界にもつとしてよい。この$M$に対し、
\begin{equation*}
\forall n \in \mathbb{N} \, \forall a \in A \, (an \le Mn)
\end{equation*}
が成り立つ。そこで、$\mathbb{Z}$から$\mathbb{Z}$への関数$\beta$を
\begin{equation*}
\beta(n) = \min \{ \, k \in \mathbb{Z} \, \mid \, \forall a \in A \, (an \le k) \, \} \quad (n \in \mathbb{N})
\end{equation*}
をみたす奇関数として定める($n=0$ のときは右辺が$0$になるから問題ない)。
 $\beta$がスロープであること、すなわち
\begin{equation}
\left| \{ \, \beta(m+n)-\beta(m)-\beta(n) \, \mid \, m,n \in \mathbb{N} \, \} \right| < \omega \tag{10}
\end{equation}
を示す。任意に $m,n \in \mathbb{N}$ をとる。$\beta$の定義より、
\begin{equation*}
\beta(m) - 1 < a_1m, \quad \beta(n) - 1 < a_2n, \quad \beta(m+n) - 1 < a_3(m+n)
\end{equation*}
をみたす $a_1, a_2, a_3 \in A$ がある。$a = \max \{ \, a_1, a_2, a_3 \, \}$ とすると、
\begin{equation*}
am \le \beta(m) < am + 1, \quad an \le \beta(n) < an + 1, \quad a(m+n) \le \beta(m+n) < a(m+n) + 1
\end{equation*}
であるから、
\begin{equation*}
-2 < \beta(m+n)-\beta(m)-\beta(n) < 1
\end{equation*}
となり、従って$(10)$が成り立つから$\beta$はスロープである。$b = [\beta]$ として実数$b$を定め、これが$A$の上限であることを示す。
 ある $a \in A$ が $b < a$ をみたすと仮定して矛盾を導く。【定理12】より$\mathbb{Q}$が$\mathbb{R}$において稠密だから、
\begin{equation*}
b < i/j < a \quad (i \in \mathbb{Z}, j \in \mathbb{N}_+)
\end{equation*}
をみたす $i,j$ がとれる。$bj < i$ すなわち $\lnot (bj \ge i)$ だから $\beta \bar{j} - \bar{i} \notin \mathcal{P}$ であり、よって
\begin{equation*}
\beta(\bar{j}(n)) - \bar{i}(n) < 0
\end{equation*}
となる $n \in \mathbb{N}_+$ が存在し、この$n$に対して $\beta(jn) < in$ である。一方で $i < aj$ より
\begin{equation*}
\beta(jn) < in < ajn
\end{equation*}
が成り立ち、$jn \in \mathbb{N}_+$ だから、これは$\beta$の作り方に矛盾する。従って $b$ は $A$の上界である。
 次に、$A$の上界$c$で $c < b$ となるものが存在すると仮定して矛盾を導く。先と同様に、
\begin{equation*}
c < i/j < b \quad (i \in \mathbb{Z}, j \in \mathbb{N}_+)
\end{equation*}
をみたす $i,j$ がとれる。$i < bj$ だから先と同様の議論によって $in < \beta(jn)$ となる $n \in \mathbb{N}_+$ が存在する。この$n$に対して、任意に $a \in A$ をとると $a \le c < i/j$ より $aj < i$ であるから、
\begin{equation*}
ajn < in < \beta(jn)
\end{equation*}
となり、$in \in \mathbb{Z}$ だからやはり$\beta$の作り方に矛盾する。従ってこのような$c$は存在せず、$b$は$A$の上限である。
 以上で$\mathbb{R}$が完備であることが示された。□

 $A$の上限 $b = [\beta]$ の作り方が、わりと自然な発想になっていることがわかると思います。以上で$\mathbb{R}$は完備性をもつ順序体であること、すなわち実数体の性質を全て持つことの証明がこれで完了しました。

 アカンポの実数論は、$\mathbb{Z}$から$\mathbb{Q}$を介さずに$\mathbb{R}$が構成でき、演算や順序の定義が自然であるという特徴をもつ、画期的な構成法です。本記事ではそれを自分なりにアレンジし、構成法も以前記事にした「形式的冪級数を用いた実数体の構成法について」とよく似た流れになって、理解しやすくなったと思います。

(追記)2021/2/14
乗法逆元の存在の証明に関する部分を大幅に修正しました。

nice!(0)  コメント(0) 
共通テーマ:学問

アルキメデス的な順序環は可換であることについて [数学]

 前回の記事で、「順序完備かつ自己稠密な順序環は体である」ことを証明しました。今回も順序環についてのちょっとした定理を証明します。

【定理】順序環は、アルキメデス的ならば可換である。

 ここでちょっとおことわりを。前回は順序環に(乗法演算の)可換性を仮定しましたが、今回はそれは仮定しません(それを証明するのですから当然ですね)。ただし乗法単位元1は有するとします。
 実際にはこの定理が証明できれば、前回の定理においても順序完備性からアルキメデス性が得られるわけですから、可換性を仮定する必要はないことになります。

 以下、$R$ を順序環とします。$R$ は乗法単位元を有するので、整数環 $\mathbb{Z}$ を部分順序環として包含すると考えられます。このとき、次の事実は数学的帰納法などを用いて簡単に証明できます。
\[ \forall n \in \mathbb{Z} \, \forall a \in R \, (na = an) \]
これを念頭において定理を証明します。

(定理の証明)$R$ が非可換と仮定し、ある $a,b \in R$ に対して $ab \neq ba$ とする。$a,b$ はどちらも$0$ではなく、また $ab \neq ba$ ならば $(-a)b \neq b(-a)$ かつ $a(-b) \neq (-b)a$ だから、$a > 0$ かつ $b > 0$ としてよい。さらに $ab < ba$ として一般性を失わない。以下これらを仮定する。
 $ba - ab > 0$ で、$R$ はアルキメデス的だから、
\[ b < m(ba - ab) \]
をみたす $m \in \mathbb{N}$ が存在する。この $m$ に対して再び $R$ のアルキメデス性より、
\[ nb < mba \le (n+1)b \]
をみたす $n \in \mathbb{N}$ が存在する。これらに対して、まず
\[ bn = nb < mba = b(ma) \]
かつ $b > 0$ より $n < ma$ が成り立つ。一方、
\[ mba + mab \le (n+1)b +mab = nb + b + mab < nb + m(ba - ab) + mab = nb + mba \]
より
\[ (ma)b < nb \]
であるから、$b > 0$ より $ma < n$ が成り立つ。これは矛盾である。□

 割とあっさり証明できてしまいました。

 そうすると、アルキメデス的でない非可換な順序環の存在を例示したくなりますが、これが今のところなかなか思いつきません。非可換環の上に演算と整合する順序を載せるのは結構難しそうです。

(2021/2/21追記)
 非可換な順序環の例がありました。


nice!(0)  コメント(0) 
共通テーマ:学問
前の10件 | -