{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 1 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 1 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 1 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 368 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 369 "" 0 1 0 0 0 0 0 1 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 371 "" 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 }{CSTYLE "" -1 374 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 375 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 376 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 377 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 378 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 379 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 380 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 381 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 382 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 383 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 384 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 385 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 386 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 387 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 388 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 389 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 390 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 391 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 392 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 393 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 395 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 396 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 397 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 398 "" 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 Ou tput" 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 380 0 "" }{TEXT 256 18 "Polynomia l 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 145 " \+ 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 " }{TEXT 372 1 "C" }{TEXT -1 44 "^n, then 1 is an element of the i deal. Here " }{TEXT 373 1 "C" }{TEXT -1 25 " are the complex numbers. " }}{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 t here can be equations that can be derived from the equations f1,..,fm \+ but that can not be always obtained by additions and multiplications w ith polynomials. Namely the 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 th e ideal, but f=0 means g^n=0, from which we can conclude: g=0. It turn s out if we include these polynomials 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 "Definition: " }}{PARA 0 "" 0 "" {TEXT -1 41 "Let \+ f1,f2,..,fm be polynomials. Then the " }{TEXT 270 13 "radical ideal" } {TEXT 379 1 " " }{TEXT -1 92 "of the ideal (F) is the collection of al l polynomials that can be obtained from f1,..,fm by:" }}{PARA 0 "" 0 " " {TEXT -1 33 "1) multiplications by polynomials" }}{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 include g as well." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "So " }{TEXT 376 45 "an ideal is closed under operations 1) and 2)" }{TEXT -1 8 ", and \+ a " }{TEXT 377 55 "radical 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 by f1,..,fm (when we think of them as equations ) is a set of polynomials that are consequences of f1=f2=..=fm=0, but \+ where we only do operations 1) and 2). The ideal does not always conta in all polynomials that are consequences of f1,..fm." }}{PARA 0 "" 0 " " {TEXT -1 17 "But according to " }{TEXT 273 26 "Hilbert's Nullstellen satz," }{TEXT -1 33 " the radical ideal is the set of " }{TEXT 271 3 " all" }{TEXT -1 32 " consequences of f1=f2=..=fm=0. " }{TEXT 272 25 "Hi lbert's Nullstellensatz" }{TEXT -1 11 " says that:" }}{PARA 0 "" 0 "" {TEXT -1 119 "g is in the radical ideal if and only if g(alpha1,..,alp ha.n)=0 for all solutions (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 of f1,..,fm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 328 11 "Definition:" }}{PARA 0 "" 0 "" {TEXT -1 20 "Let R be a ring. An " }{TEXT 378 25 "ascending chain of ideals " }{TEXT -1 24 " is a sequence of ideals" }}{PARA 0 "" 0 "" {TEXT -1 18 "I.1, I.2, I.3, ..." }}{PARA 0 "" 0 "" {TEXT -1 10 "such that " } {TEXT 329 34 "I..i is a proper subset of I.(i+1)" }{TEXT -1 12 " for e ach 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 221 " when R has no infinitely ascending chains of ideals. So every ascending (= increasing) chain of ideals m ust be a finite chain: L.1, L.2,..,L.n (finite meaning that there is a last, i.e. largest, ideal L.n in that chain)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "Let I1, I2, ... be ideals in R, and suppose that " }{TEXT 330 27 "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 fi nitely generated." }}{PARA 0 "" 0 "" {TEXT -1 98 "This means that for \+ every ideal I, there exists a finite subset F=\{f1,..,fm\} of R such t hat I=(F)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 335 6 "Proof:" }} {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 set F ." }}{PARA 0 "" 0 "" {TEXT -1 350 "This way, the ideals (F) we encount er form an ascending sequence, and when R is Noetherian this sequence \+ must be finite, and so it must end. But it only ends when I=(F). Hence we find a finite set F such that I=(F), so I is generated by finitely many elements, namely the elements of F. I will leave the proof of th e converse statement 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 -1 283 "Note that Q, the fiel d of rational numbers, has only two ideals, namely (0) = \{0\} and (1) = Q. Hence it is Noetherian. According to Hilbert's basis theorem, ev ery time we add one variable, the ring stays Noetherian. So Q, Q[x1], \+ Q[x1,x2], Q[x1,x2,x3], ... are all Noetherian. Hence:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 337 121 "Corollary: Q[x1,x2 ,..,xn] is Noetherian, so for every ideal I in Q[x1,..,xn] there exist s a finite set F such that I=(F)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 374 8 "Remark: " }{TEXT -1 18 "In this worksheet " }{TEXT 375 70 "we will only study ideals that are given by a finite set of generators" }{TEXT -1 134 ". But according to the corollary, t hat is OK, it does not leave out any ideals because there always exist s a finite set of generators." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 48 "Solution to the Central Problem: Groebner basis." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 654 "It turns out that when t he central problem can be handled, then we can find a method to comput e answers to *many* (it almost seems: pretty much all) computational p roblems involving polynomial equations or polynomial ideals. An exampl e of such computational problem is the following, given polynomials f1 ,..,fm, the problem is: \"are the equations f1=0, f2=0,..,fm=0 consist ent, in other words, does a common solution exist?\". It is consisten t if and only if 1 is not an element of the ideal (F), and so we see t hat this problem is reduced to the central problem. Later we will also look at many other problems that can be reduced to the central proble m." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "The method of solving the central problem is to compute a " }{TEXT 274 17 "Groebner basis G " }{TEXT -1 19 "of the ideal I=(F)." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 275 19 "Partial Definitio n:" }{TEXT -1 91 " A Groebner basis G of an ideal I is a finite set of polynomials G=\{g1,g2,..,gk\} such that:" }}{PARA 0 "" 0 "" {TEXT -1 32 " 1) G spans the ideal, so I=(G)." }}{PARA 0 "" 0 "" {TEXT -1 124 " 2) G has some additional property (which will be defined later) that \+ will make it easy to answer the central problem above." }}}{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 cases 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 va riable x1 (lets just take x). We know we only have to do the gcd of th e polynomials f1..fm, which we can do with the following algorithm:" } }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1002 "case1:=proc(F::set, x::na me)\n local G,G_old,i,j,li,lj,k;\n G:=F minus \{0\};\n while G<>G_o ld do\n G_old:=G;\n for i in G do for j in G minus \{i\} do\n \+ li:=leading_monomial_case1(i,x);\n lj:=leading_monomial_case1( j,x);\n if type(li/lj, polynom) then\n # The leading mono mial of i is divisible by\n # the leading monomial of j, so we can reduce\n # i modulo j.\n # We will compute k, suc h 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. i t has lower degree).\n k := i - li/lj * j;\n k := prim part(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 re place\n # i by k as follows:\n G := ((G minus \{i\}) u nion \{k\}) minus \{0\}\n # Now we've made a leading monomial \+ in G smaller,\n # and eventually this process will end.\n \+ fi\n od od\n od;\n G\nend; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&case1GR6$'%\"FG%$setG'%\"xG%%nameG6)%\"GG%&G_oldG%\"iG%\"jG%# liG%#ljG%\"kG6\"F5C%>8$-%&minusG6$9$<#\"\"!?(F5\"\"\"F@F50F88%C$>FBF8? &8&F8%%trueG?&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=F8F5F 5F5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 100 "leading_monomial_ca se1:=proc(F,x)\n # Compute the highest term.\n lcoeff(F,x) * x^deg ree(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 algorithm case1 does is computing the gcd of f1,f2,...,fm. So we could have done a simpler implementation using Maple's gcd implementa tion. However, note the similarities with the implementation of case 2 later in this worksheet." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "f1 , f2, 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(f 1,f2), f3)) \};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG<#,&*$)%\"xG \"\"$\"\"\"!\"\"*$)F)\"\"%F+\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "Using this Groebner basis G, the solution to the central proble m 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 mo dulo 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,&*$)%\"x G\"\"(\"\"\"\"\"\"*$)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 ze ro, 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::list(name))\n local G,G_old,i,j,li,lj,k;\n G:=F minu s \{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_monomial_case2(j,list_vars);\n if type(li/lj, po lynom) then\n # The leading monomial of i is divisible by\n \+ # the leading monomial of j, so we can reduce\n # i modu lo j.\n #\n # Compute k = i modulo j.\n # Then : replace i by k, which has a \"smaller\"\n # leading monomial . This process will end,\n # we're making leading monomials\n \+ # smaller and smaller until we can reduce\n # them no \+ more.\n k := i - li/lj * j;\n G := ((G minus \{i\}) un ion \{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;<#F IFJC%>8(-%7leading_monomial_case2G6$FI9%>8)-FT6$FLFV@$-%%typeG6$*&FR\" \"\"FX!\"\"%(polynomGC$>8*,&FIFC*&*&FRFCFLFCFjnFXF[o!\"\">F;-F=6$-%&un ionG6$FM<#F_oF@F;F8F8F8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 591 "leading_monomial_case2:=proc(f, list_vars)\n # Assumption: f is lin ear in the variables.\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 ha s(f,x1) then x1 (times 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 for 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#>%7leading_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*x 4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,*%#x1G\"\"\"%#x2G\"\"#%#x 3G\"\"$%#x4G\"\"%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "f2:=x1 +3*x2+5*x3+7*x4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f2G,*%#x1G\"\" \"%#x2G\"\"$%#x3G\"\"&%#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%#x2G%#x3G%#x4G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "G:=case2(F,vars);" }}{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 call ed: " }{TEXT 263 21 "upper triangular form" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 102 "Using this upper triangular form it is now eas y 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 as the ele ment of G that has x1," }}{PARA 0 "" 0 "" {TEXT -1 55 "g2 is the eleme nt 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%#g3 G6$,(%#x2G!\"\"%#x3G!\"%%#x4G!\"*,&F+\"\"#F-\"\"'" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 93 "Now G=\{g1,g2,g3\}.\nTake a polynomial g, and redu ce 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+*$)%#x3G F)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 not 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+*$)%#x3G F)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, the re must exist 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 these two cases have in common?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 28 "Now we've treated two cas es:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 383 8 "ca se 1) " }{TEXT -1 33 " just 1 variable, but any degree." }}{PARA 0 "" 0 "" {TEXT 384 8 "case 2) " }{TEXT -1 40 "any number of variables, but degree = 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 "The implementations of case 1 and case 2 were very similar; the " }{TEXT 385 59 "only real difference was in the procedure leading_mo nomial." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 276 12 "What is the " }{TEXT 381 16 "leading monomial" }{TEXT 382 17 " of \+ a polynomial?" }}{PARA 0 "" 0 "" {TEXT -1 113 "For case 1, there was a n obvious choice as for which monomial is the largest one. For 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 obvious 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 clear 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 leading mon omial. 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 variables i n any way we want to, but we have to use the same ordering every time \+ because otherwise the algorithm case2 will probably not work. So: " } {TEXT 278 68 "there are many different orderings, we'll have to choose an ordering" }{TEXT -1 113 " (but once it is chosen, we'll have to ke ep 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 that we aga in 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 is the larg est one. We would first have to define some ordering on these monomial s, and only then can we say which one is the largest. Once we've decid ed 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 a t the leading monomials of i and j, and if lj=leading_monomial(j) divi des li=leading_monomial(i) (so when li/lj is a polynomial) then 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 chosen an ord ering, 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: initiall y in the algorithm G is the set F=\{f1,f2,..\}, we can try to make an \+ element i of G \"smaller\" by substracting a suitable multiple of anot her 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 spans the same ideal, but now one of the elements of G has become \"smaller\". Note \+ that the meaning of \"smaller\" here depends on the choice we made for the ordering. We will say that we " }{TEXT 280 16 "reduce the set G" }{TEXT -1 256 " when we reduce an i element of G w.r.t. another elemen t j of G. When we can reduce the set G no further (so when there are n o two elements i<>j in G such that the leading monomial of j divides t he 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 start wi th the set G=F, and then continue to reduce elements of G until nothin g can be reduced any further. So the only thing our algorithms case1 a nd case2 do is to compute a reduced set, and we see that the implement ations are indeed very similar." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 386 74 "For these two easy cases, a reduced set \+ is automatically a Groebner basis." }{TEXT -1 112 " This means that fo r case 1 and case 2, once we have a reduced set, the central problem c an easily be answered. " }{TEXT 387 50 "For the more general case, thi s is no longer true." }{TEXT -1 222 " We will see that the algorithm f or computing a reduced set is still pretty much the same as case1 and \+ case2, however, computing a reduced set will not be sufficient for han dling the central problem, we'll have to do more." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 93 "Notice that the Maple pro cedure for computing the leading monomial of a polynomial is called " }{TEXT 388 7 "leadmon" }{TEXT -1 176 ". The input of this procedure mu st be not only the polynomial, but the ordering as well, since the lea ding monomial depends on that ordering. To use this function, first t ype " }{TEXT 389 14 "with(Groebner)" }{TEXT -1 40 ", in order to load \+ the Groebner package." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 23 "Orderin gs 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 monomial" }{TEXT -1 88 " of some polynomial, then we will call the coefficient ( which is 7 in this example) the " }{TEXT 284 19 "leading coefficient" }{TEXT -1 23 ", and x1^3*x2^5 is the " }{TEXT 285 23 "leading power pr oduct. " }{TEXT -1 20 "The Maple procedure " }{TEXT 286 7 "leadmon" } {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 sequenc e 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 conside r the leading power product x1^3*x2^5, and not the corresponding non-z ero 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 po ssible 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 nota tion Q[x1,..,xn] is an infinite dimensional Q-vector space with basis \+ [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 w ill 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 integer s, then " }{TEXT 301 16 "e=(e1,e2,..,en) " }{TEXT -1 62 "where the e.i are integers. Then we will denote the monomial: " }{TEXT 293 21 "x1^e 1*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 just means that we can multiply elements of [X] and the result will again be in \+ [X])." }}{PARA 0 "" 0 "" {TEXT -1 95 "The map e -> X^e is an isomorphi sm of the additive monoid N^n to the multiplicative monoid [X]." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 290 10 "Definiti on" }{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 ordering, which means that if s,t in [X], then precisely one of the following t hree holds: sX^e) to orderings on [X]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 292 39 "Three examples of admissible orderings :" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 6 "pur e 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 lexicographic or dering " }{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 element 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, und er the plex(x1,x2,x3) ordering, the leading monomial is: 2*x1^2. The s econd 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 ordering in the dictionary, when you compare two words in the alphabetical ordering, \+ then you at the first letter of each word. The other letters 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 "Total degree o rdering:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 309 33 "Maple notatio n: tdeg(x1,x2,..,xn)" }}{PARA 0 "" 0 "" {TEXT -1 199 "If d=(d1,d2,..,d n) and e=(e1,e2,..,en), then we say that the degree of the monomial X^ e=x1^e1*...*xn^en (or the \"total degree\") equals e1+e2+...+en. A to tal degree ordering is an ordering such that:" }}{PARA 0 "" 0 "" {TEXT -1 34 "If d1+..+dn < e1+...+en then d1 then there exist infi nitely many (even: uncountably many) different admissible orderings on [X]. To see more examples of admissible orderings type ?Groebner,term order in Maple." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 60 "Reducing a se t 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, w e 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 thro w away the zeros." }}{PARA 0 "" 0 "" {TEXT -1 266 "Then: whenever you \+ have two different elements i and j in G, and if the leading term lj o f j divides the leading term li of i, then we replace i by the reducti on of i w.r.t. j, which was i-li/lj * j. Keep doing this process 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 ordering." }} {PARA 0 "" 0 "" {TEXT -1 87 "In case 1), the only monomials where powe rs 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 ordering. 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#%#x 3G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 631 "Now we will take a set F o f polynomials, and we will take the number of variables n to be >1, an d we will also have degrees that are >1. Then, as long as we can find \+ elements i<>j in F such that the leading monomial lj of j divides the \+ 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 is \+ the same as the leading monomial of i, the leading monomial has become smaller this way. So the leading monomials will get smaller and small er during the computation in the following algorithm. Note the similar ity with the implementations case1 and case2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 993 "reduce_polynomials:=proc(F,ord)\n local G,G_ol d,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[lea dmon](i,ord);\n lj:=Groebner[leadmon](j,ord);\n if 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 # 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 k := i - li[1]/lj[1] * li[2 ]/lj[2] * j;\n k := primpart(k);\n # Since i and k are the same modulo j,\n # and j in G minus \{i\},\n # th e ideal will not change if we replace\n # i by k as follows:\n G := ((G minus \{i\}) union \{k\}) minus \{0\}\n # No w we've made a leading monomial in G smaller,\n # and eventual ly this process will end (why?...)\n fi\n od od\n od;\n G\n end; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%3reduce_polynomialsGR6$% \"FG%$ordG6)%\"GG%&G_oldG%\"iG%\"jG%#liG%#ljG%\"kG6\"F1C%>8$-%&minusG6 $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_o F9F4F1F1F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "F:=\{x1^2+2*x 2^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 set" }} {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 basis." } }{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 116 "The set F generates the same ideal as our reduced set G, and the Groebner basis GB also generates 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 390 8 "Remark: " }{TEXT -1 7 "In the " }{TEXT 391 19 "li near algebra case" }{TEXT -1 41 " (when all equations have degree 1) t hen " }{TEXT 392 6 "using " }{TEXT 396 6 "reduce" }{TEXT 395 83 " corr esponds to bringing the matrix into row echelon form (= upper triangul ar form)" }{TEXT -1 9 " whereas " }{TEXT 393 6 "using " }{TEXT 397 7 " normalf" }{TEXT 398 65 " corresponds to bringing the matrix into reduc ed row echelon form" }{TEXT -1 106 " (= upper triangular, and if you h ave a row-leader in a column then the rest of that column must be zero )." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 85 "Fro m 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 red uce(g, G, ord)=0." }}{PARA 0 "" 0 "" {TEXT -1 124 "So, when G is a Gro ebner basis, then the output of reduce(g, G, ord) is uniquely determin ed for all g in I, the output is 0." }}{PARA 0 "" 0 "" {TEXT 353 12 "P roposition:" }}{PARA 265 "" 0 "" {TEXT 354 117 "If G is a Groebner bas is then normalf(g, G, ord) is uniquely determined 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 only 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, o r in other words: g1-g2 is in I), then normalf(g1, G, ord)=normalf(g2, G, ord). If G is not a Groebner basis then this is not true." }}}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 23 "Buchberger'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 le ading monomials (note: lf and lg depend on the ordering we have chosen )." }}{PARA 0 "" 0 "" {TEXT -1 5 "Write" }}{PARA 0 "" 0 "" {TEXT -1 79 " \"leading term of f\" = \"leading coefficient of f\" * \"lead ing power product\"" }}{PARA 0 "" 0 "" {TEXT -1 23 " lf=lc(f)*lp p(f) " }}{PARA 0 "" 0 "" {TEXT -1 3 "and" }}{PARA 0 "" 0 "" {TEXT -1 22 " lg=lc(g)*lpp(g)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 39 "Now lc(f) and lc(g) are constants (the " }{TEXT 342 20 "leading coefficients" }{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*...*x n^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 o nly if lpp(g) divides t. So t can be reduced by both f and g if and on ly if lcm(lpp(f),lpp(g)) divides t. So the smallest such monomial is: " }}{PARA 0 "" 0 "" {TEXT -1 25 "t := lcm(lpp(f), lpp(g))." }}{PARA 0 "" 0 "" {TEXT -1 112 "So if we reduce t modulo the set \{f,g\}, and we do only 1 reduction step, then we can have two possible outcomes:" }} {PARA 0 "" 0 "" {TEXT -1 27 "t - t/lpp(f) * f/lc(f) or" }}{PARA 0 " " 0 "" {TEXT -1 24 "t - t/lpp(g) * g/lc(g)." }}{PARA 0 "" 0 "" {TEXT -1 289 "Both these outcomes are the same modulo (f,g), they are both e quivalent to t modulo (f,g). So the difference between the two is equi valent to t-t=0 modulo (f,g), and so it must be an element of the idea l (f,g). This difference is (note that this depends on the ordering or d that we select)" }}{PARA 0 "" 0 "" {TEXT 355 32 "Definition: The S-p olynomial is:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 61 " spoly(f,g, ord) = lcm( lpp(f), lpp(g)) * (f/lf - g /lg)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 83 "S o what we did is: Take f, and divide f by the leading term of f, and \+ we get f/lf." }}{PARA 0 "" 0 "" {TEXT -1 70 "Then take g, and divide i t by the leading term of g, and we get: g/lg." }}{PARA 0 "" 0 "" {TEXT -1 59 "Now compute t such that t/lf and t/lg are both polynomial s:" }}{PARA 0 "" 0 "" {TEXT -1 20 " t := lcm(lf, lg) " }}{PARA 0 "" 0 "" {TEXT -1 3 "or:" }}{PARA 0 "" 0 "" {TEXT -1 75 " t := lcm( lpp(f ), lpp(g) ) (we may ignore the leading constants)." }}{PARA 0 "" 0 "" {TEXT -1 53 "So then t * f/lf = t/lf * f = (some polynomial) \+ * f." }}{PARA 0 "" 0 "" {TEXT -1 41 "And t * g/lg = (some other polyno mial)*g." }}{PARA 0 "" 0 "" {TEXT -1 75 "And spoly(f,g,ord) = the diff erence = t/lf * f - t/lg * g = t*(f/lf - g/lg)" }}{PARA 0 "" 0 "" {TEXT -1 108 "and this equals: (some polynomial)*f - (some other poly nomial)*g and hence this is an element of the ideal." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "Let F be a set of polyn omials, 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 basis, we see that i f 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 pr ocess (so whether we use f1 first, or f2, or f3 or such, it should alw ays go to 0). Now Buchberger's criterium says that the converse is als o true, if all S-poly's can be reduced to zero then F is a Groebner ba sis." }}{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 ": when we do not kno w if F is a Groebner basis, then we also do not know if the output of \+ reduce(spoly(f,g,ord), F, ord) is unique or not, it can depend on coin cidence (which element of F is used first in the reduce=reduce_poly al gorithm, which second, etc.). Depending on such coincidence, it may ev en sometimes reduce to 0 and sometimes not. Buchberger's criterium hol ds no matter how the reduction is done, it is independent on the choic es you can make during the reduce algorithm, so as long as " }{TEXT 358 4 "all " }{TEXT -1 411 "S-poly's can be reduced to 0 with the redu ction algorithm (for some particular choices during this computation), then we can be sure that F is a Groebner basis. So, assuming Buchberg er's criterium is true, we see that all S-poly's reduce to 0 for any c hoices made during the reductions if and only if all S-poly's reduce t o 0 for just one particular choice made during the reduction. We will \+ postpone the proof." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 289 "So we have an algorithmic criterium which lets us test if a set is a Groebner basis or not. Let's check this with the exampl e 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 g basis 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*\"\"$*&%#x2GF+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\"\"\"%#x2GF'%#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(%#x3GF(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 368 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 138 "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 until " } {TEXT 369 4 "all " }{TEXT -1 23 "S-poly's reduce to zero" }{TEXT 370 1 " " }{TEXT -1 95 "(and there can be many of those S-poly'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: Altho ugh it may take a long time, This process terminates!" }}}}{MARK "9" 0 }{VIEWOPTS 1 1 0 1 1 1803 }