ALGORITHMIC METHODS FOR FINITELY

GENERATED ABELIAN GROUPS

H. Cohen, F. Diaz y Diaz and M. Olivier

Abstract. We describe algorithmic tools to compute with exact sequences of Abelian groups. Although simple in nature, these are essential for a number of applications such as the determination of the structure of (ℤ_{K}/𝔪)^{∗} for an ideal 𝔪 of a number field K, of ray class groups of number fields, and of conductors of the corresponding Abelian extensions.

In this note, we give the main algorithmic tools which are necessary for working with finitely generated Abelian groups. Although simple in nature, they are not completely trivial, and are essential for many applications, in particular in computational class field theory (see [Co-Di-Ol]). Furthermore, we have not been able to locate them explicitly in the mathematical litterature. Thus, after explaining how to represent groups and maps, we give algorithms for computing kernels, images, quotients and extensions of groups.

1. Definitions and Notation

All the groups that we consider are finitely generated (in fact usually finite) Abelian groups. In view of our applications, they will be written multiplicatively.

We will systematically use the following matrix notation. Let A be a group and let A = (α_{1}, …, α_{r}) be a row vector of elements in A. If X is a column vector with integer entries x_{i}, we denote by AX the element ∏_{i} α_{i}^{x_{i}} of A. More generally, if M is a matrix with r rows having integer entries, we denote by AM the row vector of the elements β_{j} = AM_{j}, where M_{j} denotes the j-th column of M. If A and B are row vectors or matrices with the same number of rows, we denote by (A|B) the (horizontal) concatenation of A and B. If X and Y are column vectors, we will denote by (\frac{X}{Y}) the (vertical) concatenation of X and Y.

Note that row vectors will always represent a list of elements in some Abelian group, while column vectors and matrices will always have integer (or sometimes rational) coefficients.

Definition 1. Let A be a group, G = (g_{1}, …, g_{r}) be elements of A, and M be a matrix with r rows and integral entries. We say that (G, M) is a system of generators and relations for A if the g_{i} are generators, and if any relation between the g_{i} is a linear combination

Typeset by AMS-TEX

Key words and phrases. Exact sequences, Abelian groups.

1991 Mathematics Subject Classification. Primary 20K05, Secondary 11Y40.

with integer coefficients of the columns of the matrix M. In matrix terms, this can be written concisely as follows:

α ∈ A ⟺ ∃X ∈ ℤ^{r}, GX = α ,
GX = 1 ⟺ ∃Y ∈ ℤ^{r}, X = MY

(in particular, we have GM = 1, where 1 is a row vector of unit elements of A).

Another way of writing the above is the existence of the following exact sequence (i.e. a presentation of A):

ℤ^{k} ⟶^{M} ℤ^{r} ⟶^{G} A ⟶ 1 .

Definition 2. Let A be a group. We say that (A, D_{A}) is a Smith normal form (SNF) for A if (A, D_{A}) is a system of generators and relations for A and if D_{A} is a diagonal matrix in Smith normal form (i.e. the diagonal elements a_{i} satisfy a_{i+1} | a_{i} for i < r) and no diagonal element is equal to 1.

Note that, by the elementary divisor theorem we know that there exists a Smith normal form and that the matrix D_{A} is unique. On the other hand, the generators A are not unique.

The following algorithm, although immediate, will be of constant use.

Algorithm 3 (SNF for groups). Let (G, M) be a system of generators and relations for a finite group A. This algorithm computes a Smith normal form (A, D_{A}) for A. It also outputs a matrix which will be useful for later use.

1. [Apply Hermite] Let H be the Hermite normal form (HNF) of the matrix M obtained by applying the HNF algorithm. If H is not a square matrix (i.e. if M was not of maximal rank), output an error message stating that M cannot be a complete system of relations or that A is infinite, and terminate.

2. [Apply Smith] Using the Smith normal form algorihm, compute unimodular matrices U and V and a diagonal matrix D in Smith normal form such that UHV = D. Set A′ ← GU^{−1}.

3. [Remove trivial components] Let n be the largest i such that D_{i,i} ≠ 1 (0 if none exists). Let D_{A} be the matrix obtained from D by keeping only the first n rows and columns, let A be the row obtained by keeping only the first n entries of A′, and let U_{a} be the (not necessarily square) matrix obtained by keeping only the first n rows of U. Output (A, D_{A}), output U_{a} and terminate the algorithm.

The validity of this algorithm is clear. Note the important relation AU_{a} = G. Moreover, if an element α of A is known on the generators G as α = GX, then on the new generators A we have α = A(U_{a}X), so the matrix U_{a} allows us to go from one system of generators to another.

We can now set the following definitions.

Definition 4. Let A be a group. We say that the group A is algorithmically known if we have done the following.

(1) We have computed a system (G, M) of generators and relations for the group A, or equivalently by Algorithm 3, a Smith normal form (A, D_{A}).

(2) We have an algorithm which, given an element α ∈ G, finds a column vector X with integer entries such that α = GX (or α = AX if we have the SNF). The column vector X will be called the discrete logarithm of α on the given generators.

When we say that we compute an Abelian group, we will always mean compute in the above sense.

A similar definition applies to maps:

Definition 5. Let A and B be two groups which are mathematically known. Assume that at least one of them is algorithmically known in the sense of Definition 4, and let ψ a homomorphism from A to B. We say that ψ is algorithmically known if the following properties are true. If B has been computed, then if α ∈ A, we can compute ψ(α) expressed on the generators of B. Conversely, if A has been computed, then, if β ∈ Im(ψ), we can compute α ∈ A such that β = ψ(α).

2. Computing quotients

Let

1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1

be a 3-term exact sequence of Abelian groups. In this section, we assume that A and B are known (in the sense of Definition 4), and that we want to compute C. We assume also that the maps ψ and ϕ are algorithmically known. Let (A, D_{A}) (resp. (B, D_{B})) be a Smith normal form of A (resp. B) (note that it is only necessary for these to be generators and relations, but usually they will be in SNF). Since ϕ is surjective, it is clear that if we set B′ = ϕ(B), B′ is a system of generators of C. We must find all the relations between them. Let V = (v_{i}) be such a relation, expressed as a column vector. Then

B′V = 1 ⟺ BV ∈ Im(ψ) ⟺ BV = ψ(A)X

for a certain integer vector X.

However, since the group B is known, we know how to compute algorithmically a matrix P such that ψ(A) = BP. Hence

B′V = 1 ⟺ BV = BP X ⟺ B(V − P X) = 1
⟺ V − P X ∈ Im(D_{B}) ⟺ V ∈ Im(P |D_{B}) .

It follows that (ϕ(B), (P |D_{B})) is a system of generators and relations for C. Formally, this gives the following.

Algorithm 6 (Quotient of groups). Given two groups A = (A, D_{A}) and B = (B, D_{B}) in SNF and an exact sequence 1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1, this algorithm computes the SNF of the group C.

1. [Compute P] Using the solution to the discrete logarithm problem in B, compute a matrix P such that ψ(A) = BP.

2. [Compute SNF] Apply Algorithm 3 to (ϕ(B), (P |D_{B})), output the SNF (C, D_{C}) of the result and the auxiliary matrix U_{a}, and terminate the algorithm.

To solve the discrete logarithm problem, we proceed as follows. Let γ ∈ C. Since ϕ is surjective and is known algorithmically, we can find β ∈ B such that γ = ϕ(β). Since we know how to compute discrete logarithms in B, we can find X such that β = BX, hence

γ = ϕ(BX) = ϕ(B)X = CU_{a}X ,

where U_{a} is the auxiliary matrix output by Algorithm 3. It follows that the discrete logarithm of γ on the generators C is given by the vector U_{a}X.

3. Computing kernels

Let B = (B, D_{B}) and C = (C, D_{C}) given in SNF, and assume again that we have an exact sequence

1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1 .

We want to compute the SNF (A, D_{A}) of A. For this, we will compute the kernel of ϕ as an Abelian group. Since ψ will give an explicit isomorphism between A and this kernel, and we assume that it is given algorithmically (as well as its inverse) we will thus have computed A.

Now β ∈ B is in the kernel of ϕ if and only if β = BX for some column vector X satisfying ϕ(BX) = 1. In other words β ∈ Ker(ϕ) ⟺ ϕ(B)X = 1. Since we can solve the discrete logarithm problem in C we can compute a matrix P such that ϕ(B) = CP. Thus

β ∈ Ker(ϕ) ⟺ CP X = 1 ⟺ P X ∈ Im D_{C} ⟺ P X + D_{C}Y = 0

for some integer vector Y. Let R = (\frac{X}{Y}). We thus have

β ∈ Ker(ϕ) ⟺ (P |D_{C})R = 0 for some Y .

This is an instance of the integer kernel problem for which we refer to [Coh]. We thus obtain the following algorithm.

Algorithm 7 (Kernels of groups). Given two groups B = (B, D_{B}) and C = (C, D_{C}) in SNF and an exact sequence 1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1, this algorithm computes the SNF of the group A.

1. [Compute matrix P] Using the solution to the discrete logarithm problem in C, compute a matrix P such that ϕ(B) = CP.

2. [Compute generators] Applying the HNF algorithm, compute a unimodular matrix U such that (P |D_{C})U = (0|W) where W is in HNF. If r is the number of elements of B, let K be the upper left r × r submatrix of U, and set A′ ← BK.

3. [Compute relations] Applying the HNF algorithm, compute a unimodular matrix U′ such that (K|D_{B})U′ = (0|W′) where W′ is in HNF. Let K′ be the upper left r × r submatrix of U′.

4. [Terminate] Find A′′ such that A′ = ψ(A′′) (which is possible since ψ is algorithmically known), apply Algorithm 3 to (A′′, K′), output the SNF (A, D_{A}) and the auxiliary matrix U_{a}K^{−1} (we will see below that K is invertible in GL_{r}(ℚ)), and terminate the algorithm.

To solve the discrete logarithm problem, let α ∈ A and β = ψ(α). Since we know how to solve the discrete logarithm problem in B, we can find X such that β = BX. Since β ∈ Ker(ϕ), the above reasoning shows that X is in the image of K. Assume proved that the matrix K is invertible (in GL_{r}(ℚ)). Then, if Y = K^{−1}X, Y must have integral entries since X is in the ℤ-image of K, and we have

ψ(A′′)Y = A′Y = BKY = BX = β = ψ(α) ,

and since ψ is injective, α = A′′Y, hence Y is the discrete logarithm on the generators A′′, hence as usual the desired discrete logarithm is equal to U_{a}Y = U_{a}K^{−1}X.

Thus we must prove the following lemma.

Lemma 8. Assume that we have a matrix equality of the form (P |D)U = (0|W), where U is invertible and D is a square matrix with nonzero determinant. Let r be the number of columns of P, or equivalently the number of 0 columns on the right hand side. Then if K is the upper left r × r submatrix of U, then K has nonzero determinant.

Proof. Write U = ( \begin{matrix}K & L \\ M & N \end{matrix} ), and let X be a column vector such that KX = 0. Since

P K + DM = 0, we have P KX + DMX = 0 so DMX = 0, and since D has nonzero determinant, MX = 0. This implies that U(\frac{X}{0}) = 0, and since U is invertible, X = 0 so the kernel of K is reduced to 0 and hence K has nonzero determinant. (Note that it is easy to write the inverse of K in GL_{r}(ℚ) in terms of the block matrix decomposition of U^{−1}.) ⊓ ⊔

4. Computing group extensions

This is by far the most important and useful case. Let A = (A, D_{A}) and C = (C, D_{C}) given in SNF, and assume again that we have an exact sequence

1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1 .

We want to compute the SNF (B, D_{B}) of the group B.

Let B′ be chosen such that ϕ(B′) = C. Let β ∈ B. We can write ϕ(β) = CX = ϕ(B′)X = ϕ(B′X), hence β − B′X ∈ Ker(ϕ) so β − B′X = ψ(AY) for some integer vector Y. Thus β = B′X + ψ(A)Y = (B′|ψ(A))R where R = (\frac{X}{Y}). It follows that (B′|ψ(A)) forms a generating set for B (this is of course trivial, but we prefer to do everything in matrix terms).

Let us find the relations between these generators. If R = (\frac{X}{Y}) is such a relation, we have B′X + ψ(A)Y = 1. If we apply ϕ to this relation, we obtain ϕ(B′)X = CX = 1, hence X ∈ Im D_{C}, i.e. X = D_{C}X_{1}. Thus we have B′D_{C}X_{1} + ψ(A)Y = 1.

Set B′′ = B′D_{C}. Then ϕ(B′′) = ϕ(B′)D_{C} = CD_{C} = 1. Thus the entries of B′′ are in Ker(ϕ) = Im(ψ), hence since we can solve the discrete logarithm problem in A we can find a matrix P such that B′′ = ψ(AP) = ψ(A)P.

So finally, the equation for our relation is

ψ(A)P X_{1} + ψ(A)Y = 1 ⟺ ψ(A)(P X_{1} + Y) = 1 ⟺ P X_{1} + Y ∈ Im D_{A}
⟺ P X_{1} + Y = D_{A}T for some integer vector T .

In other words, R is a relation if and only if we have

R = ( \begin{matrix}D_{C} & 0 \\ −P & D_{A} \end{matrix} ) ( \begin{matrix}X_{1} \\ T \end{matrix} )

for some integer vectors X_{1} and T. We then obtain the SNF as before by applying Algorithm 3. Formally, this gives the following.

Algorithm 9 (Group extensions). Given two groups A = (A, D_{A}) and C = (C, D_{C}) in SNF and an exact sequence 1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1, this algorithm computes the SNF (B, D_{B}) of the group B.

1. [Compute generators] Compute B′ such that ϕ(B′) = C (which can be done since ϕ is known algorithmically), and compute ψ(A).

2. [Compute P] Set B′′ ← B′D_{C}, and let A′′ be such that B′′ = ψ(A′′) (B′′ is in the image of ψ and A′′ can be found since ψ is known algorithmically). Using the solution to the discrete logarithm problem in A, compute a matrix P such that A′′ = AP.

3. [Terminate] Set G ← (B′|ψ(A)) and M ← ( \begin{matrix}D_{C} & 0 \\ −P & D_{A} \end{matrix} ). Apply Algorithm 3 to the

system of generators and relations (G, M), output the SNF (B, D_{B}) of B and the auxiliary matrix U_{a}, and terminate the algorithm.

To solve the discrete logarithm problem is easy. Let β ∈ B. Using the discrete logarithm in C we can find X such that ϕ(β) = CX = ϕ(B′)X, hence ϕ(β − B′X) = 1 so β − B′X ∈ Im(ψ), and using the discrete logarithm problem in A we obtain β − B′X = ψ(A)Y for some Y, so β = (B′|ψ(A))(\frac{X}{Y}). Finally, this gives β = BU_{a}(\frac{X}{Y}) hence U_{a}(\frac{X}{Y}) is our desired discrete logarithm.

Remark. From the above discussion, it is clear that the matrix −P measures the obstruction to the fact that the exact sequence is split. More precisely, if P = 0, then clearly the sequence splits, while conversely, if the exact sequence splits, one can modify the generators so that −P becomes equal to 0.

5. Four-term exact sequences

For certain application, such as the computation of ray class groups (see [Co-Di-Ol]), we will also use four term exact sequences. More precisely, assume that we have an exact sequence of the form

E ⟶^{ρ} Z ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1 .

We assume that we know the groups E = (E, D_{E}), Z = (Z, D_{Z}) and C = (C, D_{C}), and we want to compute B. Note that in the application that we have in mind, E is in general infinite, and in that case the diagonal entry of D_{E} is equal to 0 for each infinite cyclic component. This could be treated as a 3-term exact sequence by introducing the group Z/ρ(E), but it is more elegant and just as easy to treat it directly as a four term exact sequence. We leave the details to the reader, and simply give the algorithm.

Algorithm 10 (Four-term exact sequences). Given three groups E = (E, D_{E}), Z = (Z, D_{Z}) and C = (C, D_{C}) in SNF and an exact sequence E ⟶^{ρ} Z ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1, this algorithm computes the SNF (B, D_{B}) of the group B.

1. [Compute generators] Compute B′ such that ϕ(B′) = C (which can be done since ϕ is known algorithmically), and compute ψ(Z).

2. [Compute P] Set B′′ ← B′D_{C}, and let Z′ be such that B′′ = ψ(Z′) (B′′ is in the image of ψ and Z′ can be found since ψ is known algorithmically). Using the solution to the discrete logarithm problem in Z, compute a matrix P such that Z′ = ZP.

3. [Compute Q] Using the solution to the discrete logarithm problem in Z, compute a matrix Q such that ρ(E) = ZQ.

4. [Terminate] Set G ← (B′|ψ(Z)) and M ← ( \begin{matrix}D_{C} & 0 & 0 \\ −P & Q & D_{Z} \end{matrix} ). Apply Algorithm 3 to the

system of generators and relations (G, M), output the SNF (B, D_{B}) of B and the auxiliary matrix U_{a} and terminate the algorithm.

In ray class group computations, the group E will be the group of units of a number field, hence finitely generated but not finite in general. However, as can be seen from step 3, only a finite set of generators is needed.

To solve the discrete logarithm problem is again easy. Let β ∈ B. Using the discrete logarithm in C we can find X such that ϕ(β) = CX = ϕ(B′)X, hence ϕ(β − B′X) = 1 so β − B′X ∈ Im(ψ). Since Z has been computed and ψ is known algorithmically, using the solution to the discrete logarithm problem in Z we obtain β − B′X = ψ(Z)Y for some Y, so β = (B′|ψ(Z))(\frac{X}{Y}). Finally, this gives β = BU_{a}(\frac{X}{Y}) hence U_{a}(\frac{X}{Y}) is our desired discrete logarithm.

6. Computing subgroups

The last problem that we will consider is that of computing all subgroups of a given finite Abelian group C. We assume that C = (C, D_{C}), so that

C = ⨁_{i=1}^{n}(ℤ/c_{i}ℤ)γ_{i} .

We have the following result.

Proposition 11. Let C = (C, D_{C}) be a finite Abelian group as above. There is a one to one correspondence between subgroups of C and integral matrices A in Hermite normal form satisfying A^{−1}D_{C} ∈ M_{n}(ℤ). The correspondence is as follows.

(1) If A is such a matrix, we set C′ = CA in the multiplicative sense already used in the preceding sections. Then if C′ = (γ′_{i}), the subgroup H associated to A is the subgroup of C generated by the γ′_{i}.

(2) Conversely, if H is a subgroup of C, let C′ = (γ′_{i})_{1≤i≤m} be a row vector containing a system of generators of H. We can write C′ = CP for an n × m matrix P. Then A is the Hermite normal form of the matrix (P |D_{C}).

(3) Let A be a matrix in HNF, and let H be the corresponding subgroup. Then |H| = |C|/ det(A) or equivalently |C/H| = det(A).

Proof. We have C ≃ ℤ^{n}/Λ, where Λ is the lattice Λ = ⨁ c_{i}ℤ, so that a ℤ-basis of Λ is (c_{i}ϵ_{i})_{1≤i≤n}, where the ϵ_{i} are the canonical basis elements of ℤ^{n}. The isomorphism is given explicitly by sending the i-th generator γ_{i} of C to ϵ_{i}. Subgroups of ℤ^{n}/Λ are of the form Λ′/Λ, where Λ′ is a lattice such that Λ ⊂ Λ′ ⊂ ℤ^{n}. Such a lattice Λ′ can be defined in a unique way by a matrix A in Hermite normal form so that the columns of this matrix express a ℤ-basis of Λ′ on the ϵ_{i}. The condition Λ′ ⊂ ℤ^{n} means that A has integer entries, and the condition Λ ⊂ Λ′ means that A^{−1}D also has integer entries, since it is the matrix which expresses the given basis of Λ in terms of that of Λ′. In terms of generators, this correspondence translates into the equality C′ = CA of (1).

For (2), we note that CD_{C} = 1, hence if C′′ = C(P |D_{C}) we have simply added some 1’s to the generators of H. Thus, the group can be defined by the matrix of maximal rank (P |D_{C}), hence also by the Hermite normal form A of this matrix.

For (3), we know that A^{−1}D_{C} expresses a basis of Λ in terms of a basis of Λ′, hence

|H| = |Λ′/Λ| = det(A^{−1}D_{C}) = |C|/ det(A) .

⊓ ⊔

Thus, finding all subgroups of H is equivalent to finding integral HNF matrices A such that A^{−1}D_{C} also has integer entries. Note that there exist only a finite number of such matrices A, in fact exactly the number of subgroups of C or equivalently of ⨁(ℤ/c_{i}ℤ). It is natural to call these matrices the left divisors of the matrix D_{C}.

The question of finding these divisors in an efficient manner does not seem to be easy. However, in applications to algebraic number theory, the (generalized) Cohen-Lenstra heuristics say that it is reasonable to assume that the groups C that we will consider will often be cyclic or close to cyclic. Hence, we can proceed as follows. Let n be the number of cyclic components of C.

If n = 1, A divides D_{C} if and only if A = (e_{1}) where e_{1} | d_{1} and e_{1} ≥ 1, hence we simply look at all (positive) divisors of d_{1}.

If n = 2 then an immediate computation shows that A = ( \begin{matrix}e_{1} & f_{1} \\ 0 & e_{2} \end{matrix} ) divides D_{C} if and

only if for i = 1 and i = 2, e_{i} is a positive divisor of d_{i}, and f_{1} = ke_{1}/ gcd(e_{1}, d_{2}/e_{2}) with 0 ≤ k < gcd(e_{1}, d_{2}/e_{2}).

If n = 3, we can write an explicit but much more complicated recipe for the coefficients of A, but for general n, it does not seem to be possible. Thus for n ≥ 3, there does not seem to be any better solution than to try all possible HNF matrices A = (a_{i,j}) with a_{i,i} | d_{i} and

a_{i,i+1} ≡ 0 (mod a_{i,i}/ gcd(a_{i,i}, d_{i+1}/a_{i+1,i+1})) ,

which are easily seen to be necessary conditions.

Finally, we consider the question of computing the image of a subgroup of a group C by a surjective group homomorphism. The following algorithm answers this question immediately.

Algorithm 12 (Image of a subgroup). Let B = (B, D_{B}) and C = (C, D_{C}) be two finite Abelian groups written in Smith normal form, let ϕ be a group homomorphism from B to C, and finally let H be a subgroup of B defined by an HNF matrix A_{B} dividing D_{B}. This algorithm computes the HNF matrix A_{C} dividing D_{C} which defines the subgroup ϕ(H) of C. 1.[Compute matrix P] Using the solution to the discrete logarithm problem in C, compute a

matrix P such that ϕ(B) = CP. 2.[Apply Hermite] Let A_{C} be the Hermite normal form of the matrix (P A_{B}|D_{C}). Output A_{C} and terminate the algorithm.

Proof. The generators of H are by definition the entries of BA_{B}. Hence the generators of ϕ(H) are the entries of ϕ(B)A_{B} = CP A_{B}. Since CD_{C} = 1, it follows that the entries of C(P A_{B}|D_{C}) also generate ϕ(H). But the advantage of this last matrix is that it is of maximal rank (since D_{C} is), hence if A_{C} is its HNF, then CA_{C} generates ϕ(H) and A_{C} is an integral matrix in HNF. Furthermore, since it is obtained as the “matrix GCD” of P A_{B} and D_{C}, it divides D_{C}. Explicitly, let U be the unimodular matrix such

that (P A_{B}|D_{C})U = (0|A_{C}). Write in block matrix form, U^{−1} = ( \begin{matrix}U_{1} & U_{2} \\ U_{3} & U_{4} \end{matrix} ). Then

(P A_{B}|D_{C}) = (0|A_{C})U^{−1} from which it follows in particular that A_{C}U_{4} = D_{C}, hence A_{C}^{−1}D_{C} = U_{4} has indeed integral coefficients. ⊓ ⊔

References

[Coh] H. Cohen, A course in computational algebraic number theory, GTM 138, Springer-Verlag, Berlin, Heidelberg, New York, 1993.

[Co-Di-Ol] H. Cohen, F. Diaz y Diaz and M. Olivier, Computing ray class groups, conductors and discriminants, Proceedings ANTS II, Lecture Notes in Computer Science, vol. 1122, Springer-Verlag, pp. 49–57.

Laboratoire A2X, Université Bordeaux I, 351 cours de la Libération, 33405 Talence cedex E-mail: {cohen,diaz,olivier}@math.u-bordeaux.fr