# Fast change of level and applications to isogenies

David Lubicz, Damien Robert

► To cite this version:

David Lubicz, Damien Robert. Fast change of level and applications to isogenies. ANTS 2022 - Fifteenth Algorithmic Number Theory Symposium, Aug 2022, Bristol, United Kingdom. pp.article n°7, 10.1007/s40993-022-00407-9. hal-03738315

HAL Id: hal-03738315

https://inria.hal.science/hal-03738315v1

Submitted on 26 Jul 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Fast change of level and applications to isogenies

DAVID LUBICZ AND DAMIEN ROBERT

ABSTRACT. Let (A, L, Θ_n) be a dimension g abelian variety together with a level n theta structure over a field k of odd characteristic, we denote by (θ_i^{Θ_L})_{(Z/nZ)^g} ∈ Γ(A, L) the associated standard basis. For ℓ a positive integer relatively prime to n and the characteristic of k, we study change of level algorithms which allow to compute level ℓn theta functions (θ_i^{Θ_L}(x))_{i∈(Z/ℓnZ)^g} from the knowledge of level n theta functions (θ_i^{Θ_L}(x))_{(Z/nZ)^g} or conversely. The classical duplication formulas is an example of change of level algorithm to go from level n to level 2n. The main result of this paper states that there exists an algorithm to go from level n to level ℓn in O(n^gℓ^2g log(ℓ)) operations in k. We deduce an algorithm to compute an isogeny f : A → B from the knowledge of (A, L, Θ_n) and K ⊂ A[ℓ] isotropic for the Weil pairing which computes f(x) for x ∈ A(k) in O((nℓ)^g log(ℓ)) operations in k. We remark that this isogeny computation algorithm is of quasi-linear complexity in the size of K.

# 1. INTRODUCTION

1.1. Fast change of level. Let $A = \mathbb{C}^g/\Lambda$ be a dimension $g$ complex abelian variety. An analytic projective embedding of $A$ can be defined provided that we have enough analytic functions on $\mathbb{C}^g$ quasi-periodic with respect to $\Lambda$. Let $n \in \mathbb{N}$, if $\Lambda = \mathbb{Z}^g + \Omega\mathbb{Z}^g$ where $\Omega \in \mathfrak{H}_g(\mathbb{C})$ is a Siegel period matrix, we define following [Mum83, Ch. II, §1, Def. 1.2] the $\Lambda$-quasi-periodic functions of level $n$ as the vector space $R_{\Omega}^n$ over $\mathbb{C}$ of analytic functions $f$ on $\mathbb{C}^g$ such that:

$$ (1) \qquad f(z + \lambda) = f(z), \quad f(z + \Omega\lambda) = \exp(-\pi i n^t \lambda \Omega \lambda - 2\pi i n^t z \lambda) f(z), $$

for all $z \in \mathbb{C}^g$, $\lambda \in \mathbb{Z}^g$. Let $Z(\bar{n}) = (\mathbb{Z}/n\mathbb{Z})^g$. It can be shown that the dimension of $R_{\Omega}^n$ is $n^g$ and a standard basis of it is provided by the classical theta functions with characteristics $\theta[\begin{smallmatrix} 0 \\ b/n \end{smallmatrix}]$ $(z, \Omega/n)$ for $b \in Z(\bar{n})$.

Now if $\ell$ and $n$ are two positive integers, by a change of level algorithm, we mean an algorithm to compute the elements of the standard basis of $R_{\Omega}^n$ from the knowledge of the standard basis of $R_{\Omega}^{\ell n}$ (going down in level) and the other way around (going up in level).

The vector spaces $R_{\Omega}^n$ can be interpreted as the space of sections $\Gamma(A, \mathcal{L}_0^n)$ where $\mathcal{L}_0$ is a principal line bundle on $A$. The standard basis of $\Gamma(A, \mathcal{L}_0^n)$ given by the theta functions is determined by the canonical (symmetric) theta structure (see Definition 2.6) associated to $\Omega$. This point of view generalizes for an abelian variety over any field $k$. Let $(A, \mathcal{L})$ be a dimension $g$ abelian variety over a field $k$ together with an ample line bundle $\mathcal{L}$ such that $\mathcal{L} = \mathcal{L}_0^n$ with $\mathcal{L}_0$ a principal line bundle. Then a theta structure $\Theta_{\mathcal{L}}$, determines a standard basis which we denote by $(\theta_i^{\Theta_{\mathcal{L}}})_{i \in Z(\bar{n})} \in \Gamma(A, \mathcal{L})$. If $\mathcal{L}$ is very ample (e.g. $n \ge 3$ by a theorem of Lefschetz), $\Theta_{\mathcal{L}}$ defines a unique projective embedding $A \to \mathbb{P}^{2Z(\bar{n})}$ given on points by $x \mapsto (\theta_i^{\Theta_{\mathcal{L}}}(x))$. The projective point $(\theta_i^{\Theta_{\mathcal{L}}}(0_A))_{i \in Z(\bar{n})}$ is called the theta null point of $(A, \mathcal{L}, \Theta_n)$.

In the literature, change of level algorithms often take the form of a formula giving an expression of $(\theta_i^{\Theta_{\mathcal{L}}}(x))_{i \in Z(\bar{n})}$ in function of $(\theta_i^{\Theta_{\mathcal{L}}}(x))_{i \in Z(\bar{n})}$ or conversely. Change of level formulas are central in the theory of theta functions. In fact, the multiplication formulas [Mum66, p. 330] from which one can immediately deduce Riemann formulas, can be seen as a formula to go from level $n$ to level $2n$. Using Koizumi formulas [Koi76], the authors of [CR15] deduce a formula to go down from level $\ell n$ to level $n$.

<footnote>Date: July 11, 2022.</footnote>

<footnote n="2010">2010 Mathematics Subject Classification. 14K02,14Q15.</footnote>

<footnote>Key words and phrases. Isogenies, abelian varieties, computational algebraic geometry.
This work was supported by the ANR project CIAO.</footnote>
In this paper, we are interested in the computational efficiency of change of level algorithms measured as the number of field operations required to obtain the result. In this regard, we prove the following two theorems. The first theorem, proved in Theorem 4.3, is for going from level $n$ up to level $\ell n$:

**Theorem 1.1.** Let $n, \ell$ be relatively prime integers with $n$ even. Let $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ be a dimension $g$ abelian variety together with a level $n$ symmetric theta structure defined over $k$. Assume that $k$ is of characteristic zero or prime to $\ell n$.

We have that:

* Given a basis of $A[\ell]$ and the corresponding symplectic decomposition for the Weil pairing $A[\ell] = A_1[\ell] \oplus A_2[\ell]$, there is a canonical symmetric theta structure $\Theta_{\mathcal{L}\ell}$ of level $\ell n$ on $(A, \mathcal{L}^\ell)$.

* Let $x$ be a point of $A$, from the knowledge of $(\theta_i^{\Theta_{\mathcal{L}}}(x))_{i \in Z(\bar{n})}$ defined over $k(x)$, one can compute $(\theta_i^{\Theta_{\mathcal{L}}}(x))_{i \in Z(\bar{n})}$ with $O(n^g \ell^{2g} \log \ell)$ operations in $k(x)$.

In particular, we can compute the theta null point of level $\ell n$ in $O(n^g \ell^{2g} \log \ell)$ operations in $k$.

We also have a change of level algorithm to go from level $\ell n$ down to level $n$.

**Corollary 1.2.** Let $n$ be an even integer and $\ell$ an integer relatively prime to $n$. Let $(A, \mathcal{L}^\ell, \Theta_{\mathcal{L}^\ell})$ be a dimension $g$ abelian variety together with a level $\ell n$ symmetric theta structure. We suppose that $k$, the field of definition of $(A, \mathcal{L}, \Theta_{\mathcal{L}})$, is of characteristic zero or prime to $\ell n$.

We have that:

* $\Theta_{\mathcal{L}^\ell}$ induces a unique symmetric theta structure of level $n$ for $(A, \mathcal{L})$;

* Let $x$ be a point of $A$ defined over $k(x)$ given by $(\theta_i^{\Theta_{\mathcal{L}^\ell}}(x))_{i \in Z(\bar{n})}$. One can compute $(\theta_i^{\Theta_{\mathcal{L}}}(\ell x))_{i \in Z(\bar{n})}$ in $O(n^g \ell^g \log \ell)$ operations in $k(x)$.

In particular, one can compute the theta null point of level $n$ from the knowledge of the theta null point of level $\ell n$ in $O(n^g \ell^g \log \ell)$ operations in $k$.

To obtain this result, proved in Theorem 5.1, the idea is to first use Theorem 1.1 to go from level $n\ell$ to level $n\ell^2$, then descend along the isogeny $[\ell]$ using Mumford's isogeny theorem [Mum66, §1 Th. 4] to land in level $n$ (see also Example 2.17). Note that if $\ell = m^2$, we can descend along $[m]$ directly, this only costs $O((nm)^g)$ fields operations to compute $(\theta_i^{\Theta_{\mathcal{L}}}(mx))_{i \in Z(\bar{n})}$, hence $O((nm)^g \log \ell)$ fields operations to compute $(\theta_i^{\Theta_{\mathcal{L}}}(\ell x))_{i \in Z(\bar{n})}$.

In [CR15], the authors used Koizumi's formulas, given by an integral matrix $F$ such that $^tFF = \ell \mathrm{Id}_r$, to descend levels. These take $O(\ell^{gr/2} \log \ell)$ field operations, where $r=1$ if $\ell$ is a square, $r=2$ if $\ell$ is a sum of two squares, and $r=4$ otherwise. This dependence on $r$ of the complexity of Koizumi's formulas comes from the size of the kernel of $F: A^r \to A^r$ which is $\ell^{gr}$. As a consequence, Corollary 1.2 achieves a better complexity than Koizumi's formulas in the case that $\ell$ is not a sum of two squares.

As an application, we can improve the complexity of the isogeny computations algorithms [CR15; LR15]. Let $f: A \to B$ be an isogeny with kernel $K \subset A[\ell]$ isotropic for the Weil pairing. In order to compute $f$, starting from $(A, \mathcal{L}, \Theta_{\mathcal{L}})$, an abelian variety together with a level $n$ symmetric theta structure, we have to equip $B$ with a level $n$ symmetric theta structure and compute the isogeny in the coordinates provides by these theta structures. There are two strategies:

* ascend to level $\ell n$ on $A$ using Theorem 1.1 and then use Mumford's theorem to compute the isogeny from $A$ with a theta structure of level $\ell n$ to $B$ with a theta structure of level $n$;

* use the contragradiant isogeny $\tilde{f}: B \to A$ to endow $B$ with a level $\ell n$ theta structure by inverting Mumford's isogeny theorem using [LR12] (see also Section 4.1) and use Corollary 1.2 to descend from level $\ell n$ on $B$ to level $n$.

Both strategies give a quasi-linear isogeny algorithm:

**Theorem 1.3.** Let $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ be an abelian variety together with a level $n$ symmetric theta structure over $k$, $n$ even. Let $\ell$ be an odd integer prime to $n$, and we suppose that $\ell n$ is prime to the characteristic of $k$, or that $k$ is of characteristic zero. Let $K \subset A[\ell]$ be a totally isotropic subgroup for the Weil pairing defined over $k$, and let $f: A \to B = A/K$ be an isogeny.
Then $f$ induces a line bundle $\mathcal{M}$ together with $\Theta_{\mathcal{M}}$ a level $n$ symmetric theta structure for $(B, \mathcal{M})$.
Moreover, for $x$ a point of $A$ with field of definition $k(x)$ and given by $(\theta_i^{\Theta_{\mathcal{M}}}(x))_{i \in Z(\bar{n})}$ and suitable
equations for $K$, we can compute $(\theta_i^{\Theta_{\mathcal{M}}}(f(x)))_{i \in Z(\bar{n})}$ in time $O((n\ell)^g \log \ell)$ operations in $k(x)$.

Here we say that $K$ is totally isotropic whenever there exists a symplectic decomposition $A[\ell] = K \oplus K'$,
in particular $K$ is then maximal isotropic. (The converse is not true, for instance $A[\ell]$ is maximal
isotropic in $A[\ell^2]$ for the Weil pairing $e_{\ell^2}$, but is not totally isotropic.) In Remark 4.7, we explains the
tweaks to make for the algorithms above when $\ell$ is no longer prime to $n$. This algorithm improves the
isogeny algorithms of [LR12; CR15]: these followed the second approach with the slower descent of
level algorithm from Koizumi's formula. Compared to Theorem 1.1, in Theorem 1.3 we only have to
compute the action of the level subgroup $\tilde{K}$ above $K$ rather than the full $\ell n$-theta structure, which
explain the resulting complexity. We refer to Corollary 4.5 for the proof and we give examples of isogeny
computations in genus 1 and 2 in Examples 4.8 and 4.9. A similar approach is used in [CE14] but is
limited to isogenies between Jacobians.

In Section 6, we outline how to extend these algorithms when the abelian variety $A$ has real
multiplication. For descending levels and computing cyclic isogenies, Koizumi's formula was extended
to this case in [DJR+17]. But a drawback of this approach is that the isogeny $F$ given by Koizumi's
formula does not preserve the product theta structure, hence required a very costly disentangling which
made the algorithm almost impractical. This drawback does not exist the new approach. We stress
however that our new approach has not yet been implemented for cyclic isogenies, so we leave the
practical complexity for future work (see Remark 6.6).

We note that apart from isogeny computations, being able to change level allows us to give equivalent
of Thomae formula for theta functions of higher level. These could also be used to compute modular
forms (expressed as polynomials of theta functions of suitable levels), but unfortunately our method
only gives the projective theta constants, not the affine (modular) ones, so for now we can only apply
our results to modular functions. See Section 1.3 for more details.

1.2. **Outline.** For simplicity we work over the base field $\mathbb{C}$. Since our resulting algorithms are given by polynomial equations, by standard lifting and rigidity arguments they apply over algebraically closed field of characteristic $p$ too as long as everything is étale, that is as long as $p$ is prime to $\ell n$. Indeed, the moduli stack of abelian varieties with a symmetric level $\ell n$ structure is smooth over $\mathbb{Z}[\frac{1}{\ell n}]$, so we can lift them to characteristic zero (this works even for non ordinary abelian varieties). Alternatively it is not hard to use Mumford's algebraic theory [Mum66] to give direct proofs, we refer to [Rob21, § 2.10] for this. Concerning the field of definition in Theorem 1.3, we explain in Remark 4.6 how to adapt the methods of [LR15] to compute the isogeny $f$ using computations in the field of definition of $K$.

In Section 2, we review the theory of theta functions. Let $A$ be an abelian variety and $H$ a polarisation
of $A$. We define the “universal theta group” $\mathfrak{G}(H)$ associated to $H$, and the theta group $G(\mathcal{L})$ (a
subgroup of $\mathfrak{G}(H)$) associated to a line bundle $\mathcal{L}$ whose polarisation is $H$. The group $\mathfrak{G}(H)$ acts on
analytic functions, and this gives an action of $G(\mathcal{L})$ on sections of $\mathcal{L}$. The group $\mathfrak{G}(H)$ may be seen
as the theta group of all isogenous abelian varieties with polarisation given by $H$ glued together. In
Proposition 2.11, we give a simple recipe to recover the basis of theta functions from just one section $u$
of $\mathcal{L}$ and the action of $G(\mathcal{L})$. As an application, we recover Mumford’s isogeny theorem, and explain
how to compute theta functions of isogenous abelian varieties in Proposition 2.15.

In Section 3, we explain how we may compute the action of a larger group $G'$ than $G(\mathcal{L})$ on sections of $\mathcal{L}$, namely $G' = \{g \in \mathfrak{G}(H) \mid g^\ell \in G(\mathcal{L})\}$. A caveat is that sections are no longer sent to sections, so algebraically the action involves some non-canonical choices.

In Section 4.1, as an application, we show how to use this extended action to go up in level along an
isogeny, i.e. given an isogeny $f: A' \to A$, recover the theta basis for $f^*\mathcal{L}$. Then in Section 4.2, given
a decomposition $\ell = \sum a_i^2$, we construct a section $u$ of $\mathcal{L}^\ell$ from sections of $\mathcal{L}$, and we use the action
of $G'$ determined previously on these sections to compute the action of $\mathfrak{G}(\ell H)$ on $u$, hence of $G(\mathcal{L}^\ell)$
on $u$. Here the action does give sections, so the choices we made earlier all give the same final result.
Applying Proposition 2.11 then gives our basis of theta functions of level $\ell n$ on $A$. The full algorithm is
described in Theorem 4.3 and its application to isogenies in Corollary 4.5.
In Section 5, we explain how to descend in level. Finally in Section 6, we outline how to extend our algorithms to the case of real multiplication.

1.3. **Open problem.** A drawback of Proposition 2.11 for constructing theta functions is that it only works projectively, i.e. our basis of theta functions is defined up to a constant. But theta constants are also modular forms (of weight 1/2), so given a period matrix $\Omega$ there is a canonical affine basis of theta function (the basis $\theta_{[i/n]_0}(z, \Omega/n)$). Algebraically, to a basis of differential forms $w_1, \dots, w_g$ on $A$, corresponds a canonical theta constant (up to a sign) depending only on $w_1 \wedge \cdots \wedge w_g$. Keeping this basis when going up, or pushing it forward through an isogeny, this also defines canonical theta coordinates of level $\ell n$. We leave as an open problem working out exactly how to get the correct coordinates as modular forms. For the older isogeny algorithm of [LR12; CR15], getting this correct constant was done in [KNR+20], which was used to compute modular forms.

As mentioned in the introduction, the importance of this problem lies in the following: by [Igu66], every modular form of a certain level $N$ is integral over a suitable ring of theta constants. Hence being able to evaluate theta constants of arbitrary level would allow to evaluate algebraically modular forms of any level (provided we are able to express its minimal polynomial over the theta constants and then select the correct root). Unfortunately, as long as we are not able to get the correct constant, we can only use the results of this paper to evaluate modular functions of level $N$, and not modular forms.

2. CONSTRUCTING THETA FUNCTIONS

In order to fix the notations, we briefly review complex abelian varieties and theta functions and refer to [BL04; Mum83; Mum84] for more details. Our presentation follows closely that of [BL04, Ch. 6] with slight changes in the definition of theta structure and symmetric theta structure for the sake of simplicity. Let $A = V/\Lambda$ be a complex abelian variety, where $V = \mathbb{C}^g$ and $\Lambda$ is a $\mathbb{Z}$-lattice in $V$ of rank $2g$. We denote by $\pi : V \to A$ the canonical projection.

2.1. **Line bundles.** Projective coordinates on $A$ are given by analytic functions $u : V \to \mathbb{C}$ which are periodic with respect to $\Lambda$ up to some automorphic factors: $u(z + \lambda) = a_{\mathcal{L}}(z, \lambda)^{-1}u(z)$ for $z \in V$, $\lambda \in \Lambda$. The factors $a_{\mathcal{L}}(z, \lambda)$ verify the cocycle condition $a_{\mathcal{L}}(z, \lambda_1 + \lambda_2) = a_{\mathcal{L}}(z, \lambda_1)a_{\mathcal{L}}(z + \lambda_1, \lambda_2)$, $z \in V$, $\lambda_1, \lambda_2 \in \Lambda$. Equivalently, the automorphic factor $a_{\mathcal{L}}$ defines a line bundle $\mathcal{L}$ on $A$ as the quotient of the trivial line bundle on $V \times \mathbb{C}$ over $V$ by the action of $\Lambda$ given by $\lambda.(v, t) \mapsto (v + \lambda, a_{\mathcal{L}}(z, \lambda)t)$.

The possible automorphic factors are classified by the Appel–Humbert theorem. Up to changing the automorphic factor by a suitable coboundary (this simply changes the corresponding line bundle by an isomorphism), we have $a_{\mathcal{L}}(z, \lambda) = \chi_{\mathcal{L}}(\lambda)e^{\pi i/2H_{\mathcal{L}}(\lambda, \lambda)}e^{\pi H_{\mathcal{L}}(z, \lambda)}$, where $H_{\mathcal{L}}$ is an Hermitian form on $V$ associated to $\mathcal{L}$. The Hermitian form $H_{\mathcal{L}}$ is such that if $E_{\mathcal{L}} = \Im H_{\mathcal{L}}$ (where $\Im$ stands for the imaginary part), $E_{\mathcal{L}}(\Lambda, \Lambda) \subset \mathbb{Z}$, and $\chi_{\mathcal{L}}$ is a semi-character for $H_{\mathcal{L}}$ [BL04, Th 2.2.3]. We recall that a semi-character for $H_{\mathcal{L}}$ is a map $\chi : \Lambda \to \mathbb{C}_1$, satisfying $\chi(\lambda + \lambda') = \chi(\lambda)\chi(\lambda')e^{i\pi E_{\mathcal{L}}(\lambda, \lambda')}$ for all $\lambda, \lambda' \in \Lambda$.

One can recover $H_{\mathcal{L}}$ from $E_{\mathcal{L}}$, so we will call either a Riemann form of $\mathcal{L}$. The Riemann form of $\mathcal{L}$ characterizes its algebraic equivalence class. The map $\mathcal{L} \mapsto (\chi_{\mathcal{L}}, H_{\mathcal{L}})$ is a bijective correspondence between isomorphism classes of line bundles and their associated semi-characters and Riemann forms.

The algebraic equivalence class $H_{\mathcal{L}}$ of a line bundle $\mathcal{L}$ is called a polarisation on $A$. The data of the polarisation associated to $\mathcal{L}$ is equivalent to that of the morphism $\varphi_{\mathcal{L}} : A \to \tilde{A}$, $x \mapsto \tau_x^*\mathcal{L}.\mathcal{L}^{-1}$ whose analytic form is $z \mapsto H_{\mathcal{L}}(z, \cdot)$. We recall that $\mathcal{L}$ is ample if and only if either $\varphi_{\mathcal{L}}$ is an isogeny or $H_{\mathcal{L}}$ is definite positive. The symplectic form $E_{\mathcal{L}}$ allows to define the Weil pairing on $K(\mathcal{L})$ by $e_{\mathcal{L}}(\bar{x}_1, \bar{x}_2) = e^{-2\pi i E_{\mathcal{L}}(x_1, x_2)}$, where $\bar{x}_i = x_i$ mod $\Lambda$ for $i = 1, 2$. We denote by $K(\mathcal{L}) = \text{Ker } \varphi_{\mathcal{L}}$ the kernel of the polarisation, we have $K(\mathcal{L}) \simeq \Lambda(\mathcal{L})/\Lambda$, where $\Lambda(\mathcal{L}) = \Lambda^{\perp_{E_{\mathcal{L}}}}$ is the $e_{\mathcal{L}}$-orthogonal of $\Lambda$. We say that $\mathcal{L}$ is of type $n$ if $E_{\mathcal{L}}$ is of type $n$ on $\Lambda$, in which case $K(\mathcal{L}) \simeq (\mathbb{Z}/n\mathbb{Z})^{2g}$; equivalently $\mathcal{L} = \mathcal{L}_0^n$ is the $n$-th power of a principal line bundle (associated to the Hermitian form $H_{\mathcal{L}_0} = H_{\mathcal{L}}/n$).

Assume that we have a symplectic decomposition $\Lambda = \Lambda_1 \oplus \Lambda_2$ of $\Lambda$ for a Riemann form $E_{\mathcal{L}}$. We will denote such a decomposition by $\sigma = (\sigma_1, \sigma_2)$ where $\sigma_i$ is the projector onto $\Lambda_i$. Using $\sigma$, we can define a canonical semi-character by $\chi(\lambda) = e^{\pi i E(\sigma_1(\lambda), \sigma_2(\lambda))}$ [BL04, Lem. 3.1.1], which by Appel–Humbert theorem gives a canonical symmetric line bundle $\mathcal{L}^{\sigma}$, which we will often denote by $\mathcal{L}$ for simplicity.
**Remark 2.1.** For reasons explained in Section 3, we will mostly consider the case when the level $n$ is even. In this case, all the symplectic decompositions $\sigma$ of $\Lambda$ give $\chi_{\mathcal{L}^\sigma} = 1$, hence the line bundle associated by Appel-Humber thorem to the canonical semi-character does not depend on the choice of a symplectic decomposition of $\Lambda$. This means that $\mathcal{L}$ is the unique (totally) symmetric line bundle in the algebraic class given by $H$, i.e. the unique line bundle in this algebraic equivalence class such that $\mathcal{L} = \mathcal{L}_0^n$ with $\mathcal{L}_0$ principal symmetric.

**2.2. The theta group.** In this section, we introduce the theta group and study two important properties of that group that we will use, namely :

* the structure of extensions of $V$ by $\mathbb{C}^*$ and the existence of sections above $V$;

* the action of the theta group on sections of $\mathcal{L}$.

Following [BL04, Ch. 6], we denote by $\mathfrak{G}(\mathcal{L}) = \{[\alpha, w] | \alpha \in \mathbb{C}^*, w \in V\}$ the group with composition law $[\alpha_1, w_1].[\alpha_2, w_2] = [\alpha_1\alpha_2e^{\pi H_{\mathcal{L}}(w_2,w_1)}, w_1 + w_2]$. We can interpret $\mathfrak{G}(\mathcal{L})$ as the automorphism group of the trivial line bundle $\pi^*\mathcal{L} \simeq V \times \mathbb{C}$ above translations on $V$. Note that $\mathfrak{G}(\mathcal{L})$ only depends on $H_{\mathcal{L}}$, so we may also use the notation $\mathfrak{G}(H_{\mathcal{L}})$ (or $\mathfrak{G}(H)$ if $H$ is a general Riemann form).

The group $\mathfrak{G}(\mathcal{L})$ is non-commutative. If $z_1, z_2 \in V$, $g_1 = [\alpha_1, z_1]$, $g_2 = [\alpha_2, z_2]$ two elements of $\mathfrak{G}(\mathcal{L})$ above $z_1$ and $z_2$, we also recover the Weil pairing $e_{\mathcal{L}}$ as the commutator pairing: $g_1g_2g_1^{-1}g_2^{-1} = [e^{-2i\pi E_{\mathcal{L}}(z_1,z_2)}, 0]$. It is clear that $\mathfrak{G}(\mathcal{L})$ is a central extension of $V$ by $\mathbb{C}^*$. In order to study its sections above $V$, we need the following definition:

**Definition 2.2.** Let $H$ be a Riemann form on $V$. Let $\sigma: V = V_1 \oplus V_2$ be a symplectic decomposition of $V$ for $E$. Let $\Lambda$ be a lattice of $V$, we say that $\Lambda$ is compatible with $\sigma$ if $\Lambda = \Lambda \cap V_1 \oplus \Lambda \cap V_2$. We remark that $\Lambda$ is compatible with $\sigma$ if and only if $\Lambda^\perp$ is.

A symplectic decomposition $\sigma$ on $\Lambda$ induces a symplectic decomposition $\sigma \otimes \mathbb{R}: V \to V_1 \oplus V_2$ on $V$ which is compatible with $\Lambda$. This allows to extend $a_{\mathcal{L}^\sigma}$ to all of $V \times V$ via $a_{\mathcal{L}^\sigma}(v, \lambda) = e^{\pi i E(\sigma_1(\lambda), \sigma_2(\lambda))}e^{\pi/2H(\lambda, \lambda)}e^{\pi H(v, \lambda)}$, for all $(v, \lambda) \in V \times V$. This extension does not satisfy the cocycle condition and thus is not an automorphy factor.

**Lemma 2.3.** Let $H$ be a Riemann form on $V$. Let $\sigma: V = V_1 \oplus V_2$ be a symplectic decomposition of $V$ for $E = \mathfrak{H}$. Let $\Lambda'$ be a lattice in $V$ compatible with $\sigma$.

Then $\Lambda'$ is isotropic for $E$ (i.e. $E(\Lambda', \Lambda') \subset \mathbb{Z}$) if and only if $a_{\mathcal{L}^\sigma}$ satisfies the cocycle condition on $V \times \Lambda'$, if and only if there is a group section $s_{\Lambda'}: \Lambda' \to \mathfrak{G}(\mathcal{L})$.

In this case, the map

$$s_{\sigma}: \Lambda' \to \mathfrak{G}(\mathcal{L})$$

$$s_{\sigma}(\lambda) = [a_{\mathcal{L}^{\sigma}}(0, \lambda), \lambda] = [e^{\pi i E_{\mathcal{L}}(\sigma_1(\lambda), \sigma_2(\lambda))} e^{\pi/2 H_{\mathcal{L}}(\lambda, \lambda)}, \lambda].$$

is an explicit group section.

*Proof.* Writing the cocycle condition for $a_{\mathcal{L}^\sigma}$ or $V \times \Lambda'$, it is easy to see that it is equivalent to $\Lambda'$ being isotropic for $E$. If there is a group section $\Lambda' \to \mathfrak{G}(\mathcal{L})$, then the commutator interpretation of the Weil-pairing show that $\Lambda'$ has to be isotropic, since $s(\Lambda')$ is commutative.

Finally, if $\Lambda'$ is isotropic, it remains to check that $s_\sigma$ is a group section. We have seen that $a_{\mathcal{L}^\sigma}$ verifies the cocycle condition. We then have $[a_{\mathcal{L}^\sigma}(0, \lambda + \lambda'), \lambda + \lambda'] = [a_{\mathcal{L}^\sigma}(0, \lambda')a_{\mathcal{L}^\sigma}(\lambda', \lambda), \lambda + \lambda'] = [a_{\mathcal{L}^\sigma}(0, \lambda)a_{\mathcal{L}^\sigma}(0, \lambda')a_{\mathcal{L}^\sigma}(\lambda', \lambda)/a_{\mathcal{L}^\sigma}(0, \lambda), \lambda + \lambda'] = [a_{\mathcal{L}^\sigma}(0, \lambda), \lambda][a_{\mathcal{L}^\sigma}(0, \lambda'), \lambda']$. $\square$

The group $\mathfrak{G}(\mathcal{L})$ acts on analytic functions $u$ in $V$ via $[\alpha, w] \circ (\mathrm{Id} \times u) = (\mathrm{Id} \times [\alpha, w] \cdot u) \circ t_{-w}$, where $t_{-w}(z) = z - w$, namely we have:

$$(2) \qquad [\alpha, w] \cdot u(z) = \alpha e^{\pi H_{\mathcal{L}}(z-w,w)} u(z-w).$$

Let $\sigma: V = V_1 \oplus V_2$ be a symplectic decomposition of $V$ and suppose that $\Lambda$ is compatible with $\sigma$. By Lemma 2.3, we have a group section $s_\sigma: \Lambda \to \mathfrak{G}(\mathcal{L})$. We may extend it to a set section on the whole of $V$ via $s_\sigma(v) = [a_{\mathcal{L}^\sigma}(0, v), v]$.

We have:
**Lemma 2.4.** [BL04, Th. 6.1.3] The automorphism group $G(\mathcal{L})$ of $\mathcal{L}$ is equal to $G(\mathcal{L}) = Z(s(\Lambda))/s(\Lambda)$, where $Z(s(\Lambda))$ denotes the commutator of $s(\Lambda)$ in $\mathfrak{G}(H_{\mathcal{L}})$. The action of Equation (2) induces an action of $G(\mathcal{L})$ on $\Gamma(A, \mathcal{L})$.

Explicitly, for $\lambda \in \Lambda(\mathcal{L})$ and $u \in \Gamma(A, \mathcal{L})$, we have

$$ (3) \qquad s_{\sigma}(\lambda) \cdot u(z) = a_{\mathcal{L}}(z - \lambda, \lambda)u(z - \lambda). $$

*Proof.* As $\mathcal{L}$ is the quotient of the trivial bundle over $V$ by the action of $s_{\sigma}(\Lambda)$, it is clear that $s_{\sigma}(\Lambda)$ acts trivially on $\Gamma(A, \mathcal{L})$ (in fact by definition $\Gamma(A, \mathcal{L})$ are exactly the analytic functions on $V$ fixed by this subgroup). In particular, the action (2) restricted to elements of $Z(s(\Lambda))$ sends sections of $\mathcal{L}$ to other sections, hence induces an action of $G(\mathcal{L})$ on $\Gamma(A, \mathcal{L})$. Equation (3) is a simple computation. $\square$

**2.3. Theta structures.** In this section, we introduce the notion of theta structure. Let $(A = V/\Lambda, \mathcal{L})$ be a polarised abelian variety. Let $\sigma$ be a symplectic decomposition of $V$ and we suppose that $\Lambda$ is compatible with $\sigma$ and that $\mathcal{L} = \mathcal{L}^{\sigma}$. Remark that, by taking the quotient of $\Lambda(\mathcal{L})$ by $\Lambda$, $\sigma$ induces a decomposition $K(\mathcal{L}) = K_1(\mathcal{L}) \oplus K_2(\mathcal{L})$ for $e_{\mathcal{L}}$. Let $\Lambda'$ be such that $\Lambda' \subset \Lambda \subset \Lambda(\mathcal{L})$, and let $K = \Lambda'/\Lambda$. Then $\Lambda'$ is compatible with $\sigma$ if and only if the symplectic decomposition of $K(\mathcal{L})$ above induces a symplectic decomposition of $K$ for the Weil pairing $e_{\mathcal{L}}: K = K_1 \oplus K_2$ with $K_i = K_i(\mathcal{L}) \cap K$.

Given such a compatible $\Lambda'$, using Lemma 2.3 and Lemma 2.4, $s_{\sigma}(\Lambda')$ induces a canonical section $\tilde{K}$ of $K$ into $G(\mathcal{L})$. Applying this to $\Lambda' = \Lambda_1(\mathcal{L}) \oplus \Lambda_2$ and to $\Lambda' = \Lambda_1 \oplus \Lambda_2(\mathcal{L})$, we get canonical sections $s_1$ and $s_2$ of $K_1(\mathcal{L})$ and $K_2(\mathcal{L})$ (or more generally of any isotropic $K = K_1 \oplus K_2 \subset K_1(\mathcal{L}) \oplus K_2(\mathcal{L})$) into $G(\mathcal{L})$. We stress that these canonical sections depend on a choice of the symplectic decomposition $\sigma$ of $V$, a choice of a symplectic decomposition of $K(\mathcal{L})$ is not sufficient to determine the sections $s_i$. We have proved:

**Proposition 2.5.** Let $(A = V/\Lambda, \mathcal{L})$ be an abelian variety together with an ample line bundle. A choice of $\sigma$, a symplectic decomposition of $\Lambda$ for $E_{\mathcal{L}}$, determines a symplectic decomposition $K(\mathcal{L}) = K_1(\mathcal{L}) \oplus K_2(\mathcal{L})$ and sections $s_i: K_i(\mathcal{L}) \to G(\mathcal{L})$.

This motivates the following definition, slightly adapted from that of [Mum66] and [BL04, Ch. 6.6]

**Definition 2.6.** Let $(A = V/\Lambda, \mathcal{L})$ be an abelian variety of dimension $g$ together with an ample line bundle. Let $K(\mathcal{L})$ be the kernel of the polarisation defined by $\mathcal{L}$. A theta structure $\Theta_{\mathcal{L}}$ for $(A, \mathcal{L})$ is the data of:

* $K(\mathcal{L}) = K_1(\mathcal{L}) \oplus K_2(\mathcal{L})$, a symplectic decomposition of $K(\mathcal{L})$ for $e_{\mathcal{L}}$;

* for $i = 1, 2$, sections $s_i^{\Theta_{\mathcal{L}}}: K_i(\mathcal{L}) \to G(\mathcal{L})$.

Via $s_i^{\Theta_{\mathcal{L}}}$ for $i = 1, 2$, we thus get an action of $K_i(\mathcal{L})$ on $\Gamma(A, \mathcal{L})$. For $i = 1, 2$, if $P \in K_i(\mathcal{L})$, we will denote by $P \cdot u$ the action $s_i^{\Theta_{\mathcal{L}}}(P) \cdot u$ of $s_i^{\Theta_{\mathcal{L}}}(P) \in G(\mathcal{L})$ on $u$.

In the following, if $\sigma: \Lambda = \Lambda_1 \oplus \Lambda_2$ is a symplectic decomposition of $\Lambda$, we denote by $\Theta_{\mathcal{L}}^{\sigma}$ the associated canonical theta structure following Proposition 2.5. We say that $\Theta_{\mathcal{L}}$ is symmetric if there exists a symplectic decomposition $\sigma: \Lambda = \Lambda_1 \oplus \Lambda_2$ such that $\mathcal{L} = \mathcal{L}^{\sigma}$ and $\Theta_{\mathcal{L}} = \Theta_{\mathcal{L}}^{\sigma}$.

**Remark 2.7.** We briefly explain the link between our definition of a symmetric theta structure and the usual one of [Mum66] or [BL04, Ch. 6.9]. Let $\delta_{-1}$ be the group automorphism of $\mathfrak{G}(\mathcal{L})$ defined by $\delta_{-1}([\alpha, w]) = [\alpha, -w]$. Following [Mum66], we say that an element $g$ of $\mathfrak{G}(\mathcal{L})$ is symmetric if $\delta_{-1}g = g^{-1}$. One can check that the sections $s_i^{\Theta_{\mathcal{L}}}$ for $i = 1, 2$ deduced from the symplectic decomposition $\sigma$ have value in symmetric elements of $\mathfrak{G}(\mathcal{L})$, hence symmetric elements of $G(\mathcal{L})$. So a symmetric theta structure following Definition 2.6 is symmetric in the sense of [Mum66].

Changing the symplectic decomposition of $\Lambda$ will thus only change our sections by a sign on each element. Furthermore symplectic decompositions $\sigma$ of $\Lambda$ give the same symmetric theta structure on $G(\mathcal{L})$ whenever they induce the same symplectic decomposition on $K(\mathcal{L}^2) \simeq \frac{1}{2}\Lambda(\mathcal{L})/\Lambda$. Finally, if $\lambda \in \Lambda'$ is of odd order modulo $\Lambda$, then $s_{\sigma}(\lambda)$ is uniquely defined as the unique symmetric lift of order $\ell$, hence does not depend on $\sigma$.

**Definition 2.8.** Let $(A = V/\Lambda, \mathcal{L}, \Theta_{\mathcal{L}})$ be an abelian variety with a symmetric theta structure on $\mathcal{L}$. We say that a symmetric theta structure $\Theta_{\mathcal{L}}$ on $\mathcal{L}^{\ell}$ is compatible with $\Theta_{\mathcal{L}}$ if there exists a symplectic decomposition $\sigma$ of $\Lambda$ such that $\Theta_{\mathcal{L}} = \Theta_{\mathcal{L}}^{\sigma}$ and $\Theta_{\mathcal{L}}^{\ell} = \Theta_{\mathcal{L}}^{\sigma\ell}$.
The importance of theta structures lies in part in the following result (see [Mum66, §1, Th. 2]):

**Theorem 2.9 (Maschke-Mumford).** The vector space $\Gamma(A, \mathcal{L})$ is the unique projective irreducible representation of $G(\mathcal{L})$.

**Corollary 2.10.** Suppose chosen a theta structure $\Theta_{\mathcal{L}}$ for $(A, \mathcal{L})$. There is a unique basis $(\theta_i^{\Theta_{\mathcal{L}}})_{i \in K_2(\mathcal{L})}$ (up to a common projective factor $\mu$) of sections of $\mathcal{L}$ such that $\theta_0^{\Theta_{\mathcal{L}}}$ is invariant under the action of $s_1^{\Theta_{\mathcal{L}}}(K_1(\mathcal{L}))$ and if $i \in K_2(\mathcal{L})$, $\theta_i^{\Theta_{\mathcal{L}}}=s_2^{\Theta_{\mathcal{L}}}(i) \cdot \theta_0^{\Theta_{\mathcal{L}}}$. This basis is called the basis of theta functions of level $n$ if $\mathcal{L}$ is of type $n$.

The action of $s_i^{\Theta_{\mathcal{L}}}(K_i(\mathcal{L}))$ for $i=1,2$ on this basis is given by: $j_1 \cdot \theta_i^{\Theta_{\mathcal{L}}} = e_{\mathcal{L}}(j_1, i)\theta_i$ if $j_1 \in K_1(\mathcal{L})$, and $j_2 \cdot \theta_i^{\Theta_{\mathcal{L}}} = \theta_{i+j_2}^{\Theta_{\mathcal{L}}}$ if $j_2 \in K_2(\mathcal{L})$.

*Proof.* Since $\Gamma(A, \mathcal{L})$ is irreducible, it is isomorphic to the unique irreducible Heisenberg representation of $G(\mathcal{L})$ as described in [Mum66, p. 297], from which we deduce the existence of the basis $(\theta_i^{\Theta_{\mathcal{L}}})$. The computation of the action of $s_i(K_i(\mathcal{L}))$ for $i=1,2$ on the family $(\theta_j^{\Theta_{\mathcal{L}}})_{j \in K_2(\mathcal{L})}$ is immediate from its definition. $\square$

We thus immediately get the following recipe to construct the basis of theta functions of level $n$ associated to a theta structure $\Theta_{\mathcal{L}}$:

**Proposition 2.11.** Let $\Theta_{\mathcal{L}}$ be a theta structure for $(A, \mathcal{L})$. Let $u$ be any section of $\Gamma(A, \mathcal{L})$ such that if $u = \sum \lambda_i \theta_i^{\Theta_{\mathcal{L}}}$, $\lambda_0 \neq 0$. Then, up to a constant, we have $\theta_0^{\Theta_{\mathcal{L}}} = \sum_{j \in K_1(\mathcal{L})} s_1^{\Theta_{\mathcal{L}}}(j) \cdot u$, and for $i \in K_2(\mathcal{L})$, $\theta_i^{\Theta_{\mathcal{L}}} = s_2(i) \cdot \theta_0^{\Theta_{\mathcal{L}}}$.

We remark that using Mumford's algebraic theory of theta functions, the above Proposition is valid for any theta structure of level $n$ prime to the characteristic of the base field.

**Remark 2.12.** If $u$ is such that $\lambda_0 = 0$, we can still reconstruct our theta basis as follows: assume that $\lambda_i \neq 0$. Then since $\Gamma(A, \mathcal{L})$ decomposes into a sum of 1-dimensional eigenspaces for the action of $G(\mathcal{L})$: $\Gamma(A, \mathcal{L}) = \oplus_{\chi \in K_1(\mathcal{L})} \Gamma(A, \mathcal{L})^{\chi}$, and $\theta_i^{\Theta_{\mathcal{L}}}$ is a generator of $\Gamma(A, \mathcal{L})^{\chi}$ for the character $\chi = e_{\mathcal{L}}(i, \cdot)$, we recover $\theta_i^{\Theta_{\mathcal{L}}}$ as the trace of $u$ under $K_1(\mathcal{L})$ twisted by this character: $\theta_i^{\Theta_{\mathcal{L}}} = \sum_{j \in K_1(\mathcal{L})} e_{\mathcal{L}}(i, j)s(j) \cdot u = \sum_{j \in K_1(\mathcal{L})} s(i+j) \cdot u$ (alternatively one could take the trace applied to $s(-i) \cdot u$). Then $\theta_{i'}^{\Theta_{\mathcal{L}}} = s(i-i') \cdot \theta_i^{\Theta_{\mathcal{L}}}$.

**Example 2.13.** Let $\sigma : \Lambda = \Lambda_1 \oplus \Lambda_2$ be a symplectic decomposition and let $(\theta_i^{\Theta_{\mathcal{L}}})_{i \in K_2(\mathcal{L})}$ be the associated basis of theta functions. Then permuting this decomposition $\sigma' : \Lambda = \Lambda_2 \oplus \Lambda_1$ gives another basis $(\theta_i^{\Theta_{\mathcal{L}}'})$, indexed by $i \in K_1(\mathcal{L})$.

Applying Proposition 2.11, we get that (up to a constant), $\theta_0^{\Theta_{\mathcal{L}}'} = \sum_{j \in K_2(\mathcal{L})} \theta_j^{\Theta_{\mathcal{L}}'}$, and if $i \in K_1(\mathcal{L})$, $\theta_i^{\Theta_{\mathcal{L}}'} = i \cdot \theta_0^{\Theta_{\mathcal{L}}'} = \sum_{j \in K_2(\mathcal{L})} e_{\mathcal{L}}(i, j) \theta_j^{\Theta_{\mathcal{L}}'}$.

**2.4. Theta groups and isogenies.** Let $A = V_A/\Lambda_A$, $B = V_B/\Lambda_B$ be dimension $g$ abelian varieties. Let $f: A \to B$ be an isogeny, let $F: V_A \to V_B$ be the analytic representation of $f$. Let $\mathcal{M}$ be a line bundle on $B$ with polarisation $H_{\mathcal{M}}$, then $\mathcal{L} = f^*\mathcal{M}$ has associated polarisation $H_{\mathcal{L}} = F^*H_{\mathcal{M}}$. We have a map $F: \mathfrak{G}(\mathcal{L}) \to \mathfrak{G}(\mathcal{M})$, $[\alpha, w] \mapsto [\alpha, F(w)]$, which is compatible with the action on sections: if $u$ is an analytic function on $V_B$, then:

$$ (4) \qquad [\alpha, w] \cdot F^*u = F^*([\alpha, F(w)] \cdot u). $$

Fix $\sigma = (\sigma_1, \sigma_2)$ a symplectic decomposition of $\Lambda_A$ with respect to $H_{\mathcal{L}}$, let $K(\mathcal{L}) = K_1(\mathcal{L}) \oplus K_2(\mathcal{L})$ the symplectic decomposition of $K(\mathcal{L})$ deduced from $\sigma$. Assume that $\Lambda' = F^{-1}(\Lambda_B) \subset \Lambda(\mathcal{L})$ is compatible with $\sigma$. This means that there exists a symplectic decomposition of $K = \text{Ker } f$, $K = K_1 \oplus K_2$ such that $K_i = K \cap K_i(\mathcal{L})$. Then pushing $\sigma$ through $F$, we obtain a symplectic decomposition of $\Lambda_B$ that we denote by $F_*(\sigma \otimes \mathbb{R})|_{\Lambda_B} = F_*(\sigma \otimes \mathbb{R}|_{\Lambda'})$. Concretely, $F_*(\sigma_i \otimes \mathbb{R}) = F \circ (\sigma_i \otimes \mathbb{R}) \circ F^{-1}$. If $\mathcal{M}$ is the line bundle corresponding to the canonical automorphic factor $a_{\mathcal{M}}$ associated to $F_*(\sigma \otimes \mathbb{R})$ and $\mathcal{L}$ is the line bundle corresponding to $\sigma$, then we check that $a_{\mathcal{M}}(F(v), F(\lambda)) = a_{\mathcal{L}}(v, \lambda)$, hence $f^*\mathcal{M} = \mathcal{L}$.
Using Lemma 2.3, we have sections $s_{\Lambda_A}$, $s_{\Lambda_B}$ and $s_{\Lambda'}$ respectively on $\Lambda_A$, $\Lambda_B$ and $\Lambda'$ which verify $s_{\Lambda'}(\lambda') = s_{\Lambda_B}(F(\lambda'))$. Taking the quotient modulo $s_{\Lambda'}(\Lambda_A)$, we get a canonical section $\bar{s} : K \to G(\mathcal{L})$. Since $G(\mathcal{M}) = Z(s_{\Lambda_B}(\Lambda_B))/s_{\Lambda_B}(\Lambda_B)$, we get that $G(\mathcal{M}) \simeq Z(s(K))/s(K)$.

**Definition 2.14.** Let $(A = V_A/\Lambda_A, \mathcal{L}, \Theta_{\mathcal{L}})$ and $(B = V_B/\Lambda_B, \mathcal{M}, \Theta_{\mathcal{M}})$ be abelian varieties together with symmetric theta structures, and let $f : A \to B$ be an isogeny with analytic representation $F$. We say that $\Theta_{\mathcal{L}}$ and $\Theta_{\mathcal{M}}$ are compatible (along $F$) if there exists symplectic decompositions $\sigma_A$ and $\sigma_B$ such that $F_*(\sigma_A \otimes \mathbb{R}) = \sigma_B \otimes \mathbb{R}$ and $H_{\mathcal{L}} = F^*H_{\mathcal{M}}, \mathcal{L} = \mathcal{L}^{\sigma_A}, \mathcal{M} = \mathcal{M}^{\sigma_B}, \Theta_{\mathcal{L}} = \Theta_{\mathcal{L}}^{\sigma_A}, \Theta_{\mathcal{M}} = \Theta_{\mathcal{M}}^{\sigma_B}$.

Using Proposition 2.11, we get the following proposition which immediately provides an algorithm to construct theta coordinates on $(B, \mathcal{M})$, provided that we have a section $u \in \Gamma(A, \mathcal{L})$ on which we know the action of $G(\mathcal{L})$:

**Proposition 2.15.** Let $\sigma$ be a symplectic decomposition of $\Lambda$ from which we deduce a decomposition of $K(\mathcal{L}) = K_1(\mathcal{L}) \oplus K_2(\mathcal{L})$. Let $K$ be a finite subgroup of $A$ isotropic for the Weil pairing and compatible with $\sigma$ that is $K = K_1 \oplus K_2$ where $K_i = K \cap K_i(\mathcal{L})$ for $i=1,2$. Let $f : (A, \mathcal{L}) \to (B = A/K, \mathcal{M})$ be the corresponding isogeny with analytic representation $F$ and such that $f^*\mathcal{M} = \mathcal{L}$. Given the symmetric theta structure $\Theta_{\mathcal{L}} = \Theta_{\mathcal{L}}^{\sigma_A}$ on $\mathcal{L}$, there is a unique compatible symmetric theta structure $\Theta_{\mathcal{M}}$ on $\mathcal{M}$: in other words, $\Theta_{\mathcal{M}}$ only depends on $\Theta_{\mathcal{L}}$ and not on the decomposition $\sigma$ used to define $\Theta_{\mathcal{L}}$.

Let $u$ be a non-trivial section of $\Gamma(A, \mathcal{L})$. Up to a constant, we have $F^*\theta_0^{\Theta_{\mathcal{M}}^{\sigma_A}} = \sum_{j \in K_1^{\perp e_{\mathcal{L}} \oplus K_2}} s(j) \cdot u$ (assuming this trace is non-zero), and for $i \in K_2^{\perp e_{\mathcal{L}}}$, $F^*\theta_{f(i)}^{\Theta_{\mathcal{M}}^{\sigma_A}} = s(i) \cdot \theta_0^{\Theta_{\mathcal{M}}^{\sigma_A}}$.

*Proof.* From the discussion above, $\mathcal{M}$ is the quotient of $\mathcal{L}$ by the action defined by the section $\tilde{K} \subset G(\mathcal{L})$ of $K = K_1 \oplus K_2$ given by $\tilde{K} = s_1(K_1)s_2(K_2)$ (since $K$ is isotropic, these two subgroups commute so their product defines a lift).

Using [Mum66, §1, Prop. 2], we have $K(\mathcal{M}) \simeq K_1^{\perp e_{\mathcal{L}}}/K_1 \oplus K_2^{\perp e_{\mathcal{L}}}/K_2$. For $i=1,2$, Let $K_i(\mathcal{M}) = K_i^{\perp e_{\mathcal{L}}}/K_i$ and let $s_i^{\Theta_{\mathcal{M}}^{\sigma_A}} : K_i(\mathcal{M}) \to G(\mathcal{L})$ (resp. $s_i^{\Theta_{\mathcal{M}}^{\sigma_A}} : K_i(\mathcal{M}) \to G(\mathcal{M})$) be the sections defining the theta structure $\Theta_{\mathcal{L}}^{\sigma_A}$ (resp. $\Theta_{\mathcal{M}}^{\sigma_A}$). Then we have $s_i^{\Theta_{\mathcal{M}}^{\sigma_A}}(P) = F(s_i^{\Theta_{\mathcal{L}}^{\sigma_A}}(P'))$ for $P' \in K_i^{\perp e_{\mathcal{L}}}$ such that $P = f(P')$. This shows that $\Theta_{\mathcal{M}}^{\sigma_A}$ is unique. Taking a trace of $u$ under $\tilde{K}$, we get a section of $\mathcal{M}$ since $\Gamma(B, \mathcal{M}) = \Gamma(A, \mathcal{L})^{s(K)}$. We can then apply Proposition 2.11 to this trace to obtain the result. $\square$

If the trace of $u$ under $K_1^{\perp e_{\mathcal{L}}} \oplus K_2$ is zero, then since $u$ is non-trivial and $\Gamma(A, \mathcal{L})$ is irreducible there always exists an element in $g \in G(\mathcal{L})$ such that the trace of $g \cdot u$ will be non-zero. It is only in this case that we need the full action of $G(\mathcal{L})$. In general, we only need to be able to compute the action of $Z(s(K))$ to recover $\Theta_{\mathcal{M}}$.

**Remark 2.16.** As an aside of the preceding proof, if $\#K$ is odd, then by Remark 2.7, $\tilde{K}$, hence $\mathcal{M}$, does not depend on $\sigma$.

**Example 2.17.** Applying Proposition 2.15 to $u = \theta_0^{\Theta_{\mathcal{L}}^{\sigma_A}}$, we recover Mumford's isogeny theorem (compare with [BL04, Th. 6.8.2]): up to a constant, for $i \in K_2^{\perp e_{\mathcal{L}}}$, $F^*\theta_{f(i)}^{\Theta_{\mathcal{M}}^{\sigma_A}} = \sum_{j \in K_2} \theta_{i+j}^{\Theta_{\mathcal{L}}^{\sigma_A}}$.

Indeed, by definition $K_1(\mathcal{L})$ acts trivially on $\theta_0^{\Theta_{\mathcal{L}}^{\sigma_A}}$, and if $j \in K_2(\mathcal{L})$, $j \cdot \theta_0^{\Theta_{\mathcal{L}}^{\sigma_A}} = \theta_j^{\Theta_{\mathcal{L}}^{\sigma_A}}$.

**Example 2.18.** Given $\sigma : \Lambda = \Lambda_1 \oplus \Lambda_2$ a symplectic decomposition of $\Lambda$, up to an automorphism of $V = \mathbb{C}^g$, we can assume that $\Lambda_2 = \mathbb{Z}^g$. Then $\Lambda_1 = \Omega\mathbb{Z}^g$ where $\Omega$ is a $g \times g$ matrix with complex coefficients called period matrix of $A$. The data of a period matrix is equivalent to the data of $\Lambda$, a principal Riemann form $H_0$ with matrix representation $\Theta(\Omega^{-1})$ on $V$ and a symplectic decomposition of $\Lambda = \Omega\mathbb{Z}^g \oplus \mathbb{Z}^g$ for $H_0$. Let $H = nH_0$ and $\mathcal{L}$ the line bundle associated to the symplectic decomposition given by $\Omega$ in the algebraic class defined by $H$.

Recall the definition of the analytic theta functions with characteristics:

$$ \theta[a]_b(z, \Omega) = \sum_{n \in \mathbb{Z}^g} e^{\pi i t(n+a)\Omega(n+a) + 2\pi i t(n+a)(z+b)}, \text{ for } a, b \in \mathbb{Q}^g. $$

We have $K_2(\mathcal{L}) = \frac{1}{n}\mathbb{Z}^g/\mathbb{Z}^g \simeq (\mathbb{Z}/n\mathbb{Z})^g$. Under this isomorphism, the classical basis of level $n$ theta functions is given by $\theta_i(z, \Omega) = \theta[i/n](z, \Omega/n)$ (see [Mum83, Chap. II, Prop. 1.3]). These functions
are automorphic with respect to the classical factor of automorphy from Equation (1) rather than the canonical one from Section 2.1. These two automorphic factors differ by a coboundary, and using this coboundary one can translate the above theory to classical theta functions.

Mumford's isogeny theorem from Example 2.17 applied to the isogeny $A = \mathbb{C}^g/(\Omega\mathbb{Z}^g \oplus \mathbb{Z}^g) \to B = \mathbb{C}^g/(\Omega\mathbb{Z}^g \oplus \mathbb{Z}^g)$ becomes the following tautological equation between classical theta functions of level $\ell n$ on $A$ and classical theta functions of level $n$ on $B$: for $b \in \mathbb{Z}^g$,

$$ \theta[b/n] (z, \frac{\Omega/\ell}{n}) = \theta[\ell b/\ell n] (z, \Omega/\ell n). $$

### 3. AFFINE LIFTS AND RIEMANN RELATIONS

Let $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ be an abelian variety together with a line bundle and a symmetric theta structure of even level $n$. We have seen that $\Theta_{\mathcal{L}}$ defines an embedding $\iota_{\Theta_{\mathcal{L}}} : A \to \mathbb{P}^{K_2(\mathcal{L})}$, $P \mapsto (\theta_i^{\Theta_{\mathcal{L}}}(P))_{i \in K_2(\mathcal{L})}$. In this section, we gather some useful definitions and results from [LR10; LR15] to obtain the main ingredients of our algorithms.

**Definition 3.1.** We call any preimage $\tilde{P} \in \mathbb{A}^{K_2(\mathcal{L})}$ of $P$ for the canonical projection $\mathbb{A}^{K_2(\mathcal{L})} \to \mathbb{P}^{K_2(\mathcal{L})}$ an affine lift. If $\tilde{P}$ is an affine lift of $P$ and $i \in K_2(\mathcal{L})$, we denote by $(\tilde{P})_i$ or $\theta_i(\tilde{P})$ the $i^{th}$-coordinate of $\tilde{P}$, so $\tilde{P} = (\theta_i(\tilde{P}))_{i \in K_2(\mathcal{L})}$.

$$ \text{Let } * : \mathbb{C}^* \times \mathbb{A}^{K_2(\mathcal{L})} \to \mathbb{A}^{K_2(\mathcal{L})} \text{ be the action } (\lambda, \tilde{P}) \mapsto (\lambda(\tilde{P})_i)_{i \in K_2(\mathcal{L})}. $$

If $P$ is a point of $A = V/\Lambda$, we denote by $z_P \in V$ any element whose equivalence class modulo $\Lambda$ is $P$. The element $z_P$ defines an analytic affine lift $\tilde{P} = (\theta_i^{\Theta_{\mathcal{L}}}(z_P))_{i \in K_2(\mathcal{L})}$ of $P$. The action of $\mathfrak{G}(\mathcal{L})$ on analytic functions extends to vectors of analytic functions by acting coordinate by coordinate, this induces an action of $G(\mathcal{L})$ on vectors of sections of $\mathcal{L}$, and thus an action of $G(\mathcal{L})$ on $\tilde{P}$.

We can construct the affine translation by points $z_P \in V$ on theta functions explicitly via the use of Riemann relations. In this section, in order to ease the notations, we omit the theta structure symbol when we name theta functions: for $i \in K_2(\mathcal{L})$, $\theta_i = \theta_i^{\Theta_{\mathcal{L}}}$.

**Definition 3.2.** If $\mathcal{V}$ is a commutative group, we say that the elements $v_1, v_2, v_3, v_4; w_1, w_2, w_3, w_4$ are in Riemann position whenever there exists $u \in \mathcal{V}$ such that $w_i = v_i + u$ and $v_1 + v_2 + v_3 + v_4 = -2u$.

**Theorem 3.3 (Riemann's relations).** Let $z_1, z_2, z_3, z_4; z'_1, z'_2, z'_3, z'_4 \in V$ and $i_1, i_2, i_3, i_4; i'_1, i'_2, i'_3, i'_4 \in K_2(\mathcal{L})$ be in Riemann position. Let $T = K_2(\mathcal{L})[2] \simeq (\mathbb{Z}/2\mathbb{Z})^g$. Then for any character $\chi$ on $T$, we have

$$ (5) \quad \left( \sum_{t \in T} \chi(t) \theta_{i_1+t}(z_1) \theta_{i_2+t}(z_2) \right) \left( \sum_{t \in T} \chi(t) \theta_{i_3+t}(z_3) \theta_{i_4+t}(z_4) \right) = \\ \qquad \left( \sum_{t \in T} \chi(t) \theta_{i'_1+t}(z'_1) \theta_{i'_2+t}(z'_2) \right) \left( \sum_{t \in T} \chi(t) \theta_{i'_3+t}(z'_3) \theta_{i'_4+t}(z'_4) \right). $$

We can use Riemann's relations as follows. Let $z_i, z'_i \in V$ for $i = 1, \dots, 4$ be in Riemann position. Assume that we know the affine points $\tilde{P}_i = (\theta_j(z_i))_{j \in K_2(\mathcal{L})}$ for $i = 2, 3, 4$, and $\tilde{P}'_i = (\theta_j(z'_i))_{j \in K_2(\mathcal{L})}$ for $i = 1, \dots, 4$. We can recover $\tilde{P}_1 = (\theta_j(z_1))_{j \in K_2(\mathcal{L})}$, i.e. the affine theta coordinates of $z_1$, by first computing the projective theta coordinates of $P_1$ using the addition on $A$, taking an arbitrary affine lift $\tilde{P}_1$, and computing the projective factor $\lambda_1$ such that $\lambda_1 * \tilde{P}_1, \tilde{P}_2, \dots$ satisfy Riemann's relations (so we only need to use one such relation).

Of course in practice, the arithmetic on $A$ itself is usually derived from Riemann's relations. We just present a few examples and we refer to [LR16] for more details. In particular, when $n = 2$ we need to assume that the even theta null points are non-zero, which means by a result of Koizumi-Mumford-Kempf that the line bundle $\mathcal{L}$ is projectively normal.

**Example 3.4.** Let $r$ be an integer. Given the affine theta coordinates of $0, z_1, z_2, \dots, z_r \in V$ $\tilde{0}_A = (\theta_u(0))_{u \in K_2(\mathcal{L})}$, $\tilde{P}_i = (\theta_u(z_i))_{u \in K_2(\mathcal{L})}$ and also of each $z_i + z_j, i \neq j$, $\tilde{P}_{ij} = (\theta_u(z_i + z_j))_{u \in K_2(\mathcal{L})}$,
we can recover the affine theta coordinates of $m_1z_1 + m_2z_2 + \cdots + m_rz_r$ using Riemann relations. We denote the resulting affine lift by $\text{mult\_add}(m_1, \dots, m_r, \tilde{P}_i, \tilde{P}_{ij}, \tilde{0}_A)$.

As a particular case, we can compute the affine theta coordinates of $\ell z_1 + z_2$ given the affine theta coordinates of 0, $z_1$, $z_2$ and $z_1 - z_2$ (via an easy change of variable), and so of $\ell z_1$ given the affine theta coordinates of 0 and $z_1$. We denote these by $\text{diff\_mult}(\ell, \tilde{P}_1, \tilde{P}_2, \tilde{P}_1 - \tilde{P}_2, \tilde{0}_A)$ and $\text{mult}(\ell, \tilde{P}_1, \tilde{0}_A)$ respectively. These can be computed in $\mathcal{O}(\log \ell)$ field operations using a double and add algorithm.

Another particular case is the computation of the affine theta coordinates of $z_1 + z_2 + z_3$ given that $z_1, z_2, z_3, z_1+z_2, z_1+z_3, z_2+z_3$. With the notations above, we call this **threeway_add**($\tilde{P}_1, \tilde{P}_2, \tilde{P}_3, \tilde{P}_{23}, \tilde{P}_{13}, \tilde{P}_{12}, \tilde{0}_A$). Then conversely, **mult\_add** can be constructed from **threeway\_add** and **diff\_mult**.

Finally, recall that $\theta_i(z_P) = \theta_{-i}(z_P)$, so we define $(-\tilde{P})_i = \tilde{P}_{-i}$.

We want to compute the action of suitable affine lifts given by $z_P \in V$ of the points of $\ell$-torsion $P \in A[\ell]$. Let $\sigma : \Lambda = \Lambda_1 \oplus \Lambda_2$ be a symplectic decomposition. Then the lattice $\Lambda'' = \ell\Lambda_1 \oplus \frac{1}{\ell}\Lambda_2$ is isotropic for $E_\mathcal{L}$ hence, by Lemma 2.3, we get a group section $s_{\Lambda''} : \Lambda'' \to \mathfrak{G}(\mathcal{L})$. We will compute the action of elements of $s_{\Lambda''}(\Lambda''_2)$ on the theta basis of level $n$, $(\theta_i^{\Theta_{\mathcal{L}}})_{i \in K_2(\mathcal{L})}$. Since the $\theta_i^{\Theta_{\mathcal{L}}}$ are invariants by $s_{\Lambda''}(\Lambda)$, the action of $\lambda'' \in \Lambda''_2$ only depends on its class modulo $\Lambda_2$, so only depends on the $\ell$-torsion point $P \in \Lambda''_2/\Lambda_2 \simeq K_2(\mathcal{L}^\ell)[\ell]$. In the following, we denote by $\bar{s}_{\Lambda''} : K_2(\mathcal{L}^\ell)[\ell] \to \text{Aut}(\Gamma(A, \mathcal{L}))$ this action. A similar method will apply for the action of (the lifts of) the points in $K_1(\mathcal{L}^\ell)[\ell]$, for instance using Example 2.13.

By Equation (2), the action by $\bar{s}_{\Lambda''}(P)$ for $P \in K_2(\mathcal{L}^\ell)[\ell]$ is given by the translation by $\ell$-torsion points, corrected by some scalar factor, hence it is natural to use Riemann relations to compute it. In fact, Riemann relations are compatible with these corrective factors:

**Lemma 3.5.** Assume that $z_1, z_2, z_3, z_4; z'_1, z'_2, z'_3, z'_4$ in $V$ are in Riemann position, and moreover that $P_1, P_2, P_3, P_4; P'_1, P'_2, P'_3, P'_4$ in $K_2(\mathcal{L}^\ell)[\ell]$ are in Riemann position. Then the points $\bar{s}_{\Lambda''}(P_i) \cdot \theta_j^{\Theta_{\mathcal{L}}}(z_i)$ satisfy Riemann's relations.

*Proof.* If $z_1, z_2, z_3, z_4; z'_1, z'_2, z'_3, z'_4$ are in Riemann position, and $g_1 = [a_1, v_1], g_2 = [a_2, v_2], \dots$ in $\mathfrak{G}(\mathcal{L})$ too (by which we mean the $v_i$ are in Riemann position and $\prod a_i = \prod a'_i$), then since the $(\theta_j^{\Theta_{\mathcal{L}}}(z_i))_{j \in K_2(\mathcal{L})}$ satisfy Riemann relations by Theorem 3.3, we check by an easy (but a bit lengthy) computation that the $(g_i \cdot \theta_j^{\Theta_{\mathcal{L}}}(z_i))_{j \in K_2(\mathcal{L})}$ also satisfy Riemann relations. We apply this to $g_i = s_{\Lambda''}(z_{P_i}), g'_i = s_{\Lambda''}(z_{P'_i})$, where $z_{P_i}, z_{P'_i} \in V$ are such that $z_{P_i} = P_i \bmod \Lambda_2$ and $z_{P'_i} = P'_i \bmod \Lambda_2$. $\square$

This leads us to the following definition:

**Definition 3.6.** If $K$ be a subgroup of $K(\mathcal{L}^\ell)$ isotropic for the Weil pairing, We say that $\tilde{K} = \{\tilde{P}\}_{P \in K}$ is an excellent lift of $K$ if the points in $\tilde{K}$ satisfy all Riemann relations from Theorem 3.3 that involve only points in $\tilde{K}$.

We specialize what this definition means for a point and its multiples computed by the help of Riemann equations.

**Definition 3.7.** Let $P$ be a point of $\ell$-torsion with $\ell$ odd and prime to $n$. Write $\ell = 2\ell' + 1$. We say that an affine lift $\tilde{P}$ is an excellent point of $\ell$-torsion if $\text{mult}(\ell' + 1, \tilde{P}, \tilde{0}_A) = -\text{mult}(\ell', \tilde{P}, \tilde{0}_A)$.

It is easy to check that if $\tilde{P}$ is an excellent point of $\ell$-torsion, then $\mu * \tilde{P}$ too if and only if $\mu^\ell = 1$. It is clear moreover, since $\text{mult}$ is computed with Riemann equations, that if $\tilde{K}$ is an excellent lift of $K$, all $\tilde{P} \in \tilde{K}$ are excellent points of $\ell$-torsion. Furthermore, given $\tilde{K}$, if $P_1, \dots, P_g$ is a basis of $K$, we only need to be given $\tilde{P}_i$ and $\tilde{P}_{ij}$, the lifts above $P_i$ and $P_i + P_j$ respectively to recover the others via $\text{mult\_add}$.

In fact, this subset of the Riemann relations involving points of $K$ is enough to construct an excellent lift of $K$, and even recover the section of $K$ in $G(\mathcal{L})$ provided by $\bar{s}_A$". Before stating the theorem, we give word of warning: the section $s_A$" does not extend to the whole of $\Lambda$, for instance changing $\lambda$" by an element of $\Lambda_1$ (modulo $\ell\Lambda_1$) will change $s_A$"($\lambda$"). In particular, changing the symplectic decomposition $\sigma$ of $\Lambda$ will change this $s_A$", even if it does not change the induced symplectic decomposition on $A[\ell]$.
This will be exploited in the following theorem where in order to keep track of the dependence of the sections $s_{\Lambda''}$ and the induced action $\bar{s}_{\Lambda''}$ with respect to the symplectic decomposition $\sigma$, we will denote them respectively by $s_{\Lambda''},\sigma$ and $\bar{s}_{\Lambda''},\sigma$.

**Theorem 3.8.** Let $(A, \mathcal{L}, \Theta_{\mathcal{L}}^\sigma)$ be an abelian variety together with symmetric theta structure of level even defined by a symplectic decomposition $\sigma$. Let $K = K_2(\mathcal{L}^\ell)[\ell]$, and let $P_1, \dots, P_g$ be a basis of $K$. Fix once and for all an affine lift $\tilde{0}_A$ of $0_A$. Choose $\tilde{P}_i, \tilde{P}_{ij}$ excellent lifts of $P_i, P_i + P_j$ (for $i \neq j$) respectively. We can then use mult_add to compute an affine lift $\tilde{P}$ above any point $P$ in $K$. Then $\tilde{K} = \{\tilde{P}\}_{P \in K}$ is an excellent lift of $K$. Furthermore, up to changing the symplectic decomposition $\sigma$ of $\Lambda$ (more precisely up to changing $\Lambda_2$ only), for all $P \in K$, $\tilde{P}$ is exactly $\bar{s}_{\Lambda''},\sigma(P).\tilde{0}_A$.

*Proof.* A slightly less refined version is proved in [LR15, Th. 3.4.] using the functional equation of theta functions. Using the theory from Section 2, we can give a self contained proof.

First given an excellent lift $\tilde{K}$, then multiplying every element of $\tilde{K}$ by a projective factor $\mu_0$ still yields an excellent lift, so we may renormalise things such that $\tilde{0}_A = (\theta_i^{\Theta_{\mathcal{L}}^\sigma}(0))_{i \in K_2(\mathcal{L})}$. Of course $\tilde{K} = \{\bar{s}_{\Lambda''},\sigma(P).\tilde{0}_A\}_{P \in K}$ is an excellent lift of $K$ by Lemma 3.5 applied to the elements $0, 0, 0, 0; 0, 0, 0, 0 \in V$ in Riemann position.

Conversely, we construct $\tilde{K}$ as in the theorem and for all $P \in K$ and $\sigma$ a decomposition of $\Lambda$ we let $\tilde{P}^\sigma = \bar{s}_{\Lambda''},\sigma(P)$. Then we have $\tilde{P} = \mu_P * \tilde{P}^\sigma$, for $\mu_P$ a $\ell$-th-root of unity. It is enough to prove that we can always change the symplectic decomposition $\sigma$ of $\Lambda$ to $\sigma'$ so that $\tilde{P}_i^\sigma = \mu_i * \tilde{P}_i^{\sigma'}$ and $\tilde{P}_{ij}^\sigma = \mu_{ij} * \tilde{P}_{ij}^{\sigma'}$ where $\mu_i$ and $\mu_{ij}$ are arbitrary $\ell$-th-roots of unity. We can then choose $\mu_i, \mu_{ij}$ such that, after this change of decomposition, we have $\tilde{P}_i = \tilde{P}_i^{\sigma'}, \tilde{P}_{ij} = \tilde{P}_{ij}^{\sigma'}$, hence $\tilde{P} = \tilde{P}^{\sigma'}$ for all $P \in K$.

First note that by Remark 2.1, as the level of $\Theta_{\mathcal{L}}$ is even, changing the symplectic decomposition do not change the line bundle $\mathcal{L}$ associated to this decomposition. Now given $(e_1, \dots, e_g, f_1, \dots, f_g)$ a symplectic basis of $\Lambda$ with respect to $\sigma$, and fixing $i \in \{1, \dots, g\}$, we change the decomposition such that the new basis if given by $f'_i = f_i + 2k_i n \ell e_i$ (the other ones unchanged) for $k_i \in \{0, \dots, \ell-1\}$. We let $\sigma'$ the new symplectic decomposition. The new symplectic basis still gives the same symplectic decomposition of $A[2n]$, hence we have $\theta_i^{\Theta_{\mathcal{L}}^\sigma} = \theta_i^{\Theta_{\mathcal{L}}^{\sigma'}}$ for all $i \in K_2(\mathcal{L})$ by Remark 2.7. Using the definition of the sections $s_{\Lambda''},\sigma$ and $s_{\Lambda''},\sigma'$ of Lemma 2.3, we compute $s_{\Lambda''},\sigma'(\frac{f_i}{\ell}) = e^{-2\pi i e_{\mathcal{L}}(\frac{f_i}{\ell}, k_i n e_i)} s_{\Lambda''},\sigma(\frac{f_i}{\ell}) s_{\Lambda''},\sigma(2k_i n e_i)$. Since $n$ is prime to $\ell$ and $s_{\Lambda''},\sigma(2k_i n e_i)$ acts trivially on $\tilde{0}_A$, we have $s_{\Lambda''},\sigma'(\frac{f_i}{\ell}) \cdot \tilde{0}_A = \zeta^{k_i} * s_{\Lambda''},\sigma(\frac{f_i}{\ell}) \cdot \tilde{0}_A$ for $\zeta = e^{2\pi i z/\ell}$ a primary $\ell$-th root of unity. In other words, by choosing $k_i \neq 0$ and $k_j = 0$ for $j \neq i$, we can adjust $\tilde{P}_i^{\sigma'}$ without touching the others (except the $\tilde{P}_{ij}^{\sigma'}$, $j \neq i$). Likewise, fixing $i \neq j$, taking a new decomposition such that $f'_i = f_i + 2k_{ij} n \ell e_j$, $f'_j = f_j + 2k_{ij} n \ell e_i$ will change only $\tilde{P}_{ij}^{\sigma'}$ by $\zeta^{2k_{ij}}$, hence we may change it by an arbitrary $\ell$-th root of unity without affecting any others. $\square$

**Remark 3.9.** We give an algebraic interpretation of our choice of affine lifts, which will be useful for Section 4.1. Let $\Lambda' = \ell\Lambda_1 \oplus \Lambda_2$, this lattice defines an abelian variety $A' = V/\Lambda'$, and the projection modulo $\Lambda \supset \Lambda'$ gives an isogeny $f: A' \to A$. The contragredient isogeny $\tilde{f}: A \to A'$ is given analytically by $z \mapsto \ell z$, its kernel is $K = K_2(\mathcal{L}^\ell)[\ell] \simeq \frac{1}{\ell}\Lambda_2/\Lambda$. We have $(\Lambda')^\perp = \Lambda_1 \oplus \frac{1}{\ell}\Lambda_2$, so if $\mathcal{L}' = f^*\mathcal{L}$, our lattice $\Lambda'' = \ell\Lambda_1 \oplus \frac{1}{\ell}\Lambda_2$ is exactly equal to $\Lambda_1' \oplus \Lambda'(\mathcal{L}')_2$.

Now $\frac{1}{\ell}\Lambda_2/\Lambda_2 \simeq K_2(\mathcal{L}')$ can be interpreted as a symplectic complement to the kernel $K' \simeq \Lambda_1/\ell\Lambda_1 = \tilde{f}(A[\ell]) \subset A'[\ell]$ of $f$. In other words: $\frac{1}{\ell}\Lambda_2$ modulo $\Lambda$ determines the kernel of $\tilde{f}$ but, for our action, we need to look at it modulo $\Lambda'$ where it further determines a symplectic complement of $Ker f$.

If $K$ is an isotropic subgroup of $A[\ell]$ and we fix an excellent lift $\tilde{K}$ of $K$, we may extend the definition by saying that $x + \tilde{K} = \{x + \tilde{P} \mid P \in K\}$ is an excellent lift of $x$ with respect to $\tilde{K}$ and $\tilde{x}$ if these points respect all Riemann relations involving only points of $\tilde{K}$ and of $x + \tilde{K}$.

**Definition 3.10.** With the notations of Definition 3.7, let $\tilde{P}$ be an excellent lift of a $\ell$-torsion point $P \in A[\ell]$. Let $x \in A$ and fix an affine lift $\tilde{x}$. We say that $x + \tilde{P}$ is an excellent lift with respect to $\tilde{P}$ and $\tilde{x}$ if the affine point $x + \ell P$ computed via `diff_multadd` is equal to $\tilde{x}$.
If $\widetilde{x+P}$ is an excellent lift of $x+P$, then the other ones are given by $\mu * x + P$ with $\mu^\ell = 1$. By the following Theorem, we may construct an excellent lift $\widetilde{x+K}$ of $x$ with respect to $\tilde{K}$ by first constructing excellent lifts $\widetilde{x+P_i}$ for $P_i$ a basis of $K$, and then obtaining all other points by multiway additions.

**Theorem 3.11.** With the notations of Theorem 3.8, fix an excellent lift $\tilde{K}$ of $K$. Let $x$ be a point in $A$ which is not in $A[\ell]$, and $z \in V$ be such that $x = z \bmod \Lambda$. Fix an affine lift $\tilde{x}$ of $x$, fix excellent lifts $\widetilde{x+P_i}$ for $(P_i)_{i=1,...,g}$ a basis of $K$, and compute the other affine lifts $\widetilde{x+P}$ for $P \in K$ via mult\_add.

Then we may always change $z$ by another representative modulo $\Lambda$ (more precisely by an element $z+\lambda$ with $\lambda \in \Lambda_1$), such that there exists a constant $\mu$ that satisfies $\widetilde{x+P} = \mu * (P \cdot (\theta_i^{\Theta_{\mathcal{L}}^\sigma}(z))_{i \in K_2(\mathcal{L})})$ for all $P \in K$. In other words, we recover (up to the constant $\mu$ that only depends on the choice of $\tilde{x}$) exactly the action of $K$ on $(\theta_i^{\Theta_{\mathcal{L}}^\sigma}(z))$.

*Proof.* First if $\tilde{x} = (\theta_i^{\Theta_{\mathcal{L}}^\sigma}(z))_{i \in K_2(\mathcal{L})}$, and $\widetilde{x+P} = P \cdot \tilde{x}$ for $P \in K$, then the points $\widetilde{x+P}$ form an excellent lift of $x$ with respect to $\tilde{x}$ and $\tilde{K}$ by Lemma 3.5 applied to the elements $z, z, 0, 0; 0, 0, z, z \in V$ in Riemann position.

As in the proof of Theorem 3.8, in general we have for $i = 1, ..., g$, $\widetilde{x+P_i} = \mu_i * (P_i \cdot \theta_j^{\Theta_{\mathcal{L}}^\sigma}(z))_{j \in K_2(\mathcal{L})}$ for $\mu_i$ a $\ell$-th-root of unity. So it is enough to show that we can find $\lambda \in \Lambda$ such that for all $i = 1, ..., g$, $(P_i \cdot \theta_j^{\Theta_{\mathcal{L}}^\sigma}(z))_{j \in K_2(\mathcal{L})} = \mu \mu_i^{-1} * (P_i \cdot \theta_j^{\Theta_{\mathcal{L}}^\sigma}(z+\lambda))_{j \in K_2(\mathcal{L})}$ where $\mu$ is a constant independent of $i$.

For this, denote by $\pi: V \to A$ the canonical projection. The pairing $e_{\mathcal{L}}$ being perfect, we know that for $i = 1, ..., g$, there exists $\lambda_i \in \Lambda_1$ such that $e_{\mathcal{L}}(\pi(\lambda_i), P_i) = \mu_i^{-1}$, and $e_{\mathcal{L}}(\pi(\lambda_i), P_j) = 1$ for $j \neq i$. Set $\lambda = \sum_{i=1}^g \lambda_i$ and $z' = z + \lambda$. It is clear that $z' = x \bmod \Lambda$. Moreover, using Equation (3), we compute for $i = 1, ..., g$ and $j \in K_2(\mathcal{L})$:

$$ (6) \qquad \bar{s}_{\Lambda''}(\pi(-\lambda)) (\bar{s}_{\Lambda''}(P_i) \cdot \theta_j^{\Theta_{\mathcal{L}}^{\sigma}})(z) = a_{\mathcal{L}}(z+\lambda, \lambda) (\bar{s}_{\Lambda''}(P_i) \cdot \theta_j^{\Theta_{\mathcal{L}}^{\sigma}})(z'). $$

Since we have $\bar{s}_{\Lambda''}(\pi(-\lambda))\bar{s}_{\Lambda''}(P_i) = e_{\mathcal{L}}(\pi(-\lambda), P_i)\bar{s}_{\Lambda''}(P_i)s_{\Lambda''}(\pi(-\lambda)) = \mu_i s_{\Lambda''}(P_i)\bar{s}_{\Lambda''}(\pi(-\lambda))$, and since $\theta_j^{\Theta_{\mathcal{L}}^\sigma}(z)$ is invariant under $\bar{s}_{\Lambda''}(\pi(-\lambda))$, we also have

$$ (7) \qquad \bar{s}_{\Lambda''}(\pi(-\lambda)) (s_{\Lambda''}(P_i) \cdot \theta_j^{\Theta_{\mathcal{L}}^{\sigma}})(z) = \mu_i (\bar{s}_{\Lambda''}(P_i) \cdot \theta_j^{\Theta_{\mathcal{L}}^{\sigma}})(z). $$

From (6) and (7), we get for all $i = 1, ..., g$:

$$ (8) \qquad a_{\mathcal{L}}(z + \lambda, \lambda) \mu_i^{-1} * (P_i \cdot \theta_j^{\Theta_{\mathcal{L}}^{\sigma}}(z'))_{j \in K_2(\mathcal{L})} = (P_i \cdot \theta_j^{\Theta_{\mathcal{L}}^{\sigma}}(z))_{j \in K_2(\mathcal{L})}. $$

Using (6) with $P_i = 0$, we also have $a_{\mathcal{L}}(z + \lambda, \lambda) * (\theta_j^{\Theta_{\mathcal{L}}^{\sigma}}(z'))_{j \in K_2(\mathcal{L})} = (\theta_j^{\Theta_{\mathcal{L}}^{\sigma}}(z))_{j \in K_2(\mathcal{L})}$. On the other hand, multiplying $\tilde{x}$ by a factor $\mu$ changes $\widetilde{x+P}$ by the same factor $\mu$ too. So if we renormalise $\tilde{x}$ such that it corresponds exactly to $(\theta_j^{\Theta_{\mathcal{L}}^{\sigma}}(z'))_{j \in K_2(\mathcal{L})}$, then our updated $\widetilde{x+P_i}$ are exactly equal to $(\bar{s}_{\Lambda''}(P_i) \cdot \theta_j^{\Theta_{\mathcal{L}}^{\sigma}}(z'))_{j \in K_2(\mathcal{L})}$, no constants involved. $\square$

**Remark 3.12.** If the field of definition is not algebraically closed, if $P$ is a point of $\ell$-torsion, taking an excellent lift $\widetilde{P}$ of $P$ involves computing a $\ell$-th root $\mu_P$, which may live in an extension of our base field. In practice we never need $\mu_P$: all our algorithms will be independent of the choices made to compute excellent lifts, hence will only involve the value $\mu_P^\ell$ which is rational. The same holds to compute an excellent lift $\widetilde{x+P}$.

### 4. ASCENDING LEVEL

In this section, our goal is twofold:

(1) compute the theta functions of level $n\ell$, i.e. the theta functions of $G(\mathcal{L}^\ell)$

(2) compute the theta functions of level $n$ on $B = A/K$ where $K$ is totally isotropic.

Of course if we know how to do (1), we can apply Mumford's isogeny theorem to get (2).

From Propositions 2.11 and 2.15, we see that we need to

(1) Construct a section $u$ of $\mathcal{L}^\ell$;
**Algorithm 1:** Algorithm to compute an excellent lift of a point.

**input :**

* The theta null point $\tilde{0}_A$ of $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ an abelian variety with a symmetric level $n$ theta structure;

* A point $P$ in $K$ and a lift $\tilde{x}$ of a point $x$ in $A$

**output:** Excellent lifts $\tilde{P}$ of $P$ and $\tilde{x} + \tilde{P}$ of $x + P$ with respect to $\tilde{P}$

1. Fix $\tilde{P}_1$ and $\tilde{x} + \tilde{P}_1$ arbitrary lifts of $P$ and $x + P$;

2. Write $\ell = 2\ell' + 1$ and determine $\lambda$ such that $\mathrm{mult}(\ell' + 1, \lambda * \tilde{P}_1, \tilde{0}_A) = -\mathrm{mult}(\ell', \lambda * \tilde{P}_1, \tilde{0}_A)$;

3. Set $\tilde{P} = \lambda * \tilde{P}_1$;

4. Determine $\mu$ such that $\mathrm{diff\_mult}(\ell, \mu * \tilde{x} + \tilde{P}_1, \tilde{P}, \tilde{x}, \tilde{0}_A) = \tilde{x}$;

5. Set $\tilde{x} + \tilde{P} = \mu * \tilde{x} + \tilde{P}_1$;

6. return $\tilde{P}, \tilde{x} + \tilde{P}$;

**Algorithm 2:** Algorithm to compute an excellent lift of the kernel

**input :**

* The theta null point $\tilde{0}_A$ of $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ an abelian variety with a symmetric level $n$ theta structure;

* A kernel $K$ and a lift $\tilde{x}$ of a point $x$ in $A$.

**output:** Excellent lifts $\tilde{K}$ of $K$ and $\tilde{x} + \tilde{K}$ of $x + K$ with respect to $\tilde{K}$

1. Fix a basis $(P_1, \dots, P_g)$ of $K$;

2. Compute excellent lifts $\tilde{P}_i, \tilde{P}_i + \tilde{P}_j, \tilde{x} + \tilde{P}_i$ for $i \neq j \in \{1, \dots, g\}$ using Algorithm 1;

3. Use $\mathrm{mult\_add}$ to compute the other lifts $\tilde{K}$ and $\tilde{x} + \tilde{K}$;

(2) Explicit the action of $G(\mathcal{L}^\ell)$ on this $u$.

Since we will construct $u$ from theta functions of level $n$, where the action of $G(\mathcal{L})$ is explicit, we only need to understand the action of (the sections) of $K_1(\mathcal{L}^\ell)[\ell]$ and $K_2(\mathcal{L}^\ell)[\ell]$. These are given by (symmetric) elements of order $\ell$ in $G(\mathcal{L}^\ell)$. If $g \in G(\mathcal{L}^\ell)$ is such an element and is represented by $[\alpha, z_P] \in \mathfrak{G}(\mathcal{L}^\ell)$, the action on $u$ from Equation (2) shows that we need to be able to compute the translation $u(z - z_P)$. Here $z_P$ will be an affine point of $\ell$-torsion, i.e. a point in $V$ such that $P = z_P$ mod $\Lambda$ is a point of $\ell$-torsion. The multiplicative factor $\alpha e^{\pi \ell H(z-z_P, z_P)}$ can be seen as a corrective factor such that $[\alpha, z_P]$ is of order $\ell$ in $G(\mathcal{L}^\ell)$. In fact, if we use the classical factor of automorphy instead, this action is exactly the action by translation whenever $z_P \in \frac{1}{\ell} \mathbb{Z}^g$.

4.1. **Ascending level along an isogeny.** As a warm-up, given an isogeny $f: A' = V/\Lambda' \to A = V/\Lambda$ such that its kernel $K'$ is a maximal isotropic subgroup of $A'[\ell]$, we explain how to compute theta coordinates on $A'$ from the knowledge of theta coordinates on $A$. This was already explained in [LR12], but Proposition 2.11 allows us to give a shorter proof.

We suppose that $A$ is endowed with a polarisation given by a Riemann form $H_A$ of type $n$ and we choose a symplectic decomposition $\sigma: V = V_1 \oplus V_2$ with respect to $H_A$ such that $\Lambda$ is compatible with $\sigma$ following Definition 2.2. We have seen in Section 2.1 that $\sigma$ defines a canonical line bundle $\mathcal{L}$ on $A$ as well as a symmetric theta structure $\Theta_{\mathcal{L}}^{\sigma}$ by Proposition 2.5. Let $F$ be the analytic representation of $f$ then $\sigma': V = F^{-1}(V_1) \oplus F^{-1}(V_2)$ is a symplectic decomposition of $V$ for $F^*(H_A)$ and $\Lambda'$ is compatible with $\sigma'$. Thus the decomposition $\sigma'$ defines a line bundle $\mathcal{L}'$ on $A'$ such that $\mathcal{L}' = f^*(\mathcal{L})$ and a symmetric theta structure $\Theta_{\mathcal{L}'}^{\sigma'}$.

In order to compute the canonical basis defined by $\Theta_{\mathcal{L}'}^{\sigma'}$, we need to obtain a section of $\mathcal{L}'$ and to explain how $G(\mathcal{L}')$ acts on it. We consider $u$ a section of $\mathcal{L}$, and $u' = f^*u = u \circ f$. By the compatibility of the action (see Equation (4)), if $g' = [\alpha', w'] \in G(\mathcal{L}')$ is such that $f(w') \in K(\mathcal{L})$, then the action of
$g'$ on $u'$ is given by the action of $F(g')$ on $u$. For instance if $u = \theta_0 \in \Gamma(A, \mathcal{L})$, then for $i \in A'_1[n]$ acts trivially on $i \cdot u' = u'$ while the action of $i \in A'_2[n]$ is given by $i \cdot u' = F^*\theta_{f(i)}$.

It remains to explain how $A'[\ell]$ acts on $u'$. Take a decomposition $A'[\ell] = A'_1[\ell] \oplus A'_2[\ell]$ with $K' = \text{Ker } f = A'_1[\ell]$, then $A'_1[\ell]$ acts trivially on $u'$ since $u' = f^*(u)$. Thus we only need to compute the action of $P \in A'_2[\ell]$. Changing if necessary the symplectic decomposition $\sigma$ of $\Lambda$, we may assume that $\Lambda' = \ell\Lambda_1 \oplus \Lambda_2$, $F = \text{Id}$. Then this action is exactly the action of the points in $\frac{1}{\ell}\Lambda_2/\Lambda_2$ that we computed in Section 3 (see Remark 3.9).

Note that we may always change the symplectic decomposition of $\Lambda$ and $\Lambda'$ in order to make them compatible, without changing the theta structure of level $n$ on $A$ (resp. $\ell n$ on $A'$) if the following algebraic conditions are satisfied (see Remark 2.7): let $A'[2\ell n] = A'_1[2\ell n] \oplus A'_2[2\ell n]$ be the symplectic decomposition inducing the theta structure of level $\ell n$ on $A'$. Then we require that $\text{Ker } f = 2nA'_1[2\ell n]$, and that the decomposition $A[2n] = f(A'_1[2\ell n]) \oplus f(\ell A'_2[2\ell n])$ induces the theta structure of level $n$ on $A$.

When $\ell$ is prime to $n$, this amount simply to saying that the decomposition of $A'[2n]$ is sent to the decomposition of $A[2n]$ via $f$. In particular, $A'_i[n]$ is fixed, $A'_1[\ell] = K' = \text{Ker } f$ is fixed, so the only choice left is on the symplectic complement $A'_2[\ell]$ of $K'$.

From the proofs of Theorems 3.8 and 3.11 and Remark 3.9, we immediately get:

**Theorem 4.1.** Let $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ be an abelian variety together with a level $n$ symmetric theta structure. Let $K$ be a maximal isotropic kernel of $A[\ell]$, $\ell$ prime to $n$, let $A' = A/K$, and let $f: A' \to A$ be the contragredient isogeny. Let $\mathcal{L}' = f^*\mathcal{L}$. Let $x \in A$ and fix a lift $\tilde{x}$. Fix an excellent lift $\tilde{K}$ of $K$, and $x + \tilde{K}$ of $x$, as in Theorems 3.8 and 3.11. Then

(1) There exists a symmetric theta structure $\Theta_{\mathcal{L}'}$ on $(A', \mathcal{L}')$ such that for $i \in K_2(\mathcal{L}')$, if $i = i_1 + i_2$ with $i_1 \in K_2(\mathcal{L}')[n]$ and $i_2 \in K_2(\mathcal{L}')[\ell]$, $\theta_i^{\Theta_{\mathcal{L}'}}(0) = \theta_{f(i)}^{\Theta_{\mathcal{L}'}}(f(\tilde{i}_2))$. Furthermore all $\ell^{g(g+1)/2}$ theta constants given by such (compatible) theta structures arise from a choice of an excellent lift of $K$.

(2) If $x'$ is the point such that $\theta_{i_1+i_2}^{\Theta_{\mathcal{L}'}}(x') = \theta_{i_1}^{\Theta_{\mathcal{L}'}}(x+f(i_2))$, then $x'$ is a preimage of $x$ by $f$, and all $\ell^g$-preimages of $x$ arise from a different choice of excellent lift $x + \tilde{K}$.

**4.2. Ascending level on the same variety.** We assume we are given an abelian variety $(A = V/\Lambda, \mathcal{L}, \Theta_{\mathcal{L}})$ with a symmetric theta structure of even level $n$ defined by a symplectic decomposition $\sigma: \Lambda = \Lambda \oplus \Lambda_2$. We want to construct the symmetric theta structure of level $\ell n$ on $(A, \mathcal{L}^\ell)$ provided by $\sigma$ following Proposition 2.5. For simplicity we assume that $\ell$ is prime to $n$. We will apply the tools of Section 2.

Let $a_i \in \mathbb{N}$ for $i = 1, \dots, r$ be such that $\ell = \sum_{i=1}^r a_i^2$. Let $u_i \in \Gamma(A, \mathcal{L})$ for $i = 1, \dots, r$, then, as $\mathcal{L}$ is symmetric, $u_i \circ [a_i]$ (where $[a_i] : A \to A$ is the isogeny defined on points by $P \mapsto a_i P$) is a section of $\mathcal{L}^{a_i^2}$, hence $u = \prod u_i$ is a section of $\mathcal{L} \sum a_i^2 = \mathcal{L}^\ell$. We want to explicit the action of $G(\mathcal{L}^\ell)$ on $u$, we can then apply Proposition 2.11 to recover the theta basis of level $\ell n$ on $\mathcal{L}^\ell$. There is a morphism $E_\ell: \mathfrak{G}(\mathcal{L}) \to \mathfrak{G}(\mathcal{L}^\ell)$, $[\alpha, w] \mapsto [\alpha^\ell, w]$. As $\Lambda$ is isotropic for $E_\ell$ and $E_\ell$ and is compatible with $\sigma$, Lemma 2.3, gives sections $s_{\Lambda, \mathcal{L}}: \Lambda \to \mathfrak{G}(\mathcal{L})$ and $s_{\Lambda, \mathcal{L}^\ell}: \Lambda \to \mathfrak{G}(\mathcal{L}^\ell)$. One can verify that $E_\ell$ is compatible with $s_{\Lambda, \mathcal{L}}$ and $s_{\Lambda, \mathcal{L}^\ell}$ in the following way: $E_\ell(s_{\Lambda, \mathcal{L}}(\lambda)) = s_{\Lambda, \mathcal{L}^\ell}(\lambda)$ for all $\lambda \in \Lambda$.

We check that the action of $\mathfrak{G}(\mathcal{L}^\ell)$ is compatible with products of sections, and combining with the compatibility of the action with isogenies (see Section 2.4), we get:

**Lemma 4.2.** Let $\Lambda' = \frac{1}{\ell}\Lambda_1 \oplus \Lambda_2$, or $\Lambda' = \Lambda_1 \oplus \frac{1}{\ell}\Lambda_2$. For $m \in \mathbb{N}^*$, we denote by $s_{\Lambda', \mathcal{L}^m}: \Lambda' \to \mathfrak{G}(\mathcal{L}^m)$, the set section defined by $s_{\Lambda', \mathcal{L}^m}(\lambda) = [a_{\mathcal{L}^m}(0, \lambda), \lambda]$. For $\lambda \in \Lambda'$, we have:

$$s_{\Lambda', \mathcal{L}^\ell}(\lambda) \cdot \prod u_i(a_i z) = \prod s_{\Lambda', \mathcal{L}^a_i}(\lambda) \cdot u_i(a_i z) = \prod a_i^* (s_{\Lambda', \mathcal{L}}(a_i \lambda) \cdot u_i(z)).$$

*Proof.* We use compatibility of the action with the product, followed by the compatibility of the action by the isogeny $[a_i]$ (see Equation 4), whose analytic representation is exactly $z \mapsto a_i z$.

One caveat here is that while $s_{\Lambda', \mathcal{L}^\ell}$ defines a section of $\Lambda'$ into $G(\mathcal{L}^\ell)$ which does not even depends on the symplectic decomposition of $A[\ell]$ (because $\ell$ is odd), $s_{\Lambda', \mathcal{L}}$ is only a group section on $\Lambda$, and
the value of $s_{\Lambda', \mathcal{L}}(\lambda)$ depends crucially on the full symplectic decomposition of $\Lambda$. Indeed we saw in Theorem 3.8 that we had several possible choices.

But when taking the product, these choices cancel out. We can verify this: if $s_{\Lambda', \mathcal{L}}(\lambda) = [\alpha, w]$, another choice amount to multiplying the first coordinate $\alpha$ by a $\ell$-th root of unity $\zeta$, and translating the second coordinate by an element of $\Lambda$. Then we can check that this changes $s_{\Lambda', \mathcal{L}}(a_i\lambda)$ by a factor $\zeta^{a_i^2}$ on its first coordinate, hence the final product of the actions is changed by $\zeta \sum a_i^2 = \zeta^\ell = 1$. $\square$

Let $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ be an abelian variety together with a level $n$ symmetric theta structure. Then Lemma 4.2 gives us a way to compute the actions of $s_{\Lambda', \mathcal{L}}(\ell)$. Namely, if $P \in A[\ell]$ is such that $P = \lambda$ mod $\Lambda$ for $\lambda \in \Lambda'$ and $z \in V$ is such that $x = z$ mod $\Lambda$ for $x \in A$, inducing excellent lifts $\widetilde{P}$ and $x + \widetilde{P}$, we get that $a_i^* s_{\Lambda', \mathcal{L}}(a_i \lambda) \cdot \theta_j^{\Theta_{\mathcal{L}}} = a_i^*(x + \widetilde{a_i P})_j = (a_i x + \widetilde{a_i P})_j = (a_i(x + \widetilde{P}))_j$. Here one needs to be careful that we are working with affine theta coordinates, so the point $a_i(x + \widetilde{P}) = a_i(x + \widetilde{P})$ has to be computed as an affine point, using Riemann relations (or as usual using the projective arithmetic on $A$ and determining the correct projective factor through Riemann relations).

Applying Proposition 2.11 to $u_i = \theta_0^{\Theta_{\mathcal{L}}}(z)$ (we let to the reader the obvious generalisation to $u_i = \theta_{j_i}^{\Theta_{\mathcal{L}}}$), we get

**Theorem 4.3.** Let $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ be an abelian variety together with a level $n$ symmetric theta structure. Assume that $\ell$ is prime to $n$, and let $A[\ell] = A_1[\ell] \oplus A_2[\ell]$ be a symplectic decomposition. There is a unique symmetric level $\ell n$ theta structure $\Theta_{\mathcal{L}^\ell}$ compatible with $\Theta_{\mathcal{L}}$ following Definition 2.8 and this decomposition. Write $\ell = \sum_{i=1}^r a_i^2$ with $a_i \in \mathbb{N}$. Fix excellent lifts $\widetilde{A_i}[\ell]$ of the maximal isotropic subgroups $A_i[\ell]$. For $x \in A$, fix an affine lift $\tilde{x}$, excellent lifts $x + \widetilde{P}$ with respect to $\tilde{x}$ and $\widetilde{P}$ for $P \in A_1[\ell]$, and then excellent lifts $x + \widetilde{P} + Q$ with respect to $x + \widetilde{P}$ and $\widetilde{Q}$ for $Q \in A_2[\ell]$. Compute $a_i(x + \widetilde{P} + Q)$ using mult.

Let $z \in V$ be such that $x = z$ mod $\Lambda$, and let $\mu$ be such that $\theta_i^{\Theta_{\mathcal{L}}}(z) = \mu \tilde{x}$. We have:

$$ \theta_0^{\Theta_{\mathcal{L}^\ell}}(z) = \mu^\ell \sum_{\widetilde{P} \in \widetilde{A_1}[\ell]} \prod_{i=1}^r (a_i(\widetilde{x+P}))_0, $$

and if $i \in A_2[\ell]$, writing $J = Q + j$ with $Q \in A_2[\ell]$ and $j \in A_2[n]$,

$$ \theta_J^{\Theta_{\mathcal{L}^\ell}}(z) = \mu^\ell \sum_{\widetilde{P} \in \widetilde{A_1}[\ell]} \prod_{i=1}^r (a_i(x + \widetilde{P} + Q))_{a_i j}. $$

*Proof.* The unicity of $\Theta_{\mathcal{L}^\ell}$ comes from Remark 2.7 and the fact that $\ell$ is odd and prime to $n$: for $i=1,2$, the section $s_i^{\Theta_{\mathcal{L}^\ell}}$ (see Definition 2.6) above $A_i[n]$ is given by $E_\ell \circ s_i^{\Theta_{\mathcal{L}}}$, and above $A_i[\ell]$ as the unique symmetric group in $G(\mathcal{L}^\ell)$ (the unicity is because $\ell$ is odd).

By Theorem 3.8, up to changing the lattice decomposition of $\Lambda$ (twice, once for $\Lambda_2$, then for $\Lambda_1$) we can assume that we have correct lifts of $A_1[\ell]$ and $A_2[\ell]$. Let $z \in V$ be such that $x = z$ mod $\Lambda$, by Theorem 3.11, upon changing $z$ first by an element of $\Lambda_1$ then by an element of $\Lambda_2$ we may assume that there exists $\mu$ such that $(\theta_i^{\Theta_{\mathcal{L}}}(z)) = \mu * \tilde{x}$, and $P \cdot (\theta_i^{\Theta_{\mathcal{L}}}(z)) = \mu * (\tilde{x} + \widetilde{P})$ and $Q \cdot P \cdot (\theta_i^{\Theta_{\mathcal{L}}}(z)) = \mu * (\tilde{x} + \widetilde{P} + Q)$. Other analytic lifts are given by $z + \lambda$, for $\lambda \in \Lambda$. If $(\theta_i^{\Theta_{\mathcal{L}}}(z + \lambda)) = \mu * (\theta_i^{\Theta_{\mathcal{L}}}(z))$, then $(\theta_i^{\Theta_{\mathcal{L}^\ell}}(z + \lambda)) = \mu^\ell * (\theta_i^{\Theta_{\mathcal{L}^\ell}}(z))$, hence the LHS is homogeneous of degree $\ell$ with respect to $\mu$. Since $a_i(\mu \tilde{x}) = \mu a_i^2 a_i \tilde{x}$, the RHS is also homogeneous of degree $\ell$ with respect to $\mu$. Hence we may suppose that $\mu = 1$, whence the result follows by Lemma 4.2. $\square$

From the Theorem, we immediately deduce the Algorithm 3 to go up in level. We thus recover the complexity announced in Theorem 1.1, the $O(\log \ell)$ terms come from the need to compute scalar multiplications by the $a_i$.

**Remark 4.4.** The order matter here, if we normalise $x + \widetilde{P} + Q$ with respect to $x + \widetilde{Q}$ and $\widetilde{P}$ instead, we would change its value by a factor $\mu$ such that $\mu^\ell = e_{\mathcal{L}^\ell}(P, Q)$, since $e_{\mathcal{L}^\ell}$ is the commutator pairing on $G(\mathcal{L}^\ell)$. A similar idea was used in [LR10] to compute the pairing of $P$ and $Q$.
**Algorithm 3:** Algorithm to go up from level *n* to level *ℓn*.

**input:**

* The theta null point $\tilde{0}_A$ of $(A = V/\Lambda, \mathcal{L}, \Theta_{\mathcal{L}})$ an abelian variety with a symmetric level *n* theta structure;

* for *ℓ* a positive odd integer, a symplectic decomposition $A[\ell] = A_1[\ell] \oplus A_2[\ell]$ given by the theta coordinates of its basis;

* a decomposition $\ell = \sum_{i=1}^{r} a_i^2$;

* $x \in A$, given by its level *n* theta-coordinates $(\theta_i^{\Theta_{\mathcal{L}}}(x))_{i \in K_2(\mathcal{L})}$;

* $J \in K_2(\mathcal{L}^\ell)$.

**output:** the level $\ell n$ theta coordinate of index *J* of $x \in A$: $\theta_J^{\Theta_{\mathcal{L}^\ell}}(x)$.

1. Using Algorithm 2, compute excellent lifts $\tilde{x}$ and $\tilde{x} + P$ for $P \in A_1[\ell]$;

2. Write $J = Q + j$ for $j \in A_2[n]$ and $Q \in A_2[\ell]$;

3. Choose any affine lift $\tilde{Q}$ of $Q$;

4. Using Algorithm 2 compute excellent lifts $x + \tilde{P} + Q$ with respect to $x + \tilde{P}$ and $\tilde{Q}$ for all $P \in A_1[\ell]$;

5. return $\sum_{\tilde{P} \in A_1[\ell]} \prod_{i=1}^{r} \text{mult}(a_i, x + \tilde{P} + Q, \tilde{0}_A)_{a_{ij}}$;

As a corollary, applying Mumford's isogeny theorem (or using Proposition 2.15 directly) we get:

**Corollary 4.5.** Let $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ a abelian variety together with a symmetric level *n* theta structure. Let *ℓ* be prime to *n* and write *ℓ* = $\sum_{i=1}^r a_i$ for $a_i \in \mathbb{N}$. Let $K \subset A[\ell]$ be a maximal totally isotropic subgroup, and $f: A \to B = A/K$ be the isogeny. Since *ℓ* is odd, there is a unique symmetric level subgroup $\tilde{K}$ of $K$ in $G(\mathcal{L}^\ell)$, which induces via $f$ a descent $\mathcal{M}$ of $\mathcal{L}^\ell$ on $B$. Furthermore, by Proposition 2.15, $\Theta_{\mathcal{L}}$ induces a unique symmetric level *n* theta structure $\Theta_{\mathcal{M}}$ on $B$. Let $x \in A$, fix an affine lift $\tilde{x}$, excellent lifts $\tilde{K}$ of $K$, and $x + \tilde{K}$ of $x$ with respect to $\tilde{x}$ and $\tilde{K}$. Let $z \in V$ be such that $x = z \bmod \Lambda$, and let $\mu$ be such that $\theta_i(z) = \mu(\tilde{x})_i$. Then identifying $K_2(\mathcal{L})$ with $K_2(\mathcal{M})$ via $f$, we have for $j \in K_2(\mathcal{L})$,

$$ (9) \qquad \theta_{f(j)}^{\Theta_{\mathcal{M}}}(f(z)) = \mu^{\ell} \sum_{P \in \tilde{K}} \prod_{i=1}^{r} (a_i(\tilde{x} + P))_{a_{ij}}. $$

**Algorithm 4:** Algorithm to compute a $\ell^g$ isogeny.

**input:**

* The theta null point $\tilde{0}_A$ of $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ an abelian variety with a symmetric level *n* theta structure;

* *ℓ* a positive odd integer and a decomposition *ℓ* = $\sum_{i=1}^{r} a_i^2$;

* $K \subset A[\ell]$ a rank *g* isotropic subgroup of *A* defining an isogeny $f: A \to B$, described by the theta coordinates of a basis;

* $x \in A$, given by its projective level *n* coordinates $(\theta_i^{\Theta_{\mathcal{L}}}(x))_{i \in K_2(\mathcal{L})}$.

**output:** the projective coordinates of $f(x) \in A$: $(\theta_i^{\Theta_{\mathcal{M}}}(f(x))_{i \in K_2(\mathcal{M})})$.

1. Using Algorithm 2, compute excellent lifts $\tilde{x}$ and $\tilde{K}$;

2. for $j \in K_2(\mathcal{M})$ do

3. Let $j_0 \in K_2(\mathcal{L})$ be such that $j = f(j_0)$;

4. Let $\theta_j^{\Theta_{\mathcal{M}}}(f(x)) = \sum_{\tilde{P} \in \tilde{K}} \prod_{i=1}^{r} \text{mult}(a_i, x + \tilde{P}, \tilde{0}_A)_{a_{ij}}$;

5. end

6. return $(\theta_j^{\Theta_{\mathcal{M}}}(f(x)))_{j \in K_2(\mathcal{M})}$;
**Remark 4.6.** From the proof of Lemma 4.2, we don't need to take excellent lifts of $K$ and $x+K$ globally. We just need excellent lifts $\tilde{P}$ and $\tilde{x}+\tilde{P}$ individually for any $P \in K$. Indeed, the different choices cancels out in the product inside Equation (9).

When given a basis $P_1, \dots, P_g$ of $K$, it is actually faster to compute excellent lifts of $P_i$, $P_i+P_j$, $x+P_i$, $x+P_i+P_j$ and compute the rest using differential additions to get a global lift of $K$, rather than normalising each point individually.

However, if we have equations for the kernel $K$, rather than computing $\tilde{x}+\tilde{P}$ for each $P \in K$, we can compute it for a formal point of $K$, and then compute the product $\prod_{i=1}^r (a_i(\tilde{x}+\tilde{P}))_i$ formally modulo the equations. If we have a univariate parametrisation of $K$, the trace across $K$ is then given by a resultant, using the same method as in [LR15].

**Remark 4.7.** We now explain how to relax the assumption that $\ell$ odd is prime to $n$. Fix a symplectic decomposition of $\Lambda$ giving our theta null point of level $n$ on $A$. This induces a canonical symplectic decomposition of $A[\ell n]$. Algebraically, our (symmetric) theta structure of level $n$ (resp. $\ell n$) is completely determined by the corresponding symplectic decomposition of $A[2n]$ (resp. $A[2n\ell]$), and the theta structures are compatible in the sense of Definition 2.8 if $\ell A_i[2\ell n] = A_i[2n]$.

If $\ell$ is odd, we only need to fix a symplectic decomposition of $A[n\ell]$ such that $\ell A_i[\ell n] = A[n]$. If $P$ is a point of $\ell n$-torsion, $\tilde{x}$ an affine point given by level $n$ theta coordinate, we may extend the strategy of Section 3 to compute $s(P) \cdot \tilde{x}$ as follow: $g := s(P)^\ell$ is an element of $G(\mathcal{L})$, whence we know its action on $\tilde{x}$ explicitly. So we may extend the definition of an excellent lift $\tilde{P}$ and $\tilde{x}+\tilde{P}$ by requiring in this case that if $\ell = 2\ell' + 1$, $(\ell' + 1)\tilde{P} = g \cdot \ell'(-\tilde{P})$, and $\tilde{x}+\ell\tilde{P} = g \cdot \tilde{x}$. These define these lifts up to a $\ell$-th root of unity as before.

From Corollary 4.5, we get Algorithm 4 to compute an isogeny between abelian varieties. In practice, an abelian variety together with a symmetric level $n$ theta structure defined over $k$ is determined by its theta null point which is a projective point in $\mathbb{P}_k^{\eta^g-1}$ defined over $k$. The theta null point can be obtained through Thomae like formulas [Cos11] if $A$ is the Jacobian of a curve. In general, theta null points are described using the equations of (a closure of) the moduli space of abelian variety together with level $n$ theta structure as defined in [Mum67].

Note that in order to use the results of this paper, we need $n$ to be even. Moreover, as the ambient space in which $A$ is embedded has dimension $n^g - 1$ and we look for compact representation of the objects for time and memory efficiency, we want $n$ to be as small as possible. So in practise, we use $n = 2$ or $n = 4$. As all the level 2 theta functions are even, they do not provide an embedding of $A$ but rather of its associated Kummer variety $K = A/(\pm 1)$. Although $K$ is not an algebraic group, its set of points still enjoy a pseudo-group law and pairings which makes it useful for computations and some applications in cryptography [LR16; GL09; Gau07], and it is straightforward to adapt our algorithms to this case.

The examples have been computed using the magma library [BCR10]. They also could be done with the Sage reimplementation of AVIsogenies [Som21].

**Example 4.8.** Let $\mathbb{F}$ be the finite field of size 1511, $E$ the elliptic curve $y^2 = x^3 + 1211x + 600$ over $\mathbb{F}$. Let $P$ be the 7-torsion point $(858\eta^2 + 1045\eta + 830 : 386\eta^2 + 1245\eta + 811 : 1)$ in the extension field of degree 3 where $\eta^3 + 2\eta + 1500 = 0$. We compute a level 4 theta null point of $E$ using Thomae's formula (as implemented in [BCR10]): it lives in an extension of degree 6 of $\mathbb{F}$, and convert $P$ to theta coordinates. Let $K$ be the kernel generated by $P$, we check that it is rational over $\mathbb{F}$. We compute an excellent lift $\tilde{K}$ of $K$ by computing an excellent lift $\tilde{P}$ from $P$ and then using differential addition to recover the other multiples. We now apply Corollary 4.5 to the decomposition $7 = 1+1+\cdots+1$, namely

$$ (10) \qquad \theta_j^{E/K}(0) = \sum_{P \in \tilde{K}} \theta_j(\tilde{P})_j^\ell. $$

We get the following level 4 theta null point: $(853\nu^5 + 1372\nu^4 + 424\nu^3 + 743\nu^2 + 430\nu + 865, 440\nu^5 + 9\nu^4 + 663\nu^3 + 128\nu^2 + 170\nu + 280, 1024\nu^5 + 298\nu^4 + 853\nu^3 + 311\nu^2 + 632\nu + 107, 440\nu^5 + 9\nu^4 + 663\nu^3 + 128\nu^2 + 170\nu + 280)$ where $\nu^6 + \nu^4 + 106\nu^3 + 1278\nu^2 + 1032\nu + 11 = 0$.
We now convert back the theta null point of $E/K$ to an equation of $E/K$ (by computing its Legendre invariant), this gives a curve defined over an extension of degree 6 but whose $j$-invariant is $j(E/K) = 491$, hence $E/K$ descends to $\mathbb{F}$ as expected. Comparing with Vélu's formula, we recover the same elliptic curve.

**Example 4.9.** Let $C$ be the hyperelliptic curve of genus 2 given by the equation $y^2 = t^{254}x^6 + t^{223}x^5 + t^{255}x^4 + t^{318}x^3 + t^{668}x^2 + t^{543}x + t^{538}$ defined over the finite field $\mathbb{F}$ with $3^6$ elements where $t^6 + 2t^4 + t^2 + 2t + 2 = 0$. There is a unique rational totally isotropic (for the Weil pairing) subgroup $K$ in $Jac(C)[7]$. We compute (using [BCR10]) the theta null point of $Jac(C)$ and convert two generators $P, Q$ of $K$ into theta coordinates. These points $P$ and $Q$ live in an extension of degree 4 of $\mathbb{F}$. We then normalize them to form excellent affine lifts $\tilde{P}, \tilde{Q}$, along with $\tilde{P} + \tilde{Q}$. From these lifts we can compute an excellent lift $\tilde{K}$ of $K$ using differential additions, and then compute the isogenous theta null point using a trace like in Equation (10). We compute the Rosenhain invariants associated to this theta null point, and recover the isogenous curve: $y^2 = t^{293}x^6 + x^5 + t^{225}x^4 + t^{189}x^3 + t^{87}x^2 + t^{424}x + t^{289}$. We check that these two curves have the same zeta function, hence are indeed isogenous.

## 5. DESCENDING LEVEL

We now want to explain how to do the reverse of Section 4, namely given theta functions for a (symmetric) theta structure of level $\ell n$ on $\mathcal{L}^{\ell}$, compute the theta functions for the unique induced one of level $n$ on $\mathcal{L}$ (recall that we assume $n$ even).

To apply our algorithm of Proposition 2.11, we first need to construct a section $v \in \Gamma(A, \mathcal{L})$, and then explain how the theta group $G(\mathcal{L})$ acts on it. Unfortunately we cannot build an element of $\Gamma(A, \mathcal{L})$ from ones of $\Gamma(A, \mathcal{L}^{\ell})$. However, we can try to build an element of $\Gamma(A, \mathcal{L}^{\ell^2})$ of the form $u = v \circ [\ell]$. In fact if we know how (the lift of $A[\ell]$) acts in $G(\mathcal{L}^{\ell^2})$, we only need any $u \in \Gamma(A, \mathcal{L}^{\ell^2})$, and take the trace $u'$ of $u$ under $A[\ell]$ to get a section of the form $v \circ [\ell]$. More precisely, we can use Proposition 2.15 applied to the isogeny $[\ell]$ to construct the theta functions of level $n$ on $\mathcal{L}$.

But we can use Section 4.2 to go from level $n\ell$ to level $n\ell^2$. In particular, if $\ell = \sum a_i^2$, and $u_i$ are in $\Gamma(A, \mathcal{L}^{\ell})$, then $u = \prod u_i(a_i x) \in \Gamma(A, \mathcal{L}^{\ell^2})$. While we cannot directly apply the results of this section since $\ell$ is not prime to $n\ell$ (but see Remark 4.7), to apply Proposition 2.15 we only need to compute the action of (the lift of) the points in $A[\ell]$ and in $A[n]$ on $u$. In our current case this is actually easier than in Proposition 2.15, since we already have a theta structure of level $\ell n$, we already have the action of these points on the $u_i$, hence (by compatibility with product and isogenies) on $u$.

**Theorem 5.1.** Let $(A = V/\Lambda, \mathcal{L}^{\ell}, \Theta_{\mathcal{L}^{\ell}})$ be an abelian variety with a symmetric theta structure of level $n\ell$, with $n$ even and $\ell$ prime to $n$, and let $\Theta_{\mathcal{L}}$ be the unique structure on $\mathcal{L}$ compatible with $\Theta_{\mathcal{L}^{\ell}}$ (Definition 2.8). Let $A[\ell n] = A_1[\ell n] \oplus A_2[\ell n]$ the corresponding symplectic decomposition. Write $\ell = \sum_{i=1}^r a_i^2$. Let $x \in A$ and fix an arbitrary affine lift $\tilde{x}$; let $z \in V$ be such that $z \mod \Lambda = x$, and let $\mu$ be such that $\theta_i^{\Theta_{\mathcal{L}}}(z) = \mu \tilde{x}_i$.

Then for $j \in A_2[n]$, $\theta_{\ell j}^{\Theta_{\mathcal{L}}}(\ell z) = \mu^{\ell} \sum_{t \in A_2[\ell]} \prod_{i=1}^r (a_i \tilde{x})_{a_i(j+t)}$, where $a_j \tilde{x}$ is computed via mult.

*Proof.* Let $\Lambda' = \frac{1}{\ell}\Lambda$. By Lemma 2.3, there are group sections $s_{\Lambda', \mathcal{L}^{\ell}} : \Lambda' \to \mathfrak{G}(\mathcal{L}^{\ell})$ and $s_{\Lambda, \mathcal{L}} : \Lambda \to \mathfrak{G}(\mathcal{L})$. Consider the group morphism $H_{\ell} : \mathfrak{G}(\mathcal{L}^{\ell}) \to \mathfrak{G}(\mathcal{L})$, $[\alpha, v] \mapsto [\alpha^{\ell}, \ell v]$, then $H_{\ell}$ is compatible with the sections $s_{\Lambda', \mathcal{L}^{\ell}}$ and $s_{\Lambda, \mathcal{L}} : H_{\ell}(s_{\Lambda', \mathcal{L}^{\ell}}(\lambda)) = s_{\Lambda, \mathcal{L}}(\ell\lambda)$. Thus if $\Theta_{\mathcal{L}}$ is compatible with $\Theta_{\mathcal{L}^{\ell}}$, for $i=1,2$, the sections $s_i^{\Theta_{\mathcal{L}}}: A_i[n] \to G(\mathcal{L})$ defining the theta structure $\Theta_{\mathcal{L}}$ are completely determined by $s_i^{\Theta_{\mathcal{L}}}(P) = s_i^{\Theta_{\mathcal{L}^{\ell}}}(P')$ for any point $P' \in A_i[n\ell]$ with $P = \ell P'$. This proves the unicity of $\Theta_{\mathcal{L}}$.

As in Theorem 4.3, both LHS and RHS are homogeneous of degree $\ell$ with respect to $\mu$, so we may renormalize $\tilde{x}$ such that $\mu = 1$. Then we apply Proposition 2.15 combined with Lemma 4.2 and the results of Section 4. We remark that since $\theta_0^{\Theta_{\mathcal{L}^{\ell}}}$ is invariant by $A_1[\ell n]$, we only need to sum through $t \in A_2[\ell]$.

**Remark 5.2.** We can use Theorem 5.1 to get an isogeny algorithm as follows: let $f: A \to B$ be the isogeny. Then we have a contragredient isogeny $\tilde{f}: B \to A$, and given $x \in A$, we can use the results of Section 4.1 to compute the theta coordinates of level $\ell n$ of a preimage $y = \tilde{f}^{-1}(x)$ on $B$. Then applying
**Theorem 5.1** we get the theta coordinates of level $n$ of $\ell y$, which by definition of the contragredient isogeny is exactly $f(x)$. We let the reader check that this recovers exactly Corollary 4.5.

We constructed our descent algorithm by first using Theorem 4.3 to go up in level $n\ell^2$ and then descending to level $n$ via Mumford's isogeny theorem applied to the isogeny $[\ell]$. Conversely, we could recover the ascending algorithm from Theorem 5.1 by first using Section 4.1 applied to $[\ell]$ to compute the coordinates of level $\ell^2 n$ of a point $y$ such that $\ell y = x$, and then apply Theorem 5.1 to get the coordinates of level $\ell n$ of $x$.

**Remark 5.3.** Another way of descending level used in [CR15] was to consider Koizumi's formula. Koizumi uses an isogeny $F: A^r \to A^r$, where $F$ is an integer matrix such that $^tFF = \ell \mathrm{Id}_r$. In particular, the first column of $F$ is given by $(a_1, \dots, a_r)$ such that $\ell = \sum a_i^2$.

We can reinterpret our method as a tweak on this idea: we only use the first column of $F$ to map $A$ into $A^r$ via $P \mapsto (a_i P)$, this is a generalised Segre mapping $S$. The important point is that since $S^*(\mathcal{L}^\ell)^{*,r} = (\mathcal{L}^\ell)^{\sum a_i^2} = \mathcal{L}^{2\ell}$, $S(A[\ell])$ is isotropic in $(A^r, (\mathcal{L}^\ell)^{*,r})$; so we can apply Mumford's isogeny theorem to the kernel $S(A[\ell])$. This recovers the formula of Theorem 5.1.

## 6. THE CASE OF REAL MULTIPLICATION

When our abelian variety $A$ has real multiplication by an order $O$ of rank $g$, then given a principal polarisation $H_0$ we can consider polarisations of the form $\beta H_0$ where $\beta$ is a totally positive real element.

Recall that if $A = V/\Lambda$, $V$ is canonically isomorphic to the tangent space of $A$ at 0. This fixes an embedding $\varphi$ of $O$ into $\mathrm{End}(V)$. We fix a compatible isomorphism $\nu: O \otimes_Z \mathbb{C} \simeq \mathbb{C}^g \to V$.

Given a theta structure of level $n$ on $A$ (with polarisation $H = nH_0$), we want to compute a theta structure of level $\beta n$ (with polarisation $\beta H$, where $\beta H(z_1, z_2) = H(\beta z_1, z_2) = H(z_1, \beta z_2)$). We also want to compute $\beta$-isogenies: $f: (A, \mathcal{L}) \to (B, \mathcal{M})$, i.e. such that if $F$ is the analytic representation of $F$ and $H_A, H_B$ the associated polarisations, $f^*H_B = \beta H_A$. We denote by $\mathcal{L}^\beta$ the line bundle with polarisation $\beta H$ induced by this decomposition.

Here we need to assume that our theta structure is compatible with the real multiplication, i.e. is induced by a symplectic decomposition of $\Lambda$: $\Lambda = \Lambda_1 \oplus \Lambda_2$, such that $\Lambda_i$ is stable under the action of $O$ given by $\beta.\lambda \mapsto \nu(\beta)\lambda$ for $\beta \in O$ and $\lambda \in \Lambda$. We call this an RM-symplectic decomposition. Then, for instance, if $\Lambda' = \Lambda_1/\beta \oplus \Lambda_2$ and $B = V/\Lambda'$, $F: z \mapsto z$ induces a $\beta$-isogeny $(A, \mathcal{L}) \to (B, \mathcal{M})$, where $\mathcal{M}$ is the line bundle on $B$ with polarisation $H_B = H_A$ induced by the symplectic decomposition of $\Lambda'$.

We generalize Section 4.2 as follows: fix a decomposition $\beta = \sum \beta_i$ where each $\beta_i \in O$ is totally positive. For each $\beta_i$ fix a (compatible) $\beta_i$-isogeny $f_i: (A, \mathcal{L}) \to (B_i, \mathcal{M}_i)$ with analytic representation $F_i$. Let $u_i$ be a section of $\mathcal{M}_i$, then $u = \prod u_i \circ f_i$ is a section of $\mathcal{L}$.

**Example 6.1.** If $\alpha_i$ is an endomorphism of $A$, it can be considered as an $\bar{\alpha}_i\alpha_i$-isogeny, where $\bar{\alpha}$ denotes the Rosati involution under our fixed principal polarisation. Then if $\beta = \sum \bar{\alpha}_i\alpha_i$, we can use $f_i = \alpha_i$, i.e. endomorphisms rather than isogenies. The decomposition $\ell = \sum a_i^2$ from Section 4 is a special case of this where furthermore the $\alpha_i$ are integers.

A direct generalisation of Lemma 4.2 yields:

**Lemma 6.2.** Fix an RM symplectic decomposition $\Lambda = \Lambda_1 \oplus \Lambda_2$, and let $\Lambda' = \frac{1}{\beta}\Lambda_1 \oplus \Lambda_2$, or $\Lambda' = \Lambda_1 \oplus \frac{1}{\beta}\Lambda_2$. For $\beta \in O$, we denote by $s_{\Lambda', \mathcal{L}^\beta}: \Lambda' \to \mathfrak{G}(\mathcal{L}^\beta)$, the set section defined by $s_{\Lambda', \mathcal{L}^\beta}(\lambda) = [a_{\mathcal{L}^\beta}(0, \lambda), \lambda]$. For $\lambda \in \Lambda'$, we have:

$$s_{\Lambda', \mathcal{L}^\beta}(\lambda) \cdot \prod u_i(F_i(z)) = \prod s_{\Lambda', \mathcal{L}^{\beta_i}}(\lambda) u_i(F_i(z)) = \prod F_i^* (s_{\Lambda', \mathcal{L}}(F_i(\lambda)) \cdot u_i(z)).$$

To apply this Lemma, we need to assume that we know not only how to compute the isogenies $f_i$, but also their analytic representations $F_i$. More precisely: given the (affine) theta coordinates of level $n$ of $z$: $\tilde{x} = (\theta_j^{\mathcal{L}}(z))_{j \in K_2(\mathcal{L})}$, the algorithm should output the (affine) theta coordinates of $F_i(z)$: $F_i(\tilde{x}) = (\theta_j^{\mathcal{M}_i}(F_i(z)))_{j \in K_2(\mathcal{M}_i)}$. We also need compatibility with the action: given $\lambda \in \Lambda_1 \otimes_Z \mathbb{Q}$ or in $\Lambda_2 \otimes_Z \mathbb{Q}$, the coordinates $\tilde{x}$ of $z$ and the coordinates of $s(\lambda) \cdot \tilde{x} = s(\lambda) \cdot (\theta_j^{\mathcal{L}}(z))_{j \in K_2(\mathcal{L})}$ the algorithm
should output $F_i(s(\lambda) \cdot (\theta_j^\mathcal{L}(z))_{j \in K_2(\mathcal{L})}) = (s(F_i(\lambda)) \cdot (\theta_j^{M_i})_{j \in K_2(M_i)}) (F_i(z))$ (if the former equation is satisfied, the later is already automatically satisfied for $\lambda \in F_i^{-1}(\Lambda_{B,i})$).

We also need to explain how to adapt Theorems 3.8 and 3.11 to obtain an excellent lift of $K = A_1[\beta]$ when $\beta$ is of odd norm. Let $P_1, \dots, P_g$ be a basis of $K$ such that $P_i$ is of order $m_i$ and $\#K = \prod m_i$. Take an excellent lift of each $P_i$ with respect to the order $m_i$, ie if $m_i = 2m'_i + 1$, $(m'_i + 1)\tilde{P}_i = -m'_i\tilde{P}_i$, and compute the other lifts using `mult_add`. This gives an excellent lift $\tilde{K}$ of $K$. A similar method gives an excellent lift $x + \tilde{K}$ of a point $x \in A$.

Then we have the following generalisations of Theorems 4.3 and 5.1 and Corollary 4.5:

**Theorem 6.3.** Let $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ be an abelian variety together with a level $n$ symmetric theta structure. Assume that $\beta$ is of norm prime to $n$, and let $A[\beta] = A_1[\beta] \oplus A_2[\beta]$ be a symplectic decomposition. This induces a unique symmetric theta structure $\Theta_{\mathcal{L}\beta}$ on $\mathcal{L}^\beta$ compatible with $\Theta_{\mathcal{L}}$.

Let $\beta = \sum \beta_i$, and assume we can compute affine $\beta_i$-isogenies $F_i : (A, \mathcal{L}) \to (B, M_i)$ where $F_i$ is the analytic representation of the isogeny $f_i$. Fix excellent lifts $\tilde{A}_i[\beta]$ of the maximal isotropic subgroups $\tilde{A}_i[\beta]$. For $x \in A$, fix an affine lift $\tilde{x}$, excellent lifts $x + P$ with respect to $\tilde{x}$ for $P \in A_1[\beta]$ induced by $\tilde{A}_1[\beta]$, and then excellent lifts $x + P + Q$ with respect to $x + P$ for $Q \in A_2[\beta]$. For this theta structure on $\mathcal{L}^\beta$, we have (up to a constant depending on $\tilde{x}$ only):

$$ \theta_0^{\Theta_{\mathcal{L}\beta}}(x) = \sum_{\tilde{P} \in \tilde{A}_1[\tilde{\beta}]} \prod_{\tilde{\beta} \in \tilde{\beta}} \theta_0^{\Theta_{M_i}}(F_i(x + \tilde{P})), $$

and if $J \in A_2[n\beta]$, writing $J = Q + j$ with $Q \in A_2[\beta]$ and $j \in A_2[n]$,

$$ \theta_J^{\Theta_{\mathcal{L}\beta}}(x) = \sum_{\tilde{P} \in \tilde{K}_1} \prod_{\tilde{\beta} \in \tilde{\beta}} \theta_{f_i(j)}^{\Theta_{M_i}}(F_i(x + \tilde{P} + Q)). $$

*Proof.* By Lemma 6.2, $s_{\Lambda', \mathcal{L}^\beta}(\lambda) \prod \theta_0^{\Theta_{M_i}}(F_i(z)) = \prod F_i^* (s_{\Lambda', \mathcal{L}}(F_i(\lambda)) \cdot \theta_0^{\Theta_{M_i}}(z))$. By assumption, we know how to compute the analytic representation $F_i$ of the isogenies in a way compatible with the action: if $J = Q + j$ as in the Theorem, $F_i^* (s_{\Lambda', \mathcal{L}}(F_i(J)) \cdot \theta_0^{\Theta_{M_i}}(z)) = \theta_{f_i(j)}(F_j(s_{\Lambda', \mathcal{L}}(Q) \cdot \theta_j^{\Theta_{\mathcal{L}}}(z)))$, and the RHS is equal to $\theta_{f_i(j)}(F_j(z + Q))$. $\square$

**Corollary 6.4.** Let $(A, \mathcal{L}, \Theta_{\mathcal{L}})$ be an abelian variety together with a level $n$ symmetric theta structure. Let $K \subset A[\beta]$ be a maximal totally isotropic subgroup, and $f : A \to B = A/K$ be the isogeny. Assume that $\beta$ is of norm prime to $n$, then there is a unique symmetric level subgroup $\tilde{K}$ of $K$ in $G(\mathcal{L}^\beta)$, which induces via $f$ a descent $M$ of $\mathcal{L}^\beta$ on $B$. Furthermore, there is a unique level $n$ theta structure on $B$, $\Theta_M$ compatible with $\Theta_{\mathcal{L}}$ (see Definition 2.8).

Let $\beta = \sum \beta_i$, and assume we can compute affine $\beta_i$-isogenies $F_i : (A, \mathcal{L}) \to (B, M_i)$. Let $x \in A$, fix an affine lift $\tilde{x}$, excellent lifts $\tilde{K}$ of $K$, and $x + \tilde{K}$ of $x$ with respect to $\tilde{x}$ and $\tilde{K}$. Then identifying $K_2(\mathcal{L})$ with $K_2(M)$ via $f$, we have (up to a constant depending only on $\tilde{x}$)

$$ (11) \qquad \theta_{f(j)}^{\Theta_M}(f(x)) = \sum_{P \in \tilde{K}} \prod_{\tilde{\beta} \in \tilde{\beta}} (F_i(x + \tilde{P}))_{f(j)}. $$

**Theorem 6.5.** Let $(A, \mathcal{L}^\beta, \Theta_{\mathcal{L}^\beta})$ be an abelian variety with a symmetric theta structure of level $n\beta$, with $n$ even and $\beta$ of norm prime to $n$, and let $\Theta_{\mathcal{L}}$ be the unique structure on $\mathcal{L}$ compatible with $\Theta_{\mathcal{L}^\beta}$ (Definition 2.8). Let $A[\beta n] = A_1[\beta n] \oplus A_2[\beta n]$ the corresponding symplectic decomposition. Write $\beta = \sum_{i=1}^r \beta_i$, and assume that we can compute affine $\beta$-isogenies $F_i : (A, \mathcal{L}^\beta) \to (B, M_i)$, where $F_i$ is the analytic representation of $f_i$. Let $x \in A$ and fix an arbitrary affine lift $\tilde{x}$.

Then, up to a constant depending only on $\tilde{x}$, for $j \in A_2[\beta n]$,

$$ \theta_{\beta j}^{\Theta_{\mathcal{L}}}(\beta z) = \sum_{t \in A_2[\beta]} \prod_{i=1}^{r} F_i(\tilde{x})_{f_i(j+t)}. $$
**Remark 6.6.** An adaptation of Lemma 6.2 shows that by computing commutator pairings (in the spirit of [LR10]) we may tweak the algorithm of Corollary 6.4 to not only compute the isogeny $f$, but also its analytic representation $F$ in a way compatible with the action. This opens up a recursive approach to compute $\beta$-isogenies.

All the difficulty resides in bootstrapping the algorithm. In Section 4.2, we simply had to compute the multiplication by $[a_i]$, whose affine form (easily checked to be compatible with the action) is given by $\tilde{x} \mapsto \text{mult}(a_i, \tilde{x})$. When $k = \mathbb{F}_q$ is a finite field, we may use the Frobenius $\pi_q$ to compute more general endomorphisms. We then need to find a decomposition $\beta = \sum \alpha_i \bar{\alpha}_i$ of endomorphisms (possibly with denominators). This is the approach followed in [DJR+17]. Alternatively when $g = 2$, the real multiplication field is a quadratic real field $\mathbb{Q}(\sqrt{d})$, and the endomorphism $\sqrt{d}$ is a $d$-isogeny which can be computed using Corollary 4.5; see [Rob14] for this case. We leave the details to future work.

REFERENCES

[BL04] C. Birkenhake and H. Lange. *Complex abelian varieties*. Second. Vol. 302. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Berlin: Springer-Verlag, 2004, pp. xii+635. ISBN: 3-540-20488-1 (cit. on pp. 4–6, 8).

[BCR10] G. Bisson, R. Cosset, and D. Robert. "AVIsogenies". Magma package devoted to the computation of isogenies between abelian varieties. 2010. URL: https://www.math.u-bordeaux.fr/~damienrobert/avisogenies/. Free software (LGPLv2+), registered to APP (reference IDDN.FR.001.440011.000.R.P.2010.000.10000). Latest version 0.6, released on 2012-11-28. (Cit. on pp. 17, 18).

[Cos11] R. Cosset. "Application des fonctions thêta à la cryptographie sur courbes hyperelliptiques". PhD thesis. 2011 (cit. on p. 17).

[CR15] R. Cosset and D. Robert. "An algorithm for computing $(\ell, \ell)$-isogenies in polynomial time on Jacobians of hyperelliptic curves of genus 2". In: *Mathematics of Computation* 84.294 (Nov. 2015), pp. 1953–1975. DOI: 10.1090/S0025-5718-2014-02899-8. URL: http://www.normalesup.org/~robert/pro/publications/articles/niveau.pdf. HAL: hal-00578991, eprint: 2011/143. (Cit. on pp. 1–4, 19).

[CE14] J.-M. Couveignes and T. Ezome. "Computing functions on Jacobians and their quotients". In: *LMS Journal of Computation and Mathematics* 18.1 (2014), pp. 555–577. arXiv: 1409.0481 (cit. on p. 3).

[DJR+17] A. Dudeanu, D. Jetchev, D. Robert, and M. Vuille. "Cyclic Isogenies for Abelian Varieties with Real Multiplication". Oct. 2017. HAL: hal-01629829. (Cit. on pp. 3, 21).

[Gau07] P. Gaudry. "Fast genus 2 arithmetic based on Theta functions". In: *Journal of Mathematical Cryptology* 1.3 (2007), pp. 243–265 (cit. on p. 17).

[GL09] P. Gaudry and D. Lubicz. "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines". In: *Finite Fields Appl.* 15.2 (2009), pp. 246–260. ISSN: 1071-5797. DOI: 10.1016/j.ffa.2008.12.006. URL: https://doi.org/10.1016/j.ffa.2008.12.006 (cit. on p. 17).

[Igu66] J.-i. Igusa. "On the graded ring of theta-constants (II)". In: *American Journal of Mathematics* 88.1 (1966), pp. 221–236 (cit. on p. 4).

[KNR+20] M. Kirschmer, F. Narbonne, C. Ritzenthaler, and D. Robert. "Spanning the isogeny class of a power of an elliptic curve". Accepted for publication at *Mathematics of Computation*. Apr. 2020. arXiv: 2004.08315. URL: http://www.normalesup.org/~robert/pro/publications/articles/algebraic_obstruction.pdf. HAL: hal-02554714. (Cit. on p. 4).

[Koi76] S. Koizumi. "Theta relations and projective normality of abelian varieties". In: *American Journal of Mathematics* (1976), pp. 865–889 (cit. on p. 1).

[LR10] D. Lubicz and D. Robert. "Efficient pairing computation with theta functions". In: ed. by G. Hanrot, F. Morain, and E. Thomé. Vol. 6197. Lecture Notes in Comput. Sci. 9th International Symposium, Nancy, France, ANTS-IX, July 19-23, 2010, Proceedings. Springer-Verlag, July 2010. DOI: 10.1007/978-3-642-14518-6_21. URL: http:
//www.normalesup.org/~robert/pro/publications/articles/pairings.pdf. Slides: 2010-07-ANTS-Nancy.pdf (30min, International Algorithmic Number Theory Symposium (ANTS-IX), July 2010, Nancy), HAL: hal-00528944. (Cit. on pp. 9, 15, 21).

[LR12] D. Lubicz and D. Robert. "Computing isogenies between abelian varieties". In: *Compositio Mathematica* 148.5 (Sept. 2012), pp. 1483–1515. DOI: 10.1112/S0010437X12000243. arXiv: 1001.2016 [math.AG]. URL: http://www.normalesup.org/~robert/pro/publications/articles/isogenies.pdf. HAL: hal-00446062. (Cit. on pp. 2–4, 13).

[LR15] D. Lubicz and D. Robert. "Computing separable isogenies in quasi-optimal time". In: *LMS Journal of Computation and Mathematics* 18 (1 Feb. 2015), pp. 198–216. DOI: 10.1112/S146115701400045X. arXiv: 1402.3628. URL: http://www.normalesup.org/~robert/pro/publications/articles/rational.pdf. HAL: hal-00954895. (Cit. on pp. 2, 3, 9, 11, 17).

[LR16] D. Lubicz and D. Robert. "Arithmetic on Abelian and Kummer Varieties". In: *Finite Fields and Their Applications* 39 (May 2016), pp. 130–158. DOI: 10.1016/j.ffa.2016.01.009. URL: http://www.normalesup.org/~robert/pro/publications/articles/arithmetic.pdf. HAL: hal-01057467, eprint: 2014/493. (Cit. on pp. 9, 17).

[Mum66] D. Mumford. "On the equations defining abelian varieties. I". In: *Invent. Math.* 1 (1966), pp. 287–354 (cit. on pp. 1–3, 6–8).

[Mum67] D. Mumford. "On the equations defining abelian varieties. III". In: *Invent. Math.* 3 (1967), pp. 215–244 (cit. on p. 17).

[Mum83] D. Mumford. *Tata lectures on theta I*. Vol. 28. Progress in Mathematics. With the assistance of C. Musili, M. Nori, E. Previato and M. Stillman. Boston, MA: Birkhäuser Boston Inc., 1983, pp. xiii+235. ISBN: 3-7643-3109-7 (cit. on pp. 1, 4, 8).

[Mum84] D. Mumford. *Tata lectures on theta II*. Vol. 43. Progress in Mathematics. Jacobian theta functions and differential equations, With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. Boston, MA: Birkhäuser Boston Inc., 1984, pp. xiv+272. ISBN: 0-8176-3110-0 (cit. on p. 4).

[Rob14] D. Robert. "Isogenies between abelian varieties". ANR Peace conference Effective moduli spaces and applications to cryptography, Rennes. June 2014. URL: http://www.normalesup.org/~robert/pro/publications/notes/2014-06-Rennes-Moduli.pdf (cit. on p. 21).

[Rob21] D. Robert. "Efficient algorithms for abelian varieties and their moduli spaces". PhD thesis. Université Bordeaux, June 2021. URL: http://www.normalesup.org/~robert/pro/publications/academic/hdr.pdf. Slides: 2021-06-HDR-Bordeaux.pdf (1h, Bordeaux). (Cit. on p. 3).

[Som21] A. Somoza. "thetAV". Sage package devoted to the computation with abelian varieties with theta functions. 2021. URL: git@github.com:dlubicz/thetAV.git (cit. on p. 17).

IRMAR, UNIVERSITÉ DE RENNES 1, CAMPUS DE BEAULIEU, F-35042 RENNES FRANCE

Email address: david.lubicz@univ-rennes1.fr

URL: http://perso.univ-rennes1.fr/david.lubicz/

INRIA BORDEAUX-SUD-OUEST, 200 AVENUE DE LA VIEILLE TOUR, 33405 TALENCE CEDEX FRANCE

Email address: damien.robert@inria.fr

URL: http://www.normalesup.org/~robert/

INSTITUT DE MATHÉMATIQUES DE BORDEAUX, 351 COURS DE LA LIBERATION, 33405 TALENCE CEDEX FRANCE