Univariate polynomials

Introduction

Nemo allow the creation of dense, univariate polynomials over any computable ring $R$. There are two different kinds of implementation: a generic one for the case where no specific implementation exists (provided by AbstractAlgebra.jl), and efficient implementations of polynomials over numerous specific rings, usually provided by C/C++ libraries.

The following table shows each of the polynomial types available in Nemo, the base ring $R$, and the Julia/Nemo types for that kind of polynomial (the type information is mainly of concern to developers).

Base ring	Library	Element type	Parent type
Generic ring $R$	AbstractAlgebra.jl	`Generic.Poly{T}`	`Generic.PolyRing{T}`
$\mathbb{Z}$	Flint	`fmpz_poly`	`FmpzPolyRing`
$\mathbb{Z}/n\mathbb{Z}$ (small $n$)	Flint	`nmod_poly`	`NmodPolyRing`
$\mathbb{Z}/n\mathbb{Z}$ (large $n$)	Flint	`fmpz_mod_poly`	`FmpzModPolyRing`
$\mathbb{Q}$	Flint	`fmpq_poly`	`FmpqPolyRing`
$\mathbb{Z}/p\mathbb{Z}$ (small prime $p$)	Flint	`gfp_poly`	`GFPPolyRing`
$\mathbb{Z}/p\mathbb{Z}$ (large prime $p$)	Flint	`gfp_fmpz_poly`	`GFPFmpzPolyRing`
$\mathbb{F}_{p^n}$ (small $p$)	Flint	`fq_nmod_poly`	`FqNmodPolyRing`
$\mathbb{F}_{p^n}$ (large $p$)	Flint	`fq_poly`	`FqPolyRing`
$\mathbb{R}$	Arb	`arb_poly`	`ArbPolyRing`
$\mathbb{C}$	Arb	`acb_poly`	`AcbPolyRing`

The string representation of the variable and the base ring $R$ of a generic polynomial is stored in its parent object.

All polynomial element types belong to the abstract type PolyElem and all of the polynomial ring types belong to the abstract type PolyRing. This enables one to write generic functions that can accept any Nemo univariate polynomial type.

Polynomial functionality

All univariate polynomial types in Nemo follow the AbstractAlgebra.jl univariate polynomial interface:

https://nemocas.github.io/AbstractAlgebra.jl/polynomial_rings.html

Generic polynomials are also available, and Nemo univariate polynomial types also implement all of the same functionality.

We describe here only functions that are in addition to that guaranteed by AbstractAlgebra.jl, for specific coefficient rings.

Remove and valuation

Nemo.evaluate2 — Method.

evaluate2(x::arb_poly, y::Integer)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::arb_poly, y::Float64)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::arb_poly, y::fmpz)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::arb_poly, y::fmpq)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::arb_poly, y::arb)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::arb_poly, y::acb)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::acb_poly, y::Integer)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::acb_poly, y::Float64)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::acb_poly, y::fmpz)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::acb_poly, y::fmpq)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::acb_poly, y::arb)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Nemo.evaluate2 — Method.

evaluate2(x::acb_poly, y::acb)

Return a tuple $p, q$ consisting of the polynomial $x$ evaluated at $y$ and its derivative evaluated at $y$.

Examples

RR = RealField(64)
T, z = PolynomialRing(RR, "z")
   
h = z^2 + 2z + 1

s, t = evaluate2(h, RR("2.0 +/- 0.1"))

Signature

Nemo.signature — Method.

signature(f::fmpz_poly)

Return the signature of the polynomial $f$, i.e. a tuple $(r, s)$ such that $r$ is the number of real roots of $f$ and $s$ is half the number of complex roots.

Nemo.signature — Method.

signature(f::fmpq_poly)

Return the signature of $f$, i.e. a tuple $(r, s)$ where $r$ is the number of real roots of $f$ and $s$ is half the number of complex roots.

Examples

R, x = PolynomialRing(ZZ, "x")

f = x^3 + 3x + 1

(r, s) = signature(f)

Root finding

Nemo.roots — Method.

roots(x::acb_poly; target=0, isolate_real=false, initial_prec=0, max_prec=0, max_iter=0)

Attempts to isolate the complex roots of the complex polynomial $x$ by iteratively refining balls in which they lie.
This is done by increasing the working precision, starting at initial_prec. The maximal number of iterations can be set using max_iter and the maximal precision can be set using max_prec.
If isolate_real is set and $x$ is strictly real, then the real roots will be isolated from the non-real roots. Every root will have either zero, positive or negative real part.
It is assumed that $x$ is squarefree.

Examples

CC = ComplexField(64)
C, y = PolynomialRing(CC, "y")

m = y^2 + 2y + 3
n = m + CC("0 +/- 0.0001", "0 +/- 0.0001")

r = roots(n)

p = y^7 - 1

r = roots(n, isolate_real = true)

Construction from roots

Nemo.from_roots — Method.

from_roots(R::ArbPolyRing, b::Array{arb, 1})

Construct a polynomial in the given polynomial ring from a list of its roots.

Nemo.from_roots — Method.

from_roots(R::AcbPolyRing, b::Array{acb, 1})

Construct a polynomial in the given polynomial ring from a list of its roots.

Examples

RR = RealField(64)
R, x = PolynomialRing(RR, "x")

xs = arb[inv(RR(i)) for i=1:5]
f = from_roots(R, xs)

Bounding absolute values of roots

Nemo.roots_upper_bound — Method.

roots_upper_bound(x::arb_poly) -> arb

Returns an upper bound for the absolute value of all complex roots of $x$.

Nemo.roots_upper_bound — Method.

roots_upper_bound(x::acb_poly) -> arb

Returns an upper bound for the absolute value of all complex roots of $x$.

Lifting

When working over a residue ring it is useful to be able to lift to the base ring of the residue ring, e.g. from $\mathbb{Z}/n\mathbb{Z}$ to $\mathbb{Z}$.

Nemo.lift — Method.

function lift(R::FmpzPolyRing, y::nmod_poly)

Lift from a polynomial over $\mathbb{Z}/n\mathbb{Z}$ to a polynomial over $\mathbb{Z}$ with minimal reduced nonnegative coefficients. The ring R specifies the ring to lift into.

Nemo.lift — Method.

lift(R::FmpzPolyRing, y::gfp_poly)

Lift from a polynomial over $\mathbb{Z}/n\mathbb{Z}$ to a polynomial over $\mathbb{Z}$ with minimal reduced nonnegative coefficients. The ring R specifies the ring to lift into.

Nemo.lift — Method.

function lift(R::FmpzPolyRing, y::fmpz_mod_poly)

Lift from a polynomial over $\mathbb{Z}/n\mathbb{Z}$ to a polynomial over $\mathbb{Z}$ with minimal reduced nonnegative coefficients. The ring R specifies the ring to lift into.

Nemo.lift — Method.

function lift(R::FmpzPolyRing, y::gfp_fmpz_poly)

Lift from a polynomial over $\mathbb{Z}/n\mathbb{Z}$ to a polynomial over $\mathbb{Z}$ with minimal reduced nonnegative coefficients. The ring R specifies the ring to lift into.

Examples

R = ResidueRing(ZZ, 123456789012345678949)
S, x = PolynomialRing(R, "x")
T, y = PolynomialRing(ZZ, "y")

f = x^2 + 2x + 1

a = lift(T, f)

Overlapping and containment

Occasionally it is useful to be able to tell when inexact polynomials overlap or contain other exact or inexact polynomials. The following functions are provided for this purpose.

Nemo.overlaps — Method.

overlaps(x::arb_poly, y::arb_poly)

Return true if the coefficient balls of $x$ overlap the coefficient balls of $y$, otherwise return false.

Nemo.overlaps — Method.

overlaps(x::acb_poly, y::acb_poly)

Return true if the coefficient boxes of $x$ overlap the coefficient boxes of $y$, otherwise return false.

Nemo.contains — Method.

contains(x::arb_poly, y::arb_poly)

Return true if the coefficient balls of $x$ contain the corresponding coefficient balls of $y$, otherwise return false.

Nemo.contains — Method.

contains(x::acb_poly, y::acb_poly)

Return true if the coefficient boxes of $x$ contain the corresponding coefficient boxes of $y$, otherwise return false.

Nemo.contains — Method.

contains(x::arb_poly, y::fmpz_poly)

Return true if the coefficient balls of $x$ contain the corresponding exact coefficients of $y$, otherwise return false.

Nemo.contains — Method.

contains(x::arb_poly, y::fmpq_poly)

Return true if the coefficient balls of $x$ contain the corresponding exact coefficients of $y$, otherwise return false.

Nemo.contains — Method.

contains(x::acb_poly, y::fmpz_poly)

Return true if the coefficient boxes of $x$ contain the corresponding exact coefficients of $y$, otherwise return false.

Nemo.contains — Method.

contains(x::acb_poly, y::fmpq_poly)

Return true if the coefficient boxes of $x$ contain the corresponding exact coefficients of $y$, otherwise return false.

It is sometimes also useful to be able to determine if there is a unique integer contained in the coefficient of an inexact constant polynomial.

Nemo.unique_integer — Method.

unique_integer(x::arb_poly)

Return a tuple (t, z) where $t$ is true if there is a unique integer contained in each of the coefficients of $x$, otherwise sets $t$ to false. In the former case, $z$ is set to the integer polynomial.

Nemo.unique_integer — Method.

unique_integer(x::acb_poly)

Return a tuple (t, z) where $t$ is true if there is a unique integer contained in the (constant) polynomial $x$, along with that integer $z$ in case it is, otherwise sets $t$ to false.

We also have the following functions.

Base.isreal — Method.

isreal(x::acb_poly)

Return true if all the coefficients of $x$ are real, i.e. have exact zero imaginary parts.

Examples

RR = RealField(64)
CC = ComplexField(64)
R, x = PolynomialRing(RR, "x")
C, y = PolynomialRing(CC, "y")
Zx, zx = PolynomialRing(ZZ, "x")
Qx, qx = PolynomialRing(QQ, "x")

f = x^2 + 2x + 1
h = f + RR("0 +/- 0.0001")
k = f + RR("0 +/- 0.0001") * x^4
m = y^2 + 2y + 1
n = m + CC("0 +/- 0.0001", "0 +/- 0.0001")

contains(h, f)
overlaps(f, k)
contains(n, m)
t, z = unique_integer(k)
isreal(n)

Factorisation

Polynomials can be factorised over certain rings. In general we use the same format for the output as the Julia factorisation function, namely an associative array with polynomial factors as keys and exponents as values.

Nemo.isirreducible — Method.

isirreducible(x::nmod_poly)

Return true if $x$ is irreducible, otherwise return false.

Nemo.isirreducible — Method.

isirreducible(x::gfp_poly)

Return true if $x$ is irreducible, otherwise return false.

Nemo.isirreducible — Method.

isirreducible(x::fmpz_mod_poly)

Return true if $x$ is irreducible, otherwise return false.

Nemo.isirreducible — Method.

isirreducible(x::gfp_fmpz_poly)

Return true if $x$ is irreducible, otherwise return false.

Nemo.isirreducible — Method.

isirreducible(x::fq_poly)

Return true if $x$ is irreducible, otherwise return false.

Nemo.isirreducible — Method.

isirreducible(x::fq_nmod_poly)

Return true if $x$ is irreducible, otherwise return false.

Nemo.issquarefree — Method.

issquarefree(x::nmod_poly)

Return true if $x$ is squarefree, otherwise return false.

Nemo.issquarefree — Method.

issquarefree(x::gfp_poly)

Return true if $x$ is squarefree, otherwise return false.

Nemo.issquarefree — Method.

issquarefree(x::fmpz_mod_poly)

Return true if $x$ is squarefree, otherwise return false.

Nemo.issquarefree — Method.

issquarefree(x::gfp_fmpz_poly)

Return true if $x$ is squarefree, otherwise return false.

Nemo.issquarefree — Method.

issquarefree(x::fq_poly)

Return true if $x$ is squarefree, otherwise return false.

Nemo.issquarefree — Method.

issquarefree(x::fq_nmod_poly)

Return true if $x$ is squarefree, otherwise return false.

Nemo.factor — Method.

factor(x::fmpz_poly)

Returns the factorization of $x$.

Nemo.factor — Method.

factor(x::nmod_poly)

Return the factorisation of $x$.

Nemo.factor — Method.

factor(x::gfp_poly)

Return the factorisation of $x$.

Nemo.factor — Method.

factor(x::fmpz_mod_poly)

Return the factorisation of $x$.

Nemo.factor — Method.

factor(x::gfp_fmpz_poly)

Return the factorisation of $x$.

Nemo.factor — Method.

factor(x::fq_poly)

Return the factorisation of $x$.

Nemo.factor — Method.

factor(x::fq_nmod_poly)

Return the factorisation of $x$.

Nemo.factor_squarefree — Method.

factor_squarefree(x::nmod_poly)

Return the squarefree factorisation of $x$.

Nemo.factor_squarefree — Method.

factor_squarefree(x::gfp_poly)

Return the squarefree factorisation of $x$.

Nemo.factor_squarefree — Method.

factor_squarefree(x::fmpz_mod_poly)

Return the squarefree factorisation of $x$.

Nemo.factor_squarefree — Method.

factor_squarefree(x::gfp_fmpz_poly)

Return the squarefree factorisation of $x$.

Nemo.factor_squarefree — Method.

factor_squarefree(x::fq_poly)

Return the squarefree factorisation of $x$.

Nemo.factor_squarefree — Method.

factor_squarefree(x::fq_nmod_poly)

Return the squarefree factorisation of $x$.

Nemo.factor_distinct_deg — Method.

factor_distinct_deg(x::nmod_poly)

Return the distinct degree factorisation of a squarefree polynomial $x$.

Nemo.factor_distinct_deg — Method.

factor_distinct_deg(x::gfp_poly)

Return the distinct degree factorisation of a squarefree polynomial $x$.

Nemo.factor_distinct_deg — Method.

factor_distinct_deg(x::fmpz_mod_poly)

Return the distinct degree factorisation of a squarefree polynomial $x$.

Nemo.factor_distinct_deg — Method.

factor_distinct_deg(x::fmpz_mod_poly)

Return the distinct degree factorisation of a squarefree polynomial $x$.

Nemo.factor_distinct_deg — Method.

factor_distinct_deg(x::fq_poly)

Return the distinct degree factorisation of a squarefree polynomial $x$.

Nemo.factor_distinct_deg — Method.

factor_distinct_deg(x::fq_nmod_poly)

Return the distinct degree factorisation of a squarefree polynomial $x$.

Examples

R = ResidueRing(ZZ, 23)
S, x = PolynomialRing(R, "x")

f = x^2 + 2x + 1
g = x^3 + 3x + 1

R = factor(f*g)
S = factor_squarefree(f*g)
T = factor_distinct_deg((x + 1)*g*(x^5+x^3+x+1))

Special functions

Nemo.cyclotomic — Method.

cyclotomic(n::Int, x::fmpz_poly)

Return the $n$th cyclotomic polynomial, defined as $\Phi_n(x) = \prod_{\omega} (x-\omega),$ where $\omega$ runs over all the $n$th primitive roots of unity.

Nemo.swinnerton_dyer — Method.

swinnerton_dyer(n::Int, x::fmpz_poly)

Return the Swinnerton-Dyer polynomial $S_n$, defined as the integer polynomial $S_n = \prod (x \pm \sqrt{2} \pm \sqrt{3} \pm \sqrt{5} \pm \ldots \pm \sqrt{p_n})$ where $p_n$ denotes the $n$-th prime number and all combinations of signs are taken. This polynomial has degree $2^n$ and is irreducible over the integers (it is the minimal polynomial of $\sqrt{2} + \ldots + \sqrt{p_n}$).

Nemo.cos_minpoly — Method.

cos_minpoly(n::Int, x::fmpz_poly)

Return the minimal polynomial of $2 \cos(2 \pi / n)$. For suitable choice of $n$, this gives the minimal polynomial of $2 \cos(a \pi)$ or $2 \sin(a \pi)$ for any rational $a$.

Nemo.theta_qexp — Method.

theta_qexp(e::Int, n::Int, x::fmpz_poly)

Return the $q$-expansion to length $n$ of the Jacobi theta function raised to the power $r$, i.e. $\vartheta(q)^r$ where $\vartheta(q) = 1 + \sum_{k=1}^{\infty} q^{k^2}$.

Nemo.eta_qexp — Method.

eta_qexp(e::Int, n::Int, x::fmpz_poly)

Return the $q$-expansion to length $n$ of the Dedekind eta function (without the leading factor $q^{1/24}$) raised to the power $r$, i.e. $(q^{-1/24} \eta(q))^r = \prod_{k=1}^{\infty} (1 - q^k)^r$. In particular, $r = -1$ gives the generating function of the partition function $p(k)$, and $r = 24$ gives, after multiplication by $q$, the modular discriminant $\Delta(q)$ which generates the Ramanujan tau function $\tau(k)$.

Examples

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

h = cyclotomic(120, x)
j = swinnerton_dyer(5, x)
k = cos_minpoly(30, x)
l = theta_qexp(3, 30, x)
m = eta_qexp(24, 30, x)
o = cyclotomic(10, 1 + x + x^2)