Opened 10 years ago

#12561 needs_info enhancement

Reported by: Owned by: bsinclai roed major sage-8.0 padics sd86.5, sd87, padicIMA roed, pbruin Brian Sinclair, Sebastian Pauli Julian Rüth N/A add to reference manual, improve arithmetic of FrameElt, FrameEltTerm (i.e., give them a parent) u/roed/ticket/12561 0e7f566447b002f48e67b7821af865cf30629dce #15190, #14825, #20310

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.

comment:1 Changed 9 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 9 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: ↓ 4 Changed 9 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 9 years ago by roed

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

Oh wait. I looked at the wrong numbers sorry.

comment:7 Changed 8 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

comment:8 Changed 8 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 8 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 8 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 8 years ago by roed

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

comment:12 Changed 8 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 8 years ago by roed

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

comment:14 Changed 8 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 8 years ago by git

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

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

comment:18 Changed 8 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 8 years ago by bsinclai

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

comment:20 Changed 8 years ago by bsinclai

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

comment:21 Changed 8 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: ↓ 25 Changed 8 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 8 years ago by jdemeyer

• Status changed from needs_review to needs_work

comment:24 Changed 8 years ago by git

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

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 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

comment:27 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

comment:28 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

comment:29 Changed 5 years ago by roed

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

comment:30 Changed 5 years ago by saraedum

• Commit changed from 7f250dae1936931254eefdba09bb9052dfc90006 to 001088d0e35a54aa9b52946e6667b2fc41f30b28

New commits:

 ​001088d `Merge branch 'develop' into t/12561/ticket/12561`

comment:31 Changed 5 years ago by git

• Commit changed from 001088d0e35a54aa9b52946e6667b2fc41f30b28 to 6fdd537c7b5daf4260c86f4c1539911a1c647258

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

 ​6fdd537 `Fix broken import`

comment:33 Changed 4 years ago by bsinclai

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

comment:34 Changed 4 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:

 ​ac44f7c `Merge branch 'u/roed/change_precision' of git://trac.sagemath.org/sage into develop` ​4c49226 `Working on deprecating list and __getitem__ for p-adic elements` ​4088f9b `Fixing doctest errors, changes to ZZ_pX p-adic 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 p-adic 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 4 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 4 years ago by git

• Commit changed from 4df99a198be6dc27036a7f12c77aeb09dc12f969 to f699d63b78d1581baddf40fa52ecf197066dd700

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

 ​dad389b `Merge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into develop` ​f699d63 `Fixed from-import lines made incorrect by the move from factor/ to omtree/`

comment:37 Changed 4 years ago by git

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

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

comment:39 Changed 4 years ago by saraedum

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

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

• Commit changed from 9ca7f249238d70cd034a048d12675a5d46aac6b8 to 805801c218750f6aeb02ec5b960855f5ae5ca57b

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`

comment:42 Changed 4 years ago by git

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

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

 ​45bcdd9 `Improve documentation of FrameElt`

comment:44 Changed 4 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 4 years ago by saraedum

• Status changed from needs_work to needs_info

comment:46 Changed 4 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 4 years ago by git

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

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

comment:49 Changed 3 years ago by roed

• Commit changed from 93f4fe8da590d743242ad4f2f92fb4a7801f4c36 to c8a3261bb44bb0722761e04a0840cf2ec4b03316

New commits:

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

comment:50 Changed 3 years ago by git

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