Thi Xuan

Trung-Hieu V And

Thibault H Christoph

Théo M Valérie

the P S group in these last few years

Thanks

Thanks

This work would not have been possible without the support of many people. I would like first to thank Mohab S E D , for giving me so much advice which helped me a lot and of course to be in the jury of this habilitation thesis. I also want to thank all my past and current colleagues in the P S group with whom it is a pleasure to collaborate and work: Christian E , Jean-Charles F , Vincent N , Ludovic P and Guénaël R . Many thanks to Bernard M , Cordian R and Gilles V for reviewing this manuscript! I would also like to thank Alin B for accepting to be in this jury and his advice and support together with the other members of this jury: Manuel K and Fatemeh M . I am lucky to be part of a very nice work environment. Thank you to all the other members of

Chapter 1 Introduction

This habilitation thesis deals with the research that I have done since I have been with the P S group in Sorbonne Université.

On the one hand, polynomial systems arise in a wide range of areas of scientific domains such as biology [ ], chemistry [ ], quantum mechanics [ ], robotics [ ], and computing sciences, including coding theory [ ], computer vision [ ] and cryptography [ ] to cite a few. On the other hand, polynomial system solving is NP-hard, even when the ground field is finite [ , Appendix A . ]. Moreover, the non-linearity of such systems make reliability issues topical, in particular when complete and exhaustive outputs are required, in the context of numerical algorithms.

Likewise, sequences are a classical mathematical obje and computing linear recurrence relations of a multi-indexed sequence or determining the nature of this sequence based on these relations is a fundamental problem in coding theory [ , ], computer algebra [ , , ] and enumerative combinatorics [ , , ].

Whether it be for solving polynomial systems or for computing or guessing linear recurrence relations, one aims to obtain nice generators of an ideal that are able to answer the following questions. Is the number of solutions finite in an algebraic closure of the field of coe cients? How many initial terms and linear recurrence relations do one needs to compute any term of the sequence?

These questions are easily answered when we have a Gröbner basis of the ideal at hand. This is why, the main focus of my research is Gröbner bases computations with two main goals: solving polynomial systems exa ly and determining all the linear recurrence relations of a multi-indexed sequence.

.

Gröbner bases: a fundamental obje

Buchberger developed the theory of Gröbner bases and designed a first algorithm to compute them in [ ]. Since then, many e cient Gröbner basis algorithms were developed.

While lexicographic Gröbner bases are the tool of choice to represent the solution set of a polynomial system, often, they are the hardest Gröbner bases to compute. For n generic polynomials of degree d in n variables, computing the ≺ -Gröbner basis of the ideal they spanned is bounded by C 1 d C 2 n 3 , see [ ], whereas computing the ≺ -Gröbner basis of the same ideal is bounded by

C 1 d C 2 n 2 , see [ ].
As a caveat to that, Gröbner bases change of orders algorithms have been introduced. They take as an input a Gröbner basis G 1 for a monomial order ≺ 1 and another monomial order ≺ 2 and they return G 2 , a Gröbner basis of G 1 for ≺ 2 . This yields the following framework, in the zero-dimensional case, where f 1 , . . . , f s are the original polynomials that are given as an input to Buchberger's algorithm [ ] .

Solving polynomial systems

Let be an algebraic closed field and n ∈ ℕ * . We let x = (x 1 , . . . ,x n ). We recall that an ideal I ⊆ [x] is zero-dimensional if the solution set a ∈ n ∀ f ∈ I , f (a) = 0 is finite.

With the convention that x n ≺ • • • ≺ x 1 , a ≺ -Gröbner basis G of I allows one to compute the coordinates of the above solution set. Indeed, for all 1 ≤ k ≤ n, G ∩ [x k , . . . ,x n ] is a ≺ -Gröbner basis of I ∩ [x k , . . . ,x n ]. That is, ≺ -Gröbner bases extend the notion of triangular basis for linear systems.

Assuming G is reduced, it su ces then to compute the roots of the (unique) polynomial in G ∩ [x n ] to obtain the last coordinate of each solution. Then, to replace x n by each of this last coordinate in all the polynomials in G ∩ [x n-1 ,x n ] to find the corresponding second-to-last coordinate of each solution, and so on and so forth.

Furthermore, if I is radical, then after a generic change of coordinates, its reduced ≺ -Gröbner basis is said to be in shape position, i.e.

G = g n (x n ),x n-1 -g n-1 (x n ), . . . ,x 1 -g 1 (x n ) ,
with deg g n = deg I and for all 1 ≤ k ≤ n -1, deg g k < deg g n . In other words, the last coordinate parameterizes the other coordinates of the solutions.

Thanks to this, computing a ≺ -Gröbner basis of a zero-dimensional ideal f 1 , . . . , f s is a fundamental step for solving exa ly a polynomial system f 1 = • • • = f s = 0. Using the framework of Figure . , we are led to first compute a ≺ -Gröbner basis of this ideal.

Under generic assumptions, the complexity of Gröbner bases change of order from ≺ to ≺ is in Õ (D ) [ ] and O (tD 2 ) [ ], where D is the degree of the ideal and t ≤ D is the number of monomials not in x n in the ≺ -monomial basis. This parameter t is well-understood when the ideal is spanned by n generic polynomials of degree d [ , Cor. . ].

In many applications, the polynomial system at hands is stru ured. For instance, in polynomial optimization, critical values of a polynomial map restri ed to an algebraic sets are solutions of determinantal systems deriving from maximal minors. Problem 1 (Complexity of Sparse-FGLM for generic determinantal systems): Is it possible to give asymptotics for t in generic cases for some of these stru ured systems? Furthermore, depending on the asymptotics on t and the theoretical or pra ical values of , it is not clear which complexity is the better one between Õ (D ) [ ] and O (tD 2 ) [ ].

Problem 2 (Complexity of Gröbner bases change of order): Under the same generic assumptions, is there an algorithm whose complexity is better than [ , ] independently on the ratio t /D and on the chosen bound for ?

In real algebraic geometry, computing sample points in singular real algebraic sets [ ] or computing their real dimension [ ] require to compute limits of critical points of the restri ion of a polynomial map to some algebraic set depending on a parameter. This boils down to the computation of saturated ideals. State-of-the-art algorithms for a saturated ideal I :

∞ [ , ] rely on the Gröbner basis computation of an augmented ideal containing I , introducing an extra variable that must be eliminated later. Furthermore, running the F algorithm on this kind of ideal, we can observe that the computations are not regular: there a lot of degree falls. Problem 3 (Computation of Gröbner bases of saturated ideals): Is it possible to compute a Gröbner basis of I :

∞ on the fly from the generators of I without introducing an extra variable?

.

Sequences

Let u ∈ ℕ n be a n-indexed sequence with values in , that is u = (u i 1 ,...,i n ) (i 1 ,...,i n ) ∈ℕ n . There is a natural correspondence between finite linear combinations of terms of u and polynomials in [x 1 , . . . ,x n ] = [x]. For g = s ∈S s x s , with S a finite subset of ℕ n , we write Eval shifting a linear combination of terms by an index i comes down to multiplying the associated polynomial by x i . Observe that Eval is a bilinear operator from [x] × ℕ n to . Definition-Proposition 1. 1 (e.g. [12,Def. 2 and Prop. 4]): Let u ∈ ℕ n be a sequence. A polynomial g ∈ [x] defines a linear recurrence relation with constant coe cients, or C-relation for short, on u if, and only if, for all i ∈ ℕ n , Eval g x i ,u = 0.

The set of all such polynomials is an ideal of [x] called the ideal of C-relations of u and denoted I C (u).

Definition-Proposition 1. 2 (e.g. [11,Def. 2 and Prop. 3]): A sequence u ∈ ℕ n is said to be C-nite if together with a finite number of terms of u and a finite number of C-relations, one can recover all the terms of u. This is equivalent to requiring I C (u) be 0-dimensional.

In some applications, like in combinatorics, error corre ing code, but also in computer algebra through polynomial system solving, one must deal with the ideal of C-relations of a n-indexed sequence. In the last two applications, the ≺ -Gröbner basis of this ideal is the target and its roots the ultimate goal.

It is unclear, at this stage, if given an ideal I ∈ [x], we can build a sequence u ∈ ℕ n such that I C (u) = I . However, we have this following easy result. Definition-Proposition 1.3: If u and v in ℕ n are such that I C (u) ⊆ I and I C (v ) ⊆ I , then for any ∈ , I C (u + v ) ⊆ I , where u + v = (u i + v i ) i ∈ℕ n . Hence, for an ideal I of [x], there exists a whole ve or subspace of ℕ n , denoted S C (I ) such that for u ∈ S C (I ), I C (u) ⊆ I .

Remark 1.4: By convention, the zero sequence is the only sequence whose ideal of C-relations is 1 .

Theorem 1.5: Let u and v in ℕ n . Let , ∈ . Then, I C (u) ∩ I C (v ) ⊆ I C ( u + v ). Proof. Let g = s ∈S s x s ∈ I C (u) ∩ I C (v ). By linearity, for all i ∈ ℕ n , Eval g x i , u + v = Eval g x i ,u + Eval g x i ,v = 0. Hence, g ∈ I C ( u + v ).
In this manuscript, most examples will come from sequences such as the following one. Example 1.6:

Let I = (x 4 2 + x 3 2 )(x 2 1 + x 2 2 -1), (x 1 -x 2 2 -x 2 )(x 2 1 + x 2 2 -1
) . It defines the unit cercle with multiplicity 1, through the fa or x 2 1 + x 2 2 -1 appearing in both spanning polynomials and two points: the origin (0, 0), with multiplicity 3, and (0, -1), with multiplicity 1, as the common vanishing points of x 4 2 + x 3 2 = x 1x 2 2x 2 = 0. Notice that (0, -1) is also on the unit cercle and thus it has multiplicity 2 in total.

Let = x 4 1 -x 4 2 -2x 2 1 + 1 = (x 2 1 + x 2 2 -1)(x 2 1 -x 2 2 -1
) defining the union of the unit circle and the unit hyperbola.

The ideal J = I : ∞ defines the Zariski closure of the set di erence of the variety defined by I and that defined by . The resulting ideal defines the origin, with multiplicity 3, and one can proves that

J = x 3 2 ,x 1 -x 2 2 -x 2 . Now, let v ∈ S C ( J ).
By the first polynomial, we have Eval

x i 1 x j +3 2 ,v = v i ,j +3 = 0 for all (i , j ) ∈ ℕ 2 . Moreover, by the second polynomial, we have v i +1,j = Eval x i +1 1 x j 2 ,v = Eval x i 1 x j +2 2 + x i 1 x j +1 2 ,v = v i ,j +2 + v i ,j +1 for all (i , j ) ∈ ℕ 2 .
Hence, there exist 0,0 , 0,1 and 0,2 such that

v = . . . . . . . . . . . . . . . . . . 3 0 0 0 0 • • • 2 0,2 0 0 0 • • • 1 0,1 0,2 0 0 • • • 0 0,0 0,1 + 0,2 0,2 0 • • • i 2 i 1 0 1 2 3 • • • Chapter 1. Introduction 1.

Contributions

Let us recall that not all ideals can be ideals of C-relations. For instance, any sequence u, built

from K = x 2 1 ,x 1 x 2 ,x 2 2 , satisfies the relation Eval (u 0,1 x 1 -u 1,0 x 2 )x i 1 x j 2 ,u = u 0,1 u i +1,j -u 1,0 u i ,j +1 =
0 for all (i , j ) ∈ ℕ 2 . We refer to Appendix A for more details. Hence K I C (u), and K is not an ideal of C-relations. More generally, [ , Prop. . ] proves that ideals of C-relations are exa ly Gorenstein ideals [ , ] and problems occur only if the ideal has a zero of multiplicity at least 2. The following theorem can also be found in [ , Th. . ]. Theorem 1.7: Let I ⊆ [x] be a 0-dimensional ideal. The ideal I (resp. ring R = [x]/I ) is Gorenstein if, equivalently, ( ) R and its dual are isomorphic as R-modules;

( ) there exists a -linear form on R such that the following bilinear form is non degenerate

R × R → (a,b) ↦ → (a b).
In order to be self-contained, we detail in Appendix A the link between an ideal of C-relations I and the general term of a sequence in S C (I ).

Guessing the ideal of C-relations of a sequence u is the task of computing candidate polynomials in I C (u) using only finitely many terms of u. In particular, we aim at guessing a ≺-Gröbner basis of I C (u) for a given monomial order ≺. In the uni-indexed sequence case, guessing the essentially unique C-relation can be modeled through the solving a Hankel system. Yet, the best algorithm, which runs in time quasi-linear in the number of input sequence terms, uses fast polynomial arithmetic and fast extended Euclidean algorithm [ ].

In the multi-indexed setting, one can still guess the C-relations using linear algebra techniques on a multi-Hankel matrix [ , ] or a Gram-Schmidt process [ ]. The so-called Berlekamp-Massey-Sakata algorithm, due to Sakata [ , , ], guesses the relations using polynomial additions and shifts by a monomial. Problem 4 (Polynomial arithmetic for guessing C-relations): Can we model the guessing of Crelations of multi-indexed sequences with multivariate polynomial arithmetic, including polynomial multiplications and divisions?

In some applications, for instance the polynomial system solving one through the S -FGLM algorithm, the bottleneck of the algorithm is the computation of the sequence terms, and not the guessing of the C-relations. It is thus essential that only terms stri ly needed for the guessing be computed. Problem 5 (Minimization of number of queries): In the case where queries to the sequence are expensive, can we relate the number of queries to the geometry of the staircase of the output Gröbner basis?

In enumerative combinatorics, like D/ D-walks, the sequence comes with a stru ure: the terms are invariant by the a ion of a group on the indices, the nonzero terms lie on a cone. In particular, when many sequence terms are, this make the previously mentioned multi-Hankel matrix have a lot of zero rows. This translates into guessed relations that might be fake as we would not guess them with more terms at hand. Thus, we need to build a much larger matrix, for instance with many more rows than columns, to prevent guessing these fake relations. Problem 6 (Structured guessing): Can we exploit the sparsity of the nonzero terms in order to guess fewer fake relations with fewer queries? What properties do the guess relations have?

.

Contributions

. .

Problem : Complexity of S -FGLM for generic determinantal systems

In polynomial optimization, critical points methods require to compute the vanishing set of the restri ion of a linear map to an algebraic set defined by p generic polynomials by means of the simultaneous vanishing of maximal minors of a truncated Jacobian matrix. More generally, we Chapter 1. Introduction 1.4. Contributions define below the class of generic determinantal sum ideals that contains this kind of ideals and we provide an asymptotic on the parameter t for them. Definition 1.8 (see also [10,Def. 8]): With an infinite field, let I ⊂ [x] be an ideal which is the sum of m polynomials of degree at most d and the maximal minors of a matrix with polynomial entries also of degree at most d . We say that I is a generic determinantal sum ideal if the following three conditions hold:

• the ideal I is zero-dimensional and in shape position;

• the Hilbert series of

[x]/I is H ( ) = det(M ( d -1 )) (d -1) ( m-1 2 ) (1 -d ) m (1 -d -1 ) n-m (1 -) n where M ( ) is the (m -1) × (m -1)-matrix whose (i , j )th entry is k m-i k n-1-j k k ;
• for all e ≥ 1, the Hilbert series of ( [x]/I ) / x e n is equal to the series (1 -)H truncated at the first non-positive coe cient.

Theorem 1.9 (see also [10,Th. 2]): Let I be a generic determinantal sum ideal of [x] as in Definition . . Let G be the reduced ≺ -Gröbner basis of I . Let t be the number of polynomials in G whose leading monomial is divisible by x n .

Then, for d = 2 and n ≥ m,

t = m-1 k =0 n -m -1 + k k m 3m/2 -1 -j . Moreover, for d ≥ 3 and n → ∞, t ≈ 1 (n -m) 6 (d -1) 2 -1 d m (d -1) n-m n -2 m -1 .

. . Problem : Complexity of Gröbner bases change of order

State-of-the-art FGLM algorithms uses multiplication matrices to compute the polynomial in the reduced Gröbner basis for the target monomial order. These are matrices of size the degree of the ideal and with scalar entries. Using a change of paradigm and relying on polynomial matrix arithmetic, we design a new change of order algorithm whose complexity is in Õ (t -1 D) under the same generic assumption as [ ]. As a consequence, it is always asymptotically faster than both [ ] and [ ]. Furthermore, for close to 2, the complexity becomes quasi-linear in the size of the input. Theorem 1.10 (see also [20,Th. 1.1]): Let I be a zero-dimensional ideal [x] of degree D. Let G (resp. G ) be the reduced ≺ -(resp. ≺ -)Gröbner basis of I and S be the ≺ -monomial basis of [x]/I . Assume that x 1 , . . . ,x n-1 are in S , and that for all monomials ∈ S , either x n is in S or it is the ≺ -leading monomial of an element in G . Assume that I is in shape position. Then, one can compute G using Õ t -1 D operations in , where t is the number of elements of G whose ≺ -leading monomial is divisible by x n .

. . Problem : Computation of Gröbner bases of saturated ideals

Given generators f 1 , . . . , f s of an ideal I and a polynomial , we propose an algorithm extending Faugère's F algorithm [ ] that computes a partial ≺ -Gröbner basis of I and uses this partial information to find polynomials in I : not in I using linear algebra. Then, adding these new generators, it resumes the partial ≺ -Gröbner basis computation of I :

. Repeating this process, it finds polynomials in (I :

) : and so on and so forth until it stabilizes and has computed the ≺ -Gröbner basis of I :

∞ . This is the F SAT algorithm, Algorithm . . Furthermore, we modify the S -FGLM algorithm so that it takes as an input the reduced ≺ -Gröbner basis of an ideal I and perform linear algebra operations in the set of multiples of in [x]/I in order to compute the reduced ≺ -Gröbner basis of the zero-dimensional ideal I :

. This allows us to perform in one step a colon ideal computation and a change of order. Moreover, Chapter 1. Introduction 1.4. Contributions this new Algorithm . , S -FGLM-, does not assume that I is zero-dimensional, which finds application in polynomial optimization. Theorem 1.11 (see also [15,Th. 4.12]): Let I be a positive-dimensional ideal of [x], let G be its reduced ≺ -Gröbner basis and S be the associated staircase. Let ∈ [x] \ I such that I : is zero-dimensional of degree D and in shape position.

Let Σ be a finite staircase of size N containing supp NF x i n , G , ≺ for all i ∈ ℕ, where NF f ,G , ≺ is the normal form of f w.r.t. G and ≺.

Let t be the number of monomials in Σ such that x n ∈ ≺ ( G ) and let u be the number of monomials in Σ such that x n ∈ ≺ (I ) \ ≺ ( G ). Then, for a generic choice of ve or r ∈ N , Algorithm . terminates and returns the reduced ≺ -Gröbner basis of I :

. To do so, it requires at most u + n normal form computations w.r.t.

G and ≺ plus O ((t + u + n)N D ) operations in .
As a byprodu , I designed and implemented in an e cient probabilistic test for the computation of the parametrizations of x 1 , . . . ,x n-1 w.r.t. x n in √ I . It relies on the algorithm of [ , ] using x n as the linear form. Since their algorithm assume that the linear form is generic, we cannot assert that x n parameterizes the other variables. If it does not, the computed parametrizations are meaningless. Hence the necessity for an e cient validity check of the output. Furthermore, the algorithm of [ , ] builds a sequence before guessing the parametrizations and this sequence building is the a ual bottleneck. Thus, the main advantage of this validity check is that it avoids building a brand new sequence. The following lemma gives the main idea. Lemma 1.12 (see also [15,Lem. 4.15]):

Let I be a zero-dimensional ideal of [x]. Let ∈ ¯ be generic. Then, for 1 ≤ k ≤ n, I = I : x k + .
It su ces then to compute the parametrizations of such I : x k + using the same sequence u as for I . Indeed, I :

x k + is the ideal of C-relations of v = Eval (x k + )x i ,u i ∈ℕ n .
. .

Problem : Polynomial arithmetic for guessing C-relations

While the Berlekamp-Massey-Sakata algorithm [ , , ] performs multivariate polynomials additions and multiplications by a monomial to compute a Gröbner basis of the ideals of C-relations, it fails to generalize the extended Euclidean algorithm. Using the mirror of the truncated generating series of the input multi-index sequence, we design an algorithm performing polynomial divisions and normal forms to compute potential C-relations. Furthermore, we exhibit a criterion based on leading monomials to ensure which of these potential C-relations are corre or not. Finally, when called on a uni-index sequence, the algorithm comes down to performing a truncated extended Euclidean algorithm. All in all, we have the following result. Theorem 1.13 (see also [19,Th. 1]): Let u be a sequence, ≺ be a weighted degree monomial order and M be a monomial. Let us assume that the reduced ≺-Gröbner basis G of I C (u) and its associated staircase S satisfy max(S ∪ ≺ ( G))

M and for all m M , s = max M { | m M }, we have max(S ) s . Then, the variant of the Berlekamp-Massey-Sakata algorithm using polynomial arithmetic terminates and computes Gin O (# S (# S + # G)# T M ) operations in the base field, where T M is the set of monomials less or equal to M .

. . Problem : Minimization of number of queries

Assuming the first terms of the sequence are generic enough so that no fake C-relations are wrongly guessed, we design an adaptive algorithm that follows the shape of the staircase of the output Gröbner basis. It follows a strategy similar to the FGLM algorithm, which allows us to minimize the number of queries to the sequence. Theorem 1.14 (see also [19,Th. 26]): Let u be a sequence whose ideal of C-relations is zero-dimensional. Let ≺ be a monomial order, G be the reduced ≺-Gröbner basis of I C (u) and S be the associated staircase.

Assuming the A S -FGLM algorithm called on u returns a Gröbner basis G with staircase S and # S = # S , then S = S and G = G. Furthermore, the algorithm does not need more that # 2(S ∪ ≺ ( G)) sequence queries and O ((# S + # G) 2 # 2S ) operations to recover G, where 2S is the Minkowski sum of S with itself.

Chapter 1. Introduction 1.5. Organization . . Problem : Stru ured guessing P-relations, linear recurrence relations with polynomial, in the indices, coe cients can be represented by quasi-commutative polynomials. In this setting, we extend the notion of sparse Gröbner basis of [ , ]. This corresponds to P-relations between terms of the sequence that are all lying in a predefined cone. This finds application for instance in enumerative combinatorics where the indices of the nonzero terms are far from random but are a ually all in a given cone. On the one hand, this allows us to reduce the number of sequence queries to guess the relations and on the other hand, this allows us to guess more relations that are corre and fewer that are fake. For instance, for a subsequence of the Gessel walk, using 3 491 sequence terms in the full orthant, we can guess 142 relations amongst which 136 are fake and only 6 are corre . Whereas, taking only sequence terms in a cone allows us to consider sequence terms much further, which in turn allow us to guess more relations. Indeed, with 3 010 terms in a cone of the same sequence, we guess 21 relations and all of them are corre . We refer to Table . for more details. Let us also notice that these fake relations may hide corre ones as their leading monomials could divide the leading monomials of corre relations.

. . Then, Chapter is dedicated to the design of new algorithms for computing Gröbner bases in order to solve polynomial systems and their complexity analyses. Some of these algorithms are already available in . This is based on joint collaborations with Alin Bostan , Christian Eder , Andrew Ferguson , Vincent Neiger and Mohab Safey El Din . In Chapter , I give an overview on di erent algorithms for guessing Gröbner bases of ideal of C-relations of sequences and their e ciency. This is based on joint work with Brice Boyer , Jean-Charles Faugère , and Mohab Safey El Din .

In Chapter , I present extensions of works for guessing ideals of relations, but in the case of relations with polynomial coe cients. This is again related to polynomial ideals but in a ring where variables quasi-commute. This is based on joint work with Jean-Charles Faugère , and Mohab Safey El Din .

Finally, in Chapter , I propose my research proje for the forthcoming years based on increasing the fun ionalities of by implementing existing state-of-the-art algorithms and also on designing algorithms for computing Gröbner bases in the commutative and quasi-commutative towards polynomial system solving and applications to sequences. .

State-of-the-art algorithms

For positive-dimensional ideals, computes their ≺ -Gröbner basis using the F algorithm [ ]. For 0-dimensional ideals, it returns a parametrization of their solutions. In generic coordinates, and for a radical ideal, this parametrization is close to the ≺ -Gröbner basis of the ideal. To compute it, it follows the framework of Figure . . The change of order from ≺ to ≺ is performed thanks to the S -FGLM algorithm [ , ]. If the ideal is not radical, but its radical is in shape position, then it computes the parametrizations thanks to [ , ]. In this latter case, we cannot ensure that the ideal is in generic coordinates, hence we designed and implemented into an e cient probabilistic test to ensure that the computed parametrizations are parametrizations of the radical ideal. The presentation of this test is postponed to Se ion . , as it relies on algorithms presented in Chapter .

Since is also now our tool of choice to implement and validate the new algorithms that we design, some algorithms presented in the following chapters, for instance, F SAT, see Se ion . . , and S -FGLM-, see Se ion . . , have been implemented and are also available in .

. .

The F algorithm

In [ ], Buchberger's algorithm introduced the concept of critical pairs for computing Gröbner bases. For two polynomials f 1 and f 2 in a set of generators of an ideal, the critical pair ( f 1 , f 2 ) leads to a normal form computation of the S-polynomial Observe that the termination of the F algorithm only relies on Buchberger's first criterion: G = g 1 , . . . , g t is a ≺-Gröbner basis of an ideal I if for all 1 ≤ i , j ≤ t , NF sp ≺ g i , g j , G, ≺ = 0, see [ , Chap. , Sec. , Th. ].

sp ≺ f 1 , f 2 = ( ≺ ( f 1 ), ≺ ( f 2 )) ≺ ( f 1 ) f 1 - ( ≺ ( f 1 ), ≺ ( f 2 )) ≺ ( f 2 ) f 2 w.
We detail the di erences to Buchberger's algorithm. ( ) One can choose several critical pairs at a time, stored in a subset L ⊆ P . The so-called degree strategy chooses L to be the set of all critical pairs of minimal degree for a total degree monomial order, typically ≺ .

( ) For all terms of all the generators of the S-polynomials, one searches in the current intermediate Gröbner basis G for possible reducers. One adds those to L and again search for all of their terms for reducers in G. This is the SymbolicPreprocessing fun ion.

( ) Once all redu ion data is colle ed from the last step, one generates a Macaulay-like matrix Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau Sorbonne Université

Chapter 2. msolve

State-of-the-art algorithms

Input: A list of polynomials f 1 , . . . , f s spanning an ideal I ⊆ [x] and a total degree monomial order ≺. Output:

A ≺-Gröbner basis G of I . G f 1 , . . . , f s . P ( f i , f j ) 1 ≤ i < j ≤ s . While P ≠ ∅ do
Choose a subset L of P .

P P \ L. L SymbolicPreprocessing(L, G). L LinearAlgebra(L). For h ∈ L with ≺ (h) ∉ ≺ ( G) do P P ∪ (g ,h) g ∈ G . G G∪ {h}.
Return G.

Algorithm . : Faugère's F with columns corresponding to the monomials appearing in L (sorted by ≺) and rows corresponding to the coe cients of each polynomial in L. Gaussian Elimination is then applied to reduce now all chosen S-polynomials at once. This is the LinearAlgebra fun ion.

( ) Finally, one adds those polynomials associated to rows in the updated matrix to G whose leading monomials are not already in ≺ ( G). In order to optimize the algorithm one can now apply Buchberger's produ and chain criteria, see [ , ]. Thus many useless critical pairs are removed before even being added to P and fewer zero rows are computed during the linear algebra part of F . Still, in general, there are many zero redu ions left.

Di erent sele ion strategies yield di erent behavior of the algorithm. The degree strategy allows one to compute truncated Gröbner bases of ideals in case of early terminations. Definition 2.1: Let f 1 , . . . , f s be polynomials in [x] and ≺ be a monomial order. Let be a monomial and F be the -ve or subspace of f 1 , . . . , f s defined as

F = s i =1 h i f i ∀ 1 ≤ i ≤ s , ≺ (h i f i ) .
Then, G ⊂ F is a -truncated ≺-Gröbner basis of f 1 , . . . , f s if for all p ∈ F , there exists g ∈ G such that ≺ (g ) | ≺ (p) and p -≺ (p ) ≺ (g ) g is in F . Observe that taking a triangular basis of F ordered increasingly w.r.t. ≺ naturally yields a -truncated ≺-Gröbner basis thereof. Proposition 2.2: Let f 1 , . . . , f s be polynomials in [x] and ≺ be a monomial order. Let be a monomial and F be the -ve or subspace of f 1 , . . . ,

f s F = s i =1 h i f i ∀ 1 ≤ i ≤ s , ≺ (h i f i ) . A subset G = g 1 , . . . , g t ⊂ F is a -truncated ≺-Gröbner basis of f 1 , . . . , f s if,

and only if,

F ⊆ G =        t j =1 h j g j ∀ 1 ≤ j ≤ t , ≺ (h j g j )        . and for all (g i , g j ) ∈ G 2 with i ≠ j , if ( ≺ (g i ), ≺ (g j ))
, then NF sp ≺ g i , g j , G, ≺ = 0.

Remark 2.3: ( ) If ≺ is a total degree monomial order, then for d ∈ ℕ, we can also define a d -truncated ≺-Gröbner basis as a -truncated ≺-Gröbner basis for the largest monomial of Chapter 2. msolve 2.1. State-of-the-art algorithms

degree d . ( ) If G = g 1 , . . . , g t is a -truncated ≺-Gröbner basis of f 1 , . . . , f s and max 1≤i < j ≤t ( ≺ (g i ), ≺ (g j )),
then G is a ≺-Gröbner basis of f 1 , . . . , f s . Indeed, it spans the ideal and by Proposition . , all the S-polynomials reduce to 0 w.r.t. G and ≺. Hence, by Buchberger's first criterion [ , Chap. , Sec. , Th. ], it is a ≺-Gröbner basis of f 1 , . . . , f s .

( ) Definition . depends greatly on the set of generators of the ideal. Consider

f 1 = x n , f 2 = (y -1) n and f 3 = xy -y -1 for n ∈ ℕ \ {0, 1}. By Proposition . , G = f 1 , f 2 , f 3 is a n-truncated ≺ -Gröbner basis of f 1 , f 2 , f 3 . Yet, this ideal is 1 hence {1} is a m-truncated ≺ -Gröbner basis of 1 for all m ∈ ℕ. Lemma 2.4: Let f 1 , . . . , f s ∈ [x]
be the input polynomials of the F algorithm. Let d ∈ ℕ. Assume that the F algorithm uses the degree sele ion strategy and that, on line , L consists in all the critical pairs of degree d .

If no new polynomial is added to G on line , then G is a d -truncated ≺ -Gröbner basis of f 1 , . . . , f s .

. . The S -FGLM algorithm

In this subse ion, the input Gröbner basis, G , is the reduced ≺ -Gröbner basis of a zerodimensional ideal I of degree D. The output is the reduced ≺ -Gröbner basis, G , of I . In [ ] and [ , Algo. ], using [ ], the authors observe that the map

[x]/I → [x]/I f ↦ → NF x n f , G , ≺
given in the basis S , the staircase associated to G , is represented by a matrix, M x n , with a special stru ure given in the following two lemmas. Lemma 2.5: Let I be a zero-dimensional ideal of [x] of degree D, G be its reduced ≺ -Gröbner basis and S = { 0 , . . . , D -1 } be its associated staircase. Let M x n be the matrix of the linear map

f ∈ [x]/I ↦ → NF x n f , G , ≺ ∈ [x]/I .
Then, one can build the matrix M x n = (m i ,j ) 0≤i ,j <D with the following procedure: • if x n j = k , then m k ,j = 1 and for all 0 ≤ i < D, i ≠ k , m i ,j = 0;

• otherwise for all 0 ≤ i < D, m i ,j is the coe cient of i in NF x n j , G , ≺ .

Lemma 2.6 ([52, 53, 80]): Let f 1 , . . . , f n be generic polynomials of [x] of degrees at most d .

Let G be the reduced ≺ -Gröbner basis of f 1 , . . . , f n . Then, the latter case of Lemma . only happens if there exists g ∈ G such that ≺ (g ) = x n j . As a consequence, one has

NF x n j , G , ≺ = x n j -g .
Following, we can use Wiedemann algorithm [ ] on M x n to recover its minimal polynomial. Furthermore, whenever the reduced ≺ -Gröbner basis G is in shape position, i.e. there exist

g n , g n-1 , . . . , g 1 ∈ [x n ] such that G = g n (x n ),x n-1 -g n-1 (x n ), . . . ,x 1 -g 1 (x n ) ,
and for all 1 ≤ k ≤ n -1, deg g k < deg g n , then g 1 , . . . , g n-1 can be computed by solving Hankel systems of size D. This can be done using the following two algorithms, Algorithms . and . . Proposition 2.7: Let M ∈ D ×D be a matrix with s nonzero coe cients, r ∈ D be a row-ve or and c 0 , c 1 , . . . , c n-1 ∈ D be n column-ve ors. Then, Algorithm . is corre and computes the sequences (r

M i c 0 ) 0≤i <2D and (r M i c k ) 0≤i <D for 1 ≤ k ≤ n -1 in O (s D + nD 2 ) operations in .
Furthermore, if the ve ors c 0 , c 1 , . . . , c n-1 are ve ors of the canonical basis, then this complexity drops to O ((s + n)D).

Proposition 2.8: Let (v (0) i ) 0≤i <2D -1 , (v (1) i ) 0≤i <D , . . . , (v (n-1) i )
0≤i <D be the first terms of n sequences. Assume that v (0) is linear recurrent of order D. Then, Algorithm . is corre and computes, for

Chapter 2. msolve 2.1. State-of-the-art algorithms

Input: A matrix M ∈ D ×D , a row-ve or r ∈ D and n column-ve ors c 0 , c 1 , . . . , c n-1 ∈ D Output: (r M c 0 ) 0≤i <2D , (r M c 1 ) 0≤i <D , . . . , (r M c n-1 ) 0≤i <D , with 1 = (1, 0, . . . , 0) T . v (0) 0 r c 0 ,v (1) 0 r c 1 , . . . ,v (n-1) 0 r c n-1 . For i from 1 to D -1 do r r M . v (0) i r c 0 ,v (1) i r c 1 , . . . ,v (n-1) i r c n-1 . For i from D to 2D -1 do r r M . v (0) i r c 0 Return (v (0) i ) 0≤i <2D , (v (1) i ) 0≤i <D , . . . , (v (n-1) i ) 0≤i <D Algorithm . : Sequences for S -FGLM Input: Sequences (v (0) i ) 0≤i <2D -1 and (v (k ) i ) 0≤i <D for 1 ≤ k ≤ n -1 with coe cients in . Output: 0,k , . . . , D -1,k for 1 ≤ k ≤ n -1 such that for all 0 ≤ i < D, v (k ) i = D -1,k v (0) D -1+i + • • • + 0,k v (0) i . For k from 1 to n -1 do Solve the Hankel linear system v (0) 0 v (1) 1 • • • v (0) D -1 v (0) 1 v (1) 2 • • • v (0) D . . . . . . . . . v (0) D -1 v (1) D • • • v (0) 2D -2 0,k 1,k . . . D -1,k = v (k ) 0 v (k ) 1 . . . v (k ) D -1 . Return i ,k for 0 ≤ i < D and 1 ≤ k ≤ n -1.
Algorithm . : Hankel system solving for S -FGLM

Chapter 2. msolve 2.1. State-of-the-art algorithms

all 1 ≤ k ≤ n -1, 0,k , . . . , D -1,k such that ∀ 0 ≤ i < D, v (k ) i = D -1,k v (0) D -1+i + • • • + 0,k v (0) i in O (M(D)(n + log D))
operations, where M(D) denote a cost fun ion for multiplying univariate polynomials of degree D with coe cients in .

We are now in a position to present the S -FGLM algorithm in the shape position case.

Input: The reduced ≺ -Gröbner basis G of a zero-dimensional ideal I and its associated staircase S of size D. Output: The reduced ≺ -Gröbner basis of I , if it is in shape position. Build the matrix M as in Lemma . . Pick r ∈ D a row-ve or at random.

1 (1, 0, . . . , 0) T . // the column-ve or of coe cients of NF (1, G , ≺ ) For k from 1 to n -1 do Build c k the column-ve or of coe cients of NF (x k , G , ≺ ). Compute (v (0) i ) 0≤i <2D , (v (1) i ) 0≤i <D , . . . , (v (n-1) i ) 0≤i <D ) with Algorithm . called on M ,r , 1, c 1 , . . . , c n-1 . g n Berlekamp-Massey(v (0) 0 , . . . ,v (0)
2D -1 ). If deg g n < D then Return "Not in shape position or bad ve or".

Compute g 1 D -1,1 x D -1 n + • • • + 0,1 , . . . , g n-1 D -1,n-1 x D -1 n + • • • + 0,n-1 with Algorithm . called on (v (0) i ) 0≤i <2D -1 , (v (1) i ) 0≤i <D , . . . , (v (n-1) i ) 0≤i <D ). Return {g n (x n ),x n-1 -g n-1 (x n ), . . . ,x 1 -g 1 (x n )}.

Algorithm . : S -FGLM

Theorem 2.9: Let I be a zero-dimensional ideal of [x] of degree D, G be its reduced ≺ -Gröbner basis and S be its associated staircase. Let M x n be the matrix of the map

f ∈ [x]/I ↦ → NF x n f , G , ≺ ∈ [x]
/I in the monomial basis S . Let us assume that there are t monomials in S such that x n ∈ ≺ (I ) and that x 1 , . . . ,x n-1 ∈ S , that M x n is known and that the reduced ≺ -Gröbner basis G of I is in shape position. Then, Algorithm . computes G in O (tD 2 + nM(D)) operations, where M(D) denote a cost fun ion for multiplying univariate polynomials of degree D with coe cients in .

Note that the Berlekamp-Massey algorithm and its faster variants return a fa or of g n , so if the computed polynomial has degree D, i.e. it is the chara eristic polynomial of M x n , then it is also its minimal polynomial. Furthermore, based on a deterministic variant of Wiedemann's algorithm, one can also provide a deterministic variant of this algorithm to recover g n [ , Algo. ]. Remark 2.10: In [ , ], the authors consider the case where an ideal J is not in shape position but its radical J is. Let us recall that [ , Chap. , Sec. , Def. ]. In that case, the ≺ -Gröbner basis of J can be computed in a similar fashion, it su ces to replace the call to Algorithm . on line by a call to [ , Algo. ].

J = f ∈ [x] ∃k ∈ ℕ, f k ∈ J , see
Example 2.11: Let H = x 2 2 -x 1 + x 2 ,x 1 x 2 -x 1 + x 2 ,x 2 1 -x 1 +
x 2 be the ≺ -Gröbner basis of the ideal J . Its associated staircase is T = {1,x 2 ,x 1 } and the matrix of the multiplication by x 2 is

1 x 2 x 1 0 0 0 1 1 -1 -1 x 2 0 1 1 x 1
We build a sequence u with random initial coe cients, e.g. u 0,0 = 17, u 1,0 = 5 and u 0,1 = -3, thanks

Chapter 2. msolve

Experimental results

to G :

u = . . . . . . . . . . . . . . . . . . 3 0 0 0 0 • • • 2 -8 0 0 0 • • • 1 5 -8 0 0 • • • 0 17 -3 -8 0 • • • i 2 i 1 0 1 2 3 • • •
The subsequence (u 0,i 2 ) i 2 ∈ℕ satisfies the relation u 0,i 2 +3 = 0 = Eval x i 2 +3 2 ,u for all i 2 ∈ ℕ and no relation of smaller order. Hence x 3 2 ∈ J . We now solve the Hankel system

u 0,0 u 0,1 u 0,2 u 0,1 u 0,2 u 0,3 u 0,2 u 0,3 u 0,4 0 1 2 = u 1,0 u 1,1 u 1,2 17 5 -8 5 -8 0 -8 0 0 0 1 2 = -3 -8 0 to find 0 = 0 and 1 = 2 = -1. Hence, x 1 -x 2 2 -x 2 is in J .
Observe that we already knew this though. Finally,

H = x 3 2 ,x 1 -x 2 2 -y .
.

Experimental results

In order to solve over rational numbers, a multi-modular approach with e cient algorithms is implemented. The F part of the computation is performed with a tracer modulo a first prime p 1 . This first computation allows us to learn all the polynomials and their multiples that are needed at each round and also those that are reduced to 0 or that are only used to reduce other polynomials to 0. Modulo subsequent primes, we apply the tracer so that the matrices we handle are optimal: we do not compute any redu ion to 0. Furthermore, we know that this multi-modular approach corre ly computes the sought ≺ -Gröbner basis over ℚ as long as its proje ion modulo p 1 was corre ly computed.

We compare with two other computer algebra systems: • magma -. -[ ]: using the command Variety().

• maple -[ ]: using the command PolynomialSystem() from the module SolveTools with option engine=groebner. All compared implementations use Faugère's F algorithm and variants of the FGLM algorithm and then solve univariate polynomials.

All chosen systems are zero-dimensional with rational coe cients. All computations are done sequentially. First, Table . compares memory usage of against maple and magma. It illustrates the low memory usage of . However, we emphasize that is a specialized library while maple and magma are general purpose computer algebra systems.

Overall, performs very e ciently on a wide range of input systems, using way less memory than its competitors, allowing its users to solve polynomial systems which are not tra able by maple and magma.

Table . states various, partly well-known benchmarks, which di er in their specific hardness, like redu ion process, pair handling, sparsity of multiplication matrices, etc. It also deals with critical points computations, CP(d,nv,np) describes critical points for a system of np polynomials in nv variables of degree d.

For each system we give its degree and if it is radical (all but one are radical). For we give specific timing information, also on the single modular computations: We apply with the tracer option, giving also the timings for the first modular computation learning and generating the tracer (F4 (learn)) and the timings for the further modular computations applying only the We also use with independent modular computations, applying the probabilistic linear algebra in each modular F (F4 (prob.)) In any case, we apply the same FGLM implementation. Furthermore, we state the number of primes needed by to solve over ℚ. For maple and magma we just give the overall timings. Symbol '-' means that the computation was stopped after waiting more than 10 times the runtime of . For all systems, the bottleneck has been the computation of either a ≺ -Gröbner basis in shape position or a rational parametrization of the solution set.

First thing to note is that magma is in all instances slower than or maple. Although, for some examples, magma's modular F computation is even a bit faster than the other two, magma's bottleneck is both a not optimized FGLM combined with the fa that magma seems to lift a ≺ -Gröbner basis instead of a rational parametrization (the latter one having in general coe cients of significantly smaller bit size).

For nearly all systems, is faster, sometimes by an order of magnitude, than maple. We report on modular timings of maple for F (which is based on a probabilistic linear algebra) and FGLM. It appears that 's modular implementations of both F and FGLM are faster than the ones in maple (with a speed-up sometimes close to 2, sometimes less). It seems that in the multi-modular process, maple uses its probabilistic variant of F while takes advantage of its tracer. Also, maple's documentation indicates that on some examples, an algorithm computing a so-called rational univariate representation (preserving multiplicities), instead of FGLM, may be used. It is likely that on most examples we tried, FGLM is not used. Note also that maple lifts a whole ≺ -Gröbner basis over ℚ while avoids this step. Furthermore, our tracer shares some similarities with [ ].

There are, of course, few examples, where is not competitive. In particular, for some systems, may need to introduce a generic linear form as previously explained while a rational parametrization can be obtained without it (but up to computing normal forms). Also some systems admit a triangular representation, and/or can be split. It seems that maple can dete and sometimes take advantage of such situations. This is typically the case for the Noon-n examples.

Chapter 3. Computing Gröbner bases

Chapter 3 Computing Gröbner bases

In this chapter, I present some works that I have done on algorithms for computing Gröbner bases.

First, Se ion . is dedicated to change of order algorithms, whether my coauthors and I studied its complexity in some special cases or we designed new algorithms. In Se ion . , we shall look at the problems of saturating or quotienting ideals. From a geometric point of view, saturating comes down to removing a subvariety and then taking the Zariski closure of the remaining set. Then, in Se ion . , I present an e cient verification of the computation of the parametrization of the radical of an ideal when we cannot ensure that this radical is in shape position.

This chapter is based on joint work with Alin Bostan , Christian Eder , Andrew Ferguson , Vincent Neiger and Mohab Safey El Din , [ , , , ].

.

Gröbner bases change of order algorithms

Change of order algorithms can be divided into two categories, depending on the dimension of the ideal I . In positive dimension, we can mention the Gröbner walk [ ] whose goal is to update step by step the Gröbner basis when "walking" along a path from ≺ 1 to ≺ 2 in the Gröbner fan of the ideal. In dimension zero, most algorithms rely on linear algebra in the finite-dimensional quotient algebra, following the idea of [ ] yielding the so-called FGLM algorithm.

This original algorithm had a complexity O (nD 3 ), where D is the degree of the ideal, i.e. the dimension of the algebra over the base field. Let us recall that if the ideal is spanned by n generic polynomials of degree d , then D = d n . Under the assumption that the change of order is from ≺ to ≺ in shape position and some other genericity assumptions, the complexity of the change of order has been improved in [ ] to Õ (D ), where is the matrix multiplication exponent. More recently, Neiger and Schost [ ] proposed a general change of order algorithm with complexity Õ (D ) that only requires a stability assumption on the ≺ 1 -Gröbner basis and no assumption on the ≺ 2 -Gröbner basis. This stability assumption is for all monomial ,

∀1 ≤ i < j ≤ n, x j ∈ ≺ 1 (I ) =⇒ x i ∈ ≺ 1 (I ).
. .

Complexity of S -FGLM

Together, Propositions . and . and Theorem . yield the complexity of the S -FGLM algorithm in the shape position situation. While it is not easy to estimate exa ly the number s of nonzero coe cients of the matrix M x n , we can give an upper bound of it. Indeed, from the procedure of Lemma . , s ∈ O (tD), where t is the number of normal forms to perform. Using now Lemma . , we obtain that for an ideal spanned by n generic polynomials of given degrees, t is exa ly the number of polynomials in G whose leading monomials are divisible by x n . Therefore, one obtains a bound of the complexity of the S -FGLM algorithm based on the input Gröbner basis.

This opens a new branch of research to estimate t in order to have a finer complexity estimate of the S -FGLM algorithm in di erent situations. In their paper [ , Cor. . ], the authors bound t for generic systems of n polynomials of degree d in [x] and find that as d tends to +∞, t grows as 6 n d 2n-1 . This is to compare with D that grows as d n . More recently, new estimates for t have been given, especially for polynomial systems that have some of their generators as minors of a multivariate polynomial matrix.

Gröbner bases change of order algorithms

In a joint work with Alin Bostan , Andrew Ferguson and Mohab Safey El Din , we study a case of polynomial ideals that encompass systems defining the critical points of the restri ion of a linear map to an algebraic set defined by p generic polynomials by means of the simultaneous vanishing of maximal minors of a truncated Jacobian matrix. For instance, we consider f 1 , . . . , f m ∈ [x], the Jacobian matrix

J = 1 0 • • • 0 f 1 x 1 f 1 x 2 • • • f 1 x n . . . . . . . . . f m x 1 f m x 2 • • • f m x n
of 1 , the proje ion on the x 1 -axis, f 1 , . . . , f m and the ideal I = f 1 , . . . , f m + MaxMinors J . Definition 1.8 (see also [10,Def. 8]): With an infinite field, let I ⊂ [x] be an ideal which is the sum of m polynomials of degree at most d and the maximal minors of a matrix with polynomial entries also of degree at most d . We say that I is a generic determinantal sum ideal if the following three conditions hold:

• the ideal I is zero-dimensional and in shape position;

• the Hilbert series of

[x]/I is H ( ) = det(M ( d -1 )) (d -1) ( m-1 2 ) (1 -d ) m (1 -d -1 ) n-m (1 -) n where M ( ) is the (m -1) × (m -1)-matrix whose (i , j )th entry is k m-i k n-1-j k k ;
• for all e ≥ 1, the Hilbert series of ( [x]/I ) / x e n is equal to the series (1 -)H truncated at the first non-positive coe cient.

Under some regularity assumptions, the ideal defining the set of critical values of a generic polynomial map restri ed to a smooth algebraic set falls in this class, see [ ]. Thus, determining an asymptotic for t for such systems allows us to estimate the complexity of the S -FGLM algorithm in this situation and in particular for computing the critical values of the restri ion of a generic polynomial map.

Relying on manipulations of the Hilbert series given in Definition . , we simplified this expression in order to show that this Hilbert series is unimodal, which allowed us to prove the following theorem. Theorem 3.1 (see also [10,Th. 1]): Let I be a generic determinantal sum ideal of [x] as in Definition . . Let G be the reduced ≺ -Gröbner basis of I . Then, the latter case of Lemma . only happens if there exists g ∈ G such that ≺ (g ) = x n j . As a consequence, one has NF x n j , G , ≺ = x n jg .

As a consequence, the matrix of the multiplication by x n is obtained for free from the ≺ -Gröbner basis, as in Lemma . for generic systems. Taking this stru ure into account, we then prove that this number t is equal to the largest coe cient of the Hilbert series. Finally, using combinatorial techniques, we obtain formulae for t for such generic determinantal sum ideals. Theorem 1.9 (see also [10, Th. 2]): Let I be a generic determinantal sum ideal of [x] as in Definition . . Let G be the reduced ≺ -Gröbner basis of I . Let t be the number of polynomials in G whose leading monomial is divisible by x n .

Then, for d = 2 and n ≥ m,

t = m-1 k =0 n -m -1 + k k m 3m/2 -1 -j .
Chapter 3. Computing Gröbner bases

Gröbner bases change of order algorithms

Moreover, for d ≥ 3 and n → ∞,

t ≈ 1 (n -m) 6 (d -1) 2 -1 d m (d -1) n-m n -2 m -1 .
In Table . , we show the pra ical accuracy of the formulae in Theorem . , for the parameter t . For d = 2 we use our exa formula, while for d ≥ 3 we use the asymptotic formula. The column A ual is the true density of the matrix of the multiplication by x n for ≺ . The column Theoretical is an approximation given by the ratio t /D and the column Asymptotic is another one given by the asymptotic of t divided by D. The column A ual was already present in [ , Tab. ] Let us also mention that during his Ph.D., Andrew Ferguson , with Le, extended this analysis of the asymptotic of t for ideals spanned by (r + 1)-minors of a polynomial symmetric matrix ( f i ,j ) 1≤i ,j ≤m , where the f i ,j 's are in n = m-r +1 2 variables and of degree d , see [ ]. As above, their asymptotics are derived from the unimodality of the Hilbert series. As the Hilbert series is only known in the cases r = m -2, r = m -1 and r = 1, their asymptotics hold in these cases. For the other cases, they hold if the Hilbert series is rightfully conje ured to be unimodal.

. . A polynomial-matrix algorithm

Under the stability assumption, two algorithms, more e cient than the original FGLM algorithm, are at our disposal. The Faugère and Mou's S -FGLM algorithm [ , ], which requires that the reduced ≺ -Gröbner basis is in shape position and whose complexity is in O (tD) and Neiger and Schost's algorithm [ ] whose complexity is in Õ (D ).

Despite the pra ical e ciency of the S -FGLM algorithm and the asymptotics on t [ , ], the recent improvements on , the best known bounds are ≤ 2.37 285 96 [ ] or even ≤ 2.37 188 [ ], make Neiger and Schost's algorithm the fastest.

In this subse ion, I present a change of order algorithm designed by Vincent Neiger , Mohab Safey El Din and myself from ≺ to ≺ with complexity Õ (t -1 D), assuming that the ≺ -Gröbner basis satisfies the stability assumption and that the ≺ -Gröbner basis is in shape position. Since t ≤ D, this complexity makes it asymptotically faster than the two aforementioned algorithms, independently on the value of and the ratio t /D.

To do so, we push forward the study of the properties of the multiplication matrix M x n by x n . Let S be the monomial basis of [x]/I obtained from the reduced ≺ -Gröbner basis G of I . Under the stability assumption, its columns are either unit ve ors (for those ∈ S such that x n ∈ S ) or ve ors of coe cients of polynomials in G (for those ∈ S such that x n is a leading monomial of one element in G ). The latter ones are usually referred to as a "dense" former Ph.D. student at Sorbonne Université Sorbonne Université Chapter 3. Computing Gröbner bases 3.2. Saturated and colon ideals columns, [ , Sec. ] and [ , Sec. ]. This is a well-known matrix stru ure in -linear algebra, called a shifted form in [ , ], and studied in particular in the context of the computation of the chara eristic polynomial or the Frobenius normal form of a matrix over , see [ , Sec. . ].

Exploiting the algebraic stru ure itself, we relate it to operations in a [x n ]-submodule of I . Following a classical constru ion in [ , Sec. . ], instead of the multiplication matrix M x n which is in D ×D , we consider a univariate polynomial matrix P x n in [x n ] t ×t whose average column degree is D/t . This polynomial matrix can be seen as a "compression" of M x n , or more precisely of the chara eristic matrix x n Id D -M x n , with smaller matrix dimension but larger degrees.

Under a less restri ive assumption than the stability one, and which is also included in the assumptions of the S -FGLM algorithm of [ , ] and of [ ], we can build P x n for free from G . Then, we retrieve G using [x n ]-linear algebra operations on P x n . Theorem 1.10 (see also [20,Th. 1.1]): Let I be a zero-dimensional ideal [x] of degree D. Let G (resp. G ) be the reduced ≺ -(resp. ≺ -)Gröbner basis of I and S be the ≺ -monomial basis of [x]/I . Assume that x 1 , . . . ,x n-1 are in S , and that for all monomials ∈ S , either x n is in S or it is the ≺ -leading monomial of an element in G . Assume that I is in shape position. Then, one can compute G using Õ t -1 D operations in , where t is the number of elements of G whose ≺ -leading monomial is divisible by

x n . Example 3.2: Let H = x 2 2 -x 1 + x 2 ,x 1 x 2 -x 1 + x 2 ,x 2 1 -x 1 +
x 2 be the ≺ -Gröbner basis of J . Then, the associated staircase is {1,x 2 ,x 1 } and D = 3. One can read the matrix of the multiplication by x 2 in [x 1 ,x 2 ]/ J in this monomial basis dire ly from H . It is

M x 2 = 1 x 2 x 1 0 0 0 1 1 -1 -1 x 2 0 1 1 x 1 ∈ D ×D ,
where the i th column is the image of the i th monomial of the staircase by its multiplication by x 2 .

The univariate polynomial matrix P x 2 is obtained from the polynomials in H whose leading monomials are multiples of x 2 , i.e. the first t = 2 polynomials of H , and decomposed in the

[x 2 ]-module [x 2 ] + x 1 [x 2 ].
It is

P x 2 = x 2 2 + x 2 x 2 1 -1 x 2 -1 x 1 ∈ [x 2 ] t ×t .
Its Hermite normal form is

x 3 2 -x 2 2 -x 2 1 0 1 x 1 ,
which allows us to read that the polynomials x 3 2 and x 1x 2 2x 2 are both in J and [x 2 ] + x 1 [x 2 ]. Thus, they form the ≺ -Gröbner basis of J .

.

Saturated and colon ideals

Let I be an ideal of [x] and ∈ [x]. The colon and saturation ideals of I w.r.t. are defined as

I : = {h ∈ [x] | h ∈ I } , I : ∞ = h ∈ [x] ∃k ∈ ℕ, h k ∈ I .
Let us recall that by [ , Chap. ], the algebraic set

V (I : ∞ ) ⊂ n is the Zariski closure of the set di erence V (I ) \ V ( ).
Computing algebraic representations of saturated ideals arises in many applications ranging from experimental mathematics to engineering sciences (see [ , , ]) since some natural algebraic modelings come with parasite solutions which one excludes through some saturation process. For instance, modeling that some (p × q )-matrix with polynomial entries has rank r through the simultaneous vanishing of its (r + 1)-minors will include those points at which the matrix has rank less than r .

Chapter 3. Computing Gröbner bases 3.2. Saturated and colon ideals

Since

I : = 1 (I ∩ ) = (tI + (1 -t ) ) ∩ [x] I : ∞ = (I + 1 -t ) ∩ [x],
using Rabinowitsch's trick [ ] and [ , Chap. , Sec. , Th. , (ii)], one can compute Gröbner bases of these ideals choosing a monomial order eliminating t and keeping all polynomials not involving t , see also [ , Chap. , Sec. , Th. and Ex. ]. This se ion is about the computational problem of computing a Gröbner basis associated to I :

∞ or I : without introducing an extra variable. This is joint work with Christian Eder and Mohab Safey El Din . Output: A ≺ -Gröbner basis of I :

. . Bayer's algorithm

If I is homogeneous, i.e. it
x n ∞ . Homogenize f 1 , . . . , f s with variable x 0 to obtain f h 1 , . . . , f h s . Compute G , the ≺ -Gröbner basis of f h 1 , . . . , f h s with x n ≺ • • • ≺ x 1 ≺ x 0 . For each g in G h do While x n | g do g g /x n . Set x 0 to 1 in g . Return G .
Algorithm . : Bayer's algorithm When ≠ x n , one introduces a slack variable x n+1 , computes the saturation of I + x n+1w.r.t. x n+1 and eliminate x n+1 .

Rabinowitsch's trick and Bayer's algorithm constitute the state-of-the-art algorithms for computing saturations of ideals. Note that they do not take advantage of intermediate data obtained during the Gröbner basis computations since these are used as black boxes.

. . F SAT, an algorithm for saturated ideals

After the first step of the F algorithm in degree d , if no new polynomial of degree at most d is discovered, then the current Gröbner basis G is a d -truncated ≺-Gröbner basis of I . Therefore, we have a partial information on the staircase of I , and thus of I :

∞ , for ≺ since we know monomials that are outside of this staircase. The F SAT algorithm searches for polynomials in I :

∞ whose supports are entirely included in the given staircase using the fa that I :

∞ : = I : ∞ . If new polynomials are found, they are added to G and the necessary critical pairs are added to the set of pairs to handle. Then, we resume the F algorithm.

The search of new polynomials is done through linear algebra computations. From a d -truncated Gröbner basis of an ideal J , I ⊆ J ⊆ I :

∞ , we compute a bound B on the degree of the polynomials in the reduced Gröbner basis of J : ∞ = I : ∞ using the ComputeMaxDegree subroutine based on [ , Sec. . , Cor.]. Then, we compute NF ( , G, ≺) for all monomials in the associated staircase S of degree at most B. Finally, we search for vanishing linear combinations thereof. Indeed, if NF (s , G, ≺) -

∈S d ≺s c NF ( , G, ≺) = 0,
then s -∈S d , ≺s c ∈ J . This yields Algorithm . . Theorem 3.3 ([15,Th. 3.1]): Let f 1 , . . . , f s be a generating family of an ideal I ⊆ [x], ∈ [x] be a polynomial and ≺ be a total degree monomial order. Then, Algorithm . terminates and returns

Chapter 3. Computing Gröbner bases 3.2. Saturated and colon ideals

Input: A list of polynomials f 1 , . . . , f s spanning an ideal I ⊆ [x], a polynomial ∈ [x] and a total degree monomial order ≺. Output:

A ≺-Gröbner basis G of I : ∞ . G f 1 , . . . , f s . b true // tracks if G has changed P ( f i , f j ) 1 ≤ i < j ≤ s While P ≠ ∅ do
Choose a subset L of P .

P P \ L. L SymbolicPreprocessing(L, G). L LinearAlgebra(L). For h ∈ L with ≺ (h) ∉ ≺ ( G) do P (g ,h) g ∈ G . G G∪ {h}. b true. If b then // new information on ≺ (I : ∞ ) b false. B ComputeMaxDegree( G, ).
// bounds the degrees in the sought Gröbner basis

For ∉ ≺ ( G) and deg ≤ B do q NF ( , G, ≺).

Build the matrix M whose rows are given by polynomials q and columns by each monomials in their support in decreasing order. Compute a lower triangular basis K of the left-kernel of M .

For each k ∈ K do h ∉ ≺ ( G) k .
// the polynomial whose ve or of coe cients is k P

(g ,h) g ∈ G . G G∪ {h}. b true.
Return G.

Algorithm . : F SAT Chapter 3. Computing Gröbner bases 3.2. Saturated and colon ideals a ≺-Gröbner basis of I : ∞ .

Example 3.4: Let us call the F SAT algorithm on the reduced ≺ -Gröbner basis

G = (x 2 2 - x 1 + x 2 )(x 2 1 + x 2 2 -1), (x 2 1 -x 1 x 2 -x 2 2 + x 1 -x 2 )(x 2 1 + x 2 2 -1) and = x 4 1 -x 4 2 -2x 2
1 + 1 in order to compute the reduced ≺ -Gröbner basis of I :

∞ with

I = (x 4 2 + x 3 2 )(x 2 1 + x 2 2 -1), (x 1 -x 2 2 -x 2 )(x 2 1 + x 2 2 -1) . From G , we have the staircase S = {1,x 2 ,x 1 ,x 2 2 ,x 1 x 2 ,x 2 1 ,x 3 2 ,x 1 x 2 2 ,x 2 1 x 2 ,x 3 1 ,x 4 2 ,x 1 x 3 2 ,x 3 1 x 2 ,x 5 2 ,x 1 x 4 2 , x 6
2 ,x 1 x 5 2 , . . .}. Since this staircase is infinite, we first need a degree bound for the considered monomials in S . Let us choose the maximal degree in G minus one, i.e. 3.

The normal form of h w.r.t. G and ≺ , where h of degree 3 has its support in S is 0, if, and only if,

h = c 3 (x 2 2 -x 1 + x 2 ) + c 5 (x 2 1 -x 1 x 2 ) + c 6 (x 3 2 -x 1 x 2 + x 1 -x 2 ) + c 7 x 1 x 2 2 + c 8 x 2 1
x 2 + c 9 x 3 1 . Thus, we have found new polynomials in I :

∞ . We build the ideal I , spanned by I and these polynomials, and compute its reduced ≺ -Gröbner basis

G = x 2 2 -x 1 + x 2 ,x 2 1 -x 1 x 2 .
The new associated staircase is S = {1,x 2 ,x 1 ,x 1 x 2 }, which is now finite. The normal form of h w.r.t. G and ≺ , where h has its support in S , is 0 if, and only if,

h = c 3 (x 1 x 2 -x 1 + x 2 ).
We have found a new polynomial x 1 x 2x 1 + x 2 and compute the reduced ≺ -Gröbner basis

H = x 2 2 -x 1 + x 2 ,x 1 x 2 -x 1 + x 2 ,x 2 1 -x 1 + x 2 of J = I + x 1 x 2 -x 1 + x 2 .
The new associated staircase is T = {1,x 2 ,x 1 } and we cannot find a nonzero polynomial h with support in T whose normal form w.r.t. H and ≺ is 0. Therefore H is the reduced ≺ -Gröbner basis of I :

∞ = J = x 3 2 ,x 1 -x 2 2 -x 2 .
In Table . , we present timings for di erent systems with coe cients in ℚ. The F SAT algorithm is implemented in with a multi-modular approach using a tracer. This tracer requires two learning phases modulo two di erent primes before being able to run its apply phase modulo subsequent primes. We compare it with Rabinowitsch's trick implemented in either with probabilistic linear algebra or with the tracer, and with M and S . Most of the time in the first learning phase is due to the last saturation step, i.e. checking in line that no new polynomial are found in the saturated ideal. As we can see, the apply phase of F SAT is the fastest implementation by an order of magnitude. The SOS systems are obtained by making a polynomial f as the sum of the squares of p random polynomials of degree d . Then, we consider the ideals

f , f x 1 , . . . , f x s or f x 1 , . . . , f x s , for s ≤ n -1, saturated by f x n .
. .

S -FGLM-, an algorithm for colon ideals

For an ideal I = f 1 , . . . , f s and a polynomial , the colon ideal of I by is

I : = {h|h ∈ I } .
This ideal contains I and is included in I : ∞ defined in Se ion . . . In fa , there exists an integer N such that I :

N = I : N +1 = • • • = I : ∞ , see [ , Chap.
]. Let G be the reduced ≺ -Gröbner basis. We assume that the colon ideal I : is zerodimensional, thus ∉ I , and that its reduced ≺ -Gröbner basis H is in shape position: There

exist h 1 , . . . ,h n ∈ [x n ], with deg h k < deg h n for 1 ≤ k ≤ n -1, such that H = {h n (x n ),x n-1 -h n-1 (x n ), . . . ,x 1 -h 1 (x n )} .
With my co-authors, Christian Eder and Mohab Safey El Din , we designed a new algorithm in [ ] for computing H from G , even when I is positive-dimensional. Our approach is to build a matrix Mx n so that applying Wiedemann's algorithm allows us to recover H , similarly to the S -FGLM algorithm [ , ], see also Algorithms . and . . , if it is in shape position. Build the matrix M of the multiplication by x n followed by the proje ion on the space spanned by Σ. Pick r ∈ N a row-ve or at random. Build the column-ve or of coe cients of restri ed to Σ. For k from 1 to n -1 do Build k the column-ve or of coe cients of NF (x k , G , ≺ ) restri ed to Σ.

Compute (w

(0) i ) 0≤i <2N , (w (1)
i ) 0≤i <N , . . . , (w (n-1) i

) 0≤i <N ) with Algorithm . called on M ,r , , 1 , . . . , n-1 .

h n ← Berlekamp-Massey(w (0) 0 , . . . ,w (0) 2D -1 ), D deg h n . If NF (h n , G , ≺ ) ≠ 0 then Return "Bad ve or". Compute h 1 D -1,1 x N -1 n + • • • + 0,1 , . . . ,h n-1 D -1,n-1 x N -1 n + • • • + 0,n-1 with Algorithm . called on (w (0) i ) 0≤i <2D -1 , (w (1) i ) 0≤i <D , . . . , (w (n-1) i ) 0≤i <D ). For k from 1 to n -1 do If NF ((x k -h k (x n ))
, G , ≺ ) ≠ 0 then Return "Not in shape position".

Return {h n (x n ),x n-1 -h n-1 (x n ), . . . ,x 1 -h 1 (x n )}.
Algorithm . : S -FGLMsubmatrix. In

Let G = x 2 2 -x 1 + x 2 ,x 2 1 -x 1
x 2 be the ≺ -Gröbner basis of the ideal I and = x 4 1x 4 2 -2x 2 1 + 1. We build a sequence u with random initial coe cients, e.g. u 0,0 = -4, u 1,0 = 10, u 0,1 = -3 and u 1,1 = -8, thanks to G :

u = . . . . . . . . . . . . . . . . . . 5 5 0 0 0 • • • 4 -5 0 0 0 • • • 3 5 0 0 0 • • • 2 -13 0 0 0 • • • 1 10 -8 0 0 • • • 0 -4 -3 -8 0 • • • i 2 i 1 0 1 2 3 • • •
We now consider the auxiliary sequence

v = Eval x i 1 1 x i 2 2 ,u (i 1 ,i 2 ) ∈ℕ 2 , i.e. v i 1 ,i 2 = u i 1 +4,i 2 -u i 1 ,i 2 +4 - 2u i 1 +2,j + u i 1 ,i 2 for all (i 1 ,i 2 ) ∈ ℕ 2 , to find the ≺ -Gröbner basis H of I : = J , v = . . . . . . . . . . . . . . . . . . . . . 4 0 0 0 0 0 • • • 3 0 0 0 0 0 • • • 2 -8 0 0 0 0 • • • 1 5 -8 0 0 0 • • • 0 17 -3 -8 0 0 • • • i 2 i 1 0 1 2 3 4 • • • By Example . , we have H = x 3 2 ,x 1 -x 2 2 -x 2 .
In Table . , we compare Algorithm . for computing a ≺ -Gröbner basis of the zero-dimensional colon ideal I :

= I : ∞ for ≺ with M [ ] using the Groebner:-Basis command followed by the Groebner:-FGLM command. The considered input generators are

I = f , f x 1 , . . . , f x n-1 and = f x n M
for M large enough, with f the sum of p squares of polynomials of degree d in n variables. The columns # Σ and # Σ correspond to the size of the set Σ before and Chapter 3. Computing Gröbner bases 3.3. Parametrizations of the radical after redu ions by removing the zero columns, while column D gives the degree of the saturated ideal. Whether it is between # Σ and # Σ or between # Σ and D , we can observe ratios going up to around 5. Therefore, it is clear that the algorithm would not be as e cient if one were to work with Σ dire ly. Still, it would be even more beneficial to reduce further the size of Σ to be as close as possible to D .

For , we give proportions of time spent to compute the ≺ -Gröbner basis of I with F , to compute the normal form of corre power of , to build the multiplication matrix, including the computation of extra normal forms, and then to compute the ≺ -Gröbner basis. We also give the time for M in seconds using Rabinowitsch's trick [ ] and give the time for computing a ≺ -Gröbner basis and then for the change of order step to obtain a ≺ -Gröbner basis.

We can notice that the S -FGLM-algorithm approach is most e cient when either the change of order step is the most time-consuming or when the ratios between # Σ, # Σ and D are the smallest. In the former case, the algorithm benefits from the regularity of the computation of the reduced ≺ -Gröbner basis of I compared to the one of I + 1t in the Rabinowitsch's trick approach. In the latter case, when Σ or Σ are large compared to D , the overhead in the linear algebra part becomes overwhelming. Clearly, in a multi-modular approach, one would want to consider an even smaller subset of Σ to perform the computations, once D is known. All in all, we can see speed-ups that are significant and sometimes higher than 10. Table . : Timings in seconds, ≺ -Gröbner bases, positive-to-0-dimensional case.

.

Parametrizations of the radical

Proposition 3.6 (see also [15,Prop. 4.17]): Let I be a positive-dimensional ideal of [x], let G be its reduced ≺ -Gröbner basis and S be the associated staircase. Let ∈ [x] \ I such that I : is zero-dimensional, let H be its reduced ≺ -Gröbner basis and let

h n ∈ H ∩ [x n ]. If I :
is in shape position, then one can compute its reduced ≺ -Gröbner basis calling the S -FGLM-algorithm with the following modifications: ( ) On line , h n is the squarefree part of the polynomial returned by the Berlekamp-Massey algorithm.

( ) On line , h k is obtained thanks to [ , Algo. ], see also [ ].
In pra ice, when an ideal J is not in shape position, it is not easy to check that J is. Therefore, using the following lemma is the cornerstone of our probabilistic verification algorithm in [ , ] when J is not in shape position but its radical might be, see [ , Sec. . ]. Lemma 1.12 (see also [15,Lem. 4.15]): Let I be a zero-dimensional ideal of [x]. Let ∈ ¯ be generic. Then, for 1 ≤ k ≤ n, I = I : x k + .

We proceed as follows. k for 1 ≤ k ≤ n -1. By Lemma . , for a generic , J = J : x k + , hence both radical ideals are the same. Furthermore, if they are in shape position, then g k = g k for 1 ≤ k ≤ n -1. Therefore, any discrepancy must come from the fa that J is not in shape position and the polynomials x kg k (x n ) and x kg k (x n ) are meaningless.

( ) Compute the polynomials x k -g k (x n ) in J for 1 ≤ k ≤ n -1, with deg g k minimal. ( ) Compute the polynomials x k -g k (x n ) in J : x k + for

Chapter 4. Guessing Gröbner bases

Chapter 4 Guessing Gröbner bases

This chapter is devoted to guessing Gröbner bases of ideals of C-relations of sequences. That is, given a finite number of terms of a sequence, the goal is to discover the linear recurrence relations, given by polynomials, satisfied by these few terms.

In some applications, like the Gröbner bases change of order one, see Se ions . . and . , or in coding theory [ , , ], a bound on the sizes of the relations is known. Therefore, testing the relations with su ciently enough terms ensures that these are satisfied by the whole sequence. In other cases, like in combinatorics or number theory [ , , , ] no a priori bound is known. In which case, one must prove afterwards the validity of the relations.

We first recall how to guess C-relations for uni-indexed sequences using the seminal Berlekamp-Massey algorithm [ , ] and its faster variants [ ] in Se ion . . Then, we describe extensions of this algorithm to multi-indexed sequences, where my contributions lie, in Se ion . . This chapter is based on joint work with Brice Boyer , Jean-Charles Faugère , and Mohab Safey El Din [ , , , , ].

In all this chapter, multi-Hankel matrices will be used. These generalize the notion of Hankel matrices to multi-indexed as follows: given two sets of monomials T 1 and T 2 in x and a sequence u,

H T 1 ,T 2 = ••• x j ∈T 2 ••• . . . . . . . . . . . . x i ∈T 1 • • • Eval x i x j ,u • • • . . . . . . . . . . . .
.

Uni-indexed sequences and the Berlekamp-Massey algorithm

Let u = (u i ) i ∈ℕ be a one-dimensional sequence that we assume C-finite. The goal is to find the unique polynomial

G x d = x d + x d -1 x d -1 + • • • + 1 with d minimal such that I C (u) = G x d .
Though, in general d is not known and only the first N terms of u: u 0 , . . . ,u N -1 are known. Therefore, we aim to guess G x d using the fa that it must satisfies

Eval G x d ,u = • • • = Eval G x d x N -d -1 ,u = 0. ( . )
. .

Matrix viewpoints

Requiring that d is minimal and 1 , . . . , x d -1 are such that Equation ( . ) is satisfied is equivalent to looking for the largest colle ion of ve ors 1 . . .

x d -1 1 0 0 . . . 0 , 0 1 . . . x d -1 1 0 . . . 0 , . . . , 0 0 . . . 0 1 . . . x d -1 1 in the kernel of H {1},{1,...,x d -1 ,x d ,x d +1 ,...,x N -1 } = 1 ••• x d -1 x d x d +1 ••• x N -1 1 u 0 • • • u d -1 u d u d +1 • • • u N -1 .
former Post-doc at Sorbonne Université INRIA CryptoNext Security Sorbonne Université

Chapter 4. Guessing Gröbner bases

Uni-indexed sequences and the Berlekamp--Massey algorithm

Equivalently, one also looks for the smallest integer d such that

H T x N -d -1 ,T x d 1 . . . x d -1 1 = 1 ••• x d -1 x d 1 u 0 • • • u d -1 u d x u 1 • • • u d u d +1 . . . . . . . . . . . . x N -d -1 u N -d -1 • • • u N -2 u N -1 1 . . . x d -1 1 = 0,
where T m denotes the set of all monomials less or equal to m for ≺, the only monomial order on

[x].
With this modeling of the problem, we are led to a polynomial viewpoint.

. . Polynomial viewpoint

The Hankel matrix-ve or produ can be extended into

u 0 • • • u d -1 u d u 1 • • • u d u d +1 . . . . . . . . . u N -d -1 • • • u N -2 u N -1 u N -d • • • u N -1 0 . . . . . . . . . . . . u N -1 0 • • • 0 1 . . . x d -1 1 = 0 0 . . . 0 r x d -1 . . . r 1 , ( . )
representing the produ of the two polynomials

P T x N -1 = N -1 i =0 u i x N -i -1
, given by the sequence terms, and

G x d = x d + d -1 k =0 x k x k , giving the C-relation, modulo B = x N .
This can rewritten as follows, there exists

Q ∈ [x] such that Q • x N + G x d N -1 i =0 u i x N -i -1 = R, deg R < d , ( . )
which is a Bézout relation between x N and P T x N -1 , where we ask that the degree of the right-hand side member, or equivalently its leading term, is less than that of the cofa or of P T

x N -1 . The main advantage of this viewpoint is that we can now compute d and G x d using the extended Euclidean algorithm on x N and P T

x N -1 and stop the algorithm when a Bézout relation satisfies Equation ( . ).

This viewpoint gives rise to Algorithm . , which is a variant of the BM algorithm and a modified extended Euclidean algorithm. While, as written, its complexity is quadratic in N , one can use fast Euclidean algorithm [ ] to improve the time complexity to O (M(n) log n). With the matrix viewpoint, the kernel of

Input: u 0 , . . . ,u N -1 , the first N terms of a sequence u. Output: A polynomial C of degree d , with d minimal such that Eval C x i ,u = 0 for all 0 ≤ i ≤ N -d -1. m 1 /x, L m x N , 0 . m 1, L m N -1 i =0 u i x N -i -1 , 1 . While deg L m ,2 ≤ deg L m ,1 do Q Quo(L m,1 ,L m ,1 ). L m ≺ (Q ) L m -Q L m . m,m m ,m ≺ (Q ). Return L m ,2 .
H {1},{1,x,x 2 ,x 3 ,x 4 ,x 5 ,x 6 ,x 7 ,x 8 } = 1 x x 2 x 3 x 4 x 5
x 6

x 7

x 8

1 -4 10 -13 5 -5 5 -5 5 -5 ,

gives us the colle ion of ve ors

0 0 0 1 1 0 0 0 0 , 0 0 0 0 1 1 0 0 0 , 0 0 0 0 0 1 1 0 0 , 0 0 0 0 0 0 1 1 0 , 0 0 0 0 0 0 0 1 1 , hence I C (w) = x 4 + x 3 .
Equivalently, we have that

H {1,x,x 2 ,x 3 ,x 4 },{1,x,x 2 ,x 3 ,x 4 } 0 0 0 1 1 = 1 x x 2 x 3
x 4 1 -4

10 -13 5 -5

x 10 -13 5 -5 5

x 2 -13 5 -5 5 -5

x 3 5 -5 5 -5 5

x 4

-5 5 -5 5 -5

0 0 0 1 1 = 0 but H {1,x,x 2 ,x 3 ,x 4 ,x 5 },{1,x,x 2 ,x 3 } = 1 x x 2
x 3 1 -4 10 -13 5

x 10 -13 5 -5

x 2 -13 5 -5 5

x 3 5 -5 5 -5

x 4

-5 5 -5 5

x 5

5 -5 5 -5

has full rank, ensuring that no relation given by a polynomial of degree 3 exists. With the polynomial viewpoint, we perform the extended Euclidean algorithm on x 9 and P T

x 8 and find

L1 /x = [x 9 , 0] L 1 = [-4x 8 + 10x 7 -13x 6 + 5x 5 -5x 4 + 5x 3 -5x 2 + 5x -5, 1] L x = [24x 7 -55x 6 + 15x 5 -15x 4 + 15x 3 -15x 2 + 15x -25, 2x + 5] L x 2 = [-1 237x 6 + 285x 5 -285x 4 + 285x 3 -285x 2 + 45x -595, 48x 2 + 110x + 119] L x 3 = [-2 560x 5 + 2 560x 4 -2 560x 3 -3 625x 2 + 2 200x -1 600, 1 237x 3 + 285x 2 -120x + 320] L x 4 = [-5x 3 ,x 4 + x 3 ] = [R x 4 ,G x 4 ],
and G x 4 = x 4 + x 3 is a valid relation.

Remark 4.2:

The BM algorithm always returns a non-zero relation. If no pair

L x = [R x ,G x ]
satisfies the requirements, then it will return a pair L x d with ≺ (G x d )

x N -1 . From a matrix viewpoint, it returns an element of the kernel of the empty matrix H ∅,T

x d .

Chapter 4. Guessing Gröbner bases 4.2. Extensions to multi-indexed sequences .

Extensions to multi-indexed sequences

This se ion is devoted to several extensions of the uni-indexed case to the multi-indexed one. It is based on several joint works with Brice Boyer , Jean-Charles Faugère , and Mohab Safey El Din .

A first extension to the BM algorithm was proposed by Sakata for bi-indexed sequences [ ] and then was extended to n-indexed sequences [ , ]. This is the so-called Berlekamp-Massey-Sakata (BMS) algorithm. Then, Brice Boyer , Jean-Charles Faugère , and I designed a linear-algebra-based one, called S -FGLM, in [ , ] and an adaptive variant thereof. Mourrain also proposed another algorithm using a Gram-Schmidt process in [ ], called AG . Finally Jean-Charles Faugère , and I on one hand and Mohab Safey El Din and I on another hand proposed several extensions and improvements of the S -FGLM algorithm in [ , , ]. We assume now that ≺ is a monomial order such that for any monomial x i ∈ ℕ n , the set T x i is finite. Such orders compare first monomials by (weighted) degrees, like ≺ . While ≺ is not such a monomial order, one can choose a monomial order ≺ such that the ≺-Gröbner basis and the ≺ -Gröbner basis coincide by putting large weights on the first variables. Though, these weights will depend on the ideal of C-relations one is dealing with.

. . The BMS algorithm

Given a multi-indexed sequence u = (u i ) i ∈ℕ n , a monomial order ≺ and a monomial M = x a 1 1 • • • x a n n , the BMS algorithm extends the BM algorithm by computing ve ors in the kernel of a multi-Hankel matrix

H {1},T M = 1 ••• M 1 u 0,...,0 • • • u a 1 ,...,a n ,
corresponding to having relations Eval G m x i ,u = 0, with ≺ (G m ) = m minimal for the division and for all x i such that mx i M .

While the BMS algorithm computes the C-relations using polynomial multiplications by monomials and additions, Jean-Charles Faugère , and I proposed in [ , ] the following polynomial interpretation. This is a key argument towards the design of our algorithm that guesses the Crelations using polynomial arithmetic, including multivariate polynomial redu ions, which extends the univariate Euclidean division.

Guessing a ≺-Gröbner basis of I C (u) comes down to finding the least (for the partial order |) monomials m 1 , . . . ,m r M such that dim ker H T s k ,T m k > 0 with s k the greatest monomial such that s k m k M for all k , 1 ≤ k ≤ r . Indeed, by the minimality of the leading monomials, if su ciently many terms of u are known, these polynomials form a minimal ≺-Gröbner basis of I C (u).

Then, each multi-Hankel matrix-ve or produ can be extended further as in equation ( . ), taking the multi-Hankel matrix H T M ,T m k and replacing by zero any sequence term u i+ j = Eval x i x j ,u that we do not know, i.e. whenever x i x j M . This yields the linear system

Eval (1,u) • • • Eval m - k ,u Eval (m k ,u) Eval (1 + ,u) • • • Eval 1 + m - k ,u Eval (1 + m k ,u) . . . . . . . . . Eval (s k ,u) • • • Eval s k m - k ,u Eval (s k m k ,u) Eval s + k ,u • • • Eval s + k m - k ,u 0 . . . . . . . . . Eval (M ,u) 0 • • • 0 1 . . . m - k 1 = 0 0 . . . 0 f M/s + k . . . f M/a , ( .
)
where M and that, more generally, the gray zeroes need not be diagonally aligned like they are in the univariate case.

M = (T M ) = x N 1 1 • • • x N n n and
Such produ represents the produ of the polynomials

P T M = x i M u i M x i and G m k = m k + x i ≺m k x i x i modulo B = (x N 1 1 , . . . ,x N n n ). The requirement for G m k to encode a valid relation is now that ≺ (R m k ) ≺ M s k with R m k = P T M G m k mod B.
To compute these relations, one start with the pairs

L1 /xi = [x N i i , 0] for all 1 ≤ i ≤ n and L 1 = [P T M , 1].
Then, one computes S-polynomials and polynomial redu ions on the first coordinates of the pairs, and report the operations on the second coordinates of the pairs until finding all pairs

L m = [R m ,G m ],
where the leading monomial of R m is small enough for G m to encode a valid relation, for all m minimal for the partial order |. Theorem 1.13 (see also [19,Th. 1]): Let u be a sequence, ≺ be a weighted degree monomial order and M be a monomial. Let us assume that the reduced ≺-Gröbner basis G of I C (u) and its associated staircase S satisfy max(S ∪ ≺ ( G))

M and for all m M , s = max M { | m M }, we have max(S ) s . Then, the variant of the Berlekamp-Massey-Sakata algorithm using polynomial arithmetic terminates and computes Gin O (# S (# S + # G)# T M ) operations in the base field, where T M is the set of monomials less or equal to M .

Remark 4.3: As for the BM algorithm, the BMS algorithm will always return a relation G m with ≺ (G m ) = m a pure power in each variable. Therefore, it can return G m with m M , corresponding to a ve or in the kernel of the empty matrix H ∅,T m .

. . The S -FGLM algorithm

In [ , ], Brice Boyer , Jean-Charles Faugère , and I designed an algorithm, S -FGLM, that computes the reduced ≺-Gröbner basis of I C (u) by means of linear algebra. Together with u, it takes as an input a set of monomials T , ordered for ≺, and it computes the right kernel of the multi-Hankel matrix H T ,T . Ve ors in this kernel can be seen as polynomials in [x] and these polynomials with a leading term minimal for the partial order induced by the division are the ones returned by the algorithm. Furthermore, if T contains the staircase and the leading monomials of the reduced ≺-Gröbner basis of I C (u), then the S -FGLM algorithm returns this Gröbner basis.

Input: A sequence u = (u i ) i ∈ℕ n with coe cients in , a monomial ordering ≺, a su ciently large staircase T and ordered for ≺. Output: A reduced Gröbner basis of the ideal of C-relations of u. Build the matrix H T ,T . Compute the set S ⊆ T of smallest monomials, for ≺, such that rank H S,S = rank H T ,T . For all m ∈ T \ S do // stabilize S for the division

If ∃s ∈ S such that m | s then S S ∪ {m}. L T \ S sorted for ≺. G . While L ≠ do m min ≺ L Solve the linear system H S,S + H S, g = 0. G G ∪ {m + s ∈S s s }.
Remove m and any of its multiples from L.

Return G .

Algorithm . : S -FGLM

The algorithm computes the column rank profile of the matrix H T ,T , that is the set of leftmost linearly independent columns of the matrix. Since these columns are independent from the previous former Post-doc at Sorbonne Université INRIA CryptoNext Security Chapter 4. Guessing Gröbner bases 4.2. Extensions to multi-indexed sequences ones, their labels cannot be the leading monomial, for ≺, of any polynomial in the ideal of Crelations, thus they are in the associated staircase of the reduced ≺-Gröbner basis of this ideal.

4 0 0 0 0 0 • • • 3 0 0 0 0 0 • • • 2 -8 0 0 0 0 • • • 1 5 -8 0 0 0 • • • 0 17 -3 -8 0 0 • • • i 2 i 1 0 1 2 3 4 • • •
and assume we want to guess its reduced ≺ -Gröbner basis knowing that it contains no polynomial of degree higher than 3. We build the multi-Hankel H T ,T where T contains all the monomials of degree at most 3 and then determine its column-rank-profile, i.e. the leftmost independent columns,

H T ,T = 1 y x y 2 xy x 2 y 3 xy 2 xy 2 x 3
1 17 5 -3 -8 -8 -8 0 0 0 0 y 5 -8 -8 0 0 0 0 0 0 0

x -3 -8 -8 0 0 0 0 0 0 0

y 2 -8 0 0 0 0 0 0 0 0 0 xy -8 0 0 0 0 0 0 0 0 0 x 2 -8 0 0 0 0 0 0 0 0 0 y 3 0 0 0 0 0 0 0 0 0 0 xy 2 0 0 0 0 0 0 0 0 0 0 x 2 y 0 0 0 0 0 0 0 0 0 0 x 3 0 0 0 0 0 0 0 0 0 0 .
Clearly, the first 3 columns are independent, then the other columns, labeled with y 2 , xy, . . . linearly depend on them. Thus, 1, y,x = S . The leading monomials of the reduced ≺ -Gröbner basis are y 2 , xy and x 2 and we find the polynomials y 2x + y, xyx + y and x 2x + y.

The polynomial viewpoint presented in Se ion . . for the BMS algorithm is in fa more general. Taking the same notation as in Se ion . . , consider the more subtle condition for a relation to be valid: the leading monomial of R m , after discarding some monomials, is su ciently small. Then, the polynomial viewpoint allows one to compute ve ors in the kernel of a more general multi-Hankel, as those encountered in the S -FGLM algorithm. We refer the reader to [ , ] for more details.

When the nonzero terms of the sequence all lie in a cone C, we can decide to restri the constru ion of the multi-Hankel matrix to monomials in the associated algebra, i.e. the set of monomials T( C) = x i i ∈ C . In that setting, instead of guessing classical ≺-Gröbner bases, the guessed polynomials form a ≺-sparse Gröbner basis, as defined in [ , ]. Theorem 4.5 (see also [21,Th. 3.2]): Let C be cone which is also a submonoid of ℕ n . Let ≺ be a monomial order on the monomials in x. Let T ⊆ T( C) be a set of monomials stable by division.

Let u be a C-finite sequence such that I C (u) has a reduced ≺-sparse Gröbner basis Gwith support in T . Then, the S -FGLM algorithm called on u, T and ≺ computes G.

. . Adaptive algorithms

In many applications, including the change of order one when the ideal is not in shape position, computing sequence terms is expensive so that building such a large multi-Hankel matrix is prohibitive. In [ , ], my co-authors and I proposed an adaptive algorithm that starts with a 1 × 1-matrix given by T = {1}. Then, it makes it grow by adding a monomial in T . If the rank of the matrix grows, then we know that this new monomial is in the staircase of the sought Gröbner basis. Otherwise, we have guessed a polynomial in the target Gröbner basis.

This approach is similar to the original FGLM algorithm, though we might find fake C-relations when the first terms of the sequence are not generic. Later, Jean-Charles Faugère , and I designed an adaptive variant of the BMS algorithm in [ ] which can avoid testing some candidate relations, and thus requiring some sequence terms, when a bound of the degree of the zero-dimensional ideal of C-relations is known. Furthermore, in [ ], we used the polynomial viewpoint of the S -FGLM algorithm of [ ] and Se ion . . to have an adaptive algorithm using only multivariate polynomial arithmetic. In particular, we prove the following theorem. Theorem 1.14 (see also [19,Th. 26]): Let u be a sequence whose ideal of C-relations is zero-dimensional. Let ≺ be a monomial order, G be the reduced ≺-Gröbner basis of I C (u) and S be the associated staircase.

Assuming the A S -FGLM algorithm called on u returns a Gröbner basis G with staircase S and # S = # S , then S = S and G = G. Furthermore, the algorithm does not need more that # 2(S ∪ ≺ ( G)) sequence queries and O ((# S + # G) 2 # 2S ) operations to recover G, where 2S is the Minkowski sum of S with itself.

.

Benchmarks

In Figure . , we consider three families of ≺ -Gröbner basis based on the shape of their staircase: Re angle:

≺ ( G) = y d /2 ,x d in dimension 2 and ≺ ( G) = z d /3 , y d /2 ,x d dimension 3
. This case is the best for the size of the Gröbner basis compared to the size of the staircase.

L shape:

≺ ( G) = x y, y d ,x d in dimension 2 and ≺ ( G) = y z ,x z ,x y, z d , y d ,x d in dimension 3. This case is the worst for the number of sequence queries compared to the sizes of the staircase and the Gröbner basis.

Simplex:

≺ ( G) = y d ,x y d -1 , . . . ,x d in dimension 2 and ≺ ( G) = z d , y z d -1 ,x z d -1 , . . . , y d , x y d -1 , . . . ,x d in dimension 3, i.e. all the monomials of degree d . This case is the best for the number of sequence queries and the worst for the size of the Gröbner basis, both compared to the size of the staircase. The polynomial variant of the BMS and S -FGLM algorithms performs fewer arithmetic Chapter 4. Guessing Gröbner bases 4.3. Benchmarks operations than the others, for large d . More precisely, its number of operations appears to be linear in (# S ) 2 = O (# S (# S + # G)) in fixed dimension suggesting that the complexity estimate in Theorem . is pessimistic. This can be related to the uni-indexed case: the naive BM algorithm, based on naive extended Euclidean algorithm, is only quadratic in the number of sequence terms that one considers. This is the starting point of a work-in-progress of a new collaboration between Romain Lebreton and me that I detail in Se ion . .

Université de Montpellier

Chapter 5. Quasi-commutative Gröbner bases

Chapter 5

Quasi-commutative Gröbner bases

This chapter is dedicated to quasi-commutative polynomials, their link with linear recurrence relations with polynomial coe cients, or P-relations of a sequence and how to compute or guess them.

.

P-relations and quasi-commutative polynomials

Linear recurrence relations with polynomial, in the indices, coe cients is a large class of linear recurrence relations containing the class of C-relations. As a classical example, the binomial

sequence i 1 i 2 (i 1 ,i 2 ) ∈ℕ 2 satisfies, for all (i 1 ,i 2 ) ∈ ℕ 2 , (i 1 -i 2 + 1) i 1 + 1 i 2 = (i 1 + 1) i 1 i 2 , (i 2 + 1) i 1 i 2 + 1 = (i 1 -i 2 ) i 1 i 2 .
The Eval operator, see also Se ion . , can be extended to deal with these relations by adding a new set of variables = ( 1 , . . . , n ) with the property that ℓ = x ℓ x ℓ for all 1 ≤ ℓ ≤ n. The 2n variables satisfy the following quasi-commutative rules for all 1 ≤ k ,ℓ ≤ n, k ≠ ℓ ,

x k x ℓ = x ℓ x k , k ℓ = ℓ k , x k ℓ = ℓ x k , k x k = x k ( k + 1
). As a consequence, the polynomials in and x with coe cients in form a quasi-commutative ring, denoted [ ] x .

These polynomials allow us to represent P-relations through the Eval operator Eval r ∈R,s ∈S r ,s r x s ,u = r ∈R,s ∈S r ,s s r u s .

Observe that r x s k x i = (s ) k r x s +i . Therefore, for any g ∈ [ ] x , Eval g k x i ,u = i k Eval g x i ,u .

Thus, multiplying g on the right by k x i shifts the recurrence relation by i and multiplies it by i k .

We deduce that if g is such that Eval g x i ,u = 0 for all i ∈ ℕ n , then Eval g k x i ,u = 0 for all k ∈ ℕ n and i ∈ ℕ n . Hence, the set of polynomials that represent P-relations satisfied by a sequence u is a right ideal of [ ] x called the ideal of P-relations of u and denoted I P (u). From r x s k x i = (s ) k r x s +i , we also notice that for ≺, a monomial order on the variables and x, we have ≺ (g h) = ≺ (g ) ≺ (h) for any two polynomials g and h. Furthermore, the notion of Gröbner basis can be defined for right ideals with the property that a finite subset G of an ideal I is a Gröbner basis I w.r.t. ≺ if for any f ∈ I , there exist g ∈ G and a monomial m such that ≺ ( f ) = ≺ (g )m. In particular, Buchberger's algorithm and criteria can be extended to this setting, see [ ].

Example 5.1:

From (i 1 + 1 -i 2 ) i 1 +1 i 2 -(i 1 + 1) i 1 i 2 = 0 and (i 2 + 1) i 1 i 2 +1 -(i 1 -i 2 ) i 1 i 2 , we deduce that g 1 = ( 1 -2 )x 1 -( 1 + 1) and g 2 = 2 x 2 -( 1 -2 )
are in the ideal of P-relations of the binomial sequence.

Observe that in ( ) x = ( ) ⊗ [ ] x , that is and x still quasi-commute but we allow rational fra ions in , these two polynomials are linear in x and linearly independant. They thus span a zero-dimensional ideal that contains g

1 x 2 + g 2 = ( 1 -2 )x 1 x 2 -( 1 -2 + 1)x 2 -( 1 -2 ) = (x 1 x 2 -x 2 -1)( 1 -2 )
and thus x 1 x 2x 2 -1 representing the, so-called Pascal's rule, C-relation:

∀ (i 1 ,i 2 ) ∈ ℕ 2 , i 1 + 1 i 2 + 1 = i 1 i 2 + 1 + i 1 i 2 .
Chapter 5. Quasi-commutative Gröbner bases 5.2. Guessing P-relations .

Guessing P-relations

In the uni-indexed case and a sequence u = (u i ) i ∈ℕ , one can compute a basis of I P (u) using the Beckermann-Labahn algorithm [ ] and its recent improvements [ ], based on a divide-and-conquer approach. Many computer algebra systems propose an implementation of guessing P-relations algorithms, whether be it in the univariate or the multivariate case. We can cite for instance [ ] in .

. A linear-algebra-based algorithm

With Jean-Charles Faugère , , I designed an extension to the S -FGLM algorithm in order to guess P-relations or C-relations between several sequences. For P-relations satisfied by u, the idea is to build a generalized multi-Hankel matrix H T ,Θ , where T and Θ are sets of monomials in respe ively [x] and [ ] x . The entry at the interse ion of the column labeled with r x s and the row labeled with x i is Eval r x s x i ,u = (s + i) r u s +i . Therefore, a ve or in the right kernel of this matrix represents a polynomial G ∈ [ ] x such that Eval G x i ,u = 0 for all x i ∈ T .

Example 5.2: Consider the binomial sequence

i 1 i 2 (i 1 ,i 2 ) ∈ℕ 2 , Θ = {1, 2 , 1 ,x 2 ,x 1 , 2 x 2 , 1 x 2 , 2 x 1 , 1 x 1 }
is the set of all monomials of bidegree at most (1, 1) in and x for an order ≺ eliminating x and breaking ties on and on x using ≺ . We take T to be the set of all monomials of degree at most 3 so that T is larger than Θ.

H T ,Θ = 1 2 1 x 2 x 1 2 x 2 1 x 2 2 x 1 1 x 1 1 1 0 0 0 1 0 0 0 1
x 2 0 0 0 0 1 0 0 1 1

x 1 1 0 1 1 1 1 1 0 2
x 2 2 0 0 0 0 0 0 0 0 0

x 1 x 2 1 1 1 0 2 0 0 2 4

x 2 1 1 0 2 2 1 2 4 0 3

x 3 2 0 0 0 0 0 0 0 0 0

x 1 x 2 2 0 0 0 0 1 0 0 2 2

x 2 1 x 2 2 2 4 1 3 2 2 3 9

x 3 1 1 0 3 3 1 3 9 0 4

.

From this matrix, we can see the relations 2 x 2 -( 1 -2 ) and ( 1 -2 )x 1 -( 1 + 1).

More rencently, a divide-and-conquer algorithm was designed and proposed in [ ] which generalizes the Beckermann-Labahn algorithm to multi-indexed sequences.

. .

An hybrid approach

In the combinatorics context, the ultimate goal is not always to guess the whole Gröbner basis of the ideal of P-relations for a specific monomial order, but rather to determine if the sequence is P-finite or not. For instance, a necessary condition is that the ideal of P-relations in ( ) x is zerodimensional. Therefore, providing an adaptive algorithm that minimizes the number of sequence terms is of upmost importance.

In a similar fashion as in Se ion . . , we can discover, step by step, which monomials are in the staircase of the ideal of P-relations of [ ] x of the input sequence for the input monomial order ≺. In [ ], Jean-Charles Faugère , and I proposed an hybrid approach based on Gröbner bases computations for quasi-commutative polynomials to discover new P-relations without any extra queries to the sequence. The idea is that if two polynomials g 1 , g 2 ∈ [ ] x encode P-relations satisfied by the sequence, then any polynomial in g 1 , g 2 also encodes a P-relation. Therefore, as soon as two P-relations g 1 and g 2 are guessed, the goal is to compute a Gröbner basis g 1 , g 2 , . . . , g r of g 1 , g 2 . This will yield polynomials, namely g 3 , . . . , g r , whose leading monomials are not in ≺ (g 1 ), ≺ (g 2 ) . The advantage of this method is twofold. First, since ≺ (g 3 ), . . . , ≺ (g r )

INRIA CryptoNext Security

Chapter 5. Quasi-commutative Gröbner bases 5.3. Structured sequences ≺ (g 1 ), ≺ (g 2 ), they require more queries to the sequence to be corre ly guessed. Yet, such a Gröbner basis computation does not require any more queries. Then, these P-relations may help us determine that the ideal of P-relations is 0-dimensional in ( ) x , which is a necessary condition for the table to be P-finite.

.

Stru ured sequences

In many applications, like in enumerative combinatorics with D/ D-walks, the studied sequences are highly stru ured. For instance, they have a lot of zero-terms. From a linear algebra viewpoint, these zero terms induce void conditions on the C-relations or P-relations and thus drops of ranks in the generalized multi-Hankel matrix that one deals with to guess the relations. Therefore, we need to build matrices with many more rows than columns to recover corre relations, i.e. C-relations or P-relations that do not prove to be fake after further testings.

The goal is thus to only deal with the nonzero terms from the beginning. These nonzero terms lie in general in a cone C which is a submonoid of ℕ n , i.e. 0 ∈ C and for all i, j ∈ C, i + j ∈ C.

In [ ], Mohab Safey El Din and I extended the S -FGLM algorithm, and its variants, adaptive and for P-relations, so that it only considers terms of a sequence lying in a cone. In this paper, we make the connexion with sparse Gröbner bases as defined in [ , ] and extend them to the context of quasi-commutative polynomials in [ ] x for P-relations.

Given such a cone C and polynomials with support in its associated set of monomials T( C) = x i ∈ T i ∈ C , one may want to perform all the polynomial operations with monomials in T( C) in order to take advantage of the stru ure of the support when computing a Gröbner basis of the ideal they span. While this is not always possible, one can achieve this goal by considering the ideal the polynomials span in the algebra

[ C] = f = s ∈ C f s x s supp f is finite .
The ideal spanned by f 1 , . . . , f m ∈ [ C] is defined as

f 1 , . . . , f m C = m k =1 f k q k q 1 , . . . ,q m ∈ [ C] .
Given a monomial order ≺, a ≺-sparse Gröbner basis of f 1 , . . . , f m C is a finite subset thereof whose properties extend those satisfied by a Gröbner basis, in the context of the algebra [ C]. In particular, the divisibility property on the leading monomials in T( C) is still satisfied. Definition 5.3 ([56,Def. 3.1] and [7,Def. 3.3]): Let C ⊆ ℕ n be a submonoid, f 1 , . . . , f m ⊆ [ C] be polynomials and ≺ be a monomial order. Let I = f 1 , . . . , f m C . Then, a ≺-sparse Gröbner basis of I is a generating set G = g 1 , . . . , g t ⊆ [ C] such that for all f ∈ I , ≺ ( f ) = ≺ (g )x i for some g ∈ G and x i ∈ C.

The associated staircase of G is the set of monomials s in T( C) such that for any g ∈ G, there is no monomial ,(2,1) and (1, 2) as a submonoid of ℕ 2 . Although x 1 x 2 divides both x 2 1 x 2 and x 1 x 2 2 in [x], it does not in [ C] as the respe ive quotients are x 1 and x 2 , which are not in T( C).

x i ∈ T( C) such that s = ≺ (g )x i . Let us notice that for C = ℕ n , [ C] = [ℕ n ] = [x]
= (i 1 ,i 2 ) ∈ ℕ 2 i 1 ≤ 2i 2 ,i 2 ≤ 2i 1 is spanned by (1, 1)
Theorem 5.5 (see also [21,Th. 3.2]): Let C be a submonoid cone of ℕ n spanned by a finite minimal set of generators. Let ≺ be a monomial ordering on T, the set of monomials in n variables, and let T ⊂ T( C) be a set of monomials ordered for ≺ stable by division.

Then, the S -FGLM algorithm called on sequence u, T and ≺ returns a set of polynomials G with support in T( C), such that for all s ∈ T \ ≺ (G ) , s is in the associated staircase of a Furthermore, if the ideal of C-relations of u is 0-dimensional and has a reduced ≺-sparse Gröbner basis with support in T , then the output of the S -FGLM algorithm called on u and T is this reduced ≺-sparse Gröbner basis.

As an illustration, we consider walks in D-and D-spaces, namely Gessel planar walk g in the nonnegative quadrant ℕ 2 with steps in {(1, 0), (1, 1), (-1, 0), (-1, -1)} and the D-space Walk-43 w of [ ] in the nonnegative o ant ℕ 3 with steps in {(-1, -1, -1), (-1, -1, 1), (-1, 1, 0), (1, 0, 0)}. In particular, we restri ourselves to a subsequence of each where one index is 0. These walks come naturally with a cone stru ure: for instance whenever n ≠ 2n + 2 j , then g n,0,j = 0. Likewise, whenever n ≠ 8n + 2 j + 4k , then w n,0,j,k = 0. Thus, it makes sense to look for the relations given by the sequence terms g 2n +2 j,0,j and w 8n +2 j +4k ,0,j,k .

Chapter 6

Research project I want to develop my research proje on computing and guessing Gröbner bases in the commutative and quasi-commutative setting relying on as a validation tool. The main goal is to develop general implementations on the one hand and specific ones for applications from combinatorics, cryptography or robotics on the other hand.

I present my research proje in three axes. The first one, in Se ion . , is about and its development. I see it as a transverse axis. The goal is to implement existing algorithms presented in the previous chapters but also new ones that shall be designed in the other axes. Furthermore, I shall exploit high-performance computing hardware to enhance the computation capabilities of . As a second axis, Se ion . , I aim to accelerate guessing algorithms, especially for C-relations, in order to provide theoretical and pra ical complexity estimates on the S -FGLM algorithms when roots have multiplicities. In particular, we will trade the information on the multiplicities for the e ciency and vice versa, when a second multiplication matrix is required. A polynomial matrix extension is also targeted.

The last axis, Se ion . , is dedicated to Gröbner bases for quasi-commutative polynomials in order to deal with P-relations. The main obje ive is to bring the complexity of ≺ -Gröbner bases for quasi-commutative polynomials to that of classical polynomials.

. and fundamental algorithms

A first goal for is to increase its fun ionalities by implementing state-of-the-art techniques for general ideals which are not covered yet. Furthermore, at the moment the modular implementation uses native integer types which allow us to handle large chara eristic but with computations that are slower than those using floating-point types.

. . Types for the coe cients

For the moment, uses native integer types to represent modular integers with primes of size at most 31 bits. While some fast Central Processing Unit (CPU) instru ions (like AVX or AVX ) are available for integer types, current CPUs are such that even faster instru ions are available to floating-point types. These types allow us to handle modular arithmetic for lesser prime (up to 26 bits for double-precision floating-point numbers). Assuming not too many bad primes are picked during a multi-modular Gröbner basis computation, using these types could speed the computations up before lifting the result over ℚ.

Likewise, for cryptographic applications, we shall need a dedicated implementation over 2 . In fa , we may have to introduce ways to compute over non-prime finite fields. This is why, I want to integrate fast univariate polynomial-matrix operations in order to deal with computations over finite extension of finite fields, defined by a single polynomial.

. . Gröbner bases for a degree order

While the classical framework of polynomial system solving relies on computing first a ≺ -Gröbner basis, see Figure . , in some applications, a monomial order ≺ distin from ≺ might be more convenient for the computation. This can be a 2-block ≺ -order, which is already implemented in , or a weighted degree order, see also [ , , ]. When the input system is quasi-homogeneous for a system of weights, one can take advantage of this quasi-homogeneity to improve the runtime and the complexity estimates of the F and F algorithms [ , ] by a fa or depending on the produ s of the weight. We want to benefit from this by implementing this kind of weighted degree monomial orders in in order to tackle systems coming from applications such as robotics where the weights are naturally coming from dimensional homogeneity.

Another approach to speed Gröbner bases computations up for (quasi-)homogeneous systems is to use Hilbert-driven Gröbner bases algorithms. These algorithms, such as Traverso's [ ], see Chapter 6. Research project 6.1. msolve and fundamental algorithms also [ , Chap. , Sec. ], assume that the Hilbert series of the ideal is already known and provide a criterion based on the degree of a critical pair to discard it without computing its redu ion to 0. Combined with the F algorithm, this allows us to handle Macaulay-like matrices with both fewer rows and fewer columns. Note, however, that the expe ed speed-ups may only be observed in positive chara eristic or, in the case of chara eristic 0, during the learning phase modulo the first prime.

. .

Change of order

For the moment, the implemented change of order step relies on the sparse-FGLM algorithm [ , ] in the shape position case. This assumption rises issues when the solutions of the system have multiplicities: even after introducing a generic linear form, the ideal might not be in shape position. Thus we may not compute the ≺ -Gröbner basis of the ideal. While we can compute the parametrizations of the solutions, through the radical of the ideal, this makes us lose the information on the multiplicity. To this end, we want to provide more general change of order algorithms in . A first step will be to implement the seminal FGLM algorithm [ ] before considering the algorithms I developed based on linear algebra and in particular, the adaptive algorithm of [ , ], see also Se ion . . .

In order to provide an e cient implementation of the guessing algorithms, I want to use the stru ure of the multi-Hankel matrix and in particular, its quasi-Hankel stru ure. Indeed, if the univariate polynomial in x n in the reduced ≺ -Gröbner basis has a large degree, i.e. of the same magnitude order as the degree of the ideal D, the multi-Hankel matrix will be quasi-Hankel with a small displacement rank. We can thus compute its ve or in its kernel, and thus C-relations, fast using [ , ]. Furthermore, depending on the geometry of the ≺ -and ≺ -staircases, computing the coe cients of this multi-Hankel matrix can just require Algorithm . with only one matrix, the one of the multiplication by x n , but extra column-ve ors. All-in-all, when D is exponential in n, the expe ed complexity will still be dominated by the computation of the ve ors of Algorithm . in O (tD 2 ) operations.

In addition to this, I want to implement a multi-modular approach for sequences with coe cients in ℚ. The idea is that the purpose of the adaptive algorithm is to find, at a low cost, the support of the reduced ≺ -Gröbner basis. Once this has been computed modulo a first prime, we can switch to the general S -FGLM with one big multi-Hankel matrix whose rows and columns are labeled by the monomials in this support. This shall allow us to compute exa ly the number of sequence terms required to recover the sought Gröbner basis modulo subsequent primes.

. . Saturation and colon ideals

With my coauthors, we want to push forward the e ciency of F SAT by investigating computational tricks to avoid "computing zero". For instance, we want to provide an early termination criterion to reduce the time spent in the last saturation step.

Likewise, we want to study a signature approach, as in Faugère's F algorithm [ , ], to minimize the redu ions to 0 of S-polynomials.

I also want to provide a multi-modular approach and a tracer for S -FGLM-for systems over ℚ in . The goal is to learn how to minimize Σ and Σ to the a ual set of required monomials to write the ≺ -Gröbner basis of the colon ideal but also to compute the exa number of necessary sequence terms in the Wiedemann part of the algorithm. This will make computations in the apply phase modulo all the primes but the first one optimal and thus the fastest implementation.

. . Exa solving on a GPU

Graphics Processing Units (GPUs) are, by design, well-suited to process large blocks of data in parallel and thus to perform linear algebra routines, more so than CPUs. Furthermore, they natively handle double-precision floating-point number arithmetic but only simulate long integer ones through short integer arithmetic, which comes with an overhead. For instance, N CUDA Chapter 6. Research project 6.2. Faster change of order and guessing C-relations and T cores, natively, only have 8-bit integer types, whereas they, natively, have 64-bit floatingpoint types . Furthermore, it has been shown that GPUs are very e cient for corre ly rounding fun ions evaluations [ ], reinforcing even more the advantage of using floating-point arithmetic in order to simulate a modular one. Thus, we aim to take advantage of their computational power to transpose the linear algebra code of our polynomial system solver to e ciently work with GPUs.

The main obje ive of this task is the design of fast Gröbner bases computation algorithms, based on high performance linear algebra algorithms, in particular exploiting GPUs, and their integration into in order to tackle applications challenges such as multivariate cryptography or robotics. This is Dimitri Lesno 's Ph.D. subje , who I have been supervising jointly with Stef Graillat and Théo Mary since O ober . We shall first revisit modular arithmetic at the core of exa algorithms relying on fast low-precision arithmetics such as fp16, bfloat16, fp8, . . . for floating-points numbers and int8, int4 for integers. This part will be done in parallel for CPUs, as in Se ion . . and for GPUs. Then, we will adapt the block-Wiedemann approach [ , ] of the S -FGLM algorithm. Since the matrix at hand is very particular, it can be seen as the concatenation of a permutation matrix and a dense matrix after reordering the columns, we will study how to balance more e ciently the CPU load and the GPU load to iterate the produ of this matrix with some ve ors or very thin matrices. We also target the design of a sparse matrix arithmetic which is both e cient for handling Macaulay matrices for the F algorithm and dedicated to a GPU or a CPU + GPU archite ure.

In order to tackle very large problems whose solving will unlock new advances in critical applications, we have to handle large matrices that cannot even be stored on the GPU. We plan to devise new algorithms that exploit a memory representation of these Macaulay matrices that suits our computations but also the limited RAM, a few tens of gigabytes, of a graphic card. Moreover, computing Gröbner bases at scale will require the use of multiple GPUs and CPUs in parallel. We will therefore work on making the algorithms scalable in a parallel context. Notably, we will minimize memory communication between the CPU and the GPU, by adapting cache-oblivious storing and algorithms [ ] to a larger scale such as the RAM of the graphic card.

.

Faster change of order and guessing C-relations . .

Guessing faster

While the polynomial point of view allows us to bring the guessing of C-relations for multiindexed sequences closer to the fast guessing for uni-indexed sequences, there is still a complexity gap. Indeed, the stated complexity in Theorem . becomes cubic, instead of quasi-linear, for uni-indexed sequences. This is due to the complexity analysis that relies, first, on a linear number of polynomial redu ions and, second, on naive polynomial redu ions. In fa , this cubic complexity stated in Theorem . comes from an overestimation on the number of needed polynomials to reduce a new one, while in pra ice, this is not observed, especially on sequences of prescribed ideal of C-relations but with random initial terms. Thus, as an on-going collaboration with Romain Lebreton , I want to improve this algorithm by handling univariate polynomials instead of multivariate ones, in order to take advantage or their fast arithmetic while reestimating the number of redu ions to target a complexity which is only quadratic in the number of input sequence terms or the size of the output Gröbner basis.

As a second goal, I want to guess P-relations using polynomial arithmetic instead of linear algebra [ ]. From the generating series of a sequence and its derivatives, or more precisely the mirror polynomials of a truncation of these series, the goal is to find algebraic combinations thereof which are small modulo the monomial ideal x D 1 1 , . . . ,x D n n , where D 1 , . . . ,D n depend on the sequence terms we allow ourselves to use. https://www.nvidia.com/en-us/data-center/tensor-cores/ Ph.D. student at Sorbonne Université Sorbonne Université CNRS Université de Montpellier Chapter 6. Research project 6.2. Faster change of order and guessing C-relations E ciency of guessing algorithms is based on two aspe s: the number of performed operations and the number of sequence terms that are needed. Indeed, in many applications, computing the sequence is the bottleneck. Thus, to make this approach the most e cient, we shall closely look at the number of di erent sequences terms that are needed to corre ly guess the relations. Furthermore, to optimize the number of operations, we shall rely on e cient algorithms for univariate polynomials and uni-indexed sequences. The main goal is to reach a complexity at most quadratic in the size of the output instead of only cubic.

These guessing algorithms may find fake relations, this happens in general when too few terms are used or when most of the terms are 0. This can be circumvent by stru ured guessing relations using mainly the nonzero sequence terms as in [ ]. We will pay attention to these bad sequences so that our new algorithm avoids these fake relations as much as possible.

. .

Guessing radical ideals

Radical ideals are important in the polynomial system solving applications as the solutions have all multiplicities 1. Therefore, numerical methods to approximate the real or complex solutions behave much better with this kind of ideals.

In collaboration with Alin Bostan , Manuel Kauers and Christoph Koutschan , I want to investigate an extension of [ ] to more general radical ideals. Indeed, in this paper, given a sequence u, the authors propose an algorithm for guessing the ≺ -Gröbner basis of I C (u) if it is in shape position. Yet, the output is meaningless if this radical is not in shape position. While BMS and S -FGLM allow us to guess I C (u), this may require many sequence terms, especially if the ideal has a large degree. Thus, we want to propose a trade-o between the number of queries to the sequence and the quality of the output by allowing to guess polynomials only in I C (u).

. . Guessing with multiplicities

In some situations where the system has roots with multiplicities, the sought ≺ -Gröbner basis cannot be in shape position, even after a generic linear change of variables. Such a system is called 2-thick in [ ] and it requires a second stru ured D ×D-matrix, of a similar kind, to be computed: the matrix of the multiplication by x n-1 , which has O ( D) nonzero coe cients. Furthermore, in most situations the stability property is still satisfied which means that the computation of this second matrix is cheap. However, it does not ensure (a ually it almost never can) that this second matrix is computed for free.

A first goal is to derive a sharp complexity estimate on the computation of this second matrix based on the ≺ -Gröbner basis, exploiting the stability property and the work of Moreno-Socías [ ], for the first matrix. For instance, whenever ≺ (I ) = x D n n ,x D n-1 n-1 ,x n-2 , . . . ,x 1 or ≺ (I ) = x D n n ,x n x n-1 ,x 2 n-1 ,x n-2 , . . . ,x 1 which seem to be simplest cases. As a by-produ , we will obtain complexity bounds on the computation of the sequence terms that appear in the multi-Hankel matrix built by S -FGLM [ , ] to recover the ≺ -Gröbner basis. Then, as a second goal, we will rely on the quasi-Hankel stru ure of this multi-Hankel matrix, and fast algorithms for quasi-Hankel matrices [ , ], to analyze the complexity on the computation of the sought ≺ -Gröbner basis. All in all, we will have a complete description and complexity estimate of Faugère and Mou's [ , ] S -FGLM algorithm for generic 2-thick systems.

. . Polynomial matrices with multiplicities

A first goal is to adapt the polynomial-matrix algorithm for the change of order, see [ ] and Se ion . . , to take into account stru ures. For instance, in [ ] and [ ], the authors tweak respe ively the FGLM and the S -FGLM algorithms for ideals that are globally invariant under the a ion of a finite abelian group. The main idea is to split the multiplication matrices into blockmatrices, improving the complexity by a fa or that depends on the size of the group.

Another obje ive is to be able to compute the ≺ -Gröbner basis of a zero-dimensional ideal INRIA Johannes Kepler Universität Linz Österreichische Akademie der Wissenschaften Chapter 6. Research project 6.3. Algorithms for quasi-commutative Gröbner bases I : from the ≺ -Gröbner basis of a, potentially positive-dimensional, ideal I using also the polynomial-matrix algorithm for change of order. We also want to investigate the computation of a parametrization of the radical ideal when I is not radical, in order to remove multiplicities. How can we take advantage of the polynomials to add to I to span √ I in this polynomial matrix in order to compute the ≺ -Gröbner basis of √ I . Then, a last obje ive, as a follow-up to Se ion . . , is to deal with the matrix of the multiplication by x n-1 in this polynomial matrix change of order algorithm. That is, we will develop this approach by considering a polynomial matrix P x n-1 instead of M x n-1 . However, this matrix should lie in [x n-1 ,x n ] and thus, e cient bivariate-polynomial matrices operations would have to be developed in order to make this algorithm faster, theoretically and pra ically, than the S -FGLM algorithm.

. .

Applications to guessing

I also want to target applications such as coding theory and optimization problems. In the former case, I want to extend the existing algorithms for guessing recurrences in order to decode extensions of cyclic codes such as those defined on an algebraic variety. As a first step, I will consider algorithms relying on linear algebra in order to understand the stru ure of the matrix at hand. In the latter case, I want to adapt our algorithms, in particular S -FGLM, to handle numerical sequences coming from the moment approach [ ]. The main di culty will be to return non-trivial relations and we shall take inspiration from approximate algorithms to overcome it, see [ ].

.

Algorithms for quasi-commutative Gröbner bases . .

Moment approach

As a starting collaboration with Lorenzo Baldi and Pierre Lairez , we want to use the theory of holonomic fun ions, or sequences satisfying P-relations, to provide a general and e cient method for computing the moments of measures that are useful for the applications. To do so, we want to exploit the fa that when computing the volume defined by several polynomial inequalities f 1 , . . . , f r ≥ 0 in the hypercube [0, 1] n , we are led to computing the integrals ∫ [0,1] n f k 1 1 • • • f k r r dx for many indices k 1 , . . . ,k r . Yet, the sequence of integrals satisfies P-relations. These relations are fundamental and we want to guess them by computing first a few moments and then exploit them to compute more moments in order to find larger relations.

. . E cient Gröbner bases computation

Another topic I want to investigate is the computation of Gröbner bases for a total degree monomial order of ideals in a quasi-commutative setting and its theoretical and pra ical e ciency in relation with Se ion . . . A longer term goal is then to implement Gröbner bases of quasi-commutative polynomials into in order to solve applications from combinatorics and physics. Following [ ] and the generalization of Buchberger's criteria, the goal will be to dive into the understanding of how Faugère's F algorithm [ ] behaves or can be extended from the commutative setting to this one.

To do so, I want to study the module of trivial syzygies in order to get information on the sizes of the matrices that are built in F . What kind of information the commutation rules provide on the syzygies?

Hilbert series and Hilbert polynomials are powerful tools that allow one to understand the complexity of computing Gröbner bases. In the commutative case, one can derive a bound on the degree of the polynomials in a reduced Gröbner basis for a total degree order, thanks to them, see [ , Se ion . , Corollary]. We will investigate how knowing in advance the Hilbert series can speed the Gröbner bases computations up, or how together with the Hilbert polynomials, they can give us a bound on the degrees of the polynomials in the reduced ≺ -Gröbner basis.

  Figure . : Classical Gröbner bases framework for 0-dimensional ideals

  INRIARheinland-Pfälzische Technische Universität Kaiserslautern-Landau former Ph.D. student at Sorbonne Université Sorbonne Université Chapter 3. Computing Gröbner bases 3.1.

  picked at random and 1 ≤ k ≤ n-1, Check whether g k = g

  Algorithm . : Berlekamp-Massey/ Extended Euclidean algorithm Let us consider the sequence w = (w i ) i ∈ℕ , -13 5 -5 5 -5 5 -5 • • • and assume N = 9.

  Figure . : Numbers of arithmetic operations ( D/ D)

  and sparse Gröbner bases are classical Gröbner bases. Furthermore, like classical Gröbner bases, sparse Gröbner bases allow one to solve the ideal membership problem in [ C] in an e e ive way. Example 5.4: The cone C

  fundamental obje . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solving polynomial systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Complexity of Gröbner bases change of order . . . . . . . . . . . . . Problem : Computation of Gröbner bases of saturated ideals . . . . . . . . . . . Problem : Polynomial arithmetic for guessing C-relations . . . . . . . . . . . . . Problem : Minimization of number of queries . . . . . . . . . . . . . . . . . . . Problem : Stru ured guessing . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Thanks Contents		Contents
	Introdu ion
	.	Gröbner bases: a . . Problem : Complexity of S	-FGLM for generic determinantal systems .
		. .	Problem :

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  g ,u

	Chapter 1. Introduction
	1.3. Sequences

s ∈S s u s . Since Eval g x i ,u = s ∈S s u s +i ,

Chapter 1. Introduction 1.5. Organization Chapter 2. msolve Chapter 2 msolve

	[ , ] is a an open source C library developed by Christian Eder , Mohab Safey El
	Din and myself, for solving multivariate polynomial systems, with a focus on those which have
	dimension at most 0. It relies on computer algebra methods yielding algebraic parametrizations of
	their solutions. This allows us to bypass the commonly encountered issues related to accuracy and
	exhaustively met by numerical methods because of the non-linearity of the input.
	This chapter is based on joint work with Christian Eder and Mohab Safey El Din and in
	particular [ ].
	Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau
	Sorbonne Université
	INRIA
	former Ph.D. student at Sorbonne Université
	former Post-doc at Sorbonne Université
	CryptoNext Security

Chapter 2. msolve 2.2. Experimental results

	Examples		maple magma	Examples		maple magma
	Katsura-	15	271	71	Henrion-	11	26	23
	Katsura-	25	276	223	Henrion-	47	171	-
	Katsura-	66 2, 279	-	Henrion-	3, 428	-	-
	Katsura-	229 1, 123	-	Noon-	209	419	-
	Katsura-	1, 037	-	-	Noon-	881 1, 227	-
	Eco-	27	210	213	CP(3, 5, 2)	17	525	-
	Eco-	82	428	354	CP(3, 6, 2)	55 7, 885	-
	Eco-	117 1, 027	-	CP(3, 7, 2)	312	-	-
	Eco-	318 8, 654	-	CP(4, 4, 3)	24	635	-
	Eco-	15, 748	-	-	CP(4, 5, 3)	2, 065	-	-
	Phuoc-	176	-	-

Table . :

 . Maximal memory usage given in MB

	Examples	System data degree radical F (prob.) F (learn) F (apply) FGLM # primes single modular computation	trace	overall independent	maple single modular F FGLM	Others overall maple magma
	Katsura-	256	yes	0.06	0.17	0.03	0.03	83	4.89	7.49	0.10	0.04	104	2, 522
	Katsura-	512	yes	0.24	0.81	0.09	0.11	188	43.7	70.5	0.36	0.15	1, 278 82, 540
	Katsura-	1, 024	yes	1.34	6.26	0.45	0.49	388	424	814	1.82	0.74	7, 812	-
	Katsura-	2, 048	yes	8.61	56.1	3.10	3.96	835	6, 262	11, 215	8.50	5.40 120, 804	-
	Katsura-	4, 096	yes	52.8	425	18.9	30.6	1, 772	89, 390	148, 372	60.9	35.7	-	-
	Katsura-	8, 192	yes	318	3, 336	128	210	3, 847 1, 308, 602	2, 007, 170	393	271	-	-
	Eco-	256	yes	0.10	0.28	0.05	0.02	161	12.5	21.2	0.14	0.03	26.3	6, 520
	Eco-	512	yes	0.39	1.21	0.17	0.07	327	90.3	161	0.56	0.12	312 214, 770
	Eco-	1, 024	yes	2.25	11, 619	1.07	0.34	530	877	1, 619	2.97	0.85	4, 287	-
	Eco-	2, 048	yes	11.7	67.3	6.61	2.12	1, 225	12, 137	19, 553	15.1	6.70	66, 115	-
	Eco-	4, 096	yes	67.1	516	34.8	25.9	2, 670	167, 798	254, 389	104.8	69.1	-	-
	Henrion-	100	yes	0.01	0.01	0.004	0.01	83	0.71	0.83	0.01	0.01	2.7	93
	Henrion-	720	yes	0.11	0.22	0.07	0.11	612	138	157	0.17	0.16	1, 470	-
	Henrion-	5, 040	yes	9.55	27.5	6.51 20.46	4, 243	117, 803	127, 456	12.8	27.1	-	-
	Noon-	2, 173	yes	1.66	5.3	0.93	1.95	1, 305	4, 039	5, 045	1.97	3.13	432	-
	Noon-	6, 545	yes	26.6	153	17.5	72.3	6, 462	598, 647	640, 177	32.4	76.2	5, 997	-
	Phuoc-	1, 102	no	4.01	4.65	3.42	2.59	753	4, 467	5, 056	4.60	5.91	-	-
	CP(3, 5, 2)	288	yes	0.03	0.04	0.01	0.03	326	18.1	19.2	0.06	0.05	249	-
	CP(3, 6, 2)	720	yes	0.22	0.59	0.12	0.16	1, 042	390	450	0.31	0.22	23, 440	-
	CP(3, 7, 2)	1, 728	yes	1.97	8.18	1.23	1.20	3, 037	9, 643	11, 511	2.78	2.54	-	-
	CP(3, 8, 2)	4, 032	yes	18.5	111.5	12.2	19.6	8, 211	269, 766	323, 838	24.6	25.3	-	-
	CP(4, 4, 3)	576	yes	0.04	0.86	0.03	0.07	339	40.9	41.8	0.08	0.11	916	-
	CP(4, 5, 3)	3, 456	yes	3.24	8.60	2.23	4.83	2, 747	21, 528	23, 559	4.33	9.21	-	-
	CP(3, 6, 6)	729	yes	0.18	0.42	0.11	0.15	779	255	294	0.30	0.23	-	-
	CP(4, 6, 6)	4, 096	yes	7.70	25.6	5.44 14.09	3, 476	71, 472	77, 941	10.2	16.71	-	-
	CP(3, 7, 7)	2, 187	yes	2.49	8.97	1.58	1.86	2, 795	12, 412	14, 375	3.27	3.75	-	-

Table . :

 . Benchmark timings given in seconds.

	Chapter 2. msolve
	2.2. Experimental results

tracer (F4 (apply)).

Table . :

 . , while the other two columns were added in [ ]. Let us recall that in this setting, D = d m (d -1) n-m n-1 m-1 , see [ , Th. . ]. Density of matrix of the multiplication by x n for generic critical point systems

	Parameters Degree		Matrix Density
	(d ,m,n)	D	A ual Theoretical Asymptotic
	(2, 4, 9)		. %	. %	. %
	(2, 4, 10)		. %	. %	. %
	(2, 4, 11)		. %	. %	. %
	(3, 3, 6)		. %	. %	. %
	(3, 3, 7)		. %	. %	. %
	(3, 3, 8)		. %	. %	. %
	(4, 2, 5)		. %	. %	. %
	(4, 2, 6)		. %	. %	. %
	(5, 2, 5)		. %	. %	. %
	(6, 2, 5)		. %	. %	. %

  is spanned by a set of homogeneous polynomials, Bayer's algorithm [ ] allows one to compute I : x n ∞ . If it is not, then one can still recover a Gröbner basis of I : x n

	∞
	using Algorithm . , still called Bayer's algorithm:

Input: A list of polynomials f 1 , . . . , f s spanning an ideal I ⊆ [x].

  The reduced ≺ -Gröbner basis G of a generic ideal, a polynomial ∈ [x], and a finite staircase Σ of size N containing supp NF x k n , G , ≺ for all k ∈ ℕ. Output: The reduced ≺ -Gröbner basis of I :

	Chapter 3. Computing Gröbner bases 3.2. Saturated and colon ideals Sys-SOS F SAT (learn ) (learn ) (apply) (prob.) positive-dimensional to 0-dimensional (learn) Steiner . d -n -p . . . d -n -p , , , , d -n -p , , , , , d -n -p , d -n -p , , , , , d -n -p . . . . d -n -p . . . . . d -n -p , , , d -n -p , , , , , d -n -p . . . . . d -n -p . . . . d -n -p , d -n -p , , , d -n -p . d -n -p , , , , , positive-dimensional to 1-dimensional d -n -p . . . . . d -n -p . . . . d -n -p . . d -n -p , , d -n -p , d -n -p , , , , d -n -p . . . . . d -n -p . . . . . . Chapter 3. Computing Gröbner bases (apply) . , , . , . . , . . . , . . , . 3.2. Saturated and colon ideals	Maple (prob.) . , , , . . , , . . . , . . , .	Singular , , --, -, --, , -, -. , , , , -

Input:

  Table . , we give an example where a 81 068 × 81 068-matrix is replaced by a 32 184 × 32 184-submatrix for instance.

Example 3.5:

  where, for a monomial , -(resp. + ) is its preceding resp. following) monomial for ≺. Let us notice that Eval s + k m - k ,u can also be a 0 if s + k m -

	Chapter 4. Guessing Gröbner bases
	4.2. Extensions to multi-indexed sequences
	k
	former Post-doc at Sorbonne Université
	INRIA
	CryptoNext Security
	Sorbonne Université

(

  -sparse Gröbner basis of I C (u).

	Chapter 5. Quasi-commutative Gröbner bases
	5.3. Structured sequences
	Sorbonne Université

≺

Table . :

 . Guessing fake and corre P-relationsIn Table., we can see that considering only terms in the cone allows us to almost only discover corre relations compared to the full orthant case, even when the generalized multi-Hankel matrices are almost square.

	Type		Cone			Full Orthant
		Matrix size Queries	Relations Fake Corre	Matrix size Queries	Relations Fake Corre
	g n,0,j	444 × 441	866	11		0 496 × 495	946	48	0
	g n,0,j	631 × 564	1 174	0		0 1 326 × 661	1 942	84	0
	g n,0,j	721 × 711	1 408	15		8 726 × 715	1 386	67	0
	g n,0,j	1 951 × 1 089	3 010	0	21 2 556 × 1 001	3 491 136	6
	w n,0,j,k 223 × 211	430	7		1 220 × 210	395	24	0
	w n,0,j,k 444 × 253	552	2		1 680 × 267	912	37	0
	w n,0,j,k 406 × 400	799	11		6 406 × 400	771	27	0
	w n,0,j,k 806 × 522	1 320	2		6 1 540 × 589	2 073	68	0

Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau Sorbonne Université

Post-doc at Sorbonne Université INRIA

More generally, thank you the whole Computer Algebra community, especially the members of the GT Calcul Formel. This works has been partly supported by joint ANR-FWF ANR--CE -ECARP and ANR--CE -EAGLES proje s, the ANR grants ANR--CE -S and ANR--CE -D R N proje s, European Union's Horizon research and innovation programme under the Marie Skłodowska-Curie grant agreement N. (POEMA), grant DIM-RFSI --C / of the Paris Île-de-France Region, grant FA ---of the EOARD-AFOSR and PGMO grant CAMiSAdo.

On a personal level, I would like to thank my friends, my family in law, Amélie,

: Timings in seconds, ≺ -Gröbner bases of saturated ideals.

The main ideal is twofold. First, the S -FGLM algorithm builds a sequence u from G , hence unless I is not Gorenstein and the initial terms of u are not random enough, I C (u) = I . Then, we create a new sequence v = Eval x i ,u i ∈ℕ n and prove that it satisfies I C (v ) = I C (u) :

= I : .

Finally, it remains to recover the relations satisfied by v . This is where the zero-dimensionality assumption appears, we know that only finitely many monomials m are linearly independent in [x]/(I :

), which is equivalent to saying that finitely many polynomials NF (m , G , ≺ ) are linearly independent in [x]/I . Thus, we can work in a finite-dimensional subspace W of [x]/I spanned by a set of monomials that allows us to determine H .

The shape position assumption on H is of upmost importance to mimic the S -FGLM algorithm by building only one matrix, related to the multiplication by x n . Since W need not be stable by the multiplication by x n , we consider the map multiplication by x n composed with the proje ion on W . Assuming W is large enough, this new map, and its associated matrix, allow us to determine H by tweaking Algorithm . as follows in Algorithm . . Theorem 1.11 (see also [15,Th. 4.12]): Let I be a positive-dimensional ideal of [x], let G be its reduced ≺ -Gröbner basis and S be the associated staircase. Let ∈ [x] \ I such that I : is zero-dimensional of degree D and in shape position.

Let Σ be a finite staircase of size N containing supp NF x i n , G , ≺ for all i ∈ ℕ, where NF f ,G , ≺ is the normal form of f w.r.t. G and ≺.

Let t be the number of monomials in Σ such that x n ∈ ≺ ( G ) and let u be the number of monomials in Σ such that x n ∈ ≺ (I ) \ ≺ ( G ). Then, for a generic choice of ve or r ∈ N , Algorithm . terminates and returns the reduced ≺ -Gröbner basis of I :

. To do so, it requires at most u + n normal form computations w.r.t. G and ≺ plus O ((t + u + n)N D ) operations in .

As a pra ical optimization, we show that any zero column of the matrix M can be removed, together with its associated row. Repeating this process can lead to considering a much smaller Chapter 6. Research project 6.

Algorithms for quasi-commutative Gröbner bases

In the particle physics and algebraic statistics application, computing representants of the quotient ( ) x / J , where J is a 0-dimensional ideal allows one to determine the twisted cohomology defined by a likelihood fun ion, see [ ]. In this paper, the authors need to compute the contiguity matrices of J , which a ually correspond to the matrices of multiplication by x 1 , . . . ,x n in ( ) x / J . Therefore, I want to study how to e ciently build these matrices from a ≺ -Gröbner basis of J . Furthermore, depending on the shape of the ≺ -staircase, some of these matrices are obtained from free, for instance the one for x n , like in the commutative case, see [ ]. As a longer term goal, I would like to study these conditions in this setting.

Appendix A Ideals of C-relations of small degrees

A.

Uni-indexed sequences

Theses sequences (i )a i i ∈ℕ generalize the class of geometric sequences with initial term 0 and common ratio a, which are the case d = 1, and the class of arithmetic sequences with initial term 0 and common di erence 1 , which are the case d = 2 and a = 1. For the sake of the completeness,

Such a sequence will be denoted a,d .

Using Theorem . , we can deduce the general case. Theorem A.1: Let be algebraically closed and g ∈ [x]. Assume g fa ors as

As we can see, the roots of the polynomial, and their multiplicities, completely determine the form of the sequence terms.

A. Bi-indexed sequences

From the uni-indexed case and small computations, we can see that S

is the ve or space of sequences a 1 ,e 1 ⊗ a 2 ,e 2 = 1 (i 1 ) 2 (i 2 )a i 1 1 a i 2 2 (i 1 ,i 2 ) ∈ℕ 2 where e 1 ≤ d 1 , e 2 ≤ d 2 and deg 1 = e 1 , deg 2 = e 2 . While such a polynomial ideal has (a 1 ,a 2 ) as its unique root with multiplicity d 1 d 2 , this does not encompass all the cases. Before diving into multiplicities, we shall deal with the case of distin single roots.

To simplify the presentation, we mostly consider the case a 1 ≠ 0 and a 2 ≠ 0, but the results on the ideals still hold whenever a 1 , a 2 or both are 0.

A. . Single roots

Let us consider two distin points (a 1 ,a 2 ), (b 1 ,b 2 ) ∈ 2 , then we can look at the ideal of polynomials vanishing on these points. This is the ideal

the first two polynomials form a Gröbner basis of I for x 2 ≺ x 1 , otherwise the last two do. Hence, S C (I ) is a two-dimensional ve or space and u ∈ S C (I ) is uniquely determined by u 0,0 and, u 0,1 in the former case or u 1,0 in the latter one.

More generally, the sequence obtained as a linear combination, with nonzero coe cients, of the sequences

) ∈ℕ 2 has its ideal of C-relations which is exa ly the radical ideal of all polynomials vanishing on (a 1,1 ,a 1,2 ), . . . , (a k ,1 ,a k ,2 ).

It remains to deal with multiplicities. As we shall see, even the multiplicity-2 case is broader than for uni-indexed sequences. A.2. Bi-indexed sequences A. .

Root of multiplicity

The sequences whose ideal of C-relations only admits (a 1 ,a 2 ) as a root, and with multiplicity 2, are all of the type u = ( 0,0 + 1,0 i 1 + 0,1 i 2 )a i 1 1 a i 2 2 (i 1 ,i 2 ) ∈ℕ 2 with 1,0 and 0,1 not both 0. The ideal of C-relations of such a sequence u is

where b equals 1 if b = 0 and b otherwise. Notice that if 1,0 ≠ 0, the first two polynomials span the ideal, otherwise 0,1 ≠ 0 and the last two polynomials span it.

A. . Root of multiplicity

The sequences whose ideal of C-relations only admits (a 1 ,a 2 ) as a root, and with multiplicity 3, are all of the type u = ( 0,0

1,1 and 2,0 and 0,2 not both 0. The ideal of C-relations of such a sequence u is

where the i ,j 's are polynomials in the i ,j 's with 1 ≤ i + j ≤ 2. Furthermore, the i ,j 's are such that either the first two or the last two polynomials span the ideal.

Geometrically, there exists another ideal whose only root is (a 1 ,a 2 ), and with multiplicity 3. This is

Proof. Let u be such that K (a 1 ,a 2 ),3 ⊆ I C (u). Since K (a 1 ,a 2 ),3 contains (x 1a 1 ) 2 , (x 2a 2 ) 2 , u = a 1 ,e 1 ⊗ a 2 ,e 2 with e 1 ≤ 2 and e 2 ≤ 2. Assuming a 1 ,a 2 ≠ 0, then there exist , , , ∈ such that

. If either a 1 = 0 or a 2 = 0, then this proof can be adapted using the appropriate sequence a 1 ,e 1 ⊗ a 2 ,e 2 . This concludes the proof that no sequence has K (a 1 ,a 2 ),3 as its ideal of C-relations.

Abstra

This habilitation thesis deals with polynomial system solving through Gröbner bases computations. It focuses on the link between multivariate polynomials and linear recurrence relations satisfied by a multi-indexed sequence for computing Gröbner bases.

Our contributions mainly lie on the theoretical and pra ical aspe s on these Gröbner bases computations. First, we present msolve, a new open source C library, for solving polynomial systems using Gröbner bases. Second, we describe new algorithms and complexity estimates for computing Gröbner bases either for a total degree order or the lexicographic one. Then, we present linear algebras-based and polynomial-division-based algorithms for guessing linear recurrences with constant or polynomial coe cients, in generic and stru ured situations.

Finally, we detail our research proje for the forthcoming years on these aspe s.

Résumé

Cette thèse d'habilitation traite de la résolution de systèmes polynomiaux via le calcul de bases de Gröbner. Elle se concentre sur le lien entre les polynômes multivariés et les relations de récurrence linéaires satisfaites par une suite multi-indexée pour calculer des bases de Gröbner. Nos contributions portent principalement sur les aspe s théoriques et pratiques de ces calculs de bases de Gröbner. Tout d'abord, nous présentons msolve, une nouvelle bibliothèque C open source, pour la résolution de systèmes polynomiaux en utilisant les bases de Gröbner. Ensuite, nous décrivons de nouveaux algorithmes et donnons des estimations de complexité pour le calcul des bases de Gröbner soit pour un ordre de degré total, soit pour l'ordre lexicographique. Ensuite, nous présentons des algorithmes basés sur l'algèbre linéaire et sur la division de polynômes pour deviner les récurrences linéaires à coe cients constants ou polynomiaux, dans des situations génériques et stru urées.

Enfin, nous détaillons notre projet de recherche pour les années à venir sur ces aspe s.