Tristan Vaccon
email: tristan.vaccon@unilim.fr

Kazuhiro Yokoyama
email: kazuhiro@rikkyo.ac.jp

A Tropical F5 algorithm

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. While generalizing the classical theory of Gröbner bases, it is not clear how modern algorithms for computing Gröbner bases can be adapted to the tropical case. Among them, one of the most efficient is the celebrated F5 Algorithm of Faugère.

In this article, we prove that, for homogeneous ideals, it can be adapted to the tropical case. We prove termination and correctness.

Because of the use of the valuation, the theory of tropical Gröbner bases is promising for stable computations over polynomial rings over a p-adic field. We provide numerical examples to illustrate timecomplexity and p-adic stability of this tropical F5 algorithm.

Introduction

The theory of tropical geometry is only a few decades old. It has nevertheless already proved to be of significant value, with applications in algebraic geometry, combinatorics, computer science, and non-archimedean geometry (see [START_REF] Maclagan | Introduction to tropical geometry[END_REF], [START_REF] Einsiedler | Douglas Nonarchimedean amoebas and tropical varieties[END_REF]) and even attempts at proving the Riemann hypothesis (see [C15]).

Effective computation over tropical varieties make decisive usage of Gröbner bases, but before Chan and Maclagan's definition of tropical Gröbner bases taking into account the valuation in [START_REF] Chan | Gröbner bases over fields with valuations and tropical curves by coordinate projections[END_REF][START_REF] Chan | Gröbner bases over fields with valuations[END_REF], computations were only available over fields with trivial valuation where standard Gröbner bases techniques applied.

In this document, we show that following this definition, an F5 algorithms can be performed to compute tropical Gröbner bases.

Our motivations are twofold. Our first objective is to provide with the F5 algorithm a fast algorithm for tropical geometry purposes. Indeed, for classical Gröbner bases, the F5 algorithm, along with the F4, is recognized as among the fastest available nowadays.

Secondly, while our algorithms are valid and implemented for computations over Q, we aim at computation over fields with valuation that might not be effective, such as Q p or Q((t)). Indeed, in [V15], the first author has studied the computation of tropical Gröbner bases over such fields through a Matrix-F5 algorithm. For some special term orders, the numerical stability is then remarkable. Hence, our second objective in designing a tropical F5 algorithm is to pave the way for an algorithm that could at the same time be comparable to the fast methods for classical Gröbner bases, have a termination criterion and still benefit from the stability that can be obtained for tropical Gröbner bases.

Related works on tropical Gröbner bases

We refer to the book of Maclagan and Sturmfels [MS15] for an introduction to computational tropical algebraic geometry.

The computation of tropical varieties over Q with trivial valuation is available in the Gfan package by Anders Jensen (see [Gfan]), by using standard Gröbner bases computations. Yet, for computation of tropical varieties over general fields, with non-trivial valuation, such techniques are not readily available. Then Chan and Maclagan have developed in [START_REF] Chan | Gröbner bases over fields with valuations[END_REF] a way to extend the theory of Gröbner bases to take into account the valuation and allow tropical computations. Their theory of tropical Gröbner bases is effective and allows, with a suitable division algorithm, a Buchberger algorithm. Following their work, a Matrix-F5 algorithm has been proposed in [V15].

Main idea and results

Let G ′ be a finite subset of homogeneous polynomials of A := k[X 1 , . . . , X n ] for k a field with valuation. 1 We assume that G ′ is a tropical Gröbner basis of the ideal I ′ it spans for a given tropical term order ≤ . Let f 1 ∈ A be homogeneous. We are interested in computing a tropical Gröbner basis of I = I ′ + f 1 . In this homogeneous context, following Lazard [L83], we can perform computations in I d = I ∩k[X 1 , . . . , X n ] d . I d can be written as a vector space as

I d = x α f 1 , |x α | + |f 1 | = d + I ′
d , with | | denoting total degree. The second summand is already well-known as G ′ is a tropical Gröbner basis. Thanks to this way of writing the first summand, we can then filtrate the vector space I d by ordering the possible x α . The main idea of the F5 algorithm of Faugère [F02] is to use knowledge of this filtration to prevent unnecessary computations. Our main result is then:

Theorem 1.1. The Tropical F5 algorithm (Algorithm 1 on page 18) computes a tropical Gröbner basis of I. If f 1 is not a zero-divisor in A/I ′ then no polynomial reduces to zero during the computation.

Notations

Let k be a field with valuation val. The polynomial ring k[X 1 , . . . , X n ] will be denoted by A. Let T be the set of monomials of A. For u = (u 1 , . . . , u n ) ∈ Z n ≥0 , we write x u for X u 1 1 . . . X un n and |x u | for its degree. For d ∈ N, A d is the vector space of polynomials in A of degree d. Given a mapping f : U → V, Im(f ) denote the image of f. For a matrix M, Rows(M) is the list of its rows, and Im(M) denotes the left-image of M (n.b. Im(M) = span(Rows(M)). For w ∈ Im(val) n ⊂ R n and ≤ 1 a monomial order on A, we define ≤ a tropical term order as in the following definition: Definition 1.2. Given a, b ∈ k * and x α and x β two monomials in A, we write

ax α ≥ bx β if val(a) + w • α < val(b) + w • β, or val(a) + w • α = val(b) + w • β and x α ≥ 1 x β .
This is a total term order on A. We can then define accordingly for f ∈ A its highest term, denoted by LT (f ), and the corresponding monomial LM(f ). These defintions extend naturally to LM(I) and LT (I) for I an ideal of A. A tropical Gröbner bases of I (see [START_REF] Chan | Gröbner bases over fields with valuations[END_REF][START_REF] Vaccon | Matrix-F5 Algorithms and Tropical Gröbner Bases Computation[END_REF]) is then a subset of I such that its leading monomials generate as a monoid LM(I). We denote by NS(I) the set of monomials T \ LM(I). We will write occasionally tropical GB.

Let G ′ be a finite subset of homogeneous polynomials of A that is a tropical Gröbner basis of the ideal I ′ it spans. Let f 1 ∈ A be homogeneous. We are interested in computing a tropical Gröbner basis of I = I ′ + f 1 .

Signature

Contrary to the Buchberger or the F4 algorithm, the F5 algorithm relies on tags attached to polynomial so as to avoid unnecessary computation thanks to this extra information. Those tags are called signature, and they are decisive for the F5 criterion, which is one of the main ingredients of the F5 algorithm.

In this section, we provide a definition for the notion of signature we need for the F5 algorithm and deduce some of its first properties.

Definition 2.1 (Syzygies). Let v be the following k-linear map defined by the multiplication by f 1 :

v : A → A/I ′ 1 → f 1 .
Let Syz f 1 = Ker(v), LM(Syz f 1 ) be the leading monomials of the polynomials in Syz f 1 and NS(Syz f 1 ) = T \ LM(Syz f 1 ) the normal set of monomials for the module of syzygies.

Proposition 2.2. v(NS(Syz f 1 )) = Im(v).

Proof. We can prove this claim degree by degree. The method is quite similar to what was developped in Section 3.2 of [V15]. Let Remark 2.3. Clearly, LM(I ′ ) ⊂ LM(Syz f 1 ), and this is an equality if f 1 is not a zero-divisor in A/I ′ .

d ∈ N. Let α 1 , . . . , α u be LM(Syz f 1 ) ∩ A d . Let f α 1 , . . . , f αu ∈ A d be such that for all i, f α i ∈ Ker(v) and LM(f α i ) = α i . Then, written in the basis U d = (LM(Syz f 1 ) ∩ A d ) ∪ (NS(Syz f 1 ) ∩ A d ) , f α 1 , . . . ,
We can now proceed to define the notion of signature. It relies on a special order on the monomials of A, which is not a monomial order: Definition 2.4. Let x α and x β be monomials in T. We write that x α ≤ sign x β if:

1. if |x α | < |x β |. 2. if |x α | = |x β |, x α ∈ NS(Syz f 1 ) and x β / ∈ NS(Syz f 1 ). 3. if |x α | = |x β |, x α , x β ∈ NS(Syz f 1 ) and x α ≤ x β 4. if |x α | = |x β |, x α , x β / ∈ NS(Syz f 1 ) and x α ≤ x β .
Proposition 2.5. ≤ sign defines a total order on T. It is degree-refining. At a given degree, any x α in LM(I ′ ) or LM(Syz f 1 ) is bigger than any x β / ∈ LM(Syz f 1 ).

We can define naturally LM sign (g) for any g ∈ A. We should remark that in the general case, LM sign (g) = LM(g).

Definition 2.6 (Signature). For p ∈ I, using the convention that LM sign (0) = 0, we define the signature of p, denoted by S(p), to be

S(p) = min ≤ sign {LM sign (g 1 ) for g 1 ∈ A s.t. (g 1 f 1 -p) ∈ I ′ }.
Proposition 2.7. The signature is well-defined.

Remark 2.8. Clearly, p ∈ I ′ if and only if S(p) = 0. Similarly, if f 1 / ∈ I ′ then S(f 1 ) = 1.

Remark 2.9. This definition is an extension to the tropical case of that of [F15]. For trivial valuation, it coincides (after projection on last component) with that of [START_REF] Arri | The F5 criterion revised[END_REF][START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF] for elements in I \ I ′ . We have modified it to ensure that the signature takes value in (T \ LM(I ′ )) ∪ {0} , see Prop. 2.11 below.

With the fact that we can decompose an equality by degree, we have the following lemma: Proof. This is a direct consequence of Proposition 2.2. This proposition can be a little refined.

Lemma 2.12.

Let t ∈ T, f ∈ I \ I ′ then S(tf ) = tS(f ) ⇔ tS(f ) ∈ NS(Syz f 1 ) S(tf ) < sign tS(f ) ⇔ tS(f ) ∈ LM(Syz f 1 ). Proof. Let S(f ) = σ. By definition of S, we have f = ασf 1 + gf 1 + h with α ∈ k * = k \ {0}, LM(g) < sign ασ and h ∈ I ′ . If tσ ∈ NS(Syz f 1 )
, then we get directly that the leading term of the normal form (modulo G ′ ) of αtσf 1 + tgf 1 + th is tσ and in this case S(tf ) = tσ = tS(f ), otherwise we can provide a syzygy. In the other case, the normal form has a strictly smaller leading term, and we get that S(tf ) < sign tS(f ).

We then have the following property, and two last lemmas to understand the behaviour of signature.

Proposition 2.13. The following mapping Φ is a bijection:

Φ : LM(I) \ LM(I ′ ) → NS(Syz f 1 )
x α → min ≤ sign {S(x α + g), with g s.t.

x α + g ∈ I and LT (g) < x α },

Proof. It can be proved directly by computing a tropical row-echelon form of some Macaulay matrix (see Definition 4.4).

Lemma 2.14.

Let f 1 , f 2 ∈ I \I ′ be such that LM(f 1 ) > LM(f 2 ) and S(f 1 ) = S(f 2 ) = σ. Then there exist α, β ∈ k * such that S(αf 1 + βf 2 ) < sign σ. Lemma 2.15. Let f 1 , f 2 ∈ I be such that S(f 1 ) > S(f 2 ). Then for any α ∈ k * , β ∈ k, S(αf 1 + βf 2 ) = S(f 1 ).

Tropical S-Gröbner bases

The notion of signature allows the definition of a natural filtration of the vector space I by degree and signature:

Definition 3.1 (Filtration by signature). For d ∈ Z ≥0 and x α ∈ T ∩ I d , we define the vector space

I d,≤x α := {f ∈ I d , S(f ) ≤ x α } .
Then we define the filtration by signature,

I = (I d,≤x α ) d∈Z ≥0 , x α ∈T ∩I d .
Our goal in this section and the following is to define tropical Gröbner bases that are compatible with this filtration by signature. It relies on the notion of S-reduction and irreducibility. Definition 3.2 (S-reduction). Let f, g ∈ I, h ∈ I and σ ∈ T. We say that f S-reduces to g with respect to σ and with h,

f → h S,σ g
if there are t ∈ T and α ∈ k * such that:

• LT (g) < LT (f ), LM(g) = LM(f ) and fαth = g and

• S(th) < sign σ.
If σ is not specified, then we mean σ = S(f ).

It is then natural to define what is an S-irreducible polynomial.

Definition 3.3 (S-irreducible polynomial). We say that f ∈ I is S-irreducible with respect to σ ∈ T, or up to σ, if there is no h ∈ I which S-reduces it with respect to σ. If σ is not specified, then we mean σ = S(f ). If there is no ambiguity, we might omit the S -.

Remark 3.4. This definition clearly depends on I, I ′ , and the given monomial ordering.

In order to better understand what are S-irreducible polynomials, we have the following: Theorem 3.5. Let f ∈ I and x α ∈ T such that:

• f is S-irreducible with respect to x α , • f = (cx α + u)f 1 + h with c ∈ k, u ∈ A with LT (u) < cx α , h ∈ I ′ . Then f = 0 if and only if x α ∈ LM(Syz f 1 ). Moreover, if f = 0, then x α = S(f ) = Φ(LM(f )). Proof. Suppose f = 0, then 0 = f = (cx α + u)f 1 + h, hence x α ∈ LM(Syz f 1 ).
We prove the converse result by contradiction. We assume that f = 0 and x α ∈ LM(Syz f 1 ). Let t = LM(f ) and x β = Φ(t) ∈ NS(Syz f 1 ). We have x β < sign x α . There exists g ∈ I such that LM(g) = t and S(g) = x β . Since x β < x α , g is an S-reductor for f with respect to x α . This contradicts the fact that f is irreducible. Hence f = 0. For the additional fact when f = 0, ssume x α ∈ NS(Syz f 1 ). Then necessarily, x α = S(f ). Suppose now that x α = Φ(LM(f )). Then S(f ) > Φ(LM(f )). Therefore there exists a polynomial g ∈ I such that t = LM(g) = LM(f ) and Φ(t) = S(g) = Φ(LM(f )) < S(f ). It follows that g is an S-reductor of f, which leads to f being not S-irreducible.

Corollary 3.6. If g ∈ I and x α ∈ T are such that x α g = 0 is S-irreducible up to x α S(g) then S(x α g) = x α S(g).

The previous results show that the right notion of S-irreducibility for f a polynomial is up to S(f ). Nevertheless, the previous corollary can not be used for easy computation of the signatures of irreducible polynomials as we can see on the following example:

Example 3.7. We assume that z 4 ∈ G ′ and z 3 , x 4 and x 2 y 2 ∈ NS(I ′ ). We assume that we have h 1 = xy 5 + y 5 z, h 2 = x 3 y 2 zy 6 and h 3 = x 4 y 2 + y 6 such that S(h 1 ) = x 2 y, S(h 2 ) = x 3 and S(h 3 ) = z 3 and all of them are S-irreducible. We assume that x 4 > sign x 2 y 2 and Φ(x 4 y 2 z) = x 4 . Then,

zh 3 = yh 1 + xh 2 = x 4 y 2 z + y 6 z. Its signature is xS(h 2 ) = x 4
, and not z 4 . With our assumptions, the polynomial zh 3 is irreducible up to S(zh 3 ) = x 4 , whereas up to z 4 , it is not.

In other words, it is possible that the polynomial x α f is irreducible, up to S(x α f ), even though S(x α f ) < x α S(f ).

We now have enough definitions to write down the notion of S-Gröbner bases, which will be a computational key point for the F5 algorithm. Definition 3.8 (Tropical S-Gröbner basis). We say that G ⊂ I is a tropical S-Gröbner basis (or tropical S-GB, or just S-GB for short when there is no amibuity) of I with respect to G ′ , I ′ , and a given tropical term order if G ′ = {g ∈ G s.t. S(g) = 0} and for each S-irreducible polynomial f ∈ I \ I ′ , there exists g ∈ G and t ∈ T such that LM(tg) = LM(f ) and tS(g) = S(f ).

Remark 3.9. Unlike in Arri and Perry's paper [AP], we ask for tS(g) = S(f ) instead of the weaker condition S(tg) = S(f ). The main reason is to avoid misshapes like that of Example 3.7. We can nevertheless remark that thanks to Lemma 2.12, then tS(g) = S(f ) implies that S(tg) = tS(g) = S(f ).

We prove in this Section that tropical S-Gröbner bases are tropical Gröbner bases, allowing one of the main ideas of the F5 algorithm: compute tropical S-Gröbner basis instead of tropical Gröbner basis.

To that intent, we use the following two propositions.

Proposition 3.10. A polynomial f is S-irreducible iff S(f ) = Φ(LM(f )). Proof. By definition, if S(f ) = Φ(LM(f )), then clearly f is S-irreducible.
Regarding to the converse, if S(f ) > sign Φ(LM(f )), then there exists g ∈ I such that LM(g) = LM(f ) and S(g) = Φ(LM(f )), and then g S-reduces f .

Proposition 3.11. If G is a tropical S-Gröbner basis, then for any nonzero f ∈ I \ I ′ , there exists g ∈ G and t ∈ T such that:

• LM(tg) = LM(f ) • S(tg) = tS(g) = S(f ) if f is irreducible, and S(tg) = tS(g) < sign S(f ) otherwise.
Hence, there is an S-reductor for f in G if f is not irreducible.

Proof. If f is irreducible, this is a result of Definition 3.8. Let us assume that f is not S-irreducible. We take h S-irreducible such that LM(h) = LM(f ). Thanks to Proposition 3.10, it exists, and S(h) < sign S(f ). So h is an S-reductor of f. There are then t ∈ T and g ∈ G such that tLM(g) = LM(h) = LM(f ) and tS(g) = S(tg) = S(h). With Proposition 3.10, tg is irreducible. The result is proved.

We can now prove the desired connection between tropical S-Gröbner bases and tropical Gröbner bases.

Proposition 3.12. If G is a tropical S-Gröbner basis, then G is a tropical Gröbner basis of I, for < .

Proof. Let t ∈ LM(I) \ LM(I ′ ). With Proposition 2.13, there exist σ ∈ NS(Syz f 1 ) such that Φ -1 (σ) = t and f ∈ I \ I ′ such that LM(f ) = t and S(f ) = σ. By Proposition 3.11, there exists g ∈ G, u ∈ T such that LM(ug) = LM(f ) = t. Hence, the span of {LM(g), g ∈ G} contains LM(I)\ LM(I ′ ), and G ⊃ G ′ . Therefore G is a tropical Gröbner basis of I.

And we can also prove some finiteness result on tropical S-Gröbner bases, which can be usefully applied to the problem of the termination of the F5 algorithm.

Proposition 3.13. Every tropical S-Gröbner basis contains a finite tropical S-Gröbner basis.

Proof. Let G = {g i } i∈L be a tropical S-Gröbner basis. Let

V : G → T ⊕ T g i → (LM(g i ), S(g i ))
be a mapping. By Dickson's lemma, there exists some finite set J ⊂ L such that the monoid generated by the image of V is generated by

H 0 = {g i } i∈J .
We claim that H = H 0 ∪ G ′ is a finite tropical S-Gröbner basis. We have taken the union with G ′ to avoid any issue with G ′ being non-minimal. Let f ∈ I \ I ′ be an S-irreducible polynomial. Since G is a tropical S-Gröbner basis, there exists g i ∈ G and t ∈ T such that tS(g i ) = S(tg i ) = S(f ) and tLM(g i ) = LM(tg i ) = LM(f ). If i ∈ J, we are fine. Otherwise, there exists some j ∈ J and u, v ∈ T such that LM(g i ) = uLM(g j ) and S(g j ) = vS(g j ).

Three cases are possible. If u = v, then t ′ = ut ∈ T satisfies t ′ LM(g j ) = LM(f ) and t ′ S(g j ) = S(f ) and we are fine. If u < sign v then t ′ = ut ∈ T satisfies t ′ LM(g j ) = LM(f ) and t ′ S(g j ) < S(f ), contradicting the hypothesis that f is S-irreducible. If u > sign v, then for t ′ = vt ∈ T, we can take some α ∈ k such that p = fαt ′ g j satisfies LM(p) = LM(f ) but S(p) < S(f ), contradicting the irreducibility of f. As a consequence, we have proved that H is a tropical S-Gröbner basis.

The elements of H 0 we have used are of special importance, hence we give them a special name.

Definition 3.14. We say that a non-zero polynomial f ∈ I \I ′ , S-irreducible (with respect to S(f )), is primitive S-irreducible if there are no polynomials f ′ ∈ I \ I ′ and terms t ∈ T \ {1} such that f ′ is S-irreducible, LM(tf ′ ) = LM(f ) and S(tf ′ ) = S(f ).

The proof of Proposition 3.13 implies that we can obtain a finite tropical S-Gröbner basis by keeping a subset of primitive S-irreducible polynomials with different leading terms. Also, it proves there exists a finite tropical S-Gröbner basis with only primitive S-irreducible polynomials (in its I \ I ′ part).

Linear algebra and tropical S-Gröbner bases

When the initial polynomials from which we would like to compute a Gröbner basis are homogeneous, the connection between linear algebra and Gröbner bases is well known. . . , f s ) to be the matrix whose rows are the polynomials x α i,j f i written in the basis B n,d of A d . We note that Im(Mac L83]). For an homogeneous ideal I = f 1 , . . . , f s , (f 1 , . . . , f s ) is a Gröbner basis of I for a monomial order ≤ 0 if and only if: for all d ∈ N, written in a decreasingly ordered B n,d (according to ≤ 0 ), Mac d (f 1 , . . . , f s ) contains an echelon basis of Im(Mac d (f 1 , . . . , f s )).

d (f 1 , . . . , f s )) = f 1 , . . . , f s ∩ A d . Theorem 4.2 ([
By echelon basis, we mean the following Definition 4.3. Let g 1 , . . . , g r be homogeneous polynomials of degree d. Let M be the matrix whose i-th row is the row vector corresponding to g i written in B n,d . Then we say that (g 1 , . . . , g r ) is an echelon basis of Im(M) if there is a permutation matrix P such that P M is under row-echelon form.

In other words, G = (g 1 , . . . , g s ) is a Gröbner basis of I if and only if for all d, an echelon (linear) basis of

I d is contained in the set {x α g i , i ∈ 1, s , x α ∈ T, |x α g i | = d}.
We have an analogous property for tropical Gröbner bases and tropical S-GB. It follows from the study in [V15] of a tropical Matrix-F5 algorithm. We first need to adapt to the tropical setting the definitions of row-echelon form and echelon basis.

Definition 4.4 (Tropical row-echelon form). Let M be a l × m matrix which is a Macaulay matrix, written in the basis B n,d of the monomials of A of degree d. We say that (P, Q) ∈ GL n (k) × GL m (k), Q being a permutation matrix, realize a tropical row-echelon form of M if:

1. P MQ is upper-triangular and under row-echelon form.

2. The first non-zero coefficient of a row corresponds to the leading term of the polynomial corresponding to this row.

We can then define a tropical echelon basis:

Definition 4.5 (Tropical echelon basis). Let g 1 , . . . , g r be homogeneous polynomials of degree d. Let M be the matrix whose i-th row is the row vector corresponding to g i written in B n,d . Then we say that g 1 , . . . , g r is a tropical echelon basis of a vector space V ⊂ A d if there are two permutation matrices P, Q such that P MQ realizes a tropical row-echelon form of M and span(Rows(M)) = V.

This can be adapted to the natural filtration of the vector space I by (I d,x α ) d,x α we have defined in 3.1.

Theorem 4.6. Suppose that G is a set of S-irreducible homogeneous polynomials of the homogeneous ideal

I such that {g ∈ G, S(g) = 0} = G ′ . Then G is a tropical S-Gröbner basis of I if and only if for all x α ∈ T, taking d = |x α | + |f 1 |, the set {x β g, irreducible s.t. g ∈ G, x β ∈ T, |x β g| = d, x β S(g) = S(x β g) ≤ x α } contains a tropical echelon basis of I d,≤x α .
Proof. Using Proposition 3.10, it is clear that if G satisfy the above-written condition, then it satisfies Definition 3.8 of tropical S-GB. The converse is also easy using Proposition 3.11 on an echelon basis of I d,≤x α and remarking that to get an echelon basis, it is enough to reach all the leading monomials of I d,≤x α .

An easy consequence of the previous theorem is the following result of existence:

Proposition 4.7. Given G ′ and f 1 , consisting of homogeneous polynomials, there exists a tropical S-GB for I = G ′ , f 1 .

Proof. It is enough to compute a tropical echelon basis for all the I d,≤x α , by tropical row-echelon form computation (see [V15]), and take the set of all these polynomials.

Even with Proposition 3.13, the idea of the proof of Proposition 4.7 is not enough to obtain an efficient algorithm. This is why we introduce the F5 criterion and design an F5 algorithm.

Fcriterion

In this section, we explain a criterion, the F5 criterion, which yields an efficient algorithm to compute tropical Gröbner bases.

We need a slightly different notion of S-pairs, called here normal pairs. Definition 5.1 (Normal pair). Given g 1 , g 2 ∈ I, not both in I ′ , let Spol(g 1 , g 2 ) = u 1 g 1u 2 g 2 be the S-polynomial of g 1 and g 2 , where u i = lcm(LM (g 1 ),LM (g 2 ))

LT (g i )

. We say that (g 1 , g 2 ) is a normal pair if:

1. the g i 's are primitive S-irreducible polynomials.

S(u

i g i ) = LM(u i )S(g i ) for i = 1, 2. 3. S(u 1 g 1 ) = S(u 2 g 2 ).
Remark 5.2. With this definition, if (g 1 , g 2 ) is a normal pair, using Lemma 2.15, S(Spol(g 1 , g 2 )) = max(S(u 1 g 1 ), S(u 2 g 2 )) holds. Moreover, if S(u 1 g 1 ) > S(u 2 g 2 ) then u 1 = 1 as if otherwise, g 2 would be an S-reductor of g 1 . Therefore S(Spol(g 1 , g 2 )) > max(S(g 1 ), S(g 2 )).

Theorem 5.3 (F5 criterion). Suppose that G is a set of S-irreducible homogeneous polynomials of I such that:

1. {g ∈ G, S(g) = 0} = G ′ . 2. if f 1 / ∈ I ′ , there exists g ∈ G such that S(g) = 1.
3. for any g 1 , g 2 ∈ G such that (g 1 , g 2 ) is a normal pair, there exists g ∈ G and t ∈ T such that tg is S-irreducible and tS(g

) = S(tg) = S(Spol(g 1 , g 2 )).
Then G is a S-Gröbner basis of I.

Remark 5.4. The converse result is clearly true.

Remark 5.5. The g given in the second condition is primitive S-irreducible, by definition and using Lemma 2.10.

Theorem 5.3 is an analogue of the Buchberger criterion for tropical S-Gröbner bases. To prove it, we adapt the classical proof of the Buchberger criterion. We need three lemmas, the first two being very classical.

Lemma 5.6. Let P 1 , . . . , P r ∈ A, c 1 , . . . , c r ∈ k and β a term in A, σ ∈ T be such that for all i LC(P i ) = 1, LT (c i P i ) = β, P i ∈ I and S(P i ) ≤ σ. Let P = c 1 P 1 + • • • + c r P r . If LT (P ) < β, then there exist some c i,j ∈ k such that P = i,j c i,j Spol(P i , P j ) and LT (c i,j Spol(P i , P j )) < β.

Lemma 5.7. Let x α , x β , x γ , x δ ∈ T and P, Q ∈ A be such that LM(

x α P ) = LM(x β Q) = x γ and x δ = lcm(LM(P ), LM(Q)). Then Spol(x α P, x β Q) = x γ-δ Spol(P, Q).
Lemma 5.8. Let G be an S-Gröbner basis of I up to signature < σ ∈ T. Let f ∈ I, homogeneous of degree d, be such that S(f

) ≤ σ. Then there exist r ∈ N, g 1 , . . . , g r ∈ G, Q 1 , . . . , Q r ∈ A such that for all i and x α a monomial of Q i , S(x α g i ) = x α S(g i ) ≤ σ and LT (Q i g i ) ≤ LT (f ). The x α S(g i )'s are all distinct, when non-zero.
Proof. It is clear by linear algebra. One can form a Macaulay matrix in degree d whose rows corresponds to polynomials τ g with τ ∈ T, g ∈ G such that S(τ g) = τ S(g) ≤ σ. Only one per non-zero signature, and each of them reaching an element of LM(I d,≤σ ). It is then enough to stack f at the bottom of this matrix and perform a tropical LUP form computation (see Algorithm 3) to read the Q i on the reduction of f.

We can now provide a proof of Theorem 5.3.

Proof. We prove this result by induction on σ ∈ T such that G is an S-GB up to σ. It is clear for σ = 1.

Let us assume that G is an S-GB up to signature < σ for some some σ ∈ T. We can assume that all g ∈ G satisfy LC(g) = 1. Let P ∈ I be irreducible and such that S(P ) = σ. We prove that there is τ ∈ T, g ∈ G such that LM(P ) = LM(τ g) and τ S(g) = σ.

Our second assumption for G implies that there exist at least one primitive S-irreducible g ∈ G and some τ ∈ T such that τ S(g) = S(f ) = σ. If LM(τ g) = LM(f ) we are done. Otherwise, by Lemma 2.14, there exist some a, b ∈ k * such that S(af + bτ g) = σ ′ for some σ ′ < sign σ.

We can apply Lemma 5.8 to af + bτ g and obtain that there exist r ∈ N,

Q i ∈ A, g i ∈ G such that P = r i=1 Q i g i , LT (Q i g i ) ≤
P and for all i, and x γ monomial of Q i , the x γ S(g i ) = S(x γ g i ) ≤ sign σ are all distinct. We remark that LT (P )

≤ max i (LT (g i Q i )). We denote by m i := LT (g i Q i ).
Moreover, we can assume that all the g i 's are primitive S-irreducible. Indeed, if among them some g ′ is not primitive S-irreducible, then there exists h 0 , t 0 in I × T \ {1} such that h 0 is S-irreducible and LM(t 0 h 0 ) = LM(g ′ ) and t 0 S(h 0 ) = S(g ′ ) = S(t 0 h 0 ). We have S(h 0 ) ≤ sign S(g ′ ) < sign σ. Hence, we can apply the S-GB property for h 0 and we obtain g ′ 0 , τ 0 in G × T such that LM(h 0 ) = LM(τ 0 g ′ 0 ) and S(h 0 ) = S(τ 0 g ′ 0 ) = τ 0 S(g ′ 0 ). We then have LM(g ′ ) = LM(t 0 τ 0 g ′ 0 ) and S(g ′ ) = t 0 τ 0 S(g ′ 0 ) = S(t 0 τ 0 g ′ 0 ), with deg(LM(g ′ )) > deg(LM(g ′ 0 )). As a consequence, this process can only be applied a finite number of times before we obtain a g ′ k ∈ G which is primitive S-irreducible and some b ∈ T such that LM(bg ′ k ) = LM(τ g) and bS(g ′ k ) = S(bg ′ k ) = σ ′ < sign σ = S(τ g). Thus, we can assume that all the g i 's are primitive S-irreducible.

Among all such possible way of writing P as r i=1 Q i g i , we define β as the minimum of the max i (LT (g i Q i ))'s. β exists thanks to Lemma 2.10 of [START_REF] Chan | Gröbner bases over fields with valuations[END_REF].

If LT (P ) = β, then we are done. Indeed, there is then some i and τ in the terms of Q i such that LT (τ g i ) = β and S(τ g i ) ≤ σ.

We now show that LT (P ) < β leads to a contradiction.

In that case, we can write that:

P = m i =β Q i g i + m i <β Q i g i , = m i =β LT (Q i )g i + m i =β (Q i -LT (Q i ))g i + m i <β Q i g i .
As LT (P ) < β and this is also the case for the two last summands in the second part of the previous equation, LT

( m i =β LT (Q i )g i ) < β. We write LT (Q i ) = c i x α i
, with c i ∈ k and β = c 0 x β 0 for some c 0 ∈ k. Thanks to Lemma 5.6 and 2.14, there are some c j,k ∈ k and x β j,k = lcm(LM(g j ), LM(g k )) such that

m i =β LT (Q i )g i = m i ,m j =β c j,k x β 0 -β j,k Spol(g j , g k ).
Moreover, we have for all j, k involved, S(x β 0 -β j,k Spol(g j , g k )) ≤ σ and LT (c j,k x β 0 -β j,k Spol(g j , g k )) < σ.

If there is j, k such that S(Spol(g j , g k )) = σ, then, by the way the Q i were chosen (distinct signatures, multiplicativity of the signatures), the pair (g j , g k ) is normal and the third assumption is enough to conclude.

Otherwise, we have for all j, k involved, S(Spol(g j , g k )) < σ. We can apply Lemma 5.8 to obtain c j,k x β 0 -β j,k Spol(g j , g k ) = i Q j,k i g i such that for all i and x γ monomial of Q j,k i LT (Q j,k i g i ) < β and x γ S(g i ) = S(x γ g i ) ≤ σ. All in all, we obtain some Qi such that P = i Qi g i and for all i LT ( Qi g i ) < β. This contradicts with the definition of β as a minimum. So LT (P ) = β, which concludes the proof.

Remark 5.9. This theorem holds for S-GB up to a given signature or, as we work with homogeneous entry polynomials, for S-GB up to a given degree (i.e. d -S-GB).

A tropical F5 algorithm

Theorem 5.3 gives a first idea on how to do a Buchberger-style algorithm for S-GB. Yet, deciding in advance whether a pair is a normal pair does not seem to be easy. Indeed, the second condition require some knowledge on LM(Syz f 1 ) which we usually do not have. There are two natural ways to Proof. Termination: Assuming correctness, after (theoretically) performing the algorithm for all degree d in N, we obtain an S-GB. Since by Proposition 3.13 all S-GB contain a finite S-GB then at some degree d we have computed a finite S-GB. As a consequence, all S-pairs from degree d + 1 to degree 2d (at most) will not yield any new polynomial in G (no new leading monomial), and thus there will be no S-pair of degree more than 2d, which proves the termination of the algorithm.

Correctness: We proceed by induction on the signature to prove that the result of Algorithm 1 is a tropical S-GB. The result is clear for signature ≤ sign 1.

For the induction step, we assume that the result is proved up to signature

≤ sign x α , with |x α f 1 | = d. Let x β be the smallest guessed signature of M d of signature > sign x α .
We first remark that if there are rows of guessed signature > sign x β that are of true signature < sign x β then: 1. We can conclude that there is no normal pair popped from B with second half of a pair with signature x γ such that x α < sign x γ < sign x β because of condition 2 of Definition 5.1 (which prevents such signature to drop). 2. Using the F5 Criterion Theorem 5.3, it proves that we have in G (and the rows of M d up to signature x α that are added to G) an S-GB up to signature < sign x β . 3. As a consequence, using Theorem 4.6 the Symbolic Preprocessing has produced exactly enough rows of guessed (and true) signature < sign x β from G to S-reduce the row of guessed signature x β . Indeed, since we have an S-GB up to < sign x β , all necessary leading monomials could be attained by product monomialpolynomial of G with guessed signature < sign x β or through the echelon form up to < sign x β of M d . The last consequence is of course also true if there is no such row with a gap between the guessed and the true signature.

Two possibilities can occur for the result of the reduction of the row of guessed signature x β : 1. The row reduces to zero. Then the signature x β is not possible. We then have in G an S-GB up to signature ≤ sign x β . 2. The row does not reduce to zero. Then, depending on whether the reduced row provide a new leading monomial for I ≤ sign x β , we add it to G. We then have in G an S-GB up to signature ≤ sign x β . This concludes the proof by induction. We then can apply the modified F5 Criterion, Lemma 6.2 to conclude that the output of Algorithm 1 is indeed an S-GB.

To conclude the proof of Theorem 1.1, the main result on the efficiency of the F5 algorithm is still valid for its tropical version: Proposition 6.5. If f 1 is not a zero-divisor in A/I ′ , then all the processed matrices M d are (left-) injective. In other words, no row reduces to zero.

Proof. In this case, LM(Syz f 1 ) = LM(I ′ ). Hence, with the choice of rows of M d avoiding guessed signature in LM(Syz f 1 ) no syzygy can be produced. Remark 6.6 (Rewritability). Thanks to Theorem 5.3, it is possible to replace the polynomials in P in the call to Symbolic-Preprocessing on Line 8 of Algorithm 1. They can be replaced by any other multiple of element of G of the same signature. Indeed, if one of them, h, is of signature x α , the algorithm computes a tropical S-Gröbner basis up signature < x α . Hence, h can be replaced by any other polynomial of same signature, it will be reduced to the same polynomial. By induction, it proves all of them can be replaced at the same time. This paves the way for the Rewritten techniques of [F02]. The idea, as far as we understand it, is then to use the polynomial that has been the most reduced to produce a polynomial of signature S(tg) for the upcoming reduction. Taking the x β g (g ∈ G) of signature x α such that g has the biggest signature possible is a first reasonnable idea.2 It actually can lead to a substantial reduction of the running time of the F5 algorithm.

Implementation and numerical results

A toy implementation of our algorithms in Sagemath [Sage] is available on https://gist.github.com/TristanVaccon. Remark 7.1. It is possible to apply Algorithm 1 to compute a tropical Gröbner basis of I given by F = (P 1 , . . . , P s ) by performing complete computation succesively for (P 1 ), (P 1 , P 2 ), (P 1 , P 2 , P 3 ), . . . adding a polynomial at a time playing the part f 1 played in the rest of the article. As we only deal with homogeneous polynomials, it is also possible to do the global computation degree by degree, and at a given degree iteratively on the initial polynomials. By indexing accordingly the signatures, as in [F02], the algorithm can be adapted straightforwardly. This is what has been chosen in the implementation we have achieved.

We have gathered some numerical results in the following array. Timings are in seconds of CPU time. 3 We have compared ours with that of the algorithms of Chan and Maclagan in [CM13] (in Macaulay 2) and Markwig and Ren in [START_REF] Markwig | Yue Computing tropical varieties over fields with valuation[END_REF] (in Singular), provided in [START_REF] Markwig | Yue Computing tropical varieties over fields with valuation[END_REF]. A dot means that the computation could not complete. Entry systems are homogenized. Base field is Q.

Katsura 3 4 5 6 7 Cyclic 4 5 6 [START_REF] Chan | Gröbner bases over fields with valuations[END_REF] ≤ 1

• • • • • • • [MY15] ≤ 1 ≤ 1 ≤ 1 • • ≤ 1 ≤ 1 • Trop. F5
≤ 1 5 74 513 • 4 353 • Loss in precision has also been estimated in the following setting. For a given p, we take three polynomials with random coefficients in Z p (using the Haar measure) in Q p [x, y, z] of degree 2 ≤ d 1 ≤ d 2 ≤ d 3 ≤ 4. For any given choice of d i 's, we repeat the experiment 50 times. Coefficients of the initial polynomials are all given at some high enough precision O(p N ). Coefficients of the output tropical GB are known at individual precision O(p N -m ). We compute the total mean and max on those m's on the obtained tropical GB. Results are compiled in the following array as couples of mean and max, with D = d 1 + d 2 + d 3 -2 the Macaulay bound.

Future works

In this article, we have investigated the main step for a complete F4-style tropical F5 algorithm. We would like to understand more deeply the Rewritten critertion of [F02]. We would also like to understand the natural extension of our work to a Tropical F4 and to a Tropical F5 for non-homogeneous entry polynomials.

  Lemma 2.10. If p ∈ I \ I ′ is homogeneous of degree d, then deg(S(p)) = deg(p)deg(f 1 ). Proposition 2.11. For any p ∈ I \ I ′ , S(p) ∈ NS(Syz f 1 ).

Definition 4. 1 .

 1 Let c n,d = n + d -1 n -1 , and B n,d = (x d i ) 1≤i≤c n,d be the monomials of A d . Then for f 1 , . . . , f s ∈ A homogeneous polynomials, with |f i | = d i , and d ∈ N, we define Mac d (f 1 , .

  f αu is under (row)-echelon form. Let g α 1 , . . . , g αu ∈ A d be the corresponding reduced row-echelon form: we have LM(g α i ) = α i , g α i ∈ Ker(v) and the only monomial of g α i not in NS(Syz f 1 ) is α i . Now, clearly, if f ∈ A d , by reduction by the g α i 's, there exists some g ∈ A d such that v(f ) = v(g) and LM(g) ∈ NS(Syz f 1 ).

e.g. Q or Q p with p-adic valuation, or Q[[X]] with X-adic

Indeed, such a g is at first glance the most reduced possible.

Everything was performed in a guest Ubuntu 14.04 inside a Virtual Machine, with

processors and 29 GB of RAM.

Acknowledgements

We thank Jean-Charles Faugère, Pierre-Jean Spaenlehauer, Masayuki Noro, Naoyuki Shinohara and Thibaut Verron for fruitful discussions.

handle this question: Firstly, we could keep track during the algorithm of the syzygies encountered, and use a variable L as a place holder for their leading monomials. The second condition can then be replaced by LM(u i )S(g i ) / ∈ L . This is what is used in [AP]. Another way is to only consider the trivial syzygies. This amounts to take L = LM(I ′ ) and use the same replacement for the second condition. This is what is used in [F02] and [F15].

We opt for the second choice (only handling trivial syzygies). This give rise to the notion of admissible pair. Definition 6.1 (Admissible pair). Given g 1 , g 2 ∈ I, not both in I ′ , let Spol(g 1 , g 2 ) = u 1 g 1u 2 g 2 be the S-polynomial of g 1 and g 2 . We have

LT (g i )

. We say that (g 1 , g 2 ) is an admissible pair if:

1. the g i 's are primitive S-irreducible polynomials.

if S(g

∈ LM(I ′ ).

S(u

We can then remark that handling admissible pairs instead of normal pairs is harmless, as the latter is a subset of the former. Lemma 6.2. If a set G satisfies the conditions of Theorem 5.3 for all its admissible pairs then it is an S-GB.

In the general case, LM(Syz f 1 ) is not known in advance. However, it can be determined inductively on signatures. This is how the following algorithm will proceed. From a polynomial g, the signature of x α g will be guessed as x α S(g), and after an S-GB up to signature < x α S(g) is computed, we can decide whether S(x α g) = x α S(g), or else x α g happens to be reduced to zero. In the following, we certify inductively whether for a processed x α g, the guessed signature x α S(g) equals the true signature S(x α g). Similarly, guessed admissible pairs are inductively certified to be true admissibles pairs or not once condition 3 of 6.1 is certified. Using this idea, we provide a first version of an F5 algorithm in Algorithm 1, using Algorithm 2 for Symbolic Preprocessing. Remark 6.3. Only signature zero is allowed to appear multiple times in the matrix in construction. The reason is the following: because of Proposition 3.10, for an irreducible polynomial with a given signature, its leading monomial is determined by its signature. After performing the tropical row-echelon form computation, all rows corresponds to irreducible polynomials, hence two rows produced with the same signature are redundant: either they will produce the same leading monomial or they would reduce to zero.

Algorithm 2: Symbolic-Preprocessing input : P , a set of admissible pairs of degree d and G, a S-GB up to degree d -1 output: A Macaulay matrix of degree d 1 D ← the set of the leading monomials of the polynomials in P ; 2 C ← the set of the monomials of the polynomials in P ; 3 U ← the polynomials of P ;

← the element of V with δg of smallest signature, with tie-breaking by taking minimal δ (for degree then for ≤ sign ) ;

14 M ← the polynomials of U, written in Macaulay matrix of degree d and ordered by increasing signature, with no repetition of signature outside of signature 0 (choosing smallest leading monomial to break a tie of signature) ;

15 Return M ;

The tropical LUP form computation to obtain a row-echelon matrix, with no choice of pivot, is described in Algorithm 3. See [V15] for more details. The result we want to prove is then: Theorem 6.4. Algorithm 1 computes an S-GB of I. (0,1) (0,0) (0,0) (0,1) (0,1) (0,0) (0,1) 65519 (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) As for Tropical Matrix-F5, a weight differing from w = [0, 0, 0] yields bigger loss in precision. Regarding to precision in row-reduction, in F5, this weight always use the best pivot on each row. For Matrix-F5, it is always the best pivot available in the matrix. In view of our data, we can observe that the loss in precision for Tropical F5 on these examples, even though it is, as expected, bigger, has remained reasonnable compared to the one of [V15] that allowed full choice of pivot.


Nils Poulicard

Agnès Pinel-Galzi

Denis Fargette

Eugénie Hébrard
email: eugenie.hebrard@ird.fr

Alternative mutational pathways, outside the VPg, of Rice yellow mottle virus to overcome eIF(iso)4G-mediated rice resistance under strong genetic constraints

Alternative mutational pathways, outside the VPg, of Rice yellow mottle virus to overcome eIF(iso)4G-mediated rice resistance under strong genetic constraints

Nils Poulicard, Agnès

Main text

High mutation rates, high levels of recombination or reassortment, short replication cycles and high accumulation rates should allow plant viruses to adapt rapidly to new host species and resistant hosts. However, adaptation dynamics depend on the number and nature of mutations (genetic barrier) and on their fitness cost (phenotypic barrier) [START_REF] Domingo | Viral quasispecies evolution[END_REF][START_REF] Harrison | Virus variation in relation to resistance-breaking in plants[END_REF]. In particular, structural constraints and antagonistic epistasis dramatically reduce the emergence of adaptive mutations [START_REF] Camps | Genetic constraints on protein evolution[END_REF][START_REF] Sanjuan | A network model for the correlation between epistasis and genomic complexity[END_REF][START_REF] Weinreich | Perspective: Sign epistasis and genetic constraint on evolutionary trajectories[END_REF]. This is exemplified by Rice yellow mottle virus (RYMV), belonging to the genus Sobemovirus. RYMV shows a high virus content in plants [START_REF] Poulicard | Why Rice yellow mottle virus, a rapidly evolving RNA plant virus, is not efficient at breaking rymv1-2 resistance[END_REF], evolves rapidly [START_REF] Fargette | Rice yellow mottle virus, an RNA plant virus, evolves as rapidly as most RNA animal viruses[END_REF] and is able to adapt to highly resistant rice cultivars [START_REF] Pinel-Galzi | Theme and variations in the evolutionary pathways to virulence of an RNA plant virus species[END_REF], Traoré et al., 2010). However, strong demographic constraints (bottlenecks and random genetic drift), genetic constraints (codon usage and mutational bias) and phenotypic constraints (epistasis antagonism and fitness costs) have been identified, they modulate the ability to overcome the high resistance mediated by the RYMV1 gene which encodes the translation initiation factor eIF(iso)4G1 [START_REF] Poulicard | Why Rice yellow mottle virus, a rapidly evolving RNA plant virus, is not efficient at breaking rymv1-2 resistance[END_REF], Traoré et al., 2010).

The genome of RYMV consists of a single-stranded, positive-sense RNA molecule with a viral protein genome-linked (VPg) that is covalently linked to its 5' end. The VPg encoded by the central domain of ORF2a interacts with rice eIF(iso)4G1 [START_REF] Hébrard | Direct interaction between the Rice yellow mottle virus VPg and the central domain of the rice eIF(iso)4G1 factor correlates with rice susceptibility and RYMV virulence[END_REF]. A single amino acid substitution in the middle domain of eIF(iso)4G1 results in the rymv1-2 allele found in the highly resistant Oryza sativa indica cultivars Gigante and Bekarosaka [START_REF] Albar | Mutations in the eIF(iso)4G translation initiation factor confer high resistance of rice to Rice yellow mottle virus[END_REF], Rakotomalala et al., 2008). The phenotype of this recessive allele is characterised by an absence of symptom expression and a lack of viral detection by ELISA.

However, adaptation to the rymv1-2 allele has been reported, and the genetic determinism of this adaptation has been elucidated [START_REF] Pinel-Galzi | Theme and variations in the evolutionary pathways to virulence of an RNA plant virus species[END_REF]. The rymv1-2 resistance-breaking (RB) phenotype is caused by punctual mutations in the VPg, most often located at codon 48, but sometimes at codon 52. The associated major and minor mutational pathways have been described previously.

The rymv1-2 RB ability is related to an E/T polymorphism at the adjacent codon 49 of the VPg [START_REF] Poulicard | Historical contingencies modulate the adaptability of Rice yellow mottle virus[END_REF]. Threonine at codon 49 (T49) confers a strong selective advantage over viral populations harbouring E49 in susceptible and resistant O. glaberrima cultivars, whereas T49 is a major constraint to overcome the rymv1-2 allele found in O. sativa indica cultivars (cv.) Gigante and Bekarosaka. Antagonistic epistasis between T49 and RB mutations was established through mutagenesis of the infectious clone CIa. Phenotypic and genetic barriers prevented the major and minor mutational pathways from being followed.

The direct influence of the E/T polymorphism at codon 49 on the rymv1-2 RB ability of the wild-type genotype CIa (with T49) and the mutated genotype CIa49E was validated experimentally, and the T49E substitution was found to increase the ability to overcome rymv1-2 resistance from 5% to 40% [START_REF] Poulicard | Historical contingencies modulate the adaptability of Rice yellow mottle virus[END_REF]. The RB pattern of the mutant CIa49E was therefore similar to that of other wild-type viral populations containing E49 [START_REF] Pinel-Galzi | Theme and variations in the evolutionary pathways to virulence of an RNA plant virus species[END_REF] and mostly involved fixation of the R48G RB mutation (i.e., the first step in the major mutational pathway).

Although the adaptability of the CIa genotype has been assessed previously [START_REF] Pinel-Galzi | Theme and variations in the evolutionary pathways to virulence of an RNA plant virus species[END_REF], rymv1-2 resistance breakdown has never been observed. In the present study, three of 53 plants (i.e., 5%) inoculated with the CIa genotype showed characteristic RYMV symptoms [START_REF] Poulicard | Historical contingencies modulate the adaptability of Rice yellow mottle virus[END_REF]. The objective of this study was to identify and characterise the mutational pathways involved in rymv1-2 resistance breakdown in the unfit CIa genotype.

The VPg of the RB populations of each plant was amplified and directly sequenced according to a method described previously [START_REF] Fargette | Inferring the evolutionary history of rice yellow mottle virus from genomic, phylogenetic, and phylogeographic studies[END_REF]. Surprisingly, these RB populations did not show mutations in the VPg. To identify candidate mutations involved in the RB phenotype, the full-length viral genomes of these populations were amplified via RT-PCR and sequenced. Two RB genotypes were characterised by a single mutation (A2229G or G2278A), while no mutation was detected in the third RB genotype. This is the first report of an RB-associated mutation outside the VPg. To further investigate the frequency of these mutations, twenty infected plants of fifty plants inoculated with CIa49E were analysed following the same procedure. Three of the twenty plants infected with the CIa49E genotype also displayed single mutations outside the VPg (A2199G, G2275A and A2301G). These five mutations occurred within a 102-nucleotide-long stretch in the ORF2a/ORF2b overlapping region, which was located 376 nucleotides downstream of the VPg (Figure 1a). These mutations always caused non-synonymous changes in the P2a polyprotein (Figure 1b), and they generally involved the substitution of a positively charged amino acid, such as lysine or arginine, with the negatively charged amino acid glutamic acid. In contrast, these mutations did not always change the physico-chemical properties of the residue in ORF2b. The and CIa*R557Q (100% infection rate). To establish the causal role of these mutations, directed mutagenesis of the infectious clone CIa was performed using the QuikChange Site-Directed Mutagenesis Kit (Stratagene). Notably, the K531E mutation was introduced without the T49E mutation in the VPg to assess the independence of the two mutations. Transcription of the mutated clones and inoculation of the viral RNAs in planta were performed as previously described [START_REF] Poulicard | Why Rice yellow mottle virus, a rapidly evolving RNA plant virus, is not efficient at breaking rymv1-2 resistance[END_REF]. Each mutated clone was inoculated in five susceptible and five resistant individuals of O.s. indica cv. IR64 and cv. Bekarosaka, respectively. All mutants were infectious in the susceptible plants (100% infection rate). In all of the resistant plants, characteristic symptoms, high ELISA values, successful RT-PCR amplification and sequencing confirmed that the punctual mutations K531E, K541E and R557Q were directly involved in the rymv1-2 RB phenotype. Additional mutations did not emerge within the P2a or VPg coding regions. Interestingly, the role of the K531E mutation in resistance breakdown was validated in the absence of the T49E VPg mutation. Therefore, the emergence of K531E is sufficient to overcome rymv1-2 resistance.

To evaluate the accumulation of the three RB genotypes CIa49E*K531E, CIa*K541E and CIa*R557Q, three resistant and three susceptible individuals of O.s. indica cv.

Bekarosaka and cv. IR64, respectively, were back-inoculated and analysed via qRT-PCR following a protocol previously described [START_REF] Poulicard | Why Rice yellow mottle virus, a rapidly evolving RNA plant virus, is not efficient at breaking rymv1-2 resistance[END_REF]. The accumulation of each mutant genotype was compared to that of the wild-type CIa genotype and two rymv1-2 RB genotypes with mutations in the VPg, i.e., CIa*R48E and CIa*H52Y (Figure 2a). In this experiment, c.10 12 RNA copies of each genotype were inoculated per plant. The flanking region of the VPg and the C-terminal region of P2a (nucleotides 1,480-2,900) were sequenced from the total RNA extracts used for qRT-PCR, no new mutations were detected. At 28 dpi, c.10 10 copies of the CIa*K531E, CIa*K541E and CIa*R557Q genotypes had accumulated per milligram of leaf tissue in the resistant plants; i.e., their levels were 10 5 times higher than those of the wild-type CIa genotype (Figure 2a). No significant differences in RNA accumulation were detected between the CIa*K531E, CIa*K541E and CIa*R557Q genotypes (ANOVA, P>0.05). Interestingly, the accumulation of these RB genotypes was not significantly different from that of the suboptimal CIa*H52Y genotype (P>0.05). CIa*R48E showed maximal accumulation of c.10 12 RNA copies per milligram of leaf tissue in the resistant cultivar at 28 dpi, as observed previously [START_REF] Poulicard | Why Rice yellow mottle virus, a rapidly evolving RNA plant virus, is not efficient at breaking rymv1-2 resistance[END_REF], which was approximately fifty times higher than the accumulation of the other RB genotypes (P<0.0001). In the susceptible plants, the RNA accumulation of the CIa*K531E, CIa*K541E, CIa*R557Q and CIa*H52Y genotypes at 14 dpi was not significantly lower than that of the wild-type genotype (P>0.05; Figure 2b). In contrast, the CIa*R48E genotype was strongly impaired in the susceptible hosts, and its RNA accumulation was c.10 5 times lower than that of the other genotypes. Surprisingly, sequencing of the RB viral population in the susceptible plants revealed the emergence of reverse mutations 28 days after inoculation. The artificially inserted substitution from arginine to glutamic acid (from AGG to GAG) at codon 48 in VPg of the CIa*R48E genotype was displaced by a mutation that restored the positively charged residue, i.e., lysine (AAG). In addition, reversion of the K531E and K541E mutations was always observed following back-inoculation to O.s. indica cv. IR64. These reverse mutations suggested a fitness cost in susceptible hosts of the mutations that emerged in the C-terminal domain of P2a. No other mutation emerged in the P2a coding region during this fitness experiment, and compensatory mutations were never observed in the susceptible plants.

The natural diversity of the positions involved in the alternative RB pathway and their genetic context in the ORF2a/ORF2b overlapping region were analysed (Suppl. Table 1).

Sequence alignment of 33 full-length sequences of viral populations that were representative of the genetic and geographic diversity of RYMV [START_REF] Rakotomalala | Rice yellow mottle virus in Madagascar and in the Zanzibar Archipelago; island systems and evolutionary time scale to study virus emergence[END_REF] revealed that these positions were strictly conserved. The nucleotide diversity (π) was estimated for each ORF using Dnasp software [START_REF] Librado | DnaSP v5: A software for comprehensive analysis of DNA polymorphism data[END_REF]. As previously reported [START_REF] Fargette | Inferring the evolutionary history of rice yellow mottle virus from genomic, phylogenetic, and phylogeographic studies[END_REF]), the nucleotide variability was lower in ORF2a and ORF2b (π=0.054 and 0.057) than in ORF1 and ORF4 (π=0.109 and 0.087). However, these values were still higher than that found for the recently described ORFx which overlaps the 5' end of sobemovirus ORF2a (Ling et al., 2013) (π=0.029). Interestingly, the RB mutations always emerged in the ORF2a domain, which is characterised by low nucleotide diversity (Figure 3a). Overlapping viral regions (OVRs) have been reported to be highly conserved, showing strong constraints against synonymous changes [START_REF] Simon-Loriere | The effect of gene overlapping on the rate of RNA virus evolution[END_REF]. Accordingly, the P2a OVR exhibited a lower diversity of synonymous sites than the VPg, while the proportion of nonsynonymous sites was similar (Suppl. Table 2).

The organisation and the biological function of the C-terminal domain of P2a are unknown. However, the processing of the P2a polyprotein of another sobemovirus, Sesbania mosaic virus (SeMV), has recently been elucidated. In addition to a serine protease and VPg, two new proteins, designated P10 and P8, were identified [START_REF] Nair | Processing of SeMV polyproteins revisited[END_REF][START_REF] Satheshkumar | Polyprotein processing: cis and trans proteolytic activities of Sesbania mosaic virus serine protease[END_REF]. Similar to the VPg of RYMV, the VPg and P8 of SeMV were demonstrated to be natively unfolded proteins [START_REF] Hébrard | Intrinsic disorder in Viral Proteins Genome-Linked: experimental and predictive analyses[END_REF], Nair & Savithri, 2010a[START_REF] Satheshkumar | Natively Unfolded" VPg is essential for sesbania mosaic virus serine protease activity[END_REF]. Detection of the disordered arrangement of the C-terminal domain of P2a of the RYMV was then performed using the software FoldIndex© [START_REF] Obradovic | Exploiting heterogeneous sequence properties improves prediction of protein disorder[END_REF][START_REF] Prilusky | FoldIndex: a simple tool to predict whether a given protein sequence is intrinsically unfolded[END_REF]. Prediction analyses indicated an alternating arrangement of folded and unfolded domains in RYMV P2a that was similar to the profile obtained for SeMV, although the sequence identity between sobemoviruses is low (Figure 3b).

Interestingly, all of the RB mutations described in this study were located within the predicted unfolded segment of the P2a OVR, which strongly suggested that all of these RB mutations also occurred in the RYMV homologue of P8. OVRs have been reported to exhibit more structural disorder than non-overlapping regions (NOVRs) [START_REF] Rancurel | Overlapping genes produce proteins with unusual sequence properties and offer insight into de novo protein creation[END_REF]. Moreover, the termini of proteins are, on average, more prone to be disordered than internal regions (Uversky). Because intrinsically disordered protein tails are engaged in a wide range of functions, the C-terminal domain of P2a may be directly or indirectly involved in the interaction between the VPg of RYMV and the eIF(iso)4G1 of rice. Thus, the RB mutations described in this study may favour the capture of eIF(iso)4G1 in resistant plants, which would compensate for the relatively low affinity of the wild-type VPg with the rymv1-2 eIF(iso)4G1 [START_REF] Hébrard | Direct interaction between the Rice yellow mottle virus VPg and the central domain of the rice eIF(iso)4G1 factor correlates with rice susceptibility and RYMV virulence[END_REF].

Despite the crucial roles of eIFs/VPg interactions in successful infections and in plant resistance breakdown, described in numerous studies (for review [START_REF] Truniger | Recessive resistance to plant viruses[END_REF][START_REF] Wang | Eukaryotic translation initiation factor 4E-mediated recessive resistance to plant viruses and its utility in crop improvement[END_REF], exceptions are occasionally reported. The RB phenotypes induced by Lettuce mosaic virus and Clover yellow vein virus from the genus Potyvirus are sometimes related to the emergence of mutations in the cylindrical inclusion (CI) and P1 proteins, respectively [START_REF] Abdul-Razzak | Involvement of the cylindrical inclusion (CI) protein in the overcoming of an eIF4E-mediated resistance against Lettuce mosaic potyvirus[END_REF][START_REF] Nakahara | Involvement of the P1 cistron in overcoming eIF4E-mediated recessive resistance against Clover yellow vein virus in pea[END_REF]. In this study, the detected RB mutations emerged in the C-terminal domain of the P2a polyprotein, which is downstream of the VPg, within the ORF2a/ORF2b overlapping region. This alternative RB mutational pathway was revealed under strong selective constraints. The threonine at position 49 of the VPg was previously reported to be the major genetic constraint blocking the emergence of RB mutations in the VPg. This strong constraint could lead this genotype to adopt an alternative strategy to overcome the rymv1-2 allele. However, the frequency of this alternative mutational pathway in less-constrained viral populations might be underestimated, as suggested by the detection of P2a C-terminal mutations in the artificial genotype CIa49E.

Comparison of the identified RB mutational pathways revealed similarities. Although the RB mutations emerged in two different domains, they occurred in two unfolded regions of the same highly conserved P2a polyprotein. The fitness of RB genotypes with mutations in the Cterminal domain of P2a was suboptimal in rymv1-2-resistant plants and intermediate in susceptible plants, as were those of the artificially mutated genotypes CIa*H52Y and CIa*R48I [START_REF] Poulicard | Why Rice yellow mottle virus, a rapidly evolving RNA plant virus, is not efficient at breaking rymv1-2 resistance[END_REF]. Similar to genotypes CIa*48E*49E and CIa*48G*49E [START_REF] Poulicard | Why Rice yellow mottle virus, a rapidly evolving RNA plant virus, is not efficient at breaking rymv1-2 resistance[END_REF][START_REF] Poulicard | Historical contingencies modulate the adaptability of Rice yellow mottle virus[END_REF], the reversions observed here suggested a fitness cost in susceptible hosts. Taken together, the results of this study show that, in spite of tight restrictions due to a wide spectrum of constraints, a priori unfit genotypes could adopt a wide array of solutions to efficiently overcome strong selective pressures.

  genotypes harbouring the mutations A2199G, A2229G, G2275A, G2278A and A2301G were subsequently designated CIa49E*K531E, CIa*K541E, CIa49E*G556E, CIa*R557Q and CIa49E*K565E, respectively, in reference to the nature and position of the mutations in the P2a polyprotein. Back-inoculations of five resistant O.s. indica cv. Gigante plants with each viral population confirmed the rymv1-2 RB ability of three of them, CIa49E*K531E, CIa*K541E

Figure 1 :

 1 Figure legends: Figure 1: Location of the alternative resistance-breaking mutations. a. Genomic organisation of RYMV. Alternative RB mutations emerged within the carboxy-terminal domain of polyprotein P2a (black square), while the major mutational pathways involved the VPg (hatched square). ORF, open reading frame; Pro, protease; VPg, viral genome-linked protein; Pol, polymerase; CP, coat protein; fs, -1 frameshift signal. b. Nature of the alternative rymv1-2 RB mutations in the five viral populations from the infectious clone CIa (accession reference AJ608219) and the mutated clone CIa49E. Mutations are indicated in the two overlapping ORFs (ORF2a and ORF2b after the -1 frameshift).

Figure 2 :

 2 Figure 2: Fitness of the alternative resistance-breaking mutations. a. Viral accumulation of the wild-type CIa and RB genotypes with mutations within and outside the VPg (RB VPg and RB CterP2a, respectively) in resistant plants. The number of viral RNA copies per milligram of fresh leaf tissue was estimated via quantitative reverse transcriptase-polymerase chain reaction (qRT-PCR) at 28 days post-inoculation (dpi) in the resistant cultivar O.s. indica cv. Bekarosaka. a, b and c, groups that were significantly different after multiple mean comparison (ANOVA, P=0.05). b. Viral accumulation at 14 dpi in the susceptible plants O.s. indica cv. IR64.

Figure 3 :

 3 Figure 3: Distribution of RB mutations in the P2a polyprotein. Arrows: RB mutations; fs: -1 frameshift signal. a. Diversity index (total substitutions/site) calculated using Dnasp.b. Prediction of the folded/unfolded arrangement using FoldIndex.


P Aguilera
email: paula.aguilera@snecma.fr

C Lair

F Issac

B Michielsen
email: bastiaan.michielsen@onera.fr

M Hélier

M Darces

INDIRECT EFFECTS OF LIGHTNING ON AIRCRAFT ENGINE

Keywords: Lightning Simulation, Macro-Modelling, Patch Finite Elements

This paper presents a new approach for simulating the indirect effects of a lightning impact on an aircraft engine. Based on macro-modelling, it performs a model reduction, in a similar way as "stick models", but using a patch support instead. This new macro finite element space allows for fast resolution of the quasi-static lightning injection problem.

Introduction

Due to a reduced design time, numerical simulation plays a major role from the specification to the certification of an aircraft engine regarding indirect effects of lightning [START_REF] Parmantier | Indirect Effects of Lightning on Aircraft and Rotorcraft[END_REF]. On the one hand, 3D solvers, based on the resolution of discretized Maxwell's equations, can be used to predict precisely the constraints to be applied to equipments in a complex system, and therefore be a part of lightning certification process. However, they involve heavy tools which are not optimized for quick parameters optimization or measurement analysis, as they require lengthy computations, even with using a powerful parallel computer. On the other hand, much lighter models such as "stick models" have gained a lot of interest [START_REF] Prost | Lightning-Induced Current Simulation Using RL Equivalent Circuit: Application to an Aircraft Subsystem Design[END_REF]. Based on the PEEC (Partial Element Equivalent Circuit) method, they have shown to be faster and sufficiently accurate in some aeronautical applications. One drawback though is the poor estimation of the current distribution at higher frequencies as current is constrained to follow the stick path. A new model, based on macro-modelling, has been implemented to overcome this problem.

Method

Macro-modelling for lightning simulation

Assuming the quasi-static behavior of the phenomena, lightning current distribution can be expanded in a macro finite element space. Each macro finite element is locally curl-free with a constant divergence Q over a triangulated support called "patch" [START_REF] Knockaert | Generalized Poisson-Neumann Polygonal Basis Functions for the Electromagnetic Simulation of Complex Planar Structures[END_REF].

∇ . = ∂ ∂x + ∂ ∂y = (1) ∇ × = - =
Formulation (1) can be discretized in a 1-skeleton of the simplicial complex dual to the triangulation of the patch (Figure 1).

Figure 1. Simplicial complex dual of a triangulation

As can be written as the gradient of a potential: , (1) becomes:

∆ | = - 1 ! (2) • # $| % = & - 1 N ( ) *+ i ∈ ∂ . P, 0 *+ i ∈ ∂P -∂ . P 2
where ! represents the number of cells of patch P, and 3 4 ! the number of cells defining boundary 5 6 (see Figure 2). This Poisson-Neumann problem ( 2) is solved by using the surface mesh Laplace operator [START_REF] Huiskamp | Difference Formulas for Surface Laplacian on a Triangulated Surface[END_REF]. Its coefficients are given by the formulas:

∆ | = 4 8 9 : • ; 1 8 9 < ====== (3) ∆ | > = & - 4 8 9 : • 1 8 > *+ ∈ ?@*A 0, BCDB 2
where

8 9 : = 1 E 8 > > ∈ F@ A G 1 8 9 : H = 1 E 1 8 > > ∈ F@ A
(4) = 8*IJ?@*AK 8 > being the distance between nodes i and j. This operator enables the interpolation between a limited set of boundary currents and the control of the obtained current density's divergence by imposing a constant charge density equal to -L M N (see [START_REF] Andriulli | Hierarchical Bases for Nonhierarchic 3-D Triangular Meshes[END_REF] for alternative techniques).

O PQ = R P . SJ Q K = R P @TA. R U@T, T V A Q W XL PQ = Y Z P . JZ Q K = Y Z P @TA. Y U@T, T V AZ Q (5) [ PQ = R P . \ Q
where ] is a macro element, with p= 1, ..., N, N being the total number of degrees of freedom of the entire configuration. The constant \ is the surface impedance of the patch and Z Q = 8*^ Q . In this formulation, a static approximation of the Green's Function is assumed:

U@T, T V A ≈ 1 4`| T -T V | (6)

Sensitivity analysis of mesh on components

Different sources of error can be enumerated for this macro model:

-The Galerkin representation of the components.

-The relaxation method used to implement the Laplace operator. -The static approximation of the Green's function.

The inputs of the model, e.g. the number of cells of the triangulation and the type of mesh used (structured, unstructured, regular and irregular) will have an impact on the resulting coefficients. As an example, let us consider a squared plate (length l = 1 m, width w = 1 m) over which 2 orthogonal distributions circulate (Figure 3). The conductivity a is set to 4000 S/m and its depth e to 5 mm. The theoretical resistance and self-inductance of a uniform distribution in a plate are given by [START_REF] Rosa | The Self and Mutual Inductances of Linear Conductors[END_REF]: Table 6. Self-inductance of the two current distributions along x and y over an unstructured irregular mesh Tables 1 and2 show the sensitivity on coefficients R and L to the number of cells. When this number increases, the error associated to the Galerkin representation decreases. Tables 3 and4 assess the influence of the mesh structure on the results (see Figure 4). For an unstructured mesh, the dual nodes of a triangulation are not distributed at regular angles which is one of the requirements for the relaxation method used to solve (3). Finally, Table 5 and 6 show the impact of irregular distances between neighbours (see Figure 5). When the irregularity is along the equipotential lines, the error remains unchanged with respect to an unstructured regular mesh. The analysis of the error associated to a static approximation of the Green's function is presently work in process.

[ = \ = 1 aB = 0,05 Ω (7)

Numerical method

Besides this model, a global method for lightning simulation has been proposed which comprises several steps.

Step 1 concerns the identification of contact resistances in the engine Digital Mock-Up (DMU) (see Figure 6). The electrical interconnections between each conductor of the engine define a first partitioning of the interaction configuration. This partitioning delimitates complex modules such as harnesses, structures and equipments. The triangulation of each module can easily reach several millions of cells. The full-wave resolution may require a long time (typically more than ten hours on a multi-processors (256) computer, with a limited time range (typically 50 µs). As the aim of this study is the implementation of a numerical method for fast resolution, a geometric surface smoothing can be applied in order to reduce the number of micro finite elements.

Step 2 is based on geometric surface smoothing of complex conductors. The characteristic dimension of an aircraft engine is 5 meters, which is small compared to the minimal wavelength of lightning (30 meters). Therefore, as long as electrical interconnections are preserved, a reduction of the number of cells will have little impact on the results. Figure 7 shows a mesh reduction applied to some structural parts of the engine. Once all the modules have been simplified, one has to specify the final partitioning of the system, which constitutes the next step.

Step 3: The final partitioning can be done automatically over domains which are simply connected using the spectral resolution of the Laplace operator (see [START_REF] Adrian | Primal and Dual Graph Haar Bases for the Hierarchical Regularisation of the EFIE on Unstructured Meshes[END_REF]). A binary tree is then filled with subdivisions. Finally, the current distributions are implemented for each patch defined in Figure 8.

Tests set-up

The numerical method presented in this paper has been applied to a cylinder made of composite material covered by several harnesses over which tests in Continuous Wave (CW) have been run.

Figure 9. Test set-up

The system under test is placed on a wooden structure (Figure 9). The material composition is depicted in Figure 10 and the injection configuration for the CW analysis in Figure 11. The initial partitioning proposed in Figure 12 is based on the analysis of the electrical interconnections between conductors and the materials distribution in the system. This partitioning leads to a network with the pertinent degrees of freedom to obtain a good correspondence with measurements at low frequency, as it will be shown in section 4.

Low frequency partitioning

The calculation of the macro impedance matrix associated to the partitioning in Figure 12 Globally, the simulated current flowing over the cables from a lightning injection is in good agreement with measurement (Figures 13, 14, 15). However, beyond 1 MHz, it differs due to noise in the measurement chain. The high frequency response of cable 1C between 100 kHz and 1 MHz can be in better correspondence with measurement if the partitioning is modified.

Sensitivity to partitioning on HF response

The low frequency partitioning can be locally refined (see Figure 16) so that current can flow over the cylinder transversally and feed the cable 1C with the right amplitude at high frequencies (Figure 17).

Conclusion

In this paper, a new macro model for the quasi-static lightning injection problem has been proposed. It provides the pertinent number of degrees of freedom necessary to reproduce the physical phenomena of lightning. Besides this model, a numerical method has been presented, which includes the analysis of electrical interfaces between conductors, the geometrical surface smoothing for complex structures and the system partitioning on which the high frequency lightning response depends. In order to better fit the transition to this high frequency response, a dedicated model is being implemented which is based on the co-simulation between low frequency current distributions and high frequency ones which account for so-called "proximity effects" in inductive interactions. Finally, the capability of the model to deal with complex geometries will be tested by confronting the simulation with lightning injection on an actual aircraft engine.

Figure 2 .

 2 Figure 2. A macro finite element on a patch Once these current distributions have been constructed, one can compute the associated model coefficients with:

Figure 3 .

 3 Figure 3. Two orthogonal distributions over a squared plate

Figure 5 .Table 5 .

 55 Figure 5. Current distribution on an irregular unstructured mesh, left: along x, right: along y Nb of cells

Figure 6 .

 6 Figure 6. Digital Mock-Up of some constitutive elements of an aircraft engine

Figure 7 .

 7 Figure 7. Mesh reduction of part of an engine: top: 400000 cells, bottom: 2000 cells

Figure 8 .

 8 Figure 8. Partitioning applied to an engine after steps 1 and 2

FigureFigure 11 .

 11 Figure 10. Materials

Figure 12 .

 12 Figure 12. Low frequency partitioning

  takes only 30 seconds for 2000 cells in the triangulation and 20 patches. The circuit equation is solved in 1 second.

Figure 13 .

 13 Figure 13. CW analysis of normalized current over cable 1B (see Figure 11), continuous: simulation, dashed: measurement

Figure 16 .

 16 Figure 16. Locally refined partitioning

Table 1 .

 1 Resistance of the two current distributions along x and y over a structured mesh for different numbers of cells

	O ≈	d e 2`G	Cg G	2C h iQ	H -1 +	h iQ
	Nb of cells 16 -l/2	[ r 42 mΩ		[ 42 mΩ	Error x 16.0%	Error y 16.0%	Asymmetry 0%
	64 -l/4	46 mΩ		46 mΩ	8.0%	8.0%	0%
	256 -l/8	49,3 mΩ	49,3 mΩ	1.4%	1.4%	0%

C H = 2,83. 10 Xl m where h iQ = 0.447 • opi q .

Figure 4. Squared plate. Left: structured mesh, Right: unstructured mesh

Table 2 .

 2 Self-inductance of the two current distributions along x and y over a structured mesh for different numbers of cells

	Nb of cells 16 -l/2	[ r 40 mΩ	[ 40 mΩ	Error x 20.6%	Error y 20.6%	Asymmetry 0%
	64 -l/4	46 mΩ	46 mΩ	8.0%	8.0%	0%
	256 -l/8	47.4 mΩ	47.5 mΩ	5.2%	5.0%	0.2%

Table 3 .

 3 Resistance of the two current distributions along x and y over an unstructured mesh for different numbers of cells

	Nb of cells 16 -l/2	O r 0.21 µH	O 0.21 µH	Error x 25.7%	Error y 25.7%	Asymmetry 0%
	64 -l/4	0.25 µH	0.25 µH	11.7%	11.7%	0%
	256 -l/8	0.274 µH	0.274 µH	3.2%	2.5%	0.7%

Table 4 .

 4

Self-inductance of the two current distributions along x and y over an unstructured mesh for different numbers of cells