You are here

Solving Polynomial Equation Systems I: The Kronecker-Duval Philosophy

Teo Mora
Cambridge University Press
Publication Date: 
Number of Pages: 
Encyclopedia of Mathematics and Its Applications 88
[Reviewed by
David P. Roberts
, on

The two books under review, Solving Polynomial Equation Systems I: The Kronecker-Duval Philosophy and Solving Polynomial Equation Systems II: Macaulay's Paradigm and Gröbner Technology, both by Teo Mora, are the first two volumes of a planned trilogy. Each book received an emphatically positive MathSciNet review from an expert in computer algebra. I approached the books as someone who uses computer algebra daily in research, eager to know more about the internal workings of some of the programs that I'm so happy to use. Alas, I found the two books disappointing. To help you gauge how useful these books would be to you, I'll describe my experience with them in more detail. Following the author, I'll abbreviate the two titles by SPES I and SPES II.

Interesting subject matter. A quick perusal of the books showed me I was very interested in the general subject matter. SPES I is about solving a single polynomial equation in one variable while SPES II is about solving systems of polynomial equations in several variables. Both books take a highly algorithmic point of view, but do not use any specific computer algebra system.

The most classical context for solving polynomial equation systems is to take coefficients from the field of rational numbers and look for solutions with coordinates in the field of complex numbers. In this context, not only algebra but also analysis and topology play an important role. In the one-variable setting, solving f(x) = 0 means finding good numerical approximations for all its roots. For a system such as f(x,y) = 0, g(x,y) = 0 with finitely many roots, again one wants to find good numerical approximations to these roots. For a system such as f(x,y) = 0 with infinitely many solutions, one wants, as a start, to find the irreducible components of the solution curve and the genus of each of the components.

A more algebraic context for solving polynomial equation systems is to take coefficients from a general ground field k. Again one seeks information about solutions with coordinates in some fixed algebraically closed field containing k. Much information can be obtained purely algebraically without ever leaving k. For example, whether or not the system f(x) = 0 has multiple roots can be detected by discriminants. Similarly, the number of solutions to f(x,y) = 0, g(x,y) = 0 and their multiplicities can be detected by resultants. Even the genera of components of the solution curve of f(x,y) = 0 can be defined and computed algebraically.

The SPES books are decidedly in the algebraic context. The subtitles reflect major contributors. Kronecker reinterpreted solving in the one-variable context purely algebraically; in the new interpretation, one solves f(x) = 0 by iteratively adjoining formal roots to the ground field k until finally f(x) splits into linear factors. Duval's recent contribution circumvents some computational difficulties in this construction process. Macaulay's paradigm is to reduce questions about ideals in k[x1,...,xn] to questions about monomials. Gröbner technology is a collection of techniques for working within this paradigm.

Of course, the general subjects treated are both quite broad. SPES I is more than 400 pages and is divided into parts one and two. SPES II runs more than 700 pages and is divided into parts three, four, and five. Parts three and four focus on systems with zero-dimensional solution sets, like f(x,y) = 0, g(x,y) = 0 above. Part five moves up to systems with positive dimensional solutions sets, like f(x,y) = 0 above.

Three unusual features. From my first quick pass at the books, I immediately noticed three unusual superficial features. Since they are related to my later substantive concerns, I'll describe them here.

First, chapter titles are usually a bare name, or a name with a number. For example, the chapter titles of SPES II part four are Noether, Möller I, Lazard, Macaulay II, Gröbner II, Gröbner III, Möller II, and Gröbner IV.

Second, proofs do not end with a QED or a box. They end instead with a somewhat strange sign, which changes with the part.

Third, there are epigraphs from literature quite far removed from mathematics. Most noticeably, each part opens with three quotes, one from Revelation, one from Agrippa's sixteenth-century De occulta phylosophia, and one from assorted revolutionary writings. For example, part one opens with

And I saw when the Lamb opened one of the seals, and I heard, as it were the noise of thunder, one of the four beasts saying, Come and see. And I saw, and behold a white horse: and he that sat on him had a bow; and a crown was given unto him: and he went forth conquering, and to conquer.

The things depending from Saturn: bile, lead, onyx, asphodel, mole, hoopoe, eel.

Soon we will drink blood for wine.

Unusual features two and three became less strange to me when I finally caught on that the end-of-proof signs correspond to the Agrippa quotes, and respectively represent Saturn, Jupiter, Mars, Venus and Mercury. In fact, in a footnote in the preface to SPES I, Mora invites us to guess the structure of his sequels from these quotations. Since Revelation has seven seals, and De occulta phylosophia deals with the seven celestial wanderers, we can expect that SPES III will consist of a part six and a part seven, with end-of-proof signs corresponding to the moon and sun.

Disconcerting prefaces. Naturally, I then checked out the prefaces, as prefaces are often useful for quickly revealing an author's style. The first paragraph of the preface of SPES I goes as follows.

If you HOPE too much from this SPES book, you will probably be disappointed: in fact not only is it nothing more than an extension of some notes of my undergraduate course, but also my horror vacui compelled me to fill it with irrelevant information.
Similarly, the first paragraph of the preface of SPES II ends with horror vacui compelled me to report nearly all the relevant results in computational algebraic geometry that I know about.

I found Mora's peculiar vacuphobia a bad omen. More generally, the prefaces left me with the impression that Mora did not invest much time in trying to make the learning experience of the readers efficient.

A lack of overview. I then took a slower pass at the entire books. With so many pages, I was originally hoping for a comprehensive and balanced overview of the theory. Some topics would be just mentioned, some would be sketched, and some would be pursued in detail.

My original hopes were indeed too much. I found no overview, just many topics pursued in detail. For example, in the setting of f(x,y) = 0 above, components of genus zero are parametrizable via rational functions x = g(t), y = h(t), perhaps after a quadratic extension of the ground field k . Surely, I thought, this most classical instance of algebraically solving polynomial equations should have some place in SPES II. But since this topic is not pursued in detail, it is not even mentioned.

Given the chapter titles, I expected at least that the text would communicate a historical overview of the subject. But one gets only occasional fragments of historical information. Consider, for example, the chapters Möller I and Möller II mentioned above. From these chapters, we learn absolutely nothing about Möller the person and absolutely nothing about the historical context of the work. There are four Möller papers in the bibliography of SPES II. The chapters Möller I and Möller II refer explicitly to none of them, so even finding which chapters correspond to which papers is left to the detective work of the reader.

SPES I. Next, I took a close look at SPES I. Typically, I was able to understand a section only because of my substantial previous familiarity with the material. For example, Section 14.5, "Constructions with Ruler and Compass," has no diagrams or historical discussion. Points, lines, circles, and angles are denoted by symbols O1, O2, O3, and so on, according to their order of introduction in a given discussion. Similarly, Section 15.1, titled simply "A computation," is about how x24–1 factors over an arbitrary field of characteristic zero. The simple Galois-theoretic description of this situation is completely obscured by ten pages of computations. Going through section after section, I found myself pitying less prepared readers.

Occasionally, going through a section truly taught me something. For example, Section 12.2 presents Articles 342 to 354 of Gauss' Disquisitiones Arithmeticae on the complex roots of the cyclotomic polynomial fp(x) = (xp–1)/(x–1) = xp-1 + xp-2 + ... + x + 1. Analytically the situation is as simple as it ever gets: the roots are nicely spaced on the unit circle. However Gauss was not satisfied with the analytic solution, and took a more constructive algebraic approach. Specialized to p of the form 2m+1, Gauss' approach solves fp(x) by iterated square roots, and Mora presents Gauss' famous solution in the case p = 17 explicitly. Mora's point is that Gauss's approach is clearly Kroneckerian, even though he was working some eighty years before Kronecker's main foundational paper. I gained a greater appreciation of this famous chapter of mathematical history and could briefly share in the enthusiasm of the MathSciNet reviewers.

SPES II. Next, I tried to take a close look at SPES II. After the preface, pages xiv–xxii describe the general setting. The first sentence of these pages is

Let k be an infinite, perfect field, where if p:=char(k) ≠ 0, it is possible to extract p-th roots,1 and let k be the algebraic closure of k.

My pitying reflex developed in SPES I immediately kicked in, as I could imagine readers who don't recognize that the "where...roots" clause is meant just as a reminder of the definition of perfect. Pitying became mixed with annoyance as the footnote informed me that both assumptions on the field are usually unnecessary, but because of the author's "absentmindedness" it is my "responsibility" to determine when the assumptions can be removed. The annoyance moved up a notch as I realized I would have to distinguish between k and k throughout the entire book. All these concerns from the first sentence! Calligraphic, bold, sans-serif, and gothic fonts are unusually abundant in the rest of xiv–xxii. I was tired before I reached page one.

Looking through the actual chapters of SPES II, it became rapidly apparent that I had become the reader I was pitying as I went through SPES I. My background was no longer enough to place the material into a meaningful context. My reaction to the epigraphs somewhat foreshadowed my reaction to the SPES II presentations. Just as I would have to track down what asphodel and hoopoe are if I wanted to understand the first Agrippa quote, I'd have to decode line after line of notation-heavy, word-light presentation to understand any SPES II section. I was not at all confident that this process would rapidly enlighten me and so I just stopped.

Conclusion. Where does this leave you, the reader of this review? I think you are likely to find the SPES volumes useful only if you have substantial previous familiarity with the material and are quite computationally inclined.

David Roberts is an associate professor of mathematics at the University of Minnesota, Morris.


Part one: The Kronecker - Duval Philosophy 1

1 Euclid
1.1 The Division Algorithm
1.2 Euclidean Algorithm
1.3 Bezout's Identity and Extended Euclidean Algorithm
1.4 Roots of Polynomials
1.5 Factorization of Polynomials
1.6* Computing a gcd
1.6.1* Coefficient explosion
1.6.2* Modular Algorithm
1.6.3* Hensel Lifting Algorithm
1.6.4* Heuristic gcd

2 Intermezzo: Chinese Remainder Theorems
2.1 Chinese Remainder Theorems
2.2 Chinese Remainder Theorem for a Principal Ideal Domain
2.3 A Structure Theorem (1)
2.4 Nilpotents
2.5 Idempotents
2.6 A Structure Theorem (2)
2.7 Lagrange Formula

3 Cardano
3.1 A Tautology?
3.2 The Imaginary Number
3.3 An Impasse
3.4 A Tautology!

4 Intermezzo: Multiplicity of Roots
4.1 Characteristic of a Field
4.2 Finite Fields
4.3 Derivatives
4.4 Multiplicity
4.5 Separability
4.6 Perfect Fields
4.7 Squarefree Decomposition

5 Kronecker I: Kronecker's Philosophy
5.1 Quotients of Polynomial Rings
5.2 The Invention of the Roots
5.3 Transcendental and Algebraic Field Extensions
5.4 Finite Algebraic Extensions
5.5 Splitting Fields

6 Intermezzo: Sylvester
6.1 Gauss Lemma
6.2 Symmetric Functions
6.3* Newton's Theorem
6.4 The Method of Indeterminate Coefficients
6.5 Discriminant
6.6 Resultants
6.7 Resultants and Roots

7 Galois I: Finite Fields
7.1 Galois Fields
7.2 Roots of Polynomials over Finite Fields
7.3 Distinct Degree Factorization
7.4 Roots of Unity and PrimitiveRoots
7.5 Representation and Arithmetics of Finite Fields
7.6* Cyclotomic Polynomials
7.7* Cycles, Roots and Idempotents
7.8 Deterministic Polynomial-time Primality Test

8 Kronecker II: Kronecker's Model
8.1 Kronecker's Philosophy
8.2 Explicitly Given Fields
8.3 Representation and Arithmetics
8.3.1 Representation
8.3.2 Vector space arithmetics
8.3.3 Canonical representation
8.3.4 Multiplication
8.3.5 Inverse and division
8.3.6 Polynomial factorization
8.3.7 Solving polynomial equations
8.3.8 Monic polynomials
8.4 Primitive Element Theorems

9 Steinitz
9.1 Algebraic Closure
9.2 Algebraic Dependence and Transcendency Degree
9.3 The Structure of Field Extensions
9.4 Universal Field
9.5* Lùuroth's Theorem

10 Lagrange
10.1 Conjugates
10.2 Normal Extension Fields
10.3 Isomorphisms
10.4 Splitting Fields
10.5 Traceand Norm
10.6 Discriminant
10.7* Normal Bases

11 Duval
11.1 Explicit Representation of Rings
11.2 Ring Operations in a Non-unique Representation
11.3 Duval Representation
11.4 Duval's Model

12 Gauss
12.1 The Fundamental Theorem of Algebra
12.2 Cyclotomic Equations

13 Sturm
13.1* Real Closed Fields
13.2 Definitions
13.3 Sturm
13.4 Sturm Representation of Algebraic Reals
13.5 Hermite's Method
13.6 Thom Codification of Algebraic Reals (1)
13.7 Ben-Or, Kozen and Reif Algorithm
13.8 Thom Codification of Algebraic Reals (2)

14 Galois II
14.1 Galois Extension
14.2 Galois Correspondence
14.3 Solvability by Radicals
14.4 Abel-Ruffini Theorem
14.5* Constructions with Ruler and Compass 318


Part two: Factorization

15 Prelude
15.1 A Computation
15.2 An Exercise

16 Kronecker III: factorization
16.1 Von Schubert Factorization Algorithm over the Integers
16.2 Factorization of MultivariatePolynomials
16.3 Factorization over a Simple Algebraic Extension

17 Berlekamp
17.1 Berlekamp's Algorithm
17.2 The Cantor-Zassenhaus Algorithm

18 Zassenhaus
18.1 Hensel's Lemma
18.2 The Zassenhaus Algorithm
18.3 Factorization Over a Simple Transcendental Extension
18.4 Cauchy Bounds
18.5 Factorization over the Rationals
18.6 Swinnerton-Dyer Polynomials
18.7 L3 Algorithm

19 Finale
19.1 Kronecker's Dream
19.2 Van der Waerden's Example