Sub-cubic polynomial system solving for arbitrary zero-dimensional ideals: removing the shape-position, radicality, regularity, and large-characteristic hypotheses

Solving a polynomial system by Gröbner bases proceeds in two stages: compute a basis for the degree-reverse-lexicographic (DRL) order, then convert it to the lexicographic (LEX) order by a change-of-ordering step. Faugère, Gaudry, Huot and Renault (arXiv:1304.6039, ISSAC 2014) showed that, for radical ideals in Shape Position defined by regular sequences over a field of sufficiently large characteristic, the whole solving process runs in $\widetilde{O}(D^\omega)$ arithmetic operations, where $D$ is the number of solutions and $\omega<2.373$ is the exponent of matrix multiplication. The problem asks whether this sub-cubic guarantee extends to arbitrary zero-dimensional polynomial systems — inputs that need not be regular, radical, in Shape Position, or defined over a large-characteristic field — and what the optimal complexity exponent for polynomial system solving is. Later literature already removed part of the hypotheses: Neiger and Schost (2020) perform the change of ordering for arbitrary zero-dimensional ideals once the multiplication matrices are known, Berthomieu, Neiger and Safey El Din (2022) improve the Shape-Position case below $D^\omega$ under a stability assumption on the leading terms, and van der Hoeven and Lecerf (2021) achieve quasi-quadratic time for generic systems. The uniform worst-case question — the DRL stage without regularity, unconditional change of ordering without generic coordinates or characteristic restrictions, quantitative finite-field guarantees, and matching lower bounds — remains open.

Background

A Gröbner basis of a polynomial ideal $I\subset K[x_1,\dots,x_n]$ is a generating set whose leading monomials (for a fixed monomial ordering) generate the ideal of all leading monomials of $I$; it is the analogue for polynomial systems of a row-echelon form for linear systems, and from it many questions about the solutions can be answered by linear algebra. A monomial ordering is a total order on monomials compatible with multiplication; the degree-reverse-lexicographic order (DRL) usually makes Gröbner basis computation fastest, while the lexicographic order (LEX) produces a triangular, structured output from which the solutions can be read off. An ideal is zero-dimensional if the quotient ring $A=K[x_1,\dots,x_n]/I$ is a finite-dimensional $K$-vector space; its dimension $D$ is the degree of the ideal, i.e. the number of solutions in an algebraic closure counted with multiplicity. The ideal is radical when all solutions are simple (no multiplicities). It is in Shape Position when its LEX Gröbner basis has the form $\{x_1-h_1(x_n),\dots,x_{n-1}-h_{n-1}(x_n),h_n(x_n)\}$, i.e. the solutions admit a univariate polynomial representation. The PoSSo problem (Polynomial Systems Solving) asks, given $f_1,\dots,f_s\in K[x_1,\dots,x_n]$ generating a zero-dimensional ideal over $K=\mathbb{Q}$ or a finite field, to compute such a univariate representation of the solutions, from which exact or certified approximate solutions are recovered by univariate root finding. A rational univariate representation is one standard such output: a univariate polynomial whose roots encode the solutions, together with univariate rational functions recovering the value of each coordinate $x_i$ at every solution.

The classical pipeline is: (1) compute the DRL Gröbner basis, then (2) convert it to the LEX basis by the FGLM algorithm of Faugère, Gianni, Lazard and Mora (1993), which views the conversion as linear algebra in the $D$-dimensional vector space $A$: it first builds the multiplication matrices of the variables (the matrices of the maps $f\mapsto x_i f$ on $A$) and then finds the LEX basis as linear relations among normal forms, in $O(nD^3)$ operations. Change of ordering is the bottleneck of the whole process.

Write $\omega$ for the exponent of square matrix multiplication, currently known to satisfy $2\le\omega<2.373$; many linear-algebra problems (inversion, determinant, echelon forms) cost $O(m^\omega)$ for $m\times m$ matrices. A regular sequence is a sequence of polynomials $f_1,\dots,f_s$ such that each $f_{i+1}$ does not divide zero modulo $\langle f_1,\dots,f_i\rangle$ — a genericity condition satisfied by 'random' dense systems; for regular systems of degree $\le d$, Lazard's Gaussian-elimination view of Gröbner bases and subsequent analyses give a DRL basis in $\widetilde{O}(d^{\omega n})$ operations, and generically the classical Bézout bound (the number of solutions is at most the product of the degrees) gives $D=d^n$. Building on Wiedemann-type sparse algorithms of Faugère and Mou (Sparse FGLM) — Krylov-subspace methods that recover the needed linear-algebra data from few matrix–vector products with the sparse multiplication matrices — Faugère, Gaudry, Huot and Renault proved: (i) deterministically, for radical ideals in Shape Position generated by a regular sequence of bounded degree $d$, the univariate representation is computable in $\widetilde{O}(d^{\omega n})$ operations; (ii) by a Las Vegas algorithm (an algorithm that always answers correctly but may report failure, with bounded failure probability), for regular sequences of arbitrary degree, the same bound holds after a random linear change of coordinates $g\in GL(K,n)$ ($GL(K,n)$ being the group of invertible $n\times n$ matrices over $K$), which puts an arbitrary ideal into Shape Position and lets the last multiplication matrix be read off from the DRL basis via the theory of generic initial ideals (the initial ideal of $g\cdot I$ for generic $g$, which is Borel-fixed — stable under upper-triangular coordinate changes — and highly structured). Consequently, for generic systems reaching the Bézout bound, solving costs $\widetilde{O}(D^\omega)$ instead of $\widetilde{O}(D^3)$. Three families of hypotheses remain: Shape Position and radicality of the ideal; regularity of the input sequence for the DRL stage; and, over finite fields, quantitative control of the probability that the random coordinate change fails — the generic-initial-ideal argument needs the characteristic $p$ to exceed the Macaulay bound $\sum_i(\deg f_i-1)+1$, so small characteristic is not covered. The paper also observes that nothing is known about lower bounds: whether complexity below $\omega$ in $D$ (quadratic or quasi-linear) is achievable for PoSSo was open when it appeared.

Problem Statement

Let $K$ be the rational field $\mathbb{Q}$ or a finite field $\mathbb{F}_q$ of arbitrary characteristic, and let $f_1,\dots,f_s\in K[x_1,\dots,x_n]$ generate a zero-dimensional ideal $I$ of degree $D$ (the number of solutions in an algebraic closure, counted with multiplicity). No genericity hypothesis is made on the input: the sequence $f_1,\dots,f_s$ need not be regular, the ideal need not be radical, its lexicographic Gröbner basis need not be in Shape Position, and the characteristic of $K$ is unrestricted.

(1) Uniform sub-cubic solving. Does there exist an algorithm which, on every such input, outputs a univariate representation of the solutions — e.g. the lexicographic Gröbner basis or a rational univariate representation — using $\widetilde{O}(D^\omega)$ arithmetic operations in $K$, where $\omega<2.373$ is the exponent of square matrix multiplication and where, following the convention of the source paper, $\widetilde{O}$ hides logarithmic factors in $D$ and polynomial factors in the number of variables $n$ and in the maximal input degree $d$? In particular, natural components of such a result are the following: (i) a Bézout-type complexity bound for computing the degree-reverse-lexicographic Gröbner basis that does not assume the input sequence to be regular (the known $\widetilde{O}(d^{\omega n})$ bound uses regularity through the Macaulay bound on the degrees appearing during the computation); (ii) a change of ordering from the DRL basis to the LEX basis unconditionally bounded by $\widetilde{O}(D^\omega)$ — without a random change of coordinates, without structural assumptions on the initial ideal that are guaranteed only in generic coordinates, and valid in small positive characteristic (where the Borel-fixedness of generic initial ideals, and hence the free read-off of the multiplication matrices, can fail for degrees congruent to $0$ modulo $p$); (iii) for whatever random choices the algorithm makes, deterministic variants or quantitative bounds on the finite-field failure probabilities, in all characteristics.

(2) Optimality. Determine the optimal arithmetic-complexity exponent for PoSSo as a function of $D$: in particular, whether the quasi-quadratic bound $\widetilde{O}(D^2)$ — achieved for sufficiently generic square systems by van der Hoeven and Lecerf — is achievable for arbitrary zero-dimensional systems, and which nontrivial lower bounds (unconditional, or conditional on the exponent of matrix multiplication) hold for computing a univariate representation of the solutions.

References

1. Jean-Charles Faugère, Pierrick Gaudry, Louise Huot, Guénaël Renault. Polynomial Systems Solving by Fast Linear Algebra. arXiv:1304.6039 (2013). DOI 10.48550/arXiv.1304.6039, https://arxiv.org/abs/1304.6039 — published in extended form as 'Sub-cubic change of ordering for Gröbner basis: a probabilistic approach', ISSAC 2014, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 170–177, DOI 10.1145/2608628.2608669, https://doi.org/10.1145/2608628.2608669.
2. J.C. Faugère, P. Gianni, D. Lazard, T. Mora. Efficient computation of zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation 16(4):329–344 (1993). DOI 10.1006/jsco.1993.1051, https://doi.org/10.1006/jsco.1993.1051
3. D. Lazard. Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In: Computer Algebra, EUROCAL'83, Lecture Notes in Computer Science 162, pp. 146–156, Springer (1983). DOI 10.1007/3-540-12868-9_99, https://doi.org/10.1007/3-540-12868-9_99
4. Jean-Charles Faugère, Chenqi Mou. Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices. ISSAC 2011, Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, pp. 115–122, ACM. DOI 10.1145/1993886.1993908, https://doi.org/10.1145/1993886.1993908
5. Jean-Charles Faugère, Chenqi Mou. Sparse FGLM algorithms. Journal of Symbolic Computation 80:538–569 (2017). DOI 10.1016/j.jsc.2016.07.025, https://doi.org/10.1016/j.jsc.2016.07.025
6. Vincent Neiger, Éric Schost. Computing syzygies in finite dimension using fast linear algebra. Journal of Complexity 60:101502 (2020). DOI 10.1016/j.jco.2020.101502, https://arxiv.org/abs/1912.01848
7. Vincent Neiger, Hamid Rahkooy, Éric Schost. Algorithms for zero-dimensional ideals using linear recurrent sequences. arXiv:1707.01971 (2017). DOI 10.48550/arXiv.1707.01971, https://arxiv.org/abs/1707.01971
8. Seung Gyu Hyun, Vincent Neiger, Hamid Rahkooy, Éric Schost. Block-Krylov techniques in the context of sparse-FGLM algorithms. Journal of Symbolic Computation 98:163–191 (2020). DOI 10.1016/j.jsc.2019.07.010, https://arxiv.org/abs/1712.04177
9. Jérémy Berthomieu, Vincent Neiger, Mohab Safey El Din. Faster Change of Order Algorithm for Gröbner Bases under Shape and Stability Assumptions. ISSAC 2022, Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, pp. 409–418, ACM. DOI 10.1145/3476446.3535484, https://arxiv.org/abs/2202.09226
10. Joris van der Hoeven, Grégoire Lecerf. On the Complexity Exponent of Polynomial System Solving. Foundations of Computational Mathematics 21(1):1–57 (2021). DOI 10.1007/s10208-020-09453-0, https://doi.org/10.1007/s10208-020-09453-0
11. Guénaël Renault, Tristan Vaccon. On the p-adic stability of the FGLM algorithm. arXiv:1602.00848 (2016). DOI 10.48550/arXiv.1602.00848, https://arxiv.org/abs/1602.00848
12. Tristan Vaccon. Matrix-F5 algorithms and tropical Gröbner bases computation. Journal of Symbolic Computation 89:227–254 (2018). DOI 10.1016/j.jsc.2017.11.014, https://doi.org/10.1016/j.jsc.2017.11.014
13. Yuki Ishihara, Tristan Vaccon, Kazuhiro Yokoyama. On FGLM algorithms with tropical Gröbner bases. ISSAC 2020, Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, pp. 257–264, ACM. DOI 10.1145/3373207.3404037, https://arxiv.org/abs/2009.02067
14. Alexander Demin, Fabrice Rouillier, Joao Ruiz. Reading Rational Univariate Representations on lexicographic Groebner bases. arXiv:2402.07141 (2024). DOI 10.48550/arXiv.2402.07141, https://arxiv.org/abs/2402.07141