The Complexity of Solving Polynomial Equations over Local Fields
Vorlesung
Lectures: Prof. Dr. Maurice Rojas
Tutorial management: Dipl.-Math Viviana Ghiglione
Tutorials: Dipl.-Math Viviana Ghiglione

News Course Topics and Prerequisites Schedule Exercise Sheets Literature Exam Projects FAQ

News

  • Nov. 16th The inspection will take place on Wednesday 18th November 13--15 in Prof. Rojas' office (02.04.055).
  • Nov. 10th As a preparation for the exam, you can practise on homework 5.
  • Nov. 10th A corrected version of hw3 has been uploaded.
  • Nov. 5th The Repetition of the Exam will take place on November 27th, check details below.
  • Nov. 5th The list of Papers that could be chosen for the projects have been uploaded in the dedicated section.
  • Oct. 28th Notes on Sylvester Resultant and Separation of Roots have been uploaded.
  • Oct. 21st The Lectures are now scheduled from 10:15 to 12.
  • Oct. 15th The Lecture on Tuesday 10 November will not take place due to the Studentische Vollversammlung SVV.
  • Oct. 14th The written part of the exam will take place on Thursday 12 November, at 10:15, in room 02.04.011. For more details, check the dedicated section below.
  • Oct. 14th The first homework (not to be handed-in) and Viro's "Dequantization of Real Algebraic Geometry on Logarithmic Paper" have been uploaded. Other notes will be handed-in in the lecture.
  • Oct. 13th The first Tutorial is scheduled for Thursday, Oct. 22nd.

Course Topics and Prerequisites

Topics: We present a novel introduction to algebraic geometry through the problem of solving polynomial equations over the complex, real, and p-adic numbers. We pay special attention to algorithms and applications, and assume no background beyond linear algebra and basic knowledge of programming. In particular, we introduce all necessary number-theoretic background along the way, and develop fast algorithms requiring little or no commutative algebra. We will see how tropical geometry enables us to dramatically simplify earlier, more algebraic approaches, and more efficiently develop an intuition for solving equations over different fields (including finite fields). We will also see concretely how randomization and approximation leads to a new perspective on classical algebraic geometry.

Prerequisites: A solid undergraduate background in linear algebra and writing proofs. Some background in programming (in Maple, Matlab, or Sage) would be helpful but not of critical importance. Knowledge of Hermite and Smith factorization of matrices, p-adic numbers, and triangulations of polytopes would also be helpful, but not critical. The course will be self-contained but the more background you have, the deeper we can go.

Schedule

Lectures

Lectures are scheduled on Tuesdays and Thursdays during October: 13, 15, 20, 22, 27, 29 and November: 3, 5, 10, 12, 17, 19.

Day Time Room Lecturer Dates
Tue 10:15--12 MI 02.04.011 Prof. Rojas Oct. 13, 20, 27, Nov. 3, 17
Thu 10:15--12 MI 02.04.011 Prof. Rojas Oct. 15, 22, 29, Nov. 5, 12, 19

Tutorial Classes

Day Time Room Tutor Dates
Thu 12:30--14 MI 02.04.011 V. Ghiglione Oct. 22, 29, Nov. 5, 12, 19

For participation in the tutorial classes, registration on TUM-Online is mandatory.

Office Hours

Person Day Time Room Not in the office
Prof. Rojas Wed      
V. Ghiglione Wed 14:00-15:00 MI 02.04.36  

Exercise Sheets

Sheet Suggested Solution Topics Hand-in before Comments
Sheet 1 Sol. sheet 1 Euclidean Algorithm, De Moivre's Formula, Roots in Finite fields do not hand-in  
Sheet 2 Sol. sheet 2 Positive and integer roots of polynomials, path-connection, properties of x^A Oct. 26th at 12:00  
Sheet 3,4 Sol. sheet 3   Nov. 2nd, at 12:00 corrected version (Ex1 contained mistakes in Archtrop(f) and strips width)
Sheet 4 Sol. sheet 4   Nov. 9th, at 12:00 Exercises 4,5,6 of Sheet 3,4
Sheet 5   Smith Normal Form, binomial equations on F_q do not hand-it Preparation for the exam. Ex 2(b) changed (F_25 to F_17)

Homeworks and Noten Bonus

  • Every Monday a new sheet is uploaded online.
  • Hand in your solution in groups of 2-3 people by the following Monday at 12, putting it in the mail box in the basement.
  • The homeworks will be returned on Thursday in the Tutorial (and left in a folder in the closet at the beginning of Finger 02.04 afterwards).
  • By the end of the course, those who had at least 70% of the exercises (all together) evaluated with "reasonable attempt" will get a bonus of 0.3 to the exam grade (not passing grades cannot benefit from the bonus).

Notes

  • Notes on On the Separation of Roots of Univariate Polynomials: pdf
  • Notes on The Univariate Discriminant via the Sylvester Resultant: pdf
  • Notes on Hermite Normal Form: pdf
  • Oleg Viro, Dequantization of Real Algebraic Geometry on a Logarithmic Paper: Link to Arxiv 

Suggested Literature

  • E. Bach, J. Shallit: Algorithmic Number Theory, The MIT Press, 1996
  • L. Blum, F. Cucker, M. Shub, S. Smale: Complexity and Real Computation, Springer, 1998

Exam

There will be a written exam with a duration of 60 minutes for this lecture, and a final project. The final grade will be the average of the two grades (the bonus will be added to the final grade, if applicable).

Exam Day Time Room Comments
First Attempt Nov. 12th 10:15--11:15 MI 02.04.011 Registration until Nov. 8th on TUMonline
Second Attempt Nov 27th 10:15--11:15 00.08.059  

The final project will be a presentation on a topic of your choosing, related to algorithmic algebraic geometry and its applications (potential topics will also be provided).

Group projects are fine too, but the groups should be no larger than 3 people, and each student is expected to speak for at least 20 minutes.

The written part of the exam is scheduled for Thursday 12 November 2015, 10:15--11:15, room 02.04.011. Please register on TUM online by November 8th.

You will present your final projects in the last few days of lecture. Your topic should be one of these options:
  • A theorem not covered enough in class
  • A topic/paper related to the lecture
  • Applications of algebraic geometry outside mathematics

your presentation should last ca. 25 minutes, and can be done at the blackboard or with slides.

Projects will be presented on Thursday November 19th at the latest. (Tuesday Nov. 17th is also an option, please contact Prof. Rojas to fix that).

For the repetition exam, projects should be presented on Nov. 27th, time and place to be fixed with Prof. Rojas.

Suggested Topics for the Project:

1. A Wronskian approach to the real tau conjecture, by Pascal Koiran, Natacha Portier, and Sebastian Tavenas, Journal of Symbolic Computation 68 (2015), pp. 195-214. link to ArXiV 

2. A Near-Optimal Algorithm for Computing Real Roots of Sparse Polynomials, by Michael Sagraloff, Math ArXiV preprint 1401.6011 (later published in the proceedings of ISSAC 2014).link to ArXiV 

3. The number of roots of a lacunary bivariate polynomial on a line, by Martin Avendano, Journal of Symbolic Computation 44 (2009), pp.1280-1284. link to ScinceDirect 

4. A sharp bound on the number of real intersection points of a sparse plane curve with a line, by Frederic Bihan and Boulos El Hilany, Math ArXiV preprint 1506.03309. link to ArXiV 

5. Faster Real Feasibility via Circuit Discriminants, (btch?vy Frederic Bihan, J. Maurice Rojas, and Casey Stella), proceedings of ISSAC 2009 (July 28-31, Seoul, Korea), pp. 39-46, ACM Press, 2009. (Freely downloadable as Paper #56 from prof. Rojas' papers page at www.math.tamu.edu/~rojas/list2.html .)

6. Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields, (by Jingguo Bi, Qi Cheng, and J. Maurice Rojas), journal version, submitted for publication. (Freely downloadable as Paper #70 from prof. Rojas' papers page at www.math.tamu.edu/~rojas/list2.html .)

FAQ

question How can I get Maple?
The computer algebra system Maple will be useful for a few exercises. Students have access to Maple in the Rechnerhalle. Is it possible also to make use of the remote access to the Rechnerhalle computers.

question Where can I find a Maple Manual?
Tutorials and explanations can be found at the page http://www.maplesoft.com/support/help/

question Which help is allowed during the exam?
info No help, no books, no lecture notes - it's just you and your pen. If you need extra paper you can get some from the exam supervisors.