Lazy Dirichlet Series

[mantepse]

We implement lazy Dirichlet series. For example,

sage: L = LazyDirichletSeriesRing(ZZ, "z")
sage: g = L(constant=1); g
1 + 1/(2^z) + 1/(3^z) + ...
sage: g*g
1 + 2/2^z + 2/3^z + 3/4^z + 2/5^z + 4/6^z + 2/7^z + ...
sage: [number_of_divisors(n) for n in range(1, 8)]
[1, 2, 2, 3, 2, 4, 2]

sage: mu = L(moebius); mu
1 + -1/2^z + -1/3^z + -1/5^z + 1/(6^z) + -1/7^z + ...
sage: g*mu
1 + ...

sage: g = L([0], constant=1)
sage: F = L(None)
sage: F.define(1 + g*F)
sage: ff = [F[i] for i in range(1, 16)]; ff
[1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3]
sage: oeis(ff)                              # optional, internet
0: A002033: Number of perfect partitions of n.
1: A074206: Kalmár's [Kalmar's] problem: number of ordered factorizations of n.
...

CC: @tscrim @tejasvicsr1 @slel @kcrisman

Component: combinatorics

Keywords: LazyPowerSeries, FormalSeries

Author: Martin Rubey, Travis Scrimshaw

Branch/Commit: 5b48191

Reviewer: Travis Scrimshaw, Martin Rubey

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

[mantepse]

Branch: u/mantepse/lazy_dirichlet_series

[mantepse]

Commit: 21bb3e3

[mantepse]

Last 10 new commits:

937fc6d	Basic documentation for coefficient stream code.
b136d70	Improve speed of inv by using the cache.
5cd5b4d	Fix bug with inverse.
4b4c3aa	Merge branch 'u/tscrim/dense_lls-31897' of trac.sagemath.org:sage into t/31897/a_dense_implementation_for_the_lazy_laurent_series
e27da4b	Corrected coefficient stream file.
525409b	Added documentation for the coefficient_stream file.
fd6549a	Removing json file that should not be there.
4b7efa3	Fixing up some documentation and doctests.
5f84431	Merge branch 'u/tscrim/dense_lls-31897' of git://trac.sagemath.org/sage into t/32309/lazy_dirichlet_series
21bb3e3	initial version

[mantepse]

Dependencies: #31897

[mantepse]

Changed keywords from none to LazyPowerSeries, FormalSeries

[mantepse]

Author: Martin Rubey

[sagetrac-git]

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

e5c89c9	Started moving eventually_geometric to exact. There are still many issues left.
799e22c	CS_eventually_geometric is now CS_exact
f450bbd	Merge branch 'u/gh-tejasvicsr1/dense_lls-31897' of git://trac.sagemath.org/sage into t/32309/lazy_dirichlet_series

[sagetrac-git]

Changed commit from 21bb3e3 to f450bbd

[sagetrac-git]

Changed commit from f450bbd to a5e5aea

[sagetrac-git]

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

97bb021	fix doctests
d904d6d	Merge branch 'u/mantepse/dense_lls-31897' of git://trac.sagemath.org/sage into t/32309/lazy_dirichlet_series
a5e5aea	fix doctests

[sagetrac-git]

Changed commit from a5e5aea to 65210a3

[sagetrac-git]

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

65210a3

factor out add

[sagetrac-git]

Changed commit from 65210a3 to 346e2b6

[sagetrac-git]

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

346e2b6

factor out _lmul_

[sagetrac-git]

Changed commit from 346e2b6 to 2015cfe

[sagetrac-git]

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

2015cfe

factor out remaining common methods

[sagetrac-git]

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

12e127c	backport code factorization from #32309
42cdf7a	Added CS_recursive method, fixed the apply_coeff method, and corrected some documentation.
ed3e8a4	Merge branch 'u/gh-tejasvicsr1/dense_lls-31897' of git://trac.sagemath.org/sage into t/32309/lazy_dirichlet_series

[sagetrac-git]

Changed commit from 2015cfe to ed3e8a4

[sagetrac-git]

Changed commit from ed3e8a4 to 5d856df

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

3b3e0cd	Completed the second iteration of the documentation.
ee9d593	Fixed tiny bug in composition code
2be305d	Small error fixed, typos fixed.
0726785	Merge branch 'u/gh-tejasvicsr1/dense_lls-31897' of git://trac.sagemath.org/sage into u/tscrim/dense_lls-31897
e31b75e	Fixing bug in CS_apply_coeff.
d75d44c	Refactoring out the CS_exact polynomial creation and doc fixes.
e0328c8	Changing `_an_element_`, printing O(z^k), and added global option.
3db49f1	Improving documentation and partially resurrecting series().
bbc1668	Removing CS_recursion.
5d856df	Merge branch 'u/tscrim/dense_lls-31897' of git://trac.sagemath.org/sage into t/32309/lazy_dirichlet_series

[fchapoton]

comment:14

when using latex command in the doc, you need to start with r""" instead of """

For example, when using `\infty`

[mantepse]

comment:15

Thank you for the hint, I tend to overlook this :-9

Warning: this ticket is currently not updated, the newest version is in #32324 and #32345, because it turned out to be important to get a broader view on the lazy framework. Once this framework is stable (very likely soon after #31897 is in), I will probably backport, if that makes review easier.

[sagetrac-git]

Changed commit from f72ebca to 0f2355f

[tscrim]

comment:62

Replying to @mantepse:

Wow, you put in a lot of work!

I don't really understand the meaning of _internal_poly_ring yet.

It is something that we use to internally to manipulate things. Mainly it is a way around the shift issue (although with a bit more data preprocessing in the Dirichlet _element_constructor_, it might become redundant; this was the lazier approach).

There is one issue, which is important to me (and a doctest in the Taylor ticket, which, for some reason, I overlooked while backporting). I am against ordinary polynomials being re-interpreted as Dirichlet series. This is going to be a source of bugs which are very hard to understand.

sage: D = LazyDirichletSeriesRing(ZZ, 't')
sage: m = D(moebius); m
1 - 1/(2^t) - 1/(3^t) - 1/(5^t) + 1/(6^t) - 1/(7^t) + O(1/(8^t))
sage: P.<x, y> = QQ[]
sage: L.<z> = LazyLaurentSeriesRing(P)
sage: L(m)
z - z^2 - z^3 - z^5 + z^6 - z^7 + O(z^8)

When you say ordinary polynomials, do you mean Laurent/Taylor/etc. series? I think this conversion is fine; it is not a coercion. IMO, we should trust that users knows what they is doing. We should not go out of our way to tell users they are misusing something. However, if you feel strongly about it, I know a way to easily extend things to stop this conversion, but I think it is a small bit of technical debt.

Also, continuing with the definitions above, I think the below is at least fishy:

sage: R.<q> = QQ[]
sage: L(q)
z
sage: L(x)
x
sage: D(q)
1
sage: L(q^-1)
z^-1
sage: D(q^-1)
1
sage: D(x)
<repr(<sage.rings.lazy_series_ring.LazyDirichletSeriesRing_with_category.element_class at 0x7faeaca0c640>) failed: TypeError: number of arguments does not match number of variables in parent>

I have fixed it so that D(q^-1) no longer thinks it is a valid series.

Note that the element constructor for polynomials is stricter here, and I think that this is how it should be:

sage: R(x)
...
TypeError: not a constant polynomial

I am pretty sure we cannot do anything better here because we take callables as valid input and perhaps someone wants to use a polynomial (which doesn't convert into the internal poly ring) to compute coefficients. I believe your previous code would have the same behavior.

[mantepse]

comment:63

Replying to @tscrim:

Replying to @mantepse:

I don't really understand the meaning of _internal_poly_ring yet.

It is something that we use to internally to manipulate things. Mainly it is a way around the shift issue (although with a bit more data preprocessing in the Dirichlet _element_constructor_, it might become redundant; this was the lazier approach).

I cannot remember what the shift issue is, sorry.

When you say ordinary polynomials, do you mean Laurent/Taylor/etc. series?

Both. I think that all of the following should raise errors:

sage: L.<z> = LazyLaurentSeriesRing(QQ)
sage: D = LazyDirichletSeriesRing(QQ, 't')
sage: P.<q> = QQ[]
sage: D(z) # this is extremely fishy, the result is not in the correct ring
z
sage: D(q)
1
sage: D(q) == D(1)
True
sage: L(D([1,2,3]))
z + 2*z^2 + 3*z^3

I was actually mistaken that the polynomial ring would be much stricter, there seems to be some inconsistency:

sage: R.<x,y> = QQ[]
sage: S.<q> = QQ[]
sage: T.<t> = QQ[]
sage: T(q)
t
sage: T(x)
TypeError                                 Traceback (most recent call last)
...
TypeError: not a constant polynomial

I am pretty sure we cannot do anything better here because we take callables as valid input and perhaps someone wants to use a polynomial (which doesn't convert into the internal poly ring) to compute coefficients. I believe your previous code would have the same behavior.

At least before your work, using a polynomial p as a callable (via the coefficients argument) would produce the series with coefficients p(0), p(1), ... in the Laurent case, which I think is fine.

What I think is not correct is that a (Laurent or ordinary) polynomial or a Laurent of Dirichlet series is interpreted as a sequence of coefficients. This didn't happen before, at least not in the Taylor ticket code.

[sagetrac-git]

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

30d3804	Moving shift up and bug fixing.
3cea7f1	Make the Dirichlet series input only convert Dirichlet series.

[sagetrac-git]

Changed commit from 0f2355f to 3cea7f1

[sagetrac-git]

Changed commit from 3cea7f1 to 683bd3c

[sagetrac-git]

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

683bd3c

Fixing pyflakes warnings.

[tscrim]

comment:66

The first was a bug, which I fixed. Then I got rid of that because I implemented a bit of a hack to prohibit what you want (I think that is unnecessary because of the coefficients parameter and it is not wrong to do this) and not have lots of duplicated code.

[mantepse]

comment:67

OK. I am still unhappy about the following:

sage: L.<z> = LazyLaurentSeriesRing(QQ)
sage: D = LazyDirichletSeriesRing(QQ, 't')
sage: L(D(z))
z + 2*z^2 + 3*z^3 + 4*z^4 + 5*z^5 + 6*z^6 + 7*z^7 + O(z^8)
sage: L(D([1,2,3]))
z + 2*z^2 + 3*z^3
sage: D(L([1,2,3]))
6 + 17/2^t + 34/3^t + 57/4^t + 86/5^t + 121/6^t + 162/7^t + O(1/(8^t))

I also think it would be better to disallow polynomial input for Dirichlet series. I would rather require the user here to ask for D(coefficients=q^2+1).

sage: P.<q> = QQ[]
sage: D(q^2+1)
2 + 5/2^t + 10/3^t + 17/4^t + 26/5^t + 37/6^t + 50/7^t + O(1/(8^t))

[mantepse]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Martin Rubey

[mantepse]

Changed author from Martin Rubey to Martin Rubey, Travis Scrimshaw

[sagetrac-git]

Changed commit from 683bd3c to 2b40d39

[sagetrac-git]

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

b2f4cee	Merge branch 'public/rings/lazy_dirichlet_series-32309' of git://trac.sagemath.org/sage into public/rings/lazy_dirichlet_series-32309
2b40d39	Strengthening Laurent series conversion.

[tscrim]

comment:70

Replying to @mantepse:

OK. I am still unhappy about the following:

sage: L.<z> = LazyLaurentSeriesRing(QQ)
sage: D = LazyDirichletSeriesRing(QQ, 't')
sage: L(D(z))
z + 2*z^2 + 3*z^3 + 4*z^4 + 5*z^5 + 6*z^6 + 7*z^7 + O(z^8)
sage: L(D([1,2,3]))
z + 2*z^2 + 3*z^3
sage: D(L([1,2,3]))
6 + 17/2^t + 34/3^t + 57/4^t + 86/5^t + 121/6^t + 162/7^t + O(1/(8^t))

I made it so the first two fail, but they only fail because finite length Dirichlet series are not callable. If they become callable, then it will give a valid series output. I do not want to spend any more time making the code more brittle and complex to prevent some user input that may or may not be unwanted. There is no way to change the last one because it is callable and gets treated like a coefficient function, which is something the user might want. I would get upset as a user if moebius worked without naming the argument but another callable does not.

I also think it would be better to disallow polynomial input for Dirichlet series. I would rather require the user here to ask for D(coefficients=q^2+1).

sage: P.<q> = QQ[]
sage: D(q^2+1)
2 + 5/2^t + 10/3^t + 17/4^t + 26/5^t + 37/6^t + 50/7^t + O(1/(8^t))

See comment above about callables.

Greetings from Japan.

[sagetrac-git]

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

459959f

Merge remote-tracking branch 'trac/develop' into public/rings/lazy_dirichlet_series-32309

[sagetrac-git]

Changed commit from 2b40d39 to 459959f

[dimpase]

comment:72

please check that this merge makes sense.

[sagetrac-tmonteil]

comment:73

Just a small suggestion: the á in Kalmár is not an ASCII letter, hence you should add the line # -*- coding: utf-8 -*- in the beginning of the src/sage/rings/lazy_series.py file.

[dimpase]

Changed dependencies from #31897 to none

[sagetrac-git]

Changed commit from 459959f to 5b48191

[sagetrac-git]

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

5b48191

fix encoding

[mantepse]

comment:76

I agree with your assessment! Thank you!

[tscrim]

comment:77

Replying to @sagetrac-tmonteil:

Just a small suggestion: the á in Kalmár is not an ASCII letter, hence you should add the line # -*- coding: utf-8 -*- in the beginning of the src/sage/rings/lazy_series.py file.

I also said the same thing on another ticket before someone pointed out to me this is no longer necessary now that we are Python3 only.

[vbraun]

Changed branch from public/rings/lazy_dirichlet_series-32309 to 5b48191