Jean-Charles Faugère

David Lubicz

Damien Robert

Computing modular correspondences for abelian varieties

Keywords: Abelian varieties, Theta functions, Isogenies, Modular correspondences

published or not. The documents may come

Introduction

The aim of this paper is to compute a higher-dimensional analog of the classical modular polynomials Φ (X, Y ). We recall that Φ (X, Y ) is a polynomial with integer coefficients. Moreover, if j is the j-invariant associated to an elliptic curve E k over a field k then the roots of Φ (j, X) correspond to the j-invariants of elliptic curves that are -isogeneous to E k . These modular polynomials have important algorithmic applications. For instance, Atkin and Elkies (see [START_REF] Elkies | Elliptic and modular curves over finite fields and related computational issues[END_REF]) take advantage of the modular parametrisation of -torsion subgroups of an elliptic curve to improve the original point counting algorithm of Schoof [START_REF] Schoof | Counting points on elliptic curves over finite fields[END_REF].

In [Sat00], Satoh introduced an algorithm to count the number of rational points of an elliptic curve E k defined over a finite field k of small characteristic p that relies on the computation of the canonical lift of the j-invariant of E k . Here again it is possible to improve the original lifting algorithm of Satoh [START_REF] Vercauteren | A memory efficient version of Satoh's algorithm[END_REF][START_REF] Lercier | A quasi quadratic time algorithm for hyperelliptic curve point counting[END_REF] by solving over the p-adics the equation given by the modular polynomial Φ p (X, Y ).

This last algorithm has been improved by Kohel in [START_REF] Kohel | The AGM-X0(N ) Heegner point lifting algorithm and elliptic curve point counting[END_REF] using the notion of modular correspondence. For N a strictly positive integer, the modular curve X 0 (N ) parametrizes the set of isomorphism classes of elliptic curves together with an N -torsion subgroup. For instance, the curve X 0 (1) is just the line of jinvariants. Let p be prime to N . A map X 0 (pN ) → X 0 (N ) × X 0 (N ) is a modular correspondence if the image of each point represented by a pair (E, G), where G is a subgroup of order pN of E, is a couple ((E 1 , G 1 ), (E 2 , G 2 )) with E 1 = E and G 1 is the unique subgroup of index p of G, and E 2 = E/H where H is the unique subgroup of order p of G. In the case that the curve X 0 (N ) has genus zero, the correspondence can be expressed as a binary equation Φ(X, Y ) = 0 in X 0 (N ) × X 0 (N ) cutting out a curve isomorphic to X 0 (pN ) inside the product. For instance, if one considers the correspondence X 0 ( ) → X 0 (1) × X 0 (1) for a prime number then the polynomial defining its image in the product is the modular polynomial Φ (X, Y ).

In this paper, we are interested in the computation of an analog of modular correspondences for higher dimensional abelian varieties over a field k. We suppose that the characteristic of k is different from 2 and that it is possible to represent the elements of k and compute efficiently the addition and multiplication laws of k: this is the case for instance for finite fields of characteristic different from 2. We use a model of moduli space which is amenable to computations. We fix an integer g > 0 for the rest of the paper. In the following if n is a positive integer, n denotes the element (n, . . . , n) ∈ N g . We consider the set of triples of the form (A k , L , Θ B n ) where A k is a g dimensional abelian variety equipped with a symmetric ample line bundle L and a symmetric theta structure Θ B n of type n. Such a triple is called an abelian variety with an n-marking. To a triple (A k , L , Θ B n ), one can associate following [START_REF] Mumford | On the equations defining abelian varieties[END_REF] its theta null point (see Section 2). The locus of theta null points corresponding to the set of abelian varieties with an n-marking is a quasi-projective variety M n . Moreover, it is proved in [START_REF] Mumford | On the equations defining abelian varieties[END_REF] that if 8|n then M n is a classifying space for abelian varieties with an n-marking. We would like to compute an analog of modular correspondences in M n .

For this, let (A k , L , Θ A n ) be an abelian variety with a ( n)-marking. We suppose that and n are relatively prime. From the theta structure Θ A n , we deduce a decomposition of the kernel of the polarization K(L ) = K 1 (L )×K 2 (L ) into maximal isotropic subspaces for the commutator pairing associated to L . Let K(L )[ ] = K 1 (L )[ ] × K 2 (L )[ ] be the induced decomposition of the -torsion part of K(L ). Let B k be the quotient of A k by K 2 (L )[ ] and C k be the quotient of A k by K 1 (L )[ ]. In this paper, we show that the theta structure of type n of A k induces in a natural manner theta structures of type n on B k and C k . As a consequence, we obtain a modular correspondence, Φ : M n → M n × M n . In the projective coordinate system provided by theta constants, we give a system of equations for the image of M n in the product M n × M n as well as an efficient algorithm to compute, given the theta null point (b u ) u∈Z(n) of B k with a theta structure of type n, all the theta null points (c u ) u∈Z(n) of C k with a theta structure of type n such that ((b u ) u∈Z(n) , (c u ) u∈Z(n) ) is in the image of Φ . It should be remarked that in genus 1 our notion of modular correspondence does not coincide with the definition of [START_REF] Kohel | The AGM-X0(N ) Heegner point lifting algorithm and elliptic curve point counting[END_REF] which gives a parametrisation of -isogenies while with our definition with obtain a parametrisation of 2 -isogenies. Still in the case of genus 1, our modular correspondence can be used in the aforementioned applications. This paper is organized as follows. In Section 2 we recall some basic definitions and properties relating to algebraic theta functions. In Section 3, we define formally the modular correspondence, and then in Section 4 we give explicit equations for the computation of this correspondence. In particular, given the theta null an abelian variety B k with an n-marking, we define a polynomial system (the equations of the image of M n ), of which the solutions give theta null points of varities isogenous to B k . In Section 5, we describe the geometry of these solutions. The last section is devoted to the description of a fast algorithm compute the solutions.

Some notations and basic facts

In this section, we fix some notations for the rest of the paper and recall well known results on abelian varieties and theta structures.

Let A k be a g-dimensional abelian variety over a field k. Let L be a degree-d ample symmetric line bundle on A k . From here, we suppose that d is prime to the characteristic of k. Denote by K(L ) the group given by the geometric points in the kernel of the polarization corresponding to L and by G(L ) the theta group (see [START_REF] Mumford | On the equations defining abelian varieties[END_REF]p. 289]) associated to L . For x a geometric point of A k , we denote by τ x the translation by x map on A k . The theta group G(L ) (see the definition of [START_REF] Mumford | On the equations defining abelian varieties[END_REF]p. 289]) is by definition the group (representable by a group scheme by [Mum84, prop. 1]) given by the set of pairs (x, ψ), where x is a point of K(L ) and ψ is an isomorphism of line bundles ψ : L → τ *

x L , together with the composition law (x, ψ) • (y, ϕ) = (x + y, τ * y ψ • ϕ). Let δ = (δ 1 , . . . , δ g ) be a finite sequence of integers such that δ i |δ i+1 . We consider the finite group Z(δ) = (Z/δ 1 Z) × . . . × (Z/δ g Z) with elementary divisors given by δ. For a well chosen unique δ, the finite group K(δ) = Z(δ) × Ẑ(δ) (where Ẑ(δ) is the Cartier dual of Z(δ)) is isomorphic to K(L ) (see [START_REF] Mumford | Abelian varieties[END_REF]p. 132]). We note G m,k the group k * . The Heisenberg group of type δ is the group

H(δ) = G m,k × Z(δ) × Ẑ(δ)
together with the group law defined on points by (α, x 1 , x 2 ).(β, y 1 , y 2 ) = (α.β.y 2 (x 1 ), x 1 + y 1 , x 2 + y 2 ). We recall (see [START_REF] Mumford | On the equations defining abelian varieties[END_REF]cor. of Th. 1, p. 294]) that a theta structure Θ δ of type δ is an isomorphism of central extensions from H(δ) to G(L ) fitting in the following diagram:

0 / / G m,k / / H(δ) / / Θ δ K(δ) / / Θ δ 0 0 / / G m,k / / G(L ) κ / / K(L ) / / 0 , ( 1
)
where κ is the natural projection. We note that Θ δ induces an isomorphism, denoted Θ δ in the preceding diagram, from K(δ) into K(L ) and as a consequence a decomposition K(L ) = K 1 (L ) × K 2 (L ) where K 2 (L ) is the Cartier dual of K 1 (L ). As it will be explained shortly, the data of a triple (A k , L , Θ δ ) defines a basis of global sections of L that we denote (ϑ i ) i∈Z(δ) and as a consequence an morphism of A k into P d-1 k where d = g i=1 δ i is the degree of L . We recall the construction of this basis. We recall ([Mum66, p. 291]) that a level subgroup K of G(L ) is a subgroup such that K is isomorphic to its image by κ in K(L ) where κ is defined in (1). We define the maximal level subgroups K1 over K 1 (L ) and K2 over K 2 (L ) as the image by Θ δ of the subgroups (1, x, 0) x∈Z(δ) and (1, 0, y) y∈ Ẑ(δ) of H(δ). Let A 0 k be the quotient of A k by K 2 (L ) and π : A k → A 0 k be the natural projection. By the descent theory of Grothendieck (see [START_REF] Mumford | On the equations defining abelian varieties[END_REF]p. 290]), the data of K2 is equivalent to the data of a couple (L 0 , λ) where L 0 is a degree-one ample line bundle on A 0 k and λ is an isomorphism λ : π * (L 0 ) → L . Let s 0 be the unique global section of L 0 up to a constant factor and let s = λ(π * (s 0 )). We have the following proposition which is an immediate consequence of [Mum66, th. 2 p. 297] and Step I of [START_REF] Mumford | On the equations defining abelian varieties[END_REF]:

Proposition 1: For all i ∈ Z(δ), let (x i , ψ i ) = Θ δ ((1, i, 0)). We set ϑ Θ δ i = (τ * -xi ψ i (s)).
The elements (ϑ Θ δ i ) i∈Z(δ) form a basis of the global sections of L which is uniquely determined, up to a multiplication by a factor independent of i, by the data of Θ δ .

If no ambiguity is possible, we let ϑ Θ δ i = ϑ i for i ∈ Z(δ). The image of the zero point 0 of A k by the projective embeding defined by Θ δ , which has homogeneous coordinates (ϑ i (0)) i∈Z(δ) , is by definition the theta null point associated to (A k , L , Θ δ ). If Θ δ is symmetric [Mum66, p. 308 and p. 317], we say that (A k , L , Θ δ ) is an abelian variety with a δ-marking. The locus of the theta null points associated to abelian varieties with a δ-marking is a quasi-projective variety denoted M δ .

Let (A k , L , Θ δ ) be an abelian variety with a δ-marking. We recall that the natural action of G(L ) on the global sections of L is given by (x, ψ).f = τ * -x ψ(f ) for f ∈ Γ (L ) and (x, ψ) ∈ G(L ). There is an action of H(δ) on the global sections of L . After an immediate computation using the group law of H(δ) and the definition of (ϑ i ) i∈Z(δ) given by Proposition 1, on obtains the following expression for this action:

(α, i, j).ϑ m = αe δ (m + i, -j)ϑ m+i , (2)
for (α, i, j) ∈ H(δ) and e δ the commutator pairing on K(δ). By construction, this action is compatible via Θ δ with the natural action of G(L ) on (ϑ i ) i∈Z(δ) . Using (2), one can compute the coordinates in the projective system given by the (ϑ i ) i∈Z(δ) of any point of K(L ) from the theta null point associated to (A k , L , Θ δ ). Indeed, let (x, ψ) ∈ G(L ) be any lift of x ∈ K(L ) and let (α, i, j) = Θ -1 δ ((x, ψ)) then the coordinates of x in the projective system given by the (ϑ i ) i∈Z(δ) are ((α, i, j).ϑ m )(0)) m∈Z(δ) .

For δ = (δ 1 , . . . , δ g ) ∈ N g and δ = (δ 1 , . . . , δ g ) ∈ N g , we write δ|δ if for i = 1, . . . , g, we have δ i |δ i . If n ∈ N, then n|δ means that n|δ i for all i. If δ|δ , then we have the usual embedding

i : Z(δ) → Z(δ ), (x i ) i∈{1,...,g} → (δ i /δ i .x i ).
(3)

A basic ingredient of our algorithm is given by the Riemann relations which are algebraic relations satisfied by the theta null values if 2|δ.

Theorem 2 (Mumdord [Mum66] p. 333): Denote by Ẑ(2) the dual group of Z(2). Let (a i ) i∈Z(δ) be the theta null point associated to an abelian variety with a δ-marking (A k , L , Θ δ ) where 2|δ and δ is not divisible by the characteristic of k. For all x, y, u, v ∈ Z(2δ) that are congruent modulo 2Z(2δ), and all χ ∈ Ẑ(2), we have

t∈Z(2) χ(t)ϑ x+y+t ϑ x-y+t . t∈Z(2) χ(t)a u+v+t a u-v+t = = t∈Z(2) χ(t)ϑ x+u+t ϑ x-u+t . t∈Z(2) χ(t)a y+v+t a y-v+t .
Here we embed Z(2) into Z(δ) and Z(δ) into Z(2δ) using (3). A consequence of Theorem 2 is the fact that if 4|δ, from the knowledge of a valid theta null point (a i ) i∈Z(δ) , one can recover a couple (A k , L ) which it comes from. In fact, the abelian variety A k is defined by the homogeneous equations of Theorem 2. Moreover, from the knowledge of the projective embedding of A k , one recover immediately L by pulling back the sheaf O(1) of the projective space.

An immediate consequence of the preceding theorem is the Theorem 4: Let (a i ) i∈Z(δ) be the theta null point associated to an abelian variety with a δ-marking (A k , L , Θ δ ) where 2|δ. For all x, y, u, v ∈ Z(2δ) that are congruent modulo 2Z(2δ), and all χ ∈ Ẑ(2), we have

t∈Z(2) χ(t)a x+y+t a x-y+t . t∈Z(2) χ(t)a u+v+t a u-v+t = = t∈Z(2) χ(t)a x+u+t a x-u+t . t∈Z(2) χ(t)a y+v+t a y-v+t .
As Θ δ is symmetric, the theta constants also satisfy the additional symmetry relations a i = a -i , i ∈ Z(δ).

Theorem 4 gives equations satisfied by the theta null points of abelian varieties together with a δ-marking. Let M δ be the projective variety over k defined by the relations from Theorem 4. Mumford proved in [Mum67a, p. 83] the following Theorem 5: Suppose that 8|δ. Then 1. M δ is a classifying space for abelian varieties with a δ-marking: to a theta null point corresponds a unique triple

(A k , L , Θ δ ). 2. M δ is an open subset of M δ .
A geometric point P of M δ is called a theta constant. If a theta constant P is in M δ we say that P is a valid theta null point, otherwise we say that P is a degenerate theta null point.

Remark 6: As the results of Section 5 show, M δ may not be a projective closure of M δ . Nonetheless, every degenerate theta null point can be obtained from a valid theta null point by a "degenerate" group action (see the discussion after Proposition 18), hence the terminology.

Theta null points and isogenies

Let k be a field. Let and n be relatively prime integers and suppose that n is divisible by 2 and that n is prime to the characteristic of k. Let (A k , L , Θ A n ) be a g-dimensional abelian variety together with an ( n)-marking. We recall from just above Proposition 1 that the theta structure Θ A n induces a decomposition of the kernel of the polarization

K(L ) = K 1 (L ) × K 2 (L ) (4)
into maximal isotropic subgroups for the commutator pairing associated to L . Let K be either

K 1 (L )[ ] or K 2 (L )[ ].
There are two possible choices for K, one contained in K 1 (L ), the other one in K 2 (L ). In the next subsection, we explain that a choice of K determines a certain abelian variety together with an n-marking. The main results of this section are Corollary 8 and Proposition 9, which explain how its theta null point is related to A.

The isogenies defined by K

Let X k be the quotient of A k by K and let π : A k → X k be the natural projection. Let κ : G(L ) → K(L ) be the natural projection. As K is a subgroup of K(L ), we can consider the subgroup G of G(L ) defined as G = κ -1 (K). Let K be the level subgroup of G(L ) defined as the intersection of G with the image of (1, x, y)

(x,y)∈Z( n)× Ẑ( n) ⊂ H( n) by Θ A n .
By the descent theory of Grothendieck, we know that the data of K is equivalent to the data of a line bundle X on X k and an isomorphism λ : π * (X ) → L . Now, we explain that the ( n)-marking on A k induces an n-marking on X k . Let G * (L ) be the centralizer of K in G(L ). Applying [Mum66, Proposition 2 p. 291], we obtain an isomorphism

G * (L )/ K G(X ) (5)
and as a consequence a natural projection q :

G * (L ) → G(X ). As H(n) is generated by the subgroups G m × 0 × 0, 1 Gm × Z(n) × 0 Ẑ(n) and 1 Gm × 0 Z(n) × Ẑ(n), in order to define a theta structure Θ B n : H(n) → G(X ), it is enough to give morphisms 1 Gm ×Z(n)×0 Ẑ(n) → G(X ) and 1 Gm ×0 Z(n) × Ẑ(n) → G(X ) such that the resulting Θ B n is an isomorphism. Let Z * ( n), Ẑ * ( n), K * 1 and K * 2 be such that 1 Gm × Z * ( n) × 0 Ẑ( n) = Θ A n -1 (G * (L )) ∩ (1 Gm × Z( n) × 0 Ẑ( n) ), 1 Gm × 0 Z( n) × Ẑ * ( n) = Θ A n -1 (G * (L )) ∩ (1 Gm × 0 Z( n) × Ẑ( n)), 1 Gm × K * 1 × 0 Ẑ( n) = Θ A n -1 ( K) ∩ (1 Gm × Z( n) × 0 Ẑ( n) ), 1 Gm × 0 Z( n) × K * 2 = Θ A n -1 ( K) ∩ (1 Gm × 0 Z( n) × Ẑ( n)).
There are natural isomorphisms Z * ( n)/K * 1 Z(n) and Ẑ * ( n)/K * 2 Ẑ(n) from which we deduce projections p 1 : Z * ( n) → Z(n) and p 2 : Ẑ * ( n) → Ẑ(n) (compare with the diagram of [START_REF] Mumford | On the equations defining abelian varieties[END_REF]p. 303]).

We define Θ B n as the unique theta structure for X such that the following diagrams are commutative

(1, x, 0) x∈Z * ( n) p1 Θ A n / / G * (L ) q (1, x, 0) x∈Z(n) Θ B n / / G(X ) , (6)
(1, 0, y

) y∈ Ẑ * ( n) p2 Θ A n / / G * (L ) q (1, 0, y) y∈ Ẑ(n) Θ B n / / G(X ) , ( 7
)
where p1 is induced by p 1 and p2 is induced by p 2 . Using the fact that Θ A n is symmetric, it is easy to see that Θ B n is also symmetric. We say that the theta structures Θ A n and Θ B n are π-compatible (or compatible) if the diagrams (6) and (7) commute.

Let K 1 and K 2 be the maximal -torsion subgroups of respectively K 1 (L ) and K 2 (L ). By taking K = K 2 and K = K 1 in the preceding construction, we obtain respectively (B k , L 0 , Θ B n ) and (C k , L 1 , Θ C n ) two abelian varieties with an n-marking. As a consequence, we have a well defined modular correspondence

Φ : M n → M n × M n . (8)
Let π : A k → B k and π : A k → C k be the isogenies from the construction. Let [ ] be the isogeny of multiplication by on B k and let π : B k → A k be the isogeny such that [ ] = π • π. From the symmetry of L we deduce that L 0 is symmetric and by applying the formula of [Mum66, p. 289], we have [ ] * L 0 = L 2 0 . Denote by K π the kernel of π . Then π(K π ) = π(A k [ ]) so this subgroup of B k is exactly the kernel of π:

B k [ ] π ! ! A k π } } π B k C k (9)
3.2 The theta null points defined by K

The following two propositions explain the relation between the theta null point of (A k , L , Θ A n ) and the theta null points of (B k , L 0 , Θ B n ) and (C k , L 1 , Θ C n ). Keeping the notations of the previous paragraph, we have

Proposition 7: Let (A k , L , Θ A n ), (B k , L 0 , Θ B n
) and π : A k → B k be defined as above. There exists a constant factor ω ∈ k such that for all i ∈ Z(n), we have

π * (ϑ Θ B n i ) = ωϑ Θ A n i . (10)
In this identity, Z(n) is identified with a subgroup of Z( n) via the map x → x.

Proof: The theta structure Θ A n (resp. Θ B n ) induces a decomposition of the kernel of the polarization

K(L ) = K 1 (L )×K 2 (L ) (resp. K(L 0 ) = K 1 (L 0 )×K 2 (L 0 )). Denote by K 2 the kernel of π. We have that K 2 is a subgroup of K(L ) contained in K 2 (L ).
The hypotheses of [START_REF] Mumford | On the equations defining abelian varieties[END_REF]Th. 4] are verified by construction of Θ B n and Equation ( 10) is an immediate application of this theorem.

As an immediate consequence of the preceding proposition, we have

Corollary 8: Let (A k , L , Θ A n ) and (B k , L 0 , Θ B n ) be defined as above. Let (a u ) u∈Z( n) and (b u ) u∈Z(n) be theta null points respectively associated to (A k , L , Θ A n ) and (B k , L 0 , Θ B n ).
Considering Z(n) as a subgroup of Z( n) via the map x → x, there exists a constant factor ω ∈ k such that for all u ∈ Z(n), b u = ωa u .

Proposition 9: Let (A k , L , Θ A n ) and (C k , L 0 , Θ B n ) be defined as above. Let (a u ) u∈Z( n) and (c u ) u∈Z(n) be the theta null points respectively associated to

(A k , L , Θ A n ) and (C k , L 1 , Θ C n ).
We have for all u ∈ Z(n),

c u = t∈Z( ) a u+t , (11)
where Z(n) and Z( ) are considered as subgroups of Z( n) via the maps j → j and j → nj.

Proof: The proof follows the same line as that of Proposition 7. The theta structure Θ A n (resp. Θ C n ) induces a decomposition of the kernel of the polarization

K(L ) = K 1 (L ) × K 2 (L ) (resp. K(L 1 ) = K 1 (L 1 ) × K 2 (L 1 )
). Denote by K 1 the kernel of π . We have that K 1 is a subgroup of K 1 (L ) and we have an isomorphism:

σ : K 1 (L )/K 1 → K 1 (L 1 ),
which translate via Θ A n and Θ C n into the natural isomorphism

σ 0 : Z( n)/Z( ) → Z(n).
The hypotheses of [START_REF] Mumford | On the equations defining abelian varieties[END_REF]Th. 4] are then verified and Equation ( 11) is an immediate application of this theorem.

The image of the modular correspondence

In this section, we use the results of the previous section in order to give equations for the image of the modular correspondence Φ given by (8). That is, for a given point x of M n , we give equations for the set of points in M n that correspond to x via the map defined by Φ (M n ).

In order to make this precise, we let (B k , L 0 , Θ B n ) be an abelian variety together with an n-marking and denote by (b u ) u∈Z(n) its associated theta null point. Unless specified, we shall assume that 4 | n.

Denote by p 1 (resp. p 2 ) the first (resp. second) projection from M n × M n into M n , and let

π 1 = p 1 • Φ , π 2 = p 2 • Φ . We would like to compute the algebraic set π 2 (π -1 1 ((b u ) u∈Z(n)
)) which we call the image of the modular correspondence. We remark that this question is the analog in our situation of the computation of the solutions of the equation Φ (j, X) obtained by substituting in the modular polynomial Φ a certain j-invariant j ∈ k. The only difference is that our modular correspondence parametrizes 2 -isogenies while the usual one deals with -isogenies. Let P

Z( n) k = Proj(k[x u |u ∈ Z( n)]
) be the ambient projective space of M n , and let I be the homogeneous ideal defining M n , which is spanned by the relations of Theorem 4, together with the symmetry relations. Let J be the image of I under the specialization map

k[x u |u ∈ Z( n)] → k[x u |u ∈ Z( n), nu = 0], x u → b u , if u ∈ Z(n) x u , else .
and let V J be the affine variety defined by J.

Let π0

1 : P Z( n) k → P Z(n) k
and π0

2 : P Z( n) k → P Z(n) k
be the rational maps of the ambient projective spaces respectively defined on geometric points by (a u ) u∈Z( n) → (a u ) u∈Z(n) and (a u ) u∈Z( n) → ( t∈Z( ) a u+t ) u∈Z(n) . Clearly, π 1 and π 2 are the restrictions of π0

1 and π0 2 to M n . The rational map π0 1 (resp π0

2 ) restricts to a rational map π1 :

M n → M n (resp π2 : M n → M n ). By definition of J, we have V J = π-1 1 ((b u ) u∈Z(n) ). Let S = k[y u , x v |u ∈ Z(n), v ∈ Z( n)], we can consider J as a subset of S via the natural inclusion of k[x u |u ∈ Z( n)] into S.
Let L be the ideal of S generated by J together with the elements y u -t∈Z( ) x u+t and let

L = L ∩k[y u |u ∈ Z(n)]. Let V L be the subvariety of A Z(n) defined by the ideal L. By the definition of L, V L is the image by π2 of the fiber V J , so that V L = π2 (π -1 1 ((b u ) u∈Z(n) )).
Proposition 10: Keeping the notations from above, we suppose that 4 | n and let

(b u ) u∈Z(n) be the geometric point of M n corresponding to (B k , L 0 , Θ B n ). The algebraic variety V 0 L = π 2 (π -1 1 (b u ) u∈Z(n) )
has dimension 0 and is isomorphic to a subvariety of V L .

Proof: From the preceding discussion the only thing left to prove is that V 0 L has dimension 0. But this follows from the fact that the algebraic variety V J has dimension 0 [CL09, Th. 2.7] which generalize easily to the case where n is not a power of 2.

From an algorithmic point of view, with our method the hard part of the computation of the modular correspondence is the computation of

V 0 J = π -1 1 ((b u ) u∈Z(n)
), the set of points in V J that are valid theta null points. From now on, we consider only V 0 J , since computing V 0 L from it is trivial by Proposition 9.

We proceed in two steps. First we compute the solutions in V J using a specialized Gröbner basis algorithm (Section 6.3) and then we detect the valid theta null points using the results of Section 5 (see Theorem 23). But first we recall the moduli interpretation of V 0 J given by Section 3:

Proposition 11: We suppose that 4 | n, then V 0 J is the locus of theta null points (a u ) u∈Z( n) in M n such that if (A k , L , Θ n ) is the corresponding variety with an ( n)-marking then Θ A n is compatible with the theta structure Θ B n of B k . Proof: Let (a u ) u∈Z( n) be a geometric point of V 0 J . Let (A k , L , Θ n
) be a corresponding variety with ( n)-marking. If we apply the construction of Section 3, we get an abelian variety (B k , L 0 , Θ n ) with an n-marking and an isogeny π :

A k → B k such that Θ A n is compatible with Θ n . By definition of J, Corollary 8 shows that the theta null point of B is (b u ) u∈Z(n) . As 4 | n, the paragraph directly below Theorem 2 shows that (B k , L 0 ) (B k , L 0 ). By [Mum67b, p. 82] we then have that the triples (B k , L 0 , Θ n ) and (B k , L 0 , Θ n ) are isomorphic, so that Θ A n is compatible with Θ B n .
Let B k and V J be as in the previous section. This section is devoted to the study of the geometric points of V J . Our aim is twofold. First we need a way to identify degenerate theta null points in V J , and then we would like to know when two geometric points in V J correspond to isomorphic varieties. If (a u ) u∈Z( n) is a valid theta null point in V J , let (A k , L , Θ n ) be the corresponding abelian variety with an ( n)-marking and denote by π :

A k → B k the isogeny defined in Section 3. We denote by G((a u ) u∈Z( n) ) the subgroup π(A k [ ]) of B k which is isomorphic to Z( ).
From the knowledge of (a u ) u∈Z( n) , one can recover the coordinates of the points G((a u ) u∈Z( n) ). We study the image of the map G in Section 5.1, and study its fiber in Section 5.3. For this, we introduce an action of the automorphisms of the theta group H(δ) on the modular space M n in Section 5.2. In particular, we explain when two valid points give isomorphic varieties in Proposition 20. In Section 5.4 we extend the map (a u ) u∈Z( n) → G((a u ) u∈Z( n) ) to non valid theta null point in V J . The main result of this section is Theorem 23 which states that a geometric point of V J is valid if and only if the associated subgroup is isomorphic to Z( ). We then show how to obtain all degenerate points at the end of Section 5.4. In Section 5.5 we illustrate the previous results with some examples.

A group associated to valid theta null points of

V J Suppose that (a v ) v∈Z( n) is a valid theta null point in V 0 J . Let (A k , L , Θ A n )
be the corresponding abelian variety with an ( n)-marking and denote by π : A k → B k the isogeny defined in Section 3. We recall that the kernel of π is K 2 , where A[ ] = K 1 × K 2 is the symplectic decomposition introduced in Section 3.1. Then π(K 1 ) is the kernel of the contragredient isogeny π : B k → A k . We denote this kernel by G((a u ) u∈Z( n) ). More explicitly, we can consider A k as a closed subvariety of P Z( n) k via the embedding provided by Θ A n . Using the action (2) of the theta group on (a v ) v∈Z( n) , one sees that for i ∈ Z( ), the point with homogeneous

coordinates (a v+ni ) v∈Z( n) corresponds via Θ A n to the point Θ A n (i) of the - torsion subgroup K 1 of A k (k) (with the notations of Section 3). By definition of the isogeny π, we then have G((a u ) u∈Z( n) ) = π(K 1 ) = P i , i ∈ Z( ) , where P i = (a ni+ j ) j∈Z(n) . We want to determine the set of such groups G((a u ) u∈Z( n) ) as (a u ) u∈Z( n) goes through the geometric points of V 0 J . For this, let M 0 = [ ] * L 0 on B k . As L 0 is symmetric, we have that M 0 L 2 0 and as a consequence K(M 0 ), the kernel of M 0 is isomorphic over k to Z( 2 n).
The polarisation M 0 induces a commutator pairing e M0 on K(M 0 ) and as M 0 descends to L 0 via the isogeny [ ], we know that e M0 is trivial on B

k [ ]. For x 1 , x 2 ∈ B k [ ], let x 1 , x 2 ∈ B k [ 2 ]
be such that .x i = x i for i = 1, 2. We remark that x 1 and x 2 are defined up to an element of B k [ ]. As a consequence, e M0 (x 1 , x 2 ) = e M0 (x 1 , x 2 ), does not depend on the choice of x 1 and x 2 and if we put e W (x 1 , x 2 ) = e M0 (x 1 , x 2 ), we obtain a well defined bilinear map e

W : B k [ ] × B k [ ] → k. As e M0 is a perfect pairing, for any x 1 ∈ B k [ 2 ] there exits x 2 ∈ B k [ 2 ]
such that e M0 (x 1 , x 2 ) is a primitive 2 th root of unity. As a consequence, for any x 1 ∈ B k [ ] there exists x 2 ∈ B k [ ] such that e W (x 1 , x 2 ) is a primitive th root of unity and e W is also a perfect pairing. By [START_REF] Mumford | Abelian varieties[END_REF]p. 228], the pairing e W is the restriction of the commutator pairing e L 0 on

B k [ ] × B k [ ].
We then have:

Theorem 12: Let G be a subgroup of B k [ ].
Then the following are equivalent:

1. there exists a geometric point (a u ) u∈Z( n) of V 0 J corresponding to a valid theta null point such that G equals G((a u ) u∈Z( n) ); 2. G is an isotropic subgroup for the pairing e W isomorphic to Z( ).

Proof: Let (a u ) u∈Z( n) be a geometric point of V J corresponding to a valid theta null point. We know that (a u ) u∈Z( n) is the theta null point of a triple

(A k , L , Θ A n ). The theta structure Θ A n induces a decomposition K(L ) = K 1 (L )× K 2 (L ) into isotropic subgroups for the commutator pairing e L . As the isogeny π is such that π * (ϑ Θ B n i ) = ϑ Θ A n i for all i ∈ Z(n) (and identifying i ∈ Z(n) with i ∈ Z( n)), we know that G((a u ) u∈Z( n) ) = π(K 1 (L )). We denote by π : B k → A k the isogeny such that π • π = [ ] as in the diagram (9). For any x 1 , x 2 ∈ G((a u ) u∈Z( n) ), there exists x 1 , x 2 ∈ K 1 (L )[ ] such that x i = π(x i ), i = 1, 2. Let x 1 ∈ B k [ 2 ] be such that .x 1 = x 1 . We have e W (x 1 , x 2 ) = e M0 (x 1 , x 2 ) = e L (π(x 1 ), π(x 2 )). But π(x 2 ) = π • π(x 2 ) = [ ](x 2 ) = 0.
As a consequence, we have e W (x 1 , x 2 ) = 0. Now, we prove the opposite direction. Let G be an -torsion subgroup of B k [ ] isomorphic to Z( ) which is isotropic for the pairing e W and Ĝ be the dual group of G for the pairing e W . As e W is a perfect pairing, Ĝ is also a maximal rank g -torsion subgroup of B k [ ]. We want to show that G is of the form G(x) with x a geometric point of V J where J is defined by the triple (B k , L 0 , Θ B n ). For this, we consider the isogeny π :

B k → A k with kernel the subgroup G of B k . As G is contained in B k [ ],
G is an isotropic subgroup of (B k , M 0 ), and M 0 descends via π to a polarization L on A k . Let π : A k → B k be the isogeny with kernel π( Ĝ). By the commutativity of the following diagram,

(B k , M 0 ) [ ] π & & (A k , L ) π x x (B k , L 0 ) , (12)
L descends via π to L 0 .

The theta structure Θ B n induces a decomposition

K(L 0 ) = K 1 (L 0 ) × K 2 (L 0 ). Let x i = π(x i ) with x i ∈ Ĝ and i = 1, 2. Let y 1 ∈ B k [ 2 ] be such that .y 1 = x 1 .
We have by hypothesis 1 = e W (x 1 , x 2 ) = e M0 (y 1 , x 2 ) and as a consequence 1 = e M0 (x 1 , x 2 ) = e L (x 1 , x 2 ). Thus π( Ĝ) is isotropic for the pairing e L . As a consequence, we can chose a decomposition

K(L ) = K 1 (L ) × K 2 (L ) such that for i = 1, 2, π(K i (L )) = K i (L 0 ) and K 2 (L )[ ] = π( Ĝ)
. Take any theta structure Θ A n for L compatible with this decomposition. Let (a u ) u∈Z( n) be the associated theta null point. By Corollary 8, (a u ) u∈Z( n) is a geometric point of

V J . Moreover, we have G((a u ) u∈Z( n) ) = π(K 1 (L )) = G.
We want to study the structure of the fibres of a given subgroup

G of B k [ ], under the map (a u ) u∈Z( n) → G((a u ) u∈Z( n) ) for (a u ) u∈Z( n) a geometric point of V 0 J .
For this we need to study how a theta null point varies with a change of theta structure.

5.2

The action of the theta group on V 0 J We denote by Aut Gm H(δ) the group of automorphisms ψ of H(δ) inducing the identity on G m,k , i.e., the group of automorphisms ψ fitting in a diagram of the form 0

/ / G m,k / / H(δ) / / ψ K(δ) / / ψ 0 0 / / G m,k / / H(δ) / / K(δ) / / 0 . (13)
Obviously, the set of all theta structures for L is a principal homogeneous space for the group Aut Gm H(δ) via the right action Θ δ .ψ = Θ δ • ψ for ψ ∈ Aut Gm H(δ) and Θ δ a theta structure. So we can identify Aut Gm H(δ) with the group of change of theta structures. If ψ is an automorphism fitting in diagram (13), it induces an automorphism ψ of K(δ). The commutativity of diagram (13) shows that ψ is symplectic with respect to the commutator pairing, i.e., we have for all x 1 , x 2 ∈ K(δ), e δ (ψ(x 1 ), ψ(x 2 )) = e δ (x 1 , x 2 ). Denote by Sp(K(δ)) the group of symplectic automorphisms of K(δ). In order to study the possible extensions of ψ ∈ Sp(K(δ)) to an element of Aut Gm H(δ) it is convenient to introduce the following definition:

Definition 13: Let ψ ∈ Sp(K(δ)). A ψ-semi-character (or a semi-character if no confusion is possible) for the canonical pairing is a map χ ψ : K(δ) → G m,k such that for (x 1 , x 2 ), (x 1 , x 2 ) ∈ K(δ), χ ψ ((x 1 + x 1 , x 2 + x 2 )) = χ ψ ((x 1 , x 2 )). χ ψ ((x 1 , x 2 )).[ψ(x 1 , x 2 ) 2 (ψ(x 1 , x 2 ) 1 )], (14)
where we write ψ(

x 1 , x 2 ) = (ψ(x 1 , x 2 ) 1 , ψ(x 1 , x 2 ) 2 ) (resp. ψ(x 1 , x 2 ) = (ψ(x 1 , x 2 ) 1 , ψ(x 1 , x 2 ) 2 ) in the canonical decomposition of K(δ). A semi-character χ ψ is said to be sym- metric if for all (x 1 , x 2 ) ∈ K(δ), χ ψ (-(x 1 , x 2 )) = χ ψ ((x 1 , x 2 )).
The preceding definition is motivated by the lemma: Lemma 14: Let ψ ∈ Aut Gm H(δ) and let ψ be the associated symplectic automorphism of K(δ). There exists a unique semi-character χ ψ such that for all (α, (x 1 , x 2 )) ∈ H(δ),

ψ : (α, (x 1 , x 2 )) → (αχ ψ ((x 1 , x 2 )), ψ((x 1 , x 2 )). ( 15
)
As a consequence, if ψ ∈ Sp(K(δ)) there is a one on one correspondence between the set of extensions of ψ to Aut Gm H(δ) and the set of semi-characters.

Proof: Note that (15) uniquely defines a map χ ψ given ψ, and conversely, also uniquely defines a map ψ given ψ and χ ψ . Moreover, by writing out the definitions, it follows that χ ψ is a semi-character if and only if ψ is a homomorphism.

Let ψ ∈ Sp(K(δ)). If we want to show that ψ admits an extension to H(δ), by the preceding lemma, it suffices to show that there exists a ψ-semi-character.

Lemma 15: Let B = (v κ , v κ+g ) κ∈{1,...,g} be a basis of K(δ). Let ψ ∈ Sp(K(δ)).

For κ ∈ {1, . . . , 2g} let κ be the order of v κ in K(δ) and let t κ be an th κroot of unity. There exists a unique semi-character χ ψ such that χ ψ (v κ ) = t κ . Suppose that 2|δ, then this semi-character is symmetric if and only if for all κ ∈ {1, . . . , 2g}, t κ ∈ {-1, 1}.

Proof: By definition of a semi-character, there exists a function Φ :

K(δ)×G m,k × K(δ) × G m,k → G m,
k such that for every semi-character χ ψ and x, y ∈ K(δ) we have χ ψ (x + y) = Φ(x, χ ψ (x), y, χ ψ (y)). Recall that for (u, v), (u , v ) ∈ K(δ), we have

e δ ((u, v), (u , v )) = v (u).v(u ) -1 . (16)
Using (15) and the fact that ψ is simplectic, we obtain that for x, y ∈ K(δ), Φ(x, χ ψ (x), y, χ ψ (y)) = Φ(y, χ ψ (y), x, χ ψ (x)). An easy computation shows that for x, y, z ∈ K(δ), Φ(x + y, χ ψ (x + y), z, χ ψ (z)) = Φ(x, χ ψ (x), y + z, χ ψ (y + z)). Moreover, we have

χ ψ (0) = 1 G m,k and for (u, v) ∈ K(δ), χ ψ (-(u, v)) = χ ψ ((u, v)) -1 ψ(v)(ψ(u)) -1 .
Let Z B be the free commutative group over the basis B and denote by π 0 : Z B → K(δ) the canonical projection. The preceding properties show that the map B → G m,k , v κ → t κ extends to a well defined semi-character χψ :

Z B → G m,k such that for (u, v), (u , v ) ∈ Z B χψ ((u + u , v + v )) = χψ ((u, v)). χψ ((u , v )).ψ(π 0 (v ))ψ((π 0 (u))).
In order to finish the proof, we just have to prove that χ induces a well defined map on K(δ). For this it is enough to prove that for all x ∈ ker π 0 , χψ (x) = 1 and finaly we have to check that for all i ∈ {1, . . . , 2g}, χψ ( i v i ) = 1. But an easy recursion shows that for all k ∈ N, χψ (k.v i ) = χψ (v i ) k and as a consequence, we have that χψ ( i .v i ) = 1 if and only if χψ (v i ) is a th i -root of unity. This concludes the proof of the first claim of the lemma.

If χ ψ is symmetric then for all i ∈ {1, . . . , 2g}, and for k ∈ {0, . . . , i -1}, we have χ

ψ (k.v i ) = χ ψ (v i ) k = χ ψ (( i -k).v i ) = χ ψ (v i ) i-k .
As a consequence, we have for all k ∈ {0, . . . , i -1}, χ ψ (v i ) 2k = 1 and in particular χ ψ (v i ) 2 = 1.

If ψ ∈ Sp(K(δ)) and χ ψ is a semi-character, in the following, we denote by σ χ ψ (ψ) the associated automorphism of H(δ). The kernel of the group morphism Ψ : Aut Gm H(δ) → Sp(K(δ)), ψ → ψ consists of automorphisms that preserve a symplectic basis. Such automorphisms are determined by a choice of level subgroups K1 and K2 over the maximal isotropic subspaces Z(δ) and Ẑ(δ). As follows, this data defines a ψ by letting for all x ∈ Z(δ), ψ((1, x, 0)) = (α, x, 0) where (α, x, 0) ∈ K1 and for all y ∈ Ẑ(δ), ψ((1, 0, y)) = (α, 0, y) where (α, 0, y) ∈ K2 . It is well known (see the proof of [BL04, Lem. 6.6.5 p. 162] which can easily be extended to the case of a general base field) that such choices are in bijection with elements c ∈ K(δ): we map c ∈ K(δ) to the automorphism of H(δ) given by (α, x, y) → (αe δ (c, (x, y)), x, y).

(

) 17
As a consequence, we get an exact sequence

0 / / K(δ) / / Aut Gm H(δ) Ψ / / Sp(K(δ)) / / 0 . (18)
Suppose that Θ δ is symmetric. An automorphism ψ ∈ Aut Gm H(δ) is said to be symmetric if it commutes with the action (α, x, y) → (α, -x, -y) on H(δ).

We denote by Aut Gm,s H(δ) the group of symmetric automorphisms of H(δ).

Obviously, an automorphism ψ ∈ Aut Gm H(δ) coming from c ∈ K(δ) is symmetric if and only if c ∈ K(δ)[2], the subgroup of 2-torsion of K(δ). Now consider (A k , L , Θ δ ) an abelian variety with a δ-marking and let (ϑ i ) i∈Z(δ) be the associated basis of global sections of L . Note that if ψ is a symplectic automorphism of K(δ) and if χ ψ is a symmetric semi-character then ψ = σ χ ψ (ψ) is symmetric. We suppose that this is the case in the following. Let ψ( Ẑ(δ))) = Z ψ × Ẑψ , where Z ψ ⊂ Z(δ) and Ẑψ ⊂ Ẑ(δ). Denote by ( θi ) i∈Z(δ) the basis of global sections of L associated to (A k , L , Θ δ .ψ). In the following, we give an explicit formula to obtain ( θi ) i∈Z(δ) from the knowledge of (ϑ i ) i∈Z(δ) .

Let

A 0 k A k /Θ δ (ψ( Ẑ(δ))
) and π : A k → A 0 k be the canonical map. The data of the maximal level subgroup Θ δ (ψ((1, 0, y) y∈ Ẑ(δ) )) is equivalent to the data of a line bundle L 0 on A 0 k and an isomorphism π * (L 0 ) → L . Let s0 be the unique global section of L 0 . Let Z ψ⊥ = {x ∈ Z(δ)|l(x) = 1, all l ∈ Ẑψ }. As ψ is symplectic, it is clear that Z ψ⊥ ⊃ Z ψ and in fact Z ψ⊥ = Z ψ since L 0 is a principal polarisation. We can then apply the isogeny theorem [Mum66, Sec. 1, Th. 4], with σ :

Z ψ⊥ /Z ψ → 0 to obtain θ0 = λπ * ( s0 ) = i∈Z ψ ϑ i , (19)
for λ ∈ k * . Now by definition we have

θi = ψ((1, i, 0)). θ0 . ( 20
)
where the dot product is the action (2). By evaluating at 0 the basis of global sections of L in (20), we get an explicit description of the action of Sp(K(δ)) on the geometric points of M δ . Actually the obtained formulas give a valid action of Sp(K(δ)) on the geometric points of M δ .

5.3

The stabiliser of V 0 J Now, let (a u ) u∈Z( n) be a geometric point of V 0 J . As Aut Gm,s H( n) acts on M n , we are interested in the subgroup H of the elements of Aut Gm,s H( n) that leave (a u ) u∈Z( n) in V 0 J .

Definition 16: Let ψ ∈ Aut Gm,s H( n) and denote by Θ A n the theta structure

Θ A n • ψ. Then we can define Z * ( n) , Ẑ * ( n) , K * 1 , K * 2 , p 1 , p 2 for Θ A n exactly as in the definition of Z * ( n), Ẑ * ( n), K * 1 , K * 2 , p1 , p2 for Θ A n is Section 3.1.
Then, we say that ψ is compatible with H(n) if the following diagrams commute:

(1, x, 0) x∈Z * ( n) p 1 ψ / / (1, x, 0) x∈Z * ( n) p1 (1, x, 0) x∈Z(n) (1, x, 0) x∈Z(n) , (21)
(1, 0, y) y∈ Ẑ * ( n)

p 2 ψ / / (1, 0, y) y∈ Ẑ * ( n) p2 (1, 0, y) y∈ Ẑ(n) (1, 0, y) y∈ Ẑ(n) . ( 22
)
Lemma 17: We have that H is the subgroup of compatible symmetric automorphisms of H( n). In particular it does not depend on (a u ) u∈Z( n) so it is also a subgroup of Aut Gm,s H( n) that leaves V 0 J invariant.

Proof: Let (A, L , Θ A n ) be a triple corresponding to the theta null point (a u ) u∈Z( n) . Let ψ ∈ Aut Gm,s H( n), and (a u ) u∈Z( n) = ψ.(a u ) u∈Z( n) . Proposition 11 shows that (a u ) u∈Z( n) is in V 0 J if and only if the associated theta structure Θ A n .ψ is compatible with the theta structure Θ B n of B. But this means exactly that ψ is compatible with H(n).

We can describe the action of H more precisely:

Proposition 18: The action of H on V 0 J is generated by the actions given by

(a u ) u∈Z( n) → (a ψ2(u) ) u∈Z( n) , (23)
for every automorphism ψ 2 of Z( n) fixing Z(n) and

(a u ) u∈Z( n) → e n (ψ 1 (u), u).a u u∈Z( n) , (24)
for every symmetric morphism

ψ 1 : Z( n) → Ẑ( ) ⊂ Ẑ( n)
and where e n is the commutator pairing on H( n).

Proof: Let ψ ∈ H and denote by ψ ∈ Sp(H(δ)) the associated symplectic automorphism. With respect to a basis (v κ , vκ ) κ∈{1,...,g} of Z( n

) × Ẑ( n), ψ is represented by a matrix M [A, B, C, D] = A B C D ∈ Sp 2g δ (Z). Since K = Θ n (ψ( Ẑ( ))) ⊂ Θ n ( Ẑ( n)),
we have B = 0. So D = t A -1 and we see that ψ is in the subgroup of Sp(K( n)) generated by the matrices:

1. M [A, B, C, D] such that C=0 and B = 0. Then A is an automorphism and the compatibility condition implies that it must fix Z(n). By Lemma 15, there exists an extension ψ of ψ defined by the semi-character χ ψ such that

χ ψ (v κ ) = 1, χ ψ (v κ ) = 1 for κ = 1, . . . , g.
It is easily seen that ψ ∈ H and using ( 19) and (20), we see that ψ yields the action (23). we can write ψ((x, 0)) = (x, ψ 1 (x)). By looking at the conditions (6) and (7) we see that

ψ((x, y)) -(x, y) ∈ ψ( Ẑ( )) ⊂ Ẑ( ), (25)
for all (x, y) ∈ Z * ( n) × Ẑ * ( n). Using (25), we deduce that ψ 1 (x) is in Ẑ( ). Again, by Lemma 15, there exists an extension ψ of ψ defined by the semi-character χ ψ such that χ ψ (v κ ) = t κ for t κ ∈ G m,k . In order to have that ψ ∈ H we must choose t κ such that (t κ , v κ , ψ 1 (v κ )) = (1, v κ , 0). For this we can take 1) . In this case, we obtain the action (24) following ( 19) and (20).

t κ = ψ 1 (v κ )(v κ ) 1/2.( -
Because of the exact sequence from equation (18), we see that by composing ψ with a ψ ∈ H coming from the two preceding cases, we only have to study the case where ψ comes from a change of maximal level structure. Let c ∈ K(δ) defining the symplectic base change by (17). Then c ∈ K(δ)[2] since ψ is symmetric and from the compatibility conditions c ∈ ψ( Ẑ( )). As is odd, we have c = 0.

Remark 19: The action (23) gives an automorphism of the (P i ) i∈Z( ) while the action (24) leaves the (P i ) i∈Z( ) invariant. In fact by taking a basis of Z( n), we see that if ζ is a ( n) th -root of unity, the actions (24) are generated by a (n1,n2,...,ng) → ζ i,j∈[1,g] ai,j ninj a (n1,...,ng)

where (a i,j ) i,j∈[1,g] is a symmetric matrix and a i,j ∈ Z/nZ ⊂ Z/ nZ (via x → x) for i, j ∈ [1, g]. So each coefficient of one P i is multiplied by the same th -root of unity.

Our study of valid theta null points allows us to better understand the geometry of V 0 J . We know from Proposition 11 that geometric points (a u ) u∈Z( n) ∈ V 0 J classifies the isogenies π : A k → B k between marked abelian varieties verifying the compatibility condition.

Taking the contragredient of π gives an isogeny from B k to A k with kernel K = G((a u )) u∈Z( n) ). Thus, the theta null points on V 0 J correspond to varieties -isogeneous to B k . But we have seen in Proposition 18 that it may happen that different points of V 0 J give the same kernel K and hence the same variety. We want to classify the points of V 0 J corresponding to isomorphic varieties -isogeneous to B k . In other words, we want to study the fiber of the map (a u ) u∈Z( n) → G((a u ) u∈Z( n) ) defined in Section 5.1 for (a u ) u∈Z( n) a valid theta null point.

Proposition 20: Let K be a subgroup of B k [ ] isomorphic to Z( ) that is isotropic for the pairing e W . Then G -1 ({K}) is a subset of the valid theta null points in V 0 J that forms a principal homogeneous space under the action of H. In particular, the geometric points of V 0 J /H are in bijection with the -isogenies from B k (with isotropic kernel).

Proof: Let K = {P i , i ∈ Z( )} be such a maximal subgroup. Theorem 12 gives a geometric point (a u ) u∈Z( n) of V 0 J corresponding to a marked abelian variety (A k , L A , Θ A ) (and an isogeny π :

A k → B k ) such that G((a u ) u∈Z( n) ) = K. Let (a u ) u∈Z( n) be another valid theta null point in V 0 J in G -1 (K)
, corresponding to a marked abelian variety (A k , L A , Θ A ), and an associated isogeny π :

A k → B k . Since A k ∼ → B k /K ∼ → A K ,
there exists an isomorphism ψ making the following diagram commutative:

A k ψ B k π = = π A k
Taking the contragredient, we then obtain that this diagram commutes:

A k π } } B k A k π `ψ O O
By definition of the associated isogenies π and π , we know that L A = π * (L B ) and L A = π * (L B ) = ψ * (L A ). So ψ induces a morphism of the theta groups G(L A ) and G(L A ), and pulling back by the theta structures we get a symmetric automorphism ψ of H( n). Since the theta structures Θ A and Θ A are compatible with Θ B , ψ is in H. This shows that (a u ) u∈Z( n) and (a u ) u∈Z( n) are in the same orbit under H.

Classification of the valid and degenerate theta null points

In this section, we extend the map G from the set V 0 J of valid theta null points so that the domain of the extended map is V J . We start by making the structure of the solutions of the algebraic system defined by J explicit. For this let ρ : Proposition 21: We suppose that 4 | n. Let (a v ) v∈Z( n) be a geometric point of V J . For any i ∈ Z( ) such that (a ρ(j,i) ) j∈Z(n) = (0, . . . , 0), let P i be the geometric point of P Z(n) k with homogeneous coordinates (a ρ(j,i) ) j∈Z(n) . We denote by S the set {i, i ∈ Z( ), P i is well defined}, and let G((

Z(n) × Z( ) → Z( n) be
a v ) v∈Z( n) ) = {P i , i ∈ S}. Then S is a subgroup of Z( ), G((a v ) v∈Z( n) ) is an isotropic subgroup of B k [ ] for e W ,
and the map S → G((a v ) v∈Z( n) ) is a morphism of group.

Proof: The fact that P i for i ∈ S is a point of -torsion comes from [CL09, Lem. 5.6] which can be easily adapted to the case n divisible by 4 and relatively prime to n.

The proof of the preceding proposition in [START_REF] Carls | A p-adic quasi-quadratic time point counting algorithm[END_REF] proves moreover that {P i , i ∈ S} is a subgroup of the group of -torsion points of V I Θ B n (that we identify with

B k via Θ B n
) and the map i ∈ S → P i ∈ B[ ] is a group morphism. The fact that this subgroup is isotropic comes easily from [LR10, Theorem 2].

If (a v ) v∈Z( n) is a general geometric point of V J , it can happen that certain P i are not well defined and as a consequence (a v ) v∈Z( n) is not a valid theta null point. But even if every P i is well defined, (a v ) v∈Z( n) need not be a valid theta null point, as we can see for instance in Example 25 of Section 5.5 below. We need a criterion to identify the solutions of J that correspond to valid theta null points. From the discussion of Section 5.1, we know that a necessary condition for a solution (a v ) v∈Z( n) of J to be a valid theta null point is that G((a u ) u∈Z( n) ) form a subgroup of rank g of B k [ ]. Theorem 23 below asserts that this necessary condition is indeed sufficient.

First we remark that there is an action of H on V J given by ( 23) and (24) which extends the previously defined action of H on V 0 J . By Remark 19 (which can easily be extended to the case of degenerate theta null points) we know that if (a u ) u∈Z( n) is a theta null point giving the associated group {P i , i ∈ Z( ), P i well defined projective point}, then the points ψ.(a u ) u∈Z( n) where ψ ∈ H give the same associated group. In fact the converse is true:

Lemma 22: We suppose that 4 | n. Let (c u ) u∈Z( n) and (d u ) u∈Z( n) be two geometric points of V J giving the same associated group {P i , i ∈ Z( ), P i well defined projective point}.

Then there exists ψ ∈ H such that

(d u ) u∈Z( n) = ψ.(c u ) u∈Z( n) .
Proof: To ease the notation, we suppose here that S = Z( ), because the lemma will only be applied for this case in Theorem 23. Let P i = (a ρ(j,i) ) j∈Z(n) for i ∈ Z( ). First, up to an action of type (23), we can suppose that for all i ∈ Z( ), we have P

(cu) u∈Z( n) i = P (du) u∈Z( n) i
. Thus there exists λ i ∈ k such that (c ρ(j,i) ) j∈Z(n) = λ i (d ρ(j,i) ) j∈Z(n) . Since (c u ) u∈Z( n) and (d u ) u∈Z( n) are projective, we can assume that λ 0 = 1. It suffices to show that up to an action of type (24), for every i ∈ Z( ) such that P i is well defined, λ i = 1. But first we show that for such points, we have λ i = 1.

Let i ∈ Z( ) be such that (c ρ(j,i) ) j∈Z(n) is a well defined projective point. Let x, y, u, v ∈ Z(2n) be congruent modulo Z(n). We remark that for µ ∈ {1, . . . , }, ρ (x, µ.i), ρ (y, i), ρ (u, 0), ρ (v, 0), where ρ : Z(2n) × Z( n) → Z(2 n) is the morphism defined in the same manner as ρ, are elements of Z(2 n) congruent modulo Z( n). Applying Theorem 4, we obtain that t∈Z(2)

χ(t)c ρ(x+y+t,(µ+1).i) c ρ(x-y+t,(µ-1).i) . t∈Z(2) χ(t)c ρ(u+v+t,0) c ρ(u-v+t,0) = = t∈Z(2) χ(t)c ρ(x+u+t,µ.i) c ρ(x-u+t,µ.i) . t∈Z(2) χ(t)c ρ(y+v+t,i) c ρ(y-v+t,i) , (26)
for any χ ∈ Ẑ(2). We have a similar formula involving (d u ) u∈Z( n) . Using [Mum66, eq. (*) p. 339], we obtain as 4 | n that for every x, y ∈ Z(2 n), we can choose u, u ∈ Z(2 n) such that t∈Z(2) χ(t)c ρ(u+v+t,0) c ρ(u-v+t,0) = 0 (and the same is true of course if we replace c by d in the preceding inequality).

Using equation (26) for both (c u ) u∈Z( n) and (d u ) u∈Z( n) , and an easy induction, we obtain that λ µ.i = λ uµ i where (u µ ) is a sequence such that u 0 = 0, u 1 = 1 and u µ+1 + u µ-1 = 2.u µ + 2. The general term of this sequence is u µ = µ 2 . For µ = , we have

λ 2 i = λ .i = λ 0 = 1 (27)
Now, by the symmetry relations, we have for j ∈ Z(n), c ρ(j,µ.i) = c ρ(-j,-µ.i) .

Applying this for µ = 1 and j = 0, we obtain that λ i = λ

( -1) 2 i
which together with (27) gives

λ i = 1 (28)
which concludes the claim.

Let (e 1 , . . . , e g ) be the canonical basis of Z( ). Up to an action of type (24) we may assume that λ ei = 1 and λ ei+ej = 1 for i, j ∈ {1, . . . , g}, j < i. Now let a, b ∈ Z( ) be such that λ a = 1, λ b = 1 and λ a-b = 1. Then by Theorem 4 we have the relations:

t∈Z(2) χ(t)c ρ(x+y+t,a+b) c ρ(x-y+t,a-b) . t∈Z(2) χ(t)c ρ(u+v+t,0) c ρ(u-v+t,0) = = t∈Z(2) χ(t)c ρ(x+u+t,-b) c ρ(x-u+t,b) . t∈Z(2) χ(t)c ρ(y+v+t,a) c ρ(y-v+t,a) . ( 29
)
Since by symmetry, λ -b = 1, the relations (29) give that λ a+b = 1. An easy induction shows that for any i ∈ Z( ) we have λ i = 1, which concludes the proof.

As an application of Lemma 22, we have:

Theorem 23: Let (B k , L 0 , Θ B
n ) be a marked abelian variety and let (b u ) u∈Z(n) be its associated theta null point. Let (a u ) u∈Z( n) be a geometric point of V J where V J is the algebraic variety defined in Section 4. For any i ∈ Z( ), let P i be the geometric point, if well defined, of P Z(n) k with homogeneous coordinates (a ρ(j,i) ) j∈Z(n) . Denote by S the subset of Z( ) of those elements i such that P i is a well defined projective point.Then G((a u ) u∈Z( n

) ) := {P i , i ∈ S} is an -torsion subgroup of B k = V I Θ B n isomorphic to Z( ) if and only if (a u ) u∈Z( n) is a valid theta null point. In other words, G((a u ) u∈Z( n) ) is isomorphic to Z( ) if and only if there exists (A k , L , Θ A n )
an abelian variety together with an ( n)-marking with associated theta null point (a u ) u∈Z( n) .

Proof: The if part of the statement follows from the discussion in Section 5.1.

For the only if part of the statement, by Proposition 21 the group G((a u ) u∈Z( n) ) is isotropic, so by Theorem 12 there exists a valid theta null point (a u ) u∈Z( n) such that G((a u ) u∈Z( n) ) = {P i , i ∈ Z( )}. Since (a u ) u∈Z( n) and (a u ) u∈Z( n) are geometric points of V J , we can apply Lemma 22 to obtain ψ ∈ H such that (a u ) u∈Z( n) = ψ.((a u ) u∈Z( n) ). This proves that (a u ) u∈Z( n) is a valid theta null point.

The next proposition is another application of the techniques used to prove Lemma 22. This proposition is important for the algorithmic applications presented in this paper since it allows to bound the degree of the 0-dimensional variety V J which is crucial in order to assess the running time of our algorithms.

Proposition 24: If is prime to the characteristic of k and 8 | n then V J is a geometrically reduced scheme.

Proof: We recall that V J is the affine variety defined by J where J is the image of the homogeneous ideal I defining M n , under the specialization map

k[x u |u ∈ Z( n)] → k[x u |u ∈ Z( n), nu = 0], x u → b u , if u ∈ Z(n) x u , else , with (b u ) u∈Z(n) the theta null point associated to (B k , L 0 , Θ B n ). By definition, V J is a closed subvariety of the affine space A Z( n) . For i ∈ Z( ), denote by π i : A Z( n) → A Z(n) the projection induced by the inclusion ϕ i : k[x u |u ∈ Z(n)] → k[x u |u ∈ Z( n)], x u → x ρ(u,i) .
In order to prove that V J is a reduced scheme, we can suppose by doing a base change if necessary that k = k and it is enough to prove that for any connected subvariety x of V J and all λ ∈ Z( ), π λ (x) is a reduced subvariety of A Z(n) . We consider two cases.

If π λ (x) is not the point at the origin of A Z(n) then it defines a projective point of P Z(n) which is an -torsion point of V I Θ B n by Proposition 21. We will show that π λ (x) is contained in the reduced line L λ between the origin point of A Z(n) and this point of -torsion. We identify L λ with Spec(k[z]) and we suppose that x = Spec(k[[t]]/(t m )) for m ∈ N * . Then the image of x in L λ is defined by an element α λ ∈ k[[t]]/(t m ). Now, we suppose that m = 2 so that we can write α λ = β λ (1 + tξ λ ), with β λ , ξ λ ∈ k. Using equation (26) of the preceding lemma, we obtain that for all µ 2 integer, we have ξ (µ+1).λ + ξ (µ-1).λ = 2ξ µ.λ + 2ξ λ . As ξ 0 = 0, since the theta null point (b u ) u∈Z(n) is reduced, we deduce immediately that for all µ 2, ξ µ.λ = ξ λ µ 2 . Applying this for µ = yields that ξ .λ = ξ λ 2 = 0 using again that (b u ) u∈Z(n) is reduced. As is prime to the characteristic of k, we get that for all λ ∈ Z( ), ξ λ = 0 and as a consequence, for m = 2 and all λ ∈ Z( ), the image of x in L λ is reduced. An easy induction on m based on the preceding reasoning then tells us that for all λ ∈ Z( ), the image of x in L λ is reduced.

We now treat the case when π λ (x) is the origin point of

A Z(n) . Let P = (x u |u ∈ Z(n)) be the ideal of k[x u |u ∈ Z(n)] defining the reduced point at the origin of A Z(n) . Let J λ = J ∩ ϕ λ (k[x u |u ∈ Z(n)]
) and denote by J λP the local ring of J λ in P. As J is a 0-dimensional ideal, we know that there exists m a positive integer such that J λP ⊃ P m in k[x u |u ∈ Z(n)] P . Let r λ be the smallest integer with this property. We want to show that r λ = 1. In order to do so, we are going to use another formulation of the Riemann relations given by Theorem 2.

For this, we let

H( n) = Z( n) × Ẑ(2) and H(n) = Z(n) × Ẑ(2). We denote by ρ : H(n) × Z( ) → H( n) the natural isomorphism deduced from ρ. For all v = (v , v ) ∈ H( n), we let y v = t∈Z(2) v (t)x v +t . Let a 1 , a 2 , a 3 , a 4 , τ ∈ H(n) such that 2τ = a 1 -a 2 -a 3 -a 4 . Set α 1 = ρ (a 1 , 2λ), α 2 = ρ (a 2 , 0), α 3 = ρ (a 3 , 0), α 4 = ρ (a 4 , 0) and τ 1 = ρ (τ, λ) so that we have 2τ 1 = α 1 -α 2 -α 3 -α 4 . We write τ = (τ , τ ) and let H(2) = {x ∈ H( n)|x is 2 -torsion modulo Z(2) × {0}}.
By applying [Mum67a, formula (C") p. 334], we have the following relation in J:

y α1 y α2 y α3 y α4 = = 1 2 g t∈H(2) (τ + t )(2t )y α1-τ1+t y α2+τ1+t y α3+τ1+t y α4+τ1+t , (30)
where t = (t , t ) ∈ H(2). By definition, for i = 2, 3, 4, if we write a i = (a i , a i ), we have

y αi = t∈Z(2) a i (t)b a i +t .
As by hypothesis (b u ) u∈Z(n) is valid theta null points, by applying [Mum67a, formulas (*) p. 339], we obtain that for any

a i = (a i , a i ) ∈ H(n) there exists β i ∈ 2Z(n) such that t∈Z(2) a i (t)b a i +β i +t = 0.
As a consequence, for any choice of a 1 , we can find a 2 , a 3 , a 4 , and τ ∈ H(n) such that 2τ = a 1 -a 2 -a 3 -a 4 and for i = 2, 3, 4, y αi = t∈Z(2) a i (t)b a i +t = 0. (We can take for instance a 1 = a 2 = a 3 = a 4 so that a 1 -a 2 -a 3 -a 4 ∈ 2H(n) and then if necessary add to a 2 , a 3 , a 4 elements of 2Z(n) in order to have y (ai,0) = 0.) As an immediate consequence, we obtain that π 2λ (x) is also the origin point of A Z(n) .

Let r λ be the smallest integer such that r λ r λ and 4|r λ . We remark that

ϕ 2λ (k[x u |u ∈ Z(n)]) = k[y ρ (v,2λ) |v ∈ H(n)].
Let M be a degree r λ /4 monomial in the variables y ρ (v,2λ) . If necessary, by multiplying M by a suitable non null constant, we see that M is equal to a product M of r λ /4 polynomials given by the right hand of (30). These polynomials have degree 4 and are sums of products of monomials of the form y ρ (v,λ) (using the symmetry relations). We deduce from this that M ∈ P r λ and as a consequence M ∈ J λ . But this means that M ∈ J 2λ and as M can be any degree r λ /4 monomial in the variables y ρ (v,2λ) , we have proved that J 2λP ⊃ P r λ /4 . Let m be an integer such that 2 m λ = λ in Z( ). Using the previous result and an easy induction, we see that if r λ > 1 then r λ = r 2 m λ < r λ which is a contradiction.

We conclude this section by a study of the degenerate theta null points. It is easy to see that H leaves V J invariant. Now, let ψ 2 be a endomorphism of Z( n) fixing Z(n). Here we do not require ψ 2 to be an automorphism. We let ψ 2 act on

V J by (a u ) u∈Z( n) → (a ψ2(u) ) u∈Z( n)
Since ψ 2 fixes Z(n) ⊂ Z( n), it fixes the 2-torsion points in Z( n), and it is easy to see that (a ψ2(u) ) u∈Z( n) satisfies the equations of Theorem 4 and the symmetry relations. As a consequence, the point (a ψ2(u) ) u∈Z( n) is in M n . Moreover, as ψ 2 fixes Z(n), (a ψ2(u) ) u∈Z( n) is a point in V J , so if we denote by H 1 the monoid of endomorphisms of Z( n) fixing Z(n), we have a well defined monoid action H 1 × V J → V J extending the group action given by ( 23) and (24). By acting on V J with an endomorphism of Z( n) fixing Z(n) which is not an automorphism, we obtain a point of V J which is degenerate: it is a theta null point such that the associated points P i from Proposition 21 are well defined but not distinct projective points (so they do not form a rank g -torsion subgroup of B k ).

There is another way to obtain degenerate theta null points in V J . Take any geometric point (a u ) u∈Z( n) ∈ V J , and a subgroup S of Z( ) (in particular S is not empty). We define a new point (a u ) u∈Z( n) where

a ρ(j,i) = a ρ(j,i) if i ∈ S, 0 otherwise,
and we recall that ρ has be defined at the begining of Section 5.1.

Since is odd, it is easily seen that (a u ) u∈Z( n) is in general a degenerate point in V J : the P i from Proposition 21 are not defined when i ∈ S. Now, we explain that combining the two methods described above, we obtain all the degenerate theta null points of V J . For this, let (a u ) u∈Z( n) be a degenerate point of V J . Let S ⊂ Z( ) be the subgroup where the points of -torsion P i , i ∈ S of Proposition 21 are well defined. The points P i form a subgroup S of the -torsion points of B k , and f : S → S , i → P i is a group morphism (which may not be an isomorphism, since as (a u ) u∈Z( n) is degenerate the P i are not necessarily distinct). Now, we extend S into a subgroup T of B k [ ] isomorphic to Z( ), isotropic for e W (this is possible by Proposition 21). We then extend f to a morphism f : Z( ) → T by sending an element in Z( )\S to 0 B . We take an isomorphism h between Z( ) and T . By Theorem 23 there exists a geometric point (a u ) u∈Z( n) ∈ V 0 J such that the corresponding group morphism i ∈ Z( ) → P i is h. Take ψ 2 to be the endomorphism of Z( n), that we identify to Z( ) × Z(n) via ρ, which is the identity on Z(n) and h -1 f on Z( ). Consider the point (a ψ2(u) ) u∈Z( n) with the coefficients ρ(j, i), i ∈ S taken to be 0. Then it has exactly the same defined points P i as (a u ) u∈Z( n) . Lemma 22 shows that it is the same point as (a u ) u∈Z( n) up to an action of the form given by Proposition (18).

We remark that the degenerate points in V J are exactly the points where the action of H is not free: if (a u ) u∈Z( n) is a degenerate point such that the corresponding P i are not all well defined, then there is an action of the form (24) giving the same point. If the P i are well defined but do not form a maximal subgroup, then this time there is an action of the form (23) giving the same point.

Applications and examples

Together with the study of degenerate theta null points, it is now possible to count the points in V J . In this section, we suppose that is prime. For instance, take g = 1, n = 4 and = 3. Let E be an elliptic curve, and (b u ) u∈(Z/nZ) be a level 4 theta null point on E. There are 4 = #P 1 (F 3 ) classes of 3-isogenies from E, and 6 = 3 × ϕ(3) solutions in V J for each class. The actions (23) are given by (a u ) u∈(Z/ nZ) → (a x.u ) u∈Z/ nZ where x ∈ Z/ nZ is invertible and congruent to 1 mod n. There are ϕ( ) such actions. The actions (24) are given by (a u ) u∈Z/ nZ → (ζ c.u 2 a u ) u∈Z/ nZ where ζ is a th -root of unity and c ∈ Z/ Z.

If g = 2 and n = 4, it is easy to compute the number of valid theta null points in V J . First, we remark that the number of isogeny classes of degree 2 of a given dimension 2 abelian variety B k is parametrised by the points of a Grassmanian Gr(2, 4)(F ) which are isotropic (see Theorem 12): there are ( 2 + 1)( + 1) such points.

Next, the number of actions of the form ( 23) is parametrised by the number of invertible matrices of dimension 2 with coefficients in F with is given by ( 2 -1).( 2 -). The number of actions of the form (24) is 3 (the number of symmetric matrices of dimension 2). As a consequence, the number of valid theta null points in V J is 10 -8 -6 + 4 .

We remark that this number is O( 10 ). For g = 2, = 3, we have 51840 valid theta null points in V J . For a general g and , we assess the order of the number of valid theta null point which are solution of V J . The number of isotropic points of a Grassmanian Gr(g, 2.g)(F ) is O( g(g+1)/2 ). The number of actions of the form (23) is O( g 2 ) and the number of actions of the form (24) is O( g(g+1)/2 ). We deduce that the number of valid theta null point in V J is bounded by O( 2.g 2 +g ).

(31)

Example 25: In the case of genus 1 and small it is possible to list all the geometric points of V J . We take = 3 and let E be the elliptic curve given by an affine equation y 2 = x 3 + 11.x + 47 over F 79 . A corresponding theta null point of level 4 for E is (1 : 1 : 12 : 1). The four subgroups of 3-torsion of E V I Θ 4 are K 1 = {(1 : 1 : 12 : 1), (37 : 54 : 46 : 1), (8 : 60 : 74 : 1)} K 2 = {(1 : 1 : 12 : 1), (67 : 10 : 68 : 1), (62 : 8 : 70 : 1)} K 3 = {(1 : 1 : 12 : 1), (42 : 5 : 15 : 1), (40 : 16 : 3 : 1)} K 4 = {(1 : 1 : 12 : 1), (72 : 56 : 31 : 1), (69 : 24 : 33 : 1)} All geometric points of V J are defined over F 79 (υ) where υ is a root of the irreducible polynomial X 3 + 9.X + 76. For each of the four subgroups K i , there are 6 geometric points of V J giving the curve E/K i . We give a point in each class (the other points can be obtained via the actions (23) and ( 24)):

Q 1 = (16υ 2 + 19υ + 17 : 1 : 46 : 16υ 2 + 19υ + 17 : 37 : 54 : 34υ 2 + 70υ + 46 : 54 : 37 : 16υ 2 + 19υ + 17 : 46 : 1) corresponds to K 1 .

Q 2 = (64υ 2 + 67υ + 68 : 1 : 68 : 64υ 2 + 67υ + 68 : 67 : 10 : 57υ 2 + 14υ + 26 : 10 : 67 : 64υ 2 + 67υ + 68 : 68 : 1) corresponds to K 2 . Q 3 = (8υ 2 + 49υ + 48 : 1 : 3 : 8υ 2 + 49υ + 48 : 40 : 16 : 17υ 2 + 35υ + 23 : 16 : 40 : 8υ 2 + 49υ + 48 : 3 : 1) corresponds to K 3 . Q 4 = (32υ 2 + 73υ + 34 : 1 : 33 : 32υ 2 + 73υ + 34 : 69 : 24 : 68υ 2 + 7υ + 13 : 24 : 69 : 32υ 2 + 73υ + 34 : 33 : 1) corresponds to K 4 .

We also have the following degenerate points in V J : if we take x = 9 in the action (23), the image of the class of any Q i is C = {(55 : 1 : 12 : 55 : 1 : 1 : 28 : 1 : 1 : 55 : 12 : 1), (1 : 1 : 12 : 1 : 1 : 1 : 12 : 1 : 1 : 1 : 12 : 1), (23 : 1 : 12 : 23 : 1 : 1 : 39 : 1 : : 23 : 12 : 1)}. For this class, the corresponding -torsion subgroup (the points P i of Proposition 21) is {(1 : 1 : 12 : 1), (1 : 1 : 12 : 1), (1 : 1 : 12 : 1)} which has rank 0. On C the action (23) is trivial, so there are only 3 points in this degenerate class, coming from the action (24). The last degenerate point is (1 : 0 : 0 : 1 : 0 : 0 : 12 : 0 : 0 : 1 : 0 : 0), alone in its class.

Let ν be the 2-adic valuation of n. We conclude this section with some remarks concerning the case ν = 1 and the case where the characteristic of k is equal to . First, for computational reasons, for instance in order to limit the number of variables when computing the points of V J , we would like to have ν as small as possible. All the results of Section 5 are valid under the hypothesis that ν 2 (except Proposition 24 which is only proved for ν 3)) and that the characteristic of k is different from . In the case ν = 1, we can not even prove that V J is a zero dimensional variety. Nonetheless we have made extensive computations which support the idea that even in the case ν = 1, in general, V J is a zero dimensional variety whose degree is the same O() with respect to the parameter as in the case ν = 2.

We remark that the definition of V J at the begining of Section 4 is valid even if we do not suppose that is prime to the characteristic of the base field k. Moreover, the proof that V J is a 0-dimensional scheme is still correct without the hypothesis that is prime to the characteristic of k. In this case V J is not anymore reduced and the computation of the number of solutions of V J are not valid. Nonetheless, from our computations, we see the degree of the variety V J is of the same order with respect to the parameter as in the case where the characteristic of k is different from .

In the following section, we give an algorithm to find the solutions of V J . We explain why this algorithm is efficient in the case ν 2 and when the characteristic of k is different from . If ν = 1 or if the characteristic of k is equalto , we will make the hypothesis that V J is a zero dimensional variety whose degree is given by formula (31). Under this hypothesis, we can also give heuristics explaining the efficiency our algorithm.

We would like to use the formulas of Section 4 to compute the image of the modular correspondence Φ as described in the introduction of this paper for some positive integer . As said before, the main algorithmic difficulty is to solve a polynomial system defined from the equations of Theorem 4. The aim of this section is to give an algorithm to solve efficiently this system. We have made an implementation of our algorithm and used it to test the hypothesis described at the end of Section 5.

Let n = 2 ν and we suppose in this section that is an odd prime. In this section, k is a finite field. We let (B k , L 0 , Θ B n ) be a dimension-g abelian variety together with an n-marking and we denote by (b u ) u∈Z(n) its associated theta null point. Let J be the image of the homogeneous ideal defining M n given by the equation of Theorem 2, under the specialization map

k[x u |u ∈ Z( n)] → k[x u |u ∈ Z( n), nu = 0], x u → b u , if u ∈ Z(n) x u , else .
We denote by V J the 0-dimensional affine variety (hypothetically 0-dimensional if ν = 1) defined by the ideal J. Let ρ : Z(n) × Z( ) → Z( n) be the group isomorphism given by (x, y) → x + ny

Motivation

In order to find the points of the variety V J a first idea is to use an efficient Gröbner basis computation algorithm [START_REF] Becker | Gröbner bases[END_REF] such as F 4 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF]. We have carried out computations in the case g = 2, ν = 1 and = 3 with respect to a total degree order (the DRL [AL94,CLO92] or grevlex order) using the computer algebra system Magma [BCP97] implementation of F 4 . From our computation, we conclude that even for a small coefficient field (k = F 3 10 ), it takes 20 hours of computations using Magma on a powerful computer with 16 GB of RAM to obtain a Gröbner basis of J. as expected from the computations of Section 5, the number of solutions in the algebraic closure k of k is big: 30853 solutions in characteristic 3 (we note that this is consistent with the number of solutions discussed after Proposition 20 when g = 2, ν = 2 and = 3 since it is smaller than 51840). to fully solve the system (that is to say, find explicitly all the solutions in k)

we need to compute a second Gröbner basis with respect to a lexicographical order.

This last operation can be done using the FGLM [START_REF] Faugère | Efficient computation of zero-dimensional Gröbner bases by change of ordering[END_REF] algorithm. In our case it is equivalent to computing the characteristic polynomial of a 30853 × 30853 matrix. This computation did not finish using Magma for the base field k = F 3 10 . So we see that even for g = 2, ν = 1 and = 3 the computation of the points of V J is painful using a generic algorithm. In this section, we give an algorithm to solve the algebraic system defined by J for small over a big coefficient field efficiently. As an application of our method, we can mention the initialisation phase of a point counting algorithm [START_REF] Carls | A p-adic quasi-quadratic time point counting algorithm[END_REF]. Because this last point counting algorithm is efficient for curves defined over a field of small characteristic p (equal to ), but has a bad behavior with respect to p, in this part, we are mainly interested by the complexity of the algorithms in the size of k.

The main idea of our algorithm is to use explicitly the symmetry inside the problem deduced from the action of the theta group: we compute a Gröbner basis not for the whole ideal J but rather a Gröbner basis of a well chosen projection J ∩ k[x ρ(v,λ) |v ∈ Z(n)] for λ ∈ Z( ). With our strategy, the same problem (k = F 3 10 ) can be solved in seconds and far bigger problems (k = F 3 1500 ) can be solved in less than 1 hour (see Section 6.6 for experimental results).

Intuitions behind the algorithm

Our method is a combination of existing algorithms and the results of Section 5. As explained before we need to take advantage of the structure of the polynomial system (symmetries) to speedup the computations. Solving efficiently polynomial systems with symmetries is a difficult open issue. In this paper, we propose an ad hoc algorithm which is somewhat similar to the algorithm given in [?] for bilinear systems. The two important parameters to estimate the complexity of computing Gröbner bases of 0-dimensional ideals are the total number of solutions and the maximal degree of the polynomials occurring in the computations (this is also known as the degree of regularity of the ideal). We first recall the bounds in the case of bilinear systems, then we go back to the equations of Theorem 4. We first give an example to motivate our strategy. In the following we denote by T the set [x 1 , . . . , x s ] of variables and we make the hypothesis that we can split the set of variables into two non-empty subsets T = X ∪ Y . Suppose that we are given an ideal J ⊂ k[T ] generated by quadratic polynomials [f 1 , . . . , f m ] such that for i = 1, . . . , m, f i is a polynomial in k[T ] which is also bilinear; that is to say f i is linear with respect to each set of variables X and Y . When m = s and under some regularity assumption (see theorem 6 in [?]) it can be proved that a Gröbner basis with respect to a total degree ordering of the ideal K = J ∩ k[Y ] is composed of polynomials of degree less than 1 + min(#X, #Y ). In other words the ideal K can be generated by polynomials of degree as low as 1 + min(#X, #Y ). On the other hand, if we consider an ideal I ⊂ k[T ] generated by quadratic polynomials [h 1 , . . . , h s ], it is well known that a Gröbner basis of I contains polynomials of degree 1 + s = 1 + #X + #Y (Macaulay bound) when the sequence h 1 , . . . , h s is regular. In summary, for an ideal J generated by bilinear systems and a well chosen set of variables X and Y the ideal J ∩ k[Y ] can be generated by polynomials of degree less than expected (more precisely of degree less than the maximal degree of the polynomials of a Gröbner basis of an ideal generated by generic polynomials of the same degree). Moreover, the total number of solutions counted with multiplicities of I is 2 s as given by the Bézout bound whereas in the case of the ideal J generated by bilinear polynomials this number drops to s #Y 2 s when s → ∞. Thus, we observe that when #Y is constant then the number of solutions is polynomial in s and a Gröbner basis for any monomial ordering can be computed in polynomial time. Now we go back to the equation of Theorem 4: even if the equations are not bilinear we will apply a similar strategy. We chose j ∈ Z( ) and we split the set variables into two sets: Y = [x ρ(u,j) |u ∈ Z(n)] and X = T \Y . For fixed g and ν the cardinality of Y is also fixed. Moreover, we know by Proposition 21 that the solutions of the system J ∩ k[Y ] can be either the origin point of A Z(n)

= J ∩ k[Y ].
Contrarily to the case of bilinear systems we cannot prove any bound on the degree of regularity of the ideal J but we have made extensive computations which show that in general our algorithm is much more efficient than a general purpose Gröbner basis algorithm.

It is easy to detect if the system has no solution since in that case any Gröbner basis of K contains the constant polynomial 1. Now, if we assume that a solution exists, then by Proposition 21 there exists a subgroup G of rank at least 1 of the -torsion group of V I Θ B n such that all the points of G are defined over k. As the

solutions of J ∩ k[Y ] are points of V I Θ B n [ ],
we conclude that for some r we have:

√ J = P 1 ∩ • • • ∩ P r where P i is a prime ideal and deg(P i ) = 1.

Hence as soon as we obtain a Gröbner basis of K, we compute a prime decomposition of the ideal K (so that we need to factorize univariate polynomials). When the characteristic of k is precisely equal to , the ideals J and K are not reduced; in that case we can take advantage of this fact to obtain a faster algorithm: as soon as we obtain a Gröbner basis of K we compute a Gröbner basis of √ K (this can be done efficiently using gcd operations) before computing a decomposition into primes.

General strategy

In the following, J is the ideal generated by polynomials given in Theorem 4; we give a general strategy for computing at least one solution of the corresponding system (that is to say one point in V J ). All the steps of our algorithm are standard with the exception of step 1 and step 4.

Step 1 For any non-zero j ∈ Z( ), let Y = [x ρ(u,j) |u ∈ Z(n)]. Using a dedicated algorithm given in Section 6.4, we compute a truncated Gröbner basis for an elimination order and a modified graduation. This allows us to obtain an ideal K 1 ( which is zero-dimensional as a k[Y ]-ideal ). In general K 1 is not equal to K. The output of the algorithm is a sequence of polynomials [p 1 , . . . , p κ ] in k [Y ] such that K 1 is generated by (p 1 , . . . , p κ ).

Step 2 Compute a Gröbner basis G DRL of K 1 for a total degree order (DRL or grevlex). This can be done with any efficient algorithm for computing Gröbner basis, for instance F 4 .

Step 3 Compute a Gröbner basis G Lex of K 1 for a lexicographical order. This can be done by using the FGLM algorithm [?] to change the monomial order of G DRL .

Step 4 Using the method of Section 6.4, compute a decomposition into primes of the following ideal:

K 1 = P 1 ∩ • • • ∩ P r
We assume that deg(P i ) = 1 (if it is not the case we replace k by some finite extension of k a minimal polynomial of which is easy to obtain since each P i is described by a lexicographical Gröbner basis, so we can compute explicitly the splitting field of each univariate polynomials occurring in each Gröbner bases).

Step 5 For i from 1 to r, we repeat the following Steps a,b,c for the ideal (P i ) + J:

(a) Compute a Gröbner basis G i of (P i ) + J for a total degree order (DRL). (b) Change the monomial order to obtain G i a lexicographical Gröbner basis of (P i ) + J. (c) Compute a decomposition into primes: √ P i + J = P ji-1+1 ∩ • • • P ji (by convention j 0 = r). Remark 26: We can use Theorem 23 in order to recognize a valid theta null point given a geometric point P of V J . Once we have obtained a point P of V J corresponding to a valid theta null point, by Proposition 20 we can easily recover all the solutions of V J corresponding to the same isotropic subgroup K of B k using the action given by Proposition 18.

Since we have

√ J = √ K 1 ∩ J = √ P 1 ∩ J ∩ • • • ∩ √ P r ∩ J

Description of the algorithm

In this section, we give a detailed explanation of the Step 1 and Step 4 of the algorithm described in Section 6.3.

Step 1: elimination algorithm

The normal strategy for computing Gröbner bases (Buchberger, F 4 , F 5 ) consists in considering first the pairs with the minimal total degree among the list of critical pairs (see [START_REF] Cox | Ideals, Varieties and Algorithms[END_REF][START_REF] Becker | Groebner Bases, a Computationnal Approach to Commutative Algebra[END_REF], for instance).

In the following, to select critical pairs, we consider only the total degree with respect to the first set of variables X. More precisely: Moreover, we stop the computation of the Gröbner basis as soon as we find a zero dimensional system in k [Y ].

To this end, we will use the following well known algorithmic criterion to determine when a variety in k n contains only a finite number of points: Step 4: decomposition into primes The known general purpose algorithms to compute a primary decomposition of an ideal are inefficient in our case. To speed up the computation, we proceed as follow:

Step 1 The basis G Lex always contains a univariate polynomial g(x s ). We can factorize this polynomial. As we will see in the experimental section this is the most consuming part of the whole algorithm. We obtain

g(x s ) = f 1 (x s ) α1 • • • f l (x s ) α l .
Step 2 For all factors i from 1 to l we apply the lextriangular algorithm [START_REF] Lazard | Solving zero-dimensional algebraic systems[END_REF] to obtain efficiently a decomposition into triangular sets of J 1 + f i (x s ) . We can describe the algorithm beginning by the special case of two variables [x s-1 , x s ] (this enough in our case since we assume that k = k as we will see later). The general shape of a Gröbner basis with respect to a lexicographical ordering is as follows [Laz85, Theorem 1]:

G Lex =                    g (x s ) h 1 (x s-1 , x s ) = g 1 (x s ) x k1 s-1 + • • • h 2 (x s-1 , x s ) = g 2 (x s ) x k2 s-1 + • • • • • • h s (x s-1 , x s ) = x ks s-1 + • • • polynomials in variables x 1 , . . . , x s (32) with k 1 < k 2 < • • • < k s and g s-1 (x s ) | • • • | g 2 (x s ) | g 1 (x s ).
Hence we can obtain easily some factors of g(x s ): g(x s ) = g(x s ) g 1 (x s ) g 1 (x s ) = g(x s ) g 1 (x s )

g 1 (x s ) g 2 (x s ) g 2 (x s ) = • • •
Step 3 For any factor f i (x s ) of g(x s ) = f 1 (x s ) α1 • • • f l (x s ) α l , it is enough to find the first element h j (x s-1 , x s ) of the Gröbner basis such that gcd (f i (x s ) , g j (x s )) = 0.

By doing a finite extension of k ⊂ k if necessary, we can suppose that each factor is linear f i (x s ) = x s -β i so that we search for the first j such that g j (β i ) = 0: then we obtain a new polynomial in one variable h j (x s-1 , β i ) that can be factorized. Hence we can iterate the algorithm for all the other variables x s-2 , . . . , x 1 .

First experiments and optimizations

In this section, we give running times for an implementation of the strategy that we have presented in Section 6.2. We also explain some important optimizations.

The main motivation of the examples presented is this section, is to illustrate that the initialisation phase of the point counting algorithm described in [START_REF] Carls | A p-adic quasi-quadratic time point counting algorithm[END_REF] can be made efficient enough to be negligible in the overall running time of the algorithm. For this, we take g = 2 and n = 2 and we work over a field k of characteristic 3 or 5. We construct a theta null point of level 2 corresponding to an abelian variety B k of dimension 2. In order to obtain a theta null point of level 2, we can proceed in the following way:

first compute a theta null point (b u ) u∈Z(4) of level 4 by picking up at random a geometric point of the affine variety defined by the equations of Theorem 4 ; then obtain the level 2 theta null point (b u ) u∈Z(2) by letting b u = b 2u for all u ∈ Z(2).

Remark 3 :

 3 It is moreover proved in [Mum66, Cor. p. 349] that if 4|δ the image of A k by the projective morphism defined by Θ δ is the closed subvariety of P d-1 k defined by the homogeneous ideal generated by the relations of Theorem 2. (This result can be sharpened, see [Kem89, Section 8]).

  2. M [A, B, C, D] such that A = Id and B = 0. Then t C = C. For x ∈ Z( n),

  the group isomorphism given by (x, y) → x + ny. Denote by I Θ B n the ideal of k[y u |u ∈ Z(n)] for the theta structure Θ B n generated by the equations of Theorem 2 where we have substituted ϑ u by y u and a u by b u for u ∈ Z(n). The homogeneous ideal I Θ B n defines a projective variety V I Θ B n , isomorphic to B k .

  and since the decomposition of each component √ P i ∩ J is done by step 5 of the previous algorithm, we obtain a decomposition of the ideal I:√ J = P r+1 ∩ • • • ∩ P jr .

Definition 27 :

 27 Partial degree of critical pair p = (f, g):deg X (p) = total degree of lcm LT < (f ), LT < (g) in the polynomial ring R [X] where R = k [Y ] .

Proposition 28 :F

 28 Let K be an ideal in k[x κ+1 , . . . , x s ]. Let V = V K be an affine variety in k s-κ and fix a monomial ordering in k[x κ+1 , . . . , x s ]. Then the following statements are equivalent:1. V is a finite set. 2. Let G be a Gröbner basis for K. Then LT < (g) | g ∈ G = x κ+1 , . . . , x s where x ακ+1 κ+1 • • • x αs s = x min(1,ακ+1) κ+1 • • • x min(1,αs) s Algorithm 29: Algorithm F 4 (main loop -modified version) a finite subset of k[x 1 , . . . , x s ] < a monomial admissible order X = [x 1 , . . . , x κ ] and Y = [x κ+1 , . . . , x s ] Output: a finite subset of k[x 1 , . . . , x s ]. G := F and P := CritPair(f, g) | (f, g) ∈ G 2 with f = g while P = ∅ and dim(G ∩ k [Y ]) = 0 do d := min {deg X (p) | p ∈ P } minimal partial degree of critical pairs extract from P, P d the list of critical pairs of degree d R :=Matrix Reduction(Left(P d ) ∪ Right(P d ), G) for h ∈ R do P := P ∪ {CritPair(h, g) | g ∈ G} G := G ∪ {h} return G

  or represent a -torsion point of V I Θ B n . In this last case, by Lemma 22 we know that there are solutions of J corresponding to the same projective point. Denote by D the number of solutions of J ∩ k[Y ] counted with multiplicities. As there are 2g -torsion points in V I Θ B Gröbner basis of the ideal J generated by polynomials of Theorem 4 for a special elimination ordering with respect to the two blocks of variables X and Y : when comparing two monomials m and m we first try to establish if degX (m) < deg X (m ) or deg X (m) > deg X (m )where deg X designates the total degree with respect to the first block of variables X. The intuition is that we hope to eliminate more quickly the variables from the first block X and so to compute a Gröbner basis of K

	, we have D	2g+1 + 1. Hence, following [?], we
	n
	compute a

We explain how to pick up at random an element of M n . Start with a generic point (x u ) u∈Z(n) , we chose randomly dim M n elements of k that we use in order to specialise dim M n coordinates of (x u ) u∈Z(n) . Then we recover the other coordinates of (x u ) u∈Z(n) using the zero dimensional algebraic system provided by the equations of Theorem 4 where we have substituted a u by x u for all u ∈ Z(n) (if we have to chose between different roots we pick up one at random). We repeat this process until we find a point defined over k.

We construct the modular correspondence of level where is the characteristic of k. Any valid solution of the modular correspondence will corresponds to the theta null point of level 2 of an abelian variety isogeneous to B k . We can then use the algorithm of [CL09] to count the number of points of B k .

First experiments As explained in 6.1 if we try to compute directly a Gröbner basis of the ideal generated by the equations, even when k is very small (k = F 3 10 for instance), it takes 20 hours of computations on a computer with 16 GB of RAM just to compute a DRL Gröbner basis. Moreover, in characteristic 3, there is a huge number of solutions: 30853. This implies that there is no hope to solve efficiently the corresponding problem directly.

Keeping the notations of the beginning of Section 6, we apply the method described in 6.3 to find the solutions of J. We let ν = 1, = 3 and g = 2 so that Z

Taking j = ρ(0, 1) and in the following, for u = (i, j) ∈ Z( n), we let x u = x ij . With these notations, we take Y = [x 31 , x 32 , x 02 , x 01 ] and X = T \Y the set of all other variables. Then we consider J embedded in the polynomial ring k[T ] where k is F 3 k or F 5 k . In that case J ∩k [x 31 , x 32 , x 02 , x 01 ] = J ∩ k [Y ] is an ideal of degree 160 (to be compared with 30853 the degree of the whole ideal J). When k = F 5 k (resp. k = F 3 k ) the polynomial g(x s ) obtained in section 6.4 is a square-free polynomial of degree 124 (resp. a non square-free polynomial of degree 70). We report in the following table some experiments using the algorithm of section 6.3 implemented in Magma and in C (see section 6.6 for a full description of the experimental framework). First we consider only very small example:

While the theoretical complexity is linear in the size of k it is clear from the example that, in practice, the behavior of the magma implementation is not linear in log(k) as one might expect from an optimal implementation. Moreover, when we increase the size of k, step 5 becomes the most consuming part of our algorithm. Hence, even if the new algorithm is efficient enough to solve the problem for a small base field k, the problems become intractable when #k > 5 100 . In the next paragraph we propose several optimizations to overcome this limitation.

Optimizations

The idea is to apply the algorithm of section 6.3 recursively to perform Step 5: we split again the remaining variables into two parts:

and thus we can split g (x 01 ) into two factors:

Hence the polynomial g 1 (x 01 ) can be efficiently factorized when k is big.

Experimental results

Programming language and workstation

The experimental results have been obtained with several Xeon bi-processor 3.2 GHz, with 16 GB of RAM. The instances of our problem have been generated using the Magma software. We used the Magma version 2.14 for our computations. The F 5 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF] algorithm has been implemented in language C in the FGb software [?] and we used this implementation for computing the first Gröbner basis. All the other computations are performed under Magma including factorizing some univariate polynomials and computing Gröbner basis using the F 4 algorithm.

Table Notation

The following notations are used in the tables of Fig. 1 and Fig. 2 below: k is the ground field, k ⊃ k is the field extension (as explained in step 4 on page 30, we sometimes have to consider an extension k of k). The practical behavior of our algorithm is strongly depending on the size of k ; hence, since k is fixed, the practical depends strongly on the degree of the field extension [k : k]. In order to obtain consistent data in the following tables we keep only the case [k : k] = 2. -T is the total CPU time (in seconds) for the whole algorithm. -T Gen is the time for generating the Riemann equations and computing a valid level 2 theta null point (Magma). -T Grob is the sum of the Gröbner bases computations (FGb and Magma).

-T Fact is the sum of the Factorization steps (Magma).

-T 1 is the total time of the algorithm excluding generating the equations:

Interpretation of the results

-In characteristic 3, the hardest part is the generation of the equations and the computation of a valid level 2 theta null point: T Gen ≈ T . In characteristic, 5 we have T ≈ 3 T Gen . -The most consuming part in the algorithm described in 6.3 is the univariate factorization. Moreover due to the implementation in Magma T Fact is not really linear in the size of k. -The algorithm is much more efficient in characteristic 3 since:

• All the solutions occur with some multiplicity, hence we have to deal with not square-free polynomials. As a consequence, the degree of the univariate polynomials can be decreased by taking the square-free part of the polynomials. • The corresponding Gröbner bases are in not in shape-position: as explain in section 6.4 we can split the univariate polynomial by taking a gcd. -The algorithm is very efficient since we can completely find the solutions of the ideal J for sizes of the base field k = 3 1500 or k = 5 700 which are interesting for point counting application.