ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 13 Jun 2018 05:00:51 -0500Algorithm for finding a defining polynomial for an unramified extension?http://ask.sagemath.org/question/42575/algorithm-for-finding-a-defining-polynomial-for-an-unramified-extension/ I wanted to know by what algorithm sage finds a defining polynomial of an unramified extension of p-adic numbers?Tue, 12 Jun 2018 15:38:01 -0500http://ask.sagemath.org/question/42575/algorithm-for-finding-a-defining-polynomial-for-an-unramified-extension/Answer by j.c. for <p>I wanted to know by what algorithm sage finds a defining polynomial of an unramified extension of p-adic numbers?</p>
http://ask.sagemath.org/question/42575/algorithm-for-finding-a-defining-polynomial-for-an-unramified-extension/?answer=42581#post-id-42581The short answer is that this will depend on the way you defined your unramified extension. If, for instance, you defined it using `Zq` or `Qq` applied to $p^n$ for small $p,n$ then what is returned is likely to be a [Conway polynomial](https://en.wikipedia.org/wiki/Conway_polynomial_(finite_fields)) from a database included in SageMath based on the work of Frank Lübeck.
If there's some other specific case you're interested in, perhaps you can edit your question to include the code that constructs that particular extension.
----
What follows is "the long answer", or how I found this out, starting from knowing essentially nothing about algebraic number theory or any of SageMath's ANT functionality. Hopefully the description of the steps I took in diving into SageMath's source code will be helpful for you in finding the answers to any similar questions you might have in the future.
Suppose we've defined R as follows:
R.<a> = Zq(1024)
Then we can type
?R.defining_polynomial()
to look at the docstring for this particular function.
The resulting output, while somewhat helpful, does not explain what algorithm SageMath is using to compute it. However, it does contain a line pointing to the source code, something like:
File: /Applications/SageMath/local/lib/python2.7/site-packages/sage/rings/padics/padic_extension_generic.py
Now, it's a bit more convenient to look at this file online in e.g. [the github mirror of the SageMath source code](https://github.com/sagemath/sage). I've linked to the specific line where the definition of `defining_polynomial()` is [here](https://github.com/sagemath/sage/blob/master/src/sage/rings/padics/padic_extension_generic.py#L205).
In this case, it appears that this code simply returns `_given_poly`, which [is defined in the class `pAdicExtensionGeneric`](https://github.com/sagemath/sage/blob/master/src/sage/rings/padics/padic_extension_generic.py#L49) as one of the parameters to the class constructor. We never called this directly above; instead, we called `Zq`, so we should look for the code there.
We find that `Zq` is defined in `sage/rings/padics/factory.py`, specifically [here](https://github.com/sagemath/sage/blob/854f9764d14236110b8d7f7b35a7d52017e044f8/src/sage/rings/padics/factory.py#L1825). In the documentation to Zq, we find that either the polynomial can be specified by hand, or:
>By default, the polynomial chosen is the standard lift of the generator chosen for $\mathbb{F}_q$.
In fact, we could have skipped some of the code-diving above as SageMath's reference site has a [thematic tutorial on p-adics](http://doc.sagemath.org/html/en/reference/padics/sage/rings/padics/tutorial.html), see [the documentation of `Zq` on the second page](http://doc.sagemath.org/html/en/reference/padics/sage/rings/padics/factory.html#sage.rings.padics.factory.Zq).
However, to find the details of the "generator chosen for $\mathbb{F}_q$", we must return to the code:
The code implementing this can be found [here](https://github.com/sagemath/sage/blob/854f9764d14236110b8d7f7b35a7d52017e044f8/src/sage/rings/padics/factory.py#L2354), which uses the `modulus()` function in the `FiniteField` class in `sage/rings/finite_rings/finite_field_constructor.py`.
Looking at [the relevant part of that code](https://github.com/sagemath/sage/blob/854f9764d14236110b8d7f7b35a7d52017e044f8/src/sage/rings/finite_rings/finite_field_constructor.py#L569), we see that `modulus()` is constructed from `R.irreducible_element(n)` where `R = PolynomialRing(FiniteField(p), 'x')` and where $p,n$ are $2,10$ respectively because the order we chose above was 1024.
If we look at the code for the class `PolynomialRing`, we find that [its definition is split into different cases](https://github.com/sagemath/sage/blob/854f9764d14236110b8d7f7b35a7d52017e044f8/src/sage/rings/polynomial/polynomial_ring_constructor.py#L696), and the relevant one here is `PolynomialRing_dense_mod_p`. The function `irreducible_element()` is [defined within](https://github.com/sagemath/sage/blob/854f9764d14236110b8d7f7b35a7d52017e044f8/src/sage/rings/polynomial/polynomial_ring.py#L2999) and we see that the default polynomial returned in this case comes from `sage/rings/finite_rings/conway_polynomials.py` ([here](https://github.com/sagemath/sage/blob/854f9764d14236110b8d7f7b35a7d52017e044f8/src/sage/rings/finite_rings/conway_polynomials.py)), which in turn relies on `sage/databases/conway.py` ([here](https://github.com/sagemath/sage/blob/07d6c37d18811e2b377a9689790a7c5e24da16ba/src/sage/databases/conway.py)), where we finally find the information that the database comes from Frank Lübeck's tables.
Wed, 13 Jun 2018 05:00:51 -0500http://ask.sagemath.org/question/42575/algorithm-for-finding-a-defining-polynomial-for-an-unramified-extension/?answer=42581#post-id-42581