Fraction fields

# 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.Frac{T}Generic.FracField{T}
$\mathbb{Z}$FlintfmpqFlintRationalField

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 implement the AbstractAlgebra.jl fraction field interface:

https://nemocas.github.io/AbstractAlgebra.jl/fraction_fields.html

In addition, generic fractions fields are implemented in AbstractAlgebra.jl, with the following functionality:

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

All fraction types in Nemo also implement this generic functionality.

### Basic manipulation

abs(a::fmpq)

Return the absolute value of $a$.

height(a::fmpq)

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

height_bits(a::fmpq)

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

<<(a::fmpq, b::Int)

Return $2^b\times a$.

>>(a::fmpq, b::Int)

Return $2^b/a$.

Rational fractions can be compared with each other and with integers. Julia provides the full range of operators $<, >, \leq, \geq$ which depend on the following functions.

isless(a::fmpq, b::fmpq)

Return true if $a < b$, otherwise return false.

isless(a::Integer, b::fmpq)

Return true if $a < b$, otherwise return false.

isless(a::fmpq, b::Integer)

Return true if $a < b$, otherwise return false.

isless(a::fmpq, b::fmpz)

Return true if $a < b$, otherwise return false.

isless(a::fmpz, b::fmpq)

Return true if $a < b$, otherwise return false.

Examples

d = abs(ZZ(11)//3)
4 <= ZZ(7)//ZZ(3)

### Modular arithmetic

The following functions are available for rationals.

mod(a::fmpq, b::fmpz)

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

mod(a::fmpq, b::Integer)

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

Examples

a = -fmpz(2)//3
b = fmpz(1)//2

c = mod(a, 7)
d = mod(b, fmpz(5))

### Rational Reconstruction

Rational reconstruction is available for rational numbers.

reconstruct(a::fmpz, b::fmpz)

Attempt to find 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.

reconstruct(a::fmpz, b::Integer)

Attempt to find 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.

reconstruct(a::Integer, b::fmpz)

Attempt to find 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.

reconstruct(a::Integer, b::Integer)

Attempt to find 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

a = reconstruct(7, 13)
b = reconstruct(fmpz(15), 31)
c = reconstruct(fmpz(123), fmpz(237))

## Rational enumeration

Various methods exist to enumerate rationals.

next_minimal(a::fmpq)

Given $a$, returns 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 nonnegative 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().

next_signed_minimal(a::fmpq)

Given a signed rational number $a$ assumed to be in canonical form, returns 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.

next_calkin_wilf(a::fmpq)

Given $a$ return the next number in the breadth-first traversal of the Calkin-Wilf tree. Starting with zero, this generates every nonnegative 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.

next_signed_calkin_wilf(a::fmpq)

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

next_minimal(fmpz(2)//3)
next_signed_minimal(-fmpz(21)//31)
next_calkin_wilf(fmpz(321)//113)
next_signed_calkin_wilf(-fmpz(51)//(17))

### Special functions

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

harmonic(n::Int)

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

bernoulli(n::Int)

Computes the Bernoulli number $B_n$ for nonnegative $n$.

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.

dedekind_sum(h::fmpz, k::fmpz)
dedekind_sum(h::fmpz, k::Integer)

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

dedekind_sum(h::Integer, k::fmpz)

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

dedekind_sum(h::Integer, k::Integer)

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

Examples

a = harmonic(12)

b = dedekind_sum(12, 13)
c = dedekind_sum(-120, fmpz(1305))

d = bernoulli(12)

bernoulli_cache(100)
e = bernoulli(100)