function fields over towers of finite fields don't work

[swewers]

The following gives an error:

sage: R0.<z> = GF(2)[]
sage: k1 = GF(2).extension(z^2+z+1, 'z1')
sage: R1.<z> = k1[]
sage: k2 = k1.extension(z^2+z+k1.gen(), 'z2')
sage: k2
Univariate Quotient Polynomial Ring in z2 over Finite Field in z1 of size 2^2 with modulus z2^2 + z2 +z1
sage: F.<x> = FunctionField(k2)
sage: F.derivation()

NotImplementedError                       Traceback (most recent call last)

The problem is that k2, although a finite field, is not constructed as a 'true' finite field, and k2.is_perfect() is not implemented (and there are probably many more problems with
function fields over such a field).

However, fields as k2 occur frequently as residue fields of valuations, and there seems to be no easy way to construct an isomorphism from k2 to an isomorphic 'true' finite field.

TODO:

• Fix #26161
• Fix #26105
• Fix #26103 once #26105 and #26161 have been merged.
• Fix #28485

[swewers]

This is related to issue #66, in that the residue field of a valuation should have the 'natural type', e.g. a function field over a 'true' finite field.

[swewers]

Another problem is that factoring of polynomials over towers of fields is rediculously slow.

[swewers]

I was not able to construct a homomorphism from k2 into an isomorphic finite field. The problem is that although k2 is a quotient of a polynomial ring, k2.cover() is not implemented, and this seems to make
it impossible to construct a morphism from k2 to another ring which is not a coercion on the base ring of k2.

[swewers]

It seems that Sage can be fooled by setting check=False when defining a homomorphism on k2, induced from a homomorphism on k2.cover_ring():

def make_finite_field(k):
     r""" Return the finite field isomorphic to this field.

     INPUT:

     - ``k`` -- a finite field

     OUTPUT: a pair `(k_1,\phi)` where `k_1` is a 'true' finite field
     and `\phi` is an isomorphism from `k` to `k_1`.

    This function is useful when `k` is constructed as a tower of extensions
    with a finite field as a base field.

    """
    from sage.categories.finite_fields import FiniteFields

    assert k.is_field()
    assert k.is_finite()
    if k in FiniteFields:
        return k, k.hom(k.gen(), k)
    else:
        k0 = k.base_field()
        G = k.modulus()
        assert G.parent().base_ring() is k0
        k0_new, phi0 = make_finite_field(k0)
        G_new = G.map_coefficients(phi0, k0_new)
        k_new = k0_new.extension(G_new.degree())
        alpha = G_new.roots(k_new)[0][0]
        Pk0 = k.cover_ring()
        Pk0_new = k0_new[Pk0.variable_name()]
        psi1 = Pk0.hom(phi0, Pk0_new)
        psi2 = Pk0_new.hom(alpha, k_new)
        psi = psi1.post_compose(psi2)
        # psi: Pk0 --> k_new
        phi = k.hom(Pk0.gen(), Pk0, check=False)
        phi = phi.post_compose(psi)
        return k_new, phi

[swewers]

Defining a homomorphism on the fraction field of a polynomial ring doesn't work as expected:

sage: l = GF(3)
sage: k0 = PolynomialRing(l, 'x').fraction_field()
sage: k1 = FunctionField(l, 'x')
sage: phi = k0.hom(k1.gen(), k1)
sage: phi
Ring morphism:
  From: Fraction Field of Univariate Polynomial Ring in x over Finite Field of size 3
  To:   Rational function field in x over Finite Field of size 3
  Defn: x |--> x
sage: phi(k0.gen())

NotImplementedError                       Traceback (most recent call last)
...
NotImplementedError: 

[saraedum]

I am also having a look at this now.

[saraedum]

Do I understand correctly that solving #66 would solve this?

[swewers]

Hopefully, yes, but we would have to make it more precise what a solution of #66 would mean.

[saraedum]

Ok. I mean, all the finite fields you are having trouble with are residue fields of valuations? Or are you also creating iterated extensions yourself?

[saraedum]

So one thing we'd need would be a simple_model(base=None) on polynomial quotient rings that returns the polynomial ring as a simple extension of base (where base defaults to the prime subfield) together with isomorphisms.

[saraedum]

I created https://trac.sagemath.org/ticket/26103 for this. I hope that I'll find some time to work on it tomorrow.

[swewers]

Ok. I mean, all the finite fields you are having trouble with are residue fields of valuations? Or are you also creating iterated extensions yourself?

I try to use k.extension(n) which creates another finite fields with card(k)^n elements. It seems that there is a natural embedding of k into this extension:

sage: k0 = GF(2)
sage: k1 = k0.extension(2)
sage: k1
Finite Field in z2 of size 2^2
sage: k1.has_coerce_map_from(k0)
True
sage: k2 = k1.extension(3)
sage: k2
Finite Field in z6 of size 2^6
sage: k2.has_coerce_map_from(k1)
True
sage: k3 = k0.extension(3)
sage: k2.has_coerce_map_from(k3)
True

So for 'true' finite fields, it is assumed that are all embedded into one algebraic closure of FF_p. That is fine, IMO. If one wants to have specific embeddings (which may be the case), you can do this yourself.
However, once k is not a true finite field anymore, k.embedding(n) doesn't work anymore, and one has to create another explicit simple extension on top of k.

An example where I had to do this is in the branch fix_urgent_bug, in smooth_projective_curves.py, line 1208-1214.

[swewers]

So one thing we'd need would be a simple_model(base=None) on polynomial quotient rings that returns the polynomial ring as a simple extension of base (where base defaults to the prime subfield) together with isomorphisms.

Wouldn't it be enough if k.extension(f) created an extension field, together with an underlying absolute finite field, just like for number fields?

[saraedum]

Yes but that's harder to do I think. There is sage.coding.relative_finite_field_extension which I just found out about. And there were several attempts to create relative fields, e.g., https://trac.sagemath.org/ticket/23316.

[swewers]

Actually, for me simple_model(k, base=None) would be enough. That's approximately what I was trying to do with make_finite_field (see comment above).