Factoring padic polynomials #12561

sagetrac-bsinclai · 2012-02-22T09:12:51Z

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.

Depends on #15190
Depends on #14825
Depends on #20310

CC: @roed314 @pjbruin

Component: padics

Keywords: sd86.5, sd87, padicIMA

Work Issues: add to reference manual, improve arithmetic of FrameElt, FrameEltTerm (i.e., give them a parent)

Author: Brian Sinclair, Sebastian Pauli

Branch/Commit: u/roed/ticket/12561 @ 0e7f566

Reviewer: Julian Rüth

Issue created by migration from https://trac.sagemath.org/ticket/12561

The text was updated successfully, but these errors were encountered:

sagetrac-bsinclai · 2012-02-23T08:37:25Z

Attachment: 12561.patch.gz

saraedum · 2013-01-12T17:45:31Z

comment:1

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.

sagetrac-bsinclai · 2013-01-26T22:41:51Z

comment:2

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.

haikona · 2013-02-28T18:37:51Z

comment:3

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.

roed314 · 2013-03-01T22:09:16Z

comment:4

Replying to @haikona:

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.

saraedum · 2013-05-26T23:34:45Z

comment:5

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.

saraedum · 2013-05-26T23:36:03Z

comment:6

Oh wait. I looked at the wrong numbers sorry.

sagetrac-bsinclai · 2013-10-14T02:21:13Z

comment:8

Attachment: 12561.2.patch.gz

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.

saraedum · 2013-10-14T13:51:24Z

comment:9

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

jdemeyer · 2013-11-22T14:13:51Z

comment:10

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

roed314 · 2014-01-04T04:21:20Z

Dependencies: #15190

roed314 · 2014-01-04T04:21:20Z

Commit: f40ee7c

roed314 · 2014-01-04T04:21:20Z

Branch: u/roed/ticket/12561

sagetrac-bsinclai · 2014-01-06T20:17:31Z

Changed branch from u/roed/ticket/12561 to u/bsinclai/ticket/12561

roed314 · 2014-01-07T03:34:25Z

Changed branch from u/bsinclai/ticket/12561 to u/roed/ticket/12561

sagetrac-bsinclai · 2014-01-07T03:46:01Z

Changed branch from u/roed/ticket/12561 to u/bsinclai/ticket/12561

sagetrac-git · 2014-01-07T04:19:44Z

Changed commit from f40ee7c to e97aa08

sagetrac-git · 2014-01-07T04:19:44Z

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.`

roed314 · 2014-01-07T11:52:34Z

Changed branch from u/bsinclai/ticket/12561 to u/roed/ticket/12561

sagetrac-bsinclai · 2014-01-07T21:35:26Z

Changed branch from u/roed/ticket/12561 to u/bsinclai/ticket/12561

roed314 · 2014-01-08T01:45:12Z

Changed branch from u/bsinclai/ticket/12561 to u/roed/ticket/12561

sagetrac-bsinclai · 2014-01-08T04:58:11Z

Changed branch from u/roed/ticket/12561 to u/bsinclai/ticket/12561

sagetrac-bsinclai · 2014-01-08T22:29:21Z

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 non-monics 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 if-else statements in Frame.seed and Frame.find_psi. Fixed example in FrameElt.reduce.`

saraedum · 2017-07-20T03:12:24Z

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`

saraedum · 2017-07-20T03:12:24Z

Changed commit from 195abcc to 8c171f9

sagetrac-git · 2017-07-20T05:39:55Z

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`

sagetrac-git · 2017-07-20T05:39:55Z

Changed commit from 8c171f9 to 9ca7f24

sagetrac-git · 2017-07-20T07:04:27Z

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

`7e620cd`	`Renamed associated factor to residual factor`
`206443a`	`High level documentation for frames`
`805801c`	`Cleanup documentation of Frame`

sagetrac-git · 2017-07-20T07:04:27Z

Changed commit from 9ca7f24 to 805801c

sagetrac-git · 2017-07-20T07:12:23Z

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

`fb41e0e`	`Added spaces for code layout`

sagetrac-git · 2017-07-20T07:12:23Z

Changed commit from 805801c to fb41e0e

sagetrac-git · 2017-07-20T08:14:16Z

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

`45bcdd9`	`Improve documentation of FrameElt`

sagetrac-git · 2017-07-20T08:14:16Z

Changed commit from fb41e0e to 45bcdd9

saraedum · 2017-07-20T08:31:32Z

comment:44

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.

saraedum · 2017-07-20T08:31:32Z

Work Issues: add to reference manual, improve arithmetic of FrameElt, FrameEltTerm (i.e., give them a parent)

sagetrac-bsinclai · 2017-07-20T16:37:32Z

Changed commit from 45bcdd9 to 275bc9d

sagetrac-bsinclai · 2017-07-20T16:37:32Z

comment:46

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 phi_i-1)*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.

sagetrac-bsinclai · 2017-07-20T16:37:32Z

Changed branch from u/saraedum/ticket/12561 to u/bsinclai/ticket/12561

sagetrac-git · 2017-07-21T17:01:43Z

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

`93f4fe8`	`Fix some doctests, work on comparison functions`

sagetrac-git · 2017-07-21T17:01:43Z

Changed commit from 275bc9d to 93f4fe8

roed314 · 2017-08-21T04:57:32Z

Changed branch from u/bsinclai/ticket/12561 to u/roed/ticket/12561

roed314 · 2018-07-23T00:09:38Z

New commits:

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

roed314 · 2018-07-23T00:09:38Z

Changed keywords from sd86.5, sd87 to sd86.5, sd87, padicIMA

roed314 · 2018-07-23T00:09:38Z

Changed commit from 93f4fe8 to c8a3261

sagetrac-git · 2018-07-23T03:39:33Z

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`

sagetrac-git · 2018-07-23T03:39:33Z

Changed commit from c8a3261 to 0e7f566

sagetrac-bsinclai mannequin added this to the sage-5.11 milestone Feb 22, 2012

sagetrac-bsinclai mannequin added c: padics labels Feb 22, 2012

sagetrac-bsinclai mannequin assigned roed314 Feb 22, 2012

jdemeyer modified the milestones: sage-5.11, sage-5.12 Aug 13, 2013

saraedum added s: needs work and removed s: needs review labels Jul 20, 2017

mkoeppe removed this from the sage-8.0 milestone Dec 29, 2022

sagetrac-bsinclai mannequin mentioned this issue Dec 29, 2022

Improvements for p-adic polynomials #23508

Open

roed314 mentioned this issue Dec 29, 2022

padic folder refactoring #23524

Open

Factoring padic polynomials #12561

Factoring padic polynomials #12561

Comments

sagetrac-bsinclai mannequin commented Feb 22, 2012

sagetrac-bsinclai mannequin commented Feb 23, 2012

saraedum commented Jan 12, 2013

sagetrac-bsinclai mannequin commented Jan 26, 2013

haikona mannequin commented Feb 28, 2013

roed314 commented Mar 1, 2013

saraedum commented May 26, 2013

saraedum commented May 26, 2013

sagetrac-bsinclai mannequin commented Oct 14, 2013

saraedum commented Oct 14, 2013

jdemeyer commented Nov 22, 2013

roed314 commented Jan 4, 2014

roed314 commented Jan 4, 2014

roed314 commented Jan 4, 2014

sagetrac-bsinclai mannequin commented Jan 6, 2014

roed314 commented Jan 7, 2014

sagetrac-bsinclai mannequin commented Jan 7, 2014

sagetrac-git mannequin commented Jan 7, 2014

sagetrac-git mannequin commented Jan 7, 2014

roed314 commented Jan 7, 2014

sagetrac-bsinclai mannequin commented Jan 7, 2014

roed314 commented Jan 8, 2014

sagetrac-bsinclai mannequin commented Jan 8, 2014

sagetrac-bsinclai mannequin commented Jan 8, 2014

saraedum commented Jul 20, 2017

saraedum commented Jul 20, 2017

sagetrac-git mannequin commented Jul 20, 2017

sagetrac-git mannequin commented Jul 20, 2017

sagetrac-git mannequin commented Jul 20, 2017

sagetrac-git mannequin commented Jul 20, 2017

sagetrac-git mannequin commented Jul 20, 2017

sagetrac-git mannequin commented Jul 20, 2017

sagetrac-git mannequin commented Jul 20, 2017

sagetrac-git mannequin commented Jul 20, 2017

saraedum commented Jul 20, 2017

saraedum commented Jul 20, 2017

sagetrac-bsinclai mannequin commented Jul 20, 2017

sagetrac-bsinclai mannequin commented Jul 20, 2017

sagetrac-bsinclai mannequin commented Jul 20, 2017

sagetrac-git mannequin commented Jul 21, 2017

sagetrac-git mannequin commented Jul 21, 2017

roed314 commented Aug 21, 2017

roed314 commented Jul 23, 2018

roed314 commented Jul 23, 2018

roed314 commented Jul 23, 2018

sagetrac-git mannequin commented Jul 23, 2018

sagetrac-git mannequin commented Jul 23, 2018