Solving Polynomial Equation Systems I: The Kronecker-Duval Philosophy (Encyclopedia of Mathematics and its Applications, Series Number 88)

With the advent of computers, theoretical studies and solution methods for polynomial equations have changed dramatically. Many classical results can be more usefully recast within a different framework which in turn lends itself to further theoretical development tuned to computation. This first book in a trilogy is devoted to the new approach. It is a handbook covering the classical theory of finding roots of a univariate polynomial, emphasizing computational aspects, especially the representation and manipulation of algebraic numbers, enlarged by more recent representations like the Duval Model and the Thom Codification. Mora aims to show that solving a polynomial equation really means finding algorithms that help one manipulate roots rather than simply computing them; to that end he also surveys algorithms for factorizing univariate polynomials. Cover......Page 1 ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS 88......Page 2 Solving Polynomial Equation Systems I: The Kronecker–Duval Philosophy......Page 4 Copyright - ISBN: 0521811546......Page 5 Contents......Page 8 Preface......Page 12 Part one: The Kronecker – Duval Philosophy......Page 16 1 Euclid......Page 18 1.1 The Division Algorithm......Page 19 1.2 Euclidean Algorithm......Page 21 1.3 Bezout’s Identity and Extended Euclidean Algorithm......Page 23 1.4 Roots of Polynomials......Page 24 1.5 Factorization of Polynomials......Page 25 1.6.1* Coefficient explosion......Page 27 1.6.3* Hensel Lifting Algorithm......Page 31 1.6.4* Heuristic gcd......Page 33 2 Intermezzo: Chinese Remainder Theorems......Page 38 2.1 Chinese Remainder Theorems......Page 39 2.2 Chinese Remainder Theoremfor a Principal Ideal Domain......Page 41 2.3 A Structure Theorem(1)......Page 44 2.4 Nilpotents......Page 47 2.5 Idempotents......Page 50 2.6 A Structure Theorem(2)......Page 54 2.7 Lagrange Formula......Page 56 3.1 A Tautology?......Page 62 3.2 The Imaginary Number......Page 63 3.3 An Impasse......Page 66 3.4 A Tautology!......Page 67 4 Intermezzo: Multiplicity of Roots......Page 68 4.1 Characteristic of a Field......Page 69 4.2 Finite Fields......Page 70 4.3 Derivatives......Page 72 4.4 Multiplicity......Page 73 4.5 Separability......Page 77 4.6 Perfect Fields......Page 79 4.7 Squarefree Decomposition......Page 83 5 Kronecker I: Kronecker’s Philosophy......Page 89 5.1 Quotients of Polynomial Rings......Page 90 5.2 The Invention of the Roots......Page 91 5.3 Transcendental and Algebraic Field Extensions......Page 96 5.4 Finite Algebraic Extensions......Page 99 5.5 Splitting Fields......Page 101 6 Intermezzo: Sylvester......Page 106 6.1 Gauss Lemma......Page 107 6.2 Symmetric Functions......Page 111 6.3* Newton’s Theorem......Page 115 6.4 The Method of Indeterminate Coefficients......Page 121 6.5 Discriminant......Page 123 6.6 Resultants......Page 127 6.7 Resultants and Roots......Page 130 7 Galois I: Finite Fields......Page 134 7.1 Galois Fields......Page 135 7.2 Roots of Polynomials over Finite Fields......Page 138 7.3 Distinct Degree Factorization......Page 140 7.4 Roots of Unity and Primitive Roots......Page 142 7.5 Representation and Arithmetics of Finite Fields......Page 148 7.6* Cyclotomic Polynomials......Page 150 7.7* Cycles, Roots and Idempotents......Page 156 7.8 Deterministic Polynomial-time Primality Test......Page 163 8.1 Kronecker’s Philosophy......Page 171 8.2 Explicitly Given Fields......Page 174 8.3.1 Representation......Page 179 8.3.3 Canonical representation......Page 180 8.3.5 Inverse and division......Page 182 8.3.6 Polynomial factorization......Page 183 8.3.8 Monic polynomials......Page 184 8.4 Primitive Element Theorems......Page 185 9 Steinitz......Page 190 9.1 Algebraic Closure......Page 191 9.2 Algebraic Dependence and Transcendency Degree......Page 195 9.3 The Structure of Field Extensions......Page 199 9.4 Universal Field......Page 201 9.5* Lüroth’s Theorem......Page 202 10 Lagrange......Page 206 10.1 Conjugates......Page 207 10.2 Normal Extension Fields......Page 208 10.3 Isomorphisms......Page 211 10.4 Splitting Fields......Page 218 10.5 Trace and Norm......Page 221 10.6 Discriminant......Page 227 10.7* Normal Bases......Page 231 11.1 Explicit Representation of Rings......Page 236 11.2 Ring Operations in a Non-unique Representation......Page 238 11.3 Duval Representation......Page 239 11.4 Duval’s Model......Page 243 12.1 The Fundamental Theoremof Algebra......Page 247 12.2 Cyclotomic Equations......Page 252 13 Sturm......Page 278 13.1* Real Closed Fields......Page 279 13.2 Definitions......Page 287 13.3 Sturm......Page 290 13.4 SturmRepresentation of Algebraic Reals......Page 295 13.5 Hermite’s Method......Page 299 13.6 ThomCodification of Algebraic Reals (1)......Page 303 13.7 Ben-Or, Kozen and Reif Algorithm......Page 305 13.8 ThomCodification of Algebraic Reals (2)......Page 309 14 Galois II......Page 312 14.1 Galois Extension......Page 313 14.2 Galois Correspondence......Page 315 14.3 Solvability by Radicals......Page 320 14.4 Abel–Ruffini Theorem......Page 329 14.5* Constructions with Ruler and Compass......Page 333 Part two: Factorization......Page 342 15.1 A Computation......Page 344 15.2 An Exercise......Page 353 16 Kronecker III: factorization......Page 361 16.1 Von Schubert Factorization Algorithmover the Integers......Page 362 16.2 Factorization of Multivariate Polynomials......Page 365 16.3 Factorization over a Simple Algebraic Extension......Page 367 17.1 Berlekamp’s Algorithm......Page 376 17.2 The Cantor–Zassenhaus Algorithm......Page 384 18 Zassenhaus......Page 395 18.1 Hensel’s Lemma......Page 396 18.2 The Zassenhaus Algorithm......Page 404 18.3 Factorization Over a Simple Transcendental Extension......Page 406 18.4 Cauchy Bounds......Page 410 18.5 Factorization over the Rationals......Page 413 18.6 Swinnerton-Dyer Polynomials......Page 417 18.7 L^3 Algorithm......Page 420 19.2 Van der Waerden’s Example......Page 430 Bibliography......Page 435 Index......Page 437 Cover 1 ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS 88 2 Solving Polynomial Equation Systems I: The Kronecker–Duval Philosophy 4 Copyright - ISBN: 0521811546 5 Contents 8 Preface 12 Part one: The Kronecker – Duval Philosophy 16 1 Euclid 18 1.1 The Division Algorithm 19 1.2 Euclidean Algorithm 21 1.3 Bezout’s Identity and Extended Euclidean Algorithm 23 1.4 Roots of Polynomials 24 1.5 Factorization of Polynomials 25 1.6* Computing a gcd 27 1.6.1* Coefficient explosion 27 1.6.2* Modular Algorithm 31 1.6.3* Hensel Lifting Algorithm 31 1.6.4* Heuristic gcd 33 2 Intermezzo: Chinese Remainder Theorems 38 2.1 Chinese Remainder Theorems 39 2.2 Chinese Remainder Theoremfor a Principal Ideal Domain 41 2.3 A Structure Theorem(1) 44 2.4 Nilpotents 47 2.5 Idempotents 50 2.6 A Structure Theorem(2) 54 2.7 Lagrange Formula 56 3 Cardano 62 3.1 A Tautology? 62 3.2 The Imaginary Number 63 3.3 An Impasse 66 3.4 A Tautology! 67 4 Intermezzo: Multiplicity of Roots 68 4.1 Characteristic of a Field 69 4.2 Finite Fields 70 4.3 Derivatives 72 4.4 Multiplicity 73 4.5 Separability 77 4.6 Perfect Fields 79 4.7 Squarefree Decomposition 83 5 Kronecker I: Kronecker’s Philosophy 89 5.1 Quotients of Polynomial Rings 90 5.2 The Invention of the Roots 91 5.3 Transcendental and Algebraic Field Extensions 96 5.4 Finite Algebraic Extensions 99 5.5 Splitting Fields 101 6 Intermezzo: Sylvester 106 6.1 Gauss Lemma 107 6.2 Symmetric Functions 111 6.3* Newton’s Theorem 115 6.4 The Method of Indeterminate Coefficients 121 6.5 Discriminant 123 6.6 Resultants 127 6.7 Resultants and Roots 130 7 Galois I: Finite Fields 134 7.1 Galois Fields 135 7.2 Roots of Polynomials over Finite Fields 138 7.3 Distinct Degree Factorization 140 7.4 Roots of Unity and Primitive Roots 142 7.5 Representation and Arithmetics of Finite Fields 148 7.6* Cyclotomic Polynomials 150 7.7* Cycles, Roots and Idempotents 156 7.8 Deterministic Polynomial-time Primality Test 163 8 Kronecker II: Kronecker’s Model 171 8.1 Kronecker’s Philosophy 171 8.2 Explicitly Given Fields 174 8.3 Representation and Arithmetics 179 8.3.1 Representation 179 8.3.2 Vector space arithmetics 180 8.3.3 Canonical representation 180 8.3.4 Multiplication 182 8.3.5 Inverse and division 182 8.3.6 Polynomial factorization 183 8.3.7 Solving polynomial equations 184 8.3.8 Monic polynomials 184 8.4 Primitive Element Theorems 185 9 Steinitz 190 9.1 Algebraic Closure 191 9.2 Algebraic Dependence and Transcendency Degree 195 9.3 The Structure of Field Extensions 199 9.4 Universal Field 201 9.5* Lüroth’s Theorem 202 10 Lagrange 206 10.1 Conjugates 207 10.2 Normal Extension Fields 208 10.3 Isomorphisms 211 10.4 Splitting Fields 218 10.5 Trace and Norm 221 10.6 Discriminant 227 10.7* Normal Bases 231 11 Duval 236 11.1 Explicit Representation of Rings 236 11.2 Ring Operations in a Non-unique Representation 238 11.3 Duval Representation 239 11.4 Duval’s Model 243 12 Gauss 247 12.1 The Fundamental Theoremof Algebra 247 12.2 Cyclotomic Equations 252 13 Sturm 278 13.1* Real Closed Fields 279 13.2 Definitions 287 13.3 Sturm 290 13.4 SturmRepresentation of Algebraic Reals 295 13.5 Hermite’s Method 299 13.6 ThomCodification of Algebraic Reals (1) 303 13.7 Ben-Or, Kozen and Reif Algorithm 305 13.8 ThomCodification of Algebraic Reals (2) 309 14 Galois II 312 14.1 Galois Extension 313 14.2 Galois Correspondence 315 14.3 Solvability by Radicals 320 14.4 Abel–Ruffini Theorem 329 14.5* Constructions with Ruler and Compass 333 Part two: Factorization 342 15 Prelude 344 15.1 A Computation 344 15.2 An Exercise 353 16 Kronecker III: factorization 361 16.1 Von Schubert Factorization Algorithmover the Integers 362 16.2 Factorization of Multivariate Polynomials 365 16.3 Factorization over a Simple Algebraic Extension 367 17 Berlekamp 376 17.1 Berlekamp’s Algorithm 376 17.2 The Cantor–Zassenhaus Algorithm 384 18 Zassenhaus 395 18.1 Hensel’s Lemma 396 18.2 The Zassenhaus Algorithm 404 18.3 Factorization Over a Simple Transcendental Extension 406 18.4 Cauchy Bounds 410 18.5 Factorization over the Rationals 413 18.6 Swinnerton-Dyer Polynomials 417 18.7 L^3 Algorithm 420 19 Finale 430 19.1 Kronecker’s Dream 430 19.2 Van der Waerden’s Example 430 Bibliography 435 Index 437 0521811546 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. Polynomial equations have been long studied, both theoretically and with a view to solving them. Until recently, manual computation was the only solution method and the theory was developed to accommodate it. With the advent of computers, the situation changed dramatically. Many classical results can be more usefully recast within a different framework which in turn lends itself to further theoretical development tuned to computation. This first book in a trilogy is devoted to the new approach. It is a handbook covering the classical theory of finding roots of a univariate polynomial, emphasising computational aspects, especially the representation and manipulation of algebraic numbers, enlarged by more recent representations like the Duval Model and the Thom Codification. Mora aims to show that solving a polynomial equation really means finding algorithms that help one manipulate roots rather than simply computing them; to that end he also surveys algorithms for factorizing univariate polynomials. Mora covers the classical theory of finding roots of a univariate polynomial, emphasising computational aspects. He shows that solving a polynomial equation really means finding algorithms that help one manipulate roots rather than simply computing them; to that end he also surveys algorithms for factorizing univariate polynomials This preliminary chapter is just devoted to recalling the Euclidean Algorithms over a univariate polynomial ring and its elementary applications: roughly speaking they are essentially the obvious generalization of those over integers. 1. The Kronecker-Duval philosophy -- -- 2. Macaulay's paradigm and Gröbner technology.