Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

An introspection stage exists for seven-level normal form verifiers

Proved
MIPRE.Introspection.nonempty_seven

by thomasvidick · Oct 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

gap-compressionmip-remipre-formalizationnonlocal-gamesquantum-informationverifiers

MIPRE.Introspection ℓ (blueprint thm:introspection) records the data and guarantees of the introspection transformation for ℓ\ellℓ-level normal form verifiers: constants a≥1a \ge 1a≥1 and 0<b≤10 < b \le 10<b≤1 of the soundness loss δ(ε,n)=a((λn)aεb+(λn)−b)\delta(\varepsilon, n) = a\bigl((\lambda n)^a \varepsilon^b + (\lambda n)^{-b}\bigr)δ(ε,n)=a((λn)aεb+(λn)−b); a complexity constant CCC; a 555-level introspective sampler Sλintro\mathcal{S}^{\mathrm{intro}}_\lambdaSλintro​ depending only on λ\lambdaλ, with program computable from λ\lambdaλ in polynomial time; the polynomial-time compute from a verifier's programs and λ\lambdaλ to the introspective decider's program; the output, a 555-level verifier with that sampler and decider; the complexity clauses at every input and index nnn (sampler within (λn+1)C(\lambda n+1)^C(λn+1)C, dimension at most (λn+1)C(\lambda n+1)^C(λn+1)C, decider within 2(λn+1)C2^{(\lambda n+1)^C}2(λn+1)C, both at degree CCC in the input size, no answer longer than 2(λn+1)C2^{(\lambda n+1)^C}2(λn+1)C accepted) and the size bound ∣Dintro∣≤C(λ+1)C|\mathcal{D}^{\mathrm{intro}}| \le C(\lambda+1)^C∣Dintro∣≤C(λ+1)C; completeness: for a λ\lambdaλ-bounded ℓ\ellℓ-level V\mathcal{V}V, a value-111 PCC strategy for V2n\mathcal{V}_{2^n}V2n​ (answers at most (2n)λ(2^n)^\lambda(2n)λ) gives one for the output at nnn (answers at most 2(λn+1)C2^{(\lambda n+1)^C}2(λn+1)C); soundness: for λ\lambdaλ-bounded V\mathcal{V}V, n≥1n \ge 1n≥1 and ε>0\varepsilon > 0ε>0, val∗(outputn)>1−ε\mathrm{val}^*(\text{output}_n) > 1 - \varepsilonval∗(outputn​)>1−ε implies val∗(V2n)≥1−δ(ε,n)\mathrm{val}^*(\mathcal{V}_{2^n}) \ge 1 - \delta(\varepsilon, n)val∗(V2n​)≥1−δ(ε,n). The statement is that the contract holds at ℓ=7\ell = 7ℓ=7:

Nonempty (MIPRE.Introspection 7).\mathrm{Nonempty}\,\bigl(\mathtt{MIPRE.Introspection}\ 7\bigr).Nonempty(MIPRE.Introspection 7).

It is one of the three stage contracts (with AnswerReduction 5 and Repetition 7) from which GapCompression.ofPipeline builds a GapCompression; every conditional glue theorem of this upload imports it.

Formalization Note In the repository the inhabitant is MIPRE.Introspection.seven : Introspection 7 (MIPRE/Background/Introspection/Compiler.lean), Classical.choice exists_seven, with exists_seven proved from the Pauli basis test thm:qld as its only rigidity input (blueprint lem:introspection-supply). The contract uses the ambient running-time convention: exponent (λn+1)C(\lambda n+1)^C(λn+1)C in place of the paper's 2Cλn2^{C\lambda n}2Cλn, degrees in the input size, soundness only for n≥1n \ge 1n≥1 (the input is bounded at 2≤2n2 \le 2^n2≤2n), and the paper's a>0a > 0a>0 normalized to a≥1a \ge 1a≥1. The platform holds the statement only: the development proves it, in code the platform cannot host yet.

Preamble
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Polynomial.Eval.Defs
import Mathlib.Analysis.CStarAlgebra.CStarMatrix
import Mathlib.Analysis.CStarAlgebra.Classes
import Mathlib.Analysis.Matrix.Order
import Mathlib.Data.ENat.Lattice
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.List.Basic
import Mathlib.Data.Nat.Bits
import Mathlib.Data.Nat.Notation
import Mathlib.Data.Nat.Size
import Mathlib.Data.Real.Basic
import Mathlib.Data.ZMod.Basic
import Mathlib.LinearAlgebra.Matrix.Kronecker
import Mathlib.LinearAlgebra.Pi
import Definitions.Def_MIPRE_Foundations_CL_Register
import Definitions.Def_MIPRE_Foundations_CL_Basic
import Definitions.Def_MIPRE_Foundations_CL_Closure
import Definitions.Def_MIPRE_Foundations_Cost_Basic
import Definitions.Def_MIPRE_Foundations_Cost_Basic_B
import Definitions.Def_MIPRE_Foundations_Cost_Encoding
import Definitions.Def_MIPRE_Foundations_Cost_Encoding_B
import Definitions.Def_MIPRE_Foundations_Cost_PolyTime
import Definitions.Def_MIPRE_Foundations_CL_Sampler
import Definitions.Def_MIPRE_Foundations_Games
import Definitions.Def_MIPRE_Foundations_GameTransport
import Definitions.Def_MIPRE_Foundations_GameDouble
import Definitions.Def_MIPRE_Foundations_Verifier
import Definitions.Def_MIPRE_Foundations_GapCompression
import Definitions.Def_MIPRE_Foundations_VerifierValue
import Definitions.Def_MIPRE_Foundations_Pipeline_Budget
import Definitions.Def_MIPRE_Foundations_Pipeline_Introspection
Formal statement
theorem MIPRE.Introspection.nonempty_seven : Nonempty (MIPRE.Introspection 7) := by sorry
Source
https://github.com/vidick/MIPRE-formalization/blob/70cbf1c52e3d5e1dff1162fdf952c9a9f4bd99ed/MIPRE/Background/Introspection/Compiler.lean

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