# An upper bound for the solving degree in terms of the degree of regularity

Flavio Salizzoni

###### Abstract

The solving degree is an important parameter for estimating the complexity of
solving a system of polynomial equations. In this paper, we provide an upper
bound for the solving degree in terms of the degree of regularity. We also
show that this bound is optimal. As a direct consequence, we prove an upper
bound for the last fall degree and a Macaulay bound.

##  1 Introduction

Many problems can be modeled through a system of polynomial equations.
Solutions to such a system can be found in polynomial time once we know a
reduced Gröbner basis of the system. Nowadays, there are many algorithms for
the computation of Gröbner bases, among which the most efficient ones belong
to the family of linear-algebra based algorithms. This family includes among
others F4, F5, and XL algorithms [6, 7, 8]. Estimating their computational
complexity has become increasingly important because of their applications in
post-quantum cryptography.

Given a linear-algebra based algorithm $H$ for solving a system of polynomial
equations $\mathcal{F}$, the solving degree for $\mathcal{F}$ with respect to
$H$ is defined as the largest degree of a polynomial that appears while we
solve $\mathcal{F}$ using $H$. The interest in this parameter stems from the
fact that an upper bound on it, results in an upper bound on the complexity of
these algorithms. However, computing explicitly the solving degree is in
general extremely difficult. For this reason, it is useful to provide upper
bounds for the solving degree in terms of other parameters, such as the degree
of regularity, the last fall degree, and the Castelnuovo-Mumford regularity.
For instance, in [11] Huang, Kosters, Yang, and Yeo described an algorithm for
solving polynomial systems whose complexity is bounded from above by the last
fall degree. In [4], Caminata and Gorla proved that the solving degree for a
family $\mathcal{F}=\\{f_{1},\dots,f_{k}\\}$ is upper bounded by the
Castelnuovo-Mumford regularity of the family
$\mathcal{F}^{h}=\\{f_{1}^{h},\dots,f_{k}^{h}\\}$, where $f_{i}^{h}$ is the
homogenization of $f_{i}$.

The degree of regularity $\mathrm{d}_{\mathrm{reg}}(\mathcal{F})$ was
introduced by Bardet, Faugère, and Salvy in [1, 9], where they also provide an
upper bound for this degree for cryptographic semi-regular sequences. Even if
many authors use the degree of regularity as a heuristic upper bound for the
solving degree, it is not completely clear what is the exact relation between
these two parameters. For instance, see [4, Examples 4.7] and [2, Examples
2.2, 2.3 and 2.4]. In [15, 16], Semaev and Tenti proved that under certain
conditions the solving degree is bounded from above by
$2\mathrm{d}_{\mathrm{reg}}(\mathcal{F})-2$ (see [16, Corollary 3.67] and the
discussion below [15, Theorem 2.1]).

In this paper we consider the solving degree $\mathrm{sd}_{\sigma}$ for a
family of algorithms that contains among others MutantXL [3] and MXL2 [14].
The main result is the following bound for the solving degree in terms of the
degree of regularity.

######  Theorem 1.1.

Let $\mathcal{F}=\\{f_{1},\dots,f_{n}\\}$ be a family of polynomials such that
$\max\deg(f_{i})\leq\mathrm{d}_{\mathrm{reg}}(\mathcal{F})$ and let $\sigma$
be a degree-compatible term order. Then,
$\mathrm{sd}_{\sigma}(\mathcal{F})\leq\mathrm{d}_{\mathrm{reg}}(\mathcal{F})+1$.

We prove that this bound is optimal showing that for every $1<d\in\mathbb{N}$
there exists a family $\mathcal{F}$ such that
$\mathrm{d}_{\mathrm{reg}}(\mathcal{F})=d$ and
$\mathrm{sd}_{\sigma}(\mathcal{F})=d+1$. As a consequence of Theorem 1.1, we
obtain that the last fall degree is always bounded from above by the degree of
regularity. Finally, we improve the Macaulay bound for a family of polynomials
with finite degree of regularity.

##  2 Preliminaries

Let $\mathbb{K}$ be a field (not necessarily finite). For an ideal
$\mathcal{I}$ in $\mathbb{K}[x_{1},\dots,x_{n}]$, we denote by
$\mathcal{I}_{d}$ the set of all homogeneous polynomial of degree $d$ in
$\mathcal{I}$. Let $\mathcal{F}=\\{f_{1},\dots,f_{k}\\}$ be a finite family of
$\mathbb{K}[x_{1},\dots,x_{n}]$ and let $(\mathcal{F})$ be the ideal generated
by $\mathcal{F}$.

######  Definition 2.1.

Fix a term order $\sigma$. We denote by $\mathrm{Gbd}_{\sigma}(\mathcal{F})$
the maximum degree of an element of a reduced Gröbner basis of $(\mathcal{F})$
with respect to $\sigma$.

We now recall the definition of degree of regularity, as was originally given
in [1, 9] by Bardet, Faugère, and Salvy. For a polynomial
$p\in\mathbb{K}[x_{1},\dots,x_{n}]$, let $p^{\mathrm{top}}$ be the homogeneous
part of largest degree of $p$.

######  Definition 2.2.

The degree of regularity $\mathrm{d}_{\mathrm{reg}}(\mathcal{F})$ of
$\mathcal{F}$ is the smallest integer $d$ for which

$\left(\mathcal{F}^{\mathrm{top}}\right)_{d}=(\mathbb{K}[x_{1},\dots,x_{n}])_{d},$

where
$\mathcal{F}^{\mathrm{top}}=\left\\{f_{1}^{\mathrm{top}},\dots,f_{k}^{\mathrm{top}}\right\\}$.
If such a $d$ does not exist, we set
$\mathrm{d}_{\mathrm{reg}}(\mathcal{F})=+\infty$.

######  Remark 2.3.

If the term order $\sigma$ is degree-compatible, then
$\mathrm{Gbd}_{\sigma}(\mathcal{F})\leq\mathrm{d}_{\mathrm{reg}}(\mathcal{F})$,
as it has been already observed in [4, Remark 4.6] by Caminata and Gorla.

Another important parameter for a family $\mathcal{F}$ is the last fall
degree, which was defined for the first time in [12] by Huang, Kosters, and
Yeo.

######  Definition 2.4.

For an integer $d$, we denote by $V_{\mathcal{F},d}$ the smallest
$\mathbb{K}$-linear space with respect to inclusion such that

  * •

$\\{f\in\mathcal{F}:\deg(f)\leq d\\}\subseteq V_{\mathcal{F},d}$,

  * •

for every $m$ monomial in $\mathbb{K}[x_{1},\dots,x_{n}]$ and every $f\in
V_{\mathcal{F},d}$ such that $\deg(mf)\leq d$, then $mf\in V_{\mathcal{F},d}$.

We set $V_{\mathcal{F},+\infty}=(\mathcal{F})$. The last fall degree
$\mathrm{Lfd}(\mathcal{F})$ is the minimal
$d\in\mathbb{Z}_{>0}\cup\\{+\infty\\}$ such that $f\in
V_{\mathcal{F},\max\\{d,\deg(f)\\}}$ for all $f\in(\mathcal{F})$.

The solving degree is usually defined starting from the Macaulay matrix
$M(\mathcal{F},d)$ to which we add a certain number of rows, see for instance
[10, Section 2.2] for an explicit discussion. However, for the purpose of this
paper, it is more convenient for us to define the solving degree directly in
terms of the spaces $V_{\mathcal{F},d}$. Notice that the following definition
is equivalent to the standard one, as shown in [10, Theorem 1].

######  Definition 2.5.

Let $\sigma$ be a degree-compatible term order. The solving degree
$\mathrm{sd}_{\sigma}(\mathcal{F})$ of $\mathcal{F}$ is the smallest $d$ for
which $V_{\mathcal{F},d}$ contains a Gröbner basis of $\mathcal{F}$ with
respect to $\sigma$.

In [5], Caminata and Gorla proved the following result that highlights a
relation between the solving degree and the last fall degree.

######  Theorem 2.6.

Let $\mathcal{F}$ be a polynomial system and let $\sigma$ be a degree-
compatible term order. Then

$\mathrm{sd}_{\sigma}(\mathcal{F})=\max\\{\mathrm{Lfd}(\mathcal{F}),\mathrm{Gbd}_{\sigma}(\mathcal{F})\\}.$

For a more detailed discussion about the solving degree, the degree of
regularity, and the last fall degree we refer the interested reader to [4, 5].

##  3 Proof of Theorem 1.1

From now on, let $\mathcal{F}=\\{f_{1},\dots,f_{k}\\}$ be a family of
polynomials in $\mathbb{K}[x_{1},\dots,x_{n}]$ such that
$\mathrm{d}_{\mathrm{reg}}(\mathcal{F})=d<+\infty$ and $\deg(f_{i})\leq d$ for
all $1\leq i\leq k$.

######  Lemma 3.1.

For each monomial $m$ of degree $d$ there exists $p\in V_{\mathcal{F},d}$ such
that $p^{\mathrm{top}}=m$.

###### Proof.

Since $d$ is the degree of regularity of $\mathcal{F}$, there exist
$m_{1},\dots,m_{k}$ monomials such that
$\sum_{i=1}^{k}m_{i}f_{i}^{\mathrm{top}}=m$, $m_{i}\neq 0$, and
$\deg(m_{i}f_{i})\leq d$ for all $1\leq i\leq k$. Let
$p=\sum_{i=1}^{k}m_{i}f_{i}$. It is clear that $\deg(p)=\deg(m)=d$, $p\in
V_{\mathcal{F},d}$, and $p^{\mathrm{top}}=m$. ∎

Let $D=\binom{d+n-1}{d}$ and let
$\mathcal{P}_{\mathcal{F}}=\\{p_{1},\dots,p_{D}\\}\subseteq V_{\mathcal{F},d}$
be a set such that for each monic monomial $m$ of degree $d$ there exists
$1\leq i\leq D$ such that $p_{i}^{\mathrm{top}}=m$. The existence of
$\mathcal{P}_{\mathcal{F}}$ follows from Lemma 3.1. Notice that
$\mathcal{P}_{\mathcal{F}}\subseteq V_{\mathcal{F},d+1}$, since
$V_{\mathcal{F},d}\subseteq V_{\mathcal{F},d+1}$.

######  Lemma 3.2.

For every $f\in V_{\mathcal{F},d+1}$ of degree $d$, there exist
$a_{1},\dots,a_{D}\in\mathbb{K}$ and $\bar{f}\in V_{\mathcal{F},d+1}$ with
$\deg(\bar{f})<d$, such that $f=\bar{f}+\sum_{i=1}^{D}a_{i}p_{i}$, where
$p_{i}\in\mathcal{P}_{\mathcal{F}}$.

###### Proof.

Since $\langle
p_{1}^{\mathrm{top}},\dots,p_{D}^{\mathrm{top}}\rangle_{\mathbb{K}}=\mathbb{K}[x_{1},\dots,x_{n}]_{d}$,
there exist $a_{1},\dots,a_{d}\in\mathbb{K}$ such that
$f-\sum_{i=1}^{D}a_{i}p_{i}=\bar{f}$ has degree strictly smaller than $d$. As
$f,p_{1},\dots,p_{D}\in V_{\mathcal{F},d+1}$, we conclude that $\bar{f}\in
V_{\mathcal{F},d+1}$ too. ∎

We denote by $\mathscr{P}_{\mathrm{fin}}(\mathbb{K}[x_{1},\dots,x_{n}]^{3})$
the set of all finite subsets of $\mathbb{K}[x_{1},\dots,x_{n}]^{3}$. We now
define a subset $A_{d}$ of
$\mathscr{P}_{\mathrm{fin}}(\mathbb{K}[x_{1},\dots,x_{n}]^{3})$ giving a
concrete description of its elements. A set
$\\{(m_{1},a_{1},g_{1}),\dots,(m_{\ell},a_{\ell},g_{\ell})\\}\in A_{d}$ if and
only if the followings are satisfied:

  * •

there is exactly one element such that $m_{i}=1$. For simplicity, we assume
$m_{1}=1$. Then, $a_{1}=1$ and $g_{1}\in V_{\mathcal{F},d+1}$,

  * •

$m_{2},\dots,m_{\ell}$ are monic monomials of degree at least $2$,

  * •

$a_{2},\dots,a_{\ell}\in\mathbb{K}\setminus 0$ and
$g_{2},\dots,g_{\ell}\in\mathcal{P}_{\mathcal{F}}$,

  * •

if $m_{i}=m_{j}$ then $g_{i}\neq g_{j}$.

For $X,Y\in A_{d}$, we define $X\oplus Y\in A_{d}$ as follows. If
$(1,1,f_{x})\in X$ and $(1,1,f_{y})\in Y$, then $(1,1,f_{x}+f_{y})\in X\oplus
Y$. Moreover, for $m$ of degree at least $2$, we have that $(m,a,p)\in X\oplus
Y$ if and only if and only if one of the following occurs:

  * •

$(m,a,p)\in X$, and for all $b\in\mathbb{K}\setminus 0$ we have
that$(m,b,p)\notin Y$,

  * •

$(m,a,p)\in Y$, and for all $b\in\mathbb{K}\setminus 0$ we have that
$(m,b,p)\notin X$,

  * •

there exist $(m,b,p)\in X$ and $(m,c,p)\in Y$ such that $a=b+c\neq 0$.

######  Lemma 3.3.

We have that $(A_{d},\oplus)$ is an abelian group whose identity element is
$\\{(1,1,0)\\}$.

###### Proof.

The fact that $\oplus$ is associative and commutative comes from the fact that
$+$ is associative and commutative over $\mathbb{K}$. Moreover, it is clear
from the definition that $\\{(1,1,0)\\}\oplus X=X$ for all $X\in A_{d}$.
Finally, let
$X=\\{(1,1,f_{x}),(m_{2},a_{2},g_{2}),\dots,(m_{\ell},a_{\ell},g_{\ell})\\}\in
A_{d}$, then the set
$\\{(1,1,-f_{x}),(m_{2},-a_{2},g_{2}),\dots,(m_{\ell},-a_{\ell},g_{\ell})\\}$
is also an element of $A_{d}$. We denote this set by $-X$. It is easy to
verify that $X\oplus-X=\\{(1,1,0)\\}$. ∎

For
$X=\\{(1,1,f_{x}),(m_{2},a_{2},g_{2}),\dots(m_{\ell},a_{\ell},g_{\ell})\\}\in
A_{d}$ and $a\in\mathbb{K}$, we define $a\star X$ as

$a\star
X=\begin{cases}\\{(1,1,af_{x}),(m_{2},aa_{2},g_{2}),\dots(m_{\ell},aa_{\ell},g_{\ell})\\}&a\neq
0\\\ \\{(1,1,0)\\}&a=0\end{cases}$

Clearly, we have that $a\star X\in A_{d}$. One can also verify that
$(A_{d},\oplus,\star)$ is a vector space over $\mathbb{K}$.

For $X\in A_{d}$ we define the degree of $X$ as
$\deg(X)=\max\deg(m_{i}g_{i})$. Directly from the definition of $\oplus$ and
of $\star$, we obtain the following lemma.

######  Lemma 3.4.

Let $X,Y\in A_{d}$ and $0\neq a\in\mathbb{K}$, then $\deg(X\oplus
Y)\leq\max\\{\deg(X),\deg(Y)\\}$ and $\deg(a\star X)=\deg(X)$.

For $f\in\mathbb{K}[x_{1},\dots,x_{n}]$, let $A_{d,f}$ be the subset of
$A_{d}$ given by

$A_{d,f}=\left\\{\\{(m_{1},a_{1},g_{1}),\dots,(m_{\ell},a_{\ell},g_{\ell})\\}\in
A_{d}:\sum_{i=1}^{\ell}m_{i}a_{i}g_{i}=f\right\\}.$

Notice that the sets $A_{d,f}$ with $f\in\mathcal{F}$ form a partition of
$A_{d}=\bigsqcup_{f}A_{d,f}$. The following lemma shows how the operations
$\oplus$ and $\star$ act on this partition. We omit the proof since it is
straightforward.

######  Lemma 3.5.

Let $X\in A_{d,f_{x}}$, $Y\in A_{d,f_{y}}$, and $0\neq a\in\mathbb{K}$. Then
$X\oplus Y\in A_{d,f_{x}+f_{y}}$ and $a\star X\in A_{d,af_{x}}$.

Our goal now is to prove that for every $f\in(\mathcal{F})$, the corresponding
$A_{d,f}$ is not empty. To achieve this result, we need one last lemma.

######  Lemma 3.6.

Let $m$ be a monic monomial. If $f\in V_{\mathcal{F},d+1}$ and $\deg(f)\leq
d$, then there exists $X\in A_{d,mf}$ such that $\deg(X)=\deg(mf)$.

###### Proof.

We proceed by induction on $\deg(mf)$. If $\deg(mf)\leq d+1$, since $f\in
V_{\mathcal{F},d+1}$ we have $mf\in V_{\mathcal{F},d+1}$ and therefore
$X=\\{(1,1,mf)\\}\in A_{d,mf}$. So, suppose $\deg(mf)>d+1$. If $\deg(f)<d$,
there exist $m_{1},m_{2}$ monic monomials such that $m=m_{1}m_{2}$ and
$\deg(m_{1}f)=d$. Since $m_{1}f\in V_{\mathcal{F},d+1}$, without loss of
generality, we can assume $\deg(f)=d$.

By Lemma 3.2, we write $f=\bar{f}+\sum_{i=1}^{D}a_{i}p_{i}$ with
$\deg(\bar{f})<d$. By inductive hypothesis we have that there exists
$\bar{X}\in A_{d,m\bar{f}}$ such that $\deg(\bar{X})\leq\deg(m\bar{f})$. Let
$f^{\prime}=\sum_{i=1}^{D}a_{i}p_{i}$. It is clear that
$X^{\prime}=\\{(1,1,0)\\}\cup\\{(m,a_{i},p_{i}):a_{i}\neq 0\\}\in
A_{d,mf^{\prime}}$ and that $\deg(X^{\prime})=\deg(mf^{\prime})$. Since
$mf=m\bar{f}+mf^{\prime}$, by Lemma 3.5 we conclude that $\bar{X}\oplus
X^{\prime}\in A_{d,mf}$ and that $\deg(X\oplus
X^{\prime})=\max\\{\deg(m\bar{f}),\deg(mf^{\prime})\\}=\deg(mf)$. ∎

######  Proposition 3.7.

Let $f\in(\mathcal{F})$, then $A_{d,f}\neq\emptyset$.

###### Proof.

Since $f\in(\mathcal{F})$, there are
$q_{1},\dots,q_{k}\in\mathbb{K}[x_{1},\dots,x_{n}]$ such that $f=\sum
q_{i}f_{i}$. Each $q_{i}f_{i}$ can be written as $\sum m_{i,j}a_{i,j}f_{i}$
with $m_{i,j}$ monic monomial. Since for each $i,j$, $\deg(a_{i,j}f_{i})\leq
d$, by Lemma 3.6 there exists $X_{i,j}\in A_{d,a_{i,j}m_{i,j}f_{i}}$. By Lemma
3.5 we conclude that $\sum_{i,j}X_{i,j}\in A_{d,f}$. ∎

The next theorem is central in the proof of Theorem 1.1.

######  Theorem 3.8.

If $f\in(\mathcal{F})$ and $\deg(f)\leq d+1$, then $f\in V_{\mathcal{F},d+1}$.

###### Proof.

Let $\delta=\min_{X\in A_{d,f}}\deg X$ and $A_{\delta}=\\{X\in
A_{d,f}:\deg(X)=\delta\\}$. By Proposition 3.7 we have that
$A_{d,f}\neq\emptyset$ and so $A_{\delta}\neq\emptyset$. For $X,Y\in
A_{\delta}$ we say that $X\leq Y$ if the greatest monic monomial appearing in
$X$ is smaller than the greatest monic monomial appearing in $Y$ (in degree
lexicographic order with: $x_{1}>x_{2}>\dots>x_{n}$). Let
$X=\\{(m_{1},a_{1},g_{1}),\dots,(m_{\ell},a_{\ell},g_{\ell})\\}$ be a minimal
element of $A_{\delta}$ according to this order. If $\delta\leq d+1$, then
$X=\\{(1,1,f)\\}$ and this implies $f\in V_{\mathcal{F},d+1}$.

If $\delta\geq d+2$, suppose for instance that $m_{2}=x_{1}^{b_{1}}\dots
x_{n}^{b_{n}}$ is maximal among the monomials of $X$ and
$g_{2}=x_{1}^{c_{1}}\dots x_{n}^{c_{n}}+\bar{g}_{2}$ where
$\deg(\bar{g}_{2})<d$. Since $\deg(f)\leq d+1$, there exists an index $i$ such
that $(m_{i}g_{i})^{\mathrm{top}}=(m_{2}g_{2})^{\mathrm{top}}$ and
$m_{i}<m_{2}$. This implies that

$\bar{i}=\min\\{i:b_{i}\neq 0\\}<\max\\{j:c_{j}\neq 0\\}=\bar{j}.$

Let $p\in\mathcal{P}_{\mathcal{F}}$ such that
$p^{\mathrm{top}}=x_{1}^{c_{1}}\dots x_{\bar{i}}^{c_{\bar{i}}+1}\dots
x_{\bar{j}}^{c_{\bar{j}}-1}$ and $m=x_{\bar{i}}^{b_{\bar{i}}-1}\dots
x_{\bar{j}}^{b_{\bar{j}}+1}\dots x_{n}^{b_{n}}$. Then, we can write $f$ as

$f=\sum a_{i}m_{i}g_{i}+a_{2}mp-a_{2}mp=x_{\bar{i}}^{b_{\bar{i}}-1}\dots
x_{\bar{j}}^{b_{\bar{j}}}\dots
x_{n}^{b_{n}}a_{2}(x_{\bar{i}}g_{2}-x_{\bar{j}}p)+\sum_{i\neq
2}a_{i}m_{i}g_{i}+a_{2}mp.$

Notice that $\deg(x_{\bar{i}}g_{2}-x_{\bar{j}}p)\leq d$, and
$g=x_{\bar{i}}g_{2}-x_{\bar{j}}p\in V_{\mathcal{F},d+1}$ since $g_{2},p\in
V_{\mathcal{F},d}$. So, by Lemma 3.6, there exists $X_{1}\in
A_{d,a_{2}x_{\bar{i}}^{b_{\bar{i}}-1}\dots x_{\bar{j}}^{b_{\bar{j}}}\dots
x_{n}^{b_{n}}g}$ such that $\deg(X_{1})\leq\delta-1$. Let $h=\sum_{i\neq
2}a_{i}m_{i}g_{i}$, then
$X_{2}=\\{(1,1,0),(m_{3},a_{3},g_{3}),\dots,(m_{\ell},a_{\ell},g_{\ell})\\}\in
A_{d,h}$ with $\deg(X_{2})\leq\delta$. Obviously
$X_{3}=\\{(1,1,0),(m,a_{2},p)\\}\in A_{d,a_{2}mp}$. By Lemma 3.5, $X_{1}\oplus
X_{2}\oplus X_{3}\in A_{d,f}$. Since $m$ is smaller than $m_{2}$, one of the
following is true:

  * •

the maximal monomial in $X_{1}\oplus X_{2}\oplus X_{3}$ is equal to the
maximal monomial in $X$, but it appears a strictly smaller number of times,

  * •

the maximal monomial in $X_{1}\oplus X_{2}\oplus X_{3}$ is smaller than the
maximal monomial in $X$.

Since at each step the number of monomials equal to $m_{2}$ strictly
decreases, repeating this procedure a finite number of times, we find an
$\tilde{X}$ in $A_{d,f}$ that has a smaller maximal monomial than $X$. This
contradicts the minimality of $X$. Therefore, we conclude that $\delta\leq
d+1$ and so $f\in V_{\mathcal{F},d+1}$. ∎

At this point the proof of Theorem 1.1 is straightforward.

###### Proof of theorem 1.1.

If $\mathrm{d}_{\mathrm{reg}}(\mathcal{F})=+\infty$, the statement is
trivially true. Otherwise, by Remark 2.3, we know that
$\mathrm{Gbd}_{\sigma}(\mathcal{F})\leq\mathrm{d}_{\mathrm{reg}}(\mathcal{F})$.
Then, by Theorem 3.8, we obtain that every element that belongs to a reduced
Gröbner basis is in $V_{\mathcal{F},d+1}$. ∎

The next example shows that the bound in Theorem 1.1 is optimal.

######  Example 3.9.

Let $1<k\in\mathbb{N}$ and let $\mathcal{F}_{k}=\\{x^{k}+y,y^{k}+x,xy\\}$ a
family of polynomial in $\mathbb{K}[x_{1},\dots,x_{n}]$. We have that
$\mathcal{F}_{k}^{\mathrm{top}}=\\{x^{k},y^{k},xy\\}$ and therefore
$\mathrm{d}_{\mathrm{reg}}(\mathcal{F}_{k})=k$. We notice that

$x=-y^{k-1}(x^{k}+y)+(y^{k}+x)+x^{k-1}y^{k-2}(xy),$

and so $x\in(\mathcal{F}_{k})$. By symmetry, we obtain that also
$y\in(\mathcal{F}_{k})$. In particular, we have that $\\{x,y\\}$ is a reduced
Gröbner basis for $\mathcal{F}_{k}$ for every term order. On the one hand, we
observe that $x,y\notin V_{\mathcal{F}_{k},k}$. On the other hand, we have
that

$y^{2}=y(x^{k}+y)-x^{k-1}(xy)\in V_{\mathcal{F}_{k},k+1}\implies
x=(y^{k}+x)-y^{k-2}(y^{2})\in V_{\mathcal{F}_{k},k+1}\implies y\in
V_{\mathcal{F}_{k},k+1}.$

So, $\\{x,y\\}\subseteq V_{\mathcal{F}_{k},k+1}$. This implies that
$\mathrm{sd}_{\sigma}(\mathcal{F}_{k})=k+1=\mathrm{d}_{\mathrm{reg}}(\mathcal{F}_{k})+1$,
independently of the choice of the degree-compatible term order $\sigma$.

The next proposition generalizes Theorem 1.1 to an arbitrary family of
polynomials.

######  Proposition 3.10.

Let $\mathcal{F}=\\{f_{1},\dots,f_{k}\\}$ be a family of polynomials and let
$\sigma$ be a degree-compatible term order. Then,

$\mathrm{sd}_{\sigma}\leq\max\\{\mathrm{d}_{\mathrm{reg}}(\mathcal{F})+1,\deg(f_{1}),\dots,\deg(f_{k})\\}.$

###### Proof.

Let $\mathcal{F}=\\{f_{1},\dots,f_{k}\\}$ be a family of polynomial,
$t=\max\deg(f_{i})$ and suppose that
$\mathrm{d}_{\mathrm{reg}}(\mathcal{F})<t$. We denote by $\mathrm{LT}(f)$ the
leading term of $f$. If there exist indices $i,j$ and a monomial $m$ such that
$\mathrm{LT}(f_{i})=m\mathrm{LT}(f_{j})$, we substitute $f_{i}$ with
$f_{i}-mf_{j}$. By proceeding in this way, in a finite number of steps we find
a family
$\mathcal{F}^{\prime}=\\{f_{1}^{\prime},\dots,f_{s}^{\prime}\\}\subseteq
V_{\mathcal{F},t}$ such that $(\mathcal{F}^{\prime})=(\mathcal{F})$ and for
every pair of indices $i,j$ we have that
$\mathrm{LT}(f_{i})\nmid\mathrm{LT}(f_{j})$. This implies that
$\max\deg(f_{i}^{\prime})\leq\mathrm{d}_{\mathrm{reg}}(\mathcal{F}^{\prime})=d^{\prime}\leq\mathrm{d}_{\mathrm{reg}}(\mathcal{F})$.
By Theorem 1.1, we have that $V_{\mathcal{F}^{\prime},d^{\prime}+1}$ contains
a Gröbner basis of $\mathcal{F}^{\prime}$. Since
$(\mathcal{F})=(\mathcal{F}^{\prime})$, $d^{\prime}<t$, and
$\mathcal{F}^{\prime}\subseteq V_{\mathcal{F},t}$, we conclude that
$V_{\mathcal{F},t}$ contains a Gröbner basis of $\mathcal{F}$. ∎

As direct consequence of the previous proposition, we obtain the following
upper bound on the last fall degree.

######  Corollary 3.11.

Let $\mathcal{F}=\\{f_{1},\dots,f_{n}\\}$ be a family of polynomials. Then,

$\mathrm{Lfd}(\mathcal{F})\leq\max\\{\mathrm{d}_{\mathrm{reg}}(\mathcal{F})+1,\deg(f_{1}),\dots,\deg(f_{k})\\}.$

###### Proof.

By Theorem 2.6 and Proposition 3.10, we obtain that

$\mathrm{Lfd}(\mathcal{F})\leq\max\\{\mathrm{Lfd}(\mathcal{F}),\mathrm{Gbd}_{\sigma}(\mathcal{F})\\}=\mathrm{sd}_{\sigma}(\mathcal{F})\leq\max\\{\mathrm{d}_{\mathrm{reg}}(\mathcal{F})+1,\deg(f_{1}),\dots,\deg(f_{k})\\}.\qed$

In the next corollary, we provide an upper bound on the solving degree that is
linear in both the number of variables and the degree of the elements of the
system $\mathcal{F}$.

######  Corollary 3.12 (Macaulay bound).

Let
$\mathcal{F}=\\{f_{1},\dots,f_{k}\\}\subseteq\mathbb{K}[x_{1},\dots,x_{n}]$ be
a family of polynomial equations of degree at least $1$ such that
$\mathrm{d}_{\mathrm{reg}}(\mathcal{F})<\infty$ (and so $k\geq n$). Let
$d_{i}=\deg(f_{i})$ and suppose that $d_{1}\geq d_{2}\geq\dots\geq d_{k}$.
Then, for every degree-compatible term order $\sigma$

$\mathrm{sd}_{\sigma}(\mathcal{F})\leq d_{1}+\dots+d_{n}-n+2.$

###### Proof.

Since $\mathrm{d}_{\mathrm{reg}}(\mathcal{F})<\infty$, there exists
$J=\\{j_{1},\dots,j_{n}\\}\subseteq[k]$ such that
$\mathrm{d}_{\mathrm{reg}}(\mathcal{F})\leq d_{j_{1}}+\dots d_{j_{n}}-n+1$.
Since we assumed that $d_{1}\geq d_{2}\geq\dots\geq d_{k}$, we have that
$\mathrm{d}_{\mathrm{reg}}(\mathcal{F})\leq d_{1}+\dots d_{n}-n+1$. Moreover
for every $f\in\mathcal{F}$ we have that

$\deg(f)\leq d_{1}\leq d_{1}+(d_{2}-1)+\dots+(d_{n}-1)=d_{1}+\dots d_{n}-n+1.$

We conclude applying Proposition 3.10. ∎

The Macaulay bound was originally proved by Lazard in [13, Theorem 3] for the
maximum degree of an element of a reduced Gröbner basis of $\mathcal{F}$.
Notice that our bound (when it can be applied) is stronger. In fact, it
depends only on the degree of $n$ polynomials, while the bound of Lazard
depends on the degree of $n+1$ polynomials. A similar but weaker bound was
given in [4, Corollary 3.25].

We conclude with an explicit upper bound on the complexity of finding a
reduced Gröbner basis (with respect to a degree-compatible term order) of a
system of polynomial equations in terms of the degree of regularity. For
instance, this bound applies when we use algorithms such as MutantXL, MXL2,
and similar variants.

######  Proposition 3.13.

Let
$\mathcal{F}=\\{f_{1},\dots,f_{k}\\}\subseteq\mathbb{K}[x_{1},\dots,x_{n}]$ be
a family such that $\deg(f_{i})\leq\mathrm{d}_{\mathrm{reg}}(\mathcal{F})=d$.
Then, a Gröbner basis of $\mathcal{F}$ can be find in
$\mathcal{O}\left((n+1)^{4(d+1)}\right)$ operations in $\mathbb{K}$.

###### Proof.

Let $N=\binom{d+1+n}{d+1}$ be the number of monomials of degree at most
$d=\mathrm{d}_{\mathrm{reg}}(\mathcal{F})$. By Theorem 1.1, to construct a
Gröbner basis, it is sufficient to find a basis of $V_{\mathcal{F},d+1}$. In
order to do that we proceed as follows. With linear operations we can ensure
that $\mathrm{LT}(f_{i})\neq\mathrm{LT}(f_{j})$ for all $f_{i},f_{j}$. This is
equivalent to computing the reduced row echelon form of a matrix with $N$
columns and $N$ rows, which can be done in $\mathcal{O}(N^{3})$ operations in
$\mathbb{K}$. We set $\mathcal{B}=\mathcal{F}$ and
$\mathcal{M}=\\{mf_{i}:f_{i}\in\mathcal{F},\text{ m monomial of degree at
least 1, and }\deg(mf)\leq d+1\\}$. At each step, we pick an element $f$ of
$\mathcal{M}$, and with linear operations involving only multiple of elements
of $\mathcal{B}$ we reduce $f$ until we obtain an element $\bar{f}$ such that
either $\mathrm{LT}(\bar{f})=0$ or
$\mathrm{LT}(\bar{f})\notin\\{\mathrm{LT}(b):b\in\mathcal{B}\\}$. We remove
$f$ from $\mathcal{M}$. Then, if
$\mathrm{LT}(\bar{f})\notin\\{\mathrm{LT}(b):b\in\mathcal{B}\\}$, we add
$\bar{f}$ to $\mathcal{B}$ and we add to $\mathcal{M}$ all $m\bar{f}$ such
that $m$ is a monomial of degree at least $1$, and $\deg(m\bar{f})\leq d+1$.
This operation costs $\mathcal{O}(N^{2})$ operations. We repeat this operation
until either $\lvert\mathcal{B}\rvert=N$ or $\lvert\mathcal{M}\rvert=0$. Every
time that we add a new element to $\mathcal{B}$, we add at most $N$ elements
to $\mathcal{M}$. Since in $\mathcal{B}$ we can add at most $N$ elements, this
algorithm terminates in at most $N^{2}$ steps. The cost of each step is
$\mathcal{O}(N^{2})$, therefore we have that the a Gröbner basis of
$\mathcal{F}$ can be find in $\mathcal{O}(N^{4})$ operations. Since
$N\leq(n+1)^{d+1}$, we conclude. ∎

## Acknowledgement

The author is grateful to Elisa Gorla for her valuable suggestions.

## References

  * [1] Magali Bardet.  Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie.  PhD thesis, Université Paris VI, 2004.
  * [2] M. Bigdeli, E. De Negri, M. M. Dizdarevic, E. Gorla, R. Minko, and S. Tsakou.  Semi-regular sequences and other random systems of equations.  Cryptology ePrint Archive, Paper 2020/1375, 2020.  https://eprint.iacr.org/2020/1375.
  * [3] Johannes A. Buchmann, Jintai Ding, Mohamed Saied Emam Mohamed, and Wael Said Abd Elmageed Mohamed.  MutantXL: Solving Multivariate Polynomial Equations for Cryptanalysis.  In Helena Handschuh, Stefan Lucks, Bart Preneel, and Phillip Rogaway, editors, Symmetric Cryptography, volume 9031 of Dagstuhl Seminar Proceedings (DagSemProc), pages 1–7, Dagstuhl, Germany, 2009. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [4] Alessio Caminata and Elisa Gorla.  Solving multivariate polynomial systems and an invariant from commutative algebra.  In Jean Claude Bajard and Alev Topuzoğlu, editors, Arithmetic of Finite Fields, pages 3–36, Cham, 2021. Springer International Publishing.
  * [5] Alessio Caminata and Elisa Gorla.  Solving degree, last fall degree, and related invariants.  Journal of Symbolic Computation, 114:322–335, 2023.
  * [6] Nicolas T. Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir.  Efficient algorithms for solving overdefined systems of multivariate polynomial equations.  In International Conference on the Theory and Application of Cryptographic Techniques, 2000.
  * [7] Jean-Charles Faugère.  A new efficient algorithm for computing Gröbner bases (F4).  Journal of Pure and Applied Algebra, 139(1-3):61–88, June 1999\.
  * [8] 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, page 75–83, New York, NY, USA, 2002. Association for Computing Machinery.
  * [9] Jean-Charles Faugère, Magali Bardet, and Bruno Salvy.  On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations.  2004\.
  * [10] Elisa Gorla, Daniela Mueller, and Christophe Petit.  Stronger bounds on the cost of computing Gröbner bases for HFE systems.  Journal of Symbolic Computation, 109:386–398, 2022.
  * [11] Ming-Deh A. Huang, Michiel Kosters, Yun Yang, and Sze Ling Yeo.  On the last fall degree of zero-dimensional Weil descent systems.  Journal of Symbolic Computation, 87:207–226, 2018.
  * [12] Ming-Deh A. Huang, Michiel Kosters, and Sze Ling Yeo.  Last fall degree, HFE, and Weil descent attacks on ECDLP.  Cryptology ePrint Archive, Paper 2015/573, 2015.  https://eprint.iacr.org/2015/573.
  * [13] D. Lazard.  Gröbner bases, gaussian elimination and resolution of systems of algebraic equations.  In J. A. van Hulzen, editor, Computer Algebra, pages 146–156, Berlin, Heidelberg, 1983. Springer Berlin Heidelberg.
  * [14] Mohamed Saied Emam Mohamed, Wael Said Abd Elmageed Mohamed, Jintai Ding, and Johannes Buchmann.  MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy.  In Johannes Buchmann and Jintai Ding, editors, Post-Quantum Cryptography, pages 203–215, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
  * [15] Igor Semaev and Andrea Tenti.  Probabilistic analysis on macaulay matrices over finite fields and complexity of constructing gröbner bases.  Journal of Algebra, 565:651–674, 2021.
  * [16] Andrea Tenti.  Sufficiently overdetermined random polynomial systems behave like semiregular ones.  PhD thesis, University of Bergen, 2019.