Factoring padic polynomials

[bsinclai]

A native sage implementation of padic polynomial factoring

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

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

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

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