# Learning to Compute Gröbner Bases

Hiroshi Kera<EMAIL_ADDRESS>
Chiba University
Chiba, Japan Yuki Ishihara<EMAIL_ADDRESS>
Tokyo University of Science
Tokyo, Japan Yuta Kambe<EMAIL_ADDRESS>
Mitsubishi Electric Information Technology R&D Center
Kanagawa, Japan
Tristan Vaccon<EMAIL_ADDRESS>
Université de Limoges
Limoges, France
Kazuhiro Yokoyama<EMAIL_ADDRESS>
Rikkyo University (St. Paul’s University)
Tokyo, Japan

###### 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 notoriously expensive computational cost—doubly exponential time
complexity in the number of variables in the worst case. In this paper, we
achieve for the first time Gröbner basis computation through the training of a
transformer. The training requires many pairs of a polynomial system and the
associated Gröbner basis, thus motivating us to address two novel algebraic
problems: random generation of Gröbner bases and the transformation of them
into non-Gröbner polynomial systems, termed as backward Gröbner problem. We
resolve these problems with zero-dimensional radical ideals, the ideals
appearing in various applications. The experiments show that in the five-
variate case, the proposed dataset generation method is five orders of
magnitude faster than a naive approach, overcoming a crucial challenge in
learning to compute Gröbner bases.

##  1 Introduction

Understanding the properties of polynomial systems and solving them have been
a fundamental problem in computational algebra and algebraic geometry with
vast applications in cryptography (Bard, 2009; Yasuda et al., 2015), control
theory (Park & Regensburger, 2007), statistics (Diaconis & Sturmfels, 1998;
Hibi, 2014), computer vision (Stewenius, 2005), systems biology (Laubenbacher
& Sturmfels, 2009), and so forth. Special sets of polynomials, called Gröbner
bases (Buchberger, 1965), play a key role to this end. In linear algebra, the
Gaussian elimination simplifies or solves a system of linear equations by
transforming its coefficient matrix into the reduced row echelon form.
Similarly, a Gröbner basis can be regarded as a reduced form of a given
polynomial system, and its computation is a generalization of the Gaussian
elimination to general polynomial systems.

However, computing a Gröbner basis is known for its notoriously bad
computational cost in theory and practice. It is an NP-hard problem, and its
worst-case time complexity is doubly exponential in the number of variables
(Mayr & Meyer, 1982; Dubé, 1990). Nevertheless, because of its importance,
various computation algorithms have been proposed in computational algebra to
obtain Gröbner bases in better runtime. Examples include Faugère’s F4/F5
algorithms (Faugère, 1999, 2002) and M4GB (Makarim & Stevens, 2017).

In this study, we address this challenging task of computing Gröbner bases
using machine learning. Recent studies have revealed the potential of
transformer models as a powerful solver of algebraic computations. Namely,
instead of designing explicit computational procedures, we train a machine
learning model using a large amount of (non-Gröbner set, Gröbner basis) pairs.
A similar framework has also been used for other mathematical tasks. For
example, Lample & Charton (2019) showed that transformers can learn symbolic
integration simply by observing many $(\derivative*{f}{x},f)$ pairs in
training. The training samples are generated by first randomly generating $f$
and computing its derivative $\derivative*{f}{x}$ and/or by the reverse
process. Other examples include solving ordinary differential equations
(Lample & Charton, 2019), symbolic regression (Biggio et al., 2021), and basic
linear algebra (Charton, 2022a). For all the tasks, transformers exhibited a
high performance.

A crucial challenge in the learning of Gröbner basis computation is that it is
mathematically unknown how to efficiently generate many (non-Gröbner set,
Gröbner basis) pairs. To resolve this, we need an efficient backward approach
(i.e., solution-to-problem computation) because, as discussed above, the
forward approach (i.e., problem-to-solution computation) is prohibitively
expensive. Particularly, we need to address (i) a random generation of Gröbner
bases and (ii) a backward transformation from a Gröbner basis to an associated
non-Gröbner set. To our knowledge, neither of them has been addressed in
computational algebra because of the lack of motivations and applications; all
the efforts have been dedicated to the forward computation from a non-Gröbner
set to Gröbner basis. The central contributions of this study are the
discovery of these new mathematical problems, efficient computational
algorithms for them, and the first machine learning approach for Gröbner basis
computation, summarized as follows.

  * •

We provide the first approach to the Gröbner computation using a machine
learning model and experimentally show that transformers can actually learn
it. Unlike most prior studies, our results indicate that training a
transformer may be a compromise to NP-hard problems to which no efficient
(even approximate or probabilistic) algorithms have been designed.

  * •

We uncovered two unexplored algebraic problems—random generation of Gröbner
bases and backward Gröbner problem and propose efficient methods to address
them, particularly for the zero-dimensional case. These problems are not only
essential to generating a dataset for training a transformer but also
algebraically interesting, thus encouraging the interaction between
computational algebra and machine learning.

  * •

Our experiments demonstrate that our method is highly efficient and faster
than a baseline method by two to five orders of magnitude in dataset
generation. Transformers trained on the generated datasets successfully
compute Gröbner bases with moderate accuracy.

##  2 Related Work

#### Gröbner basis computation.

Gröbner basis is one of the fundamental concepts in algebraic geometry and
commutative ring theory (Cox, 2005; Gruel & Pfister, 2008). By its
computational aspect, Gröbner basis is a very useful tool for analyzing the
mathematical structures of solutions of algebraic constraints. Notably, the
form of Gröbner bases is very suited for finding solutions and allows
parametric coefficients. For such sought-after applications, it is vital to
make Gröbner basis computation very efficient and practical. Following the
definition of Gröbner bases in (Buchberger, 1965), the original algorithm to
compute them can be presented as  (i) create potential new leading terms by
constructing S-polynomials,  (ii) reduce them either to zero or to new
polynomials for the Gröbner basis, and  (iii) repeat until no new
S-polynomials can be constructed. Plenty of works has been developed to
surpass this algorithm. There are four main strategies:  (a) avoiding
unnecessary S-polynomials based on the F5 algorithm and the more general
signature-based algorithms (Faugère, 2002; Bardet et al., 2015). Machine
learning appeared for this task in (Peifer et al., 2020).  (b) More efficient
reduction using efficient linear algebraic computations using (Faugère, 1999)
and the very recent GPU-using (Berthomieu et al., 2023).  (c) Performing
modular computations, following (Arnold, 2003; Noro & Yokoyama, 2018), to
prevent coefficient growth during the computation.  (d) Using the structure of
the ideal, e.g., (Faugère et al., 1993; Berthomieu et al., 2022) for change of
term ordering for zero-dimensional ideals or (Traverso, 1997) when the Hilbert
function is known.  In this study, we presents the fifth strategy: (e) Gröbner
computation fully via learning without specifying any mathematical procedures.

#### Math transformers.

Recent studies have revealed that transformers can be used for mathematical
reasoning and symbolic computation. The training of such math transformers
only requires samples (i.e., problem–solution pairs), and no explicit
procedures need to be specified. Lample & Charton (2019) presented the first
study that uses transformers for mathematical problems. They showed that
transformers can learn symbolic integration and differential equation solving
with training with sufficiently many and diverse samples. Since then,
transformers have been applied to checking local stability and controllability
of differential equations (Charton et al., 2021), polynomial simplification
(Agarwal et al., 2021), linear algebra (Charton, 2022a, b), attack to the LWE
cryptography (Wenger et al., 2022; Li et al., 2023), and symbolic regression
(Biggio et al., 2021; Kamienny et al., 2022; d’Ascoli et al., 2022; Kamienny
et al., 2023). (Saxton et al., 2019) provides comprehensive experiments over
various mathematical tasks. Several recent studies point out that transformers
may only perform well for in-distribution samples and not generalize well to
out-distributions (Dziri et al., 2023). There are several transformer models
that address this challenge (Kim et al., 2021; Cognolato & Testolin, 2022).
While this is a fundamental challenge of the math transformers, the focus of
our study lies in revealing whether transformers can learn an extremely
difficult mathematical problem, Gröbner basis computation, and establish a
dataset generation method to experimentally examine it.

##  3 Notations and Definitions

Throughout the paper, we consider a polynomial ring $k[x_{1},\ldots,x_{n}]$
with a field $k$ and variables $x_{1},\ldots,x_{n}$.111One may regard
$k[x_{1},\ldots,x_{n}]$ as the set of all $n$-variate polynomials with
coefficients in $k$ (e.g., $k=\mathbb{R}$). We here introduce basic
definitions in algebra. Refer to App. A as necessary.

######  Definition 3.1 (Affine variety).

Let $F=\quantity{f_{1},\ldots,f_{s}}$ be a subset of $k[x_{1},\ldots,x_{n}]$.
Then, we set

$\displaystyle V(F)=V(f_{1},\ldots,f_{s})=\quantity{p\in k^{n}\mid
f_{1}(p)=\cdots=f_{s}(p)=0}.$ (3.1)

We call this the affine variety defined by $f_{1},\ldots,f_{s}$ (or by $F$).

Namely, the affine variety $V(f_{1},\ldots,f_{s})$ is the zero set of the
polynomial system
$f_{1}(x_{1},\ldots,x_{n})=\cdots=f_{s}(x_{1},\ldots,x_{n})=0$. Next, we
introduce a special set of polynomials.

######  Definition 3.2 (Ideal).

A subset $I\subset k[x_{1},\ldots,x_{n}]$ is an ideal if it satisfies the
following: (i) $0\in I$, (ii) if $f,g\in I$, then $f+g\in I$, and (iii) if
$f\in I$ and $h\in k[x_{1},\ldots,x_{n}]$, then $hf\in I$.

An ideal $I$ that contains $f_{1},\ldots,f_{s}$ relates to the polynomial
system $f_{1}(x_{1},\ldots,x_{n})=\cdots=f_{s}(x_{1},\ldots,x_{n})=0$. Indeed,
for any $p\in k^{n}$, $f_{i}(p)=f_{j}(p)=0$ implies $(f_{i}+f_{j})(p)=0$, and
for any $h\in k[x_{1},\ldots,x_{n}]$, $(hf_{i})(p)=0$ holds. Thus, roughly
speaking, $I$ contains all the polynomials that can be freely appended to the
system $f_{1}(p)=\cdots=f_{s}(p)=0$ without changing its affine variety (i.e.,
solutions). This idea is formalized as follows.

######  Definition 3.3 (Generators).

For $F=\quantity{f_{1},\ldots,f_{s}}\subset k[x_{1},\ldots,x_{n}]$, the
following set

$\displaystyle\langle F\rangle=\langle
f_{1},\ldots,f_{s}\rangle=\quantity{\sum_{i=1}^{s}h_{i}f_{i}\mid
h_{1},\ldots,h_{s}\in k[x_{1},\ldots,x_{n}]}.$ (3.2)

is an ideal and said to be generated by $f_{1},\ldots,f_{s}$ (or by $F$), and
$f_{1},\ldots,f_{s}$ are called generators.

We next define several notions that are necessary to define the Gröbner basis.

######  Definition 3.4 (Term order (informal)).

A term order $\prec$ is an order of terms222Terms refer to power products of
variables, i.e, $x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$ with
$\alpha_{1},\ldots,\alpha_{n}\in{\mathbb{Z}}_{\geq 0}$.  such as $1\prec
x_{n}\prec x_{n-1}\prec\cdots$. Constant term $1=x_{1}^{0}\cdots x_{n}^{0}$ is
the least prioritized in any term order.

Strictly speaking, a term order satisfies a few more conditions, but we omit
the detail as it is unnecessary to follow this study. We provide a well-known
term order to give an intuition.

######  Example 3.5.

The lexicographic order $\prec_{\mathrm{lex}}$ prioritizes terms with larger
exponents for the variables of small indices, e.g.,

$\displaystyle 1\prec_{\mathrm{lex}}x_{n}\quad\text{and}\quad
x_{2}\succ_{\mathrm{lex}}x_{3}^{2}\quad\text{and}\quad
x_{1}x_{2}x_{3}^{2}\prec_{\mathrm{lex}}x_{1}x_{2}^{2}x_{3}.$ (3.3)

Two terms are first compared in terms of the exponent in $x_{1}$ (larger one
is prioritized), and if a tie-break is needed, the next variable $x_{2}$ is
considered, and so forth.

The next notion plays an important role in the Gröbner basis theory.

######  Definition 3.6 (Leading term).

Let $F=\quantity{f_{1},\ldots,f_{s}}\subset k[x_{1},\ldots,x_{n}]$ and let
$\prec$ be a term order. The leading term $\mathrm{LT}({f_{i}})$ of $f_{i}$ is
the largest term in $f_{i}$ in ordering $\prec$. The leading term set of $F$
is
$\mathrm{LT}({F})=\quantity{\mathrm{LT}({f_{1}}),\ldots,\mathrm{LT}({f_{s}})}$.

Given a polynomial set $F$, the computation of a Gröbner basis is essentially
a simplification of $F$ without changing the affine variety $V(F)$. For
example, when $F=\\{h_{1}f,h_{2}f\\}$ with $h_{1}+h_{2}=1$, we may simplify it
to $\tilde{F}=\\{f\\}$ through polynomial divisions while maintaining
$V(F)=V(\tilde{F})$. The leading term defines the simplicity of polynomials;
given two polynomials $f_{1},f_{2}\in I$, $f_{1}$ is considered simpler if
$\mathrm{LT}({f_{1}})\prec\mathrm{LT}({f_{2}})$. Indeed,
$\mathrm{LT}({f})\preceq\mathrm{LT}({h_{1}f}),\mathrm{LT}({h_{2}f})$ in the
above example. Now, we introduce Gröbner bases.

######  Definition 3.7 (Gröbner basis).

Fix a term order $\prec$. A finite subset $G$ of an ideal $I$ is said to be a
$\prec$-Gröbner basis of $I$ if
$\langle{\mathrm{LT}({G})}\rangle=\langle{\mathrm{LT}({I})}\rangle$.

Note that
$\langle{\mathrm{LT}({G})}\rangle\subset\langle{\mathrm{LT}({I})}\rangle$ is
trivial from $G\subset I$. The nontriviality of the Gröbner basis lies in
$\langle{\mathrm{LT}({G})}\rangle\supset\langle{\mathrm{LT}({I})}\rangle$;
that is, a finite number of leading terms can generate the leading term of any
polynomial in the infinite set $I$. The Hilbert basis theorem (Cox et al.,
2015) guarantees that every ideal $I\neq\quantity{0}$ has a Gröbner basis. We
are particularly interested in the reduced Gröbner basis $G$ of
$I=\langle{F}\rangle$, which is unique once the term order is fixed.333See
App. A for the definition. Strictly speaking, a Gröbner base (a non-Gröbner
set) here refers to the reduced Gröbner base (the set that is not the reduced-
Gröbner basis).

#### Other notations.

The subset $k[x_{1},\ldots,x_{n}]_{\leq d}\subset k[x_{1},\ldots,x_{n}]$
denotes the set of all polynomials of total degree at most $d$. For a
polynomial matrix $A\in k[x_{1},\ldots,x_{n}]^{s\times s}$, its determinant is
given by $\det(A)\in k[x_{1},\ldots,x_{n}]$. The set ${\mathbb{F}}_{p}$ with a
prime number $p$ denotes the finite field of order $p$. The set
$\mathrm{ST}(n,k[x_{1},\ldots,x_{n}])$ denotes the set of upper-triangular
matrices with all-one diagonal entries (i.e., unimodular upper-triangular
matrices) with entries in $k[x_{1},\ldots,x_{n}]$. The total degree of $f\in
k[x_{1},\ldots,x_{n}]$ is denoted by $\deg(f)$.

We conclude this section with an intuitive (but not necessarily accurate)
explanation of Gröbner bases for those unfamiliar with this fundamental
concept in algebra.

#### Intuitive explanation of Gröbner bases and polynomial system solving.

Let $G=\\{g_{1},\ldots,g_{t}\\}$ be a Gröbner basis of an ideal
$\langle{F}\rangle=\langle{f_{1},\ldots,f_{s}}\rangle$. The polynomial system
$g_{1}(x_{1},\ldots,x_{n})=\cdots=g_{t}(x_{1},\ldots,x_{n})=0$ is a simplified
form of $f_{1}(x_{1},\ldots,x_{n})=\cdots=f_{s}(x_{1},\ldots,x_{n})=0$ with
the same solution set. With a term order $\prec_{\mathrm{lex}}$, $G$ has a
form $g_{1}\in k[x_{n_{1}},\ldots,x_{n}],g_{2}\in
k[x_{n_{2}},\ldots,x_{n}],\ldots,g_{t}\in k[x_{n_{t}},\ldots,x_{n}]$ with
$n_{1}\leq n_{2}\leq\ldots\leq n_{t}$, which may be regarded as the “reduced
row echelon form” of a polynomial system. In our particular case (i.e., zero-
dimensional ideals in shape position; cf. Sec. 4.1), we have
$(n_{1},n_{2},\ldots,n_{t})=(1,2,\ldots,n)$. Thus, one can obtain the
solutions of the polynomial system using a backward substitution, i.e., by
first solving a univariate polynomial $g_{t}$, next solving bivariate
polynomial $g_{t-1}$, which becomes univariate after substituting the
solutions of $g_{t}$, and so forth.

##  4 Random Gröbner Bases and Backward Gröbner Problem

Our goal is to realize Gröbner basis computation through a machine learning
model. To this end, we need a large training set
$\\{(F_{i},G_{i})\\}_{i=1}^{m}$ with finite polynomial set $F_{i}\subset
k[x_{1},\ldots,x_{n}]$ and Gröbner basis $G_{i}$ of $\langle{F_{i}}\rangle$.
As the computation from $F_{i}$ to $G_{i}$ is computationally expensive in
general, we instead resort to backward generation (i.e., solution-to-problem
process); that is, we generate a Gröbner basis $G_{i}$ randomly and transform
it to non-Gröbner set $F_{i}$.

What makes the learning of Gröbner basis computation hard is that, to our
knowledge, neither (i) a random generation of Gröbner basis nor (ii) the
backward transform from Gröbner basis to non-Gröbner set has been considered
in computational algebra. Its primary interest has been instead posed on
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, we address
the following problems for dataset generation.

######  Problem 4.1 (Random generation of Gröbner bases).

Find a collection $\mathcal{G}=\\{G_{i}\\}_{i=1}^{m}$ with the reduced Gröbner
basis $G_{i}\subset k[x_{1},\ldots,x_{n}]$ of $\langle{G_{i}}\rangle$,
$i=1,\ldots,m$. The collection should contain diverse bases, and we need an
efficient algorithm for constructing them.

######  Problem 4.2 (Backward Gröbner problem).

Given a Gröbner basis $G\subset k[x_{1},\ldots,x_{n}]$, find a collection
${\mathcal{F}}=\\{F_{i}\\}_{i=1}^{\mu}$ of polynomial sets that are not
Gröbner bases but $\langle{F_{i}}\rangle=\langle{G}\rangle$ for
$i=1,\ldots,\mu$. The collection should contain diverse sets, and we need an
efficient algorithm for constructing them.

Note that both Probs. 4.1 and 4.2 require the collections
${\mathcal{G}},{\mathcal{F}}$ should contain diverse polynomial sets. Thus,
the algorithms 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 (Lample & Charton, 2019; Charton, 2022a). While studying the
distribution of non-Gröbner sets and Gröbner bases might be another
challenging topic, it goes beyond the scope of the present study.

In this paper, we address the aforementioned problems with zero-dimensional
ideals.

######  Definition 4.3 (Zero-dimensional ideal).

Let $F$ be a set of polynomials in $k[x_{1},\ldots,x_{n}]$. An ideal $\langle
F\rangle$ is called a zero-dimensional ideal if all but a finite number of
terms belong to $\mathrm{LT}({\langle{F}\rangle})$.

If $k$ is an algebraically closed field (e.g., $k={\mathbb{C}}$), zero-
dimensional ideals relate to polynomial systems with a finite number of
solutions (i.e., $V(F)$ is a finite set.). Zero-dimensional ideals appear in
various application of Gröbner bases. For example, a multivariate public-key
encrypted communication (a candidate of the Post-Quantum Cryptography) with a
public polynomial system $F$ over a finite field ${\mathbb{F}}_{p}$ will be
broken if one finds an element of
$V(F\cup\\{x_{1}^{p}-x_{1},\ldots,x_{n}^{p}-x_{n}\\})$ and the ideal $\langle
F\cup\\{x_{1}^{p}-x_{1},\ldots,x_{n}^{p}-x_{n}\\}\rangle$ is a zero-
dimensional ideal (Ullah, 2012, Sec. 2.2).

A more general approach to Probs. 4.1 and 4.2 with positive-dimensional ideals
is an open problem for algebraists. The proofs of the results in the following
sections can be found in App. C.

###  4.1 Random generation of Gröbner bases

To address Prob. 4.1, we propose to use the properties of ideals in shape
position, for which Gröbner bases have a simple structure. Another potential
approach is discussed in App. B.

######  Definition 4.4 (Shape position).

Ideal $I\subset k[x_{1},\ldots,x_{n}]$ is called in shape position if some
univariate polynomials $h,g_{1},\ldots,g_{n-1}\in k[x_{n}]$ form the reduced
$\prec_{\mathrm{lex}}$-Gröbner basis of $I$ as follows.

$\displaystyle
G=\\{h(x_{n}),x_{1}-g_{1}(x_{n}),\ldots,x_{n-1}-g_{n-1}(x_{n})\\}.$ (4.1)

As can be seen, the $\prec_{\mathrm{lex}}$-Gröbner basis consists of a
univariate polynomial in $x_{n}$ and the difference of univariate polynomials
in $x_{n}$ and a leading term $x_{i}$ ($i<n$). While not all ideals are in
shape position, zero-dimensional radical ideals are almost always in shape
position.

######  Proposition 4.5 (Gianni & Mora (1989), Prop. 1.6; Noro & Yokoyama
(1999), Lem. 4.4).

Let $I$ be a zero-dimensional radical ideal.444Refer App. A for the
definition. If $k$ is of characteristic 0 or a finite field of large enough
order, then a random linear coordinate change puts I in shape position.

Thus, we can efficiently generate a random zero-dimensional ideal by sampling
$n$ polynomials in $k[x_{n}]$, i.e., $h,g_{1},\ldots,g_{n-1}$ with $h\neq 0$.
In the sampling, we make sure that the degree of $h$ is always greater than
that of $g_{1},\ldots,g_{n-1}$, which is necessary and sufficient for $G$ to
be a reduced Gröbner basis. This resolves Prob. 4.1 even with large $m$.

#### Gröbner bases for general term orders.

This approach assumes term order $\prec_{\mathrm{lex}}$. In most practical
scenarios, $\prec_{\mathrm{lex}}$-Gröbner bases are already sufficient as they
provide a simplified form of polynomial systems as presented at the end of
Sec. 3. In computational algebra, it is more common to use the graded reverse
lexicographic order because it typically leads to faster computation and
smaller size of Gröbner bases. The obtained Gröbner basis is then transformed
to the $\prec_{\mathrm{lex}}$-Gröbner basis using an efficient change-of-
ordering algorithm such as the FGLM algorithm (Faugère et al., 1993). In our
case, if necessary, one can similarly use it to obtain Gröbner bases in
non-$\prec_{\mathrm{lex}}$ order from $\prec_{\mathrm{lex}}$ Gröbner bases.
The cost of FGLM algorithm (Faugère et al., 1993) is
${\mathcal{O}}(n\cdot\deg(h)^{3})$.555Strictly speaking, the time complexity
is here based on the number of arithmetic operations over $k$.

###  4.2 Backward Gröbner problem

To address Prob. 4.2, we consider the following problem.

######  Problem 4.6.

Let $I\subset k[x_{1},\ldots,x_{n}]$ be a zero-dimensional ideal, and let
$G=(g_{1},\ldots,g_{t})^{\top}\in k[x_{1},\ldots,x_{n}]^{t}$ be a
$\prec$-Gröbner basis of $I$ with respect to term order $\prec$.666We
surcharge notations to mean that the set $\left\\{g_{1},\dots,g_{t}\right\\}$
defined by the vector $G$ is a $\prec$-Gröbner basis. Find a polynomial matrix
$A\in k[x_{1},\ldots,x_{n}]^{s\times t}$ that gives a non-Gröbner set
$F=(f_{1},\ldots,f_{s})^{\top}=AG$ such that
$\langle{F}\rangle=\langle{G}\rangle$.

Namely, we generate a set of polynomials $F=(f_{1},\ldots,f_{s})^{\top}$ from
$G=(g_{1},\ldots,g_{t})^{\top}$ by $f_{i}=\sum_{j=1}^{t}a_{ij}g_{j}$ for
$i=1,\ldots,s$, where $a_{ij}\in k[x_{1},\ldots,x_{n}]$ denotes the $(i,j)$-th
entry of $A$. However, $\langle{F}\rangle$ and $\langle{G}\rangle$ are
generally not identical. The following provides how we should design $A$ to
achieve $\langle{F}\rangle=\langle{G}\rangle$ for the zero-dimensional case
(without radicality or shape position assumption).

######  Theorem 4.7.

Let $G=(g_{1},\ldots,g_{t})^{\top}$ be a Gröbner basis of a zero-dimensional
ideal in $k[x_{1},\ldots,x_{n}]$. Let $F=(f_{1},\ldots,f_{s})^{\top}=AG$ with
$A\in k[x_{1},\ldots,x_{n}]^{s\times t}$.

  1. 1.

If $\langle{F}\rangle=\langle{G}\rangle$, it implies $s\geq n$.

  2. 2.

If $A$ has a left-inverse in $k[x_{1},\ldots,x_{n}]^{t\times s}$,
$\langle{F}\rangle=\langle{G}\rangle$ holds.

  3. 3.

The equality $\langle{F}\rangle=\langle{G}\rangle$ holds if and only if there
exists a matrix $B\in k[x_{1},\ldots,x_{n}]^{t\times s}$ such that each row of
$BA-E_{t}$ is a syzygy777Refer to App. A for the definition. of $G$, where
$E_{t}$ is the identity matrix of size $t$.

Theorem 4.7 provides several hints on designing $A$ to achieve
$\langle{F}\rangle=\langle{G}\rangle$. The first statement argues that
polynomial matrix $A$ should have at least $n$ rows. For an ideal in shape
position, we have a $\prec_{\mathrm{lex}}$-Gröbner basis $G$ of size $n$, and
thus, $A$ is a square or tall matrix. The second statement shows a sufficient
condition. The third statement provides a necessary and sufficient condition.
Using the second statement, we design a simple random transform of a Gröbner
basis to a non-Gröbner set without changing the ideal.

We now assume $\prec=\prec_{\mathrm{lex}}$ and zero-dimensional ideals in
shape position. Then, $G$ has exactly $n$ generators. When $s=n$, we have the
following.

######  Proposition 4.8.

For any $A\in k[x_{1},\ldots,x_{n}]^{n\times n}$ with $\det(A)\in
k\setminus\\{0\\}$, we have $\langle{F}\rangle=\langle{G}\rangle$.

As non-zero constant scaling does not change the ideal, we focus on $A$ with
$\det(A)=\pm 1$ without loss of generality. Such $A$ can be constructed using
a Bruhat decomposition in the form of

$\displaystyle A=U_{1}PU_{2},$ (4.2)

where $U_{1},U_{2}\in\mathrm{ST}(n,k[x_{1},\ldots,x_{n}])$ are upper-
triangular matrices with all-one diagonal entries (i.e., unimodular upper-
triangular matrices) and $P\in\\{0,1\\}^{n\times n}$ denotes a permutation
matrix. Noting that $A^{-1}$ satisfies $A^{-1}A=E_{n}$, we have
$\langle{AG}\rangle=\langle{G}\rangle$ from Thm. 4.7. Therefore, random
sampling $(U_{1},U_{2},P)$ of unimodular upper-triangular matrices
$U_{1},U_{2}$ and a permutation matrix $P$ resolves the backward Gröbner
problem for $s=n$.

We extend this idea to the case of $s>n$ using a rectangular unimodular upper-
triangular matrix:

$\displaystyle U_{2}=\matrixquantity(U_{2}^{\prime}\\\ O_{s-n,n})\in
k[x_{1},\ldots,x_{n}]^{s\times n},$ (4.3)

where $U_{2}^{\prime}\in\mathrm{ST}(n,k[x_{1},\ldots,x_{n}])$ and
$O_{s-n,n}\in k[x_{1},\ldots,x_{n}]^{(s-n)\times n}$ is the zero matrix. The
permutation matrix is now $P\in\\{0,1\\}^{s\times s}$.

Note that $U_{2}G$ already gives a non-Gröbner set such that
$\langle{U_{2}G}\rangle=\langle{G}\rangle$; however, the polynomials in the
last $s-n$ entries of $U_{2}G$ are all zero by its construction. Thus, we need
a permutation matrix $P$ to shuffle the rows and also $U_{1}$ to exclude the
zero polynomial from the final polynomial set.

To summarize, our strategy is to compute $F=U_{1}PU_{2}G$, which only requires
a sampling of ${\mathcal{O}}(s^{2})$ polynomials in $k[x_{1},\ldots,x_{n}]$,
and ${\mathcal{O}}(n^{2}+s^{2})$-times multiplications of polynomials. Note
that even in the large polynomial systems given in the MQ challenge, a post-
quantum cryptography challenge, we have $n<100$ and $s<200$ (Yasuda et al.,
2015).

Assumption: polynomial ring $k[x_{1},\ldots,x_{n}]$

Input: dataset size $m$, maximum degrees $d,d^{\prime}$, maximum size of non-
Gröbner set $s_{\max}\geq n$, and term order $\prec$.

Output: collection ${\mathcal{D}}=\\{(F_{i},G_{i})\\}_{i=1}^{m}$ of non-
Gröbner set $F_{i}\in k[x_{1},\ldots,x_{n}]^{m}$ and the reduced
$\prec$-Gröbner basis $G_{i}\subset k[x_{1},\ldots,x_{n}]$ of zero-dimensional
ideal $\langle{F}\rangle=\langle{G}\rangle$.

1 ${\mathcal{D}}\leftarrow\\{\ \\}$

2 for  _$i=1,\ldots,m$_ do

3 $G_{i}\leftarrow\\{h\\}$ with $h$, non-constant, monic/primitive, sampled
from $k[x_{n}]_{\leq d}$. $\triangleright$ Prob. 4.1

4 for  _$j=1,\ldots,n-1$_ do

5 $G_{i}\leftarrow G_{i}\cup\\{g_{j}\\}$ with $g_{j}$ sampled from
$k[x_{n}]_{\leq\deg(h)-1}$.

6

7 end for

8 $s\sim{\mathbb{U}}[n,s_{\max}]$ $\triangleright$ Prob. 4.2

9 Sample a unimodular upper-triangular matrix
$U_{1}\in\mathrm{ST}(s,k[x_{1},\ldots,x_{n}]_{\leq d^{\prime}})$.

10 Sample a unimodular upper-triangular matrix
$U_{2}^{\prime}\in\mathrm{ST}(n,k[x_{1},\ldots,x_{n}]_{\leq d^{\prime}})$.

11 Sample a permutation matrix $P\in\\{0,1\\}^{s\times s}$

12 $F_{i}\leftarrow U_{1}PU_{2}G_{i}$, where $U_{2}=[{U_{2}^{\prime}}^{\top}\
\ O_{n,s-n}]^{\top}\in k[x_{1},\ldots,x_{n}]^{s\times n}$.

13 if  _$\prec\ \neq\prec_{\mathrm{lex}}$_ then

14 $G_{i}\leftarrow\mathrm{FGLM}(G_{i},\prec_{\mathrm{lex}},\prec)$

15 end if

16 ${\mathcal{D}}\leftarrow{\mathcal{D}}\cup\\{(F_{i},G_{i})\\}$
$\triangleright$ Reorder terms in $F_{i}$ if $\prec\neq\prec_{\mathrm{lex}}$.

17 end for

Algorithm 1 Dataset generation for learning to compute zero-dimensional
Gröbner bases.

###  4.3 Dataset generation algorithm

Summarizing the discussion in the previous sections, we have Alg. 1 and the
following.

######  Theorem 4.9.

Consider polynomial ring $k[x_{1},\ldots,x_{n}]$. Given dataset size $m$,
maximum degrees $d,d^{\prime}$, maximum size of non-Gröbner set $s_{\max}\geq
n$, and term order $\prec$, Alg. 1 returns a collection
${\mathcal{D}}=\\{(F_{i},G_{i})\\}_{i=1}^{m}$ with the following properties:
For all $i=1,\ldots,m$,

  1. 1.

Both $F_{i},G_{i}\subset k[x_{1},\ldots,x_{n}]$ are finite sets and
$\absolutevalue{F_{i}}\leq s_{\max}$.

  2. 2.

The set $G_{i}$ is the reduced $\prec$-Gröbner basis of
$\langle{F_{i}}\rangle$. The set $F_{i}$ is not, unless
$G_{i},U_{1},U_{2}^{\prime},P$ are all sampled in a non-trivial Zariski closed
subset.888This can happen with probability zero if $k$ is infinite and very
low probability over large finite field.

  3. 3.

The ideal $\langle{F_{i}}\rangle=\langle{G_{i}}\rangle$ is a zero-dimensional
ideal in shape position.

The time complexity is
${\mathcal{O}}(m(nS_{1,d}+s^{2}S_{n,d^{\prime}}+(n^{2}+s^{2})M_{n,2d^{\prime}+d}))$
when $\prec=\prec_{\mathrm{lex}}$, where $S_{n,d}$ denotes the complexity of
sampling an $n$-variate polynomial with total degree at most $d$, and
$M_{n,d}$ denotes that of multiplying two $n$-variate polynomials with total
degree at most $d$. If $\prec\neq\prec_{\mathrm{lex}}$,
${\mathcal{O}}(mnd^{3})$ is additionally needed.

The proposed dataset generation method is a backward approach, which first
generates solutions and then transforms them into problems. In this case, we
have control over the complexity of the Gröbner bases and can add some
intrinsic structure if any prior information is available. For example, in a
multi-variate encryption scheme, a secret cipher text will be broken if one
finds the solution of the corresponding polynomial systems with a single
solution in a base field Yasuda et al. (2015). Such systems are zero-
dimensional, and ideals generated by them are in shape position. Particularly,
their Gröbner bases have the following form: $G=\langle
x_{n}-a_{n},x_{1}-a_{1},\ldots,x_{n-1}-a_{n-1}\rangle$, where
$a_{1},a_{2},\ldots,a_{n}$ are constants (Ullah, 2012). Backward approaches
allow one to restrict the Gröbner bases in a dataset into such a class.

This is not the case with forward approaches. While they may include prior
information into non-Gröbner sets, it is computationally expensive to obtain
the corresponding Gröbner bases. It is also worth noting that a 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. This is
because that with a Gröbner basis $G$ computed directly from a random non-
Gröbner set $F$ tends to share some polynomials with $F$, while such behavior
is unusual in practical scenarios.

##  5 Experiments

We now present experimental results on training a transformer for Gröbner
basis computation. All the experiments were conducted on a workstation with
16-core CPUs, 512 GB RAM, and two NVIDIA RTX A6000 GPUs. We provide more
information on the profile of generated datasets, the training setup, and
additional experimental results in App. D. The code will be available soon.

###  5.1 Dataset generation

Table 1: Runtime comparison (in seconds/milliseconds) of forward generation (F.) and backward generation (B.) of dataset ${\mathcal{D}}_{n}({\mathbb{F}}_{p})$ of size 1000. The forward generation used either of the three algorithms provided in Sagemath with the libSingular backend. For $n=4,5$, we set a timeout limit to one second (added to the total runtime at every occurrence) for each Gröbner basis computation. The numbers with $*$ and $\dagger$ include the timeout for more than 10 % and 40 % of the runs, respectively. Method | ${\mathbb{F}}_{7}[x_{1},\ldots,x_{n}]$ | ${\mathbb{F}}_{31}[x_{1},\ldots,x_{n}]$
---|---|---
$n=2$ |  $n=3$ |  $n=4$ |  $n=5$ |  $n=2$ |  $n=3$ |  $n=4$ |  $n=5$
F. (std) [sec] |  0.38 |  3.46 |  185∗ |  430† |  0.36 |  2.61 |  207∗ |  437†
F. (slimgb) |  0.41 |  5.14 |  174∗ |  444† |  0.40 |  7.28 |  202∗ |  460†
F. (stdfglm) |  0.97 |  1.36 |  15.5 |  114 |  1.00 |  1.45 |  18.7 |  166
B. (ours) [msec] |  2.05 |  2.88 |  3.70 |  4.90 |  2.11 |  2.78 |  3.47 |  5.27

We first demonstrate the efficiency of the proposed dataset generation
framework. We constructed eight datasets
$\\{{\mathcal{D}}_{n}({\mathbb{F}}_{p})\\}_{n,p}$ for $n\in\\{2,3,4,5\\}$ and
$p\in\\{7,31\\}$ and measured the runtime of the forward generation and our
backward generation.

#### Generation setup of ${\mathcal{D}}_{n}({\mathbb{F}}_{p})$.

The dataset ${\mathcal{D}}_{n}({\mathbb{F}}_{p})$ consists of 1,000 pairs of
non-Gröbner set and Gröbner basis in ${\mathbb{F}}_{p}[x_{1},\ldots,x_{n}]$.
Each sample $(F,G)\in{\mathcal{D}}_{n}({\mathbb{F}}_{p})$ was prepared using
the process given in Alg. 1 with
$(d,d^{\prime},s_{\max},\prec)=(5,3,n+2,\prec_{\mathrm{lex}})$. The number of
terms of univariate polynomials and $n$-variate polynomials is uniformly
determined from $[1,5]$ and $[1,2]$, respectively.

#### Forward generation.

In the forward generation, one may first generate random polynomial sets and
then compute their Gröbner bases. However, this leads to a dataset with a
totally different complexity from that constructed by the backward generation,
leading to an unfair runtime comparison between the two generation processes.
As such, the forward generation instead computes Gröbner bases of the non-
Gröbner sets given by the backward generation, leading to the identical
dataset. We used SageMath (The Sage Developers, 2023) with the libSingular
backend.

In Tab. 1, our backward generation is significant orders of magnitude faster
than the forward generation. A sharp runtime growth is observed in the forward
generation as the number of variables increases. Note that these numbers only
show the runtime on 1,000 samples, while our training requires a million
samples. Therefore, the forward generation is almost infeasible, indicating
that the proposed method resolves a critical challenge in the learning of
Gröbner basis computation.

###  5.2 Gröbner basis computation with transformers

Table 2: Accuracy [%] of Gröbner basis computation by transformers on ${\mathcal{D}}_{n}({\mathbb{F}}_{7})$. In the support accuracy, two polynomials are considered identical if they consist of an identical set of terms (i.e., identical support). The last column shows the results of training on ${\mathcal{D}}_{2}({\mathbb{F}}_{7})$ with the change of term order to $\prec_{\mathrm{grvlex}}$. Note that the datasets for $n=3,4,5$ are here constructed using $U_{1},U_{2}^{\prime}$ (cf. Alg. 1) with density $\sigma=0.6,0.3,0.2$, respectively. See the main text for the details. Metric | $\prec_{\mathrm{lex}}$ | $\prec_{\mathrm{grvlex}}$
---|---|---
$n=2$ |  $n=3$ |  $n=4$ |  $n=5$ |  $n=2$
|  $\sigma=1$ |  $\sigma=0.6$ |  $\sigma=0.3$ |  $\sigma=0.2$ |  $\sigma=1$
accuracy |  68.2 |  65.1 |  76.4 |  80.9 |  26.4
support acc. |  77.3 |  86.6 |  87.2 |  90.5 |  45.8

We now demonstrate that transformers can learn to compute Gröbner bases. To
examine the general transformer’s ability, we focus on a standard architecture
(e.g., 6 encoder/decoder layers and 8 attention heads) and a standard training
setup (e.g., the AdamW optimizer (Loshchilov & Hutter, 2019) with
$(\beta_{1},\beta_{2})=(0.9,0.999)$ and the linear decay of learning rate from
$10^{-4}$). The batch size was set to 8, and models were trained for 10
epochs. Refer to App. D for complete information.

Each polynomial set in the datasets is converted into a sequence in the prefix
representation. Unlike natural language processing, our task does not allow
the truncation of an input sequence to effectively shorten the input sequences
because the first term of the first polynomial in $F$ certainly relates to the
last term of the last polynomial. To keep the input sequence length manageable
for vanilla transformers, we use simpler datasets than those in Sec. 5.1. If
the matrices $U_{1},U_{2}^{\prime}$ in Alg. 1 are dense, the final polynomials
in $F$ tend to have many terms, leading to long input sequences. Thus, we
construct datasets using $U_{1},U_{2}^{\prime}$ with a moderate density
$\sigma\in[0,1]$ so that the maximum sequence length becomes less than 4096.
Specifically, we used $\sigma=1.0,0.6,0.3,0.2$ for $n=2,3,4,5$, respectively.
The training set has one million samples, and the test set has one thousand
samples. Other settings are the same as in Sec. 5.1 Using a more efficient
attention mechanism such as (Kitaev et al., 2020; Ding et al., 2023; Sun et
al., 2023) to handle larger polynomial sets will be a future work.

Tab. 2 shows that transformers trained on the constructed datasets compute
correct $\prec_{\mathrm{lex}}$-Gröbner bases with moderate accuracy.
Nevertheless, even when the transformer cannot produce the correct basis, the
support999The support of a polynomial $f$ refers to the set of terms in $f$.
of each polynomial in the predicted basis tends to be correct. Since there are
efficient Gröbner basis computation algorithms if the support of each
polynomial in Gröbner basis is accessible (Traverso, 1997), our experiments
successfully show the transformer’s potential in accelerating Gröbner
computation. Lastly, the last two columns of Tab. 2 suggest that learning with
$\prec_{\mathrm{grvlex}}$ may not be as effective as that with
$\prec_{\mathrm{lex}}$. In contrast, $\prec_{\mathrm{grvlex}}$ is preferred in
computational algebra because of its empirical runtime reduction in Gröbner
basis computation. We consider that the well-structured nature of
$\prec_{\mathrm{lex}}$-Gröbner bases of ideals in shape position (c.f. Eq.
(4.1)) may be favorable to transformers. Refer to App. D for success and
failure examples. Particularly, the failure examples show that the incorrect
outputs from transformers are still very reasonable.

##  6 Discussion from an Algebraic Viewpoint and Open Questions

Without the Gröbner condition, Prob. 4.6 of characterizing the $A$ such that
$F=AG$ and $\left\langle F\right\rangle=\left\langle G\right\rangle$ has been
studied in (Busé et al., 2001; Busé, 2001) to provide an algebraic necessary
and sufficient condition for the polynomial system of $F$ to have a solution
outside the variety defined by $G$. This condition is expressed explicitly by
multivariate resultants. However, strong additional assumptions are required:
$A,F,G$ are homogeneous, $G$ is a regular sequence, and in the end,
$\left\langle F\right\rangle=\left\langle G\right\rangle$ is only satisfied up
to saturation. Thus, they are not compatible with our setting and method for
Prob. 4.1.

Proposition 4.8 states that any matrix
$A\in\mathrm{SL}_{n}({k[x_{1},\ldots,x_{n}]})$ satisfies Prob. 4.6. This
raises two sets of open questions: (i) are there matrices outside
$\mathrm{SL}_{n}({k[x_{1},\ldots,x_{n}]})$ satisfying Prob. 4.6? Can we sample
them? and (ii) is it possible to efficiently sample matrices of
$\mathrm{SL}_{n}({k[x_{1},\ldots,x_{n}]})$? To efficiently generate our
dataset, we have restricted ourselves to sampling matrices having a Bruhat
decomposition (see Eq. (4.2)), which is a strict subset of
$\mathrm{SL}_{n}({k[x_{1},\ldots,x_{n}]})$. Sampling matrices in
$\mathrm{SL}_{n}({k[x_{1},\ldots,x_{n}]})$ remains an open question. Thanks to
the Suslin’s stability theorem and its algorithmic proofs (Suslin, 1977; Park
& Woodburn, 1995; Lombardi & Yengui, 2005),
$\mathrm{SL}_{n}({k[x_{1},\ldots,x_{n}]})$ is generated by elementary matrices
and a decomposition into a product of elementary matrices can be computed
algorithmically. One may hope to use sampling of elementary matrices to sample
matrices of $\mathrm{SL}_{n}({k[x_{1},\ldots,x_{n}]})$. It is unclear whether
this can be efficient as many elementary matrices are needed (Lombardi &
Yengui, 2005).

In the experiments, we restricted ourselves to polynomial sets with a moderate
sequence length so that a standard transformer can handle it. Algebraically,
this relates to zero-dimensional ideals with small linear dimension (i.e.,
dimension of $k[x_{1},\ldots,x_{n}]/\langle{F}\rangle$, see Def. A.4). To
cover more general cases, zero-dimensional ideals with large linear dimensions
and positive-dimensional ideals have to be further considered, which needs
breakthroughs both in machine learning and algebra.

##  7 Conclusion

Solving polynomial systems, or computing Gröbner bases, are fundamental in
various applications but known for its doubly exponential time complexity. In
this study, we proposed the first training framework of transformers that
realizes Gröbner basis computation via learning. The main technical challenge
lies in an efficient generation of many pairs of (non-Gröbner set, Gröbner
basis) to construct a training set, leading us to address two unexplored
algebraic problems: random generation of Gröbner bases and the backward
Gröbner problem. We resolved these problems in the case of zero-dimensional
radical ideals, which are important in various applications. Our experiments
validate that the proposed method achieves an extreme acceleration in dataset
generation and that the transformer’s ability in Gröbner basis computation. In
a broad view, our study indicates that transformers may serve as a solver for
NP-hard problems, while most prior studies only address rather easy/moderate-
level problems. Besides, our results give a new motivation to computational
algebra to consider and address several unexplored problems, posing a new
direction and potential interactions of computational algebra and machine
learning.

#### Acknowledgement.

We would like to 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.
This research was supported by JST ACT-X Grant Number JPMJAX23C8 and JSPS
KAKENHI Grant Number JP22K13901.

## References

  * Abbott et al. (2008) John Abbott, Claudia Fassino, and Maria-Laura Torrente.  Stable border bases for ideals of points.  _Journal of Symbolic Computation_ , 43(12):883–894, 2008.
  * Agarwal et al. (2021) Vishesh Agarwal, Somak Aditya, and Navin Goyal.  Analyzing the nuances of transformers’ polynomial simplification abilities.  _ArXiv_ , abs/2104.14095, 2021.
  * Antonova et al. (2020) Rika Antonova, Maksim Maydanskiy, Danica Kragic, Sam Devlin, and Katja Hofmann.  Analytic manifold learning: Unifying and evaluating representations for continuous control.  arXiv preprint arXiv:2006.08718, 2020.
  * Arnold (2003) Elizabeth Arnold.  Modular algorithms for computing gröbner bases.  _Journal of Symbolic Computation_ , 35:403–419, 2003.
  * Atiyah & MacDonald (1994) Michael F. Atiyah and Ian G. MacDonald.  _Introduction To Commutative Algebra_.  Addison-Wesley series in mathematics. Avalon Publishing, 1994.
  * Bard (2009) Gregory V. Bard.  _Algorithms for Solving Polynomial Systems_.  Springer US, 2009.
  * Bardet et al. (2015) Magali Bardet, Jean-Charles Faugère, and Bruno Salvy.  On the complexity of the F5 Gröbner basis algorithm.  _Journal of Symbolic Computation_ , 70:49–70, September 2015.
  * Becker et al. (1993) Thomas Becker, Volker Weispfenning, and Heinz Kredel.  _Gröbner Bases: A Computational Approach to Commutative Algebra_.  Graduate texts in mathematics. Springer-Verlag, 1993.
  * Berthomieu et al. (2022) Jérémy Berthomieu, Vincent Neiger, and Mohab Safey El Din.  Faster change of order algorithm for gröbner bases under shape and stability assumptions.  In _Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation_ , ISSAC ’22, pp. 409–418, New York, NY, USA, 2022\. Association for Computing Machinery.
  * Berthomieu et al. (2023) Jérémy Berthomieu, Stef Graillat, Dimitri Lesnoff, and Theo Mary.  Modular matrix multiplication on gpu for polynomial system solving.  _ACM Commun. Comput. Algebra_ , 57(2):35–38, August 2023.
  * Biggio et al. (2021) Luca Biggio, Tommaso Bendinelli, Alexander Neitz, Aurelien Lucchi, and Giambattista Parascandolo.  Neural symbolic regression that scales.  _arXiv_ , abs/2106.06427, 2021.
  * Brickenstein (2010) Michael Brickenstein.  Slimgb: Gröbner bases with slim polynomials.  _Revista Matemática Complutense_ , 23:453–466, 2010\.
  * Buchberger (1965) Bruno Buchberger.  _Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen 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 Computation, Special Issue on Logic, Mathematics, and Computer Science: Interactions. Vol. 41, Number 3-4, Pages 475–511, 2006.
  * Busé (2001) Laurent Busé.  _Étude du résultant sur une variété algébrique_.  Theses, Université Nice Sophia Antipolis, 2001.
  * Busé et al. (2001) Laurent Busé, Mohamed Elkadi, and Bernard Mourrain.  Resultant over the residual of a complete intersection.  _Journal of Pure and Applied Algebra_ , 164(1):35–57, 2001.
  * Charton (2022a) Francois Charton.  Linear algebra with transformers.  _Transactions on Machine Learning Research_ , 2022a.  URL https://openreview.net/forum?id=Hp4g7FAXXG.
  * Charton (2022b) Francois Charton.  What is my math transformer doing? - three results on interpretability and generalization.  _ArXiv_ , abs/2211.00170, 2022b.
  * Charton et al. (2021) Francois Charton, Amaury Hayat, and Guillaume Lample.  Learning advanced mathematical computations from examples.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=-gfhS00XfKj.
  * Cognolato & Testolin (2022) Samuel Cognolato and Alberto Testolin.  Transformers discover an elementary calculation system exploiting local attention and grid-like problem representation, 2022.
  * Cox (2005) David A. Cox.  Solving equations via algebras.  In _Solving Polynomial Equations_ , pp. 63–124. Springer-Verlag, Berlin, 2005.
  * Cox et al. (2015) David A. Cox, John Little, and Donald O’Shea.  _Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra_.  Undergraduate Texts in Mathematics. Springer International Publishing, 2015.
  * d’Ascoli et al. (2022) Stéphane d’Ascoli, Pierre-Alexandre Kamienny, Guillaume Lample, and François Charton.  Deep symbolic regression for recurrence prediction.  _International Conference on Machine Learning_ , 2022.
  * Diaconis & Sturmfels (1998) Persi Diaconis and Bernd Sturmfels.  Algebraic algorithms for sampling from conditional distributions.  _The Annals of Statistics_ , 26(1):363 – 397, 1998.
  * Ding et al. (2023) Jiayu Ding, Shuming Ma, Li Dong, Xingxing Zhang, Shaohan Huang, Wenhui Wang, Nanning Zheng, and Furu Wei.  LongNet: Scaling Transformers to 1,000,000,000 tokens, 2023.
  * Dubé (1990) Thomas W. Dubé.  The structure of polynomial ideals and Gröbner bases.  _SIAM Journal on Computing_ , 19(4):750–773, 1990\.
  * Dziri et al. (2023) Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi.  Faith and fate: Limits of transformers on compositionality, 2023.
  * Eisenbud (2013) David Eisenbud.  _Commutative algebra: with a view toward algebraic geometry_.  Springer Science & Business Media, 2013.
  * Fassino (2010) Claudia Fassino.  Almost vanishing polynomials for sets of limited precision points.  _Journal of Symbolic Computation_ , 45(1):19–37, 2010.
  * Faugère (1999) Jean-Charles Faugère.  A new efficient algorithm for computing Gröbner bases (F4).  _Journal of Pure and Applied Algebra_ , 139(1):61–88, 1999.
  * Faugère (2002) Jean-Charles 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, pp. 75–83, New York, NY, USA, 2002\. Association for Computing Machinery.
  * Faugère et al. (1993) Jean-Charles Faugère, Patrizia M. Gianni, Daniel Lazard, and Teo Mora.  Efficient computation of zero-dimensional Gröbner bases by change of ordering.  _Journal of Symbolic Computation_ , 16(4):329–344, 1993.
  * Gianni & Mora (1989) Patrizia Gianni and Teo Mora.  Algebraic solution of systems of polynomial equations using Groebner bases.  In _Applied Algebra, Algebraic Algorithms and Error-Correcting Codes_ , pp. 247–257, Berlin, Heidelberg, 1989. Springer Berlin Heidelberg.
  * Gruel & Pfister (2008) Gert-Martin Gruel and Gerhard Pfister.  _A Singular Introduction to Commutative Algebra, 2nd Edition_.  Sringer Verlag, 2008.
  * Heldt et al. (2009) Daniel Heldt, Martin Kreuzer, Sebastian Pokutta, and Hennie Poulisse.  Approximate computation of zero-dimensional polynomial ideals.  _Journal of Symbolic Computation_ , 44(11):1566–1591, 2009.
  * Hibi (2014) Takayuki Hibi.  _Gröbner bases. Statistics and software systems._ Springer Tokyo, March 2014.
  * Hou et al. (2016) Chenping Hou, Feiping Nie, and Dacheng Tao.  Discriminative vanishing component analysis.  In _Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI)_ , pp. 1666–1672, Palo Alto, California, 2016. AAAI Press.
  * Iraji & Chitsaz (2017) Reza Iraji and Hamidreza Chitsaz.  Principal variety analysis.  In _Proceedings of the 1st Annual Conference on Robot Learning (ACRL)_ , pp. 97–108. PMLR, 2017.
  * Kamienny et al. (2022) Pierre-Alexandre Kamienny, Stéphane d’Ascoli, Guillaume Lample, and Francois Charton.  End-to-end symbolic regression with transformers.  In _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=GoOuIrDHG_Y.
  * Kamienny et al. (2023) Pierre-Alexandre Kamienny, Guillaume Lample, Sylvain Lamprier, and Marco Virgolin.  Deep generative symbolic regression with Monte-Carlo-Tree-Search.  _arXiv_ , abs/2302.11223, 2023.
  * Karimov et al. (2020) Artur Karimov, Erivelton G. Nepomuceno, Aleksandra Tutueva, and Denis Butusov.  Algebraic method for the reconstruction of partially observed nonlinear systems using differential and integral embedding.  _Mathematics_ , 8(2):300–321, February 2020.
  * Kehrein & Kreuzer (2006) Achim Kehrein and Martin Kreuzer.  Computing border bases.  _Journal of Pure and Applied Algebra_ , 205(2):279–295, 2006.
  * Kera (2022) Hiroshi Kera.  Border basis computation with gradient-weighted normalization.  In _Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation_ , pp. 225–234, New York, 2022. Association for Computing Machinery.
  * Kera & Hasegawa (2016) Hiroshi Kera and Yoshihiko Hasegawa.  Noise-tolerant algebraic method for reconstruction of nonlinear dynamical systems.  _Nonlinear Dynamics_ , 85(1):675–692, 2016.
  * Kera & Hasegawa (2018) Hiroshi Kera and Yoshihiko Hasegawa.  Approximate vanishing ideal via data knotting.  In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI)_ , pp. 3399–3406, Palo Alto, California, 2018\. AAAI Press.
  * Kera & Hasegawa (2019) Hiroshi Kera and Yoshihiko Hasegawa.  Spurious vanishing problem in approximate vanishing ideal.  _IEEE Access_ , 7:178961–178976, 2019.
  * Kera & Hasegawa (2020) Hiroshi Kera and Yoshihiko Hasegawa.  Gradient boosts the approximate vanishing ideal.  In _Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI)_ , pp. 4428–4425, Palo Alto, California, 2020\. AAAI Press.
  * Kera & Iba (2016) Hiroshi Kera and Hitoshi Iba.  Vanishing ideal genetic programming.  In _Proceedings of the 2016 IEEE Congress on Evolutionary Computation (CEC)_ , pp. 5018–5025, Piscataway, NJ, 2016. IEEE.
  * Kim et al. (2021) Segwang Kim, Hyoungwook Nam, Joonyoung Kim, and Kyomin Jung.  Neural sequence-to-grid module for learning symbolic rules.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 8163–8171, May 2021.
  * Király et al. (2014) Franz J Király, Martin Kreuzer, and Louis Theran.  Dual-to-kernel learning with ideals.  _ArXiv_ , abs/1402.0099, 2014.
  * Kitaev et al. (2020) Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya.  Reformer: The efficient transformer.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=rkgNKkHtvB.
  * Lample & Charton (2019) Guillaume Lample and François Charton.  Deep learning for symbolic mathematics.  _ArXiv_ , abs/1912.01412, 2019.
  * Laubenbacher & Sturmfels (2009) Reinhard Laubenbacher and Bernd Sturmfels.  Computer algebra in systems biology.  _American Mathematical Monthly_ , 116(10):882–891, 2009.
  * Li et al. (2023) Cathy Li, Jana Sotakova, Emily Wenger, Zeyuan Allen-Zhu, Francois Charton, and Kristin Lauter.  SALSA VERDE: a machine learning attack on Learning With Errors with sparse small secrets, 2023.
  * Limbeck (2013) Jan Limbeck.  _Computation of approximate border bases and applications_.  PhD thesis, Passau, Universität Passau, 2013.
  * Livni et al. (2013) Roi Livni, David Lehavi, Sagi Schein, Hila Nachliely, Shai Shalev-Shwartz, and Amir Globerson.  Vanishing component analysis.  In _Proceedings of the 30th International Conference on Machine Learning_ , volume 28(1) of _Proceedings of Machine Learning Research_ , pp. 597–605, Atlanta, Georgia, USA, June 2013. PMLR.
  * Lombardi & Yengui (2005) Henri Lombardi and Ihsen Yengui.  Suslin’s algorithms for reduction of unimodular rows.  _Journal of Symbolic Computation_ , 39(6):707–717, 2005.
  * Loshchilov & Hutter (2019) Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=Bkg6RiCqY7.
  * Makarim & Stevens (2017) Rusydi H. Makarim and Marc Stevens.  M4GB: An efficient Gröbner-basis algorithm.  In _Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation_ , ISSAC’17, pp. 293–300, New York, NY, USA, 2017. Association for Computing Machinery.
  * Mayr & Meyer (1982) Ernst W. Mayr and Albert R. Meyer.  The complexity of the word problems for commutative semigroups and polynomial ideals.  _Advances in Mathematics_ , 46(3):305–329, 1982\.
  * Möller & Buchberger (1982) H. Michael Möller and Bruno Buchberger.  The construction of multivariate polynomials with preassigned zeros.  In _Computer Algebra. EUROCAM 1982. Lecture Notes in Computer Science_ , pp. 24–31. Springer Berlin Heidelberg, 1982.
  * Noro & Yokoyama (1999) Masayuki Noro and Kazuhiro Yokoyama.  A modular method to compute the rational univariate representation of zero-dimensional ideals.  _Journal of Symbolic Computation_ , 28(1):243–263, 1999.
  * Noro & Yokoyama (2018) Masayuki Noro and Kazuhiro Yokoyama.  Usage of modular techniques for efficient computation of ideal operations.  _Math. Comput. Sci._ , 12(1):1–32, 2018.
  * Park & Regensburger (2007) Hyungju Park and Georg Regensburger (eds.).  _Gröbner Bases in Control Theory and Signal Processing_.  De Gruyter, 2007.
  * Park & Woodburn (1995) Hyungjyu Park and Cynthia Woodburn.  An algorithmic proof of Suslin’s stability theorem for polynomial rings.  _Journal of Algebra_ , 178(1):277–298, 1995.
  * Peifer et al. (2020) Dylan Peifer, Michael Stillman, and Daniel Halpern-Leistner.  Learning selection strategies in buchberger’s algorithm.  In _Proceedings of the 37th International Conference on Machine Learning_ , ICML’20. JMLR.org, 2020.
  * Saxton et al. (2019) David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli.  Analysing mathematical reasoning abilities of neural models.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=H1gR5iR5FX.
  * Shao et al. (2016) Yunxue Shao, Guanglai Gao, and Chunheng Wang.  Nonlinear discriminant analysis based on vanishing component analysis.  _Neurocomputing_ , 218:172–184, 2016.
  * Stewenius (2005) Henrik Stewenius.  _Gröbner Basis Methods for Minimal Problems in Computer Vision_.  PhD thesis, Mathematics (Faculty of Engineering), 2005.
  * Sun et al. (2023) Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei.  Retentive network: A successor to Transformer for large language models, 2023.
  * Suslin (1977) Andrey Aleksandrovich Suslin.  On the structure of the special linear group over polynomial rings.  _Mathematics of the USSR - Izvestija_ , 11(2):221–238, April 1977.
  * The Sage Developers (2023) The Sage Developers.  _SageMath, the Sage Mathematics Software System (Version 10.0)_ , 2023.  https://www.sagemath.org.
  * Traverso (1997) Carlo Traverso.  Hilbert functions and the Buchberger algorithm.  _Journal of Symbolic Computation_ , 6:287–304, 1997.
  * Ullah (2012) Ehsan Ullah.  _New Techniques for Polynomial System Solving_.  PhD thesis, Universität Passau, 2012.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Wang & Ohtsuki (2018) Lu Wang and Tomoaki Ohtsuki.  Nonlinear blind source separation unifying vanishing component analysis and temporal structure.  _IEEE Access_ , 6:42837–42850, 2018.
  * Wang & Deng (2020) Mingzhe Wang and Jia Deng.  Learning to prove theorems by learning to generate theorems.  _ArXiv_ , abs/2002.07019, 2020.
  * Wang et al. (2019) Zhichao Wang, Qian Li, Gang Li, and Guandong Xu.  Polynomial representation for persistence diagram.  In _Proceedings of the 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 6116–6125, Los Alamitos, California, 2019. Conference Publishing Services.  doi: 10.1109/CVPR.2019.00628.
  * Wenger et al. (2022) Emily Wenger, Mingjie Chen, Francois Charton, and Kristin E. Lauter.  SALSA: Attacking lattice cryptography with Transformers.  In _Advances in Neural Information Processing Systems_ , volume 35, pp. 34981–34994. Curran Associates, Inc., 2022.
  * Wirth & Pokutta (2022) Elias Wirth and Sebastian Pokutta.  Conditional gradients for the approximately vanishing ideal.  _ArXiv_ , abs/2202.03349, 2022.
  * Wirth et al. (2023) Elias Samuel Wirth, Hiroshi Kera, and Sebastian Pokutta.  Approximate vanishing ideal computations at scale.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=3ZPESALKXO.
  * Yan et al. (2018) Hongliang Yan, Zifei Yan, Gang Xiao, Weizhi Wang, and Wangmeng Zuo.  Deep vanishing component analysis network for pattern classification.  _Neurocomputing_ , 316:240–250, 2018.
  * Yasuda et al. (2015) Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, Tsuyoshi Takagi, and Kouichi Sakurai.  MQ challenge: hardness evaluation of solving multivariate quadratic problems.  _Cryptology ePrint Archive_ , 2015.

##  A Basic Definitions in Algebra

######  Definition A.1 (Ring, Field (Atiyah & MacDonald (1994), Chap. 1 §1)).

A set $R$ with an additive operation $+$ and a multiplicative operation $*$ is
called a (commutative) ring if it satisfies the following conditions:

  1. 1.

$a+(b+c)=(a+b)+c$ for any $a,b,c\in R$,

  2. 2.

there exists $0\in R$ such that $a+0=0+a=a$ for any $a\in R$,

  3. 3.

for any $a\in R$, there exists $-a$ such that $a+(-a)=(-a)+a=0$,

  4. 4.

$a+b=b+a$ for any $a,b\in R$,

  5. 5.

$a*(b*c)=(a*b)*c$ for any $a,b,c\in R$,

  6. 6.

there exists $1\in R$ such that $a*1=1*a=a$ for any $a\in R$,

  7. 7.

$a*(b+c)=a*b+a*c$ for any $a,b,c\in R$,

  8. 8.

$(a+b)*c=a*c+b*c$ for any $a,b,c\in R$,

  9. 9.

$a*b=b*a$ for any $a,b\in R$.

A commutative ring $R$ is called a field if it satisfies the following
condition

  1. 10.

for any $a\in R\setminus\\{0\\}$, there exists $a^{-1}$ such that
$a*a^{-1}=a^{-1}*a=1$.

######  Definition A.2 (Polynomial Ring (Atiyah & MacDonald (1994), Chap. 1
§1)).

In Definition A.1, $k[x_{1},\ldots,x_{n}]$, the set of all $n$-variate
polynomials with coefficients in $k$, satisfies all conditions (1)-(9). Thus,
$k[x_{1},\ldots,x_{n}]$ is called a polynomial ring.

######  Definition A.3 (Quotient Ring (Atiyah & MacDonald (1994), Chap. 1
§1)).

Let $R$ be a ring and $I$ an ideal of $R$. For each $f\in R$, we set
$[f]=\\{g\in R\mid f-g\in I\\}$. Then, the set $\\{[f]\mid f\in R\\}$ is
called the quotient ring of $R$ modulo $I$ and denoted by $R/I$. Indeed, $R/I$
is a ring with an additive operation $+$ and a multiplicative operation $*$,
where $[f]+[g]=[f+g]$ and $[f]*[g]=[f*g]$ for $f,g\in R$ respectively.

######  Definition A.4 (Zero-dimensional ideal (Cox et al. (2015), Chap. 5 §3,
Thm. 6)).

Let $F$ be a set of polynomials in $k[x_{1},\ldots,x_{n}]$. An ideal
$\langle{F}\rangle$ is called a zero-dimensional ideal if the $k$-linear space
$k[x_{1},\ldots,x_{n}]/\langle{F}\rangle$ is finite-dimensional, where
$k[x_{1},\ldots,x_{n}]/\langle{F}\rangle$ is the quotient ring of
$k[x_{1},\ldots,x_{n}]$ modulo $\langle{F}\rangle$.

######  Definition A.5 (Radical ideal (Atiyah & MacDonald (1994), Chap. 1
§1)).

For an ideal $I$ of $k[x_{1},\ldots,x_{n}]$, the set $\\{f\in
k[x_{1},\ldots,x_{n}]\mid f^{m}\in I\text{ for a positive integer $m$}\\}$ is
called the radical of $I$ and denoted by $\sqrt{I}$. Also, $I$ is called a
radical ideal if $I=\sqrt{I}$.

######  Definition A.6 (Syzygy (Becker et al. (1993), Chap. 3, §3)).

Let $F=\quantity{f_{1},\ldots,f_{s}}\subset k[x_{1},\ldots,x_{n}]$. A syzygy
of $F$ is an $s$-tuple of polynomials $(q_{1},\ldots,q_{s})\in
k[x_{1},\ldots,x_{n}]^{s}$ such that $q_{1}f_{1}+\cdots+q_{s}f_{s}=0$.

######  Definition A.7 (Term (Becker et al. (1993), Chap. 2, §1)).

For a polynomial
$f=\sum_{\alpha_{1},\ldots,\alpha_{n}}c_{\alpha_{1},\ldots,\alpha_{n}}x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}$ with $c_{\alpha_{1},\ldots,\alpha_{n}}\in K$ and
$\alpha_{1},\ldots,\alpha_{n}\in{\mathbb{Z}}_{\geq 0}$, each
$x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$ is called a term in $f$.

######  Definition A.8 (Total Degree (Cox et al. (2015), Chap. 1 §1, Def. 3)).

For a term $x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$, its total degree is
the sum of indices $\alpha_{1}+\cdots+\alpha_{n}$. For a polynomial $f$, the
total degree of $f$ is the maximal total degree of terms in $f$.

######  Definition A.9 (Term order (Becker et al. (1993), Definition 5.3)).

A term order $\prec$ is a relation between terms such that

  1. 1.

(comparability) for different terms $x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}$ and $x_{1}^{\beta_{1}}\cdots x_{n}^{\beta_{n}}$, either
$x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}\prec x_{1}^{\beta_{1}}\cdots
x_{n}^{\beta_{n}}$ or $x_{1}^{\beta_{1}}\cdots x_{n}^{\beta_{n}}\prec
x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$ holds,

  2. 2.

(order-preserving) for terms $x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$,
$x_{1}^{\beta_{1}}\cdots x_{n}^{\beta_{n}}$ and $x_{1}^{\gamma_{1}}\cdots
x_{n}^{\gamma_{n}}\neq 1$, if $x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}\prec x_{1}^{\beta_{1}}\cdots x_{n}^{\beta_{n}}$ then
$x_{1}^{\alpha_{1}+\gamma_{1}}\cdots x_{n}^{\alpha_{n}+\gamma_{n}}\prec
x_{1}^{\beta_{1}++\gamma_{1}}\cdots x_{n}^{\beta_{n}+\gamma_{n}}$ holds,

  3. 3.

(minimality of 1) the term $1$ is the smallest term i.e. $1\prec
x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$ for any term
$x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}\neq 1$.

######  Example A.10.

The graded lexicographic order $\prec_{\mathrm{grlex}}$ prioritizes terms with
higher total degree.101010The total degree of term $x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}$ refers to $\sum_{i=1}^{n}\alpha_{i}$. The total degree of
polynomial $f$ refers to the maximum total degree of the terms in $f$. For
tie-break, the lexicographic order is used, e.g.,

$\displaystyle 1\prec_{\mathrm{grlex}}x_{n}\quad\text{and}\quad
x_{2}\prec_{\mathrm{grlex}}x_{3}^{2}\quad\text{and}\quad
x_{1}x_{2}x_{3}^{2}\prec_{\mathrm{grlex}}x_{1}x_{2}^{2}x_{3}.$ (A.1)

Term orders prioritizing lower total degree terms as $\prec_{\mathrm{grlex}}$
are called graded term orders.

######  Definition A.11 (Reduced Gröbner basis).

A $\prec$-Gröbner basis $G=\\{g_{1},\ldots,g_{t}\\}$ of $I$ is called the
reduced Gröbner basis of $I$ if

  1. 1.

the leading coefficient of $g_{i}$ with respect to $\prec$ is 1 for all
$i=1,\ldots,t$,

  2. 2.

no terms of $g_{i}$ lies on
$\langle{\mathrm{LT}({G\setminus\\{g_{i}\\}})}\rangle$ for any $i=1,\ldots,t$.

##  B Buchberger–Möller Alg. for Prob. 4.1

Here, we discuss another approach for Prob. 4.1 using the Buchberger–Möller
(BM) algorithm (Möller & Buchberger, 1982). Although we did not adopt this
approach, we include this for completeness because many algorithm variants
have been recently developed and applied extensively in machine learning and
other data-centric applications.

Given a set of points ${\mathbb{X}}\subset k^{n}$ and a graded term order, the
BM algorithm computes a Gröbner basis of its vanishing ideal
$I({\mathbb{X}})=\\{g\in k[x_{1},\ldots,x_{n}]\mid g(p)=0,\forall
p\in{\mathbb{X}}\\}$. While several variants follow in computational algebra
(Kehrein & Kreuzer, 2006; Abbott et al., 2008; Heldt et al., 2009; Fassino,
2010; Limbeck, 2013; Kera, 2022), interestingly, it is also recently tailored
for machine learning (Livni et al., 2013; Király et al., 2014; Hou et al.,
2016; Kera & Hasegawa, 2018, 2019, 2020; Wirth & Pokutta, 2022; Wirth et al.,
2023) and has been applied to various contexts such as machine learning (Shao
et al., 2016; Yan et al., 2018), signal processing (Wang & Ohtsuki, 2018; Wang
et al., 2019; Wang & Deng, 2020), nonlinear dynamics (Kera & Hasegawa, 2016;
Karimov et al., 2020), and more (Kera & Iba, 2016; Iraji & Chitsaz, 2017;
Antonova et al., 2020). Such a wide range of applications derives from the
distinguishing design of the BM algorithm: while most computer-algebraic
algorithms take a set of polynomials as input, it takes a set of points (i.e.,
dataset).

Therefore, to address Prob. 4.1, one may consider using the BM algorithm or
its variants, e.g., by running the BM algorithm $m$ times while sampling
diverse sets of points. An important caveat is that Gröbner bases that can be
given by the BM algorithm may be more restrictive than those considered in the
main text (i.e., the Gröbner bases of ideals in shape position). For example,
the former generates the largest ideals that have given $k$-rational points
for their roots, whereas this is not the case for the latter. Another drawback
of using the BM algorithm is its large computational cost. The time complexity
of the BM algorithm is ${\mathcal{O}}(n\cdot|{\mathbb{X}}|^{3})$. Furthermore,
we need ${\mathcal{O}}(n^{d})$ points to obtain a Gröbner basis that includes
a polynomial of degree $d$ in the average case. Therefore, the BM algorithm
does not fit our settings that a large number of Gröbner bases are needed
(i.e., $m\approx 10^{6}$). Accelerating the BM algorithm by reusing the
results of runs instead of independently running the algorithm many times can
be interesting for future work.

##  C Proofs

See 4.7

###### Proof.

(1) In general, if an ideal $I$ is generated by $s$ elements and $s<n$, then
the Krull dimension of $k[x_{1},\ldots,x_{n}]/I$ satisfies that $\dim
k[x_{1},\ldots,x_{n}]/I\geq n-s>0$ (Krull’s principal ideal theorem (Eisenbud,
2013, §10)). Since the Krull dimension of $k[x_{1},\ldots,x_{n}]/\langle
G\rangle$ is 0, we have $s\geq n$.

(2) From $F=AG$, we have $\langle F\rangle\subset\langle G\rangle$. If $A$ has
a left-inverse $B\in k[x_{1},\ldots,x_{n}]^{t\times s}$, we have $BF=BAG=G$,
indicating $\langle F\rangle\supset\langle G\rangle$. Therefore, we have
$\langle F\rangle=\langle G\rangle$.

(3) If the equality $\langle{F}\rangle=\langle{G}\rangle$ holds, then there
exists a $t\times s$ matrix $B\in k[x_{1},\ldots,x_{n}]^{t\times s}$ such that
$G=BF$. Since $F$ is defined as $F=AG$, we have $G=BF=BAG$ and $G=E_{t}G$ in
$k[x_{1},\ldots,x_{n}]^{t}$. Therefore we obtain $(BA-E_{t})G=0$. In
particular, each row of $BA-E_{t}$ is a syzygy of $G$. Conversely, if there
exists a $t\times s$ matrix $B\in k[x_{1},\ldots,x_{n}]^{t\times s}$ such that
each row of $BA-E_{t}$ is a syzygy of $G$, then we have $(BA-E_{t})G=0$ in
$k[x_{1},\ldots,x_{n}]^{t}$, therefore the equality
$\langle{F}\rangle=\langle{G}\rangle$ holds since we have $G=E_{t}G=BAG=BF$. ∎

See 4.8

###### Proof.

From the Cramer’s rule, there exists $B\in k[x_{1},\ldots,x_{n}]^{n\times n}$
such that $BA=\det(A)E_{n}$, where $E_{n}$ denotes the $n$-by-$n$ identity
matrix. Indeed, the $i$-th row $B_{i}$ of $B$ satisfies for $i=1,\ldots,n$,

$\displaystyle
B_{i}=\matrixquantity(\det(\tilde{A}_{1}^{(i)}),\ldots,\det(\tilde{A}_{n}^{(i)})),$
(C.1)

where $\tilde{A}_{j}^{(i)}$ is the matrix $A$ with the $j$-th column replaced
by the $i$-th canonical basis $e_{i}=(0,...,1,...,0)^{\top}$. Since $\det(A)$
is a non-zero constant, $A$ has the left-inverse $B/\det(A)$ in
$k[x_{1},\ldots,x_{n}]$. Thus $\langle{F}\rangle=\langle{G}\rangle$ from Thm.
4.7. ∎

See 4.9

###### Proof.

Outside of the Zariski subset part, statements 1–3 are trivial from Alg. 1 and
the discussion in Sec.s 4.1 and 4.2. To obtain the desired Zariski subsets, we
consider the vector space of polynomials of degree $d+2d^{\prime}$ or less. We
remark that if $F_{i}$ is a $\prec$-Gröbner basis, its leading terms must
belong to a finite amount of possibilities. For a polynomial to have a given
term as its leading term, zero conditions on terms greater than this term are
needed, defining a closed Zariski subset condition. By considering the finite
union of all these conditions, we obtain the desired result.

To obtain one pair $(F,G)$, the random generation of $G$ needs
${\mathcal{O}}(nS_{1,d})$, and the backward transform from $G$ to $F$ needs
${\mathcal{O}}(s^{2}S_{n,d^{\prime}})$ to get $U_{1},U_{2}$ and
$(n^{2}+s^{2})M_{n,2d^{\prime}+d})$ for the multiplication $F=U_{1}PU_{2}G$.
Note that the maximum total degree of polynomials in $F$ is $2d^{\prime}+d$. ∎

##  D Training Setup and Additional Experimental Results.

This section provides the supplemental information of our experiments
presented in Sec. 5.

###  D.1 Gröbner basis computation algorithms

In Tab. 1, we tested three algorithms provided in Sagemath with the
libSingular backend for forward generation.

####  std (libsingular:std):

The standard Buchberger algorithm.

####  slimgb (libsingular:slimgb):

A variant of the Faugère’s F4 algorithm. Refer to (Brickenstein, 2010).

####  stdfglm (libsingular:stdfglm):

Fast computation using std with the graded reverse lexicographic order
followed by the FGLM for the change of term orders.

###  D.2 Detaset profiles

Table 3: Runtime comparison (in seconds/millisecond) of forward generation (F.) and backward generation (B.) of dataset ${\mathcal{D}}_{n}({\mathbb{F}}_{p})$ of size 1000. The forward generation used either of the three algorithms provided in Sagemath with the libSingular backend. The backward generation is two orders of magnitude faster than the forward generation. Method | ${\mathbb{F}}_{7}[x_{1},\ldots,x_{n}]$ | ${\mathbb{F}}_{31}[x_{1},\ldots,x_{n}]$
---|---|---
$n=2$ |  $n=3$ |  $n=4$ |  $n=5$ |  $n=2$ |  $n=3$ |  $n=4$ |  $n=5$
|  $\sigma=1$ |  $0.6$ |  $0.3$ |  $0.2$ |  $\sigma=1$ |  $0.6$ |  $0.3$ |  $0.2$
F. (std) [sec] |  0.37 |  0.40 |  6.33 |  4.29 |  0.38 |  0.42 |  7.32 |  4.77
F. (slimgb) |  0.44 |  0.58 |  5.98 |  5.79 |  0.41 |  0.61 |  5.79 |  6.39
F. (stdfglm) |  0.99 |  1.11 |  6.24 |  6.34 |  1.01 |  1.11 |  6.34 |  6.62
B. (ours) [msec] |  2.23 |  2.47 |  2.51 |  2.78 |  2.12 |  2.45 |  2.42 |  2.79
Table 4: A profile of the generated datasets (relevant to Tab. 1). The standard deviation is shown in the superscript. Method | ${\mathbb{F}}_{7}[x_{1},\ldots,x_{n}]$ | ${\mathbb{F}}_{31}[x_{1},\ldots,x_{n}]$
---|---|---
$n=2$ |  $n=3$ |  $n=4$ |  $n=5$ |  $n=2$ |  $n=3$ |  $n=4$ |  $n=5$
size of $F$ |  3.0(±0.8) |  4.0(±0.7) |  5.0(±0.8) |  6.0(±0.8) |  3.0(±0.8) |  3.9(±0.8) |  4.9(±0.8) |  6.0(±0.8)
max deg in $F$ |  8.9(±1.8) |  9.8(±1.2) |  10(±1.0) |  10(±0.8) |  8.7(±1.8) |  9.9(±1.3) |  10(±0) |  10(±0)
min deg in $F$ |  5.6(±1.8) |  5.9(±1.9) |  6.3(±1.9) |  6.5(±1.8) |  5.4(±1.9) |  6.1(±1.8) |  6.4(±1.8) |  6.6(±1.6)
#terms in $F$ |  23(±9.6) |  34(±10) |  45(±10) |  57(±11) |  22(±9.5) |  33(±10) |  45(±10) |  57(±11)
GB ratio [%] |  0.10 |  0.00 |  0.00 |  0.00 |  0.20 |  0.00 |  0.00 |  0.00
size of $G$ |  2.0(±0) |  3.0(±0) |  4.0(±0) |  5.0(±0) |  2.0(±0) |  3.0(±0) |  4.0(±0) |  5.0(±0)
max deg in $G$ |  4.3(±1.0) |  4.3(±0.8) |  4.4(±0.8) |  4.4(±0.7) |  4.2(±1.0) |  4.4(±0.8) |  4.4(±0.7) |  4.5(±0.70)
min deg in $G$ |  3.7(±1.5) |  3.2(±1.6) |  3.0(±1.7) |  2.8(±1.6) |  3.4(±1.6) |  3.6(±1.6) |  3.5(±1.7) |  3.4(±1.7)
#terms in $G$ |  8.1(±2.4) |  11(±3.6) |  15(±4.9) |  19(±6.1) |  7.7(±2.5) |  12(±3.6) |  16(±4.8) |  20(±6.1)
GB ratio [%] |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  100
Table 5: A profile of datasets generated with a density control (relevant to Tab. 3). The standard deviation is shown in the superscript. Metric | ${\mathbb{F}}_{7}[x_{1},\ldots,x_{n}]$ | ${\mathbb{F}}_{31}[x_{1},\ldots,x_{n}]$
---|---|---
$n=2$ |  $n=3$ |  $n=4$ |  $n=5$ |  $n=2$ |  $n=3$ |  $n=4$ |  $n=5$
|  $\sigma=1$ |  $0.6$ |  $0.3$ |  $0.2$ |  $\sigma=1$ |  $0.6$ |  $0.3$ |  $0.2$
size of $F$ |  3.0(±0.8) |  4.0(±0.8) |  5.0(±0.8) |  6.0(±0.8) |  3.0(±0.8) |  4.0(±0.8) |  5.0(±0.8) |  6.0(±0.8)
max deg in $F$ |  8.8(±1.9) |  8.5(±1.9) |  8.4(±1.9) |  8.6(±1.8) |  8.7(±1.9) |  8.8(±1.9) |  8.6(±1.8) |  8.7(±1.8)
min deg in $F$ |  5.6(±1.9) |  4.1(±2.3) |  3(±2.3) |  2.6(±2.3) |  5.5(±1.9) |  4.3(±2.2) |  3.2(±2.4) |  2.9(±2.4)
#terms in $F$ |  23(±9.6) |  26(±10) |  29(±10) |  34(±11) |  23(±9.5) |  27(±10) |  30(±10) |  35(±11)
GB ratio [%] |  0.10 |  1.60 |  2.20 |  0.70 |  0.10 |  1.50 |  1.80 |  1.10
size of $G$ |  2.0(±0) |  3.0(±0) |  4.0(±0) |  5.0(±0) |  2.0(±0) |  3.0(±0) |  4.0(±0) |  5.0(±0)
max deg in $G$ |  4.3(±1) |  4.4(±0.8) |  4.4(±0.79) |  4.5(±0.7) |  4.2(±1.1) |  4.4(±0.8) |  4.5(±0.7) |  4.5(±0.7)
min deg in $G$ |  3.8(±1.6) |  3.2(±1.7) |  3(±1.7) |  2.9(±1.7) |  3.5(±1.6) |  3.6(±1.7) |  3.5(±1.7) |  3.5(±1.8)
#terms in $G$ |  8.1(±2.5) |  12(±3.6) |  15(±4.9) |  19(±6.1) |  7.7(±2.5) |  12(±3.7) |  16(±4.9) |  20(±6.1)
GB ratio [%] |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  100

We used datasets generated with a density control for training a transformer.
The runtime comparison for these datasets is given in Tab. 3. Because of the
density control, the forward generation uses less runtime but still needs a
long runtime if one needs to construct a training set with a million samples.
The backward generation used roughly 100 times less runtime. The dataset
profile of datasets are given in Tabs. 4 and 5.

###  D.3 Training of transformers.

To examine the transformer’s ability to learn Gröbner basis computation, we
focus on a standard architecture and training setup. We used a transformer
model (Vaswani et al., 2017) with standard architectures, e.g., 6
encoder/decoder layers, 8 attention heads, token embedding dimension of 512
dimensions, and feed-forward networks with 2048 inner dimensions. The dropout
rate was set to 0.1. We used the AdamW optimizer (Loshchilov & Hutter, 2019)
with $(\beta_{1},\beta_{2})=(0.9,0.999)$ with no weight decay. The learning
rate was initially set to $10^{-4}$ and then linearly decayed over training
steps. All training samples are visited in a single epoch, and the total
number of epochs was set to 10. The batch size was set to 8. At the inference
time, output sequences are generated using a beam search with width 1.

Tabs. 6– 9 show examples of success cases and Tab. 10 shows examples of
failure cases. One can see from the former that transformers accomplish
difficult computations and from the latter, interestingly, that the incorrect
predictions appear reasonable.

Table 6: Success examples ($n=2$) ID |  $F$ |  $G$
---|---|---
0 |  $f_{1}$ = $-3x_{0}^{3}+2x_{0}^{2}x_{1}+x_{1}^{3}$ |  $g_{1}$ = $x_{0}-3x_{1}$
$f_{2}$ = $2x_{0}^{4}+x_{0}^{3}x_{1}-3x_{0}x_{1}^{3}+x_{0}-3x_{1}$ |  $g_{2}$ = $x_{1}^{3}$
1 |  $f_{1}$ = $-2x_{0}^{3}x_{1}+2x_{0}^{2}x_{1}^{5}+x_{0}^{2}x_{1}^{2}-3x_{1}^{7}-3x_{1}^{5}+2x_{1}^{2}$ |  $g_{1}$ = $x_{0}-x_{1}^{4}+3x_{1}$
$f_{2}$ = $3x_{0}^{4}x_{1}^{3}-3x_{0}^{3}x_{1}^{7}+2x_{0}^{3}x_{1}^{4}+x_{0}x_{1}^{9}+x_{0}x_{1}^{7}-3x_{0}x_{1}^{4}+x_{0}-x_{1}^{4}+3x_{1}$ |  $g_{2}$ = $x_{1}^{5}+x_{1}^{3}-3$
$f_{3}$ = $x_{0}^{4}x_{1}^{3}-x_{0}^{3}x_{1}^{7}+3x_{0}^{3}x_{1}^{4}-x_{0}^{2}x_{1}^{2}-2x_{0}x_{1}^{9}-2x_{0}x_{1}^{7}+x_{0}x_{1}^{6}-x_{0}x_{1}^{4}-3x_{0}x_{1}^{3}+x_{0}x_{1}+x_{1}^{3}+3x_{1}^{2}-3$ |
4 |  $f_{1}$ = $-2x_{0}^{3}x_{1}-x_{0}^{2}x_{1}^{5}+3x_{0}^{2}x_{1}^{4}-3x_{0}^{2}x_{1}^{2}-2x_{0}^{2}x_{1}+x_{0}^{2}-3x_{0}x_{1}^{4}+2x_{0}x_{1}^{3}-2x_{0}x_{1}+x_{0}+x_{1}^{5}-3x_{1}^{4}+x_{1}^{3}+2x_{1}+2$ |  $g_{1}$ = $x_{0}-3x_{1}^{4}+2x_{1}^{3}-2x_{1}+1$
$f_{2}$ = $-2x_{0}^{4}x_{1}^{2}-x_{0}^{3}x_{1}^{6}+3x_{0}^{3}x_{1}^{5}-3x_{0}^{3}x_{1}^{4}-3x_{0}^{3}x_{1}^{3}-2x_{0}^{3}x_{1}^{2}+x_{0}^{3}x_{1}+2x_{0}^{2}x_{1}^{8}+x_{0}^{2}x_{1}^{7}-3x_{0}^{2}x_{1}^{5}+3x_{0}^{2}x_{1}^{4}-x_{0}^{2}x_{1}^{3}-2x_{0}^{2}x_{1}^{2}+2x_{0}^{2}-x_{0}x_{1}^{7}-3x_{0}x_{1}^{6}-x_{0}x_{1}^{5}-x_{0}x_{1}^{4}-2x_{0}x_{1}^{3}+x_{0}x_{1}^{2}-x_{0}x_{1}+x_{0}-2x_{1}^{8}-x_{1}^{7}-2x_{1}^{6}-2x_{1}^{3}-2x_{1}+1$ |  $g_{2}$ = $x_{1}^{5}-3x_{1}^{4}+x_{1}^{3}+2x_{1}+2$
$f_{3}$ = $-2x_{0}^{3}x_{1}^{3}+2x_{0}^{3}x_{1}-2x_{0}^{2}x_{1}^{7}-x_{0}^{2}x_{1}^{6}-3x_{0}^{2}x_{1}^{5}+3x_{0}^{2}x_{1}^{4}+3x_{0}^{2}x_{1}^{3}+2x_{0}^{2}x_{1}^{2}-2x_{0}x_{1}^{7}+3x_{0}x_{1}^{6}+3x_{0}x_{1}^{4}+2x_{0}x_{1}^{3}-x_{0}x_{1}^{2}-2x_{0}x_{1}-3x_{0}+x_{1}^{7}-2x_{1}^{5}-x_{1}^{4}+x_{1}^{3}+x_{1}^{2}-3$ |
$f_{4}$ = $-x_{0}^{4}x_{1}^{6}+x_{0}^{4}x_{1}^{5}-2x_{0}^{4}x_{1}^{4}-2x_{0}^{4}x_{1}^{3}-x_{0}^{4}x_{1}^{2}+3x_{0}^{4}+x_{0}^{3}x_{1}^{7}+x_{0}^{3}x_{1}^{6}-x_{0}^{3}x_{1}^{5}-2x_{0}^{3}x_{1}^{4}+3x_{0}^{3}x_{1}^{3}-x_{0}^{3}x_{1}^{2}-x_{0}^{3}x_{1}-2x_{0}^{3}+x_{0}^{2}x_{1}^{6}-x_{0}^{2}x_{1}^{5}-3x_{0}^{2}x_{1}^{4}+x_{0}^{2}x_{1}^{3}-3x_{0}^{2}x_{1}^{2}+x_{0}^{2}x_{1}-2x_{0}^{2}+x_{0}x_{1}^{6}+2x_{0}x_{1}^{5}+x_{0}x_{1}^{4}-3x_{0}x_{1}^{3}+3x_{0}x_{1}^{2}+x_{0}+3x_{1}^{6}-2x_{1}^{5}+2x_{1}^{3}-x_{1}^{2}-3x_{1}+1$ |
5 |  $f_{1}$ = $x_{0}^{2}x_{1}^{2}+2x_{0}x_{1}^{4}+x_{1}^{4}$ |  $g_{1}$ = $x_{0}+2x_{1}^{2}$
$f_{2}$ = $x_{0}^{2}x_{1}^{5}+2x_{0}x_{1}^{7}+x_{0}+x_{1}^{7}+2x_{1}^{2}$ |  $g_{2}$ = $x_{1}^{4}$
13 |  $f_{1}$ = $x_{0}+x_{1}^{2}$ |  $g_{1}$ = $x_{0}+x_{1}^{2}$
$f_{2}$ = $x_{0}x_{1}+3x_{0}+2x_{1}^{3}+3x_{1}^{2}+x_{1}$ |  $g_{2}$ = $x_{1}^{3}+x_{1}$
14 |  $f_{1}$ = $x_{0}x_{1}^{2}+x_{1}^{4}+x_{1}^{3}$ |  $g_{1}$ = $x_{0}+x_{1}$
$f_{2}$ = $-3x_{0}x_{1}^{3}+x_{0}-3x_{1}^{5}-3x_{1}^{4}+x_{1}$ |  $g_{2}$ = $x_{1}^{4}$
15 |  $f_{1}$ = $x_{0}^{2}x_{1}^{4}-2x_{0}^{2}x_{1}^{3}-2x_{0}x_{1}+3x_{1}^{3}-2x_{1}$ |  $g_{1}$ = $x_{0}+2x_{1}^{2}+1$
$f_{2}$ = $x_{0}^{3}x_{1}^{4}-2x_{0}^{3}x_{1}^{3}-2x_{0}^{2}x_{1}+3x_{0}x_{1}^{3}+x_{0}x_{1}^{2}-2x_{0}x_{1}+2x_{1}^{4}+x_{1}^{3}-x_{1}^{2}$ |  $g_{2}$ = $x_{1}^{3}-2x_{1}^{2}$
$f_{3}$ = $3x_{0}^{3}x_{1}^{6}+x_{0}^{3}x_{1}^{5}-x_{0}^{2}x_{1}^{3}-2x_{0}x_{1}^{5}-2x_{0}x_{1}^{4}+3x_{0}x_{1}^{3}-2x_{0}x_{1}-x_{1}^{3}+x_{1}^{2}-2x_{1}$ |
$f_{4}$ = $-3x_{0}^{3}x_{1}^{3}+2x_{0}^{2}x_{1}^{6}-3x_{0}^{2}x_{1}^{5}-3x_{0}^{2}x_{1}^{4}+3x_{0}^{2}x_{1}^{3}+x_{0}^{2}x_{1}^{2}-3x_{0}x_{1}^{4}-x_{0}x_{1}^{3}+x_{0}x_{1}^{2}+x_{0}-x_{1}^{5}+3x_{1}^{3}+2x_{1}^{2}+1$ |
Table 7: Success examples ($n=3$) ID |  $F$ |  $G$
---|---|---
0 |  $f_{1}$ = $x_{1}-2x_{2}$ |  $g_{1}$ = $x_{0}-3x_{2}$
$f_{2}$ = $-3x_{0}x_{1}x_{2}^{2}+2x_{1}x_{2}^{3}+x_{2}^{3}$ |  $g_{2}$ = $x_{1}-2x_{2}$
$f_{3}$ = $x_{0}x_{1}^{2}x_{2}^{3}+x_{0}-3x_{1}^{2}x_{2}^{4}+2x_{1}x_{2}^{4}-3x_{2}$ |  $g_{3}$ = $x_{2}^{3}$
1 |  $f_{1}$ = $x_{2}^{5}+x_{2}^{3}-3$ |  $g_{1}$ = $x_{0}-x_{2}^{4}+3x_{2}$
$f_{2}$ = $-3x_{0}x_{1}x_{2}+2x_{0}x_{2}^{5}-x_{0}x_{2}^{3}-2x_{0}x_{2}^{2}-3x_{1}^{3}x_{2}^{5}-3x_{1}^{3}x_{2}^{3}+2x_{1}^{3}+2x_{1}^{2}x_{2}^{6}+2x_{1}^{2}x_{2}^{4}+x_{1}^{2}x_{2}$ |  $g_{2}$ = $x_{1}-3x_{2}^{4}-2x_{2}^{2}+3x_{2}$
$f_{3}$ = $-2x_{0}^{2}x_{1}x_{2}^{2}-x_{0}^{2}x_{2}^{6}-3x_{0}^{2}x_{2}^{4}+x_{0}^{2}x_{2}^{3}-2x_{0}x_{1}^{3}x_{2}^{6}-2x_{0}x_{1}^{3}x_{2}^{4}-x_{0}x_{1}^{3}x_{2}+x_{0}-x_{2}^{4}+3x_{2}$ |  $g_{3}$ = $x_{2}^{5}+x_{2}^{3}-3$
$f_{4}$ = $x_{1}-3x_{2}^{4}-2x_{2}^{2}+3x_{2}$ |
3 |  $f_{1}$ = $x_{0}-x_{2}^{4}+2x_{2}^{3}+3x_{2}^{2}-2x_{2}$ |  $g_{1}$ = $x_{0}-x_{2}^{4}+2x_{2}^{3}+3x_{2}^{2}-2x_{2}$
$f_{2}$ = $2x_{0}^{2}-2x_{0}x_{1}^{3}-2x_{0}x_{2}^{4}-3x_{0}x_{2}^{3}-x_{0}x_{2}^{2}+3x_{0}x_{2}+2x_{1}^{3}x_{2}^{4}+3x_{1}^{3}x_{2}^{3}+x_{1}^{3}x_{2}^{2}-3x_{1}^{3}x_{2}+x_{1}-2x_{2}^{3}-2x_{2}-1$ |  $g_{2}$ = $x_{1}-2x_{2}^{3}-2x_{2}-1$
$f_{3}$ = $-2x_{0}^{4}+2x_{0}^{3}x_{1}^{3}+2x_{0}^{3}x_{2}^{4}+3x_{0}^{3}x_{2}^{3}+x_{0}^{3}x_{2}^{2}-x_{0}^{3}x_{2}-2x_{0}^{2}x_{1}^{3}x_{2}^{4}-3x_{0}^{2}x_{1}^{3}x_{2}^{3}-x_{0}^{2}x_{1}^{3}x_{2}^{2}+x_{0}^{2}x_{1}^{3}x_{2}+x_{0}^{2}x_{1}x_{2}-x_{0}^{2}x_{1}-2x_{0}^{2}x_{2}^{5}-3x_{0}^{2}x_{2}^{4}+x_{0}^{2}x_{2}^{3}+3x_{0}^{2}x_{2}^{2}+2x_{0}^{2}x_{2}+x_{0}^{2}+2x_{0}x_{1}^{3}x_{2}^{5}+3x_{0}x_{1}^{3}x_{2}^{4}+x_{0}x_{1}^{3}x_{2}^{3}-3x_{0}x_{1}^{3}x_{2}^{2}+2x_{0}x_{1}^{2}-x_{0}x_{1}x_{2}^{5}+2x_{0}x_{1}x_{2}^{4}+3x_{0}x_{1}x_{2}^{3}-2x_{0}x_{1}x_{2}^{2}+x_{0}x_{1}x_{2}+2x_{0}x_{1}-2x_{0}x_{2}^{4}-2x_{0}x_{2}^{2}+3x_{0}x_{2}-2x_{1}^{2}x_{2}^{4}-3x_{1}^{2}x_{2}^{3}-x_{1}^{2}x_{2}^{2}+3x_{1}^{2}x_{2}-x_{1}^{2}-2x_{1}x_{2}^{4}-2x_{1}x_{2}^{3}-x_{1}x_{2}^{2}-2x_{1}x_{2}+x_{1}+2x_{2}^{6}+3x_{2}^{5}+3x_{2}^{4}-x_{2}^{3}-x_{2}^{2}$ |  $g_{3}$ = $x_{2}^{5}-2x_{2}^{4}-x_{2}+3$
$f_{4}$ = $-x_{0}^{3}x_{1}x_{2}-2x_{0}^{3}x_{2}^{2}-3x_{0}^{2}x_{1}^{2}x_{2}+x_{0}^{2}x_{1}x_{2}^{5}+x_{0}^{2}x_{1}x_{2}^{4}-3x_{0}^{2}x_{1}x_{2}^{3}+x_{0}^{2}x_{1}x_{2}^{2}+3x_{0}^{2}x_{1}x_{2}-x_{0}^{2}x_{2}^{7}+2x_{0}^{2}x_{2}^{6}+2x_{0}^{2}x_{2}^{5}-3x_{0}^{2}x_{2}^{4}-3x_{0}^{2}x_{2}^{3}+x_{0}x_{1}^{4}+2x_{0}x_{1}^{3}x_{2}-x_{0}x_{1}^{3}-x_{0}x_{1}+3x_{1}^{5}-x_{1}^{4}x_{2}^{4}-x_{1}^{4}x_{2}^{3}+3x_{1}^{4}x_{2}^{2}-x_{1}^{4}x_{2}-3x_{1}^{4}+x_{1}^{3}x_{2}^{6}-2x_{1}^{3}x_{2}^{5}-x_{1}^{3}x_{2}^{4}+x_{1}^{3}x_{2}^{3}+2x_{1}^{3}x_{2}+x_{1}x_{2}^{4}-2x_{1}x_{2}^{3}-3x_{1}x_{2}^{2}+2x_{1}x_{2}+x_{2}^{5}-2x_{2}^{4}-x_{2}+3$ |
5 |  $f_{1}$ = $x_{1}+2x_{2}$ |  $g_{1}$ = $x_{0}+2x_{2}^{2}$
$f_{2}$ = $2x_{0}^{3}x_{1}-3x_{0}^{2}x_{1}x_{2}^{2}+x_{2}^{4}$ |  $g_{2}$ = $x_{1}+2x_{2}$
$f_{3}$ = $2x_{0}^{3}x_{1}-3x_{0}^{2}x_{1}x_{2}^{2}+3x_{0}^{2}x_{1}-x_{0}^{2}x_{2}+x_{0}+x_{2}^{4}+2x_{2}^{2}$ |  $g_{3}$ = $x_{2}^{4}$
6 |  $f_{1}$ = $0$ |  $g_{1}$ = $x_{0}+x_{2}^{4}-2x_{2}^{3}+3x_{2}^{2}+3x_{2}$
$f_{2}$ = $x_{0}+x_{2}^{4}-2x_{2}^{3}+3x_{2}^{2}+3x_{2}$ |  $g_{2}$ = $x_{1}-3x_{2}^{4}-2x_{2}^{3}+2x_{2}^{2}$
$f_{3}$ = $-x_{0}^{2}x_{1}x_{2}-3x_{0}^{2}-x_{0}x_{1}x_{2}^{5}+2x_{0}x_{1}x_{2}^{4}-3x_{0}x_{1}x_{2}^{3}-3x_{0}x_{1}x_{2}^{2}-3x_{0}x_{2}^{4}-x_{0}x_{2}^{3}-2x_{0}x_{2}^{2}-2x_{0}x_{2}+x_{2}^{5}+2x_{2}^{4}-x_{2}^{3}+2$ |  $g_{3}$ = $x_{2}^{5}+2x_{2}^{4}-x_{2}^{3}+2$
$f_{4}$ = $x_{0}^{3}x_{1}x_{2}^{2}+3x_{0}^{3}x_{2}-x_{0}^{2}x_{1}^{2}x_{2}^{2}+x_{0}^{2}x_{1}x_{2}^{6}-2x_{0}^{2}x_{1}x_{2}^{5}+3x_{0}^{2}x_{1}x_{2}^{4}+3x_{0}^{2}x_{1}x_{2}^{3}-3x_{0}^{2}x_{1}x_{2}+3x_{0}^{2}x_{2}^{5}+x_{0}^{2}x_{2}^{4}+2x_{0}^{2}x_{2}^{3}+2x_{0}^{2}x_{2}^{2}-x_{0}x_{1}^{2}x_{2}^{6}+2x_{0}x_{1}^{2}x_{2}^{5}-3x_{0}x_{1}^{2}x_{2}^{4}-3x_{0}x_{1}^{2}x_{2}^{3}-2x_{0}x_{1}^{2}x_{2}+2x_{0}x_{1}^{2}-3x_{0}x_{1}x_{2}^{5}-x_{0}x_{1}x_{2}^{4}-2x_{0}x_{1}x_{2}^{3}-2x_{0}x_{1}x_{2}^{2}-x_{0}x_{2}^{6}-2x_{0}x_{2}^{5}+x_{0}x_{2}^{4}-2x_{0}x_{2}-2x_{1}^{2}x_{2}^{5}-x_{1}^{2}x_{2}^{4}-3x_{1}^{2}x_{2}^{3}-x_{1}^{2}x_{2}+x_{1}x_{2}^{6}+2x_{1}x_{2}^{5}-x_{1}x_{2}^{4}+2x_{1}x_{2}+x_{1}-3x_{2}^{4}-2x_{2}^{3}+2x_{2}^{2}$ |
Table 8: Success examples ($n=4$) ID |  $F$ |  $G$
---|---|---
0 |  $f_{1}$ = $x_{0}x_{3}^{3}+x_{1}-3x_{3}^{4}-2x_{3}$ |  $g_{1}$ = $x_{0}-3x_{3}$
$f_{2}$ = $-2x_{0}^{2}x_{1}^{2}x_{3}^{3}-2x_{0}x_{1}^{3}-x_{0}x_{1}^{2}x_{3}^{4}-3x_{0}x_{1}^{2}x_{3}+x_{2}$ |  $g_{2}$ = $x_{1}-2x_{3}$
$f_{3}$ = $x_{0}-3x_{3}$ |  $g_{3}$ = $x_{2}$
$f_{4}$ = $3x_{0}x_{1}^{2}x_{2}+2x_{0}x_{1}x_{2}^{2}+3x_{0}x_{2}x_{3}^{2}+x_{1}x_{2}^{2}x_{3}-2x_{2}x_{3}^{3}+x_{3}^{3}$ |  $g_{4}$ = $x_{3}^{3}$
1 |  $f_{1}$ = $-2x_{0}x_{3}^{3}+2x_{3}^{7}+x_{3}^{5}+x_{3}^{4}+x_{3}^{3}-3$ |  $g_{1}$ = $x_{0}-x_{3}^{4}+3x_{3}$
$f_{2}$ = $3x_{0}^{2}x_{1}x_{3}^{4}-3x_{0}x_{1}x_{3}^{8}+2x_{0}x_{1}x_{3}^{6}+2x_{0}x_{1}x_{3}^{5}+2x_{0}x_{1}x_{3}^{4}+x_{0}x_{1}x_{3}+x_{0}-x_{3}^{4}+3x_{3}$ |  $g_{2}$ = $x_{1}-3x_{3}^{4}-2x_{3}^{2}+3x_{3}$
$f_{3}$ = $2x_{0}^{2}x_{2}^{2}+3x_{0}x_{1}^{2}x_{3}-2x_{0}x_{2}^{2}x_{3}^{4}-x_{0}x_{2}^{2}x_{3}-3x_{1}^{2}x_{3}^{5}+2x_{1}^{2}x_{3}^{2}+x_{1}-3x_{3}^{4}-2x_{3}^{2}+3x_{3}$ |  $g_{3}$ = $x_{2}+x_{3}^{4}-2x_{3}^{3}$
$f_{4}$ = $-2x_{0}x_{2}x_{3}^{2}-2x_{0}x_{3}^{6}-3x_{0}x_{3}^{5}$ |  $g_{4}$ = $x_{3}^{5}+x_{3}^{3}-3$
$f_{5}$ = $x_{2}+x_{3}^{4}-2x_{3}^{3}$ |
2 |  $f_{1}$ = $0$ |  $g_{1}$ = $x_{0}-2x_{3}^{4}+x_{3}^{3}+2x_{3}^{2}-3$
$f_{2}$ = $x_{0}-2x_{3}^{4}+x_{3}^{3}+2x_{3}^{2}-3$ |  $g_{2}$ = $x_{1}+2x_{3}^{4}+2x_{3}^{2}-x_{3}-1$
$f_{3}$ = $-x_{0}^{2}x_{1}x_{2}-2x_{0}^{2}x_{2}x_{3}^{4}-2x_{0}^{2}x_{2}x_{3}^{2}+x_{0}^{2}x_{2}x_{3}+x_{0}^{2}x_{2}-2x_{1}x_{2}^{2}+3x_{2}^{2}x_{3}^{4}+3x_{2}^{2}x_{3}^{2}+2x_{2}^{2}x_{3}+2x_{2}^{2}+x_{2}+3x_{3}^{4}+3x_{3}^{3}-2x_{3}^{2}+x_{3}$ |  $g_{3}$ = $x_{2}+3x_{3}^{4}+3x_{3}^{3}-2x_{3}^{2}+x_{3}$
$f_{4}$ = $-3x_{0}^{2}x_{1}^{2}-x_{0}x_{1}^{2}x_{3}^{4}-3x_{0}x_{1}^{2}x_{3}^{3}+x_{0}x_{1}^{2}x_{3}^{2}+2x_{0}x_{1}^{2}-2x_{0}x_{2}^{3}+x_{1}-3x_{2}^{3}x_{3}^{4}-2x_{2}^{3}x_{3}^{3}+3x_{2}^{3}x_{3}^{2}-x_{2}^{3}+2x_{3}^{4}+2x_{3}^{2}-x_{3}-1$ |  $g_{4}$ = $x_{3}^{5}+x_{3}^{4}-1$
$f_{5}$ = $-x_{0}^{2}x_{1}^{3}x_{2}^{2}-2x_{0}^{2}x_{1}^{3}x_{2}+2x_{0}x_{1}^{3}x_{2}^{2}x_{3}^{4}-x_{0}x_{1}^{3}x_{2}^{2}x_{3}^{3}-2x_{0}x_{1}^{3}x_{2}^{2}x_{3}^{2}+3x_{0}x_{1}^{3}x_{2}^{2}-3x_{0}x_{1}^{3}x_{2}x_{3}^{4}-2x_{0}x_{1}^{3}x_{2}x_{3}^{3}+3x_{0}x_{1}^{3}x_{2}x_{3}^{2}-x_{0}x_{1}^{3}x_{2}-x_{0}x_{1}^{3}-3x_{0}x_{1}x_{2}^{5}+x_{0}x_{1}x_{2}^{4}+2x_{0}x_{2}^{2}x_{3}+2x_{1}^{3}x_{3}^{4}-x_{1}^{3}x_{3}^{3}-2x_{1}^{3}x_{3}^{2}+3x_{1}^{3}-2x_{1}^{2}x_{2}^{2}+3x_{1}^{2}x_{2}-x_{1}x_{2}^{5}x_{3}^{4}-3x_{1}x_{2}^{5}x_{3}^{3}+x_{1}x_{2}^{5}x_{3}^{2}+2x_{1}x_{2}^{5}-2x_{1}x_{2}^{4}x_{3}^{4}+x_{1}x_{2}^{4}x_{3}^{3}+2x_{1}x_{2}^{4}x_{3}^{2}-3x_{1}x_{2}^{4}+3x_{1}x_{2}^{2}x_{3}^{4}+3x_{1}x_{2}^{2}x_{3}^{2}+2x_{1}x_{2}^{2}x_{3}+2x_{1}x_{2}^{2}-x_{1}x_{2}x_{3}^{4}-x_{1}x_{2}x_{3}^{2}-3x_{1}x_{2}x_{3}-3x_{1}x_{2}+3x_{2}^{2}x_{3}^{5}+2x_{2}^{2}x_{3}^{4}-3x_{2}^{2}x_{3}^{3}+x_{2}^{2}x_{3}-x_{2}-3x_{3}^{4}-3x_{3}^{3}+2x_{3}^{2}-x_{3}$ |
$f_{6}$ = $x_{3}^{5}+x_{3}^{4}-1$ |
3 |  $f_{1}$ = $0$ |  $g_{1}$ = $x_{0}-x_{3}^{4}+2x_{3}^{3}+3x_{3}^{2}-2x_{3}$
$f_{2}$ = $x_{2}-2x_{3}^{3}-2x_{3}+1$ |  $g_{2}$ = $x_{1}-2x_{3}^{3}-2x_{3}-1$
$f_{3}$ = $x_{0}-x_{3}^{4}+2x_{3}^{3}+3x_{3}^{2}-2x_{3}$ |  $g_{3}$ = $x_{2}-2x_{3}^{3}-2x_{3}+1$
$f_{4}$ = $-2x_{0}^{2}x_{1}^{2}-3x_{0}^{2}-x_{0}x_{1}^{2}x_{2}+2x_{0}x_{1}^{2}x_{3}^{4}-2x_{0}x_{1}^{2}x_{3}^{3}+x_{0}x_{1}^{2}x_{3}^{2}-x_{0}x_{1}^{2}x_{3}-x_{0}x_{1}^{2}-3x_{0}x_{1}-x_{0}x_{2}^{2}x_{3}+2x_{0}x_{2}x_{3}^{4}+2x_{0}x_{2}x_{3}^{2}-x_{0}x_{2}x_{3}+3x_{0}x_{3}^{4}+x_{0}x_{3}^{3}-2x_{0}x_{3}^{2}-x_{0}x_{3}+3x_{1}x_{3}^{4}+x_{1}x_{3}^{3}-2x_{1}x_{3}^{2}-x_{1}x_{3}+x_{3}^{5}-2x_{3}^{4}-x_{3}+3$ |  $g_{4}$ = $x_{3}^{5}-2x_{3}^{4}-x_{3}+3$
$f_{5}$ = $x_{1}-2x_{3}^{3}-2x_{3}-1$ |
5 |  $f_{1}$ = $x_{0}+2x_{3}^{2}$ |  $g_{1}$ = $x_{0}+2x_{3}^{2}$
$f_{2}$ = $-x_{0}x_{2}x_{3}^{2}-2x_{2}x_{3}^{4}+x_{2}+x_{3}^{2}$ |  $g_{2}$ = $x_{1}+2x_{3}$
$f_{3}$ = $-3x_{1}x_{2}^{2}x_{3}-3x_{1}x_{2}x_{3}^{3}+x_{3}^{4}$ |  $g_{3}$ = $x_{2}+x_{3}^{2}$
$f_{4}$ = $2x_{0}^{3}x_{1}x_{2}x_{3}^{2}-3x_{0}^{2}x_{1}x_{2}x_{3}^{4}-2x_{0}^{2}x_{1}x_{2}-2x_{0}^{2}x_{1}x_{3}^{2}-3x_{0}x_{1}^{3}x_{2}^{2}x_{3}-3x_{0}x_{1}^{3}x_{2}x_{3}^{3}+x_{0}x_{1}^{2}x_{3}^{4}+x_{1}+2x_{3}$ |  $g_{4}$ = $x_{3}^{4}$
Table 9: Success examples ($n=5$) ID |  $F$ |  $G$
---|---|---
0 |  $f_{1}$ = $x_{0}-3x_{4}$ |  $g_{1}$ = $x_{0}-3x_{4}$
$f_{2}$ = $x_{3}$ |  $g_{2}$ = $x_{1}-2x_{4}$
$f_{3}$ = $x_{1}-2x_{4}$ |  $g_{3}$ = $x_{2}$
$f_{4}$ = $x_{0}^{3}x_{1}-3x_{0}^{2}x_{1}x_{4}-3x_{1}x_{2}^{2}-x_{2}^{2}x_{4}+x_{4}^{3}$ |  $g_{4}$ = $x_{3}$
$f_{5}$ = $2x_{0}^{3}x_{1}^{3}x_{2}+x_{0}^{2}x_{1}^{3}x_{2}x_{4}+x_{1}^{3}x_{2}^{3}-2x_{1}^{2}x_{2}^{3}x_{4}+2x_{1}^{2}x_{2}x_{4}^{3}-2x_{1}x_{2}x_{3}x_{4}+x_{2}$ |  $g_{5}$ = $x_{4}^{3}$
1 |  $f_{1}$ = $x_{0}-x_{4}^{4}+3x_{4}$ |  $g_{1}$ = $x_{0}-x_{4}^{4}+3x_{4}$
$f_{2}$ = $2x_{0}^{2}x_{2}-2x_{0}x_{2}x_{4}^{4}-x_{0}x_{2}x_{4}$ |  $g_{2}$ = $x_{1}-3x_{4}^{4}-2x_{4}^{2}+3x_{4}$
$f_{3}$ = $-2x_{0}^{2}x_{2}x_{4}-2x_{0}^{2}x_{4}^{5}-3x_{0}^{2}x_{4}^{4}-2x_{0}x_{1}x_{4}+2x_{1}x_{4}^{5}+x_{1}x_{4}^{2}+x_{4}^{5}+x_{4}^{3}-3$ |  $g_{3}$ = $x_{2}+x_{4}^{4}-2x_{4}^{3}$
$f_{4}$ = $x_{1}-3x_{4}^{4}-2x_{4}^{2}+3x_{4}$ |  $g_{4}$ = $x_{3}+2x_{4}^{4}-3$
$f_{5}$ = $x_{3}+2x_{4}^{4}-3$ |  $g_{5}$ = $x_{4}^{5}+x_{4}^{3}-3$
$f_{6}$ = $x_{2}+x_{4}^{4}-2x_{4}^{3}$ |
3 |  $f_{1}$ = $x_{1}x_{2}^{2}x_{4}-2x_{1}x_{2}x_{4}^{4}-2x_{1}x_{2}x_{4}^{2}+x_{1}x_{2}x_{4}-x_{2}^{2}x_{3}x_{4}+2x_{2}x_{3}x_{4}^{4}+2x_{2}x_{3}x_{4}^{2}-x_{2}x_{3}x_{4}+x_{4}^{5}-2x_{4}^{4}-x_{4}+3$ |  $g_{1}$ = $x_{0}-x_{4}^{4}+2x_{4}^{3}+3x_{4}^{2}-2x_{4}$
$f_{2}$ = $x_{1}-2x_{4}^{3}-2x_{4}-1$ |  $g_{2}$ = $x_{1}-2x_{4}^{3}-2x_{4}-1$
$f_{3}$ = $x_{3}+2x_{4}^{4}-3x_{4}^{3}-x_{4}-1$ |  $g_{3}$ = $x_{2}-2x_{4}^{3}-2x_{4}+1$
$f_{4}$ = $-3x_{1}^{2}x_{2}^{2}x_{3}^{2}x_{4}-x_{1}^{2}x_{2}x_{3}^{2}x_{4}^{4}-x_{1}^{2}x_{2}x_{3}^{2}x_{4}^{2}-3x_{1}^{2}x_{2}x_{3}^{2}x_{4}-2x_{1}x_{2}^{2}x_{3}^{3}x_{4}-3x_{1}x_{2}x_{3}^{3}x_{4}^{4}-3x_{1}x_{2}x_{3}^{3}x_{4}^{2}-2x_{1}x_{2}x_{3}^{3}x_{4}-3x_{1}x_{3}^{2}x_{4}^{5}-x_{1}x_{3}^{2}x_{4}^{4}+3x_{1}x_{3}^{2}x_{4}-2x_{1}x_{3}^{2}-2x_{2}^{2}x_{3}^{4}x_{4}-3x_{2}x_{3}^{4}x_{4}^{4}-3x_{2}x_{3}^{4}x_{4}^{2}-2x_{2}x_{3}^{4}x_{4}+x_{2}+2x_{3}^{3}x_{4}^{5}+3x_{3}^{3}x_{4}^{4}-2x_{3}^{3}x_{4}-x_{3}^{3}-2x_{4}^{3}-2x_{4}+1$ |  $g_{4}$ = $x_{3}+2x_{4}^{4}-3x_{4}^{3}-x_{4}-1$
$f_{5}$ = $-x_{0}x_{1}^{2}x_{4}-x_{0}x_{1}x_{2}-3x_{0}x_{2}x_{3}x_{4}+x_{0}x_{2}x_{4}^{5}+2x_{0}x_{2}x_{4}^{4}+3x_{0}x_{2}x_{4}^{2}+3x_{0}x_{2}x_{4}+x_{1}^{2}x_{4}^{5}-2x_{1}^{2}x_{4}^{4}-3x_{1}^{2}x_{4}^{3}+2x_{1}^{2}x_{4}^{2}+2x_{1}x_{2}x_{3}x_{4}-3x_{1}x_{2}x_{4}^{5}+2x_{1}x_{2}x_{4}^{4}-2x_{1}x_{2}x_{4}^{3}+2x_{1}x_{2}x_{4}^{2}+3x_{2}^{4}+x_{2}^{3}x_{4}^{3}+x_{2}^{3}x_{4}+3x_{2}^{3}+2x_{2}^{2}+3x_{2}x_{4}^{3}+3x_{2}x_{4}+2x_{2}$ |  $g_{5}$ = $x_{4}^{5}-2x_{4}^{4}-x_{4}+3$
$f_{6}$ = $x_{0}-x_{4}^{4}+2x_{4}^{3}+3x_{4}^{2}-2x_{4}$ |
5 |  $f_{1}$ = $x_{1}+2x_{4}$ |  $g_{1}$ = $x_{0}+2x_{4}^{2}$
$f_{2}$ = $x_{0}+2x_{4}^{2}$ |  $g_{2}$ = $x_{1}+2x_{4}$
$f_{3}$ = $2x_{0}^{2}x_{1}-3x_{0}^{2}x_{4}+x_{4}^{4}$ |  $g_{3}$ = $x_{2}+x_{4}^{2}$
$f_{4}$ = $x_{3}-3x_{4}$ |  $g_{4}$ = $x_{3}-3x_{4}$
$f_{5}$ = $2x_{0}^{3}x_{1}^{2}x_{2}-3x_{0}^{3}x_{1}x_{2}x_{4}+x_{0}x_{1}x_{2}x_{4}^{4}+x_{2}-2x_{3}x_{4}^{3}-x_{4}^{4}+x_{4}^{2}$ |  $g_{5}$ = $x_{4}^{4}$
7 |  $f_{1}$ = $0$ |  $g_{1}$ = $x_{0}-x_{4}^{4}-3x_{4}^{3}-3x_{4}^{2}-x_{4}+2$
$f_{2}$ = $x_{3}+3x_{4}^{4}+2x_{4}^{3}-3x_{4}^{2}+3x_{4}+1$ |  $g_{2}$ = $x_{1}+2x_{4}^{4}+2x_{4}^{2}-3x_{4}+1$
$f_{3}$ = $x_{2}+x_{4}^{4}+3x_{4}^{3}-x_{4}^{2}-x_{4}$ |  $g_{3}$ = $x_{2}+x_{4}^{4}+3x_{4}^{3}-x_{4}^{2}-x_{4}$
$f_{4}$ = $-x_{0}x_{2}x_{3}^{2}-x_{0}x_{2}x_{4}^{2}-x_{0}x_{3}^{2}x_{4}^{4}-3x_{0}x_{3}^{2}x_{4}^{3}+x_{0}x_{3}^{2}x_{4}^{2}+x_{0}x_{3}^{2}x_{4}-x_{0}x_{4}^{6}-3x_{0}x_{4}^{5}+x_{0}x_{4}^{4}+x_{0}x_{4}^{3}+x_{1}+2x_{4}^{4}+2x_{4}^{2}-3x_{4}+1$ |  $g_{4}$ = $x_{3}+3x_{4}^{4}+2x_{4}^{3}-3x_{4}^{2}+3x_{4}+1$
$f_{5}$ = $x_{0}-x_{4}^{4}-3x_{4}^{3}-3x_{4}^{2}-x_{4}+2$ |  $g_{5}$ = $x_{4}^{5}-2x_{4}^{4}-x_{4}^{3}-3x_{4}+2$
$f_{6}$ = $-2x_{0}x_{3}^{2}+x_{0}x_{3}x_{4}^{4}+3x_{0}x_{3}x_{4}^{3}-x_{0}x_{3}x_{4}^{2}+x_{0}x_{3}x_{4}-2x_{0}x_{3}+2x_{2}^{2}+2x_{2}x_{4}^{4}-x_{2}x_{4}^{3}-2x_{2}x_{4}^{2}-2x_{2}x_{4}+x_{4}^{5}-2x_{4}^{4}-x_{4}^{3}-3x_{4}+2$ |
$f_{7}$ = $2x_{0}^{2}x_{2}x_{3}-3x_{0}x_{1}x_{2}^{2}+x_{0}x_{2}^{2}x_{4}^{4}+x_{0}x_{2}^{2}x_{4}^{2}+2x_{0}x_{2}^{2}x_{4}-x_{0}x_{2}^{2}-2x_{0}x_{2}x_{3}x_{4}^{4}+x_{0}x_{2}x_{3}x_{4}^{3}+x_{0}x_{2}x_{3}x_{4}^{2}-2x_{0}x_{2}x_{3}x_{4}-3x_{0}x_{2}x_{3}-2x_{1}-2x_{2}^{2}x_{4}^{4}+x_{2}^{2}x_{4}^{3}+x_{2}^{2}x_{4}^{2}-2x_{2}^{2}x_{4}-3x_{2}^{2}+3x_{4}^{4}+3x_{4}^{2}-x_{4}-2$ |
Table 10: Failure examples (ground truth v.s. prediction) ID |  $G$ (Ground Truth) |  $G^{\prime}$ (Transformer)
---|---|---
2 |  $g_{1}=x_{0}-2x_{1}^{4}+x_{1}^{3}+2x_{1}^{2}-3$ |  $g^{\prime}_{1}=x_{0}-2x_{1}^{4}+x_{1}^{3}+2x_{1}^{2}-3$
$g_{2}=x_{1}^{5}+x_{1}^{4}-1$ |  $g^{\prime}_{2}=x_{1}^{5}+x_{1}^{4}+x_{1}^{3}-3x_{1}^{2}-3$
3 |  $g_{1}=x_{0}-x_{1}^{4}+2x_{1}^{3}+3x_{1}^{2}-2x_{1}$ |  $g^{\prime}_{1}=x_{0}-x_{1}^{4}+2x_{1}^{3}+3x_{1}^{2}-2x_{1}$
$g_{2}=x_{1}^{5}-2x_{1}^{4}-x_{1}+3$ |  $g^{\prime}_{2}=x_{1}^{5}-2x_{1}^{4}+3$
6 |  $g_{1}=x_{0}+x_{1}^{4}-2x_{1}^{3}+3x_{1}^{2}+3x_{1}$ |  $g^{\prime}_{1}=x_{0}+x_{1}^{4}-2x_{1}^{3}+3x_{1}^{2}+3x_{1}$
$g_{2}=x_{1}^{5}+2x_{1}^{4}-x_{1}^{3}+2$ |  $g^{\prime}_{2}=x_{1}^{5}-2x_{1}^{4}-2x_{1}^{3}+2$
7 |  $g_{1}=x_{0}-x_{1}^{4}-3x_{1}^{3}-3x_{1}^{2}-x_{1}+2$ |  $g^{\prime}_{1}=x_{0}+2x_{1}^{4}-3x_{1}^{3}+3x_{1}^{2}-x_{1}+2$
$g_{2}=x_{1}^{5}-2x_{1}^{4}-x_{1}^{3}-3x_{1}+2$ |  $g^{\prime}_{2}=x_{1}^{5}-2x_{1}^{4}-3x_{1}+2$
2 |  $g_{1}=x_{0}-2x_{2}^{4}+x_{2}^{3}+2x_{2}^{2}-3$ |  $g^{\prime}_{1}=x_{0}-2x_{2}^{4}+x_{2}^{3}+2x_{2}^{2}-3$
$g_{2}=x_{1}+2x_{2}^{4}+2x_{2}^{2}-x_{2}-1$ |  $g^{\prime}_{2}=x_{1}-3x_{2}^{4}+2x_{2}^{2}+3x_{2}-1$
$g_{3}=x_{2}^{5}+x_{2}^{4}-1$ |  $g^{\prime}_{3}=x_{2}^{5}-x_{2}^{4}+2x_{2}^{3}-2x_{2}^{2}+3$
4 |  $g_{1}=x_{0}-3x_{2}^{4}+2x_{2}^{3}-2x_{2}+1$ |  $g^{\prime}_{1}=x_{0}-3x_{2}^{4}+2x_{2}^{3}-2x_{2}+1$
$g_{2}=x_{1}+x_{2}^{3}+x_{2}+1$ |  $g^{\prime}_{2}=x_{1}+2x_{2}^{3}+2x_{2}+3$
$g_{3}=x_{2}^{5}-3x_{2}^{4}+x_{2}^{3}+2x_{2}+2$ |  $g^{\prime}_{3}=x_{2}^{5}+2x_{2}^{4}+2x_{2}+3$
7 |  $g_{1}=x_{0}-x_{2}^{4}-3x_{2}^{3}-3x_{2}^{2}-x_{2}+2$ |  $g^{\prime}_{1}=x_{0}-3x_{2}^{4}+3x_{2}^{3}-3x_{2}^{2}+3x_{2}+3$
$g_{2}=x_{1}+2x_{2}^{4}+2x_{2}^{2}-3x_{2}+1$ |  $g^{\prime}_{2}=x_{1}+2x_{2}^{4}+2x_{2}^{2}-3x_{2}+1$
$g_{3}=x_{2}^{5}-2x_{2}^{4}-x_{2}^{3}-3x_{2}+2$ |  $g^{\prime}_{3}=x_{2}^{5}-2x_{2}^{4}-x_{2}^{3}-3x_{2}+2$
9 |  $g_{1}=x_{0}+2x_{2}^{4}+3x_{2}^{3}-2x_{2}^{2}+x_{2}-1$ |  $g^{\prime}_{1}=x_{0}+2x_{2}^{4}+3x_{2}^{3}-2x_{2}^{2}+x_{2}-1$
$g_{2}=x_{1}-3x_{2}^{4}-x_{2}^{3}-2x_{2}^{2}-2x_{2}-3$ |  $g^{\prime}_{2}=x_{1}-3x_{2}^{4}-x_{2}^{3}-2x_{2}^{2}-2x_{2}-3$
$g_{3}=x_{2}^{5}-2x_{2}^{3}-3x_{2}^{2}+2x_{2}+2$ |  $g^{\prime}_{3}=x_{2}^{5}-2x_{2}^{3}-x_{2}^{2}+2x_{2}+2$
4 |  $g_{1}=x_{0}-3x_{3}^{4}+2x_{3}^{3}-2x_{3}+1$ |  $g^{\prime}_{1}=x_{0}-3x_{3}^{4}-3x_{3}^{2}-3x_{3}+1$
$g_{2}=x_{1}+x_{3}^{3}+x_{3}+1$ |  $g^{\prime}_{2}=x_{1}+x_{3}^{3}+x_{3}+1$
$g_{3}=x_{2}+3x_{3}^{4}-3x_{3}^{3}-2x_{3}^{2}-2x_{3}+3$ |  $g^{\prime}_{3}=x_{2}+3x_{3}^{4}-3x_{3}^{3}-2x_{3}^{2}-2x_{3}+3$
$g_{4}=x_{3}^{5}-3x_{3}^{4}+x_{3}^{3}+2x_{3}+2$ |  $g^{\prime}_{4}=x_{3}^{5}-3x_{3}^{4}-3x_{3}^{3}-3x_{3}^{2}+1$
7 |  $g_{1}=x_{0}-x_{3}^{4}-3x_{3}^{3}-3x_{3}^{2}-x_{3}+2$ |  $g^{\prime}_{1}=x_{0}-x_{3}^{4}-3x_{3}^{3}-3x_{3}^{2}-x_{3}+2$
$g_{2}=x_{1}+2x_{3}^{4}+2x_{3}^{2}-3x_{3}+1$ |  $g^{\prime}_{2}=x_{1}+2x_{3}^{4}+2x_{3}^{2}-3x_{3}+1$
$g_{3}=x_{2}+x_{3}^{4}+3x_{3}^{3}-x_{3}^{2}-x_{3}$ |  $g^{\prime}_{3}=x_{2}+x_{3}^{4}+3x_{3}^{3}-x_{3}^{2}-x_{3}$
$g_{4}=x_{3}^{5}-2x_{3}^{4}-x_{3}^{3}-3x_{3}+2$ |  $g^{\prime}_{4}=x_{3}^{5}-3x_{3}^{4}-3x_{3}^{3}-3x_{3}^{2}-3$
9 |  $g_{1}=x_{0}+2x_{3}^{4}+3x_{3}^{3}-2x_{3}^{2}+x_{3}-1$ |  $g^{\prime}_{1}=x_{0}+2x_{3}^{4}+3x_{3}^{3}-2x_{3}^{2}+x_{3}-1$
$g_{2}=x_{1}-3x_{3}^{4}-x_{3}^{3}-2x_{3}^{2}-2x_{3}-3$ |  $g^{\prime}_{2}=x_{1}-3x_{3}^{4}-x_{3}^{3}-2x_{3}^{2}-2x_{3}-3$
$g_{3}=x_{2}-3x_{3}^{4}-2x_{3}^{3}-3x_{3}^{2}+x_{3}-2$ |  $g^{\prime}_{3}=x_{2}-3x_{3}^{4}-2x_{3}^{3}-3x_{3}^{2}+x_{3}-2$
$g_{4}=x_{3}^{5}-2x_{3}^{3}-3x_{3}^{2}+2x_{3}+2$ |
10 |  $g_{1}=x_{0}+3x_{3}^{3}+x_{3}^{2}+3x_{3}$ |  $g^{\prime}_{1}=x_{0}-3x_{3}^{3}-3x_{3}^{2}+3x_{3}$
$g_{2}=x_{1}-2x_{3}^{3}-x_{3}^{2}+3x_{3}+1$ |  $g^{\prime}_{2}=x_{1}-2x_{3}^{3}-x_{3}^{2}+3x_{3}+1$
$g_{3}=x_{2}-2x_{3}^{2}+3x_{3}+1$ |  $g^{\prime}_{3}=x_{2}-2x_{3}^{2}+3x_{3}+1$
$g_{4}=x_{3}^{4}+3x_{3}^{3}+2x_{3}+3$ |  $g^{\prime}_{4}=x_{3}^{4}+3x_{3}^{3}+2x_{3}+3$
2 |  $g_{1}=x_{0}-2x_{4}^{4}+x_{4}^{3}+2x_{4}^{2}-3$ |  $g^{\prime}_{1}=x_{0}-2x_{4}^{4}+x_{4}^{3}+2x_{4}^{2}-3$
$g_{2}=x_{1}+2x_{4}^{4}+2x_{4}^{2}-x_{4}-1$ |  $g^{\prime}_{2}=x_{1}+2x_{4}^{4}+2x_{4}^{2}-x_{4}-1$
$g_{3}=x_{2}+3x_{4}^{4}+3x_{4}^{3}-2x_{4}^{2}+x_{4}$ |  $g^{\prime}_{3}=x_{2}+3x_{4}^{4}+3x_{4}^{3}-2x_{4}^{2}+x_{4}$
$g_{4}=x_{3}-x_{4}^{3}-3x_{4}^{2}$ |  $g^{\prime}_{4}=x_{3}-x_{4}^{4}-x_{4}^{3}-3x_{4}^{2}$
$g_{5}=x_{4}^{5}+x_{4}^{4}-1$ |  $g^{\prime}_{5}=x_{4}^{5}+x_{4}^{4}-1$
4 |  $g_{1}=x_{0}-3x_{4}^{4}+2x_{4}^{3}-2x_{4}+1$ |  $g^{\prime}_{1}=x_{0}-3x_{4}^{4}+2x_{4}^{3}-2x_{4}+1$
$g_{2}=x_{1}+x_{4}^{3}+x_{4}+1$ |  $g^{\prime}_{2}=x_{1}-3x_{4}^{4}-3x_{4}^{3}-2x_{4}^{2}+x_{4}+1$
$g_{3}=x_{2}+3x_{4}^{4}-3x_{4}^{3}-2x_{4}^{2}-2x_{4}+3$ |  $g^{\prime}_{3}=x_{2}-3x_{4}^{4}-3x_{4}^{3}-2x_{4}^{2}-2x_{4}+3$
$g_{4}=x_{3}+x_{4}^{4}+x_{4}^{3}-2x_{4}^{2}-2x_{4}-3$ |  $g^{\prime}_{4}=x_{3}+x_{4}^{4}+x_{4}^{3}-2x_{4}^{2}-2x_{4}-3$
$g_{5}=x_{4}^{5}-3x_{4}^{4}+x_{4}^{3}+2x_{4}+2$ |  $g^{\prime}_{5}=x_{4}^{5}-3x_{4}^{4}+x_{4}^{3}+2x_{4}+2$
6 |  $g_{1}=x_{0}+x_{4}^{4}-2x_{4}^{3}+3x_{4}^{2}+3x_{4}$ |  $g^{\prime}_{1}=x_{0}+x_{4}^{4}-2x_{4}^{3}+3x_{4}^{2}+3x_{4}$
$g_{2}=x_{1}-3x_{4}^{4}-2x_{4}^{3}+2x_{4}^{2}$ |  $g^{\prime}_{2}=x_{1}-3x_{4}^{4}+2x_{4}^{3}+2x_{4}^{2}$
$g_{3}=x_{2}-x_{4}^{4}+2x_{4}^{3}-3x_{4}^{2}$ |  $g^{\prime}_{3}=x_{2}-x_{4}^{4}+2x_{4}^{3}-3x_{4}^{2}$
$g_{4}=x_{3}-3x_{4}^{4}-3x_{4}^{2}-3x_{4}$ |  $g^{\prime}_{4}=x_{3}-3x_{4}^{4}-3x_{4}^{2}-3x_{4}$
$g_{5}=x_{4}^{5}+2x_{4}^{4}-x_{4}^{3}+2$ |  $g^{\prime}_{5}=x_{4}^{5}+2x_{4}^{4}-x_{4}^{3}+2$