MR32: WIP: General extensions of p-adics

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Julian Rüth (@saraedum) opened a merge request at https://gitlab.com/sagemath/sage/-/merge_requests/32:

---

Implement extensions of p-adic fields with arbitrary base and (irreducible) defining polynomial using Xavier's `RingExtension` classes.

Things we're putting off until later (when there are references in `(parens)` below, then there is a corresponding `TODO: (see Merge Request 32 - parens)` in the source code.):

- [ ] Check that the rest of SageMath does not assume that all p-adic elements inherit from `pAdicGenericElement`. (Due to https://github.com/cython/cython/issues/4646, the general extension elements cannot inherit from `pAdicGeneralElement` and `RingExtensionElement` at the same time since they are both Cython classes. We did not really want any of the `pAdicGenericElement` methods since we almost always want to call through to the backend, so we decided to inherit from `RingExtensionElement`. However, some code might assume that all p-adic elements satisfy that `isinstance(x, pAdicGenericElement)`.)
- [ ] (krasner) Implement Krasner check to make sure that the exact defining polynomial describes a unique extension. See https://github.com/MCLF/henselization/blob/master/henselization/sage/rings/padics/henselization/henselization.py#L225 for an existing implementation.
- [ ] Make sure we have complete coverage.
- [ ] **TODO: Rewrite this task**: Implement `square_root`, `sqrt` and fix NotImplementedError("extending using the sqrt function not yet implemented")
- [ ] **TODO: Rewrite this task**: Implement `nth_root` and add extend parameter
- [ ] Add generic test methods such as `_test_trivial_powers`, `_test_expansions`, …
- [ ] Time conversions/coercions between ZZ, QQ, residue fields, p-adic rings. (We have touched quite a bit of the conversion/coercion code so we should make sure that we did not break performance of any of these, also for the old p-adic rings.)
- [ ] (coercions) Make sure conversions/coercions from/to the exact number field are working. They should not be created when `exact_field()` is called since they might have already been created by some other process. Instead, the p-adic parent should implement `_coerce_map_from_` and the number field `_convert_map_from_` appropriately. (Be careful not to create the p-adic parent in the number field's implementation and vice versa. It's easy to make everything very slow with checks such as `if other is self.exact_field()`.)
- [ ] (non-integral) Should we support non-integral defining polynomials somehow?
- [ ] (backend) The code that creates the backend should try the fast inexact p-adic code path first (`_create_backend_padic`), and if that fails (because of a PrecisionError or any other problem that we do not understand,) try the slow exact implementation (`_create_backend_exact`).
- [ ] (exact_field) Do not use `defining_polynomial(exact=True)` and `exact_field()` anywhere in our code unless absolutely necessary. (Creating a relative high-degree number field is extremely slow.) Instead, the exact modulus should be stored in the iterated polynomial quotient ring, i.e., replace the relative number field `K(f(ξ) = 0)` with the quotient `K[x]/f`. (Arithmetic in the latter is much slower, but we usually don't need to do any arithmetic there, exact maybe in `_create_backend_julian`.)
- [ ] (construction) Consider to change `construction()` of p-adic parents. Whenever a pushout is created (which e.g. often happens when evaluating a p-adic polynomial at some point) the `construction()` machinery either creates the ring of integers or creates the push out given by the algebraic extension underlying a p-adic parent. This can be extremely slow, and even worse often the attempt to form such a pushout leads to a recursive cascade of all kinds of p-adic extension rings and fields being constructed. It is unclear what should be done here exactly to improve upon this but maybe there is a better functor that describes a general extension (it's not CompletionFunctor at the exact field since constructing the exact field takes forever.)
- [ ] (integer_ring) Make sure that `integer_ring()` and `fraction_field()` of general extensions are fast. In principal these operations should be trivial since all the necessary data to describe the extension has already been computed. However, in practice they sometimes lead to a cascade of extensions being created.
- [ ] (extension) Ensure that `.extension()` does not call itself recursively more than necessary. Naturally, `.extension()` needs to call `.extension()` to create backend extension field. However, we should try to make sure that no accidental calls to `.extension()` happen as they often happen when pushouts are created. How to ensure this is completely unclear at the moment but this tends to make things relatively slow in some cases.
- [ ] (implementation) What is the meaning of the `implementation=` keyword of a general extension ring? Should the backend be created with this implementation? Currently, that keyword is ignored.
- [ ] (segfault) Fix segfaults. In calls to `CoercionModel.bin_op()`, sometimes the refcount to the parameters goes wrong. As a result, an object that should still be referenced is released and then things go terribly wrong (a p-adic element changes its type to an AttributeError, a method, then a weakref.) Why exactly this happens is currently unclear. However, we found that changing `bin_op` from `cpdef` to `def` fixes the problem (https://groups.google.com/g/cython-users/c/TQQka02k8dI.) It appears to us now that this is a bug in the code generation of Cython but maybe we're doing something wrong somewhere else. However, we can not see how this could possibly related to the p-adics changes we are making. So why are we only seeing this bug now? Apparently, due to the `construction()` of p-adic parents, finding a pushout/action sometimes becomes recursive cyling back to the original parent. This throws a CoercionException in `_register_pair`. This probably rarely happens in other parts of SageMath.
- [ ] Replace (or delete) padics/README.txt.

Depends on #26105 Depends on #28481 Depends on #21413

Component: padics

Keywords: padicBordeaux

Author: David Roe, Julian Rüth, Xavier Caruso

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

[saraedum]

Changed author from Julian Rüth to David Roe, Julian Rüth, Xavier Caruso

[saraedum]

Description changed:

[saraedum]

Changed keywords from none to padicBordeaux

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from bdf4b23 to 2379f40

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:4

New commits added to merge request. I updated the commit SHA-1. Last 10 new commits:

67c82c7	Merge branch 'develop' into 21413/class_ring_extension
8d70dbe	Code split in several files. More doctests.
efa3689	Doctest for BaseActionOnRing
7f8ce2d	Doctest for the class AlgebraToRing_coercion
991cc70	Doctest for the class AlgebraFMElement
036fb2a	Adding licence & author
5c1c5b6	Merge 7.6.beta2
0b86df7	Merge branch 'develop' into t/21413/21413/class_ring_extension
656ec77	Small fixes
2379f40	Merge branch 'u/caruso/21413/class_ring_extension' of git://trac.sagemath.org/sage into 21413_ring_extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 2379f40 to 2b29e92

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:5

New commits added to merge request. I updated the commit SHA-1. Last 10 new commits:

77332e0	Disable the construction L/K
631f228	backend morphism and tower of extensions
07481dd	Ring extensions with basis
22d7f4d	add class RingExtensionWithGen
dfef02d	Merge branch '21413_ring_extensions' into general-extensions
d4a35ac	Add base_map to homomorphisms defined by images of generators
1f78dd4	Fix some doctests
84704ba	Fix doctests and py3, incorporate small reviewer suggestion
3455e63	Merge branch '26105_base_hom' into general-extensions
2b29e92	Moving code from padics/generic_nodes.py to simpler implementations in padics/padic_extension_generic.py

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 2b29e92 to e6b9e74

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:6

New commits added to merge request. I updated the commit SHA-1. New commits:

e6b9e74

Add e() and f() for relative p-adic extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:7

New commits added to merge request. I updated the commit SHA-1. New commits:

2566db5	Make things relative
6fc7e5f	move code and rename classes
81e4a22	check arguments for finite free ring extensions
abae222	Merge branch 'u/caruso/21413/class_ring_extension' of git://trac.sagemath.org/sage into general-extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from e6b9e74 to abae222

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:8

New commits added to merge request. I updated the commit SHA-1. New commits:

fa57ca1	use RingExtensionWithBasis for general p-adic extensions
1d2850d	Establish the basic extension framework
9e430b1	towards trivial extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from abae222 to 9e430b1

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 9e430b1 to e4b60dd

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:9

New commits added to merge request. I updated the commit SHA-1. New commits:

c99fa82	morphisms between RingExtensions now support im_gens
6a52519	Merge branch 't/26105/26105_base_hom' into t/21413/21413/class_ring_extension
0433a1a	more work on morphisms
e4b60dd	Merge remote-tracking branch 'trac/u/caruso/21413/class_ring_extension' into general-extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from e4b60dd to 3f945c1

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:10

New commits added to merge request. I updated the commit SHA-1. New commits:

c4f2a3f	Fix _is_valid_homomorphism_
ac1c05a	Documenting category and base_map options
1738aa9	Fix some doctests, remove category keywords from doctests
3f945c1	Merge branch '26105_base_hom' into general-extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:11

New commits added to merge request. I updated the commit SHA-1. New commits:

45da59b	Implement `_im_gens_` and _is_valid_homomorphism_
0360897	Merge branch '28487_padic_morphisms' into general-extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 3f945c1 to 0360897

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 0360897 to c56b013

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:12

New commits added to merge request. I updated the commit SHA-1. New commits:

d0e0953	Add base_map to finite_field homsets
16feb8d	Fix some errors with positional check arguments
c56b013	Merge branch '26105_base_hom' into general-extensions

[roed314]

comment:13

The following generates infinite recursion:

sage: R.<x> = ZZ[]
sage: K.<a> = Qp(2).extension(x)

[xcaruso]

Dependencies: #26105, #28481, #21413

[xcaruso]

Changed branch from u/galois/mrs/32/general-extensions to u/caruso/mrs/32/general-extensions

[xcaruso]

comment:16

Fixed. But it still doesn't work because Qp(2) does not implement free_module

[xcaruso]

Changed branch from u/caruso/mrs/32/general-extensions to u/galois/mrs/32/general-extensions

[embray]

comment:17

Ticket retargeted after milestone closed

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:18

New commits added to merge request. I updated the commit SHA-1. New commits:

46d7bee

Merge branch 'general-extensions' of gitlab.com:sagemath/dev/sage into general-extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from c56b013 to 46d7bee

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:19

New commits added to merge request. I updated the commit SHA-1. New commits:

0e1097d

Merge branch 'develop' into general-extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 46d7bee to 0e1097d

[mkoeppe]

comment:20

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:22

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:23

Setting a new milestone for this ticket based on a cursory review.

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 0e1097d to ece6ca8

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:25

New commits added to merge request. I updated the commit SHA-1. New commits:

ece6ca8

Merge remote-tracking branch 'trac/develop' into general-extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:26

New commits added to merge request. I updated the commit SHA-1. New commits:

b9ce455	Fix category of padic rings
0db38c2	Drop split() function
e4ae500	Add renaming TODOs for general p-adics extensions
e1d34d9	Fix missing import
dcb2a21	Fix absolute_ring() doctest

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from ece6ca8 to dcb2a21

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from dcb2a21 to 2d2dc8c

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:27

New commits added to merge request. I updated the commit SHA-1. New commits:

b2808f7	Fix printing of two-step extensions
2d2dc8c	Added some long time markers

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 2d2dc8c to 0f20064

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:28

New commits added to merge request. I updated the commit SHA-1. New commits:

4d3757d	Fix initialization of general extension elements
3c81737	Implement generators of general p-adic extensions
9df4334	Correctly initialize generic p-adic base rings
f5114a8	Do not attempt to access cdef fields from Python code
0f20064	Fix unramified detection in p-adic factory

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 0f20064 to 73936a6

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:29

New commits added to merge request. I updated the commit SHA-1. New commits:

c485fd2	Test e() and f() for trivial extensions
deb180a	Fix some lint
81366e0	Fix pAdicGeneralExtension.absolute_ring()
8f58009	Simplify handling of exact_modulus in p-adic extension rings
3278623	Add exact_valuation() for exact_field() of p-adics
76106b8	Ring extension defined by generator for general p-adic extensions
ca9ef97	Remove obsolete TODO
73936a6	Force correct normalization of exact modulus of p-adic extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 73936a6 to 3af812e

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:30

New commits added to merge request. I updated the commit SHA-1. New commits:

60b4f78	Fix change() when resetting q
204076f	Implement absolute_f() and absolute_e() for general extensions
3af812e	Implement simple general unramified extensions of p-adic base rings

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from 3af812e to f7e6ff9

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:31

New commits added to merge request. I updated the commit SHA-1. Last 10 new commits:

22d02b2	Fix gens() of padic extensions
193dbd1	Fix backend access in general extension element
22ecf6e	Fix printing of trivial extensions
1231555	Implement residue_class_field() of general extensions
572e6a2	Fixing doctests
fca317b	Merge remote-tracking branch 'gitlab/finite-field-relative' into general-extensions
7bdf55f	Work around randomness in factoring doctest
51dab21	Fix printing of relative finite fields
19f16de	Allow conversion of lists to p-adic elements with valshift
f7e6ff9	Print trivial extensions properly

[f588ca1e-f96a-4dea-804d-c55eab873dab]

comment:32

New commits added to merge request. I updated the commit SHA-1. New commits:

eef22fd	Fixing doctests
07c7ec0	Fix printing of trivial finite field extensions
4e4fdb3	Merge branch 'finite-field-relative' of gitlab.com:sagemath/dev/sage into finite-field-relative
6d45965	Restore old behavior of augmented valuations
e4acc8a	Merge branch 'finite-field-relative' into general-extensions
db8d954	Drop unused import
4be14a1	Fix embeddings between trivial extensions
1883a97	Merge branch 'finite-field-relative' into general-extensions

[f588ca1e-f96a-4dea-804d-c55eab873dab]

Changed commit from f7e6ff9 to 1883a97