581d-2010-11-19-morphisms

552 days ago by wstein

Math 581d

Morphisms

A morphism is a structure preserving map between two parents.  Sage supports the creation of morphisms.

In Sage, the typical way you specify a morphism from a "Parent with Generators" (which is most parents), is to give the images of the generators.  However, one can define morphisms using whatever method you want, and apply them however you want ("im_gens" is just what the data is called).
 
       

Recall our example from last time, in which we created a new parent data type GoldenIntegers.    Suppose we would like the ring of golden integers to be viewed naturally as embedded in some other specific ring, from the point of view of the coercion model.  Without modifying Sage itself, the only way to do this is to learn about morphisms and:

  1. Use the embedding option to _populate_coercion_lists, as explained here, or
  2. Register a new coercion, as explained here, or
  3. Define a convert method on GoldenRingElement. 

We will explain all of these approaches below.
 
       

Here's our code from last time.   Note that I implemented _mul_ this time.
class GoldenIntegers(Ring): def __init__(self): Ring.__init__(self, base=ZZ) def _repr_(self): return "The Golden Ring" def gen(self, i=0): if i == 0: return GoldenElement(self, 0, 1) else: raise IndexError def ngens(self): return 1 def _element_constructor_(self, x): if isinstance(x, GoldenElement): return x return GoldenElement(self, ZZ(x), ZZ(0)) def _coerce_map_from_(self, S): print "_coerce_map_from_(%s, %s)"%(self, S) if S is ZZ: return True if S == Integers(13): return True class GoldenElement(RingElement): def __init__(self, parent, a, b): RingElement.__init__(self, parent) # sets self._parent to parent self._a = a self._b = b def _repr_(self): return "%s + %s*(1+sqrt(5))/2"%(self._a, self._b) def _add_(left, right): return GoldenElement(left.parent(), left._a+right._a, left._b+right._b) def _sub_(left, right): return GoldenElement(left.parent(), left._a-right._a, left._b-right._b) def _mul_(left, right): (a,b,c,d) = (left._a,left._b,right._a,right._b) return GoldenElement(left.parent(), a*c + b*d, b*c + a*d + b*d) 
       
R = GoldenIntegers(); R 
        
The Golden Ring
The Golden Ring

Registering a coercion.

Let's try the second method, of registering a new coercion.  First we create the homset of homomorphisms from R to RDF (=real double precision field).  In Sage, homsets are normal parent objects, just like any other parents.
H = Hom(R, RDF); H 
        
Set of Homomorphisms from The Golden Ring to Real Double Field
Set of Homomorphisms from The Golden Ring to Real Double Field
gamma_in_RDF = RDF( (1+sqrt(5))/2 ); gamma_in_RDF 
        
1.61803398875
1.61803398875

A homomorphism is simply specified by giving the image of the generators.
phi = H([gamma_in_RDF]); phi 
        
Traceback (click to the left of this block for traceback)
...
TypeError: images do not define a valid homomorphism
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_69.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cGhpID0gSChbZ2FtbWFfaW5fUkRGXSk7IHBoaQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmpl_R2YK/___code___.py", line 2, in <module>
    exec compile(u'phi = H([gamma_in_RDF]); phi
  File "", line 1, in <module>
    
  File "/Users/wstein/sage/install/sage-4.6/local/lib/python2.6/site-packages/sage/rings/homset.py", line 81, in __call__
    raise TypeError, "images do not define a valid homomorphism"
TypeError: images do not define a valid homomorphism

Checking with %debug on the console, we find that this is because:

ipdb> morphism.RingHomomorphism_im_gens(self, im_gens, check=check)
*** NotImplementedError: Verification of correctness of homomorphisms from The Golden Ring not yet implemented.

 

ipdb> morphism.RingHomomorphism_im_gens(self, im_gens, check=check)

*** NotImplementedError: Verification of correctness of homomorphisms from The Golden Ring not yet implemented.

 

 

This is a message that is produced in parent.pyx because we didn't define the method _is_valid_homomorphism_ yet.  Let's do it:
R._is_valid_homomorphism_? 
       

File: /Users/wstein/sage/install/sage-4.6/devel/sage/sage/structure/parent.pyx

Type: <type ‘builtin_function_or_method’>

Definition: R._is_valid_homomorphism_(codomain, im_gens)

Docstring:

Return True if im_gens defines a valid homomorphism from self to codomain; otherwise return False.

If determining whether or not a homomorphism is valid has not been implemented for this ring, then a NotImplementedError exception is raised.

File: /Users/wstein/sage/install/sage-4.6/devel/sage/sage/structure/parent.pyx

Type: <type ‘builtin_function_or_method’>

Definition: R._is_valid_homomorphism_(codomain, im_gens)

Docstring:

Return True if im_gens defines a valid homomorphism from self to codomain; otherwise return False.

If determining whether or not a homomorphism is valid has not been implemented for this ring, then a NotImplementedError exception is raised.
class GoldenIntegers(Ring): def __init__(self): Ring.__init__(self, base=ZZ) def _is_valid_homomorphism_(self, codomain, im_gens): if len(im_gens) != 1: return False if im_gens[0]**2 - im_gens[0] - 1 == 0: return True return False def _repr_(self): return "The Golden Ring" def gen(self, i=0): if i == 0: return GoldenElement(self, 0, 1) else: raise IndexError def ngens(self): return 1 def _element_constructor_(self, x): if isinstance(x, GoldenElement): return x return GoldenElement(self, ZZ(x), ZZ(0)) def _coerce_map_from_(self, S): print "_coerce_map_from_(%s, %s)"%(self, S) if S is ZZ: return True if S == Integers(13): return True 
       

It works!
R = GoldenIntegers(); H = Hom(R, RDF); phi = H([ gamma_in_RDF ]); phi 
        
Ring morphism:
  From: The Golden Ring
  To:   Real Double Field
  Defn: 0 + 1*(1+sqrt(5))/2 |--> 1.61803398875
Ring morphism:
  From: The Golden Ring
  To:   Real Double Field
  Defn: 0 + 1*(1+sqrt(5))/2 |--> 1.61803398875

But we can't use it yet.
gamma = R.0; phi(gamma) 
        
Traceback (click to the left of this block for traceback)
...
NotImplementedError
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_73.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("Z2FtbWEgPSBSLjA7IHBoaShnYW1tYSk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmpbO4umX/___code___.py", line 2, in <module>
    exec compile(u'gamma = R.gen(0); phi(gamma)
  File "", line 1, in <module>
    
  File "map.pyx", line 440, in sage.categories.map.Map.__call__ (sage/categories/map.c:3365)
  File "morphism.pyx", line 1087, in sage.rings.morphism.RingHomomorphism_im_gens._call_ (sage/rings/morphism.c:5636)
  File "element.pyx", line 416, in sage.structure.element.Element._im_gens_ (sage/structure/element.c:3216)
NotImplementedError

Again, looking at the above traceback and possibly consulting the source code of Sage, we find that there is another method that we have to define: _im_gens_
gamma._im_gens_? 
       

File: /Users/wstein/sage/install/sage-4.6/devel/sage/sage/structure/element.pyx

Type: <type 'builtin_function_or_method'>

Definition: gamma._im_gens_(codomain, im_gens)

Docstring:



        Return the image of self in codomain under the map that sends
        the images of the generators of the parent of self to the
        tuple of elements of im_gens.

File: /Users/wstein/sage/install/sage-4.6/devel/sage/sage/structure/element.pyx

Type: <type 'builtin_function_or_method'>

Definition: gamma._im_gens_(codomain, im_gens)

Docstring:



        Return the image of self in codomain under the map that sends
        the images of the generators of the parent of self to the
        tuple of elements of im_gens.

No problem:
class GoldenElement(RingElement): def __init__(self, parent, a, b): RingElement.__init__(self, parent) # sets self._parent to parent self._a = a self._b = b def _im_gens_(self, codomain, im_gens): return codomain(self._a) + codomain(self._b)*im_gens[0] def _repr_(self): return "%s + %s*(1+sqrt(5))/2"%(self._a, self._b) def _add_(left, right): return GoldenElement(left.parent(), left._a+right._a, left._b+right._b) def _sub_(left, right): return GoldenElement(left.parent(), left._a-right._a, left._b-right._b) def _mul_(left, right): (a,b,c,d) = (left._a,left._b,right._a,right._b) return GoldenElement(left.parent(), a*c + b*d, b*c + a*d + b*d) 
       
R = GoldenIntegers(); H = Hom(R, RDF); phi = H([ gamma_in_RDF ]) gamma = R.0; phi(gamma) 
        
1.61803398875
1.61803398875
phi(3 + gamma) 
        
_coerce_map_from_(The Golden Ring, Integer Ring)
4.61803398875
_coerce_map_from_(The Golden Ring, Integer Ring)
4.61803398875
2*gamma 
        
0 + 2*(1+sqrt(5))/2
0 + 2*(1+sqrt(5))/2
phi(7 + 2*gamma) 
        
10.2360679775
10.2360679775

So finally, we have a working morphism.  Let's use it to register a new coercion!
gamma + RDF(2.3) 
        
_coerce_map_from_(The Golden Ring, Real Double Field)
_coerce_map_from_(The Golden Ring, Rational Field)
Traceback (click to the left of this block for traceback)
...
TypeError: unsupported operand parent(s) for '+': 'The Golden Ring' and
'Real Double Field'
_coerce_map_from_(The Golden Ring, Real Double Field)
_coerce_map_from_(The Golden Ring, Rational Field)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_80.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("Z2FtbWEgKyBSREYoMi4zKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmp8HFIBX/___code___.py", line 3, in <module>
    exec compile(u'gamma + RDF(_sage_const_2p3 )
  File "", line 1, in <module>
    
  File "element.pyx", line 1274, in sage.structure.element.RingElement.__add__ (sage/structure/element.c:10853)
  File "coerce.pyx", line 765, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6995)
TypeError: unsupported operand parent(s) for '+': 'The Golden Ring' and 'Real Double Field'
phi.register_as_coercion() 
        
Traceback (click to the left of this block for traceback)
...
AssertionError: coercion from The Golden Ring to Real Double Field
already registered or discovered
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_81.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cGhpLnJlZ2lzdGVyX2FzX2NvZXJjaW9uKCk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmpu2Q9Ds/___code___.py", line 2, in <module>
    exec compile(u'phi.register_as_coercion()
  File "", line 1, in <module>
    
  File "morphism.pyx", line 116, in sage.categories.morphism.Morphism.register_as_coercion (sage/categories/morphism.c:2387)
  File "parent.pyx", line 1368, in sage.structure.parent.Parent.register_coercion (sage/structure/parent.c:9695)
  File "parent.pyx", line 1408, in sage.structure.parent.Parent.register_coercion (sage/structure/parent.c:9635)
AssertionError: coercion from The Golden Ring to Real Double Field already registered or discovered

What went wrong?  The problem is that Sage already started automatically deciding on coercions, and once that happpens, for efficiency and consistency reasons you are not allowed to register further coercions.  The solution is to register the coercion map right when you make R.
R = GoldenIntegers(); H = Hom(R, RDF); phi = H([ gamma_in_RDF ]) phi.register_as_coercion() 
       

Now, let's try it out:
gamma = R.0 gamma + RDF(2.5) 
        
_coerce_map_from_(The Golden Ring, Real Double Field)
4.11803398875
_coerce_map_from_(The Golden Ring, Real Double Field)
4.11803398875

Nice!  Notice that the coercion ended up going into the real double field.
 
       

Summary:

In order to create a working morphism from instances of our GoldenRing class to some other ring S, we did the following:

  1. Defined the method def _is_valid_homomorphism_(self, codomain, im_gens)  in the GoldenRing class, which verifies that a morphism is valid.
  2. Defined the method def _im_gens_(self, codomain, im_gens) in the GoldenElement class, which computes where an element goes under a valid morphism.
  3. Learned about H = Hom(A,B), which creates the set of homomorphisms from A to B.
  4. Learned that we make elements of H like so:   H(list of images of generators of A in B)

We also learned about register_as_coercion, which must be called immediately after you make your parent.  Using that we can inform Sage that it should add some morphisms to the coercion model.
 
       

Finally, there is also the embedding= option.  We abuse it below.  (I say "abuse", since in fact the golden ring doesn't really embed into RDF, since RDF is a finite set, due to rounding.)
class GoldenIntegers(Ring): def __init__(self): Ring.__init__(self, base=ZZ) phi = self.hom([RDF( (1+sqrt(5))/2 )]) self._populate_coercion_lists_(embedding=phi) def _is_valid_homomorphism_(self, codomain, im_gens): if len(im_gens) != 1: return False if im_gens[0]**2 - im_gens[0] - 1 == 0: return True return False def _repr_(self): return "The Golden Ring" def gen(self, i=0): if i == 0: return GoldenElement(self, 0, 1) else: raise IndexError def ngens(self): return 1 def _element_constructor_(self, x): if isinstance(x, GoldenElement): return x return GoldenElement(self, ZZ(x), ZZ(0)) def _coerce_map_from_(self, S): print "_coerce_map_from_(%s, %s)"%(self, S) if S is ZZ: return True if S == Integers(13): return True 
       
R = GoldenIntegers(); gamma = R.0 gamma + RDF(2.3) 
        
_coerce_map_from_(The Golden Ring, Real Double Field)
3.91803398875
_coerce_map_from_(The Golden Ring, Real Double Field)
3.91803398875

Since RDF embeds into the symbolic ring, the following automatically works.  
gamma + sqrt(2) 
        
_coerce_map_from_(The Golden Ring, Symbolic Ring)
sqrt(2) + 1.61803398875
_coerce_map_from_(The Golden Ring, Symbolic Ring)
sqrt(2) + 1.61803398875

However, it seems a bit weird to turn (1+sqrt(5))/2 into the number 1.61803398875, just to put it somewhere where we could represent (1+sqrt(5))/2 exactly!  Let's try embedding into SR, instead.
class GoldenIntegers(Ring): def __init__(self): Ring.__init__(self, base=ZZ) phi = self.hom([( 1+sqrt(5))/2 ]) self._populate_coercion_lists_(embedding=phi) def _is_valid_homomorphism_(self, codomain, im_gens): if len(im_gens) != 1: return False if im_gens[0]**2 - im_gens[0] - 1 == 0: return True return False def _repr_(self): return "The Golden Ring" def gen(self, i=0): if i == 0: return GoldenElement(self, 0, 1) else: raise IndexError def ngens(self): return 1 def _element_constructor_(self, x): if isinstance(x, GoldenElement): return x return GoldenElement(self, ZZ(x), ZZ(0)) def _coerce_map_from_(self, S): print "_coerce_map_from_(%s, %s)"%(self, S) if S is ZZ: return True if S == Integers(13): return True 
       
R = GoldenIntegers(); gamma = R.0 gamma + sqrt(2) 
        
_coerce_map_from_(The Golden Ring, Symbolic Ring)
sqrt(2) + 1/2*sqrt(5) + 1/2
_coerce_map_from_(The Golden Ring, Symbolic Ring)
sqrt(2) + 1/2*sqrt(5) + 1/2

But now the following won't work, because there isn't a canonical map in any direction.
gamma + RDF(2.3) 
        
_coerce_map_from_(The Golden Ring, Real Double Field)
_coerce_map_from_(The Golden Ring, Symbolic Ring)
_coerce_map_from_(The Golden Ring, The Golden Ring)
_coerce_map_from_(The Golden Ring, Integer Ring)
_coerce_map_from_(The Golden Ring, Rational Field)
Traceback (click to the left of this block for traceback)
...
TypeError: unsupported operand parent(s) for '+': 'The Golden Ring' and
'Real Double Field'
_coerce_map_from_(The Golden Ring, Real Double Field)
_coerce_map_from_(The Golden Ring, Symbolic Ring)
_coerce_map_from_(The Golden Ring, The Golden Ring)
_coerce_map_from_(The Golden Ring, Integer Ring)
_coerce_map_from_(The Golden Ring, Rational Field)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_89.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("Z2FtbWEgKyBSREYoMi4zKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmpuvV1Kl/___code___.py", line 3, in <module>
    exec compile(u'gamma + RDF(_sage_const_2p3 )
  File "", line 1, in <module>
    
  File "element.pyx", line 1274, in sage.structure.element.RingElement.__add__ (sage/structure/element.c:10853)
  File "coerce.pyx", line 765, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6995)
TypeError: unsupported operand parent(s) for '+': 'The Golden Ring' and 'Real Double Field'

There is a canonical coercion from the golden ring to the symbolic ring, and one from RDF to the symbolic ring, but the coercion system doesn't know how to figure out that this is the best place to map things to.  (And I don't know how to tell it to do so...)
 
       

Look at the _populate_coercion_lists_ method in more detail:
R._populate_coercion_lists_?? 
       
 
       

Let's use a Convert Methods to make it so golden elements automatically coerce to arbitrary precision reals

There is something called the _convert_method_name, which allows you to add a method to your elements, to make it so certain rings automatically can coerce elements in.  For example, below we figure out what the method name is for arbitrary precision floating point numbers, then define it for our GoldenElement class.  Now there is automatically a coercion map to arbitrary precision reals.  This is similar to the builtin Python methods like __float__.
RR._convert_method_name 
        
'_mpfr_'
'_mpfr_'
class GoldenElement(RingElement): def __init__(self, parent, a, b): RingElement.__init__(self, parent) # sets self._parent to parent self._a = a self._b = b def _mpfr_(self, F): return self._a + self._b * (1+F(5).sqrt())/2 def __float__(self): return float(self._a) + float(self._b) + float( (1+sqrt(5))/2 ) def _im_gens_(self, codomain, im_gens): return codomain(self._a) + codomain(self._b)*im_gens[0] def _repr_(self): return "%s + %s*(1+sqrt(5))/2"%(self._a, self._b) def _add_(left, right): return GoldenElement(left.parent(), left._a+right._a, left._b+right._b) def _sub_(left, right): return GoldenElement(left.parent(), left._a-right._a, left._b-right._b) def _mul_(left, right): (a,b,c,d) = (left._a,left._b,right._a,right._b) return GoldenElement(left.parent(), a*c + b*d, b*c + a*d + b*d) 
       
R = GoldenIntegers() x = 2*R.0 + 5 RealField(200)(x) 
        
_coerce_map_from_(The Golden Ring, Integer Ring)
_coerce_map_from_(The Golden Ring, Real Field with 200 bits of
precision)
8.2360679774997896964091736687312762354406183596115257242709
_coerce_map_from_(The Golden Ring, Integer Ring)
_coerce_map_from_(The Golden Ring, Real Field with 200 bits of precision)
8.2360679774997896964091736687312762354406183596115257242709
float(x) 
        
8.6180339887498949
8.6180339887498949
RealField(300)(x) 
        
_coerce_map_from_(The Golden Ring, Real Field with 300 bits of
precision)
8.2360679774997896964091736687312762354406183596115257242708972454105209\
2563780489941441441
_coerce_map_from_(The Golden Ring, Real Field with 300 bits of precision)
8.23606797749978969640917366873127623544061835961152572427089724541052092563780489941441441
RR(x) 
        
_coerce_map_from_(The Golden Ring, Real Field with 53 bits of precision)
8.23606797749979
_coerce_map_from_(The Golden Ring, Real Field with 53 bits of precision)
8.23606797749979