Faster bivariate lexicographic Gröbner bases modulo xk Xavier DAHAN1 1 Tohoku university, IEHE, Sendai, Japan Abstract 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 , xk ⟩ in O∼ (td2 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∼ (td2 k + s2 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). Keywords Gröbner bases, Lexicographic order, Bivariate, Euclidean division 1. Introduction 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 f1 , . . . , ft ∈ K[x, y], of maximal degree d in y, and total degree dtot , Schost and St-Pierre in [2], obtains a running time in O∼ (tω dω dtot ) when at least one fi 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 xk , that is of the ideal ⟨f1 , . . . , ft , xk ⟩. The idea is to work in the ring R = K[x]/xk and to compute the Howell normal form of a generalized Sylvester matrix of the fi ∈ 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 dP . In this paragraph we let dP = 1 to simplify comparisons. Our algorithm based on Euclidean division works in O∼ (td2 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 = (hs , . . . , h0 ). Assume that lm(hs ) ≺ · · · ≺ lm(h0 ), 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) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings 7 order with x ≺ y. Under our setting we have hs = P k , and if we let degx (P ) = 1 like when P = x, then degx (hs ) = k. Let degy (h0 ) = n0 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∼ (s2 n0 k) (see [1, Prop. 4.4 & Prop. 5.1]). Note that s ≤ min{k, d} and n0 ≤ d. So we obtain an algorithm that computes the reduced lexGb in O∼ (td2 k + s2 n0 k), always within O∼ (td2 k + s2 dk). This is comparable or better than O∼ (tdω k) as soon as s2 n0 = O(tdω ). In the case t = O(1) and s ≈ d = k, we obtain O∼ (d4 ) 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∼ (td2 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). Some timings We tested the algorithm for two input polynomials modulo xk : k k ! ! Y Y i i−1 i ak ≡ (y + i + x + · · · + x ) , bk ≡ (y + 1 + 2x) (y + i + x + · · · + x + 2x ) i=1 i=2 The reduced lexGb of ⟨ak , bk , xk ⟩ 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 8 the internal Gröbner engine of Magma by calling GroebnerBasis([a, b, xk ]) (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 ⟨f1 , . . . , ft , 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 ⟨f1 , . . . , ft ⟩, not modulo a univariate polynomial, with our Euclidean- division based algorithm. After the work [11], a natural question asks how can we compute the lexGb of two polynomials f1 , f2 from their subresultant sequence? To this end, it is enlightening to access the lexGbs modulo Piki , where Piki runs over the primary factors of the elimination polynomial of the (fj )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ω dtot ) 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[x, y]. Think of f = xz 2 + yz + x + y, nilpotent modulo the primary ⟨x2 , y 2 ⟩ ⊂ K[x, y]. It appears that the reduced lexGb of the ideal ⟨f, y 2 , x2 ⟩ is [f, y 2 , xy, x2 ]. 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. Related works 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. 2. The algorithm 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, Cf ← MonicForm(f˜, P k ) where: Cf = gcd(content(f˜), P k ) ∈ K[x], f is monic in y, ⟨f˜, P k ⟩ = ⟨Cf f, P k ⟩. (1) The Euclidean algorithm can be pursued with the monic f , and Cf f will be part of the lexGb. We adapt this strategy to design the main algorithm H ← Add(f, G) where G is a minimal ′ lexGb such that G ∩ K[x] = ⟨P k ⟩ with k ′ ≤ k, f ∈ K[x, y] and H is a minimal lexGb of ⟨f ⟩ + ⟨G⟩. Assuming for the moment this algorithm correct and running in time O∼ (d2 k ′ ), the general algorithm 1 “lexGb” has the following worst-case complexity: 9 Algorithm 1: G ← lexGb(f1 , . . . , ft ; P k ) Input: Bivariate polynomials f1 , . . . , ft . Power of an irreducible polynomial P k ∈ K[x]. Output: reduced lexGb of ⟨f1 , . . . , ft , P k ⟩ 1 f1 , . . . , ft ← f1 mod P k , . . . , ft mod P k // O∼ (tddx ) or free k 2 G ← [P ] 3 for i=1,. . . ,t do 4 G ← Add(fi , G) // O∼ (d2 kdP ) 5 return Reduce(G) // Reduce based on the normal form of [1, Section 4]. O∼ (s2 n0 k) Theorem 1. Let d be the maximal degree in y of the polynomials f1 , . . . , ft . Let dx their maximal degree in x. Let dP = degx (P ). Algorithm 1 computes a minimal lexGb of ⟨f1 , . . . , ft , P k ⟩ in O∼ (td2 kdP + tddx ). If the input polynomials are reduced modulo P k , or if P = x then the cost is O∼ (td2 kdP ). The reduced lexGb requires additionally O∼ (s2 n0 k) operations in K, where s = |G|, n0 = degy (g0 ) is the largest y-degree of the polynomials in the output. Algorithm 2: Add(g, G) Input: g ∈ K[x, y], G = [g0 , . . . , gs ] minimal lexGb modulo P k = gs Output: minimal lexGb of ⟨g⟩ + ⟨G⟩ 6 if G == [constant] then 7 return [1] 8 f, Cf ← MonicForm(g, P k ) // ⟨Cf f, P k ⟩ = ⟨g, P k ⟩, f monic, Cf ∈ K[x] 9 if f == 1 then 10 return AddUnivariate(Cf , G) //Special “easy” case where input polynomial ∈ K[x] 11 if |G| == 1 then 12 return [Cf f, P k ] 13 return AddGeneric(f, Cf , G) // Output generates ⟨Cf f ⟩ + ⟨G⟩ 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 df := degy (f ) ≥ 1. Its role essentially boils down to managing four cases. Write G = [g0 , . . . , gs ] (lm(gs ) ≺ · · · ≺ lm(g0 ), so that gs = P k and degy (g0 ) = n0 ). 1. Case distinction: ℓ > k or ℓ ≤ k (equivalently Cf ∤ gs = P k or Cf | gs ) 2. Subcases distinction: df ≤ n0 or df > n0 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. Algorithms AddTwoA and AddTwoB The input are monic bivariate polynomials a, b, monic univariate polynomials Ca , Cb which are powers of P , and a minimal lexGb G modulo P k . 10 Algorithm 3: AddGeneric(f, Cf , G) Input: f ∈ K[x, y] monic degy (f ) ≥ 1, Cf = P t ∈ K[x], G minimal lexGb modulo P k Output: minimal lexGb of ⟨Cf f ⟩ + ⟨G⟩ 14 Let G = [g0 , . . . , gs−1 , P k ], and write g0 = M0 g0,y 15 Ca ← gcd(M0 , Cf ) // Ca = Cf or Ca = M0 16 if Ca == Cf then 17 a ← f, b ← g0,y , Cb ← M0 // Cb b = g0 18 else 19 b ← f, a ← g0,y , Cb ← Cf // Ca a = g0 20 if degy (a) > degy (b) then // Always holds ⟨Ca a, Cb b, P ⟩ = ⟨Cf f, g0 , P k ⟩ k 21 return AddTwoA(a, b, Ca , Cb , G≥1 ) // lexGb of ⟨Ca a, Cb b⟩ + ⟨g1 , . . . , gs ⟩ 22 else 23 return AddTwoB(a, b, Ca , Cb , G≥1 ) // lexGb of ⟨Ca a, Cb b⟩ + ⟨g1 , . . . , gs ⟩ Additional degree constraints on a, b, Ca , Cb depend on one or the other algorithm. The output is a minimal lexGb of ⟨Ca a, Cb 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. Algorithm 4: AddTwoA(a, b, Ca , Cb , G) Input: 1. a, b ∈ K[x, y] monic, degy (a) > degy (b) 2. Ca , Cb ∈ K[x] powers of P , Ca | Cb | P k , 3. G minimal lexGb modulo P k , and degy (a) > degy (G) Output: minimal lexGb of ⟨Ca a, Cb b⟩ + ⟨G⟩ k 24 r ← a mod b // b monic. Over R = K[x]/⟨ PCb ⟩. It holds ⟨Cb a, Cb b, P k ⟩ = ⟨Cb b, Cb r, P k ⟩ g1 25 if r ≡ 0 mod Cb then // Here ⟨Cb a, Cb b, P k ⟩ = ⟨Cb b, P k ⟩ ′′ 26 1 G ← Add(b, Cb G) // Here ⟨Cb G ′′ ⟩ = ⟨Cb b⟩ + ⟨G⟩ 27 else 28 G ′ ← Add(r, C1b G) // ⟨Cb G ′ ⟩ = ⟨Cb r⟩ + ⟨G⟩ ′′ ′ ′′ ′ 29 G ← Add(b, G ) // ⟨Cb G ⟩ = ⟨Cb b⟩ + ⟨Cb G ⟩ = ⟨Cb b, Cb r⟩ + ⟨G⟩ = ⟨Cb b, Cb a⟩ + ⟨G⟩ 30 if Ca == Cb then 31 return Cb · G ′′ // Here ⟨Cb G ′′ ⟩ = ⟨Cb b, Ca a⟩ + ⟨G⟩ 32 else 33 return [Ca a] cat Cb · G ′′ // output generates ⟨Ca a⟩ + ⟨Cb G ′′ ⟩ = ⟨Ca a, Cb b⟩ + ⟨G⟩ Algorithm 5: AddTwoB(a, b, Ca , Cb , G) Input: 1. a, b ∈ K[x, y] monic, degy (a) ≤ degy (b), 2. Ca , Cb ∈ K[x] powers of P , Ca | Cb | P k , 3. G minimal lexGb modulo P k , degy (b) > degy (G) Output: minimal lexGb of ⟨Ca a, Cb b⟩ + ⟨G⟩ k Cb 34 r← C a b mod a // a monic. Over R = K[x]/⟨ PCa ⟩. It holds ⟨Ca r, Ca a, P k ⟩ = ⟨Cb b, Ca a, P k ⟩. k 35 if r ≡ 0 mod PCa then // Here ⟨Ca a, P k ⟩ = ⟨Ca a, Cb b, P k ⟩ 1 36 return Ca · Add(a, Ca G) // Output generates ⟨Ca a⟩ + ⟨G⟩ 37 else 38 G ′ ← Add(r, C1a G) // ⟨Ca G ′ ⟩ = ⟨Ca r⟩ + ⟨G⟩ return Ca · Add(a, G ′ ) // Output generates ⟨Ca a⟩ + ⟨Ca G ′ ⟩ = ⟨Ca a, Cb b⟩ + ⟨G⟩ 11 References [1] É. Schost, C. St-Pierre, Newton iteration for lexicographic Gröbner bases in two variables, Journal of Algebra 653 (2024) 325–377. [2] É. Schost, C. St-Pierre, p-adic algorithms for bivariate Gröbner bases, in: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, ACM, New York, NY, USA, 2023. [3] K. Kalorkoti, Counting and Gröbner bases, J. Symbolic Computation 31 (2001) 307–313. [4] D. Bayer, M. Stillman, A criterion for detecting m-regularity, Inventiones mathematicae 87 (1987) 1–11. [5] H. Loh, The converse of a theorem by Bayer and Stillman, Advances in Applied Mathematics 80 (2016) 62–69. [6] J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), Journal of pure and applied algebra 139 (1999) 61–88. [7] J.-C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), in: Proceedings of the 2002 international symposium on Symbolic and algebraic computation, 2002, pp. 75–83. [8] 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 (1993) 329–344. [9] D. Lazard, Ideal bases and primary decomposition: case of two variables, Journal Symbolic Computation 1 (1985) 261–270. [10] A. Storjohann, Algorithms for matrix canonical forms, Ph.D. thesis, ETH Zürich, 2000. [11] X. Dahan, Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one, Journal of Symbolic Computation 110 (2022) 24–65. [12] X. Dahan, Chinese remainder theorem for bivariate lexicographic Gröbner bases, in: Proceed- ings of the 2023 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’23, ACM press, New York, NY, USA, 2023. [13] M. Lederer, The vanishing ideal of a finite set of closed points in affine space, J. of Pure and Applied Algebra 212 (2008) 1116–1133. [14] M. Marinari, T. Mora, A remark on a remark by Macaulay or enhancing Lazard structural theorem, Bull. Iranian Math. Soc. 29 (2003) 1–45, 85. [15] B. Felszeghy, B. Ráth, L. Rónyai, The lex game and some applications, Journal of Symbolic Computation 41 (2006) 663 – 681. [16] G. Villard, On computing the resultant of generic bivariate polynomials, in: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’18, ACM, 2018, p. 391–398. [17] G. Villard, Elimination ideal and bivariate resultant over finite fields, in: Proceedings of the 2023 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’23, ACM press, New York, NY, USA, 2023. [18] J. van der Hoeven, R. Larrieu, Fast reduction of bivariate polynomials with respect to sufficiently regular Gröbner bases, in: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’18, ACM, New York, NY, USA, 2018, pp. 199–206. [19] J. van der Hoeven, R. Larrieu, Fast Gröbner basis and polynomial reduction for generic bivariate ideal, Applicable Algebra in Engineering, Communication and Computing 30 (2019) 509–539. [20] J. van der Hoeven, G. Lecerf, Fast computation of generic bivariate resultants, Journal of Complexity 62 (2021) 101499. 12