スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

グレブナー基底

Gröbner 基底の定義と Buchberger の判定法。

※ MathJax を使用しています。数式を表示するためには、JavaScript をオンにする必要があります。

単項式順序

$n$ を正の整数, $K$ を体とし, $K[X] = K[X_{1}, X_{2}, \ldots, X_{n}]$ を $K$ 上の $n$ 変数多項式環とする. また, $$ \mathbb{Z}_{\geq 0}^{n} = \{ (\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n})\in\mathbb{Z}^{n} \mid \alpha_{k}\geq 0\;(k=1, 2, \ldots, n) \} $$ とおき, 各 $\alpha = (\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n})\in\mathbb{Z}_{\geq 0}^{n}$ に対して $X^{\alpha} = X_{1}^{\alpha_{1}}X_{2}^{\alpha_{2}}\cdots X_{n}^{\alpha_{n}}$ とおく.

$K[X]$ の項順序あるいは単項式順序とは, $K[X]$ の単項式からなる部分集合 $M=\{ X^{\alpha} \mid \alpha\in \mathbb{Z}_{\geq 0}^{n} \}$ における順序 $\leq$ で次の二つの条件を満たすものをいう.

(i) $M$ は $\leq$ に関して整列集合である. すなわち, $M$ は $\leq$ に関して全順序集合であって, $M$ の任意の空でない部分集合は $\leq$ に関して最小元をもつ.

(ii) 任意の $\alpha$, $\beta$, $\gamma\in\mathbb{Z}_{\geq 0}^{n}$ に対して, $X^{\alpha}<X^{\beta}$ ならば $X^{\alpha+\gamma}<X^{\beta+\gamma}$.

例えば, $M$ における順序を $$ X^{\alpha} < X^{\beta} \Longleftrightarrow \mbox{$\beta-\alpha$ の $0$ でない最初の成分が正} $$ によって定めると, $K[X]$ の項順序になる. これを辞書式順序という. $K[X]$ の項順序の定め方は他にもある.

多変数多項式の割り算

$K[X]$ を 体 $K$ 上の $n$ 変数多項式環とし, 項順序を固定する. $\displaystyle f(X) = \sum_{\alpha\in\mathbb{Z}_{\geq 0}^{n}}a_{\alpha}X^{\alpha}\in K[X]$ に対して, \begin{align*} & \mathrm{mltdeg}(f) = \max\{ \alpha\in\mathbb{Z}_{\geq 0}^{n} \mid a_{\alpha}\neq 0 \}, \\ & \mathrm{LM}(f) = X^{\mathrm{mltdeg}(f)}, \\ & \mathrm{LC}(f) = a_{\mathrm{mltdeg}(f)}, \\ & \mathrm{LT}(f) = \mathrm{LC}(f)\mathrm{LM}(f) \end{align*} とおく. 上から順に, $f$ の多重次数, 最高次単項式, 最高次係数, 最高次項という.

$f\in K[X]$ を $f_{1}$, $f_{2}$, $\ldots$, $f_{m}\in K[X]$ で割るとは, $g_{1}$, $g_{2}$, $\ldots$, $g_{m}$, $r\in K[X]$ で次の条件を満たすものを見つけることである.

(i) $\displaystyle f = \sum_{i=1}^{m}g_{i}f_{i} + r$.

(ii) $r$ に現れるどの単項式も, $\mathrm{LM}(f_{1})$, $\mathrm{LM}(f_{2})$, $\ldots$, $\mathrm{LM}(f_{m})$ のどれでも割り切れない.

このとき, $r$ を余りという.

条件 (i), (ii) を満たす $g_{1}$, $g_{2}$, $\ldots$, $g_{m}$, $r$ が一意的に定まるとは限らない. しかし, それらを求める手続きがあることは知られている.

$G$ を $K[X]$ の有限部分集合とする. $f$ を $G$ で割るとは, $G = \{f_{1}$, $f_{2}$, $\ldots$, $f_{m}\}$ のとき, $f$ を $f_{1}$, $f_{2}$, $\ldots$, $f_{m}$ で割ることと定義する.

Gröbner 基底

$K[X]$ を 体 $K$ 上の $n$ 変数多項式環とし, 項順序を固定する. $K[X]$ の部分集合 $S$ に対して, \begin{align*} \mathrm{LM}(S) &= \{ \mathrm{LM}(f) \mid f\in S \}, \\ \mathrm{LT}(S) &= \{ \mathrm{LT}(f) \mid f\in S \} \end{align*} とおく. $\mathrm{LM}(S)$ によって生成される $K[X]$ のイデアル $\langle\mathrm{LM}(S)\rangle$ と, $\mathrm{LT}(S)$ によって生成される $K[X]$ のイデアル $\langle\mathrm{LT}(S)\rangle$ とは一致する.

$J\neq\{0\}$ を $K[X]$ のイデアルとする. $J$ の有限部分集合 $G=\{f_{1}$, $f_{2}$, $\ldots$, $f_{s}\}$ が $J$ の Gröbner 基底であるとは, $$ \langle\mathrm{LM}(J)\rangle = \langle\mathrm{LM}(G)\rangle = \langle\mathrm{LM}(f_{1}),\,\mathrm{LM}(f_{2}),\,\ldots,\,\mathrm{LM}(f_{s})\rangle $$ が成り立つときにいう.

任意の項順序とイデアル $J\neq\{0\}$ に対して, $J$ の Gröbner 基底が存在する. また, $J$ の Gröbner 基底は $J$ を生成する: $J = \langle G\rangle = \langle f_{1}$, $f_{2}$, $\ldots$, $f_{s}\rangle$.

Buchberger の判定法

$K[X]$ を 体 $K$ 上の $n$ 変数多項式環とし, 項順序を固定する.

$\mathbb{Z}_{\geq 0}^{n}$ の元 $\alpha = (\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n})$, $\beta = (\beta_{1}, \beta_{2}, \ldots, \beta_{n})$ に対して, $\gamma_{i}=\max\{\alpha_{i}, \beta_{i}\}$ とし, $\gamma = (\gamma_{1}, \gamma_{2}, \ldots, \gamma_{n})$ とおく. このとき, $X^{\gamma}$ を $X^{\alpha}$ と $X^{\beta}$ の最小公倍単項式といい, $\mathrm{LCM}(X^{\alpha}, X^{\beta})$ で表す.

$K[X]$ の $0$ でない元 $f$, $g$ に対して, $$ S(f, g) = \frac{\mathrm{LCM}(LM(f), LM(g))}{LT(f)}f-\frac{\mathrm{LCM}(LM(f), LM(g))}{LT(g)}g $$ を $f$ と $g$ の $S$-多項式という.

Buchberger の判定法は, イデアルの生成元が Gröbner 基底であるかどうかの判定条件を与える.

[Buchberger の判定法] $K[X]$ のイデアル $J\neq\{0\}$ の有限個の生成元からなる集合 $G=\{f_{1}$, $f_{2}$, $\ldots$, $f_{m}\}$ が $J$ の Gröbner 基底であるための必要十分条件は, すべての $i$, $j$ $(1\leq i<j\leq m)$ に対して, $S$-多項式 $S(f_{i}, f_{j})$ を $G$ で割ったときの余りが $0$ になることである.

Buchberger のアルゴリズムは, イデアルが有限個の生成元とともに与えられたとき, それから Gröbner 基底を有限回の操作で構成する手続きである.

[Buchberger のアルゴリズム] $K[X]$ のイデアル $J\neq\{0\}$ の有限個の生成元からなる集合 $G$ が与えられているとする. $G$ に対する次の操作を考える:

$G$ の二つの元 $f_{i}$, $f_{j}$ の $S$-多項式 $S(f_{i}, f_{j})$ を $G$ で割った余り $r_{ij}$ が $0$ でなければ, $G\cup\{r_{ij}\}$ を新しい $G$ とする.

この操作は有限回で終わり, 最後に得た $G$ が $J$ の Gröbner 基底になる.

参考文献

  • 丸山正樹: グレブナー基底とその応用, 共立出版, 2002.

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。