Algorithms in Intersection Theory in the Plane

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 the quotient ring of a bivariate zero-dimensional ideal $I\\subseteq \\mathbb K[x,y]$, \\textit{i.e.} finding the points (maximal ideals of $\\mathbb K[x,y]/I$) and describing the regular functions on those points. A natural way to address this problem is via Gr\\"obner bases as they reduce the problem of finding the points to a problem of factorisation, and the sheaf of rings of regular functions can be studied with those bases through the division algorithm and localisation. \nLet $I\\subseteq \\mathbb K[x,y]$ be an ideal generated by $\\mathcal F$, a subset of $\\mathbb A[x,y]$ with $\\mathbb A\\hookrightarrow\\mathbb K$ and $\\mathbb K$ a field. We present an algorithm that features a quadratic convergence to find a Gr\\"obner basis of $I$ or its primary component at the origin. \n \nWe introduce an $\\mathfrak m$-adic Newton iteration to lift the lexicographic Gr\\"obner basis of any finite intersection of zero-dimensional primary components of $I$ if $\\mathfrak m\\subseteq \\mathbb A$ is a \\textit{good} maximal ideal. It relies on a structural result about the syzygies in such a basis due to Conca \\textit{\\&} Valla (2008), from which arises an explicit map between ideals in a stratum (or Gr\\"obner cell) and points in the associated moduli space. We also qualify what makes a maximal ideal $\\mathfrak m$ suitable for our filtration. \n \nWhen the field $\\mathbb K$ is \\textit{large enough}, endowed with an Archimedean or ultrametric valuation, and admits a fraction reconstruction algorithm, we use this result to give a complete $\\mathfrak m$-adic algorithm to recover $\\mathcal G$, the Gr\\"obner basis of $I$. We observe that previous results of Lazard that use Hermite normal forms to compute Gr\\"obner 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 $\\mathcal G$ and to control the probability of choosing a \\textit{good} maximal ideal $\\mathfrak m\\subseteq\\mathbb A$ to build the $\\mathfrak m$-adic expansion of $\\mathcal G$. \nInspired by Pardue (1994), we also give a constructive proof to \ncharacterise a Zariski open set of $\\mathrm{GL}_2(\\mathbb K)$ (with action on $\\mathbb 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 $|\\mathbb K|$ is sufficiently large. This sharpens our analysis \nto obtain, when $\\mathbb A=\\mathbb Z$ or $\\mathbb A=k[t]$, a complexity less than cubic in terms of the dimension of $\\mathbb Q[x,y]/\\langle \\mathcal G\\rangle$ and softly linear in the height of the coefficients of $\\mathcal G$. \n \nWe adapt the resulting method and present the analysis to find the $\\langle x,y\\rangle$-primary component of $I$. We also discuss the transition towards other primary components via linear mappings, called \\emph{untangling} and \\emph{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.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.