\(\newcommand{\Q}{\mathbb{Q}}\renewcommand{\dotsc}{\cdots}\DeclareMathOperator{\Res}{Res}\DeclareMathOperator{\Gal}{Gal}\)最近の記事を書いてきた知見から、従来の原始元 \(V\) を使う方法での計算について、計算効率を上げられる箇所が３ヵ所ほどあることに気づきましたので、紹介します。
\(F(x)\) の計算
すべての \(V_{k}\) を根に持つ多項式 \(F(x)\) は、次のように終結式の反復計算だけで求められます。
手順
まず手順から述べます。やはり、\(f(x)=x^{3}-3x-1\), \(V=\alpha+2\beta+3\gamma\) を例としましょう。準備として、「退職後は素人数学者」さんの \(r_{1}\), \(r_{2}\), \(r_{3}\) を求めておきます。\(f(x)\) を \(x-\alpha\), \(x-\beta\), \(x-\gamma\) で順次割っていった余りはすべて \(0\) になるので
\begin{align}
\alpha^{3}-3\alpha-1 &= 0 \label{galois-sol16-eq:1}\\
\alpha^{2}+\alpha\beta+\beta^{2}-3 &= 0 \label{galois-sol16-eq:2}\\
\alpha+\beta+\gamma &= 0 \label{galois-sol16-eq:3}
\end{align}
がなりたちます。それぞれの左辺が「退職後は素人数学者」さんの \(r_{1}\), \(r_{2}\), \(r_{3}\) で、以下では \(\alpha\), \(\beta\), \(\gamma\) を変数（不定元）とする多項式として扱います。
\(x-V\) に対して、以下のように \(r_{3}\), \(r_{2}\), \(r_{1}\) に対して順次終結式を計算します。まず、\(\gamma\) を変数と見て \(r_{3}\) との終結式を求めます。
\begin{equation}
\Res(x-V, r_{3}; \gamma) = \Res(x-\alpha-2\beta-3\gamma, \alpha+\beta+\gamma; \gamma) = -x-2\alpha-\beta \label{galois-sol16-eq:4}
\end{equation}
これは、符号を除けば単に\eqref{galois-sol16-eq:3}を使って \(x-V\) から \(\gamma\) を消去しただけです。終結式なので符号の違いは重要ではありません。
続いて、今の結果と \(r_{2}\) の間で、\(\beta\) を変数と見た終結式を計算します。
\begin{equation}
\Res(-x-2\alpha-\beta, \alpha^{2}+\alpha\beta+\beta^{2}-3; \beta) = x^2+3\alpha x+3\alpha^2-3 \label{galois-sol16-eq:5}
\end{equation}
さらに、今の結果と \(r_{1}\) の間で、\(\alpha\) を変数と見た終結式を計算します。
\begin{equation}
\Res(x^2+3\alpha x+3\alpha^2-3, \alpha^{3}-3\alpha-1; \alpha) = x^6-18x^4+81x^2-81 \label{galois-sol16-eq:6}
\end{equation}
得られた \(x^6-18x^4+81x^2-81\) がすべての \(V_{k}\) を根に持つ \(F(x)\) となります。たったこれだけです。
原理
なぜこれだけで \(F(x)\) が求まるのか説明しましょう。まず、\(f(x)=0\) の \(3\) 解 \(2\cos 20^\circ\), \(2\cos 140^\circ\), \(2\cos 260^\circ\) を \(\alpha_{1}\), \(\alpha_{2}\), \(\alpha_{3}\) とおきます。この \(3\) つに \(\alpha\), \(\beta\), \(\gamma\) というラベルを割り振る割り当て方は \(3!=6\) 通りあります。特に \(\alpha=\alpha_{1}\) としたとき、\(\beta\) のとりうる値は \(\alpha_{2}\), \(\alpha_{3}\) の \(2\) 通りで、これらを \(\beta^{(1)}_{1}\), \(\beta^{(1)}_{2}\) としましょう。同様に、\(\alpha=\alpha_{i}\) としたときに \(\beta\) のとりうる値を \(\beta^{(i)}_{1}\), \(\beta^{(i)}_{2}\) とします。
また、\(\alpha\), \(\beta\) のとる値を \(\alpha=\alpha_{i}\), \(\beta=\beta^{(i)}_{j}\) と決めたとき、 \(\gamma\) のとりうる値は一意に決まりますが、これを形式的に \(\gamma^{(i,j)}_{1}\) としましょう。例えば \(\gamma^{(1,1)}_{1} = \alpha_{3}\), \(\gamma^{(1,2)}_{1} = \alpha_{2}\) です。そうすると、\(6\) 通りのラベルの割り当て方は
\begin{align*}
\alpha &= \alpha_{i} && (i=1,2,3) \\
\beta &= \beta^{(i)}_{j} && (j=1,2) \\
\gamma &= \gamma^{(i,j)}_{k} && (k=1)
\end{align*}
と表され、
\begin{equation}
F(x) = \prod_{i=1}^{3} \prod_{j=1}^{2} \prod_{k=1}^{1} (x-\alpha_{i}-2\beta^{(i)}_{j}-3\gamma^{(i,j)}_{k}) \label{galois-sol16-eq:7}
\end{equation}
となります。
計算を進める前に、これらと \(r_{1}\), \(r_{2}\), \(r_{3}\) の関係をちょっと確認しておきます。
[a] \(\alpha_{i} \; (i=1,2,3)\) は\eqref{galois-sol16-eq:1}を \(\alpha\) の方程式と見たときの \(3\) 解です。
[b] \(\beta^{(i)}_{j} \; (j=1,2)\) は\eqref{galois-sol16-eq:2}で \(\alpha=\alpha_{i}\) とおいた \(\beta\) の方程式の \(2\) 解です。
[c] \(\gamma^{(i,j)}_{k} \; (k=1)\) は\eqref{galois-sol16-eq:3}で \(\alpha=\alpha_{i}\), \(\beta=\beta^{(i)}_{j}\) とおいた \(\gamma\) の方程式の \(1\) 解です。
[c]から、\eqref{galois-sol16-eq:7}のいちばん内側の積はこうなります。
\begin{equation}
\prod_{k=1}^{1} (x-\alpha_{i}-2\beta^{(i)}_{j}-3\gamma^{(i,j)}_{k}) = x+2\alpha_{i} + \beta^{(i)}_{j} \label{galois-sol16-eq:8}
\end{equation}
これは単に \(\gamma^{(i,j)}_{k}\) を消去しただけで、符号を除けば\eqref{galois-sol16-eq:4}と実質的に同じ計算です。つまり、\eqref{galois-sol16-eq:4}で \(\alpha=\alpha_{i}\), \(\beta=\beta^{(i)}_{j}\) としたものが\eqref{galois-sol16-eq:8}になっています。
これより、\eqref{galois-sol16-eq:7}の次の段階までの積はこうなります。
\begin{equation}
\prod_{j=1}^{2} \prod_{k=1}^{1} (x-\alpha_{i}-2\beta^{(i)}_{j}-3\gamma^{(i,j)}_{k}) = \prod_{j=1}^{2} (x+2\alpha_{i} + \beta^{(i)}_{j}) \label{galois-sol16-eq:9}
\end{equation}
[b]を考えると、\eqref{galois-sol16-eq:9}右辺の積は実質的に\eqref{galois-sol16-eq:5}と同じ計算です。つまり、\eqref{galois-sol16-eq:5}で \(\alpha=\alpha_{i}\) としたものが\eqref{galois-sol16-eq:9}と同じになり、したがって
\begin{equation*}
\eqref{galois-sol16-eq:9} = x^2+3\alpha_{i} x+3{\alpha_{i}}^2-3
\end{equation*}
となります。
よって、\eqref{galois-sol16-eq:7}の最終段階の積はこうです。
\begin{equation}
\prod_{i=1}^{3} \prod_{j=1}^{2} \prod_{k=1}^{1} (x-\alpha_{i} – 2\beta^{(i)}_{j} – 3\gamma^{(i,j)}_{k}) = \prod_{i=1}^{3} (x^2+3\alpha_{i} x+3{\alpha_{i}}^2-3) \label{galois-sol16-eq:10}
\end{equation}
[a]を考えると、\eqref{galois-sol16-eq:10}右辺の積は\eqref{galois-sol16-eq:6}と同じ計算です。つまり\eqref{galois-sol16-eq:6}によって \(F(x)\) が求まるわけです。
考察
以上の計算は、実は「退職後は素人数学者」さんの改良されたアルゴリズムと本質的には同じです。“≪g(x)の計算方法の改良≫”の部分で
第1列の \(x-v_{i}\; (i=1,2,\dots,24)\) を2個ずつ取って掛け合わせ,第2節で述べた方法により \(x_{1}\), \(x_{2}\), \(x_{3}\), \(x_{4}\) の次数を低減させて,その結果を第2列の \(g_{1k}(x) \; (k=1,2,\dots,12)\)とする。
とされている部分は、上の計算で2段階目までの終結式を計算するのと同じことをやっています。違いは、
- 「退職後は素人数学者」さんの計算だと、文字式の計算としては実質的に同じ計算の \(12\) 回の繰り返しになっている（文字が入れ替わっただけ）所を \(1\) 回で済ませている
- \(x_{3}\), \(x_{4}\) （など）の対称式の部分を多項式の割り算の繰り返しで文字消去している所を、終結式を用いて最初から文字消去された形で計算している
という点です。
同じように、
第2列の \(g_{1k}(x) \; (k=1,2,\dots,12)\) を3個ずつ取って掛け合わせ,第2節で述べた方法により \(x_1\), \(x_2\), \(x_3\), \(x_4\) の次数を低減させて,その結果を第3列の \(g_{2l}(x) \; (l=1,2,3,4)\) とする。このとき,\(g_{1k}(x)\) は \(x_1\), \(x_2\) だけからなるので, \(x_3\), \(x_4\) の次数低減は省略することができる。
とされている部分は、上の計算では3段階目の終結式の計算に相当します。
こういったことから、終結式法の方が多少効率は向上しているのではないかと思います。
各解を \(V\) で表す式
\(f(x)=0\) の各解を \(V\) の \(\Q\) 係数多項式で表す式の求め方として、jurupapa さんが当初使っていた方法を振り返ります。処理に時間がかかっていたのは、最初の段階「\(V\) と同じ位置（先頭）に \(\alpha\) を持つような \(V_{k}\) すべてを根に持つ多項式」を求める段階でした。
http://maxima.hatenablog.jp/entry/2017/10/28/124236
http://maxima.hatenablog.jp/entry/2018/11/04/171152
上の例なら、
\begin{equation}
(x-\alpha-2\beta-3\gamma) (x-\alpha-2\gamma-3\beta) \label{galois-sol16-eq:11}
\end{equation}
を、\(\Q(\alpha)\) 係数の多項式として求めることになります。これは、実は上の終結式の反復計算で、最後の\eqref{galois-sol16-eq:6}を計算する直前の結果\eqref{galois-sol16-eq:5}で得られています。つまり
\begin{equation*}
\eqref{galois-sol16-eq:11} = \eqref{galois-sol16-eq:5} = x^2+3\alpha x+3\alpha^2-3
\end{equation*}
です。なぜ終結式の反復計算で所期の式が得られるのかは、前節の計算過程を再度辿ってみればわかるでしょう。
これさえ出れば、あとは多項式の GCD 計算だけ（グレブナー基底を使ってもいいですね）で「\(\alpha\) を根に持つ \(\Q(V)\) 係数の \(1\) 次多項式」を求めることができ、目的の式が得られます。
このやり方だと、jurupapa さんが http://maxima.hatenablog.jp/entry/2018/11/04/171152 で
iMac corei5 2.7GHz (2013年のマシン)に8GBメモリ搭載のマシンを使い、SBCLという64bit版のLispでコンパイルしたMaxima 5.42.1に32GBのメモリを割り当てて計算したところ、時間は2時間、メモリ消費は最大17GB使いました。
と書かれていた \(f(x)=x^{5}-5x+12\) の計算も容易でした。
既に「代数拡大体上での既約分解」の技法によって、「各解を \(V\) の \(\Q\) 係数多項式で表す式」を十分高速に求める手法は確立しており、「どの根とどの解が対応するか」の同定に多少の試行錯誤が必要とは言え十分軽い処理で計算ができるようにはなっているので、ここで説明した計算は（その後に必要な計算量も考えると）実用上の優位性はないかもしれませんが、まあこんな手法もあるんだ、ということで。
\(\theta(x)\) の計算
以前、https://ikumi.que.jp/blog/archives/717 とその【追記】で \(\theta(x)\) の求め方の改良について述べましたが、改良をさらに向上させられることに気づきました。以下説明します。ただし、「べき根の選び方の不定性によって、\(0\) になる可能性もならない可能性もある式」はないものとします。
その記事通り、\(\theta_{1}(x) \: (\ne 0)\) の最高次係数を \(a\) とします（\(a\) は \(V\), \(\zeta\) の \(K\) 係数多項式）。このとき、
\begin{equation}
\theta_{1}(x) = a \eta_{1}(x) \label{galois-sol16-eq:12}
\end{equation}
（ただし、\(\eta_{1}(x)\) は \(x\) の \(K(\zeta) (=\tilde{K})\) 係数多項式）となるのでした。この \(\eta_{1}(x)\) を求める方針として、上掲記事では次の２通りを書きましたが、ここに実はまだ無駄がありました。
- \(\dfrac{\theta_{1}(x)}{a}\)（の各係数）は \(V\) の有理式であり、分母の有理化により \(V\) の多項式に直して整理
- \(a^{p-1}\theta_{1}(x)\)（の各係数）を \(V\) の多項式に直して整理
\eqref{galois-sol16-eq:12}の両辺を見比べると、\(x\) の各次数の係数について、次の形の等式が得られます。
\begin{equation}
\fbox{\(V\) の \(\tilde{K}\) 係数多項式} = \underbrace{a}_{\text{\(V\) の \(\tilde{K}\) 係数多項式}} \times \fbox{\(\tilde{K}\) の数} \label{galois-sol16-eq:13}
\end{equation}
左辺の枠内と \(a\) は既知、右辺の枠内は未知です。\(V\) は既知である部分にしか含まれていません。
今、\(\tilde{K}\) 上の \(V\) の最小多項式 \(g_{i}(x)\) がわかっているという想定なので、\eqref{galois-sol16-eq:13}で既知の部分の \(V\) の次数下げは２ヶ所とも終わっているとしてよいです。そうすると、「\(V\) の \(\tilde{K}\) 係数多項式」としての表現は\eqref{galois-sol16-eq:13}の左辺・右辺で一意的（※ ここで「べき根の選び方の不定性によって、\(0\) になる可能性もならない可能性もある式はない」という仮定を使っています）ですから、\eqref{galois-sol16-eq:13}は「左辺・右辺の \(V\) の各次数の係数ごとに等式がなりたつ」ような式になっています（※ ここがわかりにくければ、こう言い換えてみます。体 \(\tilde{K}(V)\) の \(\tilde{K}\) 係数ベクトル空間としての基底は、\(V\) に関して次数下げしてあれば \(1, V, V^{2}, \dotsc\) だから、両辺の \(V^{i}\) の係数どうしは一致する）。すなわち、\eqref{galois-sol16-eq:13}右辺枠内は「左辺を \(V\) の多項式として見たときの定数項」と「\(a\) を \(V\) の多項式として見たときの定数項」の比として決定できます。つまり体 \(\tilde{K}\) 内のみの割り算で算出可能です。「定数項」ではなく「最高次の係数」としても構いません（定数項だと両方とも \(0\) になりうる可能性があることを考えると、最高次の係数の方が汎用性があります）。
こうして、\(\eta_{1}(x)\) のすべての係数が具体的に計算できます。実際には、\(x\) の各次数ごとに別々に\eqref{galois-sol16-eq:13}を使うよりも、\eqref{galois-sol16-eq:12}の形のまま、「左辺を \(V\) の多項式として見たときの定数項（あるいは最高次の係数）」——\(x\) の \(\tilde{K}\) 係数多項式になります——と「\(a\) を \(V\) の多項式として見たときの定数項（あるいは最高次の係数）」——こちらは \(x\) は含まない、単なる \(\tilde{K}\) の数——の比として直接 \(\eta_{1}(x)\) を求める方がすっきりするでしょう。
続いて、\(\theta_{2}(x)\) は
\begin{equation*}
\theta_{2}(x) = a^{2} \eta_{2}(x)
\end{equation*}
（ただし、\(\eta_{2}(x)\) は \(x\) の \(\tilde{K}\) 係数多項式）となることが解っていました。この \(\eta_{2}(x)\) も未知ですが、\(a^{2}\) を計算して \(V\) の多項式として次数下げした形を求めておけば、\(\eta_{1}(x)\) と同じように \(V\) の最高次係数どうしの比をとることにより、\(x\) の \(\tilde{K}\) 係数多項式として具体的に求められます。
以下同様にして \(\eta_{1}(x), \dots, \eta_{p-1}(x)\) がすべて求められるので、別途 \(\theta_{p}(x)\) および \(a^{p}=A\) を求めておくことによって、\(h(x)\) を次のように求めることができます。
\begin{equation*}
h(x) = \frac{\theta_{1}(x) + \dots + \theta_{p}(x)}{p} = \frac{\sqrt[p]{A} \eta_{1}(x) + \sqrt[p]{A}^{2}\eta_{2}(x) + \dots + \sqrt[p]{A}^{p-1} \eta_{p-1}(x) + \theta_{p}(x)}{p}
\end{equation*}
コメントを残す