Opened 4 years ago

Closed 3 years ago

#26105 closed enhancement (fixed)

Support base_morphism for hom(im_gens)

Reported by: Julian Rüth Owned by:
Priority: major Milestone: sage-9.0
Component: coercion Keywords: padicBordeaux
Cc: David Roe, Xavier Caruso, Stefan Wewers Merged in:
Authors: Julian Rüth, David Roe Reviewers: David Roe, Julian Rüth, Xavier Caruso
Report Upstream: N/A Work issues:
Branch: 626f4ca (Commits, GitHub, GitLab) Commit: 626f4ca244b2f87ce0838cba554244cc7ac037f0
Dependencies: Stopgaps:

Status badges

Description (last modified by Julian Rüth)

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.

Change History (43)

comment:1 Changed 4 years ago by Julian Rüth

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

comment:2 Changed 4 years ago by Julian Rüth

Description: modified (diff)

comment:3 Changed 4 years ago by Jeroen Demeyer

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...

comment:4 Changed 4 years ago by Julian Rüth

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.

comment:5 Changed 4 years ago by Julian Rüth

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.

comment:6 in reply to:  4 Changed 4 years ago by Jeroen Demeyer

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.

comment:7 in reply to:  4 ; Changed 4 years ago by Jeroen Demeyer

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.

comment:8 in reply to:  7 ; Changed 4 years ago by Julian Rüth

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?

comment:9 in reply to:  8 Changed 4 years ago by Jeroen Demeyer

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.

comment:10 Changed 4 years ago by Julian Rüth

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)?

Last edited 4 years ago by Julian Rüth (previous) (diff)

comment:11 in reply to:  10 Changed 4 years ago by Jeroen Demeyer

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.

comment:12 Changed 4 years ago by Julian Rüth

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

comment:13 Changed 4 years ago by Xavier 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?

comment:14 Changed 4 years ago by Julian Rüth

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]))

comment:15 Changed 3 years ago by Julian Rüth

Keywords: padicBordeaux added

comment:16 Changed 3 years ago by David Roe

Branch: u/roed/26105_base_hom

comment:17 Changed 3 years ago by David Roe

Commit: 1f78dd4c51b965187c3004eb5b743b41efe4e347
Status: newneeds_review

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:

d4a35acAdd base_map to homomorphisms defined by images of generators
1f78dd4Fix some doctests

comment:18 Changed 3 years ago by Julian Rüth

Authors: Julian RüthJulian Rüth, David Roe
Reviewers: David Roe, Julian Rüth

comment:19 Changed 3 years ago by git

Commit: 1f78dd4c51b965187c3004eb5b743b41efe4e34784704ba5472818a3efe97f6ef0784f4e383c512f

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

84704baFix doctests and py3, incorporate small reviewer suggestion

comment:20 in reply to:  14 Changed 3 years ago by Xavier 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

comment:21 Changed 3 years ago by Xavier Caruso

Authors: Julian Rüth, David RoeJulian Rüth, David Roe, Xavier Caruso
Status: needs_reviewneeds_work

comment:22 Changed 3 years ago by Xavier Caruso

Authors: Julian Rüth, David Roe, Xavier CarusoJulian Rüth, David Roe
Reviewers: David Roe, Julian RüthDavid Roe, Julian Rüth, Xavier Caruso

comment:23 Changed 3 years ago by Xavier 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

comment:24 Changed 3 years ago by git

Commit: 84704ba5472818a3efe97f6ef0784f4e383c512fac1c05a2120c44a8bc4310dc1237559bda618b5f

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

c4f2a3fFix _is_valid_homomorphism_
ac1c05aDocumenting category and base_map options

comment:25 Changed 3 years ago by git

Commit: ac1c05a2120c44a8bc4310dc1237559bda618b5f1738aa9010a4362b26bd76a015747dcee4731ad8

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

1738aa9Fix some doctests, remove category keywords from doctests

comment:26 Changed 3 years ago by David Roe

Status: needs_workneeds_review

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

comment:27 Changed 3 years ago by git

Commit: 1738aa9010a4362b26bd76a015747dcee4731ad8d0e095381e58f26786a979298291b3ced85500a5

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

d0e0953Add base_map to finite_field homsets

comment:28 Changed 3 years ago by git

Commit: d0e095381e58f26786a979298291b3ced85500a516feb8dfa1caf7aebd9e31f75397ebc6d084643e

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

16feb8dFix some errors with positional check arguments

comment:29 Changed 3 years ago by git

Commit: 16feb8dfa1caf7aebd9e31f75397ebc6d084643eaa84741e43d429d05348ec8d1a2629e2f09a41b8

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

c48e142Fix pyflakes
aa84741Fix some doctests

comment:30 Changed 3 years ago by Xavier 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).

Last edited 3 years ago by Xavier Caruso (previous) (diff)

comment:31 Changed 3 years ago by Xavier Caruso

Status: needs_reviewneeds_work

comment:32 Changed 3 years ago by git

Commit: aa84741e43d429d05348ec8d1a2629e2f09a41b83d7377618234d5fd125b4803d30c72d909363e7a

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

3d73776Fixing Lie algebra morphisms

comment:33 Changed 3 years ago by git

Commit: 3d7377618234d5fd125b4803d30c72d909363e7a72b677c28fdd9db2054a8b0ffc5a1b3aeaadd829

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

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

comment:34 Changed 3 years ago by David Roe

Status: needs_workneeds_review

comment:35 Changed 3 years ago by git

Commit: 72b677c28fdd9db2054a8b0ffc5a1b3aeaadd829d780c6fdf4a793e833d091bb1de98198f3d89ae2

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

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

comment:36 Changed 3 years ago by git

Commit: d780c6fdf4a793e833d091bb1de98198f3d89ae2bfcbebefa46b2e5f4845a73b848c3771fad1fcd5

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

bfcbebeFix bug in composition

comment:37 Changed 3 years ago by Xavier Caruso

LGTM (see also discussion on Zulip).

Positive review when patchbot is happy.

comment:38 Changed 3 years ago by Xavier 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.

comment:39 Changed 3 years ago by Xavier Caruso

Branch: u/roed/26105_base_homu/caruso/26105_base_hom

comment:40 Changed 3 years ago by Xavier Caruso

Commit: bfcbebefa46b2e5f4845a73b848c3771fad1fcd5626f4ca244b2f87ce0838cba554244cc7ac037f0

I've just updated the doctest.

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


New commits:

a62a47cMerge branch 'u/roed/26105_base_hom' of git://trac.sagemath.org/sage into base_hom
5324a83Merge branch 'develop' into base_hom
2f526f8Merge branch 'u/roed/26105_base_hom' of git://trac.sagemath.org/sage into base_hom
3705163Merge branch 'u/roed/26105_base_hom' of git://trac.sagemath.org/sage into base_hom
243e72aMerge branch 'develop' into base_hom
626f4cafix doctest

comment:41 Changed 3 years ago by David Roe

Status: needs_reviewpositive_review

Looks good to me.

comment:42 Changed 3 years ago by Frédéric Chapoton

Milestone: sage-8.4sage-9.0

comment:43 Changed 3 years ago by Volker Braun

Branch: u/caruso/26105_base_hom626f4ca244b2f87ce0838cba554244cc7ac037f0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.