On the Computational Complexity of Modular Symbols (Q4024693)

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.