1 Groebner hara/

Transcription

1 1 Groebner sinara@blade.nagaokaut.ac.jp hara/

2

3 Groebner Groebner URL

4

5 ( ) R 2 + : R R R, (a, b) a + b : R R R, (a, b) a b 2 0, 1 R (R, +,, 0, 1) (1) a, b, c R (a + b) + c = a + (b + c). (2) a, b R a + b = b + a. (3) a R a + 0 = a, 0 + a = a. (4) a R b R a + b = b + a = 0. (5) a, b, c R (a b) c = a (b c). (6) a R a 1 = a, 1 a = a. (7) a, b, c R a (b + c) = a b + a c, (a + b) c = a c + b c. (8) a, b R a b = b a. (9) a R a 0 b R a b = b a = 1. 1 (1) +, R (2) 0, 1 R (3) a b ab (4) 1.1 (4) b a a (5) a + ( b) a b (6) 1.1 (9) b a a 1

6 2 1 1 (7) a b 1 a/b (1) (2) (R, +,, 0, 1) R 1.2 ( ) R (1) R (2) R (3) a R (4) a R (5) a 0 = 0. (6) a ( b) = (a b). 1 ( ) (1) (Z, +,, 0, 1). (2) (Q, +,, 0, 1). (3) (R, +,, 0, 1). (4) (C, +,, 0, 1). (5) (Z[ d], +,, 0, 1) d (6) (k[x 1, x 2,, x n ], +,, 0, 1). k (7) (M n (k), +,, O, E). (8) (D n (k), +,, O, E). (9) A 2 = {a, b} (10) A 4 = {a, b, c, d} + a b a a b b b a a b a a a b a b + a b c d a a b c d b b c d a c c d a b d d a b c 0 = a, 1 = b a b c d a a a a a b a b c d c a c a c d a d c b 0 = a, 1 = b k Q, R, C {a, b, c} : (a, b, c) : x : x x : x P = Q : P Q P Q : P Q P Q : P Q P Q : P Q 1.3 ( ) f : X Y (1) y Y x Xf(x) = y f (2) x, x X(x x f(x) f(x )) f (3) f f

7 ( ) R, S f : R S f R S (1) a, b R f(a + b) = f(a) + f(b) (2) a, b R f(a b) = f(a) f(b) (3) f(1) = 1 f f R S R S R S R = S 1.5 f : R S (1) f(0) = 0. (2) f( a) = f(a). (3) f(a 1 ) = f(a) 1, (a 1 ). (4) f f 1 2 (1) R i : R R, x x (2) f : A 2 A 4, f(a) = a, f(b) = c (3) g : A 4 A 2, g(a) = a, g(b) = b, g(c) = a, g(d) = b 1.6 ( ) (R, +,, 0, 1) S +,, 0, 1 S R j : S R, x x 3 (1) Z Q (2) Q R (3) R C (4) D n (k) M n (k) ( ) R I I R 4 (1) x, y I x + y I. (2) x R y I x y I. (1) R {0} R (2) nz = {n m m Z} Z (3) A 4 I = {a, c} (4) R = k[x] x I = <x 2 + 1> (5) R S R R = S (6) R 1.8 S R <S> = {x R s 1, s 2,, s n S r 1, r 2,, r n R x = r 1 s 1 + r 2 s r n s n }

8 4 1 S S = {s 1, s 2,, s k } <S> <s 1, s 2,, s k > Rs 1 + Rs Rs k <a> = Ra 2 < S > R 5 Z <n> = nz 1.9 ( ) R I a R [a] = {x R x a I} a ( ) R/I = {[a] a R} 3 [a] = {a + x R x I} a + I 6 ( ) (1) Z/2Z = {[0], [1]}, [0] = {, 2, 0, 2, 4, }, [1] = {, 1, 1, 3, 5, }. (2) Z/4Z = {[0], [1], [2], [3]}, [0] = {, 4, 0, 4, 8, }. (3) k[x]/<x 2 + 1>, [0] = {a(x 2 + 1) k[x] a k} ( ) (1) a b I. (2) [a] [b] φ. (3) [a] = [b]. (4) a [b] (1) x x R/I a x a x (2) a 1, a 2, R [a 1 ] [a 2 ] = R [a 1 ], [a 2 ], {a 1, a 2, } R/I (3) π : R R/I, a [a] 7 ( ) (1) {0, 1} Z/2Z (2) {0, 1, 2, 3} Z/4Z (3) {a + bx k[x] a k, b k} k[x]/<x 2 + 1> 1.12 ( ) R I R R/I +, 0, 1 ( ) (1) x + y = [a + b] a x, b y (2) x y = [a b] a x, b y (3) 0 = [0] (4) 1 = [1] 1.13 (R/I, +,, 0, 1) π : R R/I, a [a] 8 ( ) (1) Z/2Z = {[0], [1]}, + [0] [1] [0] [0] [1] [1] [1] [0] [0] [1] [0] [0] [0] [1] [0] [1]

9 1 5 + [0] [1] [2] [3] [0] [1] [2] [3] [0] [0] [1] [2] [3] (2) Z/4Z = {[0], [1], [2], [3]}, [1] [1] [2] [3] [0] [2] [2] [3] [0] [1] [3] [3] [0] [1] [2] (3) R[x]/<x 2 + 1> = {a + bi a, b R}, i = [x]. 0 = 0 + 0i, 1 = 1 + 0i, (a + bi) + (c + di) = (a + c) + (b + d)i, (a + bi) (c + di) = (ac bd) + (ad + bc)i.. [0] [0] [0] [0] [0] [1] [0] [1] [2] [3] [2] [0] [2] [0] [2] [3] [0] [3] [2] [1] (, ) f : R S (1) Imf = {f(x) S x R} f (image) (2) Kerf = {x R f(x) = 0} f (kernel) 1.15 (1) Imf S (2) Kerf R 1.16 ( ) f : R S f : R/Kerf Imf, [a] f(a). [ ] (1) well-defined (2) (3) (4) 1.17 (1) Z/2Z = A 2. (2) Z/4Z = A 4. (3) R[x]/<x 2 + 1> = C ( ) R 1.19 a, b R a b = 0 = a = 0 b = ( ) R I R a, b R a b I = a I b I I R R/I I 9 (1) R = Z, I = 3Z I (2) R = Z, I = 4Z I 1.22 ( ) R I R I J R J J = I J = R

10 R/I I [ ] R/I {0} R I J I R a J I a I [a] 0 R/I [a] [b] [a][b] = [1] [ab 1] = 0 ab 1 I J ab J 1 J J = R I I R R/I [a] R/I, [a] 0 a I <a, I> = R r R s I ra + s = 1 [r][a] = [1] = 1 [r] [a] 10 ( ) (1) 3Z Z Z/3Z (2) R[x]/<x 2 + 1> = C <x 2 + 1> R[x] 1.24 p Z/pZ F p p (, ) R R 4 (1) R R = R {0} (2) R (R[x]) = R k k = Q, R, C 2.1 ( ) k[x] = {a m x m + a m 1 x m a 0 i a i k, m N} (1 ) 5 N = Z 0 = {0 }. 2.2 f = a m x m + a m 1 x m a 0, (a m 0) deg(f) = m (degree) LC(f) = a m (leading coefficient) LM(f) = x m (leading monomial) LT(f) = a m x m (leading term) RT(f) = f LT(f) (rest term) 2.3 f, g 0 (1) deg(fg) = deg(f) + deg(g). (2) f + g 0 deg(f + g) max{deg(f), deg(g)}. (3) f + g 0 deg(f) deg(g) deg(f + g) = max{deg(f), deg(g)}.

11 ( ) f, g k[x], g 0 q k[x] f = g q g f g f q = f/g f g 2.5 f, g 0 (1) deg(g) deg(f) LT(g) LT(f). (2) deg(g) deg(f), h = f LT(f) g h = 0 (h 0 deg(f) > deg(h)). LT(g) 2.6 ( ) f, g k[x], g 0 f g (1) f = g q + r, q, r k[x]. (2) r = 0 (r 0 deg r < deg g). Input : f, g Output : q, r q := 0; r := f WHILE r!= 0 AND LT(g) LT(r) DO q := q + LT(r) / LT(g) r := r - ( LT(r) / LT(g) ) * g (1), (2) q, r 11 f = x 3 + 2x 2 + x + 1 g = 2x + 1 1/2x^2 + 3/4x + 1/ x + 1 x^3 + 2x^2 + x + 1 x^3 + 1/2x^ /2x^2 + x + 1 3/2x^2 + 3/4x /4x + 1 1/4x + 1/ / ( ) q, r q f div g quotient(f, g) r f mod g ramainder(f, g) [ ][ 2.6] 2.8 g f f mod g = 0. [ ] ( ) (1) f mod (x a) = f(a). (2) (x a) f f(a) = ( ) f(x) = 0 deg f 2.11 (1 ) k[x]

12 8 1 [ ] I k[x] {0} I {0} deg h I = <h> <h> I I <h> f I r = f mod h r I r 0 deg r < deg h deg h r = 0 h f f <h> I <h> 2.12 (, PID) PID (Principal Ideal Domain) 2.3 GCD 2.13 f, g k[x] f, g GCD(f, g) (gratest common devisor) h (1) h f, h g. (2) p (p f, p g p h) ( ) f, g k[x] (1) GCD(f, g) k[x] (2) <f, g> = <GCD(f, g)>. (3) GCD(f, g) Input : f, g Output : h h := f s := g WHILE s!= 0 DO r := remainder(h, s) h := s s := r [ ] (1), (2): <f, g> <f, g> = <h> h h f g GCD f, g <h> h f, h g p f, p g <f, g> <p> p h h, h GCD h h h h h h (3): 12 (1) GCD(x 4 1, x 6 1) = x 2 1. (2) GCD(x 5 + 2x 3 + x, x 4 + x 2 x) = x ( ) f, g k[x] h f h g h GCD(f, g) deg GCD(f, g) = f, g, h k[x] f g h f g f h [ ] 1 = af + bg a, b k[x] f gh f bgh = (1 af)h = h afh fk = h afh k f (k + ah) = h f h

13 ( ) f, g k[x] af + bg = GCD(f, g) a, b deg a < deg g deg GCD(f, g), deg b < deg f deg GCD(f, g). a, b : Input : f, g (!= 0) Output : h, a, b h, s := f, g a, b, c, d = 1, 0, 0, 1 WHILE s!= 0 DO q := quotient(h, s) r := h - qs r0 := a - qc r1 := b - qd h, s := s, r a, c := c, r0 b, d := d, r1 [ ] 13 (1) f = x 4 x 2, g = x 3 1 GCD(f, g) = x 1 = (x + 1)f + ( x 2 x 1)g. x x^3-1 x^4-x^2 x^4 - x -x x^2+x x^3-1 x^3-x^ x^2-1 x^2 - x -x x - 1 -x^2 + x -x^2 + x a: x b: x x -1 x -x x 1 -x -1 x^2 + x x + 1 -x^2-x-1 (2) f = x 4 1, g = x 6 1 GCD(f, g) = x 2 1 = x 2 f + 1 g. (3) f = x 5 + 2x 3, g = x 4 + x 2 x GCD(f, g) = x = x 2 f + ( x 3 x 1) g f 1, f 2,, f s GCD h

14 10 1 (1) h f 1, f 2,, f s. (2) p f 1, f 2,, f s p h. h GCD(f 1, f 2,, f s ) 2.19 s 0, f 1, f 2,, f s k[x] (1) GCD(f 1, f 2,, f s ) (2) <GCD(f 1, f 2,, f s )> = <f 1, f 2,, f s >. (3) GCD(f 1, f 2,, f s ) = GCD(f 1, GCD(f 2,, f s )). (4) GCD(f 1, f 2,, f s ) [ ] (1), (2): k[x] <f 1, f 2,, f s > h 2.14 (3), (4): h = GCD(f 2,, f s ) (2) <h> = <f 2,, f s > <f 1, h> = <f 1, <h>> = <f 1, <f 2,, f s >> = <f 1, f 2,, f s > GCD GCD(f 1, h) = GCD(f 1, f 2,, f s ) GCD(f 1, f 2,, f s ) 14 GCD(x 3 3x + 2, x 4 1, x 6 1) = GCD(x 3 3x + 2, x 2 1) = x ( ) x 3 + 4x 2 + 3x 1 <x 3 3x + 2, x 4 1, x 6 1> x 3 + 4x 2 + 3x 1 x ( ) a R a 1 a = bc, (b, c R) b c a 16 Z 2.21 R = Z k[x] (k ) p R R/<p> [ ] [f] R/<p>, [f] 0 p f GCD(f, p) = 1 h = GCD(f, p) h p, h f h p h = 1 h = p h = p p f h = 1 af + bp = 1 a, b R [a][f] = 1 [f] [a] 17 F 7 = Z/7Z ( 2)3 = = 2 = 5 18 Q[x]/<x 2 2> x 2 + x + 1 (x 2)(x 2 2) + ( x + 3)(x 2 + x + 1) = 7. [x 2 + x + 1] 1 = 1 7 [ x + 3] 1 2 = ( 2 + 3) ( ) p R p (ab), (a, b R) p a p b p 2.23 p <p> 2.24

15 3 11 [ ] p p = ab p a p b p a p = au u R p = pub p(1 ub) = 0 ub = 1 b p b 2.25 P ID [ ] p p ab p a GCD(p, a) = 1 k, l pk + la = 1 pkb + lab = b p ab p p b p b p 6 k[x] k[x 1, x 2,, x n ] 19 Z[ 5] = {a+b 5 a, b Z} 2, 3, 1+ 5, = (1+ 5)(1 5) Z[ 5] P ID 3 3 ( ) X Y = {(x, y) x X, y Y } X Y Z = {(x, y, z) x X, y Y, z Z} (X Y ) Z = X (Y Z) = X Y Z X n = {(x 1, x 2,, x n ) x i X} f : X n Y, x = (x 1, x 2,, x n ) f(x) = f(x 1, x 2,, x n ) 3.1 ( ) n k f 1, f 2,, f s k[x 1, x 2,, x n ] V(f 1, f 2,, f s ) = {a k n f i (a) = 0 (1 i s)} f 1, f 2,, f s (1) V(x 2 + y 2 1) (2) V(xy x 3 + 1) (3) V(y 2 x 3 )

16 (4) V(y 2 x 3 x 2 ) (5) V(z x 2 y 2 ) (6) V(z 2 x 2 y 2 ) (7) V(x 2 y 2 z 2 + z 3 ). fi (8) V(x + y + z, x z, 2x + w). (9) V(xz, yz) (10) V(y x 2, z x 3 ) V, W k n V W, V W [ ] V = V(f 1, f 2 ), W = V(g 1, g 2 ) V W = V(f 1, f 2, g 1, g 2 ), V W = V(f 1 g 1, f 1 g 2, f 2 g 1, f 2 g 2 ) (1) V(f 1, f 2,, f s ) φ 1 (2) 1 (3) 3.3 (, ) R I S S I

17 I k[x 1, x 2,, x n ] I V(I) = {a k n f(a) = 0 ( f I)}. 3.5 V(<f 1, f 2,, f s >) = V(f 1, f 2,, f s ). k n [ ] f i <f 1, f 2,, f s > a V(<f 1, f 2,, f s >) a V(f 1, f 2,, f s ) V(<f 1, f 2,, f s >) V(f 1, f 2,, f s ) i f i (a) = 0 f = c i f i <f 1, f 2,, f s > f(a) = ( c i f i )(a) = c i f i (a) = 0 V(f 1, f 2,, f s ) V(<f 1, f 2,, f s >) 21 <2x 2 +3y 2 11, x 2 y 2 3> = <x 2 4, y 2 1> V(2x 2 +3y 2 11, x 2 y 2 3) = V(x 2 4, y 2 1) = {(±2, ±1)} 3.6 S k n I(S) = {f k[x 1, x 2,, x n ] f(a) = 0 ( a S)}. S 3.7 I(S) k[x 1, x 2,, x n ] [ ] 22 (1) k 2 I({(0, 0)}) = <x, y> (2) k n I(k n ) = {0} k I(k n ) = {0} 3.12 k = F 2 I(k) = <x(x 1)> (3) I(φ) = k[x 1, x 2,, x n ]. V : I : { } { }. { } { }. 3.8 (V I ) (1) V W I(V ) I(W ) V, W k n (2) I J V(I) V(J) I, J k[x 1, x 2,, x n ] (3) V V(I) I(V ) I V k n I k[x 1, x 2,, x n ] [ ] (1), (2) (3) V V(I) a V f I f(a) = 0 f I a V f(a) = 0 I(V ) I. 3.9 I k[x 1, x 2,, x n ] I I(V(I)). [ ] V(I) V(I) 3.8(3) V = V(I) I(V(I)) I 7 I = I(V(I))

18 14 1 R 3 I = <y x 2, z x 3 > I(V(I)) I f I(V(I)) = I(V(y x 2, z x 2 )) h 1, h 2 R[x, y, z], r R[x] f = h 1 (y x 2 ) + h 2 (z x 3 ) + r x α y β z γ = x α (x 2 + (y x 2 )) β (x 3 + (z x 3 )) γ ) V(I) (x, y, z) = (t, t 2, t 3 ) t R r(t) = 0 ( t R) r = 0 : R 2 I = <x 2, y 2 > V(I) = {(0, 0)} I(V(I)) = I({(0, 0)}) = <x, y> k 1 I(V(I)) = I I = {f k n Z 0 f n I} 3.10 V k n V = V(I(V )). [ ] V V(I(V )) : I(V ) I(V ) 3.8(3) I = I(V ) V V(I(V )) V V(I(V )) : V V = V(I) I 3.9 I I(V(I)) 3.8(2) V(I) V(I(V(I))) V )) 3.11 V, W (1) V W I(V ) I(W ). (2) V = W I(V ) = I(W ). (3) I : { } { } [ ] (1) ( ) 3.8(1) ( ) I(V ) I(W ) V 3.8(2) V(I(V )) V(I(W )) V, W 3.10 V W (2) (1) (3) (2) 3.12 k I(k n ) = {0} [ ] n = 1 : a k f(a) = 0 f = x a f = 0 n = t OK n = t + 1 x = (x 1, x 2,, x t ), y = x t+1 f I(k t+1 ) f = n f n(x)y n, f n k[x 1, x 2,, x n ] a = (a 1, a 2,, a t ) k n F (y) = n f n(a)y n k[y] b k F (b) = 0 1 F = 0 n f n (a) = 0 a n = t f n = 0 f = 0 f <f 1, f 2,, f s > I I(V(I))

19 15 2 Groebner 2 A, B AB = E BA = E AB = E B = A 1 BA = A 1 A = E ( ) ( ) a b e f A =, B = c d g h ( ) ( ) ae + bg 1 af + bh ae + cf 1 be + df AB E = = 0 BA E = = 0 ce + dg cf + dh 1 ag + ch bg + dh 1 : require "algebra" P = MPolynomial(Rational) a,b,c,d,e,f,g,h = P.vars("abcdefgh") M = SquareMatrix(P, 2) A, B = M[[a,b],[c,d]], M[[e,f],[g,h]] C, D = A*B - 1, B*A - 1 F = C.flatten cb = Groebner.basis_coeff(F) puts "F = #{F.inspect}" D.each do row row.each do g q, r = g.div_cg(f, cb) puts "#{g} = #{q.inspect} * F" if r.zero? end end F = [ae + bg - 1, af + bh, ce + dg, cf + dh - 1] ae + cf - 1 = [dh, -dg, af, -ae + 1] * F be + df = [-df, de, bf, -be] * F ag + ch = [-ch, cg, ah, -ag] * F bg + dh - 1 = [-dh + 1, dg, -af, ae] * F

20 16 2 Groebner ae + cf 1 = dh (ae + bg 1) dg (af + bh) + af (ce + dg) + ( ae + 1) (cf + dh 1) be + df = df (ae + bg 1) + de (af + bh) + bf (ce + dg) be (cf + dh 1) ag + ch = ch (ae + bg 1) + cg (af + bh) + ah (ce + dg) ag (cf + dh 1) bg + dh 1 = ( dh + 1) (ae + bg 1) + dg (af + bh) af (ce + dg) + ae (cf + dh 1) AB = E BA = E ( ) X (X, ) (1) x x. (2) x y, y z x z. (3) x y, y x x = y. x, y, z X (4) x, y X x y y x 23 (1) N = Z 0 = {0 } (2) N x y y x 1.2 ( ) X α β α β 24 (1) N {0} x y y x (1) x > y x y x y (2) x y y x (3) x < y x y x y

21 (N n ) α = (α 1, α 2,, α n ), β = (β 1, β 2,, β n ) N n α β i α i β i N n 8 (N n, ) n ( ) 2 (X, ), (Y, ) (X Y, ) : (x 1, y 1 ) (x 2, y 2 ) x 1 x 2 y 1 y N n N N n = N n 1 N 2 N n 2.1 Dikson 2.1 ( ) (X, ) A A X 25 {n N n 1} N a A x X(x a x A). 2.2 ( ) S X (1) X A S A a A s S a s. S A S A (2) X S <S> = {x X s S x s} S S = {s 1, s 2,, s k } <S> <s 1, s 2,, s k > (3) X A A 2.3 (1) <S> X (2) S <S> = S (3) S A A <S> [ ]

22 18 2 Groebner 2.4 (Dickson ) (X, ) X X Dickson Dickson (1) N N Dickson (2) N 23 (2) N Dickson 2.5 (Dickson ) (X, ) 3 (1) X Dickson (2) X S = (x 1, x 2, ) (3) X S = (x 1, x 2, ) i, j i < j x i x j [ ] (1) (2): S S S S S S i 1 S S(k) = {x i S k < i x i1 x k x i } S(i 1 ) S(i 1 ) S(i 2 ) x i3, x i4, x i1 x i2 x i3 x i4 (2) (3): x i2 (3) (1): Dickson X A x 1 A {x 1 } A A x 2 {x 1, x 2 } A x 2 x 3 A x 1 x 3 x 2 x 3 x n x 1 x n, x 2 x n,, x n 1 x n S = (x 1, x 2, ) (3) x X Dickson A 1 A 2 A 3 X N n N A n = A N [ ] X Dickson i A i F i A i F i A i i n F A n n X Dickson A 1 = {} A 1 A 2 A 3 A k X A k x X A k A k+1 = <A k {x}> A k A k+1 A n, n (X, ), (Y, ) Dickson (X Y, ) Dickson [ ] (x 1, y 1 ), (x 2, y 2 ), X Y X Dickson 2.5 (2) 1, 2, A {x i i A} Y Dickson 2.5 (3) A i, j (i < j) y i y j (x i, y i ) (x j, y j ) 2.5 (3) X Y Dickson 2.8 (N n ) N n Dickson N n <A> A A <A> = <A > [ ] n = 1 N Dickson n = k Dickson 2.7 N k+1 = N k N Dickson n N n Dickson

23 2 19 A A A <A > 2.3 <A> <<A >> = <A > A A <A> = <A > (, ) (X, ) A a A (1) x A (x a) a A (2) x A (x < a ) a A (N 2, ) A = {(0, 1), (1, 0)} a = (0, 1) 2.10 ( ) (X, ) (X, ) 13 Dickson 28 (1) (N, ) (2) (N n, ) n 2 (3) (Z, ) (4) (Q 0, ) 2.3 Noether ( ) Dickson Noether 2.11 (Noether ) (X, ) S S Noether Nethoer 2.12 (X, ) Noether X x 1 > x 2 > [ ] ( X A x 1 A A x 1 x 1 x 2 A x 1 > x 2 > x 3 > A 2.13 Dicskon Noether [ ] 2.12 Noether Dickson 29 Noether Dickson X x, y X x > y Noether Dickson 2.14 Noether Dickson

24 20 2 Groebner [ ] Dickson (X, ), (Y, ) Noether (X Y, ) Noether [ ] N n α = (α 1, α 2,, α n ), β = (β 1, β 2,, β n ) N n α + β = (α 1 + β 1, α 2 + β 2,, α n + β n ) 3.1 ( ) (N n, ) + α β γ N n α + γ β + γ 3.2 (N n, ) + (1) (2) (3) α N n α 0. [ ] (1) (2): A N n A A A A α 0 α A α A α α α α α 0 α 0 A (2) (3): α < 0 α α > α + α > α + α + α > (3) (1): α β α β N n α β 0 β α β 3.3 ( ) N n (1) (2) N n (3) N n [ ] 3.2

25 N n 3.5 (, lex, lexcographic order, > lex ) α = (α 1, α 2,, α n ), β = (β 1, β 2,, β n ) α > lex β α i, β i α i, β i α i > β i. 3.6 lex [ ] 4 α = (α 1, α 2,, α n ) α = α i 3.7 (, grlex, graded lexcographic order, > grlex ) α > grlex β ( α > β ) ( α = β α > lex β). 3.8 grlex [ ] 3.9 (, grevlex, graded reverse lexcographic order, > grevlex ) α = (α 1, α 2,, α n ), β = (β 1, β 2,, β n ) α > grevlex β ( α > β ) ( α = β α i, β i α i, β i α i < β i ) grevlex [ ] 30 {(0, 0, 3), (2, 0, 2), (1, 2, 1)} lex grlex grevlex (3, 0, 0) (2, 0, 2) (1, 2, 1) (2, 0, 2) (1, 2, 1) (2, 0, 2) (1, 2, 1) (3, 0, 0) (3, 0, 0) 14 N 2 grlex grevlex ( ) α = (α 1, α 2,, α n ) x α α = x 1 α2 α 1 x 2 x n n k[x 1, x 2,, x n ] 15 x α x β α β ( ) ( ) N n α = (α 1, α 2,, α n ), β = (β 1, β 2,, β n ) N n x α x β x α x β α β N n

26 22 2 Groebner N n ( ) k[x 1, x 2,, x n ] (1) x α x β x α x β (2) (3) x α x β x α x γ x β x γ 31 5x 3 + 7x 2 z 2 + 4xy 2 z + 4z 2 (lex) = 7x 2 z 2 + 4xy 2 z 5x 3 + 4z 2 (grlex) = 4xy 2 z + 7x 2 z 2 5x 3 + 4z 2 (grevlex) 3.14 f = α a αx α f 0 deg(f) = multideg(f) = max{α a α 0}. LC(f) = a deg(f) (leading coefficient) LM(f) = x deg(f) (leading monomial) LT(f) = a deg(f) x deg(f) (leading term) RT(f) = f LT(f) (rest term) 16 LT(f) LT(g) deg f deg g 32 f = 5x 3 + 7x 2 z 2 + 4xy 2 z + 4z 2 lex deg(f) = (3, 0, 0) LC(f) = 5 LM(f) = x 3 LT(f) = 5x 3 RT(f) = 7x 2 z 2 + 4xy 2 z + 4z f, g 0 (1) deg(fg) = deg(f) + deg(g). (2) f + g 0 deg(f + g) max{deg(f), deg(g)}. (3) f + g 0 deg(f) deg(g) deg(f + g) = max{deg(f), deg(g)} ( ) f F = (f 1, f 2,, f s ) (1) f = a 1 f 1 + a 2 f a s f s + r. a i r (2) r = 0 r 0 i LT(f i ) r (3) a i f i 0 deg(f) deg(a i f i )

27 3 23 Input : f, f_1, f_2,..., f_s Output : a_1, a_2,..., a_s, r a_1 := 0; a_2 = 0;... ; a_s := 0; r := 0 p := f WHILE p!= 0 DO i := 1 sw := False WHILE i <= s AND sw = False DO IF LT(f_i) divides LT(p) THEN a_i := a_i + LT(p) / LT(f_i) p := p - ( LT(p) / LT(f_i) ) * f_i sw := True ELSE i := i + 1 IF sw = False THEN r := r + LT(p) P := p - LT(p) f i f_i 33 lex (x 2 y + xy 2 + y 2 ) (xy 1, y 2 1) = (x + y, 1) x + y + 1. xy - 1 x + y r: x + y + 1 y^ x^2y + xy^2 + y^2 x^2y - x xy^2 + x + y^2 xy^2 - y x + y^2 + y --> x y^ ȳ > y 1 --> 1 0 [ ] ( 3.4) 3.17 ( F, mod F ) f k[x 1, x 2,, x n ], F = (f 1, f 2,, f t ) f F r f F remainder(f, F ) f mod F 3.18 F = (g 1, g 2,, g t ) ( ) F k [ ] 34 (1) F (xy 2 x) (xy 1, y 2 1) = (y, 0) ( x y) [lex]. (xy 2 x) (y 2 1, xy 1) = (x, 0) 0 [lex]. (2) (lex grlex) (xy + y 2 ) (x + y 2 ) = y ( y 3 + y 2 ) [lex]. (xy + y 2 ) (x + y 2 ) = 1 (xy x) [grlex]. (3) (x > y y > x) (x + y 2 ) (x + y) = 1 (y 2 y) [lex, x > y]. (y 2 + x) (y + x) = y x (x 2 + x) [lex, y > x].

28 24 2 Groebner 17 f mod F = 0 f <F > 34 (1) f mod F 0 f <F > 4 N n 5 F k[x 1, x 2,, x n ] deg(f ) = {deg(f) f F, f 0} LT(F ) = {LT(f) f F, f 0} LM(F ) = {LM(f) f F, f 0} 4.1 I deg(i) [ ] ( ) F k[x 1, x 2,, x n ] <F > deg(<f >) < deg(f )> deg(<f >) = < deg(f )> 35 f 1 = x 3, f 2 = x 2 y + x F = {f 1, f 2 }, <F > = <f 1, f 2 > x 2 = yf 1 + xf 2 <F >. lex (2, 0) = deg x 2 deg(<f >). < deg(f )> = < deg(f 1 ), deg(f 2 )> = <(3, 0), (2, 1)> deg x 2 < deg(f )> deg(<f >) < deg(f )> ( <F > = <x> ) 4.2 ( ) I G deg(i) = < deg(g)> G I 4.3 I G I I = <G> [ ] 3.16 f I G = (g 1, g 2,, g t ) a 1, a 2,, a t r r = f a 1 g 1 a t g t I r 0 i deg(g i ) deg(r) < deg(g)> deg(r) deg(i) = < deg(g)> 36 lex G = (x + y, y z) I = <G> [ ] deg(i) < deg(x + y), deg(y z)> f I, f 0 (1, 0, 0) deg(f) (0, 1, 0) deg(f) LT(f) z f z x t f(z) f I f y = t 0 f(t) = 0 f 0 z t

29 ( ) k k[x 1, x 2,, x n ] I ( 0) [ ] deg(i) deg(g 1 ), deg(g 2 ),, deg(g t ), (g i I) G = (g 1, g 2,, g t ) < deg(g)> = < deg(g 1 ), deg(g 2 ),, deg(g t )> = deg(i). 4.5 ( ) k k[x 1, x 2,, x n ] [ ] 4.6 I 1 I 2 k[x 1, x 2,, x n ] i 0 I i = I i0, ( i i 0 ) [ ] k[x 1, x 2,, x n ] I V(I) = {x k n f I f(x) = 0} G = (g 1, g 2,, g t ) I f k[x 1, x 2,, x n ] r (1) r = 0 r 0 r deg deg(g i ) ( ) (2) g I f = g + r [ ] G 3.16 f = g + r = g + r r r = g g I 0 deg(r r ) deg(i) < deg(g)> = < deg(g 1 ), deg(g 2 ),, deg(g t )> i deg(g i ) deg(r r) r r deg deg(g i ) 5.2 ( ) f k[x 1, x 2,, x n ] I : G = (f 1, f 2,, f t ) I f G G f i 5.1 (1), (2) r f G f G 5.3 G I f I f G = 0. [ ] f = f f G = 0. F = (f 1, f 2,, f t )

30 26 2 Groebner 5.2 S- 5.4 (S- ) x γ LM(f) LM(g) f g S S(f, g) = xγ LT(f) f xγ LT(g) g = f g 37 grlex f = x 3 y 2 x 2 y 3 +x, g = 3x 4 y +y 2 x γ = x 4 y 2, S(f, g) = xf y 3 g = x3 y 3 +x 2 y (1) deg S(f, g) < deg LCM(LT(f), LT(g)). (2) deg f = deg g deg S(f, g) < deg f. (3) deg f = deg g S(f, g) = f LC(f) g LC(g). (4) c, c k, c 0, c 0 S(c f, c g) = S(f, g). (5) S(f, g) S(x α f, x β g). x δ = deg LCM(LM(x α f), LM(x β g)), x γ = LCM(LM(f), LM(g)) S(x α f, x β g) = x δ x α f LM(x α f) xδ x β g LM(x β g) = xδ γ ( xγ f LM(f) xγ f LM(g) ) = xδ γ S(f, g) 5.5 δ N n, f 1, f 2,, f t k[x 1, x 2,, x n ] <f 1, f 2,, f t > <f 1, f 2,, f t > δ = { i a if i i deg(a i f i ) δ} F k[x 1, x 2,, x n ] <F > δ 19 δ N n (1) <F > δ + <G> δ = <F G> δ. (2) f i g i (1 i t) <g 1, g 2,, g t > δ <f 1, f 2,, f t > δ. 5.6 f <F > deg f (1) <f> δ <F > δ, δ N n. (2) deg(f) < deg(f )>. [ ] F = (f 1, f 2,, f t ) f = i a if i, deg(a i f i ) deg f (1) af <f> δ af <F > δ (a k[x 1, x 2,, x n ]) af = i aa if i, deg(aa i f i ) deg af δ (2) LT(f) = deg(a if i)=deg f LT(a i)lt(f i ) deg(a i f i ) = deg f i deg(f i ) deg(f) 20 (1) f F = 0 f <F > deg f (2) 2 f <F > : f = y, F = (x + y, x), δ = (0, 1), lex y <x + y, x> (0,1) = {0} deg(y) < deg(x + y), deg(x)> = <(1, 0)> 5.7 f 1, f 2,, f t deg δ f = i c if i, (c i k) deg f < δ f S(f i, f j ) k

31 6 27 [ ] LC(f i ) = 1 i c if i = c 1 (f 1 f 2 ) + (c 1 + c 2 )(f 2 f 3 ) + + (c 1 + c c t 1 )(f t 1 f t ) + (c 1 + c c t )f t. f i f i+1 deg δ c 1 + c c t = 0. i c if i = c 1 S(f 1, f 2 ) + (c 1 + c 2 )S(f 2, f 3 ) + + (c 1 + c c t 1 )S(f t 1, f t ). 5.8 F = {f 1, f 2,, f t } S(F, F ) = {S(f i, f j ) 1 i < j t} T (F ) = F S(F, F ) 5.9 F = {f 1, f 2,, f t }, f <F > δ, deg f < δ δ < δ f <T (F )> δ [ ] f = i a if i, a i k[x 1, x 2,, x n ], deg(a i f i ) δ f = deg(a i f i )=δ LT(a i)f i +f f δ δ 5.7 S(LT(ai )f i, LT(a j )f j ) 1 δ 1 = max{deg S(LT(a i )f i, LT(a j )f j ) i < j, deg(a i f i ) = deg(a j f j ) = δ} δ 1 < δ <S(LT(ai )f i, LT(a j )f j ) i < j> δ1 18(5) S(LT(a i )f i, LT(a j )f j ) S(f i, f j ) 19(2) <S(fi, f j ) i < j> δ1 = <S(F, F )> δ1 f <F > δ2 (δ 2 < δ) δ = max{δ 1, δ 2 } f <S(F, F )> δ + <F > δ = <T (F )> δ 5.10 ( S ) G = (g 1, g 2,, g s ) I G I S(g i, g j ) G = 0 ( i j ) [ ] ( ) S(g i, g j ) I = <G> S(g i, g j ) G = 0 ( 5.3 ) ( ) S(g i, g j ) G = 0 S(g i, g j ) <G> deg S(gi, g j ) 5.6(1) δ <S(g i, g j )> δ <G> δ <T (G)> δ = <G> δ f I = <G> f <G> deg f δ f <G> δ 3.4 δ δ deg f δ deg f < δ 5.9 δ < δ f <T (G)> δ = <G> δ δ δ = deg f f <G> deg f 5.6(2) deg(f) < deg(g)> f I deg(i) < deg(g)> G ( ) I = <f 1, f 2,, f s >

32 28 2 Groebner Input: F = (f_1, f_2,..., f_s) Output: G = (g_1, g_2,..., g_t) : <F> G := F REPEAT G := G For each pair {p, q}, p!= q, in G DO S := S(p, q) mod G IF S!= 0 THEN G := G + (S) UNTIL G = G [ ] ( ) S(F, F ) = {S(f i, f j ) F 1 i < j s} {0}, T (F ) = F S(F, F ) REPEAT G G G = T (G ) < deg(t i (F ))> (i = 0, 1, 2, ) 2.6 i 0 < deg(t i (F ))> (i i 0 ) G 0 = T i0 (F ) < deg(t (G 0 ))> = < deg(g 0 )> deg(s(g 0, G 0 )) < deg(g 0 )> 0 deg(s(g, g ) G0 ) (g, g G 0 ) deg(g 0 ) G 0 S(G 0, G 0 ) = {} REPEAT i 0 ( ) 5.10 G 0 = T i 0(F ) <G 0 > = <F > 6.2 (1) f F = 0 f F +(g) = 0. (2) f F = f f F +(f) = 0. (3) f F = r f F +(r) = 0. [ ] (1) f F = 0 f F +(g) 5.1 LT(g) sw True f F +(g) f F f F +(g) = 0 (2) F 0 f f (3) ( 3.18) r = f F f r F = f F r F = f F r = 0 (1) f r F +(r) = 0 f r F +(r) = f F +(r) r F +(r) = f F +(r) ( r F = r (2)) f F +(r) = ( ) Input: F = (f_1, f_2,..., f_s) Output: G = (g_1, g_2,..., g_t) : <F> G := F B := {(i, j) : 1 <= i < j <= s} t := s WHILE B!= {} DO Select (i, j) in B S := S(f_i, f_j) mod G IF S!= 0 THEN t := t + 1 f_t := S G := G + (f_t) B := B + {(i, t) : 1 <= i < t} B := B - {(i, j)} G [ ] ( ) IF S 0 S = f t 0 deg(g + (S)) deg(g) IF deg(g) 2.6 WHILE 1 B 1 WHILE

33 6 29 ( ) WHILE B (i, j) S(f i, f j ) G = 0 B (i, j) IF G G S(f i, f j ) G = 0 G G 6.2(1) S(f i, f j ) G = 0 S = S(f i, f j ) G 0 6.2(3) S(f i, f j ) G +(S) = 0 G G + (S) S(f i, f j ) G = 0 (i, j) S(f i, f j ) G = G 38 R = k[x, y] x > y grlex f 1 = x 3 2xy f 2 = x 2 y 2y 2 + x I = <f 1, f 2 > [ ] I G = {f 1, f 2, f 3, f 4, f 5 } f 3 = x 2 f 4 = 2xy f 5 = 2y 2 + x. ( ) Calculation of Groebner Basis of (grlex): f1 = x^3-2xy f2 = x^2y - 2y^2 + x G = (f1, f2) = (x^3-2xy, x^2y - 2y^2 + x) B = {(1, 2)} Round 1 S(f1, f2) = (y) * f1 - (x) * f2 = -x^2. (-x^2) mod G = -x^2. Description of mod: (null) New Generator: f3 = -x^ G = (f1, f2, f3) = (x^3-2xy, x^2y - 2y^2 + x, -x^2) B = {(1, 3), (2, 3)} Round 2 S(f1, f3) = (1) * f1 - (-x) * f3 = -2xy. (-2xy) mod G = -2xy. Description of mod: (null) New Generator: f4 = -2xy G = (f1, f2, f3, f4) = (x^3-2xy, x^2y - 2y^2 + x, -x^2, -2xy) B = {(2, 3), (1, 4), (2, 4), (3, 4)} Round 3 S(f2, f3) = (1) * f2 - (-y) * f3 = -2y^2 + x. (-2y^2 + x) mod G = -2y^2 + x. Description of mod: (null) New Generator: f5 = -2y^2 + x G = (f1, f2, f3, f4, f5) = (x^3-2xy, x^2y - 2y^2 + x, -x^2, -2xy, -2y^2 + x) B = {(1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5), (4, 5)} Round 4 S(f1, f4) = (y) * f1 - (-1/2x^2) * f4 = -2xy^2. (-2xy^2) mod G = 0. Description of mod: #1-2xy^2 => a[4] += y Round 5 S(f2, f4) = (1) * f2 - (-1/2x) * f4 = -2y^2 + x.

34 30 2 Groebner (-2y^2 + x) mod G = 0. Description of mod: #1-2y^2 + x => a[5] += 1 Round 6 S(f3, f4) = (-y) * f3 - (-1/2x) * f4 = 0. (0) mod G = 0. Description of mod: (null) Round 7 S(f1, f5) = (y^2) * f1 - (-1/2x^3) * f5 = 1/2x^4-2xy^3. (1/2x^4-2xy^3) mod G = 0. Description of mod: #1 1/2x^4-2xy^3 => a[1] += 1/2x #2-2xy^3 + x^2y => a[4] += y^2 #3 x^2y => a[4] += -1/2x Round 8 S(f2, f5) = (y) * f2 - (-1/2x^2) * f5 = 1/2x^3-2y^3 + xy. (1/2x^3-2y^3 + xy) mod G = 0. Description of mod: #1 1/2x^3-2y^3 + xy => a[1] += 1/2 #2-2y^3 + 2xy => a[5] += y #3 xy => a[4] += -1/2 Round 9 S(f3, f5) = (-y^2) * f3 - (-1/2x^2) * f5 = 1/2x^3. (1/2x^3) mod G = 0. Description of mod: #1 1/2x^3 => a[1] += 1/2 #2 xy => a[4] += -1/2 Round 10 S(f4, f5) = (-1/2y) * f4 - (-1/2x) * f5 = 1/2x^2. (1/2x^2) mod G = 0. Description of mod: #1 1/2x^2 => a[3] += -1/2 RESULT ================================================================= G = ( f1 = x^3-2xy, f2 = x^2y - 2y^2 + x, f3 = -x^2, f4 = -2xy, f5 = -2y^2 + x ) (, ) I k[x 1, x 2,, x n ] G (1), (2) G (1) p G LC(p) = 1 (2) p G deg(p) < deg(g {p})> (2) (3) G (3) p G p deg < deg(g {p})> 6.5 I G p G deg(p) < deg(g {p})> G {p} I [ ] deg(i) = < deg(g)> = < deg(g {p})> 6.6 ( ) I k[x 1, x 2,, x n ] I [ ] p G deg(p) deg(g {p}) G := G {p} R = k[x, y] x > y grlex f 1 = x 3 2xy, f 2 = x 2 y 2y 2 + x I = <f 1, f 2 > f 3 = x 2, f 4 = 2xy, f 5 = 2y 2 + x G = (f 1, f 2, f 3, f 4, f 5 )

35 6 31 [ ] deg(g) = {(3, 0), (2, 1), (2, 0), (1, 1), (0, 2)} deg(f 3 ) deg(f 1 ), deg(f 4 ) deg(f 2 ) G = <f 3, f 4, f 5 > G = (x 2, xy, y x) 21 x 2 = 2y xy 2x (y 2 1 2x) 6.7 ( ) Input: G = (f_1, f_2,..., f_s): I Output: G~ = (g_1, g_2,..., g_s) : I i := 1 G~ := G WHILE i <= s DO f_i := f mod(g~ - {f_i}) G~ := G~ - {f_i} + {f_i } i := i + 1 [ ] G deg(f 1 ) < deg(g {f 1 })> f 1 G {f 1} = f 1 deg(f 1 ) = deg(f 1 ) G = G {f 1 } {f 1} deg( G) = deg(g) ( ) f 1 deg deg(g {f 1}) = deg( G {f 1}) f 1 I ( ) G G G G G (2) G (3),..., G (s) deg(g) = deg( G) = = deg( G (s) ) f i = f G (i 1) {f i } i deg < deg( G (i 1) {f i })> = < deg( G (s) {f i })> G (s) = <f 1, f 2,, f s> G = (x 2, xy, y 2 1 2x) I = <G> G = (x 2 + xy, xy, y 2 1 2x) I 6.8 ( ) [ ] G, G G, G G, G deg(g) = deg( G) [ ] p G < deg(g)> = < deg( G)> p G deg(p ) deg(p) p G deg(p ) deg(p ) deg(p) p p p G {p} deg(p) < deg(p )> < deg(g {p})> G p = p deg(p) = deg(p ) deg( G) deg(g) deg( G) g G, g G deg(g) = deg( g) g = g [ ] f T(f) g g I g g G = 0 (a) deg(g) = deg( g) T(g g) T(RT(g)) T(RT( g)) (b) T(RT(g)) deg deg(g) deg(g {g}) deg(g) T(RT( g))

36 32 2 Groebner deg deg( G) = deg(g) (a) T(g g) deg deg(g) g g G = g g (c) (a) (c) g g = 0 G = G 6.9 ( )

37 33 3 Groebner x y z = 0. (3.1) w I = <3x 6y 2z, 2x 4y + 4w, x 2y z w> (3.2) 6.3 (lex ) G = (3x 6y 2z, 2x 4y + 4w, x 2y z w, z + 3w) Calculation of Groebner Basis of (lex): f1 = 3x - 6y - 2z f2 = 2x - 4y + 4w f3 = x - 2y - z - w G = (f1, f2, f3) = (3x - 6y - 2z, 2x - 4y + 4w, x - 2y - z - w) B = {(1, 2), (1, 3), (2, 3)} Round 1 S(f1, f2) = (1/3) * f1 - (1/2) * f2 = -2/3z - 2w. (-2/3z - 2w) mod G = -2/3z - 2w. New Generator: f4 = -2/3z - 2w G = (f1, f2, f3, f4) = (3x - 6y - 2z, 2x - 4y + 4w, x - 2y - z - w, -2/3z - 2w) B = {(1, 3), (2, 3), (1, 4), (2, 4), (3, 4)} Round 2 S(f1, f3) = (1/3) * f1 - (1) * f3 = 1/3z + w. (1/3z + w) mod G = 0. Round 3 S(f2, f3) = (1/2) * f2 - (1) * f3 = z + 3w. (z + 3w) mod G = 0. Round 4 S(f1, f4) = (1/3z) * f1 - (-3/2x) * f4 = -3xw - 2yz - 2/3z^2. (-3xw - 2yz - 2/3z^2) mod G = 0. Round 5 S(f2, f4) = (1/2z) * f2 - (-3/2x) * f4 = -3xw - 2yz + 2zw. (-3xw - 2yz + 2zw) mod G = 0. Round 6 S(f3, f4) = (z) * f3 - (-3/2x) * f4 = -3xw - 2yz - z^2 - zw.

38 34 3 Groebner (-3xw - 2yz - z^2 - zw) mod G = 0. RESULT ================================================================= G = ( f1 = 3x - 6y - 2z, f2 = 2x - 4y + 4w, f3 = x - 2y - z - w, f4 = -2/3z - 2w ) LT(G) = (3x, 2x, x, z) G = (x 2y z w, z + 3w) x 2y z w (z+3w) = x 2y + 2w, z + 3w (x 2y z w) = z + 3w G = (x 2y + 2w, z + 3w) (1) : x y z = w (2) : x y z = w 1.2 G I f I f G = 0 I = <x 3 2xy, x 2 y 2y 2 + x> x 2 + 2y 3 x 2 + 2y 3 + y 40 I x > y > z grlex G = <x 2, xy, y 2 1 2x> x 2 + 2y 3G = 0 x 2 + 2y 3 I x 2 + 2y 3 + y G = y 0 x 2 + 2y 3 + y I 1.3 x 2 + y 2 + z 2 = 1 x 2 + z 2 = y x = z I = <f 1, f 2, f 3 >, f 1 = x 2 + y 2 + z 2 1, f 2 = x 2 + z 2 y, f 3 = x z I F = (x 2 + y 2 + z 2 1, x 2 + z 2 y, x z) x > y > z lex G = (x 2 + y 2 + z 2 1, x 2 + z 2 y, x y, y 2 + y 1, y + 2z 2, 4z 4 + 2z 2 1).

39 1 35 Calculation of Groebner Basis of (lex): f1 = x^2 + y^2 + z^2-1 f2 = x^2 - y + z^2 f3 = x - z G = (f1, f2, f3) = (x^2 + y^2 + z^2-1, x^2 - y + z^2, x - z) B = {(1, 2), (1, 3), (2, 3)} Round 1 S(f1, f2) = (1) * f1 - (1) * f2 = y^2 + y - 1. (y^2 + y - 1) mod G = y^2 + y - 1. New Generator: f4 = y^2 + y G = (f1, f2, f3, f4) = (x^2 + y^2 + z^2-1, x^2 - y + z^2, x - z, y^2 + y - 1) B = {(1, 3), (2, 3), (1, 4), (2, 4), (3, 4)} Round 2 S(f1, f3) = (1) * f1 - (x) * f3 = xz + y^2 + z^2-1. (xz + y^2 + z^2-1) mod G = -y + 2z^2. New Generator: f5 = -y + 2z^ G = (f1, f2, f3, f4, f5) = (x^2 + y^2 + z^2-1, x^2 - y + z^2, x - z, y^2 + y - 1, -y + 2z^2) B = {(2, 3), (1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5), (4, 5)} Round 3 S(f2, f3) = (1) * f2 - (x) * f3 = xz - y + z^2. (xz - y + z^2) mod G = 0. Round 4 S(f1, f4) = (y^2) * f1 - (x^2) * f4 = -x^2y + x^2 + y^4 + y^2z^2 - y^2. (-x^2y + x^2 + y^4 + y^2z^2 - y^2) mod G = 0. Round 5 S(f2, f4) = (y^2) * f2 - (x^2) * f4 = -x^2y + x^2 - y^3 + y^2z^2. (-x^2y + x^2 - y^3 + y^2z^2) mod G = 0. Round 6 S(f3, f4) = (y^2) * f3 - (x) * f4 = -xy + x - y^2z. (-xy + x - y^2z) mod G = 0. Round 7 S(f1, f5) = (y) * f1 - (-x^2) * f5 = 2x^2z^2 + y^3 + yz^2 - y. (2x^2z^2 + y^3 + yz^2 - y) mod G = 4z^4 + 2z^2-1. New Generator: f6 = 4z^4 + 2z^ G = (f1, f2, f3, f4, f5, f6) = (x^2 + y^2 + z^2-1, x^2 - y + z^2, x - z, y^2 + y - 1, -y + 2z^2, 4z^4 + 2z^2-1) B = {(2, 5), (3, 5), (4, 5), (1, 6), (2, 6), (3, 6), (4, 6), (5, 6)} Round 8 S(f2, f5) = (y) * f2 - (-x^2) * f5 = 2x^2z^2 - y^2 + yz^2. (2x^2z^2 - y^2 + yz^2) mod G = 0. Round 9 S(f3, f5) = (y) * f3 - (-x) * f5 = 2xz^2 - yz. (2xz^2 - yz) mod G = 0. Round 10 S(f4, f5) = (1) * f4 - (-y) * f5 = 2yz^2 + y - 1. (2yz^2 + y - 1) mod G = 0. Round 11 S(f1, f6) = (z^4) * f1 - (1/4x^2) * f6 = -1/2x^2z^2 + 1/4x^2 + y^2z^4 + z^6 - z^4. (-1/2x^2z^2 + 1/4x^2 + y^2z^4 + z^6 - z^4) mod G = 0. Round 12 S(f2, f6) = (z^4) * f2 - (1/4x^2) * f6 = -1/2x^2z^2 + 1/4x^2 - yz^4 + z^6. (-1/2x^2z^2 + 1/4x^2 - yz^4 + z^6) mod G = 0. Round 13 S(f3, f6) = (z^4) * f3 - (1/4x) * f6 = -1/2xz^2 + 1/4x - z^5. (-1/2xz^2 + 1/4x - z^5) mod G = 0. Round 14 S(f4, f6) = (z^4) * f4 - (1/4y^2) * f6 = -1/2y^2z^2 + 1/4y^2 + yz^4 - z^4. (-1/2y^2z^2 + 1/4y^2 + yz^4 - z^4) mod G = 0. Round 15 S(f5, f6) = (-z^4) * f5 - (1/4y) * f6 = -1/2yz^2 + 1/4y - 2z^6. (-1/2yz^2 + 1/4y - 2z^6) mod G = 0. RESULT ================================================================= G = ( f1 = x^2 + y^2 + z^2-1, f2 = x^2 - y + z^2, f3 = x - z, f4 = y^2 + y - 1, f5 = -y + 2z^2, f6 = 4z^4 + 2z^2-1 )

40 36 3 Groebner G = (f 3, f 5, f 6 ) = (x z, y 2z 2, z z2 1 4 ) LT(G) = (x, y, z 4 ) z z2 1 4 = 0 z z = ± 1 ± 5. 4 x, y ( (Elimination Theorem)) I k[x 1, x 2,, x n ] G x 1 > x 2 > > x n lex I Groebner G k[x l,, x n ] k[x l,, x n ] I k[x l,, x n ] Groebner [ ] f I k[x l,, x n ] g G LT(g) LT(f) LT(f) k[x l,, x n ] LT(g) k[x l,, x n ] g k[x l,, x n ] g G k[x l,, x n ] LT(g) LT(f) g <LT(I k[x l,, x n ])> <LT(G k[x l,, x n ])> 1.5 : x = t 4 y = t 3 z = t 2 I = <f 1, f 2, f 3 >, f 1 = t 4 x, f 2 = t 3 y, f 3 = t 2 z I t > x > y > z lex G = (t 4 x, t 3 y, t 2 z) : Calculation of Groebner Basis of (lex): f1 = t^4 - x f2 = t^3 - y f3 = t^2 - z G = (t 4 x, t 3 y, t 2 z, ty x, x + z 2, tz y, y 2 + z 3 ) G = (f1, f2, f3) = (t^4 - x, t^3 - y, t^2 - z) B = {(1, 2), (1, 3), (2, 3)} Round 1 S(f1, f2) = (1) * f1 - (t) * f2 = ty - x. (ty - x) mod G = ty - x. New Generator: f4 = ty - x G = (f1, f2, f3, f4) = (t^4 - x, t^3 - y, t^2 - z, ty - x) B = {(1, 3), (2, 3), (1, 4), (2, 4), (3, 4)}

41 1 37 Round 2 S(f1, f3) = (1) * f1 - (t^2) * f3 = t^2z - x. (t^2z - x) mod G = -x + z^2. New Generator: f5 = -x + z^ G = (f1, f2, f3, f4, f5) = (t^4 - x, t^3 - y, t^2 - z, ty - x, -x + z^2) B = {(2, 3), (1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5), (4, 5)} Round 3 S(f2, f3) = (1) * f2 - (t) * f3 = tz - y. (tz - y) mod G = tz - y. New Generator: f6 = tz - y G = (f1, f2, f3, f4, f5, f6) = (t^4 - x, t^3 - y, t^2 - z, ty - x, -x + z^2, tz - y) B = {(1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5), (4, 5), (1, 6), (2, 6), (3, 6), (4, 6), (5, 6)} Round 4 S(f1, f4) = (y) * f1 - (t^3) * f4 = t^3x - xy. (t^3x - xy) mod G = 0. Round 5 S(f2, f4) = (y) * f2 - (t^2) * f4 = t^2x - y^2. (t^2x - y^2) mod G = -y^2 + z^3. New Generator: f7 = -y^2 + z^ G = (f1, f2, f3, f4, f5, f6, f7) = (t^4 - x, t^3 - y, t^2 - z, ty - x, -x + z^2, tz - y, -y^2 + z^3) B = {(3, 4), (1, 5), (2, 5), (3, 5), (4, 5), (1, 6), (2, 6), (3, 6), (4, 6), (5, 6), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7)} Round 6 S(f3, f4) = (y) * f3 - (t) * f4 = tx - yz. (tx - yz) mod G = 0. Round 7 S(f1, f5) = (x) * f1 - (-t^4) * f5 = t^4z^2 - x^2. (t^4z^2 - x^2) mod G = 0. Round 8 S(f2, f5) = (x) * f2 - (-t^3) * f5 = t^3z^2 - xy. (t^3z^2 - xy) mod G = 0. Round 9 S(f3, f5) = (x) * f3 - (-t^2) * f5 = t^2z^2 - xz. (t^2z^2 - xz) mod G = 0. Round 10 S(f4, f5) = (x) * f4 - (-ty) * f5 = tyz^2 - x^2. (tyz^2 - x^2) mod G = 0. Round 11 S(f1, f6) = (z) * f1 - (t^3) * f6 = t^3y - xz. (t^3y - xz) mod G = 0. Round 12 S(f2, f6) = (z) * f2 - (t^2) * f6 = t^2y - yz. (t^2y - yz) mod G = 0. Round 13 S(f3, f6) = (z) * f3 - (t) * f6 = ty - z^2. (ty - z^2) mod G = 0. Round 14 S(f4, f6) = (z) * f4 - (y) * f6 = -xz + y^2. (-xz + y^2) mod G = 0. Round 15 S(f5, f6) = (-tz) * f5 - (x) * f6 = -tz^3 + xy. (-tz^3 + xy) mod G = 0. Round 16 S(f1, f7) = (y^2) * f1 - (-t^4) * f7 = t^4z^3 - xy^2. (t^4z^3 - xy^2) mod G = 0. Round 17 S(f2, f7) = (y^2) * f2 - (-t^3) * f7 = t^3z^3 - y^3. (t^3z^3 - y^3) mod G = 0. Round 18 S(f3, f7) = (y^2) * f3 - (-t^2) * f7 = t^2z^3 - y^2z. (t^2z^3 - y^2z) mod G = 0. Round 19 S(f4, f7) = (y) * f4 - (-t) * f7 = tz^3 - xy. (tz^3 - xy) mod G = 0. Round 20 S(f5, f7) = (-y^2) * f5 - (-x) * f7 = xz^3 - y^2z^2. (xz^3 - y^2z^2) mod G = 0. Round 21 S(f6, f7) = (y^2) * f6 - (-tz) * f7 = tz^4 - y^3. (tz^4 - y^3) mod G = 0. RESULT ================================================================= G = ( f1 = t^4 - x, f2 = t^3 - y,

42 38 3 Groebner f3 = t^2 - z, f4 = ty - x, f5 = -x + z^2, f6 = tz - y, f7 = -y^2 + z^3 ) LT(G) = (t 4, t 3, t 2, ty, x, tz, y 2 ) G = (t 2 z, ty x, x z 2, tz y, y 2 z 3 ) LT(G) = (t 2, ty, x, tz, y 2 ) ty x (t2 z, x z 2, tz y, y 2 z 3 ) = ty z 2 G = (t 2 z, ty z 2, x z 2, tz y, y 2 z 3 ) x z 2 = y 2 z 3 = x 2 + y 2 + z 2 = 1 f(x, y, z) = x 3 + 2xyz z 2 g(x, y, z) = x 2 + y 2 + z 2 1 λ f x = λg x f y = λg y f z = λg z g = 0 3x 2 + 2yz 2xλ = 0 2xz 2yλ = 0 2xy 2z 2zλ = 0 x 2 + y 2 + z 2 1 = 0 Groebner lex, λ > x > y > z z z z z 0 z 1.7 x8 x3 x2 x4 x5 x7 x6 x1

43 1 39 F 3 = Z/3Z x i x j x i = x j + 1 x i = x j + 2 (x i x j 1)(x i x j 2) = 0 x i 2 + x i x j + x j 2 1 = 0. (i, j) L L = {(1, 2), (1, 5), (1, 6), (2, 3), (2, 4), (2, 8), (3, 4), (3, 8), (4, 5), (4, 7), (5, 6), (5, 7), (6, 7), (7, 8)} F = {x 2 i +x i x j +x 2 j 1 (i, j) L} V(<F >) x 8 0 F = F {x 8 }, V(<F >) x 1 > > x 8 lex <F > G = {x 1 x 7, x 2 + x 8, x 3 x 7, x 4, x 5 + x 7, x 6, x , x 8 } V(<F >) = V(<G>) (, ) I R I = {f R n 0 f n I} I 1.3 (1) I R (2) R {0} = {0} (3) R = R. (4) I = R I = R. [ ] 1.4 ( ) k a n x n +a n 1 x n 1 + +a 0 = 0, n > 0, a i k (0 i n), a n 0 k k 41 (1) C ( ) (2) F 3 (x = 0 ) 1.5 ( (Hilbert s Nullstellensatz)) k I R = k[x 1, x 2,, x n ] V(I) (1) V(I) = φ I = R. (2) I(V(I)) = I. [ ] 1.6 k (f 1, f 2,, f s ) k[x 1, x 2,, x n ] (1) f 1 = f 2 = = f s = 0 k n 1.9 ( ) 1.7 V(<G>) C x 3 1 = (x 1)(x 2 + x + 1) = 0

44 40 3 Groebner 1, ω, ω 2 ( ω = ) x 3 i 1 = x 3 j 1 = 0 x i, x j 2 x 2 i + x i x j + x 2 j = 0. F = {x 3 i 1 1 i 8} {x 2 i + x ix j + x 2 j (i, j) L} {x 8 1} <F > G = (x 1 x 7, x 2 + x 7 + 1, x 3 x 7, x 4 1, x 5 + x 7 + 1, x 6 1, x x 7 + 1, x 8 1) G (1) V(<G>) 1.10 ( ) ( ) A(a 1, a 2 ), B(b 1, b 2 ), C(c 1, c 2 ) H(x, y) AH, BH, CH BC, CA, AB f 1 = (x a 1 )(b 1 c 1 ) + (y a 2 )(b 2 c 2 ) f 2 = (x b 1 )(c 1 a 1 ) + (y b 2 )(c 2 a 2 ) f 3 = (x c 1 )(a 1 b 1 ) + (y c 2 )(a 2 b 2 ) f 1 = f 2 = f 3 = 0 A, B, C 1 a 1 a 2 s = 1 b 1 b 2 1 c 1 c 2 s 0 s 1 = 0 I = <f 1, f 2, f 3, s 1> lex, x > y > a 1 > a 2 > b 1 > b 2 > c 1 > c 2 g 1 = x + a 1 a 2 b 1 a 1 a 2 c 1 a 1 b 1 c 2 + a 1 c 1 c 2 + a 2 2b 2 a 2 2c 2 a 2 b a 2 b 1 c 1 a 2 b a 2 c b 2 1c 2 b 1 c 1 c 2 b 1 + b 2 2c 2 b 2 c 2 2 g 2 = y a 2 1b 1 + a 2 1c 1 + a 1 b 2 1 a 1 c 2 1 a 2 2b 1 + a 2 2c 1 +a 2 b 1 b 2 + a 2 b 1 c 2 a 2 b 2 c 1 a 2 c 1 c 2 a 2 b 2 1c 1 b 1 b 2 c 2 + b 1 c b 2 c 1 c 2 g 3 = a 1 b 2 a 1 c 2 a 2 b 1 + a 2 c 1 + b 1 c 2 b 2 c 1 1 g 3 = s 1 g 1 = g 2 = g 3 = 0 (x, y) ( (Extension Theorem)) k I = <f 1, f 2,, f s > k[x 1, x 2,, x n ] I 1 = I k[x 2,, x n ] f i x 1 f i = g i (x 2,, x n )x N i 1 +. (a 2,, a n ) V(I 1 ), (a 2,, a n ) V(g 1, g 2,, g s ) k (a 1, a 2,, a n ) V(I) [ ] ( ) a k I = <f 1, f 2,, f s > k[x 1, x 2,, x n ] I 1 = I k[x 2,, x n ] i f i x 1 f i = c x N 1 +, c k, c 0, N > 0. (a 2,, a n ) V(g 1, g 2,, g s ) a 1 k (a 1, a 2,, a n ) V(I)

45 2 41 [ ]

46

47 43 1 ( ) ( ) / / ( ) ( ) 2000, ( ) :3800 :3900 ( ) ( ) 2002, ( ) 3600 ( ) / / ( ) ( ) 2000, ( ) :4200 : ( ) ( ) 2000, ( ) ( ) ( ) 1997, ( ) 3000 ( ) ( ) 2003, ( ) 4200 Risa/Asir ( )

48 44 ( ) 2003, ( ) 4200 [ 9] ( ) ( ) 1993, ( ) 3600 ( ) ( ) 1994, 2 URL Web : hara/class/ : sinara@blade.nagaokaut.ac.jp

49 45 +, 20, 16 =, 16 5, 16 f F, 23 < > δ, 26, 17 bar, 7 deg, 6, 22 deg, 6 Dickson, 18 Dickson, 18 div, 7 F p, 6 GDD, 8, 9 grevlex, 21 grlex, 21 I, 13 LC, 6, 22 lex, 21 LM, 6, 22 LT, 6, 22 mod, 7 mod, 23 multideg, 22 N, 6, 16 Nethoer, 19 Noether, 19 PID, 8 /, 7 quotient, 7 remainder, 7, 39 RT, 6, 22 S(, ), 26 S-, 26 V, 11, 13, 11, 7, 22, 7, 3, 1, 6, 5, 16, 9, 1, 30, 12, 17, 10, 30, 19, 5, 24, 20, 1, 8, 39, 19, 8, 21, 21, 21, 17, 3, 16, 16, 3, 7, 22, 7, 22, 4, 4, 4, 5, 25, 17, 4, 17, 19, 17, 2, 16, 2, 5, 5, 10, 6, 1, 39, 4, 4, 6, 6, 4, 8, 21, 20, 21, 2, 11, 18

50 46, 3, 3, 17, 24, 4, 17, 25, 39, 27, 28, 3, 3, 12, 17, 20, 22, 7, 7, 22