Welcome to the Weekly Seminars on Algorithms in Algebraic Geometry, which took place every Mondays 14:00-15:30 CET of the first semester of 2024, at KU Leuven at KU Leuven campus Arenberg 3, in the seminar room B02.18 (full name 200B.02.018; second floor of the Math building 200B).
Organizers: Rémi Prébet and Erdenebayar Bayarmagnai
Registration:
Please email Rémi if you are interested in attending the meeting or have any questions.
Overview:
The main goal of this reading seminar is to get familiar with some algorithmic aspects of both classic and real algebraic geometry. The program will be divided in two parts. We will first survey various techniques on complex algebraic varieties, before switching to their real counterpart. These will be introduced and illustrated with several examples, using both hands and computer algebra softwares.
Schedule:
February 19, 2024 - B02.18: Rémi Prébet
Introduction and overview: After recalling some basic notions both from complex and real algebraic geometry, I will present and use some classic algorithmic tools to perform basic operations on algebraic varieties and solve geometric problems both from pure and applied side.
February 26, 2024 - B02.18: Erdenebayar Bayarmagnai
Introduction to Gröbner bases: In this talk, I will talk about monomial orderings, a division algorithm and Gröbner bases, and explain how Gröbner bases solve the ideal membership problem.
March 4, 2024 - B02.18: Ngoc-Anh Nguyen
Applications of Gröbner bases: I will discuss some of the applications of Gröbner basis, particularly for consistency problems, radical membership testings, and some geometric operations of algebraic sets (with the help of elimination theorem).
March 11, 2024 - B02.18: Sebastian Seemann
Dimension of Varieties: In this talk we will discuss dimension of Varieties and give a fully algebraic and implementable definition. We start by studying monomial Ideals and their complements and finish with a study of affine Hilbert functions. Then we will see how Gröbner basis theory allows us to apply Hilberts results for monomial Ideals to arbitrary Ideals.
March 18, 2024 - S.01.05: Giacomo Masiero
The F4 algorithm: The F4 algorithms are a family of algorithms which improve in efficiency the classical Buchberger’s method to compute Gröbner bases for polynomial ideals. In the first part, we will investigate their underlying philosophy, which is inspired by homogeneous Gröbner bases and linear algebra. In the second part, we will highlight how these reflect in the pseudocode of the F4 algorithms.
March 25, 2024 - B.00.05: Cas Proost
The Groebner fan and computational tropical geometry: In this talk, I will define tropical varieties from the viewpoint of Gröbner theory and polyhedral geometry, starting from the Gröbner fan.
April 15, 2024 - B01.18: Emiliano Liwski
Quantifier Elimination Over Algebraically Closed Fields: In this talk I will give the definition of constructible sets and I will prove that, in the context of algebraically closed fields, the projection of a constructible set is constructible.
April 22, 2024 - B02.18: Erdenebayar Bayarmagnai
Real root counting: I will talk about two main results of counting real roots of univariate polynomials with real coefficients. The first result is Budan-Fourier theorem which gives an upper bound for the number of real roots counted with multiplicities in (a,b). The second result is Sturm's theorem which exactly counts the number of real roots without multiplicities in (a,b).
April 29, 2024 - B02.14 (15:30-17:00) : Rémi Prébet
Quantifier Elimination over real numbers: After some reminders of the previous sessions, we will define quantifier elimination when dealing with real numbers by analogy with the algebraically closed case we saw previously. Following the analogy, this will lead us to define a new class of sets, namely semi-algebraic sets, and which is stable by projection. The proof of the latter will be at the core of the presentation, and will heavily rely on the techniques introduced in the two previous talks.
May 6, 2024 - B02.18: Ngoc-Anh Nguyen
Cylindrical Algebraic Decomposition (CAD) and subresultant sequences: In talk, I will introduce the cylindrical algebraic decompositions and give illustrative examples to get familiar with it, before stating the associated main theorem. We will then define subresultant sequences, a powerful tool that is at the core of CAD.
May 13, 2024 - B02.18: Emiliano Liwski
The Decomposition Theorem and Applications: In this talk, I will explain why the cylindrical decomposition adapted to a semi algebraic set always exists, and I will give some consequences of this fact.
May 27, 2024 - B02.18: Giacomo Masiero
Efficiently computing Remainder and Subresultant sequences : The computation of signed remainder sequences (SRS) is of crucial significance in real algebraic geometry. However, the coefficients of the polynomials in such sequences can increase exponentially from the input, causing naturally storage problems. We introduce a strategy to predict the bitsizes of the coefficients of the polynomials in the SRS. This is done through the theory of subresultant polynomials, which are related to the SRS by proportionality.
June 3, 2024 - B02.18: Zirui Yan
The addition laws of elliptic curves over rings: In this talk, we will talk about the relation between elliptic curves over fields and over rings, and a way to compute the addition of two points at infinity.
June 11, 2024 - B02.18: Sebastian Seemann
The Cylindrical Algebraic Decomposition Algorithm : In this talk, we will see Cylindrical Decomposition (CAD) formulated as an algorithm. We will talk about how the CAD algorithm can be used for various applications, most importantly algorithmic quantifier elimination. To do this we will review and introduce many notions such as elimination sets, CAD adapted to a set of polynomials and cylindrical realizable sign conditions.
Books:
Ideals, Varieties and Algorithms by David A.Cox, John Little and Donal O'Shea
Algorithms in Real Algebraic Geometry by Saugata Basu, Richard Pollack, and Marie-Françoise Roy