Univariate polynomials over \(\QQ\) implemented via FLINT¶
AUTHOR:
Sebastian Pancratz
- class sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint[source]¶
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)[source]¶
Return the sum of two rational polynomials.
EXAMPLES:
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
>>> 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
- _sub_(right)[source]¶
Return the difference of two rational polynomials.
EXAMPLES:
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
>>> 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
- _lmul_(right)[source]¶
Return
self * right
, whereright
is a rational number.EXAMPLES:
sage: R.<t> = QQ[] sage: f = 3/2*t^3 - t + 1/3 sage: f * 6 # indirect doctest 9*t^3 - 6*t + 2
>>> 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
- _rmul_(left)[source]¶
Return
left * self
, whereleft
is a rational number.EXAMPLES:
sage: R.<t> = QQ[] sage: f = 3/2*t^3 - t + 1/3 sage: 6 * f # indirect doctest 9*t^3 - 6*t + 2
>>> 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
- _mul_(right)[source]¶
Return the product of
self
andright
.EXAMPLES:
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
>>> 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
- _mul_trunc_(right, n)[source]¶
Truncated multiplication.
EXAMPLES:
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
>>> 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
ALGORITHM:
Call the FLINT method
fmpq_poly_mullow
.
- degree()[source]¶
Return the degree of
self
.By convention, the degree of the zero polynomial is \(-1\).
EXAMPLES:
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
>>> 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
- denominator()[source]¶
Return the denominator of
self
.EXAMPLES:
sage: R.<t> = QQ[] sage: f = (3 * t^3 + 1) / -3 sage: f.denominator() 3
>>> 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
- disc()[source]¶
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: 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
>>> 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: R.<t> = QQ[] sage: f = 2*t^3 + t + 1 sage: d = f.discriminant(); d -116
>>> 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: R.<t> = QQ[] sage: f = t^3 + 3*t - 17 sage: f.discriminant() -7911
>>> from sage.all import * >>> R = QQ['t']; (t,) = R._first_ngens(1) >>> f = t**Integer(3) + Integer(3)*t - Integer(17) >>> f.discriminant() -7911
- discriminant()[source]¶
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: 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
>>> 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: R.<t> = QQ[] sage: f = 2*t^3 + t + 1 sage: d = f.discriminant(); d -116
>>> 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: R.<t> = QQ[] sage: f = t^3 + 3*t - 17 sage: f.discriminant() -7911
>>> from sage.all import * >>> R = QQ['t']; (t,) = R._first_ngens(1) >>> f = t**Integer(3) + Integer(3)*t - Integer(17) >>> f.discriminant() -7911
- factor_mod(p)[source]¶
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: 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
>>> 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
Variable names that are reserved in PARI, such as
zeta
, are supported (see Issue #20631):sage: R.<zeta> = QQ[] sage: (zeta^2 + zeta + 1).factor_mod(7) (zeta + 3) * (zeta + 5)
>>> 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)
- factor_padic(p, prec=10)[source]¶
Return the \(p\)-adic factorization of this polynomial to the given precision.
INPUT:
p
– prime numberprec
– integer; the precision
OUTPUT: factorization of
self
viewed as a \(p\)-adic polynomialEXAMPLES:
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))
>>> 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))
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: # 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
>>> 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
A more difficult example:
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
>>> 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
Try some bogus inputs:
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
>>> 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
- galois_group(pari_group=False, algorithm='pari')[source]¶
Return the Galois group of this polynomial as a permutation group.
INPUT:
self
– irreducible polynomialpari_group
– boolean (default:False
); ifTrue
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 groupP
, typePermutationGroup(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: # 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
>>> 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
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: # 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
>>> 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
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: 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
>>> 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
- galois_group_davenport_smith_test(num_trials=50, assume_irreducible=False)[source]¶
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: 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
>>> 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
- gcd(right)[source]¶
Return the (monic) greatest common divisor of
self
andright
.Corner cases: if
self
andright
are both zero, returns zero. If only one of them is zero, returns the other polynomial, up to normalisation.EXAMPLES:
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
>>> 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
- hensel_lift(p, e)[source]¶
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:
OUTPUT: Hensel lifts; list of polynomials over \(\ZZ / p^e \ZZ\)
EXAMPLES:
sage: R.<x> = QQ[] sage: R((x-1)*(x+1)).hensel_lift(7, 2) [x + 1, x + 48]
>>> 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]
If the input polynomial \(f\) is not monic, we get a factorization of \(f / lc(f)\):
sage: R(2*x^2 - 2).hensel_lift(7, 2) [x + 1, x + 48]
>>> from sage.all import * >>> R(Integer(2)*x**Integer(2) - Integer(2)).hensel_lift(Integer(7), Integer(2)) [x + 1, x + 48]
- inverse_series_trunc(prec)[source]¶
Return a polynomial approximation of precision
prec
of the inverse series of this polynomial.EXAMPLES:
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
>>> 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
- is_irreducible()[source]¶
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: R.<t> = QQ[] sage: (t^2 + 2).is_irreducible() True sage: (t^2 - 1).is_irreducible() False
>>> 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
- is_one()[source]¶
Return whether or not this polynomial is one.
EXAMPLES:
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
>>> 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
- is_zero()[source]¶
Return whether or not
self
is the zero polynomial.EXAMPLES:
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
>>> 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
- lcm(right)[source]¶
Return the monic (or zero) least common multiple of
self
andright
.Corner cases: if either of
self
andright
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: 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
>>> 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
- list(copy=True)[source]¶
Return a list with the coefficients of
self
.EXAMPLES:
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() []
>>> 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() []
- numerator()[source]¶
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: R.<t> = QQ[] sage: f = (3 * t^3 + 1) / -3 sage: f.numerator() -3*t^3 - 1
>>> 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
- quo_rem(right)[source]¶
Return the quotient and remainder of the Euclidean division of
self
andright
.Raises a
ZeroDivisionError
ifright
is zero.EXAMPLES:
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
>>> 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
- real_root_intervals()[source]¶
Return isolating intervals for the real roots of
self
.EXAMPLES:
We compute the roots of the characteristic polynomial of some Salem numbers:
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)]
>>> 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)]
- resultant(right)[source]¶
Return the resultant of
self
andright
.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: 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
>>> 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
- reverse(degree=None)[source]¶
Reverse the coefficients of this polynomial (thought of as a polynomial of degree
degree
).INPUT:
degree
–None
or integral value that fits in anunsigned long
(default: degree ofself
); 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: 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
>>> 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
Next, an example where the returned polynomial has lower degree because the original polynomial has low coefficients equal to zero:
sage: R.<t> = QQ[] sage: f = 3/4*t^2 + 6*t^7 sage: f.reverse() 3/4*t^5 + 6
>>> 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
The next example illustrates the passing of a value for
degree
less than the length ofself
, notationally resulting in truncation prior to reversing: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
>>> 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
Now we illustrate the passing of a value for
degree
greater than the length ofself
, notationally resulting in zero padding at the top end prior to reversing: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
>>> 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
- revert_series(n)[source]¶
Return a polynomial \(f\) such that
f(self(x)) = self(f(x)) = x mod x^n
.EXAMPLES:
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
>>> 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
- truncate(n)[source]¶
Return
self
truncated modulo \(t^n\).INPUT:
n
– the power of \(t\) modulo whichself
is truncated
EXAMPLES:
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
>>> 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
- xgcd(right)[source]¶
Return polynomials \(d\), \(s\), and \(t\) such that
d == s * self + t * right
, where \(d\) is the (monic) greatest common divisor ofself
andright
. The choice of \(s\) and \(t\) is not specified any further.Corner cases: if
self
andright
are zero, returns zero polynomials. Otherwise, if onlyself
is zero, returns(d, s, t) = (right, 0, 1)
up to normalisation, and similarly if onlyright
is zero.EXAMPLES:
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)
>>> 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)