# Coercion via Construction Functors¶

class sage.categories.pushout.AlgebraicClosureFunctor

Algebraic Closure.

EXAMPLE:

sage: F = CDF.construction()[0]
sage: F(QQ)
Algebraic Field
sage: F(RR)
Complex Field with 53 bits of precision
sage: F(F(QQ)) is F(QQ)
True

merge(other)

Mathematically, Algebraic Closure subsumes Algebraic Extension. However, it seems that people do want to work with algebraic extensions of RR. Therefore, we do not merge with algebraic extension.

TEST:

sage: K.<a>=NumberField(x^3+x^2+1)
sage: CDF.construction()[0].merge(K.construction()[0]) is None
True
sage: CDF.construction()[0].merge(CDF.construction()[0])
AlgebraicClosureFunctor

class sage.categories.pushout.AlgebraicExtensionFunctor(polys, names, embeddings, cyclotomic=None, **kwds)

Algebraic extension (univariate polynomial ring modulo principal ideal).

EXAMPLE:

sage: K.<a> = NumberField(x^3+x^2+1)
sage: F = K.construction()[0]
sage: F(ZZ['t'])
Univariate Quotient Polynomial Ring in a over Univariate Polynomial Ring in t over Integer Ring with modulus a^3 + a^2 + 1


Note that, even if a field is algebraically closed, the algebraic extension will be constructed as the quotient of a univariate polynomial ring:

sage: F(CC)
Univariate Quotient Polynomial Ring in a over Complex Field with 53 bits of precision with modulus a^3 + a^2 + 1.00000000000000
sage: F(RR)
Univariate Quotient Polynomial Ring in a over Real Field with 53 bits of precision with modulus a^3 + a^2 + 1.00000000000000


Note that the construction functor of a number field applied to the integers returns an order (not necessarily maximal) of that field, similar to the behaviour of ZZ.extension(...):

sage: F(ZZ)
Order in Number Field in a with defining polynomial x^3 + x^2 + 1


This also holds for non-absolute number fields:

sage: K.<a,b> = NumberField([x^3+x^2+1,x^2+x+1])
sage: F = K.construction()[0]
sage: O = F(ZZ); O
Relative Order in Number Field in a with defining polynomial x^3 + x^2 + 1 over its base field


Unfortunately, the relative number field is not a unique parent:

sage: O.ambient() is K
False
sage: O.ambient() == K
True

expand()

Decompose the functor $$F$$ into sub-functors, whose product returns $$F$$.

EXAMPLES:

sage: P.<x> = QQ[]
sage: K.<a> = NumberField(x^3-5,embedding=0)
sage: L.<b> = K.extension(x^2+a)
sage: F,R = L.construction()
sage: prod(F.expand())(R) == L
True
sage: K = NumberField([x^2-2, x^2-3],'a')
sage: F, R = K.construction()
sage: F
AlgebraicExtensionFunctor
sage: L = F.expand(); L
[AlgebraicExtensionFunctor, AlgebraicExtensionFunctor]
sage: L[-1](QQ)
Number Field in a1 with defining polynomial x^2 - 3

merge(other)

Merging with another AlgebraicExtensionFunctor.

INPUT:

other – Construction Functor.

OUTPUT:

• If self==other, self is returned.
• If self and other are simple extensions and both provide an embedding, then it is tested whether one of the number fields provided by the functors coerces into the other; the functor associated with the target of the coercion is returned. Otherwise, the construction functor associated with the pushout of the codomains of the two embeddings is returned, provided that it is a number field.
• If these two extensions are defined by Conway polynomials over finite fields, merges them into a single extension of degree the lcm of the two degrees.
• Otherwise, None is returned.

REMARK:

Algebraic extension with embeddings currently only works when applied to the rational field. This is why we use the admittedly strange rule above for merging.

EXAMPLES:

The following demonstrate coercions for finite fields using Conway or pseudo-Conway polynomials:

sage: k = GF(3^2, conway=True, prefix='z'); a = k.gen()
sage: l = GF(3^3, conway=True, prefix='z'); b = l.gen()
sage: a + b # indirect doctest
z6^5 + 2*z6^4 + 2*z6^3 + z6^2 + 2*z6 + 1


Note that embeddings are compatible in lattices of such finite fields:

sage: m = GF(3^5, conway=True, prefix='z'); c = m.gen()
sage: (a+b)+c == a+(b+c) # indirect doctest
True
sage: from sage.categories.pushout import pushout
sage: n = pushout(k, l)
sage: o = pushout(l, m)
sage: q = pushout(n, o)
sage: q(o(b)) == q(n(b)) # indirect doctest
True


Coercion is also available for number fields:

sage: P.<x> = QQ[]
sage: L.<b> = NumberField(x^8-x^4+1, embedding=CDF.0)
sage: M1.<c1> = NumberField(x^2+x+1, embedding=b^4-1)
sage: M2.<c2> = NumberField(x^2+1, embedding=-b^6)
sage: M1.coerce_map_from(M2)
sage: M2.coerce_map_from(M1)
sage: c1+c2; parent(c1+c2)    #indirect doctest
-b^6 + b^4 - 1
Number Field in b with defining polynomial x^8 - x^4 + 1
sage: pushout(M1['x'],M2['x'])
Univariate Polynomial Ring in x over Number Field in b with defining polynomial x^8 - x^4 + 1


In the previous example, the number field L becomes the pushout of M1 and M2 since both are provided with an embedding into L, and since L is a number field. If two number fields are embedded into a field that is not a numberfield, no merging occurs:

sage: K.<a> = NumberField(x^3-2, embedding=CDF(1/2*I*2^(1/3)*sqrt(3) - 1/2*2^(1/3)))
sage: L.<b> = NumberField(x^6-2, embedding=1.1)
sage: L.coerce_map_from(K)
sage: K.coerce_map_from(L)
sage: pushout(K,L)
Traceback (most recent call last):
...
CoercionException: ('Ambiguous Base Extension', Number Field in a with defining polynomial x^3 - 2, Number Field in b with defining polynomial x^6 - 2)

class sage.categories.pushout.BlackBoxConstructionFunctor(box)

Construction functor obtained from any callable object.

EXAMPLES:

sage: from sage.categories.pushout import BlackBoxConstructionFunctor
sage: FG = BlackBoxConstructionFunctor(gap)
sage: FS = BlackBoxConstructionFunctor(singular)
sage: FG
BlackBoxConstructionFunctor
sage: FG(ZZ)
Integers
sage: FG(ZZ).parent()
Gap
sage: FS(QQ['t'])
//   characteristic : 0
//   number of vars : 1
//        block   1 : ordering lp
//                  : names    t
//        block   2 : ordering C
sage: FG == FS
False
True

class sage.categories.pushout.CompletionFunctor(p, prec, extras=None)

Completion of a ring with respect to a given prime (including infinity).

EXAMPLES:

sage: R = Zp(5)
sage: R
5-adic Ring with capped relative precision 20
sage: F1 = R.construction()[0]
sage: F1
Completion[5]
sage: F1(ZZ) is R
True
sage: F1(QQ)
5-adic Field with capped relative precision 20
sage: F2 = RR.construction()[0]
sage: F2
Completion[+Infinity]
sage: F2(QQ) is RR
True
sage: P.<x> = ZZ[]
sage: Px = P.completion(x) # currently the only implemented completion of P
sage: Px
Power Series Ring in x over Integer Ring
sage: F3 = Px.construction()[0]
sage: F3(GF(3)['x'])
Power Series Ring in x over Finite Field of size 3


TEST:

sage: R1.<a> = Zp(5,prec=20)[]
sage: R2 = Qp(5,prec=40)
sage: R2(1) + a
(1 + O(5^20))*a + (1 + O(5^40))
sage: 1/2 + a
(1 + O(5^20))*a + (3 + 2*5 + 2*5^2 + 2*5^3 + 2*5^4 + 2*5^5 + 2*5^6 + 2*5^7 + 2*5^8 + 2*5^9 + 2*5^10 + 2*5^11 + 2*5^12 + 2*5^13 + 2*5^14 + 2*5^15 + 2*5^16 + 2*5^17 + 2*5^18 + 2*5^19 + O(5^20))

commutes(other)

Completion commutes with fraction fields.

EXAMPLE:

sage: F1 = Qp(5).construction()[0]
sage: F2 = QQ.construction()[0]
sage: F1.commutes(F2)
True


TEST:

The fraction field R in the example below has no completion method. But completion commutes with the fraction field functor, and so it is tried internally whether applying the construction functors in opposite order works. It does:

sage: P.<x> = ZZ[]
sage: C = P.completion(x).construction()[0]
sage: R = FractionField(P)
sage: hasattr(R,'completion')
False
sage: C(R) is Frac(C(P))
True
sage: F = R.construction()[0]
sage: (C*F)(ZZ['x']) is (F*C)(ZZ['x'])
True


The following was fixed in trac ticket #15329 (it used to result in an infinite recursion):

sage: from sage.categories.pushout import pushout
sage: pushout(Qp(7),RLF)
Traceback (most recent call last):
...
CoercionException: ('Ambiguous Base Extension', 7-adic Field with capped relative precision 20, Real Lazy Field)

merge(other)

Two Completion functors are merged, if they are equal. If the precisions of both functors coincide, then a Completion functor is returned that results from updating the extras dictionary of self by other.extras. Otherwise, if the completion is at infinity then merging does not increase the set precision, and if the completion is at a finite prime, merging does not decrease the capped precision.

EXAMPLE:

sage: R1.<a> = Zp(5,prec=20)[]
sage: R2 = Qp(5,prec=40)
sage: R2(1)+a         # indirect doctest
(1 + O(5^20))*a + (1 + O(5^40))
sage: R3 = RealField(30)
sage: R4 = RealField(50)
sage: R3(1) + R4(1)   # indirect doctest
2.0000000
sage: (R3(1) + R4(1)).parent()
Real Field with 30 bits of precision


TESTS:

We check that #12353 has been resolved:

sage: RealIntervalField(53)(-1) > RR(1)
False
sage: RealIntervalField(54)(-1) > RR(1)
False
sage: RealIntervalField(54)(1) > RR(-1)
True
sage: RealIntervalField(53)(1) > RR(-1)
True


We check that various pushouts work:

sage: R0 = RealIntervalField(30)
sage: R1 = RealIntervalField(30, sci_not=True)
sage: R2 = RealIntervalField(53)
sage: R3 = RealIntervalField(53, sci_not = True)
sage: R4 = RealIntervalField(90)
sage: R5 = RealIntervalField(90, sci_not = True)
sage: R6 = RealField(30)
sage: R7 = RealField(30, sci_not=True)
sage: R8 = RealField(53, rnd = 'RNDD')
sage: R9 = RealField(53, sci_not = True, rnd = 'RNDZ')
sage: R10 = RealField(53, sci_not = True)
sage: R11 = RealField(90, sci_not = True, rnd = 'RNDZ')
sage: Rlist = [R0,R1,R2,R3,R4,R5,R6,R7,R8,R9,R10,R11]
sage: from sage.categories.pushout import pushout
sage: pushouts = [R0,R0,R0,R1,R0,R1,R0,R1,R0,R1,R1,R1,R1,R1,R1,R1,R1,R1,R1,R1,R1,R1,R1,R1,R0,R1,R2,R2,R2,R3,R0,R1,R2,R3,R3,R3,R1,R1,R3,R3,R3,R3,R1,R1,R3,R3,R3,R3,R0,R1,R2,R3,R4,R4,R0,R1,R2,R3,R3,R5,R1,R1,R3,R3,R5,R5,R1,R1,R3,R3,R3,R5,R0,R1,R0,R1,R0,R1,R6,R6,R6,R7,R7,R7,R1,R1,R1,R1,R1,R1,R7,R7,R7,R7,R7,R7,R0,R1,R2,R3,R2,R3,R6,R7,R8,R9,R10,R9,R1,R1,R3,R3,R3,R3,R7,R7,R9,R9,R10,R9,R1,R1,R3,R3,R3,R3,R7,R7,R10,R10,R10,R10,R1,R1,R3,R3,R5,R5,R7,R7,R9,R9,R10,R11]
sage: all([R is S for R, S in zip(pushouts, [pushout(a, b) for a in Rlist for b in Rlist])])
True

sage: P0 = ZpFM(5, 10)
sage: P1 = ZpFM(5, 20)
sage: P2 = ZpCR(5, 10)
sage: P3 = ZpCR(5, 20)
sage: P4 = ZpCA(5, 10)
sage: P5 = ZpCA(5, 20)
sage: P6 = Qp(5, 10)
sage: P7 = Qp(5, 20)
sage: Plist = [P2,P3,P4,P5,P6,P7]
sage: from sage.categories.pushout import pushout
sage: pushouts = [P2,P3,P4,P5,P6,P7,P3,P3,P5,P5,P7,P7,P4,P5,P4,P5,P6,P7,P5,P5,P5,P5,P7,P7,P6,P7,P6,P7,P6,P7,P7,P7,P7,P7,P7,P7]
sage: all([P is Q for P, Q in zip(pushouts, [pushout(a, b) for a in Plist for b in Plist])])
True

class sage.categories.pushout.CompositeConstructionFunctor(*args)

A Construction Functor composed by other Construction Functors.

INPUT:

F1, F2,...: A list of Construction Functors. The result is the composition F1 followed by F2 followed by ...

EXAMPLES:

sage: from sage.categories.pushout import CompositeConstructionFunctor
sage: F = CompositeConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0],QQ.construction()[0],ZZ['y'].construction()[0])
sage: F
Poly[y](FractionField(Poly[x](FractionField(...))))
True
sage: F == CompositeConstructionFunctor(*F.all)
True
sage: F(GF(2)['t'])
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)

expand()

Return expansion of a CompositeConstructionFunctor.

NOTE:

The product over the list of components, as returned by the expand() method, is equal to self.

EXAMPLES:

sage: from sage.categories.pushout import CompositeConstructionFunctor
sage: F = CompositeConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0],QQ.construction()[0],ZZ['y'].construction()[0])
sage: F
Poly[y](FractionField(Poly[x](FractionField(...))))
sage: prod(F.expand()) == F
True

class sage.categories.pushout.ConstructionFunctor

Base class for construction functors.

A construction functor is a functorial algebraic construction, such as the construction of a matrix ring over a given ring or the fraction field of a given ring.

In addition to the class Functor, construction functors provide rules for combining and merging constructions. This is an important part of Sage’s coercion model, namely the pushout of two constructions: When a polynomial p in a variable x with integer coefficients is added to a rational number q, then Sage finds that the parents ZZ['x'] and QQ are obtained from ZZ by applying a polynomial ring construction respectively the fraction field construction. Each construction functor has an attribute rank, and the rank of the polynomial ring construction is higher than the rank of the fraction field construction. This means that the pushout of QQ and ZZ['x'], and thus a common parent in which p and q can be added, is QQ['x'], since the construction functor with a lower rank is applied first.

sage: F1, R = QQ.construction()
sage: F1
FractionField
sage: R
Integer Ring
sage: F2, R = (ZZ['x']).construction()
sage: F2
Poly[x]
sage: R
Integer Ring
sage: F3 = F2.pushout(F1)
sage: F3
Poly[x](FractionField(...))
sage: F3(R)
Univariate Polynomial Ring in x over Rational Field
sage: from sage.categories.pushout import pushout
sage: P.<x> = ZZ[]
sage: pushout(QQ,P)
Univariate Polynomial Ring in x over Rational Field
sage: ((x+1) + 1/2).parent()
Univariate Polynomial Ring in x over Rational Field


When composing two construction functors, they are sometimes merged into one, as is the case in the Quotient construction:

sage: Q15, R = (ZZ.quo(15*ZZ)).construction()
sage: Q15
QuotientFunctor
sage: Q35, R = (ZZ.quo(35*ZZ)).construction()
sage: Q35
QuotientFunctor
sage: Q15.merge(Q35)
QuotientFunctor
sage: Q15.merge(Q35)(ZZ)
Ring of integers modulo 5


Functors can not only be applied to objects, but also to morphisms in the respective categories. For example:

sage: P.<x,y> = ZZ[]
sage: F = P.construction()[0]; F
MPoly[x,y]
sage: A.<a,b> = GF(5)[]
sage: f = A.hom([a+b,a-b],A)
sage: F(A)
Multivariate Polynomial Ring in x, y over Multivariate Polynomial Ring in a, b over Finite Field of size 5
sage: F(f)
Ring endomorphism of Multivariate Polynomial Ring in x, y over Multivariate Polynomial Ring in a, b over Finite Field of size 5
Defn: Induced from base ring by
Ring endomorphism of Multivariate Polynomial Ring in a, b over Finite Field of size 5
Defn: a |--> a + b
b |--> a - b
sage: F(f)(F(A)(x)*a)
(a + b)*x

commutes(other)

Determine whether self commutes with another construction functor.

NOTE:

By default, False is returned in all cases (even if the two functors are the same, since in this case merge() will apply anyway). So far there is no construction functor that overloads this method. Anyway, this method only becomes relevant if two construction functors have the same rank.

EXAMPLES:

sage: F = QQ.construction()[0]
sage: P = ZZ['t'].construction()[0]
sage: F.commutes(P)
False
sage: P.commutes(F)
False
sage: F.commutes(F)
False

expand()

Decompose self into a list of construction functors.

NOTE:

The default is to return the list only containing self.

EXAMPLE:

sage: F = QQ.construction()[0]
sage: F.expand()
[FractionField]
sage: Q = ZZ.quo(2).construction()[0]
sage: Q.expand()
[QuotientFunctor]
sage: P = ZZ['t'].construction()[0]
sage: FP = F*P
sage: FP.expand()
[FractionField, Poly[t]]

merge(other)

Merge self with another construction functor, or return None.

NOTE:

The default is to merge only if the two functors coincide. But this may be overloaded for subclasses, such as the quotient functor.

EXAMPLES:

sage: F = QQ.construction()[0]
sage: P = ZZ['t'].construction()[0]
sage: F.merge(F)
FractionField
sage: F.merge(P)
sage: P.merge(F)
sage: P.merge(P)
Poly[t]

pushout(other)

Composition of two construction functors, ordered by their ranks.

NOTE:

• This method seems not to be used in the coercion model.
• By default, the functor with smaller rank is applied first.

TESTS:

sage: F = QQ.construction()[0]
sage: P = ZZ['t'].construction()[0]
sage: F.pushout(P)
Poly[t](FractionField(...))
sage: P.pushout(F)
Poly[t](FractionField(...))

class sage.categories.pushout.FractionField

Construction functor for fraction fields.

EXAMPLE:

sage: F = QQ.construction()[0]
sage: F
FractionField
sage: F.domain()
Category of integral domains
sage: F.codomain()
Category of fields
sage: F(GF(5)) is GF(5)
True
sage: F(ZZ['t'])
Fraction Field of Univariate Polynomial Ring in t over Integer Ring
sage: P.<x,y> = QQ[]
sage: f = P.hom([x+2*y,3*x-y],P)
sage: F(f)
Ring endomorphism of Fraction Field of Multivariate Polynomial Ring in x, y over Rational Field
Defn: x |--> x + 2*y
y |--> 3*x - y
sage: F(f)(1/x)
1/(x + 2*y)
True

class sage.categories.pushout.IdentityConstructionFunctor

A construction functor that is the identity functor.

TESTS:

sage: from sage.categories.pushout import IdentityConstructionFunctor
sage: I = IdentityConstructionFunctor()
sage: I(RR) is RR
True
True

class sage.categories.pushout.InfinitePolynomialFunctor(gens, order, implementation)

A Construction Functor for Infinite Polynomial Rings (see infinite_polynomial_ring).

AUTHOR:

– Simon King

This construction functor is used to provide uniqueness of infinite polynomial rings as parent structures. As usual, the construction functor allows for constructing pushouts.

Another purpose is to avoid name conflicts of variables of the to-be-constructed infinite polynomial ring with variables of the base ring, and moreover to keep the internal structure of an Infinite Polynomial Ring as simple as possible: If variables $$v_1,...,v_n$$ of the given base ring generate an ordered sub-monoid of the monomials of the ambient Infinite Polynomial Ring, then they are removed from the base ring and merged with the generators of the ambient ring. However, if the orders don’t match, an error is raised, since there was a name conflict without merging.

EXAMPLES:

sage: A.<a,b> = InfinitePolynomialRing(ZZ['t'])
sage: A.construction()
[InfPoly{[a,b], "lex", "dense"},
Univariate Polynomial Ring in t over Integer Ring]
sage: type(_[0])
<class 'sage.categories.pushout.InfinitePolynomialFunctor'>
sage: B.<x,y,a_3,a_1> = PolynomialRing(QQ, order='lex')
sage: B.construction()
(MPoly[x,y,a_3,a_1], Rational Field)
sage: A.construction()[0]*B.construction()[0]
InfPoly{[a,b], "lex", "dense"}(MPoly[x,y](...))


Apparently the variables $$a_1,a_3$$ of the polynomial ring are merged with the variables $$a_0, a_1, a_2, ...$$ of the infinite polynomial ring; indeed, they form an ordered sub-structure. However, if the polynomial ring was given a different ordering, merging would not be allowed, resulting in a name conflict:

sage: A.construction()[0]*PolynomialRing(QQ,names=['x','y','a_3','a_1']).construction()[0]
Traceback (most recent call last):
...
CoercionException: Incompatible term orders lex, degrevlex


In an infinite polynomial ring with generator $$a_\ast$$, the variable $$a_3$$ will always be greater than the variable $$a_1$$. Hence, the orders are incompatible in the next example as well:

sage: A.construction()[0]*PolynomialRing(QQ,names=['x','y','a_1','a_3'], order='lex').construction()[0]
Traceback (most recent call last):
...
CoercionException: Overlapping variables (('a', 'b'),['a_1', 'a_3']) are incompatible


Another requirement is that after merging the order of the remaining variables must be unique. This is not the case in the following example, since it is not clear whether the variables $$x,y$$ should be greater or smaller than the variables $$b_\ast$$:

sage: A.construction()[0]*PolynomialRing(QQ,names=['a_3','a_1','x','y'], order='lex').construction()[0]
Traceback (most recent call last):
...
CoercionException: Overlapping variables (('a', 'b'),['a_3', 'a_1']) are incompatible


Since the construction functors are actually used to construct infinite polynomial rings, the following result is no surprise:

sage: C.<a,b> = InfinitePolynomialRing(B); C
Infinite polynomial ring in a, b over Multivariate Polynomial Ring in x, y over Rational Field


There is also an overlap in the next example:

sage: X.<w,x,y> = InfinitePolynomialRing(ZZ)
sage: Y.<x,y,z> = InfinitePolynomialRing(QQ)


$$X$$ and $$Y$$ have an overlapping generators $$x_\ast, y_\ast$$. Since the default lexicographic order is used in both rings, it gives rise to isomorphic sub-monoids in both $$X$$ and $$Y$$. They are merged in the pushout, which also yields a common parent for doing arithmetic:

sage: P = sage.categories.pushout.pushout(Y,X); P
Infinite polynomial ring in w, x, y, z over Rational Field
sage: w[2]+z[3]
w_2 + z_3
sage: _.parent() is P
True

expand()

Decompose the functor $$F$$ into sub-functors, whose product returns $$F$$.

EXAMPLES:

sage: F = InfinitePolynomialRing(QQ, ['x','y'],order='degrevlex').construction()[0]; F
InfPoly{[x,y], "degrevlex", "dense"}
sage: F.expand()
[InfPoly{[y], "degrevlex", "dense"}, InfPoly{[x], "degrevlex", "dense"}]
sage: F = InfinitePolynomialRing(QQ, ['x','y','z'],order='degrevlex').construction()[0]; F
InfPoly{[x,y,z], "degrevlex", "dense"}
sage: F.expand()
[InfPoly{[z], "degrevlex", "dense"},
InfPoly{[y], "degrevlex", "dense"},
InfPoly{[x], "degrevlex", "dense"}]
sage: prod(F.expand())==F
True

merge(other)

Merge two construction functors of infinite polynomial rings, regardless of monomial order and implementation.

The purpose is to have a pushout (and thus, arithmetic) even in cases when the parents are isomorphic as rings, but not as ordered rings.

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ,implementation='sparse')
sage: Y.<x,y> = InfinitePolynomialRing(QQ,order='degrevlex')
sage: X.construction()
[InfPoly{[x,y], "lex", "sparse"}, Rational Field]
sage: Y.construction()
[InfPoly{[x,y], "degrevlex", "dense"}, Rational Field]
sage: Y.construction()[0].merge(Y.construction()[0])
InfPoly{[x,y], "degrevlex", "dense"}
sage: y[3] + X(x[2])
x_2 + y_3
sage: _.parent().construction()
[InfPoly{[x,y], "degrevlex", "dense"}, Rational Field]

class sage.categories.pushout.LaurentPolynomialFunctor(var, multi_variate=False)

Construction functor for Laurent polynomial rings.

EXAMPLES:

sage: L.<t> = LaurentPolynomialRing(ZZ)
sage: F = L.construction()[0]
sage: F
LaurentPolynomialFunctor
sage: F(QQ)
Univariate Laurent Polynomial Ring in t over Rational Field
sage: K.<x> = LaurentPolynomialRing(ZZ)
sage: F(K)
Univariate Laurent Polynomial Ring in t over Univariate Laurent Polynomial Ring in x over Integer Ring
sage: P.<x,y> = ZZ[]
sage: f = P.hom([x+2*y,3*x-y],P)
sage: F(f)
Ring endomorphism of Univariate Laurent Polynomial Ring in t over Multivariate Polynomial Ring in x, y over Integer Ring
Defn: Induced from base ring by
Ring endomorphism of Multivariate Polynomial Ring in x, y over Integer Ring
Defn: x |--> x + 2*y
y |--> 3*x - y
sage: F(f)(x*F(P).gen()^-2+y*F(P).gen()^3)
(3*x - y)*t^3 + (x + 2*y)*t^-2

merge(other)

Two Laurent polynomial construction functors merge if the variable names coincide. The result is multivariate if one of the arguments is multivariate.

EXAMPLE:

sage: from sage.categories.pushout import LaurentPolynomialFunctor
sage: F1 = LaurentPolynomialFunctor('t')
sage: F2 = LaurentPolynomialFunctor('t', multi_variate=True)
sage: F1.merge(F2)
LaurentPolynomialFunctor
sage: F1.merge(F2)(LaurentPolynomialRing(GF(2),'a'))
Multivariate Laurent Polynomial Ring in a, t over Finite Field of size 2
sage: F1.merge(F1)(LaurentPolynomialRing(GF(2),'a'))
Univariate Laurent Polynomial Ring in t over Univariate Laurent Polynomial Ring in a over Finite Field of size 2

class sage.categories.pushout.MatrixFunctor(nrows, ncols, is_sparse=False)

A construction functor for matrices over rings.

EXAMPLES:

sage: MS = MatrixSpace(ZZ,2, 3)
sage: F = MS.construction()[0]; F
MatrixFunctor
sage: MS = MatrixSpace(ZZ,2)
sage: F = MS.construction()[0]; F
MatrixFunctor
sage: P.<x,y> = QQ[]
sage: R = F(P); R
Full MatrixSpace of 2 by 2 dense matrices over Multivariate Polynomial Ring in x, y over Rational Field
sage: f = P.hom([x+y,x-y],P); F(f)
Ring endomorphism of Full MatrixSpace of 2 by 2 dense matrices over Multivariate Polynomial Ring in x, y over Rational Field
Defn: Induced from base ring by
Ring endomorphism of Multivariate Polynomial Ring in x, y over Rational Field
Defn: x |--> x + y
y |--> x - y
sage: M = R([x,y,x*y,x+y])
sage: F(f)(M)
[    x + y     x - y]
[x^2 - y^2       2*x]

merge(other)

Merging is only happening if both functors are matrix functors of the same dimension. The result is sparse if and only if both given functors are sparse.

EXAMPLE:

sage: F1 = MatrixSpace(ZZ,2,2).construction()[0]
sage: F2 = MatrixSpace(ZZ,2,3).construction()[0]
sage: F3 = MatrixSpace(ZZ,2,2,sparse=True).construction()[0]
sage: F1.merge(F2)
sage: F1.merge(F3)
MatrixFunctor
sage: F13 = F1.merge(F3)
sage: F13.is_sparse
False
sage: F1.is_sparse
False
sage: F3.is_sparse
True
sage: F3.merge(F3).is_sparse
True

class sage.categories.pushout.MultiPolynomialFunctor(vars, term_order)

A constructor for multivariate polynomial rings.

EXAMPLES:

sage: P.<x,y> = ZZ[]
sage: F = P.construction()[0]; F
MPoly[x,y]
sage: A.<a,b> = GF(5)[]
sage: F(A)
Multivariate Polynomial Ring in x, y over Multivariate Polynomial Ring in a, b over Finite Field of size 5
sage: f = A.hom([a+b,a-b],A)
sage: F(f)
Ring endomorphism of Multivariate Polynomial Ring in x, y over Multivariate Polynomial Ring in a, b over Finite Field of size 5
Defn: Induced from base ring by
Ring endomorphism of Multivariate Polynomial Ring in a, b over Finite Field of size 5
Defn: a |--> a + b
b |--> a - b
sage: F(f)(F(A)(x)*a)
(a + b)*x

expand()

Decompose self into a list of construction functors.

EXAMPLES:

sage: F = QQ['x,y,z,t'].construction()[0]; F
MPoly[x,y,z,t]
sage: F.expand()
[MPoly[t], MPoly[z], MPoly[y], MPoly[x]]


Now an actual use case:

sage: R.<x,y,z> = ZZ[]
sage: S.<z,t> = QQ[]
sage: x+t
x + t
sage: parent(x+t)
Multivariate Polynomial Ring in x, y, z, t over Rational Field
sage: T.<y,s> = QQ[]
sage: x + s
Traceback (most recent call last):
...
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'
sage: R = PolynomialRing(ZZ, 'x', 500)
sage: S = PolynomialRing(GF(5), 'x', 200)
sage: R.gen(0) + S.gen(0)
2*x0

merge(other)

Merge self with another construction functor, or return None.

EXAMPLES:

sage: F = sage.categories.pushout.MultiPolynomialFunctor(['x','y'], None)
sage: G = sage.categories.pushout.MultiPolynomialFunctor(['t'], None)
sage: F.merge(G) is None
True
sage: F.merge(F)
MPoly[x,y]

class sage.categories.pushout.PermutationGroupFunctor(gens, domain)

EXAMPLES:

sage: from sage.categories.pushout import PermutationGroupFunctor
sage: PF = PermutationGroupFunctor([PermutationGroupElement([(1,2)])], [1,2]); PF
PermutationGroupFunctor[(1,2)]

gens()

EXAMPLES:

sage: P1 = PermutationGroup([[(1,2)]])
sage: PF, P = P1.construction()
sage: PF.gens()
[(1,2)]

merge(other)

Merge self with another construction functor, or return None.

EXAMPLES:

sage: P1 = PermutationGroup([[(1,2)]])
sage: PF1, P = P1.construction()
sage: P2 = PermutationGroup([[(1,3)]])
sage: PF2, P = P2.construction()
sage: PF1.merge(PF2)
PermutationGroupFunctor[(1,2), (1,3)]

class sage.categories.pushout.PolynomialFunctor(var, multi_variate=False, sparse=False)

Construction functor for univariate polynomial rings.

EXAMPLE:

sage: P = ZZ['t'].construction()[0]
sage: P(GF(3))
Univariate Polynomial Ring in t over Finite Field of size 3
True
sage: R.<x,y> = GF(5)[]
sage: f = R.hom([x+2*y,3*x-y],R)
sage: P(f)((x+y)*P(R).0)
(-x + y)*t


By trac ticket #9944, the construction functor distinguishes sparse and dense polynomial rings. Before, the following example failed:

sage: R.<x> = PolynomialRing(GF(5), sparse=True)
sage: F,B = R.construction()
sage: F(B) is R
True
sage: S.<x> = PolynomialRing(ZZ)
sage: R.has_coerce_map_from(S)
False
sage: S.has_coerce_map_from(R)
False
sage: S.0 + R.0
2*x
sage: (S.0 + R.0).parent()
Univariate Polynomial Ring in x over Finite Field of size 5
sage: (S.0 + R.0).parent().is_sparse()
False

merge(other)

Merge self with another construction functor, or return None.

NOTE:

Internally, the merging is delegated to the merging of multipolynomial construction functors. But in effect, this does the same as the default implementation, that returns None unless the to-be-merged functors coincide.

EXAMPLE:

sage: P = ZZ['x'].construction()[0]
sage: Q = ZZ['y','x'].construction()[0]
sage: P.merge(Q)
sage: P.merge(P) is P
True

class sage.categories.pushout.QuotientFunctor(I, names=None, as_field=False)

Construction functor for quotient rings.

NOTE:

The functor keeps track of variable names.

EXAMPLE:

sage: P.<x,y> = ZZ[]
sage: Q = P.quo([x^2+y^2]*P)
sage: F = Q.construction()[0]
sage: F(QQ['x','y'])
Quotient of Multivariate Polynomial Ring in x, y over Rational Field by the ideal (x^2 + y^2)
sage: F(QQ['x','y']) == QQ['x','y'].quo([x^2+y^2]*QQ['x','y'])
True
sage: F(QQ['x','y','z'])
Traceback (most recent call last):
...
CoercionException: Can not apply this quotient functor to Multivariate Polynomial Ring in x, y, z over Rational Field
sage: F(QQ['y','z'])
Traceback (most recent call last):
...
TypeError: Could not find a mapping of the passed element to this ring.

merge(other)

Two quotient functors with coinciding names are merged by taking the gcd of their moduli.

EXAMPLE:

sage: P.<x> = QQ[]
sage: Q1 = P.quo([(x^2+1)^2*(x^2-3)])
sage: Q2 = P.quo([(x^2+1)^2*(x^5+3)])
sage: from sage.categories.pushout import pushout
sage: pushout(Q1,Q2)    # indirect doctest
Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^4 + 2*x^2 + 1


The following was fixed in trac ticket #8800:

sage: pushout(GF(5), Integers(5))
Finite Field of size 5

class sage.categories.pushout.SubspaceFunctor(basis)

Constructing a subspace of an ambient free module, given by a basis.

NOTE:

This construction functor keeps track of the basis. It can only be applied to free modules into which this basis coerces.

EXAMPLES:

sage: M = ZZ^3
sage: S = M.submodule([(1,2,3),(4,5,6)]); S
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[1 2 3]
[0 3 6]
sage: F = S.construction()[0]
sage: F(GF(2)^3)
Vector space of degree 3 and dimension 2 over Finite Field of size 2
User basis matrix:
[1 0 1]
[0 1 0]

merge(other)

Two Subspace Functors are merged into a construction functor of the sum of two subspaces.

EXAMPLE:

sage: M = GF(5)^3
sage: S1 = M.submodule([(1,2,3),(4,5,6)])
sage: S2 = M.submodule([(2,2,3)])
sage: F1 = S1.construction()[0]
sage: F2 = S2.construction()[0]
sage: F1.merge(F2)
SubspaceFunctor
sage: F1.merge(F2)(GF(5)^3) == S1+S2
True
sage: F1.merge(F2)(GF(5)['t']^3)
Free module of degree 3 and rank 3 over Univariate Polynomial Ring in t over Finite Field of size 5
User basis matrix:
[1 0 0]
[0 1 0]
[0 0 1]


TEST:

sage: P.<t> = ZZ[]
sage: S1 = (ZZ^3).submodule([(1,2,3),(4,5,6)])
sage: S2 = (Frac(P)^3).submodule([(t,t^2,t^3+1),(4*t,0,1)])
sage: v = S1([0,3,6]) + S2([2,0,1/(2*t)]); v   # indirect doctest
(2, 3, (12*t + 1)/(2*t))
sage: v.parent()
Vector space of degree 3 and dimension 3 over Fraction Field of Univariate Polynomial Ring in t over Integer Ring
User basis matrix:
[1 0 0]
[0 1 0]
[0 0 1]

class sage.categories.pushout.VectorFunctor(n, is_sparse=False, inner_product_matrix=None)

EXAMPLE:

sage: F = (ZZ^3).construction()[0]
sage: F
VectorFunctor
sage: F(GF(2)['t'])
Ambient free module of rank 3 over the principal ideal domain Univariate Polynomial Ring in t over Finite Field of size 2 (using NTL)

merge(other)

Two constructors of free modules merge, if the module ranks coincide. If both have explicitly given inner product matrices, they must coincide as well.

EXAMPLE:

Two modules without explicitly given inner product allow coercion:

sage: M1 = QQ^3
sage: P.<t> = ZZ[]
sage: M2 = FreeModule(P,3)
sage: M1([1,1/2,1/3]) + M2([t,t^2+t,3])     # indirect doctest
(t + 1, t^2 + t + 1/2, 10/3)


If only one summand has an explicit inner product, the result will be provided with it:

sage: M3 = FreeModule(P,3, inner_product_matrix = Matrix(3,3,range(9)))
sage: M1([1,1/2,1/3]) + M3([t,t^2+t,3])
(t + 1, t^2 + t + 1/2, 10/3)
sage: (M1([1,1/2,1/3]) + M3([t,t^2+t,3])).parent().inner_product_matrix()
[0 1 2]
[3 4 5]
[6 7 8]


If both summands have an explicit inner product (even if it is the standard inner product), then the products must coincide. The only difference between M1 and M4 in the following example is the fact that the default inner product was explicitly requested for M4. It is therefore not possible to coerce with a different inner product:

sage: M4 = FreeModule(QQ,3, inner_product_matrix = Matrix(3,3,1))
sage: M4 == M1
True
sage: M4.inner_product_matrix() == M1.inner_product_matrix()
True
sage: M4([1,1/2,1/3]) + M3([t,t^2+t,3])      # indirect doctest
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for '+': 'Ambient quadratic space of dimension 3 over Rational Field
Inner product matrix:
[1 0 0]
[0 1 0]
[0 0 1]' and 'Ambient free quadratic module of rank 3 over the integral domain Univariate Polynomial Ring in t over Integer Ring
Inner product matrix:
[0 1 2]
[3 4 5]
[6 7 8]'

sage.categories.pushout.construction_tower(R)

An auxiliary function that is used in pushout() and pushout_lattice().

INPUT:

An object

OUTPUT:

A constructive description of the object from scratch, by a list of pairs of a construction functor and an object to which the construction functor is to be applied. The first pair is formed by None and the given object.

EXAMPLE:

sage: from sage.categories.pushout import construction_tower
sage: construction_tower(MatrixSpace(FractionField(QQ['t']),2))
[(None, Full MatrixSpace of 2 by 2 dense matrices over Fraction Field of Univariate Polynomial Ring in t over Rational Field), (MatrixFunctor, Fraction Field of Univariate Polynomial Ring in t over Rational Field), (FractionField, Univariate Polynomial Ring in t over Rational Field), (Poly[t], Rational Field), (FractionField, Integer Ring)]

sage.categories.pushout.pushout(R, S)

Given a pair of Objects R and S, try and construct a reasonable object Y and return maps such that canonically $$R \leftarrow Y \rightarrow S$$.

ALGORITHM:

This incorporates the idea of functors discussed Sage Days 4. Every object R can be viewed as an initial object and a series of functors (e.g. polynomial, quotient, extension, completion, vector/matrix, etc.). Call the series of increasingly-simple rings (with the associated functors) the “tower” of R. The construction method is used to create the tower.

Given two objects R and S, try and find a common initial object Z. If the towers of R and S meet, let Z be their join. Otherwise, see if the top of one coerces naturally into the other.

Now we have an initial object and two ordered lists of functors to apply. We wish to merge these in an unambiguous order, popping elements off the top of one or the other tower as we apply them to Z.

• If the functors are distinct types, there is an absolute ordering given by the rank attribute. Use this.
• Otherwise:
• If the tops are equal, we (try to) merge them.
• If exactly one occurs lower in the other tower we may unambiguously apply the other (hoping for a later merge).
• If the tops commute, we can apply either first.
• Otherwise fail due to ambiguity.

EXAMPLES:

Here our “towers” are $$R = Complete_7(Frac(\ZZ))$$ and $$Frac(Poly_x(\ZZ))$$, which give us $$Frac(Poly_x(Complete_7(Frac(\ZZ))))$$:

sage: from sage.categories.pushout import pushout
sage: pushout(Qp(7), Frac(ZZ['x']))
Fraction Field of Univariate Polynomial Ring in x over 7-adic Field with capped relative precision 20


Note we get the same thing with

sage: pushout(Zp(7), Frac(QQ['x']))
Fraction Field of Univariate Polynomial Ring in x over 7-adic Field with capped relative precision 20
sage: pushout(Zp(7)['x'], Frac(QQ['x']))
Fraction Field of Univariate Polynomial Ring in x over 7-adic Field with capped relative precision 20


Note that polynomial variable ordering must be unambiguously determined.

sage: pushout(ZZ['x,y,z'], QQ['w,z,t'])
Traceback (most recent call last):
...
CoercionException: ('Ambiguous Base Extension', Multivariate Polynomial Ring in x, y, z over Integer Ring, Multivariate Polynomial Ring in w, z, t over Rational Field)
sage: pushout(ZZ['x,y,z'], QQ['w,x,z,t'])
Multivariate Polynomial Ring in w, x, y, z, t over Rational Field


Some other examples:

sage: pushout(Zp(7)['y'], Frac(QQ['t'])['x,y,z'])
Multivariate Polynomial Ring in x, y, z over Fraction Field of Univariate Polynomial Ring in t over 7-adic Field with capped relative precision 20
sage: pushout(ZZ['x,y,z'], Frac(ZZ['x'])['y'])
Multivariate Polynomial Ring in y, z over Fraction Field of Univariate Polynomial Ring in x over Integer Ring
sage: pushout(MatrixSpace(RDF, 2, 2), Frac(ZZ['x']))
Full MatrixSpace of 2 by 2 dense matrices over Fraction Field of Univariate Polynomial Ring in x over Real Double Field
sage: pushout(ZZ, MatrixSpace(ZZ[['x']], 3, 3))
Full MatrixSpace of 3 by 3 dense matrices over Power Series Ring in x over Integer Ring
sage: pushout(QQ['x,y'], ZZ[['x']])
Univariate Polynomial Ring in y over Power Series Ring in x over Rational Field
sage: pushout(Frac(ZZ['x']), QQ[['x']])
Laurent Series Ring in x over Rational Field


AUTHORS:

sage.categories.pushout.pushout_lattice(R, S)

Given a pair of Objects $$R$$ and $$S$$, try and construct a reasonable object $$Y$$ and return maps such that canonically $$R \leftarrow Y \rightarrow S$$.

ALGORITHM:

This is based on the model that arose from much discussion at Sage Days 4. Going up the tower of constructions of $$R$$ and $$S$$ (e.g. the reals come from the rationals come from the integers) try and find a common parent, and then try and fill in a lattice with these two towers as sides with the top as the common ancestor and the bottom will be the desired ring.

See the code for a specific worked-out example.

EXAMPLES:

sage: from sage.categories.pushout import pushout_lattice
sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
sage: A.codomain()
Fraction Field of Univariate Polynomial Ring in x over 7-adic Field with capped relative precision 20
sage: A.codomain() is B.codomain()
True
sage: A, B = pushout_lattice(ZZ, MatrixSpace(ZZ[['x']], 3, 3))
sage: B
Identity endomorphism of Full MatrixSpace of 3 by 3 dense matrices over Power Series Ring in x over Integer Ring


AUTHOR:

sage.categories.pushout.type_to_parent(P)

An auxiliary function that is used in pushout().

INPUT:

A type

OUTPUT:

A Sage parent structure corresponding to the given type

TEST:

sage: from sage.categories.pushout import type_to_parent
sage: type_to_parent(int)
Integer Ring
sage: type_to_parent(float)
Real Double Field
sage: type_to_parent(complex)
Complex Double Field
sage: type_to_parent(list)
Traceback (most recent call last):
...
TypeError: Not a scalar type.


Functors

#### Next topic

Covariant Functorial Constructions