Opened 3 years ago

Closed 2 years ago

#26105 closed enhancement (fixed)

Support base_morphism for hom(im_gens)

Reported by: saraedum Owned by:
Priority: major Milestone: sage-9.0
Component: coercion Keywords: padicBordeaux
Cc: roed, caruso, swewers 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 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.

Change History (43)

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

comment:2 Changed 3 years ago by saraedum

  • Description modified (diff)

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

comment:4 follow-ups: Changed 3 years ago by 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.

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

comment:6 in reply to: ↑ 4 Changed 3 years ago by 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.

comment:7 in reply to: ↑ 4 ; follow-up: Changed 3 years ago by 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.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 3 years ago by 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?

comment:9 in reply to: ↑ 8 Changed 3 years ago by 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.

comment:10 follow-up: Changed 3 years ago by 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)?

Last edited 3 years ago by saraedum (previous) (diff)

comment:11 in reply to: ↑ 10 Changed 3 years ago by 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.

comment:12 Changed 3 years ago by saraedum

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

comment:13 Changed 3 years ago by 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 follow-up: Changed 3 years ago by 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]))

comment:15 Changed 2 years ago by saraedum

  • Keywords padicBordeaux added

comment:16 Changed 2 years ago by roed

  • Branch set to u/roed/26105_base_hom

comment:17 Changed 2 years ago by roed

  • Commit set to 1f78dd4c51b965187c3004eb5b743b41efe4e347
  • Status changed from new to needs_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 2 years ago by saraedum

  • Authors changed from Julian Rüth to Julian Rüth, David Roe
  • Reviewers set to David Roe, Julian Rüth

comment:19 Changed 2 years ago by git

  • Commit changed from 1f78dd4c51b965187c3004eb5b743b41efe4e347 to 84704ba5472818a3efe97f6ef0784f4e383c512f

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 2 years ago by 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 2 years ago by caruso

  • Authors changed from Julian Rüth, David Roe to Julian Rüth, David Roe, Xavier Caruso
  • Status changed from needs_review to needs_work

comment:22 Changed 2 years ago by caruso

  • Authors changed from Julian Rüth, David Roe, Xavier Caruso to Julian Rüth, David Roe
  • Reviewers changed from David Roe, Julian Rüth to David Roe, Julian Rüth, Xavier Caruso

comment:23 Changed 2 years ago by 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 2 years ago by git

  • Commit changed from 84704ba5472818a3efe97f6ef0784f4e383c512f to ac1c05a2120c44a8bc4310dc1237559bda618b5f

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

c4f2a3fFix _is_valid_homomorphism_
ac1c05aDocumenting category and base_map options

comment:25 Changed 2 years ago by git

  • Commit changed from ac1c05a2120c44a8bc4310dc1237559bda618b5f to 1738aa9010a4362b26bd76a015747dcee4731ad8

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

1738aa9Fix some doctests, remove category keywords from doctests

comment:26 Changed 2 years ago by roed

  • Status changed from needs_work to needs_review

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

comment:27 Changed 2 years ago by git

  • Commit changed from 1738aa9010a4362b26bd76a015747dcee4731ad8 to d0e095381e58f26786a979298291b3ced85500a5

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

d0e0953Add base_map to finite_field homsets

comment:28 Changed 2 years ago by git

  • Commit changed from d0e095381e58f26786a979298291b3ced85500a5 to 16feb8dfa1caf7aebd9e31f75397ebc6d084643e

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

16feb8dFix some errors with positional check arguments

comment:29 Changed 2 years ago by git

  • Commit changed from 16feb8dfa1caf7aebd9e31f75397ebc6d084643e to aa84741e43d429d05348ec8d1a2629e2f09a41b8

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

c48e142Fix pyflakes
aa84741Fix some doctests

comment:30 Changed 2 years ago by 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 2 years ago by caruso (previous) (diff)

comment:31 Changed 2 years ago by caruso

  • Status changed from needs_review to needs_work

comment:32 Changed 2 years ago by git

  • Commit changed from aa84741e43d429d05348ec8d1a2629e2f09a41b8 to 3d7377618234d5fd125b4803d30c72d909363e7a

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

3d73776Fixing Lie algebra morphisms

comment:33 Changed 2 years ago by git

  • Commit changed from 3d7377618234d5fd125b4803d30c72d909363e7a to 72b677c28fdd9db2054a8b0ffc5a1b3aeaadd829

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 2 years ago by roed

  • Status changed from needs_work to needs_review

comment:35 Changed 2 years ago by git

  • Commit changed from 72b677c28fdd9db2054a8b0ffc5a1b3aeaadd829 to d780c6fdf4a793e833d091bb1de98198f3d89ae2

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 2 years ago by git

  • Commit changed from d780c6fdf4a793e833d091bb1de98198f3d89ae2 to bfcbebefa46b2e5f4845a73b848c3771fad1fcd5

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

bfcbebeFix bug in composition

comment:37 Changed 2 years ago by caruso

LGTM (see also discussion on Zulip).

Positive review when patchbot is happy.

comment:38 Changed 2 years ago by 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 2 years ago by caruso

  • Branch changed from u/roed/26105_base_hom to u/caruso/26105_base_hom

comment:40 Changed 2 years ago by caruso

  • Commit changed from bfcbebefa46b2e5f4845a73b848c3771fad1fcd5 to 626f4ca244b2f87ce0838cba554244cc7ac037f0

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 2 years ago by roed

  • Status changed from needs_review to positive_review

Looks good to me.

comment:42 Changed 2 years ago by chapoton

  • Milestone changed from sage-8.4 to sage-9.0

comment:43 Changed 2 years ago by vbraun

  • Branch changed from u/caruso/26105_base_hom to 626f4ca244b2f87ce0838cba554244cc7ac037f0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.