MATH3349/MATH4349/MATH6209 (Special Topics in Math): Computational Algebraic Geometry

ANU. Semester 1, 2020.

Zoom Lecture: Thursday 3:30 pm -- 5:30 pm.

Zoom Workshop: Wednesday 1:00 pm -- 2:00 pm.

Instructors:

Martin Helmer

Markus Hegland

Books:

Invitation to Nonlinear Algebra by Mateusz Michałek and Bernd Sturmfels.

Ideals, varieties, and algorithms : an introduction to computational algebraic geometry and commutative algebra (Fourth Edition) by David Cox, John Little, and Donal O'Shea.

The numerical solution of systems of polynomials arising in engineering and science by Andrew John Sommese and Charles W. Wampler. Note this book can be accessed by ANU students online via the university library.

The references below overlap with our course and interested students may enjoy consulting them on occasion. Note, however, that these references contain some material that we will not cover.

• Algebraic geometry: a first course by Joe Harris.
• Algebraic Geometry class notes by Andreas Gathmann.

Course Goals:

The goal of this course is to introduce students to algebraic geometry in a hands on manner. We will explore the use of both symbolic and numeric computational techniques in algebraic geometry. Students are encouraged to use computer tools such as Macaulay2 or Sage to explore examples and investigate problems.

The primary object at study will by systems of polynomial equations in $n$ variables. The solutions set of a system of polynomial equations forms a geometric object called a variety; we will see that this corresponds to a (radical) ideal in a polynomial ring. We will explore the geometry of varieties both computationally and abstractly using the algebraic structure of polynomial rings.

Course Schedule and Notes:

The dates of the lectures are approximate and may be adjusted slightly through the course of the term. Hand written notes from lecture will be uploaded here in the corresponding place in the schedule.

Polynomial Rings and Gröbner basis

• Week 1 (Feb 24): Chapter 1 of MS
• Lecture 1. M2 Example.

• Week 2 (March 2): Chapter 1 of MS and §2.7 of CLO
• Lecture 2. M2 Example.

• Week 3 (March 9): Chapter 1 of MS and §2.6 and §2.7 of CLO
• Lecture 3. M2 Example.

• Week 4 (March 16): §1.3 and Chapter 2 of MS
• Lecture 4. Workshop M2 Example. M2 Example.
• Week 5 (March 30): Chapter 2 of MS
• Lecture 5. Workshop M2 Example. M2 Example.
• Week 6 (April 23): Chapter 2 of MS
• Lecture 6. Workshop M2 Example. Lecture M2 Example.

• Week 7 (April 30): Chapter 3 of MS
• Lecture 7. Workshop M2 Example. Lecture M2 Example.

• Week 8 (May 7): Chapter 3 and 4 of MS
• Lecture 8. Workshop Notes. Lecture M2 Example.

• Week 9 (May 14): Chapter 4 of MS and Chapter 2 of SW
• Lecture 9. Workshop Notes. Workshop M2 Example.
• Week 10 (May 20): Numerical Irreducible Decomposition
  • Workshop 10 Notes. Workshop 10 M2 Example.

• Week 10 (May 21):
• Lecture Notes.
• Floating Point and Dyadic Fractions. M2 Code. Jupyter Notebook
• Rounding Errors. M2 Code. Jupyter Notebook
• Homotopy Continuation in Practice.
• Numerical Considerations: One Variable Homotopy Continuation. M2 Code. Jupyter Notebook
• Condition Numbers. M2 Code. Jupyter Notebook
• Computing GCD. M2 Code. Jupyter Notebook

• Week 11 (May 28): Chapter 6 of MS
• Lecture Notes. M2 Example..

• Week 12 (June 4): Chapter 8 of MS
• Lecture Notes. M2 Example..

Assignments:

• Assignment 1. Due March 30.
  • Regular Problems -- All from Chapter 1 of MS --: 1, 4, 5, 7, 13. Bonus Problem: 12.
    • Hint for problem 12: Let ${e_i}^n$ denote the elementary symmetric polynomial of degree $i$ in $n$ variables and let $I_n$ be the ideal in generated by ${e_1}^n$, ..., ${e_n}^n$. Show that the monomials $x^a$ for $0\le a_j\le \mathrm{n-j}$ form a k-basis for the quotient ring $\mathrm{R/}{I}_n$. More details here.
  • Programming Problem 1: Implement a M2/Sage function which performs the multivariate polynomial division algorithm (we will discuss this in workshop on March 11); this can be found in 2.3 of CLO (see Theorem 3 in that section). Your algorithm should take as input a polynomial along with the list of polynomials $f_1\mathrm{,...,}{f}_{\mathrm{r}}$ to be divided by and output a list of quotients $q_1\mathrm{,...,}{q}_{\mathrm{r}}$ and a remainder $r$, both in .
  • Programming Problem 2: Using your division algorithm implementation from Problem 1 implement the version of Buchberger's Algorithm presented in class (see also Theorem 2 in 2.7 of CLO). Comment on how your implementation compares in speed to the standard M2/Sage implementation, suggest a possible improvement (you don't need to implement this, just comment on it... you can write this as a brief comment in your code file).
• Assignment 2. Due April 28.
  • From Chapter 2 of MS: 1, 2, 3, 5, 14.
  • From 2.7 of CLO: 11 (If you don't have the book: Show that the result of applying the Euclidean Algorithm to a pair of single variable polynomials is a reduced Gröbner basis for the ideal they generate and explain how the steps of the Euclidean Algorithm can be seen as special cases of the operations used in Buchberger's algorithm).
  • M2/Sage Problem.
• Assignment 3. Due May 20.
  • From Chapter 3 of MS: 6, 7, 8, 9, 13. For #9 and #13 you may (and should) use M2/Sage to prove that your example is as requested. For #9 you can work over the rationals, Q. That is, even though you work over Q in Sage/M2 the degree of the ideal I you construct is the number of points in your variety V(I) over the complex numbers provided your ideal is zero dimensional and radical. Hint for #6, consider the decomposition for some positive integer $n$.
  • M2/Sage Problems.
  • M2/Sage Problems LaTex file.
• Assignment 4. Due June 5.
  • Regular Problems: Chapter 4, #8 from MS and Chapter 6, #3 from MS.
  • Programming Problems:
    1. Implement the single variable homotopy continuation path-tracker in M2/Sage. You should use the algorithm presented in class (Euler predictor + Newton corrector), this is also presented in Chapter 2 of SW. Use this along with the M2/Sage Gröbner basis function to program a method which computes floating point approximations of all solutions to a multi-variant polynomial system defined by a zero dimensional ideal. Test your implementation on some examples.
    2. What happens if you apply your homotopy continuation method to a one variable polynomial with repeated roots? Can you think of a way to avoid this problem assuming you don't need to preserve the multiplicity of the repeated root (there is no need to implement this, just 1-2 sentences about possible solutions is fine)?

Practice Problems

• Problem Set 1 (Week 1 -- 4).
  • Problems 1 -- 20 from Chapter 1 of MS.
• Problem Set 2 (Week 5 & 6).
  • Problems 1 -- 17 from Chapter 2 of MS.
• Problem Set 3 (Week 7 & 8).
  • Problems 1 -- 17 from Chapter 3 of MS.
  • Problems 1 -- 12 from Chapter 4.8 of CLO (pg 231).

Workshop Presentation Schedule

Term Project/Paper:

This course will involve a term project. The project will require students to independently study a class-related topic. The results of your work and the understanding that you have gained will be summarized in a short paper. Your paper should be self-contained and should be written so that to the other students in our class can understand it. The target length will be approximately 10 pages. If appropriate your project may also have a software component, in such cases the report may be somewhat shorter but should still contain the ideas behind the algorithms present in your software.

• Any of the the topics listed in Appendix D §2 of CLO.
• A topic of your suggestion (please run it by me).
• Tropical Geometry: The goal here would be to expand on what is covered in Chapter 7 of MS by consulting other references.
• Tensors: The goal here would be to expand on what is covered in Chapter 9 of MS by consulting other references.
• Representation Theory: The goal here would be to expand on what is covered in Chapter 10 of MS by consulting other references.
• Semidefinite Programming: The goal here would be to expand on what is covered in Chapter 9 of MS by consulting other references.
• Automated Geometric Theorem Proving: The goal here would be to expand on what is covered in §6.4 of CLO by consulting other references.
• Robotics and Kinematics: The goal here would be to expand on what is covered in §6.1 to §6.3 of CLO by consulting other references.
• Invariant Theory of Finite Groups. The goal here would be to summarize and expand on what is found in CLO and MS.
• Modern Gröbner Bases algorithms. The goal of this project would be to describe recent advances in algorithms to compute Gröbner Bases. A starting point for this would be Chapter 10 of CLO, and in particular §10.3 and §10.4. This project would be a good candidate to include some programming, but it would not be required.
• A brief introduction to intersection theory and the Chow ring. This is covered in Chapter 1 of the first reference. This project could, for example, focus on a proof of Corollary 2.4 of the first reference below (note that this project involves many new concepts beyond what we cover in class):
  • David Eisenbud, and Joe Harris. 3264 and all that: A second course in algebraic geometry. Cambridge University Press, 2016.
  • William Fulton. Introduction to intersection theory in algebraic geometry. No. 54. American Mathematical Soc., 1984.

• April 7: Proposal Submission
• June 1: Draft Submission
• June 8: Peer Review Submission
• June 19: Project Submission

• Main report: 80% of your project grade
• This should be an approximately 10 page report detailing what you have studied. It should give the key definitions and build to some sort of main result, either a theorem or algorithm, and it should detail the theoretical basis for this result in either case. Your report should be written so that other students in the class can understand it.
• Peer review: 10% of your project grade
• As part of your projects you will be asked to swap a first draft with one other student in the class. You will then write feedback on the other students report, this feedback should point out any mathematical (or typographical) errors you note and should offer comments on things that could be clarified. Your mark for this will be based on your comments, i.e. on how well you critically read the other students work
• Proposal: 10% of your project grade
• A one page outline of what you propose to study and how you plan to do so.
• There may be an option to give a talk on your project, but this will depend on scheduling and level of interest.

• You may partner with another student to jointly explore a related topic, however you must each submit your own independently written term paper. In particular you and your exploration partner should focus on at least slightly different aspects of the topic.
• You may have overlapping (but independently written) definitions and background, but your main result should be different.
• If you find these guidelines unclear please speak to me about it.

• Your project (and ideally your proposal) should be prepared using LaTex. To get you started there is an example file below.
• The tex file
• The resulting pdf file

Algebra Software:

• Macaulay2
• Download and install
• Use online
• M2 may also be used online via the Sage Math Cloud. To use M2 this way create an account (this is free) and open a new project, then start a new Terminal (>_ icon). Once the Sage terminal opens type the command: M2. M2 will then open and you can enter M2 commands.
• Computations in polynomial rings:
• Polynomial Rings
• Quotient Rings
• Factoring Polynomials
• Computing gcd
• Division with remainder, i.e. getting a representative in a quotient ring, inverting an element in a quotient ring which is also a field etc.
• Check if an integer or ideal is prime
• Check equality of ideals (or numbers or other objects)

Installing M2 in Windows

• Download/install Ubuntu 18.04 from the Windows Store
• Follow the Ubuntu Install instructions for M2 (if you use 18.04 Ubuntu the following should do it)
• sudo echo 'deb http://www.math.uiuc.edu/Macaulay2/Repositories/Ubuntu bionic main' >/etc/apt/sources.list.d/macaulay2.list
• sudo apt-key adv --keyserver hkp://keys.gnupg.net --recv-key CD9C0E09B0C780943A1AD85553F8BD99F40DCB31
• sudo apt-get update -q
• sudo apt-get install -y -q macaulay2
Then typing 'M2' in the Ubuntu terminal should do it, optionally you can also install Xserver and run the emacs GUI.
• Install Xserver and emacs (if desired)
• Sage
• Sage Cell
• Sage Math Cloud
• Computations in polynomial rings:
• Univariate Polynomial Rings Description
• General Polynomial Rings Description

Homework Policy:

Some things to keep in mind when doing your homework:

1. You are encouraged to discuss problems with your classmates and are free to consult online resources. Working together on math problems can be an excellent way to learn and the internet is a useful resource. However your final written solutions you hand in must be your own work written in your own words, that is your final solutions must be written by yourself without consulting someone else's solution.
2. All solutions should be written in complete, grammatically correct, English (or at least a very close approximation of this) with mathematical symbols and equations interspersed as appropriate. These solutions should carefully explain the logic of your approach.
3. All proofs must be complete and detailed for full marks. Avoid the use of phrases such as 'it is easy to see' or 'the rest is straightforward', you will likely be docked marks. Proofs in your homework should be clear and explicit and should be more detailed than textbook proofs.
4. If the grader is unable to make out your writing then this may hurt your mark.

Grading:

You will have the option to give a final talk on your term project; this will effect the grade breakdown. Giving a final talk is encouraged, but not required.

If you do give a presentation the grades will be broken down as follows:

• Assignments: 43%
• Written Portion of Term Project: 43%
• Oral Presentation on Term Project: 7%
• Participation in Workshop Discussions: 7%

If you do not give a presentation the grades will be broken down as follows:

• Assignments: 45%
• Term Project: 48%
• Participation in Workshop Discussions: 7%

Exam Dates:

• Midterm: April 24 (tentative).