# 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 ring | Library | Element type | Parent type |
---|---|---|---|

Generic ring $R$ | AbstractAlgebra.jl | `Generic.Frac{T}` | `Generic.FracField{T}` |

$\mathbb{Z}$ | Flint | `fmpq` | `FlintRationalField` |

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

`Base.abs`

— Method.`abs(a::fmpq)`

Return the absolute value of $a$.

`Nemo.height`

— Method.`height(a::fmpq)`

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

`Nemo.height_bits`

— Method.`height_bits(a::fmpq)`

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

`Base.:<<`

— Method.`<<(a::fmpq, b::Int)`

Return $2^b\times a$.

`Base.:>>`

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

`Base.isless`

— Method.`isless(a::fmpq, b::fmpq)`

Return

`true`

if $a < b$, otherwise return`false`

.

`Base.isless`

— Method.`isless(a::Integer, b::fmpq)`

Return

`true`

if $a < b$, otherwise return`false`

.

`Base.isless`

— Method.`isless(a::fmpq, b::Integer)`

Return

`true`

if $a < b$, otherwise return`false`

.

`Base.isless`

— Method.`isless(a::fmpq, b::fmpz)`

Return

`true`

if $a < b$, otherwise return`false`

.

`Base.isless`

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

`Base.mod`

— Method.`mod(a::fmpq, b::fmpz)`

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

`Base.mod`

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

`Nemo.reconstruct`

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

`Nemo.reconstruct`

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

`Nemo.reconstruct`

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

`Nemo.reconstruct`

— Method.`reconstruct(a::Integer, b::Integer)`

**Examples**

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

## Rational enumeration

Various methods exist to enumerate rationals.

`Nemo.next_minimal`

— Method.`next_minimal(a::fmpq)`

Given $x$, 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 $x < 0$ we throw a

`DomainError()`

.

`Nemo.next_signed_minimal`

— Method.`next_signed_minimal(a::fmpq)`

Given a signed rational number $x$ 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.

`Nemo.next_calkin_wilf`

— Method.`next_calkin_wilf(a::fmpq)`

Given $x$ 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.

`Nemo.next_signed_calkin_wilf`

— Method.`next_signed_calkin_wilf(a::fmpq)`

Given a signed rational number $x$ 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.

`Nemo.harmonic`

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

`Nemo.bernoulli`

— Method.`bernoulli(n::Int)`

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

`Nemo.bernoulli_cache`

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

`Nemo.dedekind_sum`

— Method.`dedekind_sum(h::fmpz, k::fmpz)`

`Nemo.dedekind_sum`

— Method.`dedekind_sum(h::fmpz, k::Integer)`

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

`Nemo.dedekind_sum`

— Method.`dedekind_sum(h::Integer, k::fmpz)`

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

`Nemo.dedekind_sum`

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