Opened 2 years ago

Last modified 14 months ago

#22956 new enhancement

p-adic completions/Henselizations backed by exact rings

Reported by: saraedum Owned by:
Priority: major Milestone: sage-8.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 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. (#23020)
  2. Orders are not unique parents. (#24934)
  3. PolynomialQuotientRing should be a unique parent. (#22983)
  4. Do not sort factorizations (#25226)
  5. More polynomials need to be irreducible (#25227)
  6. Fix initialization problems of integer polynomials (#25228)
  7. (is_irreducible should be cached) (#23164)
  8. (is_squarefree should be cached) (#23182)
  9. (is_irreducible should be able to call _is_irreducible_univariate_polynomial on the base ring.) (#23168)
  10. (is_squarefree should be able to call _is_squarefree_univariate_polynomial on the base ring.) (#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)) (#23170)
  12. (gcd(a,a) is a should be true for polynomials over number fields.) (#23171)
  13. (Remove Element._cache_key that someone forgot to delete when taking out Element.__hash__.) (#23173)

Change History (24)

comment:1 Changed 2 years ago by saraedum

  • Description modified (diff)

comment:2 Changed 2 years ago by saraedum

  • Description modified (diff)

comment:3 Changed 2 years ago by saraedum

  • Description modified (diff)

comment:4 Changed 2 years ago by saraedum

  • Description modified (diff)
  • Keywords sd86.5 added

comment:5 Changed 2 years ago by saraedum

  • Description modified (diff)

comment:6 Changed 2 years ago by saraedum

  • Description modified (diff)

comment:7 Changed 2 years ago by saraedum

  • Description modified (diff)

comment:8 Changed 2 years ago by saraedum

  • Description modified (diff)

comment:9 Changed 2 years ago by roed

  • Keywords sd87 added

comment:10 Changed 19 months ago by saraedum

  • Description modified (diff)

comment:11 Changed 19 months ago by saraedum

  • Description modified (diff)

comment:12 Changed 19 months ago by saraedum

  • Dependencies changed from #21869 to #21869, #24934

comment:13 Changed 19 months ago by saraedum

  • Dependencies changed from #21869, #24934 to #21869, #24934, #22983
  • Description modified (diff)

comment:14 Changed 17 months ago by saraedum

  • Dependencies changed from #21869, #24934, #22983 to #21869, #24934, #22983, #25226

comment:15 Changed 17 months ago by saraedum

  • Description modified (diff)

comment:16 Changed 17 months ago by saraedum

  • Description modified (diff)

comment:17 Changed 17 months ago by saraedum

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

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

  • Branch set to u/saraedum/henselization

comment:20 Changed 17 months ago by saraedum

  • Commit set to f841c6e5194bcac414e51635db9296d7c7c55142
  • Description modified (diff)

Last 10 new commits:

a39d7b0fix pickling
d4d4c35Merge remote-tracking branch 'trac/u/saraedum/orders' into orders
5c1c320add missing doctests
d402a21Merge remote-tracking branch 'trac/u/saraedum/orders' into henselization
ba5a7d0Remove unused code
e14b8a7Merge branch 'orders' into henselization
57e6d44Teach more rings about irreducible polynomials
36faa36Merge branch 'irreducible' into henselization
10b0144Use default coercion/conversion maps when generating integer polynomials
f841c6eMerge branch 'flint_poly_init' into henselization

comment:21 Changed 17 months ago by saraedum

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

  • Branch u/saraedum/henselization deleted
  • Commit f841c6e5194bcac414e51635db9296d7c7c55142 deleted

comment:23 Changed 16 months ago by saraedum

  • Branch set to u/saraedum/22956

comment:24 Changed 14 months ago by roed

  • Commit set to 7520220e3739038149ee2104c329f6a19ebd667e
  • Keywords padicIMA added

Last 10 new commits:

d4d4c35Merge remote-tracking branch 'trac/u/saraedum/orders' into orders
5c1c320add missing doctests
d402a21Merge remote-tracking branch 'trac/u/saraedum/orders' into henselization
ba5a7d0Remove unused code
e14b8a7Merge branch 'orders' into henselization
57e6d44Teach more rings about irreducible polynomials
36faa36Merge branch 'irreducible' into henselization
10b0144Use default coercion/conversion maps when generating integer polynomials
f841c6eMerge branch 'flint_poly_init' into henselization
7520220Merge remote-tracking branch 'trac/u/saraedum/henselization' into HEAD
Note: See TracTickets for help on using tickets.