Jean-Charles Faugère

Mohab Safey

El Din

Pierre-Jean Spaenlehauer

Gröbner Bases of Bihomogeneous Ideals Generated by Polynomials of Bidegree (1, 1): Algorithms and Complexity

Keywords: Gröbner bases, bihomogeneous ideals, algorithms, complexity

Solving multihomogeneous systems, as a wide range of structured algebraic systems occurring frequently in practical problems, is of first importance. Experimentally, solving these systems with Gröbner bases algorithms seems to be easier than solving homogeneous systems of the same degree. Nevertheless, the reasons of this behaviour are not clear. In this paper, we focus on bilinear systems (i.e. bihomogeneous systems where all equations have bidegree (1, 1)). Our goal is to provide a theoretical explanation of the aforementioned experimental behaviour and to propose new techniques to speed up the Gröbner basis computations by using the multihomogeneous structure of those systems. The contributions are theoretical and practical. First, we adapt the classical F 5 criterion to avoid reductions to zero which occur when the input is a set of bilinear polynomials. We also prove an explicit form of the Hilbert series of bihomogeneous ideals generated by generic bilinear polynomials and give a new upper bound on the degree of regularity of generic affine bilinear systems. We propose also a variant of the F 5 Algorithm dedicated to multihomogeneous systems which exploits a structural property of the Macaulay matrix which occurs on such inputs. Experimental results show that this variant requires less time and memory than the classical homogeneous F 5 Algorithm. Lastly, we investigate the complexity of computing a Gröbner basis for the grevlex ordering of a generic 0-dimensional affine bilinear system over k[x 1 , . . . , x n x , y 1 , . . . , y n y ]. In particular, we show that this complexity is upper bounded by O n x +n y +min(n x +1,n y +1) min(n x +1,n y +1) ω , which is polynomial in n x + n y (i.e. the number of unknowns) when min(n x , n y ) is constant.

Introduction

The problem of multivariate polynomial system solving is an important topic in computer algebra since algebraic systems can arise from many practical applications (cryptology, robotics, Email addresses: Jean-Charles.Faugere@inria.fr (Jean-Charles Faugère), Mohab.Safey@lip6.fr (Mohab Safey El Din), Pierre-Jean.Spaenlehauer@lip6.fr (Pierre-Jean Spaenlehauer) real algebraic geometry, coding theory, signal processing, etc...). One method to solve them is based on the Gröbner basis theory. Due to their practical importance, efficient algorithms to compute Gröbner bases of algebraic systems are required: for instance Buchberger's Algorithm [START_REF] Buchberger | An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal[END_REF]), Faugère F 4 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF]) or F 5 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF]).

In this article, we focus on the F 5 Algorithm. In particular, the F 5 criterion is a tool which removes the so-called reductions to zero (which are useless) during the Gröbner basis computation when the input system is a regular sequence. For instance, consider a sequence of polynomials ( f 1 , . . . , f m ). The reductions to zero come from the leading monomials in the colon ideals f 1 , . . . , f i-1 : f i . Given a term order, let LM(I) denote the ideal generated by the leading monomials of the elements of an ideal I. Then the reductions to zero detected by the F 5 criterion are those related to LM( f 1 , . . . , f i-1 ). For regular systems, LM( f 1 , . . . , f i-1 ) = LM( f 1 , . . . , f i-1 : f i ). Therefore, the F 5 criterion removes all useless reductions. In practice, if a homogeneous polynomial system is chosen "at random", then it is regular.

In this paper, we consider multihomogeneous systems, which are not regular sequences in the polynomial ring. Such systems can appear in cryptography [START_REF] Faugère | Cryptanalysis of MinRank[END_REF]), in coding theory [START_REF] Ourivski | New technique for decoding codes in the rank metric and its cryptography applications[END_REF]) or in effective geometry (see Safey El [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]; Safey El [START_REF] El Din | Strong bi-homogeneous Bézout theorem and its use in effective real algebraic geometry[END_REF]).

A multihomogeneous polynomial is defined with respect to a partition of the unknowns, and is homogeneous with respect to each subset of variables. The finite sequence of degrees is called the multi-degree of the polynomial. For instance, a bihomogeneous polynomial f of bidegree (d 1 , d 2 ) over k[x 0 , . . . , x n x , y 0 , . . . , y n y ] is a polynomial such that ∀λ , µ, f (λ x 0 , . . . , λ x n x , µy 0 , . . . , µy n y ) = λ d 1 µ d 2 f (x 0 , . . . , x n x , y 0 , . . . , y n y ).

In general, multihomogeneous systems are not regular. Consequently, the F 5 criterion does not remove all reductions to zero. Our goal is to understand the underlying structure of these multihomogeneous algebraic systems, and then use it to speed up the computation of a Gröbner basis in the context of F 5 . In this paper, we focus on bihomogeneous ideals generated by polynomials of bidegree (1, 1).

Main results

Let k be a field, f 1 , . . . f m ∈ k[x 0 , . . . , x n x , y 0 , . . . , y n y ] be bilinear polynomials. We denote by F i the polynomial family ( f 1 , . . . , f i ) and by I i the ideal F i . We start by describing the algorithmic results of the paper, obtained by exploiting the algebraic structure of bilinear systems.

In order to understand this structure, we study properties of the jacobian matrices with respect to the two subsets of variables x 0 , . . . , x n x and y 0 , . . . , y n y :

jac x (F i ) =     ∂ f 1 ∂ x 0 • • • ∂ f 1 ∂ x nx . . . . . . . . . ∂ f i ∂ x 0 • • • ∂ f i ∂ x nx     jac y (F i ) =     ∂ f 1 ∂ y 0 • • • ∂ f 1 ∂ y ny . . . . . . . . . ∂ f i ∂ y 0 • • • ∂ f i ∂ y ny    
We show that the kernels of those matrices (whose entries are linear forms) correspond to the reductions to zero not detected by the classical F 5 criterion. In general, all elements in these kernels are vectors of maximal minors of the jacobian matrices (Lemma 2). For instance, if n x = n y = 2 and m = 4, consider v = (minor(jac x (F 4 ), 1), -minor(jac x (F 4 ), 2), minor(jac x (F 4 ), 3), -minor(jac x (F 4 ), 4)) and w = (minor(jac y (F 4 ), 1), -minor(jac y (F 4 ), 2), minor(jac y (F 4 ), 3), -minor(jac y (F 4 ), 4)), where minor(jac x (F 4 ), k) (resp. minor(jac y (F 4 ), k)) denotes the determinant of the matrix obtained from jac x (F 4 ) (resp. jac y (F 4 )) by removing the k-th row. The generic syzygies corresponding to reductions to zero which are not detected by the classical F 5 criterion are v ∈ Ker L (jac x (F 4 )) and w ∈ Ker L (jac y (F 4 )).

We show (Corollary 2) that, in general, the ideal I i-1 : f i is spanned by I i-1 and by the maximal minors of jac x (F i-1 ) (if i > n y + 1) and jac y (F i-1 ) (if i > n x + 1). The leading monomial ideal of I i-1 : f i describes the reductions to zero associated to f i . Thus we need results about ideals generated by maximal minors of matrices whose entries are linear forms in order to get a description of the syzygy module. In particular, we prove that, in general, grevlex Gröbner bases of those ideals are linear combinations of the generators (Theorem 3). Based on this result, one can compute efficiently a Gröbner basis of I i-1 : f i once a Gröbner basis of I i-1 is known.

This allows us to design an Algorithm (Algorithm 4) dedicated to bilinear systems, which yields an extension of the classical F 5 criterion. This subroutine, when merged within a matricial version of the F 5 Algorithm (Algorithm 2), eliminates all reductions to zero during the computation of a Gröbner basis of a generic bilinear system. For instance, during the computation of a grevlex Gröbner basis of a system of 12 generic bilinear equations over k[x 0 , . . . , x 6 , y 0 , . . . , y 6 ], the new criterion detects 990 reductions to zero which are not found by the usual F 5 criterion. Even if this new criterion seems to be more complicated than the usual F 5 criterion (some precomputations have to be performed), we prove that the cost induced by those precomputations is negligible compared to the cost of the whole computation.

Next, we introduce a notion of bi-regularity which describes the structure of generic bilinear systems. When the input of Algorithm 4 is a bi-regular system, then it returns all reductions to zero. We also give a complete description of the syzygy module of such systems, up to a conjecture (Conjecture 1) on a linear algebra problem over rings. This conjecture is supported by practical experiments. We also prove that there are no reductions to zero with the classical F 5 criterion for affine bilinear systems (Proposition 5) which is important for practical applications.

We describe now the main complexity results of the paper. We need some results on the socalled Hilbert bi-series of ideals generated by bilinear systems. For bi-regular bilinear system, we give an explicit form of these series (Theorem 5):

HS I m (t 1 ,t 2 ) = N m (1 -t 1 ) n x +1 (1 -t 2 ) n y +1 , N m (t 1 ,t 2 ) = (1 -t 1 t 2 ) m + ∑ m-(ny+1) ℓ=1 (1 -t 1 t 2 ) m-(ny+1)-ℓ t 1 t 2 (1 -t 2 ) ny+1 1 -(1 -t 1 ) ℓ ∑ ny+1 k=1 t ny+1-k 1 ℓ+ny-k ny+1-k + ∑ m-(nx+1) ℓ=1 (1 -t 1 t 2 ) m-(nx+1)-ℓ t 1 t 2 (1 -t 1 ) nx+1 1 -(1 -t 2 ) ℓ ∑ nx+1 k=1 t nx+1-k 2 ℓ+nx-k nx+1-k .
After this analysis, we propose a variant of the Matrix F 5 Algorithm dedicated to multihomogeneous systems. The key idea is to decompose the Macaulay matrices into a set of smaller matrices whose row echelon forms can be computed independently. We provide some experimental results of an implementation of this algorithm in Magma2.15. This multihomogeneous variant can be more than 20 times faster for bihomogeneous systems than our Magma implementation of the classical Matrix F 5 Algorithm. We perform a theoretical complexity analysis based on the Hilbert series in the case of bilinear systems, which provides an explanation of this gap.

Finally, we establish a sharp upper bound on the degree of regularity of 0-dimensional affine bilinear systems (Theorem 6). Let f 1 , . . . , f n x +n y be an affine bilinear system of k[x 0 , . . . , x n x -1 , y 0 , . . . , y n y -1 ], then the maximal degree reached during the computation of a Gröbner basis with respect to the grevlex ordering is upper bounded by:

d reg ≤ min (n x + 1, n y + 1) .
This bound is exact in practice for generic bilinear systems and permits to derive complexity estimates for solving bilinear systems (Corollary 3) which can be applied to practical problems (see for instance [START_REF] Faugère | Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology[END_REF] for an application to the MinRank problem).

State of the art

The complexity analysis that we perform by proving properties on the Hilbert bi-series of bilinear ideals follows a path which is similar to the one used to analyze the complexity of the F 5 algorithm in the case of homogeneous regular sequences (see [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]). In [START_REF] Kreuzer | Basic tools for computing in multigraded rings[END_REF], the properties of Buchberger's Algorithm are investigated in the context of multigraded rings. Cox et al. (2007a) gives an analysis of the structure of the syzygy module in the case of three bihomogeneous equations with no common solution in the biprojective space.

The algorithmic use of multihomogeneous structures has been investigated mostly in the framework of multivariate resultants (see [START_REF] Dickenstein | Multihomogeneous resultant formulae by means of complexes[END_REF]; [START_REF] Emiris | Multihomogeneous resultant formulae for systems with scaled support[END_REF] and references therein for the most recent results) following the line of work initiated by [START_REF] Mccoy | On the resultant of a system of forms homogeneous in each of several sets of variables[END_REF]. In the context of solving polynomial systems by using straight-line programs as data-structures, [START_REF] Jeronimo | Computing multihomogeneous resultants using straight-line programs[END_REF] provides an alternative way to compute resultant formula for multihomogeneous systems.

As we have seen in the description of the main results, the knowledge of Gröbner bases of ideals generated by maximal minors of linear matrices play a crucial role. Theorem 3 which states that such Gröbner bases are obtained by a single row echelon form computation is a variant of the main results in [START_REF] Sturmfels | Maximal minors and their leading terms[END_REF] and [START_REF] Bernstein | Combinatorics of maximal minors[END_REF] (see also the survey by [START_REF] Bruns | Gröbner bases and determinantal ideals[END_REF]).

More generally, the theory of multihomogeneous elimination is investigated in Rémond (2001) providing tools to generalize some well-known notions (e.g. Chow forms, resultant formula, heights) in the homogeneous case to multihomogeneous situations. Such works are initiated in [START_REF] Van Der Waerden | On Hilbert's Function, Series of Composition of Ideals and a generalization of the Theorem of Bezout[END_REF] where the Hilbert bi-series of bihomogeneous ideals is introduced.

Structure of the paper

This paper is articulated as follows. Some tools from commutative algebra are introduced. Next, we investigate the case of bilinear systems and propose an algorithm to remove all reductions to zero during the Gröbner basis computation. Then we prove its correctness and explain why it is efficient for generic bilinear systems. To continue our study of the structure of bilinear ideals, we give the explicit form of the Hilbert bi-series of generic bilinear ideals. Finally, we prove a new bound on the degree of regularity of generic affine bilinear systems and we use it to derive new complexity bounds. Technical results and their proofs are postponed in Appendix.

Acknowledgments.

We are grateful to Ludovic Perret, Ioannis Z. Emiris and anonymous referees for their helpful comments and suggestions. This work is supported by the CAC grant of the French National Research Agency (ANR-09-JCJCJ-0064-01), the EXACTA grant of the French National Research Agency (ANR-09-BLAN-0371-01) and the National Science Foundation of China, and by the European Commission through the ICT programme under contract ICT-2007-216676 ECRYPT II.

Gröbner bases: the Matrix F 5 Algorithm

Gröbner bases: notations

In this section, R denotes the polynomial ring k[x 1 , . . . , x n ] (where k is a field) and for all

β = (β 1 , . . . , β n ) ∈ N n , x β denotes x β 1 1 , • • • , x β n n .
Gröbner bases are defined with respect to a monomial ordering (see Cox et al. (2007b), page 55, Definition 1). In this paper, we focus in particular on the so-called grevlex ordering (degree reverse lexicographical ordering).

Definition 1. The grevlex ordering is defined by:

x α ≺ x β ⇔      ∑ α i < ∑ β i or ∑ α i = ∑ β i and the first coordinates from the right which are different satisfy α i > β i .
If ≺ is a monomial ordering and f ∈ R is a polynomial, then its greatest monomial with respect to ≺ is called leading monomial and denoted by LM ≺ ( f ) (or simply LM( f ) when there is no ambiguity on the considered ordering).

If I ⊂ R is a polynomial ideal, its leading monomial ideal (i.e. {LM ≺ ( f ) : f ∈ I} ) is denoted by LM ≺ (I) (or simply LM(I) when there is no ambiguity on the ordering) .

Definition 2. let I ⊂ R be an ideal, and ≺ be a monomial ordering. A Gröbner basis of I (relatively to ≺) is a finite subset G ⊂ I such that: LM ≺ (G) = LM ≺ (I). Definition 3. Let I ⊂ R be an ideal, ≺ be a monomial ordering and f ∈ R be a polynomial. Then there exist unique polynomials f ∈ R and g ∈ I such that f = f + g and none of the monomials appearing in f are in LM ≺ (I). The polynomial f is called the normal form of f (with respect to I and ≺), and is denoted NF I,≺ ( f ).

It is well known that NF I,≺ ( f ) = 0 if and only if f ∈ I (see e.g. Cox et al. (2007b)). Definition 4. Let I ⊂ R be a homogeneous ideal, ≺ be a monomial ordering and D be an integer. We call D-Gröbner basis a finite set of polynomials G such that G = I and

∀ f ∈ I with deg( f ) ≤ D, there exists g ∈ G such that LM ≺ (g) divides LM ≺ ( f ).
The following Lemma is a straightforward consequence of Dickson's Lemma (Cox et al., 2007b, page 71, Theorem 5).

Lemma 1. Let I ⊂ R be an ideal and let ≺ be a monomial ordering. There exists D ∈ N such that every D-Gröbner basis with respect to ≺ is a Gröbner basis of I with respect to ≺.

The Matrix F 5 Algorithm

We use a variant of the F 5 Algorithm, called Matrix F 5 Algorithm, which is suitable to perform complexity analyses (see [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]; [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]; [START_REF] Faugère | Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases[END_REF]).

Given a set of generators ( f 1 , . . . , f m ) of a homogeneous polynomial ideal I ⊂ R, an integer D and a monomial ordering ≺, the Matrix F 5 Algorithm computes a D-Gröbner basis of I with respect to ≺. It performs incrementally by considering the ideals

I i = f 1 , . . . , f i for 1 ≤ i ≤ m.
Let d ∈ N, denote by R d the k-vector space of polynomials in R of degree d. As in [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF] and [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF], we use a definition of the row echelon form of a matrix which is slightly different from the usual definition: we call row echelon form the matrix obtained by applying the Gaussian elimination Algorithm without permuting the rows. The idea of the Matrix F 5 Algorithm (see Algorithm 2 below) is to calculate triangular bases of the vector spaces I i ∩ R d for 1 ≤ d ≤ D and 1 ≤ i ≤ m and to deduce from them a d-basis of I i+1 . These triangular bases are obtained by computing row echelon forms of the Macaulay matrices. Definition 5. Let F i = ( f 1 , . . . , f i ) ∈ R i be a sequence of homogeneous polynomials of degrees (d 1 , . . . , d i ) and ≺ be a monomial ordering. The Macaulay matrix in degree d Macaulay ≺ (F i , d) is the matrix whose rows contain the coefficients of the polynomials {t f j } where 1 ≤ j ≤ i and t ∈ R is a monomial of degree dd j . The columns correspond to the monomials in R of degree d and are sorted by ≺ in descending order. Each row has a signature (t, f j ) and they are sorted as follows: a row with signature (t 1 , f j ) is preceding a row with signature (t 2 , f k ) if j < k or ( j = k and t 1 ≺ t 2 ). The element at the intersection of the row (t, f j ) and the column corresponding to the monomial m is the coefficient of m in the polynomial t f j .

When the row echelon form of a Macaulay matrix is computed, the rows which are linear combinations of preceding rows are reduced to zero. Such computations are useless: removing these rows before computing the row echelon form will not modify the result but lead to significant practical improvements. The so-called F 5 criterion (see [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF]) is used to detect these reductions to zero and is given below. In Algorithm 2, the matrices M d,i are similar to Macaulay matrices: their rows and their columns are sorted with the same orderings and their rows span the same vector spaces. Moreover, if ( f 1 , . . . , f m ) is a regular sequence, then the rows of their row echelon form M d,i are bases of I i ∩ R d .

Algorithm 1. F 5 criterion -returns a boolean

Require:

(t, f i ) the signature of a row A matrix M in row echelon form 1: If t is the leading monomial of a row of M , then return true, 2: else return false. Now, we give a description of the Matrix F 5 Algorithm.

Algorithm 2. Matrix F 5 (see [START_REF] Faugère | Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases[END_REF]; [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]; [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF]) end for 20: end for 21: return G

Require:      ( f 1 , . . . , f m ) homogeneous polynomials of degree d 1 ≤ d 2 ≤ . . . ≤ d m D an integer a monomial ordering ≺ Ensure: G is a D-Gröbner basis of f 1 , . . . , f m for ≺ 1: G ← { f 1 , . . . ,
We recall now some results mostly given by [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF] which justify the F 5 criterion by relating reductions to zero appearing in an incremental computation of a Gröbner basis of a homogeneous ideal with the syzygy module of the polynomial system under consideration. Definition 6. Let ( f 1 , . . . , f m ) be polynomials in R. A syzygy is an element s = (s 1 , . . . , s m ) ∈ R m such that ∑ m j=1 f j s j = 0. The degree of the syzygy is defined by max j (deg( f j ) + deg(s j )). The set of all syzygies is a submodule of R m called the syzygy module of ( f 1 , . . . , f m ).

The next theorem explains how reductions to zero and syzygies are related: Theorem 1 (F 5 criterion, [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF]).

1. If t ∈ LM(I i-1 ) then there exists a syzygy (s 1 , . . . , s i ) of ( f 1 , . . . , f i ) such that LM(s i ) = t. 2. Let (t, f i ) be the signature of a row of M d,m . Then the following assertions are equivalent:

(a) the row (t, f i ) is zero in the row echelon form M d,m . (b) t / ∈ LM(I i-1
) and there exists a syzygy s = (s 1 , . . . , s i ) of ( f 1 , . . . , f i ) such that t = LM(s i ).

The rows eliminated by the F 5 criterion correspond to the trivial syzygies, i.e. the syzygies (s 1 , . . . , s m ) such that ∀1 ≤ i ≤ m, s i ∈ f 1 , . . . , f i-1 , f i+1 , . . . , f m . These particular syzygies come from the commutativity of R (for all 1 ≤ i, j ≤ m, f i f jf j f i = 0). It is well known that in the generic case, the syzygy module of a polynomial system is generated by the trivial syzygies.

Definition 7. (Eisenbud, 1995, page 419) Let ( f 1 , . . . , f m ) be a sequence of homogeneous polynomials and let I i ⊂ R be the ideal f 1 , . . . , f i . The following assertions are equivalent:

1. the syzygy module of ( f 1 , . . . , f m ) is generated by the trivial syzygies.

2. for 2 ≤ i ≤ m, f i is not a divisor of 0 in R/I i-1 .
A sequence of polynomials which satisfies these conditions is called a regular sequence. This notion of regularity is essential since the regular sequences correspond exactly to the systems such that there is no reduction to zero during the computation of a Gröbner basis with F 5 (see [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF]). Moreover, generic polynomial systems with less equations than unknowns are regular.

Gröbner bases computation for bilinear systems

Overview

Let F = ( f 1 , . . . , f 4 ) be four bilinear polynomials in Q[x 0 , x 1 , x 2 , y 0 , y 1 , y 2 ], I be the ideal generated by F and V ⊂ C 6 be its associated algebraic variety. As above, I i denotes the ideal f 1 , . . . , f i , and we consider the grevlex ordering with x 0 ≻ . . . ≻ x n x ≻ y 0 ≻ . . . ≻ y n y . Since f 1 , . . . , f 4 are bilinear, for all (a 0 , a 1 , a 2 ) ∈ C 3 and 1 ≤ i ≤ 4, f i (a 0 , a 1 , a 2 , 0, 0, 0) = 0. Hence, V contains the linear affine subspace defined by y 0 = y 1 = y 2 = 0 which has dimension 3. We conclude that V has dimension at least 3.

Consequently, the sequence ( f 1 , f 2 , f 3 , f 4 ) is not regular (since the codimension of an ideal generated by a regular sequence is equal to the length of the sequence). Hence, there are reductions to zero during the computation of a Gröbner basis with the F 5 Algorithm (see [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF]).

When the four polynomials are chosen randomly, one remarks experimentally that these reductions correspond to the rows with signatures (x 3 0 , f 4 ) and (y 3 0 , f 4 ). This experimental observation can be explained as follows.

Consider the jacobian matrices

jac x (F) =     ∂ f 1 ∂ x 0 ∂ f 1 ∂ x 1 ∂ f 1 ∂ x 2 . . . . . . . . . ∂ f 4 ∂ x 0 ∂ f 4 ∂ x 1 ∂ f 4 ∂ x 2     and jac y (F) =     ∂ f 1 ∂ y 0 ∂ f 1 ∂ y 1 ∂ f 1 ∂ y 2 . . . . . . . . . ∂ f 4 ∂ y 0 ∂ f 4 ∂ y 1 ∂ f 4 ∂ y 2    
and the vectors of variables X and Y. By Euler's formula, it is immediate that for any sequence of polynomials (q 1 , q 2 , q 3 , q 4 ), (q 1 , . . . , q 4 ).jac x (F).X = 4 ∑ i=1 q i f i and (q 1 , . . . , q 4 ).jac y (F).Y =

4 ∑ i=1 q i f i (1)
Denote by Ker L (jac x (F)) (resp. Ker L (jac y (F))) the left kernel of jac x (F) (resp. jac y (F)). Therefore, if (q 1 , . . . , q 4 ) belongs to Ker L (jac x (F)) (resp. Ker L (jac y (F))), then the relation (1) implies that (q 1 , . . . , q 4 ) belongs to the syzygy module of I.

Given a (k + 1, k)-matrix M, denote by minor(M, j) the minor obtained by removing the j-th row from M. Consider By Cramer's rule, v ∈ Ker L (jac x (F)). A symmetric statement can be made for jac y (F). From this observation, one deduces that minor(jac x (F), 4) f 4 (resp. minor(jac y (F), 4) f 4 ) belongs to

I 3 = f 1 , f 2 , f 3 .
We conclude that the rows with signature (LM(minor(jac x (F), 4)), f 4 ) and (LM(minor(jac y (F), 4)), f 4 ) are reduced to zero when performing the Matrix F 5 Algorithm described in the previous section.

A straightforward computation shows that if F contains polynomials which are chosen randomly, LM(minor(jac x (F), 4)) = y 3 0 and LM(minor(jac y (F), 4)) = x 3 0 . In this section, we generalize this approach to sequences of bilinear polynomials of arbitrary length. Hence, the jacobian matrices have a number of rows which is is not the number of columns incremented by 1. But, even in this more general setting, we exhibit a relationship between the left kernels of the jacobian matrices and the syzygy module of the ideal spanned by the sequence under consideration. This allows us to prove a new F 5 -criterion dedicated to bilinear systems. On the one hand, when plugged into the Matrix F 5 Algorithm, this criterion detects reductions to zero which are not detected by the classical criterion. On the other hand, we prove that a D-Gröbner basis is still computed by the Matrix F 5 Algorithm when it uses the new criterion.

Jacobian matrices of bilinear systems and syzygies

From now on, we use the following notations:

• R = k[x 0 , . . . , x n x , y 0 , . . . , y n y ]; • F = ( f 1 , . . . , f m ) ⊂ R m is a sequence of bilinear polynomials and F i = ( f 1 , . . . , f i ) for 1 ≤ i ≤ m;
• I is the ideal generated by F and I i is the ideal generated by F i ;

• Let M be a ℓ × c matrix, with ℓ > c. We call maximal minors of M the determinants of the c × c sub-matrices of M;

• jac x (F i ) and jac y (F i ) are respectively the jacobian matrices

    ∂ f 1 ∂ x 0 • • • ∂ f 1 ∂ x nx . . . . . . . . . ∂ f i ∂ x 0 • • • ∂ f i ∂ x nx     and     ∂ f 1 ∂ y 0 • • • ∂ f 1 ∂ y ny . . . . . . . . . ∂ f i ∂ y 0 • • • ∂ f i ∂ y ny     ;
• Given a matrix M, Ker L (M) denotes the left kernel of M;

• X is the vector [x 0 , . . . , x n x ] t and Y is the vector [y 0 , . . . , y n y ] t ;

• ( f 1 , . . . , f m ) ∈ k[x 0 , . . . , x n x -1 , y 0 , . . . , y n y -1
] m is an affine bilinear system if there exists a homogeneous bilinear system

( f h 1 , . . . , f h m ) ∈ k[x 0 , . . . , x n x , y 0 , . . . , y n y ] m such that f i (x 0 , . . . , x n x -1 , y 0 , . . . , y n y -1 ) = f h i (x 0 , . . . , x n x -1 , 1, y 0 , . . . , y n y -1 , 1).
Lemma 2. Let i > n x + 1 (resp. i > n y + 1), and let s be a maximal minor of jac x (F i-1 ) (resp. jac y (F i-1 )). Then there exists a vector (s 1 , . . . ,

s i-1 , s) in Ker L (jac x (F i )) (resp. Ker L (jac y (F i ))).
Proof. The proof is done when considering s as a maximal minor of jac x (F i-1 ) with i > n x + 1. The case where s is a maximal minor of jac y (F i-1 ) with i > n y + 1 is proved similarly. Notice that jac x (F i-1 ) is a matrix with i -1 rows and n x + 1 columns and i -1 ≥ n x + 1. Denote by ( j 1 , . . . , j i-n x -2 ) the rows deleted from jac x (F i-1 ) to construct its submatrix J whose determinant is s.

Consider now the i × (in x -2)-matrix T such that its (ℓ, k) entry is 1 if and only if ℓ = j k , else it is 0. N denotes the following i × (i -1) matrix:

N = jac x (F i ) T .
A straightforward use of Cramer's rule shows that

(minor(N, 1), -minor(N, 2), . . . , (-1) i+1 minor(N, i)) ∈ Ker L (N).
Remark that this implies

(minor(N, 1), -minor(N, 2), . . . , (-1) i+1 minor(N, i)) ∈ Ker L (jac x (F i )).
Computing minor(N, i) by going across the last columns of N shows that minor(N, i) = ±s.

Theorem 2. Let i > n x + 1 (resp. i > n y + 1) and let s be a linear combination of maximal minors of jac x (F i-1 ) (resp. jac y (F i-1 )). Then s ∈ I i-1 : f i .
Proof. By assumption, s = ∑ ℓ a ℓ s ℓ where each s ℓ is a maximal minor of jac x (F i-1 ). According to Lemma 2, for each minor s ℓ there exists (s

(ℓ) 1 , . . . , s (ℓ) i-1 ) such that (s (ℓ) 1 , . . . , s (ℓ) i-1 , s ℓ ) ∈ Ker L (jac x (F i ))
Thus, by summation over ℓ, one obtains

( ∑ ℓ a ℓ s (ℓ) 1 , . . . , ∑ ℓ a ℓ s (ℓ) i-1 , s) ∈ Ker L (jac x (F i )).
(2)

Moreover, by Euler's formula

( ∑ ℓ a ℓ s (ℓ) 1 , . . . , ∑ ℓ a ℓ s (ℓ) i-1 , s)jac x (F i )X = s f i + i-1 ∑ j=1 ∑ ℓ a ℓ s (ℓ) j f j . By the relation (2), s f i + ∑ i-1 j=1 ∑ ℓ a ℓ s (ℓ) j f j = 0, which implies that s ∈ I i-1 : f i . Corollary 1. Let i > n x + 1 (resp. i > n y + 1), M (i) x (resp. M (i)
y ) be the ideal generated by the maximal minors of jac

x (F i ) (resp. jac y (F i )). Then M (i-1) x ⊂ I i-1 : f i (resp. M (i-1) y ⊂ I i-1 : f i ).
Proof. By Theorem 2, all minors of jac x (F i-1 ) (resp. jac y (F i-1 )) are elements of I i-1 : f i . Thus,

I i-1 : f i contains a set of generators of M (i-1) x (resp. M (i-1) y
). Since I i-1 : f i is an ideal, our assertion follows.

Example 1. Consider the following bilinear system in GF (7)[x 0 ,x 1 ,x 2 ,y 0 ,y 1 ,y 2 ,y 3 ]: f 1 = x 0 y 0 + 5x 1 y 0 + 4x 2 y 0 + 5x 0 y 1 + 3x 1 y 1 + x 0 y 2 + 4x 1 y 2 + 5x 2 y 2 + 5x 0 y 3 + x 1 y 3 + 2x 2 y 3 ,f 2 = 2x 0 y 0 + 4x 1 y 0 + 6x 2 y 0 + 2x 0 y 1 + 5x 1 y 1 + 6x 0 y 2 + 4x 2 y 2 + 3x 0 y 3 + 2x 1 y 3 + 4x 2 y 3 ,f 3 = 5x 0 y 0 + 5x 1 y 0 + 2x 2 y 0 + 4x 0 y 1 + 6x 1 y 1 + 4x 2 y 1 + 6x 1 y 2 + 4x 2 y 2 + x 0 y 3 + x 1 y 3 + 5x 2 y 3 ,f 4 = 6x 0 y 0 + 5x 2 y 0 + 4x 0 y 1 + 5x 1 y 1 + x 2 y 1 + x 0 y 2 + x 1 y 2 + 6x 2 y 2 + 2x 0 y 3 + 4x 1 y 3 + 5x 2 y 3 ,f 5 = 6x 0 y 0 + 3x 1 y 0 + 6x 2 y 0 + 3x 0 y 1 + 5x 2 y 1 + 2x 0 y 2 + 4x 1 y 2 + 5x 2 y 2 + 2x 0 y 3 + 4x 1 y 3 + 5x 2 y 3 . Its jacobian matrices jac x (F 4 ) and jac y (F 4 ) are:

jac x (F 4 ) =     y 0 + 5y 1 + y 2 + 5y 3
5y 0 + 3y 1 + 4y 2 + y 3 4y 0 + 5y 2 + 2y 3 2y 0 + 2y 1 + 6y 2 + 3y 3 4y 0 + 5y 1 + 2y 3 6y 0 + 4y 2 + 4y 3 5y 0 + 4y 1 + y 3 5y 0 + 6y 1 + 6y 2 + y 3 2y 0 + 4y 1 + 4y 2 + 5y 3 6y 0 + 4y 1 + y 2 + 2y 3 5y 1 + y 2 + 4y 3 5y

0 + y 1 + 6y 2 + 5y 3     . jac y (F 4 ) =     x 0 + 5x 1 + 4x 2 5x 0 + 3x 1 x 0 + 4x 1 + 5x 2 5x 0 + x 1 + 2x 2 2x 0 + 4x 1 + 6x 2 2x 0 + 5x 1 6x 0 + 4x 2 3x 0 + 2x 1 + 4x 2 5x 0 + 5x 1 + 2x 2 4x 0 + 6x 1 + 4x 2 6x 1 + 4x 2 x 0 + x 1 + 5x 2 6x 0 + 5x 2 4x 0 + 5x 1 + x 2 x 0 + x 1 + 6x 2 2x 0 + 4x 1 + 5x 2     .
An straightforward computation shows that the maximal minors of the matrix jac x (F 4 ) and jac y (F 4 ) are in f 1 , f 2 , f 3 , f 4 : f 5 , in accordance with Corollary 1. An example of a corresponding syzygy is obtained by the vanishing of the determinant

det [jac x (F 5 )|T |F 5 ]=det      y 0 + 5y 1 + y 2 + 5y 3 5y 0 + 3y 1 + 4y 2 + y 3 4y 0 + 5y 2 + 2y 3 1 f 1 2y 0 + 2y 1 + 6y 2 + 3y 3 4y 0 + 5y 1 + 2y 3 6y 0 + 4y 2 + 4y 3 0 f 2 5y 0 + 4y 1 + y 3 5y 0 + 6y 1 + 6y 2 + y 3 2y 0 + 4y 1 + 4y 2 + 5y 3 0 f 3 6y 0 + 4y 1 + y 2 + 2y 3 5y 1 + y 2 + 4y 3 5y 0 + y 1 + 6y 2 + 5y 3 0 f 4 6y 0 + 3y 1 + 2y 2 + 2y 3 3y 0 + 4y 2 + 4y 3 6y 0 + 5y 1 + 5y 2 + 5y 3 0 f 5      = 0.
The above results imply that for all g ∈ M

(i-1) x (resp. g ∈ M (i-1) y
), the rows of signature (LM(g), f i ) are reduced to zero during the Matrix F 5 Algorithm. In order to remove these rows, it is crucial to compute a Gröbner basis of the ideals M (i-1) x and M (i-1) y . These ideals are generated by the maximal minors of matrices whose entries are linear forms. The goal of the following section is to understand the structure of such ideals and how Gröbner bases can be efficiently computed in that case.

Gröbner bases and maximal minors of matrices with linear entries

Let L be the set of homogeneous linear forms in the ring R X = k[x 0 , . . . , x n x ], ≺ be the grevlex ordering on R X (with x 0 ≻ • • • ≻ x n x ) and Mat L (p, q) be the set of p × q matrices with entries in L with p ≥ q and n x ≥ pq. Note that Mat L (p, q) is a k-vector space of finite dimension.

Given M ∈ Mat L (p, q), we denote by MaxMinors(M) the set of maximal minors of M. We denote by Macaulay ≺ (MaxMinors(M), q) the Macaulay matrix in degree q associated to MaxMinors(M) and to the ordering ≺ (each row represents a polynomial of MaxMinors(M) and the columns represent the monomials of degree q in k[x 0 , . . . , x n x ] sorted by ≺, see Definition 5).

The main result of this paragraph lies in the following theorem: it states that, in general, a Gröbner basis of MaxMinors(M) is a linear combination of the generators. Theorem 3. There exists a nonempty Zariski-open set O in Mat L (p, q) such that for all M ∈ O, a grevlex Gröbner basis of MaxMinors(M) with respect to ≺ is obtained by computing the row echelon form of Macaulay ≺ (MaxMinors(M), q). This theorem is related with a result from Sturmfels, [START_REF] Bernstein | Combinatorics of maximal minors[END_REF], which states that the ideal generated by the maximal minors of a matrix whose entries are variables is a universal Gröbner Basis. We tried without success to use this result in order to prove Theorem 3. Therefore, we propose an ad-hoc proof, which is based on the following Lemmas whose proofs are postponed to the end of the paragraph. Lemma 3. Let Monomials p-q (q) be the set of monomials of degree q in k[x 0 , . . . ,

x p-q ]. There exists a Zariski-open subset O ′ of Mat L (p, q) such that for all M ∈ O ′ Monomials p-q (q) ⊂ LM( MaxMinors(M) )
Lemma 4. Let Monomials p-q (q) be the set of monomials of degree q in k[x 0 , . . . ,

x p-q ]. There exists a Zariski-open subset O ′′ of Mat L (p, q) such that for all M ∈ O ′′ LM( MaxMinors(M) ) ⊂ Monomials p-q (q) Lemma 5. The Zariski-open set O ′ ∩ O ′′ ⊂ Mat L (p, q) is nonempty. Proof of Theorem 3. From Lemmas 3, 4 and 5, O = O ′ ∩ O ′′ is a nonempty Zariski open set. Now let M be a matrix in O ⊂ Mat L (p, q). Monomials p-q (q) = LM( MaxMinors(M) ).
Thus all polynomials in a minimal Gröbner basis of MaxMinors(M) have degree q and then can be obtained by computing the row echelon form of Macaulay ≺ (MaxMinors(M), q). We prove now Lemmas 3, 4 and 5.

Proof of Lemma 3. Let M be the (p, q)-matrix whose (i, j)-entry is a generic homogeneous linear form ∑

n x k=0 a (i, j) k x k ∈ k(a (i, j) 0 , . . . , a (i, j) k )[x 0 , . . . , x n x ]. Denote by a the set a = {a (i, j) k , 0 ≤ k ≤ n x , 1 ≤ i ≤ p, 1 ≤ j ≤ q}. Given a set a = {a (i, j) k ∈ k, 0 ≤ k ≤ n x , 1 ≤ i ≤ p, 1 ≤ j ≤ q} consider the specialization map ϕ a : M → M a ∈ Mat L (p, q) such that the (i, j)-entry of M a is ∑ n x k=0 a (i, j) k x k ∈ k[x 0 , . . . , x n x ].
We prove below that there exists a polynomial g ∈ k[a] such that, if g(a) = 0 then Monomials p-q (q) ⊂ LM( MaxMinors(ϕ a (M)) ).

Consider the Macaulay matrix Macaulay ≺ (MaxMinors(M), q). Remark that the number of monomials in Monomials p-q (q) equals the number of maximal minors of M. Moreover, by construction of Macaulay ≺ (MaxMinors(M), q) and by definition of ≺ (see Definition 1), the first p q columns of Macaulay ≺ (MaxMinors(M), q) contain the coefficients of the monomials in Monomials p-q (q) of the polynomials in MaxMinors(M).

Saying that Monomials p-q (q) ⊂ LM( MaxMinors(M) ) is equivalent to saying that the determinant of the square submatrix of Macaulay ≺ (MaxMinors(M), q) containing its first p q columns is non-zero. Let g ∈ k[a] be this determinant.

The inequality g = 0 defines a Zariski-open set O ′ such that for all a ∈ O ′ Monomials p-q (q) ⊂ LM( MaxMinors(ϕ a (M)) ).

In the following ψ denotes the canonical inclusion morphism from k[x 0 , . . . ,

x n x ] to k ′ [x 0 , . . . , x p-q ],
where k ′ is the field of fractions k(x p-q+1 , . . . , x n x ).

For (v 1 , . . . , v n x -p+q ), ψ v denotes the specialization morphism:

ψ v : k[x 0 , . . . , x n x ] -→ k[x 0 , . . . , x p-q ] f (x 0 , . . . , x n x ) -→ f (x 0 , . . . , x p-q , v 1 , . . . , v n x -p+q ) Lemma 6. There exists a Zariski open set O ′′′ , such that if a ∈ O ′′′ , then the ideal MaxMinors(ψ • ϕ a (M)
) is radical and its degree is p q-1 .

Proof. There exists an affine bilinear system f 1 , . . . , f p ∈ k ′ (a)[x 0 , . . . , x p-q , y 0 , . . . , y q-2 ], such that:

ψ(M) •      y 0 . . . y q-2 1      =    f 1 . . . f p    .
Let I denote the ideal f 1 , . . . , f p . According to Lemma 17 (in Appendix), there exists a polynomial

h 1 ∈ k[a], such that if h 1 (a) = 0, then MaxMinors(ψ • ϕ a (M)) = ϕ a ( f 1 ), . . . , ϕ a ( f p ) ∩ k ′ [x 0 , . . . , x p-q ].
One remarks that there also exists a polynomial

h 2 ∈ k[a] such that if h 2 (a) = 0, then ϕ a (I) is 0-dimensional (since f 1 , . . . , f p
is a generic affine bilinear system with p equations and p variables, see Proposition 8). From Lemma 16 (in Appendix), there exists a polynomial h 3 such that if h 3 (a) = 0, then ϕ a (I) is radical. From now on, we suppose that h 1 (a)h 2 (a)h 3 (a) = 0. If (w 0 , . . . , w p-q ) ∈ Var( MaxMinors(ψ • ϕ a (M)) ) (where Var denotes the variety), then the set of points in Var(ϕ a (I)) whose projection is (w 0 , . . . , w p-q ) can be obtained by solving an affine linear system. The set of solutions of this system is nonempty and finite (since ϕ a (I) is 0-dimensional), thus it contains a unique element. So there is a bijection between Var(ϕ a (I)) and Var( MaxMinors(ψ • ϕ a (M)) ). As ϕ a (I) is radical,

deg(ϕ a (I)) = deg( MaxMinors(ψ • ϕ a (M)) ).
By Corollary 4, this degree is p q-1 . According to Lemma 3,

deg( MaxMinors(ψ • ϕ a (M)) ) ≤ deg( MaxMinors(ψ • ϕ a (M)) ) ≤ deg( Monomials p-q (q) ) = p q-1 . Therefore, deg( MaxMinors(ψ • ϕ a (M)) ) = deg( MaxMinors(ψ • ϕ a (M)) )
and thus

MaxMinors(ψ • ϕ a (M)) = MaxMinors(ψ • ϕ a (M)) .
Monomials p-q (q) ⊂ LM( MaxMinors(ψ • ϕ a (M)) ).
A basis of k ′ [x 0 , . . . , x p-q ]/ Monomials p-q (q) is given by the set of all monomials of degree less than q. Therefore, the dimension of k ′ [x 0 , . . . , x p-q ]/ Monomials p-q (q) (as a k ′ -vector space) is p q-1 . Thus, from Lemma 6,

deg( MaxMinors(ψ • ϕ a (M)) ) = p q -1 = deg( Monomials p-q (q) ).
Therefore, all polynomials in MaxMinors(ψ • ϕ a (M)) have degree at least q. Now let g = 0 be a polynomial in MaxMinors(ϕ a (M)) . Then there exists v = (v 1 , . . . , v n x -p+q ) such that the specialized polynomial verifies ψ v (g) = 0 and such that deg(

MaxMinors(ψ v • ϕ a (M)) ) = p q-1 . Thus ψ v (g) is a polynomial of degree at least q in k[x 0 , . . . , x p-q ]
. Now suppose by contradiction that LM(g) / ∈ Monomials p-q (q) . Since deg(ψ v (g)) ≥ q, there exists a monomial m in g such that m ∈ Monomials p-q (q) . Thus consider g 1 = g -λ m + λ NF(m) (where λ is the coefficient of m in g). One remarks that LM(g) = LM(g 1 ) /

∈ Monomials p-q (q) . Since g 1 ∈ MaxMinors(ϕ a (M)) , by a similar argument there also exists a monomial m 1 ∈ Monomials p-q (q) in g 1 . By induction construct the sequence

g i = g i-1 -λ i-1 m i-1 +λ i-1 NF(m i-1 ).
This sequence is infinite and strictly decreasing (for the induced partial ordering on polynomials:

h 1 ≺ h 2 if LM(h 1 ) ≺ LM(h 2 ) or if LM(h 1 ) = LM(h 2 ) and h 1 -LM(h 1 ) ≺ h 2 -LM(h 2 )).
But, when ≺ is the grevlex ordering, there does not exist such an infinite and strictly decreasing sequence.

Therefore LM(g) ∈ Monomials p-q (q) , which concludes the proof.

Proof of Lemma 5. In order to prove that the Zariski open set O ′ ∩ O ′′ is nonempty, we exhibit an explicit element. Consider the matrix M of Mat L (p, q) whose (i, j)-entry is x i+ j-2 if 0 ≤ i + j -2 ≤ pq and i ≥ j, else it is 0.

M =             x 0 0 . . . 0 x 1 x 0 . . . 0 . . . x 1 . . . . . . x p-q . . . . . . . . . . . . . . . . . . x p-q-1 0 0 . . . x p-q             .
Remark that MaxMinors(M) ⊂ k[x 0 , . . . , x p-q ]. Since Monomials p-q (q) is a zero-dimensional ideal in k[x 0 , . . . , x p-q ], the fact that LM(MaxMinors(M)) = Monomials p-q (q) implies that LM( MaxMinors(M) ) = Monomials p-q (q) . Thus, we prove in the sequel that LM(MaxMinors(M)) = Monomials p-q (q).

A first observation is that the cardinality of MaxMinors(M) equals the cardinality of Monomials p-q (q). Let m be a maximal minor of M. Thus m is the determinant of a q × q submatrix M ′ obtained by removing pq rows from M. Let i 1 , . . . , i p-q be the indices of these rows (with i 1 < . . . < i p-q ). Denote by ⋆ the product coefficient by coefficient of two matrices (i.e. the Hadamard product) and let S q be the set of q × q permutation matrices. Thus m = ∑ σ ∈S q (-1) sgn(σ ) det(σ ⋆ M ′ ).

Since for all σ ∈ S q , det(σ ⋆ M ′ ) is a monomial, there exists σ 0 ∈ S q such that LM(m) = ± det(σ 0 ⋆ M ′ )

We prove now that σ 0 = id. Suppose by contradiction that σ 0 = id. In the sequel, we denote by

• M ′ [i, j] the (i, j)-entry of M ′ .
• e i the q × 1 unit vector whose i-th coordinate is 1 and all its other coordinates are 0;

• σ 0 j is the integer i such that σ 0 e j = e i .

Since, by assumption, σ 0 = id, there exists 1 ≤ i < j ≤ q such that σ 0 j > σ 0 i . Because of the structure of M, we know that for the grevlex ordering

x 0 ≻ • • • ≻ x n x , M ′ [i, σ 0 j ]M ′ [ j, σ 0 i ] ≻ M ′ [i, σ 0 i ]M ′ [ j, σ 0 j ].
Let σ ′ be defined by

σ ′ k =      σ 0 k if k = i and k = j σ 0 j if k = i σ 0 i if k = j Then det(σ ′ ⋆ M ′ ) ≻ det(σ 0 ⋆ M ′ ) and by induction det(id ⋆ M ′ ) ≻ det(σ 0 ⋆ M ′ ). This also proves that the coefficient of det(id ⋆ M ′ ) in MaxMinors(M) is 1 and contradicts the fact that LM(m) = ± det(σ 0 ⋆ M ′ ). This proved that LM(m) = | det(id ⋆ M ′ )|. Now one can remark that det(id ⋆ M ′ ) = x i 1 -1 0 x i 2 -i 1 -1 1 x i 3 -i 2 -1 2 . . . x p-i p-q -1 p-q . Thus if m 1 , m 2 are distinct elements in MaxMinors(M), then LM(m 1 ) = LM(m 2 ).
Since for all m in MaxMinors(M), LM(m) ∈ Monomials p-q (q), and MaxMinors(M) has the same cardinality as Monomials p-q (q), we can deduce that LM(MaxMinors(M)) = Monomials p-q (q).

An extension of the F 5 criterion for bilinear systems

We can now present the main algorithm of this section. Given a sequence of homogeneous bilinear forms F = ( f 1 , . . . , f m ) ⊂ R generating an ideal I ⊂ R and ≺ a monomial ordering, it returns a set of pairs (g, f i ) such that g ∈ I i-1 : f i and g / ∈ I i-1 (for i > min(n x +1, n y +1)). Following Theorem 2 and 3, this is done by considering the matrices jac x (F i ) (resp. jac y (F i )) for i > n x +1 (resp. i > n y + 1) and performing a row echelon form on Macaulay ≺ (MaxMinors(jac x (F i )), n x + 1) (resp. Macaulay ≺ (MaxMinors(jac y (F i )), n y + 1)).

First we describe the subroutine Reduce (Algorithm 3) which reduces a set of homogeneous polynomials of the same degree: Algorithm 3. Reduce Require: ≺ a monomial ordering and (S, q) where S is a set of homogeneous polynomials of degree q. Ensure: T is a reduced set of homogeneous polynomials of degree q.

1: M ← Macaulay ≺ (S, q). 2: M ← RowEchelonForm(M).

3: Return T the set of polynomials corresponding to the rows of M.

The main algorithm uses this subroutine in order to compute a row echelon form of Macaulay ≺ (MaxMinors(jac x (F i )), n x 1) (resp. Macaulay ≺ (MaxMinors(jac y (F i )), n y + 1)):

Algorithm 4. BLcriterion

Require:

m bilinear polynomials f 1 , . . . , f m such that m ≤ n x + n y . ≺ a monomial ordering over k[x 0 , . . . , x n x , y 0 , . . . , y n y ] Ensure: V a set of pairs (h, f i ) such that h ∈ I i-1 : f i and h / ∈ I i-1 . 1: V ← / 0 2: for i from 2 to m do 3:

if i > n y + 1 then 4:
T ← Reduce(MaxMinors(jac y (F i-1 )), n y + 1).

5:

for h in T do

6: V ← V ∪ {(h, f i )} 7:
end for 8:

end if 9: if i > n x + 1 then 10: T ′ ← Reduce(MaxMinors(jac x (F i-1 )), n x + 1). 11: for h in T ′ do 12: V ← V ∪ {(h, f i )} 13:
end for 14: end if 15: end for 16: Return V

The following proposition explains how the output of Algorithm 4 is related to reductions to zero occurring during the Matrix F 5 Algorithm.

Proposition 1 (Extended F 5 criterion for bilinear systems). Let f 1 , . . . , f m be bilinear polynomials and ≺ be a monomial ordering. Let (t, f i ) be the signature of a row during the Matrix F 5 Algorithm and let V be the output of Algorithm BLCRITERION. Then if there exists (h, f i ) in V such that LM(h) = t, then the row with signature (t, f i ) will be reduced to zero.

Proof. According to Theorem 2, h f i ∈ I i-1 . Therefore

t f i = (h -t) f i + i-1 ∑ j=1 g j f j .
This implies that the row with signature (t, f i ) is a linear combination of preceding rows in Macaulay(F i , deg(t f i )). Hence this row will be reduced to zero. Now we can merge this extended criterion with the Matrix F 5 Algorithm. To do so, we denote by V the output of BLCRITERION (V has to be computed at the beginning of Matrix F 5 Algorithm), and we replace in Algorithm 2 the F 5 CRITERION by the following BILINF 5 CRITERION: Algorithm 5. BILINF 5 CRITERION -returns a boolean

Require:

(t, f i ) the signature of a row A matrix M in row echelon form

1: Return true if t is the leading monomial of a row of M or ∃(h, f i ) ∈ V such that LM(h) = t
4. F 5 without reduction to zero for generic bilinear systems

Main results

The goal of this part of the paper is to show that Algorithm 4 finds all reductions to zero for generic bilinear systems. In order to describe the structure of ideals generated by generic bilinear systems, we define a notion of bi-regularity (Definition 8). For bi-regular systems, we give a complete description of the syzygy module (Proposition 3 and Corollary 2). Finally, we show that, for such systems, Algorithm 4 finds all reductions to zero and that generic bilinear systems are bi-regular (Theorem 4), assuming a conjecture about the kernel of generic matrices whose entries are linear forms (Conjecture 1).

Kernel of matrices whose entries are linear forms

Consider a monomial ordering ≺ such that its restriction to k[x 0 , . . . , x n x ] (resp. k[y 0 , . . . , y n y ]) is the grevlex ordering (for instance the usual grevlex ordering with x 0 ≻ x 1 ≻ . . . ≻ y 0 ≻ . . . ≻ y n y ).

Let ℓ, c, n x be integers such that c < ℓ ≤ n x + c -1. Let M be the set of matrices ℓ × c whose coefficients are linear forms in k[x 0 , . . . , x n x ]. Let T be the set of ℓ × (ℓc -1) matrices T such that:

• each column of T has exactly one 1 and the rest of the coefficients are 0.

• each row of T has at most one 1 and all the other coefficients are 0.

• (T[i 1 , j 1 ] = T[i 2 , j 2 ] = 1 and i 1 < i 2 ) ⇒ j 1 < j 2
If T ∈ T and M ∈ M , we denote by M T the ℓ × (ℓ -1) matrix obtained by adding to M the columns of T. According to the proof of Lemma 2, some elements of the left kernel of a matrix M can be expressed as vectors of maximal minors:

∀T ∈ T ,      minor(M T , 1) -minor(M T , 2) . . . (-1) m+1 minor(M T , m)      ∈ Ker L (M).
Actually, we observed experimentally that kernels of random matrices M ∈ M are generated by those vectors of minors. This leads to the formulation of the following conjecture:

Conjecture 1. The set of matrices M ∈ M such that Ker L (M) =               minor(M T , 1) -minor(M T , 2) . . . (-1) m+1 minor(M T , m)               T∈T contains a nonempty Zariski open subset of M .

Structure of generic bilinear systems

With the following definition, we try to give an analog of regular sequences for bilinear systems. This definition is closely related to the generic behaviour of Algorithm 4. Definition 8. Let ≺ be a monomial ordering such that its restriction to k[x 0 , . . . , x n x ] (resp. k[y 0 , . . . , y n y ]) is the grevlex ordering. Let m ≤ n x + n y and f 1 , . . . , f m be bilinear polynomials of R. We say that the polynomial sequence

( f 1 , . . . , f m ) is a bi-regular sequence if m = 1 or if ( f 1 , . . . , f m-1
) is a bi-regular sequence and

LM(I m-1 : f m ) = Monomials x m-n y -2 (n y + 1) + Monomials y m-n x -2 (n x + 1) +LM(I m-1 )
In the following, we use the notations:

• BL (n x , n y ) the k-vector space of bilinear polynomials in K[x 0 , . . . , x n x , y 0 , . . . , y n y ];

• X (resp. Y ) is the ideal x 0 , . . . , x n x (resp. y 0 , . . . , y n y );

• An ideal is called bihomogeneous if it admits a set of bihomogeneous generators.

• J i denotes the saturated ideal I i : (X ∩Y ) ∞ ;

• Given a polynomial sequence ( f 1 , . . . , f m ), we denote by Syz triv the module of trivial syzygies, i.e. the set of all syzygies (s 1 , . . . , s m ) such that ∀i, s i ∈ f 1 , . . . , f i-1 , f i+1 , . . . , f m ;

• A primary ideal P ⊂ R is called admissible if X ⊂ √ P and Y ⊂ √ P;

• Let E be a k-vector space such that dim(E) < ∞. We say that a property P is generic if it is satisfied on a nonempty open subset of E (for the Zariski topology), i.e. ∃h ∈ k[a 1 , . . . , a dim(E) ], h = 0, such that

P does not hold on (a 1 , . . . , a dim(E) ) ⇒ h(a 1 , . . . , a dim(E) ) = 0.
Without loss of generality, we suppose in the sequel that n x ≤ n y .

Lemma 7. Let I m be an ideal spanned by m generic bilinear equations f 1 , . . . , f m and I m = ∩ P∈P P be a minimal primary decomposition.

• If m < n x + 1, then all components of I m are admissible.

• If n x + 1 ≤ m < n y + 1 and P 0 ∈ P is a primary non-admissible component, then Y ⊂ √ P 0 .

Proof. We prove that if m < n x + 1 (resp. m < n y + 1) and P 0 is a primary non-admissible component, then X ⊂ √ P 0 (resp. Y ⊂ √ P 0 ). Lemma 7 is a consequence of this fact. Consider the field k ′ = k(y 0 , . . . , y n y ) and the canonical inclusion

ψ : R → k ′ [x 0 , . . . , x n x ]. ψ(I m ) is an ideal of k ′ [x 0 , . . . , x n x ] spanned by m polynomials in k ′ [x 0 , . . . , x n x ]. Generically, (ψ( f 1 ), . . . , ψ( f m )) is a regular sequence of k ′ [x 0 , . . . , x n x ].
Thus there exists an polynomial f ∈ X (homogeneous in the x i s) such that ψ( f ) is not a divisor of 0 in k ′ [x 0 , . . . , x n x ]/ψ(I m ). This means that ψ(I m ) : ψ( f ) = ψ(I m ). Suppose the assertion of Lemma 7 is false. Then X ⊂ √ P 0 and hence, f ∈ √ P 0 . Therefore there exists g ∈ k[y 0 , . . . ,

y n y ] such that, in R, g f ∈ √ I m (take g in (∩ P∈P\{P 0 } √ P) \ { √ P 0 } which is nonempty). Thus ψ( f ) ∈ ψ(I m ) (since ψ(g) is invertible in k ′ ), which is impossible since ψ(I m ) : ψ( f ) = ψ(I m ).

Lemma 8.

• If m ≤ n x there exists a nonempty Zariski-open set O ⊂ BL K (n x , n y ) m such that ( f 1 , . . . , f m ) ⊂ O implies that I m has codimension m and all the components of a minimal primary decomposition of I m are admissible;

• if n x + 1 ≤ m, then there exists a nonempty Zariski-open set O ⊂ BL K (n x , n y ) m such that ( f 1 , . . . , f m ) ⊂ O implies that X is a prime associated to √ I m ; • if n y + 1 ≤ m, then there exists a nonempty Zariski-open set O ⊂ BL K (n x , n y ) m such that ( f 1 , . . . , f m ) ⊂ O implies that Y is a prime associated to √ I m .
Proof.

• If m ≤ n x , then by Lemma 7, J m = I m . Then according to Theorem 7, there exists a nonempty Zariski-open set O ⊂ BL K (n x , n y ) m such that ( f 1 , . . . , f m ) ⊂ O implies that ( f 1 , . . . , f m ) is a regular sequence. Therefore, I m has codimension m and all the components of a minimal primary decomposition of I m are admissible.

• If n x + 1 ≤ m, then according to Proposition 8, J m = (I m : Y ∞ ) : X ∞ is equidimensional of codimension m. Let V x be the set {(0, . . . , 0, a 0 , . . . , a n y )|a i ∈ k}. Since V x ⊂ Var(I m : Y ∞ ) and codim(V x ) = n x +1, it can be deduced that V x ⊂ Var(J m ) and Var(I m :

Y ∞ ) = Var(J m )∪ V x . This means that √ I m : Y ∞ = √ J m ∩ X and √ J m ⊂ X. Thus X is a prime associated to √ I m : Y ∞ . Since Y is not a subset of X, X is also a prime ideal associated to √ I m .
• Similar proof in the case n y + 1 ≤ m.

Lemma 9. Suppose that the local ring R X /I X (resp. R Y /I Y ) is regular and that X (resp. Y ) is a prime ideal associated to √ I and let Q be an isolated primary component of a minimal primary decomposition of I containing X (resp. Y ). Then Q = X (resp. Q = Y ).

Proof. By assumption, X is a prime ideal associated to √ I. Then, there exists an isolated primary component of a minimal primary decomposition of I which contains a power of X and does not meet R \ X. This proves that I X does not contain a unit in R X .

By assumption R X /I X is regular and local, then R X /I X is an integral ring (see e.g. (Eisenbud, 1995, Corollary 10.14)) which implies that I X is prime and does not contain a unit in R X .

Let

I = Q 1 ∩ • • • ∩ Q s be
a minimal primary decomposition of I. In the sequel, Q i X denotes the localization of Q i by X. Suppose first that there exists 1 ≤ i ≤ s such that I X = Q i X with Q i nonadmissible which does not meet the multiplicatively closed part R \ X . Then Q i X is obviously prime which implies that Q i itself is prime (Atiyah and MacDonald, 1969, Proposition 3.11 (iv)). Our claim follows.

It remains to prove that I X = Q i X for some 1 ≤ i ≤ s. Suppose that the Q i 's are numbered such that Q j meets the multiplicatively closed set R \ X for r

+ 1 ≤ j ≤ s but not Q 1 , . . . , Q r . I X = Q 1 X ∩ • • • ∩ Q r X
and it is a minimal primary decomposition (Atiyah and MacDonald, 1969, Proposition 4.9). Hence, since I X is prime, r = 1 and Q 1 is the isolated minimal primary component containing X.

Proposition 2. Let k be a field of characteristic 0. There exists a nonempty Zariski-open set O ⊂ BL (n x , n y ) m such that for all ( f 1 , . . . , f m ) ⊂ O the non-admissible components of a minimal primary decomposition of f 1 , . . . , f m are either X or Y .

Proof. Suppose that n x + 1 ≤ m. Then, by Lemma 8, there exists a nonempty Zariski-open set O 1 such that X is an associated prime to √ I. Note also that this implies that I X has codimension n x + 1. Thus, by Lemma 9, it is sufficient to prove that there exists a nonempty Zariski-open set O 2 such that for all ( f 1 , . . . ,

f m ) ∈ O 1 ∩ O 2 , R X /I X is a regular local ring.
From the Jacobian Criterion (see e.g. Eisenbud (1995), Theorem 16.19), the local ring R X /I X is regular if and only if jac( f 1 , . . . , f m ) taken modulo X has codimension n x + 1. Since the generators of I are bilinear, the latter condition is equivalent to saying that the matrix

J X =     ∂ f 1 ∂ x 0 • • • ∂ f 1 ∂ x nx . . . • • • . . . ∂ f m ∂ x 0 • • • ∂ f m ∂ x nx    
has rank n x + 1. We prove below that there exists a nonempty Zariski-open set O 3 such that for all ( f 1 , . . . , f m ) ∈ O 3 , J X has rank n x + 1. Let c 1 , . . . , c m be vectors of coordinates of BL (n x , n y ) m , M be the vector of all bilinear monomials in R and K be the field of rational fractions k(c 1 , . . . , c m ). Consider the polynomials g i = M.c T i for 1 ≤ i ≤ m and the Zariski-open set O 3 in BL (n x , n y ) m defined by the non-vanishing of all the coefficients of the maximal minors of the generic matrix

J X =     ∂ g 1 ∂ x 0 • • • ∂ g 1 ∂ x nx . . . • • • . . . ∂ g m ∂ x 0 • • • ∂ g m ∂ x nx     .
It is obvious that ( f 1 , . . . , f m ) ∈ O 3 implies that J X has rank n x + 1; our claim follows.

In the case where n y ≤ m, the proof follows the same pattern using Lemmas 8 and 9 and the Jacobian criterion. The only difference is that one has to prove that there exists a nonempty Zariski-open set O 4 such that for all ( f 1 , . . . , f m ) ∈ O 4 the matrix

J Y =     ∂ f 1 ∂ y 0 • • • ∂ f 1 ∂ y nx . . . • • • . . . ∂ f m ∂ y 0 • • • ∂ f m ∂ y ny    
has rank n y + 1, which is done as above.

Remark 2. The proof of Proposition 2 relies on the use of the Jacobian Criterion. From (Eisenbud, 1995, Theorem 16.19), it remains valid if the characteristic of k is large enough so that the residue class field of X (resp. Y ) is separable.

The two following propositions explain why the rows reduced to zero in the generic case during the F 5 Algorithm have a signature (t, f i ) such that t ∈ k[x 0 , . . . , x n x ] or t ∈ k[y 0 , . . . , y n y ].

Proposition 3. Let m be an integer such that m ≤ n x + n y . Let L be the set of bilinear systems with m polynomials (L ⊂ R m ). Then the set of bilinear systems f 1 , . . . ,

f m such that Syz = (Syz ∩ k[x 0 , . . . , x n x ] m ) ∪ (Syz ∩ k[y 0 , . . . , y n y ] m ) ∪ Syz triv contains a nonempty Zariski-open subset of L.
Proof. Let s = (s 1 , . . . , s m ) be a syzygy. Thus, s m is in I m-1 : f m . We can suppose without loss of generality that the s i are bihomogeneous of same bidegree (Proposition 6). According to Theorem 7, there exists a nonempty Zariski open set

O 1 ⊂ BL (n x , n y ) m , such that if ( f 1 , . . . , f m ) ∈ O 1 , then f m is not a divisor of 0 in R/J m-1 .
We can deduce from this observation that s m ∈ J m-1 . So s m ∈ I m-1 or there exists P a non-admissible primary component of I m-1 such that s m / ∈ P. Assume that s m / ∈ I m-1 . From Proposition 2, there exists a nonempty Zariski open set

O 2 ⊂ BL (n x , n y ) m , such that if ( f 1 , . . . , f m ) ∈ O 2 ,
then x 0 , . . . , x n x = P (or y 0 , . . . , y n y = P), which implies that s m ∈ k[y 0 , . . . , y n y ] (or s m ∈ k[x 0 , . . . , x n x ]).

Finally, we see that, if

( f 1 , . . . , f m ) ∈ O 1 ∩ O 2 , then s m ∈ I m-1 ∪ k[y 0 , . . . , y n y ] ∪ k[x 0 , . . . , x n x ].
Since the syzygy module of a bihomogeneous system is generated by bihomogeneous syzygies, it can be deduced that Syz

= (Syz ∩ k[x 0 , . . . , x n x ] m ) ∪ (Syz ∩ k[y 0 , . . . , y n y ] m ) ∪ Syz triv .
Proposition 4. Let V be the output of Algorithm BLCRITERION and let (h, f i ) be an element of V . Then

• if h ∈ k[x 0 , . . . , x n x ], then ∀ j, y j h ∈ I i-1 . • if h ∈ k[y 0 , . . . , y n y ], then ∀ j, x j h ∈ I i-1 .
Proof. Suppose that h ∈ k[x 0 , . . . , x n x ] is a maximal minor of jac y (F i-1 ) (the proof is similar if h ∈ k[y 0 , . . . , y n y ]). Consider the matrix jac y (F i-1 ) as defined in Algorithm 4. Then there exists an (i -1) × (i -1) extension M T of jac y (F i-1 ) such that det(M T ) = h (similarly to the proof of Lemma 2). Let 0 ≤ j ≤ n y be an integer. Consider the polynomials h 1 , . . . , h i-1 , where h k is the determinant of the (i -2) × (i -2) matrix obtained by removing the ( j + 1)th column and the kth row from M T .

Then we can remark that

h 1 -h 2 . . . (-1) i h i-1 • M T = 0 . . . 0 (-1) j det(M T ) 0 . . . 0
where the only non-zero component is in the ( j + 1)th column. Keeping only the n y + 1 first columns of M T , we obtain

h 1 -h 2 . . . (-1) i h i-1 • jac y (F i-1 ) = 0 . . . 0 (-1) j det(M T ) 0 . . . 0 Since jac y (F i-1 ) •    y 0 . . . y n y    =    f 1 . . . f i-1   , the following equality holds h 1 -h 2 . . . (-1) i-1 h i-2 (-1) i h i-1 •    f 1 . . . f i-1    = y j det(M T ) = y j h.
This implies that y j h ∈ I i-1 .

Corollary 2. Let m be an integer such that m ≤ n x +n y and let f 1 , . . . , f m be bilinear polynomials. Let V be the output of Algorithm BLCRITERION. Assume that

(I m-1 : f m ) ∩ k[x 0 , . . . , x n x ] = {h ∈ k[x 0 , . . . , x n x ] : (h, f m ) ∈ V } . (I m-1 : f m ) ∩ k[y 0 , . . . , y n y ] = {h ∈ k[y 0 , . . . , y n y ] : (h, f m ) ∈ V } . Let G x (resp G y ) be a Gröbner basis of (I m-1 : f m )∩k[x 0 , . . . , x n x ] (resp. (I m-1 : f m )∩k[y 0 , . . . , y n y ]) and let G m-1 be a Gröbner basis of I m-1 . If Syz = (Syz∩k[x 0 , . . . , x n x ] m )∪(Syz∩k[y 0 , . . . , y n y ] m )∪ Syz triv , then G x ∪ G y ∪ G m-1 is a Gröbner basis of I m-1 : f m .
Proof. Let f ∈ I m-1 : f m be a polynomial. Thus there exist s 1 , . . . , s m-1 such that (s 1 , . . . , s m-1 , f ) ∈ Syz. Since I m-1 and f m are bihomogeneous, we can suppose without loss of generality that f is bihomogeneous (Proposition 6). Let (d 1 , d 2 ) denote its bidegree.

• If d 2 = 0 (resp. d 1 = 0), then f ∈ G x (resp. f ∈ G y ). • Let G x = {g (x) i } 1≤i≤card(G x ) and G y = {g (y) i } 1≤i≤card(G y ) . If d 1 = 0 and d 2 = 0 then, since Syz = (Syz ∩ k[x 0 , . . . , x n x ] m ) ∪ (Syz ∩ k[y 0 , . . . , y n y ] m ) ∪ Syz triv , f = ∑ 1≤i≤card(G x ) q i g (x) i + ∑ 1≤i≤card(G y ) q ′ i g (y) i + t
where t ∈ I m-1 is a bihomogeneous polynomial and the q i and q ′ i are also bihomogeneous. Since d 2 = 0 and g (x) i ∈ k[x 0 , . . . , x n x ], q i must be in y 0 , . . . , y n y . According to Proposition 4, ∀i, q i g (x)

i ∈ I m-1 . By a similar argument, ∀i, q ′ i g

(y) i ∈ I m-1 . Finally, f ∈ I m-1 .
We just proved that I m-1 :

f m ⊂ I m-1 ∪ G x ∪ G y .
By construction, we also have the other inclusion

I m-1 ∪ G x ∪ G y ⊂ I m-1 : f m . Thus, G x ∪ G y ∪ G m-1 is a Gröbner basis of I m-1 : f m .
Corollary 2 shows that, when a bilinear system is bi-regular, it is possible to find a Gröbner basis of I m-1 : f m (which yields the monomials t such that the row (t, f m ) reduces to zero) as soon as we know the three Gröbner bases G x , G y , and G m-1 . In fact, we only need G x and G y since the reductions to zero corresponding to G m-1 are eliminated by the usual F 5 criterion. Fortunately, we can obtain G x and G y just by performing linear algebra over the maximal minors of a matrix (Theorem 3).

We now present the main result of this section. If we suppose that Conjecture 1 is true, then the following Theorem shows that generic bilinear systems are bi-regular.

Theorem 4. Let m, n x , n y ∈ N such that m < n x + n y . If Conjecture 1 is true, then the set of bi- regular sequences ( f 1 , . . . , f m ) contains a nonempty Zariski-open set. Moreover, if ( f 1 , . . . , f m
) is a bi-regular sequence, then there are no reductions to zero with the extended F 5 criterion.

Proof. Let G m be a minimal Gröbner basis of I m-1 : f m . The reductions to zero (t, f m ) which are not detected by the usual F 5 criterion are exactly those such that t ∈ LM(G m ) and t / ∈ LM(I m-1 ). We showed that there exists a nonempty Zariski-open subset

O 1 of BL (n x , n y ) such that if f m ∈ O 1 , then t ∈ LM(I m-1 : f m ∩ k[x 0 , . . . , x n x ]) or t ∈ LM(I m-1 : f m ∩ k[y 0 , . . . , y n y ]) 22
(Proposition 3). If we suppose that Conjecture 1 is true, then there exists a nonempty Zariski-

open subset O 2 of BL (n x , n y ) such that if f m ∈ O 2 , I m-1 : f m ∩ k[x 0 , . . . , x n x ] (resp. I m-1 : f m ∩ k[y 0 , . . . , y n y ]
) is spanned by the maximal minors of jac x (F m-1 ) (resp. jac y (F m-1 )). Thus, by Theorem 3, there exists a nonempty Zariski-open subset

O 3 of BL (n x , n y ) such that if f m ∈ O 3 , LM(I m-1 : f m ∩ k[x 0 , . . . , x n x ]) = Monomials x m-n y -2 (n y + 1) (resp. LM(I m-1 : f m ∩ k[y 0 , . . . , y n y ]) = Monomials y m-n x -2 (n x +1) ). Suppose that f m ∈ O 1 ∩O 2 ∩O 3 (which is a nonempty Zariski-open subset) and that (t, f m ) is a reduction to zero such that t / ∈ LM(I m-1 ). Then t ∈ Monomials x m-n y -2 (n y + 1) or t ∈ Monomials y m-n x -2 (n x + 1)
. By Lemma 3, t is a leading monomial of a linear combination of the maximal minors of jac x (F m-1 ) (or jac y (F m-1 )). Consequently, the reduction to zero (t, f m ) is detected by the extended F 5 criterion.

Remark 3. Thanks to the analysis of Algorithm 4, we know exactly which reductions to zero can be avoided during the computation of a Gröbner basis of a bilinear system. If a bilinear system is bi-regular, then Algorithm 4 finds all reductions to zero. Indeed, this algorithm detects reductions to zero coming from linear combinations of maximal minors of the matrices jac x (F i ) and jac y (F i ). According to Theorem 4, there are no other reductions to zero for bi-regular systems.

Example 1 (continued). The system f 1 , . . . , f 5 given in Example 1 is bi-regular and there are no reduction to zero during the computation of a Gröbner basis with the extended F 5 criterion.

Hilbert bi-series of bilinear systems

An important tool to describe ideals spanned by bilinear equations is the so-called Hilbert series. In the homogeneous case, complexity results for F 5 were obtained with this tool (see e.g. [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]). In this section, we provide an explicit form of the Hilbert bi-series -a bihomogeneous analog of the Hilbert series -for ideals spanned by generic bilinear systems. To find this bi-series, we use the combinatorics of the syzygy module of bi-regular systems. With this tool, we will be able to do a complexity analysis of a special version of the F 5 which will be presented in the next section.

The following notation will be used throughout this paper: the vector space of bihomogeneous polynomials of bidegree (α, β ) will be denoted by R α,β . If I is a bihomogeneous ideal, then I α,β will denote the vector space I ∩ R α,β .

Definition 9 (Van der Waerden (1929); Safey El [START_REF] El Din | Strong bi-homogeneous Bézout theorem and its use in effective real algebraic geometry[END_REF]). Let I be a bihomogeneous ideal of R. The Hilbert bi-series is defined by

HS I (t 1 ,t 2 ) = ∑ (α,β )∈N 2 dim(R α,β /I α,β )t α 1 t β 2 .
Remark 4. The usual univariate Hilbert series for homogeneous ideals can easily be deduced from the Hilbert bi-series by putting t 1 = t 2 (see Safey El [START_REF] El Din | Strong bi-homogeneous Bézout theorem and its use in effective real algebraic geometry[END_REF]).

We can now present the main result of this section: an explicit form of the bi-series for bi-regular bilinear systems.

Theorem 5. Let f 1 , . . . , f m ∈ R be a bi-regular bilinear sequence, with m ≤ n x + n y . Then

HS I m (t 1 ,t 2 ) = N m (t 1 ,t 2 ) (1 -t 1 ) n x +1 (1 -t 2 ) n y +1 , where N m (t 1 ,t 2 ) = (1 -t 1 t 2 ) m + ∑ m-(ny+1) ℓ=1 (1 -t 1 t 2 ) m-(ny+1)-ℓ t 1 t 2 (1 -t 2 ) ny+1 1 -(1 -t 1 ) ℓ ∑ ny+1 k=1 t ny+1-k 1 ℓ+ny-k ny+1-k + ∑ m-(nx+1) ℓ=1 (1 -t 1 t 2 ) m-(nx+1)-ℓ t 1 t 2 (1 -t 1 ) nx+1 1 -(1 -t 2 ) ℓ ∑ nx+1 k=1 t nx+1-k 2 ℓ+nx-k nx+1-k .
We decompose the proof of this theorem into a sequence of lemmas.

If I is an ideal of R and f is a polynomial, we denote by f the equivalence class of f in R/I and ann

R/I ( f ) = {v ∈ R/I : v f = 0}, ann R/I ( f ) α,β = {v ∈ R/I of bidegree (α, β ) : v f = 0}.
If I is a bihomogeneous ideal and f is a bihomogeneous polynomial, we use the following notation:

G I, f (t 1 ,t 2 ) = ∑ (α,β )∈N 2 dim(ann R/I ( f ) α,β )t α 1 t β 2 . Lemma 10. Let f 1 , . . . , f m ∈ R be bihomogeneous polynomials, with 1 < m ≤ n x +n y . Let (d 1 , d 2 )
be the bidegree of f m . Then

HS I m (t 1 ,t 2 ) = (1 -t d 1 1 t d 2 2 )HS I m-1 + t d 1 1 t d 2 2 G I m-1 , f (t 1 ,t 2 ).
Proof. We have the following exact sequence:

0 → ann R/I m-1 ( f ) ϕ 1 -→ R/I m-1 ϕ 2 -→ R/I m-1 ϕ 3 -→ R/I m → 0.
where ϕ 1 and ϕ 3 are the canonical inclusion and projection, and ϕ 2 is the multiplication by f m . From this exact sequence of ideals, we can deduce an exact sequence of vector spaces:

0 → (ann R/I m-1 ( f )) α,β ϕ 1 -→ R I m-1 α,β ϕ 2 -→ R I m-1 α+d 1 ,β +d 2 ϕ 3 -→ R I m α+d 1 ,β +d 2 → 0.
Thus the alternate sum of the dimensions of vector spaces of an exact sequence is 0:

dim((ann R/I m-1 ( f )) α,β ) -dim R I m-1 α,β + dim R I m-1 α+d 1 ,β +d 2 -dim R I m α+d 1 ,β +d 2 = 0.
By multiplying this relation by t α 1 t β 2 and by summing over (α, β ), we obtain the claimed recurrence:

HS I m (t 1 ,t 2 ) = (1 -t d 1 1 t d 2 2 )HS I m-1 + t d 1 1 t d 2 2 G I m-1 , f (t 1 ,t 2 ).
Lemma 11. Let f 1 , . . . , f m ∈ R be a bi-regular bilinear sequence, with m ≤ n x + n y . Then, for all

2 ≤ i ≤ m, G I i-1 , f i (t 1 ,t 2 ) = g (i-1) x (t 1 ) + g (i-1) y (t 2 ),
where

g (i-1) x (t) =    0 if i ≤ n y + 1 1 (1-t) nx+1 -∑ 1≤ j≤n y +1 ( i-1-j ny+1-j )t ny+1-j (1-t) nx+ny-i+2
.

g (i-1) y (t) =    0 if i ≤ n x + 1 1 (1-t) ny+1 -∑ 1≤ j≤n x +1 ( i-1-j nx+1-j )t nx+1-j (1-t) nx+ny-i+2
.

Proof. Saying that v ∈ ann R/I i-1 ( f i ) is equivalent to saying that the row with signature (LM(v), f i ) is not detected by the classical F 5 criterion. According to Theorem 4, if the system is bi-regular, the reductions to zero corresponding to non-trivial syzygies are exactly:

m i=nx+2 {(t, f i ) : t ∈ Monomials y i-nx-2 (n x + 1)} m i=ny+2 {(t, f i ) : t ∈ Monomials x i-ny-2 (n y + 1)}.
By Proposition 4, we know that if

P ∈ k[x 0 , . . . , x n x ] ∩ (I i-1 : f i ) (resp. k[y 0 , . . . , y n y ] ∩ (I i-1 : f i )), then ∀ j, y j P ∈ I i-1 (resp. x j P ∈ I i-1 ). Thus G I i-1 , f i (t 1 ,t 2 )
is the generating bi-series of the monomials in k[x 0 , . . . , x n x ] which are a multiple of a monomial of degree n y + 1 in x 0 , . . . , x i-n y -2 and of the monomials in k[y 0 , . . . , y n y ] which are a multiple of a monomial of degree n x + 1 in y 0 , . . . , y i-n x -2 . Denote by g

(i-1) x (t) (resp. g (i-1) y (t)
) the generating series of the monomials in k[x 0 , . . . , x n x ] (resp. k[y 0 , . . . , y n y ]) which are a multiple of a monomial of degree n y + 1 (resp. n x + 1) in x 0 , . . . , x i-n y -2 (resp. y 0 , . . . , y i-n x -2 ). Then we have

G I i-1 , f i (t 1 ,t 2 ) = g (i-1) x (t 1 ) + g (i-1) y (t 2 ).
Next we use combinatorial techniques to give an explicit form of g (i-1) x (t) and g (i-1) y (t). Let c(t) denote the generating series of the monomials in k[x i-n y -1 , . . . , x n x ]:

c(t) = ∞ ∑ j=0 n x + n y -i + j + 1 j t j = 1 (1 -t) n x +n y -i+2 .
Let B j denote the number of monomials in k[x 0 , . . . , x i-n y -2 ] of degree j. Then

1 (1 -t) n x +n y +2 = c(t) + B 1 c(t)t + • • • + B n y c(t)t n y + g (i-1) x (t).
Since B j = i-n y -1+ j j , we can conclude:

g (i-1) x (t) =    0 if i ≤ n y + 1 1 (1-t) nx+1 -∑ 1≤ j≤n y +1 ( i-1-j ny+1-j )t ny+1-j (1-t) nx+ny-i+2
.

Proof of Theorem 5. Since the polynomials are bilinear, by Lemma 10, we have

HS I i (t 1 ,t 2 ) = (1 -t 1 t 2 )HS I i-1 + t 1 t 2 G I i-1 , f i (t 1 ,t 2 ).
Lemma 11 gives the value of G I i-1 , f i (t 1 ,t 2 ). To initiate the recurrence, we need

HS I 0 (t 1 ,t 2 ) = HS 0 (t 1 ,t 2 ) = 1 (1 -t 1 ) n x +1 (1 -t 2 ) n y +1 .
Then we can obtain the claimed form of the bi-series by solving the recurrence:

HS I i (t 1 ,t 2 ) = N i (t 1 ,t 2 ) (1 -t 1 ) n x +1 (1 -t 2 ) n y +1 N i (t 1 ,t 2 ) = (1 -t 1 t 2 ) i + m-1 ∑ j=0 t 1 t 2 (1 -t 1 t 2 ) j G I j , f j+1 (t 1 ,t 2 ).
Example 1 (continued). The Hilbert bi-series of the ideal generated by the five polynomials of Example 1 is

HS(t 1 ,t 2 ) = 1 (1-t 1 ) 3 (1-t 2 ) 4 (t 1 5 t 2 5 -4t 1 5 t 2 4 + 6t 1 5 t 2 3 -4t 1 5 t 2 2 + t 1 5 t 2 -6t 1 3 t 2 5 + 15t 1 3 t 2 4 -10t 1 3 t 2 3 + 8t 1 2 t 2 5 -15t 1 2 t 2 4 + 10t 1 2 t 2 2 -3t 1 t 2 5 + 5t 1 t 2 4 -5t 1 t 2 + 1),
and is in accordance with the formula given in Theorem 5. Also, notice that the intermediate series g x (t) and g y (t) match the theoretical values. For instance: g

(3)

y = t 3 (1 -t) 4 .

Towards complexity results

A multihomogeneous F 5 Algorithm

We now describe how it is possible to use the multihomogeneous structure of the matrices arising in the Matrix F 5 Algorithm to speed-up the computation of a Gröbner basis. In order to have simple notations, the description is made in the context of bihomogeneous systems, but it can be easily transposed in the context of multihomogeneous systems.

Let f 1 , . . . , f m be a sequence of bihomogeneous polynomials. Consider the matrices M d in degree d appearing during the Matrix F 5 Algorithm. One can remark that each row represents a bihomogeneous polynomial. Let (d 1 , d 2 ) be the bidegree of one row of this matrix. Then the only non-zero coefficients on this row are in columns which represent a monomial of bidegree (d 1 , d 2 ). Therefore a possible strategy to use the bihomogeneous structure is the following: This way, instead of computing the row echelon form of a big matrix, we can decompose the problem and compute independently the row echelon form of smaller matrices. This strategy can be extended to multihomogeneous systems.

• For each couple (d 1 , d 2 ) such that d 1 + d 2 = d, construct the matrix M d 1 ,d 2 .
In Table 1, the execution time and the memory usage of this multihomogeneous variant of F 5 are compared to the classical homogeneous Matrix F 5 Algorithm for computing a D-Gröbner basis for random bihomogeneous systems (for the grevlex ordering). Both implementations are made in Magma2.15-7. The experimental results have been obtained with a Xeon processor 2.50GHz cores and 20 GB of RAM. We are aware that we should compare efficient implementations of these two algorithms to have a more precise evaluation of the speed-up we can expect for practical applications. However, these experiments give a first estimation of that speed-up. Furthermore, we can also expect to save a lot of memory by decomposing the Macaulay matrix into smaller matrices. This is crucial for practical applications, since untractability is often due to the lack of memory.

A theoretical complexity analysis in the bilinear case

In this section, we provide a theoretical explanation of the speed-up observed when using the bihomogeneous structure of bilinear systems. To estimate the complexity of the Matrix F 5 Algorithm, we consider that the cost is dominated by the cost of the reductions of the matrices with the highest degree. By using the new criterion described in Section 3.4, all the matrices appearing during the computations have full rank for generic inputs (these ranks are the dimensions of the k-vector spaces I d 1 ,d 2 ). We consider that the complexity of reducing a r × c matrix with Gauss elimination is O(r 2 c). Thus the complexity of computing a D-Gröbner basis with the usual Matrix F 5 Algorithm and the extended criterion for a bilinear system of m equations over k[x 0 , . . . , x n x , y 0 , . . . , y n y ] is When using the multihomogeneous structure, the complexity becomes:

T hom = C 1 D + n x + n y + 1 D -[t D ]
T multihom = C 2    ∑ d 1 +d 2 =D 1≤d 1 ,d 2 ≤D-1 dim(R d 1 ,d 2 ) -[t d 1 1 t d 2 2 ]HS(t 1 ,t 2 ) 2 dim(R d 1 ,d 2 )    , where dim(R d 1 ,d 2 ) = d 1 +n x d 1 d 2 +n y d 2
. Thus the theoretical speed-up that we expect is:

speedup th = C 3 F(n x , n y , m, D)
where

C 3 = C 1 C 2 is a constant and F(n x , n y , m, D) =        D+n x +n y +1 D -[t D ]HS(t,t) 2 D+n x +n y +1 D ∑ d 1 +d 2 =D 1≤d 1 ,d 2 ≤D-1 dim(R d 1 ,d 2 ) -[t d 1 1 t d 2 2 ]HS(t 1 ,t 2 ) 2 dim(R d 1 ,d 2 )       
. Now let us compare this theoretical speed-up with the one observed in practice. We can see in Table 2 that experimental results match the theoretical complexity: speedup ≈ 0.6F(n x , n y , m, D).

Number of reductions to zero removed by the extended F 5 criterion

Table 3 shows the number of reductions to zero during the execution of the Buchberger, F 4 and F 5 algorithm. The input systems are random bilinear systems of n x + n y equations over GF(65521)[x 0 , . . . , x n x , y 0 , . . . , y n y ]. Experimentally, there is no reduction to zero when using the extended criterion (Algorithm 4). Notice that the number of reductions to zero which are not detected by the classical F 5 criterion matches the theorical value for a bi-regular system (Definition 8):

n x +n y -1 ∑ i=n y +1 i n y + 1 + n x +n y -1 ∑ i=n x +1 i n x + 1 .
Although the number of reductions to zero removed by the extended criterion is not small compared to the number of useful reductions, they arise in low degree (n x + 1 and n y + 1). Hence, it is not clear what speed-up could be expected with an efficient implementation.

degree of regularity is a crucial indicator of the complexity of Gröbner basis algorithms: for 0-dimensional ideals, it is the lowest integer d reg such that all monomials of degree d reg are in LM(I) (see [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]). As a consequence, the degrees of all polynomials occurring in the F 5 algorithm are lower than d reg + 1. In the following, ≺ still denotes the grevlex ordering.

Lemma 12. If the system F is generic, then there exists polynomials g 0 , . . . , g n x -1 ∈ k[y 0 , . . . , y n y -1 ] such that ∀ j ∈ {0, . . . , n x -1}, x j -g j (y 0 , . . . , y n y -1 ) ∈ ϑ (I).

Proof. We consider the m × n x matrix A = jac x (ϑ (F)) and the vector B = ϑ ( f 1 )(0, . . . , 0, y 0 , . . . , y n y -1 ) . . . ϑ ( f m )(0, . . . , 0, y 0 , . . . , y n y -1 ) .

Thus A •    x 0 . . . x n x -1    + B =    ϑ ( f 1 ) . . . ϑ ( f m )    .
We denote by {A (i) } all the n x × n x sub-matrices of A. Let (α 0 , . . . , α n y -1 ) ∈ Var( MaxMinors(ϑ (jac x (F))) ) be an element of the variety. Let A α (resp. B α ) denote the matrix A (resp. B) where y i has been substituted by α i for all i. Since ϑ (I) is 0-dimensional, the affine linear system

A α •   x 0 . . . x x -1   + B α = 0
has a unique solution. Therefore, the matrix A α is of full rank. Consequently, there exists an invertible n x × n x sub-matrix of A α .

Since k is infinite, we can suppose without loss of generality that, if the system is generic, then for all α in the variety, the matrix A

(1) α obtained by considering the n x first rows of A α is invertible (if A

(1) α is not invertible, just replace the original bilinear system by an equivalent system where each new equation is a generic linear combination of the original equations). Thus det(A (1) α ) = 0. According to Lemma 6 and 17, MaxMinors(ϑ (jac x (F))) = ϑ ( f 1 ), . . . , ϑ ( f m ) ∩k[y 0 , . . . , y n y -1 ]. Thus det(A (1) ) (i.e. the matrix of the n x first rows of A) does not vanish on any element of the variety of ϑ (I). Therefore, the Nullstellensatz says that det(A (1) ) is invertible in k[y 0 , . . . , y n y -1 ]/(ϑ (I)∩ k[y 0 , . . . , y n y -1 ]). Let h denote its inverse. We know from Cramer's rule that there exists polynomials g j ∈ k[y 0 , . . . , y n y -1 ] such that x j det(A (1) ) -g j (y 0 , . . . , y n y -1 ) ∈ ϑ (I).

Multiplying this relation by h, we obtain:

x j -hg j (y 0 , . . . , y n y -1 ) ∈ ϑ (I). Theorem 6. If the system F is generic, then the degree of regularity of ϑ (I) is upper bounded by d reg ≤ min(n x + 1, n y + 1).

Proof. We supposed that n x ≤ n y , so we want to prove that

d reg ≤ n x +1. Let t = ∏ n x -1 j=0 x α j j ∏ n y -1 k=0 y β k k be a monomial of degree n x + 1. According to Lemma 12, t - n x -1 ∏ j=0 g j (y 0 , . . . , y n y -1 ) α j n y -1 ∏ k=0 y β k k ∈ ϑ (I).
Now consider the normal form with respect to the ideal J = MaxMinors(ϑ (jac x (F))) . Then

t -NF J,≺ ( n x -1 ∏ j=0 g j (y 0 , . . . , y n y -1 ) α j n y -1 ∏ k=0 y β k k ) ∈ ϑ (I).
Since all monomials of degree n x + 1 are in LM( MaxMinors(ϑ

(jac x (F))) ) (Lemma 3), deg(NF J,≺ ( n x -1 ∏ j=0 g j (y 0 , . . . , y n y -1 ) α j n y -1 ∏ k=0 y β k k )) < n x + 1. This implies that LM(t -NF J,≺ ( n x -1 ∏ j=0 g j (y 0 , . . . , y n y -1 ) α j n y -1 ∏ k=0 y β k k )) = t.
Therefore, for each monomial t of degree n x + 1, t ∈ LM(ϑ (I)). This means that d reg ≤ n x + 1.

Example 1 (continued). The degree of regularity of the affine system (ϑ ( f 1 ), . . . , ϑ ( f 5 )) is 3 in accordance with Theorem 6 and the classical F 5 criterion removes all reductions to zero during the computation of a Gröbner basis for the grevlex ordering.

The following corollary is a consequence of Theorem 6.

Corollary 3. The arithmetic complexity of computing a Gröbner basis of a generic bilinear system f 1 , . . . , f n x +n y ∈ k[x 0 , . . . , x n x -1 , y 0 , . . . , y n y -1 ] with the F 5 Algorithm is upper bounded by

O n x + n y + min(n x + 1, n y + 1) min(n x + 1, n y + 1) ω ,
where 2 ≤ ω ≤ 3 is the linear algebra constant.

Proof. According to [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF], the complexity of the computation of the Gröbner basis of a 0-dimensional ideal is upper bounded by

O n + d reg d reg ω ,
where n is the number of variables and d reg denotes the degree of regularity. In the case of a generic affine bilinear system in k[x 0 , . . . , x n x -1 , y 0 , . . when n = n x +n y . Notice also that if min(n x , n y ) is constant, then the complexity of computing a Gröbner basis of a 0dimensional generic affine bilinear system is polynomial in the number of unknowns n = n x + n y . Moreover, the inequality d reg ≤ min(n x + 1, n y + 1) is experimentally sharp, it is an equality for random bilinear systems (see Table 4).

Perspectives and conclusion

In this paper, we analyzed the structure of ideals generated by generic bilinear equations. We proposed an explicit description of their syzygy module. With this analysis, we were able to propose an extension of the F 5 criterion dedicated to bilinear systems. Furthermore, an explicit formula for the Hilbert bi-series is deduced from the combinatorics of the syzygy module. With this tool, we made a complexity analysis of a multihomogeneous variant of the F 5 Algorithm.

We also analyzed the complexity of computing Gröbner bases of affine bilinear systems. We showed that generic affine bilinear systems are regular, and we proposed an upper bound for the degree of regularity of those systems.

Interestingly, properties of the ideals generated by the maximal minors of the jacobian matrices are especially important. In particular, a Gröbner basis (for the grevlex ordering) of such an ideal is a linear combination of the generators. In the affine case, this ideal permits to eliminate variables.

The next step of this work would be to generalize the results to more general multihomogeneous systems. For the time being, it is not clear how the results can be extended. In particular, it would be interesting to understand the structure of the syzygy module of general multihomogeneous systems, and to have an explicit formula of their Hilbert series. Also, having sharp upper bounds on the degree of regularity of multihomogeneous systems would be important for practical applications. Remark 6. All results in this section can be generalized to multihomogeneous systems. Since we focus on bilinear systems in this paper, we describe them in this more restrictive context.

Lemma 14. Let P be an admissible prime ideal of R. The set of bilinear polynomials f ∈ R such that f / ∈ P contains a Zariski nonempty open set.

Proof. Let f be the generic bilinear polynomial

f = ∑ j,k
a j,k x j y k in k({a j,k } 0≤ j≤n x ,0≤k≤n y )[x 0 , . . . , x n x , y 0 , . . . , y n y ]. Since P is admissible, there exists x j 0 y k 0 such that x j 0 y k 0 / ∈ P (this shows the non-emptiness). Let ≺ be an admissible order. Then consider the normal form for this order NF P (f) = ∑ t monomial h t (a 0,0 . . . , a n x ,n y )t.

By multiplying by the least common multiple of the denominators, we can assume without loss of generality that for each t, h t is a polynomial. Thus, if a bilinear polynomial is in P, then its coefficients are in the variety of the polynomial system ∀t, h t (a 0,0 , . . . , a n x ,n y ) = 0.

Theorem 7. Let m, n x , n y ∈ N such that m ≤ n x + n y . Then the set of bilinear systems f 1 , . . . , f m such that for all i, f i does not divide 0 in R/J i-1 contains a Zariski nonempty open subset.

Proof. We prove the Theorem by recurrence on m. Suppose that for all i such that 2 ≤ i ≤ m -1, f i is not a divisor of 0 in R/J i-1 . We prove that the set of bilinear polynomials f such that f is not a divisor of 0 in R/J m-1 contains a nonempty Zariski open subset. According to Lemma 14, for each admissible prime ideal P ∈ Ass(I m-1 ), the set O P = { f / ∈ P} contains a nonempty Zariski open subset. Thus P O P contains a nonempty Zariski subset. Therefore, the set of bilinear polynomials f which are not divisor of 0 in R/J m-1 (this set is exactly P O P ) contains a Zariski nonempty open subset.

Proposition 8. Let m ≤ n x + n y and f 1 , . . . , f m be bilinear polynomials such that for all i such that 2 ≤ i ≤ m, f i is not a divisor of 0 in R/J i-1 . Then for all i such that 1 ≤ i ≤ m, the ideal J i is equidimensional and its codimension is i.

Proof. We prove the Proposition by recurrence on m.

• J 1 = I 1 is equidimensional and codim(I 1 ) = 1;

• Suppose that J i-1 is equidimensional of codimension i -1. Then J i = (J i-1 + f i ) : (X ∩ Y ) ∞ . f i does not divide 0 in R/J i-1 (Theorem 7), thus J i-1 + f i is equidimensional of codimension i. The saturation does not decrease the dimension of any primary component of J i-1 + f i . Therefore, J i is equidimensional and its codimension is i.

Suppose now that Ψ(k m ) is dense in k m . By Sard's theorem (Shafarevich, 1977, Chap. 2, Section 6.2, Theorem 2), there exists (ε 1 , . . . , ε m ) ∈ k m which does not lie in the set of critical values of Ψ. This implies that at any point of the algebraic variety defined by g 1 -ε 1 = • • • = g m -ε m = 0, ϑ • ϕ a (det(jac X,Y (F))) does not vanish. Remark now that there exists a ′ such that g i -ε i = ϑ • ϕ a ′ ( f i ). We conclude that a ′ ∈ k m(n x +n y +2) \ J , which ends the proof. Proof. Let a be an element in O 2 (as defined in Lemma 16). Thus ϑ • ϕ a (I) is radical. Now let (v 0 , . . . , v n x -1 , w 0 , . . . , w n y -1 ) ∈ Var(ϑ • ϕ a (I)) be an element of the variety. Then This implies that rank(ϑ • ϕ a (jac y (F)) x i =v i ) < n y + 1, and therefore (v 0 , . . . , v n x -1 ) ∈ Var( MaxMinors(ϑ • ϕ a (jac y (F))) ).

Conversely, let (v 0 , . . . , v n x -1 ) ∈ Var( MaxMinors(ϑ • ϕ a (jac y (F))) ). Thus there exists a non trivial vector (w 0 , . . . , w n y ) in the right kernel Ker(ϑ • ϕ a (jac y (F)) x i =v i ). This means that (v 0 , . . . , v n x -1 , 1, w 0 , . . . , w n y ) is in the variety of ϕ a (I):

(v 0 , . . . , v n x -1 , 1, w 0 , . . . , w n y ) ∈ Var(ϕ a jac y (F) •    y 0 . . .

y n y   )
From Lemma 15, w n y = 0 if the system is generic. Hence (v 0 , . . . , v n x -1 , w 0 w n y , . . . , w n y -1 w n y ) ∈ Var(ϑ • ϕ a (I)).

Furthermore

  , the inequality h 1 (a)h 2 (a)h 3 (a) = 0 defines the wanted Zariski open set. Proof of Lemma 4. Consider the Zariski open set O ′′ = O ′ ∩ O ′′′ (where O ′ is defined in Lemma 3 and O ′′′ is defined in Lemma 6) and let a be taken in O ′′ . According to Lemma 3,

Remark 1 .

 1 In the following, Monomials x n (d) (resp. Monomials y n (d)) denotes the set of monomials of degree d in k[x 0 , . . . , x n ] (resp. k[y 0 , . . . , y n ]). If n < 0, we use the convention Monomials x n (d) = Monomials y n (d) = / 0.

  Adams, W.,Loustaunau, P., 1994. An introduction to Gröbner bases. American Mathematical Society. Ars, G., 2005. Applications des bases de Gröbner à la cryptographie. Ph.D. thesis, Université de Rennes I. Atiyah, M., MacDonald, I., 1969. Introduction to Commutative Algebra. Series in Mathematics. Addison-Wesley.[START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]. Étude des systèmes algébriques surdéterminés. applications aux codes correcteurs et à la cryptographie.Ph.D. thesis, Université Paris 6.

Lemma 17 .

 17 There exists a nonempty Zariski open set O3 , such that if a ∈ O 3 , MaxMinors(ϑ • ϕ a (jac y (F))) = ϑ • ϕ a ( f 1 ), . . . , ϑ • ϕ a ( f m ) ∩ k[x 0 , . . . , x n x -1 ].

ϑ

  • ϕ a (jac y (F)) x i =v i •

Finally.

  MaxMinors(ϑ • ϕ a (jac y (F))) ) = Var( ϑ • ϕ a ( f 1 ), . . . , ϑ • ϕ a ( f m ) ∩ k[x 0 , . . . , x n x -1 ])and ϑ • ϕ a (I) is radical (Lemma 16). The Nullstellensatz concludes the proof.Corollary 4. There exists a nonempty Zariski open set O4 , such that if a ∈ O 4 , card(Var(ϑ • ϕ a (I))) = deg(ϑ • ϕ a (I)) = n x + n y n x Proof. According to Lemma 16 and Lemma 15, if a ∈ O 1 ∩O 2 , then deg(ϑ •ϕ a (I)) = card(Var(ϑ • ϕ a (I)) = card(Var(ϕ a (I))). This value is the so-called multihomogeneous Bézout number of ϕ a (I), i.e. the coefficient of z n x 1 z n y 2 in (z 1 + z 2 ) n x +n y (see e.g.[START_REF] Morgan | A homotopy for solving general polynomial systems that respects m-homogeneous structures[END_REF]), namely n x +n y n x Remark 7. Actually, by studying ideals spanned by maximal minors of matrices whose entries are linear forms, it can be shown that, for a generic affine bilinear system, MaxMinors(ϑ • ϕ a (jac y (F))) is radical (see Lemma 6). Hence Lemma 17 shows that, for generic affine bilinear systems,MaxMinors(ϑ • ϕ a (jac y (F))) = ϑ • ϕ a ( f 1 ), . . . , ϑ • ϕ a ( f m ) ∩ k[x 0 , . . . , x n x -1 ],MaxMinors(ϑ • ϕ a (jac x (F))) = ϑ • ϕ a ( f 1 ), . . . , ϑ • ϕ a ( f m ) ∩ k[y 0 , . . . , y n y -1 ].

Table 1 :

 1 The rows of this matrix represent the polynomials of M d of bidegree (d 1 , d 2 ) and the columns represent the monomials of R d 1 ,d 2 .• Compute the row echelon form of the matrices M d 1 ,d 2 . This gives bases of I d 1 ,d 2 .• The union of the bases gives a basis of I d since I d = d 1 +d 2 =d I d 1 ,d 2 . Execution time and memory usage of the multihomogeneous variant of F 5

						Multihomogeneous	Homogeneous
	n x	n y	m	bidegree	D	time	memory	time	memory	speed-up
	3	4	7	(1, 1)	6	16.9s	30MB	265.7s	280MB	16
	3	4	7	(1, 1)	7	105s	92MB	2018s	1317MB	19
	4	4	8	(1, 1)	7	582s	275MB	13670s	4210MB	23
	5	4	9	(1, 1)	7	3343s	957MB	66371s	12008MB	20
	5	5	10	(1, 1)	6	645s	435MB	10735s	4330MB	17
	2	2	4	(1, 2)	10	11.4s	19MB	397s	299MB	35
	2	2	4	(1, 2)	8	1.7s	10MB	16s	52MB	9
	3	3	6	(1, 2)	8	67s	80MB	1146s	983MB	17
	4	4	8	(1, 2)	8	2222s	1031MB	40830s	12319MB	63
	2	2	4	(2, 2)	11	29s	27MB	899s	553MB	31
	3	3	6	(2, 2)	8	27s	47MB	277s	452MB	10
	3	3	6	(2, 2)	9	152s	154MB	2380s	1939MB	16
	3	4	7	(2, 2)	9	1034s	505MB	18540s	7658MB	18
	4	4	8	(2, 2)	8	690s	385MB	7260s	4811MB	11
	4	4	8	(2, 2)	9	6355s	2216MB	-	>20000MB	-

Table 2 :

 2 Decomposing the matrices: experimental speed-up

	HS(t,t)	2 D + n x + n y + 1 D	.

Table 4 :

 4 . , y n y -1 ], n = n x + n y and d reg ≤ min(n x + 1, n y + 1) (Theorem 6). Experimental results: degree of regularity and reductions to zero for random affine bilinear systems Remark 5. This bound on the degree of regularity should be compared with the degree of regularity of a generic quadratic system with n equations and n variables. The Macaulay bound (see[START_REF] Lazard | Gröbner bases, gaussian elimination and resolution of systems of algebraic equations[END_REF]) says that the degree of regularity of such systems is m + 1. The complexity of computing a Gröbner basis of a generic quadratic system of n equations in k[x 1 , . . . , x n ] is upper bounded by O 2n

		n x n y nb. eq. d reg nb. reductions to 0
		2	3	5	3	0
		2	4	6	3	0
		3 10	13	4	0
		5	8	13	6	0
		6	6	12	7	0
	n+1	ω , which is larger than O	min(n x +1,n y +1) n x +n y +min(n x +1,n y +1)	ω

v = (minor(jac x (F), 1), -minor(jac x (F), 2), minor(jac x (F), 3), -minor(jac x (F), 4)).

Structure of generic affine bilinear systems

In this section, we show that generic affine bilinear systems have a particular structure: they are regular (Definition 7). Consequently, the usual F 5 criterion removes all reductions to zero.

Proposition 5. Let S be the set of affine bilinear systems over k[x 1 , . . . , x n x , y 1 , . . . , y n y ] with m ≤ n x + n y equations. Then the subset

Proof. Let ( f 1 , . . . , f m ) be a generic affine bilinear system. Assume that it is not regular. Then for some i, there exists g ∈ R such that g / ∈ I i-1 and g f i ∈ I i-1 . Denote by g h the bi-homogenization of g. Then

) is a generic bilinear system, hence it is bi-regular (Theorem 4). Thus g h ∈ k[x 0 , . . . , x n x ] or g h ∈ k[y 0 , . . . , y n y ]. Let us suppose that g h ∈ k[x 0 , . . . , x n x ] (the proof is similar if g h ∈ k[y 0 , . . . , y n y ]). Therefore y n y g h ∈ f h 1 , . . . , f h i-1 when the system is bi-regular (Proposition 4). By putting x n x = 1 and y n y = 1, we see that in this case, g ∈ I i-1 , which yields a contradiction. This shows that generic affine bilinear systems are regular.

Degree of regularity of affine bilinear systems

In this part, m, n x and n y are three integers such that m = n x + n y . We consider a system of bilinear polynomials

.

Also, I stands for the ideal f 1 , . . . , f m and ϑ (I) denotes the ideal ϑ ( f 1 ), . . . , ϑ ( f m ) . In the following, we suppose without loss of generality that n x ≤ n y . We also assume in this part of the paper that the characteristic of k is 0 (although the results remain true when the characteristic is large enough).

The goal of this section is to give an upper bound on the so-called degree of regularity of an ideal I generated by a generic affine bilinear system with m equations and m variables. The

Appendix A. Bihomogeneous ideals

In this part, we use notations similar to those used in Section 4:

• BH (n x , n y ) the k-vector space of bilinear polynomials in k[x 0 , . . . , x n x , y 0 , . . . , y n y ];

• X (resp. Y ) is the ideal x 0 , . . . , x n x (resp. y 0 , . . . , y n y );

• An ideal is called bihomogeneous if it admits a set of bihomogeneous generators.

• J i denotes the saturated ideal I i : (X ∩Y ) ∞ ;

• Given a polynomial sequence ( f 1 , . . . , f m ), we denote by Syz triv the module of trivial syzygies, i.e. the set of all syzygies (s 1 , . . . ,

• Let E be a k-vector space such that dim(E) < ∞. We say that a property P is generic if it is satisfied on a nonempty open subset of E (for the Zariski topology), i.e. ∃h ∈ k[a 1 , . . . , a dim(E) ], h = 0, such that P does not hold on (a 1 , . . . , a dim(E) ) ⇒ h(a 1 , . . . , a dim(E) ) = 0.

Proposition 6 [START_REF] El Din | Strong bi-homogeneous Bézout theorem and its use in effective real algebraic geometry[END_REF]). Let I be an ideal of R. The two following assertions are equivalent:

• I is bihomogeneous.

• For all h ∈ I, every bihomogeneous component of h is in I.

Lemma 13 [START_REF] El Din | Strong bi-homogeneous Bézout theorem and its use in effective real algebraic geometry[END_REF]). Let f 1 , . . . , f m ∈ R be polynomials, and I m = ∩P l be a minimal primary decomposition of I m and let Adm be the set of the admissible ideals of the decomposition. Then J m = ∩ P∈Adm P.

Proposition 7. let f 1 , . . . , f m ∈ R be polynomials with m ≤ n x + n y , and Ass(I i-1 ) be the set of prime ideals associated to I i-1 . The following assertions are equivalent:

1. for all i such that 2 ≤ i ≤ m, f i is not a divisor of 0 in R/J i-1 .

2. for all i such that 2 ≤ i ≤ m, ( f i ∈ P, P ∈ Ass(I i-1 )) ⇒ P is non-admissible.

Proof. It is a straightforward consequence of Lemma 13.

Appendix B. Ideals generated by generic affine bilinear systems

Let k be a field of characteristic 0, m = n x + n y , and a be the set

We consider generic polynomials f 1 , . . . , f m in k(a)[x 0 , . . . , x n x , y 0 , . . . , y n y ]:

and we denote by I ⊂ k(a)[x 0 , . . . , x n x , y 0 , . . . , y n y ] the ideal they generate. In the sequel, ϑ denotes the dehomogenization morphism:

.

For a ∈ k m(n x +n y +2) , ϕ a stands for the specialization:

ϕ a : k(a)[x 0 , . . . , x n x , y 0 , . . . , y n y ] → k[x 0 , . . . , x n x , y 0 , . . . , y n y ] f (a)(x 0 , . . . , x n x , y 0 , . . . , y n y ) → f (a)(x 0 , . . . , x n x , y 0 , . . . , y n y ) Also Var(ϕ a (I)) ⊂ P n x × P n y (resp. Var(ϑ • ϕ a (I)) ⊂ kn x +n y ) denotes the variety of ϕ a (I) (resp. ϑ • ϕ a (I)).

Lemma 15. There exists a nonempty Zariski open set O 1 such that if a ∈ O 1 , then for all (α 0 , . . . , α n x , β 0 , . . . , β n y ) ∈ Var(ϕ a (I)), α n x = 0 and β n y = 0. This implies that the application Var(ϑ • ϕ a (I))

-→ Var(ϕ a (I)) (α 0 , . . . , α n x -1 , β 0 , . . . , β n y -1 ) -→ (α 0 , . . . , α n x -1 , 1, β 0 , . . . , β n y -1 , 1) is a bijection.

Proof. See (Van der Waerden, 1929, page 751).

Lemma 16. There exists a nonempty Zariski open set O

and J be its associated algebraic variety. By the Jacobian Criterion (see e.g. (Eisenbud, 1995, Theorem 16.19)), if a does not belong to J , then ϑ • ϕ a (I) is radical. Thus, it is sufficient to prove that k m(n x +n y +2) \ J is non-empty.

To do that, we prove that for all a ∈ k m(n x +n y +2) , there exists (ε 1 , . . . , ε m ) such that the ideal ϑ • ϕ a ( f 1 ) + ε 1 , . . . , ϑ • ϕ a ( f m ) + ε m is radical. Denote by g i = ϑ • ϕ a ( f i ) for 1 ≤ i ≤ m and consider the mapping Ψ

x ∈ k m → (g 1 (x), . . . , g m (x)) ∈ k m .

Suppose first that Ψ(k m ) is not dense in k m . Since Ψ(k m ) is a constructible set, it is contained in a Zariski-closed subset of k m and there exists (ε 1 , . . . , ε m ) such that the algebraic variety defined by g 1 -ε 1 = • • • = g m -ε m = 0 is empty. Since there exists a ′ such that g i -ε i = ϑ • ϕ a ′ ( f i ), we conclude that ϑ • ϕ a ′ (I) = 1 . This implies that a ′ / ∈ J .