この Aurifeuille シリーズは2年ほどブランクがあって3回目。 前2回は Aurifeuillian 因数分解 と Aurifeuille 恒等式 について書いた。 今回は計算方法の一つを紹介する。
簡単にするためにあまり複雑な一般化は省いて、 平方因子を持たない \(2\) 以上の整数 \(k\) に対し、\(n\) を \(k \equiv 1 \pmod{4}\) ならば \(k\)、そうでなければ \(2k\) とする。 このときある整数係数多項式 \(F\) と \(G\) により円分多項式 \(\Phi_n(X)\) を \(F(X)^2 - kX G(X)^2\) という形(Aurifeuille 恒等式)に書ける。 この \(F\) と \(G\) を求める方法を見ていきたい。
\(k=5\) の時のように整数 \(\Phi_n(k)\) の因数分解をして \(k\) 進数展開から求めるのは、いろいろ問題がある。 整数の因数分解自体が難しいし、\(k\) 以上の係数や負の係数が必要になると破綻してしまう。 一般的に使える方法は、もっと代数的な議論だ。
前に見たように \(k\zeta_n\) が \(\mathbb{Q}[\zeta_n]\) で平方数になっているというのがキーだった。 ここで紹介する Stevenhagen の方法は、\(\sqrt{k\zeta_n}\) が \(\mathbb{Q}[\zeta_n]\) に入っているならば、\(\zeta_n\) の多項式で表せるという事実に基づいている。
具体的な \(\sqrt{k\zeta_n}\) を表す \(\zeta_n\) の多項式が \[H(X) = \sum_{1 \leq a \leq 2n \land (a, 2n) =1 \land (\frac{k}{a})=1} X^{(a+1)/2}\] と与えられる。実際 \(X\) に \(\zeta_n\) を代入すると、 \(1/2\) 乗は \(\zeta_n\) を \(\zeta_{2n}\) にし、 \(+1\) の分の \(\zeta_{2n}\) で括った残りは \(\mathbb{Q}(\zeta_2n)\) から \(\mathbb{Q}(\sqrt{k})\) へのトレースになりそれは値として \(\sqrt{k}\) だから結局 \(\zeta_{2n}\sqrt{k} = \sqrt{k\zeta_n}\) となる。 この \(H\) と \(\Phi_n\) にユークリッドの互除法を適用する。 余りの次数が段階的に下がっていくが、最初に \(\phi(n)/2\) 以下になった多項式を \(f\) とし、次の段階の多項式を \(f^*\) とする。 このとき、\(f^*\) の定数項を \(f\) の適当な有理数 \(\alpha\) 倍で消したもの \(f^*-\alpha f\) を \(Xg\) とおくと、 \(f\) を先頭項係数 \(c\) で割ったものが \(F\)、逆にその \(c\) を \(g\) に掛けたものの符号を調整すると \(k G\) となる。 という形で \(F\) と \(G\) が求められる。
最後の部分が不思議な感じなのでもう少し補足しておく。 補助的な多項式 \(\gamma_i\) を \(\gamma_0 = 1\), \(\gamma_1 = 0\) から始めて、 \[ \Phi_n = \begin{vmatrix} 1 & H \\ 0 & \Phi_n \end{vmatrix} = \pm\begin{vmatrix} \gamma_i & f_i\\ \gamma_{i+1} & f_{i+1}\end{vmatrix}\] とユークリッドの互除法を行変形と見ていくと、行列式は符号を除いて一定である。 定数項を消す処理も行変形なので \[ \Phi_n = \pm\begin{vmatrix} \gamma & f\\ \gamma^* & f^*\end{vmatrix} = \pm\begin{vmatrix} \gamma & f \\ \gamma' & Xg \end{vmatrix}\] が得られる。 一方 Aurifeuille 恒等式は \[ \Phi_n = \begin{vmatrix} cG & cF \\ c^{-1}F & c^{-1} X k G\end{vmatrix}\] と表現できる。 最後の二つの式の右辺の要素同士が(符号を除いて)等しいことが言える(詳しくは参考文献を)ので上のようなアルゴリズムとなる。
例として \(k=7\) としてみよう。\(n=14\) だ。 \(1\) 以上 \(28\) 以下かつ \(28\) と互いに素かつヤコビ記号 \(\left(\frac{7}{a}\right)\) が \(1\) という条件を満たすのは \(a \in \{1,3,9,19,25,27\}\) なので、 \[H_{14}(X) = X + X^2 + X^5 + X^{10} + X^{13} + X^{14}\] だ。 この \(f_0=H_{14}\) と円分多項式 \(f_1=\Phi_{14}\) にユークリッドの互除法を適用する。 \[f_2(X) = f_0(X) \bmod f_1(X) = X^4 - 2 X^3 + 2 X^2 + 2\] \[f_3(X) = f_1(X) \bmod f_2(X) = -X^3 - 3 X^2 - 3 X - 1\] \[f_4(X) = f_2(X) \bmod f_3(X) = 14 X^2 + 14 X + 7\] ここで \(f_3\) の次数が \(\phi(14)/2=3\) 以下なので、\(f = f_3\) 、\(f^* = f_4\) とする。 \(f^*\) の定数項 \(7\) を \(f\) で消すために \(\alpha=-7\) とする。 \[f^*(X) - \alpha f(X) = -7 X^3 -7 X^2 -7 X\] これを \(X\) で割って \[g(X) = -7 X^2 -7 X -7\] を得る。 \(f\) の先頭係数は \(-1\) なので、 \[F(X) = -f(X) = X^3 + 3 X^2 + 3 X + 1\] \[G(X) = -g(X) / 7 = X^2 + X + 1\] よって \[\Phi_{14}(X) = (X^3 + 3 X^2 + 3 X + 1)^2 - 7X (X^2 + X + 1)^2\] を得る。
参考文献
P. Stevenhagen "On Aurifeullian factorizations Indagationes Mathematicae (Proceedings), Volume 90, Issue 4, 1987, Pages 451-468