p-adic completions/Henselizations backed by exact rings

[saraedum]

All p-adic 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 p-adic 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 p-adic 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 monkey-patched; the ones in parentheses are for better performance):

The attached branch contains all these changes.

1. Polynomials should not require coefficients to implement __nonzero__ for printing. (Do not require coefficient's __nonzero__ to be implemented for polynomial printing #23020)
2. Orders are not unique parents. (Orders are not unique parents #24934)
3. PolynomialQuotientRing should be a unique parent. (polynomial quotient rings are unique parents #22983)
4. Do not sort factorizations (Do not sort inductive valuations #25226)
5. More polynomials need to be irreducible (More polynomials should know that they are irreducible #25227)
6. Fix initialization problems of integer polynomials (Use coercion maps when initializing polynomials in ℤ[x] #25228)
7. (is_irreducible should be cached) (cache Polynomial.is_irreducible() #23164)
8. (is_squarefree should be cached) (Cache is_squarefree() for polynomials #23182)
9. (is_irreducible should be able to call _is_irreducible_univariate_polynomial on the base ring.) (is_irreducible can be implemented on the parent as _is_irreducible_univariate_polynomial #23168)
10. (is_squarefree should be able to call _is_squarefree_univariate_polynomial on the base ring.) (is_squarefree can be implemented on the base as _is_squarefree_univariate_polynomial #23169)
11. (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)) (Stability for the generators of principal ideals #23170)
12. (gcd(a,a) is a should be true for polynomials over number fields.) (Stability for gcd(x,x) #23171)
13. (Remove Element._cache_key that someone forgot to delete when taking out Element.__hash__.) (Remove Element._cache_key() #23173)

Depends on #21869
Depends on #22983
Depends on #23020
Depends on #23164
Depends on #23168
Depends on #23169
Depends on #23170
Depends on #23171
Depends on #23173
Depends on #23182
Depends on #24934
Depends on #24655
Depends on #25226
Depends on #25227
Depends on #25228

CC: @roed314 @xcaruso

Component: padics

Keywords: sd86.5, sd87, padicIMA

Author: Julian Rüth

Branch/Commit: u/saraedum/22956 @ 7520220

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

[saraedum]

Changed keywords from none to sd86.5

[roed314]

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

[saraedum]

Changed dependencies from #21869 to #21869, #24934

[saraedum]

Changed dependencies from #21869, #24934 to #21869, #24934, #22983

[saraedum]

Changed dependencies from #21869, #24934, #22983 to #21869, #24934, #22983, #25226

[saraedum]

Changed dependencies from #21869, #24934, #22983, #25226 to #21869, #22983, #23020, #23164, #23168, #23169, #23170, #23171, #23173, #23182, #24934, #25226, #25227

[saraedum]

Changed dependencies 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

[saraedum]

Branch: u/saraedum/henselization

[saraedum]

Last 10 new commits:

a39d7b0	fix pickling
d4d4c35	Merge remote-tracking branch 'trac/u/saraedum/orders' into orders
5c1c320	add missing doctests
d402a21	Merge remote-tracking 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

[saraedum]

Commit: f841c6e

[saraedum]

Changed dependencies 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

[saraedum]

Changed commit from f841c6e to none

[saraedum]

Changed branch from u/saraedum/henselization to none

[saraedum]

Branch: u/saraedum/22956

[roed314]

Last 10 new commits:

d4d4c35	Merge remote-tracking branch 'trac/u/saraedum/orders' into orders
5c1c320	add missing doctests
d402a21	Merge remote-tracking 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 remote-tracking branch 'trac/u/saraedum/henselization' into HEAD

[roed314]

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

[roed314]

Commit: 7520220