Ticket #10963: bla.py

File bla.py, 83.4 KB (added by nthiery, 7 years ago)
Line 
1"""
2Coercion via Construction Functors
3"""
4from functor import Functor, IdentityFunctor_generic
5from basic import *
6
7from sage.structure.parent import CoercionException
8
9# TODO, think through the rankings, and override pushout where necessary.
10
11class ConstructionFunctor(Functor):
12    """
13    Base class for construction functors.
14
15    A construction functor is a functorial algebraic construction,
16    such as the construction of a matrix ring over a given ring
17    or the fraction field of a given ring.
18
19    In addition to the class :class:`~sage.categories.functor.Functor`,
20    construction functors provide rules for combining and merging
21    constructions. This is an important part of Sage's coercion model,
22    namely the pushout of two constructions: When a polynomial ``p`` in
23    a variable ``x`` with integer coefficients is added to a rational
24    number ``q``, then Sage finds that the parents ``ZZ['x']`` and
25    ``QQ`` are obtained from ``ZZ`` by applying a polynomial ring
26    construction respectively the fraction field construction. Each
27    construction functor has an attribute ``rank``, and the rank of
28    the polynomial ring construction is higher than the rank of the
29    fraction field construction. This means that the pushout of ``QQ``
30    and ``ZZ['x']``, and thus a common parent in which ``p`` and ``q``
31    can be added, is ``QQ['x']``, since the construction functor with
32    a lower rank is applied first.
33
34    ::
35
36        sage: F1, R = QQ.construction()
37        sage: F1
38        FractionField
39        sage: R
40        Integer Ring
41        sage: F2, R = (ZZ['x']).construction()
42        sage: F2
43        Poly[x]
44        sage: R
45        Integer Ring
46        sage: F3 = F2.pushout(F1)
47        sage: F3
48        Poly[x](FractionField(...))
49        sage: F3(R)
50        Univariate Polynomial Ring in x over Rational Field
51        sage: from sage.categories.pushout import pushout
52        sage: P.<x> = ZZ[]
53        sage: pushout(QQ,P)
54        Univariate Polynomial Ring in x over Rational Field
55        sage: ((x+1) + 1/2).parent()
56        Univariate Polynomial Ring in x over Rational Field
57
58    When composing two construction functors, they are sometimes
59    merged into one, as is the case in the Quotient construction::
60
61        sage: Q15, R = (ZZ.quo(15*ZZ)).construction()
62        sage: Q15
63        QuotientFunctor
64        sage: Q35, R = (ZZ.quo(35*ZZ)).construction()
65        sage: Q35
66        QuotientFunctor
67        sage: Q15.merge(Q35)
68        QuotientFunctor
69        sage: Q15.merge(Q35)(ZZ)
70        Ring of integers modulo 5
71    """
72    def __mul__(self, other):
73        """
74        Compose construction functors to a composit construction functor, unless one of them is the identity.
75
76        NOTE:
77
78        The product is in functorial notation, i.e., when applying the product to an object
79        then the second factor is applied first.
80
81        TESTS::
82
83            sage: from sage.categories.pushout import IdentityConstructionFunctor
84            sage: I = IdentityConstructionFunctor()
85            sage: F = QQ.construction()[0]
86            sage: P = ZZ['t'].construction()[0]
87            sage: F*P
88            FractionField(Poly[t](...))
89            sage: P*F
90            Poly[t](FractionField(...))
91            sage: (F*P)(ZZ)
92            Fraction Field of Univariate Polynomial Ring in t over Integer Ring
93            sage: I*P is P
94            True
95            sage: F*I is F
96            True
97
98        """
99        if not isinstance(self, ConstructionFunctor) and not isinstance(other, ConstructionFunctor):
100            raise CoercionException, "Non-constructive product"
101        if isinstance(other,IdentityConstructionFunctor):
102            return self
103        if isinstance(self,IdentityConstructionFunctor):
104            return other
105        return CompositeConstructionFunctor(other, self)
106       
107    def pushout(self, other):
108        """
109        Composition of two construction functors, ordered by their ranks.
110
111        NOTE:
112       
113        - This method seems not to be used in the coercion model.
114
115        - By default, the functor with smaller rank is applied first.
116
117        TESTS::
118
119            sage: F = QQ.construction()[0]
120            sage: P = ZZ['t'].construction()[0]
121            sage: F.pushout(P)
122            Poly[t](FractionField(...))
123            sage: P.pushout(F)
124            Poly[t](FractionField(...))
125
126        """
127        if self.rank > other.rank:
128            return self * other
129        else:
130            return other * self
131           
132    def __cmp__(self, other):
133        """
134        Equality here means that they are mathematically equivalent, though they may have
135        specific implementation data. This method will usually be overloaded in subclasses.
136        by default, only the types of the functors are compared. Also see the \code{merge}
137        function.
138
139        TESTS::
140
141            sage: from sage.categories.pushout import IdentityConstructionFunctor
142            sage: I = IdentityConstructionFunctor()
143            sage: F = QQ.construction()[0]
144            sage: P = ZZ['t'].construction()[0]
145            sage: I == F        # indirect doctest
146            False
147            sage: I == I        # indirect doctest
148            True
149
150        """
151        return cmp(type(self), type(other))
152       
153    def __str__(self):
154        """
155        NOTE:
156
157        By default, it returns the name of the construction functor's class.
158        Usually, this method will be overloaded.
159
160        TEST::
161
162            sage: F = QQ.construction()[0]
163            sage: F                  # indirect doctest
164            FractionField
165            sage: Q = ZZ.quo(2).construction()[0]
166            sage: Q                  # indirect doctest
167            QuotientFunctor
168
169        """
170        s = str(type(self))
171        import re
172        return re.sub("<.*'.*\.([^.]*)'>", "\\1", s)
173       
174    def __repr__(self):
175        """
176        NOTE:
177
178        By default, it returns the name of the construction functor's class.
179        Usually, this method will be overloaded.
180
181        TEST::
182
183            sage: F = QQ.construction()[0]
184            sage: F                  # indirect doctest
185            FractionField
186            sage: Q = ZZ.quo(2).construction()[0]
187            sage: Q                  # indirect doctest
188            QuotientFunctor
189
190        """
191        return str(self)
192       
193    def merge(self, other):
194        """
195        Merge ``self`` with another construction functor, or return None.
196
197        NOTE:
198
199        The default is to merge only if the two functors coincide. But this
200        may be overloaded for subclasses, such as the quotient functor.
201
202        EXAMPLES::
203
204            sage: F = QQ.construction()[0]
205            sage: P = ZZ['t'].construction()[0]
206            sage: F.merge(F)
207            FractionField
208            sage: F.merge(P)
209            sage: P.merge(F)
210            sage: P.merge(P)
211            Poly[t]
212
213        """
214        if self == other:
215            return self
216        else:
217            return None
218           
219    def commutes(self, other):
220        """
221        Determine whether ``self`` commutes with another construction functor.
222
223        NOTE:
224
225        By default, ``False`` is returned in all cases (even if the two
226        functors are the same, since in this case :meth:`merge` will apply
227        anyway). So far there is no construction functor that overloads
228        this method. Anyway, this method only becomes relevant if two
229        construction functors have the same rank.
230
231        EXAMPLES::
232
233            sage: F = QQ.construction()[0]
234            sage: P = ZZ['t'].construction()[0]
235            sage: F.commutes(P)
236            False
237            sage: P.commutes(F)
238            False
239            sage: F.commutes(F)
240            False
241       
242        """
243        return False
244
245    def expand(self):
246        """
247        Decompose ``self`` into a list of construction functors.
248
249        NOTE:
250
251        The default is to return the list only containing ``self``.
252
253        EXAMPLE::
254
255            sage: F = QQ.construction()[0]
256            sage: F.expand()
257            [FractionField]
258            sage: Q = ZZ.quo(2).construction()[0]
259            sage: Q.expand()
260            [QuotientFunctor]
261            sage: P = ZZ['t'].construction()[0]
262            sage: FP = F*P
263            sage: FP.expand()
264            [FractionField, Poly[t]]
265        """
266        return [self]
267
268       
269class CompositeConstructionFunctor(ConstructionFunctor):
270    """
271    A Construction Functor composed by other Construction Functors.
272
273    INPUT:
274
275    ``F1, F2,...``: A list of Construction Functors. The result is the
276    composition ``F1`` followed by ``F2`` followed by ...
277
278    EXAMPLES::
279
280        sage: from sage.categories.pushout import CompositeConstructionFunctor
281        sage: F = CompositeConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0],QQ.construction()[0],ZZ['y'].construction()[0])
282        sage: F
283        Poly[y](FractionField(Poly[x](FractionField(...))))
284        sage: F == loads(dumps(F))
285        True
286        sage: F == CompositeConstructionFunctor(*F.all)
287        True
288        sage: F(GF(2)['t'])
289        Univariate Polynomial Ring in y over Fraction Field of Univariate Polynomial Ring in x over Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 2 (using NTL)
290
291    """
292
293    def __init__(self, *args):
294        """
295        TESTS::
296
297            sage: from sage.categories.pushout import CompositeConstructionFunctor
298            sage: F = CompositeConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0],QQ.construction()[0],ZZ['y'].construction()[0])
299            sage: F
300            Poly[y](FractionField(Poly[x](FractionField(...))))
301            sage: F == CompositeConstructionFunctor(*F.all)
302            True
303
304        """
305
306    def _apply_functor_to_morphism(self, f):
307        """
308        Apply the functor to an object of ``self``'s domain.
309       
310        TESTS::
311
312            sage: from sage.categories.pushout import CompositeConstructionFunctor
313            sage: F = CompositeConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0],QQ.construction()[0],ZZ['y'].construction()[0])
314            sage: R.<a,b> = QQ[]
315            sage: f = R.hom([a+b, a-b])
316            sage: F(f)           # indirect doctest
317            Ring ...
318        """
319
320    def _apply_functor(self, R):
321        """
322        Apply the functor to an object of ``self``'s domain.
323       
324        TESTS::
325       
326            sage: from sage.categories.pushout import CompositeConstructionFunctor
327            sage: F = CompositeConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0],QQ.construction()[0],ZZ['y'].construction()[0])
328            sage: R.<a,b> = QQ[]
329            sage: F(R)       # indirect doctest
330            Univariate Polynomial Ring in y over Fraction Field of Univariate Polynomial Ring in x over Fraction Field of Multivariate Polynomial Ring in a, b over Rational Field
331
332        """
333        for c in self.all:
334            R = c(R)
335        return R
336
337    def __cmp__(self, other):
338        """
339        TESTS::
340
341            sage: from sage.categories.pushout import CompositeConstructionFunctor
342            sage: F = CompositeConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0],QQ.construction()[0],ZZ['y'].construction()[0])
343            sage: F == loads(dumps(F)) # indirect doctest
344            True
345
346        """
347        if isinstance(other, CompositeConstructionFunctor):
348            return cmp(self.all, other.all)
349        else:
350            return cmp(type(self), type(other))
351           
352    def __mul__(self, other):
353        """
354        Compose construction functors to a composit construction functor, unless one of them is the identity.
355
356        NOTE:
357
358        The product is in functorial notation, i.e., when applying the product to an object
359        then the second factor is applied first.
360
361        EXAMPLES::
362
363            sage: from sage.categories.pushout import CompositeConstructionFunctor
364            sage: F1 = CompositeConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0])
365            sage: F2 = CompositeConstructionFunctor(QQ.construction()[0],ZZ['y'].construction()[0])
366            sage: F1*F2
367            Poly[x](FractionField(Poly[y](FractionField(...))))
368
369        """
370        if isinstance(self, CompositeConstructionFunctor):
371            all = [other] + self.all
372        elif isinstance(other,IdentityConstructionFunctor):
373            return self
374        else:
375            all = other.all + [self]
376        return CompositeConstructionFunctor(*all)
377   
378    def __str__(self):
379        """
380        TESTS::
381
382            sage: from sage.categories.pushout import CompositeConstructionFunctor
383            sage: F = CompositeConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0],QQ.construction()[0],ZZ['y'].construction()[0])
384            sage: F     # indirect doctest
385            Poly[y](FractionField(Poly[x](FractionField(...))))
386
387        """
388        s = "..."
389        for c in self.all:
390            s = "%s(%s)" % (c,s)
391        return s
392       
393    def expand(self):
394        """
395        Return expansion of a CompositeConstructionFunctor.
396
397        NOTE:
398
399        The product over the list of components, as returned by
400        the ``expand()`` method, is equal to ``self``.
401
402        EXAMPLES::
403
404            sage: from sage.categories.pushout import CompositeConstructionFunctor
405            sage: F = CompositeConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0],QQ.construction()[0],ZZ['y'].construction()[0])
406            sage: F
407            Poly[y](FractionField(Poly[x](FractionField(...))))
408            sage: prod(F.expand()) == F
409            True
410
411        """
412        return list(reversed(self.all))
413
414       
415class IdentityConstructionFunctor(ConstructionFunctor):
416    """
417    A construction functor that is the identity functor.
418
419    TESTS::
420
421        sage: from sage.categories.pushout import IdentityConstructionFunctor
422        sage: I = IdentityConstructionFunctor()
423    """
424    rank = -100
425
426    def __init__(self):
427        """
428        TESTS::
429
430            sage: from sage.categories.pushout import IdentityConstructionFunctor
431            sage: I = IdentityConstructionFunctor()
432            sage: IdentityFunctor(Sets()) == I
433            True
434            sage: I(RR) is RR
435            True
436
437        """
438        ConstructionFunctor.__init__(self, Sets(), Sets())
439
440    def _apply_functor(self, x):
441        """
442        Return the argument unaltered.
443       
444        TESTS::
445
446            sage: from sage.categories.pushout import IdentityConstructionFunctor
447            sage: I = IdentityConstructionFunctor()
448            sage: I(RR) is RR      # indirect doctest
449            True
450        """
451        return x
452
453    def _apply_functor_to_morphism(self, f):
454        """
455        Return the argument unaltered.
456       
457        TESTS::
458
459            sage: from sage.categories.pushout import IdentityConstructionFunctor
460            sage: I = IdentityConstructionFunctor()
461            sage: f = ZZ['t'].hom(['x'],QQ['x'])
462        """
463        return f
464
465    def __cmp__(self, other):
466        """
467        TESTS::
468       
469            sage: from sage.categories.pushout import IdentityConstructionFunctor
470            sage: I = IdentityConstructionFunctor()
471            sage: I == IdentityFunctor(Sets())     # indirect doctest
472            True
473            sage: I == QQ.construction()[0]
474            False
475
476        """
477
478    def __mul__(self, other):
479        """
480        Compose construction functors to a composit construction functor, unless one of them is the identity.
481
482        NOTE:
483
484        The product is in functorial notation, i.e., when applying the product to an object
485        then the second factor is applied first.
486
487        TESTS::
488
489            sage: from sage.categories.pushout import IdentityConstructionFunctor
490            sage: I = IdentityConstructionFunctor()
491            sage: F = QQ.construction()[0]
492            sage: P = ZZ['t'].construction()[0]
493            sage: I*F is F     # indirect doctest
494            True
495            sage: F*I is F
496            True
497            sage: I*P is P
498            True
499            sage: P*I is P
500            True
501
502        """
503        if isinstance(self, IdentityConstructionFunctor):
504            return other
505        else:
506            return self
507
508
509class PolynomialFunctor(ConstructionFunctor):
510    """
511    Construction functor for univariate polynomial rings.
512
513    EXAMPLE::
514
515        sage: P = ZZ['t'].construction()[0]
516        sage: P(GF(3))
517        Univariate Polynomial Ring in t over Finite Field of size 3
518        sage: P == loads(dumps(P))
519        True
520        sage: R.<x,y> = GF(5)[]
521        sage: f = R.hom([x+2*y,3*x-y],R)
522        sage: P(f)((x+y)*P(R).0)
523        (-x + y)*t
524
525    By trac ticket #9944, the construction functor distinguishes sparse and
526    dense polynomial rings. Before, the following example failed::
527
528        sage: R.<x> = PolynomialRing(GF(5), sparse=True)
529        sage: F,B = R.construction()
530        sage: F(B) is R
531        True
532        sage: S.<x> = PolynomialRing(ZZ)
533        sage: R.has_coerce_map_from(S)
534        False
535        sage: S.has_coerce_map_from(R)
536        False
537        sage: S.0 + R.0
538        2*x
539        sage: 1+1
540        2
541        sage: 1+1
542        2
543    """
544    rank = 9
545
546    def __init__(self, var, multi_variate=False, sparse=False):
547        """
548        TESTS::
549
550            sage: from sage.categories.pushout import PolynomialFunctor
551            sage: P = PolynomialFunctor('x')
552            sage: P(GF(3))
553            Univariate Polynomial Ring in x over Finite Field of size 3
554
555        There is an optional parameter ``multi_variate``, but
556        apparently it is not used::
557
558            sage: Q = PolynomialFunctor('x',multi_variate=True)
559            sage: Q(ZZ)
560            Univariate Polynomial Ring in x over Integer Ring
561            sage: Q == P
562            True
563
564        """
565        from rings import Rings
566        Functor.__init__(self, Rings(), Rings())
567        self.var = var
568        self.multi_variate = multi_variate
569        self.sparse = sparse
570
571    def _apply_functor(self, R):
572        """
573        Apply the functor to an object of ``self``'s domain.
574       
575        TEST::
576
577            sage: P = ZZ['x'].construction()[0]
578            sage: P(GF(3))      # indirect doctest
579            Univariate Polynomial Ring in x over Finite Field of size 3
580
581        """
582        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
583        return PolynomialRing(R, self.var, sparse=self.sparse)
584
585    def __cmp__(self, other):
586        """
587        TESTS::
588
589            sage: from sage.categories.pushout import MultiPolynomialFunctor
590            sage: Q = MultiPolynomialFunctor(('x',),'lex')
591            sage: P = ZZ['x'].construction()[0]
592            sage: P
593            Poly[x]
594            sage: Q
595            MPoly[x]
596            sage: P == Q
597            True
598            sage: P == loads(dumps(P))
599            True
600            sage: P == QQ.construction()[0]
601            False
602        """
603
604    def merge(self, other):
605        """
606        EXAMPLE::
607
608            sage: P = ZZ['x'].construction()[0]
609            sage: Q = ZZ['y','x'].construction()[0]
610            sage: P.merge(Q)
611            sage: P.merge(P) is P
612            True
613
614        """
615        if isinstance(other, MultiPolynomialFunctor):
616            return other.merge(self)
617        elif self == other:
618            # i.e., they only differ in sparsity
619            if not self.sparse:
620                return self
621            return other
622        else:
623            return None
624
625    def __str__(self):
626        """
627        TEST::
628
629            sage: P = ZZ['x'].construction()[0]
630            sage: P       # indirect doctest
631            Poly[x]
632
633        """
634        return "Poly[%s]" % self.var
635
636class MultiPolynomialFunctor(ConstructionFunctor):
637    """
638    A constructor for multivariate polynomial rings.
639
640    EXAMPLES::
641
642        sage: P.<x,y> = ZZ[]
643        sage: F = P.construction()[0]; F
644        MPoly[x,y]
645        sage: A.<a,b> = GF(5)[]
646        sage: F(A)
647        Multivariate Polynomial Ring in x, y over Multivariate Polynomial Ring in a, b over Finite Field of size 5
648        sage: f = A.hom([a+b,a-b],A)
649        sage: F(f)
650        Ring endomorphism of Multivariate Polynomial Ring in x, y over Multivariate Polynomial Ring in a, b over Finite Field of size 5
651          Defn: Induced from base ring by
652                Ring endomorphism of Multivariate Polynomial Ring in a, b over Finite Field of size 5
653                  Defn: a |--> a + b
654                        b |--> a - b
655        sage: F(f)(F(A)(x)*a)
656        (a + b)*x
657
658    """
659   
660    rank = 9
661
662    def __init__(self, vars, term_order):
663        """
664        EXAMPLES::
665       
666            sage: F = sage.categories.pushout.MultiPolynomialFunctor(['x','y'], None)
667            sage: F(CC)
668            Multivariate Polynomial Ring in x, y over Complex Field with 53 bits of precision
669        """
670        Functor.__init__(self, Rings(), Rings())
671        self.vars = vars
672        self.term_order = term_order
673
674    def _apply_functor(self, R):
675        """
676        Apply the functor to an object of ``self``'s domain.
677       
678        EXAMPLES::
679       
680            sage: R.<x,y,z> = QQ[]
681            sage: F = R.construction()[0]; F
682            MPoly[x,y,z]
683            sage: F(RR)          # indirect doctest
684            Multivariate Polynomial Ring in x, y, z over Real Field with 53 bits of precision
685            sage: F(RR)          # indirect doctest
686            Multivariate Polynomial Ring in x, y, z over Real Field with 53 bits of precision
687            sage: F(RR)          # indirect doctest
688            Multivariate Polynomial Ring in x, y, z over Real Field with 53 bits of precision
689            sage: F(RR)          # indirect doctest
690            Multivariate Polynomial Ring in x, y, z over Real Field with 53 bits of precision
691            sage: F(RR)          # indirect doctest
692            Multivariate Polynomial Ring in x, y, z over Real Field with 53 bits of precision
693        """
694        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
695        return PolynomialRing(R, self.vars)
696
697    def __cmp__(self, other):
698        """
699        EXAMPLES::
700       
701            sage: F = ZZ['x,y,z'].construction()[0]
702            sage: G = QQ['x,y,z'].construction()[0]
703            sage: F == G
704            True
705            sage: G == loads(dumps(G))
706            True
707            sage: G = ZZ['x,y'].construction()[0]
708            sage: F == G
709            False
710        """
711        c = cmp(type(self), type(other))
712        if c == 0:
713            c = cmp(self.vars, other.vars) or cmp(self.term_order, other.term_order)
714        elif isinstance(other, PolynomialFunctor):
715            c = cmp(self.vars, (other.var,))
716        return c
717       
718    def __mul__(self, other):
719        """
720        If two MPoly functors are given in a row, form a single MPoly functor
721        with all of the variables.
722       
723        EXAMPLES::
724       
725            sage: F = sage.categories.pushout.MultiPolynomialFunctor(['x','y'], None)
726            sage: G = sage.categories.pushout.MultiPolynomialFunctor(['t'], None)
727            sage: G*F
728            MPoly[x,y,t]
729        """
730        if isinstance(other,IdentityConstructionFunctor):
731            return self
732        if isinstance(other, MultiPolynomialFunctor):
733            if self.term_order != other.term_order:
734                raise CoercionException, "Incompatible term orders (%s,%s)." % (self.term_order, other.term_order)
735            if set(self.vars).intersection(other.vars):
736                raise CoercionException, "Overlapping variables (%s,%s)" % (self.vars, other.vars)
737            return MultiPolynomialFunctor(other.vars + self.vars, self.term_order)
738        elif isinstance(other, CompositeConstructionFunctor) \
739              and isinstance(other.all[-1], MultiPolynomialFunctor):
740            return CompositeConstructionFunctor(other.all[:-1], self * other.all[-1])
741        else:
742            return CompositeConstructionFunctor(other, self)
743
744    def merge(self, other):
745        """
746        Merge ``self`` with another construction functor, or return None.
747       
748        EXAMPLES::
749       
750            sage: F = sage.categories.pushout.MultiPolynomialFunctor(['x','y'], None)
751            sage: G = sage.categories.pushout.MultiPolynomialFunctor(['t'], None)
752            sage: F.merge(G) is None
753            True
754            sage: F.merge(F)
755            MPoly[x,y]
756        """
757        if self == other:
758            return self
759        else:
760            return None
761
762    def expand(self):
763        """
764        Decompose ``self`` into a list of construction functors.
765       
766        EXAMPLES::
767       
768            sage: F = QQ['x,y,z,t'].construction()[0]; F
769            MPoly[x,y,z,t]
770            sage: F.expand()
771            [MPoly[t], MPoly[z], MPoly[y], MPoly[x]]
772           
773        Now an actual use case::
774       
775            sage: R.<x,y,z> = ZZ[]
776            sage: S.<z,t> = QQ[]
777            sage: x+t
778            x + t
779            sage: parent(x+t)
780            Multivariate Polynomial Ring in x, y, z, t over Rational Field
781            sage: T.<y,s> = QQ[]
782            sage: x + s
783            Traceback (most recent call last):
784            ...
785            TypeError: unsupported operand parent(s) for '+': 'Multivariate Polynomial Ring in x, y, z over Integer Ring' and 'Multivariate Polynomial Ring in y, s over Rational Field'
786            sage: R = PolynomialRing(ZZ, 'x', 500)
787            sage: S = PolynomialRing(GF(5), 'x', 200)
788            sage: R.gen(0) + S.gen(0)
789            2*x0
790        """
791        if len(self.vars) <= 1:
792            return [self]
793        else:
794            return [MultiPolynomialFunctor((x,), self.term_order) for x in reversed(self.vars)]
795
796    def __str__(self):
797        """
798        TEST::
799       
800            sage: QQ['x,y,z,t'].construction()[0]
801            MPoly[x,y,z,t]
802        """
803        return "MPoly[%s]" % ','.join(self.vars)
804
805
806
807class InfinitePolynomialFunctor(ConstructionFunctor):
808    """
809    A Construction Functor for Infinite Polynomial Rings (see :mod:`~sage.rings.polynomial.infinite_polynomial_ring`).
810   
811    AUTHOR:
812
813    -- Simon King
814
815    This construction functor is used to provide uniqueness of infinite polynomial rings as parent structures.
816    As usual, the construction functor allows for constructing pushouts.
817   
818    Another purpose is to avoid name conflicts of variables of the to-be-constructed infinite polynomial ring with
819    variables of the base ring, and moreover to keep the internal structure of an Infinite Polynomial Ring as simple
820    as possible: If variables `v_1,...,v_n` of the given base ring generate an *ordered* sub-monoid of the monomials
821    of the ambient Infinite Polynomial Ring, then they are removed from the base ring and merged with the generators
822    of the ambient ring. However, if the orders don't match, an error is raised, since there was a name conflict
823    without merging.
824
825    EXAMPLES::
826
827        sage: A.<a,b> = InfinitePolynomialRing(ZZ['t'])
828        sage: A.construction()
829        [InfPoly{[a,b], "lex", "dense"},
830         Univariate Polynomial Ring in t over Integer Ring]
831        sage: type(_[0])
832        <class 'sage.categories.pushout.InfinitePolynomialFunctor'>
833        sage: B.<x,y,a_3,a_1> = PolynomialRing(QQ, order='lex')
834        sage: B.construction()
835        (MPoly[x,y,a_3,a_1], Rational Field)
836        sage: A.construction()[0]*B.construction()[0]
837        InfPoly{[a,b], "lex", "dense"}(MPoly[x,y](...))
838
839    Apparently the variables `a_1,a_3` of the polynomial ring are merged with the variables
840    `a_0, a_1, a_2, ...` of the infinite polynomial ring; indeed, they form an ordered sub-structure.
841    However, if the polynomial ring was given a different ordering, merging would not be allowed,
842    resulting in a name conflict::
843
844        sage: A.construction()[0]*PolynomialRing(QQ,names=['x','y','a_3','a_1']).construction()[0]
845        Traceback (most recent call last):
846        ...
847        CoercionException: Incompatible term orders lex, degrevlex
848
849    In an infinite polynomial ring with generator `a_\\ast`, the variable `a_3` will always be greater
850    than the variable `a_1`. Hence, the orders are incompatible in the next example as well::
851       
852        sage: A.construction()[0]*PolynomialRing(QQ,names=['x','y','a_1','a_3'], order='lex').construction()[0]
853        Traceback (most recent call last):
854        ...
855        CoercionException: Overlapping variables (('a', 'b'),['a_1', 'a_3']) are incompatible
856
857    Another requirement is that after merging the order of the remaining variables must be unique.
858    This is not the case in the following example, since it is not clear whether the variables `x,y`
859    should be greater or smaller than the variables `b_\\ast`::
860
861        sage: A.construction()[0]*PolynomialRing(QQ,names=['a_3','a_1','x','y'], order='lex').construction()[0]
862        Traceback (most recent call last):
863        ...
864        CoercionException: Overlapping variables (('a', 'b'),['a_3', 'a_1']) are incompatible
865
866    Since the construction functors are actually used to construct infinite polynomial rings, the following
867    result is no surprise::
868
869        sage: C.<a,b> = InfinitePolynomialRing(B); C
870        Infinite polynomial ring in a, b over Multivariate Polynomial Ring in x, y over Rational Field
871
872    There is also an overlap in the next example::
873
874        sage: X.<w,x,y> = InfinitePolynomialRing(ZZ)
875        sage: Y.<x,y,z> = InfinitePolynomialRing(QQ)
876
877    `X` and `Y` have an overlapping generators `x_\\ast, y_\\ast`. Since the default lexicographic order is
878    used in both rings, it gives rise to isomorphic sub-monoids in both `X` and `Y`. They are merged in the
879    pushout, which also yields a common parent for doing arithmetic::
880
881        sage: P = sage.categories.pushout.pushout(Y,X); P
882        Infinite polynomial ring in w, x, y, z over Rational Field
883        sage: w[2]+z[3]
884        w_2 + z_3
885        sage: _.parent() is P
886        True
887    """
888
889    def __init__(self, gens, order, implementation):
890        """
891        TEST::
892
893            sage: 1+1
894            2
895            sage: 1+1
896            2
897        """
898
899    def _apply_functor_to_morphism(self, f):
900        """
901        Morphisms for inifinite polynomial rings are not implemented yet.
902
903        TEST::
904
905            sage: P.<x,y> = QQ[]
906            sage: R.<alpha> = InfinitePolynomialRing(P)
907            sage: 1+1
908            2
909            sage: 1+1
910            2
911            sage: 1+1
912            2
913        """
914
915    def _apply_functor(self, R):
916        """
917        Apply the functor to an object of ``self``'s domain.
918       
919        TEST::
920
921            sage: F = sage.categories.pushout.InfinitePolynomialFunctor(['a','b','x'],'degrevlex','sparse'); F
922            InfPoly{[a,b,x], "degrevlex", "sparse"}
923            sage: F(QQ['t']) # indirect doctest
924            Infinite polynomial ring in a, b, x over Univariate Polynomial Ring in t over Rational Field
925
926        """
927        from sage.rings.polynomial.infinite_polynomial_ring import InfinitePolynomialRing
928        return InfinitePolynomialRing(R, self._gens, order=self._order, implementation=self._imple)
929
930    def __str__(self):
931        """
932        TEST::
933
934            sage: F = sage.categories.pushout.InfinitePolynomialFunctor(['a','b','x'],'degrevlex','sparse'); F # indirect doctest
935            InfPoly{[a,b,x], "degrevlex", "sparse"}
936
937        """
938        return 'InfPoly{[%s], "%s", "%s"}'%(','.join(self._gens), self._order, self._imple)
939
940    def __cmp__(self, other):
941        """
942        TEST::
943
944            sage: F = sage.categories.pushout.InfinitePolynomialFunctor(['a','b','x'],'degrevlex','sparse'); F # indirect doctest
945            InfPoly{[a,b,x], "degrevlex", "sparse"}
946            sage: F == sage.categories.pushout.InfinitePolynomialFunctor(['a','b','x'],'deglex','sparse')
947            False
948
949        """
950        c = cmp(type(self), type(other))
951        if c == 0:
952            c = cmp(self._gens, other._gens) or cmp(self._order, other._order) or cmp(self._imple, other._imple)
953        return c
954
955    def __mul__(self, other):
956        """
957        Compose construction functors to a composit construction functor, unless one of them is the identity.
958
959        NOTE:
960
961        The product is in functorial notation, i.e., when applying the product to an object
962        then the second factor is applied first.
963
964        TESTS::
965
966            sage: F1 = QQ['a','x_2','x_1','y_3','y_2'].construction()[0]; F1
967            MPoly[a,x_2,x_1,y_3,y_2]
968            sage: F2 = InfinitePolynomialRing(QQ, ['x','y'],order='degrevlex').construction()[0]; F2
969            InfPoly{[x,y], "degrevlex", "dense"}
970            sage: F3 = InfinitePolynomialRing(QQ, ['x','y'],order='degrevlex',implementation='sparse').construction()[0]; F3
971            InfPoly{[x,y], "degrevlex", "sparse"}
972            sage: F2*F1
973            InfPoly{[x,y], "degrevlex", "dense"}(Poly[a](...))
974            sage: F3*F1
975            InfPoly{[x,y], "degrevlex", "sparse"}(Poly[a](...))
976            sage: F4 = sage.categories.pushout.FractionField()
977            sage: F2*F4
978            InfPoly{[x,y], "degrevlex", "dense"}(FractionField(...))
979
980        """
981        if isinstance(other,IdentityConstructionFunctor):
982            return self
983        if isinstance(other, self.__class__): #
984            INT = set(self._gens).intersection(other._gens)
985            if INT:
986                # if there is overlap of generators, it must only be at the ends, so that
987                # the resulting order after the merging is unique
988                if other._gens[-len(INT):] != self._gens[:len(INT)]:
989                    raise CoercionException, "Overlapping variables (%s,%s) are incompatible" % (self._gens, other._gens)
990                OUTGENS = list(other._gens) + list(self._gens[len(INT):])
991            else:
992                OUTGENS = list(other._gens) + list(self._gens)
993            # the orders must coincide
994            if self._order != other._order:
995                return CompositeConstructionFunctor(other, self)
996            # the implementations must coincide
997            if self._imple != other._imple:
998                return CompositeConstructionFunctor(other, self)
999            return InfinitePolynomialFunctor(OUTGENS, self._order, self._imple)
1000
1001        # Polynomial Constructor
1002        # Idea: We merge into self, if the polynomial functor really provides a substructure,
1003        # even respecting the order. Note that, if the pushout is computed, only *one* variable
1004        # will occur in the polynomial constructor. Hence, any order is fine, which is exactly
1005        # what we need in order to have coercion maps for different orderings.
1006        if isinstance(other, MultiPolynomialFunctor) or isinstance(other, PolynomialFunctor):
1007            if isinstance(other, MultiPolynomialFunctor):
1008                othervars = other.vars
1009            else:
1010                othervars = [other.var]
1011            OverlappingGens = [] ## Generator names of variable names of the MultiPolynomialFunctor
1012                              ## that can be interpreted as variables in self
1013            OverlappingVars = [] ## The variable names of the MultiPolynomialFunctor
1014                                 ## that can be interpreted as variables in self
1015            RemainingVars = [x for x in othervars]
1016            IsOverlap = False
1017            BadOverlap = False
1018            for x in othervars:
1019                if x.count('_') == 1:
1020                    g,n = x.split('_')
1021                    if n.isdigit():
1022                        if g.isalnum(): # we can interprete x in any InfinitePolynomialRing
1023                            if g in self._gens: # we can interprete x in self, hence, we will not use it as a variable anymore.
1024                                RemainingVars.pop(RemainingVars.index(x))
1025                                IsOverlap = True # some variables of other can be interpreted in self.
1026                                if OverlappingVars:
1027                                    # Is OverlappingVars in the right order?
1028                                    g0,n0 = OverlappingVars[-1].split('_')
1029                                    i = self._gens.index(g)
1030                                    i0 = self._gens.index(g0)
1031                                    if i<i0: # wrong order
1032                                        BadOverlap = True
1033                                    if i==i0 and int(n)>int(n0): # wrong order
1034                                        BadOverlap = True
1035                                OverlappingVars.append(x)
1036                            else:
1037                                if IsOverlap: # The overlap must be on the right end of the variable list
1038                                    BadOverlap = True
1039                        else:
1040                            if IsOverlap: # The overlap must be on the right end of the variable list
1041                                BadOverlap = True
1042                    else:
1043                        if IsOverlap: # The overlap must be on the right end of the variable list
1044                            BadOverlap = True
1045                else:
1046                    if IsOverlap: # The overlap must be on the right end of the variable list
1047                        BadOverlap = True
1048                   
1049            if BadOverlap: # the overlapping variables appear in the wrong order
1050                raise CoercionException, "Overlapping variables (%s,%s) are incompatible" % (self._gens, OverlappingVars)
1051            if len(OverlappingVars)>1: # multivariate, hence, the term order matters
1052                if other.term_order.name()!=self._order:
1053                    raise CoercionException, "Incompatible term orders %s, %s" % (self._order, other.term_order.name())
1054            # ok, the overlap is fine, we will return something.
1055            if RemainingVars: # we can only partially merge other into self
1056                if len(RemainingVars)>1:
1057                    return CompositeConstructionFunctor(MultiPolynomialFunctor(RemainingVars,term_order=other.term_order), self)
1058                return CompositeConstructionFunctor(PolynomialFunctor(RemainingVars[0]), self)
1059            return self
1060        return CompositeConstructionFunctor(other, self)
1061
1062    def merge(self,other):
1063        """
1064        Merge two construction functors of infinite polynomial rings, regardless of monomial order and implementation.
1065
1066        The purpose is to have a pushout (and thus, arithmetic) even in cases when the parents are isomorphic as
1067        rings, but not as ordered rings.
1068
1069        EXAMPLES::
1070
1071            sage: X.<x,y> = InfinitePolynomialRing(QQ,implementation='sparse')
1072            sage: Y.<x,y> = InfinitePolynomialRing(QQ,order='degrevlex')
1073            sage: X.construction()
1074            [InfPoly{[x,y], "lex", "sparse"}, Rational Field]
1075            sage: Y.construction()
1076            [InfPoly{[x,y], "degrevlex", "dense"}, Rational Field]
1077            sage: Y.construction()[0].merge(Y.construction()[0])
1078            InfPoly{[x,y], "degrevlex", "dense"}
1079            sage: y[3] + X(x[2])
1080            x_2 + y_3
1081            sage: _.parent().construction()
1082            [InfPoly{[x,y], "degrevlex", "dense"}, Rational Field]
1083
1084        """
1085        # Merging is only done if the ranks of self and other are the same.
1086        # It may happen that other is a substructure of self up to the monomial order
1087        # and the implementation. And this is when we want to merge, in order to
1088        # provide multiplication for rings with different term orderings.
1089        if not isinstance(other, InfinitePolynomialFunctor):
1090            return None
1091        if set(other._gens).issubset(self._gens):
1092            return self
1093        return None
1094        try:
1095            OUT = self*other
1096            # The following happens if "other" has the same order type etc.
1097            if not isinstance(OUT, CompositeConstructionFunctor):
1098                return OUT
1099        except CoercionException:
1100            pass
1101        if isinstance(other,InfinitePolynomialFunctor):
1102            # We don't require that the orders coincide. This is a difference to self*other
1103            # We only merge if other's generators are an ordered subset of self's generators
1104            for g in other._gens:
1105                if g not in self._gens:
1106                    return None
1107            # The sequence of variables is part of the ordering. It must coincide in both rings
1108            Ind = [self._gens.index(g) for g in other._gens]
1109            if sorted(Ind)!=Ind:
1110                return None
1111            # OK, other merges into self. Now, chose the default dense implementation,
1112            # unless both functors refer to the sparse implementation
1113            if self._imple != other._imple:
1114                return InfinitePolynomialFunctor(self._gens, self._order, 'dense')
1115            return self
1116        return None
1117
1118    def expand(self):
1119        """
1120        Decompose the functor `F` into sub-functors, whose product returns `F`.
1121
1122        EXAMPLES::
1123
1124            sage: F = InfinitePolynomialRing(QQ, ['x','y'],order='degrevlex').construction()[0]; F
1125            InfPoly{[x,y], "degrevlex", "dense"}
1126            sage: F.expand()
1127            [InfPoly{[y], "degrevlex", "dense"}, InfPoly{[x], "degrevlex", "dense"}]
1128            sage: F = InfinitePolynomialRing(QQ, ['x','y','z'],order='degrevlex').construction()[0]; F
1129            InfPoly{[x,y,z], "degrevlex", "dense"}
1130            sage: F.expand()
1131            [InfPoly{[z], "degrevlex", "dense"},
1132             InfPoly{[y], "degrevlex", "dense"},
1133             InfPoly{[x], "degrevlex", "dense"}]
1134            sage: prod(F.expand())==F
1135            True
1136
1137        """
1138        if len(self._gens)==1:
1139            return [self]
1140        return [InfinitePolynomialFunctor((x,), self._order, self._imple) for x in reversed(self._gens)]
1141
1142
1143
1144class MatrixFunctor(ConstructionFunctor):
1145    """
1146    A construction functor for matrices over rings.
1147
1148    EXAMPLES::
1149
1150        sage: MS = MatrixSpace(ZZ,2, 3)
1151        sage: F = MS.construction()[0]; F
1152        MatrixFunctor
1153        sage: MS = MatrixSpace(ZZ,2)
1154        sage: F = MS.construction()[0]; F
1155        MatrixFunctor
1156        sage: P.<x,y> = QQ[]
1157        sage: R = F(P); R
1158        Full MatrixSpace of 2 by 2 dense matrices over Multivariate Polynomial Ring in x, y over Rational Field
1159        sage: f = P.hom([x+y,x-y],P); F(f)
1160        Ring endomorphism of Full MatrixSpace of 2 by 2 dense matrices over Multivariate Polynomial Ring in x, y over Rational Field
1161          Defn: Induced from base ring by
1162                Ring endomorphism of Multivariate Polynomial Ring in x, y over Rational Field
1163                  Defn: x |--> x + y
1164                        y |--> x - y
1165        sage: M = R([x,y,x*y,x+y])
1166        sage: F(f)(M)
1167        [    x + y     x - y]
1168        [x^2 - y^2       2*x]
1169
1170    """
1171    rank = 10
1172
1173    def __init__(self, nrows, ncols, is_sparse=False):
1174        """
1175        TEST::
1176
1177            sage: from sage.categories.pushout import MatrixFunctor
1178            sage: F = MatrixFunctor(2,3)
1179            sage: F == MatrixSpace(ZZ,2,3).construction()[0]
1180            True
1181            sage: F.codomain()
1182            Category of commutative additive groups
1183            sage: R = MatrixSpace(ZZ,2,2).construction()[0]
1184            sage: R.codomain()
1185            Category of rings
1186            sage: F(ZZ)
1187            Full MatrixSpace of 2 by 3 dense matrices over Integer Ring
1188            sage: F(ZZ) in F.codomain()
1189            True
1190            sage: R(GF(2))
1191            Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 2
1192            sage: R(GF(2)) in R.codomain()
1193            True
1194        """
1195        if nrows == ncols:
1196            Functor.__init__(self, Rings(), Rings()) # Algebras() takes a base ring
1197        else:
1198            # Functor.__init__(self, Rings(), MatrixAlgebras()) # takes a base ring
1199            Functor.__init__(self, Rings(), CommutativeAdditiveGroups()) # not a nice solution, but the best we can do.
1200        self.nrows = nrows
1201        self.ncols = ncols
1202        self.is_sparse = is_sparse
1203
1204    def _apply_functor(self, R):
1205        """
1206        Apply the functor to an object of ``self``'s domain.
1207       
1208        TEST:
1209
1210        The following is a test against a bug discussed at ticket #8800
1211
1212            sage: F = MatrixSpace(ZZ,2,3).construction()[0]
1213            sage: F(RR)         # indirect doctest
1214            Full MatrixSpace of 2 by 3 dense matrices over Real Field with 53 bits of precision
1215            sage: F(RR) in F.codomain()
1216            True
1217
1218        """
1219        from sage.matrix.matrix_space import MatrixSpace
1220        return MatrixSpace(R, self.nrows, self.ncols, sparse=self.is_sparse)
1221
1222    def __cmp__(self, other):
1223        """
1224        TEST::
1225       
1226            sage: F = MatrixSpace(ZZ,2,3).construction()[0]
1227            sage: F == loads(dumps(F))
1228            True
1229            sage: F == MatrixSpace(ZZ,2,2).construction()[0]
1230            False
1231
1232        """
1233        c = cmp(type(self), type(other))
1234        if c == 0:
1235            c = cmp((self.nrows, self.ncols), (other.nrows, other.ncols))
1236        return c
1237
1238    def merge(self, other):
1239        """
1240        Merging is only happening if both functors are matrix functors of the same dimension.
1241        The result is sparse if and only if both given functors are sparse.
1242
1243        EXAMPLE::
1244
1245            sage: F1 = MatrixSpace(ZZ,2,2).construction()[0]
1246            sage: F2 = MatrixSpace(ZZ,2,3).construction()[0]
1247            sage: F3 = MatrixSpace(ZZ,2,2,sparse=True).construction()[0]
1248            sage: F1.merge(F2)
1249            sage: F1.merge(F3)
1250            MatrixFunctor
1251            sage: F13 = F1.merge(F3)
1252            sage: F13.is_sparse
1253            False
1254            sage: F1.is_sparse
1255            False
1256            sage: F3.is_sparse
1257            True
1258            sage: F3.merge(F3).is_sparse
1259            True
1260
1261        """
1262        if self != other:
1263            return None
1264        else:
1265            return MatrixFunctor(self.nrows, self.ncols, self.is_sparse and other.is_sparse)
1266
1267class LaurentPolynomialFunctor(ConstructionFunctor):
1268    """
1269    Construction functor for Laurent polynomial rings.
1270
1271    EXAMPLES::
1272
1273        sage: L.<t> = LaurentPolynomialRing(ZZ)
1274        sage: F = L.construction()[0]
1275        sage: F
1276        LaurentPolynomialFunctor
1277        sage: F(QQ)
1278        Univariate Laurent Polynomial Ring in t over Rational Field
1279        sage: K.<x> = LaurentPolynomialRing(ZZ)
1280        sage: F(K)
1281        Univariate Laurent Polynomial Ring in t over Univariate Laurent Polynomial Ring in x over Integer Ring
1282        sage: P.<x,y> = ZZ[]
1283        sage: f = P.hom([x+2*y,3*x-y],P)
1284        sage: F(f)
1285        Ring endomorphism of Univariate Laurent Polynomial Ring in t over Multivariate Polynomial Ring in x, y over Integer Ring
1286          Defn: Induced from base ring by
1287                Ring endomorphism of Multivariate Polynomial Ring in x, y over Integer Ring
1288                  Defn: x |--> x + 2*y
1289                        y |--> 3*x - y
1290        sage: F(f)(x*F(P).gen()^-2+y*F(P).gen()^3)
1291        (3*x - y)*t^3 + (x + 2*y)*t^-2
1292
1293    """
1294    rank = 9
1295
1296    def __init__(self, var, multi_variate=False):
1297        """
1298        INPUT:
1299
1300        - ``var``, a string or a list of strings
1301        - ``multi_variate``, optional bool, default ``False`` if ``var`` is a string
1302          and ``True`` otherwise: If ``True``, application to a Laurent polynomial
1303          ring yields a multivariate Laurent polynomial ring.
1304
1305        TESTS::
1306
1307            sage: from sage.categories.pushout import LaurentPolynomialFunctor
1308            sage: F1 = LaurentPolynomialFunctor('t')
1309            sage: F2 = LaurentPolynomialFunctor('s', multi_variate=True)
1310            sage: F3 = LaurentPolynomialFunctor(['s','t'])
1311            sage: F1(F2(QQ))
1312            Univariate Laurent Polynomial Ring in t over Univariate Laurent Polynomial Ring in s over Rational Field
1313            sage: F2(F1(QQ))
1314            Multivariate Laurent Polynomial Ring in t, s over Rational Field
1315            sage: F3(QQ)
1316            Multivariate Laurent Polynomial Ring in s, t over Rational Field
1317
1318        """
1319        Functor.__init__(self, Rings(), Rings())
1320        if not isinstance(var, (basestring,tuple,list)):
1321            raise TypeError, "variable name or list of variable names expected"
1322        self.var = var
1323        self.multi_variate = multi_variate or not isinstance(var, basestring)
1324
1325    def __cmp__(self, other):
1326        """
1327        TESTS::
1328
1329            sage: from sage.categories.pushout import LaurentPolynomialFunctor
1330            sage: F1 = LaurentPolynomialFunctor('t')
1331            sage: F2 = LaurentPolynomialFunctor('t', multi_variate=True)
1332            sage: F3 = LaurentPolynomialFunctor(['s','t'])
1333            sage: F1 == F2
1334            True
1335            sage: F1 == loads(dumps(F1))
1336            True
1337            sage: F1 == F3
1338            False
1339            sage: F1 == QQ.construction()[0]
1340            False
1341
1342        """
1343        c = cmp(type(self), type(other))
1344        if c == 0:
1345            c = cmp(self.var, other.var)
1346        return c
1347
1348    def merge(self, other):
1349        """
1350        Two Laurent polynomial construction functors merge if the variable names coincide.
1351        The result is multivariate if one of the arguments is multivariate.
1352
1353        EXAMPLE::
1354
1355            sage: from sage.categories.pushout import LaurentPolynomialFunctor
1356            sage: F1 = LaurentPolynomialFunctor('t')
1357            sage: F2 = LaurentPolynomialFunctor('t', multi_variate=True)
1358            sage: F1.merge(F2)
1359            LaurentPolynomialFunctor
1360            sage: F1.merge(F2)(LaurentPolynomialRing(GF(2),'a'))
1361            Multivariate Laurent Polynomial Ring in a, t over Finite Field of size 2
1362            sage: F1.merge(F1)(LaurentPolynomialRing(GF(2),'a'))
1363            Univariate Laurent Polynomial Ring in t over Univariate Laurent Polynomial Ring in a over Finite Field of size 2
1364
1365        """
1366        if self == other or isinstance(other, PolynomialFunctor) and self.var == other.var:
1367            return LaurentPolynomialFunctor(self.var, (self.multi_variate or other.multi_variate))
1368        else:
1369            return None
1370
1371       
1372class VectorFunctor(ConstructionFunctor):
1373    """
1374    A construction functor for free modules over commutative rings.
1375
1376    EXAMPLE::
1377
1378        sage: F = (ZZ^3).construction()[0]
1379        sage: F
1380        VectorFunctor
1381        sage: F(GF(2)['t'])
1382        Ambient free module of rank 3 over the principal ideal domain Univariate Polynomial Ring in t over Finite Field of size 2 (using NTL)
1383       
1384
1385    """
1386    rank = 10 # ranking of functor, not rank of module.
1387    # This coincides with the rank of the matrix construction functor, but this is OK since they can not both be applied in any order
1388
1389
1390def pushout_lattice(R, S):
1391    r"""
1392    Given a pair of Objects $R$ and $S$, try and construct a
1393    reasonable object $Y$ and return maps such that
1394    canonically $R \leftarrow Y \rightarrow S$.
1395   
1396    ALGORITHM:
1397   
1398    This is based on the model that arose from much discussion at Sage Days 4.
1399    Going up the tower of constructions of $R$ and $S$ (e.g. the reals
1400    come from the rationals come from the integers) try and find a
1401    common parent, and then try and fill in a lattice with these
1402    two towers as sides with the top as the common ancestor and
1403    the bottom will be the desired ring.
1404
1405    See the code for a specific worked-out example.
1406       
1407    EXAMPLES::
1408
1409        sage: from sage.categories.pushout import pushout_lattice
1410        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1411        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1412        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1413        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1414        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1415        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1416        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1417        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1418        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1419        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1420        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1421        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1422        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1423        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1424        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1425        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1426        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1427        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1428        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1429        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1430        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1431        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1432        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1433        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1434        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1435        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1436        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1437        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1438        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1439        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1440        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1441        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1442        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1443        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1444        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1445        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1446        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1447        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1448        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1449        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1450        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1451        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1452        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1453        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1454        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1455        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1456        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1457        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1458        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1459        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1460        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1461        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1462        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1463        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1464        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1465        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1466        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1467        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1468        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1469        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1470        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1471        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1472        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1473        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1474        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1475        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1476        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1477        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1478        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1479        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1480        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1481        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1482        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1483        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1484        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1485        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1486        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1487        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1488        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1489        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1490        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1491        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1492        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1493        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1494        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1495        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1496        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1497        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1498        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1499        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1500        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1501        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1502        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1503        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1504        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1505        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1506        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1507        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1508        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1509        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1510        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1511        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1512        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1513        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1514        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1515        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1516        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1517        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1518        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1519        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1520        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1521        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1522        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1523        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1524        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1525        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1526        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1527        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1528        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1529        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1530        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1531        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1532        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1533        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1534        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1535        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1536        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1537        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1538        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1539        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1540        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1541        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1542        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1543        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1544        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1545        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1546        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1547        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1548        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1549        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1550        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1551        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1552        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1553        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1554        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1555        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1556        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1557        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1558        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1559        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1560        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1561        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1562        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1563        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1564        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1565        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1566        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1567        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1568        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1569        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1570        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1571        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1572        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1573        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1574        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1575        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1576        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1577        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1578        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1579        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1580        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1581        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1582        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1583        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1584        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1585        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1586        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1587        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1588        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1589        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1590        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1591        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1592        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1593        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1594        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1595        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1596        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1597        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1598        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1599        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1600        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1601        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1602        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1603        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1604        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1605        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1606        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1607        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1608        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1609        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1610        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1611        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1612        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1613        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1614        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1615        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1616        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1617        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1618        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1619        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1620        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1621        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1622        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1623        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1624        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1625        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1626        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1627        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1628        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1629        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1630        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1631        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1632        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1633        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1634        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1635        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1636        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1637        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1638        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1639        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1640        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1641        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1642        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1643        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1644        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1645        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1646        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1647        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1648        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1649        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1650        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1651        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1652        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1653        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1654        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1655        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1656        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1657        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1658        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1659        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1660        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1661        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1662        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1663        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1664        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1665        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1666        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1667        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1668        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1669        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1670        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1671        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1672        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1673        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1674        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1675        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1676        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1677        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1678        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1679        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1680        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1681        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1682        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1683        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1684        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1685        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1686        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1687        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1688        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1689        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1690        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1691        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1692        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1693        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1694        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1695        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1696        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1697        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1698        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1699        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1700        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1701        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1702        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1703        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1704        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1705        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1706        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1707        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1708        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1709        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1710        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1711        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1712        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1713        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1714        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1715        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1716        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1717        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1718        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1719        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1720        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1721        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1722        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1723        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1724        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1725        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1726        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1727        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1728        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1729        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1730        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1731        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1732        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1733        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1734        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1735        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1736        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1737        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1738        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1739        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1740        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1741        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1742        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1743        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1744        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1745        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1746        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1747        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1748        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1749        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1750        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1751        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1752        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1753        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1754        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1755        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1756        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1757        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1758        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1759        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1760        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1761        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1762        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1763        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1764        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1765        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1766        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1767        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1768        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1769        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1770        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1771        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1772        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1773        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1774        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1775        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1776        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1777        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1778        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1779        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1780        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1781        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1782        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1783        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1784        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1785        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1786        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1787        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1788        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1789        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1790        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1791        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1792        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1793        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1794        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1795        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1796        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1797        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1798        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1799        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1800        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1801        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1802        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1803        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1804        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1805        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1806        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1807        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1808        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1809        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1810        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1811        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1812        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1813        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1814        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1815        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1816        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1817        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1818        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1819        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1820        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1821        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1822        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1823        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1824        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1825        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1826        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1827        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1828        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1829        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1830        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1831        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1832        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1833        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1834        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1835        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1836        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1837        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1838        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1839        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1840        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1841        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1842        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1843        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1844        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1845        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1846        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1847        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1848        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1849        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1850        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1851        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1852        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1853        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1854        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1855        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1856        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1857        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1858        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1859        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1860        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1861        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1862        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1863        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1864        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1865        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1866        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1867        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1868        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1869        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1870        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1871        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1872        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1873        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1874        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1875        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1876        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1877        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1878        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1879        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1880        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1881        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1882        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1883        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1884        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1885        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1886        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1887        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1888        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1889        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1890        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1891        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1892        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1893        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1894        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1895        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1896        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1897        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1898        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1899        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1900        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1901        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1902        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1903        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1904        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1905        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1906        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1907        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1908        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1909        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1910        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1911        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1912        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1913        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1914        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1915        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1916        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1917        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1918        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1919        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1920        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1921        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1922        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1923        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1924        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1925        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1926        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1927        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1928        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1929        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1930        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1931        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1932        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1933        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1934        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1935        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1936        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1937        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1938        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1939        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1940        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1941        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1942        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1943        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1944        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1945        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1946        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1947        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1948        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1949        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1950        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1951        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1952        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1953        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1954        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1955        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1956        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1957        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1958        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1959        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1960        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1961        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1962        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1963        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1964        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1965        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1966        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1967        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1968        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1969        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1970        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1971        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1972        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1973        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1974        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1975        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1976        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1977        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1978        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1979        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1980        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
1981    """