The Complexity of Solving Polynomial Equations over Local Fields
- 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
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.
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.
Lectures are scheduled on Tuesdays and Thursdays during October: 13, 15, 20, 22, 27, 29 and November: 3, 5, 10, 12, 17, 19.
|| MI 02.04.011
|| Prof. Rojas
|| Oct. 13, 20, 27, Nov. 3, 17
|| MI 02.04.011
|| Prof. Rojas
|| Oct. 15, 22, 29, Nov. 5, 12, 19
|| 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.
|| Suggested Solution
|| Hand-in before
| 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 on On the Separation of Roots of Univariate Polynomials:
- Notes on The Univariate Discriminant via the Sylvester Resultant:
- Notes on Hermite Normal Form:
- Oleg Viro, Dequantization of Real Algebraic Geometry on a Logarithmic Paper: Link to Arxiv
- 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
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).
| First Attempt
|| Nov. 12th
|| MI 02.04.011
|| Registration until Nov. 8th on TUMonline
| Second Attempt
|| Nov 27th
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,
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 .)
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.
Where can I find a Maple Manual?
Tutorials and explanations can be found at the page http://www.maplesoft.com/support/help/
Which help is allowed during the exam?
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.