Opened 11 years ago

Last modified 2 months ago

#4618 needs_info enhancement

Puiseux series

Reported by: ljpk Owned by: AlexGhitza
Priority: minor Milestone: sage-8.9
Component: algebra Keywords: Puiseux, days100
Cc: mmezzarobba, vdelecroix, dkrenn Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: public/4618 (Commits) Commit: e0c03113eaa38ec5ce101d16332b81ecf9ce70d8
Dependencies: #24420, #24431 Stopgaps:

Description (last modified by vdelecroix)

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.

Change History (46)

comment:1 Changed 11 years ago by mabshoff

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

comment:2 Changed 11 years ago by AlexGhitza

  • Type changed from defect to enhancement

comment:3 Changed 10 years ago by AlexGhitza

  • Component changed from linear algebra to algebra
  • Owner changed from was to AlexGhitza
  • Report Upstream set to N/A

comment:4 Changed 8 years ago by kcrisman

See also #9555.

comment:5 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 6 years ago by chapoton

  • Keywords Puiseux added

comment:8 Changed 6 years ago by rws

  • Description modified (diff)

comment:9 Changed 6 years ago by rws

  • Description modified (diff)

comment:10 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:11 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:12 Changed 5 years ago by kcrisman

See also #9289.

comment:13 Changed 5 years ago by rws

  • Milestone changed from sage-6.4 to sage-wishlist

comment:15 Changed 4 years ago by cswiercz

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.

comment:16 Changed 4 years ago by chapoton

  • Branch set to public/4618
  • Commit set to 7c6e9fbd65e4b19eed62d8cc8d8694659b49e996

just made a git branch, not tested at all


New commits:

7c6e9fbtrac #4618 creating a branch from Chris Swierczewski code

comment:17 Changed 4 years ago by git

  • Commit changed from 7c6e9fbd65e4b19eed62d8cc8d8694659b49e996 to a828db5df2268a20bea62b83033c2325f7cfeaca

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

a828db5trac #4618 details, not working yet

comment:18 Changed 4 years ago by git

  • Commit changed from a828db5df2268a20bea62b83033c2325f7cfeaca to 0e38712d192a35f9cf35d1c92e053b412ad8e940

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

0e38712trac #4618 now working

comment:19 Changed 4 years ago by git

  • Commit changed from 0e38712d192a35f9cf35d1c92e053b412ad8e940 to 8fe475bada98e8b7a2912693525f56d036dcaa10

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

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

comment:20 Changed 4 years ago by git

  • Commit changed from 8fe475bada98e8b7a2912693525f56d036dcaa10 to 2e05bc8e741b8f943f4fedff664e24a1f8ba9bc7

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

5ecc828Merge branch 'public/4618' into 7.2.b1
2e05bc8trac #4618 some more doc, and removed puiseux.py

comment:21 Changed 4 years ago by mmezzarobba

  • Cc mmezzarobba added

comment:22 Changed 4 years ago by git

  • Commit changed from 2e05bc8e741b8f943f4fedff664e24a1f8ba9bc7 to 9af42db0e6db06161e484f318e456e664cbf9ebc

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

9af42dbtrac #4618 some more doc and tests

comment:23 Changed 3 years ago by git

  • Commit changed from 9af42db0e6db06161e484f318e456e664cbf9ebc to 98afe229b00ae434a5a2bd4849bf94081ff39bca

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

ec9dbc3Merge branch 'public/4618' into 7.2.rc1
98afe22puiseux series, more doc, moved a method to Laurent series

comment:24 Changed 3 years ago by mmarco

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.

comment:25 Changed 3 years ago by chapoton

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%

Last edited 3 years ago by chapoton (previous) (diff)

comment:26 Changed 22 months ago by vdelecroix

  • Cc vdelecroix added

comment:27 Changed 22 months ago by vdelecroix

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

comment:28 follow-up: Changed 22 months ago by vdelecroix

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.

comment:29 Changed 22 months ago by vdelecroix

  • Dependencies set to #24420, #24431

comment:30 Changed 22 months ago by vdelecroix

  • Description modified (diff)
  • Milestone changed from sage-wishlist to sage-8.2
  • Summary changed from Request for Puiseux series in SAGE to Puiseux series

comment:31 Changed 22 months ago by dkrenn

  • Cc dkrenn added

comment:32 Changed 6 months ago by git

  • Commit changed from 98afe229b00ae434a5a2bd4849bf94081ff39bca to a922e2acef3c871a23600de9d299d210673fcee4

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

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

comment:33 Changed 6 months ago by soehms

I do the following changes:

  1. Adaptation to current version 8.8.beta3 in order to have the code compile again.
  2. 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).
  3. 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).
  4. I add more doctests.

There is still work to do, for example:

  1. 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:
    1. 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.
    2. 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.
  1. 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?
  1. 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)
    
  1. Further doctests are needed.
  2. Integration into documentation.

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

comment:34 Changed 3 months ago by soehms

  • Keywords days100 added

comment:35 Changed 3 months ago by vdelecroix

  • Milestone changed from sage-8.2 to sage-8.9

comment:36 follow-up: Changed 3 months ago by chapoton

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

comment:37 Changed 3 months ago by soehms

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.

comment:38 in reply to: ↑ 36 Changed 3 months ago by soehms

Replying to chapoton:

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)!

comment:39 Changed 3 months ago by git

  • Commit changed from a922e2acef3c871a23600de9d299d210673fcee4 to 506d2dce9874e9bd913a04928cb60da9e168ccda

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

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

comment:40 in reply to: ↑ 28 ; follow-up: Changed 3 months ago by vdelecroix

Replying to vdelecroix:

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/

comment:41 Changed 3 months ago by git

  • Commit changed from 506d2dce9874e9bd913a04928cb60da9e168ccda to e0c03113eaa38ec5ce101d16332b81ecf9ce70d8

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

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

comment:42 in reply to: ↑ 40 Changed 3 months ago by soehms

Replying to vdelecroix:

Replying to vdelecroix:

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?

comment:43 follow-up: Changed 3 months ago by chapoton

I think that V stand for Verschiebung.

comment:44 in reply to: ↑ 43 ; follow-up: Changed 3 months ago by soehms

Replying to chapoton:

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?

comment:45 in reply to: ↑ 44 ; follow-up: Changed 2 months ago by kcrisman

Replying to soehms:

Replying to chapoton:

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?

comment:46 in reply to: ↑ 45 Changed 2 months ago by soehms

  • Status changed from new to needs_info

Replying to kcrisman:

Replying to soehms:

Replying to chapoton:

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?

Note: See TracTickets for help on using tickets.