Opened 2 years ago
Last modified 14 months ago
#22956 new enhancement
padic completions/Henselizations backed by exact rings
Reported by:  saraedum  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  padics  Keywords:  sd86.5, sd87, padicIMA 
Cc:  roed, caruso  Merged in:  
Authors:  Julian Rüth  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/saraedum/22956 (Commits)  Commit:  7520220e3739038149ee2104c329f6a19ebd667e 
Dependencies:  #21869, #22983, #23020, #23164, #23168, #23169, #23170, #23171, #23173, #23182, #24934, #24655, #25226, #25227, #25228  Stopgaps: 
Description (last modified by )
All padic rings currently available in Sage are backed by elements that consist of an approximation and a precision. It can sometimes be tedious to work with such elements since error propagation needs to be analyzed and many algorithms in Sage don't play nice with such inexact elements.
This ticket implements an exact alternative where padic rings are backed by absolute number fields. The idea is to use exact elements in number fields where possible and describe algebraic elements as limits of Mac Lane valuations (see #21869). Since computations in number fields (and in particular in relative extensions) are slow in Sage, extensions are always rewritten as isomorphic rings defined by an absolute number field with defining (Eisenstein) polynomials with small coefficients.
A prototype of this exists as a standalone project https://github.com/saraedum/completion. The idea of this ticket is not necessarily to get this prototype into Sage but to track the few things that need to change in Sage for it to work (fast).
One can of course not expect arithmetic to be as fast as in the inexact padic rings but the approach seems to have its merits. With a few tweaks in Sage, this implementation can compute the degree 384 splitting field (unramified of degree 2) of a degree 12 polynomial over Q2 in less than three minutes.
Required changes to Sage (that can not be monkeypatched; the ones in parentheses are for better performance):
The attached branch contains all these changes.
 Polynomials should not require coefficients to implement
__nonzero__
for printing. (#23020)  Orders are not unique parents. (#24934)
PolynomialQuotientRing
should be a unique parent. (#22983) Do not sort factorizations (#25226)
 More polynomials need to be irreducible (#25227)
 Fix initialization problems of integer polynomials (#25228)
 (
is_irreducible
should be cached) (#23164)  (
is_squarefree
should be cached) (#23182)  (
is_irreducible
should be able to call_is_irreducible_univariate_polynomial
on the base ring.) (#23168)  (
is_squarefree
should be able to call_is_squarefree_univariate_polynomial
on the base ring.) (#23169)  (Ideal generators should be more stable (i.e., the generator of a principal ideal should be exactly the element that was used to create that ideal)) (#23170)
 (
gcd(a,a) is a
should be true for polynomials over number fields.) (#23171)  (Remove
Element._cache_key
that someone forgot to delete when taking outElement.__hash__
.) (#23173)
Change History (24)
comment:1 Changed 2 years ago by
 Description modified (diff)
comment:2 Changed 2 years ago by
 Description modified (diff)
comment:3 Changed 2 years ago by
 Description modified (diff)
comment:4 Changed 2 years ago by
 Description modified (diff)
 Keywords sd86.5 added
comment:5 Changed 2 years ago by
 Description modified (diff)
comment:6 Changed 2 years ago by
 Description modified (diff)
comment:7 Changed 2 years ago by
 Description modified (diff)
comment:8 Changed 2 years ago by
 Description modified (diff)
comment:9 Changed 2 years ago by
 Keywords sd87 added
comment:10 Changed 19 months ago by
 Description modified (diff)
comment:11 Changed 19 months ago by
 Description modified (diff)
comment:12 Changed 19 months ago by
 Dependencies changed from #21869 to #21869, #24934
comment:13 Changed 19 months ago by
 Dependencies changed from #21869, #24934 to #21869, #24934, #22983
 Description modified (diff)
comment:14 Changed 17 months ago by
 Dependencies changed from #21869, #24934, #22983 to #21869, #24934, #22983, #25226
comment:15 Changed 17 months ago by
 Description modified (diff)
comment:16 Changed 17 months ago by
 Description modified (diff)
comment:17 Changed 17 months ago by
 Dependencies changed from #21869, #24934, #22983, #25226 to #21869, #22983, #23020, #23164, #23168, #23169, #23170, #23171, #23173, #23182, #24934, #25226, #25227
comment:18 Changed 17 months ago by
 Dependencies changed from #21869, #22983, #23020, #23164, #23168, #23169, #23170, #23171, #23173, #23182, #24934, #25226, #25227 to #21869, #22983, #23020, #23164, #23168, #23169, #23170, #23171, #23173, #23182, #24934, #25226, #25227, #25228
 Description modified (diff)
comment:19 Changed 17 months ago by
 Branch set to u/saraedum/henselization
comment:20 Changed 17 months ago by
 Commit set to f841c6e5194bcac414e51635db9296d7c7c55142
 Description modified (diff)
comment:21 Changed 17 months ago by
 Dependencies changed from #21869, #22983, #23020, #23164, #23168, #23169, #23170, #23171, #23173, #23182, #24934, #25226, #25227, #25228 to #21869, #22983, #23020, #23164, #23168, #23169, #23170, #23171, #23173, #23182, #24934, #24655, #25226, #25227, #25228
 Description modified (diff)
comment:22 Changed 16 months ago by
 Branch u/saraedum/henselization deleted
 Commit f841c6e5194bcac414e51635db9296d7c7c55142 deleted
comment:23 Changed 16 months ago by
 Branch set to u/saraedum/22956
comment:24 Changed 14 months ago by
 Commit set to 7520220e3739038149ee2104c329f6a19ebd667e
 Keywords padicIMA added
Last 10 new commits:
d4d4c35  Merge remotetracking branch 'trac/u/saraedum/orders' into orders

5c1c320  add missing doctests

d402a21  Merge remotetracking branch 'trac/u/saraedum/orders' into henselization

ba5a7d0  Remove unused code

e14b8a7  Merge branch 'orders' into henselization

57e6d44  Teach more rings about irreducible polynomials

36faa36  Merge branch 'irreducible' into henselization

10b0144  Use default coercion/conversion maps when generating integer polynomials

f841c6e  Merge branch 'flint_poly_init' into henselization

7520220  Merge remotetracking branch 'trac/u/saraedum/henselization' into HEAD

Last 10 new commits:
fix pickling
Merge remotetracking branch 'trac/u/saraedum/orders' into orders
add missing doctests
Merge remotetracking branch 'trac/u/saraedum/orders' into henselization
Remove unused code
Merge branch 'orders' into henselization
Teach more rings about irreducible polynomials
Merge branch 'irreducible' into henselization
Use default coercion/conversion maps when generating integer polynomials
Merge branch 'flint_poly_init' into henselization