CS 867 - Algorithmic Properties of
Polynomial Rings

University of Western Ontario
Computer Science Department

Date: September 11, 2009

It is a standard problem in mathematical sciences to study which properties of a given structure are preserved in derived structures. A trivial example of such preservation is the fact that every subgraph of a planar graph is itself planar. A more involved example is the fact that, if $R$ is a unique factorization domain, then so is the ring $R[x]$ of univariate polynomials over $R$. Many algorithms rely on properties that are preserved under certain transformations. For instance, if $R$ is again a unique factorization domain, then the so-called subresultant algorithm reduces polynomial gcd computations in $R[x]$ to number gcd computations in $R$. In this course, we will discuss the algorithmic properties of $R$ that can be lifted to $R[x]$, with an emphasis on those which help solving systems of equations. In particular, we will discuss the lifting from $R$ to $R[x]$ of prime and primary decomposition of ideals.

Here's a tentative schedule for the lectures.

1. Commutative Rings (January, 11)
2. Univariate polynomials (January, 18)
3. Polynomial GCDs over direct products of fields (January, 25)
4. Resultants (February, 1)
5. Prime and primary decompositions (February, 8 and 15)
6. Zero-dimensional ideals (March, 1 and 8)
7. Regular chains (March, 15 and 22)
8. Gröbner bases over rings (March, 29 and April, 5)
9. Student presentations (TBA)

The six first lectures deal with standard subjects of a commutative algebra course. It is assumed that the participants have some familiarity with the notions presented there. Indeed, we will revisit them with an emphasis on algorithmic properties.

Then six last lectures cover non-classical subjects that were developed in the last decades by computer algebraists. The theory of regular chains, introduced by M. Kalkbrener in 1991, will be the central notion of this second series. It is recognized today that regular chains are among the most efficient tools for exact solving of systems of algebraic or differential equations.

Outlines.

To be posted.

Lectures.

To be posted.

Projects.

To be posted.

Resources.

These are links to some books and software related to the course.

• The Ideals, Varieties, and Algorithms book
• The Using Algebraic Geometry book
• The AXIOM Computer Algebra System at NAG ltd
• AXIOM Today