Magali Bardet
email: magali.bardet@univ-rouen.fr

Jean-Charles Faugère

Bruno Salvy
email: bruno.salvy@inria.fr

On the complexity of the F5 Gröbner basis algorithm

Keywords: Gröbner bases, F 5 algorithm, Complexity, Regular Sequences, Noether Position

We study the complexity of Gröbner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system.

We give a bound on the number of polynomials of degree d in a Gröbner basis computed by Faugère's F 5 algorithm (2002) in this generic case for the grevlex ordering (which is also a bound on the number of polynomials for a reduced Gröbner basis, independently of the algorithm used). Next, we analyse more precisely the structure of the polynomials in the Gröbner bases with signatures that F 5 computes and use it to bound the complexity of the algorithm.

Our estimates show that the version of F 5 we analyse, which uses only standard Gaussian elimination techniques, outperforms row reduction of the Macaulay matrix with the best known algorithms for moderate degrees, and even for degrees up to the thousands if Strassen's multiplication is used. The degree being fixed, the factor of improvement grows exponentially with the number of variables.

Introduction

The complexity of Gröbner bases has been the object of extensive studies. It is well-known that in the worst-case, the complexity is doubly exponential in the number of variables. This is the result of a series of works both on lower bounds by [START_REF] Mayr | The complexity of the word problems for commutative semigroups and polynomial ideals[END_REF]; [START_REF] Huỳnh | A superexponential lower bound for Gröbner bases and Church-Rosser commutative Thue systems[END_REF] and on upper bounds, first in characteristic 0 by [START_REF] Giusti | Some effectivity problems in polynomial ideal theory[END_REF]; [START_REF] Möller | Upper and lower bounds for the degree of Groebner bases[END_REF] and then in positive characteristic by [START_REF] Dubé | The structure of polynomials ideals and Gröbner bases[END_REF].

These worst-case estimates have led to the unfortunately widespread belief that Gröbner bases are not a useful tool beyond toy examples. However, it has been observed for a long time that the actual behaviour of Gröbner bases implementations can be quite efficient. For instance, the matrix-F 5 algorithm that we analyse in this article, itself a downgraded version of Faugère's F 5 algorithm (2002) and a particular case of [START_REF] Faugère | Solving Systems of Polynomial Equations with Symmetries Using SAGBI-Gröbner Bases[END_REF], has given surprisingly good results on a cryptographic challenge (see [START_REF] Faugère | Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases[END_REF] where a set of 80 dense polynomials in 80 variables was solved by this algorithm). This motivates an investigation of the complexity of Gröbner basis algorithms for useful special classes of polynomial systems.

In this article, we concentrate on the important case of homogeneous systems. Any system can be brought into this form by adding a variable and homogenizing. It is classical that the computation of Gröbner bases can be performed by linear algebra on a large matrix that has been described precisely by [START_REF] Macaulay | On some formulae in elimination[END_REF]. The explicit relation with Gröbner bases can be found in the works of [START_REF] Lazard | Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations[END_REF] and [START_REF] Giusti | Some effectivity problems in polynomial ideal theory[END_REF][START_REF] Giusti | A note on the complexity of constructing standard bases[END_REF]. From there, a simple statement of a complexity bound is the following.

Proposition 1. Let ( f 1 , . . . , f m ) be a system of homogeneous polynomials in k[x 1 , . . . , x n ] with k an arbitrary field. The number of operations in k required to compute a Gröbner basis of the ideal I generated by ( f 1 , . . . , f m ) for a graded monomial ordering up to degree D is bounded by

O mD n + D -1 D ω , as D → ∞
where ω is the exponent of matrix multiplication over k.

The terminology and notations relative to Gröbner bases are recalled in Section 1, and we generally follow [START_REF] Cox | Ideals, Varieties, and Algorithms[END_REF]. The simple proof of this proposition is given in Section 1. For the notation ω and related notions, we refer to von zur [START_REF] Von Zur Gathen | Modern Computer Algebra, 2nd Edition[END_REF].

Getting a "small" bound on the highest degree of the elements of the Gröbner basis then leads to good complexity estimates. Such a bound is available for regular systems in the gradedreverse-lexicographical order (grevlex). In this situation, [START_REF] Lazard | Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations[END_REF] has shown that after a generic linear change of coordinates, a bound is given by the index of regularity of the ideal, which is itself bounded by Macaulay's bound:

i reg ≤ m ∑ i=1 (d i -1) + 1, (1)
where d i = deg( f i ). This bound is named after [START_REF] Macaulay | On some formulae in elimination[END_REF], who obtained it as an upper bound on the degree of intermediate polynomials used in the computation of a resultant of generic multivariate polynomials.

Taking m = n -ℓ (with ℓ ≥ 0) and injecting Macaulay's bound (1) into the upper bound of Proposition 1 leads to a general asymptotic bound for the number of operations:

δ δ (δ -1) δ -1 ω(n-ℓ) n 2-ω/2 (δ -1) δ 2π(δ -1) 3 ω/2 + O(1/n) , n → ∞, (2)
where δ , assumed to be larger than 1, is the arithmetic mean of the d i 's. (When δ = 1, the system is linear.) Thus in this case, we have a complexity which is simply exponential in the number of variables. Since in this case, if the field is algebraically closed, by Bézout's bound, the degree of the variety is also exponential, the result can be interpreted as a polynomial complexity in some size of the result. No change of variable is necessary when the dimension is 0. Otherwise, without a 2 generic linear change of coordinates, the bound does not hold in general, as observed by [START_REF] Möller | Upper and lower bounds for the degree of Groebner bases[END_REF]. These results can be made effective by a careful study of the required genericity condition. Indeed, [START_REF] Lejeune-Jalabert | Effectivité de calculs polynomiaux[END_REF] shows that a sufficient condition for the bound to hold is that the variables be in simultaneous Noether position with respect to the polynomial system. (The definition is recalled in Section 1). If the system is regular but the variables are not in simultaneous Noether position, and the field is sufficiently large, then a linear change of variables can be exhibited that puts the variables in this position. The complexity of actually finding such a linear change of variables in the worst case has been studied by Giusti (1988, §5.6) and later by [START_REF] Giusti | La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial[END_REF]. It is used as an ingredient to compute the dimension in small complexity [START_REF] Giusti | Computing the dimension of a projective variety: the projective Noether Maple package[END_REF]). The name "simultaneous Noether position" for this situation has been used at least since the work of [START_REF] Krick | A computational method for Diophantine approximation[END_REF].

This simply exponential behaviour being established, we are interested in sharpening the complexity estimates. This is important in order to compare various algorithms precisely, including approaches to polynomial system solving that do not use Gröbner bases, such as developed by [START_REF] Giusti | A Gröbner free alternative for polynomial system solving[END_REF]. We concentrate on systems with variables in simultaneous Noether position. This forms the basis for many other applications, either by changes of coordinates as we have just indicated, or by changes of order following [START_REF] Faugère | Efficient computation of zero-dimensional Gröbner bases by change of ordering[END_REF], or by other techniques as developed for instance by [START_REF] Lakshman | On the complexity of zero-dimensional algebraic systems[END_REF]; [START_REF] Lakshman | A single exponential bound on the complexity of computing Gröbner bases of zero-dimensional ideals[END_REF]; [START_REF] Hashemi | Sharper complexity bounds for zero-dimensional Gröbner bases and polynomial system solving[END_REF].

Most algorithmic variants of [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal[END_REF] algorithm spend part of their time computing reductions to 0, which is why many criteria and strategies have been developed over the years. An assessment of the efficiency of these strategies is obtained for instance by a comparison of their complexity for m = n -ℓ polynomials in n variables with the bound (2), for an arbitrary fixed ℓ ≥ 0. We obtain such a complexity estimate for a specific algorithm, namely Faugère's F 5 algorithm (2002). This algorithm has been the first one to introduce signatures in order to detect efficiently useless reductions to zero. Since then, many researchers have worked on understanding the new criteria behind F 5 , which has led to new variants of the signature-based approach. [START_REF] Eder | A survey on signature-based Gröbner basis computations[END_REF] give a detailed introduction to this topic. In Section 2, we present and analyse the matrix-F 5 version of the algorithm. A consequence of our results is the following estimate.

Theorem 2. Let ( f 1 , . . . , f m ) be a system of homogeneous polynomials of identical degree δ ≥ 2 in k[x 1 , . . . , x n ] with m = n -ℓ and ℓ ≥ 0, with respect to which (x 1 , . . . , x n ) are in simultaneous Noether position. Then the number of arithmetic operations in k required by Algorithm matrix-F 5 to compute a Gröbner basis for the grevlex order is bounded by a function of δ , ℓ, n that behaves asymptotically as

B(δ ) n n (A(δ , ℓ) + O(1/n)), n → ∞, (3)
when ℓ and δ are O(1). There, the coefficients B(δ ) and A(δ , ℓ) are given by

B(δ ) = λ 0 +1 λ 0 2δ -1 1 λ 2 0 -1 (λ 0 +1) 2 and A(δ , ℓ) = 1 -δ -1 2π • 1 + λ -1 0 3 -1 (1 + λ 0 ) 1+ℓ ,
λ 0 being the unique positive root between δ -1 2 and δ -1 of

λ + 1 λ 2δ = 1 1 -δ (λ +1) 2 -λ 2 (λ +1) 3 -λ 3
.

Moreover, the dominant term B(δ ) is bounded between δ 3 and 3δ 3 .

Explicit values of this bound (3), called the F 5 -bound, are given in Table 1. We now draw a few consequences of this theorem.

δ 2 3 4 5 6 7 8 B(δ ) n 2 4.29 n 2 6.16 n 2 7.44 n 2 8.43 n 2 9.23 n 2 9.90 n 2 10.5 n = (2 n ) 4.3 (3 n ) 3.9 (4 n ) 3.7 (5 n ) 3.6 (6 n ) 3.6 (7 n ) 3.5 (8 n ) 3.5 = (2.5) n 2 3n (2.7) n 3 3n (2.7) n 4 3n (2.8) n 5 3n (2.8) n 6 3n (2.8) n 7 3n (2.8) n 8 3n
Numerical estimates. In view of (2), B(δ ) can be compared to δ δ /(δ -1) δ -1 ω where ω is the exponent of matrix multiplication over k, and therefore our result can be interpreted as a first measure of the extent to which the F 5 algorithm exploits the structure of the Macaulay matrix for the computation. In Figure 1, we display the values of B(δ ) as well as the arithmetic complexity of the linear algebra performed on the Macaulay matrix for different values of the exponent ω. The first plot gives these values for δ from 2 to 10, and the second one gives the logarithm of these values in terms of log(δ ), for δ from 2 1 to 2 14 = 16384. For 2 ≤ δ < 7, the F 5 -bound gives a better complexity than the [START_REF] Coppersmith | Matrix multiplication via arithmetic progressions[END_REF] bound ω < 2.376 and the recently improved bounds down to ω < 2.373 by [START_REF] Stothers | On the complexity of matrix multiplication[END_REF][START_REF] Vassilevska Williams | Multiplying matrices faster than Coppersmith-Winograd[END_REF] and Le [START_REF] Gall | Powers of tensors and fast matrix multiplication[END_REF]. It is better than Strassen's bound ω = log 2 7 for 2 ≤ δ < 9911. Thus in practice, for this whole range of degrees, the complexity estimate of F 5 behaves asymptotically (wrt to n) exponentially better than linear algebra with fast matrix multiplication over the Macaulay matrix.

Nonhomogeneous systems. In the affine case, Theorem 2 can often be applied with ℓ = 1: let ( f 1 , . . . , f n ) be a system of affine polynomials of identical degree δ ≥ 2 in k[x 1 , . . . , x n ]; we consider (H 1 , . . . , H n ) the polynomials obtained by homogenizing the f i in k[x 1 , . . . , x n , h]. Provided x 1 , . . . , x n , h are in simultaneous Noether position with respect to the system (H 1 , . . . , H n ) (or equivalently, x 1 , . . . , x n are in simultaneous Noether position with respect to the system formed by the homogeneous part of highest degree of the f i ), we can then apply the theorem to (H 1 , . . . , H n ) and derive a bound on the number of operations.

Other term orders. Under the same hypotheses as in Theorem 2, the computation of a Gröbner basis for the lexicographical order can be achieved by first computing a Gröbner basis for the grevlex order using Algorithm matrix-F 5 in O(nB n ) operations and then converting into a basis for the lexicographical order using the FGLM algorithm of [START_REF] Faugère | Efficient computation of zero-dimensional Gröbner bases by change of ordering[END_REF] in O(nδ 3n ) operations. Since B ≥ δ 3 , the overall complexity is still bounded by O(nB n ) arithmetic operations over k. System solving. If the field k is infinite and the system is regular, a generic linear change of variables puts the variables in simultaneous Noether position. The construction is given for instance by Giusti (1988, §5.6), see also [START_REF] Giusti | La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial[END_REF]. Thus in practice, for zerodimensional polynomial system solving, the simultaneous Noether position hypothesis can be replaced by the regularity of the system. This article is structured as follows. In Section 1, we recall the basic definitions and properties of regular sequences and Gröbner bases, the relation between Gröbner bases and linear algebra and the definition of simultaneous Noether position. In Section 2, we give a simple version of the F 5 algorithm and we give a structure theorem for Gröbner bases computed by this signaturebased algorithm. In Section 3 we describe more precisely its behaviour for systems with variables in simultaneous Noether position for the grevlex ordering and deduce an upper bound for the complexity of F 5 in this case. Finally, in Section 4 we discuss the practical accuracy of the bounds we provide in this paper. In view of our numerical experiments, the practical behaviour of the algorithm F 5 seems to be asymptotically exponentially better than our bound. A characterisation of the exact exponent in the complexity is still open.

Preliminary versions of this work have appeared in Bardet's PhD thesis (2004).

Gröbner Bases and Regularity

This section gathers classical definitions and properties, so that this article is self-contained. We generally follow the terminology and notations of [START_REF] Cox | Ideals, Varieties, and Algorithms[END_REF].

Basic Notation and Definitions

The polynomial systems we consider are always denoted

( f 1 , . . . , f m ) ∈ k[x 1 , . . . , x n ]
where k is a field. We denote by d i the degree of f i . Throughout this article, the polynomials are homogenous. The set of homogeneous polynomials of degree d is denoted k[x 1 , . . . , x n ] d . We use T i to denote the set of nonzero monomials in x 1 , . . . , x i (i.e., products x α 1 1 • • • x α i i with nonnegative integer exponents α j ), and T i d the subset of monomials of degree d. When i = n, we use simply T = T n and T d = T n d . The ideal generated by the polynomial system is denoted I = f 1 , . . . , f m and the vector space of homogeneous polynomials of degree d in I is denoted I d .

A monomial ordering is a total order on monomials that is compatible with the product and such that every nonempty set has a smallest element for the order. Such an ordering is graded if monomials of different degrees are ordered according to their degree. The leading term LT( f ) of a polynomial f is the term (i.e., monomial multiplied by a nonzero constant in k) corresponding to its largest monomial for the given monomial ordering.

The grevlex ordering is a graded ordering. The order between two monomials of the same degree

x α = x α 1 1 • • • x α n n and x β = x β 1 1 • • • x β n
n is given by x α ≻ x β when the last nonzero element of (α 1β 1 , . . . , α nβ n ) is negative. Thus, among the monomials of degree d, the order is

x d 1 ≻ x d-1 1 x 2 ≻ x d-2 1 x 2 2 ≻ • • • ≻ x d 2 ≻ x d-1 1 x 3 ≻ x d-2 1 x 2 x 3 ≻ x d-2 1 x 2 3 ≻ • • • ≻ x d n .
A Gröbner basis of an ideal I for a given monomial ordering is a set G of generators of I such that the leading terms of G generate the monomial ideal LT(I ) , which is the ideal generated by the monomials LT( f ), f ∈ I . A polynomial is reduced with respect to the Gröbner basis G when its leading term is not a multiple of those of G. The basis is reduced if each element g ∈ G is reduced with respect to G \ {g}.

Macaulay's Matrix

We recall briefly the construction of this matrix and the explicit relation with Gröbner bases, which can be found in the works by [START_REF] Lazard | Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations[END_REF] and [START_REF] Giusti | Some effectivity problems in polynomial ideal theory[END_REF][START_REF] Giusti | A note on the complexity of constructing standard bases[END_REF]. There are several advantages to this point of view: one is that, for a graded order, it gives an easy access to the Hilbert function of the ideal, another one is that upper bounds on the complexity are easily recovered from classical linear algebra.

For a given degree d and polynomial system ( f 1 , . . . , f m ), Macaulay's matrix M d,m has its columns indexed by the monomials of T d . For each polynomial f i of the system and each monomial t ∈ T d-d i , it contains one row whose entry in the column indexed by a monomial t ′ is the coefficient of t ′ in t f i . Thus, the rows of this matrix generate the vector space I d . The Hilbert function is defined by

HF I (d) = dim k[x 1 , . . . , x n ] d /I d , it is therefore equal to the dimension n+d-1 d of k[x 1 , . . . , x n ] d minus the rank of M d,m . For d large enough,

Gröbner Bases

Performing a Gaussian elimination on the matrix M d,m computes a basis of I d . If moreover, the columns are ordered by decreasing order with respect to the chosen graded monomial ordering, and column pivoting is not allowed, then the leading terms of this basis give LT(I d ). From these bases for min(d 1 , . . . , d m ) ≤ d ≤ D, where D is the maximal degree of the elements in the reduced Gröbner basis of I , this Gröbner basis can be reconstructed. This way, the computation is reduced to linear algebra operations.

From there we now prove the general upper bound on the complexity that has been given in Proposition 1.

Macaulay's matrix

M d,m has C d = |T d | = n+d-1 d columns and R d = |T d-d 1 | + • • •+ |T d-d m | rows.
A basis of its rows is obtained by the computation of a reduced row echelon form. [START_REF] Storjohann | Algorithms for matrix canonical forms[END_REF] has shown that fast matrix multiplication can be used to compute this form with a complexity of O(R d C d r ω-2 ), where r is the rank of the matrix. Thus, this is bounded by

O(R d C ω-1 d ).
The computation is performed for d = min(d 1 , . . . , d m ), . . . , D. The number of rows is bounded by mC d and C d is an increasing sequence, so that the conclusion of Proposition 1 follows.

The remaining problems are to bound D and to perform this Gaussian elimination efficiently by taking the structure of the matrix into account. An important class where this can be done is the class of regular systems.

Regular Systems

Definition 1. ( f 1 , . . . , f m ) is regular if for all i = 1, . . . , m, f i is not a zero-divisor in the quotient ring k[x 1 , . . . , x n ]/ f 1 , . . . , f i-1 . In other words if there exists g such that g f i ∈ f 1 , . . . , f i-1 then g belongs to f 1 , . . . , f i-1 .
The following Lemma gives a characterisation of zero-divisors for homogeneous polynomials:

Lemma 3. Let I ⊂ k[x 1 , . . . , x n ] be an homogeneous ideal, I = 1 , and f ∈ k[x 1 , . . . , x n ] homogeneous of degree δ ≥ 1. Then f is not a zero-divisor in k[x 1 , . . . , x n ]/I if and only if H I + f (z) = (1 -z δ ) H I (z).
Proof. The proof boils down to using the relation between the dimensions of the kernel K d and image of the application of multiplication by

f from k[x 1 , . . . , x n ] d-δ /I d-δ to k[x 1 , . . . , x n ] d /I d . This gives HF I + f (d) = HF I (d) -HF I (d -δ ) + dim(K d ), d ∈ N. (4)
(with the convention HF(-d) = 0 for d ≥ 1). Multiplying (4) by z d and summing over d leads to

H I + f (z) = (1 -z δ )H I (z) + ∑ d≥0 dim(K d )z d .
The equivalence results from the definition:

f is not a zero-divisor in k[x 1 , . . . , x n ]/I if and only if dim(K d ) = 0 for all d ≥ 0.
This leads to a classical property of regular systems, essentially due to Macaulay (1916, §58):

Proposition 4. The system of homogeneous polynomials ( f 1 , . . . , f m ) ⊂ k[x 1 , . . .

, x n ] is regular if and only if its Hilbert series is

H I (z) = Π m j=1 (1 -z d j ) (1 -z) n . ( 5
)
If m = n, then the sequence ( f 1 , . . . , f n ) is regular if and only if its Hilbert series is a polynomial.

Proof. The first part follows from the previous lemma and H (z) = (1z) -n that counts the number of homogeneous monomials.

For m = n, if H I (z) is a polynomial, then Bézout's bound (Cox et al., 2005, ch. 3 §5) states that H I (1), which is the number of solutions of I in the algebraic closure of k, is bounded by

Π n j=1 d j . But Equation (4) leads to H I (z) ≥ ∏ n j=1 (1 -z d j )/(1 -z) n
with inequality coefficient by coefficient. By taking the value at z = 1, we get ∏ n j=1 d j ≥ H I (1) ≥ ∏ n j=1 d j , which proves the equality. As each coefficient of the Hilbert series is nonnegative, we deduce that H

I (z) = ∏ n j=1 (1 -z d j )/(1 -z) n
and the sequence is regular by the first part of the lemma.

Corollary 5. Let ( f 1 , . . . , f n ) be a regular system of homogeneous polynomials in k[x 1 , . . . , x n ],
then the highest degree in the elements of a Gröbner basis for a graded ordering is bounded by Macaulay's bound (1).

Proof. When m = n, the Hilbert series ( 5) is a polynomial, whose degree D is one less than the bound (1). This implies that the Hilbert function is 0 for degree D. In other words all the monomials of T D belong to I D , whence the result.

Example 1. The system

   f 1 = x 2 + y 2 -2xz -2yz + z 2 + h 2 f 2 = x 2 + xy + yz -z 2 -2h 2 f 3 = x 2 -y 2 + 2yz -2z 2 (6) in k[x, y, z, h],
represents, for h = 0, the intersection of a projective circle and two hyperbolas over k = R. The coefficient of h 2 is chosen so that the point (1, 1, 1, 1) is a solution of the system. The Hilbert series of the systems ( f 1 , f 2 ) and ( f 1 , f 2 , f 3 ) (computed from a Gröbner Basis for a grevlex ordering) are respectively 4 , showing that these systems are regular.

H ( f 1 , f 2 ) (t) = (1 + t) 2 /(1 -t) 2 = (1 -t 2 ) 2 /(1 -t) 4 and H ( f 1 , f 2 , f 3 ) (t) = (1 + t) 3 /(1 -t) = (1 -t 2 ) 3 /(1 -t)

Noether position

Definition 2. The variables (x 1 , . . . , x m ) are in Noether position with respect to the system

( f 1 , . . . , f m ) if their canonical images in k[x 1 , . . . , x n ]/ f 1 , . . . , f m are algebraic integers over k[x m+1 , . . . , x n ] and moreover k[x m+1 , . . . , x n ] ∩ f 1 , . . . , f m = 0 . The variable x i ∈ k[x 1 , . . . , x n ]/ f 1 , . . . , f m is an algebraic integer over k[x m+1 , . . . ,
x n ] when there exists a polynomial g ∈ k[x i , x m+1 , . . . , x n ] ∩ f 1 , . . . , f m that is monic with respect to x i . A Gröbner basis of f 1 , . . . , f m for an elimination monomial ordering such that {x j , 1 ≤ j = i ≤ m} > {x i , x m+1 , . . . , x n } contains such a g (up to a constant) if and only if x i has the desired property.

Example 2. The variables (x, y) are in Noether position with respect to the system ( f 1 , f 2 ) from Example 1. Indeed, a Gröbner basis of the system for the lexicographical ordering

x > y > z > h (resp. y > x > z > h) contains the polynomial 2 y 4 -6 y 3 z + 12 y 2 z 2 + 7 y 2 h 2 -8 yz 3 -20 yzh 2 + 4 z 2 h 2 + 9 h 4 (resp. 2 x 4 + 2 x 3 z -2 x 2 z 2 -3 x 2 h 2 -2 xz 3 -2 xzh 2 + z 2 h 2 + 4 h 4 ).
On the other hand, the variables (y, z) are not in Noether position with respect to the system ( f 1 , f 2 ). Again, a Gröbner basis computation for the lexicographical ordering shows that

I ∩ k[y, x, h] = 2 y 3 x + 4 y 2 x 2 -y 2 h 2 + 8 yx 3 -8 yxh 2 -4 x 2 h 2 -h 4 .
Geometrically, the Noether position implies that the algebraic set defined by the system has dimension nm and, in an algebraic closure of k, for any value of (x m+1 , . . . , x n ), the system has exactly the same number of solutions (counting multiplicity). In a sufficiently large field, for regular systems, the variables can be put in Noether position by a generic linear change of variables, as explained by [START_REF] Giusti | Combinatorial dimension theory of algebraic varieties[END_REF].

The following proposition characterises algebraically the Noether position property for homogeneous ideals. It shows that in this case, this position is also equivalent to the condition that the system ( f 1 , . . . , f m , x m+1 , . . . , x n ) has only the solution {0}.

Proposition 6 (Lejeune-Jalabert, 1984). Let ( f 1 , . . . , f m ) be a system of homogeneous polynomials of k[x 1 , . . . , x n ], such that f 1 , . . . , f m = 1 . If the variables (x 1 , . . . , x m ) are in Noether position with respect to the system ( f 1 , . . . , f m ), then the sequence ( f 1 , . . . , f m , x m+1 , . . . , x n ) is regular.

Proof. The variables (x 1 , . . . , x m ) being in Noether position with respect to the system ( f 1 , . . . , f m ),

for each 1 ≤ i ≤ m, there exists a polynomial g ∈ k[x i , x m+1 , . . . , x n ] ∩ f 1 , . . . , f m of degree n i ≥ 1 in x i such that the coefficient of x n i i in g is 1.
This implies that the Hilbert series

H ( f 1 ,..., f m ,x m+1 ,...,x n ) (z) is a polynomial. Then by Proposition 4, ( f 1 , . . . , f m , x m+1 , . . . , x n ) is a reg- ular sequence.
From the computational point of view, the following proposition gives very precise information on the structure of a grevlex Gröbner basis, it plays an important role in obtaining good complexity estimates in the next section.

Proposition 7 (Lejeune-Jalabert, 1984, Ch. 3, Prop. 3.4). Let (x 1 , . . . , x m ) be in Noether position with respect to the homogeneous system ( f 1 , . . . , f m ). Let θ m be a ring endomorphism of k[x 1 , . . . , x n ] such that θ m (x i ) = x i for i ∈ {1, . . . , m}, while θ m (x i ) = 0 for i > m. Then, for the grevlex monomial ordering

LT( f 1 , . . . , f m ) = LT(θ m ( f 1 , . . . , f m )) • x m+1 , . . . , x n .
In other words, the leading terms of the elements of the reduced Gröbner basis do not depend on the variables (x m+1 , . . . , x n ).

Proof. Let I = f 1 , . . . , f m . The inclusion LT(I ) ⊃ LT(θ m (I )) • x m+1 , . . . , x n follows from the fact that for the grevlex monomial ordering, when

θ m ( f ) = 0, LT( f ) = LT(θ m ( f )).
Conversely let f ∈ I and let M = x α 1 1 • • • x α n n be its leading monomial for the grevlex ordering. We have to prove that there exists g ∈ I with leading monomial

x α 1 1 • • • x α m m .
Since the ideal is homogeneous, we can assume f to be homogeneous as well. Let l be the largest index such that x l |M. By definition of the grevlex ordering and the fact that M is the leading monomial of f , there exist homogeneous polynomials g l , . . . ,

g n ∈ k[x 1 , . . . , x n ] such that f = x α l l g l + x l+1 g l+1 + • • • + x n g n , g l ∈ k[x 1 , . . . , x l ]\{0} and LT(g l ) = x α 1 1 • • • x α l-1 l-1 . (7)
By Proposition 6, the sequence

( f 1 , . . . , f m , x m+1 , . . . , x n ) is regular. If l > m, then f ≡ x α l
l g l ≡ 0 mod I + x l+1 , . . . , x n and since from Proposition 4 x l is not a zero-divisor in k[x 1 , . . . , x n ]/(I + x l+1 , . . . , x n ) we deduce successively that g l ≡ 0 mod I + x l+1 , . . . , x n and g l ≡ 0 mod I . Hence, starting from

f ∈ I such that LT( f ) ∈ k[x 1 , . . . , x l ] with l > m, we obtain g l ∈ I such that LT( f ) = x α l l LT(g l ) and LT(g l ) ∈ k[x 1 , . . . , x l-1 ]. By induction on l we can find a polynomial g ∈ I such that LT( f ) = x α m+1 m+1 • • • x α l l LT(g) and LT(g) ∈ k[x 1 , . . . , x m ]
. This proves the converse inclusion.

In view of the incremental nature of the F 5 algorithm, an even stronger property will be useful in our considerations.

Definition 3. The variables (x 1 , . . . , x n ) are in simultaneous Noether position with respect to the system ( f 1 , . . . , f m ) when the variables (x 1 , . . . , x i ) are in Noether position with respect to ( f 1 , . . . , f i ) for all i ∈ {1, . . . , m}.

Example 3. The variables (x, y, z, h) in Example 1 are in simultaneous Noether position with respect to the system ( f 1 , f 2 , f 3 ) from Equation (6).

Again, this situation is generic for regular systems and can be reached by a linear change of coordinates if the field is sufficiently large.

2. Signature-based Gröbner basis computations: the F 5 Algorithm

Description of the Matrix-F 5 algorithm

Faugère's ( 2002) F 5 algorithm is designed so that it ensures that no "useless" reduction to 0 is performed when the input system is regular. We now describe a matrix version of F 5 that is well-suited to a complexity analysis. The main difference with the original algorithm is that the maximal degree occurring in the computation is given as an input of the algorithm. As in Faugère's F 4 algorithm (1999), linear algebra is used to reduce the polynomials. The resulting algorithm is very easy to implement. It is probably somewhat less efficient than the original F 5 on most practical examples, but it lets us compute an upper bound on the complexity of F 5 . It is this matrix variant that was used with success by [START_REF] Faugère | Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases[END_REF].

In order to keep track of the polynomials that lead to the different rows of the matrices encountered during the algorithm, it is convenient to view a matrix (M) as a map (s,t) ∈ S × T → M s,t ∈ k where S is a finite subset of N × T and T a finite subset of T ordered using a graded ordering. A row indexed by s = (i, τ) will be used to represent a polynomial obtained as the sum of τ f i and some other "smaller" polynomials in I ; this index s is the signature of the corresponding polynomial. A row in the matrix M is specified by its signature s, and we identify the vector Row(M, s) = [M s,t |t ∈ T ] and the polynomial ∑ t∈T M s,t t; the leading term of a row is the leading term of the corresponding polynomial. We fix the following notation: Rows(M) = S and LT(M) is the set of leading terms of all the rows of M. A valid elementary row operation on M consists in replacing the row s ∈ S by the linear combination Row(M, s) ← Row(M, s) + λ Row(M, s ′ ) where λ ∈ k, s ′ ∈ S and the additional condition that s ′ = ( j ′ , u ′ ) < s = ( j, u) (i.e., j ′ < j or ( j = j ′ and u ′ ≺ u)). The index of the line is unchanged. We denote by Md,i the result of Gaussian elimination applied to the matrix M d,i using a sequence of valid elementary row operations.

There are two distinct ways of performing a valid Gaussian elimination: either we perform reductions only for the leading term of each row, in which case we call the reduction a topreduction, or we perform more valid reductions so that each column containing a leading coefficient has zeros elsewhere below, in which case we call the reduction a full-reduction. The complexity analysis of this paper is done in the top-reduction case, and in Section 4 an experimental comparison with the full-reduction case is given.

The algorithm matrix-F 5 constructs matrices incrementally in the degree and the number of polynomials. Let d be the current degree and i the current number of polynomials (in other words we are computing a Gröbner basis of f 1 , . . . , f i truncated in degree d). The algorithm constructs a matrix M d,i obtained from the Macaulay matrix M d,i by removing selected rows. With the previous notation, M d,i is a map S × T d → k such that S is a subset of {1, . . . , i} × T . [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5 )[END_REF] defines the signature of a polynomial and uses it to give a new criterion to remove useless computations. In the matrix-F 5 algorithm the signatures become the indices of the rows and the original criterion translates as: Proposition 8 (F 5 criterion). If t is the leading term of Row( Md-d i ,i-1 , s) where s < (i, 1) then the row indexed by (i,t) belongs to the vector space generated by the rows of M d,i having smaller index.

Proof. The hypothesis is that t ∈ LT( f 1 , . . . ,

f i-1 d-d i ), say t = LT(h) with h = ∑ i-1 k=1 h k f k . This implies that t f i = ∑ i-1 k=1 f i h k f k + (t -h) f i ,
where the first term belongs to Row M d,i-1 and the last one is a linear combination of rows of M d,i having smaller index, as LT(th) ≺ LT(h).

We now describe the matrix-F 5 algorithm. Here the order is any monomial ordering. It enters the algorithm through the function LT.

Algorithm matrix-F 5

Input: homogeneous polynomials ( f 1 , . . . , f m ) with degrees

d 1 ≤ • • • ≤ d m ;
a maximal degree D. Output: The elements of degree at most D of the reduced Gröbner bases of ( f 1 , . . . , f i ), for i = 1, . . . , m.

1.

for i from 1 to n do G i := / 0; end for // initialise the Gröbner Bases G i of ( f 1 , . . . , f i ).

2.

for d from d 1 to D do 3.

M d,0 := / 0, Md,0 := / 0 4.

for i from 1 to m do 5.

if d < d i then M d,i := M d,i-1 6. else if d = d i then 7.
M d i ,i := add the new row f i to Md i ,i-1 with index (i, 1) 8.

else 9.

M d,i := Md,i-1 10.

Crit := LT( Md-d i ,i-1 )

11.

for

f in Rows(M d-1,i )\ Rows(M d-1,i-1 ) do 12. (i, u) := index( f ), with u = x j 1 • • • x j d-d i -1 , 13. and 1 ≤ j 1 ≤ • • • ≤ j d-d i -1 ≤ n 14.
for j from j d-d i -1 to n do 15.

if ux j ∈ Crit then 16.

add the new row x j f with index (i, ux j ) in M d,i Add to G i all rows of Md,i not reducible by LT(G i )

23.

end for

24.

end for

25. return [G i | i = 1, . . . , m]
The for loop of line 14 constructs the matrix M d,i containing all the polynomials

x α 1 1 • • • x α n n f i with α 1 + • • • + α n = d -d i (except
some that reduce trivially to zero). In order to avoid redundant computations, these are constructed from the rows of the previous matrix M d-1,i by multiplying all rows by all variables. A row indexed by (i,

x α 1 1 • • • x α j j
) with α j = 0 can arise from several rows in M d-1,i , we choose to construct it from the row indexed by

(i, u) in M d-1,i with u = x α 1 1 • • • x α j -1 j
and multiply it by x j , the largest variable occurring in u. This insures that every row comes from exactly one row in the previous matrix.

Example 4. Algorithm matrix-F 5 over Example 1 constructs the following matrices. In degree 2,

M 2,3 =   x 2 xy y 2 xz yz z 2 hx yh zh h 2 f 1 1 1 -2 -2 1 1 f 2 1 1 1 -1 -2 f 3 1 -1 2 -2   ,
where only nonzero entries are displayed. Gaussian reduction yields

M2,3 =   x 2 xy y 2 xz yz z 2 hx yh zh h 2 f 1 1 1 -2 -2 1 1 f 2 1 -1 2 3 -2 -3 f 3 2 -2 -4 3 1   .
From M2,3 , it follows that the indices and leading terms of the elements in G 3 are {((1, 1), x 2 ), ((2, 1), xy), ((3, 1), y 2 )}.

Next, in degree 3, M3,3 contains (in that order) the columns x 3 , x 2 y, y 2 x, y 3 , x 2 z, zxy, zy 2 , xz 2 , yz 2 , z 3 , x 2 h, xyh, y 2 h, xzh, yzh, z 2 h, h 2 x, h 2 y, h 2 z, h 3 and the rows with indices and leading terms

(ind.) (1, h) (1, z) (1, y) (1, x) (2, h) (2, z) (2, y) (2, x) (3, h) (3, z) (3, y) (3, x) (LT) x 2 h x 2 z x 2 y x 3 xyh xyz xy 2 y 3 y 2 h y 2 z xz 2 yz 2
The underlined leading terms are those inserted into G 3 by Algorithm matrix-F 5 in line (22). Degree 4 is the first time the F 5 criterion is used. The set Crit of line (10) is empty for i = 1 by convention, but it contains x 2 for i = 2 and x 2 , xy for i = 3. Thus in line (16), all rows (i, m) with i = 1, 2, 3 and m a monomial of degree 2 are added to M 4,2 and M 4,3 , except the rows (2, x 2 ), (3, xy) and (3, x 2 ). The matrix M4,3 contains 7 4 = 35 columns and 3 5 2 -3 = 27 rows. The rows that are reduced during the Gaussian elimination and that are added to the Gröbner basis are ((3, y 2 ), z 4 ). No reduction to 0 has occurred and the Gröbner bases are

G 1 = {((1, 1), x 2 + y 2 -2xz -2yz + z 2 + h 2 )}, G 2 = G 1 ∪ ((2, 1), xy -y 2 + 2 xz + 3 yz -2 z 2 -3 h 2 ) ((2, x), 2 y 3 -7 xyz -3 y 2 z -2 xz 2 -yz 2 + 2 z 3 + 3 xh 2 + 4 yh 2 + 2 zh 2 ) , G 3 = G 2 ∪        ((3, 1), 2 y 2 -2 xz -4 yz + 3 z 2 + h 2 ) ((3, y), 4 xz 2 + 3 yz 2 -2 z 3 + 3 xh 2 + 3 yh 2 -11 zh 2 ) ((3, x), 3 yz 2 -6 z 3 + 11 xh 2 -5 yh 2 -3 zh 2 ) ((3, y 2 ), 3 z 4 + 4 xzh 2 + 12 yzh 2 -7 z 2 h 2 -12 h 4 )       
.

The main property of this algorithm is given in the following theorem.

Theorem 9. The algorithm matrix-F 5 computes the elements of degree at most D of the reduced Gröbner bases of f 1 , . . . , f i , i = 1, . . . , m. Moreover if ( f 1 , . . . , f m ) is a regular sequence then all the matrices M d,i have full rank.

Proof. The proof of the first statement follows the algorithm: it is an induction on d and i.

For d = d 1 and i = 1, the result is clear. Assuming the induction hypothesis, we now have to prove that the rows of M d,i generate f 1 , . . . , f i d . Then we can deduce that LT( Md,i ) generates LT( f 1 , . . . , f i d ) and the conclusion on G i follows.

It is thus sufficient to show that for any τ ∈ T d-d i , the polynomial τ f i is generated by the rows of M d,i . If d ≤ d i the result is clear. Otherwise, let j be the highest index such that x j | τ and let u = τ/x j . If u is not the index of a row of M d-1,i \ M d-1,i-1 then by the induction hypothesis u f i is generated by the rows of M d-1,i-1 and therefore τ f i is generated by the rows of M d,i-1 . This justifies the selection of rows in the loop over s. Otherwise, τ f i is entered by the algorithm in M d,i , unless τ ∈ LT( Md-d i ,i-1 ) since then τ is eliminated by the criterion, thanks to Proposition 8.

The second part of the theorem is proved by contradiction. If a row of M d,i indexed by (i, u) reduces to 0, this means that the algorithm has constructed an identity

g i f i + • • • + g 1 f 1 = 0.
Moreover, the criterion ensures that g i = 0 is reduced with respect to f 1 , . . . , f i-1 . This contradicts the regularity of ( f 1 , . . . , f i ).

Other useful properties of the algorithm matrix-F 5 that are needed later are gathered in the following Lemma.

Lemma 10.

1. Any row entered by the algorithm matrix-F 5 into the matrix M d,i represents a polynomial

g i f i + • • • + g 1 f 1 ,
where g i is reduced with respect to f 1 , . . . , f i-1 ; 2. if g ∈ G i \ G i-1 , then its index s g has the form (i,t).

Proof. The first property comes from the proof of the previous theorem. The second one comes from the fact that the algorithm works incrementally with respect to i.

Structure theorem for Grevlex Bases with variables in Simultaneous Noether Position

The estimate in Proposition 1 describes precisely the shape of the final Gröbner basis, but it does not take into account any specificity of the F 5 algorithm. Hence we first study in more detail the structure of grevlex bases computed by F 5 , giving the shape of the signatures associated to those polynomials. We further restrict to a special situation, namely when the variables are in simultaneous Noether position. The following proposition will play a crucial role when estimating precisely the number of operations of the matrix-F 5 algorithm.

Proposition 11. [Structure of the F 5 -bases] Let ( f 1 , . . . , f m ) be a homogeneous system for which the variables (x 1 , . . . , x n ) are in simultaneous Noether position. Let G 1 , . . . , G m be the result of the matrix-F 5 algorithm applied to this system for the grevlex ordering. Then, for all (( j,t), g) ∈ G i , one has j ≤ i, LT(g) ∈ T j and t ∈ T j-1 . Proof. That j ≤ i is a consequence of the incremental nature of the algorithm. Also, since reductions do not change the index and only involve rows with smaller indices, one has that if (( j,t), g) ∈ G i , then (( j,t), g) ∈ G j . Thus by induction it is sufficient to consider ((i,t), g). The result on LT(g) is given by Proposition 7 using the simultaneous Noether position hypothesis.

The property that t ∈ T i-1 is more deeply related to the way the algorithm F 5 works. We prove it by induction on i and on the degree of t. For i = 1, the only element of the basis is ((1, 1), f 1 ); it satisfies the property. Let now i > 1 and t = 1. We decompose t as t = Xu, where X = 1 is of minimal degree such that, for some polynomial h, ((i, u), h) ∈ G i . Let ((i, u 1 ), g 1 ), . . . , ((i, u s ), g s ) be the elements of G i distinct from h coming from rows with indices smaller than (i,t) (i.e., u j < t). Following Algorithm F 5 , the polynomial g is obtained from Xh by reductions in the matrix by h and the g j 's, and LT(Xh) ≥ LT(g). From line 22 in Algorithm matrix-F 5 we see that LT(Xh) > LT(g), so by definition of h there exists an index k and a monomial µ with µ LT(g k ) = X LT(h).

By the minimality of X, we have that X | LT(g k ). Since g k ∈ G i , by Proposition 7 this implies X ∈ T i and then also µ ∈ T i . We prove by contradiction that x i ∤ X. Again by the minimality of X, if x i | X, then x i ∤ µ and therefore x i | LT(g k ) and µ ∈ T i-1 . By induction there exists a monomial τ ∈ T i-1 such that g k has index (i, τ). Now we have that ((i, Xu), g) is reduced by a row indexed (i, µτ) but this is a contradiction since µτ ∈ T i-1 is such that µτ ≻ Xu for the order grevlex and this would not be a valid row reduction.

Complexity Analysis of F 5

Number of Polynomials

The following theorem gives quantitative information on the structure of a reduced Gröbner basis (which is independent of the algorithm used to compute it). To the best of our knowledge, it has not been given before.

Theorem 12. Let ( f 1 , . . . , f m ) be a homogeneous system for which the variables (x 1 , . . . , x n ) are in simultaneous Noether position, with

d 1 = deg( f 1 ) ≤ • • • ≤ d m = deg( f m ).
Let G i be a reduced Gröbner basis of ( f 1 , . . . , f i ) for the grevlex monomial ordering for 1 ≤ i ≤ m. Then the number of polynomials of degree d in G i whose leading term does not belong to LT(G i-1 ) is bounded by b

(i) d , where B i (z) = ∞ ∑ d=0 b (i) d z d = z d i i-1 ∏ k=1 1 -z d k 1 -z . ( 8
)
For fixed i, let D i = (d 1 -1) + • • • + (d i-1 -1). Then the sequence h d = b (i) d+d i , 0 ≤ d ≤ D i is positive, symmetric (h D i -d = h d ), unimodal (h 0 ≤ • • • ≤ h ⌊D i /2⌋ ≥ • • • ≥ h D i ) and log-concave (h 2 d ≥ h d-1 h d+1 ). Example 5. In Example 4, the series B 3 (z) = z 2 (1 + z) 2 = z 2 + 2z 3 + z 4
gives exactly the number of polynomials of degree 2, 3 and 4 in G 3 \ G 2 .

Proof. The proof is by induction on i. If i = 1 then by definition of the Noether position, the basis is reduced to one polynomial with leading term x d 1 1 so that in this case B 1 (z) = z d 1 as expected.

Assuming the property to hold for i -1, we now prove it for i. Consider g ∈ G i , which can be written

g = g i f i + • • • + g 1 f 1 , (9)
for some polynomials g i . By Proposition 11, we can restrict our attention to g i with LT(g i ) belonging to k[x 1 , . . . , x i-1 ]. Now if g ∈ G i has degree d and does not belong to the Gröbner basis of f 1 , . . . , f i-1 , the number of possible leading monomials of g i in such a decomposition is bounded by the number of monomials of degree dd i in k[x 1 , . . . , x i-1 ] that are not leading terms of a polynomial in f 1 , . . . , f i-1 , and this is precisely

HF θ i-1 f 1 ,..., f i-1 (d -d i ) with θ i-1 as in Proposition 7
. This is a bound on the dimension of a vector space containing these elements of G i . It is therefore also a bound on their possible number of leading terms, whence the result.

The properties of h d come from the fact that these properties are true for each of the coefficient sequences of the polynomials (1z d k )/(1z) and are preserved by multiplication of these polynomials (see, e.g., [START_REF] Stanley | Log-concave and unimodal sequences in algebra, combinatorics, and geometry[END_REF]).

Note that since the series in Theorem 12 is actually a polynomial of degree

δ = i ∑ j=1 (d j -1) + 1,
we deduce that this is also a bound on the highest degree of the elements in a reduced grevlex Gröbner basis, thus recovering (Lejeune-Jalabert, 1984, Ch. 3, Cor. 3.5), and from there the result of [START_REF] Lazard | Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations[END_REF] after a generic linear change of variables.

Corollary 13. For a system with variables in simultaneous Noether position, a bound on the number of operations in k required to compute a Gröbner basis for the grevlex ordering is obtained by taking D = ∑ m j=1 (d j -1) + 1 in Proposition 1.

The next section shows that the F 5 algorithm achieves a smaller complexity.

Upper Bound for F 5

We now give a proof of Theorem 2 from page 3 using the F 5 criterion. Note that the asymptotic character of this result is only relative to n: we obtain an actual bound for any fixed degree δ .

Proof. The outline of the proof is as follows. First, we exploit the information on the shape of the Gröbner basis from Theorem 12 in order to get a good control over the number of operations. Following the structure of the algorithm we get a bound as a sum over i = 1, . . . , m, corresponding to the rows induced by each input polynomial f i , of sums over d, corresponding to the columns induced by the monomials of a given degree. Next, we observe that the (bound on the) cost of all steps over i is bounded by that devoted to the last polynomial f m . The situation with respect to degrees is different: there is an intermediate degree where more work takes place. (In fact, we only prove that there is a degree where our bound dominates the other ones, but this behaviour can be observed in practice.) Then, we compute the asymptotic expansion of both this intermediate degree and the (bound on the) number of rows involved in that degree. The final result is obtained by injecting these expansions into the bounds.

Exact bound from the numbers of rows and columns in the top

N F 5 = m ∑ i=1 D ∑ d=δ b (i) d i + d -1 d n + d -1 d . ( 10
)
Bound on the number of polynomials in M d,i \ M d,i-1 . For an arbitrary d and i, we have

b (i) d ≤ B i (r) r d ,
for any r > 0 which follows from the positivity of the coefficients of B i (see ( 8)). This bound holds for arbitrary r > 0; it is minimised by choosing for r a root of the derivative of the right-hand side, which is equivalent (using the logarithmic derivative) to taking r such that

d = r B ′ i (r) B i (r) . As B i (r) = r δ 1-r δ 1-r i
for equations of identical degree δ , this is equivalent to

i = 1 + (d -δ ) • δ 1 -r -δ - 1 1 -r -1 -1 . (11)
For d ≥ δ , the right-hand side of this equation is a differentiable function of r, its derivative is negative, and it has extreme values +∞ and d-1 δ -1 . This is then a positive decreasing function of r. This shows that (11) defines r as a function r (i, d)

for i ≥ d-1
δ -1 and δ ≤ d, and this function is a positive, decreasing, differentiable function of i.

The same reasoning on the equation d = r

B ′ i (r)
B i (r) shows that r(i, d) is differentiable with respect to d, for δ ≤ d ≤ deg B i , and that it is positive and increasing.

Bound on the work on the ith polynomial. A bound on the sequence summed in ( 10) is now obtained by bounding the differentiable function of i

B i (r(i, d)) r(i, d) d i + d -1 d n + d -1 d for 1 ≤ i ≤ m such that b (i) d = 0, i.e., i ≥ d-1 δ -1
. This is an increasing function of i. Indeed, the last binomial does not depend on i, the previous one is clearly increasing and the logarithmic derivative of the first factor w.r.t. i is

1 -r(i, d) δ 1 -r(i, d) = 1 + r(i, d) + • • • + r(i, d) δ -1 (12)
which is positive. Hence, we have the bound

N F 5 ≤ m D ∑ d=δ B m (r(m, d)) r(m, d) d m + d -1 d n + d -1 d . ( 13
)
(Intuitively, the most expensive part of the computation is performed for i = m.)

The most expensive degree d. Consider now the summand as a function of d. Its logarithmic derivative in d for fixed r has a simple expression, which vanishes for d root of the equation

2ψ(d + m) -2ψ(d + 1) = log r(m, d), ( 14
)
where ψ is the logarithmic derivative of the Γ function (see, e.g., (Abramowitz and Stegun, 1992, Ch. 6)). Thus we now have two equations, ( 14) and ( 11) (with i = m), relating r, d, m.

As a consequence of the functional equation of the Γ function (Γ(s + 1) = sΓ(s)), the lefthand side of ( 14) can be rewritten using the alternative expression

ψ(d + m) -ψ(d + 1) = 1 d + 1 + • • • + 1 d + m -1 .
It follows that Equation ( 14 gives the solution to (11,14) (for i = m). Moreover, we have ρ(m) ≥ 1.

We have now isolated the most expensive step of the algorithm and basically bound all of them by it. The total number of arithmetic operations in k required by algorithm matrix-F 5 is therefore bounded by

N F 5 ≤ m (m (δ -1) + 1 -(δ -1)) B m (ρ(m)) ρ(m) d(m) m + d(m) -1 d(m) m + ℓ + d(m) -1 d(m) , (15)
where we have used the bound on D from Corollary 13 and the hypothesis n = m + ℓ.

Asymptotic expansions. We now let m → ∞ and obtain the asymptotic behaviour of both ρ and d simultaneously, before injecting into the bound above.

Rewriting (11) yields

d(m) -δ m -1 = δ 1 -ρ(m) -δ - 1 1 -ρ(m) -1 , (16)
from which we define λ (m) := d(m) m .

Now, since ρ(m) ≥ 1, the right-hand side of Equation ( 16) takes its values between δ -1 2 and δ -1, which implies that λ (m) is bounded as m → ∞.

Thus we can compute the asymptotic behaviour of ( 14), using the classical expansion

ψ(x) = log(x) - 1 2x - ∞ ∑ n=1 B(2n) 2n(x 2n ) , x → +∞ (17)
where B(n) is the nth Bernoulli number. This gives

ρ(m) = 1 + λ (m) -1 2 + O 1 m
We can then eliminate ρ(m) from ( 16) asymptotically:

λ (m) + O 1 m = δ 1 -(1 + λ (m) -1 ) -2δ - 1 1 -(1 + λ (m) -1 ) -2 + O 1 m
from which we see that as m → ∞, λ (m) tends to λ 0 the unique root between δ -1 2 and δ -1 of

λ 0 = δ 1 -1 + λ -1 0 -2δ - 1 1 -1 + λ -1 0 -2
or equivalently

1 + λ -1 0 2δ = 1 1 -δ (λ 0 +1) 2 -λ 0 2 (λ 0 +1) 3 -λ 0 3 . (18)
Now, Equation ( 14) using ( 17) gives ρ as a bivariate formal expansion in 1/m and λλ 0 , with

ρ = 1 + λ -1 0 2 - 2(λ 0 + 1) λ 3 0 (λ -λ 0 ) - (λ 0 + 1) (2 λ 0 + 1) λ 3 0 1 m + ∑ i, j≥1 ρ i, j (λ 0 ) (λ -λ 0 ) i m j .
Injecting into Equation ( 16) yields a bivariate formal power series Φ(1/m, λλ 0 ) = 0 where

Φ(1/m, λ -λ 0 ) =   3 λ 0 2 + 3 λ 0 + 2 (λ 0 + 1) λ 0 - 2 3 λ 0 2 + 3 λ 0 + 1 λ 0 (λ 0 + 1) (2 λ 0 + 1) δ   (λ -λ 0 )+   3 λ 0 3 + 5 λ 0 2 + 4 λ 0 + 1 λ 0 (λ 0 + 1) - 2 λ 0 2 + 2 λ 0 + 1 λ 0 (λ 0 + 1) δ   1 m + O λ -λ 0 m
The asymptotic implicit function theorem (see, e.g., [START_REF] Gérard | Asymptotic implicit function theorems. Part I: the preparation theorem and division theorem[END_REF]) implies that the asymptotic expansion of λλ 0 is given by the formal power series S ∈ C[[1/m]] such that Φ(1/m, S(1/m)) = 0. This series can be computed to arbitrary order, e.g., by indeterminate coefficients or Newton iteration, and for instance we get

λ (m) = λ 0 - (2 λ 0 + 1) 2 λ 0 2 + 2 λ 0 + 1 δ -3 λ 0 3 -5 λ 0 2 -4 λ 0 -1 6 λ 0 2 + 6 λ 0 + 2 δ -6 λ 0 3 -9 λ 0 2 -7 λ 0 -2 1 m + O 1 m 2 , ρ(m) = (λ 0 + 1) 2 λ 0 2 - (λ 0 + 1) 2 (2 λ 0 + 1) (2 δ + 1) λ 0 2 6 λ 0 2 + 6 λ 0 + 2 δ -6 λ 0 3 -9 λ 0 2 -7 λ 0 -2 1 m + O 1 m 2 .
Final bound. We now inject these estimates into (15) and obtain the final result:

N F 5 ≤ A m    λ 0 +1 λ 0 2δ -1 1 λ 0 2 -1 (λ 0 +1) 2    m 1 + O 1 m ,
where A is a constant depending only on δ , λ 0 and ℓ, whose value is given by

A = 1 -δ -1 2π • 1 + λ -1 0 3 -1 (1 + λ 0 ) 1+ℓ .
Inequalities. The proof of Theorem 2 is concluded by showing that the expression abbreviated B(δ ) in the theorem remains within the interval [δ 3 , 3δ 3 ].

The lower bound is obtained by observing that, in view of ( 18),

B -δ 3 = δ λ 2 0 (λ 0 + 1) 2 1 -δ + 3λ 0 -2δ λ 0 + 3λ 2 0 -δ 3 = δ (δ -λ 0 )(δ -1 -λ 0 )(λ 0 + δ + 2δ λ 0 + λ 2 0 ) 1 -δ + 3λ 0 -2δ λ 0 + 3λ 2 0 = δ (δ -λ 0 )(δ -1 -λ 0 )(λ 0 + δ + 2δ λ 0 + λ 2 0 ) ((1 + λ 0 ) 3 -λ 3 0 )(1 + λ -1 0 ) -2δ and this is nonnegative since λ 0 is smaller than δ -1.
The upper bound is obtained in two steps: first B(δ )/δ 3 is shown to be increasing with δ and next its limit as δ → ∞ is computed. Equation ( 18) shows that λ 0 is a differentiable function of δ and thus so is B. An expression for λ ′ 0 (δ ) is obtained by differentiating (18). Injecting this expression into the derivative of B and simplifying gives the logarithmic derivative of B(δ )/δ 3 :

B ′ (δ ) B(δ ) - 3 δ = (3λ 2 0 + 3λ 0 + 1) ln((1 + λ -1 0 ) 2 ) -3(2λ 0 + 1) (2λ 0 + 1) δ .
The numerator depends on λ 0 only. Its positivity is obtained by using the lower bound ln(1+x) ≥ xx 2 /2 + x 3 /3x 4 /4 for x ∈ (0, 1), leading to a polynomial that is positive as soon as λ 0 > 1.4. Since λ 0 ≥ (δ -1)/2, the monotonicity of B(δ )/δ 3 is then established by checking the values for the cases δ = 2, 3, 4 and indeed, we obtain the approximations 2.45, 2.66, 2.73 that conclude this part. The limit of B(δ )/δ 3 is obtained in a way similar to the asymptotic expansions above. We first consider the asymptotic behaviour of λ 0 as δ → ∞. Setting λ 0 = cδ and taking the asymptotic expansion of ( 18) yields

e 2/c + O(1/δ ) = 3c 3c -2 + O(1/δ ).
The limiting value of c is therefore the solution of the equation given by the leading term. It can be expressed in terms of the Lambert W function as

lim δ →∞ λ 0 δ = 2 3 +W (-3e -3 ) ≃ 0.708858.
In terms of this value of the limit of c, a direct computation gives

lim δ →∞ B(δ ) δ 3 = -4 W (-3e -3 )(3 +W (-3e -3 )) 2 ≃ 2.81405669.
This concludes the proof that B(δ ) ≤ 3δ 3 , with a more precise estimate in place of the factor 3.

Note that full asymptotic expansions of all the parameters can be derived along the same lines.

Practical results

In order to estimate the accuracy or the lack of preciseness of our complexity result, we performed actual Gröbner bases computations for quadratic and cubic systems of n equations in n unknowns, in simultaneous Noether position, with dense coefficients. These results have been obtained on a PC (laptop) with 4 GB of RAM. The F 5 algorithm has been implemented in the C language within the FGb software [START_REF] Faugère | FGb: A Library for Computing Gröbner Bases[END_REF] and we used this implementation to compute the Gröbner basis and to count the exact number of arithmetic operations (multiplications of integers modulo p = 65521). These results show that the estimate of the number of polynomials in the Gröbner basis (Eq. ( 8), Theorem 12) and the asymptotic bound of N F 5 (Eq. ( 3), Theorem 2) are very precise, but that the quantity N F 5 (Equation ( 10)) could be sharpened. This will be done in a future work.

Accuracy of the asymptotic estimate of N F 5 . We plot in Figure 2 the values of N F 5 computed from Eq. ( 10) and its asymptotic estimate given in Theorem 2, Eq. ( 3). This shows that the asymptotic bound for N F 5 is accurate. d , the number of polynomials computed by the matrix F 5 algorithm, and the number of polynomials in the reduced Gröbner basis. It has been shown that F 5 computes "redundant" polynomials that do not belong to the reduced Gröbner basis (see, e.g., [START_REF] Eder | Modifying Faugère's F5 algorithm to ensure termination[END_REF]). Moreover, F 5 sometimes reduces less than b (i) d polynomials. But experimentally, this difference is small. When all the equations have the same degree d i = δ , the total number of polynomials in our estimation (8) becomes: Estimation of N F 5 in Equation (10). In Tables 2 and3 we report for each n the quantities top F 5 and N F 5 , where top F 5 is the experimental number of multiplications for the matrix version of F 5 using only top reductions as described in Section 2.1, and N F 5 is given by formula (10). These values are represented graphically on Figures 4 page 22 and 5 page 23. n top F 5 full F 5 N F 5 7 2 19.83 = 2 2.83n 2 20.78 = 2 2.97n 2 25.6 = 2 3.65n 8 2 22.95 = 2 2.87n 2 23.14 = 2 2.89n 2 29.7 = 2 3.72n 9 2 26.19 = 2 2.91n 2 25.39 = 2 2.82n 2 33.9 = 2 3.77n 10 2 29.38 = 2 2.94n 2 27.94 = 2 2.79n 2 38.1 = 2 3.81n 11 2 32.65 = 2 2.97n 2 30.46 = 2 2.77n 2 42.3 = 2 3.84n 12 2 35.90 = 2 2.99n 2 33.20 = 2 2.77n 2 46.4 = 2 3.87n 13 2 35.86 = 2 2.76n 2 50.7 = 2 3.9n 14 2 38.70 = 2 2.76n 2 54.9 = 2 3.92n 15 2 41.52 = 2 2.79n 2 59.1 = 2 3.94n 16 2 44.43 = 2 2.78n 2 63.3 = 2 3.96n This time, we observe a significant gap between the exact values and our bound. Remember that the bound in Equation ( 10) is computed assuming that b 2 20.06 = 2 4.01n 2 22.01 = 2 4.40n 2 24.2 = 2 4.84n 6 2 24.93 = 2 4.16 2 25.85 = 2 4.31n 2 30.1 = 2 5.02n 7 2 29.87 = 2 4.27 2 29.78 = 2 4.25n 2 36.1 = 2 5.16n 8 2 34.86 = 2 4.36 2 33.98 = 2 4.25n 2 42.1 = 2 5.26n 9 2 39.88 = 2 4.43n 2 38.39 = 2 4.27n 2 48.15 = 2 5.35n 10 2 41.91 = 2 4.29n 2 54.19 = 2 5.42n

Polys F 5 = m ∑ i=1 D ∑ d=δ b (i) d = m ∑ i=1 δ i-1 = δ m -1 δ -1 .
Table 3: Cubic equations (δ = 3) coefficients (before reduction) as the row in degree d -1. Hence the matrices M d,i are sparse matrices. This phenomenon is amplified when the degree d and the number of variables n grow, and explains the gap between our bound and the experiments. We did not find a way to capture this phenomenon in our bound yet, also because we compute a worst-case bound that has to capture all the non-generic behaviors.

Top reduction vs full reduction. Tables 2 and3 also contain the quantity full F 5 , which is the exact number of multiplications for Algorithm F ′ 5 as described in the original article [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5 )[END_REF]; this algorithm is a matrix version of F 5 where a full reduction is used over the rows, instead of only a top reduction: for each row, reductions are performed not only for the leading term, but also for all the remaining coefficients. Experimental results show that this strategy becomes quickly efficient as n grows, which is due to the fact, observed empirically, that the rows in the matrices are sparser with this algorithm than with top reduction only. We thank the anonymous referees for their careful reading and helpful comments.

Figure 1 :

 1 Figure 1: Asymptotic of the F 5 -bound vs linear algebra on the Macaulay Matrix

  this function is a polynomial (the Hilbert polynomial HP I ). The generating function H I = ∑ d≥0 HF I (d)z d is called the Hilbert series of the ideal.

  -reduction case. Arithmetic operations are only performed during the Gaussian reductions. If we perform only top-reductions, for each 1 ≤ i ≤ m and δ ≤ d ≤ D, by Theorems 9 and 12 there are at most b (i) d polynomials in M d,i \ M d,i-1 that need to be reduced, and they need to be reduced by Md,i-1 . By Proposition 11 the leading term of the result is in T i d , which implies that at most i+d-1 d rows are involved in this reduction, each row containing n+d-1 d columns. This gives the following bound on the number of arithmetic operations

  ) defines a unique positive, differentiable function d(m), such that the pair (d(m), ρ(m)) with the notation ρ(m) := r(m, d(m)))

Figure 2 :

 2 Figure 2: Comparison of N F 5 with its asymptotic estimate

Figure 3

 3 Figure3shows that this bound is very close to the actual number of polynomials computed by the matrix F 5 algorithm. 20

F 5 )

 5 Figure 3: Comparison of the exact/approximated number of polynomials computed by F 5

d

  Figure 4: Experiments with δ = 2 n top F 5 full F 5 N F 5 52 20.06 = 2 4.01n 2 22.01 = 2 4.40n 2 24.2 = 2 4.84n 6 2 24.93 = 2 4.16 2 25.85 = 2 4.31n 2 30.1 = 2 5.02n 7 2 29.87 = 2 4.27 2 29.78 = 2 4.25n 2 36.1 = 2 5.16n 8 2 34.86 = 2 4.36 2 33.98 = 2 4.25n 2 42.1 = 2 5.26n 9 2 39.88 = 2 4.43n 2 38.39 = 2 4.27n 2 48.15 = 2 5.35n 10 2 41.91 = 2 4.29n 2 54.19 = 2 5.42n

Figure 5 :

 5 Figure 5: Experiments with δ = 3

Table 1 :

 1 Asymptotic Behaviour of the F 5 -bound (Equation (3)), in terms of the Bézout bound δ n .

	log 2 (B(δ ))	14
		12
		10
		8
		6
		4
		2	4	6	8	10	δ

Table 2 :

 2 Quadratic equations (δ = 2)

Acknowledgement

This work was partly supported by the HPAC grant of the French National Research Agency (HPAC ANR-11-BS02-013).