An introspection stage exists for seven-level normal form verifiers
ProvedMIPRE.Introspection.nonempty_sevenMIPRE.Introspection ℓ (blueprint thm:introspection) records the data and guarantees of the introspection transformation for -level normal form verifiers: constants and of the soundness loss ; a complexity constant ; a -level introspective sampler depending only on , with program computable from in polynomial time; the polynomial-time compute from a verifier's programs and to the introspective decider's program; the output, a -level verifier with that sampler and decider; the complexity clauses at every input and index (sampler within , dimension at most , decider within , both at degree in the input size, no answer longer than accepted) and the size bound ; completeness: for a -bounded -level , a value- PCC strategy for (answers at most ) gives one for the output at (answers at most ); soundness: for -bounded , and , implies . The statement is that the contract holds at :
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 in place of the paper's , degrees in the input size, soundness only for (the input is bounded at ), and the paper's normalized to . The platform holds the statement only: the development proves it, in code the platform cannot host yet.
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
theorem MIPRE.Introspection.nonempty_seven : Nonempty (MIPRE.Introspection 7) := by sorry