The Complexity of Solving Polynomial Equations over Local Fields
Vorlesung
News
 Nov. 16th The inspection will take place on Wednesday 18th November 1315 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 handedin) and Viro's "Dequantization of Real Algebraic Geometry on Logarithmic Paper" have been uploaded. Other notes will be handedin 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
padic 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 numbertheoretic
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, padic numbers, and triangulations of polytopes
would also be helpful, but not critical. The course will be
selfcontained 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:1512 
MI 02.04.011 
Prof. Rojas 
Oct. 13, 20, 27, Nov. 3, 17 
Thu 
10:1512 
MI 02.04.011 
Prof. Rojas 
Oct. 15, 22, 29, Nov. 5, 12, 19 
Tutorial Classes
Day 
Time 
Room 
Tutor 
Dates 
Thu 
12:3014 
MI 02.04.011 
V. Ghiglione 
Oct. 22, 29, Nov. 5, 12, 19 
For participation in the tutorial classes, registration on TUMOnline is mandatory.
Office Hours
Exercise Sheets
Sheet 
Suggested Solution 
Topics 
Handin before 
Comments 
Sheet 1 
Sol. sheet 1 
Euclidean Algorithm, De Moivre's Formula, Roots in Finite fields 
do not handin 

Sheet 2 
Sol. sheet 2 
Positive and integer roots of polynomials, pathconnection, 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 handit 
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 23 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:
 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 ^{}
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:1511:15 
MI 02.04.011 
Registration until Nov. 8th on TUMonline 
Second Attempt 
Nov 27th 
10:1511: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:1511: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. 195214.
link to ArXiV ^{}
2. A NearOptimal 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.12801284.
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
2831, Seoul, Korea), pp. 3946, ACM Press, 2009. (Freely downloadable
as Paper #56 from prof. Rojas' papers page at www.math.tamu.edu/~rojas/list2.html .)
6. SubLinear 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
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.