Tutorial: Real Algebraic Geometry

Aim of this tutorial: to provide a transition from elementary real algebraic geometry (represented, for example by Cox, Little and O’Shea (2005)) to more advanced topics in this area (represented, for example, by Basu, Pollack and Roy (2003)).

We shall mainly be interested in semi-algebraic sets. These are subsets of real n-space that are defined by a finite number of polynomial equations and polynomial inequalities.

One of the main results in this area is Tarski’s theorem that the elementary theory of algebra and geometry is decidable. (See Tarski(1951).) In particular, whether a semi-algebraic set is non-empty is decidable. It also follows that every subset of real n-space definable by a first order formula is semi-algebraic.

Prerequisites for this tutorial: a basic knowledge of linear algebra and the rudiments of a basic course in algebra through the definitions and basic properties of groups, rings and fields, and in topology through the elementary properties of closed, open, compact and connected sets.

This tutorial should be of interest to students and researchers in mathematics, computer science and engineering

References:

• Basu, S.; Pollack, R. and Roy, M-F. (2003) Algorithms in Real Algebraic Geometry, Springer.
• Cox, D.; Little, J. and O’Shea, D. (2005) Ideals, Varieties, and Algorithms, Springer.

• Tarski, A. (1951) A decision method for elementary algebra and geometry, Prepared for publication by J. C. C. McKinsey. University of California Press. Available at http://perso.univ-rennes1.fr/marie-francoise.roy/Tarski51.pdf

• Thursday, July 5, 2007, 409 Lind Hall, Tim Hardy (Mathematics Department, Wayne State College, Nebraska)

  Distance matrices

  Abstract: A "distance matrix" is a matrix containing the distances, taken pairwise, of a set of points. I shall trace the history of distance matrices during the last 150 years. I shall develop distance matrices from an inner product. I shall present some applications and at least one generalization.



• Thursday, June 28, 2007, 409 Lind Hall, Kenneth R. Driessel (Department of Mathematics, Iowa State University)

  Border bases (continued)

  Abstract: We discussed border bases on May 21 and June 7 June 14 and June 21. We shall continue that discussion.

  I continue to look at the following books and papers:

  Kehrein, A; Kreuzer, M. and Robbiano, L. (2005) "An algebraist's view of border basis", in Dickenstein, A. and Emiris, I.Z. (2005), Solving Polynomial Equations}, Springer.

  Mourrain, B. (1999) "A new criterion for normal form algorithms", in Applied algebra, algebraic algorithms and error-correcting codes (Honolulu, HI, 1999), 430-443, Lecture Notes in Computer Science, 1719, Springer.

  Stetter, H.J. (2004) Numerical Polynomial Algebra, SIAM.

  I plan to mainly follow the last few chapters in the book by Stetter.

  As usual, I shall try to minimize prerequisites.



• Thursday, June 21, 2007, 409 Lind Hall, Kenneth R. Driessel (Department of Mathematics, Iowa State University)

  Border bases (continued)

  Abstract: We discussed border bases on May 21 and June 7 June 14. We shall continue that discussion.

  I continue to look at the following books and papers:

  Kehrein, A; Kreuzer, M. and Robbiano, L. (2005) "An algebraist's view of border basis," in Dickenstein, A. and Emiris, I.Z. (2005), Solving Polynomial Equations}, Springer.

  Mourrain, B. (1999) "A new criterion for normal form algorithms," in Applied algebra, algebraic algorithms and error-correcting codes (Honolulu, HI, 1999), 430-443, Lecture Notes in Computer Science, 1719, Springer.

  Stetter, H.J. (2004) Numerical Polynomial Algebra, SIAM.

  I shall continue to mainly follow the paper/chapter by Kehrein, Kreuzer and Robbiano.

  As usual, I shall try to minimize prerequisites.



• Thursday, June 14, 2007, 305 Lind Hall, Kenneth R. Driessel (Department of Mathematics, Iowa State University)

  Border bases (continued)

  Abstract: We discussed border bases on May 21 and June 7. We shall continue that discussion.

  I continue to look at the following books and papers:

  Kehrein, A; Kreuzer, M. and Robbiano, L. (2005) "An algebraist's view of border basis", in Dickenstein, A. and Emiris, I.Z. (2005), Solving Polynomial Equations}, Springer.

  Mourrain, B. (1999) "A new criterion for normal form algorithms", in Applied algebra, algebraic algorithms and error-correcting codes (Honolulu, HI, 1999), 430-443, Lecture Notes in Computer Science, 1719, Springer.

  Stetter, H.J. (2004) Numerical Polynomial Algebra, SIAM.

  I shall continue to mainly follow the paper by Kehrein, Kreuzer and Robbiano.

  As usual, I shall try to minimize prerequisites.



• Thursday, June 7, 2007, 305 Lind Hall, Kenneth R. Driessel (Department of Mathematics, Iowa State University)

  Border bases (continued)

  Abstract: We discussed border bases for a short time on May 21. We shall continue that discussion (after a review since we did not meet last week). I have been looking at the following books and papers:

  Kehrein, A; Kreuzer, M. and Robbiano, L. (2005) "An algebraist's view of border basis", in Dickenstein, A. and Emiris, I.Z. (2005), Solving Polynomial Equations}, Springer.

  Mourrain, B. (1999) "A new criterion for normal form algorithms", in Applied algebra, algebraic algorithms and error-correcting codes (Honolulu, HI, 1999), 430-443, Lecture Notes in Computer Science, 1719, Springer.

  Stetter, H.J. (2004) Numerical Polynomial Algebra, SIAM.

  I shall mainly follow the paper by Kehrein, Kreuzer and Robbiano.

  As usual, I shall try to minimize prerequisites.



• Thursday, May 24, 2007, Kenneth R. Driessel (Department of Mathematics, Iowa State University)

  Numerical polynomial algebra

  Abstract: See the book "Numerical Polynomial Algebra" by H. J. Stetter, SIAM, 2004.



• Thursday, May 17, 2007, Kenneth R. Driessel (Department of Mathematics, Iowa State University)

  Sums of squares of polynomials (continued)

  Abstract: The value of a multivariate polynomial that is a sum of squares of polynomials is always weakly positive. But there are some multivariate polynomials that are always weakly positive and yet not sums of squares. We shall continue to discuss this matter.



• Thursday, May 10, 2007, Kenneth R. Driessel (Department of Mathematics, Iowa State University)

  Sums of squares of polynomials

  Abstract: The value of a multivariate polynomial that is a sum of squares of polynomials is always weakly positive. But there are some multivariate polynomials that are always weakly positive and yet not sums of squares. We shall discuss this matter.

  I shall use the following paper as a basis for our discussion:

  "An algorithm for sums of squares of real polynomials" by V. Powers and T. Woermann, J. of Pure and Applied Algebra 127 (1998) .

  You can also find a copy of the paper on Thorsten Woermann's web site.

  In the paper, Powers and Woermann present "an algorithm to determine if a real polynomial is a sum of squares of polynomials,and an explicit representation if it is a sum of squares. This algorithm uses the fact that a sum of squares representation of a real polynomial corresponds to a real, symmetric, positive semi-definite matrix whose entries satisfy certain liner equations."

  We shall discuss a number of applications of this algorithm.

  As usual I shall try to minimize prerequisites.

  

• Thursday, May 3, 2007, Richard B. Moeckel (School of Mathematics, University of Minnesota)

  Some applications of real root counting to mechanics

  Abstract: This talk is intended to illustrate some of the methods covered last semester in the real algebraic geometry tutorial. I will describe some problems from celestial mechanics which can be reduced to counting real roots of systems of polynomial equations. I will show how to solve some of the simplest ones by using Sturm's algorithm and Hermite root counting and will mention several open problems.



• Thursday, April 26, 2007, Joel Roberts (School of Mathematics, University of Minnesota)

  Real and complex varieties: comparisons, contrasts and examples
  html version of the presentation

  Abstract: Properties of a complex variety often can be illustrated by a picture of its real locus. Conversely, we can often understand a real variety by studying the corresponding complex variety. At the same time, there are cases where the properties of real varieties and complex varieties are quite different. This can include basic properties like connectedness, compactness, and local dimension near singular points.

  In this talk we will exhibit pictures of some curves and surfaces, that illustrate some of these similarities and differences. These figures will include several types of surfaces in R³.

  Many of the surface pictures are interactive, in that they are posted on a webpage, where the viewer — using nothing more than a Java-enabled browser — can rotate the figure continuously by dragging it with the mouse.

  

  Kenneth R. Driessel (Department of Mathematics, Iowa State University)
  Tutorial Notes
• Thursday, April 12, 2007, Applications of the abstract Positivstellensatz
• Thursday, April 5, 2007, The generalized abstract Positivstellensatz
• Thursday, March 29, 2007, Real rings (continued)
• Thursday, March 22, 2007, Real rings (continued)
  Recall that we started to talk about real rings on March 1. The topic was new for us at that time.

  Also recall that a commutative ring with identity is "real" if the only representation of zero as the sum of squares is the trivial one.

  Since we did not meet during the last two weeks, I shall include an substantial review as part of our discussion.

  I shall mainly follow the material in the chapter "Real Rings" in the book "Positive Polynomials" by Prestel and Delzell.

  Our objective will be a proof of an absrtact version of the real Nullstellensatz.

• Thursday, March 1, 2007, Real rings
  A commutative ring with identity is "real" if the only representation of zero as the sum of squares is the trivial one.

  This will be a new topic for us. I shall try to minimize prerequisites.

  I shall mainly follow the material in the chapter "Real Rings" in the book "Positive Polynomials" by Prestel and Delzell.

  Our objective will be a proof of the real Nullstellensatz.

• Thursday, February 22, 2007, Quotients of polynomial rings, Hermite's quadratic form and root counting (continued)
  I shall mainly follow the material in the section "Zero-dimensional systems" in the book by Basu, Pollack and Roy.
• Thursday, February 15, 2007, Quotients of polynomial rings, Hermite's quadratic form and root counting (continued)
  I shall mainly follow the material in the section "Zero-dimensional systems" in the book by Basu, Pollack and Roy.
• Thursday, February 8 , 2007, Quotients of polynomial rings, Hermite's quadratic form and root counting (continued)
• Thursday, February 1 , 2007, Quotients of polynomial rings, Hermite's quadratic form and root counting
  I shall mainly follow the material in the section "Zero-dimensional systems" in the book by Basu, Pollack and Roy.
• Thursday, January 25, 2007, Semi-algebraic sets and functions
• Thursday, December 14, 2006, Quadratic forms and root counting (continued)
• Thursday, December 7, 2006, Quadratic forms and root counting
• Thursday, November 30, 2006, The projection theorem for semi-algebraic sets (continued)
• Wednesday, November 22, 2006, The projection theorem for semi-algebraic sets Note day change due to the Thanksgiving Holiday.
• Thursday, November 16, 2006, Elimination of quantifiers (continued)
• Thursday, November 9, 2006, Elimination of quantifiers
• Thursday, November 2, 2006, Sturm's root counting theorem and Tarski's generalization (continued)
• Thursday, October 19, 2006, Sturm's theorem and Tarski's generalization
• Thursday, October 12, 2006, Closure operators and Galois connections
• Thursday, October 5, 2006, A first order language for ordered rings
• Thursday, September 28, 2006, Ordered rings and fields (continued)
We shall continue to discuss ordered rings and fields.
• Thursday, September 14, 2006, Ordered rings and fields