︠edaf3607-40cc-4a19-b2e2-cd24f5aab7c4i︠
%html
<h1 style="text-align: center;">Computer Methods for Classical Modular Forms</h1>
<h2 style="text-align: center;">Sage Days 20.25 talk (March 23, 2010)</h2>
<h2 style="text-align: center;">William Stein, University of Washington</h2>
<p style="text-align: center;"><img src="modforms.png" alt="" /></p>
<p style="text-align: center;">(see <a href="http://8tb.us/home/boothby/cover/samples/" target="_new">http://8tb.us/home/boothby/cover/samples/</a> for more)</p>

<p><strong>Project: </strong>Include code in Sage for computing pictures as above for any modular form.</p>

︡eec186bd-9aa2-4509-83c4-ed7435942685︡{"html": "<h1 style=\"text-align: center;\">Computer Methods for Classical Modular Forms</h1>\r\n<h2 style=\"text-align: center;\">Sage Days 20.25 talk (March 23, 2010)</h2>\r\n<h2 style=\"text-align: center;\">William Stein, University of Washington</h2>\r\n<p style=\"text-align: center;\"><img src=\"modforms.png\" alt=\"\" /></p>\r\n<p style=\"text-align: center;\">(see <a href=\"http://8tb.us/home/boothby/cover/samples/\" target=\"_new\">http://8tb.us/home/boothby/cover/samples/</a> for more)</p>\r\n\r\n<p><strong>Project: </strong>Include code in Sage for computing pictures as above for any modular form.</p>"}︡
︠765ed1c2-6045-4d0f-a093-bdacab323207i︠
%html
<p>This talk is mainly about approaches to solving the following:</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<strong> PROBLEM</strong>:</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Compute the Hecke module $M_k(N,\varepsilon)$ for $k\geq 2$ an<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; integer, and $\varepsilon:(\ZZ/N\ZZ)^* \to \CC^*$ a Dirichlet<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; character.</p>
<p>(We are also interested in $M_k(\Gamma_H(N))$, and many other related spaces,<br />but will focus this talk mostly on the above problem.)</p>
<p><br /><br /><strong>Practical Complexity: </strong>For <em>this</em> talk, I mostly only care about <em>"practical complexity</em>", so<br />constants and real-world implementations matter a lot.&nbsp; Thus on<br />practical problems, an exponential time algorithm that completes in<br />100 hours is far more "practical" than a polynomial time algorithm that would<br />take years to finish (... implementing).</p>
<p>&nbsp;</p>

︡e14879b1-8c54-45a7-afab-f604c0e7d943︡{"html": "<p>This talk is mainly about approaches to solving the following:</p>\r\n<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<strong> PROBLEM</strong>:</p>\r\n<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Compute the Hecke module $M_k(N,\\varepsilon)$ for $k\\geq 2$ an<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; integer, and $\\varepsilon:(\\ZZ/N\\ZZ)^* \\to \\CC^*$ a Dirichlet<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; character.</p>\r\n<p>(We are also interested in $M_k(\\Gamma_H(N))$, and many other related spaces,<br />but will focus this talk mostly on the above problem.)</p>\r\n<p><br /><br /><strong>Practical Complexity: </strong>For <em>this</em> talk, I mostly only care about <em>\"practical complexity</em>\", so<br />constants and real-world implementations matter a lot.&nbsp; Thus on<br />practical problems, an exponential time algorithm that completes in<br />100 hours is far more \"practical\" than a polynomial time algorithm that would<br />take years to finish (... implementing).</p>\r\n<p>&nbsp;</p>"}︡
︠209e3f25-7a89-4fcc-ae14-1e56169a87abi︠
%html
<p><strong>Acknowledgement:</strong> "Practical" also means <em><strong>open</strong></em> -- you get to look at the code, can change anything, etc.&nbsp; Everything I'll show you in this talk today is open source and freely available in any recent copy of Sage... thanks to the hard work of:</p>
<ul>
<li>Jordi Quer</li>
<li>David Loeffler</li>
<li>Craig Citro</li>
<li>Alex Ghitza</li>
<li>John Cremona</li>
<li>Jon Bober</li>
<li>Robert Bradshaw</li>
<li>Robert Miller</li>
<li>Jen Balakrishnan</li>
<li>me</li>
<li>... and many, many others</li>
</ul>

︡8437bd8c-0f17-4236-ae99-5b2a299cad34︡{"html": "<p><strong>Acknowledgement:</strong> \"Practical\" also means <em><strong>open</strong></em> -- you get to look at the code, can change anything, etc.&nbsp; Everything I'll show you in this talk today is open source and freely available in any recent copy of Sage... thanks to the hard work of:</p>\r\n<ul>\r\n<li>Jordi Quer</li>\r\n<li>David Loeffler</li>\r\n<li>Craig Citro</li>\r\n<li>Alex Ghitza</li>\r\n<li>John Cremona</li>\r\n<li>Jon Bober</li>\r\n<li>Robert Bradshaw</li>\r\n<li>Robert Miller</li>\r\n<li>Jen Balakrishnan</li>\r\n<li>me</li>\r\n<li>... and many, many others</li>\r\n</ul>"}︡
︠204e0e39-ce44-4f84-94bc-91396e39b4cei︠
%html
<p><em><strong>Notation for </strong></em><em><strong>Dirichlet characters</strong></em>:&nbsp; We represent a character by giving the images of <em>"canonical"</em> generators for $(\ZZ/N\ZZ)^*$, which are minimal at each cyclic prime power factor.</p>

︡31f47dba-43d7-46a8-aa96-b8702d919284︡{"html": "<p><em><strong>Notation for </strong></em><em><strong>Dirichlet characters</strong></em>:&nbsp; We represent a character by giving the images of <em>\"canonical\"</em> generators for $(\\ZZ/N\\ZZ)^*$, which are minimal at each cyclic prime power factor.</p>"}︡
︠adda4d0d-4609-424f-bde7-6f17f558894f︠
G = DirichletGroup(4*5)
G.unit_gens()
︡53fa7a71-e053-43f0-887f-ed65a2447974︡{"stdout": "[11, 17]"}︡
︠4e1e7f83-a0f9-4032-8b6d-847571386698︠
show(list(G))
︡4250cf07-c06d-4126-a878-de091f2500a6︡{"html": "<div class=\"math\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[\\left[1, 1\\right], \\left[-1, 1\\right], \\left[1, \\zeta_{4}\\right], \\left[-1, \\zeta_{4}\\right], \\left[1, -1\\right], \\left[-1, -1\\right], \\left[1, -\\zeta_{4}\\right], \\left[-1, -\\zeta_{4}\\right]\\right]</div>"}︡
︠c6202dc5-8d16-40c4-ab8a-48a162772bf6i︠
%html
<h1 style="text-align: center;">The Dimension</h1>
<ol>
<li>Dimension formula for any $N,k, \varepsilon$, with $k\geq 2$.&nbsp;&nbsp; Proofs start with Riemann-Hurwitz and get complicated.</li>
<li>General formulas in Cohen-Oesterle, but with <em><strong>no proofs</strong></em>. Jordi Quer finally gave proofs in around 2007 when he visited Seattle to work on Sage.</li>
<li>Dimension formulas incredibly useful double checks on all other algorithms...</li>
<li>Computing dimension for $k=1$ is comparably much harder.</li>
</ol>

︡b0d160ee-beaa-4520-80a2-63ee0e93b8fb︡{"html": "<h1 style=\"text-align: center;\">The Dimension</h1>\r\n<ol>\r\n<li>Dimension formula for any $N,k, \\varepsilon$, with $k\\geq 2$.&nbsp;&nbsp; Proofs start with Riemann-Hurwitz and get complicated.</li>\r\n<li>General formulas in Cohen-Oesterle, but with <em><strong>no proofs</strong></em>. Jordi Quer finally gave proofs in around 2007 when he visited Seattle to work on Sage.</li>\r\n<li>Dimension formulas incredibly useful double checks on all other algorithms...</li>\r\n<li>Computing dimension for $k=1$ is comparably much harder.</li>\r\n</ol>"}︡
︠c8b33712-0948-403e-a3b5-7b78a096c188︠
@interact
def f(N=(13,(1..500)), k=(2..100)):
    for e in DirichletGroup(N).galois_orbits():
        eps = e[0]
        html("dim $M_{%s}(%s,%s) = %s$"%(k,N,latex(eps),
                             dimension_modular_forms(eps,k)))
    html("<br><hr>")                         
    for e in DirichletGroup(N).galois_orbits():
        eps = e[0]
        html("dim $S_{%s}(%s,%s) = %s$"%(k,N,latex(eps),
                             dimension_cusp_forms(eps,k)))
︡56ea9e36-d74c-4029-bd79-efe50fed2fe6︡︡
︠c7a8bbd4-5855-471b-a597-33471471ebe9i︠
%html
<h1 style="text-align: center;">Two Subproblems:&nbsp;</h1>
<h2 style="text-align: center;">Modular Forms = Eisenstein Subspace $\bigoplus$ Cuspidal Subspace</h2>

︡979f19ae-0dd8-4c66-84a1-9a8cf6418b68︡{"html": "<h1 style=\"text-align: center;\">Two Subproblems:&nbsp;</h1>\r\n<h2 style=\"text-align: center;\">Modular Forms = Eisenstein Subspace $\\bigoplus$ Cuspidal Subspace</h2>"}︡
︠6c499f0b-5913-45dd-9203-23d19e255c59i︠
%html
<h1 style="text-align: center;">Eisenstein Series</h1>
<ul>
<li>There is an explicit easy-to-compute direct formula for a basis of $q$-expansions for ${\rm Eis}_k(N,\varepsilon)$, which one can deduce by staring at Miyake's book on Modular Forms long enough.</li>
</ul>

︡cb7e0f0e-5376-4063-a770-1c56d9e0ad12︡{"html": "<h1 style=\"text-align: center;\">Eisenstein Series</h1>\r\n<ul>\r\n<li>There is an explicit easy-to-compute direct formula for a basis of $q$-expansions for ${\\rm Eis}_k(N,\\varepsilon)$, which one can deduce by staring at Miyake's book on Modular Forms long enough.</li>\r\n</ul>"}︡
︠c5a8301a-7ce3-46ce-ba13-4108dd900488i︠
%html
<h2><strong>The formulas:</strong></h2>
<p>Suppose $\chi$ and $\psi$ are primitive Dirichlet characters with conductors $L$ and $R$, respectively.   Let $$  E_{k,\chi,\psi}(q) = c_0 + \sum_{m \geq 1} \left(                   \sum_{n|m} \psi(n) \cdot \chi(m/n) \cdot n^{k-1}\right) q^{m} \in \QQ(\chi, \psi)[[q]], $$ where  $$ c_0 = \begin{cases} 0 &amp; {\rm if }\,\,\, L&gt;1, \\ - \frac{B_{k,\psi}}{2k} &amp; {\rm if }\,\,\, L=1. \end{cases} $$</p>

<h2><strong>Theorem</strong> (Miyake, Chapter 7):</h2>
<p>Suppose $t$ is a positive integer and $\chi$, $\psi$ are as above and that $k$ is a positive integer such that $\chi(-1)\psi(-1) = (-1)^k$. Except when $k=2$ and $\chi=\psi=1$, the power series  $E_{k,\chi,\psi}(q^t)$ defines an element of  $M_k(RLt,\chi \psi)$. If $\chi=\psi=1$, $k=2$, $t&gt;1$,  and $E_2(q) = E_{k,\chi,\psi}(q)$, then  $E_2(q) - t E_2(q^t)$ is a modular form in $M_2(\Gamma_0(t))$.</p>
<p>Moreover, the set of Eisenstein series in $M_k(N, \varepsilon)$ above with $RLt \mid N$ and $\chi \psi = \varepsilon$   form a basis for the   Eisenstein subspace ${\rm Eis}_k(N,\varepsilon)$.</p>

︡5b102166-421a-422b-9ba2-a1eab405257f︡{"html": "<h2><strong>The formulas:</strong></h2>\r\n<p>Suppose $\\chi$ and $\\psi$ are primitive Dirichlet characters with conductors $L$ and $R$, respectively.   Let $$  E_{k,\\chi,\\psi}(q) = c_0 + \\sum_{m \\geq 1} \\left(                   \\sum_{n|m} \\psi(n) \\cdot \\chi(m/n) \\cdot n^{k-1}\\right) q^{m} \\in \\QQ(\\chi, \\psi)[[q]], $$ where  $$ c_0 = \\begin{cases} 0 &amp; {\\rm if }\\,\\,\\, L&gt;1, \\\\ - \\frac{B_{k,\\psi}}{2k} &amp; {\\rm if }\\,\\,\\, L=1. \\end{cases} $$</p>\r\n\r\n<h2><strong>Theorem</strong> (Miyake, Chapter 7):</h2>\r\n<p>Suppose $t$ is a positive integer and $\\chi$, $\\psi$ are as above and that $k$ is a positive integer such that $\\chi(-1)\\psi(-1) = (-1)^k$. Except when $k=2$ and $\\chi=\\psi=1$, the power series  $E_{k,\\chi,\\psi}(q^t)$ defines an element of  $M_k(RLt,\\chi \\psi)$. If $\\chi=\\psi=1$, $k=2$, $t&gt;1$,  and $E_2(q) = E_{k,\\chi,\\psi}(q)$, then  $E_2(q) - t E_2(q^t)$ is a modular form in $M_2(\\Gamma_0(t))$.</p>\r\n<p>Moreover, the set of Eisenstein series in $M_k(N, \\varepsilon)$ above with $RLt \\mid N$ and $\\chi \\psi = \\varepsilon$   form a basis for the   Eisenstein subspace ${\\rm Eis}_k(N,\\varepsilon)$.</p>"}︡
︠28947b16-37ca-4b95-b10d-344c021d75fa︠
@interact
def f(N=(1..30), k=(12,(2..100))):
    for e in DirichletGroup(N).galois_orbits():
        eps = e[0]
        html("Eis$_{%s}(%s,%s)$:"%(k,N,latex(list(eps.values_on_gens()))))
        for E in EisensteinForms(eps, k).eisenstein_series():
            view((E.parameters(), E))
︡7dc89ac1-1a5c-4ac3-8d7d-3d4c4bedfd62︡︡
︠77bc1fdc-2971-4234-a151-71a8dad0f321i︠
%html
<p><strong>Important Trick: </strong>we can compute generalized Bernoulli numbers $B_{k,\varepsilon}$ very quickly in terms of the classical $B_c$ for $c\leq k$ (see page 656 of Cohen's <em>Number Theory and Diophantine Equations</em>, section 9). The $B_c$ can be computed <strong><em>very </em></strong>quickly, due to fast code in PARI and also very different fast parallel code by David Harvey.&nbsp;</p>

︡2ff363bd-45f1-4212-9016-2d0157831267︡{"html": "<p><strong>Important Trick: </strong>we can compute generalized Bernoulli numbers $B_{k,\\varepsilon}$ very quickly in terms of the classical $B_c$ for $c\\leq k$ (see page 656 of Cohen's <em>Number Theory and Diophantine Equations</em>, section 9). The $B_c$ can be computed <strong><em>very </em></strong>quickly, due to fast code in PARI and also very different fast parallel code by David Harvey.&nbsp;</p>"}︡
︠eda353f3-dc04-4833-a33b-95aee0fd4193︠
@interact
def f(N=(1..30), k=(12,(2..100))):
    for e in DirichletGroup(N).galois_orbits():
        eps = e[0]
        html('$B_{%s,%s} = %s$'%(k, latex(eps), latex(eps.bernoulli(k))))
︡ba2566a2-1517-4352-9cb9-f0b67038314a︡︡
︠f6a108c6-b45d-4fa4-90da-9926c4643988i︠
%html
<p><strong>Project</strong>: The code for computing $B_{k,\varepsilon}$ in Sage could probably easily be made faster with some more work.&nbsp; See the comments in the source code.</p>

︡9054e823-1276-49d8-b2ee-dcce66f56693︡{"html": "<p><strong>Project</strong>: The code for computing $B_{k,\\varepsilon}$ in Sage could probably easily be made faster with some more work.&nbsp; See the comments in the source code.</p>"}︡
︠b12b9298-6776-424b-9908-54a9a9231b71i︠
%html
<h1 style="text-align: center;">Computing Cusp Forms</h1>
<p>There are (at least) four distinct algorithms for computing classical cuspidal modular forms.  Each has <strong><em>unique advantages</em></strong> over all of the others, and it is important to master<em><strong> all</strong></em> of them (no software has yet done so...).</p>
<ol>
<li>Explicit Generators</li>
<li>The Hijikata (Eichler-Selberg) trace formula</li>
<li>Modular symbols</li>
<li>Rational quaternion algebras and supersingular elliptic curves</li>
</ol>

︡cdc5f414-6dc1-4819-b6d9-c010875ccb71︡{"html": "<h1 style=\"text-align: center;\">Computing Cusp Forms</h1>\r\n<p>There are (at least) four distinct algorithms for computing classical cuspidal modular forms.  Each has <strong><em>unique advantages</em></strong> over all of the others, and it is important to master<em><strong> all</strong></em> of them (no software has yet done so...).</p>\r\n<ol>\r\n<li>Explicit Generators</li>\r\n<li>The Hijikata (Eichler-Selberg) trace formula</li>\r\n<li>Modular symbols</li>\r\n<li>Rational quaternion algebras and supersingular elliptic curves</li>\r\n</ol>"}︡
︠bd8830df-392e-4e50-9654-a12a0cd06713i︠
%html
<h2 style="text-align: center;">1. Cusp Forms: Explicit Generators</h2>
<p><strong>Unique Advantages:</strong></p>
<ol>
<li>Fast for large weight (using fast univariate polynomial multiplication, thanks to FLINT)</li>
<li>Easy to understand and implement once generators are known.</li>
</ol>
<p>&nbsp;</p>
<p><strong>Prototype:</strong> We have an isomorphism of rings:</p>
<p>$$\bigoplus_k M_k({\rm SL}_2(\ZZ)) \cong \CC[E_4, E_6]$$</p>
<p>where $E_4$ and $E_6$ are the weight 4 and 6 Eisenstein series.</p>

︡92f81ab4-1968-4434-8979-cd7610e40d22︡{"html": "<h2 style=\"text-align: center;\">1. Cusp Forms: Explicit Generators</h2>\r\n<p><strong>Unique Advantages:</strong></p>\r\n<ol>\r\n<li>Fast for large weight (using fast univariate polynomial multiplication, thanks to FLINT)</li>\r\n<li>Easy to understand and implement once generators are known.</li>\r\n</ol>\r\n<p>&nbsp;</p>\r\n<p><strong>Prototype:</strong> We have an isomorphism of rings:</p>\r\n<p>$$\\bigoplus_k M_k({\\rm SL}_2(\\ZZ)) \\cong \\CC[E_4, E_6]$$</p>\r\n<p>where $E_4$ and $E_6$ are the weight 4 and 6 Eisenstein series.</p>"}︡
︠29264909-5378-4143-b9ac-68268fc1d94b︠
show(eisenstein_series_qexp(4,10))
︡388d8bf7-7528-4650-a5f9-35a7261ac4b9︡{"html": "<div class=\"math\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\frac{1}{240} + q + 9q^{2} + 28q^{3} + 73q^{4} + 126q^{5} + 252q^{6} + 344q^{7} + 585q^{8} + 757q^{9} + O(q^{10})</div>"}︡
︠48207623-c431-4fcb-b8db-f1a6a0afdc12︠
time E = eisenstein_series_qexp(4,10^4)
︡056ad6b5-cded-416e-9e9c-f5533ddc9d05︡{"stdout": "Time: CPU 0.10 s, Wall: 0.39 s"}︡
︠06c45430-d664-428b-b698-fc317c542f4a︠
time Delta = delta_qexp(10^5)
︡3b39bb8e-8887-42f9-9915-6a96433886a3︡{"stdout": "Time: CPU 0.22 s, Wall: 0.89 s"}︡
︠8783044b-4773-4c34-adb5-7c8a433705c8i︠
%html
<p><strong>Project: </strong>Clean up some of these $q$-expansion functions.&nbsp; For example, look at this mess below, where the names and input parameters for $\Delta$ and $\eta$ couldn't be more inconsistent!!&nbsp; Also, there should be an easy way to find them all, e.g., modforms.[tab].</p>

︡80f57a98-25d4-4941-8a40-6a67b1402275︡{"html": "<p><strong>Project: </strong>Clean up some of these $q$-expansion functions.&nbsp; For example, look at this mess below, where the names and input parameters for $\\Delta$ and $\\eta$ couldn't be more inconsistent!!&nbsp; Also, there should be an easy way to find them all, e.g., modforms.[tab].</p>"}︡
︠bd08bc51-100f-4555-bbb1-6937813720bd︠
delta_qexp(10,'q',ZZ)          # by William Stein
︡2e402749-21d8-42b4-82ef-e4f6de40b1a9︡{"stdout": "q - 24*q^2 + 252*q^3 - 1472*q^4 + 4830*q^5 - 6048*q^6 - 16744*q^7 + 84480*q^8 - 113643*q^9 + O(q^10)"}︡
︠382d4d06-1375-4498-8981-15228a64f504︠
qexp_eta(ZZ[['q']], 10)        # by David Loeffler
︡41d5e7ca-adf2-4228-b123-f977048b2d84︡{"stdout": "1 - q - q^2 + q^5 + q^7 + O(q^10)"}︡
︠2efef111-8e95-4125-bc34-7d95c471bbcai︠
%html
<p><strong>Project</strong>: One can find ring generators for other levels.&nbsp; Code something systematic for small levels in Sage.&nbsp;&nbsp;</p>

︡a0611ac3-8ca4-4f2e-aa82-1dc84b929578︡{"html": "<p><strong>Project</strong>: One can find ring generators for other levels.&nbsp; Code something systematic for small levels in Sage.&nbsp;&nbsp;</p>"}︡
︠5d889a2d-3be0-42a6-8ac0-4535cacdcea6i︠
%html
<h2 style="text-align: center;">2. Cusp Forms: The Hijikata (Eichler-Selberg) Trace Formula</h2>
<p><strong>Unique Advantages:</strong></p>
<ol>
<li>Impressive "<em>practical</em> complexity" to compute ${\rm Tr}(T_p)$ with $p$ big or with <strong>weight big</strong>. </li>
<li>Relevant to certain algorithms for computing $p$-adic modular forms.</li>
</ol>
<p>&nbsp;</p>
<p>See <a href="http://wstein.org/Tables/hijikata.html" target="_blank">http://wstein.org/Tables/hijikata.html</a> for the 2-page formula itself, which is an enormous sum over class numbers and solutions to certain quadratic equations modulo various integers.&nbsp; There is a non-optimized PARI and Magma implementation at that page, which I wrote in 1998 (!).</p>
<p>&nbsp;</p>

︡33317243-1756-4b58-8ce0-240160052cb9︡{"html": "<h2 style=\"text-align: center;\">2. Cusp Forms: The Hijikata (Eichler-Selberg) Trace Formula</h2>\r\n<p><strong>Unique Advantages:</strong></p>\r\n<ol>\r\n<li>Impressive \"<em>practical</em> complexity\" to compute ${\\rm Tr}(T_p)$ with $p$ big or with <strong>weight big</strong>. </li>\r\n<li>Relevant to certain algorithms for computing $p$-adic modular forms.</li>\r\n</ol>\r\n<p>&nbsp;</p>\r\n<p>See <a href=\"http://wstein.org/Tables/hijikata.html\" target=\"_blank\">http://wstein.org/Tables/hijikata.html</a> for the 2-page formula itself, which is an enormous sum over class numbers and solutions to certain quadratic equations modulo various integers.&nbsp; There is a non-optimized PARI and Magma implementation at that page, which I wrote in 1998 (!).</p>\r\n<p>&nbsp;</p>"}︡
︠aa4148e3-0343-4dc0-b1ec-11a539d65549︠
#g = get_remote_file('http://wstein.org/Tables/hijikata.gp')
g = '/home/wstein/sd20.2/hijikata.gp'
︡2e44f509-e209-47d9-9f92-fcc11ad9d611︡︡
︠cf318192-291a-4f96-a761-b182290eb8a4︠
len(open(g).read().splitlines())     # short!
︡f5f6fc53-4263-4ac9-a69c-3722ae9f03cf︡{"stdout": "135"}︡
︠94046b04-ed4a-4451-959c-a881c4850383︠
gp.read(g)
︡2ca92049-73a6-4cfc-a099-1d6153bbc16d︡︡
︠92174481-97d8-4433-b4b1-4119cb37dd03i︠
%html
<pre>tr(n,k,N) = tr(T_n on S_k(Gamma_0(N))). (If n | N then n must be prime.)</pre>

︡3b83f7e9-ad3a-433e-a281-69633d334368︡{"html": "<pre>tr(n,k,N) = tr(T_n on S_k(Gamma_0(N))). (If n | N then n must be prime.)</pre>"}︡
︠47ad8f05-34e7-4eed-8c00-3d04baa113ba︠
gp.eval('tr(17, 24, 1)')
︡5dccb23d-0059-454e-ab8a-0cb603f23abc︡{"stdout": "'254028147597540'"}︡
︠eaed2c71-4ef8-4c90-a58a-127273d7f6a4︠
CuspForms(1,24).T(17).trace()
︡271177d6-eff2-49a0-8ebd-f3b6f0d6c114︡{"stdout": "254028147597540"}︡
︠d3a0b629-d89a-41dc-a22e-2a3f32edca7f︠
time CuspForms(1,12).T(100000).trace()   # this just uses explicit expansion of Delta.
︡8784d189-e220-4d31-9248-73b1776361cd︡{"stdout": "-2983637890141033828147200000\nTime: CPU 0.01 s, Wall: 0.01 s"}︡
︠51d487b2-5ab3-42ac-bfa8-1c457252a554︠
time gp.eval('tr(100000,12,1)')   # in theory should be asymptotically much better than explicit q-exp
︡6e99f042-3869-499d-9347-d3aa6b06fc37︡{"stdout": "'-2983637890141033828147200000'\nTime: CPU 0.00 s, Wall: 15.75 s"}︡
︠6c92bbf5-ed8e-462f-a14f-edef93f12187i︠
%html
<p><strong>Project</strong>: Port this to Sage and make it <strong><em>fast</em></strong> enough to be useful.&nbsp; <em>Challenge:</em> Verify that $p | \tau(p)$ for $p=7758337633$.</p>

︡481be9c0-2d36-4660-809f-874802defe50︡{"html": "<p><strong>Project</strong>: Port this to Sage and make it <strong><em>fast</em></strong> enough to be useful.&nbsp; <em>Challenge:</em> Verify that $p | \\tau(p)$ for $p=7758337633$.</p>"}︡
︠50fcd545-0a12-4dd4-af6c-a83e0c00d0a1i︠
%html
<h2 style="text-align: center;">3. Cusp Forms: Modular Symbols</h2>
<p><strong>Unique Advantages:</strong></p>
<ol>
<li>Fairly general (any $N,k,\varepsilon$ with $k\geq 2$).</li>
<li>Yields <em><strong>unique</strong></em> information about special values of $L$-functions.</li>
<li>Also, unique information about <strong>abelian varieties</strong> (and motives when $k&gt;2$) that no other method gives. </li>
</ol>

<p><strong>Basic Idea:</strong>&nbsp;</p>
<ol>
<li>Compute the homology group $H_1(X_0(N),\QQ, \{{\rm cusps}\})$ in terms of an explicit presentation (<em><strong>Manin symbols</strong></em>) got from images of the path $\{0,\infty\}$ from $0$ to $\infty$.&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</li>
<li>This amounts to <em><strong>sparse linear algebra</strong></em> over $\QQ$.</li>
<li>Then compute Hecke operators using an explicit formula (and <em><strong>Heilbronn matrices</strong></em> -- see Merel's SLNM 1585).&nbsp;</li>
<li>Use <strong>dense linear algebra</strong> to decompose new subspace of $S_k$ as a direct sum of simple modules.</li>
<li>Compute system of <em><strong>Hecke eigenvalues</strong></em> associated to each summand.</li>
<li>Everything generalizes to higher weight, nontrivial characters, etc. </li>
</ol>

︡c33620e5-6247-49f8-8640-603bca548f59︡{"html": "<h2 style=\"text-align: center;\">3. Cusp Forms: Modular Symbols</h2>\r\n<p><strong>Unique Advantages:</strong></p>\r\n<ol>\r\n<li>Fairly general (any $N,k,\\varepsilon$ with $k\\geq 2$).</li>\r\n<li>Yields <em><strong>unique</strong></em> information about special values of $L$-functions.</li>\r\n<li>Also, unique information about <strong>abelian varieties</strong> (and motives when $k&gt;2$) that no other method gives. </li>\r\n</ol>\r\n\r\n<p><strong>Basic Idea:</strong>&nbsp;</p>\r\n<ol>\r\n<li>Compute the homology group $H_1(X_0(N),\\QQ, \\{{\\rm cusps}\\})$ in terms of an explicit presentation (<em><strong>Manin symbols</strong></em>) got from images of the path $\\{0,\\infty\\}$ from $0$ to $\\infty$.&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</li>\r\n<li>This amounts to <em><strong>sparse linear algebra</strong></em> over $\\QQ$.</li>\r\n<li>Then compute Hecke operators using an explicit formula (and <em><strong>Heilbronn matrices</strong></em> -- see Merel's SLNM 1585).&nbsp;</li>\r\n<li>Use <strong>dense linear algebra</strong> to decompose new subspace of $S_k$ as a direct sum of simple modules.</li>\r\n<li>Compute system of <em><strong>Hecke eigenvalues</strong></em> associated to each summand.</li>\r\n<li>Everything generalizes to higher weight, nontrivial characters, etc. </li>\r\n</ol>"}︡
︠214faa57-e978-43de-a53d-3535620f3a13︠
@interact
def f(N=(30,(1..400))):
    P = P1List(N)
    def pnt(n,m):
        if m == 0: return infinity
        return float(n)/m
    def geodesic(alpha, beta):
        if alpha == infinity or beta == infinity: return line([(0,0),(0,.5)])
        return disk(((alpha+beta)/2,0), abs((alpha-beta)/2), 
                    (0,pi), thickness=1, fill=False)         
    G = Graphics()
    for i in range(len(P)):
        a,b,c,d = P.lift_to_sl2z(i)
        G += geodesic(pnt(b,d), pnt(a,c))
    G.ymin(0); G.set_aspect_ratio(1)
    html("The %s generating Manin symbols $\\gamma\\{0,\\infty\\}$ of level %s"%(len(P), N))
    show(G, figsize=10)
︡8940c1fa-f102-4730-b9a1-61dc339d6217︡︡
︠bf966b06-822a-42e5-a13a-42b483f0b857i︠
%html
<h3>Explicit Presentation for Modular Symbols of Level 65</h3>

︡0aa290d4-5df4-427a-bfda-52427ea1df95︡{"html": "<h3>Explicit Presentation for Modular Symbols of Level 65</h3>"}︡
︠2bd7e6cc-1461-43d3-ab11-33f61d98e844︠
M = ModularSymbols(65,sign=1); M
︡cd6d7874-c11c-4213-8386-59b2030a3b6b︡{"stdout": "Modular Symbols space of dimension 8 for Gamma_0(65) of weight 2 with sign 1 over Rational Field"}︡
︠8d936531-98f2-480a-8b55-5b196b57b7ca︠
M.manin_generators()
︡3d74d780-41bc-4cf6-8066-5a8e583d4366︡{"stdout": "[(0,1), (1,0), (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10), (1,11), (1,12), (1,13), (1,14), (1,15), (1,16), (1,17), (1,18), (1,19), (1,20), (1,21), (1,22), (1,23), (1,24), (1,25), (1,26), (1,27), (1,28), (1,29), (1,30), (1,31), (1,32), (1,33), (1,34), (1,35), (1,36), (1,37), (1,38), (1,39), (1,40), (1,41), (1,42), (1,43), (1,44), (1,45), (1,46), (1,47), (1,48), (1,49), (1,50), (1,51), (1,52), (1,53), (1,54), (1,55), (1,56), (1,57), (1,58), (1,59), (1,60), (1,61), (1,62), (1,63), (1,64), (5,1), (5,2), (5,3), (5,4), (5,6), (5,7), (5,8), (5,9), (5,11), (5,12), (5,13), (5,18), (5,23), (13,1), (13,2), (13,3), (13,4), (13,5)]"}︡
︠505361c8-5f6a-4051-a857-f24a8c37d57d︠
M.manin_basis()
︡52d59b35-d148-4b23-8ad7-a26daf4aada4︡{"stdout": "[1, 67, 68, 73, 75, 79, 80, 83]"}︡
︠fe34ae3e-d0e3-4271-9cf6-88279a5d3cc3︠
M.manin_gens_to_basis()[:5]
︡d60127d5-2b91-4b7c-bc4a-987b4a5b520a︡{"stdout": "[-1  0  0  0  0  0  0  0]\n[ 1  0  0  0  0  0  0  0]\n[ 0  0  0  0  0  0  0  0]\n[ 0  1 -2  1 -1  0  1 -1]\n[ 0  0 -1  1 -1  0  1 -1]"}︡
︠ca475293-5d46-4ad7-be61-6bf767bfd4bei︠
%html
<h3>Hecke Operators at Level 65</h3>

︡efa5cb8b-3ea1-4e66-ad29-151b6ce1adbb︡{"html": "<h3>Hecke Operators at Level 65</h3>"}︡
︠b1c74bb0-11c3-44ed-b457-80a210ab6ffa︠
M = ModularSymbols(65,sign=1); M
︡e23d3ac7-8625-4bc2-981e-a247d6f752d8︡{"stdout": "Modular Symbols space of dimension 8 for Gamma_0(65) of weight 2 with sign 1 over Rational Field"}︡
︠9106bde7-870d-482d-a496-51661438eeb7︠
T2 = M.hecke_matrix(2); T2       # wrt rational homology
︡57f62033-f648-48d1-b263-c0ffbf4b0040︡{"stdout": "[   3   -1    2   -1    1    0   -1    1]\n[   0    0    1    1    1    0    0    0]\n[   0  1/2   -1    1  1/2  1/2  3/2   -2]\n[   0  3/2    0    0  1/2  1/2  1/2   -1]\n[   0  3/2    2   -1  3/2  1/2 -3/2    1]\n[   0 -1/2    0    0  1/2  1/2  5/2    0]\n[   0    0    1    0    0    2    0    1]\n[   0    0    0   -1    0    1    0    2]"}︡
︠257da7cd-2e96-41bd-85e4-188b0bd1e58b︠
show(factor(T2.charpoly()))
︡cdbc2ae2-dd32-4219-87a0-94c213194355︡{"html": "<div class=\"math\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}(x + 1) \\cdot (x - 3)^{3} \\cdot (x^{2} - 3) \\cdot (x^{2} + 2 x - 1)</div>"}︡
︠4e743600-ea70-4581-9f5a-0c363573ed96︠
M.integral_hecke_matrix(2)      # integral homology
︡7aa308e8-681e-4452-918f-20812ce7dd55︡{"stdout": "[ 3 -2  2 -1  2  1  0  1]\n[ 0  1  2  0  1  1  0  1]\n[ 0  1 -1  1  0  0  1 -2]\n[ 0  3  0  0 -1 -1 -1 -1]\n[ 0  3  2 -1  0 -1 -3  1]\n[ 0 -1  0  0  1  1  3  0]\n[ 0  0  1  0  0  2  0  1]\n[ 0  0  0 -1  0  1  0  2]"}︡
︠c19ba283-4cec-4dd3-8dd4-f1808486247ci︠
%html
<h3>Decomposition of New Subspace at Level 65</h3>

︡4bec3862-bd82-4685-a86d-bd7518def5d2︡{"html": "<h3>Decomposition of New Subspace at Level 65</h3>"}︡
︠f91778ec-c560-46ea-9b37-d33f9eb1f406︠
M = ModularSymbols(65,sign=1); M
︡00737c11-8ca9-43f3-9cf2-3cfaaca62d4e︡{"stdout": "Modular Symbols space of dimension 8 for Gamma_0(65) of weight 2 with sign 1 over Rational Field"}︡
︠6d80db6b-2af1-495b-9906-4bb2d2f8b334︠
N = M.cuspidal_subspace().new_subspace(); N
︡84f4e8b8-5895-4d57-acee-9e222c0581fc︡{"stdout": "Modular Symbols subspace of dimension 5 of Modular Symbols space of dimension 8 for Gamma_0(65) of weight 2 with sign 1 over Rational Field"}︡
︠edf91921-2ccf-4328-b345-da7469e46d3a︠
N.decomposition()
︡ac867ed2-dfca-48fb-8e83-98c8ab1935c9︡{"stdout": "[\nModular Symbols subspace of dimension 1 of Modular Symbols space of dimension 8 for Gamma_0(65) of weight 2 with sign 1 over Rational Field,\nModular Symbols subspace of dimension 2 of Modular Symbols space of dimension 8 for Gamma_0(65) of weight 2 with sign 1 over Rational Field,\nModular Symbols subspace of dimension 2 of Modular Symbols space of dimension 8 for Gamma_0(65) of weight 2 with sign 1 over Rational Field\n]"}︡
︠ef40ea6e-8fd6-424f-93f1-ffc10b7c0d04i︠
%html
<h3>Systems of Hecke Eigenvalues</h3>

︡2c99a170-6807-443c-9f54-e67a5b489bdc︡{"html": "<h3>Systems of Hecke Eigenvalues</h3>"}︡
︠80466a78-6265-44dd-9a3f-8211c672f982︠
M = ModularSymbols(65,sign=1)
D = M.cuspidal_subspace().new_subspace().decomposition()
f = D[1]; f
︡ea4f7877-433a-4ca9-b85f-352acda0bdfa︡{"stdout": "Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 8 for Gamma_0(65) of weight 2 with sign 1 over Rational Field"}︡
︠1efe11a5-56f7-4047-948a-dca585526dd7i︠
%html
<p>There is a clever "compressed representation" of the Fourier coefficients $a_n$ that arises naturally out of the modular symbols algorithm.</p>

︡9a12d290-fc7e-49f1-81e7-ee1bb2cf71de︡{"html": "<p>There is a clever \"compressed representation\" of the Fourier coefficients $a_n$ that arises naturally out of the modular symbols algorithm.</p>"}︡
︠a5391f46-05e0-4425-a44c-f603e83530af︠
A, v = f.compact_system_of_eigenvalues(prime_range(30))
print v
A
︡56c1469c-deca-4bca-aa2f-35e4e0c569af︡{"stdout": "(1, 1/2*alpha + 1)\n[-2  2]\n[-1  2]\n[ 1  0]\n[ 4 -4]\n[ 3 -2]\n[-1  0]\n[ 0 -4]\n[ 1  2]\n[ 1 -2]\n[-4  8]"}︡
︠367d3c91-b996-42af-8f3e-c714d22c2f9di︠
%html
<p>The product gives the actual eigenvalues:</p>

︡bf947176-44b6-4932-9f97-ffd4387e504f︡{"html": "<p>The product gives the actual eigenvalues:</p>"}︡
︠aaff3aa9-0578-4797-9446-c69bee64372c︠
A*v
︡8803405b-b8f6-428b-98ce-c7455f2432de︡{"stdout": "(alpha, alpha + 1, 1, -2*alpha, -alpha + 1, -1, -2*alpha - 4, alpha + 3, -alpha - 1, 4*alpha + 4, 3*alpha + 9, 6*alpha + 6, -2*alpha - 8, 5*alpha + 1, 2*alpha, -6*alpha - 12, 3*alpha + 9, -8, -2, -7*alpha - 5, -6*alpha - 6, 6*alpha + 6, -2*alpha - 8, 6, 4*alpha + 2)"}︡
︠61919ddb-4dcf-4790-a3e8-603492fa2c93i︠
%html
<p>Here is a more impressive example.&nbsp; The rows of $A$ are small, but the actual Hecke eigenvalues expressed in terms of a power basis are huge (see below).</p>

︡30b4601e-5c1e-4016-b829-fc7d38563eb2︡{"html": "<p>Here is a more impressive example.&nbsp; The rows of $A$ are small, but the actual Hecke eigenvalues expressed in terms of a power basis are huge (see below).</p>"}︡
︠43d1575e-c5cb-49b4-91a3-e3baa16a7c5b︠
f = ModularSymbols(389,sign=1)[5]
A, v = f.compact_system_of_eigenvalues(prime_range(30))
A
︡529c488b-4783-45b9-b903-8432fce25022︡{"stdout": "[ -73/8   -3/4  -61/4   73/4   -9/4  -33/4   29/4  -21/4   49/4    7/2   11/4   -1/4     -1      0   33/2    -17   -1/2    -16     16   -1/4]\n[     4      0      4     -4      0      0      0      2     -2      0      0      0      0      0     -4      4      0      4     -4      0]\n[     6      0      6     -8      0      4     -4      2     -6     -2      0      0      0      0     -8      8      0      8     -8      0]\n[     8      0     10    -12      4      8     -8      2    -10     -4     -4      0      0      0    -12     12      0     10    -10      0]\n[    12      0     20    -24      4      8     -8      8    -16     -4     -4      4      0      0    -20     20      4     20    -20      0]\n[    14      4     20    -28      8     18    -16      2    -18     -8     -8      0      4     -4    -20     20      0     20    -20      2]\n[ 169/4   -1/2  105/2 -125/2   -3/2   29/2  -13/2   57/2  -77/2     -3  -11/2    5/2      6      4    -57     58      1     52    -60    9/2]\n[ -17/4    5/2  -21/2   17/2   -1/2   -5/2    5/2   -9/2   13/2      3    3/2   -1/2     -2     -4     13     -6     -1    -12     12   -1/2]\n[-195/4  -13/2 -117/2  159/2  -23/2  -77/2   55/2  -27/2   99/2     15   29/2   -3/2     -8     10     55    -66     -3    -52     64  -11/2]\n[ -37/2      1    -25     33     -5     -5      5    -17     17      2      3     -5      0      0     26    -28     -2    -26     26     -1]"}︡
︠c5682ea4-92b7-466e-b998-835c7388115b︠
A[1]
︡7a0e5223-1cab-4f17-bc24-958bc65982fe︡{"stdout": "(4, 0, 4, -4, 0, 0, 0, 2, -2, 0, 0, 0, 0, 0, -4, 4, 0, 4, -4, 0)"}︡
︠921e7d21-55e0-4a31-89d0-9fd4499e9990i︠
%html
<p>versus</p>

︡b8bdd67e-9b75-4f9e-b9f2-f5f9c350ce70︡{"html": "<p>versus</p>"}︡
︠d849da42-4960-4d42-8bb0-4c106d32d4bd︠
(A*v)[1]
︡dc1318b2-3038-40ca-b81d-8e9fcbc036e2︡{"stdout": "-20146763/1097385680*alpha^19 + 20466323/219477136*alpha^18 + 119884773/274346420*alpha^17 - 753611053/274346420*alpha^16 - 381358355/109738568*alpha^15 + 3611475535/109738568*alpha^14 + 6349339639/1097385680*alpha^13 - 56878934241/274346420*alpha^12 + 71555185319/1097385680*alpha^11 + 163330998525/219477136*alpha^10 - 223188336749/548692840*alpha^9 - 169878973265/109738568*alpha^8 + 265944624817/274346420*alpha^7 + 199655892261/109738568*alpha^6 - 1167579836501/1097385680*alpha^5 - 619178000979/548692840*alpha^4 + 261766056911/548692840*alpha^3 + 4410485304/13717321*alpha^2 - 14646077211/274346420*alpha - 1604641167/68586605"}︡
︠d73b9d92-afac-4fa8-9143-250e007b4958︠
(A*v)[2]
︡0bbd43c4-31ef-446a-a914-a441c99f7c37︡{"stdout": "252247073/1097385680*alpha^19 - 89195955/109738568*alpha^18 - 6876716517/1097385680*alpha^17 + 13248231811/548692840*alpha^16 + 3639338697/54869284*alpha^15 - 32041245347/109738568*alpha^14 - 367946611589/1097385680*alpha^13 + 2037515640679/1097385680*alpha^12 + 816602908511/1097385680*alpha^11 - 368120881159/54869284*alpha^10 - 19595857657/1097385680*alpha^9 + 763403091515/54869284*alpha^8 - 403904463001/137173210*alpha^7 - 1743458092745/109738568*alpha^6 + 5304122556631/1097385680*alpha^5 + 9907751136883/1097385680*alpha^4 - 704659646193/274346420*alpha^3 - 236814032039/109738568*alpha^2 + 88326575941/274346420*alpha + 37821733103/274346420"}︡
︠922ad627-8a4c-47b6-a909-2e80f6084fcfi︠
%html
<p><strong>Project:</strong>&nbsp; I optimized the hell out of the compact_system_of_eigenvalues command in several special cases, e.g., trivial character.&nbsp; But the general case is still slow.&nbsp; Fix that.</p>

︡32327239-9216-464b-9366-2d323bb5504e︡{"html": "<p><strong>Project:</strong>&nbsp; I optimized the hell out of the compact_system_of_eigenvalues command in several special cases, e.g., trivial character.&nbsp; But the general case is still slow.&nbsp; Fix that.</p>"}︡
︠b09782f1-dbc4-4e81-b9c7-797a89a3fa52i︠
%html
<h2 style="text-align: center;">4. Cusp Forms: Rational Quaternion Algebras and Supersingular Elliptic Curves</h2>
<p>&nbsp;</p>
<p>The algorithm is the same as what John Voight talked about on Monday, but specialized to the case of $\QQ$.&nbsp; In short, suppose $p^{2r+1}$ exactly divides the level $N$.&nbsp; Compute an Eichler order $R$ of level $N$ in the quaternion algebra ramified at $p,\infty$, enumerate the right ideal classes in $R$, and compute Hecke operators acting on the free abelian group on these ideal classes.&nbsp;</p>
<p>&nbsp;</p>
<p><strong>Unique Advantages:</strong></p>
<ol>
<li> As a biproduct, provides <strong>explicit theta series</strong> basis for (a certain subspace of)       $S_2(\Gamma_0(N))$, for certain $N$, and sometimes theta series can        be efficiently computed to high precision. </li>
<li> Provides <strong>unique input</strong> (the Monodromy Pairing) needed by my algorithm for computing         Tamagawa numbers of <strong>modular abelian varieties</strong>, and also for computing Kolyvagin cohomology classes.&nbsp; </li>
<li>There is a canonical basis and the matrices of Hecke operators are <strong>extremely sparse</strong>, e.g., $T_{p}$ has (at most) $p+1$ nonzero entries per row, no matter what the level!!! </li>
<li>Mestre <em>Method of Graphs</em> variant is <strong>very fast</strong> and easy to implement (when applicable).</li>
</ol>

︡3aa4dda7-401a-4239-8342-fd1f09626532︡{"html": "<h2 style=\"text-align: center;\">4. Cusp Forms: Rational Quaternion Algebras and Supersingular Elliptic Curves</h2>\r\n<p>&nbsp;</p>\r\n<p>The algorithm is the same as what John Voight talked about on Monday, but specialized to the case of $\\QQ$.&nbsp; In short, suppose $p^{2r+1}$ exactly divides the level $N$.&nbsp; Compute an Eichler order $R$ of level $N$ in the quaternion algebra ramified at $p,\\infty$, enumerate the right ideal classes in $R$, and compute Hecke operators acting on the free abelian group on these ideal classes.&nbsp;</p>\r\n<p>&nbsp;</p>\r\n<p><strong>Unique Advantages:</strong></p>\r\n<ol>\r\n<li> As a biproduct, provides <strong>explicit theta series</strong> basis for (a certain subspace of)       $S_2(\\Gamma_0(N))$, for certain $N$, and sometimes theta series can        be efficiently computed to high precision. </li>\r\n<li> Provides <strong>unique input</strong> (the Monodromy Pairing) needed by my algorithm for computing         Tamagawa numbers of <strong>modular abelian varieties</strong>, and also for computing Kolyvagin cohomology classes.&nbsp; </li>\r\n<li>There is a canonical basis and the matrices of Hecke operators are <strong>extremely sparse</strong>, e.g., $T_{p}$ has (at most) $p+1$ nonzero entries per row, no matter what the level!!! </li>\r\n<li>Mestre <em>Method of Graphs</em> variant is <strong>very fast</strong> and easy to implement (when applicable).</li>\r\n</ol>"}︡
︠281f5ced-a084-4551-9119-fe4e78ebda66i︠
%html
<p>Example: Level $65 = 5\cdot 13$</p>

︡be4b40cc-ea42-4cda-bb72-2dd7de18ed77︡{"html": "<p>Example: Level $65 = 5\\cdot 13$</p>"}︡
︠b27dc90f-dcea-4e00-9231-2595801e96e1︠
B = BrandtModule(5, 13); B
︡e7137906-1348-4fea-9350-b56b478d1845︡{"stdout": "Brandt module of dimension 6 of level 5*13 of weight 2 over Rational Field"}︡
︠0d0571b6-bd17-428e-b099-cfb90a572467︠
B.quaternion_algebra()
︡6a6f291a-9310-439f-a813-ca62e35b97e2︡{"stdout": "Quaternion Algebra (-2, -5) with base ring Rational Field"}︡
︠032428f1-0900-4757-a59c-08241a6361c1︠
B.order_of_level_N()
︡e50053d0-cb99-4706-9f2d-6055d2c08678︡{"stdout": "Order of Quaternion Algebra (-2, -5) with base ring Rational Field with basis (1/2 + 1/2*j + 7/2*k, 1/4*i + 1/2*j + 41/4*k, j + 7*k, 13*k)"}︡
︠d66a9345-f39e-431f-a09c-c5ba6891fd3d︠
B.right_ideals()
︡ab304e66-c6b3-4d1a-a0d2-9fa9e59e6939︡{"stdout": "(Fractional ideal (2 + 2*j + 14*k, i + 2*j + 41*k, 4*j + 28*k, 52*k), Fractional ideal (2 + 2*j + 14*k, 2*i + 4*j + 30*k, 8*j + 4*k, 52*k), Fractional ideal (2 + 6*j + 42*k, i + 2*j + 41*k, 8*j + 56*k, 104*k), Fractional ideal (2 + 6*j + 94*k, i + 6*j + 17*k, 8*j + 56*k, 104*k), Fractional ideal (2 + 14*j + 46*k, i + 14*j + 73*k, 16*j + 112*k, 208*k), Fractional ideal (2 + 14*j + 254*k, i + 30*j + 185*k, 32*j + 224*k, 416*k))"}︡
︠d6b0cd56-5eab-45ff-87b9-34384893abec︠
T2 = B.hecke_matrix(2); T2
︡cd0cfd10-876e-4d7b-8b63-39257cff1776︡{"stdout": "[0 1 1 1 0 0]\n[3 0 0 0 0 0]\n[1 0 0 1 1 0]\n[1 0 1 0 1 0]\n[0 0 1 1 0 1]\n[0 0 0 0 3 0]"}︡
︠eff63a7f-2615-427b-9205-d3989e130009︠
factor(T2.charpoly())
︡496c03cc-3d12-4048-b590-ee4311f3408a︡{"stdout": "(x - 3) * (x + 1) * (x^2 - 3) * (x^2 + 2*x - 1)"}︡
︠7b17013f-6b67-4203-bb99-e92bbfa5ccc5︠
B.brandt_series(2)
︡96aff0c6-bd2f-4789-ade4-e69d7c33e450︡{"stdout": "[1/2 + q + O(q^2)     1/2 + O(q^2)     1/2 + O(q^2)     1/2 + O(q^2)     1/2 + O(q^2)     1/2 + O(q^2)]\n[    1/6 + O(q^2) 1/6 + q + O(q^2)     1/6 + O(q^2)     1/6 + O(q^2)     1/6 + O(q^2)     1/6 + O(q^2)]\n[    1/2 + O(q^2)     1/2 + O(q^2) 1/2 + q + O(q^2)     1/2 + O(q^2)     1/2 + O(q^2)     1/2 + O(q^2)]\n[    1/2 + O(q^2)     1/2 + O(q^2)     1/2 + O(q^2) 1/2 + q + O(q^2)     1/2 + O(q^2)     1/2 + O(q^2)]\n[    1/2 + O(q^2)     1/2 + O(q^2)     1/2 + O(q^2)     1/2 + O(q^2) 1/2 + q + O(q^2)     1/2 + O(q^2)]\n[    1/6 + O(q^2)     1/6 + O(q^2)     1/6 + O(q^2)     1/6 + O(q^2)     1/6 + O(q^2) 1/6 + q + O(q^2)]"}︡
︠81b0708d-6ae1-4484-8cfb-7abbc6493b26i︠
%html
<p><strong>The Method of Graphs: For prime level</strong></p>
<p>Compute Hecke action directly on the free abelian group on supersingular $j$-invariants in characteristic $p$.</p>

︡fd45a489-66a4-46bb-ae8e-61849d83f352︡{"html": "<p><strong>The Method of Graphs: For prime level</strong></p>\r\n<p>Compute Hecke action directly on the free abelian group on supersingular $j$-invariants in characteristic $p$.</p>"}︡
︠54526229-8cd1-4888-b49d-bb96677928a9︠
@interact
def f(p=(131,tuple(prime_range(11,400)))):
    X = SupersingularModule(p)
    T2 = X.hecke_matrix(2)
    G = DiGraph(T2)
    G.plot(graph_border=True, vertex_labels=False, vertex_size=30).show(figsize=6)
︡aa128f2d-a0ba-404b-b4ab-04da68ce9308︡︡
︠229b7999-a7a0-407d-b290-329c2dfb8ceai︠
%html
<p><strong>Project: </strong>Implement computation of Eichler orders when $p^{2r+1}$ divides the level, with $r\geq 1$.</p>
<p><strong>Project: </strong>Higher weight?</p>

︡8998af44-d34c-4be7-9cf4-4e01c1d9de44︡{"html": "<p><strong>Project: </strong>Implement computation of Eichler orders when $p^{2r+1}$ divides the level, with $r\\geq 1$.</p>\r\n<p><strong>Project: </strong>Higher weight?</p>"}︡
︠93dbb547-ce88-4414-9d0e-8b3cd9043d1ci︠
%html
<h2 style="text-align: center;"><strong>Closing Remarks</strong></h2>
<ol>
<li>I have only scratched the surface.&nbsp; There are <em>many, many</em> other relevant algorithms, e.g., SLNM 1585 gives an algorithm for computing weight 1 forms in some cases.&nbsp; There are also algorithms for half-integral weight forms. </li>
<li>Edixhoven et al. have a theoretical algorithm for computing $a_p$ at level 1 in time polynomial in $\log(p)$ via a Schoff-like approach.&nbsp; They posted a book about this to the arxiv, and seek feedback.</li>
<li>I wrote a book on computing modular forms that the AMS published.&nbsp; It is now <em><strong>totally free</strong></em> at my website. </li>
</ol>

︡2e397443-be94-4a89-92d2-7edf227302d0︡{"html": "<h2 style=\"text-align: center;\"><strong>Closing Remarks</strong></h2>\r\n<ol>\r\n<li>I have only scratched the surface.&nbsp; There are <em>many, many</em> other relevant algorithms, e.g., SLNM 1585 gives an algorithm for computing weight 1 forms in some cases.&nbsp; There are also algorithms for half-integral weight forms. </li>\r\n<li>Edixhoven et al. have a theoretical algorithm for computing $a_p$ at level 1 in time polynomial in $\\log(p)$ via a Schoff-like approach.&nbsp; They posted a book about this to the arxiv, and seek feedback.</li>\r\n<li>I wrote a book on computing modular forms that the AMS published.&nbsp; It is now <em><strong>totally free</strong></em> at my website. </li>\r\n</ol>"}︡