[IVA] Chapter 2, Section 3, Exercise 1, 6, 11

Exercise 1

2変数版を暫定的にscalaで書きました
http://ideone.com/BUbIU8

grlex

f divMod List(f1,f2)
res7: (List[foo.Poly2], foo.Poly2) = (List(
1x^6+1x^2,
),
1x^7+1x^3+-1y+1)

f divMod List(f2,f1)                          
res8: (List[foo.Poly2], foo.Poly2) = (List(
, 
1x^6+1x^2),
1x^7+1x^3+-1y+1)

lex

f divMod List(f1,f2)                          
res7: (List[foo.Poly2], foo.Poly2) = (List(
1x^6+1x^5y+1x^4y^2+1x^4+1x^3y+1x^2y^2+2x^2+2xy+2y^2+2,
1x^6+1x^5y+1x^4+1x^3y+2x^2+2xy+2),
2y^3+-1y+1)


f divMod List(f2,f1)
res8: (List[foo.Poly2], foo.Poly2) = (List(
1x^6y^2+1x^5y^5+1x^4y^8+1x^3y^11+1x^2y^14+1x^2y^2+1xy^17+1xy^5+1y^20+1y^8,
),
1y^23+1y^11+-1y+1)


Exercise 6

$g = 2x(2xy^2-x) - 3y(3x^2y - y -1) = -3x^2 + 2y^2 + 2y \in \langle 2xy^2-x, \; 3x^2y - y -1 \rangle$
であることは明らかだが、grlex 順序の元では、LTを考えると
$g = 0 \dot (2xy^2-x) + 0 \dot ((3x^2y - y -1) + g$ と除算されるのは明らか。

Exercise 11

あんまり厳密に証明出来ませんでした。

a. 数学的帰納法で示す

$i=1$ の場合、
$\beta \in \Delta_1 = \alpha(1) +  \mathbb{Z}^n_{\geq 0}$ ゆえ、ある $\gamma \in \mathbb{Z}^n_{\geq 0}$ が存在して $\beta = \alpha(1) + \gamma$ よって割り切れる。
$j
$i=k$ まで成り立つとして$i=k+1$ の場合を考える。
$$\beta \in \Delta_{k+1} = (\alpha(k+1)+ \mathbb{Z}^n_{\geq 0}) - \cup_{i=1}^k \Delta_i$$
ある $1 \leq j \leq k$ が存在して $\beta \in \Delta_j$ と仮定すると、
$\beta \in  \cup_{i=1}^k \Delta_i$ ゆえ $\beta \notin \Delta_{k+1}$ となって矛盾。故にそのような $j$ は存在しない。すると$x^{\alpha(k+1)}$が$x^{\beta}$を割り切る事はあきらか。
また$j < i$のとき$\alpha(j) \in \Delta_j$ ゆえ$x^{\alpha(j)}$が$x^{\beta}$を割り切るなら、$\beta \in \Delta_j$ となるが同様に$\beta \notin \Delta_{k+1}$となる。

b. $s^{\alpha(i)}$ が $x^{\gamma}$を割り切るなら$\gamma \in \Delta_i$である。よって$\gamma \in \bar{\Delta}$ であるならばどの 
$x^{\alpha(i)}$ も$x^{\gamma}$を割り切らない。

c. $\beta + \alpha(i) \notin \Delta_i$ とする。するとa.より、$x^{\beta+\alpha(i)$ を $x^{\alpha(i)}$ が割り切らない、ある$j < i$ が存在して $x^{\beta+\alpha(i)}$ を $x^{\alpha(j)}$ が割り切るか、となるが、前者はありえないので後者。
すると$f=a_1f_1+\cdots+a_jf_j+\cdots$ という分解において、$a_j$ を $a_j + c x^{\beta+\alpha(i)-\alpha(j)}$ の様に修正する事で $i$ について考察する時の $f$ の $\beta+\alpha(i)$ の項を消せる。よって$\beta + \alpha(i) \in \Delta_i$ と出来る。

d. このセクションで作った除算アルゴリズムがそのアルゴリズム、なんだがどう示したものか。