\(\newcommand{\zettaiti}[1]{\lvert #1 \rvert} \newcommand{\field}[1]{\mathbb{#1}} \newcommand{\Q}{\field{Q}} \newcommand{\rnsg}{\vartriangleright}\)
組成列の計算
前記事での「退職後は素人数学者」さんの考察を見て、組成列の計算法について改めて考えてみました。
「退職後は素人数学者」さんのアルゴリズムだと、組成列 \[ G_{0} \rnsg G_{1} \rnsg \dots \] を計算する際、単位群が現れるまでは、どの \(G_{k}\) に対しても改めてその正規部分群全てを計算し直すことになります。しかし、どの \(G_{k}\) の（正規）部分群も、最初の群 \(G_{0}\) の部分群です。
したがって、一連の計算では、最初に \(G_{0}\) の部分群を全部求めておけば、後はそれを再利用することができます。
それから、正規部分群については、このアルゴリズムでは小さい方から順にすべての正規部分群を作っていますが、どうせ欲しいのは「最大の」正規真部分群だけなので、真部分群のうち要素数が大きい方から順に試していって、最初に正規部分郡になっているものを次の \(G_{k}\) にする、というやり方の方が手っ取り早い気がします。
上のふたつの考えを合わせると、次のようなアルゴリズムになります。
- \(G_{0}\) の部分群をすべて求め、要素数が多い順にソートしたリストを \(L\) とする。
- \(k=0\) とする。
- 以下のように、部分群が正規部分郡になっているかを順に試していく。
- \(\zettaiti{G_{k}}=1\) なら終了。
- \(H\) を \(L\) の先頭の要素とし、\(L\) からはその \(H\) を捨てる（\(L\) の長さは \(1\) 減る）。
- \(\zettaiti{H} > \zettaiti{G_{k}}/2\) ならば ii へ戻る。
- \(\zettaiti{H}\) が \(\zettaiti{G_{k}}\) を割り切らなければ ii へ戻る。
- \(H \subset G_{k}\) でなければ ii へ戻る。
- \(\forall g \in G_{k}, gHg^{-1} \subset H\) ならば \(G_{k+1}\) を \(H\) とし、\(k\) を \(1\) 増やして i へ戻る。そうでなければ ii へ戻る。
このアルゴリズムの場合、最初に \(G_{0}\) に対して正規部分群とは限らない群も含めてすべての部分群を求めることになるので、\(G_{0}\) が正規部分群でない部分群を極めて大量に持つときは、「退職後は素人数学者」さんのアルゴリズムより効率が劣ることもあるでしょう。ただ、そう極端な状況でなければ、おそらくこちらの方が速く動くのではないか、と期待しています。
とは言っても、「可解な方程式の解の具体形をべき根で表す」という処理全体の中では、組成列の計算時間が占める割合は大したことないでしょうから、ここの最適化をあんまりがんばっても意味は乏しいでしょうが…。
蛇足ですが、目標として「方程式が可解だった場合に解をべき根で表す」以上のことをまったく追求しないのであれば、上の手順で \(G_{k+1}\) が求まった段階で、\(\zettaiti{G_{k}}/\zettaiti{G_{k+1}}\) が素数でなければそこで処理を打ち切り、「ガロア群が可解でなかったので解をべき根で表すことはできない」と表示して終了する（組成列を最後まで求める必要はない）、というプログラムでも構わないですね。
最小多項式の因数分解
ehito さんが http://ehito.hatenablog.com/entry/2019/04/11/193241 で書かれたアイディアによって、べき根の添加で \(g_{k-1}(x)\) から \(g_{k}(x)\) を求める計算がさらにシンプルにできることがわかりました。その技法中で現れる「解が一意に定まらない連立 \(1\) 次方程式」の解の不定性が結果に影響せずうまく正しい式が得られるメカニズムについて、コメント欄での ehito さんとのやりとりで教えていただいたことも含めて、以下簡単な解説を書きます。
ガロア群が \(6\) 次巡回群になる方程式\[ f(x) = x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1 = 0 \]を例に取って説明します。
この方程式の解は \(1\) の原始 \(7\) 乗根全体で、最小分解体を作る原始元は \(V = \alpha_{1}\) とおくことができます。解のすべてを \(V\) で表す式は、当然ながら
\begin{align*} \alpha_{1}&=V^{1}&\qquad \alpha_{4}&=V^{4} \\ \alpha_{2}&=V^{2}&\qquad \alpha_{5}&=V^{5} \\ \alpha_{3}&=V^{3}&\qquad \alpha_{6}&=V^{6} \end{align*}となります。\(V\) の \(\Q\) 上の最小多項式は \(g(x)=f(x)\) そのものです。
ガロア群は上述の通り \(6\) 次巡回群で、その生成子 \(\sigma\) は\[ \sigma\colon V \mapsto V^{3} \]から誘導される \(\Q\) 同型写像です。実際、\(\sigma\) を繰り返し作用させると\[ \underbrace{V}_{V_{1}} \mapsto \underbrace{V^{3}}_{V_{2}} \mapsto \underbrace{V^{2}}_{V_{3}} \mapsto \underbrace{V^{6}}_{V_{4}} \mapsto \underbrace{V^{4}}_{V_{5}} \mapsto \underbrace{V^{5}}_{V_{6}} \mapsto V \]となって \(6\) 回で（初めて）元に戻ります。また、この計算から、\(\sigma\) は解（の添字）に対する置換としては\[ \sigma = (1\quad 3\quad 2\quad 6\quad 4\quad 5) \]という巡回置換です。\(G = \langle \sigma \rangle\)
組成列としては\[ \underbrace{G}_{G_{0}} \rnsg \underbrace{\{e, \sigma^{3}\}}_{G_{1}} \rnsg \underbrace{\{e\}}_{G_{2}} \]を取りましょう。※ \(G_{1}\) は \(G_{0}\) の最大の正規真部分群ではありませんが、組成列にはなっているので問題はありません。
最初に、以前の説明通り、適当な \(1\) のべき根を添加するのですが、この例の場合はその添加をするかどうかは以後の話に影響しないので、ここでは省略します。いきなり \(g_{0}(x) = g(x) = x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\) をべき根で因数分解しましょう。この場合\begin{align} \label{eq:galois-sol11-5} h_{0}(x) &= (x-V_{1})(x-V_{4}) = x^{2} – (V+V^{6})x + 1 = x^{2} + (1+V^{2}+V^{3}+V^{4}+V^{5})x + 1 \\
h_{1}(x) &= (x-V_{2})(x-V_{5}) = x^{2} – (V^{3}+V^{4})x + 1 \notag\\
h_{2}(x) &= (x-V_{3})(x-V_{6}) = x^{2} – (V^{2}+V^{5})x + 1 \notag
\end{align}
なので、\(\omega\) を \(1\) の原始 \(3\) 乗根として
\begin{align}
\theta_{1}(x) &= h_{0}(x) + \omega h_{1}(x) + \omega^{2} h_{2}(x) \notag\\
&= (1+\omega+\omega^{2})(x^{2}+1) + \bigl(1+V^{2}+V^{3}+V^{4}+V^{5} – \omega(V^{3}+V^{4}) – \omega^{2}(V^{2}+V^{5})\bigr)x \notag\\
&= \bigl(1 + (\omega + 2)(V^{2}+V^{5}) + (1-\omega)(V^{3}+V^{4})\bigr)x
\label{eq:galois-sol11-1}\end{align}となります。
ehito さんの技法では、\(\theta_{1}(x)\)〜\(\theta_{p-1}(x)\) をすべて求める必要はありません。それらのうち、ゼロ多項式でないものがひとつ見つかれば OK です。上の例では \(\theta_{1}(x)\) の \(2\) 次と \(0\) 次の項は \(0\) になってしまいましたが、\(1\) 次の項が消えずに残っています。なので \(\theta_{2}(x)\) はもう求める必要はないのです。このようにして見つかった、 \(0\) でない任意の係数を \(r\) とおきます。
\begin{equation}
\label{eq:galois-sol11-2}
r = 1 + (\omega + 2)(V^{2}+V^{5}) + (1-\omega)(V^{3}+V^{4})
\end{equation}
\(\theta_{1}(x)\) の作り方から、その任意の係数は \(\sigma\) で \(\omega^{-1}\) 倍になるので、\eqref{eq:galois-sol11-2}の右辺では \(V\) は必ず消えずに残ります。
一方、やはり \(\theta_{1}(x)\) の作り方から、\(r\) は \(3\) 乗すると \(V\) が消えます（\(g_{0}(V)=0\) を使って次数下げすれば）。また、当然ながら \(r,
r^{2}(=r^{p-1})\) からは \(V\) は消えずに残ります（つまり、\(3\) 乗して初めて \(V\) が消える）。実際に計算してみると、
\begin{align}
\label{eq:galois-sol11-3}
r^{2} &= 3\omega + 1 + (5\omega+4)(V^{2}+V^{5}) +
(4\omega-1)(V^{3}+V^{4}) \\
\label{eq:galois-sol11-4}
r^{3} &= 7(3\omega+1)
\end{align}
です（\(g_{0}(V)=0\) と \(\omega^{2}+\omega+1=0\) を使った）。
すると、まず\eqref{eq:galois-sol11-4}より \(r\) が\[ r = \sqrt[3]{7(3\omega+1)} \]とべき根で求まります。これは目新しい話ではありません。今まで通りです。
一方、\eqref{eq:galois-sol11-2}, \eqref{eq:galois-sol11-3}で \(V^{1}\)〜\(V^{5}\) を形式的に別個の未知数と見ると連立 \(1\) 次方程式となります。この連立方程式は、式の数が \(2\) 本なのに「未知数」の個数が \(5\) なので解は一意に定まりません。しかし、その解を\eqref{eq:galois-sol11-5}に代入して \(h_{0}(x)\) を求めてみると、結果はその不定性に影響されず一意に定まります。
その理由は、今の例に特化して説明すると、\eqref{eq:galois-sol11-2}, \eqref{eq:galois-sol11-3}に \(V\) が \(V^{2}+V^{5}\)、\(V^{3}+V^{4}\) の形のみを通じて含まれていて、\eqref{eq:galois-sol11-5}にも \(V\) はそれらの形を通じてしか含まれていないから、と言えます。実際、\eqref{eq:galois-sol11-2}, \eqref{eq:galois-sol11-3}は \(V^{2}+V^{5}\), \(V^{3}+V^{4}\) について次のように解けます。\begin{gather*} \begin{pmatrix} \omega+2 & 1-\omega \\ 5\omega+4 & 4\omega-1 \end{pmatrix} \begin{pmatrix} V^{2}+V^{5} \\ V^{3}+V^{4} \end{pmatrix} = \begin{pmatrix} r-1 \\ r^{2}-1-3\omega \end{pmatrix} \\ \therefore \begin{pmatrix} V^{2}+V^{5} \\ V^{3}+V^{4} \end{pmatrix} = \begin{pmatrix} \omega+2 & 1-\omega \\ 5\omega+4 & 4\omega-1 \end{pmatrix}^{-1} \begin{pmatrix} r-1 \\ r^{2}-1-3\omega \end{pmatrix} \end{gather*}
これより、\eqref{eq:galois-sol11-5}を使うと、\(h_{0}(x)\) が \(r\) と \(\omega\) だけを使って求められます。
今の、連立方程式の解の不定性に結果が影響されない理由を一般的に説明しましょう。今、\(g(x)\) の因数分解が \(g_{k-1}(x)\) まで進んでいて、その段階での体が \(K\) だったとしましょう。このとき、\(h_{0}(x)\) の任意の係数 \(C\) は \(V\) の \(K\) 係数多項式として表されています。\(g_{k-1}(V)=0\) を使って次数下げすれば、この表し方は一意的です。\begin{align}
C &= a + bV + cV^{2} + \dotsb \quad (a,b,c, \dotsc \in K) \notag\\
&= \underbrace{(a \quad b\quad c\quad \dots)}_{\boldsymbol{a}} \underbrace{\begin{pmatrix} 1 \\ V \\ V^{2} \\ \vdots \end{pmatrix}}_{\boldsymbol{V}} = \boldsymbol{a} \boldsymbol{V}
\label{eq:galois-sol11-6}
\end{align}（\(\boldsymbol{a}\) の成分はすべて既知）
そして、この \(C\) は、\(r\) の \(K\) 係数多項式としても表されることが解っています。\begin{align}
C &= s + tr + ur^{2} + \dotsb \quad (s,t,u, \dotsc \in K) \notag\\
\label{eq:galois-sol11-7}
&= \underbrace{(s\quad t\quad u\quad \dots)}_{\boldsymbol{s}} \underbrace{\begin{pmatrix} 1 \\ r \\ r^{2} \\ \vdots \end{pmatrix}}_{\boldsymbol{r}} = \boldsymbol{s} \boldsymbol{r}
\end{align}（\(\boldsymbol{s}\) の成分をこれから求めたい）
そして、\eqref{eq:galois-sol11-2}, \eqref{eq:galois-sol11-3}に当たる式が解っています。つまり、\(r, r^{2}, \dots, r^{p-1}\) を \(V\) の \(K\) 係数多項式として表した式が手元にあります。
\[ \begin{cases}
r &= \square + \square V + \square V^{2} + \dotsb \\
r^{2} &= \triangle + \triangle V + \triangle V^{2} + \dotsb \\
r^{3} &= \dots \\
\dots \end{cases} \]
つまり\begin{align}
\begin{pmatrix}
1 \\ r \\ r^{2} \\ \vdots
\end{pmatrix} &=
\underbrace{\begin{pmatrix}
1 & 0 & 0 & \dots \\
\square & \square & \square & \dots \\
\triangle & \triangle & \triangle & \dots \\
\dots & \dots & \dots & \dots\\ \end{pmatrix}}_{\boldsymbol{M}}
\begin{pmatrix}
1 \\ V \\ V^{2} \\ \vdots
\end{pmatrix} \notag\\
\therefore \boldsymbol{r} &= \boldsymbol{M} \boldsymbol{V}
\label{eq:galois-sol11-8}\end{align}です。（\(\boldsymbol{M}\) の成分はすべて \(K\) の数として既知）
\eqref{eq:galois-sol11-8}を\eqref{eq:galois-sol11-7}に代入すると
\[ C = \underbrace{\boldsymbol{s} \boldsymbol{M}}_{K \text{成分}}
\boldsymbol{V} \]
です。これと\eqref{eq:galois-sol11-6}を比較し、\eqref{eq:galois-sol11-6}の一意性を使うと
\begin{equation}
\label{eq:galois-sol11-9}
\boldsymbol{s} \boldsymbol{M} = \boldsymbol{a}
\end{equation}
が言えます。
以上の準備のもとで、\eqref{eq:galois-sol11-8}を形式的に \(V, V^{2}, \dotsc\) に対する連立方程式と見た時の解の任意のひとつを \(U_{1}, U_{2}, \dotsc\) としましょう。つまり \(U_{1}, U_{2}, \dotsc\) は
\begin{equation}
\label{eq:galois-sol11-10}
\boldsymbol{r} = \boldsymbol{M} \underbrace{\begin{pmatrix}
1 \\ U_{1} \\ U_{2} \\ \vdots
\end{pmatrix}}_{\boldsymbol{U}}
\end{equation}
をみたす数です。この \(\boldsymbol{U}\) を、\(\boldsymbol{V}\) の代わりに \eqref{eq:galois-sol11-6}の右辺に代入すると
\begin{align*} \boldsymbol{a} \boldsymbol{U} &= \boldsymbol{s} \boldsymbol{M} \boldsymbol{U} \quad (\because \eqref{eq:galois-sol11-9}) \\ &= \boldsymbol{s} \boldsymbol{r} \quad (\because \eqref{eq:galois-sol11-10}) \\ &= C \quad (\because \eqref{eq:galois-sol11-7}) \end{align*}
となって正しく \(C\) が得られます。
つまりこういうことです。\(U_{1}, U_{2}, \dots\) は、実際には \(r\) の \(K\) 係数多項式として手に入るわけですが、\(\boldsymbol{s}\) の成分の具体的な値を知らず、\(\boldsymbol{a}\) の成分だけを知っている段階であっても、\(\boldsymbol{a} \boldsymbol{U}\) を整理するだけで\eqref{eq:galois-sol11-7}の形の式が得られ、結果として \(\boldsymbol{s}\) の成分の具体的な形が得られる、というわけです。
以上のことが、\(h_{0}(x)\) の任意の係数 \(C\) に対してなりたつので、これによって \(g_{k}(x) = h_{0}(x)\) が \(K[r]\) 係数多項式として具体的に求まるわけです。
コメントを残す