Number Fields¶
Introduction¶
Like many other computations in algebraic number theory, the splitting of rational primes can be treated by rational methods only. This fact is very important if computation by automatic computing machinery is considered. Only the knowledge of the irreducible polynomial \(f(x)\), a zero of which generates the field in question, is needed.
Olga Taussky, 1953
Concepts like number fields and algebraic numbers are essential to our
understanding of algebraic number theory, but to the computer the subject is
all about polynomials: the ring \(\mathbb{Q}[x]\) reduced modulo irreducible
polynomials \(f(x) \in \mathbb{Q}[x]\). It thus finds a natural home under the
polys
module in SymPy.
Various authors (such as Taussky, Zimmer, Pohst and Zassenhaus, or Cohen)
have articulated the main goals of computational algebraic number theory in
different ways, but invariably the list centers around a certain essential set
of tasks. As a goal for the numberfields
module in SymPy, we may set the
following list, based on [Cohen93], Sec. 4.9.3.
For a number field \(K = \mathbb{Q}(\theta)\), whose ring of algebraic integers is denoted \(\mathbb{Z}_K\), compute:
an integral basis of \(\mathbb{Z}_K\)
the decomposition of rational primes in \(\mathbb{Z}_K\)
\(\mathfrak{p}\)adic valuations for ideals and elements
the Galois group of the Galois closure of \(K\)
a system of fundamental units of \(K\)
the regulator \(R(K)\)
the class number
the structure of the class group \(Cl(K)\)
decide whether a given ideal is principal, and if so compute a generator.
As a foundation, and to support our basic ability to define and work with number fields and algebraic numbers, we also set the following problems, following [Cohen93], Sec. 4.5.
Given an algebraic number – expressed by radicals and rational operations, or even as a special value of a transcendental function – determine its minimal polynomial over \(\mathbb{Q}\).
The Subfield Problem: Given two number fields \(\mathbb{Q}(\alpha)\), \(\mathbb{Q}(\beta)\) via the minimal polynomials for their generators \(\alpha\) and \(\beta\), decide whether one field is isomorphic to a subfield of the other, and if so exhibit an embedding.
The Field Membership Problem: Given two algebraic numbers \(\alpha\), \(\beta\), decide whether \(\alpha \in \mathbb{Q}(\beta)\), and if so write \(\alpha = f(\beta)\) for some \(f(x) \in \mathbb{Q}[x]\).
The Primitive Element Problem: Given several algebraic numbers \(\alpha_1, \ldots, \alpha_m\), compute a single algebraic number \(\theta\) such that \(\mathbb{Q}(\alpha_1, \ldots, \alpha_m) = \mathbb{Q}(\theta)\).
At present only a subset of the tasks enumerated above is yet supported in SymPy, and if you are interested in expanding support, you are encouraged to contribute! An excellent source, providing solutions to all the remaining problems (as well as those already solved) is [Cohen93].
At time of writing, the existing solutions to the above problems are found in the following places:
Task 
Implementation 














Solving the Main Problems¶
Integral Basis¶
 sympy.polys.numberfields.basis.round_two(T, radicals=None)[source]¶
Zassenhaus’s “Round 2” algorithm.
 Parameters
T :
Poly
The irreducible monic polynomial over ZZ defining the number field.
radicals : dict, optional
This is a way for any \(p\)radicals (if computed) to be returned by reference. If desired, pass an empty dictionary. If the algorithm reaches the point where it computes the nilradical mod \(p\) of the ring of integers \(Z_K\), then an \(\mathbb{F}_p\)basis for this ideal will be stored in this dictionary under the key
p
. This can be useful for other algorithms, such as prime decomposition. Returns
Pair
(ZK, dK)
, where:ZK
is aSubmodule
representing the maximal order.dK
is the discriminant of the field \(K = \mathbb{Q}[x]/(T(x))\).
Explanation
Carry out Zassenhaus’s “Round 2” algorithm on a monic irreducible polynomial T over ZZ. This computes an integral basis and the discriminant for the field \(K = \mathbb{Q}[x]/(T(x))\).
Ordinarily this function need not be called directly, as one can instead access the
maximal_order()
,integral_basis()
, anddiscriminant()
methods of anAlgebraicField
.Examples
Working through an AlgebraicField:
>>> from sympy import Poly, QQ >>> from sympy.abc import x, theta >>> T = Poly(x ** 3 + x ** 2  2 * x + 8) >>> K = QQ.algebraic_field((T, theta)) >>> print(K.maximal_order()) Submodule[[2, 0, 0], [0, 2, 0], [0, 1, 1]]/2 >>> print(K.discriminant()) 503 >>> print(K.integral_basis(fmt='sympy')) [1, theta, theta**2/2 + theta/2]
Calling directly:
>>> from sympy import Poly >>> from sympy.abc import x >>> from sympy.polys.numberfields.basis import round_two >>> T = Poly(x ** 3 + x ** 2  2 * x + 8) >>> print(round_two(T)) (Submodule[[2, 0, 0], [0, 2, 0], [0, 1, 1]]/2, 503)
The nilradicals mod \(p\) that are sometimes computed during the Round Two algorithm may be useful in further calculations. Pass a dictionary under \(radicals\) to receive these:
>>> T = Poly(x**3 + 3*x**2 + 5) >>> rad = {} >>> ZK, dK = round_two(T, radicals=rad) >>> print(rad) {3: Submodule[[1, 1, 0], [1, 0, 1]]}
References
 R708
Cohen, H. A Course in Computational Algebraic Number Theory.
Prime Decomposition¶
 sympy.polys.numberfields.primes.prime_decomp(p, T=None, ZK=None, dK=None, radical=None)[source]¶
Compute the decomposition of rational prime p in a number field.
 Parameters
p : int
The rational prime whose decomposition is desired.
T :
Poly
, optionalMonic irreducible polynomial defining the number field \(K\) in which to factor. NOTE: at least one of T or ZK must be provided.
ZK :
Submodule
, optionalThe maximal order for \(K\), if already known. NOTE: at least one of T or ZK must be provided.
dK : int, optional
The discriminant of the field \(K\), if already known.
radical :
Submodule
, optionalThe nilradical mod p in the integers of \(K\), if already known.
 Returns
List of
PrimeIdeal
instances.
Explanation
Ordinarily this should be accessed through the
primes_above()
method of anAlgebraicField
.Examples
>>> from sympy import Poly, QQ >>> from sympy.abc import x, theta >>> T = Poly(x ** 3 + x ** 2  2 * x + 8) >>> K = QQ.algebraic_field((T, theta)) >>> print(K.primes_above(2)) [[ (2, x**2 + 1) e=1, f=1 ], [ (2, (x**2 + 3*x + 2)/2) e=1, f=1 ], [ (2, (3*x**2 + 3*x)/2) e=1, f=1 ]]
References
 R709
Cohen, H. A Course in Computational Algebraic Number Theory. (See Algorithm 6.2.9.)
 class sympy.polys.numberfields.primes.PrimeIdeal(ZK, p, alpha, f, e=None)[source]¶
A prime ideal in a ring of algebraic integers.
 __init__(ZK, p, alpha, f, e=None)[source]¶
 Parameters
ZK :
Submodule
The maximal order where this ideal lives.
p : int
The rational prime this ideal divides.
alpha :
PowerBasisElement
Such that the ideal is equal to
p*ZK + alpha*ZK
.f : int
The inertia degree.
e : int,
None
, optionalThe ramification index, if already known. If
None
, we will compute it here.
 __mul__(other)[source]¶
Convert to a
Submodule
and multiply by anotherSubmodule
or a rational number.See also
 as_submodule()[source]¶
Represent this prime ideal as a
Submodule
. Returns

Will be equal to
self.p * self.ZK + self.alpha * self.ZK
.
Explanation
The
PrimeIdeal
class serves to bundle information about a prime ideal, such as its inertia degree, ramification index, and twogenerator representation, as well as to offer helpful methods likevaluation()
andtest_factor()
.However, in order to be added and multiplied by other ideals or rational numbers, it must first be converted into a
Submodule
, which is a class that supports these operations.In many cases, the user need not perform this conversion deliberately, since it is automatically performed by the arithmetic operator methods
__add__()
and__mul__()
.Raising a
PrimeIdeal
to a nonnegative integer power is also supported.Examples
>>> from sympy import Poly, cyclotomic_poly, prime_decomp >>> T = Poly(cyclotomic_poly(7)) >>> P0 = prime_decomp(7, T)[0] >>> print(P0**6 == 7*P0.ZK) True
Note that, on both sides of the equation above, we had a
Submodule
. In the next equation we recall that adding ideals yields their GCD. This time, we need a deliberate conversion toSubmodule
on the right:>>> print(P0 + 7*P0.ZK == P0.as_submodule()) True
 test_factor()[source]¶
Compute a test factor for this prime ideal.
Explanation
Write \(\mathfrak{p}\) for this prime ideal, \(p\) for the rational prime it divides. Then, for computing \(\mathfrak{p}\)adic valuations it is useful to have a number \(\beta \in \mathbb{Z}_K\) such that \(p/\mathfrak{p} = p \mathbb{Z}_K + \beta \mathbb{Z}_K\).
Essentially, this is the same as the number \(\Psi\) (or the “reagent”) from Kummer’s 1847 paper (Ueber die Zerlegung…, Crelle vol. 35) in which ideal divisors were invented.
padic Valuation¶
 sympy.polys.numberfields.primes.prime_valuation(I, P)[source]¶
Compute the Padic valuation for an integral ideal I.
 Parameters
I :
Submodule
An integral ideal whose valuation is desired.
P :
PrimeIdeal
The prime at which to compute the valuation.
 Returns
int
Examples
>>> from sympy import QQ >>> from sympy.abc import theta >>> from sympy.polys import cyclotomic_poly >>> from sympy.polys.numberfields import prime_valuation >>> T = cyclotomic_poly(5) >>> K = QQ.algebraic_field((T, theta)) >>> P = K.primes_above(5) >>> ZK = K.maximal_order() >>> print(prime_valuation(25*ZK, P[0])) 8
See also
References
 R710
Cohen, H. A Course in Computational Algebraic Number Theory. (See Algorithm 4.8.17.)
Finding Minimal Polynomials¶
 sympy.polys.numberfields.minpoly.minimal_polynomial(ex, x=None, compose=True, polys=False, domain=None)[source]¶
Computes the minimal polynomial of an algebraic element.
 Parameters
ex : Expr
Element or expression whose minimal polynomial is to be calculated.
x : Symbol, optional
Independent variable of the minimal polynomial
compose : boolean, optional (default=True)
Method to use for computing minimal polynomial. If
compose=True
(default) then_minpoly_compose
is used, ifcompose=False
then groebner bases are used.polys : boolean, optional (default=False)
If
True
returns aPoly
object else anExpr
object.domain : Domain, optional
Ground domain
Notes
By default
compose=True
, the minimal polynomial of the subexpressions ofex
are computed, then the arithmetic operations on them are performed using the resultant and factorization. Ifcompose=False
, a bottomup algorithm is used withgroebner
. The default algorithm stalls less frequently.If no ground domain is given, it will be generated automatically from the expression.
Examples
>>> from sympy import minimal_polynomial, sqrt, solve, QQ >>> from sympy.abc import x, y
>>> minimal_polynomial(sqrt(2), x) x**2  2 >>> minimal_polynomial(sqrt(2), x, domain=QQ.algebraic_field(sqrt(2))) x  sqrt(2) >>> minimal_polynomial(sqrt(2) + sqrt(3), x) x**4  10*x**2 + 1 >>> minimal_polynomial(solve(x**3 + x + 3)[0], x) x**3 + x + 3 >>> minimal_polynomial(sqrt(y), x) x**2  y
 sympy.polys.numberfields.minpoly.minpoly(ex, x=None, compose=True, polys=False, domain=None)[source]¶
This is a synonym for
minimal_polynomial()
.
The Subfield Problem¶
Functions in polys.numberfields.subfield
solve the “Subfield Problem” and
allied problems, for algebraic number fields.
Following Cohen (see [Cohen93] Section 4.5), we can define the main problem as follows:
Subfield Problem:
Given two number fields \(\mathbb{Q}(\alpha)\), \(\mathbb{Q}(\beta)\) via the minimal polynomials for their generators \(\alpha\) and \(\beta\), decide whether one field is isomorphic to a subfield of the other.
From a solution to this problem flow solutions to the following problems as well:
Primitive Element Problem:
Given several algebraic numbers \(\alpha_1, \ldots, \alpha_m\), compute a single algebraic number \(\theta\) such that \(\mathbb{Q}(\alpha_1, \ldots, \alpha_m) = \mathbb{Q}(\theta)\).
Field Isomorphism Problem:
Decide whether two number fields \(\mathbb{Q}(\alpha)\), \(\mathbb{Q}(\beta)\) are isomorphic.
Field Membership Problem:
Given two algebraic numbers \(\alpha\), \(\beta\), decide whether \(\alpha \in \mathbb{Q}(\beta)\), and if so write \(\alpha = f(\beta)\) for some \(f(x) \in \mathbb{Q}[x]\).
 sympy.polys.numberfields.subfield.field_isomorphism(a, b, *, fast=True)[source]¶
Find an embedding of one number field into another.
 Parameters
a :
Expr
Any expression representing an algebraic number.
b :
Expr
Any expression representing an algebraic number.
fast : boolean, optional (default=True)
If
True
, we first attempt a potentially faster way of computing the isomorphism, falling back on a slower method if this fails. IfFalse
, we go directly to the slower method, which is guaranteed to return a result. Returns
List of rational numbers, or None
If \(\mathbb{Q}(a)\) is not isomorphic to some subfield of \(\mathbb{Q}(b)\), then return
None
. Otherwise, return a list of rational numbers representing an element of \(\mathbb{Q}(b)\) to which \(a\) may be mapped, in order to define a monomorphism, i.e. an isomorphism from \(\mathbb{Q}(a)\) to some subfield of \(\mathbb{Q}(b)\). The elements of the list are the coefficients of falling powers of \(b\).
Explanation
This function looks for an isomorphism from \(\mathbb{Q}(a)\) onto some subfield of \(\mathbb{Q}(b)\). Thus, it solves the Subfield Problem.
Examples
>>> from sympy import sqrt, field_isomorphism, I >>> print(field_isomorphism(3, sqrt(2))) [3] >>> print(field_isomorphism( I*sqrt(3), I*sqrt(3)/2)) [2, 0]
 sympy.polys.numberfields.subfield.primitive_element(extension, x=None, *, ex=False, polys=False)[source]¶
Find a single generator for a number field given by several generators.
 Parameters
extension : list of
Expr
Each expression must represent an algebraic number \(\alpha_i\).
x :
Symbol
, optional (default=None)The desired symbol to appear in the computed minimal polynomial for the primitive element \(\theta\). If
None
, we use a dummy symbol.ex : boolean, optional (default=False)
If and only if
True
, compute the representation of each \(\alpha_i\) as a \(\mathbb{Q}\)linear combination over the powers of \(\theta\).polys : boolean, optional (default=False)
 Returns
Pair (f, coeffs) or triple (f, coeffs, reps), where:
f
is the minimal polynomial for the primitive element.coeffs
gives the primitive element as a linear combination of the given generators.reps
is present if and only if argumentex=True
was passed, and is a list of lists of rational numbers. Each list gives the coefficients of falling powers of the primitive element, to recover one of the original, given generators.
Explanation
The basic problem is this: Given several algebraic numbers \(\alpha_1, \alpha_2, \ldots, \alpha_n\), find a single algebraic number \(\theta\) such that \(\mathbb{Q}(\alpha_1, \alpha_2, \ldots, \alpha_n) = \mathbb{Q}(\theta)\).
This function actually guarantees that \(\theta\) will be a linear combination of the \(\alpha_i\), with nonnegative integer coefficients.
Furthermore, if desired, this function will tell you how to express each \(\alpha_i\) as a \(\mathbb{Q}\)linear combination of the powers of \(\theta\).
Examples
>>> from sympy import primitive_element, sqrt, S, minpoly, simplify >>> from sympy.abc import x >>> f, lincomb, reps = primitive_element([sqrt(2), sqrt(3)], x, ex=True)
Then
lincomb
tells us the primitive element as a linear combination of the given generatorssqrt(2)
andsqrt(3)
.>>> print(lincomb) [1, 1]
This means the primtiive element is \(\sqrt{2} + \sqrt{3}\). Meanwhile
f
is the minimal polynomial for this primitive element.>>> print(f) x**4  10*x**2 + 1 >>> print(minpoly(sqrt(2) + sqrt(3), x)) x**4  10*x**2 + 1
Finally,
reps
(which was returned only because we set keyword argex=True
) tells us how to recover each of the generators \(\sqrt{2}\) and \(\sqrt{3}\) as \(\mathbb{Q}\)linear combinations of the powers of the primitive element \(\sqrt{2} + \sqrt{3}\).>>> print([S(r) for r in reps[0]]) [1/2, 0, 9/2, 0] >>> theta = sqrt(2) + sqrt(3) >>> print(simplify(theta**3/2  9*theta/2)) sqrt(2) >>> print([S(r) for r in reps[1]]) [1/2, 0, 11/2, 0] >>> print(simplify(theta**3/2 + 11*theta/2)) sqrt(3)
 sympy.polys.numberfields.subfield.to_number_field(extension, theta=None, *, gen=None)[source]¶
Express one algebraic number in the field generated by another.
 Parameters
extension :
Expr
or list ofExpr
Either the algebraic number that is to be expressed in the other field, or else a list of algebraic numbers, a primitive element for which is to be expressed in the other field.
theta :
Expr
, None, optional (default=None)If an
Expr
representing an algebraic number, behavior is as described under Explanation. IfNone
, then this function reduces to a shorthand for callingprimitive_element()
onextension
and turning the computed primitive element into anAlgebraicNumber
.gen :
Symbol
, None, optional (default=None)If provided, this will be used as the generator symbol for the returned
AlgebraicNumber
. Returns
AlgebraicNumber
Belonging to \(\mathbb{Q}(\theta)\) and equaling \(\eta\).
 Raises
IsomorphismFailed
If \(\eta \not\in \mathbb{Q}(\theta)\).
Explanation
Given two algebraic numbers \(\eta, \theta\), this function either expresses \(\eta\) as an element of \(\mathbb{Q}(\theta)\), or else raises an exception if \(\eta \not\in \mathbb{Q}(\theta)\).
This function is essentially just a convenience, utilizing
field_isomorphism()
(our solution of the Subfield Problem) to solve this, the Field Membership Problem.As an additional convenience, this function allows you to pass a list of algebraic numbers \(\alpha_1, \alpha_2, \ldots, \alpha_n\) instead of \(\eta\). It then computes \(\eta\) for you, as a solution of the Primitive Element Problem, using
primitive_element()
on the list of \(\alpha_i\).Examples
>>> from sympy import sqrt, to_number_field >>> eta = sqrt(2) >>> theta = sqrt(2) + sqrt(3) >>> a = to_number_field(eta, theta) >>> print(type(a)) <class 'sympy.core.numbers.AlgebraicNumber'> >>> a.root sqrt(2) + sqrt(3) >>> print(a) sqrt(2) >>> a.coeffs() [1/2, 0, 9/2, 0]
We get an
AlgebraicNumber
, whose.root
is \(\theta\), whose value is \(\eta\), and whose.coeffs()
show how to write \(\eta\) as a \(\mathbb{Q}\)linear combination in falling powers of \(\theta\).See also
Internals¶
Algebraic number fields¶
Algebraic number fields are represented in SymPy by the
AlgebraicField
class, which is a part of
the polynomial domains system.
Representing algebraic numbers¶
There are several different ways to represent algebraic numbers, and different forms may be preferable for different computational tasks. See [Cohen93], Sec. 4.2.
As number field elements¶
In SymPy, there is a distinction between number and expression classes defined
in the sympy.core.numbers
module on the one hand, and domains and
domain elements defined in the polys
module on the other.
This is explained in more detail here.
When it comes to algebraic numbers, the sympy.core.numbers
module
offers the AlgebraicNumber
class, while the
polys
module offers the
ANP
class. This is the type of domain
elements belonging to the AlgebraicField
domain.
As elements of finitelygenerated modules¶
In computational algebraic number theory, finitelygenerated \(\mathbb{Z}\)modules are of central importance. For example, every order and every ideal is such a module.
In particular, the maximal order – or ring of integers – in a number field is a finitelygenerated \(\mathbb{Z}\)module, whose generators form an integral basis for the field.
Classes allowing us to represent such modules, and their elements, are provided
in the modules
module. Here, the ModuleElement
class
provides another way to represent algebraic numbers.
Finitelygenerated modules¶
Modules in number fields.
The classes defined here allow us to work with finitely generated, free modules, whose generators are algebraic numbers.
There is an abstract base class called Module
, which has two
concrete subclasses, PowerBasis
and Submodule
.
Every module is defined by its basis, or set of generators:
For a
PowerBasis
, the generators are the first \(n\) powers (starting with the zeroth) of an algebraic integer \(\theta\) of degree \(n\). ThePowerBasis
is constructed by passing the minimal polynomial of \(\theta\).For a
Submodule
, the generators are a set of \(\mathbb{Q}\)linear combinations of the generators of another module. That other module is then the “parent” of theSubmodule
. The coefficients of the \(\mathbb{Q}\)linear combinations may be given by an integer matrix, and a positive integer denominator. Each column of the matrix defines a generator.
>>> from sympy.polys import Poly, cyclotomic_poly, ZZ
>>> from sympy.abc import x
>>> from sympy.polys.matrices import DomainMatrix, DM
>>> from sympy.polys.numberfields.modules import PowerBasis
>>> T = Poly(cyclotomic_poly(5, x))
>>> A = PowerBasis(T)
>>> print(A)
PowerBasis(x**4 + x**3 + x**2 + x + 1)
>>> B = A.submodule_from_matrix(2 * DomainMatrix.eye(4, ZZ), denom=3)
>>> print(B)
Submodule[[2, 0, 0, 0], [0, 2, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2]]/3
>>> print(B.parent)
PowerBasis(x**4 + x**3 + x**2 + x + 1)
Thus, every module is either a PowerBasis
,
or a Submodule
, some ancestor of which is a
PowerBasis
. (If S
is a Submodule
, then its
ancestors are S.parent
, S.parent.parent
, and so on).
The ModuleElement
class represents a linear combination of the
generators of any module. Critically, the coefficients of this linear
combination are not restricted to be integers, but may be any rational
numbers. This is necessary so that any and all algebraic integers be
representable, starting from the power basis in a primitive element \(\theta\)
for the number field in question. For example, in a quadratic field
\(\mathbb{Q}(\sqrt{d})\) where \(d \equiv 1 \mod{4}\), a denominator of \(2\) is
needed.
A ModuleElement
can be constructed from an integer column vector
and a denominator:
>>> U = Poly(x**2  5)
>>> M = PowerBasis(U)
>>> e = M(DM([[1], [1]], ZZ), denom=2)
>>> print(e)
[1, 1]/2
>>> print(e.module)
PowerBasis(x**2  5)
The PowerBasisElement
class is a subclass of
ModuleElement
that represents elements of a
PowerBasis
, and adds functionality pertinent to elements
represented directly over powers of the primitive element \(\theta\).
Arithmetic with module elements¶
While a ModuleElement
represents a linear combination over the
generators of a particular module, recall that every module is either a
PowerBasis
or a descendant (along a chain of
Submodule
objects) thereof, so that in fact every
ModuleElement
represents an algebraic number in some field
\(\mathbb{Q}(\theta)\), where \(\theta\) is the defining element of some
PowerBasis
. It thus makes sense to talk about the number field
to which a given ModuleElement
belongs.
This means that any two ModuleElement
instances can be added,
subtracted, multiplied, or divided, provided they belong to the same number
field. Similarly, since \(\mathbb{Q}\) is a subfield of every number field,
any ModuleElement
may be added, multiplied, etc. by any
rational number.
>>> from sympy import QQ
>>> from sympy.polys.numberfields.modules import to_col
>>> T = Poly(cyclotomic_poly(5))
>>> A = PowerBasis(T)
>>> C = A.submodule_from_matrix(3 * DomainMatrix.eye(4, ZZ))
>>> e = A(to_col([0, 2, 0, 0]), denom=3)
>>> f = A(to_col([0, 0, 0, 7]), denom=5)
>>> g = C(to_col([1, 1, 1, 1]))
>>> e + f
[0, 10, 0, 21]/15
>>> e  f
[0, 10, 0, 21]/15
>>> e  g
[9, 7, 9, 9]/3
>>> e + QQ(7, 10)
[21, 20, 0, 0]/30
>>> e * f
[14, 14, 14, 14]/15
>>> e ** 2
[0, 0, 4, 0]/9
>>> f // g
[7, 7, 7, 7]/15
>>> f * QQ(2, 3)
[0, 0, 0, 14]/15
However, care must be taken with arithmetic operations on
ModuleElement
, because the module \(C\) to which the result will
belong will be the nearest common ancestor (NCA) of the modules \(A\), \(B\) to
which the two operands belong, and \(C\) may be different from either or both
of \(A\) and \(B\).
>>> A = PowerBasis(T)
>>> B = A.submodule_from_matrix(2 * DomainMatrix.eye(4, ZZ))
>>> C = A.submodule_from_matrix(3 * DomainMatrix.eye(4, ZZ))
>>> print((B(0) * C(0)).module == A)
True
Before the arithmetic operation is performed, copies of the two operands are
automatically converted into elements of the NCA (the operands themselves are
not modified). This upward conversion along an ancestor chain is easy: it just
requires the successive multiplication by the defining matrix of each
Submodule
.
Conversely, downward conversion, i.e. representing a given
ModuleElement
in a submodule, is also supported – namely by
the represent()
method
– but is not guaranteed to succeed in general, since the given element may
not belong to the submodule. The main circumstance in which this issue tends
to arise is with multiplication, since modules, while closed under addition,
need not be closed under multiplication.
Multiplication¶
Generally speaking, a module need not be closed under multiplication, i.e. need not form a ring. However, many of the modules we work with in the context of number fields are in fact rings, and our classes do support multiplication.
Specifically, any Module
can attempt to compute its own
multiplication table, but this does not happen unless an attempt is made to
multiply two ModuleElement
instances belonging to it.
>>> A = PowerBasis(T)
>>> print(A._mult_tab is None)
True
>>> a = A(0)*A(1)
>>> print(A._mult_tab is None)
False
Every PowerBasis
is, by its nature, closed under multiplication,
so instances of PowerBasis
can always successfully compute their
multiplication table.
When a Submodule
attempts to compute its multiplication table,
it converts each of its own generators into elements of its parent module,
multiplies them there, in every possible pairing, and then tries to
represent the results in itself, i.e. as \(\mathbb{Z}\)linear combinations
over its own generators. This will succeed if and only if the submodule is
in fact closed under multiplication.
Module Homomorphisms¶
Many important number theoretic algorithms require the calculation of the
kernel of one or more module homomorphisms. Accordingly we have several
lightweight classes, ModuleHomomorphism
,
ModuleEndomorphism
, InnerEndomorphism
, and
EndomorphismRing
, which provide the minimal necessary machinery
to support this.
Class Reference¶
 class sympy.polys.numberfields.modules.Module[source]¶
Generic finitelygenerated module.
This is an abstract base class, and should not be instantiated directly. The two concrete subclasses are
PowerBasis
andSubmodule
.Every
Submodule
is derived from another module, referenced by itsparent
attribute. IfS
is a submodule, then we refer toS.parent
,S.parent.parent
, and so on, as the “ancestors” ofS
. Thus, everyModule
is either aPowerBasis
or aSubmodule
, some ancestor of which is aPowerBasis
. __call__(spec, denom=1)[source]¶
Generate a
ModuleElement
belonging to this module. Parameters
spec :
DomainMatrix
, intSpecifies the numerators of the coefficients of the
ModuleElement
. Can be either a column vector over ZZ, whose length must equal the number \(n\) of generators of this module, or else an integerj
, \(0 \leq j < n\), which is a shorthand for column \(j\) of \(I_n\), the \(n \times n\) identity matrix.denom : int, optional (default=1)
Denominator for the coefficients of the
ModuleElement
. Returns

The coefficients are the entries of the spec vector, divided by denom.
Examples
>>> from sympy.polys import Poly, cyclotomic_poly >>> from sympy.polys.numberfields.modules import PowerBasis, to_col >>> T = Poly(cyclotomic_poly(5)) >>> A = PowerBasis(T) >>> e = A(to_col([1, 2, 3, 4]), denom=3) >>> print(e) [1, 2, 3, 4]/3 >>> f = A(2) >>> print(f) [0, 0, 1, 0]
 ancestors(include_self=False)[source]¶
Return the list of ancestor modules of this module, from the foundational
PowerBasis
downward, optionally includingself
.See also
 basis_elements()[source]¶
Get list of
ModuleElement
being the generators of this module.
 element_from_rational(a)[source]¶
Return a
ModuleElement
representing a rational number. Parameters
 Returns
Explanation
The returned
ModuleElement
will belong to the first module on this module’s ancestor chain (including this module itself) that starts with unity.Examples
>>> from sympy.polys import Poly, cyclotomic_poly, QQ >>> from sympy.polys.numberfields.modules import PowerBasis >>> T = Poly(cyclotomic_poly(5)) >>> A = PowerBasis(T) >>> a = A.element_from_rational(QQ(2, 3)) >>> print(a) [2, 0, 0, 0]/3
 endomorphism_ring()[source]¶
Form the
EndomorphismRing
for this module.
 mult_tab()[source]¶
Get the multiplication table for this module (if closed under mult).
 Returns
dict of dict of lists
 Raises
ClosureFailure
If the module is not closed under multiplication.
Explanation
Computes a dictionary
M
of dictionaries of lists, representing the upper triangular half of the multiplication table.In other words, if
0 <= i <= j < self.n
, thenM[i][j]
is the listc
of coefficients such thatg[i] * g[j] == sum(c[k]*g[k], k in range(self.n))
, whereg
is the list of generators of this module.If
j < i
thenM[i][j]
is undefined.Examples
>>> from sympy.polys import Poly, cyclotomic_poly >>> from sympy.polys.numberfields.modules import PowerBasis >>> T = Poly(cyclotomic_poly(5)) >>> A = PowerBasis(T) >>> print(A.mult_tab()) {0: {0: [1, 0, 0, 0], 1: [0, 1, 0, 0], 2: [0, 0, 1, 0], 3: [0, 0, 0, 1]}, 1: {1: [0, 0, 1, 0], 2: [0, 0, 0, 1], 3: [1, 1, 1, 1]}, 2: {2: [1, 1, 1, 1], 3: [1, 0, 0, 0]}, 3: {3: [0, 1, 0, 0]}}
 property n¶
The number of generators of this module.
 nearest_common_ancestor(other)[source]¶
Locate the nearest common ancestor of this module and another.
 Returns
Module
,None
See also
 one()[source]¶
Return a
ModuleElement
representing unity, and belonging to the first ancestor of this module (including itself) that starts with unity.
 property parent¶
The parent module, if any, for this module.
 Returns
Module
,None
Explanation
For a
Submodule
this is itsparent
attribute; for aPowerBasis
this isNone
.See also
 power_basis_ancestor()[source]¶
Return the
PowerBasis
that is an ancestor of this module.See also
 represent(elt)[source]¶
Represent a module element as an integerlinear combination over the generators of this module.
 Parameters
elt :
ModuleElement
The module element to be represented. Must belong to some ancestor module of this module (including this module itself).
 Returns
DomainMatrix
over ZZThis will be a column vector, representing the coefficients of a linear combination of this module’s generators, which equals the given element.
 Raises
ClosureFailure
If the given element cannot be represented as a ZZlinear combination over this module.
Explanation
In our system, to “represent” always means to write a
ModuleElement
as a ZZlinear combination over the generators of the presentModule
. Furthermore, the incomingModuleElement
must belong to an ancestor of the presentModule
(or to the presentModule
itself).The most common application is to represent a
ModuleElement
in aSubmodule
. For example, this is involved in computing multiplication tables.On the other hand, representing in a
PowerBasis
is an odd case, and one which tends not to arise in practice, except for example when using aModuleEndomorphism
on aPowerBasis
.In such a case, (1) the incoming
ModuleElement
must belong to thePowerBasis
itself (since the latter has no proper ancestors) and (2) it is “representable” iff it belongs to \(\mathbb{Z}[\theta]\) (although generally aPowerBasisElement
may represent any element of \(\mathbb{Q}(\theta)\), i.e. any algebraic number).Examples
>>> from sympy import Poly, cyclotomic_poly >>> from sympy.polys.numberfields.modules import PowerBasis, to_col >>> from sympy.abc import zeta >>> T = Poly(cyclotomic_poly(5)) >>> A = PowerBasis(T) >>> a = A(to_col([2, 4, 6, 8]))
The
ModuleElement
a
has all even coefficients. If we representa
in the submoduleB = 2*A
, the coefficients in the column vector will be halved:>>> B = A.submodule_from_gens([2*A(i) for i in range(4)]) >>> b = B.represent(a) >>> print(b.transpose()) DomainMatrix([[1, 2, 3, 4]], (1, 4), ZZ)
However, the element of
B
so defined still represents the same algebraic number:>>> print(a.poly(zeta).as_expr()) 8*zeta**3 + 6*zeta**2 + 4*zeta + 2 >>> print(B(b).over_power_basis().poly(zeta).as_expr()) 8*zeta**3 + 6*zeta**2 + 4*zeta + 2
See also
 submodule_from_gens(gens, hnf=True, hnf_modulus=None)[source]¶
Form the submodule generated by a list of
ModuleElement
belonging to this module. Parameters
gens : list of
ModuleElement
belonging to this module.hnf : boolean, optional (default=True)
If True, we will reduce the matrix into Hermite Normal Form before forming the
Submodule
.hnf_modulus : int, None, optional (default=None)
Modulus for use in the HNF reduction algorithm. See
hermite_normal_form()
. Returns
Examples
>>> from sympy.polys import Poly, cyclotomic_poly >>> from sympy.polys.numberfields.modules import PowerBasis >>> T = Poly(cyclotomic_poly(5)) >>> A = PowerBasis(T) >>> gens = [A(0), 2*A(1), 3*A(2), 4*A(3)//5] >>> B = A.submodule_from_gens(gens) >>> print(B) Submodule[[5, 0, 0, 0], [0, 10, 0, 0], [0, 0, 15, 0], [0, 0, 0, 4]]/5
See also
 submodule_from_matrix(B, denom=1)[source]¶
Form the submodule generated by the elements of this module indicated by the columns of a matrix, with an optional denominator.
 Parameters
B :
DomainMatrix
over ZZEach column gives the numerators of the coefficients of one generator of the submodule. Thus, the number of rows of B must equal the number of generators of the present module.
denom : int, optional (default=1)
Common denominator for all generators of the submodule.
 Returns
 Raises
ValueError
If the given matrix B is not over ZZ or its number of rows does not equal the number of generators of the present module.
Examples
>>> from sympy.polys import Poly, cyclotomic_poly, ZZ >>> from sympy.polys.matrices import DM >>> from sympy.polys.numberfields.modules import PowerBasis >>> T = Poly(cyclotomic_poly(5)) >>> A = PowerBasis(T) >>> B = A.submodule_from_matrix(DM([ ... [0, 10, 0, 0], ... [0, 0, 7, 0], ... ], ZZ).transpose(), denom=15) >>> print(B) Submodule[[0, 10, 0, 0], [0, 0, 7, 0]]/15
See also
 whole_submodule()[source]¶
Return a submodule equal to this entire module.
Explanation
This is useful when you have a
PowerBasis
and want to turn it into aSubmodule
(in order to use methods belonging to the latter).
 zero()[source]¶
Return a
ModuleElement
representing zero.
 class sympy.polys.numberfields.modules.PowerBasis(T)[source]¶
The module generated by the powers of an algebraic integer.
 element_from_poly(f)[source]¶
Produce an element of this module, representing f after reduction mod our defining minimal polynomial.
 Parameters
 Returns
 class sympy.polys.numberfields.modules.Submodule(parent, matrix, denom=1, mult_tab=None)[source]¶
A submodule of another module.
 __init__(parent, matrix, denom=1, mult_tab=None)[source]¶
 Parameters
parent :
Module
The module from which this one is derived.
matrix :
DomainMatrix
over ZZThe matrix whose columns define this submodule’s generators as linear combinations over the parent’s generators.
denom : int, optional (default=1)
Denominator for the coefficients given by the matrix.
mult_tab : dict,
None
, optionalIf already known, the multiplication table for this module may be supplied.
 property QQ_matrix¶
DomainMatrix
over QQ, equal toself.matrix / self.denom
, and guaranteed to be dense. Returns
DomainMatrix
over QQ
Explanation
Depending on how it is formed, a
DomainMatrix
may have an internal representation that is sparse or dense. We guarantee a dense representation here, so that tests for equivalence of submodules always come out as expected.Examples
>>> from sympy.polys import Poly, cyclotomic_poly, ZZ >>> from sympy.abc import x >>> from sympy.polys.matrices import DomainMatrix >>> from sympy.polys.numberfields.modules import PowerBasis >>> T = Poly(cyclotomic_poly(5, x)) >>> A = PowerBasis(T) >>> B = A.submodule_from_matrix(3*DomainMatrix.eye(4, ZZ), denom=6) >>> C = A.submodule_from_matrix(DomainMatrix.eye(4, ZZ), denom=2) >>> print(B.QQ_matrix == C.QQ_matrix) True
 add(other, hnf=True, hnf_modulus=None)[source]¶
Add this
Submodule
to another. Parameters
other :
Submodule
hnf : boolean, optional (default=True)
If
True
, reduce the matrix of the combined module to its Hermite Normal Form.hnf_modulus : ZZ, None, optional
If a positive integer is provided, use this as modulus in the HNF reduction. See
hermite_normal_form()
. Returns
Explanation
This represents the module generated by the union of the two modules’ sets of generators.
 basis_element_pullbacks()[source]¶
Return list of this submodule’s basis elements as elements of the submodule’s parent module.
 discard_before(r)[source]¶
Produce a new module by discarding all generators before a given index r.
 mul(other, hnf=True, hnf_modulus=None)[source]¶
Multiply this
Submodule
by a rational number, aModuleElement
, or anotherSubmodule
. Parameters
other : int, ZZ, QQ,
ModuleElement
,Submodule
hnf : boolean, optional (default=True)
If
True
, reduce the matrix of the product module to its Hermite Normal Form.hnf_modulus : ZZ, None, optional
If a positive integer is provided, use this as modulus in the HNF reduction. See
hermite_normal_form()
. Returns
Explanation
To multiply by a rational number or
ModuleElement
means to form the submodule whose generators are the products of this quantity with all the generators of the present submodule.To multiply by another
Submodule
means to form the submodule whose generators are all the products of one generator from the one submodule, and one generator from the other.
 reduced()[source]¶
Produce a reduced version of this submodule.
 Returns
Explanation
In the reduced version, it is guaranteed that 1 is the only positive integer dividing both the submodule’s denominator, and every entry in the submodule’s matrix.
 class sympy.polys.numberfields.modules.ModuleElement(module, col, denom=1)[source]¶
Represents an element of a
Module
.NOTE: Should not be constructed directly. Use the
__call__()
method or themake_mod_elt()
factory function instead. __init__(module, col, denom=1)[source]¶
 Parameters
module :
Module
The module to which this element belongs.
col :
DomainMatrix
over ZZColumn vector giving the numerators of the coefficients of this element.
denom : int, optional (default=1)
Denominator for the coefficients of this element.
 __add__(other)[source]¶
A
ModuleElement
can be added to a rational number, or to anotherModuleElement
.Explanation
When the other summand is a rational number, it will be converted into a
ModuleElement
(belonging to the first ancestor of this module that starts with unity).In all cases, the sum belongs to the nearest common ancestor (NCA) of the modules of the two summands. If the NCA does not exist, we return
NotImplemented
.
 __mul__(other)[source]¶
A
ModuleElement
can be multiplied by a rational number, or by anotherModuleElement
.Explanation
When the multiplier is a rational number, the product is computed by operating directly on the coefficients of this
ModuleElement
.When the multiplier is another
ModuleElement
, the product will belong to the nearest common ancestor (NCA) of the modules of the two operands, and that NCA must have a multiplication table. If the NCA does not exist, we returnNotImplemented
. If the NCA does not have a mult. table,ClosureFailure
will be raised.
 __mod__(m)[source]¶
Reducing a
ModuleElement
mod an integer m reduces all numerator coeffs mod \(d m\), where \(d\) is the denominator of theModuleElement
.Explanation
Recall that a
ModuleElement
\(b\) represents a \(\mathbb{Q}\)linear combination over the basis elements \(\{\beta_0, \beta_1, \ldots, \beta_{n1}\}\) of a module \(B\). It uses a common denominator \(d\), so that the representation is in the form \(b=\frac{c_0 \beta_0 + c_1 \beta_1 + \cdots + c_{n1} \beta_{n1}}{d}\), with \(d\) and all \(c_i\) in \(\mathbb{Z}\), and \(d > 0\).If we want to work modulo \(m B\), this means we want to reduce the coefficients of \(b\) mod \(m\). We can think of reducing an arbitrary rational number \(r/s\) mod \(m\) as adding or subtracting an integer multiple of \(m\) so that the result is positive and less than \(m\). But this is equivalent to reducing \(r\) mod \(m \cdot s\).
Examples
>>> from sympy import Poly, cyclotomic_poly >>> from sympy.polys.numberfields.modules import PowerBasis >>> T = Poly(cyclotomic_poly(5)) >>> A = PowerBasis(T) >>> a = (A(0) + 15*A(1))//2 >>> print(a) [1, 15, 0, 0]/2
Here,
a
represents the number \(\frac{1 + 15\zeta}{2}\). If we reduce mod 7,>>> print(a % 7) [1, 1, 0, 0]/2
we get \(\frac{1 + \zeta}{2}\). Effectively, we subtracted \(7 \zeta\). But it was achieved by reducing the numerator coefficients mod \(14\).
 property QQ_col¶
DomainMatrix
over QQ, equal toself.col / self.denom
, and guaranteed to be dense.See also
 column(domain=None)[source]¶
Get a copy of this element’s column, optionally converting to a domain.
 equiv(other)[source]¶
A
ModuleElement
may test as equivalent to a rational number or anotherModuleElement
, if they represent the same algebraic number. Parameters
other : int, ZZ, QQ,
ModuleElement
 Returns
bool
 Raises
UnificationFailed
If
self
andother
do not share a commonPowerBasis
ancestor.
Explanation
This method is intended to check equivalence only in those cases in which it is easy to test; namely, when other is either a
ModuleElement
that can be unified with this one (i.e. one which shares a commonPowerBasis
ancestor), or else a rational number (which is easy because everyPowerBasis
represents every rational number).
 classmethod from_int_list(module, coeffs, denom=1)[source]¶
Make a
ModuleElement
from a list of ints (instead of a column vector).
 is_compat(other)[source]¶
Test whether other is another
ModuleElement
with same module.
 property n¶
The length of this element’s column.
 over_power_basis()[source]¶
Transform into a
PowerBasisElement
over ourPowerBasis
ancestor.
 reduced()[source]¶
Produce a reduced version of this ModuleElement, i.e. one in which the gcd of the denominator together with all numerator coefficients is 1.
 reduced_mod_p(p)[source]¶
Produce a version of this
ModuleElement
in which all numerator coefficients have been reduced mod p.
 to_ancestor(anc)[source]¶
Transform into a
ModuleElement
belonging to a given ancestor of this element’s module. Parameters
anc :
Module
 to_parent()[source]¶
Transform into a
ModuleElement
belonging to the parent of this element’s module.
 unify(other)[source]¶
Try to make a compatible pair of
ModuleElement
, one equivalent to this one, and one equivalent to the other. Returns
Pair
(e1, e2)
Each
ei
is aModuleElement
, they belong to the sameModule
,e1
is equivalent toself
, ande2
is equivalent toother
. Raises
UnificationFailed
If
self
andother
have no common ancestor module.
Explanation
We search for the nearest common ancestor module for the pair of elements, and represent each one there.
 class sympy.polys.numberfields.modules.PowerBasisElement(module, col, denom=1)[source]¶
Subclass for
ModuleElement
instances whose module is aPowerBasis
. property T¶
Access the defining polynomial of the
PowerBasis
.
 sympy.polys.numberfields.modules.make_mod_elt(module, col, denom=1)[source]¶
Factory function which builds a
ModuleElement
, but ensures that it is aPowerBasisElement
if the module is aPowerBasis
.
 class sympy.polys.numberfields.modules.ModuleHomomorphism(domain, codomain, mapping)[source]¶
A homomorphism from one module to another.
 __init__(domain, codomain, mapping)[source]¶
 Parameters
domain :
Module
The domain of the mapping.
codomain :
Module
The codomain of the mapping.
mapping : callable
An arbitrary callable is accepted, but should be chosen so as to represent an actual module homomorphism. In particular, should accept elements of domain and return elements of codomain.
Examples
>>> from sympy import Poly, cyclotomic_poly >>> from sympy.polys.numberfields.modules import PowerBasis, ModuleHomomorphism >>> T = Poly(cyclotomic_poly(5)) >>> A = PowerBasis(T) >>> B = A.submodule_from_gens([2*A(j) for j in range(4)]) >>> phi = ModuleHomomorphism(A, B, lambda x: 6*x) >>> print(phi.matrix()) DomainMatrix([[3, 0, 0, 0], [0, 3, 0, 0], [0, 0, 3, 0], [0, 0, 0, 3]], (4, 4), ZZ)
 kernel(modulus=None)[source]¶
Compute a Submodule representing the kernel of this homomorphism.
 Parameters
modulus : int, optional
A positive prime number \(p\) if the kernel should be computed mod \(p\).
 Returns

 class sympy.polys.numberfields.modules.ModuleEndomorphism(domain, mapping)[source]¶
A homomorphism from one module to itself.
 class sympy.polys.numberfields.modules.InnerEndomorphism(domain, multiplier)[source]¶
An inner endomorphism on a module, i.e. the endomorphism corresponding to multiplication by a fixed element.
 __init__(domain, multiplier)[source]¶
 Parameters
domain :
Module
The domain and codomain of the endomorphism.
multiplier :
ModuleElement
The element \(a\) defining the mapping as \(x \mapsto a x\).
 class sympy.polys.numberfields.modules.EndomorphismRing(domain)[source]¶
The ring of endomorphisms on a module.
 inner_endomorphism(multiplier)[source]¶
Form an inner endomorphism belonging to this endomorphism ring.
 Parameters
multiplier :
ModuleElement
Element \(a\) defining the inner endomorphism \(x \mapsto a x\).
 Returns
 represent(element)[source]¶
Represent an element of this endomorphism ring, as a single column vector.
 Parameters
element :
ModuleEndomorphism
belonging to this ring. Returns

Column vector equalling the vertical stacking of all the columns of the matrix that represents the given element as a mapping.
Explanation
Let \(M\) be a module, and \(E\) its ring of endomorphisms. Let \(N\) be another module, and consider a homomorphism \(\varphi: N \rightarrow E\). In the event that \(\varphi\) is to be represented by a matrix \(A\), each column of \(A\) must represent an element of \(E\). This is possible when the elements of \(E\) are themselves representable as matrices, by stacking the columns of such a matrix into a single column.
This method supports calculating such matrices \(A\), by representing an element of this endomorphism ring first as a matrix, and then stacking that matrix’s columns into a single column.
Examples
Note that in these examples we print matrix transposes, to make their columns easier to inspect.
>>> from sympy import Poly, cyclotomic_poly >>> from sympy.polys.numberfields.modules import PowerBasis >>> from sympy.polys.numberfields.modules import ModuleHomomorphism >>> T = Poly(cyclotomic_poly(5)) >>> M = PowerBasis(T) >>> E = M.endomorphism_ring()
Let \(\zeta\) be a primitive 5th root of unity, a generator of our field, and consider the inner endomorphism \(\tau\) on the ring of integers, induced by \(\zeta\):
>>> zeta = M(1) >>> tau = E.inner_endomorphism(zeta) >>> tau.matrix().transpose() DomainMatrix( [[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, 1, 1, 1]], (4, 4), ZZ)
The matrix representation of \(\tau\) is as expected. The first column shows that multiplying by \(\zeta\) carries \(1\) to \(\zeta\), the second column that it carries \(\zeta\) to \(\zeta^2\), and so forth.
The
represent
method of the endomorphism ringE
stacks these into a single column:>>> E.represent(tau).transpose() DomainMatrix( [[0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1]], (1, 16), ZZ)
This is useful when we want to consider a homomorphism \(\varphi\) having
E
as codomain:>>> phi = ModuleHomomorphism(M, E, lambda x: E.inner_endomorphism(x))
and we want to compute the matrix of such a homomorphism:
>>> phi.matrix().transpose() DomainMatrix( [[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1], [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1], [0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0]], (4, 16), ZZ)
Note that the stacked matrix of \(\tau\) occurs as the second column in this example. This is because \(\zeta\) is the second basis element of
M
, and \(\varphi(\zeta) = \tau\).
 sympy.polys.numberfields.modules.find_min_poly(alpha, domain, x=None, powers=None)[source]¶
Find a polynomial of least degree (not necessarily irreducible) satisfied by an element of a finitelygenerated ring with unity.
 Parameters
alpha :
ModuleElement
The element whose min poly is to be found, and whose module has multiplication and starts with unity.
domain :
Domain
The desired domain of the polynomial.
x :
Symbol
, optionalThe desired variable for the polynomial.
powers : list, optional
If desired, pass an empty list. The powers of alpha (as
ModuleElement
instances) from the zeroth up to the degree of the min poly will be recorded here, as we compute them. Returns
Poly
,None
The minimal polynomial for alpha, or
None
if no polynomial could be found over the desired domain. Raises
MissingUnityError
If the module to which alpha belongs does not start with unity.
ClosureFailure
If the module to which alpha belongs is not closed under multiplication.
Examples
For the \(n\)th cyclotomic field, \(n\) an odd prime, consider the quadratic equation whose roots are the two periods of length \((n1)/2\). Article 356 of Gauss tells us that we should get \(x^2 + x  (n1)/4\) or \(x^2 + x + (n+1)/4\) according to whether \(n\) is 1 or 3 mod 4, respectively.
>>> from sympy import Poly, cyclotomic_poly, primitive_root, QQ >>> from sympy.abc import x >>> from sympy.polys.numberfields.modules import PowerBasis, find_min_poly >>> n = 13 >>> g = primitive_root(n) >>> C = PowerBasis(Poly(cyclotomic_poly(n, x))) >>> ee = [g**(2*k+1) % n for k in range((n1)//2)] >>> eta = sum(C(e) for e in ee) >>> print(find_min_poly(eta, QQ, x=x).as_expr()) x**2 + x  3 >>> n = 19 >>> g = primitive_root(n) >>> C = PowerBasis(Poly(cyclotomic_poly(n, x))) >>> ee = [g**(2*k+2) % n for k in range((n1)//2)] >>> eta = sum(C(e) for e in ee) >>> print(find_min_poly(eta, QQ, x=x).as_expr()) x**2 + x + 5
Utilities¶
 sympy.polys.numberfields.utilities.is_rat(c)[source]¶
Test whether an argument is of an acceptable type to be used as a rational number.
Explanation
Returns
True
on any argument of typeint
, ZZ, or QQ.See also
 sympy.polys.numberfields.utilities.is_int(c)[source]¶
Test whether an argument is of an acceptable type to be used as an integer.
Explanation
Returns
True
on any argument of typeint
or ZZ.See also
 sympy.polys.numberfields.utilities.get_num_denom(c)[source]¶
Given any argument on which
is_rat()
isTrue
, return the numerator and denominator of this number.See also
 sympy.polys.numberfields.utilities.extract_fundamental_discriminant(a)[source]¶
Extract a fundamental discriminant from an integer a.
 Parameters
a: int, must be 0 or 1 mod 4
 Returns
Pair
(D, F)
of dictionaries. Raises
ValueError
If a is not 0 or 1 mod 4.
Explanation
Given any rational integer a that is 0 or 1 mod 4, write \(a = d f^2\), where \(d\) is either 1 or a fundamental discriminant, and return a pair of dictionaries
(D, F)
giving the prime factorizations of \(d\) and \(f\) respectively, in the same format returned byfactorint()
.A fundamental discriminant \(d\) is different from unity, and is either 1 mod 4 and squarefree, or is 0 mod 4 and such that \(d/4\) is squarefree and 2 or 3 mod 4. This is the same as being the discriminant of some quadratic field.
Examples
>>> from sympy.polys.numberfields.utilities import extract_fundamental_discriminant >>> print(extract_fundamental_discriminant(432)) ({3: 1, 1: 1}, {2: 2, 3: 1})
For comparison:
>>> from sympy import factorint >>> print(factorint(432)) {2: 4, 3: 3, 1: 1}
References
 R711
Cohen, H. A Course in Computational Algebraic Number Theory. (See Prop. 5.1.3)
 class sympy.polys.numberfields.utilities.AlgIntPowers(T, modulus=None)[source]¶
Compute the powers of an algebraic integer.
Explanation
Given an algebraic integer \(\theta\) by its monic irreducible polynomial
T
over ZZ, this class computes representations of arbitrarily high powers of \(\theta\), as ZZlinear combinations over \(\{1, \theta, \ldots, \theta^{n1}\}\), where \(n = \deg(T)\).The representations are computed using the linear recurrence relations for powers of \(\theta\), derived from the polynomial
T
. See [1], Sec. 4.2.2.Optionally, the representations may be reduced with respect to a modulus.
Examples
>>> from sympy import Poly, cyclotomic_poly >>> from sympy.polys.numberfields.utilities import AlgIntPowers >>> T = Poly(cyclotomic_poly(5)) >>> zeta_pow = AlgIntPowers(T) >>> print(zeta_pow[0]) [1, 0, 0, 0] >>> print(zeta_pow[1]) [0, 1, 0, 0] >>> print(zeta_pow[4]) [1, 1, 1, 1] >>> print(zeta_pow[24]) [1, 1, 1, 1]
References
 R712
Cohen, H. A Course in Computational Algebraic Number Theory.
 sympy.polys.numberfields.utilities.coeff_search(m, R)[source]¶
Generate coefficients for searching through polynomials.
 Parameters
m : int
Length of coeff list.
R : int
Initial max abs val for coeffs (will increase as search proceeds).
 Returns
generator
Infinite generator of lists of coefficients.
Explanation
Lead coeff is always nonnegative. Explore all combinations with coeffs bounded in absolute value before increasing the bound. Skip the allzero list, and skip any repeats. See examples.
Examples
>>> from sympy.polys.numberfields.utilities import coeff_search >>> cs = coeff_search(2, 1) >>> C = [next(cs) for i in range(13)] >>> print(C) [[1, 1], [1, 0], [1, 1], [0, 1], [2, 2], [2, 1], [2, 0], [2, 1], [2, 2], [1, 2], [1, 2], [0, 2], [3, 3]]
 sympy.polys.numberfields.utilities.supplement_a_subspace(M)[source]¶
Extend a basis for a subspace to a basis for the whole space.
 Parameters
M :
DomainMatrix
The columns give the basis for the subspace.
 Returns

This matrix is invertible and its first \(r\) columns equal M.
 Raises
DMRankError
If M was not of maximal rank.
Explanation
Given an \(n \times r\) matrix M of rank \(r\) (so \(r \leq n\)), this function computes an invertible \(n \times n\) matrix \(B\) such that the first \(r\) columns of \(B\) equal M.
This operation can be interpreted as a way of extending a basis for a subspace, to give a basis for the whole space.
To be precise, suppose you have an \(n\)dimensional vector space \(V\), with basis \(\{v_1, v_2, \ldots, v_n\}\), and an \(r\)dimensional subspace \(W\) of \(V\), spanned by a basis \(\{w_1, w_2, \ldots, w_r\}\), where the \(w_j\) are given as linear combinations of the \(v_i\). If the columns of M represent the \(w_j\) as such linear combinations, then the columns of the matrix \(B\) computed by this function give a new basis \(\{u_1, u_2, \ldots, u_n\}\) for \(V\), again relative to the \(\{v_i\}\) basis, and such that \(u_j = w_j\) for \(1 \leq j \leq r\).
Examples
Note: The function works in terms of columns, so in these examples we print matrix transposes in order to make the columns easier to inspect.
>>> from sympy.polys.matrices import DM >>> from sympy import QQ, FF >>> from sympy.polys.numberfields.utilities import supplement_a_subspace >>> M = DM([[1, 7, 0], [2, 3, 4]], QQ).transpose() >>> print(supplement_a_subspace(M).to_Matrix().transpose()) Matrix([[1, 7, 0], [2, 3, 4], [1, 0, 0]])
>>> M2 = M.convert_to(FF(7)) >>> print(M2.to_Matrix().transpose()) Matrix([[1, 0, 0], [2, 3, 3]]) >>> print(supplement_a_subspace(M2).to_Matrix().transpose()) Matrix([[1, 0, 0], [2, 3, 3], [0, 1, 0]])
References
 R713
Cohen, H. A Course in Computational Algebraic Number Theory (See Sec. 2.3.2.)
 sympy.polys.numberfields.utilities.isolate(alg, eps=None, fast=False)[source]¶
Find a rational isolating interval for a real algebraic number.
 Parameters
alg : str, int,
Expr
The algebraic number to be isolated. Must be a real number, to use this particular function. However, see also
Poly.intervals()
, which isolates complex roots when you passall=True
.eps : positive element of QQ, None, optional (default=None)
Precision to be passed to
Poly.refine_root()
fast : boolean, optional (default=False)
Say whether fast refinement procedure should be used. (Will be passed to
Poly.refine_root()
.) Returns
Pair of rational numbers defining an isolating interval for the given
algebraic number.
Examples
>>> from sympy import isolate, sqrt, Rational >>> print(isolate(sqrt(2))) (1, 2) >>> print(isolate(sqrt(2), eps=Rational(1, 100))) (24/17, 17/12)
See also