News and Talks

More

Position

September 2014 — Present
Wissenschaftlicher Mitarbeiter (c.-à-d. enseignant-chercheur associé) in the team of Peter Bürgisser. Logo TU Berlin

TU BerlinFachgebiet Algebra & Zahlentheorie

September 2011 – August 2014
PhD candidate. Logo Inria
Advisors: Bruno Salvy and Alin Bostan.

Inria SaclayÉquipe Specfun

September 2010 – May 2011
Visiting member in Fields Institute, Toronto. Logo Fields Institute

Advisor: Edward Bierstone.

Recent work

The boundary of the orbit of the 3x3 determinant polynomial

December 2015

The 3x3 determinant polynomial

The orbit of a polynomial $P(x_1,\dotsc,x_n)$ is the set of all polynomials obtained from $P$ by invertible linear changes of variables. The boundary of the orbit of $P$ is the set of limit points of the orbit that are not in the orbit itself. For example, the polynomial $y(yz+x^2)$ is in the boundary of the orbit of the polynomial $P(x,y,z) = yz^2 -x^3$ because

In “The boundary of the orbit of the 3 by 3 determinant polynomial”, we describe the boundary of the orbit of the 3x3 determinant polynomial, $\det_3(x_1,\dotsc, x_9)$. It has two irreducible components: the closures of the orbits of the polynomials $\det_3(x_1,\dotsc, x_8, -x_1-x_5)$ and $x_4 \cdot x_1^2 + x_5\cdot x_2^2 + x_6\cdot x_3^2 + x_7\cdot x_1x_2 + x_8\cdot x_2x_3 + x_9\cdot x_1x_3$.

(with Jesko Hüttenhain )

Multiple binomial sums

October 2015

Andrews-Paule identity.

An equality between two binomial sums.

Algorithms to compute discrete sums are well studied since Zeilberger coined the method of creative telescoping. The range of applications of these algorithms is wide, but they are not yet entirely satisfactory: to prove an identity, the help of algorithms is decisive but it is often the case that algorithm cannot conclude alone, without human insight.

In “Multiple binomial sums”, we define a class of discrete sums, called multiple binomial sums, and we describe an efficient algorithm that can prove or disprove that two given such sums are equal. The algorithm relies on the computation of periods of rational integral. From a mathematical point of view, multiple binomial sums have very interesting properties: it turns out that that they are exactly the diagonals of rational functions.

All the algorithms we describe are implemented in the Maple package BinomSums.

(with Alin Bostan and Bruno Salvy )

The Chow variety of quadratic space curves

August 2015

It is well known that lines of the projective space $\mathbb P^3$ — or equivalently, 2-dimensional subspaces of a 4-dimensional vector space — are parametrized by a projective variety of dimension four, the Grassmannian $G(2,4)$. And Plücker coordinates realize this variety as a quadric of $\mathbb P^5$. What about the parametrization curves of degree two in $\mathbb P^3$? Celebrated predecessors — Cayley, van der Waerden, Green, Morrison, Gel’fand, Kapranov, Zelevinsky, etc. — have shown how to realize this parametrization as a 8-dimensional subvariety of $\mathbb P^{19}$: the Chow variety of quadratic space curves.

In “Computing the Chow variety of quadratic space curves”, we performed the computations all the way through to give the explicit equations. For example, we obtain that the two components of the Chow variety of quadratic space curves have degree 140 and 92.

(with Peter Bürgisser, Kathlén Kohn and Bernd Sturmfels )

Smale's 17th problem: A deterministic algorithm to compute approximate roots of polynomial systems

July 2015

Homotopy continuation algorithm

Homotopy continuation algorithm.

For numerically solving polynomial system of equation, the method of homotopy continuation is widely used. They are a lot of questions related to its computational complexity, the first of which is Smale's 17th problem. In a recent breakthrough, Berltrán and Pardo have shown how to achieve a polynomial average complexity with a probabilistic algorithm. The last obstacle that remains concerning Smale's 17th problem is to find a determinitic algorithm. It is precisely what I do in “A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time”. This gives an answer to Smale's 17th problem, in the strongest sense.

Publications

(ordered by date of writing)
  • February 2016 conference paper

    On p-adic differential equations with separation of variables

    by Pierre Lairez and Tristan Vaccon

    ISSAC 2016 (Waterloo, ON, Canada).

    DOI: 10.1145/2930889.2930912

    Abstract. Several algorithms in computer algebra involve the computation of a power series solution of a given ordinary differential equation. Over finite fields, the problem is often lifted in an approximate $p$-adic setting to be well-posed. This raises precision concerns: how much precision do we need on the input to compute the output accurately? In the case of ordinary differential equation with separation of variables, we apply the recent technique of differential precision to obtain optimal bounds on the stability of the Newton iteration. It applies, for example, to algorithms for manipulating algebraic numbers over finite fields, for computing isogenies between elliptic curves or for deterministically finding roots of polynomials in finite fields. The new bounds lead to significant speedups in practice.

    • February 2, 2016 (preprint)
    • March 31, 2016 (accepted)
  • December 2015 preprint

    The boundary of the orbit of the 3 by 3 determinant polynomial

    by Jesko Hüttenhain and Pierre Lairez

    6 pages.

    Abstract. We consider the 3 x 3 determinant polynomial and we describe the limit points of the set of all polynomials obtained from the determinant polynomial by linear change of variables. This answers a question of J. M. Landsberg.

    • December 8, 2015 (preprint)
  • October 2015 journal article

    Multiple binomial sums

    by Alin Bostan, Pierre Lairez and Bruno Salvy

    Journal of symbolic computation (2016), to appear.

    Abstract. Multiple binomial sums form a large class of multi-indexed sequences, closed under partial summation, which contains most of the sequences obtained by multiple summation of products of binomial coefficients and also all the sequences with algebraic generating function. We study the representation of the generating functions of binomial sums by integrals of rational functions. The outcome is twofold. Firstly, we show that a univariate sequence is a multiple binomial sum if and only if its generating function is the diagonal of a rational function. Secondly, we propose algorithms that decide the equality of multiple binomial sums and that compute recurrence relations for them. In conjunction with geometric simplifications of the integral representations, this approach behaves well in practice. The process avoids the computation of certificates and the problem of the appearance of spurious singularities that afflicts discrete creative telescoping, both in theory and in practice.

    • October 26, 2015 (preprint)
    • April 3, 2016 (accepted)
    • June 15, 2016 (revised)
  • August 2015 conference paper

    Computing the Chow variety of quadratic space curves

    by Peter Bürgisser, Kathlén Kohn, Pierre Lairez and Bernd Sturmfels

    Mathematical Aspects of Computer and Information Sciences (MACIS 2015), Lecture Notes in Computer Science 9582, pp. 130-136.

    DOI: 10.1007/978-3-319-32859-1_10

    Abstract. Quadrics in the Grassmannian of lines in 3-space form a 19-dimensional projective space. We study the subvariety of coisotropic hypersurfaces. Following Gel’fand, Kapranov and Zelevinsky, it decomposes into Chow forms of plane conics, Chow forms of pairs of lines, and Hurwitz forms of quadric surfaces. We compute the ideals of these loci.

    • August 29, 2015 (preprint)
    • November 27, 2015 (revision)
  • July 2015 journal article

    A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time

    by Pierre Lairez

    Foundations of computational mathematics (2016), to appear.

    DOI: 10.1007/s10208-016-9319-7

    Abstract. We describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum-Shub-Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale’s 17th problem. The main idea is to make use of the randomness contained in the input itself.

    • July 20, 2015 (preprint)
    • October 7, 2015 (revision)
    • March 14, 2016 (revision)
    • March 15, 2016 (accepted)
    • May 18, 2016 (published online)
  • November 2014 thesis

    Périodes d’intégrales rationnelles : algorithmes et applications

    by Pierre Lairez

    Thèse de doctorat, prix de thèse de l’École polytechnique.

    Jury de thèse :

    Abstract. A period of rational integral is the result of integrating, with respect to one or several variables, a rational function along a closed path. When the period under consideration depends on a parameter, it satisfies a specific linear differential equation called Picard-Fuchs equation. These equations and their computation are important for computer algebra, but also for algebraic geometry (they contains geometric invariants), in combinatorics (many generating functions are periods) or in theoretical physics. This thesis offers and studies algorithms to compute them.

    The first chapter shows bounds on the size of Picard-Fuchs equations and on the complexity of their computation. Existing algorithms for computing these equations often produce, in the same time, certificates, typically huge, which allows to check afterwards the correctness of the equation. The bounds I obtained enlighten the computational nature of Picard-Fuchs equations, they show in particular that the certificates are not a required byproduct. The proof relies on the study of the generic case and the reduction of pole order with Griffiths-Dwork method.

    The second chapter offers an algorithms for computing Picard-Fuchs equations more efficiently. It allows for the resolution of many previously unsolved problems. It relies on a method for reducing the pole order which extends Griffiths-Dwork reduction to the singulars cases.

    The third chapter draws a rigorous correspondence between periods of rational integrals and generating functions of multiple binomial sums. Together with the computation of Picard-Fuchs equations, it allows automatically proving identities about binomial sums.

    • November 12, 2014 (defense)
  • April 2014 journal article

    Computing periods of rational integrals

    by Pierre Lairez

    Mathematics of computation 85 (2016), pp. 1719-1752.

    Supplementary material

    DOI: 10.1090/mcom/3054

    Abstract. A period of a rational integral is the result of integrating, with respect to one or several variables, a rational function over a closed path. This work focuses particularly on periods depending on a parameter: in this case the period under consideration satisfies a linear differential equation, the Picard-Fuchs equation. I give a reduction algorithm that extends the Griffiths-Dwork reduction and apply it to the computation of Picard-Fuchs equations. The resulting algorithm is elementary and has been successfully applied to problems that were previously out of reach.

    • April 20, 2014 (preprint)
    • January 31, 2015 (revision)
    • March 13, 2015 (accepted)
    • November 6, 2015 (published electronically)
  • January 2013 conference paper

    Creative telescoping for rational functions using the Griffiths-Dwork method

    by Alin Bostan, Pierre Lairez and Bruno Salvy

    Proceedings of ISSAC 2013 (Boston, USA). distinguished student author award

    DOI: 10.1145/2465506.2465935

    Abstract. Creative telescoping algorithms compute linear differential equations satisfied by multiple integrals with parameters. We describe a precise and elementary algorithmic version of the Griffiths-Dwork method for the creative telescoping of rational functions. This leads to bounds on the order and degree of the coefficients of the differential equation, and to the first complexity result which is simply exponential in the number of variables. One of the important features of the algorithm is that it does not need to compute certificates. The approach is vindicated by a prototype implementation.

    • January 18, 2013 (preprint)
    • April 21, 2013 (revision)
    • March 22, 2013 (accepted)
    • June 6, 2013 (print)
  • July 2011 journal article

    Resolution except for minimal singularities II. The case of four variables

    by Edward Bierstone, Pierre Lairez and Pierre Milman

    Advances in Mathematics, 2012, vol. 231, no. 5, pp. 3003–3021.

    DOI: 10.1016/j.aim.2012.08.001

    Abstract. In this sequel to “Resolution except for minimal singularities I”, we find the smallest class of singularities in four variables with which we necessarily end up if we resolve singularities except for normal crossings. The main new feature is a characterization of singularities in four variables which occur as limits of triple normal crossings singularities, and which cannot be eliminated by a birational morphism that avoids blowing up normal crossings singularities.

    • July 27, 2011 (preprint)
    • August 1, 2012 (accepted)
    • December 1, 2012 (print)

Software

BinomSums

2015

BinomSums is a package for the computer algebra system Maple that provides functions to handle multiple binomial sums through integral representations. It implements the algorithms described in “Multiple binomial sums”.

GitHub repo

Periods

2014

Periods is a package for the computer algebra system Magma that provides functions to compute periods of rational integrals. It implements the algorithm described in “Computing periods of rational integrals”. Several computational premières have been performed with it and it has been critical in augmenting and the database of Calabi-Yau operators. It is also capable of integrating the integral representations that the package BinomSums outputs.

GitHub repo