Sage Reference Manual: Coercion

Release 9.0

The Sage Development Team

Jan 01, 2020

 CONTENTS

1 Preliminaries 1
1.1 What is coercion all about? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Parents and Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Maps between Parents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Basic Arithmetic Rules 5

3 How to Implement 7
3.1 Methods to implement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Provided Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Discovering new parents 13

5 Modules 15
5.1 The coercion model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.2 Coerce actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3 Coerce maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.4 Coercion via construction functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.5 Group, ring, etc. actions on objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.6 Containers for storing coercion data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.7 Exceptions raised by the coercion model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6 Indices and Tables 73

Python Module Index 75

Index 77

i
ii
 CHAPTER

ONE

PRELIMINARIES

1.1 What is coercion all about?

The primary goal of coercion is to be able to transparently do arithmetic, comparisons, etc. between elements of
distinct sets.
As a concrete example, when one writes 1 + 1/2 one wants to perform arithmetic on the operands as rational numbers,
despite the left being an integer. This makes sense given the obvious and natural inclusion of the integers into the
rational numbers. The goal of the coercion system is to facilitate this (and more complicated arithmetic) without
having to explicitly map everything over into the same domain, and at the same time being strict enough to not resolve
ambiguity or accept nonsense. Here are some examples:
sage: 1 + 1/2
3/2
sage: R.<x,y> = ZZ[]
sage: R
Multivariate Polynomial Ring in x, y over Integer Ring
sage: parent(x)
Multivariate Polynomial Ring in x, y over Integer Ring
sage: parent(1/3)
Rational Field
sage: x+1/3
x + 1/3
sage: parent(x+1/3)
Multivariate Polynomial Ring in x, y over Rational Field

sage: GF(5)(1) + CC(I)

Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for +: 'Finite Field of size 5' and 'Complex
˓→Field with 53 bits of precision'

1.2 Parents and Elements

Parents are objects in concrete categories, and Elements are their members. Parents are first-class objects. Most things
in Sage are either parents or have a parent. Typically whenever one sees the word Parent one can think Set. Here are
some examples:
sage: parent(1)
Integer Ring
sage: parent(1) is ZZ
(continues on next page)

1
Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

True
sage: ZZ
Integer Ring
sage: parent(1.50000000000000000000000000000000000)
Real Field with 120 bits of precision
sage: parent(x)
Symbolic Ring
sage: x^sin(x)
x^sin(x)
sage: R.<t> = Qp(5)[]
sage: f = t^3-5; f
(1 + O(5^20))*t^3 + 4*5 + 4*5^2 + 4*5^3 + 4*5^4 + 4*5^5 + 4*5^6 + 4*5^7 + 4*5^8 + 4*5^
˓→9 + 4*5^10 + 4*5^11 + 4*5^12 + 4*5^13 + 4*5^14 + 4*5^15 + 4*5^16 + 4*5^17 + 4*5^18

˓→+ 4*5^19 + 4*5^20 + O(5^21)

sage: parent(f)
Univariate Polynomial Ring in t over 5-adic Field with capped relative precision 20
sage: f = EllipticCurve('37a').lseries().taylor_series(10); f # abs tol 1e-14
0.997997869801216 + 0.00140712894524925*z - 0.000498127610960097*z^2 + 0.
˓→000118835596665956*z^3 - 0.0000215906522442708*z^4 + (3.20363155418421e-6)*z^5 +

˓→O(z^6) # 32-bit
0.997997869801216 + 0.00140712894524925*z - 0.000498127610960097*z^2 + 0.
˓→000118835596665956*z^3 - 0.0000215906522442708*z^4 + (3.20363155418427e-6)*z^5 +

˓→O(z^6) # 64-bit
sage: parent(f)
Power Series Ring in z over Complex Field with 53 bits of precision

There is an important distinction between Parents and types:

sage: a = GF(5).random_element()
sage: b = GF(7).random_element()
sage: type(a)
<type '[Link].finite_rings.integer_mod.IntegerMod_int'>
sage: type(b)
<type '[Link].finite_rings.integer_mod.IntegerMod_int'>
sage: type(a) == type(b)
True
sage: parent(a)
Finite Field of size 5
sage: parent(a) == parent(b)
False

However, non-Sage objects do not really have parents, but we still want to be able to reason with them, so their type is
used instead:

sage: a = int(10)
sage: parent(a)
<... 'int'>

In fact, under the hood, a special kind of parent “The set of all Python objects of class T” is used in these cases.
Note that parents are not always as tight as possible.

sage: parent(1/2)
Rational Field
sage: parent(2/1)
Rational Field

2 Chapter 1. Preliminaries
 Sage Reference Manual: Coercion, Release 9.0

1.3 Maps between Parents

Many parents come with maps to and from other parents.

Sage makes a distinction between being able to convert between various parents, and coerce between them. Conver-
sion is explicit and tries to make sense of an object in the target domain if at all possible. It is invoked by calling:

sage: ZZ(5)
5
sage: ZZ(10/5)
2
sage: QQ(10)
10
sage: parent(QQ(10))
Rational Field
sage: a = GF(5)(2); a
2
sage: parent(a)
Finite Field of size 5
sage: parent(ZZ(a))
Integer Ring
sage: GF(71)(1/5)
57
sage: ZZ(1/2)
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer

Conversions need not be canonical (they may for example involve a choice of lift) or even make sense mathematically
(e.g. constructions of some kind).

sage: ZZ("123")
123
sage: ZZ(GF(5)(14))
4
sage: ZZ['x']([4,3,2,1])
x^3 + 2*x^2 + 3*x + 4
sage: a = Qp(5, 10)(1/3); a
2 + 3*5 + 5^2 + 3*5^3 + 5^4 + 3*5^5 + 5^6 + 3*5^7 + 5^8 + 3*5^9 + O(5^10)
sage: ZZ(a)
6510417

On the other hand, Sage has the notion of a coercion, which is a canonical morphism (occasionally up to a conven-
tional choice made by developers) between parents. A coercion from one parent to another must be defined on the
whole domain, and always succeeds. As it may be invoked implicitly, it should be obvious and natural (in both the
mathematically rigorous and colloquial sense of the word). Up to inescapable rounding issues that arise with inexact
representations, these coercion morphisms should all commute. In particular, if there are coercion maps 𝐴 → 𝐵 and
𝐵 → 𝐴, then their composites must be the identity maps.
Coercions can be discovered via the Parent.has_coerce_map_from() method, and if needed explicitly in-
voked with the [Link]() method:

sage: QQ.has_coerce_map_from(ZZ)
True
sage: QQ.has_coerce_map_from(RR)
False
sage: ZZ['x'].has_coerce_map_from(QQ)
(continues on next page)

1.3. Maps between Parents 3

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

False
sage: ZZ['x'].has_coerce_map_from(ZZ)
True
sage: ZZ['x'].coerce(5)
5
sage: ZZ['x'].coerce(5).parent()
Univariate Polynomial Ring in x over Integer Ring
sage: ZZ['x'].coerce(5/1)
Traceback (most recent call last):
...
TypeError: no canonical coercion from Rational Field to Univariate Polynomial Ring in
˓→x over Integer Ring

4 Chapter 1. Preliminaries
 CHAPTER

TWO

BASIC ARITHMETIC RULES

Suppose we want to add two element, a and b, whose parents are A and B respectively. When we type a+b then
1. If A is B, call a._add_(b)
2. If there is a coercion 𝜑 : 𝐵 → 𝐴, call a._add_( 𝜑 (b))
3. If there is a coercion 𝜑 : 𝐴 → 𝐵, call 𝜑 (a)._add_(b)
4. Look for 𝑍 such that there is a coercion 𝜑𝐴 : 𝐴 → 𝑍 and 𝜑𝐵 : 𝐵 → 𝑍, call 𝜑𝐴 (a)._add_( 𝜑𝐵 (b))
These rules are evaluated in order; therefore if there are coercions in both directions, then the parent of a._add_b is A
– the parent of the left-hand operand is used in such cases.
The same rules are used for subtraction, multiplication, and division. This logic is embedded in a coercion model
object, which can be obtained and queried.

sage: parent(1 + 1/2)

Rational Field
sage: cm = coercion_model; cm
<[Link] object at ...>
sage: [Link](ZZ, QQ)
Coercion on left operand via
Natural morphism:
From: Integer Ring
To: Rational Field
Arithmetic performed after coercions.
Result lives in Rational Field
Rational Field

sage: [Link](ZZ['x','y'], QQ['x'])

Coercion on left operand via
Coercion map:
From: Multivariate Polynomial Ring in x, y over Integer Ring
To: Multivariate Polynomial Ring in x, y over Rational Field
Coercion on right operand via
Coercion map:
From: Univariate Polynomial Ring in x over Rational Field
To: Multivariate Polynomial Ring in x, y over Rational Field
Arithmetic performed after coercions.
Result lives in Multivariate Polynomial Ring in x, y over Rational Field
Multivariate Polynomial Ring in x, y over Rational Field

The coercion model can be used directly for any binary operation (callable taking two arguments).

sage: cm.bin_op(77, 9, gcd)

1

5
Sage Reference Manual: Coercion, Release 9.0

There are also actions in the sense that a field 𝐾 acts on a module over 𝐾, or a permutation group acts on a set. These
are discovered between steps 1 and 2 above.

sage: [Link](ZZ['x'], ZZ, [Link])

Action discovered.
Right scalar multiplication by Integer Ring on Univariate Polynomial Ring in x
˓→over Integer Ring

Result lives in Univariate Polynomial Ring in x over Integer Ring

Univariate Polynomial Ring in x over Integer Ring

sage: [Link](ZZ['x'], ZZ, [Link])

Action discovered.
Right inverse action by Rational Field on Univariate Polynomial Ring in x over
˓→Integer Ring

with precomposition on right by Natural morphism:

From: Integer Ring
To: Rational Field
Result lives in Univariate Polynomial Ring in x over Rational Field
Univariate Polynomial Ring in x over Rational Field

sage: f = QQ.coerce_map_from(ZZ)
sage: f(3).parent()
Rational Field

Note that by trac ticket #14711 Sage’s coercion system uses maps with weak references to the domain. Such maps
should only be used internally, and so a copy should be used instead (unless one knows what one is doing):

sage: QQ._internal_coerce_map_from(int)
(map internal to coercion system -- copy before use)
Native morphism:
From: Set of Python objects of class 'int'
To: Rational Field
sage: copy(QQ._internal_coerce_map_from(int))
Native morphism:
From: Set of Python objects of class 'int'
To: Rational Field

Note that the user-visible method (without underscore) automates this copy:

sage: copy(QQ.coerce_map_from(int))
Native morphism:
From: Set of Python objects of class 'int'
To: Rational Field

sage: QQ.has_coerce_map_from(RR)
False
sage: QQ['x'].get_action(QQ)
Right scalar multiplication by Rational Field on Univariate Polynomial Ring in x over
˓→Rational Field

sage: QQ2 = QQ^2

sage: (QQ2).get_action(QQ)
Right scalar multiplication by Rational Field on Vector space of dimension 2 over
˓→Rational Field

sage: QQ['x'].get_action(RR)
Right scalar multiplication by Real Field with 53 bits of precision on Univariate
˓→Polynomial Ring in x over Rational Field

6 Chapter 2. Basic Arithmetic Rules

 CHAPTER

THREE

HOW TO IMPLEMENT

3.1 Methods to implement

• Arithmetic on Elements: _add_, _sub_, _mul_, _div_

This is where the binary arithmetic operators should be implemented. Unlike Python’s __add__, both operands
are guaranteed to have the same Parent at this point.
• Coercion for Parents: _coerce_map_from_
Given two parents R and S, R._coerce_map_from_(S) is called to determine if there is a coercion 𝜑 :
𝑆 → 𝑅. Note that the function is called on the potential codomain. To indicate that there is no coercion from S
to R (self), return False or None. This is the default behavior. If there is a coercion, return True (in which
case an morphism using R._element_constructor_ will be created) or an actual Morphism object with
S as the domain and R as the codomain.
• Actions for Parents: _get_action_ or _rmul_, _lmul_, _act_on_, _acted_upon_
Suppose one wants R to act on S. Some examples of this could be 𝑅 = Q, 𝑆 = Q[𝑥] or 𝑅 = Gal(𝑆/Q) where
𝑆 is a number field. There are several ways to implement this:
– If 𝑅 is the base of 𝑆 (as in the first example), simply implement _rmul_ and/or _lmul_ on the Elements
of 𝑆. In this case r * s gets handled as s._rmul_(r) and s * r as s._lmul_(r). The argu-
ment to _rmul_ and _lmul_ are guaranteed to be Elements of the base of 𝑆 (with coercion happening
beforehand if necessary).
– If 𝑅 acts on 𝑆, one can define the methods _act_on_ on Elements of 𝑅 or _acted_upon_ on Ele-
ments of 𝑆. In this case r * s gets handled as r._act_on_(s, True) or s._acted_upon_(r,
False) and s * r as r._act_on_(s, False) or s._acted_upon_(r, True). There is no
constraint on the type or parents of objects passed to these methods; raise a TypeError or ValueError
if the wrong kind of object is passed in to indicate the action is not appropriate here.
– If either 𝑅 acts on 𝑆 or 𝑆 acts on 𝑅, one may implement R._get_action_ to return an actual Action
object to be used. This is how non-multiplicative actions must be implemented, and is the most powerful
and complete way to do things.
It should be noted that for the first way to work, elements of 𝑆 are required to be ModuleElements. This
requirement is likely to be lifted in the future.
• Element conversion/construction for Parents: use _element_constructor_ not __call__
The Parent.__call__() method dispatches to _element_constructor_. When someone writes
R(x, ...), this is the method that eventually gets called in most cases. See the documentation on the
__call__ method below.
Parents may also call the self._populate_coercion_lists_ method in their __init__ functions to pass
any callable for use instead of _element_constructor_, provide a list of Parents with coercions to self (as

7
Sage Reference Manual: Coercion, Release 9.0

an alternative to implementing _coerce_map_from_), provide special construction methods (like _integer_

for ZZ), etc. This also allows one to specify a single coercion embedding out of self (whereas the rest of
the coercion functions all specify maps into self). There is extensive documentation in the docstring of the
_populate_coercion_lists_ method.

3.2 Example

Sometimes a simple example is worth a thousand words. Here is a minimal example of setting up a simple Ring that
handles coercion. (It is easy to imagine much more sophisticated and powerful localizations, but that would obscure
the main points being made here.)

class Localization(Ring):
def __init__(self, primes):
"""
Localization of `\ZZ` away from primes.
"""
Ring.__init__(self, base=ZZ)
self._primes = primes
self._populate_coercion_lists_()

def _repr_(self):
"""
How to print self.
"""
return "%s localized at %s" % ([Link](), self._primes)

def _element_constructor_(self, x):

"""
Make sure x is a valid member of self, and return the constructed element.
"""
if isinstance(x, LocalizationElement):
x = x._value
else:
x = QQ(x)
for p, e in [Link]().factor():
if p not in self._primes:
raise ValueError("Not integral at %s" % p)
return LocalizationElement(self, x)

def _coerce_map_from_(self, S):

"""
The only things that coerce into this ring are:

- the integer ring

- other localizations away from fewer primes

"""
if S is ZZ:
return True
elif isinstance(S, Localization):
return all(p in self._primes for p in S._primes)

class LocalizationElement(RingElement):

(continues on next page)

8 Chapter 3. How to Implement

 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

def __init__(self, parent, x):
RingElement.__init__(self, parent)
self._value = x

# We're just printing out this way to make it easy to see what's going on in the
˓→ examples.

def _repr_(self):
return "LocalElt(%s)" % self._value

# Now define addition, subtraction, and multiplication of elements.

# Note that left and right always have the same parent.

def _add_(left, right):

return LocalizationElement([Link](), left._value + right._value)

def _sub_(left, right):

return LocalizationElement([Link](), left._value - right._value)

def _mul_(left, right):

return LocalizationElement([Link](), left._value * right._value)

# The basering was set to ZZ, so c is guaranteed to be in ZZ

def _rmul_(self, c):

return LocalizationElement([Link](), c * self._value)

def _lmul_(self, c):

return LocalizationElement([Link](), self._value * c)

That’s all there is to it. Now we can test it out:

sage: R = Localization([2]); R
Integer Ring localized at [2]
sage: R(1)
LocalElt(1)
sage: R(1/2)
LocalElt(1/2)
sage: R(1/3)
Traceback (most recent call last):
...
ValueError: Not integral at 3

sage: [Link](1)
LocalElt(1)
sage: [Link](1/4)
Traceback (click to the left for traceback)
...
TypeError: no canonical coercion from Rational Field to Integer Ring localized at [2]

sage: R(1/2) + R(3/4)

LocalElt(5/4)
sage: R(1/2) + 5
LocalElt(11/2)
sage: 5 + R(1/2)
LocalElt(11/2)
(continues on next page)

3.2. Example 9
Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: R(1/2) + 1/7
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for +: 'Integer Ring localized at [2]' and
˓→'Rational Field'

sage: R(3/4) * 7
LocalElt(21/4)

sage: R.get_action(ZZ)
Right scalar multiplication by Integer Ring on Integer Ring localized at [2]
sage: cm = [Link].get_coercion_model()
sage: [Link](R, ZZ, [Link])
Coercion on right operand via
Conversion map:
From: Integer Ring
To: Integer Ring localized at [2]
Arithmetic performed after coercions.
Result lives in Integer Ring localized at [2]
Integer Ring localized at [2]

sage: [Link](R, ZZ, [Link])

Action discovered.
Right scalar multiplication by Integer Ring on Integer Ring localized at [2]
Result lives in Integer Ring localized at [2]
Integer Ring localized at [2]

sage: R6 = Localization([2,3]); R6
Integer Ring localized at [2, 3]
sage: R6(1/3) - R(1/2)
LocalElt(-1/6)
sage: parent(R6(1/3) - R(1/2))
Integer Ring localized at [2, 3]

sage: R.has_coerce_map_from(ZZ)
True
sage: R.coerce_map_from(ZZ)
Conversion map:
From: Integer Ring
To: Integer Ring localized at [2]

sage: R6.coerce_map_from(R)
Conversion map:
From: Integer Ring localized at [2]
To: Integer Ring localized at [2, 3]

sage: [Link](R(1/2))
LocalElt(1/2)

sage: [Link](R, R6, [Link])

Coercion on left operand via
Conversion map:
From: Integer Ring localized at [2]
To: Integer Ring localized at [2, 3]
Arithmetic performed after coercions.
Result lives in Integer Ring localized at [2, 3]
Integer Ring localized at [2, 3]

10 Chapter 3. How to Implement

 Sage Reference Manual: Coercion, Release 9.0

3.3 Provided Methods

• __call__
This provides a consistent interface for element construction. In particular, it makes sure that conversion always
gives the same result as coercion, if a coercion exists. (This used to be violated for some Rings in Sage as the
code for conversion and coercion got edited separately.) Let R be a Parent and assume the user types R(x),
where x has parent X. Roughly speaking, the following occurs:
1. If X is R, return x (*)
2. If there is a coercion 𝑓 : 𝑋 → 𝑅, return 𝑓 (𝑥)
3. If there is a coercion 𝑓 : 𝑅 → 𝑋, try to return 𝑓 −1 (𝑥)
4. Return R._element_constructor_(x) (**)
Keywords and extra arguments are passed on. The result of all this logic is cached.
(*) Unless there is a “copy” keyword like R(x, copy=False)
(**) Technically, a generic morphism is created from X to R, which may use magic methods like _integer_
or other data provided by _populate_coercion_lists_.
• coerce
Coerces elements into self, raising a type error if there is no coercion map.
• coerce_map_from, convert_map_from
Returns an actual Morphism object to coerce/convert from another Parent to self. Barring direct construction
of elements of R, R.convert_map_from(S) will provide a callable Python object which is the fastest way
to convert elements of S to elements of R. From Cython, it can be invoked via the cdef _call_ method.
• has_coerce_map_from
Returns True or False depending on whether or not there is a coercion. R.has_coerce_map_from(S)
is shorthand for R.coerce_map_from(S) is not None
• get_action
This will unwind all the _get_action_, _rmul_, _lmul_, _act_on_, _acted_upon_, ...
methods to provide an actual Action object, if one exists.

3.3. Provided Methods 11

Sage Reference Manual: Coercion, Release 9.0

12 Chapter 3. How to Implement

 CHAPTER

FOUR

DISCOVERING NEW PARENTS

New parents are discovered using an algorithm in sage/category/[Link]. The fundamental idea is that most Parents
in Sage are constructed from simpler objects via various functors. These are accessed via the construction()
method, which returns a (simpler) Parent along with a functor with which one can create self.

sage: [Link]()
(AlgebraicClosureFunctor, Real Field with 53 bits of precision)
sage: [Link]()
(Completion[+Infinity, prec=53], Rational Field)
sage: [Link]()
(FractionField, Integer Ring)
sage: [Link]() # None

sage: Zp(5).construction()
(Completion[5, prec=20], Integer Ring)
sage: [Link](5, 100, {})
5-adic Field with capped relative precision 100
sage: c, R = [Link]()
sage: a = [Link]()[0]
sage: [Link](c)
False
sage: RR == c(QQ)
True

sage: [Link].construction_tower(Frac(CDF['x']))
[(None,
Fraction Field of Univariate Polynomial Ring in x over Complex Double Field),
(FractionField, Univariate Polynomial Ring in x over Complex Double Field),
(Poly[x], Complex Double Field),
(AlgebraicClosureFunctor, Real Double Field),
(Completion[+Infinity, prec=53], Rational Field),
(FractionField, Integer Ring)]

Given Parents R and S, such that there is no coercion either from R to S or from S to R, one can find a common Z with
coercions 𝑅 → 𝑍 and 𝑆 → 𝑍 by considering the sequence of construction functors to get from a common ancestor to
both R and S. We then use a heuristic algorithm to interleave these constructors in an attempt to arrive at a suitable Z
(if one exists). For example:

sage: ZZ['x'].construction()
(Poly[x], Integer Ring)
sage: [Link]()
(FractionField, Integer Ring)
sage: [Link](ZZ['x'], QQ)
Univariate Polynomial Ring in x over Rational Field
(continues on next page)

13
Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: [Link](ZZ['x'], QQ).construction()
(Poly[x], Rational Field)

The common ancestor is 𝑍 and our options for Z are Frac(Z[𝑥]) or Frac(Z)[𝑥]. In Sage we choose the later, treating
the fraction field functor as binding “more tightly” than the polynomial functor, as most people agree that Q[𝑥] is the
more natural choice. The same procedure is applied to more complicated Parents, returning a new Parent if one can
be unambiguously determined.

sage: [Link](Frac(ZZ['x,y,z']), QQ['z, t'])

Univariate Polynomial Ring in t over Fraction Field of Multivariate Polynomial Ring
˓→in x, y, z over Rational Field

14 Chapter 4. Discovering new parents

 CHAPTER

FIVE

MODULES

5.1 The coercion model

The coercion model manages how elements of one parent get related to elements of another. For example, the integer
2 can canonically be viewed as an element of the rational numbers. (The parent of a non-element is its Python type.)

sage: ZZ(2).parent()
Integer Ring
sage: QQ(2).parent()
Rational Field

The most prominent role of the coercion model is to make sense of binary operations between elements that have
distinct parents. It does this by finding a parent where both elements make sense, and doing the operation there. For
example:

sage: a = 1/2; [Link]()

Rational Field
sage: b = ZZ['x'].gen(); [Link]()
Univariate Polynomial Ring in x over Integer Ring
sage: a+b
x + 1/2
sage: (a+b).parent()
Univariate Polynomial Ring in x over Rational Field

If there is a coercion (see below) from one of the parents to the other, the operation is always performed in the codomain
of that coercion. Otherwise a reasonable attempt to create a new parent with coercion maps from both original parents
is made. The results of these discoveries are cached. On failure, a TypeError is always raised.
Some arithmetic operations (such as multiplication) can indicate an action rather than arithmetic in a common parent.
For example:

sage: E = EllipticCurve('37a')
sage: P = E(0,0)
sage: 5*P
(1/4 : -5/8 : 1)

where there is action of Z on the points of 𝐸 given by the additive group law. Parents can specify how they act on or
are acted upon by other parents.
There are two kinds of ways to get from one parent to another, coercions and conversions.
Coercions are canonical (possibly modulo a finite number of deterministic choices) morphisms, and the set of all
coercions between all parents forms a commuting diagram (modulo possibly rounding issues). Z → Q is an example
of a coercion. These are invoked implicitly by the coercion model.

15
Sage Reference Manual: Coercion, Release 9.0

Conversions try to construct an element out of their input if at all possible. Examples include sections of coercions,
creating an element from a string or list, etc. and may fail on some inputs of a given type while succeeding on others
(i.e. they may not be defined on the whole domain). Conversions are always explicitly invoked, and never used by the
coercion model to resolve binary operations.
For more information on how to specify coercions, conversions, and actions, see the documentation for Parent.
class [Link]
Bases: object
See also [Link]
EXAMPLES:

sage: f = ZZ['t','x'].0 + QQ['x'].0 + CyclotomicField(13).gen(); f

t + x + (zeta13)
sage: [Link]()
Multivariate Polynomial Ring in t, x over Cyclotomic Field of order 13 and degree
˓→12

sage: ZZ['x','y'].0 + ~Frac(QQ['y']).0

(x*y + 1)/y
sage: MatrixSpace(ZZ['x'], 2, 2)(2) + ~Frac(QQ['x']).0
[(2*x + 1)/x 0]
[ 0 (2*x + 1)/x]
sage: f = ZZ['x,y,z'].0 + QQ['w,x,z,a'].0; f
w + x
sage: [Link]()
Multivariate Polynomial Ring in w, x, y, z, a over Rational Field
sage: ZZ['x,y,z'].0 + ZZ['w,x,z,a'].1
2*x

AUTHOR:
• Robert Bradshaw
analyse(xp, yp, op=’mul’)
Emulate the process of doing arithmetic between xp and yp, returning a list of steps and the parent that the
result will live in. The explain function is easier to use, but if one wants access to the actual morphism
and action objects (rather than their string representations) then this is the function to use.
EXAMPLES:

sage: cm = [Link].get_coercion_model()
sage: GF7 = GF(7)
sage: steps, res = [Link](GF7, ZZ)
sage: steps
['Coercion on right operand via', Natural morphism:
From: Integer Ring
To: Finite Field of size 7, 'Arithmetic performed after coercions.']
sage: res
Finite Field of size 7
sage: f = steps[1]; type(f)
<type '[Link].finite_rings.integer_mod.Integer_to_IntegerMod'>
sage: f(100)
2

bin_op(x, y, op)
Execute the operation op on x and y. It first looks for an action corresponding to op, and failing that, it
tries to coerces x and y into a common parent and calls op on them.
If it cannot make sense of the operation, a TypeError is raised.

16 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

INPUT:
• x - the left operand
• y - the right operand
• op - a python function taking 2 arguments

Note: op is often an arithmetic operation, but need not be so.

EXAMPLES:

sage: cm = [Link].get_coercion_model()
sage: cm.bin_op(1/2, 5, [Link])
5/2

The operator can be any callable:

sage: R.<x> = ZZ['x']

sage: cm.bin_op(x^2-1, x+1, gcd)
x + 1

Actions are detected and performed:

sage: M = matrix(ZZ, 2, 2, range(4))

sage: V = vector(ZZ, [5,7])
sage: cm.bin_op(M, V, [Link])
(7, 31)

canonical_coercion(x, y)
Given two elements x and y, with parents S and R respectively, find a common parent Z such that there are
coercions 𝑓 : 𝑆 ↦→ 𝑍 and 𝑔 : 𝑅 ↦→ 𝑍 and return 𝑓 (𝑥), 𝑔(𝑦) which will have the same parent.
Raises a type error if no such Z can be found.
EXAMPLES:

sage: cm = [Link].get_coercion_model()
sage: cm.canonical_coercion(mod(2, 10), 17)
(2, 7)
sage: x, y = cm.canonical_coercion(1/2, matrix(ZZ, 2, 2, range(4)))
sage: x
[1/2 0]
[ 0 1/2]
sage: y
[0 1]
[2 3]
sage: parent(x) is parent(y)
True

There is some support for non-Sage datatypes as well:

sage: x, y = cm.canonical_coercion(int(5), 10)

sage: type(x), type(y)
(<type '[Link]'>, <type '[Link]'>)

sage: x, y = cm.canonical_coercion(int(5), complex(3))

(continues on next page)

5.1. The coercion model 17

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: type(x), type(y)
(<type 'complex'>, <type 'complex'>)

sage: class MyClass:

....: def _sage_(self):
....: return 13
sage: a, b = cm.canonical_coercion(MyClass(), 1/3)
sage: a, b
(13, 1/3)
sage: type(a)
<type '[Link]'>

We also make an exception for 0, even if Z does not map in:

sage: canonical_coercion(vector([1, 2, 3]), 0)

((1, 2, 3), (0, 0, 0))
sage: canonical_coercion(GF(5)(0), float(0))
(0, 0)

coercion_maps(R, S)
Give two parents 𝑅 and 𝑆, return a pair of coercion maps 𝑓 : 𝑅 → 𝑍 and 𝑔 : 𝑆 → 𝑍 , if such a 𝑍 can be
found.
In the (common) case that 𝑅 = 𝑍 or 𝑆 = 𝑍 then None is returned for 𝑓 or 𝑔 respectively rather than
constructing (and subsequently calling) the identity morphism.
If no suitable 𝑓, 𝑔 can be found, a single None is returned. This result is cached.

Note: By trac ticket #14711, coerce maps should be copied when using them outside of the coercion
system, because they may become defunct by garbage collection.

EXAMPLES:

sage: cm = [Link].get_coercion_model()
sage: f, g = cm.coercion_maps(ZZ, QQ)
sage: print(copy(f))
Natural morphism:
From: Integer Ring
To: Rational Field
sage: print(g)
None

sage: ZZx = ZZ['x']

sage: f, g = cm.coercion_maps(ZZx, QQ)
sage: print(f)
(map internal to coercion system -- copy before use)
Ring morphism:
From: Univariate Polynomial Ring in x over Integer Ring
To: Univariate Polynomial Ring in x over Rational Field
sage: print(g)
(map internal to coercion system -- copy before use)
Polynomial base injection morphism:
From: Rational Field
To: Univariate Polynomial Ring in x over Rational Field

(continues on next page)

18 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: K = GF(7)
sage: cm.coercion_maps(QQ, K) is None
True

Note that to break symmetry, if there is a coercion map in both directions, the parent on the left is used:

sage: V = QQ^3
sage: W = V.__class__(QQ, 3)
sage: V == W
True
sage: V is W
False
sage: cm = [Link].get_coercion_model()
sage: cm.coercion_maps(V, W)
(None, (map internal to coercion system -- copy before use)
Coercion map:
From: Vector space of dimension 3 over Rational Field
To: Vector space of dimension 3 over Rational Field)
sage: cm.coercion_maps(W, V)
(None, (map internal to coercion system -- copy before use)
Coercion map:
From: Vector space of dimension 3 over Rational Field
To: Vector space of dimension 3 over Rational Field)
sage: v = V([1,2,3])
sage: w = W([1,2,3])
sage: parent(v+w) is V
True
sage: parent(w+v) is W
True

common_parent(*args)
Computes a common parent for all the inputs. It’s essentially an 𝑛-ary canonical coercion except it can
operate on parents rather than just elements.
INPUT:
• args – a set of elements and/or parents
OUTPUT:
A Parent into which each input should coerce, or raises a TypeError if no such Parent can be
found.
EXAMPLES:

sage: cm = [Link].get_coercion_model()
sage: cm.common_parent(ZZ, QQ)
Rational Field
sage: cm.common_parent(ZZ, QQ, RR)
Real Field with 53 bits of precision
sage: ZZT = ZZ[['T']]
sage: QQT = QQ['T']
sage: cm.common_parent(ZZT, QQT, RDF)
Power Series Ring in T over Real Double Field
sage: cm.common_parent(4r, 5r)
<type 'int'>
sage: cm.common_parent(int, float, ZZ)
<type 'float'>
(continues on next page)

5.1. The coercion model 19

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: real_fields = [RealField(prec) for prec in [10,20..100]]
sage: cm.common_parent(*real_fields)
Real Field with 10 bits of precision

There are some cases where the ordering does matter, but if a parent can be found it is always the same:
sage: QQxy = QQ['x,y']
sage: QQyz = QQ['y,z']
sage: cm.common_parent(QQxy, QQyz) == cm.common_parent(QQyz, QQxy)
True
sage: QQzt = QQ['z,t']
sage: cm.common_parent(QQxy, QQyz, QQzt)
Multivariate Polynomial Ring in x, y, z, t over Rational Field
sage: cm.common_parent(QQxy, QQzt, QQyz)
Traceback (most recent call last):
...
TypeError: no common canonical parent for objects with parents: 'Multivariate
˓→Polynomial Ring in x, y over Rational Field' and 'Multivariate Polynomial

˓→Ring in z, t over Rational Field'

discover_action(R, S, op, r=None, s=None)

INPUT:
• R - the left Parent (or type)
• S - the right Parent (or type)
• op - the operand, typically an element of the operator module
• r - (optional) element of R
• s - (optional) element of S.
OUTPUT:
• An action A such that s op r is given by A(s,r).
The steps taken are illustrated below.
EXAMPLES:
sage: P.<x> = ZZ['x']
sage: P.get_action(ZZ)
Right scalar multiplication by Integer Ring on Univariate Polynomial Ring in
˓→x over Integer Ring

sage: ZZ.get_action(P) is None

True
sage: cm = [Link].get_coercion_model()

If R or S is a Parent, ask it for an action by/on R:

sage: cm.discover_action(ZZ, P, [Link])
Left scalar multiplication by Integer Ring on Univariate Polynomial Ring in x
˓→over Integer Ring

If R or S a type, recursively call get_action with the Sage versions of R and/or S:

sage: cm.discover_action(P, int, [Link])
Right scalar multiplication by Integer Ring on Univariate Polynomial Ring in
˓→x over Integer Ring

(continues on next page)

20 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

with precomposition on right by Native morphism:
From: Set of Python objects of class 'int'
To: Integer Ring

If op is division, look for action on right by inverse:

sage: cm.discover_action(P, ZZ, [Link])
Right inverse action by Rational Field on Univariate Polynomial Ring in x
˓→over Integer Ring

with precomposition on right by Natural morphism:

From: Integer Ring
To: Rational Field

Check that trac ticket #17740 is fixed:

sage: R = GF(5)['x']
sage: cm.discover_action(R, ZZ, [Link])
Right inverse action by Finite Field of size 5 on Univariate Polynomial Ring
˓→in x over Finite Field of size 5

with precomposition on right by Natural morphism:

From: Integer Ring
To: Finite Field of size 5
sage: cm.bin_op([Link](), 7, [Link]).parent()
Univariate Polynomial Ring in x over Finite Field of size 5

Check that trac ticket #18221 is fixed:

sage: F.<x> = FreeAlgebra(QQ)
sage: x / 2
1/2*x
sage: cm.discover_action(F, ZZ, [Link])
Right inverse action by Rational Field on Free Algebra on 1 generators (x,)
˓→over Rational Field

with precomposition on right by Natural morphism:

From: Integer Ring
To: Rational Field

discover_coercion(R, S)
This actually implements the finding of coercion maps as described in the coercion_maps method.
EXAMPLES:
sage: cm = [Link].get_coercion_model()

If R is S, then two identity morphisms suffice:

sage: cm.discover_coercion(SR, SR)
(None, None)

If there is a coercion map either direction, use that:

sage: cm.discover_coercion(ZZ, QQ)
((map internal to coercion system -- copy before use)
Natural morphism:
From: Integer Ring
To: Rational Field, None)
sage: cm.discover_coercion(RR, QQ)
(continues on next page)

5.1. The coercion model 21

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

(None, (map internal to coercion system -- copy before use)
Generic map:
From: Rational Field
To: Real Field with 53 bits of precision)

Otherwise, try and compute an appropriate cover:

sage: ZZxy = ZZ['x,y']

sage: cm.discover_coercion(ZZxy, RDF)
((map internal to coercion system -- copy before use)
Call morphism:
From: Multivariate Polynomial Ring in x, y over Integer Ring
To: Multivariate Polynomial Ring in x, y over Real Double Field,
Polynomial base injection morphism:
From: Real Double Field
To: Multivariate Polynomial Ring in x, y over Real Double Field)

Sometimes there is a reasonable “cover,” but no canonical coercion:

sage: [Link](QQ, QQ^3)

Vector space of dimension 3 over Rational Field
sage: print(cm.discover_coercion(QQ, QQ^3))
None

division_parent(P)
Deduces where the result of division in P lies by calculating the inverse of [Link]() or P.
an_element().
The result is cached.
EXAMPLES:

sage: cm = [Link].get_coercion_model()
sage: cm.division_parent(ZZ)
Rational Field
sage: cm.division_parent(QQ)
Rational Field
sage: ZZx = ZZ['x']
sage: cm.division_parent(ZZx)
Fraction Field of Univariate Polynomial Ring in x over Integer Ring
sage: K = GF(41)
sage: cm.division_parent(K)
Finite Field of size 41
sage: Zmod100 = Integers(100)
sage: cm.division_parent(Zmod100)
Ring of integers modulo 100
sage: S5 = SymmetricGroup(5)
sage: cm.division_parent(S5)
Symmetric group of order 5! as a permutation group

exception_stack()
Returns the list of exceptions that were caught in the course of executing the last binary operation. Useful
for diagnosis when user-defined maps or actions raise exceptions that are caught in the course of coercion
detection.
If all went well, this should be the empty list. If things aren’t happening as you expect, this is a good place
to check. See also coercion_traceback().

22 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

EXAMPLES:

sage: cm = [Link].get_coercion_model()
sage: cm.record_exceptions()
sage: 1/2 + 2
5/2
sage: cm.exception_stack()
[]
sage: 1/2 + GF(3)(2)
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for +: 'Rational Field' and 'Finite
˓→Field of size 3'

Now see what the actual problem was:

sage: import traceback

sage: cm.exception_stack()
['Traceback (most recent call last):...', 'Traceback (most recent call last):.
˓→..']

sage: print(cm.exception_stack()[-1])
Traceback (most recent call last):
...
TypeError: no common canonical parent for objects with parents: 'Rational
˓→Field' and 'Finite Field of size 3'

This is typically accessed via the coercion_traceback() function.

sage: coercion_traceback()
Traceback (most recent call last):
...
TypeError: no common canonical parent for objects with parents: 'Rational
˓→Field' and 'Finite Field of size 3'

explain(xp, yp, op=’mul’, verbosity=2)

This function can be used to understand what coercions will happen for an arithmetic operation between
xp and yp (which may be either elements or parents). If the parent of the result can be determined then it
will be returned.
EXAMPLES:

sage: cm = [Link].get_coercion_model()

sage: [Link](ZZ, ZZ)

Identical parents, arithmetic performed immediately.
Result lives in Integer Ring
Integer Ring

sage: [Link](QQ, int)

Coercion on right operand via
Native morphism:
From: Set of Python objects of class 'int'
To: Rational Field
Arithmetic performed after coercions.
Result lives in Rational Field
Rational Field

sage: R = ZZ['x']
(continues on next page)

5.1. The coercion model 23

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: [Link](R, QQ)
Action discovered.
Right scalar multiplication by Rational Field on Univariate Polynomial
˓→Ring in x over Integer Ring

Result lives in Univariate Polynomial Ring in x over Rational Field

Univariate Polynomial Ring in x over Rational Field

sage: [Link](ZZ['x'], QQ, [Link])

Coercion on left operand via
Ring morphism:
From: Univariate Polynomial Ring in x over Integer Ring
To: Univariate Polynomial Ring in x over Rational Field
Defn: Induced from base ring by
Natural morphism:
From: Integer Ring
To: Rational Field
Coercion on right operand via
Polynomial base injection morphism:
From: Rational Field
To: Univariate Polynomial Ring in x over Rational Field
Arithmetic performed after coercions.
Result lives in Univariate Polynomial Ring in x over Rational Field
Univariate Polynomial Ring in x over Rational Field

Sometimes with non-sage types there is not enough information to deduce what will actually happen:
sage: R100 = RealField(100)
sage: [Link](R100, float, [Link])
Right operand is numeric, will attempt coercion in both directions.
Unknown result parent.
sage: parent(R100(1) + float(1))
<type 'float'>
sage: [Link](QQ, float, [Link])
Right operand is numeric, will attempt coercion in both directions.
Unknown result parent.
sage: parent(QQ(1) + float(1))
<type 'float'>

Special care is taken to deal with division:

sage: [Link](ZZ, ZZ, [Link])
Identical parents, arithmetic performed immediately.
Result lives in Rational Field
Rational Field

sage: ZZx = ZZ['x']

sage: QQx = QQ['x']
sage: [Link](ZZx, QQx, [Link])
Coercion on left operand via
Ring morphism:
From: Univariate Polynomial Ring in x over Integer Ring
To: Univariate Polynomial Ring in x over Rational Field
Defn: Induced from base ring by
Natural morphism:
From: Integer Ring
To: Rational Field
Arithmetic performed after coercions.
(continues on next page)

24 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

Result lives in Fraction Field of Univariate Polynomial Ring in x over
˓→Rational Field

Fraction Field of Univariate Polynomial Ring in x over Rational Field

sage: [Link](int, ZZ, [Link])

Coercion on left operand via
Native morphism:
From: Set of Python objects of class 'int'
To: Integer Ring
Arithmetic performed after coercions.
Result lives in Rational Field
Rational Field

sage: [Link](ZZx, ZZ, [Link])

Action discovered.
Right inverse action by Rational Field on Univariate Polynomial Ring in x
˓→over Integer Ring

with precomposition on right by Natural morphism:

From: Integer Ring
To: Rational Field
Result lives in Univariate Polynomial Ring in x over Rational Field
Univariate Polynomial Ring in x over Rational Field

Note: This function is accurate only in so far as analyse() is kept in sync with the bin_op() and
canonical_coercion() which are kept separate for maximal efficiency.

get_action(R, S, op=’mul’, r=None, s=None)

Get the action of R on S or S on R associated to the operation op.
EXAMPLES:

sage: cm = [Link].get_coercion_model()
sage: ZZx = ZZ['x']
sage: cm.get_action(ZZx, ZZ, [Link])
Right scalar multiplication by Integer Ring on Univariate Polynomial Ring in
˓→x over Integer Ring

sage: cm.get_action(ZZx, QQ, [Link])

Right scalar multiplication by Rational Field on Univariate Polynomial Ring
˓→in x over Integer Ring

sage: QQx = QQ['x']

sage: cm.get_action(QQx, int, [Link])
Right scalar multiplication by Integer Ring on Univariate Polynomial Ring in
˓→x over Rational Field

with precomposition on right by Native morphism:

From: Set of Python objects of class 'int'
To: Integer Ring

sage: A = cm.get_action(QQx, ZZ, [Link]); A

Right inverse action by Rational Field on Univariate Polynomial Ring in x
˓→over Rational Field

with precomposition on right by Natural morphism:

From: Integer Ring
To: Rational Field
sage: x = [Link]()
sage: A(x+10, 5)
(continues on next page)

5.1. The coercion model 25

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

1/5*x + 2

get_cache()
This returns the current cache of coercion maps and actions, primarily useful for debugging and introspec-
tion.
EXAMPLES:
sage: cm = [Link].get_coercion_model()
sage: cm.canonical_coercion(1,2/3)
(1, 2/3)
sage: maps, actions = cm.get_cache()

Now let us see what happens when we do a binary operations with an integer and a rational:
sage: left_morphism_ref, right_morphism_ref = maps[ZZ, QQ]

Note that by trac ticket #14058 the coercion model only stores a weak reference to the coercion maps in
this case:
sage: left_morphism_ref
<weakref at ...; to '[Link].Z_to_Q' at ...>

Moreover, the weakly referenced coercion map uses only a weak reference to the codomain:
sage: left_morphism_ref()
(map internal to coercion system -- copy before use)
Natural morphism:
From: Integer Ring
To: Rational Field

To get an actual valid map, we simply copy the weakly referenced coercion map:
sage: print(copy(left_morphism_ref()))
Natural morphism:
From: Integer Ring
To: Rational Field
sage: print(right_morphism_ref)
None

We can see that it coerces the left operand from an integer to a rational, and doesn’t do anything to the
right.
Now for some actions:
sage: R.<x> = ZZ['x']
sage: 1/2 * x
1/2*x
sage: maps, actions = cm.get_cache()
sage: act = actions[QQ, R, [Link]]; act
Left scalar multiplication by Rational Field on Univariate Polynomial Ring in
˓→x over Integer Ring

sage: [Link]()
Rational Field
sage: [Link]()
Univariate Polynomial Ring in x over Integer Ring
sage: [Link]()
(continues on next page)

26 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

Univariate Polynomial Ring in x over Rational Field
sage: act(1/5, x+10)
1/5*x + 2

record_exceptions(value=True)
Enables (or disables) recording of the exceptions suppressed during arithmetic.
Each time that record_exceptions is called (either enabling or disabling the record), the exception_stack is
cleared.
reset_cache()
Clear the coercion cache.
This should have no impact on the result of arithmetic operations, as the exact same coercions and actions
will be re-discovered when needed.
It may be useful for debugging, and may also free some memory.
EXAMPLES:

sage: cm = [Link].get_coercion_model()
sage: len(cm.get_cache()[0]) # random
42
sage: cm.reset_cache()
sage: cm.get_cache()
({}, {})

richcmp(x, y, op)
Given two arbitrary objects x and y, coerce them to a common parent and compare them using rich
comparison operator op.
EXAMPLES:

sage: from [Link] import get_coercion_model

sage: from [Link] import op_LT, op_LE, op_EQ, op_NE, op_GT,
˓→op_GE

sage: richcmp = get_coercion_model().richcmp

sage: richcmp(None, None, op_EQ)
True
sage: richcmp(None, 1, op_LT)
True
sage: richcmp("hello", None, op_LE)
False
sage: richcmp(-1, 1, op_GE)
False
sage: richcmp(int(1), float(2), op_GE)
False

If there is no coercion, we only support == and !=:

sage: x = [Link](); y = GF(2).one()

sage: richcmp(x, y, op_EQ)
False
sage: richcmp(x, y, op_NE)
True
sage: richcmp(x, y, op_GT)
Traceback (most recent call last):
(continues on next page)

5.1. The coercion model 27

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

...
TypeError: unsupported operand parent(s) for >: 'Rational Field' and 'Finite
˓→Field of size 2'

We support non-Sage types with the usual Python convention:

sage: class AlwaysEqual(object):

....: def __eq__(self, other):
....: return True
sage: x = AlwaysEqual()
sage: x == 1
True
sage: 1 == x
True

verify_action(action, R, S, op, fix=True)

Verify that action takes an element of R on the left and S on the right, raising an error if not.
This is used for consistency checking in the coercion model.
EXAMPLES:

sage: R.<x> = ZZ['x']

sage: cm = [Link].get_coercion_model()
sage: cm.verify_action(R.get_action(QQ), R, QQ, [Link])
Right scalar multiplication by Rational Field on Univariate Polynomial Ring
˓→in x over Integer Ring

sage: cm.verify_action(R.get_action(QQ), RDF, R, [Link])

Traceback (most recent call last):
...
RuntimeError: There is a BUG in the coercion model:
Action found for R <built-in function mul> S does not have the correct
˓→domains

R = Real Double Field

S = Univariate Polynomial Ring in x over Integer Ring
(should be Univariate Polynomial Ring in x over Integer Ring, Rational
˓→Field)

action = Right scalar multiplication by Rational Field on

Univariate Polynomial Ring in x over Integer Ring (<type '[Link].
˓→coerce_actions.RightModuleAction'>)

verify_coercion_maps(R, S, homs, fix=False)

Make sure this is a valid pair of homomorphisms from R and S to a common parent. This function is used
to protect the user against buggy parents.
EXAMPLES:

sage: cm = [Link].get_coercion_model()
sage: homs = QQ.coerce_map_from(ZZ), None
sage: cm.verify_coercion_maps(ZZ, QQ, homs) == homs
True
sage: homs = QQ.coerce_map_from(ZZ), RR.coerce_map_from(QQ)
sage: cm.verify_coercion_maps(ZZ, QQ, homs) == homs
Traceback (most recent call last):
...
RuntimeError: ('BUG in coercion model, codomains must be identical', Natural
˓→morphism:

(continues on next page)

28 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

From: Integer Ring
To: Rational Field, Generic map:
From: Rational Field
To: Real Field with 53 bits of precision)

[Link].is_mpmath_type(t)
Check whether the type t is a type whose name starts with either mpmath. or [Link]..
EXAMPLES:

sage: from [Link] import is_mpmath_type

sage: is_mpmath_type(int)
False
sage: import mpmath
sage: is_mpmath_type([Link](2))
False
sage: is_mpmath_type(type([Link](2)))
True
sage: is_mpmath_type(type([Link](2)))
True

[Link].is_numpy_type(t)
Return True if and only if 𝑡 is a type whose name starts with numpy.
EXAMPLES:

sage: from [Link] import is_numpy_type

sage: import numpy
sage: is_numpy_type(numpy.int16)
True
sage: is_numpy_type([Link])
True
sage: is_numpy_type([Link]) # Alias for Python float
False
sage: is_numpy_type([Link])
True
sage: is_numpy_type([Link])
True
sage: is_numpy_type(int)
False
sage: is_numpy_type(Integer)
False
sage: is_numpy_type(Sudoku)
False
sage: is_numpy_type(None)
False

[Link].parent_is_integers(P)
Check whether the type or parent represents the ring of integers.
EXAMPLES:

sage: from [Link] import parent_is_integers

sage: parent_is_integers(int)
True
sage: parent_is_integers(long)
True
(continues on next page)

5.1. The coercion model 29

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: parent_is_integers(float)
False
sage: parent_is_integers(bool)
True
sage: parent_is_integers(dict)
False

sage: import numpy

sage: parent_is_integers(numpy.int16)
True
sage: parent_is_integers(numpy.uint64)
True
sage: parent_is_integers([Link])
False

sage: import gmpy2

sage: parent_is_integers([Link])
True
sage: parent_is_integers([Link])
False

Ensure (trac ticket #27893) is fixed:

sage: K.<f> = QQ[]

sage: [Link](2) * f
2*f

[Link].parent_is_numerical(P)
Test if elements of the parent or type P can be numerically evaluated as complex numbers (in a canonical way).
EXAMPLES:

sage: from [Link] import parent_is_numerical

sage: import gmpy2, numpy
sage: [parent_is_numerical(R) for R in [RR, CC, QQ, QuadraticField(-1),
....: int, complex, [Link], [Link]]]
[True, True, True, True, True, True, True, True]
sage: [parent_is_numerical(R) for R in [SR, QQ['x'], QQ[['x']], str]]
[False, False, False, False]
sage: [parent_is_numerical(R) for R in [RIF, RBF, CIF, CBF]]
[False, False, False, False]

[Link].parent_is_real_numerical(P)
Test if elements of the parent or type P can be numerically evaluated as real numbers (in a canonical way).
EXAMPLES:

sage: from [Link] import parent_is_real_numerical

sage: import gmpy2, numpy
sage: [parent_is_real_numerical(R) for R in [RR, QQ, ZZ, RLF,
....: QuadraticField(2), int, float, [Link], [Link]]]
[True, True, True, True, True, True, True, True, True]
sage: [parent_is_real_numerical(R) for R in [CC, QuadraticField(-1),
....: complex, [Link], [Link]]]
[False, False, False, False, False]
sage: [parent_is_real_numerical(R) for R in [SR, QQ['x'], QQ[['x']], str]]
[False, False, False, False]
(continues on next page)

30 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: [parent_is_real_numerical(R) for R in [RIF, RBF, CIF, CBF]]
[False, False, False, False]

[Link].py_scalar_parent(py_type)
Returns the Sage equivalent of the given python type, if one exists. If there is no equivalent, return None.
EXAMPLES:

sage: from [Link] import py_scalar_parent

sage: py_scalar_parent(int)
Integer Ring
sage: py_scalar_parent(long) # py2
Integer Ring
sage: py_scalar_parent(float)
Real Double Field
sage: py_scalar_parent(complex)
Complex Double Field
sage: py_scalar_parent(bool)
Integer Ring
sage: py_scalar_parent(dict),
(None,)

sage: import fractions

sage: py_scalar_parent([Link])
Rational Field

sage: import numpy

sage: py_scalar_parent(numpy.int16)
Integer Ring
sage: py_scalar_parent(numpy.int32)
Integer Ring
sage: py_scalar_parent(numpy.uint64)
Integer Ring

sage: py_scalar_parent([Link])
Real Double Field
sage: py_scalar_parent([Link])
Real Double Field

sage: py_scalar_parent([Link])
Complex Double Field

sage: import gmpy2

sage: py_scalar_parent([Link])
Integer Ring
sage: py_scalar_parent([Link])
Rational Field
sage: py_scalar_parent([Link])
Real Double Field
sage: py_scalar_parent([Link])
Complex Double Field

[Link].py_scalar_to_element(x)
Convert x to a Sage Element if possible.
If x was already an Element or if there is no obvious conversion possible, just return x itself.
EXAMPLES:

5.1. The coercion model 31

Sage Reference Manual: Coercion, Release 9.0

sage: from [Link] import py_scalar_to_element

sage: x = py_scalar_to_element(42)
sage: x, parent(x)
(42, Integer Ring)
sage: x = py_scalar_to_element(int(42))
sage: x, parent(x)
(42, Integer Ring)
sage: x = py_scalar_to_element(long(42))
sage: x, parent(x)
(42, Integer Ring)
sage: x = py_scalar_to_element(float(42))
sage: x, parent(x)
(42.0, Real Double Field)
sage: x = py_scalar_to_element(complex(42))
sage: x, parent(x)
(42.0, Complex Double Field)
sage: py_scalar_to_element('hello')
'hello'

sage: from fractions import Fraction

sage: f = Fraction(int(2^100), int(3^100))
sage: py_scalar_to_element(f)
1267650600228229401496703205376/515377520732011331036461129765621272702107522001

Note that bools are converted to 0 or 1:

sage: py_scalar_to_element(False), py_scalar_to_element(True)

(0, 1)

Test gmpy2’s types:

sage: import gmpy2

sage: x = py_scalar_to_element([Link](42))
sage: x, parent(x)
(42, Integer Ring)
sage: x = py_scalar_to_element([Link]('3/4'))
sage: x, parent(x)
(3/4, Rational Field)
sage: x = py_scalar_to_element([Link](42.57))
sage: x, parent(x)
(42.57, Real Double Field)
sage: x = py_scalar_to_element([Link](int(42), int(42)))
sage: x, parent(x)
(42.0 + 42.0*I, Complex Double Field)

Test compatibility with py_scalar_parent():

sage: from [Link] import py_scalar_parent

sage: elt = [True, int(42), long(42), float(42), complex(42)]
sage: for x in elt:
....: assert py_scalar_parent(type(x)) == py_scalar_to_element(x).parent()

sage: import numpy

sage: elt = [numpy.int8('-12'), numpy.uint8('143'),
....: numpy.int16('-33'), numpy.uint16('122'),
....: numpy.int32('-19'), numpy.uint32('44'),
....: numpy.int64('-3'), numpy.uint64('552'),
(continues on next page)

32 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

....: numpy.float16('-1.23'), numpy.float32('-2.22'),
....: numpy.float64('-3.412'), numpy.complex64(1.2+I),
....: numpy.complex128(-2+I)]
sage: for x in elt:
....: assert py_scalar_parent(type(x)) == py_scalar_to_element(x).parent()

sage: elt = [[Link](42), [Link]('3/4'),

....: [Link](42.57), [Link](int(42), int(42))]
sage: for x in elt:
....: assert py_scalar_parent(type(x)) == py_scalar_to_element(x).parent()

5.2 Coerce actions

class [Link].coerce_actions.ActOnAction
Bases: [Link].coerce_actions.GenericAction
Class for actions defined via the _act_on_ method.
class [Link].coerce_actions.ActedUponAction
Bases: [Link].coerce_actions.GenericAction
Class for actions defined via the _acted_upon_ method.
class [Link].coerce_actions.GenericAction
Bases: [Link]
codomain()
Returns the “codomain” of this action, i.e. the Parent in which the result elements live. Typically, this
should be the same as the acted upon set.
EXAMPLES:
Note that coerce actions should only be used inside of the coercion model. For this test, we need to strongly
reference the domains, for otherwise they could be garbage collected, giving rise to random errors (see trac
ticket #18157).

sage: M = MatrixSpace(ZZ,2)
sage: A = [Link].coerce_actions.ActedUponAction(M, Cusps, True)
sage: [Link]()
Set P^1(QQ) of all cusps

sage: S3 = SymmetricGroup(3)
sage: QQxyz = QQ['x,y,z']
sage: A = [Link].coerce_actions.ActOnAction(S3, QQxyz, False)
sage: [Link]()
Multivariate Polynomial Ring in x, y, z over Rational Field

class [Link].coerce_actions.IntegerAction
Bases: [Link]
Abstract base class representing some action by integers on something. Here, “integer” is defined loosely in the
“duck typing” sense.
INPUT:
• Z – a type or parent representing integers

5.2. Coerce actions 33

Sage Reference Manual: Coercion, Release 9.0

For the other arguments, see Action.

Note: This class is used internally in Sage’s coercion model. Outside of the coercion model, special precautions
are needed to prevent domains of the action from being garbage collected.

class [Link].coerce_actions.IntegerMulAction
Bases: [Link].coerce_actions.IntegerAction
Implement the action 𝑛 · 𝑎 = 𝑎 + 𝑎 + ... + 𝑎 via repeated doubling.
Both addition and negation must be defined on the set 𝑀 .
INPUT:
• Z – a type or parent representing integers
• M – a ZZ-module
• m – (optional) an element of M
EXAMPLES:

sage: from [Link].coerce_actions import IntegerMulAction

sage: R.<x> = QQ['x']
sage: act = IntegerMulAction(ZZ, R)
sage: act(5, x)
5*x
sage: act(0, x)
0
sage: act(-3, x-1)
-3*x + 3

class [Link].coerce_actions.IntegerPowAction
Bases: [Link].coerce_actions.IntegerAction
The right action a ^ n = a * a * ... * a where 𝑛 is an integer.
The action is implemented using the _pow_int method on elements.
INPUT:
• Z – a type or parent representing integers
• M – a parent whose elements implement _pow_int
• m – (optional) an element of M
EXAMPLES:

sage: from [Link].coerce_actions import IntegerPowAction

sage: R.<x> = LaurentSeriesRing(QQ)
sage: act = IntegerPowAction(ZZ, R)
sage: act(x, 5)
x^5
sage: act(x, -2)
x^-2
sage: act(x, int(5))
x^5

class [Link].coerce_actions.LeftModuleAction
Bases: [Link].coerce_actions.ModuleAction

34 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

class [Link].coerce_actions.ModuleAction
Bases: [Link]
Module action.
See also:
This is an abstract class, one must actually instantiate a LeftModuleAction or a RightModuleAction.
INPUT:
• G – the actor, an instance of Parent.
• S – the object that is acted upon.
• g – optional, an element of G.
• a – optional, an element of S.
• check – if True (default), then there will be no consistency tests performed on sample elements.
NOTE:
By default, the sample elements of S and G are obtained from an_element(), which relies on the implemen-
tation of an _an_element_() method. This is not always available. But usually, the action is only needed
when one already has two elements. Hence, by trac ticket #14249, the coercion model will pass these two
elements to the ModuleAction constructor.
The actual action is implemented by the _rmul_ or _lmul_ function on its elements. We must, however,
be very particular about what we feed into these functions, because they operate under the assumption that the
inputs lie exactly in the base ring and may segfault otherwise. Thus we handle all possible base extensions
manually here.
codomain()
The codomain of self, which may or may not be equal to the domain.
EXAMPLES:
Note that coerce actions should only be used inside of the coercion model. For this test, we need to strongly
reference the domains, for otherwise they could be garbage collected, giving rise to random errors (see trac
ticket #18157).

sage: from [Link].coerce_actions import LeftModuleAction

sage: ZZxyz = ZZ['x,y,z']
sage: A = LeftModuleAction(QQ, ZZxyz)
sage: [Link]()
Multivariate Polynomial Ring in x, y, z over Rational Field

domain()
The domain of self, which is the module that is being acted on.
EXAMPLES:
Note that coerce actions should only be used inside of the coercion model. For this test, we need to strongly
reference the domains, for otherwise they could be garbage collected, giving rise to random errors (see trac
ticket #18157).

sage: from [Link].coerce_actions import LeftModuleAction

sage: ZZxyz = ZZ['x,y,z']
sage: A = LeftModuleAction(QQ, ZZxyz)
sage: [Link]()
Multivariate Polynomial Ring in x, y, z over Integer Ring

5.2. Coerce actions 35

Sage Reference Manual: Coercion, Release 9.0

class [Link].coerce_actions.PyScalarAction
Bases: [Link]
class [Link].coerce_actions.RightModuleAction
Bases: [Link].coerce_actions.ModuleAction
[Link].coerce_actions.detect_element_action(X, Y, X_on_left, X_el=None,
Y_el=None)
Return an action of X on Y as defined by elements of X, if any.
EXAMPLES:
Note that coerce actions should only be used inside of the coercion model. For this test, we need to strongly
reference the domains, for otherwise they could be garbage collected, giving rise to random errors (see trac
ticket #18157).

sage: from [Link].coerce_actions import detect_element_action

sage: ZZx = ZZ['x']
sage: M = MatrixSpace(ZZ,2)
sage: detect_element_action(ZZx, ZZ, False)
Left scalar multiplication by Integer Ring on Univariate Polynomial Ring in x
˓→over Integer Ring

sage: detect_element_action(ZZx, QQ, True)

Right scalar multiplication by Rational Field on Univariate Polynomial Ring in x
˓→over Integer Ring

sage: detect_element_action(Cusps, M, False)

Left action by Full MatrixSpace of 2 by 2 dense matrices over Integer Ring on Set
˓→P^1(QQ) of all cusps

sage: detect_element_action(Cusps, M, True),

(None,)
sage: detect_element_action(ZZ, QQ, True),
(None,)

5.3 Coerce maps

class [Link].coerce_maps.CCallableConvertMap_class
Bases: [Link]
class [Link].coerce_maps.CallableConvertMap
Bases: [Link]
This lets one easily create maps from any callable object.
This is especially useful to create maps from bound methods.
EXAMPLES:

sage: from [Link].coerce_maps import CallableConvertMap

sage: def foo(P, x): return x/2
sage: f = CallableConvertMap(ZZ, QQ, foo)
sage: f(3)
3/2
sage: f
Conversion via foo map:
From: Integer Ring
To: Rational Field

Create a homomorphism from R to R+ viewed as additive groups.

36 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

sage: f = CallableConvertMap(RR, RR, exp, parent_as_first_arg=False)

sage: f(0)
1.00000000000000
sage: f(1)
2.71828182845905
sage: f(-3)
0.0497870683678639

class [Link].coerce_maps.DefaultConvertMap
Bases: [Link]
This morphism simply calls the codomain’s element_constructor method, passing in the codomain as the first
argument.
EXAMPLES:

sage: QQ[['x']].coerce_map_from(QQ)
Coercion map:
From: Rational Field
To: Power Series Ring in x over Rational Field

class [Link].coerce_maps.DefaultConvertMap_unique
Bases: [Link].coerce_maps.DefaultConvertMap
This morphism simply defers action to the codomain’s element_constructor method, WITHOUT passing in the
codomain as the first argument.
This is used for creating elements that don’t take a parent as the first argument to their __init__ method,
for example, Integers, Rationals, Algebraic Reals. . . all have a unique parent. It is also used when the ele-
ment_constructor is a bound method (whose self argument is assumed to be bound to the codomain).
class [Link].coerce_maps.ListMorphism
Bases: [Link]
class [Link].coerce_maps.NamedConvertMap
Bases: [Link]
This is used for creating elements via the _xxx_ methods.
For example, many elements implement an _integer_ method to convert to ZZ, or a _rational_ method to convert
to QQ.
method_name
class [Link].coerce_maps.TryMap
Bases: [Link]
[Link].coerce_maps.test_CCallableConvertMap(domain, name=None)
For testing CCallableConvertMap_class.

5.4 Coercion via construction functors

class [Link]
Bases: [Link]
Algebraic Closure.
EXAMPLES:

5.4. Coercion via construction functors 37

Sage Reference Manual: Coercion, Release 9.0

sage: F = [Link]()[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.
class [Link](polys, names, embed-
dings=None, struc-
tures=None, cyclo-
tomic=None, precs=None,
implementations=None,
**kwds)
Bases: [Link]
Algebraic extension (univariate polynomial ring modulo principal ideal).
EXAMPLES:

sage: K.<a> = NumberField(x^3+x^2+1)

sage: F = [Link]()[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 [Link](...):

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 = [Link]()[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

sage: [Link]() is K
True

expand()
Decompose the functor 𝐹 into sub-functors, whose product returns 𝐹 .

38 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

EXAMPLES:

sage: P.<x> = QQ[]

sage: K.<a> = NumberField(x^3-5,embedding=0)
sage: L.<b> = [Link](x^2+a)
sage: F,R = [Link]()
sage: prod([Link]())(R) == L
True
sage: K = NumberField([x^2-2, x^2-3],'a')
sage: F, R = [Link]()
sage: F
AlgebraicExtensionFunctor
sage: L = [Link](); 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, prefix='z'); a = [Link]()

sage: l = GF(3^3, prefix='z'); b = [Link]()
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, prefix='z'); c = [Link]()

sage: (a+b)+c == a+(b+c) # indirect doctest
True
sage: from [Link] import pushout
sage: n = pushout(k, l)
sage: o = pushout(l, m)
sage: q = pushout(n, o)
(continues on next page)

5.4. Coercion via construction functors 39

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

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 with b = -0.
˓→2588190451025208? + 0.9659258262890683?*I

sage: pushout(M1['x'],M2['x'])
Univariate Polynomial Ring in x over Number Field in b with defining
˓→polynomial x^8 - x^4 + 1 with b = -0.2588190451025208? + 0.9659258262890683?

˓→*I

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 with a = -0.6299605249474365? + 1.

˓→091123635971722?*I, Number Field in b with defining polynomial x^6 - 2 with

˓→b = 1.122462048309373?)

class [Link](box)
Bases: [Link]
Construction functor obtained from any callable object.
EXAMPLES:

sage: from [Link] 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'])
polynomial ring, over a field, global ordering
// coefficients: QQ
// number of vars : 1
(continues on next page)

40 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

// block 1 : ordering lp
// : names t
// block 2 : ordering C
sage: FG == FS
False
sage: FG == loads(dumps(FG))
True

class [Link](p, prec, extras=None)

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

commutes(other)
Completion commutes with fraction fields.
EXAMPLES:

sage: F1 = Zp(5).construction()[0]
sage: F2 = [Link]()[0]
sage: [Link](F2)
True

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.
EXAMPLES:

5.4. Coercion via construction functors 41

Sage Reference Manual: Coercion, Release 9.0

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

class [Link](*args)
Bases: [Link]
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 [Link] import CompositeConstructionFunctor

sage: F = CompositeConstructionFunctor([Link]()[0],ZZ['x'].
˓→construction()[0],[Link]()[0],ZZ['y'].construction()[0])

sage: F
Poly[y](FractionField(Poly[x](FractionField(...))))
sage: F == loads(dumps(F))
True
sage: F == CompositeConstructionFunctor(*[Link])
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 GF2X)

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 [Link] import CompositeConstructionFunctor

sage: F = CompositeConstructionFunctor([Link]()[0],ZZ['x'].
˓→construction()[0],[Link]()[0],ZZ['y'].construction()[0])

sage: F
Poly[y](FractionField(Poly[x](FractionField(...))))
sage: prod([Link]()) == F
True

class [Link]
Bases: [Link]
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.

42 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

In addition to the class Functor, construction functors provide rules for combining and merging construc-
tions. 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 = [Link]()
sage: F1
FractionField
sage: R
Integer Ring
sage: F2, R = (ZZ['x']).construction()
sage: F2
Poly[x]
sage: R
Integer Ring
sage: F3 = [Link](F1)
sage: F3
Poly[x](FractionField(...))
sage: F3(R)
Univariate Polynomial Ring in x over Rational Field
sage: from [Link] 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 = ([Link](15*ZZ)).construction()
sage: Q15
QuotientFunctor
sage: Q35, R = ([Link](35*ZZ)).construction()
sage: Q35
QuotientFunctor
sage: [Link](Q35)
QuotientFunctor
sage: [Link](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 = [Link]()[0]; F
MPoly[x,y]
sage: A.<a,b> = GF(5)[]
sage: f = [Link]([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
(continues on next page)

5.4. Coercion via construction functors 43

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

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

common_base(other_functor, self_bases, other_bases)

This function is called by pushout() when no common parent is found in the construction tower.

Note: The main use is for multivariate construction functors, which use this function to implement
recursion for pushout().

INPUT:
• other_functor – a construction functor.
• self_bases – the arguments passed to this functor.
• other_bases – the arguments passed to the functor other_functor.
OUTPUT:
Nothing, since a CoercionException is raised.

Note: Overload this function in derived class, see e.e. MultivariateConstructionFunctor.

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 = [Link]()[0]
sage: P = ZZ['t'].construction()[0]
sage: [Link](P)
False
sage: [Link](F)
False
sage: [Link](F)
False

expand()
Decompose self into a list of construction functors.
NOTE:
The default is to return the list only containing self.
EXAMPLES:

44 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

sage: F = [Link]()[0]
sage: [Link]()
[FractionField]
sage: Q = [Link](2).construction()[0]
sage: [Link]()
[QuotientFunctor]
sage: P = ZZ['t'].construction()[0]
sage: FP = F*P
sage: [Link]()
[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 = [Link]()[0]
sage: P = ZZ['t'].construction()[0]
sage: [Link](F)
FractionField
sage: [Link](P)
sage: [Link](F)
sage: [Link](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.

class [Link]
Bases: [Link]
Construction functor for fraction fields.
EXAMPLES:

sage: F = [Link]()[0]
sage: F
FractionField
sage: [Link]()
Category of integral domains
sage: [Link]()
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
(continues on next page)

5.4. Coercion via construction functors 45

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: P.<x,y> = QQ[]
sage: f = [Link]([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)
sage: F == loads(dumps(F))
True

class [Link]
Bases: [Link]
A construction functor that is the identity functor.
class [Link](gens, order, implementa-
tion)
Bases: [Link]
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 𝑣1 , ..., 𝑣𝑛 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: [Link]()
[InfPoly{[a,b], "lex", "dense"},
Univariate Polynomial Ring in t over Integer Ring]
sage: type(_[0])
<class '[Link]'>
sage: B.<x,y,a_3,a_1> = PolynomialRing(QQ, order='lex')
sage: [Link]()
(MPoly[x,y,a_3,a_1], Rational Field)
sage: [Link]()[0]*[Link]()[0]
InfPoly{[a,b], "lex", "dense"}(MPoly[x,y](...))

Apparently the variables 𝑎1 , 𝑎3 of the polynomial ring are merged with the variables 𝑎0 , 𝑎1 , 𝑎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: [Link]()[0]*PolynomialRing(QQ,names=['x','y','a_3','a_1']).
˓→construction()[0]

Traceback (most recent call last):

(continues on next page)

46 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

...
CoercionException: Incompatible term orders lex, degrevlex

In an infinite polynomial ring with generator 𝑎* , the variable 𝑎3 will always be greater than the variable 𝑎1 .
Hence, the orders are incompatible in the next example as well:

sage: [Link]()[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 𝑥, 𝑦 should be greater or smaller than
the variables 𝑏* :

sage: [Link]()[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)

𝑋 and 𝑌 have an overlapping generators 𝑥* , 𝑦* . Since the default lexicographic order is used in both rings, it
gives rise to isomorphic sub-monoids in both 𝑋 and 𝑌 . They are merged in the pushout, which also yields a
common parent for doing arithmetic:

sage: P = [Link](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 𝐹 into sub-functors, whose product returns 𝐹 .
EXAMPLES:

sage: F = InfinitePolynomialRing(QQ, ['x','y'],order='degrevlex').

˓→construction()[0]; F

InfPoly{[x,y], "degrevlex", "dense"}

sage: [Link]()
(continues on next page)

5.4. Coercion via construction functors 47

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

[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: [Link]()
[InfPoly{[z], "degrevlex", "dense"},
InfPoly{[y], "degrevlex", "dense"},
InfPoly{[x], "degrevlex", "dense"}]
sage: prod([Link]())==F
True

merge(other)
Merge two construction functors of infinite polynomial rings, regardless of monomial order and imple-
mentation.
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: [Link]()
[InfPoly{[x,y], "lex", "sparse"}, Rational Field]
sage: [Link]()
[InfPoly{[x,y], "degrevlex", "dense"}, Rational Field]
sage: [Link]()[0].merge([Link]()[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 [Link](var, multi_variate=False)

Bases: [Link]
Construction functor for Laurent polynomial rings.
EXAMPLES:
sage: L.<t> = LaurentPolynomialRing(ZZ)
sage: F = [Link]()[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 = [Link]([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

(continues on next page)

48 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

Defn: x |--> x + 2*y
y |--> 3*x - y
sage: F(f)(x*F(P).gen()^-2+y*F(P).gen()^3)
(x + 2*y)*t^-2 + (3*x - y)*t^3

merge(other)
Two Laurent polynomial construction functors merge if the variable names coincide. The result is multi-
variate if one of the arguments is multivariate.
EXAMPLES:

sage: from [Link] import LaurentPolynomialFunctor

sage: F1 = LaurentPolynomialFunctor('t')
sage: F2 = LaurentPolynomialFunctor('t', multi_variate=True)
sage: [Link](F2)
LaurentPolynomialFunctor
sage: [Link](F2)(LaurentPolynomialRing(GF(2),'a'))
Multivariate Laurent Polynomial Ring in a, t over Finite Field of size 2
sage: [Link](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 [Link](nrows, ncols, is_sparse=False)

Bases: [Link]
A construction functor for matrices over rings.
EXAMPLES:

sage: MS = MatrixSpace(ZZ,2, 3)
sage: F = [Link]()[0]; F
MatrixFunctor
sage: MS = MatrixSpace(ZZ,2)
sage: F = [Link]()[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 = [Link]([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.
EXAMPLES:

5.4. Coercion via construction functors 49

Sage Reference Manual: Coercion, Release 9.0

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: [Link](F2)
sage: [Link](F3)
MatrixFunctor
sage: F13 = [Link](F3)
sage: F13.is_sparse
False
sage: F1.is_sparse
False
sage: F3.is_sparse
True
sage: [Link](F3).is_sparse
True

class [Link](vars, term_order)

Bases: [Link]
A constructor for multivariate polynomial rings.
EXAMPLES:

sage: P.<x,y> = ZZ[]

sage: F = [Link]()[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 = [Link]([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: [Link]()
[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
(continues on next page)

50 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

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: [Link](0) + [Link](0)
2*x0

merge(other)
Merge self with another construction functor, or return None.
EXAMPLES:

sage: F = [Link](['x','y'], None)

sage: G = [Link](['t'], None)
sage: [Link](G) is None
True
sage: [Link](F)
MPoly[x,y]

class [Link]
Bases: [Link]
An abstract base class for functors that take multiple inputs (e.g. Cartesian products).
common_base(other_functor, self_bases, other_bases)
This function is called by pushout() when no common parent is found in the construction tower.
INPUT:
• other_functor – a construction functor.
• self_bases – the arguments passed to this functor.
• other_bases – the arguments passed to the functor other_functor.
OUTPUT:
A parent.
If no common base is found a [Link].coerce_exceptions.CoercionException
is raised.

Note: Overload this function in derived class, see e.g. MultivariateConstructionFunctor.

class [Link](gens, domain)

Bases: [Link]
EXAMPLES:

sage: from [Link] import PermutationGroupFunctor

sage: PF = PermutationGroupFunctor([PermutationGroupElement([(1,2)])], [1,2]); PF
PermutationGroupFunctor[(1,2)]

5.4. Coercion via construction functors 51

Sage Reference Manual: Coercion, Release 9.0

gens()
EXAMPLES:

sage: P1 = PermutationGroup([[(1,2)]])
sage: PF, P = [Link]()
sage: [Link]()
[(1,2)]

merge(other)
Merge self with another construction functor, or return None.
EXAMPLES:

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

class [Link](var, multi_variate=False,

sparse=False)
Bases: [Link]
Construction functor for univariate polynomial rings.
EXAMPLES:

sage: P = ZZ['t'].construction()[0]
sage: P(GF(3))
Univariate Polynomial Ring in t over Finite Field of size 3
sage: P == loads(dumps(P))
True
sage: R.<x,y> = GF(5)[]
sage: f = [Link]([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 = [Link]()
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.

52 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

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.
EXAMPLES:

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

class [Link](I, names=None, as_field=False)

Bases: [Link]
Construction functor for quotient rings.
NOTE:
The functor keeps track of variable names.
EXAMPLES:

sage: P.<x,y> = ZZ[]

sage: Q = [Link]([x^2+y^2]*P)
sage: F = [Link]()[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.
EXAMPLES:

sage: P.<x> = QQ[]

sage: Q1 = [Link]([(x^2+1)^2*(x^2-3)])
sage: Q2 = [Link]([(x^2+1)^2*(x^5+3)])
sage: from [Link] 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

5.4. Coercion via construction functors 53

Sage Reference Manual: Coercion, Release 9.0

class [Link](basis)
Bases: [Link]
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 = [Link]([(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 = [Link]()[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.
EXAMPLES:
sage: M = GF(5)^3
sage: S1 = [Link]([(1,2,3),(4,5,6)])
sage: S2 = [Link]([(2,2,3)])
sage: F1 = [Link]()[0]
sage: F2 = [Link]()[0]
sage: [Link](F2)
SubspaceFunctor
sage: [Link](F2)(GF(5)^3) == S1+S2
True
sage: [Link](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]

class [Link](n, is_sparse=False, in-

ner_product_matrix=None)
Bases: [Link]
A construction functor for free modules over commutative rings.
EXAMPLES:
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 GF2X)

54 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

merge(other)
Two constructors of free modules merge, if the module ranks and the inner products coincide. If both have
explicitly given inner product matrices, they must coincide as well.
EXAMPLES:
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]'

[Link].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.

5.4. Coercion via construction functors 55

Sage Reference Manual: Coercion, Release 9.0

EXAMPLES:

sage: from [Link] 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)]

[Link].expand_tower(tower)
An auxiliary function that is used in pushout().
INPUT:
A construction tower as returned by construction_tower().
OUTPUT:
A new construction tower with all the construction functors expanded.
EXAMPLES:

sage: from [Link] import construction_tower, expand_tower

sage: construction_tower(QQ['x,y,z'])
[(None, Multivariate Polynomial Ring in x, y, z over Rational Field),
(MPoly[x,y,z], Rational Field),
(FractionField, Integer Ring)]
sage: expand_tower(construction_tower(QQ['x,y,z']))
[(None, Multivariate Polynomial Ring in x, y, z over Rational Field),
(MPoly[z], Univariate Polynomial Ring in y over Univariate Polynomial Ring in x
˓→over Rational Field),

(MPoly[y], Univariate Polynomial Ring in x over Rational Field),

(MPoly[x], Rational Field),
(FractionField, Integer Ring)]

[Link](R, S)
Given a pair of objects 𝑅 and 𝑆, try to construct a reasonable object 𝑌 and return maps such that canonically
𝑅 ← 𝑌 → 𝑆.
ALGORITHM:
This incorporates the idea of functors discussed at Sage Days 4. Every object 𝑅 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 objects (with the associated functors) the “tower” of 𝑅. The construction method
is used to create the tower.
Given two objects 𝑅 and 𝑆, try to find a common initial object 𝑍. If the towers of 𝑅 and 𝑆 meet, let 𝑍 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 unam-
biguous order, popping elements off the top of one or the other tower as we apply them to 𝑍.
• If the functors are of 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.

56 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

– Otherwise fail due to ambiguity.

The algorithm assumes by default that when a construction 𝐹 is applied to an object 𝑋, the object 𝐹 (𝑋) admits
a coercion map from 𝑋. However, the algorithm can also handle the case where 𝐹 (𝑋) has a coercion map to 𝑋
instead. In this case, the attribute coercion_reversed of the class implementing 𝐹 should be set to True.
EXAMPLES:
Here our “towers” are 𝑅 = 𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒7 (𝐹 𝑟𝑎𝑐(Z)) and 𝐹 𝑟𝑎𝑐(𝑃 𝑜𝑙𝑦𝑥 (Z)), which give us
𝐹 𝑟𝑎𝑐(𝑃 𝑜𝑙𝑦𝑥 (𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒7 (𝐹 𝑟𝑎𝑐(Z)))):

sage: from [Link] 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

A construction with coercion_reversed = True (currently only the SubspaceFunctor construc-

tion) is only applied if it leads to a valid coercion:

5.4. Coercion via construction functors 57

Sage Reference Manual: Coercion, Release 9.0

sage: A = ZZ^2
sage: V = span([[1, 2]], QQ)
sage: P = [Link](A, V)
sage: P
Vector space of dimension 2 over Rational Field
sage: P.has_coerce_map_from(A)
True

sage: V = (QQ^3).span([[1, 2, 3/4]])

sage: A = ZZ^3
sage: pushout(A, V)
Vector space of dimension 3 over Rational Field
sage: B = [Link]([[0, 0, 2/3]])
sage: pushout(B, V)
Vector space of degree 3 and dimension 2 over Rational Field
User basis matrix:
[1 2 0]
[0 0 1]

Some more tests with coercion_reversed = True:

sage: from [Link] import ConstructionFunctor

sage: class EvenPolynomialRing(type(QQ['x'])):
....: def __init__(self, base, var):
....: super(EvenPolynomialRing, self).__init__(base, var)
....: self.register_embedding(base[var])
....: def __repr__(self):
....: return "Even Power " + super(EvenPolynomialRing, self).__repr__()
....: def construction(self):
....: return EvenPolynomialFunctor(), [Link]()[self.variable_name()]
....: def _coerce_map_from_(self, R):
....: return [Link]().has_coerce_map_from(R)
sage: class EvenPolynomialFunctor(ConstructionFunctor):
....: rank = 10
....: coercion_reversed = True
....: def __init__(self):
....: ConstructionFunctor.__init__(self, Rings(), Rings())
....: def _apply_functor(self, R):
....: return EvenPolynomialRing([Link](), R.variable_name())
sage: pushout(EvenPolynomialRing(QQ, 'x'), ZZ)
Even Power Univariate Polynomial Ring in x over Rational Field
sage: pushout(EvenPolynomialRing(QQ, 'x'), QQ)
Even Power Univariate Polynomial Ring in x over Rational Field
sage: pushout(EvenPolynomialRing(QQ, 'x'), RR)
Even Power Univariate Polynomial Ring in x over Real Field with 53 bits of
˓→precision

sage: pushout(EvenPolynomialRing(QQ, 'x'), ZZ['x'])

Univariate Polynomial Ring in x over Rational Field
sage: pushout(EvenPolynomialRing(QQ, 'x'), QQ['x'])
Univariate Polynomial Ring in x over Rational Field
sage: pushout(EvenPolynomialRing(QQ, 'x'), RR['x'])
Univariate Polynomial Ring in x over Real Field with 53 bits of precision

sage: pushout(EvenPolynomialRing(QQ, 'x'), EvenPolynomialRing(QQ, 'x'))

Even Power Univariate Polynomial Ring in x over Rational Field
sage: pushout(EvenPolynomialRing(QQ, 'x'), EvenPolynomialRing(RR, 'x'))
(continues on next page)

58 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

Even Power Univariate Polynomial Ring in x over Real Field with 53 bits of
˓→precision

sage: pushout(EvenPolynomialRing(QQ, 'x')^2, RR^2)

Ambient free module of rank 2 over the principal ideal domain Even Power
˓→Univariate Polynomial Ring in x over Real Field with 53 bits of precision

sage: pushout(EvenPolynomialRing(QQ, 'x')^2, RR['x']^2)

Ambient free module of rank 2 over the principal ideal domain Univariate
˓→Polynomial Ring in x over Real Field with 53 bits of precision

Some more tests related to univariate/multivariate constructions. We consider a generalization of polynomial

rings, where in addition to the coefficient ring 𝐶 we also specify an additive monoid 𝐸 for the exponents of the
indeterminate. In particular, the elements of such a parent are given by
𝐼
∑︁
𝑐𝑖 𝑋 𝑒𝑖
𝑖=0

with 𝑐𝑖 ∈ 𝐶 and 𝑒𝑖 ∈ 𝐸. We define

sage: class GPolynomialRing(Parent):
....: def __init__(self, coefficients, var, exponents):
....: [Link] = coefficients
....: [Link] = var
....: [Link] = exponents
....: super(GPolynomialRing, self).__init__(category=Rings())
....: def _repr_(self):
....: return 'Generalized Polynomial Ring in %s^(%s) over %s' % (
....: [Link], [Link], [Link])
....: def construction(self):
....: return GPolynomialFunctor([Link], [Link]), self.
˓→coefficients

....: def _coerce_map_from_(self, R):

....: return [Link].has_coerce_map_from(R)

and
sage: class GPolynomialFunctor(ConstructionFunctor):
....: rank = 10
....: def __init__(self, var, exponents):
....: [Link] = var
....: [Link] = exponents
....: ConstructionFunctor.__init__(self, Rings(), Rings())
....: def _repr_(self):
....: return 'GPoly[%s^(%s)]' % ([Link], [Link])
....: def _apply_functor(self, coefficients):
....: return GPolynomialRing(coefficients, [Link], [Link])
....: def merge(self, other):
....: if isinstance(other, GPolynomialFunctor) and [Link] == [Link]:
....: exponents = pushout([Link], [Link])
....: return GPolynomialFunctor([Link], exponents)

We can construct a parent now in two different ways:

sage: GPolynomialRing(QQ, 'X', ZZ)
Generalized Polynomial Ring in X^(Integer Ring) over Rational Field
sage: GP_ZZ = GPolynomialFunctor('X', ZZ); GP_ZZ
(continues on next page)

5.4. Coercion via construction functors 59

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

GPoly[X^(Integer Ring)]
sage: GP_ZZ(QQ)
Generalized Polynomial Ring in X^(Integer Ring) over Rational Field

Since the construction

sage: GP_ZZ(QQ).construction()
(GPoly[X^(Integer Ring)], Rational Field)

uses the coefficient ring, we have the usual coercion with respect to this parameter:
sage: pushout(GP_ZZ(ZZ), GP_ZZ(QQ))
Generalized Polynomial Ring in X^(Integer Ring) over Rational Field
sage: pushout(GP_ZZ(ZZ['t']), GP_ZZ(QQ))
Generalized Polynomial Ring in X^(Integer Ring) over Univariate Polynomial Ring
˓→in t over Rational Field

sage: pushout(GP_ZZ(ZZ['a,b']), GP_ZZ(ZZ['b,c']))

Generalized Polynomial Ring in X^(Integer Ring)
over Multivariate Polynomial Ring in a, b, c over Integer Ring
sage: pushout(GP_ZZ(ZZ['a,b']), GP_ZZ(QQ['b,c']))
Generalized Polynomial Ring in X^(Integer Ring)
over Multivariate Polynomial Ring in a, b, c over Rational Field
sage: pushout(GP_ZZ(ZZ['a,b']), GP_ZZ(ZZ['c,d']))
Traceback (most recent call last):
...
CoercionException: ('Ambiguous Base Extension', ...)

sage: GP_QQ = GPolynomialFunctor('X', QQ)

sage: pushout(GP_ZZ(ZZ), GP_QQ(ZZ))
Generalized Polynomial Ring in X^(Rational Field) over Integer Ring
sage: pushout(GP_QQ(ZZ), GP_ZZ(ZZ))
Generalized Polynomial Ring in X^(Rational Field) over Integer Ring

sage: GP_ZZt = GPolynomialFunctor('X', ZZ['t'])

sage: pushout(GP_ZZt(ZZ), GP_QQ(ZZ))
Generalized Polynomial Ring in X^(Univariate Polynomial Ring in t
over Rational Field) over Integer Ring

sage: pushout(GP_ZZ(ZZ), GP_QQ(QQ))

Generalized Polynomial Ring in X^(Rational Field) over Rational Field
sage: pushout(GP_ZZ(QQ), GP_QQ(ZZ))
Generalized Polynomial Ring in X^(Rational Field) over Rational Field
sage: pushout(GP_ZZt(QQ), GP_QQ(ZZ))
Generalized Polynomial Ring in X^(Univariate Polynomial Ring in t
over Rational Field) over Rational Field
sage: pushout(GP_ZZt(ZZ), GP_QQ(QQ))
Generalized Polynomial Ring in X^(Univariate Polynomial Ring in t
over Rational Field) over Rational Field
sage: pushout(GP_ZZt(ZZ['a,b']), GP_QQ(ZZ['c,d']))
Traceback (most recent call last):
...
CoercionException: ('Ambiguous Base Extension', ...)
sage: pushout(GP_ZZt(ZZ['a,b']), GP_QQ(ZZ['b,c']))
Generalized Polynomial Ring in X^(Univariate Polynomial Ring in t over Rational
˓→Field)

over Multivariate Polynomial Ring in a, b, c over Integer Ring

60 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

Some tests with Cartesian products:

sage: from [Link].cartesian_product import CartesianProduct

sage: A = CartesianProduct((ZZ['x'], QQ['y'], QQ['z']), Sets().
˓→CartesianProducts())

sage: B = CartesianProduct((ZZ['x'], ZZ['y'], ZZ['t']['z']), Sets().

˓→CartesianProducts())

sage: [Link]()
(The cartesian_product functorial construction,
(Univariate Polynomial Ring in x over Integer Ring,
Univariate Polynomial Ring in y over Rational Field,
Univariate Polynomial Ring in z over Rational Field))
sage: pushout(A, B)
The Cartesian product of
(Univariate Polynomial Ring in x over Integer Ring,
Univariate Polynomial Ring in y over Rational Field,
Univariate Polynomial Ring in z over Univariate Polynomial Ring in t over
˓→Rational Field)

sage: pushout(ZZ, cartesian_product([ZZ, QQ]))

Traceback (most recent call last):
...
CoercionException: 'NoneType' object is not iterable

sage: from [Link] import PolynomialFunctor

sage: from [Link].cartesian_product import CartesianProduct
sage: class CartesianProductPoly(CartesianProduct):
....: def __init__(self, polynomial_rings):
....: sort = sorted(polynomial_rings, key=lambda P: P.variable_name())
....: super(CartesianProductPoly, self).__init__(sort, Sets().
˓→CartesianProducts())

....: def vars(self):

....: return tuple(P.variable_name() for P in self.cartesian_factors())
....: def _pushout_(self, other):
....: if isinstance(other, CartesianProductPoly):
....: s_vars = [Link]()
....: o_vars = [Link]()
....: if s_vars == o_vars:
....: return
....: return pushout(CartesianProductPoly(
....: self.cartesian_factors() +
....: tuple(f for f in other.cartesian_factors()
....: if f.variable_name() not in s_vars)),
....: CartesianProductPoly(
....: other.cartesian_factors() +
....: tuple(f for f in self.cartesian_factors()
....: if f.variable_name() not in o_vars)))
....: C = [Link]()
....: if C is None:
....: return
....: elif isinstance(C[0], PolynomialFunctor):
....: return pushout(self, CartesianProductPoly((other,)))

sage: pushout(CartesianProductPoly((ZZ['x'],)),
....: CartesianProductPoly((ZZ['y'],)))
The Cartesian product of
(Univariate Polynomial Ring in x over Integer Ring,
Univariate Polynomial Ring in y over Integer Ring)
(continues on next page)

5.4. Coercion via construction functors 61

Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: pushout(CartesianProductPoly((ZZ['x'], ZZ['y'])),
....: CartesianProductPoly((ZZ['x'], ZZ['z'])))
The Cartesian product of
(Univariate Polynomial Ring in x over Integer Ring,
Univariate Polynomial Ring in y over Integer Ring,
Univariate Polynomial Ring in z over Integer Ring)
sage: pushout(CartesianProductPoly((QQ['a,b']['x'], QQ['y'])),
....: CartesianProductPoly((ZZ['b,c']['x'], SR['z'])))
The Cartesian product of
(Univariate Polynomial Ring in x over
Multivariate Polynomial Ring in a, b, c over Rational Field,
Univariate Polynomial Ring in y over Rational Field,
Univariate Polynomial Ring in z over Symbolic Ring)

sage: pushout(CartesianProductPoly((ZZ['x'],)), ZZ['y'])

The Cartesian product of
(Univariate Polynomial Ring in x over Integer Ring,
Univariate Polynomial Ring in y over Integer Ring)
sage: pushout(QQ['b,c']['y'], CartesianProductPoly((ZZ['a,b']['x'],)))
The Cartesian product of
(Univariate Polynomial Ring in x over
Multivariate Polynomial Ring in a, b over Integer Ring,
Univariate Polynomial Ring in y over
Multivariate Polynomial Ring in b, c over Rational Field)

sage: pushout(CartesianProductPoly((ZZ['x'],)), ZZ)

Traceback (most recent call last):
...
CoercionException: No common base ("join") found for
The cartesian_product functorial construction(...) and None(Integer Ring):
(Multivariate) functors are incompatible.

AUTHORS:
• Robert Bradshaw
• Peter Bruin
• Simon King
• Daniel Krenn
• David Roe
[Link].pushout_lattice(R, S)
Given a pair of objects 𝑅 and 𝑆, try to construct a reasonable object 𝑌 and return maps such that canonically
𝑅 ← 𝑌 → 𝑆.
ALGORITHM:
This is based on the model that arose from much discussion at Sage Days 4. Going up the tower of constructions
of 𝑅 and 𝑆 (e.g. the reals come from the rationals come from the integers), try to find a common parent, and
then try to 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:

62 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

sage: from [Link] import pushout_lattice

sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
sage: [Link]()
Fraction Field of Univariate Polynomial Ring in x over 7-adic Field with capped
˓→relative precision 20

sage: [Link]() is [Link]()

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:
• Robert Bradshaw
[Link].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

5.5 Group, ring, etc. actions on objects

The terminology and notation used is suggestive of groups acting on sets, but this framework can be used for modules,
algebras, etc.
A group action 𝐺 × 𝑆 → 𝑆 is a functor from 𝐺 to Sets.

Warning: An Action object only keeps a weak reference to the underlying set which is acted upon. This
decision was made in trac ticket #715 in order to allow garbage collection within the coercion framework (this is
where actions are mainly used) and avoid memory leaks.
sage: from [Link] import Action
sage: class P: pass
sage: A = Action(P(),P())
sage: import gc
sage: _ = [Link]()
sage: A
<repr(<[Link] at 0x...>) failed: RuntimeError: This action
˓→acted on a set that became garbage collected>

To avoid garbage collection of the underlying set, it is sufficient to create a strong reference to it before the action
is created.
sage: _ = [Link]()
sage: from [Link] import Action
sage: class P: pass
sage: q = P()
sage: A = Action(P(),q)
sage: [Link]()
0
sage: A
Left action by <__main__.P ... at ...> on <__main__.P ... at ...>

5.5. Group, ring, etc. actions on objects 63

Sage Reference Manual: Coercion, Release 9.0

AUTHOR:
• Robert Bradshaw: initial version
class [Link]
Bases: [Link]
The action of G on S.
INPUT:
• G – a parent or Python type
• S – a parent or Python type
• is_left – (boolean, default: True) whether elements of G are on the left
• op – (default: None) operation. This is not used by Action itself, but other classes may use it
G
act(g, x)
This is a consistent interface for acting on x by g, regardless of whether it’s a left or right action.
If needed, g and x are converted to the correct parent.
EXAMPLES:

sage: R.<x> = ZZ []
sage: from [Link].coerce_actions import IntegerMulAction
sage: A = IntegerMulAction(ZZ, R, True) # Left action
sage: [Link](5, x)
5*x
sage: [Link](int(5), x)
5*x
sage: A = IntegerMulAction(ZZ, R, False) # Right action
sage: [Link](5, x)
5*x
sage: [Link](int(5), x)
5*x

actor()
codomain()
domain()
is_left()
left_domain()
op
operation()
right_domain()
class [Link]
Bases: [Link]
The endomorphism defined by the action of one element.
EXAMPLES:

64 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

sage: A = ZZ['x'].get_action(QQ, self_on_left=False, op=[Link])

sage: A
Left scalar multiplication by Rational Field on Univariate Polynomial
Ring in x over Integer Ring
sage: A(1/2)
Action of 1/2 on Univariate Polynomial Ring in x over Integer Ring
under Left scalar multiplication by Rational Field on Univariate
Polynomial Ring in x over Integer Ring.

class [Link]
Bases: [Link]
An action that acts as the inverse of the given action.
EXAMPLES:

sage: V = QQ^3
sage: v = V((1, 2, 3))
sage: cm = get_coercion_model()

sage: a = cm.get_action(V, QQ, [Link])

sage: a
Right scalar multiplication by Rational Field on Vector space of dimension 3 over
˓→Rational Field

sage: ~a
Right inverse action by Rational Field on Vector space of dimension 3 over
˓→Rational Field

sage: (~a)(v, 1/3)

(3, 6, 9)

sage: b = cm.get_action(QQ, V, [Link])

sage: b
Left scalar multiplication by Rational Field on Vector space of dimension 3 over
˓→Rational Field

sage: ~b
Left inverse action by Rational Field on Vector space of dimension 3 over
˓→Rational Field

sage: (~b)(1/3, v)
(3, 6, 9)

sage: c = cm.get_action(ZZ, list, [Link])

sage: c
Left action by Integer Ring on <... 'list'>
sage: ~c
Traceback (most recent call last):
...
TypeError: no inverse defined for Left action by Integer Ring on <... 'list'>

codomain()
class [Link]
Bases: [Link]
A precomposed action first applies given maps, and then applying an action to the return values of the maps.
EXAMPLES:
We demonstrate that an example discussed on trac ticket #14711 did not become a problem:

5.5. Group, ring, etc. actions on objects 65

Sage Reference Manual: Coercion, Release 9.0

sage: E = ModularSymbols(11).2
sage: s = E.modular_symbol_rep()
sage: del E,s
sage: import gc
sage: _ = [Link]()
sage: E = ModularSymbols(11).2
sage: v = E.manin_symbol_rep()
sage: c,x = v[0]
sage: y = x.modular_symbol_rep()
sage: coercion_model.get_action(QQ, parent(y), op=[Link])
Left scalar multiplication by Rational Field on Abelian Group of all Formal
˓→Finite Sums over Rational Field

with precomposition on right by Coercion map:

From: Abelian Group of all Formal Finite Sums over Integer Ring
To: Abelian Group of all Formal Finite Sums over Rational Field

codomain()
domain()
left_precomposition
The left map to precompose with, or None if there is no left precomposition map.
right_precomposition
The right map to precompose with, or None if there is no right precomposition map.

5.6 Containers for storing coercion data

This module provides TripleDict and MonoDict. These are structures similar to WeakKeyDictionary
in Python’s weakref module, and are optimized for lookup speed. The keys for TripleDict consist of triples
(k1,k2,k3) and are looked up by identity rather than equality. The keys are stored by weakrefs if possible. If any one
of the components k1, k2, k3 gets garbage collected, then the entry is removed from the TripleDict.
Key components that do not allow for weakrefs are stored via a normal refcounted reference. That means that any
entry stored using a triple (k1,k2,k3) so that none of the k1,k2,k3 allows a weak reference behaves as an entry in a
normal dictionary: Its existence in TripleDict prevents it from being garbage collected.
That container currently is used to store coercion and conversion maps between two parents (trac ticket #715) and to
store homsets of pairs of objects of a category (trac ticket #11521). In both cases, it is essential that the parent structures
remain garbage collectable, it is essential that the data access is faster than with a usual WeakKeyDictionary, and
we enforce the “unique parent condition” in Sage (parent structures should be identical if they are equal).
MonoDict behaves similarly, but it takes a single item as a key. It is used for caching the parents which allow a
coercion map into a fixed other parent (trac ticket #12313).
By trac ticket #14159, MonoDict and TripleDict can be optionally used with weak references on the values.
Note that this kind of dictionary is also used for caching actions and coerce maps. In previous versions of Sage, the
cache was by strong references and resulted in a memory leak in the following example. However, this leak was fixed
by trac ticket #715, using weak references:
sage: K.<t> = GF(2^55)
sage: for i in range(50):
....: a = K.random_element()
....: E = EllipticCurve(j=a)
....: P = E.random_point()
....: Q = 2*P
(continues on next page)

66 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: L = [Partitions(n) for n in range(200)] # purge strong cache in
˓→CachedRepresentation

sage: import gc
sage: n = [Link]()
sage: from [Link].elliptic_curves.ell_finite_field import EllipticCurve_finite_
˓→field

sage: LE = [x for x in gc.get_objects() if isinstance(x, EllipticCurve_finite_field)]

sage: len(LE)
1

class [Link].coerce_dict.MonoDict
Bases: object
This is a hashtable specifically designed for (read) speed in the coercion model.
It differs from a python WeakKeyDictionary in the following important ways:
• Comparison is done using the ‘is’ rather than ‘==’ operator.
• Only weak references to the keys are stored if at all possible. Keys that do not allow for weak
references are stored with a normal refcounted reference.
• The callback of the weak references is safe against recursion, see below.
There are special cdef set/get methods for faster access. It is bare-bones in the sense that not all
dictionary methods are implemented.
IMPLEMENTATION:
It is implemented as a hash table with open addressing, similar to python’s dict.
INPUT:
• data – optional iterable defining initial data, as dict or iterable of (key, value) pairs.
• weak_values – optional bool (default False). If it is true, weak references to the values in
this dictionary will be used, when possible.
EXAMPLES:

sage: from [Link].coerce_dict import MonoDict

sage: L = MonoDict()
sage: a = 'a'; b = 'ab'; c = '-15'
sage: L[a] = 1
sage: L[b] = 2
sage: L[c] = 3

The key is expected to be a unique object. Hence, the item stored for c can not be obtained by
providing another equal string:

sage: L[a]
1
sage: L[b]
2
sage: L[c]
3
sage: L['-15']
Traceback (most recent call last):
...
KeyError: '-15'

5.6. Containers for storing coercion data 67

Sage Reference Manual: Coercion, Release 9.0

Not all features of Python dictionaries are available, but iteration over the dictionary items is possible:

sage: sorted([Link]())
[('-15', 3), ('a', 1), ('ab', 2)]
sage: del L[c]
sage: sorted([Link]())
[('a', 1), ('ab', 2)]
sage: len(L)
2
sage: for i in range(1000):
....: L[i] = i
sage: len(L)
1002
sage: L['a']
1
sage: L['c']
Traceback (most recent call last):
...
KeyError: 'c'

Note that MW also accepts values that do not allow for weak references:

sage: MW[k] = int(5)

sage: MW[k]
5

The following demonstrates that :class:`MonoDict` is safer than

:class:`~[Link]` against recursions created by nested
callbacks; compare :trac:`15069` (the mechanism used now is different, though)::

sage: M = MonoDict()
sage: class A: pass
sage: a = A()
sage: prev = a
sage: for i in range(1000):
....: newA = A()
....: M[prev] = newA
....: prev = newA
sage: len(M)
1000
sage: del a
sage: len(M)
0

The corresponding example with a Python :class:`[Link]`

would result in a too deep recursion during deletion of the dictionary
items::

sage: import weakref

sage: M = [Link]()
sage: a = A()
sage: prev = a
sage: for i in range(1000):
....: newA = A()
....: M[prev] = newA
....: prev = newA
sage: len(M)
1000
(continues on next page)

68 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

(continued from previous page)

sage: del a # py2 -- does not appear to be an issue on Python 3
Exception RuntimeError: 'maximum recursion depth exceeded...' in <function
˓→remove at ...> ignored

sage: len(M) > 0 # py2

True

Check that also in the presence of circular references, :class:`MonoDict`

gets properly collected::

sage: import gc
sage: def count_type(T):
....: return len([c for c in gc.get_objects() if isinstance(c,T)])
sage: _ = [Link]()
sage: N = count_type(MonoDict)
sage: for i in range(100):
....: V = [MonoDict({"id":j+100*i}) for j in range(100)]
....: n= len(V)
....: for i in range(n): V[i][V[(i+1)%n]]=(i+1)%n
....: del V
....: _ = [Link]()
....: assert count_type(MonoDict) == N
sage: count_type(MonoDict) == N
True

AUTHORS:

- Simon King (2012-01)

- Nils Bruin (2012-08)
- Simon King (2013-02)
- Nils Bruin (2013-11)

copy()
Return a copy of this MonoDict as Python dict.
EXAMPLES:

sage: from [Link].coerce_dict import MonoDict

sage: L = MonoDict()
sage: L[1] = 42
sage: [Link]()
{1: 42}

items()
Iterate over the (key, value) pairs of this MonoDict.
EXAMPLES:

sage: from [Link].coerce_dict import MonoDict

sage: L = MonoDict()
sage: L[1] = None
sage: L[2] = True
sage: [Link]()
<generator object at ...>
sage: sorted([Link]())
[(1, None), (2, True)]

class [Link].coerce_dict.MonoDictEraser
Bases: object

5.6. Containers for storing coercion data 69

Sage Reference Manual: Coercion, Release 9.0

Erase items from a MonoDict when a weak reference becomes invalid.

This is of internal use only. Instances of this class will be passed as a callback function when creating a weak
reference.
EXAMPLES:

sage: from [Link].coerce_dict import MonoDict

sage: class A: pass
sage: a = A()
sage: M = MonoDict()
sage: M[a] = 1
sage: len(M)
1
sage: del a
sage: import gc
sage: n = [Link]()
sage: len(M) # indirect doctest
0

AUTHOR:
• Simon King (2012-01)
• Nils Bruin (2013-11)
class [Link].coerce_dict.ObjectWrapper
Bases: object
A simple fast wrapper around a Python object. This is like a 1-element tuple except that it does not keep a
reference to the wrapped object.
class [Link].coerce_dict.TripleDict
Bases: object
This is a hashtable specifically designed for (read) speed in the coercion model.
It differs from a python dict in the following important ways:
• All keys must be sequence of exactly three elements. All sequence types (tuple, list, etc.) map to the same
item.
• Any of the three key components that support weak-refs are stored via a weakref. If any of these compo-
nents gets garbage collected then the entire entry is removed. In that sense, this structure behaves like a
nested WeakKeyDictionary.
• Comparison is done using the ‘is’ rather than ‘==’ operator.
There are special cdef set/get methods for faster access. It is bare-bones in the sense that not all dictionary
methods are implemented.
INPUT:
• data – optional iterable defining initial data, as dict or iterable of (key, value) pairs.
• weak_values – optional bool (default False). If it is true, weak references to the values in this dictionary
will be used, when possible.
IMPLEMENTATION:
It is implemented as a hash table with open addressing, similar to python’s dict.
EXAMPLES:

70 Chapter 5. Modules
 Sage Reference Manual: Coercion, Release 9.0

sage: from [Link].coerce_dict import TripleDict

sage: L = TripleDict()
sage: a = 'a'; b = 'b'; c = 'c'
sage: L[a,b,c] = 1
sage: L[a,b,c]
1
sage: L[c,b,a] = -1
sage: sorted([Link]())
[(('a', 'b', 'c'), 1), (('c', 'b', 'a'), -1)]
sage: del L[a,b,c]
sage: list([Link]())
[(('c', 'b', 'a'), -1)]
sage: len(L)
1
sage: for i in range(1000):
....: L[i,i,i] = i
sage: len(L)
1001
sage: L = TripleDict(L)
sage: L[c,b,a]
-1
sage: L[a,b,c]
Traceback (most recent call last):
...
KeyError: ('a', 'b', 'c')
sage: L[a]
Traceback (most recent call last):
...
KeyError: 'a'
sage: L[a] = 1
Traceback (most recent call last):
...
KeyError: 'a'

AUTHORS:
• Robert Bradshaw, 2007-08
• Simon King, 2012-01
• Nils Bruin, 2012-08
• Simon King, 2013-02
• Nils Bruin, 2013-11
copy()
Return a copy of this TripleDict as Python dict.
EXAMPLES:

sage: from [Link].coerce_dict import TripleDict

sage: L = TripleDict()
sage: L[1,2,3] = 42
sage: [Link]()
{(1, 2, 3): 42}

items()
Iterate over the (key, value) pairs of this TripleDict.
EXAMPLES:

5.6. Containers for storing coercion data 71

Sage Reference Manual: Coercion, Release 9.0

sage: from [Link].coerce_dict import TripleDict

sage: L = TripleDict()
sage: L[1,2,3] = None
sage: [Link]()
<generator object at ...>
sage: list([Link]())
[((1, 2, 3), None)]

class [Link].coerce_dict.TripleDictEraser
Bases: object
Erases items from a TripleDict when a weak reference becomes invalid.
This is of internal use only. Instances of this class will be passed as a callback function when creating a weak
reference.
EXAMPLES:

sage: from [Link].coerce_dict import TripleDict

sage: class A: pass
sage: a = A()
sage: T = TripleDict()
sage: T[a,ZZ,None] = 1
sage: T[ZZ,a,1] = 2
sage: T[a,a,ZZ] = 3
sage: len(T)
3
sage: del a
sage: import gc
sage: n = [Link]()
sage: len(T) # indirect doctest
0

AUTHOR:
• Simon King (2012-01)
• Nils Bruin (2013-11)

5.7 Exceptions raised by the coercion model

exception [Link].coerce_exceptions.CoercionException
Bases: TypeError
This is the baseclass of exceptions that the coercion model raises when trying to discover coercions. We don’t
use standard Python exceptions to avoid inadvertently catching and suppressing real errors.
Usually one raises this to indicate the attempted action isn’t implemented/appropriate, but if there are other
things to try not to immediately abort to the user.

72 Chapter 5. Modules
 CHAPTER

SIX

INDICES AND TABLES

• Index
• Module Index
• Search Page

73
Sage Reference Manual: Coercion, Release 9.0

74 Chapter 6. Indices and Tables

 PYTHON MODULE INDEX

c
[Link], 63
[Link], 37

s
[Link], 15
[Link].coerce_actions, 33
[Link].coerce_dict, 66
[Link].coerce_exceptions, 72
[Link].coerce_maps, 36

75
Sage Reference Manual: Coercion, Release 9.0

76 Python Module Index

 INDEX

A
act() ([Link] method), 64
ActedUponAction (class in [Link].coerce_actions), 33
Action (class in [Link]), 64
ActionEndomorphism (class in [Link]), 64
ActOnAction (class in [Link].coerce_actions), 33
actor() ([Link] method), 64
AlgebraicClosureFunctor (class in [Link]), 37
AlgebraicExtensionFunctor (class in [Link]), 38
analyse() ([Link] method), 16

B
bin_op() ([Link] method), 16
BlackBoxConstructionFunctor (class in [Link]), 40

C
CallableConvertMap (class in [Link].coerce_maps), 36
canonical_coercion() ([Link] method), 17
CCallableConvertMap_class (class in [Link].coerce_maps), 36
codomain() ([Link] method), 64
codomain() ([Link] method), 65
codomain() ([Link] method), 66
codomain() ([Link].coerce_actions.GenericAction method), 33
codomain() ([Link].coerce_actions.ModuleAction method), 35
coercion_maps() ([Link] method), 18
CoercionException, 72
CoercionModel (class in [Link]), 16
common_base() ([Link] method), 44
common_base() ([Link] method), 51
common_parent() ([Link] method), 19
commutes() ([Link] method), 41
commutes() ([Link] method), 44
CompletionFunctor (class in [Link]), 41
CompositeConstructionFunctor (class in [Link]), 42
construction_tower() (in module [Link]), 55
ConstructionFunctor (class in [Link]), 42
copy() ([Link].coerce_dict.MonoDict method), 69

77
Sage Reference Manual: Coercion, Release 9.0

copy() ([Link].coerce_dict.TripleDict method), 71

D
DefaultConvertMap (class in [Link].coerce_maps), 37
DefaultConvertMap_unique (class in [Link].coerce_maps), 37
detect_element_action() (in module [Link].coerce_actions), 36
discover_action() ([Link] method), 20
discover_coercion() ([Link] method), 21
division_parent() ([Link] method), 22
domain() ([Link] method), 64
domain() ([Link] method), 66
domain() ([Link].coerce_actions.ModuleAction method), 35

E
exception_stack() ([Link] method), 22
expand() ([Link] method), 38
expand() ([Link] method), 42
expand() ([Link] method), 44
expand() ([Link] method), 47
expand() ([Link] method), 50
expand_tower() (in module [Link]), 56
explain() ([Link] method), 23

F
FractionField (class in [Link]), 45

G
G ([Link] attribute), 64
GenericAction (class in [Link].coerce_actions), 33
gens() ([Link] method), 51
get_action() ([Link] method), 25
get_cache() ([Link] method), 26

I
IdentityConstructionFunctor (class in [Link]), 46
InfinitePolynomialFunctor (class in [Link]), 46
IntegerAction (class in [Link].coerce_actions), 33
IntegerMulAction (class in [Link].coerce_actions), 34
IntegerPowAction (class in [Link].coerce_actions), 34
InverseAction (class in [Link]), 65
is_left() ([Link] method), 64
is_mpmath_type() (in module [Link]), 29
is_numpy_type() (in module [Link]), 29
items() ([Link].coerce_dict.MonoDict method), 69
items() ([Link].coerce_dict.TripleDict method), 71

L
LaurentPolynomialFunctor (class in [Link]), 48
left_domain() ([Link] method), 64
left_precomposition ([Link] attribute), 66

78 Index
 Sage Reference Manual: Coercion, Release 9.0

LeftModuleAction (class in [Link].coerce_actions), 34

ListMorphism (class in [Link].coerce_maps), 37

M
MatrixFunctor (class in [Link]), 49
merge() ([Link] method), 38
merge() ([Link] method), 39
merge() ([Link] method), 41
merge() ([Link] method), 45
merge() ([Link] method), 48
merge() ([Link] method), 49
merge() ([Link] method), 49
merge() ([Link] method), 51
merge() ([Link] method), 52
merge() ([Link] method), 52
merge() ([Link] method), 53
merge() ([Link] method), 54
merge() ([Link] method), 54
method_name ([Link].coerce_maps.NamedConvertMap attribute), 37
ModuleAction (class in [Link].coerce_actions), 34
MonoDict (class in [Link].coerce_dict), 67
MonoDictEraser (class in [Link].coerce_dict), 69
MultiPolynomialFunctor (class in [Link]), 50
MultivariateConstructionFunctor (class in [Link]), 51

N
NamedConvertMap (class in [Link].coerce_maps), 37

O
ObjectWrapper (class in [Link].coerce_dict), 70
op ([Link] attribute), 64
operation() ([Link] method), 64

P
parent_is_integers() (in module [Link]), 29
parent_is_numerical() (in module [Link]), 30
parent_is_real_numerical() (in module [Link]), 30
PermutationGroupFunctor (class in [Link]), 51
PolynomialFunctor (class in [Link]), 52
PrecomposedAction (class in [Link]), 65
pushout() (in module [Link]), 56
pushout() ([Link] method), 45
pushout_lattice() (in module [Link]), 62
py_scalar_parent() (in module [Link]), 31
py_scalar_to_element() (in module [Link]), 31
PyScalarAction (class in [Link].coerce_actions), 35

Q
QuotientFunctor (class in [Link]), 53

Index 79
Sage Reference Manual: Coercion, Release 9.0

R
record_exceptions() ([Link] method), 27
reset_cache() ([Link] method), 27
richcmp() ([Link] method), 27
right_domain() ([Link] method), 64
right_precomposition ([Link] attribute), 66
RightModuleAction (class in [Link].coerce_actions), 36

S
[Link] (module), 63
[Link] (module), 37
[Link] (module), 15
[Link].coerce_actions (module), 33
[Link].coerce_dict (module), 66
[Link].coerce_exceptions (module), 72
[Link].coerce_maps (module), 36
SubspaceFunctor (class in [Link]), 53

T
test_CCallableConvertMap() (in module [Link].coerce_maps), 37
TripleDict (class in [Link].coerce_dict), 70
TripleDictEraser (class in [Link].coerce_dict), 72
TryMap (class in [Link].coerce_maps), 37
type_to_parent() (in module [Link]), 63

V
VectorFunctor (class in [Link]), 54
verify_action() ([Link] method), 28
verify_coercion_maps() ([Link] method), 28

80 Index