Opened 7 years ago

Last modified 8 months ago

#12561 needs_info enhancement

Factoring padic polynomials

Reported by: bsinclai Owned by: roed
Priority: major Milestone: sage-8.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 bsinclai)

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)

12561.patch (36.1 KB) - added by bsinclai 7 years ago.
12561.2.patch (70.0 KB) - added by bsinclai 6 years ago.

Download all attachments as: .zip

Change History (53)

Changed 7 years ago by bsinclai

comment:1 Changed 7 years ago by saraedum

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.

comment:2 Changed 6 years ago by bsinclai

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 follow-up: Changed 6 years ago by 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 p-adic polynomials.

comment:4 in reply to: ↑ 3 Changed 6 years ago by roed

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 p-adic 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 saraedum

The algorithm used in pfactortree only works for square-free polynomials, so I don't think this is a bug. Square-free decomposition doesn't work currently though, see #13439.

comment:6 Changed 6 years ago by saraedum

Oh wait. I looked at the wrong numbers sorry.

comment:7 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 6 years ago by bsinclai

comment:8 Changed 6 years ago by bsinclai

This new patch replaces the first and has a great deal of improvements, bug-fixes, and documentation. The examples should be more sensible now.

It should successfully factor monic, square-free, fixed-mod padic polynomials without fail.

I am running more tests to ensure its validity as well as implementing the transformations needed to handle non-monic cases, which would leave it only dependant on square-free decomposition.

comment:9 Changed 6 years ago by saraedum

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 6 years ago by jdemeyer

Please be aware of #15422 (which fixes some bugs in Sage's factoring of non-squarefree p-adic polynomials).

comment:11 Changed 6 years ago by roed

  • Branch set to u/roed/ticket/12561
  • Commit set to f40ee7c0ec80d00277d433be31565ef60c8bd135
  • Dependencies set to #15190

comment:12 Changed 6 years ago by bsinclai

  • 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 6 years ago by roed

  • Branch changed from u/bsinclai/ticket/12561 to u/roed/ticket/12561

comment:14 Changed 6 years ago by bsinclai

  • 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 6 years ago by git

  • Commit changed from f40ee7c0ec80d00277d433be31565ef60c8bd135 to e97aa083dafac6f5ec8a5823ed459c4532a240b5

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

e97aa08Added check at FrameElt.polynomial to not allow negative exponents. Added example to FrameElt.residue.

comment:16 Changed 6 years ago by roed

  • 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 6 years ago by bsinclai

  • Branch changed from u/roed/ticket/12561 to u/bsinclai/ticket/12561

comment:18 Changed 6 years ago by roed

  • 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 6 years ago by bsinclai

  • Branch changed from u/roed/ticket/12561 to u/bsinclai/ticket/12561

comment:20 Changed 6 years ago by bsinclai

  • Commit changed from e97aa083dafac6f5ec8a5823ed459c4532a240b5 to e1bb657e7131cc02d0da9f787072d441fb1ea0de
  • Status changed from new to needs_review

New commits:

f2e4f41Adding a bit more documentation
2bf9723Merge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into ticket/12561
61d57efAdding more doctests, fixing trailing whitespace
60f5d9bMiscellaneous style improvements, rewrite of _newton_polygon using monotone chain algorithm
6432e20Changes to make sure types of slope, _exponent, Eplus, etc are consistent - int, Integer or Rational.
1d3f6c6A few more changes related to variable types
0ec528dFix ignoring non-monics with all coefficients divisible by uniformizer. Fixes in FrameElt.
ab1540dMerge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into ticket/12561
e1bb657Remove unneeded if-else statements in Frame.seed and Frame.find_psi. Fixed example in FrameElt.reduce.

comment:21 Changed 6 years ago by jdemeyer

Some comments (not planning to actually review this):

  1. I would hope that this code works for all kinds of p-adic polynomials (over Zp, over Qp, over field extensions, all with different kinds of precision). Still, (almost) all examples in the doctests use ZpFM.
  2. The factor() method doesn't actually use this code. What's the point then?
  3. It would be good if this code would also support the factor_padic() method for polynomials over ZZ and QQ.
  4. What happens if the assumption the the polynomial is squarefree doesn't hold?
  5. 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)
    
  6. 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 follow-up: Changed 6 years ago by jdemeyer

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 = (x-1)^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 6 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:24 Changed 6 years ago by git

  • Commit changed from e1bb657e7131cc02d0da9f787072d441fb1ea0de to 7f250dae1936931254eefdba09bb9052dfc90006

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

7f250daFix unit part of factorization and factoring polynomials divisible by x.

comment:25 in reply to: ↑ 22 Changed 6 years ago by roed

Replying to jdemeyer:

The new code also seems slower than the factor() which is already in Sage (at least when #15654 is applied).

It hasn't been optimized, so I'm hoping that these timings will improve (currently, a lot of time is spent in initialization of various objects that can be reduced).

comment:26 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:27 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:28 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:29 Changed 2 years ago by roed

  • Branch changed from u/bsinclai/ticket/12561 to u/roed/ticket/12561

comment:30 Changed 2 years ago by saraedum

  • Commit changed from 7f250dae1936931254eefdba09bb9052dfc90006 to 001088d0e35a54aa9b52946e6667b2fc41f30b28
  • Keywords sd86.5 added

New commits:

001088dMerge branch 'develop' into t/12561/ticket/12561

comment:31 Changed 2 years ago by git

  • Commit changed from 001088d0e35a54aa9b52946e6667b2fc41f30b28 to 6fdd537c7b5daf4260c86f4c1539911a1c647258

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

6fdd537Fix broken import

comment:32 Changed 2 years ago by roed

  • Keywords sd87 added

comment:33 Changed 2 years ago by bsinclai

  • Dependencies changed from #15190 to #15190, #14825, #20310

comment:34 Changed 2 years ago by bsinclai

  • Branch changed from u/roed/ticket/12561 to u/bsinclai/ticket/12561
  • Commit changed from 6fdd537c7b5daf4260c86f4c1539911a1c647258 to 4df99a198be6dc27036a7f12c77aeb09dc12f969

Last 10 new commits:

ac44f7cMerge branch 'u/roed/change_precision' of git://trac.sagemath.org/sage into develop
4c49226Working on deprecating list and __getitem__ for p-adic elements
4088f9bFixing doctest errors, changes to ZZ_pX p-adic types
24ee4ffFixing doctest errors due to switching from list to expansion
cbfeb34Making behavior of teichmuller_expansion uniform across precision types, adding doctests
f5e2440Fix 'x'->'var' typo in some docstrings, add polynomial method to ntl p-adic types
779ddb8Remove added NOTES: in CR_template
985a23aamend documentation of ccoefficients
cab0c9eMerge branch 'u/saraedum/polynomial_representation_of_a_padic_number' of git://trac.sagemath.org/sage into develop
4df99a1Created OMTree class, moved files from factor/ to omtree/, updated documentation, added access functions.

comment:35 Changed 2 years ago by bsinclai

  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-8.0
  • Status changed from needs_work to needs_review

comment:36 Changed 2 years ago by git

  • Commit changed from 4df99a198be6dc27036a7f12c77aeb09dc12f969 to f699d63b78d1581baddf40fa52ecf197066dd700

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

dad389bMerge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into develop
f699d63Fixed from-import lines made incorrect by the move from factor/ to omtree/

comment:37 Changed 2 years ago by git

  • Commit changed from f699d63b78d1581baddf40fa52ecf197066dd700 to 195abcc1702521f6b8aef97bc8090b058bb6bcbc

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

195abccBrought doctest coverage to 100%

comment:38 Changed 2 years ago by saraedum

  • Branch changed from u/bsinclai/ticket/12561 to u/saraedum/ticket/12561

comment:39 Changed 2 years ago by saraedum

  • Commit changed from 195abcc1702521f6b8aef97bc8090b058bb6bcbc to 8c171f96d5dd92db4de335bf90cf0fbc4749d314
  • Reviewers set to Julian Rüth

Last 10 new commits:

8081eabadded doctests after fixing conflicts
063b58cMerge branch 'develop' into t/20073/ticket/20073
48be601Added documentation to verify that the extension has the right defining polynomial
921af5eChanging modulus and defining_polynomial to use an exact keyword
39043f1Merge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/20310/change_precision
77779eaminor docstring changes
6e2495fMerge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/20310/change_precision
7428353minor docstring fixes
998b3c1Merge branch 't/20310/change_precision' into t/12561/ticket/12561
8c171f9remove conflict markers

comment:40 Changed 2 years ago by git

  • Commit changed from 8c171f96d5dd92db4de335bf90cf0fbc4749d314 to 9ca7f249238d70cd034a048d12675a5d46aac6b8

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

9a519eaimprove documentation
81ab3a8Remove __cmp__
7366625Implement __hash__
45dfd22improve documentation
0af8e52Added some high level documentation for associated factors
bd15d71add exact keyword
9d01c94Merge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/12561/ticket/12561
9ca7f24fix doctest

comment:41 Changed 2 years ago by git

  • Commit changed from 9ca7f249238d70cd034a048d12675a5d46aac6b8 to 805801c218750f6aeb02ec5b960855f5ae5ca57b

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

7e620cdRenamed associated factor to residual factor
206443aHigh level documentation for frames
805801cCleanup documentation of Frame

comment:42 Changed 2 years ago by git

  • Commit changed from 805801c218750f6aeb02ec5b960855f5ae5ca57b to fb41e0e5ebd32022ad01d1fb29c2acc43fba0e79

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

fb41e0eAdded spaces for code layout

comment:43 Changed 2 years ago by git

  • Commit changed from fb41e0e5ebd32022ad01d1fb29c2acc43fba0e79 to 45bcdd91f1ba286c02c114c56aaada4ab2aa8d97

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

45bcdd9Improve documentation of FrameElt

comment:44 Changed 2 years ago by saraedum

  • 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 2 years ago by saraedum

  • Status changed from needs_work to needs_info

comment:46 Changed 2 years ago by bsinclai

  • 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 p-adic integers as valuation-and-unit or (FrameElt? in phii-1)*phiideg. 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 2 years ago by git

  • Commit changed from 275bc9d7eb7f4531c419ede1367321f79fa57e21 to 93f4fe8da590d743242ad4f2f92fb4a7801f4c36

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

93f4fe8Fix some doctests, work on comparison functions

comment:48 Changed 2 years ago by roed

  • Branch changed from u/bsinclai/ticket/12561 to u/roed/ticket/12561

comment:49 Changed 12 months ago by roed

  • Commit changed from 93f4fe8da590d743242ad4f2f92fb4a7801f4c36 to c8a3261bb44bb0722761e04a0840cf2ec4b03316
  • Keywords padicIMA added

New commits:

c8a3261Merge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into t/12561/om_tree

comment:50 Changed 12 months ago by git

  • Commit changed from c8a3261bb44bb0722761e04a0840cf2ec4b03316 to 0e7f566447b002f48e67b7821af865cf30629dce

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

0e7f566Merge branch 'u/roed/ticket/12561' of git://trac.sagemath.org/sage into t/12561/padic_poly

comment:51 Changed 8 months ago by pbruin

  • Cc pbruin added
Note: See TracTickets for help on using tickets.