Learning to compute Gröbner bases
Authors: Hiroshi Kera
Yuki Ishihara
Yuta Kambe
Tristan Vaccon
Kazuhiro Yokoyama
Venue: NeurIPS 2024 poster (2024)
Keywords: Transformer; Gröbner bases; Computational algebra
Primary area: machine_learning_for_other_sciences_and_fields
TL;DR: We show the learnability of Gröbner basis computation and raise new algebraic and machine learning challenges.

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.

Learning to compute Gröbner bases
Hiroshi Kera" Chiba University, Zuse Institute Berlin
Yuki Ishihara
Nihon University
ishihara, yuki
@nihon-u. wuw.iiiiiiinnnnnnn
jp
kera@chiba-u. jp
Yuta Kambe
Tristan Vaccon
Mitsubishi Electric
Limoges University
kambe, yuta@bx. wwwp://wwww.ssssseerrrc..oo.....
tristan tristan. www.coaonnnnnni.cci.....m fr
Kazuhiro Yokoyama
Rikkyo University
kazuhiro@rikkyo..acc. ac.
Abstract
Solving polynomial system, computing associated Gröbner basis, has been a fundamental task in computational algebra. However, it 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 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 O-dimensional radical ideals, the ideals appearing 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 crucial challenge in learning to compute Gröbner bases, and Gröbner computation is learnable in particular class.
Introduction
Understanding the properties of polynomial systems and solving them have been fundamental problem in computational algebra and algebraic geometry with vast applications in cryptography [8]
93]. control theory (71). statisties [27] 41). computer vision 778,, systems biology [60], and so
forth. Special sets of polynomials called Gröbner bases [6] play a key role to this end. In linear
algebra, the Gaussian elimination simplifies or solves system linear equations by transforming its coefficient matrix into the reduced row echelon form. Similarly, a Gröbner basis can be regarded as reduced form of given polynomial system, and its computation elimination to general polynomial systems. However, computing a Gröbner basis is known for its notoriously bad computational cost theory and practice. It an NP-hard problem with the doubly exponential worst-case time complexity in the number of variables (29 67), Nevertheless, because of its importance, various algorithms have been proposed computational algebra obtain Gröbner bases in better runtime. Examples include Faugère's F4/F5 algorithms B3 34 and M4GB [66].
generalization of the Gaussian
"corresponiing author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this study, we investigate Gröbner basis computation from a learning perspective, envisioning it as practical compromise to address large-scale polynomial system solving and understanding when mathematical algorithms are computationally intractable. The learning approach does not require explicit design of computational procedures, and we only need to train a model using large amount of (non-Gröbner set, Gröbner basis) pairs. Further, if we restrict ourselves to particular class of Gröbner bases (or associated ideals), the model may internally find some patterns useful for prediction. The success of learning indicates the existence of such patterns, which encourages the improvement of mathematical algorithms and heuristics. Several recent studies have already
addressed mathematical tasks via learning, particularly using Transformers [1 [9 [58]. For example, [58] showed that Transformers can learn symbolic integration simply by observing many (df .f) pairs in training. The training samples are generated by first randomly generating f and computing its derivative dff /dx and/or by the reverse process.
However, a crucial challenge in the learning of Gröbner basis computation is that it is mathematically unknown how efficiently generate many (non- non-Gröbnnr set, Gröbner basis) pairs. We need an efficient backward approach (i.e., pellutionnto-problee forward approach (i.e.. problem-to-solueee
computation) because, discussed above, the computation) is prohibitively expensive. To this end, we frame two problems: (i) random generation of Gröbner bases and (ii) a backward transformation from a Gröbner basis to an associated non- non-Gröbner set. To our knowledge, neither of them has been addressed in the study of Gröbner bases because of the lack of motivations; all the efforts have been dedicated to the forward computation from a non- Gröbner set to Gröbner basis.
Another challenge in the learning approach using Transformers lies in the tokenization of polynomials on infinite fields, such as R. and Q. To cover wide range of coefficients, one has to either prepare numerous number tokens or split number into digits. The former requires large embedding matrix, and the latter incurs large attention matrices due to the lengthy sequences. To resolve this, we introduce continuous embedding scheme, which embeds coefficient tokens by small network and avoids the tradeoff between vocabulary size and sequence length. The continuity of the function realized by the network naturally implements the continuity of the numbers in the embedding.
We summarize the contributions as follows.
We investigate the first learning approach to the Gröbner computation using Transformers and experimentally show its learnability. 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-rradom generation of Gröbner bases and backward Gröbner problem and propose efficient methods to address them in the O- dimensional case. The problems essential to the learning approach but also algebraically interesting and need interaction between computational algebra and machine learning.
We propose a new input embedding to efficiently handle a large range of coefficients without the tradeoff between the size of the embedding matrix and attention maps.
Our experiments show that the proposed dataset generation is highly efficient and faster than baseline method by a few orders of magnitude. Further, we observe a learnability gap between polynomials on finite fields and infinite fields while predicting polynomial supports are more tractable.
2 Related Work
Gröhner basis computation. Gröbner basis is one of the fundamental concepts in algebraic geometry and commutative ring theory 224 39 By its computational aspect, Gröbner basis is very useful tool for analyzing the mathematical structures of solutions of algebraic constraints. Notably, the form of Gröbner bases is suited for finding solutions and allows parametric coefficients, and thus, it is vital to make Gröbner basis computation efficient and practical in applications. Following the definition of Gröbner bases in [16], the original algorithm to compute them can be presented as (i) create potential new leading terms by constructing S 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 work has been developed to surpass this algorithm. There are four main strategies: (a) avoiding unnecessary S-polynomials based on the F5 algorithm and the more general signature based algorithmss 34]. Machine learning appeared for this task in 73 (b) More efficient

---

reduction using efficient linear algebraic computations using [33 and the very recent GPU-using [2] (c) Performing modular computations. following 70. prevent coefficient growth during the
computation. (d) Using the structure of the ideal, e.g. 13 35 for change of term ordering for O-dimensional ideals or [83] when the Hilbert function known. In this study, we present the fifth strategy: (e) Gröbner basis computation fully via learning without specifying any mathematical procedures.
Transformers for mathematics. Recent studies have revealed that Transformers can be used for mathematical reasoning and symbolic computation. The training only requires samples (i.e., problem-solution pairs), and no explicit mathematical procedures need to be specified. In [58). the first study that uses Transformers for mathematical problems is presented. It 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 (2), polynomial simplification [3] linear algebra 19 20). symbolic regression [4, 26 44 45), Lyapunov function design [4] and attacking the LWE cryptography [61 191. In (75), comprehensive experiments over various mathematical tasks are provided. In contrast to the aforementioned studies, we found that Gröbner basis computation, an NP-hard problem, even has an algebraic challenge in the dataset generation. This paper introduces unexplored algebraic problems and provides an efficient algorithm for a special but important case (i.e., O-dimensional ideals), thereby realizing an experimental validation of the learning of Gröbner basis computation.
3 Notations and Definitions
We introduce the necessary notations and definitions in this Section. The reader interested in a gentle introduction to Gröbner basis theory can refer to the classical book (25). For their comfort, we have moreover compiled most elementary additional definitions and notations in App. A
We consider a polynomial ring k[
xn,] with a field & and variables .i....,Ixp For a set the ideal generated by F denoted by (F)). Once term order on the terms of k(z1,.... _n. is fixed, one can define leading terms and Gröbner bases.
F C .(.i.......
: ]n]],
Definition 3.1 (Leading term). Let F= (f,,..,,fs. C k[a), In. and let - be a term order. The leading term (fa) of fi is the largest term in fi in ordering <. The leading term set of F is LT(F)= = (LT(f))..... LT(f))}-
Definition 3.2 (Gröbner basis). Fix a term order x. A finite subset G of an ideal I is said to be Grröber basis of I if (LT = (LT(I)).
The condition (LT(G)) divided by the leading term LT(g) of an element E G. It gives complete test whether given polynomial h is in I or not by polynomial division with G, similar Gaussian elimination by a basis of a vector space. The remainder is 0 means that h E T, and otherwise means that h g T. This related to finding solutions. Roughly speaking,
(LT(T)) means that for any element h E I, the leading term LT(h) is
E I = (f1,.... fa), then we have a form h i=l f, and the system fi (1 (I,)) ... = ( n.n = 0 shares solutions with the equation ((.,,..., 2n) = O.
Note that (LT(G)) C (LT(1)) is trivial from G C 1. The nontriviality of the Gröbner basis lies in (LT(G)) S (LT( 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 (25] guarantees that every ideal I * {0} has a Grübner basis. Moreover, using the multivariate division algorithm, one gets that any Gröbner basis G of an ideal generates I. We are particularly interested in the reduced Gröbner basis G of
7 (F), which is unique once the term order is fixed.
Intuition of Gröbner bases and system solving. Let G = (9I...., 9t 3 be Gröbner basis of an ideal (F) = (fi..... f.). The polynomial system 91 (21, ..fi,,..,,,,, Fn) _... (x ... 2x,)) simplified form of fi (I1...... .n.) =
is a fs(x1...., In) = 0 with the same solution set. With the term order <tex, G has a form 91 E k( Jn), 92 E ki ki.r.g...... [(]l:::...,,)).................. ..)....,.e It E k(zm,...... 2n]] with n1 < r22 - ... < nı, which may be regarded as the "reduced row echelon form" of polynomial system. In our particular case (i.e., O-dimensional ideals in shape position; ef. Sec. (4.2), we have (ni, ,,,...,,7., ne) = (1, 2, .......7 ..). Thus, one can obtain the solutions of the polynomial system using
3

---

a backward substitution, i.e., by first solving univariate polynomial 9t. next solving bivariate polynomial It-1, which becomes univariate after substituting the solutions of gt. and so forth.
Other notations. The subset flz1,....,,y C , ,.] denotes the set of all polynomials of total degree at most d. For polynomial matrix A E k(a1..... Fn ==]=,,, its determinant is given by (A)(A) E k(21,,...,INN The set F, with prime number p denotes the finite field of order The set ST k ,,, Fn)) denotes the set of upper- triangular matrices with all-one diagonal entries (i.e., unimodular upper-triangular matrices) with entries in k( ,T The total degree of [(, is denoted by deg(f).
Fnl.
4 New Algebraic Problems
Our goal is to realize Gröbner basis computation through a machine learning model. To this end, we need a large training set {(F,, G=) with finite polynomial set F; C k(zi,..., Inn and Gröbner basis G2 of (Ft). As the computation from F; G, is computationally expensive in general, we instead resort to backward generation (i.e., solution-to -autionnto-problem problem process); that is, we generate a Gröbner basis G2 randomly and transform to non- non-Gröbner set Ft.
What makes the learning of Gröbuer basis computation hard is that, to our knowledge, neither (i) 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. Its primary interest has been instead posed 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 them. Formally,
address the following problems for dataset generation.
Problem 4.1 (Random generation of Gröbner bases). Find a collection G = [G:] with the reduced Gröbner basis G; C k(x1,..., Tn.] of (Gi), i = = 1,..., m. The collection should contain diverse buses, and we need an efficient algorithm for constructing them.
Problem 4.2 (Backward Gröbner problem). Given Gröbner basis G C k(a1,....,, find find a col- lection F = [Fi) of polynomial sets that are not Gröbner bases but (F.) = (G) for i I,... H. The collection should contain diverse sets, and we need an efficient algorithm for constructing them.
Problems 4.1 and 4.2 require the collections F to contain diverse polynomial sets. Thus, the algo- rithms for these problems should not be deterministic but should have some controllable randomness. Several studies reported that the distribution of samples in a training set determines the generalization ability of models trained on it [19 However, the distribution of non- non-Gröbner sets and Gröbner bases is unexplored and challenging object of study. It can be another challenging topic and goes beyond the scope of the present study.
4.1 Scope of this study
Non-Gröbner sets have various forms across applications. For example, in cryptography (particularly post-quantum cryptosystems), polynomials are restricted to dense degree-2 polynomials and generated by an encryption scheme [93. On the other hand, in systems biology (particularly, reconstruction of gene regulatory networks), they are typically assumed to be sparse [59]. In statistics (particularly algebraic statistics), they are restricted to binomials, i.e., polynomials with two monomials [4]] 79).
As the first study of Gröbner basis computation using Transformers, do not focus particular application and instead address a generic case reflecting a motivation shared by various applications of computing Gröbner basis: solving polynomial systems understanding ideals associated with polynomial systems having solutions. Particularly, we focus on O-dimensional radical ideals, a special but fundamental class of ideals.
Definition 4.3 (0-dimensional ideal). Let F be set of polynomials in k[æ xy]. ]. An ideal (F) is called a O-mimensional ideal if all but a finite number of terms belong to LT((F)).
In fact, the number of terms not belong to IT, f.)) is an upper bound of the number of solutions of the system fi fi Inn) ., fa)) implies the finiteness of the number of solutions.
(a Ix) 0. In particular, the finiteness of the number of terms not belong to (JT( ....,,,,
This is the reason why we call such ideals "O-dimensional" ideals in Def. 4.

---

O-dimensional ideals are the fundamental ideals in the study of pure algebra. This is partly because of the ease of analysis. As Def. A.. shows, O-dimensional ideals relate to snite-dimensionall vector spaces, and thus, analysis and algorithm design can be essentially addressed by matrices and linear algebra.
Also ideals in most practical scenarios are known to be O-dimensional. For example, a multivariate public-key encrypted communication (a candidate of post-quantum cryptosystems) with public polynomial system F' over a finite field IF,, will be broken if one finds any root of the system FU F - 21...... 2% Fn1) One should note that the ideal (F U {x #1....... x% 1n is O-dimensional [84] Sec. 2.21. Generically, O-dimensional ideals defined from polynomial systems having solutions are radica (i.e., non non-radical ideals are in a zero- cero-measure set in the Zariski topology). The proofs of the results in the following sections can be found in App. C Hereinafter, the sampling of polynomials is done by uniform sampling of coefficients from prescribed range.
is also worth noting that Transformers cannot be an efficient tool for general Gröbner basis computation, and thus, we should focus on particular class of ideals and pursue in-distribution accuracy. This is evident from the facts that Gröbner basis computation is NP-hard and that machine learning models perform best on in-distribution samples and do not generalize perfectly. Fortunately, unlike standard machine learning tasks (e.g., image classification task), users can frame their problems beforehand (i.e., they know what types of polynomials they want to handle), and they can collect as many training samples as they want if an efficient algorithm exists. As mentioned above. the form of non-Gröbne sets varies across applications, and thus, we focus on the generic case and leave the specialization to future work.
4.2 Random generation of Gröbner bases
We address Prob. 4.1 using the fact that O-dimensional radical ideals are generally in shape position. Definition 4.4 (Shape position). Ideal I C k[x1 ......... 2n. is called in shape position if some univariate
polynomials h, .I......
: E 1o [,,,, form the reduced <texe Gröbner basis of I as follows.
G (h,21 21 - 91, In-1 9n-1)
(4.1)
As can be seen, the -tex- Grööber basis consists of a univariate polynomial in 2.n and the difference of univariate polynomials in vr, and a leading term H; for < n. While not all ideals are in shape position. O-dimensional radical ideals are almost always in shape position: if an (fi...., fe) C k[T a O-dimensional and radical ideal, a random coordinate change (y/1...., Mo) = (#1...., x. 2..). R with a regular (i.e., invertible) matrix R E kn yields fi...., f. E klyi,.... :nll and the ideal (y1, (.1,-..; yn) generally has the reduced -tex Gröbner basis in the form of Eq. (4.1) (cf. Prop. 14
Inl
With this fact, an efficient sampling of Gröbner bases of O-dimensional radical ideals can be realized by sampling polynomials in k[zn], ie., h, g1. ... In-1 with h * O. We have to make sure that the degree h is always greater than that of 91..... In-1, which is necessary and sufficient for G' to be reduced Gröbner basis. This approach involves efficiency and randomness, and thus resolving Prob, 4.1 Note that while our approach assumes term order -tex. if necessary, one can use an efficient ofange-of-orderinn algorithm, e.g., the FGLM algorithm [35]. The cost of the FGLM algorithm is (n deg(h) (h))) based on the number of arithmetic operations over k. Besides the ideals in shape position, also consider the Cauchy module in App. B, which defines another class of O-dimensiiona ideals.
4.3 Backward Gröbner problem
To address Prob. 4.2 we consider the following problem.
Problem 4.5. Let I C k(z be O-dimensional ideal, and let G = (gi....,gt) T E
k(zz..... 2,,1" be its -Gröbner basis with respect term order -1 Find a polynomial matrix A E 2,, 1xt giving a non-Gröbner set F (ft...., AG such that (F") GG).
2See App. A for the definition.
We surcharge notations mean that the set (6i, (gi.... ge3 defined by the vector G is R-Gröbner basis.
5

---

Namely, we generate set of polynomials F = (fi...., fa) from G = (g1......9) by fr = Ej=1 4ig9; for i = ,, where dij 11(2,....,,, Inn] denotes the (i, (i,j)-th entry of A. Note that (F) and (G)) are generally not identical, and the design of A such that (F) (G) is of our question.
similar question was studied without the Gröbner condition in [17 They provided an algebraic necessary and sufficient condition for the polynomial system of F to have solution outside the variety defined by G. This condition expressed explicitly by multivariate resultants. However, strong additional assumptions
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
Our analysis gives the following results for the design to achieve (F) (G) for the O-dimensional case (without radicality or shape position assumption).
Theorem 4.6. Let G (g1....,, T
.T)) be Gröbner basis of O-dimensional ideal in k| Fnl. Let F = (J1...., Ss) = AG with A E k([1,-... .,n ]xx
1. 1f = -G), it implies 2
2. If A has a left-inverse in klr 1xx, (F) = (G) holds.
3. The equality (F) = (G) holds if and only if there exists a matrix B E k(z)..... Fn xx such that each row of BA Fg is syzyg H
off. where Fg is the identity matrix of size t.
The first statement of Thm. 4.6 argues that polynomial matrix A should have at least rows. For an ideal in shape position, we have a <tex-Gröbnee basis G of size n, and thus, A is a square or tall matrix. The second statement shows sufficient condition. The third statement provides necessary and sufficient condition. Using the second statement, we design a simple random transform of Gröbner basis non-Gröbner set without changing the ideal.
We now assume <=< and O-dimensional ideals in shape position. Then, G has exactly n generators. When s n, have the following.
Proposition 4.7. For any A kl xn," j"x" with det(AA E 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. Such A can be constructed using the Bruhat decomposition:
A U, PU2,
(4.2)
where U1, U2 E ST(n, k[ Fn.)) are upper-triangular matrices with all-one diagonal entries (i.e., unimodular upper-triangular matrices) and P E {0, 1] denotes a permutation matrix. Noting that A satisfies A = En. we have (AG) = (G) from Thm. 4.6 Therefore, random sampling (U1. U2 P) of unimodular upper-triangular matrices U1, U2 and a permutation matrix resolves the backward Gröbner problem for
We extend this idea the case of s >> n using a rectangular unimodular upper- trianulai matrix:
(0.0%
Ui
U2
E k(01, ................................ Jn 8xn
(4.3)
where U32 E (fri,,/ai.... In) and O Oa-n, E k(a),.... Nn. xr) (e-n)xn is the zero matrix. The permutation matrix is now P E 1)ax, Note that U2G already gives non-Gröbner set such that (U2G) = (G); however, the polynomials in the last s n entries of U2G are all zero by its construction. To avoid this, the permutation matrix P shuffles the rows and also U1 to exclude the zero polynomial from the final polynomial set.
To summarize, our strategy is to compute == U2 PUZG, which only requires a sampling of (ss2) polynomials in k(x ... I..]. and O(n² + )-imes multiplications of polynomials. Note that even in the large polynomial systems in the MQ challenge, a post-quantum cryptography challenge, we have n 100 and 200 9
'Refer to App. A for the definition.

---

4.4 Dataset generation algorithm
The combination the discussion in the previous sections gives an efficient dataset generation algorithm (see Alg. [ a pseudocode).
Theorem 4.8. Consider a polynomial ring k(z1...., En] Given the dataset size maximum
degrees d, > O, maximum size of non-Gröbner set smax 2 n, and term order x, Alg. 1 returns a collection D {(Fi, G.) with the following properties: For all i= ,,...,
1. G = and FFll S mmax-
2. The set G; is the reduced 2-Gröbner basis of (F:). The set P; is not, unless Gi, Gú,Ui,U5 U1, P are all sampled in a non-trivial Zariski closed subser
3. The ideal (Fi) = =G.)) is a O-dimensional ideal in shape position.
The time complexity is O + S²Sn..'
+ d' + (n² 82 Mn.24+a+)) when -1= where Sn,d denotes the complexity of sampling n-variate polynomial with total degree most d, and Ma, denotes that of multiplying two n-variate polynomials with total degree at most If 2 Alxx. Ommdd) 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 bases and can add some intrinsic structure if any prior information is available. For example, a variate encryption scheme encapsulates secret key information in the solution of polynomial system with single solution in base field [93] The ideal associated with such system O-dimensional and in shape position; namely, its Gröbner basis has the following form:
G = (I,, an; 11 ai,.... In an-1),, 1), where d1 .2...... (n are constants 884 The backward approach allows one to restrict the Gröbner bases in a dataset into such a class.
This is not the case with forward approaches. While they may include prior information into non- Gröbner sets, is computationally expensive to obtain the corresponding Gröbner bases. It is also worth noting that naive forward approach, which randomly generates non-Gröbner sets and computes their Gröbner bases, should be avoided even if it were computationally tractable because, for example, if the Gröbner basis of such F is generally {1) when [F] n.
5 Hybrid Input Embedding
Transformers efficient learner of seguence-to-sequuence functions. They receive and generate a sequence of tokens. In our context, for example, {u² 10, y) can be tokenized as [x, 2, +, -10, <sep>, yl. sequence of tokens. The vocabulary set V is the collection of all possible tokens. Each token E V has a predesignated token ID i(s) E N. and the input embedding layer of Transformer associates them with the i(s)-th row of the embedding matrix WE E RDVXD where D the embedding dimension. The embedding matrix is updated during training, and eventually, we have a nice vector representation for each token.
However, this approach requires large embedding matrix to handle wide range of number tokens The number tokens dominate the vocabulary set, and Transformers have to learn the relationship of the number tokens from scratch during the training. At the inference, if the given numbers of range, the model cannot work. In our case, this inconvenient, particularly when the coefficient field is k Q. For example, let F = { (-5/3y² y 1/2, 7/2xy2 2 33x 2). which we obtained from random sampling with some upper bounds on the degree, number of terms, and integers appearing in numerators and denominators. Even the simplicity of F. its reduced -röy-eröbner 158760 42741ly + 612912 012912/427411
basis has a polynomial of gi = x + (69520//424411 we tokenize a/b as [a, /, b). we need to prepare more than a million integer tokens. Noting that 91 R + 1.33y² 0.37y + 1.43, it is more reasonable to handle coefficients as real values and also implement the inductive bias on the continuity of numbers the embedding.
If
'This can happen with probability zero is infinite and very low probability over large finite field. 'We may tokenize number by the digits (e.g., 123 by [1, 2, 3)). but this makes input sequences long and affects the quadratic memory cost of attention mechanism. See [19] for the effect of number tokenization.
7

---

Table 1: Runtime comparison (in seconds) of forward generation (F.) and backward generation (B.) of dataset (Q) of size 1,000. The forward generation used either of the three algorithms provided in SageMath with the libSingular backend. We set timeout limit to five seconds (added to the total runtime at every occurrence) for each Gröbner basis computation. The numbers with t and include the timeout for more than 13% and 25% of the runs, respectively (cf. Tab. for the success rate).
Method
π = 2
12 = 4
n 5
R. (STD)
4.20
216.3
740.1
1411.1
F. (SLIMGB)
4.29
183.4
697.5t
1322.7
(STDFGLM)
7.22
8.29
21.0
164.3
B. (ours)
5.23
3,46
7.05
7.91
We propose hybrid input embedding that accepts both discrete token IDs and continuous values. Let [s1,..., .1.] ] to sequence of tokens. Some of these tokens are in V and otherwise in R. For those in V/ the standard input embedding based on the embedding matrix is applied. For the others, small ferwaforward network fE + RR. is applied. Transformer with the proposed embedding should equip regression head for these continuous tokens. This allows us to handle any number as single token without the explosion of the vocabulary set (i.e., embedding matrix). As feed-forward networks are continuous function, they naturally implement the continuity of numbers; two close values $1, 82 E R are expected to be embedded in similar vectors. The hybrid input embedding has two advantages. First, claimed above, are longer suffering from the large embedding matrix for registering many number tokens and can naturally implement the continuity bias. Second, We do not have the "out-of-range" issue. Further, we can scale the coefficients of given polynomials globally so that they match our training coefficient range ? Refer to App. D for the details.
6 Experiments
We now present the efficiency of the proposed dataset generation method and the learnability of Gröbner basis computation and NVIDIA RTX A6000ada GPUs. The training of model takes less than a day single GPU. More information on the profile of generated datasets, the training setup, and additional experimental results are given in Apps. andd]
[] All the experiments were conducted with 48-core CPUs, 768GB RAM,
6.1 Dataset generation
First, we demonstrate the efficiency of the proposed dataset generation framework. We constructed 16 datasets D, (k) for E 3,, 4, 5) and & E F1. Q, ] and measured the runtime of the forward generation and our backward generation. The dataset (k) consists of 1,000 pairs of non- non-Gröbner set and Gröbner basis in & kfz1...... ...] of ideals in shape position. Each sample (F, G) E DD (k) was prepared using Alg. 1 with (d, d', Smax: x) (5,3, n + 2, <tex). The number of terms of univariate polynomials and n-variate polynomials is uniformly determined from [1,5] and [1, 2]. respectively. When & = Q, the coefficient a/b are restricted to those with a, b E (-,,....5) 5} for random polynomials and a, b E {-100,... .., 100} for polynomials in F. In the forward generation, one may first generate random polynomial sets and then compute their Gröbner bases. However, this leads to dataset with 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 [82 with the libSingular backend. As Tab. [ shows, 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 training typically requires millions of samples. Therefore, the forward generation is almost infeasible, and the proposed method resolves bottleneck in the learning of Gröbner basis computation.
backward generation is few orders of magnitude faster than the
In the follow-up survey, we found that a very similar idea was proposed in 37 in broader context, which shows continuous embedding of number tokens perform better than the discrete embedding in various tasks.
'The code is available at ht /ttp///tttbbb/t
wtw.ekKKERA/ttaaaaaeeeeeee groebner

---

Table 2: Accuracy [%] support accuracy [%] of Gröbner basis computation by Transformer D,, (k). ) In the support accuracy, two polynomials are considered identical they consist of an identical set of terms (i.e., identical support). Transformers are trained on either discrete input embedding (disc.) and the hybrid embedding (hyb.). Note that the datasets for n = 3, 4, 5 are here with density o 0.6, 0.3, 0.2, respectively.
constructed using U1, U2 (cf. Alg. 1
Shape position
Cauchy module
Coeff.
π 2
3
5
n 2
3
disc.
93.7 995.4
88.7/92.0
90.8 /4.0
86.5790.3
99.7 / 99.88
97.2/97.6
hyb.
66.8 / 87.3
69.0 89.8
62.7 / 86.8
0.0/ 84.9
98.3 99.77
80.1 89.2
disc.
72.3 79.1
78.1/83.2
71.3 74.6
88.3
98.7 / 19.88
98.1 / 99..7
F7
hyb.
54.1 78.7
55.8/840 84.3
46.1/81.8
84.4
95.8 / 99.77
80.8 /91.2
disc.
46.8/77.3
50.2/80.9
51.1/83.7
28.6/77.9
93.8 99.7
94.7 /99.6
Fa1
hyb. 6.1/75.3
8
0.1/
0.1/76.9
15.1 / /9..5
10.9 99.4
R
hyb.
$1.2785.0
61.0788.0
61.7787.5
45.6782.9
28.37 100
4.37 100
6.2
Learnability of Gröbner basis computation
We now demonstrate that Transformers can learn to compute Gröbner bases. To examine the general Transformer's 's ability, we focus standard architecture (e.g., 6 encoder/decoder layers and 8 attention heads) and a standard training setup (e.g., the Adam optimizer [65] with (31, (1) = (0.9, 0.999) and linear decay of learning rate from 10-1). The batch size set to 16, and models were trained for 8 epochs. We also tested the hybrid input embedding. Refer to App. E for the complete information. Each polynomial set in the datasets converted into a sequence using the prefix representation and the separator tokens. Unlike natural language processing, our task does not allow the truncation of input sequence because the first term of the first polynomial in F certainly relates to the last term of the last polynomial. To make the input sequence length manageable for vanilla Transformers, we used simpler datasets D, (k) using U1. U22 in Alg. of moderate density α E (0, 1]. This makes the maximum sequence length less than 5,000. Specifically, we used o 1.0, 0.6, 0.3, 0.2 for 2, 3, 4, 5, respectively. The training set has one million samples, and the test set has one thousand samples. With hybrid input embedding, coefficients are predicted by regression, and we quantized them for F, and otherwise regarded them correct when the mean squared error is less than 0.1.
Table 2 shows that trained Transformers successfully compute Gröbner bases with moderate/high accuracy. Several intriguing observations below are obtained. See App. [F for more results. Particu- larly, App. F3 presents several examples found in the datasets for which Transformer successfully computed Gröbner bases sigmificantly faster than math algorithms. Table[]alse includes the results on Cauchy module datasets on which Transformers are trained and tested. The dataset generation starts with sampling the roots in ke", and the other parts follow the generation of D,, (k). The results on (Q, = 3) with standard embedding is not shown as requires too many number tokens.
The performance gap across the rings. The accuracy shows that the learning is more successful on infinite field coefficients &s {Q. R} than finite field ones & = Fy. This may be a counter-intuitive observation because there are more possible coefficients G and F for Q than F, Specifically, for G. the coefficient a/b be E Q is restricted to those with a, E { {-5 .,........ 5) (i.e., roughly 50 choices), and 100} (i.e., roughly 20,000 choices) for F. In contrast, there are only p choices for F,. The performance even degrades for the larger order p = 31. Interestingly, the support accuracy shows that the terms forming the polynomial (i.e., the supporr of polynomial) are correctly identified well. Thus, Transformers have difficulty determining the coefficients in finite fields. Several studies have also reported that learning to solve a problem involving modular arithmetic may encounter some difficulties (1 38, 74], but no critical workaround is known.
a. E { {-100,
Incorrect yet reasonable failures. We observed that the predictions by Transformer are mostly reasonable even when they are incorrect. For example, only several coefficients may be incorrect, and the support can be correct as suggested by the relatively high support accuracy in Tab. 2 In such a case, one can use a Gröbner basis computation algorithm that works efficiently given the leading terms of the target unknown Gröbner basis 83), Refer to App. F2 for extensive lists of examples.

---

Distance
Slice
Normalized Slice
product
Slice (Unnorm.)
Distance
Slice
Norm
Normalized product
Slice
(Unnorm.)
Slice
2 laver
(Ri)
(hv)
(4)
(v))
(
(18)
(iv)
(V)
(vi
(a) Embedding of IR-coefficients
(b) Embedding IF coefffiifsss
Figure 1: Visual analysis of embedding vectors of numbers given by the proposed embedding. Embedding R to (c) E IR from Cmin to Cmax with B bins to obtain M E R RBBx D. the fix figures show from the left, (i) the Euclidean distance matrix of M, (ii) its slice at O, (iii) the norm of embedding vectors, (iv) the dot product M MM' with M of the row-no www-normalized M, (v) fe(0)" M and (vi) (F M. (a) Trained on R[ (Cmins Cmax) = (-100, 100). (b) Trained on E31 [2]; (Cmin: Cmax) (0,31). The embedding layer fF. has one/two hidden layers (top/bottom rows). As can be seen, the relationship between embedding vectors in terms of distance and dot product is aligned well in the infinite field and not in the finite field.
Hybrid embedding. Table S shows that determining coefficients by regression is less successful than classifications. For infinite field k; this may be because of the accumulation of coefficient errors during the auto-regressive generation. Thus, the current best practice would be to prepare many number tokens in the vocabulary set, or a sophisticated
approach may be helpful (76). Note that the results for k: = F are shown for reference as the finite field elements do not have ordering. Figure SaarreeTshooe shows a contrast between the embedding functions learned in infinite field and finite field. Particularly, the slice of distance matrix (ii) and that of the dot- cetd-prodct matrix (vi) show that these metrics align well with the difference between numbers in R. However, we cannot observe convincing patterns in the embedding in F31. For the two-layer case in Fig. [[), observe sharp changes around +5 of the horizontal axis. This may be because of the gap in the coefficient range in the input and output space. The coefficients of F ranges between [-100, 100). while that of G does between [-5, 5]. In Tab. we show that the increase of hidden layers of fP does not lead to improvement.
gegression-b--llasifieee
7 Conclusion
This study proposed the first learning approach to fundamental algebraic task, the Gröbner basis computation. While various recent studies have reported the learnability of mathematical problems by Transformers, we addressed the first problem with nontriviality in the dataset generation. Ultimately, the learning approach may be useful to address large-scale problems that cannot be approached by Gröbner basis computation algorithms because of their computational complexity. Transformers can output predictions in moderate runtime. The outputs may be incorrect, but there is a chance of obtaining hint of solution, shown in our experiments. We believe that our study reveals many interesting open questions to achieve Gröbner basis computation learning. Some are algebraic problems, and others machine learning challenges, further discussed in Sec.
Acknowledgement. We would like thank Masayuki Noro (Rikkyo University) for his fruitful comments on our dataset construction algorithm and Noriki Nishida (RIKEN Center for Advanced Intelligence Project) for his help in the implementation. Hiroshi Kera was supported by JST PRESTO Grant Number JPMJPR24K4, JST ACT-X Grant Number IPMJAX23C8, Mitsubishi Electric Infor- mation Technology R&D Center, and the Chiba University IAAR Research Support Program and the Program for Forming Japan's 's Peak Research Universities (J-PEAKS). Yuki Ishihara was supported by JSPS KAKENHI Grant Number JP22K1 1 13901 and Institute of Mathematics for Industry, Joint Usage/Research Center in Kyushu University (FY2023 Short-term Joint Research "Speeding up of symbolic computation and its application solving industrial problems" (2023a006)). Yuta Kambe was supported by Mitsubishi Electric Research Associate Program.
10

---

References
[1] Abbott, C. Fassino, and M.-L. Torrente. Stable border bases for ideals of points. Journal of Symbolic Computation, 43 (3(11):883-938 8944,,999225 2008.
[2] J. Abbott, M. Kreuzer, and L. Robbiano. Computing zero-dimensional schemes. Journal of Symbolic Computation, 39(1):31-49) 2005.
[3] V. Agarwal, S. Aditya, and N. Goyal. Analyzing the nuances of transformers' polynomial simplification abilities. In The First Mathematical Reasoning in General Artificial Intelligence Workshop at International Conference on Learning Representations, 2021.
[4] A. Alfarano, F. Charton, and A. Hayat. Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[5] R. Antonova, M. Maydanskiy, D. Kragic, Devlin, and K. Hofmann. Analytic manifold learning: Unifying and evaluating representations for continuous control. arXiv, abs/2006.0877 18,, 2020.
[6] E. Arnold. Modular algorithms for computing Gröbner bases. Journal of Symbolic Computation, 35:403-419, 2003.
[7] M. F. Atiyah and G. MacDonald. Introduction To Commutative Algebra. Addison- Wesley series in mathematics. Avalon Publishing, 1994.
[8] G. V. Bard. Algorithms for Solving Polynomial Systems. Springer US, 2009.
[9] M. Bardet, J.-C. Faugère, and B. Salvy. On the complexity of the F5 Gröbner basis algorithm. Journal of Symbolic Computation, 70:49-70 September 2015.
[10] T. Becker, V. Weispfenning, and H. Kredel. Gröbner Bases: A Computational Approach to Commutative Algebra. Graduate texts in mathematics. Springer- Verlag, 1993.
[11] I. Beltagy, M. E. Peters, and A. Cohan. Longformer: The long-document transformer. arXiv, 2020.
[12] J. Berthomieu, S. Graillat, D. Lesnoff, and Mary. Modular matrix multiplication on GPU for polynomial system solving. ACM Commun. Comput. Algebra, 57(2):35-33 38, August 2023.
[13] J. Berthomieu, V. Neiger, and M. Safey El Din. Faster change order algorithm for Gröb- ner bases under shape and stability assumptions. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, pages 409-418, 2022.
[14] L. Biggio, T. Bendinelli, A. Neitz, A. Lucchi, and G. Parascandolo. Neural symbolic regression that scales. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 936-945, 18-24 Jul 2021.
[15] M. Brickenstein. Slimgb: Gröbner bases with slim polynomials. Revista Matemática Com- plutense, 23:453-466, 2010.
[16] B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionaten Polynomideal (An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal). PhD thesis. Mathematical Institute, University of Innsbruck, Austria, 1965. English translation in J. of Symbolic Com- putation, Special Issue on Logic, Mathematics, and Computer Science: Interactions. Vol. 41, Number 3-4, Pages 475-511, 2006.
[17] L. Busé. Étude du résultant sur une variété algébrique. Theses, Université Nice Sophia Antipolis, 2001.
[18] I. Busé, M. Elkadi, and B. Mourrain. Resultant over the residual complete intersection. Journal of Pure and Applied Algebra, 164(1):35-57, 2001.

---

[19] F. Charton. Linear algebra with transformers. Transactions on Machine Learning Research, 2022.
[20] Charton, What my math transformer doing? ttree results on interpretability and generalization. arXiv, abs/221 1.00170, 2022.
[21] F. Charton. Learning the greatest common divisor: explaining transformer predictions. In The Twelfih International Conference on Learning Representations, 2024.
[22] Charton, Hayat, and G. Lample. Learning advanced mathematical computations from examples. In International Conference on Learning Representations, 2021.
[23] Y. Chen, Q. Tao, F. Tonin, and J. A. Suykens. Primal-Attention. Self-attention through asymmetric kernel SVD primal representation. In Advances Neural Information Processing Systems, 2023.
[24] D. A. Cox. Solving equations via algebras. In Solving Polynomial Equations, pages 63-124. Springer- ppringer-Verlag, Berlin, 2005.
[25] D. A. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer International Publishing, 2015.
[26] S. D'Ascoli, P.-A. Kamienny, G. Lample, and F. Charton. Deep symbolic regression for recur- rence prediction. In Proceedings of the 39th International Conference on Machine Learning. volume 162, pages 4530-4536, 17-23 Jul 2022.
[27] Diaconis and B. Sturmfels. Algebraic algorithms for sampling from conditional distributions. The Annals of Statistics, 26(1):363 397, 1998.
[28] J. Ding, S. Ma, L. Dong, X. Zhang. S. Huang, W. Wang, N. Zheng, and F. Wei. LongNet: Scaling Transformers to 1, 1,000,000,000 tokens. arXiv, 2307.02486, 2023.
[29] W. Dubé. The structure of polynomial ideals and Gröbner bases. SIAM Journal on Computing. 19(4):750-773, 1990.
[30] N. Dziri, X. Lu, M. Sclar, X. L. Li, L. Jiang, B. Y. Lin, S. Welleck, P. West, C. Bhagavatula, R. L. Bras, J. D. Hwang, S. Sanyal, X. Ren, A. Ettinger, Z. Harchaoui, and Y. Choi Faith and fate: Limits of transformers on compositionality. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[31] D. Eisenbud. Commutative algebra: with a view toward algebraic geometry. Springer Science & Business Media, 2013.
[32] C. Fassino. Almost vanishing polynomials for sets of limited precision points. Journal of Symbolic Computation, 45(1):19-37, 2010.
[33] J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, 139(1))61-88, 1999.
[34] 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, ISSAC '02, page 75-83, New York, NY, USA, 2002. Association for Computing Machinery.
[35] J.-C. Faugère, P. M. Gianni, D. Lazard, and T. Mora. Efficient computation zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation, 16(4):329-344, 1993.
[36] P. Gianni and T. Mora. Algebraic solution of systems of polynomial equations using Groebner bases. Applied Algebra, Algebraic Algorithms and Error-Coreecting Codes, pages 247-257, Berlin, Heidelberg, 1989. Springer Berlin Heidelberg.
[37] S. Golkar, M. Pettee, M. Eickenberg, A. Bietti, M. Cranmer, G. Krawezik, F. Lanusse, M. Mc- Cabe, R. Ohana, I.. Parker, B. R.S. Blancard, T. Tesileanu, K. Cho, and S. Ho. XVal: continuous number encoding for large language models, 2023.
12

---

[38] A. Gromov. Grokking modular arithmetic. arXiv, abs/2301.02679, 2023.
[39] G.-M. Gruel and G. Pfister. A Singular Introduction to Commutative Algebra, 2nd Edition. Sringer Verlag, 2008.
[40] D. Heldt, M. Kreuzer, S. Pokutta, and H. Poulisse. Approximate computation of zero- dimensional polynomial ideals. Journal of Symbolic Computation, 4A(11)1166-1591, 2009.
[41] T. Hibi. Gröbner bases. Statistics and software systems. Springer Tokyo, March 2014.
[42] C. Hou, F. Nie, and D. Tao. Discriminative vanishing component analysis. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 1666-1672, Palo Alto, California, 2016. AAAI Press.
[43] R. Iraji and H. Chitsaz. Principal variety analysis. In Proceedings of the 1t Annual Conference on Robot Learning (ACRL), pages 97-108. PMLR, 2017.
[44] P.-.. Kamienny, S. d' Ascooll, G. Lample, and F. Charton. End-to-end symbolic regression with transformers, In Advances in Neural Information Processing Systems, 2022.
[45] P.-A. Kamienny, G. Lample, S. Lamprier, and M. Virgolin. Deep generative symbolic regression with Monte-Carloo-Teee Tree-Search. arXiv, abs/2302. 1223, 2023.
[46] A. Karimov, E. G. Nepomuceno, A. Tutueva, and D. Butusov. Algebraic method for the reconstruction of partially observed nonlinear systems using differential and integral embedding. Mathematics, 8(2):300-311, February 2020.
[47] A. Karimov, V. Rybin, E. Kopets, T. Karimov, E. Nepomuceno, and D. Butusov. Identifying empirical equations of chaotic circuit from data. Nonlinear Dynamics, 111(1):871-886, 2023.
[48] A. Kehrein and M. Kreuzer. Computing border bases. Journal of Pure and Applied Algebra, 205(2):279-2)) 2006.
[49] H. Kera. Border basis computation with gradient- normalization. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, pages 225-234, New York, 2022. Association for Computing Machinery.
[50] H. Kera and Y. Hasegawa. Noise-tolerant algebraic method for reconstruction of nonlinear dynamical systems. Nonlinear Dynamics, (((())675-692, 2016.
[51] H. Kera and Y. Hasegawa. Approximate vanishing ideal via data knotting. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, pages 3399-3406, Palo Alto, California, 2018. AAAI Press.
[52] H. Kera and Y. Hasegawa. Spurious vanishing problem in approximate vanishing ideal. JEEE 2019.
Access,
[53] H. Kera and Y. Hasegawa. Gradient boosts the approximate vanishing ideal. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, pages 4428 4425, Palo Alto, California, 2020. AAAI Press.
[54] H. Kera and Y. Hasegawa. Monomial-agnostec computation of vanishing idcals. Journal of Computational Algebra, 11:100022, 2024.
[55) H. Kera and H. lba. Vanishing ideal genetic programming. In Proceedings of the 2016 IEEE Congress Evolutionary Computation (CEC), pages 5018-5025, Piscataway, NJ, 2016. IEEE.
[56] J. Király, M. Kreuzer, and L. Theran. Dual-to-kereel learning with ideals. abs/1402.0009, 2014.
arXiv,
[57] N. Kitaev, L. Kaiser, and A. Levskaya. Reformer: The efficient Transformer. In International Conference on Learning Representations, 2020.
[58] G. Lample and Charton. Deep learning for symbolic mathematics. In International Conference on Learning Representations, 2020.
13

---

[59] R. Laubenbacher and B. Stigler. A computational algebra approach to the reverse engineering of gene regulatory networks. Journal of Theoretical Biology, 229(4):523-533) 2004.
[60] R. Laubenbacher and Sturmfels. Computer algebra in systems biology. American Mathemat- ical Monthly, 16(11))882--9))) 191, 2009.
[61] C. Li, E. Wenger, Z. Allen-Zhu, F. Charton, and K. E. Lauter. SALSA VERDE: a machine learning attack on LWE with sparse small secrets. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[62] J. Limbeck. Computation of approximate border bases and applications. PhD thesis, Passau, Universität Passau, 2013.
[63] R. Livni, D. Lehavi, S. Schein, H. Nachliely, S. Shalev-Shwartz, and A. Globerson. Vanishing component analysis. In Proceedings of the 30th International Conference Machine Learning, volume 28(1) ) of Proceedings of Machine Learning Research, pages 597-605, Atlanta, Georgia, USA, June 2013. PMLR.
[64] H. Lombardi and I. Yengui. Suslin's 's algorithms for reduction of unimodular rows. Journal of Symbolic Computation, 3966)777-7717 2005.
[65] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
[66] R. H. Makarim and M. Stevens. M4GB: An efficient Gröbner-basis algorithm. In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC' 17, pages 293-300, New York, NY, USA, 2017. Association for Computing Machinery.
[67] E. W. Mayr and A. R. Meyer. The complexity the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics, 46(3):305-32) 1982.
[68] H. M. Möller and B. Buchberger. The construction of multivariate polynomials with preassigned zeros. In Computer Algebra. EUROCAM 1982. Lecture Notes Computer Science, pages 24-31. Springer Berlin Heidelberg, 1982.
[69] M. Noro and K. Yokoyama. A modular method to compute the rational univariate representation of zero-dimensional ideals. Journal of Symbolic Computation, 28(1):243-263, 1999.
[70] M. Noro and K. Yokoyama. Usage of modular techniques for efficient computation of ideal operations. Math. Comput. Sci., 12(1):1-32, 2018
[71] H. Park and G. Regensburger, editors. Gröbner Bases in Control Theory and Signal Processing. De Gruyter, 2007.
[72] H. Park and C. Woodburn. An algorithmic proof of Suslin's stability theorem for polynomial rings. Journal of Algebra, 178(1):277-298 1995.
[73] D. Peifer, M. Stillman, and D. Halpern-Leistner Learning selection strategies in buchberger's algorithm. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. JMLR.org. 2020.
[74] A. Power, Y. Burda, H. Edwards, I. Babuschkin, and V. Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets. arXiv, abs/2201.02 .02177, 2022.
[75] D. Saxton, E. Grefenstette, F. Hill, and P. Kohli. Analysing mathematical reasoning abilities of neural models. In International Conference on Learning Representations, 2019.
[76] D. Shah and T. M. Aamodt. Learning label encodings for deep regression. In The Eleventh International Conference on Learning Representations, 2023.
[77] Y. Shao, G. Gao, and C. Wang. Nonlinear discriminant analysis based on vanishing component analysis. Neurocomputing. 218:172-181 184, 2016
[78] H. Stewenius. Gröbner Basis Methods for Minimal Problems Computer Vision. PhD thesis, Mathematics (Faculty of Engineering), 2005.
14

---

[79] B. Sturmfels. Solving systems of polynomial equations. Number 97. American Mathematical Soc., 2002.
[80] Y. Sun, L. Dong, S. Huang, S. Ma, Xia, J. Xue, J. Wang, and Wei. Retentive network: A successor to Transformer for large language models. arXiv, 2023.
[81] A. Suslin. On the structure of the special linear group over polynomial rings. Mathematics of the USSR lzvestija, 11(2)221-238, April 1977.
[82] The Sage Developers. SageMath, the Sage Mathematics Software System (Version 10.0), 2023. https:/ / /www://wwwww/c//////////// sagemath. org.
[83] C. Traverso. Hilbert functions and the Buchberger algorithm. Journal of Symbolic Computation, 6:287-304, 1997.
[84] E. Ullah. New Techniques for Polynomial System Solving. PhD thesis, Universität Passau, 2012.
[85] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[86] I.. Wang and 'T. Ohtsuki. Nonlinear blind source separation unifying vanishing component analysis and temporal structure. IEEE Access, 6:42837-42850, 2018.
[87] M. Wang and J. Deng. Learning to prove theorems by learning to generate theorems. In Advances in Neural Information Processing Systems, volume 33, pages 18146-18157. Curran Associates, Inc., 2020.
[88] Z. Wang, Q. Li, G. Li, and G. Xu. Polynomial representation for persistence diagram. In Proceedings of the 2019 IEEE/CVE Conference on Computer Vision and Puttern Recognition, pages 61 1116--10 14116-6125,, 2019.
[89] E. Wenger, M. Chen, F. Charton, and K. E. Lauter. SALSA: Attacking lattice cryptography with Transformers. In Advances in Neural Information Processing Systems, volume 35, pages 34981-34994, 2022.
[90] E. S. Wirth, H. Kera, and Pokutta. Approximate vanishing ideal computations at scale. In International Conference on Learning Representations, 2023.
[91] F. S. Wirth and S. Pokutta. Conditional gradients for the approximately vanishing ideal. In Proceedings of The 25th International Conference on Artificial Intelligence and Statisties, volume 151, pages 2191-2209, 28-30 Mar 2022.
[92] H. Yan, Z. Yan, G. Xiao, W. Wang, and W. Zuo. Deep vanishing component analysis network for pattern classification. Neurocomputing, 316:240-250, 2018
[93] T. Yasuda, X. Dahan, Y-J. Huang, T. Takagi, and K. Sakurai. MQ challenge: hardness evaluation of solving multivariate quadratic problems. Cryptology ePrint Archive, 2015.
15

---

A Basic Definitions in Algebra
Definition A.1 (Ring, Field (77) Chap. $1)). A set R with an additive operation and multiplicative operation * called (commutative) ring if it satisfies the following conditions:
1. a a (b + c) = (a + b) + for any a, b, c E R
2. there exists 0 E R such that + = 0 +
for any a E R,
3. for any a E R, there exists -a such that a + (-a) = (-a) +a= 0,
4. a + = b+ a for any a, E R,
5. a * (b * c) (a * b) e for any a, b, c R.
6. there exists E R such that 1 1 * for any a E R,
7. (b+
b for any a, a, R.
8. (a + b)
c b+ for any a, b,b. E R.
9. a = b * for any a, b E R.
commutative ring R is called field if it satisfies the following condition
10. for any a E R {0), there exists a -1 such that a * a =a Definition A.2 (Polynomial Ring ((7), Chap. 1 $1)). In Definition A.1 k k[x1,... n. the set of all n-variate polynomials with coefficients in k satisfies all conditions (I)- Thus, k( Fnl is called polynomial ring.
Definition A.3 (Quotient Ring (17), Chap. 1 $1).. Let R be a ring and an ideal of R. For each f R. we set [f] = {g E R f E 1}. Then, the set {If] f E R is called the quotient ring of modulo 1 and denoted by R/I. Indeed, R/ is a ring with an additive operation + and a for f,g E R respectively. Definition A.4 (Generators). For F = ......... fo} C k f.11....... znJ. the following set
multiplicative operation where [f] [g] = [f + g] and [f] [g]==
(F) hufe hi.... h, E k(
(A.1)
is an ideal and said to be generated by and fi, are called generators.
Definition A.5 (O-dimensional ideal ((25), Chap. 5 $3, Thm. 6)). Let F be set of polynomials in _.]]- x.)] An ideal (F)) is called O-dimensional ideal if the k-linear space k(z .x,) is finite-dimensional, where k bfzj.....II.. (F)) is the quotient ring of k(z1,... xn) modulo (F). Definition A.6 (Radical ideal (17), Chap. 1 $1)). For an ideal I of if vn). the set { e ((x1,-.., [,.] fm E 7 for positive integer m) is called the radical of 7 and denoted by vT. Also, I is called a radical ideal if [ = VI.
k(z1.....
Definition A.7 (Syzygy (110), Chap. 3, $3)). Let F' [f..... fa} C k(z1..... k[ zn]" such that qı Definition A.8 (Term (110), Chap. 2, $1). For a polynomial f Eoj Ca......,,
InJ. A syzygy of F 9ofe =0
an s-tuple of polynomials (gI....,9.
with Co a....... E K and ai,...,, On E Zzo, each 2 ... x h is called a term in
Definition A.9 (Total Degree ((25), Chap. $1, Def. 3)). For term Ft ...r%. its total degree is the sum of indices a1 + +... On- For a polynomial f, the total degree of f is the maximal total degree of terms f.
Definition A.10 (Term order (10), Definition 5.3)). A term order x is relation between terms such that
1. (comparability) for different terms ....
21 an ... wnt and 8 ... r. either 2 ... 2..
91 wffn or x r.. 3n x a
0e holds,
2. (order-preserving) for terms vi on
... an 21 ... x and #1 7 ... 27 + 1, if
I
31 ...,. then x on tn an x
titt 3n +7n holds.
x
16

---

3. (minimality of 1) the term 1 is the smallest term i.e. 1 21 ... -2." for any term 21 2n #
Example A.1I. The lexicographic order tee prioritizes terms with larger exponents for the variables of small indices, e.g..
32 > lex 23 and T13223 <lex x12223.
(A.2)
Two terms are first compared in terms of the exponent in xı (larger one is prioritized), and if tie-break is needed, the next variable 12 is considered, and so forth.
Example A.12. The graded lexicographic order <grlex prioritizes terms with higher total degree For tie-break, the lexicographic order is used, e.g..
1 Xgilex In and I2 Xgrlex 2z and Z1 <gelex F14z23.
(A.3)
Term orders prioritizing lower total degree terms grlee called graded term orders. Definition A.13 (Reduced Gröbner basis). x-Gröbner basis ,9t of is called the reduced Gröbner basis of T if
1. the leading coefficient of 9, with respect to is 1 for all i 1, I....,t
2. no terms of lies on (LT \ ()) for any i i= 1=....,;"
Proposition A.14 ((36), Prop. 1.6; [69]. Lem. 4.4). Let 1 be O-dimensional radical ideal. If is of characteristic or finite field of large enough order, then random linear coordinate change puts I in shape position.
B Cauchy module
We here provide the definition the Cauchy module, which defines another class of O-dimensional ideals.
Definition B.1 (Elementary symmetric polynomials). The elementary symmetric polynomials
$1,..., 8n in variables ..,....> In are
8
Σ Si<tii
Ties
k 1=.....,2
(B.1)
Definition B.2 (Cauchy modulc). Let Sn be the symmetric group on a finite set of size n. Let be an algebraically closed field, and let (an,... an) E kn be a generic point (i.e., a # aj for i * j). Let the finite subset C kn
= (o(a) (ao(1)) ... (o(n)) a Sy)
(B.2)
Let (1( be polynomial of 1,
(1t) = 2 - s2(a)
(-1)"s, (a) =
(t a;).
(B.3)
i=1
Let us introduce indeterminates 21,..., 2n and fi (22) f1 (21) 22 21
f2 (22,21) 21)
(B.4)
fz (2g, 21)
(22, 21)
fa 22,2)
(B.5)
23
(B.6)
fn (2n) fn-1 (2ns 2n -n-2, 2........ .2..). fa-1 (2n-1, ....;
(B.7)
Zn Zn-1
(= 21
Zn s1 (a))
(B.8)
The set of polynomials C' = {f1,.... ffa....ff! f.} is called the Cauchy module. Remark B.3. The Cauchy module is the reduced -Töbner basis of (C) with ø1 Alex
-lex
Zn.
9The total degree of term si ... 2 refers to Ei. The total degree of polynomial f refers to the maximum total degree of the terms in f.
17

---

Algorithm 1: Dataset generation for learning to compute O-dimensional Gröbner bases.
Assumption: polynomial ring (.x1,...; Zin
Input: dataset size maximum degrees d, d', maximum size of non-Gröbner set Smax 2 n, and term order <. Output: collection D {(F, Gi)) of non-Gröbner set F; k( In,' and the reduced <-Gröbner basis G. k(zi..... Fnd O-dimensional ideal (F) = (G).
D - 0 for i 1, ,..., do
Gi - {h} with h, non-constant, monic/primitive, sampled from k(
Prob. 4.
for = -.......---- n- do
G. - G. U with gj sampled from ki d(xn)gdeg(()-1
end
U[n, Smax]
Prob. 4.2
Sample unimodular upper-triangular matrix U, E ST Sample unimodular upper-triangular matrix U1 ST(n, k[ )d)). Sample permutation matrix P E {0, 13xx
11
F; + PU2G, where U2 = IU4 On,a-nl E sx i + f then
13
G; + FGLM(G,, -lex: -)
end
15
D - D (UF(
> Reorder terms in Fj if x
16
end
C Dataset generation algorithm
Theorem 4.6. Let G (91.....9t) " be Gröbner basis of O-dimensional ideal k. Let F = (J1....,ss) Ss) = AG with A k(x,,-..,,.8 1x11
1. (f = (G), it implies s 2 n.
2. If A has a left-inverse in k| [n] 1xx, (F) (G) holds.
3. The equality (F)) (G) holds if and only if there exists matrix B E klz In. jtxs such that each row of BA Eg a syzyg, 10 of G, where Eg is the identity matrix of size t.
Proof.
(I) In general, if an ideal / is generated by elements and < then the Krull dimension of k[z 2/1 satisfies that dim ;(.),...,, > n 5 (Krull's principal ideal theorem [3] $10D.. Since the Krull dimension of k(z,,...,..1 (,](())) is O, we have 2 n.
(2) From F AG, have (F) (G). If has left-inverse B K[11.......................... ........... ex,, have BF BAG G. indicating (F) 3 (G). Therefore, we have (F) = (G).
(3) If the equality (F) (G)) holds, then there exists a x matrix B E k[z1..... .r ]x, such that G BF. Since F is defined as F = AG, we have
BF = BAG and G = F.G in kfzi.... rr,'" Therefore we obtain (BA F.)G 0. In particular, each row of BA F, is 2n [_, such that each row of BA E, is syzygy of G, then we have (BA - E,) 0 in k[ In)", therefore the equality
syzygy of G. Conversely, if there exists a x s matrix B E k[
(F) = (G") holds since we have = E,G = BAG = BF.
Proposition 4.7. For any E A(. Jxx with det(A) E kc (0), we have (F) (G).
Refer to App. for the definition.
18

---

Proof. From the Cramer's rule, there exists B E k(z1,..... Fn. Inn nnnn such that BA = det(A)) En. where En denotes the n-by-n identity matrix. Indeed, the i-th row B, of satisfies for ....., n,
B₁ det(A) dett (det [4]
det (A%)
(C.1)
where 1/5 is the matrix A with the j-th column replaced by the i-th canonical basis (0, 1,....0) 0)T. Since det(.A) ((A) is non-2ero constant, A has the left-inverse B in k(zi,...., En] mn]x Thus (F) = (G)
from Thm. 4.6
Theorem 4.8. Consider a polynomial ring k(zi....,zn)) Given the dataset size maximum
degrees d, > O, maximum size of non- Grö-Grööeer set Suax 2 n, and term order x, Alg. 7 returns a collection D {(FF, km with the following properties: For all i= =,1..... 1,..., m,
1. [G|] and [Fll S Smax-
2. The set G2 is the reduced <-Gröbner basis of (F.). The set F; is not, unless G4, U1, U2, are all sampled in a non-trivial Zariski closed subset
3. The ideal (Fi) (G.) a O-dimensional ideal in shape position.
The time complexity is Omm(nS1. + S² + (n² + Mn. when <= where Sn,d denotes the complexity of sampling n-variate polynomial with total degree most d, and Ma,d denotes that of multiplying two n-variate polynomials with total degree at most d. If * Stex. O(mmd3) is additionally needed.
Proof. Outside of the Zariski subset part, statements 1-3 are trivial from Alg. and the discussion in Sec.s 4.2 and 4.3 To obtain the desired Zariski subsets, consider the vector space of polynomials of degree d + 2d or less. We remark that if F; is a <-Gröbner basis, its leading terms must belong to finite amount of possibilities. For a polynomial have given term 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, obtain the desired result.
To obtain one pair (F, G), the random generation of needs O(nSI,a). and the backward transform from G F needs Oss2Sn.d) Sn.dr) to get U1. U2 and (n² Mr Mn.2 2dd for the multiplication F PU,GG Note that the maximum total degree of polynomials in F is 2d' + d.
D Hybrid Input Embedding
We here present the supplemental information of Transformers with hybrid input embedding. Let to be sequence of tokens. Some of these tokens are in V and otherwise in IR. We call the former discrete tokens and the latter continuous tokens. For discrete tokens, the standard input embedding based on the embedding matrix is applied. For continuous tokens, a small feed-forward network fE R RDD is applied. Unlike discrete tokens, continuous tokens are predicted by regression. For this sake, Transformers should equip a regression head, and they solve classification task and regression task simultaneously. In the classification task, continuous tokens are all replaced with a single coefficient token. In other words, the classification head predicts the support of the polynomials, while the regression head predicts the coefficients to be filled in the coefficient tokens. The auto-regressive generation process is naturally induced by standard method.
s = [s1....,$1,
] SL]
In our experiments, implemented fe by one-hidden layer ReLU Network, i.c., fε(ω) = W24p(1 + b,) + b2,
(D.I)
where wi, b, E IRP, W,, E D b2 E RR and & is the ReLU function applied entry-wise. We also tried fg with one more hidden layer. However, this only has minor improvement on the case; see Tab. 3
E Training Setup
This section provides the supplemental information of our experiments presented in Sec. 6
This happen with probability zero if & is infinite and very low probability large finite field.
19

---

Table 3: Comparison of implementations of continuous input embedding fE on D (k:).
Coefficient
Q
F7
IF 31
one hidden layer two hidden layers
66.8 / 87.3
54.1 / 78.7
6.1 75.3
57.2 / 85.0
67.2/ 87.7
54.3 78.8
5.6 75.7
56.2 / 83.6
E.1 Gröbner basis computation algorithms
In Tab. generation.
[
we tested three algorithms provided in SageMath with the libSingular backend for forward
STD (Libsingular:stdd) The standard Buchberger algorithm.
SLIMGB (Libsingular:sllimgbi variant of the Faugère's F4 algorithm. Refer
13
STDFGLM (Libsingular:stdfggl)) Fast computation using STD with the graded reverse lex- icographic order followed by the FGLM for the change of term orders. Only for O-dimensional cases.
E.2 Training setup
Dataset. Both training and test samples are generated using our method. involves sampling of random polynomials. The degree and the support size (the number of terms) of them as well coeffi- cients are restricted by user-defined bounds (see Sec. 6.I). Let dinax Pmax be the maximum degree and the maximum support size. A random polynomial is obtained the sum of μ ~ U[1, (maxl] monomials uniformly and randomly sampled from k k(xr,,..,, In Sdmaxx When the samples are fed to Transformer, polynomials are tokenized into infix representation. For example, {a² 11/2y, y} C Q(r y] is tokenized to [C1, E2, EO, +, C-1, /, C2, EO, E1, <sep>, C1 EO, E1.
with a standard architecture: 6 encoder/decoder layers, attention heads, token embedding dimension of 512 dimensions, and feed-forward networks with 2048 inner dimensions. The absolute positional embedding is learned from scratch. The dropout rate
Training. We used a Transformer model 85
0.1. We used the AdamW optimizer (65) with (81, B2) (0.9, 0.999) with weight decay. The learning rate was initially set to 10 and then linearly decayed over training steps. All training samples are visited in a single epoch, and the total number of epochs was set size was set to 16. At the inference time, output sequences are generated using a beam search with width For the hybrid input embedding. we used ReLU network with one hidden layer (cf. Sec.Dr A model with this embedding predicts coefficients continuous values, and the mean-squared loss with weight 0.01 additionally used for the training. Note that while the exponents are also numbers, we treat them as discrete tokens because they are always discrete and their range is moderate.
The batch
F Additional Experimental Results.
We provide the additional experimental results with Transformers with the standard input embedding.
F.1
Dataset generation
The runtime comparison for datasets with and without density control is given Tab, 4 and the success rate (i.e., not encountering the timeout) is given in Tab.5 The generation of density controlled datasets D,; (k:) (1,000 samples) requires less runtime, and the proposed method not always the fastest. However, it is important to remember that the forward method is still not feasible because of the difficulty in sampling overdetermined non- Con-Gröbner sets (i.e., Fs). Generally, such F only leads to trivial ideal with Gröbner basis {1). The profile of datasets is given in Tab.
20

---

Table 4: Runtime comparison (in seconds) of forward generation (F.) and backward generation (B.) of dataset D (k) of size 1,000. The forward generation used either the three algorithms provided in SageMath with the libSingular backend. For D (k), the proposed method is not necessarily the fastest, Note that the runtime of the forward methods does not include the sampling of F, and F is given from the datasets constructed by the backward method. The sampling step roughly consists of 30% the runtime in the backward method. is also worth noting that sampling overdetermined F generally leads to a trivial ideal with the Gröbner basis (1).
D
D (Q)
Method
11 =
2
11
=
3
11
n=
71 = 2
71 = 3
71 = 4
7 =
5
1.0
0.6
0.3
0.2
(STD)
4.20
216.3
740.1
1411.1
4.20
104.3
101.0
117.4
E. (SLIMGB)
4.29
183.4
697.5
1322.7
4.29
77.1
98.9
134.5
(STDFGLM)
7.22
8.29
21.0
164.3
7.22
12.1
9.75
14.9
B. (ours)
5.23
5.46
7.05
7.91
5.23
11.2
7.85
13.7
D (F7
D 12
(F7)
Method
n1
71
71
71
a 2 0 =
n 3
n
n
0
0
0
1.0
0.6
0.3
0.2
(STD)
4.93
4.57
818.9
2123.3
4.93
4.30
48.8
91.5
(SLIMGB)
4.92
5.57
561.0
1981.2
4.92
4.65
32.9
81.8
R. (STDFGLM)
8.02
6.33
9.20
62.6
8.02
7.50
7.25
7.46
B. (ours)
6.79
8.36
10.5
14.2
6.79
8.72
10.5
14.5
D, F31)
D (F
Method
11 2
11 3
Y1 4
Y1 5
2
3
4
5
0
0
0
0
1.0
0.6
0.3
0.2
F. (STD)
5.08
5.04
777.6
2110.4
5.08
4.39
20.6
114.0
(SLIMGB)
5.07
6.91
664.2
2026.0
5.07
4.98
22.2
103.2
F. (STDFGLM)
8.10
6.73
9.14
80.2
8.10
6.95
7.23
8,58
(ours)
7.40
8.37
10.5
14.7
7.40
18.0
9.91
15.3
F.2 Success and failure cases
Tables 7 show examples of success cases. One can see that Transformers can solve many non- trivial instances. Tables 19 and 21 show examples of failure cases. One can that, interestingly, the incorrect predictions appear reasonable. Examples are all taken according to their order each dataset (i.e., cherry-pickinng
F.3 Superiority of Transformer in several cases.
Approaching Gröbner basis computation using a Transformer has a potential advantage in the runtime because the computational cost has less dependency the problem difficulty than mathematical algorithms do. However, currently, mathematical algorithms run faster than Transformers because of naive input scheme. Nevertheless, observed several examples in our D,, (k) datasets for which Transformers generate the solutions efficiently, while mathematical algorithms take significantly longer time or encounter timeout.
Particularly, we examined the examples in D,, (k) where several forward methods encounter a timeout with the five-second budget, see Tab. 5 We fed these examples to Transformer and the three forward algorithms again, but now with a 100-second budget. For such examples, as shown Tab. 22 Transformers completed the computation in less than second, while the two forward algorithms, STD and SLIMGB, often used longer computation time or encountered a timeout.
It is worth noting that STD and SLIMGB general-purpose algorithms, while STDFGLM is specially designed for the zero-dimension ideals. To summarize, Transformers successfully computed Gröbner bases with much less runtime than general-purposs algorithms for several examples. This shows
21

---

Table 5: Success rate [%]] of forward generation with the seve-second timeout limit.
D
D
(
Method
71
11
71
71
71
71 3
n1 4
n
5
0 =
0 =
0 =
0
1.0
0.6
0.3
0.2
(STD)
T00.0
96.0
85.5
72.2
100.0
98.3
98.2
97.9
(SLIMGB)
100.0
96.6
86.4
74.4
100.0
98.7
98.3
97.6
(STDFGLM)
100.0
100.0
99.9
98.4
100.0
100.0
100.0
100.0
D F
D (F7)
Method
71
71 3
Y1
Y1 5
n 2
71 3
n
n
5
0
0
0
1.0
0.6
0.3
0.2
(STD)
100.0
100.0
84.8
58.7
100.0
100.0
99.3
98.4
E. (SLIMGB)
100.0
100.0
91.6
62.9
100.0
100.0
99.7
98.7
(STDFGLM)
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
D
D (F
Method
n
71
71
71
n 2
n 3
n 4
n 5
O =
O =
0 =
0
1.0
0.6
0.3
0.2
F. (STD)
100.0
100.0
86.0
59.2
100.0
100.0
99.7
98.0
(SLIMGB)
100.0
100.0
89.6
62.3
100.0
100.0
99.8
98.5
(STDFGLM)
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
Table 6: Dataset profiles. The standard deviation is shown in the superscript.
Metric
(2)
P77(0) (Q)
===
0.3
0.2
Size of Ft
2.57 71)
3:4 20.00)
62.
2,57 2.07710771
371(30077)
4.86 208.
5.9p!
Max dogree in P
+.011
8.x(=1144)
9.2(+1120)
9.1(+1.22)
(+1000)
(.34(+1.63) +2.0+))
(.44)
degree
4.09 41
(.5(211.92)
4.75(111 60)
(.96(11.5)
409(11100)
(96(42.00)
3,5(
3.38(
of temms F
1544 (7.87)
3318(18 (176727.977
42.0
1546
2436(229.15)
40.32(2:11300 (2.6(1110.34
Grohner miño
(10.000)
o(100)
of20)
o(1.0)
0:00
g(200002)
o(10)
o(=20)
Size of
2000200
3000
4000
300
30001000
1000
5.00
Max depree
400(11.32)
4.0 400121.32)
4.001:1.32
4.0(11)32)
400(2:132)
400(11.32)
4.00
4.0 1.
Min degres G @ temms
247
2mm(+1.14)
1799 1.00)
Lea +0.00)
247 (.29)
20r +..14)
1.9 (.9(+1002)
1.60/
8.9)(=3.25)
11.00/$4.118 187
13.861=4.00
283(#8.24)
11.9944.11
13.87(244.90)
niño
((20)
((:0)
((20)
((20)
((20)
((10)
(2b0)
(2:0)
Menic
Dr (F7)
D, (8r)
3000 100
203))
5000 80
300
300
92)
5
Max degree F
791(12.04
8.5(21.67)
851(11147 84)
791 (22004)
845(11..7)
8.3(211.3))
(.1(11..77)
Min degree
437 +2.06
413(-2.07)
(4.11)
4,37 +2000)
+2.07)
3.44
(+2.1)
+111
19.8 0000+9.00
27.61110.47
34.2(#11
4130(=11.00
19.8 62)
21.51=
34.0(411107)) 11.01)
41.50(#11.00 1.)
Grobner naño
0.02 (1.001)
031)
o120)
((1.)
000
0(20.001)
o(10)
o(20)
Size of G
2.00
300
4.0!
sop
200
300(+0)
400
50o(+0)
Max degree in G
194
3.9(=1134)
1.8()1184)
194()1884))
193(#11.4)
(.9)(=1.84)
394 11.44))34)
Min
2.39 10/11.20 22)
(.9(221111
(7701:007)
(.3(10..0)
2.3(111
199(41.11)
L.2
of temss G
632
11.8
1347(=4.94
632(+233)
k7)(43.23)
Geöhbee mito
((#0)
((b0)
=00)
(+:0)
(+#0)
(+:0)
((+0)
(=#0)
Metric
(Pai)
o 1.0
0.6
a 0.3
0.2
Size of
s.pl F2)
400 -0.22
+0.82)
600
300
F0.82)
Gopl F0.82)
degree
$11142.00
1.5(=1.6))
162(41164)
(60(1146)
(.1
8.5 (65(41.6))
8.2(#1.84)
8.69(#1.40) (.44)
Min degree F
4.55 4.5(112.0))
433(22.00)
(12
(41
4.5(12206)
433012)08)
38) (22
361
p temss
2046 19.74)
3500
12.00012.00
2046 74)
28 23.01100.
11.01111111
42.0
g(#0.017)
000000000
0(#0.003)
o(+0)
0(#00017)
o(*0.000)
o(#000001)
o(=0)
200
10)
400
500
2.00 10)
300
100
500
Max depree G
401(21.31)
4ax 4ax(11.31)
4
Min degree
2./41.244 24)
211(=1118)
(.9()1107))
L6g +0.(++
256(+1124)
216(+1.18)
(xx(+1.07)
+0.9))
663(42
9.1(233.6)
1130125.0g 11.7(444.8)
661(12.33)
9,6(43.
(1..144115)
(430(45000)
Grihner ntio
((20)
(dbo)
((20)
((:0)
((20)
((:0)
(db0
((20)
22

---

potential advantage of using a Transformer in Gröbner basis computation, particularly for large-scale problems.
F,4 Generalization to out-distribution samples
Handling out-distribution samples is beyond the scope of the current work. Several studies of using a Transformer for math problems (e.g., integer multiplication (30] and linear algebra [19] addressed out-distribution generalization by controlling the training sample distribution. This is because these problems are of moderate difficulty, and naive training sample generation methods exist. However, this is not the case for our task, and we thus focused on the problem of efficient generation of training samples this paper. Nevertheless, we consider that presenting limitation of our work by experiments is helpful for future work. Thus, we here present that the Transformers trained on our datasets certainly fail on out-distribution samples through several cases.
Out-distribution samples. We generate additional datasets (k) for k E {Q, F7, F31 These datasets generated as D,, (k) with slight difference in sampling of random polynomials. Origi- nally, a (degree-bounded) random polynomial is obtained using monomials randomly sampled from k(x1,-..;; :.......;ppl........ Sdyls. Since there are more high-degree terms than low-degree ones, random polyno- mials are more likely to be high-degree. In (k). we instead uniformly sample the degree-bound d from W[L, dmax], and then conduct the sampling of monomials. As Tab. 23 shows, this change in the sampling strategy causes some distribution shifts. Table 24 shoss the prediction accuracy and support accuracy on the new datasets. As can be seen, the accuracy drops when the base field is a finite field Fp. When it is Q, the accuracy drop is moderate.
Katsura-n. Katsura-n is a typical benchmarking example for Gröbner basis computation algorithms ("-n" denotes the number of variables). Table 25 shows a list of examples for different E {2, 3, 4} and k (Q, Fr,, F31]. While the Gröbner bases in Katsura-n have form of Eq. 44.1). one can readily find its qualitative difference in the non- non-Gröbner sets from those in our (k. datasets (cf. Tables 11). For example, non-Gröbner sets in Katsura-n consist of low-degree sparse polynomials, whereas those in (k) are not because of the generation processes (i.e., the product and sum of polynomials through the multiplication by polynomial matrices U1. U2). Therefore, Katsura-n examples are greatly out-distributed samples for our Transformers. We fed these samples to the trained Transformers, but only obtained the output sequences that cannot transformed back to polynomials because of their invalid prefix representation.
As Gröbner basis computation is an NP-hard problem, it may not be good idea to peruse general solver via learning. Instead, we should ultimately aim at a solver for large-scale but specialized cases. Thus, the generation of application-specific training samples and the pursuit of in-distribution accuracy will be a future direction. From this perspective, existing mathematical benchmark examples may not be practical because they are mostly artificial, empirically found difficult, and/or designed for easily generating variations in the number of variables [2] They are useful for math algorithms, i... the algorithms proved work for all the cases (i.e.. 100% misut-disttibution samples), but not for our current work because they are out-distribution samples.
G Buchberger-Mölllr Algorithm for Prob. 4.1
Here, we discuss another approach for Prob. 4.] [uiig the Buchberger Möller (BM) algorithm 2 68 Although we did not adopt this approach, we include this for completeness as many variants have been recently developed and applied extensively in machine learning and other data-centric applications.
Given a set of points X C km and a graded term order, the BM algorithm computes a Gröbner basis g(p) 0, Vp E X). While several variants 54 62), interestingly. it is also recently tailored for
of its vanishing ideal T(X) {g E k[z1,-....
Fn
follow in computational algebra [
32 40
48
49
machine learning 42 51553 56
63 90
91). Various applications have followed such as machine
learning [77] 92). signal processing 88)-8), nonlinear dynamics
[46) 47 50), and more [5 43 [5].
Such broad applications derived from the distinguishing design of the BM algorithm: unlike most computer-algebratt algorithms, it takes set of points (i.e., dataset) as input, not set of polynomials.
For example, refer to
html
23

---

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 On [x Furthermore, we need Onr")) points to obtain a Gröbner basis that includes a polynomial of degree in the average case. Therefore, the BM algorithm does not fit our settings that large number of Gröbner bases are needed (i.e., = 10%). Accelerating the BM algorithm by reusing the results of runs instead of independently running the algorithm many times can be interesting for future work.
H
Open Questions
Random generation of Gröbner bases To our knowledge, no prior studies addressed this problem. Our study focuses on generic O-dimensional ideals. These ideals are generally in shape position. and simple sampling strategy is available. However, some applications may be interested in other classes of ideals (e.g., positive dimensional or binomial ones) or particular subset of O-dimensional ideals (e.g., those associated with a single solution in the coefficient field). The former case is an open problem. The latter case may be addressed by the Buchberger- Mööler algorithms 68 (cf. App. G
Backward Gröbner problem. Machine learning models perform better for in-distribution samples than out-distribution samples. Thus, it is essential to design a training sample distribution that is close to one's use case. As noted in Sec. 4.1 polynomial systems (either Gröbner basis or not) take domain-specific form. Backward generation gives us control over Gröbner bases but not for non-Gröbner sets. Hence, we need a well-tailored backward generation method specialized to an application, as the specialized Gröbner basis computation algorithms in computational algebra. This paper addressed a generic case. Prop. 4.7 states that any matrix A E SL, (k[x),.... Zn.) satisfies Prob. 4.5) This raises two sets of open questions: (i) are there matrices outside (L.,
satisfying Prob. 4.3% Can we sample them? and (ii) is it possible to efficiently sample matrices of
SL, (k(zI....... I. ? To efficiently generate our dataset, we have restricted ourselves to sampling matrices having Bruhat decomposition (see Eq. (4.2)), which is strict subset of SL, (k|æ1,..... (k(.)........... xx,)).
Sampling matrices in (k(z). Fn remains an open question. Thanks to Suslin's stability
theorem and its algorithmic proofs 664 72 81. (k( .n.)) is generated by elementary matrices and a decomposition into a product of elementary matrices can be computed algorithmically. One may hope to sampling of elementary matrices to sample matrices of SL.,, (k [x11 ........................ (u.)). It
is unclear whether this can be efficient as many elementary matrices are needed [64].
Distribution analysis. Several studies have reported that careful design of a training set leads to a better generalization of Transformers [19] 21]. Algebraically, analyzing the distribution of Gröbner bases and the non-Gröbner sets is challenging, particularly when some additional structures (e.g., sparsity) are injected. Thus, the first step may be to investigate the generic case (i.c., dense polynomials). In this case, Thm. (46 is helpful to design an algorithm that is certified to be able to yield all possible G and J' almost uniformly. While dataset generation algorithms should run efficiently for practicality, solid analysis may be of independent interest in computational algebra.
Long mathematical expressions. As in most of the prior studies, we used a Transformer of a standard architecture to see the necessity of specialized model. From the accuracy aspect, such a vanilla model may be sufficient for Q[ xx,] but not for Fp.=....... In). From the efficiency perspective, the quadratic cost of the attention mechanism prevents us from scaling up the problem size. For large n, both non-GB sets and Gröbner bases generally consist of many dense polynomials, leading to long input and output sequences. Unlike natural language processing tasks, the input sequence cannot be split as all the symbols are related in mathematical tasks. It is worth studying
several attention mechanisms that work with sub-quadratic memory cost 11 2 28 57 80 can
be introduced with a small degradation of performance even for mathematical sequences, which have a different nature from natural language (e.g., a single modification of the input sequence can completely change the solution of the problem).
24

---

Table 7: Success examples from the D2 (Q) test
ID
F
G
f1 1 2x
2x +50 2/321 + +1/5
91 Fy +5/20f 2x 529 2/321 + +/55
0
f2 = 3/50ga/ + 1/5mffm + 3/2rzz4
92 r
5/4zi + 5
7/10000 + 13/5xga + 3/5ngz]
1/75x62 +1/252021 ++ +1/25202++2 +
5z1
f1 zozr oÎ 3r
81 2/3
91 En I1
f2 = 1/325a/
+
4r
2
= 1] + 2x 21 2/3
11/3rga
+8/3r027
2r| 6z 2r
4/3x/
fo = 4/32/2/ +
16
2 + 22
44/3r3z]
+ 32 02/3r + 3/
13/4m/a
+ 5/2xl=/
33/20zqa
5/ 5/4rpm1
+ +5/6a
rga + 3/5mpa
6/50ga] -5/4 -19 2//
-4=-3/25mnp 3/252/221
1/4mg=/
-1/2nja
7/25x #1144r
- 1//62/ -3/25
6/25mqr/ + -13/20x
22 22/25x222
2/ 2/25x - = -
-24 + 1/44ga7
8x707 3/ 3/40j + 11
1/6ag vo +
=1=3/4x
200, + 20
1/52041
40 I1
2
2x 1/52f
f2 -5/3z0
3/2x801 5/3eßar
92
2 6 4ro01 + +2/5x00 + 4x + +3/5x²
fa -5/6aj 5/6x//1
5/2xga/
13/4r/44 + 1/20/n2 - raz
+ 2
1/50001 5o + +3/2r
2r
1/50 21
fi 5 + 4 + I
91 T0 4/5
3
f2 = -2=522/3rpp
+ 20/33
5/30/ + +5/3roa] 4/30n11
fo = 5/22f22 + 2x0er
2
5/62g=1 + +2/3xnx + +1/20003 + J0 4/5
= 5/3rt
rf + 5/4x1 5/2
91 To
5/
5/4z1
5/2
4
f2 = x + +5/30/21
+ x}27 //x2aa1
0
5z
1/5
1/2x + 5002f
25 + 10/33
200 + 20021
500 + 5/662 1/2x1
5/82/ - 5/4z/
ʃa = r8 5/3aga1 + xd + 5/ ///
1/2r + 500af
25x 1 + 10 o
2r +5/2n
55
5/40p=/ - 5/221
+100
+ /2 5x
x² 5/4r7 5/2x11
1/5
=1 2/5x1
Tu + 2/5x1
5
= 111--/300 -1/30
x
3/4x/
2/15 2/15xØ2
92 = x
1/20mg21
1 4
f1 3/ 5//
T + 3/25000
91 0n - 5/3z + 1/50 4/521
6
12/25xga/
+ 3/4ro + x
29/220r
19/20x²
3/5x1 - 1/2
f== 3/100x3
1/20/2/ + 3/50x02
92 - - 1/50f + 44/50 - 1/2
6/25maa
3//8022
Iq 1/2x
29/40x
- -5/3o1 + 40 - 1/1007
21 21/20x1
fi = To 5/4x 5/4
91 In + 5/4z 5/4
7
f2 = r
5/4mg
+ 4r + 5/4xg
92 = x + 2/ + 2/501
50001
5 + +xf 1/2rr/
2/5xz
25

---

Table 8: Success examples from the D3 (Q) test set.
ID
F
G
= 4mozie2 + 4/5xp1122 + 4/52043
91 ro 1/422
zWzž 40f22 + -
0
1== 5x1=) 20r 1
-
92 = T1 +22
-2 1/422-
Ja 4/5rjaja3
+
4 4/25mgrrut uz 4/50gafu2
93 2
4/25r8r2 1/5aguj03
1/50mm2 3/5
16/3m 16/3rg0fa2
11 (1tp::=:66111112/===//// 16/3x/42
2/5x002 4/3x
4/3r,42 - 4/3x122 + +1
4mprja² + 4 + 3/50gT/02
4/3rgT1 +355gga
5
20r
5/4z|22-93 -5//2225/42/55
+5
16/3x112
4/3r1
fo -1/3r 22
1/32/02
2/5rgr1
- 2/ 2/5
162j2f02
16/52fafæ2-
-2 - -66/5200715
-16001/12 + 4
5002112
+ 11/32q2122
11/3rp0102
2/152022
+ 1/500022
81 x
1/12.2
1/3r2
f1 11
J5 4x2
91 TD + 1/52 + 4/3322 + 5/3
f2 -2=--/330 2/300 1/5 x2
+ 2/3x0
+ +/33x/32
= 01 x2 4.2
2
2/3rgT1
2 2/5n
8/50002 3 +2/3rgu2+8/3an
/55ff22
3/25x -3/5m/12
1/5x,
fo -1/2x/072
+ 1/20g0/13
2
= = + 3/522 - 3/2
2x
2/3rg0132
+ 2/3r
8/30/a2
3/200007
3/10ra2f45
6/5mga 12 1/50p1143
2/5xr02
8/52ga Jо - -9/100x
-3/5rf12
3/4ria - 3/25x + 1/50/
9/5x/a2
+ 16/522 x 16/5x
1/52 +4/3x2 + +/3
-1/2ngu702
+ 1 1/2
20
Th
3/ 3/20xfufař
3/ 3/102g0141 6/52/2123
4/3rgr1и
5/30/01
9/ 9/100r02fa
3/5 a
3/4
1/4x0a
1/20or1
+ 3/2ro1112
- 1/200
7/2r0r2
3 -6x02
1/20z
1/3rf12
5/12n/ -11 + 2x
23 23/52² 3/2
fa f= 4/9r/-/22
3r
4/90
16 16/9r8 +
11/15r
4 4
5
4/152/0fu4 + 16 16/1521011)
1/2mnan
2/25m00fz/
+ 8/15mpr12)
5/60g r3
+ 3/2mp1 02 + 6rozfa
1/10
2/3800112
2/3rp=
3/ 3/2000125
2 23 23/3802112 + 5/3mp)
20/3 20/300a2
I032 3xf02
69 69/5xf43
+ 9/2x²
+ 1/30
17 27
-3/4x122
3/2z
6
1/20z]
1/32 5/322
26

---

Table Success examples from the D7 (Q) test set.
ID
F
G
fi = 3xg 13 33/203
2o + 323
z3 - -3/22z
f2 = -3 3//5x/=3 9/5 + 3/52003
92 = 01 + +33
0
9/10x +
f3= 1
1/2000////1
12 - 1/5xg + 1/403 +
3/4rqui03 3/ - riæg
4/5x 1223
4/5x223 + -
[==1/ -
3/2r
94 94 3 r3 + 4/3r3
+3 1
1/5xg43 - 11/50223 +
4
+
1/5x3 1/4r3
f=z 2/5x3 1/2
=0 1/203
= 2 -2/5212123
1/2xn
92 = 11 2/5233 1/2
2/3r/r3 +13rfa3+//15211000 11/4111/00
2222
+ 4/152/23 +
/6. 122013 +23
1/2x3 - -5/2
f3=-4/3mga 00l00///11602222 5/401022
2/300// +
93 =3=02 + 4/330 + +33 - 4/5x3
Tn 5/2r/32 T13233
4/30113 -2/321 + +1/411 + 10/3rr
1/10x3 +3/823
fr 2 + 20/23 2 + 202713
91 -1 1/22g 5/2
2/5 12 - -1/ 1/100/112 + 1/30/a2
2/150/a223
1/64f02
1/50fa3
2/25m143 +1 11/10r11g
13.3 ( +1/25300
5/ 5/2n3 + 82 + +4/3r3
+ 23
4/523
f1 == + x3
91 = Fo + 1/303 2/3
f2 -3/2x
3 /2 5/4xg
92 T1 + 33/2x3
2
5/32g2123
2/3r
2/320022.3
1500g/s5566m67 5/12ng43
5/ +1/92/11
21 +1+3/203
f 5/2-//21111
5/82//33
93 = 12 +33
5/4z/a3
5/6
+ 5/3200123
3/2mgr103
+
9/ 9/4mp33
+ 1/2rf02
1/2rfa3 + 1/202 1/2r3
f4 = -5/81113
5 /6 1250
=
5/24na12rg 21: 31/12rg22
3xn
5/18x10215 5//111353
+ 1/20102
3/4r2r3 + 1/2x2 1/22g13 23
fo f== f 3344002222 - - -3/420011241
+
+ -9/40o2ag
5/3r003 - 10/33aa3 +
20/9m113
40/9z103 - 4 1/4 -22--34440 3/4r213
2x223 6r 2r
+ 1/3rg 2/3
fi Tg 1/3r3
Tu 1/323
f2 = -1 #
+ 1/2 + 1/909a3
92 = 51 + 11/203
3
1/62 23 + 3/523
f3 = 1322213
3/ 52 1233 - 1009002 +
= D2 + D3
5x0 1/3rf5223 + 3j 7/613
f4 1. 1/2001132 + 4/5 + 2oaa
x + 3/52z
3/5x023 + 1/5x,2/
1/
4/15x//3
+
4 23
fo -5
3/ 3/10xq2fa3
201012223 -3 -
3/2rn2283 4 12
3/4002223 + 1/20043
+ 3/ 3/1000
1/100fa503
3/5x102 + I1 122
3/5x,1223
+ 1/203a3 + 1/60243 5
3x4
27

---

Table 10: Success examples from the D
(Q)
test set.
ID
F
G
=1 1
91 To
2x + 1/4
6 =/ - 1
= 5/44 1/2
5/4rfut
T1
5x4
0
1/2xj=1 -ija 1/807
1/330
324 +5/32g7574
32 150301
52 x +2/5z 224 - -
I3 = T6 T
93 = 02
50
x 2/5 + 2x 5/2
1/40
2
Toz
21
2x 1
1/40fa1 4
4/30112221
1/152/232
12
-3/521024311
3/
20104
2n
-4r13 11/22114 20/3./
4rār,
1/30233
60/30321
1/54343 20x5x²
2- 4x3a 8/5agu2
80327 10
38 T23341
1/5022331 -2
2/2552274
22/5.g7322
1/20gT3 Tz
13
2r 1 + 1/42g
x + 33+3/200 3/2x1 11221
5/3zj
S1 = 1/2000142
+
1/ 1/2
J4 33 + 5 1/5a2
+ 1/2m,, 2/5
4/3r0=qx33
5 5/3x0=/03
5/ 5/62001224
1/2x02 122
1/20001122 222
1o + Su00
15 15/2n02143 F4
25 25
5/ 5/200022
+ 1
1/2
4 /30oot4
75 75/22g0301 2 - 25/ 25///220 22/220222
24
+
Inazei + 5000384
25 48023
1/2nfa2r4 1/221=3a4
1/80/a354 - 4/33a 1
4/3x
sf1za1
5/34faz0) + 11 11/3rf133
-1/2:3r11/2233 5/12ri
1/8x -/3dtur-443r,r1-3
1/30
5/62g=] - -
4/3rgg)
2xz07
2/3rga/ 20/92332
+ E3
+
fo -2923
3/ 22202/22230
95 r + 3/2x1
1/2x]
5/3x
3/2000223+2023 + 200
1/ 1/40pa -3/2r
3//2/
02 rx - 3/88 +1/3011/
3r r4
5/302
3/2rga rt 3/2x215.1
30
3/8r203 15224337
+ 3/2022
29/ 29/42243r 47/4422222
29 100203
2020za4 + 5223
15
3/5rza - 3/20zz]
6/
5 5x
28

---

Table 11: Success examples from the 22 (F7) test set.
ID
F
G
S1 = xn + 301
= In + 321
f2 = an + 16 + 2
7 + x²
x
92 = r
f1 f 2r
91 F0
1
f2 11 + +2002
To 2x +2
21
3r +11
fs 26z1
-2x 3 + Ioo _ 20
3z -2
11=2m
16 1 + +30 + 1 2r +3a
91 = Fo + +z
2rf
3
2x 321
f== 1 32 - 22 + 20
92 = of + 2x
21 +2
2
2n 21 30
300 - To4l 2002 + 200 1 + Toal
In + 30 3
2r
fs f +2] -320a1
20 20
3m 3 2rjr
+ r 3
3rg x +
3r
3
21 +
fi 2n
200z
20
+ 2I0TI
+
= + +0 +
J + 2x 2x
4
f2 =
3 i
+
+
2
+ 16
2,2
- r + z
92 = =
3r 4
2
+ Tg
r0 +1
fo 1/
r
21 + 3 o1 -r +
2
+ 2
200 t
f4 - 3r
+2x
-3r
3r
T6 +
- +
21
- -xx
2r
3r
2x
5
f1 = 1i
+ 30 + ri
f1 = In -
2002
4 + 2m +.0
92 = =
3x + 3r
-3
f = =3
xozt
- xn - 41 3x +
= 40 + 2x
+ 2x
2x T1
7
f2 2r
3
3000
30001 +00 3x
92 11
2r r
r
2x1
2
3 + 21g
3r r 2n
+
2 6 + 2
2 T1
-r
- 3r -2r
r1
ft [1=212] +2 +r
200 2
30 31
2x
2
2 + 3rqx] - 2x
+ 3mp
+ r 2x
r + 3 +3
fi =
91 To
10
f2 = - =
+ 32
+ 2x
2000
01
3m 300 2x0
fa - 1 3
"
u +
3x - 1h
r
300
3x
+ 30
fi = + + 2r
91 To +
2
=2 x +3rr0
2x
2n
11
I + 32 - x
I1
fa I r + 2
+ 20321
30
2r
2
+ 3
200 +
3mm + 6 2r
+ 2r +2 -2r
f 2
2
2r
2x
30
3
+ m
r 3 + 2x
20
2 202
2 200
29

---

Table Success examples from the D3 (F7) test set.
ID
F
G
f 22-2aa
2rgar 1 -
91 40 +32
1/03
0
fz 23=-2z022 +3zgat - -21
- 20
92 11
323 -
26 + +30021 -30 + 22
2x1
x1 - 3x2 -3
fa 2rd 12
1
-3 21
42 -32 2x
3x2
risiah 22
Tn Inri
1od122 +.D
10:22-2111
1-2 1 +32
fi 41=30p 3x + +3 +23++
-2
3rgaj =3r 2 +
+262
+
2
2
2 -3m
-3
2/13-200 22
oi 2 30f22
211-11 +2
F1 + x2 - 3r
2rd -33
fi + 3r2
Du + 302
f2 3ay 2
2ng
+ 31 +2 +3
92 = 81 2
+ T2 +
2x 2n fa = 3 -
93 12
To 21 20 10
Tgaf02 20 + 202122 + Tn
3 - 3r 33 -2
f4 -
20j
ai 26 33
30 +
2 -1
20 26 20F1
2 212 +21
8102
3r, 12
fi = 1==2 2r
2
2 32 +3
91 F0
f2 3r102g
-3r 2
92 01
2
3ry01 + Tnzg -gg 3r
+ 31
3rf00 2122
2x +2
2002) fs 2| 20 - 21
T2
Ty + 20121 riz 21 20102
x132 + 3z
2x +2
+ 20
3r 1 + 3070r
3.3,
2n 220 +20
20 20f
2x 21
-2r1
10 33
3x +z
22
fo f==2nf=1 + 3r
T + 21 17
2a/ 20
22 + 2
20 - 3 3 + 2g 2r/17
30 + 22f 2n 3m12
35122
3r 2
30

---

Table 13: Success examples from the Dj (F7) test set.
ID
F
G
fi =1 3r3 223 +
fg = 21 - 3r 20 2xg - 3z3 +
92 = 11 - 3z3 + z 203
+
13 22g +2
2
f3 = - -2 1i - 2
12 3z3 + 2 +
32f5123 + 3
262122
I0 1223
300zi2 1o2z13 3- + 2002203
20022
30 -2g 22g
23
zス=² + 32/23 3- -2rjz3
f4 = 21 +
+ 20
91 = 33 3z3
3
32
+ 2 2
2-
3ajajaz
32
+ 2/41220
2rg
2 + 32
20 32
<6 3x -x00211
2
Tnriag + tozl
Int
+ 20g 1223
Jy3133 20
35 33 + 30pej
3 tot253
2r0
200
To 21o0223
3ro2223
3ri=, - 20/220 + +3z
+ 1233
ai02 + I3 303 -1
fo -ra + 34g
2
2njafaj - 2r
34
3afejas
30j
20
3x S + 2/21122
26-11223
20f2123 22ς 2064113 -
x6²1 + 20o 22000 -
2 3r
300221
35002
2 28or3 + 1on12-Ighh In 1og--np Io
23
F12523 - 2r
322ugtzzr t1313 +
2nd
f6 = -3rg1/2 - 22
2
30/2f2225
2 =n
22g
32g + 2x
3
22/0113 - 2n
30 2
22a3 33g 202
2
204f2233 + 1ona5
200z1052
320411313
320212523
3z
Jo 12 + 21 1222
2
3x0 0i
a/ + 33
212
+ 2r 25.3
201r r 3r r2
2x
2x
F3
h= 3rg 2103 + 2133 23
91 3p +
223 2
3
f== = -2 + 32
32 32 23
92 = 01
223
20/01 3n1r5 + 320
33
xfr203
rir203 + 2x703 - 01
3r10 + 22. 3
fs -2n
3r
+ 32/212223
12 2003 -3
ToT1Tg3
+ 2g314223
Tooao +
2r
321z3
1/
2rf 20n0+221100 22113
22 23
203 -2
2 f4=
22
= =
30f0103 22
2rp 2 12
20101
Tp
x1x021
3
32
3x
3x
33
+
2rix233
4113 2
31
20203
3r + +3
2.3
31

---

Table 14: Success examples from the Dj (F7) test set.
ID
F
G
f1 = + ff
3r4
91 = 50 2.
34
f2 -1oaf03 + 2zfazzi + 2izzry
92 I1 3z4
11-222331--- 333304
0
f3 -3afst33
93 122 ITA
20l1z0z04 - forifyt
20 + 3 2x02321
20
1112032 3131311 -2
24
f=== -21--11azzy 44423341 + 26
91 = 43 3z.
3ajas 3104f
31
8f42aj 20021a80334 + 32
rhr2 323r1
2r2r4 + -4 3z
fs 201011243 20114224 + atja
95 1 r 3zd
30j=ja1 + 31
+ 20g21
201z1 2n Jo 22
xiplaj- -2
20f 3nszsaa
+ 22103.332
301 231223344 + 21
3r 3 + 1344 12
2
I3 + 324
fo = - 1 2,
20
30 3
30
2104f
To - 2n
Tn + +f,233 31
2rf - -ff03 -5pr]
321 - 321z
2 J2
30yz +22 22
3 2xjaf43
24
-20 + x/2224
"0b12334
3 + 32f2fa3a1
207
+ 2f
2
20f
20grza7 + 2/0221
2ro0f1225 - 3000
1oz1322j4i Int12223 + 3212
-30011
Tnti34 2ng233
2 22
To
3r4031344 + 22
+ 301021
3r 3r 210324 2 20
fis + 32T
f1 =
91 = 50
28g
f2 T2 + Fn 2r4
92 01 F4
3
fs 3x. + 300 Tg213234 20
32 + 24
F4 + 221022 + F3 x -A4
fa = 22000223 + 2r
3
94 F3 F4
30 3
+ 32/2220
3aq + 32m + 35 + 1703.
sfr334 + +af2z 3
x22)
I4 -4
fs= 122 22 -00 -
95 =
32/ 2r + 20 + 30 +
30 3 + 3x + 30013
20q23 + 3xrrr 3 201 + 42
3x 2x3
32

---

Table 15: Success examples from the D2 (15 test set.
ID
F
G
J1 vo 8
91
Ig 8
2
f2 8
2x 12 Fool
82
42 vi
-xj +1
fs T
+ +6rāzt
? 152
5ang + 5
50g
14
4mg=1 9x
10x
9
3
10ma2
12
+
13
7x
+
7x 82
Ji = Grff
6x 2 11ag01
91 40
10x +
11x 2x
4
= 3m/=1
10mga7 30grr
Fool
92 1
3 - -11001 152g +
=10x 3
+5 11x1
15x
- 1==13021-200
+3rrg
9x
8a3=1 1427af - 1laga
620
15mg=] + 12xoa + 15
11
6z - 11x -1x9
13r 133 -x
/4=-7xh<4 -00 -
62
Trira T 1002-3r-mm 20/
3
6
-3z0a
36
12xpa + 13r 1 +
+ 30
10x Φ1
fi = 1521
91 30 92 1
15x1
6
f2 4rg + 2x 10 2 - 5 + x
83 = 3 14x
+ of + 3
12x
-xxaa] 6 400 12x
6x + 2x1
fi 6z
10r 2 + 557
91 Tu 12
7
f2 1
12x
11 f 6x
92 T1
12
fa = 9u
15xh + 6. 13rgx²
11x Argar
3zp²1 9z1
f1 3x x
12r + of
= TO + 10x -4
14
f2 = 14x
- 11x
Gaga 200 15a
92 = x
10x
fi 4x +
2 1 2x0 +8r02
To + 10
15
xoza 3x021 11x + 9xm
f2 = 62f21 5 + 6r + 3
92 = 5z 9x 2 14x1
12xjja + 14ziaa + 11xja1
14m
9xze + 52/21 + 13
3 462
-00
+ +2 ff -
fs=-15xf41 -12x +5 -
11xg=1 7z70 + 12x
14rfa1
62/2 - 14 - -4
3r +15
4mgaf -
12m64
8 - 12
+ 8xp 10
fi Ii + 14x1 +3
91 Tg
+ 14x; +
16
f2 11r S
+ - 13xh
92 1
20 2
90 - 4o + 7x + 3x 10x
fa= A 7m gag 5 r1 4r
3 n
8 13
300
20 + 9x
2 14x
4x + 8T
33

---

Table 16: Success examples from the D3 (F) test set.
ID
F
fi = 11 + 8 - xn22 + 62
14x2 + 9x - 7x2 + 15
15rg22 + 10mp32 + 12 15rf
4
15x129 + 3r1 10 + 10
80,42 +
4r, + zz + 9r 62
12x2
f2=5z8r110
2 +826
=
92
4x2 11
5
4efor
154
221 3
2 41o
4.q0ia2 + Troafah
130osf22
2000f43
4mgaf Fo
8062122
10 + 14mp3j
30gz1 - 30022 - 3r + 42
13x +50 +17
14x
f== 12rfr1 + 1324a + 115
93
22
9
6x
12x2
90/ar12 + Taper -0
T
2xf211zg + 9x
22
9060142
12xf
+ 11
152f0122
14z6a]
92
2 2
12
15
20
+ 13
13
7 m
+ 25
1
+ 15 2
13 25
12 2
+ 11 122
13 202
7
+ 140001
2002
+ 20022
13ara2
T0 I1 9x + 14ma2
4x² - -11
[4= 14
+ 10 + 2ngrfer
5
3rzafaz
5200122
11z 6 + 4rosfa)
10mgafa)
12
To + Safa
10a
10xfa] - 3r a + 14r
3xfx; + +6rfaz +r 13r +
2 147fa0 - 2r + 10
7xf 11r
14r 9r.
=7z2 15
f1 = 7 80r 6x
91 CD 10
f2 = - 527 - 12x
+
12
92 = 01 10
5
D0 f x2 4
To
3z
10
fs -1200113
T2
4
= 42
3x 10x
+ +1
10
f4 - 150g
10
13rfa3 12
11 -9 + 5
3xfx 4x²
15x + 11x + 22
===
Du + 12x + 13xz 2
f2 = 12100 2
14 12 + 11x 12
92 = 41 + 5x 14x² -
9
12r 11x 2
f== 12-99
5 + 15
= =
1 22 15200113
10 + 270
12x3 + 13r. -2
f4 = 12
2r2r2 14
6apaf 11sse,a
2 1z 2zf102
72j
Tag=z + 5 + 2ry02 + 13r0afa
14x 132g0
12002502 +
f== 2 ( +
7
10x
8
3
11 - 200 x2 - 14
13x x + +1000113
11
+ x
13x + 2 + 11
2
+ Ti + 8x
12xg + 9x + 5x 14x, +9
34

---

Table 17: Success examples from the Dj (Fs1) test set.
ID
F
G
f
12
91
40 +
f2 = baiay + 30023 + 6zf=3
T1 22
+
= 11 +
0
32 Txs 7
f3 = -
50001
= 12 +
10x7 5
12
14200112 10zgzga3 + 10zf2243
15 4rj -
91
12x 22
12nqa² + 92f
9mf 201002
12x1 - 1002 +
fs = 6x8²1 14mg + 13xj2faz
1izjzies
122 + 1330212
5002i03 2002
26 + 8z 50/23
8xf2; +e)
6213
11 + 11aaag 111133
11x203
15x3 1503 +8
f1=400mz3+ +ann 10 +3
= 10 + 929 15
10 +
6
12=-41
3 11
92
5.3 7xğ 13x. 13
10 - -10
1n314g 00 + 2ig
9ng - 15
fa = -11
7 + 152ga3 12
= D2 800 + 3x3 9
12ng03
11z
+ 140p03at + 1622az
10mp01 1010z21
-13004343
+ +
7a5a3 + 92303 5.3
7x3
13rg 13
f4= 44-4m11122
3 12
=
10ng - 100m)
6
14mpa
80021355500 42
8x1=5 + +3x
12
- +
23
5.0 1222
15 + 6
4
30 3r
13 _ +
12m
9xg23
9 + 8r
9xf
6αf 11rf
11z700 9r
32 + 4z 8x3 + 333 9
- 1220
Tatzr 13r
132 rga
6ag 13
12nf22 3xfezaj
5262225
15m
50001 + 10200102 + 13
3
4 -300233 - + 220
7xn22 + 3
2no
14
14xp.2 + +11 + +5 20
Gr
15012553 2r 15
7xioa - 12x. +3 +44
+9 +
4mfara 4rz + 1-6 13a. -154
7
15x3
35

---

Table 18: Success examples from the D5 (IFz)) test set.
ID
F
G
f1 13 4xf + 9r x
91 57
14x4 + 15
f2 +2
13 1
I1 + 824
0
6r3 - 13r 11
2xza. + +2 +
+
93 = D2 - 14x4
-3
+8
2202/133 300zi=344 + 15
f4 -61jr1032
91 33 + 800
+ 6
10 + 134g4yJ4
+ 7 20
11 + 5 + 9213334
+ 112123
80201 - 14x +5
f= 10m 72j090zz4
+ 15x
95 = =
52602 3 +
5
1220012001+20022 +9m02322
60034 + 320
12 14xf
3x 7
3r3.4 14x
14x20}u4 150222
502r
+ 82 14x4
fi= Ta - 1 - 12r 60 133
91 = 50 12
3xjus + 80304
f2 13a
92f - 2
= + 11
8
1107 + 8 + 4rf
1001 + 65 + 12105
221320z41 + + 13r3 +11
f - 132fz1 10ffff-112-jp11 +82 42
D2 13
4r + 22, + 122
+
13riæ3a4 18331
15
1==-10ozf+ + +7f
= 03 15
2rf=3a² 12x3
+ xfæzs]
4x
12
+
62
15 r2
14x 12r
6 3r203
13
31=3300 + 13
1
95 44
+ +
4rt + 4x 2r
+fffas
132fz)a1- - 52
14xfa]
13
90ÿz1 - -e2=1-127721 7 +3x]
fo = 111/
3 + 8204
10ag07 -0000=_110000044
3x
7
2x + 7 - 12
121
6012z03 155
3x
82.
r32z24- 15532
J7 10
14
200z|0z21 + 200
zozfaz
321210221 + To
15x00123
11zpzie4 + 81
11roahazzg
10xfa3
7rf 13r723
14xfa20074
14xfxz24 + 1121431334 +
2010303
-222-6 6r
15x - 12
12
36

---

Table 19: Failure examples from the D (Q) test sets for 2,3, 5 (ground truth v.s. prediction).
ID
G (Ground Truth)
G' (Transformer)
15
91
1/4xf
5/4z]
+
2/331
5/4
9 2g + 1/4x + 2/3r1 - 5/4
92 = zî
-2/3z
4/3z/
+
g = x 22/3x
2 +2
26
91 Iω
-
1/5z/
+1 1/2x/
9 zα -1/2z}
1//0/
x1+2/3
92 z]
-3/521
4/3
92 z - -1/2x²
3/5x1
4/3
91 = 2g 2x
9 2g 2x1
36
92 2
5/2x/
1/4z/ 1/2x/ 1/3
9 z + +5/2x
5/4x/
1/2x 1/3
91 = + 4x - 1/ 1/5x3 + 5/4r2 + 1/2
9 = zo + 4r - +
12
92 = 21 1/2
113322
g2 = σ1 -/2
3/2
3/2
93 5 - 3/2x3
5/3
22 2/3x
3/23033 5/3
91 = dμ + + 42 5/302
91 = dg 2/332 1 + 4
15
f2 31 2x
453m222
92 #1 5/332 +2
93 22 4x
23 +
93 0 + 4x
7
2 + 22
91 = Σш + 202
9 = Φω + 2
16
92 1/5
92
1/5
93
20
+ 1/502 +
7 x2 + 1/522 +1
91 J0 2/3r3
9 ио 2/33zz
92 4x3 + 1 1/4r3
92 +/4433
6
93 = Σ2
Iड -3 3/5
93 = I² 23 + x 3/5
94 23
5 91 = 3
+ 413 + 4
9 ПЗ 5 4r3
4x3
91 = Σ0 3
92 = Ø1 1/
1/5x,
g = Æ1 1/5x3
7
93 Σ2 2/ 5x
+ 5/222 2/303 3/5
9 x2 2/ 2/5x
+ +//213
2/3333
3/5
94 r3 4/5z
T3
x3 4/5ag
3r3
33
91 = + 1/4
-
9 xо + 1/443
-
f2 = I + 2x
9 #1 2r
16
93 Σ2 2x 3/2
93 22 2I 3/2
7
91 = 23
5z
1/2
2
5x
1/403 3/2
91 do 5
3/5z/
+2
g 06 5Λ 3/5r
4x +2
92 - 2/5x/
1 1/32a
1/3 1/2xx4 +3/5
9 2/5x
1/3x
-1-1//2x+3355
93 = 82 3/524
93 ø2 2/5x4
94 33 4
4/5x1
12. 3/584
94 2 4/5x
34 3/504
95 = x4
5x
+ 3/ 2xx σA
/ = x + 3/2x
21 -5
91 = 20 r 4x 5/3
9 = T0 Σ
+ 4.A 5/3
92 31 r
9 I
F
+1
7
93 =
9 = Σ2
91 = F3
2x + 4/3x1
91 X3 + 2x
4/3x1
g5 54
9 X 2/3a1
91 + + -
9 00 2
92 = I + 11322
+ +/332 : + 5xx + 3/4
g2 = L + 1/30
+ 4433x/ + 5x4 3/4
8
93 F2 + 1/2x
34
9 Σ2 F4
91 Σ3 5/4z
x2 x
9 Σ3 5 4x
x x2
95 = x4 4 4/30
+ F44
96 J 4/30/
37

---

Table 20: Failure examples from the D (Ir) test sets for 2,3, 3, 4, (ground truth v.s. prediction).
ID
G' (Ground Truth)
G' (Transformer)
2
91 20
+1
9
3r
+1
92 zi
-2
92
2
6
91 -i
3r
+ 3z1
2g
2
3r
3r1
92 = z
2x
x
$2
2
8
91 Σg
32
+ 2x
+ 2x1
9
3x
2x
2
92
30
+ 2x
ø 9 20
92
3r
2
91 = 00
12
22
8
02
92 21
93 22
12
20
382
22
+
2x
22
91 Tp
Р1 X0
12
92
3x2 2
92
3r 22 +3
93 22
22
+1
91 = Zu 3
2x - 22 +1
91 = Σy 3r,
2r
15
18
f/2 31 12
3x2 2
9 I1 F2
+ 352
93 3
3r
+
93
3r
12
91 Zо 3r
3r
9 æ0 3r
3rl
0
92 2r
23 3r3
92 21 2r
23
3r3
93 203
2
X2 + 2r²
-
94 33 323
9 X3 F3
91 3
91 Z0
92 = + 32
+ 23
3x3
+ 3r3 -
+ 3r
x3
3x3
30z
-
93 32 3x
2
93 Σ2
+ 3r
2
94 23 2x
3
2x3
94 23
2T
3x
2
91 +
F0
5
92 I1
g I1 +
93 = 3
93 = X2
94 Σ3
Р. Σ3
91 Σо 3r4
9 = Fo 3
92 J1
9 I +1 93 x2 + 2 91 23 +3
1
93
3
П4 J3 3
55 21
Р X
91 = Σμ 3x
91 = Σ0 24
92 I1 3x
2x44 +3
g I1 + 3x
2
2
93
3z
3Σ4
Р X2 3r
3r4
94 F3 2
91 X3
95 24 3ΣA
9 Σ4 3FA
91 = +2 2
91 = Σ +2
92 I1
g I1 +2
14
93 22 + r3
2x +
3 -
93 I2 + 2
2x
3x,
94 = Σ3 3
9. Σ3
95 54 F4
5 11 + TA
38

---

Table 21: Failure examples from the D, 3 test sets for n 2,3, (ground truth v.s. prediction).
ID
G (Ground Truth)
G' (Transformer)
91 = 14x
9x. + 12x}
+ 14r1 + 15
g = 2g 14r
+ 9r + 12x,
+ 14x; + 15
0
92 = z + 15x
5x 7zj
g2 = zं
11x
11x;
fi 370
9 30
92 31
92 = #1 -
3
91 = Iд
Sa + 8
9 = H0
8.
+ +81
92 2
14r
10x + 2x +
92 x
3x
10 + 2x +
91 = Σμ + 5
Φ = 2ω +
0
f2
Sa
+ 15z2 5.2 11
92 #1 8r
12n2
8.2 13
93 22 2x
+ 1502
+
Р3 = 22
2n
15z,
+4
91 14x
+ 13x
10
6.2
10
91 H0
2r
+ x
10x3
6 - 10
92 31 14r.
4x
522
8.
92 Æ1
14xh
4x)
5
+ 8x
93 22 7
+ 7x3
9 Z
2x
2x
2x
2
91 = + 15x
12x
13x2
10
7
= Zo 15
12x
13r2
10
92 = Σ 9w
92 = X + 9
93 22 15
5x
93 2 14
+ 14r
1403+0
91 Tp + 11x3
4r 8x3
9 = 30 + 11
4 803
1
f2
7
92 #1
93 = Σ2 + 2
7 = 22 +
94 Σ3 5 6r3
94 x3 5
11xg
91 HO 6az
+ 13x3
9 ип 6az
1323
92 = + 12 11 + 10xg
15xg + 10
+ 12r
11x3
+ 10x3 3
15xg + 10
3
93 = 22 82
15x3
= X2
SI
ST
Sz
15zz
94 Σ3 2
2x
533
9 Φ3
21
2
503
91 = 523
+ 13
9 = Z0
5I3
13
92 Σ1 + 11x
13
92 Σ1 + 11x
13
5
93 22 503
9
9 22
5 -
91 = 23
2x
11x
62z -
= Ø3
Σ
11r3
10x3 -
91 = 0о 10x
12x1
11x,
13
9 X0 10x
12x
11x, 13
92 = + 2
= æ + 2r,
93 = x2 + 7
11x
12. 2 + 7 - 13
93 = ø2 + 7x
11x) ] - 12x² + 7 - 13
94 Σ3 5x
x
15x
4x
94 ΣΑ 5x
15x
2x
95 = 24 13r
+8
x 13x
+8
91 = Σо + 7x
+
3x
+ 15
+ 3r4 +9 9
9 = To 2r
3x
+ 15x
+ 3r4 + 9
92 = I1 3
12x
62
F4
15
g I1 + 6α
11x + 12x
520 +
2
93 + 6
7 = Σ2 6
94 = Σ3
15x
3x
13 - + 9
91 = Xy 15x
+ 3z
13x
2
g5 4
7
5m
13r4
9 2 7x
5x
13z.
91 Zо 13r
10x
11x2
5
9 Z0 13x
10x
11x
5
92 = F1 + 10x
13r 12
92 = Σ1 + 10x
13r
12
3
93 32 12r
12x
9 Σ2 12
+ 12r
94 = 4
= Σ3 15
95 x 9x
3r
9 T 9x
3x
39

---

Table 22: Runtime comparison (in seconds) of forward generation (F.) and Transformer on timeout examples. Timeout limit: 100 seconds. Red cells indicate timeout. For each configuration, up first 10 unique samples are shown. Transformer successfully predicted the correct Gröbner bases for these examples.
Sample ID
D
n
(0 0.3)
F. (STD)
F. (SLIMGB)
F. (STDFGLM)
Transformer
23
0.005
100.0
0.008
0.110
49
100.0
0.018
0.008
0.253
64
0.006
100.0
0.008
0.147
171
100.0
100.0
0.015
0.238
341
100.0
0.011
0.008
0,212
384
100.0
100.0
0.009
0.142
423
0.123
100.0
0.008
0.167
530
100.0
0.005
0.010
0.197
542
0.005
100.0
0.008
0,212
552
100.0
100.0
0.008
0.185
D, (Q)
0.2)
Sample ID
(STD)
F. (SLIMGB)
F. (STDFGLM)
Transformer
61
0.005
100.0
0.009
0.170
76
0.004
100.0
0.008
0.292
130
100.0
0.014
0.008
0,227
153
100.0
19.384
0.009
0,220
175
100.0
34.825
0.192
0,390
208
100,0
0.013
0.008
0,223
269
100,0
0.006
0.069
0.320
295
0,005
100.0
0.008
0,282
320
0.005
100.0
0.008
0.309
333
0.135
100.0
0.008
0.296
D, (F7)
n 4 (a = 0.3)
Sample
(STD)
F. (SLIMGB)
F. (STDFGLM)
Transformer
407
100.0
4.788
0.013
0.189
717
100.0
0.004
0.007
0.135
765
100.0
0,004
0.007
0,122
915
100.0
5.832
0.009
0.136
916
100.0
0.022
0.008
0.266
D (F7)
n 5 (a = 0.2)
Sample
(STD)
F. (SLIMGB)
F. (STDFGLMM)
Transformer
74
100.0
100.0
0.045
0.314
121
100.0
100.0
0.011
0.285
256
100.0
100.0
0.008
0.144
267
100.0
0.005
0.008
0.284
274
100.0
0.006
0.007
0.209
433
100.0
38.895
0.013
0,285
438
0.432
100.0
0.011
0.270
492
100.0
0.020
0.007
0.144
568
100.0
0.008
0.007
0.223
766
100.0
100.0
0.009
0.144
D (F
(a
0.3)
Sample ID
F. (STD)
F. (SLIMGB)
F. (STDFGLM)
Transtormer
954
100.0
0.157
0.008
0.123
Dj (Fa1
0.2)
Sample ID
(STD)
F. (SLIMGB)
F. (STDFGLM)
Transformer
196
100.0
0.051
0.007
0.267
715
100.0
26.161
0.008
0.160
40

---

Table 23: Dataset profile comparison between (k) and D (k). The standard deviation is shown in the superscript.
Metrie
(Q)
(Q)
D (1')
DF'Fa))
D7, (Fa1)
Size of F
2,56
3.06 3 20.82)
3.03(20881
3.04
3.01
Max degree in F
1.97(#21.55)
(1177)
(291
5.56
1.18
Min degree
2.50 $1000
4.19 (11
2..0
(...04))00)
(.85(#1163)
4.64
# of terms in F
10.56(++6.02)
15.64 (5.64())7000
13.46(#*7.14)
20.02 (#9.60)
13.73(#7.10)
20. 20.79(#*..8))
Gröbner ratio
((+0)
((+b))
0.002 0.002 (+0.000
(t0.040
((=0)
((*to)
Size
2
2(+0)
2
2
2
2
Max degree in G
2.48(+1132)
4.09
2.53
(.94
2:53
4.09
Min degree in
1.21 (:b0.54)
(...2)))
(0..5)
2.37(#1.21)
1,21 (#0.57)
2.60(#11.2))
terms in G
3.69(#1.65)
6.65(42.32)
(.72(21.64)
6.31
3.74 (.74
6.70(42.32)
Gröbner ratio
(200
(2:0
(200
(20)
(=00
(#00
Table 24: Accuracy and support accuracy of Transformers out-distribution evaluation set DI (A:).
Metric
(Q)
D (17)
D (1311)
accuracy
83.8
36.1 52.9
support acc.
86.7
62.0
54.4
Table 25: Katsura-n on Q(21....,....................... Fx]. Katsura-5 is not presented because of its complexity.
F
f1 2g + 2r1 -
91 2g +
2x1
2
f2 26
Fg 2x
92 2
21
f1 26 + 22
2x
91 20 60z
+
3
f2 x6 Fg + 2x 2n²
92 21 30z
76
2
T2
fa 2 20
93 22
4
10
42
RT T2
f1 Zo + 2x + 2r2 253
91
23
+
11415422222 6
33
+
9146536848
21
4158574456
838935856
4
x3
x3
5913075
23
f2 20 20 + 22x 2x 22
92 9719772
5913075
J
1971025
2015
2
73975630752
23
6
12121915038
276094
1496
1025
197 1975
$14792828
1678512
9158924
197 1025
T3
fa 20001 -201002 21 2x203
93 02
238
1971025
03
1548616608
38-0228774
120
197 1025
20249
132524276.
30947828
59 3025
T
T3 5913075 T 5913075
f. 2ro02 21 2x1 D2
94
2
+ J3
5346 23 8019
3564
1266
23
12830
33
41

---

1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the
paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction present the scope of the study and its contribu- tions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We clarify the problem setting in this paper and potential future work in Section 4.1 Besides, several open questions are discussed in detail in the Appendix H
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
42

---

Justification:
All the assumptions and complete proofs are provided in Sections and
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provided detailed description of the experiment setups.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
43

---

Answer: [Yes]
Justification:
The code to reproduce our experiments is released.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
stipaiisssooooiocyyy. for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the training and test details to follow the results are provided in Sections B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Error bars were not measured due to computational costs. However, we conducted experiments on various setups and provide their details in Sections and
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
44

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The information is given at the beginning of Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http://pw////oeooooooo///o/////a
Answer: [Yes]
Justification:
We have confirmed the present study meets the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: This paper focuses on the learnability of a mathematical task, and we cannot see any urgent social impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
45

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
This paper does not have an evident risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
46

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
47


Reviews:
[{"review_id": "xuTrB1ewK9", "reviewer": "Reviewer_BQDD", "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.", "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": "It is not clear whether this work can be generalized to beyond 0-dimensional ideals.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduced a novel method to compute a significant problem in computational algebra, demonstrating high accuracy for certain types of rings. The efficient backward sampling methods are less explored and may facilitate further ML studies in this field. Additionally, this backward approach helps restrict the Gröbner basis to applications of interest. The paper is well-written and easy to follow.", "weaknesses": "* I have serval questions about the choice of the 0-dimensional ideal as the scope of the study : \n(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? \n(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? \n(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. \n\n* 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. \n\nIt 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. \n\n\nReference\n[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.\n[2] Charton, François. \"Linear algebra with transformers.\" arXiv preprint arXiv:2112.01898 (2021).\n[3] Golkar, Siavash, et al. \"xval: A continuous number encoding for large language models.\" arXiv preprint arXiv:2310.02989 (2023).\n[4] McLeish, Sean, et al. \"Transformers Can Do Arithmetic with the Right Embeddings.\" arXiv preprint arXiv:2405.17399 (2024).\n[5] Kamienny, Pierre-Alexandre, et al. \"Deep generative symbolic regression with Monte-Carlo-tree-search.\" International Conference on Machine Learning. PMLR, 2023.\n[6] Jha, Piyush, et al. \"RLSF: Reinforcement Learning via Symbolic Feedback.\" arXiv preprint arXiv:2405.16661 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful and constructive comments and thorough review, as well as many pointers to related papers. \n\n### **On Weaknesses**\n\n**Choice of 0-dimensional ideals.**\nWe received several comments/questions about this assumption from several reviewers; please refer to the Global Response for the motivation for the choice.\n\n\n**Particular v.s. generic.**\nYou seem to find contradictive policies from our claims: \n> [l.178] \n> ... focus on a particular class of ideals...\"\n> \n> [l.183] \n> ..., the form of non-Gröbner sets varies across applications, and thus, we focus on the generic case and leave the specialization to future work.\n\nThe former claims the need to focus on a particular class of ideals as it is difficult to cover all the cases in a single work. The latter says that our way of particularization is more driven by a computer-algebraic viewpoint and not biased toward a single application. We will update our manuscript to avoid such confusion.\n\n\n**Hybrid input embedding.**\nThank you for completing our literature survey! In our reading, [2,4] rely on traditional discrete embedding based on mantissa (between 0 and 9999) and exponent, which requires keeping a large vocabulary and learning the numbers' relation from scratch. We found [3; Golkar+, Oct. 2023] to be close to our idea. The difference is that in their work, a real value is represented as the length of the embedding vector of the number token, while we use an MLP to find an embedding directly and have more degree of freedom (i.e., length and direction). Interestingly, Figure 1 shows that our embedding also encodes the values by the scale. We need experiments of Gröbner basis computation learning to check if their method outperforms ours and also discrete embedding. We will review and include them in our references. \n\n**In-distribution accuracy.**\nWe appreciate your pointer to an interesting work. It seems that the paper (particularly Table 2) indicates a potential generalization even for NP-hard problems. It is also very surprising to me that models trained on a 100-variable dataset perform better in a 600-variable dataset than in a 100-variable dataset. We are not sure if this is called generalization (although it is great). \n> 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.\n\nWe don't claim that a generalization of learning is unachievable for NP-hard problems; we only present our picture of using Transformer for Gröbner basis computation. The learning approach may provide faster computation than classical algorithms, but the problem itself has been proven NP-hard, so machine learning models cannot break this. \n\n### **On Questions**\n**Dataset diversity.**\nTable 6 provides several statistics of the datasets (we will make it cleaner in the update). The degrees and the number of terms have certain variances, which empirically shows diversity. Tables 4 and 22 also present the existence of hard samples for mathematical algorithms, which supports a certain diversity of the generated samples. \n\nTheoretically, defining and measuring the diversity of generators is not very clear. For Gröbner basis sampling, we performed uniform sampling for degree, the number of terms, and so on, so the Gröbner bases were sampled uniformly randomly in a sense. For non-Gröbner sets computed from the Gröbner bases, a reasonable starting point would be the question on the reachability: can we sample all possible generating set $F$ such that $\\langle F \\rangle = \\langle G \\rangle$ from a Gröbner basis $G$? As of now, we suspect the answer is negative because we are based on Theorem 4.2 (2), a sufficient condition. We are now tackling designing an efficient algorithm based on Theorem 4.2 (3), a necessary and sufficient condition, but this requires a deeply algebraic discussion. \n\n**Generalization to the positive-dimensional case.**\nPlease kindly refer to the Global Response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IbLDBhsDaj", "reviewer": "Reviewer_YTLb", "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. \n\nTo address this learning problem, the authors address other interesting problems such as random generation of Gröbner bases and the Backward Gröbner problem.", "questions": "1) What is the largest number of variables for which the machine learning method gave interesting results? \n\n2) How does the accuracy of the model decay with the number of variables? \n\n3) What is the relation between the number of variables and the time necessary to train the model?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper provide an interesting experimental evaluation on how transformers can be used to learn Gröbner bases. The random generation of Gröbner bases is also interesting.", "weaknesses": "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. \n\nThe 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. \n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thorough review and insightful comments. You raise the characterization of a subclass of polynomial systems as the main concern, and our rebuttal mostly focuses on this point. We would like you to refer to the Global Response as well.\n\n### **On Weaknesses**\n\n**Characterization of a subclass of polynomial systems.**\nWe appreciate your fundamental remark. We acknowledge that our paper does not provide a comprehensive characterization of the subclass of polynomial systems that can be efficiently solved using our transformer-based approach. Generally speaking, it is difficult to answer what problems can be solved by Transformers or what sample distributions are learnable by Transformers. \n\nInstead, our study currently approaches the question: for what class of polynomial systems can we prepare a dataset efficiently for Transformer training? The trainablity in this sense should come before the learnability from a practical point of view. As an initial work, we break down the trainability question into two components: Gröbner basis sampling and backward Gröbner problem. These can be answered affirmatively through the design of algorithms. For the former, we suggest ideals in shape position, Cauchy module, and potentially, ideals of points (cf. Appendix~G). For the latter, we suggest 0-dimensional ideals (Theorem 4.7).\n\n**Number of variables**\nThis is also an important point. Ultimately, we envision that Transformers will be used for large-scale problems (i.e., problems with many variables and equations) that mathematical algorithms cannot address. \n\nHowever, the number of variables that Transformer can handle is currently restrictive. The restriction comes from the current simple tokenization of polynomial systems: for example, {$x^2-10, y$} is tokenized as $\\texttt{[x, **, 2, +, -10, <sep>, y]}$, (cf. Section 5). Eventually, a single $n$-variate term requires $O(n)$ tokens, leading to a long input sequence for large $n$. As well known in Transformer literature, the space complexity of the attention mechanism scales in $O(L^2)$, where $L$ denotes the input length.\n\nThe scope of this study is to establish the problem of learning to compute Gröbner bases, and thus, we tested its learnability based on a standard model, including tokenization. For scale-up, one may be able to embed a term by its coefficient (i.e., single token) and inject the exponent part as a position vector because this is literally a position in the term space. We are currently working on it in our follow-up paper. \n\nIt is also worth noting that even for $n=5$, we have observed a potential advantage of using machine learning. Table 22 shows that there are several instances in which Transformer models successfully compute Gröbner bases in less than a second, whereas algebraic methods take much longer (100 seconds and timeout for most cases).\n\n**Balance between theoretical and learning parts.** Thank you for your fair evaluation and great writing suggestions. We indeed have a great algebraic interest in random generation of (non-Gröbner basis, Gröbner basis pair). We adopted the current structure by taking into account the potential readers (i.e., NeurIPS readers), who may be more interested in the learning part. We will reconsider the presentation. Thank you very much.\n\n### **On Questions**\nWe appreciate your insightful questions. We believe the learning approach of Gröbner bases has an advantage over algebraic algorithms for large-scale problems. However, as described above, the training on large $n$ requires an efficient input embedding of polynomial systems. We could also try larger $n$ by using a few more GPUs, but we considered this to be very interesting. It should be more reasonable to design an efficient input embedding for polynomial systems first and then see the impact of the increase in $n$ on the learning complexity. Here, we only provide quick answers to your questions below.\n\n**Largest number of variables with interesting results:**\nWe have only tested up to $n=5$. Even at this point, we have already observed interesting results, such as the contrast between infinite and finite fields (Table 2) and Transformer supremacy (Table 22). \n\n**Accuracy decay with the number of variables:**\nThe accuracy change with respect to the number of variables is given in Table 2, but the results would also change the density parameter $\\sigma$. This is also a consequence of the input length restriction. \n\n**Relation between the number of variables and training time.** We collected the training time from our experiment log and summarized it below. Note that the training time here can have been affected by the other processes running in parallel, so these numbers can be regarded as upper bounds. The table shows that we generally need longer training time for larger $n$. Not shown here, but we also tried longer training but we only observed a subtle improvement. \n\n|  | $n=2$ | $n=3$ | $n=4$ | $n=5$ |\n| -------- | -------- | -------- | -------- |-------- |\n| $\\mathbb{Q}[x_1,\\ldots, x_n]$     | 5.8     | 8.4      | 9.8     | 12.5    |\n| $\\mathbb{F}_7[x_1,\\ldots, x_n]$   | 6.2     | 12.6     | 8.6     | 9.5     |\n| $\\mathbb{F}_{31}[x_1,\\ldots, x_n]$| 7.3     | 10.4     | 10.6    | 11.8    |\n*The training time in hours.\n\nThanks to the questions, we realize that there are two interleaving factors that affect the complexity of learning. For larger $n$, the Gröbner basis computation becomes algebraically more difficult. At the same time, dataset generation algorithms generate larger systems (i.e., longer input/target sequences), making learning more difficult from a machine learning perspective. We have to find a way to separate these factors for future discussion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OVPCxisO5h", "reviewer": "Reviewer_WoAv", "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.\n\nThe paper gives adequate solution for both of these issues and implements it,", "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?\n\n2) Why did you limit the rings to Q,R F_p. Why not N or p-adic numbers?", "limitations": "Exemplary!", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper tackles a really tough and important problem with a novel approach. This is done while also placing the work nicely in the existing literature.\n\nI enjoyed reading the open questions section in the Appendix.", "weaknesses": "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\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your strongly positive evaluation of our work! \n\n**Benefits.** \nIn general, if the terms of the input polynomial system $f_1,\\ldots,f_m$ are fixed and the coefficients $\\{c_{i,\\alpha}\\}$, where $f_i = \\sum_{\\alpha} c_{i,\\alpha} x^{\\alpha}$, are considered as parameters, it is known that by using the comprehensive Gröbner basis theory, i.e., the parameterized Gröbner basis theory, the terms appearing in the reduced Gröbner basis $G$ of the ideal $\\langle f_1,\\ldots,f_m \\rangle$ are identical for general coefficient values of $\\{c_{i,\\alpha}\\}$. In other words, this means that in most cases, the combinations of terms on a reduced Gröbner basis are determined only by the combinations of terms in the input polynomial system. This can also be observed from the relatively high support accuracy in our experiments.\n\nFrom the above, there is still no concrete guarantee that our method will give a correct model, including the coefficients, but it is believed that there is some guarantee that the terms will be guessed correctly. In algebra, guessing the terms of the Gröbner basis gives a global invariant of the ideal, such as the initial ideal or the Hilbert polynomial. Therefore, we can consider using our model as an oracle or heuristic to provide global invariants of ideals (initial ideals, Hilbert polynomials) for downstream tasks. Indeed, there is an accelerated Gröbner basis computation algorithm using Hilbert polynomials [1]. In future work, we can construct efficient polynomial solving and Gröbner basis computation theory by assuming further information (e.g., entire supports) given by Transformers.\n\n**Other fields.**\nThe proposed dataset generation works for other coefficient fields, including $\\mathbb{Q}_p$. However, as $\\mathbb{N}$ is not a field (or even a ring), the set $\\mathbb{N}[x_1,\\ldots, x_n]$ is beyond the scope of Gröbner basis theory. The ring $\\mathbb{Q}_p[x_1, \\ldots, x_n]$ is associated with a non-Archimedean geometry, so it should be interesting to see how the learning goes. In our experiments, the learning was more successful with $\\mathbb{Q}$, which equips a canonical metric, than with $\\mathbb{F}_p$, which has no non-trivial metrics. An experiment on $\\mathbb{Q}_p[x_1, \\ldots, x_n]$ may serve as the midpoint between them.\n\n[1] C. Traverso, Hilbert functions and the Buchberger algorithm, Journal of Symbolic Computation, 1997.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1344RhpXEF", "reviewer": "Reviewer_pNNy", "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)$: \n\n$(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.\n\nTo 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.", "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. \n\n- 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]). \nHence 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": "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.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The article proposes a serious study, is well-written and very comprehensible for non-experts in computational algebra and Gröbner basis. \n\n- The introduction and comparison to existing work is clear.\n\n- The articles presents interesting ideas to generate training datasets, using a backward approach. Instead of first sampling the $f_i$'s (non-Gröbner set) and then an associated Gröbner basis, they first generate a set of polynomials formed by some gi's and then generate an associated system of polynomials fi's that thave property (P) (in other words, first generate the solutions, then the problem).\n\n- The authors included example of success for, but also examples of failure, which can be of use for future improvements.\n\n- The authors share in details the results and conclusion of their study, in particular their experiments. Therefore, this article may be of great interest beyond the computational algebra community, including those who have to solve polynomial systems of questions for various applications.", "weaknesses": "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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thorough review and strongly positive assessment of our work. We are grateful that you listed many strengths of our work.\n\n**Reduced Gröbner basis.** The reduced Gröbner basis is defined independently from shape position. A Gröbner basis $G$ is called reduced when i) the leading term coefficients are all one and ii) there is no redundancy (see. Definition A.13.) in that any terms of $g \\in G$ is not divisible by the leading term of other polynomials in $G$. We will include a few follow-up lines to make it more friendly to readers unfamiliar with Grönber bases.\n\n**Gröbner basis definition for non-experts.** It is indeed very important to broaden the scope of readers by introducing some intuition on the definition of a Gröbner basis. We prepare the paragraph at [l.118] to give such an intuition of Gröbner bases, but it is true that this does not give an intuition of Definition 3.2. The suggested explanation elegantly presents the point of the definition, and we will integrate it into our explanation. Once our paper gets accepted, there will be an additional content page. We will exploit it.\n\nWe will clean up our manuscript by taking into account your comments on missing table references and providing a more friendly introduction to Gröbner bases. Again, we thank you for your strong support of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jngGx6jlkB", "reviewer": "Reviewer_q3D1", "summary": "This paper provides a machine learning algorithm to compute Gröbner bases of 0-dimensional ideals in shape position. \nTo 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. \nThe associated algorithm running time is derived in Theorem 4.8. \nAfter generating tuples with the two above-mentioned steps, the authors rely on Transformers for learning to compute Gröbner bases.", "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. \nRandom search applied to higher-dimensional ideals would be more challenging and interesting. Could the authors provide more insights to address such problems?\n\n- 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": "- There is no section dedicated about the limitations of this work in the main text. Section H is not part of the main text.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- The benchmarks show that computing Gröbner bases with the proposed backward approach can be substantially more efficient than with the usual \"forward\" algorithms.", "weaknesses": "- 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\". \n\n- 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. \n\n- 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. \n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# NeurIPS 2024 Rebuttal (Reviewer q3D1)\n\nWe appreciate your thorough review and valuable feedback. Below, we answer the weaknesses and questions.\n\n## **On Weaknesses**\n\n**Theoretical guarantees on training.** Providing theoretical guarantees on global/local convergence, running time, and error bounds for the training of Transformers (or deep neural networks) is generally difficult. \nTo our knowledge, such guarantees have been (partially) given only for simple models, e.g., two-layer networks or infinitely wide networks. Hence, this should be beyond the scope of our study. The tight page limitation forced us to send the description of Transformers and its training to the appendix, but as mentioned around [l.335], they follow a standard one. The exception is when hybrid embedding is used, where we have a small MLP at the input embedding, a regression head for predicting coefficients, and MSE loss. These are described in Section 5 and Appendix D, but we will review the manuscript to give further details. \n\n**Benchmarks and applications.**\nShowing the superiority of using Transformers for large-scale problems in benchmarks and applications is indeed important. However, to achieve this, we need a few more fundamental steps, e.g., \n1. Designing dataset generation algorithms tailored for target applications.\n2. Discovering an efficient tokenization of large polynomial systems.\n\nOn 1), since the characteristics of polynomial systems vary across applications, one needs to design a special way of generating them. Our work did this for zero-dimensional radical ideals as a first step because 0-dimensionality is common in several applications (cf. Global Response). \n\nOn 2), we need an efficient representation of polynomial systems for scale-up. The scope of this study is to establish the problem of learning to compute Gröbner bases, and thus, we tested its learnability based on a standard model and training. The tokenization of polynomials also follows a standard one; for example, $\\{x^2-10, y\\}$ is tokenized as $\\texttt{[x, **, 2, +, -10, <sep>, y]}$, (cf. Section 5). Eventually, a single $n$-variate term requires $O(n)$ tokens, leading to a long input sequence for large $n$. As well known in Transformer literature, the space complexity of the attention mechanism scales as $O(L^2)$ with input length $L$. A potential approach to shorten the input is to embed a term by its coefficient and inject the exponent part as position vectors because this is literally a position in the term space. We are currently working on it in our follow-up paper. \n\nIt is worth noting that the current study already observed that Gröbner basis computation is computationally costly for $n=5$ in Table 1, where about 24% of the instances encountered timeout for two standard algorithms. Further, Table 22 shows that for all the algorithms, there are several instances for which Transformers run accurately and significantly faster. Thus, we have already partially observed the Transformer's supremacy.\n\n**Writing and format.**\nWe will carefully clean up our manuscript manually and systematically (e.g., using LLM). A grammar checker applied before submission does not seem to work well for sentences with latex codes. As for the placement of the proofs and limitations, in my limited experience, it is common for the NeurIPS papers to have them in Appendix. The paper checklist justifies this; see [l.947], \n> The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.\n\nIn our manuscript, the intuition is provided below each theorem. About the limitations, because this study tackles a new problem, we needed a thorough discussion of open questions, which led us to send it to Appendix. The checklist does not clarify whether the limitation section should be included in the main text. \n\nAccording to the submission instructions, accepted papers will get another content page, so we may be able to include the proofs and/or limitations in the main text in such a case.\n\n## **On Questions**\n\n**0-dimensional ideals.** If an ideal is in shape position, it is also 0-dimensional. Thus, the assumption of shape-positioned ideals cannot be weaker than that of 0-dimensionality. We assume that you intend to mean \"assuming 0-dim is strong; further assuming shape position is OK.\" As several reviewers ask about the assumption, we provide the Global Response to address it. Please kindly refer to it.\n\n**Killer applications.**\nOne of the potential killer applications is cryptanalysis. The security of \ncryptography is often reduced to the difficulty of solving certain mathematical problems. \nRecently, the SALSA project [1] has shown that a Transformer-based approach can solve the LWE (Learning With Errors) problem, which is the basis for the security of lattice-based cryptographies. The overview of their approach is as follows:\n\n1. From the cryptosystem to be analyzed, generate samples of LWE and their solutions as training data and perform training.\n2. Input the LWE corresponding to the ciphertext to be attacked into the model constructed in Step 1. If the output gives the secret, the cryptosystem is vulnerable.\n\nThe computational difficulty of the Gröbner basis problem for 0-dimensional ideals is the basis for the security of AES [2], which is currently the mainstream symmetric key encryption, and multivariate polynomial encryption [3], which provided candidates in the NIST Post-Quantum Cryptography Standardization process. Our future target is to make our proposed efficient data set generation and machine learning the basis for some security analysis in cryptography.\n\n[1] E. Wenger, et al., SALSA: Attacking lattice cryptography with transformers, 2022.\n\n[2] J. Buchmann, et al., Block ciphers sensitive to Gröbner basis attacks. 2005\n\n[3] A. Kipnis, et al., Unbalanced oil and vinegar signature schemes, 1999", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Global Response

We sincerely appreciate the reviewers' time and efforts in reviewing our manuscript. We have received many insightful comments and questions, which have been carefully considered in this rebuttal and the next manuscript update.

While we will answer most of the comments and questions from each reviewer individually, here we would like to elaborate on our assumption of 0-dimensional ideals, as this topic appears to be of interest to several reviewers (particularly Reviewers BQDD and q3D1).

### **On 0-dimensional ideal settings**
This study focuses on 0-dimensional ideals, and several reviewers asked about its motivation and generalization to positive-dimensional ideals. A short answer is that the choice of 0-dimensional ideals is reasonable from both computational algebra and application standpoints, and generalization to the positive-dimensional case is challenging but interesting future work. 

### **Motivation**
Our study is the first to approach Gröbner basis computation via end-to-end learning. We found that dataset generation poses unexplored algebraic tasks, i.e., sampling of Gröbner bases and their back-transformation to non-Gröbner sets. It is very difficult to resolve this in the most general case in a single work, so we naturally had to restrict ourselves to a particular case. We chose 0-dimensional ideals for two reasons:

**i)** From a computer algebraic perspective, 0-dimensional ideals are the most popular class of ideals to study. This is partly because of the ease of analysis. As Definition A.5 shows, 0-dimensional ideals relate to finite-dimensional vector spaces, and thus, analysis and algorithm design can be essentially addressed by matrices and linear algebra. As a consequence, we have more useful statements and algorithms for this case. As such, we focused on the 0-dimensional case as a reasonable starting point, where many facts and tools are accessible. It is also worth noting that on a finite field, any ideal becomes 0-dimensional by including the field equations (i.e., polynomials restricting the solutions to the finite field; e.g., $x(x-1)$ for $\mathbb{F}_2[x]$) to the generators. Such extensions of generators are perfectly acceptable when we are interested in the solutions, not the Gröbner bases themselves.

**ii)** From an application perspective, 0-dimensional ideals are again popular objects to study. Namely, many applications share a motivation of finding solutions for polynomial systems with an implicit assumption of finitely many solutions. If a system (or its associated ideal) is 0-dimensional, it has finitely many solutions (and the reverse is also true if the coefficient field is algebraically closed). For example, the multivariate cryptosystem, a promising candidate for signature-based post-quantum cryptosystem standardization by NIST, is based on 0-dimensional ideals [1]. In control theory, finding equilibria of rational dynamical systems is reduced to polynomial system solving with an assumption that there are finite equilibria. The estimation of the domain of attraction around an equilibrium is also reduced to polynomial system solving [2]. In machine learning, the computation of generators of 0-dimensional ideals has been studied as a feature extraction method [3, 4, 5] (see Appendix G for more), including an ICML'13 best paper.

### **Generalization**
Generalization to positive-dimensional ideals is non-trivial, and we leave it to future work. One of our contributions to the community is posing this new open problem with motivation from machine learning. We currently have no particular idea to address this. Perhaps we might be able to design some constructive algorithms for binomials, which appear in applications to combinatorics and algebraic statistics.


[1] T. Yasuda, X. Dahan, Y.-J. Huang, T. Takagi, and K. Sakurai. MQ challenge: hardness evaluation of solving multivariate quadratic problems. Cryptology ePrint Archive, 2015.

[2] D. Nešić, I.M.Y. Mareels, T. Glad, M. Jirstrand, The Gröbner Basis Method in Control Design: an Overview, IFAC, 2002,

[3] R. Livni, D. Lehavi, S. Schein, H. Nachliely, S. Shalev-Shwartz, and A. Globerson. Vanishing component analysis. ICML, 2013. (Best Paper Award)

[4] H. Kera and Y. Hasegawa. Gradient boosts the approximate vanishing ideal. AAAI, 2020

[5] E. S. Wirth and S. Pokutta. Conditional gradients for the approximately vanishing ideal. AISTATS, 2022

Meta-review: 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.
Decision: Accept (poster)