Polynomials¶

Polynomial manipulation algorithms and algebraic objects.

Computations with polynomials are at the core of computer algebra and having a fast and robust polynomials manipulation module is a key for building a powerful symbolic manipulation system. Here we document a dedicated module for computing in polynomial algebras over various coefficient domains.

There is a vast number of methods implemented, ranging from simple tools like polynomial division, to advanced concepts including Gröbner bases and multivariate factorization over algebraic number domains.

Basic polynomial manipulation functions¶

User-friendly public interface to polynomial functions.

class diofant.polys.polytools.Poly[source]

Generic class for representing polynomial expressions.

EC(order=None)[source]

Returns the last non-zero coefficient of self.

Examples

>>> Poly(x**3 + 2*x**2 + 3*x, x).EC()
3

EM(order=None)[source]

Returns the last non-zero monomial of self.

Examples

>>> Poly(4*x**2 + 2*x*y**2 + x*y + 3*y, x, y).EM()
x**0*y**1

ET(order=None)[source]

Returns the last non-zero term of self.

Examples

>>> Poly(4*x**2 + 2*x*y**2 + x*y + 3*y, x, y).ET()
(x**0*y**1, 3)

LC(order=None)[source]

Returns the leading coefficient of self.

Examples

>>> Poly(4*x**3 + 2*x**2 + 3*x, x).LC()
4

LM(order=None)[source]

Returns the leading monomial of self.

The leading monomial signifies the the monomial having the highest power of the principal generator in the polynomial expression.

Examples

>>> Poly(4*x**2 + 2*x*y**2 + x*y + 3*y, x, y).LM()
x**2*y**0

LT(order=None)[source]

Returns the leading term of self.

The leading term signifies the term having the highest power of the principal generator in the polynomial expression.

Examples

>>> Poly(4*x**2 + 2*x*y**2 + x*y + 3*y, x, y).LT()
(x**2*y**0, 4)

TC()[source]

Returns the trailing coefficient of self.

Examples

>>> Poly(x**3 + 2*x**2 + 3*x, x).TC()
0

all_coeffs()[source]

Returns all coefficients from a univariate polynomial self.

Examples

>>> Poly(x**3 + 2*x - 1, x).all_coeffs()
[1, 0, 2, -1]

all_roots(multiple=True, radicals=True)[source]

Return a list of real and complex roots with multiplicities.

Examples

>>> Poly(2*x**3 - 7*x**2 + 4*x + 4).all_roots()
[-1/2, 2, 2]
>>> Poly(x**3 + x + 1).all_roots()
[RootOf(x**3 + x + 1, 0), RootOf(x**3 + x + 1, 1),
RootOf(x**3 + x + 1, 2)]

args

Don’t mess up with the core.

Examples

>>> Poly(x**2 + 1, x).args
(x**2 + 1, x)

as_dict(native=False)[source]

Switch to a dict representation.

Examples

>>> Poly(x**2 + 2*x*y**2 - y, x, y).as_dict()
{(0, 1): -1, (1, 2): 2, (2, 0): 1}

as_expr(*gens)[source]

Convert a Poly instance to an Expr instance.

Examples

>>> f = Poly(x**2 + 2*x*y**2 - y, x, y)

>>> f.as_expr()
x**2 + 2*x*y**2 - y
>>> f.as_expr({x: 5})
10*y**2 - y + 25
>>> f.as_expr(5, 6)
379

cancel(other, include=False)[source]

Cancel common factors in a rational function self/other.

Examples

>>> Poly(2*x**2 - 2, x).cancel(Poly(x**2 - 2*x + 1, x))
(1, Poly(2*x + 2, x, domain='ZZ'), Poly(x - 1, x, domain='ZZ'))

>>> Poly(2*x**2 - 2, x).cancel(Poly(x**2 - 2*x + 1, x), include=True)
(Poly(2*x + 2, x, domain='ZZ'), Poly(x - 1, x, domain='ZZ'))

clear_denoms(convert=False)[source]

Clear denominators, but keep the ground domain.

Examples

>>> f = Poly(x/2 + Rational(1, 3))

>>> f.clear_denoms()
(6, Poly(3*x + 2, x, domain='QQ'))
>>> f.clear_denoms(convert=True)
(6, Poly(3*x + 2, x, domain='ZZ'))

coeff_monomial(monom)[source]

Returns the coefficient of monom in self if there, else None.

Examples

>>> p = Poly(24*x*y*exp(8) + 23*x, x, y)

>>> p.coeff_monomial(x)
23
>>> p.coeff_monomial(y)
0
>>> p.coeff_monomial(x*y)
24*E**8
>>> p.coeff_monomial((1, 1))
24*E**8


Note that Expr.coeff() behaves differently, collecting terms if possible; the Poly must be converted to an Expr to use that method, however:

>>> p.as_expr().coeff(x)
24*E**8*y + 23
>>> p.as_expr().coeff(y)
24*E**8*x
>>> p.as_expr().coeff(x*y)
24*E**8

coeffs(order=None)[source]

Returns all non-zero coefficients from self in lex order.

Examples

>>> Poly(x**3 + 2*x + 3, x).coeffs()
[1, 2, 3]

cofactors(other)[source]

Returns the GCD of self and other and their cofactors.

For two polynomials f and g it returns polynomials (h, cff, cfg) such that h = gcd(f, g), and cff = quo(f, h) and cfg = quo(g, h) are, so called, cofactors of f and g.

Examples

>>> Poly(x**2 - 1, x).cofactors(Poly(x**2 - 3*x + 2, x))
(Poly(x - 1, x, domain='ZZ'),
Poly(x + 1, x, domain='ZZ'),
Poly(x - 2, x, domain='ZZ'))

compose(other)[source]

Computes the functional composition of self and other.

Examples

>>> Poly(x**2 + x, x).compose(Poly(x - 1, x))
Poly(x**2 - x, x, domain='ZZ')

content()[source]

Returns the GCD of polynomial coefficients.

Examples

>>> Poly(6*x**2 + 8*x + 12, x).content()
2

count_roots(inf=None, sup=None)[source]

Return the number of roots of self in [inf, sup] interval.

Examples

>>> Poly(x**4 - 4, x).count_roots(-3, 3)
2
>>> Poly(x**4 - 4, x).count_roots(0, 1 + 3*I)
1

decompose()[source]

Computes a functional decomposition of self.

Examples

>>> Poly(x**4 + 2*x**3 - x - 1).decompose()
[Poly(x**2 - x - 1, x, domain='ZZ'), Poly(x**2 + x, x, domain='ZZ')]

deflate()[source]

Reduce degree of self by mapping x_i**m to y_i.

Examples

>>> Poly(x**6*y**2 + x**3 + 1, x, y).deflate()
((3, 2), Poly(x**2*y + x + 1, x, y, domain='ZZ'))

degree(gen=0)[source]

Returns degree of self in x_j.

The degree of 0 is negative infinity.

Examples

>>> Poly(x**2 + y*x + 1, x, y).degree()
2
>>> Poly(x**2 + y*x + y, x, y).degree(y)
1
>>> Poly(0, x).degree()
-oo

degree_list()[source]

Returns a list of degrees of self.

Examples

>>> Poly(x**2 + y*x + 1, x, y).degree_list()
(2, 1)

diff(*specs, **kwargs)[source]

Computes partial derivative of self.

Examples

>>> Poly(x**2 + 2*x + 1, x).diff()
Poly(2*x + 2, x, domain='ZZ')

>>> Poly(x*y**2 + x, x, y).diff((0, 0), (1, 1))
Poly(2*x*y, x, y, domain='ZZ')

discriminant()[source]

Computes the discriminant of self.

Examples

>>> Poly(x**2 + 2*x + 3, x).discriminant()
-8

dispersion(other=None)[source]

Compute the dispersion of polynomials.

Examples

>>> Poly((x - 3)*(x + 3)).dispersion()
6


References

dispersionset(other=None)[source]

Compute the dispersion set of two polynomials.

Examples

>>> sorted(Poly((x - 3)*(x + 3)).dispersionset())
[0, 6]

div(other, auto=True)[source]

Polynomial division with remainder of self by other.

Examples

>>> Poly(x**2 + 1, x).div(Poly(2*x - 4, x))
(Poly(1/2*x + 1, x, domain='QQ'), Poly(5, x, domain='QQ'))

>>> Poly(x**2 + 1, x).div(Poly(2*x - 4, x), auto=False)
(Poly(0, x, domain='ZZ'), Poly(x**2 + 1, x, domain='ZZ'))

domain

Get the ground domain of self.

eject(*gens)[source]

Eject selected generators into the ground domain.

Examples

>>> f = Poly(x**2*y + x*y**3 + x*y + 1, x, y)

>>> f.eject(x)
Poly(x*y**3 + (x**2 + x)*y + 1, y, domain='ZZ[x]')
>>> f.eject(y)
Poly(y*x**2 + (y**3 + y)*x + 1, x, domain='ZZ[y]')

eval(x, a=None, auto=True)[source]

Evaluate self at a in the given variable.

Examples

>>> Poly(x**2 + 2*x + 3, x).eval(2)
11

>>> Poly(2*x*y + 3*x + y + 2, x, y).eval(x, 2)
Poly(5*y + 8, y, domain='ZZ')

>>> f = Poly(2*x*y + 3*x + y + 2*z, x, y, z)

>>> f.eval({x: 2})
Poly(5*y + 2*z + 6, y, z, domain='ZZ')
>>> f.eval({x: 2, y: 5})
Poly(2*z + 31, z, domain='ZZ')
>>> f.eval({x: 2, y: 5, z: 7})
45

>>> f.eval((2, 5))
Poly(2*z + 31, z, domain='ZZ')
>>> f(2, 5)
Poly(2*z + 31, z, domain='ZZ')

exclude()[source]

Remove unnecessary generators from self.

Examples

>>> Poly(a + x, a, b, c, d, x).exclude()
Poly(a + x, a, x, domain='ZZ')

exquo(other, auto=True)[source]

Computes polynomial exact quotient of self by other.

Examples

>>> Poly(x**2 - 1, x).exquo(Poly(x - 1, x))
Poly(x + 1, x, domain='ZZ')

>>> Poly(x**2 + 1, x).exquo(Poly(2*x - 4, x))
Traceback (most recent call last):
...
ExactQuotientFailed: 2*x - 4 does not divide x**2 + 1

exquo_ground(coeff)[source]

Exact quotient of self by a an element of the ground domain.

Examples

>>> Poly(2*x + 4).exquo_ground(2)
Poly(x + 2, x, domain='ZZ')

>>> Poly(2*x + 3).exquo_ground(2)
Traceback (most recent call last):
...
ExactQuotientFailed: 2 does not divide 3 in ZZ

factor_list()[source]

Returns a list of irreducible factors of self.

Examples

>>> f = 2*x**5 + 2*x**4*y + 4*x**3 + 4*x**2*y + 2*x + 2*y

>>> Poly(f).factor_list()
(2, [(Poly(x + y, x, y, domain='ZZ'), 1),
(Poly(x**2 + 1, x, y, domain='ZZ'), 2)])

free_symbols

Free symbols of a polynomial expression.

Examples

>>> Poly(x**2 + 1).free_symbols
{x}
>>> Poly(x**2 + y).free_symbols
{x, y}
>>> Poly(x**2 + y, x).free_symbols
{x, y}

free_symbols_in_domain

Free symbols of the domain of self.

Examples

>>> Poly(x**2 + 1).free_symbols_in_domain
set()
>>> Poly(x**2 + y).free_symbols_in_domain
set()
>>> Poly(x**2 + y, x).free_symbols_in_domain
{y}

classmethod from_dict(rep, *gens, **args)[source]

Construct a polynomial from a dict.

classmethod from_expr(rep, *gens, **args)[source]

Construct a polynomial from an expression.

classmethod from_list(rep, *gens, **args)[source]

Construct a polynomial from a list.

classmethod from_poly(rep, *gens, **args)[source]

Construct a polynomial from a polynomial.

gcd(other)[source]

Returns the polynomial GCD of self and other.

Examples

>>> Poly(x**2 - 1, x).gcd(Poly(x**2 - 3*x + 2, x))
Poly(x - 1, x, domain='ZZ')

gcdex(other, auto=True)[source]

Extended Euclidean algorithm of self and other.

Returns (s, t, h) such that h = gcd(f, g) and s*f + t*g = h.

Examples

>>> f = x**4 - 2*x**3 - 6*x**2 + 12*x + 15
>>> g = x**3 + x**2 - 4*x - 4

>>> Poly(f).gcdex(Poly(g))
(Poly(-1/5*x + 3/5, x, domain='QQ'),
Poly(1/5*x**2 - 6/5*x + 2, x, domain='QQ'),
Poly(x + 1, x, domain='QQ'))

gen

Return the principal generator.

Examples

>>> Poly(x**2 + 1, x).gen
x

get_modulus()[source]

Get the modulus of self.

Examples

>>> Poly(x**2 + 1, modulus=2).get_modulus()
2

ground_roots()[source]

Compute roots of self by factorization in the ground domain.

Examples

>>> Poly(x**6 - 4*x**4 + 4*x**3 - x**2).ground_roots()
{0: 2, 1: 2}

half_gcdex(other, auto=True)[source]

Half extended Euclidean algorithm of self and other.

Returns (s, h) such that h = gcd(f, g) and s*f = h (mod g).

Examples

>>> f = x**4 - 2*x**3 - 6*x**2 + 12*x + 15
>>> g = x**3 + x**2 - 4*x - 4

>>> Poly(f).half_gcdex(Poly(g))
(Poly(-1/5*x + 3/5, x, domain='QQ'), Poly(x + 1, x, domain='QQ'))

has_only_gens(*gens)[source]

Return True if Poly(f, *gens) retains ground domain.

Examples

>>> Poly(x*y + 1, x, y, z).has_only_gens(x, y)
True
>>> Poly(x*y + z, x, y, z).has_only_gens(x, y)
False

inject(front=False)[source]

Inject ground domain generators into self.

Examples

>>> f = Poly(x**2*y + x*y**3 + x*y + 1, x)

>>> f.inject()
Poly(x**2*y + x*y**3 + x*y + 1, x, y, domain='ZZ')
>>> f.inject(front=True)
Poly(y**3*x + y*x**2 + y*x + 1, y, x, domain='ZZ')

integrate(*specs, **args)[source]

Computes indefinite integral of self.

Examples

>>> Poly(x**2 + 2*x + 1, x).integrate()
Poly(1/3*x**3 + x**2 + x, x, domain='QQ')

>>> Poly(x*y**2 + x, x, y).integrate((0, 1), (1, 0))
Poly(1/2*x**2*y**2 + 1/2*x**2, x, y, domain='QQ')

intervals(all=False, eps=None, inf=None, sup=None, fast=False, sqf=False)[source]

Compute isolating intervals for roots of self.

For real roots the Vincent-Akritas-Strzebonski (VAS) continued fractions method is used.

References

Examples

>>> Poly(x**2 - 3, x).intervals()
[((-2, -1), 1), ((1, 2), 1)]
>>> Poly(x**2 - 3, x).intervals(eps=1e-2)
[((-26/15, -19/11), 1), ((19/11, 26/15), 1)]

invert(other, auto=True)[source]

Invert self modulo other when possible.

Examples

>>> Poly(x**2 - 1, x).invert(Poly(2*x - 1, x))
Poly(-4/3, x, domain='QQ')

>>> Poly(x**2 - 1, x).invert(Poly(x - 1, x))
Traceback (most recent call last):
...
NotInvertible: zero divisor

is_cyclotomic

Returns True if self is a cyclotomic polynomial.

Examples

>>> f = x**16 + x**14 - x**10 + x**8 - x**6 + x**2 + 1
>>> Poly(f).is_cyclotomic
False

>>> g = x**16 + x**14 - x**10 - x**8 - x**6 + x**2 + 1
>>> Poly(g).is_cyclotomic
True

is_ground

Returns True if self is an element of the ground domain.

Examples

>>> Poly(x, x).is_ground
False
>>> Poly(2, x).is_ground
True
>>> Poly(y, x).is_ground
True

is_homogeneous

Returns True if self is a homogeneous polynomial.

A homogeneous polynomial is a polynomial whose all monomials with non-zero coefficients have the same total degree.

Examples

>>> Poly(x**2 + x*y, x, y).is_homogeneous
True
>>> Poly(x**3 + x*y, x, y).is_homogeneous
False

is_irreducible

Returns True if self has no factors over its domain.

Examples

>>> Poly(x**2 + x + 1, x, modulus=2).is_irreducible
True
>>> Poly(x**2 + 1, x, modulus=2).is_irreducible
False

is_linear

Returns True if self is linear in all its variables.

Examples

>>> Poly(x + y + 2, x, y).is_linear
True
>>> Poly(x*y + 2, x, y).is_linear
False

is_monic

Returns True if the leading coefficient of self is one.

Examples

>>> Poly(x + 2, x).is_monic
True
>>> Poly(2*x + 2, x).is_monic
False

is_multivariate

Returns True if self is a multivariate polynomial.

Examples

>>> Poly(x**2 + x + 1, x).is_multivariate
False
>>> Poly(x*y**2 + x*y + 1, x, y).is_multivariate
True
>>> Poly(x*y**2 + x*y + 1, x).is_multivariate
False
>>> Poly(x**2 + x + 1, x, y).is_multivariate
True

is_one

Returns True if self is a unit polynomial.

Examples

>>> Poly(0, x).is_one
False
>>> Poly(1, x).is_one
True

is_primitive

Returns True if GCD of the coefficients of self is one.

Examples

>>> Poly(2*x**2 + 6*x + 12, x).is_primitive
False
>>> Poly(x**2 + 3*x + 6, x).is_primitive
True

is_quadratic

Returns True if self is quadratic in all its variables.

Examples

>>> Poly(x*y + 2, x, y).is_quadratic
True
>>> Poly(x*y**2 + 2, x, y).is_quadratic
False

is_squarefree

Returns True if self is a square-free polynomial.

Examples

>>> Poly(x**2 - 2*x + 1, x).is_squarefree
False
>>> Poly(x**2 - 1, x).is_squarefree
True

is_term

Returns True if self is zero or has only one term.

Examples

>>> Poly(3*x**2, x).is_term
True
>>> Poly(3*x**2 + 1, x).is_term
False

is_univariate

Returns True if self is a univariate polynomial.

Examples

>>> Poly(x**2 + x + 1, x).is_univariate
True
>>> Poly(x*y**2 + x*y + 1, x, y).is_univariate
False
>>> Poly(x*y**2 + x*y + 1, x).is_univariate
True
>>> Poly(x**2 + x + 1, x, y).is_univariate
False

is_zero

Returns True if self is a zero polynomial.

Examples

>>> Poly(0, x).is_zero
True
>>> Poly(1, x).is_zero
False

l1_norm()[source]

Returns l1 norm of self.

Examples

>>> Poly(-x**2 + 2*x - 3, x).l1_norm()
6

lcm(other)[source]

Returns polynomial LCM of self and other.

Examples

>>> Poly(x**2 - 1, x).lcm(Poly(x**2 - 3*x + 2, x))
Poly(x**3 - 2*x**2 - x + 2, x, domain='ZZ')

length()[source]

Returns the number of non-zero terms in self.

Examples

>>> Poly(x**2 + 2*x - 1).length()
3

ltrim(gen)[source]

Remove dummy generators from the “left” of self.

Examples

>>> Poly(y**2 + y*z**2, x, y, z).ltrim(y)
Poly(y**2 + y*z**2, y, z, domain='ZZ')

max_norm()[source]

Returns maximum norm of self.

Examples

>>> Poly(-x**2 + 2*x - 3, x).max_norm()
3

monic(auto=True)[source]

Divides all coefficients by LC(f).

Examples

>>> Poly(3*x**2 + 6*x + 9).monic()
Poly(x**2 + 2*x + 3, x, domain='QQ')

>>> Poly(3*x**2 + 4*x + 2).monic()
Poly(x**2 + 4/3*x + 2/3, x, domain='QQ')

monoms(order=None)[source]

Returns all non-zero monomials from self in lex order.

Examples

>>> Poly(x**2 + 2*x*y**2 + x*y + 3*y, x, y).monoms()
[(2, 0), (1, 2), (1, 1), (0, 1)]

classmethod new(rep, *gens)[source]

Construct Poly instance from raw representation.

nroots(n=15, maxsteps=50, cleanup=True)[source]

Compute numerical approximations of roots of self.

Parameters: n … the number of digits to calculate maxsteps … the maximum number of iterations to do If the accuracy n cannot be reached in maxsteps, it will raise an exception. You need to rerun with higher maxsteps.

Examples

>>> Poly(x**2 - 3).nroots(n=15)
[-1.73205080756888, 1.73205080756888]
>>> Poly(x**2 - 3).nroots(n=30)
[-1.73205080756887729352744634151, 1.73205080756887729352744634151]

nth_power_roots_poly(n)[source]

Construct a polynomial with n-th powers of roots of self.

Examples

>>> f = Poly(x**4 - x**2 + 1)

>>> f.nth_power_roots_poly(2)
Poly(x**4 - 2*x**3 + 3*x**2 - 2*x + 1, x, domain='ZZ')
>>> f.nth_power_roots_poly(3)
Poly(x**4 + 2*x**2 + 1, x, domain='ZZ')
>>> f.nth_power_roots_poly(4)
Poly(x**4 + 2*x**3 + 3*x**2 + 2*x + 1, x, domain='ZZ')
>>> f.nth_power_roots_poly(12)
Poly(x**4 - 4*x**3 + 6*x**2 - 4*x + 1, x, domain='ZZ')

one

Return one polynomial with self’s properties.

pdiv(other)[source]

Polynomial pseudo-division of self by other.

Examples

>>> Poly(x**2 + 1, x).pdiv(Poly(2*x - 4, x))
(Poly(2*x + 4, x, domain='ZZ'), Poly(20, x, domain='ZZ'))

per(rep, gens=None, remove=None)[source]

Create a Poly out of the given representation.

Examples

>>> a = Poly(x**2 + 1)
>>> R = ZZ.poly_ring(x)

>>> a.per(R.from_dense([ZZ(1), ZZ(1)]), gens=[y])
Poly(y + 1, y, domain='ZZ')

pexquo(other)[source]

Polynomial exact pseudo-quotient of self by other.

Examples

>>> Poly(x**2 - 1, x).pexquo(Poly(2*x - 2, x))
Poly(2*x + 2, x, domain='ZZ')

>>> Poly(x**2 + 1, x).pexquo(Poly(2*x - 4, x))
Traceback (most recent call last):
...
ExactQuotientFailed: 2*x - 4 does not divide x**2 + 1

pquo(other)[source]

Polynomial pseudo-quotient of self by other.

Examples

>>> Poly(x**2 + 1, x).pquo(Poly(2*x - 4, x))
Poly(2*x + 4, x, domain='ZZ')

>>> Poly(x**2 - 1, x).pquo(Poly(2*x - 2, x))
Poly(2*x + 2, x, domain='ZZ')

prem(other)[source]

Polynomial pseudo-remainder of self by other.

Examples

>>> Poly(x**2 + 1, x).prem(Poly(2*x - 4, x))
Poly(20, x, domain='ZZ')

primitive()[source]

Returns the content and a primitive form of self.

Examples

>>> Poly(2*x**2 + 8*x + 12, x).primitive()
(2, Poly(x**2 + 4*x + 6, x, domain='ZZ'))

quo(other, auto=True)[source]

Computes polynomial quotient of self by other.

Examples

>>> Poly(x**2 + 1, x).quo(Poly(2*x - 4, x))
Poly(1/2*x + 1, x, domain='QQ')

>>> Poly(x**2 - 1, x).quo(Poly(x - 1, x))
Poly(x + 1, x, domain='ZZ')

quo_ground(coeff)[source]

Quotient of self by a an element of the ground domain.

Examples

>>> Poly(2*x + 4).quo_ground(2)
Poly(x + 2, x, domain='ZZ')

>>> Poly(2*x + 3).quo_ground(2)
Poly(x + 1, x, domain='ZZ')

rat_clear_denoms(other)[source]

Clear denominators in a rational function self/other.

Examples

>>> f = Poly(x**2/y + 1, x)
>>> g = Poly(x**3 + y, x)

>>> p, q = f.rat_clear_denoms(g)

>>> p
Poly(x**2 + y, x, domain='ZZ[y]')
>>> q
Poly(y*x**3 + y**2, x, domain='ZZ[y]')

real_roots(multiple=True, radicals=True)[source]

Return a list of real roots with multiplicities.

Examples

>>> Poly(2*x**3 - 7*x**2 + 4*x + 4).real_roots()
[-1/2, 2, 2]
>>> Poly(x**3 + x + 1).real_roots()
[RootOf(x**3 + x + 1, 0)]

refine_root(s, t, eps=None, steps=None, fast=False, check_sqf=False)[source]

Refine an isolating interval of a root to the given precision.

Examples

>>> Poly(x**2 - 3, x).refine_root(1, 2, eps=1e-2)
(19/11, 26/15)

rem(other, auto=True)[source]

Computes the polynomial remainder of self by other.

Examples

>>> Poly(x**2 + 1, x).rem(Poly(2*x - 4, x))
Poly(5, x, domain='ZZ')

>>> Poly(x**2 + 1, x).rem(Poly(2*x - 4, x), auto=False)
Poly(x**2 + 1, x, domain='ZZ')

reorder(*gens, **args)[source]

Efficiently apply new order of generators.

Examples

>>> Poly(x**2 + x*y**2, x, y).reorder(y, x)
Poly(y**2*x + x**2, y, x, domain='ZZ')

replace(x, y=None)[source]

Replace x with y in generators list.

Examples

>>> Poly(x**2 + 1, x).replace(x, y)
Poly(y**2 + 1, y, domain='ZZ')

resultant(other, includePRS=False)[source]

Computes the resultant of self and other via PRS.

If includePRS=True, it includes the subresultant PRS in the result. Because the PRS is used to calculate the resultant, this is more efficient than calling subresultants() separately.

Examples

>>> f = Poly(x**2 + 1, x)

>>> f.resultant(Poly(x**2 - 1, x))
4
>>> f.resultant(Poly(x**2 - 1, x), includePRS=True)
(4, [Poly(x**2 + 1, x, domain='ZZ'), Poly(x**2 - 1, x, domain='ZZ'),
Poly(-2, x, domain='ZZ')])

retract(field=None)[source]

Recalculate the ground domain of a polynomial.

Examples

>>> f = Poly(x**2 + 1, domain=QQ.poly_ring(y))
>>> f
Poly(x**2 + 1, x, domain='QQ[y]')

>>> f.retract()
Poly(x**2 + 1, x, domain='ZZ')
>>> f.retract(field=True)
Poly(x**2 + 1, x, domain='QQ')

root(index, radicals=True)[source]

Get an indexed root of a polynomial.

Examples

>>> f = Poly(2*x**3 - 7*x**2 + 4*x + 4)

>>> f.root(0)
-1/2
>>> f.root(1)
2
>>> f.root(2)
2
>>> f.root(3)
Traceback (most recent call last):
...
IndexError: root index out of [-3, 2] range, got 3

>>> Poly(x**5 + x + 1).root(0)
RootOf(x**3 - x**2 + 1, 0)

set_domain(domain)[source]

Set the ground domain of self.

set_modulus(modulus)[source]

Set the modulus of self.

Examples

>>> Poly(5*x**2 + 2*x - 1, x).set_modulus(2)
Poly(x**2 + 1, x, modulus=2)

shift(a)[source]

Efficiently compute Taylor shift f(x + a).

Examples

>>> Poly(x**2 - 2*x + 1, x).shift(2)
Poly(x**2 + 2*x + 1, x, domain='ZZ')

slice(x, m, n=None)[source]

Take a continuous subsequence of terms of self.

sqf_list()[source]

Returns a list of square-free factors of self.

Examples

>>> f = 2*x**5 + 16*x**4 + 50*x**3 + 76*x**2 + 56*x + 16

>>> Poly(f).sqf_list()
(2, [(Poly(x + 1, x, domain='ZZ'), 2),
(Poly(x + 2, x, domain='ZZ'), 3)])

sqf_norm()[source]

Computes square-free norm of self.

Returns s, f, r, such that g(x) = f(x-sa) and r(x) = Norm(g(x)) is a square-free polynomial over K, where a is the algebraic extension of the ground domain.

Examples

>>> s, f, r = Poly(x**2 + 1, x, extension=[sqrt(3)]).sqf_norm()

>>> s
1
>>> f
Poly(x**2 - 2*sqrt(3)*x + 4, x, domain='QQ<sqrt(3)>')
>>> r
Poly(x**4 - 4*x**2 + 16, x, domain='QQ')

sqf_part()[source]

Computes square-free part of self.

Examples

>>> Poly(x**3 - 3*x - 2, x).sqf_part()
Poly(x**2 - x - 2, x, domain='ZZ')

sturm(auto=True)[source]

Computes the Sturm sequence of self.

Examples

>>> Poly(x**3 - 2*x**2 + x - 3, x).sturm()
[Poly(x**3 - 2*x**2 + x - 3, x, domain='QQ'),
Poly(3*x**2 - 4*x + 1, x, domain='QQ'),
Poly(2/9*x + 25/9, x, domain='QQ'),
Poly(-2079/4, x, domain='QQ')]

subresultants(other)[source]

Computes the subresultant PRS of self and other.

Examples

>>> Poly(x**2 + 1, x).subresultants(Poly(x**2 - 1, x))
[Poly(x**2 + 1, x, domain='ZZ'),
Poly(x**2 - 1, x, domain='ZZ'),
Poly(-2, x, domain='ZZ')]

terms(order=None)[source]

Returns all non-zero terms from self in lex order.

Examples

>>> Poly(x**2 + 2*x*y**2 + x*y + 3*y, x, y).terms()
[((2, 0), 1), ((1, 2), 2), ((1, 1), 1), ((0, 1), 3)]

terms_gcd()[source]

Remove GCD of terms from the polynomial self.

Examples

>>> Poly(x**6*y**2 + x**3*y, x, y).terms_gcd()
((3, 1), Poly(x**3*y + 1, x, y, domain='ZZ'))

termwise(func, *gens, **args)[source]

Apply a function to all terms of self.

Examples

>>> def func(k, coeff):
...     k = k[0]
...     return coeff//10**(2-k)

>>> Poly(x**2 + 20*x + 400).termwise(func)
Poly(x**2 + 2*x + 4, x, domain='ZZ')

to_exact()[source]

Make the ground domain exact.

Examples

>>> Poly(x**2 + 1.0).to_exact()
Poly(x**2 + 1, x, domain='QQ')

to_field()[source]

Make the ground domain a field.

Examples

>>> Poly(x**2 + 1).to_field()
Poly(x**2 + 1, x, domain='QQ')

to_ring()[source]

Make the ground domain a ring.

Examples

>>> Poly(x**2 + 1, field=True).to_ring()
Poly(x**2 + 1, x, domain='ZZ')

total_degree()[source]

Returns the total degree of self.

Examples

>>> Poly(x**2 + y*x + 1, x, y).total_degree()
2
>>> Poly(x + y**5, x, y).total_degree()
5

trunc(p)[source]

Reduce self modulo a constant p.

Examples

>>> Poly(2*x**3 + 3*x**2 + 5*x + 7, x).trunc(3)
Poly(-x**3 - x + 1, x, domain='ZZ')

unify(other)[source]

Make self and other belong to the same domain.

Examples

>>> f, g = Poly(x/2 + 1), Poly(2*x + 1)

>>> f
Poly(1/2*x + 1, x, domain='QQ')
>>> g
Poly(2*x + 1, x, domain='ZZ')

>>> F, G = f.unify(g)

>>> F
Poly(1/2*x + 1, x, domain='QQ')
>>> G
Poly(2*x + 1, x, domain='QQ')

unit

Return unit polynomial with self’s properties.

zero

Return zero polynomial with self’s properties.

class diofant.polys.polytools.PurePoly[source]

Class for representing pure polynomials.

free_symbols

Free symbols of a polynomial.

Examples

>>> PurePoly(x**2 + 1).free_symbols
set()
>>> PurePoly(x**2 + y).free_symbols
set()
>>> PurePoly(x**2 + y, x).free_symbols
{y}

diofant.polys.polytools.poly_from_expr(expr, *gens, **args)[source]

Construct a polynomial from an expression.

diofant.polys.polytools.parallel_poly_from_expr(exprs, *gens, **args)[source]

Construct polynomials from expressions.

diofant.polys.polytools.degree(f, *gens, **args)[source]

Return the degree of f in the given variable.

The degree of 0 is negative infinity.

Examples

>>> degree(x**2 + y*x + 1, gen=x)
2
>>> degree(x**2 + y*x + 1, gen=y)
1
>>> degree(0, x)
-oo

diofant.polys.polytools.degree_list(f, *gens, **args)[source]

Return a list of degrees of f in all variables.

Examples

>>> degree_list(x**2 + y*x + 1)
(2, 1)

diofant.polys.polytools.LC(f, *gens, **args)[source]

Return the leading coefficient of f.

Examples

>>> LC(4*x**2 + 2*x*y**2 + x*y + 3*y)
4

diofant.polys.polytools.LM(f, *gens, **args)[source]

Return the leading monomial of f.

Examples

>>> LM(4*x**2 + 2*x*y**2 + x*y + 3*y)
x**2

diofant.polys.polytools.LT(f, *gens, **args)[source]

Return the leading term of f.

Examples

>>> LT(4*x**2 + 2*x*y**2 + x*y + 3*y)
4*x**2

diofant.polys.polytools.pdiv(f, g, *gens, **args)[source]

Compute polynomial pseudo-division of f and g.

Examples

>>> pdiv(x**2 + 1, 2*x - 4)
(2*x + 4, 20)

diofant.polys.polytools.prem(f, g, *gens, **args)[source]

Compute polynomial pseudo-remainder of f and g.

Examples

>>> prem(x**2 + 1, 2*x - 4)
20

diofant.polys.polytools.pquo(f, g, *gens, **args)[source]

Compute polynomial pseudo-quotient of f and g.

Examples

>>> pquo(x**2 + 1, 2*x - 4)
2*x + 4
>>> pquo(x**2 - 1, 2*x - 1)
2*x + 1

diofant.polys.polytools.pexquo(f, g, *gens, **args)[source]

Compute polynomial exact pseudo-quotient of f and g.

Examples

>>> pexquo(x**2 - 1, 2*x - 2)
2*x + 2

>>> pexquo(x**2 + 1, 2*x - 4)
Traceback (most recent call last):
...
ExactQuotientFailed: 2*x - 4 does not divide x**2 + 1

diofant.polys.polytools.div(f, g, *gens, **args)[source]

Compute polynomial division of f and g.

Examples

>>> div(x**2 + 1, 2*x - 4, field=False)
(0, x**2 + 1)
>>> div(x**2 + 1, 2*x - 4)
(x/2 + 1, 5)

diofant.polys.polytools.rem(f, g, *gens, **args)[source]

Compute polynomial remainder of f and g.

Examples

>>> rem(x**2 + 1, 2*x - 4, field=False)
x**2 + 1
>>> rem(x**2 + 1, 2*x - 4)
5

diofant.polys.polytools.quo(f, g, *gens, **args)[source]

Compute polynomial quotient of f and g.

Examples

>>> quo(x**2 + 1, 2*x - 4)
x/2 + 1
>>> quo(x**2 - 1, x - 1)
x + 1

diofant.polys.polytools.exquo(f, g, *gens, **args)[source]

Compute polynomial exact quotient of f and g.

Examples

>>> exquo(x**2 - 1, x - 1)
x + 1

>>> exquo(x**2 + 1, 2*x - 4)
Traceback (most recent call last):
...
ExactQuotientFailed: 2*x - 4 does not divide x**2 + 1

diofant.polys.polytools.half_gcdex(f, g, *gens, **args)[source]

Half extended Euclidean algorithm of f and g.

Returns (s, h) such that h = gcd(f, g) and s*f = h (mod g).

Examples

>>> half_gcdex(x**4 - 2*x**3 - 6*x**2 + 12*x + 15, x**3 + x**2 - 4*x - 4)
(-x/5 + 3/5, x + 1)

diofant.polys.polytools.gcdex(f, g, *gens, **args)[source]

Extended Euclidean algorithm of f and g.

Returns (s, t, h) such that h = gcd(f, g) and s*f + t*g = h.

Examples

>>> gcdex(x**4 - 2*x**3 - 6*x**2 + 12*x + 15, x**3 + x**2 - 4*x - 4)
(-x/5 + 3/5, x**2/5 - 6*x/5 + 2, x + 1)

diofant.polys.polytools.invert(f, g, *gens, **args)[source]

Invert f modulo g when possible.

Examples

>>> invert(x**2 - 1, 2*x - 1)
-4/3

>>> invert(x**2 - 1, x - 1)
Traceback (most recent call last):
...
NotInvertible: zero divisor


For more efficient inversion of Rationals, use the mod_inverse function:

>>> mod_inverse(3, 5)
2
>>> (Integer(2)/5).invert(Integer(7)/3)
5/2

diofant.polys.polytools.subresultants(f, g, *gens, **args)[source]

Compute subresultant PRS of f and g.

Examples

>>> subresultants(x**2 + 1, x**2 - 1)
[x**2 + 1, x**2 - 1, -2]

diofant.polys.polytools.resultant(f, g, *gens, **args)[source]

Compute resultant of f and g.

Examples

>>> resultant(x**2 + 1, x**2 - 1)
4

diofant.polys.polytools.discriminant(f, *gens, **args)[source]

Compute discriminant of f.

Examples

>>> discriminant(x**2 + 2*x + 3)
-8

diofant.polys.polytools.cofactors(f, g, *gens, **args)[source]

Compute GCD and cofactors of f and g.

Returns polynomials (h, cff, cfg) such that h = gcd(f, g), and cff = quo(f, h) and cfg = quo(g, h) are, so called, cofactors of f and g.

Examples

>>> cofactors(x**2 - 1, x**2 - 3*x + 2)
(x - 1, x + 1, x - 2)

diofant.polys.polytools.gcd_list(seq, *gens, **args)[source]

Compute GCD of a list of polynomials.

Examples

>>> gcd_list([x**3 - 1, x**2 - 1, x**2 - 3*x + 2])
x - 1

diofant.polys.polytools.gcd(f, g, *gens, **args)[source]

Compute GCD of f and g.

Examples

>>> gcd(x**2 - 1, x**2 - 3*x + 2)
x - 1

diofant.polys.polytools.lcm_list(seq, *gens, **args)[source]

Compute LCM of a list of polynomials.

Examples

>>> lcm_list([x**3 - 1, x**2 - 1, x**2 - 3*x + 2])
x**5 - x**4 - 2*x**3 - x**2 + x + 2

diofant.polys.polytools.lcm(f, g, *gens, **args)[source]

Compute LCM of f and g.

Examples

>>> lcm(x**2 - 1, x**2 - 3*x + 2)
x**3 - 2*x**2 - x + 2

diofant.polys.polytools.terms_gcd(f, *gens, **args)[source]

Remove GCD of terms from f.

If the deep flag is True, then the arguments of f will have terms_gcd applied to them.

If a fraction is factored out of f and f is an Add, then an unevaluated Mul will be returned so that automatic simplification does not redistribute it. The hint clear, when set to False, can be used to prevent such factoring when all coefficients are not fractions.

Examples

>>> terms_gcd(x**6*y**2 + x**3*y, x, y)
x**3*y*(x**3*y + 1)


The default action of polys routines is to expand the expression given to them. terms_gcd follows this behavior:

>>> terms_gcd((3+3*x)*(x+x*y))
3*x*(x*y + x + y + 1)


If this is not desired then the hint expand can be set to False. In this case the expression will be treated as though it were comprised of one or more terms:

>>> terms_gcd((3+3*x)*(x+x*y), expand=False)
(3*x + 3)*(x*y + x)


In order to traverse factors of a Mul or the arguments of other functions, the deep hint can be used:

>>> terms_gcd((3 + 3*x)*(x + x*y), expand=False, deep=True)
3*x*(x + 1)*(y + 1)
>>> terms_gcd(cos(x + x*y), deep=True)
cos(x*(y + 1))


Rationals are factored out by default:

>>> terms_gcd(x + y/2)
(2*x + y)/2


Only the y-term had a coefficient that was a fraction; if one does not want to factor out the 1/2 in cases like this, the flag clear can be set to False:

>>> terms_gcd(x + y/2, clear=False)
x + y/2
>>> terms_gcd(x*y/2 + y**2, clear=False)
y*(x/2 + y)


The clear flag is ignored if all coefficients are fractions:

>>> terms_gcd(x/3 + y/2, clear=False)
(2*x + 3*y)/6

diofant.polys.polytools.trunc(f, p, *gens, **args)[source]

Reduce f modulo a constant p.

Examples

>>> trunc(2*x**3 + 3*x**2 + 5*x + 7, 3)
-x**3 - x + 1

diofant.polys.polytools.monic(f, *gens, **args)[source]

Divide all coefficients of f by LC(f).

Examples

>>> monic(3*x**2 + 4*x + 2)
x**2 + 4*x/3 + 2/3

diofant.polys.polytools.content(f, *gens, **args)[source]

Compute GCD of coefficients of f.

Examples

>>> content(6*x**2 + 8*x + 12)
2

diofant.polys.polytools.primitive(f, *gens, **args)[source]

Compute content and the primitive form of f.

Examples

>>> primitive(6*x**2 + 8*x + 12)
(2, 3*x**2 + 4*x + 6)

>>> eq = (2 + 2*x)*x + 2


Expansion is performed by default:

>>> primitive(eq)
(2, x**2 + x + 1)


Set expand to False to shut this off. Note that the extraction will not be recursive; use the as_content_primitive method for recursive, non-destructive Rational extraction.

>>> primitive(eq, expand=False)
(1, x*(2*x + 2) + 2)

>>> eq.as_content_primitive()
(2, x*(x + 1) + 1)

diofant.polys.polytools.compose(f, g, *gens, **args)[source]

Compute functional composition f(g).

Examples

>>> compose(x**2 + x, x - 1)
x**2 - x

diofant.polys.polytools.decompose(f, *gens, **args)[source]

Compute functional decomposition of f.

Examples

>>> decompose(x**4 + 2*x**3 - x - 1)
[x**2 - x - 1, x**2 + x]

diofant.polys.polytools.sturm(f, *gens, **args)[source]

Compute Sturm sequence of f.

Examples

>>> sturm(x**3 - 2*x**2 + x - 3)
[x**3 - 2*x**2 + x - 3, 3*x**2 - 4*x + 1, 2*x/9 + 25/9, -2079/4]

diofant.polys.polytools.sqf_norm(f, *gens, **args)[source]

Compute square-free norm of f.

Returns s, f, r, such that g(x) = f(x-sa) and r(x) = Norm(g(x)) is a square-free polynomial over K, where a is the algebraic extension of the ground domain.

Examples

>>> sqf_norm(x**2 + 1, extension=[sqrt(3)])
(1, x**2 - 2*sqrt(3)*x + 4, x**4 - 4*x**2 + 16)

diofant.polys.polytools.sqf_part(f, *gens, **args)[source]

Compute square-free part of f.

Examples

>>> sqf_part(x**3 - 3*x - 2)
x**2 - x - 2

diofant.polys.polytools.sqf_list(f, *gens, **args)[source]

Compute a list of square-free factors of f.

Examples

>>> sqf_list(2*x**5 + 16*x**4 + 50*x**3 + 76*x**2 + 56*x + 16)
(2, [(x + 1, 2), (x + 2, 3)])

diofant.polys.polytools.sqf(f, *gens, **args)[source]

Compute square-free factorization of f.

Examples

>>> sqf(2*x**5 + 16*x**4 + 50*x**3 + 76*x**2 + 56*x + 16)
2*(x + 1)**2*(x + 2)**3

diofant.polys.polytools.factor_list(f, *gens, **args)[source]

Compute a list of irreducible factors of f.

Examples

>>> factor_list(2*x**5 + 2*x**4*y + 4*x**3 + 4*x**2*y + 2*x + 2*y)
(2, [(x + y, 1), (x**2 + 1, 2)])

diofant.polys.polytools.factor(f, *gens, **args)[source]

Compute the factorization of expression, f, into irreducibles. (To factor an integer into primes, use factorint.)

There two modes implemented: symbolic and formal. If f is not an instance of Poly and generators are not specified, then the former mode is used. Otherwise, the formal mode is used.

In symbolic mode, factor() will traverse the expression tree and factor its components without any prior expansion, unless an instance of Add is encountered (in this case formal factorization is used). This way factor() can handle large or symbolic exponents.

By default, the factorization is computed over the rationals. To factor over other domain, e.g. an algebraic or finite field, use appropriate options: extension, modulus or domain.

Examples

>>> factor(2*x**5 + 2*x**4*y + 4*x**3 + 4*x**2*y + 2*x + 2*y)
2*(x + y)*(x**2 + 1)**2

>>> factor(x**2 + 1)
x**2 + 1
>>> factor(x**2 + 1, modulus=2)
(x + 1)**2
>>> factor(x**2 + 1, gaussian=True)
(x - I)*(x + I)

>>> factor(x**2 - 2, extension=sqrt(2))
(x - sqrt(2))*(x + sqrt(2))

>>> factor((x**2 - 1)/(x**2 + 4*x + 4))
(x - 1)*(x + 1)/(x + 2)**2
>>> factor((x**2 + 4*x + 4)**10000000*(x**2 + 1))
(x + 2)**20000000*(x**2 + 1)


By default, factor deals with an expression as a whole:

>>> eq = 2**(x**2 + 2*x + 1)
>>> factor(eq)
2**(x**2 + 2*x + 1)


If the deep flag is True then subexpressions will be factored:

>>> factor(eq, deep=True)
2**((x + 1)**2)

diofant.polys.polytools.intervals(F, all=False, eps=None, inf=None, sup=None, strict=False, fast=False, sqf=False)[source]

Compute isolating intervals for roots of f.

Examples

>>> intervals(x**2 - 3)
[((-2, -1), 1), ((1, 2), 1)]
>>> intervals(x**2 - 3, eps=1e-2)
[((-26/15, -19/11), 1), ((19/11, 26/15), 1)]

diofant.polys.polytools.refine_root(f, s, t, eps=None, steps=None, fast=False, check_sqf=False)[source]

Refine an isolating interval of a root to the given precision.

Examples

>>> refine_root(x**2 - 3, 1, 2, eps=1e-2)
(19/11, 26/15)

diofant.polys.polytools.count_roots(f, inf=None, sup=None)[source]

Return the number of roots of f in [inf, sup] interval.

If one of inf or sup is complex, it will return the number of roots in the complex rectangle with corners at inf and sup.

Examples

>>> count_roots(x**4 - 4, -3, 3)
2
>>> count_roots(x**4 - 4, 0, 1 + 3*I)
1

diofant.polys.polytools.real_roots(f, multiple=True)[source]

Return a list of real roots with multiplicities of f.

Examples

>>> real_roots(2*x**3 - 7*x**2 + 4*x + 4)
[-1/2, 2, 2]

diofant.polys.polytools.nroots(f, n=15, maxsteps=50, cleanup=True)[source]

Compute numerical approximations of roots of f.

Examples

>>> nroots(x**2 - 3, n=15)
[-1.73205080756888, 1.73205080756888]
>>> nroots(x**2 - 3, n=30)
[-1.73205080756887729352744634151, 1.73205080756887729352744634151]

diofant.polys.polytools.ground_roots(f, *gens, **args)[source]

Compute roots of f by factorization in the ground domain.

Examples

>>> ground_roots(x**6 - 4*x**4 + 4*x**3 - x**2)
{0: 2, 1: 2}

diofant.polys.polytools.nth_power_roots_poly(f, n, *gens, **args)[source]

Construct a polynomial with n-th powers of roots of f.

Examples

>>> f = x**4 - x**2 + 1
>>> g = factor(nth_power_roots_poly(f, 2))

>>> g
(x**2 - x + 1)**2

>>> R_f = [(r**2).expand() for r in roots(f)]
>>> R_g = roots(g)

>>> set(R_f) == set(R_g)
True

diofant.polys.polytools.cancel(f, *gens, **args)[source]

Cancel common factors in a rational function f.

Examples

>>> A = Symbol('A', commutative=False)

>>> cancel((2*x**2 - 2)/(x**2 - 2*x + 1))
(2*x + 2)/(x - 1)
>>> cancel((sqrt(3) + sqrt(15)*A)/(sqrt(2) + sqrt(10)*A))
sqrt(6)/2

diofant.polys.polytools.reduced(f, G, *gens, **args)[source]

Reduces a polynomial f modulo a set of polynomials G.

Given a polynomial f and a set of polynomials G = (g_1, ..., g_n), computes a set of quotients q = (q_1, ..., q_n) and the remainder r such that f = q_1*g_1 + ... + q_n*g_n + r, where r vanishes or r is a completely reduced polynomial with respect to G.

Examples

>>> reduced(2*x**4 + y**2 - x**2 + y**3, [x**3 - x, y**3 - y])
([2*x, 1], x**2 + y**2 + y)

diofant.polys.polytools.groebner(F, *gens, **args)[source]

Computes the reduced Gröbner basis for a set of polynomials.

Parameters: F (list) – a set of polynomials *gens (tuple) – polynomial generators **args (dict) – a dictionary of parameters, namely order : str, optional Monomial order, defaults to lex. method : {‘buchberger’, ‘f5b’}, optional Set algorithm to compute Gröbner basis. By default, an improved implementation of the Buchberger algorithm is used. field : bool, optional Force coefficients domain to be a field. Defaults to False.

Examples

>>> F = [x*y - 2*x, 2*x**2 - y**2]

>>> groebner(F)
GroebnerBasis([2*x**2 - y**2, x*y - 2*x, y**3 - 2*y**2],
x, y, domain='ZZ', order='lex')

>>> groebner(F, order=grevlex)
GroebnerBasis([y**3 - 2*y**2, 2*x**2 - y**2, x*y - 2*x],
x, y, domain='ZZ', order='grevlex')

>>> groebner(F, field=True)
GroebnerBasis([x**2 - y**2/2, x*y - 2*x, y**3 - 2*y**2],
x, y, domain='QQ', order='lex')


References

class diofant.polys.polytools.GroebnerBasis[source]

Represents a reduced Gröbner basis.

contains(poly)[source]

Check if poly belongs the ideal generated by self.

Examples

>>> f = 2*x**3 + y**3 + 3*y
>>> G = groebner([x**2 + y**2 - 1, x*y - 2])

>>> G.contains(f)
True
>>> G.contains(f + 1)
False

dimension

Dimension of the ideal, generated by a Gröbner basis.

independent_sets

Compute independent sets for ideal, generated by a Gröbner basis.

References

reduce(expr, auto=True)[source]

Reduces a polynomial modulo a Gröbner basis.

Given a polynomial f and a set of polynomials G = (g_1, ..., g_n), computes a set of quotients q = (q_1, ..., q_n) and the remainder r such that f = q_1*f_1 + ... + q_n*f_n + r, where r vanishes or r is a completely reduced polynomial with respect to G.

Examples

>>> f = 2*x**4 - x**2 + y**3 + y**2
>>> G = groebner([x**3 - x, y**3 - y])

>>> G.reduce(f)
([2*x, 1], x**2 + y**2 + y)
>>> Q, r = _

>>> expand(sum(q*g for q, g in zip(Q, G)) + r)
2*x**4 - x**2 + y**3 + y**2
>>> _ == f
True

set_order(order)[source]

Convert a Gröbner basis from one ordering to another.

Notes

The FGLM algorithm [FaugereGLM93] used to convert reduced Gröbner bases of zero-dimensional ideals from one ordering to another. Sometimes it is infeasible to compute a Gröbner basis with respect to a particular ordering directly.

Examples

>>> F = [x**2 - 3*y - x + 1, y**2 - 2*x + y - 1]
>>> G = groebner(F, x, y, order='grlex')

>>> G.set_order('lex') == groebner(F, x, y, order='lex')
True

diofant.polys.polytools.poly(expr, *gens, **args)[source]

Efficiently transform an expression into a polynomial.

Examples

>>> poly(x*(x**2 + x - 1)**2)
Poly(x**5 + 2*x**4 - x**3 - 2*x**2 + x, x, domain='ZZ')


Extra polynomial manipulation functions¶

High-level polynomials manipulation functions.

diofant.polys.polyfuncs.symmetrize(F, *gens, **args)[source]

Rewrite a polynomial in terms of elementary symmetric polynomials.

A symmetric polynomial is a multivariate polynomial that remains invariant under any variable permutation, i.e., if f = f(x_1, x_2, ..., x_n), then f = f(x_{i_1}, x_{i_2}, ..., x_{i_n}), where (i_1, i_2, ..., i_n) is a permutation of (1, 2, ..., n) (an element of the group S_n).

Returns a tuple of symmetric polynomials (f1, f2, ..., fn) such that f = f1 + f2 + ... + fn.

Examples

>>> symmetrize(x**2 + y**2)
(-2*x*y + (x + y)**2, 0)

>>> symmetrize(x**2 + y**2, formal=True)
(s1**2 - 2*s2, 0, [(s1, x + y), (s2, x*y)])

>>> symmetrize(x**2 - y**2)
(-2*x*y + (x + y)**2, -2*y**2)

>>> symmetrize(x**2 - y**2, formal=True)
(s1**2 - 2*s2, -2*y**2, [(s1, x + y), (s2, x*y)])

diofant.polys.polyfuncs.horner(f, *gens, **args)[source]

Rewrite a polynomial in Horner form.

Among other applications, evaluation of a polynomial at a point is optimal when it is applied using the Horner scheme.

Examples

>>> from diofant.abc import e

>>> horner(9*x**4 + 8*x**3 + 7*x**2 + 6*x + 5)
x*(x*(x*(9*x + 8) + 7) + 6) + 5

>>> horner(a*x**4 + b*x**3 + c*x**2 + d*x + e)
e + x*(d + x*(c + x*(a*x + b)))

>>> f = 4*x**2*y**2 + 2*x**2*y + 2*x*y**2 + x*y

>>> horner(f, wrt=x)
x*(x*y*(4*y + 2) + y*(2*y + 1))

>>> horner(f, wrt=y)
y*(x*y*(4*x + 2) + x*(2*x + 1))


References

diofant.polys.polyfuncs.interpolate(data, x)[source]

Construct an interpolating polynomial for the data points.

Examples

A list is interpreted as though it were paired with a range starting from 1:

>>> interpolate([1, 4, 9, 16], x)
x**2


This can be made explicit by giving a list of coordinates:

>>> interpolate([(1, 1), (2, 4), (3, 9)], x)
x**2


The (x, y) coordinates can also be given as keys and values of a dictionary (and the points need not be equispaced):

>>> interpolate([(-1, 2), (1, 2), (2, 5)], x)
x**2 + 1
>>> interpolate({-1: 2, 1: 2, 2: 5}, x)
x**2 + 1

diofant.polys.polyfuncs.viete(f, roots=None, *gens, **args)[source]

Generate Viete’s formulas for f.

Examples

>>> r1, r2 = symbols('r1:3')

>>> viete(a*x**2 + b*x + c, [r1, r2], x)
[(r1 + r2, -b/a), (r1*r2, c/a)]


Domain constructors¶

Tools for constructing domains for expressions.

diofant.polys.constructor.construct_domain(obj, **args)[source]

Construct a minimal domain for the list of coefficients.

Algebraic number fields¶

Computational algebraic field theory.

diofant.polys.numberfields.minimal_polynomial(ex, method=None, **args)[source]

Computes the minimal polynomial of an algebraic element.

Parameters: ex (algebraic element expression) method (str, optional) – If compose, the minimal polynomial of the subexpressions of ex are computed, then the arithmetic operations on them are performed using the resultant and factorization. If groebner, a bottom-up algorithm, using Gröbner bases is used. Defaults are determined by setup(). domain (Domain, optional) – If no ground domain is given, it will be generated automatically from the expression.

Examples

>>> minimal_polynomial(sqrt(2))(x)
x**2 - 2
>>> minimal_polynomial(sqrt(2), domain=QQ.algebraic_field(sqrt(2)))(x)
x - sqrt(2)
>>> minimal_polynomial(sqrt(2) + sqrt(3))(x)
x**4 - 10*x**2 + 1
>>> minimal_polynomial(solve(x**3 + x + 3)[0][x])(x)
x**3 + x + 3
>>> minimal_polynomial(sqrt(y))(x)
x**2 - y

diofant.polys.numberfields.primitive_element(extension, **args)[source]

Construct a common number field for all extensions.

References

diofant.polys.numberfields.field_isomorphism(a, b, **args)[source]

Construct an isomorphism between two number fields.

Monomials encoded as tuples¶

Tools and arithmetics for monomials of distributed polynomials.

class diofant.polys.monomials.Monomial(monom, gens=None)[source]

Class representing a monomial, i.e. a product of powers.

as_expr(*gens)[source]

Convert a monomial instance to a Diofant expression.

gcd(other)[source]

Greatest common divisor of monomials.

lcm(other)[source]

Least common multiple of monomials.

diofant.polys.monomials.itermonomials(variables, degree)[source]

Generate a set of monomials of the given total degree or less.

Given a set of variables $$V$$ and a total degree $$N$$ generate a set of monomials of degree at most $$N$$. The total number of monomials is huge and is given by the following formula:

$\frac{(\#V + N)!}{\#V! N!}$

For example if we would like to generate a dense polynomial of a total degree $$N = 50$$ in 5 variables, assuming that exponents and all of coefficients are 32-bit long and stored in an array we would need almost 80 GiB of memory! Fortunately most polynomials, that we will encounter, are sparse.

Examples

Consider monomials in variables $$x$$ and $$y$$:

>>> from diofant.polys.orderings import monomial_key

>>> sorted(itermonomials([x, y], 2), key=monomial_key('grlex', [y, x]))
[1, x, y, x**2, x*y, y**2]

>>> sorted(itermonomials([x, y], 3), key=monomial_key('grlex', [y, x]))
[1, x, y, x**2, x*y, y**2, x**3, x**2*y, x*y**2, y**3]


Orderings of monomials¶

Definitions of monomial orderings.

class diofant.polys.orderings.LexOrder[source]

Lexicographic order of monomials.

class diofant.polys.orderings.GradedLexOrder[source]

Graded lexicographic order of monomials.

class diofant.polys.orderings.ReversedGradedLexOrder[source]

Reversed graded lexicographic order of monomials.

Formal manipulation of roots of polynomials¶

Implementation of RootOf class and related tools.

class diofant.polys.rootoftools.RootOf[source]

Represents k-th root of a univariate polynomial.

The ordering used for indexing takes real roots to come before complex ones, sort complex roots by real part, then by imaginary part and finally takes complex conjugate pairs of roots to be adjacent.

Parameters: f (Expr) – Univariate polynomial expression. x (Symbol or Integer) – Polynomial variable or the index of the root. index (Integer or None, optional) – Index of the root. If None (default), parameter x is used instead as index. radicals (bool, optional) – Explicitly solve linear or quadratic polynomial equation (enabled by default). expand (bool, optional) – Expand polynomial, enabled default. evaluate (bool or None, optional) – Control automatic evaluation.

Examples

>>> expand_func(RootOf(x**3 + I*x + 2, 0))
RootOf(x**6 + 4*x**3 + x**2 + 4, 1)

classmethod all_roots(poly, radicals=True)[source]

Get real and complex roots of a polynomial.

eval_rational(tol)[source]

Returns a Rational approximation to self with the tolerance tol.

The returned instance will be at most ‘tol’ from the exact root.

The following example first obtains Rational approximation to 1e-7 accuracy for all roots of the 4-th order Legendre polynomial, and then evaluates it to 5 decimal digits (so all digits will be correct including rounding):

>>> p = legendre_poly(4, x, polys=True)
>>> roots = [r.eval_rational(Rational(1, 10)**7) for r in p.real_roots()]
>>> roots = [str(r.evalf(5)) for r in roots]
>>> roots
['-0.86114', '-0.33998', '0.33998', '0.86114']

interval

Return isolation interval for the root.

classmethod real_roots(poly, radicals=True)[source]

Get real roots of a polynomial.

refine()[source]

Refine isolation interval for the root.

class diofant.polys.rootoftools.RootSum[source]

Represents a sum of all roots of a univariate polynomial.

classmethod new(poly, func, auto=True)[source]

Construct new RootSum instance.

Symbolic root-finding algorithms¶

Algorithms for computing symbolic roots of polynomials.

diofant.polys.polyroots.roots(f, *gens, **flags)[source]

Computes symbolic roots of a univariate polynomial.

Given a univariate polynomial f with symbolic coefficients (or a list of the polynomial’s coefficients), returns a dictionary with its roots and their multiplicities.

Only roots expressible via radicals will be returned. To get a complete set of roots use RootOf class or numerical methods instead. By default cubic and quartic formulas are used in the algorithm. To disable them because of unreadable output set cubics=False or quartics=False respectively. If cubic roots are real but are expressed in terms of complex numbers (casus irreducibilis) the trig flag can be set to True to have the solutions returned in terms of cosine and inverse cosine functions.

To get roots from a specific domain set the filter flag with one of the following specifiers: Z, Q, R, I, C. By default all roots are returned (this is equivalent to setting filter='C').

By default a dictionary is returned giving a compact result in case of multiple roots. However to get a list containing all those roots set the multiple flag to True; the list will have identical roots appearing next to each other in the result. (For a given Poly, the all_roots method will give the roots in sorted numerical order.)

Examples

>>> roots(x**2 - 1, x)
{-1: 1, 1: 1}

>>> p = Poly(x**2-1, x)
>>> roots(p)
{-1: 1, 1: 1}

>>> p = Poly(x**2-y, x, y)

>>> roots(Poly(p, x))
{-sqrt(y): 1, sqrt(y): 1}

>>> roots(x**2 - y, x)
{-sqrt(y): 1, sqrt(y): 1}

>>> roots([1, 0, -1])
{-1: 1, 1: 1}


References

Special polynomials¶

Functions for generating interesting polynomials, e.g. for benchmarking.

diofant.polys.specialpolys.swinnerton_dyer_poly(n, x=None, **args)[source]

Generates n-th Swinnerton-Dyer polynomial in $$x$$.

diofant.polys.specialpolys.cyclotomic_poly(n, x=None, **args)[source]

Generates cyclotomic polynomial of order $$n$$ in $$x$$.

diofant.polys.specialpolys.symmetric_poly(n, *gens, **args)[source]

Generates symmetric polynomial of order $$n$$.

diofant.polys.specialpolys.random_poly(x, n, inf, sup, domain=PythonIntegerRing(), polys=False, percent=None)[source]

Return a polynomial of degree n with coefficients in [inf, sup].

diofant.polys.specialpolys.interpolating_poly(n, x, X='x', Y='y')[source]

Construct Lagrange interpolating polynomial for n data points.

Orthogonal polynomials¶

Efficient functions for generating orthogonal polynomials.

diofant.polys.orthopolys.jacobi_poly(n, a, b, x=None, **args)[source]

Generates Jacobi polynomial of degree $$n$$ in $$x$$.

diofant.polys.orthopolys.chebyshevt_poly(n, x=None, **args)[source]

Generates Chebyshev polynomial of the first kind of degree $$n$$ in $$x$$.

diofant.polys.orthopolys.chebyshevu_poly(n, x=None, **args)[source]

Generates Chebyshev polynomial of the second kind of degree $$n$$ in $$x$$.

diofant.polys.orthopolys.hermite_poly(n, x=None, **args)[source]

Generates Hermite polynomial of degree $$n$$ in $$x$$.

diofant.polys.orthopolys.legendre_poly(n, x=None, **args)[source]

Generates Legendre polynomial of degree $$n$$ in $$x$$.

diofant.polys.orthopolys.laguerre_poly(n, x=None, alpha=None, **args)[source]

Generates Laguerre polynomial of degree $$n$$ in $$x$$.

diofant.polys.orthopolys.spherical_bessel_fn(n, x=None, **args)[source]

Coefficients for the spherical Bessel functions.

Those are only needed in the jn() function.

The coefficients are calculated from:

fn(0, z) = 1/z fn(1, z) = 1/z**2 fn(n-1, z) + fn(n+1, z) == (2*n+1)/z * fn(n, z)

Examples

>>> spherical_bessel_fn(1, z)
z**(-2)
>>> spherical_bessel_fn(2, z)
-1/z + 3/z**3
>>> spherical_bessel_fn(3, z)
-6/z**2 + 15/z**4
>>> spherical_bessel_fn(4, z)
1/z - 45/z**3 + 105/z**5

diofant.polys.orthopolys.gegenbauer_poly(n, a, x=None, **args)[source]

Generates Gegenbauer polynomial of degree $$n$$ in $$x$$.

Manipulation of rational functions¶

Tools for manipulation of rational expressions.

diofant.polys.rationaltools.together(expr, deep=False)[source]

Denest and combine rational expressions using symbolic methods.

This function takes an expression or a container of expressions and puts it (them) together by denesting and combining rational subexpressions. No heroic measures are taken to minimize degree of the resulting numerator and denominator. To obtain completely reduced expression use cancel(). However, together() can preserve as much as possible of the structure of the input expression in the output (no expansion is performed).

A wide variety of objects can be put together including lists, tuples, sets, relational objects, integrals and others. It is also possible to transform interior of function applications, by setting deep flag to True.

By definition, together() is a complement to apart(), so apart(together(expr)) should return expr unchanged. Note however, that together() uses only symbolic methods, so it might be necessary to use cancel() to perform algebraic simplification and minimise degree of the numerator and denominator.

Examples

>>> together(1/x + 1/y)
(x + y)/(x*y)
>>> together(1/x + 1/y + 1/z)
(x*y + x*z + y*z)/(x*y*z)

>>> together(1/(x*y) + 1/y**2)
(x + y)/(x*y**2)

>>> together(1/(1 + 1/x) + 1/(1 + 1/y))
(x*(y + 1) + y*(x + 1))/((x + 1)*(y + 1))

>>> together(exp(1/x + 1/y))
E**(1/y + 1/x)
>>> together(exp(1/x + 1/y), deep=True)
E**((x + y)/(x*y))

>>> together(1/exp(x) + 1/(x*exp(x)))
E**(-x)*(x + 1)/x

>>> together(1/exp(2*x) + 1/(x*exp(3*x)))
E**(-3*x)*(E**x*x + 1)/x


Partial fraction decomposition¶

Algorithms for partial fraction decomposition of rational functions.

diofant.polys.partfrac.apart(f, x=None, full=False, **options)[source]

Compute partial fraction decomposition of a rational function.

Given a rational function f, computes the partial fraction decomposition of f. Two algorithms are available: One is based on the undertermined coefficients method, the other is Bronstein’s full partial fraction decomposition algorithm.

The undetermined coefficients method (selected by full=False) uses polynomial factorization (and therefore accepts the same options as factor) for the denominator. Per default it works over the rational numbers, therefore decomposition of denominators with non-rational roots (e.g. irrational, complex roots) is not supported by default (see options of factor).

Bronstein’s algorithm can be selected by using full=True and allows a decomposition of denominators with non-rational roots. A human-readable result can be obtained via doit() (see examples below).

Examples

By default, using the undetermined coefficients method:

>>> apart(y/(x + 2)/(x + 1), x)
-y/(x + 2) + y/(x + 1)


The undetermined coefficients method does not provide a result when the denominators roots are not rational:

>>> apart(y/(x**2 + x + 1), x)
y/(x**2 + x + 1)


You can choose Bronstein’s algorithm by setting full=True:

>>> apart(y/(x**2 + x + 1), x, full=True)
RootSum(_w**2 + _w + 1, Lambda(_a, (-2*y*_a/3 - y/3)/(x - _a)))


Calling doit() yields a human-readable result:

>>> apart(y/(x**2 + x + 1), x, full=True).doit()
(-y/3 - 2*y*(-1/2 - sqrt(3)*I/2)/3)/(x + 1/2 + sqrt(3)*I/2) + (-y/3 -
2*y*(-1/2 + sqrt(3)*I/2)/3)/(x + 1/2 - sqrt(3)*I/2)

diofant.polys.partfrac.apart_list(f, x=None, dummies=None, **options)[source]

Compute partial fraction decomposition of a rational function and return the result in structured form.

Given a rational function f compute the partial fraction decomposition of f. Only Bronstein’s full partial fraction decomposition algorithm is supported by this method. The return value is highly structured and perfectly suited for further algorithmic treatment rather than being human-readable. The function returns a tuple holding three elements:

• The first item is the common coefficient, free of the variable $$x$$ used for decomposition. (It is an element of the base field $$K$$.)
• The second item is the polynomial part of the decomposition. This can be the zero polynomial. (It is an element of $$K[x]$$.)
• The third part itself is a list of quadruples. Each quadruple has the following elements in this order:
• The (not necessarily irreducible) polynomial $$D$$ whose roots $$w_i$$ appear in the linear denominator of a bunch of related fraction terms. (This item can also be a list of explicit roots. However, at the moment apart_list never returns a result this way, but the related assemble_partfrac_list function accepts this format as input.)
• The numerator of the fraction, written as a function of the root $$w$$
• The linear denominator of the fraction excluding its power exponent, written as a function of the root $$w$$.
• The power to which the denominator has to be raised.

On can always rebuild a plain expression by using the function assemble_partfrac_list.

Examples

A first example:

>>> f = (2*x**3 - 2*x) / (x**2 - 2*x + 1)
>>> pfd = apart_list(f)
>>> pfd
(1,
Poly(2*x + 4, x, domain='ZZ'),
[(Poly(_w - 1, _w, domain='ZZ'), Lambda(_a, 4), Lambda(_a, x - _a), 1)])

>>> assemble_partfrac_list(pfd)
2*x + 4 + 4/(x - 1)


Second example:

>>> f = (-2*x - 2*x**2) / (3*x**2 - 6*x)
>>> pfd = apart_list(f)
>>> pfd
(-1,
Poly(2/3, x, domain='QQ'),
[(Poly(_w - 2, _w, domain='ZZ'), Lambda(_a, 2), Lambda(_a, x - _a), 1)])

>>> assemble_partfrac_list(pfd)
-2/3 - 2/(x - 2)


Another example, showing symbolic parameters:

>>> pfd = apart_list(t/(x**2 + x + t), x)
>>> pfd
(1,
Poly(0, x, domain='ZZ[t]'),
[(Poly(_w**2 + _w + t, _w, domain='ZZ[t]'),
Lambda(_a, -2*t*_a/(4*t - 1) - t/(4*t - 1)),
Lambda(_a, x - _a), 1)])

>>> assemble_partfrac_list(pfd)
RootSum(t + _w**2 + _w, Lambda(_a, (-2*t*_a/(4*t - 1) - t/(4*t - 1))/(x - _a)))


This example is taken from Bronstein’s original paper:

>>> f = 36 / (x**5 - 2*x**4 - 2*x**3 + 4*x**2 + x - 2)
>>> pfd = apart_list(f)
>>> pfd
(1,
Poly(0, x, domain='ZZ'),
[(Poly(_w - 2, _w, domain='ZZ'), Lambda(_a, 4), Lambda(_a, x - _a), 1),
(Poly(_w**2 - 1, _w, domain='ZZ'), Lambda(_a, -3*_a - 6), Lambda(_a, x - _a), 2),
(Poly(_w + 1, _w, domain='ZZ'), Lambda(_a, -4), Lambda(_a, x - _a), 1)])

>>> assemble_partfrac_list(pfd)
-4/(x + 1) - 3/(x + 1)**2 - 9/(x - 1)**2 + 4/(x - 2)


References

diofant.polys.partfrac.assemble_partfrac_list(partial_list)[source]

Reassemble a full partial fraction decomposition from a structured result obtained by the function apart_list.

Examples

This example is taken from Bronstein’s original paper:

>>> f = 36 / (x**5 - 2*x**4 - 2*x**3 + 4*x**2 + x - 2)
>>> pfd = apart_list(f)
>>> pfd
(1,
Poly(0, x, domain='ZZ'),
[(Poly(_w - 2, _w, domain='ZZ'), Lambda(_a, 4), Lambda(_a, x - _a), 1),
(Poly(_w**2 - 1, _w, domain='ZZ'), Lambda(_a, -3*_a - 6), Lambda(_a, x - _a), 2),
(Poly(_w + 1, _w, domain='ZZ'), Lambda(_a, -4), Lambda(_a, x - _a), 1)])

>>> assemble_partfrac_list(pfd)
-4/(x + 1) - 3/(x + 1)**2 - 9/(x - 1)**2 + 4/(x - 2)


If we happen to know some roots we can provide them easily inside the structure:

>>> pfd = apart_list(2/(x**2-2))
>>> pfd
(1,
Poly(0, x, domain='ZZ'),
[(Poly(_w**2 - 2, _w, domain='ZZ'),
Lambda(_a, _a/2), Lambda(_a, x - _a),
1)])

>>> pfda = assemble_partfrac_list(pfd)
>>> pfda
RootSum(_w**2 - 2, Lambda(_a, _a/(x - _a)))/2

>>> pfda.doit()
-sqrt(2)/(2*(x + sqrt(2))) + sqrt(2)/(2*(x - sqrt(2)))

>>> a = Dummy("a")
>>> pfd = (1, Poly(0, x), [([sqrt(2), -sqrt(2)], Lambda(a, a/2), Lambda(a, -a + x), 1)])

>>> assemble_partfrac_list(pfd)
-sqrt(2)/(2*(x + sqrt(2))) + sqrt(2)/(2*(x - sqrt(2)))


Dispersion of Polynomials¶

diofant.polys.dispersion.dispersion(p, q=None, *gens, **args)[source]

Compute the dispersion of polynomials.

For two polynomials $$f(x)$$ and $$g(x)$$ with $$\deg f > 0$$ and $$\deg g > 0$$ the dispersion $$\operatorname{dis}(f, g)$$ is defined as:

$\begin{split}\operatorname{dis}(f, g) & := \max\{ J(f,g) \cup \{0\} \} \\ & = \max\{ \{a \in \mathbb{N} | \gcd(f(x), g(x+a)) \neq 1\} \cup \{0\} \}\end{split}$

and for a single polynomial $$\operatorname{dis}(f) := \operatorname{dis}(f, f)$$. Note that we make the definition $$\max\{\} := -\infty$$.

References

diofant.polys.dispersion.dispersionset(p, q=None, *gens, **args)[source]

Compute the dispersion set of two polynomials.

For two polynomials $$f(x)$$ and $$g(x)$$ with $$\deg f > 0$$ and $$\deg g > 0$$ the dispersion set $$\operatorname{J}(f, g)$$ is defined as:

$\begin{split}\operatorname{J}(f, g) & := \{a \in \mathbb{N}_0 | \gcd(f(x), g(x+a)) \neq 1\} \\ & = \{a \in \mathbb{N}_0 | \deg \gcd(f(x), g(x+a)) \geq 1\}\end{split}$

For a single polynomial one defines $$\operatorname{J}(f) := \operatorname{J}(f, f)$$.

Examples

Note that the definition of the dispersion is not symmetric:

>>> fp = Poly(x**4 - 3*x**2 + 1)
>>> gp = fp.shift(-3)
>>> sorted(dispersionset(fp, gp))
[2, 3, 4]
>>> dispersion(fp, gp)
4
>>> sorted(dispersionset(gp, fp))
[]
>>> dispersion(gp, fp)
-oo


Computing the dispersion also works over field extensions:

>>> fp = Poly(x**2 + sqrt(5)*x - 1, x)
>>> gp = Poly(x**2 + (2 + sqrt(5))*x + sqrt(5), x)
>>> sorted(dispersionset(fp, gp))
[2]
>>> sorted(dispersionset(gp, fp))
[1, 4]


We can even perform the computations for polynomials having symbolic coefficients:

>>> fp = Poly(4*x**4 + (4*a + 8)*x**3 + (a**2 + 6*a + 4)*x**2 + (a**2 + 2*a)*x, x)
>>> sorted(dispersionset(fp))
[0, 1]


References