--- abstract: 'Jacobi's $\theta$ function has numerous applications in mathematics and computer science; a naive algorithm allows the computation of $\theta(z,\tau)$, for $z, \tau$ verifying certain conditions, with precision $P$ in $O(\mathcal{M}(P) \sqrt{P})$ bit operations, where $\mathcal{M}(P)$ denotes the number of operations needed to multiply two complex $P$-bit numbers. We generalize an algorithm which computes specific values of the $\theta$ function (the *theta-constants*) in asymptotically faster time; this gives us an algorithm to compute $\theta(z, \tau)$ with precision $P$ in $O(\mathcal{M}(P) \log P)$ bit operations, for any $\tau \in \mathcal{F}$ and $z$ reduced using the quasi-periodicity of $\theta$.' author: - | Hugo Labrande$ ^{1,2,3,4}$\ ****\ $^1$ Université de Lorraine, LORIA, UMR 7503, Vandoeuvre-lès-Nancy, F-54506, France\ $^2$ LORIA / INRIA Lorraine, CARAMEL team,\ 615 rue du jardin botanique, 54602 Villers-lès-Nancy Cedex, France\ $^3$ CNRS, LORIA, UMR 7503, Vandoeuvre-lès-Nancy, F-54506, France\ $^4$ University of Calgary, 2500 University Dr NW, Calgary, AB, Canada T2N1N4\ <wjuarez@example.net> bibliography: - 'biblioarticle.bib' nocite: '[@*]' title: 'Computing Jacobi's theta-fuction in quasi-linear time' --- Introduction ============ Jacobi's $\theta$ function appears in a wide range of fields, such as non-linear differential equations (as a solution of the heat equation), the study of modular forms, and number theory, in which it is the main ingredient to convert between algebraic and analytic representations of elliptic curves. Namely, we have the embedding @Mumford1 [I.4] $$\begin{aligned} \mathbb{C}/(\mathbb{Z} + \tau \mathbb{Z}) & \rightarrow & \mathbb{P}^3(\mathbb{C}) \\ z & \mapsto & \left( \theta_{00}(2z, \tau), \theta_{01}(2z, \tau), \theta_{10}(2z, \tau), \theta_{11}(2z, \tau) \right)\end{aligned}$$ where the $\theta_i$ are essentially the $\theta$ function with its $z$ argument translated. We also have the equation $$\wp(z, \tau) = \frac{\pi^2}{3} (\theta_{10}^4(0,\tau) - \theta_{01}^4(0,\tau)) - \pi^2 \theta_{01}^2(0,\tau) \theta_{10}^2(0,\tau) \frac{\theta_{00}^2(z,\tau)}{\theta_{11}^2(z,\tau)}$$ which allows to compute, for any point on the torus, its $x$-coordinate on the curve $E(\mathbb{C}) : y^2 = 4x^3 - g_2 x - g_3$. Special values of the $\theta$ function have interesting additional properties: the *theta-constants*, the value of $\theta$ at points $z = 0, \frac{1}{2}$ and $\frac{\tau}{2}$. As modular forms in $\tau$, they are linked to other modular functions, such as the $j$-invariant or Dedekind's $\eta$ function. Computing the value of the theta-constants allows one to compute the value of those modular functions; this has been used in record computations of class polynomials @Enge, which are interesting to generate safe cryptographic curves with the CM method. The main problem we are dealing with here is to compute $\theta(z, \tau)$ with given absolute precision $P$, which allows us to compute the above embedding at any given precision. We will suppose throughout the article that $(z, \tau)$ satisfy certain conditions; the general case can be deduced from this one using formulas we mention later. The $\theta$ function is defined by a rapidly convergent series; under the conditions specified on $z, \tau$, it gives a naive algorithm that requires a running time of $O(\mathcal{M}(P) \sqrt{P})$ bit operations, where $\mathcal{M}(P)$ is the number of operations needed to multiply two $P$-bit complex numbers. Although fast, this is a worse running time than other transcendental functions such as the exponential of a complex number, which can be computed in *quasi-optimal time* $O(\mathcal{M}(P) \log P)$. There is an algorithm to compute the theta-constants asymptotically faster than with the naive method, outlined in @Dupont. This algorithm relies on connections between theta-constants and the *arithmetico-geometric mean* (AGM) of Gauss; the complex-valued AGM, when evaluated at the theta-constants, has interesting properties, and this is used along with Newton's method to, in a sense, invert the AGM and recover the values of the theta-constants. This algorithm allows computation of theta-constants for $\tau \in \mathcal{F}$ with precision $P$ in quasi-optimal time $O(\mathcal{M}(P) \log P)$, independently of $\tau$. It is faster than the naive method for precisions as low as a few thousand bits. In this article, we provide a generalization of this algorithm which computes $\theta(z, \tau)$, for $\tau \in \mathcal{F}$ and $z$ such that ${\operatorname{Im}}(z) \leq {\operatorname{Im}}(\tau)/2$, with absolute precision $P$ in $O(\mathcal{M}(P) \log P)$ bit operations. We give two algorithms: the first one runs in quasi-optimal time in $P$, but its running time depends on $z$ and $\tau$; we then use this algorithm as a subroutine to build a quasi-optimal algorithm with complexity independent of $z$ and $\tau$, provided $\tau \in \mathcal{F}$ and ${\operatorname{Im}}(z) \leq {\operatorname{Im}}(\tau)/2$. An GNU MPC @MPC implementation of the algorithm was realized; it is faster than the naive method for values of $P$ greater than a few hundred thousand digits. Our algorithm provides the six values $\theta(z, \tau), \theta(z+\frac{1}{2}, \tau), \theta(z+\frac{\tau}{2}, \tau), \theta(0, \tau), \theta(\frac{1}{2})$ and $\theta(\frac{\tau}{2})$, which are sufficient to compute the projective embedding mentioned above. It can also be used to compute the Weierstrass $\wp$ function and its derivative in quasi-optimal time; hence, this paper provides a quasi-optimal time algorithm to compute the "Jacobi map" $\mathbb{C}/\Lambda \rightarrow E(\mathbb{C})$ of an elliptic curve. We note that the "Abel map" $E(\mathbb{C}) \rightarrow \mathbb{C}/\Lambda$ can already be computed in quasi-optimal time using links to elliptic integrals and the Landen isogeny; see @BostMestre88 and @CremonaThongjunthug. We note that @LutherOttenTheta gives an algorithm to compute $\theta$ with real arguments (i.e. $\theta(u, m)$ with $0 < m < 1$ and $0 \leq u \leq K(m)$), defined by its representation as an infinite product, with the same, quasi-optimal complexity. Their algorithm relies on the Landen transform for the $\theta$ function, and could perhaps be generalized to the complex setting. We had independently pursued this line of thought, but found that in the complex setting, the presence of trigonometric functions induced heavy precision losses for some inputs; however, there may be a workaround those issues, which would allow one to find an algorithm for the complex setting and with quasi-optimal complexity relying on the Landen transform. This article is organized as follows. We introduce the necessary mathematical background and the strategies we follow for argument reduction in Section 2, which justifies our choice to consider throughout the paper the case $\tau \in \mathcal{F}$ and ${\operatorname{Im}}(z) \leq {\operatorname{Im}}(\tau)/2$; we then provide an analysis of the naive algorithm for $\theta(z,\tau)$ under those conditions. Section 3 introduces a sequence derived from relations between values of $\theta$, and we prove quadratic convergence of a certain homogeneization of the sequence; this is what replaces the AGM in the general case. Section 4 gives a first algorithm for computing $\theta$-functions, with a complexity depending on $z$ and $\tau$; this is quasi-optimal provided that $z,\tau$ belong to a compact set. We then get rid of the dependency in $z, \tau$ much in the same way as in the case of theta-constants, which gives a uniform algorithm with complexity $O(\mathcal{M}(P) \log P)$. Section 5 shows timings for our GNU MPC implementation of this last algorithm and compare it to our implementation of the naive algorithm. The function theta, and theta-constants ======================================= Definitions and argument reduction {#section:argumentreduction} ---------------------------------- We recall a few basic facts, following the presentation of @Mumford1. Define, for $z \in \mathbb{C}$ and $\tau \in \mathcal{H}$ (i.e. ${\operatorname{Im}}\tau > 0$) $$\theta(z, \tau) = \sum_{n \in \mathbb{Z}} \exp\left(\pi i \tau n^2 + 2 \pi i n z\right).$$ \[quasi-periodicity\] We have $\theta(z + 1, \tau) = \theta(z, \tau)$ and $\theta(z + \tau, \tau) = e^{- \pi i z - 2 \pi i \tau} \theta(z, \tau)$; in fact for any integers $a,b$, $$\theta(z + a\tau + b, \tau) = e^{- i \pi a^2 \tau - 2 i \pi a z} \theta(z,\tau). \label{eq:quasiperiodicitytheta}$$ We also define the following variants of the theta function (which are related to the definition of "theta functions with characteristics") @Mumford1 [Section I.3]: \[defineFlavorsofTheta\] $$\begin{aligned} \theta_{00}(z, \tau) = \theta\left(z, \tau\right) & \qquad & \theta_{10}(z, \tau) = \exp\left(\pi i \tau/4 + \pi i z \right) \theta\left(z + \frac{\tau}{2}, \tau\right) \\ \theta_{01}(z, \tau) = \theta\left(z+\frac{1}{2}, \tau\right) & \qquad & \theta_{11}(z, \tau) = \exp\left(\pi i \tau/4 + \pi i (z+1/2) \right) \theta\left(z + \frac{\tau+1}{2}, \tau\right) \\\end{aligned}$$ We define **theta-constants** as the values in 0 of those functions. Those functions and their theta-constants are linked by a great number of formulas; we will give such formulas as we use them, and most of them can be found in @Mumford1 [Section I.5]. Note that we have: For any $\tau$, the functions $z \mapsto \theta_{00}(z,\tau), z \mapsto \theta_{01}(z,\tau), z \mapsto \theta_{10}(z,\tau)$ are even, while $z \mapsto \theta_{11}(z,\tau)$ is odd. The latter implies that $\theta_{11}(0,\tau) = 0$, so the only theta constants we are interested in are $\theta_{00}(0,\tau), \theta_{01}(0,\tau)$, and $\theta_{10}(0,\tau)$. Those properties can be used for the purpose of argument reduction. For instance, we can use the parity of $\theta$ to suppose that ${\operatorname{Im}}(z) \geq 0$; if this is not the case, one can consider $-z$ instead of $z$, which does not change the value of $\theta$ but ensures that ${\operatorname{Im}}(z) \geq 0$. Furthermore, Equation can be used to recover $\theta(z,\tau)$ from the value of $\theta(z',\tau)$, where $z'$ is such that $|{\operatorname{Re}}(z')| \leq \frac{1}{2}$ and $|{\operatorname{Im}}(z')|~\leq~\frac{{\operatorname{Im}}(\tau)}{2}$; the added cost is the cost of computing an exponential factor. This exponential factor can become quite big; should one want to compute $\theta(z,\tau)$ with an error of at most $2^{-P}$, they have to work with representations of at least $P + C$ bits, with $$C = \log_2(|\theta(z',\tau)|) + \pi \log_2(e) (a^2 {\operatorname{Im}}(\tau) + 2a {\operatorname{Im}}(z)) + 2$$ This is because the integral part of the result fits in $C$ bits, while the fractional part should be coded on at least $P$ bits to ensure a final error bounded by $2^{-P}$. The complexity of running our algorithm and computing the exponential factor will be $O(\mathcal{M}(P + C) \log(P + C))$, and hence will depend on $\tau$ and $z$; this is inevitable. Hence, throughout the paper we suppose that $z$ is reduced, in the sense that $|{\operatorname{Re}}(z)| \leq \frac{1}{2}$ and $0 \leq {\operatorname{Im}}(z) \leq \frac{{\operatorname{Im}}(\tau)}{2}$, with the understanding that the step of argument reduction has a complexity depending on the original values of $z$ and $\tau$. However, as Section \[subsection:naive\] shows, this hypothesis, combined with a hypothesis in $\tau$, allows us to work with values of $\theta$ bounded by 4, which allows us to write an algorithm with complexity only depending on $P$ for any $z$ satisfying these conditions. We can also reduce the second argument of $\theta$. Define the action of $SL_2(\mathbb{Z})$ on the complex upper-half plane $\mathcal{H}$ by $$\begin{pmatrix} a & b \\ c & d \end{pmatrix} \cdot \tau \mapsto \frac{a \tau + b}{c \tau + d}.$$ Its fundamental domain is $$\mathcal{F} = \{ \omega \in \mathcal{H} \enskip | \enskip |{\operatorname{Re}}(\omega)| < 1/2, |\omega|>1 \}$$ Computing $\tau' \in \mathcal{F}$ and $M = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \in SL_2(\mathbb{Z})$ such that $\tau' = M \tau$ can be done by finding the shortest vector in the lattice $(1, \tau)$ using Gauss's algorithm @Vallee, which (since the inertia is small) will be asymptotically negligible. The value of $\theta(z,\tau)$ can then be computed from $\theta(z', \tau')$ (for some value $z'$) using the following theorem: \[extension of <span>@Mumford1 [Theorem 7.1]</span>\] Let $\tau \in \mathcal{H}$ and $z \in \mathbb{C}$, and let\ $\gamma = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \in SL_2(\mathbb{Z})$. Suppose $c > 0$, or $c = 0$ and $d > 0$; if not, take $-\gamma$. Then we have: $$\label{eq:sl2andthetavalues} \theta_i\left(\frac{z}{c\tau +d}, \frac{a \tau +b}{c \tau +d}\right) = \zeta_{i, \gamma, \tau} \sqrt{c \tau + d} e^{i \pi c z^2/(c \tau +d)} \theta_{\sigma(i)}(z, \tau)$$ where the square root is taken with positive real part, $\zeta_{i, \gamma, \tau}$ is an eighth root of unity and $\sigma$ is a permutation of the elements $(00,01,10)$, defined by the following table: a b c d $\sigma(00,01,10)$ ------ ------ ------ ------ -------------------- odd even even odd $(00,01,10)$ odd odd even odd $(01,00,10)$ odd even odd odd $(10,01,00)$ even odd odd even $(00,10,01)$ odd odd odd even $(10,00,01)$ even odd odd odd $(01,10,00)$ Define for any $\gamma = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \in SL_2(\mathbb{Z})$: $$e_{\gamma}(\tau) = c \tau + d, \qquad f_{\gamma}(z, \tau) = e^{i \pi c z^2/(c \tau + d)}$$ With a bit of care, one can prove $$e_{\gamma_1}(\gamma_2 \tau) e_{\gamma_2}(\tau) = e_{\gamma_1 \gamma_2}(\tau), \qquad f_{\gamma_1}\left(\frac{z}{c_2 \tau + d_2}, \gamma_2 \tau\right) f_{\gamma_2}(z, \tau) = f_{\gamma_1 \gamma_2}(z, \tau)$$ The maps $T: \tau \mapsto \tau + 1$ and $S: \tau \mapsto \frac{-1}{\tau}$ are generators of $SL_2(\mathbb{Z})$, and we have @Mumford1 [Table V, p. 36] $$\theta_i\left(z, T \tau\right) = \zeta_{i,T, \tau} \sqrt{e_{T}(\tau)} f_{T}(z, \tau) \theta_{\sigma_T(i)}(z, \tau), \qquad \theta_i\left(\frac{z}{\tau}, S \tau\right) = \zeta_{i,S, \tau} \sqrt{e_{S}(\tau)} f_{S}(z, \tau) \theta_{\sigma_S(i)}(z, \tau)$$ with square roots taken with real parts and for some $\zeta \in \mathbb{U}_8$ and $\sigma_S, \sigma_T \in \mathfrak{S}_3$. Hence for all $\gamma \in SL_2(\mathbb{Z})$, $$\theta_i\left( \frac{z}{e_{\gamma}(\tau)^2}, \gamma \tau \right) = \zeta_{i, \gamma, \tau} \sqrt{e_{\gamma}(\tau)} f_{\gamma}(z, \tau) \theta_{\sigma_{\gamma}(i)}(z, \tau)$$ for some root of unity and some permutation. The correspondance $\gamma \mapsto \sigma_{\gamma}$ can be determined from @Mumford1 [p. 36], although one can simply notice it is independent of $z$ and use the tables found by Gauss in the case of theta-constants @Cox [Eq. 2.15]. Finally, we could attempt to give a formula for $\zeta_{i, \gamma, \tau}$, but it is more efficient to simply compute a very low precision approximation of $\theta(z, \tau)$ and compare it to the full-precision value to determine which eighth root is needed. Thus, in order to recover $\theta_i(z, \tau)$ from $\theta_i\left(\frac{z}{c \tau + d}, \frac{a \tau + b}{c \tau + d} \right)$, one needs to compute $\sqrt{c \tau + d}$ (which is done in $O(\mathcal{M}(P))$ bit operations) and $e^{\pi i c z^2 / (c\tau+d)}$ (done in $O(\mathcal{M}(P) \log P)$ bit operations), and perform a division; determining $\zeta$ is asymptotically negligible. The cost of this step is then $O(\mathcal{M}(P) \log P)$ bit operations. We note that in general, because of the permutation $\sigma_{\gamma}$, we need to have computed all three values $\theta_{00,01,10}\left(\frac{z}{c \tau + d}, \frac{a \tau + b}{c \tau + d} \right)$ in order to be able to use the formula to compute, say, $\theta_{00}(z,\tau)$. We will occasionally talk about computing $\theta_{11}$, but this will not be the focus of the paper. Hence, the problem we consider in this paper is the following: $$\begin{aligned} \text{Compute } && \theta_{00}(z,\tau), \theta_{00}(0,\tau), \theta_{01}(z,\tau), \theta_{01}(0,\tau), \theta_{10}(z,\tau), \theta_{10}(0,\tau) \notag \\ \text{where } && |\tau| > 1, \quad |{\operatorname{Re}}(\tau)| \leq \frac{1}{2}, \quad {\operatorname{Im}}(\tau) > 0, \notag \\ &&|{\operatorname{Re}}(z)| \leq \frac{1}{2}, \quad 0 \leq {\operatorname{Im}}(z) \leq \frac{{\operatorname{Im}}(\tau)}{2} \label{eq:conditions} \\ \text{ in quasi-optimal time,} && \text{ i.e. } O(\mathcal{M}(P) \log P). \notag\end{aligned}$$ Naive algorithm to compute theta {#subsection:naive} --------------------------------- ### Partial summation of the series defining theta We define the following partial summation for the series defining $\theta(z, \tau)$: $$S_B(z, \tau) = 1 + \sum_{0 < n < B} q^{n^2} ( e^{2 i \pi n z} + e^{-2 i \pi n z})$$ where use the notation $q = e^{i \pi \tau}$. We have \[naiveboundtheta\] Suppose that ${\operatorname{Im}}(\tau) \geq 0.35$ and $0 \leq {\operatorname{Im}}(z) \leq {\operatorname{Im}}(\tau)/2$; in particular, this is the case if the conditions are satisfied. Then, for $B \geq 1$, $|\theta(z,\tau) - S_B(z,\tau)| \leq 3 |q|^{(B-1)^2}$. We look at the remainder of the series: $$\begin{aligned} \label{eq:proofnaive} |\theta(z, \tau) - S_B(z, \tau)| & \leq & \sum_{n \geq B} |q|^{n^2} (|e^{2 i \pi n z}| + |e^{-2 i \pi n z}|) \notag \\ & \leq & \sum_{n \geq B} |q|^{n^2} (1+|q|^{-n}) \leq 2 \sum_{n \geq B} |q|^{n^2-n} \notag \\ & \leq & 2 \sum_{n \geq B} |q|^{(n-1)^2} \leq 2 \sum_{n \geq 0} |q|^{(B-1+n)^2} \notag \\ & \leq & 2 |q|^{(B-1)^2} \sum_{n \geq 0} |q|^{2n(B-1)+n^2} \notag \\ & \leq & 2 \frac{|q|^{(B-1)^2}}{1 - |q|^{2B-1}}\end{aligned}$$ A numerical calculation shows that for ${\operatorname{Im}}(\tau) \geq 0.35$, we have $\frac{2}{1-|q|} \leq 3$, which proves the proposition. We can prove the same inequality for $\theta_{01}$, since the series that define it has the same terms, up to sign, as the series for $\theta$. Note that, unlike the analysis of @Dupont for naive theta-constant evaluation, we cannot get a bound for the relative precision: since $\theta(\frac{1+\tau}{2}, \tau) = 0$, there is no lower bound for $|\theta(z, \tau)|$.[^1] If we set $$B(P, \tau) = \left\lceil \sqrt{\frac{P+2}{\pi {\operatorname{Im}}(\tau) \log_2(e)}} \right\rceil+1.$$ we have $4 |q|^{(B-1)^2} \leq 2^{-P}$, which means the approximation is accurate with absolute precision $P$. We just showed that: \[naivecomplex\] To compute $\theta(z, \tau)$ with absolute precision $P$ bits, it is enough to sum over all $k \in \mathbb{Z}$ such that $$|k| \leq \left\lceil \sqrt{\frac{P+2}{\pi {\operatorname{Im}}(\tau) \log_2(e)}} \right\rceil + 1$$ Note that this bound is larger than the one of @Dupont [p. 5]. ### Naive algorithm We then present a naive algorithm to compute not only the value of $\theta(z, \tau)$, but also the value of $\theta_{01}(z, \tau), \theta_{00}(0, \tau), \theta_{01}(0, \tau)$ for only a marginal amount of extra computation; this is the algorithm we will use for comparison to the fast algorithm we propose in this article. The algorithm performs computations at a precision $\mathcal{P}$, which we determine later so that the result is accurate to the desired precision $P$. Define the sequence $(v_n)_{n \in \mathbb{N}}$ as $$v_n = q^{n^2} (e^{2 i \pi n z} + e^{-2 i \pi n z})$$ so that $\theta(z, \tau) = 1 + \sum_{n \geq 1} v_n$. This satisfies the following recurrence relation for $n>1$: $$v_{n+1} = q^{2n} v_1 v_n - q^{4n} v_{n-1}.$$ We use this recursion formula to compute $v_n$ efficiently, which is similar to the trick used by @ThomeEnge [Prop. 3]. This removes the need for divisions and the need to compute and store $e^{-2i \pi n z}$, which can get quite big; indeed, computing it only to multiply it by the very small $q^{n^2}$ is wasteful. The resulting algorithm is Algorithm \[naive\]. \[1\] $\text{prec} \gets \mathcal{P}$ $B\gets \left\lceil \sqrt{\frac{P+2}{\pi {\operatorname{Im}}(\tau) \log_2(e)}} \right\rceil + 1$ $\theta_{0,z}\gets 1, \theta_{1,z}\gets 1, \theta_{0,0}\gets 1, \theta_{1,0}\gets 1$ $q\gets e^{i \pi \tau}, \qquad q_1\gets q, \qquad q_2\gets q$ $v_1\gets e^{2 i \pi (z+\tau/2)} + e^{-2 i \pi (z-\tau/2)}, \qquad v\gets v_1, \qquad v'\gets 2$ /\* $q_1 = q^n, q_2 = q^{n^2}, v = v_n, v' = v_{n-1}$ \*/ $\theta_{0,z}\gets \theta_{0,z} + v, \qquad \theta_{1,z}\gets \theta_{1,z} + (-1)^i \times v$ $\theta_{0,0}\gets \theta_{0,0} + 2 q_2, \qquad \theta_{1,0}\gets \theta_{1,0} + (-1)^i \times 2 q_2$ $q_2\gets q_2 \times (q_1)^2 \times q$ $q_1\gets q_1 \times q$ $\text{temp}\gets v, \qquad v\gets \left( q_1^2 \times v_1 \right) \times v - q_1^4 \times v' \qquad v'\gets \text{temp}$ ### Error analysis and complexity We have the following theorem: \[naiveanalysis\] For $z, \tau$ satisfying conditions , Algorithm \[naive\] with $\mathcal{P} = P + \log B + 7$ computes $\theta_{00}(z, \tau)$, $\theta_{01}(z, \tau)$, $\theta_{00}(0, \tau)$, $\theta_{01}(0, \tau)$ with absolute precision $P$ bits. This gives an algorithm which has bit complexity $O\left(\mathcal{M}(P) \sqrt{\frac{P}{{\operatorname{Im}}(\tau)}}\right)$. Performing the analysis of this algorithm requires bounding the error that is incurred during the computation. We then compensate the number of inaccurate bits by increasing the precision. We use the following theorem: \[theoremlossofprec\] For $j = 1,2$, let $z_j = x_j + i y_j \in \mathbb{C}$ and $\tilde{z_j} = \tilde{x_j} + i \tilde{y_j}$ its approximation. Suppose that $|z_j - \tilde{z_j}| \leq k_j 2^{-P}$ and that $k_j \leq 2^{P/2}$. Then 1. $|{\operatorname{Re}}(z_1+z_2) - {\operatorname{Re}}(\tilde{z_1}+\tilde{z_2})| \leq (k_1 + k_2) 2^{-P}$ 2. $|{\operatorname{Re}}(z_1z_2) - {\operatorname{Re}}(\tilde{z_1}\tilde{z_2})| \leq (2 + 2 k_1|z_2| + 2 k_2|z_1|) 2^{-P}$ 3. $|{\operatorname{Re}}(z_1^2) - {\operatorname{Re}}(\tilde{z_1}^2)| \leq (2 + 4 k_1|z_1|) 2^{-P}$ and the same bounds apply to imaginary parts as well; and 4. $|e^{z_1} - e^{\tilde{z_1}}| \leq |e^{z_1}|\frac{7 k_1 + 8.5}{2} 2^{-P} $. Furthermore if $|z_j| \geq 2 k_j 2^{-P}$, 5. $| {\operatorname{Re}}\left(\frac{z_1}{z_2}\right) - {\operatorname{Re}}\left(\frac{\tilde{z_1}}{\tilde{z_2}}\right)| \leq \left( \frac{6(2 + 2k_1 |z_2| + 2k_2 |z_1|)}{|z_2|^2} + \frac{2(4 + 8 k_2 |z_2|)(2 |z_1||z_2| + 1) + 2}{|z_2|^4} \right) 2^{-P}$ and the same bound applies to the imaginary part, and 6. $|\sqrt{z_1} - \sqrt{\tilde{z_1}}| \leq \frac{k_1}{\sqrt{|z_1|}} 2^{-P} $. This theorem is not very hard to prove; we refer to @absolutelossofprec for details. \[Proof of Theorem \[naiveanalysis\]\] We first determine the size of the quantities we are manipulating; this is needed to evaluate the error incurred during the computation, as well as the number of bits needed to store fixed-point approximations of absolute precision $P$ of the intermediate quantities. Taking $B=1$ in Proposition \[naiveboundtheta\] gives $|\theta(z,\tau)-1| \leq 3$, so $|\theta(z,\tau)| \leq 4$; actually, this also proves $|S_B(z,\tau)|\leq 4$, which means that $|\theta_{0,z}|, |\theta_{1,z}|, |\theta_{0,0}|, |\theta_{1,0}|$ are bounded by 4. We also have $|q| \leq 0.07$, and $|q_2| \leq |q|^{n^2} \leq |q|^n = |q_1| \leq |q| \leq 0.07$. As for the $v_i$, we have $v_0 = 2$, and for $n \geq 1$ $$|v_n| \leq |q|^{n^2+n} + |q|^{n^2-n} \leq (1+|q|^{2n}) q^{n^2-n} \leq 1.0049 q^{n^2-n} \leq 1.0049$$ Hence, storing all the complex numbers above, including our result, with absolute precision $P$ only requires $P+2$ bits, since their integral part is coded on only 2 bits. Note that, had we computed $e^{-2i \pi n z}$ before multiplying it by $q^{n^2}$, we would have needed $O({\operatorname{Im}}(\tau))$ more bits, which worsens the asymptotic complexity. Computing the absolute precision lost during this computation is done using Theorem \[theoremlossofprec\]. We start with the bounds $|\tau - \tilde{\tau}| \leq \frac{1}{2} 2^{-\mathcal{P}}$ and $|z - \tilde{z}| \leq \frac{1}{2} 2^{-\mathcal{P}}$, coming from the hypothesis that the approximations of $z$ and $\tau$ are correctly rounded with precision $\mathcal{P}$. We then need to estimate $k_{v_1}$ and $k_q$, which can be done using the formula giving the absolute error when computing an exponential from Theorem \[theoremlossofprec\]. Given that $\tau \in \mathcal{F}$, we have $$\begin{aligned} | q - \tilde{q} | & \leq & 0.07 \frac{7 \times 1/2 + 8.5}{2} 2^{-P} \leq 0.42 \times 2^{-P} \\ | v_1 - \tilde{v_1}| & \leq & 6 ( |e^{-\pi({\operatorname{Im}}(\tau)+2{\operatorname{Im}}(z))}| + |e^{\pi(2{\operatorname{Im}}(z)-{\operatorname{Im}}(\tau))}| ) \times 2^{-P} \\ & \leq & 6 (|q|+1) 2^{-P} \leq 6.42 \times 2^{-P}\end{aligned}$$ which means that $k_q \leq 0.42$ and $k_{v_1} \leq 6.42$. We then need to evaluate the loss of precision for each variable and at each step of the algorithm, which gives recurrence relations with non-constant coefficients. Solving those is rather tedious, and we use loose upper bounds to simplify the computation; we do not detail this proof in the present article. The results obtained by this method show that the error on the computation of the theta-constants is bounded by $(0.3B + 105.958)2^{-\mathcal{P}}$, and the one on the computation of the theta function is smaller than $(5.894 B + 28.062)2^{-\mathcal{P}}$. This proves that the number of bits lost is bounded by $\log_2 B + c$, where $c$ is a constant smaller than 7; hence we set $\mathcal{P} = P + \log B + 7$. Finally, evaluating $\pi$ and $\exp(z)$ with precision $\mathcal{P}$ can be done in $O(\mathcal{M}(\mathcal{P}) \log \mathcal{P})$ @Borwein, but this is negligible asymptotically. In the end, computing an approximation up to $2^{-P}$ of $\theta(z, \tau)$ can be done in $O\left(\mathcal{M}\left(P + \log(P/{\operatorname{Im}}(\tau)) + c \right) \sqrt{\frac{P}{{\operatorname{Im}}(\tau)}} \right) = O\left(\mathcal{M}(P) \sqrt{\frac{P}{{\operatorname{Im}}(\tau)}}\right)$ bit operations. ### Computing theta10 {#section:theta10naive} We mentioned in section \[section:argumentreduction\] the need to compute $\theta_{10}(z,\tau)$ and $\theta_{10}(0, \tau)$ as well. One could think of recovering those values using Jacobi's quartic formula and the equation of the variety: $$\begin{aligned} \theta_{00}(0,\tau)^4 &=& \theta_{01}(0,\tau)^4 + \theta_{10}(0,\tau)^4 \label{eq:Jacobi} \\ \theta_{00}^2(z,\tau) \theta_{00}^2(0,\tau) &=& \theta_{01}^2(z,\tau) \theta_{01}^2(0,\tau) + \theta_{10}^2(z,\tau) \theta_{10}^2(z,\tau) \label{eq:Variety}\end{aligned}$$ that is to say, compute $$\begin{aligned} \theta_{10}(0, \tau) &=& \left( \theta_{00}(0,\tau)^4 - \theta_{01}(0,\tau)^4 \right)^{1/4} \\ \theta_{10}(z, \tau) &=& \frac{\sqrt{\theta_{00}^2(z,\tau) \theta_{00}^2(0,\tau) - \theta_{01}^2(z,\tau) \theta_{01}^2(0,\tau)} }{\theta_{10}(0,\tau)}.\end{aligned}$$ However, this approach induces an asymptotically large loss of absolute precision for both $\theta_{10}(0,\tau)$ and $\theta_{10}(z,\tau)$. According to Theorem \[theoremlossofprec\], both square root extraction and inversion induce a loss of precision proportional to $|z|^{-1}$; since $\theta_{10}(0,\tau) \sim 4 q^{1/2}$, the number of bits lost by applying those formulas is $O({\operatorname{Im}}(\tau))$. Note that those formulas would also induce a big loss in relative precision; since $\theta_{00}(0,\tau)$ and $\theta_{01}(0,\tau)$ are very close when ${\operatorname{Im}}(\tau)$ goes to infinity, the subtraction induces a relative precision loss of $O({\operatorname{Im}}(\tau))$ bits (for more details, see @Dupont [Section 6.3]). Either of those analyses show that, in order to compensate precision loss, the naive algorithm should actually be run with a precision of $O(P + \log B + {\operatorname{Im}}(\tau))$, which gives a running time that worsens, insteads of getting better, when ${\operatorname{Im}}(\tau)$ gets big. We do not recommend this approach. Instead, one should compute partial summations of the series defining $\theta_{10}$, much in the same way as we did for $\theta(z,\tau)$. We outline the analysis in this case, which is very similar to the one for $\theta$: supposing $n \geq 2$, we have $n^2-2n \geq (n-2)^2$, which can be used to prove that $|\theta_{10}(z,\tau) - S_B| \leq 3|q|^{(B-2)^2}$, so that the bound on $B$ is thus just one more than for $\theta$; the recurrence relation is the same; $q^{2n}|v_1|$ is bounded by 2 instead of 1, which in the worst case means $\log B$ more guard bits are needed. In what follows, we will refer to this algorithm as "the naive algorithm to compute $\theta_{10}(0, \tau), \theta_{10}(z,\tau)$"; its asymptotic complexity is, just like Algorithm \[naive\], $O\left(\mathcal{M}(P) \sqrt{\frac{P}{{\operatorname{Im}}(\tau)}}\right)$ bit operations, which gets better as ${\operatorname{Im}}(\tau)$ increases. We note that similar considerations apply to the problem of computing $\theta_{11}$. One can compute $\theta_{11}(z,\tau)$ using the formula @Mumford1 [p.22] $$\label{eq:recoverTheta11} \theta_{11}(z,\tau)^2 = \frac{\theta_{01}(z,\tau)^2 \theta_{10}(0,\tau)^2 - \theta_{10}(z,\tau)^2 \theta_{01}(0,\tau)^2}{\theta_{00}(0,\tau)^2}.$$ Using this formula loses only a few bits of precision since $\theta_{00}(0,\tau)$ is bounded; however, one then needs to compute a square root, which potentially loses $O({\operatorname{Im}}(\tau))$ bits. Hence, a summation of the series, which directly gives $\theta_{11}$, is preferable. Fast computation of theta-constants {#section:AGMthetaconstants} ----------------------------------- Recall the definition of the arithmetico-geometric mean (AGM) for two positive real numbers $a,b$: $$\begin{aligned} \label{eq:AGM} a_0 = a, && b_0 = b \notag \\ a_{n+1} = \frac{a_n + b_n}{2} && b_{n+1} = \sqrt{a_n b_n}\end{aligned}$$ The sequences $(a_n)_{n \in \mathbb{N}}$ and $(b_n)_{n \in \mathbb{N}}$ both converge to the same limit, called the **arithmetico-geometric mean** of $a$ and $b$. Furthermore, $(a_n)$ and $(b_n)$ are quadratically convergent, in the sense of the following definition: A sequence $(a_n)$ is said to be **quadratically convergent** (to a limit $\ell$) if there is a $C > 0$ such that for $n$ large enough: $$|a_{n+1} - a_n | \leq C |a_n - a_{n-1}|^2$$ The constant $C$ in the case of the AGM can be taken as $\frac{\pi}{8 \min(|a|,|b|)}$ @Dupont [Thm. 1]. Quadratic convergence implies that the number of exact digits approximately doubles with each iteration, so that one only needs $O(\log P)$ iterations to compute $\operatorname{AGM}(a,b)$ with precision $P$; hence the total cost of computing $\operatorname{AGM}(a,b)$ is $O(\mathcal{M}(P) \log P)$ bit operations. It is possible to generalize the AGM to complex numbers, but there are two possibilities for the choice of the square root at each step. We then call **an AGM sequence for $\bm{a}$ and $\bm{b}$** any sequence $(a_n, b_n)_{n \in \mathbb{N}}$ such that $$a_0=a, \quad b_0=b, \qquad 2a_{n+1} = a_n+b_n, \quad b_{n+1}^2 = a_n b_n$$ Note that there are uncountably many AGM sequences for $a, b$. We define unambiguously *the* AGM of two complex numbers following @Cox: Let $a,b \in \mathbb{C}$ and let $(a_n, b_n)_{n \in \mathbb{N}}$ be an AGM sequence for $a$ and $b$. We say that the choice of signs is **good** at the rank $n$ if $$| a_n - b_n | < |a_n + b_n| \qquad or \quad |a_n-b_n| = |a_n+b_n| \text{ and } {\operatorname{Im}}\left(\frac{b_n}{a_n}\right) > 0$$ We call the AGM sequence for $a$ and $b$ in which all the choices of signs are good the **optimal AGM sequence**, and define $\operatorname{AGM}(a,b)$ as the limit of the optimal AGM sequence for $a$ and $b$. Finally we have the following proposition: \[<span>@Cox [Proposition 2.1]</span>\] Let $(a_n, b_n)_{n \in \mathbb{N}}$ be an AGM sequence for $a,b$: - If $(a_n, b_n)$ has infinitely many bad choices of sign, $\lim_{n \rightarrow \infty} a_n = 0$ and the convergence is at least linear; - If $(a_n, b_n)$ has only finitely many bad choices of sign (for instance if it is optimal), $(a_n)$ and $(b_n)$ both converge quadratically to the same non-zero limit. The link between the complex AGM and theta-constants is well-known: \[propTauduplication0\] We have the following formulas linking theta-constants: $$\begin{aligned} \theta_{00}^2(0, 2\tau) &=& \frac{\theta_{00}^2(0, \tau) + \theta_{01}^2(0, \tau)}{2} \label{eq:TauduplicationConstant00} \\ \theta_{01}^2(0, 2\tau) &=& \theta_{00}(0, \tau) \theta_{01}(0, \tau) \label{eq:TauduplicationConstant01}\end{aligned}$$ This shows that $(\theta_{00}^2(0, 2^n \tau), \theta_{01}(0, 2^n \tau))_{n \in \mathbb{N}}$ is an AGM sequence for $\theta_{00}^2(0, \tau)$ and $\theta_{01}^2(0, \tau)$, and it converges quadratically to 1. Whether or not this sequence is the optimal AGM sequence is controlled by the following result: \[<span>@Dupont [Theorem 2]</span> or <span>@Cox [Lemma 2.9]</span>\] Define $$\mathcal{F}_{k'} = \left\{ \tau \in \mathcal{H} \text{ such that } |{\operatorname{Re}}(\tau)|<1, \left|\tau + \frac{3}{4}\right| \geq \frac{1}{4}, \left|\tau + \frac{1}{4}\right| > \frac{1}{4}, \left|\tau - \frac{1}{4}\right| \geq \frac{1}{4}, \left|\tau - \frac{3}{4}\right| > \frac{1}{4} \right\} \subset \mathcal{H}$$ Let $\tau \in \mathcal{F}_{k'}$, and let $(a_n, b_n)_{n \in \mathbb{N}}$ the optimal AGM sequence for $\theta_{00}^2(0, \tau)$ and $\theta_{01}^2(0, \tau)$. Then for all $n$ we have $(a_n, b_n) = (\theta_{00}^2(0, 2^n \tau), \theta_{01}^2(0, 2^n \tau))$, which implies $\operatorname{AGM}(\theta_{00}^2(0, \tau), \theta_{01}^2(0, \tau)) = 1$. In @Dupont [Algorithm 4], an algorithm relying on the AGM, and with complexity $O(\mathcal{M}(P) \log P)$, is given to compute the value of the theta-constants with precision $P$ bits. The algorithm uses the fact that $k'(\tau) = \frac{\theta_{01}^2(0, \tau)}{\theta_{00}^2(0, \tau)}$ is a solution to the following equation: $$\label{eq:newtonkprime} i \operatorname{AGM}(1, z) - \tau \operatorname{AGM}\left(1, \sqrt{1 - z^2}\right) = 0$$ which is a consequence of the action of $SL_2(\mathbb{Z})$ on the theta-constants, as well as of Jacobi's quartic formula (Equation ). Newton's method, when given an approximation of $k'(\tau)$ with precision $P/2$ as well as the knowledge of $\tau$ with precision $P$, computes an approximation of $k'(\tau)$ with precision $P-\delta$, where $\delta$ is a small constant. If one carries out Newton's method while doubling the working precision with each iteration, it is asymptotically only as costly as the last iteration; this means $k'(\tau)$ can be computed with precision $P$ in quasi-optimal running time. One can then recover the individual values of the theta-constants using the equation $$\label{eq:AGMQuotients} \operatorname{AGM}\left(1, \frac{\theta_{01}(0, \tau)^2}{\theta_{00}(0, \tau)^2} \right) = \frac{1}{\theta_{00}(0, \tau)^2}.$$ However, the complexity of this algorithm is not uniform – that is to say, it reaches this complexity only for $\tau$ within a compact set. A variant of the algorithm is proposed in @Dupont [Algorithm 5] which makes the complexity uniform: if $P \leq 2 \log {\operatorname{Im}}(\tau)$, use the naive algorithm (which gives the right complexity); if not, compute the value of the theta-constants at $\frac{\tau}{2^n}$ for some $n \leq \log {\operatorname{Im}}(\tau)$, and use the AGM to compute the theta-constants at $\tau$. This gives an algorithm which complexity does not depend on $\tau$. A sequence related to theta-functions {#section:aboutF} ===================================== Definition of the F sequence ---------------------------- We start with the following formula: \[propTauduplicationZ\] $$\begin{aligned} \theta_{00}(z, 2\tau)^2 &=& \frac{\theta_{00}(z,\tau) \theta_{00}(0,\tau) + \theta_{01}(z, \tau) \theta_{01}(0, \tau)}{2} \label{eq:Tauduplication00} \\ \theta_{01}(z, 2\tau)^2 &=& \frac{\theta_{00}(z,\tau) \theta_{01}(0,\tau) + \theta_{01}(z, \tau) \theta_{00}(0, \tau)}{2} \label{eq:Tauduplication01}\end{aligned}$$ This formula is called in @CossetPhd [formula 3.13, p.39] the change of basis formula from the $\mathcal{F}_2$ basis to the $\mathcal{F}_{(n,2)^2}$ basis. However a direct proof can be obtained with limited effort, using the series defining $\theta$ and some manipulations and term reorganization akin to $$\sum_{n + m \equiv 0 \pmod{2}} q^{n^2 + m^2} = \sum_{i, j \in \mathbb{Z}} q^{(i+j)^2 + (i-j)^2} .$$ We also note that one can similarly prove the following formula, which will be used in section \[section:uniformalgorithm\]: $$\label{eq:Tauduplication10} \theta_{10}(z, 2\tau)^2 = \frac{\theta_{00}(z,\tau) \theta_{00}(0,\tau) - \theta_{01}(z,\tau) \theta_{01}(0,\tau)}{2}$$ We then define the following function: $$\begin{aligned} F : \mathbb{C}^4 & \rightarrow & \mathbb{C}^4 \\ (x,y,z,t) & \mapsto & \left( \frac{\sqrt{x} \sqrt{z} + \sqrt{y} \sqrt{t}}{2}, \frac{\sqrt{x} \sqrt{t} + \sqrt{y} \sqrt{z}}{2}, \frac{z+t}{2}, \sqrt{z}\sqrt{t} \right)\end{aligned}$$ Hence, according to Proposition \[propTauduplication0\] and \[propTauduplicationZ\], for some appropriate choice of roots we have $$F\left( \theta_{00}^2(z,\tau), \theta_{01}^2(z,\tau), \theta_{00}^2(0,\tau), \theta_{01}^2(0,\tau) \right) = \left( \theta_{00}^2(z,2\tau), \theta_{01}^2(z,2\tau), \theta_{00}^2(0,2\tau), \theta_{01}^2(0,2\tau) \right).$$ \[Remark\] One can also write rewrite $F$ using Karatsuba-like techniques $$\begin{aligned} \label{FKaratsuba} F(x,y,z,t) = && \left( \frac{(\sqrt{x}+\sqrt{y})(\sqrt{z}+\sqrt{t}) + (\sqrt{x}-\sqrt{y})(\sqrt{z}-\sqrt{t})}{4}, \right. \\ && \left. \frac{(\sqrt{x}+\sqrt{y})(\sqrt{z}+\sqrt{t}) - (\sqrt{x}-\sqrt{y})(\sqrt{z}-\sqrt{t})}{4}, \right. \notag \\ && \left. \frac{(\sqrt{z}+\sqrt{t})^2 + (\sqrt{z}-\sqrt{t})^2}{4}, \frac{(\sqrt{z}+\sqrt{t})^2 - (\sqrt{z}-\sqrt{t})^2}{4} \right) \notag\end{aligned}$$ to speed up computations. Following section \[section:AGMthetaconstants\], we define a **good choice** for square roots at the rank $n$ as the following conditions being satisfied: - ${\operatorname{Re}}(\sqrt{x_n}) \geq 0$, ${\operatorname{Re}}(\sqrt{z_n}) \geq 0$; - $|\sqrt{x_n} - \sqrt{y_n}| < |\sqrt{x_n} + \sqrt{y_n}|$, or $|\sqrt{x_n} - \sqrt{y_n}| = |\sqrt{x_n} + \sqrt{y_n}|$ and ${\operatorname{Im}}\left(\frac{\sqrt{y_n}}{\sqrt{x_n}}\right) > 0$; - $|\sqrt{z_n} - \sqrt{t_n}| < |\sqrt{z_n} + \sqrt{t_n}|$, or $|\sqrt{z_n} - \sqrt{t_n}| = |\sqrt{z_n} + \sqrt{t_n}|$ and ${\operatorname{Im}}\left(\frac{\sqrt{t_n}}{\sqrt{z_n}}\right) > 0$. The last condition is equivalent to $|z_n-t_n| \leq |z_n+t_n|$, which means that $(z_n, t_n)$ is an AGM sequence for $(z_0, t_0)$ in which all the choices of sign are good. Note that the condition $|x-y| < |x+y|$ is equivalent to ${\operatorname{Re}}\left(\frac{y}{x}\right) > 0$. Again, similarly to the AGM, for any $x,y,z,t \in \mathbb{C}$ we define the **optimal F sequence** $((x_n, y_n, z_n, t_n))_{n \in \mathbb{N}}$ as follows: $$\begin{aligned} (x_0, y_0, z_0, t_0) &=& (x,y,z,t) \\ (x_{n+1}, y_{n+1}, z_{n+1}, t_{n+1}) &=& F\left(x_n, y_n, z_n, t_n\right)\end{aligned}$$ where all the choices of sign for the square roots are good. The study of this sequence and its convergence is done in Section \[section:convergence\]. Link with theta-functions ------------------------- ### More argument reduction {#section:moreArgReduction} We go slightly further than the conditions in order to justify the forthcoming results. We wish to further reduce $z$, as follows: $$\label{eq:conditionsz} 0 \leq {\operatorname{Im}}(z) \leq \frac{{\operatorname{Im}}(\tau)}{4}, \qquad |{\operatorname{Re}}(z)| \leq \frac{1}{8}$$ The first hypothesis allows us to avoid $z = \frac{\tau+1}{2}$, which is a zero of $\theta(z,\tau)$, and hence a pole of quotients of the form $\frac{\theta_i}{\theta_{00}}$, which we consider in our algorithm much in the same way as @Dupont. We prove Lemma \[realPartsOfQuotients\] and Theorem \[goodchoicethetas\] under this assumption. The second condition complements the first one as follows: Let $z, \tau$ such that $|{\operatorname{Re}}(\tau)| \leq \frac{1}{2}$ and the conditions of are verified. Then $\frac{z}{\tau}, \frac{-1}{\tau}$ verify the first condition of . Write $$\left|{\operatorname{Im}}\left( \frac{z}{\tau} \right) \right| = \frac{1}{|\tau|^2} |{\operatorname{Im}}(z) {\operatorname{Re}}(\tau) - {\operatorname{Re}}(z) {\operatorname{Im}}(\tau)| \leq \frac{{\operatorname{Im}}(\tau)}{|\tau|^2} \left(\frac{1}{4} \frac{1}{2} + \frac{1}{8}\right) = \frac{1}{4} {\operatorname{Im}}\left(\frac{-1}{\tau}\right).$$ This will be used to apply Theorem \[goodchoicethetas\] to $\frac{z}{\tau}, \frac{-1}{\tau}$ in Proposition \[propmathfrakF\]. Note that those conditions are satisfied if one takes $z' = \frac{z}{2}$ with $z$ satisfying conditions . One can then compute $\theta_{00,01}^2(z,\tau)$ from $\theta_{00,01,10}^2(z/2,\tau)$ and $\theta_{00,01,10}^2(0,\tau)$ using the following *$z$-duplication formulas* @Mumford1 [p. 22]: $$\begin{aligned} \label{eq:Zduplication} \theta_{00}(z, \tau) \theta_{00}^3(0,\tau) &=& \theta_{01}^4(z/2, \tau) + \theta_{10}^4(z/2, \tau) \\ \theta_{01}(z, \tau) \theta_{01}^3(0,\tau) &=& \theta_{00}^4(z/2, \tau) - \theta_{10}^4(z/2, \tau) \notag \\ \theta_{10}(z, \tau) \theta_{10}^3(0,\tau) &=& \theta_{00}^4(z/2, \tau) - \theta_{01}^4(z/2, \tau). \notag\end{aligned}$$ This requires the knowledge of $\theta_{10}(z,\tau)$ and the associated theta-constant; this could be computed using Jacobi's formula (Equation ) and the equation of the variety (Equation ), but we end up using a different trick in our final algorithm. ### Good choices of sign and thetas We now prove that, for the arguments we consider, the good choices of sign correspond exactly to values of $\theta$: \[realPartsOfQuotients\] For any $\tau$ such that ${\operatorname{Im}}(\tau) \geq \operatorname{0.345}$ (in particular, for $\tau \in \mathcal{F}$) and $z$ verifying the first condition in we have $$|\theta_{00}(z,\tau) - \theta_{01}(z,\tau)| < |\theta_{00}(z,\tau) + \theta_{01}(z,\tau)|,$$ which also proves that ${\operatorname{Re}}\left(\frac{\theta_{01}(z,\tau)}{\theta_{00}(z,\tau)}\right) > 0, {\operatorname{Re}}\left(\frac{\theta_{01}(0,\tau)}{\theta_{00}(0,\tau)}\right) > 0$. Write: $$\begin{aligned} |\theta_{00}(z,\tau) + \theta_{01}(z,\tau) - 2| & \leq & 2 \sum_{n \geq 2, n \text{ even}} |q^{n^2} (w^{2n}+w^{-2n})| \\ & \leq & 2 \sum_{n \geq 2, n \text{ even}} |q|^{n^2} (1 + |q|^{-n/2}) \\ & \leq & 2 \sum_{n \geq 1} |q|^{4n^2} (1 + |q|^{-n}) \\ & \leq & 2 |q|^3 + 2 |q|^4 + \frac{2q^{16}}{1-q^{20}} + \frac{2q^{14}}{1-q^{19}} \\ |\theta_{00}(z,\tau) - \theta_{01}(z,\tau)| & \leq & 2 \sum_{n \geq 1, n \text{ odd}} |q|^{n^2} (1 + |q|^{-n/2}) \\ & \leq & 2 |q|^{1/2} + 2|q| + \frac{2q^9}{1-q^{16}} + \frac{2q^{7.5}}{1-q^{19}}\end{aligned}$$ We have $$\frac{2 |q|^{1/2} + 2|q| + \frac{2q^9}{1-q^{16}} + \frac{2q^{7.5}}{1-q^{19}}}{2 - (2 |q|^3 + 2 |q|^4 + \frac{2q^{16}}{1-q^{20}} + \frac{2q^{14}}{1-q^{19}})} \leq 1$$ for ${\operatorname{Im}}(\tau) > \operatorname{0.345}$, which proves the lemma. We are now ready to prove: \[goodchoicethetas\] Let $(x_n, y_n, z_n, t_n)$ be the optimal F sequence for $\theta_{00}^2(z,\tau), \theta_{01}^2(z,\tau), \theta_{00}^2(0,\tau), \theta_{01}^2(0,\tau)$. For any $\tau$ such that ${\operatorname{Im}}(\tau) \geq \operatorname{0.345}$ and $z$ satisfying the first condition of we have $$(x_n, y_n, z_n, t_n) = \left( \theta_{00}^2(z, 2^n\tau), \theta_{01}^2(z, 2^n \tau), \theta_{00}^2(0, 2^n \tau), \theta_{01}^2(0, 2^n \tau) \right)$$ This is true for $n=0$; we prove the statement inductively. Suppose it is true for $n=k$. We have for any $\tau$: $$\theta_{00}(0, \tau) = 1 + 2q + c, \qquad |c| \leq \frac{2|q|^4}{1-|q|^5}$$ For any $\tau$ such that ${\operatorname{Im}}(\tau) \geq \operatorname{0.345}$, $2|q| \leq 0.676$ and $|c| \leq 0.027$; hence ${\operatorname{Re}}(\theta_{00}(0,2^k \tau)) > 0$ for any $k$, which proves that $\sqrt{z_k}=\theta_{00}(0,2^k\tau)$. Lemma \[realPartsOfQuotients\] shows that ${\operatorname{Re}}\left( \frac{\theta_{01}(0,\tau)}{\theta_{00}(0,\tau)} \right) > 0$, and we also have ${\operatorname{Re}}\left( \frac{\sqrt{t_k}}{\sqrt{z_k}} \right) \geq 0$ since the choice of roots is good, hence $\sqrt{t_k}=\theta_{01}(0, 2^k\tau)$. Proposition \[propTauduplication0\] then proves that $t_{k+1}=\theta_{01}^2(0,2^{k+1}\tau)$ and $z_{k+1}=\theta_{00}^2(0, 2^{k+1} \tau)$. Similarly, given that $z$ satisfies the first condition of : $$\label{eq:estimateTheta} |\theta_{00}(z, \tau) - 1| \leq |q|^{1/2} + |q| + |q|^3 + |q|^4 + |q|^{7/2} + |q|^9 + \frac{2|q|^{14}}{1-|q|^2}$$ For ${\operatorname{Im}}(\tau) \geq \operatorname{0.345}$, this is strictly smaller than 1; hence ${\operatorname{Re}}(\theta_{00}(z,\tau)) > 0$, which proves that $\sqrt{x_k} = \theta_{00}(z, 2^k \tau)$. Again, Lemma \[realPartsOfQuotients\] proves that ${\operatorname{Re}}\left( \frac{\theta_{01}(z,2^k \tau)}{\theta_{00}(z, 2^k\tau)} \right) > 0$, and since the choice of signs is good, ${\operatorname{Re}}\left( \frac{\sqrt{y_k}}{\sqrt{x_k}} \right) \geq 0$, necessarily $\sqrt{y_k} = \theta_{01}(z, 2^k \tau)$. This along with Proposition \[propTauduplicationZ\] finishes the induction. Note that a consequence of this proposition is the following fact: \[thetaQuadraticallyConvergent\] The optimal F sequence for $\theta_{00}^2(z,\tau), \theta_{01}^2(z,\tau), \theta_{00}^2(0,\tau), \theta_{01}^2(0,\tau)$ converges quadratically to $(1,1,1,1)$. A function with quasi-optimal time evaluation --------------------------------------------- The strategy of @Dupont is to use an homogenization of the AGM to get a function $f_{\tau}:~\mathbb{C}~\rightarrow~\mathbb{C}$, on which Newton's method can be applied. To generalize this, we homogenize the function which maps to $(x,y,z,t)$ the limit of the optimal F sequence associated to them; it becomes a function from $\mathbb{C}^2$ to $\mathbb{C}^2$. We call this function $F^{\infty}$; this function is a major building block for the function we use to compute our two parameters $z, \tau$ using Newton's method. \[calcullambda\] Let $\lambda, \mu \in \mathbb{C}$. Let $((x_n, y_n, z_n, t_n))_{n \in \mathbb{N}}$ be the optimal F sequence for $(x,y,z,t)$, and $((x'_n, y'_n, z'_n, t'_n))_{n \in \mathbb{N}}$ the optimal F sequence for $(\lambda x,\lambda y,\mu z,\mu t)$. Put $\lim_{n \rightarrow \infty} z_n = z_{\infty}$ and $\lim_{n \rightarrow \infty} z'_n = z'_{\infty}$. Then we have $$\mu = \frac{z'_{\infty}}{z_{\infty}}, \qquad \qquad \lambda = \frac{ \left( \lim_{n \rightarrow \infty} \left( \frac{x'_n}{z'_{\infty}} \right)^{2^n} \right) \times z'_{\infty}}{\left( \lim_{n \rightarrow \infty} \left( \frac{x_n}{z_{\infty}} \right)^{2^n} \right) \times z_{\infty}}$$ We prove by induction that $$x'_n = \epsilon_n \lambda^{1/2^n} \mu^{1-1/2^n} x_n, \quad y'_n = \epsilon_n \lambda^{1/2^n} \mu^{1-1/2^n} y_n, \qquad z'_n = \mu z_n, \quad t'_n = \mu t_n,$$ where ${\operatorname{Re}}(\lambda^{1/2^n}) \geq 0$, ${\operatorname{Re}}(\mu^{1-1/2^n}) \geq 0$, and $\epsilon_n$ is a $2^n$-th root of unity. This is enough to prove the proposition above, since then $$\lim_{n \rightarrow \infty} \left( \frac{x'_n}{z'_{\infty}} \right)^{2^n} = \lim_{n \rightarrow \infty} \lambda \mu^{2^n-1} \left( \frac{x_n}{z'_{\infty}} \right)^{2^n} = \frac{\lambda}{\mu} \lim_{n \rightarrow \infty} \left( \frac{x_n}{z_{\infty}} \right)^{2^n}.$$ Since this is true for $n=0$, suppose this is true for $n=k$. We have $$z'_{k+1} = \frac{z'_k + t'_k}{2} = \mu z_{k+1}.$$ As for $t_{k+1}$, we can write $$\sqrt{z'_k} = \epsilon_z \sqrt{\mu} \sqrt{z_k}, \qquad \sqrt{t'_k} = \epsilon_t \sqrt{\mu} \sqrt{t_k}$$ where $\epsilon_z = \pm 1$ and $\epsilon_t = \pm 1$, and the square roots are taken with positive real part. But since ${\operatorname{Re}}\left(\frac{\sqrt{t'_k}}{\sqrt{z'_k}}\right) \geq 0$ and ${\operatorname{Re}}\left(\frac{\sqrt{t_k}}{\sqrt{z_k}} \right) \geq 0$, we have $\epsilon_z = \epsilon_t$. Hence $$t'_{k+1} = \left( \epsilon_z \sqrt{\mu} \sqrt{z_k} \right) \left( \epsilon_z \sqrt{\mu} \sqrt{t_k} \right) = \mu t_{k+1}.$$ As for the other coordinates, we have $$\sqrt{x'_k} = \epsilon_x \sqrt{\epsilon_k} \lambda^{1/2^{k+1}} \mu^{1/2-1/2^{k+1}} \sqrt{x_k}, \qquad \sqrt{y'_k} = \epsilon_y \sqrt{\epsilon_k} \lambda^{1/2^{k+1}} \mu^{1/2-1/2^{k+1}} \sqrt{y_k}$$ where the roots are taken with positive real part, and $\epsilon_x, \epsilon_y \in \{-1, 1\}$. Since ${\operatorname{Re}}\left( \frac{\sqrt{y_k}}{\sqrt{x_k}} \right) \geq 0$ and we require ${\operatorname{Re}}\left( \frac{\sqrt{y'_k}}{\sqrt{x'_k}} \right) \geq 0$, necessarily $\epsilon_x = \epsilon_y$; hence $$x'_{k+1} = \frac{\sqrt{x'_k} \sqrt{z'_k} + \sqrt{y'_k} \sqrt{t'_k}}{2} = \epsilon_{k+1} \lambda^{1/2^{k+1}} \mu^{1-1/2^{k+1}} \frac{\sqrt{x_k} \sqrt{z_k} + \sqrt{y_k} \sqrt{t_k}}{2} = \epsilon_{k+1} \lambda^{1/2^{k+1}} \mu^{1-1/2^{k+1}} x_{k+1}$$ where $\epsilon_{k+1} = \epsilon_x \sqrt{\epsilon_z}$ is indeed such that $\epsilon_{k+1}^{2^{k+1}} = 1$. This proves the proposition. In the case of theta-functions, however, we have: \[thetasPow2PowN\] $$\lim_{n \rightarrow \infty} \frac{\theta(z,2^n\tau)^{2^n}}{\theta(0,2^n\tau)^{2^n}} = 1$$ It is enough to prove $\lim_{n \rightarrow \infty} \theta(z,2^n\tau)^{2^n} = 1$, since it also covers the case $z=0$. Write, like Equation : $$\theta(z, 2^n\tau) = 1 + q^{2^n}(w^2+w^{-2}) + c, \qquad |c| \leq \frac{2|q|^{2^n+3}}{1-|q|}$$ We can write $\theta(z,2^n\tau) = 1 + d_n$ with $|d_n| \leq 2 |q|^{2^n}|w^2+w^{-2}|$. We then have classically $$|\theta(z,2^n\tau)^{2^n} - 1| \sim |2^n d_n|$$ and since $\lim_{n \rightarrow \infty} 2^n |q|^{2^n} = 0$, this proves the proposition. Combining this with Theorems \[calcullambda\] and \[goodchoicethetas\] proves that, for $(x_n,y_n,z_n,t_n)$ as in Theorem \[goodchoicethetas\], we have $$\lambda = \lim_{n \rightarrow \infty} \left( \frac{x'_n}{\mu} \right)^{2^n} \times \mu.$$ In particular, if we define the following function: $$\begin{aligned} F^{\infty} : \mathbb{C}^4 & \rightarrow & \mathbb{C}^2 \\ (x, y, z, t) & \mapsto & \left(\left( \lim_{n \rightarrow \infty} \left( \frac{x_n}{z_{\infty} } \right)^{2^n} \right) \times z_{\infty}, z_{\infty} \right)\end{aligned}$$ where $z_{\infty} = \lim_{n \rightarrow \infty} z_n$, then we have that, for any $z, \tau$ satisfying the hypotheses of Theorem \[goodchoicethetas\], $$F^{\infty}\left(\lambda \theta_{00}^2(z,\tau), \lambda \theta_{01}^2(z,\tau), \mu \theta_{00}^2(0,\tau), \mu \theta_{01}^2(0,\tau) \right) = (\lambda, \mu).$$ For instance, $$\label{eq:OurAGMQuotients} F^{\infty}\left(1, \frac{\theta_{01}^2(z,\tau)}{\theta_{00}^2(z,\tau)} , 1, \frac{\theta_{01}^2(0,\tau)}{\theta_{00}^2(0,\tau)} \right) = \left( \frac{1}{\theta_{00}^2(z,\tau)}, \frac{1}{\theta_{00}^2(0,\tau)} \right).$$ This is similar to Equation , and will play a similar role in the computation of $\theta(z,\tau)$. Convergence {#section:convergence} ----------- Let us start by showing that, contrary to the AGM and despite Proposition \[thetaQuadraticallyConvergent\], an optimal F sequence does not always converge quadratically; for instance, the optimal F sequence for $(2,2,1,1)$ is $((2^{1/2^n}, 2^{1/2^n}, 1, 1))_{n \in \mathbb{N}}$, which does not converge quadratically. This is a big difference from the AGM, and this is why we are reluctant to call optimal F sequences a "generalization of the AGM". However, we now show that the sequence $(\lambda_n) = \left(\left(\frac{x_n}{z_{\infty}}\right)^{2^n} \times z_{\infty} \right)_{n \in \mathbb{N}}$ converges quadratically, whence $F^{\infty}$ can be computed in $O(\mathcal{M}(P) \log P)$ bit operations. In all that follows, we take $C > 1$ such that $|x_0|, |y_0|, |z_0|, |t_0| \leq C$. Note that the equations defining $F$ can then be used to prove inductively that $$\forall n \in \mathbb{N}, |x_n|, |y_n|, |z_n|, |t_n| \leq C.$$ We prove in Section \[section:proveAllHypo\] that there is a suitable $C$ for any $z, \tau$ we consider in our final algorithm. We also have a lower bound: There exists $\epsilon, n_0$ such that for all $n \geq n_0$, $|x_n|, |y_n|, |z_n|, |t_n| \geq \epsilon$. Note that @Cox [Prop 2.1] proves that $|z_n|, |t_n| \geq c$, with $c=\frac{2}{\pi} \min(|z_0|, |t_0|)$. Suppose $|x_n|, |y_n|, |z_n|, |t_n| \geq \delta > 0$, and write $$|\sqrt{x_n}+\sqrt{y_n}|^2 = 2|\sqrt{x_n}|^2 + 2|\sqrt{y_n}|^2 - |\sqrt{x_n}-\sqrt{y_n}|^2.$$ Using $|\sqrt{x_n}-\sqrt{y_n}| \leq |\sqrt{x_n}+\sqrt{y_n}|$, which comes the fact that choices of square roots are good, we derive the two following lower bounds. $$\begin{aligned} |\sqrt{x_n}+\sqrt{y_n}| &\geq \sqrt{ 2|\sqrt{x_n}|^2 + 2|\sqrt{y_n}|^2 - |x_n-y_n|}, \\ & \geq 2 \sqrt{\delta} \sqrt{1-\frac{|x_n-y_n|}{4 \delta}},\\ \llap{and } |\sqrt{x_n}+\sqrt{y_n}|^2 &\geq { 2|\sqrt{x_n}|^2 + 2|\sqrt{y_n}|^2 - |\sqrt{x_n}+\sqrt{y_n}|^2},\\ |\sqrt{x_n}+\sqrt{y_n}|^2 &\geq { |\sqrt{x_n}|^2 + |\sqrt{y_n}|^2} \geq 2\delta.\end{aligned}$$ Using the same arguments, we obtain: $$\begin{aligned} |\sqrt{z_n}+\sqrt{t_n}| &\geq 2 \sqrt{c} \sqrt{1 - \frac{|z_n-t_n|}{4 c}},\\ |\sqrt{z_n}+\sqrt{t_n}| &\geq \sqrt{2c}.\end{aligned}$$ We then have $$\begin{aligned} |\sqrt{x_n}-\sqrt{y_n}| & \leq \frac{|x_n-y_n|}{|\sqrt{x_n}+\sqrt{y_n}|} \leq \frac{|x_n-y_n|}{\sqrt{2 \delta} }, \\ |\sqrt{z_n}-\sqrt{t_n}| & \leq \frac{|z_n-t_n|}{|\sqrt{z_n}+\sqrt{t_n}|} \leq \frac{|z_n-t_n|}{\sqrt{2 c} }\end{aligned}$$ which we use along with Equation \[FKaratsuba\] to write: $$|x_{n+1}| \geq \sqrt{\delta} \sqrt{c} \sqrt{\left( 1-\frac{|x_n-y_n|}{4 \delta} \right) \left( 1 - \frac{|z_n-t_n|}{4 c} \right)} - \frac{|x_n-y_n||z_n-t_n|}{8 \sqrt{\delta} \sqrt{c} }$$ Now, using only @Cox [Prop 2.1] and Equation \[FKaratsuba\], we can write $$|x_{n+1}-y_{n+1}| = \frac{|\sqrt{x_n}-\sqrt{y_n}| |\sqrt{z_n} - \sqrt{t_n}|}{2} \leq \sqrt{\frac{C}{2c}} |z_n-t_n|$$ which proves that $(|x_n-y_n|)$ converges quadratically to 0; we thus have $|x_n - y_n| \leq C_n \frac{\delta}{2^{2^n}}$, $|z_n - t_n| \leq C'_n \frac{c}{2^{2^n}}$ with $C_n, C'_n = o(2^{2^n})$. This gives $$|x_{n+1}| \geq \sqrt{\delta} \sqrt{c} \left( \sqrt{\left( 1-\frac{C_n}{2^{2^n+2}} \right) \left( 1 - \frac{C'_n}{2^{2^n+2}} \right)} - \frac{C_n}{2^{2^n+3}} \frac{C'_n}{2^{2^n+3}} \right)$$ Finally, supposing that $c > \delta$, we get that $|x_n| \geq \delta \Rightarrow |x_{n+1}| \geq \delta \epsilon_n$; since $(\epsilon_n)$ converges to 1 quadratically, $\prod_{k \geq n} \epsilon_n$ converges to $\epsilon > 0$, which proves that $|x_{n+k}| \geq \epsilon \delta$ for all $k$. We now prove that $(\lambda_n) = \left(\left(\frac{x_n}{z_{\infty}}\right)^{2^n} \times z_{\infty} \right)_{n \in \mathbb{N}}$ converges quadratically, by proving the following theorem: \[thmconvergence\] The sequence $(\lambda_n)$ converges, to a limit $\lambda$. Furthermore, for $P$ large enough, there exists a constant $c_1 > 0$, depending on $C, \epsilon$ and $|\lambda|$, such that, if $k$ is the first integer such that $|z_k - t_k| \leq 2^{-P-k-c_1}$, then $\lambda_{k+1}$ is an approximation of $\lambda$ with absolute precision $P$ bits. The point here is that once $z_n$ and $t_n$ are close enough, $x_{n+1}$ and $y_{n+1}$ are also close and the value of $\lambda_n$ does not change much after that. Let $c_1 \geq 0$, and take $n$ the first integer for which $|z_n - t_n| \leq \eta$ with $\eta = 2^{-P - c_1 - n}$. We then have for all $k \geq 0$ @Dupont [Theorem 1]: $$|z_{n+k} - t_{n+k} | \leq A^{2^k-1} \eta^{2^k}$$ with $A = \frac{\pi}{8 \min(|z_0|, |t_0|)}$. Furthermore, $|z_{n+1}-z_n| = \frac{1}{2} |z_n - t_n|$, so that $$|z_{\infty} - z_{n+k}| \leq \frac{1}{2} \sum_{i=k}^{\infty} A^{2^i-1} \eta^{2^i}$$ and we have $|z_{\infty} - z_{n+k}| \leq \frac{1}{A} \left(A \eta \right)^{2^k}$. Finally, using Equation , one can write $$\begin{aligned} |x_{n+k+1}-y_{n+k+1}| & \leq & \frac{|\sqrt{x_n}-\sqrt{y_n}||\sqrt{z_n}-\sqrt{t_n}|}{2} \\ & \leq & \sqrt{C} \sqrt{2} \sqrt{|z_{n+k+1}-t_{n+1}|} \text{ \qquad since $z_{n+k+1}-t_{n+k+1} = \frac{(\sqrt{z_{n+k}}-\sqrt{t_{n+k}})^2}{2}$ } \\ & \leq & \sqrt{2AC} |z_{n+k} - t_{n+k}|.\end{aligned}$$ Now, define $q_n = \frac{(x_n/z_{\infty})^2}{x_{n-1}/z_{\infty}}$, so that $\frac{\lambda_{n+1}}{\lambda_n} = q_n^{2^n}$. Note that if one makes the approximation $x_{n+k+1} = y_{n+k+1}$ and $z_{n+k+1} = t_{n+k+1} = z_{\infty}$, we have $x_{n+k+2} = \sqrt{x_{n+k+1} z_{\infty}}$ which gives $q_{n+k+2} = 1$. We take a closer look at those approximations: $$\begin{aligned} |x_{n+k+2} - \sqrt{x_{n+k+1}} \sqrt{z_{n+k+1}}| & \leq & \frac{|\sqrt{y_{n+k+1}}-\sqrt{x_{n+k+1}}| |\sqrt{z_{n+k+1}}+\sqrt{t_{n+k+1}}|}{4} \\ && + \frac{|\sqrt{y_{n+k+1}}+\sqrt{x_{n+k+1}}| |\sqrt{z_{n+k+1}}-\sqrt{t_{n+k+1}}|}{4} \\ & \leq & \frac{\sqrt{C}}{2} (|\sqrt{y_{n+k+1}}-\sqrt{x_{n+k+1}}| + |\sqrt{z_{n+k+1}}-\sqrt{t_{n+k+1}}|) \\ & \leq & \frac{\sqrt{C}}{2} \left( \frac{\sqrt{2AC}}{|\sqrt{x_{n+k}}+\sqrt{y_{n+k}}|} |z_{n+k}-t_{n+k}| + \sqrt{2A} |z_{n+k+1}-t_{n+k+1} | \right) \\ & \leq & C' (A \eta)^{2^k}\end{aligned}$$ so $$\begin{aligned} q_{n+k+2} - 1 &=& \frac{(x_{n+k+2}/z_{\infty})^2 - x_{n+k+1}/z_{\infty}}{x_{n+k+1}/z_{\infty}} \\ & \leq & \frac{\frac{1}{z_{\infty}^2} (\sqrt{x_{n+k+1}} \sqrt{z_{n+k+1}} + C'(A \eta)^{2^k})^2 - x_{n+k+1}/z_{\infty}}{x_{n+k+1}/z_{\infty}} \\ & \leq & \frac{x_{n+k+1} z_{n+k+1}/z_{\infty}^2 - x_{n+k+1} / z_{\infty}}{x_{n+k+1}/z_{\infty}} + \frac{2C/z_{\infty}^2 C'(A \eta)^{2^k} + C'^2 (A \eta)^{2^{k+1}}}{x_{n+k+1}/z_{\infty}} \\ & \leq & \frac{1}{2 z_{\infty}} \sum_{i=k+1}^{\infty} (A \eta)^{2^i} + \frac{C C'(A \eta)^{2^k}}{x_{n+k+1} z_{\infty}} + \frac{C'^2 (A \eta)^{2^{k+1}}}{x_{n+k+1}/z_{\infty}} \\ & \leq & c \times (A \eta)^{2^k}\end{aligned}$$ This proves that $(q_n)$ converges quadratically to 1; using the equivalent $q_n^{2^n} - 1 \sim 2^n q_n$, we have that $(q_n^{2^n})$ also converges quadratically to 1, which proves the convergence of the sequence $(\lambda_n)$. Finally we have $$\begin{aligned} q_{n+2}^{2^{n+2}} ... q_{n+k}^{2^{n+k}} - 1 &\leq & \prod_{i=0}^{k-2} \left(1+ c (A\eta)^{2^i}\right)^{2^{n+i+2}} - 1 \\ & < & \exp\left(4 c \sum_{i=0}^{k-2} 2^{n+i} (A \eta)^{2^i}\right) -1 \\ & \leq & \frac{4 c \sum_{i=0}^{k-2} 2^{n+i} (A\eta)^{2^i}}{1-(4 c \sum_{i=0}^{k-2} 2^{n+i} (A \eta)^{2^i})/2}\end{aligned}$$ which proves, for $P$ large enough, $$\begin{aligned} |\lambda - \lambda_{n+1}| & \leq & 8 c |\lambda_{n+1}| \sum_{i=0}^{\infty} 2^{n+i} (A\eta)^{2^i} \\ & \leq & 16 c |\lambda_{n+1}| A \eta 2^n \\ & \leq & 16 A c |\lambda_{n+1}| 2^{-c_1} \times 2^{-P}\end{aligned}$$ This inequality proves that, at least for $P$ large enough, $|\lambda_{n+1}| \leq 2 |\lambda|$. Hence if we suppose $\log_2(32 A c |\lambda|) \leq c_1$, we have that $\lambda_{n+1}$ is an approximation of $\lambda$ with $P$ bits of absolute precision. \[1\] Work at precision $\mathcal{P}$. $n \gets 0$ $n \gets n+1$ $(x,y,z,t) \gets F(x,y,z,t)$ $(x,y,z,t) \gets F(x,y,z,t)$ Return $\left( \left( \frac{x}{z} \right)^{2^{n+1}} \times z, z \right)$ This gives an algorithm, Algorithm \[Finfty\], to compute $F^{\infty}(x,y,z,t)$. According to @Dupont [Theorem 12], if $n = \max( \log |\log| z_0/t_0||, 1) + \log(P+c_1)$, $a_n$ is an approximation of $\operatorname{AGM}\left(1, |\frac{z_0}{t_0}|\right)$ with relative precision $P$ bits. This proves that at the end of the algorithm, $n = O(\log P)$; in fact, we have more precisely $n \leq \log_2 P + C''$ with $C''$ a constant independent of $P$. Finally in the next subsection proves that one can take $\mathcal{P} = P + O(\log P)$, which means that this algorithm computes $F^{\infty}$ in $O(\mathcal{M}(P) \log P)$ bit operations. Loss of precision {#section:Finftybitslost} ----------------- We use Theorem \[theoremlossofprec\] in order to evaluate the precision lost when computing $F^{\infty}(x,y,z,t)$. First note that the upper and lower bounds on the terms of the sequence allow us to write $$\begin{aligned} \left(\frac{1}{\sqrt{|z_n|}} + \frac{1}{\sqrt{|t_n|}}\right) \left(\sqrt{|z_n|} + \sqrt{|t_n|}\right) & \leq & b/2 \\ \left(\frac{1}{\sqrt{|z_n|}} + \frac{1}{\sqrt{|t_n|}}\right) \left(\sqrt{|x_n|} + \sqrt{|y_n|}\right) & \leq & b \\ \left(\frac{1}{\sqrt{|x_n|}} + \frac{1}{\sqrt{|y_n|}}\right) \left(\sqrt{|z_n|} + \sqrt{|t_n|}\right) & \leq & b\end{aligned}$$ for some $b >1$; for instance, one can take $b = \max\left(1, 4 \sqrt{\frac{C}{\epsilon}}\right)$. We prove in Section \[section:proveAllHypo\] the existence of $\epsilon$ and $C$, and hence of $b$, for any values of theta we consider as arguments. We first evaluate a bound on the error incurred when computing $F$ using Equation . Using those formulas allows us to get error bounds that are identical for $F_x$ and $F_y$, and $F_z$ and $F_t$. For simplicity, we assume that the error on $z$ and $t$ is the same, as well as the error on $x$ and $y$. This gives: $$\begin{aligned} |{\operatorname{Re}}(F_x) - {\operatorname{Re}}(\tilde{F_x})| & \leq & \left(1 + k_z \left(\frac{1}{\sqrt{|z|}} + \frac{1}{\sqrt{|t|}}\right) \left(\sqrt{|x|} + \sqrt{|y|}\right) + k_x\left(\frac{1}{\sqrt{|x|}} + \frac{1}{\sqrt{|y|}}\right) \left(\sqrt{|z|} + \sqrt{|t|} \right) \right) 2^{-P} \\ |{\operatorname{Re}}(F_z) - {\operatorname{Re}}(\tilde{F_z})| & \leq & \left(1 + 2 k_z \left(\frac{1}{\sqrt{|z|}} + \frac{1}{\sqrt{|t|}} \right) \left(\sqrt{|z|} + \sqrt{|t|} \right) \right) 2^{-P}\end{aligned}$$ We thus get the following induction relations when looking at what happens when applying $F$ $n$ times in a row: $$k^{(n)}_x \leq 1 + b k^{(n-1)}_z + b k^{(n-1)}_x, \qquad k^{(n)}_z \leq 1 + b k^{(n-1)}_z$$ The last equation rewrites as $k^{(n)}_z + \frac{1}{b-1} \leq b\left(k^{(n-1)}_z + \frac{1}{b-1}\right)$, which gives $k^{(n)}_z \leq b^n\left(k_z+\frac{1}{b-1}\right)$. The induction for $x$ becomes $k^{(n)}_x \leq 1 + (k_z + \frac{1}{b-1}) b^n + b k^{(n-1)}_x$, which we solve: $$k^{(n)}_x \leq (1+b+...+b^n)k_x + nb^n \left(k_z + \frac{1}{b-1}\right) \leq b^n\left( nk_z + \frac{b+n}{b-1} \right)$$ For $b>1$, we have for $n$ large enough that $k^{(n)} \leq 2b^{2n}$, which ultimately means the number of bits lost when applying $F$ $n$ times in a row is bounded
{'source': 'arXiv_out/1511'}