Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Borrow subtraction on binary lists

Definition
InfoLossLAR_Native_AFT_BinarySubtraction

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

info-loss-lar-native-5c3becbnative-binary-arithmeticstoc-2027

Binary subtraction returns a digit list rrr, a final borrow bit β\betaβ, and a native operation charge. For input strings a,ba,ba,b, incoming borrow c∈{0,1}c\in\{0,1\}c∈{0,1}, and m=max⁡{∣a∣,∣b∣}m=\max\{|a|,|b|\}m=max{∣a∣,∣b∣}, the arithmetic balance is

v(r)+v(b)+c=v(a)+2mβ.v(r)+v(b)+c=v(a)+2^m\beta.v(r)+v(b)+c=v(a)+2mβ.

The routine processes individual digits. Its final borrow also records the comparison needed by division and signed arithmetic.

Definition code
import Definitions.Def_InfoLossLAR_Native_AFT_BinaryArithmeticProgram
import Mathlib


/-! Explicit borrow subtraction and comparison, with no integer primitive. -/
namespace AFT.BinaryArithmetic

structure Difference where
  digits : List Bool
  borrow : Bool
  work : ℕ

def borrowBit (a b carry : Bool) : Bool := (!a && (b || carry)) || (b && carry)

theorem fullSubtractor (a b carry : Bool) :
    (sumBit a b carry).toNat+b.toNat+carry.toNat = a.toNat+2*(borrowBit a b carry).toNat := by
  cases a <;> cases b <;> cases carry <;> decide

def subtract (carry : Bool) : List Bool → List Bool → Difference
  | [],[] => ⟨[],carry,2⟩
  | a::as,[] =>
    let next := subtract (borrowBit a false carry) as []
    ⟨sumBit a false carry::next.digits,next.borrow,next.work+10⟩
  | [],b::bs =>
    let next := subtract (borrowBit false b carry) [] bs
    ⟨sumBit false b carry::next.digits,next.borrow,next.work+10⟩
  | a::as,b::bs =>
    let next := subtract (borrowBit a b carry) as bs
    ⟨sumBit a b carry::next.digits,next.borrow,next.work+10⟩

theorem subtract_length (as bs : List Bool) (carry : Bool) :
    (subtract carry as bs).digits.length = max as.length bs.length := by
  induction as generalizing bs carry with
  | nil =>
    induction bs generalizing carry with
    | nil => simp [subtract]
    | cons b bs ih => simp [subtract,ih]
  | cons a as ih =>
    cases bs with
    | nil => simp [subtract,ih]
    | cons b bs => simp [subtract,ih,Nat.succ_max_succ]

theorem subtract_work (as bs : List Bool) (carry : Bool) :
    (subtract carry as bs).work=10*max as.length bs.length+2 := by
  induction as generalizing bs carry with
  | nil =>
    induction bs generalizing carry with
    | nil => simp [subtract]
    | cons b bs ih => simp [subtract,ih];omega
  | cons a as ih =>
    cases bs with
    | nil => simp [subtract,ih];omega
    | cons b bs => simp [subtract,ih,Nat.succ_max_succ];omega

theorem subtract_balance (as bs : List Bool) (carry : Bool) :
    value (subtract carry as bs).digits+value bs+carry.toNat =
      value as+(subtract carry as bs).borrow.toNat*2^(max as.length bs.length) := by
  induction as generalizing bs carry with
  | nil =>
    induction bs generalizing carry with
    | nil => simp [subtract,value]
    | cons b bs ih =>
      have hh := ih (borrowBit false b carry)
      have hf := fullSubtractor false b carry
      simp only [subtract,value,List.length_cons,List.length_nil,Nat.zero_max,Bool.toNat_false] at *
      rw [pow_succ]
      nlinarith
  | cons a as ih =>
    cases bs with
    | nil =>
      have hh := ih [] (borrowBit a false carry)
      have hf := fullSubtractor a false carry
      simp only [subtract,value,List.length_cons,List.length_nil,Nat.max_zero,Bool.toNat_false] at *
      rw [pow_succ]
      nlinarith
    | cons b bs =>
      have hh := ih bs (borrowBit a b carry)
      have hf := fullSubtractor a b carry
      simp only [subtract,value,List.length_cons,Nat.succ_max_succ] at *
      rw [pow_succ]
      nlinarith

theorem value_lt (digits : List Bool) : value digits < 2^digits.length := by
  induction digits with
  | nil => simp [value]
  | cons b tail ih =>
    have hb : b.toNat ≤ 1 := by cases b <;> decide
    simp only [value,List.length_cons,pow_succ]
    omega

theorem subtract_borrow (as bs : List Bool) :
    (subtract false as bs).borrow = true ↔ value as < value bs := by
  have hh := subtract_balance as bs false
  have hv := value_lt (subtract false as bs).digits
  rw [subtract_length] at hv
  simp only [Bool.toNat_false,Nat.add_zero] at hh
  cases hb : (subtract false as bs).borrow <;> simp only [hb,Bool.toNat_false,Bool.toNat_true,zero_mul,one_mul] at hh
  · simp only [Bool.false_eq_true,false_iff];omega
  · simp only [true_iff];omega

theorem subtract_value (as bs : List Bool) (h : value bs ≤ value as) :
    value (subtract false as bs).digits=value as-value bs := by
  have hn : (subtract false as bs).borrow=false := by
    cases hb : (subtract false as bs).borrow
    · rfl
    · exact False.elim ((subtract_borrow as bs).mp hb |>.not_ge h)
  have hh := subtract_balance as bs false
  simp only [hn,Bool.toNat_false,zero_mul,Nat.add_zero] at hh
  omega

end AFT.BinaryArithmetic
Source
Local manuscript repository commit 5c3becb254daaa8738368b474349766c1769c2a0; lean/AFT/BinarySubtraction.lean; migrated native SHA256 3b3901f2c3e1e412c1501cc06899fc7efa890644c7d586368427e7d4e048644c; 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