{VERSION 6 0 "SUN SPARC SOLARIS" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 1 24 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 257 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 1 24 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 12 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 291 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 296 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 297 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 299 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 300 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 301 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 302 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 303 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 304 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 305 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 306 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 307 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 308 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 309 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 310 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 311 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 312 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 313 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 314 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 315 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 316 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 317 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 318 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 319 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 320 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 321 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 322 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 323 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 324 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 325 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 326 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 327 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 328 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 329 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 330 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 331 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 332 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 333 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 334 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 335 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 336 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 337 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 338 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 339 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 340 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 341 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 342 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 343 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 344 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 345 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 346 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 347 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 348 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 349 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 350 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 351 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 352 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 353 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 354 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 355 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 356 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 357 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 358 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 359 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 360 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 361 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 362 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 363 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 364 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 365 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 366 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 367 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 368 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 369 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 370 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 371 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 372 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 373 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 374 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 375 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 376 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 377 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 378 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 379 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 380 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 381 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 382 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 383 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 384 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 385 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 386 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 387 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 388 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 389 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 390 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 391 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 392 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 393 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 394 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 395 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 396 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 397 "" 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 398 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 399 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 400 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 401 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 402 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 403 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 404 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 405 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 406 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 407 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 408 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 409 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 410 "" 1 12 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 411 "" 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 412 "" 1 12 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 413 "" 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 414 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 415 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 416 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 417 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 418 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 419 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 420 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 421 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 422 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 423 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 424 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 425 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 426 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 427 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 428 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 429 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 430 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 431 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 432 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 433 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 434 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 435 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 436 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 437 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 438 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 439 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 440 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 441 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 442 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 443 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 444 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 445 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 446 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 447 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 448 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 449 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 450 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 451 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 452 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 453 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 454 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 455 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 456 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 457 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 458 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 459 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 460 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 461 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 462 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 463 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 464 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 465 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 466 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 467 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 468 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 469 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 470 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 471 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 472 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 473 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 474 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 475 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 476 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 477 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 478 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 479 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 480 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 481 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 482 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 485 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 486 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 487 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 488 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 489 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 490 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 491 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 492 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 493 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 494 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 495 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 496 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 500 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 503 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 504 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 505 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 506 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 507 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 508 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 509 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 510 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 511 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 512 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 513 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 516 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 520 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 521 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 525 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 526 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 528 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 529 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 530 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 531 "" 0 1 0 0 0 0 0 1 0 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 1 }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 }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 1 }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 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 0 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }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 1 }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 1 }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 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 261 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 262 1 {CSTYLE " " -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 263 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 264 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }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 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 266 1 {CSTYLE "" -1 -1 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 267 1 {CSTYLE "" -1 -1 "" 0 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 379 0 "" }{TEXT 256 18 "Polynomia l Ideals." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "Let " }{TEXT 398 1 "F" }{TEXT -1 46 "=\{f1,f2,..,fm\} be a finite s et of elements of " }{TEXT 399 1 "R" }{TEXT -1 1 "=" }{TEXT 400 1 "Q" }{TEXT -1 51 "[x1,x2,..,xn]. The ideal generated by the set F is:" }} {PARA 0 "" 0 "" {TEXT 401 1 "I" }{TEXT -1 4 " = (" }{TEXT 402 1 "F" } {TEXT -1 50 ") = (f1,f2,...,fm) = \{ a1*f1+..+am*fm | a1..am in " } {TEXT 403 2 "R " }{TEXT -1 2 "\}." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 257 0 "" }{TEXT 258 53 "Central p roblem for computing with polynomial ideals:" }}{PARA 256 "" 0 "" {TEXT -1 19 "Given a finite set " }{TEXT 404 1 "F" }{TEXT -1 16 " of p olynomials " }{TEXT 405 1 "F" }{TEXT -1 18 "=\{f1,f2,..,fm\} in " } {TEXT 406 1 "R" }{TEXT -1 1 "=" }{TEXT 407 1 "Q" }{TEXT -1 11 "[x1,.., xn]." }}{PARA 267 "" 0 "" {TEXT -1 16 "Given some g in " }{TEXT 408 1 "R" }{TEXT -1 31 ", how can we check if g is in (" }{TEXT 409 1 "F" } {TEXT -1 2 ")?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 266 "" 0 "" {TEXT 259 15 "Second Problem:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 397 30 "And, if g turns out to be in (" }{TEXT 410 1 "F" }{TEXT 411 61 "), in other words: g=a1*f1+...+am*fm for some a1,a2,..,am in " } {TEXT 412 1 "R" }{TEXT 413 35 ", how then can we find such a1..am?" } {TEXT -1 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 26 "Ideals and radic al ideals." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 266 30 "Interpretation of ideal I=(F)." }{TEXT -1 148 " One way to th ink about this ideal is the following: Think of the polynomials f1,f2, ..,fm as equations in the variables x1,x2,..xn. Then the ideal " } {TEXT 415 1 "I" }{TEXT -1 103 " is the set of all equations that follo w from the equations f1,f2,..,fm using the following operations:" }} {PARA 0 "" 0 "" {TEXT -1 38 " 1) multiplication with polynomials" } }{PARA 0 "" 0 "" {TEXT -1 17 " 2) additions." }}{PARA 0 "" 0 "" {TEXT -1 3 "So " }{TEXT 414 1 "I" }{TEXT -1 181 " is the set of all R- linear combinations of f1,f2,..,fm. Clearly, if the equations f1=0, f 2=0, .. ,fm=0 have a common solution (x1..xn)=(alpha.1, .. alpha.n) th en every element of " }{TEXT 416 1 "I" }{TEXT -1 55 " has must also ha ve the solution (alpha.1, .. alpha.n)." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 134 "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 " }{TEXT 417 1 "I" }{TEXT -1 51 ", then th e system f1=f2=...=fm=0 has no solutions. " }{TEXT 267 25 "Hilbert's N ullstellensatz" }{TEXT -1 148 " implies 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 371 1 "C" }{TEXT -1 44 "^n, then 1 is an element of the ideal. Here " }{TEXT 372 1 "C" } {TEXT -1 25 " are the complex numbers." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 235 "Note that when you view f1, f2,.., f m as equations (f1=f2=...=fm=0) then there could be equations that can be derived from the equations f1,..,fm but that can not be obtained u sing just operations 1) and 2) above. Namely the following:" }}{PARA 0 "" 0 "" {TEXT -1 37 "suppose f is an element of the ideal " }{TEXT 418 1 "I" }{TEXT -1 368 "=(f1,..,fm), and suppose f = g^n for some po lynomial g and some positive integer n. 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 con clude: g=0. It turns out if we include these polynomials g as well, th en 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 268 12 "Definition: " }}{PARA 0 "" 0 " " {TEXT -1 56 "Let F = \{f1,f2,..,fm\} be a set of polynomials. Then t he " }{TEXT 269 13 "radical ideal" }{TEXT 378 1 " " }{TEXT -1 92 "of t he ideal (F) is the collection of all polynomials that can be obtained from f1,..,fm by:" }}{PARA 0 "" 0 "" {TEXT -1 36 " 1) multiplicatio ns by polynomials" }}{PARA 0 "" 0 "" {TEXT -1 16 " 2) additions." }} {PARA 0 "" 0 "" {TEXT -1 72 " 3) Whenever g^n, n>1 is in our collect ion, then we include g as well." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 3 "So " }{TEXT 375 45 "an ideal is closed und er operations 1) and 2)" }{TEXT -1 8 ", and a " }{TEXT 376 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 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 272 26 "Hilbert's Nullstellensatz," }{TEXT -1 33 " th e radical ideal is the set of " }{TEXT 270 3 "all" }{TEXT -1 31 " cons equences of f1=f2=..=fm=0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 271 25 "Hilbert's Nullstellensatz" }{TEXT -1 132 " says \+ that: g is in the radical ideal if and only if g(alpha1,..,alpha.n)=0 for all solutions (alpha.1,.,alpha.n) of f1=f2=..=fm=0." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 161 "In other words: I f f1,..,fm and g are in R, then g is in the radical ideal of f1,..fm i f and only if the following is true:\nFor every point (alpha1..alpha.n ) in " }{TEXT 419 1 "C" }{TEXT -1 86 "^n, if this point is a common so lution of f1,..,fm then it is a solution of g as well." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 327 11 "Definition:" }} {PARA 0 "" 0 "" {TEXT -1 20 "Let R be a ring. An " }{TEXT 377 25 "asce nding chain of ideals" }{TEXT -1 26 " is a sequence of ideals " } {TEXT 420 1 "I" }{TEXT -1 3 "1, " }{TEXT 421 1 "I" }{TEXT -1 3 "2, " } {TEXT 422 1 "I" }{TEXT -1 17 "3, ... such that " }{TEXT 328 1 "I" } {TEXT 423 7 ".i is a" }{TEXT 424 15 " proper subset " }{TEXT 425 3 "of " }{TEXT 426 2 "I." }{TEXT 427 5 "(i+1)" }{TEXT -1 12 " for each i." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 330 11 "Defini tion:" }}{PARA 0 "" 0 "" {TEXT -1 12 "R is called " }{TEXT 331 10 "Noe therian" }{TEXT -1 136 " when R has no infinitely long ascending chain s of ideals. So every ascending (i.e. increasing) chain of ideals must be a finite chain: " }{TEXT 485 1 "I" }{TEXT -1 3 "1, " }{TEXT 486 1 "I" }{TEXT -1 6 "2,.., " }{TEXT 487 2 "I." }{TEXT -1 60 "n (finite mea ning that there is a last, i.e. largest, ideal " }{TEXT 488 1 "I" } {TEXT -1 18 ".n in that chain)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 4 "Let " }{TEXT 431 1 "I" }{TEXT -1 3 "1, " } {TEXT 432 1 "I" }{TEXT -1 40 "2, ... be ideals in R, and suppose that \+ " }{TEXT 329 1 "I" }{TEXT 428 17 ".i is a subset of" }{TEXT 430 2 " I " }{TEXT 429 6 ".(i+1)" }{TEXT -1 80 " for each i. If R is Noetherian \+ then that means there must exist an n such that " }{TEXT 433 2 "I." } {TEXT -1 4 "n = " }{TEXT 434 2 "I." }{TEXT -1 14 "m for all m>n." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 332 9 "Examples: " }}{PARA 0 "" 0 "" {TEXT 435 1 "Q" }{TEXT -1 8 "[x] and " }{TEXT 436 1 "Z" }{TEXT -1 5 " and " }{TEXT 437 1 "Z" }{TEXT -1 19 "[x] are Noeth erian." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 333 12 "Proposition:" }}{PARA 0 "" 0 "" {TEXT -1 50 "A ring R is Noetheria n if and only if every ideal " }{TEXT 438 1 "I" }{TEXT -1 23 " is fini tely generated." }}{PARA 0 "" 0 "" {TEXT -1 32 "This means that for ev ery ideal " }{TEXT 439 1 "I" }{TEXT -1 31 ", there exists a finite sub set " }{TEXT 440 1 "F" }{TEXT -1 15 "=\{f1,..,fm\} of " }{TEXT 441 1 " R" }{TEXT -1 11 " such that " }{TEXT 442 1 "I" }{TEXT -1 2 "=(" } {TEXT 443 1 "F" }{TEXT -1 2 ")." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } {TEXT 334 6 "Proof:" }}{PARA 0 "" 0 "" {TEXT -1 4 "Let " }{TEXT 489 1 "I" }{TEXT -1 65 " be an ideal, and let F=\{\}. As long as (F) is a pr oper subset of " }{TEXT 490 1 "I" }{TEXT -1 21 ", take an element of \+ " }{TEXT 491 1 "I" }{TEXT -1 215 " but not in (F), and put that elemen t in the set F. This way, the ideals (F) we encounter form an ascendin g sequence, and when R is Noetherian this sequence must be finite, and so it must end. But it only ends when " }{TEXT 492 1 "I" }{TEXT -1 45 "=(F). Hence we find a finite set F such that " }{TEXT 493 1 "I" } {TEXT -1 9 "=(F), so " }{TEXT 494 1 "I" }{TEXT -1 130 " is generated b y finitely many elements, namely the elements of F. I will leave the p roof of the converse statement to the reader." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 335 26 "Hilbert's basis theorem: " }{TEXT -1 3 "If " }{TEXT 495 1 "R" }{TEXT -1 26 " is Noetherian th en so is " }{TEXT 496 1 "R" }{TEXT -1 4 "[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 10 "Note that " }{TEXT 444 1 "Q" }{TEXT -1 81 ", the field of rational numbers, has only two ideals , namely (0) = \{0\} and (1) = " }{TEXT 445 1 "Q" }{TEXT -1 126 ". Hen ce it is Noetherian. According to Hilbert's basis theorem, every time \+ we add one variable, the ring stays Noetherian. So " }{TEXT 446 1 "Q" }{TEXT -1 2 ", " }{TEXT 447 1 "Q" }{TEXT -1 6 "[x1], " }{TEXT 448 1 "Q " }{TEXT -1 9 "[x1,x2], " }{TEXT 449 1 "Q" }{TEXT -1 43 "[x1,x2,x3], . .. are all Noetherian. Hence:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 336 10 "Corollary:" }}{PARA 0 "" 0 "" {TEXT 500 107 "Q[x1,x2,..,xn] is Noetherian; for every ideal I in Q[x1,..,xn] th ere exists a finite set F such that I=(F)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 373 8 "Remark: " }{TEXT -1 18 "In this worksheet " }{TEXT 374 70 "we will only study ideals that are given b y a finite set of generators" }{TEXT -1 134 ". But according to the co rollary, that is OK, it does not leave out any ideals because there al ways exists a finite set of generators." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 48 "Solution to the Central Pro blem: Groebner basis." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 107 "It turns out that when the central problem can be han dled, then we can find a method to compute answers to " }{TEXT 450 4 " many" }{TEXT -1 214 " (it almost seems: pretty much all) computational problems involving polynomial equations or polynomial ideals. An exam ple of such computational problem is the following, given polynomials \+ f1,..,fm, the problem is:" }}{PARA 0 "" 0 "" {TEXT -1 101 " \"are t he equations f1=0, f2=0,..,fm=0 consistent, in other words, does a com mon solution exist?\"." }}{PARA 0 "" 0 "" {TEXT -1 227 "It is consiste nt 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 als o look at many other problems that can be reduced to the central probl em." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "Th e method of solving the central problem is to compute a " }{TEXT 273 17 "Groebner basis G " }{TEXT -1 13 "of the ideal " }{TEXT 451 1 "I" } {TEXT -1 5 "=(F)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 274 19 "Partial Definition:" }{TEXT -1 32 " A Groebner basis G o f an ideal " }{TEXT 452 1 "I" }{TEXT -1 58 " is a finite set of polyno mials G=\{g1,g2,..,gk\} such that:" }}{PARA 0 "" 0 "" {TEXT -1 26 " 1) G spans the ideal, so " }{TEXT 503 1 "I" }{TEXT -1 5 "=(G)." }}{PARA 0 "" 0 "" {TEXT -1 114 " 2) G has an additional property (to be define d later) that will make it easy to answer the central problem above." }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 33 "Two easy cases of Groebner bas es." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 30 "We 'll do two easy cases first:" }}{PARA 0 "" 0 "" {TEXT 260 13 "Easy cas e 1):" }{TEXT -1 36 " n=1, so we have only one variable." }}{PARA 0 " " 0 "" {TEXT 261 12 "Easy case 2)" }{TEXT -1 95 ": n>1, but now degre e(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 264 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 polynomials f1..fm, which we can do with the following algorit hm:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 990 "case1:=proc(F::set, \+ x::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_case1(i,x);\n lj := leading_m onomial_case1(j,x);\n if type(li/lj, polynom) then\n # Th e leading monomial of i is divisible by\n # the leading monomi al of j, so we can reduce\n # i modulo j.\n # We will \+ compute k, such that i and k are the same\n # modulo j, in suc h a way that k has a smaller\n # leading monomial (i.e. lower \+ degree) than i\n k := i - li/lj * j;\n k := primpart(k );\n # Since i and k are the same modulo j,\n # and j \+ is in G minus \{i\},\n # the ideal will not change if we repla ce\n # i by k as follows:\n G := ((G minus \{i\}) unio n \{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: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 100 "leading_monomial_case1:=proc(F,x)\n # Compute the highest t erm.\n lcoeff(F,x) * x^degree(F,x)\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 260 "Of course, the only thing that algorithm case1 does is c omputing the gcd of f1,f2,...,fm. So we could have done a simpler impl ementation using Maple's gcd implementation. However, note the similar ities with the implementation of case 2 later in this worksheet." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "f1 , f2, f3 := x^6-x^3, x^8 -x^3, x^12-x^7;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6%%#f1G%#f2G%#f3G 6%,&*$)%\"xG\"\"'\"\"\"F.*$)F,\"\"$F.!\"\",&*$)F,\"\")F.F.F/F2,&*$)F, \"#7F.F.*$)F,\"\"(F.F2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "F := \{f1,f2,f3\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG<%,&*$)%\"x G\"\"'\"\"\"F+*$)F)\"\"$F+!\"\",&*$)F)\"\")F+F+F,F/,&*$)F)\"#7F+F+*$)F )\"\"(F+F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "G := case1(F \+ ,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG<#,&*$)%\"xG\"\"$\"\"\"! \"\"*$)F)\"\"%F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "G := \+ \{ expand(gcd(gcd(f1,f2), f3)) \};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%\"GG<#,&*$)%\"xG\"\"$\"\"\"!\"\"*$)F)\"\"%F+F+" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 86 "Using this Groebner basis G, the solution to the c entral problem is now the following:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 16 " g in (F) " }{TEXT 453 4 "<==>" } {TEXT -1 14 " g in (G) " }{TEXT 454 4 "<==>" }{TEXT -1 54 " the \+ remainder of g modulo the element in G is zero." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "g := x^7+x^ 8; remainder := rem(g,G[1],x); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"gG,&*$)%\"xG\"\"(\"\"\"F**$)F(\"\")F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*remainderG,$*&\"\"#\"\"\")%\"xG\"\"$F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Non-zero remainder, so g was not in (F). " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "g := x^15-2*x^13+x^11; \+ remainder := rem(g,G[1],x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"g G,(*$)%\"xG\"#:\"\"\"F**&\"\"#F*)F(\"#8F*!\"\"*$)F(\"#6F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*remainderG\"\"!" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 37 "zero remainder, so this g was in (F)." }}{PARA 0 "" 0 " " {TEXT -1 18 "Now we'll look at " }{TEXT 265 7 "case 2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 807 "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 := l eading_monomial_case2(j,list_vars);\n if type(li/lj, polynom) the n\n # The leading monomial of i is divisible by\n # th e leading monomial of j, so we can reduce\n # i modulo j. So \+ let k be i reduced modulo j.\n k := i - li/lj * j;\n # Then: replace i by k, which has a \"smaller\"\n # leading mon omial. This process will end, because\n # we're making leading monomials smaller and smaller\n # until we can reduce them no more.\n G := ((G minus \{i\}) union \{k\}) minus \{0\}\n \+ fi\n od od\n od;\n G\nend: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 590 "leading_monomial_case2:=proc(f, list_vars)\n # Ass umption: f is linear in the variables.\n # What is the leading monom ial, 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 (times its coefficient)\n # is the l eading 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 foll owing 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:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "f1 := x1+2*x2+3*x3+4*x4:" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "f2 := x1+3*x2+5*x3+7*x4:" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "f3 := x1+4*x2+9*x3+16*x4: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "F := \{f1,f2,f3\};\nvar s := [x1,x2,x3,x4];\nG := case2(F,vars);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG<%,*%#x1G\"\"\"*&\"\"#F(%#x2GF(F(*&\"\"$F(%#x3GF(F(*&\"\"% F(%#x4GF(F(,*F'F(*&F-F(F+F(F(*&\"\"&F(F.F(F(*&\"\"(F(F1F(F(,*F'F(*&F0F (F+F(F(*&\"\"*F(F.F(F(*&\"#;F(F1F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%%varsG7&%#x1G%#x2G%#x3G%#x4G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"GG<%,*%#x1G\"\"\"*&\"\"%F(%#x2GF(F(*&\"\"*F(%#x3GF(F(*&\"#;F(%#x4GF( F(,(F+!\"\"*&F*F(F.F(F3*&F-F(F1F(F3,&*&\"\"#F(F.F(F(*&\"\"'F(F1F(F(" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 26 "We see that the algorithm " } {TEXT 263 6 "case2 " }{TEXT -1 87 "has brought the linear equations f1 ,f2,f3 in a form that in linear algebra is called: " }{TEXT 262 21 "u pper triangular form" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 16 "We had an ideal " }{TEXT 504 1 "I" } {TEXT -1 92 " generated by the set F = \{f1,f2,f3\} and what we have f ound is another set of generators G. " }}{PARA 0 "" 0 "" {TEXT -1 3 "S o " }{TEXT 505 1 "I" }{TEXT -1 53 " = (F) = (G). But this new set of \+ generators G is a " }{TEXT 455 24 "better set of generators" }{TEXT -1 27 " than the old generators F," }}{PARA 0 "" 0 "" {TEXT -1 77 "bet ter in the following sense: if we want to test if some polynomial g is in " }{TEXT 506 1 "I" }{TEXT -1 31 ", then this will be much easier" }}{PARA 0 "" 0 "" {TEXT -1 82 "if we use G instead of F (because G i s in upper triangular form while F is not)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "First we number the elements of G as follows: Take g1 as the element of G that has x1," }}{PARA 0 " " 0 "" {TEXT -1 103 "Then take g2 as the element of G that is not g1, \+ and that has x2, and let g3 be the remaining element." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 206 "if has(G[1],x1) then g1:=G[1]\ne lif has(G[2],x1) then g1:=G[2]\nelse g1:=G[3]\nfi;\n GG:=G minus \{g1\}:\nif has(GG[1],x2) then\n g2 := GG[1]; g3 := GG[ 2]\nelse\n g2 := GG[2]; g3 := GG[1]\nfi;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g1G,*%#x1G\"\"\"*&\"\"%F'%#x2GF'F'*&\"\"*F'%#x3GF'F' *&\"#;F'%#x4GF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g2G,(%#x2G!\" \"*&\"\"%\"\"\"%#x3GF*F'*&\"\"*F*%#x4GF*F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g3G,&*&\"\"#\"\"\"%#x3GF(F(*&\"\"'F(%#x4GF(F(" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "Now G=\{g1,g2,g3\} generates the i deal " }{TEXT 507 1 "I" }{TEXT -1 19 ", in other words: " }{TEXT 508 1 "I" }{TEXT -1 20 " = (G) = (g1,g2,g3)." }}{PARA 0 "" 0 "" {TEXT -1 55 "Take some abritrary polynomial g. To check if it is in " }{TEXT 509 1 "I" }{TEXT -1 26 ", all we have to do now is" }}{PARA 0 "" 0 "" {TEXT -1 65 "reduce that polynomial modulo g1,g2,g3 and look at the re mainder:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "g := x1^2+x2^2+ x3^2+x4^2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,**$)%#x1G\"\"#\" \"\"F**$)%#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\"\"#F&F&" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "Not zero, so g was not in the idea l." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 19 "Let s 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\" \"$\"\"\"F**$)%#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,x 3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{PARA 0 "" 0 "" {TEXT -1 57 "So this g has remainder 0 modulo G, so g is in the ideal \+ " }{TEXT 510 1 "I" }{TEXT -1 13 " = (F) = (G)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 34 "The above tests to see if g is in " }{TEXT 511 1 "I" }{TEXT -1 67 " would not have worked if we had used f1,f2,f3 instead of g1,g2,g3," }}{PARA 0 "" 0 "" {TEXT -1 71 "and it is in this sense that g1,g2,g3 is a better set of generator s (a " }{TEXT 456 14 "Groebner basis" }{TEXT -1 15 ") of the ideal " } {TEXT 516 1 "I" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 34 "Recall that the fact that g is in " } {TEXT 512 1 "I" }{TEXT -1 56 " = (F) means there exist polynomials a1, a2,a3 such that:" }}{PARA 0 "" 0 "" {TEXT -1 47 " g = a1*f1+a2* f2+a3*f3.\nLikewise, since " }{TEXT 513 1 "I" }{TEXT -1 89 " is also e qual to (G)=(g1,g2,g3), the polynomial g must also be a combination of g1,g2,g3" }}{PARA 0 "" 0 "" {TEXT -1 35 "(which is what we actually t ested)." }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 39 "What do these two cas es 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 382 8 "case 1) " }{TEXT -1 33 " just 1 va riable, but any degree." }}{PARA 0 "" 0 "" {TEXT 383 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 384 59 "only real d ifference was in the procedure leading_monomial." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 275 12 "What is the " }{TEXT 380 16 "leading monomial" }{TEXT 381 17 " of a polynomial?" }}{PARA 0 "" 0 "" {TEXT -1 113 "For case 1, there was an obvious choice as for w hich monomial is the largest one. For example, in the polynomial:" }} {PARA 0 "" 0 "" {TEXT -1 31 " 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 "F or case 2, however, there is no obvious choice. For example, in the po lynomial" }}{PARA 0 "" 0 "" {TEXT -1 23 " 2*x1+3*x2+4*x3+5*x4" }} {PARA 0 "" 0 "" {TEXT -1 48 "it is not clear what the \"largest\" mono mial is. " }{TEXT 276 82 "To decide which monomial we think of as the \+ largest, we need to choose an ordering" }{TEXT -1 241 ". We picked the ordering x1>x2>x3>x4, making 2*x1 the leading 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 " }{TEXT 457 94 " another ordering would have been j ust fine, as long as we consistently use the same ordering." }{TEXT -1 259 " In the algorithm leading_monomial_case2 we can order the vari ables in any way we want to, but we have to use the same ordering ever y time because otherwise the algorithm case2 will probably not work. S ince there are many different ways to order the variables" }{TEXT 277 34 ", we'll have to choose an ordering" }{TEXT -1 108 " (but once it i s chosen, we'll have to keep using the same ordering throughout all co mputations that we do)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 109 "In the general case, i.e. not case 1 and case 2, we will see that we again need an ordering on the monomials." }}{PARA 0 "" 0 "" {TEXT -1 53 "Given a polynomial like for example: x1*x2 + 3* x3^5" }}{PARA 0 "" 0 "" {TEXT -1 604 "it makes a priori no sense to sa y which of the two monomials is the largest one. We would first have t o define some ordering on these monomials, and only then can we say wh ich one is the largest. Once we've decided which ordering to use, then the strategy will be to pick elements i,j in the set G like in the al gorithms case1 and case2, then we look at the leading monomials of i a nd j, and if lj:=leading_monomial(j) divides li:=leading_monomial(i) \+ (so if li/lj is a polynomial) then we can make the leading monomial \+ of i smaller by doing the following:\n\n replace i by i - li/ lj * j (***)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 115 "So: Once we have chosen an ordering, from that moment on it makes sense to say which is the largest monomial, the l" }{TEXT 278 16 "eading monomial," }{TEXT -1 192 " of a polynomial. Given a set of polynomials G=\{g1,g2,..\}, we can try to make an element i of G \+ \"smaller\" by substracting a suitable multiple of another element j o f G, like in equation (***)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 42 "If i' = i-li/lj * j then we will say that " } {TEXT 280 27 "i reduces to i' w.r.t. j. " }{TEXT -1 236 "When we repl ace i by i' in G, we see that G still spans the same ideal, but now o ne 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 279 16 "reduce the set G" }{TEXT -1 271 " w hen we reduce some element i of G w.r.t. some other element j of G. W hen we can reduce the set G no further (so when there are no two disti nct 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 281 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 385 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 386 50 "For the more general case, thi s is no longer true." }{TEXT -1 228 " 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 no longer be sufficient f or handling the central problem, we'll have to do more." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 81 "The Maple procedure \+ for computing the leading monomial of a polynomial is called " }{TEXT 387 7 "leadmon" }{TEXT -1 176 ". The input of this procedure must be n ot only the polynomial, but the ordering as well, since the leading mo nomial depends on that ordering. To use this function, first type " } {TEXT 388 14 "with(Groebner)" }{TEXT -1 40 ", in order to load the Gro ebner package." }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 23 "Orderings on m onomials." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "If 7*x1^3*x2^5 is the " }{TEXT 282 16 "leading monomial" }{TEXT -1 88 " of some polynomial, then we will call the coefficient (which i s 7 in this example) the " }{TEXT 283 19 "leading coefficient" }{TEXT -1 23 ", and x1^3*x2^5 is the " }{TEXT 284 23 "leading power product. \+ " }{TEXT -1 20 "The Maple procedure " }{TEXT 285 7 "leadmon" }{TEXT -1 8 " in the " }{TEXT 286 16 "Groebner package" }{TEXT -1 296 " takes as input: a polynomial and an ordering. The output is a sequence cons isting of the leading coefficient and the leading power product. In th e 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 corresponding non-zero co efficient." }}{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 287 12 "Definition: " }{TEXT -1 73 "[x1,..,xn] = \{x1^i1 *..* xn^in, w here i1,..,in are nonnegative integers\}." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "In this notation " }{TEXT 458 1 "Q " }{TEXT -1 16 "[x1,..,xn] is a " }{TEXT 459 1 "Q" }{TEXT -1 65 "-vect or space with basis [x1,..,xn]=\{1,x1,x2,..,x1^2,x1*x2,....\}." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 288 10 "Notation : " }{TEXT -1 15 "We will denote " }{TEXT 294 12 "x1,x2,..,xn " } {TEXT -1 3 "as " }{TEXT 295 1 "X" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 3 "So " }{TEXT 296 4 "Q[X]" }{TEXT -1 12 " stands for " } {TEXT 297 14 "Q[x1,x2,..,xn]" }{TEXT -1 8 ". And " }{TEXT 298 3 "[X] " }{TEXT -1 56 " stands for the set of all power products in x1,x2,..x n." }}{PARA 0 "" 0 "" {TEXT -1 22 "If e is an element of " }{TEXT 299 3 "N^n" }{TEXT -1 8 ", where " }{TEXT 460 1 "N" }{TEXT -1 43 " is the \+ set of non-negative integers, then " }{TEXT 300 16 "e=(e1,e2,..,en) " }{TEXT -1 62 "where the e.i are integers. Then we will denote the mono mial: " }{TEXT 292 21 "x1^e1*x2^e2*...*xn^en" }{TEXT -1 19 " more bri efly as: " }{TEXT 293 3 "X^e" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 110 "The set [X] is a commutative m onoid (that just means that the product of two elements of [X] is agai n in [X])." }}{PARA 0 "" 0 "" {TEXT -1 58 "The map e -> X^e is an isom orphism of the additive monoid " }{TEXT 461 1 "N" }{TEXT -1 36 "^n to \+ the multiplicative monoid [X]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 289 10 "Definition" }{TEXT -1 36 ": An ordering \+ < on [X] is called an " }{TEXT 290 19 "admissible ordering" }{TEXT -1 6 " when:" }}{PARA 0 "" 0 "" {TEXT -1 58 "1) The element 1 in [X] is s maller 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 10 "3) < is a " }{TEXT 462 17 "complete ordering" }{TEXT -1 120 ", \+ which means that if s,t in [X], then precisely one of the following th ree holds:\n s X^e) to orderings on [X]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 291 39 "Three examples of a dmissible orderings:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 257 "" 0 "" {TEXT -1 6 "pure l" }{TEXT 301 22 "exicographic ordering:" }} {PARA 258 "" 0 "" {TEXT 302 33 "Maple notation: plex(x1,x2,..,xn)" }} {PARA 0 "" 0 "" {TEXT -1 65 "If d=(d1,d2,..,dn) and e=(e1,e2,..,en) th en we say that d e.i, and if then d.i < e.i then d is the sma llest, otherwise e is the smallest." }}{PARA 0 "" 0 "" {TEXT -1 36 "In the pure lexicographic ordering " }{TEXT 305 17 "plex(x1,x2,..,xn)" }{TEXT -1 10 " one has: " }{TEXT 304 12 "x1>x2>...>xn" }{TEXT -1 11 ", and even:" }}{PARA 0 "" 0 "" {TEXT 303 51 " x1 is bigger than any el ement of [x2,x3,...,xn]." }}{PARA 0 "" 0 "" {TEXT 306 55 " x2 is big ger than any element of [x3,x4,..,xn], etc." }}{PARA 0 "" 0 "" {TEXT 309 9 "Example: " }{TEXT -1 490 "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 m onomial is: 2*x1^2. The second largest monomial is -4*x1*x2^4, the thi rd 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 th e alphabetical ordering, then at first you only look at the first lett er 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 307 22 "Total degree ordering:" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }{TEXT 308 33 "Maple 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 monomial X^e=x1^e1*...*xn^en (or t he \"total degree\") equals e1+e2+...+en. A total degree ordering is a n ordering such that:" }}{PARA 0 "" 0 "" {TEXT -1 34 "If d1+..+dn < e1 +...+en then d 1 then there exist infinitely many (even: uncountably many) different \+ admissible orderings on [X]. To see more examples type ?Groebner,termo rder in Maple." }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 60 "Reducing a set of polynomials w.r.t. an admissible ordering." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 80 "In the two easy cases, we started with a set F=\{f1,f2,...,fm\} of polynomials in " }{TEXT 520 1 "Q" }{TEXT -1 4 "[X]=" }{TEXT 521 1 "Q" }{TEXT -1 57 "[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 t he zeros." }}{PARA 0 "" 0 "" {TEXT -1 274 "Then: whenever you have two different elements i and j in G, and if the leading monomial lj of j \+ divides the leading monomial 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 68 " To decide what the leading monomial was, we had to pick an ordering." }}{PARA 0 "" 0 "" {TEXT -1 87 "In case 1), the only monomials where po wers 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]) ;\n# 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 596 "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, it cancels. This way, leading monomials will get smaller and smaller during the computation in the \+ following algorithm. Note the similarity with the implementations case 1 and case2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 975 "reduce_pol ynomials:=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[leadmon](i,ord);\n lj:=Groebne r[leadmon](j,ord);\n if type(li[2]/lj[2], polynom) then\n \+ # The leading monomial of i is divisible by\n # the leading m onomial of j, so we can reduce i modulo j.\n k := i - li[1]/lj [1] * li[2]/lj[2] * j;\n # Now k is the reduction of i modulo \+ j, but because we cancelled\n # the leading monomial of i, we \+ get that k has a smaller leading\n # monomial than i. The ide al will not change if we replace i\n # by k (or by primpart(k) ) because i,k are congruent modulo j\n # and j is in G minus \+ \{i\}.\n G := ((G minus \{i\}) union \{primpart(k)\}) minus \{ 0\}\n # Now we've made a leading monomial in G smaller,\n \+ # and eventually this process will end (why?...)\n fi\n o d od\n od;\n G\nend: " }}}{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(%#x3GF(F(!\"\",&*(F'F(F)F (F*F(F(F(F+,(*$)F'\"\"#F(F(*&F1F()F)F1F(F(*&\"\"$F()F*F1F(F(" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "G:=reduce_polynomials(F,ord) ; # The reduced set" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG<%,*%#x1G \"\"\"%#x2GF(%#x3GF(F(!\"\",.*&\"\"$F()F)\"\"#F(F(*&F.F()F*F0F(F(*&F'F (F*F(F+F'F(*&F)F(F*F(F(F)F+,.F.F+*&F)F(F2F(F+F4F(*&\"\"%F()F*F.F(F(*&F 0F(F2F(F+F*F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "GB:=gbasis (F,ord); # The Groebner basis." }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#G BG7&,.\"\"*!\"\"*&\"#:\"\"\")%#x3G\"\"$F+F+*&\"#>F+)F-\"\"#F+F(F-F(*& \"#?F+)F-\"\"&F+F+*&\"\"'F+)F-\"\"%F+F(,0*&F4F+F9F+F+*&F8F+F,F+F(*&F.F +F1F+F+*&F.F+%#x2GF+F(*(F.F+F@F+F-F+F+*&\"#8F+F-F+F(F:F(,*%#x1GF+F@F+F -F+F+F(,.*&F'F+)F@F2F+F+*&\"#SF+F9F+F(*&\"#7F+F,F+F+*&F8F+F1F+F+*&F4F+ F-F+F+\"#6F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "g:=op( sele ct(i -> not has(i,\{x1,x2\}), GB) );" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%\"gG,.\"\"*!\"\"*&\"#:\"\"\")%#x3G\"\"$F*F**&\"#>F*)F,\"\"#F*F'F,F '*&\"#?F*)F,\"\"&F*F**&\"\"'F*)F,\"\"%F*F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 108 "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 22 " (F)=(G)=(GB)." }}{PARA 0 "" 0 "" {TEXT -1 338 "Given the set F it is hard to tell that g is an element of (F). Given the set G, it is still hard to see whether g is an element of the ide al (F)=(G) or not. Therefore, simply reducing a set like we did in the algorithm above is not sufficient to handle the central problem, whic h means that our reduced set G is not yet a Groebner basis." }}}} {SECT 0 {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 502 "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 divisib le by\n # the leading monomial of j, so we can reduce i modulo j.\n k := i - li[1]/lj[1] * li[2]/lj[2] * j;\n i := p rimpart(k);\n fi\n od\n od;\n i\nend: " }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "Note that the prev ious algorithm reduce_polynomials is now the same as this algorithm:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 220 "reduce_polynomials:=proc (F,ord)\n local i,G,k;\n G:=F minus \{0\};\n for i in G do\n k: =reduce_poly(i, G minus \{i\}, ord);\n if k<>i then\n retu rn procname((G minus \{i\}) union \{k\}, ord)\n fi\n od;\n G\nen d: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "F;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<%,*%#x1G\"\"\"%#x2GF&%#x3GF&F&!\"\",&*(F%F&F'F&F(F& F&F&F),(*$)F%\"\"#F&F&*&F/F&)F'F/F&F&*&\"\"$F&)F(F/F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "G:=reduce_polynomials(F,ord);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG<%,*%#x1G\"\"\"%#x2GF(%#x3GF(F(! \"\",.*&\"\"$F()F)\"\"#F(F(*&F.F()F*F0F(F(*&F'F(F*F(F+F'F(*&F)F(F*F(F( F)F+,.F.F+*&F)F(F2F(F+F4F(*&\"\"%F()F*F.F(F(*&F0F(F2F(F+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*F%*&\"#?F()F*\"\"&F(F( *&\"\"'F()F*\"\"%F(F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "re duce_poly(g,G,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,.\"\"*!\"\"*& \"#:\"\"\")%#x3G\"\"$F(F(*&\"#>F()F*\"\"#F(F%F*F%*&\"#?F()F*\"\"&F(F(* &\"\"'F()F*\"\"%F(F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "red uce_poly(g,GB,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 90 "The procedure reduce_poly is imple mented in Maple in the Groebner package, under the name " }{TEXT 312 7 "reduce." }}{PARA 0 "" 0 "" {TEXT -1 152 "To use this function reduc e, we first have to load the Groebner package with the command with(Gr oebner), which we already 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*F%*&\"#?F()F*\"\"&F(F(*&\"\"'F()F*\"\"%F(F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "reduce(g,GB,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 261 "" 0 "" {TEXT 318 11 "Defini tion:" }{TEXT -1 27 " Let I be an ideal and let " }{TEXT 314 3 "ord" } {TEXT -1 57 " be an ordering. Then a set of polynomials G is called a \+ " }{TEXT 313 15 "Groebner basis " }{TEXT -1 37 "for the ideal I w.r.t. this ordering " }{TEXT 316 4 "ord " }{TEXT -1 5 "when:" }}{PARA 262 " " 0 "" {TEXT 315 42 " For every polynomial g in R, one has:" }} {PARA 263 "" 0 "" {TEXT 317 62 " 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 33 "In the above computation, we had " }{TEXT 463 1 "I " }{TEXT -1 76 "=(F), and ord was some elimination ordering. As we see from the definition, " }{TEXT 340 53 "the set G that we computed was \+ not a Groebner basis. " }{TEXT -1 117 "The set GB is a Groebner basis. So the gbasis command in the Groebner package does more than just red uce_polynomials." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 34 "You may wonder why the procedures " }{TEXT 319 18 "reduce _polynomials" }{TEXT -1 5 " and " }{TEXT 320 11 "reduce_poly" }{TEXT -1 33 " (which does exactly the same as " }{TEXT 321 6 "reduce" } {TEXT -1 56 " in the Groebner package) terminate. What the procedure \+ " }{TEXT 322 6 "reduce" }{TEXT -1 23 " does is the following:" }} {PARA 0 "" 0 "" {TEXT -1 21 "given one polynomial " }{TEXT 323 2 "f," }{TEXT -1 11 " and a set " }{TEXT 324 4 "poly" }{TEXT 525 1 "s" } {TEXT -1 43 " of some other polynomials, it will reduce " }{TEXT 464 1 "f" }{TEXT -1 57 " by substracting multiples of the other polynomial s from " }{TEXT 465 1 "f" }{TEXT -1 63 ". During each step, one of the following two things can happen:" }}{PARA 0 "" 0 "" {TEXT -1 8 " \+ 1) " }{TEXT 466 1 "f" }{TEXT -1 18 " becomes zero, or:" }}{PARA 0 "" 0 "" {TEXT -1 32 " 2) the leading monomial of " }{TEXT 467 1 "f" } {TEXT -1 17 " becomes smaller." }}{PARA 0 "" 0 "" {TEXT -1 110 "Let l1 , l2, l3,... be the sequence of leading monomials of f that occur duri ng this algorithm. So we see that:" }}{PARA 0 "" 0 "" {TEXT -1 18 "l1 \+ > l2 > l3 > ..." }}{PARA 0 "" 0 "" {TEXT -1 18 "Now the algorithm " } {TEXT 526 6 "reduce" }{TEXT -1 44 " terminates because of the followin g result:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 326 11 "Definition:" }{TEXT -1 109 " A well-ordering is an ordering fo r which an infinite decreasing sequence l1 > l2 > l3 > ... does not e xist." }}{PARA 0 "" 0 "" {TEXT 325 11 "Proposition" }{TEXT -1 60 ": if < is an admissible ordering, then < is a well-ordering." }}{PARA 0 " " 0 "" {TEXT 337 6 "Proof:" }}{PARA 0 "" 0 "" {TEXT -1 342 "If < is an admissible ordering, then l1 > l2 implies that l2 does not divide l1. Therefore, the ideal (l1) is a proper subset of the ideal (l1,l2). An d likewise, the ideal (l1,l2) is a proper subset of the ideal (l1,l2,l 3). 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 would allow any \+ ordering then the reduction need not terminate. For example, if we had the ordering 1 > x > x^2 > x^3 > ..., which is not a well-ordering, a nd 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 338 80 "in order for the reducti on process to terminate, we need to use a well-ordening." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 351 "We always use an \+ admissible ordering, so the proposition tells us that the algorithm re duce_poly will terminate. The algorithm reduce_polynomials terminates \+ as well. Note though that in the proof we only showed that a sequence \+ l1>l2>... must end, but our proof gives us no indication whatsoever in how long such a sequence could be. As a consequence, " }{TEXT 339 143 "although we have proven that the reduction process ends, the proo f gives us no method to find an upper bound for the number of reductio n steps." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 163 "Upper bounds (note that these will depend on the ordering that yo u use) do exist, but they tend to be very large. And indeed, the reduc tion can take quite a while." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 343 7 "Remark:" }{TEXT -1 100 " If G is a finite set o f polynomials, and g is a polynomial, and ord is an admissible orderin g then:" }}{PARA 0 "" 0 "" {TEXT 344 66 "The output of reduce(g, G, or d) is not always uniquely determined." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 179 "Why? Well, when G=\{f1,f2,..,fm\} th en 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 outpu t of " }{TEXT 345 18 "reduce_polynomials" }{TEXT -1 166 " is not uniqu ely determined. If you do a computation, and you restart Maple, and ap ply the algorithm on the same input you might get a different answer. \+ In the loop: " }{TEXT 346 21 "for i in G do ... od " }{TEXT -1 187 "th e variable i will 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. A nd the final result can depend on that order." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 89 "In Maple there are two co mmands that reduce a polynomial g modulo a set of polynomials G." }} {PARA 0 "" 0 "" {TEXT -1 3 "1) " }{TEXT 347 6 "reduce" }{TEXT -1 38 " \+ This procedure keeps on reducing g " }{TEXT 349 10 "until the " } {TEXT -1 1 "l" }{TEXT 350 47 "eading monomial of g can not be further \+ reduced" }{TEXT -1 50 ". It is the same as reduce_poly in this workshe et." }}{PARA 0 "" 0 "" {TEXT -1 3 "2) " }{TEXT 348 10 "normalf " } {TEXT -1 35 "This procedure keeps on reducing g " }{TEXT 351 52 "until none of the terms of g can be further reduced." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 389 8 "Remark: " }{TEXT -1 7 "In the " }{TEXT 390 19 "linear algebra case" }{TEXT -1 41 " (when all eq uations have degree 1) then " }{TEXT 391 5 "using" }{TEXT 469 1 " " } {TEXT 394 6 "reduce" }{TEXT 393 1 " " }{TEXT 470 39 "corresponds to br inging the matrix into" }{TEXT 471 18 " row echelon form " }{TEXT 468 25 "(= upper triangular form)" }{TEXT -1 9 " whereas " }{TEXT 392 5 "u sing" }{TEXT 472 1 " " }{TEXT 395 7 "normalf" }{TEXT 396 1 " " }{TEXT 473 39 "corresponds to bringing the matrix into" }{TEXT 474 25 " 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 68 "Fro m the definition, we see that G is a Groebner basis of the ideal " } {TEXT 475 1 "I" }{TEXT -1 34 " if and only if for all g we have:" }} {PARA 0 "" 0 "" {TEXT -1 17 " g in " }{TEXT 476 1 "I" } {TEXT 477 1 " " }{TEXT -1 35 "if and only if reduce(g, G, ord)=0." }} {PARA 0 "" 0 "" {TEXT -1 103 "So, if G is a Groebner basis, then the o utput of reduce(g, G, ord) is uniquely determined for all g in " } {TEXT 478 1 "I" }{TEXT -1 32 ", the output for those g's is 0." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 352 12 "Proposit ion:" }}{PARA 264 "" 0 "" {TEXT 353 85 "If G is a Groebner basis then \+ normalf(g, G, ord) is uniquely determined for all g in " }{TEXT 479 1 "Q" }{TEXT 480 24 "[x1,..,xn]. Furthermore:" }}{PARA 265 "" 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 15 "So whenever g1+" }{TEXT 528 1 "I" }{TEXT -1 6 " = g2+" }{TEXT 529 2 "I " }{TEXT -1 37 " (i.e. g1 is equivalent \+ to g2 modulo " }{TEXT 530 1 "I" }{TEXT -1 33 ", or in other words: g1- g2 is in " }{TEXT 531 1 "I" }{TEXT -1 7 "), then" }}{PARA 0 "" 0 "" {TEXT -1 92 "normalf(g1, G, ord)=normalf(g2, G, ord). If G is not a Gr oebner basis then this is not true." }}}}{SECT 0 {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 leading monomials (note: l f and lg depend on the ordering we have chosen)." }}{PARA 0 "" 0 "" {TEXT -1 5 "Write" }}{PARA 0 "" 0 "" {TEXT -1 83 " \"leading monom ial of f\" = \"leading coefficient of f\" * \"leading power product\" " }}{PARA 0 "" 0 "" {TEXT -1 25 " lf = lc(f)*lpp(f) " }}{PARA 0 "" 0 "" {TEXT -1 3 "and" }}{PARA 0 "" 0 "" {TEXT -1 24 " 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 341 20 "leading coefficients" }{TEXT -1 37 "), and lpp(f), lpp(g) in [X] are the " } {TEXT 342 23 "leading power products." }}{PARA 0 "" 0 "" {TEXT -1 333 "What would be the smallest power product t=x1^e1*...*xn^en in [X] tha t 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) d ivides 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 25 "t := lcm(lpp(f), lpp(g))." }}{PARA 0 "" 0 "" {TEXT -1 114 "If we reduce this t modulo the set \{f,g\}, and we do only 1 r eduction 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 215 "Both these outcomes are the same modulo (f,g), they are both equivale nt to t modulo (f,g). So the difference between the two is 0 modulo (f ,g), and so that must be an element of the ideal (f,g). This differenc e is: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 354 32 "Definition: The S-polynomial is:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 " spoly(f,g, ord) = lcm( lpp(f), l pp(g)) * (f/lf - g/lg)\n" }}{PARA 0 "" 0 "" {TEXT -1 59 "(note that th is depends on the ordering ord that we select)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "So what we did is: Take \+ f, and divide f by the leading monomial of f, and we get f/lf." }} {PARA 0 "" 0 "" {TEXT -1 74 "Then take g, and divide it by the leading monomial 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 polynomials:" }}{PARA 0 "" 0 "" {TEXT -1 20 " t := lcm(lf, lg) " }}{PARA 0 "" 0 "" {TEXT -1 3 " or:" }}{PARA 0 "" 0 "" {TEXT -1 78 " t := lcm( lpp(f), lpp(g) ) \+ (we may ignore the leading coefficients)." }}{PARA 0 "" 0 "" {TEXT -1 53 "So then t * f/lf = t/lf * f = (some polynomial) * f." }}{PARA 0 "" 0 "" {TEXT -1 43 "And t * g/lg = (some other polynomial) * g." }} {PARA 0 "" 0 "" {TEXT -1 75 "And spoly(f,g,ord) = the difference = t/l f * f - t/lg * g = t*(f/lf - g/lg)" }}{PARA 0 "" 0 "" {TEXT -1 108 "an d this equals: (some polynomial)*f - (some other polynomial)*g and he nce 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 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 basis, we see that if F is a Groebne r 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 whethe r we use f1 first, or f2, or f3 or such, it should always go to 0). No w 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 355 23 "Buchberger's cri terium." }}{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 42 " 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 356 4 "Note" }{TEXT -1 487 ": when we do not know if F i s a Groebner basis, then we also do not know if the output of reduce(s poly(f,g,ord), F, ord) is unique or not, it can depend on coincidence \+ (which element of F is used first in the reduce algorithm, which secon d, etc.). Depending on such coincidence, it may even sometimes reduce \+ to 0 and sometimes not. Buchberger's criterium holds no matter how the reduction is done, it is independent on the choices you can make duri ng the reduce algorithm, so as long as " }{TEXT 357 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, assuming Buchberger's criterium is tr ue, we see that all S-poly's reduce to 0 for any choices made during t he reductions if and only if all S-poly's reduce to 0 for just one par ticular choice made during the reduction. We will postpone the proof. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 127 "Now \+ we have an algorithmic criterium which lets us test if a set is a Groe bner basis or not. Let's check this with the example " }{TEXT 481 1 "I " }{TEXT -1 162 "=(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&%#x3GF&F&!\"\",&*(F%F&F'F&F(F&F&F&F),(*$)F%\"\"#F&F&*&F/F&)F'F/F &F&*&\"\"$F&)F(F/F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 96 "fo r i in F do for j in F minus \{i\} do\n S:=spoly(i,j, ord);\n prin t(reduce(S, F, ord));\nod od:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,**&) %#x2G\"\"#\"\"\"%#x3GF(F(*&F&F()F)F'F(F(*&F&F(F)F(!\"\"F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,.*&\"\"$\"\"\")%#x2G\"\"#F&!\"\"*(F)F&F(F&% #x3GF&F**&F)F&F(F&F&*&\"\"%F&)F,F)F&F**&F)F&F,F&F&F&F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,*\"\"\"!\"\"*&)%#x2G\"\"#F$%#x3GF$F%*&F(F$)F*F)F$ F%*&F(F$F*F$F$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,,*(\"\"#\"\"\")%#x2 G\"\"$F&%#x3GF&!\"\"*(F)F&)F*F)F&F(F&F+F(F&F*F&F&F+" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#,.*&\"\"$\"\"\")%#x2G\"\"#F&F&*(F)F&F(F&%#x3GF&F&*&F) F&F(F&!\"\"*&\"\"%F&)F+F)F&F&*&F)F&F+F&F-F&F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,,*(\"\"#\"\"\")%#x2G\"\"$F&%#x3GF&F&*(F)F&)F*F)F&F(F&F &F(!\"\"F*F-F&F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 108 "The set F is definitely not a Groebner basis (using reduce(S, F, ord) none of the \+ spoly's reduced to zero!)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "G;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<%,*%#x1G\"\"\"%#x2GF&%#x3GF& F&!\"\",.*&\"\"$F&)F'\"\"#F&F&*&F,F&)F(F.F&F&*&F%F&F(F&F)F%F&*&F'F&F(F &F&F'F),.F,F)*&F'F&F0F&F)F2F&*&\"\"%F&)F(F,F&F&*&F.F&F0F&F)F(F&" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 97 "for i in G do for j in G min us \{i\} do\n S:=spoly(i,j, ord);\n print(reduce(S, G, ord))\nod od:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0*&\"#?\"\"\")%#x3G\"\"%F&F&*&\"\"'F&)F(\"\"$F&!\"\"*& F-F&)F(\"\"#F&F&*&F-F&%#x2GF&F.*(F-F&F3F&F(F&F&*&\"#8F&F(F&F.F)F." }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0*&\"#?\"\"\")%#x3G\"\"%F&!\"\"*&\"\"'F&)F(\"\"$F&F&*&F.F&)F(\"\"# F&F**&F.F&%#x2GF&F&*(F.F&F3F&F(F&F**&\"#8F&F(F&F&F)F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0*&\"#?\"\"\")%#x3G\"\"%F&!\"\"*&\"\"'F&)F(\"\"$F &F&*&F.F&)F(\"\"#F&F**&F.F&%#x2GF&F&*(F.F&F3F&F(F&F**&\"#8F&F(F&F&F)F& " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0*&\"#?\"\"\")%#x3G\"\"%F&F&*&\" \"'F&)F(\"\"$F&!\"\"*&F-F&)F(\"\"#F&F&*&F-F&%#x2GF&F.*(F-F&F3F&F(F&F&* &\"#8F&F(F&F.F)F." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 136 "The set G i s a little better than F, some of the spoly's reduced to 0 with reduce (S, G, ord), but not all. So G is not a Groebner basis." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "GB;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7&,.\"\"*!\"\"*&\"#:\"\"\")%#x3G\"\"$F)F)*&\"#>F))F+\"\"#F)F&F+F&*& \"#?F))F+\"\"&F)F)*&\"\"'F))F+\"\"%F)F&,0*&F2F)F7F)F)*&F6F)F*F)F&*&F,F )F/F)F)*&F,F)%#x2GF)F&*(F,F)F>F)F+F)F)*&\"#8F)F+F)F&F8F&,*%#x1GF)F>F)F +F)F)F&,.*&F%F))F>F0F)F)*&\"#SF)F7F)F&*&\"#7F)F*F)F)*&F6F)F/F)F)*&F2F) F+F)F)\"#6F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 106 "for i in G B do for j in \{op(GB)\} minus \{i\} do\n S:=spoly(i,j, ord);\n \+ print(reduce(S, GB, ord))\nod od:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# \"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 65 "The set GB is a Groebner basis, all the S-poly's r educed to zero." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 27 "Computing a \+ Groebner basis." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 97 "Let F be a set of polynomials F=\{f1,f2,..,fm\}. We want \+ to compute a Groebner basis for the ideal " }{TEXT 482 1 "I" }{TEXT -1 101 "=(F). We can use Buchberger's algorithm to check if the set F \+ is already a Groebner basis as follows:" }}{PARA 0 "" 0 "" {TEXT -1 75 "Compute all the S-polynomials: spoly(f, g, ord) for all pairs \+ f,g in F." }}{PARA 0 "" 0 "" {TEXT -1 92 "Reduce each S-poly by F. Whe n they all reduce to 0, then we are done, F is a Groebner basis." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 55 "What if t hey 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 did n't reduce to zero\}. (**)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 115 "Note that since we only added elements of the ideal to the set F, the new F generates the same ideal as the old F. " }}{PARA 0 "" 0 "" {TEXT -1 30 "Is the new F a Groebner basis?" }} {PARA 0 "" 0 "" {TEXT -1 12 "We see that " }{TEXT 361 20 "all S-poly's of the " }{TEXT 362 5 "old F" }{TEXT 360 48 " can be reduced to zero \+ when we reduce with the " }{TEXT 363 5 "new F" }{TEXT -1 8 ". Note: " }{TEXT 358 21 "\"can be reduced to 0\"" }{TEXT -1 10 ", and not " } {TEXT 359 23 "\"will be reduced to 0\"," }{TEXT -1 117 " because the r esult of the reduction depends on coincidence. However, nothing guaran tees us that all S-poly's of the " }{TEXT 364 5 "new F" }{TEXT -1 38 " can also be reduced to zero with the " }{TEXT 365 7 "new F, " }{TEXT -1 16 "and indeed, the " }{TEXT 366 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 367 6 "new F " }{TEXT -1 305 "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. The new F is not a Groebner basis if and onl y if not all of these S-poly's reduce to zero. If they don't all reduc e to zero, then what do we do?" }}{PARA 0 "" 0 "" {TEXT -1 161 "Idea: \+ we won't let that bother us, we'll simply do step (**) again! (this ti me for the new F). In fact, we'll just keep on doing step (**) again a nd again until " }{TEXT 368 4 "all " }{TEXT -1 23 "S-poly's reduce to \+ zero" }{TEXT 369 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 m iracle is: Although it may take a long time, This process terminates! " }}}}{MARK "9 14 0" 95 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }