27 June, 2014

[IVA] Chapter 2, Section 3, Exercise 11

前回、ちゃんと解けなかったので。

c. 除算アルゴリズムによって $f=a_1 f_1 + \cdots + a_s f_s + r$ と得られたとする。
$f$ のLMを $x^{\beta}$ とするとき、$\beta \in \Delta_1 = \alpha(1) + \mathbb{Z}^n_{\geq 0}$ であるならば、ある$\gamma \in  \mathbb{Z}^n_{\geq 0}$ が存在して $x^{\beta} = x^{\alpha(1)} x^{\gamma}$ となるから、
$$a_1 \rightarrow a_1 + \frac{\mathrm{LT}(f)}{\mathrm{LT}(f_1)}, \; f \rightarrow f - \frac{\mathrm{LT}(f)}{\mathrm{LT}(f_1)}f_1$$
を繰り返す事で、$\mathrm{multideg}(f) \notin \Delta_1$ と出来る。

$f \leftarrow f - a_1 f_1$ とすると、上の議論より $\mathrm{multideg}(f) \notin \Delta_1$。
同様にして、もし $\mathrm{multideg}(f) \in \Delta_2$  ならば、
$$a_2 \rightarrow a_2 + \frac{\mathrm{LT}(f)}{\mathrm{LT}(f)}, \; f \rightarrow f_2 - \frac{\mathrm{LT}(f)}{\mathrm{LT}(f_2)}f_2$$
を繰り返す事で、$\mathrm{multideg}(f) \notin \Delta_2$ と出来る。

$\mathrm{multideg}(f)$ が $\Delta_1, \Delta_2, \cdots, \Delta_s$ のどれにも含まれない場合は、$r \rightarrow r + \mathrm{LT}(f), \; f \rightarrow f -  \mathrm{LT}(f)$ とするが、これは $\mathrm{multideg}(f) \in \bar{\Delta}$ である $\mathrm{LT}(f)$ を $r$ へと移動して、次の項について、$\Delta_1, \cdots, \Delta_s, \bar{\Delta}$ のどれに属すか探索を繰り返すことと等しい。

d. 唯一である事を示す。
$f = a_1 f_1 + \cdots a_s f_s + r = a_1' f_1 + \cdots a_s' f_s + r'$ と書けたとする。
仮定より $\mathrm{multideg}(f - a_1 f_1), \mathrm{multideg}(f - a_1' f_1),  \notin \Delta_1$ であるが、$a_1 \neq a_1'$  とすると $(a_1 - a_1')f_1 \in Delta_1$ であるから矛盾。よって $a_1 = a_1'$ 。
同様にして $a_2 = a_2', \; \cdots, a_s = a_s'$ であることを示す事が出来、その結果 $r=r'$。
  

No comments: