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