数式処理ソフトによる～その15 & 新・方程式のガロア群の求め方

$\newcommand{\Q}{\mathbb{Q}}$
これまで、与えられた方程式のガロア群を求めたり、可解な方程式の解をべき根で表すことをテーマにして一連の記事を書いてきた。本記事では、その過程にグレブナー基底を利用する方法とその数学的背景、及びガロア群を求める新しいやり方を解説する。後者は、これまで非常に重かった計算をだいぶ軽減できると期待できる………と元々は思っていたのだが、前記事で「退職後は素人数学者」さんが従来の手法での計算時間の大幅な短縮を実現されていたので、そちらでの意義はあんまりないかもしれない（笑）。

グレブナー基底の概観

グレブナー基底を求めることで何が得られるかを、ここでの私たちの目的に沿った形で言うと「連立方程式を同値変形で解いた解」が得られる。例えば、連立方程式
\begin{equation} \label{eq:howtocomputegaloisgroup-new-6}\begin{cases}
2x+3y-12 &= 0 \\
x-y-1 &= 0
\end{cases} \end{equation}
をグレブナー基底を使って解きたいとしよう。Wolfram Alphaを使うなら、
GroebnerBasis[{2*x+3*y-12,x-y-1},{x,y}] と入力する。すると、「結果」には {y-2, x-3} と表示されるだろう。

maxima では、標準ではグレブナー基底が使えるようにはなっていないので、まず拡張機能としてロードする。大抵は wxmaxima を通じて maxima を使っているだろうから、
load("grobner")$
までタイプしたら Enter ではなく Shift キーを押しながら Enter（あるいは、Control キーを押しながら Enter）を入力する。数秒待つとロードが終わってグレブナー基底関連のコマンド・関数が使えるようになる（一度ロードした後は、その maxima を終了するまでは再度ロードする必要はない。一度終了して、再度 maxima を起動したら、ふたたびロードする必要がある）。

そうしたら
poly_reduced_grobner([2*x+3*y-12,x-y-1],[x,y]);
とタイプして Shift+Enter で
[y-2,x-3]
が得られる。

大体見当がついたろうが、結果の {y-2, x-3} や [y-2,x-3] が求まったグレブナー基底で、これが上記の連立方程式の解が $x=3$, $y=2$ であることを表している。

また、入力に現れた 2*x+3*y-12,x-y-1 は、解きたい連立方程式の左辺である。それらをコンマで区切り、Wolfram Alpha なら {} で、maxima なら [] でくくったものが第1引数になる。第2引数は {x,y} や [x,y] になっているが、これらは当面「どの文字を未知数と見るか」の指定だと思っておけばよい。実はこの順番にも意味があるが、それについてはまた後で説明する。

今述べた通り入力は連立方程式から「$=0$」を除いた残りだったわけだが、結果の {y-2, x-3} や [y-2,x-3] には逆に「$=0$」を追加することで、$x=3$, $y=2$ という解が得られるわけだ。

このように、$2x+3y-12$, $x-y-1$ のグレブナー基底を求めた結果が $y-2$, $x-3$ になったが、グレブナー基底というものの著しい特徴は、これらに「$=0$」を補った式が連立方程式としては必ず同値変形になるということである。
\[ \eqref{eq:howtocomputegaloisgroup-new-6} \iff
\begin{cases}
y-2 &= 0 \\
x-3 &= 0
\end{cases} \]
今の場合、元の方程式が未知数について $1$ 次だったので同値性は別に驚くようなことではないが、グレブナー基底のすごい所は次数によらず同値な結果が得られるという点である（具体例はすぐ後で）。

「同値性が確実に保証された式変形」なんて高度な処理が、「任意の」連立方程式に対して可能なはずはない。グレブナー基底で扱える方程式は、未知数について「多項式で」表される形の連立方程式に限られる。

例えば
\[ \begin{cases}
x^{2} + y^{2} &= 2 \\
2x-y &= 1
\end{cases} \]
を解かせると、Wolfram Alpha なら GroebnerBasis[{x^2+y^2-2,2*x-y-1},{x,y}] と入力した結果
{5 y^2 + 2 y - 7, 2 x - y - 1} となって、maxima なら（入力と出力を並べて書くと）
poly_reduced_grobner([x^2+y^2-2,2*x-y-1],[x,y]);
[-y+2*x-1,5*y^2+2*y-7]
となる。つまり、上の連立方程式を
\[ \begin{cases}
5y^2+2y-7 &= 0 \\
2x-y-1 &= 0
\end{cases} \]
に同値変形してくれたわけだ。

ここで、「同値変形」とは言っても結果はあくまで「多項式の形」でしか与えてくれないので、「$(x,y) = (1,1) \text{ or } (x,y) = (-\dfrac{1}{5}, -\dfrac{7}{5})$」のような「親切な」結果にまでしてくれるわけではない。結果に現れる $y$ だけの $2$ 次方程式 $5y^{2}+2y-7=0$ を解いて $y=1 \text{ or } y=-\dfrac{7}{5}$ を導き、$2x-y-1=0$ と合わせて $x$ も求めるのは人間が行う（あるいは、グレブナー基底以外の手法にバトンタッチして数式処理ソフトに求めさせる）必要がある。

こういったグレブナー基底を求める機能が、ガロア群を求めたり、可解な方程式をべき根で解いたりする私たちの目的にどのように有効なのか、引き続き見ていこう。グレブナー基底について説明すべきことはまだある（例えば、上で触れた「未知数指定の指定順の意味」など）が、それは以下の説明の中のしかるべき個所で取り上げることにする。

従来の手法をグレブナー基底で

拡大体での商の計算

可解な方程式の解をべき根で表そうとした場合、「退職後は素人数学者」さんの元々のアルゴリズム（私が勝手に「アルゴリズムA」と名付けたもの）では、方程式によっては「べき根の選び方の不定性によって、$0$ になる可能性もならない可能性もある式」が分母に現れ、これが問題を引き起こしていた。この問題はグレブナー基底を用いると回避できるようになり、jurupapa さんの改訂版のプログラムではオプションで利用できるようになっている。その動作原理を見ていこう。

以前の記事では、$r^{2}+3=0$, $\omega^{2}+\omega+1=0$ をみたす $r$, $\omega$ に対して、$\dfrac{1}{2\omega + 1 + r}$ がうまく処理できない、という例を挙げた。これは、グレブナー基底で「分母の有理化」を行うことで解決できる。具体的には
http://maxima.hatenablog.jp/entry/2019/01/21/011356
での ehito さんのコメントの通りだが、使っている文字をこちらに合わせ、数学的背景を交えながら説明する。

やりたいことは、要するに
\begin{equation}
\label{eq:howtocomputegaloisgroup-new-1}
\begin{cases}
r^{2} + 3 &= 0 \\
\omega^{2}+\omega+1 &=0 \\
(2\omega+1+r)x &=1
\end{cases}
\end{equation}
を連立させ、これを $r$, $\omega$, $x$ を未知数とする連立方程式と見なして解く、ということになる。ここで、グレブナー基底が扱えるのは未知数について「多項式の」形の連立方程式だけだった、という制限を考慮し、第３の式では $x=\dfrac{1}{2\omega+1+r}$ の分母を払った形にしてある。

一見、第３の式には意味がなさそうにも思える。未知数 $x$ を増やした所で論理構造が変わるわけでなく、登場する文字を意味なく増やして複雑化しただけのようにも見えるからだ。しかし、グレブナー基底を応用する際は、このように「扱いたい値を表すためだけに新しく未知数をおく」ということがしばしば有力な手段になるのだ。これは、以下の話を読み進めれば自然に見てとれるだろう。

さて、\eqref{eq:howtocomputegaloisgroup-new-1}をグレブナー基底を用いて同値変形しよう。$\omega$ は $w$ で代用する。Wolfram Alpha だったら
GroebnerBasis[{r^2+3,w^2+w+1,(2*w+1+r)*x-1}, {x,w,r}] と入力し、（グレブナー基底の拡張機能ロード済みの）maxima だったら
poly_reduced_grobner([r^2+3,w^2+w+1,(2*w+1+r)*x-1], [x,w,r]);
と入力することになる。結果はそれぞれ {r^2 + 3, -r + 2 w + 1, r + 6 x},[r^2+3,2*w-r+1,-6*x-r] となり、次の同値変形が得られた。
\[ \eqref{eq:howtocomputegaloisgroup-new-1} \iff
\begin{cases}
r^{2} +3 &= 0 \\
2\omega+1-r &=0 \\
r+6x &= 0
\end{cases} \]
結果の第３式は $x=-\dfrac{r}{6}$ となることを意味している。さらに第２式も考えに入れれば、べき根の選び方として $2\omega+1-r=0$ が選択されており、このもとで $\dfrac{1}{2\omega+1+r} = -\dfrac{r}{6}$ となることが導かれたことになる。要するに、グレブナー基底を用いて「分母の有理化」ができたわけだ。なぜ都合よく「分母の有理化」を行った結果が導けたのかというと、ここが実は「変数指定の指定順」がキーになるポイントなのだが、詳しくは後で説明する。

ここではまず、次のような疑問に先に答えておこう。「元々 $\dfrac{1}{2\omega+1+r}$ を考えていたときは、分母が $0$ になる可能性があったから、正しく処理するなら
\begin{equation}
\label{eq:howtocomputegaloisgroup-new-2}
\frac{1}{2\omega+1+r} =
\begin{cases}
-\frac{r}{6} & (\text{$2\omega+1+r \ne 0$のとき}) \\
\text{値を持たない} & (\text{$2\omega+1+r = 0$のとき})
\end{cases}
\end{equation}
となるという話だったのでは？$\text{分母}=0$ の可能性はどこに行った？その可能性を勝手に無視しているということは、これは正しい同値変形になっていないのでは？」この疑問に対しては、\eqref{eq:howtocomputegaloisgroup-new-1}で $x$ を含む式を、予め分母を払った形で与えていた点に注意しよう。Wolfram Alpha や maxima は、$(2\omega+1+r)x =1$ を予め与えられた条件として処理を開始するわけだから、この時点で $2\omega+1+r \ne 0$ という条件も暗黙のうちに与えられていたことになる。つまり、数式処理ソフトが何か不正な処理を行ったわけではなく、上の変形は確かに同値変形になっている。

すると次に出てくる疑問はこうだろう。「それは結局人間が入力を数式処理ソフトに与える段階で『$\text{分母}=0$』の可能性を勝手に排除してしまっただけということだが、そんなことをしてはまずいのでは？」そう、一般に「$r^{2}+3=0$ かつ $\omega^{2}+\omega+1=0$ のもとで、$\dfrac{1}{2\omega+1+r}$ の値を知りたい」という問に対する純粋な答そのものとしては、この結果は不十分で、「フルの結果」\eqref{eq:howtocomputegaloisgroup-new-2}に比べて欠落がある。しかし、今考えている「$g(x)$ の逐次因数分解」という文脈では、これは問題にならない。そのことは、$\dfrac{1}{2\omega+1+r}$ タイプではなく、実際に現れる $\dfrac{r(2\omega+1)-3}{2\omega+1+r}$ タイプ、すなわち「$\frac{0}{0}$ 型不定形」が出現するタイプの方を題材に後の方でまた解説する。

その前に一旦、先ほど述べた「分母の有理化」と「変数の指定順」の関係について説明しておく。グレブナー基底を使うと一般に「分母の有理化」が可能で、それは次のようにすればいい。例えば、$\dfrac{1}{\sqrt{2}+\sqrt{3}}$ の分母の有理化がしたいとしよう。これは、$x^{2}=2$, $y^{2}=3$ をみたす数に対し $z=\dfrac{1}{x+y}$ を簡約化したいということと同じだが、これを連立方程式として捉え、
\begin{equation}
\label{eq:howtocomputegaloisgroup-new-3}
\begin{cases}
x^{2} -2 &= 0 \\
y^{2} -3 &= 0 \\
z(x+y) -1 &= 0
\end{cases}
\end{equation}
と表してみる。これをグレブナー基底を使って同値変形するのだが、ここでは変数の指定順が重要だ。指定順を $x,y,z$ にすると
\[ \eqref{eq:howtocomputegaloisgroup-new-3} \iff
\begin{cases}
2 x + z^3 – 9 z &=0 \\
2 y + z^3 – 11 z &=0 \\
z^4 – 10 z^2 + 1 &=0
\end{cases} \]
となってうまく行かない（Wolfram Alpha なら GroebnerBasis[{x^2-2,y^2-3,z*(x+y)-1}, {x,y,z}] 、maxima なら poly_reduced_grobner([x^2-2,y^2-3,z*(x+y)-1], [x,y,z]);）ここは指定順を $z,x,y$ の順にするとうまく行って、 \[ \eqref{eq:howtocomputegaloisgroup-new-3} \iff \begin{cases} x^2 – 2 &= 0 \\ y^2 – 3 &= 0 \\ x – y + z &= 0 \end{cases} \]
となり、第３式が $z=y-x$ と変形できることから $\dfrac{1}{\sqrt{2}+\sqrt{3}} = \sqrt{3} – \sqrt{2}$ の「分母の有理化」ができていることがわかる（Wolfram Alpha なら GroebnerBasis[{x^2-2,y^2-3,z*(x+y)-1}, {z,x,y}] 、maxima なら poly_reduced_grobner([x^2-2,y^2-3,z*(x+y)-1], [z,x,y]);）。

なぜ「変数の指定順」を変えるとうまく行くかと言うと、実はこの順序は、同値変形を行う上での「変数を消去する優先順位」の指定になっているからだ（※ 本当は、これは多変数多項式の「先頭項」を決めるための「単項式順序」というものを指定しているのだが、グレブナー基底を「連立方程式の同値変形」のツールとしてのみ見ている今の私たちの立場だと、それは結果的に「変数を消去する優先順位」を指定しているのと同じことになる、と理解すればよい）。つまり、最初の「$x,y,z$」の順序だと、「得られる式ではなるべく $x$ が、続いて $y$ が消去されている形にせよ。$z$ は消去されず多くの式に残ってしまっていてもいい」と要求したことになっている。その結果「$x$, $y$ を含まず $z$ だけが含まれる式 $z^4 – 10 z^2 + 1 =0$」が結果に含まれた。これだと「$z$ を $x$, $y$ で表す式」は得られない。

一方、ふたつ目の「$z,x,y$」の順序では「なるべく $z$ を消去することが優先。$x$, $y$ の消去はその後」という要求になっている。このため、結果の式で $x^{2}=2$, $y^{2}=3$ は $z$ を含まない形でそのまま残り、残る $z$ を含む式は $x$, $y$ が平気で残る…つまり $z$ を $x$, $y$ で表せる形の式となった。それが、結果として「分母の有理化」を行ったのと同じことになったわけである。

これで、先ほどの\eqref{eq:howtocomputegaloisgroup-new-1}をグレブナー基底で処理するときに変数の指定順を「$x,\omega,r$」にした理由がわかったろう。分母を有理化したい $x$ を最優先で消去する指定順にしたため、有理化がうまく行ったのである。

さて、引き続き $\dfrac{r(2\omega+1)-3}{2\omega+1+r}$ タイプの商をグレブナー基底で処理する話に移る。今度は、連立方程式は
\[ \begin{cases}
r^{2} + 3 &= 0 \\
\omega^{2}+\omega+1 &= 0 \\
(2\omega+1+r)x &= r(2\omega+1)-3
\end{cases} \]
となる。Wolfram Alpha なら GroebnerBasis[{r^2+3,w^2+w+1,(2*w+1+r)*x-(2*r*w+r-3)},{x,w,r}]、maxima なら poly_reduced_grobner([r^2+3,w^2+w+1,(2*w+1+r)*x-(2*r*w+r-3)],[x,w,r]); と入力することになるが、どちらも[r^2+3,w^2+w+1,2*w*x+r*x+x-2*r*w-r+3]
という結果になって様子がおかしい。与えられた式をそのまま返しただけになっている。これは、元々の商 $\dfrac{r(2\omega+1)-3}{2\omega+1+r}$ が、「べき根の選び方によっては、$\frac{0}{0}$ 型不定形になる式」だったためだ。つまり等式 $(2\omega+1+r)x = r(2\omega+1)-3$ は、$x$ の係数と右辺が同時に $0$ になる可能性があり、その場合は $x$ は任意の値でよくなってしまう。このせいで、「多項式の同値変形」の制限のもとでは、「$x=\dots$」の形の等式を得ることができない。

どうすればいいかは、
http://maxima.hatenablog.jp/entry/2019/01/21/011356
のコメント欄での jurupapa さんと ehito さんのやりとりの中で論じられている。「$\text{分母}=0$」の可能性を除外するため、連立方程式に $(2\omega+1+r)y=1$ を追加してやればいいのだ。
\begin{equation}
\label{eq:howtocomputegaloisgroup-new-4}
\begin{cases}
r^{2} + 3 &= 0 \\
\omega^{2}+\omega+1 &= 0 \\
(2\omega+1+r)x &= r(2\omega+1)-3 \\
(2\omega+1+r)y &= 1
\end{cases}
\end{equation}
$y$ はダミーの（新たな）未知数である。Wolfram Alpha なら GroebnerBasis[{r^2+3,w^2+w+1,(2*w+1+r)*x-(2*r*w+r-3),(2*w+1+r)*y-1},{y,x,w,r}]、maxima なら poly_reduced_grobner([r^2+3,w^2+w+1, (2*w+1+r)*x-(2*r*w+r-3), (2*w+1+r)*y-1],[y,x,w,r]); となる。ダミーでしかない $y$ はなるべく登場してこないよう、消去の優先順位を最も高くしてある。結果は
\[ \eqref{eq:howtocomputegaloisgroup-new-4} \iff \begin{cases}
r^2+3 &=0 \\
2\omega-r+1 &=0 \\
x-r &=0 \\
6y+r &=0
\end{cases} \]
となって、期待通りべき根の選び方が $2\omega-r+1=0$ に制限されて $x=r$ という「分母の有理化」が実行された。ダミー未知数 $y$ についても $y=-\dfrac{r}{6}$ という結果が得られている。

ここで、「勝手に $\text{分母} \ne 0$ の条件を追加していいのか？本当に $\text{分母}=0$ だったらまずいじゃないか？」という疑問について考察しておこう。まず、私たちが解決すべき課題は「べき根の選び方の不定性によって、$0$ になる可能性も、ならない可能性もある式」が分母にある場合だったことを思い出そう。今の場合、べき根の選び方は自由なのだから、そのような式のうち特定の $1$ 個だけに限れば、「$0$ でない」と決めつけても一般性は失われない。それは「色々あるべき根の選び方のうち、適するものを選んだだけ」と考えればいいからだ。上の例の場合、それが「$2\omega-r+1=0$」に反映されていて、「べき根の選び方のうち、これをみたすものしか許されない」ということを意味する。つまりこれは、以前の記事で書いた

体の拡大過程の各ステップごとに、正しい結果を得るためにどんな条件を追加すればいいか

がわかったということで、グレブナー基底を使えばそれが自動的に得られるということだ。

さらに「本当に、べき根の選び方の自由度を調節すれば必ず $\text{分母} \ne 0$ にできるのか？どんな選び方をしても $\text{分母} = 0$ になるような場合があったらどうするんだ？」という点も考えておこう。もしそんなことがあったとすると、\eqref{eq:howtocomputegaloisgroup-new-4}に当たる連立方程式が解なしになる。そういう場合、グレブナー基底を求めさせるとどうなるかと言うと、「$1$」という単独の出力になる。これはつまり同値変形の結果が「$1=0$」になるということで、元の連立方程式の未知数にどんな値を代入しても決して等式が成立しない、ということだ。このようにして、分母が本当に $0$ になってしまうかどうかは、グレブナー基底が「単独の $1$」になるかどうかをチェックすることで判定ができる。その場合は利用しようとしていた $\theta_{i}(x)$ の最高次の係数と思っていたものが実は $0$ だった、ということなので、最高次の係数の候補として次に次数の高い項、あるいは別の $\theta_{j}(x)$ の最高次の係数を試す…ということをしていけばよい。

また、そもそも以前の記事で書いたように、「$1$ のべき根の添加は、最初に一度だけ行っておくだけで済ます」ようにすれば、最初から「べき根の選び方の不定性によって、$0$ になる可能性も、ならない可能性もある式」が分母に現れることを避けられる。こちらで問題を回避しておいた方が筋がいいだろう。

$g(x)$ の逐次因数分解

以上の話は、$g(x)$ の因数分解を進める 1 ステップで、$V$ の新しい最小多項式 $h(x)$ を「大量の $\theta_{i}(x)$ をまず求め、それらを組み合わせて $h(x)$ を作る」のように「手作り」する場合の話だ。しかし、ehito さんが http://maxima.hatenablog.jp/entry/2019/01/21/011356 のコメント欄で

グレブナー基底を用いれば，最小多項式と冪根の定義多項式を同時に求めることもできます

と書かれた通り、実はグレブナー基底を使えば手作りの必要はなく、$h(x)$ まで含めて自動的に求められる。

maxima で書かれたプロトタイプのプログラムは、ehito さんが http://ehito.hatenablog.com/entry/20190123/1548255005 で公開して下さっているが、やはりここでは数学的背景を交えて説明する。ここでは、根を求めたい多項式は $f(x)=x^{4}+2x^{3}+3x^{2}+4x+5$ で、$V = \alpha_{1} – \alpha_{2} + 2\alpha_{3} + 0\alpha_{4} +3\alpha_{5}$ となっており、ガロア群はフルの $S_{4}$、$V$ の最小多項式は
\[ g(x) = x^{24} + 24x^{23} + 336x^{22} + 3344x^{21} + 25740x^{20} + 159984x^{19} + 820856x^{18} + 3519504x^{17} + 12721926x^{16} + 39075680x^{15} + 104485896x^{14} + 257189424x^{13} + 603068156x^{12} + 1264487184x^{11} + 1484791560x^{10} – 3707413456x^9 – 23515353279x^8 – 53513746296x^7 – 7075256024x^6 + 299352120960x^5 + 770653544880x^4 + 869309952000x^3 + 1145273500800x^2 + 1451723788800x + 1818528595200 \]
となっている。体の拡大過程の第 1 ステップでは $p=2$ であり、$\theta_{1}(x) = \dfrac{h_{0}(x) – h_{1}(x)}{2}$ の最高次の係数は、$g(V)=0$ を使って次数下げした後は
\[ -\frac{1}{209545976417338944}(1802958665V^{22} + 39665090630V^{21} + 524580202740V^{20} + 4938491366600V^{19} + 35917920450635V^{18} + 210145521609990V^{17} + 1006371942278150V^{16} + 3977779456166720V^{15} + 13035039787796175V^{14} + 35490090761328530V^{13} + 83355266821597880V^{12} + 187374005424681720V^{11} + 409423561822850285V^{10} + 710497887957908450V^9 – 527741385127623570V^8 – 9890271294167003200V^7 – 29302186108233608560V^6 – 32740075840801574400V^5 + 125250591988477051200V^4 + 529066274435720117760V^3 + 459213722346625891200V^2 – 118558331806418265600V + 511948241523805824000) \]
となっている（これを一時的に $\varphi(V)$ とおこう）。ここからは、今までの手順（「手作り」）だと、$(\varphi(V))^{2}$ を $g(V)=0$ で次数下げすると定数になることを使い、実際にその定数を求めて $a=\varphi(V)$ をべき根で表すと共に、$(\varphi(V))^{2-1}\theta_{1}(x)$ を $g(V)=0$ で次数下げしたものも $V$ によらなくなることから実際に $V$ を含まない $x$ の多項式として求め、そこから $h_{0}(x)$ をべき根としての $a$ を係数に含む多項式として求める…という流れだった。

しかし、ehito さんはそんなことをしないで、グレブナー基底を使って
\[ \begin{cases}
g(V) &= 0 \\
a &= \varphi(V)
\end{cases} \]
を $a$, $V$ に関する連立方程式として同値変形している。変数の指定順は $V$, $a$ で、Wolfram Alpha や maxima に対する実際の入力はかなり長くなるのでここには書かないが、こういう結果が得られる。
\[ \begin{cases} 5V^{12} + 60V^{11} + 480V^{10} + 2600V^9 +10110V^8 +29040V^7 +57100V^6 +68520V^5 +178965V^4 +552820V^3 +1981500V^2 +2878800V +6762000 + 5V^6a + 30V^5a + 120V^4a + 280V^3a + 33V^2a – 414Va – 82a &= 0 \\ a^2-38880000 &= 0 \end{cases} \]
この第 2 式から、$a$ はべき根 $\sqrt{38880000} = 3600\sqrt{3}$ であることがわかる。そして第 1 式から $V$ は $\Q(a)$ 係数の多項式
\[ h(x) = 5x^{12} + 60x^{11} + 480x^{10} + 2600x^9 +10110x^8 +29040x^7 +57100x^6 +68520x^5 +178965x^4 +552820x^3 +1981500x^2 +2878800x +6762000 + 5x^6a + 30x^5a + 120x^4a + 280x^3a + 33x^2a – 414xa – 82a \]
の根であることもわかる。同値変形で得られた以上、これが $V$ の $\Q(a)$ 上の最小多項式になっているはずだ（※ 注）。これで、必要としていたものはすべて求まってしまった。「手作り」の手順のかなりの分は、グレブナー基底を求めるとその過程で内部的に同等なことが実行されて、自動的に得られるということになる。

※ ただ、ここが本当に「最小多項式」と言えるのかどうか、ちょっと自信はない。単に「同値変形になっている」というだけだと、最小多項式とは言い切れないのではないだろうか？例えば、左辺が「最小多項式の $2$ 乗」という形で出力されていたとしても、「同値変形」になっていること自体は間違いないわけだが…。【2020,1/5追記】肯定的に解決した。ちょびっとだけ、イデアルとグレブナー基底の知識を使う。まず、$\Q(a)$ 上の $V$ の最小多項式は定数倍を除き一意に決まるので、得られた結果の第 1 式 $t(V,a)$ が $V$ の多項式として $\Q(a)$ 上で異なる既約因子を持つことはありえない。したがって $t(V,a)$ は定数倍を除き $h(V,a)$ のべき乗と一致する。そのべき乗の指数が $1$ であることを示す。グレブナー基底は元の多項式と同じイデアルを生成するので、イデアル $\langle t(V,a), \underbrace{\text{第 2 式}}_{a^2-38880000\text{に当たる式}}\rangle$ に $g(V)$ が含まれる。すなわち多項式の等式として \[ g(V) = A(V,a) t(V,a) + B(V,a) \text{第 2 式} \] となるような多項式 $A$, $B$ が存在する。よって、$a$ に実際に第 2 式をみたすべき根を代入すると、$g(V)$ が $\Q(a)$ 係数の範囲で $t(V,a)$ で割り切れる。したがって、$t(V,a)$ が $h(V,a)$ の $2$ 乗以上のべきだった場合、既約な $g(x)$ が $h(x,a)$ で $2$ 回以上割り切れることになって矛盾する。

今のは $p=2$ のステップの話だったが、$p>2$ でも同様である。ehito さんの例で、上の話の続きのステップがどうなっているのかを引き続き見てみよう。上で得られた $V$ の $\Q(a)$ 上の最小多項式 $h(x)$ を、$x$ と $a$ の $\Q$ 係数多項式として $g(x,a)$ とおき直す。次のステップは $p=3$ であり、$1$ の原始 $3$ 乗根 $\omega$ が顔を出す。新しくおいた $h_{i}(x)$ は $\Q[V,a]$ 係数の多項式で、それに対して新しい $\theta_{i}(x)$ が定まる。
\[ \theta_{1}(x) = \frac{h_{0}(x) + \omega h_{1}(x) + \omega^{2} h_{2}(x)}{3} \]
で、これは実際には $\Q[V,a,\omega]$ 係数の多項式となっている。$\omega^{2}+\omega+1=0$ と $g(V,a)=0$ を使って $\omega$ と $V$ の次数下げをした後の $\theta_{1}(x)$ の最高次係数が、$V$, $a$, $\omega$ の $\Q$ 係数多項式として得られる。それはとてつもなく長いので、ここでは省略するが、改めて $\varphi(V,a,\omega)$ とおこう。当然、$(\varphi(V,a,\omega))^{3}$ を $g(V,a)=0$, $a^{2}=38880000$, $\omega^{2} + \omega+1=0$ を使って次数下げすれば $V$ が消えて $a$ と $\omega$ だけの式になり、$b=\varphi(V,a,\omega)$ が $3$ 乗根として求まるはずである（が、その計算はやはり直接はやらない）。よって、ここでグレブナー基底を求めて同値変形する連立方程式は
\[ \begin{cases}
g(V,a) &= 0 \\
a^2-38880000 &= 0 \\
\omega^{2}+\omega+1 &= 0 \\
b &= \varphi(V,a,\omega)
\end{cases} \]
である。変数の優先順位を $V$,$b$, $a$, $\omega$ としてこのグレブナー基底を求めれば、$b^{3}$ を $a$, $\omega$ で表した式と、$a^2-38880000 = 0$, $\omega^{2}+\omega+1 = 0$、それから $\Q(a,b,\omega)$ 上の $V$ の最小多項式が得られるという寸法（これは数式処理ソフトでも時間がかかる）。

この技法を使った場合でも、方程式によっては $\theta_{i}(x)$ の最高次係数が「べき根の選び方によって $0$ になる可能性も、ならない可能性もある式」になることがある。そういう場合は先ほどと同じくダミーの未知数を加えて「$\ne 0$」の条件を強制する手もあるが、上でも書いた通り、それよりも「$1$ のべき根の添加は、最初に一度だけ行っておくだけで済ます」ようにして、最初からそういう不定性が出ないやり方でやる方が紛れがなくていいだろう。

解を $V$ で表す式

元の方程式の解 $\alpha$, $\beta$, $\gamma$ を $V$ の $\Q$ 係数多項式として表す式の求め方については、https://ikumi.que.jp/blog/archives/746 でも触れた「代数拡大体上での因数分解」を使う方法がいちばん簡潔で早いだろうが、原理的にはグレブナー基底を使って求めることもできる。http://maxima.hatenablog.jp/entry/2017/10/28/124236 のコメント欄で ehito さんが提示してくださったやり方で、当初は jurupapa さんも使っていた方法だった。この技法が、２年余りを経てやっと私にも理解できるようになったわけだ（笑）。

いつもの例として $f(x)=x^{3}-3x-1$, $V=\alpha+2\beta+3\gamma$ で、$V$の最小多項式として $g(x) = x^{3}-9x-9$ を選んだ場合を考える。ehito さんが提示してくださったのは

poly_reduced_grobner (
 [ v ^ 3 - 9 * v - 9,
 a + 2 * b + 3 * c - v,
 a + b + c,
 a * b + b * c + c * a + 3,
 a * b * c - 1 ],
 [ a, b, c, v ] ) ;

で（$\alpha$, $\beta$, $\gamma$ をそれぞれ $a$, $b$, $c$ で代用している）、これは要するに次の連立方程式を同値変形しようというものだ。
\[ \begin{cases}
g(V) &= 0 \\
V &= \alpha + 2\beta + 3\gamma \\
\alpha + \beta + \gamma &= 0 \\
\alpha\beta + \beta\gamma + \gamma\alpha &= -3 \\
\alpha\beta\gamma &= 1
\end{cases} \]
後ろ３つが元の $3$ 次方程式の解と係数の関係だから、これで $\alpha$, $\beta$, $\gamma$ が $f(x)=0$ の３解である条件が過不足なく表されている。$V = \alpha + 2\beta + 3\gamma$ だけだと $V$ の最小多項式が $g(x)$ と $x^{3}-9x+9$ のどちらなのか決まらないため、$g(V)=0$ の条件も加えることで、$\alpha$, $\beta$, $\gamma$, $V$ に対する必要十分条件となっている。そして、グレブナー基底を求める際の変数消去の優先順位が $\alpha$, $\beta$, $\gamma$, $V$ と指定されている。つまり $V$ はいくらでも残って構わないから $\alpha$, $\beta$, $\gamma$ の登場をなるべく少なくせよ、という要求になっており、それに従って同値変形が行われる結果として $\alpha$, $\beta$, $\gamma$ が $V$ のみの式で表されるわけだ。実行結果は、maxima だとこうなる。
[v^3-9*v-9,v^2-3*c-6,v^2-3*v-3*a-6,-2*v^2+3*v-3*b+12]
Wolfram Alpha だとこんな入力だ。GroebnerBasis[{v^3-9*v-9,a+2*b+3*c-v,a+b+c,a*b+b*c+c*a+3,a*b*c-1},{a,b,c,v}]
出力はこうである。
{v^3 - 9 v - 9, 3 c - v^2 + 6, 3 b + 2 v^2 - 3 v - 12, 3 a - v^2 + 3 v + 6}
どちらにしろ、いつもの結果
\[ \begin{cases}
V^{3} -9V -9 &= 0 \\
\alpha &= \frac{V^{2}}{3}-V-2 \\
\beta &= -\frac{2}{3}V^{2}+V+4 \\
\gamma &= \frac{V^{2}}{3} – 2
\end{cases} \]
が得られている。

ただし、ここの計算でグレブナー基底を使うと、次数の高い方程式では処理が相当に重くなる。これは、元々グレブナー基底の計算は、かなり計算量が膨れ上がる性質のものだからだ（そのため、実用的にはこのように数式処理ソフトに任せて計算してもらうべきもので、手計算で実現できるようなものではない）。

ガロア群を求める別法

代数拡大体上での因数分解の確認と、小規模な拡張

早い所「ガロア群を求める別法」の解説に進みたいが、その過程で「代数拡大体上での因数分解」をちょっと拡張した技法に触れざるを得ないので、先にその話を済ませておく。「代数拡大体上での因数分解」の maxima での計算の仕方と、ちょっとした拡張の原理の説明の２点からなる話になる。

maxima での計算

maxima では組み込み関数 factor でその機能が使え、引数を 2 つ与えて factor(p,q); と入力すると「q の根を使って p を既約分解する」ことができる。例えば、
factor(x^2-2*x-1,a^2-2);
と入力すれば
(x-a-1)*(x+a-1)
という結果が得られ、これは「$a^{2}-2=0$ をみたす数 $a$ を使って、$x^{2}-2x-1$ が $(x-a-1)(x+a-1)$ と既約分解される」ことを表す。なお、Wolfram Alpha だとどう入力すればいいのか（そういう機能が組み込みで用意されているのか）、私にはわからなかった。以下も、実行例は maxima のみを記す。

代数拡大体上での因数分解の拡張

以前
https://ikumi.que.jp/blog/archives/746
で説明したアルゴリズムは、「$\Q$ 係数多項式を $\Q(a)$ 係数の範囲で既約分解する」ものだったが、実はまったく同じ手順で「$\Q(a)$ 係数多項式を $\Q(a)$ 係数の範囲で既約分解する」こともできる。その原理を説明しよう。

既約分解したい多項式は重根を持たないとし、それを $x$, $a$ の 2 変数多項式と見て、$p(x,a)$ とおく（$a$ は $\Q$ 上代数的なので、$p$ は $a$ についても多項式の形としてよい）。$a$ の $\Q$ 上の最小多項式を $q(x)$ とし、$q(x)$ の実際の根を $a_{1}, a_{2}, \dotsc$ としよう。$c$ を整数として $p(X-ca,a)$ と $q(a)$ の間で $a$ に関する終結式を作り、$X$ の $\Q$ 係数多項式を得る。それが平方因子を持たないように整数 $c$ を選んでおけば、以前の手順とまったく同様に $p(X-ca,a)$ の $X$ に関する $\Q(a)$ 上の既約分解、ひいては $p(x,a)$ の $x$ に関する $\Q(a)$ 上の既約分解が得られる（以前と違って、$p$ が $a$ を陽に含む場合は、しばしば $c=0$ が適する値になる）。そのようになる原理も以前と同じだ。また、平方因子を持たないように整数 $c$ を選べることは、次のようにして確かめられる: $p(x,a_{1})$ の根を $b_{11}, b_{12}, b_{13}, \dots$ とする。仮定より、これらはすべて互いに異なる。定数倍を除き
\begin{align*} p(x,a_{1}) &= (x-b_{11})(x-b_{12})\dotsm \\ \therefore p(X-ca_{1},a_{1}) &= (X-ca_{1}-b_{11})(X-ca_{1}-b_{12})\dotsm \end{align*}
である。また、$p(x,a_{2})$ の根を $b_{21}, b_{22}, b_{23}, \dots$ とすれば、これらもすべて互いに異なり、定数倍を除き
\begin{align*} p(x,a_{2}) &= (x-b_{21})(x-b_{22})\dotsm \\ \therefore p(X-ca_{2},a_{2}) &= (X-ca_{2}-b_{21})(X-ca_{2}-b_{22})\dotsm \end{align*}
である。（以下同様）

すると、終結式は定数倍を除き
\begin{align*} p(X-ca_{1},a_{1})p(X-ca_{2},a_{2})\dotsm &= (X-ca_{1}-b_{11}) (X-ca_{1}-b_{12}) \dotsm \\ &\times (X-ca_{2}-b_{21})(X-ca_{2}-b_{22})\dotsm \end{align*}
となるので、$X$ の多項式としての根は
\[ ca_{i} + b_{ij} \quad (i=1,2,\dots; j=1,2,\dots) \]
となる。よって、これらが互いにすべて異なる整数 $c$ は必ず存在する。（※ 上では、「$p(x,a)$ が $x$ の多項式として $a=a_{1}, a_{2}, \dots$ のどの値に対しても重根を持たない」ということを仮定しているが、「$a_{1}, a_{2}, \dots$ のうち一部の値に対しては重根を持ち、他の値に対しては重根を持たない」ということは起こらない。なぜならば、もし $x$ の多項式として $p(x,a_{1}) = (\Phi(x,a_{1}))^{2}\Psi(x,a_{1})$ と因数分解されていたとすると（ただし、$\Phi$, $\Psi$ は $2$ 変数の $\Q$ 係数多項式）、$a_{1}$ と $\Q$ 上で共役な他の値 $a_{2}, a_{3}, \dotsc$ に対しても同じ形の式 $p(x,a_{i}) = (\Phi(x,a_{i}))^{2} \Psi(x,a_{i})$ の式が成立するので）

maxima の factor コマンドは、この機能をすでに内包済みのようだ。例えば
factor(x^4-2*a^2,a^2-2);
を入力すると、結果は
(x-a)*(x+a)*(x^2+2)
なる。つまり、$a^{2}=2$ をみたす $a$ によって $x^{4}-2a^{2}$ を $\Q[a]$ 上で既約分解すると $(x-a)(x+a)(x^{2}+2)$ となる、という結果がちゃんと得られている。

ガロア群を求める別法・具体的手順

「代数拡大体上での因数分解」の技法を知って以来、折に触れて思い返して「$f(x)$ の根 $\alpha$ 1個を添加しただけで最小分解体ができてしまう場合は、他の根がすべて $\alpha$ の有理係数多項式として表せるわけだから、そこからガロア群も求められるな」ということを考えていたのだが、「1個だけでは最小分解体ができない場合も、他の解を1個ずつ順に追加していけばいつかは最小分解体に達するんだから、再帰的処理で原始元が作れてガロア群を求められるんじゃないか？」というアイディアを思いついた。「ひょっとして、ehito さんが以前公開された、私には何が何だかさっぱり理解できなかったガロア群計算ルーチンってこれと近いんじゃないの？」と思いついて、新たな視点でコードを眺め直してみると、まさしくそうであることがわかった。以下では、その後 ehito さんが整備・公開された
http://ehito.hatenablog.com/entry/2019/02/24/150254
http://ehito.hatenablog.com/entry/2019/06/23/150150
も——私に何とか解る所だけ（笑）——参考にし、新しいアルゴリズムを解説してみる。なお、ここまでの記述で解る通り、新規性はなく、やってることは ehito さんの後追いに過ぎない。

元々の（有理数係数の）方程式を $f(x)=0$ とする。私のこれまでのガロア群を求めるアルゴリズムは、$f(x)$ は重根さえ持たなければ可約であっても動作したが、新しい方法は「代数拡大体上での因数分解」の技法を使う都合上、$f(x)$ は（$\Q$ 上）既約である必要があるので、ここからしばらくは $f(x)$ は既約とする。可約だった場合は最後の方で考察しようと思ったが、そこまで書き切れなかったので、次回の記事に回すことにする。

また、ひとまずは使う手法に制限をつけずに、グレブナー基底も要所要所で利用して計算を進める。一通り話が済んだ後で、グレブナー基底を使っていた所を、より初等的な計算で迂回する手順を考察する。

グレブナー基底・あり

まず、$f(x)$ をその根 $\alpha$ を添加した体 $\Q(\alpha)$ 上で既約分解する。ここでは、「代数拡大体上での因数分解」を使う。

maxima による実行例を、$f(x)=x^{3}-3x-1$, $f(x)=x^{3}-2$ について示す（$\alpha$ を $a$ で代用している）。

(%i1)    factor(x^3-3*x-1,a^3-3*a-1);
(%o1)    (x-a)*(x-a^2+a+2)*(x+a^2-2)
(%i2)    factor(x^3-2,a^3-2);
(%o2)    (x-a)*(x^2+a*x+a^2)

つまりこうなっている。
\begin{align*} x^{3}-3x-1 &= (x-\alpha)(x-\alpha^{2}+\alpha+2)(x+\alpha^{2}-2) \\ x^{3}-2 &= (x-\alpha)(x^{2}+\alpha x+\alpha^{2}) \end{align*}
当然ながら、必ず $x-\alpha$ が因子のひとつとなる。このことを考えれば、始めから $f(x)$ を $x-\alpha$ で割っておき、その商に対して上の拡張「$\Q(\alpha)$ 係数の多項式を $\Q(\alpha)$ 係数の範囲で既約分解」を実行してもいいだろう。

まず、ひとつめの $f(x)=x^{3}-3x-1$ のように $\Q(\alpha)$ で $f(x)$ が完全に因数分解し尽くしてしまう場合を考える。この場合は簡単だ。$\Q(\alpha)$ が $f(x)$ の最小分解体そのものなので、最小分解体の原始元としては $\alpha$ が選べ、その $\Q$ 上の最小多項式は $f(x)$ そのものである。上の例では、$f(x)=0$ の解は $\alpha_{1} = \alpha$, $\alpha_{2} = \alpha^{2}-\alpha-2$, $\alpha_{3} = -\alpha^{2}+2$ であり、ガロア群の元は
\begin{align*} \alpha &\mapsto \alpha_{1} = \alpha \\ \alpha &\mapsto \alpha_{2} = \alpha^{2}-\alpha-2 \\ \alpha &\mapsto \alpha_{3} = -\alpha^{2}+2 \end{align*}
のそれぞれが $\Q(\alpha)$ に誘導する同型写像となる。これらの写像が、解の置換としてどんな置換かはすぐわかる。例えば、$\alpha \mapsto \alpha_{2}$ が誘導する同型写像が第3の解 $\alpha_{3}$ をうつす先はこのように計算できる。
\begin{align*} \alpha_{3} = -\alpha^{2} + 2 &\mapsto -{\alpha_{2}}^{2} + 2 \\ &= -(\alpha^{2}-\alpha-2)^{2}+2 \\ &= -\alpha^{4}+2\alpha^{3}+3\alpha^{2}-4\alpha-2 \\ &= \alpha \quad (\because f(\alpha)=\alpha^{3}-3\alpha-1=0) \end{align*}
つまり、$\alpha \mapsto \alpha_{2}$ が誘導する同型写像は、第3の解 $\alpha_{3}$ を第1の解 $\alpha_{1}$ にうつす。このようにして、3つの同型写像のいずれに対しても、どの解をどの解にうつすのかはすべて計算できる（と言っても、最初の $\alpha \mapsto \alpha_{1}$ は当然恒等写像なので、わざわざ求めるまでもないが）。

続いて、$\alpha$ を添加しただけでは最小分解体ができなかった場合に進もう。上の２つ目の例の $f(x)=x^{3}-2$ では、$x-\alpha$ 以外の既約因子が因数分解しきれずに $x^{2}+\alpha x +\alpha^{2}$ という $2$ 次式になっている。そこで、この $2$ 次式の根を $\beta$ として、さらに $\beta$ も使って既約分解を行う。（なお、この $\beta$ も当然 $f(x)$ の根のひとつである）
\begin{gather}
\beta^{2}+\alpha\beta+\alpha^{2} = 0 \notag\\
x^{2}+\alpha x+\alpha^{2} =
(x-\beta)(x+\alpha+\beta) \label{eq:howtocomputegaloisgroup-new-10}
\end{gather}
今の場合は、\eqref{eq:howtocomputegaloisgroup-new-10}の計算は手計算でも可能で、$\Q(\alpha,\beta)$ では $f(x)$ が $1$ 次式に分解しつくした。
\[ x^{3}-3x-1 = (x-\alpha)(x-\beta)(x+\alpha+\beta) \]
つまり $\Q(\alpha,\beta)$ が $f(x)$ の最小分解体である。

したがって、この $\Q(\alpha,\beta)$ を単拡大 $\Q(u)$ として実現できる原始元 $u$ が見つかれば、やはり先ほどと同じようにガロア群がわかるはずである。具体的には、$\alpha$, $\beta$ の有理係数の具体的な多項式として表せる $u$ をうまく作って、$\alpha$, $\beta$ を $u$ の有理係数多項式として具体的に表し、さらに $u$ の $\Q$ 上の最小多項式が求まればいい。

それにはどうすればいいか…は、ガロア理論（体論）の教科書には大体書いてあるだろう。$u=\alpha+ c\beta$ とおいて、整数 $c$ を適切に選べば、$u$ は望みの原始元となるのだった。例えば $c=-1$ として、$u=\alpha-\beta$ が適切かどうか調べてみよう。
\begin{equation}
\label{eq:howtocomputegaloisgroup-new-8}
\begin{cases}
\alpha^{3} -2 &= 0 \\
\beta^{2}+\alpha\beta+\alpha^{2} &= 0 \\
u &= \alpha – \beta
\end{cases}
\end{equation}
を $\alpha$, $\beta$, $u$ についての連立方程式として見て、グレブナー基底を求めることで同値変形してみる。maxima で
poly_reduced_grobner([a^3-2,b^2+a*b+a^2,u-a+b],[a,b,u]);
の出力は
[-u^4-18*u-36*b,u^6+108,u^4-18*u+36*a]
となった（$\beta$ を $b$ で代用している）ので、
\[ \eqref{eq:howtocomputegaloisgroup-new-8} \iff
\begin{cases}
u^{6} + 108 &= 0 \\
36\alpha + u^{4} – 18u &= 0 \\
36\beta + u^{4} + 18u &= 0
\end{cases} \]
となる。するとまず $\alpha$, $\beta$ が $u$ について解けて
\begin{equation}
\label{eq:howtocomputegaloisgroup-new-9}
\begin{cases}
\alpha &= -\frac{u^{4}}{36} + \frac{u}{2} \\
\beta &= -\frac{u^{4}}{36} – \frac{u}{2}
\end{cases}
\end{equation}
だから $\alpha, \beta \in \Q(u)$ で、よって $\Q(\alpha, \beta) = \Q(u)$ である。つまり $c=-1$ は適する整数値である。よって、$u = \alpha – \beta$ がこれまでの $V$ に相当する量であり、さらに $u$ の $\Q$ 上の最小多項式が $g(x)=x^{6}+108$ であることもわかった。

また、\eqref{eq:howtocomputegaloisgroup-new-10}によって、$f(x)$ の $\alpha$, $\beta$ 以外の根 $\gamma$ は $-\alpha-\beta$ であるから、\eqref{eq:howtocomputegaloisgroup-new-9}を用いて
\begin{equation}
\label{eq:howtocomputegaloisgroup-new-11}
\gamma = -\alpha-\beta = \frac{u^{4}}{18}
\end{equation}
もわかった。

ここから、ガロア群を求める考え方は大きく分けて２つある。

$u$ が最小分解体の原始元なのだから、$g(x)$ も $\Q(u)$ 上で完全に因数分解しつくすはずである。実際、
factor(x^6+108, u^6+108);
を実行すれば
((x-u)*(x+u)*(12*x-u^4-6*u)*(12*x-u^4+6*u)*(12*x+u^4-6*u)*(12*x+u^4+6*u))/20736
が得られるので \[ g(x) = \text{（定数）} (x-u)(x+u) (12x-u^{4}-6u) (12x-u^{4}+6u) (12x+u^{4}-6u) (12x+u^{4}+6u) \] となっている。すなわち $g(x)$ の $6$ つの根は \begin{align*} u_{1} &= u \\ u_{2} &= -u \\ u_{3} &= \frac{u^{4}}{12} + \frac{u}{2} \\ u_{4} &= \frac{u^{4}}{12} – \frac{u}{2} \\ u_{5} &= -\frac{u^{4}}{12} + \frac{u}{2} \\ u_{6} &= -\frac{u^{4}}{12} – \frac{u}{2} \end{align*} とわかって、$u$ を $u_{1}, \dots, u_{6}$ のそれぞれにうつす同型写像としてガロア群が得られる。それぞれの写像が解 $\alpha$, $\beta$, $\gamma$ をどのように入れ替えるかは、\eqref{eq:howtocomputegaloisgroup-new-9}と\eqref{eq:howtocomputegaloisgroup-new-11}から直接計算できる。
今のやり方は、$g(x)$（あるいは $g(x)$ を $x-u$ で割った商）を $\Q(u)$ 上の $1$ 次式の積に分解する際に、いちから「代数拡大体上での既約分解」を使った。しかし、これは $g(x)$ の次数が高くなるとかなり計算が大変になる。もうひとつの考え方は、各解を $u$ で表す式がわかっていることを使うものだ。

$u= \alpha – \beta$ の両辺に、ガロア共役変換（ガロア群の同型写像）を順に一通り作用させてみたとすると、左辺には $g(x)$ の根が一通りすべて並ぶ。そして右辺には解 $\alpha$, $\beta$ を別の解にうつした値が並ぶ。したがって、$g(x)$ の根の候補は \begin{align} u_{1} &= \alpha – \beta \quad (=u) \notag\\ u_{2} &= \beta – \gamma \label{eq:howtocomputegaloisgroup-new-5}\\ u_{3} &= \gamma – \alpha \notag\\ u_{4} &= \alpha – \gamma \notag\\ u_{5} &= \gamma – \beta \notag\\ u_{6} &= \beta – \alpha \notag \end{align} のみである（※ 上の $u_{1}, \dots, u_{6}$ とは添字のつけ方は揃えていない）。これらの右辺に\eqref{eq:howtocomputegaloisgroup-new-9}, \eqref{eq:howtocomputegaloisgroup-new-11}を代入すると $u$ のみの式が作れる。 \begin{align*} u_{1} &= u \\ u_{2} &= -\frac{u^{4}}{12} – \frac{u}{2} \\ u_{3} &= \frac{u^{4}}{12} – \frac{u}{2} \\ u_{4} &= -\frac{u^{4}}{12} + \frac{u}{2} \\ u_{5} &= \frac{u^{4}}{12} + \frac{u}{2} \\ u_{6} &= -u \end{align*} これらを順次 $g(x)$ に代入して、$g(u)=0$ で次数下げして $0$ になるかどうかを調べれば、$g(x)$ の根が $u_{1}, \dots, u_{6}$ のどれなのかがわかる（$u_{1}=u$ が根なのは当たり前なので、実際には $u_{2}$ 以降だけ調べればよい）。

例えば \begin{align*} g(u_{2}) &= g\Bigl( -\frac{u^{4}}{12} – \frac{u}{2} \Bigr) \\ &= \Bigl( -\frac{u^{4}}{12} – \frac{u}{2} \Bigr)^{6} + 108 \\ &= 0 \quad (\because u^{6}+108=0) \end{align*} なので $u_{2}$ は $g(x)$ の根のひとつである。また、\eqref{eq:howtocomputegaloisgroup-new-5}から、$u$ を $u_{2}$ にうつすガロア共役変換は $\alpha$, $\beta$ を $\beta$, $\gamma$ にうつすことがわかる。他の解 $\gamma$ がどの解にうつるかは、この場合は消去法ですぐわかるが、一般には他の解は複数あるので一般性のある手順を述べると、そのうつり先は\eqref{eq:howtocomputegaloisgroup-new-11}で、$u$ を $u_{2} = -\frac{u^{4}}{12} – \frac{u}{2}$ に置き換えた結果を $g(u)=0$ で次数下げし、どの解と等しくなるかを調べることでわかる。このようにして、$g(x)$ の根であるとわかった $u_{i}$ に対し、$u \mapsto u_{i}$ が解の置換としてどのように働くかが決定できる。

今の場合は $g(x)$ が $3!=6$ 次だからガロア群がフルの対称群 $S_{6}$ であることは予めわかり、$(\alpha,\beta) \mapsto (\beta,\gamma)$ だろうがどんな置換でもガロア群の元になっていることが保証されているが、一般にはそうではない。だから、$u_{2}, \dots, u_{6}$ のどれが $g(x)$ の根なのかは、上のような試行錯誤によってしかわからないこともある。

こんな具合にして、「2つ目の解 $\beta$ まで $\Q$ に添加すれば最小分解体が作れる」ような方程式の場合も、ガロア群が解の置換群として求まり、かつ、最小分解体を作る原始元 $u$ ですべての解を $\Q$ 係数多項式で表す式と、$u$ の $\Q$ 上の最小多項式 $g(x)$ を手に入れられる。

一般化に当たって、注意すべきことを３つ述べておく。

$u=\alpha + c\beta$ の整数 $c$ の値が適するかどうかは、上のようにグレブナー基底を求めて、$\alpha$, $\beta$ が $u$ の有理係数多項式で表せるかどうか、つまり求まったグレブナー基底が $\text{(有理数)}\alpha + \text{($u$の有理係数多項式)}$ 及び $\text{(有理数)}\beta + \text{($u$ の有理係数多項式)}$ の形の多項式を含んでいるかどうかでチェックする。ダメだった場合は、$c$ の値を変えてうまく行くまで繰り返す…という試行錯誤を行う。試行錯誤なしに事前に適する $c$ の値を知る方法は、（あるのかもしれないが）私は知らない。
今の場合、既約分解\eqref{eq:howtocomputegaloisgroup-new-10}は手計算で実行できたが、それは $x^{2}+\alpha x + \alpha^{2}$ が $x$ の $2$ 次式だったおかげだ。このため、その根を $\beta$ とおくだけで $(x-\beta)(x+\alpha+\beta)$ と既約分解ができてしまった。しかし、一般にはこれは $x$ の高次の多項式になりうる。となると、「$x^{2}+\alpha x + \alpha^{2}$ に当たる高次多項式（あるいはそれを $x-\beta$ で割った商の高次多項式）を、$\Q(\alpha, \beta)$ 上で既約分解する」ことが必要になる。そのような場合にどうすればいいかを、$f(x)=x^{6}-2$ を例にとって説明する。

まず、$f(x)$ の根 $\alpha$ を使って $f(x)$ を $\Q(\alpha)$ 上で既約分解するとこうなる。 \[ f(x) = (x-\alpha) (x+\alpha) (x^{2}-\alpha x +\alpha^{2}) (x^{2} + \alpha x + \alpha^{2}) \] $1$ 次式に分解しきれずに残った既約 $2$ 次式の一方（好きな方を選んでよい）$x^{2}-\alpha x +\alpha^{2}$ の根を $\beta$ とする。 \[ \beta^{2}-\alpha\beta + \alpha^{2}=0 \] $\Q(\alpha, \beta)$ の原始元 $u$ を見つける。maxima で試したところ、$u=\alpha-\beta$ や $u=\alpha – 2\beta$ ではダメで、$u=\alpha+2\beta$ なら適した。
poly_reduced_grobner([a^6-2,b^2-a*b+a^2,u-a-2*b],[a,b,u]);
の出力が
[-u^7+1514*u-5040*b,-u^12-572*u^6-470596,-u^7-1006*u+2520*a]
となったので \begin{align*} \alpha &= \frac{u^{7}+1006u}{2520} \\ \beta &= \frac{-u^{7}+1514u}{5040} \end{align*} で、$u$ の $\Q$ 上の最小多項式は $g(x) = x^{12}+572x^{6}+470596$ である。先ほどの既約 $2$ 次因子を、$\Q(u)$ 係数の多項式として表す。 \begin{align*} x^{2}-\alpha x + \alpha^{2} &= x^{2} – \frac{u^{7}+1006u}{2520} x + \Bigl( \frac{u^{7}+1006u}{2520} \Bigr)^{2} \\ x^{2}+\alpha x + \alpha^{2} &= x^{2} + \frac{u^{7}+1006u}{2520} x + \Bigl( \frac{u^{7}+1006u}{2520} \Bigr)^{2} \end{align*} （前者は $x-\beta$ で割り切れることがわかっているので、その商を使ってもよい）そして、それぞれを $\Q(u)$ 係数の範囲で既約分解する。
factor(x^2-(u^7+1006*u)*x/2520+((u^7+1006*u)/2520)^2,u^12+572*u^6+470596);
の出力が
((1680*x-u^7-166*u)*(5040*x+u^7-1514*u))/8467200
なので \[ x^{2}-\alpha x + \alpha^{2} = \text{（定数）}(1680x-u^7-166u) (\underbrace{5040x+u^7-1514u}_{5040(x-\beta)}) \] であり、
factor(x^2+(u^7+1006*u)*x/2520+((u^7+1006*u)/2520)^2,u^12+572*u^6+470596);
の出力が
((1680*x+u^7+166*u)*(5040*x-u^7+1514*u))/8467200
だから \[ x^{2}+\alpha x + \alpha^{2} = \text{（定数）}(1680x+u^7+166u) (5040x-u^7+1514u) \] である。いずれも $1$ 次式まで因数分解しつくしたので、$\Q(u)\: (=\Q(\alpha, \beta))$ が $f(x)$ の最小分解体になっている。$f(x)$ の根は \begin{align*} \alpha &= \frac{u^{7}+1006u}{2520} & -\alpha &= -\frac{u^{7}+1006u}{2520} \\ \beta &= \frac{-u^{7}+1514u}{5040} & -\beta &= \frac{u^{7}-1514u}{5040} \\ &\quad \frac{u^{7}+166u}{1680} &&\quad -\frac{u^{7}+166u}{1680} \end{align*} だ。後は先ほど述べた２つの方法のどちらかでガロア群（$g(x)$ の根を $u$ で表した式その他）を求めればよい。
ここまで、グレブナー基底を求めて得られた $u$ のみの有理係数多項式をそのまま $u$ の最小多項式としてきたが、実を言うと本当にそう言い切れるかやや微妙な所がある。以前のアルゴリズムで、$V$ のみたす $n!$ 次の整数係数多項式 $F(x)$ は必ずしも既約とは限らず、可約だった場合にはその任意の既約因子を $V$ の最小多項式として選択できた。それと同様に、上の手順で得られた $u$ のみの有理係数多項式も、場合によっては可約になっている…という可能性がない、ということは私には証明できなかった。そこで、グレブナー基底の結果から、$u$ の最小多項式を確実に得る手順も述べておく。

上の $f(x)=x^{6}-2$ の場合を例に取る。$\alpha$ の $\Q$ 上の最小多項式が $6$ 次の $f(x)$ だから、$[\Q(\alpha):\Q] = 6$ である。また、$\beta$ の $\Q(\alpha)$ 上の最小多項式が $2$ 次の $x^{2}-\alpha x +\alpha^{2}$ だから、$[\Q(\alpha,\beta):\Q(\alpha)] = 2$ である。したがって、$\Q(\alpha,\beta) = \Q(u)$ の $\Q$ に対する拡大次数は $6\times 2 = 12$ で、これが $u$ の $\Q$ 上の最小多項式の次数である。ゆえに、グレブナー基底の同値変形によって $u$ の $12$ 次式が得られた時点で、これが最小多項式にもなっていることがわかる。この手順で、もし次数が一致していなければ、グレブナー基底によって得られたものは最小多項式でないので、それを $\Q$ 上で既約分解して、その任意の既約因子を最小多項式 $g(u)$ とすればいいだろう。グレブナー基底を求める変形が同値変形であることは保証されているので、どの既約因子でも差し支えないはずだ。

さて、それでは $\Q(\alpha, \beta)$ がまだ $f(x)$ の最小分解体にならない場合に進もう。例として、$f(x)=x^{4}+x+1$ の場合を考えよう。

$f(x)$ の根 $\alpha$ を用いて $f(x)$ を $\Q(\alpha)$ 上で既約分解する。maxima の入力と出力を交互に並べると

     f(x) := x^4+x+1;
     f(x):=x^4+x+1
     factor(f(x),f(a));
     (x-a)*(x^3+a*x^2+a^2*x+a^3+1)

（maxima では、f(x) := x^4+x+1 は関数の定義を意味する）だから
\[ f(x) = (x-\alpha)(x^{3} + \alpha x^{2} + \alpha^{2} x + \alpha^{3}+1) \] である。$t(x) = x^{3} + \alpha x^{2} + \alpha^{2} x + \alpha^{3}+1$ の根を $\beta$ とおき、$x-\beta$ で割った商を求めると

     t(x) := x^3+a*x^2+a^2*x+a^3+1;
     t(x):=x^3+a*x^2+a^2*x+a^3+1
     quotient(t(x),x-b,x);
     x^2+(b+a)*x+b^2+a*b+a^2

である（quotient が商を求める関数で、$t(x)$ を $x-b$ で割った商を、変数 $x$ について求めている）。
\[ f(x) = (x-\alpha)(x-\beta)(x^2 + (\beta+\alpha)x + \beta^2 + \alpha\beta + \alpha^2) \]
さらに、$\Q(\alpha,\beta)$ の原始元 $u$ を求める。$u=\alpha-\beta$ がうまく行き、

     poly_reduced_grobner([f(a),t(b),u-a+b],[a,b,u]);
    [-735*u^10+4000*u^8-4620*u^6+30213*u^4+194240*u^2- 338522*u-677044*b-368392,-u^12-8*u^8-26*u^6+112*u^4-216*u^2- 229,735*u^10-4000*u^8+4620*u^6-30213*u^4-194240*u^2-338522*u+ 677044*a+368392]

より
\begin{align*}
\alpha &= -\frac{735u^{10}- 4000u^8+ 4620u^6- 30213u^4- 194240u^2- 338522u+ 368392}{677044} \\
\beta &= \frac{-735u^{10}+ 4000u^8 -4620u^6 +30213u^4 +194240u^2 -338522u -368392}{677044}
\end{align*}
が得られる。また、$[\Q(\alpha, \beta):\Q] = 4\times 3 = 12$ なので $u$ の $12$ 次式 $-u^{12} -8u^8 -26u^6 +112u^4 -216u^2 -229$ から最小多項式がわかる: $g(x) = x^{12} +8x^8 +26x^6 -112x^4 +216x^2 +229$

$f(x)$ の残る既約因子の係数を $u$ で表す。$g(u)=0$ を使って次数下げする。
\begin{align*} x^2 + (\beta+\alpha)x + \beta^2 + \alpha\beta + \alpha^2 &= x^2+(-(735u^{10}-4000u^8+4620u^6-30213u^4-194240u^2+338522u+368392)/677044-(735u^{10}-4000u^8+4620u^6-30213u^4-194240u^2-338522u+368392)/677044)x+((735u^{10}-4000u^8+4620u^6-30213u^4-194240u^2+338522u+368392)^2)/(458388577936)+((735u^{10}-4000u^8+4620u^6-30213u^4-194240u^2-338522u+368392)^2)/(458388577936)+((735u^{10}-4000u^8+4620u^6-30213u^4-194240u^2-338522u+368392)(735u^{10}-4000u^8+4620u^6-30213u^4-194240u^2+338522u+368392))/(458388577936) \\ &= (458388577936x^2+(-995254680u^{10}+5416352000u^8- 6255886560u^6+40911060744u^4+263018053120u^2- 498835186496)x+1620675u^{20}-17640000u^{18}+68374200u^{16}- 244119330u^{14}-67453200u^{12}+5448864360u^{10}-11487264693u^8+45423264960u^6+46406167824u^4-314741627996u^2+ 407137996992)/458388577936 \\ &= (677044x^2 + (-1470u^{10}+8000u^8-9240u^6+60426u^4+388480u^2-736784)x + 4200u^{10}+1323u^8+26400u^6+117516u^4-457079u^2+557568)/677044 \end{align*}
これを $\Q(u)$ 内で既約分解する。分母の定数 $677044$ は不要なので、分子のみ見ればよい。

     factor(677044*x^2 + (-1470*u^10+8000*u^8-9240*u^6+60426*u^4+388480*u^2-736784)*x + 4200*u^10+1323*u^8+26400*u^6+117516*u^4-457079*u^2+557568,g(u));
     677044*x^2-1470*u^10*x+8000*u^8*x-9240*u^6*x+60426*u^4*x+388480*u^2*x-736784*x+4200*u^10+1323*u^8+26400*u^6+117516*u^4-457079*u^2+557568

$2$ 次式のままなので、$\Q(\alpha,\beta) = \Q(u)$ は $f(x)$ の分解体ではない。この $2$ 次式を $tt(x)$ とおく。

ここでどうするか。残っている $tt(x)$は $f(x)$ の因子なので、その根は元々の方程式の解である。そこで、これまでと同様、その根を $\gamma$ とおいて、$\Q(u,\gamma) = \Q(\alpha,\beta,\gamma)$ 内での因数分解を行えばよい。
\[ tt(\gamma) = 677044\gamma^2 + (-1470u^{10}+8000u^8-9240u^6+60426u^4+388480u^2-736784)\gamma + 4200u^{10}+1323u^8+26400u^6+117516u^4-457079u^2+557568 = 0 \]
$tt(x)$ は $2$ 次式なので、その根 $\gamma$ を使えば既約分解できることは明らかだが、一般性を考慮してその変形はしないで先に進む。

$\Q(u,\gamma) = \Q(v)$ となる $v$ をさがす。$v=u+2\gamma$ とおくとうまく行った。$\gamma$ を $c$ で代用して
poly_reduced_grobner([g(u),tt(c),v-u-2*c],[u,c,v]);
でグレブナー基底を計算させると、かなり長い出力となったので結果は省略するが、$v$ の $24$ 次式、$u$ と $\gamma$ をそれぞれ $v$ の $23$ 次式で表す式が得られた。$[\Q(u,\gamma):\Q] = 12 \cdot 2 = 24$ なので、$v$ の $24$ 次式が $v$ の最小多項式である。

これらを使って $tt(x)$ を $\Q(v)$ 係数の多項式に書き直し、$\Q(v)$ 係数の範囲内で既約分解すると、目論見通り $1$ 次式の積に分解しつくした。よって $\Q(v)$ が $f(x)$ の最小分解体である。$\alpha$, $\beta$ を $u$ で表す式は得ていたから、さらに $v$ で表す式も求められる。また、$v$ をその共役にうつす同型写像が、どの解をどの解にうつすかは、$v=u+2\gamma = \alpha – \beta + 2\gamma$ であることなどを使って求められる。

こんな具合に、どの段階でも「そこまで拡大した体の $\Q$ 上の原始元（$\alpha$, $u$, $v$ など）が得られている」ので、「新たに解を添加した拡大体の新たな原始元をその都度作れる」ようになっている。その繰り返しによって、原理的にはどんな高次の方程式でもガロア群が求められる。

グレブナー基底・なし

計算原理がわかった所で、引き続きグレブナー基底を回避する初等的アルゴリズムを考察しよう。上の手順でグレブナー基底を使っているのは、$u=\alpha + c\beta$ などの組み合わせで、$\Q(\alpha,\beta) = \Q(u)$ をみたす $u$ を見つける所だ。

$\alpha$ の $\Q$ 上の最小多項式は $f(x)$ である。$f(x)$ を $\Q(\alpha)$ 係数内で既約分解したときの既約因子に、$2$ 次以上のものが残っているとしよう。一般にはそれは複数ありうるが、そのうちの任意のひとつを選んで固定し、$\phi(x; \alpha)$ とおく。$\phi(x; \alpha)$ の根を $\beta$ とおけば、$\beta$ の $\Q(\alpha)$ 上の最小多項式は $\phi(x; \alpha)$ である。元々 $\phi(x;\alpha)$ は $f(x)$ の因子だったから、$\phi(x;\alpha)$ の根は「$f(x)$ の根のうち、$\alpha$ 以外のものの全部又は一部」である。再び $f(x)=x^{3}-2$ を例にとると、$\phi(x;\alpha) = x^{2} + \alpha x + \alpha^{2}$ で、$\beta^{2} + \alpha\beta + \alpha^{2}=0$ である。

$f(x)=x^{3}-2$ の根を $\alpha_{1}$, $\alpha_{2}$, $\alpha_{3}$ とし、$\phi(x; \alpha_{i}) = x^{2} + \alpha_{i} x + {\alpha_{i}}^{2}$ の根を $\beta_{i1}$, $\beta_{i2}$ とする。添字の付け方の一例は
\begin{align*} \alpha_{1} &= \sqrt[3]{2} & \beta_{11} &= \sqrt[3]{2}\omega & \beta_{12} &= \sqrt[3]{2} \omega^{2} \\ \alpha_{2} &= \sqrt[3]{2}\omega & \beta_{21} &= \sqrt[3]{2} & \beta_{22} &= \sqrt[3]{2} \omega^{2} \\ \alpha_{3} &= \sqrt[3]{2}\omega^{2} & \beta_{31} &= \sqrt[3]{2} & \beta_{32} &= \sqrt[3]{2} \omega \end{align*}
となるが、こうやって具体化しない方が一般化の道筋が見えやすいだろう。$\alpha = \alpha_{1}$, $\beta = \beta_{11}$ とする。

以下の計算をやりやすくするため、$u$ の定義式で整数 $c$ がかかる相手を $\beta$ から $\alpha$ に変更して $u=c \alpha + \beta$ としよう。これでも本質的な違いはない。

$\alpha_{i} \; (i=1,2,3)$ は互いに異なり、$i$ を固定したとき $\beta_{ij} \; (j=1,2)$ も異なるため、$c\alpha_{i} + \beta_{ij} \; (i=1,2,3; j=1,2)$ がすべて異なるような整数 $c$ が存在する。

考えることは次の３つになる。

上のような整数 $c$ を選べば、$u= c\alpha + \beta$ が $\Q(\alpha,\beta) = \Q(u)$ をみたすのはどうしてだったか。
その整数 $c$ はどうやって見つければいいか。
そのときどうやって $u$ の $\Q$ 上の最小多項式を得ればよいか。

まず $\beta = u-c\alpha$ を $\phi(\beta;\alpha)=0$ に代入して $\beta$ を消去すると
\[ (u-c\alpha)^{2} + \alpha(u-c\alpha) + \alpha^{2} = 0 \]
となる。よって、$\psi(x) = (u-c x)^{2} + x(u-cx) + x^{2}$ とおくと、$\alpha$ は $f(x)$ と $\psi(x)$ の共通根。しかし、$\alpha$ 以外の共通根はない。なぜならば、$f(x)$ の他の根 $\alpha_{2}$ に対しては
\begin{align*} \psi(\alpha_{2}) &= (u-c\alpha_{2})^{2} + \alpha_{2}(u-c\alpha_{2}) +{\alpha_{2}}^{2} \\ &= \phi(u-c\alpha_{2}; \alpha_{2}) \\ &= (u-c\alpha_{2} – \beta_{21}) (u-c\alpha_{2} – \beta_{22}) \end{align*}
である。そうすると $u=c\alpha_{1} + \beta_{11}$ だったことと $c$ に対する仮定から $\psi(\alpha_{2}) \ne 0$ と言え、同様に $\psi(\alpha_{3}) \ne 0$ も言える。

ゆえに、$\Q$ 係数の $f(x)$ と $\Q(u)$ 係数の $\psi(x)$ の間で互除法を実行すれば、唯一の最大公約式 $x-\alpha$ が $\Q(u)$ 係数の多項式として算出され、$\alpha \in \Q(u)$ が言えた。するとさらに $\beta = u – c\alpha$ も $\Q(u)$ の元である。これで $\Q(\alpha,\beta) \subset \Q(u)$ で、一方 $u=c \alpha + \beta$ より $\Q(u) \subset \Q(\alpha,\beta)$ であるから $\Q(u) = \Q(\alpha,\beta)$ がなりたつ。
今度は不定元 $U$ に対し $\psi(x,U) = (U-cx)^{2} + x(U-cx) + x^{2} = \phi(U-cx;x)$ と定義し直し、$f(x)$ との間で変数 $x$ についての終結式を作る。終結式の性質から、$c$ がどんな整数でもその結果は $U$ の $\Q$ 係数多項式（$r(U)$ とする）になるが、一方 $r(U)$ は定数倍の違いを除き次のものに等しい。 \begin{align*} &\quad \psi(\alpha_{1};U) \psi(\alpha_{2};U) \psi(\alpha_{3};U) \\ &= \phi(U-c\alpha_{1}; \alpha_{1}) \phi(U-c\alpha_{2}; \alpha_{2}) \phi(U-c\alpha_{3}; \alpha_{3}) \\ &= (U-c\alpha_{1} – \beta_{11}) (U-c\alpha_{1} – \beta_{22}) \times (U-c\alpha_{2} – \beta_{21}) (U-c\alpha_{2} – \beta_{22}) \times (U-c\alpha_{3} – \beta_{31}) (U-c\alpha_{3} – \beta_{32}) \end{align*} したがって、$r(U)$ の根は $c\alpha_{i} + \beta_{ij} \; (i=1,2,3;j=1,2)$ の全体である。よって、整数 $c$ の値を色々変えて、$r(U)$ が平方因子を持たない（$r'(U)$ と $r(U)$ が互いに素になる）ような $c$ が見つかるまで試せばよい。
上のふたつから、適切な $c$ に対しては、終結式として求めた $r(U)$ が $u=c\alpha + \beta = c \alpha_{1} + \beta_{11}$ を根に持っている。したがって、$u$ の $\Q$ 上の最小多項式は $r(U)$ を割り切る。一方、$f(x)=x^{3}-2$ は $3$ 次、$\phi(x;\alpha) = x^{2} + \alpha x +\alpha^{2}$ は $x$ について $2$ 次であることから、次のふたつはいずれも $3\times2 = 6$ に等しい。
- $r(U)$ の $U$ についての次数（終結式の作り方より）
- $\Q(\alpha,\beta)$ の $\Q$ 上の拡大次数
後者は $\Q$ 上の $u$ の最小多項式の次数でもある（$\because \Q(u) = \Q(\alpha,\beta)$）。よって、$r(U)$ こそがその最小多項式でなければならない。つまり、こうやって求めた終結式こそが、$u$ の最小多項式そのものだったというわけだ。

………これ、見直してみると上の方でやってる「$\Q(a)$ 係数の多項式を $\Q(a)$ 上で既約分解する」で出てきたのとまったく同じ計算してますね。まだ理解が整理できてないですが、おそらく実はもうちょっと深い背景があって、それを理解してると両方とも同じ話としてスッキリ理解できるんでしょうね…。$r(U)$ が最小多項式になり、したがって既約になる、ということは、上の話で、元々 $p(x,a)$ が $\Q(a)$ で既約だった場合は、$r(X)$ も既約で $\Q$ 上で分解はしない、ということですね。

このようにして、$u$ の最小多項式 $r(U)$ が得られるので、それを使って $\psi(x;u)$ と $f(x)$ の間で $x$ の多項式として互除法を実行すれば $1$ 次式の GCD が得られる（実際の計算過程では、$x$ の多項式としての係数が $u$ の有理式の形になることもあるので、分母が $0$ にならないかどうかの確認や、分数形を多項式形に直すために、$u$ の最小多項式が具体的に求まった後でないと計算ができない）。その $1$ 次式の根として $\alpha$ が $u$ の有理係数有理式（したがって、多項式）として求まるから、$\beta = u-c\alpha$ も $u$ の有理係数多項式として求まる。

具体的には、次の手順になる。

$c$ の決定
$u$ の最小多項式の算出
$\alpha$, $\beta$ を $u$ で表す

まず、$u=c\alpha + \beta$ で、適する整数 $c$ を見つける。試しに $c=1$ としてみる。$\psi(x,U) = (U-x)^{2} + x(U-x) + x^{2}$ と $f(x)=x^{3}-2$ の間で、$x$ に関する終結式 $r(U)$ を求める。 \[ r(U) = U^{6} + 4U^{3} + 4 \] （これは一目で完全平方式と見抜けるが、常にそうとは限らないので、それに気づかないフリをして）$r'(U) = 6U^{5}+12U^{2}$ と $r(U)$ の間で、$U$ の多項式として GCD を求めると \[ \gcd(r(U),r'(U)) = U^{3}+2 \] となるので、$r(U)$ は平方因子 $U^{3}+2$ を持つ。よって $c=1$ は不適とわかる。

次に $c=-1$ を試す。$\psi(x,U) = (U+x)^{2} + x(U+x) + x^{2}$ と $f(x)=x^{3}-2$ の間で、$x$ に関する終結式 $r(U)$ を求める。 \[ r(U) = U^{6}+108 \] $r'(U) = 6U^{5}$ と $r(U)$ の間で GCD を求めると \[ \gcd(r(U),r'(U)) = 1 \] だから $r(U)$ は平方因子を持たない。よって $c=-1$ は適しており、$u=-\alpha+\beta$ は $\Q(\alpha,\beta)$ に対する原始元。

したがって、$r(U)=U^{6}+108$ は $u$ の $\Q$ 上の最小多項式（上述の通り、既約かどうか調べなくても、$c=-1$ が適するとわかった時点で、次数のカウントによって $r(U)$ が最小多項式とわかる。つまり自動的に既約になる）。<\p>

そこで、$r(u)=u^{6}+108=0$ のもとで、$\psi(x;u) = (u+x)^{2} + x(u+x) + x^{2}$ と $f(x)=x^{3}-2$ の $x$ の多項式としての GCD を求める。普通に互除法を使うとこうだ。 \begin{align*} f(x) \div \psi(x;u) \text{ の余り} &= \frac{2u^2x+u^3-6}{3} \\ \psi(x;u) \div (2u^2x+u^3-6) \text{ の余り} &= \frac{u^6+108}{4u^4} \end{align*} ここで、$r(u)=0$ より $\text{分母}=4u^{4} \ne 0$ が保証され、かつ $\text{分子} = u^{6}+108 = 0$ となるので、ここで確かに割り切れている。よって \[ \gcd(f(x), \psi(x,u)) = 2u^2x+u^3-6 \] （※ 実際には、GCD が $1$ 次式になることが保証されるので、第一の余り算で $x$ の $1$ 次式が出た所でそれが GCD であることは確定する（次の余り算で割り切れることが確定する）。なお、一般には随時 $r(u)=0$ で次数下げして、係数が $0$ にならないかどうか確かめる必要がある。例えば、余りが $(u^{6}+108)x^{2} + u^{2}x+3$ のようになったら、見かけが $x$ の $2$ 次式でも実際には $1$ 次式なので、これこそが GCD、ということになる（さらに互除法を進行させるのは誤り））

この $1$ 次式の根が $\alpha$ だから \[ \alpha = -\frac{u^{3}-6}{2u^{2}} \] となる。さらに、$r(u)=u^{6}+108 = 0$ を使って「分母の有理化」を行うと \[ \alpha = -\frac{108u+6u^{4}}{216} = – \frac{u^{4}}{36} – \frac{u}{2} \] で、$u=-\alpha+\beta$ から \[ \beta = u+\alpha = -\frac{u^{4}}{36} + \frac{u}{2} \]

これで、グレブナー基底抜きで必要な情報が一通り揃えられた。

以上のアルゴリズムは、おそらく
http://ehito.hatenablog.com/entry/2019/02/24/150254
で公開されているプログラムとおおよそ同じものだろう。maxima の文法・コマンドを私が詳しく知らないのとプログラムの書き方が（私にとっては）かなり巧妙なのとでちゃんとは理解できていないが、部分的に読み取れる式の作り方や、

有理数体 Q に p の根を１つずつ添加し，その都度，拡大体の Q 上の定義式（絶対定義式）の次数を上げてゆく（代数体上の 2 次以上の既約因子から primitive element を生成する），分解体の定義式の計算としては一般的なものです

といったコメントからおおよそ見当がつく。（そして、

分解体の定義式の計算としては一般的なもの

ということは、要するに考え方としてはこの界隈の人にはよく知られたものであって、それにようやく追いつけた、というだけのことなのだろう。高次対称式の値を基本対称式に帰着して計算する、という以前のアルゴリズムの何と出遅れていたことよ…（笑））

続く

ガロア群の新しい計算法はあと２つ思いついているが、それは次回の記事に回す。この記事を書き始める前は全部いっぺんに書くつもりだったが、思ったより長い記事になってしまって残りを書く気力が今はない（笑）。なお、うち一方は計算効率などまったく考えていない、ほとんど「ネタ」でしかないものなので期待しないように。もう一方も、計算効率として特に優れているわけではないだろう。

また、$f(x)$ が $\Q$ 上可約だった場合のガロア群の求め方の注意についても次回に回す。