On the Computational Complexity of Modular Symbols

DOI10.2307/2153219MaRDI QIDQ4024693zbMATH OpenOpenAlexFDO

Publication date 10 February 1993

Full work available at URL https://doi.org/10.2307/2153219

computation of modular symbols fast algorithms geodesic lines period integrals polynomial time algorithms

Special values of automorphic (L)-series, periods of automorphic forms, cohomology, modular symbols (11F67) Number-theoretic algorithms; complexity (11Y16)

Review text

Let \(\Gamma\) be a congruence subgroup of \(SL(2,\mathbb{Z})\) such that the compact Riemann surface \(X=\Gamma\backslash H\cup\{i\infty\}\cup\mathbb{Q}\) has genus \(>0\). \((H\)=upper half-plane, \(\mathbb{Q}\)=rationals.) Let \(f(z)\) be a modular cusp from of weight 2 on \(\Gamma\). For \(\alpha,\beta\in\mathbb{Q}\cup\{i\infty\}\) let \(\{\alpha,\beta\}_ \Gamma\) denote the geodesic joining \(\alpha\) to \(\beta\). ``Modular symbols are period integrals \((*)\) \(2\pi i\int f(z) dz\), with path of integration \(\{\alpha,\beta\}_ \Gamma\). According to the author, his aim is ``to provide fast algorithms for the computation of modular symbols, such computations being ``necessary, for example, in the verification of the Taniyama-Weil conjecture. The author introduces the ``height function \(h\) on \(\mathbb{Q}\) by putting \(h(a/b)=\max(| a|,| b|)\), where \(a/b\in\mathbb{Q}\), \((a,b)=1\), and extends \(h\) to \(\mathbb{Q}(i)\cup\{i\infty\}\) by defining \(h(i\infty)=0\) and \(h(\alpha+i\beta)=\max(h(\alpha),h(\beta))\) for \(\alpha,\beta\in\mathbb{Q}\). An ``arithmetic operation on \(\mathbb{Q}(i)\) denotes an exact arithmetic operation on \(\mathbb{Q}(i)\) of the type \(\alpha\pm\beta\), \(\alpha\cdot\beta\) or \(\alpha/\beta\). Given a complex valued function \(F\) on \((\mathbb{Q}\cup\{i\infty\})^ 2\) and \(\alpha,\beta\in\mathbb{Q}\cup\{i\infty\}\), the author employs the phrase \(``F(\alpha,\beta)\) can be computed to within an error \(\varepsilon\) (\(>0\)) to mean that after a finite number of arithmetic operations the machine can find \(c\in\mathbb{Q}(i)\) such that \(| F(\alpha,\beta)- c|<\varepsilon\). Specializing to the case of the Hecke congruence group \(\Gamma_ 0(N)\), he proves two theorems. Theorem 1. Put \(X_ 0(N)=\Gamma_ 0(N)\backslash H\cup\mathbb{Q}\cup\{i\infty\}\). Let \(f(z)\) be a cusp form of weight 2 on \(\Gamma_ 0(N)\), with known Fourier coefficients, such that \(f\) is an eigenfunction of the Hecke operators \(Tp\), for prime \(p\), \(p\nmid N\). Let \(\{\alpha,\beta\}_{\Gamma_ 0(N)}\) be a geodesic on \(X_ 0(N)\) of height \(H=\max(h(\alpha),h(\beta))\). Fix \(\varepsilon>0\) and \(\rho\geq 0\). Then there exists \(c=c(\varepsilon)>0\) such that for squarefree \(N>c\), the modular symbol \((*)\), integrated over \(\{\alpha,\beta\}_{\Gamma_ 0(N)}\), may be computed to within an error \(\exp\{(- N^{\rho+\varepsilon/2})\log H\}\) in at most \(N^{1+\rho+\varepsilon}(\log H)\) exact arithmetic operations. Theorem 2. Let \(f(z)\) and \(\{\alpha,\beta\}_{\Gamma_ 0(N)}\) be as in Theorem 1, with the additional assumption that the Fourier coefficients of \(f(z)\) are in \(\mathbb{Q}\). Fix \(\varepsilon>0\). Then there exists a constant \(c=c(\varepsilon)>0\) such that for squarefree \(N>c\), the modular symbol \((*)\) may be computed exactly in at most \(N^{2+\varepsilon}\log H\) exact arithmetic operations.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: On the Computational Complexity of Modular Symbols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4024693)