Puiseux series

[sagetrac-ljpk]

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

[sagetrac-mabshoff]

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]

comment:4

See also #9555.

[fchapoton]

Changed keywords from none to Puiseux

[kcrisman]

comment:12

See also #9289.

[fchapoton]

comment:14

some code is available here:

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

[cswiercz]

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]

comment:16

just made a git branch, not tested at all

---

New commits:

7c6e9fb

trac #4618 creating a branch from Chris Swierczewski code

[tscrim]

comment:61

Unfortunately I have some more comments that I think should be addressed before a positive review:

In _coerce_map_from_:

         EXAMPLES::
+
             sage: R.<x> = PuiseuxSeriesRing(ZZ)

Also, some small doc tweaks:

 cdef class PuiseuxSeries(AlgebraElement):
     r"""
+    A Puiseux series.
+
     We store a Puiseux series

Common practice is to have the __init__ be the first method, and all of its doc should be moved to the class-level doc (with some formatting improvements done) with a TestSuite(foo).run() being in the __init__'s docstring.

IIRC long is going away in Python3, and better overall I think would be a size_t for the _e attribute. Also, since _l is a Laurent series, shouldn't it also be a LaurentSeries object.

Why also is laurent_part a @property and not just a normal method? (I think p.laurent_part() is actually wrong because of this and should be p.laurent_part, but that is moot if that changes.)

Probably good idea to break encapsulation and not have the function call here: return self._l.laurent_polynomial()(t) (i.e., just access the underlying polynomial).

For the _richcmp_, I think it would be a good idea to not call V on the underlying Laurent polynomials and instead implement a proper comparison as this will be significantly faster.

I think we should change the MIT license to our standard license. I believe this is compatible.

[sagetrac-git]

Changed commit from da3718d to 485102c

[sagetrac-git]

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

485102c

4618: corrections according to reviewers suggestions

[soehms]

comment:63

All your suggestions seem to be reasonable to me.

[tscrim]

comment:64

Thank you. Some last little things: all INPUT: blocks should not end in a period/full-stop (unless it is really long). Also these specific changes:

         - ``prec`` -- (default: ``infinity``) the precision of the series
-            as a rational number.
+          as a rational number

-    - ``parent`` -- Ring, the target parent.
+    - ``parent`` -- the parent ring
 
     - ``f``  -- one of the following types of inputs:
-        - instance of :class:`PuiseuxSeries`
-        - instance that can be coerced into the Laurent sersies ring of the parent.
+
+      * instance of :class:`PuiseuxSeries`
+      * instance that can be coerced into the Laurent series ring of the parent
 
-    - ``e`` -- integer (optional, default 1) for setting the ramification index.
+    - ``e`` -- integer (default: 1); the ramification index

     def __init__(self, parent, f, e=1):
         r"""
+        Initialize ``self``.
+
-        TESTS:
+        TESTS::

-Applies :meth:`shift` using the operator `<<`
+Apply :meth:`shift` using the operator `<<`.

[sagetrac-git]

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

99f43aa

4618: docstring formatting

[sagetrac-git]

Changed commit from 485102c to 99f43aa

[soehms]

comment:66

Replying to @tscrim:

Thank you. Some last little things:

Done!

[tscrim]

comment:67

Thank you. Positive review.

[soehms]

comment:68

Thanks a lot, as well!

[vbraun]

Changed branch from public/4618 to 99f43aa

[slel]

comment:70

Did this also solve #9289 (Implement Puiseux polynomials)?

[slel]

Changed commit from 99f43aa to none

[tscrim]

comment:71

Replying to @slel:

Did this also solve #9289 (Implement Puiseux polynomials)?

Implicitly, but not really since we should have a dedicated parent and element for the polynomials.

[soehms]

comment:72

Replying to @tscrim:

Replying to @slel:

Did this also solve #9289 (Implement Puiseux polynomials)?

Implicitly, but not really since we should have a dedicated parent and element for the polynomials.

But maybe it's a good idea to have the implementation of the Puiseux polynomial rely as much as possible on the Puiseux series. That would avoid having a lot of duplicated code. At the moment the code attached to ticket #9289 is not far away from being copy pasted from the corresponding classes for Laurent polynomials with some name refactoring done. So we would not loose that much if we decide to implement the Puiseux polynomials as "restricted Puiseux series".

What is standing against that?

[tscrim]

comment:73

That would work, but it would likely be slow. I think the thing to do is follow the same pattern as here: extend the Laurent polynomials by wrapping them as a Puiseux polynomial with the ramification index and associated methods. Perhaps to avoid some code duplication, one could be clever with a template class or common ABC.

[soehms]

comment:74

Replying to @tscrim:

That would work, but it would likely be slow.

Travis, I don't see the point of what would make that noticeable slower. I think all calculation that could harm performance will be executed inside polynomial classes independent on how we translate it to them. A little bit more time used for the translation because there is one step more cannot amount that much.

What I have in mind is similar to how I did the embedding of the localization into the fraction field (via a value attribute). In the meantime I've seen that there is a special class ElementWrapper for such constructions (I hadn't been aware of it when implementing the localization).

[tscrim]

comment:75

It is a bit more than that one step. IIRC, there are also a lot more optimizations than can and are done for polynomials that are not available for power series. For one, they don't have to worry about precision. So arithmetic starts to get bogged down by this. Plus that extra level of indirection does add a bit of time (also in creating the extra elements, which is much slower than the function call). While it is not much, perhaps 2-5%, because arithmetic operations are often used in tight loops (and frequently), this can have an outsized impact on algorithm run times.

[soehms]

comment:76

Replying to @tscrim:

Thanks for the explanations! I will think about your suggestion to capsule common functionalities in a template class. Do you mean a class that will be put in between CommutativeAlgebraElement and PuiseuxPolynomial repectively in between AlgebraElement and PuiseuxSeries? But maybe, we should have done #28992 before.

BTW: is there a special reason why the series are not inherited from CommutativeAlgebraElement?

[tscrim]

comment:77

There is the Polynomial class IIRC, but between that and PuiseuxPolynomial, yes. It would mostly be the Laurent polynomial code with the rammification index, but for the more time critical operations, it would just use the fact that the index is 1. Hopefully this would be minimal, but definitely all of the arithmetic operations would fall under this.

[tscrim]

comment:78

I also don't remember if there was some specific reason why it doesn't.