Basic Definitions/Theorems for Continued Fractions

Summary

We define generalised, simple, and regular continued fractions and functions to evaluate their convergents. We follow the naming conventions from Wikipedia and [Wal18], Chapter 1.

Main definitions

1. Generalised continued fractions (gcfs)
2. Simple continued fractions (scfs)
3. (Regular) continued fractions ((r)cfs)
4. Computation of convergents using the recurrence relation in convs.
5. Computation of convergents by directly evaluating the fraction described by the gcf in convs'.

Implementation notes

1. The most commonly used kind of continued fractions in the literature are regular continued fractions. We hence just call them ContFract in the library.
2. We use sequences from Data.Seq to encode potentially infinite sequences.

References

• https://en.wikipedia.org/wiki/Generalized_continued_fraction
• Wall, H.S., Analytic Theory of Continued Fractions

Tags

numerics, number theory, approximations, fractions

Definitions

structure GenContFract.Pair (α : Type u_1) : Type u_1

We collect a partial numerator aᵢ and partial denominator bᵢ in a pair ⟨aᵢ, bᵢ⟩.

• a : α

  Partial numerator

• b : α

  Partial denominator

instance GenContFract.instInhabitedPair : {a : Type u_2} → [inst : Inhabited a] → Inhabited (GenContFract.Pair a)

Equations

• GenContFract.instInhabitedPair = { default := { a := default, b := default } }

Interlude: define some expected coercions and instances.

instance GenContFract.Pair.instRepr {α : Type u_1} [Repr α] : Repr (GenContFract.Pair α)

Make a GenContFract.Pair printable.

Equations

• GenContFract.Pair.instRepr = { reprPrec := fun (p : GenContFract.Pair α) (x : ℕ) => Std.Format.text "(a : " ++ repr p.a ++ Std.Format.text ", b : " ++ repr p.b ++ Std.Format.text ")" }

def GenContFract.Pair.map {α : Type u_1} {β : Type u_2} (f : α → β) (gp : GenContFract.Pair α) : GenContFract.Pair β

Maps a function f on both components of a given pair.

Equations

• GenContFract.Pair.map f gp = { a := f gp.a, b := f gp.b }

def GenContFract.Pair.coeFn {α : Type u_1} {β : Type u_2} [Coe α β] : GenContFract.Pair α → GenContFract.Pair β

The coercion between numerator-denominator pairs happens componentwise.

Equations

• GenContFract.Pair.coeFn = GenContFract.Pair.map Coe.coe

instance GenContFract.Pair.instCoe {α : Type u_1} {β : Type u_2} [Coe α β] : Coe (GenContFract.Pair α) (GenContFract.Pair β)

Coerce a pair by elementwise coercion.

Equations

• GenContFract.Pair.instCoe = { coe := GenContFract.Pair.coeFn }

@[simp]

theorem GenContFract.Pair.coe_toPair {α : Type u_1} {β : Type u_2} [Coe α β] {a : α} {b : α} : ↑{ a := a, b := b } = { a := Coe.coe a, b := Coe.coe b }

theorem GenContFract.ext_iff {α : Type u_1} (x : GenContFract α) (y : GenContFract α) : x = y ↔ x.h = y.h ∧ x.s = y.s

theorem GenContFract.ext {α : Type u_1} (x : GenContFract α) (y : GenContFract α) (h : x.h = y.h) (s : x.s = y.s) : x = y

structure GenContFract (α : Type u_1) : Type u_1

A generalised continued fraction (gcf) is a potentially infinite expression of the form $$ h + \dfrac{a_0} {b_0 + \dfrac{a_1} {b_1 + \dfrac{a_2} {b_2 + \dfrac{a_3} {b_3 + \dots}}}} $$ where h is called the head term or integer part, the aᵢ are called the partial numerators and the bᵢ the partial denominators of the gcf. We store the sequence of partial numerators and denominators in a sequence of GenContFract.Pairs s. For convenience, one often writes [h; (a₀, b₀), (a₁, b₁), (a₂, b₂),...].

• h : α

  Head term

• s : Stream'.Seq (GenContFract.Pair α)

  Sequence of partial numerator and denominator pairs.

def GenContFract.ofInteger {α : Type u_1} (a : α) : GenContFract α

Constructs a generalized continued fraction without fractional part.

Equations

• GenContFract.ofInteger a = { h := a, s := Stream'.Seq.nil }

instance GenContFract.instInhabited {α : Type u_1} [Inhabited α] : Inhabited (GenContFract α)

Equations

• GenContFract.instInhabited = { default := GenContFract.ofInteger default }

def GenContFract.partNums {α : Type u_1} (g : GenContFract α) : Stream'.Seq α

Returns the sequence of partial numerators aᵢ of g.

Equations

• g.partNums = Stream'.Seq.map GenContFract.Pair.a g.s

def GenContFract.partDens {α : Type u_1} (g : GenContFract α) : Stream'.Seq α

Returns the sequence of partial denominators bᵢ of g.

Equations

• g.partDens = Stream'.Seq.map GenContFract.Pair.b g.s

def GenContFract.TerminatedAt {α : Type u_1} (g : GenContFract α) (n : ℕ) : Prop

A gcf terminated at position n if its sequence terminates at position n.

Equations

• g.TerminatedAt n = g.s.TerminatedAt n

instance GenContFract.terminatedAtDecidable {α : Type u_1} (g : GenContFract α) (n : ℕ) : Decidable (g.TerminatedAt n)

It is decidable whether a gcf terminated at a given position.

Equations

• g.terminatedAtDecidable n = id inferInstance

def GenContFract.Terminates {α : Type u_1} (g : GenContFract α) : Prop

A gcf terminates if its sequence terminates.

Equations

• g.Terminates = g.s.Terminates

Interlude: define some expected coercions.

def GenContFract.coeFn {α : Type u_1} {β : Type u_2} [Coe α β] : GenContFract α → GenContFract β

The coercion between GenContFract happens on the head term and all numerator-denominator pairs componentwise.

Equations

• ↑g = { h := Coe.coe g.h, s := Stream'.Seq.map GenContFract.Pair.coeFn g.s }

instance GenContFract.instCoe {α : Type u_1} {β : Type u_2} [Coe α β] : Coe (GenContFract α) (GenContFract β)

Coerce a gcf by elementwise coercion.

Equations

• GenContFract.instCoe = { coe := GenContFract.coeFn }

@[simp]

theorem GenContFract.coe_toGenContFract {α : Type u_1} {β : Type u_2} [Coe α β] {g : GenContFract α} : ↑g = { h := Coe.coe g.h, s := Stream'.Seq.map GenContFract.Pair.coeFn g.s }

def GenContFract.IsSimpContFract {α : Type u_1} (g : GenContFract α) [One α] : Prop

A generalized continued fraction is a simple continued fraction if all partial numerators are equal to one. $$ h + \dfrac{1} {b_0 + \dfrac{1} {b_1 + \dfrac{1} {b_2 + \dfrac{1} {b_3 + \dots}}}} $$

Equations

• g.IsSimpContFract = ∀ (n : ℕ) (aₙ : α), g.partNums.get? n = some aₙ → aₙ = 1

def SimpContFract (α : Type u_1) [One α] : Type u_1

A simple continued fraction (scf) is a generalized continued fraction (gcf) whose partial numerators are equal to one. $$ h + \dfrac{1} {b_0 + \dfrac{1} {b_1 + \dfrac{1} {b_2 + \dfrac{1} {b_3 + \dots}}}} $$ For convenience, one often writes [h; b₀, b₁, b₂,...]. It is encoded as the subtype of gcfs that satisfy GenContFract.IsSimpContFract.

Equations

• SimpContFract α = { g : GenContFract α // g.IsSimpContFract }

def SimpContFract.ofInteger {α : Type u_1} [One α] (a : α) : SimpContFract α

Constructs a simple continued fraction without fractional part.

Equations

• SimpContFract.ofInteger a = ⟨GenContFract.ofInteger a, ⋯⟩

instance SimpContFract.instInhabited {α : Type u_1} [One α] : Inhabited (SimpContFract α)

Equations

• SimpContFract.instInhabited = { default := SimpContFract.ofInteger 1 }

instance SimpContFract.instCoeGenContFract {α : Type u_1} [One α] : Coe (SimpContFract α) (GenContFract α)

Lift a scf to a gcf using the inclusion map.

Equations

• SimpContFract.instCoeGenContFract = { coe := Subtype.val }

def SimpContFract.IsContFract {α : Type u_1} [One α] [Zero α] [LT α] (s : SimpContFract α) : Prop

A simple continued fraction is a (regular) continued fraction ((r)cf) if all partial denominators bᵢ are positive, i.e. 0 < bᵢ.

Equations

• s.IsContFract = ∀ (n : ℕ) (bₙ : α), (↑s).partDens.get? n = some bₙ → 0 < bₙ

def ContFract (α : Type u_1) [One α] [Zero α] [LT α] : Type u_1

A (regular) continued fraction ((r)cf) is a simple continued fraction (scf) whose partial denominators are all positive. It is the subtype of scfs that satisfy SimpContFract.IsContFract.

Equations

• ContFract α = { s : SimpContFract α // s.IsContFract }

Interlude: define some expected coercions.

def ContFract.ofInteger {α : Type u_1} [One α] [Zero α] [LT α] (a : α) : ContFract α

Constructs a continued fraction without fractional part.

Equations

• ContFract.ofInteger a = ⟨SimpContFract.ofInteger a, ⋯⟩

instance ContFract.instInhabited {α : Type u_1} [One α] [Zero α] [LT α] : Inhabited (ContFract α)

Equations

• ContFract.instInhabited = { default := ContFract.ofInteger 0 }

instance ContFract.instCoeSimpContFract {α : Type u_1} [One α] [Zero α] [LT α] : Coe (ContFract α) (SimpContFract α)

Lift a cf to a scf using the inclusion map.

Equations

• ContFract.instCoeSimpContFract = { coe := Subtype.val }

instance ContFract.instCoeGenContFract {α : Type u_1} [One α] [Zero α] [LT α] : Coe (ContFract α) (GenContFract α)

Lift a cf to a scf using the inclusion map.

Equations

• ContFract.instCoeGenContFract = { coe := fun (c : ContFract α) => ↑↑c }

Computation of Convergents

We now define how to compute the convergents of a gcf. There are two standard ways to do this: directly evaluating the (infinite) fraction described by the gcf or using a recurrence relation. For (r)cfs, these computations are equivalent as shown in Algebra.ContinuedFractions.ConvergentsEquiv.

We start with the definition of the recurrence relation. Given a gcf g, for all n ≥ 1, we define

• A₋₁ = 1, A₀ = h, Aₙ = bₙ₋₁ * Aₙ₋₁ + aₙ₋₁ * Aₙ₋₂, and
• B₋₁ = 0, B₀ = 1, Bₙ = bₙ₋₁ * Bₙ₋₁ + aₙ₋₁ * Bₙ₋₂.

Aₙ, Bₙ are called the nth continuants, Aₙ the nth numerator, and Bₙ the nth denominator of g. The nth convergent of g is given by Aₙ / Bₙ.

def GenContFract.nextNum {K : Type u_2} [DivisionRing K] (a : K) (b : K) (ppredA : K) (predA : K) : K

Returns the next numerator Aₙ = bₙ₋₁ * Aₙ₋₁ + aₙ₋₁ * Aₙ₋₂, where predA is Aₙ₋₁, ppredA is Aₙ₋₂, a is aₙ₋₁, and b is bₙ₋₁.

Equations

• GenContFract.nextNum a b ppredA predA = b * predA + a * ppredA

def GenContFract.nextDen {K : Type u_2} [DivisionRing K] (aₙ : K) (bₙ : K) (ppredB : K) (predB : K) : K

Returns the next denominator Bₙ = bₙ₋₁ * Bₙ₋₁ + aₙ₋₁ * Bₙ₋₂, where predB is Bₙ₋₁ and ppredB is Bₙ₋₂, a is aₙ₋₁, and b is bₙ₋₁.

Equations

• GenContFract.nextDen aₙ bₙ ppredB predB = bₙ * predB + aₙ * ppredB

def GenContFract.nextConts {K : Type u_2} [DivisionRing K] (a : K) (b : K) (ppred : GenContFract.Pair K) (pred : GenContFract.Pair K) : GenContFract.Pair K

Returns the next continuants ⟨Aₙ, Bₙ⟩ using nextNum and nextDen, where pred is ⟨Aₙ₋₁, Bₙ₋₁⟩, ppred is ⟨Aₙ₋₂, Bₙ₋₂⟩, a is aₙ₋₁, and b is bₙ₋₁.

Equations

• GenContFract.nextConts a b ppred pred = { a := GenContFract.nextNum a b ppred.a pred.a, b := GenContFract.nextDen a b ppred.b pred.b }

def GenContFract.contsAux {K : Type u_2} [DivisionRing K] (g : GenContFract K) : Stream' (GenContFract.Pair K)

Returns the continuants ⟨Aₙ₋₁, Bₙ₋₁⟩ of g.

Equations

• g.contsAux 0 = { a := 1, b := 0 }
• g.contsAux 1 = { a := g.h, b := 1 }
• g.contsAux n.succ.succ = match g.s.get? n with | none => g.contsAux (n + 1) | some gp => GenContFract.nextConts gp.a gp.b (g.contsAux n) (g.contsAux (n + 1))

def GenContFract.conts {K : Type u_2} [DivisionRing K] (g : GenContFract K) : Stream' (GenContFract.Pair K)

Returns the continuants ⟨Aₙ, Bₙ⟩ of g.

Equations

• g.conts = g.contsAux.tail

def GenContFract.nums {K : Type u_2} [DivisionRing K] (g : GenContFract K) : Stream' K

Returns the numerators Aₙ of g.

Equations

• g.nums = Stream'.map GenContFract.Pair.a g.conts

def GenContFract.dens {K : Type u_2} [DivisionRing K] (g : GenContFract K) : Stream' K

Returns the denominators Bₙ of g.

Equations

• g.dens = Stream'.map GenContFract.Pair.b g.conts

def GenContFract.convs {K : Type u_2} [DivisionRing K] (g : GenContFract K) : Stream' K

Returns the convergents Aₙ / Bₙ of g, where Aₙ, Bₙ are the nth continuants of g.

Equations

• g.convs n = g.nums n / g.dens n

def GenContFract.convs'Aux {K : Type u_2} [DivisionRing K] : Stream'.Seq (GenContFract.Pair K) → ℕ → K

Returns the approximation of the fraction described by the given sequence up to a given position n. For example, convs'Aux [(1, 2), (3, 4), (5, 6)] 2 = 1 / (2 + 3 / 4) and convs'Aux [(1, 2), (3, 4), (5, 6)] 0 = 0.

Equations

• GenContFract.convs'Aux x 0 = 0
• GenContFract.convs'Aux x n.succ = match x.head with | none => 0 | some gp => gp.a / (gp.b + GenContFract.convs'Aux x.tail n)

def GenContFract.convs' {K : Type u_2} [DivisionRing K] (g : GenContFract K) (n : ℕ) : K

Returns the convergents of g by evaluating the fraction described by g up to a given position n. For example, convs' [9; (1, 2), (3, 4), (5, 6)] 2 = 9 + 1 / (2 + 3 / 4) and convs' [9; (1, 2), (3, 4), (5, 6)] 0 = 9

Equations

• g.convs' n = g.h + GenContFract.convs'Aux g.s n