fmpz_mpoly – multivariate polynomials over the integers

class flint.fmpz_mpoly_ctx

A class for storing the polynomial context

Parameters:

• names – A tuple containing the names of the variables of the ring.

• ordering – The term order for the ring.

Do not construct one of these directly, use fmpz_mpoly_ctx.get.

append_gens(self, *gens: str)

Get a context with the specified generators appended.

>>> from flint import fmpz_mpoly_ctx
>>> ctx = fmpz_mpoly_ctx.get(('x', 'y', 'z'))
>>> ctx.append_gens('a', 'b')
fmpz_mpoly_ctx(5, '<Ordering.lex: 'lex'>', ('x', 'y', 'z', 'a', 'b'))

compatible_context_check(self, other)

constant(self, z)

Create a constant polynomial in this context

classmethod create_context_key(cls, names: str | Iterable[str | tuple[str, int]], ordering: Ordering | str = Ordering.lex)

Create a key for the context cache via the variable names and the ordering.

static create_variable_names(names: str | Iterable[str | tuple[str, int]]) → tuple[str]

Create a tuple of variable names based off either str, Iterable[str], tuple[str, int], or Iterable[tuple[str, int]].

>>> flint_mpoly_context.create_variable_names('x')
('x',)
>>> flint_mpoly_context.create_variable_names(('x', 3))
('x0', 'x1', 'x2')
>>> flint_mpoly_context.create_variable_names([('x', 3), 'y'])
('x0', 'x1', 'x2', 'y')

drop_gens(self, gens: Iterable[str | int])

Get a context with the specified generators removed.

>>> from flint import fmpz_mpoly_ctx
>>> ctx = fmpz_mpoly_ctx.get(('x', 'y', 'z', 'a', 'b'))
>>> ctx.drop_gens(('x', -2))
fmpz_mpoly_ctx(3, '<Ordering.lex: 'lex'>', ('y', 'z', 'b'))

classmethod from_context(cls, flint_mpoly_context ctx: flint_mpoly_context, names=None, ordering=None)

Get a new context from an existing one. Optionally override names or ordering.

from_dict(self, d)

Create a fmpz_mpoly from a dictionary in this context.

The dictionary’s keys are tuples of ints (or anything that implicitly converts to fmpz) representing exponents, and corresponding values of fmpz.

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> ctx.from_dict({(1,0):2, (1,1):3, (0,1):1})
3*x*y + 2*x + y

gen(self, slong i)

Return the i th generator of the polynomial ring

>>> ctx = fmpz_mpoly_ctx.get(('z', 3), 'degrevlex')
>>> ctx.gen(1)
z1

gens(self)

classmethod get(cls, *args, **kwargs)

Retrieve or create a context via generator names, names and the ordering, ordering.

See create_variable_names for naming schemes.

infer_generator_mapping(self, flint_mpoly_context ctx: flint_mpoly_context)

Infer a mapping of generator indexes from this contexts generators, to the provided contexts generators. Inference is done based upon generator names.

>>> from flint import fmpz_mpoly_ctx
>>> ctx = fmpz_mpoly_ctx.get(('x', 'y', 'z', 'a', 'b'))
>>> ctx2 = fmpz_mpoly_ctx.get(('b', 'a'))
>>> mapping = ctx.infer_generator_mapping(ctx2)
>>> mapping
{3: 1, 4: 0}
>>> list(sorted(mapping.items()))  # Set ordering is not stable
[(3, 1), (4, 0)]

name(self, int i: int)

names(self) → tuple[str]

nvars(self)

Return the number of variables in the context

>>> ctx = fmpz_mpoly_ctx.get(('x', 4), 'lex')
>>> ctx.nvars()
4

ordering(self)

Return the term order of the context object.

>>> ctx = fmpz_mpoly_ctx.get(('w', 4), 'deglex')
>>> ctx.ordering()
<Ordering.deglex: 'deglex'>

py_names

py_names: object

term(self, coeff=None, exp_vec=None)

Create a monomial from a coefficient and exponent vector. coeff defaults to 1. exp_vec` defaults to (0,) * self.nvars()`.

>>> from flint import fmpz_mpoly_ctx
>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> ctx.term(coeff=5, exp_vec=(2, 3))
5*x0^2*x1^3
>>> ctx.term()
1

variable_to_index(self, var: int | str) → int

Convert a variable name string or possible index to its index in the context.

If var is negative, return the index of the self.nvars() + var

class flint.fmpz_mpoly(val=0, ctx=None)

The fmpz_mpoly type represents sparse multivariate polynomials over the integers.

coefficient(self, slong i)

Return the coefficient at index i.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> p = ctx.from_dict({(0, 1): 2, (1, 1): 3})
>>> p.coefficient(1)
2

coeffs(self)

Return the coefficients of each term as a fmpz

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> f = ctx.from_dict({(0, 0): 1, (1, 0): 2, (0, 1): 3, (1, 1): 4})
>>> f.coeffs()
[4, 2, 3, 1]

compose(self, *args, ctx=None) → fmpz_mpoly

Compose this polynomial with other fmpz_mpolys. All arguments must share the same context, it may different from this polynomials context.

>>> ctx = fmpz_mpoly_ctx.get(('x',), 'lex')
>>> ctx1 = fmpz_mpoly_ctx.get(('y', 2), 'lex')
>>> f = ctx.from_dict({(2,): 1})
>>> g = ctx1.from_dict({(1, 0): 1, (0, 1): 1})
>>> f
x^2
>>> g
y0 + y1
>>> f.compose(g)
y0^2 + 2*y0*y1 + y1^2

content(self)

Return the GCD of the coefficients of self.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> x0, x1 = ctx.gens()
>>> f = 3 * x0**2 * x1 + 6 * x0 * x1
>>> f.content()
3

context(self)

Return the context object for this polynomials.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> p = ctx.from_dict({(0, 1): 2})
>>> ctx is p.context()
True

deflate(self, list N: list[int]) → fmpz_mpoly

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

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> f = x**3 * y + x * y**4 + x * y
>>> f.deflate([2, 3])
x + y + 1

deflation(self) → tuple[fmpz_mpoly, list[int]]

Compute the deflation of self, that is p(X^(1/N)) for maximal N.

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> f = x**2 * y**2 + x * y**2
>>> q, N = f.deflation()
>>> q, N
(x^2*y + x*y, [1, 2])
>>> q.inflate(N) == f
True

deflation_index(self) → tuple[list[int], list[int]]

Compute the exponent vectors 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 vector I is the shift that was applied to the exponents. It is the exponent vector of the monomial returned by deflation_monom.

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> f = x**3 * y + x * y**4 + x * y
>>> N, I = f.deflation_index()
>>> N, I
([2, 3], [1, 1])
>>> f_deflated = f.deflate(N)
>>> f_deflated
x + y + 1
>>> m = ctx.term(exp_vec=I)
>>> m
x*y
>>> m * f_deflated.inflate(N)
x^3*y + x*y^4 + x*y

deflation_monom(self) → tuple[fmpz_mpoly, list[int], fmpz_mpoly]

Compute the exponent vector 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.

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> f = x**3 * y + x * y**4 + x * y
>>> fd, N, m = f.deflation_monom()
>>> fd, N, m
(x + y + 1, [2, 3], x*y)
>>> m * fd.inflate(N)
x^3*y + x*y^4 + x*y

degrees(self)

Return a tuple of degrees.

>>> ctx = fmpz_mpoly_ctx.get(('x', 4), 'lex')
>>> p = sum(x**i for i, x in enumerate(ctx.gens()))
>>> p
x1 + x2^2 + x3^3 + 1
>>> p.degrees()
(0, 1, 2, 3)

derivative(self, var)

Return the derivative of this polynomial with respect to the provided variable. The argument can either be the variable as a string, or the index of the variable in the context.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> p = ctx.from_dict({(0, 3): 2, (2, 1): 3})
>>> p
3*x0^2*x1 + 2*x1^3
>>> p.derivative("x0")
6*x0*x1
>>> p.derivative(1)
3*x0^2 + 6*x1^2

discriminant(self, var)

Return the discriminant of self with respect to variable var.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> x0, x1 = ctx.gens()
>>> f = (x0 + x1)**2 + 1
>>> f.discriminant('x1')
-4

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.

>>> Zm = fmpz_mpoly
>>> ctx = fmpz_mpoly_ctx.get(('x', 'y', 'z'), 'lex')
>>> p1 = Zm("2*x + 4", ctx)
>>> p2 = Zm("3*x*z + 3*x + 3*z + 3", ctx)
>>> (p1 * p2).factor()
(6, [(z + 1, 1), (x + 2, 1), (x + 1, 1)])
>>> (p2 * p1 * p2).factor()
(18, [(z + 1, 2), (x + 2, 1), (x + 1, 2)])

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.

>>> Zm = fmpz_mpoly
>>> ctx = fmpz_mpoly_ctx.get(('x', 'y', 'z'), 'lex')
>>> p1 = Zm("2*x + 4", ctx)
>>> p2 = Zm("3*x*y + 3*x + 3*y + 3", ctx)
>>> (p1 * p2).factor_squarefree()
(6, [(y + 1, 1), (x^2 + 3*x + 2, 1)])
>>> (p1 * p2 * p1).factor_squarefree()
(12, [(y + 1, 1), (x + 1, 1), (x + 2, 2)])

gcd(self, other)

Return the gcd of self and other.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> f = ctx.from_dict({(1, 1): 4, (0, 0): 1})
>>> g = ctx.from_dict({(0, 1): 2, (1, 0): 2})
>>> (f * g).gcd(f)
4*x0*x1 + 1

iadd(self, other)

In-place addition, mutates self.

>>> from flint import fmpz_mpoly_ctx
>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> f = ctx.from_dict({(1, 0): 2, (0, 1): 3, (1, 1): 4})
>>> f
4*x0*x1 + 2*x0 + 3*x1
>>> f.iadd(5)
>>> f
4*x0*x1 + 2*x0 + 3*x1 + 5

imul(self, other)

In-place multiplication, mutates self.

>>> from flint import fmpz_mpoly_ctx
>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> f = ctx.from_dict({(1, 0): 2, (0, 1): 3, (1, 1): 4})
>>> f
4*x0*x1 + 2*x0 + 3*x1
>>> f.imul(2)
>>> f
8*x0*x1 + 4*x0 + 6*x1

inflate(self, list N: list[int]) → fmpz_mpoly

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

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> f = x + y + 1
>>> f.inflate([2, 3])
x^2 + y^3 + 1

integral(self, var)

Return the integral of this polynomial*B with respect to the provided variable where B is minimal. That is, given p this method returns (B, P) such that P’ = B*p or P/B is the formal integral of p.

The argument can either be the variable as a string, or the index of the variable in the context.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> p = ctx.from_dict({(0, 3): 2, (2, 1): 3})
>>> p
3*x0^2*x1 + 2*x1^3
>>> p.integral("x0")
(1, x0^3*x1 + 2*x0*x1^3)
>>> p.integral(1)
(2, 3*x0^2*x1^2 + x1^4)

is_constant(self)

Returns True if this is a constant polynomial.

>>> ctx = fmpz_mpoly_ctx.get(['x', 'y'])
>>> x, y = ctx.gens()
>>> p = x**2 + y
>>> p.is_constant()
False
>>> (0*p + 1).is_constant()
True

is_one(self)

is_zero(self)

isub(self, other)

In-place subtraction, mutates self.

>>> from flint import fmpz_mpoly_ctx
>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> f = ctx.from_dict({(1, 0): 2, (0, 1): 3, (1, 1): 4})
>>> f
4*x0*x1 + 2*x0 + 3*x1
>>> f.isub(5)
>>> f
4*x0*x1 + 2*x0 + 3*x1 - 5

leading_coefficient(self)

Leading coefficient in the monomial ordering.

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> p = 2*x*y + 3*x + 4*y**2 + 5
>>> p
2*x*y + 3*x + 4*y^2 + 5
>>> p.leading_coefficient()
2

monomial(self, slong i)

Return the exponent vector at index i as a tuple.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> p = ctx.from_dict({(0, 1): 2, (1, 1): 3})
>>> p.monomial(1)
(0, 1)

monoms(self)

Return the exponent vectors of each term as a tuple of fmpz.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> f = ctx.from_dict({(0, 0): 1, (1, 0): 2, (0, 1): 3, (1, 1): 4})
>>> f.monoms()
[(1, 1), (1, 0), (0, 1), (0, 0)]

primitive(self)

Return the content and primitive of self.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> x, y = ctx.gens()
>>> f = 4*x + 2*x*y
>>> f.primitive()
(2, x0*x1 + 2*x0)

project_to_context(self, other_ctx, dict mapping: dict[str | int, str | int] = None)

Project this polynomial to a different context.

This is equivalent to composing this polynomial with the generators of another context. By default the mapping between contexts is inferred based on the name of the generators. Generators with names that are not found within the other context are mapped to 0. The mapping can be explicitly provided.

>>> from flint import fmpz_mpoly_ctx
>>> ctx = fmpz_mpoly_ctx.get(('x', 'y', 'a', 'b'))
>>> ctx2 = fmpz_mpoly_ctx.get(('a', 'b'))
>>> x, y, a, b = ctx.gens()
>>> f = x + 2*y + 3*a + 4*b
>>> f.project_to_context(ctx2)
3*a + 4*b
>>> f.project_to_context(ctx2, mapping={"x": "a", "b": 0})
5*a

reduction_primitive_part(self, vec)

Compute the the primitive part of the reduction (remainder of multivariate quasi-division with remainder) with respect to the polynomials vec.

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> f = 2 * x**3 -x**2 * y + y**3 + 3 * y
>>> g1 = x**2 + y**2 + 1
>>> g2 = x * y - 2
>>> vec = fmpz_mpoly_vec([g1, g2], ctx)
>>> vec
fmpz_mpoly_vec([x^2 + y^2 + 1, x*y - 2], ctx=fmpz_mpoly_ctx(2, '<Ordering.lex: 'lex'>', ('x', 'y')))
>>> f.reduction_primitive_part(vec)
x - y^3

repr(self)

resultant(self, other, var)

Return the resultant of self and other with respect to variable var.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> x0, x1 = ctx.gens()
>>> f = x0**2 * x1 + x0 * x1
>>> g = x0 + x1
>>> f.resultant(g, 'x1')
x0^3 + x0^2

spoly(self, g)

Compute the S-polynomial of self and g, scaled to an integer polynomial by computing the LCM of the leading coefficients.

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> f = ctx.from_dict({(2, 0): 1, (0, 1): -1})
>>> g = ctx.from_dict({(3, 0): 1, (1, 0): -1})
>>> f.spoly(g)
-x*y + x

sqrt(self, assume_perfect_square: bool = False)

Return the square root of self. If self is known to be a perfect square provide assume_perfect_square=True for a more efficient result. If self is not a square root the result is not guaranteed to be correct.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> f = ctx.from_dict({(1, 1): 4, (0, 0): 1})
>>> (f * f).sqrt()
4*x0*x1 + 1

str(self)

subs(self, dict_args) → fmpz_mpoly

Partial evaluate this polynomial with select constants. Keys must be generator names or generator indices, all values must be fmpz.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> f = ctx.from_dict({(0, 0): 1, (1, 0): 2, (0, 1): 3, (1, 1): 4})
>>> f.subs({"x1": 0})
2*x0 + 1

term_content(self)

Return the GCD of the terms of self. If self is zero, then the result will be zero, otherwise it will be a monomial with positive coefficient.

>>> ctx = fmpz_mpoly_ctx.get(('x', 2), 'lex')
>>> x0, x1 = ctx.gens()
>>> f = 3 * x0**2 * x1 + 6 * x0 * x1
>>> f.term_content()
3*x0*x1

terms(self)

Return the exponent vectors and coefficient of each term.

>>> from flint import fmpq_mpoly_ctx
>>> ctx = fmpq_mpoly_ctx.get(('x', 2), 'lex')
>>> f = ctx.from_dict({(0, 0): 1, (1, 0): 2, (0, 1): 3, (1, 1): 4})
>>> list(f.terms())
[((1, 1), 4), ((1, 0), 2), ((0, 1), 3), ((0, 0), 1)]

to_dict(self)

total_degree(self)

Return the total degree.

>>> ctx = fmpz_mpoly_ctx.get(('x', 4), 'lex')
>>> p = ctx.from_dict({(1, 0, 0, 0): 1, (0, 2, 0, 0): 2, (0, 0, 3, 0): 3})
>>> p.total_degree()
3

unused_gens(self)

Report the unused generators from this polynomial.

A generator is unused if it’s maximum degree is 0.

>>> from flint import fmpz_mpoly_ctx
>>> ctx = fmpz_mpoly_ctx.get(('x', 4))
>>> ctx2 = fmpz_mpoly_ctx.get(('x1', 'x2'))
>>> f = sum(ctx.gens()[1:3])
>>> f
x1 + x2
>>> f.unused_gens()
('x0', 'x3')

class flint.fmpz_mpoly_vec(iterable_or_len, _, double_indirect: bool = False)

A class representing a vector of fmpz_mpolys.

autoreduction(self, groebner=False) → fmpz_mpoly_vec

Compute the autoreduction of self. If groebner is True and self is a Gröbner basis, compute the reduced reduced Gröbner basis of self, throws an RuntimeError otherwise.

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> f2 = 3*x**2 - y
>>> k2 = 3*x*y - 3*x
>>> h = y**2 - y
>>> vec = fmpz_mpoly_vec([f2, k2, h], ctx)
>>> vec.is_autoreduced()
False
>>> vec2 = vec.autoreduction()
>>> vec2.is_autoreduced()
True
>>> vec2
fmpz_mpoly_vec([3*x^2 - y, x*y - x, y^2 - y], ctx=fmpz_mpoly_ctx(2, '<Ordering.lex: 'lex'>', ('x', 'y')))

buchberger_naive(self, limits=None)

Compute the Gröbner basis of self using a naive implementation of Buchberger’s algorithm.

Provide limits in the form of a tuple of (ideal_len_limit, poly_len_limit, poly_bits_limit) to halt execution if the length of the ideal basis set exceeds ideal_len_limit, the length of any polynomial exceeds poly_len_limit, or the size of the coefficients of any polynomial exceeds poly_bits_limit.

If limits is provided return a tuple of (result, success). If success is False then result is a valid basis for self, but it may not be a Gröbner basis.

NOTE: This function is exposed only for convenience, it is a naive implementation and does not compute a reduced basis. To construct a reduced basis use autoreduce.

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> f = x**2 - y
>>> g = x**3*y - x
>>> vec = fmpz_mpoly_vec([f, g], ctx)
>>> vec.is_groebner()
False
>>> vec2 = vec.buchberger_naive()
>>> vec2
fmpz_mpoly_vec([x^2 - y, x^3*y - x, x*y^2 - x, y^3 - y], ctx=fmpz_mpoly_ctx(2, '<Ordering.lex: 'lex'>', ('x', 'y')))
>>> vec.buchberger_naive(limits=(2, 2, 512))
(fmpz_mpoly_vec([x^2 - y, x^3*y - x], ctx=fmpz_mpoly_ctx(2, '<Ordering.lex: 'lex'>', ('x', 'y'))), False)
>>> vec2.is_autoreduced()
False
>>> vec2.autoreduction()
fmpz_mpoly_vec([x^2 - y, y^3 - y, x*y^2 - x], ctx=fmpz_mpoly_ctx(2, '<Ordering.lex: 'lex'>', ('x', 'y')))

is_autoreduced(self) → bool

Check if self is auto-reduced (or inter-reduced).

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> f2 = 3*x**2 - y
>>> k = x*y - x
>>> k2 = 3*x*y - 3*x
>>> h = y**2 - y
>>> vec = fmpz_mpoly_vec([f2, k, h], ctx)
>>> vec.is_autoreduced()
True
>>> vec = fmpz_mpoly_vec([f2, k2, h], ctx)
>>> vec.is_autoreduced()
False

is_groebner(self, other=None) → bool

Check if self is a Gröbner basis. If other is not None then check if self is a Gröbner basis for other.

>>> ctx = fmpz_mpoly_ctx.get(('x', 'y'), 'lex')
>>> x, y = ctx.gens()
>>> f = x**2 - y
>>> g = x**3 - x
>>> k = x*y - x
>>> h = y**2 - y
>>> vec = fmpz_mpoly_vec([f, k, h], ctx)
>>> vec.is_groebner()
True
>>> vec.is_groebner(fmpz_mpoly_vec([f, g], ctx))
True
>>> vec.is_groebner(fmpz_mpoly_vec([f, x**3], ctx))
False