平成12年度修士論文

非可換多項式環 k (α) ⟨x, y⟩ / (yx − αxy)の左単項生成イデアルの共通部分の生成元について

指導教官: 木村俊一教官

広島大学大学院理学研究科博士課程前期数学専攻

学生番号: M1171023 森島聖

平成 13 年 2 月 9 日

概要

本論文は, yx = αxy を満たす非可換多項式環 k (α) ⟨x, y⟩ / (yx − αxy) の左単項生成イデアルの共通部分の生成元に関して考察したものである. 可換多項式環では, 単項生成イデアルの共通部分は最小公倍多項式によって単項生成されるわけだが, 左 Gröbner 基底アルゴリズムを用いた計算機実験の結果から非可換多項式環 k (α) ⟨x, y⟩ / (yx − αxy) の左単項生成イデアルの共通部分は必ずしも単項生成にならないことがわかった. そこで, 単項生成になるいくつかの条件の場合について証明つきで構成し, 単項生成でない場合については具体的構成は出来なかったが, 計算機実験から高々2 元で生成されるのではないかという予想をたてた. この予想や, また, 単項生成になるための必要十分条件に関しては, 今後研究を行っていく上で大変興味深いものとなっている.

目次

第 1 章多項式環と Gröbner 基底 5 1.1 多項式環と Gröbner 基底 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

第 2 章左 Gröbner 基底のアルゴリズムと応用 8 2.1 左除法定理と左 Gröbner 基底 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 左消去イデアルと左単項生成イデアルの共通部分 . . . . . . . . . . . . . . . . . . . . 17

第 3 章左単項生成イデアルの共通部分の生成元 19 3.1 生成元についての考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 問題と予想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

付録 A 左除法定理プログラム 40

付録 B 左簡約 Gröbner 基底プログラム 43

付録 C 左イデアル所属判定プログラム 45

序

k を標数 0 の体とする. 可換多項式環 k [x_{1}, ⋯, x_{n}] での Gröbner 基底の応用についてはよく知られており, 消去イデアル, 多項式で表された連立方程式の解, 有理関数で表されたパラメータ表示に対応する陰表示, イデアル商, イデアルの飽和, イデアルの共通部分, イデアルの根基, イデアルの準素分解, シジジー等を計算可能にする ([1][2]).

この論文では Gröbner 基底の概念を非可換多項式環に応用し, 左単項生成イデアルの共通部分の生成元について考察する.

まず 1 章で k [x_{1}, ⋯, x_{n}] での Gröbner 基底とその応用, 特に, 消去イデアルの定義 (Definition 1.4) や, 消去イデアルを求めるアルゴリズム (Theorem 1.5), また, それを用いてイデアルの共通部分の生成元を計算するアルゴリズム (Theorem 1.6) を紹介する.

2 章では x_{j}x_{i} = αx_{i}x_{j} (j > i) を満たす, x_{i} で生成される非可換多項式環

R′ = k (α) ⟨x_{1}, ⋯, x_{n}⟩ /(x_{j}x_{i} − αx_{i}x_{j} | j > i)

に Gröbner 基底の概念を適用した左 Gröbner 基底とその応用について議論する. 左 Gröbner 基底 (Definition 2.5) は左除法定理 (Theorem 2.3) と左 S 多項式 (Definition 2.6) を用いて構成することが出来る. このアルゴリズムを用いることにより左消去イデアル (Definition 2.17) と左単項生成イデアルの共通部分の生成元を計算することが出来る (Theorem 2.18,Theorem 2.19).

3 章では, 特に yx = αxy を満たす 2 変数非可換多項式環

R = k (α) ⟨x, y⟩ /(yx − αxy)

に限定し, 左 Gröbner 基底アルゴリズムを用いた左単項生成イデアルの共通部分の生成元の計算及び考察を行う. 可換多項式環では, 単項生成イデアルの共通部分は最小公倍多項式によって単項生成される. しかし, R では左単項生成イデアルの共通部分は必ずしも単項生成にはならない. 例えば,

(*) R · (x + 1) ∩ R · (y + 1) = R · (x^{2}y + x^{2} + \frac{(α + 1)}{α}xy + \frac{(α + 1)}{α}x + \frac{y}{α} + \frac{1}{α})

+R · (xy^{2} + \frac{(α + 1)}{α}xy + \frac{y^{2}}{α^{2}} + \frac{x}{α} + \frac{(α + 1)}{α^{2}}y + \frac{1}{α})

が挙げられる (Example 3.3). この２元は左簡約 Gröbner 基底 (Definition 2.12) になっており, その一意性 (Proposition 2.13) から単項生成にはならないことが示される (Lemma 3.4). このように必ずしも左単項生成イデアルの共通部分は単項生成にはならないのだが, 計算機実験の結果 (Example 3.22) から, 左 Gröbner 基底の定義に用いる単項式順序 (Definition 1.1) として辞書式順序 (Example 1.2.1) x > y を取るとき高々2 元からなる左簡約 Gröbner 基底で生成されるのではないかと予想される (Conjecture 3.25). 一方, 単項生成になる場合については, いくつかの構成方法 (Proposition 3.16, Proposition 3.21) を与える. ここで, この構成方法に関連して, 高橋宣能氏による予想 (Conjecture 3.24) が提起されている. 最後に残るのは単項生成になる必要十分条件は何かという問題 (Problem 3.23) である. これらの予想や問題は, 今後研究を行っていく上で大変興味深いものとなっている.

本文における記号の説明： R′ は x_{j}x_{i} = αx_{i}x_{j} (i < j) を満たす多変数非可換多項式環, R は yx = αxy を満たす 2 変数非可換多項式環を表し, R′ の多項式はすべて x_{j}x_{i} = αx_{i}x_{j} (i < j) を用いて各項を x_{1}, ⋯, x_{n} の順の積で表すことにする. R の多項式についても同様である. これにより, 非可換多項式環上で可換の積を考えることが出来るので, これを『∗』によって表す. また, 特に断わらない限り単項生成元は零多項式でないと仮定する.

謝辞：本論文作成と研究にあたり, 木村俊一先生には多大な御指導と助言をいただきました. 木村俊一先生の海外出張時には, 高橋宣能先生にも御指導と助言をいただきました. 2 年間で様々な面においてお世話になった他の諸先生方や友人達, また, 6 年間, 勉学に励む上での素晴しい環境を私に与えて下さった広島大学も含めて, この場を借りて感謝の意を表します.

第1章多項式環とGröbner基底

1.1 多項式環と Gröbner 基底

Gröbner 基底という概念は廣中平祐と B. Buchberger によって発見されたものであるが, この概念は, 計算代数, 特に多項式環における様々な代数的対象の具体量の計算への応用を多く持つ. この節では,(可換) 多項式環 k [x_{1}, ⋯, x_{n}] における Gröbner 基底とその応用について簡単に説明する. なお, この節での定義の細密な部分や証明については [1],[2] を参照するとよいが, 同様の議論を 2 章で非可換多項式環について詳しく述べる.

まず単項式に順序づけを行う. Definition 1.1 M を単項式全体の集合とする. M 上の関係 > が

1. > は, 全順序である.

2. > は, 整列順序である.

3. ∀a, b, c ∈ M に対し, a > b ⟹ ac > bc を満たすとき, > を M 上の単項式順序という.

単項式順序は, x^{α} > x^{β} のとき, α > β と表すこともある. ただし, α = (α_{1}, ⋯, α_{n}) で, x^{α} = x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} とする. β についても同様である.

以下に単項式順序の例をいくつか挙げる. Example 1.2

1. 辞書式順序 ( lex order ) α >_{lex} β ⟺ α − β の 0 でない一番左にくる要素が正の数.

2. 総次数辞書式順序 ( grlex order ) α >_{grlex} β ⟺

∑_{i=1}^{n} α_{i} > ∑_{i=1}^{n} β_{i} または, ∑_{i=1}^{n} α_{i} = ∑_{i=1}^{n} β_{i} かつ α >_{lex} β

3. 総次数逆辞書式順序 ( grevlex order ) α >_{grevlex} β ⟺

∑_{i=1}^{n} α_{i} > ∑_{i=1}^{n} β_{i} または, ∑_{i=1}^{n} α_{i} = ∑_{i=1}^{n} β_{i} かつ α − β の 0 でない一番右にくる要素が負の数.

4. l 番目消去順序 ( l-th elimination order ) α >_{l} β ⟺

∑_{i=1}^{l} α_{i} > ∑_{i=1}^{l} β_{i} または, ∑_{i=1}^{l} α_{i} = ∑_{i=1}^{l} β_{i} かつ α >_{grevlex} β

この単項式順序に関しては, [3] を参考にするとよい.

上の例では x_{1} > ⋯ > x_{n} となっているが, 変数に任意の順序を定めても同様に単項式順序を定めることが出来る. また, 1 や 4 のような

∃l s.t. ∀p = x_{1}^{α_{1}} ⋯ x_{l}^{α_{l}}(≠ 1), ∀q = x_{l+1}^{α_{l+1}} ⋯ x_{n}^{α_{n}} に対し, p > q

を満たすような単項式順序を l 番目消去型順序という.

すべての単項式順序は加重行列によって行列表示出来ることが知られている. 上から順に行ベクトルと比較したいそれぞれの単項式の指数の内積の大小を調べるやり方である. 例えば, 総次数辞書順序なら,

\underbrace{( \begin{matrix}1 & 1 & 1 & … & 1 & 1 \\ 1 & 0 & 0 & … & 0 & 0 \\ 0 & 1 & 0 & … & 0 & 0 \\ ⋮ & ⋮ & ... & & & ⋮ \\ ⋮ & ⋮ & & ... & & ⋮ \\ ⋮ & ⋮ & & & ... & ⋮ \\ 0 & 0 & 0 & … & 0 & 1 \end{matrix} )}_{n}

l 番目消去イデアルなら,

^{l}

\underbrace{( \begin{matrix}1 & … & 1 & 0 & … & 0 \\ 1 & 1 & … & 1 & 1 & 1 \\ 1 & 1 & … & 1 & 1 & 0 \\ 1 & 1 & … & 1 & 0 & 1 \\ ⋮ & & & ... & ⋮ & ⋮ \\ ⋮ & & ... & & ⋮ & ⋮ \\ ⋮ & ... & & & ⋮ & ⋮ \\ 0 & 1 & … & 1 & 1 & 1 \end{matrix} )}_{n}

のように行列表示する. 詳細は [4] を参照のこと.

単項式順序を固定したとき, 多項式 f の項の中で最も大きいものを f の先導項といい LT(f) と表す. また, その単項式を LM(f), 係数を LC(f), LT(f) の指数部分を multideg(f) と表す. さらに G ⊂ k [x_{1}, ⋯, x_{n}] に対し, LT(G) を, G の元の先導項の集合とする.

以後, 特に断わらない限り x_{1} > ⋯ > x_{n} であるような, ある単項式順序を固定し議論を進めていく.

Definition 1.3 I ⊂ k [x_{1}, ⋯, x_{n}] をイデアル, G ⊂ I を I の有限生成系とし , 単項式順序 > を固定する.

(LT(I)) = (LT(G))

が満たされるとき, G を I の > に関する Gröbner 基底という. ただし, 有限集合 A に対し, (A) は, A のすべての元で生成されるイデアルを表す.

実際, I = (f_{1}, ⋯, f_{s}) のように具体的に生成元が与えられた場合,Gröbner 基底を計算するアルゴリズム (Buchberger のアルゴリズム) が知られている. 特に簡約 Gröbner 基底と呼ばれるものは一意に定まるので, 以後, Gröbner 基底は簡約化されたものを扱うことにする.

多項式を複数の多項式で割りたいとき, 多変数型の除法定理アルゴリズムを適用することによりそれぞれの商多項式と剰余多項式を計算することが出来るが, 一般に, 単項式順序や多項式で割る順番を変えて計算するとこれらは一意ではない. しかし,Gröbner 基底で割ると, 単項式順序や割る順番にかかわらず剰余多項式は一意に定まる. このことから, 具体的に多項式とイデアルの生成元が与えられたときに, イデアルの Gröbner 基底を用いることにより, 多項式がイデアルに所属しているかどうかの判定が可能になる.

この他にも Gröbner 基底の応用例は多いが, ここでは消去イデアルを計算するアルゴリズムとイデアルの共通部分を計算するアルゴリズムについて述べておく.

Definition 1.4 I ⊂ k [x_{1}, ⋯, x_{n}] をイデアルとするとき,

I_{l} := I ∩ k [x_{l+1}, ⋯, x_{n}]

を l 番目消去イデアルという.

より一般にR′ = k [x_{i_{1}}, ⋯, x_{i_{s}}] ({x_{i_{1}}, ⋯, x_{i_{s}}} ⊂ {x_{1}, ⋯, x_{n}}) に対して, I′ = I ⋂ R′ を {x_{i_{1}}, ⋯, x_{i_{s}}} に関する消去イデアルということもあるが, 変数を並べかえることにより以下と同じ議論が出来る. 次の定理が, l 番目消去イデアルの生成元 (Gröbner 基底) の計算アルゴリズムを与える.

Theorem 1.5 G をイデアル I ⊂ k [x_{1}, ⋯, x_{n}] の l 番目消去型順序に関する (簡約)Gröbner 基底とする. このとき 0 ≤ l ≤ n に対し,

G_{l} := G ∩ k [x_{l+1}, ⋯, x_{n}]

は l 番目消去イデアル I_{l} の (簡約)Gröbner 基底である.

上で述べた通り l 番目消去型順序には, 辞書式順序や l 番目消去順序があるのだが, 実際に計算する場合には, 辞書式順序よりも l 番目消去順序のほうが計算スピードが速い傾向があることが計算機実験からわかった. ちなみに, l 番目消去順序で計算した l 番目消去イデアルの生成元は, 総次数逆辞書式順序に関する Gröbner 基底となる. なお, 辞書式順序や l 番目消去順序が l 番目消去型順序といわれる所以は, この定理から明らかであろう.

次の定理はイデアルの共通部分の生成元を計算するアルゴリズムを与える.

Theorem 1.6 I, J ⊂ k [x_{1}, ⋯, x_{n}] をイデアルとする. このとき,

I ∩ J = (tI + (1 − t) J) ∩ k [x_{1}, ⋯, x_{n}] .

この定理からイデアル tI + (1 − t) J ⊂ k [t, x_{1}, ⋯, x_{n}] の {t} に関する 1 番目消去イデアルを計算すれば, I ∩ J の生成元 (Gröbner 基底) が求まる.

第2章左Gröbner基底のアルゴリズムと応用

1 章では Gröbner 基底とその応用について簡単にふれたが, この章では, x_{j}x_{i} = αx_{i}x_{j} を満たす x_{i} で生成される非可換多項式環

R′ = k (α) ⟨x_{1}, ⋯, x_{n}⟩ /(x_{j}x_{i} − αx_{i}x_{j} | j > i)

に Gröbner 基底の概念を導入した左 Gröbner 基底アルゴリズムとその応用について議論していく. なお, R′ の多項式はすべて x_{j}x_{i} = αx_{i}x_{j} (i < j) を用いて各項を x_{1}, ⋯, x_{n} の順の積で表すことにする. このように表したとき, 非可換多項式環上で可換の積を表したい場合には『∗』の記号を用いることにする. また, このとき, 単項式順序が可換の場合と同様に定義できるので, 以後, 特に断らない限り単項式順序を固定して議論を進める.

2.1 左除法定理と左 Gröbner 基底

まず初めに, 非可換の場合の除法定理アルゴリズムを紹介する.

Lemma 2.1 s = cx^{a}, t = dx^{b} ∈ R′ c, d ∈ k (α) a = (a_{1}, ⋯, a_{n}) b = (b_{1}, ⋯, b_{n}) とする. このとき,

st = α^{e}(s ∗ t) ただし, e = ∑_{i=1}^{n−1} (b_{i} ∑_{j=i+1}^{n} a_{j}).

証明は容易なので省略する.

Definition 2.2 前補題での α^{e} は, s と t によって決まるので, これを sig(s, t) とおく. すなわち, st = sig(s, t)(s ∗ t) と表せる.

次の定理が左除法定理とそのアルゴリズムである.

Theorem 2.3 f, f_{1}, ⋯, f_{s} ∈ R′ ( f_{i} ≠ 0 ) に対し,

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r (r = 0 または LT(f_{i}) は r のどの項も右から割り切らない )

を満たす a_{1}, ⋯, a_{s}, r ∈ R′ が存在する (以下に述べる通り計算方法がある).

(Proof)

コンピュータの言語をまねた疑似コードを用いて表示する. ただし, 疑似コードと証明での除法演算記号『A/B』及び, 『\frac{A}{B}』は, 可換の除法を意味する. この論文において以下この演算記号は特に断わらない限り同様のものとする.

Input: f_{1}, ⋯, f_{s}, f Output: a_{1}, ⋯, a_{s}, r

a_{1} := 0; ⋯; a_{s} := 0; r := 0 p := f WHILE p ≠ 0 DO

i := 1

divisionoccurred := false

WHILE i ≤ s AND divisionoccurred = false Do IF LT(f_{i}) divides LT(p) THEN

a_{i} := a_{i} + LT(p)/(LT(f_{i})sig(LT(p)/LT(f_{i}), LT(f_{i}))) p := p − (LT(p)/(LT(f_{i})sig(LT(p)/LT(f_{i}), LT(f_{i}))))f_{i} divisionoccurred := true

ELSE

i := i + 1

IF divisionoccurred = false THEN r := r + LT(p)

p := p − LT(p)

これが, 計算方法であることを示す.

この計算方法には, 各計算段階において, LT(p) を割り切るような LT(f_{i}) が存在する場合の段階 ( 除法段階とする ) と, LT(p) を割り切るような LT(f_{i}) が存在しない場合の段階 ( 余り段階とする ) の 2 通りがある. まず, a_{1}, ⋯, a_{s}, r, p の初期値を, a_{1(0)}, ⋯, a_{s(0)}, r_{(0)}, p_{(0)} とおき, m 回目の計算段階における a_{1}, ⋯, a_{s}, r, p の値を, a_{1(m)}, ⋯, a_{s(m)}, r_{(m)}, p_{(m)} とおく.

まず, 各計算段階において

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + p + r

を満たすことを示す. m = 0 のとき,

a_{1(0)}f_{1} + ⋯ + a_{s(0)}f_{s} + p_{(0)} + r_{(0)} = 0 · f_{1} + ⋯ + 0 · f_{s} + f + 0 = f.

m 回目の計算段階に進む前に,

f = a_{1(m−1)}f_{1} + ⋯ + a_{s(m−1)}f_{s} + p_{(m−1)} + r_{(m−1)}

が成り立っていると仮定する. m 回目の計算段階が除法段階のとき, 値が変わる変数は, a_{i}, p で

a_{i(m)}f_{i} + p_{(m)} = \{a_{i(m−1)} + \frac{LT(p_{(m−1)})}{LT(f_{i})sig(LT(p_{(m−1)})/LT(f_{i}), LT(f_{i}))}\} f_{i}

+ \{p_{(m−1)} − \frac{LT(p_{(m−1)})}{LT(f_{i})sig(LT(p_{(m−1)})/LT(f_{i}), LT(f_{i}))}f_{i}\}

= a_{i(m−1)}f_{i} + p_{(m−1)} より

f = a_{1(m)}f_{1} + ⋯ + a_{s(m)}f_{s} + p_{(m)} + r_{(m)}.

m 回目の計算段階が余り段階のとき, 値が変わる変数は, p, r で

p_{(m)} + r_{(m)} = {p_{(m−1)} − LT(p_{(m−1)})} + {r_{(m−1)} + LT(p_{(m−1)})} = p_{(m−1)} + r_{(m−1)}

より

f = a_{1(m)}f_{1} + ⋯ + a_{s(m)}f_{s} + p_{(m)} + r_{(m)}.

以上により, 各計算段階において

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + p + r

を満たす.

次に, p = 0 のときに計算が終わるので, 出力結果が

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r

となることは明らかである.

さらに, 出力結果が, r = 0 または ∀LT(f_{i}) は r のすべての項を割り切らないという条件を満たすことは, r の初期値 (r_{(0)} = 0) と, 余り段階に進む条件 (LT(p) を割り切るような LT(f_{i}) は存在しない ) と, 余り段階における計算 (r_{(m)} = r_{(m−1)} + LT(p_{(m−1)})) より明らかである.

最後に, 有限回の計算で p = 0 になる, つまり, 計算が有限回で終わることを示す. m 回目の計算段階が除法段階のとき

p_{(m)} = p_{(m−1)} − \frac{LT(p_{(m−1)})}{LT(f_{i})sig(LT(p_{(m−1)})/LT(f_{i}), LT(f_{i}))}f_{i}

LT (\frac{LT(p_{(m−1)})}{LT(f_{i})sig(LT(p_{(m−1)})/LT(f_{i}), LT(f_{i}))}f_{i}) = \frac{LT(p_{(m−1)})}{LT(f_{i})sig(LT(p_{(m−1)})/LT(f_{i}), LT(f_{i}))}LT(f_{i})

= sig(LT(p_{(m−1)})/LT(f_{i}), LT(f_{i}))\frac{LT(p_{(m−1)}) ∗ LT(f_{i})}{LT(f_{i})sig(LT(p_{(m−1)})/LT(f_{i}), LT(f_{i}))} = LT(p_{(m−1)})

より, multideg(p_{(m)}) < multideg(p_{(m−1)}) または p_{(m)} = 0 になる. m 回目の計算段階が余り段階のとき

p_{(m)} = p_{(m−1)} − LT(p_{(m−1)})

より, 明らかに multideg(p_{(m)}) < multideg(p_{(m−1)}) または p_{(m)} = 0 になる. 単項式順序は整列順序なので, 以上により, 有限回の計算で p = 0 になる. (証明終わり)

左除法定理アルゴリズムにより求まる商多項式と剰余多項式は f_{i} で割る順番や単項式順序に依存する.

左除法定理アルゴリズムを数式処理ソフト Mathematica 用にリスト処理計算を用いて実装したプログラム NCPolyDiv を用いて具体例を計算する. なお, プログラムと説明については, 付録 A を参照のこと.

Example 2.4 1. k (α) ⟨x, y⟩ /(yx − αxy) において

\{ \begin{matrix}f = x^{2}y^{3} + 1 \\ f_{1} = xy − y \\ f_{2} = y^{2} + 1 \end{matrix}

とする.

  In[2]:=f=x^2*y^3+1;f1=xy-y;f2=y^2+1

f を右から総次数逆辞書式順序 x > y に関して {f_{1}, f_{2}} で割る. なお, t はダミー変数である (付録 A 参照).

  In[3]:=NCPolyDiv[f,{f1,f2},grevlex,{x,y,t}]

Out[3]=\{\{\frac{y^{2}}{α^{4}} + \frac{xy^{2}}{α^{2}} , \frac{y}{α^{4}} \} , 1 − \frac{y}{α^{4}} \}

よって,

x^{2}y^{3} + 1 = (\frac{y^{2}}{α^{4}} + \frac{xy^{2}}{α^{2}} ) (xy − y) + \frac{y}{α^{4}} (y^{2} + 1) + 1 − \frac{y}{α^{4}}

である.

2. k (α) ⟨x, y, z⟩ /(yx − αxy, zy − αyz, zx − αxz) において

\{ \begin{matrix}f = xyz + yz^{3} \\ f_{1} = x − y^{2} \\ f_{2} = y^{2} + z \\ f_{3} = z − 1 \\ f_{4} = y \end{matrix}

とする.

  In[4]:=f=x*y*z+y*z^3;f1=x-y^2;f2=y^2+z;f3=z-1;f1=y

f を右から辞書式順序 x > y > z に関して {f_{1}, f_{2}, f_{3}, f_{4}} で割る.

  In[5]:=NCPolyDiv[f,{f1,f2,f3,f4},lex,{x,y,z,t}]

Out[5]=\{\{\frac{yz}{α^{2}} , \frac{yz}{α^{2}} , y + yz + yz^{2} − \frac{y}{α^{2}} − \frac{yz}{α^{2}} , 1 − \frac{1}{α^{2}} \} , 0\}

よって,

xyz + yz^{3} = \frac{yz}{α^{2}} (x − y^{2}) + \frac{yz}{α^{2}} (y^{2} + z) + (y + yz + yz^{2} − \frac{y}{α^{2}} − \frac{yz}{α^{2}} ) (z − 1) + (1 − \frac{1}{α^{2}} ) y

である.

次に, 左 Gröbner 基底を定義する. Definition 2.5 I ⊂ R′ を左イデアル, G ⊂ I を I の有限生成系とし , 単項式順序 > を固定する.

I_{L} (LT(I)) = I_{L} (LT(G))

を満たすとき, G を I の > に関する左 Gröbner 基底という. ただし, I_{L} (A) は, A を生成系とする左イデアルを表わす.

左除法定理アルゴリズムを用いて, 左 Gröbner 基底アルゴリズムを構成する. そのためには, 次の左 S 多項式という概念が必要になる. Definition 2.6 f, g ∈ R′ を零でない多項式とし, m = lcm(LM(f), LM(g)) を可換の意味での最大公約多項式 ( ここでは単項式 ) とする. このとき,

S_{L}(f, g) = sig (\frac{m}{LT(g)}, LT(g)) ; sig (\frac{m}{LT(f)}, LT(f)) · \frac{m}{LT(f)} · f − \frac{m}{LT(g)} · g

を f と g の左 S 多項式という. 左 S 多項式という概念は, 定義からわかるように各々の先導項を消去するものである. Definition 2.7 f, f_{1}, ⋯, f_{s} ∈ R′ ( ∀f_{i} ≠ 0 ) とし, F = {f_{1}, ⋯, f_{s}} を順序付き集合とする. 左除法定理アルゴリズムを用いて

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r (r = 0 または LT(f_{i}) は r のどの項も右から割り切らない ) と表したときの剰余多項式 r を, \overline{f}^{F} と表す.

左 S 多項式を用いることにより, 左 Gröbner 基底であるかどうかの判定ができる. Theorem 2.8 I = I_{L}(G) ⊂ R′ を左イデアルとしする. このとき,

G が I の左 Gröbner 基底 ⟺ ∀p, q ∈ G に対し, \overline{S_{L}(p, q)}^{G} = 0.

証明は省略する. [5] の T heorem 3.11 を参照のこと.

左 S 多項式を用いて左 Gröbner 基底アルゴリズムを構成する.

Theorem 2.9 I = I_{L}(f_{1}, ⋯, f_{s})(≠ {0}) ⊂ R′ を左イデアルとする. このとき, 次のアルゴリズムが I の左 Gröbner 基底 G を求めるものである.

Input: F = (f_{1}, ⋯, f_{s}) Output: F ⊂ G を満たす I の左 Gröbner 基底 G = (g_{1}, ⋯, g_{t})

G := F REPEAT

G′ := G
FOR p ≠ q を満たす G′ の元の組 {p, q} DO
S := \overline{S_{L}(p, q)}^{G′}
IF S ≠ 0 THEN G := G ⋃ {S}

UNTIL G = G′

(Proof)

まず始めに, すべての計算段階において, G ⊂ I であることを示す. 初期値は, G = F より, G ⊂ I. G′ ⊂ I と仮定する. 各計算段階において, G には, ある p, q ∈ G′ に対して, S = \overline{S_{L}(p, q)}^{G′} ≠ \{0\} なら, S が加わる. p, q ∈ G′ ⊂ I より, S_{L}(p, q) ∈ I となる. よって, (I ⊃)G′ = {g_{1}, ⋯, g_{s}} とすると左除法定理より,

S = S_{L}(p, q) − a_{1}g_{1}−, ⋯, −a_{s}g_{s} (∀i a_{i} ∈ R′)

となり, S ∈ I. よって, G ⋃ {S} ⊂ I より, すべての計算段階において G ⊂ I である.

次に, すべての計算段階において I_{L}(G) = I を示す. しかしこのことは, F が I の生成系であることと, すべての計算段階において F ⊂ G より明らかである.

計算が終了するのは, 最終行において G = G′ となるとき, すなわち ∀p, q ∈ G に対し, \overline{S_{L}(p, q)}^{G′} = 0 となるときである. よって, 前定理より, G は I の左 Gröbner 基底である.

最後に, 計算が有限回の計算段階で終了することを示す. G′ ⊂ G より I_{L}(LT(G′)) ⊂ I_{L}(LT(G)). まず最終行において G′ ≠ G のとき, I_{L}(LT(G′)) ≠ I_{L}(LT(G)) であることを示す. G′ ≠ G であるということは, ある p, q ∈ G′ に対して, S = \overline{S_{L}(p, q)}^{G′} が G に加わるということである. S は S_{L}(p, q) を右から G′ で割った剰余多項式より, LT(S) ∉ I_{L}(LT(G′)). 一方で LT(S) ∈ I_{L}(LT(G)) より, G′ ≠ G ならば, I_{L}(LT(G′)) ≠ I_{L}(LT(G)) である. よって, 計算段階を繰り返すことにより, 左イデアルの昇鎖が出来る. 非可換多項式環 R′ はネーター環より, 有限回で I_{L}(LT(G′)) = I_{L}(LT(G)) になる. このとき G′ = G となるので, 計算は有限回で終了する. (証明終わり)

このアルゴリズムは, S 多項式を可換の場合で定義し,(可換) 除法定理アルゴリズムを用いることにより, 同様に, (可換)Gröbner 基底を計算するものでもある. 可換の場合, Buchberger のアルゴリズムといわれており, Gröbner 基底アルゴリズムの基本になっている. 現在では Gröbner 基底アルゴリズムの様々な改良によって計算がより効率よく出来るようになっている. しかし, すべての場合に最適なアルゴリズムはなく, 計算する対象によって, 効率のよいアルゴリズムは違うものになる. アルゴリズムの改良に関しては [1], Gröbner 基底アルゴリズムにまつわる話は [6] を参照するとよい. なお,(非可換) 左 Gröbner 基底アルゴリズムに関しても可換の場合の改良が幾つか応用できる.

前定理のアルゴリズムによって出力される左 Gröbner 基底は, 必要以上の元を出力する場合がある. 次の補題により, どの元が不必要かがわかる.

Lemma 2.10 G を左イデアル I ⊂ R′ の左 Gröbner 基底, p ∈ G を LT(p) ∈ I_{L} (LT(G − {p})) を満たす多項式とする. このとき, G − {p} は I の左 Gröbner 基底である.

(Proof)

G は I の左Gröbner基底より, I_{L} (LT(I)) = I_{L} (LT(G)) を満たす.仮定より, LT(p) ∈ I_{L} (LT(G − {p})) から, I_{L} (LT(G − {p})) = I_{L} (LT(G)). よって, G − {p} は I の左 Gröbner 基底である. (証明終わり)

このことにより, 不必要な元を除去し, 元の数を極小にすることが出来る.

Definition 2.11 左イデアル I ⊂ R′ の左 Gröbner 基底 G が,

1. ∀p ∈ G に対し, LC(p) = 1

2. ∀p ∈ G に対し, LT(p) ∉ I_{L} (LT(G − {p}))

を満たすとき, G を I の左極小 Gröbner 基底という.

元の数が極小になったからといって, 左極小 Gröbner 基底が一意に定まるわけではない. 次に定める左簡約 Gröbner 基底が, 単項式順序を固定したときに, 左イデアルの左 Gröbner 基底を一意にするものである.

Definition 2.12 左イデアル I ⊂ R′ の左 Gröbner 基底 G が,

1. ∀p ∈ G に対し, LC(p) = 1

2. ∀p ∈ G に対し, p の任意の項 m に対して m ∉ I_{L} (LT(G − {p}))

を満たすとき, G を I の左簡約 Gröbner 基底という.

左簡約 Gröbner 基底の存在と一意性は次の命題により示される.

Proposition 2.13 I(≠ {0}) ⊂ R′ を左イデアルとする. このとき, I の左簡約 Gröbner 基底が一意に存在する.

(Proof)

G を I の左極小 Gröbner 基底とする. g ∈ G の任意の項 m が m ∉ I_{L} (LT(G − {g})) のとき, g を G で簡約されたと定義することにより, G のすべての元を簡約することで左簡約 Gröbner 基底を構成することが出来る. g が G で簡約されているならば, I の他のどの左極小 Gröbner 基底に対しても, 簡約されているのは明らかである. g ∈ G に対し, g′ = \overline{g}^{G−\{g\}} とおき, G′ = (G − \{g\}) ⋃ \{g′\} とする. つまり, G の元 g を g′ と入れ替えたものを G′ とする. g′ は g を右から G − {g} で割ったものであるから, G の極小性の定義より, LT(g) は左除法定理アルゴリズムの余り段階にいく. つまり, 剰余多項式 g′ の先導項は LT(g), すなわち LT(g′) = LT(g) となる. このことより, I_{L} (LT(G′)) = I_{L} (LT(G)) となり, G′ ⊂ I から, G′ もまた I の左極小 Gröbner 基底となる. さらに g′ は g を G − {g} で右から割ったときの剰余多項式より, g′ の任意の項は, LT(G − {g′}) (= LT(G − {g})) の任意の元で右から割り切れない. よって, g′ は G で簡約されている. 一度簡約されると他のどの元を簡約しても明らかに簡約されたままであるので, この操作を G のすべての元に施すことにより, 具体的に左簡約 Gröbner 基底が構成出来る. 次に一意性を示す. G と G′′ を I の左簡約 Gröbner 基底とする. G と G′′ の極小性から明らかに LT(G) = LT(G′′) である. すなわち, g ∈ G に対し, LT(g) = LT(g′′) を満たす g′′ ∈ G′′ が存在する. ここで, g = g′′ を示せば, 一意性は証明される. g − g′′ ∈ I で, G は左 Gröbner 基底より, \overline{g − g′′}^{G} = 0. LT(g) = LT(g′′) より, g − g′′ の先導項は消去されていて, 残りの項, すなわち, g, g′′ の両方の項のなかで消去されていないものは, 簡約性の定義より LT(G) (= LT(G′′)) の任意の元で右から割り切れない. 以上のことから, 0 = \overline{g − g′′}^{G} = g − g′′. よって, g = g′′. (証明終わり)

以後, 左 Gröbner 基底は, 特に断わらない限り, 簡約化されたものを扱うことにする.

上の証明における構成方法により, 左簡約 Gröbner 基底を計算することができる. 左 (簡約)Gröbner 基底アルゴリズムを数式処理ソフト Mathematica にリスト処理計算を用いて, さらに計算スピードに関して幾つかの改良を施して実装したプログラム NCGroebner を付録 B に掲げる. 以下, このプログラムを用いた具体例の計算結果について述べる.

Example 2.14

1. k (α) ⟨x, y⟩ /(yx − αxy) において

\{ \begin{matrix}f_{1} = x + 1 \\ f_{2} = y + 1 \end{matrix}

とする.

       In[7]:=f1=x+1;f2=y+1

左イデアル I = I_{L} (f_{1}, f_{2}) の辞書式順序 x > y に関する左 ( 簡約 )Gröbner 基底を求める.

       In[8]:=NCGroebner[{f1,f2},lex,{x,y,t}]
       Out[8]={1}

よって, I の左 ( 簡約 )Gröbner 基底は,

{1}

である.

すなわち, この例から示されることは,

I_{L} (x + 1, y + 1) = k (α) ⟨x, y⟩ /(yx − αxy)

ということである.

1 = \frac{y + α}{α − 1} · (x + 1) − \frac{αx + 1}{α − 1} · (y + 1) ∈ I_{L} (x + 1, y + 1)

からも, 明らかであろう ( なお, α → 1 とすると発散する ).

2. k (α) ⟨x, y, z⟩ /(yx − αxy, zy − αyz, zx − αxz) において

\{ \begin{matrix}f_{1} = x − z^{4} \\ f_{2} = y − z^{5} \\ f_{3} = x + y \end{matrix}

とする.

       In[9]:=f1=x-z^4;f2=y-z^5;f3=x+y

左イデアル J = I_{L} (f_{1}, f_{2}, f_{3}) の総次数辞書式順序 x > y > z に関する左 ( 簡約 )Gröbner 基底を求める.

       In[10]:=NCGroebner[{f1,f2,f3},grlex,{x,y,z,t}]
       Out[10]={z^{4}, x, y}

よって, J の左 ( 簡約 )Gröbner 基底は,

{x, y, z^{4}}

である.

ちなみに, 可換多項式環では, イデアル (f_{1}, f_{2}, f_{3}) ⊂ k [x, y, z] の総次数辞書式順序 x > y > z に関する ( 簡約 )Gröbner 基底は,

{x + y, yz + y, y^{2} + y, z^{4} + y}

である.

1 章で可換多項式環において, 多項式を Gröbner 基底で割った剰余多項式は, 単項式順序や割る順番に関わらず定まることを述べたが, 非可換多項式環 R′ についても同様のことがいえる.

Proposition 2.15 G = {g_{1}, ⋯, g_{t}} を左イデアル I ⊂ R′ の左 Gröbner 基底とし, f ∈ R′ とする. このとき, 次の条件を満たす r ∈ R′ が一意に定まる.

1. r = 0 または, r の任意の項は, 各 i に対し, LT(g_{i}) で右から割り切れない.

2. f − r ∈ I.

特に, r は, f を G で任意の単項式順序と任意の割る順番で右から割った時の剰余多項式である.

(Proof)

左除法定理より f = a_{1}g_{1} + ⋯ + g_{t}f_{t} + r と表わせ, g = a_{1}g_{1} + ⋯ + g_{t}f_{t} とおくことによって, 条件は満たされる. 次に r の一意性を示す. f = g + r = g′ + r′ を条件を満たすものとする. そうすると, r − r′ = g′ − g ∈ I. ここで r ≠ r′ と仮定すると, LT(r − r′) ∈ I_{L}(LT(I)) = I_{L}(LT(g_{1}), ⋯, LT(g_{t})) となる. このことより, LT(r − r′) を右から割り切るような LT(g_{i}) が存在する. このことは, 条件 1 に矛盾する. よって, r = r′ である. (証明終わり)

この命題から次の系が導きだされる.

Corollary 2.16 G を左イデアル I ⊂ R′ の左 Gröbner 基底とし, f ∈ R′ とする. このとき,

f ∈ I ⟺ f を G で右から割った時の剰余多項式が零多項式.

(Proof) (⟸): 明らか. (⟹): f ∈ I とすると, f − 0 ∈ I は, 前命題の条件を満たすので, 0 が剰余多項式. (証明終わり)

この系から, 多項式 f ∈ R′ と左イデアル I ⊂ R′ の生成元が, 与えられたとき, f が I の元であるかという問題 (左イデアルの所属問題) が, I の左 Gröbner 基底を計算し, f に左除法定理アルゴリズムを適用したときの剰余多項式が零多項式かどうかを見ることによって解決出来る.

2.2 左消去イデアルと左単項生成イデアルの共通部分

この節では, 左 Gröbner 基底アルゴリズムの応用例として, 左消去イデアルを求めるアルゴリズムと左単項生成イデアルの共通部分の生成元を計算するアルゴリズムを紹介する.

まず, l 番目左消去イデアルを定義し, アルゴリズムを紹介する.

Definition 2.17 I ⊂ R′ を左イデアルとするとき,

I_{l} := I ∩ k (α) ⟨x_{l+1}, ⋯, x_{n}⟩ /(x_{j}x_{i} − αx_{i}x_{j} | j > i ≥ l + 1)

を l 番目左消去イデアルという.

Theorem 2.18 I ⊂ R′ を左イデアル, G を I の l 番目消去型順序に関する左簡約 Gröbner 基底とする. このとき,

G_{l} := G ∩ k (α) ⟨x_{l+1}, ⋯, x_{n}⟩ /(x_{j}x_{i} − αx_{i}x_{j} | j > i ≥ l + 1)

は l 番目左消去イデアル I_{l} の左簡約 Gröbner 基底である.

(Proof)

R′_{l} = k (α) ⟨x_{l+1}, ⋯, x_{n}⟩ /(x_{j}x_{i} − αx_{i}x_{j} | j > i ≥ l + 1) とおく. まず, G_{l} ⊂ I_{l} を示す. しかしこのことは, G ⊂ I を R′_{l} に制限したことより明らか. よって, G_{l} が I_{l} の左 Gröbner 基底であることを示すには, I_{L}(LT(I_{l})) = I_{L}(LT(G_{l})) を示せば良い. (⊃) は常に成り立っているので, f ∈ I_{l} に対し LT(f) ∈ I_{L}(LT(G_{l})) を示せば良い. f ∈ I_{l} ⊂ I で G は I の左 Gröbner 基底より, ある g ∈ G について, LT(f) は左から LT(g) で割り切れる. このとき, LT(f) ∈ R′_{l} より, LT(g) ∈ R′_{l}. 今, 単項式順序は l 番目消去型順序より, g の項に x_{1}, ⋯, x_{n} の変数が含まれることはない. よって, g ∈ G_{l} となり, LT(f) ∈ I_{L}(LT(G_{l})) が示された. 残りは G_{l} の簡約性を示せばよいが, このことは G が簡約で G_{l} はその部分集合より簡約性の条件を満たすのは明らか. (証明終わり)

1 章の可換多項式環 k [x_{1}, ⋯, x_{n}] の場合と同様, l 番目消去順序で計算した l 番目左消去イデアルの生成元は, 総次数逆辞書式順序に関して左簡約 Gröbner 基底となる.

R′ [t] を R′ に可換な変数 t を付加した環とする. このとき, 次の定理から, 変数 t > x_{1} > ⋯ > x_{n} に関する 1 番目左消去イデアルを計算することにより, R′ の左生成イデアルの共通部分の生成元が計算出来る. なお, 環 R′ [t] の左 Gröbner 基底とアルゴリズムについては特に述べなかったが, 変数 t > x_{1} > ⋯ > x_{n} に対し,

sig(t^{p}x^{a}, t^{q}x^{b}) = α^{e} ただし, e = ∑_{i=1}^{n−1} (b_{i} ∑_{j=i+1}^{n} a_{j})

と定義することにより, R′ の場合と同様の議論が成り立つ. このことは, 証明をたどっていけば明らかであろう.

Theorem 2.19 I_{1}, I_{2} ⊂ R′ を左イデアルする. このとき, 左イデアル J = I_{L} (tI_{1} + (1 − t)I_{2}) ⊂ R′ [t] に対し,

I_{1} ∩ I_{2} = J ∩ R′.

(Proof) (⊂): h ∈ I_{1} ∩ I_{2} とすると, t は可換な変数より,

h = th + (1 − t)h ∈ tI_{1} + (1 − t)I_{2} = R′tI_{1} + R′(1 − t)I_{2} = I_{L} (tI_{1} + (1 − t)I_{2}) = J.

また, 明らかに h ∈ R′ より, h ∈ J ⋂ R′. (⊃): h ∈ J ∩ R′ とする. h ∈ J より, ある f ∈ I_{1}, g ∈ I_{2} に対し, h = tf + (1 − t)g と表わせる. h ∈ R′ でもあるので, h の項の中で t を含む項は消去されている. よって, t = 1 としたとき, h = f ∈ I_{1}. また, t = 0 としたとき, h = g ∈ I_{2}. (証明終わり)

3 章では, この定理を用いて, 2 変数非可換多項式環 R における左単項生成イデアルの共通部分 Rf ∩ Rg (f, g ∈ R) の左簡約 Gröbner 基底を実際に計算し, その個数などについて考察する.

第3章{左単項生成イデアルの共通部分の生 \atop 成元}

この章では, 2 変数非可換多項式環 R = k (α) ⟨x, y⟩ /(yx − αxy) に限定して, 2 章で紹介したアルゴリズムを用いて, 実際に左単項生成イデアルの共通部分の生成元を計算する. さらにこの計算結果から, 生成元が高々2 元で生成されるのではないかという予想をたてる. この章でも, 非可換多項式環上で可換の積を表したい場合には『∗』の記号を用いることにする.

3.1 生成元についての考察

f, g ∈ R に対して Rf ∩ Rg の生成元を考察するわけだが, まず初めに, f, g が共に零多項式でないとすると, 必ず Rf ∩ Rg は零でない多項式を含むことを証明しておく.

Proposition 3.1 f, g ∈ R^{×} とする. このとき,

Rf ∩ Rg ≠ {0} .

(Proof)

hf = h′g  (3.1)

を満たす零でない h, h′ ∈ R の存在性を示せば良い. deg(f) = p, deg(g) = q ( p, q は既知数 ), deg(h) = r + q, deg(h′) = r + p ( r は未知数 ) とおき, (3.1) の両辺をそれぞれ展開し, 未知数の係数を比較する方程式を解く. deg(hf) = deg(h′g) = r + p + q より, (3.1) の両辺は r + p + q 次式である. 一般に n 次式の係数の数は高々 a_{n} = \frac{(n + 1) (n + 2)}{2} 個より, (3.1) の両辺の係数を比較する方程式は高々 a_{r+p+q} 個である. また, 方程式の未知数の数は a_{r+p} + a_{r+q} である. この方程式は線形なので, 『方程式の数 < 未知数の数』 , つまりここでは,

a_{r+p+q} < a_{r+p} + a_{r+q}  (3.2)

を満たす r(≥ 0) が存在すれば, この方程式は零解以外の解を持つことになる. よって, 共に零でない h, h′ ∈ R の存在性が示される. (3.2) を満たす r(≥ 0) の存在性は,

lim_{r→+∞}(a_{r+p} + a_{r+q} − a_{r+p+q}) = +∞

より明らか. (証明終わり)

この証明は高橋宣能氏の示唆を受けたものである. なお, (3.2) の不等式を r について解くことにより,

r > \frac{−3 + \sqrt{8pq + 1}}{2}

に対して Rf ∩ Rg は, (r + p + q) 次以下の元を含むことがわかる. また, この命題は,

x_{j}x_{i} = c_{ij}x_{i}x_{j} + p_{ij} ( 1 ≤ i < j ≤ n, c_{ij} ∈ k^{×}, p_{ij} < x_{i}x_{j} )

を満たす solvable type といわれる非可換多項式環 k ⟨x_{1}, ⋯, x_{n}⟩ /(x_{j}x_{i} − c_{ij}x_{i}x_{j} − p_{ij} | i < j) についても成り立つ. ただし, p_{ij} < x_{i}x_{j} とは, p_{ij} の任意の項 t_{ij} に対し, t_{ij} < x_{i}x_{j} を表す. しかし, 一般的な非可換多項式環 k ⟨x_{1}, ⋯, x_{n}⟩ では成り立たない. 次がその例である.

Example 3.2 R = k ⟨x, y⟩ とすると, Rx ∩ Ry = {0}.

例として, 非可換多項式環 R において f = x + 1 と g = y + 1 でそれぞれ単項生成される左イデアルの共通部分の生成元を計算する.

Example 3.3 f = x + 1, g = y + 1 ∈ R とする.

  In[11]:=f=x+1;g=y+1

Rf ∩ Rg の生成元を計算する. まず,R に可換な変数 t を付加した環の左イデアル J = I_{L}(tf, (1 − t)g) の, 変数 t > x > y の 1 番目消去順序による左 Gröbner 基底を計算する. ちなみに NCGroebner は 2 章でも紹介したように 3 番目の変数に関しては可換になるようにプログラムを組んでいたのでここでは 3 番目に t をいれる. よって, 変数 t > x > y の 1 番目消去順序の行列表示は, 変数を {x, y, t} と入力するとき,

( \begin{matrix}0 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{matrix} )

となる.

  In[12]:=J=NCGroebner[{t*f,(1-t)*g},{{0,0,1},{1,1,1},{1,0,1},{0,1,1},{1,1,0}},
                  {x,y,t}]

Out[12]=\{\frac{1}{−1 + α} − \frac{t}{−1 + α} + \frac{y}{−1 + α} + \frac{tα}{−1 + α} + \frac{xα}{−1 + α} + \frac{xyα}{−1 + α},

x + x^{2} + xy + x^{2}y + \frac{1}{α} + \frac{x}{α} + \frac{y}{α} + \frac{xy}{α} , xy + xy^{2} + \frac{y}{α^{2}} + \frac{y^{2}}{α^{2}} + \frac{1}{α} + \frac{x}{α} + \frac{y}{α} + \frac{xy}{α} \}

よって, J の左 Gröbner 基底は,

\{t + \frac{αxy}{α − 1} + \frac{αx}{α − 1} + \frac{y}{α − 1} + \frac{1}{α − 1}, x^{2}y + x^{2} + \frac{(α + 1)}{α}xy + \frac{(α + 1)}{α}x + \frac{y}{α} + \frac{1}{α},

xy^{2} + \frac{(α + 1)}{α}xy + \frac{y^{2}}{α^{2}} + \frac{x}{α} + \frac{(α + 1)}{α^{2}}y + \frac{1}{α}\}

である. この集合を R に制限する, すなわち, 元のなかで t を含むものを除くと Rf ∩ Rg の生成元になる. よって,

  In[13]:={J[[2]],J[[3]]}

Out[13]=\{x + x^{2} + xy + x^{2}y + \frac{1}{α} + \frac{x}{α} + \frac{y}{α} + \frac{xy}{α} , xy + xy^{2} + \frac{y}{α^{2}} + \frac{y^{2}}{α^{2}} + \frac{1}{α} + \frac{x}{α} + \frac{y}{α} + \frac{xy}{α} \}

より,

(*) R · (x + 1) ∩ R · (y + 1) = R · (x^{2}y + x^{2} + \frac{(α + 1)}{α}xy + \frac{(α + 1)}{α}x + \frac{y}{α} + \frac{1}{α})

+R · (xy^{2} + \frac{(α + 1)}{α}xy + \frac{y^{2}}{α^{2}} + \frac{x}{α} + \frac{(α + 1)}{α^{2}}y + \frac{1}{α})

である. 2 章でもふれたが, この生成元は総次数逆辞書式順序に関して左簡約 Gröbner 基底になっている.

この例の計算結果 (*) が正しいことを検証しておく.

まず,

\{ \begin{matrix}h_{1} = tf = t + tx \\ h_{2} = (1 − t)g = 1 − t + y − ty \\ g_{1} = t + \frac{αxy}{α − 1} + \frac{αx}{α − 1} + \frac{y}{α − 1} + \frac{1}{α − 1} \\ g_{2} = x^{2}y + x^{2} + \frac{(α + 1)}{α}xy + \frac{(α + 1)}{α}x + \frac{y}{α} + \frac{1}{α} \\ g_{3} = xy^{2} + \frac{(α + 1)}{α}xy + \frac{y^{2}}{α^{2}} + \frac{x}{α} + \frac{(α + 1)}{α^{2}}y + \frac{1}{α} \end{matrix}

とおく.

  In[14]:=h1=t+t*x;h2=1-t+y-t*y;g1=J[[1]];g2=J[[2]];g3=J[[3]]

まず, I_{L}(h_{1}, h_{2}) = I_{L}(g_{1}, g_{2}, g_{3})(⊂ R [t]) を示す. (⊂): h_{1}, h_{2} ∈ I_{L}(g_{1}, g_{2}, g_{3}) を示せば良い. 左除法定理アルゴリズムより,

  In[15]:=NCPolyDiv[h1,{g1,g2,g3},{{0,0,1},{1,1,1},{1,0,1},{0,1,1},{1,1,0}},{x,y,t}]

Out[15]=\{\{1 + x, −\frac{α}{−1 + α}, 0\} , 0\}

  In[16]:=NCPolyDiv[h2,{g1,g2,g3},{{0,0,1},{1,1,1},{1,0,1},{0,1,1},{1,1,0}},{x,y,t}]

Out[16]=\{\{−1 − y, 0, \frac{α^{2}}{−1 + α}\} , 0\}

よって,

h_{1} = (x + 1) g_{1} − \frac{α}{α − 1}g_{2} + 0 · g_{3} ∈ I_{L}(g_{1}, g_{2}, g_{3})

h_{2} = − (y + 1) g_{1} + 0 · g_{2} + \frac{α^{2}}{α − 1}g_{3} ∈ I_{L}(g_{1}, g_{2}, g_{3})

このことは, 手計算によって確認出来る. (⊃): g_{i} = a_{i}h_{1} +b_{i}h_{2} となる a_{i}, b_{i} を求めたいが, {h_{1}, h_{2}} が左 Gröbner 基底でないため, 単純に左除法定理アルゴリズムを適用しても剰余多項式が 0 にならない (先の例では,{g_{1}, g_{2}, g_{3}} が左 Gröbner 基底であろうという予想があったから, 左イデアルの所属問題から左除法定理アルゴリズムのみで判定が出来た). よって, ここでは, より一般的に多項式 f ∈ R [t] と左イデアル I = I_{L}(f_{1}, ⋯, f_{s}) ⊂ R [t] が与えられたときに, f ∈ I ならば, 具体的に, f = a_{1}f_{1} + ⋯ + a_{s}f_{s} (a_{i} ∈ R [t]) のような表現のひとつを計算するアルゴリズムが欲しい. このアルゴリズムは左 S 多項式と左 Gröbner 基底アルゴリズムと左除法定理アルゴリズムを組み合わせることにより構成することが出来るが, ここでは具体的な表現が知りたいだけなのでアルゴリズムの構成方法については省略する. そこで, 数式処理ソフト Mathematica でリスト処理計算を用いて組んだプログラム NCIdealRepr を用いて, g_{1}, g_{2}, g_{3} ∈ I_{L}(h_{1}, h_{2}) を確かめる. なお, プログラムと説明については, 付録 C を参照のこと.

  In[18]:=NCIdealRepr[g1,{h1,h2},{x,y,t}]

Out[18]=\{\frac{y}{−1 + α} + \frac{α}{−1 + α}, \frac{1}{−1 + α} + \frac{xα}{−1 + α}\}

  In[19]:=NCIdealRepr[g2,{h1,h2},{x,y,t}]

Out[19]=\{x + \frac{1}{α} + \frac{y}{α} + \frac{xy}{α} , x + x^{2} + \frac{1}{α} + \frac{x}{α}\}

  In[20]:=NCIdealRepr[g3,{h1,h2},{x,y,t}]

Out[20]=\{\frac{y}{α^{2}} + \frac{y^{2}}{α^{2}} + \frac{1}{α} + \frac{y}{α}, xy + \frac{y}{α^{2}} + \frac{1}{α} + \frac{x}{α}\}

よって,

g_{1} = (\frac{y}{α − 1} + \frac{α}{α − 1}) h_{1} + (\frac{1}{α − 1} + \frac{αx}{α − 1}) h_{2} ∈ I_{L}(h_{1}, h_{2})

g_{2} = (x + \frac{1}{α} + \frac{y}{α} + \frac{xy}{α} ) h_{1} + (x^{2} + \frac{α + 1}{α}x + \frac{1}{α}) h_{2} ∈ I_{L}(h_{1}, h_{2})

g_{3} = (\frac{y^{2}}{α^{2}} + \frac{α + 1}{α^{2}}y + \frac{1}{α}) h_{1} + (xy + \frac{y}{α^{2}} + \frac{1}{α} + \frac{x}{α}) h_{2} ∈ I_{L}(h_{1}, h_{2})

このことが正しいことは, 手計算によって確認出来る.

最後に {g_{1}, g_{2}, g_{3}} が 1 番目消去順序 t > x > y に関する左簡約 Gröbner 基底であることを示す. 左 Gröbner 基底であることは, \overline{S_{L}(g_{1}, g_{2})}^{\{g_{1},g_{2},g_{3}\}} = \overline{S_{L}(g_{1}, g_{3})}^{\{g_{1},g_{2},g_{3}\}} = \overline{S_{L}(g_{2}, g_{3})}^{\{g_{1},g_{2},g_{3}\}} = 0 を示せば十分である.

S_{L}(g_{1}, g_{2}) = x^{2}yg_{1} − tg_{2} = \frac{x^{2}y}{α − 1} + \frac{x^{2}y^{2}}{α − 1} + \frac{α^{2}x^{3}y}{α − 1} + \frac{α^{2}x^{3}y^{2}}{α − 1} − txy − tx − tx^{2} − \frac{t}{α} − \frac{tx}{α} − \frac{ty}{α} − \frac{txy}{α} = r_{12}

S_{L}(g_{1}, g_{3}) = xy^{2}g_{1} − tg_{3}

= \frac{xy^{2}}{α − 1} + \frac{xy^{3}}{α − 1} + \frac{α^{3}x^{2}y^{2}}{α − 1} + \frac{α^{3}x^{2}y^{3}}{α − 1} − txy − \frac{ty}{α^{2}} − \frac{ty^{2}}{α^{2}} − \frac{t}{α} − \frac{tx}{α} − \frac{ty}{α} − \frac{txy}{α} = r_{13}

S_{L}(g_{2}, g_{3}) = \frac{y}{α^{2}} g_{2} − xg_{3} = \frac{xy^{2}}{α} + \frac{y}{α^{3}} + \frac{y^{2}}{α^{3}} − \frac{x}{α} − \frac{x^{2}}{α} − \frac{x^{2}y}{α} = r_{23}

このことが正しいことは, 手計算によって確認出来る.

In[21]:=r12=\frac{x^{2}y}{α − 1} + \frac{x^{2}y^{2}}{α − 1} + \frac{α^{2}x^{3}y}{α − 1} + \frac{α^{2}x^{3}y^{2}}{α − 1} − txy − tx − tx^{2} − \frac{t}{α} − \frac{tx}{α} − \frac{ty}{α} − \frac{txy}{α}

In[22]:=r13=\frac{xy^{2}}{α − 1} + \frac{xy^{3}}{α − 1} + \frac{α^{3}x^{2}y^{2}}{α − 1} + \frac{α^{3}x^{2}y^{3}}{α − 1} − txy − \frac{ty}{α^{2}} − \frac{ty^{2}}{α^{2}} − \frac{t}{α} − \frac{tx}{α} − \frac{ty}{α} − \frac{txy}{α}

In[23]:=r23=\frac{xy^{2}}{α} + \frac{y}{α^{3}} + \frac{y^{2}}{α^{3}} − \frac{x}{α} − \frac{x^{2}}{α} − \frac{x^{2}y}{α}

左除法定理アルゴリズムより,

  In[24]:=NCPolyDiv[r12,{g1,g2,g3},{{0,0,1},{1,1,1},{1,0,1},{0,1,1},{1,1,0}},{x,y,t}]

Out[24]=\{\{−x − x^{2} − xy − \frac{1}{α} − \frac{x}{α} − \frac{y}{α} − \frac{xy}{α} , \frac{1}{−1 + α} + \frac{y}{−1 + α} + \frac{xy}{−1 + α} + \frac{xα}{−1 + α}, 0\} , 0\}

  In[25]:=NCPolyDiv[r13,{g1,g2,g3},{{0,0,1},{1,1,1},{1,0,1},{0,1,1},{1,1,0}},{x,y,t}]

Out[25]=\{\{−xy − \frac{y}{α^{2}} − \frac{y^{2}}{α^{2}} − \frac{1}{α} − \frac{x}{α} − \frac{y}{α} − \frac{xy}{α} , \frac{1}{−1 + α} + \frac{y}{−1 + α} + \frac{y}{(−1 + α) α} + \frac{y^{2}}{(−1 + α) α}, 0\} , 0\}

  In[26]:=NCPolyDiv[r23,{g1,g2,g3},{{0,0,1},{1,1,1},{1,0,1},{0,1,1},{1,1,0}},{x,y,t}]

Out[26]=\{\{0, −\frac{1}{α}, −\frac{1}{α}\} , 0\}

よって,

r_{12} = − (x + x^{2} + xy + \frac{1}{α} + \frac{x}{α} + \frac{y}{α} + \frac{xy}{α} ) g_{1} + (\frac{1}{α − 1} + \frac{y}{α − 1} + \frac{xy}{α − 1} + \frac{αx}{α − 1}) g_{2} + 0 · g_{3} + 0

r_{13} = − (xy + \frac{y}{α^{2}} + \frac{y^{2}}{α^{2}} + \frac{1}{α} + \frac{x}{α} + \frac{y}{α} + \frac{xy}{α} ) g_{1} + (\frac{1}{α − 1} + \frac{y}{α − 1} + \frac{y}{α (α − 1)} + \frac{y^{2}}{α (α − 1)}) g_{2} + 0 · g_{3} + 0

r_{23} = 0 · g_{1} − \frac{1}{α}g_{2} + \frac{1}{α}g_{3} + 0

このことが正しいことは, 手計算によって確認出来る. よって, {g_{1}, g_{2}, g_{3}} は, 1 番目消去順序 t > x > y に関する左 Gröbner 基底である. 簡約性については容易に確認出来る.

以上により, {g_{1}, g_{2}, g_{3}} は, 左イデアル I_{L}(h_{1}, h_{2}) (⊂ R [t]) の 1 番目消去順序 t > x > y に関する左簡約 Gröbner 基底であることは示された. よって Theorem 2.19 より (∗) が確認出来た.

今求めた左イデアル R · (x + 1) ∩ R · (y + 1) の生成元 {g_{2}, g_{3}} が総次数逆辞書式順序に関して左簡約 Gröbner 基底になっていることより, 次の補題から, この左イデアルは単項生成でないことがわかる.

Lemma 3.4 I ⊂ R を左イデアルとし, I の左簡約 Gröbner 基底 G を, |G| ≥ 2 を満たすようにする単項式順序が存在するとする. このとき, I は単項生成ではない.

(Proof)

そうでないとする. すなわち, Rh = I を満たす h ∈ R が存在するとする. {h} は, どの単項式順序に関しても左 Gröbner 基底である左普遍 Gröbner 基底であり, 先導項の係数が 1 になるように定数倍することにより, {h} は左簡約 Gröbner 基底としてよい. 左簡約 Gröbner 基底の一意性より, ある単項式順序で左簡約 Gröbner 基底が G になることはありえない. よって, 矛盾. (証明終わり)

よって, この計算例により, 非可換多項式環 R では, 一般的に左単項生成イデアルの共通部分は単項生成にならないことがわかる.

また, g_{2}, g_{3} をそれぞれ NCPolyDiv を用いて右から x + 1, y + 1 で割ることにより, 次の 2 通りの既約因子分解が得られる.

g_{2} = x^{2}y + x^{2} + \frac{(α + 1)}{α}xy + \frac{(α + 1)}{α}x + \frac{y}{α} + \frac{1}{α} = \frac{1}{α}(xy + αx + y + 1)(x + 1) = \frac{1}{α}(αx + 1)(x + 1)(y + 1)

g_{3} = xy^{2} + \frac{(α + 1)}{α}xy + \frac{y^{2}}{α^{2}} + \frac{x}{α} + \frac{(α + 1)}{α^{2}}y + \frac{1}{α} = \frac{1}{α^{2}} (y + α)(y + 1)(x + 1)

= \frac{1}{α^{2}} (α^{2}xy + αx + y + α)(y + 1)

よって, このことから, 非可換多項式環 R では, 一般的に多項式の既約因子分解が一意でないことがわかる.

ここで一般に Rf ∩Rg の生成元の数はどうなるのかという疑問が残る. そこで, いろいろな f, g ∈ R に対し, 生成元の数を計算すると次の表になる.

f  g  生成元の数生成元の数
(grevlex order) (lex order)
x + 1  y + 1  2  2
x + y  y + 1  2  2
x^{2} + 1  y^{2} + 1  2  2
x^{3} + y  y^{3} + 1  2  2
x^{3} + 1  y^{3} + 1  2  2
x^{10}y^{8} − x^{5}y^{6}  x^{7}y^{3} − x^{2}y^{2}  2  2
xy + x + 1  x + y  2  2
xy + x + 1  x + y + 1  2  2
x + y + 1  xy + 1  2  2
x^{2} + x + y + 1  y + 1  2  2
x + y^{2} + 1  x^{2} + 1  2  2
x^{2} + y^{2}  x + 1  2  2
x^{2} − y^{2} − 1  x − y  2  2
x^{2} − y^{2} − 1  x − y + 1  2  2
x^{4} − xy  y − 1  2  2
x^{2}y − xy  xy^{2} − xy  2  2
x^{2}y − xy − x  xy^{2} − xy + y  2  2
x^{4} − xy  x + y^{3}  3  2
x^{2} + y  y^{2} + x  3  2
x^{3} + y  y^{3} + x  3  2
x^{3} + y^{2}  y^{3} + x^{2}  3  2
x^{3}y + y^{2}  xy^{3} + x^{2}  3  2
x^{3}y + xy^{2}  xy^{3} + x^{2}  3  2
x^{5}y + x^{3}y^{2}  xy^{3} + x^{2}y  3  2
x^{5}y^{10} + x^{3}y^{7}  x^{10}y^{3} + x^{2}y^{8}  3  2
x^{165}y^{30} − xy  x^{15}y^{46} − x^{21}y^{6}  3  ?
x^{3}y^{2} + xy^{5}  x^{2}y + x^{6}y^{2}  3  2
x^{3}y^{6} + xy^{10}  x^{2}y + x^{10}y^{2}  3  2
x^{4} − y  x + y^{3}  3  2
x − y  x^{2} − y^{2}  1  1
x + y  x^{2} − y^{2}  1  1
x − y  x^{2} + y^{2}  1  1
x + y  x^{2} + y^{2}  1  1
xy^{2} + y  x^{3}y^{2} + x^{2}y + 1  1  1
y + 1  x^{2}y + x^{2} + 1  1  1
x^{5}y^{4} + x^{2}y^{3} + y + 1  x^{7}y^{4} + x^{4}y^{3} + x^{2}y + x^{2} + 1  1  1
x^{5}y^{4} + x^{2}y^{3} + y + 1  x^{7}y^{4} + x^{4}y^{3} + x^{2}y + x^{2} + x  1  1
x^{5}y^{4} + x^{2}y^{3} + y + 1  x^{7}y^{4} + x^{4}y^{3} + x^{2}y + x^{2} + y  1  1
x^{2}y + y^{3} + 1  α^{6}x^{4}y^{4} + α^{2}x^{2}y^{2} + x^{2}y^{6} + y^{4} + x^{2}y^{3} + y + 1  1  1
x^{2}y + y^{3} + 1  α^{6}x^{4}y^{4} + α^{2}x^{2}y^{2} + x^{2}y^{6} + y^{4} + x^{2}y^{3} + 2y  1  1

表の一番右の欄は, 辞書式順序に関して左簡約 Gröbner 基底を計算し直したものである. ここで計算した例では, 生成元は, 辞書式順序に関しては高々2 元になった. ただし, 『?』のところは容量超過のため計算が完了しなかった. また, 単項生成になる例もあった.

それでは, 単項生成になる場合はどんな時であろうか. 明らかに単項生成になる場合として, 次の 2 つ場合が挙げられる. 証明は明らかなので省略する.

Lemma 3.5 f, g ∈ k [x] または f, g ∈ k [y] のとき,

Rf ∩ Rg = R · lcm(f, g).

Lemma 3.6 f, g ∈ R, f は g で右から割り切れるとする. このとき,

Rf ∩ Rg = Rf.

そこで, これらの場合ほど明らかでない単項生成の場合について論じる.

議論に入る前に, 幾つかの定義と補題等を紹介する.

Definition 3.7 f ∈ R, f = ∑_{γ=(a,b)} c_{γ}x^{a}y^{b}, c_{γ} ∈ k (α) は有限個を除いて 0 とする. このとき,

F_{f} := {f^{∗} ∈ R | f^{∗} = ∑_{γ=(a,b)} c′_{γ}x^{a}y^{b} c′_{γ} ∈ k (α) c_{γ} = 0 ⟺ c′_{γ} = 0}

と定義する.

F_{f} は, 直観的には, 多項式 f の項の係数を 0 でない任意の係数に置き換えた多項式 f^{∗} の全体の集合である.

Lemma 3.8 f, m ∈ R, m は単項式とする. このとき, fm = mf^{∗} を満たすような f^{∗} ∈ F_{f} が存在する.

(Proof)

f = ∑_{γ=(a,b)} c_{γ}x^{a}y^{b}, c_{γ} ∈ k (α) は有限個を除いて 0 とする. また, m = x^{a′}y^{b′} とする.

fm = ( ∑_{γ=(a,b)} c_{γ}x^{a}y^{b}) x^{a′}y^{b′}

= ∑_{γ=(a,b)} c_{γ}sig(x^{a}y^{b}, x^{a′}y^{b′})x^{a+a′}y^{b+b′}

= ∑_{γ=(a,b)} x^{a′}y^{b′}c_{γ} \frac{sig(x^{a}y^{b}, x^{a′}y^{b′})}{sig(x^{a′}y^{b′}, x^{a}y^{b})}x^{a}y^{b}

= x^{a′}y^{b′} ∑_{γ=(a,b)} c_{γ} \frac{sig(x^{a}y^{b}, x^{a′}y^{b′})}{sig(x^{a′}y^{b′}, x^{a}y^{b})}x^{a}y^{b} = m ∑_{γ=(a,b)} c_{γ} \frac{sig(x^{a}y^{b}, x^{a′}y^{b′})}{sig(x^{a′}y^{b′}, x^{a}y^{b})}x^{a}y^{b}

よって, f^{∗} = ∑_{γ=(a,b)} c_{γ} \frac{sig(x^{a}y^{b}, x^{a′}y^{b′})}{sig(x^{a′}y^{b′}, x^{a}y^{b})}x^{a}y^{b} ∈ F_{f}.

(証明終わり)

Definition 3.9 前補題の f^{∗} を f_{m}^{∗} と表す.

Proposition 3.10 f(≠ 0) ∈ R とし, m_{f} を可換の意味での f の各項の最大公約単項式とする. このとき,

f = f̃· m_{f}

と表す表現が一意に存在する.

(Proof)

f は m_{f} で右から割り切れるので, 左除法定理から f̃ ∈ R の存在性は明らか. また, 1 つの元で左除法定理アルゴリズムを用いて右から割るので, f̃ の一意性についても明らか. (証明終わり)

Definition 3.11 上の表現 f = f̃· m_{f} を f の単項式表現という.

Example 3.12 f = x^{2}y + xy^{2} ∈ R とする.

f = (x + \frac{1}{α}y) · xy (f̃ = x + \frac{1}{α}y m_{f} = xy)

が f の単項式表現である.

Lemma 3.13 f(≠ 0) ∈ R とし, f = f̃· m_{f} を f の単項式表現とする. このとき,

1. m_{f} = 1.

2. ∀f̃^{∗} ∈ F_{f} に対し, m_{f^{∗}} = 1.

3. f が右から単項式 m ∈ R で割り切れるとする. このとき, m_{f} は右から m で割り切れる.

(Proof)

1. 単項式表現の定義から明らか.

2. f̃ と f̃^{∗} では, 各項の変数の部分は同じなので, 明らか.

3. f = t_{1} + ⋯ + t_{s} ( t_{i} は f の項で互いに打ち消し合うものはない ) とする. f が右から m で割り切れるということは, t_{i} = a_{i}m を満たすような項 a_{i} ∈ R が存在する. t_{i} = sig(a_{i}, m)(a_{i} ∗ m) より, m は可換の意味で f の任意の項を割り切る. m_{f} は可換の意味で各項の最大公約単項式より, m_{f} は可換の意味で m で割り切れる. よって, m_{f} = b ∗ m = \frac{1}{sig(b, m)}bm を満たす単項式

b ∈ R が存在する. このことから, m_{f} は右から m で割り切れる.

(証明終わり)

Proposition 3.14 f, g ∈ R を共に零でない多項式とし, f = f̃· m_{f}, g = g̃ · m_{g} をそれぞれの単項式表現とする. このとき,

m_{fg} = m_{f} ∗ m_{g}.

特に, m_{fg} = m_{gf} である.

(Proof) fg = (f̃· m_{f}) · (g̃ · m_{g}) = (f̃· g̃_{m_{f}}^{∗})m_{f}m_{g} = {sig(m_{f}, m_{g}) · f̃· g̃_{m_{f}}^{∗} } (m_{f} ∗ m_{g}) 後は, m_{_{f}·g_{m_{f}}^{∗}} = 1 を示せば良い. ここで着目したいのは, h ∈ R に対し, m_{h} = 1 であるということは, h の項には, 定数項があるか, もしくは, x のみを含む項と y のみを含む項が共にあるということであ

る. 今, m_{f} = m_{g_{m_{f}}^{∗}} = 1 より,

f̃ = p + a_{1}x^{b_{1}} + a_{2}y^{b_{2}} + a_{3} g̃_{m_{f}}^{∗} = q + c_{1}x^{d_{1}} + c_{2}y^{d_{2}} + c_{3}

p, q ∈ R: 後の 3 つの単項式を含まない. b_{i}, d_{i} ≥ 0: それぞれ, x のみを含む項, y のみを含む項の次数として最小になるようにとる. a_{i}, c_{i} ∈ k (α)

a_{3} = 0 ⟹ a_{1} ≠ 0, a_{2} ≠ 0, b_{1} > 0, b_{2} > 0
c_{3} = 0 ⟹ c_{1} ≠ 0, c_{2} ≠ 0, d_{1} > 0, d_{2} > 0

とおける. a_{3} = c_{3} = 0 のとき,b_{i}, d_{i} の最小性から,

f̃· g̃_{m_{f}}^{∗} = r + a_{1}c_{1}x^{b_{1}+d_{1}} + a_{2}c_{2}y^{b_{2}+d_{2}} r ∈ R: 後の 2 つの単項式を含まない.

のように表せ, a_{i}c_{i} ≠ 0, b_{i}+d_{i} > 0 から x のみを含む項と y のみを含む項が共にあるので, m_{_{f}·g_{m_{f}}^{∗}} = 1.

a_{3} ≠ 0 かつ c_{3} ≠ 0 のとき, f̃ · g̃_{m_{f}}^{∗} には定数項 a_{3}c_{3}(≠ 0) があるので, m_{_{f}·g_{m_{f}}^{∗}} = 1. a_{3} ≠ 0, c_{3} = 0 のとき,d_{i} の最小性から,

f̃· g̃_{m_{f}}^{∗} = r′ + a_{3}c_{1}x^{d_{1}} + a_{3}c_{2}y^{d_{2}} r′ ∈ R: 後の 2 つの単項式を含まない.

のように表せ, a_{3}c_{i} ≠ 0, d_{i} > 0 から x のみを含む項と y のみを含む項が共にあるので, m_{_{f}·g_{m_{f}}^{∗}} = 1. a_{3} = 0, c_{3} ≠ 0 のときも同様に示せる. 以上により, m_{_{f}·g_{m_{f}}^{∗}} = 1. よって, m_{fg} = m_{f} ∗ m_{g} がいえる. このことから, 特に, m_{fg} = m_{f} ∗ m_{g} = m_{g} ∗ m_{f} = m_{gf} が成り立つ. (証明終わり)

ここからは, 単項生成になることが明らかでないいくつかの場合の構成方法について述べる.

どちらか一方が単項式の場合, 計算実験より, 単項生成になるであろうという予想がつき, 単項生成元を具体的に構成し, それが正しいことを証明した.

Proposition 3.15 f, m ∈ R, m は単項式, 可換の意味で gcd(m_{f}, m) = m′′ とし, 可換の除法で

m′ = \frac{m}{m′′} とする. このとき,

Rf ∩ Rm = Rm′f.

(Proof)

f は右から m′′ で割り切れるので, f = gm′′ を満たす g ∈ R が存在する. (⊃): m′f ∈ Rf は自明. また,

m′f = m′gm′′ = g_{m′}^{∗}m′m′′ = g_{m′}^{∗} \frac{1}{sig(m′, m′′)}(m′ ∗ m′′) = \frac{1}{sig(m′, m′′)}g_{m′}^{∗}m ∈ Rm.

(⊂): h ∈ Rf ∩ Rm とする. h は, ある a, b ∈ R によって h = af = bm と表わせる.

agm′′ = af = bm = b(m′ ∗ m′′) = \frac{1}{sig(m′, m′′)}bm′m′′

よって, ag = \frac{1}{sig(m′, m′′)}bm′ より, ag は右から m′ で割り切れる. a = ã · m_{a}, g = g̃ · m_{g} をそれぞれ

の単項式表現とすると, Proposition 3.14, Lemma 3.13 より, m_{a} ∗ m_{g} は右から m′ で割り切れる. ここで, 可換の意味で gcd(m_{g}, m′) = 1 を示す. m′′ のとりかたにより, g は m′ の可換の意味での (定数以外の) 約数で割り切れない. よって, m_{g} は Proposition 3.14 より, m′ の可換の意味での定数以外の任意の約数で割り切れない. 以上により, gcd(m_{g}, m′) = 1 である. 一方で, m_{a} ∗ m_{g} は右から m′ で割り切れるので, 可換の意味でも m_{a} ∗ m_{g} は m′ で割り切れることから, 可換の意味で m_{a} は m′ で割り切れる. もちろん, m_{a} は右からも m′ で割り切れるので, a は右から m′ で割り切れる. よって, a = pm を満たす p ∈ R が存在し, h = af = pm′f ∈ Rm′f である. (証明終わり)

表での単項生成になる例はすべて f, g とも単項式ではない. 実はすべて f = ag + cm (c ∈ k (α) , a, m ∈ R, m は単項式 ) の関係を満たしている. さらに一般化して, f = f′l, g = g′l (f′, g′ の右共通因子は定数以外にない) と表わした時に f′ = ag′ + cm (c ∈ k (α) , a, m ∈ R, m は単項式 ) の関係を満たしている場合も, 単項生成になるであろうという予想を計算実験からたて, 単項生成元を具体的に構成し, それが正しいことを証明した. 特に c = 1, a = 0 とおくことにより, 前命題はこの場合の特別な例だったことがわかる.

Proposition 3.16 f, g ∈ R を, f′, g′, l ∈ R ( f′ と g′ の右共通因子は定数のみ ) を用いて, f = f′l, g = g′l と表す. このとき,

g′ = af′ + cm
a, m ∈ R, m は単項式, c ∈ k (α)^{×}

と表すことが出来るならば,

Rf ∩ Rg = Rf′_{m}^{∗}g.

(Proof) (⊃): f′_{m}^{∗}g ∈ Rg は明らか. また,

f′_{m}^{∗}g = f′_{m}^{∗}g′l = f′_{m}^{∗}(af′ + cm)l = (f′_{m}^{∗}af′ + cf′_{m}^{∗}m)l = (f′_{m}^{∗}af′ + cmf′)l = (f′_{m}^{∗}a + cm)f ∈ Rf.

(⊂): h ∈ Rf ∩ Rg とする. h ∈ Rg より, ある p ∈ R によって, h = pg = p(af′ + cm)l と表せる. よって, p が右から f′_{m}^{∗} で割り切れることを示せばよい. 一方で, h ∈ Rf でもあるので, ある q ∈ R によって h = qf と表せる. よって, qf = p(af′ + cm)l の両辺を右から l で割り, 式を整理することにより, r = q − pa に対し,

cpm = rf′  (3.3)

となる. p, r, f′ の単項式表現をそれぞれ, p = p̃ · m_{p}, r = r̃ · m_{r}, f′ = f̃′ · m_{f′} とおき, (3.3) の両辺の単項式表現の単項式の部分を比較することにより,

m_{p} ∗ m = m_{r} ∗ m_{f′}  (3.4)

が得られる. また, p が右から f′_{m}^{∗} で割り切れることを示せばよいことと, (3.3) から, rf′ が右から f′_{m}^{∗}m で割り切れることを示せばよいことになる. さらに, f′_{m}^{∗}m = mf′ から, r が右から m で割り切れることを示せばよいことになる. 今, m と m_{f′} が, 可換の意味で定数以外の共通因子 γ を持つとすると, m と m_{f′} はそれぞれ右から γ で割り切れる. よって, g′ = a · f̃′ · m_{f′} + cm から, g′ は右から γ で割り切れる. また, f′ = f̃′ · m_{f′} も右から γ で割り切れる. このことは, f′ と g′ のとり方に矛盾する. よって, m と m_{f′} は可換の意味で互いに素である. よって, (3.4) より, 可換の意味で m_{r} は m で割り切れる. よって, m_{r} は右から m で割り切れるので, r は右から m で割り切れる. (証明終わり)

一般に R では, 既約因子分解は一意ではなかった. よって, この命題における f′, g′ も一意ではない. また, f′, g′ を固定しても, f′ = ag′ + cm の表現も一意ではない. 例えば, f′ = 2x^{2} + xy, g′ = x + y に対し, f′ = xg′ + x^{2} = 2xg′ − xy である. しかし, この命題からわかることは, 表し方は一意ではないが, とにかく, g′_{m}^{∗} は 0 でない定数倍を除いて一意に定まるということである.

Example 3.17 f, g ∈ R を

\{ \begin{matrix}f = (x + y)(x + 1)(y + 1) = (x + 1)(x + y)(y + 1) = x^{2}y + αxy^{2} + x^{2} + (α + 1)xy + y^{2} + x + y \\ g = (x + 1)(x + y)(y + 1) = x^{2}y + xy^{2} + x^{2} + 2xy + y^{2} + x + y \end{matrix}

と定める. f, g を共に右から y + 1 で割ると, f′ = x^{2} + αxy + x + y, g′ = x^{2} + xy + x + y とおけ, f, g の右共通因子は定数のみであることが容易に確かめられる. ここで,

f′ = g′ + (α − 1)xy

と表せ,

g′_{xy}^{∗} = α^{2}x^{2} + xy + αx + \frac{y}{α}

より,

Rf ∩ Rg = R · (α^{2}x^{2} + xy + αx + \frac{y}{α}) f = Rh

h = α^{2}x^{4}y + α^{2} (α + 1) x^{3}y^{2} + α^{2}x^{2}y^{3} + α^{2}x^{4} + α(α + 1)^{2}x^{3}y + α (3α + 2) x^{2}y^{2} + (α + 1) xy^{3}

+α (α + 1) x^{3} + α (2α + 3) x^{2}y + 2 (α + 1) xy^{2} + \frac{y^{3}}{α} + αx^{2} + (α + 1) xy + \frac{y^{2}}{α}

である. ちなみに左 Gröbner 基底アルゴリズムを用いて生成元を計算すると,

  In[27]:=f=x^2*y+α*x*y^2+x^2+(α+1)*x*y+y^2+x+y
  In[28]:=g=x^2*y+x*y^2+x^2+2x*y+y^2+x+y
  In[29]:=NCGroebner[{t*f,(1-t)*g},{{0,0,1},{1,1,1},{1,0,1},{0,1,1},{1,1,0}},
                {x,y,t}]

Out[29]=\{−\frac{tx}{−1 + α} − \frac{tx^{2}}{−1 + α} − \frac{ty}{−1 + α} − \frac{txy}{−1 + α} − \frac{tx^{2}y}{−1 + α} − \frac{ty^{2}}{−1 + α} − \frac{xα}{−1 + α} + \frac{txα}{−1 + α}−

\frac{x^{2}α}{−1 + α} + \frac{tx^{2}α}{−1 + α} − \frac{yα}{−1 + α} + \frac{tyα}{−1 + α} − \frac{2xyα}{−1 + α} + \frac{txyα}{−1 + α} − \frac{x^{2}yα}{−1 + α} + \frac{tx^{2}yα}{−1 + α}−

\frac{y^{2}α}{−1 + α} + \frac{ty^{2}α}{−1 + α} − \frac{xy^{2}α}{−1 + α},

\frac{x}{−1 + α} + \frac{x^{2}}{−1 + α} + \frac{y}{−1 + α} + \frac{2xy}{−1 + α} − \frac{txy}{−1 + α} + \frac{x^{2}y}{−1 + α} + \frac{y^{2}}{−1 + α} + \frac{xy^{2}}{−1 + α}−

\frac{txy^{2}}{−1 + α} + \frac{txyα}{−1 + α} + \frac{txy^{2}α}{−1 + α},

−\frac{ty^{2}}{−1 + α} − \frac{ty^{3}}{−1 + α} − \frac{xα}{−1 + α} − \frac{x^{2}α}{−1 + α} − \frac{yα}{−1 + α} − \frac{2xyα}{−1 + α} − \frac{x^{2}yα}{−1 + α} − \frac{2y^{2}α}{−1 + α}+

\frac{ty^{2}α}{−1 + α} − \frac{xy^{2}α}{−1 + α} − \frac{y^{3}α}{−1 + α} + \frac{ty^{3}α}{−1 + α} − \frac{x^{2}α^{2}}{−1 + α} − \frac{x^{3}α^{2}}{−1 + α} − \frac{2xyα^{2}}{−1 + α} − \frac{2x^{2}yα^{2}}{−1 + α}−

\frac{x^{3}yα^{2}}{−1 + α} − \frac{3xy^{2}α^{2}}{−1 + α} − \frac{x^{2}y^{2}α^{2}}{−1 + α} − \frac{xy^{3}α^{2}}{−1 + α} − \frac{x^{2}yα^{3}}{−1 + α} − \frac{x^{2}y^{2}α^{3}}{−1 + α},

x^{3} + x^{4} + 2x^{2}y + 2x^{3}y + x^{4}y + 3x^{2}y^{2} + x^{3}y^{2} + x^{2}y^{+} \frac{y^{2}}{α^{3}} + \frac{y^{3}}{α^{3}} + \frac{xy}{α^{2}} + \frac{2xy^{2}}{α^{2}} +

\frac{xy^{3}}{α^{2}} + \frac{x^{2}}{α} + \frac{x^{3}}{α} + \frac{xy}{α} + \frac{3x^{2}y}{α} + \frac{x^{3}y}{α} + \frac{2xy^{2}}{α} + \frac{2x^{2}y^{2}}{α} + \frac{xy^{3}}{α} + x^{3}yα + x^{3}y^{2}α\}

より, Rf ∩ Rg = Rh′,

h′ = x^{4}y + (α + 1) x^{3}y^{2} + x^{2}y^{3} + x^{4} + \frac{(α + 1)^{2}}{α} x^{3}y + \frac{(3α + 2)}{α}x^{2}y^{2} + \frac{(α + 1)}{α^{2}}xy^{3}

+\frac{(α + 1)}{α}x^{3} + \frac{(2α + 3)}{α}x^{2}y + \frac{2 (α + 1)}{α^{2}}xy^{2} + \frac{y^{3}}{α^{3}} + \frac{x^{2}}{α} + \frac{(α + 1)}{α^{2}}xy + \frac{y^{2}}{α^{3}}

である. h = α^{2}h′ より, 前命題の構成方法から求めたものと, 左 Gröbner 基底アルゴリズムを用いて求めたものは定数倍 (α^{2} 倍 ) を除いて同じである.

今までに紹介した単項生成になる例はすべてこのタイプであった. そこで疑問になるのが, それ以外の単項生成になる例が見つけられないかということである. そこで次の例がどうやら Proposition3.16 の逆の反例になっているようである.

Example 3.18 f, g ∈ R を

\{ \begin{matrix}f = x^{2}y + x^{2} + \frac{(α + 1)}{α}xy + \frac{(α + 1)}{α}x + \frac{y}{α} + \frac{1}{α} \\ g = xy^{2} + \frac{(α + 1)}{α}xy + \frac{y^{2}}{α^{2}} + \frac{x}{α} + \frac{(α + 1)}{α^{2}}y + \frac{1}{α} \end{matrix}

と定める. 実はこの f, g は, R · (x + 1) ∩ R · (y + 1) の生成元であったが, Rf ∩ Rg の生成元を左 Gröbner 基底アルゴリズムを用いて計算すると, 単項生成になり, その生成元は,

h = x^{2}y^{2} + \frac{(α + 1)}{α}x^{2}y + \frac{(α + 1)}{α^{2}}xy^{2} + \frac{x^{2}}{α} + \frac{2 (α + 1)}{α^{2}}xy + \frac{y^{2}}{α^{3}} + \frac{(α + 1)}{α^{2}}

となる. 今, h をそれぞれ右から f と g で割ると,

h = (\frac{y}{α^{2}} + \frac{1}{α}) f = (x + \frac{1}{α}) g

となる. もし, この f と g が Proposition3.16 の仮定 ( f と g は入れ替えても良い ) を満たしているとするならば,

f = f′l_{1}, g = p^{∗}l_{1} (p^{∗} ∈ F_{y+1}, f′と p^{∗}の右共通因子は定数のみ) を満たす l_{1} ∈ R が存在する.(3.5)

もしくは,

f = q^{∗}l_{2}, g = g′l_{2} (q^{∗} ∈ F_{x+1}, q^{∗}と g′の右共通因子は定数のみ) を満たす l_{2} ∈ R が存在する.(3.6)

を満たしているはずである. ところが,

\{ \begin{matrix}r_{1} = αxy + x + y + 1 \\ r_{2} = αxy + αx + y + α \\ r_{3} = αxy + αx + y + 1 \end{matrix} r_{1}, r_{2}, r_{3} ∈ R

に対し,

\{ \begin{matrix}g = (\frac{y}{α^{2}} + \frac{1}{α}) r_{1}  \frac{y}{α^{2}} + \frac{1}{α} ∈ F_{y+1} \\ g = (\frac{y}{α^{2}} + \frac{1}{α^{2}} ) r_{2}  \frac{y}{α^{2}} + \frac{1}{α^{2}} ∈ F_{y+1} \\ f = (\frac{x}{α} + \frac{1}{α}) r_{3}  \frac{x}{α} + \frac{1}{α} ∈ F_{x+1} \end{matrix}  (3.7)

と表されるが, f を右から r_{1}, r_{2}, g を右から r_{3} で割ると.

\{ \begin{matrix}f = (\frac{x}{α} + \frac{1}{α}) r_{1} + \frac{(α − 1)}{α}x^{2} + \frac{(α − 1)}{α}x \\ f = (\frac{x}{α} + \frac{1}{α}) r_{2} − \frac{(α − 1)}{α}x − \frac{(α − 1)}{α} \\ g = (\frac{y}{α^{2}} + \frac{1}{α^{2}} ) r_{3} + \frac{(α − 1)}{α^{2}}y + \frac{(α − 1)}{α^{2}} \end{matrix}

となり, 割り切れない. ここで, g = p^{∗}r, f = q^{∗}r′ (p^{∗} ∈ F_{y+1}, q^{∗} ∈ F_{x+1} r, r′ ∈ R) と表せたときのそれぞれの因子は, (3.7) の因子の零でない定数倍のみであろう. よって, 同じく, f を右から r_{1}, r_{2} の零でない定数倍, g を右から r_{3} の零でない定数倍で割っても割り切れない. よって, (3.5) を満たす l_{1} と, (3.6) を満たす l_{2} は存在しないと思われる. 以上により, この例は, Proposition3.16 の仮定を満たしていないと思われるが, 単項生成になる.

さらに, Rf ∩ Rg が単項生成になるような f, g ∈ R に対し、次の 2 つの補題が成り立つ.

Lemma 3.19 f, g ∈ R に対し, Rf ∩ Rg が単項生成とする. その生成元を pg (p ∈ R) とすると任意の単項式 m ∈ R に対し,

Rf ∩ Rmg = Rp_{m′′}^{′∗}mg.

ただし, 単項式 m′ ∈ R を p, m の右最大共通因子とし, p = p′m′, m = m′ ∗ m′′ (p′, m′′ ∈ R, m′′ は単項式 ) とする.

(Proof) (⊃):

p_{m′′}^{′∗}mg = \frac{1}{sig(m′′, m′)}p_{m′′}^{′∗}m′′m′g = \frac{1}{sig(m′′, m′)}m′′p′m′g = \frac{1}{sig(m′′, m′)}m′′pg.

pg ∈ Rf でもあるので, p_{m′′}^{′∗}mg ∈ Rf ∩ Rmg. (⊂): q ∈ Rf ⋂ Rmg とすると, ある s, t ∈ R によって, q = sf = tmg と表せる. よって, t が右から p_{m′′}^{′∗} で割り切れることを示せばよい. 一方で, q ∈ Rf ∩ Rg でもあるので, ある r ∈ R によって, q = rpg と表せる. よって, rpg = tmg の両辺を右から g で割り, 式を整理することにより,

rp′ = \frac{1}{sig(m′′, m,)}tm′′

となる. さらに, 両辺の左から m′′ をかけて, 式を整理することにより,

r_{m′′}^{∗}p_{m′′}^{′∗} = \frac{1}{sig(m′′, m′)}m′′t

となる. よって, m′′t は右から p_{m′′}^{′∗} で割り切れて, さらに m′′ のとり方により, t は右から p_{m′′}^{′∗} で割り切れる. (証明終わり)

Lemma 3.20 f, g ∈ R に対し, Rf ∩ Rg が単項生成とする. その生成元を pg (p ∈ R) とすると任意の a ∈ R に対し,

Rf ∩ R · (af + g) = Rp(af + g).

(Proof) (⊃): p(af + g) = paf + pg で, pg ∈ Rf より, p(af + g) ∈ Rf ∩ Rp(af + g). (⊂): q ∈ Rf ∩ R · (af + g) とすると, ある s, t ∈ R によって, q = sf = t(af + g) と表せる. よって, t が右から p で割り切れることを示せばよい. sf = t(af + g) を整理して, (s − ta)f = tg となり, tg は右から f で割り切れる. よって, tg ∈ Rf となり, さらに, tg ∈ Rg より, tg ∈ Rpg となる. よって, t は右から p で割り切れる. (証明終わり)

この 2 つの補題をまとめることにより, 次の命題が導かれる.

Proposition 3.21 f, g ∈ R に対し, Rf ∩ Rg が単項生成とする. その生成元を pg (p ∈ R) とすると, 任意の a ∈ R, c ∈ k (α)^{×}, 任意の単項式 m ∈ R に対し,

Rf ∩ R · (af + cmg) = Rp_{m′′}^{′∗}(af + cmg).

ただし, 単項式 m′ ∈ R を p, m の右最大共通因子とし, p = p′m′, m = m′ ∗ m′′ (p′, m′′ ∈ R, m′′ は単項式 ) とする.

ここで疑問となるのが, 単項生成になるための必要十分条件は何かということである. さらに, 前に述べたが, 計算機実験の計算結果から, 左単項生成イデアルの共通部分の生成元は, 特に辞書式順序に関して, 高々2 元で生成されるのではないかという予想がたつ. またさらにその 2 つの元でそれぞれ単項生成される左イデアルの共通部分の生成元を計算したところ単項生成になったことから, この場合も単項生成になるのではないかという予想もたつ. 次節でこれらの問題と予想をまとめた. この節では最後に, 表での単項生成にならない例での, 辞書式順序に関しての 2 つの生成元を記載しておく.

Example 3.22 1. f = x + y, g = y + 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{2}y − \frac{y^{3}}{α^{3}} + x^{2} − \frac{(α + 1)}{α^{2}} xy − \frac{(α^{2} + α + 1)}{α^{3}} y^{2} − \frac{(α + 1)}{α^{2}} x − \frac{(α + 1)}{α^{2}} y, xy^{2} + \frac{y^{3}}{α^{2}} + \frac{(α + 1)}{α} xy + \frac{(α + 1)}{α^{2}} y^{2} + \frac{x}{α} + \frac{y}{α}\}

である.

2. f = x^{2} + 1, g = y^{2} + 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{4}y^{2} + x^{4} + \frac{(α^{4} + 1)}{α^{4}} x^{2}y^{2} + \frac{(α^{4} + 1)}{α^{4}} x^{2} + \frac{y^{2}}{α^{4}} + \frac{1}{α^{4}} , x^{2}y^{4} + \frac{y^{4}}{α^{8}} + \frac{(α^{4} + 1)}{α^{4}} x^{2}y^{2} + \frac{x^{2}}{α^{4}} + \frac{(α^{4} + 1)}{α^{8}} y^{2} + \frac{1}{α^{4}} \}

である.

3. f = x^{3} + y, g = y^{3} + 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{6}y^{3} + \frac{(α^{9} + 1)}{α^{9}} x^{3}y^{4} + x^{6} + \frac{y^{5}}{α^{12}} + \frac{(α^{9} + 1)}{α^{9}} x^{3}y + \frac{y^{2}}{α^{12}} , x^{3}y^{6} + \frac{y^{7}}{α^{18}} + \frac{(α^{9} + 1)}{α^{9}} x^{3}y^{3} + \frac{(α^{9} + 1)}{α^{18}} y^{4} + \frac{x^{3}}{α^{9}} + \frac{y}{α^{9}} \}

である.

4. f = x^{3} + 1, g = y^{3} + 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{6}y^{3} + x^{6} + \frac{(α^{9} + 1)}{α^{9}} x^{3}y^{3} + \frac{(α^{9} + 1)}{α^{9}} x^{3} + \frac{y^{3}}{α^{9}} + \frac{1}{α^{9}} , x^{3}y^{6} + \frac{(α^{9} + 1)}{α^{9}} x^{3}y^{3} + \frac{y^{6}}{α^{18}} + \frac{x^{3}}{α^{9}} + \frac{(α^{9} + 1)}{α^{18}} y^{3} + \frac{1}{α^{9}} \}

である.

5. f = x^{10}y^{8} − x^{5}y^{6}, g = x^{7}y^{3} − x^{2}y^{2} とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{15}y^{10} − α^{15}x^{15}y^{9} − \frac{x^{10}y^{9}}{α^{35}} + α^{10}x^{10}y^{7} + \frac{x^{5}y^{7}}{α^{40}} − \frac{x^{5}y^{6}}{α^{10}} , x^{20}y^{6} − \frac{x^{15}y^{9}}{α^{45}} − \frac{x^{15}y^{8}}{α^{25}} − \frac{x^{15}y^{7}}{α^{5}} + \frac{x^{10}y^{8}}{α^{75}} + \frac{x^{10}y^{7}}{α^{50}} + \frac{x^{10}y^{6}}{α^{25}} − \frac{x^{5}y^{6}}{α^{75}} \}

である.

6. f = xy + x + 1, g = x + y とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{3}y + \frac{(α^{4} + 3α^{3} + 3α^{2} + 2α + 1)}{α(2α^{2} + 2α + 1)} x^{2}y^{2} + \frac{(α^{2} + 3α + 1)}{α(2α^{2} + 2α + 1)} xy^{3} + x^{3} + \frac{(α^{3} + 3α^{2} + 4α + 2)}{2α^{2} + 2α + 1} x^{2}y + \frac{(α^{3} + α^{2} + 2α + 1)}{α(2α^{2} + 2α + 1)} xy^{2}

+ \frac{(2α^{3} + 3α^{2} + α − 1)}{α(2α^{2} + 2α + 1)} x^{2} + \frac{(2α^{4} + 3α^{3} + 2α^{2} + 2α + 1)}{α(2α^{2} + 2α + 1)} xy + \frac{(α^{2} + 3α + 1)}{α^{3} (2α^{2} + 2α + 1)} y^{2} + \frac{(α^{2} − 1)}{α(2α^{2} + 2α + 1)} x + \frac{(α^{2} − 1)}{α(2α^{2} + 2α + 1)} y,

x^{2}y^{3} + \frac{xy^{4}}{α^{3}} + \frac{(α + 1)}{α} x^{2}y^{2} + \frac{(α + 1)}{α^{3}} xy^{3} + \frac{(α^{2} − 1)}{α^{3}} x^{2}y + \frac{xy^{2}}{α^{2}} + \frac{y^{3}}{α^{6}} − \frac{x^{2}}{α^{3}} + \frac{y^{2}}{α^{4}} − \frac{x}{α^{3}} − \frac{y}{α^{3}} \}

である.

7. f = xy + x + 1, g = x + y + 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{3}y − \frac{xy^{3}}{α^{3}} + x^{3} − \frac{(α + 1)}{α^{3}} x^{2}y − \frac{(α^{3} + α^{2} + 2α + 1)}{α^{4}} xy^{2} + \frac{(α^{3} − α − 1)}{α^{3}} x^{2} − \frac{(α^{3} + 2α^{2} + 2α + 2)}{α^{4}} xy − \frac{y^{2}}{α^{5}} − \frac{(2α^{2} + 2α + 1)}{α^{4}} x

− \frac{(α^{3} + α^{2} + α + 1)}{α^{5}} y − \frac{(α^{2} + α + 1)}{α^{4}} ,

x^{2}y^{2} + \frac{xy^{3}}{α^{2}} + \frac{(α^{2} + α + 1)}{α^{2}} x^{2}y + \frac{(α + 1)^{2}}{α^{3}} xy^{2} + \frac{(α + 1)}{α^{2}} x^{2} + \frac{2(α^{2} + α + 1)}{α^{3}} xy + \frac{y^{2}}{α^{4}} + \frac{(α + 1)^{2}}{α^{3}} x + \frac{(α^{2} + α + 1)}{α^{4}} y + \frac{(α + 1)}{α^{3}}\}

である.

8. f = x + y + 1, g = xy + 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{3}y + \frac{(α^{4} + 3α^{3} + 2α^{2} + 2α + 1)}{α(α^{2} + 2α + 2)} x^{2}y^{2} + \frac{(α^{2} + 3α + 1)}{α(α^{2} + 2α + 2)} xy^{3} + \frac{(α^{3} + 2α^{2} + 4α + 3)}{α(α^{2} + 2α + 2)} x^{2}y + \frac{(2α^{3} + 4α^{2} + 3α + 1)}{α^{2} (α^{2} + 2α + 2)} xy^{2} + x^{2}

+ \frac{(α^{4} + 3α^{3} + 4α^{2} + 5α + 2)}{α^{2} (α^{2} + 2α + 2)} xy + \frac{(α^{2} + 3α + 1)}{α^{3} (α^{2} + 2α + 2)} y^{2} + \frac{(2α^{3} + 4α^{2} + 3α + 1)}{α^{3} (α^{2} + 2α + 2)} y + \frac{(2α + 3)}{α(α^{2} + 2α + 2)} ,

x^{2}y^{3} + \frac{xy^{4}}{α^{3}} + \frac{x^{2}y^{2}}{α^{2}} + \frac{(α + 1)}{α^{4}} xy^{3} − \frac{x^{2}y}{α^{3}} + \frac{xy^{2}}{α^{4}} + \frac{y^{3}}{α^{6}} + \frac{(α + 1)}{α^{6}} y^{2} − \frac{x}{α^{3}} − \frac{(α^{2} − 1)}{α^{5}} y − \frac{1}{α^{3}} \}

である.

9. f = x^{2} + x + y + 1, g = y + 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{3}y + x^{3} + \frac{(α + 1)}{α} x^{2}y + \frac{xy^{2}}{α^{2}} + \frac{(α + 1)}{α} x^{2} + \frac{(α^{2} + α + 1)}{α^{2}} xy + \frac{y^{2}}{α^{2}} + \frac{(α + 1)}{α^{2}} x + \frac{(α + 1)}{α^{2}} y + \frac{1}{α} ,

x^{2}y^{2} + \frac{(α + 1)}{α} x^{2}y + \frac{xy^{2}}{α^{2}} + \frac{y^{3}}{α^{4}} + \frac{x^{2}}{α} + \frac{(α + 1)}{α^{2}} xy + \frac{(α^{2} + α + 1)}{α^{4}} y^{2} + \frac{x}{α} + \frac{(α^{2} + α + 1)}{α^{3}} y + \frac{1}{α}\}

である.

10. f = x + y^{2} + 1, g = x^{2} + 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{α^{2}x^{2}y^{4} + (α^{4} + 1) x^{3}y^{2} + x^{4} + \frac{(α^{4} + 1)}{α^{2}} x^{2}y^{2} + \frac{y^{4}}{α^{6}} + \frac{(α^{2} + 1)}{α^{2}} x^{3} + \frac{(α^{4} + 1)}{α^{4}} xy^{2} + \frac{(α^{2} + 1)}{α^{2}} x^{2} + \frac{(α^{4} + 1)}{α^{6}} y^{2} + \frac{(α^{2} + 1)}{α^{2}} x + \frac{1}{α^{2}} ,

\frac{x^{2}y^{6}}{α^{4}} + x^{3}y^{4} + \frac{(α^{4} + α^{2} + 1)}{α^{8}} x^{2}y^{4} + \frac{y^{6}}{α^{16}} + \frac{(α^{2} + 1)}{α^{6}} x^{3}y^{2} + \frac{xy^{4}}{α^{8}} + \frac{(2α^{4} + α^{2} + 1)}{α^{10}} x^{2}y^{2} + \frac{(α^{4} + α^{2} + 1)}{α^{16}} y^{4} + \frac{2x^{3}}{α^{10}} + \frac{(α^{2} + 1)}{α^{10}} xy^{2}

+ \frac{2x^{2}}{α^{10}} + \frac{(2α^{4} + α^{2} + 1)}{α^{14}} y^{2} + \frac{2x}{α^{10}} + \frac{2}{α^{10}} \}

である.

11. f = x^{2} + y^{2}, g = x + 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{4} + x^{2}y^{2} + \frac{(α^{2} + 1)}{α^{2}} x^{3} + \frac{(α^{2} + 1)}{α^{2}} xy^{2} + \frac{x^{2}}{α^{2}} + \frac{y^{2}}{α^{2}} , x^{3}y^{2} + \frac{xy^{4}}{α^{4}} + \frac{x^{2}y^{2}}{α^{4}} + \frac{y^{4}}{α^{8}} + \frac{x^{3}}{α^{6}} + \frac{xy^{2}}{α^{6}} + \frac{x^{2}}{α^{6}} + \frac{y^{2}}{α^{6}} \}

である.

12. f = x^{2} − y^{2} − 1, g = x − y とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{4} − (α^{2} + 1) x^{3}y + (α − 1) x^{2}y^{2} + \frac{(α^{2} + 1)}{α^{2}} xy^{3} − \frac{y^{4}}{α^{3}} − x^{2} + \frac{(α^{2} + 1)}{α^{2}} xy − \frac{y^{2}}{α^{3}} ,

x^{3}y^{2} − \frac{x^{2}y^{3}}{α^{2}} − \frac{xy^{4}}{α^{4}} + \frac{y^{5}}{α^{8}} + \frac{x^{3}}{α^{5} (α − 1)} − \frac{x^{2}y}{α^{3} (α − 1)} − \frac{(α^{2} − α + 1)}{α^{5} (α − 1)} xy^{2} + \frac{(α^{3} + α − 1)}{α^{8} (α − 1)} y^{3} + \frac{x}{α^{5} (α − 1)} + \frac{y}{α^{5} (α − 1)}\}

である.

13. f = x^{2} − y^{2} − 1, g = x − y + 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{4} − \frac{(α + 1)}{α} x^{2}y^{2} + \frac{y^{4}}{α^{5}} + \frac{(α^{3} + α^{2} + α + 1)}{α^{3} (α − 1)} x^{3} − \frac{(2α^{3} + α^{2} + 1)}{α^{3} (α − 1)} x^{2}y − \frac{(α^{3} + α^{2} + α + 1)}{α^{3} (α − 1)} xy^{2} + \frac{(2α^{3} + α^{2} + 1)}{α^{5} (α − 1)} y^{3}

− \frac{(α^{5} − α^{4} − 2α^{2} − α − 1)}{α^{4} (α − 1)} x^{2} − \frac{(2α^{3} + α^{2} + 1)}{α^{5} (α − 1)} y^{2} − \frac{(α^{3} + α^{2} + α + 1)}{α^{3} (α − 1)} x + \frac{(2α^{3} + α^{2} + 1)}{α^{5} (α − 1)} y − \frac{(2α^{2} + α + 1)}{α^{4} (α − 1)} ,

x^{3}y − \frac{x^{2}y^{2}}{α} + \frac{y^{4}}{α^{5}} − \frac{xy^{3}}{α^{2}} + \frac{(α + 1)}{α^{3} (α − 1)} x^{3} − \frac{(α^{2} + 1)}{α^{3} (α − 1)} x^{2}y − \frac{(α + 1)}{α^{3} (α − 1)} xy^{2} + \frac{(α^{2} + 1)}{α^{5} (α − 1)} y^{3} + \frac{(α + 1)}{α^{4} (α − 1)} x^{2} − \frac{xy}{α^{2}}

− \frac{(α^{2} + 1)}{α^{5} (α − 1)} y^{2} − \frac{(α + 1)}{α^{3} (α − 1)} x + \frac{(α^{2} + 1)}{α^{5} (α − 1)} y − \frac{(α + 1)}{α^{4} (α − 1)}\}

である.

14. f = x^{4} − xy, g = y − 1 とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{7}y − x^{7} − \frac{(α^{3} + 1)}{α^{6}} x^{4}y + \frac{(α^{3} + 1)}{α^{6}} x^{4} − \frac{xy^{3}}{α^{9}} + \frac{(α^{6} + α^{3} + 1)}{α^{9}} xy^{2} − \frac{(α^{3} + 1)}{α^{6}} xy, x^{4}y^{2} − \frac{(α^{3} + 1)}{α^{3}} x^{4}y + \frac{x^{4}}{α^{3}} − \frac{xy^{3}}{α^{6}} + \frac{(α^{3} + 1)}{α^{6}} xy^{2} − \frac{xy}{α^{3}} \}

である.

15. f = x^{2}y − xy, g = xy^{2} − xy とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{3}y^{2} − x^{3}y − \frac{(α + 1)}{α} x^{2}y^{2} + \frac{(α + 1)}{α} x^{2}y + \frac{xy^{2}}{α} − \frac{xy}{α} , x^{2}y^{3} − \frac{(α + 1)}{α} x^{2}y^{2} − \frac{xy^{3}}{α^{2}} + \frac{x^{2}y}{α} + \frac{(α + 1)}{α^{2}} xy^{2} − \frac{xy}{α} \}

である.

16. f = x^{2}y − xy − x, g = xy^{2} − xy + y とする. Rf ∩ Rg の辞書式順序に関する Gröbner 基底は

\{x^{4}y^{3} − \frac{α (2α + 3)}{α^{2} + 2α + 2} x^{3}y^{4} − x^{4}y^{2} + \frac{(α^{4} − 4α^{2} − 5α − 2)}{α^{2} (α^{2} + 2α + 2)} x^{3}y^{3} + \frac{(2α + 3)}{α^{2} (α^{2} + 2α + 2)} x^{2}y^{4} + \frac{(α^{4} + 3α^{3} + 4α^{2} + 5α + 2)}{α^{2} (α^{2} + 2α + 2)} x^{3}y^{2}

− \frac{(α^{3} − 3α − 3)}{α^{3} (α^{2} + 2α + 2)} x^{2}y^{3} + \frac{x^{3}y}{α} − \frac{(α^{4} + 4α^{3} + 8α^{2} + 6α + 1)}{α^{3} (α^{2} + 2α + 2)} x^{2}y^{2} + \frac{(2α + 3)}{α^{4} (α^{2} + 2α + 2)} xy^{3} − \frac{(α^{4} + 2α^{3} + 3α^{2} + 5α + 4)}{α^{3} (α^{2} + 2α + 2)} x^{2}y

+ \frac{(α^{3} + 5α^{2} + 6α + 3)}{α^{4} (α^{2} + 2α + 2)} xy^{2} + \frac{(α^{2} + 5α + 4)}{α^{3} (α^{2} + 2α + 2)} xy,

x^{3}y^{5} − \frac{(α^{2} − 1)}{α^{2}} x^{3}y^{4} − \frac{x^{2}y^{5}}{α^{4}} − \frac{(α + 1)}{α^{3}} x^{3}y^{3} + \frac{(α^{2} − 1)}{α^{5}} x^{2}y^{4} + \frac{x^{3}y^{2}}{α^{3}} + \frac{(α + 2)}{α^{4}} x^{2}y^{3} − \frac{xy^{4}}{α^{7}} − \frac{(α^{2} − 1)}{α^{5}} x^{2}y^{2} − \frac{(α + 1)}{α^{7}} xy^{3} − \frac{x^{2}y}{α^{4}}

+ \frac{(α^{2} − 1)}{α^{6}} xy^{2} + \frac{xy}{α^{4}} \}

である.

17. f = x^{4} − xy, g = x + y^{3} とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{α^{5}x^{4}y^{6} + (α^{8} + 1) x^{5}y^{3} − \frac{xy^{7}}{α^{13}} + x^{6} − \frac{(α^{8} + 1)}{α^{9}} x^{2}y^{4} − x^{3}y, \frac{x^{4}y^{11}}{α^{8}} + x^{5}y^{8} − \frac{xy^{12}}{α^{41}} − \frac{x^{2}y^{9}}{α^{24}} + \frac{x^{4}y^{3}}{α^{15}} + \frac{x^{5}}{α^{23}} − \frac{xy^{4}}{α^{24}} − \frac{x^{2}y}{α^{23}} \}

である.

18. f = x^{2} + y, g = y^{2} + x とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{αx^{2}y^{4} + (α + 1) x^{3}y^{2} + \frac{y^{5}}{α^{7}} + x^{4} + \frac{(α^{3} + 1)}{α^{4}} xy^{3} + x^{2}y, \frac{x^{2}y^{5}}{α^{3}} + x^{3}y^{3} + \frac{y^{6}}{α^{13}} + \frac{xy^{4}}{α^{6}} + \frac{x^{2}y^{2}}{α^{4}} + \frac{x^{3}}{α^{7}} + \frac{y^{3}}{α^{8}} + \frac{xy}{α^{7}} \}

である.

19. f = x^{3} + y, g = y^{3} + x とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{α^{5}x^{3}y^{6} + (α^{8} + 1) x^{4}y^{3} + \frac{y^{7}}{α^{13}} + x^{5} + \frac{(α^{8} + 1)}{α^{9}} xy^{4} + x^{2}y, \frac{x^{3}y^{11}}{α^{8}} + x^{4}y^{8} + \frac{y^{12}}{α^{41}} + \frac{xy^{9}}{α^{24}} − \frac{x^{3}y^{3}}{α^{15}} − \frac{x^{4}}{α^{23}} − \frac{y^{4}}{α^{24}} − \frac{xy}{α^{23}} \}

である.

20. f = x^{3} + y^{2}, g = y^{3} + x^{2} とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{α^{3}x^{3}y^{7} + α^{11}x^{5}y^{4} + \frac{y^{9}}{α^{18}} + \frac{x^{2}y^{6}}{α} + α^{5}x^{4}y^{3} + x^{6} + \frac{xy^{5}}{α^{4}} + x^{3}y^{2},

\frac{x^{3}y^{8}}{α^{10}} + x^{5}y^{5} + \frac{y^{10}}{α^{34}} + \frac{x^{2}y^{7}}{α^{15}} + \frac{(α^{5} − 1)}{α^{12}} x^{4}y^{4} + \frac{(α^{5} − 1)}{α^{24}} xy^{6} + \frac{x^{3}y^{3}}{α^{13}} + \frac{x^{5}}{α^{18}} + \frac{y^{5}}{α^{22}} + \frac{x^{2}y^{2}}{α^{18}} \}

である.

21. f = x^{3}y + y^{2}, g = xy^{3} + x^{2} とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{α^{3}x^{4}y^{7} + \frac{(α^{8} + 1)}{α} x^{5}y^{4} + \frac{xy^{8}}{α^{15}} + x^{6}y + \frac{(α^{8} + 1)}{α^{10}} x^{2}y^{5} + x^{3}y^{2}, \frac{x^{4}y^{12}}{α^{9}} + x^{5}y^{9} + \frac{xy^{13}}{α^{42}} + \frac{x^{2}y^{10}}{α^{24}} − \frac{x^{4}y^{4}}{α^{13}} − \frac{x^{5}y}{α^{20}} − \frac{xy^{5}}{α^{22}} − \frac{x^{2}y^{2}}{α^{20}} \}

である.

22. f = x^{3}y + xy^{2}, g = xy^{3} + x^{2} とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{x^{3}y^{7} + \frac{xy^{8}}{α^{12}} + \frac{(α^{5} + 1)}{α} x^{4}y^{4} + \frac{(α^{5} + 1)}{α^{7}} x^{2}y^{5} + x^{5}y + x^{3}y^{2}, \frac{x^{3}y^{9}}{α^{6}} + \frac{xy^{10}}{α^{22}} + x^{4}y^{6} + \frac{x^{2}y^{7}}{α^{10}} + \frac{x^{3}y^{4}}{α^{6}} + \frac{xy^{5}}{α^{12}} + \frac{x^{4}y}{α^{10}} + \frac{x^{2}y^{2}}{α^{10}} \}

である.

23. f = x^{5}y + x^{3}y^{2}, g = xy^{3} + x^{2}y とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{αx^{5}y^{5} + (α^{3} + 1) x^{6}y^{3} + \frac{x^{3}y^{6}}{α^{7}} + x^{7}y + \frac{(α^{3} + 1)}{α^{4}} x^{4}y^{4} + x^{5}y^{2}, \frac{x^{5}y^{6}}{α^{3}} + x^{6}y^{4} + \frac{x^{3}y^{7}}{α^{13}} + \frac{x^{4}y^{5}}{α^{6}} + \frac{x^{5}y^{3}}{α^{4}} + \frac{x^{6}y}{α^{7}} + \frac{x^{3}y^{4}}{α^{8}} + \frac{x^{4}y^{2}}{α^{7}} \}

である.

24. f = x^{5}y^{10} + x^{3}y^{7}, g = x^{10}y^{3} + x^{2}y^{8} とする. Rf ∩ Rg の辞書式順序に関する Gröbner 基底は

\{−α^{44}x^{13}y^{24} − \frac{x^{5}y^{29}}{α^{124}} − \frac{x^{11}y^{21}}{α^{18}} − \frac{x^{3}y^{26}}{α^{162}} + x^{15}y^{10} + \frac{x^{7}y^{15}}{α^{56}} + x^{13}y^{7} + \frac{x^{5}y^{12}}{α^{32}} ,

x^{13}y^{27} + \frac{x^{5}y^{32}}{α^{192}} + \frac{x^{11}y^{24}}{α^{68}} + \frac{x^{3}y^{29}}{α^{236}} + \frac{x^{13}y^{10}}{α^{78}} + \frac{x^{5}y^{15}}{α^{134}} + \frac{x^{11}y^{7}}{α^{78}} + \frac{x^{3}y^{12}}{α^{110}} \}

である.

25. f = x^{165}y^{30} −xy, g = x^{15}y^{46} −x^{21}y^{6} とする. Rf ∩Rg の総次数逆辞書式順序に関する左 Gröbner

基底は

\{x^{179}y^{155} − \frac{(α^{6734} + 1)}{α^{6320}} x^{185}y^{75} + \frac{x^{191}y^{35}}{α^{6146}} − \frac{x^{15}y^{86}}{α^{13940}} + \frac{(α^{6734} + 1)}{α^{13700}} x^{21}y^{46} − \frac{x^{27}y^{6}}{α^{6966}} ,

x^{343}y^{104} − α^{348}x^{349}y^{64} − \frac{(α^{6734} + 1)}{α^{12136}} x^{179}y^{75} + \frac{(α^{6734} + 1)}{α^{11962}} x^{185}y^{35} + \frac{x^{15}y^{46}}{α^{12782}} − \frac{x^{21}y^{6}}{α^{12782}} ,

x^{349}y^{75} − α^{174}x^{355}y^{35} − \frac{x^{179}y^{86}}{α^{886}} + \frac{x^{191}y^{6}}{α^{646}} + \frac{x^{15}y^{57}}{α^{10070}} − \frac{x^{21}y^{17}}{α^{10004}} \}

である. この例での辞書式順序に関する左 Gröbner 基底は, 容量超過のため計算が完了しなかった. しかし, この例でも辞書式順序に関しては 2 元で生成されるのではないかと予想している.

26. f = x^{3}y^{2} + xy^{5}, g = x^{2}y + x^{6}y^{2} とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{α^{4}x^{6}y^{9} + \frac{(α^{14} + 1)}{α^{2}} x^{8}y^{6} + x^{10}y^{3} + \frac{x^{2}y^{8}}{α^{24}} + \frac{(α^{14} + 1)}{α^{18}} x^{4}y^{5} + \frac{x^{6}y^{2}}{α^{4}} , \frac{x^{6}y^{13}}{α^{16}} + x^{8}y^{10} + \frac{x^{2}y^{12}}{α^{60}} + \frac{x^{4}y^{9}}{α^{32}} + \frac{x^{6}y^{6}}{α^{24}} + \frac{x^{8}y^{3}}{α^{36}} + \frac{x^{2}y^{5}}{α^{40}} + \frac{x^{4}y^{2}}{α^{40}} \}

である.

27. f = x^{3}y^{6} + xy^{10}, g = x^{2}y + x^{10}y^{2} とする. Rf ∩ Rg の辞書式順序に関する Gröbner 基底は

\{α^{22}x^{10}y^{15} + \frac{(α^{34} + 1)}{α^{2}} x^{12}y^{11} + x^{14}y^{7} + \frac{x^{2}y^{14}}{α^{82}} + \frac{(α^{34} + 1)}{α^{74}} x^{4}y^{10} + \frac{x^{6}y^{6}}{α^{40}} ,

\frac{x^{10}y^{28}}{α^{36}} + x^{12}y^{24} + \frac{x^{2}y^{27}}{α^{244}} + \frac{x^{4}y^{23}}{α^{176}} + \frac{x^{10}y^{11}}{α^{122}} + \frac{x^{12}y^{7}}{α^{154}} + \frac{x^{2}y^{10}}{α^{194}} + \frac{x^{4}y^{6}}{α^{194}} \}

である.

28. f = x^{4} − y, g = x + y^{3} とする. Rf ∩ Rg の辞書式順序に関する左 Gröbner 基底は

\{α^{8}x^{4}y^{6} + (α^{11} + 1) x^{5}y^{3} − \frac{y^{7}}{α^{16}} + x^{6} − \frac{(α^{11} + 1)}{α^{12}} xy^{4} − x^{2}y, \frac{x^{4}y^{14}}{α^{11}} + x^{5}y^{11} − \frac{y^{15}}{α^{67}} − \frac{xy^{12}}{α^{44}} − \frac{x^{4}y^{3}}{α^{26}} − \frac{x^{5}}{α^{37}} + \frac{y^{4}}{α^{38}} + \frac{xy}{α^{37}} \}

である.

3.2 問題と予想

まず, R の左単項生成イデアルの共通部分が単項生成になるための必要十分条件は何かという問題を提起する.

Problem 3.23 R = k (α) ⟨x, y⟩ / (yx − αxy) , f, g ∈ R とする. このとき, Rf ∩ Rg が単項生成になるための必要十分条件は何か ?

この問題について, Proposition 3.16, Proposition 3.21 に関連して, 高橋宣能氏は次の予想を提起している.

Conjecture 3.24 (Takahashi’s Conjecture) f, g ∈ k [x, y] を k (α) ⟨x, y⟩ / (yx − αxy) の元とみる. f, g が可換の意味で gcd(f, g) = 1 を満たし, さらに, Rf ∩ Rg が単項生成で, その生成元 h ∈ R が

lim_{α→1} h = f ∗ g

を満たすとすると, f = g = 0 は可換の意味で xy = 0 となるような解のみを持つ.

最後に R の左単項生成イデアルの共通部分は高々2 元で生成されるのではないかという予想と, その 2 元でそれぞれ単項生成される左イデアルの共通部分は単項生成されるのではないかという予想を述べておく.

Conjecture 3.25 R = k (α) ⟨x, y⟩ / (yx − αxy) , f, g ∈ R とする. このとき, Rf ∩ Rg は,( 辞書式順序 x > y に関して ) 高々2 元の左簡約 Gröbner 基底で生成される.

この予想は Example 3.22 の例に関しては成り立っている.

Conjecture 3.26 R = k (α) ⟨x, y⟩ / (yx − αxy) , Rf ∩ Rg(f, g ∈ R) は辞書式順序 x > y に関して左簡約 Gröbner 基底 {h_{1}, h_{2}} (h_{1}, h_{2} ∈ R) を持つとき, Rh_{1} ∩ Rh_{2} は単項生成である.

この予想も Example 3.22 の例に関しては成り立っている.

付録A 左除法定理プログラム

以下は, 数式処理ソフト Mathematica で左除法を実行するプログラムである.

In[1]:=
NCPolyDiv[polynomial_, generator_, monoorder_, valueorder_] :=
Module[{LT2, ListPoly, PolyList, Polymono2, sig, PolyDiv2, popo},

(* 単項式順序を辞書式順序に設定する関数 *)

If[monoorder == lex,
LT2[f_] :=LT2[f] =
Module[{s, lt, a},
s = Length[f];
lt = f[[1]];
Do[If[DeleteCases[lt[[2]] - f[[a]][[2]], 0][[1]] < 0,
   lt = f[[a]]], {a,2,s}];
lt]];

(* 単項式順序を総次数辞書式順序に設定する関数 *)

If[monoorder == grlex,
LT2[f_] :=LT2[f] =
Module[{s, lt, t, sum1, sum2, a},
s = Length[f];
lt = f[[1]];
t = Length[lt[[2]]];
Do[sum1 = Sum[lt[[2]][[i]], {i, t}];
  sum2 = Sum[f[[a]][[2]][[i]], {i, t}];
  If[sum1 < sum2,
    lt = f[[a]],
    If[sum1 == sum2,
      If[DeleteCases[lt[[2]] - f[[a]][[2]], 0][[1]] < 0,
        lt = f[[a]]]]], {a, 2, s}];
lt]];

(* 単項式順序を総次数逆辞書式順序に設定する関数 *)

If[monoorder == grevlex,
LT2[f_] :=LT2[f] =
Module[{s, lt, t, sum1, sum2, a},
s = Length[f];
lt = f[[1]];
t = Length[lt[[2]]];
Do[sum1 = Sum[lt[[2]][[i]], {i, t}];
  sum2 = Sum[f[[a]][[2]][[i]], {i, t}];
  If[sum1 < sum2,
    lt = f[[a]],
      If[sum1 == sum2,
        If[DeleteCases[lt[[2]] - f[[a]][[2]], 0][[-1]] > 0,
          lt = f[[a]]]]], {a, 2, s}];
lt]];

(* 単項式順序を行列表示で設定する関数 *)

If[monoorder =!= lex && monoorder =!= grlex && monoorder =!= grevlex,
LT2[f_] :=LT2[f] =
Module[{s, lt, t, c, j},
s = Length[f];
lt = f[[1]];
t = Length[monoorder];
Do[c = False;
  j = 1;
  While[c == False,
    If[monoorder[[j]].lt[[2]] =!= monoorder[[j]].f[[i]][[2]],
      c = True;
      If[monoorder[[j]].lt[[2]] < monoorder[[j]].f[[i]][[2]],
        lt = f[[i]]]];
        j = j + 1], {i, 2, s}];
lt]];

(* 入力された多項式の組をリスト表示に変換する関数 *)

 PolyList[F_, val_] :=
Module[{s, PolyListone},
PolyListone[f_, v_] :=PolyListone[f, v] =
Module[{getcoeff, MonomialList, aa, bb, kkk, tta, cce, ii, dc},
getcoeff[m_, b_] := getcoeff[m, b] =
  Module[{a, c},
    If[Variables[m] =!= {},
      a = Exponent[m, b];
      c = Times @@ (b^a);
      If[c =!= 1,
        {Coefficient[m, Times @@ (b^a)], a},
        {m, a}],
      {m,Table[0, {Length[b]}]}]];
MonomialList[aiueo_] :=
  Module[{sasisuseso, full},
    kakikukeko = Expand[aiueo] + sasisuseso;
    full = FullForm[kakikukeko];
    DeleteCases[Table[full[[1]][[iii]], {iii, 1, Length[full[[1]]]}],
      sasisuseso]];
aa = MonomialList[f];
bb = Length[aa];
tta = Table[getcoeff[aa[[i]], v], {i, 1, bb}];
cce = True;
Do[ii = j + 1;
  cce = True;
  While[cce,
    If[tta[[j]][[2]] == tta[[ii]][[2]],
      cce = False;
      tta = ReplacePart[tta, {tta[[ii]][[1]] + tta[[j]][[1]], tta[[ii][[2]]},ii];
      tta = ReplacePart[tta, True, j]];
    If[ii == Length[tta],
      cce = False,
      ii = ii + 1]], {j, 1, Length[tta] - 1}];
dc = DeleteCases[tta, True];
Table[{Expand[Simplify[dc[[iii]][[1]]]], dc[[iii]][[2]]},
  {iii, 1, Length[dc]}]];
s = Length[F];
Table[PolyListone[F[[i]], val], {i, s}]];

(* リスト表示の多項式の組を多項式に変換する関数 *)

 ListPoly[F_, val_] :=ListPoly[F, val] =
Module[{ListPolyone, s, FF},
ListPolyone[f_, v_] :=ListPolyone[f, v] =
Module[{s, ss},
s = Length[f];
ss = Length[v];
Sum[f[[i]][[1]]*Product[v[[j]]^(f[[i]][[2]][[j]]), {j, 1, ss}], {i, 1, s}]];
s = Length[F];
FF = {};
Do[FF = Append[FF, ListPolyone[F[[i]], val]], {i, s}];
FF];

(* リスト表示の多項式にリスト表示の項を加える関数 *)

 Polymono2[f_, m_] :=Polymono2[f, m] =
Module[{ff, fgfg, s, c, a},
ff = f;
s = Length[ff];
If[s == 0,
ff = {m},
c = True;
a = 1;
While[c,
If[DeleteCases[m[[2]] - ff[[a]][[2]], 0] == {},
  fgfg = Expand[Simplify[Together[ff[[a]][[1]] + m[[1]]]]];
  ff = ReplacePart[ff, {fgfg, m[[2]]}, a];
  If[ff[[a]][[1]] == 0,
    ff = Delete[ff, a]];
  c = False,
  a = a + 1];
If[a == s + 1,
  ff = Append[ff, m];
  c = False]]];

ff];

(* リスト表示の 2 つの項をかけたときの sig を計算する関数 *)

 sig[le_, ri_] :=
Module[{s},
s = Length[le] - 1;
α^(Sum[Sum[le[[b]], {b, a + 1, s}]*ri[[a]], {a, 1, s - 1}])];

(* リスト表示の多項式において左除法定理を計算する関数 *)

 PolyDiv2[f_, g_] :=PolyDiv2[f, g] =
Module[{s, a, r, p, i, c, h1, h2},
s = Length[g];
a = {};
Do[a = Append[a, {}], {s}];
r = {};
p = f;
While[p =!= {},
  i = 1;
  c = True;
  While[i <= s && c,
    h1 = LT2[p][[2]] - LT2[g[[i]]][[2]];
    If[Select[h1, #1 < 0 &] == {},
      h2 = LT2[p][[1]]/(sig[h1, LT2[g[[i]]][[2]]]*LT2[g[[i]]][[1]]);
      a = ReplacePart[a, Polymono2[a[[i]], {h2, h1}], i];
      gg = g[[i]];
      While[gg =!= {},
         p = Polymono2[p,
           {-sig[h1, LT2[gg][[2]]]*h2*LT2[gg][[1]],h1 + LT2[gg][[2]]}];
         gg = Polymono2[gg, {-LT2[gg][[1]], LT2[gg][[2]]}]];
      c = False,
      i = i + 1]];
  If[c,
    r = Polymono2[r, LT2[p]];
    p = Polymono2[p, {-LT2[p][[1]], LT2[p][[2]]}]]];
{a, r}];

(* 実際に計算 *)

popo = PolyDiv2[PolyList[{polynomial}, valueorder][[1]],
PolyList[generator, valueorder]];
Expand[Simplify[{ListPoly[popo[[1]], valueorder],
ListPoly[{popo[[2]]}, valueorder][[1]]}]]]

プログラムの説明： f, f_{1}, ⋯, f_{s} ∈ R′, x_{1} > ⋯ > x_{n} を満たす単項式順序 (monomialorder) > に対し,

          NCPolyDiv[ f, { f_{1}, · · · , f_{s} }, monomialorder, { x_{1}, · · · , x_{n}, t } ]

と入力すると, 左除法定理 f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r における商多項式と剰余多項式の組

{{ a_{1}, ⋯, a_{っ s}}, r }

を出力する. ただし monomialorder には, 単項式順序を加重行列表示したものを入力する. 単項式順序が辞書式順序, 総次数辞書式順序, 総次数逆辞書式順序の場合には, それぞれ, lex, grlex, grevlex と入力してもよい. また, 変数のリストの部分に余分な変数 t があるのは, R′ に可換な変数 t を付加した環でこのプログラムを使用するために予め最後の変数は可換になるように組んだためである. よって, ここでは最後の変数 x_{n} が可換にならないように, ダミー変数 t を付加しておく.

付録B 左簡約Gröbner基底プログラム

以下は, 数式処理ソフト Mathematica で左簡約 Gröbner 基底を計算するプログラムである. ただし, プログラム内の関数で, NCPolyDiv で用いたものについては省略してある.

In[6]:=
NCGroebner[generator_, monoorder_, valueorder_] :=
Module[{LT2, ListPoly, PolyList, Polymono2, sig, PolyDiv2, S2, Groeb3,
MinGroeb,RedGroeb},

「まずここで単項式順序を指定する. プログラムについては NCPolyDiv 内の初めの４つの If 文を参照のこと」 ;

(* 入力された多項式の組をリスト表示に変換する関数 *)

 PolyList[F_, val_] := 「省略: NCPolyDiv 内の PolyList を参照のこと」 ;

(* リスト表示の多項式の組を多項式に変換する関数 *)

 ListPoly[F_, val_] := 「省略: NCPolyDiv 内の ListPoly を参照のこと」 ;

(* リスト表示の多項式にリスト表示の項を加える関数 *)

 Polymono2[f_, m_] := 「省略: NCPolyDiv 内の Polymono2 を参照のこと」 ;

(* 2 つのリスト表示の項をかけたときの sig を計算する関数 *)

 sig[le_, ri_] := 「省略: NCPolyDiv 内の sig を参照のこと」 ;

(* リスト表示の多項式において左除法定理を計算する関数 *)

 PolyDiv2[f_, g_] := 「省略: NCPolyDiv 内の PolyDiv2 を参照のこと」 ;

(* リスト表示の多項式の左 S 多項式を計算する関数 *)

S2[f_, g_] := S2[f, g] =
Module[{mf, mg, s, c, a, b, si1, si2, sisi, z, aa, ff, gg},
mf = LT2[f][[2]];
mg = LT2[g][[2]];
s = Length[mf];
c = {};
Do[c = Append[c, Max[{mf[[i]], mg[[i]]}]], {i, 1, s}];
a = {1/(LT2[f][[1]]), c - mf};
b = {1/(LT2[g][[1]]), c - mg};
si1 = sig[a[[2]], LT2[f][[2]]];
si2 = sig[b[[2]], LT2[g][[2]]];
sisi = si2/si1;
z = {};
aa = {};
ff = f;
While[ff =!= z,
  aa = Polymono2[aa,
    {sisi*sig[a[[2]], LT2[ff][[2]]]*a[[1]]*LT2[ff][[1]],
    a[[2]] + LT2[ff][[2]]}];
  ff = Polymono2[ff,
    {-LT2[ff][[1]], LT2[ff][[2]]}]];
gg = g;
While[gg =!= z,
  aa = Polymono2[aa,
    {-sig[b[[2]], LT2[gg][[2]]]*b[[1]]*LT2[gg][[1]],
    b[[2]] + LT2[gg][[2]]}];
  gg = Polymono2[gg, {-LT2[gg][[1]], LT2[gg][[2]]}]];
aa];

(* リスト表示の多項式の組の左 Groebner 基底を計算する関数 *)

 Groeb3[F_] :=Groeb3[F] =
Module[{s, B, G, t, ss, k, S},
s = Length[F];
B = {};
Do[Do[B = Append[B, {i, j}], {j, i + 1, s}], {i, 1, s - 1}];
G = F;
t = s;
ss = Length[F[[1]][[1]][[2]]];
While[B =!= {},
  k = B[[1]];

  S = PolyDiv2[S2[G[[k[[1]]]], G[[k[[2]]]]], G][[2]];
  If[S =!= {},
    t = t + 1;
    G = Append[G, S];
    Do[B = Append[B, {tt, t}], {tt, 1, t - 1}]];
  B = Delete[B, 1]];
G];

(* リスト表示の左 Groebner 基底を極小化する関数 *)

 MinGroeb[F_] :=MinGroeb[F] =
Module[{G, s, a, h, ss, t, sss, aa},
G = Groeb3[F];
s = Length[G];
Do[
  Do[
    If[i =!= j && G[[j]] =!= a && G[[i]] =!= a,
      h = LT2[G[[i]]][[2]] - LT2[G[[j]]][[2]];
      If[Select[h, #1 < 0 &] == {},
        G = ReplacePart[G, a, i]]];
  j = j + 1, {j, s}];
i = i + 1, {i, s}];
G = DeleteCases[G, a];
ss = Length[G];
Do[t = LT2[G[[k]]][[1]];
  If[t =!= 1,
    sss = Length[G[[k]]];
    aa = G[[k]];
    Do[aa = ReplacePart[aa,
      {Expand[Simplify[aa[[m]][[1]]/t]], aa[[m]][[2]]}, m], {m,sss}];
    G = ReplacePart[G, aa, k]], {k, ss}];
G];

(* リスト表示の左極小 Groebner 基底を簡約化する関数 *)

 RedGroeb[F_] :=RedGroeb[F] =
Module[{G, s, k},
G = MinGroeb[F];
s = Length[G];
Do[k = PolyDiv2[G[[j]], Delete[G, j]][[2]];
  G = ReplacePart[G, k, j], {j, s}];
G];

(* 実際に計算 *)

 Expand[Simplify[ListPoly[RedGroeb[PolyList[generator,valueorder]],
valueorder]]]]

プログラムの説明： f_{1}, ⋯, f_{s} ∈ R′, x_{1} > ⋯ > x_{n} を満たす単項式順序 (monomialorder) > に対し,

          NCGroebner[ { f_{1}, · · · , f_{s} }, monomialorder, { x_{1}, · · · , x_{n}, t } ]

と入力すると, 左イデアル I_{L} (f_{1}, ⋯, f_{s}) の左 (簡約)Gröbner 基底

{ g_{1}, ⋯, g_{t} }

を出力する. ただし monomialorder とダミー変数 t については, NCPolyDiv と同様である.

付録C 左イデアル所属判定プログラム

以下は, 数式処理ソフト Mathematica で多項式が, 与えられた左イデアルに属するかどうかを判定し, 属する場合については具体的表現を計算するプログラムである. ただし, プログラム内の関数で, NCPolyDiv 及び NCGroebner で用いたものについては省略してある.

In[17]:=
NCIdealRepr[polynomial_, generator_, valueorder_] :=
   Module[{monoorder, LT2, ListPoly, PolyList, Polymono2, sig, PolyPlus,
   PolyTimes, PolyDiv2, S2, Groeb3, fmc, gmc, lenlen, datedate, ans, qp,
   kake, tashi, kotae},

(* 単項式順序を総次数逆辞書式に設定 *)

 monoorder = grevlex;

「まずここで単項式順序を総次数逆辞書式に設定する. プログラムについては NCPolyDiv 内の初めの４つの If 文の３つ目を参照のこと」 ; (* 入力された多項式の組をリスト表示に変換する関数 *)

 PolyList[F_, val_] := 「省略: NCPolyDiv 内の PolyList を参照のこと」 ;

(* リスト表示の多項式の組を多項式に変換する関数 *)

 ListPoly[F_, val_] := 「省略: NCPolyDiv 内の ListPoly を参照のこと」 ;

(* リスト表示の多項式にリスト表示の項を加える関数 *)

 Polymono2[f_, m_] := 「省略: NCPolyDiv 内の Polymono2 を参照のこと」 ;

(* 2 つのリスト表示の項をかけたときの sig を計算する関数 *)

 sig[le_, ri_] := 「省略: NCPolyDiv 内の sig を参照のこと」 ;

(* リスト表示の多項式において左除法定理を計算する関数 *)

(* リスト表示の多項式の加法を計算する関数 *)

   PolyPlus[f_, g_] :=
 Module[{k, ff},
       k = Length[g];
       ff = f;
       Do[ff = Polymono2[ff, g[[i]]], {i, 1, k}];
       ff];

(* リスト表示の多項式の乗法を計算する関数 *)

 PolyTimes[f_, g_] :=
     Module[{k, ff, q},
       If[f == {} || g == {},
         {},
         m = Length[f];
         k = Length[g];
         ff[i_] := Table[
           {sig[f[[i]][[2]], g[[kk]][[2]]]*f[[i]][[1]]*g[[kk]][[1]],
           f[[i]][[2]] + g[[kk]][[2]]}, {kk, 1, k}];
         q = {};
         Do[q = PolyPlus[q, ff[ii]], {ii, 1, m}];
         q]];

(* リスト表示の多項式において左除法定理を計算する関数 *)

 PolyDiv2[f_, g_] := 「省略: NCPolyDiv 内の PolyDiv2 を参照のこと」 ;

(* リスト表示の多項式の左 S 多項式を計算する関数 *)

 S2[f_, g_] := 「省略: NCGroebner 内の S2 を参照のこと」 ;

(* リスト表示の多項式の組の左 Groebner 基底を計算する関数

 (注: NCGroebner 内のものとは違う) *)
 Groeb3[F_] :=Groeb3[F] =
     Module[{s, B, G, t, ss, k, S4, S, S3},
        s = Length[F];
        B = {};
        Do[Do[B = Append[B, {i, j}], {j, i + 1, s}], {i, 1, s - 1}];
        G = F;
        t = s;
        ss = Length[F[[1]][[1]][[2]]];
        While[B =!= {},
          k = B[[1]];
          S4 = PolyDiv2[S2[G[[k[[1]]]], G[[k[[2]]]]], G];

       S = S4[[2]];
       S3 = S4[[1]];
       Do[
         If[S3[[i]] =!= {},
           S3 = ReplacePart[S3,
             Table[{-S3[[i]][[j]][[1]], S3[[i]][[j]][[2]]},
               {j, 1, Length[S3[[i]]]}], i]], {i, 1, Length[S4[[1]]]}];
       S3 = ReplacePart[S3, Polymono2[S3[[B[[1]][[1]]]], fmc], B[[1]][[1]]];
       S3 = ReplacePart[S3, Polymono2[S3[[B[[1]][[2]]]], gmc], B[[1]][[2]]];
       If[S =!= {},
         t = t + 1;
         G = Append[G, S];
         datedate = Append[datedate, S3];
         Do[B = Append[B, {tt, t}], {tt, 1, t - 1}]];
       B = Delete[B, 1]];
     G];

(* 実際に計算 *)

lenlen = Length[generator];
datedate = Table[{}, {lenlen}];
datedate = Table[datedate, {lenlen}];
Do[datedate = ReplacePart[datedate,
  ReplacePart[Table[{}, {lenlen}], {{1, Table[0, {Length[valueorder]}]}}, i],      i], {i, 1, lenlen}];
ans = Expand[Simplify[ListPoly[Groeb3[PolyList[generator,
  valueorder]], valueorder]]];
Do[
  Do[datedate = ReplacePart[datedate,
    Join[Table[PolyPlus[PolyTimes[datedate[[i]][[k]], datedate[[j]][[i]]],
      datedate[[j]][[k]]], {k, 1, lenlen}],
      Table[datedate[[j]][[p]], {p, lenlen + 1, j - 1}]], j],
    {j, i + 1, Length[ans]}], {i, lenlen + 1, Length[ans] - 1}];
Do[datedate = ReplacePart[datedate,
  Delete[datedate[[i]], Table[{j}, {j, lenlen + 1, i - 1}]], i],
  {i, lenlen + 2, Length[ans]}];
qp = PolyDiv2[PolyList[{polynomial}, valueorder][[1]],
  PolyList[ans, valueorder]];
If[qp[[2]] =!= {},
  False,
  kotae = Table[kake = Table[PolyTimes[qp[[1]][[j]], datedate[[j]][[i]]],
    {j, 1, Length[ans]}];
    tashi = {};
    Do[tashi = PolyPlus[tashi, kake[[j]]], {j, 1, Length[ans]}];
    tashi, {i, 1, lenlen}];
  Expand[Simplify[ListPoly[kotae, valueorder]]]]]

プログラムの説明： f, f_{1}, ⋯, f_{s} ∈ R′[t] に対し,

NCIdealRepr[ f, { f_{1}, ⋯, f_{s} }, { x_{1}, ⋯, x_{n}, t } ]

と入力すると, f ∈ I_{L}(f_{1}, ⋯, f_{s}) のときは, f = a_{1}f_{1} + ⋯ + a_{s}f_{s} (a_{i} ∈ R′ [t]) を満たすような

{ a_{1}, ⋯, a_{s} }

を出力する. また, f ∉ I_{L}(f_{1}, ⋯, f_{s}) のときは

                                    False

を出力する.

関連図書

[1] D. Cox, J. Little, D. O’Shea: Ideals, Varieties, and Algorithm, Springer, 1996.

[2] T. Becker, V. Weispfenning: Gröbner Bases, Springer, 1993.

[3] D. Bayer, M. Stillman: A theorem on refining division orders by the reverse lexicographic order, Duke J. Math. 55, pp. 321–328, 1987.

[4] L. Robbiano: On the theory of graded structures, J. Symbolic Comput. 2, pp. 139–170, 1986.

[5] A. Kandri-Roby, V. Weispfenning: Non-commutative Gröbner bases in algebras of solvable type, J. Symbolic Comput. 9, no. 1, pp. 1–26, 1990.

[6] 上野健爾, 志賀浩二, 砂田利一編集: 数学のたのしみ, No. 11 「多項式環の視点: グレブナー基底」 , 日本評論社, 1999.