Puiseux series - Githubissues

af34da7a-5b1a-45c9-aac1-252621303487 commented 15 years ago

We provide an implementation of Puiseux series, that is power series in x^(1/n) where n is an arbitrary integer.

When the base ring is an algebraically closed field, this is an algebraically closed field. In other words, any polynomial in QQ[X,Y] has a solution in Y as a Puiseux series in X over QQbar.

Depends on #24420 Depends on #24431 Depends on #28239

CC: @mezzarobba @videlec @dkrenn

Component: algebra

Keywords: Puiseux, days100

Author: Chris Swierczewski

Branch: 99f43aa

Reviewer: Travis Scrimshaw, Frédéric Chapoton, Sebastian Oehms

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

85eec1a4-3d04-4b4d-b711-d4db03337c41 commented 15 years ago

comment:1

Hi ljpk,

requests like this shouls always go to [sage-devel] too since people generally do not look for things to do in trac. Sending the same request to [sage-devel] will make people aware of the problem and might get some design discussion going. Obviously if you are working on code this is different, but if you expect someone else to do the dirty work a little advertisement cannot hurt :)

Cheers,

Michael

kcrisman commented 13 years ago

comment:4

-From the duplicate #9289:

-```

sage: S = PolynomialRing(QQ, ['a','b','c']); S
Multivariate Puiseux Polynomial Ring in a, b, c over Rational Field -```
-Operations: roots of monomials, ...
-See also: http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Puiseux, http://en.wikipedia.org/wiki/Puiseux_series

kcrisman commented 9 years ago

comment:12

See also #9289.

fchapoton commented 8 years ago

comment:14

some code is available here:

https://github.com/abelfunctions/abelfunctions/tree/master/abelfunctions

3421e925-4b79-48cc-ba65-9123d4ab1b38 commented 8 years ago

comment:15

As mentioned in an email correspondence with chapoton I believe my implementation of PuiseuxSeriesRing and PuiseuxSeriesRingElementto be pretty complete in regards to fitting into Sage's coercion model. Hopefully it will, at the very least, be a good starting point.

Thanks to chapoton for offering to plug this code into Sage!

On a side note, I also have some code for computing Puiseux series representations of places on a plane algebraic curve. The entry function is abelfunctions.puiseux_series.puiseux_series. I'm sure someone with better Sage skills than myself can improve the algorithm and plug that in as well.

fchapoton commented 8 years ago

comment:16

just made a git branch, not tested at all

New commits:

7c6e9fb trac #4618 creating a branch from Chris Swierczewski code

fchapoton commented 8 years ago

Branch: public/4618

fchapoton commented 8 years ago

Commit: 7c6e9fb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

a828db5 trac #4618 details, not working yet

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 7c6e9fb to a828db5

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from a828db5 to 0e38712

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

0e38712 trac #4618 now working

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

8fe475b trac #4618, now working a little bit more, and added some doc

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 0e38712 to 8fe475b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`5ecc828`	`Merge branch 'public/4618' into 7.2.b1`
`2e05bc8`	`trac #4618 some more doc, and removed puiseux.py`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 8fe475b to 2e05bc8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 2e05bc8 to 9af42db

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

9af42db trac #4618 some more doc and tests

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`ec9dbc3`	`Merge branch 'public/4618' into 7.2.rc1`
`98afe22`	`puiseux series, more doc, moved a method to Laurent series`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 9af42db to 98afe22

miguelmarco commented 7 years ago

comment:24

This is a nice addition. Is it ready for review?

A few comments:

Is it planned to extend it to the multivariate case?
It would be nice to add a more detailed mathematical explanation about what a Puiseux series is in the docstring.

fchapoton commented 7 years ago

comment:25

It is probably not ready, there seems to be a bug lurking around.

No plan to implement the multivariate case.

and the coverage is not 100%

videlec commented 6 years ago

comment:27

This is needed to allow extend=True for the nth_root method in #10720 (see also this sage-devel thread).

videlec commented 6 years ago

comment:28

An innocent operation like the following will multiply the memory footprint by 24 with no change in information

sage: p = prod(1 - q^n + O(q^100) for n in range(1,100))   # fine: 100 * coeff size
sage: q^(1/24) * p   # bad: 100 * 24 * coeff size

The above example is the q-series expansion of the Dedekind eta function. There might be a more clever data structure to use as this kind of series is frequently encountered when dealing with modular forms.

videlec commented 6 years ago

Dependencies: #24420, #24431

videlec commented 6 years ago

Description changed:

--- 
+++ 
@@ -1,15 +1,3 @@
-In MAGMA, one can have fractional exponents for power series (which it calls Puiseux series), but SAGE does not seem to support this:
+We provide an implementation of Puiseux series, that is power series in `x^(1/n)` where `n` is an arbitrary integer.

-```
-sage: PSR.<q>=PowerSeriesRing(QQ)
-sage: q^(1/5)
----------------------------------------------------------------------------
-NotImplementedError                       Traceback (most recent call last)
-
-/home/ljpk/.sage/temp/sage/2339/_home_ljpk_Eisenstein_sage_9.py in <module>()
-/home/was/s/local/lib/python2.5/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__pow__ (sage/structure/element.c:8866)()
-/home/was/s/local/lib/python2.5/site-packages/sage/structure/element.so in sage.structure.element.generic_power_c (sage/structure/element.c:17789)()
-
-NotImplementedError: non-integral exponents not supported
-```
-
+When the base ring is an algebraically closed field, this is an algebraically closed field. In other words, any polynomial in `QQ[X,Y]` has a solution in `Y` as a Puiseux series in `X` over `QQbar`.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

`927b88d`	`Merge branch 'public/4618' of git://trac.sagemath.org/sage into puiseux_series_4618`
`a922e2a`	`trac #4618: have it compile again and some corrections`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 98afe22 to a922e2a

soehms commented 5 years ago

comment:33

I do the following changes:

Adaptation to current version 8.8.beta3 in order to have the code compile again.
I replace the method _cmp_ of PuiseuxSeries by _richcmp_ and let it completely rely on the corresponding method of class LaurentSeries. The reason for this is not only modernisation, but also that the former method doesn't work correctly (for example comparison with zero returns wrong results).
I add a specification of the representative of the Puiseux series inside the constructor of PuiseuxSeries in such a way that the ramification index is minimized. This improves the methods laurent_series and power_series (the examples given there would not work else-wise).
I add more doctests.

There is still work to do, for example:

There are several workarounds on other bugs in Sage. In general I think, these workarounds should be removed and the corresponding bugs should be treated in separate tickets. Examples: a. In the methods _repr_, exponents and coefficients there is the following comment: NOTE: self.__l.coefficients() is bugged when the coefficients are in QQbar but coerced into SR .... I have no idea how far it makes sense to consider Puiseux series (Laurent series, polynomial rings, ...) over the SymbolicRing. But since these constructions are possible, they should work (or should be blocked). There are simple examples where this is not the case:

sage: PS = PolynomialRing(SR,'x')
sage: P = PolynomialRing(QQ,'x')
sage: q = P((1,1,5)); q
5*x^2 + x + 1
sage: p = PS(q)
sage: p.coefficients()
[5*x^2 + x + 1]
sage: p in SR
True

Is this a known bug? Concerning the methods in question, I think that they should rely more directly on the according methods of `LaurentSeries`.

b. In the method add_bigoh the following error is caught:

sage: L.<x> = LaurentSeriesRing(QQ)
sage: q = x^2 + x^3
sage: q.add_bigoh(-1)
Traceback (most recent call last):
...
ValueError: prec (= -3) must be non-negative

This should be fixed in `LaurentSeries`.

I think we should clarify the following behavior of the method add_bigoh:

sage: R.<x> = PuiseuxSeriesRing(ZZ)
sage: p = x**(-1/3) + 2*x**(1/5)
sage: p.add_bigoh(1/2)
x^(-1/3) + 2*x^(1/5) + O(x^(7/15))

is this acceptable?

The method _repr_ needs work:

sage: R.<x> = PuiseuxSeriesRing(Zp(5))
sage: x**(1/2) + 5 * x^(1/3)
5 + O(5^21)*x^(1/3) + (1 + O(5^20))*x^(1/2)

Further doctests are needed.
Integration into documentation.

I will continue to work on this ticket according to feedback!

soehms commented 5 years ago

Changed keywords from Puiseux to Puiseux, days100

fchapoton commented 5 years ago

comment:36

There is a hash doctest failure with python3:

sage -t --long src/sage/rings/puiseux_series_ring_element.pyx
**********************************************************************
File "src/sage/rings/puiseux_series_ring_element.pyx", line 549, in sage.rings.puiseux_series_ring_element.PuiseuxSeries.__hash__
Failed example:
    hash(p)  # indirect doctest
Expected:
    -15360174648385722
Got:
    8039939419124139326

soehms commented 5 years ago

comment:37

In agreement with Frédéric I have created the tickets #28238 and #28239 to treat the external bugs mentioned in comment 32. The according workarounds in the code can be removed.

soehms commented 5 years ago

comment:38

Replying to @fchapoton:

There is a hash doctest failure with python3:

sage -t --long src/sage/rings/puiseux_series_ring_element.pyx
**********************************************************************
File "src/sage/rings/puiseux_series_ring_element.pyx", line 549, in sage.rings.puiseux_series_ring_element.PuiseuxSeries.__hash__
Failed example:
    hash(p)  # indirect doctest
Expected:
    -15360174648385722
Got:
    8039939419124139326

I will look at that at home (since I have no sage with python3 on the computer I am carrying with me)!

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

`afb0acc`	`Merge branch 'public/4618' of git://trac.sagemath.org/sage into puiseux_series_4618`
`506d2dc`	4618: fixing doctest of `__hash__` and remove workaround for #28239

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from a922e2a to 506d2dc

videlec commented 5 years ago

comment:40

Replying to @videlec:

An innocent operation like the following will multiply the memory footprint by 24 with no change in information
sage: p = prod(1 - q^n + O(q^100) for n in range(1,100))   # fine: 100 * coeff size
sage: q^(1/24) * p   # bad: 100 * 24 * coeff size
The above example is the q-series expansion of the Dedekind eta function. There might be a more clever data structure to use as this kind of series is frequently encountered when dealing with modular forms.

Concerning this example, you might want to read https://oscar.computeralgebra.de/blogs/2018/08/03/PuiseuxSeries/

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 506d2dc to e0c0311

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

e0c0311 4618: remove workaround for #28238 and add a Note to add_bigoh

soehms commented 5 years ago

comment:42

Replying to @videlec:

Replying to @videlec:
An innocent operation like the following will multiply the memory footprint by 24 with no change in information
sage: p = prod(1 - q^n + O(q^100) for n in range(1,100))   # fine: 100 * coeff size
sage: q^(1/24) * p   # bad: 100 * 24 * coeff size
The above example is the q-series expansion of the Dedekind eta function. There might be a more clever data structure to use as this kind of series is frequently encountered when dealing with modular forms.
Concerning this example, you might want to read https://oscar.computeralgebra.de/blogs/2018/08/03/PuiseuxSeries/

The multiplication of memory-size is caused by the call of the V-method (implemented for Puiseux series) in the Laurent series class but it happens in the polynomial attached to the power series of the attached Laurent series.

sage: P.<q> = PuiseuxSeriesRing(QQ)
sage: p = prod((1 - q^n).add_bigoh(100) for n in range(1,100))
sage: t = q^(1/24) * p
sage: s = t.laurent_part().valuation_zero_part().polynomial()
sage: len(s.list())
2209
sage: len(p.laurent_part().valuation_zero_part().polynomial().list())
93

So the most generic option would be to implement a data-compression in the corresponding polynomial class. But this may involve external software as in the case of the example:

sage: type(s)
<type 'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint'>

The same thing is true concerening the level of power series (for exmaple choosing implementation='pari'). So I think, the best place for implementing a smarter data structure would be the Laurent series class and could be done there by a scale factor as it is mentined in the article concerning the implementation in OSCAR: "Laurent series themselves are also stored with a valuation, precision and a scale factor".

My suggestion is, to open a new ticket on that task concerning such an implementation for the Laurent series. The method V should than just change the scale factor (instead of stretching the data volume). The implementaion of the Puiseux series could stay as it is. In opposite to ramifications_index to new scale factor could be named covering_index, for instance.

BTW: what does this V stand for?

fchapoton commented 5 years ago

comment:43

I think that V stand for Verschiebung.

soehms commented 5 years ago

comment:44

Replying to @fchapoton:

I think that V stand for Verschiebung.

That sounds as if we should look for a better name! I even don't see a connection. The only mathematical meaning of Verschiebung I know is that of a translation in euclidean geometry. What about to replace V by power_inflation?

kcrisman commented 5 years ago

comment:45

Replying to @soehms:

Replying to @fchapoton:

I think that V stand for Verschiebung.

That sounds as if we should look for a better name! I even don't see a connection. The only mathematical meaning of Verschiebung I know is that of a translation in euclidean geometry.

It is probably from Witt vector terminology, where that is a standard term?

soehms commented 5 years ago

comment:46

Replying to @kcrisman:

Replying to @soehms:

Replying to @fchapoton:

I think that V stand for Verschiebung.

That sounds as if we should look for a better name! I even don't see a connection. The only mathematical meaning of Verschiebung I know is that of a translation in euclidean geometry.

It is probably from Witt vector terminology, where that is a standard term?

Thanks for the explanation! Indeed, that meaning of Verschiebung hasn't been present in my mind. But anyway, I would prefer a method name that doesn't dependent on any special context (and has more than just one letter). The V could by kept as an alias (together with an appropriate explanation). Opinions?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

`33bf6af`	`Merge branch 'public/4618' of git://trac.sagemath.org/sage into public/4618`
`637cf86`	`Updating the framework to use UniqueRepresentation and a few other misc changes.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from e0c0311 to 637cf86

tscrim commented 4 years ago

comment:48

I added a long form verschiebung to the Laurent series with V as an alias. I also brought the class up to our current framework with UniqueRepresentation and better use of the category framework. I also fixed a bunch of places in the doc and other misc code changes. There are still some doctests missing, but code-wise I think this is acceptable for inclusion (we can always make additional changes later).

Although there is a substantial overlap with the code for Laurent series. I almost feel like we should just extend the Laurent series class with the necessary features with _e to avoid duplication (that one extra little bit of information shouldn't change the speed or have a real affect on memory).

tscrim commented 4 years ago

Reviewer: Travis Scrimshaw

sagemath / sage

Puiseux series #4618

-From the duplicate #9289: