nopu@wiki
nopu@wiki

Gröbner基底

背景 

式を解いてから別の式に代入する
→　数値誤差とか場合分け的なものが発生する。だるい。
x^3- 2=0 \quad \Rightarrow \quad x=2^{\frac{1}{3}} \mbox{ in } \mathbb{R}
x^2+y^2-1=0 \quad \Rightarrow \quad y = \pm \sqrt{1-x^2}

→ 式のまま使えたらうれしい。
\begin{cases} x^3- 2=0 \\ 2 x^6-y+1=0 \end{cases}
\Rightarrow y=2 (x^3)^2+1 = 2 \times 2^2+1 = 9
\begin{cases} x^2+y^2-1=0 \\ x^2+2x+y^2=0\end{cases}
\Rightarrow 2x + (x^2+y^2) = 2x + 0= 0 \quad \therefore x=y=0

ストーリー 

連立方程式を「解きやすい」ものに変形する操作　＝　イデアル
　→ 根基イデアル
連立方程式の解　＝　零点集合
　→ 代数的集合
→ 零点集合（代数的集合）とイデアル（根基イデアル）の相互関係
　ザリスキ閉包，ヒルベルトの零点定理

ある多項式が単項式イデアルに入ったら，その多項式の項は全て含まれる。

「ある多項式があるイデアルに入るかどうか？」の判定法
「Gröbner基底で割った余りが０になるかどうか？」で分かる。

1. Gröbner基底の定義，Gröbner基底かどうかの判定法（Buchbergerほか），Gröbner基底の作り方，最小かつユニークなGröbner基底（被約性）
2. 割り算のアルゴリズム，そのための単項式順序（多項式の先頭を定める方法），余りの一意性
3？. 消去定理

代数的集合 

K : field
\mathbb{Q},\mathbb{R},\mathbb{C},\mathbb{F}_p=\frac{\mathbb{Z}}{p\mathbb{Z}}

An : Affine Space
Knに構造を入れたもの（ザリスキとか）
\mathbb{A}^n := \{ P= \underbrace{(a_1,a_2, \cdots,a_n)}_{\mbox{Affine coordinate}} | a_i \in K\} \simeq \mathbb{K}^n

A := K[X] := K[X1,...,Xn] : polynomial ring

Prop. 体上の多項式環は整域

Def. 零点
P \in \mathbb{A}^n, \, f \in \mathbb{K}[X]
Pがfの零点であるとは，以下が成り立つことをいう。
f(P) := f(a_1,\cdots,a_n) = 0

Def. 零点集合
T \subset \mathbb{K}[X]
Tの零点集合Z(T)とは，Tの各元に共通する零点の集合である。
Z(T) := \{ P\in\mathbb{A}^n | f(P)=0 \mbox{ for } {}^\forall f \in T\}

Def. 代数的集合
Z \subset \mathbb{A}^n
Zが代数的集合であるとは，Zがある多項式集合Tの零点集合になることをいう。
{}^\exists T \subset \mathbb{K}[X] \mbox{ s.t. } Z=Z(T)

Zariski Topology 

Lem. 零点集合の性質  
S,T ⊂ K[X] とする。
1. S \subset T \Rightarrow Z(S) \supset Z(T)
2. Z(\langle S \rangle)=Z(S)

Th. 代数的集合は閉集合の公理を満たす。
1. \bigcap_{\lambda \in \Lambda} Z(T_\lambda) = Z(\bigcap_{\lambda \in \Lambda} T_\lambda) \quad T_\lambda \in \mathbb{K}[X]
2. Z(A) \cup Z(T) = Z(\langle S \rangle \cap \langle T \rangle ) = Z(ST) \quad S,T \in \mathbb{K}[X]
3.  Z(\{ 0 \})=\mathbb{A}^n, \quad Z(\{ 1 \}) = \phi

Def. Zariski位相
Affine Sp. An は代数的集合を閉集合とする位相空間である。
この位相をZariski位相という。

Ex. A1の閉集合
φか，A1から有限集合（φを含む）を引っこ抜いたもの。

Zのイデアル 

Def. Zのイデアル
Z⊂An のイデアル I(Z) は次で定義される。
I(Z) := \{ f \in \mathbb{K}[X] | f(P) = {}^\forall P \in Z\}

Lem. Zのイデアルの性質
Z,W ⊂ An とする。
1. Z \subset W \Rightarrow I(Z) \supset I(W)
2. I(Z) は K[X] のイデアル

Prop. 
1. Z,W ⊂ An
  I(Z \cap W) \supset I(Z) + I(W)
  I(Z \cup W) = I(Z) \cap I(W)
2. I(φ)=K[X]
3. I(An)={0} (但しKの標数∞に限る)
4. P := (a_1, \cdots, a_n) \in \mathbb{A}^n \Rightarrow I(P) = \langle x_1-a_1, \cdots, x_n-a_n\rangle

Zariski閉包 

Prop. 
1. T⊂K[X]
  I(Z(T)) \supset T
  Z(I(Z(T))) = Z(T)
2. Z⊂An
  Z(I(Z)) \supset Z
  I(Z(I(Z))) = I(Z)

Prop. Zariski closure
Z⊂An
 \overline{Z} = Z(I(Z))

Hilbertの零点定理 

Def. 根基 radical
R：可換環； I⊂R：イデアル
Iの根基√Iを以下で定義する。
 \sqrt{I} := \{ a \in R | {}^\exists m>0 \, : \, a^m \in I\} 
特に，I=√I となるとき，Iを根基イデアルという。

Lem. 根基の性質
1. √I は R のイデアル
2. I⊂J ⇒ √I⊂√J
3. √I=√√I

Prop. Zのイデアルは根基イデアル
Z⊂An ⇒ I(Z)は根基イデアル
Z \subset \mathbb{A}^n \Rightarrow I(Z)=\sqrt{I(Z)}

Th. Hilbertの零点定理
K=K-：代数的閉包（K係数多項式の根を全て含めた体のうち，最小のもの）
I⊂K[X]：イデアル
このとき，以下が成り立つ。
I(Z(I)) = \sqrt{I}

Cor. 代数的集合と根基イデアルの関係
K：代数的閉包のとき，次の全単射が存在する。
(代数的集合 Z⊂An) ⇔ (根基イデアル I⊂K[X])

単項式順序 

Def. 単項式順序
Z≧0nの順序関係>が単項式順序であるとは，
1. 全順序性 \alpha,\beta \in \mathbb{Z}_{\geq 0 }^n \Rightarrow \alpha > \beta \mbox{ or } \alpha = \beta \mbox{ or } \beta > \alpha
2. 加法性 \alpha,\beta,\gamma \in \mathbb{Z}_{\geq 0 }^n \quad \alpha > \beta \Rightarrow \alpha + \gamma > \beta + \gamma
3. 整列性  \emptyset \neq S \subset \mathbb{Z}_{\geq 0 }^n \Rightarrow S \mbox{ has a minimum element.} 
3' 降鎖条件（狭義減少列の長さは有限）
   \emptyset \neq S \subset \mathbb{Z}_{\geq 0 }^n \quad \alpha^{(1)} > \alpha^{(2)} > \cdots \Rightarrow {}^\exists k \mbox{ s.t. } \alpha^{(k)} = \alpha^{(k+1)} = \cdots

Ex. 辞書式順序 lexicographic order
\alpha <_l \beta \Leftrightarrow {}^\exists i \mbox{ s.t. } \alpha_1 = \beta_1, \cdots, \alpha_{i-1}=\beta_{i-1}, \alpha_i < \beta_i 

Def. 多項式の先頭項
多項式の並べ方（つまり何が先頭か）は，単項式順序のとり方に依る。
多重指数表記 \mathbb{K}[X] \ni f := \sum_{finite \, \alpha} C_\alpha x^\alpha (C_\alpha \in \mathbb{K})
多重次数  \mathrm{deg} f := \max_{C_\alpha \neq 0} \alpha
先頭項  LT(f) := C_{\mathrm{deg} f}x^{\mathrm{deg} f} 
先頭単項式  LM(f) := x^{\mathrm{deg} f} 
先頭係数  LC(f) := C_{\mathrm{deg} f} 

Ex. 次数付き辞書式順序 graded lexcographic order
|α|=Σαi を全次数という。
 \alpha >_{gl} \beta \Leftrightarrow \begin{cases} |\alpha|>|\beta| \\ |\alpha|=|\beta| \mbox{ and } \alpha >_{lex} \beta \end{cases}

Ex. 逆辞書式順序 reverse lexcographic order
これは単項式順序でない！
 \alpha >_{rl} \beta \Leftrightarrow {}^\exists i \mbox{ s.t. }\alpha_i < \beta_i, \alpha_{i+1} = \beta_{i+1}, \cdots, \alpha_n=\beta_n

Ex. 次数付き逆辞書式順序 graded reverse lexcographic order
 \alpha >_{grl} \beta \Leftrightarrow \begin{cases} |\alpha|>|\beta| \\ |\alpha|=|\beta| \mbox{ and } \alpha >_{rl} \beta \end{cases}

多項式の割り算

タグ：

+ タグ編集
  • タグ：

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー と 利用規約 が適用されます。

タグの更新に失敗しました
エラーが発生しました。ページを更新してください。
ページを更新
「Gröbner基底」をウィキ内検索
最終更新：2009年07月29日 18:58
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。