Opened 4 years ago

Closed 16 months ago

#14828 closed enhancement (fixed)

Slope factorisation of polynomials over padics

Reported by: caruso Owned by: roed
Priority: major Milestone: sage-7.2
Component: padics Keywords: polynomials, padics, sd52, days71
Cc: defeo Merged in:
Authors: Xavier Caruso, Frédéric Chapoton Reviewers: Julian Rüth, Maurizio Monge
Report Upstream: N/A Work issues:
Branch: 868e84e (Commits) Commit: 868e84eda1d8eef914171b72e3d629b73134e793
Dependencies: Stopgaps:

Description (last modified by saraedum)

Factorization over the p-adics is currently broken (or at least not very useful.) This implements slope factorization and adds some structure for polynomial rings over discrete valuation rings.

Attachments (1)

trac_14828_padic_polynomials.patch (39.8 KB) - added by caruso 4 years ago.

Download all attachments as: .zip

Change History (56)

comment:1 Changed 4 years ago by caruso

  • Dependencies set to #14823, #14826
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by roed

I've basically abandoned the code at #6084, but I would like to extract pieces of it into other tickets. I'll try to take a look at this ticket once its prerequisites are fixed and see if I can extract anything useful from #6084 to add here. You have a different approach to polynomials with unknown degree here. I think I like it better than what I was doing, but I need to think about it a bit.

Changed 4 years ago by caruso

comment:3 Changed 4 years ago by caruso

I updated my patch so that it fits with #14826 (many modifications made there).

Last edited 4 years ago by caruso (previous) (diff)

comment:4 follow-up: Changed 4 years ago by chapoton

Hello,

maybe it would be a good idea to close first the simpler ticket #6667 ?

I have made there a patch which is rather "local" but also careless about precision issues.

I see that here you are changing the behaviour of the general Newton polygon, which I would prefer to avoid.

What would you think of trying to use for #6667 a mixture of my patch there and the part of your patch here dealing with that ?

comment:5 in reply to: ↑ 4 Changed 4 years ago by caruso

I agree with all your remarks.

I just do not understand the sense of "you are changing the behaviour of the general Newton polygon". Do you mean that I'm doing some changes in the class NewtonPolygon. If so, I still believe that it's better to do this way because it really makes sense to create a Newton polygon by giving the list of all valuations of the underlying polynomial (and these valuations may be infinite). Actually, I should have put this modification in #14826 but this ticket is already closed.

comment:6 follow-up: Changed 4 years ago by chapoton

It seems that the NewtonPolygon? class is not doing what I would have expected. It gives

sage: NP = NewtonPolygon([ (0,0), (1,45), (3,6) ]); NP
Finite Newton polygon with 2 vertices: (0, 0), (3, 6)

So it is implicitely assuming that the polytope is rather a kind of "lower envelope". In my opinion, the doc needs to be enhanced, with more explanations and a link to the newton_polytope method below.

Compare to

sage: x,y=polygen(QQ,'x, y')
sage: p = 1 + x*y**45 + x**3*y**6
sage: p.newton_polytope()
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices
sage: p.newton_polytope().vertices()
(A vertex at (0, 0), A vertex at (1, 45), A vertex at (3, 6))

which is for me the expected behavior.

Anyway, I still think that this has rather to be solved in #6667.

comment:7 in reply to: ↑ 6 Changed 4 years ago by caruso

Replying to chapoton:

Anyway, I still think that this has rather to be solved in #6667.

I agree. I nevertheless prefer my patch than yours because it basically deals with precision issues. Hence, I've extracted the relevant parts of my patch and submitted them to ticket #6667 (and I've also taken into account your remarks). If you are happy with this solution, please give a positive review to #6667 so that we can close this ticket.

comment:8 Changed 4 years ago by saraedum

  • Keywords sd52 added

comment:9 Changed 4 years ago by defeo

  • Branch set to public/ticket/14828
  • Created changed from 06/26/13 12:24:24 to 06/26/13 12:24:24
  • Modified changed from 09/02/13 13:03:04 to 09/02/13 13:03:04

comment:10 Changed 4 years ago by defeo

  • Dependencies #14823, #14826 deleted

comment:11 Changed 4 years ago by defeo

  • Dependencies set to #14823, #14826

comment:12 Changed 4 years ago by defeo

  • Cc defeo added
  • Milestone changed from sage-5.12 to sage-6.0

comment:13 Changed 4 years ago by defeo

The mercurial patch conflicted with 5.12-beta4.

I manually solved the conflicts. It seems it passes doctests, but I'll feel much more confident if Xavier reviews the new branch.

comment:14 Changed 4 years ago by defeo

I spoke too fast. I have the following failures

sage -t src/sage/schemes/hyperelliptic_curves/hyperelliptic_padic_field.py  # 3 doctests failed
sage -t src/sage/schemes/elliptic_curves/padic_lseries.py  # 1 doctest failed
sage -t src/sage/misc/classgraph.py  # 3 doctests failed
sage -t src/sage/rings/padics/pow_computer_ext.pyx  # 1 doctest failed

(plus others that look unrelated).

comment:15 Changed 4 years ago by chapoton

It would be better to have #6667 as a dependency, in my humble opinion. The patch in #6667 looks good, but the patchbot has not checked it yet.

comment:16 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:17 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:18 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:19 Changed 3 years ago by git

  • Commit set to c8800dd3368f0bb05b27719b62b889018257c0a6

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

14554cbMerge branch 'public/ticket/14828' of ssh://trac.sagemath.org:22/sage into 14828
c8800ddtrac #14282 merge done, needs to be checked, tests seem to pass

comment:20 Changed 3 years ago by chapoton

  • Authors set to Xavier Caruso, Frédéric Chapoton

comment:21 Changed 3 years ago by saraedum

  • Status changed from needs_review to needs_work

I had a quick lock at this. It seems that many methods/classes lack doctests or docstrings at all. I hope you don't mind that I set this back to needs_work.

comment:22 Changed 3 years ago by git

  • Commit changed from c8800dd3368f0bb05b27719b62b889018257c0a6 to 69ba436cc01833a58b47617c23da38689db3c801

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

5c875ceMerge branch 'public/ticket/14828' of ssh://trac.sagemath.org:22/sage into 14828
69ba436trac #14828 working on doc mainly

comment:23 Changed 3 years ago by git

  • Commit changed from 69ba436cc01833a58b47617c23da38689db3c801 to 8fc61982c456d5b4702b7fcc96ac70b6dc391736

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

8fc6198more on doc

comment:24 Changed 3 years ago by chapoton

Several things are needed :

  • add doc to quo_rem and factor_mod
  • add one-line description at the beginning of several functions

comment:25 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:26 Changed 3 years ago by git

  • Commit changed from 8fc61982c456d5b4702b7fcc96ac70b6dc391736 to 5a1a485c5888b374f8380915eed4fdd3b732d3a5

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

2a9e90cMerge branch 'public/ticket/14828' into 6.4.b6
5a1a485trac #14828 more doc, other minor changes

comment:27 Changed 2 years ago by git

  • Commit changed from 5a1a485c5888b374f8380915eed4fdd3b732d3a5 to d2f52cf0e8631aee2856bbe60dcbb6e0e1dc2920

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

d2f52cfMerge branch 'public/ticket/14828' into 6.5.rc0

comment:28 Changed 2 years ago by jdemeyer

This branch is doing too many things unrelated to the topic of the ticket. I think the changes involving categories and the doctest clean-up should be separated in new tickets.

comment:29 Changed 2 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.8

comment:30 Changed 23 months ago by git

  • Commit changed from d2f52cf0e8631aee2856bbe60dcbb6e0e1dc2920 to bbe959d69bc3868cdc49a2f2cdc8e62d83bc52d5

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

d59c712Merge branch 'public/ticket/14828' into 6.9.b4
bbe959dtrac #14828 trying to make it build again

comment:31 Changed 23 months ago by jdemeyer

  • Dependencies #14823, #14826 deleted
  • Description modified (diff)

comment:32 Changed 23 months ago by git

  • Commit changed from bbe959d69bc3868cdc49a2f2cdc8e62d83bc52d5 to edbf797a6ea03e827122d00895576d945ef6ea8f

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

edbf797trac #14828 trying to make the doc build

comment:33 Changed 21 months ago by git

  • Commit changed from edbf797a6ea03e827122d00895576d945ef6ea8f to 309d3732b825eabf9c7d192c965a7b28fdb512ab

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

309d373Merge branch 'public/ticket/14828' into 6.10.beta3

comment:34 Changed 16 months ago by git

  • Commit changed from 309d3732b825eabf9c7d192c965a7b28fdb512ab to b8cfd47068dfd122946a57cde3767fceed515cc3

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

b8cfd47Merge branch 'develop' into t/14828/public/ticket/14828

comment:35 Changed 16 months ago by git

  • Commit changed from b8cfd47068dfd122946a57cde3767fceed515cc3 to 2dd40c1c25c20943db220947e18bac71d8e6c135

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

7be6780Merge branch 'develop' into t/14828/public/ticket/14828
34581cdadded todo.
2dd40c1fixed doctext failing because of a bug that is no longer there

comment:36 Changed 16 months ago by git

  • Commit changed from 2dd40c1c25c20943db220947e18bac71d8e6c135 to a320013e19516836e69e5944d5e0a8601ecf9ac8

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

a320013More doctests

comment:37 Changed 16 months ago by jdemeyer

I remind you of 28. Doing three unrelated things in one branch is not good practice.

comment:38 Changed 16 months ago by caruso

Yes, thanks for the remainder. I'll try to split my ticket.

Last edited 16 months ago by caruso (previous) (diff)

comment:39 follow-up: Changed 16 months ago by saraedum

I believe that if the authors can find a reviewer then it stay in one ticket. It is not pretty. But it is probably not worth splitting it just for the sake of it.

Last edited 16 months ago by saraedum (previous) (diff)

comment:40 in reply to: ↑ 39 Changed 16 months ago by jdemeyer

Replying to saraedum:

I believe that if the authors can find a reviewer then it stay in one ticket.

True, but you might find it easier to find reviewers if you split it up.

But it is probably not worth splitting it just for the sake of it.

That's certainly true, but I don't think it is splitting "just for the sake of it". Besides potentially easier reviewing, there is also less chances of conflicts or breakage with smaller tickets.

comment:41 follow-up: Changed 16 months ago by saraedum

  • Description modified (diff)
  • Reviewers set to Julian Rüth

Xavier, I volunteer to review this if you want to set it back to needs review.

comment:42 Changed 16 months ago by saraedum

  • Keywords days71 added

comment:43 in reply to: ↑ 41 Changed 16 months ago by maurimo

Replying to saraedum:

Xavier, I volunteer to review this if you want to set it back to needs review.

Already reviewed during Sage Days 71, I communicated directly with Xavier about all issues that needed to be fixed.

comment:44 Changed 16 months ago by maurimo

  • Milestone changed from sage-6.8 to sage-7.2

All required wark has been done, so I will mark it as positive_review.

Last edited 16 months ago by maurimo (previous) (diff)

comment:45 Changed 16 months ago by maurimo

  • Status changed from needs_work to positive_review

comment:46 Changed 16 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict, please fix

comment:47 Changed 16 months ago by git

  • Commit changed from a320013e19516836e69e5944d5e0a8601ecf9ac8 to b59f44883d55fb5eae40c09c82218197921a7045

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

b59f448Merge branch 'develop' into t/14828/public/ticket/14828

comment:48 Changed 16 months ago by caruso

  • Reviewers changed from Julian Rüth to Julian Rüth, Maurizio Monge
  • Status changed from needs_work to needs_review

This should be fixed (hopefully).

comment:49 Changed 16 months ago by chapoton

  • Status changed from needs_review to needs_work

several failing doctests, see patchbot report

comment:50 Changed 16 months ago by git

  • Commit changed from b59f44883d55fb5eae40c09c82218197921a7045 to 868e84eda1d8eef914171b72e3d629b73134e793

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

868e84eFailing doctests fixed

comment:51 Changed 16 months ago by caruso

  • Status changed from needs_work to needs_review

This should be fixed.

comment:52 Changed 16 months ago by saraedum

  • Status changed from needs_review to needs_work

It seems your last change remove the implementation of content().

comment:53 Changed 16 months ago by caruso

Well, I removed it from sage.rings.polynomial.padic.polynomial_padic_capped_relative_dense but the generic implementation in sage.rings.polynomial.padic.polynomial_padic is still there. And it works!

comment:54 Changed 16 months ago by saraedum

  • Status changed from needs_work to positive_review

Fine then :)

comment:55 Changed 16 months ago by vbraun

  • Branch changed from public/ticket/14828 to 868e84eda1d8eef914171b72e3d629b73134e793
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.