Algebraic numbers
Nemo allows working with exact real and complex algebraic numbers.
The default algebraic number type in Nemo is provided by Calcium. The associated field of algebraic numbers is represented by the constant parent object called CalciumQQBar.
For convenience we define
QQBar = CalciumQQBarso that algebraic numbers can be constructed using QQBar instead of CalciumQQBar. Note that this is the name of a specific parent object, not the name of its type.
| Library | Element type | Parent type |
|---|---|---|
| Calcium | qqbar | CalciumQQBarField |
Important note on performance
The default algebraic number type represents algebraic numbers in canonical form using minimal polynomials. This works well for representing individual algebraic numbers, but it does not provide the best performance for field arithmetic. For fast calculation in $\overline{\mathbb{Q}}$, CalciumField should typically be used instead (see the section on Exact real and complex numbers). Alternatively, to compute in a fixed subfield of $\overline{\mathbb{Q}}$, you may fix a generator $a$ and construct an Antic number field to represent $\mathbb{Q}(a)$.
Algebraic number functionality
Constructing algebraic numbers
Methods to construct algebraic numbers include:
- Conversion from other numbers and through arithmetic operations
- Computing the roots of a given polynomial
- Computing the eigenvalues of a given matrix
- Random generation
- Exact trigonometric functions (see later section)
- Guessing (see later section)
Examples
Arithmetic:
julia> ZZRingElem(QQBar(3))
3
julia> QQFieldElem(QQBar(3) // 2)
3//2
julia> QQBar(-1) ^ (QQBar(1) // 3)
Root 0.500000 + 0.866025*im of x^2 - x + 1Solving the quintic equation:
julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over QQ, x)
julia> v = roots(x^5-x-1, QQBar)
5-element Vector{qqbar}:
Root 1.16730 of x^5 - x - 1
Root 0.181232 + 1.08395*im of x^5 - x - 1
Root 0.181232 - 1.08395*im of x^5 - x - 1
Root -0.764884 + 0.352472*im of x^5 - x - 1
Root -0.764884 - 0.352472*im of x^5 - x - 1
julia> v[1]^5 - v[1] - 1 == 0
trueComputing exact eigenvalues of a matrix:
julia> eigenvalues(ZZ[1 1 0; 0 1 1; 1 0 1], QQBar)
3-element Vector{qqbar}:
Root 2.00000 of x - 2
Root 0.500000 + 0.866025*im of x^2 - x + 1
Root 0.500000 - 0.866025*im of x^2 - x + 1Interface
roots — Methodroots(f::ZZPolyRingElem, R::CalciumQQBarField)Return all the roots of the polynomial f in the field of algebraic numbers R. The output array is sorted in the default sort order for algebraic numbers. Roots of multiplicity higher than one are repeated according to their multiplicity.
roots — Methodroots(f::QQPolyRingElem, R::CalciumQQBarField)Return all the roots of the polynomial f in the field of algebraic numbers R. The output array is sorted in the default sort order for algebraic numbers. Roots of multiplicity higher than one are repeated according to their multiplicity.
eigenvalues — Methodeigenvalues(A::ZZMatrix, R::CalciumQQBarField)Return all the eigenvalues of the matrix A in the field of algebraic numbers R. The output array is sorted in the default sort order for algebraic numbers. Eigenvalues of multiplicity higher than one are repeated according to their multiplicity.
eigenvalues — Methodeigenvalues(A::QQMatrix, R::CalciumQQBarField)Return all the eigenvalues of the matrix A in the field of algebraic numbers R. The output array is sorted in the default sort order for algebraic numbers. Eigenvalues of multiplicity higher than one are repeated according to their multiplicity.
rand — Methodrand(R::CalciumQQBarField; degree::Int, bits::Int, randtype::Symbol=:null)Return a random algebraic number with degree up to degree and coefficients up to bits in size. By default, both real and complex numbers are generated. Set the optional randtype to :real or :nonreal to generate a specific type of number. Note that nonreal numbers require degree at least 2.
Numerical evaluation
Examples
Algebraic numbers can be evaluated numerically to arbitrary precision by converting to real or complex Arb fields:
julia> RR = ArbField(64); RR(sqrt(QQBar(2)))
[1.414213562373095049 +/- 3.45e-19]
julia> CC = AcbField(32); CC(QQBar(-1) ^ (QQBar(1) // 4))
[0.7071067812 +/- 1.35e-11] + [0.7071067812 +/- 1.35e-11]*imMinimal polynomials, conjugates, and properties
Examples
Retrieving the minimal polynomial and algebraic conjugates of a given algebraic number:
julia> minpoly(polynomial_ring(ZZ, "x")[1], QQBar(1+2im))
x^2 - 2*x + 5
julia> conjugates(QQBar(1+2im))
2-element Vector{qqbar}:
Root 1.00000 + 2.00000*im of x^2 - 2x + 5
Root 1.00000 - 2.00000*im of x^2 - 2x + 5Interface
iszero — Methodiszero(x::qqbar)Return whether x is the number 0.
isone — Methodisone(x::qqbar)Return whether x is the number 1.
isinteger — Methodisinteger(x::qqbar)Return whether x is an integer.
is_rational — Methodis_rational(x::qqbar)Return whether x is a rational number.
isreal — Methodisreal(x::qqbar)Return whether x is a real number.
degree — Methoddegree(x::qqbar)Return the degree of the minimal polynomial of x.
is_algebraic_integer — Methodis_algebraic_integer(x::qqbar)Return whether x is an algebraic integer.
minpoly — Methodminpoly(R::ZZPolyRing, x::qqbar)Return the minimal polynomial of x as an element of the polynomial ring R.
minpoly — Methodminpoly(R::ZZPolyRing, x::qqbar)Return the minimal polynomial of x as an element of the polynomial ring R.
conjugates — Methodconjugates(a::qqbar)Return all the roots of the polynomial f in the field of algebraic numbers R. The output array is sorted in the default sort order for algebraic numbers.
denominator — Methoddenominator(x::qqbar)Return the denominator of x, defined as the leading coefficient of the minimal polynomial of x. The result is returned as an ZZRingElem.
numerator — Methodnumerator(x::qqbar)Return the numerator of x, defined as x multiplied by its denominator. The result is an algebraic integer.
height — Methodheight(x::qqbar)Return the height of the algebraic number x. The result is an ZZRingElem integer.
height_bits — Methodheight_bits(x::qqbar)Return the height of the algebraic number x measured in bits. The result is a Julia integer.
Complex parts
Examples
julia> real(sqrt(QQBar(1im)))
Root 0.707107 of 2x^2 - 1
julia> abs(sqrt(QQBar(1im)))
Root 1.00000 of x - 1
julia> floor(sqrt(QQBar(1000)))
Root 31.0000 of x - 31
julia> sign(QQBar(-10-20im))
Root -0.447214 - 0.894427*im of 5x^4 + 6x^2 + 5Interface
real — Methodreal(a::qqbar)Return the real part of a.
imag — Methodimag(a::qqbar)Return the imaginary part of a.
abs — Methodabs(a::qqbar)Return the absolute value of a.
abs2 — Methodabs2(a::qqbar)Return the squared absolute value of a.
conj — Methodconj(a::qqbar)Return the complex conjugate of a.
sign — Methodsign(a::qqbar)Return the complex sign of a, defined as zero if a is zero and as $a / |a|$ otherwise.
csgn — Methodcsgn(a::qqbar)Return the extension of the real sign function taking the value 1 strictly in the right half plane, -1 strictly in the left half plane, and the sign of the imaginary part when on the imaginary axis. Equivalently, $\operatorname{csgn}(x) = x / \sqrt{x^2}$ except that the value is 0 at zero. The value is returned as a Julia integer.
sign_real — Methodsign_real(a::qqbar)Return the sign of the real part of a as a Julia integer.
sign_imag — Methodsign_imag(a::qqbar)Return the sign of the imaginary part of a as a Julia integer.
floor — Methodfloor(a::qqbar)Return the floor function of a as an algebraic number. Use ZZRingElem(floor(a)) to construct a Nemo integer instead.
ceil — Methodceil(a::qqbar)Return the ceiling function of b as an algebraic number. Use ZZRingElem(ceil(a)) to construct a Nemo integer instead.
Comparing algebraic numbers
The operators == and != check exactly for equality.
We provide various comparison functions for ordering algebraic numbers:
- Standard comparison for real numbers (
<,isless) - Real parts
- Imaginary parts
- Absolute values
- Absolute values of real or imaginary parts
- Root sort order
The standard comparison will throw if either argument is nonreal.
The various comparisons for complex parts are provided as separate operations since these functions are far more efficient than explicitly computing the complex parts and then doing real comparisons.
The root sort order is a total order for complex algebraic numbers used to order the output of roots and conjugates canonically. We define this order as follows: real roots come first, in descending order. Nonreal roots are subsequently ordered first by real part in descending order, then in ascending order by the absolute value of the imaginary part, and then in descending order of the sign of the imaginary part. This implies that complex conjugate roots are adjacent, with the root in the upper half plane first.
Examples
julia> 1 < sqrt(QQBar(2)) < QQBar(3)//2
true
julia> x = QQBar(3+4im)
Root 3.00000 + 4.00000*im of x^2 - 6x + 25
julia> is_equal_abs(x, -x)
true
julia> is_equal_abs_imag(x, 2-x)
true
julia> is_less_real(x, x // 2)
falseInterface
is_equal_real — Methodis_equal_real(a::qqbar, b::qqbar)Compares the real parts of a and b.
is_equal_imag — Methodis_equal_imag(a::qqbar, b::qqbar)Compares the imaginary parts of a and b.
is_equal_abs — Methodis_equal_abs(a::qqbar, b::qqbar)Compares the absolute values of a and b.
is_equal_abs_real — Methodis_equal_abs_real(a::qqbar, b::qqbar)Compares the absolute values of the real parts of a and b.
is_equal_abs_imag — Methodis_equal_abs_imag(a::qqbar, b::qqbar)Compares the absolute values of the imaginary parts of a and b.
is_less_real — Methodis_less_real(a::qqbar, b::qqbar)Compares the real parts of a and b.
is_less_imag — Methodis_less_imag(a::qqbar, b::qqbar)Compares the imaginary parts of a and b.
is_less_abs — Methodis_less_abs(a::qqbar, b::qqbar)Compares the absolute values of a and b.
is_less_abs_real — Methodis_less_abs_real(a::qqbar, b::qqbar)Compares the absolute values of the real parts of a and b.
is_less_abs_imag — Methodis_less_abs_imag(a::qqbar, b::qqbar)Compares the absolute values of the imaginary parts of a and b.
is_less_root_order — Methodis_less_root_order(a::qqbar, b::qqbar)Compares the a and b in root sort order.
Roots and trigonometric functions
Examples
julia> root(QQBar(2), 5)
Root 1.14870 of x^5 - 2
julia> sinpi(QQBar(7) // 13)
Root 0.992709 of 4096x^12 - 13312x^10 + 16640x^8 - 9984x^6 + 2912x^4 - 364x^2 + 13
julia> tanpi(atanpi(sqrt(QQBar(2)) + 1))
Root 2.41421 of x^2 - 2x - 1
julia> root_of_unity(QQBar, 5)
Root 0.309017 + 0.951057*im of x^4 + x^3 + x^2 + x + 1
julia> root_of_unity(QQBar, 5, 4)
Root 0.309017 - 0.951057*im of x^4 + x^3 + x^2 + x + 1
julia> w = (1 - sqrt(QQBar(-3)))//2
Root 0.500000 - 0.866025*im of x^2 - x + 1
julia> is_root_of_unity(w)
true
julia> is_root_of_unity(w + 1)
false
julia> root_of_unity_as_args(w)
(6, 5)Interface
sqrt — Methodsqrt(a::qqbar; check::Bool=true)Return the principal square root of a.
root — Methodroot(a::qqbar, n::Int)Return the principal n-th root of a. Requires positive n.
root_of_unity — Methodroot_of_unity(C::CalciumQQBarField, n::Int)Return the root of unity $e^{2 \pi i / n}$ as an element of the field of algebraic numbers C.
root_of_unity — Methodroot_of_unity(C::CalciumQQBarField, n::Int, k::Int)Return the root of unity $e^{2 \pi i k / n}$ as an element of the field of algebraic numbers C.
is_root_of_unity — Methodis_root_of_unity(a::qqbar)Return whether the given algebraic number is a root of unity.
root_of_unity_as_args — Methodroot_of_unity_as_args(a::qqbar)Return a pair of integers (q, p) such that the given a equals $e^{2 \pi i p / q}$. The denominator q will be minimal, with $0 \le p < q$. Throws if a is not a root of unity.
exp_pi_i — Methodexp_pi_i(a::qqbar)Return $e^{\pi i a}$ as an algebraic number. Throws if this value is transcendental.
log_pi_i — Methodlog_pi_i(a::qqbar)Return $\log(a) / (\pi i)$ as an algebraic number. Throws if this value is transcendental or undefined.
sinpi — Methodsinpi(a::qqbar)Return $\sin(\pi a)$ as an algebraic number. Throws if this value is transcendental.
cospi — Methodcospi(a::qqbar)Return $\cos(\pi a)$ as an algebraic number. Throws if this value is transcendental.
tanpi — Methodtanpi(a::qqbar)Return $\tan(\pi a)$ as an algebraic number. Throws if this value is transcendental or undefined.
asinpi — Methodasinpi(a::qqbar)Return $\operatorname{asin}(a) / \pi$ as an algebraic number. Throws if this value is transcendental.
acospi — Methodacospi(a::qqbar)Return $\operatorname{acos}(a) / \pi$ as an algebraic number. Throws if this value is transcendental.
atanpi — Methodatanpi(a::qqbar)Return $\operatorname{atan}(a) / \pi$ as an algebraic number. Throws if this value is transcendental or undefined.
Guessing
Examples
An algebraic number can be recovered from a numerical value:
julia> RR = ArbField(53); guess(QQBar, RR("1.41421356 +/- 1e-6"), 2)
Root 1.41421 of x^2 - 2Warning: the input should be an enclosure. If you have a floating-point approximation, you should add an error estimate; otherwise, the only algebraic number that can be guessed is the binary floating-point number itself.
julia> RR = ArbField(128);
julia> x = RR(0.1); # note: 53-bit binary approximation of 1//10 without radius
julia> guess(QQBar, x, 1)
Root 0.100000 of 36028797018963968x - 3602879701896397
julia> guess(QQBar, x + RR("+/- 1e-10"), 1)
Root 0.100000 of 10x - 1Interface
guess — Functionguess(R::CalciumQQBarField, x::acb, maxdeg::Int, maxbits::Int=0)Try to reconstruct an algebraic number from a given numerical enclosure x. The algorithm looks for candidates up to degree maxdeg and with coefficients up to size maxbits (which defaults to the precision of x if not given). Throws if no suitable algebraic number can be found.
Guessing typically requires high precision to succeed, and it does not make much sense to call this function with input precision smaller than $O(maxdeg \cdot maxbits)$. If this function succeeds, then the output is guaranteed to be contained in the enclosure x, but failure does not prove that such an algebraic number with the specified parameters does not exist.
This function does a single iteration with the target parameters. For best performance, one should invoke this function repeatedly with successively larger parameters when the size of the intended solution is unknown or may be much smaller than a worst-case bound.
guess — Functionguess(R::CalciumQQBarField, x::acb, maxdeg::Int, maxbits::Int=0)Try to reconstruct an algebraic number from a given numerical enclosure x. The algorithm looks for candidates up to degree maxdeg and with coefficients up to size maxbits (which defaults to the precision of x if not given). Throws if no suitable algebraic number can be found.
Guessing typically requires high precision to succeed, and it does not make much sense to call this function with input precision smaller than $O(maxdeg \cdot maxbits)$. If this function succeeds, then the output is guaranteed to be contained in the enclosure x, but failure does not prove that such an algebraic number with the specified parameters does not exist.
This function does a single iteration with the target parameters. For best performance, one should invoke this function repeatedly with successively larger parameters when the size of the intended solution is unknown or may be much smaller than a worst-case bound.