Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Canonical signed binary rational data

Definition
InfoLossLAR_Native_AFT_BinaryRationalData

by BoomShaKaLaaaKa · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

info-loss-lar-native-5c3becb

A rational encoding consists of a sign bit sss, canonical numerator and denominator digit lists representing u,v∈Nu,v\in\mathbb Nu,v∈N, and conditions v>0v>0v>0 and gcd⁡(u,v)=1\gcd(u,v)=1gcd(u,v)=1. Its decoded value is

decode⁡(s,u,v)=(−1)suv.\operatorname{decode}(s,u,v)=(-1)^s\frac{u}{v}.decode(s,u,v)=(−1)svu​.

The reduction routine uses the binary gcd, division, and normalization operations to produce this representation from supplied numerator and positive-denominator strings. Results pair the rational data with a native operation charge.

Definition code
import Definitions.Def_InfoLossLAR_Native_AFT_BinaryEuclid
import Definitions.Def_InfoLossLAR_Native_AFT_RationalHeight
import Mathlib



/-! Canonical rational data stored as Boolean lists. Proof fields are erased;
semantic reduced height controls the actual operand representation length. -/
namespace AFT.BinaryArithmetic

def signedValue (negative : Bool) (digits : List Bool) : ℤ :=
  if negative then -(value digits : ℤ) else (value digits : ℤ)

@[simp] theorem signedValue_natAbs (negative : Bool) (digits : List Bool) :
    (signedValue negative digits).natAbs=value digits := by
  cases negative <;> simp [signedValue]

structure RationalBits where
  negative : Bool
  numerator : List Bool
  denominator : List Bool
  numerator_normal : numerator.length=(value numerator).size
  denominator_normal : denominator.length=(value denominator).size
  denominator_positive : 0 < value denominator
  coprime : (value numerator).Coprime (value denominator)

namespace RationalBits

def decode (input : RationalBits) : ℚ :=
  Rat.mk' (signedValue input.negative input.numerator) (value input.denominator)
    input.denominator_positive.ne' (by simpa only [signedValue_natAbs] using input.coprime)

theorem decode_num (input : RationalBits) :
    input.decode.num=signedValue input.negative input.numerator := rfl



theorem decode_fraction (input : RationalBits) :
    input.decode=(signedValue input.negative input.numerator : ℚ)/(value input.denominator : ℚ) := by
  rw [← Rat.num_div_den input.decode]
  rfl



end RationalBits

structure RationalResult where
  data : RationalBits
  work : ℕ

/-- Actual Euclid, two actual binary divisions, then high-zero trimming. -/
def reduce (negative : Bool) (num den : List Bool) (hden : 0 < value den) : RationalResult :=
  let common := gcd num den
  let top := divide num common.digits
  let bottom := divide den common.digits
  let nt := normalize top.quotient
  let nd := normalize bottom.quotient
  have hc : 0 < value common.digits := by
    simpa only [common,gcd_value] using Nat.gcd_pos_of_pos_right (value num) hden
  have ht : value nt.digits=value num/Nat.gcd (value num) (value den) := by
    simpa only [nt,normalize_value,top,common,gcd_value] using (divide_value num common.digits hc).1
  have hd : value nd.digits=value den/Nat.gcd (value num) (value den) := by
    simpa only [nd,normalize_value,bottom,common,gcd_value] using (divide_value den common.digits hc).1
  ⟨{negative := negative,numerator := nt.digits,denominator := nd.digits
    numerator_normal := by dsimp only [nt];rw [normalize_length,normalize_value]
    denominator_normal := by dsimp only [nd];rw [normalize_length,normalize_value]
    denominator_positive := by rw [hd];exact Nat.div_gcd_pos_of_pos_right _ hden
    coprime := by rw [ht,hd];exact Nat.coprime_div_gcd_div_gcd (Nat.gcd_pos_of_pos_right _ hden)},
    common.work+top.work+bottom.work+nt.work+nd.work+8⟩

theorem reduce_numerator (negative : Bool) (num den : List Bool) (hden : 0 < value den) :
    value (reduce negative num den hden).data.numerator=value num/Nat.gcd (value num) (value den) := by
  have hc : 0 < value (gcd num den).digits := by rw [gcd_value];exact Nat.gcd_pos_of_pos_right _ hden
  simp only [reduce,normalize_value,(divide_value num (gcd num den).digits hc).1,gcd_value]

theorem reduce_denominator (negative : Bool) (num den : List Bool) (hden : 0 < value den) :
    value (reduce negative num den hden).data.denominator=value den/Nat.gcd (value num) (value den) := by
  have hc : 0 < value (gcd num den).digits := by rw [gcd_value];exact Nat.gcd_pos_of_pos_right _ hden
  simp only [reduce,normalize_value,(divide_value den (gcd num den).digits hc).1,gcd_value]

theorem reduce_value (negative : Bool) (num den : List Bool) (hden : 0 < value den) :
    (reduce negative num den hden).data.decode=(signedValue negative num : ℚ)/(value den : ℚ) := by
  rw [RationalBits.decode_fraction]
  have hneg : (reduce negative num den hden).data.negative=negative := rfl
  simp only [signedValue,hneg]
  rw [reduce_numerator,reduce_denominator]
  have hc : (Nat.gcd (value num) (value den) : ℚ) ≠ 0 := by
    exact_mod_cast (Nat.gcd_pos_of_pos_right _ hden).ne'
  cases negative <;> simp only [Bool.false_eq_true,ite_false,ite_true,Int.cast_neg,Int.cast_natCast]
  all_goals rw [Nat.cast_div (Nat.gcd_dvd_left ..),Nat.cast_div (Nat.gcd_dvd_right ..)]
  all_goals first | exact hc | field_simp [hc]



end AFT.BinaryArithmetic
Source
Local manuscript repository commit 5c3becb254daaa8738368b474349766c1769c2a0; lean/AFT/BinaryRationalData.lean; migrated native SHA256 3b61e90cabedb20ce7a4ad82b6d23f7fc21b0903ba2f6e470c21ea4c0f3addc0; retained source units selected by Lean oracle.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me