Univariate polynomials over number fields¶

AUTHOR:

Luis Felipe Tabera Alonso (2014-02): initial version.

EXAMPLES:

Define a polynomial over an absolute number field and perform basic operations with them:

Sage

sage: x = polygen(ZZ, 'x')
sage: N.<a> = NumberField(x^2 - 2)
sage: K.<x> = N[]
sage: f = x - a
sage: g = x^3 - 2*a + 1
sage: f * (x + a)
x^2 - 2
sage: f + g
x^3 + x - 3*a + 1
sage: g // f
x^2 + a*x + 2
sage: g % f
1
sage: factor(x^3 - 2*a*x^2 - 2*x + 4*a)
(x - 2*a) * (x - a) * (x + a)
sage: gcd(f, x - a)
x - a

Python

>>> from sage.all import *
>>> x = polygen(ZZ, 'x')
>>> N = NumberField(x**Integer(2) - Integer(2), names=('a',)); (a,) = N._first_ngens(1)
>>> K = N['x']; (x,) = K._first_ngens(1)
>>> f = x - a
>>> g = x**Integer(3) - Integer(2)*a + Integer(1)
>>> f * (x + a)
x^2 - 2
>>> f + g
x^3 + x - 3*a + 1
>>> g // f
x^2 + a*x + 2
>>> g % f
1
>>> factor(x**Integer(3) - Integer(2)*a*x**Integer(2) - Integer(2)*x + Integer(4)*a)
(x - 2*a) * (x - a) * (x + a)
>>> gcd(f, x - a)
x - a

Sage Live

x = polygen(ZZ, 'x')
N.<a> = NumberField(x^2 - 2)
K.<x> = N[]
f = x - a
g = x^3 - 2*a + 1
f * (x + a)
f + g
g // f
g % f
factor(x^3 - 2*a*x^2 - 2*x + 4*a)
gcd(f, x - a)

Polynomials are aware of embeddings of the underlying field:

Sage

sage: # needs sage.rings.padics
sage: x = polygen(ZZ, 'x')
sage: Q7 = Qp(7)
sage: r1 = Q7(3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8
....:          + 6*7^9 + 6*7^10 + 2*7^11 + 7^12 + 7^13 + 2*7^15 + 7^16 + 7^17
....:          + 4*7^18 + 6*7^19)
sage: N.<b> = NumberField(x^2 - 2, embedding=r1)
sage: K.<t> = N[]
sage: f = t^3 - 2*t + 1
sage: f(r1)
1 + O(7^20)

Python

>>> from sage.all import *
>>> # needs sage.rings.padics
>>> x = polygen(ZZ, 'x')
>>> Q7 = Qp(Integer(7))
>>> r1 = Q7(Integer(3) + Integer(7) + Integer(2)*Integer(7)**Integer(2) + Integer(6)*Integer(7)**Integer(3) + Integer(7)**Integer(4) + Integer(2)*Integer(7)**Integer(5) + Integer(7)**Integer(6) + Integer(2)*Integer(7)**Integer(7) + Integer(4)*Integer(7)**Integer(8)
...          + Integer(6)*Integer(7)**Integer(9) + Integer(6)*Integer(7)**Integer(10) + Integer(2)*Integer(7)**Integer(11) + Integer(7)**Integer(12) + Integer(7)**Integer(13) + Integer(2)*Integer(7)**Integer(15) + Integer(7)**Integer(16) + Integer(7)**Integer(17)
...          + Integer(4)*Integer(7)**Integer(18) + Integer(6)*Integer(7)**Integer(19))
>>> N = NumberField(x**Integer(2) - Integer(2), embedding=r1, names=('b',)); (b,) = N._first_ngens(1)
>>> K = N['t']; (t,) = K._first_ngens(1)
>>> f = t**Integer(3) - Integer(2)*t + Integer(1)
>>> f(r1)
1 + O(7^20)

Sage Live

# needs sage.rings.padics
x = polygen(ZZ, 'x')
Q7 = Qp(7)
r1 = Q7(3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8
         + 6*7^9 + 6*7^10 + 2*7^11 + 7^12 + 7^13 + 2*7^15 + 7^16 + 7^17
         + 4*7^18 + 6*7^19)
N.<b> = NumberField(x^2 - 2, embedding=r1)
K.<t> = N[]
f = t^3 - 2*t + 1
f(r1)

We can also construct polynomials over relative number fields:

Sage

sage: # needs sage.symbolic
sage: N.<i, s2> = QQ[I, sqrt(2)]
sage: K.<x> = N[]
sage: f = x - s2
sage: g = x^3 - 2*i*x^2 + s2*x
sage: f * (x + s2)
x^2 - 2
sage: f + g
x^3 - 2*I*x^2 + (sqrt2 + 1)*x - sqrt2
sage: g // f
x^2 + (-2*I + sqrt2)*x - 2*sqrt2*I + sqrt2 + 2
sage: g % f
-4*I + 2*sqrt2 + 2
sage: factor(i*x^4 - 2*i*x^2 + 9*i)
(I) * (x - I + sqrt2) * (x + I - sqrt2) * (x - I - sqrt2) * (x + I + sqrt2)
sage: gcd(f, x - i)
1

Python

>>> from sage.all import *
>>> # needs sage.symbolic
>>> N = QQ[I, sqrt(Integer(2))]; (i, s2,) = N._first_ngens(2)
>>> K = N['x']; (x,) = K._first_ngens(1)
>>> f = x - s2
>>> g = x**Integer(3) - Integer(2)*i*x**Integer(2) + s2*x
>>> f * (x + s2)
x^2 - 2
>>> f + g
x^3 - 2*I*x^2 + (sqrt2 + 1)*x - sqrt2
>>> g // f
x^2 + (-2*I + sqrt2)*x - 2*sqrt2*I + sqrt2 + 2
>>> g % f
-4*I + 2*sqrt2 + 2
>>> factor(i*x**Integer(4) - Integer(2)*i*x**Integer(2) + Integer(9)*i)
(I) * (x - I + sqrt2) * (x + I - sqrt2) * (x - I - sqrt2) * (x + I + sqrt2)
>>> gcd(f, x - i)
1

Sage Live

# needs sage.symbolic
N.<i, s2> = QQ[I, sqrt(2)]
K.<x> = N[]
f = x - s2
g = x^3 - 2*i*x^2 + s2*x
f * (x + s2)
f + g
g // f
g % f
factor(i*x^4 - 2*i*x^2 + 9*i)
gcd(f, x - i)

class sage.rings.polynomial.polynomial_number_field.Polynomial_absolute_number_field_dense(parent, x=None, check=True, is_gen=False, construct=False)[source]¶

Bases: Polynomial_generic_dense_field

Class of dense univariate polynomials over an absolute number field.

gcd(other)[source]¶

Compute the monic gcd of two univariate polynomials using PARI.

INPUT:

other – a polynomial with the same parent as self

OUTPUT: the monic gcd of self and other

EXAMPLES:

Sage

sage: x = polygen(ZZ, 'x')
sage: N.<a> = NumberField(x^3 - 1/2, 'a')
sage: R.<r> = N['r']
sage: f = (5/4*a^2 - 2*a + 4)*r^2 + (5*a^2 - 81/5*a - 17/2)*r + 4/5*a^2 + 24*a + 6
sage: g = (5/4*a^2 - 2*a + 4)*r^2 + (-11*a^2 + 79/5*a - 7/2)*r - 4/5*a^2 - 24*a - 6
sage: gcd(f, g**2)
r - 60808/96625*a^2 - 69936/96625*a - 149212/96625
sage: R = QQ[I]['x']
sage: f = R.random_element(2)
sage: g = f + 1
sage: h = R.random_element(2).monic()
sage: f *= h
sage: g *= h
sage: gcd(f, g) - h
0
sage: f.gcd(g) - h
0

Python

>>> from sage.all import *
>>> x = polygen(ZZ, 'x')
>>> N = NumberField(x**Integer(3) - Integer(1)/Integer(2), 'a', names=('a',)); (a,) = N._first_ngens(1)
>>> R = N['r']; (r,) = R._first_ngens(1)
>>> f = (Integer(5)/Integer(4)*a**Integer(2) - Integer(2)*a + Integer(4))*r**Integer(2) + (Integer(5)*a**Integer(2) - Integer(81)/Integer(5)*a - Integer(17)/Integer(2))*r + Integer(4)/Integer(5)*a**Integer(2) + Integer(24)*a + Integer(6)
>>> g = (Integer(5)/Integer(4)*a**Integer(2) - Integer(2)*a + Integer(4))*r**Integer(2) + (-Integer(11)*a**Integer(2) + Integer(79)/Integer(5)*a - Integer(7)/Integer(2))*r - Integer(4)/Integer(5)*a**Integer(2) - Integer(24)*a - Integer(6)
>>> gcd(f, g**Integer(2))
r - 60808/96625*a^2 - 69936/96625*a - 149212/96625
>>> R = QQ[I]['x']
>>> f = R.random_element(Integer(2))
>>> g = f + Integer(1)
>>> h = R.random_element(Integer(2)).monic()
>>> f *= h
>>> g *= h
>>> gcd(f, g) - h
0
>>> f.gcd(g) - h
0

Sage Live

x = polygen(ZZ, 'x')
N.<a> = NumberField(x^3 - 1/2, 'a')
R.<r> = N['r']
f = (5/4*a^2 - 2*a + 4)*r^2 + (5*a^2 - 81/5*a - 17/2)*r + 4/5*a^2 + 24*a + 6
g = (5/4*a^2 - 2*a + 4)*r^2 + (-11*a^2 + 79/5*a - 7/2)*r - 4/5*a^2 - 24*a - 6
gcd(f, g**2)
R = QQ[I]['x']
f = R.random_element(2)
g = f + 1
h = R.random_element(2).monic()
f *= h
g *= h
gcd(f, g) - h
f.gcd(g) - h

class sage.rings.polynomial.polynomial_number_field.Polynomial_relative_number_field_dense(parent, x=None, check=True, is_gen=False, construct=False)[source]¶

Bases: Polynomial_generic_dense_field

Class of dense univariate polynomials over a relative number field.

gcd(other)[source]¶

Compute the monic gcd of two polynomials.

Currently, the method checks corner cases in which one of the polynomials is zero or a constant. Then, computes an absolute extension and performs the computations there.

INPUT:

other – a polynomial with the same parent as self

OUTPUT: the monic gcd of self and other

See Polynomial_absolute_number_field_dense.gcd() for more details.

EXAMPLES:

Sage

sage: # needs sage.symbolic
sage: N = QQ[sqrt(2), sqrt(3)]
sage: s2, s3 = N.gens()
sage: x = polygen(N)
sage: f = x^4 - 5*x^2 + 6
sage: g = x^3 + (-2*s2 + s3)*x^2 + (-2*s3*s2 + 2)*x + 2*s3
sage: gcd(f, g)
x^2 + (-sqrt2 + sqrt3)*x - sqrt3*sqrt2
sage: f.gcd(g)
x^2 + (-sqrt2 + sqrt3)*x - sqrt3*sqrt2

Python

>>> from sage.all import *
>>> # needs sage.symbolic
>>> N = QQ[sqrt(Integer(2)), sqrt(Integer(3))]
>>> s2, s3 = N.gens()
>>> x = polygen(N)
>>> f = x**Integer(4) - Integer(5)*x**Integer(2) + Integer(6)
>>> g = x**Integer(3) + (-Integer(2)*s2 + s3)*x**Integer(2) + (-Integer(2)*s3*s2 + Integer(2))*x + Integer(2)*s3
>>> gcd(f, g)
x^2 + (-sqrt2 + sqrt3)*x - sqrt3*sqrt2
>>> f.gcd(g)
x^2 + (-sqrt2 + sqrt3)*x - sqrt3*sqrt2

Sage Live

# needs sage.symbolic
N = QQ[sqrt(2), sqrt(3)]
s2, s3 = N.gens()
x = polygen(N)
f = x^4 - 5*x^2 + 6
g = x^3 + (-2*s2 + s3)*x^2 + (-2*s3*s2 + 2)*x + 2*s3
gcd(f, g)
f.gcd(g)