You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
508 lines
16 KiB
508 lines
16 KiB
r"""
|
|
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]$.
|
|
"""
|
|
|
|
from sympy.core.add import Add
|
|
from sympy.core.numbers import AlgebraicNumber
|
|
from sympy.core.singleton import S
|
|
from sympy.core.symbol import Dummy
|
|
from sympy.core.sympify import sympify, _sympify
|
|
from sympy.ntheory import sieve
|
|
from sympy.polys.densetools import dup_eval
|
|
from sympy.polys.domains import QQ
|
|
from sympy.polys.numberfields.minpoly import _choose_factor, minimal_polynomial
|
|
from sympy.polys.polyerrors import IsomorphismFailed
|
|
from sympy.polys.polytools import Poly, PurePoly, factor_list
|
|
from sympy.utilities import public
|
|
|
|
from mpmath import MPContext
|
|
|
|
|
|
def is_isomorphism_possible(a, b):
|
|
"""Necessary but not sufficient test for isomorphism. """
|
|
n = a.minpoly.degree()
|
|
m = b.minpoly.degree()
|
|
|
|
if m % n != 0:
|
|
return False
|
|
|
|
if n == m:
|
|
return True
|
|
|
|
da = a.minpoly.discriminant()
|
|
db = b.minpoly.discriminant()
|
|
|
|
i, k, half = 1, m//n, db//2
|
|
|
|
while True:
|
|
p = sieve[i]
|
|
P = p**k
|
|
|
|
if P > half:
|
|
break
|
|
|
|
if ((da % p) % 2) and not (db % P):
|
|
return False
|
|
|
|
i += 1
|
|
|
|
return True
|
|
|
|
|
|
def field_isomorphism_pslq(a, b):
|
|
"""Construct field isomorphism using PSLQ algorithm. """
|
|
if not a.root.is_real or not b.root.is_real:
|
|
raise NotImplementedError("PSLQ doesn't support complex coefficients")
|
|
|
|
f = a.minpoly
|
|
g = b.minpoly.replace(f.gen)
|
|
|
|
n, m, prev = 100, b.minpoly.degree(), None
|
|
ctx = MPContext()
|
|
|
|
for i in range(1, 5):
|
|
A = a.root.evalf(n)
|
|
B = b.root.evalf(n)
|
|
|
|
basis = [1, B] + [ B**i for i in range(2, m) ] + [-A]
|
|
|
|
ctx.dps = n
|
|
coeffs = ctx.pslq(basis, maxcoeff=10**10, maxsteps=1000)
|
|
|
|
if coeffs is None:
|
|
# PSLQ can't find an integer linear combination. Give up.
|
|
break
|
|
|
|
if coeffs != prev:
|
|
prev = coeffs
|
|
else:
|
|
# Increasing precision didn't produce anything new. Give up.
|
|
break
|
|
|
|
# We have
|
|
# c0 + c1*B + c2*B^2 + ... + cm-1*B^(m-1) - cm*A ~ 0.
|
|
# So bring cm*A to the other side, and divide through by cm,
|
|
# for an approximate representation of A as a polynomial in B.
|
|
# (We know cm != 0 since `b.minpoly` is irreducible.)
|
|
coeffs = [S(c)/coeffs[-1] for c in coeffs[:-1]]
|
|
|
|
# Throw away leading zeros.
|
|
while not coeffs[-1]:
|
|
coeffs.pop()
|
|
|
|
coeffs = list(reversed(coeffs))
|
|
h = Poly(coeffs, f.gen, domain='QQ')
|
|
|
|
# We only have A ~ h(B). We must check whether the relation is exact.
|
|
if f.compose(h).rem(g).is_zero:
|
|
# Now we know that h(b) is in fact equal to _some conjugate of_ a.
|
|
# But from the very precise approximation A ~ h(B) we can assume
|
|
# the conjugate is a itself.
|
|
return coeffs
|
|
else:
|
|
n *= 2
|
|
|
|
return None
|
|
|
|
|
|
def field_isomorphism_factor(a, b):
|
|
"""Construct field isomorphism via factorization. """
|
|
_, factors = factor_list(a.minpoly, extension=b)
|
|
for f, _ in factors:
|
|
if f.degree() == 1:
|
|
# Any linear factor f(x) represents some conjugate of a in QQ(b).
|
|
# We want to know whether this linear factor represents a itself.
|
|
# Let f = x - c
|
|
c = -f.rep.TC()
|
|
# Write c as polynomial in b
|
|
coeffs = c.to_sympy_list()
|
|
d, terms = len(coeffs) - 1, []
|
|
for i, coeff in enumerate(coeffs):
|
|
terms.append(coeff*b.root**(d - i))
|
|
r = Add(*terms)
|
|
# Check whether we got the number a
|
|
if a.minpoly.same_root(r, a):
|
|
return coeffs
|
|
|
|
# If none of the linear factors represented a in QQ(b), then in fact a is
|
|
# not an element of QQ(b).
|
|
return None
|
|
|
|
|
|
@public
|
|
def field_isomorphism(a, b, *, fast=True):
|
|
r"""
|
|
Find an embedding of one number field into another.
|
|
|
|
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))) # doctest: +SKIP
|
|
[3]
|
|
>>> print(field_isomorphism( I*sqrt(3), I*sqrt(3)/2)) # doctest: +SKIP
|
|
[2, 0]
|
|
|
|
Parameters
|
|
==========
|
|
|
|
a : :py:class:`~.Expr`
|
|
Any expression representing an algebraic number.
|
|
b : :py:class:`~.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$.
|
|
|
|
"""
|
|
a, b = sympify(a), sympify(b)
|
|
|
|
if not a.is_AlgebraicNumber:
|
|
a = AlgebraicNumber(a)
|
|
|
|
if not b.is_AlgebraicNumber:
|
|
b = AlgebraicNumber(b)
|
|
|
|
a = a.to_primitive_element()
|
|
b = b.to_primitive_element()
|
|
|
|
if a == b:
|
|
return a.coeffs()
|
|
|
|
n = a.minpoly.degree()
|
|
m = b.minpoly.degree()
|
|
|
|
if n == 1:
|
|
return [a.root]
|
|
|
|
if m % n != 0:
|
|
return None
|
|
|
|
if fast:
|
|
try:
|
|
result = field_isomorphism_pslq(a, b)
|
|
|
|
if result is not None:
|
|
return result
|
|
except NotImplementedError:
|
|
pass
|
|
|
|
return field_isomorphism_factor(a, b)
|
|
|
|
|
|
def _switch_domain(g, K):
|
|
# An algebraic relation f(a, b) = 0 over Q can also be written
|
|
# g(b) = 0 where g is in Q(a)[x] and h(a) = 0 where h is in Q(b)[x].
|
|
# This function transforms g into h where Q(b) = K.
|
|
frep = g.rep.inject()
|
|
hrep = frep.eject(K, front=True)
|
|
|
|
return g.new(hrep, g.gens[0])
|
|
|
|
|
|
def _linsolve(p):
|
|
# Compute root of linear polynomial.
|
|
c, d = p.rep.rep
|
|
return -d/c
|
|
|
|
|
|
@public
|
|
def primitive_element(extension, x=None, *, ex=False, polys=False):
|
|
r"""
|
|
Find a single generator for a number field given by several 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)
|
|
|
|
Parameters
|
|
==========
|
|
|
|
extension : list of :py:class:`~.Expr`
|
|
Each expression must represent an algebraic number $\alpha_i$.
|
|
x : :py:class:`~.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 :py:class:`~.Poly`.
|
|
Otherwise return it as an :py:class:`~.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.
|
|
|
|
"""
|
|
if not extension:
|
|
raise ValueError("Cannot compute primitive element for empty extension")
|
|
extension = [_sympify(ext) for ext in extension]
|
|
|
|
if x is not None:
|
|
x, cls = sympify(x), Poly
|
|
else:
|
|
x, cls = Dummy('x'), PurePoly
|
|
|
|
if not ex:
|
|
gen, coeffs = extension[0], [1]
|
|
g = minimal_polynomial(gen, x, polys=True)
|
|
for ext in extension[1:]:
|
|
if ext.is_Rational:
|
|
coeffs.append(0)
|
|
continue
|
|
_, factors = factor_list(g, extension=ext)
|
|
g = _choose_factor(factors, x, gen)
|
|
s, _, g = g.sqf_norm()
|
|
gen += s*ext
|
|
coeffs.append(s)
|
|
|
|
if not polys:
|
|
return g.as_expr(), coeffs
|
|
else:
|
|
return cls(g), coeffs
|
|
|
|
gen, coeffs = extension[0], [1]
|
|
f = minimal_polynomial(gen, x, polys=True)
|
|
K = QQ.algebraic_field((f, gen)) # incrementally constructed field
|
|
reps = [K.unit] # representations of extension elements in K
|
|
for ext in extension[1:]:
|
|
if ext.is_Rational:
|
|
coeffs.append(0) # rational ext is not included in the expression of a primitive element
|
|
reps.append(K.convert(ext)) # but it is included in reps
|
|
continue
|
|
p = minimal_polynomial(ext, x, polys=True)
|
|
L = QQ.algebraic_field((p, ext))
|
|
_, factors = factor_list(f, domain=L)
|
|
f = _choose_factor(factors, x, gen)
|
|
s, g, f = f.sqf_norm()
|
|
gen += s*ext
|
|
coeffs.append(s)
|
|
K = QQ.algebraic_field((f, gen))
|
|
h = _switch_domain(g, K)
|
|
erep = _linsolve(h.gcd(p)) # ext as element of K
|
|
ogen = K.unit - s*erep # old gen as element of K
|
|
reps = [dup_eval(_.rep, ogen, K) for _ in reps] + [erep]
|
|
|
|
if K.ext.root.is_Rational: # all extensions are rational
|
|
H = [K.convert(_).rep for _ in extension]
|
|
coeffs = [0]*len(extension)
|
|
f = cls(x, domain=QQ)
|
|
else:
|
|
H = [_.rep for _ in reps]
|
|
if not polys:
|
|
return f.as_expr(), coeffs, H
|
|
else:
|
|
return f, coeffs, H
|
|
|
|
|
|
@public
|
|
def to_number_field(extension, theta=None, *, gen=None, alias=None):
|
|
r"""
|
|
Express one algebraic number in the field generated by another.
|
|
|
|
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
|
|
:py:func:`~.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 :py:func:`~.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 :py:class:`~.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$.
|
|
|
|
Parameters
|
|
==========
|
|
|
|
extension : :py:class:`~.Expr` or list of :py:class:`~.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 : :py:class:`~.Expr`, None, optional (default=None)
|
|
If an :py:class:`~.Expr` representing an algebraic number, behavior is
|
|
as described under **Explanation**. If ``None``, then this function
|
|
reduces to a shorthand for calling :py:func:`~.primitive_element` on
|
|
``extension`` and turning the computed primitive element into an
|
|
:py:class:`~.AlgebraicNumber`.
|
|
gen : :py:class:`~.Symbol`, None, optional (default=None)
|
|
If provided, this will be used as the generator symbol for the minimal
|
|
polynomial in the returned :py:class:`~.AlgebraicNumber`.
|
|
alias : str, :py:class:`~.Symbol`, None, optional (default=None)
|
|
If provided, this will be used as the alias symbol for the returned
|
|
:py:class:`~.AlgebraicNumber`.
|
|
|
|
Returns
|
|
=======
|
|
|
|
AlgebraicNumber
|
|
Belonging to $\mathbb{Q}(\theta)$ and equaling $\eta$.
|
|
|
|
Raises
|
|
======
|
|
|
|
IsomorphismFailed
|
|
If $\eta \not\in \mathbb{Q}(\theta)$.
|
|
|
|
See Also
|
|
========
|
|
|
|
field_isomorphism
|
|
primitive_element
|
|
|
|
"""
|
|
if hasattr(extension, '__iter__'):
|
|
extension = list(extension)
|
|
else:
|
|
extension = [extension]
|
|
|
|
if len(extension) == 1 and isinstance(extension[0], tuple):
|
|
return AlgebraicNumber(extension[0], alias=alias)
|
|
|
|
minpoly, coeffs = primitive_element(extension, gen, polys=True)
|
|
root = sum([ coeff*ext for coeff, ext in zip(coeffs, extension) ])
|
|
|
|
if theta is None:
|
|
return AlgebraicNumber((minpoly, root), alias=alias)
|
|
else:
|
|
theta = sympify(theta)
|
|
|
|
if not theta.is_AlgebraicNumber:
|
|
theta = AlgebraicNumber(theta, gen=gen, alias=alias)
|
|
|
|
coeffs = field_isomorphism(root, theta)
|
|
|
|
if coeffs is not None:
|
|
return AlgebraicNumber(theta, coeffs, alias=alias)
|
|
else:
|
|
raise IsomorphismFailed(
|
|
"%s is not in a subfield of %s" % (root, theta.root))
|