形式的ローラン級数体上で証明するz変換の公式（勉強ノート） [数学]
前回の記事で、形式的ローラン級数体 $\mathbb{C}((X))$ 上で $X^{-1} = z$ とおいて「後シフト演算子」として扱い、線形漸化式の一般項を求めるのに使ったりしました。ここで$z$という文字を使ったことを見て、制御工学などをかじった人はニヤニヤしていると思います。そう、これは離散システムの解析で用いる「z変換」と同じ形をしているのです。
なぜそうなるかというと、数列$f$の母関数表現
\[ f \ = \ \sum_{k=0}^\infty f(k)X^k \]
において不定元$X$を $z^{-1}$ で置き換えると、
\[ f \ = \ \sum_{k=0}^\infty f(k)z^{-k} \]
となり、これはそのまま数列$f$のz変換の定義式になっているからです。つまり、数列を母関数と同一視することによって、自然にz変換が得られることになります。
もちろん本来のz変換とは違いもあります。本来のz変換では$z$は$\mathbb{C}$上を動く複素変数として考えますが、ここでは$z$は演算子、すなわち $\mathbb{C}((X))$ 上の定数です。勝手に数値を代入することはできません。その代わり、本来のz変換で考慮しないといけない無限級数の「収束性」については、ここではいっさい考慮する必要はありません。そればかりか、考える対象を$\mathbb{C}$に限る必要もなく、$K$が体でありさえすれば形式的ローラン級数体 $K((X))$ を考えることができるので、この方法は任意の体を値にとる数列の解析に共通して使える手法になります。まああまりに一般化しすぎるとややこしくなるので、ここでは対象は $\mathbb{C}$ と決めることにします。
そういうわけで、ここからは本来のz変換で成り立つ諸々の公式について、形式的ローラン級数体 $\mathbb{C}((X))$ 上でも同じ形の公式が成り立つことを、順に確かめていくことにします。
まずは前回の記事で紹介した2つの公式を再掲します。
証明も前回の記事に書かれています。フィボナッチ数列の一般項を求めるためには、この2つの公式があれば十分でした。
次に、形式微分という概念を導入します。$\mathbb{C}((X))$ の元$h$が
\begin{equation*}
h = \sum_{k=N}^\infty h(k)X^k \quad (N \in \mathbb{Z})
\end{equation*}
と表されているとき、その不定元$X$による形式微分を
\begin{equation*}
\frac{d}{dX}h = \sum_{k=N}^\infty kh(k)X^{k-1}
\end{equation*}
で定義します。これは項別に整関数の普通の微分を取った形なので、疑問はないと思います。これに対しても普通の微分と同様な次の公式が成立します。
（証明）
i) $h_1,h_2$ の最低次数をそれぞれ $N_1, N_2 \in \mathbb{Z}$ とすると、形式的ローラン級数の積の定義より、
\begin{equation*}
h_1h_2 = \sum_{k=N_1+N_2}^\infty \left( \sum_{i=0}^{k-(N_1+N_2)} h_1(k-i-N_2)h_2(i+N_2) \right) X^k
\end{equation*}
これより、
\begin{equation*}
\frac{d}{dX}(h_1h_2) = \sum_{k=N_1+N_2}^\infty k\left( \sum_{i=0}^{k-(N_1+N_2)} h_1(k-i-N_2)h_2(i+N_2) \right) X^{k-1}
\end{equation*}
一方で、
\begin{eqnarray*}
&& \left( \frac{d}{dX}h_1 \right) h_2 + h_1 \left( \frac{d}{dX}h_2 \right) \\
&=& \left( \sum_{k=N_1}^\infty kh_1(k)X^{k-1} \right) \left( \sum_{k=N_2}^\infty h_2(k)X^k \right) + \left( \sum_{k=N_1}^\infty h_1(k)X^k \right) \left( \sum_{k=N_2}^\infty kh_2(k)X^{k-1} \right) \\
&=& X^{-1}\left( \sum_{k=N_1}^\infty kh_1(k)X^k \right) \left( \sum_{k=N_2}^\infty h_2(k)X^k \right) + X^{-1}\left( \sum_{k=N_1}^\infty h_1(k)X^k \right) \left( \sum_{k=N_2}^\infty kh_2(k)X^k \right) \\
&=& X^{-1}\sum_{k=N_1+N_2}^\infty \left( \sum_{i=0}^{k-(N_1+N_2)} (k-i-N_2)h_1(k-i-N_2)h_2(i+N_2) \right) X^k \\
&& + X^{-1}\sum_{k=N_1+N_2}^\infty \left( \sum_{i=0}^{k-(N_1+N_2)} h_1(k-i-N_2)(i+N_2)h_2(i+N_2) \right) X^k \\
&=& \sum_{k=N_1+N_2}^\infty k\left( \sum_{i=0}^{k-(N_1+N_2)} h_1(k-i-N_2)h_2(i+N_2) \right) X^{k-1}
\end{eqnarray*}
これらより
\begin{equation*}
\frac{d}{dX}(h_1h_2) = \left( \frac{d}{dX}h_1 \right) h_2 + h_1 \left( \frac{d}{dX}h_2 \right)
\end{equation*}
ii) $n \ge 0$ のときは積の公式 i)より数学的帰納法によって導かれる。$n < 0$ のときは、i)より
\begin{equation*}
\left( \frac{d}{dX}h^n \right) h^{-n} + h^n \left( \frac{d}{dX}h^{-n} \right) = \frac{d}{dX}(h^nh^{-n}) = \frac{d}{dX}1 = 0
\end{equation*}
これより、
\begin{equation*}
\frac{d}{dX}h^n = -\left( \frac{d}{dX}h^{-n} \right) \frac{h^n}{h^{-n}} = -(-n)\left( \frac{d}{dX}h \right) h^{-n-1} \cdot \frac{h^n}{h^{-n}} = n \left( \frac{d}{dX}h \right) h^{n-1}
\end{equation*}
となるから成立する。□
$X$による形式微分と同様に、$z$による形式微分を考えることもできます。これは$X$を $z^{-1}$ で置き換えた表現
\begin{equation*}
h = \sum_{k=N}^\infty h(k)z^{-k} \quad (N \in \mathbb{Z})
\end{equation*}
に対して$z$で項別微分した、
\begin{equation*}
\frac{d}{dz}h = \sum_{k=N}^\infty (-k)h(k)z^{-k-1}
\end{equation*}
によって定義されます。【公式3】と同じ形の積や冪乗の公式も成立し、証明も同じです。
さらに、本来のz変換で知られた次の公式も成立します。
（証明）
左辺の$X$を $z^{-1}$ で置き換えると、
\begin{equation*}
\sum_{k=0}^\infty kf(k) X^k = \sum_{k=0}^\infty kf(k) z^{-k} = -z \left( \sum_{k=0}^\infty (-k)f(k) z^{-k-1} \right) = -z \frac{d}{dz}f
\end{equation*}
□
形式微分を用いると、次の公式が導かれます。
（証明）証明すべき公式の右辺は、
\begin{equation*}
\frac{z}{(z-r)^n} = \frac{z^{1-n}}{(1-rz^{-1})^n} = \frac{X^{n-1}}{(1-rX)^n}
\end{equation*}
と変形できるから、
\begin{equation}
\frac{1}{(1-rX)^n} = \sum_{k=0}^\infty {}_k \mathrm{C}_{n-1} r^{k-n+1}X^{k-n+1} \tag{1}
\end{equation}
を証明すればよいことがわかる。$n=1$ のときは【公式2】で$z$を $X^{-1}$ に置き換えることより成立。$n$に対して$(1)$が成立するならば、両辺を$X$で形式微分すると、【公式3】ii) を用いて、
\begin{equation*}
\frac{rn}{(1-rX)^{n+1}} = \sum_{k=0}^\infty (k-n+1){}_k \mathrm{C}_{n-1} r^{k-n+1}X^{k-n} = \sum_{k=0}^\infty \frac{k(k-1) \cdots (k-n+2)(k-n+1)}{(n-1)!} r^{k-n+1}X^{k-n}
\end{equation*}
これより、
\begin{equation*}
\frac{1}{(1-rX)^{n+1}} = \sum_{k=0}^\infty \frac{k(k-1) \cdots (k-n+1)}{n!} r^{k-n}X^{k-n} = \sum_{k=0}^\infty {}_k \mathrm{C}_{(n+1)-1} r^{k-(n+1)+1}X^{k-(n+1)+1}
\end{equation*}
となるから $n+1$ に対しても$(1)$が成立する。従って数学的帰納法よりすべての $n \ge 1$ に対して$(1)$が成立する。□
この公式によって、前回の記事で紹介した定数係数線形漸化式の一般項を求める方法において、重根が生じた場合でも「逆z変換」ができるので、原理的には一般項が求められることになります。特に$n$が小さい場合に【公式5】を具体的にかくと、
\begin{equation*}
\sum_{k=0}^\infty k r^{k-1}X^k = \frac{z}{(z-r)^2}
\end{equation*}
\begin{equation*}
\sum_{k=0}^\infty \frac{k(k-1)}{2} r^{k-2}X^k = \frac{z}{(z-r)^3}
\end{equation*}
などとなります。
あと、z変換の線型性や、数列の畳み込みがz変換すると積になるという性質を表す公式は、そもそもの数列を母関数（形式的冪級数）と同一視したことから当然に成り立つので、ここでの改めての証明は省略しました。
以前の記事で紹介した「ミクシンスキーの演算子法」では、微分演算子$s$によって関数を表現するとラプラス変換と同じ形になりました。ここでは形式的ローラン級数体上の後シフト演算子$z$で数列を表現するとz変換と同じ形になりました。数学のアナロジーは本当に面白いです。
なぜそうなるかというと、数列$f$の母関数表現
\[ f \ = \ \sum_{k=0}^\infty f(k)X^k \]
において不定元$X$を $z^{-1}$ で置き換えると、
\[ f \ = \ \sum_{k=0}^\infty f(k)z^{-k} \]
となり、これはそのまま数列$f$のz変換の定義式になっているからです。つまり、数列を母関数と同一視することによって、自然にz変換が得られることになります。
もちろん本来のz変換とは違いもあります。本来のz変換では$z$は$\mathbb{C}$上を動く複素変数として考えますが、ここでは$z$は演算子、すなわち $\mathbb{C}((X))$ 上の定数です。勝手に数値を代入することはできません。その代わり、本来のz変換で考慮しないといけない無限級数の「収束性」については、ここではいっさい考慮する必要はありません。そればかりか、考える対象を$\mathbb{C}$に限る必要もなく、$K$が体でありさえすれば形式的ローラン級数体 $K((X))$ を考えることができるので、この方法は任意の体を値にとる数列の解析に共通して使える手法になります。まああまりに一般化しすぎるとややこしくなるので、ここでは対象は $\mathbb{C}$ と決めることにします。
そういうわけで、ここからは本来のz変換で成り立つ諸々の公式について、形式的ローラン級数体 $\mathbb{C}((X))$ 上でも同じ形の公式が成り立つことを、順に確かめていくことにします。
まずは前回の記事で紹介した2つの公式を再掲します。
【公式1】（シフト）
$f \in \mathbb{C}[[X]], \ n \ge 1$ とすると、
\begin{equation*}
\sum_{k=0}^\infty f(k+n) X^k = z^nf - f(0)z^n - f(1)z^{n-1} - \cdots - f(n-1)z
\end{equation*}
【公式2】（等比数列）
$r \in \mathbb{C}$ とすると、
\begin{equation*}
\sum_{k=0}^\infty r^kX^k = \frac{z}{z-r}
\end{equation*}
証明も前回の記事に書かれています。フィボナッチ数列の一般項を求めるためには、この2つの公式があれば十分でした。
次に、形式微分という概念を導入します。$\mathbb{C}((X))$ の元$h$が
\begin{equation*}
h = \sum_{k=N}^\infty h(k)X^k \quad (N \in \mathbb{Z})
\end{equation*}
と表されているとき、その不定元$X$による形式微分を
\begin{equation*}
\frac{d}{dX}h = \sum_{k=N}^\infty kh(k)X^{k-1}
\end{equation*}
で定義します。これは項別に整関数の普通の微分を取った形なので、疑問はないと思います。これに対しても普通の微分と同様な次の公式が成立します。
【公式3】（形式微分の積と冪乗）
i) $h_1, h_2 \in \mathbb{C}((X))$とすると、 \begin{equation*} \frac{d}{dX}(h_1h_2) = \left( \frac{d}{dX}h_1 \right) h_2 + h_1 \left( \frac{d}{dX}h_2 \right) \end{equation*} ii) $h \in \mathbb{C}((X)), \ n \in \mathbb{Z}$とすると、 \begin{equation*} \frac{d}{dX}h^n = n(\frac{d}{dX}h)h^{n-1} \end{equation*}
i) $h_1, h_2 \in \mathbb{C}((X))$とすると、 \begin{equation*} \frac{d}{dX}(h_1h_2) = \left( \frac{d}{dX}h_1 \right) h_2 + h_1 \left( \frac{d}{dX}h_2 \right) \end{equation*} ii) $h \in \mathbb{C}((X)), \ n \in \mathbb{Z}$とすると、 \begin{equation*} \frac{d}{dX}h^n = n(\frac{d}{dX}h)h^{n-1} \end{equation*}
（証明）
i) $h_1,h_2$ の最低次数をそれぞれ $N_1, N_2 \in \mathbb{Z}$ とすると、形式的ローラン級数の積の定義より、
\begin{equation*}
h_1h_2 = \sum_{k=N_1+N_2}^\infty \left( \sum_{i=0}^{k-(N_1+N_2)} h_1(k-i-N_2)h_2(i+N_2) \right) X^k
\end{equation*}
これより、
\begin{equation*}
\frac{d}{dX}(h_1h_2) = \sum_{k=N_1+N_2}^\infty k\left( \sum_{i=0}^{k-(N_1+N_2)} h_1(k-i-N_2)h_2(i+N_2) \right) X^{k-1}
\end{equation*}
一方で、
\begin{eqnarray*}
&& \left( \frac{d}{dX}h_1 \right) h_2 + h_1 \left( \frac{d}{dX}h_2 \right) \\
&=& \left( \sum_{k=N_1}^\infty kh_1(k)X^{k-1} \right) \left( \sum_{k=N_2}^\infty h_2(k)X^k \right) + \left( \sum_{k=N_1}^\infty h_1(k)X^k \right) \left( \sum_{k=N_2}^\infty kh_2(k)X^{k-1} \right) \\
&=& X^{-1}\left( \sum_{k=N_1}^\infty kh_1(k)X^k \right) \left( \sum_{k=N_2}^\infty h_2(k)X^k \right) + X^{-1}\left( \sum_{k=N_1}^\infty h_1(k)X^k \right) \left( \sum_{k=N_2}^\infty kh_2(k)X^k \right) \\
&=& X^{-1}\sum_{k=N_1+N_2}^\infty \left( \sum_{i=0}^{k-(N_1+N_2)} (k-i-N_2)h_1(k-i-N_2)h_2(i+N_2) \right) X^k \\
&& + X^{-1}\sum_{k=N_1+N_2}^\infty \left( \sum_{i=0}^{k-(N_1+N_2)} h_1(k-i-N_2)(i+N_2)h_2(i+N_2) \right) X^k \\
&=& \sum_{k=N_1+N_2}^\infty k\left( \sum_{i=0}^{k-(N_1+N_2)} h_1(k-i-N_2)h_2(i+N_2) \right) X^{k-1}
\end{eqnarray*}
これらより
\begin{equation*}
\frac{d}{dX}(h_1h_2) = \left( \frac{d}{dX}h_1 \right) h_2 + h_1 \left( \frac{d}{dX}h_2 \right)
\end{equation*}
ii) $n \ge 0$ のときは積の公式 i)より数学的帰納法によって導かれる。$n < 0$ のときは、i)より
\begin{equation*}
\left( \frac{d}{dX}h^n \right) h^{-n} + h^n \left( \frac{d}{dX}h^{-n} \right) = \frac{d}{dX}(h^nh^{-n}) = \frac{d}{dX}1 = 0
\end{equation*}
これより、
\begin{equation*}
\frac{d}{dX}h^n = -\left( \frac{d}{dX}h^{-n} \right) \frac{h^n}{h^{-n}} = -(-n)\left( \frac{d}{dX}h \right) h^{-n-1} \cdot \frac{h^n}{h^{-n}} = n \left( \frac{d}{dX}h \right) h^{n-1}
\end{equation*}
となるから成立する。□
$X$による形式微分と同様に、$z$による形式微分を考えることもできます。これは$X$を $z^{-1}$ で置き換えた表現
\begin{equation*}
h = \sum_{k=N}^\infty h(k)z^{-k} \quad (N \in \mathbb{Z})
\end{equation*}
に対して$z$で項別微分した、
\begin{equation*}
\frac{d}{dz}h = \sum_{k=N}^\infty (-k)h(k)z^{-k-1}
\end{equation*}
によって定義されます。【公式3】と同じ形の積や冪乗の公式も成立し、証明も同じです。
さらに、本来のz変換で知られた次の公式も成立します。
【公式4】（微分）
$f \in \mathbb{C}[[X]]$ とすると、
\begin{equation*}
\sum_{k=0}^\infty kf(k) X^k = -z \frac{d}{dz}f
\end{equation*}
（証明）
左辺の$X$を $z^{-1}$ で置き換えると、
\begin{equation*}
\sum_{k=0}^\infty kf(k) X^k = \sum_{k=0}^\infty kf(k) z^{-k} = -z \left( \sum_{k=0}^\infty (-k)f(k) z^{-k-1} \right) = -z \frac{d}{dz}f
\end{equation*}
□
形式微分を用いると、次の公式が導かれます。
【公式5】（多重極）
$r \in \mathbb{C}, \ n \ge 1$ とすると、
\begin{equation*}
\sum_{k=0}^\infty {}_k \mathrm{C}_{n-1} r^{k-n+1}X^k = \frac{z}{(z-r)^n}
\end{equation*}
（証明）証明すべき公式の右辺は、
\begin{equation*}
\frac{z}{(z-r)^n} = \frac{z^{1-n}}{(1-rz^{-1})^n} = \frac{X^{n-1}}{(1-rX)^n}
\end{equation*}
と変形できるから、
\begin{equation}
\frac{1}{(1-rX)^n} = \sum_{k=0}^\infty {}_k \mathrm{C}_{n-1} r^{k-n+1}X^{k-n+1} \tag{1}
\end{equation}
を証明すればよいことがわかる。$n=1$ のときは【公式2】で$z$を $X^{-1}$ に置き換えることより成立。$n$に対して$(1)$が成立するならば、両辺を$X$で形式微分すると、【公式3】ii) を用いて、
\begin{equation*}
\frac{rn}{(1-rX)^{n+1}} = \sum_{k=0}^\infty (k-n+1){}_k \mathrm{C}_{n-1} r^{k-n+1}X^{k-n} = \sum_{k=0}^\infty \frac{k(k-1) \cdots (k-n+2)(k-n+1)}{(n-1)!} r^{k-n+1}X^{k-n}
\end{equation*}
これより、
\begin{equation*}
\frac{1}{(1-rX)^{n+1}} = \sum_{k=0}^\infty \frac{k(k-1) \cdots (k-n+1)}{n!} r^{k-n}X^{k-n} = \sum_{k=0}^\infty {}_k \mathrm{C}_{(n+1)-1} r^{k-(n+1)+1}X^{k-(n+1)+1}
\end{equation*}
となるから $n+1$ に対しても$(1)$が成立する。従って数学的帰納法よりすべての $n \ge 1$ に対して$(1)$が成立する。□
この公式によって、前回の記事で紹介した定数係数線形漸化式の一般項を求める方法において、重根が生じた場合でも「逆z変換」ができるので、原理的には一般項が求められることになります。特に$n$が小さい場合に【公式5】を具体的にかくと、
\begin{equation*}
\sum_{k=0}^\infty k r^{k-1}X^k = \frac{z}{(z-r)^2}
\end{equation*}
\begin{equation*}
\sum_{k=0}^\infty \frac{k(k-1)}{2} r^{k-2}X^k = \frac{z}{(z-r)^3}
\end{equation*}
などとなります。
あと、z変換の線型性や、数列の畳み込みがz変換すると積になるという性質を表す公式は、そもそもの数列を母関数（形式的冪級数）と同一視したことから当然に成り立つので、ここでの改めての証明は省略しました。
以前の記事で紹介した「ミクシンスキーの演算子法」では、微分演算子$s$によって関数を表現するとラプラス変換と同じ形になりました。ここでは形式的ローラン級数体上の後シフト演算子$z$で数列を表現するとz変換と同じ形になりました。数学のアナロジーは本当に面白いです。
形式的ローラン級数体を使った線形漸化式の解法について（勉強ノート） [数学]
以前この記事で「ミクシンスキーの演算子法」を紹介し、線形微分方程式の解法に応用できることを示しました。
ならば、そのアナロジーで、数列の線形漸化式の一般項を求めるのにも使えるはずだ、と考えてみました。
すると、それは何のことはない、単なる「形式的冪級数環の商体」すなわち形式的ローラン級数体になってしまいました。
それを応用した線形漸化式の解法もよく知られているようですが、僕的にはやはり面白かったので、改めて本記事で紹介します。
複素数を値とする数列の全体を $\mathcal{S}$ とします。$\mathcal{S}$ における加法演算 $+$ を単なる項別の和で、乗法演算 $\ast$ を畳み込みで定義します。すなわち、$f, g \in \mathcal{S}$ に対して、
\begin{eqnarray*}
(f+g)(k) &=& f(k) + g(k) \\
(f \ast g)(k) &=& \sum_{i=0}^k f(k-i)g(i)
\end{eqnarray*}
で定義します。これはミクシンスキーの演算子法に倣ったもので、ここから $\mathcal{S}$ が零因子を持たない環であることを示していこうと考えました。
ところが、数列をその「母関数」と言われる形式的冪級数に対応してしまえば、そんな考察はとっくに終わっていることに気がつきました。それは次のことになります。
$f \in \mathcal{S}$ である数列 $f$ に対して、次の（$1$変数の）形式的冪級数を対応させます（形式的冪級数とは、収束、発散など解析的なことは一切考えない冪級数のことです。なお本記事では不定元を $X$ で表します）。
\[ f \quad \longmapsto \quad \sum_{k=0}^\infty f(k)X^k \]
すると、$\mathcal{S}$ の加法と乗法は、次のように形式的冪級数における加法と乗法にキッチリ対応します。
\begin{eqnarray*}
f+g \quad &\longmapsto& \quad \sum_{k=0}^\infty f(k)X^k + \sum_{k=0}^\infty g(k)X^k \\
f \ast g \quad &\longmapsto& \quad \left( \sum_{k=0}^\infty f(k)X^k \right) \left( \sum_{k=0}^\infty g(k)X^k \right)
\end{eqnarray*}
そこで、これ以降 $\mathcal{S}$ を形式的冪級数の全体 $\mathbb{C}[[X]]$ と同一視してしまうことにします。つまり数列をその母関数と同一視し、$\mathbb{C}[[X]]$ の要素として考えます。従ってここからは、
\[ f \ = \ \sum_{k=0}^\infty f(k)X^k \]
として、形式的冪級数 $f$ の $X^k$ の係数を $f(k)$ と表し、積の記号も省略して $fg$ と書きます。
$\mathbb{C}[[X]]$ はその加法演算と乗法演算に対して可換環になります。加法単位元は係数が全て $0$ の級数、乗法単位元は定数項だけが $1$ で他の係数は全て $0$ の級数です。従ってこれは「形式的冪級数環」と呼ばれます。そして $\mathbb{C}[[X]]$ が零因子を持たない、すなわち整域であることもわかっており、簡単に証明できます。定数項が $0$ であれば乗法逆元を持たないことも簡単にわかるので、$\mathbb{C}[[X]]$ は体ではありません。
$\mathbb{C}[[X]]$ の中では、数列に作用して様々な結果を導く「演算子」がいくつか存在します（以下の演算子の名前は私が適当に付けたものです）。
(1) 部分和演算子 $\displaystyle \sigma = \sum_{k=0}^\infty X^k$
これは $\displaystyle \sigma f = \sum_{k=0}^\infty \left( \sum_{i=0}^k f(i) \right) X^k$ と作用します。つまり各係数が元の係数の部分和になります。
(2) 差分演算子 $\Delta = 1 - X$
これは $\displaystyle \Delta f = f(0) + \sum_{k=1}^\infty (f(k) - f(k-1)) X^k$ と作用します。つまり定数項は元の係数と同じで、$1$次以上の各係数が元の係数の差分になります。$\sigma \Delta = 1$ すなわち $\sigma$ と $\Delta$ は互いに逆元であることも簡単に示されます。
(3) 前シフト演算子 $1 - \Delta = X$
これは $\displaystyle (1 - \Delta) f = Xf = \sum_{k=1}^\infty f(k-1) X^k$ と作用します。つまり定数項が $0$ で、$1$次以上の各係数がもとの$1$つ前の係数となります。
これを $n$ 回繰り返し作用させる演算子 $X^n$ は、$n-1$次以下の係数が $0$ で、$n$次以上の各係数が元の$n$個前の係数となります。
$X^n \ (n \ge 1)$ は $\mathbb{C}[[X]]$ において逆元を持ちませんので、$n$個あとの係数を導く演算子は $\mathbb{C}[[X]]$ の中にはありません。
さて、$\mathbb{C}[[X]]$ は零因子を持たない環なので、その商体（分数体）を構成することができます。これは（複素係数の）「形式的ローラン級数体」として知られており、$\mathbb{C}((X))$ と書きます。$\mathbb{C}((X))$ の要素 $h$ は $f,g \in \mathbb{C}[[X]], \ g \neq 0$ によって、
\[ h \ = \ \frac{f}{g} \]
と表されますが、これは
\[ h \ = \ \sum_{k=N}^\infty h(k)X^k \quad (N \in \mathbb{Z}) \]
と展開することができて、不定元 $X$ の負の冪の項が有限個だけ許されるような級数になります。
考える対象を $\mathbb{C}((X))$ まで拡張すると、これは体なので四則演算が自由にできて、$X$ の有理式なども考えることができます。従って次の演算子が存在します。
(4) 後シフト演算子 $z = X^{-1}$
これは $f \in \mathbb{C}[[X]]$ に対して $\displaystyle zf = \sum_{k=-1}^\infty f(k+1) X^k$ と作用します。つまり$-1$次の係数が $f(0)$ で、$0$次以上の各係数がもとの$1$つ後の係数となります。$z^n = X^{-n} \ (n \ge 1)$ についてはこの繰り返しです。
後シフト演算子 $z$ を使うと、
\[ \sum_{k=0}^\infty f(k+1) X^k = \sum_{k=-1}^\infty f(k+1) X^k - f(0)X^{-1} = zf - f(0)z \]
が成り立ち、これを繰り返すと一般に、
\[ \sum_{k=0}^\infty f(k+n) X^k = z^nf - f(0)z^n - f(1)z^{n-1} - \cdots - f(n-1)z \quad (n \ge 1) \tag{1} \]
が成り立ちます。この関係は後で漸化式の一般項を求めるときに使います。
ここで、初項 $1$ 公比 $r$ の等比数列を母関数にしたもの
\[ g_r = \sum_{k=0}^\infty r^kX^k \]
を考えます。これは前シフト演算子 $X$ を作用させると
\[ Xg_r = \sum_{k=1}^\infty r^{k-1}X^k \]
となるので、
\[ g_r = 1 + rXg_r \]
が成り立ちます。従って $\mathbb{C}((X))$ 上では四則演算が自由にできますから、
\[ g_r = \frac{1}{1-rX} = \frac{z}{z-r} \]
すなわち、
\[ \sum_{k=0}^\infty r^kX^k = \frac{z}{z-r} \quad ( z = X^{-1} ) \tag{2} \]
と表されます。これは $\mathbb{C}((X))$ における等比数列の一つの表現です。これを覚えておきましょう。
いよいよ、形式的ローラン級数体 $\mathbb{C}((X))$ を用いて線形漸化式を解く方法に入ります。例として（典型的すぎますが）フィボナッチ数列の一般項を求めてみましょう。
フィボナッチ数列 $F$ はご存知の通り、定数係数$2$階線形漸化式
\[ F(k+2) = F(k+1) + F(k) \ \ (k \in \mathbb{N}), \quad F(0)=0, \quad F(1)=1 \]
で定義される数列です。これを解くために、漸化式の各項を母関数に置き換えて次のように $\mathbb{C}[[X]]$ 上の関係として書き直します。
\[ \sum_{k=0}^\infty F(k+2)X^k = \sum_{k=0}^\infty F(k+1)X^k + \sum_{k=0}^\infty F(k)X^k \]
これはそのまま $\mathbb{C}((X))$ 上の関係とみなせるので、$(1)$を使って後シフト演算子 $z$ を用いた次の形にすることができます。
\[ z^2F - F(0)z^2 - F(1)z = zF - F(0)z + F \]
$\mathbb{C}((X))$ は体なので、初期値を入れて次のように式変形することができます。
\[ F = \frac{z}{z^2 - z - 1} \]
この分母は、$\displaystyle \alpha = \frac{1+\sqrt{5}}{2}, \ \beta = \frac{1-\sqrt{5}}{2}$ とおくと、
\[ z^2 - z - 1 = (z - \alpha)(z - \beta) \]
と因数分解できるので、
\[ F = \frac{z}{z^2 - z - 1} = \frac{1}{\alpha - \beta} \left( \frac{z}{z - \alpha} - \frac{z}{z - \beta} \right) \]
と部分分数分解できます。
そこでこの右辺を先ほど導出した等比数列の表現$(2)$と比べてみると、ドンピシャに合致していることがわかります。従って、
\begin{eqnarray*}
F &=& \frac{1}{\alpha - \beta} \left( \sum_{k=0}^\infty \alpha^kX^k - \sum_{k=0}^\infty \beta^kX^k \right) \\
&=& \sum_{k=0}^\infty \left( \frac{\alpha^k - \beta^k}{\alpha - \beta} \right) X^k \\
&=& \sum_{k=0}^\infty \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^k - \left( \frac{1-\sqrt{5}}{2} \right)^k \right) X^k
\end{eqnarray*}
これは $\mathbb{C}[[X]]$ 上の関係なので、これよりフィボナッチ数列の一般項は、
\[ F(k) = \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^k - \left( \frac{1-\sqrt{5}}{2} \right)^k \right) \]
と求められました。
一般の定数係数$n$階線形漸化式
\[ f(k+n) + c_1f(k+n-1) + c_2f(k+n-2) + \cdots + c_nf(k) = g(k) \quad (k \in \mathbb{N}) \]
についても、フィボナッチ数列と同様にして、次の $z$ に関する代数方程式
\[ z^n + c_1z^{n-1} + c_2z^{n-2} + \cdots + c_n = 0 \]
の根を求めることに帰着できます（重根が含まれると少しややこしくなります）。$g$ が $0$ でない一般の数列の場合にも、等比数列との間の畳み込み演算を使って、最終的に一般項を求めることができます。
微分方程式と漸化式、ミクシンスキーの演算子法と形式的ローラン級数体、数学のアナロジーを知ると非常に楽しいです。
ならば、そのアナロジーで、数列の線形漸化式の一般項を求めるのにも使えるはずだ、と考えてみました。
すると、それは何のことはない、単なる「形式的冪級数環の商体」すなわち形式的ローラン級数体になってしまいました。
それを応用した線形漸化式の解法もよく知られているようですが、僕的にはやはり面白かったので、改めて本記事で紹介します。
複素数を値とする数列の全体を $\mathcal{S}$ とします。$\mathcal{S}$ における加法演算 $+$ を単なる項別の和で、乗法演算 $\ast$ を畳み込みで定義します。すなわち、$f, g \in \mathcal{S}$ に対して、
\begin{eqnarray*}
(f+g)(k) &=& f(k) + g(k) \\
(f \ast g)(k) &=& \sum_{i=0}^k f(k-i)g(i)
\end{eqnarray*}
で定義します。これはミクシンスキーの演算子法に倣ったもので、ここから $\mathcal{S}$ が零因子を持たない環であることを示していこうと考えました。
ところが、数列をその「母関数」と言われる形式的冪級数に対応してしまえば、そんな考察はとっくに終わっていることに気がつきました。それは次のことになります。
$f \in \mathcal{S}$ である数列 $f$ に対して、次の（$1$変数の）形式的冪級数を対応させます（形式的冪級数とは、収束、発散など解析的なことは一切考えない冪級数のことです。なお本記事では不定元を $X$ で表します）。
\[ f \quad \longmapsto \quad \sum_{k=0}^\infty f(k)X^k \]
すると、$\mathcal{S}$ の加法と乗法は、次のように形式的冪級数における加法と乗法にキッチリ対応します。
\begin{eqnarray*}
f+g \quad &\longmapsto& \quad \sum_{k=0}^\infty f(k)X^k + \sum_{k=0}^\infty g(k)X^k \\
f \ast g \quad &\longmapsto& \quad \left( \sum_{k=0}^\infty f(k)X^k \right) \left( \sum_{k=0}^\infty g(k)X^k \right)
\end{eqnarray*}
そこで、これ以降 $\mathcal{S}$ を形式的冪級数の全体 $\mathbb{C}[[X]]$ と同一視してしまうことにします。つまり数列をその母関数と同一視し、$\mathbb{C}[[X]]$ の要素として考えます。従ってここからは、
\[ f \ = \ \sum_{k=0}^\infty f(k)X^k \]
として、形式的冪級数 $f$ の $X^k$ の係数を $f(k)$ と表し、積の記号も省略して $fg$ と書きます。
$\mathbb{C}[[X]]$ はその加法演算と乗法演算に対して可換環になります。加法単位元は係数が全て $0$ の級数、乗法単位元は定数項だけが $1$ で他の係数は全て $0$ の級数です。従ってこれは「形式的冪級数環」と呼ばれます。そして $\mathbb{C}[[X]]$ が零因子を持たない、すなわち整域であることもわかっており、簡単に証明できます。定数項が $0$ であれば乗法逆元を持たないことも簡単にわかるので、$\mathbb{C}[[X]]$ は体ではありません。
$\mathbb{C}[[X]]$ の中では、数列に作用して様々な結果を導く「演算子」がいくつか存在します（以下の演算子の名前は私が適当に付けたものです）。
(1) 部分和演算子 $\displaystyle \sigma = \sum_{k=0}^\infty X^k$
これは $\displaystyle \sigma f = \sum_{k=0}^\infty \left( \sum_{i=0}^k f(i) \right) X^k$ と作用します。つまり各係数が元の係数の部分和になります。
(2) 差分演算子 $\Delta = 1 - X$
これは $\displaystyle \Delta f = f(0) + \sum_{k=1}^\infty (f(k) - f(k-1)) X^k$ と作用します。つまり定数項は元の係数と同じで、$1$次以上の各係数が元の係数の差分になります。$\sigma \Delta = 1$ すなわち $\sigma$ と $\Delta$ は互いに逆元であることも簡単に示されます。
(3) 前シフト演算子 $1 - \Delta = X$
これは $\displaystyle (1 - \Delta) f = Xf = \sum_{k=1}^\infty f(k-1) X^k$ と作用します。つまり定数項が $0$ で、$1$次以上の各係数がもとの$1$つ前の係数となります。
これを $n$ 回繰り返し作用させる演算子 $X^n$ は、$n-1$次以下の係数が $0$ で、$n$次以上の各係数が元の$n$個前の係数となります。
$X^n \ (n \ge 1)$ は $\mathbb{C}[[X]]$ において逆元を持ちませんので、$n$個あとの係数を導く演算子は $\mathbb{C}[[X]]$ の中にはありません。
さて、$\mathbb{C}[[X]]$ は零因子を持たない環なので、その商体（分数体）を構成することができます。これは（複素係数の）「形式的ローラン級数体」として知られており、$\mathbb{C}((X))$ と書きます。$\mathbb{C}((X))$ の要素 $h$ は $f,g \in \mathbb{C}[[X]], \ g \neq 0$ によって、
\[ h \ = \ \frac{f}{g} \]
と表されますが、これは
\[ h \ = \ \sum_{k=N}^\infty h(k)X^k \quad (N \in \mathbb{Z}) \]
と展開することができて、不定元 $X$ の負の冪の項が有限個だけ許されるような級数になります。
考える対象を $\mathbb{C}((X))$ まで拡張すると、これは体なので四則演算が自由にできて、$X$ の有理式なども考えることができます。従って次の演算子が存在します。
(4) 後シフト演算子 $z = X^{-1}$
これは $f \in \mathbb{C}[[X]]$ に対して $\displaystyle zf = \sum_{k=-1}^\infty f(k+1) X^k$ と作用します。つまり$-1$次の係数が $f(0)$ で、$0$次以上の各係数がもとの$1$つ後の係数となります。$z^n = X^{-n} \ (n \ge 1)$ についてはこの繰り返しです。
後シフト演算子 $z$ を使うと、
\[ \sum_{k=0}^\infty f(k+1) X^k = \sum_{k=-1}^\infty f(k+1) X^k - f(0)X^{-1} = zf - f(0)z \]
が成り立ち、これを繰り返すと一般に、
\[ \sum_{k=0}^\infty f(k+n) X^k = z^nf - f(0)z^n - f(1)z^{n-1} - \cdots - f(n-1)z \quad (n \ge 1) \tag{1} \]
が成り立ちます。この関係は後で漸化式の一般項を求めるときに使います。
ここで、初項 $1$ 公比 $r$ の等比数列を母関数にしたもの
\[ g_r = \sum_{k=0}^\infty r^kX^k \]
を考えます。これは前シフト演算子 $X$ を作用させると
\[ Xg_r = \sum_{k=1}^\infty r^{k-1}X^k \]
となるので、
\[ g_r = 1 + rXg_r \]
が成り立ちます。従って $\mathbb{C}((X))$ 上では四則演算が自由にできますから、
\[ g_r = \frac{1}{1-rX} = \frac{z}{z-r} \]
すなわち、
\[ \sum_{k=0}^\infty r^kX^k = \frac{z}{z-r} \quad ( z = X^{-1} ) \tag{2} \]
と表されます。これは $\mathbb{C}((X))$ における等比数列の一つの表現です。これを覚えておきましょう。
いよいよ、形式的ローラン級数体 $\mathbb{C}((X))$ を用いて線形漸化式を解く方法に入ります。例として（典型的すぎますが）フィボナッチ数列の一般項を求めてみましょう。
フィボナッチ数列 $F$ はご存知の通り、定数係数$2$階線形漸化式
\[ F(k+2) = F(k+1) + F(k) \ \ (k \in \mathbb{N}), \quad F(0)=0, \quad F(1)=1 \]
で定義される数列です。これを解くために、漸化式の各項を母関数に置き換えて次のように $\mathbb{C}[[X]]$ 上の関係として書き直します。
\[ \sum_{k=0}^\infty F(k+2)X^k = \sum_{k=0}^\infty F(k+1)X^k + \sum_{k=0}^\infty F(k)X^k \]
これはそのまま $\mathbb{C}((X))$ 上の関係とみなせるので、$(1)$を使って後シフト演算子 $z$ を用いた次の形にすることができます。
\[ z^2F - F(0)z^2 - F(1)z = zF - F(0)z + F \]
$\mathbb{C}((X))$ は体なので、初期値を入れて次のように式変形することができます。
\[ F = \frac{z}{z^2 - z - 1} \]
この分母は、$\displaystyle \alpha = \frac{1+\sqrt{5}}{2}, \ \beta = \frac{1-\sqrt{5}}{2}$ とおくと、
\[ z^2 - z - 1 = (z - \alpha)(z - \beta) \]
と因数分解できるので、
\[ F = \frac{z}{z^2 - z - 1} = \frac{1}{\alpha - \beta} \left( \frac{z}{z - \alpha} - \frac{z}{z - \beta} \right) \]
と部分分数分解できます。
そこでこの右辺を先ほど導出した等比数列の表現$(2)$と比べてみると、ドンピシャに合致していることがわかります。従って、
\begin{eqnarray*}
F &=& \frac{1}{\alpha - \beta} \left( \sum_{k=0}^\infty \alpha^kX^k - \sum_{k=0}^\infty \beta^kX^k \right) \\
&=& \sum_{k=0}^\infty \left( \frac{\alpha^k - \beta^k}{\alpha - \beta} \right) X^k \\
&=& \sum_{k=0}^\infty \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^k - \left( \frac{1-\sqrt{5}}{2} \right)^k \right) X^k
\end{eqnarray*}
これは $\mathbb{C}[[X]]$ 上の関係なので、これよりフィボナッチ数列の一般項は、
\[ F(k) = \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^k - \left( \frac{1-\sqrt{5}}{2} \right)^k \right) \]
と求められました。
一般の定数係数$n$階線形漸化式
\[ f(k+n) + c_1f(k+n-1) + c_2f(k+n-2) + \cdots + c_nf(k) = g(k) \quad (k \in \mathbb{N}) \]
についても、フィボナッチ数列と同様にして、次の $z$ に関する代数方程式
\[ z^n + c_1z^{n-1} + c_2z^{n-2} + \cdots + c_n = 0 \]
の根を求めることに帰着できます（重根が含まれると少しややこしくなります）。$g$ が $0$ でない一般の数列の場合にも、等比数列との間の畳み込み演算を使って、最終的に一般項を求めることができます。
微分方程式と漸化式、ミクシンスキーの演算子法と形式的ローラン級数体、数学のアナロジーを知ると非常に楽しいです。
ミクシンスキーの演算子法で「むだ時間要素」を定義（勉強ノート） [数学]
以前この記事で、ミクシンスキーの演算子法と、それを使って制御理論で使われる伝達関数法の展開ができることを（自分なりの理解として）紹介しました。
しかし、その記事の中で登場する実際の伝達関数としては、微分演算子$s$の有理式の形で表されるものしかありませんでした。普通は伝達関数はラプラス変換によって定義され、もっと多種多様な$s$の関数が登場しますが、先の記事にはとにもかくにもこれがないと始まらないというべき重要なものが抜けています。
そう、「むだ時間要素」です。
むだ時間要素とは、$L$を正実数とすると、入力 $u(t)$ に対して出力 $y(t) = u(t-L)$ を返すようなシステムの要素のことです。つまり時間$L$だけ出力が遅れて現れるということです。この要素の伝達関数はラプラス変換ならば、
\begin{equation*}
\int_0^\infty y(t)e^{-st}dt = \int_0^\infty u(t-L)e^{-st}dt = \int_{-L}^\infty u(\xi)e^{-s(\xi+L)}d\xi = e^{-sL} \int_0^\infty u(\xi)e^{-s\xi}d\xi
\end{equation*}
より、$e^{-sL}$ であることがすぐにわかります（ $t < 0$ では $u(t) =0$ と考えます）。しかし、ミクシンスキーの演算子法で定義した空間 $\mathcal{M}$ においては、$s$は微分演算子であり、$s$の指数関数なるものの意味が明らかではないので、改めて定義する必要があります。
そこで、$\mathcal{M}$ における $e^{-sL}$ を既知の関数を使って定義することを考えます。
$\mathcal{M}$ においては、例えば
\[ \frac{1}{s-a} = \{ e^{at} \} \]
のように、関数 $f(t)$ の$\mathcal{M}$ における表現が$f$のラプラス変換と同じ形をしていました。そこで、ディラックのデルタ関数$\delta$を使った次の関係に注目します。
\[ \int_0^\infty \delta(t-L)e^{-st}dt = e^{-sL} \]
これは $\delta(t-L)$ のラプラス変換が $e^{-sL}$ ということなので、
\[ e^{-sL} = \{ \delta(t-L) \} \]
と定義すれば良いように思えます。こう定義すると、任意の $[0, \infty)$ における連続関数 $f(t) \in \mathcal{C}$（ただし $t < 0$ のときは $f(t)=0$ とします）に対して、デルタ関数のよく知られた性質を使うことによって、
\begin{equation*}
\int_0^t \delta((t-\xi)-L)f(\xi)d\xi = f(t-L) \tag{1}
\end{equation*}
が導かれますので、これを$\mathcal{M}$に持ち込むと
\begin{equation*}
\{ \delta(t-L) \} \ast \{ f(t) \} = \{ f(t-L) \}
\end{equation*}
となりますから、$e^{-sL} = \{ \delta(t-L) \}$ がむだ時間要素の伝達関数の意味になっています。
しかしこの定義はやはりマズイですね。$\mathcal{C}$ はそもそも $[0,\infty)$ において連続な複素数値関数の集合だったのに、関数でもないデルタ関数をあたかも $\mathcal{C}$ の要素のように使って $\mathcal{M}$ の要素を定義するのはルール違反です。
そこで、$(1)$において左辺をデルタ関数$\delta$の代わりに、ステップ関数$\ell$に置き換えてみましょう。ここで$\ell$は、
\begin{equation*}
\ell(t) =
\left\{
\begin{array}{ll}
1 & (t \ge 0) \\
0 & (t < 0)
\end{array}
\right.
\end{equation*}
によって定まる関数です。これを使うと、
\begin{equation*}
\int_0^t \ell((t-\xi)-L)f(\xi)d\xi =
\left\{
\begin{array}{ll}
\displaystyle \int_0^{t-L} f(\xi)d\xi & (t \ge L) \\
0 & (0 \le t < L)
\end{array}
\right.
\tag{2}
\end{equation*}
この両辺の微分をとると、
\begin{equation*}
\frac{d}{dt} \left( \int_0^t \ell((t-\xi)-L)f(\xi)d\xi \right) =
\left\{
\begin{array}{ll}
f(t-L) & (t > L) \\
0 & (0 \le t < L)
\end{array}
\right\}
= f(t-L) \quad (t \neq L)
\end{equation*}
となります。これを$\mathcal{M}$に持ち込むと、$(2)$の右辺の関数は初期値が$0$なので左辺は微分演算子$s$を掛ければよく、また不連続点 $t=L$ を無視すると、
\begin{equation*}
s \ast \{ \ell(t-L) \} \ast \{ f(t) \} = \{ f(t-L) \}
\end{equation*}
が得られます。従って $s \ast \{ \ell(t-L) \}$ がむだ時間要素に相当することになるので、これを $e^{-sL}$ と定義すれば良いように思えます。
しかしこれでもまだ良くありません。なぜなら、$\mathcal{C}$の要素 は $[0,\infty)$ において連続という条件があるのに、$\ell(t-L)$ は $t=L$ において不連続になっているからです。
そこでステップ関数$\ell$の代わりに、ランプ関数$R$を使います。ここで$R$は、
\begin{equation*}
R(t) =
\left\{
\begin{array}{ll}
t & (t \ge 0) \\
0 & (t < 0)
\end{array}
\right.
\end{equation*}
によって定まる関数で、全実数域で連続になります。従って $\{ R(t-L) \} \in \mathcal{C}$ となるので、$\mathcal{M}$ 上の演算子の定義として堂々と使用することができます。
$(1)$において左辺を$\delta$の代わりに$R$に置き換えてみましょう。$t \ge L$ のときは、
\begin{equation*}
\int_0^t R((t-\xi)-L)f(\xi)d\xi = \int_0^{t-L} (t-L-\xi)f(\xi)d\xi
\end{equation*}
ここで $\displaystyle F(t) = \int_0^tf(\xi)d\xi$ とおくと、部分積分を用いて、
\begin{equation*}
\int_0^{t-L} (t-L-\xi)f(\xi)d\xi = \int_0^{t-L} F(\xi)d\xi
\end{equation*}
従って $t < L$ のときも合わせて、
\begin{equation*}
\int_0^t R((t-\xi)-L)f(\xi)d\xi =
\left\{
\begin{array}{ll}
\displaystyle \int_0^{t-L} F(\xi)d\xi & (t \ge L) \\
0 & (0 \le t < L)
\end{array}
\right.
\end{equation*}
となり、これは $[0,\infty)$ で連続です。
この両辺を微分すると、
\begin{equation*}
\frac{d}{dt} \left( \int_0^t R((t-\xi)-L)f(\xi)d\xi \right) =
\left\{
\begin{array}{ll}
F(t-L) & (t \ge L) \\
0 & (0 \le t < L)
\end{array}
\right.
\end{equation*}
となって、これも $[0,\infty)$ で連続です。さらにもう1回微分すると、
\begin{equation*}
\frac{d^2}{dt^2} \left( \int_0^t R((t-\xi)-L)f(\xi)d\xi \right) =
\left\{
\begin{array}{ll}
f(t-L) & (t > L) \\
0 & (0 \le t < L)
\end{array}
\right\}
= f(t-L) \quad (t \neq L)
\end{equation*}
となりますので、これを$\mathcal{M}$に持ち込むと、
\begin{equation*}
s^2 \ast \{ R(t-L) \} \ast \{ f(t) \} = \{ f(t-L) \} \tag{3}
\end{equation*}
が得られます。従って $s^2 \ast \{ R(t-L) \}$ がむだ時間要素に相当することになるので、結局次のように定義すれば良いことになります。
これだとミクシンスキーの演算子法の世界で正当な定義です。この定義を使って$(3)$を書き換えると、
\[ e^{-sL} \ast \{ f(t) \} = \{ f(t-L) \} \tag{4} \]
となり、$e^{-sL}$ がむだ時間要素を表すことが明白です。
ちなみに、上の定義で形式的に $L=0$ とすると、左辺は乗法単位元 $1 = \delta$ となり、右辺は
\[ s^2 \ast \{ R(t) \} = s \ast (s \ast R) = s \ast (R' + R(0)) = s \ast \ell = \delta \]
となるので、整合が取れています。
もう一つ、これは$s$の指数関数の形で表現されていますので、$L,M > 0$ に対して指数法則
\[ e^{-sL} \ast e^{-sM} = e^{-s(L+M)} \]
が成立することを示す必要があります。このことは「むだ時間要素」の意味から明らかなようにも見えますが、きちんと証明するためには、$(4)$において $f(t) = R(t-M)$ とおくことにより、
\[ e^{-sL} \ast \{ R(t-M) \} = \{ R((t-L)-M) \} = \{ R(t-(L+M)) \} \]
となるので、
\begin{eqnarray*}
e^{-sL} \ast e^{-sM} &=& e^{-sL} \ast s^2 \ast \{ R(t-M) \}\\
&=& s^2 \ast e^{-sL} \ast \{ R(t-M) \} \\
&=& s^2 \ast \{ R(t-(L+M)) \} \\
&=& e^{-s(L+M)}
\end{eqnarray*}
とすれば導かれます。
［注意］式$(3)$や$(4)$の右辺の $\{ f(t-L) \}$ は、$t < L$ では $f(t-L)=0$ なので、$f(0) = 0$ ならば $f(t-L)$ が $[0,\infty)$ で連続になるので問題ないですが、そうでない場合は $\mathcal{M}$ の要素として未定義なので問題があります。そこで逆に $\mathcal{M}$ においては$(4)$の左辺で右辺を「定義」してしまう方法があります。これによって $f(0) \neq 0$ の場合も $\{ f(t-L) \}$ を $\mathcal{M}$ の要素とみなせます。もっとよい定義としては、$g(t)$ が一般に $[0,\infty)$ で区分的連続関数ならば、その不定積分 $\displaystyle G(t) = \int_0^t g(\xi)d\xi$ が $[0,\infty)$ で連続なので、$\mathcal{M}$上で $g = s \ast G$ と定義することができます。従って $\{ f(t-L) \}$ についても $f(t-L)$ が $[0,\infty)$ で区分的連続関数なので $\mathcal{M}$ の要素になります。
参考文献：吉田耕作、「演算子法―一つの超函数論」、東京大学出版会（1982）
（前記事）
しかし、その記事の中で登場する実際の伝達関数としては、微分演算子$s$の有理式の形で表されるものしかありませんでした。普通は伝達関数はラプラス変換によって定義され、もっと多種多様な$s$の関数が登場しますが、先の記事にはとにもかくにもこれがないと始まらないというべき重要なものが抜けています。
そう、「むだ時間要素」です。
むだ時間要素とは、$L$を正実数とすると、入力 $u(t)$ に対して出力 $y(t) = u(t-L)$ を返すようなシステムの要素のことです。つまり時間$L$だけ出力が遅れて現れるということです。この要素の伝達関数はラプラス変換ならば、
\begin{equation*}
\int_0^\infty y(t)e^{-st}dt = \int_0^\infty u(t-L)e^{-st}dt = \int_{-L}^\infty u(\xi)e^{-s(\xi+L)}d\xi = e^{-sL} \int_0^\infty u(\xi)e^{-s\xi}d\xi
\end{equation*}
より、$e^{-sL}$ であることがすぐにわかります（ $t < 0$ では $u(t) =0$ と考えます）。しかし、ミクシンスキーの演算子法で定義した空間 $\mathcal{M}$ においては、$s$は微分演算子であり、$s$の指数関数なるものの意味が明らかではないので、改めて定義する必要があります。
そこで、$\mathcal{M}$ における $e^{-sL}$ を既知の関数を使って定義することを考えます。
$\mathcal{M}$ においては、例えば
\[ \frac{1}{s-a} = \{ e^{at} \} \]
のように、関数 $f(t)$ の$\mathcal{M}$ における表現が$f$のラプラス変換と同じ形をしていました。そこで、ディラックのデルタ関数$\delta$を使った次の関係に注目します。
\[ \int_0^\infty \delta(t-L)e^{-st}dt = e^{-sL} \]
これは $\delta(t-L)$ のラプラス変換が $e^{-sL}$ ということなので、
\[ e^{-sL} = \{ \delta(t-L) \} \]
と定義すれば良いように思えます。こう定義すると、任意の $[0, \infty)$ における連続関数 $f(t) \in \mathcal{C}$（ただし $t < 0$ のときは $f(t)=0$ とします）に対して、デルタ関数のよく知られた性質を使うことによって、
\begin{equation*}
\int_0^t \delta((t-\xi)-L)f(\xi)d\xi = f(t-L) \tag{1}
\end{equation*}
が導かれますので、これを$\mathcal{M}$に持ち込むと
\begin{equation*}
\{ \delta(t-L) \} \ast \{ f(t) \} = \{ f(t-L) \}
\end{equation*}
となりますから、$e^{-sL} = \{ \delta(t-L) \}$ がむだ時間要素の伝達関数の意味になっています。
しかしこの定義はやはりマズイですね。$\mathcal{C}$ はそもそも $[0,\infty)$ において連続な複素数値関数の集合だったのに、関数でもないデルタ関数をあたかも $\mathcal{C}$ の要素のように使って $\mathcal{M}$ の要素を定義するのはルール違反です。
そこで、$(1)$において左辺をデルタ関数$\delta$の代わりに、ステップ関数$\ell$に置き換えてみましょう。ここで$\ell$は、
\begin{equation*}
\ell(t) =
\left\{
\begin{array}{ll}
1 & (t \ge 0) \\
0 & (t < 0)
\end{array}
\right.
\end{equation*}
によって定まる関数です。これを使うと、
\begin{equation*}
\int_0^t \ell((t-\xi)-L)f(\xi)d\xi =
\left\{
\begin{array}{ll}
\displaystyle \int_0^{t-L} f(\xi)d\xi & (t \ge L) \\
0 & (0 \le t < L)
\end{array}
\right.
\tag{2}
\end{equation*}
この両辺の微分をとると、
\begin{equation*}
\frac{d}{dt} \left( \int_0^t \ell((t-\xi)-L)f(\xi)d\xi \right) =
\left\{
\begin{array}{ll}
f(t-L) & (t > L) \\
0 & (0 \le t < L)
\end{array}
\right\}
= f(t-L) \quad (t \neq L)
\end{equation*}
となります。これを$\mathcal{M}$に持ち込むと、$(2)$の右辺の関数は初期値が$0$なので左辺は微分演算子$s$を掛ければよく、また不連続点 $t=L$ を無視すると、
\begin{equation*}
s \ast \{ \ell(t-L) \} \ast \{ f(t) \} = \{ f(t-L) \}
\end{equation*}
が得られます。従って $s \ast \{ \ell(t-L) \}$ がむだ時間要素に相当することになるので、これを $e^{-sL}$ と定義すれば良いように思えます。
しかしこれでもまだ良くありません。なぜなら、$\mathcal{C}$の要素 は $[0,\infty)$ において連続という条件があるのに、$\ell(t-L)$ は $t=L$ において不連続になっているからです。
そこでステップ関数$\ell$の代わりに、ランプ関数$R$を使います。ここで$R$は、
\begin{equation*}
R(t) =
\left\{
\begin{array}{ll}
t & (t \ge 0) \\
0 & (t < 0)
\end{array}
\right.
\end{equation*}
によって定まる関数で、全実数域で連続になります。従って $\{ R(t-L) \} \in \mathcal{C}$ となるので、$\mathcal{M}$ 上の演算子の定義として堂々と使用することができます。
$(1)$において左辺を$\delta$の代わりに$R$に置き換えてみましょう。$t \ge L$ のときは、
\begin{equation*}
\int_0^t R((t-\xi)-L)f(\xi)d\xi = \int_0^{t-L} (t-L-\xi)f(\xi)d\xi
\end{equation*}
ここで $\displaystyle F(t) = \int_0^tf(\xi)d\xi$ とおくと、部分積分を用いて、
\begin{equation*}
\int_0^{t-L} (t-L-\xi)f(\xi)d\xi = \int_0^{t-L} F(\xi)d\xi
\end{equation*}
従って $t < L$ のときも合わせて、
\begin{equation*}
\int_0^t R((t-\xi)-L)f(\xi)d\xi =
\left\{
\begin{array}{ll}
\displaystyle \int_0^{t-L} F(\xi)d\xi & (t \ge L) \\
0 & (0 \le t < L)
\end{array}
\right.
\end{equation*}
となり、これは $[0,\infty)$ で連続です。
この両辺を微分すると、
\begin{equation*}
\frac{d}{dt} \left( \int_0^t R((t-\xi)-L)f(\xi)d\xi \right) =
\left\{
\begin{array}{ll}
F(t-L) & (t \ge L) \\
0 & (0 \le t < L)
\end{array}
\right.
\end{equation*}
となって、これも $[0,\infty)$ で連続です。さらにもう1回微分すると、
\begin{equation*}
\frac{d^2}{dt^2} \left( \int_0^t R((t-\xi)-L)f(\xi)d\xi \right) =
\left\{
\begin{array}{ll}
f(t-L) & (t > L) \\
0 & (0 \le t < L)
\end{array}
\right\}
= f(t-L) \quad (t \neq L)
\end{equation*}
となりますので、これを$\mathcal{M}$に持ち込むと、
\begin{equation*}
s^2 \ast \{ R(t-L) \} \ast \{ f(t) \} = \{ f(t-L) \} \tag{3}
\end{equation*}
が得られます。従って $s^2 \ast \{ R(t-L) \}$ がむだ時間要素に相当することになるので、結局次のように定義すれば良いことになります。
【ミクシンスキーの演算子法における「むだ時間要素」の定義】
$L > 0$ に対し、$\mathcal{M}$において \[ e^{-sL} = s^2 \ast \{ R(t-L) \} \] と定義する。ただし$R$はランプ関数を表す。
$L > 0$ に対し、$\mathcal{M}$において \[ e^{-sL} = s^2 \ast \{ R(t-L) \} \] と定義する。ただし$R$はランプ関数を表す。
これだとミクシンスキーの演算子法の世界で正当な定義です。この定義を使って$(3)$を書き換えると、
\[ e^{-sL} \ast \{ f(t) \} = \{ f(t-L) \} \tag{4} \]
となり、$e^{-sL}$ がむだ時間要素を表すことが明白です。
ちなみに、上の定義で形式的に $L=0$ とすると、左辺は乗法単位元 $1 = \delta$ となり、右辺は
\[ s^2 \ast \{ R(t) \} = s \ast (s \ast R) = s \ast (R' + R(0)) = s \ast \ell = \delta \]
となるので、整合が取れています。
もう一つ、これは$s$の指数関数の形で表現されていますので、$L,M > 0$ に対して指数法則
\[ e^{-sL} \ast e^{-sM} = e^{-s(L+M)} \]
が成立することを示す必要があります。このことは「むだ時間要素」の意味から明らかなようにも見えますが、きちんと証明するためには、$(4)$において $f(t) = R(t-M)$ とおくことにより、
\[ e^{-sL} \ast \{ R(t-M) \} = \{ R((t-L)-M) \} = \{ R(t-(L+M)) \} \]
となるので、
\begin{eqnarray*}
e^{-sL} \ast e^{-sM} &=& e^{-sL} \ast s^2 \ast \{ R(t-M) \}\\
&=& s^2 \ast e^{-sL} \ast \{ R(t-M) \} \\
&=& s^2 \ast \{ R(t-(L+M)) \} \\
&=& e^{-s(L+M)}
\end{eqnarray*}
とすれば導かれます。
［注意］式$(3)$や$(4)$の右辺の $\{ f(t-L) \}$ は、$t < L$ では $f(t-L)=0$ なので、$f(0) = 0$ ならば $f(t-L)$ が $[0,\infty)$ で連続になるので問題ないですが、そうでない場合は $\mathcal{M}$ の要素として未定義なので問題があります。そこで逆に $\mathcal{M}$ においては$(4)$の左辺で右辺を「定義」してしまう方法があります。これによって $f(0) \neq 0$ の場合も $\{ f(t-L) \}$ を $\mathcal{M}$ の要素とみなせます。もっとよい定義としては、$g(t)$ が一般に $[0,\infty)$ で区分的連続関数ならば、その不定積分 $\displaystyle G(t) = \int_0^t g(\xi)d\xi$ が $[0,\infty)$ で連続なので、$\mathcal{M}$上で $g = s \ast G$ と定義することができます。従って $\{ f(t-L) \}$ についても $f(t-L)$ が $[0,\infty)$ で区分的連続関数なので $\mathcal{M}$ の要素になります。
参考文献：吉田耕作、「演算子法―一つの超函数論」、東京大学出版会（1982）
（前記事）
有限体の勉強 〜麻雀大会組合せ問題への応用〜 [数学]
有限体について書かれたサイトをいくつか読んでいると、「麻雀大会組合せ問題」とでもいうべき問題に有限体 $F_4$ を使って解を与える方法がよく紹介されています（例えばこのサイトなど）。
僕はこれらの説明をパッと読んで、なんでこれでうまくいくのかがなかなか良くわかりませんでした。今日になってようやく理解できた気になりましたので、僕（サル）にもわかる書き方でうまくいく原理を紹介します。
「麻雀大会組合せ問題」とは次の問題です。
麻雀は一つの卓を$4$人で囲んで行うゲームですから、あるメンバーから見ると$1$ゲーム（「半荘（ハンチャン）」と言います）あたり$3$人と卓を囲むので、自分以外の$15$人全員とちょうど$1$回ずつ卓を囲むには半荘$5$回が必要なわけです。全メンバーがそのような卓の囲み方になるような計画ができるかという問題です。卓が$4$つあれば半荘$4$回が同時並行できるので、それも最大に活用して$16$名が無駄な待ち時間なく進むようにせよとの要求もあります。可能なのでしょうか。
この問題を解くのに、位数$4$の有限体 $F_4$ が使えるというのが今回の話です。
実は今回の話では「 $F_4$ は$4$個の元を持つ体である」以上のことは何一つ使いません。体の構造がどうなっているかを考える必要はないのです。そこで $F_4$ の$4$個の元を、
\[ F_4 = \{ \, e_1, \, e_2, \, e_3, \, e_4 \, \} \]
とおきます。$e_1 \sim e_4$ のどれかが$0$だったり$1$だったりしますが、それは気にしなくても構いません。
まず、$F_4$ の元 $x,y$ の$2$つ組 $(x,y)$ を要素にもつ集合 $F_4^2$ を考えます。これを「$F_4$ 上の $xy-$平面」略して「$F_4$ 平面」と呼びます。
この集合の要素数は$16$で、これらを「$F_4$ 平面上の点」と呼びます。そして各点をそれぞれ麻雀大会のメンバー$16$人に割り当てます。
次に、$x,y$ を $F_4$ 上を動く変数とし、$a,b,c$ を $F_4$ 上の定数（パラメータ）として、次の$2$種類の式を考えます。
\begin{eqnarray*}
(A) \quad y &=& ax+b \\
(B) \quad x &=& c
\end{eqnarray*}
これらはどちらも $x,y$ に関する$1$次式ですので、「$F_4$ 平面上の直線」と呼びます。$(A)$ の形の直線はパラメータ $a,b$ の組合せで$16$通りあり、$(B)$ の形の直線はパラメータ $c$ の個数の$4$通りあり、合計$20$通りの直線があります。
ここで僕は、$F_4$ 平面のイメージとして $4 \times 4$ の格子状の点の並びをイメージしてしまったので、その上に直線がどのように引けるのかで困惑してしまいました。名前につられて幾何的な平面や直線をイメージするのはこの場合には逆効果です。以下の議論は純粋に代数的に考えることが肝要です。
$F_4$ 平面上の点と直線の関係には、普通のユークリッド幾何と同じ、次の性質が成り立ちます。
これらは $F_4$ が体であることから、次に示すように中学校の数学でやったのと全く同様のやり方で証明できます。
まず①を証明します。異なる$2$点を $(x_1,y_1), (x_2,y_2)$ とします。$x_1=x_2$ と $y_1=y_2$ は同時には成立しません。
$x_1 \neq x_2$ の場合を考えます。もしこれらを同時に通る直線があれば、それは $(B)$ の形ではありえませんので $(A)$ の形になり、
\begin{eqnarray*}
y_1 &=& ax_1+b \\
y_2 &=& ax_2+b
\end{eqnarray*}
が同時に成り立つはずです。上の式から下の式を引くと、
\[ y_1-y_2 = a(x_1-x_2) \]
となるので、$x_1-x_2 \neq 0$ と $F_4$ が体であることより、
\[ a = \frac{y_1-y_2}{x_1-x_2} \]
と $a$ が定まり、これを使って
\[ b = \frac{-x_1(y_1-y_2)}{x_1-x_2} + y_1 = \frac{x_1y_2-x_2y_1}{x_1-x_2} \]
と $b$ も定まり、従って直線が$1$つに定まります。この直線が実際に$2$点 $(x_1,y_1), (x_2,y_2)$ を通ることも確認できますので、$x_1 \neq x_2$ の場合に①が示されました。
$x_1=x_2, \ y_1 \neq y_2$ の場合は、$c=x_1=x_2$ としたときの $(B)$ の形が唯一の$2$点を通る直線になります。以上で①が証明されました。
次に②を証明します。ここでいう平行する異なる$2$直線とは、$a$ が同じで $b$ が異なる $(A)$ の形の$2$直線、または $c$ が異なる $(B)$ の形の$2$直線のことをいいます。
前者の場合、$b_1 \neq b_2$ に対して次の$2$直線を考えます。
\begin{eqnarray*}
y &=& ax+b_1 \\
y &=& ax+b_2
\end{eqnarray*}
これらがもし$1$点 $(x_0,y_0)$ を共有したと仮定すると、
\begin{eqnarray*}
y_0 &=& ax_0+b_1 \\
y_0 &=& ax_0+b_2
\end{eqnarray*}
より $b_1=b_2$ が導かれるので、矛盾を生じます。
後者の場合、$c_1 \neq c_2$ に対して次の$2$直線を考えます。
\begin{eqnarray*}
x &=& c_1 \\
x &=& c_2
\end{eqnarray*}
これらがもし$1$点 $(x_0,y_0)$ を共有したと仮定すると、
\begin{eqnarray*}
x_0 &=& c_1 \\
x_0 &=& c_2
\end{eqnarray*}
より $c_1=c_2$ が導かれるので、やはり矛盾を生じます。以上で②が証明されました。
さて、$F_4$ 平面上の直線についてはさらに次の性質があります。
これを示すために、$F_4 = \{ \, e_1, \, e_2, \, e_3, \, e_4 \, \}$ としたことを思い出しましょう。$(A)$ の形の直線 $y = ax+b$ については、
\[ (e_1, ae_1+b), \ (e_2, ae_2+b), \ (e_3, ae_3+b), \ (e_4, ae_4+b) \tag{1} \]
の$4$個の点を通り、それ以外は通りようがありません。また $(B)$ の形の直線 $x = c$ については、
\[ (c,e_1), \ (c,e_2), \ (c,e_3), \ (c,e_4) \tag{2} \]
の$4$個の点を通り、それ以外は通りようがありません。これで③が成り立つことがわかります。
直線に関する①②③の性質を使うと、麻雀大会組合せ問題が次のように解決されます。
まず、$a=e_1$ と固定し、$b=e_1,e_2,e_3,e_4$ とした $(A)$ の形の$4$本の直線を考え、これらの直線をそれぞれ雀卓に見立てます。性質③より各直線はちょうど$4$点を通り、それらは$(1)$を具体的に（ $F_4$ において）計算することによって特定できます。特定した各点にはそれぞれメンバーが割り当てられていますので、$4$台の雀卓にそれぞれ$4$人ずつのメンバーが割り当てられます。また、これら$4$本の直線は平行していますので、性質②より同じメンバーが$2$台以上の卓に割り当てられることはありません。従って、これで$16$人のメンバー全員が$4$卓を使って同時に半荘をプレイできることになります。
全卓が半荘$1$回終了したら、次に $a=e_2$ と固定し、$b=e_1,e_2,e_3,e_4$ とした $(A)$ の形の$4$本の直線を考えて同様に雀卓にメンバーを割り当てて半荘をプレイします。これが終わればまた $a=e_3, a=e_4$ として同様に続けます。最後に $c=e_1,e_2,e_3,e_4$ とした $(B)$ の形の$4$本の直線について$(2)$を用いて雀卓にメンバーを割り当てて半荘をプレイします。以上で同時に$4$卓ずつ$5$回、全部で$20$回の半荘がプレイされます。
そして、性質①によって、異なる$2$人のメンバーはちょうど$1$回だけ同じ卓に割り当てられます。
これで問題の要件を満足する麻雀大会の組合せを計画することができました。
この問題の解法をよく見ると、初めにことわったとおり、「 $F_4$ は$4$個の元を持つ体である」以上のことは何一つ使っていないことがわかると思います。ということは、例えば位数$8$の有限体 $F_8$ を使って、
「$64$人の選手が、$8$レーンあるプールを使って水泳大会を行う場合の、各々の選手が自分以外の全ての選手とちょうど$1$回だけ同時に泳ぐような組合せ」
を計画することも、麻雀大会と全く同じ方法で可能なわけです（この場合各選手は全部で$9$回泳ぐことになります。かなりしんどい。）。さらに一般に、$q$が素数のべきであれば位数$q$の有限体 $F_q$ が存在しますので、$q^2$ 人のメンバーが $q$ 人ずつ組になって行う何らかの大会（人狼ゲームでも何でも可）の組合せが $F_q$ を使って上記の方法で計画できることになります。
（前記事）
僕はこれらの説明をパッと読んで、なんでこれでうまくいくのかがなかなか良くわかりませんでした。今日になってようやく理解できた気になりましたので、僕（サル）にもわかる書き方でうまくいく原理を紹介します。
「麻雀大会組合せ問題」とは次の問題です。
【問題】$16$人のメンバーで$4$卓を使用して麻雀大会を行う。$4$卓全てを同時に無駄なく使用し、しかも全てのメンバーが自分以外の$15$人と各々ちょうど$1$回ずつ卓を囲むような組合せを計画せよ。
麻雀は一つの卓を$4$人で囲んで行うゲームですから、あるメンバーから見ると$1$ゲーム（「半荘（ハンチャン）」と言います）あたり$3$人と卓を囲むので、自分以外の$15$人全員とちょうど$1$回ずつ卓を囲むには半荘$5$回が必要なわけです。全メンバーがそのような卓の囲み方になるような計画ができるかという問題です。卓が$4$つあれば半荘$4$回が同時並行できるので、それも最大に活用して$16$名が無駄な待ち時間なく進むようにせよとの要求もあります。可能なのでしょうか。
この問題を解くのに、位数$4$の有限体 $F_4$ が使えるというのが今回の話です。
実は今回の話では「 $F_4$ は$4$個の元を持つ体である」以上のことは何一つ使いません。体の構造がどうなっているかを考える必要はないのです。そこで $F_4$ の$4$個の元を、
\[ F_4 = \{ \, e_1, \, e_2, \, e_3, \, e_4 \, \} \]
とおきます。$e_1 \sim e_4$ のどれかが$0$だったり$1$だったりしますが、それは気にしなくても構いません。
まず、$F_4$ の元 $x,y$ の$2$つ組 $(x,y)$ を要素にもつ集合 $F_4^2$ を考えます。これを「$F_4$ 上の $xy-$平面」略して「$F_4$ 平面」と呼びます。
この集合の要素数は$16$で、これらを「$F_4$ 平面上の点」と呼びます。そして各点をそれぞれ麻雀大会のメンバー$16$人に割り当てます。
次に、$x,y$ を $F_4$ 上を動く変数とし、$a,b,c$ を $F_4$ 上の定数（パラメータ）として、次の$2$種類の式を考えます。
\begin{eqnarray*}
(A) \quad y &=& ax+b \\
(B) \quad x &=& c
\end{eqnarray*}
これらはどちらも $x,y$ に関する$1$次式ですので、「$F_4$ 平面上の直線」と呼びます。$(A)$ の形の直線はパラメータ $a,b$ の組合せで$16$通りあり、$(B)$ の形の直線はパラメータ $c$ の個数の$4$通りあり、合計$20$通りの直線があります。
ここで僕は、$F_4$ 平面のイメージとして $4 \times 4$ の格子状の点の並びをイメージしてしまったので、その上に直線がどのように引けるのかで困惑してしまいました。名前につられて幾何的な平面や直線をイメージするのはこの場合には逆効果です。以下の議論は純粋に代数的に考えることが肝要です。
$F_4$ 平面上の点と直線の関係には、普通のユークリッド幾何と同じ、次の性質が成り立ちます。
① 異なる$2$点を通る直線は$1$本だけ存在する
② 平行する異なる$2$直線は点を共有しない
② 平行する異なる$2$直線は点を共有しない
これらは $F_4$ が体であることから、次に示すように中学校の数学でやったのと全く同様のやり方で証明できます。
まず①を証明します。異なる$2$点を $(x_1,y_1), (x_2,y_2)$ とします。$x_1=x_2$ と $y_1=y_2$ は同時には成立しません。
$x_1 \neq x_2$ の場合を考えます。もしこれらを同時に通る直線があれば、それは $(B)$ の形ではありえませんので $(A)$ の形になり、
\begin{eqnarray*}
y_1 &=& ax_1+b \\
y_2 &=& ax_2+b
\end{eqnarray*}
が同時に成り立つはずです。上の式から下の式を引くと、
\[ y_1-y_2 = a(x_1-x_2) \]
となるので、$x_1-x_2 \neq 0$ と $F_4$ が体であることより、
\[ a = \frac{y_1-y_2}{x_1-x_2} \]
と $a$ が定まり、これを使って
\[ b = \frac{-x_1(y_1-y_2)}{x_1-x_2} + y_1 = \frac{x_1y_2-x_2y_1}{x_1-x_2} \]
と $b$ も定まり、従って直線が$1$つに定まります。この直線が実際に$2$点 $(x_1,y_1), (x_2,y_2)$ を通ることも確認できますので、$x_1 \neq x_2$ の場合に①が示されました。
$x_1=x_2, \ y_1 \neq y_2$ の場合は、$c=x_1=x_2$ としたときの $(B)$ の形が唯一の$2$点を通る直線になります。以上で①が証明されました。
次に②を証明します。ここでいう平行する異なる$2$直線とは、$a$ が同じで $b$ が異なる $(A)$ の形の$2$直線、または $c$ が異なる $(B)$ の形の$2$直線のことをいいます。
前者の場合、$b_1 \neq b_2$ に対して次の$2$直線を考えます。
\begin{eqnarray*}
y &=& ax+b_1 \\
y &=& ax+b_2
\end{eqnarray*}
これらがもし$1$点 $(x_0,y_0)$ を共有したと仮定すると、
\begin{eqnarray*}
y_0 &=& ax_0+b_1 \\
y_0 &=& ax_0+b_2
\end{eqnarray*}
より $b_1=b_2$ が導かれるので、矛盾を生じます。
後者の場合、$c_1 \neq c_2$ に対して次の$2$直線を考えます。
\begin{eqnarray*}
x &=& c_1 \\
x &=& c_2
\end{eqnarray*}
これらがもし$1$点 $(x_0,y_0)$ を共有したと仮定すると、
\begin{eqnarray*}
x_0 &=& c_1 \\
x_0 &=& c_2
\end{eqnarray*}
より $c_1=c_2$ が導かれるので、やはり矛盾を生じます。以上で②が証明されました。
さて、$F_4$ 平面上の直線についてはさらに次の性質があります。
③ 各直線はちょうど $F_4$ の元の数（$4$個）の点を通る
これを示すために、$F_4 = \{ \, e_1, \, e_2, \, e_3, \, e_4 \, \}$ としたことを思い出しましょう。$(A)$ の形の直線 $y = ax+b$ については、
\[ (e_1, ae_1+b), \ (e_2, ae_2+b), \ (e_3, ae_3+b), \ (e_4, ae_4+b) \tag{1} \]
の$4$個の点を通り、それ以外は通りようがありません。また $(B)$ の形の直線 $x = c$ については、
\[ (c,e_1), \ (c,e_2), \ (c,e_3), \ (c,e_4) \tag{2} \]
の$4$個の点を通り、それ以外は通りようがありません。これで③が成り立つことがわかります。
直線に関する①②③の性質を使うと、麻雀大会組合せ問題が次のように解決されます。
まず、$a=e_1$ と固定し、$b=e_1,e_2,e_3,e_4$ とした $(A)$ の形の$4$本の直線を考え、これらの直線をそれぞれ雀卓に見立てます。性質③より各直線はちょうど$4$点を通り、それらは$(1)$を具体的に（ $F_4$ において）計算することによって特定できます。特定した各点にはそれぞれメンバーが割り当てられていますので、$4$台の雀卓にそれぞれ$4$人ずつのメンバーが割り当てられます。また、これら$4$本の直線は平行していますので、性質②より同じメンバーが$2$台以上の卓に割り当てられることはありません。従って、これで$16$人のメンバー全員が$4$卓を使って同時に半荘をプレイできることになります。
全卓が半荘$1$回終了したら、次に $a=e_2$ と固定し、$b=e_1,e_2,e_3,e_4$ とした $(A)$ の形の$4$本の直線を考えて同様に雀卓にメンバーを割り当てて半荘をプレイします。これが終わればまた $a=e_3, a=e_4$ として同様に続けます。最後に $c=e_1,e_2,e_3,e_4$ とした $(B)$ の形の$4$本の直線について$(2)$を用いて雀卓にメンバーを割り当てて半荘をプレイします。以上で同時に$4$卓ずつ$5$回、全部で$20$回の半荘がプレイされます。
そして、性質①によって、異なる$2$人のメンバーはちょうど$1$回だけ同じ卓に割り当てられます。
これで問題の要件を満足する麻雀大会の組合せを計画することができました。
この問題の解法をよく見ると、初めにことわったとおり、「 $F_4$ は$4$個の元を持つ体である」以上のことは何一つ使っていないことがわかると思います。ということは、例えば位数$8$の有限体 $F_8$ を使って、
「$64$人の選手が、$8$レーンあるプールを使って水泳大会を行う場合の、各々の選手が自分以外の全ての選手とちょうど$1$回だけ同時に泳ぐような組合せ」
を計画することも、麻雀大会と全く同じ方法で可能なわけです（この場合各選手は全部で$9$回泳ぐことになります。かなりしんどい。）。さらに一般に、$q$が素数のべきであれば位数$q$の有限体 $F_q$ が存在しますので、$q^2$ 人のメンバーが $q$ 人ずつ組になって行う何らかの大会（人狼ゲームでも何でも可）の組合せが $F_q$ を使って上記の方法で計画できることになります。
（前記事）
有限体の勉強 〜有限体をExcel上で計算する〜 [数学]
「有限体の勉強」という記事をいくつか書いてきましたが、これらの記事を書くために多くの有限体の四則演算を実際に行う必要が生じ、手計算ではとても大変なのでスプレッドシートを使ってきました。ここでその具体的な方法を紹介します。なお、ここではスプレッドシートとは一般用語の「表計算ソフト」の意味で使っており、Excelが代表的ですが LibreOffice(Calc) や Googleスプレッドシートも同様の操作になります。
有限体といっても、本記事では標数$2$の有限体を対象とします。標数が$2$以外の有限体はビット演算関数が使えないのでかなり複雑になるからです。
例としてリード・ソロモン符号の記事でも使った $F_{256}$ の場合を考えます。
まず、この体の元をどう表現するかを決める必要があります。そのために必要なのは $F_{256}$ の原始多項式です。これは $F_2$ 上の$8$次の既約多項式で、その根が $F_{256}$ の原始元になるもののことです。一般に原始多項式は試行錯誤で探し出すことになりますが、いまの場合は、
\[ X^8+X^4+X^3+X^2+1 \]
が原始多項式になることが知られていますのでこれを使い、その一つの根を$\alpha$と書きます。このとき、
\[ \alpha^8 = \alpha^4+\alpha^3+\alpha^2+1 \]
が成り立つので（標数$2$なのでプラスとマイナスの区別はありません）、$\alpha$のべき乗について、
\begin{eqnarray*}
\alpha^0 &=& && && && && && && && \alpha^0 \\
\alpha^1 &=& && && && && && && \alpha^1 \\
&\cdots& \\
\alpha^7 &=& \alpha^7 \\
\alpha^8 &=& && && && \alpha^4 &+& \alpha^3 &+& \alpha^2 && &+& \alpha^0 \\
\alpha^9 &=& && && \alpha^5 &+& \alpha^4 &+& \alpha^3 && &+& \alpha^1 \\
&\cdots& \\
\alpha^{253} &=& && \alpha^6 && && && &+& \alpha^2 &+& \alpha^1 &+& \alpha^0 \\
\alpha^{254} &=& \alpha^7 && && && &+& \alpha^3 &+& \alpha^2 &+& \alpha^1
\end{eqnarray*}
という1対1の対応ができ、$0$を除く $F_{256}$ の元が網羅されます（$\alpha^{255} = \alpha^0 = 1$ です）。左辺をべき表現、右辺をベクトル表現といいます。
Excel上でべき表現とベクトル表現をどうデータ化するかですが、べき表現は指数をそのまま整数値で、ベクトル表現は$\alpha$を$2$に置き換えて計算した数値でデータ化するのが一番扱い易いです。後者はどういうことかというと、例えば
\[ \alpha^4+\alpha^3+\alpha^2+\alpha^0 \quad \to \quad 2^4+2^3+2^2+2^0 = 29 \]
と数値化して扱うということです。そしてExcel上ではこのベクトル表現の数値化を基本とします。なぜなら BITXOR 関数などのビット演算関数が使えることと、べき表現は$0$を扱うことができないからです。
とはいえ、後で説明するようにべき表現も頻繁に使いますので、Excel上でべき表現とベクトル表現の対応表を作ることから始めます。縦にべき表現として$0$から$254$までを並べ、その右側の列に次のようにしてベクトル表現を入れます。$1$行目にべき表現$0$に対してベクトル表現$1$を入れます。$2$行目以降は一つ上の行の数値を$2$進法のビット列とみなし、それを BITLSHIFT 関数で左に$1$ビットシフトし、BITAND 関数で下$8$ビットだけをとり、さらに一つ上の行の数値の$7$ビット目が$1$ならば（つまり$128$以上ならば）$2^4+2^3+2^2+2^0 = 29$ との排他的論理和を BITXOR 関数で入れます。これをべき表現$254$の行まで繰り返すと、対応表が出来上がります。
この対応表はべき表現順に並んでいますので、これを丸ごとコピーして値ペーストし、左右を入れ替えてベクトル表現順に並べ替えた対応表も作っておきます。
言葉ではわかりにくいので、これらの対応表を LibreOffice で作ったものをここにアップロードします。ダウンロードしてセル内の数式を確認してください。Excelでも開けます。
対応表ができあがったら、これは一つのシートとして置いておき（シート名を「対応表」とします）、本番の計算は同じファイルの別シートで行うのが便利です。
例として、セルA1とセルB1にベクトル表現で表した数値が入っており、これらの $F_{256}$ としての和、差、積、商を返す計算式は次のようになります。
和については先ほど登場した BITXOR 関数を使って
=BITXOR(A1,B1)
となります。この関数は引数の数値を$2$進法のビット列とみなして各ビット毎に排他的論理和をとる関数です。
差については標数が$2$なので和と全く同じ
=BITXOR(A1,B1)
となります。
積については、べき表現だと単に足し合わせて$255$の剰余をとるだけなので、ここで先ほど作った対応表を使ってベクトル表現からべき表現に変換し、足し合わせて$255$の剰余をとり、結果をまた対応表でべき表現からベクトル表現に戻せばできあがりです。これらの変換には、みんな大好き VLOOKUP 関数が使えます。実際に書き下すと、
=VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)
となります（対応表のセル範囲はアップロードしたファイルに対応しています）。ただし引数がどちらも$0$でなければこれで良いのですが、どちらかが$0$だとエラーが出てしまいますので、複雑にはなりますが IF 関数を使って、
=IF(A1=0,0,IF(B1=0,0,VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば完璧です。
商については、積の場合の指数の和を差に変えれば良いので、例えば、
=IF(B1=0,"ゼロ除算エラー",IF(A1=0,0,VLOOKUP(MOD(
VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)-VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE)
,255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば良いでしょう。
（続く）（前記事）
有限体といっても、本記事では標数$2$の有限体を対象とします。標数が$2$以外の有限体はビット演算関数が使えないのでかなり複雑になるからです。
例としてリード・ソロモン符号の記事でも使った $F_{256}$ の場合を考えます。
まず、この体の元をどう表現するかを決める必要があります。そのために必要なのは $F_{256}$ の原始多項式です。これは $F_2$ 上の$8$次の既約多項式で、その根が $F_{256}$ の原始元になるもののことです。一般に原始多項式は試行錯誤で探し出すことになりますが、いまの場合は、
\[ X^8+X^4+X^3+X^2+1 \]
が原始多項式になることが知られていますのでこれを使い、その一つの根を$\alpha$と書きます。このとき、
\[ \alpha^8 = \alpha^4+\alpha^3+\alpha^2+1 \]
が成り立つので（標数$2$なのでプラスとマイナスの区別はありません）、$\alpha$のべき乗について、
\begin{eqnarray*}
\alpha^0 &=& && && && && && && && \alpha^0 \\
\alpha^1 &=& && && && && && && \alpha^1 \\
&\cdots& \\
\alpha^7 &=& \alpha^7 \\
\alpha^8 &=& && && && \alpha^4 &+& \alpha^3 &+& \alpha^2 && &+& \alpha^0 \\
\alpha^9 &=& && && \alpha^5 &+& \alpha^4 &+& \alpha^3 && &+& \alpha^1 \\
&\cdots& \\
\alpha^{253} &=& && \alpha^6 && && && &+& \alpha^2 &+& \alpha^1 &+& \alpha^0 \\
\alpha^{254} &=& \alpha^7 && && && &+& \alpha^3 &+& \alpha^2 &+& \alpha^1
\end{eqnarray*}
という1対1の対応ができ、$0$を除く $F_{256}$ の元が網羅されます（$\alpha^{255} = \alpha^0 = 1$ です）。左辺をべき表現、右辺をベクトル表現といいます。
Excel上でべき表現とベクトル表現をどうデータ化するかですが、べき表現は指数をそのまま整数値で、ベクトル表現は$\alpha$を$2$に置き換えて計算した数値でデータ化するのが一番扱い易いです。後者はどういうことかというと、例えば
\[ \alpha^4+\alpha^3+\alpha^2+\alpha^0 \quad \to \quad 2^4+2^3+2^2+2^0 = 29 \]
と数値化して扱うということです。そしてExcel上ではこのベクトル表現の数値化を基本とします。なぜなら BITXOR 関数などのビット演算関数が使えることと、べき表現は$0$を扱うことができないからです。
とはいえ、後で説明するようにべき表現も頻繁に使いますので、Excel上でべき表現とベクトル表現の対応表を作ることから始めます。縦にべき表現として$0$から$254$までを並べ、その右側の列に次のようにしてベクトル表現を入れます。$1$行目にべき表現$0$に対してベクトル表現$1$を入れます。$2$行目以降は一つ上の行の数値を$2$進法のビット列とみなし、それを BITLSHIFT 関数で左に$1$ビットシフトし、BITAND 関数で下$8$ビットだけをとり、さらに一つ上の行の数値の$7$ビット目が$1$ならば（つまり$128$以上ならば）$2^4+2^3+2^2+2^0 = 29$ との排他的論理和を BITXOR 関数で入れます。これをべき表現$254$の行まで繰り返すと、対応表が出来上がります。
この対応表はべき表現順に並んでいますので、これを丸ごとコピーして値ペーストし、左右を入れ替えてベクトル表現順に並べ替えた対応表も作っておきます。
言葉ではわかりにくいので、これらの対応表を LibreOffice で作ったものをここにアップロードします。ダウンロードしてセル内の数式を確認してください。Excelでも開けます。
対応表ができあがったら、これは一つのシートとして置いておき（シート名を「対応表」とします）、本番の計算は同じファイルの別シートで行うのが便利です。
例として、セルA1とセルB1にベクトル表現で表した数値が入っており、これらの $F_{256}$ としての和、差、積、商を返す計算式は次のようになります。
和については先ほど登場した BITXOR 関数を使って
=BITXOR(A1,B1)
となります。この関数は引数の数値を$2$進法のビット列とみなして各ビット毎に排他的論理和をとる関数です。
差については標数が$2$なので和と全く同じ
=BITXOR(A1,B1)
となります。
積については、べき表現だと単に足し合わせて$255$の剰余をとるだけなので、ここで先ほど作った対応表を使ってベクトル表現からべき表現に変換し、足し合わせて$255$の剰余をとり、結果をまた対応表でべき表現からベクトル表現に戻せばできあがりです。これらの変換には、みんな大好き VLOOKUP 関数が使えます。実際に書き下すと、
=VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)
となります（対応表のセル範囲はアップロードしたファイルに対応しています）。ただし引数がどちらも$0$でなければこれで良いのですが、どちらかが$0$だとエラーが出てしまいますので、複雑にはなりますが IF 関数を使って、
=IF(A1=0,0,IF(B1=0,0,VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば完璧です。
商については、積の場合の指数の和を差に変えれば良いので、例えば、
=IF(B1=0,"ゼロ除算エラー",IF(A1=0,0,VLOOKUP(MOD(
VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)-VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE)
,255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば良いでしょう。
（続く）（前記事）
有限体の勉強 〜リード・ソロモン符号の誤り訂正の原理〜 [数学]
前回の記事で、リード・ソロモン符号の符号化と誤り訂正のシミュレーションをしてみました。その中で、誤り訂正についてはWikipediaの記事どおりにやってみただけで、その原理についてはまだ理解していませんでした。今回それを若干理解できたつもりになったので紹介します。
符号化に使う有限体（ガロア体）は前回の記事どおり $F_{256}$ とし、原始元$\alpha$も前回どおり、誤りシンボルの最大数も $t=2$ として、生成多項式 $G(X)$ についても前回使った
\[ G(X) = (X-\alpha^0)(X-\alpha^1)(X-\alpha^2)(X-\alpha^3) \]
を使います（生成多項式はもう少し一般化できますが、そこは省略します）。$t$が大きくなると、この後に出てくる行列のサイズが大きくなりますが、原理は同じです。
送信するシンボル数を冗長化符号も含めて$N$とすると、符号多項式 $C(X)$ の次数は $N-1$ です。$C(X)$ はその作り方から生成多項式 $G(X)$ で整除できるので、
\[ C(\alpha^0) = C(\alpha^1) = C(\alpha^2) = C(\alpha^3) = 0 \]
が成り立ちます。
ここで、通信路上で誤りが生じて最大$2$シンボルの誤りが生じたとします。このとき受信した多項式 $Y(X)$ は、
\begin{eqnarray*}
Y(X) &=& C(X) + E(X) \\
E(X) &=& e_1X^{m_1} + e_2X^{m_2} \quad (\, 0 \le m_1 \le m_2 \le N-1\,)
\end{eqnarray*}
と表せます。この $E(X)$ が求まると $C(X)$ が復元できることになります。誤りシンボル数がちょうど$2$個なら $e_1 \neq 0, e_2 \neq 0, m_1 \neq m_2$ 、$1$個ならば $e_1 \neq 0, e_2=0$ 、$0$個ならば $e_1=e_2=0$ と考えます。
そこで、まずシンドロームと呼ばれる次の値を $Y(X)$ から計算します。なお、これから出てくる計算は当然ながら全て有限体 $F_{256}$ 上での四則演算です。
\begin{eqnarray*}
S_1 &=& Y(\alpha^0) &=& E(\alpha^0) &=& e_1+e_2 \\
S_2 &=& Y(\alpha^1) &=& E(\alpha^1) &=& e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
S_3 &=& Y(\alpha^2) &=& E(\alpha^2) &=& e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
S_4 &=& Y(\alpha^3) &=& E(\alpha^3) &=& e_1\alpha^{3m_1}+e_2\alpha^{3m_2}
\end{eqnarray*}
ここで、実際に生じた誤りのシンボル数を$k$個とし、まず $k=2$ と仮定します。そして誤り位置多項式を、
\[ \sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) = 1 + \sigma_1X + \sigma_2X^2 \]
と定義します。この $\sigma(X)$ の係数 $\sigma_1, \sigma_2$ が具体的に求まれば、
\[ \sigma(\alpha^{-m_1}) = \sigma(\alpha^{-m_2}) = 0 \tag{1} \]
かつ、上記以外の $\alpha^m$ に対しては $\sigma(\alpha^m) \neq 0$ なので、$m$を$0$から $-(N-1)$ まで動かして上記の代入計算をすれば誤り位置 $m_1,m_2$ が求まります。そこで $\sigma_1, \sigma_2$ の求め方ですが、上記$(1)$より
\begin{eqnarray*}
1 + \sigma_1\alpha^{-m_1} + \sigma_2\alpha^{-2m_1} &=& 0 \\
1 + \sigma_1\alpha^{-m_2} + \sigma_2\alpha^{-2m_2} &=& 0
\end{eqnarray*}
が成り立つので、変形すると
\begin{eqnarray*}
\alpha^{m_1}\sigma_1 + \sigma_2 &=& \alpha^{2m_1} \\
\alpha^{m_2}\sigma_1 + \sigma_2 &=& \alpha^{2m_2}
\end{eqnarray*}
になります（標数$2$なので係数の$-$は$+$に置き換えできます）。これは行列でかくと、
\begin{equation*}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
=
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\tag{2}
\end{equation*}
となります。
一方、シンドロームについて、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1\alpha^{m_1}+e_2\alpha^{m_2} & e_1+e_2 \\
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} & e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\tag{3}
\end{eqnarray*}
が成り立つので、これと$(2)$より、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
e_1\alpha^{3m_1}+e_2\alpha^{3m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
S_3 \\
S_4 \\
\end{bmatrix}
\tag{4}
\end{eqnarray*}
が得られます。$(3)$より行列式を計算すると、
\begin{equation*}
\begin{vmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{vmatrix}
=
\begin{vmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{vmatrix}
\begin{vmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{vmatrix}
= e_1e_2(\alpha^{m_2}-\alpha^{m_1})(\alpha^{m_1}-\alpha^{m_2}) \neq 0
\tag{5}
\end{equation*}
と$0$でなく、$S_1 \sim S_4$ は既知なので、$(4)$を解いて $\sigma_1, \sigma_2$ を求めることができます。
これから先述の方法で $m_1, m_2$ が求まるので、シンドロームの定義式から得られる、
\begin{equation*}
\begin{bmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
e_1 \\
e_2 \\
\end{bmatrix}
=
\begin{bmatrix}
S_1 \\
S_2 \\
\end{bmatrix}
\end{equation*}
を解いて $e_1, e_2$ を求めることができます。この計算も
\begin{equation*}
\begin{vmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{vmatrix}
= \alpha^{m_2}-\alpha^{m_1} \neq 0
\end{equation*}
と行列式が$0$でないので可能です。これで無事に $E(X)$ を求めることができたので、誤り訂正ができました。
誤りシンボル数が $k<2$ のときは、$(5)$の行列式が$0$になるのでその判定ができて、計算がもっと簡単になります。
ここまでWikipediaに載っていたピーターソン法について、その誤り訂正の原理を紹介しました。しかしこの方法は「訂正するシンボル数が多いときは計算量が増大するため大規模な復号には使えないという欠点がある」ということだそうです。
そこで以下、より計算量の少ない方法であるユークリッド法について、J-Stageから閲覧できる開発者である平澤らの論文を参考にして、簡単に紹介します。
誤りシンボル数の最大値は一般化して$t$とし、生成多項式を
\[ G(X) = (X - \alpha^0)(X - \alpha^1) \cdots (X - \alpha^{2t}) \]
として、これから生成された $N-1$ 次の符号多項式 $C(X)$ が送信され、受信側では$k$個 $(k \le t)$ のシンボルに誤りが生じた受信多項式 $Y(X)$ を受信したとします。誤り多項式 $E(X) = Y(X) - C(X)$ を
\[ E(X) = e_1X^{m_1} + e_2X^{m_2} + \cdots + e_kX^{m_k} \quad (\, 0 \le m_1 < m_2 < \cdots < m_k \le N-1\,)\]
とすると、誤り訂正の目的はこの $E(X)$ を具体的に求めることです。
まず、$Y(X)$ からシンドローム
\[ S_j = Y(\alpha^{j-1}) \quad (j=1,2, \cdots, 2t) \]
を計算し、これらを係数とする次のシンドローム多項式 $S(X)$ を定義します。
\[ S(X) = S_1 + S_2X + S_3X^2 + \cdots + S_{2t}X^{2t-1} \]
このとき、各シンドロームの値について、
\[ S_j = E(\alpha^{j-1}) = e_1\alpha^{(j-1)m_1} + e_2\alpha^{(j-1)m_2} + \cdots + e_k\alpha^{(j-1)m_k} \quad (j=1,2, \cdots, 2t) \]
が成り立つので、$S(X)$ は次のように変形できます。
\[ S(X) = \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \]
次に、誤り位置多項式 $\sigma(X)$ を次によって定義します。
\begin{equation*}
\sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) \cdots (1 - \alpha^{m_k}X)
\end{equation*}
ここまではピーターソン法と同じですが、ここで次の関係式
\begin{equation*}
(1 - \alpha^{m_i}X)(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) = 1 - \alpha^{2tm_i}X^{2t} \quad (i=1, \cdots, k)
\end{equation*}
が成り立つので、$\sigma(X)S(X)$ について、
\begin{eqnarray*}
\sigma(X)S(X) &=& \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \prod_{1 \le j \le k}(1 - \alpha^{m_j}X) \\
&=& \sum_{i=1}^k e_i(1 - \alpha^{2tm_i}X^{2t}) \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \\
&=& \phi(X)X^{2t} + \eta(X)
\end{eqnarray*}
すなわち
\[ \sigma(X)S(X) + \phi(X)X^{2t} = \eta(X) \tag{6} \]
と表せます。ここで $\eta(X)$ は
\[ \eta(X) = \sum_{i=1}^k e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \tag{7} \]
で定まる $k-1$ 次以下の多項式で、これを誤り数値多項式といいます。
従って、誤り訂正問題は既知の多項式 $S(X)$ と $X^{2t}$ から、$(6)$をみたす多項式 $\sigma(X)$ と $\eta(X)$ とを求める問題に帰着されることになります。これを解くには、$S(X)$ と $X^{2t}$ の最大公約多項式を求めるユークリッド互除法のアルゴリズムが使えます。これが「ユークリッド法」と名付けられている理由です。このアルゴリズムはピーターソン法に比べて高速です。
$\eta(X)$ の次数が $k-1$ 次以下で $k \le t$ を前提としているので、ユークリッド互除法の剰余多項式の次数が $t-1$ 以下になれば、そこで停止すれば良いことになります。
この方法で $\sigma(X)$ と $\eta(X)$ が具体的に求まれば、まず誤りシンボル数 $k$ は $\sigma(X)$ の次数であり、誤り位置 $m_i$ は $\sigma(X)$ からピーターソン法と同様に
\[ \sigma(\alpha^{-m_i}) = 0 \quad (i=1, \cdots, k) \]
をみたす$k$個の指数が最大$N$回の代入によって求まります。
誤り数値 $e_i$ については、$(7)$に $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入して、
\[ \eta(\alpha^{-m_i}) = e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \tag{8} \]
から求まりますが、計算をもっと簡単にするためには、$\sigma(X)$ の形式微分
\[ \sigma'(X) = - \sum_{i=1}^k \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \]
をとって、これに $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入すると、
\[ \sigma'(\alpha^{-m_i}) = \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \]
となるので、これと$(8)$より
\[ e_i = \frac{ \alpha^{m_i} \eta(\alpha^{-m_i}) }{ \sigma'(\alpha^{-m_i}) } \quad (i=1, \cdots, k) \]
によっても求まります。なお、$\sigma(X)$ の形式微分は具体的には、
\[ \sigma(X) = 1 + \sigma_1X + \sigma_2X^2 + \cdots + \sigma_kX^k \]
に対して
\[ \sigma'(X) = \sigma_1 + 2\sigma_2X + \cdots + k\sigma_kX^{k-1} \]
ですが、標数$2$なので$k$が偶数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_{k-1}X^{k-2} \]
$k$が奇数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_kX^{k-1} \]
となります。
以上で受信多項式 $Y(X)$ から誤り多項式 $E(X)$ が具体的に求められたので、誤り訂正ができました。
巧妙すぎて頭がクラクラしそうです。感動しました。
（続く）（前記事）
符号化に使う有限体（ガロア体）は前回の記事どおり $F_{256}$ とし、原始元$\alpha$も前回どおり、誤りシンボルの最大数も $t=2$ として、生成多項式 $G(X)$ についても前回使った
\[ G(X) = (X-\alpha^0)(X-\alpha^1)(X-\alpha^2)(X-\alpha^3) \]
を使います（生成多項式はもう少し一般化できますが、そこは省略します）。$t$が大きくなると、この後に出てくる行列のサイズが大きくなりますが、原理は同じです。
送信するシンボル数を冗長化符号も含めて$N$とすると、符号多項式 $C(X)$ の次数は $N-1$ です。$C(X)$ はその作り方から生成多項式 $G(X)$ で整除できるので、
\[ C(\alpha^0) = C(\alpha^1) = C(\alpha^2) = C(\alpha^3) = 0 \]
が成り立ちます。
ここで、通信路上で誤りが生じて最大$2$シンボルの誤りが生じたとします。このとき受信した多項式 $Y(X)$ は、
\begin{eqnarray*}
Y(X) &=& C(X) + E(X) \\
E(X) &=& e_1X^{m_1} + e_2X^{m_2} \quad (\, 0 \le m_1 \le m_2 \le N-1\,)
\end{eqnarray*}
と表せます。この $E(X)$ が求まると $C(X)$ が復元できることになります。誤りシンボル数がちょうど$2$個なら $e_1 \neq 0, e_2 \neq 0, m_1 \neq m_2$ 、$1$個ならば $e_1 \neq 0, e_2=0$ 、$0$個ならば $e_1=e_2=0$ と考えます。
そこで、まずシンドロームと呼ばれる次の値を $Y(X)$ から計算します。なお、これから出てくる計算は当然ながら全て有限体 $F_{256}$ 上での四則演算です。
\begin{eqnarray*}
S_1 &=& Y(\alpha^0) &=& E(\alpha^0) &=& e_1+e_2 \\
S_2 &=& Y(\alpha^1) &=& E(\alpha^1) &=& e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
S_3 &=& Y(\alpha^2) &=& E(\alpha^2) &=& e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
S_4 &=& Y(\alpha^3) &=& E(\alpha^3) &=& e_1\alpha^{3m_1}+e_2\alpha^{3m_2}
\end{eqnarray*}
ここで、実際に生じた誤りのシンボル数を$k$個とし、まず $k=2$ と仮定します。そして誤り位置多項式を、
\[ \sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) = 1 + \sigma_1X + \sigma_2X^2 \]
と定義します。この $\sigma(X)$ の係数 $\sigma_1, \sigma_2$ が具体的に求まれば、
\[ \sigma(\alpha^{-m_1}) = \sigma(\alpha^{-m_2}) = 0 \tag{1} \]
かつ、上記以外の $\alpha^m$ に対しては $\sigma(\alpha^m) \neq 0$ なので、$m$を$0$から $-(N-1)$ まで動かして上記の代入計算をすれば誤り位置 $m_1,m_2$ が求まります。そこで $\sigma_1, \sigma_2$ の求め方ですが、上記$(1)$より
\begin{eqnarray*}
1 + \sigma_1\alpha^{-m_1} + \sigma_2\alpha^{-2m_1} &=& 0 \\
1 + \sigma_1\alpha^{-m_2} + \sigma_2\alpha^{-2m_2} &=& 0
\end{eqnarray*}
が成り立つので、変形すると
\begin{eqnarray*}
\alpha^{m_1}\sigma_1 + \sigma_2 &=& \alpha^{2m_1} \\
\alpha^{m_2}\sigma_1 + \sigma_2 &=& \alpha^{2m_2}
\end{eqnarray*}
になります（標数$2$なので係数の$-$は$+$に置き換えできます）。これは行列でかくと、
\begin{equation*}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
=
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\tag{2}
\end{equation*}
となります。
一方、シンドロームについて、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1\alpha^{m_1}+e_2\alpha^{m_2} & e_1+e_2 \\
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} & e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\tag{3}
\end{eqnarray*}
が成り立つので、これと$(2)$より、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
e_1\alpha^{3m_1}+e_2\alpha^{3m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
S_3 \\
S_4 \\
\end{bmatrix}
\tag{4}
\end{eqnarray*}
が得られます。$(3)$より行列式を計算すると、
\begin{equation*}
\begin{vmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{vmatrix}
=
\begin{vmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{vmatrix}
\begin{vmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{vmatrix}
= e_1e_2(\alpha^{m_2}-\alpha^{m_1})(\alpha^{m_1}-\alpha^{m_2}) \neq 0
\tag{5}
\end{equation*}
と$0$でなく、$S_1 \sim S_4$ は既知なので、$(4)$を解いて $\sigma_1, \sigma_2$ を求めることができます。
これから先述の方法で $m_1, m_2$ が求まるので、シンドロームの定義式から得られる、
\begin{equation*}
\begin{bmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
e_1 \\
e_2 \\
\end{bmatrix}
=
\begin{bmatrix}
S_1 \\
S_2 \\
\end{bmatrix}
\end{equation*}
を解いて $e_1, e_2$ を求めることができます。この計算も
\begin{equation*}
\begin{vmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{vmatrix}
= \alpha^{m_2}-\alpha^{m_1} \neq 0
\end{equation*}
と行列式が$0$でないので可能です。これで無事に $E(X)$ を求めることができたので、誤り訂正ができました。
誤りシンボル数が $k<2$ のときは、$(5)$の行列式が$0$になるのでその判定ができて、計算がもっと簡単になります。
ここまでWikipediaに載っていたピーターソン法について、その誤り訂正の原理を紹介しました。しかしこの方法は「訂正するシンボル数が多いときは計算量が増大するため大規模な復号には使えないという欠点がある」ということだそうです。
そこで以下、より計算量の少ない方法であるユークリッド法について、J-Stageから閲覧できる開発者である平澤らの論文を参考にして、簡単に紹介します。
誤りシンボル数の最大値は一般化して$t$とし、生成多項式を
\[ G(X) = (X - \alpha^0)(X - \alpha^1) \cdots (X - \alpha^{2t}) \]
として、これから生成された $N-1$ 次の符号多項式 $C(X)$ が送信され、受信側では$k$個 $(k \le t)$ のシンボルに誤りが生じた受信多項式 $Y(X)$ を受信したとします。誤り多項式 $E(X) = Y(X) - C(X)$ を
\[ E(X) = e_1X^{m_1} + e_2X^{m_2} + \cdots + e_kX^{m_k} \quad (\, 0 \le m_1 < m_2 < \cdots < m_k \le N-1\,)\]
とすると、誤り訂正の目的はこの $E(X)$ を具体的に求めることです。
まず、$Y(X)$ からシンドローム
\[ S_j = Y(\alpha^{j-1}) \quad (j=1,2, \cdots, 2t) \]
を計算し、これらを係数とする次のシンドローム多項式 $S(X)$ を定義します。
\[ S(X) = S_1 + S_2X + S_3X^2 + \cdots + S_{2t}X^{2t-1} \]
このとき、各シンドロームの値について、
\[ S_j = E(\alpha^{j-1}) = e_1\alpha^{(j-1)m_1} + e_2\alpha^{(j-1)m_2} + \cdots + e_k\alpha^{(j-1)m_k} \quad (j=1,2, \cdots, 2t) \]
が成り立つので、$S(X)$ は次のように変形できます。
\[ S(X) = \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \]
次に、誤り位置多項式 $\sigma(X)$ を次によって定義します。
\begin{equation*}
\sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) \cdots (1 - \alpha^{m_k}X)
\end{equation*}
ここまではピーターソン法と同じですが、ここで次の関係式
\begin{equation*}
(1 - \alpha^{m_i}X)(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) = 1 - \alpha^{2tm_i}X^{2t} \quad (i=1, \cdots, k)
\end{equation*}
が成り立つので、$\sigma(X)S(X)$ について、
\begin{eqnarray*}
\sigma(X)S(X) &=& \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \prod_{1 \le j \le k}(1 - \alpha^{m_j}X) \\
&=& \sum_{i=1}^k e_i(1 - \alpha^{2tm_i}X^{2t}) \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \\
&=& \phi(X)X^{2t} + \eta(X)
\end{eqnarray*}
すなわち
\[ \sigma(X)S(X) + \phi(X)X^{2t} = \eta(X) \tag{6} \]
と表せます。ここで $\eta(X)$ は
\[ \eta(X) = \sum_{i=1}^k e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \tag{7} \]
で定まる $k-1$ 次以下の多項式で、これを誤り数値多項式といいます。
従って、誤り訂正問題は既知の多項式 $S(X)$ と $X^{2t}$ から、$(6)$をみたす多項式 $\sigma(X)$ と $\eta(X)$ とを求める問題に帰着されることになります。これを解くには、$S(X)$ と $X^{2t}$ の最大公約多項式を求めるユークリッド互除法のアルゴリズムが使えます。これが「ユークリッド法」と名付けられている理由です。このアルゴリズムはピーターソン法に比べて高速です。
$\eta(X)$ の次数が $k-1$ 次以下で $k \le t$ を前提としているので、ユークリッド互除法の剰余多項式の次数が $t-1$ 以下になれば、そこで停止すれば良いことになります。
この方法で $\sigma(X)$ と $\eta(X)$ が具体的に求まれば、まず誤りシンボル数 $k$ は $\sigma(X)$ の次数であり、誤り位置 $m_i$ は $\sigma(X)$ からピーターソン法と同様に
\[ \sigma(\alpha^{-m_i}) = 0 \quad (i=1, \cdots, k) \]
をみたす$k$個の指数が最大$N$回の代入によって求まります。
誤り数値 $e_i$ については、$(7)$に $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入して、
\[ \eta(\alpha^{-m_i}) = e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \tag{8} \]
から求まりますが、計算をもっと簡単にするためには、$\sigma(X)$ の形式微分
\[ \sigma'(X) = - \sum_{i=1}^k \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \]
をとって、これに $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入すると、
\[ \sigma'(\alpha^{-m_i}) = \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \]
となるので、これと$(8)$より
\[ e_i = \frac{ \alpha^{m_i} \eta(\alpha^{-m_i}) }{ \sigma'(\alpha^{-m_i}) } \quad (i=1, \cdots, k) \]
によっても求まります。なお、$\sigma(X)$ の形式微分は具体的には、
\[ \sigma(X) = 1 + \sigma_1X + \sigma_2X^2 + \cdots + \sigma_kX^k \]
に対して
\[ \sigma'(X) = \sigma_1 + 2\sigma_2X + \cdots + k\sigma_kX^{k-1} \]
ですが、標数$2$なので$k$が偶数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_{k-1}X^{k-2} \]
$k$が奇数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_kX^{k-1} \]
となります。
以上で受信多項式 $Y(X)$ から誤り多項式 $E(X)$ が具体的に求められたので、誤り訂正ができました。
巧妙すぎて頭がクラクラしそうです。感動しました。
（続く）（前記事）
有限体の勉強 〜リード・ソロモン符号のシミュレーション〜 [数学]
有限体の勉強を始めてちょっとわかった気になってきましたが、ここで有限体の応用の一つである「誤り訂正符号」、その中でも誤り訂正能力が高い方式である「リード・ソロモン符号」について、その原理をシミュレートしてみたいと思います。
誤り訂正能力がどのくらい高いのかというと、
「送りたいシンボルに2t個の冗長なシンボルを追加するだけで、t個までならどのシンボルにどんな誤りが生じても正しく復元することができる」
というくらい高いのです。QRコードがある程度まで汚損しても正しく読み取れるのはこの符号方式を使っているからであり、他にもCDや衛星通信など様々な場面で使われています。
このリード・ソロモン符号については、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}$ の元はべき表現で扱うことを基本とするので、乗法演算は指数を足し合わせて$\mod 255$ をとることで行えます。加法演算はちょっと手間ですが、変換表を用いてベクトル表現にしてから各ビット毎にXORを取って、再び変換表を用いてべき表現にすれば求まります。実際にはこれらの計算は全部スプレッドシート上で関数を駆使して行いました。
では、実際に文字列 "Hello!" をリード・ソロモン符号で符号化し、通信路上で生じた誤りが受信側で復元できることを見てみましょう。以下ではWikipediaの記事の方法に従ってシミュレートします。
リード・ソロモン符号では、符号を $F_{256}$ の元を係数とする多項式で表します。"Hello!" の6文字をASCIIコード16進で表すと、
となりますが、これを $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$までのどのような数字を入れても、復号した緑のセルは元の青いセルの値が正しく表示されることが確認できると思います。
有限体の四則演算が自由自在にできることを利用した巧妙な符号化方式であることが実感できました。考えた人（リードさんとソロモンさん）は天才ですね。
（続く）（前記事）
誤り訂正能力がどのくらい高いのかというと、
「送りたいシンボルに2t個の冗長なシンボルを追加するだけで、t個までならどのシンボルにどんな誤りが生じても正しく復元することができる」
というくらい高いのです。QRコードがある程度まで汚損しても正しく読み取れるのはこの符号方式を使っているからであり、他にもCDや衛星通信など様々な場面で使われています。
このリード・ソロモン符号については、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$までのどのような数字を入れても、復号した緑のセルは元の青いセルの値が正しく表示されることが確認できると思います。
有限体の四則演算が自由自在にできることを利用した巧妙な符号化方式であることが実感できました。考えた人（リードさんとソロモンさん）は天才ですね。
（続く）（前記事）
有限体の勉強 〜位数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)$ を基底とする「ベクトル表現」との対応づけができます。これが次の表です。
この表の見方は、例えば上から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$ の原始元にならないので、原始多項式ではありません。既約多項式が原始多項式かどうかを係数から簡単に見分ける方法があるのかないのか、今の僕はその知見を持っていません。
（続く）（前記事）
なぜ $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$ の原始元にならないので、原始多項式ではありません。既約多項式が原始多項式かどうかを係数から簡単に見分ける方法があるのかないのか、今の僕はその知見を持っていません。
（続く）（前記事）
有限体の勉強 〜素体上の既約多項式への分解〜 [数学]
有限体のことを何も知らないので勉強を始めました。前回は標数2の有限体のうち、$F_2$ から $F_{16}$ までの加算乗算表を作るところまでやってみました。
この過程で見えてきたことを一つずつ検証してみます。
まず単純な話ですが、$F_2$ 上の多項式には次数$n$が何であっても必ず$n$次の既約多項式がある、という事実があります。$2$次ならば $X^2+X+1$ がそうですし、$3$次でも$4$次でもありました。これは標数が一般の素数$p$に対して成り立ちます。
このことを証明するために、有限体の位数（元の数）に関する基本的な定理をまず書いておきます。
（証明）$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)$ の形式微分は標数が$p$であることから $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} \]
という拡大体の系列ができていることがわかります。
これは一般に次の形で成り立ちます。
（証明）$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$ の分解については、次の特徴でまとめられることがわかります。
（証明）①は【定理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$だから、拡大 $F_{p^k}/F_p$ の次数$k$は $k \ge m$ をみたす。従って $k=m$ となるしかなく、$m \mid n$ が従うが、仮定より $m \nmid n$ なので矛盾である。
④については、もし $X^{p^m}-X$ が$1$次以上の多項式 $f(X)$ の平方を因子に持ったと仮定すると、
\[ X^{p^m}-X = f(X)^2g(X) \]
と表され、この両辺を形式微分すると標数が$p$であることから、
\[ -1 = f(X)(2f'(X)g(X)+f(X)g'(X)) \]
となって矛盾を生じる。
□
$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$に対して次のように証明できます（既約多項式でなくても成立します）。
（証明）$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*}
のようにそれぞれの既約多項式の中で巡回することがわかります。
これでとりあえず前回の記事に関する検証ができたし、これ以上書くとボロが出るので、この辺までにしておきます。
（続く）（前記事）
この過程で見えてきたことを一つずつ検証してみます。
まず単純な話ですが、$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)$ の形式微分は標数が$p$であることから $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$の既約多項式を因子に持たない。
④ $X^{p^n}-X$ は$1$次以上の多項式の平方を因子に持たない。
① $n$の全ての約数$m$に対し、$X^{p^n}-X$ は $X^{p^m}-X$ を因子に持つ。
② $n$の全ての約数$m$に対し、$X^{p^n}-X$ は次数$m$の全ての既約多項式を因子に持つ。
③ $m$が$n$の約数でなければ、$X^{p^n}-X$ は次数$m$の既約多項式を因子に持たない。
④ $X^{p^n}-X$ は$1$次以上の多項式の平方を因子に持たない。
（証明）①は【定理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$だから、拡大 $F_{p^k}/F_p$ の次数$k$は $k \ge m$ をみたす。従って $k=m$ となるしかなく、$m \mid n$ が従うが、仮定より $m \nmid n$ なので矛盾である。
④については、もし $X^{p^m}-X$ が$1$次以上の多項式 $f(X)$ の平方を因子に持ったと仮定すると、
\[ X^{p^m}-X = f(X)^2g(X) \]
と表され、この両辺を形式微分すると標数が$p$であることから、
\[ -1 = f(X)(2f'(X)g(X)+f(X)g'(X)) \]
となって矛盾を生じる。
□
$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*}
のようにそれぞれの既約多項式の中で巡回することがわかります。
これでとりあえず前回の記事に関する検証ができたし、これ以上書くとボロが出るので、この辺までにしておきます。
（続く）（前記事）
有限体の勉強 〜標数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}$ なので、その加算表と乗算表は次のようになります。
(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 \]
と表し、「ベクトル表現」と呼びます。このベクトル表現を用いて加算表、乗算表を作ると、次のようになります。
ここで加算表を作るのは、単にベクトル空間における加算なので、それぞれの係数を $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)$ としたベクトル表現で加算表と乗算表を作ることを考えます。加算表は簡単で、次のようになります。
乗算表についても地道に計算して $\alpha^3 = \alpha+1$ を使って $\alpha$ の$3$次以上の項を消せばよいのですが、なにぶん埋めるべきマスの数が多いのでとても面倒です。もうちょっと楽をすることを考えます。
実は $F_8$ の元のうち$0$を除いた$7$個については、$\alpha$ のべき乗との間に次の関係があります。
これくらいの計算はまだ頑張る気になる範囲です。これを見ると、$\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$の行と列を付け加えると、次の乗算表が出来上がります。
これで $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)$ としたベクトル表現で、まず加算表を作ると次のようになります。
乗算表を作るために、$F_8$ でやったのと同様に、$\alpha$ のべき表現とベクトル表現との対応表を作ります。
$F_{16}^\times$ の位数は$15$なので $\alpha^{15} = 1 = \alpha^0$ です。すなわち $\alpha$ の指数は $\mod 15$ で計算すればよいわけです。$F_8$ でやったのと同様にべき表現での乗算表をEXCELなどのスプレッドシートで作り、それをベクトル表現に置き換えて$0$の行と列を追加すると、次のように $F_{16}$ の乗算表が出来上がります。
これで $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に変換したものです。サイトの作成者様に感謝いたします。）
（続く）
有限体とは文字どおり、有限個の元で構成される体（四則演算が定義された代数系）のことですが、これについては、
① 有限体の位数（元の数）$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に変換したものです。サイトの作成者様に感謝いたします。）
（続く）
