math.NA — Numerical Analysis

A polynomial-time algorithm to compute Theta functions of Schottky groups

Contributed by Marc Masdeu

Abelian integrals, holomorphic differentials, period matrices and the Schottky--Klein prime function of a Riemann surface uniformized by a classical Schottky group are given by Poincar\'e theta series, which are sums over the elements of a free group. The algorithms that evaluate these series sum a truncated, possibly adaptively pruned, portion of the Cayley tree of the group, and the number of terms needed grows exponentially with the number of correct digits. We observe that the sum over all group elements starting with a fixed generator is a holomorphic function on the complement of a disc, and that these functions satisfy an exact linear functional equation coming from the self-similarity of the Cayley tree, given by a transfer operator built from the generators. Representing them by truncated Taylor expansions turns the evaluation of the series into a finite-dimensional linear problem, which we solve iteratively. The resulting algorithm computes the integrals $\Omega_n$, the period matrix and the prime function to $P$ bits of precision; for a fixed Schottky datum the number of arithmetic operations is cubic in $P$ and in the genus. We prove that it converges geometrically under a standard Schottky-type hypothesis on the group, which is closely related to the absolute convergence of the series. Along the way we give a complete proof of the cross-ratio formula for the period matrix, including a term that is missing from one version of it in the literature. We compare with the existing algorithms, and illustrate the method by reproducing a published value of the prime function and computing it to $30$ digits, and by computing period matrices of genus up to six to about $25$ digits.