PhD Defence • Computer Algebra • Algorithms in Intersection Theory in the Plane

Please note: This PhD defence will take place in MC 5417 and virtually.

Catherine St-Pierre, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Éric Schost

This thesis presents an algorithm to find the local structure of intersections of plane curves.

More precisely, we address the question of describing the scheme of a bivariate zero-dimensional ideal I ⊆ R (ideals of Spec R/I + regular functions and their localisation). A natural way to address this problem is to find a Gröbner basis of an ideal or its primary components. Let I ⊆ K[x,y] be an ideal generated by a subset of A[x,y] with A a domain contained in a field K. We present an algorithm that features a quadratic convergence to find a Gröbner basis of I or its primary component at the origin.

We introduce an m-adic Newton iteration to lift the lexicographic Gröbner of any finite intersection of zero-dimensional primary components of I if m ⊆ A a good maximal ideal. It relies on a structural result about the syzygies in such a basis due to Conca & Valla, from which arises an explicit map between ideals in a stratum (or Gröbner cell) and points in the associated moduli space. We also qualify what makes a maximal ideal m suitable for our filtration.

When the field K is large enough, endowed with an Archimedean or ultrametric valuation, and admits a fraction reconstruction algorithm, we use this result to give a complete m-adic algorithm to recover G, the Gröbner basis of I. We observe that previous results of Lazard that use Hermite normal forms to compute Gröbner bases for ideals with two generators can be generalised to a set of n generators. We use this result to obtain a bound on the height of the coefficients of G and to control the probability of choosing a good maximal ideal m ⊆ A to build the m-adic expansion of G. Inspired by Pardue (1994), we also give a constructive proof to characterise a Zariski open set of GL2(K) (with action on K[x,y]) that changes coordinates in such a way as to ensure the initial term ideal of a zero-dimensional I becomes Borel-fixed when |K| is sufficiently large. This sharpens our analysis to obtain, when A = Z or A = k[t], a complexity cubic in terms the dimension of Q[x,y]/(G) and softly linear in the height of the coefficients of G.

We adapt the resulting method and present the analysis to find a (x, y)-primary component of I.

We discuss the transition toward other primary components via linear mappings, called untangling and tangling, introduced by van der Hoeven and Lecerf (2017). The two maps form one isomorphism to find points with an isomorphic local structure and, at the origin, bind them. We give a slightly faster tangling algorithm and discuss new applications of these techniques. We show how to extend these ideas to bivariate settings and give a bound on the arithmetic complexity for certain algebras.

To attend this PhD seminar in person, please go to MC 5417. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/94825932784.