Opened 7 years ago
Last modified 5 months ago
#12561 needs_info enhancement
Factoring padic polynomials
Reported by:  bsinclai  Owned by:  roed 

Priority:  major  Milestone:  sage8.0 
Component:  padics  Keywords:  sd86.5, sd87, padicIMA 
Cc:  roed, pbruin  Merged in:  
Authors:  Brian Sinclair, Sebastian Pauli  Reviewers:  Julian Rüth 
Report Upstream:  N/A  Work issues:  add to reference manual, improve arithmetic of FrameElt, FrameEltTerm (i.e., give them a parent) 
Branch:  u/roed/ticket/12561 (Commits)  Commit:  0e7f566447b002f48e67b7821af865cf30629dce 
Dependencies:  #15190, #14825, #20310  Stopgaps: 
Description (last modified by )
OM Tree construction and a native sage implementation of padic polynomial factoring using it. This factorization works for polynomials over Zp as well as over unramified and totally ramified extensions of Zp.
Attachments (2)
Change History (53)
Changed 7 years ago by
comment:1 Changed 6 years ago by
comment:2 Changed 6 years ago by
Other than the poor state of documentation and polish, I cannot find any faults. I have run the code through all of the previously failed examples with no issue outside of occasionally having insufficient precision. The newton polygon code does not elegantly handle the infinite slope case (the case where the current phi actually divides Phi), but it doesn't have to for factoring since it can be (and is) caught earlier in the loop.
comment:3 followup: ↓ 4 Changed 6 years ago by
Patch applies correctly on 7.5 and all doctests written so far pass. However:
In the doctest from pfactortree()
:
sage: from sage.rings.polynomial.padics.factor.factoring import jorder4,pfactortree sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 ) sage: pfactortree(f) # long (3.8s) [(1 + O(2^24))*x^64 + (65536 + O(2^24))*x^34 + (32 + O(2^24))*x^32 + (1048576 + O(2^24))*x^2 + (256 + O(2^24))]
This is just returning the polynomial unfactored, so demonstrably the factoring isn't working here. We should get:
sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 ) sage: f.factor() ((1 + O(2^24))*x^32 + (65536 + O(2^24))*x^2 + (16 + O(2^24))) * ((1 + O(2^24))*x^32 + (16 + O(2^24)))
Also, we should rework this code so that a sage Factorization object is returned, and that pfactortree is called by the .factor()
method attached to padic polynomials.
comment:4 in reply to: ↑ 3 Changed 6 years ago by
Replying to spice:
Patch applies correctly on 7.5 and all doctests written so far pass. However:
In the doctest from
pfactortree()
:sage: from sage.rings.polynomial.padics.factor.factoring import jorder4,pfactortree sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 ) sage: pfactortree(f) # long (3.8s) [(1 + O(2^24))*x^64 + (65536 + O(2^24))*x^34 + (32 + O(2^24))*x^32 + (1048576 + O(2^24))*x^2 + (256 + O(2^24))]This is just returning the polynomial unfactored, so demonstrably the factoring isn't working here. We should get:
sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 ) sage: f.factor() ((1 + O(2^24))*x^32 + (65536 + O(2^24))*x^2 + (16 + O(2^24))) * ((1 + O(2^24))*x^32 + (16 + O(2^24)))Also, we should rework this code so that a sage Factorization object is returned, and that pfactortree is called by the
.factor()
method attached to padic polynomials.
Note that increasing the precision yields a factorization:
sage: f = ZpFM(2,44,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2) + 2^34) sage: pfactortree(f) [(1 + O(2^44))*x^32 + (7242791239680 + O(2^44))*x^30 + (13194407968768 + O(2^44))*x^28 + (7902202888192 + O(2^44))*x^26 + (2147483648 + O(2^44))*x^24 + (442381107200 + O(2^44))*x^22 + (21474836480 + O(2^44))*x^20 + (6193337597952 + O(2^44))*x^18 + (240518168576 + O(2^44))*x^16 + (2405122965504 + O(2^44))*x^14 + (2886218022912 + O(2^44))*x^12 + (16766847680512 + O(2^44))*x^10 + (1099511627776 + O(2^44))*x^8 + (2190164885504 + O(2^44))*x^6 + (14293651161088 + O(2^44))*x^4 + (14178492350464 + O(2^44))*x^2 + (8796093022224 + O(2^44)), (1 + O(2^44))*x^32 + (10349394804736 + O(2^44))*x^30 + (8796093022208 + O(2^44))*x^28 + (5291936645120 + O(2^44))*x^26 + (17149804937216 + O(2^44))*x^22 + (11398848446464 + O(2^44))*x^18 + (15187063078912 + O(2^44))*x^14 + (825338363904 + O(2^44))*x^10 + (15402021158912 + O(2^44))*x^6 + (3413693759488 + O(2^44))*x^2 + (8797166764048 + O(2^44))]
In the case Simon pointed out, adding 2^34
doesn't do anything since the precision cap of the base ring is 24, so we have an actual example of a reducible polynomial being claimed to be irreducible.
comment:5 Changed 6 years ago by
The algorithm used in pfactortree
only works for squarefree polynomials, so I don't think this is a bug. Squarefree decomposition doesn't work currently though, see #13439.
comment:6 Changed 6 years ago by
Oh wait. I looked at the wrong numbers sorry.
comment:7 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
Changed 6 years ago by
comment:8 Changed 6 years ago by
This new patch replaces the first and has a great deal of improvements, bugfixes, and documentation. The examples should be more sensible now.
It should successfully factor monic, squarefree, fixedmod padic polynomials without fail.
I am running more tests to ensure its validity as well as implementing the transformations needed to handle nonmonic cases, which would leave it only dependant on squarefree decomposition.
comment:9 Changed 6 years ago by
Nice. I volunteer to review this once it is ready. On a first look, several methods still don't have docstrings (but you are probably aware of this).
comment:10 Changed 5 years ago by
Please be aware of #15422 (which fixes some bugs in Sage's factoring of nonsquarefree padic polynomials).
comment:11 Changed 5 years ago by
 Branch set to u/roed/ticket/12561
 Commit set to f40ee7c0ec80d00277d433be31565ef60c8bd135
 Dependencies set to #15190
comment:12 Changed 5 years ago by
 Branch changed from u/roed/ticket/12561 to u/bsinclai/ticket/12561
 Modified changed from 01/04/14 04:21:20 to 01/04/14 04:21:20
comment:13 Changed 5 years ago by
 Branch changed from u/bsinclai/ticket/12561 to u/roed/ticket/12561
comment:14 Changed 5 years ago by
 Branch changed from u/roed/ticket/12561 to u/bsinclai/ticket/12561
 Modified changed from 01/07/14 03:34:25 to 01/07/14 03:34:25
comment:15 Changed 5 years ago by
 Commit changed from f40ee7c0ec80d00277d433be31565ef60c8bd135 to e97aa083dafac6f5ec8a5823ed459c4532a240b5
Branch pushed to git repo; I updated commit sha1. New commits:
e97aa08  Added check at FrameElt.polynomial to not allow negative exponents. Added example to FrameElt.residue.

comment:16 Changed 5 years ago by
 Branch changed from u/bsinclai/ticket/12561 to u/roed/ticket/12561
 Modified changed from 01/07/14 04:19:44 to 01/07/14 04:19:44
comment:17 Changed 5 years ago by
 Branch changed from u/roed/ticket/12561 to u/bsinclai/ticket/12561
comment:18 Changed 5 years ago by
 Branch changed from u/bsinclai/ticket/12561 to u/roed/ticket/12561
 Modified changed from 01/07/14 21:35:26 to 01/07/14 21:35:26
comment:19 Changed 5 years ago by
 Branch changed from u/roed/ticket/12561 to u/bsinclai/ticket/12561
comment:20 Changed 5 years ago by
 Commit changed from e97aa083dafac6f5ec8a5823ed459c4532a240b5 to e1bb657e7131cc02d0da9f787072d441fb1ea0de
 Status changed from new to needs_review
New commits:
f2e4f41  Adding a bit more documentation

2bf9723  Merge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into ticket/12561

61d57ef  Adding more doctests, fixing trailing whitespace

60f5d9b  Miscellaneous style improvements, rewrite of _newton_polygon using monotone chain algorithm

6432e20  Changes to make sure types of slope, _exponent, Eplus, etc are consistent  int, Integer or Rational.

1d3f6c6  A few more changes related to variable types

0ec528d  Fix ignoring nonmonics with all coefficients divisible by uniformizer. Fixes in FrameElt.

ab1540d  Merge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into ticket/12561

e1bb657  Remove unneeded ifelse statements in Frame.seed and Frame.find_psi. Fixed example in FrameElt.reduce.

comment:21 Changed 5 years ago by
Some comments (not planning to actually review this):
 I would hope that this code works for all kinds of padic polynomials (over
Zp
, overQp
, over field extensions, all with different kinds of precision). Still, (almost) all examples in the doctests useZpFM
.  The
factor()
method doesn't actually use this code. What's the point then?  It would be good if this code would also support the
factor_padic()
method for polynomials overZZ
andQQ
.  What happens if the assumption the the polynomial is squarefree doesn't hold?
 Units in the
Factorization
should be put in the "unit" part, this is wrong:sage: x = polygen(ZpFM(2,10)) sage: pfactor(3*x)[1] (1 + 2 + O(2^10), 1)
 Similarly, the primes should actually be primes, this should have a factor 2 with multiplicity 2:
sage: x = polygen(ZpFM(2,10)) sage: pfactor(4*x)[1] (2^2 + O(2^10), 1)
comment:22 followup: ↓ 25 Changed 5 years ago by
The new code also seems slower than the factor()
which is already in Sage (at least when #15654 is applied).
sage: x = polygen(ZpFM(3,50)) sage: pol = (x1)^100 + x sage: %time F1=factor(pol) CPU times: user 0.68 s, sys: 0.00 s, total: 0.68 s Wall time: 0.68 s sage: %time F2=pfactor(pol) CPU times: user 2.17 s, sys: 0.01 s, total: 2.18 s Wall time: 2.16 s
comment:23 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:24 Changed 5 years ago by
 Commit changed from e1bb657e7131cc02d0da9f787072d441fb1ea0de to 7f250dae1936931254eefdba09bb9052dfc90006
Branch pushed to git repo; I updated commit sha1. New commits:
7f250da  Fix unit part of factorization and factoring polynomials divisible by x.

comment:25 in reply to: ↑ 22 Changed 5 years ago by
comment:26 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:27 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:28 Changed 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:29 Changed 23 months ago by
 Branch changed from u/bsinclai/ticket/12561 to u/roed/ticket/12561
comment:30 Changed 23 months ago by
 Commit changed from 7f250dae1936931254eefdba09bb9052dfc90006 to 001088d0e35a54aa9b52946e6667b2fc41f30b28
 Keywords sd86.5 added
New commits:
001088d  Merge branch 'develop' into t/12561/ticket/12561

comment:31 Changed 23 months ago by
 Commit changed from 001088d0e35a54aa9b52946e6667b2fc41f30b28 to 6fdd537c7b5daf4260c86f4c1539911a1c647258
Branch pushed to git repo; I updated commit sha1. New commits:
6fdd537  Fix broken import

comment:32 Changed 21 months ago by
 Keywords sd87 added
comment:33 Changed 21 months ago by
 Dependencies changed from #15190 to #15190, #14825, #20310
comment:34 Changed 21 months ago by
 Branch changed from u/roed/ticket/12561 to u/bsinclai/ticket/12561
 Commit changed from 6fdd537c7b5daf4260c86f4c1539911a1c647258 to 4df99a198be6dc27036a7f12c77aeb09dc12f969
Last 10 new commits:
ac44f7c  Merge branch 'u/roed/change_precision' of git://trac.sagemath.org/sage into develop

4c49226  Working on deprecating list and __getitem__ for padic elements

4088f9b  Fixing doctest errors, changes to ZZ_pX padic types

24ee4ff  Fixing doctest errors due to switching from list to expansion

cbfeb34  Making behavior of teichmuller_expansion uniform across precision types, adding doctests

f5e2440  Fix 'x'>'var' typo in some docstrings, add polynomial method to ntl padic types

779ddb8  Remove added NOTES: in CR_template

985a23a  amend documentation of ccoefficients

cab0c9e  Merge branch 'u/saraedum/polynomial_representation_of_a_padic_number' of git://trac.sagemath.org/sage into develop

4df99a1  Created OMTree class, moved files from factor/ to omtree/, updated documentation, added access functions.

comment:35 Changed 21 months ago by
 Description modified (diff)
 Milestone changed from sage6.4 to sage8.0
 Status changed from needs_work to needs_review
comment:36 Changed 21 months ago by
 Commit changed from 4df99a198be6dc27036a7f12c77aeb09dc12f969 to f699d63b78d1581baddf40fa52ecf197066dd700
comment:37 Changed 21 months ago by
 Commit changed from f699d63b78d1581baddf40fa52ecf197066dd700 to 195abcc1702521f6b8aef97bc8090b058bb6bcbc
Branch pushed to git repo; I updated commit sha1. New commits:
195abcc  Brought doctest coverage to 100%

comment:38 Changed 21 months ago by
 Branch changed from u/bsinclai/ticket/12561 to u/saraedum/ticket/12561
comment:39 Changed 21 months ago by
 Commit changed from 195abcc1702521f6b8aef97bc8090b058bb6bcbc to 8c171f96d5dd92db4de335bf90cf0fbc4749d314
 Reviewers set to Julian Rüth
Last 10 new commits:
8081eab  added doctests after fixing conflicts

063b58c  Merge branch 'develop' into t/20073/ticket/20073

48be601  Added documentation to verify that the extension has the right defining polynomial

921af5e  Changing modulus and defining_polynomial to use an exact keyword

39043f1  Merge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/20310/change_precision

77779ea  minor docstring changes

6e2495f  Merge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/20310/change_precision

7428353  minor docstring fixes

998b3c1  Merge branch 't/20310/change_precision' into t/12561/ticket/12561

8c171f9  remove conflict markers

comment:40 Changed 21 months ago by
 Commit changed from 8c171f96d5dd92db4de335bf90cf0fbc4749d314 to 9ca7f249238d70cd034a048d12675a5d46aac6b8
Branch pushed to git repo; I updated commit sha1. New commits:
9a519ea  improve documentation

81ab3a8  Remove __cmp__

7366625  Implement __hash__

45dfd22  improve documentation

0af8e52  Added some high level documentation for associated factors

bd15d71  add exact keyword

9d01c94  Merge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/12561/ticket/12561

9ca7f24  fix doctest

comment:41 Changed 21 months ago by
 Commit changed from 9ca7f249238d70cd034a048d12675a5d46aac6b8 to 805801c218750f6aeb02ec5b960855f5ae5ca57b
comment:42 Changed 21 months ago by
 Commit changed from 805801c218750f6aeb02ec5b960855f5ae5ca57b to fb41e0e5ebd32022ad01d1fb29c2acc43fba0e79
Branch pushed to git repo; I updated commit sha1. New commits:
fb41e0e  Added spaces for code layout

comment:43 Changed 21 months ago by
 Commit changed from fb41e0e5ebd32022ad01d1fb29c2acc43fba0e79 to 45bcdd91f1ba286c02c114c56aaada4ab2aa8d97
Branch pushed to git repo; I updated commit sha1. New commits:
45bcdd9  Improve documentation of FrameElt

comment:44 Changed 21 months ago by
 Status changed from needs_review to needs_work
 Work issues set to add to reference manual, improve arithmetic of FrameElt, FrameEltTerm (i.e., give them a parent)
I think it would be very nice to come up with a parent for FrameElt? and FrameEltTerm? and then inherit from Element for these. This would make implementation of arithmetic much easier I think.
Isn't FrameElt? basically just a sparse polynomial whose coefficients are FrameEltTerm?? I actually find it surprising that FrameEltTerm? exists. It's just wrapping a FrameElt? except in the base case where it is wrapping a constant. I think that a tower of sparse polynomial rings could give you the same much more easily.
Not sure if you feel like rewriting this or if we should postpone this.
comment:45 Changed 21 months ago by
 Status changed from needs_work to needs_info
comment:46 Changed 21 months ago by
 Branch changed from u/saraedum/ticket/12561 to u/bsinclai/ticket/12561
 Commit changed from 45bcdd91f1ba286c02c114c56aaada4ab2aa8d97 to 275bc9d7eb7f4531c419ede1367321f79fa57e21
I think that in the end, finding a parent for FrameElt? and FrameEltTerm? make sense. FrameElts? are sparse polynomials of FrameEltTerms? and FrameEltTerms? are either representations of padic integers as valuationandunit or (FrameElt? in phi_{i1})*phi_{i}^{deg}. However, there are specialized mechanics to consider and these objects are at the core of most of this code.
I think that this would be worthwhile, but might make sense to do as part of a refactor that also collapses segments and residual factors into frames and cleans up the object interface.
comment:47 Changed 21 months ago by
 Commit changed from 275bc9d7eb7f4531c419ede1367321f79fa57e21 to 93f4fe8da590d743242ad4f2f92fb4a7801f4c36
Branch pushed to git repo; I updated commit sha1. New commits:
93f4fe8  Fix some doctests, work on comparison functions

comment:48 Changed 20 months ago by
 Branch changed from u/bsinclai/ticket/12561 to u/roed/ticket/12561
comment:49 Changed 9 months ago by
 Commit changed from 93f4fe8da590d743242ad4f2f92fb4a7801f4c36 to c8a3261bb44bb0722761e04a0840cf2ec4b03316
 Keywords padicIMA added
New commits:
c8a3261  Merge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into t/12561/om_tree

comment:50 Changed 9 months ago by
 Commit changed from c8a3261bb44bb0722761e04a0840cf2ec4b03316 to 0e7f566447b002f48e67b7821af865cf30629dce
Branch pushed to git repo; I updated commit sha1. New commits:
0e7f566  Merge branch 'u/roed/ticket/12561' of git://trac.sagemath.org/sage into t/12561/padic_poly

comment:51 Changed 5 months ago by
 Cc pbruin added
On the wiki page about padic factoring it says that the implementation doesn't work correctly for some examples. Is there only a problem with some specific cases? I just tried a few products of low degree polynomials and the factorizations seemed ok.
I want to try to debug the code, so if you know of any simple examples for which it doesn't work, that would be helpful.