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:

1. an integral basis of \(\mathbb{Z}_K\)

2. the decomposition of rational primes in \(\mathbb{Z}_K\)

3. \(\mathfrak{p}\)-adic valuations for ideals and elements

4. the Galois group of the Galois closure of \(K\)

5. a system of fundamental units of \(K\)

6. the regulator \(R(K)\)

7. the class number

8. the structure of the class group \(Cl(K)\)

9. 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.

10. 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}\).

11. 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.

12. 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]\).

13. 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
integral basis	round_two()
prime decomposition	prime_decomp()
\(\mathfrak{p}\)-adic valuation	prime_valuation()
Galois group	galois_group()
find minimal polynomial	minimal_polynomial()
subfield	field_isomorphism()
field membership	to_number_field()
primitive element	primitive_element()

Solving the Main Problems

Integral Basis

sympy.polys.numberfields.basis.round_two(T, radicals=None)

Zassenhaus’s “Round 2” algorithm.

Parameters:

T : Poly, AlgebraicField

Either (1) the irreducible polynomial over ZZ or QQ defining the number field, or (2) an AlgebraicField representing the number field itself.

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 a Submodule 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 an irreducible polynomial T over ZZ or QQ. This computes an integral basis and the discriminant for the field \(K = \mathbb{Q}[x]/(T(x))\).

Alternatively, you may pass an AlgebraicField instance, in place of the polynomial T, in which case the algorithm is applied to the minimal polynomial for the field’s primitive element.

Ordinarily this function need not be called directly, as one can instead access the maximal_order(), integral_basis(), and discriminant() methods of an AlgebraicField.

Examples

Working through an AlgebraicField:

>>> from sympy import Poly, QQ
>>> from sympy.abc import x
>>> T = Poly(x ** 3 + x ** 2 - 2 * x + 8)
>>> K = QQ.alg_field_from_poly(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 + theta**2/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]]}

See also

AlgebraicField.maximal_order, AlgebraicField.integral_basis, AlgebraicField.discriminant

References

[R802]

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)

Compute the decomposition of rational prime p in a number field.

Parameters:

p : int

The rational prime whose decomposition is desired.

T : Poly, optional

Monic irreducible polynomial defining the number field \(K\) in which to factor. NOTE: at least one of T or ZK must be provided.

ZK : Submodule, optional

The 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, optional

The 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 an AlgebraicField.

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

[R803]

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)

A prime ideal in a ring of algebraic integers.

__init__(ZK, p, alpha, f, e=None)

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, optional

The ramification index, if already known. If None, we will compute it here.

__add__(other)

Convert to a Submodule and add to another Submodule.

See also

as_submodule

__mul__(other)

Convert to a Submodule and multiply by another Submodule or a rational number.

See also

as_submodule

as_submodule()

Represent this prime ideal as a Submodule.

Returns:

Submodule

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 two-generator representation, as well as to offer helpful methods like valuation() and test_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 non-negative 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 to Submodule on the right:

>>> print(P0 + 7*P0.ZK == P0.as_submodule())
True

See also

__add__, __mul__

property is_inert

Say whether the rational prime we divide is inert, i.e. stays prime in our ring of integers.

reduce_ANP(a)

Reduce an ANP to a “small representative” modulo this prime ideal.

Parameters:

elt : ANP

The element to be reduced.

Returns:

ANP

The reduced element.

See also

reduce_element, reduce_alg_num, Submodule.reduce_element

reduce_alg_num(a)

Reduce an AlgebraicNumber to a “small representative” modulo this prime ideal.

Parameters:

elt : AlgebraicNumber

The element to be reduced.

Returns:

AlgebraicNumber

The reduced element.

See also

reduce_element, reduce_ANP, Submodule.reduce_element

reduce_element(elt)

Reduce a PowerBasisElement to a “small representative” modulo this prime ideal.

Parameters:

elt : PowerBasisElement

The element to be reduced.

Returns:

PowerBasisElement

The reduced element.

See also

reduce_ANP, reduce_alg_num, Submodule.reduce_element

repr(field_gen=None, just_gens=False)

Print a representation of this prime ideal.

Parameters:

field_gen : Symbol, None, optional (default=None)

The symbol to use for the generator of the field. This will appear in our representation of self.alpha. If None, we use the variable of the defining polynomial of self.ZK.

just_gens : bool, optional (default=False)

If True, just print the “(p, alpha)” part, showing “just the generators” of the prime ideal. Otherwise, print a string of the form “[ (p, alpha) e=…, f=… ]”, giving the ramification index and inertia degree, along with the generators.

Examples

>>> from sympy import cyclotomic_poly, QQ
>>> from sympy.abc import x, zeta
>>> T = cyclotomic_poly(7, x)
>>> K = QQ.algebraic_field((T, zeta))
>>> P = K.primes_above(11)
>>> print(P[0].repr())
[ (11, x**3 + 5*x**2 + 4*x - 1) e=1, f=3 ]
>>> print(P[0].repr(field_gen=zeta))
[ (11, zeta**3 + 5*zeta**2 + 4*zeta - 1) e=1, f=3 ]
>>> print(P[0].repr(field_gen=zeta, just_gens=True))
(11, zeta**3 + 5*zeta**2 + 4*zeta - 1)

test_factor()

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.

valuation(I)

Compute the \(\mathfrak{p}\)-adic valuation of integral ideal I at this prime ideal.

Parameters:

I : Submodule

See also

prime_valuation

p-adic Valuation

sympy.polys.numberfields.primes.prime_valuation(I, P)

Compute the P-adic 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.polys.numberfields import prime_valuation
>>> K = QQ.cyclotomic_field(5)
>>> P = K.primes_above(5)
>>> ZK = K.maximal_order()
>>> print(prime_valuation(25*ZK, P[0]))
8

See also

PrimeIdeal.valuation

References

[R804]

Cohen, H. A Course in Computational Algebraic Number Theory. (See Algorithm 4.8.17.)

Galois Groups

sympy.polys.numberfields.galoisgroups.galois_group(f, *gens, by_name=False, max_tries=30, randomize=False, **args)

Compute the Galois group for polynomials f up to degree 6.

Parameters:

f : Expr

Irreducible polynomial over ZZ or QQ, whose Galois group is to be determined.

gens : optional list of symbols

For converting f to Poly, and will be passed on to the poly_from_expr() function.

by_name : bool, default False

If True, the Galois group will be returned by name. Otherwise it will be returned as a PermutationGroup.

max_tries : int, default 30

Make at most this many attempts in those steps that involve generating Tschirnhausen transformations.

randomize : bool, default False

If True, then use random coefficients when generating Tschirnhausen transformations. Otherwise try transformations in a fixed order. Both approaches start with small coefficients and degrees and work upward.

args : optional

For converting f to Poly, and will be passed on to the poly_from_expr() function.

Returns:

Pair (G, alt)

The first element G indicates the Galois group. It is an instance of one of the sympy.combinatorics.galois.S1TransitiveSubgroups sympy.combinatorics.galois.S2TransitiveSubgroups, etc. enum classes if by_name was True, and a PermutationGroup if False.

The second element is a boolean, saying whether the group is contained in the alternating group \(A_n\) (\(n\) the degree of T).

Raises:

ValueError

if f is of an unsupported degree.

MaxTriesException

if could not complete before exceeding max_tries in those steps that involve generating Tschirnhausen transformations.

Examples

>>> from sympy import galois_group
>>> from sympy.abc import x
>>> f = x**4 + 1
>>> G, alt = galois_group(f)
>>> print(G)
PermutationGroup([
(0 1)(2 3),
(0 2)(1 3)])

The group is returned along with a boolean, indicating whether it is contained in the alternating group \(A_n\), where \(n\) is the degree of T. Along with other group properties, this can help determine which group it is:

>>> alt
True
>>> G.order()
4

Alternatively, the group can be returned by name:

>>> G_name, _ = galois_group(f, by_name=True)
>>> print(G_name)
S4TransitiveSubgroups.V

The group itself can then be obtained by calling the name’s get_perm_group() method:

>>> G_name.get_perm_group()
PermutationGroup([
(0 1)(2 3),
(0 2)(1 3)])

Group names are values of the enum classes sympy.combinatorics.galois.S1TransitiveSubgroups, sympy.combinatorics.galois.S2TransitiveSubgroups, etc.

See also

Poly.galois_group

Finding Minimal Polynomials

sympy.polys.numberfields.minpoly.minimal_polynomial(ex, x=None, compose=True, polys=False, domain=None)

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, if compose=False then groebner bases are used.

polys : boolean, optional (default=False)

If True returns a Poly object else an Expr object.

domain : Domain, optional

Ground domain

Notes

By default compose=True, the minimal polynomial of the subexpressions of ex are computed, then the arithmetic operations on them are performed using the resultant and factorization. If compose=False, a bottom-up algorithm is used with groebner. 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)

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)

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. If False, 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)

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)

If True, return the minimal polynomial as a Poly. Otherwise return it as an Expr.

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 argument ex=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 non-negative 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 generators sqrt(2) and sqrt(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 arg ex=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, alias=None)

Express one algebraic number in the field generated by another.

Parameters:

extension : Expr or list of Expr

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. If None, then this function reduces to a shorthand for calling primitive_element() on extension and turning the computed primitive element into an AlgebraicNumber.

gen : Symbol, None, optional (default=None)

If provided, this will be used as the generator symbol for the minimal polynomial in the returned AlgebraicNumber.

alias : str, Symbol, None, optional (default=None)

If provided, this will be used as the alias 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

field_isomorphism, primitive_element

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 finitely-generated modules

In computational algebraic number theory, finitely-generated \(\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 finitely-generated \(\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.

Finitely-generated 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\). The PowerBasis is constructed by passing either the minimal polynomial of \(\theta\), or an AlgebraicField having \(\theta\) as its primitive element.

• 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 the Submodule. 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

Generic finitely-generated module.

This is an abstract base class, and should not be instantiated directly. The two concrete subclasses are PowerBasis and Submodule.

Every Submodule is derived from another module, referenced by its parent attribute. If S is a submodule, then we refer to S.parent, S.parent.parent, and so on, as the “ancestors” of S. Thus, every Module is either a PowerBasis or a Submodule, some ancestor of which is a PowerBasis.

__call__(spec, denom=1)

Generate a ModuleElement belonging to this module.

Parameters:

spec : DomainMatrix, int

Specifies 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 integer j, \(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:

ModuleElement

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)

Return the list of ancestor modules of this module, from the foundational PowerBasis downward, optionally including self.

See also

Module

basis_elements()

Get list of ModuleElement being the generators of this module.

element_from_rational(a)

Return a ModuleElement representing a rational number.

Parameters:

a : int, ZZ, QQ

Returns:

ModuleElement

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()

Form the EndomorphismRing for this module.

is_compat_col(col)

Say whether col is a suitable column vector for this module.

mult_tab()

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, then M[i][j] is the list c of coefficients such that g[i] * g[j] == sum(c[k]*g[k], k in range(self.n)), where g is the list of generators of this module.

If j < i then M[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)

Locate the nearest common ancestor of this module and another.

Returns:

Module, None

See also

Module

property number_field

Return the associated AlgebraicField, if any.

Returns:

AlgebraicField, None

Explanation

A PowerBasis can be constructed on a Poly \(f\) or on an AlgebraicField \(K\). In the latter case, the PowerBasis and all its descendant modules will return \(K\) as their .number_field property, while in the former case they will all return None.

one()

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 its parent attribute; for a PowerBasis this is None.

See also

Module

power_basis_ancestor()

Return the PowerBasis that is an ancestor of this module.

See also

Module

represent(elt)

Represent a module element as an integer-linear 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 ZZ

This 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 ZZ-linear combination over this module.

Explanation

In our system, to “represent” always means to write a ModuleElement as a ZZ-linear combination over the generators of the present Module. Furthermore, the incoming ModuleElement must belong to an ancestor of the present Module (or to the present Module itself).

The most common application is to represent a ModuleElement in a Submodule. 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 a ModuleEndomorphism on a PowerBasis.

In such a case, (1) the incoming ModuleElement must belong to the PowerBasis itself (since the latter has no proper ancestors) and (2) it is “representable” iff it belongs to \(\mathbb{Z}[\theta]\) (although generally a PowerBasisElement 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 represent a in the submodule B = 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.represent, PowerBasis.represent

starts_with_unity()

Say whether the module’s first generator equals unity.

submodule_from_gens(gens, hnf=True, hnf_modulus=None)

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:

Submodule

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

submodule_from_matrix(B, denom=1)

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 ZZ

Each 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:

Submodule

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

submodule_from_gens

whole_submodule()

Return a submodule equal to this entire module.

Explanation

This is useful when you have a PowerBasis and want to turn it into a Submodule (in order to use methods belonging to the latter).

zero()

Return a ModuleElement representing zero.

class sympy.polys.numberfields.modules.PowerBasis(T)

The module generated by the powers of an algebraic integer.

__init__(T)

Parameters:

T : Poly, AlgebraicField

Either (1) the monic, irreducible, univariate polynomial over ZZ, a root of which is the generator of the power basis, or (2) an AlgebraicField whose primitive element is the generator of the power basis.

element_from_ANP(a)

Convert an ANP into a PowerBasisElement.

element_from_alg_num(a)

Convert an AlgebraicNumber into a PowerBasisElement.

element_from_poly(f)

Produce an element of this module, representing f after reduction mod our defining minimal polynomial.

Parameters:

f : Poly over ZZ in same var as our defining poly.

Returns:

PowerBasisElement

represent(elt)

Represent a module element as an integer-linear combination over the generators of this module.

See also

Module.represent, Submodule.represent

class sympy.polys.numberfields.modules.Submodule(parent, matrix, denom=1, mult_tab=None)

A submodule of another module.

__init__(parent, matrix, denom=1, mult_tab=None)

Parameters:

parent : Module

The module from which this one is derived.

matrix : DomainMatrix over ZZ

The 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, optional

If already known, the multiplication table for this module may be supplied.

property QQ_matrix

DomainMatrix over QQ, equal to self.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)

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:

Submodule

Explanation

This represents the module generated by the union of the two modules’ sets of generators.

basis_element_pullbacks()

Return list of this submodule’s basis elements as elements of the submodule’s parent module.

discard_before(r)

Produce a new module by discarding all generators before a given index r.

mul(other, hnf=True, hnf_modulus=None)

Multiply this Submodule by a rational number, a ModuleElement, or another Submodule.

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:

Submodule

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.

reduce_element(elt)

If this submodule \(B\) has defining matrix \(W\) in square, maximal-rank Hermite normal form, then, given an element \(x\) of the parent module \(A\), we produce an element \(y \in A\) such that \(x - y \in B\), and the \(i\)th coordinate of \(y\) satisfies \(0 \leq y_i < w_{i,i}\). This representative \(y\) is unique, in the sense that every element of the coset \(x + B\) reduces to it under this procedure.

Parameters:

elt : ModuleElement

An element of this submodule’s parent module.

Returns:

elt : ModuleElement

An element of this submodule’s parent module.

Raises:

NotImplementedError

If the given ModuleElement does not belong to this submodule’s parent module.

StructureError

If this submodule’s defining matrix is not in square, maximal-rank Hermite normal form.

Explanation

In the special case where \(A\) is a power basis for a number field \(K\), and \(B\) is a submodule representing an ideal \(I\), this operation represents one of a few important ways of reducing an element of \(K\) modulo \(I\) to obtain a “small” representative. See [Cohen00] Section 1.4.3.

Examples

>>> from sympy import QQ, Poly, symbols
>>> t = symbols('t')
>>> k = QQ.alg_field_from_poly(Poly(t**3 + t**2 - 2*t + 8))
>>> Zk = k.maximal_order()
>>> A = Zk.parent
>>> B = (A(2) - 3*A(0))*Zk
>>> B.reduce_element(A(2))
[3, 0, 0]

References

[Cohen00] (1,2)

Cohen, H. Advanced Topics in Computational Number Theory.

reduced()

Produce a reduced version of this submodule.

Returns:

Submodule

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.

represent(elt)

Represent a module element as an integer-linear combination over the generators of this module.

See also

Module.represent, PowerBasis.represent

class sympy.polys.numberfields.modules.ModuleElement(module, col, denom=1)

Represents an element of a Module.

NOTE: Should not be constructed directly. Use the __call__() method or the make_mod_elt() factory function instead.

__init__(module, col, denom=1)

Parameters:

module : Module

The module to which this element belongs.

col : DomainMatrix over ZZ

Column vector giving the numerators of the coefficients of this element.

denom : int, optional (default=1)

Denominator for the coefficients of this element.

__add__(other)

A ModuleElement can be added to a rational number, or to another ModuleElement.

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)

A ModuleElement can be multiplied by a rational number, or by another ModuleElement.

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 return NotImplemented. If the NCA does not have a mult. table, ClosureFailure will be raised.

__mod__(m)

Reduce this ModuleElement mod a Submodule.

Parameters:

m : int, ZZ, QQ, Submodule

If a Submodule, reduce self relative to this. If an integer or rational, reduce relative to the Submodule that is our own module times this constant.

See also

Submodule.reduce_element

property QQ_col

DomainMatrix over QQ, equal to self.col / self.denom, and guaranteed to be dense.

See also

Submodule.QQ_matrix

column(domain=None)

Get a copy of this element’s column, optionally converting to a domain.

equiv(other)

A ModuleElement may test as equivalent to a rational number or another ModuleElement, if they represent the same algebraic number.

Parameters:

other : int, ZZ, QQ, ModuleElement

Returns:

bool

Raises:

UnificationFailed

If self and other do not share a common PowerBasis 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 common PowerBasis ancestor), or else a rational number (which is easy because every PowerBasis represents every rational number).

classmethod from_int_list(module, coeffs, denom=1)

Make a ModuleElement from a list of ints (instead of a column vector).

is_compat(other)

Test whether other is another ModuleElement with same module.

property n

The length of this element’s column.

over_power_basis()

Transform into a PowerBasisElement over our PowerBasis ancestor.

reduced()

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)

Produce a version of this ModuleElement in which all numerator coefficients have been reduced mod p.

to_ancestor(anc)

Transform into a ModuleElement belonging to a given ancestor of this element’s module.

Parameters:

anc : Module

to_parent()

Transform into a ModuleElement belonging to the parent of this element’s module.

unify(other)

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 a ModuleElement, they belong to the same Module, e1 is equivalent to self, and e2 is equivalent to other.

Raises:

UnificationFailed

If self and other 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)

Subclass for ModuleElement instances whose module is a PowerBasis.

property T

Access the defining polynomial of the PowerBasis.

as_expr(x=None)

Create a Basic expression from self.

property generator

Return a Symbol to be used when expressing this element as a polynomial.

If we have an associated AlgebraicField whose primitive element has an alias symbol, we use that. Otherwise we use the variable of the minimal polynomial defining the power basis to which we belong.

property is_rational

Say whether this element represents a rational number.

norm(T=None)

Compute the norm of this number.

numerator(x=None)

Obtain the numerator as a polynomial over ZZ.

poly(x=None)

Obtain the number as a polynomial over QQ.

to_ANP()

Convert to an equivalent ANP.

to_alg_num()

Try to convert to an equivalent AlgebraicNumber.

Returns:

AlgebraicNumber

Raises:

StructureError

If the PowerBasis to which this element belongs does not have an associated AlgebraicField.

Explanation

In general, the conversion from an AlgebraicNumber to a PowerBasisElement throws away information, because an AlgebraicNumber specifies a complex embedding, while a PowerBasisElement does not. However, in some cases it is possible to convert a PowerBasisElement back into an AlgebraicNumber, namely when the associated PowerBasis has a reference to an AlgebraicField.

sympy.polys.numberfields.modules.make_mod_elt(module, col, denom=1)

Factory function which builds a ModuleElement, but ensures that it is a PowerBasisElement if the module is a PowerBasis.

class sympy.polys.numberfields.modules.ModuleHomomorphism(domain, codomain, mapping)

A homomorphism from one module to another.

__init__(domain, codomain, mapping)

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)

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:

Submodule

This submodule’s generators span the kernel of this homomorphism over ZZ, or else over GF(p) if a modulus was given.

matrix(modulus=None)

Compute the matrix of this homomorphism.

Parameters:

modulus : int, optional

A positive prime number \(p\) if the matrix should be reduced mod \(p\).

Returns:

DomainMatrix

The matrix is over ZZ, or else over GF(p) if a modulus was given.

class sympy.polys.numberfields.modules.ModuleEndomorphism(domain, mapping)

A homomorphism from one module to itself.

__init__(domain, mapping)

Parameters:

domain : Module

The common domain and codomain of the mapping.

mapping : callable

An arbitrary callable is accepted, but should be chosen so as to represent an actual module endomorphism. In particular, should accept and return elements of domain.

class sympy.polys.numberfields.modules.InnerEndomorphism(domain, multiplier)

An inner endomorphism on a module, i.e. the endomorphism corresponding to multiplication by a fixed element.

__init__(domain, multiplier)

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)

The ring of endomorphisms on a module.

__init__(domain)

Parameters:

domain : Module

The domain and codomain of the endomorphisms.

inner_endomorphism(multiplier)

Form an inner endomorphism belonging to this endomorphism ring.

Parameters:

multiplier : ModuleElement

Element \(a\) defining the inner endomorphism \(x \mapsto a x\).

Returns:

InnerEndomorphism

represent(element)

Represent an element of this endomorphism ring, as a single column vector.

Parameters:

element : ModuleEndomorphism belonging to this ring.

Returns:

DomainMatrix

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 ring E 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)

Find a polynomial of least degree (not necessarily irreducible) satisfied by an element of a finitely-generated 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, optional

The 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 \((n-1)/2\). Article 356 of Gauss tells us that we should get \(x^2 + x - (n-1)/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((n-1)//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((n-1)//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)

Test whether an argument is of an acceptable type to be used as a rational number.

Explanation

Returns True on any argument of type int, ZZ, or QQ.

See also

is_int

sympy.polys.numberfields.utilities.is_int(c)

Test whether an argument is of an acceptable type to be used as an integer.

Explanation

Returns True on any argument of type int or ZZ.

See also

is_rat

sympy.polys.numberfields.utilities.get_num_denom(c)

Given any argument on which is_rat() is True, return the numerator and denominator of this number.

See also

is_rat

sympy.polys.numberfields.utilities.extract_fundamental_discriminant(a)

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 by factorint().

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

[R805]

Cohen, H. A Course in Computational Algebraic Number Theory. (See Prop. 5.1.3)

class sympy.polys.numberfields.utilities.AlgIntPowers(T, modulus=None)

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 ZZ-linear combinations over \(\{1, \theta, \ldots, \theta^{n-1}\}\), 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

[R806]

Cohen, H. A Course in Computational Algebraic Number Theory.

__init__(T, modulus=None)

Parameters:

T : Poly

The monic irreducible polynomial over ZZ defining the algebraic integer.

modulus : int, None, optional

If not None, all representations will be reduced w.r.t. this.

sympy.polys.numberfields.utilities.coeff_search(m, R)

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 non-negative. Explore all combinations with coeffs bounded in absolute value before increasing the bound. Skip the all-zero 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)

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:

DomainMatrix

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

[R807]

Cohen, H. A Course in Computational Algebraic Number Theory (See Sec. 2.3.2.)

sympy.polys.numberfields.utilities.isolate(alg, eps=None, fast=False)

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 pass all=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

Poly.intervals