Learning to compute Gröbner bases

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 11:09:48

Abstract: Solving a polynomial system, or computing an associated Gröbner basis, has been a fundamental task in computational algebra. However, it is also known for its notorious doubly exponential time complexity in the number of variables in the worst case. This paper is the first to address the learning of Gröbner basis computation with Transformers. The training requires many pairs of a polynomial system and the associated Gröbner basis, raising two novel algebraic problems: random generation of Gröbner bases and transforming them into non-Gröbner ones, termed as backward Gröbner problem. We resolve these problems with 0-dimensional radical ideals, the ideals appearing in various applications. Further, we propose a hybrid input embedding to handle coefficient tokens with continuity bias and avoid the growth of the vocabulary set. The experiments show that our dataset generation method is a few orders of magnitude faster than a naive approach, overcoming a crucial challenge in learning to compute Gröbner bases, and Gröbner computation is learnable in a particular class.

Main paper: 
 introduction: 
 Understanding the properties of polynomial systems and solving them have been a fundamental problem in computational algebra and algebraic geometry with vast applications in cryptography (Bard, 2009; Yasuda et al., 2015) , control theory (Park & Regensburger, 2007) , statistics (Diaconis & Sturmfels, 1998; Hibi, 2014) , computer vision (Stewenius, 2005) , systems biology (Laubenbacher & Sturmfels, 2009) , and so forth. Special sets of polynomials, called Gröbner bases, play a key role to this end. In linear algebra, the Gaussian elimination simplifies or solves a system of linear equations by transforming its coefficient matrix into the reduced row echelon form. Similarly, a Gröbner basis can be regarded as a reduced form of a given polynomial system, and its computation is a generalization of the Gaussian elimination to general polynomial systems.However, computing a Gröbner basis is known for its notoriously bad computational cost in theory and practice. It is an NP-hard problem, and its worst-case time complexity is doubly exponential in the number of variables (Mayr & Meyer, 1982; Dubé, 1990) . Nevertheless, because of its importance, various computation algorithms have been proposed in computational algebra to obtain Gröbner bases in better runtime. Examples include Faugère's F4/F5 algorithms (Faugère, 1999; Faugère, 2002) and M4GB (Makarim & Stevens, 2017) .In this study, we address this challenging task of computing Gröbner bases using machine learning.Recent studies have revealed the potential of transformer models as a powerful solver of algebraic computations. Namely, instead of designing explicit computational procedures, we train a machine learning model using a large amount of (non-Gröbner set, Gröbner basis) pairs. A similar framework has also been used for other mathematics tasks. For example, (Lample & Charton, 2019) showed that transformer models can learn symbolic integration simply by observing many ( df /dx , f ) pairs in training. The training samples are generated by first randomly generating f and computing its derivative df /dx and/or the reverse process. Other examples include solving ordinary differential equations (Lample & Charton, 2019) , symbolic regression (Biggio et al., 2021) , and basic linear algebra (Charton, 2022a) . For all the tasks, transformers exhibited a high performance.A crucial challenge in the learning of Gröbner basis computation is that it is mathematically unknown how to efficiently generate many (non-Gröbner set, Gröbner basis) pairs. To resolve this, we need an efficient backward approach (i.e., solution-to-problem computation) because, as discussed above, the forward approach (i.e., problem-to-solution computation) is prohibitively expensive. Particularly, we need to address (i) a random generation of Gröbner bases and (ii) a backward transfor-mation from a Gröbner basis to an associated non-Gröbner set. To our knowledge, neither of them has been addressed in computational algebra because of the lack of motivations and applications; all the efforts have been dedicated to the forward computation from a non-Gröbner set to Gröbner basis. The central contributions of this study are the discovery of these new mathematical problems, efficient computational algorithms for them, and the first machine learning approach for Gröbner basis computation, summarized as follows.• We provide the first approach to the Gröbner computation using a machine learning model and experimentally show that transformers can actually learn it. Unlike most prior studies, our results indicate that training a transformer may be a compromise to NP-hard problems to which no efficient (even approximate or probabilistic) algorithms have been designed.• We uncovered two unexplored algebraic problems-random generation of Gröbner bases and backward Gröbner problem and propose efficient methods to address them, particularly for the zero-dimensional case. These problems are not only essential to generating a dataset for training a transformer but also algebraically interesting, thus encouraging the interaction between computational algebra and machine learning.• Our experiments demonstrate that our method is highly efficient and faster than a baseline method by two to five orders of magnitude in dataset generation. Transformers trained on the generated datasets successfully compute Gröbner bases with moderate accuracy. 
related work: 
 Gröbner basis computation. Gröbner basis is one of the fundamental concepts in algebraic geometry and commutative ring theory, see (Cox, 2005; Gruel & Pfister, 2008) . By its computational aspect, Gröbner basis is a very useful tool for analyzing the mathematical structures of solutions of algebraic constraints. Notably, the form of Gröbner bases is very suited for finding solutions and allows parametric coefficients. For such sought-after applications, it is vital to make Gröbner basis computation very efficient and practical. Following the definition of Gröbner bases in (Buchberger, 1976) , the original algorithm to compute them can be presented as (i) create potential new leading terms by constructing S-polynomials, (ii) reduce them either to zero or to new polynomials for the Gröbner basis, and (iii) repeat until no new S-polynomials can be constructed. Plenty of works has been developed to surpass this algorithm. There are four main strategies: (a) avoid unnecessary S-polynomials, following the F 5 algorithm and the more general signature-based algorithms (Faugère, 2002; Bardet et al., 2015) . Machine learning appeared for this task in (Peifer et al., 2020) . (b) more efficient reduction using efficient linear algebraic computations, following (Faugère, 1999) and the very recent GPU-using (Berthomieu et al., 2023) . (c) perform modular computations, following (Arnold, 2003; Noro & Yokoyama, 2018) , to prevent coefficient growth during the computation. (d) use the structure of the ideal, e.g., (Faugère et al., 1993; Berthomieu et al., 2022) for change of term ordering for zero-dimensional ideals or (Traverso, 1997) when the Hilbert function is known. In this study, we presents the fifth strategy: (e) Gröbner computation fully via learning without specifying any mathematical procedures.Math transformers. Recent studies have revealed that transformers can be used for mathematical reasoning and symbolic computation. The training of such math transformers only requires samples (i.e., problem-solution pairs), and no explicit procedures need to be specified. (Lample & Charton, 2019) presented the first study that uses transformers for mathematical problems. They showed that transformers can learn symbolic integration and differential equation solving with training with sufficiently many and diverse samples. Since then, transformers have been applied to checking local stability and controllability of differential equations (Charton et al., 2021) , polynomial simplification (Agarwal et al., 2021) , linear algebra (Charton, 2022a; b) , attack to the LWE cryptography Wenger et al. (2022) ; Li et al. (2023) , and symbolic regression (Biggio et al., 2021; Kamienny et al., 2022; d'Ascoli et al., 2022; Kamienny et al., 2023) . (Saxton et al., 2019) provides comprehensive experiments over various mathematical tasks. Another line of math transformers is for automatic theorem proving (Liu et al., 2022; Palermo et al., 2022; Wang & Deng, 2020; Lample et al., 2022; Li et al., 2021; Polu & Sutskever, 2020; Li et al., 2020; Saxton et al., 2019) , which is not of our current scope. Several recent studies point out that transformers may only perform well for in-distribution samples and not generalize well to out-distributions (Dziri et al., 2023) . There are several transformer models that address this challenge (Kim et al., 2021; Cognolato & Testolin, 2022) . While this is a fundamental challenge of the math transformers, the focus of our study lies in revealing whether transformers can learn an extremely difficult mathematical problem, Gröbner basis computation, and establish a dataset generation method to experimentally examine it. 
notations and definitions: 
 Throughout the paper, we consider a polynomial ring k[x 1 , . . . , x n ] with a field k and variables x 1 , . . . , x n . 1 We here introduce basic definitions in algebra. Refer to App. A as necessary. Definition 3.1 (Affine variety). Let F = {f 1 , . . . , f s } be a subset of k[x 1 , . . . , x n ]. Then, we setV (F ) = V (f 1 , . . . , f s ) = {p ∈ k n | f 1 (p) = • • • = f s (p) = 0}. (3.1)We call this the affine variety defined by f 1 , . . . , f s (or by F ).Namely, the affine variety V (f 1 , . . . , f s ) is the zero set of the polynomial system An ideal I that contains f 1 , . . . , f s relates to the polynomial systemf 1 (x 1 , . . . , x n ) = • • • = f s (x 1 , . . . , x n ) = 0. Next,f 1 (x 1 , . . . , x n ) = • • • = f s (x 1 , . . . , x n ) = 0. Indeed, for any p ∈ k n , f i (p) = f j (p) = 0 implies (f i + f j )(p) = 0,and for any h ∈ k[x 1 , . . . , x n ], (hf i )(p) = 0 holds. Thus, roughly speaking, I contains all the polynomials that can be freely appended to the system f 1 (p) = • • • = f s (p) = 0 without changing its affine variety (i.e., solutions). This idea is formalized as follows.Definition 3.3 (Generators). For F = {f 1 , . . . , f s } ⊂ k[x 1 , . . . , x n ], the following set ⟨F ⟩ = ⟨f 1 , . . . , f s ⟩ = s i=1 h i f i | h 1 , . . . , h s ∈ k[x 1 , . . . , x n ] . (3.2)is an ideal and said to be generated by f 1 , . . . , f s (or by F ), and f 1 , . . . , f s are called generators.We next define several notions that are necessary to define the Gröbner basis. Definition 3.4 (Term order (informal)). A term order ≺ is an order of terms2 such as1 ≺ x n ≺ x n-1 ≺ • • • . Constant term 1 = x 0 1 • • • x 0n is the least prioritized in any term order.Strictly speaking, a term order satisfies a few more conditions, but we omit the detail as it is unnecessary to follow this study. We provide two well-known term orders to give an intuition.Example 3.5. The lexicographic order ≺ lex prioritizes terms with larger exponents for the variables of small indices, e.g.,1 ≺ lex x n and x 2 ≻ lex x 2 3 and x 1 x 2 x 2 3 ≺ lex x 1 x 2 2 x 3 . (3.3)Two terms are first compared in terms of the exponent in x 1 (larger one is prioritized), and if a tie-break is needed, the next variable x 2 is considered, and so forth.The next notion plays an important role in the Gröbner basis theory. Definition 3.6 (Leading term). Let F = {f 1 , . . . , f s } ⊂ k[x 1 , . . . , x n ] and let ≺ be a term order. The leading term LT(f i ) of f i is the largest term in f i in ordering ≺. The leading term set of F is LT(F ) = {LT(f 1 ), . . . , LT(f s )}.Given a polynomial set F , the computation of a Gröbner basis is essentially a simplification of F without changing the affine variety V (F ). For example, whenF = {h 1 f, h 2 f } with h 1 + h 2 = 1,we may simplify it to F = {f } through polynomial divisions, while maintaining V (F ) = V ( F ).The leading term defines the simplicity of polynomials; given two polynomialsf 1 , f 2 ∈ I, f 1 is considered simpler if LT(f 1 ) ≺ LT(f 2 ). Indeed, LT(f ) ≺ LT(h 1 f), LT(h 2 f ) in the above example. Now, we introduce Gröbner bases.Definition 3.7 (Gröbner basis). Fix a term order ≺. A finite subset G of an ideal I is said to be a ≺-Gröbner basis of I if ⟨LT(G)⟩ = ⟨LT(I)⟩.Note that ⟨LT(G)⟩ ⊂ ⟨LT(I)⟩ is trivial from G ⊂ I. The nontriviality of the Gröbner basis lies in ⟨LT(G)⟩ ⊃ ⟨LT(I)⟩; that is, a finite number of leading terms can generate the leading term of any polynomial in the infinite set I. The Hilbert basis theorem (Cox et al., 2015) guarantees that every ideal I ̸ = {0} has a Gröbner basis.Other notations. The subset k[x 1 , . . . , x n ] ≤d ⊂ k[x 1 , . . . , x n ] denotes the set of all polynomials of total degree at most d. For a polynomial matrix A ∈ k[x 1 , . . . , x n ] s×s , its determinant is given by det(A) ∈ k[x 1 , . . . , x n ]. The set F p with a prime number p denotes the finite field of order p.We conclude this section with an intuitive (but not necessarily accurate) explanation of Gröbner bases for those unfamiliar with this fundamental concept in algebra.Intuitive explanation of Gröbner bases and polynomial system solving.Let G = {g 1 , . . . , g t } be a Gröbner basis of an ideal ⟨F ⟩ = ⟨f 1 , . . . , f s ⟩. The polynomial system g 1 (x 1 , . . . , x n ) = • • • = g t (x 1 , . . . , x n ) = 0 is a simplified form of f 1 (x 1 , . . . , x n ) = • • • = f s (x 1 , . . . , x n ) = 0 with the same solution set. With a term order ≺ lex , G has a form g 1 ∈ k[x n1 , . . . , x n ], g 2 ∈ k[x n2 , . . . , x n ], . . . , g t ∈ k[x nt , . . . , x n ] with n 1 ≤ n 2 ≤ . . . ≤ n t ,which may be regarded as the "reduced row echelon form" of a polynomial system. In our particular case (i.e., zero-dimensional ideals in shape position; cf. Sec. 4.1), we have (n 1 , n 2 , . . . , n t ) = (1, 2, . . . , n). Thus, one can obtain the solutions of the polynomial system using a backward substitution, i.e., by first solving a univariate polynomial g t , next solving bivariate polynomial g t-1 , which becomes univariate by substituting the solutions of g t , and so forth.4 RANDOM GR ÖBNER BASES AND BACKWARD GR ÖBNER PROB.Our goal is to realize Gröbner basis computation through a machine learning model. To train such a model, we need a large training set {(F i , G i )} m i=1 with a finite polynomial set F i ⊂ k[x 1 , . . . , x n ] and a Gröbner basis G i of ⟨F ⟩. As the computation of F i to G i is computationally expensive in general, we first generate a Gröbner basis G i randomly and then transform it to non-Gröbner set F i . Such a backward generation (i.e., solution-to-problem process) has also been used in related studies that train transformer models for mathematical computations. This is because in general, the forward generation (i.e., problem-to-solution process) is much harder.What makes the learning of Gröbner basis computation hard is that, to our knowledge, neither (i) a random generation of Gröbner basis nor (ii) the backward transform from Gröbner basis to non-Gröbner set has been considered in computational algebra. A central question in computational algebra has been posed on an efficient Gröbner basis computation (i.e., forward generation), and nothing motivates the random generation of Gröbner basis nor the backward transform. Interestingly, machine learning now sheds light on these problems. Formally, we address the following problems for dataset generation. Problem 4.1 (Random generation of Gröbner bases). Fix a term order. Find a collection G = {G i } m i=1 of Gröbner bases, whereG i ⊂ k[x 1 , . . . , x n ] is a Gröbner basis of ⟨G i ⟩.The collection should contain diverse bases, and we need an efficient algorithm for constructing them. Problem 4.2 (Backward Gröbner problem). Fix a term order. Given a Gröbner basis G ⊂ k[x 1 , . . . , x n ], find a collection F = {F i } µ i=1 of polynomial sets that are not Gröbner bases but ⟨F i ⟩ = ⟨G⟩ for all i = 1, . . . , µ. The collection should contain diverse sets, and we need an efficient algorithm for constructing them.In this paper, we address these problems for zero-dimensional ideals. Definition 4.3 (Zero-dimensional ideal). Let F be a set of polynomials in k[x 1 , . . . , x n ]. An ideal ⟨F ⟩ is called a zero-dimensional ideal if all but a finite number of terms belong to LT(⟨F ⟩).If k is an algebraically closed field (e.g., k = C), zero-dimensional ideals relate to polynomial systems with a finite number of solutions (i.e., V (F ) is a finite set.). Zero-dimensional ideals appear in various application of Gröbner bases. For example, a multivariate public-key encrypted communication (a candidate of the Post-Quantum Cryptography) with a public polynomial system F over a finite field F p will be broken if one finds an element of V (F ∪ {x p 1 -x 1 , . . . , x p n -x n }) and the ideal ⟨F ∪ {x p 1 -x 1 , . . . , x p n -x n }⟩ is a zero-dimensional ideal (Ullah, 2012, Sec. 2.2) . A more general approach to Probs. 4.1 and 4.2 with positive-dimensional ideals is an open problem for algebraists. The proofs of the results in the following sections can be found in App. C. 
random generation of gr öbner bases: 
 To address Prob. 4.1, we propose to use the properties of ideals in shape position, for which Gröbner bases have a simple structure. Another potential approach is discussed in App. B. Definition 4.4 (Shape position). Ideal I ⊂ k[x 1 , . . . , x n ] is called in shape position if its Gröbner basis with respect to ≺ lex has a form ofG = {h(x n ), x 1 -g 1 (x n ), . . . , x n-1 -g n-1 (x n )}, (4.1) where h, g 1 , . . . , g n-1 are univariate polynomials in k[x n ].As can be seen, the ≺ lex -Gröbner basis consists of a univariate polynomial in x n and the difference of univariate polynomials in x n and a leading term x i (i < n). Unfortunately, not all ideals are in shape position. Nevertheless, zero-dimensional radical ideals are almost always in shape position (but the converse is not always true). Proposition 4.5 (Gianni & Mora (1989 ), Prop. 1.6, Noro & Yokoyama (1999), Lem. 4.4) . Let I be a zero-dimensional radical ideal3 . If k is of characteristic 0 or a finite field of large enough order, then a random linear coordinate change puts I in shape position.Thus, we can efficiently generate a random zero-dimensional ideal by sampling n polynomials in k[x n ], i.e., h, g 1 , . . . , g n-1 with h ̸ = 0. This resolves Prob. 4.1 even with large m.Gröbner bases for general term orders. This approach assumes term order ≺ lex . In most practical scenarios, ≺ lex -Gröbner bases are already sufficient as they provide a simplified form of polynomial systems as presented at the end of Sec. 3. In computational algebra, it is more common to use the graded reverse lexicographic order because it typically leads to faster computation and smaller size of Gröbner bases. The obtained Gröbner basis is then transformed to the ≺ lex -Gröbner basis using an efficient change-of-ordering algorithm such as the FGLM algorithm (Faugère et al., 1993) . In our case, if necessary, one can similarly use it to obtain Gröbner bases in non-≺ lex order from ≺ lex Gröbner bases. The cost of FGLM algorithm (Faugère et al., 1993) is O(n • deg(h) 3 ). 4To address Prob. 4.2, we consider the following problem. Problem 4.6. Let I ⊂ k[x 1 , . . . , x n ] be a zero-dimensional ideal, and let G = (g 1 , . . . , g t ) ⊤ ∈ k[x 1 , . . . , x n ] t be a ≺-Gröbner basis of I with respect to term order ≺.5 Find a polynomial matrixA ∈ k[x 1 , . . . , x n ] s×t that gives a non-Gröbner set F = (f 1 , . . . , f s ) ⊤ = AG such that ⟨F ⟩ = ⟨G⟩.Namely, we generate a set of polynomialsF = (f 1 , . . . , f s ) ⊤ from G = (g 1 , . . . , g t ) ⊤ by f i = t j=1 a ij g j , for i = 1, . . . , s, where a ij ∈ k[x 1 , . . . ,x n ] denotes the (i, j)-th entry of A. However, ⟨F ⟩ and ⟨G⟩ are generally not identical. The following provides how we should design A to achieve ⟨F ⟩ = ⟨G⟩ for the zero-dimensional case (without radicality or shape position assumption). Theorem 4.7. Let G = (g 1 , . . . , g t ) ⊤ be a Gröbner basis of a zero-dimensional ideal in k[x 1 , . . . , x n ]. Let F = (f 1 , . . . , f s ) ⊤ = AG with A ∈ k[x 1 , . . . , x n ] s×t . 1. If ⟨F ⟩ = ⟨G⟩, it implies s ≥ n. 2. If A has a left-inverse in k[x 1 , . . . , x n ] s×t , ⟨F ⟩ = ⟨G⟩ holds.3. The equality ⟨F ⟩ = ⟨G⟩ holds if and only if there exists a matrix B ∈ k[x 1 , . . . , x n ] t×s such that each row of BA -E t is a syzygy6 of G, where E t is the identity matrix of size t.In Thm. 4.7, the first statement argues that polynomial matrix A should have at least n rows to have ⟨F ⟩ = ⟨G⟩. If the ideal is in shape position, we have a ≺ lex -Gröbner basis G of size n, and thus, A becomes a square or tall matrix. The second statement shows a sufficient condition for designing A such that ⟨AG⟩ = ⟨G⟩. The third statement provides the sufficient and necessary conditions. In practice, the second statement provides a simple approach for the random transformation of a Gröbner basis to a non-Gröbner set without changing the ideal.We first assume to use ≺ lex , where G has exactly n generators. Discussion on the case with general term orders will come later. For the case of s = n, we have the following. Proposition 4.8. For anyA ∈ k[x 1 , . . . , x n ] n×n with det(A) ∈ k \ {0}, we have ⟨F ⟩ = ⟨G⟩.As (non-zero) constant scaling does not change the ideal, we focus on A with det(A) = ±1 without loss of generality. Then, such A can be constructed using a Bruhat decomposition in the form ofA = U 1 P U 2 , (4.2)whereU 1 , U 2 ∈ k[x 1 , . . . ,x n ] n×n are upper-triangular matrices with all-one diagonal entries (i.e., unimodular upper-triangular matrices) and P ∈ {0, 1} n×n denotes a permutation matrix. Noting that A -1 satisfies A -1 A = E n , we have ⟨AG⟩ = ⟨G⟩ from Thm. 4.7. Therefore, random sampling (U 1 , U 2 , P ) of unimodular upper-triangular matrices U 1 , U 2 and a permutation matrix P resolves the backward Gröbner problem for s = n.We extend this idea to the case of s > n using a rectangular unimodular upper-triangular matrix:EQUATIONwhereU ′ 2 ∈ k[x 1 , . . . ,x n ] n×n denotes a unimodular upper-triangular matrix and O s-n,n ∈ k[x 1 , . . . , x n ] (s-n)×n is the zero matrix. The permutation matrix is now P ∈ {0, 1} s×s .Note that U 2 G already gives a non-Gröbner set such that ⟨U 2 G⟩ = ⟨G⟩; however, the polynomials in the last s -n entries of U 2 G are all zero by its construction. Thus, we need a permutation matrix P to shuffle the rows and also U 1 to exclude the zero polynomial from the final polynomial set.To summarize, our strategy is to compute F = U 1 P U 2 G, which only requires a sampling of O(s 2 ) polynomials in k[x 1 , . . . , x n ], and O(n 2 + s 2 )-times multiplications of polynomials. Note that even in the large polynomial systems given in the MQ challenge, a post-quantum cryptography challenge, we have n < 100 and s < 200 (Yasuda et al., 2015) .Summarizing the discussion in the previous sections, we have Alg. 1 and the following. Theorem 4.9. Consider polynomial ring k[x 1 , . . . , x n ]. Given dataset size m, maximum degrees d, d ′ , maximum size of non-Gröbner set s max ≥ n, and term order ≺, Alg. 1 returns a collectionD = {(F i , G i )} mi=1 with the following properties: For all i = 1, . . . , m,1. Both F i , G i ⊂ k[x 1 , . . . , x n ] are finite sets and |F i | ≤ s max . 2. The set G i is a ≺-Gröbner basis. The set F i is not, unless G i , U 1 , U ′ 2 , P are sampled in a non-trivial Zariski closed subset. 7 3. The ideal ⟨F i ⟩ = ⟨G i ⟩ is a zero-dimensional ideal in shape position. The time complexity is O(m(nS 1,d + s 2 S n,d ′ + (n 2 + s 2 )M n,2d ′ +d ))when ≺=≺ lex , where S n,d denotes the complexity of sampling an n-variate polynomial with total degree at most d, and M n,d denotes that of multiplying two n-variate polynomials with total degree at most d. If ⊀ =≺ lex , O(nd 3 ) is additionally needed.The proposed dataset generation method is a backward approach, which first generates solutions and then transforms them into problems. In this case, we have control over the complexity of the Gröbner Algorithm 1: Dataset generation for learning to compute zero-dimensional Gröbner bases. Assumption: polynomial ring k[x 1 , . . . , x n ] Input: dataset size m, maximum degrees d, d ′ , maximum size of non-Gröbner set s max ≥ n, and term order ≺.Output: collection D = {(F i , G i )} m i=1 of non-Gröbner set F i ∈ k[x 1 , . . . , x n ] m and a ≺-Gröbner basis G i ⊂ k[x 1 , . . . , x n ] with ⟨F ⟩ = ⟨G⟩, a zero-dimensional ideal. D ← { } for i = 1, . . . , m do G i ← {h} with a non-constant polynomial h sampled from k[x n ] ≤d . ▷ Problem 4.1 for j = 1, . . . , n -1 do G i ← G i ∪ {g j } with g j sampled from k[x n ] ≤d . end s ∼ U[n, s max ] ▷ Problem 4.2Sample a unimodular upper-triangular matrixU 1 ∈ k[x 1 , . . . , x n ] s×s ≤d ′ .Sample a unimodular upper-triangular matrixU ′ 2 ∈ k[x 1 , . . . , x n ] n×n ≤d ′ .Sample a permutation matrix P ∈ {0, 1} s×sF i ← U 1 P U 2 G i , where U 2 = [U ′ 2 ⊤ O n,s-n ] ⊤ ∈ k[x 1 , . . . , x n ] s×n . if ≺ ̸ =≺ lex then G i ← FGLM(G i , ≺ lex , ≺) end D ← D ∪ {(F i , G i )} ▷ Reorder terms in F i if ⊀ =≺ lex . endbases and can add some intrinsic structure if any prior information is available. For example, polynomial systems used in a multivariate encryption scheme tend to have only a single solution, and it belongs to the base field (Yasuda et al., 2015) (and thus, are zero-dimensional systems). Ideals generated by such polynomial systems are in shape position and have Gröbner bases of the following form: G = ⟨x n -a n , x 1 -a 1 , . . . , x n-1 -a n-1 ⟩, where a 1 , a 2 , . . . , a n are constants (Ullah, 2012) . Backward approaches allow one to restrict the Gröbner bases in a dataset into such a class. This is not the case with forward approaches. Instead, they can include prior information into non-Gröbner sets, although it is computationally expensive to obtain the corresponding Gröbner bases from them. It is also worth noting that a naive forward approach, which first randomly generates non-Gröbner sets and then computes their Gröbner bases, should be avoided even when the computational cost could be resolved. In many such cases, a Gröbner basis G computed directly from a random non-Gröbner set F will share some polynomials with F while such a behavior is unusual in various cases where one needs to compute Gröbner bases. 
experiments: 
 We now present experimental results on training a transformer for Gröbner basis computation. All the experiments were conducted on a workstation with 16-core CPUs, 512 GB RAM, and a single NVIDIA RTX A6000 GPU. We provide more information on the profile of generated datasets, the training setup, and additional experimental results in App. D. The code will be available soon.We first demonstrate the efficiency of the proposed dataset generation framework. We constructed eight datasets {D n (F p )} n,p for n ∈ {2, 3, 4, 5} and p ∈ {7, 31} and measured the runtime of the forward generation and our backward generation.Generation setup of D n (F p ). The dataset D n (F p ) consists of 1,000 pairs of non-Gröbner set and Gröbner basis in F p [x 1 , . . . , x n ]. Each sample (F, G) ∈ D n (F p ) was prepared using the process given in Alg. 1 with (d, d ′ , s max , ≺) = (5, 3, n + 2, ≺ lex ). The number of terms of univariate polynomials and n-variate polynomials is uniformly determined from [1, 5] and [1, 2] , respectively. Table 1 : Runtime comparison (in seconds/milliseconds) of forward generation (F.) and backward generation (B.) of dataset D n (F p ) of size 1000. The forward generation used either of the three algorithms provided in Sagemath with the libSingular backend. For n = 4, 5, we set a timeout limit to one second (added to the total runtime at every occurrence) for each Gröbner basis computation. The numbers with * and † include the timeout for more than 10 % and 40 % of the runs, respectively. Forward generation. In the forward generation, one may first generate random polynomial sets and then compute their Gröbner bases. However, this leads to a dataset with a totally different complexity from that constructed by the backward generation, leading to an unfair runtime comparison between the two generation processes. As such, the forward generation instead computes Gröbner bases of the non-Gröbner sets given by the backward generation, leading to the identical dataset. We used SageMath (The Sage Developers, 2023) with the libSingular backend.Method F 7 [x 1 , . . . , x n ] F 31 [x 1 , . . . , x n ] n = 2 n = 3 n = 4 n = 5 n = 2 n = 3 n = 4 n = 5 F. (STDIn Tab. 1, our backward generation is significant orders of magnitude faster than the forward generation. A sharp runtime growth is observed in the forward generation as the number of variables increases. Note that these numbers only show the runtime on 1,000 samples, while our training requires a million samples. Therefore, the forward generation is almost infeasible, indicating that the proposed method resolves a critical challenge in the learning of Gröbner basis computation.We now demonstrate that transformers can learn to compute Gröbner bases. To examine the general transformer's ability, we focus on a standard architecture (e.g., 6 encoder/decoder layers and 8 attention heads) and a standard training setup (e.g., the AdamW optimizer (Loshchilov & Hutter, 2019) with (β 1 , β 2 ) = (0.9, 0.999) and the linear decay of learning rate from 10 -4 ). The batch size was set to 8, and models were trained for 10 epochs. Refer to App. D for complete information.Each polynomial set in the datasets is converted into a sequence in the prefix representation. Unlike natural language processing, our task does not allow the truncation of an input sequence to effectively shorten the input sequences because the first term of the first polynomial in F certainly relates to the last term of the last polynomial. To keep the input sequence length manageable for vanilla transformers, we use simpler datasets than those in Sec. 5.1. If the matrices U 1 , U ′ 2 in Alg. 1 are dense, the final polynomials in F tend to have many terms, leading to long input sequences. Thus, we construct datasets using U 1 , U ′ 2 with a moderate density σ ∈ [0, 1] so that the maximum sequence length becomes less than 4096. Specifically, we used σ = 1.0, 0.6, 0.3, 0.2 for n = 2, 3, 4, 5, respectively. The training set has one million samples, and the test set has one thousand samples. Other settings are the same as in Sec. 5.1 Using a more efficient attention mechanism such as (Kitaev et al., 2020; Ding et al., 2023; Sun et al., 2023) to handle larger polynomial sets will be a future work.Tab. 2 shows that transformers trained on the constructed datasets compute correct ≺ lex -Gröbner bases with moderate accuracy. Nevertheless, even when the transformer cannot produce the correct basis, the support8 of each polynomial in the predicted basis tends to be correct. Since there are efficient Gröbner basis computation algorithms if the support of each polynomial in Gröbner basis is accessible (Traverso, 1997) , our experiments successfully show the transformer's potential in accelerating Gröbner computation. Lastly, the last two columns of Tab. 2 suggest that learning with ≺ grvlex may not be as effective as that with ≺ lex .9 In contrast, ≺ grvlex is preferred in computational algebra because of its empirical runtime reduction in Gröbner basis computation. We consider that the well-structured nature of ≺ lex -Gröbner bases of ideals in shape position (c.f. Eq. (4.1)) may be favorable to transformers. Refer to App. D for success and failure examples. Particularly, the failure examples show that the incorrect outputs from transformers are still very reasonable. 
discussion from an algebraic viewpoint and open questions: 
 Without the Gröbner condition, Prob. 4.6 of characterizing the A such that F = AG and ⟨F ⟩ = ⟨G⟩ has been studied in (Busé et al., 2001; Busé, 2001) to provide an algebraic necessary and sufficient condition for the polynomial system of F to have a solution outside the variety defined by G. This condition is expressed explicitly by multivariate resultants. However, strong additional assumptions are required: A, F, G are homogeneous, G is a regular sequence, and in the end, ⟨F ⟩ = ⟨G⟩ is only satisfied up to saturation. Thus, they are not compatible with our setting and method for Prob. 4.1.Prop. 4.8 states that any matrix A ∈ SL n (k[x 1 , . . . , x n ]) satisfies Prob. 4.6. This raises two sets of open questions: (i) are there matrices outside SL n (k[x 1 , . . . , x n ]) satisfying Prob. 4.6? Can we sample them? and (ii) is it possible to efficiently sample matrices of SL n (k[x 1 , . . . , x n ])? To efficiently generate our dataset, we have restricted ourselves to sampling matrices having a Bruhat decomposition (see Eq. ( 4.2)), which is a strict subset of SL n (k[x 1 , . . . , x n ]). Sampling matri- ces in SL n (k[x 1 , . . . , x n ]) remains an open question. Thanks to the Suslin's stability theorem and its algorithmic proofs (Suslin, 1977; Park & Woodburn, 1995; Lombardi & Yengui, 2005) ,SL n (k[x 1 , . . . , x n ]) is generated by elementary matrices and a decomposition into a product of elementary matrices can be computed algorithmically. One may hope to use sampling of elementary matrices to sample matrices of SL n (k[x 1 , . . . , x n ]). It is unclear whether this can be efficient as many elementary matrices are needed (Lombardi & Yengui, 2005) .In the experiments, we restricted ourselves to polynomial sets with a moderate sequence length so that a standard transformer can handle it. Algebraically, this relates to zero-dimensional ideals with small linear dimension (i.e., dimension of k[x 1 , . . . , x n ]/⟨F ⟩, see Def. A.4). To cover more general cases, zero-dimensional ideals with large linear dimensions and positive-dimensional ideals have to be further considered, which needs breakthroughs both in machine learning and algebra. 
conclusion: 
 Solving polynomial systems, or computing Gröbner bases, are fundamental in various applications but known for its doubly exponential time complexity. In this study, we proposed the first training framework of transformers that realizes Gröbner basis computation via learning. The main technical challenge lies in an efficient generation of many pairs of (non-Gröbner set, Gröbner basis) to construct a training set, leading us to address two unexplored algebraic problems: random generation of Gröbner bases and the backward Gröbner problem. We resolved these problems in the case of zero-dimensional radical ideals, which are important in various applications. Our experiments validate that the proposed method achieves an extreme acceleration in dataset generation and that the transformer's ability in Gröbner basis computation. In a broad view, our study indicates that transformers may serve as a solver for NP-hard problems, while most prior studies only address rather easy/moderate-level problems. Besides, our results give a new motivation to computational algebra to consider and address several unexplored problems, posing a new direction and potential interactions of computational algebra and machine learning. A commutative ring R is called a field if it satisfies the following condition 10. for any a ∈ R \ {0}, there exists a -1 such that a * a -1 = a -1 * a = 1. Definition A. 2 (Polynomial Ring (Atiyah & MacDonald (1994) , Chap. 1 §1)). In Definition A.1, k[x 1 , . . . , x n ], the set of all n-variate polynomials with coefficients in k, satisfies all conditions (1)-( 9). Thus, k[x 1 , . . . , x n ] is called a polynomial ring. Definition A.3 (Quotient Ring (Atiyah & MacDonald (1994) , Chap. 1 §1)). Let R be a ring and I an ideal of R.For each f ∈ R, we set [f ] = {g ∈ R | f -g ∈ I}. Then, the set {[f ] | f ∈ R} iscalled the quotient ring of R modulo I and denoted by R/I. Indeed, R/I is a ring with an additive operation + and a multiplicative operation * , where (Cox et al. (2015) , Chap. 5 §3, Thm. 6)). Let F be a set of polynomials in k (Becker et al. (1993) (Becker et al. (1993) , Chap.[f ] + [g] = [f + g] and [f ] * [g] = [f * g] for f, g ∈ R respectively. Definition A.4 (Zero-dimensional ideal[x 1 , . . . , x n ]. An ideal ⟨F ⟩ is called a zero-dimensional ideal if the k-linear space k[x 1 , . . . , x n ]/⟨F ⟩ is finite-dimensional, where k[x 1 , . . . , x n ]/⟨F ⟩ is the quotient ring of k[x 1 , . . . , x n ] modulo ⟨F ⟩. Definition A.5 (Radical ideal (Atiyah & MacDonald (1994), Chap. 1 §1)). For an ideal I of k[x 1 , . . . , x n ], the set {f ∈ k[x 1 , . . . , x n ] | f m ∈ I for a positive integer m} is called the radi- cal of I and denoted by √ I. Also, I is called a radical ideal if I = √ I. Definition A.6 (Syzygy, Chap. 3, §3)). Let F = {f 1 , . . . , f s } ⊂ k[x 1 , . . . , x n ]. A syzygy of F is an s-tuple of polynomials (q 1 , . . . , q s ) ∈ k[x 1 , . . . , x n ] s such that q 1 f 1 + • • • + q s f s = 0. Definition A.7 (Term2, §1)). For a polynomial f = α1,...,αn c α1,...,αn x α1 1 • • • x αn n with c α1,...,αn ∈ K and α 1 , . . . , α n ∈ Z ≥0 , each x α1 1 • • • x αn n is called a term in f . Definition A.8 (Total Degree (Cox et al. (2015) , Chap. 1 §1, Def. 3)). For a term x α1 1 • • • x αn n , its total degree is the sum of indices α 1 + • • • + α n . For a polynomial f , the total degree of f is the maximal total degree of terms in f . Definition A.9 (Term order (Becker et al. (1993) , Definition 5.3)). A term order ≺ is a relation between terms such that 1. (comparability) for different termsx α1 1 • • • x αn n and x β1 1 • • • x βn n , either x α1 1 • • • x αn n ≺ x β1 1 • • • x βn n or x β1 1 • • • x βn n ≺ x α1 1 • • • x αn n holds, 2. (order-preserving) for terms x α1 1 • • • x αn n , x β1 1 • • • x βn n and x γ1 1 • • • x γn n ̸ = 1, if x α1 1 • • • x αn n ≺ x β1 1 • • • x βn n then x α1+γ1 1 • • • x αn+γn n ≺ x β1++γ1 1 • • • x βn+γn n holds,3. (minimality of 1) the term 1 is the smallest term i.e.1 ≺ x α1 1 • • • x αn n for any term x α1 1 • • • x αn n ̸ = 1.Example A.10. The graded lexicographic order ≺ grlex prioritizes terms with higher total degree. 10 For tie-break, the lexicographic order is used, e.g.,1 ≺ grlex x n and x 2 ≺ grlex x 2 3 and x 1 x 2 x 2 3 ≺ grlex x 1 x 2 2 x 3 . (A.1)Term orders prioritizing lower total degree terms as ≺ grlex are called graded term orders.B BUCHBERGER-M ÖLLER ALG. FOR PROB. 4.1Here, we discuss another approach for Prob. 4.1 using the Buchberger-Möller (BM) algorithm (Möller & Buchberger, 1982) . Although we did not adopt this approach, we include this for completeness because many algorithm variants have been recently developed and applied extensively in machine learning and other data-centric applications.Given a set of points X ⊂ k n and a graded term order, the BM algorithm computes a Gröbner basis of its vanishing ideal I(X) = {g ∈ k[x 1 , . . . , x n ] | g(p) = 0, ∀p ∈ X}. While several variants follow in computational algebra (Kehrein & Kreuzer, 2006; Abbott et al., 2008; Heldt et al., 2009; Fassino, 2010; Limbeck, 2013; Kera, 2022) , interestingly, it is also recently tailored for machine learning (Livni et al., 2013; Király et al., 2014; Hou et al., 2016; Kera & Hasegawa, 2018; Kera & Hasegawa, 2019; Kera & Hasegawa, 2020; Wirth & Pokutta, 2022; Wirth et al., 2023) and has been applied to various contexts such as machine learning (Shao et al., 2016; Yan et al., 2018) , signal processing (Wang & Ohtsuki, 2018; Wang et al., 2019; Wang & Deng, 2020) , nonlinear dynamics (Kera & Hasegawa, 2016; Karimov et al., 2020) , and more (Kera & Iba, 2016; Iraji & Chitsaz, 2017; Antonova et al., 2020) . Such a wide range of applications derives from the distinguishing design of the BM algorithm: while most computer-algebraic algorithms take a set of polynomials as input, it takes a set of points (i.e., dataset).Therefore, to address Prob. 4.1, one may consider using the BM algorithm or its variants, e.g., by running the BM algorithm m times while sampling diverse sets of points. An important caveat is that Gröbner bases that can be given by the BM algorithm may be more restrictive than those considered in the main text (i.e., the Gröbner bases of ideals in shape position). For example, the former generates the largest ideals that have given k-rational points for their roots, whereas this is not the case for the latter. Another drawback of using the BM algorithm is its large computational cost. The time complexity of the BM algorithm is O(n • |X| 3 ). Furthermore, we need O(n d ) points to obtain a Gröbner basis that includes a polynomial of degree d in the average case. Therefore, the BM algorithm does not fit our settings that a large number of Gröbner bases are needed (i.e., m ≈ 10 6 ). Accelerating the BM algorithm by reusing the results of runs instead of independently running the algorithm many times can be interesting for future work.C PROOFS Proof. Outside of the Zariski subset part, statements 1-3 are trivial from Alg. 1 and the discussion in Sec.s 4.1 and 4.2. To obtain the desired Zariski subsets, we consider the vector space of polynomials of degree d + 2d ′ or less. We remark that if F i is a ≺-Gröbner basis, its leading terms must belong to a finite amount of possibilities. For a polynomial to have a given term as its leading term, zero conditions on terms greater than this term are needed, defining a closed Zariski subset condition. By considering the finite union of all these conditions, we obtain the desired result.To obtain one pair (F, G), the random generation of G needs O(nS 1,d ), and the backward transform from G to F needs O(s 2 S n,d ′ ) to get U 1 , U 2 and (n 2 + s 2 )M n,2d ′ +d ) for the multiplication F = U 1 P U 2 G. Note that the maximum total degree of polynomials in F is 2d ′ + d. 
 
 Appendix: This section provides the supplemental information of our experiments presented in Sec. 5.In Tab. 1, we tested three algorithms provided in Sagemath with the libSingular backend for forward generation.STD (libsingular:std): The standard Buchberger algorithm. SLIMGB (libsingular:slimgb): A variant of the Faugère's F4 algorithm. Refer to (Brickenstein, 2010) .STDFGLM (libsingular:stdfglm): Fast computation using STD with the graded reverse lexicographic order followed by the FGLM for the change of term orders.We used datasets generated with a density control for training a transformer. The runtime comparison for these datasets is given in Tab. 3. Because of the density control, the forward generation uses .8) 4.0 (±0.7) 5.0 (±0.8) 6.0 (±0.8) 3.0 (±0.8) 3.9 (±0.8) 4.9 (±0.8) 6.0 (±0.8) max deg in F 8.9 (±1.8) 9.8 (±1.2) 10 (±1.0) 10 (±0.8) 8.7 (±1.8) 9.9 (±1.3) 10 (±0) 10 (±0) min deg in F 5.6 (±1.8) 5.9 (±1.9) 6.3 (±1.9) 6.5 (±1.8) 5.4 (±1.9) 6.1 (±1.8) 6.4 (±1.8) 6.6 (±1.6) #terms in F 23 (±9.6) 34 (±10) 45 (±10) 57 (±11) 22 (±9.5) 33 (±10) 45 (±10) 57 (±11) GB ratio [%] 0.10 0.00 0.00 0.00 0.20 0.00 0.00 0.00 size of G 2.0 (±0) 3.0 (±0) 4.0 (±0) 5.0 (±0) 2.0 (±0) 3.0 (±0) 4.0 (±0) 5.0 (±0) max deg in G 4.3 (±1.0) 4.3 (±0.8) 4.4 (±0.8) 4.4 (±0.7) 4.2 (±1.0) 4.4 (±0.8) 4.4 (±0.7) 4.5 (±0.70) min deg in G 3.7 (±1.5) 3.2 (±1.6) 3.0 (±1.7) 2.8 (±1.6) 3.4 (±1.6) 3.6 (±1.6) 3.5 (±1.7) 3.4 (±1.7) #terms in G 8.1 (±2.4) 11 (±3.6) 15 (±4.9) 19 (±6.1) 7.7 (±2.5) 12 (±3.6) 16 (±4.8) 20 (±6. .8) 4.0 (±0.8) 5.0 (±0.8) 6.0 (±0.8) 3.0 (±0.8) 4.0 (±0.8) 5.0 (±0.8) 6.0 (±0.8) max deg in F 8.8 (±1.9) 8.5 (±1.9) 8.4 (±1.9) 8.6 (±1.8) 8.7 (±1.9) 8.8 (±1.9) 8.6 (±1.8) 8.7 (±1.8) min deg in F 5.6 (±1.9) 4.1 (±2.3) 3 (±2.3) 2.6 (±2.3) 5.5 (±1.9) 4.3 (±2.2) 3.2 (±2.4) 2.9 (±2.4) #terms in F 23 (±9.6) 26 (±10) 29 (±10) 34 (±11) 23 (±9.5) 27 (±10) 30 (±10) 35 (±11) GB ratio [%] 0.10 1.60 2.20 0.70 0.10 1.50 1.80 1.10 size of G 2.0 (±0) 3.0 (±0) 4.0 (±0) 5.0 (±0) 2.0 (±0) 3.0 (±0) 4.0 (±0) 5.0 (±0) max deg in G 4.3 (±1) 4.4 (±0.8) 4.4 (±0.79) 4.5 (±0.7) 4.2 (±1.1) 4.4 (±0.8) 4.5 (±0.7) 4.5 (±0.7) min deg in G 3.8 (±1.6) 3.2 (±1.7) 3 (±1.7) 2.9 (±1.7) 3.5 (±1.6) 3.6 (±1.7) 3.5 (±1.7) 3.5 (±1.8) #terms in G 8.1 (±2.5) 12 (±3.6) 15 (±4.9) 19 (±6.1) 7.7 (±2.5) 12 (±3.7) 16 (±4.9) 20 (±6. To examine the transformer's ability to learn Gröbner basis computation, we focus on a standard architecture and training setup. We used a transformer model (Vaswani et al., 2017) with standardOne may regard k[x1, . . . , xn] as the set of all n-variate polynomials with coefficients in k (e.g., k = R).Terms refer to power products of variables, i.e, x α 1 1 • • • x αn n with α1, . . . , αn ∈ Z ≥0 .Refer App. A for the definition.Strictly speaking, the time complexity is here based on the number of arithmetic operations over k.We surcharge notations to mean that the set {g1, . . . , gt} defined by the vector G is a ≺-Gröbner basis.Refer to App. A for the definition.This can happen with probability zero if k is infinite and very low probability over large finite field.The support of a polynomial f refers to the set of terms in f .The training with ≺ grvlex used a dataset that is essentially identical to D2(F7). We simply apply the FGLM algorithm to G and a term reordering to F for each (F, G) ∈ D2(F7).• • • x αn n refers to n i=1 αi. The total degree of polynomial f refers to the maximum total degree of the terms in f .Refer to App. A for the definition.This can happen with probability zero if k is infinite and very low probability over large finite field. 


Decision: In computational algebra, a crucial problem with various applications is the computation of a Gröbner basis of a polynomial system. The computational barrier of this NP-hard problem is the doubly exponential time complexity in the number of variables. In order to overcome this barrier, this paper focuses on the class of zero-dimensional ideals and proposes a Transformer-based approach to compute Gröbner bases. There are two key challenges behind this learning approach: generating a sample set of labeled examples and tokenizing polynomials on infinite fields. These challenges are addressed by providing a computationally efficient solution to the “backward” Gröbner problem and a continuous embedding scheme. Experiments conducted on polynomial systems of different fields validate the effectiveness of this approach.

Based on the reviewers’ comments and the discussion with the authors, the strengths of this paper outweigh its weaknesses. Notably, most reviewers agree on the novelty of this approach. From a theoretical viewpoint, the sampling method obtained by solving the backward Gröbner problem is elegant. From an empirical viewpoint, the experimental evaluation indicating how transformers can learn to compute Gröbner bases is also interesting.

However, several concerns have been raised by reviewers, and I strongly encourage the authors to revise the paper accordingly. Notably:
* Presentation: significant effort has been spent on providing a manuscript that is accessible to the machine learning community by providing clear notation and a smooth flow of algebraic concepts. Yet, it is highly likely that such a study will be read by algebraists. Therefore, some key notions about Transformers should be included in the paper, for example, in Section 5, before embarking on tokenization issues.
* Motivation: regarding the choice of zero-dimensional ideals, the global authors' response is insightful and some arguments in this response should be included in the paper to clarify the choice. 
* Positioning: as the key theoretical result of this paper lies in an efficient way of generating sample sets for supervised learning of Gröbner bases, it might be relevant to re-organize the paper according to this fundamental result. The empirical evaluation with Transformers is also interesting, but the current state-of-the-art in computational learning theory does not provide probabilistic guarantees of the sample/computational complexities of these models.
* Scalability: a discussion about the fact that, for the moment, datasets include only a small number of variables should be included in the experimental section. The authors' clarification of this issue in the rebuttal could be used for this purpose.
* Applicability: The above scalability issue naturally raises the question of whether such a transformer-based approach can be targeted to practical applications (e.g., in Biology or Cryptography). A discussion on this question could be incorporated in the conclusion.

Reviews: review: paper_summary: paper_summary: This paper presents a Transformer based method to compute Gröbner basis, a known NP-hard problem.  The authors focus on polynomials with 0-dimensional radical ideals and propose efficient algorithms to generate training samples of polynomial systems and their corresponding Gröbner basis. The main novelties include (1) an efficient backward transformation algorithm from a Gröbner basis to an associated non-Gröbner set; (2) a hybrid input embedding for both discrete and continuous-value tokens. The transformer, which was trained on millions of Gröbner basis pairs generated by the authors, performed well on some types of rings.
strength_weakness: strength_weakness: * I have serval questions about the choice of the 0-dimensional ideal as the scope of the study : 
(1) the authors first mentioned “…, and thus, we should focus on a particular class of ideals and pursue in-distribution accuracy” and then claimed “… and thus, we focus on the generic case and leave the specialization to future work”.  Do you regard this choice as a “particular” or “general” case of the Gröbner basis computation? 
(2) What is motivation of focusing on 0-dimensional ideals (since it is already mentioned that this work is meant to be general)? Is it purely because of the sampling easiness? Also, what are the difficulties of working on the more general Gröbner basis computation problem? 
(3) The discussion of, whether Transformers, or more generally, ML methods, can help NP-hard problems generally or only in-distribution, is interesting. There are some results from the SAT field that end-to-end ML models may be able to generalize to out-of-distribution problems [1]. As you claim here “in-distribution accuracy” is what we are after, it is important to include some experiments across different applications, to support this claim. 

* The hybrid input embedding for both discrete and continuous-value tokens is claimed to be one of the paper’s contributions. However, this idea is not new, as other research has explored similar problems (e.g.,  [2, 3, 4]). The authors do not provide a review of existing methods or distinguish their approach from these works. 

It is interesting to note that many incorrect results are reasonable. This suggests that incorporating the Transformer method with planning (5) or RL (6) may help the performance through feedbacks. 


Reference
[1] Cameron, Chris, et al. "Predicting propositional satisfiability via end-to-end learning." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.
[2] Charton, François. "Linear algebra with transformers." arXiv preprint arXiv:2112.01898 (2021).
[3] Golkar, Siavash, et al. "xval: A continuous number encoding for large language models." arXiv preprint arXiv:2310.02989 (2023).
[4] McLeish, Sean, et al. "Transformers Can Do Arithmetic with the Right Embeddings." arXiv preprint arXiv:2405.17399 (2024).
[5] Kamienny, Pierre-Alexandre, et al. "Deep generative symbolic regression with Monte-Carlo-tree-search." International Conference on Machine Learning. PMLR, 2023.
[6] Jha, Piyush, et al. "RLSF: Reinforcement Learning via Symbolic Feedback." arXiv preprint arXiv:2405.16661 (2024).
questions: questions: * With the proposed sampling methods based on shape position and Cauchy module, how diverse is this generated set? Does these generating methods further restrict the scope less than the 0-dimensional radical ideals?
limitations: limitations: It is not clear whether this work can be generalized to beyond 0-dimensional ideals.
paper_summary: paper_summary: Gröbner bases are a tool of fundamental importance in the field of computational algebra. Unfortunately known algorithms for computing Gröbner bases are very ineficient, having a running time that is double-exponential on the number of variables. In this work, the authors propose a machine-learning based approach for the computation problem. Instead of devising an algorithm that is always guaranteed to correctly output a Gröbner basis, the authors propose a learning algorithm based on transformers. 

To address this learning problem, the authors address other interesting problems such as random generation of Gröbner bases and the Backward Gröbner problem.
strength_weakness: strength_weakness: The main weakness, in my opinion, is that the paper does not attempt to provide a characterization of a subclass of polynomial systems that can be efficiently solved using the transformed-based approach. Therefore it is difficult to have an idea of what properties the input polynomial system must satisfy in order for the approach to give reasonable results. 

The number of variables considered in the experiments (n=2,3,4,5) is way to low to give an idea about the complexity of the problem.  For this number of variables it is not clear whether the machine learning method provides any advantage at all with respect to traditional computational algebraic approaches. 

The theoretical part of the paper is much more concentrated on the issue of random generation of Gröbner bases than on the learning part. For this reason, it is my impression that the authors are putting too much emphasis on the part of the paper where results are not very satisfactory (the learning theory part). The paper would be more solid if concentrated on random generation of Gröbner bases with the learning part as an interesting application.
questions: questions: 1) What is the largest number of variables for which the machine learning method gave interesting results? 

2) How does the accuracy of the model decay with the number of variables? 

3) What is the relation between the number of variables and the time necessary to train the model?
limitations: limitations: Yes.
paper_summary: paper_summary: The paper proposes to learn to compute Gröbner bases (as the title says). This includes two important problems. 1) Generating the dataset and 3) Finding an appropriate encoding of the problem to feed into a transformer architecture. That is finding an encoding for a system of polynomials to be solved.

The paper gives adequate solution for both of these issues and implements it,
strength_weakness: strength_weakness: The method does not provide any guarantees. In this regard it is then not entirely clear what the benefit would be of having "hints at the right solution".
questions: questions: 1) Could the authors comment on my point raised in the "weakness". Specifically, how do you envisage to use learned Gröbner basis to be useful for any downstream tasks? Would you use them as a heuristic to exactly solve polynomial systems?

2) Why did you limit the rings to Q,R F_p. Why not N or p-adic numbers?
limitations: limitations: Exemplary!
paper_summary: paper_summary: This article investigates the use of machine learning techniques to compute Gröbner basis of polynomial systems. This problem consists in, given a term order and a finite set of polynomials $f_1, \cdots, f_m$, to compute another set of polynomials $g_1, \cdots, g_m$ that have the following desirable properties $(P)$: 

$(P)$ the $g_i$'s all belong the ideal generated by $f_1, \cdots, f_m$, and such that any leading term in the ideal generated by the $f_i$'s is generated by the $g_i$'s.

To do so, the authors propose a method to first sample training data, which was previously problematic. Then, after embedding the set of polynomials $f_i$'s and $g_i$'s that they embed (after tokenization and a hybrid embedding technique that they detail in the appendix), they make use of a transformer to output the $g_i$'s given the $f_i$'s.
strength_weakness: strength_weakness: I do not see a major weakness of this article. It constitutes a serious study of the use of machine learning advancements for computational algebra. One comment (not a weakness): Section D, there is a reference to a Table that is missing (line 728).
questions: questions: - Line 115, the authors mention the notion of reduced Gröbner basis. Do they mean normalized and in shape position?  The authors may want to clarify this. 

- The authors may want (if they think this is relevant) to introduce some short additional comment for non-experts about the Gröbner basis definition line 109. This would help to understand the motivation of the definition. Namely: Understanding and finding solutions of a polynomial system can be adressed via studying the ideal generated by the fi's. For example, if one is able to find if the constant 1 is in the ideal generated by the fi's, then there is no solution for the system. It turns out the condition on the leading terms in the defintion are equivalent to, given a polynomial h, that the remainder after multivariate division of h by the gi's to be zero if and only if the h is in the ideal generated by the fi's (see for instance Definition 1 in [70]). 
Hence one can answer the above question (if 1 is in the ideal) -- as well as others-- by performing a multivariate division algorithm taking on 1 and the Gröbner basis. It the output is 0, then 1 belong to the ideal and there is no solution.
limitations: limitations: The authors clearly explain the apparent limitation of their work, in particular to which extent the experiments they conducted are successful. They report extensive experimental results in the appendix, in particular failed examples.
paper_summary: paper_summary: This paper provides a machine learning algorithm to compute Gröbner bases of 0-dimensional ideals in shape position. 
To address the backward Gröbner problem, the authors propose an algorithm based on 1) random generation of Gröbner bases by sampling univariate polynomials related to the shape position, then on 2) random generation of a polynomial matrix to generate non-Gröbner sets. 
The associated algorithm running time is derived in Theorem 4.8. 
After generating tuples with the two above-mentioned steps, the authors rely on Transformers for learning to compute Gröbner bases.
strength_weakness: strength_weakness: - The paper contains many typos, grammatical mistakes and missing articles. The authors are invited to carefully rewrite the paper to increase the overall quality. Two examples (among many) are in p6, l255: "Consider polynomial ring", "Given dataset size". 

- The training approach, via Transformers, does not come with any theoretical guarantees related to global/local convergence, running time, error bounds. No explanation is provided regarding the cases where the method works or fails. The ML algorithms related to transformers are mostly described in the appendix and only vaguely in the main text. 

- The paper does not address concrete benchmarks of target applications (e.g. in cryptography or biological systems) where computing Gröbner bases is out of reach or very time consuming. Providing such experiments would definitely make the approach credible. 

- Many important aspects (theorem proofs, limitations) are postponed to the appendix. Overall I believe that this work, possibly sound and surely interesting, would be worth publishing but the current conference format (coming together with a short allocated review time) and focus are certainly not the best fit.
questions: questions: - The framework is limited to 0-dimensional ideals in shape position. It is well known that the shape position assumption is not so strong but the 0-dimensional ideal one is very strong. 
Random search applied to higher-dimensional ideals would be more challenging and interesting. Could the authors provide more insights to address such problems?

- Could the authors derive a killer application for which their framework would provide new results or results obtained in a more efficient way than with the forward approach?
limitations: limitations: - There is no section dedicated about the limitations of this work in the main text. Section H is not part of the main text.

Comments: title: Answer to authors' rebuttal
comment: Thanks for the clarifications. I will keep my current recommendation.
I thank the reviewer for their detailed overall rebuttal and intend to maintain my score.

(and yes N is not a field, apologies)
Thank you for your reading and support!
Thanks for your reply. I will maintain my score and will argue in favor of this work if needed.
Thank you for reading our rebuttal and responding promptly. 

We again clarify that your comments/questions are very critical to improving the current work and also directing future work. We believe that we've addressed your comments/questions. Particularly, it is important for us that you kindly comprehend the scope of this study and its value within this scope, with which your evaluation of our work hopefully increases. 

We'd be happy to engage further.
Thanks for your comments, I will maintain my score.