# 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.FracFieldElem{T}` | `Generic.FracField{T}` |

$\mathbb{Z}$ | Flint | `QQFieldElem` | `QQField` |

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

`sign`

— Method`sign(a::QQFieldElem)`

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

`height`

— Method`height(a::QQFieldElem)`

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

`height_bits`

— Method`height_bits(a::QQFieldElem)`

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

`<<`

— Method`<<(a::QQFieldElem, b::Int)`

Return $a \times 2^b$.

`>>`

— Method`>>(a::QQFieldElem, b::Int)`

Return $a/2^b$.

`floor`

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

`ceil`

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

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

`mod`

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

### Rational Reconstruction

Rational reconstruction is available for rational numbers.

`reconstruct`

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

`reconstruct`

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

## Rational enumeration

Various methods exist to enumerate rationals.

`next_minimal`

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

`next_signed_minimal`

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

`next_calkin_wilf`

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

`next_signed_calkin_wilf`

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

### Random generation

`rand_bits`

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

### Special functions

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

`harmonic`

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

`bernoulli`

— Method`bernoulli(n::Int)`

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

See also `bernoulli_cache`

.

**Examples**

```
julia> d = bernoulli(12)
-691//2730
```

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

See also `bernoulli`

.

**Examples**

```
julia> bernoulli_cache(100)
julia> e = bernoulli(100)
-94598037819122125295227433069493721872702841533066936133385696204311395415197247711//33330
```

`dedekind_sum`

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

`simplest_between`

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