Solving Polynomial Equation Systems

Teo Mora0521811546, 9780521811545, 9780511064494, 9780521811569, 0521811562

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 :
Title……Page 5
Half-title……Page 3
Series-title……Page 4
Copyright……Page 6
Contents……Page 9
Preface……Page 13
Part one The Kronecker – Duval Philosophy……Page 17
1 Euclid……Page 19
1.1 The Division Algorithm……Page 20
1.2 Euclidean Algorithm……Page 22
1.3 Bezout’s Identity and Extended Euclidean Algorithm……Page 24
1.4 Roots of Polynomials……Page 25
1.5 Factorization of Polynomials……Page 26
1.6.1 Coefficient explosion……Page 28
1.6.3 Hensel Lifting Algorithm……Page 32
1.6.4 Heuristic gcd……Page 34
2 Intermezzo: Chinese Remainder Theorems……Page 39
2.1 Chinese Remainder Theorems……Page 40
2.2 Chinese Remainder Theorem for a Principal Ideal Domain……Page 42
2.3 A Structure Theorem (1)……Page 45
2.4 Nilpotents……Page 48
2.5 Idempotents……Page 51
2.6 A Structure Theorem (2)……Page 55
2.7 Lagrange Formula……Page 57
3.1 A Tautology?……Page 63
3.2 The Imaginary Number……Page 64
3.3 An Impasse……Page 67
3.4 A Tautology!……Page 68
4 Intermezzo: Multiplicity of Roots……Page 69
4.1 Characteristic of a Field……Page 70
4.2 Finite Fields……Page 71
4.3 Derivatives……Page 73
4.4 Multiplicity……Page 74
4.5 Separability……Page 78
4.6 Perfect Fields……Page 80
4.7 Squarefree Decomposition……Page 84
5 Kronecker I: Kronecker’s Philosophy……Page 90
5.1 Quotients of Polynomial Rings……Page 91
5.2 The Invention of the Roots……Page 92
5.3 Transcendental and Algebraic Field Extensions……Page 97
5.4 Finite Algebraic Extensions……Page 100
5.5 Splitting Fields……Page 102
6 Intermezzo: Sylvester……Page 107
6.1 Gauss Lemma……Page 108
6.2 Symmetric Functions……Page 112
6.3 Newton’s Theorem……Page 116
6.4 The Method of Indeterminate Coefficients……Page 122
6.5 Discriminant……Page 124
6.6 Resultants……Page 128
6.7 Resultants and Roots……Page 131
7 Galois I: Finite Fields……Page 135
7.1 Galois Fields……Page 136
7.2 Roots of Polynomials over Finite Fields……Page 139
7.3 Distinct Degree Factorization……Page 141
7.4 Roots of Unity and Primitive Roots……Page 143
7.5 Representation and Arithmetics of Finite Fields……Page 149
7.6 Cyclotomic Polynomials……Page 151
7.7 Cycles, Roots and Idempotents……Page 157
7.8 Deterministic Polynomial-time Primality Test……Page 164
8.1 Kronecker’s Philosophy……Page 172
8.2 Explicitly Given Fields……Page 175
8.3.1 Representation……Page 180
8.3.3 Canonical representation……Page 181
8.3.5 Inverse and division……Page 183
8.3.6 Polynomial factorization……Page 184
8.3.8 Monic polynomials……Page 185
8.4 Primitive Element Theorems……Page 186
9 Steinitz……Page 191
9.1 Algebraic Closure……Page 192
9.2 Algebraic Dependence and Transcendency Degree……Page 196
9.3 The Structure of Field Extensions……Page 200
9.4 Universal Field……Page 202
9.5 Lüroth’s Theorem……Page 203
10 Lagrange……Page 207
10.1 Conjugates……Page 208
10.2 Normal Extension Fields……Page 209
10.3 Isomorphisms……Page 212
10.4 Splitting Fields……Page 219
10.5 Trace and Norm……Page 222
10.6 Discriminant……Page 228
10.7 Normal Bases……Page 232
11.1 Explicit Representation of Rings……Page 237
11.2 Ring Operations in a Non-unique Representation……Page 239
11.3 Duval Representation……Page 240
11.4 Duval’s Model……Page 244
12.1 The Fundamental Theorem of Algebra……Page 248
12.2 Cyclotomic Equations……Page 253
13 Sturm……Page 279
13.1 Real Closed Fields……Page 280
13.2 Definitions……Page 288
13.3 Sturm……Page 291
13.4 Sturm Representation of Algebraic Reals……Page 296
13.5 Hermite’s Method……Page 300
13.6 Thom Codification of Algebraic Reals (1)……Page 304
13.7 Ben-Or, Kozen and Reif Algorithm……Page 306
13.8 Thom Codification of Algebraic Reals (2)……Page 310
14 Galois II……Page 313
14.1 Galois Extension……Page 314
14.2 Galois Correspondence……Page 316
14.3 Solvability by Radicals……Page 321
14.4 Abel–Ruffini Theorem……Page 330
14.5 Constructions with Ruler and Compass……Page 334
Part two Factorization……Page 343
15.1 A Computation……Page 345
15.2 An Exercise……Page 354
16 Kronecker III: factorization……Page 362
16.1 Von Schubert Factorization Algorithm over the Integers……Page 363
16.2 Factorization of Multivariate Polynomials……Page 366
16.3 Factorization over a Simple Algebraic Extension……Page 368
17.1 Berlekamp’s Algorithm……Page 377
17.2 The Cantor–Zassenhaus Algorithm……Page 385
18 Zassenhaus……Page 396
18.1 Hensel’s Lemma……Page 397
18.2 The Zassenhaus Algorithm……Page 405
18.3 Factorization Over a Simple Transcendental Extension……Page 407
18.4 Cauchy Bounds……Page 411
18.5 Factorization over the Rationals……Page 414
18.6 Swinnerton-Dyer Polynomials……Page 418
18.7 L Algorithm……Page 421
19.2 Van der Waerden’s Example……Page 431
Bibliography……Page 436
Index……Page 438