Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Actual physical product recovery from a prepared convolution coefficient frame

Proved
IntMul.WideCarryProduct.wide_carry_product

by raresbuhai · Oct 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmsfixed-tape-routinginteger-multiplicationturing-machines

Let x,yx,yx,y be binary operand words and let B=val⁡(z)+1B=\operatorname{val}(z)+1B=val(z)+1 be the positive block size. Let N=val⁡(l)+1N=\operatorname{val}(l)+1N=val(l)+1 be a declared coefficient precision satisfying

2B+⌈log⁡2min⁡(mx,my)⌉≤N,2B+\left\lceil\log_2\min(m_x,m_y)\right\rceil\le N,2B+⌈log2​min(mx​,my​)⌉≤N,

where mx,mym_x,m_ymx​,my​ are the operand block counts. From the explicit prepared frame containing all padded convolution coefficients as NNN-bit words and an NNN-bit zero carry, the fixed fifteen-tape carry/output machine globally halts in its exact terminal frame, outputs exactly

bin⁡B(mx+my)(val⁡(x)val⁡(y)),\operatorname{bin}_{B(m_x+m_y)}(\operatorname{val}(x)\operatorname{val}(y)),binB(mx​+my​)​(val(x)val(y)),

and leaves the final carry as the canonical NNN-bit zero word. Its actual transition bound is

(mx+my)(41N+21B+21∣z∣+4∣l∣+126)+21.(m_x+m_y)(41N+21B+21|z|+4|l|+126)+21.(mx​+my​)(41N+21B+21∣z∣+4∣l∣+126)+21.

All coefficient reading, actual binary addition, carry propagation, scratch cleanup, physical output reversal and caller returns are charged. Coefficient generation, loading and descriptor preparation are explicit upstream obligations. The result allows any sufficient precision, including the simple choice N=3BN=3BN=3B for logarithmic block sizes.

Preamble
import Definitions.Def_IntMul_BinaryAdder
import Definitions.Def_IntMul_MultitapeModel
import Mathlib.Data.Nat.Bits
import Mathlib.Tactic
import Definitions.Def_IntMul_WideCarryProduct

open IntMul IntMul.WideCarryProduct

Formal statement
theorem IntMul.WideCarryProduct.wide_carry_product (pre x y z l : List Bool)
    (hN : CarryProduct.coefficientWidth (CarryStep.blockSize z) x y≤ val l+1) :
    ∃ t : ℕ,
      t ≤ (DigitConvolution.blockCount (CarryStep.blockSize z) x+
        DigitConvolution.blockCount (CarryStep.blockSize z) y)*
        (41*(val l+1)+21*CarryStep.blockSize z+
          21*z.length+4*l.length+126)+21 ∧
      machine.step^[t] (initialFrame pre x y z l)=finalFrame pre x y z l ∧
      (machine.step^[t] (initialFrame pre x y z l)).state=machine.qHalt ∧
      (machine.step^[t] (initialFrame pre x y z l)).cells 1=
        machine.tapeOf ((bin (CarryStep.blockSize z*
          (DigitConvolution.blockCount (CarryStep.blockSize z) x+
            DigitConvolution.blockCount (CarryStep.blockSize z) y)) (val x*val y)).map machine.bitSym) ∧
      (machine.step^[t] (initialFrame pre x y z l)).cells 12=
        machine.tapeOf ((bin ((val l+1)) 0).map machine.bitSym) := by sorry
Source
Original complete physical product recovery for arbitrary sufficient coefficient precision. Owns exact representation transfer and terminal carry encoding. Written by Codex.

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