Fundamental Problems in Algorithmic Algebra

Chee Keng Yap Courant Institute of Mathematical Sciences New York University 251 Mercer Street New York, NY 10012

September 8, 1993

TO BE PUBLISHED BY PRINCETON UNIVERSITY PRESS

Copyright Reserve: This preliminary version may be copied, in part or wholly, for private use provided this copyright page is kept intact with each partial or whole copy. For classroom distribution, please request permission. Contact the author at the above address for the on-going changes to the manuscript. The reader is kindly requested to inform the author of any errors, typographical or otherwise. All suggestions welcome. Electronic mail: yap@cs.nyu.edu.

Contents

0. Introduction I. Basic Arithmetic II. The GCD III. Subresultants IV. Modular Techniques: Chinese Remainder V. Fundamental Theorem of Algebra VI. Roots of Polynomials VII. Sturm Theory VIII. Gaussian Lattice Reduction IX. Lattices and Polynomial Factorization X. Elimination Theory XI. Gröbner Bases XII. Continued Fractions

PREFACE

These notes were first written for a course on Algebraic Computing: Solving Systems of Polynomial Equations, given in the Spring Semester of 1989 at the Free University of Berlin. They were thoroughly revised following a similar course at the Courant Institute in the Spring of 1992. Prerequisites are an undergraduate course in algebra and a graduate course in algorithmics.

I regard this course as an introduction to computer algebra. The subject matter (‘starting from the Fundamental Theorem of Algebra’) is as classical as one gets in theoretical computer science, and yet it is refreshingly contemporary in interest. This is because the complexity viewpoint exposes many classical questions to new light. There is a common misunderstanding that equates computational mathematics with numerical analysis. In fact, it seems to me that the older name of “symbolic manipulation” given to our field arose as a direct contrast to “numerical computation”. The preferred name today is “computer algebra”, although I feel that “algorithmic algebra” gives a better emphasis to the fundamental nature of the subject. In any case, computer algebra uses quite distinct techniques, and satisfies requirements distinct from that in numerical analysis. In many areas of computer application (robotics, computeraided design, geometric modeling, etc) computer algebra is now recognized as an essential tool. This is partly driven by the wide-spread availability of powerful computer work-stations, and the rise of a new generation of computer algebra systems to take advantage of this computing power.

The full spectrum of activity in computer algebra today covers many important areas that we do not even give a hint of in these lectures: it ranges from more specialized topics such as algorithmic integration theory, to implementation issues in computer algebra systems, to a highly developed and beautiful complexity theory of algebraic problems, to problems in allied application areas such as robot motion planning. Our material is necessarily selective, although we feel that if one must cut one swath from the elementary into the deeper parts of the subject in an introductory course, this is a choice cut. Historically, what we identified as “Fundamental problems” in these lectures were clearly central to the development of algebra and even of mathematics. There is an enormous amount of relevant classical literature on these fundamental problems, in part a testimony to the strong algorithmic nature of mathematics before the twentieth century. Even when restricted to this corpus of knowledge (classical, supplemented by modern algorithmic development), my colleagues will surely notice important gaps. But I hope they may still find this book useful as a launching point into their own favorite areas.

We have tried to keep the style of the book close to the lecture form in which this material originally existed. Of course, we have considerably expanded on the lecture material. This mainly consisted of the filling in of mathematical background: a well-equipped student may skip this. The teacher could convey the central ideas quickly at the expense of generality, for instance, by assuming that the rings under discussion are the “canonical examples” ( and F [X]). One teaching plan is to choose a subset of the material in each Lecture Section of this book for presentation in a 2-hour class (the typical length of class at Courant), with the rest assigned for further reading.

I thank Frau Schottke from the Free University for her dedicated transcription of my original hand-written notes into the computer.

Chee Yap Greenwich Village September 8, 1993