数理論理3:構文論

今回は ・言語に対して,その言語の定理式の全体が定まること をLKと呼ばれる流儀で述べます.以下,言語,その言語の論理式の任意の集合Σを固定します. (定義3-1)論理式の任意の集合の対(Ψ,Ω)をシーケントと呼び,Σから導出可能なシーケントの全…

数理論理2:意味論

今回は ・言語,構造,割り当てに対して,その言語の項,論理式の値が定まること そして ・言語に対して,その言語の valid な論理式の全体が定まること を述べます.以下,言語を固定します. (定義2-1)構造は空でない集合D(domainと呼びます)と次…

nfsplitting(*,,2);

私が案出した Galois 群の計算方法を PARI の開発メンバーの方にお伝えしたところ,それに基づいた nfsplitting さらに galoisinit の改良版を作成してくださいました. 試用方法は https://pari.math.u-bordeaux.fr/cgi-bin/gitweb.cgi?p=pari.git;a=tree;h…

数理論理1:言語

ちょっとした経緯があり,数理論理(古典一階論理)の基本事項を少し書きます.今回は ・言語に対して,その言語の項,論理式の全体が定まること を述べます. (定義1-1)言語は,次のような互いに区別できる記号の集合です. 変数記号 x1 x2 … (可…

代数体上の線型方程式系の求解

今回の冪根拡大の構成では,中間体上の線型方程式系(連立一次方程式)を解くことが一つの柱となっています( http://ehito.hatenablog.com/entry/2019/04/11/193241 ).それは例えば,定義多項式が c5^4+c5^3+c5^2+c5+1, e1^2+10, e2^5+((-3750*c5^3)-3750…

位数の取得

前回も触れたように,nfsplitting の処理時間は結果の多項式の次数を第二引数として与えることで一般に短縮されます.この性質を利用するため本プログラムでは,その次数,つまり,入力多項式 の 上の Galois 群 の位数を,予め用意したある範囲内の全ての c…

多項式の Galois 群計算

本プログラムの Galois 群計算の仕組みは http://ehito.hatenablog.com/entry/2019/02/24/200919 で述べましたが,今回は具体例を用いて解説します.この方法は,単に入力多項式の Galois 群 を特定するのではなく,本プログラムの目標である入力多項式の根…

円分体上の Galois 群

前回までの冪根拡大では,円分体を基礎体とする一方,中間体の生成は 上の Galois 群の組成列に従っており, となる の発生原因となっていました.今回はこれを「まず円分体とその上の分解体の Galois 群を構成し,その組成列を用いて中間体を生成する手順」…

GGRR on SageMath

今回の「可解な方程式の全ての根を Galois 理論に基づく方法により冪根で表すプログラム」を SageMath ( http://www.sagemath.org/ ) に移植しました.SageMath は https://cocalc.com/?utm_source=sagemath.org&utm_medium=icon から,Facebook,Github,Go…

代数体上の多項式の高速乗算

一連の冪根拡大の構成では, を根全体とする多項式 の係数 から冪根を生成し,その過程で得られる情報を に還元して分解体の primitive element の最小多項式 を得ていますが, については 達の基本対称式を漸化式から得る方法,最小多項式についても幾度か…

改善策と問題点

前々回の記事( http://ehito.hatenablog.com/entry/2019/04/11/193241 )で述べた方法では, 以降をただ つの を見付けるために生成していますが,実は を得た段階で,それが に属する場合には,先述の通り拡大を行わず,属さない場合,つまり, が となる…

A comparison of splitting field calculators

方程式 f=0 の Gaolis 群の元の陽な表示(置換や同型写像)の取得には「分解体の定義多項式」と「 primitive element による f の根の多項式表示」の利用が古典的です.そこで今回は,幾つかの計算機代数システムについて,当該処理を担当する関数によるサン…

冪根拡大の新たな構成法

上の既約多項式 に対して,次が既知であるとします. (1) の 上の最小分解体 の定義多項式 (つまり, の primitive element の 上の最小多項式) (2) の各根 ( は に対応する変数) (3)各 についての (つまり, の根 )および の根の列に対する…

位数が大きな場合

これまでの RR シリーズでは,分解体の定義多項式,primitive element による入力多項式の根の表示, primitive element を根の 線型結合で表した際の係数を古典的な Trager の方法( http://www.cecm.sfu.ca/personal/monaganm/teaching/TopicsinCA17/Trage…

QE による検証

Mathematica の QE のデフォルトの議論領域は Reduce[Exists[x, a*x^2 == 1]] に対する出力 からも判るように複素数体であり,前回公開した Mathematica での実装の目的の 1 つは,この QE による結果の検証でした.Mathematica で前回の各関数の定義コード…

Mathematica 推参

オリジナルプログラムの元になったコードは Mathematica で書かれていますが,汎用性を重視した筆致なので,今回は https://reference.wolfram.com/language/tutorial/AlgebraicNumberFields.html.ja にある代数体関連の組み込み関数などを用いて書いてみま…

円分体の利用

RR シリーズでは冪根が代数的整数となるよう変数の導入時に係数を調整しています.これは algebraic モードへの適用を念頭に置いたものですが,1 の原始冪乗根の中間体上の定義式は必ずしも monic でないため,RR6m では,tellrat への入力の前に線形変換を…

inv 再考

置換の表現には,リストタイプと巡回タイプとがあり,それぞれ積,逆元の実装に適していますが,今回のコードは根の置換という出自からリストタイプを利用しており,逆元の実装に工夫の余地がありました.現在公開中の inv は inv(A):=map(second,sort(map("…

GCD の利用

現在のオリジナルプログラムや RR6 では,分解体の primitive element A の中間体 K(w,a) 上の定義式が Lagrange resolvents の和となることを利用していますが,http://ehito.hatenablog.com/entry/2019/03/02/163023 で述べたように,A の K(w,a) 上の定義…

微調整

http://ehito.hatenablog.com/entry/2019/02/24/234939 の実行例の timer_info() を見ると [[total,0.001663981382026495*sec,5586,9.295*sec,0], [mp,0.214*sec,15,3.21*sec,0], [nGG,0.1895333333333333*sec,15,2.843*sec,0], [RR6,0.167*sec,15,2.505*sec…

実行例

円分多項式の例です. (%i9) ROU(x,N):=rat(apply("*",makelist((x^(N/s)-1)^moebius(s),s,listify(divisors(N)))))$ Evaluation took 0.0000 seconds (0.0000 elapsed) using 0 bytes. (%i10) for i:3 thru 22 do print([p:ROU(x,i),mp(p),RR6(cs(nGG(DA)))…

4.添加する元の定義式,および,5.分解体の相対定義式(解説)

現在のオリジナルプログラムでは,すべての Lagrange Resolvent の冪乗,開冪,和を取って,表題の2つを算出しています.一方,http://ehito.hatenablog.com/entry/20190123/1548255005 で提案した方法は,分解体の(基礎体 K 上の)定義式 P,新たに添加す…

4.添加する元の定義式,および,5.分解体の相対定義式

取り敢えず,コードと例を記します.解説はまた後日. load("grobner")$ factor2list(f0):=block([f:num(f0)],if op(f)="-" then args(-f) elseif op(f)="*" then args(f) else [f])$ rrem(S,T):=block([U:S],map(lambda([s],U:remainder(U,s[1],s[2])),T),U…

3.組成列

組成列の計算については,http://ehito.hatenablog.com/entry/2019/02/13/200937 で述べましたが,mnsg に積閉の必要条件などを加え,やや速くなっています.cs の引数は nGG の出力,出力は先述の通りです. mul(A,B):=map(lambda([s],A[s]),B)$ inv(A):=ma…

2.Galois 群

現在のオリジナルプログラムでは,Galois 群の元と分解体の絶対定義式の根との対応の把握に若干の検索を行っています.これに対して,下記の nGG では,1.で得た RA における A が絶対定義式 DA の任意の根であるという点に着目して,それらの根と「入力 p…

1.分解体の絶対定義多項式

今回のオリジナルプログラム https://github.com/YasuakiHonda/GaloisGroupSolver が行う主な処理は 1.分解体の絶対定義式 2.Galois 群 3.組成列 4.添加する元の定義式 5.分解体の相対定義式 の算出です.種々の方法の比較の意味も含め,私家版を…

正規部分群の構成

今回のオリジナルプログラムでは各元の一点集合の conjugate closure から極大正規部分群を選んでいますが,それが必ずしも正しい結果を与えないことも,例えば G:[[1,2,3,4,5,6],[1,2,3,4,6,5],[1,2,4,3,5,6],[1,2,4,3,6,5], [2,1,3,4,5,6],[2,1,3,4,6,5],[…

冪乗に分解できるタイプ

今回のオリジナルプログラムでは,例えば,SolveSolvable(x^2-2)$ の根の表示には [[alpha[1],alpha[1]^2-8]] が現れるので,SolveSolvable(x^2-8)$ と問うと,[[alpha[1],alpha[1]^2-32]] が現れるので,...となってしまいます.プログラムの趣意に反す…

Groebner基底の利用(その1)

jurupapaさん( http://maxima.hatenablog.jp/ )が公開しておられる「可解な方程式を冪根で解く」プログラムの処理の一部に Groebner 基底を用いてみました.例は以下のものです. http://maxima.hatenablog.jp/entry/2018/10/09/005917 http://maxima.hate…

CAD-QE on PARI+Singular(実行例)

同じ例を開発中の PARI+Singular 上での CAD-QE で処理すると... ? tst11Sv2s01([ex,ex],[a,b,x,y],and,[sgn np (x^2+y^2-1),sgn 0 (a*x+b*y-1)],2*7);Ans(); *** connecting adjacent 16/796 cells. 1[a <= [a+1,1],true,true,true] 2[[a+1,1] < a < [a,…