Solving Polynomial Equation Systems I

✍ Scribed by Teo Mora

• Publisher: Cambridge University Press
• Year: 2003
• Tongue: English
• Leaves: 438
• Series: Encyclopedia of Mathematics and its Applications
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

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