Univariate polynomials over \(\QQ\) implemented via FLINT

AUTHOR:

• Sebastian Pancratz

class sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint

Bases: Polynomial

Univariate polynomials over the rationals, implemented via FLINT.

Internally, we represent rational polynomial as the quotient of an integer polynomial and a positive denominator which is coprime to the content of the numerator.

_add_(right)

Return the sum of two rational polynomials.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = 2/3 + t + 2*t^3
sage: g = -1 + t/3 - 10/11*t^4
sage: f + g
-10/11*t^4 + 2*t^3 + 4/3*t - 1/3

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(2)/Integer(3) + t + Integer(2)*t**Integer(3)
>>> g = -Integer(1) + t/Integer(3) - Integer(10)/Integer(11)*t**Integer(4)
>>> f + g
-10/11*t^4 + 2*t^3 + 4/3*t - 1/3

Sage Live

R.<t> = QQ[]
f = 2/3 + t + 2*t^3
g = -1 + t/3 - 10/11*t^4
f + g

_sub_(right)

Return the difference of two rational polynomials.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = -10/11*t^4 + 2*t^3 + 4/3*t - 1/3
sage: g = 2*t^3
sage: f - g                                 # indirect doctest
-10/11*t^4 + 4/3*t - 1/3

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = -Integer(10)/Integer(11)*t**Integer(4) + Integer(2)*t**Integer(3) + Integer(4)/Integer(3)*t - Integer(1)/Integer(3)
>>> g = Integer(2)*t**Integer(3)
>>> f - g                                 # indirect doctest
-10/11*t^4 + 4/3*t - 1/3

Sage Live

R.<t> = QQ[]
f = -10/11*t^4 + 2*t^3 + 4/3*t - 1/3
g = 2*t^3
f - g                                 # indirect doctest

_lmul_(right)

Return self * right, where right is a rational number.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = 3/2*t^3 - t + 1/3
sage: f * 6                   # indirect doctest
9*t^3 - 6*t + 2

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(3)/Integer(2)*t**Integer(3) - t + Integer(1)/Integer(3)
>>> f * Integer(6)                   # indirect doctest
9*t^3 - 6*t + 2

Sage Live

R.<t> = QQ[]
f = 3/2*t^3 - t + 1/3
f * 6                   # indirect doctest

_rmul_(left)

Return left * self, where left is a rational number.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = 3/2*t^3 - t + 1/3
sage: 6 * f                  # indirect doctest
9*t^3 - 6*t + 2

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(3)/Integer(2)*t**Integer(3) - t + Integer(1)/Integer(3)
>>> Integer(6) * f                  # indirect doctest
9*t^3 - 6*t + 2

Sage Live

R.<t> = QQ[]
f = 3/2*t^3 - t + 1/3
6 * f                  # indirect doctest

_mul_(right)

Return the product of self and right.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = -1 + 3*t/2 - t^3
sage: g = 2/3 + 7/3*t + 3*t^2
sage: f * g                           # indirect doctest
-3*t^5 - 7/3*t^4 + 23/6*t^3 + 1/2*t^2 - 4/3*t - 2/3

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = -Integer(1) + Integer(3)*t/Integer(2) - t**Integer(3)
>>> g = Integer(2)/Integer(3) + Integer(7)/Integer(3)*t + Integer(3)*t**Integer(2)
>>> f * g                           # indirect doctest
-3*t^5 - 7/3*t^4 + 23/6*t^3 + 1/2*t^2 - 4/3*t - 2/3

Sage Live

R.<t> = QQ[]
f = -1 + 3*t/2 - t^3
g = 2/3 + 7/3*t + 3*t^2
f * g                           # indirect doctest

_mul_trunc_(right, n)

Truncated multiplication.

EXAMPLES:

Sage

sage: x = polygen(QQ)
sage: p1 = 1/2 - 3*x + 2/7*x**3
sage: p2 = x + 2/5*x**5 + x**7
sage: p1._mul_trunc_(p2, 5)
2/7*x^4 - 3*x^2 + 1/2*x
sage: (p1*p2).truncate(5)
2/7*x^4 - 3*x^2 + 1/2*x

sage: p1._mul_trunc_(p2, 1)
0
sage: p1._mul_trunc_(p2, 0)
Traceback (most recent call last):
...
ValueError: n must be > 0

Python

>>> from sage.all import *
>>> x = polygen(QQ)
>>> p1 = Integer(1)/Integer(2) - Integer(3)*x + Integer(2)/Integer(7)*x**Integer(3)
>>> p2 = x + Integer(2)/Integer(5)*x**Integer(5) + x**Integer(7)
>>> p1._mul_trunc_(p2, Integer(5))
2/7*x^4 - 3*x^2 + 1/2*x
>>> (p1*p2).truncate(Integer(5))
2/7*x^4 - 3*x^2 + 1/2*x

>>> p1._mul_trunc_(p2, Integer(1))
0
>>> p1._mul_trunc_(p2, Integer(0))
Traceback (most recent call last):
...
ValueError: n must be > 0

Sage Live

x = polygen(QQ)
p1 = 1/2 - 3*x + 2/7*x**3
p2 = x + 2/5*x**5 + x**7
p1._mul_trunc_(p2, 5)
(p1*p2).truncate(5)
p1._mul_trunc_(p2, 1)
p1._mul_trunc_(p2, 0)

ALGORITHM:

Call the FLINT method fmpq_poly_mullow.

degree()

Return the degree of self.

By convention, the degree of the zero polynomial is \(-1\).

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = 1 + t + t^2/2 + t^3/3 + t^4/4
sage: f.degree()
4
sage: g = R(0)
sage: g.degree()
-1

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(1) + t + t**Integer(2)/Integer(2) + t**Integer(3)/Integer(3) + t**Integer(4)/Integer(4)
>>> f.degree()
4
>>> g = R(Integer(0))
>>> g.degree()
-1

Sage Live

R.<t> = QQ[]
f = 1 + t + t^2/2 + t^3/3 + t^4/4
f.degree()
g = R(0)
g.degree()

denominator()

Return the denominator of self.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = (3 * t^3 + 1) / -3
sage: f.denominator()
3

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = (Integer(3) * t**Integer(3) + Integer(1)) / -Integer(3)
>>> f.denominator()
3

Sage Live

R.<t> = QQ[]
f = (3 * t^3 + 1) / -3
f.denominator()

disc()

Return the discriminant of this polynomial.

The discriminant \(R_n\) is defined as

\[R_n = a_n^{2 n-2} \prod_{1 \le i < j \le n} (r_i - r_j)^2,\]

where \(n\) is the degree of this polynomial, \(a_n\) is the leading coefficient and the roots over \(\QQbar\) are \(r_1, \ldots, r_n\).

The discriminant of constant polynomials is defined to be 0.

OUTPUT: discriminant, an element of the base ring of the polynomial ring

Note

Note the identity \(R_n(f) := (-1)^{(n (n-1)/2)} R(f,f') a_n^{(n-k-2)}\), where \(n\) is the degree of this polynomial, \(a_n\) is the leading coefficient, \(f'\) is the derivative of \(f\), and \(k\) is the degree of \(f'\). Calls resultant().

ALGORITHM:

Use PARI.

EXAMPLES:

In the case of elliptic curves in special form, the discriminant is easy to calculate:

Sage

sage: R.<t> = QQ[]
sage: f = t^3 + t + 1
sage: d = f.discriminant(); d
-31
sage: d.parent() is QQ
True
sage: EllipticCurve([1, 1]).discriminant() / 16                             # needs sage.schemes
-31

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = t**Integer(3) + t + Integer(1)
>>> d = f.discriminant(); d
-31
>>> d.parent() is QQ
True
>>> EllipticCurve([Integer(1), Integer(1)]).discriminant() / Integer(16)                             # needs sage.schemes
-31

Sage Live

R.<t> = QQ[]
f = t^3 + t + 1
d = f.discriminant(); d
d.parent() is QQ
EllipticCurve([1, 1]).discriminant() / 16                             # needs sage.schemes

Sage

sage: R.<t> = QQ[]
sage: f = 2*t^3 + t + 1
sage: d = f.discriminant(); d
-116

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(2)*t**Integer(3) + t + Integer(1)
>>> d = f.discriminant(); d
-116

Sage Live

R.<t> = QQ[]
f = 2*t^3 + t + 1
d = f.discriminant(); d

Sage

sage: R.<t> = QQ[]
sage: f = t^3 + 3*t - 17
sage: f.discriminant()
-7911

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = t**Integer(3) + Integer(3)*t - Integer(17)
>>> f.discriminant()
-7911

Sage Live

R.<t> = QQ[]
f = t^3 + 3*t - 17
f.discriminant()

discriminant()

Return the discriminant of this polynomial.

The discriminant \(R_n\) is defined as

\[R_n = a_n^{2 n-2} \prod_{1 \le i < j \le n} (r_i - r_j)^2,\]

where \(n\) is the degree of this polynomial, \(a_n\) is the leading coefficient and the roots over \(\QQbar\) are \(r_1, \ldots, r_n\).

The discriminant of constant polynomials is defined to be 0.

OUTPUT: discriminant, an element of the base ring of the polynomial ring

Note

Note the identity \(R_n(f) := (-1)^{(n (n-1)/2)} R(f,f') a_n^{(n-k-2)}\), where \(n\) is the degree of this polynomial, \(a_n\) is the leading coefficient, \(f'\) is the derivative of \(f\), and \(k\) is the degree of \(f'\). Calls resultant().

ALGORITHM:

Use PARI.

EXAMPLES:

In the case of elliptic curves in special form, the discriminant is easy to calculate:

Sage

sage: R.<t> = QQ[]
sage: f = t^3 + t + 1
sage: d = f.discriminant(); d
-31
sage: d.parent() is QQ
True
sage: EllipticCurve([1, 1]).discriminant() / 16                             # needs sage.schemes
-31

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = t**Integer(3) + t + Integer(1)
>>> d = f.discriminant(); d
-31
>>> d.parent() is QQ
True
>>> EllipticCurve([Integer(1), Integer(1)]).discriminant() / Integer(16)                             # needs sage.schemes
-31

Sage Live

R.<t> = QQ[]
f = t^3 + t + 1
d = f.discriminant(); d
d.parent() is QQ
EllipticCurve([1, 1]).discriminant() / 16                             # needs sage.schemes

Sage

sage: R.<t> = QQ[]
sage: f = 2*t^3 + t + 1
sage: d = f.discriminant(); d
-116

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(2)*t**Integer(3) + t + Integer(1)
>>> d = f.discriminant(); d
-116

Sage Live

R.<t> = QQ[]
f = 2*t^3 + t + 1
d = f.discriminant(); d

Sage

sage: R.<t> = QQ[]
sage: f = t^3 + 3*t - 17
sage: f.discriminant()
-7911

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = t**Integer(3) + Integer(3)*t - Integer(17)
>>> f.discriminant()
-7911

Sage Live

R.<t> = QQ[]
f = t^3 + 3*t - 17
f.discriminant()

factor_mod(p)

Return the factorization of self modulo the prime \(p\).

Assumes that the degree of this polynomial is at least one, and raises a ValueError otherwise.

INPUT:

• p – prime number

OUTPUT: factorization of this polynomial modulo \(p\)

EXAMPLES:

Sage

sage: R.<x> = QQ[]
sage: (x^5 + 17*x^3 + x + 3).factor_mod(3)
x * (x^2 + 1)^2
sage: (x^5 + 2).factor_mod(5)
(x + 2)^5

Python

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> (x**Integer(5) + Integer(17)*x**Integer(3) + x + Integer(3)).factor_mod(Integer(3))
x * (x^2 + 1)^2
>>> (x**Integer(5) + Integer(2)).factor_mod(Integer(5))
(x + 2)^5

Sage Live

R.<x> = QQ[]
(x^5 + 17*x^3 + x + 3).factor_mod(3)
(x^5 + 2).factor_mod(5)

Variable names that are reserved in PARI, such as zeta, are supported (see Issue #20631):

Sage

sage: R.<zeta> = QQ[]
sage: (zeta^2 + zeta + 1).factor_mod(7)
(zeta + 3) * (zeta + 5)

Python

>>> from sage.all import *
>>> R = QQ['zeta']; (zeta,) = R._first_ngens(1)
>>> (zeta**Integer(2) + zeta + Integer(1)).factor_mod(Integer(7))
(zeta + 3) * (zeta + 5)

Sage Live

R.<zeta> = QQ[]
(zeta^2 + zeta + 1).factor_mod(7)

factor_padic(p, prec=10)

Return the \(p\)-adic factorization of this polynomial to the given precision.

INPUT:

• p – prime number

• prec – integer; the precision

OUTPUT: factorization of self viewed as a \(p\)-adic polynomial

EXAMPLES:

Sage

sage: # needs sage.rings.padic
sage: R.<x> = QQ[]
sage: f = x^3 - 2
sage: f.factor_padic(2)
(1 + O(2^10))*x^3 + O(2^10)*x^2 + O(2^10)*x
+ 2 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + 2^9 + O(2^10)
sage: f.factor_padic(3)
(1 + O(3^10))*x^3 + O(3^10)*x^2 + O(3^10)*x
+ 1 + 2*3 + 2*3^2 + 2*3^3 + 2*3^4 + 2*3^5 + 2*3^6 + 2*3^7 + 2*3^8 + 2*3^9 + O(3^10)
sage: f.factor_padic(5)
((1 + O(5^10))*x
 + 2 + 4*5 + 2*5^2 + 2*5^3 + 5^4 + 3*5^5 + 4*5^7 + 2*5^8 + 5^9 + O(5^10))
* ((1 + O(5^10))*x^2
   + (3 + 2*5^2 + 2*5^3 + 3*5^4 + 5^5 + 4*5^6 + 2*5^8 + 3*5^9 + O(5^10))*x
   + 4 + 5 + 2*5^2 + 4*5^3 + 4*5^4 + 3*5^5 + 3*5^6 + 4*5^7 + 4*5^9 + O(5^10))

Python

>>> from sage.all import *
>>> # needs sage.rings.padic
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(3) - Integer(2)
>>> f.factor_padic(Integer(2))
(1 + O(2^10))*x^3 + O(2^10)*x^2 + O(2^10)*x
+ 2 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + 2^9 + O(2^10)
>>> f.factor_padic(Integer(3))
(1 + O(3^10))*x^3 + O(3^10)*x^2 + O(3^10)*x
+ 1 + 2*3 + 2*3^2 + 2*3^3 + 2*3^4 + 2*3^5 + 2*3^6 + 2*3^7 + 2*3^8 + 2*3^9 + O(3^10)
>>> f.factor_padic(Integer(5))
((1 + O(5^10))*x
 + 2 + 4*5 + 2*5^2 + 2*5^3 + 5^4 + 3*5^5 + 4*5^7 + 2*5^8 + 5^9 + O(5^10))
* ((1 + O(5^10))*x^2
   + (3 + 2*5^2 + 2*5^3 + 3*5^4 + 5^5 + 4*5^6 + 2*5^8 + 3*5^9 + O(5^10))*x
   + 4 + 5 + 2*5^2 + 4*5^3 + 4*5^4 + 3*5^5 + 3*5^6 + 4*5^7 + 4*5^9 + O(5^10))

Sage Live

# needs sage.rings.padic
R.<x> = QQ[]
f = x^3 - 2
f.factor_padic(2)
f.factor_padic(3)
f.factor_padic(5)

The input polynomial is considered to have “infinite” precision, therefore the \(p\)-adic factorization of the polynomial is not the same as first coercing to \(\QQ_p\) and then factoring (see also Issue #15422):

Sage

sage: # needs sage.rings.padic
sage: f = x^2 - 3^6
sage: f.factor_padic(3, 5)
((1 + O(3^5))*x + 3^3 + O(3^5)) * ((1 + O(3^5))*x + 2*3^3 + 2*3^4 + O(3^5))
sage: f.change_ring(Qp(3,5)).factor()
Traceback (most recent call last):
...
PrecisionError: p-adic factorization not well-defined since
the discriminant is zero up to the requestion p-adic precision

Python

>>> from sage.all import *
>>> # needs sage.rings.padic
>>> f = x**Integer(2) - Integer(3)**Integer(6)
>>> f.factor_padic(Integer(3), Integer(5))
((1 + O(3^5))*x + 3^3 + O(3^5)) * ((1 + O(3^5))*x + 2*3^3 + 2*3^4 + O(3^5))
>>> f.change_ring(Qp(Integer(3),Integer(5))).factor()
Traceback (most recent call last):
...
PrecisionError: p-adic factorization not well-defined since
the discriminant is zero up to the requestion p-adic precision

Sage Live

# needs sage.rings.padic
f = x^2 - 3^6
f.factor_padic(3, 5)
f.change_ring(Qp(3,5)).factor()

A more difficult example:

Sage

sage: R.<x> = QQ[]
sage: f = 100 * (5*x + 1)^2 * (x + 5)^2
sage: f.factor_padic(5, 10)                                                 # needs sage.rings.padic
(4*5^4 + O(5^14)) * ((1 + O(5^9))*x + 5^-1 + O(5^9))^2
* ((1 + O(5^10))*x + 5 + O(5^10))^2

Python

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(100) * (Integer(5)*x + Integer(1))**Integer(2) * (x + Integer(5))**Integer(2)
>>> f.factor_padic(Integer(5), Integer(10))                                                 # needs sage.rings.padic
(4*5^4 + O(5^14)) * ((1 + O(5^9))*x + 5^-1 + O(5^9))^2
* ((1 + O(5^10))*x + 5 + O(5^10))^2

Sage Live

R.<x> = QQ[]
f = 100 * (5*x + 1)^2 * (x + 5)^2
f.factor_padic(5, 10)                                                 # needs sage.rings.padic

Try some bogus inputs:

Sage

sage: # needs sage.rings.padic
sage: f.factor_padic(3, -1)
Traceback (most recent call last):
...
ValueError: prec_cap must be nonnegative
sage: f.factor_padic(6, 10)
Traceback (most recent call last):
...
ValueError: p must be prime
sage: f.factor_padic('hello', 'world')
Traceback (most recent call last):
...
TypeError: unable to convert 'hello' to an integer

Python

>>> from sage.all import *
>>> # needs sage.rings.padic
>>> f.factor_padic(Integer(3), -Integer(1))
Traceback (most recent call last):
...
ValueError: prec_cap must be nonnegative
>>> f.factor_padic(Integer(6), Integer(10))
Traceback (most recent call last):
...
ValueError: p must be prime
>>> f.factor_padic('hello', 'world')
Traceback (most recent call last):
...
TypeError: unable to convert 'hello' to an integer

Sage Live

# needs sage.rings.padic
f.factor_padic(3, -1)
f.factor_padic(6, 10)
f.factor_padic('hello', 'world')

galois_group(pari_group=False, algorithm='pari')

Return the Galois group of this polynomial as a permutation group.

INPUT:

• self – irreducible polynomial

• pari_group – boolean (default: False); if True instead return the Galois group as a PARI group. This has a useful label in it, and may be slightly faster since it doesn’t require looking up a group in GAP. To get a permutation group from a PARI group P, type PermutationGroup(P).

• algorithm – 'pari', 'gap', 'kash', 'magma' (default: 'pari', for degrees is at most 11; 'gap', for degrees from 12 to 15; 'kash', for degrees from 16 or more).

OUTPUT: Galois group

ALGORITHM:

The Galois group is computed using PARI in C library mode, or possibly GAP, KASH, or MAGMA.

Note

The PARI documentation contains the following warning: The method used is that of resolvent polynomials and is sensitive to the current precision. The precision is updated internally but, in very rare cases, a wrong result may be returned if the initial precision was not sufficient.

GAP uses the “Transitive Groups Libraries” from the “TransGrp” GAP package which comes installed with the “gap” Sage package.

MAGMA does not return a provably correct result. Please see the MAGMA documentation for how to obtain a provably correct result.

EXAMPLES:

Sage

sage: # needs sage.groups sage.libs.pari
sage: R.<x> = QQ[]
sage: f = x^4 - 17*x^3 - 2*x + 1
sage: G = f.galois_group(); G
Transitive group number 5 of degree 4
sage: G.gens()
((1,2,3,4), (1,2))
sage: G.order()
24

Python

>>> from sage.all import *
>>> # needs sage.groups sage.libs.pari
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(4) - Integer(17)*x**Integer(3) - Integer(2)*x + Integer(1)
>>> G = f.galois_group(); G
Transitive group number 5 of degree 4
>>> G.gens()
((1,2,3,4), (1,2))
>>> G.order()
24

Sage Live

# needs sage.groups sage.libs.pari
R.<x> = QQ[]
f = x^4 - 17*x^3 - 2*x + 1
G = f.galois_group(); G
G.gens()
G.order()

It is potentially useful to instead obtain the corresponding PARI group, which is little more than a 4-tuple. See the PARI manual for the exact details. (Note that the third entry in the tuple is in the new standard ordering.)

Sage

sage: # needs sage.groups sage.libs.pari
sage: f = x^4 - 17*x^3 - 2*x + 1
sage: G = f.galois_group(pari_group=True); G
PARI group [24, -1, 5, "S4"] of degree 4
sage: PermutationGroup(G)
Transitive group number 5 of degree 4

Python

>>> from sage.all import *
>>> # needs sage.groups sage.libs.pari
>>> f = x**Integer(4) - Integer(17)*x**Integer(3) - Integer(2)*x + Integer(1)
>>> G = f.galois_group(pari_group=True); G
PARI group [24, -1, 5, "S4"] of degree 4
>>> PermutationGroup(G)
Transitive group number 5 of degree 4

Sage Live

# needs sage.groups sage.libs.pari
f = x^4 - 17*x^3 - 2*x + 1
G = f.galois_group(pari_group=True); G
PermutationGroup(G)

You can use KASH or GAP to compute Galois groups as well. The advantage is that KASH (resp. GAP) can compute Galois groups of fields up to degree 23 (resp. 15), whereas PARI only goes to degree 11. (In my not-so-thorough experiments PARI is faster than KASH.)

Sage

sage: R.<x> = QQ[]
sage: f = x^4 - 17*x^3 - 2*x + 1
sage: f.galois_group(algorithm='kash')   # optional - kash
Transitive group number 5 of degree 4

sage: # needs sage.libs.gap
sage: f = x^4 - 17*x^3 - 2*x + 1
sage: f.galois_group(algorithm='gap')
Transitive group number 5 of degree 4
sage: f = x^13 - 17*x^3 - 2*x + 1
sage: f.galois_group(algorithm='gap')
Transitive group number 9 of degree 13
sage: f = x^12 - 2*x^8 - x^7 + 2*x^6 + 4*x^4 - 2*x^3 - x^2 - x + 1
sage: f.galois_group(algorithm='gap')
Transitive group number 183 of degree 12

sage: f.galois_group(algorithm='magma')  # optional - magma
Transitive group number 5 of degree 4

Python

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(4) - Integer(17)*x**Integer(3) - Integer(2)*x + Integer(1)
>>> f.galois_group(algorithm='kash')   # optional - kash
Transitive group number 5 of degree 4

>>> # needs sage.libs.gap
>>> f = x**Integer(4) - Integer(17)*x**Integer(3) - Integer(2)*x + Integer(1)
>>> f.galois_group(algorithm='gap')
Transitive group number 5 of degree 4
>>> f = x**Integer(13) - Integer(17)*x**Integer(3) - Integer(2)*x + Integer(1)
>>> f.galois_group(algorithm='gap')
Transitive group number 9 of degree 13
>>> f = x**Integer(12) - Integer(2)*x**Integer(8) - x**Integer(7) + Integer(2)*x**Integer(6) + Integer(4)*x**Integer(4) - Integer(2)*x**Integer(3) - x**Integer(2) - x + Integer(1)
>>> f.galois_group(algorithm='gap')
Transitive group number 183 of degree 12

>>> f.galois_group(algorithm='magma')  # optional - magma
Transitive group number 5 of degree 4

Sage Live

R.<x> = QQ[]
f = x^4 - 17*x^3 - 2*x + 1
f.galois_group(algorithm='kash')   # optional - kash
# needs sage.libs.gap
f = x^4 - 17*x^3 - 2*x + 1
f.galois_group(algorithm='gap')
f = x^13 - 17*x^3 - 2*x + 1
f.galois_group(algorithm='gap')
f = x^12 - 2*x^8 - x^7 + 2*x^6 + 4*x^4 - 2*x^3 - x^2 - x + 1
f.galois_group(algorithm='gap')
f.galois_group(algorithm='magma')  # optional - magma

galois_group_davenport_smith_test(num_trials=50, assume_irreducible=False)

Use the Davenport-Smith test to attempt to certify that \(f\) has Galois group \(A_n\) or \(S_n\).

Return 1 if the Galois group is certified as \(S_n\), 2 if \(A_n\), or 0 if no conclusion is reached.

By default, we first check that \(f\) is irreducible. For extra efficiency, one can override this by specifying assume_irreducible=True; this yields undefined results if \(f\) is not irreducible.

A corresponding function in Magma is IsEasySnAn.

EXAMPLES:

Sage

sage: P.<x> = QQ[]
sage: u = x^7 + x + 1
sage: u.galois_group_davenport_smith_test()
1
sage: u = x^7 - x^4 - x^3 + 3*x^2 - 1
sage: u.galois_group_davenport_smith_test()
2
sage: u = x^7 - 2
sage: u.galois_group_davenport_smith_test()
0

Python

>>> from sage.all import *
>>> P = QQ['x']; (x,) = P._first_ngens(1)
>>> u = x**Integer(7) + x + Integer(1)
>>> u.galois_group_davenport_smith_test()
1
>>> u = x**Integer(7) - x**Integer(4) - x**Integer(3) + Integer(3)*x**Integer(2) - Integer(1)
>>> u.galois_group_davenport_smith_test()
2
>>> u = x**Integer(7) - Integer(2)
>>> u.galois_group_davenport_smith_test()
0

Sage Live

P.<x> = QQ[]
u = x^7 + x + 1
u.galois_group_davenport_smith_test()
u = x^7 - x^4 - x^3 + 3*x^2 - 1
u.galois_group_davenport_smith_test()
u = x^7 - 2
u.galois_group_davenport_smith_test()

gcd(right)

Return the (monic) greatest common divisor of self and right.

Corner cases: if self and right are both zero, returns zero. If only one of them is zero, returns the other polynomial, up to normalisation.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = -2 + 3*t/2 + 4*t^2/7 - t^3
sage: g = 1/2 + 4*t + 2*t^4/3
sage: f.gcd(g)
1
sage: f = (-3*t + 1/2) * f
sage: g = (-3*t + 1/2) * (4*t^2/3 - 1) * g
sage: f.gcd(g)
t - 1/6

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = -Integer(2) + Integer(3)*t/Integer(2) + Integer(4)*t**Integer(2)/Integer(7) - t**Integer(3)
>>> g = Integer(1)/Integer(2) + Integer(4)*t + Integer(2)*t**Integer(4)/Integer(3)
>>> f.gcd(g)
1
>>> f = (-Integer(3)*t + Integer(1)/Integer(2)) * f
>>> g = (-Integer(3)*t + Integer(1)/Integer(2)) * (Integer(4)*t**Integer(2)/Integer(3) - Integer(1)) * g
>>> f.gcd(g)
t - 1/6

Sage Live

R.<t> = QQ[]
f = -2 + 3*t/2 + 4*t^2/7 - t^3
g = 1/2 + 4*t + 2*t^4/3
f.gcd(g)
f = (-3*t + 1/2) * f
g = (-3*t + 1/2) * (4*t^2/3 - 1) * g
f.gcd(g)

hensel_lift(p, e)

Assuming that this polynomial factors modulo \(p\) into distinct monic factors, computes the Hensel lifts of these factors modulo \(p^e\). We assume that self has integer coefficients.

Return an empty list if this polynomial has degree less than one.

INPUT:

• p – prime number; coerceable to Integer

• e – exponent; coerceable to Integer

OUTPUT: Hensel lifts; list of polynomials over \(\ZZ / p^e \ZZ\)

EXAMPLES:

Sage

sage: R.<x> = QQ[]
sage: R((x-1)*(x+1)).hensel_lift(7, 2)
[x + 1, x + 48]

Python

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> R((x-Integer(1))*(x+Integer(1))).hensel_lift(Integer(7), Integer(2))
[x + 1, x + 48]

Sage Live

R.<x> = QQ[]
R((x-1)*(x+1)).hensel_lift(7, 2)

If the input polynomial \(f\) is not monic, we get a factorization of \(f / lc(f)\):

Sage

sage: R(2*x^2 - 2).hensel_lift(7, 2)
[x + 1, x + 48]

Python

>>> from sage.all import *
>>> R(Integer(2)*x**Integer(2) - Integer(2)).hensel_lift(Integer(7), Integer(2))
[x + 1, x + 48]

Sage Live

R(2*x^2 - 2).hensel_lift(7, 2)

inverse_series_trunc(prec)

Return a polynomial approximation of precision prec of the inverse series of this polynomial.

EXAMPLES:

Sage

sage: x = polygen(QQ)
sage: p = 2 + x - 3/5*x**2
sage: q5 = p.inverse_series_trunc(5)
sage: q5
151/800*x^4 - 17/80*x^3 + 11/40*x^2 - 1/4*x + 1/2
sage: q5 * p
-453/4000*x^6 + 253/800*x^5 + 1

sage: q100 = p.inverse_series_trunc(100)
sage: (q100 * p).truncate(100)
1

Python

>>> from sage.all import *
>>> x = polygen(QQ)
>>> p = Integer(2) + x - Integer(3)/Integer(5)*x**Integer(2)
>>> q5 = p.inverse_series_trunc(Integer(5))
>>> q5
151/800*x^4 - 17/80*x^3 + 11/40*x^2 - 1/4*x + 1/2
>>> q5 * p
-453/4000*x^6 + 253/800*x^5 + 1

>>> q100 = p.inverse_series_trunc(Integer(100))
>>> (q100 * p).truncate(Integer(100))
1

Sage Live

x = polygen(QQ)
p = 2 + x - 3/5*x**2
q5 = p.inverse_series_trunc(5)
q5
q5 * p
q100 = p.inverse_series_trunc(100)
(q100 * p).truncate(100)

is_irreducible()

Return whether this polynomial is irreducible.

This method computes the primitive part as an element of \(\ZZ[t]\) and calls the method is_irreducible for elements of that polynomial ring.

By definition, over any integral domain, an element \(r\) is irreducible if and only if it is nonzero, not a unit and whenever \(r = ab\) then \(a\) or \(b\) is a unit.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: (t^2 + 2).is_irreducible()
True
sage: (t^2 - 1).is_irreducible()
False

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> (t**Integer(2) + Integer(2)).is_irreducible()
True
>>> (t**Integer(2) - Integer(1)).is_irreducible()
False

Sage Live

R.<t> = QQ[]
(t^2 + 2).is_irreducible()
(t^2 - 1).is_irreducible()

is_one()

Return whether or not this polynomial is one.

EXAMPLES:

Sage

sage: R.<x> = QQ[]
sage: R([0,1]).is_one()
False
sage: R([1]).is_one()
True
sage: R([0]).is_one()
False
sage: R([-1]).is_one()
False
sage: R([1,1]).is_one()
False

Python

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> R([Integer(0),Integer(1)]).is_one()
False
>>> R([Integer(1)]).is_one()
True
>>> R([Integer(0)]).is_one()
False
>>> R([-Integer(1)]).is_one()
False
>>> R([Integer(1),Integer(1)]).is_one()
False

Sage Live

R.<x> = QQ[]
R([0,1]).is_one()
R([1]).is_one()
R([0]).is_one()
R([-1]).is_one()
R([1,1]).is_one()

is_zero()

Return whether or not self is the zero polynomial.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = 1 - t + 1/2*t^2 - 1/3*t^3
sage: f.is_zero()
False
sage: R(0).is_zero()
True

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(1) - t + Integer(1)/Integer(2)*t**Integer(2) - Integer(1)/Integer(3)*t**Integer(3)
>>> f.is_zero()
False
>>> R(Integer(0)).is_zero()
True

Sage Live

R.<t> = QQ[]
f = 1 - t + 1/2*t^2 - 1/3*t^3
f.is_zero()
R(0).is_zero()

lcm(right)

Return the monic (or zero) least common multiple of self and right.

Corner cases: if either of self and right are zero, returns zero. This behaviour is ensures that the relation \(\lcm(a,b)\cdot \gcd(a,b) = a\cdot b\) holds up to multiplication by rationals.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = -2 + 3*t/2 + 4*t^2/7 - t^3
sage: g = 1/2 + 4*t + 2*t^4/3
sage: f.lcm(g)
t^7 - 4/7*t^6 - 3/2*t^5 + 8*t^4 - 75/28*t^3 - 66/7*t^2 + 87/8*t + 3/2
sage: f.lcm(g) * f.gcd(g) // (f * g)
-3/2

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = -Integer(2) + Integer(3)*t/Integer(2) + Integer(4)*t**Integer(2)/Integer(7) - t**Integer(3)
>>> g = Integer(1)/Integer(2) + Integer(4)*t + Integer(2)*t**Integer(4)/Integer(3)
>>> f.lcm(g)
t^7 - 4/7*t^6 - 3/2*t^5 + 8*t^4 - 75/28*t^3 - 66/7*t^2 + 87/8*t + 3/2
>>> f.lcm(g) * f.gcd(g) // (f * g)
-3/2

Sage Live

R.<t> = QQ[]
f = -2 + 3*t/2 + 4*t^2/7 - t^3
g = 1/2 + 4*t + 2*t^4/3
f.lcm(g)
f.lcm(g) * f.gcd(g) // (f * g)

list(copy=True)

Return a list with the coefficients of self.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = 1 + t + t^2/2 + t^3/3 + t^4/4
sage: f.list()
[1, 1, 1/2, 1/3, 1/4]
sage: g = R(0)
sage: g.list()
[]

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(1) + t + t**Integer(2)/Integer(2) + t**Integer(3)/Integer(3) + t**Integer(4)/Integer(4)
>>> f.list()
[1, 1, 1/2, 1/3, 1/4]
>>> g = R(Integer(0))
>>> g.list()
[]

Sage Live

R.<t> = QQ[]
f = 1 + t + t^2/2 + t^3/3 + t^4/4
f.list()
g = R(0)
g.list()

numerator()

Return the numerator of self.

Representing self as the quotient of an integer polynomial and a positive integer denominator (coprime to the content of the polynomial), returns the integer polynomial.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = (3 * t^3 + 1) / -3
sage: f.numerator()
-3*t^3 - 1

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = (Integer(3) * t**Integer(3) + Integer(1)) / -Integer(3)
>>> f.numerator()
-3*t^3 - 1

Sage Live

R.<t> = QQ[]
f = (3 * t^3 + 1) / -3
f.numerator()

quo_rem(right)

Return the quotient and remainder of the Euclidean division of self and right.

Raises a ZeroDivisionError if right is zero.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = R.random_element(2000)
sage: g = R.random_element(1000)
sage: q, r = f.quo_rem(g)
sage: f == q*g + r
True

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = R.random_element(Integer(2000))
>>> g = R.random_element(Integer(1000))
>>> q, r = f.quo_rem(g)
>>> f == q*g + r
True

Sage Live

R.<t> = QQ[]
f = R.random_element(2000)
g = R.random_element(1000)
q, r = f.quo_rem(g)
f == q*g + r

real_root_intervals()

Return isolating intervals for the real roots of self.

EXAMPLES:

We compute the roots of the characteristic polynomial of some Salem numbers:

Sage

sage: R.<t> = QQ[]
sage: f = 1 - t^2 - t^3 - t^4 + t^6
sage: f.real_root_intervals()
[((1/2, 3/4), 1), ((1, 3/2), 1)]

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(1) - t**Integer(2) - t**Integer(3) - t**Integer(4) + t**Integer(6)
>>> f.real_root_intervals()
[((1/2, 3/4), 1), ((1, 3/2), 1)]

Sage Live

R.<t> = QQ[]
f = 1 - t^2 - t^3 - t^4 + t^6
f.real_root_intervals()

resultant(right)

Return the resultant of self and right.

Enumerating the roots over \(\QQ\) as \(r_1, \dots, r_m\) and \(s_1, \dots, s_n\) and letting \(x\) and \(y\) denote the leading coefficients of \(f\) and \(g\), the resultant of the two polynomials is defined by

\[x^{\deg g} y^{\deg f} \prod_{i,j} (r_i - s_j).\]

Corner cases: if one of the polynomials is zero, the resultant is zero. Note that otherwise if one of the polynomials is constant, the last term in the above is the empty product.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = (t - 2/3) * (t + 4/5) * (t - 1)
sage: g = (t - 1/3) * (t + 1/2) * (t + 1)
sage: f.resultant(g)
119/1350
sage: h = (t - 1/3) * (t + 1/2) * (t - 1)
sage: f.resultant(h)
0

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = (t - Integer(2)/Integer(3)) * (t + Integer(4)/Integer(5)) * (t - Integer(1))
>>> g = (t - Integer(1)/Integer(3)) * (t + Integer(1)/Integer(2)) * (t + Integer(1))
>>> f.resultant(g)
119/1350
>>> h = (t - Integer(1)/Integer(3)) * (t + Integer(1)/Integer(2)) * (t - Integer(1))
>>> f.resultant(h)
0

Sage Live

R.<t> = QQ[]
f = (t - 2/3) * (t + 4/5) * (t - 1)
g = (t - 1/3) * (t + 1/2) * (t + 1)
f.resultant(g)
h = (t - 1/3) * (t + 1/2) * (t - 1)
f.resultant(h)

reverse(degree=None)

Reverse the coefficients of this polynomial (thought of as a polynomial of degree degree).

INPUT:

• degree – None or integral value that fits in an unsigned long (default: degree of self); if specified, truncate or zero pad the list of coefficients to this degree before reversing it

EXAMPLES:

We first consider the simplest case, where we reverse all coefficients of a polynomial and obtain a polynomial of the same degree:

Sage

sage: R.<t> = QQ[]
sage: f = 1 + t + t^2 / 2 + t^3 / 3 + t^4 / 4
sage: f.reverse()
t^4 + t^3 + 1/2*t^2 + 1/3*t + 1/4

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(1) + t + t**Integer(2) / Integer(2) + t**Integer(3) / Integer(3) + t**Integer(4) / Integer(4)
>>> f.reverse()
t^4 + t^3 + 1/2*t^2 + 1/3*t + 1/4

Sage Live

R.<t> = QQ[]
f = 1 + t + t^2 / 2 + t^3 / 3 + t^4 / 4
f.reverse()

Next, an example where the returned polynomial has lower degree because the original polynomial has low coefficients equal to zero:

Sage

sage: R.<t> = QQ[]
sage: f = 3/4*t^2 + 6*t^7
sage: f.reverse()
3/4*t^5 + 6

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(3)/Integer(4)*t**Integer(2) + Integer(6)*t**Integer(7)
>>> f.reverse()
3/4*t^5 + 6

Sage Live

R.<t> = QQ[]
f = 3/4*t^2 + 6*t^7
f.reverse()

The next example illustrates the passing of a value for degree less than the length of self, notationally resulting in truncation prior to reversing:

Sage

sage: R.<t> = QQ[]
sage: f = 1 + t + t^2 / 2 + t^3 / 3 + t^4 / 4
sage: f.reverse(2)
t^2 + t + 1/2

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(1) + t + t**Integer(2) / Integer(2) + t**Integer(3) / Integer(3) + t**Integer(4) / Integer(4)
>>> f.reverse(Integer(2))
t^2 + t + 1/2

Sage Live

R.<t> = QQ[]
f = 1 + t + t^2 / 2 + t^3 / 3 + t^4 / 4
f.reverse(2)

Now we illustrate the passing of a value for degree greater than the length of self, notationally resulting in zero padding at the top end prior to reversing:

Sage

sage: R.<t> = QQ[]
sage: f = 1 + t + t^2 / 2 + t^3 / 3
sage: f.reverse(4)
t^4 + t^3 + 1/2*t^2 + 1/3*t

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(1) + t + t**Integer(2) / Integer(2) + t**Integer(3) / Integer(3)
>>> f.reverse(Integer(4))
t^4 + t^3 + 1/2*t^2 + 1/3*t

Sage Live

R.<t> = QQ[]
f = 1 + t + t^2 / 2 + t^3 / 3
f.reverse(4)

revert_series(n)

Return a polynomial \(f\) such that f(self(x)) = self(f(x)) = x mod x^n.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = t - t^3/6 + t^5/120
sage: f.revert_series(6)
3/40*t^5 + 1/6*t^3 + t

sage: f.revert_series(-1)
Traceback (most recent call last):
ValueError: argument n must be a nonnegative integer, got -1

sage: g = - t^3/3 + t^5/5
sage: g.revert_series(6)
Traceback (most recent call last):
...
ValueError: self must have constant coefficient 0 and a unit for coefficient t^1

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = t - t**Integer(3)/Integer(6) + t**Integer(5)/Integer(120)
>>> f.revert_series(Integer(6))
3/40*t^5 + 1/6*t^3 + t

>>> f.revert_series(-Integer(1))
Traceback (most recent call last):
ValueError: argument n must be a nonnegative integer, got -1

>>> g = - t**Integer(3)/Integer(3) + t**Integer(5)/Integer(5)
>>> g.revert_series(Integer(6))
Traceback (most recent call last):
...
ValueError: self must have constant coefficient 0 and a unit for coefficient t^1

Sage Live

R.<t> = QQ[]
f = t - t^3/6 + t^5/120
f.revert_series(6)
f.revert_series(-1)
g = - t^3/3 + t^5/5
g.revert_series(6)

truncate(n)

Return self truncated modulo \(t^n\).

INPUT:

• n – the power of \(t\) modulo which self is truncated

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = 1 - t + 1/2*t^2 - 1/3*t^3
sage: f.truncate(0)
0
sage: f.truncate(2)
-t + 1

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(1) - t + Integer(1)/Integer(2)*t**Integer(2) - Integer(1)/Integer(3)*t**Integer(3)
>>> f.truncate(Integer(0))
0
>>> f.truncate(Integer(2))
-t + 1

Sage Live

R.<t> = QQ[]
f = 1 - t + 1/2*t^2 - 1/3*t^3
f.truncate(0)
f.truncate(2)

xgcd(right)

Return polynomials \(d\), \(s\), and \(t\) such that d == s * self + t * right, where \(d\) is the (monic) greatest common divisor of self and right. The choice of \(s\) and \(t\) is not specified any further.

Corner cases: if self and right are zero, returns zero polynomials. Otherwise, if only self is zero, returns (d, s, t) = (right, 0, 1) up to normalisation, and similarly if only right is zero.

EXAMPLES:

Sage

sage: R.<t> = QQ[]
sage: f = 2/3 + 3/4 * t - t^2
sage: g = -3 + 1/7 * t
sage: f.xgcd(g)
(1, -12/5095, -84/5095*t - 1701/5095)

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> f = Integer(2)/Integer(3) + Integer(3)/Integer(4) * t - t**Integer(2)
>>> g = -Integer(3) + Integer(1)/Integer(7) * t
>>> f.xgcd(g)
(1, -12/5095, -84/5095*t - 1701/5095)

Sage Live

R.<t> = QQ[]
f = 2/3 + 3/4 * t - t^2
g = -3 + 1/7 * t
f.xgcd(g)

Make live