fmpz_poly – polynomials over integers

class flint.fmpz_poly(*args)

The fmpz_poly type represents dense univariate polynomials over the integers.

>>> fmpz_poly([1,2,3]) ** 3
27*x^6 + 54*x^5 + 63*x^4 + 44*x^3 + 21*x^2 + 6*x + 1
>>> divmod(fmpz_poly([2,0,1,1,6]), fmpz_poly([3,5,7]))
(0, 6*x^4 + x^3 + x^2 + 2)

static chebyshev_t(n)

Returns the Chebyshev polynomial of the first kind \(T_n(x)\) as an fmpz_poly.

>>> fmpz_poly.chebyshev_t(3)
4*x^3 + (-3)*x

static chebyshev_u(n)

Returns the Chebyshev polynomial of the second kind \(U_n(x)\) as an fmpz_poly.

>>> fmpz_poly.chebyshev_u(3)
8*x^3 + (-4)*x

coeffs(self)

Returns the coefficients of self as a list

>>> from flint import fmpz_poly
>>> f = fmpz_poly([1,2,3,4,5])
>>> f.coeffs()
[1, 2, 3, 4, 5]

complex_roots(self, bool verbose=False)

Computes all the complex roots of this polynomial. Returns a list of pairs (c, m) where c is the root as an acb and m is the multiplicity of the root.

>>> from flint import fmpz_poly, ctx
>>> ctx.prec = 53

>>> fmpz_poly([]).complex_roots()
[]
>>> fmpz_poly([1]).complex_roots()
[]
>>> fmpz_poly([2,0,1]).complex_roots()
[([1.41421356237310 +/- 4.96e-15]j, 1), ([-1.41421356237310 +/- 4.96e-15]j, 1)]
>>> for c, m in (fmpz_poly([2,3,4]) * fmpz_poly([5,6,7,11])**3).complex_roots():
...     print(f'{float(c.real)} + {float(c.imag)}*j : {m}')
...
-0.375 + 0.5994789404140899*j : 1
-0.375 + -0.5994789404140899*j : 1
-0.7352847274048426 + 0.0*j : 3
0.04946054552060311 + 0.7846931676471847*j : 3
0.04946054552060311 + -0.7846931676471847*j : 3

content(self)

Return the GCD of the coefficients of self.

>>> fmpz_poly([3, 6, 0]).content()
3

static cos_minpoly(ulong n)

Returns the monic polynomial of \(2 \cos(2 \pi / n)\) as an fmpz_poly.

>>> fmpz_poly.cos_minpoly(7)
x^3 + x^2 + (-2)*x + (-1)

static cyclotomic(ulong n)

Returns the cyclotomic polynomial \(\Phi_n(x)\) as an fmpz_poly.

>>> fmpz_poly.cyclotomic(12)
x^4 + (-1)*x^2 + 1

deflate(self, int n: int) → fmpz_poly

Compute the deflation of self for a provided n, that is return q such that q(x) = p(x^(1/n)).

>>> f = fmpz_poly([1, 0, 1])
>>> f.deflate(2)
x + 1

deflation(self) → tuple[fmpz_poly, int]

Compute the deflation of self, that is p(x^(1/n)) for maximal n. returns q, n such that self == q.inflate(n).

>>> f = fmpz_poly([1, 0, 1])
>>> q, n = f.deflation()
>>> q, n
(x + 1, 2)
>>> q.inflate(n) == f
True

deflation_index(self) → tuple[int, int]

Compute the exponent n and i such that p(x^(1/n)) = x^i * q(x^n) for maximal n. Importantly the deflation itself is not computed here. The returned exponent i is the shift that was applied to the exponents. It is the exponent of the monomial returned by deflation_monom.

>>> f = fmpz_poly([1, 0, 1])
>>> f.deflation_index()
(1, 1)

deflation_monom(self) → tuple[fmpz_poly, int, fmpz_poly]

Compute the exponent n and monomial m such that p(x^(1/n)) = m * q(x^n) for maximal n. The returned monomial allows the undo-ing of the deflation.

>>> f = fmpz_poly([1, 0, 1])
>>> f.deflation_monom()
(x^2 + 1, 1, x)

degree(self) → long

derivative(self)

factor(self)

Factors self into irreducible factors, returning a tuple (c, factors) where c is the content of the coefficients and factors is a list of (poly, exp) pairs.

>>> (-73 * fmpz_poly([1,2,3]) ** 3 * fmpz_poly([5,6,7,8,9]) ** 8).factor()
(-73, [(3*x^2 + 2*x + 1, 3), (9*x^4 + 8*x^3 + 7*x^2 + 6*x + 5, 8)])
>>> fmpz_poly.chebyshev_t(6).factor()
(1, [(2*x^2 + (-1), 1), (16*x^4 + (-16)*x^2 + 1, 1)])
>>> (fmpz_poly([-1,1])**100).factor()
(1, [(x + (-1), 100)])
>>> fmpz_poly([1,2,3,4,5,6]).factor()
(1, [(6*x^5 + 5*x^4 + 4*x^3 + 3*x^2 + 2*x + 1, 1)])

factor_squarefree(self)

Factors self into square-free factors, returning a tuple (c, factors) where c is the content of the coefficients and factors is a list of (poly, exp) pairs.

>>> x = fmpz_poly([0, 1])
>>> p = (-3 * x**2 * (x + 1)**2 * (x - 1)**3)
>>> p.factor_squarefree()
(-3, [(x^2 + x, 2), (x + (-1), 3)])
>>> p.factor()
(-3, [(x, 2), (x + 1, 2), (x + (-1), 3)])

gcd(self, other)

Returns the greatest common divisor of self and other.

>>> A = fmpz_poly([2,0,1,0,5]); B = fmpz_poly([2,3,4])
>>> (A*B).gcd(B)
4*x^2 + 3*x + 2

height_bits(self, bool signed=False)

static hilbert_class_poly(long D)

Returns the Hilbert class polynomial \(H_D(x)\) as an fmpz_poly.

>>> fmpz_poly.hilbert_class_poly(-3)
x
>>> fmpz_poly.hilbert_class_poly(-4)
x + (-1728)
>>> fmpz_poly.hilbert_class_poly(-59)
x^3 + 30197678080*x^2 + (-140811576541184)*x + 374643194001883136
>>> fmpz_poly.hilbert_class_poly(-5)
Traceback (most recent call last):
  ...
ValueError: D must be an imaginary quadratic discriminant

inflate(self, int n: int) → fmpz_poly

Compute the inflation of self for a provided n, that is return q such that q(x) = p(x^n).

>>> f = fmpz_poly([1, 1])
>>> f.inflate(2)
x^2 + 1

is_constant(self)

True if this is a constant polynomial.

>>> x = fmpz_poly([0, 1])
>>> two = fmpz_poly([2])
>>> x.is_constant()
False
>>> two.is_constant()
True

is_cyclotomic(self)

is_gen(self)

Return True if the polynomial is the generator of the polynomial, \(x\), and False otherwise

>>> x = fmpz_poly([0, 1])
>>> x
x
>>> x.is_gen()
True
>>> (x + 1).is_gen()
False

is_one(self)

True if this polynomial is equal to one.

>>> fmpz_poly([2]).is_one()
False

is_zero(self)

True if this polynomial is the zero polynomial.

>>> fmpz_poly([]).is_zero()
True

leading_coefficient(self)

Returns the leading coefficient of the polynomial.

>>> f = fmpz_poly([1, 2, 3])
>>> f
3*x^2 + 2*x + 1
>>> f.leading_coefficient()
3

left_shift(self, slong n)

Returns self shifted left by n coefficients by inserting zero coefficients. This is equivalent to multiplying the polynomial by x^n

>>> f = fmpz_poly([1,2,3])
>>> f.left_shift(0)
3*x^2 + 2*x + 1
>>> f.left_shift(1)
3*x^3 + 2*x^2 + x
>>> f.left_shift(4)
3*x^6 + 2*x^5 + x^4

length(self) → long

real_roots(self)

repr(self)

resultant(self, other)

Returns the resultant of self and other.

>>> A = fmpz_poly([1, 0, -1]); B = fmpz_poly([1, -1])
>>> A.resultant(B)
0
>>> C = fmpz_poly([1, 0, 0, 0, 0, -1, 1])
>>> D = fmpz_poly([1, 0, 0, -1, 0, 0, 1])
>>> C.resultant(D)
3
>>> f = fmpz_poly([1, -1] + [0] * 98 + [1])
>>> g = fmpz_poly([1] + [0] * 50 + [-1] + [0] * 48 + [1])
>>> f.resultant(g)
1125899906842623

right_shift(self, slong n)

Returns self shifted right by n coefficients. This is equivalent to the floor division of the polynomial by x^n

>>> f = fmpz_poly([1,2,3])
>>> f.right_shift(0)
3*x^2 + 2*x + 1
>>> f.right_shift(1)
3*x + 2
>>> f.right_shift(4)
0

roots(self)

Computes all the roots in the base ring of the polynomial. Returns a list of all pairs (v, m) where v is the integer root and m is the multiplicity of the root.

To compute complex roots of a polynomial, instead use the .complex_roots() method, which is available on certain polynomial rings.

>>> from flint import fmpz_poly
>>> fmpz_poly([1, 2]).roots()
[]
>>> fmpz_poly([2, 1]).roots()
[(-2, 1)]
>>> fmpz_poly([12, 7, 1]).roots()
[(-3, 1), (-4, 1)]
>>> (fmpz_poly([-5,1]) * fmpz_poly([-5,1]) * fmpz_poly([-3,1])).roots()
[(3, 1), (5, 2)]

sqrt(self)

str(self, bool ascending=False, var='x', *args, **kwargs)

Convert to a human-readable string (generic implementation for all polynomial types).

If ascending is True, the monomials are output from low degree to high, otherwise from high to low.

static swinnerton_dyer(ulong n, bool use_arb=True)

Returns the Swinnerton-Dyer polynomial \(S_n(x)\) as an fmpz_poly. Warning: the degree is \(2^n\).

>>> fmpz_poly.swinnerton_dyer(0)
x
>>> fmpz_poly.swinnerton_dyer(1)
x^2 + (-2)
>>> fmpz_poly.swinnerton_dyer(2)
x^4 + (-10)*x^2 + 1
>>> fmpz_poly.swinnerton_dyer(3)
x^8 + (-40)*x^6 + 352*x^4 + (-960)*x^2 + 576

truncate(self, slong n)

Notionally truncate the polynomial to have length n. If n is larger than the length of the input, then a copy of self is returned. If n is not positive, then the zero polynomial is returned.

Effectively returns this polynomial \(\mod x^n\).

>>> f = fmpz_poly([1,2,3])
>>> f.truncate(3) == f
True
>>> f.truncate(2)
2*x + 1
>>> f.truncate(1)
1
>>> f.truncate(0)
0
>>> f.truncate(-1)
0