Mini Course on Real Algebraic Numbers (July 2004)

In the continuing mini course series at AG 1 of the Max-Planck-Institut für Informatik, Arno Eigenwillig gives a...

«Mini Course on Real Algebraic Numbers»
on Tuesday and Thursday at 16:15-17:45 in room 46/024;
starting Tue, July 6th and ending Tue, July 20th.

This mini course started out with the idea to do "something on non-linear computational geometry and the algebraic methods it needs" in a bottom-up fashion. While collecting material and preparing the first lecture, it became clear to me that in the limited time frame of 4 × 90 minutes, we cannot get much further from the bottom than to cover real algebraic numbers and their algorithmic treatment. I'd like to address the following three items which I consider to be particularly interesting:

  1. Let us refresh our knowledge about the axiomatization and construction of the reals. Then let's see what kind of effective representation this gives rise to: guaranteed approximation.
    For that last part I recommend a recent paper by Chee Yap.
  2. Then let's take a less analytic and more algebraic perspective and discuss symbolic computation with algebraic numbers, especially real algebraic numbers. This is the main topic of the course. It requires us to look first at computations with polynomials.
  3. Finally, as probably the most general application of real algebraic numbers, I want to talk about the decidability of their first-order logic. I believe this positive result is worth knowing when you work on problems that have a continuous aspect to them; just like the classical limits of computability and the closely related undecidability of the first-order theory of the integers are important to be aware of for discrete problems.
Schedule:

Tue, July 6th Rational, real, complex, algebraic, and transcendental numbers.
Computing with guaranteed approximations.
Lecture notes (.ps.gz)
Thu, July 8th no mini course (speaker absent)
Tue, July 13th Univariate polynomials. Algebraic numbers, 1st half.
Click here for references.
Exceptional room for this day: 46/021
Thu, July 15th Algebraic numbers, 2nd half.
Click here for references.
Tue, July 20th The first order theory of real closed fields is decidable.
Click here for references.