11institutetext: Momonari Kudo 22institutetext: Fukuoka Institute of
Technology, 3-30-1 Wajiro-higashi, Higashi-ku, Fukuoka, 811-0295 Japan
22email<EMAIL_ADDRESS>33institutetext: Kazuhiro Yokoyama 44institutetext:
Rikkyo University, 3-34-1 Nishi-Ikebukuro, Toshima-ku, Tokyo, 171-8501 Japan
44email<EMAIL_ADDRESS>
# On Hilbert-Poincaré series of affine semi-regular polynomial sequences and
related Gröbner bases

Momonari Kudo and
Kazuhiro Yokoyama

###### Abstract

Gröbner bases are nowadays central tools for solving various problems in
commutative algebra and algebraic geometry. A typical use of Gröbner bases is
the multivariate polynomial system solving, which enables us to construct
algebraic attacks against post-quantum cryptographic protocols. Therefore, the
determination of the complexity of computing Gröbner bases is very important
both in theory and in practice: One of the most important cases is the case
where input polynomials compose an (overdetermined) affine semi-regular
sequence. The first part of this paper aims to present a survey on the Gröbner
basis computation and its complexity. In the second part, we shall give an
explicit formula on the (truncated) Hilbert-Poincaré series associated to the
homogenization of an affine semi-regular sequence. Based on the formula, we
also study (reduced) Gröbner bases of the ideals generated by an affine semi-
regular sequence and its homogenization. Some of our results are considered to
give mathematically rigorous proofs of the correctness of methods for
computing Gröbner bases of the ideal generated by an affine semi-regular
sequence.

##  1 Introduction

Let $K$ be a field, and $R=K[x_{1},\ldots,x_{n}]$ the polynomial ring in $n$
variables over $K$. For a polynomial $f$ in $R$, let $f^{\rm top}$ denote its
maximal total-degree part  which is called the top part here, and let $f^{h}$
denote its homogenization in $R^{\prime}=R[y]$ by an extra variable $y$,  see
Subsection 3.1 below for details.  We denote by $\langle F\rangle_{R}$ (or
$\langle F\rangle$ simply) the ideal generated by a non-empty subset $F$ of
$R$. For a finitely generated graded $R$-(or $R^{\prime}$-)module $M$, we also
denote by ${\rm HF}_{M}$ and ${\rm HS}_{M}$ its Hilbert function and its
Hilbert–Poincaré series, respectively. A Gröbner basis of an ideal $I$ in $R$
is defined as a special kind of generator set for $I$, and it gives a
computational tool to determine many properties of the ideal. A typical
application of computing Gröbner bases is solving the multivariate polynomial
(MP) problem: Given $m$ polynomials $f_{1},\ldots,f_{m}$ in $R$, find
$(a_{1},\ldots,a_{n})\in K^{n}$ such that $f_{i}(a_{1},\ldots,a_{n})=0$ for
all $i$ with $1\leq i\leq m$. A particular case where polynomials are all
quadratic is called the MQ problem, and its hardness is applied to
constructing public-key cryptosystems and digital signature schemes that are
expected to be quantum resistant. Therefore, analyzing the complexity of
computing Gröbner bases is one of the most important problems both in theory
and in practice.

An algorithm for computing Gröbner bases was proposed first by Buchberger
Buchberger , and so far a number of its improvements such as the $F_{4}$ F4
and $F_{5}$ F5  algorithms have been proposed, see Subsection 3.1 below for a
summary. In general, it is very difficult to determine the complexity of
computing Gröbner bases, but in some cases, we can estimate it with several
algebraic invariants such as the solving degree, the degree of regularity, the
Castelnuovo–Mumford regularity, and the first and last fall degrees; we refer
to CG23  for the relations between these invariants.

The first part of this paper aims to survey the Gröbner basis computation, and
to review its complexity in the case where input polynomials generate a zero-
dimensional ideal. For this, in Section 2, we first recall foundations in
commutative algebra such as Koszul complex, Hilbert-Poincaré series, and semi-
regular sequence, which are useful ingredients to estimate the complexity of
computing Gröbner bases. Then, we overview existing Gröbner basis algorithms
in Subsection 3.1. Subsequently, it will be described in Subsection 3.2 how to
estimate the complexity of computing the reduced Gröbner basis of a zero-
dimensional ideal, with the notion of homogenization.

In the second part, we focus on affine semi-regular polynomial sequences,
where a sequence $F=(f_{1},\ldots,f_{m})\in R^{m}$ of (not necessarily
homogeneous) polynomials is said to be affine (cryptographic) semi-regular if
$F^{\rm top}=(f_{1}^{\rm top},\ldots,f_{m}^{\rm top})$ is (cryptographic)
semi-regular, see Definitions 4, 7, and 8 for details. Note that homogeneous
semi-regular sequences are conjectured by Pardue (Pardue, , Conjecture B) to
be generic sequences of polynomials, and affine (cryptographic) semi-regular
sequences are often appearing in the construction of multivariate public key
cryptosystems and digital signature schemes. In Section 4 below, we relate the
Hilbert-Poincaré series of $R^{\prime}/\langle F^{h}\rangle$ with that of
$R/\langle F^{\rm top}\rangle$. As a corollary, we obtain an explicit formula
of the truncation at degree $D-1$ of the Hilbert-Poincaré series of
$R^{\prime}/\langle F^{h}\rangle$, where $D$ is the degree of regularity for
$\langle F^{\rm top}\rangle$. The following theorem summarizes these results:

######  Theorem 1.1 (Theorem 4.1, Corollaries 1 and 2)

With notation as above, assume that $F$ is affine cryptographic semi-regular.
Then ${\rm HF}_{R^{\prime}/\langle F^{h}\rangle}(d)=\sum_{i=0}^{d}{\rm
HF}_{R/\langle F^{\rm top}\rangle}(i)$ and $(\langle\mathrm{LM}(\langle
F^{h}\rangle)\rangle_{R^{\prime}})_{d}=(\langle\mathrm{LM}(\langle F^{\rm
top}\rangle)\rangle_{R^{\prime}})_{d}$ for each $d$ with $d<D$. Hence, we also
obtain ${\rm HS}_{R^{\prime}/\langle
F^{h}\rangle}(z)\equiv\prod_{i=1}^{m}(1-z^{d_{i}})/(1-z)^{n+1}\pmod{z^{D}}$,
so that $F^{h}$ is $D$-regular (see Definition 4 for the definition of the
$d$-regularity).

As an application of this theorem, we explore reduced Gröbner bases of
$\langle F\rangle$, $\langle F^{h}\rangle$, and $\langle F^{\rm top}\rangle$
in Section 5 below, dividing the cases into the degree less than $D$ or not.
In particular, we rigorously prove some existing results, which are often used
for analyzing the complexity of computing Gröbner bases, and moreover extend
them.

##  2 Preliminaries

In this section, we recall definitions of Koszul complex, Hilbert–Poincaré
series, and semi-regular polynomial sequences, and collect some known facts
related to them. Throughout this section, let $R=K[X]=K[x_{1},\ldots,x_{n}]$
be the polynomial ring of $n$ variables $X=(x_{1},\ldots,x_{n})$ over a field
$K$. As a notion, for a polynomial $f$ in $R$, we denote its total degree by
$\deg(f)$. As $R$ is a graded ring with respect to total degree, for a
polynomial $f$, its maximal total degree part, denoted by $f^{\rm top}$, is
defined as its graded component of $\deg(f)$, that is, the sum of all terms of
$f$ whose total degree equals to $\deg(f)$.

###  2.1 Koszul complex and its homology

Let $f_{1},\ldots,f_{m}\in R$ be homogeneous polynomials of degrees
$d_{1},\ldots,d_{m}$, and put $d_{j_{1}\cdots
j_{i}}:=\sum_{k=1}^{i}d_{j_{k}}$. For each $0\leq i\leq m$, we define a free
$R$-module  of rank $\binom{m}{i}$

$K_{i}(f_{1},\ldots,f_{m}):=\left\\{\begin{array}[]{cl}\displaystyle\bigoplus_{1\leq
j_{1}<\cdots<j_{i}\leq m}R({-d_{j_{1}\cdots j_{i}}})\mathbf{e}_{j_{1}\cdots
j_{i}}&(i\geq 1)\\\ R&(i=0),\end{array}\right.$

where $\mathbf{e}_{j_{1}\cdots j_{i}}$ is a standard basis.  We also define a
graded homomorphism

$\varphi_{i}:K_{i}(f_{1},\ldots,f_{m})\longrightarrow
K_{i-1}(f_{1},\ldots,f_{m})$ (1)

of degree $0$ by

$\varphi_{i}(\mathbf{e}_{j_{1}\cdots
j_{i}}):=\sum_{k=1}^{i}(-1)^{k-1}f_{j_{k}}\mathbf{e}_{j_{1}\cdots\hat{j_{k}}\cdots
j_{i}}.$ (2)

Here, $\hat{j_{k}}$ means to omit $j_{k}$.  For example, we have
$\mathbf{e}_{1\hat{2}3}=\mathbf{e}_{13}$. To simplify the notation, we set
$K_{i}:=K_{i}(f_{1},\ldots,f_{m})$. Then,

$K_{\bullet}:0\to
K_{m}\xrightarrow{\varphi_{m}}\cdots\xrightarrow{\varphi_{3}}K_{2}\xrightarrow{\varphi_{2}}K_{1}\xrightarrow{\varphi_{1}}K_{0}\to
0$ (3)

is a complex, and we call it the Koszul complex of $(f_{1},\ldots,f_{m})$. The
$i$-th homology group is given by

$H_{i}(K_{\bullet})=\mathrm{Ker}(\varphi_{i})/\mathrm{Im}(\varphi_{i+1}).$ (4)

In particular, we have

$H_{0}(K_{\bullet})=R/\langle f_{1},\ldots,f_{m}\rangle_{R}.$ (5)

The kernel and the image of a graded homomorphism are both graded submodule in
general, so that $\mathrm{Ker}(\varphi_{i})$ and $\mathrm{Im}(\varphi_{i+1})$
are graded $R$-module, and so is the quotient module $H_{i}(K_{\bullet})$. In
the following, we denote by $H_{i}(K_{\bullet})_{d}$ the degree-$d$
homogeneous part of $H_{i}(K_{\bullet})$.

Note that $\mathrm{Ker}(\varphi_{1})=\mathrm{syz}(f_{1},\ldots,f_{m})$ (the
right hand side is the module of syzygies), and that
$\mathrm{Im}(\varphi_{2})\subset
K_{1}=\bigoplus_{j=1}^{m}R(-d_{j})\mathbf{e}_{j}$ is generated by

$\\{\mathbf{t}_{i,j}:=f_{i}\mathbf{e}_{j}-f_{j}\mathbf{e}_{i}:1\leq i<j\leq
m\\}.$ (6)

Hence, putting

$\mathrm{tsyz}(f_{1},\ldots,f_{m}):=\langle\mathbf{t}_{i,j}:1\leq i<j\leq
m\rangle_{R},$ (7)

we have

$H_{1}(K_{\bullet})=\mathrm{syz}(f_{1},\ldots,f_{m})/\mathrm{tsyz}(f_{1},\ldots,f_{m}).$
(8)

######  Definition 1 (Trivial syzygies)

With notation as above, we call each generator $\mathbf{t}_{i,j}$ (or each
element of $\mathrm{tsyz}(f_{1},\ldots,f_{m})$) a trivial syzygy for
$(f_{1},\ldots,f_{m})$. We also call $\mathrm{tsyz}(f_{1},\ldots,f_{m})$ the
module of trivial syzygies.

We also note that $H_{m}(K_{\bullet})=0$, since $\varphi_{m}$ is clearly
injective by definition.

###### Remark 1

When $K=\mathbb{F}_{q}$, a vector of the form $f_{i}^{q-1}\mathbf{e}_{i}$ is
also referred to as a trivial syzygy, in the context of Ding-Schmidt’s
definition for first fall degree Ding2013  (see (CG20, , Section 4.2) or (N22,
, Section 3.2) for reviews). More concretely, putting $B:=R/\langle
x_{1}^{q},\ldots,x_{n}^{q}\rangle_{R}$ and
$\overline{f}_{i}:=f_{i}\bmod{\langle x_{1}^{q},\ldots,x_{n}^{q}\rangle}$, we
define the Koszul complex of $(\overline{f}_{1},\ldots,\overline{f}_{m})\in
B^{m}$ similarly to that of $(f_{1},\ldots,f_{m})\in R^{m}$, and denote it by
$\overline{K}_{\bullet}=\overline{K}_{\bullet}(\overline{f}_{1},\ldots,\overline{f}_{m})$.
Then, the vectors
$\overline{f}_{i}\mathbf{e}_{j}-\overline{f}_{j}\mathbf{e}_{i}$ and
$\overline{f}_{i}^{q-1}\mathbf{e}_{i}$ in $B^{m}$ for $1\leq i<j\leq m$ are
syzygies for $(\overline{f}_{1},\ldots,\overline{f}_{m})$. Each
$\overline{f}_{i}\mathbf{e}_{j}-\overline{f}_{j}\mathbf{e}_{i}$ is called a
Koszul syzygy, and the Koszul syzygies together with
$\overline{f}_{i}^{q-1}\mathbf{e}_{i}$’s are referred to as trivial syzygies
for $(\overline{f}_{1},\ldots,\overline{f}_{m})$. The first fall degree
$d_{\rm ff}(f_{1},\ldots,f_{m})$ is equal to the minimal integer $d$ with
$\mathrm{syz}(\overline{f}_{1},\ldots,\overline{f}_{m})_{d}\supsetneq\mathrm{tsyz^{+}}(\overline{f}_{1},\ldots,\overline{f}_{m})_{d}$
in $(B_{d-d_{i}})^{m}$, where
$\mathrm{tsyz^{+}}(\overline{f}_{1},\ldots,\overline{f}_{m})$ denotes the
submodule in $B^{m}$ generated by the trivial syzygies for
$(\overline{f}_{1},\ldots,\overline{f}_{m})$.

Note that, for each $i$, a homomorphism $H_{i}(K_{\bullet})\to
H_{i}(\overline{K}_{\bullet})$ is canonically induced by taking modulo
$\langle x_{1}^{q},\ldots,x_{n}^{q}\rangle_{R}$. In particular, we have the
following composite $K$-linear map:

$\eta_{d}:H_{1}(K_{\bullet})_{d}\to
H_{1}(\overline{K}_{\bullet})_{d}\to\mathrm{syz}(\overline{f}_{1},\ldots,\overline{f}_{m})_{d}/\mathrm{tsyz^{+}}(\overline{f}_{1},\ldots,\overline{f}_{m})_{d}.$

for each $d$. Putting $d=d_{\rm ff}(f_{1},\ldots,f_{m})$ and letting $D$ to be
the minimal integer with $H_{1}(K_{\bullet})_{D}\neq 0$, it is straightforward
to verify the following:

  * •

If $q>D$, then $\eta_{D}$ is injective, and
$\mathrm{syz}(\overline{f}_{1},\ldots,\overline{f}_{m})_{D}\supsetneq\mathrm{tsyz^{+}}(\overline{f}_{1},\ldots,\overline{f}_{m})_{D}$,
whence $D\geq d$.

  * •

If $q>d$, then $\eta_{d}$ is surjective. In this case, $H_{1}(K)_{d}\neq 0$,
so that $D\leq d$.

See (N22, , Lemmas 4.2 and 4.3) for a proof. Therefore, we have $d=D$ for
sufficiently large any $q$.

###  2.2 Hilbert–Poincaré series and semi-regular sequences

######  Definition 2 (Hilbert–Poincaré series)

For a finitely generated graded $R$-module $M$, we define the Hilbert function
${\rm HF}_{M}$ of $M$, given by

${\rm HF}_{M}(d)=\mathrm{dim}_{K}M_{d}$ (9)

for each $d\in{\color[rgb]{0,0,0}\mathbb{Z}_{\geq 0}}$. The Hilbert–Poincaré
series ${\rm HS}_{M}$ of $M$ is defined as the formal power series

${\rm HS}_{M}(z)=\sum_{d=0}^{\infty}{\rm
HF}_{M}(d)z^{d}\in\mathbb{Z}\llbracket z\rrbracket.$ (10)

######  Theorem 2.1 (cf. (BW, , Chapter 10))

Let $I$ be a homogeneous ideal of $R$ generated by a set $G\subset R$ of
homogeneous elements of degree not greater than $d$. Let $\prec$ be  a graded
ordering on the monomials in $R$. Then, the following are equivalent:

  1. 1.

$\langle\mathrm{LT}(G)\rangle_{\leq d}=\langle\mathrm{LT}(I)\rangle_{\leq d}$.

  2. 2.

Every $f\in I_{\leq d}$ is reduced to zero modulo $G$.

  3. 3.

For every pair of $f,g\in G$ with
$\mathrm{deg}(\mathrm{LCM}(\mathrm{LM}(f),\mathrm{LM}(g)))\leq d$, the
$S$-polynomial $S(f,g)$ is reduced to zero modulo $G$.

In this case, $G$ is called a $d$-Gröbner basis of $I$ with respect to
$\prec$.

We also review the notion of semi-regular sequence defined by Pardue Pardue .

######  Definition 3 (Semi-regular sequences, (Pardue, , Definition 1))

Let $I$ be a homogeneous ideal of $R$. A degree-$d$ homogeneous element $f\in
R$ is said to be semi-regular on $I$ if the multiplication map
$(R/I)_{t-d}\longrightarrow(R/I)_{d}\ ;\ g\mapsto gf$ is injective or
surjective, for every $t$ with $t\geq d$. A sequence $(f_{1},\ldots,f_{m})\in
R^{m}$ of homogeneous polynomials is said to be semi-regular on $I$ if $f_{i}$
is semi-regular on $I+\langle f_{1},\ldots,f_{i-1}\rangle_{R}$, for every $i$
with $1\leq i\leq m$.

Throughout the rest of this subsection, let $f_{1},\ldots,f_{m}\in R$ be
homogeneous elements of degree $d_{1},\ldots,d_{m}$ respectively, and put
$I=\langle f_{1},\ldots,f_{m}\rangle_{R}$. Furthermore, put
$I^{(0)}:=\\{0\\}$, $A^{(0)}:=R/I^{(0)}=R$. For each $i$ with $1\leq i\leq m$,
we also set $I^{(i)}:=\langle f_{1},\ldots,f_{i}\rangle_{R}$,
$A^{(i)}:=R/I^{(i)}$. The degree-$d$ homogeneous part $A_{d}^{(i)}$ of each
$A^{(i)}$ is given by $A_{d}^{(i)}=R_{d}/I_{d}^{(i)}$, where
$I_{d}^{(i)}=I^{(i)}\cap R_{d}$. We denote by $\psi_{f_{i}}$ the
multiplication map

$A^{(i-1)}\longrightarrow A^{(i-1)}\ ;\ g\mapsto gf_{i},$ (11)

which is a graded homomorphism of degree $d_{i}$. For every $t\geq d_{i}$, the
restriction map

$\psi_{f_{i}}|_{A^{(i-1)}_{t-d_{i}}}:A^{(i-1)}_{t-d_{i}}\to A^{(i-1)}_{t}$

is a $K$-linear map. On the other hand, as for the surjective homomorphism

$\phi_{i-1}:A^{(i-1)}\to A^{(i)}\ ;\ f+I^{(i-1)}\mapsto f+I^{(i)},$ (12)

it is straightforward to see that for each $t$ with $0\leq t\leq d_{i}-1$, the
restriction map

$\phi_{i-1}|_{A_{t}^{(i-1)}}:A_{t}^{(i-1)}\to A_{t}^{(i)}$

is an isomorphism of $K$-linear spaces, whence

$\mathrm{dim}_{K}A^{(i-1)}_{t}=\mathrm{dim}_{K}A^{(i)}_{t}\quad(0\leq t\leq
d_{i}-1).$ (13)

###### Lemma 1

With notation as above, for each $1\leq i\leq m$ and for each $t\geq d_{i}$,
we have the following equalities:

$\dim_{K}(A^{(i)}_{t})=\dim_{K}(A^{(i-1)}_{t})-\mathrm{dim}_{K}\mathrm{Im}\left(A^{(i-1)}_{t-d_{i}}\xrightarrow{\times
f_{i}}A^{(i-1)}_{t}\right),$ (14)
$\mathrm{dim}_{K}\mathrm{Im}\left(A^{(i-1)}_{t-d_{i}}\xrightarrow{\times
f_{i}}A^{(i-1)}_{t}\right)=\dim_{K}(A^{(i-1)}_{t-d_{i}})-\mathrm{dim}_{K}(0:f_{i})_{t-d_{i}},$
(15)

where we set $(0:f_{i})=\\{g\in A^{(i-1)}:gf_{i}=0\\}$. Hence,

  * •

The multiplication map $A^{(i-1)}_{t-d_{i}}\xrightarrow{\times
f_{i}}A^{(i-1)}_{t}$ is injective if and only if

$\dim_{K}(A^{(i)}_{t})=\dim_{K}(A^{(i-1)}_{t})-\dim_{K}(A^{(i-1)}_{t-d_{i}}).$
(16)

In this case, one has ${\rm dim}_{K}(A^{(i-1)}_{t-d_{i}})\leq{\rm
dim}_{K}(A^{(i-1)}_{t})$.

  * •

The multiplication map $A^{(i-1)}_{t-d_{i}}\xrightarrow{\times
f_{i}}A^{(i-1)}_{t}$ is surjective if and only if

$\dim_{K}(A^{(i)}_{t})=0.$ (17)

In this case, one has ${\rm dim}_{K}(A^{(i-1)}_{t-d_{i}})\geq{\rm
dim}_{K}(A^{(i-1)}_{t})$.

###### Proof

Let $i$ and $t$ be integers such that $1\leq i\leq m$ and $t\geq d_{i}$. Since
we have $(0:f_{i})_{t-d_{i}}=\\{g\in A^{(i-1)}_{t-d_{i}}:gf_{i}=0\\}$, the
sequence

$\setcounter{MaxMatrixCols}{11}\begin{CD}0@>{}>{}>(0:f_{i})_{t-d_{i}}@>{}>{}>A^{(i-1)}_{t-d_{i}}@>{\times
f_{i}}>{}>A^{(i-1)}_{t}@>{}>{}>A^{(i)}_{t}@>{}>{}>0\end{CD}$ (18)

of $K$-linear maps is exact, where $(0:f_{i})_{t-d_{i}}\to
A_{t-d_{i}}^{(i-1)}$ is an inclusion map. The exactness of this sequence
implies the desired equalities (14) and (15).

The semi-regularity is characterized by equivalent conditions in Proposition 1
below. In particular, the fourth condition enables us to compute the
Hilbert–Poincaré series of each $A^{(i)}$ easily.

######  Proposition 1 (cf. (Pardue, , Proposition 1))

With notation as above, the following are equivalent:

  1. 1.

$(f_{1},\ldots,f_{m})\in R^{m}$ is semi-regular.

  2. 2.

For each $1\leq i\leq m$ and for each $t\geq d_{i}$, we have (16) or (17),
namely

$\dim_{K}(A^{(i)}_{t})=\max\\{0,\dim_{K}(A^{(i-1)}_{t})-\dim_{K}(A^{(i-1)}_{t-d_{i}})\\}.$

  3. 3.

For each $i$ with $1\leq i\leq m$, we have

${\rm HS}_{A^{(i)}}(z)=[{\rm HS}_{A^{(i-1)}}(z)(1-z^{d_{i}})].$ (19)

  4. 4.

For each $i$ with $1\leq i\leq m$, we have

${\rm
HS}_{A^{(i)}}(z)=\left[\frac{\prod_{j=1}^{i}(1-z^{d_{j}})}{(1-z)^{n}}\right].$
(20)

When $K$ is an infinite field, Pardue also conjectured in (Pardue, ,
Conjecture B) that generic polynomial sequences are semi-regular.

###  2.3 Cryptographic semi-regular sequences

We here review the notion of cryptographic semi-regular sequences, which are
defined by a  condition weaker than one for semi-regular sequences. The notion
of cryptographic semi-regular sequences is introduced first by Bardet et al.
(e.g., BFS , BFSY ) motivated to analyzing the complexity of computing Gröbner
bases. Diem Diem2  also formulated cryptographic semi-regular sequences, in
terms of commutative and homological algebra. The terminology “cryptographic”
was named by Bigdeli et al. in their recent work BNDGMT21 , in order to
distinguish such a sequence from a semi-regular sequence defined by Pardue
(see Definition 3 in the previous subsection).

######  Definition 4 ((BFS, , Definition 3); see also (Diem2, , Definition 1))

Let $f_{1},\ldots,f_{m}\in R$ be homogeneous polynomials of positive degrees
$d_{1},\ldots,d_{m}$ respectively, and put $I=\langle
f_{1},\ldots,f_{m}\rangle_{R}$. The notations $I^{(i)}$ and $A^{(i)}$ are also
the same as in the previous subsection. For each integer $d$ with
$d\geq\mathrm{max}\\{d_{i}:1\leq i\leq m\\}$, we call a sequence
$(f_{1},\ldots,f_{m})\in R^{m}$ of homogeneous polynomials $d$-regular if it
satisfies the following condition:

  * •

For each $i$ with $1\leq i\leq m$, if a homogeneous polynomial $g\in R$
satisfies $gf_{i}\in\langle f_{1},\ldots,f_{i-1}\rangle_{R}$ and
$\mathrm{deg}(gf_{i})<d$, then we have $g\in\langle
f_{1},\ldots,f_{i-1}\rangle_{R}$. In other word, the multiplication map
$A^{(i-1)}_{t-d_{i}}\longrightarrow A^{(i-1)}_{t}\ ;\ g\mapsto gf_{i}$ is
injective for every $t$ with $d_{i}\leq t<d$.

Diem Diem2  determined the (truncated) Hilbert series of $d$-regular sequences
as in the following proposition:

######  Theorem 2.2 (cf. (Diem2, , Theorem 1))

With the same notation as in Definition 4, the following are equivalent  for
each $d$ with $d\geq\mathrm{max}\\{d_{i}:1\leq i\leq m\\}$:

  1. 1.

$(f_{1},\ldots,f_{m})\in R^{m}$ is $d$-regular. Namely, for each $(i,t)$ with
$1\leq i\leq m$ and $d_{i}\leq t<d$, the equality (16) holds.

  2. 2.

We have

${\rm
HS}_{A^{(m)}}(z)\equiv\frac{\prod_{j=1}^{m}(1-z^{d_{j}})}{(1-z)^{n}}\pmod{z^{d}}.$
(21)

  3. 3.

$H_{1}(K_{\bullet}(f_{1},\ldots,f_{m}))_{\leq d-1}=0$.

######  Proposition 2 ((Diem2, , Proposition 2 (a)))

With the same notation as in Definition 4, let $D$ and $i$ be natural numbers.
Assume that  $H_{i}(K(f_{1},\ldots,f_{m}))_{\leq D}=0$. Then, for each $j$
with $1\leq j<m$, we have  $H_{i}(K(f_{1},\ldots,f_{j}))_{\leq D}=0$.

###### Definition 5

A finitely generated graded $R$-module $M$ is said to be Artinian if there
exists a sufficiently large $D\in\mathbb{Z}$ such that $M_{d}=0$ for all
$d\geq D$.

######  Definition 6 ((BFS, , Definition 4), (BFSY, , Definition 5))

For a homogeneous ideal $I$ of $R$, we define its degree of regularity $d_{\rm
reg}(I)$ as follows: If the finitely generated graded $R$-module $R/I$ is
Artinian, we set $d_{\rm reg}(I):=\mathrm{min}\\{d:R_{d}=I_{d}\\}$, and
otherwise we set $d_{\rm reg}(I):=\infty$.

As for an upper-bound on the degree of regularity, we refer to (GG23-2, ,
Theorem 21).

###### Remark 2

In Definition 6, since $R/I$ is Noetherian, it is Artinian if and only if it
is of finite length. In this case, the degree of regularity $d_{\rm reg}(I)$
is equal to the Castelnuovo-Mumford regularity $\mathrm{reg}(I)$ of $I$ (see
e.g., (Eisen, , §20.5) for the definition), whence $d_{\rm
reg}(I)=\mathrm{reg}(I)=\mathrm{reg}(R/I)+1$.

######  Definition 7 ((BFS, , Definition 5), (BFSY, , Definition 5); see also
(Diem, , Section 2))

A sequence $(f_{1},\ldots,f_{m})\in R^{m}$ of homogeneous polynomials is said
to be cryptographic semi-regular if it is $d_{\rm reg}(I)$-regular, where we
set $I=\langle f_{1},\ldots,f_{m}\rangle_{R}$.

The cryptographic semi-regularity is characterized by equivalent conditions in
Proposition 3 below. In particular, the second condition enables us to compute
the Hilbert–Poincaré series of $A^{(i)}$ easily.

######  Proposition 3 ((Diem2, , Proposition 1 (d)); see also (BFSY, ,
Proposition 6))

With the same notation as in Definition 4, we put $D=d_{\rm reg}(I)$. Then,
the following are equivalent:

  1. 1.

$(f_{1},\ldots,f_{m})\in R^{m}$ is cryptographic semi-regular.

  2. 2.

We have

${\rm
HS}_{R/I}(z)=\left[\frac{\prod_{j=1}^{m}(1-z^{d_{j}})}{(1-z)^{n}}\right].$
(22)

  3. 3.

$H_{1}(K_{\bullet}(f_{1},\ldots,f_{m}))_{\leq D-1}=0$.

###### Remark 3

By the definition of degree of regularity, if $(f_{1},\ldots,f_{m})\in R^{m}$
is cryptographic semi-regular, $d_{\rm reg}(I)$ coincides with $\deg({\rm
HS}_{R/I}(z))+1$, where we set $I=\langle f_{1},\ldots,f_{m}\rangle$.

In 1985, Fröberg already conjectured in Froberg  that, when $K$ is an infinite
field, a sequence of homogeneous polynomials $f_{1},\ldots,f_{m}\in R$ of
degrees $d_{1},\ldots,d_{m}$ generates an ideal $I$ with the Hilbert series of
the form (22), namely $(f_{1},\ldots,f_{m})$ is cryptographic semi-regular. It
can be proved (cf. Pardue ) that Fröberg’s conjecture is equivalent to
Pardue’s one (Pardue, , Conjecture B) introduced in Subsection 2.2. We also
note that Moreno-Socías conjecture MS  is stronger than the above two
conjectures, see (Pardue, , Theorem 2) for a proof.

It follows from the fourth condition of Proposition 1 together with the second
condition of Proposition 3 that the semi-regularity implies the cryptographic
semi-regularity.

######  Definition 8 (Affine semi-regular sequences)

A sequence $F=(f_{1},\ldots,f_{m})\in R^{m}$ of not necessarily homogeneous
polynomials $f_{1},\ldots,f_{m}$ is said to be semi-regular (resp.
cryptographic semi-regular) if $F^{\rm top}=(f_{1}^{\rm top},\ldots,f_{m}^{\rm
top})$ is semi-regular (resp. cryptographic semi-regular). In this case, we
call $F$ an affine semi-regular (resp. affine cryptographic semi-regular)
sequence.

###### Remark 4

For an affine crytographic semi-regular sequence $F=(f_{1},\ldots,f_{m})\in
R^{m}$ with $K=\mathbb{F}_{q}$, it follows from Proposition 3 that $d_{\rm
reg}(\langle F^{\rm top}\rangle)\leq d_{\rm ff}(f_{1}^{\rm
top},\ldots,f_{m}^{\rm top})$ for $q\gg 0$, where $d_{\rm ff}(f_{1}^{\rm
top},\ldots,f_{m}^{\rm top})$ is the first fall degree defined in Remark 1.

##  3 Quick review on the computation of Gröbner basis

In this section, we first review previous studies on the computation of
Gröbner bases for polynomial ideals.

###  3.1 Overview of existing Gröbner basis algorithms

Since Buchberger Buchberger  discovered the notion of Gröbner bases and a
fundamental algorithm for computing them, many efforts have been done for
improving the efficiency of the computation based on Buchberger’s algorithm.
In his algorithm, S-polynomials play an important role for the Gröbner basis
construction and give a famous termination criterion called Buchberger’s
criterion, that is, for a given ideal $I$ of a polynomial ring over a field,
its finite generating subset $G$ is a Gröbner basis of $I$ with respect to a
monomial ordering if and only if the S-polynomial $S(g,g^{\prime})$ for any
distinct pair $g,g^{\prime}\in G$ is reduced to $0$ modulo $G$. For details on
Buchberger’s algorithm and monomial orders, see e.g., BW .

In the below, we list effective improvements for algorithms which are, at the
same time, very useful to analyze the complexity of the Gröbner basis
computation. Here we note that the choice of a monomial order is also very
crucial for the efficiency of the Gröber basis computation, but we here do not
discuss about its choice. (In general, the degree reverse lexicographical
(DRL) ordering111This ordering is also called the graded reverse
lexicographical (grevlex) ordering. is considered as the most efficient
ordering for the computation.)

•

(1) Related to S-polynomial:

–

(1-1) Strategy for selecting S-polynomial: It is considered to be very
effective to apply so called the normal strategy, where we choose a pair
$(g,g^{\prime})$ for which the least common multiple (LCM) of the leading
monomials ${\rm LM}(g)$ and ${\rm LM}(g^{\prime})$ with respect to the fixed
ordering $\prec$ as smaller as possible. (See (BW, , Chapter 5.5).) The
strategy is very suited for a homogeneous ideal with a degree compatible
ordering such as DRL, as we can utilize the graded structure of a homogeneous
ideal. Also, the sugar strategy is designed for a non-homogeneous ideal to
make the computational behavior very close to that for the homogenized ideal.
See Subsection 3.1 below for some details on homogenization. (See also (CLO, ,
Chapter 2.10).)

–

(1-2) Avoiding unnecessary S-polynomial computation: In Buchberger’s
algorithm, we add a polynomial to a generating set $G$ which is computed from
an S-polynomial by possible reduction of elements in $G$. Since the cost of
the construction of S-polynomials and their reduction dominate the whole
computation, S-polynomials which are reduced to 0 are very harmful for the
efficiency. Thus, it is highly desired to avoid such unnecessary S-polynomials
as many as possible.

*

(A) Based on simple rules: At earlier stage, there are easily computable
rules, called Buchberger’s criterion and Gebauer-Möller’s one. Those are using
the relation of the LMs of a pair and those of a triple, see (BW, , Chapter
5.5). Then, in 2002, Faugére F5  introduced the notion of signature and
proposed his $F_{5}$ algorithm based on a general rule among signatures. We
call algorithms using signatures including variants of $F_{5}$ signature-based
algorithms (SBA). See a survey EF  and the detail in Subsection 3.1 below.

*

(B) Using invariants of polynomial ideal: For a homogeneous ideal $I$ of a
polynomial ring $R$, when its Hilbert function ${\rm HF}_{R/I}(z)$ is known
before the computation, we can utilize the value ${\rm HF}_{R/I}(d)$ for each
$d\in{\mathbb{N}}$ (cf. Tra ). Because, by the value ${\rm HF}_{R/I}(d)$, we
can check whether we can stop the computation of S-polynomials of degree $d$
or not. We call an algorithm using Hilbert functions a Hilbert driven
(Buchberger’s) algorithm. See (CLO, , Chapter 10.2) or (DL, , Section 3.5).

•

(2) Efficient computation of S-polynomial reduction: Since the computation of
S-polynomial reduction is a dominant step in the whole Gröbner basis
computation, its efficiency heavily affects the total efficiency. As the
reduction for a polynomial by elements of $G$ is sequentially applied, we can
transform the whole reduction to a Gaussian elimination of a matrix. This
approach was suggested in form of Macaulay matrices by Lazard Lazard81  and
the first efficient algorithm was given by Faugére F4 , which is called the
$F_{4}$ algorithm. Of course, we can combine the $F_{4}$ and $F_{5}$
algorithms effectively, which is called the matrix-$F_{5}$ algorithm.

•

(3) Solving coefficient growth: For a polynomial ideal over the rational
number field ${\mathbb{Q}}$, the computation may be suffered by certain growth
of coefficients in polynomials appearing during the Gröbner basis computation.
To resolve this problem, several modular methods were proposed. As a typical
one, we can use Chinese remainder algorithm (CRA), where we first compute the
reduced Gröbner bases $G_{p}$ over several finite fields ${\mathbb{F}}_{p}$
and then recover the reduced Gröbner basis from $G_{p}$’s by CRA. See NY  for
details about choosing primes $p$.

###### Remark 5

For several public key cryptosystems based on polynomial ideals over finite
fields or the elliptic curve discrete logarithm problem, estimating the cost
of finding zeros of polynomial ideals is important to analyze the security of
those systems, where the computation of their Gröbner bases is a fundamental
tool. In this situation,  the $F_{5}$ algorithm and matrix-$F_{5}$ algorithm
as its efficient variant with an efficient DRL ordering are considered, as not
only those can attain efficient computation but also they are suited for
estimating the computational complexity.

In the below, we introduce the notion of homogenization and an algorithm for
Gröbner basis computation based on signature ($F_{5}$ or its variants) which
will be used for our study in Section 5 below.

#### Homogenization of polynomials and monomial orders

We begin with recalling the notion of homogenization. (See (KR, , Chapter 4)
for details.) Let $K$ be a field, $X=\\{x_{1},\ldots,x_{n}\\}$ a set of
variables, and $\mathcal{T}$ the set of all monomials in $X$. 222As the
symbolc $m$ is used for the size of a generating set, we use $\mathcal{T}$
instead of $\mathcal{M}$.

  1. (1)

For a non-homogeneous polynomial $f=\sum_{{t}\in\mathcal{T}}c_{t}{t}$ in
$K[X]$ with $c_{t}\in K$, its homogenization $f^{h}$ is defined, by
introducing a new variable $y$, as

$f^{h}=\sum_{{t}\in\mathcal{T}}c_{t}{t}{y^{\deg(f)-{\color[rgb]{0,0,0}\deg(t)}}}.$

Thus $f^{h}$ is a homogeneous polynomial in $X\cup\\{y\\}$ over $K$ with total
degree $d=\deg(f)$. Also for a set $F$ of polynomials, its homogenization
$F^{h}$ is defined as $F^{h}=\\{f^{h}\;|\;f\in F\\}$. We also write $X^{h}$
for $X\cup\\{y\\}$.

  2. (2)

Conversely, for a homogeneous polynomial $h$ in $K[X\cup\\{y\\}]$, its
dehomogenization $h^{\rm deh}$ is defined by substituting $y$ with $1$, that
is, $h^{\rm deh}=h(X,1)$. (It is also denoted by $h|_{y=1}$.) For a set $H$ of
homogeneous polynomials in $K[X\cup\\{y\\}]$, its dehomogenization $H^{\rm
deh}$ (or $H|_{y=1}$) is defined as $H^{\rm deh}=\\{h^{\rm deh}\;|\;h\in
H\\}$.

  3. (3)

For an ideal $I$ of $K[X]$, its homogenization $I^{h}$, as an ideal, is
defined as $\langle I^{h}\rangle_{K[X\cup\\{y\\}]}$.

  4. (4)

For a homogeneous ideal $J$ in $K[X\cup\\{y\\}]$, its dehomogenization $J^{\rm
deh}$, as a set, is an ideal of $K[X]$. We note that if a homogeneous ideal
$J$ is generated by $H$, then $J^{\rm deh}=\langle H^{\rm deh}\rangle_{K[X]}$
and for an ideal $I$ of $K[X]$, we have $(I^{h})^{\rm deh}=I$.

  5. (5)

For a monomial (term) order $\prec$ on the set of monomials $\mathcal{T}$ in
$X$, its homogenization $\prec_{h}$ on the set of monomials $\mathcal{T}^{h}$
in $X\cup\\{y\\}$ is defined as follows: For two monomials $X^{\alpha}y^{a}$,
$X^{\beta}y^{b}$ in $\mathcal{T}^{h}$,
$X^{\alpha}y^{a}\prec_{h}X^{\beta}y^{b}$ if and only if one of the following
holds:

     * (i)

$a+|\alpha|<b+|\beta|$, or

     * (ii)

$a+|\alpha|=b+|\beta|$ and $X^{\alpha}\prec X^{\beta}$,

where $\alpha=(\alpha_{1},\ldots,\alpha_{n})\in\mathbb{Z}_{\geq 0}^{n}$ and
$|\alpha|=\alpha_{1}+\cdots+\alpha_{n}$, and where $X^{\alpha}$ denotes
$x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$. Here, for a monomial
$X^{\alpha}{\color[rgb]{0,0,0}y^{a}}$, we call $X^{\alpha}$ and
${\color[rgb]{0,0,0}y^{a}}$ the $X$-part and the $y$-part, respectively. If a
monomial order $\prec$ is degree-compatible,  that is, it first compares the
total degrees, the restriction $\prec_{h}|_{\mathcal{T}}$ of $\prec_{h}$ on
$\mathcal{T}$ coincides with $\prec$.

It is well-known that for a Gröbner basis $H$ of $\langle F^{h}\rangle$ with
respect to $\prec^{h}$, its dehomonization $\\{h^{\rm deh}\;|\;h\in H\\}$ is
also a Gröbner basis of $\langle F\rangle$ with respect to $\prec$.

#### Signature and $F_{5}$ algorithm

Here we briefly outline the $F_{5}$ algorithm, which is an improvement of
Buchberger’s algorithm. For details, see a survey EF . Let
$F=\\{f_{1},\ldots,f_{m}\\}\subset R=K[X]$ be a given generating set. For each
polynomial $h$ constructed during Gröbner basis computation of $\langle
F\rangle$, the $F_{5}$ algorithm attaches a special label called a signature
as follows: Since $h$ belongs to $\langle F\rangle$, it can be written as

$h=a_{1}f_{1}+a_{2}f_{2}+\cdots+a_{m}f_{m},$ (23)

for some $a_{1},\ldots,a_{m}\in R$. Then, we assign $h$ to
$a_{1}\mathbf{e}_{1}+\cdots+a_{m}\mathbf{e}_{m}\in R^{m}$ and we call its
leading monomial $t\mathbf{e}_{i}$ with respect to a monomial (module)
ordering in $R^{m}$ the signature of $h$. As the expression (23) is not
unique, in order to determine the signature, we construct the expression
procedurally or use the uniquely determined residue in $R^{m}/{\rm
syz}(f_{1},\ldots,f_{m})$ by a module Gröbner basis of ${\rm
syz}(f_{1},\ldots,f_{m})$. (For the latter case, we call it the minimal
signature.) Here we denote the signature of $h$ by ${\rm sig}(h)$. Anyway, in
the $F_{5}$ algorithm, we can meet the both by carefully choosing
S-polynomials and by applying restricted reduction steps (called
$\Sigma$-reductions) for S-polynomials without any change of the signature.
(So, we need not to compute a module Gröbner basis of ${\rm
syz}(f_{1},\ldots,f_{m})$.) We note that for the S-polynomial
$S(h_{1},h_{2})={\color[rgb]{0,0,0}c_{1}t_{1}h_{1}-c_{2}t_{2}h_{2}}$ with
$c_{1},c_{2}\in K$ and $t_{1},t_{2}\in\mathcal{T}$, the signature  ${\rm
sig}(S(h_{1},h_{2}))$ is determined as the largest one between ${\rm
sig}({\color[rgb]{0,0,0}c_{1}t_{1}}h_{1})$ and ${\rm
sig}({\color[rgb]{0,0,0}c_{2}t_{2}}h_{2})$. Then, we have the following
criteria which are very useful to avoid the computation of unnecessary
S-polynomials. (The latter one is called the syzygy criterion.)

######  Proposition 4 (cf. CLO , EF )

In the $F_{5}$ algorithm, we need not compute an S-polynomial if some
S-polynomial of the same signature was already proceeded, since both are
reduced to the same polynomial. Moreover, we need not compute an S-polynomial
of signature $s$ if there is a signature $s^{\prime}$ such that $s^{\prime}$
divides $s$ and some S-polynomial with the signature $s^{\prime}$ is reduced
to $0$.

###  3.2 Complexity of the Gröbner basis computation

In general, determining the complexity of computing a Gröbner basis is very
hard; in the worst-case, the complexity is doubly exponential in the number of
variables, see e.g., C14 , MR13 , Ritscher  for surveys. It is well-known that
a Gröbner basis with respect to a degree-compatible monomial ordering (in
particular, DRL ordering) can be computed quite more efficiently than ones
with respect to other orderings in general. Moreover, in the case where the
input polynomials generate a zero-dimensional ideal, once a Gröbner basis with
respect to an efficient monomial ordering is computed, one with respect to any
other ordering can be computed easily by the FGLM basis conversion algorithm
FGLM . From this, we focus on the case where the monomial ordering is degree-
compatible, and if necessary we also assume that the ideal generated by the
input polynomials is zero-dimensional.

A typical way to estimate the complexity is to count  the number of
S-polynomials that are reduced during the Gröbner basis computation. In the
case where the chosen monomial ordering is degree-compatible, the most
efficient strategy to compute Gröbner bases is the so-called normal strategy,
which proceed degree by degree, namely increase the degree of critical pairs
defining S-polynomials, as in the $F_{4}$ and $F_{5}$ algorithms. For an
algorithm adopting this strategy, several S-polynomials are dealt with
consecutively at the same degree, which is called the step degree. The lowest
step degree at which an intermediate ideal basis contains a minimal Gröbner
basis is called the solving degree of the algorithm. Determining (or finding a
tight bound for) the solving degree is difficult without computing any Gröbner
basis. On the other hand, once it is specified, we can estimate the complexity
of the algorithm in a straightforward manner. For example, for a linear
algebra-based algorithm, such as an $F_{4}$-family including the
(matrix-)$F_{5}$ algorithm and the XL family (cf. XL ), that follows Lazard’s
atrategy Lazard  to reduces S-polynomials by the Gaussian elimination on
Macaulay matrices, its complexity is estimated to be $O(N^{\omega})$ with
$N=\binom{n+D}{n}$, where $D$ is the solving degree, and where $\omega$ is the
matrix multiplication exponent with $2\leq\omega<3$.

Caminata et al. (cf. BNDGMT21 , CG20 , CG23 ) defined the solving degree of an
algorithm based on Lazard’s strategy in a mathematically rigorous way, see
their papers for the definition. For a given polynomial sequence
$F=(f_{1},\ldots,f_{m})\in R^{m}$ and a degree-compatible monomial ordering
$\prec$, it is denoted by $\mathrm{sd}_{\prec}(F)$. They provided a
mathematical formulation for the relation between the solving degree
$\mathrm{sd}_{\prec}(F)$ and algebraic invariants coming from $F$, such as the
maximal Gröbner basis degree, the degree of regularity, the
Castelnuovo–Mumford regularity, the first and last degrees, and so on. Here,
the maximal Gröbner basis degree of the ideal $\langle F\rangle_{R}$ is the
maximal degree of elements in the reduced Gröbner basis of $\langle
F\rangle_{R}$ with respect to a fixed monomial ordering $\prec$, and is
denoted by $\mathrm{max.GB.deg}_{\prec}(F)$.

In the following, we recall some of Caminata et al.’s results. We set $\prec$
as the DRL ordering on $R$ with $x_{n}\prec\cdots\prec x_{1}$, and fix it
throughout the rest of this subsection. Let $y$ be an extra variable for
homogenization as in the previous subsection, and $\prec^{h}$ the
homogenization of $\prec$, so that $y\prec x_{i}$ for any $i$ with $1\leq
i\leq n$. Then, we have

${\rm max.GB.deg}_{\prec}(F)\leq\mathrm{\rm sd}_{\prec}(F)=\mathrm{\rm
sd}_{\prec^{h}}(F^{h})={\rm max.GB.deg}_{\prec^{h}}(F^{h}),$

see CG20  for a proof. Here, we also recall Lazard’s bound for the maximal
Gröbner basis degree of $\langle F^{h}\rangle_{R^{\prime}}$ with
$R^{\prime}=R[y]$:

######  Theorem 3.1 (Lazard; (Lazard, , Theorem 2))

With notation as above, we assume that the number of projective zeros of
$F^{h}$ is finite (and therefore $m\geq n$), and that
$f_{1}^{h}=\cdots=f_{m}^{h}=0$ has no non-trivial solution over the algebraic
closure $\overline{K}$ with $y=0$, i.e., $F^{\rm top}$ has no solution in
$\overline{K}^{n}$ other than $(0,\ldots,0)$. Then, supposing also that
$d_{1}\geq\cdots\geq d_{m}$, we have

$\mathrm{max.GB.deg}_{\prec^{h}}(F^{h})\leq d_{1}+\cdots+d_{\ell}-\ell+1$ (24)

with $\ell:=\mathrm{min}\\{m,n+1\\}$.

Lazard’s bound given in (24) is also referred to as the Macaulay bound, and it
provides an upper-bound for the solving degree of $F$ with respect to  a DRL
ordering.

As for the maximal Gröbner basis degree of $\langle F\rangle$, if $\langle
F^{\rm top}\rangle$ is Aritinian, we have

$\mathrm{max.GB.deg}_{\prec^{\prime}}(F)\leq d_{\rm reg}(\langle F^{\rm
top}\rangle)$ (25)

for any degree-compatible ordering $\prec^{\prime}$ on $R$, see (CG20, ,
Remark 15) or Lemma 4 below for a proof. Both $d_{\rm reg}(\langle F^{\rm
top}\rangle)$ and $\mathrm{\rm sd}_{\prec}(F)$ are greater than or equal to
${\rm max.GB.deg}_{\prec}(F)$, whereas the degree of regularity (or the first
fall degree) used in the cryptographic literature as a proxy (or a heuristic
upper-bound) for the solving degree. However, it is pointed out in BNDGMT21 ,
CG20 , and CG23  by explicit examples that any of the degree of regularity and
the first fall degree does not produce an estimate for the solving degree in
general, even when $F$ is an affine (cryptographic) semi-regular sequence.
Caminata-Gorla proved in CG23  that the solving degree is nothing but the last
fall degree if it is greater than the maximal Gröbner basis degree:

######  Theorem 3.2 ((CG23, , Theorem 3.1))

With notation as above, for any degree-compatible monomial ordering
$\prec^{\prime}$ on $R$, we have the following inequality:

$\mathrm{sd}_{\prec^{\prime}}(F)=\max\\{d_{F},{\rm
max.GB.deg}_{{\color[rgb]{0,0,0}\prec^{\prime}}}(F)\\},$

where $d_{F}$ denotes the last fall degree of $F$ defined in (CG23, ,
Definition 1.5).

By this theorem, if $d_{\rm reg}({\color[rgb]{0,0,0}\langle F^{\rm
top}\rangle})<d_{F}$, the degree of regularity is no longer an upper-bound on
the solving degree.

On the other hand, Semaev and Tenti claimed that the solving degree is linear
in the degree of regularity, if $K$ is a (large) finite field, and if the
input system contains  polynomials related to the field equations, say
$x_{i}^{q}-x_{i}$ for $1\leq i\leq n$:

######  Theorem 3.3 ((ST, , Theorem 2.1), (Tenti, , Corollary 3.67))

With notation as above, assume that $K=\mathbb{F}_{q}$, and that $F$ contains
$x_{i}^{q}-x_{i}$ for $1\leq i\leq n$. Put $D=d_{\rm reg}(\langle F^{\rm
top}\rangle)$. If $D\geq\max\\{\deg(f):f\in F\\}$ and $D\geq q$, then we have

$\mathrm{sd}_{\prec}(F)\leq 2D-2.$ (26)

In Subsection 5.2 below, we will prove a similar inequality (26) for the case
where $F$ not necessarily contains a field equation but is cryptographic semi-
regular.

##  4 Hilbert-Poincaré series of affine semi-regular sequence

As in the previous section, let $K$ be a field, and
$R=K[X]=K[x_{1},\ldots,x_{n}]$ denote the polynomial ring of $n$ variables
over $K$. We denote by $R_{d}$ the homogeneous part of degree $d$, that is,
the set of homogeneous polynomials of degree $d$ and $0$. Recall Definition 7
for the definition of cryptographic semi-regular sequences.

The Hilbert-Poincaré series of (homogeneous) cryptographic semi-regular (resp.
semi-regular) sequences is given by (22). On the other hand, the Hilbert-
Poincaré series of the homogenizaton $F^{h}$ cannot be computed without
knowing its Gröbner basis in general, but we shall prove that it can be
computed till the degree $d_{\rm reg}(\langle F^{\rm top}\rangle)$ if $F$ is
affine cryptographic semi-regular, namely $F^{\rm top}$ is cryptographic semi-
regular.

###### Theorem 4.1

Let $R=K[x_{1},\ldots,x_{n}]$ and $R^{\prime}=R[y]$, and let
$F=(f_{1},\ldots,f_{m})$ be a sequence of not necessarily homogeneous
polynomials in $R$. Assume that $F$ is affine cryptographic semi-regular.
Then, for each $d$ with $d<D:=d_{\mathrm{reg}}(\langle F^{\rm top}\rangle)$,
we have

${\rm HF}_{R^{\prime}/\langle F^{h}\rangle}(d)={\rm HF}_{R/\langle F^{\rm
top}\rangle}(d)+{\rm HF}_{{\color[rgb]{0,0,0}R^{\prime}}/\langle
F^{h}\rangle}(d-1),$ (27)

and hence

${\rm HF}_{R^{\prime}/\langle F^{h}\rangle}(d)={\rm HF}_{R/\langle F^{\rm
top}\rangle}(d)+\cdots+{\rm HF}_{R/\langle F^{\rm top}\rangle}(0),$ (28)

whence we can compute the value ${\rm HF}_{R^{\prime}/\langle
F^{h}\rangle}(d)$ from the formula (22).

###### Proof

Let $K_{\bullet}=K_{\bullet}(f_{1}^{h},\ldots,f_{m}^{h})$ by the Koszul
complex associated to $(f_{1}^{h},\ldots,f_{m}^{h})$, which is given by (3).
By tensoring $K_{\bullet}$ with $R^{\prime}/\langle y\rangle_{R^{\prime}}\cong
K[x_{1},\ldots,x_{n}]=R$ over $R^{\prime}$, we obtain the following exact
sequence of chain complexes:

$\textstyle{0\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{K_{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\times
y}$$\textstyle{K_{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi_{\bullet}}$$\textstyle{K_{\bullet}\otimes_{R^{\prime}}R\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0,}$

where $\times y$ is a graded homomorphism of degree $1$ multiplying each entry
of a vector with $y$. Note that there is an isomorphism

$K_{i}\otimes_{R^{\prime}}R\cong\bigoplus_{1\leq j_{1}<\cdots<j_{i}\leq
m}R(-d_{j_{1}\cdots
j_{i}})\mathbf{e}_{j_{1}\cdots{\color[rgb]{0,0,0}{j_{i}}}},$

by which $\pi_{i}:K_{i}\to K_{i}\otimes_{R^{\prime}}R$ reduces each entry of a
vector in $K_{i}$ modulo $y$. In particular, we have

$\displaystyle K_{0}\otimes_{R^{\prime}}R$ $\displaystyle=$ $\displaystyle
R^{\prime}/\langle
f_{1}^{h},\ldots,f_{m}^{h}\rangle_{R^{\prime}}\otimes_{R^{\prime}}R^{\prime}/\langle
y\rangle_{R^{\prime}}$ $\displaystyle\cong$ $\displaystyle R^{\prime}/\langle
f_{1}^{h},\ldots,f_{m}^{h},y\rangle_{R^{\prime}}$ $\displaystyle\cong$
$\displaystyle R/\langle f_{1}^{\rm top},\ldots,f_{m}^{\rm top}\rangle_{R}$

for $i=0$. This means that the chain complex
$K_{\bullet}\otimes_{R^{\prime}}R$ gives rise to the Kosuzul complex
associated with $({f}_{1}^{\rm top},\ldots,f_{m}^{\rm top})$. We induce a long
exact sequence of homology groups. In particular, for each degree $d$, we have
the following long exact sequence:

$\textstyle{H_{i+1}(K_{\bullet})_{d-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\times
y}$$\textstyle{H_{i+1}(K_{\bullet})_{d}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi_{i+1}}$$\textstyle{H_{i+1}(K_{\bullet}\otimes_{R^{\prime}}R)_{d}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\delta_{i+1}}$$\textstyle{H_{i}(K_{\bullet})_{d-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\times
y}$$\textstyle{H_{i}(K_{\bullet})_{d}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi_{i}}$$\textstyle{H_{i}(K_{\bullet}\otimes_{R^{\prime}}R)_{d}}$

where $\delta_{i+1}$ is a connecting homomorphism produced by the Snake lemma.
For $i=0$, we have the following exact sequence:

$\textstyle{H_{1}(K_{\bullet}\otimes_{R^{\prime}}R)_{d}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{H_{0}(K_{\bullet})_{d-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\times
y}$$\textstyle{H_{0}(K_{\bullet})_{d}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{H_{0}(K_{\bullet}\otimes_{R^{\prime}}R)_{d}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0.}$

From our assumption that $F^{\rm top}$ is cryptographic semi-regular, it
follows from Propostion 3 that $H_{1}(K_{\bullet}\otimes_{R^{\prime}}R)_{\leq
D-1}=0$ for $D:=d_{\rm reg}(\langle F^{\rm top}\rangle)$. Therefore, if $d\leq
D-1$, we have an exact sequence

$\textstyle{0\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{H_{0}(K_{\bullet})_{d-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\times
y}$$\textstyle{H_{0}(K_{\bullet})_{d}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{H_{0}(K_{\bullet}\otimes_{R^{\prime}}R)_{d}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$

of $K$-linear spaces, so that

$\mathrm{dim}_{K}H_{0}(K_{\bullet})_{d}=\mathrm{dim}_{K}H_{0}(K_{\bullet}\otimes_{R^{\prime}}R)_{d}+\mathrm{dim}_{K}H_{0}(K_{\bullet})_{d-1}$

by the dimension theorem. Since $H_{0}(K_{\bullet})=R^{\prime}/\langle
F^{h}\rangle$ and
${\color[rgb]{0,0,0}H_{0}(K_{\bullet}\otimes_{R^{\prime}}R)}=R/\langle F^{\rm
top}\rangle$, we have the equality (27), as desired.

###### Remark 6

In the proof of Theorem 4.1, the multiplication map
$H_{0}(K_{\bullet})_{d-1}\to H_{0}(K_{\bullet})_{d}$ by $y$ is injective for
all $d<D$, whence ${\rm HF}_{R^{\prime}/\langle F^{h}\rangle}(d)$ is
monotonically increasing for $d<D-1$. On the other hand, since
$H^{0}(K_{\bullet}\otimes_{R^{\prime}}R)_{d}=(R/\langle F^{\rm
top}\rangle)_{d}=0$ for all $d\geq D$ by the definition of the degree of
regularity, the multiplication map $H_{0}(K_{\bullet})_{d-1}\to
H_{0}(K_{\bullet})_{d}$ by $y$ is surjective for all $d\geq D$, whence ${\rm
HF}_{R^{\prime}/\langle F^{h}\rangle}(d)$ is monotonically decreasing for
$d\geq D-1$. By this together with (C14, , Theorem 3.3.4), the homogeneous
ideal $\langle F^{h}\rangle$ is zero-dimensional or trivial, i.e., there are
at most a finite number of projective zeros of $F^{h}$ (and thus there are at
most a finite number of affine zeros of $F$).

By Theorem 4, it can be proved that the Hilbert-Poincaré series of
$R^{\prime}/\langle F^{h}\rangle$ satisfies the following which may correspond
to (BFSY, , Proposition 6):

###### Corollary 1

Let $D=d_{\rm reg}(\langle F^{\rm top}\rangle)$. Then

${\rm HS}_{R^{\prime}/\langle
F^{h}\rangle}(z)\equiv\frac{\prod_{i=1}^{m}(1-z^{d_{i}})}{(1-z)^{n+1}}\pmod{z^{D}}.$
(29)

Therefore, by Theorem 2.2 ((Diem2, , Theorem 1)), $F^{h}$ is $D$-regular.
Here, we note that $D=\deg({\rm HS}_{R/\langle F^{\rm
top}\rangle}{)}+1={\deg\left(\left[\frac{\prod_{i=1}^{m}(1-z^{d_{i}})}{(1-z)^{n}}\right]\right)}+1$.

###### Proof

Let ${\rm
HS}^{\prime}(z)=\frac{\prod_{i=1}^{m}(1-z^{d_{i}})}{(1-z)^{n+1}}\bmod{z^{D}}$
and let ${\rm HF}^{\prime}(d)$ denote the coefficient of ${\rm
HS^{\prime}}(z)$ of degree $d$ for $d<D$. First we remark that, as $F^{\rm
top}$ is a cryptographic semi-regular sequence, the Hilbert-Poincaré series of
$R/\langle F^{\rm top}\rangle$ satisfies the following:

${\rm HS}_{R/\langle F^{\rm
top}\rangle}(d){\color[rgb]{0,0,0}=\left[\frac{\prod_{i=1}^{m}(1-z^{d_{i}})}{(1-z)^{n}}\right]}=\frac{\prod_{i=1}^{m}(1-z^{d_{i}})}{(1-z)^{n}}\bmod{z^{D}},$

since ${\rm HF}_{R/\langle F^{\rm top}\rangle}(d)=0$ for $d\geq D$. Then we
have

$\displaystyle{\rm HS}^{\prime}(z)\bmod{z^{D}}$ $\displaystyle=$
$\displaystyle\frac{\prod_{i=1}^{m}(1-z^{d_{i}})}{(1-z)^{n+1}}\bmod{z^{D}}$
$\displaystyle=$
$\displaystyle\frac{\prod_{i=1}^{m}(1-z^{d_{i}})}{(1-z)^{n}}\times(1+z+\cdots+z^{D-1})\bmod{z^{D}}$
$\displaystyle=$ $\displaystyle{\rm HS}_{R/\langle F^{\rm
top}\rangle}(z)\cdot(1+z+\cdots+z^{D-1})\bmod{z^{D}}.$

Therefore, for $d<D$, the equation (28) gives

${\rm HF}^{\prime}(d)={\rm HF}_{R/\langle F^{\rm top}\rangle}(d)+\cdots+{\rm
HF}_{R/\langle F^{\rm top}\rangle}(0)={\rm HF}_{R^{\prime}/\langle
F^{h}\rangle}(d),$

which implies the desired equality (29).

To prove the following corollary, we use a fact that, for a homogeneous ideal
$I$ in $R$, the equality
$\sum_{i=0}^{d}\mathrm{dim}_{K}I_{i}=\mathrm{dim}_{K}(IR^{\prime})_{d}$ holds
for each $d\geq 0$.

###### Corollary 2

With notation as above, assume that $F=(f_{1},\ldots,f_{m})\in R^{m}$ is
affine cryptographic semi-regular. Put $\overline{I}:=\langle F^{\rm
top}\rangle_{R}$ and $\tilde{I}:=\langle F^{h}\rangle_{R^{\prime}}$. Then, we
have
$(\langle\mathrm{LM}(\tilde{I})\rangle_{R^{\prime}})_{d}=(\langle\mathrm{LM}(\overline{I})\rangle_{R^{\prime}})_{d}$
for each $d$ with $d<D:=d_{\rm reg}(\overline{I})$.

###### Proof

We prove
$(\langle\mathrm{LM}(\tilde{I})\rangle_{R^{\prime}})_{d}\subset(\langle\mathrm{LM}(\overline{I})\rangle_{R^{\prime}})_{d}$
by the induction on $d$. The case where $d=0$ is clear from Theorem 4.1, and
so we assume $d>0$. Any element in
$(\langle\mathrm{LM}(\tilde{I})\rangle_{R^{\prime}})_{d}$ is represented as a
finite sum of elements in $R^{\prime}$ of the form $g\cdot\mathrm{LM}(h)$ with
$g\in R^{\prime}$, $h\in\tilde{I}$, and $\mathrm{deg}(gh)=d$. Hence, we can
also write each $g\cdot\mathrm{LM}(h)$ as a $K$-linear combination of elements
of the form $\mathrm{LM}(th)$ for a monomial $t$ in $R^{\prime}$ of dgeree
$\mathrm{deg}(g)$, where $th$ is an element in $\tilde{I}$ of degree $d$.
Therefore, it suffices for showing “$\subset$” to prove that
$\mathrm{LM}(f)\in(\langle\mathrm{LM}(\overline{I})\rangle_{R^{\prime}})_{d}$
for any $f\in\tilde{I}$ with $\mathrm{deg}(f)=d$. We may assume that $f$ is
homogeneous. It is straightforward that $f|_{y=0}\in\overline{I}_{\leq d}$. If
$\mathrm{LM}(f)\in R=K[x_{1},\ldots,x_{n}]$, then we have $\mathrm{LM}(f)={\rm
LM}(f|_{y=0})\in\mathrm{LM}(\overline{I})$. Thus, we may also assume that
$y\mid\mathrm{LM}(f)$. In this case, it follows from the definition of the DRL
ordering that any other term in $f$ is also divisible by $y$, so that
$f\in\langle y\rangle_{R^{\prime}}$. Thus, we can write $f=yh$ for some $h\in
R^{\prime}$, where $h$ is homogeneous of degree $d-1$. As in the proof of
Theorem 4.1, the multiplication map

$(R^{\prime}/\tilde{I})_{d^{\prime}-1}\to(R^{\prime}/\tilde{I})_{d^{\prime}}\
;\ h^{\prime}\bmod{\tilde{I}}\mapsto yh^{\prime}\bmod{\tilde{I}}$

is injective for any $d^{\prime}<d_{\mathrm{reg}}(\overline{I})$, since $F$ is
cryptographic semi-regular. Therefore, it follows from $f\in\tilde{I}_{d}$
that $h\in\tilde{I}_{d-1}$, whence $f=yh\in y\tilde{I}_{d-1}$. By the
induction hypothesis, there exists $g\in\overline{I}$ such that
$\mathrm{LM}(g)\mid\mathrm{LM}(h)$, whence
$\mathrm{LM}(f)\in(\langle\mathrm{LM}(\overline{I})\rangle_{R^{\prime}})_{d}$.

Here, it follows from Theorem 4.1 that

$\displaystyle\mathrm{dim}_{K}(R^{\prime})_{d}-\mathrm{dim}_{K}\tilde{I}_{d}$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{d}\left(\mathrm{dim}_{K}R_{i}-\mathrm{dim}_{K}{\overline{I}}_{i}\right)=\sum_{i=0}^{d}\mathrm{dim}_{K}R_{i}-\sum_{i=0}^{d}\mathrm{dim}_{K}{\overline{I}}_{i}$
$\displaystyle=$
$\displaystyle\mathrm{dim}_{K}(R^{\prime})_{d}-\mathrm{dim}_{K}(\overline{I}R^{\prime})_{d},$

and thus
$\mathrm{dim}_{K}\tilde{I}_{d}=\mathrm{dim}_{K}(\overline{I}R^{\prime})_{d}$.
Hence, it follows from
$\langle\mathrm{LM}(\overline{I})\rangle_{R^{\prime}}=\langle\mathrm{LM}(\overline{I}R^{\prime})\rangle_{R^{\prime}}$
that

$\mathrm{dim}_{K}(\langle\mathrm{LM}(\tilde{I})\rangle_{R^{\prime}})_{d}=\mathrm{dim}_{K}(\langle\mathrm{LM}(\overline{I})\rangle_{R^{\prime}})_{d},$

whence
$(\langle\mathrm{LM}(\tilde{I})\rangle_{R^{\prime}})_{d}=(\langle\mathrm{LM}(\overline{I})\rangle_{R^{\prime}})_{d}$,
as desired.

###### Example 1

We give a simple example. Let $p=73$, $K={\mathbb{F}}_{p}$, and

$\displaystyle f_{1}$ $\displaystyle=$ $\displaystyle
x_{1}^{2}+(3x_{2}-2x_{3}-1)x_{1}+x_{2}^{2}+(-2x_{3}-2)x_{2}+x_{3}^{2}+x_{3},$
$\displaystyle f_{2}$ $\displaystyle=$ $\displaystyle
4x_{1}^{2}+(3x_{2}+4x_{3}-2)x_{1}-x_{2}+x_{3}^{2}+2x_{3},$ $\displaystyle
f_{3}$ $\displaystyle=$ $\displaystyle
3x_{1}^{2}-x_{1}+9x_{2}^{2}+(-6x_{3}+1)x_{2}+x_{3}^{2}-x_{3},$ $\displaystyle
f_{4}$ $\displaystyle=$ $\displaystyle
x_{1}^{2}+(-6x_{2}+2x_{3}-2)x_{1}+9x_{2}^{2}+(-6x_{3}+1)x_{2}+2x_{3}^{2}.$

Then, $d_{1}=d_{2}=d_{3}=d_{4}=2$. As their  top parts (maximal total degree
parts) are

$\displaystyle f_{1}^{\rm top}$ $\displaystyle=$ $\displaystyle
x_{1}^{2}+(3x_{2}-2x_{3})x_{1}+x_{2}^{2}-2x_{3}x_{2}+x_{3}^{2},$
$\displaystyle f_{2}^{\rm top}$ $\displaystyle=$ $\displaystyle
4x_{1}^{2}+(3x_{2}+4x_{3})x_{1}+x_{3}^{2},$ $\displaystyle f_{3}^{\rm top}$
$\displaystyle=$ $\displaystyle 3x_{1}^{2}+9x_{2}^{2}-6x_{3}x_{2}+x_{3}^{2},$
$\displaystyle f_{4}^{\rm top}$ $\displaystyle=$ $\displaystyle
x_{1}^{2}+(-6x_{2}+2x_{3})x_{1}+9x_{2}^{2}-6x_{3}x_{2}+2x_{3}^{2},$

one can verify that $F^{\rm top}$ is a cryptographic semi-regular sequence.
Moreover, its degree of regularity is equal to $3$. Indeed, the reduced
Gröbner basis $G_{\rm top}$ of the ideal $\langle F^{\rm top}\rangle$ with
respect to  the DRL ordering $x_{1}\succ x_{2}\succ x_{3}$ is

$\\{x_{3}^{2}x_{2},x_{3}^{3},x_{1}^{2}+68x_{3}x_{2}+55x_{3}^{2},x_{2}x_{1}+27x_{3}x_{2}+29x_{3}^{2},x_{2}^{2}+x_{3}x_{2}+71x_{3}^{2},x_{3}x_{1}+3x_{3}x_{2}+33x_{3}^{2}\\}.$

Then its leading monomials are
$x_{3}^{3},x_{3}^{2}x_{2},x_{1}^{2},x_{1}x_{2},x_{2}^{2},x_{3}x_{1}$ and its
Hilbert-Poincaré series satisfies

${\rm HS}_{R/\langle F^{\rm
top}\rangle}(z)=2z^{2}+3z+1=\left(\frac{(1-z^{2})^{4}}{(1-z)^{3}}\bmod{z^{3}}\right),$

whence the degree of regularity of $\langle F^{\rm top}\rangle$ is 3.

On the other hand, the reduced Gröbner basis $G_{\rm hom}$ of the ideal
$\langle F^{h}\rangle$ with respect to  the DRL ordering $x_{1}\succ
x_{2}\succ x_{3}\succ y$ is

$\displaystyle\\{y^{3}x_{1},y^{3}x_{2},y^{3}x_{3},60y^{2}x_{1}+(x_{3}^{2}+22y^{2})x_{2}+39y^{2}x_{3},$
$\displaystyle
72y^{2}x_{1}+14y^{2}x_{2}+x_{3}^{3}+56y^{2}x_{3},16y^{2}x_{1}+(yx_{3}+55y^{2})x_{2}+38y^{2}x_{3},$
$\displaystyle
72y^{2}x_{1}+66y^{2}x_{2}+yx_{3}^{2}+70y^{2}x_{3},x_{1}^{2}+72yx_{1}+(68x_{3}+40y)x_{2}+55x_{3}^{2}+14yx_{3},$
$\displaystyle(x_{2}+20y)x_{1}+(27x_{3}+37y)x_{2}+29x_{3}^{2}+12yx_{3},$
$\displaystyle 57yx_{1}+x_{2}^{2}+(x_{3}+3y)x_{2}+71x_{3}^{2}+52yx_{3},$
$\displaystyle(x_{3}+22y)x_{1}+(3x_{3}+5y)x_{2}+33x_{3}^{2}+14yx_{3}\\}$

and its leading monomials are
$y^{3}x_{1},y^{3}x_{2},y^{3}x_{3},x_{3}^{2}x_{2},x_{3}^{3},yx_{2}x_{3},yx_{3}^{2},x_{1}^{2},x_{1}x_{2},x_{2}^{2},x_{1}x_{3}$.
Then the Hilbert-Poincaré series of $R^{\prime}/\langle F^{h}\rangle$
satisfies

$\left({\rm HS}_{R^{\prime}/\langle
F^{h}\rangle}(z)\bmod{z^{3}}\right)=\left(6z^{2}+4z+1\bmod{z^{3}}\right)=\left(\frac{(1-z^{2})^{4}}{(1-z)^{4}}\bmod{z^{3}}\right).$

We note that ${\rm HF}_{R^{\prime}/\langle F^{h}\rangle}(3)=4$ and ${\rm
HF}_{R^{\prime}/\langle F^{h}\rangle}(4)=1$. We can also examine ${\rm
LM}(G_{\rm hom})_{d<D}={\rm LM}(G_{\rm top})_{d<D}$ and, for $g\in G_{\rm
hom}$, if ${\rm LM}(g)$ is divided by $y$, then $\deg(g)\geq D=3$. Thus, at
the degree 3, there occurs a degree-fall. See the detail in Subsection 3.2.1.
Also, the reduced Gröbner basis of $\langle F\rangle$ with respect to $\prec$
is $\\{x,y,z\\}$ and we can examine that the dehomonization of $G_{\rm hom}$
is also a Gröbner basis of $\langle F\rangle$.

##  5 Application to Gröbner bases computation

We use the same notation as in the previous section, and assume that $F$ is
cryptographic semi-regular. Here we apply results in the previous section to
the computation of Gröbner bases of ideals $\langle F\rangle$ and $\langle
F^{h}\rangle$. Let $G$, $G_{\rm hom}$, and $G_{\rm top}$ be reduced Gröbner
bases of $\langle F\rangle$, $\langle F^{h}\rangle$, and $\langle F^{\rm
top}\rangle$, respectively, where their monomial ordering are DRL $\prec$ or
its extension $\prec^{h}$. Also we let $D=d_{\rm reg}(\langle F^{\rm
top}\rangle)$.

As to the computation of $G$, in special settings on $F$ such as $F$
containing field equations or $F$ appearing in a multivariate polynomial
cryptosystem, methods using the value $D$ or those of the Hilbert function for
degrees less than $D$ were proposed. (See ST ; Sakata .) Our results in the
section can be considered as a certain extension and to give exact
mathematical proofs for the correctness of the methods.

Here, we extend the notion of top part to a homogeneous polynomial $h$ in
$R^{\prime}=R[y]$. We call $h|_{y=0}$ the top part of $h$ and denote it by
$h^{\rm top}$. Thus, if $h^{\rm top}$ is not zero, it coincides with the top
part $(h|_{y=1})^{\rm top}$ of the dehomogenization $h|_{y=1}$ of $h$. We
remark that $g^{\rm top}=(g^{h})^{\rm top}$ for a polynomial $g$ in $R$.

###  5.1 Gröbner basis elements of degree less than $D$

Here we show relations between $(G_{\rm hom})_{<D}$ and $(G_{\rm top})_{<D}$
with proofs which are useful for the computations of $G_{\rm hom}$ and $G$.

Since $F^{\rm top}$ is cryptographic semi-regular and $F^{h}$ is $D$-regular
by Corollary 1, $H_{1}(K_{\bullet}(F^{\rm
top}))_{{\color[rgb]{0,0,0}<D}}=H_{1}(K_{\bullet}(F^{h}))_{{\color[rgb]{0,0,0}<D}}=0$.
As $H_{1}(K_{\bullet}(F^{h}))={\rm syz}(F^{h})/{\rm tsyz}(F^{h})$ and
$H_{1}(K_{\bullet}(F^{\rm top}))={\rm syz}(F^{\rm top})/{\rm tsyz}(F^{h})$
(see (8)), we have the following corollary, where ${\rm tsyz}(F^{h})$ denotes
the module of trivial syzygies (see Definition 1).

######  Corollary 3 ((Diem2, , Theorem 1))

It follows that ${\rm syz}(F^{\rm top})_{<D}={\rm tsyz}(F^{\rm top})_{<D}$ and
${\rm syz}(F^{h})_{<D}={\rm tsyz}(F^{h})_{<D}$.

This implies that, in the Gröbner basis computation $G_{\rm hom}$ with respect
to a degree-compatible ordering $\prec^{h}$, if an S-polynomial
$S(g_{1},g_{2})=t_{1}g_{1}-t_{2}g_{2}$ of degree less than $D$ is reduced to
$0$, it comes from some trivial syzyzy, that is,
$\sum_{i=1}^{m}(t_{1}a^{(1)}_{i}-t_{2}a^{(2)}_{i}-b_{i})\mathbf{e}_{i}$
belongs to $\color[rgb]{0,0,0}{\rm tsyz}(F^{h})_{<D}$, where
$g_{1}=\sum_{i=1}^{m}a^{(1)}_{i}f_{i}^{h}$,
$g_{2}=\sum_{i=1}^{m}a^{(2)}_{i}f_{i}^{h}$,
$S(g_{1},g_{2})=\sum_{i=1}^{m}b_{i}f_{i}^{h}$ and ${\rm
sig}(S(g_{1},g_{2}))={\color[rgb]{0,0,0}{\rm
LM}(\sum_{i=1}^{m}(t_{1}a^{(1)}_{i}-t_{2}a^{(2)}_{i}-b_{i})\mathbf{e}_{i})}$
Thus, since the $F_{5}$ algorithm (or its variant such as the matrix-$F_{5}$
algorithm) with the Schreyer ordering automatically discards an S-polynomial
whose signature is the LM of some trivial syzygy, we can avoid unnecessary
S-polynomials. See Subsection 3.1 for a brief outline of the $F_{5}$ algorithm
and the syzygy criterion (Proposition 4).

In addition to the facts above, as mentioned (somehow implicitly) in (Bar, ,
Section 3.5) and BFSY , when we compute a Gröbner basis of $\langle
F^{h}\rangle$ for the degree less than $D$ by the $F_{5}$ algorithm with
respect to $\prec^{h}$, for each computed non-zero polynomial $g$ from an
S-polynomial, say $S(g_{1},g_{2})$, of degree less than $D$, its signature
does not come from any trivial syzygy and so the reductions of
$S(g_{1},g_{2})$ are done only at its top part. This implies that the Gröbner
basis computation process of $\langle F^{h}\rangle$ corresponds exactly to
that of $\langle F\rangle$ for each degree less than $D$.  Especially, the
following lemma holds. Here we give a concrete and easy proof using Corollary
2. We  also note that the following can be considered as a corrected version
of (Sakata, , Theorem 4).

###### Lemma 2

For each degree $d<D$,

${\rm LM}(G_{\rm hom})_{d}={\rm LM}(G_{\rm top})_{d}.$ (30)

###### Proof

We can prove the equality (30) by the induction on $d$. Assume that the
equality (30) holds for  $d<D-1$.

Consider any $t\in{\rm LM}(G_{\rm hom})_{d+1}$. Then, there is a polynomial
$g\in G_{\rm hom}$ such that ${\rm LM}(g)=t$. By Corollary 2, for $d+1<D$, we
have

$(\langle\mathrm{LM}(\langle
F^{h}\rangle{\color[rgb]{0,0,0})}\rangle_{R^{\prime}})_{d+1}=(\langle\mathrm{LM}(\langle
F^{\rm top}\rangle_{\color[rgb]{0,0,0}R})\rangle_{R^{\prime}})_{d+1}$

and ${\rm LM}(g)$ is divided by ${\rm LM}(g^{\prime})$ for some $g^{\prime}\in
G_{\rm top}$. Since $G_{\rm hom}$ is reduced, ${\rm LM}(g)$ is not divisible
by any monomial in ${\rm LM}(G_{\rm hom})_{\leq d}={\rm LM}(G_{\rm top})_{\leq
d}$, and hence $\mathrm{deg}(g^{\prime})=d+1$. In this case, we have
$\mathrm{LM}(g)=\mathrm{LM}(g^{\prime})$. Thus, ${\rm LM}(G_{\rm
hom})_{d+1}\subset{\rm LM}(G_{\rm top})_{d+1}$ holds.

By the same argument, ${\rm LM}(G_{\rm hom})_{d+1}\supset{\rm LM}(G_{\rm
top})_{d+1}$ can be shown. We note that for each $t\in{\rm LM}(G_{\rm
top})_{d+1}$, there is a polynomial $g\in{\color[rgb]{0,0,0}(G_{\rm
top})_{d+1}}{\color[rgb]{0,0,0}\subset\langle F^{\rm top}\rangle_{d+1}}$ such
that $t={\rm LM}(g)$. In this case, there are homogeneous polynomials
$a_{1},\ldots,a_{m}$ such that $g=\sum_{i=1}^{m}a_{i}f^{\rm top}$. Then
$g^{\prime}=\sum_{i=1}^{m}a_{i}f^{h}$ in $\langle F^{h}\rangle_{d+1}$ has $t$
as its LM.

Next we consider $(G_{\rm hom})_{D}$.

###### Lemma 3

For each monomial $M$ in $X$ of degree $D$, there is an element $g$ in
$(G_{\rm hom})_{\leq D}$ such that ${\rm LM}(g)$ divides $M$. Therefore,

$\langle{\rm LM}((G_{\rm hom})_{\leq D})\rangle\cap R_{D}=R_{D}.$ (31)

Moreover, for each element $g$ in $(G_{\rm hom})_{D}$ with $g^{\rm
top}\not=0$, the top-part $g^{\rm top}$ consists of one term, that is, $g^{\rm
top}={\rm LT}(g)$, where ${\rm LT}$ denotes the leading term of $g$. (We
recall ${\rm LT}(g)={\rm LC}(g){\rm LM}(g)$.)

###### Proof

Since $\langle F^{\rm top}\rangle_{D}=R_{D}$, for each monomial $M$ in $X$ of
degree $D$, there are homogeneous polynomials $a_{1},\ldots,a_{m}$ such that
$M=\sum_{i=1}^{m}a_{i}f_{i}^{\rm top}$. Now consider
$h=\sum_{i=1}^{m}a_{i}f_{i}^{h}$ which belongs to $\langle F^{h}\rangle$.
Then, as $f_{i}^{h}=f_{i}^{\rm top}+yh_{i}$ for some $h_{i}$ in $R^{\prime}$,
we have

$h=\sum_{i=1}^{m}a_{i}(f_{i}^{\rm top}+yh_{i})=\sum_{i=1}^{m}a_{i}f_{i}^{\rm
top}+y\sum_{i=1}^{m}a_{i}h_{i}=M+y\sum_{i=1}^{m}a_{i}h_{i}$

and ${\rm LM}(h)=M$. As $G_{\rm hom}$ is the reduced Gröbner basis of $\langle
F^{h}\rangle$, there is some $g$ in $(G_{\rm hom})_{\leq D}$ whose LM divides
$M$.

Next we prove the second assertion. Let $g_{1},\ldots,g_{k}$ be all elements
of $(G_{\rm hom})_{D}$ which have non-zero top parts, and set ${\rm
LM}(g_{1})\prec\cdots\prec{\rm LM}(g_{k})$. We show that $g_{i}^{\rm top}={\rm
LT}(g_{i})$ for all $i$. Suppose, to the contrary, that our claim does not
hold for some $g_{i}$. Then, $g_{i}^{\rm top}$ can be written as $={\rm
LT}(g_{i})+T_{2}+\cdots+T_{s}$ for some terms $T_{2},\ldots,T_{s}$ in $R_{D}$.
Since ${\rm LM}(T_{j})\prec{\rm LM}(g_{i})$ for $2\leq j\leq s$, it follows
from equality (31) that each $\mathrm{LM}(T_{j})$ is equal to ${\rm
LM}(g_{\ell})$ for some $\ell<i$ or is divisible by ${\rm LM}(g^{\prime})$ for
some $g^{\prime}\in(G_{\rm hom})_{<D}$. This contradicts to the fact that
$G_{\rm hom}$ is reduced.

###### Remark 7

If we apply a signature-based algorithm such as the $F_{5}$ algorithm or its
variant to compute the Gröbner basis of $\langle F^{h}\rangle$, its
$\Sigma$-Gröbner basis is a Gröbner basis, but is not always reduced in the
sense of ordinary Gröbner basis, in general. In this case, we have to compute
so called inter-reduction among elements of the $\Sigma$-Gröbner basis for
obtaining the reduced Gröbner basis.

###  5.2 Gröbner basis elements of degree not less than $D$

In this subsection, we shall extend the upper bound on solving degree given in
(ST, , Theorem 2.1) to our case.

###### Remark 8

In ST , polynomial ideals over ${\mathbb{F}}_{q}[X]$ are considered. Under the
condition where the generating set $F$ contains the field equations
$x_{i}^{q}-x_{i}$ for $1\leq i\leq n$, the solving degree of $\langle
F\rangle$ is bounded by $2D-2$, where $D=d_{\rm deg}(\langle F^{\rm
top}\rangle)$. For estimating the upper bound, the property $\langle F^{\rm
top}\rangle_{D}=R_{D}$ was essentially used. As the property also holds in our
case, we  may apply their arguments. Also in (BNDGMT21, , Section 3.2), the
case where $F^{h}$ is cryptographic semi-regular is considered. The results on
the solving degree and the maximal degree of the Gröbner basis are heavily
related to our result in this subsection. See Example 2.

When we use the normal selection strategy on the choice of S-polynomials, the
Gröbner basis computation of $\langle F\rangle$ proceeds along with the graded
structure of $R$ in its early stage, By Lemma 2 it simulates faithfully that
of $\langle F^{\rm top}\rangle$ until the degree of computed polynomial
becomes $D-1$, that is, it produces $\\{g|_{y=1}:g\in(G_{\rm hom})_{<D}\\}$.
Also, by Lemma 3, it also produces $\\{g|_{y=1}:g\in(G_{\rm hom})_{D},{g^{\rm
top}\not=0}\\}$. We note that, as $g^{\rm top}\not=0$, $g|_{y=1}$ is also
produced during the computation of the Gröbner basis $G$. We also note that
the $F_{5}$ algorithm actually uses the normal strategy.

###### Lemma 4

If $D\geq{\rm max}\\{\deg(f):f\in F\\}$, then the maximal Gröbner basis degree
and the solving degree are bounded as follows:

${\rm max.GB.}\deg_{\prec}(F)\leq D\mbox{ and }{\rm
sd}_{\prec}(F)\leq{\color[rgb]{0,0,0}2D-2}.$

###### Proof

We consider $H=\\{g|_{y=1}:g\in(G_{\rm hom})_{\leq D},{g^{\rm top}\not=0}\\}$.
Then $H$ is a subset obtained at earlier stage of Gröbner basis computation of
$\langle F\rangle$. By Lemma 3, $\langle{\rm LM}(H)\rangle$ contains all
monomials in $X$ of degree $D$.

Then we continue the Gröbner basis computation from $H$. In this latter
process, all polynomials generated from S-polynomials are reduced by elements
of $H$. Therefore, their LM’s are reduced with respect to any monomial (in
$X$) of degree $D$ and thus, their degrees are not more than $D-1$. Thus, the
maximal Gröbner basis degree is bounded by $D$, and the degree of
S-polynomials dealt in the whole computation is bounded by $2D$.

Next we show that we can avoid any S-polynomial of degree $2D$ or $2D-1$.

(i) If an S-polynomial $S(g_{1},g_{2})$ has its degree $2D$, then
$\deg(g_{1})=\deg(g_{2})=D$ and $\gcd({\rm LM}(g_{1}),{\rm LM}(g_{2}))=1$.
Then, Buchberger’s criterion predicts that $S(g_{1},g_{2})$ is always reduced
to 0.

(ii) If an S-polynomial $S(g_{1},g_{2})$ has its degree $2D-1$, then
$\deg(g_{1})=\deg(g_{2})=D$, $\deg(g_{1})=D,\deg(g_{2})=D-1$ or
$\deg(g_{1})=D-1,\deg(g_{2})=D$.

For the case where $\deg(g_{1})=D,\deg(g_{2})=D-1$ or
$\deg(g_{1})=D-1,\deg(g_{2})=D$, we have $\gcd({\rm LM}(g_{1}),{\rm
LM}(g_{2}))=1$, and hence $S(g_{1},g_{2})$ is always reduced to 0 by
Buchberger’s criterion.

Finally, we consider the remaining case where $\deg(g_{1})=\deg(g_{2})=D$. In
this case, $g_{1}$ and $g_{2}$ should belong to $H$ and recall from Lemma 3
that both of $(g_{1})^{\rm top}$ and $(g_{2})^{\rm top}$ are single terms.
Then $S(g_{1},g_{2})$ cancels the top parts of $t_{1}g_{1}$ and $t_{2}g_{2}$,
where $S(g_{1},g_{2})=t_{1}g_{1}-t_{2}g_{2}$ for some terms $t_{1}$ and
$t_{2}$. Thus, the degree of $S(g_{1},g_{2})$ is less than $2D-1$.

We refer to (CG20, , Remark 15) for another proof of ${\rm
max.GB.}\deg_{\prec}(F)\leq D$.

As to the computation of $G_{\rm hom}$, we have a result similar to Lemma 4.
Since $\langle{\rm LM}(G_{\rm hom})_{\leq D}\rangle$ contains all monomials in
$X$ of degree $D$, for any polynomial $g$ generated in the middle of the
computation of $G_{\rm hom}$ the degree of $X$ part of ${\rm LM}(g)$ is less
than $D$. Because $g$ is reduced by $(G_{\rm hom})_{\leq D}$. Thus, letting
${\mathcal{U}}$ be the set of all polynomials generated during the computation
of $G_{\rm hom}$, we have

$\\{\mbox{The $X$-part of }{\rm
LM}(g):g\in{\mathcal{U}}\\}\subset\\{x_{1}^{e_{1}}\cdots
x_{n}^{e_{n}}:e_{1}+\cdots+e_{n}\leq D\\}.$

As different $g,g^{\prime}\in{\mathcal{U}}$ can not have the same $X$ part in
their leading terms, the $\\#{\mathcal{U}}$ is bounded by the number of
monomials in $X$ of degree not greater than $D$, that is $\binom{n+D}{n}$. By
using the $F_{5}$ algorithm or its efficient variant, under an assumption that
every unnecessary S-polynomial can be avoided, the number of computed
S-polynomials during the computation of $G_{\rm hom}$ coincides with the
number $\\#{\mathcal{U}}$ and is bounded by $\binom{n+D}{n}$.

###### Example 2

When $m=n+1$ and $d_{1}=\cdots=d_{m}=2$, the Hilbert-Poincáre series of
$R/\langle F^{\rm top}\rangle$ is
$\left[\frac{(1-z^{2})^{n+1}}{(1-z)^{n}}\right]$. Since
$\frac{(1-z^{2})^{n}}{(1-z)^{n}}=(1+z)^{n}=\sum_{i=0}^{n}\binom{n}{i}z^{i}$,
we have

$\frac{(1-z^{2})^{n+1}}{(1-z)^{n}}=(1+z)^{n}(1-z^{2})=1+nz+\sum_{i=2}^{n}\left(\binom{n}{i}-\binom{n}{i-2}\right)z^{i}-nz^{n+1}-z^{n+2},$

so that $D=d_{\rm reg}(\langle F^{\rm
top}\rangle)=\min\left\\{i:\binom{n}{i}-{\color[rgb]{0,0,0}\binom{n}{i-2}}\leq
0\right\\}=\lfloor(n+1)/2\rfloor+1$. In this case, as

${\color[rgb]{0,0,0}2D-2=2(\lfloor(n+1))/2\rfloor+1)-2\leq n+1,}$

we have ${\rm sd}_{\prec}(F)\leq{\color[rgb]{0,0,0}n+1}$ in Lemma 4; see
(BNDGMT21, , Theorem 4.2, Therorem 4.7) for the bound in the case where
$F^{h}$ is a generic sequence.

We note that, in the homogeneous case, we can apply the bound on the maximal
Gröbner basis degree to the solving degree. However, in our case where $F$ is
inhomogeneous, the last fall degree of $F$ coincides with the solving degree.
(See Theorem 3.2.) On the other hand, the solving degree of $F$ can be bounded
by the maximal Gröbner basis degree of $F^{h}$ and we can apply Theorem 3.1,
as our case satisfies its conditions. Then, for the case where $m=n+1$ and
$d_{1}=\cdots=d_{n+1}=2$, it gives the bound $n+2$ for ${\rm
max.GB}.\deg_{\prec^{h}}(F^{h})={\rm
sd}_{\prec^{h}}(F^{h}){\color[rgb]{0,0,0}\geq{\rm sd}_{\prec}(F)}$.

###### Acknowledgements.

The authors thank the anonymous referee for helpful comments. The authors are
also grateful to Yuta Kambe and Shuhei Nakamura for helpful comments. This
work was supported by JSPS Grant-in-Aid for Young Scientists 20K14301 and
23K12949, JSPS Grant-in-Aid for Scientific Research (C) 21K03377, and JST
CREST Grant Number JPMJCR2113.

## References

  * (1) M. Bardet: Étude des systémes algébriques surdéterminés. Applications aux codes correcteurs et á la cryptographie. PhD thesis, Université Paris IV, 2004.
  * (2) M. Bardet, J.-C. Faugére, and B. Salvy: On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations (extended abstract). In: Proceedings of the International Conference on Polynomial System Solving, 71–74, 2004.
  * (3) M. Bardet, J.-C. Faugére, B. Salvy, and B.-Y. Yang: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In: Proceedings of MEGA 2005: Eighth International Symposium on Effective Methods in Algebraic Geometry, 2005.
  * (4) T. Becker and V. Weispfenning: Gröbner Bases: A Computational Approach to Commutative Algebra. GTM, 141, Springer, NY, 1993.
  * (5) M. Bigdeli, E. De Negri, M. M. Dizdarevic, E. Gorla, R. Minko, and S. Tsakou: Semi-Regular Sequences and Other Random Systems of Equations. In: Women in Numbers Europe III, 24, Springer (2021).
  * (6) B. Buchberger: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Innsbruck: Univ. Innsbruck, Mathematisches Institut (Diss.) (1965).
  * (7) A. Caminata and E. Gorla: Solving Multivariate Polynomial Systems and an Invariant from Commutative Algebra. WAIFI 2020: 3–36.
  * (8) A. Caminata and E. Gorla: Solving degree, last fall degree, and related invariants. Journal of Symbolic Computation, 114, 322–335 (2023).
  * (9) J. G. Capaverde: Gröbner bases: Degree bounds and generic ideals. Ph.D thesis, Clemson University, 2014.
  * (10) N. Courtois, A. Klimov, J. Patarin, and A. Shamir: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. EUROCRYPT 2000, LNCS, 1807, Springer, 2000.
  * (11) D. A. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms (Fourth Edition). Undergraduate Texts in Mathematics, Springer, NY, 2010.
  * (12) W. Decker and C. Lossen: Computing in Algebraic Geometry: A Quick Start using SINGULAR. Algorithms and Computation in Mathematics, 16, Springer, 2006.
  * (13) C. Diem: Bounded regularity. Journal of Algebra, Volume 423, 2015, pp. 1143–1160.
  * (14) C. Diem: The XL-algorithm and a Conjecture from Commutative Algebra. Asiacrypt’04, LNCS, 3329, pp. 323–337.
  * (15) J. Ding and D. Schmidt: Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields. In: M. Fischlin, S. Katzenbeisser (eds), Number Theory and Cryptography, Lecture Notes in Computer Science, 8260, Springer, Berlin, Heidelberg.
  * (16) D. Eisenbud: Commutative Algebra: With a View Toward Algebraic Geometry. GTM, vol. 150, Springer (1995).
  * (17) C. Eder and J.-C., Faugère: A survey on signature-based algorithms for computing Gröbner bases. Journal of Symbolic Computation 80 (2017), 719–784.
  * (18) J.-C., Faugère: A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, 139 (1999), 61–88.
  * (19) J.-C., Faugère: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). Proceedings of ISSAC 2002, ACM Press, (2002), pp.75–82.
  * (20) J.-C., Faugère, P. Gianni, D. Lazard, and T. Mora: Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering. Journal of Symbolic Computation, 16 (4), pp. 329–344 (1993)
  * (21) R. Fröberg: An inequality for Hilbert series of graded algebras. Math. Scand., 56 (1985), 117–144.
  * (22) G. Gaggero and E. Gorla: The complexity of solving a random polynomial system. arxiv: 2309.03855, 2023.
  * (23) M. Kreuzer and L. Robbiano: Computational Commutative Algebra 2. Springer, 2005.
  * (24) D. Lazard: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. Computer algebra (London, 1983), pp. 146–156, Lecture Notes in Computer Science, vol. 162, Springer, Berlin, 1983.
  * (25) D. Lazard: Résolution des systèmes d’équations algébriques. Theoretical Computer Science, Volume 15, Issue 1, pp. 77–110, 1981.
  * (26) E. W. Mayr and S. Ritscher: Dimension-dependent bounds for Gröbner bases of polynomial ideals. Journal of Symbolic Computation, Vol. 49 (2013), pp. 78–94.
  * (27) G. Moreno-Socías: Autour de la fonction de Hilbert-Samuel (escaliers d’idéaux polynomiaux), Thèse, École Polytechnique, 1991.
  * (28) S. Nakamura: Formal Power Series on Algebraic Cryptanalysis, arxiv: 2007.14729, 2023.
  * (29) M. Noro and K. Yokoyama. Usage of modular techniques for efficient Computation of ideal operations. Mathematics in Computer Science 12, 1–32, 2018.
  * (30) K. Pardue: Generic sequences of polynomials. Journal of Algebra, 324.4, pp. 579–590, 2010.
  * (31) S. Ritscher: Degree Bounds and Complexity of Gröbner Bases of Important Classes of Polynomial Ideals. Ph.D thessis, Technische Universität München Institut für Mathematik, 2012.
  * (32) Y. Sakata and T. Takagi: Efficient algorithm for solving MQ problem using Hilbert series and its implementation. preprint and presented at Computer Security Symposium 2023 held at Fukuoka. (in Japanese)
  * (33) I. Semaev and A. Tenti: Probabilistic analysis on Macaulay matrices over finite fields and complexity constructing Gröbner bases. Journal of Algebra 565, 651–674, 2021.
  * (34) A. Tenti: Sufficiently overdetermined random polynomial systems behave like semiregular ones, PhD Thesis, University of Bergen (2019), available at https://hdl.handle.net/1956/21158
  * (35) C. Traverso: Hilbert functions and the Buchberger algorithm. Journal of Symbolic Computation 22.4 (1996): 355–376.