この Aurifeuille シリーズは2年ほどブランクがあって3回目。
前2回は Aurifeuillian 因数分解 と Aurifeuille 恒等式 について書いた。
今回は計算方法の一つを紹介する。
簡単にするためにあまり複雑な一般化は省いて、
平方因子を持たない 以上の整数 に対し、 を ならば 、そうでなければ とする。
このときある整数係数多項式 と により円分多項式 を という形(Aurifeuille 恒等式)に書ける。
この と を求める方法を見ていきたい。
の時のように整数 の因数分解をして 進数展開から求めるのは、いろいろ問題がある。
整数の因数分解自体が難しいし、 以上の係数や負の係数が必要になると破綻してしまう。
一般的に使える方法は、もっと代数的な議論だ。
前に見たように が で平方数になっているというのがキーだった。
ここで紹介する Stevenhagen の方法は、 が に入っているならば、 の多項式で表せるという事実に基づいている。
具体的な を表す の多項式が
と与えられる。実際 に を代入すると、
乗は を にし、 の分の で括った残りは から へのトレースになりそれは値として だから結局 となる。
この と にユークリッドの互除法を適用する。
余りの次数が段階的に下がっていくが、最初に 以下になった多項式を とし、次の段階の多項式を とする。
このとき、 の定数項を の適当な有理数 倍で消したもの を とおくと、
を先頭項係数 で割ったものが 、逆にその を に掛けたものの符号を調整すると となる。
という形で と が求められる。
最後の部分が不思議な感じなのでもう少し補足しておく。
補助的な多項式 を , から始めて、
とユークリッドの互除法を行変形と見ていくと、行列式は符号を除いて一定である。
定数項を消す処理も行変形なので
が得られる。
一方 Aurifeuille 恒等式は
と表現できる。
最後の二つの式の右辺の要素同士が(符号を除いて)等しいことが言える(詳しくは参考文献を)ので上のようなアルゴリズムとなる。
例として としてみよう。 だ。
以上 以下かつ と互いに素かつヤコビ記号 が
という条件を満たすのは なので、
だ。
この と円分多項式 にユークリッドの互除法を適用する。
ここで の次数が 以下なので、 、 とする。
の定数項 を で消すために とする。
これを で割って
を得る。
の先頭係数は なので、
よって
を得る。
参考文献
P. Stevenhagen "On Aurifeullian factorizations Indagationes Mathematicae (Proceedings), Volume 90, Issue 4, 1987, Pages 451-468