{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 256 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 1 24 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 1 12 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 291 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 292 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 297 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 299 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 300 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 302 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 303 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 304 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 305 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 306 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 307 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 308 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 309 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 310 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 311 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 312 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 313 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 314 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 315 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 316 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 317 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 318 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 319 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 320 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 321 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 322 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 323 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 324 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 325 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 326 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 327 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 328 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 329 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 330 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 331 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 332 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 333 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 334 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 335 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 336 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 337 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 338 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 339 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 340 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 341 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 342 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 343 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 344 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 345 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 346 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 347 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 348 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 349 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 350 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 351 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 352 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 353 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 354 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 }{CSTYLE "" -1 355 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 356 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 357 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 358 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 359 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 360 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 361 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 362 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 363 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 364 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 365 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 366 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 367 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 369 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 370 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 372 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 373 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 258 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 259 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 260 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 261 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 262 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 263 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 264 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 265 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 266 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 256 18 "Polynomial Ideals." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 110 "Let F=\{f1,f2,..,fm\} be a finite set of elements of R=Q[x1,x2,.. ,xn]. Then the ideal generated by the set F is:" }}{PARA 0 "" 0 "" {TEXT -1 60 "I = (F) = (f1,f2,...,fm) = \{ a1*f1+..+am*fm | a1..am in \+ R \}." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }{TEXT 257 0 "" }{TEXT 258 53 "Central problem for computing with po lynomial ideals:" }}{PARA 256 "" 0 "" {TEXT -1 113 "Given a finite set F of polynomials F=\{f1,f2,..,fm\} in R=Q[x1,..,xn]. If g in R, how c an we check if g is in (F)?" }}{PARA 257 "" 0 "" {TEXT -1 0 "" }{TEXT 259 15 "Second Problem:" }{TEXT 260 134 " And, if it turns out that g \+ is in (F), in other words: g=a1*f1+...+am*fm for some a1,a2,..,am in R , how then can we find such a1..am?" }{TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 26 "Ideals and radical ideals." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 267 30 "Interpretation of ideal \+ I=(F)." }{TEXT -1 228 " One way to think about this ideal is the foll owing: Think of the polynomials f1,f2,..,fm as equations in the variab les x1,x2,..xn. Then the ideal I is the set of all equations that are \+ follow from the equations f1,f2,..,fm by:" }}{PARA 0 "" 0 "" {TEXT -1 34 "1) multiplication with polynomials" }}{PARA 0 "" 0 "" {TEXT -1 13 "2) additions." }}{PARA 0 "" 0 "" {TEXT -1 60 "So I is the set of all \+ R-linear combinations of f1,f2,..,fm." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 186 "There is one very special equation, \+ namely 1=0. This equation has no solutions. Therefore we see that if 1 is an element of the ideal I, then the system f1=f2=...=fm=0 has no s olutions. " }{TEXT 268 25 "Hilbert's Nullstellensatz" }{TEXT -1 184 " \+ says that the converse is also true, if f1=f2..=fm=0 is not consistent , i.e. there is no solution (x1,x2,..,xn) = (alpha1,alpha2,..,alpha.n) in C^n, then 1 is an element of the ideal." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 252 "Note that when you view f1, f2 ,.., fm as equations (f1=f2=...=fm=0) then there can be equations that can be derived from the equations f1,..,fm but that can not be always obtained by additions and multiplications with polynomials. Namely th e following:" }}{PARA 0 "" 0 "" {TEXT -1 122 "suppose f is an element \+ of the ideal I=(f1,..,fm), and suppose f = g^n for some polynomial g \+ and some positive integer n." }}{PARA 0 "" 0 "" {TEXT -1 283 "Then f1= f2=..=fm=0 implies f=0 because f is in the ideal, but f=0 means g^n=0, from which we can conclude: g=0. It turns out if we include these pol ynomials g as well, then one obtains the set of all polynomials which \+ (viewed as equations) are consequences of the equations f1,..,fm." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 269 12 "Definiti on: " }}{PARA 0 "" 0 "" {TEXT -1 41 "Let f1,f2,..,fm be polynomials. T hen the " }{TEXT 270 14 "radical ideal " }{TEXT -1 92 "of the ideal (F ) is the collection of all polynomials that can be obtained from f1,.. ,fm by:" }}{PARA 0 "" 0 "" {TEXT -1 33 "1) multiplications by polynomi als" }}{PARA 0 "" 0 "" {TEXT -1 13 "2) additions." }}{PARA 0 "" 0 "" {TEXT -1 69 "3) Whenever g^n, n>1 is in our collection, then we includ e g as well." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 111 "So an ideal is closed under operations 1) and 2), and a radica l ideal is closed under operations 1), 2) and 3)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 262 "So the ideal generated b y f1,..,fm (when we think of them as equations) is a set of polynomial s that are consequences of f1=f2=..=fm=0, but where we only do operati ons 1) and 2). The ideal does not always contain all polynomials that \+ are consequences of f1,..fm." }}{PARA 0 "" 0 "" {TEXT -1 17 "But accor ding to " }{TEXT 273 26 "Hilbert's Nullstellensatz," }{TEXT -1 33 " th e radical ideal is the set of " }{TEXT 271 3 "all" }{TEXT -1 32 " cons equences of f1=f2=..=fm=0. " }{TEXT 272 25 "Hilbert's Nullstellensatz " }{TEXT -1 11 " says that:" }}{PARA 0 "" 0 "" {TEXT -1 119 "g is in t he radical ideal if and only if g(alpha1,..,alpha.n)=0 for all solutio ns (alpha.1,.,alpha.n) of f1=f2=..=fm=0." }}{PARA 0 "" 0 "" {TEXT -1 146 "In other words: If f1,..,fm and g are in R, then from f1=f2=..=fm =0 we may conclude that g=0 if and only if g is in the radical ideal o f f1,..,fm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 328 11 "Definition:" }}{PARA 0 "" 0 "" {TEXT -1 88 "Let R be a ring. A n ascending chain of ideals is a finite or infinite sequence of ideals " }}{PARA 0 "" 0 "" {TEXT -1 33 "I1, I2,...I.n or I1, I2, I3, ..." }} {PARA 0 "" 0 "" {TEXT -1 10 "such that " }{TEXT 329 33 "I.i is a prope r subset of I.(i+1)" }{TEXT -1 12 " for each i." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 331 11 "Definition:" }}{PARA 0 " " 0 "" {TEXT -1 12 "R is called " }{TEXT 332 10 "Noetherian" }{TEXT -1 53 " when R has no infinitely ascending chains of ideals." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "Let I1, I2, ... be ideals in R, and suppose that " }{TEXT 330 26 "I.i is a subset of \+ I.(i+1)" }{TEXT -1 91 " for each i. If R is Noetherian then there must exist an n such that I.n = I.m for all m>n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 333 9 "Examples:" }}{PARA 0 "" 0 "" {TEXT -1 35 "Q[x] and Z and Z[x] are Noetherian." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 334 12 "Proposition:" }}{PARA 0 "" 0 "" {TEXT -1 74 "A ring R is Noetherian if and only if every ideal I is finitely generated." }}{PARA 0 "" 0 "" {TEXT -1 98 "This means t hat for every ideal I, there exists a finite subset F=\{f1,..,fm\} of \+ R such that I=(F)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 335 6 "Proo f:" }}{PARA 0 "" 0 "" {TEXT -1 32 "Let I be an ideal, and let F=\{\}. " }}{PARA 0 "" 0 "" {TEXT -1 111 "As long as (F) is a proper subset of I, take an element of I but not in (F), and put that element in the s et F." }}{PARA 0 "" 0 "" {TEXT -1 258 "This way, the ideals (F) we enc ounter form an ascending sequence, and when R is Noetherian this seque nce must be finite. Hence we find a finite set F such that I=(F), so I is finitely generated. I will leave the proof of the converse stateme nt to the reader." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 336 24 "Hilbert's basis theorem:" }}{PARA 0 "" 0 "" {TEXT -1 35 "If R is Noetherian then so is R[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 337 121 "Corollary: Q[x1,x2,..,xn] is Noetheri an, so for every ideal I in Q[x1,..,xn] there exists a finite set F su ch that I=(F)." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 48 "Solution to th e Central Problem: Groebner basis." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 654 "It turns out that when the central probl em can be handled, then we can find a method to compute answers to *ma ny* (it almost seems: pretty much all) computational problems involvin g polynomial equations or polynomial ideals. An example of such comput ational problem is the following, given polynomials f1,..,fm, the prob lem is: \"are the equations f1=0, f2=0,..,fm=0 consistent, in other wo rds, does a common solution exist?\". It is consistent if and only if 1 is not an element of the ideal (F), and so we see that this problem is reduced to the central problem. Later we will also look at many ot her problems that can be reduced to the central problem." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "The method of solv ing the central problem is to compute a " }{TEXT 274 17 "Groebner basi s G " }{TEXT -1 19 "of the ideal I=(F)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 275 19 "Partial Definition:" }{TEXT -1 91 " A Groebner basis G of an ideal I is a finite set of polynomials G=\{g 1,g2,..,gk\} such that:" }}{PARA 0 "" 0 "" {TEXT -1 32 " 1) G spans th e ideal, so I=(G)." }}{PARA 0 "" 0 "" {TEXT -1 124 " 2) G has some add itional property (which will be defined later) that will make it easy \+ to answer the central problem above." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "Note: the Groebner basis spans the idea l generated by f1,..,fm, not the radical ideal." }}}{SECT 1 {PARA 3 " " 0 "" {TEXT -1 33 "Two easy cases of Groebner bases." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 30 "We'll do two easy case s first:" }}{PARA 0 "" 0 "" {TEXT 261 13 "Easy case 1):" }{TEXT -1 36 " n=1, so we have only one variable." }}{PARA 0 "" 0 "" {TEXT 262 12 "Easy case 2)" }{TEXT -1 95 ": n>1, but now degree(f.i, \{x1,x2,..,xn \})=1 for all f.i, so all f.i are linear in x1,x2,..,xn." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 11 "First easy " } {TEXT 265 6 "case 1" }{TEXT -1 162 ", so there is only one variable x1 (lets just take x). We know we only have to do the gcd of the polynom ials f1..fm, which we can do with the following algorithm:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1002 "case1:=proc(F::set, x::name)\n l ocal G,G_old,i,j,li,lj,k;\n G:=F minus \{0\};\n while G<>G_old do\n \+ G_old:=G;\n for i in G do for j in G minus \{i\} do\n li:=l eading_monomial_case1(i,x);\n lj:=leading_monomial_case1(j,x);\n \+ if type(li/lj, polynom) then\n # The leading monomial of \+ i is divisible by\n # the leading monomial of j, so we can red uce\n # i modulo j.\n # We will compute k, such that i and k are\n # the same modulo j, in such a way that k\n \+ # has a smaller leading monomial than i\n # (i.e. it has lo wer degree).\n k := i - li/lj * j;\n k := primpart(k); \n # Since i and k are the same modulo j,\n # and j in G minus \{i\},\n # the ideal will not change if we replace\n \+ # i by k as follows:\n G := ((G minus \{i\}) union \{k \}) minus \{0\}\n # Now we've made a leading monomial in G sma ller,\n # and eventually this process will end.\n fi\n \+ od od\n od;\n G\nend; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&c ase1GR6$'%\"FG%$setG'%\"xG%%nameG6)%\"GG%&G_oldG%\"iG%\"jG%#liG%#ljG% \"kG6\"F5C%>8$-%&minusG6$9$<#\"\"!?(F5\"\"\"F@F50F88%C$>FBF8?&8&F8%%tr ueG?&8'-F:6$F8<#FFFGC%>8(-%7leading_monomial_case1G6$FF9%>8)-FQ6$FIFS@ $-%%typeG6$*&FO\"\"\"FU!\"\"%(polynomGC%>8*,&FFF@*&*&FOF@FIF@FgnFUFhn! \"\">F\\o-%)primpartG6#F\\o>F8-F:6$-%&unionG6$FJ<#F\\oF=F8F5F5F5" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 100 "leading_monomial_case1:=pro c(F,x)\n # Compute the highest term.\n lcoeff(F,x) * x^degree(F,x) \nend;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%7leading_monomial_case1GR6 $%\"FG%\"xG6\"F)F)*&-%'lcoeffG6$9$9%\"\"\")F/-%'degreeGF-F0F)F)F)" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 260 "Of course, the only thing that al gorithm case1 does is computing the gcd of f1,f2,...,fm. So we could h ave done a simpler implementation using Maple's gcd implementation. Ho wever, note the similarities with the implementation of case 2 later i n this worksheet." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "f1 , f 2, f3 := x^6-x^3,x^8-x^3,x^12-x^7;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >6%%#f1G%#f2G%#f3G6%,&*$)%\"xG\"\"'\"\"\"\"\"\"*$)F,\"\"$F.!\"\",&*$)F ,\"\")F.F/F0F3,&*$)F,\"#7F.F/*$)F,\"\"(F.F3" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "F:=\{f1,f2,f3\};" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%\"FG<%,&*$)%\"xG\"\"'\"\"\"\"\"\"*$)F)\"\"$F+!\"\",&*$)F)\"\")F+F, F-F0,&*$)F)\"#7F+F,*$)F)\"\"(F+F0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "G:=case1(F ,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"GG<#,&*$)%\"xG\"\"$\"\"\"!\"\"*$)F)\"\"%F+\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "G:= \{ expand(gcd(gcd(f1,f2), f3)) \};" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG<#,&*$)%\"xG\"\"$\"\"\"!\"\"*$)F )\"\"%F+\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "Using this Groe bner basis G, the solution to the central problem is now the following :" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 82 "g in (F) <---> g in (G) <----> the remainder of g modulo the element in G \+ is zero." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "g:=x^7+x^8;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,&*$)%\"xG\"\"(\"\"\"\"\"\"*$)F( \"\")F*F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "rem(g,G[1],x); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$*$)%\"xG\"\"$\"\"\"\"\"#" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 29 "Not zero, so g is not in (F)." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "g:=x^15-2*x^13+x^11;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,(*$)%\"xG\"#:\"\"\"\"\"\"*$)F( \"#8F*!\"#*$)F(\"#6F*F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 " rem(g,G[1],x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 26 "zero, so this g is in (F)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 18 "Now we'll look at " }{TEXT 266 7 "case 2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 815 "case2:=proc(F::set, list_vars::lis t(name))\n local G,G_old,i,j,li,lj,k;\n G:=F minus \{0\};\n while G <>G_old do\n G_old:=G;\n for i in G do for j in G minus \{i\} do \n li:=leading_monomial_case2(i,list_vars);\n lj:=leading_mo nomial_case2(j,list_vars);\n if type(li/lj, polynom) then\n \+ # The leading monomial of i is divisible by\n # the leading monomial of j, so we can reduce\n # i modulo j.\n #\n # Compute k = i modulo j.\n # Then: replace i by k, w hich has a \"smaller\"\n # leading monomial. This process will end,\n # we're making leading monomials\n # smaller a nd smaller until we can reduce\n # them no more.\n k : = i - li/lj * j;\n G := ((G minus \{i\}) union \{k\}) minus \{ 0\}\n fi\n od od\n od;\n G\nend; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&case2GR6$'%\"FG%$setG'%*list_varsG-%%listG6#%%nameG6 )%\"GG%&G_oldG%\"iG%\"jG%#liG%#ljG%\"kG6\"F8C%>8$-%&minusG6$9$<#\"\"!? (F8\"\"\"FCF80F;8%C$>FEF;?&8&F;%%trueG?&8'-F=6$F;<#FIFJC%>8(-%7leading _monomial_case2G6$FI9%>8)-FT6$FLFV@$-%%typeG6$*&FR\"\"\"FX!\"\"%(polyn omGC$>8*,&FIFC*&*&FRFCFLFCFjnFXF[o!\"\">F;-F=6$-%&unionG6$FM<#F_oF@F;F 8F8F8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 591 "leading_monomial_ case2:=proc(f, list_vars)\n # Assumption: f is linear in the variabl es.\n # What is the leading monomial, the highest\n # monomial? To decide this, we simply pick\n # some ordering on the monomials that can\n # occur, say: x1 > x2 > ..\n # So, if has(f,x1) then x1 (ti mes its coefficient)\n # is the leading monomial. If it doesn't have x1, but\n # it has x2, then the leading monomial is a constant\n \+ # times x2, etc. So we get the following algorithm:\n local x;\n f or x in list_vars do\n if has(f,x) then\n RETURN(coeff( f,x)*x)\n fi\n od\nend;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%7l eading_monomial_case2GR6$%\"fG%*list_varsG6#%\"xG6\"F+?&8$9%%%trueG@$- %$hasG6$9$F--%'RETURNG6#*&-%&coeffGF3\"\"\"F-F;F+F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "f1:=x1+2*x2+3*x3+4*x4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,*%#x1G\"\"\"%#x2G\"\"#%#x3G\"\"$%#x4G\" \"%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "f2:=x1+3*x2+5*x3+7*x 4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f2G,*%#x1G\"\"\"%#x2G\"\"$%#x 3G\"\"&%#x4G\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "f3:=x1 +4*x2+9*x3+16*x4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f3G,*%#x1G\"\" \"%#x2G\"\"%%#x3G\"\"*%#x4G\"#;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "F:=\{f1,f2,f3\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG<%,* %#x1G\"\"\"%#x2G\"\"#%#x3G\"\"$%#x4G\"\"%,*F'F(F)F,F+\"\"&F-\"\"(,*F'F (F)F.F+\"\"*F-\"#;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "vars: =[x1,x2,x3,x4];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%varsG7&%#x1G%#x2 G%#x3G%#x4G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "G:=case2(F,v ars);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG<%,*%#x1G\"\"\"%#x2G\" \"%%#x3G\"\"*%#x4G\"#;,(F)!\"\"F+!\"%F-!\"*,&F+\"\"#F-\"\"'" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 26 "We see that the algorithm " } {TEXT 264 6 "case2 " }{TEXT -1 87 "has brought the linear equations f1 ,f2,f3 in a form that in linear algebra is called: " }{TEXT 263 21 "u pper triangular form" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 102 " Using this upper triangular form it is now easy to check if a given g \+ is in the ideal (F), as follows." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 40 "Take g1 is the element of G that has x1, " }}{PARA 0 "" 0 "" {TEXT -1 55 "g2 is the element of G that is not g1 , and that has x2," }}{PARA 0 "" 0 "" {TEXT -1 27 "and g3 is the last \+ element." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "if has(G[1],x1) then g1:=G[1] elif has(G[2],x1) then g1:=G[2] else g1:=G[3] fi;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g1G,*%#x1G\"\"\"%#x2G\"\"%%#x3G\"\" *%#x4G\"#;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "GG:=G minus \+ \{g1\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#GGG<$,(%#x2G!\"\"%#x3G! \"%%#x4G!\"*,&F)\"\"#F+\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "if has(GG[1],x2) then g2,g3:=GG[1],GG[2] else g2,g3:=GG[3],GG[2] fi;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$%#g2G%#g3G6$,(%#x2G!\"\"%#x 3G!\"%%#x4G!\"*,&F+\"\"#F-\"\"'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "Now G=\{g1,g2,g3\}.\nTake a polynomial g, and reduce it modulo g1 \+ g2 and g3 using the remainder:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "g:=x1^2+x2^2+x3^2+x4^2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"gG,**$)%#x1G\"\"#\"\"\"\"\"\"*$)%#x2GF)F*F+*$)%#x3GF)F*F+*$)%#x4GF)F *F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "rem(rem( rem(g,g1,x1 ) ,g2,x2), g3,x3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$*$)%#x4G\"\"# \"\"\"\"#?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "Not zero, so g is n ot in the ideal." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 19 "Lets try another g:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "g:=x1^3+x2^3+x3^3+x4^3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,**$)%#x1G\"\"$\"\"\"\"\"\"*$)%#x2GF)F*F+*$)%#x3GF)F*F+*$) %#x4GF)F*F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "rem(rem( rem (g,g1,x1) ,g2,x2), g3,x3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" } }}{PARA 0 "" 0 "" {TEXT -1 75 "So this g is in the ideal, there must e xist polynomials a1,a2,a3 such that:" }}{PARA 0 "" 0 "" {TEXT -1 20 "g =a1*f1+a2*f2+a3*f3." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 39 "What do t hese two cases have in common?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 28 "Now we've treated two cases:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 "case 1) just 1 va riable, but any degree." }}{PARA 0 "" 0 "" {TEXT -1 48 "case 2) any nu mber of variables, but degree = 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 161 "The implementations of case 1 and case 2 were very similar. The main difference was in the procedure leading_m onomial, which was different for case 1 and case 2." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 276 45 "What is the leading mo nomial of a polynomial?" }}{PARA 0 "" 0 "" {TEXT -1 113 "For case 1, t here was an obvious choice as for which monomial is the largest one. F or example, in the polynomial:" }}{PARA 0 "" 0 "" {TEXT -1 29 " 5*x^6 + 3*x^8 + 17*x^2 + 22" }}{PARA 0 "" 0 "" {TEXT -1 83 "the monomial 3* x^8 is the leading monomial, it is the term with the highest degree." }}{PARA 0 "" 0 "" {TEXT -1 79 "For case 2, however, there is no obviou s choice. For example, in the polynomial" }}{PARA 0 "" 0 "" {TEXT -1 20 " 2*x1+3*x2+4*x3+5*x4" }}{PARA 0 "" 0 "" {TEXT -1 48 "it is not cle ar what the \"largest\" monomial is. " }{TEXT 277 82 "To decide which \+ monomial we think of as the largest, we need to choose an ordering" } {TEXT -1 549 ". We picked the ordering x1>x2>x3>x4, making 2*x1 the le ading monomial. Of course, we could have chosen another ordering (say: x3>x2>x4>x1, making 4*x3 the leading monomial), and we would be able \+ to do the \"Central Problem\" just as well. So another ordering would \+ have been just fine, as long as we consistently use the same ordering \+ of course. In the algorithm leading_monomial_case2 we can order the va riables in any way we want to, but we have to use the same ordering ev ery time because otherwise the algorithm case2 will probably not work. So: " }{TEXT 278 68 "there are many different orderings, we'll have t o choose an ordering" }{TEXT -1 113 " (but once it is chosen, we'll ha ve to keep using the same ordering throughout all computations that we will do)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 129 "In the general case, i.e. not case 1 and case 2, we will see t hat we again need an ordering on the monomials. Given a polynomial:" } }{PARA 0 "" 0 "" {TEXT -1 14 "x1*x2 + 3*x3^5" }}{PARA 0 "" 0 "" {TEXT -1 550 "it makes a priori no sense to say which of the two monomials i s the largest one. We would first have to define some ordering on thes e monomials, and only then can we say which one is the largest. Once w e've decided which ordering to use, then the strategy will be to pick \+ elements i,j in the set G like in the algorithms case1 and case2, then we look at the leading monomials of i and j, and if lj=leading_monomi al(j) divides li=leading_monomial(i) (so when li/lj is a polynomial) t hen we can make the leading monomial of i smaller by replacing i by:" }}{PARA 0 "" 0 "" {TEXT -1 21 "i - li/lj * j (***)" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 115 "So: Once we have chose n an ordering, from that moment on it makes sense to say which is the \+ largest monomial, the l" }{TEXT 279 16 "eading monomial," }{TEXT -1 293 " of a polynomial. Given a set of polynomials G=\{g1,g2,..\}, note : initially in the algorithm G is the set F=\{f1,f2,..\}, we can try t o make an element i of G \"smaller\" by substracting a suitable multip le of another element j of G, like in equation (***). If i'=i-li/lj * \+ j then we will say that " }{TEXT 281 27 "i reduces to i' w.r.t. j. " }{TEXT -1 236 "When we replace i by i' in G, we see that G still span s the same ideal, but now one of the elements of G has become \"smalle r\". Note that the meaning of \"smaller\" here depends on the choice w e made for the ordering. We will say that we " }{TEXT 280 16 "reduce t he set G" }{TEXT -1 256 " when we reduce an i element of G w.r.t. anot her element j of G. When we can reduce the set G no further (so when t here are no two elements i<>j in G such that the leading monomial of j divides the leading monomial of i) then we will say that the set G is " }{TEXT 282 8 "reduced." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 297 "Notice that our implementations case1 and case2 s tart with the set G=F, and then continue to reduce elements of G until nothing can be reduced any further. So the only thing our algorithms \+ case1 and case2 do is to compute a reduced set, and we see that the im plementations are indeed very similar." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 458 "For these two easy cases, a reduced \+ set is automatically a Groebner basis. This means that for case 1 and \+ case 2, once we have a reduced set, the central problem can easily be \+ answered. For the more general case, this is no longer true. We will s ee that the algorithm for computing a reduced set is still pretty much the same as case1 and case2, however, computing a reduced set will no t be sufficient for handling the central problem, we'll have to do mor e." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 451 "No tice that the Maple procedure for computing the leading monomial of a \+ polynomial is called leadmon. The input of this procedure must be not \+ only the polynomial, but the ordering as well, since the leading monom ial depends on that ordering. To use this function, first type with(G roebner), in order to load the Groebner package. In the book the leadi ng monomial is called the initial, but in this worksheet I'll use the \+ same terminology as in Maple." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 23 "Orderings on monomials." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 22 "If 7*x1^3*x2^5 is the " }{TEXT 283 16 "leading mon omial" }{TEXT -1 88 " of some polynomial, then we will call the coeffi cient (which is 7 in this example) the " }{TEXT 284 19 "leading coeffi cient" }{TEXT -1 23 ", and x1^3*x2^5 is the " }{TEXT 285 23 "leading p ower product. " }{TEXT -1 20 "The Maple procedure " }{TEXT 286 7 "lead mon" }{TEXT -1 8 " in the " }{TEXT 287 16 "Groebner package" }{TEXT -1 296 " takes as input: a polynomial and an ordering. The output is a sequence consisting of the leading coefficient and the leading power \+ product. In the ordering of monomials such as 7*x1^3*x2^5 we will only consider the leading power product x1^3*x2^5, and not the correspondi ng non-zero coefficient." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 103 "If we have n variables, x1,..,xn, then the set of all possible power products is denoted by [x1,..,xn]:" }}{PARA 0 "" 0 "" {TEXT 288 12 "Definition: " }{TEXT -1 73 "[x1,..,xn] = \{x1^i1 *. .* xn^in, where i1,..,in are nonnegative integers\}." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 136 "Notice that in this no tation Q[x1,..,xn] is an infinite dimensional Q-vector space with basi s [x1,..,xn]=\{1,x1,x2,..xn,x1^2,x1*x2,....\}." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 289 10 "Notation: " }{TEXT -1 15 "We will denote " }{TEXT 295 12 "x1,x2,..,xn " }{TEXT -1 3 "as " } {TEXT 296 1 "X" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 3 "So " } {TEXT 297 4 "Q[X]" }{TEXT -1 12 " stands for " }{TEXT 298 14 "Q[x1,x2, ..,xn]" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 4 "And " }{TEXT 299 3 "[X]" }{TEXT -1 56 " stands for the set of all power products in x1,x2,..xn." }}{PARA 0 "" 0 "" {TEXT -1 22 "If e is an element of " } {TEXT 300 3 "N^n" }{TEXT -1 52 ", where N is the set of non-negative i ntegers, then " }{TEXT 301 16 "e=(e1,e2,..,en) " }{TEXT -1 62 "where t he e.i are integers. Then we will denote the monomial: " }{TEXT 293 21 "x1^e1*x2^e2*...*xn^en" }{TEXT -1 19 " more briefly as: " }{TEXT 294 3 "X^e" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 131 "Notice that [X] is a commutative monoid (that ju st means that we can multiply elements of [X] and the result will agai n be in [X])." }}{PARA 0 "" 0 "" {TEXT -1 95 "The map e -> X^e is an i somorphism of the additive monoid N^n to the multiplicative monoid [X] ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 290 10 "Def inition" }{TEXT -1 36 ": An ordering < on [X] is called an " }{TEXT 291 19 "admissible ordering" }{TEXT -1 6 " when:" }}{PARA 0 "" 0 "" {TEXT -1 58 "1) The element 1 in [X] is smaller than any other element ." }}{PARA 0 "" 0 "" {TEXT -1 49 "2) If s < t, then s*u < t*u for all \+ s,t,u in [X]." }}{PARA 0 "" 0 "" {TEXT -1 129 "3) < is a complete orde ring, which means that if s,t in [X], then precisely one of the follow ing three holds: sX^e) to orderings on [X]." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT 292 39 "Three examples of admissible orderin gs:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 6 "p ure l" }{TEXT 302 22 "exicographic ordering:" }}{PARA 259 "" 0 "" {TEXT 303 33 "Maple notation: plex(x1,x2,..,xn)" }}{PARA 0 "" 0 "" {TEXT -1 65 "If d=(d1,d2,..,dn) and e=(e1,e2,..,en) then we say that d e.i, and if then d.i < e.i then d is the smallest, otherwise e is the smallest." }}{PARA 0 "" 0 "" {TEXT -1 36 "In the pure lexicogr aphic ordering " }{TEXT 306 17 "plex(x1,x2,..,xn)" }{TEXT -1 10 " one has: " }{TEXT 305 12 "x1>x2>...>xn" }{TEXT -1 11 ", and even:" }} {PARA 0 "" 0 "" {TEXT 304 51 " x1 is bigger than any element of [x2, x3,...,xn]." }}{PARA 0 "" 0 "" {TEXT 307 55 " x2 is bigger than any e lement of [x3,x4,..,xn], etc." }}{PARA 0 "" 0 "" {TEXT 310 9 "Example : " }{TEXT -1 471 "in the polynomial 3*x3^12 + 2*x1^2 - 4*x1*x2^4 + 9 *x2*x3, under the plex(x1,x2,x3) ordering, the leading monomial is: 2* x1^2. The second largest monomial is -4*x1*x2^4, the third largest is \+ 9*x2*x3 and the smallest monomial is 3*x3^12. So this is like the orde ring in the dictionary, when you compare two words in the alphabetical ordering, then you at the first letter of each word. The other letter s will only play a role if the first letter is the same in both words. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 308 22 "Tota l degree ordering:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 309 33 "Map le notation: tdeg(x1,x2,..,xn)" }}{PARA 0 "" 0 "" {TEXT -1 199 "If d=( d1,d2,..,dn) and e=(e1,e2,..,en), then we say that the degree of the m onomial X^e=x1^e1*...*xn^en (or the \"total degree\") equals e1+e2+.. .+en. A total degree ordering is an ordering such that:" }}{PARA 0 "" 0 "" {TEXT -1 34 "If d1+..+dn < e1+...+en then d1 then there exist infinitely many (even: uncountably many) different admissible o rderings on [X]. To see more examples of admissible orderings type ?Gr oebner,termorder in Maple." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 60 "Re ducing a set of polynomials w.r.t. an admissible ordering." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 143 "In the two easy \+ cases, we started with a set F=\{f1,f2,...,fm\} of polynomials in Q[X] =Q[x1,x2,..,xn]. To reduce the set F, we did the following:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 40 "Start with G=F \+ and throw away the zeros." }}{PARA 0 "" 0 "" {TEXT -1 266 "Then: whene ver you have two different elements i and j in G, and if the leading t erm lj of j divides the leading term li of i, then we replace i by the reduction of i w.r.t. j, which was i-li/lj * j. Keep doing this proce ss until we can not reduce any more elements." }}{PARA 0 "" 0 "" {TEXT -1 64 "To decide what the leading term was, we had to pick an or dering." }}{PARA 0 "" 0 "" {TEXT -1 87 "In case 1), the only monomials where powers of x, which we ordered by: 1x2>...>xn." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 103 "In the general case, we will have to choose an orderin g. Let's take for example the following ordering:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "with(Groebner): # Load the Groebner package. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 93 "ord:=lexdeg([x1,x2],[x3 ]); # we'll use this ordening, but we can also choose other ordenings. " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$ordG-%'lexdegG6$7$%#x1G%#x2G7#% #x3G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 631 "Now we will take a set F of polynomials, and we will take the number of variables n to be >1, \+ and we will also have degrees that are >1. Then, as long as we can fin d elements i<>j in F such that the leading monomial lj of j divides th e leading monomial li of i, we will replace i by the reduction of i w. r.t. j, which is: i-li/lj*j. Since the leading monomial of li/lj * j i s the same as the leading monomial of i, the leading monomial has beco me smaller this way. So the leading monomials will get smaller and sma ller during the computation in the following algorithm. Note the simil arity with the implementations case1 and case2." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 993 "reduce_polynomials:=proc(F,ord)\n local G,G_ old,i,j,li,lj,k;\n G:=F minus \{0\};\n while G<>G_old do\n G_old: =G;\n for i in G do for j in G minus \{i\} do\n li:=Groebner[l eadmon](i,ord);\n lj:=Groebner[leadmon](j,ord);\n if type(li [2]/lj[2], polynom) then\n # The leading monomial of i is divi sible by\n # the leading monomial of j, so we can reduce\n \+ # i modulo j.\n # We will compute k, such that i and k ar e\n # the same modulo j, in such a way that k\n # has \+ a smaller leading monomial than i\n k := i - li[1]/lj[1] * li[ 2]/lj[2] * j;\n k := primpart(k);\n # Since i and k ar e the same modulo j,\n # and j in G minus \{i\},\n # t he ideal will not change if we replace\n # i by k as follows: \n G := ((G minus \{i\}) union \{k\}) minus \{0\}\n # \+ Now we've made a leading monomial in G smaller,\n # and eventu ally this process will end (why?...)\n fi\n od od\n od;\n G \nend; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%3reduce_polynomialsGR6$ %\"FG%$ordG6)%\"GG%&G_oldG%\"iG%\"jG%#liG%#ljG%\"kG6\"F1C%>8$-%&minusG 6$9$<#\"\"!?(F1\"\"\"FF>F4?&8&F4%%trueG?&8'-F66$F4<#FBFCC%> 8(-&%)GroebnerG6#%(leadmonG6$FB9%>8)-FM6$FEFR@$-%%typeG6$*&&FK6#\"\"# \"\"\"&FTFgn!\"\"%(polynomGC%>8*,&FBF<*&*(&FK6#FF_o-%)primpartG6#F_o>F4-F66$-%&unionG6$FF<#F_ oF9F4F1F1F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "F:=\{x1^2+2* x2^2+3*x3^2, x1*x2*x3-1, x1+x2+x3-1\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG<%,(*$)%#x1G\"\"#\"\"\"\"\"\"*$)%#x2GF*F+F**$)%#x3GF*F+\" \"$,*F)F,F/F,F2F,!\"\"F,,&*(F)F,F/F,F2F,F,F5F," }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 47 "G:=reduce_polynomials(F,ord); # The reduced se t" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG<%,.*$)%#x1G\"\"#\"\"\"\"\" $*$)%#x3GF*F+F,*&%#x2G\"\"\"F/F2!\"#F1F**&F)F2F/F+F*F)F3,*F)F2F1F2F/F2 !\"\"F2,.!\"$F2*$)F/F,F+\"\"&*&F)F+F.F+F2F4F6F-!\"%F/F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "GB:=gbasis(F,ord); # The Groebner b asis." }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#GBG7&,.!\"*\"\"\"*$)%#x3G \"\"$\"\"\"\"#:*$)F+\"\"#F-!#>F+!\"\"*$)F+\"\"&F-\"#?*$)F+\"\"%F-!\"', *%#x1GF(%#x2GF(F+F(F3F(,.F8!#?F)\"\"'F=!\"$*&F=F(F+F(F,F+\"\"(FDF(,.*$ )F=F1F-\"\"*F8\"#!)F)!#CF/F.F+!#S!#AF(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "g:=op( select(i -> not has(i,\{x1,x2\}), GB) );" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,.!\"*\"\"\"*$)%#x3G\"\"$\"\"\" \"#:*$)F*\"\"#F,!#>F*!\"\"*$)F*\"\"&F,\"#?*$)F*\"\"%F,!\"'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 108 "The set F spans the same ideal as our re duced set G, and the Groebner basis GB also spans the same ideal, so" }}{PARA 0 "" 0 "" {TEXT -1 13 "(F)=(G)=(GB)." }}{PARA 0 "" 0 "" {TEXT -1 336 "The polynomial g is an element of (F), and, given the set F, t hat is hard to tell. Given the set G, it is still hard to see whether \+ g is an element of the ideal (F) or not. Therefore, simply reducing a \+ set like we did in the algorithm above is not sufficient to handle the central problem. Our reduced set G is not yet a Groebner basis." }}}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 29 "Definition of Groebner basis." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 188 "We have \+ seen that, given a polynomial, we can reduce it modulo other polynomia ls, by operations like: replace i by its reduction i-li/lj * j. This c an be done with the following algorithm:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 516 "reduce_poly:=proc(f,polys,ord)\n local i,j,i_old,li ,lj,k;\n i:=f;\n while i_old<>i do\n i_old:=i;\n li:=Groebne r[leadmon](i,ord);\n for j in polys do\n lj:=Groebner[leadmon ](j,ord);\n if i=0 then\n RETURN(0)\n elif type(li[2 ]/lj[2], polynom) then\n # The leading monomial of i is divisi ble by\n # the leading monomial of j, so we can reduce\n \+ # i modulo j.\n k := i - li[1]/lj[1] * li[2]/lj[2] * j;\n \+ i := primpart(k);\n fi\n od\n od;\n i\nend; " }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%,reduce_polyGR6%%\"fG%&polysG%$ordG6 (%\"iG%\"jG%&i_oldG%#liG%#ljG%\"kG6\"F1C%>8$9$?(F1\"\"\"F7F108&F4C%>F9 F4>8'-&%)GroebnerG6#%(leadmonG6$F49&?&8%9%%%trueGC$>8(-F?6$FFFD@&/F4\" \"!-%'RETURNG6#FP-%%typeG6$*&&F=6#\"\"#\"\"\"&FKFY!\"\"%(polynomGC$>8) ,&F4F7*&*(&F=6#F7F7FXF7FFF7Fen*&&FKF`o\"\"\"Ffn\"\"\"Fgn!\"\">F4-%)pri mpartG6#F[oF4F1F1F1" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "Note that \+ the previous algorithm reduce_polynomials is now the same as:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 222 "reduce_polynomials:=proc(F, ord)\n local i,G,k;\n G:=F minus \{0\};\n for i in G do\n k:=re duce_poly(i, G minus \{i\}, ord);\n if k<>i then\n RETURN( procname((G minus \{i\}) union \{k\}, ord))\n fi\n od;\n G\nend; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%3reduce_polynomialsGR6$%\"FG% $ordG6%%\"iG%\"GG%\"kG6\"F-C%>8%-%&minusG6$9$<#\"\"!?&8$F0%%trueGC$>8& -%,reduce_polyG6%F8-F26$F0<#F89%@$0F " 0 "" {MPLTEXT 1 0 2 "F;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#<%,(*$)%#x1G\"\"#\"\"\"\"\"\"*$)%#x2GF (F)F(*$)%#x3GF(F)\"\"$,*F'F*F-F*F0F*!\"\"F*,&*(F'F*F-F*F0F*F*F3F*" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "G:=reduce_polynomials(F,ord) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG<%,.*$)%#x1G\"\"#\"\"\"\"\" $*$)%#x3GF*F+F,*&%#x2G\"\"\"F/F2!\"#F1F**&F)F2F/F+F*F)F3,*F)F2F1F2F/F2 !\"\"F2,.!\"$F2*$)F/F,F+\"\"&*&F)F+F.F+F2F4F6F-!\"%F/F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "g; # Note that g was in the ideal I =(F)=(G)=(GB)." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,.!\"*\"\"\"*$)%#x3G \"\"$\"\"\"\"#:*$)F(\"\"#F*!#>F(!\"\"*$)F(\"\"&F*\"#?*$)F(\"\"%F*!\"' " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "reduce_poly(g,G,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,.!\"*\"\"\"*$)%#x3G\"\"$\"\"\"\"#:* $)F(\"\"#F*!#>F(!\"\"*$)F(\"\"&F*\"#?*$)F(\"\"%F*!\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "GB;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7&,.!\"*\"\"\"*$)%#x3G\"\"$\"\"\"\"#:*$)F)\"\"#F+!#>F)!\"\"*$)F)\" \"&F+\"#?*$)F)\"\"%F+!\"',*%#x1GF&%#x2GF&F)F&F1F&,.F6!#?F'\"\"'F;!\"$* &F;F&F)F&F*F)\"\"(FBF&,.*$)F;F/F+\"\"*F6\"#!)F'!#CF-F,F)!#S!#AF&" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "reduce_poly(g,GB,ord);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 90 "The procedure reduce_poly is implemented in Maple in the \+ Groebner package, under the name " }{TEXT 313 7 "reduce." }}{PARA 0 " " 0 "" {TEXT -1 152 "To use this function reduce, we first have to loa d the Groebner package with the command with(Groebner), which we alrea dy did earlier in this worksheet." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "reduce(g,G,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#, .!\"*\"\"\"*$)%#x3G\"\"$\"\"\"\"#:*$)F(\"\"#F*!#>F(!\"\"*$)F(\"\"&F*\" #?*$)F(\"\"%F*!\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "reduc e(g,GB,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 262 "" 0 "" {TEXT 319 11 "Definition:" }{TEXT -1 27 " Let I be a n ideal and let " }{TEXT 315 3 "ord" }{TEXT -1 57 " be an ordering. Th en a set of polynomials G is called a " }{TEXT 314 15 "Groebner basis \+ " }{TEXT -1 37 "for the ideal I w.r.t. this ordering " }{TEXT 317 4 "o rd " }{TEXT -1 5 "when:" }}{PARA 263 "" 0 "" {TEXT 316 37 "For every p olynomial g in R, one has:" }}{PARA 264 "" 0 "" {TEXT 318 57 "reduce(g , G, ord) = 0 if and only if g is in the ideal I." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 110 "In the above computation , we had I=(F), and ord was some elimination ordering. As we see from \+ the definition, " }{TEXT 341 53 "the set G that we computed was not a \+ Groebner basis. " }{TEXT -1 117 "The set GB is a Groebner basis. So th e gbasis command in the Groebner package does more than just reduce_po lynomials." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 34 "You may wonder why the procedures " }{TEXT 320 18 "reduce_polyn omials" }{TEXT -1 5 " and " }{TEXT 321 11 "reduce_poly" }{TEXT -1 33 " (which does exactly the same as " }{TEXT 322 6 "reduce" }{TEXT -1 56 " in the Groebner package) terminate. What the procedure " }{TEXT 323 6 "reduce" }{TEXT -1 23 " does is the following:" }}{PARA 0 "" 0 "" {TEXT -1 21 "given one polynomial " }{TEXT 324 2 "f," }{TEXT -1 11 " a nd a set " }{TEXT 325 4 "poly" }{TEXT -1 166 "s of some other polynomi als, it will reduce f by substracting multiples of the other polynomia ls from f. During each step, one of the following two things can happe n:" }}{PARA 0 "" 0 "" {TEXT -1 22 "1) f becomes zero, or:" }}{PARA 0 " " 0 "" {TEXT -1 45 "2) the leading monomial of f becomes smaller." }} {PARA 0 "" 0 "" {TEXT -1 110 "Let l1, l2, l3,... be the sequence of le ading monomials of f that occur during this algorithm. So we see that: " }}{PARA 0 "" 0 "" {TEXT -1 18 "l1 > l2 > l3 > ..." }}{PARA 0 "" 0 " " {TEXT -1 68 "Now the algorithm reduce terminates because of the foll owing result:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 327 11 "Definition:" }{TEXT -1 109 " A well-ordering is an order ing for which an infinite decreasing sequence l1 > l2 > l3 > ... does not exist." }}{PARA 0 "" 0 "" {TEXT 326 11 "Proposition" }{TEXT -1 60 ": if < is an admissible ordering, then < is a well-ordering." }} {PARA 0 "" 0 "" {TEXT 338 6 "Proof:" }}{PARA 0 "" 0 "" {TEXT -1 342 "I f < is an admissible ordering, then l1 > l2 implies that l2 does not d ivide l1. Therefore, the ideal (l1) is a proper subset of the ideal (l 1,l2). And likewise, the ideal (l1,l2) is a proper subset of the ideal (l1,l2,l3). Because these are ideals in a Noetherian ring, it follows that the sequence l1 > l2 > ... must be finite, it must end." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 281 "If we wo uld allow any ordering then the reduction need not terminate. For exam ple, if we had the ordering 1 > x > x^2 > x^3 > ..., which is not a we ll-ordering, and if we tried to reduce f=x modulo x^2-x, then x would \+ reduce to x^2, which reduces to x^3, which reduces to x^4, etc." }} {PARA 0 "" 0 "" {TEXT -1 16 "So we see that: " }{TEXT 339 80 "in order for the reduction process to terminate, we need to use a well-ordenin g." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 351 "We always use an admissible ordering, so the proposition tells us that t he algorithm reduce_poly will terminate. The algorithm reduce_polynomi als terminates as well. Note though that in the proof we only showed t hat a sequence l1>l2>... must end, but our proof gives us no indicatio n whatsoever in how long such a sequence could be. As a consequence, \+ " }{TEXT 340 143 "although we have proven that the reduction process e nds, the proof gives us no method to find an upper bound for the numbe r of reduction steps." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 163 "Upper bounds (note that these will depend on the orde ring that you use) do exist, but they tend to be very large. And indee d, the reduction can take quite a while." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 344 7 "Remark:" }{TEXT -1 100 " If G is a finite set of polynomials, and g is a polynomial, and ord is an admis sible ordering then:" }}{PARA 0 "" 0 "" {TEXT 345 66 "The output of re duce(g, G, ord) is not always uniquely determined." }}{PARA 0 "" 0 "" {TEXT -1 179 "Why: well, when G=\{f1,f2,..,fm\} then you have a choice in the reduction process, namely: which of the f.i do you use first, \+ which do you use second, etcetera. Also: the output of " }{TEXT 346 18 "reduce_polynomials" }{TEXT -1 166 " is not uniquely determined. If you do a computation, and you restart Maple, and apply the algorithm \+ on the same input you might get a different answer. In the loop: " } {TEXT 347 21 "for i in G do ... od " }{TEXT -1 187 "the variable i wil l take as values the elements f1,f2,..,fm in the set G, but you don't \+ know in which order that happens because G is a set. And the final res ult can depend on that order." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 89 "In Maple there are two commands that redu ce a polynomial g modulo a set of polynomials G." }}{PARA 0 "" 0 "" {TEXT -1 3 "1) " }{TEXT 348 6 "reduce" }{TEXT -1 36 " This procedure k eeps on reducing g " }{TEXT 350 10 "until the " }{TEXT -1 1 "l" } {TEXT 351 47 "eading monomial of g can not be further reduced" }{TEXT -1 50 ". It is the same as reduce_poly in this worksheet." }}{PARA 0 " " 0 "" {TEXT -1 3 "2) " }{TEXT 349 8 "normalf " }{TEXT -1 35 "This pro cedure keeps on reducing g " }{TEXT 352 52 "until none of the terms of g can be further reduced." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 85 "From the definition, we see that G is a Groebner \+ basis of the ideal I if and only if:" }}{PARA 0 "" 0 "" {TEXT -1 42 "g in I if and only if reduce(g, G, ord)=0." }}{PARA 0 "" 0 "" {TEXT -1 124 "So, when G is a Groebner basis, then the output of reduce(g, G, o rd) is uniquely determined for all g in I, the output is 0." }}{PARA 0 "" 0 "" {TEXT 353 12 "Proposition:" }}{PARA 265 "" 0 "" {TEXT 354 117 "If G is a Groebner basis then normalf(g, G, ord) is uniquely dete rmined for all g in Q[x1,..,xn]. Furthermore one has" }}{PARA 266 "" 0 "" {TEXT -1 89 "normalf(g1, G, ord) = normalf(g2, G, ord) if and onl y if g1 is equivalent to g2 modulo I." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 196 "So whenever g1+I = g2+I (i.e. g1 is equivalent to g2 modulo I, or in other words: g1-g2 is in I), then no rmalf(g1, G, ord)=normalf(g2, G, ord). If G is not a Groebner basis th en this is not true." }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 23 "Buchber ger's criterium." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "Let f and g be polynomials." }}{PARA 0 "" 0 "" {TEXT -1 97 "Let lf and lg be their leading monomials (note: lf and lg depend o n the ordering we have chosen)." }}{PARA 0 "" 0 "" {TEXT -1 41 "Write \+ lf=lc(f)*lpp(f) and lg=lc(g)*lpp(g)" }}{PARA 0 "" 0 "" {TEXT -1 41 "wh ere lc(f) and lc(g) are constants (the " }{TEXT 342 20 "leading coeffi cients" }{TEXT -1 37 "), and lpp(f), lpp(g) in [X] are the " }{TEXT 343 23 "leading power products." }}{PARA 0 "" 0 "" {TEXT -1 333 "What \+ would be the smallest power product t=x1^e1*...*xn^en in [X] that can \+ be reduced by f and by g? Now t can be reduced by f if and only if lpp (f) divides t. And t can be reduced by g if and only if lpp(g) divides t. So t can be reduced by both f and g if and only if lcm(lpp(f),lpp( g)) divides t. So the smallest such monomial is:" }}{PARA 0 "" 0 "" {TEXT -1 22 "t=lcm(lpp(f), lpp(g))." }}{PARA 0 "" 0 "" {TEXT -1 112 "S o if we reduce t modulo the set \{f,g\}, and we do only 1 reduction st ep, then we can have two possible outcomes:" }}{PARA 0 "" 0 "" {TEXT -1 30 "t - 1/lc(f) * t/lpp(f) * f or" }}{PARA 0 "" 0 "" {TEXT -1 27 " t - 1/lc(g) * t/lpp(g) * g." }}{PARA 0 "" 0 "" {TEXT -1 289 "Both thes e outcomes are the same modulo (f,g), they are both equivalent to t mo dulo (f,g). So the difference between the two is equivalent to t-t=0 m odulo (f,g), and so it must be an element of the ideal (f,g). This dif ference is (note that this depends on the ordering ord that we select) " }}{PARA 0 "" 0 "" {TEXT 355 32 "Definition: The S-polynomial is:" }} {PARA 0 "" 0 "" {TEXT -1 77 "spoly(f,g, ord) = (t - 1/lc(g) * t/lpp(g) * g) - (t - 1/lc(f) * t/lpp(f) * f)" }}{PARA 0 "" 0 "" {TEXT -1 64 " \+ = lcm( lc(f), lc(g)) * (f/lf - g/lg)" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "Let F be \+ a set of polynomials, and let f,g in F." }}{PARA 0 "" 0 "" {TEXT -1 505 "Now S=spoly(f,g, ord) is an element of the ideal (f,g) and hence \+ also an element of the ideal (F). So, by definition of a Groebner basi s, we see that if F is a groebner basis then reduce(S, F, ord) must be 0, and in fact it must be zero regardless of the choices made during \+ the reduction process (so whether we use f1 first, or f2, or f3 or suc h, it should always go to 0). Now Buchberger's criterium says that the converse is also true, if all S-poly's can be reduced to zero then F \+ is a Groebner basis." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT 356 23 "Buchberger's criterium." }}{PARA 0 "" 0 "" {TEXT -1 68 "The set F is a Groebner basis w.r.t. the ordering ord if and only \+ if" }}{PARA 0 "" 0 "" {TEXT -1 32 "reduce(spoly(f,g,ord), F, ord)=0" } }{PARA 0 "" 0 "" {TEXT -1 19 "for every f,g in F." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 357 4 "Note" }{TEXT -1 499 ": wh en we do not know if F is a Groebner basis, then we also do not know i f the output of reduce(spoly(f,g,ord), F, ord) is unique or not, it ca n depend on coincidence (which element of F is used first in the reduc e=reduce_poly algorithm, which second, etc.). Depending on such coinci dence, it may even sometimes reduce to 0 and sometimes not. Buchberger 's criterium holds no matter how the reduction is done, it is independ ent on the choices you can make during the reduce algorithm, so as lon g as " }{TEXT 358 4 "all " }{TEXT -1 411 "S-poly's can be reduced to 0 with the reduction algorithm (for some particular choices during this computation), then we can be sure that F is a Groebner basis. So, ass uming Buchberger's criterium is true, we see that all S-poly's reduce \+ to 0 for any choices made during the reductions if and only if all S-p oly's reduce to 0 for just one particular choice made during the reduc tion. We will postpone the proof." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 289 "So we have an algorithmic criterium whic h lets us test if a set is a Groebner basis or not. Let's check this w ith the example I=(F) from earlier in this worksheet. We had computed a set G that was not a Groebner basis, and then we had computed a set GB with the gbasis algorithm in Maple." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "F;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<%,(*$)%#x1G\"\" #\"\"\"\"\"\"*$)%#x2GF(F)F(*$)%#x3GF(F)\"\"$,*F'F*F-F*F0F*!\"\"F*,&*(F 'F*F-F*F0F*F*F3F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "for i \+ in F do for j in F minus \{i\} do S:=spoly(i,j, ord); reduce(S, F, ord ) od od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG,(*$)%#x1G\"\"#\"\" \"\"\"\"*$)%#x2GF)F*F)*$)%#x3GF)F*\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,*%#x1G\"\"\"%#x2GF'%#x3GF'!\"\"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,,*$)%#x1G\"\"#\"\"\"\"\"\"*$)%#x3GF)F*\"\"$*&%#x 2GF+F(F+!\"#*&F1F*F.F+F2F1F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,.*$)% #x1G\"\"#\"\"\"\"\"$*&F&\"\"\"%#x3GF+\"\"%F&!\"%*$)F,F'F(\"\"&F,F.F'F+ " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,&*(%#x1G\"\"\"%#x2GF(%#x3GF (F(!\"\"F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,(*&)%#x1G\"\"$\" \"\"%#x3G\"\"\"F,*&F(F,)F+F)F*F)%#x2G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,,*&)%#x1G\"\"$\"\"\"%#x3G\"\"\"F**&F&F*)F)F'F(F'F&!\"# F)F-\"\"#F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG,*%#x1G\"\"\"%#x2 GF'%#x3GF'!\"\"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,(*$)%#x1G \"\"#\"\"\"\"\"\"*$)%#x2GF)F*F)*$)%#x3GF)F*\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,,*&%#x2G\"\"\"%#x1GF(\"\"#*&F'\"\"\"%#x3GF(F*F'! \"#*$)F)F*F,!\"\"*$)F-F*F,!\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,.*$ )%#x1G\"\"#\"\"\"!\"$*&F&\"\"\"%#x3GF+!\"%F&\"\"%*$)F,F'F(!\"&F,F.!\"# F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,&*(%#x1G\"\"\"%#x2GF(%#x3 GF(F(!\"\"F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,**&%#x3G\"\"\") %#x1G\"\"#\"\"\"F(*&F*F()F'F+F,F(*&F*F,F'F,!\"\"F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,**&%#x3G\"\"\")%#x1G\"\"#\"\"\"F&*&F(F&)F%F)F*F&*&F (F*F%F*!\"\"F&F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG,&*(%#x1G\" \"\"%#x2GF(%#x3GF(F(!\"\"F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG, (*$)%#x1G\"\"#\"\"\"\"\"\"*$)%#x2GF)F*F)*$)%#x3GF)F*\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,(%#x2G!\"#*&)%#x1G\"\"$\"\"\"%#x3G\"\"\" !\"\"*&F*F.)F-F+F,!\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,,*&)%#x1G\" \"$\"\"\"%#x3G\"\"\"!\"\"*&F&F*)F)F'F(!\"$F&\"\"#F)F/!\"#F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,*%#x1G\"\"\"%#x2GF'%#x3GF'!\"\"F'" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,*!\"\"\"\"\"*&%#x3GF')%#x1G\"\" #\"\"\"F&*&F+F')F)F,F-F&*&F+F-F)F-F'" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#,*!\"\"\"\"\"*&%#x3GF%)%#x1G\"\"#\"\"\"F$*&F)F%)F'F*F+F$*&F)F+F'F+F% " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "G;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<%,.*$)%#x1G\"\"#\"\"\"\"\"$*$)%#x3GF(F)F**&%#x2G\"\"\" F-F0!\"#F/F(*&F'F0F-F)F(F'F1,*F'F0F/F0F-F0!\"\"F0,.!\"$F0*$)F-F*F)\"\" &*&F'F)F,F)F0F2F4F+!\"%F-F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "for i in G do for j in G minus \{i\} do S:=spoly(i,j, ord); reduce (S, G, ord) od od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG,.*$)%#x1G \"\"#\"\"\"\"\"$*$)%#x3GF)F*F+*&%#x2G\"\"\"F.F1!\"#F0F)*&F(F1F.F*F)F(F 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,*%#x1G\"\"\"%#x2GF'%#x3GF' !\"\"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,2*&%#x2G\"\"\")%#x3G \"\"#\"\"\"\"\"$*&F*F()F'F+F,!\"#*$F/F,F+*(%#x1GF(F'F,F*F,F+*&F'F,F3F, F0*$)F3F-F,!\"$*&F*F,)F3F+F,F7*$F9F,F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.!\"$\"\"\"*$)%# x3G\"\"$\"\"\"\"\"&*&%#x1GF')F*\"\"#F,F'*&F/F,F*F'!\"\"*$F0F,!\"%F*F1 " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,2*$)%#x3G\"\"%\"\"\"\"\"$*& )F(F+F*%#x2G\"\"\"!\"#*&F.F*)F(\"\"#F*F3*&%#x1GF/F-F*!#8*&F5F*F2F*\"#5 F5\"\"**&F(F/)F5F3F*F+*&F5F*F(F*!\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#,.*$)%#x3G\"\"%\"\"\"\"#?%#x1G\"\"$*&F*\"\"\"F&F-!\"$*$)F&F+F(!\"'F& !\"(F2F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG,*%#x1G\"\"\"%#x2GF' %#x3GF'!\"\"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.*$)%#x1G\"\" #\"\"\"\"\"$*$)%#x3GF)F*F+*&%#x2G\"\"\"F.F1!\"#F0F)*&F(F1F.F*F)F(F2" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,2*&%#x2G\"\"\")%#x3G\"\"#\"\" \"!\"$*&F*F()F'F+F,F+*$F/F,!\"#*(%#x1GF(F'F,F*F,F1*&F'F,F3F,F+*$)F3\" \"$F,F7*&F*F,)F3F+F,F7*$F9F,F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\" !" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.!\"$\"\"\"*$)%#x3G\"\"$\" \"\"\"\"&*&%#x1GF')F*\"\"#F,F'*&F/F,F*F'!\"\"*$F0F,!\"%F*F1" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,2*&)%#x3G\"\"#\"\"\")%#x1GF)F*\"\"\"* &F,F-)F(\"\"$F*F-*&F,F*F'F*!\"\"%#x2GF0*&F/F*F3F-!\"&*(F,F*F3F*F(F-F-* &F3F*F'F*\"\"%*&F3F*F(F*!\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,.*$)% #x3G\"\"%\"\"\"!#?*$)F&\"\"$F(\"\"'%#x1G!\"$*&F.\"\"\"F&F1F,F&\"\"(F2F 1" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG,.!\"$\"\"\"*$)%#x3G\"\"$\" \"\"\"\"&*&%#x1GF')F*\"\"#F,F'*&F/F,F*F'!\"\"*$F0F,!\"%F*F1" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.*$)%#x1G\"\"#\"\"\"\"\"$*$)%#x3GF)F* F+*&%#x2G\"\"\"F.F1!\"#F0F)*&F(F1F.F*F)F(F2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,2%#x1G!\"**&F&\"\"\")%#x3G\"\"$\"\"\"\"#8*&F+F)) F&\"\"#F-!\"$*&F&F-)F+F1F-!#5*&F&F-F+F-\"\"'*$)F+\"\"%F-F2*&F*F-%#x2GF )F1*&F%\"jG,*%#x1G\"\"\"%#x2GF'%#x3GF'!\"\"F'" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,2%#x2G!\"$*&)%#x3G\"\"$\"\"\"F& \"\"\"\"\"&*(%#x1GF-F&F,F*F-!\"\"*&F&F,)F*\"\"#F,!\"%*&F&F,F*F,F4*&F3F ,)F0F4F,F1*&F0F,F)F,F1*&F0F,F3F,F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# ,.*$)%#x3G\"\"%\"\"\"\"#?%#x1G\"\"$*&F*\"\"\"F&F-!\"$*$)F&F+F(!\"'F&! \"(F2F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "GB;" }}{PARA 12 " " 1 "" {XPPMATH 20 "6#7&,.!\"*\"\"\"*$)%#x3G\"\"$\"\"\"\"#:*$)F)\"\"#F +!#>F)!\"\"*$)F)\"\"&F+\"#?*$)F)\"\"%F+!\"',*%#x1GF&%#x2GF&F)F&F1F&,.F 6!#?F'\"\"'F;!\"$*&F;F&F)F&F*F)\"\"(FBF&,.*$)F;F/F+\"\"*F6\"#!)F'!#CF- F,F)!#S!#AF&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 91 "for i in GB do for j in \{op(GB)\} minus \{i\} do S:=spoly(i,j, ord); reduce(S, G B, ord) od od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG,.!\"*\"\"\"*$ )%#x3G\"\"$\"\"\"\"#:*$)F*\"\"#F,!#>F*!\"\"*$)F*\"\"&F,\"#?*$)F*\"\"%F ,!\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.*$)%#x1G\"\"#\"\"\"\" \"**$)%#x3G\"\"%F*\"#!)*$)F.\"\"$F*!#C*$)F.F)F*\"#:F.!#S!#A\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,6*$)%#x1G\"\"#\"\"\"!#\")*&F'F* )%#x3G\"\"$F*\"$N\"*&)F.F)F*F'F*!$r\"*&F.\"\"\"F'F*!\"**&F'F*)F.\"\"%F *!#a*$)F.\"\"*F*!%+;*$)F.\"\")F*\"$![*$)F.\"\"(F*!$+$*$)F.\"\"'F*\"$+) *$)F.\"\"&F*\"$S%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,*%#x1G\"\"\"%#x2GF'%#x3GF'!\"\"F'" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,2%#x2G!\"**&)%#x3G\"\"$\"\"\"F& \"\"\"\"#:*&F&F,)F*\"\"#F,!#>*&F&F,F*F-!\"\"*&F&F,)F*\"\"%F,!\"'*&%#x1 GF-)F*\"\"&F,!#?*$)F*\"\"'F,F=*$F;F,\"#?" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.*$)%#x3G\"\"%\" \"\"!#?*$)F(\"\"$F*\"\"'%#x1G!\"$*&F0\"\"\"F(F3F.F(\"\"(F4F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,4%#x1G!#F*&F&\"\"\")%#x3G\"\"$\"\"\" \"#X*&F&F-)F+\"\"#F-!#d*&F&F-F+F)!\"$*&F&F-)F+\"\"%F-\"#U*$)F+\"\")F- \"$+%*$)F+\"\"(F-!$?\"*$)F+\"\"&F-!$S\"*$F6F-FD" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG,*%#x1G \"\"\"%#x2GF'%#x3GF'!\"\"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG, .*$)%#x1G\"\"#\"\"\"\"\"**$)%#x3G\"\"%F*\"#!)*$)F.\"\"$F*!#C*$)F.F)F* \"#:F.!#S!#A\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,2*$)%#x1G \"\"$\"\"\"\"\"**&%#x3G\"\"\")F(\"\"#F*F+*$F/F*!\"**&%#x2GF.)F-\"\"%F* !#!)*&)F-F)F*F4F*\"#C*&F4F*)F-F0F*!#:*&F4F*F-F*\"#SF4\"#A" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG ,.*$)%#x3G\"\"%\"\"\"!#?*$)F(\"\"$F*\"\"'%#x1G!\"$*&F0\"\"\"F(F3F.F(\" \"(F4F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,2*&%#x3G\"\"\")%#x1G \"\"#\"\"\"\"\"$*&F*F()F'F+F,F-*&F*F,F'F,!\"$*&%#x2GF()F'\"\"%F,\"#?*& )F'F-F,F3F,!\"'*&F*F,F3F,F-*&F3F,F'F,!\"(F3F<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.!\"*\" \"\"*$)%#x3G\"\"$\"\"\"\"#:*$)F*\"\"#F,!#>F*!\"\"*$)F*\"\"&F,\"#?*$)F* \"\"%F,!\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,2%#x2G\"\"**&)%# x3G\"\"$\"\"\"F&\"\"\"!#:*&F&F,)F*\"\"#F,\"#>*&F&F,F*F-F-*&F&F,)F*\"\" %F,\"\"'*&%#x1GF-)F*\"\"&F,\"#?*$)F*F7F,F<*$F:F,!#?" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG,.*$)% #x3G\"\"%\"\"\"!#?*$)F(\"\"$F*\"\"'%#x1G!\"$*&F0\"\"\"F(F3F.F(\"\"(F4F 3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.*$)%#x1G\"\"#\"\"\"\"\"** $)%#x3G\"\"%F*\"#!)*$)F.\"\"$F*!#C*$)F.F)F*\"#:F.!#S!#A\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,6*&%#x1G\"\"\")%#x3G\"\"%\"\"\" !#g*&F'F,)F*\"\"$F,\"#=*$)F'\"\"#F,!\"**&F'F,F*F(\"#@F'F7*$)F*\"\"&F,! #!)*$F)F,\"#C*$F/F,!#:*$)F*F4F,\"#SF*\"#A" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,*%#x1G \"\"\"%#x2GF'%#x3GF'!\"\"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG, 2*&%#x2G\"\"\")%#x3G\"\"%\"\"\"!#?*&)F*\"\"$F,F'F,\"\"'*&%#x1GF(F'F,! \"$*&F'F,F*F(\"\"(F'F6*&F*F,)F3\"\"#F,F4*&F3F,)F*F9F,F4*&F3F,F*F,F0" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.!\"*\"\"\"*$)%#x3G\"\"$\"\"\"\"#:*$)F*\"\"#F,!#>F*!\"\"* $)F*\"\"&F,\"#?*$)F*\"\"%F,!\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"SG,4*$)%#x3G\"\")\"\"\"!$+%*$)F(\"\"(F*\"$?\"*&%#x1G\"\"\")F(\"\"%F* !#U*$)F(\"\"&F*\"$S\"*$F3F*F9F1\"#F*&F1F*)F(\"\"$F*!#X*&F1F*)F(\"\"#F* \"#d*&F1F*F(F2F>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"iG,.*$)%#x1G\"\"#\"\"\"\"\"**$)%#x3G\"\"%F* \"#!)*$)F.\"\"$F*!#C*$)F.F)F*\"#:F.!#S!#A\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,*%#x1G\"\"\"%#x2GF'%#x3GF'!\"\"F'" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"SG,2*&%#x2G\"\"\")%#x3G\"\"%\"\"\"\"#!)*&)F* \"\"$F,F'F,!#C*&F'F,)F*\"\"#F,\"#:*&F'F,F*F(!#SF'!#A*$)%#x1GF0F,!\"**& F*F,)F;F4F,F<*$F>F,\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.*$)%#x3G\"\"%\"\"\"!#?*$)F(\" \"$F*\"\"'%#x1G!\"$*&F0\"\"\"F(F3F.F(\"\"(F4F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,6*&%#x1G\"\"\")%#x3G\"\"%\"\"\"\"#g*&F'F,)F*\"\" $F,!#=*$)F'\"\"#F,\"\"**&F'F,F*F(!#@F'F7*$)F*\"\"&F,\"#!)*$F)F,!#C*$F/ F,\"#:*$)F*F4F,!#SF*!#A" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"jG,.!\"*\"\"\"*$)%#x3G\"\"$\"\"\" \"#:*$)F*\"\"#F,!#>F*!\"\"*$)F*\"\"&F,\"#?*$)F*\"\"%F,!\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG,6*$)%#x1G\"\"#\"\"\"\"#\")*&F'F*)%#x3 G\"\"$F*!$N\"*&)F.F)F*F'F*\"$r\"*&F.\"\"\"F'F*\"\"**&F'F*)F.\"\"%F*\"# a*$)F.F6F*\"%+;*$)F.\"\")F*!$![*$)F.\"\"(F*\"$+$*$)F.\"\"'F*!$+)*$)F. \"\"&F*!$S%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 326 "So for the set F that we started with, none of the S-poly's reduced to 0 using reduce(S, F, ord). So F is definitely not a Groebner basis. The set G was a little better, some of the S-po ly's reduced to zero, but not all, so that is not a Groebner basis eit her. The set GB is a Groebner basis, all the S-poly's reduced to zero. " }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 27 "Computing a Groebner basis. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 230 "Let \+ F be a set of polynomials F=\{f1,f2,..,fm\}. We want to compute a Groe bner basis for the ideal I=(F). We can use Buchberger's algorithm to c heck if the set F is already a Groebner basis as follows: Compute all \+ the S-polynomials:" }}{PARA 0 "" 0 "" {TEXT -1 16 "spoly(f, g, ord)" } }{PARA 0 "" 0 "" {TEXT -1 54 "where f,g in F and f<>g (if f=g then the S-poly is 0)." }}{PARA 0 "" 0 "" {TEXT -1 95 "We reduce each S-poly b y F. When they all reduce to 0, then we are done, F is a Groebner basi s." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 55 "Wha t if they don't all reduce to zero? Idea: then do:" }}{PARA 0 "" 0 " " {TEXT -1 83 "F := F union \{all S-polys (or their reductions) that d idn't reduce to zero\}. (**)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 115 "Note that since we only added elements o f ideal to the set F, the new F will generate the same ideal as the o ld F." }}{PARA 0 "" 0 "" {TEXT -1 30 "Is the new F a Groebner basis?" }}{PARA 0 "" 0 "" {TEXT -1 12 "We see that " }{TEXT 362 20 "all S-poly 's of the " }{TEXT 363 5 "old F" }{TEXT 361 48 " can be reduced to zer o when we reduce with the " }{TEXT 364 5 "new F" }{TEXT -1 8 ". Note: \+ " }{TEXT 359 21 "\"can be reduced to 0\"" }{TEXT -1 10 ", and not " } {TEXT 360 23 "\"will be reduced to 0\"," }{TEXT -1 117 " because the r esult of the reduction depends on coincidence. However, nothing garant uees us that all S-poly's of the " }{TEXT 365 5 "new F" }{TEXT -1 38 " can also be reduced to zero with the " }{TEXT 366 7 "new F, " }{TEXT -1 16 "and indeed, the " }{TEXT 367 5 "new F" }{TEXT -1 37 " is not ne cessarily a Groebner basis." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 12 "What if the " }{TEXT 369 6 "new F " }{TEXT -1 309 "is still not a Groebner basis? How do we know that in the first p lace? Well, we would have to compute all S-poly's of the new F and red uce them using the new F. So, the new F is not a Groebner basis if and only if not all of these S-poly's reduce to zero. If they don't all r educe to zero, then what do we do?" }}{PARA 0 "" 0 "" {TEXT -1 132 "Id ea: we won't let that bother us, we'll simply do step (**) again! In f act, we'll just keep on doing step (**) over and over again " }{TEXT -1 6 "until " }{TEXT 370 4 "all " }{TEXT -1 23 "S-poly's reduce to zer o" }{TEXT 372 1 " " }{TEXT -1 95 "(and there can be many of those S-po ly's, because F is getting larger and larger all the time)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 78 "Now the miracle is: Although it may take a long time, This process terminates!" }}}} {MARK "9" 0 }{VIEWOPTS 1 1 0 1 1 1803 }