# 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 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::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)`

`Nemo.evaluate2`

— Method`evaluate2(x::arb_poly, y::arb)`

`Nemo.evaluate2`

— Method`evaluate2(x::arb_poly, y::acb)`

`Nemo.evaluate2`

— Method`evaluate2(x::acb_poly, y::Integer)`

`Nemo.evaluate2`

— Method`evaluate2(x::acb_poly, y::Float64)`

`Nemo.evaluate2`

— Method`evaluate2(x::acb_poly, y::fmpz)`

`Nemo.evaluate2`

— Method`evaluate2(x::acb_poly, y::fmpq)`

`Nemo.evaluate2`

— Method`evaluate2(x::acb_poly, y::arb)`

`Nemo.evaluate2`

— Method`evaluate2(x::acb_poly, y::acb)`

**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

`AbstractAlgebra.Generic.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::Vector{arb})`

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

`Nemo.from_roots`

— Method`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 = 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}$.

`AbstractAlgebra.lift`

— Method`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.

`AbstractAlgebra.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.

`AbstractAlgebra.lift`

— Method`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.

`AbstractAlgebra.lift`

— Method`lift(R::FmpzPolyRing, y::gfp_fmpz_poly)`

`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`

.

`Base.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`

.

`Base.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`

.

`Base.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`

.

`Base.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`

.

`Base.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`

.

`Base.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`

.

**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

Certain polynomials can be factored (`fmpz_poly',`

nmod*poly ,gfp*poly

`,`

fmpz*mod*poly

`,`

gfp*fmpz*poly

`,`

fq*poly*nmod_poly`) and the interface follows the specification in AbstractAlgebra.jl. The following additional functions are available.

`,`

fq`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)
```