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

Exersise 1.

$S=(c_1, \cdots, c_s)$, $T=(d_1, \cdots, d_s)$ は $F=(f_1, \cdots, f_s)$ の syzygy ゆえ、
$$\sum_{i=1}^s c_i \mathrm{LT}(f_i) = \sum_{i=1}^s d_i \mathrm{LT}(f_i) = 0$$ .

$$\sum_{i=1}^s (c_i + d_i)  \mathrm{LT}(f_i) = \sum_{i=1}^s c_i \mathrm{LT}(f_i) + \sum_{i=1}^s d_i \mathrm{LT}(f_i) = 0$$ ,
$$\sum_{i=1}^s (g c_i)  \mathrm{LT}(f_i) = g \sum_{i=1}^s c_i \mathrm{LT}(f_i) = 0$$ ,
より
$S+T=(c_1 + d_1, \cdots, c_s + d_s)$, $g \cdot S = (g c_1, \cdots, g c_s)$ もまた syzygy となる。

Exercise 6.

$S_j$ が $S(G)$ の multideg $\gamma_j$ の homogeneous syzygy であるとき、$S_j \cdot G$ の multideg $< \gamma_j$ を示せ。

$G = (g_1, \cdots, g_s)$ とする。

$S_j \cdot G = \sum_{i=1}^s c_i x^{\alpha(i)} g_i$ であるが、
$$\mathrm{multideg}(S_j \cdot G)$$
$$= \mathrm{multideg}(\sum_{i=1}^s c_i x^{\alpha(i)} g_i) \leq \max_{i=1}^s \mathrm{multideg}(x^{\alpha(i)} g_i)$$
$$= \max_{i=1}^s \mathrm{multideg}(x^{\alpha(i)} \mathrm{LT}(g_i))$$

ここで等号成立は $\sum_{i=1}^s x^{\alpha(i)} \mathrm{LT}(g_i) \neq 0$ の場合であるが、

$S_j \subset S(G)$ であるから $\sum_{i=1}^s c_i x^{\alpha(i)} \mathrm{LT}(g_i) = 0$

より等号は成立しない。よって $\mathrm{multideg}(S_j \cdot G) < \max_{i=1}^s \mathrm{multideg}(x^{\alpha(i)} g_i)$ であるが、

homogeneous syzygy の定義より

$S_j = (c_1 x^{\alpha(1)}, \cdots, c_s x^{\alpha(s)})$ where $c_i \in k$ かつ $c_i \neq 0$ ならば $\alpha(i) + \mathrm{multideg}(g_i) = \gamma_j$

であるから、
 $\mathrm{multideg}(S_j \cdot G) < \gamma_j$ となる。

Exersise 11.

元の Buchberger では除算を 17 回、syzygy を使用したものは 4 回で済んでいる。

用いたコードは https://github.com/tmiya/scala_Buchberger にあります。

   // buchberger
  val buch_f1 = Poly(Seq(
     (Mono(Seq(3,0,0))(grlex), Q(1,1)),
     (Mono(Seq(1,1,0))(grlex), Q(-2,1))
     ))(grlex)                                    //> buch_f1  : basic.Poly = x^3 + -2xy
  val buch_f2 = Poly(Seq(
     (Mono(Seq(2,1,0))(grlex), Q(1,1)),
     (Mono(Seq(0,2,0))(grlex), Q(-2,1)),
     (Mono(Seq(1,0,0))(grlex), Q(1,1))
     ))(grlex)                                    //> buch_f2  : basic.Poly = x^2y + -2y^2 + x
  val buch_base1 = Poly.buchberger(Seq(buch_f1, buch_f2))(grlex)
                                                  //> divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| buch_base1  : Seq[basic.Poly] = ArrayBuffer(x^3 + -2xy, x^2y + -2y^2 + x, -
                                                  //| x^2, -2xy, -2y^2 + x)
  val buch_base2 = Poly.reduce(buch_base1)(grlex) //> buch_base2  : Seq[basic.Poly] = List(x^2, xy, y^2 + -1/2x)
  
  val buch2_base1 = Poly.buchberger2(Seq(buch_f1, buch_f2))(grlex)
                                                  //> divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| divmod
                                                  //| buch2_base1  : Seq[basic.Poly] = ArrayBuffer(x^3 + -2xy, x^2y + -2y^2 + x, 
                                                  //| -x^2, -2y^2 + x, -2xy)