Xavier Caruso

David Lubicz

Linear Algebra over Z p [[u]] and related rings

Let R be a complete discrete valuation ring, S = R [[u]] and n a positive integer. The aim of this paper is to explain how to compute efficiently usual operations such as sum and intersection of sub-S-modules of S d . As S is not principal, it is not possible to have a uniform bound on the number of generators of the modules resulting of these operations. We explain how to mitigate this problem, following an idea of Iwasawa, by computing an approximation of the result of these operations up to a quasi-isomorphism. In the course of the analysis of the p-adic and u-adic precisions of the computations, we have to introduce more general coefficient rings that may be interesting for their own sake. Being able to perform linear algebra operations modulo quasi-isomorphism with S-modules has applications in Iwasawa theory and p-adic Hodge theory.

Introduction

Let R be a complete discrete valuation ring (see §2.1 for a reminder of the definition) whose valuation is denoted by v R . Let K denote its fraction field with valuation v K and π be a uniformizer of R. We set S = R[[u]]; it is the ring of formal series over R. Our aim is to provide efficient algorithms to deal with finitely generated modules over S. Since, we can always represent a torsion module as the quotient of two torsion-free modules, we shall focus on torsion-free modules.

Any finitely generated torsion-free S-module M can be considered as a submodule of S d for d big enough. As a consequence, we can represent M by a matrix whose columns are the coefficients of generators of M in the canonical basis of S d . Thus we can reformulate our problem as follows: given M 1 and M 2 two matrices representing respectively the S-modules M 1 and M 2 embedded in S d , give algorithms to compute a matrix representing M 1 ∩ M 2 or M 1 + M 2 . We would like also to be able to check membership, equality of sub-S-modules, inclusions, etc. As S is not a principal ideal domain, in order to control the number of generators of the sub-S-modules of S d , we propose, following an idea of Iwasawa, to compute approximations of the submodules resulting of aforementioned operations in the following sense: we say that a morphism M 1 → M 2 is a quasiisomorphism if its kernel and co-kernel have both finite length, and we want to make computations modulo quasi-isomorphisms. We propose two different approaches, each of them having its own advantages and disadvantages.

First, we notice that there exists a correspondence between the set of classes of modules modulo quasi-isomorphism and modules over the rings S π and S u defined respectively as the localization of S with respect to π and the completion of the localization of S with respect to u. For A = S π , S u , let Free d A be the set of free sub-A-modules of A d , and denote by Mod d S/qis the set of quasiisomorphism classes of sub-S-modules of S d , there is an injective morphism Ψ ′ : Mod d S/qis → Free d Sπ × Free d Su , M → (M ⊗ S S π , M ⊗ S S u ), where M is any representative in the class M . The image of Ψ ′ can be precisely characterized (see Theorem 1.1 below). Using this correspondence, operations with modules with coefficients in S reduces to the computation with modules over S π and S u . As these two last rings are Euclidean, there exist classical canonical representations and algorithms to manipulate modules over these rings.

A second approach consists in finding a canonical representative in a class of modules modulo quasi-isomophism which is amenable to computations. Such a representative is provided by the maximal module of a S-module M . It can be defined as the unique free module in the class of quasi-isomorphism of M . We present an algorithm to compute the maximal module associated to a sub-S-module of S d which is inspired by a construction of Cohen, presented in [10, p. 131], to obtain a classification up to quasi-isomorphism of finitely generated S-modules. We can then compose this algorithm with algorithms to compute basic operations on free modules in order to compute with representatives up to quasi-isomorphisms.

In order to obtain real algorithms (i.e. something computable by a Turing machine) we have to consider the fact that elements of S and its localized are not finite. In this paper we consider an approach in two steps in order to solve this problem. First, we give the ability to Turing machines, to manipulate, by the way of oracles, elements of S, S π , S u . More precisely, we suppose given oracles able to store elements of the base ring, compute valuation, multiplication, addition, inversion, and Euclidean division. We express the complexity of an algorithm with oracle by the number of calls to the oracles to compute ring operations. Once we have well defined algorithm with oracles to compute with modules, we study in a second time the problem of turning them into real algorithms.

Much in the same way as for floating point arithmetic, the actual computations with modules with coefficients in S are done with approximations up to certain π-adic and u-adic precisions. It is important to ensure that the (truncated) outputs of our algorithms are correct which means that they do not depend on the π or u powers of the input that we have forgotten. In order to deal with this precision analysis, it is convenient to consider a generalisation of the family of ring coefficients S. Namely, given α, β relatively prime integers, we write ν = β/α and set S ν = { a i u i ∈ K[[u]]|v K (a i ) + νi ≥ 0, ∀i ∈ N}. We have S 0 = S. In this paper, we develop a theory of S ν -modules which encompass modules over S and use it in order to obtain algorithm with complexity bounds and proof of correctness.

More precisely, we generalize the definition of a maximal module for finitely generated torsionfree S ν -modules. Denote by Max d Sν the set of maximal sub-S ν -modules of S d ν . We prove the following theorem (see Theorem 3.12), which generalize the above mentioned decomposition: is injective and its image consists of pairs (A, B) such that A and B generate the same E -vector space in E d . If a pair (A, B) satisfies this condition, its unique preimage under Ψ is given by A∩B.

In the theorem, E is a field containing S ν and its localized S ν,π and S ν,u which is precisely defined in Section 2.2. We give an algorithm with oracles to compute the maximal module associated to a finitely generated torsion-free S ν -module. In general, it is not true that the maximal module of a torsion-free S ν -module is free, although this property holds when ν = 0. Nonetheless, by using the theory of continued fraction, it is possible to obtain a tight upper bound on the number of generators of a maximal module embedded in S d ν . If ν is rational, it admits a unique finite development as a continued fraction that we denote by [a 0 ; a 1 , . . . , a n ] (here, we suppose that a n = 1). We can prove the following (see Theorem 3.32): Theorem 1.2. Let ν = [a 0 ; a 1 , . . . , a n ]. Let M be a sub-S ν -module of S d ν . Then Max(M ) is generated by at most d • (2 + ⌈n/2⌉ i=1 a 2i ) elements. We provide some simple examples to show that a lot of basic operations that we need in order to compute with modules over S ν , such as the computation of the Gauss valuation, are not stable. This means that, in general, the computation with approximations of the input data does not yield approximation of the result. This is where it becomes interesting to use the possibility to change the slope ν of the base ring S ν . In the context of our computation, a bigger slope plays the role of a loss of precision in the computation of an approximation of a module over S ν . In this direction, we can prove the following theorem (see Theorem 4.7 for a precise statement): Theorem 1.3. Let M 1 and M 2 be two finitely generated sub-S ν -modules of S d ν such that M 2 ⊂ 1/π c M 1 for a positive integer c. Let M 1 and M 2 be the matrices with coefficients in S ν of generators of M 1 and M 2 in the canonical basis of S d ν . Suppose we are given approximations M r 1 and M r 2 of M 1 and M 2 respectively. Then, for a well chosen ν ′ > ν, there exists a polynomial time algorithm in the length of the representation of M r 1 and M r 2 to compute a matrix M r 3 which is an approximation of the maximal module associated to

(M 1 ⊗ Sν S ν ′ ) + (M 2 ⊗ Sν S ν ′ ).
The organisation of the paper is as follows: in §2, we introduce the rings S ν , and their basic arithmetic and analytic properties. In §3, we generalize some classical results of Iwasawa to the case of finitely generated S ν -modules and then give an algorithm with oracle to compute the maximal module associated to a torsion-free S ν -module and obtain an upper bound on the number of generators of a maximal module. Note that §2 and §3, we only describe algorithms with oracles. In §4, we study the problem of p-adic and u-adic precisions and turn the algorithms with oracles obtained in the previous sections into real algorithms.

Arithmetic of the rings S ν

In order to compute with modules over S ν we first have to study the basic arithmetic properties of their base ring. In this section, we show that its localized with respect to u α /π β and π becomes Euclidean. We provide algorithms with oracles to compute the Euclidean division in these rings which will be very useful for our purpose along with their complexity expressed in term of the number of ring operations. They will be turned into real algorithms (i.e. working on a real Turing machine) in §4 where we study the problem of precision of computation in the rings S ν .

Notations

We fix the notations for the rest of the paper. Let R be a ring equipped with a discrete valuation v R , that is a map v R : R → N ≥0 ∪ {+∞} satisfying the following conditions:

• for all x ∈ R, v R (x) = +∞ if and only if x = 0; • for all x ∈ R, v R (x) = 0 if and only if x is invertible; • for all x, y ∈ R, v R (xy) = v R (x) + v R (y); • for all x, y ∈ R, v R (x + y) ≥ min(v R (x), v R (y)).
Let a be a fixed real number in (0, 1). One can define a distance d on R by the formula d(x, y) = a v R (x-y) (x, y ∈ R) where we use the convention that a +∞ = 0. For the rest of the paper, we assume that R is complete with respect to d. We recall that R is a local ring whose maximal ideal is M = {x ∈ R|v R (x) > 0}. Up to renormalizing v R , it is safe to assume that it is surjective, what we do. We denote by π a uniformizer of R, that is an element of R whose valuation is 1. Every element x in R can then be written x = π r u where r = v R (x) and u ∈ R is invertible. Here are several classical examples of such rings R:

• the ring Z p of p-adic integers equipped with the usual p-adic valuation;

• more generally, the ring of integers of any finite extension of Q p ;

• for any field k, the ring k[[u]] of formal power series with coefficients in k.

We now go back to a general R. It follows easily from the definition that the field of fractions of

R is just R[1/π]. Let's denote it by K and set S = R[[u]
], the ring of formal series over R. The valuation v R can be extended uniquely to a valuation v K on K.

Definition and first properties of S ν

Denote by K[[u]

] the power series ring with coefficients in K. It is classical to define the Gauss valuation of an element

a i u i ∈ K[[u]] as the smallest v K (a i ) if it exists. The ring of elements of K[[u]] with non negative Gauss valuation is nothing but R[[u]].
In this section, we are going to consider more generally a family of valuations parametrized by a slope ν ∈ Q so as to define the subring of K[[u]] of elements with positive valuation. The following lemma gives some basic properties of v ν and deg W . In particular, it shows that v ν has the usual properties of a valuation:

Definition 2.1. Let ν ∈ Q. We define the Gauss valuation v ν : K[[u]] → Q ∪ {+∞, -∞} by v ν (x) = +∞ if x = 0, v ν ( a i u i ) = min{v K (a i ) + νi, i ∈ N} if x = 0 and this minimum exists and v ν (x) = -∞ otherwise. The Weierstrass degree of x denoted deg ν W (x) is given by deg ν W (0) = -∞, deg ν W (x) = min{i|v K (a i ) + νi = v ν (x)} if v ν (x) = -∞
Lemma 2.2. For x, y ∈ K[[u]] we have: 1. v ν (x) = +∞ if and only if x = 0; 2. v ν (x • y) = v ν (x) + v ν (y); 3. v ν (x + y) ≥ min(v ν (x), v ν (y)). Moreover for all x, y ∈ K[[u]] with finite Gauss valuation, deg W (x.y) = deg W (x) + deg W (y).
Proof. To prove 2., we first suppose that x = a i u i and y = b i u i have finite valuation. Let

z = x • y = c i u i . We have v K (c i ) + νi = v K ( i j=0 a j • b i-j ) + νi ≥ min j {v K (a j ) + ν • j + v K (b i-j ) + ν • (i -j)} ≥ v ν (x) + v ν (y). Moreover, by taking i = deg W (x) + deg W (y) in the previous computation, we obtain that v K (c deg W (x)+deg W (y) ) = v ν (x) + v ν (y). If v ν (x) = -∞
and y = 0, we can apply the previous result to the series obtained by truncating x up to a certain power to show that v ν (x • y) = -∞. The proof of the rest of the lemma is left to the reader.

We let S

ν = {x ∈ K[[u]]|v ν (x) ≥ 0}. By definition, an element x ∈ S ν can we written as a series x = i∈N a i u i ,
where a i ∈ K and v K (a i ) ≥ -νi.

Remark 2.3. It is clear that S ν is complete for the valuation v ν . Nonetheless, the ring S ν is not a valuation ring. In fact, although v ν (u α /π β ) = 0 for ν = 0 (resp. v ν (u) = 0 for ν = 0), u α /π β (resp. u) is not invertible in S ν .

We let

S ν,π = S ν [1/π] = i∈N a i u i , a i ∈ K such that v K (a i ) + νi bounded below .
In the same way, it is clear that one can extend the v ν valuation of S ν over S ν [π β /u α ] and we let S ν,u = S ν [π β /u α ] where the hat stands for the completion of S ν [π β /u α ] with respect to the topology defined by v ν . Put in another way,

S ν,u = i∈Z a i u i , a i ∈ S ν and lim i→-∞ v K (a i ) + νi = +∞ .
We moreover define

E = i∈Z a i u i , a i ∈ K v K (a i ) + νi bounded below and lim i→-∞ v K (a i ) + νi = +∞ .
We have the following commutative diagram of inclusions:

Sν,π Sν E Sν,u (1)
As S ν,π is a subring of K[[u]], it is equipped with the v ν valuation and the Weierstrass degree associated to v ν . Moreover, one can extend, in an obvious manner, the definition of v ν and the Weierstrass degree for S ν,u and E .

We can interpret the ring S ν in terms of the analytic functions on the π-adic disc. In order to explain this, for ν ∈ Q, we consider the open disk

D ν = {x ∈ K|v K (x) > ν}. Denote by O ν the ring of convergent series O ν = { i∈N a i u i |a i ∈ K, lim inf i→+∞ vK (ai) i ≥ -ν} in the disk D ν . It is clear that S ν,π is exactly the set {f ∈ K[[u]]| v K (f (x)) bounded below on D ν } and S ν can be described as {f ∈ K[[u]]| v K (f (x)
) bounded below by 0 on D ν }. Thus, there are obvious inclusions S ν ⊂ S ν,π ⊂ O ν but one should beware of the fact that the last inclusion is strict. Indeed for instance, for R = Z p , ν = 0 the series i>0 u i i which defines the function log(1 -u) is convergent in the unity disk but is obviously not in S 0,π since v π (1/i) has no lower bound. Assuming that ν is rational (what we do), the following proposition gives another characterisation of elements of O ν that lies in S ν,π . Proposition 2.4. An element x ∈ O ν is in S ν,π if and only if x has only a finite number of zeros in O ν .

Proof. Let x ∈ O ν . The number of zeros of x ∈ D ν is equal to the length of the interval above which the Newton polygon of x has a slope < -ν. If this length is finite, it is clear that v p (a i ) is bounded below by a line of the form -νi + c with c a constant and as a consequence is an element of S ν,π .

Conversely, suppose that x ∈ S ν,π . This means that v p (a i ) + νi is bounded below and is contained in Z+νZ which is a discrete subgroup of R (as ν is rational). Thus, the set {v p (a i )+νi, i ∈ N } reaches a minimum for a certain index i 0 . This means that for all i > i 0 , the slope of the Newton polygon of x is greater than -ν and x has a finite number of zeros in D ν .

We end up this section, by remarking that up to an extension of the base ring R all the S ν 's are isomorphic to a S 0 . Indeed, write ν = β/α with α, β relatively prime numbers and let ̟, in an algebraic closure of K, be such that ̟ α = π. Let R ′ = R[̟], K ′ be the fraction field of R ′ (and a finite extension of K). The valuation on R extends uniquely on R ′ by setting v K ′ (̟) = 1/α. For µ = 0, ν, let S µ ′ = S µ ⊗ R R ′ . The valuation v K ′ defines a Gauss valuation on S µ ′ that we denote also by v µ . Lemma 2.5. Keeping the notations from above, the morphism of ring ρ : S 0 ′ → S ′ ν , defined by ρ(1) = 1 and ρ(u) = u ̟ β is an isomorphism. Moreover, if x ∈ S 0 ′ we have v 0 (x) = v ν (ρ(x)) and

deg 0 W (x) = deg ν W (ρ(x)). Proof. By definition, S ′ ν = { a i u i |v K ′ (a i ) + νi ≥ 0} = { a i (u/̟ β ) i |v K ′ (a i ) ≥ 0} from
which it is clear that ρ is an isomorphism. The rest of the lemma is an easy verification.

Division in S ν

The Weierstrass degree allows us to describe an Euclidean division in S ν . Although, the existence of such a division is classical (see for instance [START_REF] Lang | Cyclotomic fields[END_REF]) at least over S 0 = R[[u]], we give here a proof for all ν which provides an algorithm with oracles to compute the Euclidean division.

In order to study divisibility in S ν , we have a first result:

Lemma 2.6. Let x, z ∈ S ν . We suppose that deg W (x) = 0 then there exists y ∈ S ν such that x.y = z if and only if v ν (x) ≤ v ν (z).

Proof. We suppose that deg

W (x) = 0. If there exists y ∈ S ν such that x • y = z then clearly v ν (x) ≤ v ν (z). Reciprocally, we suppose that v ν (x) ≤ v ν (z). Write x = i∈N a i u i and z = i∈N c i u i . Since a 0 is invertible in K there exists y ∈ K[[u]] such that x.y = z. We have to prove that v ν (y) ≥ 0. For this, write y = i∈N b i u i . We have v K (b 0 ) = v K (c 0 ) -v K (a 0 ) ≥ 0 by hypothesis. Then, for j ≥ 1, we prove by induction that v K (b j ) + νj ≥ 0. We have b j = a -1 0 • c j -a -1 0 j i=1 a i • b j-i . But v K (a -1 0 • c j ) + νj ≥ v ν (z) -v ν (x) ≥ 0 because deg W (x) = 0. Moreover, for i = 1 . . . j, v K (a -1 0 • a i • b j-i ) + νj = v K (a i ) + νi -v ν (x) + v K (b j-i ) + ν(j -i).
But by definition v K (a i ) + νi -v ν (x) ≥ 0 and by the induction hypothesis v K (b j-i ) + ν(j -i) ≥ 0. Therefore, v K (b j ) + νj ≥ 0 and we are done.

Applying Lemma 2.6 to z = 1, we get Corollary 2.7. Let x = i∈N a i x i ∈ S ν , then x is invertible in S ν if and only if deg W (x) = 0 and v ν (x) = 0.

We note that the corollary implies that S ν is a local ring. Next, we introduce the following notations: for x = i∈N a i u i ∈ S ν and d a positive integer, we let Hi(x, d) = i≥d a i u i and Lo

(x, d) = d-1 i=0 a i u i . It is clear that x = Lo(x, d) + Hi(x, d). Proposition 2.8. Let x, y ∈ S ν . Suppose that v ν (y) ≥ v ν (x) then there exist a unique couple (q, r) ∈ S ν × (K[u] ∩ S ν ) such that deg(r) < deg W (x) and y = q • x + r.
Proof. First, we prove the existance of (q, r). Let d = deg W (x), we consider the sequences (q i ) and (r i ) defined by q 0 = 0 and r 0 = y and

q i+1 = q i + Hi(r i , d) Hi(x, d) , r i+1 = r i - Hi(r i , d) Hi(x, d) • x. (2)
We are going to prove by induction that q i and r i are convergent sequences (for the v ν valuation) of elements of S ν . Let e = v ν (Lo(x, d)) -v ν (Hi(x, d)) > 0. Our induction hypothesis is that q i and r i are elements of S ν , that v ν (Hi(r i , d)) ≥ e • i + v ν (Hi(y, d)) and that y = q i • x + r i . It is clearly true for i = 0.

By the induction hypothesis, we have v ν (Hi(r i , d)) ≥ v ν (Hi(y, d)) and by hypothesis v ν (Hi(y, d)) ≥ v ν (y) ≥ v ν (x) = v ν (Hi(x, d)) so that v ν (Hi(r i , d)) ≥ v ν (Hi(x, d)). Applying Lemma 2.6, we obtain Hi(ri,d) Hi(x,d) ∈ S ν and then q i+1 , r i+1 ∈ S ν . Next writing x = Hi(x, d) + Lo(x, d), we get

r i+1 = Lo(r i , d) - Hi(r i , d) Hi(x, d) • Lo(x, d). (3)
Applying Lemma 2.2, we obtain that v ν (Hi(r i+1 , d))

≥ v ν (Hi(r i , d)) + v ν (Lo(x, d)) -v ν (Hi(x, d)).
Using the induction hypothesis, we get that v ν (Hi(r i+1 , d)) ≥ e • (i + 1) + v ν (Hi(y, d)). Finally, using the hypothesis that y = q i • x + r i , we immediately check using (2) that y = q i+1 • x + r i+1 .

From the induction, we deduce that q i and r i are convergent sequences of S ν for the v ν valuation. In fact, we have q i+1 -q i = Hi (ri,d) Hi(x,d) so that v ν (q i+1 -q

i ) = v ν (Hi(r i , d)) -v ν (Hi(x, d)) ≥ e • i + v ν (Hi(y, d)) -v ν (Hi(x, d)) ≥ e • i.
The same argument works for r i . Denote by q and r the limits. As for all i ∈ N, y = q i • x + r i , we have y = q • x + r. Moreover, since Hi(r i , d) ≥ e • i, we have Hi(r, d) = 0, so that r ∈ K[u] and deg(r) < deg W (x).

We prove the unicity of (q, r).

Let (q ′ , r ′ ) ∈ S ν × (K[u] ∩ S ν ) such that y = q ′ • x + r ′ . Then (q -q ′ ) • x = r ′ -r. We have deg W ((q -q ′ ) • x) = deg W (r ′ -r) < deg W (x) which is only possible if q = q ′ and r = r ′ .
From the proof of Proposition 2.8, we deduce Algorithm 1 to compute from the knowledge of x, y, the elements q ′ , r ′ ∈ S ν such that v ν (q -q ′ ) ≥ prec and v ν (r -r ′ ) ≥ prec. Furthermore, by the proof of the proposition, the number of iterations of the while loop is bounded by ⌈prec/e⌉. We deduce that Algorithm 1 needs one inversion and 3 • ⌈prec/e⌉ multiplications in S ν .

Algorithm 1: EuclieanDivision input : x, y ∈ S ν with v ν (y) ≥ v ν (x), prec ∈ N output : q, r ∈ S ν such that y = q • x + r and v ν (Hi(r, deg W (x))) ≥ prec 1 q ← 0; 2 r ← y; 3 d ← deg W (x); 4 while v ν (Hi(r, d)) < prec do 5 q ← q + Hi(r,d) Hi(x,d) ; 6 r ← r -Hi(r,d)
Hi(x,d) • x; 7 return q, r; Now, let x ∈ S ν , following [START_REF] Lang | Cyclotomic fields[END_REF] we say that x is distinguished if v ν (x) = 0. With this definition, we can state the classical Weierstrass preparation theorem: Corollary 2.9 (Weierstrass preparation). Let x ∈ S ν be a distinguished element and let d = deg W (x). Then we can write x = q • h, where q ∈ S ν is an invertible element and h

∈ K[u] ∩ S ν is of the form h = u d π ν•d + d-1 i=0 b i u i with v K (b i ) + νi > 0.
Proof. We first notice that dν is a nonnegative integer. Indeed, it is clearly nonnegative, and writing x = a d u d , we have v R (a d ) + dν = 0 (since x is assumed to be distinguished) and, consequently,

dν = -v R (a d ) ∈ Z.
By proposition 2.8, there exist q ∈ S ν and r ∈ K[u] ∩ S ν such that deg r < d and

u d π d•ν = q • x + r.
Using Lemma 2.2, we obtain v ν (q) = 0 and deg W (q) = 0. Then, Corollary 2.7 implies that q is invertible. To finish the proof it suffices to remark that deg W ( u d π d•ν -r) = d and the result follows from the definition of deg W .

Remark 2.10. The previous proposition is closely related to the Proposition 2.4 since it says that an element of O ν is in S ν,π if and only if it can be written as product of a polynomial times a function which does not have any zero in D ν .

The following proposition states that the rings S ν,π and S ν,u are Euclidean rings and provides algorithms with oracles to compute the division.

Proposition 2.11. The ring S ν,π is Euclidean, the ring S ν,u is a discrete valuation ring for the valuation v ν (and as a consequence is also Euclidean). Moreover, E is a field.

Proof. Let x, y ∈ S ν,π . There exist s, t ∈ N such that π s x, π t y ∈ S ν and v ν (π t • y) ≥ v ν (π s • x). Applying Proposition 2.8, yields q ∈ S ν and r ∈ K[[u]] ∩ S ν such that deg(r) < deg W (x) and y = π s-t • q • x + π -t • r and we are done.

In order to prove that S ν,u is a discrete valuation ring, we have to show that the set of invertible elements of S ν,u is the set of elements x ∈ S ν,u such that v ν (x) = 0. Write ν = β/α, with α, β relatively prime numbers. Let m be the ideal defined by {x ∈ S ν,u , v ν (x) > 0}, it is clear that S ν,u /m is isomorphic to the field k((u α )). As S ν,u is complete for the v ν valuation, the Hensel lift algorithm gives an algorithm with oracles to compute the inverse of an element whose valuation is zero. The Algorithm 2 uses a fast Newton iteration to perform this computation modulo m n at the expense of O(log(n)) multiplications in S ν,u .

Let x be a non zero element of E , by dividing it by a power of π we can suppose that v ν (x) = 0 and by using the algorithm with oracle Algorithm 2, we can invert it.

Algorithm 2: Inverse input : x ∈ S ν,u such that v ν (x) = 0, n ∈ N output : y ∈ S ν,u such that x • y = 1 mod m n 1 if n = 1 then 2 y ← 1/x mod m; 3 else 4 y ← Inverse(x, ⌈n/2⌉); 5 y ← y + y(1 -ay) mod m n ;
Remark 2.12. One can use the usual Euclidean algorithm to compute the Bézout coefficients of x, y ∈ S ν,π . This algorithm outputs g, k, l, m, n ∈ S ν,π such that g is the greatest common divisor of x and y, k

• x + l • y = g, m • x + n • y = 0 and k • n -l • m = 1.
It proceeds by using the fact that gcd(x, y) = gcd(y, r) where r is the rest of the division of x by y and uses O(deg W (y)) calls to the Euclidean division Algorithm 1. We remark, as the rest of the division of two elements of S ν is an element of K[u], that starting from the second iteration of this algorithm all the divisions to be computed are the usual division between elements of K[u]. Unfortunately, we will see that in §4, that the Euclidean algorithm in general is not stable, so that we might need extra informations, about x and y in order to compute an approximation of their gcd from the knowledge of an approximation of x and an approximation of y.

Modules over S ν

Let d be a positive integer and fix ν ∈ Q. We want to compute with finitely generated torsion free S ν -modules. Any such module M can be embedded in S d ν for d ∈ N and can be represented by a matrix with coefficients in S ν whose column vectors are the coordinates of generators of M in the canonical basis of S d ν . Indeed, we can always embed M is M ⊗ Sν Frac(S ν ) and select a basis (e 1 , . . . , e d ) of M ⊗ Sν Frac(S ν ) together with an element D ∈ S ν such that the image of M in M ⊗ Sν Frac(S ν ) is contained in the free S ν -module generated by the 1 D .e i 's. A first problem arises here: it is not possible to bound the number of generators of the submodules of S d ν that we have to compute with. For instance, for d = 1 and ν = 0, choose a positive integer k and consider the sub-S 0 -module M k of S 0 generated by the family (π k-j u j ) j=0,...,k . Then M k can not be generated by less than k + 1 elements. Indeed, let (e 0 , . . . , e n ) ∈ S n 0 be a family of generators of M k , and for j ≥ 0 and define a filtration on M k by letting F j M k = M k ∩ u j S 0 . We are going to prove by induction on t ∈ {0, . . . , k} that there exists a matrix M t ∈ M n×n (S 0 ) such that, if we set (e ′ 0 , . . . , e ′ n ) = (e 0 , . . . , e n ) • M t then (e ′ 0 , . . . , e ′ n ) is a family of generators of M k , for j < t, e ′ j = u j π k-j mod F j+1 M k and (e ′ j ) j≥t is a family of generators of F t M k . This is obviously true for t = 0. Suppose that it is true for t 0 ∈ {0, . . . , k}. Let (e ′ 0 , . . . , e ′ n ) = (e 0 , . . . , e n ) • M t0 . As the morphism (

k j=t0 S 0 e ′ j )/F t0+1 M k → π k-t R, defined by u t0 a i u i → a 0 is an isomorphism, we can suppose if necessary by renumbering the family (e ′ i ) that e ′ t0 = u t0 π k-t0 mod F t0+1 M k .
Then, by considering linear combinations of the form e ′ j -λe ′ t0+1 for λ ∈ S 0 for j > t 0 , one can obtain a matrix M t0+1 satisfying the induction hypothesis for t 0 + 1. Finally, we get n ≥ k.

A second problem comes from the fact that there is no unique way to represent a module by a set of generators. For computational purpose, in order to check equality between modules for instance, it is important to have a canonical representation, that is a bijective correspondence between mathematical objects and data structures. An example of such a canonical representation exists for finitely generated modules with coefficients in an Euclidean ring ( [START_REF] Cohen | A course in computational algebraic number theory[END_REF]): it is the so-called Hermite Normal Form (HNF). It is given by a triangular matrix (with some extra conditions) that can be computed from an initial matrix M by doing operations on column vectors of M . Even if S ν is not Euclidean, we could have hoped that such representations still exist for free modules. Unfortunately, it turns out that it is not the case. Indeed, in general, there does not even exist a triangular matrix form for matrices over S ν . For instance, for ν = 0, take:

M = u π π u ∈ M 2×2 (S 0 )
and assume that M can be written as a product LP where L is lower-triangular and P is invertible. Let α and β be the diagonal entries of L. Then, α and β belong to the maximal ideal of S 0 (since the coefficients of M all belong to this ideal) and the product αβ is equal to a unit times u 2 -π 2 . Hence, by multiplying β by an invertible element in S 0 if necessary, we can assume that β = u ± π since S 0 is a unique factorisation domain. On the other hand, by hypothesis, there exist a, b ∈ S 0 such that ua + πb = 0 and πa + ub = β. This equality implies that π divides a and therefore that β = πa + ub ∈ uS 0 + π 2 S 0 . This is a contradiction.

In this section, we explain how to get around these problems. First, we recall the notion of quasi-isomorphism and study the localisation of the modules with respect to π or u α /π β in order to obtain canonical representations well suited for the computation in the category of modules up to quasi-isomorphism. Then, we describe a generalisation of an algorithm of Cohen to compute the maximal module associated to a given torsion-free S ν -module and obtain a bound on the number of generators of a maximal S ν -module. We explain how to combine the different approaches in order to obtain a comprehensive algorithmic toolbox for modules over S ν .

Quasi-isomorphism and maximal modules

In order to be able to control the number of generators of a S ν -module, we are going to compute up to finite modules which will be considered as "negligible". Definition 3.1. A finitely generated S ν -module is said to be finite if it has finite length. Let M and M ′ be two finitely generated S ν -modules, let f : M → M ′ be a S ν -linear morphism. We say that f is a quasi-isomorphism if its kernel and its co-kernel are finite modules. Remark 3.2. Since ker f and coker f are finitely generated (because S ν is a noetherian ring), it is easy to check that they have finite length if and only if they are canceled, at the same time, by a distinguished element of S ν and a power of π. A quasi-isomorphism between torsion-free modules is always injective. Indeed, its kernel, being a submodule annihilated by a power of u α /π β and π of a torsion free module, is zero.

Example 3.3. Let M be the submodule of S 0 generated by (π 2 , πu 3 ). The inclusion M ⊂ πS 0 yields an injective morphism whose is annihilated by π and u 3 . As a consequence M is quasiisomorphic to the free module π.S 0 (see figure 2).

We have a canonical representative in a class of quasi-isomorphism which is given by the following definition. Definition 3.4. Let M be a torsion-free finitely generated S ν -module. We say that M ′ together with a quasi-isomorphism f : M → M ′ is maximal for M if for every N , torsion-free S ν -module, and quasi-isomorphism f ′ : M → N , there exists a morphism g : N → M ′ which makes the following diagram commutative:

π u u 3 π 2 Figure 2: The module M is quasi-isomorphic to π • S 0 . M M ′ N f f ′ g (4)
The morphism g in the definition is unique and is in fact a quasi-isomorphism. Indeed, by the commutativity of the diagram, the image of g contains the image of f . Thus, the cokernel of g is finite. Moreover, since f is injective, g is injective on Imf ′ , which is cofinite in N . It follows that ker g is finite and g is a quasi-isomorphism. Moreover, for every x ∈ N , there exists a positive integer n such that π n x is in the image of f ′ . The image of π n x by g is then uniquely defined by the commutativity of the diagram (4). The uniqueness of g follows.

A maximal module for M , if it exists, is unique up to isomorphism. Indeed, if M ′ and M ′′ are two maximal modules for M then there exist two quasi-isomorphisms g 1 : M ′ → M ′′ and g 2 : M ′′ → M ′ and the uniqueness of g in the diagram (4) implies that

g 1 • g 2 = Id M ′′ and g 2 • g 1 = Id M ′ .
If it exists, we denote the maximal module of M by Max(M ). We can rephrase the above by saying that if M ′ is the maximal module for M then there is a quasi-isomorphism from M into M ′ and any quasi-isomorphism M ′ → M ′′ is an isomorphism. In fact, this condition characterises maximal modules: Lemma 3.5. Let M be a finitely generated torsion free S ν -module. Let M ′ be a S ν -module such that there is a quasi-isomorphism f : M → M ′ . The following assertions are equivalent:

1. M ′ is maximal; 2. any quasi-isomorphism M ′ → M ′′ is an isomorphism.
Proof. We only have to prove that the second property implies that M ′ verifies the universal property of maximal modules. For this let N be a finite type S ν -module such that there is a quasi-isomorphism

f ′ : M → N . Let ∆ = f ⊕ f ′ : M → M ′ ⊕ N be the diagonal embedding and let M 0 = M ′ ⊕N ∆(M )
. It is clear that M 0 is a finitely generated torsion free S ν -module. There are canonical injections i M ′ : M ′ → M 0 and i N : N → M 0 . We claim that i M ′ and i N are quasi-isomorphisms. To see that, it suffices to show that the induced injection i

M = (i M ′ , i N ) • ∆ : M → M 0 has a finite cokernel. But coker i M = coker f ⊕ coker f ′ ∆(M ) ∩ (coker f ⊕ coker f ′ ) which has finite length being a quotient of coker f ⊕ coker f ′ .
Next, by hypothesis i M ′ is in fact an isomorphism so that we have a quasi-isomorphism g = i -1 M ′ • i N which sits in the following diagram:

M ′ M ′ ⊕N ∆(M) M N i N i M ′ f f ′ g (5)
It is clear that the lower left triangle of the diagram is commutative and we are done.

A theorem of Iwasawa [START_REF] Iwasawa | On Γ-extensions of algebraic number fields[END_REF] asserts that if M is a finitely generated module over S 0 , then Max(M ) exists and is free of finite rank over S 0 . The main object of §3.3 is to extend this result to modules over S ν : we shall provide a constructive proof of the existence of Max(M ) for any finitely generated torsion-free module M over S ν . We will see however that this Max(M ) is not free in general; nevertheless we shall provide an upper bound on the number of generators of Max(M ). Lemma 3.6. Let f : M → M ′ be a quasi-isomorphism between torsion-free finitely generated S ν -modules. Suppose that M ′ is free then M ′ is maximal.

Proof. We use the criterion of Lemma 3.5. Let N be a finitely generated S ν -module such that there is a quasi-isomorphism f ′ : M ′ → N and we want to show that f ′ is an isomorphism. As M ′ is torsion-free, we know that f ′ is injective. Now, suppose that there exists a non zero element in the cokernel of f ′ . It means that there exists a non zero x ∈ N which is not in the image of f ′ . As f ′ is a quasi-isomorphism there exists n ∈ N and λ ∈ S ν a distinguished element with

π n • x ∈ Imf ′ and λ • x ∈ Imf ′ . If we set z 1 = f ′ -1 (π n • x) and z 2 = f ′ -1 (λ • x), we have the relation λz 1 -π n z 2 = 0, (6)
in M ′ . Let (e i ) i∈I be a basis of M ′ and write z i = µ j i e j for i = 1, 2. Putting this in [START_REF] Coppersmith | Matrix multiplication via arithmetic progressions[END_REF], we obtain that λµ j 1 = π n µ j 2 and thus π n |µ j 1 for j ∈ I since λ is a distinguished element of S ν . But then f ′ ( µ j 1 /π n e j ) = 1/π n .f (z 1 ) = x contradicting the fact that x is not in the image of f ′ . Remark 3.7. One can rephrase Iwasawa's result in a more abstract way using the category language. Let Mod Sν be the category of finitely generated S ν -modules, that are torsion-free and let Mod tf Sν (resp. Free Sν ) denote its full subcategory gathering all torsion-free modules (resp. all free modules). We also introduce the category Mod qis Sν , which is by definition the category of finitely generated S ν -modules up to quasi-isomorphism, i.e. Mod qis Sν is obtained from Mod Sν by inverting formally quasi-isomorphisms. We have a natural functor Mod Sν → Mod qis Sν , whose restriction to Mod tf Sν defines a pylonet in the sense of [START_REF] Caruso | F p -représentations semi-stables[END_REF], §1. It follows from the results of loc. cit (see Corollary 1.2.2) that the Max construction is a functor: to a morphism f : M → M ′ in Mod tf Sν , one can attach a morphism Max(f ) : Max(M ) → Max(M ′ ). We recall briefly the construction of Max(f ). Let M ′′ be the pushout M ′ ⊕ M Max(M ), that is the direct sum M ′ ⊕ Max(M ) divided by M (embedded diagonally). We have a natural morphism M ′ → M ′′ which turns out to be a quasiisomorphism. Hence, there exists a map M ′′ → Max(M ′ ) and we finally define Max(M ) to be the compositum Max(M ) → M ′′ → Max(M ′ ) where the first map comes from the natural embedding

Max(M ) → M ′ ⊕ Max(M ).
If M is a submodule of S d ν (for some positive integer d), the following proposition gives a very explicit description of Max(M ). Proposition 3.8. Write ν = β/α, with α, β relatively prime integers. Let d be a positive integer and M be a submodule of S d ν . Then Max(M ) exists and

Max(M ) = x ∈ S d ν | ∃n ∈ N, π n x ∈ M and (u α /π β ) n • x ∈ M . Furthermore the morphism i M : M → Max(M ) is the natural embedding.
Proof. Let M max be the set of x ∈ S d ν such that there exists some n such that π n x and (u α /π β ) n • x belong to M . We want to show that Max(M ) exists and is equal to M max . It is clear that M ⊂ M max and that the quotient M max /M is canceled by a power of π and a power of u α /π β which is a distinguished element. Hence it has finite length, and the inclusion M → M max is a quasi-isomorphism. Next, suppose that we are given a S ν -module M 0 together with a quasiisomorphism g : M max → M 0 . Then there is a quasi-isomorphism i M : M → M 0 that sits in the following diagram:

M Mmax S d ν M0 i M g (7)
Note that g is injective as it is a quasi-isomorphism. Moreover, we know that the cokernel of ι M is annihilated by a power of u α /π β and a power of π, which implies that g is surjective. Thus, g is an isomorphism and by Lemma 3.5, Max(M ) exists and Max(M ) = M max as claimed. The second part of the proposition is clear from the above diagram.

It follows directly from Proposition 3.8 that the intersection of two maximal modules is maximal. The same is however not true for the sum: in general the S ν -module M + M ′ is not maximal even if M and M ′ are (take for example M = uS 0 and M ′ = πS 0 ). This leads us to define the new operation + max (which is much more pleasant than the usual sum of modules) on the set of maximal submodules of S d ν as follows:

M + max M ′ = Max(M + M ′ ).
We also deduce from Proposition 3.8 that a S 0 -module M is free if and only if M = M max . This gives a nice criterion to check if a S 0 -module is free. It is not true in general for a sub-S νmodule M of S d ν that Max(M ) is free (this will become apparent when we give the general shape of a maximal S ν -module in §3.3). However, by Lemma 2.5, every S ν becomes isomorphic to S 0 over a finite extension ν verifying the condition of Proposition 3.9. Proof. In order to prove that Φ is injective, it is enough to prove that Φ has a left inverse. For this, let M ∈ Max d Sν and let

R ′ = R[̟] (where ̟ depends on ν). Set S ′ ν = S ν ⊗ R R ′ .
Φ : Max d Sν -→ Free d S ′ ν M → Max(M ⊗ Sν S ′ ν ) is injective. A left inverse of Φ is given by M ′ → M ′ ∩ S d ν .
M ′ = Max(M ⊗ Sν S ′ ν ) ∈ Free d S ′
ν . Then it suffices to prove that

M 2 = M ′ ∩ S d ν is a maximal sub-S ν -module of S d ν .
Indeed, as it is clear that M 2 contains M and that the injection M → M 2 is a quasi-isomorphism since the injection M → M ′ is a quasiisomorphism, we remark that by the maximality of M it would imply that M = M 2 .

For this let x ∈ S d ν and suppose that there exists n ∈ N such that

π n •x ∈ M 2 and (u α /π β ) n •x ∈ M 2 . As M ′ is maximal and M 2 ⊂ M ′ , by Proposition 3.8, it means that x ∈ M ′ . hence x ∈ M 2 .
Using again Proposition 3.8, we deduce that M 2 is maximal.

Let us now prove the last claim of the proposition. Let

M ′ ∈ Free d S ′
ν which admits a basis (e i ) i∈I where e i ∈ (S ′ ν ) d and e i = ̟ αi e ′ i with e ′ i ∈ (S ν ) d and α i ∈ N. We have to find a sub-S νmodule

M of S d ν such that M ⊗ Sν S ′ ν is quasi-isomorphic to M ′ . As M ′ = e i S ′
ν , it is enough to treat the case d = 1. Let 0 ≤ α 1 be an integer and let M ′ be the sub-S ′ ν -module of S ′ ν generated by ̟ α1 . Let λ be a positive integer such that α1 α + λ β α = γ ∈ Z. Such a λ exists because α and β are relatively prime. Let M be the sub-S ν -module of S ν generated by π and

u λ π γ . Let µ = ̟ -α1 u λ π γ , it is clear that v ν (µ) = 0 so that µ is a distinguished element of S ′ ν . Thus, we have ̟ α1 .µ ∈ M ⊗ Sν S ′ ν and ̟ α1 • ̟ α-α1 ∈ M ⊗ Sν S ′ ν therefore M ⊗ Sν S ′ ν is quasi-isomorphic to M ′ .

An approach based on localisation

We have seen that in a class of quasi-isomorphism of a finite type torsion-free S ν -module M there exists a distinguished element Max(M ). In this section, we use this fact in order to represent the quasi-isomorphism class of M by localizing with respect to u α /π β and π. We thus obtain a representation of finite type torsion-free S ν -modules amenable to computations.

A useful bijection

We keep our fixed positive integer d. We recall that

E = i∈Z a i u i , a i ∈ K, v K (a i ) + νi bounded below and lim i→-∞ v K (a i ) + νi = +∞
Ψ ′ : Free d S -→ Free d Sπ × Free d Su M → (M π , M u ).
is injective. If a pair (A, B) is in the image of Ψ ′ , its unique preimage under Ψ ′ is given by A ∩ B.

Proof. From the descriptions of elements of S, S π , S u and E in terms of series, it follows that

S = S π ∩ S u . If M ∈ Free d S ,
it is isomorphic to S h for h ≤ d and, by applying the preceding remark component by component, we get M = M π ∩ M u . This implies the injectivity of Ψ ′ and the given formula for its left-inverse.

Using Lemma 3.11, we can prove: Theorem 3.12. The natural map

Ψ : Max d Sν -→ Free d Sν,π × Free d Sν,u M → (M π , M u ).
is injective and its image consists of pairs (A, B) such that A and B generate the same E -vector space in E d . If a pair (A, B) satisfies this condition, its unique preimage under Ψ is given by A∩B. Furthermore, we have the following equalities:

Ψ(M ∩ M ′ ) = (M π ∩ M ′ π , M u ∩ M ′ u ) Ψ(M + max M ′ ) = (M π + M ′ π , M u + M ′ u ) for all M , M ′ ∈ Max d Sν . Proof. Let ̟ in an algebraic closure of K, be such that ̟ α = π. Let R ′ = R[̟] and S ′ ν = S ν ⊗ R R ′ . We know by Lemma 2.5 that S ′ ν is isomorphic to R ′ [[u]].
Then, the map Ψ sits in the following commutative diagram:

Max d Sν Free d Sν,π × Free d Sν,u Free S ′ ν Free d S ′ ν,π × Free d S ′ ν,u Ψ Max(. ⊗S ν S ′ ν ) . ⊗S ν S ′ ν Ψ ′ (8)
By Proposition 3.9, the map M → Max(M ⊗ Sν S ′ ν ) is injective and Ψ ′ is injective by Lemma 3.11, from which we deduce that Ψ is injective by the commutativity of [START_REF] Iwasawa | On Γ-extensions of algebraic number fields[END_REF].

We want to prove now that if the pair (A, B) belongs to Free d Sν,π × Free d Sν,u and satisfies the condition of the theorem, then M = A ∩ B is maximal over S ν and Ψ(M ) = (A, B). We claim that there exists a basis (e 1 , . . . , e h ) of A (over S ν,π ) such that M is included inside the S ν -module generated by the e i 's. Indeed, let us first consider (e 1 , . . . , e h ) a basis of A and denote by M ′ the S ν -module generated by the e i 's. Now, remark that, by our assumption on the pair (A, B), every element x ∈ B can be written as a E -linear combination of the e i 's. Taking for n the smallest valuation of the coefficients appearing in this writing, we get x ∈ π -n M ′ u . Moreover, since B is finitely generated over S ν,u , we can choose a uniform n. Replacing e i by π -n e ′ i for all i, we then get

A = M ′ π and B ⊂ M ′ u . Thus M = A ∩ B ⊂ M ′ π ∩ M ′ u = M ′ .
Since S ν is a noetherian ring (recall that ν is rational), we find that M is finitely generated over S ν . Furthermore, one can compute Max(M ) using Proposition 3.8: if x is an element of S d ν for which there exists n such that π n x and (u α /π β ) n x belong to M , then x ∈ A (since π is invertible in S ν,π ) and x ∈ B (since u α /π β is invertible in S ν,u ). Thus x ∈ M and Max(M ) = M , i.e. M is maximal.

Let us prove now that Ψ(M ) = (A, B). By the same argument as before, we find that there exists a positive integer n such that

π n M ′ ⊂ M ⊂ M ′ , from what it follows that M π = M ′ π = A.
The method to prove that M u = B is analogous: we first show that there exists a basis (e 1 , . . . , e h ) of B over S ν,u and some elements s 1 , . . . , s h ∈ S ν such that:

• all s i 's are invertible in S ν,u , and

• we have s i e i S ν ⊂ M ⊂ e i S ν .
From these conditions, it follows that M u is generated by the e i 's over S u and, consequently, that

M u = B.
It remains to prove the claimed formulas concerning intersections and sums. For the intersection, we note that if

M ∩ M ′ = (M π ∩ M u ) ∩ (M ′ π ∩ M ′ u ) = (M π ∩ M ′ π ) ∩ (M u ∩ M ′ u )
. Hence, we just need to justify that M π ∩ M ′ π and M u ∩ M ′ u are free over S ν,π and S ν,u respectively, and that they generate the same E -vector space. The freedom follows from the classification theorem of finitely generated modules over principal rings, whereas the second property is a consequence of the flatness of E over S ν,π and S ν,u .

For the sum, we have to justify that (M

+ max M ′ ) π = M π +M ′ π and (M + max M ′ ) u = M u +M ′ u . It is clear that (M + M ′ ) π = M π + M ′ π and (M + M ′ ) u = M u + M ′ u .
Hence, it is enough to prove that, given a finitely generated S ν -module N ∈ S d ν , we have Max(N ) π = N π and Max(N ) u = N u . It is obvious by Proposition 3.8.

Reinterpretation in the language of categories We introduce the "fiber product" category Free Sν,π ⊗ Free E Free Sν,u whose objects are triples (A, B, f ) where A ∈ Free Sν,π , B ∈ Free Sν,u and f : E ⊗ Sν,π A → E ⊗ Sν,u B is an E -linear isomorphism. We have natural functors in both directions between Max Sν and Free Sν,π ⊗ Free E Free Sν,u : to an object M of Max d Sν , we associate the triple (S ν,π ⊗ S M , S ν,u ⊗ S M , f ) where f is the canonical isomorphism, and conversely, to a triple (M π , M u , f ), we associate the fiber product of the following diagram (which turns out to be free of finite rank over S ν ):

Mu Mπ E ⊗S ν,π Mπ E ⊗S ν,u Mu (9)
Theorem 3.12 then says that these two functors are equivalences of categories inverse one to the other. Actually, this result can be generalized to non-free modules as follows.

Proposition 3.13. The functor

Mod Sν → Mod Sν,π ⊗ Mod E Mod Sν,u , M → (S ν,π ⊗ S M , S ν,u ⊗ S M ) factors through Mod qis
Sν and the resulting functor

Mod qis Sν → Mod Sν,π ⊗ Mod E Mod Sν,u
is an equivalence of categories.

Proof. Left to the reader.

Normal forms for modules over S ν,π and S ν,u

As S ν,π and S ν,u are Euclidean rings there exists a good notion of rank as well as Hermite Normal Forms for matrix over these rings. In this section, we state propositions giving the shape of Hermite Normal Form together with algorithms with oracles to compute them. We recall that an algorithm with oracle is a Turing machine which has access to oracles to store elements of the base ring and perform all usual ring operations: test equality, computation of the valuation, addition, opposite, multiplication and Euclidean division. We will measure the time complexity of the algorithms by counting the number of calls to the oracles. Classically, we then derive some consequences which will be used in this paper. For the complexity analysis, we denote by θ a real number such that product of two d × d matrices with coefficient in S ν can be done in O(d θ ) ring operations. With a naive algorithm, we can take θ = 3 and with the current best known algorithm of Coppersmith and Winograd [START_REF] Coppersmith | Matrix multiplication via arithmetic progressions[END_REF], θ = 2.376.

Proposition 3.14. Let M = (m ij ) ∈ M d×d ′ (S ν,π
), let r be the rank of M . Then, there exists an invertible matrix P such that M.P = T with

T = t 1 0 0 ⋆ t r ⋆ ⋆ ⋆ 0 0                   , (10)
where

• for i = 1, . . . , r, t i = u dj + dj-1 i=0 b j u j with v K (b j ) + ν(j -d j ) > 0 ; • for i = 1, . . . ,
r, T l(i),i = t i and l is a scrictly increasing function from {1, . . . r} to {1, . . . , d} such that l(1) = 1.

The matrix T is said to be an echelon form of M . Let d max be the maximal Weierstrass degree of the entries of M , an echelon form of M can be computed in

O(d•d ′ •d max +max(d θ •d ′ , d ′θ •d) log(2d ′ /d))
ring operations If the echelon form moreover satisfies:

• all entries on the l(i) th -row are elements of K[u] of degree < d i .

then T is unique with these properties and is called the Hermite Normal Form. The Hermite Normal form of M can be computed from an echelon form of M at the expense of an additional O(r 2 ) ring operations.

Proposition 3.15. Let M ∈ M d×d ′ (S ν,u ), let r be the rank of M . Then there exists an invertible matrix P such that M.P = T and

T = π d1 0 0 ⋆ π dr ⋆ ⋆ ⋆ 0 0                   , (11)
where

• for i = 1, . . . , r, T l(i),i = π di where l is a strictly increasing function from {1, . . . r} to {1, . . . , d} such that l(1) = 1.

The matrix T is said to be an echelon form of M . An echelon form of M can be computed in

O(d.d ′ ) + max(d θ • d ′ , d ′θ • d) log(2d ′ /d)) ring operations.
If the echelon form moreover satisfies

• the entries on the l(i) th -row are representatives modulo π di .

then T is unique with these properties and the called the Hermite Normal Form of M . The Hermite Normal form of M can be computed at the expense of an additional O(r 2 ) ring operations.

Proof. The proof of the previous propositions as well as algorithms to compute the echelon form of M with the given complexity is an immediate consequence of [ ) is a full rank matrix then there exists an invertible matrix P such that M • P has the form [START_REF] Von | Modern computer algebra[END_REF] with all entries defined modulo π max{d1,...,dr} .

Let S ν,loc be S ν,u or S ν,π . We derive some consequences of the existence of triangle forms and Hermite Normal Form for the representation and computation with finitely generated sub-S ν,locmodules of S d ν,loc . We can represent a finitely generated sub-S ν,loc -module M of S d ν,loc by a d × d matrix M giving d generators of M in the canonical basis of S d ν,loc since every sub-module of S d ν,loc has dimension at most d. Keeping the same notations, one can compute the module of syzygies of M . For this it is enough to compute R, a matrix of maximal rank such that M • R = 0 which can easily be done by computing an echelon form of M . Given a vector V ∈ S d ν,loc provided by its coordinates vector V in the canonical basis, one can check efficiently if V ∈ M by finding a vector X such that M.X = V which can also be done with the echelon form of M .

Let M and M ′ representing the modules M and M ′ , one can compute a matrix representing the module M + M ′ by computing the echelon form of the matrix (M M ′ ) and taking the d first columns. One can compute the intersection of M and M ′ in the same way by finding R and R ′ such that (M M ′ ) R R ′ = 0.

Consequences for algorithmics

In view of the results of §3.2.1 and §3.2.2, we shall represent a maximal S ν -module M living in some S d ν as a pair (A, B) where A (resp. B) is the matrix with coefficients in S ν,π (resp. in S ν,u ) in Hermite Normal Form representing S ν,π ⊗ Sν M (resp. S ν,u ⊗ Sν M ).

The second part of Theorem 3.12 tells us that it is very easy to compute intersections and "maximal-sums" of S ν -modules with this representation. Indeed, we just have to perform the same operations on each component, and we have already explained in §3.2.2 how to do it efficiently. As the Hermite Normal Form is unique, it is also very easy to check the equality of two maximal sub-S ν -modules of S d ν . Using only the echelon form of the matrices A and B it is also possible to test membership.

Even better, this representation is also very convenient for many other operations we would like to perform on S ν -modules. Below we detail three of them. First, let M ⊂ S d ν be a maximal S ν -module. By definition, the saturation of M in S d ν is the module

M sat = x ∈ S d ν | ∃n ∈ N, π n x ∈ M .
It follows from Proposition 3.8 that M sat is maximal over S ν , and we would like to compute it. For that, working with our representation, we need to compute (M sat ) π and (M sat ) u . But, we have

(M sat ) π = M π and (M sat ) u = x ∈ S d ν,u | ∃n ∈ N, π n x ∈ M u .
The computation of (M sat ) π is then for free, whereas the computation of (M sat ) u can be achieved using Smith forms, which is here quite efficient due to the fact that S ν,u is a discrete valuation ring. An important special case is when M has rank d over S ν . Then (M sat ) u is always equal to S d ν,u . Thus, in this case, if M is represented by the pair of matrices (A, B), then M sat is just represented by the pair (A, I) where I is the identity matrix.

More generally, one can consider the following situation. Let M ∈ Max d Sν and M ′ ∈ Max d Sν,π . We want to compute M ∩M ′ , which is a maximal module over S ν . As before, we need to determine (M ∩ M ′ ) π and (M ∩ M ′ ) u and one can check that:

(M ∩ M ′ ) π = M π ∩ M ′ π (M ∩ M ′ ) u = M u ∩ M ′ u .
Note that, here, M ′ u is vector space over E . As before, the intersection M u ∩ M ′ u can be computed using Smith forms and, if M ′ has rank d over S ν,π , we just have M ′ u = E d and so (M ∩M ′ ) u = M u . The third example we would like to present is obtained from the previous one by inverting the roles of S ν,π and S ν,u : we take M ∈ Free d Sν and M ′ ∈ Free d Sν,u and we want to compute M ∩ M ′ . We then have

(M ∩ M ′ ) π = M π ∩ M ′ π and (M ∩ M ′ ) u = M u ∩ M ′ .
Here a new difficulty occurs: M ′ π is a E -vector space and so, in previous formulas, it appears an intersection between a free module over S ν,π and a E -vector space. Again, one can compute this Smith form. However, it is not so efficient as before since S ν,π is just an Euclidean ring, and not a discrete valuation ring. Anyway, it remains true that, in the case where M ′ has full rank, then M ′ π = E d . So, in this case, (M ∩ M ′ ) π is just equal to M π and the computation of (M ∩ M ′ ) π becomes very easy.

Further localisations

We remark that the matrix appearing in Proposition 3.15 has coefficients in S ν,u which is a discrete valuation ring while the matrix of Proposition 3.14 has coefficients in S ν,π which is only Euclidean. For certain applications, it can be more convenient to compute with elements in a discrete valuation ring; for instance, the computation of the Smith Normal Form can be made faster in a discrete valuation ring.

It is actually possible to work only over discrete valuation rings by localising further. More precisely, for any element a ∈ K (where K is an algebraic closure K of K) with valuation > ν, we have a canonical injective morphism S ν,π → K[[u -a]] which maps a series to its Taylor expansion at a. Hence, if M p is a sub-S ν,π -module of S d ν,π , one can consider

M p,a = M p ⊗ Sν,π K[[u -a]] ⊂ K[[u -a]] d
for all element a as before. Moreover, if M p has maximal rank, all M p,a 's are trivial (i.e. equal to K[[u -a]]) expect a finite number of them (which are those for which a is a root of one of the t i 's of Proposition 3.14). In addition, the map:

Ξ : Mod d Sν,π -→ a∈R Mod d K[[u-a]] M p → (M p,a ) a
is injective and commutes with sums and intersections. Hence, one can substitute to M p , the (finite) family consisting of all non trivial M p,a 's. This way, we just have to work with modules defined over discrete valuation rings. Note finally that there exist algorithms to compute one representation from the other. Indeed, remark first that computing the image of M p by Ξ is trivial if M p is represented by a matrix of generators: it is enough to map all coefficients of this matrix to all K[[u -a]]'s. Going in the other direction is more subtle but is explained In [START_REF] Caruso | Random matrix over a dvr and lu factorization[END_REF], §2.3.

A generalisation of Iwasawa's theorem and applications

The aim of this subsection is to present an algorithm with oracle to compute the maximal module associated to a S ν -module. Moreover, as a byproduct of our study, we will derive an upper bound on the number of generators of a maximal sub-S ν -module of S n ν . The idea of our construction (inspired by an algorithm of Cohen) is to consider the matrix of relations of a module and to perform elementary operations preserving quasi-isomorphisms to put this matrix in a certain form. In order to do so, we first need a way to compute the matrix of relations of a module or at least a certain approximation of it. Let M be a torsion-free finitely generated S ν -module and let (e 1 , . . . , e k ) ∈ M k be a family of generators of M . We denote by R the module of relations of (e 1 , . . . , e k ) that is the set of (λ 1 , . . . , λ k ) ∈ S k ν such that k i=1 λ i e i = 0. Let r be the rank of M ⊗ Sν S ν,π . From the exact sequence

0 → R ⊗ Sν S ν,π → S k ν,π → M ⊗ Sν S ν,π → 0, ( 12
)
we deduce that R ⊗ Sν S ν,π is a free module over S ν,π of rank ℓ = k -r. Let (f 1 , . . . , f ℓ ) be a basis of R ⊗ Sν S ν,π and set

R ′ = ⊕ ℓ i=1 (S ν,π • f i ∩ S k ν ). Apparently, R ′ is a sub-S ν -module of R which is free of rank ℓ. Indeed, if n i denotes the smallest integer such that π ni • f i ∈ S k ν , then the family (π ni • f i ) is a basis of R ′ . Moreover, we have the inclusion R ′ ⊃ π N R for a certain N since R ′ ⊗ Sν S ν,π = R ⊗ Sν S ν,π
. Now, from the knowledge of the matrix M ∈ M d×k (S ν ) whose column vectors are the coordinates of e i in the canonical basis of S d ν , we can compute a matrix R ′ ∈ M k×ℓ (S ν ) of generators of R ′ using the algorithms of §3.2.2. We have by definition M.R ′ = 0. Of course in the above construction, we can replace, mutatis mutandis the localisation with respect to π by the localisation with respect to u α /π β .

An algorithm to compute the maximal module

We start with a couple of matrices M = (m i,j ) ∈ M d×k (S ν ) and R = (r i,j ) ∈ M k×ℓ (S ν ) representing the generators of M embedded in S d ν and a sub-module of R containing π N R for a certain N . We are going to prove by induction that we can put R in triangular form by using elementary operations on the rows of R and the columns of M which preserve M up to quasi-isomorphism. We suppose that for a positive integer i 0 there is a strictly increasing function t : [1, i 0 ] → N * such that

• for all i = 1, . . . , i 0 -1, for j > i, and t(i) ≤ m < t(i + 1), r j,m = 0 ;

• for all i = 1, . . . , i 0 , for all j > t(i), r i,j = 0.

The matrix R has the following shape:

R = r 1,t(1) r i0,t(i0) ⋆ ⋆ ⋆ ⋆                 , (13)
where the blanks represent 0 entries. We set t(i 0 + 1) to be the first integer t such that t(i 0 ) < t ≤ ℓ and there exists a j ≥ i 0 + 1 with r j,t = 0. If no such integer exists then we have finished. In order to describe operations on rows (resp. columns) of a matrix T of dimension k × ℓ it is convenient to denote the row vectors of T (resp. the column vectors of T ) by L i (T ) for i = 1, . . . , k (resp. C i (T ) for i = 1, . . . , ℓ). We say that the condition Cond(i) on R is satisfied if there exist two different indices j 0 , j 1 ∈ {1, . . . , k} such that r j0,t(i) • r j1,t(i) = 0, v ν (r j0,t(i) ) ≤ v ν (r j1,t(i) ) and deg W (r j0,t(i) ) ≤ deg W (r j1,t(i) ). We apply the algorithm ColumnReduction (see Algorithm 3) on R, M, i 0 + 1, t(i 0 + 1).

It is clear that the matrix M returned by Algorithm 3 represents the same module M since it modifies M by performing elementary operations on the columns. Moreover, the algorithm preserves the relation M • R = 0. The effect of the operation of Step 5 of Algorithm 3 on the entry r j1,t(i) of R is either

• replace it by 0,

• or it decreases strictly its Weierstrass degree and it increases its Gauss valuation.

Hence, it is easily seen that after a finite number of loops the conditions Cond(t(i 0 + 1)) will no longer be satisfied on R. It may happen that there is only one nonzero entry on the t(i 0 + 1) th column of R and in this case, we are basically done: by permuting the rows of R we can suppose that the non zero entry is r i0+1,t(i0+1) . Next, we remark that the vector v of M whose coordinates in the canonical basis of S d ν is given by the (i 0 + 1) th column of M verifies r i0+1,t(i0+1) • v = 0 which means that v = 0 and we can set r i0+1,j = 0 for j > t(i 0 + 1).

If there are several nonzero entries on the t(i 0 + 1) th column of R and the condition Cond(t(i 0 + 1)) is not satisfied on R, we let j 0 be such that v ν (r j0,t(i0+1) ) = min 1≤j≤k {v ν (r j,t(i0+1) )}. Note that we have v ν (r j0,t(i0+1) ) < v ν (r j,t(i0+1) ) for j = j 0 because on the contrary, the condition Cond(t(i 0 + 1)) would be satisfied on R. By multiplying the t(i 0 + 1) th column of R by an element of S ν,π with valuation -v ν (r j0,t(i0+1) ), we can moreover suppose that v ν (r j0,t(i0+1) ) = 0. Let δ = min j =j0 (v ν (r j,t(i0+1) )).

Algorithm 3: ColumnReduction (preliminary version)

input :

• M ∈ M d×k (S ν )

• R ∈ M k×ℓ (S ν ) in the form (13),

• i, t(i) ∈ N output : R,M such that M • R = 0 and R does not satisfy condition Cond(t(i))

1 while Cond(t(i)) is satisfied do 2 Pick up j 0 , j 1 ∈ {1, . . . , k} such that r j0,t(i) • r j1,t(i) = 0, v ν (r j0,t(i) ) ≤ v ν (r j1,t(i0+1) ) and deg W (r j0,t(i) ) ≤ deg W (r j1,t(i) ); 3 (q, r) ← EuclideanDivision(r j0,t(i) , r j1,t(i) ); 4 C j0 (M ) ← C j0 (M ) + qC j1 (M ); 5 L j1 (R) ← L j1 (R) -qL j0 (R);
6 return M, R;

The case ν = 0 First, we suppose that ν = 0 from which we deduce that δ is a positive integer.

Denote by e 1 , . . . , e k the generators of M represented by the column vectors of the matrix M . Denote by M 1 the module generated by (e ′ j ) j=1...k with e ′ j = e j for j = j 0 and e ′ j0 = 1 π e j0 . The identity of S d ν induces an inclusion f : M → M 1 . It is clear that the cokernel of f is annihilated by π. Moreover, we have

r j0,t(i0+1) .e ′ j0 = j =j0 r j,t(i0+1) π e j . (14)
As the right hand side of ( 14) is in M since r j,t(i 0 +1) π ∈ S ν , the cokernel of f is also annihilated by r j0,t(i0+1) which is a distinguished element of S ν . We conclude that f is a quasi-isomorphism.

We denote by O 1 (j) the operation on the couple of matrices (M, R) which consists in multiplying by 1 π the (j) th column of M and multiplying by π the (j) th row of R. Keeping the hypothesis and notations of the preceding paragraph, it is clear that if (M, R) represents the module M and its relations, then the matrices resulting of the operation of O 1 (j 0 ) represents the module M 1 which is quasi-isomorphic to M . By repeating operations of the form O 1 (j) a finite number of time, we can suppose that δ = 0. But it means that the condition Cond(t(i 0 + 1)) is not satisfied on R and we can call again Algorithm 3.

We thus obtain the algorithm ColumnReduction (final version) which takes a relation matrix of the form (13) for i 0 and returns a relation matrix of the same form for i 0 + 1. The algorithm MatrixReduction (final version), Algorithm 6, uses ColumnReduction in order to compute a new set of generators of a module quasi-isomorphic to M the relation matrix of which has a triangular form.

The general case We reduce the general case to the case ν = 0, by using Lemma 2.5. Let ̟ in an algebraic closure of K be such that

̟ α = π. Let R ′ = R[̟], S ′ ν = S ν ⊗ R R ′ and M ′ = M ⊗ Sν S ′
ν . The valuation on R (resp. the Gauss valuation on S ν ) extends uniquely to R ′ (resp. to S ′ ν ). We have v ν (̟) = 1/α. The algorithm for the general case is exactly the same as for the case ν = 0 up to the point when Cond(t(i 0 + 1)) is not satisfied. By multiplying the t(i 0 + 1) th column of R by ̟ -vν (r j 0 ,t(i 0 +1) )•α , we can moreover suppose that v ν (r j0,t(i0+1) ) = 0. Let δ = min j =j0 (v ν (r j,t(i0+1) )).

With this setting, we can define a quasi-isomorphism in the same manner as before. Namely, let e 1 , . . . , e k be the generators of M ′ as a sub-module of S ′ ν d represented by the column vectors of the matrix M . Denote by M ′ 1 the module generated by (e ′ j ) j=1...k where e ′ j = e j for j = j 0 and e ′ j0 = 1 ̟ δ e j0 . Then the natural injection M ′ → M ′ 1 is a quasi-isomorphism. We denote by O 2 (j, δ) the operation on the couple of matrices (M, R) with coefficients in S ′ ν which consists in multiplying by 1 ̟ δ the (j) th column of M and multiplying by ̟ δ the (j) th row of R. With the hypothesis and notations of this paragraph (i.e. M has the form (13)), if (M, R) represents the module M ′ and its Algorithm 4: MatrixReduction for the case ν = 0 input :

• R ∈ M k×ℓ (S ν ), • M ∈ M d×k (S ν ) such that M • R = 0. output : R ∈ M k×ℓ (S ′ ν ), M ∈ M d×k (S ′ ν ) such that M • R = 0 and R is a triangular matrix. i 0 ← 0; t(i 0 ) ← 1; while i ≤ k do t(i 0 ) ← min{t|t > t(i 0 ) and ∃j > 0, with r j,t = 0 }; i 0 ← i 0 + 1; M, R ← ColumnReduction(M, R, i 0 , t(i 0 )); for j ← t(i 0 ) + 1 to ℓ do r i0,j ← 0 Algorithm 5: ColumnReduction (final version) for ν = 0 input : • M ∈ M d×k (S ν ),
• R ∈ M k×ℓ (S ν ) in the form (13),

• i, t(i) ∈ N the position of the last non zero "diagonal" entry of R.

output : R,M such that M.R = 0 and R is triangular up to the i + 1 row.

while ∃j 0 , j 1 such that j 0 = j 1 and r j0,

t(i) • r j1,t(i) = 0 do while Cond(t(i)) is satisfied do Pick up j 0 , j 1 ∈ {1, . . . , k} such that r j0,t(i) • r j1,t(i) = 0, v ν (r j0,t(i) ) ≤ v ν (r j1,t(i) ) and deg W (r j0,t(i) ) ≤ deg W (r j1,t(i) );
(q, r) ← EuclideanDivision(r j0,t(i) , r j1,t(i) );

C j0 (M ) ← C j0 (M ) + qC j1 (M ); L j1 (R) ← L j1 (R) -qL j0 (R); Let j 0 be such that deg W (r j0,t(i) ) = max 1≤j≤k {deg W (r j,t(i) )}; δ ← min j =j0 (v ν (r j,t(i) )) -v ν (r j0,t(i) ); C j0 (M ) ← 1 π δ C j0 (M ); 10 L j0 (R) ← π δ L j0 (R); 11 return M, R;
relations, then the matrices (M ′ , R ′ ) resulting of the operation of O 2 (j 0 , δ) represents the module M ′ 1 which have been shown to be quasi-isomorphic to M ′ (as a S ′ ν -module). Moreover, R ′ verifies the condition Cond(t(i 0 + 1)).

The matrix M ′ (resp. R ′ ), resulting of the operation O 2 (j, δ) is made of column (resp. row) vectors with coefficients in S ν multiplied by ̟ δ for a certain δ ∈ 1 α Z. An important claim is that this structure will be kept intact in the course of the computations involving all the elementary operations introduced up to now. In fact, these operations on the rows of R are:

• multiplication of a row by a ̟ α , for α an integer ;

• permutation of the rows ;

• for j 0 , j 1 ∈ {1, . . . , k}, replacing L j1 (R) by L j1 (R)-q ′ L j0 (R) where q ′ is the quotient of ̟ α 1 •y by ̟ α0 • x for x, y ∈ S ν and α 0 , α 1 ∈ N.
It is clear that the two first operations does not change the structure of R and the same thing is true for the last operation. Indeed, let q ∈ S ν,π and r ∈ S ν,π ∩ K[u] with deg(r) ≤ deg W (x), be such that y = q • x + r, then for α 0 , α 1 ∈ N, we have ̟ α0 • y = ̟ α0-α1 q • ̟ α1 x + ̟ α0 r so that we have q ′ = ̟ α0-α1 q with q ∈ S ν .

In order to prove formality this claim and take advantage of it to carry out all the computations in the smaller S ν coefficient ring, we represent the couple of matrices (M ′ , R ′ ) with coefficients in S ′ ν by a triple (M, R, L) where M, R are matrices with coefficients in S ν and

L = [α 1 , . . . , α k ] is a list of integers such that for i = 1, . . . , k, C i (M ′ ) = ̟ α i C i (M ) and L i (R ′ ) = ̟ -αi L i (R). We say that the condition Cond ′ (i) on R is satisfied if there exists two different j 0 , j 1 ∈ {1, . . . , k} such that r j0,t(i) • r j1,t(i) = 0, v ν (r j0,t(i) ) + αj 0 α ≤ v ν (r j1,t(i) ) + αj 1 α and deg W (r j0,t(i) ) ≤ deg W (r j1,t(i) )
. With these notations, we can write the final version of the MatrixReduction algorithm (see Algorithm 6) which encode the matrices M ′ , R ′ with coefficients in S ′ ν with a couple M, R of matrices with coefficients in S ν and a list of integers.

Example 3.17. We illustrate the operation of the algorithm on the module of example 3.3. Recall that M is the submodule of S 0 generated by (π 2 , πu 3 ). It is represented in the canonical basis of S 0 by the matrices M of generators and R of relation :

M = π 2 πu 3 , R = u 3 -π .
It is clear that Cond(1) is not verified on R since there is no division possible between its entries. As a consequence, we apply operation O 1 (1) on the couple (M, R) to obtain:

M = π πu 3 , R = πu 3 -π .
Now, we have πu 3 = -u 3 • π and by applying on M (resp. R) an elementary operation on the columns (resp. rows), we get finally :

M = π 0 , R = 0 -π .
An we deduce that the maximal module associate to M is π.S 0 .

Computation of Max(M )

Let

M 1 , R 1 , L 1 = MatrixReduction(M, R, L = [0, . . . , 0]). Let L 1 = [β 1 , . . . , β k ].
We denote by M ′ 1 the sub-S ′ ν -module of (S ′ ν ) d generated by the vectors given in the canonical basis of (S ′ ν ) d by the column vectors ̟ βi • C i (M 1 ) for i ∈ {1, . . . , k} such that L i (R 1 ) is the zero vector. Lemma 3.18. We have . We say simply that a b is a best approximation (resp. a positive best approximation) of r if a b is a best approximation (resp. a positive best approximation) relatively to 1. Remark 3.24. Our definition of best approximation corresponds to what is often called in the literature best approximation of second kind (see [START_REF] Ya | Continued fractions[END_REF]).

M ′ 1 = Max(M ⊗ Sν S ′ ν ).
Everything we need about continued fractions is contained in the following theorem (see [START_REF] Ya | Continued fractions[END_REF]Th. 15 and Th. 16]). 1. Every convergent p k /q k is a best approximation of x.

2. Reciprocally, every best approximation of x is a convergent, the only exceptions being the cases x = a 0 + κ, with κ ∈ [1/2, 1[, p0 q0 = a0 1 . Moreover, for i = 0, . . . , n -1, x -pi qi > 0 for i even and x -pi qi < 0 for i odd. Let r be a real number and b an integer. In the following, it is convenient to denote by min(r, b) • for all j ∈ {0, . . . , n}, {q j } x > 0 if j is even, {q j } x < 0 if j is odd;

(resp. min + (r, b)) the integer a such that |b • r -a| = min{|b • r -k|, k ∈ Z} (resp. such that b • r -a = min{b • r -k, k ∈ Z with b • r -k > 0}).
• for j ∈ {1, . . . , n -2} for all ζ integer such that 0 ≤ ζ < a j+2 , ζ • {q j+1 } x + {q j } x has the same sign has {q j } x .

Moreover for all j ∈ {1, . . . , n -2} and all ζ integer such that 0 ≤ ζ < a j+2 ,

{ζ • q j+1 + q j } x = ζ • {q j+1 } x + {q j } x .
Proof. The fact that {q j } x > 0 if j is even, {q j } x < 0 if j is odd is an immediate consequence of Theorem 3.25. If ζ = 0, there is nothing to prove. We suppose for instance that {q j } x > 0 and {q j+1 } x < 0 (the other case can be treated in a similar manner). Suppose that for 0 < ζ < a j+2 , we have

{q j } x + ζ • {q j+1 } x < 0. ( 17
)
Let ζ be the smallest verifying (17), then ζ ≥ 2 since we have by definition of a best approximation

|{q j } x | > |{q j+1 } x |. Then, as {q j } x + (ζ -1) • {q j+1 } x > 0, we have |{q j } x + ζ • {q j+1 } x | < |{q j+1 } x |
which is a contradiction with the fact that there is no best approximation of x the denominator of which is between q j+1 and q j+2 = a n+2 q j+1 + q j > ζ • q j+1 + q j . With our hypothesis, for all integer ζ such that 0 < ζ < a j+2 , we have {q j } x > {q j } x +ζ •{q j+1 } x . Thus we have we have {q j } x > ζ(q j+1 •x-min(x, q j+1 ))+q j •x-min(x, q j ) > 0, so that 1/2 > (ζq j+1 + q j ) • x -ζ min(x, q j+1 ) -min(x, q j ) > 0 (remember that as j ≥ 1, {q j } x ≤ 1/2). As a consequence, ζ min(x, q j+1 ) + min(x, q j ) = min(x, ζq j+1 + q j ) thus {ζ • q j+1 + q j } x = ζ • {q j+1 } x + {q j } x .

For x = [a 0 ; a 1 , . . . , a n ] ∈ Q and γ a positive integer, we would like to be able to obtain the list of positive best approximations of x relatively to γ. The lemma tells us that not only the convergents p 2i /q 2i for i ∈ {0, . . . , ⌊n/2⌋} are positive best approximations of x but also the min + (x, q 2i + µq 2i+1 )/(q 2i + µq 2i+1 ) for i ∈ {0, . . . , ⌊(n -2)/2⌋} and µ integer such that 1 < µ < a 2i+2 . The following proposition states that these are all the positive best approximations of x and gives a generalisation for the case of a positive γ. Proposition 3.28. Let x = a/b where a, b are relatively prime integers. Write x = [a 0 ; a 1 , . . . , a n ] and denote by p k /q k the sequence of convergents associated to the continued fraction [a 0 ; a 1 , . . . , a n ]. Let γ < b be a positive integer. Let γ ≤ d ≤ b be an integer such that min + (x,d) d is a positive best approximation of x relatively to γ. Let i be the biggest index such that d -q 2i+1 ≥ γ and let λ be the biggest integer such that d -q 2i+1 -λ • q 2i+2 ≥ γ. Then

1) min + (x,d-q2i+1-λ•q2i+2) d-q2i+1-λ•q2i+2
is a positive best approximation of x relatively to γ.

2) If e is such that d-q 2i+1 -λ•q 2i+2 < e < d then min + (x, e)/e is not a positive best approximation of x relatively to γ.

Moreover, we have

{d -q 2i+1 -λ • q 2i+2 } + x -{d} + x = λ • {q 2i+2 } x -{q 2i+1 } x > 0. ( 18
)
Proof. Let i and λ be defined as in the statement. We remark that we have λ < a 2i+3 . Indeed, by hypothesis d -q 2i+1 -λ • q 2i+2 ≥ γ, but we have q 2i+3 = a 2i+3 • q 2i+2 + q 2i+1 and we know that

d -q 2i+3 < γ. For 0 ≤ ζ < a 2i+3 an integer, let µ(ζ) = q 2i+1 + ζ.q 2i+2 , h = d -µ(λ).
First, we prove that

{d} + x -{µ(ζ)} x = {d -µ(ζ)} + x , (19)
if 0 ≤ ζ < a 2i+3 . Using Lemma 3.27, we obtain Now, suppose that there exists γ ≤ e < d such that To finish the proof, we note that (18) is an immediate consequence of (19) and Lemma 3.27.

0 ≤ min(x, µ(ζ)) -µ(ζ) • x < 1. ( 20
) As 0 ≤ d • x -min + (x, d) < 1, we have 0 ≤ (d -µ(ζ)) • x -min + (x, d) + min(x, µ(ζ)) <
{d} + x < {e} + x ≤ {h} + x . (22)
+ x -{e(ζ)} + x | = |{µ(ζ)} + x - {µ(ζ + 1)} + x | = {q 2i+2 } x ,
Let x be a rational and γ a positive integer. From the Proposition 3.28, we immediately obtain an algorithm (see Algorithm 7) to compute the reserve ordered list of the integers q such that min + (x, q)/q is a positive best approximation of x relatively to γ.

From Algorithm 7, it is possible to obtain a bound on the number of positive best approximations of a rational number x. In order to state the following corollary, we introduce a notation: for (µ, ρ, χ) ∈ R 2 × N, we denote by L(µ, ρ, χ) the finite arithmetic sequence with first term µ, common difference ρ and length χ (if χ is zero then the sequence is considered as empty).

Corollary 3.29. Let x = [a 0 ; a 1 , . . . , a n ] be a rational number, denote by p k /q k for k = 0, . . . , n the associated sequence of convergents. Let γ be a positive integer. The list a positive best approximations of x relatively to γ has cardinality bounded by 2 + ⌊n/2⌋ i=1 a 2i . Denote by L the finite sequence of increasing integers q such that min + (x, q)/q is a positive best approximation relatively to γ. Let I = {0, . . . , ⌊(n -1)/2⌋}. There exist two sequences (µ i ) i∈I and (χ i ) i∈I with coefficients respectively in Q and N such that L = ∪ i∈I L(µ i , q 2i+1 , χ i ). Moreover, for i ∈ I, the sequence ({q} +

x ) q∈L(µi,q2i+1,χi) is also an arithmetic sequence with common difference {q 2i+1 } x < 0.

Proof. To prove the first part of the statement, it suffices to show that the number of elements of the list generated by the loop beginning in line 12 of Algorithm 7 for a given value of nextqk is less than a nextqk+1 . Indeed, it is clear from the initialisation of Algorithm 7 that nextqk is running through the odd indices in {0, . . . , n -1}. Now the relation q

[nextqk + 1] = a nextqk+1 • q[nextqk]+q[nextqk-1]
implies that the loop on line 12 is executed at most a nextqk+1 times. Taking into account the first and last element in the list L, we obtain that its cardinality is bounded by 2 + ⌊n/2⌋ i=1 a 2i . The second part of the statement is clear, since the while loop on line 12 build a (reverse ordered) arithmetic sequence of common difference q[nextqk] and the last point is an immediate consequence of (18). Remark 3.30. Denote by L the output of Algorithm 7. By the corollary, L is a union of arithmetic sequences each of which can be encoded by a triple of integers giving the first term of the sequence, its common difference and the number of terms of the sequence. Recall that x = [a 0 ; a 1 , . . . , a n ]. Using this encoding, the list L can be represented (as a data structure) by O(n) bits of information. Moreover, it is easy to modify Algorithm 7 so that it returns the list L encoded in that way and have running time O(n). For this, we just have to replace lines 12-14 by:

length ← floor last -γ q[nextqk] ; first ← last -length • q[nextqk]; L ← (first, q[nextqk], length) ∪ L; last ← first
We have everything at hand in order to compute efficiently the generators of N = {x ∈ S ν |v ν (x) ≥ -δ/α}. Indeed, consider the line L given by the equation y + x. β α = -δ α . Let γ = δ β mod α, where δ β mod α is considered as a positive integer in {0, . . . , α -1}. Then -γ is the abscissa of the first point of the line L with integer coordinates to the left of the origin point. Denote by (q i ) i∈I the list of integers q i such that min + (β/α, q i )/q i is a positive best approximation of β/α relatively to γ. Then if we set α i = q i -γ, it is easily seen that the α i are precisely the same as the one defined in the Lemma 3.22.

Corollary 3.31. Let ν = β/α = [a 0 ; a 1 , . . . , a n ]. Let δ be an integer. Set N = {x ∈ S ν |v ν (x) ≥ -δ/α}.
Then N is generated elements of the form (π βi .u αi ) i∈J where the cardinality of J is bounded by 2 + ⌊n/2⌋ i=1 a 2i . Let I = {1, . . . , ⌊n/2⌋}. There exist two sequences (µ i ) i∈I and (χ i ) i∈I with coefficients respectively in Q and N such that (α i ) i∈J = ∪ i∈I L(µ i , q 2i+1 , χ i ). Moreover, the sequence v ν (π βi .u αi ) αi∈L(µi,q2i+1,χi) is also an arithmetic sequence.

By gathering all the results of this section, we obtain: i=1 a 2i ). These generators can be represented by d vectors of S d ν and d • ⌊n/2⌋ arithmetic sequences of the form L(µ, q, χ) where q is the denominator of a convergent of odd index associated to [a 0 ; a 1 , . . . , a n ].

Application: scalar extension of S

ν -modules Let ν ′ , ν ∈ Q such that ν ′ > ν, there is a natural inclusion θ ν,ν ′ : S ν → S ν ′ . Given a module M over S ν , We would like to compute the module Max(M ⊗ Sν S ν ′ ) ∈ Max d S ν ′ . If M = (m ij ) ∈ M d×k (S ν )

Generality with precision

We recall from the introduction that R is a complete discrete valuation ring, and that for algorithmic applications we are mostly interested by:

• Z p or more generally the ring a integer of a finite extension of Q p ,

• the ring k[[X]] of formal power series with coefficients in a (finite) field k.

In any case, if π denote the uniformizer element of R and p π is a positive integer, we shall represent an element of R by its image in the quotient R/π pπ R. We suppose that there exists algorithms to compute the arithmetic operations of the ring R/π pπ R. We say that an element x ∈ R/π pπ R is the data of element of x ∈ R up to π-adic precision p π if x mod π pπ = x.

For the complexity analysis, we shall assume that we have efficient algorithms to perform all standard operations in quotients R/π pπ R for all integers p π . We discuss briefly the validity of this assumption for the aforementioned classical examples of rings R. In the case that R = k[[X]], we suppose that the operations in the field k costs one unit of time and can be represented by one unit of memory. With that in mind, if R = k[[X]] there exists a trivial algorithm to perform additions. It is optimal in the sense that its complexity is equal to the size of the inputs. The same thing is true if R is the ring of integers of any finite extension of Q p . Things are more complicated for the multiplication of two elements of R/π pπ R, whose time will be denoted by T 0 (p π ) in the rest of this paper. In the case R = Z p , using Strassen algorithm [START_REF] Von | Modern computer algebra[END_REF], we have T (p π ) = Õ(p π ) where the soft-O notation means that we neglect logarithmic factors. If R is the ring of integer of a degree d finite extension of Q p , we can represent elements of R with a degree d -1 polynomial with coefficients in Z p and using again Strassen algorithm for polynomials, we have T

0 (p π ) = Õ(d • p π ). If R = k[[X]]
using again Strassen algorithm for polynomials, we have T (p π ) = Õ(p π ) (we suppose here that operation in k costs one unit of time). We can summarize these results by saying that with the best known algorithms, the time T 0 (p π ) is quasi-linear log(|R/π pπ R|).

An obvious way to obtain a finite approximation of an element of a i u i ∈ S ν is to consider a representative modulo a certain power p u of u. We, thus obtain a degree p u -1 polynomial with coefficients in R that we can represent by a vector of dimension p u with coefficients in R up to precision p π as before. We call this representation the flat approximation of an element of S ν with u-adic precision p u and π-adic precision p π or the (p u , p π )-flat approximation. The data of a representative with π-adic precision p π and u-adic precision p u of an element x = a i u i /π ⌈iν⌉ ∈ S ν is given by a polynomial pu i=0 a i u i /π ⌈iν⌉ such that a i = a i mod π pπ . It should be remarked however that the flat approximation is not the only possible procedure to truncate an element of S ν in order to obtain a finite structure. For instance, one can represent an element of S ν up to a certain u-adic precision p u by a polynomial pu-1 i=0 a i u i with coefficients in R of degree p u -1. Such a polynomial may itself be represented by the data of a i mod π pπ for i = 0, . . . , p u -1, as before but it is also possible to represent pu-1 i=0 a i u i by coefficients with different π-adic precisions a i mod π pπ,i . Put in another way, we want to obtain a representative of pu-1 i=0 a i u i modulo the R-module pu-1 i=0 π pπ i u i /π ⌈iν⌉ • R. We call this representation the jagged approximation. We can generalize even further the flat and jagged approximations. For instance, we remark that for f = a i u i ∈ S ν the flat and jagged approximations consist in the data of f (i) (0)/i! for i = 0, . . . , p u -1 but we could also provide the data of f (i) (x)/i! for any x ∈ K in the radius of convergence of f .

Taking into account the previous examples, we say that a data of precision is given by any sub-R-module P of S ν . Most of the time, but not always, we want S ν /P to be R-module of finite length. Indeed, it may happen that we compute with objects of S ν that can be represented exactly with a finite structure. This is the case for instance, if the characteristic of R is 0, of any element Z ⊂ R. In this special case, it makes sense to consider a data of precision P such that S ν /P is not of finite length in order to take into account the fact that we know certain elements of S ν with "infinite precision". In general, in order to represent an element of S d ν by a finite data structure, one can consider a sub-R-module P of S d ν such that most of the time S d ν /P has finite length. Then, in order to compute a function f : S d ν → S d ν , we would like to replace it by its approximation f : S d ν /P → S d ν /f (P). This naive approach does not work in general since, as f is not always R-linear, the image by f of a data of precision is not a data of precision. Though, it is possible to approximate f (P) by the smallest possible data of precision. One way to do this is to consider a regular data precision which is a data of precision that is a S ν -module. Then for x ∈ S d ν and h ∈ P, one can write the first order Taylor development of f in x f (x + h) = f (x) + df x (h) + O(h 2 ).

Most of the time (but not always), df x (P) will be the correct data of precision (see [START_REF] Caruso | adic precision[END_REF] for a full discussion about this). Note that any flat approximation is a regular data of precision but this is not always the case that a jagged approximation is a regular data of precision. The computation of the function f reduces to the computation of the function on the representative up to the given precision and the computation of the precision of the result. A more general precision data is intuitively less convenient for computations since it involves more complex data structures. For instance, each coefficient of a polynomial representing an element of S ν with the jagged approximation may have very unbalanced length so that it may be difficult to adapt asymptotically fast arithmetic for such objects. On the other side, we are going to see shortly that even for a very common operation in S ν such as the computation of the Euclidean division, one may take advantage of the flexibility of the jagged approximation. Hence, the choice of a representation to compute with elements of S ν is a non trivial trade off between space/time complexity on the one hand and the quantity of precision we accept to loss on the other hand.

It is convenient to represent a jagged precision by a series. For this, let P π = ∞ i=0 a i u i /π ⌊iν⌋ ∈ S ν . In the following, we denote by P(P π ) the sub-R-module of S ν given by ∞ i=0 a i u i /π ⌊iν⌋ • R. Moreover, if P is sub-R-module of S ν , we denote by repr(P) : S ν → S ν /P the canonical projection of R-modules. It is clear that P(P π ) only depends on the valuation of the coefficients a i of P π = ∞ i=0 a i u i /π ⌊iν⌋ ∈ S ν . If p π is an integer, we will use the notations P f (p u , p π ) for

P( pu-1 i=0 π pπ u i /π ⌊iν⌋ + ∞ pu u i /π ⌊iν⌋ )
which corresponds to the (p u , p π )-flat approximation. If P ′ and P are two sub-R-modules of S ν such that P ′ ⊂ P then there is a canonical projection S ν /P ′ → S ν /P that we denote also (by abuse of notation) by repr(P). If λ ∈ S ν , and P is a sub-R-module of S ν , we denote by λ.P = {λ.x, x ∈ P} the sub-R-module of S ν . If λ is distinguished and S ν /P has finite length then S ν /(λ • P) has finite length. If P, P ′ are sub-R-modules of S ν , we denote by P • P ′ the submodule generated by all products xy for (x, y) ∈ (P × P ′ ). It is clear that if S ν /P and S ν /P ′ have finite length then S ν /(P • P ′ ) also have finite length.

Lemma 4.1. For all P, P ′ sub-R-modules of S ν such that S ν /P and S ν /P ′ have finite length, for all x, y ∈ S ν we have:

1. if P ′ ⊃ P then repr(P ′ )(repr(P)(x)) = repr(P ′ )(x) ;

2. repr(P + P ′ )(repr(P)(x)) + repr(P + P ′ )(repr(P ′ )(y)) = repr(P + P ′ )(x + y) ; We discuss briefly the complexity of the elementary arithmetic operations in S ν with the (p u , p π )flat approximation. First, we remark that the size of an element of S ν with the (p u , p π )-flat approximation is in the order of p π • p u . As before, the time of an addition in S ν is linear in the size of a representative of S ν since it reduces to the addition of two polynomials of degree p u -1 with coefficients in R/π pπ R. We denote by T (p u , p π ) the time cost of the multiplication of two elements of S ν with the (p u , p π )-flat approximation. Again, by using a tweaked Strassen's algorithm, we have T (p u , p π ) = Õ(p u • T (p π )) = Õ(p u • p π ). In the following, we study the precision of some important functions using the flat and jagged approximation.

Finite precision computation with elements of S ν

Most of the time, even for very elementary function dealing with elements of S ν , it is not possible to ensure the stability of the result without some extra assumption. We illustrate this fact with some important examples.

First, consider the Gauss valuation function v ν : K[[u]] → Q. A natural way to define v ν on a representative modulo P f (p u , p π ), with p u , p π positive integers, is to compute the valuation of the truncated representative in S ν . For instance let x = π + u 10 , then v 0 (repr(P f (9, 2))(x)) = v 0 (π) = 1. We denote also this function by v ν . But then we have v 0 (repr(P f (9, 2))(x)) = 1 and v 0 (repr(P f (10, 2))(x)) = 0. From the previous example, one can see that the Gauss valuation of an element x ∈ S ν,π can not be computed in general from the knowledge of its approximation. Still, it is possible to obtain the Gauss valuation of an element x ∈ S ν,π from the knowledge of its approximation if we are given some extra-information about x. For instance, if v ν (repr(P f (p u , p π ))(x)) = 0 and if we know furthermore that x ∈ S ν then we are sure that v ν (x) = 0. More generally, it may happen than we have a guaranty that x ∈ 1/π λ .S ν for a λ ∈ Z. Then, if ν is big enough, it is possible to compute the valuation of x from the knowledge of repr(P f (p u , p π ))(x). Lemma 4.2. Let x = a i u i ∈ 1/π λ • S ν for λ a positive integer. Let p u be a positive integer and x ∈ K[u] be the unique representative of x mod u pu of degree < p u . We suppose that x = 0 and that d = deg W (x) < p u .

Let ν ′ ∈ Q be such that

ν ′ -ν ≥ λ + v ν (x) p u -d , ( 25
)
then v ν ′ (x) = v ν ′ (x).
Proof. Let x = a i u i ∈ 1/π λ • S ν . By definition, we have v ν ′ (x) ≤ v K (a d ) + ν ′ • d and on the other side we have of course v ν ′ (x) ≤ v ν ′ (x). Thus, in order to prove the lemma, we just have to check that for all i ≥ p u , we have

v K (a i ) + ν ′ • i ≥ v K (a d ) + ν ′ • d. (26)
But, using x ∈ 1/π λ • S ν , we get v K (a i ) + ν • i ≥ -λ

for all i ≥ p u . From (26) and (27), we deduce that it is enough to prove that -λ + i(ν ′ -ν) ≥ v K (a d )+ν ′ .d. Since ν ′ -ν ≥ 0 by hypothesis, it suffices to prove that -λ+p u (ν ′ -ν) ≥ v k (a d )+ν ′ .d for all i ≥ p u . This is equivalent to

ν ′ ≥ v K (a d ) + p u • ν + λ p u -d , (28)
which is exactly (25).

This lemma, while totally elementary, shows the following very important fact: by increasing the ν parameter of the S ν -module, one can obtain guaranties on the valuation of a certain x = a i u i ∈ S ν from the knowledge of its representative x = pu-1 i=1 a i u i with bounded Weierstrass degree under the general hypothesis of a lower bound on the valuation of the coefficients a i .

Another important operation for the arithmetic of S ν is the inversion.

Lemma 4.3. Let x ∈ S ν and suppose that deg W (x) = 0 and that v ν (x) = 0 so that by Corollary 2.7, x is invertible. Let p u , p π be positive integers. Then repr(P f (p u , p π ))(x) ∈ S ν /P f (p u , p π ) is also invertible and we have repr(P f (p u , p π ))(x) -1 = repr(P f (p u , p π ))(x -1 ).

Proof. Write x = a i u i /π ⌊iν⌋ , x -1 = b i u i /π ⌊iν⌋ and c = 1 = c i u i /π ⌊iν⌋ with c j = j i=0 a i • b j-i . We have v K (a 0 ) = 0 so that we can compute a 0 -1 mod p π = b 0 mod p π . Then, using the formula b j π ⌊jν⌋ = 1 a 0 • j-1 i=0 a i b j-i π ⌊iν⌋ π ⌊(j-i)ν⌋ , together with the remark that π ⌊jν⌋ /(π ⌊iν⌋ π ⌊(j-i)ν⌋ ) is equal to 1 or π, we obtain by induction for j = 1, . . . , p u -1, b j mod p π .

Theorem 1 . 1 .

 11 The natural mapΨ : Max d Sν -→ Free d Sν,π × Free d Sν,u M → (M π , M u ).

Figure 1 :

 1 Figure 1: The Gauss valuation of π 2 • u 4 with ν = 1/3 is 10/3.

  Moreover, the image of Φ contains the subset of Free d S ′ ν of free modules which admit a basis (e i ) i∈I where e i ∈ (S ′ ν ) d and e i = ̟ αi e ′ i with e ′ i ∈ (S ν ) d and α i ∈ N. Remark 3.10. Actually, we will prove later (see Lemma 3.18) that the image of Φ is exactly the subset of Free d S ′

  is a field containing S ν,π and S ν,u . If M is a sub-S ν -module of E d , we shall denote by M π (resp. M u ) the sub-S ν,π -module (resp. the sub-S ν,u -module) of E d generated by M . For example, if M is free over S ν with basis (e 1 , . . . , e h ), then M π (resp. M u ) is also free over S ν,π (resp. S ν,u ) with the same basis. As M is torsion free, and as S ν,u and S ν,π are principal ideal domains, M π and M u are free. We denote by Max d Sν the set of maximal sub-S ν -modules of S d ν and for A = S ν , S ν,π or S ν,u , let Free d A denote the set of sub-A-modules of A d , which are free over A. Recall that Max d S0 = Free d S0 . Thus, the following lemma provides a useful description of maximal S 0 -modules. Lemma 3.11. Let S = S 0 . The natural map

Definition 3 .

 3 23. Let r be a real number, and let γ be a positive integer. We say that a fraction a b (b ≥ γ) is a best approximation (resp. a positive best approximation) of r relatively to γ if for all integers c, d such that γ ≤ d ≤ b and c/d = a/b (resp. such that γ ≤ d ≤ b, dr -c > 0 and c/d = a/b), we have |dr -c| > |br -a| (resp. dr -c > br -a > 0)

Theorem 3 .

 3 25. Let x = [a 0 ; a 1 , . . . , a n ].

  Then, for r a real number and b a positive integer, we let {b} r = b • r -min(r, b) and {b} + r = b • r -min + (r, b). Example 3.26. Let r = 0.9 and b = 2. Then we have min(r, b) = 2, min + (r, b) = 1, {b} r = -0.2 and {b} + r = 0.8. We need the following lemma: Lemma 3.27. We have:

  2. We have to prove that(d -µ(ζ)) • x -min + (x, d) + min(x, µ(ζ)) < 1. Suppose, on the contrary, that (d -µ(ζ)) • x -min + (x, d) + min(x, µ(ζ)) ≥ 1,then because of (20), we have:0 ≤ (d -µ(ζ)) • x -min + (x, d) + min(x, µ(ζ)) -1 < d • x -min + (x, d).(21) If ζ ≤ λ this is a contradiction with the hypothesis that min + (x,d) d is a positive best approximation of x relatively to γ. If ζ > λ then (d -µ(ζ)) • x -min + (x, d) + min(x, µ(ζ)) < (d -µ(λ)) • xmin + (x, d) + min(x, µ(λ)) because {µ(ζ)} + x > {µ(λ)} + x by Lemma 3.27. Next, we remark that (d -µ(λ)) • x -min + (x, d) + min(x, µ(λ)) < 1 by what we have just proved, so that we have (d -µ(ζ)) • x -min + (x, d) + min(x, µ(ζ)) < 1. In any case, we are done.

  we deduce that |{e -e(ζ)} x | < {q 2i+2 } x and the fact that |e -e(ζ)| < q 2i+3 contradicts the second statement of Theorem 3.25.Thus, we have that {e}+ x = {e(ζ)} + x . Then, from (22), we can write {e} + x = {d} + x -{µ(ζ)} x ≤ {h} + x = {d} + x -{µ(λ)} x so that {µ(ζ)} x ≥ {µ(λ)} x . Suppose that {µ(ζ)} x > {µ(λ)} x then, as λ ≤ ζ < a 2i+3 ,it means that ζ > λ. But then, e = e(ζ) = d -µ(ζ) < γ which is a contradiction with the hypothesis γ ≤ e. As a consequence, we have λ = ζ and e = h.

Theorem 3 .

 3 32. Let ν = [a 0 ; a 1 , . . . , a n ]. Let M be a sub-S ν -module of S d ν . Then a bound on the number of generators of Max(M ) is d.(2 + ⌈n/2⌉

3 .

 3 let P 0 = y • P + x • P ′ + P • P ′ , thenrepr(P 0 )(repr(P)(x)) • repr(P 0 )(repr(P ′ )(y)) = repr(P 0 )(x • y); 4. if P ′ ⊃ P, then repr(P ′ )(repr(P)(x)) • repr(P ′ )(y) = repr(P ′ )(x • y)Proof. The fist claim is trivial. Then we have (x + P) + (y + P ′ ) = x + y + (P + P ′ ) and (x + P) • (y + P ′ ) = x • y + x • P ′ + y • P + P • P ′ . The fourth claim, is an immediate consequence of 1 and 3.

  7, Theoreme 3.1] together with the fact that S ν,π and S ν,u are Euclidean rings. Moreover for all x, y ∈ S ν,π one can compute the gcd(x, y) in O(deg W (y)) ring operations. From its triangle form, one can then compute the Hermite Form of M with coefficients in S ν,π at the expense of O(d • r • d max ) ring operations.Remark 3.16. We deduce from this proposition that if M ∈ M d×d ′ (S ν,π ) is a full rank matrix, there exists P such that M • P is a matrix of the form[START_REF] Lang | Cyclotomic fields[END_REF] with all coefficients in K[u]. In the same way, if M ∈ M d×d ′ (S ν,u

  As for all ζ ∈ {λ, . . . , a 2i+3 -1}, |{e(ζ + 1)}

	For 0 ≤ ζ < a 2i+3 a non negative integer, let e(ζ) = d -µ(ζ). Choose ζ so that |{e} + x -{e(ζ)} + x | is minimal. By (19), we know that {e(ζ)} + x = {d} + x -{µ(ζ)} x . As moreover {d} + x -{µ(a 2i+3 )} x ≤ {d} + x (following Lemma 3.27) and {e(λ)} + x = {h} + x , we deduce that λ ≤ ζ < a 2i+3 . Suppose that {e} + x -{e(ζ)} + x = 0.

Algorithm 6: MatrixReduction input :

• R ∈ M k×ℓ (S ν ),

• M ∈ M d×k (S ν ) such that M • R = 0.

output : R ∈ M k×ℓ (S ′ ν ), M ∈ M d×k (S ′ ν ), L such that M • R = 0 and R is a triangular matrix.

1 i 0 ← 0; 2 t(i 0 ) ← 1; 3 L ← [0, . . . , 0]; 4 while i ≤ k do 5 i 0 ← i 0 + 1; 6 t(i 0 ) ← min{t|t > t(i 0 ) and ∃j > 0, with r j,t = 0 }; 7 while ∃j 0 , j 1 such that j 0 = j 1 and r j0,t(i0) • r j1,t(i0) = 0 do 8 while Cond ′ (t(i 0 )) is satisfied do 9 Pick up j 0 , j 1 ∈ {1, . . . , k} such that r j0,t(i0) • r j1,t(i0) = 0, v ν (r j0,t(i0) ) + L[j0] α ≤ v ν (r j1,t(i0) ) + L[j1] α and deg W (r j0,t(i0) ) ≤ deg W (r j1,t(i0) );

if v ν (r j0,t(i0) ) > v ν (r j1,t(i0) ) then δ 0 ← ⌈v ν (r j0,t(i0) ) -v ν (r j1,t(i0) )⌉;

L j1 (R) ← π δ0 L j1 (R);

C j1 (M ) ← π -δ0 C j1 (M );

(q, r) ← EuclideanDivision(r j0,t(i0) , r j1,t(i0) );

C j0 (M ) ← C j0 (M ) + qC j1 (M );

Let j 0 be such that deg W (r j0,t(i0) ) = max 1≤j≤k {deg W (r j,t(i0) )};

δ ← min j =j0 (v ν (r j,t(i0) )) -v ν (r j0,t(i0) );

for j ← t(i 0 ) + 1 to ℓ do r i0,j ← 0 Let j 0 ∈ {1, . . . , k} be such that r j0,t(i0) = 0;

(C j0 (M ), C i0 (M )) ← (C i0 (M ), C j0 (M ));

(L j0 (R), L i0 (R)) ← (L i0 (R), L j0 (R));

Proof. Let M ′ = M ⊗ Sν S ′ ν and let M 1 be the sub-S ′ ν -module of (S ′ ν ) d generated by the column vectors of M 1 . It is clear that M 1 = M ′ 1 since for i ∈ {1, . . . , k} such that L i (R 1 ) is not the zero vector, we have C i (M 1 ) = 0 (because M 1 is torsion free). As M 1 is obtained from M ′ by a sequence of quasi-isomorphisms, it means that there exists a quasi-isomorphism q ′ : M ′ → M ′ 1 . If we prove that M ′ 1 is a free S ′ ν -module, we are done by Lemma 3.6. Consider the exact sequence 0 → R → S k ν → M → 0 associated to the family (e 1 , . . . , e k ) of generators of M . As S ′ ν is flat over S ν , and as

= 0 from which we deduce that R 1 = 0 and we are done.

Remark 3.19. As a byproduct of the preceding proof, we see that the vectors given in the canonical basis of (S ′ ν ) d by the column vectors

The corollary is an immediate consequence of Proposition 3.9 and Lemma 3.18.

Computation with S ν -modules

Proposition 3.9 and Lemma 3.18 establish a one-to-one correspondence Φ :

Moreover, the image of Φ is exactly the set of free sub-S ′ νmodules of S ′ ν d which admit a basis (e i ) i∈I where e i ∈ (S ′ ν ) d and e i = ̟ αi e ′ i with e ′ i ∈ (S ν ) d and 0 ≤ α i ≤ α. We have seen that a M ∈ Φ(Max d Sν ) can be represented by a couple (M, L) where M ∈ M d×k (S ν ) and L is a list of positive integers ≤ α.

From the data of a matrix representing an element of M ∈ Max d Sν the algorithm MatrixReduction computes the couple (M, L) representing Φ(M ). Moreover, if M ′ ∈ Φ(Max d Sν ), the Algorithm 7 allows to recover Φ -1 (M ′ ). We see that we can easily go back and forth between the different representations. For most of the applications however, it is convenient to represent an element of M ∈ Max d Sν by a couple (M, L). Indeed, we have the lemma:

Proof. For the first claim, we have Φ

Next, we prove the second claim. We have the following diagram of quasi-isomorphisms:

Sν ) be represented respectively by the couples (M 1 , L 1 ) and (M 2 , L 2 ). Then, by Lemma 3.21 one can represent the sum M 1 + max M 2 by applying the algorithm Ma-trixReduction on the couple ((M 1 M 2 ), L 1 + L 2 ) (where L 1 + L 2 is the concatenation of the lists L 1 and L 2 ). The representation as a couple (M, L) is however not well suited to the computation of the intersection of modules, since it implies the computation of the kernel of a matrix with coefficient in S ν which is not Euclidean.

The generators of a maximal module

In order to have a complete algorithm (with oracles) to compute Max(M ), it remains to explain how to recover M 2 = M ′ 1 ∩S d ν from the knowledge of M ′ 1 (see §3.3.2 for the definition of M ′ 1 ). We would like also to obtain a bound on the number of generators of M 2 . By the construction of M ′ 1 , there exists a basis (e 1 , . . . , e k ) ∈ S d ν and δ i ∈ N for i = 1, . . . , k, such that

Hence, it is enough to explain how to compute M ′ 1 ∩S d ν when M ′ 1 has dimension 1. In this case, M ′ 1 is generated by an element of the form 1 ̟ δ • y where y ∈ S ν and by definition, we want to find generators for the S ν -module {x ∈ S ν |v ν (x) ≥ v ν ( 1 ̟ δ • y)}. We are reduced to the problem of finding generators of the S ν -module N = {x ∈ S ν |v ν (x) ≥ -δ/α}. Lemma 3.22. Let δ ∈ {0, . . . , α -1}. We define inductively a sequence of couple of integers (α i , β i ) by setting α 0 = 0, β 0 = 0. Then for i > 0, while β i-1 + α i-1 ν > -δ α , we let (α i , β i ) be the unique couple of integers such that

• for all (x, y) = (α i , β i ) ∈ Z 2 such that 0 ≤ x ≤ α i and y+xν ≥ -δ α , we have β i +α i ν < y+xν, • α i is the smallest integer strictly greater than α i-1 such that there exists an integer β i with (α i , β i ) satisfying the two conditions above.

The family (π βi • u αi ) has cardinality bounded by α and is a system of generators of the S νmodule N = {x ∈ S ν |v ν (x) ≥ -δ/α}.

Proof. First, it is clear by definition that all the π βi • u αi are elements of N . Moreover, it is clear that α i is bounded by -δ/β mod α.

Denote by N 0 the sub-S ν -module of N generated by the family (π βi • u αi ). Let x ∈ N , we prove inductively on deg

by applying Corollary 2.9, we can write x = q • h, with q ∈ S ν invertible and h ∈ K[u] is a degree d polynomial such that v ν (h) ≥ -δ/α and deg W (h) = d. We have to show that h is in N 0 . Let i 0 be the greatest index such that α i0 ≤ d. Then by construction of the family (α i , β i ), we have v ν (π βi 0 • u αi 0 ) ≤ v ν (h). Indeed, if t is the term of h of degree d then t ∈ N and if we write t = π µ •u χ , we have by construction β i0 + α i0 ν ≤ µ+ χν. Thus we can write h = q 1 • π βi 0 • u αi 0 + r where q 1 ∈ S ν , deg W (r) < α i0 and v ν (r) ≥ -δ/α. We can then apply the induction hypothesis on r to conclude.

From the above lemma, one can easily deduce an algorithm to compute the generators of N = {x ∈ S ν |v ν (x) ≥ -δ/α} as well as an upper bound on the number of generators. In order to find the α i we just run over all the values between 1 and -δ/β mod α and check for each of them if it satisfies the conditions of Lemma 3.22. Nevertheless this algorithm is inefficient and the obtained bound is far from tight. In the following, we explain how to obtain a tight bound as well as an efficient algorithm to compute a family of generators of N by using the theory of continued fractions. In order to set up the notations, we briefly recall the results from this theory that we need (see [START_REF] Ya | Continued fractions[END_REF]). For a 0 , . . . , a n integers, the notation [a 0 ; a 1 , . . . , a n ] refers to the value of the continued fraction

We take the convention that a n = 1 in [a 0 ; a 1 , . . . , a n ] so that every rational number can be written uniquely as a finite continued fraction. Let r = [a 0 ; a 1 , . . . , a n ]. We let p 0 = a 0 , q 0 = 1,

The fractions p k /q k are called the k th convergent of the continued fraction [a 0 ; a 1 , . . . , a n ]. We have the properties:

• the integers p k and q k are relatively prime (see [9, Th. 2]);

Algorithm 7: Reverse order list of positive best approximations input :

• γ ≤ b a positive integer.

output : L a reverse ordered list of the integers q such that min + (x, q)/q is a positive best approximation of x relatively to γ

return L; is a matrix representing M , it can be done by calling the algorithm MatrixReduction on the matrix (θ ν,ν ′ (m ij )).

Nevertheless, if M is maximal, there is another better way to carry out this computation. Assume that M is represented by a couple (M ′ , L ′ ) with M ′ ∈ M d×k (S ν ) and L ′ = [α 1 , . . . , α k ] is a list of integers. Let (f 1 , . . . , f k ) with f i = ̟ αi • e i for i = 1, . . . , k and e i ∈ S d ν be the basis of Φ(M ) given by the column vectors associated to the couple (M ′ , L ′ ) (see Remark 3.19). Then by definition M is generated by the sub-S ν -modules

Moreover, using Algorithm 7, one can recover a family of generators of F i which are of the form s j • e i with s j ∈ S ν and following Remark 3.30 it is possible to encode the generators of F i by a list of arithmetic sequences. As this representation is very compact, we would like take advantage of it in order to compute the scalar extension. By working component by component, we only have to consider the case of a sub-S νmodule of S ν , N = {x ∈ S ν |v ν (x) ≥ -δ/α} for δ ∈ N. Then it has been seen in Corollary 3.31 that N is generated elements of the form (π βi .u αi ) i∈J . More precisely, write ν = [a 0 ; a 1 , . . . , a n ] and let I = {1, . . . , ⌊n/2⌋}. Then, there exists three sequences (µ i ) i∈I , where (ζ i ) i∈I and (χ i ) i∈I with coefficients respectively in Q, N and N such that (α j

Of course, the sequence (π βj .u αj ) j∈J has coefficients in S ν ′ and is a family of generators of N ′ . Hence, Max(N ′ ) corresponds to the couple (M ′ , L ′ ) where the unique element of L ′ is given the minimum of all quantites β j + ν ′ • α j when j runs over J. Now, we remark that the sequence β j + ν ′ • α j is arithmeric when j runs over one subset L(µ i , ζ i , χ i ). On this subset, the minimum is reached for the first index or the last one. Thus, to compute L ′ , it is enough to take the minimum over these particular indices. It yields an algorithm whose complexity is O(n) -or O(nd) for the d-dimensional case -where we recall that n is the length of the continued fraction of ν (in

Comparing the two approaches

We have introduced two different ways to represent S ν -modules and compute with them. It is important to compare the two approaches since they are well suited for different kind of applications. We call the representation of §3. We explain how to compute the (M, L)-representation associated to a (M π , M u )-representation in the case that the associated module M ∈ Max d Sν has full rank. Suppose we are given the couple (M π , M u ) representing M where M π = (m π,i,j ) ∈ M d×k (S ν,π ) and M u = (m u,i,j ) ∈ M d×k (S ν,u ). We can suppose, by multiplying M π by a certain power of π (which is invertible in S ν,π ), that all the m π,i,j ∈ S ν . As the coefficients of M u are defined modulo a certain power of π (namely the determinant of M u ), we can also suppose, by multiplying M u by a certain power of u α /π β (which is invertible in S ν,u ), that all the coefficients of M u belongs to S ν . Let D u = det(M u ) ∈ S ν . On the other side, let

By definition, we have v ν (D π ) = 0. Denote by M π 0 (resp. M u 0 ) the sub-S ′ ν -module of (S ′ ν ) d generated by the column vectors of D u M π (resp. D π M u ), considered as matrices with coefficients in S ′ ν . We can prove:

Lemma 3.33. Keeping the above notations, we have:

Proof. Using the formula adj(M ) = det(M ).M -1 , it is clear that the column vectors of the matrix D u M π (resp. D π M u ) belong to the S ′ ν,u -module generated by the column vectors of M u (resp. the S ′ ν,π -module generated by the column vectors of M π ). As a consequence, we have

. By Proposition 3.8, it means that there exists n ∈ N such that

Note that D u is a power of π, as a consequence there exists n 0 > n such that

We would like to prove that there exists n 1 ∈ N such that (u/̟ β ) n1 x ∈ M π 0 + M u 0 . For this, it suffices to prove that (u/̟

ν,u (remember that v ν (D π ) = 0) there exists t ∈ S ′ ν and n 2 ∈ N such that t.D π = (u/̟ β ) n2 mod π n0 S ′ ν . Denote by f 1 , . . . , f k the vectors whose coordinates in the canonical basis of (S ′ ν ) d are given by the column vectors of M u 0 . Now, as (u/̟ β ) n • x ∈ M u there exist λ i ∈ S ′ ν,u , for i = 1, . . . , k, such that

ν ) d and using the triangular form of the matrix M u (see Proposition 3.15) we have that λ i ∈ S ′ ν for i = 1, . . . , k. By multiplying the preceding equation by t.D π , we obtain:

. As a consequence by taking n 1 = n + n 2 , we have:

By ( 23) and ( 24), there exists a m ∈ N such that

and we are done.

Remark 3.34. In the preceding construction, we need the extension S ′ ν of S ν just to ensure that v ν (D π ) = 0. Thus, if v ν (det(M π )) ∈ Z, this extension is not necessary.

Now, let M ∈ Max d

Sν be represented by a couple (M π , M u ). As M π and M u are given in Hermite Normal Form, we can easily compute D π and D u . Let M ′ π = D u M π and M ′ u = D π M u . Lemma 3.33 tells us that we can then obtain the (M, L)-representation of M by calling the MatrixReduction algorithm on the matrix (M ′ π M ′ u ). The main advantage of the (M π , M u )-representation is that is provides unique representation of maximal modules over S ν , because of the same property for Hermite Normal Forms. Thus, it allows to test equality between modules. We have seen also that the echelon form is well suited to test whether x ∈ S d ν is an element of M ∈ Max d Sν as well as to computation the intersection of two modules. On the other side the (M, L)-representation provides an actual basis of module in Max d Sν . Moreover, the base change operation ⊗ Sν S ν ′ only makes sense in the (M, L)-representation and we will see in §4, an important application of this operation. Indeed, if ν ′ ≥ ν, altough there is a natural inclusion morphism S ν ⊂ S ν ′ , the two sub-rings of E , S ν,u and S ν ′ ,u are not comparable by the inclusion relation.

Representation and precision

In the previous sections, we have presented algorithms to compute with S ν -modules by using, as a black-box, the ring operations of S ν . As elements of S ν can not be coded with a finite data structure, these procedures are not algorithms stricto sensus since they can not be implemented on a Turing machine for instance. In order to turn them into algorithms, we have to explain how to represent mathematical objects by finite data structures. Much in the same way as we compute with approximations of real numbers, we can represent power series with coefficients R by truncating them up to a certain precision. Then we have to ensure the stability of the computations, i.e. that the result is independent of the part of the input that we ignore. In the following, we proceed in an incremental manner. First, we explain how to represent the elements of the coefficient ring R of S ν by a finite structure, then we deal with elements of S ν and finally with more complex structures with coefficients in S ν such as S ν -modules. Let x, y ∈ S ν . In order to be able to compute an approximation of the Euclidean division of y by x , it is necessary to know that v ν (y) ≥ v ν (x). One way to have that guaranty is to be given x with enough precision to know that it is distinguished. Then one can compute its Weierstrass degree. In the following proposition, we keep the notations of Proposition 2.8. Proposition 4.4. Let x, y ∈ S ν . Suppose that x is distinguished and let d = deg W (x). Let q ∈ S ν and r ∈ K[u] ∩ S ν be such that deg(r) < d and y = q • x + r. Put e = v ν (Lo(x)) > 0, let p π be a positive integer and p x = ⌈p π /e⌉d. Let

There exists an algorithm which takes as input repr(P f (p x , p π ))(x) and repr(P(P y ))(y) and outputs repr(P f (p x , p π ))(q) and repr(P f (∞, p π ))(r). Proof. Recall that, from Proposition 2.8, q, r are the limits of the sequences (q j , r j ) defined by q 0 = 0 and r 0 = y and

For j = 0, . . . , ⌈p π /e⌉, let

and let t(j) = repr(P(P y,j ))(r j ). It is clear that t(0) = repr(P(P y ))(y). We are going to prove that if we know repr(P f (p x , p π ))(x) and t(j) then we can compute t(j + 1). Write Hi(x, d) = u d /π νd • x 0 , with x 0 an invertible element of S ν . Then from repr(P f (p x , p π ))(Hi(x, d)), we immediately obtain repr(P f (p x -d, p π ))(Hi(x 0 , d)), and by Lemma 4.3, we can compute repr(P f (p xd, p π ))(1/(Hi(x 0 , d))). As P f (p x -d, p π ) ⊂ P(p x -d • j, P y,j ), applying Lemma 4.1, we deduce that repr(P(P y,j ))(Hi(r j , d)/Hi(x 0 , d)) = repr(P(P y,j )(repr(P f (p x -d, p π ))(1/(Hi(x 0 , d)))).repr(P(P y,j )(Hi(r j , d)). (29)

We remark that repr(P(P y,j )(Hi(r j , d)) = Hi(t(j), d) so that the left hand side of (29) can be computed from the known data. Dividing repr(P(P y,j ))(Hi(r j , d)/Hi(x 0 , d)) by u d /π ⌊dν⌋ , we obtain repr(P(P j ))(Hi(r j , d)/Hi(x, d)), where

Next, as v ν (Lo(x)) = e, still be applying Lemma 4.1, and remarking that t(j + 1) = π e • P j , we obtain repr(P(t(j + 1)))( Hi(r j , d)

repr(P(t(j + 1)))(repr(P(P j ))(Hi(r j , d)/Hi(x, d))).repr(P f (∞, p π ))(Lo(x)). (31)

From the above, we deduce by induction that we can compute repr(P(P y,⌈pπ /e⌉ ))(r). But we have P(P y,⌈pπ /e⌉ ) = P f (∞, p π ) so that we can compute repr(P f (∞, p π ))(r) as claimed. Moreover, as we can compute repr(P(P j ))(Hi(r j , d)/Hi(x, d)), by Lemma 4.1, we can compute repr( P(P j ))(q) = repr(P 0 )(q) and we are done. Remark 4.5. In the preceding proposition, we see that in order to be able to compute repr(P f (d, p π ))(r), we really use all the information contained in repr(P(p y , P y ))(y). If we use the flat precision, then to obtain repr(P(d, p π )) we need to know repr(P(⌈p π /e⌉.d, p π ))(y). This shows that the flat precision is not well adapted to the computation of the Euclidean division in S ν since a lot of information about the operands is not useful for the computation.

The proposition shows that following the computations of Algorithm 1 on representatives modulo the given precision, we obtain the outputs with the guaranty that the result has the claimed precision.

The last operation in S ν (actually in S ν,π ) that we would like to consider is the gcd computation. To begin with, we consider some very simple examples, for elements of S ν which are polynomials. Suppose that R = Z 5 , ν = 0 so that S ν = Z 5 [[u]]. Let P 1 = repr(P f (∞, 2))(u -1) and P 2 = repr(P f (∞, 2))(u -2). Then it is clear that for all P 1 , P 2 ∈ S ν such that P 1 = P 1 mod P f (∞, 2) and P 2 = P 2 mod P f (∞, 2) then gcd(P 1 , P 2 ) = 1. This can be seen by using the Euclidean algorithm to compute the extended gcd of P 1 and P 2 in S ν /P f (∞, 2) which obviously returns 1. In this case, it is safe to claim that gcd(P 1 , P 2 ) = 1.

Next, consider P 3 = repr(P f (∞, 2))(u -1) and P 4 = repr(P f (∞, 2))(u -1). In this case, it is very easy to find different representatives of P 3 and P 4 the gcd of which is not equal. For instance, we can take P 3 = P 4 = u -1 in this case gcd(P 3 , P 4 ) = u -1 but if we take P 3 = u -1 and P 4 = u -6 then gcd(P 3 , P 4 ) = 1. If we compute the gcd of P 3 and P 4 using the Euclidean algorithm, we obtain u -1 and we do not have enough precision on the next remainder to decide whether it vanishes or not. This example shows that, in the case that the gcd of the representatives is not surely 1 it is not even clear how to define it since the result may change depending on the representatives in S ν that we use in order to compute it.

Finite precision computation with modules with coefficients in S ν

Let M 1 and M 2 be two maximal sub-S ν -modules of S d ν . In this section, we are interested by the computation of the maximal sum M 1 + max M 2 of M 1 and M 2 . We would like to carry out computations with finite precision and have a guaranty on the precision of the results. The preceding example suggests that even in the case d = 1, we can not hope much in that direction. Indeed, the computation of the maximal sum of two sub-S ν -modules of S ν,π reduces to the computation of the gcd of two elements of S ν,π and we have seen in §4.2, that unless this sum is S ν,π , we can not guaranty that the result computed with finite precision is an approximation of the result computed on representatives in S ν,π .

As before, we need some extra-information, that we can get from the mathematical context of our computation, in order to guaranty the precision of the output. A very natural extra-information that can arise in practise is the following: let M 1 and M 2 be two sub-S ν -modules of S d ν,π and we know that there exists a positive integer c such that M 2 ⊂ 1/π c M 1 . We recognize a generalisation of the hypothesis of Lemma 4.2 where we have shown in the case that d = 1 that we can obtain a guaranty on the valuation v ν of approximations of elements of K[[u]] for well chosen ν. This situation is also crucial in the paper [START_REF] Caruso | Semi-simplifiée modulo p des représentations semi-stables : une approche algorithmique[END_REF]. We are going to see that, although we don't know how to compute an approximation of M 1 + max M 2 , we can describe an algorithm which outputs an approximation of (M

The computation of ν ′ from p u and ν.

In order to compute M 1 + max M 2 , it is enough to be able to compute M 1 + max S ν • t where t ∈ M 2 . Indeed, let (t 1 , . . . , t h ′ ) be a family of generators of M 2 , we have

Let t ∈ M 2 and let (e 1 , . . . , e h ) be a family of generators of M 1 . By our hypothesis, we know that there exists λ i ∈ 1/π c • S ν such that t = λ i e i . We remark that if all the λ i are in S ν then t ∈ M 1 so that M 1 + S ν • t = M 1 and there is nothing to do. Write λ i = j≥0 a i j u j with v K (a i j ) + ν • j ≥ -c. Let p u a positive integer, we are going to choose ν ′ , as it is explained in figure 4, such that j≥pu a i j u i ∈ S ν ′ . For this it is enough to take ν ′ ≥ ν + c/p u . Let t ′ = i λ ′ i e i with λ ′ i = pu-1 j=0 a i j u j and t ′′ = i λ ′′ i e i with λ ′′ i = ∞ pu a i j u j . Using the same remark as above, we have:

i is a polynomial in u, we can obtain its valuation, greatest common divisor and all the operations that we need in order to compute (M 1 ⊗ Sν S ν ′ ) + max (t • S ν ′ ).

We recall that we write ν = β/α with α, β relatively prime numbers and let ̟ in an algebraic closure of K, be such that ̟

The algorithm AddVector is an adaptation of the algorithm MatrixReduction.

In the preceding algorithm, Cond(λ, L) returns true if there exists j 0 , j 1 ∈ {1, . . . , h} such that λ

) We want to give a consequence of this algorithm. We first need a definition. Definition 4.6. Let M be a sub-S ν -module of S d ν . Let P be a sub-R-module of S ν . We say that a matrix M r = (m r ij ) ∈ M d×d ′ (S ν /P) is an P-approximation of M is there exists a matrix M = (m ij ) ∈ M d×d ′ (S ν ) whose columns are the coordinates of generators of M in the canonical basis of S d ν and such that m r ij = repr(P)(m ij ).

By iterating this algorithm AddVector on a set of (t 1 , . . . , t h ′ ) of generators of M 2 , we obtain the following theorem: suppose that we are given M r 1 = (repr(P 0 (p u , p π ))(m 1 ij )) and M r 2 = (repr(P 0 (p u , p π ))(m 2 ij )). Let e be the number of columns of M 2 and let ν ′ = ν + ec/p u . Then there exists a polynomial time algorithm in the length of the representation of M r 1 and M r 2 to compute a matrix M r 3 = (M 3 ij ) with coefficients in S ν ′ /P 0 (p u , p π ) which is a P 0 (p u , p π )-approximation of (M 1 ⊗ Sν S ν ′ ) + max (M 2 ⊗ Sν S ν ′ ).