Rational addition increases binary height additively
ProvedAFT.RationalNumerics.HeightBound.addinfo-loss-lar-native-5c3becbrational-arithmeticstoc-2027
Let and . Suppose the absolute reduced numerator and denominator of are at most , and those of are at most . Then
This bounds operand growth in the exact rational arithmetic used by the constructive affine sampler.
Preamble
import Definitions.Def_InfoLossLAR_Native_AFT_RationalHeight import Mathlib /-! # Explicit binary height bounds for executable rational arithmetic -/ namespace AFT.RationalNumerics end AFT.RationalNumerics section AFT.RationalNumerics open AFT.RationalNumerics open scoped BigOperators namespace AFT.RationalNumerics.HeightBound end AFT.RationalNumerics.HeightBound section HeightBound open AFT.RationalNumerics.HeightBound
Formal statement
theorem AFT.RationalNumerics.HeightBound.add {first second : ℚ} {firstBits secondBits : ℕ}
(hf : HeightBound first firstBits) (hs : HeightBound second secondBits) :
HeightBound (first+second) (firstBits+secondBits+1) := by sorrySource
Local manuscript repository commit 5c3becb254daaa8738368b474349766c1769c2a0; lean/AFT/RationalHeight.lean, theorem HeightBound.add, lines 44–62; transplanted from the migrated source without changing its type.