implement Dirichlet series

[rwst]

kcrisman in #8383 comment:20:

Did somebody say defining Dirichlet series? Here is an implementation that I haven't had time to try out but which might be a good basis for that. This sage-support thread may also be relevant, though I don't know how advanced that psage code is.

The following file lists some product forms and their corresponding generating functions, it should be used to pick doctests for the g.f. input part of this ticket. The resp. OEIS entries are partly conjectural. https://drive.google.com/file/d/0B4PmRyK1JXgHY29aa00zZnhib1k/

Followup: #18102

CC: @kcrisman @sagetrac-mkamalakshya @jonhanke @slel

Component: number theory

Keywords: moebius, zeta, sigma, euler_phi, euler, Dirichlet series

Author: Jonathan Hanke, Ralf Stephan

Branch/Commit: public/ticket/16477 @ eb20067

Reviewer: Kamalakshya Mahatab, Vincent Delecroix, Jeroen Demeyer, Jonas Jermann, Ralf Stephan

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

[kcrisman]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
-kcrisman in [comment:20](#comment%3A20) of #8383:
+kcrisman in [#8383 comment:20](https://github.com/sagemath/sage/issues/8383#comment:20):
 > Did somebody say [defining Dirichlet series](http://ask.sagemath.org/question/2540/defining-dirichlet-series)?  [Here is an implementation](http://www.wordpress.jonhanke.com/Software/Sage__Dirichlet_series/Dirichlet_series.sage) that I haven't had time to try out but which might be a good basis for that.  [This sage-support thread](https://groups.google.com/forum/#!msg/sage-support/v7TFXKbAV0E/) may also be relevant, though I don't know how advanced that psage code is.

[kcrisman]

comment:3

Attachment: Dirichlet_series.sage.gz

I've attached the relevant file as well.

[e1ec7f9c-6cef-47b0-b1f9-6886b4d011f0]

Commit: c0037b2

[e1ec7f9c-6cef-47b0-b1f9-6886b4d011f0]

Branch: u/mkamalakshya/16477

[e1ec7f9c-6cef-47b0-b1f9-6886b4d011f0]

New commits:

c0037b2

Made the patch in to branch.

[kcrisman]

comment:8

See also how to do it in Pari. Indeed, it has multiplication of Dirichlet series and so forth. Maybe that could be used somehow, since it already exists and is presumably well-tested.

[rwst]

comment:9

This is not correct. The commit author (contrary to the committer) should show as Jonathan Hanke. This is done by using the --author option of git ci. I will change that.

[rwst]

Changed branch from u/mkamalakshya/16477 to public/dirichlet-series

[rwst]

Changed commit from c0037b2 to cfcd3aa

[rwst]

comment:11

I also moved the file under modular/.

---

New commits:

cfcd3aa

16477: original draft of Dirichlet series

[rwst]

Author: Jonathan Hanke

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

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

d1f4d30

16477: adapt to Sage; fix most doctest failures

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

Changed commit from cfcd3aa to d1f4d30

[rwst]

Dependencies: #18038

[rwst]

Work Issues: use pari, g.f. input

[rwst]

Changed author from Jonathan Hanke to Jonathan Hanke, Ralf Stephan

[jdemeyer]

Changed dependencies from #18038 to #18038, #18041

[jdemeyer]

comment:16

About PARI: dirmul and dirdiv already work in Sage. direuler is difficult because of the syntax direuler(p=a,b,expr) involving a loop variable and an expression to be evaluated.

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

Changed commit from d1f4d30 to 949082c

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

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

3860235	16477: cleanup; switch from string to generating function input (limited impl.)
f677923	16477: add dirmul, dirdiv to pari class gen
949082c	16477: use dirmul, dirdiv; many fixes

[rwst]

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
 kcrisman in [#8383 comment:20](https://github.com/sagemath/sage/issues/8383#comment:20):
 > Did somebody say [defining Dirichlet series](http://ask.sagemath.org/question/2540/defining-dirichlet-series)?  [Here is an implementation](http://www.wordpress.jonhanke.com/Software/Sage__Dirichlet_series/Dirichlet_series.sage) that I haven't had time to try out but which might be a good basis for that.  [This sage-support thread](https://groups.google.com/forum/#!msg/sage-support/v7TFXKbAV0E/) may also be relevant, though I don't know how advanced that psage code is.

+The following file lists some product forms and their corresponding generating functions, it should be used to pick doctests for the g.f. input part of this ticket. The resp. OEIS entries are partly conjectural.
+https://drive.google.com/file/d/0B4PmRyK1JXgHY29aa00zZnhib1k/

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

comment:19

Hi

Just an idea:

Shouldn't it be possible to define/implement Dirichlet series by specifying a function (from Z/ideals/whatever) for their coefficients?

I guess that would require some base class (which ideally would accept/parse/recognize functions from Z/whatever) for the coefficient functions. It would do parsing tasks, printing(!) of functions, arithmetic operations/dirichlet convolutions/etc... (Completely) multiplicative functions would be a "nice" subclass. Ideally the implementation would at least support basic Dirichlet series example.

Again: Just an idea (for either an extension or a new implementation/ticket).

Regards, Jonas

[kcrisman]

comment:20

You are quite right - so, does Pari support this? If not, then it's probably a fairly big job and should be a different ticket (while you should make sure that this ticket remains agnostic with respect to your questions so the backend can be changed). If yes, hopefully we could just hook into their stuff for anything nontrivial.

[rwst]

comment:21

At the moment this is implemented:

sage: Lminus4 = dirichlet_series([kronecker(-4,n) for n in range(1,21)]); Lminus4
1 + -1/(3^s) + 1/(5^s) + -1/(7^s) + 1/(9^s) + -1/(11^s) + 1/(13^s) + -1/(15^s) + 1/(17^s) + -1/(19^s) + O(21^(-s))
sage: zeta = dirichlet_series([1]*20); zeta
1 + 1/(2^s) + 1/(3^s) + 1/(4^s) + 1/(5^s) + 1/(6^s) + 1/(7^s) + 1/(8^s) + 1/(9^s) + 1/(10^s) + 1/(11^s) + 1/(12^s) + 1/(13^s) + 1/(14^s) + 1/(15^s) + 1/(16^s) + 1/(17^s) + 1/(18^s) + 1/(19^s) + 1/(20^s) + O(21^(-s))
sage: zeta * Lminus4^(-1)
1 + 1/(2^s) + 2/(3^s) + 1/(4^s) + 2/(6^s) + 2/(7^s) + 1/(8^s) + 2/(9^s) + 2/(11^s) + 2/(12^s) + 2/(14^s) + 1/(16^s) + 2/(18^s) + 2/(19^s) + O(21^(-s))

Please give a concrete example what you like to see!

[rwst]

comment:22

I just found this: https://github.com/williamstein/psage/blob/master/psage/lseries/eulerprod.py#L1128

EDIT: This has much more generality and lets this ticket look like a child's toy, so there 8P

[jdemeyer]

comment:23

Concerning the dependencies #18038 and #18041: if you want to use direuler now, you can still do it using strings: pari("direuler(...)") should work just like in GP:

sage: pari("direuler(p=2, 20, 1/(1-X)/(1-p*X))")
[1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, 42]

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

comment:24

rws:

I'm in particular hoping for an exact implementation of arithmetic/multiplicative functions:

id = ArithmeticFunctions().id()
sigma0 = ArithmeticFunction(lambda n: sigma0(n))
id*id == sigma0 // Dirichlet convolution

...

f = DirichletSeries(id)*DirichletSeries(id)
f == DirichletSeries(sigma0)
f[91234154]
f // nice representations:
=> sum_{n in Z} (sum_{d|n} 1)
or: sum_{n in Z} sigma0(n)

...

Those certainly form a nice subset of possible coefficient functions / dirichlet series. More generally I was hoping for the possibility to specify Dirichlet series / coefficient functions exactly, not only up to some precision. E.g. (bad example) DirichletSeries(lambda n: sin(n)) or e.g. by specifying an (exact) generating series as e.g. a rational function

Calculating the n'th coefficient from these to get a DirichletSeries as now is at least rather simple.

Other ideas: exact verification of identities (not only up to precision), nice representations/output of coefficient functions after operations (hard), support functions from ideals (TODO: figure out the correct category for the domain of coefficient functions).

I am aware that this is not a small task and might not be easily possible in python. But I hope you get the idea of what I had in mind...

[kcrisman]

comment:25

That is probably a bit beyond this ticket, though maybe not. It would be nice to have such "symbolic" ones too.

[rwst]

comment:26

Replying to @jjermann:

f = DirichletSeries(id)*DirichletSeries(id)
f == DirichletSeries(sigma0)
f[91234154]
f // nice representations:
=> sum_{n in Z} (sum_{d|n} 1)
or: sum_{n in Z} sigma0(n)

nice representations/output of coefficient functions after operations (hard),

That would first need conversion of the g.f. into divisor sum form. Another ticket.

id = ArithmeticFunctions().id()
sigma0 = ArithmeticFunction(lambda n: sigma0(n))
id*id == sigma0 // Dirichlet convolution

That would need ability to compute a g.f. from the coefficients. I think this is possible but hard.

support functions from ideals (TODO: figure out the correct category for the domain of coefficient functions).

And a third ticket.

So this ticket would prepare for the others by providing creation from expressions of a limited form (polynomial fractions with generator from zeta(a*s+b) and L(c)).

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

comment:27

Replying to @rwst:

Replying to @jjermann:

f = DirichletSeries(id)*DirichletSeries(id)
f == DirichletSeries(sigma0)
f[91234154]
f // nice representations:
=> sum_{n in Z} (sum_{d|n} 1)
or: sum_{n in Z} sigma0(n)

nice representations/output of coefficient functions after operations (hard),

That would first need conversion of the g.f. into divisor sum form. Another ticket.

There are (at least) two different (exact) approaches:

• Coefficient functions
• Generating functions (as q-series?), I am not entirely sure what you mean by it...

I was emphasizing on the coefficient function part. Clearly it is possible to define dirichlet series by specifying the coefficient function (as a normal function). It is even relatively simple to implement all kind of operations. Individual coefficients could also be calculated (up to some precision). What is hard is getting a "nice representation" (e.g. a divisor sum form as you mentioned above).

• One idea might be to somehow "decompile" a function into source code / some at least nicer form.
• One idea might be to use symbolic expression (rather limited).
• Another idea might be to implement very basic coefficient functions and allow all kind of operations with them (using ast(?)/whatever) to be as flexible as possible with the combinations (include as many of the popular examples as possible).
• Finally we could simply use the old representation by just calculating the coefficients up to some precision. The advantage would be that "precision" is no longer part of the series, only of the representation.

id = ArithmeticFunctions().id()
sigma0 = ArithmeticFunction(lambda n: sigma0(n))
id*id == sigma0 // Dirichlet convolution

That would need ability to compute a g.f. from the coefficients. I think this is possible but hard.

The relation between coefficient functions and generating series might be a challenge. I wonder what approach is more suitable. Maybe the two concepts both have interesting cases that cannot easily be translated to the other way. So maybe both ways should be supported (?).

support functions from ideals (TODO: figure out the correct category for the domain of coefficient functions).

And a third ticket.

So this ticket would prepare for the others by providing creation from expressions of a limited form (polynomial fractions with generator from zeta(a*s+b) and L(c)).

I was thinking in very general terms ("any" function from Z). That should be fairly simple (even with operations on series) and allow the calculation of the coefficients up to an arbitrary precision. Example:

(F+G).cf = lambda n: F.cf(n) + G.cf(n)
(F*G).cf = lambda n: sum(F.cf(d)*G.cf(n/d) for d in divisors(n))

However it will be very hard to get "nice" representation of the coefficient functions.

Maybe "polynomial fractions with genertore from zeta(a*s+b) and L(c)" is more powerful, I don't know.

Side remark: Dirichlet series could/should be viewed as something like a Fourier transform of an Arithmetic function.

[rwst]

comment:28

Replying to @jjermann:

• Generating functions (as q-series?), I am not entirely sure what you mean by it...

See https://en.wikipedia.org/wiki/Generating_function#Dirichlet_series_generating_functions

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

comment:29

Replying to @rwst:

Replying to @jjermann:

• Generating functions (as q-series?), I am not entirely sure what you mean by it...

See https://en.wikipedia.org/wiki/Generating_function#Dirichlet_series_generating_functions

Yes but that doesn't explain how the g.f. is implemented (in an exact way). For some families of Dirichlet series the corresponding ordinary (or exponential) generating series could be stored as a rational function (e.g. 1/(1-q)).

I assumed you meant this when refering to g.f. How else could you store the g.f. in an exact matter?

[rwst]

comment:30

Replying to @jjermann:

How else could you store the g.f. in an exact matter?

Nearly all D.g.f.'s I have seen (and certainly all that generate your arithmetic functions) are polynomials in A. zeta(as+b), B. L(chi(c,d), s), C. (1-e^(-s+f)), with a,b,c,d,e,f integer. Okay, this is not a proof, but well supported by data in the OEIS. So I want to store that polynomial.

[kcrisman]

comment:31

I agree that both of these representations are useful and desired. Would it be possible to implement the basics here - esp. since it turns out Pari has a lot of the functionality we need - and then put the generating function stuff (which I would also use) in a separate ticket? I'm just concerned that this will never happen despite a lot of enthusiasm.

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

comment:32

Unfortunately experience shows that this concern is well founded. So yes, I agree.

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

comment:33

Just for your information:

I started some preliminary (poc) test implementation of arithmetic functions (no tests/documentation etc). The first idea was to use symbolic expressions but they don't work well together with sums which are absolutely crucial for operations on arithmetic functions...

The test implementation is available on u/jj/arith_functions:

https://github.com/sagemath/sagetrac-mirror/commit/526e1ae40f94cff95e5dc6926208b831643edfb4

Here is a simple example:

sigma3 = ArithmeticFunction(lambda n: sigma(n,3), lambda n,_: "sigma({},3)".format(n), lambda n,_: "\\sigma_{{3}}\\left({}\\right)".format(n))
sigma3^2
show(sigma3^2)
(sigma3^2)(5)

[rwst]

comment:34

Replying to @jjermann:

I started some preliminary (poc) test implementation of arithmetic functions (no tests/documentation etc).

https://github.com/sagemath/sagetrac-mirror/commit/526e1ae40f94cff95e5dc6926208b831643edfb4

I think you should open an enhancement ticket for this branch, just to make it possible to discuss specifics. Note: I am supporting your effort of formulating the algebraic side of these functions. Note too that Dirichlet series represent a superset of these functions, so your code cannot serve as the parent ring implementation of this ticket, and a different ticket is needed.

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

comment:35

Ok, I created a ticket: https://github.com/sagemath/sage-prod/issues/18102

Regarding Dirichlet series: It seems that rational functions (over what?) might provide a nice (internal) basis for how (exact) Dirichlet series are stored. The coefficients can be calculated and it should be possible to automatically define a corresponding coefficient function. This would still benefit from a nice base class for arithmetic functions (in particular since we know to construct/represent the coefficient function, this additional information could be "passed on" to / used by the arithmetic function element).

[rwst]

Changed branch from public/dirichlet-series to u/rws/16477-1

[rwst]

Changed dependencies from #18038, #18041 to none

[rwst]

comment:37

This version now supports generating functions of a certain form. Please see the documentation. This should suffice as a first version. Further development possibilities were already discussed in this ticket.

Please review.

---

New commits:

05c8cba	Merge branch 'develop' into tmp9
5698ef1	16477: adapt code to Sage; rewrite to allow generated series

[rwst]

Changed commit from 949082c to 5698ef1

[videlec]

comment:38

Hello,

1. there is no need to add method dirmul and dirdiv to the pari gen object. This is taken care automatically since #17631. Doctesting is cool thoug. But move it somewhere else.

2. Why is this new module in sage.modular? It makes no sense.

3. You should try harder to use pari and not gp. Since #17631, most functions are available directly in pari.

4. DirichletSeries would better inherit from RingElement. In that case, you must not define __add__, __mul__, __div__ etc but _add_, _mul_, _div_. That way you will get benefits from coercion (e.g. multiplication by scalars). You might have a look to polynomials (in sage.rings.polynomials.* or power series (in sage.rings.power_series_*).

5. What is the purpose of the commented code?

6. The error must be new style ones. Please use

    raise MyError("my message")

instead of

    raise MyError, "my message"

Vincent

[rwst]

comment:39

Replying to @videlec:

Thanks, I accept points 1 and 6 but:

2. Why is this new module in sage.modular? It makes no sense.

The Dirichlet characters are there too. I don't see why not.

3. You should try harder to use pari and not gp. Since #17631, most functions are available directly in pari.

But not those needing closures, see comment:16 and #18038

4. DirichletSeries would better inherit from RingElement. In that case, you must not define __add__, __mul__, __div__ etc but _add_, _mul_, _div_. That way you will get benefits from coercion (e.g. multiplication by scalars). You might have a look to polynomials (in sage.rings.polynomials.* or power series (in sage.rings.power_series_*).

This is clearly a separate ticket.

5. What is the purpose of the commented code?

I didn't want to erase useful ideas of the original author.

[videlec]

comment:40

Hello,

Replying to @rwst:

Replying to @videlec:

2. Why is this new module in sage.modular? It makes no sense.

The Dirichlet characters are there too. I don't see why not.

Because sage.modular is intended for modular forms. A Dirichlet serie is not necessarily a modular form. To me, modules and submodules should work by inclusion. Or at least try to.

I do not see Dirichlet series as a subset of modular forms. I perfectly understand the reason why it is here, but it would be better in sage.functions or sage.rings. The directory sage.modular really contains too much stuff. This is historical as people that initiated Sage were very interested in modular forms.

3. You should try harder to use pari and not gp. Since #17631, most functions are available directly in pari.

But not those needing closures, see comment:16 and #18038

I see! Do you mind adding a comment in the docstring saying that as soon as #18038 is ready, this can be modified?

5. What is the purpose of the commented code?

I didn't want to erase useful ideas of the original author.

Why letting it commented then?

Vincent

[videlec]

comment:41

Replying to @videlec:

Hello,

Replying to @rwst:

Replying to @videlec:

2. Why is this new module in sage.modular? It makes no sense.

The Dirichlet characters are there too. I don't see why not.

Because sage.modular is intended for modular forms. A Dirichlet serie is not necessarily a modular form. To me, modules and submodules should work by inclusion. Or at least try to.

I do not see Dirichlet series as a subset of modular forms. I perfectly understand the reason why it is here, but it would be better in sage.functions or sage.rings. The directory sage.modular really contains too much stuff. This is historical as people that initiated Sage were very interested in modular forms.

What do you think of sage.lfunctions?

Vincent

[rwst]

comment:42

Replying to @videlec:

What do you think of sage.lfunctions?

What else would you put in there (I have no idea myself)?

[videlec]

comment:43

Replying to @rwst:

Replying to @videlec:

What do you think of sage.lfunctions?

What else would you put in there (I have no idea myself)?

You can first have a look to what is already in.

[rwst]

comment:44

I vaguely remember having had a look at some time but now I see you're right.

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

comment:45

Replying to @rwst:

I vaguely remember having had a look at some time but now I see you're right.

Note that L-function / L-series usual refer to functions / series satisfying some very specific (more restrictive) set of axioms (AC/FE/etc) - in contrast to Dirichlet series or abstract Dirichlet series. So there is definitely some justification for introducing a new class (at least if it supports exact representation).

Also if I remember correctly the L-function is not an exact representation but also restricted by precision. What I would like to see is support for exact abstract Dirichlet series, e.g. by using symbolic coefficient functions or by using exact generating series in terms of rational functions.

If they are not implemented in an exact way I am curious about the background: How / in what context will they be used? Why is a new class required?

In any case I agree that Dirichlet series don't belong to sage.modular.

Best Jonas