Spaces:
Sleeping
Sleeping
| """Utilities for algebraic number theory. """ | |
| from sympy.core.sympify import sympify | |
| from sympy.ntheory.factor_ import factorint | |
| from sympy.polys.domains.rationalfield import QQ | |
| from sympy.polys.domains.integerring import ZZ | |
| from sympy.polys.matrices.exceptions import DMRankError | |
| from sympy.polys.numberfields.minpoly import minpoly | |
| from sympy.printing.lambdarepr import IntervalPrinter | |
| from sympy.utilities.decorator import public | |
| from sympy.utilities.lambdify import lambdify | |
| from mpmath import mp | |
| def is_rat(c): | |
| r""" | |
| 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``, :ref:`ZZ`, or :ref:`QQ`. | |
| See Also | |
| ======== | |
| is_int | |
| """ | |
| # ``c in QQ`` is too accepting (e.g. ``3.14 in QQ`` is ``True``), | |
| # ``QQ.of_type(c)`` is too demanding (e.g. ``QQ.of_type(3)`` is ``False``). | |
| # | |
| # Meanwhile, if gmpy2 is installed then ``ZZ.of_type()`` accepts only | |
| # ``mpz``, not ``int``, so we need another clause to ensure ``int`` is | |
| # accepted. | |
| return isinstance(c, int) or ZZ.of_type(c) or QQ.of_type(c) | |
| def is_int(c): | |
| r""" | |
| 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 :ref:`ZZ`. | |
| See Also | |
| ======== | |
| is_rat | |
| """ | |
| # If gmpy2 is installed then ``ZZ.of_type()`` accepts only | |
| # ``mpz``, not ``int``, so we need another clause to ensure ``int`` is | |
| # accepted. | |
| return isinstance(c, int) or ZZ.of_type(c) | |
| def get_num_denom(c): | |
| r""" | |
| Given any argument on which :py:func:`~.is_rat` is ``True``, return the | |
| numerator and denominator of this number. | |
| See Also | |
| ======== | |
| is_rat | |
| """ | |
| r = QQ(c) | |
| return r.numerator, r.denominator | |
| def extract_fundamental_discriminant(a): | |
| r""" | |
| Extract a fundamental discriminant from an integer *a*. | |
| 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 :py:func:`~.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} | |
| 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. | |
| References | |
| ========== | |
| .. [1] Cohen, H. *A Course in Computational Algebraic Number Theory.* | |
| (See Prop. 5.1.3) | |
| """ | |
| if a % 4 not in [0, 1]: | |
| raise ValueError('To extract fundamental discriminant, number must be 0 or 1 mod 4.') | |
| if a == 0: | |
| return {}, {0: 1} | |
| if a == 1: | |
| return {}, {} | |
| a_factors = factorint(a) | |
| D = {} | |
| F = {} | |
| # First pass: just make d squarefree, and a/d a perfect square. | |
| # We'll count primes (and units! i.e. -1) that are 3 mod 4 and present in d. | |
| num_3_mod_4 = 0 | |
| for p, e in a_factors.items(): | |
| if e % 2 == 1: | |
| D[p] = 1 | |
| if p % 4 == 3: | |
| num_3_mod_4 += 1 | |
| if e >= 3: | |
| F[p] = (e - 1) // 2 | |
| else: | |
| F[p] = e // 2 | |
| # Second pass: if d is cong. to 2 or 3 mod 4, then we must steal away | |
| # another factor of 4 from f**2 and give it to d. | |
| even = 2 in D | |
| if even or num_3_mod_4 % 2 == 1: | |
| e2 = F[2] | |
| assert e2 > 0 | |
| if e2 == 1: | |
| del F[2] | |
| else: | |
| F[2] = e2 - 1 | |
| D[2] = 3 if even else 2 | |
| return D, F | |
| class AlgIntPowers: | |
| r""" | |
| Compute the powers of an algebraic integer. | |
| Explanation | |
| =========== | |
| Given an algebraic integer $\theta$ by its monic irreducible polynomial | |
| ``T`` over :ref:`ZZ`, this class computes representations of arbitrarily | |
| high powers of $\theta$, as :ref:`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]) # doctest: +SKIP | |
| [-1, -1, -1, -1] | |
| >>> print(zeta_pow[24]) # doctest: +SKIP | |
| [-1, -1, -1, -1] | |
| References | |
| ========== | |
| .. [1] Cohen, H. *A Course in Computational Algebraic Number Theory.* | |
| """ | |
| def __init__(self, T, modulus=None): | |
| """ | |
| Parameters | |
| ========== | |
| T : :py:class:`~.Poly` | |
| The monic irreducible polynomial over :ref:`ZZ` defining the | |
| algebraic integer. | |
| modulus : int, None, optional | |
| If not ``None``, all representations will be reduced w.r.t. this. | |
| """ | |
| self.T = T | |
| self.modulus = modulus | |
| self.n = T.degree() | |
| self.powers_n_and_up = [[-c % self for c in reversed(T.rep.to_list())][:-1]] | |
| self.max_so_far = self.n | |
| def red(self, exp): | |
| return exp if self.modulus is None else exp % self.modulus | |
| def __rmod__(self, other): | |
| return self.red(other) | |
| def compute_up_through(self, e): | |
| m = self.max_so_far | |
| if e <= m: return | |
| n = self.n | |
| r = self.powers_n_and_up | |
| c = r[0] | |
| for k in range(m+1, e+1): | |
| b = r[k-1-n][n-1] | |
| r.append( | |
| [c[0]*b % self] + [ | |
| (r[k-1-n][i-1] + c[i]*b) % self for i in range(1, n) | |
| ] | |
| ) | |
| self.max_so_far = e | |
| def get(self, e): | |
| n = self.n | |
| if e < 0: | |
| raise ValueError('Exponent must be non-negative.') | |
| elif e < n: | |
| return [1 if i == e else 0 for i in range(n)] | |
| else: | |
| self.compute_up_through(e) | |
| return self.powers_n_and_up[e - n] | |
| def __getitem__(self, item): | |
| return self.get(item) | |
| def coeff_search(m, R): | |
| r""" | |
| Generate coefficients for searching through polynomials. | |
| 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]] | |
| 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. | |
| """ | |
| R0 = R | |
| c = [R] * m | |
| while True: | |
| if R == R0 or R in c or -R in c: | |
| yield c[:] | |
| j = m - 1 | |
| while c[j] == -R: | |
| j -= 1 | |
| c[j] -= 1 | |
| for i in range(j + 1, m): | |
| c[i] = R | |
| for j in range(m): | |
| if c[j] != 0: | |
| break | |
| else: | |
| R += 1 | |
| c = [R] * m | |
| def supplement_a_subspace(M): | |
| r""" | |
| Extend a basis for a subspace to a basis for the whole space. | |
| 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]]) | |
| Parameters | |
| ========== | |
| M : :py:class:`~.DomainMatrix` | |
| The columns give the basis for the subspace. | |
| Returns | |
| ======= | |
| :py:class:`~.DomainMatrix` | |
| This matrix is invertible and its first $r$ columns equal *M*. | |
| Raises | |
| ====== | |
| DMRankError | |
| If *M* was not of maximal rank. | |
| References | |
| ========== | |
| .. [1] Cohen, H. *A Course in Computational Algebraic Number Theory* | |
| (See Sec. 2.3.2.) | |
| """ | |
| n, r = M.shape | |
| # Let In be the n x n identity matrix. | |
| # Form the augmented matrix [M | In] and compute RREF. | |
| Maug = M.hstack(M.eye(n, M.domain)) | |
| R, pivots = Maug.rref() | |
| if pivots[:r] != tuple(range(r)): | |
| raise DMRankError('M was not of maximal rank') | |
| # Let J be the n x r matrix equal to the first r columns of In. | |
| # Since M is of rank r, RREF reduces [M | In] to [J | A], where A is the product of | |
| # elementary matrices Ei corresp. to the row ops performed by RREF. Since the Ei are | |
| # invertible, so is A. Let B = A^(-1). | |
| A = R[:, r:] | |
| B = A.inv() | |
| # Then B is the desired matrix. It is invertible, since B^(-1) == A. | |
| # And A * [M | In] == [J | A] | |
| # => A * M == J | |
| # => M == B * J == the first r columns of B. | |
| return B | |
| def isolate(alg, eps=None, fast=False): | |
| """ | |
| Find a rational isolating interval for a real algebraic number. | |
| Examples | |
| ======== | |
| >>> from sympy import isolate, sqrt, Rational | |
| >>> print(isolate(sqrt(2))) # doctest: +SKIP | |
| (1, 2) | |
| >>> print(isolate(sqrt(2), eps=Rational(1, 100))) | |
| (24/17, 17/12) | |
| Parameters | |
| ========== | |
| alg : str, int, :py:class:`~.Expr` | |
| The algebraic number to be isolated. Must be a real number, to use this | |
| particular function. However, see also :py:meth:`.Poly.intervals`, | |
| which isolates complex roots when you pass ``all=True``. | |
| eps : positive element of :ref:`QQ`, None, optional (default=None) | |
| Precision to be passed to :py:meth:`.Poly.refine_root` | |
| fast : boolean, optional (default=False) | |
| Say whether fast refinement procedure should be used. | |
| (Will be passed to :py:meth:`.Poly.refine_root`.) | |
| Returns | |
| ======= | |
| Pair of rational numbers defining an isolating interval for the given | |
| algebraic number. | |
| See Also | |
| ======== | |
| .Poly.intervals | |
| """ | |
| alg = sympify(alg) | |
| if alg.is_Rational: | |
| return (alg, alg) | |
| elif not alg.is_real: | |
| raise NotImplementedError( | |
| "complex algebraic numbers are not supported") | |
| func = lambdify((), alg, modules="mpmath", printer=IntervalPrinter()) | |
| poly = minpoly(alg, polys=True) | |
| intervals = poly.intervals(sqf=True) | |
| dps, done = mp.dps, False | |
| try: | |
| while not done: | |
| alg = func() | |
| for a, b in intervals: | |
| if a <= alg.a and alg.b <= b: | |
| done = True | |
| break | |
| else: | |
| mp.dps *= 2 | |
| finally: | |
| mp.dps = dps | |
| if eps is not None: | |
| a, b = poly.refine_root(a, b, eps=eps, fast=fast) | |
| return (a, b) | |