GitHub

Algebraic closure of the rational numbers

An implementation of the field of all algebraic numbers, that is, an algebraic closure of the field of rational numbers, is provided through the type QQBarField and the corresponding element type QQBarFieldElem.

Note that the field of algebraic closure is implemented as an ordered field; see Comparing algebraic numbers.

Constructing the field of algebraic numbers

julia> algebraic_closure(QQ)
Algebraic closure of rational field

Printing

Before looking at examples, we comment on the printing of algebraic numbers. As an illustration, consider the algebraic number $\sqrt[3]{2}$ with minimal polynomial $X^3 - 2$. This is printed as follows:

julia> Qbar = algebraic_closure(QQ);

julia> z = root(Qbar(2), 3)
{a3: 1.25992}

julia> Qx, x = QQ[:x]
(Univariate polynomial ring in x over QQ, x)

julia> minpoly(Qx, z) # to see the minimal polynomial
x^3 - 2

The first part a3 indicates that this is an algebraic number of degree $3$, which is followed by 1.25992, an approximation of the root.

Algebraic number functionality

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> Qb = algebraic_closure(QQ);

julia> ZZRingElem(Qb(3))
3

julia> QQFieldElem(Qb(3) // 2)
3//2

julia> Qb(-1) ^ (Qb(1) // 3)
{a2: 0.500000 + 0.866025*im}

Solving the quintic equation:

julia> Qb = algebraic_closure(QQ);

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

julia> v = roots(Qb, x^5-x-1)
5-element Vector{QQBarFieldElem}:
 {a5: 1.16730}
 {a5: 0.181232 + 1.08395*im}
 {a5: 0.181232 - 1.08395*im}
 {a5: -0.764884 + 0.352472*im}
 {a5: -0.764884 - 0.352472*im}

julia> v[1]^5 - v[1] - 1 == 0
true

Computing exact eigenvalues of a matrix:

julia> Qb = algebraic_closure(QQ);

julia> eigenvalues(Qb, ZZ[1 1 0; 0 1 1; 1 0 1])
3-element Vector{QQBarFieldElem}:
 {a1: 2.00000}
 {a2: 0.500000 + 0.866025*im}
 {a2: 0.500000 - 0.866025*im}

Interface

roots — Method
roots(R::QQBarField, f::ZZPolyRingElem)

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.

source
roots — Method
roots(R::QQBarField, f::QQPolyRingElem)

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.

source
eigenvalues — Method
eigenvalues(R::QQBarField, A::ZZMatrix)
eigenvalues(R::QQBarField, A::QQMatrix)

Return the eigenvalues A in the field of algebraic numbers R. The output array is sorted in the default sort order for algebraic numbers.

source
eigenvalues(L::Field, M::MatElem{T}) where T <: RingElem

Return the eigenvalues of M over the field L.

source
eigenvalues_with_multiplicities — Method
eigenvalues_with_multiplicities(R::QQBarField, A::ZZMatrix)
eigenvalues_with_multiplicities(R::QQBarField, A::QQMatrix)

Return the eigenvalues A in the field of algebraic numbers R together with their algebraic multiplicities as a vector of tuples. The output array is sorted in the default sort order for algebraic numbers.

source
eigenvalues_with_multiplicities(L::Field, M::MatElem{T}) where T <: RingElem

Return the eigenvalues of M over the field L together with their algebraic multiplicities as a vector of tuples.

source
eigenvalues — Method
eigenvalues(R::QQBarField, A::ZZMatrix)
eigenvalues(R::QQBarField, A::QQMatrix)

Return the eigenvalues A in the field of algebraic numbers R. The output array is sorted in the default sort order for algebraic numbers.

source
eigenvalues(L::Field, M::MatElem{T}) where T <: RingElem

Return the eigenvalues of M over the field L.

source
eigenvalues_with_multiplicities — Method
eigenvalues_with_multiplicities(R::QQBarField, A::ZZMatrix)
eigenvalues_with_multiplicities(R::QQBarField, A::QQMatrix)

Return the eigenvalues A in the field of algebraic numbers R together with their algebraic multiplicities as a vector of tuples. The output array is sorted in the default sort order for algebraic numbers.

source
eigenvalues_with_multiplicities(L::Field, M::MatElem{T}) where T <: RingElem

Return the eigenvalues of M over the field L together with their algebraic multiplicities as a vector of tuples.

source
rand — Method
rand(R::QQBarField; 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.

source

Numerical evaluation

Examples

Algebraic numbers can be evaluated numerically to arbitrary precision by converting to real or complex Arb fields:

julia> Qb = algebraic_closure(QQ);

julia> RR = ArbField(64); RR(sqrt(Qb(2)))
[1.414213562373095049 +/- 3.45e-19]

julia> CC = AcbField(32); CC(Qb(-1) ^ (Qb(1) // 4))
[0.707106781 +/- 2.74e-10] + [0.707106781 +/- 2.74e-10]*im

Minimal polynomials, conjugates, and properties

Examples

Retrieving the minimal polynomial and algebraic conjugates of a given algebraic number:

julia> Qb = algebraic_closure(QQ);

julia> minpoly(polynomial_ring(ZZ, "x")[1], Qb(1+2im))
x^2 - 2*x + 5

julia> conjugates(Qb(1+2im))
2-element Vector{QQBarFieldElem}:
 {a2: 1.00000 + 2.00000*im}
 {a2: 1.00000 - 2.00000*im}

Interface

iszero — Method
iszero(x::QQBarFieldElem)

Return whether x is the number 0.

source
isone — Method
isone(x::QQBarFieldElem)

Return whether x is the number 1.

source
isinteger — Method
isinteger(x::QQBarFieldElem)

Return whether x is an integer.

source
is_rational — Method
is_rational(x::QQBarFieldElem)

Return whether x is a rational number.

source
isreal — Method
isreal(x::QQBarFieldElem)

Return whether x is a real number.

source
degree — Method
degree(x::QQBarFieldElem)

Return the degree of the minimal polynomial of x.

source
minpoly — Method
minpoly(R::ZZPolyRing, x::QQBarFieldElem)

Return the minimal polynomial of x as an element of the polynomial ring R.

source
minpoly — Method
minpoly(R::QQPolyRing, x::QQBarFieldElem)

Return the minimal polynomial of x as an element of the polynomial ring R.

source
conjugates — Method
conjugates(a::QQBarFieldElem)

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.

source
denominator — Method
denominator(x::QQBarFieldElem)

Return the denominator of x, defined as the leading coefficient of the minimal polynomial of x. The result is returned as an ZZRingElem.

source
numerator — Method
numerator(x::QQBarFieldElem)

Return the numerator of x, defined as x multiplied by its denominator. The result is an algebraic integer.

source
height — Method
height(x::QQBarFieldElem)

Return the height of the algebraic number x. The result is an ZZRingElem integer.

source
height_bits — Method
height_bits(x::QQBarFieldElem)

Return the height of the algebraic number x measured in bits. The result is a Julia integer.

source

Complex parts

Examples

julia> Qb = algebraic_closure(QQ);

julia> real(sqrt(Qb(1im)))
{a2: 0.707107}

julia> abs(sqrt(Qb(1im)))
{a1: 1.00000}

julia> floor(sqrt(Qb(1000)))
{a1: 31.0000}

julia> sign(Qb(-10-20im))
{a4: -0.447214 - 0.894427*im}

Interface

real — Method
real(a::QQBarFieldElem)

Return the real part of a.

source
imag — Method
imag(a::QQBarFieldElem)

Return the imaginary part of a.

source
abs — Method
abs(a::QQBarFieldElem)

Return the absolute value of a.

source
abs2 — Method
abs2(a::QQBarFieldElem)

Return the squared absolute value of a.

source
conj — Method
conj(a::QQBarFieldElem)

Return the complex conjugate of a.

source
sign — Method
sign(a::QQBarFieldElem)

Return the complex sign of a, defined as zero if a is zero and as $a / |a|$ otherwise.

source
csgn — Method
csgn(a::QQBarFieldElem)

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.

source
sign_real — Method
sign_real(a::QQBarFieldElem)

Return the sign of the real part of a.

source
sign_imag — Method
sign_imag(a::QQBarFieldElem)

Return the sign of the imaginary part of a.

source

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> Qb = algebraic_closure(QQ);

julia> 1 < sqrt(Qb(2)) < Qb(3)//2
true

julia> x = Qb(3+4im)
{a2: 3.00000 + 4.00000*im}

julia> is_equal_abs(x, -x)
true

julia> is_equal_abs_imag(x, 2-x)
true

julia> is_less_real(x, x // 2)
false

Interface

is_equal_real — Method
is_equal_real(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the real parts of a and b.

source
is_equal_imag — Method
is_equal_imag(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the imaginary parts of a and b.

source
is_equal_abs — Method
is_equal_abs(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the absolute values of a and b.

source
is_equal_abs_real — Method
is_equal_abs_real(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the absolute values of the real parts of a and b.

source
is_equal_abs_imag — Method
is_equal_abs_imag(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the absolute values of the imaginary parts of a and b.

source
is_less_real — Method
is_less_real(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the real parts of a and b.

source
is_less_imag — Method
is_less_imag(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the imaginary parts of a and b.

source
is_less_abs — Method
is_less_abs(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the absolute values of a and b.

source
is_less_abs_real — Method
is_less_abs_real(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the absolute values of the real parts of a and b.

source
is_less_abs_imag — Method
is_less_abs_imag(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the absolute values of the imaginary parts of a and b.

source
is_less_root_order — Method
is_less_root_order(a::QQBarFieldElem, b::QQBarFieldElem)

Compares the a and b in root sort order.

source

Roots and trigonometric functions

Examples

julia> Qb =  algebraic_closure(QQ);

julia> root(Qb(2), 5)
{a5: 1.14870}

julia> sinpi(Qb(7) // 13)
{a12: 0.992709}

julia> tanpi(atanpi(sqrt(Qb(2)) + 1))
{a2: 2.41421}

julia> root_of_unity(Qb, 5)
{a4: 0.309017 + 0.951057*im}

julia> root_of_unity(Qb, 5, 4)
{a4: 0.309017 - 0.951057*im}

julia> w = (1 - sqrt(Qb(-3)))//2
{a2: 0.500000 - 0.866025*im}

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 — Method
sqrt(a::QQBarFieldElem; check::Bool=true)

Return the principal square root of a.

source
root — Method
root(a::QQBarFieldElem, n::Int)

Return the principal n-th root of a. Requires positive n.

source
root_of_unity — Method
root_of_unity(C::QQBarField, n::Int, k::Int = 1)

Return the root of unity $e^{2 \pi i k / n}$ as an element of the field of algebraic numbers C.

source
root_of_unity — Method
root_of_unity(C::QQBarField, n::Int, k::Int = 1)

Return the root of unity $e^{2 \pi i k / n}$ as an element of the field of algebraic numbers C.

source
is_root_of_unity — Method
is_root_of_unity(a::QQBarFieldElem)

Return whether the given algebraic number is a root of unity.

source
root_of_unity_as_args — Method
root_of_unity_as_args(a::QQBarFieldElem)

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.

source
exp_pi_i — Method
exp_pi_i(a::QQBarFieldElem)

Return $e^{\pi i a}$ as an algebraic number. Throws if this value is transcendental.

source
log_pi_i — Method
log_pi_i(a::QQBarFieldElem)

Return $\log(a) / (\pi i)$ as an algebraic number. Throws if this value is transcendental or undefined.

source
sinpi — Method
sinpi(a::QQBarFieldElem)

Return $\sin(\pi a)$ as an algebraic number. Throws if this value is transcendental.

Examples

julia> QQBar = algebraic_closure(QQ);

julia> x = sinpi(QQBar(1//3))
{a2: 0.866025}
source
cospi — Method
cospi(a::QQBarFieldElem)

Return $\cos(\pi a)$ as an algebraic number. Throws if this value is transcendental.

Examples

julia> QQBar = algebraic_closure(QQ);

julia> x = cospi(QQBar(1//6))
{a2: 0.866025}
source
sincospi — Method
sincospi(a::QQBarFieldElem)

Return $\sin(\pi a)$ and $\cos(\pi a)$ as a pair of algebraic numbers. Throws if either value is transcendental.

Examples

julia> QQBar = algebraic_closure(QQ);

julia> s, c = sincospi(QQBar(1//3))
({a2: 0.866025}, {a1: 0.500000})
source
tanpi — Method
tanpi(a::QQBarFieldElem)

Return $\tan(\pi a)$ as an algebraic number. Throws if this value is transcendental or undefined.

source
asinpi — Method
asinpi(a::QQBarFieldElem)

Return $\operatorname{asin}(a) / \pi$ as an algebraic number. Throws if this value is transcendental.

source
acospi — Method
acospi(a::QQBarFieldElem)

Return $\operatorname{acos}(a) / \pi$ as an algebraic number. Throws if this value is transcendental.

source
atanpi — Method
atanpi(a::QQBarFieldElem)

Return $\operatorname{atan}(a) / \pi$ as an algebraic number. Throws if this value is transcendental or undefined.

source

Guessing

Examples

An algebraic number can be recovered from a numerical value:

julia> Qb = algebraic_closure(QQ);

julia> RR = real_field(); guess(Qb, RR("1.41421356 +/- 1e-6"), 2)
{a2: 1.41421}

Warning: the input should be an enclosure. If you have a floating-point approximation, you should add an error estimate; otherwise, at best the only algebraic number that can be guessed is the binary floating-point number itself, at worst no guess is possible.

julia> Qb = algebraic_closure(QQ);

julia> RR = real_field();

julia> x = RR(0.1)       # note: 53-bit binary approximation of 1//10 without radius
[0.10000000000000000555 +/- 1.12e-21]

julia> guess(Qb, x, 1)
ERROR: No suitable algebraic number found

julia> guess(Qb, x + RR("+/- 1e-10"), 1)
{a1: 0.100000}

Interface

guess — Function
guess(R::QQBarField, x::AcbFieldElem, maxdeg::Int, maxbits::Int=0)
guess(R::QQBarField, x::ArbFieldElem, maxdeg::Int, maxbits::Int=0)
guess(R::QQBarField, x::ComplexFieldElem, maxdeg::Int, maxbits::Int=0)
guess(R::QQBarField, x::RealFieldElem, 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.

source

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 a number field to represent $\mathbb{Q}(a)$.