# source:sage/rings/morphism.py@4005:d0435ae9cb51

Revision 4005:d0435ae9cb51, 17.4 KB checked in by 'Martin Albrecht <malb@…, 6 years ago (diff)

added a bunch of loads(dumps(s)) == s doctests, most fail, superficially fixed failure for crypto subdirectory

Line
1r"""
2Homomorphisms of rings
3
4We give a large number of examples of ring homomorphisms.
5
6EXAMPLE: Natural inclusion $\Z \hookrightarrow \Q$.
7    sage: H = Hom(ZZ, QQ)
8    sage: phi = H([1])
9    sage: phi(10)
10    10
11    sage: phi(3/1)
12    3
13    sage: phi(2/3)
14    Traceback (most recent call last):
15    ...
16    TypeError: 2/3 must be coercible into Integer Ring
17
18There is no homomorphism in the other direction:
19    sage: H = Hom(QQ, ZZ)
20    sage: H([1])
21    Traceback (most recent call last):
22    ...
23    TypeError: images do not define a valid homomorphism
24
25EXAMPLE: Reduction to finite field.
26    sage: H = Hom(ZZ, GF(9, 'a'))
27    sage: phi = H([1])
28    sage: phi(5)
29    2
30    sage: psi = H([4])
31    sage: psi(5)
32    2
33
34EXAMPLE: Map from single variable polynomial ring.
35    sage: R, x = PolynomialRing(ZZ, 'x').objgen()
36    sage: phi = R.hom([2], GF(5))
37    sage: phi
38    Ring morphism:
39      From: Univariate Polynomial Ring in x over Integer Ring
40      To:   Finite Field of size 5
41      Defn: x |--> 2
42    sage: phi(x + 12)
43    4
44
45EXAMPLE: Identity map on the real numbers.
46    sage: f = RR.hom([RR(1)]); f
47    Ring endomorphism of Real Field with 53 bits of precision
48      Defn: 1.00000000000000 |--> 1.00000000000000
49    sage: f(2.5)
50    2.50000000000000
51    sage: f = RR.hom( [2.0] )
52    Traceback (most recent call last):
53    ...
54    TypeError: images do not define a valid homomorphism
55
56EXAMPLE: Homomorphism from one precision of field to another.
57
58From smaller to bigger doesn't make sense:
59    sage: R200 = RealField(200)
60    sage: f = RR.hom( R200 )
61    Traceback (most recent call last):
62    ...
63    TypeError: Natural coercion morphism from Real Field with 53 bits of precision to Real Field with 200 bits of precision not defined.
64
65From bigger to small does:
66    sage: f = RR.hom( RealField(15) )
67    sage: f(2.5)
68    2.500
69    sage: f(RR.pi())
70    3.142
71
72EXAMPLE: Inclusion map from the reals to the complexes:
73    sage: i = RR.hom([CC(1)]); i
74    Ring morphism:
75      From: Real Field with 53 bits of precision
76      To:   Complex Field with 53 bits of precision
77      Defn: 1.00000000000000 |--> 1.00000000000000
78    sage: i(RR('3.1'))
79    3.10000000000000
80
81EXAMPLE: A map from a multivariate polynomial ring to itself:
82    sage: R.<x,y,z> = PolynomialRing(QQ,3)
83    sage: phi = R.hom([y,z,x^2]); phi
84    Ring endomorphism of Polynomial Ring in x, y, z over Rational Field
85      Defn: x |--> y
86            y |--> z
87            z |--> x^2
88    sage: phi(x+y+z)
89    z + y + x^2
90
91EXAMPLE: An endomorphism of a quotient of a multi-variate polynomial ring:
92    sage: R.<x,y> = PolynomialRing(QQ)
93    sage: S.<a,b> = quo(R, ideal(1 + y^2))
94    sage: phi = S.hom([a^2, -b])
95    sage: phi
96    Ring endomorphism of Quotient of Polynomial Ring in x, y over Rational Field by the ideal (1 + y^2)
97      Defn: a |--> a^2
98            b |--> -1*b
99    sage: phi(b)
100    -1*b
101    sage: phi(a^2 + b^2)
102    -1 + a^4
103
104EXAMPLE: The reduction map from the integers to the integers modulo 8,
105viewed as a quotient ring:
106
107    sage: R = ZZ.quo(8*ZZ)
108    sage: pi = R.cover()
109    sage: pi
110    Ring morphism:
111      From: Integer Ring
112      To:   Ring of integers modulo 8
113      Defn: Natural quotient map
114    sage: pi.domain()
115    Integer Ring
116    sage: pi.codomain()
117    Ring of integers modulo 8
118    sage: pi(10)
119    2
120    sage: pi.lift()
121    Set-theoretic ring morphism:
122      From: Ring of integers modulo 8
123      To:   Integer Ring
124      Defn: Choice of lifting map
125    sage: pi.lift(13)
126    5
127
128
129EXAMPLE: Inclusion of GF(2) into GF(4,'a').
130    sage: k = GF(2)
131    sage: i = k.hom(GF(4, 'a'))
132    sage: i
133    Coercion morphism:
134      From: Finite Field of size 2
135      To:   Finite Field in a of size 2^2
136    sage: i(0)
137    0
138    sage: a = i(1); a.parent()
139    Finite Field in a of size 2^2
140
141We next compose the inclusion with reduction from the integers to GF(2).
142    sage: pi = ZZ.hom(k)
143    sage: pi
144    Coercion morphism:
145      From: Integer Ring
146      To:   Finite Field of size 2
147    sage: f = i * pi
148    sage: f
149    Composite morphism:
150      From: Integer Ring
151      To:   Finite Field in a of size 2^2
152      Defn:   Coercion morphism:
153              From: Integer Ring
154              To:   Finite Field of size 2
155            then
156              Coercion morphism:
157              From: Finite Field of size 2
158              To:   Finite Field in a of size 2^2
159    sage: a = f(5); a
160    1
161    sage: a.parent()
162    Finite Field in a of size 2^2
163
164EXAMPLE: Inclusion from $\Q$ to the 3-adic field.
165    sage: phi = QQ.hom(Qp(3, print_mode = 'series'))
166    sage: phi
167    Coercion morphism:
168      From: Rational Field
169      To:   3-adic Field with capped relative precision 20
170    sage: phi.codomain()
171    3-adic Field with capped relative precision 20
172    sage: phi(394)
173    1 + 2*3 + 3^2 + 2*3^3 + 3^4 + 3^5 + O(3^20)
174
175EXAMPLE: An automorphism of a quotient of a univariate polynomial ring.
176    sage: R.<x> = PolynomialRing(QQ)
177    sage: S.<sqrt2> = R.quo(x^2-2)
178    sage: sqrt2^2
179    2
180    sage: (3+sqrt2)^10
181    993054*sqrt2 + 1404491
182    sage: c = S.hom([-sqrt2])
183    sage: c(1+sqrt2)
184    -sqrt2 + 1
185
186Note that \sage verifies that the morphism is valid:
187    sage: (1 - sqrt2)^2
188    -2*sqrt2 + 3
189    sage: c = S.hom([1-sqrt2])    # this is not valid
190    Traceback (most recent call last):
191    ...
192    TypeError: images do not define a valid homomorphism
193
194EXAMPLE: Endomorphism of power series ring.
195    sage: R.<t> = PowerSeriesRing(QQ); R
196    Power Series Ring in t over Rational Field
197    sage: f = R.hom([t^2]); f
198    Ring endomorphism of Power Series Ring in t over Rational Field
199      Defn: t |--> t^2
200    sage: R.set_default_prec(10)
201    sage: s = 1/(1 + t); s
202    1 - t + t^2 - t^3 + t^4 - t^5 + t^6 - t^7 + t^8 - t^9 + O(t^10)
203    sage: f(s)
204    1 - t^2 + t^4 - t^6 + t^8 - t^10 + t^12 - t^14 + t^16 - t^18 + O(t^20)
205
206EXAMPLE: Frobenious on a power series ring over a finite field.
207    sage: R.<t> = PowerSeriesRing(GF(5))
208    sage: f = R.hom([t^5]); f
209    Ring endomorphism of Power Series Ring in t over Finite Field of size 5
210      Defn: t |--> t^5
211    sage: a = 2 + t + 3*t^2 + 4*t^3 + O(t^4)
212    sage: b = 1 + t + 2*t^2 + t^3 + O(t^5)
213    sage: f(a)
214    2 + t^5 + 3*t^10 + 4*t^15 + O(t^20)
215    sage: f(b)
216    1 + t^5 + 2*t^10 + t^15 + O(t^25)
217    sage: f(a*b)
218    2 + 3*t^5 + 3*t^10 + t^15 + O(t^20)
219    sage: f(a)*f(b)
220    2 + 3*t^5 + 3*t^10 + t^15 + O(t^20)
221
222EXAMPLE: Homomorphism of Laurent series ring.
223    sage: R.<t> = LaurentSeriesRing(QQ)
224    sage: f = R.hom([t^3 + t]); f
225    Ring endomorphism of Laurent Series Ring in t over Rational Field
226      Defn: t |--> t + t^3
227    sage: R.set_default_prec(10)
228    sage: s = 2/t^2 + 1/(1 + t); s
229    2*t^-2 + 1 - t + t^2 - t^3 + t^4 - t^5 + t^6 - t^7 + t^8 - t^9 + O(t^10)
230    sage: f(s)
231    2*t^-2 - 3 - t + 7*t^2 - 2*t^3 - 5*t^4 - 4*t^5 + 16*t^6 - 9*t^7 + O(t^8)
232    sage: f = R.hom([t^3]); f
233    Ring endomorphism of Laurent Series Ring in t over Rational Field
234      Defn: t |--> t^3
235    sage: f(s)
236    2*t^-6 + 1 - t^3 + t^6 - t^9 + t^12 - t^15 + t^18 - t^21 + t^24 - t^27
237    sage: s = 2/t^2 + 1/(1 + t); s
238    2*t^-2 + 1 - t + t^2 - t^3 + t^4 - t^5 + t^6 - t^7 + t^8 - t^9 + O(t^10)
239    sage: f(s)
240    2*t^-6 + 1 - t^3 + t^6 - t^9 + t^12 - t^15 + t^18 - t^21 + t^24 - t^27
241
242Note that the homomorphism must result in a converging Laurent series,
243so the valuation of the image of the generator must be positive:
244    sage: R.hom([1/t])
245    Traceback (most recent call last):
246    ...
247    TypeError: images do not define a valid homomorphism
248    sage: R.hom([1])
249    Traceback (most recent call last):
250    ...
251    TypeError: images do not define a valid homomorphism
252
253
254EXAMPLE: Complex conjugation on cyclotomic fields.
255    sage: K.<zeta7> = CyclotomicField(7)
256    sage: c = K.hom([1/zeta7]); c
257    Ring endomorphism of Cyclotomic Field of order 7 and degree 6
258      Defn: zeta7 |--> -zeta7^5 - zeta7^4 - zeta7^3 - zeta7^2 - zeta7 - 1
259    sage: a = (1+zeta7)^5; a
260    zeta7^5 + 5*zeta7^4 + 10*zeta7^3 + 10*zeta7^2 + 5*zeta7 + 1
261    sage: c(a)
262    5*zeta7^5 + 5*zeta7^4 - 4*zeta7^2 - 5*zeta7 - 4
263    sage: c(zeta7 + 1/zeta7)       # this element is obviously fixed by inversion
264    -zeta7^5 - zeta7^4 - zeta7^3 - zeta7^2 - 1
265    sage: zeta7 + 1/zeta7
266    -zeta7^5 - zeta7^4 - zeta7^3 - zeta7^2 - 1
267
268EXAMPLE: Embedding a number field into the reals.
269    sage: R.<x> = PolynomialRing(QQ)
270    sage: K.<beta> = NumberField(x^3 - 2)
271    sage: alpha = RR(2)^(1/3); alpha
272    1.25992104989487
273    sage: i = K.hom([alpha],check=False); i
274    Ring morphism:
275      From: Number Field in beta with defining polynomial x^3 - 2
276      To:   Real Field with 53 bits of precision
277      Defn: beta |--> 1.25992104989487
278    sage: i(beta)
279    1.25992104989487
280    sage: i(beta^3)
281    2.00000000000000
282    sage: i(beta^2 + 1)
283    2.58740105196820
284
285TESTS:
286    sage: H = Hom(ZZ, QQ)
288    True
289
290    sage: K.<zeta7> = CyclotomicField(7)
291    sage: c = K.hom([1/zeta7])
293    True
294
295    sage: R.<t> = PowerSeriesRing(GF(5))
296    sage: f = R.hom([t^5])
298    True
299
300"""
301
302#*****************************************************************************
303#       Copyright (C) 2006 William Stein <wstein@gmail.com>
304#
306#
308#*****************************************************************************
309
310from sage.categories.all import Morphism, is_Homset, Sets
311import ideal
312
313import homset
314
315def is_RingHomomorphism(phi):
316    return isinstance(phi, RingHomomorphism)
317
318class RingMap(Morphism):
319    """
320    Set-theoretic map between rings.
321    """
322    def __init__(self, parent):
323        Morphism.__init__(self, parent)
324
325    def _repr_type(self):
326        return "Set-theoretic ring"
327
328    def __call__(self, x):
329        if ideal.is_Ideal(x):
330            R = self.codomain()
331            return R.ideal([self(y) for y in x.gens()])
332        return Morphism.__call__(self, x)
333
334
335class RingMap_lift(RingMap):
336    r"""
337    Given rings $R$ and $S$ such that for any $x \in R$ the function
338    \code{x.lift()} is an element that naturally coerces to $S$, this
339    returns the set-theoretic ring map $R \to S$ sending $x$ to
340    \code{x.lift()}.
341
342    EXAMPLES:
343        sage: R, (x,y) = PolynomialRing(QQ, 2, 'xy').objgens()
344        sage: S.<xbar,ybar> = R.quo( (x^2 + y^2, y) )
345        sage: S.lift()
346        Set-theoretic ring morphism:
347          From: Quotient of Polynomial Ring in x, y over Rational Field by the ideal (y, y^2 + x^2)
348          To:   Polynomial Ring in x, y over Rational Field
349          Defn: Choice of lifting map
350    """
351    def __init__(self, R, S):
352        H = R.Hom(S, Sets())
353        RingMap.__init__(self, H)
354        self.__S = S  # for efficiency
355        try:
356            S._coerce_(R(0).lift())
357        except TypeError:
358            raise TypeError, "No natural lift map"
359
360    def _repr_defn(self):
361        return "Choice of lifting map"
362
363    def _call_(self, x):
364        return self.__S._coerce_(x.lift())
365
366class RingHomomorphism(RingMap):
367    """
368    Homomorphism of rings.
369    """
370    def __init__(self, parent):
371        if not homset.is_RingHomset(parent):
372            raise TypeError, "parent must be a ring homset"
373        RingMap.__init__(self, parent)
374
375    def _repr_type(self):
376        return "Ring"
377
378    def _set_lift(self, lift):
379        if not isinstance(lift, RingMap):
380            raise TypeError, "lift must be a RingMap"
381        if lift.domain() != self.codomain():
382            raise TypeError, "lift must have correct domain"
383        if lift.codomain() != self.domain():
384            raise TypeError, "lift must have correct codomain"
385        self.__lift = lift
386
387    def is_injective(self):
388        ## TODO -- actually implement this in some generality (!)
389        raise NotImplementedError
390
391    def is_zero(self):
392        r"""
393        Return True if this is the zero map and False otherwise.
394
395        A *ring* homomorphism is considered to be 0 if and only if
396        it sends the 1 element of the domain to the 0 element of the
397        codomain.
398
399        EXAMPLES:
400        First an example of a map that is obviously nonzero.
401            sage: h = Hom(ZZ, QQ)
402            sage: f = h.natural_map()
403            sage: f.is_zero()
404            False
405
406        Next we make the zero ring as $\ZZ/1\ZZ$.
407            sage: R = Integers(1)
408            sage: R
409            Ring of integers modulo 1
410            sage: h = Hom(ZZ, R)
411            sage: f = h.natural_map()
412            sage: f.is_zero()
413            True
414
415        Finally we check an example in characteristic 2.
416            sage: h = Hom(ZZ, GF(2))
417            sage: f = h.natural_map()
418            sage: f.is_zero()
419            False
420        """
421        return self(self.domain()(1)) == self.codomain()(0)
422
423    def inverse_image(self, I):
424        """
425        Return the inverse image of the ideal $I$ under this ring
426        homomorphism.
427        """
428        raise NotImplementedError
429
430    def lift(self, x=None):
431        """
432        Return a lifting homomorphism associated to this homomorphism,
433        if it has been defined.
434
435        If x is not None, return the value of the lift morphism on x.
436        """
437        if not (x is None):
438            return self.lift()(x)
439        try:
440            return self.__lift
441        except AttributeError:
442            raise ValueError, "No lift map defined."
443
444
445from sage.categories.morphism import FormalCoercionMorphism
446class RingHomomorphism_coercion(FormalCoercionMorphism, RingHomomorphism):
447    pass
448
449import sage.structure.all
450
451class RingHomomorphism_im_gens(RingHomomorphism):
452    """
453    A ring homomorphism determined by the images of generators.
454    """
455    def __init__(self, parent, im_gens, check=True):
456        RingHomomorphism.__init__(self, parent)
457        if not isinstance(im_gens, (tuple, list)):
458            im_gens = [im_gens]
459        im_gens = sage.structure.all.Sequence(im_gens, parent.codomain())
460        if len(im_gens) != parent.domain().ngens():
461            raise ValueError, "number of images must equal number of generators"
462        if check:
463            t = parent.domain()._is_valid_homomorphism_(parent.codomain(), im_gens)
464            if not t:
465                raise ValueError, "relations do not all (canonically) map to 0 under map determined by images of generators."
466        self.__im_gens = im_gens
467
468    def im_gens(self):
469        return self.__im_gens
470
471    def _repr_defn(self):
472        D = self.domain()
473        ig = self.__im_gens
474        return '\n'.join(['%s |--> %s'%(D.gen(i), ig[i]) for\
475                       i in range(D.ngens())])
476
477    def _call_(self, x):
478        return x._im_gens_(self.codomain(), self.im_gens())
479
480class RingHomomorphism_cover(RingHomomorphism):
481    r"""
482    A homomorphism induced by quotienting a ring out by an ideal.
483
484    EXAMPLES:
485        sage: R.<x,y> = PolynomialRing(QQ, 2)
486        sage: S.<a,b> = R.quo(x^2 + y^2)
487        sage: phi = S.cover(); phi
488        Ring morphism:
489          From: Polynomial Ring in x, y over Rational Field
490          To:   Quotient of Polynomial Ring in x, y over Rational Field by the ideal (y^2 + x^2)
491          Defn: Natural quotient map
492        sage: phi(x+y)
493        b + a
494    """
495    def __init__(self, ring, quotient_ring):
496        RingHomomorphism.__init__(self, ring.Hom(quotient_ring))
497
498    def _call_(self, x):
499        return self.codomain()(x)
500
501    def _repr_defn(self):
502        return "Natural quotient map"
503
504    def kernel(self):
505        return self.codomain().defining_ideal()
506
507
508class RingHomomorphism_from_quotient(RingHomomorphism):
509    r"""
510    A ring homomorphism with domain a generic quotient ring.
511
512    INPUT:
513        parent -- a ring homset Hom(R,S)
514        phi -- a ring homomorphism C --> S, where C is the
515               domain of R.cover()
516    OUTPUT:
517        a ring homomorphism
518
519    The domain $R$ is a quotient object $C \to R$, and
520    \code{R.cover()} is the ring homomorphism $\varphi: C \to R$.  The
521    condition on the elements \code{im_gens} of $S$ is that they
522    define a homomorphism $C \to S$ such that each generator of the
523    kernel of $\varphi$ maps to $0$.
524
525    EXAMPLES:
526        sage: R.<x, y, z> = PolynomialRing(QQ, 3)
527        sage: S.<a, b, c> = R.quo(x^3 + y^3 + z^3)
528        sage: phi = S.hom([b, c, a]); phi
529        Ring endomorphism of Quotient of Polynomial Ring in x, y, z over Rational Field by the ideal (z^3 + y^3 + x^3)
530          Defn: a |--> b
531                b |--> c
532                c |--> a
533        sage: phi(a+b+c)
534        c + b + a
535
536
537     Validity of the homomorphism is determined, when possible, and a
538     TypeError is raised if there is no homomorphism sending the
539     generators to the given images.
540        sage: S.hom([b^2, c^2, a^2])
541        Traceback (most recent call last):
542        ...
543        TypeError: images do not define a valid homomorphism
544    """
545    def __init__(self, parent, phi):
546        RingHomomorphism.__init__(self, parent)
547        R = parent.domain()
548        pi = R.cover()  # the covering map
549        if pi.domain() != phi.domain():
550            raise ValueError, "Domain of phi must equal domain of covering."
551        for x in pi.kernel().gens():
552            if phi(x) != 0:
553                raise ValueError, "relations do not all (canonically) map to 0 under map determined by images of generators."
554        self.__lift = pi.lift()
555        self.__phi = phi
556
557    def morphism_from_cover(self):
558        return self.__phi
559
560    def _repr_defn(self):
561        D = self.domain()
562        ig = self.__phi.im_gens()
563        return '\n'.join(['%s |--> %s'%(D.gen(i), ig[i]) for\
564                          i in range(D.ngens())])
565
566    def _call_(self, x):
567        return self.__phi(self.__lift(x))
568
569
570
Note: See TracBrowser for help on using the repository browser.