Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

The pipeline with three separate computed values (round six, `pipeline_err3`)

Proved
NLogN.KFZ.pipeline_err3

by xuanji · Oct 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinteger-multiplicationkappa-improvement

The pipeline with three separate computed values (per-call procedures): U ≈ F u, V ≈ F v, and Z ≈ F(conj z) for z = Q_p(U V).

The following holds (Lean statement, in the scope of module Solutions.KFZChirpR):

theorem NLogN.KFZ.pipeline_err3 {κ : Type*} [Fintype κ] (p : ℕ) {F : (κ → ℂ) → (κ → ℂ)} (hF : LinC F)
    (Es : ℝ) (hEs : Es * hp p ≤ 1 / 100) {u v : κ → ℂ} (hu1 : ‖u‖ ≤ 1 / 4) (hv1 : ‖v‖ ≤ 1 / 4)
    {U V Z : κ → ℂ} (hU : ‖U - F u‖ ≤ Es * hp p) (hV : ‖V - F v‖ ≤ Es * hp p)
    (hZ : ‖Z - F (cnj (QA p (U * V)))‖ ≤ Es * hp p) :
    Grid p (QA p (U * V)) ∧ ‖QA p (U * V)‖ ≤ 1 / 2 ∧
    ‖cnj Z - cnj (F (cnj (F u * F v)))‖ ≤ (3 * Es + 2) * hp p

Context. KFZ: the per-call form of the chirp interface

ChirpNeed fixes M̃r per n before the input and the machine state, and asks the procedure to output exactly C̃(x) = chirpT p (mcT p M̃r θ̃ θ̃⁻) b̃ ã x. With P18IL as the only source of M̃r, this cannot be met. P18IL gives, for each initial state encK s f (unmanaged part s, tail l on stack 0), some run with some result zh within the Prop 18 bound. Nothing ties the results of two different states together, and a P18IL procedure may legally read s or l and restore it. The dependence on the input tape Isym can be removed (KFZIsym); the dependence on s and l cannot. The obvious workaround, computing mrX exactly, is an integer product of size Θ(V) and does not fit the V · Ncost · polylog budget.

This file gives the per-call statement and shows that it gives the chain everything it uses:

  • ChirpNeedR: ChirpNeed with ∃ Mrt (and its ErC · hp bound) moved after the input. The tables θ̃, θ̃⁻, ã, b̃ and ζ stay fixed per n (they are explicit FM table outputs).
  • ChirpNeed.toR: ChirpNeed → ChirpNeedR.
  • chirp_call_err: for any M̃r with the Prop 18 bound and the fixed tables, one call satisfies ‖C̃ x − Q F_t x‖ ≤ (Er + 22) hp, ‖C̃ x‖ ≤ 1, Grid p (C̃ x). These are exactly the conclusions chain_close uses about the chirp step (its hCt).
  • pipeline_err3: pipeline_err with three separate computed values F̃u, F̃v, F̃(z̄) instead of one

Formalization Note. Part of the Lean formalization of the round-six κ-improvement (integer-multiplication-kappa campaign, target IntMul.Kappa.jain_round6_framework). The statement is copied verbatim from the Lean development; the platform node carries the same declaration name. Definitions it mentions live in the IntMul_Kappa_R6_Defs* bundles (on top of the published κ bundles IntMul_Kappa_K_Defs*).

Preamble
-- Round-six κ development (integer-multiplication-kappa), generated by skeleton subtraction.

import Definitions.Def_IntMul_Kappa_K_Defs33
import Definitions.Def_IntMul_Kappa_R6_Defs1
import Definitions.Def_IntMul_MultitapeModel
import Mathlib
import Definitions.Def_IntMul_HvdH_M_Defs8
import Definitions.Def_IntMul_HvdH_Numeric
import Definitions.Def_IntMul_HvdH_ExpApprox
import Definitions.Def_IntMul_HvdH_Twiddle
import Definitions.Def_IntMul_HvdH_RealExp
import Definitions.Def_IntMul_HvdH_SApprox
import Definitions.Def_IntMul_HvdH_MachineRef
import Definitions.Def_IntMul_HvdH_DiagApprox
import Definitions.Def_IntMul_HvdH_EApprox
import Definitions.Def_IntMul_HvdH_JApprox
import Definitions.Def_IntMul_HvdH_BApprox
import Definitions.Def_IntMul_HvdH_FPApprox

set_option autoImplicit false
set_option relaxedAutoImplicit false
set_option maxHeartbeats 1000000

open NLogN NLogN.KFZ
open IntMul NLogN.KIL NLogN.KFB IntMul.HvdH IntMul.OpenAI.RT IntMul.OpenAI.RC IntMul.OpenAI.Glue IntMul.OpenAI.RCost NLogN.KFM
variable {D : ℕ}
Formal statement
theorem NLogN.KFZ.pipeline_err3 {κ : Type*} [Fintype κ] (p : ℕ) {F : (κ → ℂ) → (κ → ℂ)} (hF : LinC F)
    (Es : ℝ) (hEs : Es * hp p ≤ 1 / 100) {u v : κ → ℂ} (hu1 : ‖u‖ ≤ 1 / 4) (hv1 : ‖v‖ ≤ 1 / 4)
    {U V Z : κ → ℂ} (hU : ‖U - F u‖ ≤ Es * hp p) (hV : ‖V - F v‖ ≤ Es * hp p)
    (hZ : ‖Z - F (cnj (QA p (U * V)))‖ ≤ Es * hp p) :
    Grid p (QA p (U * V)) ∧ ‖QA p (U * V)‖ ≤ 1 / 2 ∧
    ‖cnj Z - cnj (F (cnj (F u * F v)))‖ ≤ (3 * Es + 2) * hp p := by sorry
Source
S. Jain, round-six networks for the integer-multiplication κ-improvement campaign (https://github.com/Swapnil-jain/integer-mult-kappa, commit 5868dc7) and D. Colkitt, integer-mult-bounds (https://github.com/CrocSwap/integer-mult-bounds); target `IntMul.Kappa.jain_round6_framework`. Lean declaration `NLogN.KFZ.pipeline_err3`, Solutions/KFZChirpR.lean (lines 114–156) of the round-six development.

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me