Skip to content

WIP: General extensions of p-adics

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.
Edited by Julian Rüth

Merge request reports

Loading