
P. Giorgi, B. Grenet, A. Perret du Cray.
J. Symb. Comput., 2021.
Accepted for publication.
Polynomial multiplication is known to have quasilinear complexity in both the dense and the sparse cases. Yet no truly linear algorithm has been given in any case for the problem, and it is not clear whether it is even possible. This leaves room for a better algorithm for the simpler problem of verifying a polynomial product. While finding deterministic methods seems out of reach, there exist probabilistic algorithms for the problem that are optimal in number of algebraic operations.
We study the generalization of the problem to the verification of a polynomial product modulo a sparse divisor. We investigate its bit complexity for both dense and sparse multiplicands. In particular, we are able to show the primacy of the verification over modular multiplication when the divisor has a constant sparsity and a second highestdegree monomial that is not too large. We use these results to obtain new bounds on the bit complexity of the standard polynomial multiplication verification. In particular, we provide optimal algorithms in the bit complexity model in the dense case by improving a result of Kaminski and develop the first quasioptimal algorithm for verifying sparse polynomial product.
@article{GGPdC21j,
title = {{Polynomial modular product verification and its implications}},
author = {Giorgi, Pascal and Grenet, Bruno and Perret du Cray, Armelle},
year = 2021,
journal = {J. Symb. Comput.},
volume = ISSAC'20 special issue,
pages = {to appear},
arxiv = {2101.02142},
hal = {hal03102121},
note = {Accepted for publication.},
}

P. Giorgi, B. Grenet, A. Perret du Cray.
No polynomialtime algorithm is known to test whether a sparse polynomial G divides another sparse polynomial F. While computing the quotient Q=F quo G can be done in polynomial time with respect to the sparsities of F, G and Q, this is not yet sufficient to get a polynomialtime divisibility test in general. Indeed, the sparsity of the quotient Q can be exponentially larger than the ones of F and G. In the favorable case where the sparsity #Q of the quotient is polynomial, the best known algorithm to compute Q has a nonlinear factor #G#Q in the complexity, which is not optimal.
In this work, we are interested in the two aspects of this problem. First, we propose a new randomized algorithm that computes the quotient of two sparse polynomials when the division is exact. Its complexity is quasilinear in the sparsities of F, G and Q. Our approach relies on sparse interpolation and it works over any finite field or the ring of integers. Then, as a step toward faster divisibility testing, we provide a new polynomialtime algorithm when the divisor has a specific shape. More precisely, we reduce the problem to finding a polynomial S such that QS is sparse and testing divisibility by S can be done in polynomial time. We identify some structure patterns in the divisor G for which we can efficiently compute such a polynomial S.
@inProceedings{GGPdC21,
title = {{On exact division and divisibility testing for sparse polynomials}},
author = {Giorgi, Pascal and Grenet, Bruno and Perret du Cray, Armelle},
year = 2021,
booktitle = {Proceedings of ISSAC},
pages = {to appear},
doi = {10.1145/3452143.3465539},
publisher = {ACM},
arxiv = {2102.04826},
hal = {hal03136945},
}

A. Chattopadhyay, B. Grenet, P. Koiran, N. Portier, Y. Strozecki.
Implementation in the package
Lacunaryx of Mathemagix.
We present a deterministic polynomialtime algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. It is based on a new Gap theorem which allows to test whether $P(X)=\sum_{j=1}^k a_j X^{\alpha_j}(vX+t)^{\beta_j}(uX+w)^{\gamma_j}$ is identically zero in polynomial time. Previous algorithms for this task were based on Gap Theorems expressed in terms of the height of the coefficients. Our Gap Theorem is based on the valuation of the polynomial and is valid for any field of characteristic zero. As a consequence we obtain a faster and more elementary algorithm. Furthermore, we can partially extend the algorithm to other situations, such as absolute and approximate factorizations.
We also give a version of our Gap Theorem valid for fields of large characteristic, and deduce a randomized polynomialtime algorithm to compute multilinear factors with at least three monomials of multivariate lacunary polynomials of finite fields of large characteristic. We provide NPhardness results to explain our inability to compute binomial factors.
@article{CGKPS21,
title = {{Computing the multilinear factors of lacunary polynomials without heights}},
author = {Chattopadhyay, Arkadev and Grenet, Bruno and Koiran, Pascal and Portier, Natacha and Strozecki, Yann},
year = 2021,
journal = {J. Symb. Comput.},
volume = 104,
pages = {183206},
doi = {10.1016/j.jsc.2020.04.013},
arxiv = {1311.5694},
hal = {hal00936318},
}

P. Giorgi, B. Grenet, A. Perret du Cray.
We present a probabilistic algorithm to compute the product of two univariate sparse polynomials over a field with a number of bit operations that is quasilinear in the size of the input and the output. Our algorithm works for any field of characteristic zero or larger than the degree. We mainly rely on sparse interpolation and on a new algorithm for verifying a sparse product that has also a quasilinear time complexity. Using Kronecker substitution techniques we extend our result to the multivariate case.
@inProceedings{GGPdC20,
title = {{Essentially optimal sparse polynomial multiplication}},
author = {Giorgi, Pascal and Grenet, Bruno and Perret du Cray, Armelle},
year = 2020,
booktitle = {Proceedings of ISSAC},
pages = {202209},
doi = {10.1145/3373207.3404026},
publisher = {ACM},
arxiv = {2001.11959},
hal = {hal02476609},
}

P. Giorgi, B. Grenet, D. S. Roche.
We consider spacesaving versions of several important operations on univariate polynomials, namely power series inversion and division, division with remainder, multipoint evaluation, and interpolation. Nowclassical results show that such problems can be solved in (nearly) the same asymptotic time as fast polynomial multiplication. However, these reductions, even when applied to an inplace variant of fast polynomial multiplication, yield algorithms which require at least a linear amount of extra space for intermediate results. We demonstrate new inplace algorithms for the aforementioned polynomial computations which require only constant extra space and achieve the same asymptotic running time as their outofplace counterparts. We also provide a precise complexity analysis so that all constants are made explicit, parameterized by the space usage of the underlying multiplication algorithms.
@inProceedings{GGR20,
title = {{Fast inplace algorithms for polynomial operations: division, evaluation, interpolation}},
author = {Giorgi, Pascal and Grenet, Bruno and Roche, Daniel S.},
year = 2020,
booktitle = {Proceedings of ISSAC},
pages = {210217},
doi = {10.1145/3373207.3404061},
publisher = {ACM},
arxiv = {2002.10304},
hal = {lirmm02493066},
}

We give a new simple and short ("oneline") analysis for the runtime of the wellknown Euclidean Algorithm. While very short simple, the obtained upper bound in optimal.
@inProceedings{GV20,
title = {{One (more) line on the most Ancient Algorithm in History}},
author = {Grenet, Bruno and Volkovich, Ilya},
year = 2020,
booktitle = {Proceedings of SOSA},
pages = {1517},
doi = {10.1137/1.9781611976014.3},
publisher = {SIAM},
arxiv = {1808.07957},
hal = {lirmm02335368},
}

P. Giorgi, B. Grenet, D. S. Roche.
The polynomial multiplication problem has attracted considerable attention since the early days of computer algebra, and several algorithms have been designed to achieve the best possible time complexity. More recently, efforts have been made to improve the space complexity, developing modified versions of a few specific algorithms to use no extra space while keeping the same asymptotic running time.
In this work, we broaden the scope in two regards. First, we ask whether an arbitrary multiplication algorithm can be performed inplace generically. Second, we consider two important variants which produce only part of the result (and hence have less space to work with), the socalled middle and short products, and ask whether these operations can also be performed inplace.
To answer both questions in (mostly) the affirmative, we provide a series of reductions starting with any linearspace multiplication algorithm. For full and short product algorithms these reductions yield inplace versions with the same asymptotic time complexity as the outofplace version. For the middle product, the reduction incurs an extra logarithmic factor in the time complexity only when the algorithm is quasilinear.
@inProceedings{GGR19,
title = {{Generic reductions for inplace polynomial multiplication}},
author = {Giorgi, Pascal and Grenet, Bruno and Roche, Daniel S.},
year = 2019,
booktitle = {Proceedings of ISSAC},
pages = {187194},
doi = {10.1145/3326229.3326249},
publisher = {ACM},
arxiv = {1902.02967},
hal = {lirmm02003089},
}

B. Grenet, J. van der Hoeven, G. Lecerf.
Appl. Alg. Eng. Comm. Comput., 2016.
See also our
related paper for randomized algorithms and fast implementations.
We design new deterministic algorithms, based on Graeffe transforms, to compute all the roots of a polynomial which splits over a finite field $\mathbb{F}_q$ . Our algorithms were designed to be particularly efficient in the case when the cardinality $q1$ of the multiplicative group of $\mathbb{F}_q$ is smooth. Such fields are often used in practice because they support fast discrete Fourier transforms. We also present a new nearly optimal algorithm for computing characteristic polynomials of multiplication endomorphisms in finite field extensions. This algorithm allows for the efficient computation of Graeffe transforms of arbitrary orders.
@article{GHL16,
title = {{Deterministic root finding over finite fields using Graeffe transforms}},
author = {Grenet, Bruno and van der Hoeven, Joris and Lecerf, Grégoire},
year = 2016,
journal = {Appl. Alg. Eng. Comm. Comput.},
volume = 27,
number = 3,
pages = {237{}257},
doi = {10.1007/s0020001502805},
hal = {hal01104251},
}

B. Grenet.
J. Symb. Comput., 2016.
ISSAC 2014 special issue
In this paper, we present a new method for computing boundeddegree factors of lacunary multivariate polynomials. In particular for polynomials over number fields, we give a new algorithm that takes as input a multivariate polynomial $f$ in lacunary representation and a degree bound $d$ and computes the irreducible factors of degree at most $d$ of $f$ in time polynomial in the lacunary size of $f$ and in $d$. Our algorithm consists in a reduction of the problem to the univariate case on the one hand and to the irreducible factorization of multivariate lowdegree polynomials on the other hand, which is valid for any field of zero characteristic.
The reduction algorithms we propose are elementary in that they only manipulate the exponent vectors of the input polynomial. The proof of correctness and the complexity bounds rely on the valuations of certain formal power series with rational exponents, called Puiseux series, and on considerations on the Newton polytope of the polynomial.
@article{Gre16,
title = {{Boundeddegree factors of lacunary multivariate polynomials}},
author = {Grenet, Bruno},
year = 2016,
journal = {J. Symb. Comput.},
volume = 75,
pages = {171{}192},
doi = {10.1016/j.jsc.2015.11.013},
arxiv = {1412.3570},
note = {ISSAC 2014 special issue},
}

B. Grenet.
ACM Comm. Comput. Algebra, 2015.
ISSAC 2015 Software Presentation
In this paper, we report on an implementation in the free software Mathemagix of lacunary factorization algorithms, distributed as a library called
Lacunaryx.
@article{Gre15,
title = {{Lacunaryx: Computing boundeddegree factors of lacunary polynomials}},
author = {Grenet, Bruno},
year = 2015,
journal = {ACM Comm. Comput. Algebra},
volume = 49,
number = 4,
pages = {121{}124},
doi = {10.1145/2893803.2893807},
arxiv = {1506.03726},
note = {ISSAC 2015 Software Presentation},
}

B. Grenet, J. van der Hoeven, G. Lecerf.
Consider a finite field $\mathbb{F}_q$ whose multiplicative group has smooth cardinality. We study the problem of computing all roots of a polynomial that splits over $\mathbb{F}_q$, which was one of the bottlenecks for fast sparse interpolation in practice. We revisit and slightly improve existing algorithms and then present new randomized ones based on the Graeffe transform. We report on our implementation in the Mathemagix computer algebra system, confirming that our ideas gain by an order of magnitude in practice.
@inProceedings{GHL15,
title = {{Randomized Root Finding over Finite FFTfields Using Tangent Graeffe Transforms}},
author = {Grenet, Bruno and van der Hoeven, Joris and Lecerf, Grégoire},
year = 2015,
booktitle = {Proceedings of ISSAC},
pages = {197204},
doi = {10.1145/2755996.2756647},
publisher = {ACM},
hal = {hal01104279},
}

We present a new algorithm for the computation of the irreducible factors of degree at most d, with multiplicity, of multivariate lacunary polynomials over fields of characteristic zero. The algorithm reduces this computation to the computation of irreducible factors of degree at most $d$ of univariate lacunary polynomials and to the factorization of lowdegree multivariate polynomials. The reduction runs in time polynomial in the size of the input polynomial and in $d$. As a result, we obtain a new polynomialtime algorithm for the computation of lowdegree factors, with multiplicity, of multivariate lacunary polynomials over number fields, but our method also gives partial results for other fields, such as the fields of $p$adic numbers or for absolute or approximate factorization for instance.
The core of our reduction uses the Newton polygon of the input polynomial, and its validity is based on the NewtonPuiseux expansion of roots of bivariate polynomials. In particular, we bound the valuation of $f(X,\phi)$ where $f$ is a lacunary polynomial and $\phi$ a Puiseux series whose vanishing polynomial has low degree.
@inProceedings{Gre14,
title = {{Computing lowdegree factors of lacunary polynomials: a NewtonPuiseux approach}},
author = {Grenet, Bruno},
year = 2014,
booktitle = {Proceedings of ISSAC},
pages = {224{}231},
doi = {10.1145/2608628.2608649},
publisher = {ACM},
arxiv = {1401.4720},
}

A. Chattopadhyay, B. Grenet, P. Koiran, N. Portier, Y. Strozecki.
The lacunary, or supersparse, representation of a multivariate polynomial $P$ is a list of pairs $(c,e)$ where $c$ is a coefficient of $P$ and $e$ is a vector of exponent. Each pair defines a term of the polynomial, and $P$ equals the sum of all these terms. The factorization of lacunary polynomial has been investigated in a series of papers by Cucker, Koiran and Smale (J. Symb. Comput., 1999), Lenstra (Number Theory in Progress, 1999), and Kaltofen and Koiran (ISSAC 2005 & 2006). In this paper, we are interested in more elementary proofs for some of these results. We focus on Kaltofen and Koiran’s results dealing with linear factors of bivariate lacunary polynomials. In particular, we give a polynomialtime algorithm to find linear factors of bivariate polynomials that is not based on heights of algebraic numbers. This simplification allows us to give a similar result for some fields of positive characteristic. Our main technical result is an upper bound on the valuation of polynomials of the form $P(X,1+X)$ where $P$ is a bivariate lacunary polynomial, and can be viewed as a generalization of a result of Hajós.
@inProceedings{CGKPS13,
title = {{Factoring bivariate lacunary polynomials without heights}},
author = {Chattopadhyay, Arkadev and Grenet, Bruno and Koiran, Pascal and Portier, Natacha and Strozecki, Yann},
year = 2013,
booktitle = {Proceedings of ISSAC},
pages = {141{}158},
doi = {10.1145/2465506.2465932},
publisher = {ACM},
arxiv = {1206.4224},
}

B. Grenet, P. Koiran, N. Portier.
The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of $n$ homogeneous equations in $n$ variables is satisfiable (the resultant is a polynomial in the system's coefficients which vanishes if and only if the system is satisfiable). In this paper, we investigate the complexity of computing the multivariate resultant.
First, we study the complexity of testing the multivariate resultant for zero. Our main result is that this problem is NPhard under deterministic reductions in any characteristic, for systems of lowdegree polynomials with coefficients in the ground field (rather than in an extension). In characteristic zero, we observe that this problem is in the ArthurMerlin class AM if the generalized Riemann hypothesis holds true, while the best known upper bound in positive characteristic remains PSPACE.
Second, we study the classical algorithms to compute the resultant. They usually rely on the computation of the determinant of an exponentialsize matrix, known as Macaulay matrix. We show that this matrix belongs to a class of succinctly representable matrices, for which testing the determinant for zero is proved PSPACEcomplete. This means that improving Canny's PSPACE upper bound requires either to look at the fine structure of the Macaulay matrix to find an ad hoc algorithm for computing its determinant, or to use altogether different techniques.
@article{GKP13,
title = {{On the complexity of the multivariate resultant}},
author = {Grenet, Bruno and Koiran, Pascal and Portier, Natacha},
year = 2013,
journal = {J. Complexity},
volume = 29,
number = 2,
pages = {142{}157},
doi = {10.1016/j.jco.2012.10.001},
arxiv = {1210.1451},
}

B. Grenet, Th. Monteil, S. Thomassé.
This paper studies Symmetric Determinantal Representations (SDR) in characteristic 2, that is the representation of a polynomial $P$ by a symmetric matrix $M$ such that $P=\det M$, and where each entry of $M$ is either a constant or a variable.
We first give a necessary condition for a polynomial to have an SDR. It implies that some polynomials have n SDR, answering a question of Grenet et al.
A large part of the paper is then devoted to the case of multilinear polynomials. We prove that the existence of an SDR for a multilinear polynomial is equivalent to the existence of a factorization of the polynomial in certain quotient rings. We develop some algorithms to test the factorizability in these rings and use them to find SDRs when they exist. Altogether, this gives us polynomialtime algorithms to factorize the polynomials in the quotient rings and to build SDRs.
@article{GMT13,
title = {{Symmetric determinantal representations in characteristic{~}2}},
author = {Grenet, Bruno and Monteil, Thierry and Thomassé, Stéphan},
year = 2013,
journal = {Linear Alg. Appl.},
volume = 439,
number = 5,
pages = {1364{}1381},
doi = {10.1016/j.laa.2013.04.022},
arxiv = {1210.5879},
}

B. Grenet, P. Koiran, N. Portier, Y. Strozecki.
Polynomial identity testing and arithmetic circuit lower bounds are two central questions in algebraic complexity theory. It is an intriguing fact that these questions are actually related. One of the authors of the present paper has recently proposed a "real τconjecture" which is inspired by this connection. The real τconjecture states that the number of real roots of a sum of products of sparse univariate polynomials should be polynomially bounded. It implies a superpolynomial lower bound on the size of arithmetic circuits computing the permanent polynomial.
In this paper we show that the real τconjecture holds true for a restricted class of sums of products of sparse polynomials. This result yields lower bounds for a restricted class of depth4 circuits: we show that polynomial size circuits from this class cannot compute the permanent, and we also give a deterministic polynomial identity testing algorithm for the same class of circuits.
@inProceedings{GKPS11,
title = {{The Limited Power of Powering: Polynomial Identity Testing and a Depthfour Lower Bound for the Permanent}},
author = {Grenet, Bruno and Koiran, Pascal and Portier, Natacha and Strozecki, Yann},
year = 2011,
booktitle = {Proceedings of FSTTCS},
number = 13,
pages = {127{}139},
doi = {10.4230/LIPIcs.FSTTCS.2011.127},
series = {LIPIcs},
publisher = {Dagstuhl},
arxiv = {1107.1434},
}

B. Grenet, E. L. Kaltofen, P. Koiran, N. Portier.
We deploy algebraic complexity theoretic techniques for constructing symmetric determinantal representations of weaklyskew circuits, which include formulas. Our representations produce matrices of much smaller dimensions than those given in the convex geometry literature when applied to polynomials having a concise representation (as a sum of monomials, or more generally as an arithmetic formula or a weaklyskew circuit). These representations are valid in any field of characteristic different from 2. In characteristic 2 we are led to an almost complete solution to a question of Bürgisser on the VNPcompleteness of the partial permanent. In particular, we show that the partial permanent cannot be VNPcomplete in a finite field of characteristic 2 unless the polynomial hierarchy collapses.
@inProceedings{GKKP11c,
title = {{Symmetric Determinantal Representation of WeaklySkew Circuits}},
author = {Grenet, Bruno and Kaltofen, Erich L. and Koiran, Pascal and Portier, Natacha},
year = 2011,
booktitle = {Proceedings of STACS},
number = 9,
pages = {543{}554},
doi = {10.4230/LIPIcs.STACS.2011.543},
series = {LIPIcs},
publisher = {Dagstuhl},
hal = {hal00573631},
}

B. Grenet, E. L. Kaltofen, P. Koiran, N. Portier.
See also Chapters 3 & 4 of my
PhD Thesis for simplified proofs of these results.
We deploy algebraic complexity theoretic techniques to construct symmetric determinantal representations of formulas and weakly skew circuits. Our representations produce matrices of much smaller dimensions than those given in the convex geometry literature when applied to polynomials having a concise representation (as a sum of monomials, or more generally as an arithmetic formula or a weakly skew circuit). These representations are valid in any field of characteristic different from 2. In characteristic 2 we are led to an almost complete solution to a question of Bürgisser on the VNPcompleteness of the partial permanent. In particular, we show that the partial permanent cannot be VNPcomplete in a finite field of characteristic 2 unless the polynomial hierarchy collapses.
@inCollection{GKKP11j,
title = {{Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits}},
author = {Grenet, Bruno and Kaltofen, Erich L. and Koiran, Pascal and Portier, Natacha},
year = 2011,
booktitle = {Randomization, Relaxation, and Complexity in Polynomial Equation Solving},
number = 556,
pages = {61{}96},
doi = {10.1090/conm/556},
isbn = {9780821852286},
editor = {Leonid Gurvits and Philippe P{\'e}bay and J. Maurice Rojas and David C. Thompson},
series = {Contemporary Mathematics},
publisher = {AMS},
arxiv = {1001.3804},
}

B. Grenet.
Manuscript, 2011.
The Permanent versus Determinant problem is the following: Given an $n\times n$ matrix $X$ of indeterminates over a field of characteristic different from two, find the smallest matrix $M$ whose coefficients are linear functions in the indeterminates such that the permanent of $X$ equals the determinant of $M$. We prove that the dimensions of $M$ are at most $2^n1$.
@misc{Gre11,
title = {{An Upper Bound for the Permanent versus Determinant Problem}},
author = {Grenet, Bruno},
year = 2011,
howpublished = {Manuscript},
}

In 1930, Gödel presented in Königsberg his famous Incompleteness Theorem, stating that some true mathematical statements are unprovable. Yet, this result gives us no idea about those independent (that is, true and unprovable) statements, about their frequency, the reason they are unprovable, and so on. Calude and Jürgensen proved in 2005 Chaitin's "heuristic principle" for an appropriate measure: the theorems of a finitelyspecified theory cannot be significantly more complex than the theory itself. In this work, we investigate the existence of other measures, different from the original one, which satisfy this "heuristic principle". At this end, we introduce the definition of acceptable complexity measure of theorems.
@article{Gre10,
title = {{Acceptable Complexity Measures of Theorems}},
author = {Grenet, Bruno},
year = 2010,
journal = {Compl. Syst.},
volume = 18,
number = 4,
pages = {403{}425},
arxiv = {0910.0045},
url = {http://www.complexsystems.com/abstracts/v18_i04_a02.html},
}

B. Grenet, P. Koiran, N. Portier.
The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of $n$ homogeneous equations in $n$ variables is satisfiable (the resultant is a polynomial in the system’s coefficients which vanishes if and only if the system is satisfiable). In this paper we present several NPhardness results for testing whether a multivariate resultant vanishes, or equivalently for deciding whether a square system of homogeneous equations is satisfiable. Our main result is that testing the resultant for zero is NPhard under deterministic reductions in any characteristic, for systems of lowdegree polynomials with coefficients in the ground field (rather than in an extension). We also observe that in characteristic zero, this problem is in the ArthurMerlin class AM if the generalized Riemann hypothesis holds true. In positive characteristic, the best upper bound remains PSPACE.
@inProceedings{GKP10,
title = {{The Multivariate Resultant is NPhard in Any Characteristic}},
author = {Grenet, Bruno and Koiran, Pascal and Portier, Natacha},
year = 2010,
booktitle = {Proceedings of MFCS},
number = 6281,
pages = {477{}488},
doi = {10.1007/9783642151552_42},
series = {LNCS},
publisher = {Springer},
arxiv = {0912.2607},
}