Speed up computation of twists of newforms

[11d1fc49-71a1-44e1-869f-76be013245a0]

The current code for computing twists of newforms by Dirichlet characters is unnecessarily slow, because it computes a full decomposition of the target space into simple Hecke modules, and then throws all but one of the factors away. It is quicker just to directly pull out the appropriate factor using kernels of Hecke matrices.

Depends on #18478

Component: modular forms

Author: David Loeffler

Branch/Commit: a99880c

Reviewer: Peter Bruin

Issue created by migration from https://trac.sagemath.org/ticket/18663

[11d1fc49-71a1-44e1-869f-76be013245a0]

Branch: u/davidloeffler/better_twists

[11d1fc49-71a1-44e1-869f-76be013245a0]

Dependencies: 18478

[11d1fc49-71a1-44e1-869f-76be013245a0]

Commit: 480f951

[11d1fc49-71a1-44e1-869f-76be013245a0]

comment:2

Here's a patch. I tested it doing sage: Newforms(11)[0].twist(DirichletGroup(5).0) and it went down from about 30 sec to about 3 sec on my machine. The doctest requires #18478 to pass.

---

New commits:

480f951

Trac 18663: Speed up computation of twists of newforms

[pjbruin]

Changed dependencies from 18478 to #18478

[pjbruin]

comment:4

I haven't looked at this in detail, but with both this ticket and #6018 applied, the example from #18086 comment:15 only takes about a second. However, some long doctests fail even with #18478 merged:

sage -t --long --warn-long 49.1 src/sage/modular/modform/element.py
**********************************************************************
File "src/sage/modular/modform/element.py", line 1188, in sage.modular.modform.element.Newform.twist
Failed example:
    Delta.twist(chi, level=3)  # long time
Expected:
    Traceback (most recent call last):
    ...
    RuntimeError: twist of q - 24*q^2 + 252*q^3 - 1472*q^4 + 4830*q^5 + O(q^6) by Dirichlet character modulo 1 of conductor 1 is not a newform in Cuspidal subspace of dimension 3 of Modular Forms space of dimension 5 for Congruence Subgroup Gamma0(3) of weight 12 over Cyclotomic Field of order 1 and degree 1
Got:
    ...
         raise RuntimeError('twist of %s by %s is not a newform in %s' % (self, chi, S))
    UnboundLocalError: local variable 'S' referenced before assignment
**********************************************************************
File "src/sage/modular/modform/element.py", line 1192, in sage.modular.modform.element.Newform.twist
Failed example:
    Delta.twist(chi, level=3, check=False)  # long time
Exception raised:
    ...
         raise RuntimeError('twist of %s by %s is not a newform in %s' % (self, chi, S))
    UnboundLocalError: local variable 'S' referenced before assignment
**********************************************************************
1 item had failures:
   2 of  17 in sage.modular.modform.element.Newform.twist
    [305 tests, 2 failures, 45.85 s]
----------------------------------------------------------------------
sage -t --long --warn-long 49.1 src/sage/modular/modform/element.py  # 2 doctests failed
----------------------------------------------------------------------

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 480f951 to 91d4941

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

91d4941

Trac 18663: fix doctest failure

[11d1fc49-71a1-44e1-869f-76be013245a0]

comment:6

Sorry, that was sloppy of me! Here's a fix.

[pjbruin]

comment:7

One of the doctests still fails, this time because the effect of setting check=False is changed:

File "src/sage/modular/modform/element.py", line 1192, in sage.modular.modform.element.Newform.twist
Failed example:
    Delta.twist(chi, level=3, check=False)  # long time
Exception raised:
    ...
    RuntimeError: twist of q - 24*q^2 + 252*q^3 - 1472*q^4 + 4830*q^5 + O(q^6) by Dirichlet character modulo 1 of conductor 1 is not a newform in Cuspidal subspace of dimension 3 of Modular Forms space of dimension 5 for Congruence Subgroup Gamma0(3) of weight 12 over Cyclotomic Field of order 1 and degree 1

We should either just remove this doctest, or find a new example to document that check=False can lead to wrong results.

[11d1fc49-71a1-44e1-869f-76be013245a0]

Changed branch from u/davidloeffler/better_twists to u/davidloeffler/better_twists_2

[11d1fc49-71a1-44e1-869f-76be013245a0]

comment:9

Here's a new version. I've made a subtle change which ensures that the code cannot return bogus results (even if check=False); it now either returns a correct answer, or fails with a ValueError if the form is not new at the specified level. The change is that the code starts by taking the new subspace of the modular symbols (which is pretty cheap to compute) and only then starts filtering down to kernels of Hecke operators.

I've also changed the error messages a bit so it returns a different error if the computed mod sym space is 0 than if it's too large (the latter could, theoretically, happen in valid examples if the level was gigantic, whereas the former can only occur if the input is bogus so it makes sense to return ValueError).

---

New commits:

a99880c

Trac 18663: Speed up computation of twists of newforms

[11d1fc49-71a1-44e1-869f-76be013245a0]

Changed commit from 91d4941 to a99880c

[11d1fc49-71a1-44e1-869f-76be013245a0]

Author: David Loeffler

[pjbruin]

comment:11

This looks good to me now.

[pjbruin]

Reviewer: Peter Bruin

[vbraun]

Changed branch from u/davidloeffler/better_twists_2 to a99880c