Solving Polynomial Equation Systems II: Macaulay's Paradigm and Gröbner Technology (Encyclopedia of Mathematics and its Applications, Series Number 99)

The second volume of this comprehensive treatise focusses on Buchberger theory and its application to the algorithmic view of commutative algebra. In distinction to other works, the presentation here is based on the intrinsic linear algebra structure of Groebner bases, and thus elementary considerations lead easily to the state-of-the-art in issues of implementation. The same language describes the applications of Groebner technology to the central problems of commutative algebra. The book can be also used as a reference on elementary ideal theory and a source for the state-of-the-art in its algorithmization. Aiming to provide a complete survey on Groebner bases and their applications, the author also includes advanced aspects of Buchberger theory, such as the complexity of the algorithm, Galligo's theorem, the optimality of degrevlex, the Gianni-Kalkbrener theorem, the FGLM algorithm, and so on. Thus it will be essential for all workers in commutative algebra, computational algebra and algebraic geometry. Cover 1 Half Title 3 Series Page 4 Title 5 Copyright 6 Contents 8 Preface 13 Setting 16 Part three Gauss, Euclid, Buchberger: Elementary Gröbner Bases 25 20 Hilbert 27 20.1 Affine Algebraic Varieties and Ideals 27 20.2 Linear Change of Coordinates 32 20.3 Hilbert’s Nullstellensatz 34 20.4 *Kronecker Solver 39 20.5 Projective Varieties and Homogeneous Ideals 46 20.6 *Syzygies and Hilbert Function 52 20.7 *More on the Hilbert Function 58 20.8 Hilbert’s and Gordan’s Basissätze 60 21 Gauss II 70 21.1 Some Heretical Notation 71 21.2 Gaussian Reduction 75 21.3 Gaussian Reduction and Euclidean Algorithm Revisited 87 22 Buchberger 96 22.1 From Gauss to Gröbner 99 22.2 Gröbner Basis 102 22.3 Toward Buchberger’s Algorithm 107 22.4 Buchberger’s Algorithm (1) 120 22.5 Buchberger’s Criteria 122 22.6 Buchberger’s Algorithm (2) 128 23 Macaulay I 133 23.1 Homogenization and Affinization 134 23.2 H-bases 138 23.3 Macaulay’s Lemma 143 23.4 Resolution and Hilbert Function for Monomial Ideals 146 23.5 Hilbert Function Computation: the ‘Divide-and-Conquer’ Algorithms 160 23.6 H-bases and Gröbner Bases for Modules 162 23.7 Lifting Theorem 166 23.8 Computing Resolutions 170 23.9 Macaulay’s Nullstellensatz Bound 176 23.10 *Bounds for the Degree in the Nullstellensatz 180 24 Gröbner I 194 24.1 Rewriting Rules 197 24.2 Gröbner Bases and Rewriting Rules 207 24.3 Gröbner Bases for Modules 212 24.4 Gröobner Bases in Graded Rings 219 24.5 Standard Bases and the Lifting Theorem 222 24.6 Hironaka’s Standard Bases and Valuations 227 24.7 *Standard Bases and Quotient Rings 242 24.8 *Characterization of Standard Bases in Valuation Rings 247 24.9 Term Ordering: Classification and Representation 258 24.10 *Gröbner Bases and the State Polytope 271 25 Gebauer and Traverso 279 25.1 Gebauer–Möller and Useless Pairs 279 25.2 Buchberger’s Algorithm (3) 288 25.3 Traverso’s Choice 295 25.4 Gebauer–Möller’s Staggered Linear Bases and Faugère’s F5 298 26 Spear 313 26.1 Zacharias Rings 315 26.2 Lexicographical Term Ordering and Elimination Ideals 324 26.3 Ideal Theoretical Operation 328 26.4 *Multivariate Chinese Remainder Algorithm 337 26.5 Tag-Variable Technique and Its Application to Subalgebras 340 26.6 Caboara–Traverso Module Representation 345 26.7 *Caboara Algorithm for Homogeneous Minimal Resolutions 353 Part four Duality 357 27 Noether 359 27.1 Noetherian Rings 361 27.2 Prime, Primary, Radical, Maximal Ideals 364 27.3 Lasker–Noether Decomposition: Existence 369 27.4 Lasker–Noether Decomposition: Uniqueness 374 27.6 Decomposition of Homogeneous Ideals 388 27.7 *The Closure of an Ideal at the Origin 392 27.8 Generic System of Coordinates 395 27.9 Ideals in Noether Position 398 27.10 *Chains of Prime Ideals 402 27.11 Dimension 404 27.12 Zero-dimensional Ideals and Multiplicity 408 27.13 Unmixed Ideals 414 28 Möller I 417 28.1 Duality 417 28.2 Möller Algorithm 425 29 Lazard 438 29.1 The FGLM Problem 439 29.2 The FGLM Algorithm 442 29.3 Border Bases and Gröbner Representation 450 29.4 Improving Möller’s Algorithm 456 29.5 Hilbert Driven and Gröbner Walk 464 29.6 *The Structure of the Canonical Module 469 30 Macaulay II 475 30.1 The Linear Structure of an Ideal 476 30.2 Inverse System 480 30.3 Representing and Computing the Linear Structure of an Ideal 485 30.4 Noetherian Equations 490 30.5 Dialytic Arrays of M(r) and Perfect Ideals 502 30.6 Multiplicity of Primary Ideals 516 30.7 The Structure of Primary Ideals at the Origin 518 31 Gröbner II 524 31.1 Noetherian Equations 525 31.2 Stability 526 31.3 Gröbner Duality 528 31.4 Leibniz Formula 532 31.5 Differential Inverse Functions at the Origin 533 31.6 Taylor Formula and Gröbner Duality 536 32 Gröbner III 541 32.1 Macaulay Bases 542 32.2 Macaulay Basis and Gröbner Representation 545 32.3 Macaulay Basis and Decomposition of Primary Ideals 546 32.4 Horner Representation of Macaulay Bases 551 32.5 Polynomial Evaluation at Macaulay Bases 555 32.6 Continuations 557 32.7 Computing a Macaulay Basis 566 33 Möller II 573 33.1 Macaulay’s Trick 574 33.2 The Cerlienco–Mureddu Correspondence 578 33.3 Lazard Structural Theorem 584 33.4 Some Factorization Results 586 33.5 Some Examples 593 33.6 An Algorithmic Proof 598 Part five Beyond Dimension Zero 607 34 Gröbner IV 609 34.1 Nulldimensionale Basissätze 610 34.2 Primitive Elements and Allgemeine Basissatz 617 34.3 Higher-Dimension Primbasissatz 622 34.4 Ideals in Allgemeine Positions 625 34.5 Solving 629 34.6 Gianni–Kalkbrener Theorem 632 35 Gianni–Trager–Zacharias 638 35.1 Decomposition Algorithms 639 35.2 Zero-dimensional Decomposition Algorithms 640 35.3 The GTZ Scheme 646 35.4 Higher-dimensional Decomposition Algorithms 655 35.5 Decomposition Algorithms for Allgemeine Ideals 658 35.5.1 Zero-dimensional Allgemeine Ideals 658 35.5.2 Higher-dimensional Allgemeine Ideals 661 35.6 Sparse Change of Coordinates 664 35.6.1 Gianni’s Local Change of Coordinates 665 35.6.2 Giusti–Heintz Coordinates 669 35.7 Linear Algebra and Change of Coordinates 674 35.8 Direct Methods for Radical Computation 678 35.9 Caboara–Conti–Traverso Decomposition Algorithm 682 35.10 Squarefree Decomposition of a Zero-dimensional Ideal 684 36 Macaulay III 689 36.1 Hilbert Function and Complete Intersections 690 36.2 The Coefficients of the Hilbert Function 694 36.3 Perfectness 702 37 Galligo 710 37.1 Galligo Theorem (1): Existence of Generic Escalier 710 37.2 Borel Relation 721 37.3 *Galligo Theorem (2): The Generic Initial Ideal is Borel Invariant 730 37.4 *Galligo Theorem (3): The Structure of the Generic Escalier 734 37.5 Eliahou–Kervaire Resolution 738 38 Giusti 749 38.1 The Complexity of an Ideal 750 38.2 Toward Giusti’s Bound 752 38.3 Giusti’s Bound 757 38.4 Mayr and Meyer’s Example 759 38.5 Optimality of Revlex 765 Bibliography 773 Index 782 "The second volume of this comprehensive treatise focusses on Buchberger theory and its application to the algorithmic view of commutative algebra. In distinction from other works, the presentation here is based on the intrinsic linear algebra structure of Grobner bases, and thus elementary considerations lead to an easy introduction to the state of the art in issues of implementation. The same language describes the applications of Grobner technology to the central problems of commutative alegbra (from Hilbert function and resolution computation, up to the Lasker-Noether decomposition). At the same time, the book can be used as a reference on elementary ideal theory and a source for the state of the art in its algorithmization. The efficiency of this algorithmization is shown by its ability to link the new Grobner technology with the old combinatorial and linear algebra approach performed and advocated by Macaulay; such a paradigm is discussed and illustrated in this book, which also gives a careful commentary of Macaulay's notion of inverse systems and algorithms for computing them. Aiming to be a complete survey on Grobner bases and their applications, the book also includes the advanced aspects of Buchberger theory, such as the complexity of the algorithm, Galligo's theorem, the optimality of degrevlex, the Gianni-Kalkbrener theorem, the FGLM algorithm, and so on. Thus it will be essential for all workers in commutative algebra, computational algebra and algebraic geometry. Book jacket."--BOOK JACKET A complete survey of Gröbner bases and their applications, this book will be essential for all workers in commutative algebra, computational algebra and algebraic geometry. The second volume of the treatise focuses on Buchberger theory and its application to the algorithmic view of commutative algebra. In distinction to other works, the presentation is based on the intrinsic linear algebra structure of Gröbner bases, making this a state-of-the-art reference on issues of implementation. A complete survey of Grobner bases and their applications, this book will be essential for all workers in commutative algebra, computational algebra and algebraic geometry. The second volume of the treatise focuses on Buchberger theory and its application to the algorithmic view of commutative algebra. In distinction to other works, the presentation is based on the intrinsic linear algebra structure of Grobner bases, making this a state-of-the-art reference on issues of implementation. Preface Part III. Gauss, Euclid, Buchberger - Elementary Groebner Bases: 20. Hilbert 21. Gauss 22. Buchberger 23. Macaulay I 24. Groebner I 25. Gebauer and Traverso 26. Spear Part IV. Duality: 27. Noether 28. Moeller I 29. Lazard 30. Macaulay II 31. Groebner II 32. Groebner III 33. Moeller II Part IV. Beyond Dimension Zero: 34. Groebner IV 35. Gianni Trager Zacharias 36. Macaulay III 37. Galligo 38. Giusti Bibliography Index. Let k be an infinite, perfect field, where, if p := char(k) 0, it is possible to extract pth roots, and let k be an algebraically closed extension of k. The second volume of a comprehensive treatise. This part focuses on Buchberger theory and its application to the algorithmic view of commutative algebra