代数的数に関する演算
**********

代数的数の表現
=======

Asir においては, 代数体という対象は定義されない. 独立した対象として定義されるのは, 代数的数である. 代数体は, 有理数体に, 代数的数を有限個順次添加した体として仮想的に定義される. 新たな代数的数は, 有理数およびこれまで定義された代数的数の多項式を係数とする 1 変数多項式を定義多項式として定義される. 以下, ある定義多項式の根として定義された代数的数を, root と呼ぶことにする.

     [0] A0=newalg(x^2+1);
     (#0)
     [1] A1=newalg(x^3+A0*x+A0);
     (#1)
     [2]  [type(A0),ntype(A0)];
     [1,2]

この例では, A0 は x^2+1=0 の根, A1 は, その A0 を係数に含む x^3+A0*x+A0=0 の根として定義されている.

newalg() の引数すなわち定義多項式には次のような制限がある.

 1. 定義多項式は 1 変数多項式でなければならない.

 2. newalg() の引数である定義多項式は, 代数的数を含む式の簡単化のために用いられる. この簡単化は, 組み込み函数 srem() に相当する内部ルーチンを用いて行われる. このため, 定義多項式の主係数は, 有理数になっている必要がある.

 3. 定義多項式の係数は すでに定義されている root の有理数係数多項式でなければならない.

 4. 定義多項式は, その係数に含まれる全ての root を有理数に添加した体上で既約でなければならない.

newalg() が行う引数チェックは, 1 および 2 のみである. 特に, 引数の定義多項式の既約性は全くチェックされない. これは既約性のチェックが多大な計算量を必要とするためで, この点に関しては, ユーザの責任に任されている.

一旦 newalg() によって定義された代数的数は, 数としての識別子を持ち, また, 数の中では代数的数としての識別子を持つ. (type(), vtype() 参照.) さらに, 有理数と, root の有理式も同様に代数的数となる.

     [87] N=(A0^2+A1)/(A1^2-A0-1);
     ((#1+#0^2)/(#1^2-#0-1))
     [88] [type(N),ntype(N)];
     [1,2]

例からわかるように, rootは #N と表示される. しかし, ユーザはこの形では入力できない. root は変数に格納して用いるか, あるいは alg(N) により取り出す. また, 効率は落ちるが, 全く同じ引数 (変数は異なっていてもよい) により newalg() を呼べば, 新しい代数的数は定義されずに既に定義されたものが得られる.

     [90] alg(0);
     (#0)
     [91] newalg(t^2+1);
     (#0)

root の定義多項式は, defpoly() により取り出せる.

     [96] defpoly(A0);
     t#0^2+1
     [97] defpoly(A1);
     t#1^3+t#0*t#1+t#0

ここで現れた, t#0, t#1 はそれぞれ #0, #1 に対応する不定元である. これらもユーザが入力することはできない. var() で取り出すか, あるいは algv(N) により取り出す.

     [98] var(@);
     t#1
     [99] algv(0);
     t#0
     [100]

代数的数の演算
=======

前節で, 代数的数の表現, 定義について述べた. ここでは, 代数的数を用いた演算について述べる. 代数的数に関しては, 組み込み函数として提供されている機能はごく少数で, 大部分はユーザ定義函数により実現されている. ファイルは, sp で, gr と同様 Asir の標準ライブラリディレクトリにおかれている.

     [0] load("gr")$
     [1] load("sp")$

あるいは, 常に用いるならば, $HOME/.asirrc に書いておくのもよい.

root は その他の数と同様, 四則演算が可能となる. しかし, 定義多項式による簡単化は自動的には行われないので, ユーザの判断で適宜行わなければならない. 特に, 分母が 0 になる場合に致命的なエラーとなるため, 実際に分母を持つ代数的数を生成する場合には細心の注意が必要となる.

代数的数の, 定義多項式による簡単化は, simpalg() で行う.

     [49] T=A0^2+1;
     (#0^2+1)
     [50] simpalg(T);
     0

simpalg() は有理式の形をした代数的数を, 多項式の形に簡単化する.

     [39] A0=newalg(x^2+1);
     (#0)
     [40] T=(A0^2+A0+1)/(A0+3);
     ((#0^2+#0+1)/(#0+3))
     [41] simpalg(T);
     (3/10*#0+1/10)
     [42] T=1/(A0^2+1);
     ((1)/(#0^2+1))
     [43] simpalg(T);
     div : division by 0
     stopped in invalgp at line 258 in file "/usr/local/lib/asir/sp"
     258                     return 1/A;
     (debug)

この例では, 分母が 0 の代数的数を簡単化しようとして 0 による除算が生じたため, ユーザ定義函数である simpalg() の中でデバッガが呼ばれたことを示す. simpalg() は, 代数的数を係数とする多項式の各係数を簡単化できる.

     [43] simpalg(1/A0*x+1/(A0+1));
     (-#0)*x+(-1/2*#0+1/2)

代数的数を係数とする多項式の基本演算は, 適宜 simpalg() を呼ぶことを除けば通常の場合と同様であるが, 因数分解などで頻繁に用いられるノルムの計算などにおいては, root を不定元に置き換える必要が出てくる. この場合, algptorat() を用いる.

     [83] A0=newalg(x^2+1);
     (#0)
     [84] A1=newalg(x^3+A0*x+A0);
     (#1)
     [85] T=(2*A0+A1*A0+A1^2)*x+(1+A1)/(2+A0);
     (#1^2+#0*#1+2*#0)*x+((#1+1)/(#0+2))
     [86] S=algptorat(T);
     (((t#0+2)*t#1^2+(t#0^2+2*t#0)*t#1+2*t#0^2+4*t#0)*x+t#1+1)/(t#0+2)
     [87] algptorat(coef(T,1));
     t#1^2+t#0*t#1+2*t#0

このように, algptorat() は, 多項式, 数に含まれる root を, 対応する不定元, すなわち #N に対する t#N に置き換える. 既に述べたように, この不定元はユーザが入力することはできない. これは, ユーザの入力した不定元と, root に対応する不定元が一致しないようにするためである.

逆に, root に対応する不定元を, 対応する root に置き換えるためには rattoalgp() を用いる.

     [88] rattoalgp(S,[alg(0)]);
     (((#0+2)/(#0+2))*t#1^2+((#0^2+2*#0)/(#0+2))*t#1+((2*#0^2+4*#0)/(#0+2)))*x
     +((1)/(#0+2))*t#1+((1)/(#0+2))
     [89] rattoalgp(S,[alg(0),alg(1)]);
     (((#0^3+6*#0^2+12*#0+8)*#1^2+(#0^4+6*#0^3+12*#0^2+8*#0)*#1+2*#0^4+12*#0^3
     +24*#0^2+16*#0)/(#0^3+6*#0^2+12*#0+8))*x+(((#0+2)*#1+#0+2)/(#0^2+4*#0+4))
     [90] rattoalgp(S,[alg(1),alg(0)]);
     (((#0+2)*#1^2+(#0^2+2*#0)*#1+2*#0^2+4*#0)/(#0+2))*x+((#1+1)/(#0+2))
     [91] simpalg(@89);
     (#1^2+#0*#1+2*#0)*x+((-1/5*#0+2/5)*#1-1/5*#0+2/5)
     [92] simpalg(@90);
     (#1^2+#0*#1+2*#0)*x+((-1/5*#0+2/5)*#1-1/5*#0+2/5)

rattoalgp() は, 置換の対象となる root のリストを第 2 引数にとり, 左から順に, 対応する不定元を置き換えて行く. この例は, 置換する順序を換えると簡単化を行わないことにより結果が一見異なるが, 簡単化により実は一致することを示している. algptorat(), rattoalgp() は, ユーザが独自の簡単化を行いたい場合などにも用いることができる.

代数体上での 1 変数多項式の演算
=================

sp では, 1 変数多項式に限り, GCD, 因数分解およびそれらの応用として最小分解体を求める函数を提供している.

GCD
---

代数体上での GCD は gcda() により計算される. この函数はモジュラ演算および中国剰余定理により代数体上の GCD を計算するもので, 逐次拡大に対しても有効である.

     [63] A=newalg(t^9-15*t^6-87*t^3-125);
     (#0)
     [64] B=newalg(75*s^2+(10*A^7-175*A^4-470*A)*s+3*A^8-45*A^5-261*A^2);
     (#1)
     [65] P1=75*x^2+(150*B+10*A^7-175*A^4-395*A)*x+(75*B^2+(10*A^7-175*A^4-395*A)*B
     +13*A^8-220*A^5-581*A^2)$
     [66] P2=x^2+A*x+A^2$
     [67] gcda(P1,P2,[B,A]);
     27*x+((#0^6-19*#0^3-65)*#1-#0^7+19*#0^4+38*#0)

無平方分解, 因数分解
-----------

無平方分解は, 多項式とその微分との GCD の計算から始まるもっとも一般的なアルゴリズムを採用している. 函数は asq() である.

     [116] A=newalg(x^2+x+1);
     (#4)
     [117] T=simpalg((x+A+1)*(x^2-2*A-3)^2*(x^3-x-A)^2);
     x^11+(#4+1)*x^10+(-4*#4-8)*x^9+(-10*#4-4)*x^8+(16*#4+20)*x^7+(24*#4-6)*x^6
     +(-29*#4-31)*x^5+(-15*#4+28)*x^4+(38*#4+29)*x^3+(#4-23)*x^2+(-21*#4-7)*x
     +(3*#4+8)
     [118] asq(T);
     [[x^5+(-2*#4-4)*x^3+(-#4)*x^2+(2*#4+3)*x+(#4-2),2],[x+(#4+1),1]]

結果は通常と同様に, [因子, 重複度] のリストとなるが, 全ての因子の積は, もとの多項式と定数倍の差はあり得る. これは, 因子を整数係数にして見やすくするためで, 因数分解でも同様である.

代数体上での因数分解は, Trager によるノルム法を改良したもので, 特にある多項式に対し, その根を添加した体上でその多項式自身を因数分解する場合に特に有効である.

     [119] af(T,[A]);
     [[x^3-x+(-#4),2],[x^2+(-2*#4-3),2],[x+(#4+1),1]]

引数は 2 つで, 第 2 引数は, root のリストである. 因数分解は有理数体に, それらの root を添加した体上で行われる. root の順序には制限がある. すなわち, 後で定義されたものほど前の方にこなければならない. 並べ換えは, 自動的には行われない. ユーザの責任となる.

ノルムを用いた因数分解においては, ノルムの計算と整数係数 1 変数多項式の因数分解の効率が, 全体の効率を左右する. このうち, 特に高次の多項式の場合に後者において組合せ爆発により計算不能になる場合がしばしば生ずる.

     [120] B=newalg(x^2-2*A-3);
     (#5)
     [121] af(T,[B,A]);
     [[x+(#5),2],[x^3-x+(-#4),2],[x+(-#5),2],[x+(#4+1),1]]

最小分解体
-----

やや特殊な演算ではあるが, 前節の因数分解を反復適用することにより, 多項式の最小分解体を求めることができる. 函数は sp() である.

     [103] sp(x^5-2);
     [[x+(-#1),2*x+(#0^3*#1^3+#0^4*#1^2+2*#1+2*#0),2*x+(-#0^4*#1^2),2*x
     +(-#0^3*#1^3),x+(-#0)],[[(#1),t#1^4+t#0*t#1^3+t#0^2*t#1^2+t#0^3*t#1+t#0^4],
     [(#0),t#0^5-2]]]

sp() は 1 引数で, 結果は [1 次因子のリスト, [[root, algptorat(定義多項式)] のリスト] なるリストである. 第 2 要素の [root,algptorat(定義多項式)] のリストは, 右から順に, 最小分解体が得られるまで添加していった root を示す. その定義多項式は, その直前までの root を添加した体上で既約であることが保証されている.

結果の第 1 要素である 1 次因子のリストは, 第 2 要素の root を全て添加した体上での, sp() の引数の多項式の全ての因子を表す. その体は最小分解体となっているので, 因子は全て 1 次となるわけである. af() と同様, 全ての因子の積は, もとの多項式と定数倍の差はあり得る.

代数的数に関する函数のまとめ
==============

newalg
------

newalg(DEFPOLY)
     :: root を生成する.

return
     代数的数 (root)

defpoly
     多項式

  * DEFPOLY を定義多項式とする代数的数 (root) を生成する.

  * DEFPOLY に対する制限に関しては, see 代数的数の表現.

     [0] A0=newalg(x^2-2);
     (#0)

参照
     defpoly

defpoly
-------

defpoly(ALG)
     :: root の定義多項式を返す.

return
     多項式

alg
     代数的数 (root)

  * root ALG の定義多項式を返す.

  * root を #N とすれば, 定義多項式の主変数は t#N となる.

     [1] defpoly(A0);
     t#0^2-2

参照
     newalg, alg, algv

alg
---

alg(I)
     :: インデックスに対応する root を返す.

return
     代数的数 (root)

i
     整数

  * root #I を返す.

  * #I はユーザが直接入力できないため, alg(I) という形で入力する.

     [2] x+#0;
     syntax error
     0
     [3] alg(0);
     (#0)

参照
     newalg, algv

algv
----

algv(I)
     :: alg(I) に対応する不定元を返す.

return
     多項式

i
     整数

  * 多項式 t#I を返す.

  * t#I はユーザが直接入力できないため, algv(I) という形で入力する.

     [4] var(defpoly(A0));
     t#0
     [5] t#0;
     syntax error
     0
     [6] algv(0);
     t#0

参照
     newalg, defpoly, alg

simpalg
-------

simpalg(RAT)
     :: 有理式に含まれる代数的数を簡単化する.

return
     有理式

rat
     有理式

  * sp で定義されている.

  * 数, 多項式, 有理式に含まれる代数的数を, 含まれる root の定義多項式により簡単化する.

  * 数の場合, 分母があれば有理化され, 結果は root の多項式となる.

  * 多項式の場合, 各係数が簡単化される.

  * 有理式の場合, 分母分子が多項式として簡単化される.

     [7] simpalg((1+A0)/(1-A0));
     simpalg undefined
     return to toplevel
     [7] load("sp")$
     [46] simpalg((1+A0)/(1-A0));
     (-2*#0-3)
     [47] simpalg((2-A0)/(2+A0)*x^2-1/(3+A0));
     (-2*#0+3)*x^2+(1/7*#0-3/7)
     [48] simpalg((x+1/(A0-1))/(x-1/(A0+1)));
     (x+(#0+1))/(x+(-#0+1))

algptorat
---------

algptorat(POLY)
     :: 多項式に含まれる root を, 対応する不定元に置き換える.

return
     多項式

poly
     多項式

  * sp で定義されている.

  * 多項式に含まれる root #N を全て t#N に置き換える.

     [49] algptorat((-2*alg(0)+3)*x^2+(1/7*alg(0)-3/7));
     (-2*t#0+3)*x^2+1/7*t#0-3/7

参照
     defpoly, algv

rattoalgp
---------

rattoalgp(POLY,ALGLIST)
     :: 多項式に含まれる root に対応する不定元を root に置き換える.

return
     多項式

poly
     多項式

alglist
     リスト

  * sp で定義されている.

  * 第 2 引数は root のリストである. rattoalgp() は, この root に対応する不定元を, それぞれ root に置き換える.

     [51] rattoalgp((-2*algv(0)+3)*x^2+(1/7*algv(0)-3/7),[alg(0)]);
     (-2*#0+3)*x^2+(1/7*#0-3/7)

参照
     alg, algv

gcda
----

gcda(POLY1,POLY2,ALIST)
     :: 代数体上の 1 変数多項式の GCD

return
     多項式

poly1, poly2
     多項式

alist
     リスト

  * sp で定義されている.

  * 2 つの 1 変数多項式の GCD を求める.

  * ALIST は入力に現れる root および, それらの定義に含まれる root を再帰的に取り出して並べたリスト. A が B の定義に含まれている場合, A は B より後 (右) に並ばなければならない.

     [76] X=x^6+3*x^5+6*x^4+x^3-3*x^2+12*x+16$
     [77] Y=x^6+6*x^5+24*x^4+8*x^3-48*x^2+384*x+1024$
     [78] A=newalg(X);
     (#0)
     [79] gcda(X,subst(Y,x,x+A),[A]);
     x+(-#0)

参照
     gr hgr gr_mod, asq af

sp_norm
-------

sp_norm(ALG,VAR,POLY,ALGLIST)
     :: 代数体上でのノルムの計算

return
     多項式

var
     POLY の主変数

poly
     1 変数多項式

alg
     root

alglist
     root のリスト

  * sp で定義されている.

  * POLY の, ALG に関するノルムをとる. すなわち, K = Q(ALGLIST \ {ALG}) とするとき, POLY に現れる ALG を, ALG の K 上の共役に置き換えたもの全ての積を返す.

  * 結果は K 上の多項式となる.

  * 実際には入力により場合わけが行われ, 終結式の直接計算や中国剰余定理により計算されるが, 最適な選択が行われているとは限らない. 大域変数 USE_RES を 1 に設定することにより, 常に終結式により計算させることができる.

     [0] load("sp")$
     [39] A0=newalg(x^2+1)$
     [40] A1=newalg(x^2+A0)$
     [41] sp_norm(A1,x,x^3+A0*x+A1,[A1,A0]);
     x^6+(2*#0)*x^4+(#0^2)*x^2+(#0)
     [42] sp_norm(A0,x,@@,[A0]);
     x^12+2*x^8+5*x^4+1

参照
     res, asq af

asq, af
-------

asq(POLY)
     :: 代数体上の 1 変数多項式の無平方分解

af(POLY,ALGLIST)
     :: 代数体上の 1 変数多項式の因数分解

return
     リスト

poly
     多項式

alglist
     root のリスト

  * いずれも sp で定義されている.

  * root を含まない場合は整数上の函数が呼び出され高速であるが, root を含む場合には, gcda() が起動されるためしばしば時間がかかる.

  * af() は, 基礎体の指定, すなわち第 2 引数の, root のリストの指定が必要である.

  * alglist で指定される root は, 後で定義されたものほど前の方に来なければならない.

  * 結果は, 通常の無平方分解, 因数分解と同様 [因子, 重複度] のリストである.

  * 重複度を込めた因子の全ての積は, POLY と定数倍の違いがあり得る.

     [99] asq(-x^4+6*x^3+(2*alg(0)-9)*x^2+(-6*alg(0))*x-2);
     [[-x^2+3*x+(#0),2]]
     [100] af(-x^2+3*x+alg(0),[alg(0)]);
     [[x+(#0-1),1],[-x+(#0+2),1]]

参照
     gcda, fctr sqfr

sp
--

sp(POLY)
     :: 最小分解体を求める.

return
     リスト

poly
     多項式

  * sp で定義されている.

  * 有理数係数の 1 変数多項式 POLY の最小分解体, およびその体上での POLY の 1 次因子への分解を求める.

  * 結果は, POLY の因子のリストと, 最小分解体の, 逐次拡大による表現からなるリストである.

  * 最小分解体は, [root,algptorat(defpoly(root))] のリストとして表現されている. すなわち, 求める最小分解体は, 有理数体に, この root を全て添加した体として得られる. 添加は, 右の方の root から順に行われる.

  * sp() は, 内部でノルムの計算のために sp_norm() をしばしば起動する. ノルムの計算は, 状況に応じてさまざまな方法で行われるが, そこで用いられる方法が最善とは限らず, 単純な終結式の計算の方が高速である場合もある. 大域変数 USE_RES を 1 に設定することにより, 常に終結式により計算させることができる.

     [101] L=sp(x^9-54);
     [[x+(-#2),-54*x+(#1^6*#2^4),54*x+(#1^6*#2^4+54*#2),54*x+(-#1^8*#2^2),
     -54*x+(#1^5*#2^5),54*x+(#1^5*#2^5+#1^8*#2^2),-54*x+(-#1^7*#2^3-54*#1),
     54*x+(-#1^7*#2^3),x+(-#1)],[[(#2),t#2^6+t#1^3*t#2^3+t#1^6],[(#1),t#1^9-54]]]
     [102] for(I=0,M=1;I<9;I++)M*=L[0][I];
     [111] M=simpalg(M);
     -1338925209984*x^9+72301961339136
     [112] ptozp(M);
     -x^9+54

参照
     asq af, defpoly, algptorat, sp_norm.