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.
Books:The primary course text will be the (draft) textbook Invitation to Nonlinear Algebra below. We will refer to this book as MS, the book by Cox, Little and O'Shea as CLO, and the book by Sommese and Wampler as SW as required in the course outline below.
Invitation to Nonlinear Algebra by Mateusz Michałek and Bernd Sturmfels.We will also reference the following books for certain portions of the course:
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.
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 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.A major component of this study will be the theory of Gröbner basis and of homotopy continuation. At the end of the course students will be able to answer such questions as: Does a given system of polynomials have finitely many solutions? If so, what are they? If there are infinitely many solutions, how can can these be described and understood?
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 4 (March 16): §1.3 and Chapter 2 of MS
- Week 5 (March 30): Chapter 2 of MS
- Week 6 (April 23): Chapter 2 of MS
- Week 9 (May 14): Chapter 4 of MS and Chapter 2 of SW
- Week 10 (May 20): Numerical Irreducible Decomposition
- 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
Assignments:Assignments and due dates will be posted here. All assignments are due at the beginning of class on the marked due date. The questions will primarily be taken from exercises in MS and CLO (due dates below are tentative).
- 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 denote the elementary symmetric polynomial of degree in variables and let be the ideal in generated by , ..., . Show that the monomials for form a k-basis for the quotient ring . 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 to be divided by and output a list of quotients and a remainder , 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).
- Regular Problems -- All from Chapter 1 of MS --: 1, 4, 5, 7, 13. Bonus Problem: 12.
- 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 .
- 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:
- 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.
- 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 ProblemsHere are some suggested problems from MS and CLO; you should be prepared to discuss some of these problems in the workshop time.
- 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 ScheduleMarch 18: W.C. (Suggested Questions: #6 from Ch. 1 of MS)
April 1: M.T. (Suggested Questions: #15 or both of #16 and #17 from Ch. 1 of MS)
April 22: I.L. (Suggested Questions: #10 of 2.7 in CLO or #12 from Ch. 2 of MS or #10 of Ch. 2 of MS)
April 29: M.S. (Suggested Questions: #11 from Ch. 2 of MS or #12 of Ch. 2 of MS or #8 of 8.2 in CLO or #18 of 8.2 in CLO)
May 6: A.O. (Suggested Questions: #3 from Ch. 3 of MS or #5 of Ch. 3 of MS or #10 of Ch. 3 of MS)
May 13: L.C. (Suggested Questions: #1 and #2 of Ch. 4 of MS or #5 of Ch. 3 of MS or #10 of Ch. 3 of MS)
May 20: A.Y. (Suggested Questions: #2 of Ch. 4 of MS or #10 of Ch. 4 of MS or #5 [Generalized Elimination Theorem] of 3.1 [Chapter 3, Section 1] of CLO)
May 27: A.W. (Suggested Questions: #2 of Ch. 4 of MS or #10 of Ch. 4 of MS or #9 [Application of Extension Theorem] of 3.1 [Chapter 3, Section 1] of CLO [Note the notation used by CLO for elimination ideals is a bit different but a quick glance through the chapter should make it clear])
June 3: P.M. (Suggested Questions: #1 of Ch. 6 of MS or #9 of Ch. 6 of MS or #8 of 4.1 [Chapter 4, Section 1] of CLO [Deals with: Any Variety over a Not Algebraically Closed Field Can be Defined By A Single Eq.])
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.Suggested Topics:
- 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 (M2 for short) and Sage are both excellent open source computer algebra systems with some very helpful functions for algebra, algebraic geometry and number theory (among other things).
- 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)
- 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
- Install Xserver and emacs (if desired)
Installing M2 in Windows
Homework Policy:There will be four assignments, worth about 11% each. These will consist primarily of problems from the course texts.
Some things to keep in mind when doing your homework:
- 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.
- 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.
- 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.
- If the grader is unable to make out your writing then this may hurt your mark.
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%
- Midterm: April 24 (tentative).