search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.37k stars 462 forks source link

Interface with arb L-function evaluation #24823

Open rwst opened 6 years ago

rwst commented 6 years ago

http://fredrikj.net/blog/2016/11/dirichlet-l-functions-in-arb/

has Dirichlet character objects and evaluation of their L-functions. Sage should provide an interface to this functionality.

CC: @dimpase @jdemeyer

Component: interfaces

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

dimpase commented 6 years ago
comment:1

Would arb be a faster alternative to lcalc than pari?

jdemeyer commented 6 years ago
comment:2

lcalc is specifically good for finding zeros on the critical line. And this text from the quoted page does not sound promising:

Beware that real_roots.c just uses brute force interval subdivision to prove that no real roots are missed. This gets very slow for modestly large q and/or t (note that 6475 function evaluations were needed to search [−10,10] even though there are only 6 sign changes). There are far more efficient ways (e.g. Turing's method) to provably locate zeros of L-functions and also make sure that there are no zeros off the critical line, which might be implemented in Arb in the future. A relatively simple improvement would be to use Taylor polynomials.

rwst commented 6 years ago
comment:3

See also https://github.com/fredrik-johansson/arb/issues/164

fredrik-johansson commented 6 years ago
comment:4

Replying to @jdemeyer:

lcalc is specifically good for finding zeros on the critical line. And this text from the quoted page does not sound promising:

Beware that real_roots.c just uses brute force interval subdivision to prove that no real roots are missed. This gets very slow for modestly large q and/or t (note that 6475 function evaluations were needed to search [−10,10] even though there are only 6 sign changes). There are far more efficient ways (e.g. Turing's method) to provably locate zeros of L-functions and also make sure that there are no zeros off the critical line, which might be implemented in Arb in the future. A relatively simple improvement would be to use Taylor polynomials.

That's not really a limitation of the L-function evaluation though; it's just that doing interval root-finding naively is extremely inefficient. An implementation of Turing's method on top of the Dirichlet L-function evaluation in Arb should work just fine (in fact, Dave Platt wrote such code as an LMFDB script, but I haven't tested it myself). As should an ordinary numerical root-finding algorithm if you don't care about provable correctness.

jdemeyer commented 6 years ago
comment:5

As far as I know, lcalc is not provably correct. But it is fast...

jdemeyer commented 6 years ago
comment:6

I have a feature request by the way for arb: support arbitrary L-functions instead of only Dirichlet L-functions.

The lfun package of PARI/GP has support for a wide range of L-functions and it would be nice if one could feed the data from PARI/GP to arb to do calculations. Of course, one would need to figure out which kind of data are needed to represent an L-function.

fredrik-johansson commented 6 years ago
comment:7

Several people have already asked for such a feature. I have vague plans to work on this with Pascal Molin, as soon as he has time... or rather, he'd be the one working on it with me providing some assistance, since he's the one who really understands the algorithms. At least the plan is support some other types (e.g. elliptic curves). My limited understanding is that it's very hard to guarantee anything for general L-functions, but you might be able to do something conditional upon the user providing some assertions about the input (bounds on coefficients, etc.). For L-functions other than Dirichlet L-functions (where we have the Hurwitz zeta decomposition and other special techniques), the actual numerical method should be more or less the same as what Pari does, though.