Fraction fields

Nemo allows the creation of fraction fields over any ring $R$. We don't require $R$ to be an integral domain, however no attempt is made to deal with the general case. Two fractions $a/b$ and $c/d$ are equal in Nemo iff $ad = bc$. Thus, in practice, a greatest common divisor function is currently required for the ring $R$.

In order to make the representation $a/b$ unique for printing, we have a notion of canonical unit for elements of a ring $R$. When canonicalising $a/b$, each of the elements $a$ and $b$ is first divided by the canonical unit of $b$.

The canonical_unit function is defined for elements of every Nemo ring. It must have the properties

canonical_unit(u) == u
canonical_unit(a*b) == canonical_unit(a)*canonical_unit(b)

for any unit $u$ of the ring in question, and $a$ and $b$ arbitrary elements of the ring.

For example, the canonical unit of an integer is its sign. Thus a fraction of integers always has positive denominator after canonicalisation.

The canonical unit of a polynomial is the canonical unit of its leading coefficient, etc.

There are two different kinds of implementation of fraction fields in Nemo: a generic one for the case where no specific implementation exists (provided by AbstractAlgebra.jl), and efficient implementations of fractions over specific rings, usually provided by C/C++ libraries.

The following table shows each of the fraction types available in Nemo, the base ring $R$, and the Julia/Nemo types for that kind of fraction (the type information is mainly of concern to developers).

Base ringLibraryElement typeParent type
Generic ring $R$AbstractAlgebra.jlGeneric.FracFieldElem{T}Generic.FracField{T}
$\mathbb{Z}$FlintQQFieldElemQQField

All fraction element types belong to the abstract type FracElem and all of the fraction field types belong to the abstract type FracField. This enables one to write generic functions that can accept any Nemo fraction type.

Fraction functionality

All fraction types in Nemo provide functionality for fields described in AbstractAlgebra.jl:

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

In addition all the fraction field functionality of AbstractAlgebra.jl is provided, along with generic fractions fields as described here:

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

Basic manipulation

signMethod
sign(a::QQFieldElem)

Return the sign of $a$ ($-1$, $0$ or $1$) as a fraction.

source
heightMethod
height(a::QQFieldElem)

Return the height of the fraction $a$, namely the largest of the absolute values of the numerator and denominator.

source
height_bitsMethod
height_bits(a::QQFieldElem)

Return the number of bits of the height of the fraction $a$.

source
<<Method
<<(a::QQFieldElem, b::Int)

Return $a \times 2^b$.

source
>>Method
>>(a::QQFieldElem, b::Int)

Return $a/2^b$.

source
floorMethod
floor(a::QQFieldElem)

Return the greatest integer that is less than or equal to $a$. The result is returned as a rational with denominator $1$.

source
ceilMethod
ceil(a::QQFieldElem)

Return the least integer that is greater than or equal to $a$. The result is returned as a rational with denominator $1$.

source

Examples

julia> d = abs(ZZ(11)//3)
11//3

julia> 4 <= ZZ(7)//ZZ(3)
false

Modular arithmetic

The following functions are available for rationals.

modMethod
mod(a::QQFieldElem, b::ZZRingElem)
mod(a::QQFieldElem, b::Integer)

Return $a \pmod{b}$ where $b$ is an integer coprime to the denominator of $a$.

Examples

julia> mod(-ZZ(2)//3, 7)
4

julia> mod(ZZ(1)//2, ZZ(5))
3
source

Rational Reconstruction

Rational reconstruction is available for rational numbers.

reconstructMethod
reconstruct(a::ZZRingElem, m::ZZRingElem)
reconstruct(a::ZZRingElem, m::Integer)
reconstruct(a::Integer, m::ZZRingElem)
reconstruct(a::Integer, m::Integer)

Attempt to return a rational number $n/d$ such that $0 \leq |n| \leq \lfloor\sqrt{m/2}\rfloor$ and $0 < d \leq \lfloor\sqrt{m/2}\rfloor$ such that gcd$(n, d) = 1$ and $a \equiv nd^{-1} \pmod{m}$. If no solution exists, an exception is thrown.

Examples

julia> a = reconstruct(7, 13)
1//2

julia> b = reconstruct(ZZ(15), 31)
-1//2

julia> c = reconstruct(ZZ(123), ZZ(237))
9//2
source
reconstructMethod
reconstruct(a::ZZRingElem, m::ZZRingElem, N::ZZRingElem, D::ZZRingElem)

Attempt to return a rational number $n/d$ such that $0 \leq |n| \leq N$ and $0 < d \leq D$ such that $2 N D < m$, gcd$(n, d) = 1$, and $a \equiv nd^{-1} \pmod{m}$.

Returns a tuple (success, n/d), where success signals the success of reconstruction.

source

Rational enumeration

Various methods exist to enumerate rationals.

next_minimalMethod
next_minimal(a::QQFieldElem)

Given $a$, return the next rational number in the sequence obtained by enumerating all positive denominators $q$, and for each $q$ enumerating the numerators $1 \le p < q$ in order and generating both $p/q$ and $q/p$, but skipping all gcd$(p,q) \neq 1$. Starting with zero, this generates every non-negative rational number once and only once, with the first few entries being $0, 1, 1/2, 2, 1/3, 3, 2/3, 3/2, 1/4, 4, 3/4, 4/3, \ldots$. This enumeration produces the rational numbers in order of minimal height. It has the disadvantage of being somewhat slower to compute than the Calkin-Wilf enumeration. If $a < 0$ we throw a DomainError().

Examples

julia> next_minimal(ZZ(2)//3)
3//2
source
next_signed_minimalMethod
next_signed_minimal(a::QQFieldElem)

Given a signed rational number $a$ assumed to be in canonical form, return the next element in the minimal-height sequence generated by next_minimal but with negative numbers interleaved. The sequence begins $0, 1, -1, 1/2, -1/2, 2, -2, 1/3, -1/3, \ldots$. Starting with zero, this generates every rational number once and only once, in order of minimal height.

Examples

julia> next_signed_minimal(-ZZ(21)//31)
31//21
source
next_calkin_wilfMethod
next_calkin_wilf(a::QQFieldElem)

Return the next number after $a$ in the breadth-first traversal of the Calkin-Wilf tree. Starting with zero, this generates every non-negative rational number once and only once, with the first few entries being $0, 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, \ldots$. Despite the appearance of the initial entries, the Calkin-Wilf enumeration does not produce the rational numbers in order of height: some small fractions will appear late in the sequence. This order has the advantage of being faster to produce than the minimal-height order.

Examples

julia> next_calkin_wilf(ZZ(321)//113)
113//244
source
next_signed_calkin_wilfMethod
next_signed_calkin_wilf(a::QQFieldElem)

Given a signed rational number $a$ returns the next element in the Calkin-Wilf sequence with negative numbers interleaved. The sequence begins $0, 1, -1, 1/2, -1/2, 2, -2, 1/3, -1/3, \ldots$. Starting with zero, this generates every rational number once and only once, but not in order of minimal height.

Examples

julia> next_signed_calkin_wilf(-ZZ(51)//(17))
1//4
source

Random generation

rand_bitsMethod
rand_bits(::QQField, b::Int)

Return a random signed rational whose numerator and denominator both have $b$ bits before canonicalisation. Note that the resulting numerator and denominator can be smaller than $b$ bits.

source

Special functions

The following special functions are available for specific rings in Nemo.

harmonicMethod
harmonic(n::Int)

Return the harmonic number $H_n = 1 + 1/2 + 1/3 + \cdots + 1/n$. Table lookup is used for $H_n$ whose numerator and denominator fit in a single limb. For larger $n$, a divide and conquer strategy is used.

Examples

julia> a = harmonic(12)
86021//27720
source
bernoulliMethod
bernoulli(n::Int)

Return the Bernoulli number $B_n$ for non-negative $n$.

See also bernoulli_cache.

Examples

julia> d = bernoulli(12)
-691//2730
source
bernoulli_cacheMethod
bernoulli_cache(n::Int)

Precomputes and caches all the Bernoulli numbers up to $B_n$. This is much faster than repeatedly calling bernoulli(k). Once cached, subsequent calls to bernoulli(k) for any $k \le n$ will read from the cache, making them virtually free.

See also bernoulli.

Examples

julia> bernoulli_cache(100)

julia> e = bernoulli(100)
-94598037819122125295227433069493721872702841533066936133385696204311395415197247711//33330
source
dedekind_sumMethod
dedekind_sum(h::ZZRingElem, k::ZZRingElem)

Return the Dedekind sum $s(h,k)$ for arbitrary $h$ and $k$.

Examples

julia> b = dedekind_sum(12, 13)
-11//13

julia> c = dedekind_sum(-120, ZZ(1305))
-575//522
source
simplest_betweenMethod
  simplest_between(l::QQFieldElem, r::QQFieldElem)

Return the simplest fraction in the closed interval $[l, r]$. A canonical fraction $a_1 / b_1$ is defined to be simpler than $a_2 / b_2$ if and only if $b_1 < b_2$ or $b_1 = b_2$ and $a_1 < a_2$.

Examples

julia> simplest_between(QQ(1//10), QQ(3//10))
1//4
source