GitHub

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 ringLibraryElement typeParent type
Generic ring $R$AbstractAlgebra.jlGeneric.Poly{T}Generic.PolyRing{T}
$\mathbb{Z}$FlintZZPolyRingElemZZPolyRing
$\mathbb{Z}/n\mathbb{Z}$ (small $n$)FlintzzModPolyRingElemzzModPolyRing
$\mathbb{Z}/n\mathbb{Z}$ (large $n$)FlintZZModPolyRingElemZZModPolyRing
$\mathbb{Q}$FlintQQPolyRingElemQQPolyRing
$\mathbb{Z}/p\mathbb{Z}$ (small prime $p$)FlintfpPolyRingElemfpPolyRing
$\mathbb{Z}/p\mathbb{Z}$ (large prime $p$)FlintFpPolyRingElemFpPolyRing
$\mathbb{F}_{p^n}$ (small $p$)FlintfqPolyRepPolyRingElemfqPolyRepPolyRing
$\mathbb{F}_{p^n}$ (large $p$)FlintFqPolyRepPolyRingElemFqPolyRepPolyRing
$\mathbb{R}$ (arbitrary precision)ArbRealPolyRealPolyRing
$\mathbb{C}$ (arbitrary precision)ArbComplexPolyComplexPolyRing
$\mathbb{R}$ (fixed precision)ArbArbPolyRingElemArbPolyRing
$\mathbb{C}$ (fixed precision)ArbAcbPolyRingElemAcbPolyRing

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 PolyRingElem 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 provide the AbstractAlgebra univariate polynomial functionality:

https://nemocas.github.io/AbstractAlgebra.jl/stable/polynomial

Generic polynomials are also available.

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::RealPoly, y::RingElement)

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

source
Nemo.evaluate2 — Method
evaluate2(x::ComplexPoly, y::RingElement; prec::Int = precision(Balls))

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

source

Examples

julia> RR = RealField()
Real field

julia> T, z = polynomial_ring(RR, "z")
(Univariate polynomial ring in z over RR, z)

julia> h = z^2 + 2z + 1
z^2 + 2.0000000000000000000*z + 1

julia> s, t = evaluate2(h, RR("2.0 +/- 0.1"))
([9e+0 +/- 0.611], [6e+0 +/- 0.201])

Signature

Nemo.signature — Method
signature(f::ZZPolyRingElem)

Return the signature of $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.

Examples

julia> R, x = polynomial_ring(ZZ, "x");

julia> signature(x^3 + 3x + 1)
(1, 1)
source
Nemo.signature — Method
signature(f::QQPolyRingElem)

Return the signature of $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.

Examples

julia> R, x = polynomial_ring(QQ, "x");

julia> signature(x^3 + 3x + 1)
(1, 1)
source

Root finding

AbstractAlgebra.Generic.roots — Method
roots(x::ComplexPoly; 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.

source

Examples

julia> CC = ComplexField()
Complex field

julia> C, y = polynomial_ring(CC, "y")
(Univariate polynomial ring in y over CC, y)

julia> m = y^2 + 2y + 3
y^2 + 2.0000000000000000000*y + 3.0000000000000000000

julia> n = m + CC("0 +/- 0.0001", "0 +/- 0.0001")
y^2 + 2.0000000000000000000*y + [3.000 +/- 1.01e-4] + [+/- 1.01e-4]*im

julia> r = roots(n);

julia> sort(r; by=x->(real(x), imag(x))) # sort roots to make printing consistent
2-element Vector{ComplexFieldElem}:
 [-1.00 +/- 1.01e-4] + [-1.414 +/- 3.14e-4]*im
 [-1.00 +/- 1.01e-4] + [1.414 +/- 3.14e-4]*im

julia> p = y^7 - 1
y^7 - 1.0000000000000000000

julia> r = roots(n, isolate_real = true);

julia> sort(r; by=x->(real(x), imag(x))) # sort roots to make printing consistent
2-element Vector{ComplexFieldElem}:
 [-1.00 +/- 1.01e-4] + [-1.414 +/- 3.14e-4]*im
 [-1.00 +/- 1.01e-4] + [1.414 +/- 3.14e-4]*im

Construction from roots

Nemo.from_roots — Method
from_roots(R::ArbPolyRing, b::Vector{ArbFieldElem})

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

source
Nemo.from_roots — Method
from_roots(R::AcbPolyRing, b::Vector{AcbFieldElem})

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

source

Examples

julia> RR = RealField()
Real field

julia> R, x = polynomial_ring(RR, "x")
(Univariate polynomial ring in x over RR, x)

julia> xs = [inv(RR(i)) for i=1:5]
5-element Vector{RealFieldElem}:
 1.0000000000000000000
 0.50000000000000000000
 [0.3333333333333333333 +/- 4.24e-20]
 0.25000000000000000000
 [0.2000000000000000000 +/- 2.44e-20]

julia> f = from_roots(R, xs)
x^5 + [-2.283333333333333333 +/- 4.54e-19]*x^4 + [1.875000000000000000 +/- 5.10e-19]*x^3 + [-0.708333333333333333 +/- 3.99e-19]*x^2 + [0.1250000000000000000 +/- 3.69e-20]*x + [-0.00833333333333333333 +/- 4.13e-21]

julia> all(x -> contains_zero(evaluate(f, x)), xs)
true

Bounding absolute values of roots

Nemo.roots_upper_bound — Method
roots_upper_bound(x::RealPoly) -> ArbFieldElem

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

source
Nemo.roots_upper_bound — Method
roots_upper_bound(x::ComplexPoly) -> ArbFieldElem

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

source

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}$.

AbstractAlgebra.lift — Method
lift(R::ZZPolyRing, y::zzModPolyRingElem)

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

source
AbstractAlgebra.lift — Method
lift(R::ZZPolyRing, y::fpPolyRingElem)

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

source
AbstractAlgebra.lift — Method
lift(R::ZZPolyRing, y::ZZModPolyRingElem)

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

source
AbstractAlgebra.lift — Method
lift(R::ZZPolyRing, y::FpPolyRingElem)

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

source

Examples

julia> R, = residue_ring(ZZ, 123456789012345678949)
(Integers modulo 123456789012345678949, Map: ZZ -> ZZ/(123456789012345678949))

julia> S, x = polynomial_ring(R, "x")
(Univariate polynomial ring in x over ZZ/(123456789012345678949), x)

julia> T, y = polynomial_ring(ZZ, "y")
(Univariate polynomial ring in y over ZZ, y)

julia> f = x^2 + 2x + 1
x^2 + 2*x + 1

julia> a = lift(T, f)
y^2 + 2*y + 1

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::RealPoly, y::RealPoly)

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

source
Nemo.overlaps — Method
overlaps(x::ComplexPoly, y::ComplexPoly)

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

source
Base.contains — Method
contains(x::RealPoly, y::RealPoly)

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

source
Base.contains — Method
contains(x::ComplexPoly, y::ComplexPoly)

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

source
Base.contains — Method
contains(x::RealPoly, y::ZZPolyRingElem)

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

source
Base.contains — Method
contains(x::RealPoly, y::QQPolyRingElem)

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

source
Base.contains — Method
contains(x::ComplexPoly, y::ZZPolyRingElem)

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

source
Base.contains — Method
contains(x::ComplexPoly, y::QQPolyRingElem)

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

source

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::RealPoly)

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.

source
Nemo.unique_integer — Method
unique_integer(x::ComplexPoly)

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.

source

Examples

julia> RR = RealField()
Real field

julia> R, x = polynomial_ring(RR, "x")
(Univariate polynomial ring in x over RR, x)

julia> f = x^2 + 2x + 1
x^2 + 2.0000000000000000000*x + 1

julia> h = f + RR("0 +/- 0.0001")
x^2 + 2.0000000000000000000*x + [1.000 +/- 1.01e-4]

julia> k = f + RR("0 +/- 0.0001") * x^4
[+/- 1.01e-4]*x^4 + x^2 + 2.0000000000000000000*x + 1

julia> contains(h, f)
true

julia> overlaps(f, k)
true

julia> t, z = unique_integer(k)
(true, x^2 + 2*x + 1)
julia> CC = ComplexField()
Complex field

julia> C, y = polynomial_ring(CC, "y")
(Univariate polynomial ring in y over CC, y)

julia> m = y^2 + 2y + 1
y^2 + 2.0000000000000000000*y + 1

julia> n = m + CC("0 +/- 0.0001", "0 +/- 0.0001")
y^2 + 2.0000000000000000000*y + [1.000 +/- 1.01e-4] + [+/- 1.01e-4]*im

julia> contains(n, m)
true

julia> isreal(n)
false

julia> isreal(m)
true

Factorisation

Certain polynomials can be factored (ZZPolyRingElem',zzModPolyRingElem,fpPolyRingElem,ZZModPolyRingElem,FpPolyRingElem,FqPolyRepPolyRingElem,fqPolyRepPolyRingElem`) and the interface follows the specification in AbstractAlgebra.jl. The following additional functions are available.

Nemo.factor_distinct_deg — Method
factor_distinct_deg(x::zzModPolyRingElem)

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

source
Nemo.factor_distinct_deg — Method
factor_distinct_deg(x::fpPolyRingElem)

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

source
Nemo.factor_distinct_deg — Method
factor_distinct_deg(x::ZZModPolyRingElem)

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

source
Nemo.factor_distinct_deg — Method
factor_distinct_deg(x::ZZModPolyRingElem)

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

source
Nemo.factor_distinct_deg — Method
factor_distinct_deg(x::FqPolyRepPolyRingElem)

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

source
Nemo.factor_distinct_deg — Method
factor_distinct_deg(x::fqPolyRepPolyRingElem)

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

source

Examples

julia> R, = residue_ring(ZZ, 23)
(Integers modulo 23, Map: ZZ -> ZZ/(23))

julia> S, x = polynomial_ring(R, "x")
(Univariate polynomial ring in x over ZZ/(23), x)

julia> f = x^2 + 2x + 1
x^2 + 2*x + 1

julia> g = x^3 + 3x + 1
x^3 + 3*x + 1

julia> R = factor(f*g)
1 * (x + 1)^2 * (x^3 + 3*x + 1)

julia> S = factor_squarefree(f*g)
1 * (x + 1)^2 * (x^3 + 3*x + 1)

julia> T = factor_distinct_deg((x + 1)*g*(x^5+x^3+x+1))
Dict{Int64, zzModPolyRingElem} with 3 entries:
  4 => x^4 + 7*x^3 + 4*x^2 + 5*x + 13
  3 => x^3 + 3*x + 1
  1 => x^2 + 17*x + 16

Special functions

Nemo.cyclotomic — Method
cyclotomic(n::Int, x::ZZPolyRingElem)

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.

source
Nemo.swinnerton_dyer — Method
swinnerton_dyer(n::Int, x::ZZPolyRingElem)

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}$).

source
Nemo.cos_minpoly — Method
cos_minpoly(n::Int, x::ZZPolyRingElem)

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$.

source
Nemo.theta_qexp — Method
theta_qexp(e::Int, n::Int, x::ZZPolyRingElem)

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}$.

source
Nemo.eta_qexp — Method
eta_qexp(e::Int, n::Int, x::ZZPolyRingElem)

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)$.

source

Examples

julia> R, x = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over ZZ, x)

julia> h = cyclotomic(120, x)
x^32 + x^28 - x^20 - x^16 - x^12 + x^4 + 1

julia> j = swinnerton_dyer(5, x)
x^32 - 448*x^30 + 84864*x^28 - 9028096*x^26 + 602397952*x^24 - 26625650688*x^22 + 801918722048*x^20 - 16665641517056*x^18 + 239210760462336*x^16 - 2349014746136576*x^14 + 15459151516270592*x^12 - 65892492886671360*x^10 + 172580952324702208*x^8 - 255690851718529024*x^6 + 183876928237731840*x^4 - 44660812492570624*x^2 + 2000989041197056

julia> k = cos_minpoly(30, x)
x^4 + x^3 - 4*x^2 - 4*x + 1

julia> l = theta_qexp(3, 30, x)
72*x^29 + 32*x^27 + 72*x^26 + 30*x^25 + 24*x^24 + 24*x^22 + 48*x^21 + 24*x^20 + 24*x^19 + 36*x^18 + 48*x^17 + 6*x^16 + 48*x^14 + 24*x^13 + 8*x^12 + 24*x^11 + 24*x^10 + 30*x^9 + 12*x^8 + 24*x^6 + 24*x^5 + 6*x^4 + 8*x^3 + 12*x^2 + 6*x + 1

julia> m = eta_qexp(24, 30, x)
-29211840*x^29 + 128406630*x^28 + 24647168*x^27 - 73279080*x^26 + 13865712*x^25 - 25499225*x^24 + 21288960*x^23 + 18643272*x^22 - 12830688*x^21 - 4219488*x^20 - 7109760*x^19 + 10661420*x^18 + 2727432*x^17 - 6905934*x^16 + 987136*x^15 + 1217160*x^14 + 401856*x^13 - 577738*x^12 - 370944*x^11 + 534612*x^10 - 115920*x^9 - 113643*x^8 + 84480*x^7 - 16744*x^6 - 6048*x^5 + 4830*x^4 - 1472*x^3 + 252*x^2 - 24*x + 1

julia> o = cyclotomic(10, 1 + x + x^2)
x^8 + 4*x^7 + 9*x^6 + 13*x^5 + 14*x^4 + 11*x^3 + 6*x^2 + 2*x + 1