# 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)Arbarb_polyArbPolyRing
$\mathbb{C}$ (fixed precision)Arbacb_polyAcbPolyRing

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

evaluate2Method
evaluate2(x::RealPoly, y::RingElement)

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

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

Examples

RR = RealField(64)
T, z = polynomial_ring(RR, "z")

h = z^2 + 2z + 1

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

### Signature

signatureMethod
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)
signatureMethod
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)

### Root finding

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

Examples

CC = ComplexField(64)
C, y = polynomial_ring(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

from_rootsMethod
from_roots(R::ArbPolyRing, b::Vector{arb})

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

from_rootsMethod
from_roots(R::AcbPolyRing, b::Vector{acb})

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

Examples

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

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

### Bounding absolute values of roots

roots_upper_boundMethod
roots_upper_bound(x::RealPoly) -> arb

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

roots_upper_boundMethod
roots_upper_bound(x::ComplexPoly) -> 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}$.

liftMethod
lift(R::ZZPolyRing, y::zzModPolyRingElem)

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.

liftMethod
lift(R::ZZPolyRing, y::fpPolyRingElem)

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.

liftMethod
lift(R::ZZPolyRing, y::ZZModPolyRingElem)

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.

liftMethod
lift(R::ZZPolyRing, y::FpPolyRingElem)

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 = residue_ring(ZZ, 123456789012345678949)
S, x = polynomial_ring(R, "x")
T, y = polynomial_ring(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.

overlapsMethod
overlaps(x::RealPoly, y::RealPoly)

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

overlapsMethod
overlaps(x::ComplexPoly, y::ComplexPoly)

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

containsMethod
contains(x::RealPoly, y::RealPoly)

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

containsMethod
contains(x::ComplexPoly, y::ComplexPoly)

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

containsMethod
contains(x::RealPoly, y::ZZPolyRingElem)

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

containsMethod
contains(x::RealPoly, y::QQPolyRingElem)

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

containsMethod
contains(x::ComplexPoly, y::ZZPolyRingElem)

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

containsMethod
contains(x::ComplexPoly, y::QQPolyRingElem)

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.

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

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

Examples

RR = RealField(64)
CC = ComplexField(64)
R, x = polynomial_ring(RR, "x")
C, y = polynomial_ring(CC, "y")
Zx, zx = polynomial_ring(ZZ, "x")
Qx, qx = polynomial_ring(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

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.

factor_distinct_degMethod
factor_distinct_deg(x::zzModPolyRingElem)

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

factor_distinct_degMethod
factor_distinct_deg(x::fpPolyRingElem)

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

factor_distinct_degMethod
factor_distinct_deg(x::ZZModPolyRingElem)

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

factor_distinct_degMethod
factor_distinct_deg(x::ZZModPolyRingElem)

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

factor_distinct_degMethod
factor_distinct_deg(x::FqPolyRepPolyRingElem)

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

factor_distinct_degMethod
factor_distinct_deg(x::fqPolyRepPolyRingElem)

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

Examples

R = residue_ring(ZZ, 23)
S, x = polynomial_ring(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

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

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

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

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

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

Examples

R, x = polynomial_ring(ZZ, "x")
S, y = polynomial_ring(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)