.. _polys-numberfields: .. currentmodule:: sympy.polys.numberfields ============= 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 :py:mod:`~.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 ================================= ====================================== (1) integral basis :py:func:`~.round_two` (2) prime decomposition :py:func:`~.prime_decomp` (3) $\mathfrak{p}$-adic valuation :py:func:`~.prime_valuation` (10) find minimal polynomial :py:func:`~.minimal_polynomial` (11) subfield :py:func:`~.field_isomorphism` (12) field membership :py:func:`~.to_number_field` (13) primitive element :py:func:`~.primitive_element` ================================= ====================================== Solving the Main Problems ========================= Integral Basis -------------- .. _IntegralBasis: .. currentmodule:: sympy.polys.numberfields.basis .. autofunction:: round_two Prime Decomposition ------------------- .. _PrimeDecomposition: .. currentmodule:: sympy.polys.numberfields.primes .. autofunction:: prime_decomp .. autoclass:: PrimeIdeal :members: .. automethod:: PrimeIdeal.__init__ .. automethod:: PrimeIdeal.__add__ .. automethod:: PrimeIdeal.__mul__ p-adic Valuation ---------------- .. _pAdicValuation: .. currentmodule:: sympy.polys.numberfields.primes .. autofunction:: prime_valuation Finding Minimal Polynomials --------------------------- .. _MinimalPolynomials: .. currentmodule:: sympy.polys.numberfields.minpoly .. autofunction:: minimal_polynomial .. autofunction:: minpoly The Subfield Problem -------------------- .. _SubfieldProblem: .. automodule:: sympy.polys.numberfields.subfield .. autofunction:: field_isomorphism .. autofunction:: primitive_element .. autofunction:: to_number_field Internals ========= Algebraic number fields ----------------------- Algebraic number fields are represented in SymPy by the :py:class:`~.AlgebraicField` class, which is a part of :ref:`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 :py:mod:`sympy.core.numbers` module on the one hand, and domains and domain elements defined in the :py:mod:`~sympy.polys` module on the other. This is explained in more detail :ref:`here`. When it comes to algebraic numbers, the :py:mod:`sympy.core.numbers` module offers the :py:class:`~.AlgebraicNumber` class, while the :py:mod:`~sympy.polys` module offers the :py:class:`~sympy.polys.polyclasses.ANP` class. This is the type of domain elements belonging to the :py:class:`~.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 :py:mod:`~.modules` module. Here, the :py:class:`~.ModuleElement` class provides another way to represent algebraic numbers. Finitely-generated modules -------------------------- .. automodule:: sympy.polys.numberfields.modules Class Reference ``````````````` .. autoclass:: Module :members: .. automethod:: Module.__call__ .. autoclass:: PowerBasis :members: .. automethod:: PowerBasis.__init__ .. autoclass:: Submodule :members: .. automethod:: Submodule.__init__ .. autoclass:: ModuleElement :members: .. automethod:: ModuleElement.__init__ .. automethod:: ModuleElement.__add__ .. automethod:: ModuleElement.__mul__ .. automethod:: ModuleElement.__mod__ .. autoclass:: PowerBasisElement :members: .. autofunction:: make_mod_elt .. autoclass:: ModuleHomomorphism :members: .. automethod:: ModuleHomomorphism.__init__ .. autoclass:: ModuleEndomorphism :members: .. automethod:: ModuleEndomorphism.__init__ .. autoclass:: InnerEndomorphism :members: .. automethod:: InnerEndomorphism.__init__ .. autoclass:: EndomorphismRing :members: .. automethod:: EndomorphismRing.__init__ .. autofunction:: find_min_poly Utilities --------- .. currentmodule:: sympy.polys.numberfields.utilities .. autofunction:: is_rat .. autofunction:: is_int .. autofunction:: get_num_denom .. autofunction:: extract_fundamental_discriminant .. autoclass:: AlgIntPowers :members: .. automethod:: AlgIntPowers.__init__ .. autofunction:: coeff_search .. autofunction:: supplement_a_subspace .. autofunction:: isolate .. _ideal: https://en.wikipedia.org/wiki/Ideal_(ring_theory) .. _order: https://en.wikipedia.org/wiki/Order_(ring_theory) .. _ring of integers: https://en.wikipedia.org/wiki/Ring_of_integers .. _integral basis: https://en.wikipedia.org/wiki/Algebraic_number_field#Integral_basis