Support base_morphism for hom(im_gens)

[saraedum]

Currently, the method .hom(im_gens) on parents allows you to define the images of the generators of a structure. This is assuming that the coefficients of these generators can be sent to the codomain with some canonical coercion.

This is often insufficient, e.g., in the case of polynomial rings where you would also like to define a map that translate the ring of coefficients non-canonically. Note that function fields already have a specialized .hom() implementation that supports this feature.

See #26103 for a followup.

[saraedum]

roed, caruso: I am curious to hear what you think about this. I have been stumbling upon this several times during the past years.

[jdemeyer]

The problem with im_gens is that it's not really mathematically defined in the first place. So I wouldn't try to add more functionality to it.

Instead, I would define a specific morphism class for polynomial rings. Mathematically, a ring morphism from a polynomial ring is defined by a morphism of the base together with the images of the generators. That was my plan for #25558 but I stopped working on that...

[saraedum]

Polynomial rings are just one example. Another one (see #26103) are extensions, say an extension of a finite field where I would like to define a map k(α)→l.

But I think I also had this issue with fraction fields before.

I agree, that specialized morphism classes can be nice because they might have more knowledge about the objects involved (say to implement is_injective()/is_surjective()) but I don't want to implement a new class whenever I need a map between new types of parents and generic code might do that as well.

Maybe I'll just use a SetMorphism if I shouldn't extend hom() though I personally don't like these.

Anyway, let me give a try at extending hom() and see what the result looks like.

[saraedum]

Looking at the ring homomorphism code brings back bad memories from #23204. Maybe I don't want to add more to morphism.pyx and homset.py as these should probably be drastically simplified if anything.

[jdemeyer]

Replying to saraedum:

I agree, that specialized morphism classes can be nice because they might have more knowledge about the objects involved (say to implement is_injective()/is_surjective()) but I don't want to implement a new class whenever I need a map between new types of parents and generic code might do that as well.

Of course, if it works using generic code, that's fine for me. But it might be harder to do it that way. I'm pretty sure that some of the existing issues with morphism are precisely because code wants to be too generic and doesn't really know what it is doing.

[jdemeyer]

Replying to saraedum:

Another one (see #26103) are extensions, say an extension of a finite field where I would like to define a map k(α)→l.

But this is really a map induced by a polynomial ring map k[x] → l. We already have a class for such maps induced on a quotient, so we just need the polynomial ring map.

[saraedum]

Replying to jdemeyer:

Replying to saraedum:

Another one (see #26103) are extensions, say an extension of a finite field where I would like to define a map k(α)→l.

But this is really a map induced by a polynomial ring map k[x] → l. We already have a class for such maps induced on a quotient, so we just need the polynomial ring map.

I am not sure I understand. If k is not a prime field, then how would I would I define my map k[x]→l?

[jdemeyer]

Replying to saraedum:

I am not sure I understand. If k is not a prime field, then how would I would I define my map k[x]→l?

By giving a map k → l and the image of x.

If k is not a prime finite field, then use recursion: k = f[α], so k → l is induced by a map f[x] → l.

[saraedum]

Sorry, my question was how to do this in Sage precisely. So, I can map k(α)→k[x] by mapping the generator to x. Then I map k[x]→l[x] by using an induced map. Finally I use the evaluation l[x]→l. But are people really supposed to figure this out on their own?

If I understand your proposal in comment 7 above, you would like to see a shortcut to define k[x]→l as (k[x]).hom(α', base_morphism=k→l). But why not go all the way and allow people to write (k(α)).hom(α', base_morphism=k→l)?

[jdemeyer]

Replying to saraedum:

But why not go all the way and allow people to write (k(α)).hom(α', base_morphism=k→l)?

I'm only talking about the implementation. What you "allow people to write" is an entirely different discussion.

[saraedum]

An alternative might be to just document these things in the docstring of hom().

[caruso]

@saraedum: I'm not sure that I understand what you have in mind. Could you please give a short concrete example of what you would like to see implemented, please?

[saraedum]

A concrete example where I would like to be able to specify a base_morphism is the following:

sage: k = GF(2)
sage: R.<a> = k[]
sage: l.<a> = k.extension(a^3 + a^2 + 1)
sage: R.<b> = l[]
sage: m.<b> = l.extension(b^2 + b + a)
sage: n.<z> = GF(2^6)

sage: m.hom([z^4 + z^3 + 1], base_morphism=l.hom([z^5 + z^4 + z^2]))

[roed]

I fixed a few other things as well:

• a whitespace issue in parent.pyx (a function indented three spaces rather than 4)
• Changed some double underscore attributes to single underscore
• Switched some custom caching to cached_method.

---

New commits:

​d4a35ac	Add base_map to homomorphisms defined by images of generators
​1f78dd4	Fix some doctests

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​84704ba

Fix doctests and py3, incorporate small reviewer suggestion

[caruso]

Replying to saraedum:

A concrete example where I would like to be able to specify a base_morphism is the following:

sage: k = GF(2)
sage: R.<a> = k[]
sage: l.<a> = k.extension(a^3 + a^2 + 1)
sage: R.<b> = l[]
sage: m.<b> = l.extension(b^2 + b + a)
sage: n.<z> = GF(2^6)

sage: m.hom([z^4 + z^3 + 1], base_morphism=l.hom([z^5 + z^4 + z^2]))

This example raises the following error with the current implementation:

Traceback (most recent call last)
...
ValueError: relations do not all (canonically) map to 0 under map determined by images of generators

[caruso]

A similar problem occurs with Lie algebras:

sage: R.<x> = ZZ[]
sage: K.<i> = NumberField(x^2 + 1)
sage: cc = K.hom([-i])
sage: L.<X,Y,Z,W> = LieAlgebra(K, {('X','Y'): {'Z':i}, ('X','Z'): {'W':1}})
sage: M.<A,B,C,D> = LieAlgebra(K, {('A','B'): {'C':i}, ('A','C'): {'D':1}})
sage: phi = L.morphism({X:A, Y:B, Z:C, W:D}, base_map=cc)

The last line should raise an error since phi is not a Lie Algebra morphism:

sage: phi(X.bracket(Y))
-i*C
sage: phi(X).bracket(phi(Y))
i*C

In the same fashion, if I define:

sage: phi = L.morphism({X:A,Y:B,W:D}, base_map=cc)

I expect Z to be mapped to -C but this is not the case:

sage: phi(Z)
C

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c4f2a3f	Fix _is_valid_homomorphism_
​ac1c05a	Documenting category and base_map options

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​1738aa9

Fix some doctests, remove category keywords from doctests

[roed]

Okay, I think I've addressed Xavier's comments.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d0e0953

Add base_map to finite_field homsets

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​16feb8d

Fix some errors with positional check arguments

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c48e142	Fix pyflakes
​aa84741	Fix some doctests

[caruso]

There are still issues with Lie algebra:

sage: R.<x> = ZZ[]
sage: K.<i> = NumberField(x^2 + 1)
sage: cc = K.hom([-i])
sage: L.<X,Y,Z> = LieAlgebra(K, {('X','Y'): {'Z':i}})
sage: M.<A,B,C> = LieAlgebra(K, {('A','B'): {'C':-i}})
sage: phi = L.morphism({X:A, Y:B, Z:C}, base_map=cc)
Traceback (most recent call last):
ValueError: this does not define a Lie algebra morphism; contradictory values for brackets of length 2

but I think that phi is a well-defined semi-linear morphism of Lie algebras.

The checking is performed in the __init__ function of LieAlgebraMorphism_from_generators (starting at line 474 of src/sage/algebras/lie_algebras/morphism.py).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3d73776

Fixing Lie algebra morphisms

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​72b677c

change_ring -> map_coefficients and fix composition of morphisms defined by images of generators

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d780c6f

Change base_map so that the codomain is always the codomain of the map

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​bfcbebe

Fix bug in composition

[caruso]

LGTM (see also discussion on Zulip).

Positive review when patchbot is happy.

[caruso]

There are failing doctests.

File "src/sage/rings/morphism.pyx", line 837, in sage.rings.morphism.RingHomomorphism._composition_
Failed example:
    (f*f).base_map()
Expected:
    Ring morphism:
      From: Univariate Polynomial Ring in x over Rational Field
      To:   Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
      Defn: x |--> 2*x
Got:
    Ring morphism:
      From: Univariate Polynomial Ring in x over Rational Field
      To:   Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
      Defn: x |--> 2*x
            with map of base ring
**********************************************************************
File "src/sage/rings/morphism.pyx", line 1117, in sage.rings.morphism.RingHomomorphism_im_gens.__init__
Failed example:
    phi = S.hom([xx+1,xx-1],check=False)
Expected:
    Traceback (most recent call last):
    ...
    TypeError: images do not define a valid homomorphism
Got:
    <BLANKLINE>
**********************************************************************
File "src/sage/rings/morphism.pyx", line 1192, in sage.rings.morphism.RingHomomorphism_im_gens.base_map
Failed example:
    phi.base_map()
Expected:
    Ring endomorphism of Number Field in i with defining polynomial x^2 + 1
      Defn: i |--> -i
Got:
    Composite map:
      From: Number Field in i with defining polynomial x^2 + 1
      To:   Univariate Polynomial Ring in y over Number Field in i with defining polynomial x^2 + 1
      Defn:   Ring endomorphism of Number Field in i with defining polynomial x^2 + 1
              Defn: i |--> -i
            then
              Polynomial base injection morphism:
              From: Number Field in i with defining polynomial x^2 + 1
              To:   Univariate Polynomial Ring in y over Number Field in i with defining polynomial x^2 + 1
**********************************************************************
File "src/sage/structure/parent_gens.pyx", line 311, in sage.structure.parent_gens.ParentWithGens.gens.hom
Failed example:
    f = R.hom([x+1], base_map=lambda t: t+1); f
Exception raised:
    Traceback (most recent call last):
      File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.structure.parent_gens.ParentWithGens.gens.hom[22]>", line 1, in <module>
        f = R.hom([x+Integer(1)], base_map=lambda t: t+Integer(1)); f
      File "sage/structure/parent_gens.pyx", line 328, in sage.structure.parent_gens.ParentWithGens.hom (build/cythonized/sage/structure/parent_gens.c:3690)
        return parent.Parent.hom(self, im_gens, codomain, base_map=base_map, category=category, check=check)
      File "sage/structure/parent.pyx", line 1360, in sage.structure.parent.Parent.hom (build/cythonized/sage/structure/parent.c:11708)
        return self.Hom(codomain, **Hom_kwds)(im_gens, **kwds)
      File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage/rings/homset.py", line 208, in __call__
        return morphism.RingHomomorphism_im_gens(self, im_gens, base_map=base_map, check=check)
      File "sage/rings/morphism.pyx", line 1134, in sage.rings.morphism.RingHomomorphism_im_gens.__init__ (build/cythonized/sage/rings/morphism.c:8239)
        if base_map.codomain() is not self.codomain():
    AttributeError: 'function' object has no attribute 'codomain'
**********************************************************************
File "src/sage/structure/parent_gens.pyx", line 315, in sage.structure.parent_gens.ParentWithGens.gens.hom
Failed example:
    f.category_for()
Expected:
    Join of Category of euclidean domains and Category of commutative algebras over (finite enumerated fields and subquotients of monoids and quotients of semigroups) and Category of infinite sets
Got:
    Category of enumerated euclidean domains
**********************************************************************
File "src/sage/structure/parent_gens.pyx", line 317, in sage.structure.parent_gens.ParentWithGens.gens.hom
Failed example:
    f(-1)
Expected:
    0
Got:
    4
**********************************************************************

And the flag is red for non_ascii and pyflakes but I don't understand what's wrong.

[caruso]

I've just updated the doctest.

If you agree with my changes, please give a positive review.

---

New commits:

​a62a47c	Merge branch 'u/roed/26105_base_hom' of git://trac.sagemath.org/sage into base_hom
​5324a83	Merge branch 'develop' into base_hom
​2f526f8	Merge branch 'u/roed/26105_base_hom' of git://trac.sagemath.org/sage into base_hom
​3705163	Merge branch 'u/roed/26105_base_hom' of git://trac.sagemath.org/sage into base_hom
​243e72a	Merge branch 'develop' into base_hom
​626f4ca	fix doctest

[roed]

Looks good to me.