MR32: WIP: General extensions of p-adics

[sagetrac-gitlab-bot]

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]

Changed keywords from none to padicBordeaux

[sagetrac-gitlab-bot]

Changed commit from bdf4b23 to 2379f40

[sagetrac-gitlab-bot]

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

[sagetrac-gitlab-bot]

Changed commit from 2379f40 to 2b29e92

[sagetrac-gitlab-bot]

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

[sagetrac-gitlab-bot]

Changed commit from 2b29e92 to e6b9e74

[sagetrac-gitlab-bot]

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

[sagetrac-gitlab-bot]

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

[sagetrac-gitlab-bot]

Changed commit from e6b9e74 to abae222

[sagetrac-gitlab-bot]

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

[sagetrac-gitlab-bot]

Changed commit from abae222 to 9e430b1

[sagetrac-gitlab-bot]

Changed commit from 9e430b1 to e4b60dd

[sagetrac-gitlab-bot]

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

[sagetrac-gitlab-bot]

Changed commit from e4b60dd to 3f945c1

[sagetrac-gitlab-bot]

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

[sagetrac-gitlab-bot]

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

[sagetrac-gitlab-bot]

Changed commit from 3f945c1 to 0360897

[sagetrac-gitlab-bot]

Changed commit from 0360897 to c56b013

[sagetrac-gitlab-bot]

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

[sagetrac-gitlab-bot]

Changed commit from 480d005 to e90f40b

[sagetrac-gitlab-bot]

comment:121

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

e90f40b

Work around segfault

[sagetrac-gitlab-bot]

comment:123

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

538345b

Link TODOs in MR 32

[sagetrac-gitlab-bot]

Changed commit from e90f40b to 538345b

[sagetrac-gitlab-bot]

Changed commit from 538345b to b6d60a0

[sagetrac-gitlab-bot]

comment:128

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

8ef666b	set variable name (not sure it's better like this)
b6d60a0	Merge branch 'general-extensions' of gitlab.com:sagemath/dev/sage into general-extensions

[sagetrac-gitlab-bot]

Changed commit from b6d60a0 to 68ad527

[sagetrac-gitlab-bot]

comment:129

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

a707c0c	accelerate computation of generator
68ad527	small optimization

[mkoeppe]

Removed branch from issue description; replaced by PR #34993