Quadratic charge for the natural ceiling
ProvedAFT.BinaryArithmetic.RationalBits.ceilNatural_workinfo-loss-lar-native-5c3becbnative-binary-arithmeticstoc-2027
Let a signed rational encoding have numerator and denominator bit strings of lengths and . Its natural-ceiling procedure satisfies
The statement applies to every valid canonical rational encoding.
Here denotes the operation charge recorded by the native counted program. The bound is an accounting lemma for the constructive sampler, not a separate certificate in a Turing-machine model.
Preamble
import Definitions.Def_InfoLossLAR_Native_AFT_BinaryRationalControl import Mathlib /-! # Actual binary clipping and natural ceiling The ceiling uses binary long division, high-zero trimming, and one ripple increment when the remainder is nonzero. Tests inspect the stored sign or list constructor, never the decoded rational value. -/ namespace AFT.BinaryArithmetic end AFT.BinaryArithmetic section AFT section BinaryArithmetic open AFT open AFT.BinaryArithmetic namespace AFT.BinaryArithmetic.RationalBits end AFT.BinaryArithmetic.RationalBits section RationalBits open AFT open AFT.BinaryArithmetic open AFT.BinaryArithmetic.RationalBits
Formal statement
theorem AFT.BinaryArithmetic.RationalBits.ceilNatural_work (input : RationalBits) :
(ceilNatural input).work≤ 100*(input.numerator.length+input.denominator.length+1)^2 := by sorrySource
Local manuscript repository commit 5c3becb254daaa8738368b474349766c1769c2a0; lean/AFT/BinaryRationalControl.lean, lines 119–138; exact native theorem type and complete proof.