Algorithmic Algebraic Geometry (Fall 2011)

Math 648 (Sec. 600)

TuTh: 15:55-17:10, ENPH 201

Instructor: Prof. J. Maurice Rojas
E-mail: rojas@math.tamu.edu
Web Page: http://www.math.tamu.edu/~rojas

Algebraic geometry was born over two millenia ago, with the aim of understanding how to solve polynomial equations. While algebraic geometry pursued deeper and deeper abstract questions in the 20th century, the need for robust and efficient algorithms for equation solving has always remained. Especially now, applications such as chemistry, signal processing, robotics, coding theory, optimization, mathematical biology, computer vision, game theory, and statistics need efficient polynomial system solving.

Math 648 gives an introduction to algebraic geometry from a quantitative and algorithmic point of view. Students completing this course will be well-prepared to understand recent developments in areas such as algebraic complexity, algorithmic number theory, coding theory, and computational algebra. Also, the foundations are presented from a broad point of view, emphasizing the connections of algebraic geometry to number theory and combinatorics.

Policies and Syllabus

Handouts, Homework, and Other Announcements

Office Hours: W 13:00-17:00, and by appointment, in Milner 206

MAIN REFERENCES:

• [BCSS98] Complexity and Real Computation, by L. Blum, F. Cucker, M. Shub, and S. Smale, Springer-Verlag 1998.
• [Roj09] Algorithmic Complexity in Algebraic Geometry, by J. Maurice Rojas, in preparation.
• [Stu02] Solving Systems of Polynomial Equations, by Bernd Sturmfels, CBMS Lecture Series, AMS Press, 2002.
• Course Reader (a constantly growing collection of excerpts from recent books, expository papers, and research papers).

SUPPLEMENTAL REFERENCES:

• [Ahl78] Complex Analysis, Lars V. Ahlfors, 3rd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., 1978.
• [BS96] Algorithmic Number Theory, Eric Bach and Jeff Shallit, MIT Press, 1996.
• [CLO97] Ideals, Varieties, and Algorithms, by David A. Cox, John B. Little, and Donal O'Shea, Springer-Verlag, 1997.
• [CLO98] Using Algebraic Geometry, by David A. Cox, John B. Little, and Donal O'Shea, Springer-Verlag, 1998.
• [GKZ94] Discriminants, Resultants, and Multidimensional Determinants, by Israel M. Gel'fand, Misha M. Kapranov, and Andrei V. Zelevinsky, Mathematics: Theory & Applications, Birkhauser Boston, Inc., Boston, MA, 1994.
• [IMS09] Tropical Algebraic Geometry, by Ilia Itenberg, Grigory Mikhalkin, and Evgenii Shustin; Oberwolfach Seminars, Birkhauser Basel, 2nd ed., 2009.
• [Pap94] Computational Complexity, by Christos H. Papadimitriou, Addison-Wesley, Reading, MA, 1994.
• [Zie95] Lectures on Polytopes, Gunter M. Ziegler, Springer-Verlag, 1995.

Syllabus:

We'll cover topics in numerical analysis (NA) not usually covered in any algebraic geometry class, topics in algebraic geometry (AG) not usually covered in any numerical analysis class, and topics in algorithmic complexity not usually covered in any course on NA or AG. The precise topics will most likely be a subset of the following:

Applications of polynomial system solving and external motivations for algebraic and arithmetic geometry...

Preliminaries on binomial systems

Random polynomials and the harmonious fundamental theorem of algebra

Amoeba theory in low-dimensions

Homotopy inspired proof of the Fundamental Theorem of Algebra

Smale's 17th Problem

Topological and geometric preliminaries

Algebraic preliminaries, including univariate discriminants

Descartes' Rule of Signs and an easy proof of a weak version which extends to exponential sums

The univariate case of the Gelfond-Kazarnovski-Khovanski theorem on complex fewnomials

Many polyhedral connections along the way...

Newton's method

Smale's alpha theory and the effective inverse function theorem

The robust alpha theorem and an intro to univariate polynomial equation sol ving

Projective space

Bezout's Theorem with multiplicities

Kushnirenko's Theorem and an outline of its proof

Toric Varieties

Stochastic Kushnirenko's Theorem via the momentum map

Some facts on algebraic curves and completing Kushnirenko's Theorem

The A-Discriminant

Bernstein's Theorem and an outline of its proof

Mixed Subdivisions

Toric Resultants

...and Turing/BSS Complexity, P=?NP, Numerical conditioning, Homotopy Algorithms, Khovanski's Theorem on Fewnomials, Effective Nullstellensatze, Resultants and Eigensolving, Semi-Algebraic Sets, Connections to Number Theory, Connections to Semidefinite Programming.

Note: Since this course presents some very results, this syllabus is subject to change. (Last updated 8/31/2011.)

---