Aurifeuille 恒等式の計算方法 (Brent)

Brent による Aurifeuille 恒等式の計算方法を紹介していく。 Brent によれば Stevenhagen の方法は互除法の係数爆発が起きるので次数の大きな円分多項式には適用できないとのことである。 Stevenhagen の方法は実質的に「\(\sqrt{k\zeta_n}\) が \(\mathbb{Q}[\zeta_n]\) に入っているならば、\(\zeta_n\) の多項式で表せる」という事実しか使わなかったが、Brent の方法ではもう少し特殊事情を考えて多項式の係数を決定していく。

あまり複雑な一般化は省いて、 平方因子を持たない \(3\) 以上の奇数 \(k\) に対し、\(n\) を \(k\equiv 1\pmod 4\) ならば \(k\)、そうでなければ \(2k\) とする。 \(\zeta = \zeta_{2n}\) とすると \(\mathbb{Q}[\zeta]\) の \(\mathbb{Q}\) 上のガロワ群は \(\left(\mathbb{Z}/2n\mathbb{Z}\right)^{\times}\) と同型である。 \(\mathbb{Q}[\zeta]\)　に含まれる実2次体 \(\mathbb{Q}[\sqrt{k}]\) に対応する指数 \(2\) の部分群 \(H\) を見つけられる。 具体的には \(H=\left\{\pm a \in \left(\mathbb{Z}/2n\mathbb{Z}\right)^{\times} | 1 \leq a \leq n \land (\frac{k}{a})=1\right\}\) だ。

\[L(X) = \prod_{a\in H}(X - \zeta^a)\] を考えると実は \[L(X) = F(X^2) - \left(\frac{2}{k}\right) X\sqrt{k} G(X^2)\] となることが Schinzel によって示されているそうだ(論文を参照できていないので伝聞)。 つまり、偶数次の項を拾うと \(F\) が得られて奇数次の項を拾うと \(G\) が得られるのだ。 具体的な係数を得るには次のように考えればいい。 \(L(X)\) の係数は根が与えられているので解と係数の関係から計算できる。 そこに現れる根の対称式はその冪和で書き表せる(Newton の恒等式)。 \(1\) の冪根の冪和はガロワ群の作用を考えると簡単に表せる(ガウス周期)。

ガロワ群の元 \(b\) は \(\zeta\) に対し \(\zeta^b\) として作用する。 \(L(X)\) の根の冪和を \[p_b = \sum_{a \in H} \zeta^{ab}\] と書くことにしよう。 \(L(X)\) の根の和 \(p_1 = \sum_{a\in H} \zeta^a\) はもちろん \(H\) の各元の作用で不変である。 また、\(p_1^2 = k\) であるから、\(p_1 = \sqrt{k}\) と考えて良い。 一方、\(H\) のコセットの各元の作用では \(-p_1\) に移る。 これらが \(1 \leq b \leq 2n\) の内、\(2n\) と互いに素な \(b\) による \(b\) 乗和に相当する。 残る \(2n\) との最大公約数 \(\Gamma_{b} = (b, 2n)\) が \(1\) より大きい場合で、\(b\) が偶数ならば \[p_b = \sum_{a \in H} \zeta^{ab} = \mu(2n/ \Gamma_b) \phi(\Gamma_b / 2) \in \mathbb{Z}\] となることが知られている。 \(b\) が奇数ならば \(0\) になる。 以上で根の冪和が決定できた。

奇数冪に現れる \(\sqrt{k}\) を最初から括って、残りの整数係数部分だけを考える。 \(F\) と \(G\) は相反多項式なので半分の次数まで計算すればいい。 といった工夫により、整数の計算だけを行えばいいことになる。

先に \(d=\phi(n)/2\) とおいて \(F\) と \(G\) を \[F(X) = \sum_{j=0}^{d}f_j X^{d-j}\] \[G(X) = \sum_{j=0}^{d - 1}g_j X^{d-j-1}\] と表すことにしよう。 モニックであることは判っているので \(f_0 = g_0 = 1\) である、ということは後ほど使う。 目標は \(f_j\), \(g_j\) を求めることだ。

ステップ1では、根の冪和に相当する(\(\sqrt{k}\) の因子は取り除いた)数として、\(q_j\) を求める。 必要なのは \(1 \leq j \leq d\) の範囲だ。 \(j\) が奇数の時 \(q_j = \left(\frac{k}{j}\right)\)、偶数の時 \(q_j = \mu(2n/\Gamma_j)\phi(\Gamma_j/2)\) とすれば良い。

ステップ2では、Newton の恒等式から導かれる次の漸化式を \(j = 1\) から次数の半分まで順に解く。 \[f_j = \frac{1}{2j}\sum_{i=0}^{j-1}\left(k q_{2j-2i-1} g_i - q_{2j - 2i} f_i \right)\] \[g_j = \frac{1}{2j+1}\left(f_j + \sum_{i=0}^{j-1}\left(q_{2j-2i+1} f_i - q_{2j - 2i} g_i \right)\right)\] 初期値は上で述べた \(f_0 = g_0 = 1\) だ。

ステップ3(最後のステップ)では、相反多項式であることを利用して \(F\), \(G\) それぞれの次数まで \(f_j = f_{d-j}\), \(g_j = g_{d-j-1}\) を求める。 これで計算終了だ。

例として前回と同じ \(k=7\) を計算しよう。 \(n = 14\), \(d=\phi(14)/2 = 3\) となる。

ステップ1。\(q_1=1\), \(q_2 = 1\)、\(q_3 = 1\)。

ステップ2は \(d/2 = 3/2\) なので \(f_1\), \(g_1\) を計算すれば十分。 \[f_1 = \frac{1}{2} \left(7 q_1 g_0 - q_2 f_0\right) = \frac{1}{2} (7 - 1) = 3\] \[g_1 = \frac{1}{3} \left(f_1 + q_3 f_0 - q_2 g_0\right) = \frac{1}{3} (3+1 - 1) = 1\]

ステップ3。\(f_2=f_1=3\), \(f_3=f_0=1\), \(g_2=g_0=1\)。

したがって、 \[\Phi_{14}(X)= (X^3 + 3 X^2 + 3 X + 1)^2 - 7X (X^2 + X + 1)^2\] が得られた。

確かに Stevenhagen の方法より無駄が少なそうだ。

参考文献

Richard P. Brent "Computing Aurifeullian Factors" in Computational Algebra and Number Theory, Mathematics and its Applications Vol. 325, 1995, Pages 201-212

Aurifeuille 恒等式の計算方法 (Stevenhagen)

この 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