この記事のコードをJupyter notebook形式で見るにはこちら。
引き続きジョージア工科大学のMatt Baker教授のブログから、リュカ多項式による平方剰余の相互法則の証明を説明します。
前回(1)では終結式について解説しました。終結式の性質として以下の4つを説明しました。
R1 \(f,\,g \in Z[X]\) ならば \(resultant\left(f,g,X\right) \in Z\)
R2 \(resultant\left(f,g\right) \equiv resultant\left(f,g\, mod\, d\right)\,mod\,d\)
R3 \(resultant\left(f,g,x\right)=\prod_{i=1}^m{g\left(a_i\right)}\)
R4 \({\it resultant}\left(f\left(x\right) , g\left(x\right) , x\right) \\ =\left(-1\right)^{{\it hipow}\left(f\left(x\right) , x\right)\,{\it hipow}\left(g\left(x\right) , x\right)}\,{\it resultant}\left(g\left(x\right) , f\left(x\right) , x\right)\)
そして最後のR4と平方剰余の相互法則を見比べることで、次の2つの性質を満たす\(F_n\left(x\right)\)が存在すれば、相互法則の証明が完成することを知りました。
\( {\it resultant}\left(F_{p}(x) , F_{q}(x)\right)={\it jacobi}\left(p , q\right) \)
\({\it hipow}\left(F_{n}(x) , x\right)=\frac{n-1}{2}\)
これからリュカ多項式\(LP_n\left(x\right)\)とその変形\(H_n\left(x\right)\)を導入します。そしてこの\(H_n\left(x\right)\)こそが上記の2つの性質を満たす、求める多項式であることを示します。
リュカ多項式\(LP_n\left(x\right)\)はフィボナッチ数と同じように、最初の２項を指定した多項式列として定義されます。
(%i1) LP[0](x):=2;
$$ \tag{${\it \%o}_{1}$}{\it LP}_{0}(x):=2 $$
(%i2) LP[1](x):=x;
$$ \tag{${\it \%o}_{2}$}{\it LP}_{1}(x):=x $$
(%i3) LP[n](x):=x*LP[n-1](x)+LP[n-2](x);
$$ \tag{${\it \%o}_{3}$}{\it LP}_{n}(x):=x\,{\it LP}_{n-1}(x)+{\it LP}_{n-2}(x) $$
これで定義は終了です。うまく定義できているか試してみます。
(%i4) for n:1 thru 11 step 2 do print(expand('LP[n](x)=LP[n](x)));
\({\it LP}_{1}(x)=x\)
\({\it LP}_{3}(x)=x^3+3\,x\)
\({\it LP}_{5}(x)=x^5+5\,x^3+5\,x\)
\({\it LP}_{7}(x)=x^7+7\,x^5+14\,x^3+7\,x\)
\({\it LP}_{9}(x)=x^9+9\,x^7+27\,x^5+30\,x^3+9\,x\)
\({\it LP}_{11}(x)=x^{11}+11\,x^9+44\,x^7+77\,x^5+55\,x^3+11\,x\)
$$ \tag{${\it \%o}_{4}$}\mathbf{done} $$
実はこの記事では奇数番目、もっというと奇素数番目のリュカ多項式しか興味がありません。上の実行例では奇数番目のリュカ多項式を計算してみました。いくつか気がつくことがあります。
すべてのn番目のリュカ多項式の次数はnです。すべての奇数番目のリュカ多項式では、定数項がゼロです。また1次の項の係数はnになっています。さらに偶数次数の項の係数はすべて0です。これらはすべて数学的帰納法で証明できます。
さて定数項が0ですべて奇数次数の項しか無い、ということから、\(LP_n\left(x\right)\)の各項の次数から1を引き2で割った多項式を考えることができます。この多項式を\(H_n\left(x\right)\)として導入します。
(%i5) H[n](x):=if oddp(n) then ratsubst(x,x^2,expand(LP[n](x)/x)) else ratsubst(x,x^2,expand(LP[n](x)));
$$ \tag{${\it \%o}_{5}$}H_{n}(x):=\mathbf{if}\;{\it oddp}\left(n\right)\;\mathbf{then}\;{\it ratsubst}\left(x , x^2 , {\it expand}\left(\frac{{\it LP}_{n}(x)}{x}\right)\right)\;\mathbf{else}\;{\it ratsubst}\left(x , x^2 , {\it expand}\left({\it LP}_{n}(x)\right)\right) $$
早速奇数番目の\(H_n\left(x\right)\)を計算してみましょう。
(%i6) for n:1 thru 11 step 2 do print('H[n](x)=expand(H[n](x)));
\(H_{1}(x)=1\)
\(H_{3}(x)=x+3\)
\(H_{5}(x)=x^2+5\,x+5\)
\(H_{7}(x)=x^3+7\,x^2+14\,x+7\)
\(H_{9}(x)=x^4+9\,x^3+27\,x^2+30\,x+9\)
\(H_{11}(x)=x^5+11\,x^4+44\,x^3+77\,x^2+55\,x+11\)
$$ \tag{${\it \%o}_{6}$}\mathbf{done} $$
これが所望の多項式であり、最初に述べた2つの条件を満たすのです。
ここから\(H_n\left(x\right)\)の性質を示していきます。まず次数から片付けましょう。\(H_n\left(x\right)\)は\(LP_n\left(x\right)\)は各項の次数を1引いて2で割って得られたものです。つまり\(H_n\left(x\right)\)の次数は\(\frac{n-1}{2}\)です。maximaの組み込み関数hipow(f,x)を使っていくつかのnについて\(H_n\left(x\right)\)の次数を求めてみましょう。
(%i11) [hipow(H[7](x),x),hipow(H[17](x),x),hipow(H[19](x),x)];
$$ \tag{${\it \%o}_{11}$}\left[ 3 , 8 , 9 \right] $$
確かにそうなっていますね。
次に\(H_n\left(0\right)=n\)を確認しましょう。
(%i12) [H[7](0),H[17](0),H[19](0)];
$$ \tag{${\it \%o}_{12}$}\left[ 7 , 17 , 19 \right] $$
確かにそうなっています。これは対応するリュカ多項式の定数項を考えると自明です。
次は係数の性質です。%i6の計算で実はpを奇素数として\(H_p\left(x\right) \equiv x^p\)つまり\(x^p\)以外の項の係数はすべてmod pで0なのです（n=9の時は30という係数が見えますが、9は素数では無いので関係ありません）。
maximaの組み込み関数polymod(poly,p)で確認してみましょう。
(%i13) [polymod(H[7](x),7),polymod(H[17](x),17),polymod(H[19](x),19)];
$$ \tag{${\it \%o}_{13}$}\left[ x^3 , x^8 , x^9 \right] $$
この証明はリュカ多項式列の一般項を求めれば、そこからは自明です。一般項の計算は別の機会に譲ることにします。
いよいよ最も重要な性質である、p,qを異なる奇素数として、\(H_{p}\left(x\right)\)と\(H_{q}\left(x\right)\)の終結式がヤコビ記号（ルジャンドル記号）と一致することを見ます。
(%i14) [resultant(H[7](x),H[11](x),x),resultant(H[19](x),H[11](x),x),resultant(H[19](x),H[3](x),x),resultant(H[21](x),H[5](x),x)];
$$ \tag{${\it \%o}_{14}$}\left[ 1 , 1 , -1 , 1 \right] $$
(%i15) [jacobi(11,7),jacobi(11,19),jacobi(3,19),jacobi(5,21)];
$$ \tag{${\it \%o}_{15}$}\left[ 1 , 1 , -1 , 1 \right] $$
計算してみると見事に一致していることがわかります。一応その理屈を追ってみましょう。まず%o16が成り立ちます。これは終結式の性質R2（上の方をみてください）からでます。
(%i16) 'resultant('H[p](x),'H[q](x),x)=mod('resultant(x^( (p-1)/2),'H[q](x) ),p);
$$ \tag{${\it \%o}_{16}$}{\it resultant}\left(H_{p}(x) , H_{q}(x) , x\right)={\it resultant}\left(x^{\frac{p-1}{2}} , H_{q}(x)\right) \rm{mod} p $$
ところで任意の多項式fについて%o17が成り立ちます。これは終結式の性質R3及びf(0)はfの根をすべてかけたもの、という根と係数の関係からわかります。
(%i17) 'resultant(x^n,'f(x))=f(0)^n;
$$ \tag{${\it \%o}_{17}$}{\it resultant}\left(x^{n} , f\left(x\right)\right)=f\left(0\right)^{n} $$
念のため簡単な例で試してみましょう。
(%i18) resultant(x^6,x^2+3*x+a,x);
$$ \tag{${\it \%o}_{18}$}a^6 $$
この事実を使うと%o19がわかります。
(%i19) 'resultant(x^((p-1)/2),'H[q](x),x)='H[q](0)^((p-1)/2);
$$ \tag{${\it \%o}_{19}$}{\it resultant}\left(x^{\frac{p-1}{2}} , H_{q}(x) , x\right)=H_{q}(0)^{\frac{p-1}{2}} $$
ところで\(H_{n}\left(0\right)=n\)でしたから%o20が成り立ちます。
(%i20) 'H[q](0)^((p-1)/2)=q^((p-1)/2);
$$ \tag{${\it \%o}_{20}$}H_{q}(0)^{\frac{p-1}{2}}=q^{\frac{p-1}{2}} $$
この右辺、知っていますよね。平方剰余で登場するオイラーの規準の右辺です。一応オイラーの規準を再掲します。
\(jacobi(p,q) \equiv q^{\frac{p-1}{2}}\, mod\, p\)
従って最初と最後を繋ぐと、
\({\it resultant}\left(H_{p}(x) , H_{q}(x) , x\right) \equiv jacobe(p,q)\,mod\,p\)
一方、左辺の終結式は（別途証明が必要ですが）必ず1 or -1になることがわかっているので、上記式は等号で成り立ちます。つまり、
\({\it resultant}\left(H_{p}(x) , H_{q}(x) , x\right) = jacobe(p,q)\)
というわけで、証明終了です。
それにしても奇妙な証明です。数論っぽい議論が出てくるのはオイラーの規準を使ったところくらいです。終結式は、数式処理などではよく出てくるのですが、数論とは縁遠い、という印象です。2次体とか円分体とかもう全く出てきません。それにここで定義したリュカ多項式にはどんな意味があるのか、、、。
