Lemma prog_run_direct of the MIP* = RE formalization
ProvedMIPRE.Introspection.SamplerProgram.prog_run_directA statement of the module MIPRE.Foundations.Introspection.SamplerProgram of the MIP* = RE formalization (commit 70cbf1c of vidick/MIPRE-formalization). The executable typed introspection sampler router. Dimension queries and Pauli queries call the supplied sampler once. Auxiliary queries write the zero vector or the appropriate factor indicator, using the length of the supplied vector. This total router needs no decoding of the ambient dimension and does not depend on the number of hiding types.
Formal statement. In Lean, with the scope shown:
open MIPRE
open MIPRE.Introspection
open MIPRE.Introspection.SamplerProgram
open MIPRE.Cost MIPRE.Cost.PolyTimeFun MIPRE.CL MIPRE.CL.Detyping.Program
theorem MIPRE.Introspection.SamplerProgram.prog_run_direct {P : Type*} [SizedEncoding P] (S : TypedSampler 3 P)
(x : Data) (out : BitStr) (h : route x = directResult out) :
∃ t, (prog S).Runs x (encode out) t
Formalization Note MIPRE.Introspection.SamplerProgram.prog_run_direct is declared in MIPRE/Foundations/Introspection/SamplerProgram.lean, lines 123–125. The binders, hypotheses and conclusion are exactly those of the Lean statement above; the uploaded statement elaborates to the same type as the declaration in the repository. The definitions it mentions are those of the published definition bundles of the module's import closure.
import Mathlib.Algebra.BigOperators.Group.Finset.Basic import Mathlib.Algebra.BigOperators.Ring.Finset import Mathlib.Algebra.Polynomial.Degree.Lemmas import Mathlib.Algebra.Polynomial.Eval.Defs import Mathlib.Algebra.Polynomial.Eval.Degree import Mathlib.Analysis.CStarAlgebra.CStarMatrix import Mathlib.Analysis.CStarAlgebra.Classes import Mathlib.Analysis.Matrix.Order import Mathlib.Data.ENat.Lattice import Mathlib.Data.Finset.Image import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Fintype.Option import Mathlib.Data.Fintype.Pi import Mathlib.Data.Fintype.Prod import Mathlib.Data.Fintype.Sum import Mathlib.Data.List.Basic import Mathlib.Data.List.OfFn 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 Mathlib.Logic.Equiv.Fin.Basic import Mathlib.Tactic.DeriveFintype import Mathlib.Tactic.Linarith import Mathlib.Tactic.Ring import Definitions.Def_MIPRE_Foundations_Games import Definitions.Def_MIPRE_Foundations_CL_Register import Definitions.Def_MIPRE_Foundations_CL_Basic import Definitions.Def_MIPRE_Foundations_Cost_Basic_B import Definitions.Def_MIPRE_Foundations_Cost_Encoding_B import Definitions.Def_MIPRE_Foundations_SAT_Circuit import Definitions.Def_MIPRE_Foundations_Cost_PolyTime import Definitions.Def_MIPRE_Foundations_CL_Closure_B import Definitions.Def_MIPRE_Foundations_CL_Sampler import Definitions.Def_MIPRE_Foundations_Cost_Closure import Definitions.Def_MIPRE_Foundations_Cost_Loops_B import Definitions.Def_MIPRE_Foundations_Cost_Fold import Definitions.Def_MIPRE_Foundations_Cost_Unary import Definitions.Def_MIPRE_Foundations_Cost_Numeric_B import Definitions.Def_MIPRE_Foundations_GameTransport import Definitions.Def_MIPRE_Foundations_GameAdapt import Definitions.Def_MIPRE_Foundations_CL_Embedding import Definitions.Def_MIPRE_Foundations_CL_Graph import Definitions.Def_MIPRE_Foundations_CL_Detyping import Definitions.Def_MIPRE_Foundations_CL_DetypingLaw import Definitions.Def_MIPRE_Foundations_SampledGame import Definitions.Def_MIPRE_Foundations_CL_DetypingGame import Definitions.Def_MIPRE_Foundations_CL_TypedSampler import Definitions.Def_MIPRE_Foundations_Cost_Binary import Definitions.Def_MIPRE_Foundations_SAT_Formula import Definitions.Def_MIPRE_Foundations_SAT_FmlLib import Definitions.Def_MIPRE_Foundations_SAT_Flatten import Definitions.Def_MIPRE_Foundations_Cost_Reader import Definitions.Def_MIPRE_Foundations_SAT_FmlProg import Definitions.Def_MIPRE_Foundations_SAT_ArrayProg import Definitions.Def_MIPRE_Foundations_Cost_BinaryArithmetic import Definitions.Def_MIPRE_Foundations_Cost_BinaryCompare import Definitions.Def_MIPRE_Foundations_Cost_TreeBits import Definitions.Def_MIPRE_Foundations_CL_DetypingProgFinite import Definitions.Def_MIPRE_Foundations_CL_DetypingProgParse import Definitions.Def_MIPRE_Foundations_CL_DetypingQueries import Definitions.Def_MIPRE_Foundations_CL_DetypingProgBits import Definitions.Def_MIPRE_Foundations_CL_DetypingProgCall import Definitions.Def_MIPRE_Foundations_CL_DetypingProgRoute import Definitions.Def_MIPRE_Foundations_Cost_Growth import Definitions.Def_MIPRE_Foundations_CL_DetypingProgQueries import Definitions.Def_MIPRE_Foundations_CL_DetypingProgSampler import Definitions.Def_MIPRE_Foundations_CL_DetypingProgCost import Definitions.Def_MIPRE_Foundations_Introspection_Types import Definitions.Def_MIPRE_Foundations_Introspection_TypeGraph import Definitions.Def_MIPRE_Foundations_Introspection_TypedPresentation import Definitions.Def_MIPRE_Foundations_Introspection_SamplerProgram open MIPRE open MIPRE.Introspection open MIPRE.Introspection.SamplerProgram open MIPRE.Cost MIPRE.Cost.PolyTimeFun MIPRE.CL MIPRE.CL.Detyping.Program
theorem MIPRE.Introspection.SamplerProgram.prog_run_direct {P : Type*} [SizedEncoding P] (S : TypedSampler 3 P)
(x : Data) (out : BitStr) (h : route x = directResult out) :
∃ t, (prog S).Runs x (encode out) t := by sorry