Given t bivariate polynomials f1, . . . , ft ∈ K[x, y], and an integer k we report a work-in-progress to compute a minimal, not reduced, lexicographic Gröbner basis of the ideal ⟨f1, . . . , ft, x k ⟩ in O ∼ (td 2 k), where d is an upper bound on the y-degree of the fi's. Using the fast normal form algorithm of Schost & St-Pierre [1], this implies that we can compute its reduced Gröbner basis in O ∼ (td 2 k + s 2 dk) where s is the number of polynomials contained in the output Gröbner basis. In many instances this improves the algorithm of Schost & St-Pierre [2] based on the Howell matrix normal form that runs in time O ∼ (td ω k).
Background Lexicographic Gröbner bases (lexGb for short) play a fundamental role when manipulating polynomial systems due to the elimination property that they are endowed with. But the lexicographic order often does not behave well with standard Gröbner bases algorithms [3], whereas the degree reverse lexicographic order has been often observed to behave the best among monomial orders when computing a Gröbner basis. This is grounded in strong theoretical evidences [4,5]. As a result, a standard strategy to compute a zero-dimensional lexGb consists first in computing a Gröbner basis for the degree reverse lexicographic order with efficient modern algorithms like F4, F5 [6,7] and then proceed to a change of order algorithm [8] to compute the reduced lexGb.
In the case of two variables only, the situation is different. For t polynomials f 1 , . . . , f t ∈ K[x, y], of maximal degree d in y, and total degree d tot , Schost and St-Pierre in [2], obtains a running time in O ∼ (t ω d ω d tot ) when at least one f i has for leading monomial y d . As usual ω is the exponent of matrix multiplication. This algorithm computes the Hermite normal form of a generalized Sylvester matrix of the input polynomials, extending the case t = 2 treated by Lazard [9,Section 5].
The same article [2] also considers computing the reduced lexGb modulo x k , that is of the ideal ⟨f 1 , . . . , f t , x k ⟩. The idea is to work in the ring R = K[x]/x k and to compute the Howell normal form of a generalized Sylvester matrix of the f i ∈ R[y]. This Howell normal form is the adaptation of the Hermite normal form for matrices of polynomials with coefficients in R. The cost can be made of O ∼ (td ω k).
Result We consider here the more general moduli P k , for P an irreducible polynomial in K[x] of degree d P . In this paragraph we let d P = 1 to simplify comparisons. Our algorithm based on Euclidean division works in O ∼ (td 2 k) and computes a minimal but not reduced Gröbner basis.
Schost & St-Pierre's normal form algorithm. The cost of reducing this minimal lexGb is due to another article of Schost & St-Pierre [1, Section 4] and is better stated in term of the output lexGb H = (h s , . . . , h 0 ). Assume that lm(h s ) ≺ • • • ≺ lm(h 0 ), where ≺ stands for the lexicographic SCSS 2024: 10th International Symposium on Symbolic Computation in Software Science, August 28-30, 2024, Tokyo, Japan email: xdahan@gmail.com (X. DAHAN) orcid: 0000-0001-6042-6132 (X. DAHAN) order with x ≺ y. Under our setting we have h s = P k , and if we let deg x (P ) = 1 like when P = x, then deg x (h s ) = k. Let deg y (h 0 ) = n 0 be the largest y-degree of the polynomials in H, and let s + 1 = |H| be the number of polynomials in the output. Then reducing H costs O ∼ (s 2 n 0 k) (see [1,Prop. 4.4 & Prop. 5.1]).
Note that s ≤ min{k, d} and n 0 ≤ d. So we obtain an algorithm that computes the reduced lexGb in O ∼ (td 2 k + s 2 n 0 k), always within O ∼ (td 2 k + s 2 dk). This is comparable or better than O ∼ (td ω k) as soon as s 2 n 0 = O(td ω ). In the case t = O(1) and s ≈ d = k, we obtain O ∼ (d 4 ) which is worth than O ∼ (d ω+1 ). But in many cases, the asymptotic complexity is better.
Implementation The articles [2,1] do not mention any implementation. Indeed, implementations of the Howell normal form are apparently seldom and not available publicly -at least in major computer algebra systems. We only found Chapter 4 of the PhD thesis of Storjohann which gives the complexity of O ∼ (d ω k), see [10,Theorem 4.6], and from which originates the result of [2].
On the other hand, since the presented algorithm that computes a minimal non-reduced lexGb in O ∼ (td 2 k) can be compared to the quadratic-time standard Euclidean algorithm, it is efficient up to fast univariate arithmetic (polynomial operations involving the x-variable only). Our implementation in Magma (available at http://xdahan.sakura.ne.jp/lexgb24.html) supports this claim. As for the normal form algorithm modulo a reduced Gröbner basis of Schost & St-Pierre [1, Section 4], making an implementation efficient is an interesting challenge. For now we resorted here to the internal Magma command "Reduce" (in orange).
We tested the algorithm for two input polynomials modulo x k :
The reduced lexGb of ⟨a k , b k , x k ⟩ has s + 1 = k + 1 polynomials (the maximum possible) and is dense (it has O(k 3 ) coefficients). Therefore, this family of examples is suitable for benchmarking as it involves worst case situations: the number of recursive calls is maximal, the cost of the normal form is maximal. Note also that taking only t = 2 polynomials as input is not restrictive since recursive calls involve more polynomials in the input. We report below on timings for k = 30, 40, . . . , 120 (left) and k = 70, 140, . . . , 250 (right) over a prime finite field of 64bits. With t = O(1), k ≈ d, the theoretical cost to obtain a minimal lexGb is O ∼ (k 3 ). The internal command Reduce of Magma becomes quickly the bottleneck (in orange. Time > 500s for k > 200, timings are not displayed). Without surprise, its timing grows faster than the cost of the fast version of Schost & St-Pierre, which is here O ∼ (k 4 ) (it seems to be closer to something in O ∼ (k 5 )). Although we could not compare with the Howell form approach of [2], we could compare with the internal Gröbner engine of Magma by calling GroebnerBasis([a, b, x k ]) (red, until k = 100). As already reported in [11], the timings are incomparably slow.
Scope The motivation behind working modulo P k is twofold. Firstly, this serves as a skeleton for a similar algorithm that tackles the more general input ⟨f 1 , . . . , f t , T ⟩ for an arbitrary polynomial T ∈ K[x], not necessarily the power of an irreducible one. See [11], which utilizes dynamic evaluation, for a detailed account when t = 2. Secondly, we would like to target the reduced lexGb H of the general input ⟨f 1 , . . . , f t ⟩, not modulo a univariate polynomial, with our Euclideandivision based algorithm. After the work [11], a natural question asks how can we compute the lexGb of two polynomials f 1 , f 2 from their subresultant sequence? To this end, it is enlightening to access the lexGbs modulo P k i i , where P k i i runs over the primary factors of the elimination polynomial of the (f j ) j 's. The work [12] then permits to understand how these lexGbs can reconstruct H via Chinese remainders. These remarks lead to a reasonable hope to compute a minimal lexGb faster than the O ∼ (t ω d ω d tot ) of [2].
Treating only two variables is clearly limited. Yet, all aspects shall be mastered as there is a cliff in difficulty when considering more than two variables: no general form of Lazard's structural theorem [9] which is key in this work and in [2,1]. Let us mention though the radical case where some sort of generalizations of Lazard's theorem have been shown [13,14,15]. The Euclidean algorithm based approach certainly helps to understand where this difficulty stems from. One aspect of it can be related to the absence of a MonicForm routine (see Eq. ( 1)) that would transform a nilpotent polynomial, say in K[x, y, z] modulo a primary ideal in K
Observe the new polynomial xy introduced with the smaller variables x and y. This phenomenon does not appear for two variables only. Therefore, the Euclidean division approach helps to understand better the case of three variables or more.
Recently, articles dealing with bivariate Gröbner bases have flourished. A number of them address the question of quasi-optimal asymptotic complexity estimates, with adequate genericity assumptions, and the relation with the resultant [16,17,18,19,20]. Focusing on non-generic lexGbs, the work [11] from which the present work is inspired, generalizes dynamic evaluation to a non-squarefree modulus. We have already cited [2,1]. Besides the fast normal form in Section 4, the article [1] introduces a fast Newton iteration for general bivariate lexGbs.
Overview It is based on ideas introduced in [11], which is constrained to two input polynomials a and b. Let us summarize the content of the first part of [11] which focuses on working modulo P k (the second part focuses on working modulo an arbitrary monic univariate polynomial). The divisions occurring in the Euclidean algorithm of a and b modulo P k require invertible leading coefficients. In the ring R = K[x]/⟨P k ⟩ elements are either invertible or nilpotent. Weierstrass preparation theorem realized by Hensel lifting permits to circumvent this difficulty, by calculating a "monic form": Given f ∈ K[x, y] reduced modulo P k , we denote f, C f ← MonicForm( f , P k ) where:
The Euclidean algorithm can be pursued with the monic f , and C f f will be part of the lexGb. We adapt this strategy to design the main algorithm
y] and H is a minimal lexGb of ⟨f ⟩ + ⟨G⟩. Assuming for the moment this algorithm correct and running in time O ∼ (d 2 k ′ ), the general algorithm 1 "lexGb" has the following worst-case complexity:
Additional degree constraints on a, b, C a , C b depend on one or the other algorithm. The output is a minimal lexGb of ⟨C a a, C b b⟩ + ⟨G⟩ (whence the name "AddTwo"). The key point is the degree decrease obtained by the Euclidean division at Lines 24 and 34. Then they undertake recursive calls. These divisions henceforth imply the complexity stated in Theorem 1.
//Special "easy" case where input polynomial ∈ K[x]
The main algorithm 2 "Add" The purpose is given a minimal lexGb G as above, not necessarily zero-dimensional, and a polynomial f ∈ K[x, y] to construct a minimal lexGb of the ideal ⟨f ⟩+⟨G⟩. Thus, it is interesting for its own. It builds upon Euclidean divisions, the key point consists in obtaining a degree (in y) decrease through a Euclidean division (see Lines 24 and 34), and then to proceed to adequate recursive calls, with smaller input data (Lines 21 and 23). The algorithm 2 "Add" actually only treats base cases, and then calls Algorithm 3 "AddGeneric", whose input are amenable to recursive calls. One base case is when f ∈ K[x] (Line 10) treated apart in the "easy" AddUnivariate. We omit this short algorithm in this work-in-progress report. Otherwise Algorithm 3 AddGeneric, called at Line 13, treats "generic" input: f monic, reduced modulo P k , and
Its role essentially boils down to managing four cases. Write G = [g 0 , . . . , g s ] (lm(g s ) ≺ • • • ≺ lm(g 0 ), so that g s = P k and deg y (g 0 ) = n 0 ).
The first case distinction is treated by renaming variables (if-test at Line 16). The subcase distinction (if-test at Line 20) leads to call two subroutines AddTwoA and AddTwoB which looks very similar, but with key differences.
The input are monic bivariate polynomials a, b, monic univariate polynomials C a , C b which are powers of P , and a minimal lexGb G modulo P k .