Lemma last_correct of the MIP* = RE formalization
ProvedMIPRE.Introspection.AuxiliaryBoundary.last_correctA statement of the module MIPRE.Foundations.Introspection.AuxiliaryHidingBoundaryProgram of the MIP* = RE formalization (commit 70cbf1c of vidick/MIPRE-formalization). Executable boundary edges of the hiding chain. The first edge compares the initial dual quotient and untouched tail. The last edge scans both reported prefixes, then compares those prefixes and the full dual answers. Query functions are parameters so the same programs use the proved padded-source interface.
Formal statement. In Lean, with the scope shown:
open MIPRE
open MIPRE.Introspection
open MIPRE.Introspection.AuxiliaryBoundary
open MIPRE.Cost MIPRE.Cost.PolyTimeFun MIPRE.LowDegree.BinaryLinear MIPRE.Introspection.AuxiliaryProgram MIPRE.Introspection.CLChecks
theorem MIPRE.Introspection.AuxiliaryBoundary.last_correct (f : PolyTimeFun AuxiliarySource.Context BitStr)
(m : PolyTimeFun AuxiliarySource.Context (List BitStr)) (ctx : AuxiliarySource.Context)
{n ℓ : ℕ} {P : CL.CLFun CL.𝔽₂ (Fin n) ℓ} {T : Finset (Fin n)} (hP : P.SupportedOn T)
(a b c v d : Fin n → CL.𝔽₂)
(hq : ∀ j < ℓ - 1, AuxiliaryScan.QueriesCorrectAt f m ctx P j) :
last f m ℓ (ctx, (CL.toBits a, CL.toBits b, CL.toBits c), (CL.toBits v, CL.toBits d)) = true ↔
(∃ x, (P.truncate (ℓ - 1)).eval x = P.outputPrefix (ℓ - 1) a) ∧
(∃ x, (P.truncate (ℓ - 1)).eval x = P.outputPrefix (ℓ - 1) v) ∧
CLChecks.hidingRead P (a, b, c) (v, d, ())
Formalization Note MIPRE.Introspection.AuxiliaryBoundary.last_correct is declared in MIPRE/Foundations/Introspection/AuxiliaryHidingBoundaryProgram.lean, lines 105–128. 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.CharP.Two import Mathlib.Algebra.Field.ZMod import Mathlib.Algebra.MvPolynomial.CommRing import Mathlib.Algebra.MvPolynomial.Degrees import Mathlib.Algebra.MvPolynomial.SchwartzZippel import Mathlib.Algebra.Polynomial.Degree.Lemmas import Mathlib.Algebra.Polynomial.Eval.Defs import Mathlib.Algebra.Polynomial.Eval.Degree import Mathlib.Algebra.Polynomial.Monic import Mathlib.Algebra.Polynomial.Roots import Mathlib.Analysis.CStarAlgebra.CStarMatrix import Mathlib.Analysis.CStarAlgebra.Classes import Mathlib.Analysis.CStarAlgebra.Matrix import Mathlib.Analysis.InnerProductSpace.PiL2 import Mathlib.Analysis.Matrix.Order import Mathlib.Analysis.Matrix.PosDef import Mathlib.Analysis.SpecialFunctions.Complex.Circle import Mathlib.Computability.Primrec.List 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.Matrix.Mul import Mathlib.Data.Nat.Bits import Mathlib.Data.Nat.Notation import Mathlib.Data.Nat.Size import Mathlib.Data.Rat.Cast.Order import Mathlib.Data.Real.Basic import Mathlib.Data.ZMod.Basic import Mathlib.FieldTheory.Finite.GaloisField import Mathlib.LinearAlgebra.BilinearForm.Orthogonal import Mathlib.LinearAlgebra.FiniteDimensional.Lemmas import Mathlib.LinearAlgebra.LinearIndependent.Lemmas import Mathlib.LinearAlgebra.Matrix.Kronecker import Mathlib.LinearAlgebra.Matrix.ToLin import Mathlib.LinearAlgebra.Pi import Mathlib.Logic.Denumerable import Mathlib.Logic.Equiv.Fin.Basic import Mathlib.Logic.Function.Iterate import Mathlib.RingTheory.Trace.Basic import Mathlib.Tactic.DeriveFintype import Mathlib.Tactic.IntervalCases import Mathlib.Tactic.Linarith import Mathlib.Tactic.Ring import Definitions.Def_MIPRE_Foundations_Games import Definitions.Def_MIPRE_Foundations_Distances import Definitions.Def_MIPRE_Foundations_CL_Register import Definitions.Def_MIPRE_Foundations_CL_Canonical 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_Verifier 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_LowDegree_Encoding import Definitions.Def_MIPRE_Foundations_Closeness import Definitions.Def_MIPRE_Foundations_PerfectStrategy import Definitions.Def_MIPRE_Foundations_GameTransport import Definitions.Def_MIPRE_Foundations_GameDouble import Definitions.Def_MIPRE_Foundations_OpBound import Definitions.Def_MIPRE_Foundations_OpBound_B import Definitions.Def_MIPRE_Foundations_StateDistance import Definitions.Def_MIPRE_Foundations_StateDistance_B import Definitions.Def_MIPRE_Foundations_POVMValue import Definitions.Def_MIPRE_Foundations_Sign import Definitions.Def_MIPRE_Foundations_CrossConsistency import Definitions.Def_MIPRE_Foundations_CrossConsistency_B import Definitions.Def_MIPRE_Foundations_PVM import Definitions.Def_MIPRE_Foundations_PVM_B import Definitions.Def_MIPRE_Foundations_Commutation import Definitions.Def_MIPRE_Foundations_Dilation import Definitions.Def_MIPRE_Foundations_Expanded import Definitions.Def_MIPRE_Foundations_LowDegree_SchwartzZippel import Definitions.Def_MIPRE_Foundations_LowDegree_Anticomm import Definitions.Def_MIPRE_Foundations_Weyl import Definitions.Def_MIPRE_Foundations_Parseval import Definitions.Def_MIPRE_Foundations_Linearity import Definitions.Def_MIPRE_Foundations_Sandwich import Definitions.Def_MIPRE_Foundations_Pasting 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_GapCompression import Definitions.Def_MIPRE_Foundations_Cost_Codable_B import Definitions.Def_MIPRE_Foundations_Halting_Descriptions import Definitions.Def_MIPRE_Foundations_CL_TypedSampler import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryRepresentation import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPolynomial 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_LowDegree_BinaryLinear import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryElimination import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryBasisProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryEchelon import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryEchelon_B import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryBasis import Definitions.Def_MIPRE_Foundations_LowDegree_BinarySolve import Definitions.Def_MIPRE_Foundations_LowDegree_BinarySolve_B import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryMatrixSolve import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryMatrixSolve_B import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryKernel 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_Machine_B import Definitions.Def_MIPRE_Foundations_Cost_MachineData_B import Definitions.Def_MIPRE_Foundations_Cost_Interpreter_B import Definitions.Def_MIPRE_Foundations_Cost_MachineBound_B import Definitions.Def_MIPRE_Foundations_Cost_Toolkit_B import Definitions.Def_MIPRE_Foundations_Cost_Universal_B import Definitions.Def_MIPRE_Foundations_Halting_Lists_B import Definitions.Def_MIPRE_Foundations_Cost_Growth import Definitions.Def_MIPRE_Foundations_Halting_Arith import Definitions.Def_MIPRE_Foundations_Halting_Arith_B import Definitions.Def_MIPRE_Foundations_VerifierValue import Definitions.Def_MIPRE_Foundations_Pipeline_Budget 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_CL_DetypingDeciderRoute import Definitions.Def_MIPRE_Foundations_CL_DetypingDeciderProg import Definitions.Def_MIPRE_Foundations_CL_DetypingClock import Definitions.Def_MIPRE_Foundations_Pipeline_Introspection import Definitions.Def_MIPRE_Foundations_Halting_PolyBounded import Definitions.Def_MIPRE_Foundations_Introspection_ClockArithmetic import Definitions.Def_MIPRE_Foundations_Introspection_ParserBits import Definitions.Def_MIPRE_Foundations_Introspection_ParserAnswers import Definitions.Def_MIPRE_Foundations_Introspection_DynamicParserSlice import Definitions.Def_MIPRE_Foundations_Introspection_DynamicParser import Definitions.Def_MIPRE_Foundations_Introspection_Clock import Definitions.Def_MIPRE_Foundations_Introspection_ClockCost import Definitions.Def_MIPRE_Foundations_Introspection_ClockSimulation import Definitions.Def_MIPRE_Foundations_Introspection_SourceCompilerGuard import Definitions.Def_MIPRE_Foundations_WeylEPR import Definitions.Def_MIPRE_Foundations_Introspection_Types import Definitions.Def_MIPRE_Foundations_Introspection_SamplingPrefix import Definitions.Def_MIPRE_Foundations_Introspection_TwirlDistance import Definitions.Def_MIPRE_Foundations_Introspection_LinearMeasurement import Definitions.Def_MIPRE_Foundations_Introspection_CommutatorParseval import Definitions.Def_MIPRE_Foundations_Introspection_BlockTwirl import Definitions.Def_MIPRE_Foundations_Introspection_BlockPOVM import Definitions.Def_MIPRE_Foundations_Introspection_EPR import Definitions.Def_MIPRE_Foundations_Introspection_BlockRetention import Definitions.Def_MIPRE_Foundations_Introspection_PauliMixing import Definitions.Def_MIPRE_Foundations_Introspection_RegisterTransport import Definitions.Def_MIPRE_Foundations_Introspection_RegisterEPR import Definitions.Def_MIPRE_Foundations_Introspection_RegisterMixing import Definitions.Def_MIPRE_Foundations_Introspection_RegisterCoordinates import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryChecks import Definitions.Def_MIPRE_Foundations_Introspection_TypedPredicate import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryReadProgram import Definitions.Def_MIPRE_Foundations_Introspection_ClockedQueryProgram import Definitions.Def_MIPRE_Foundations_Introspection_Readout import Definitions.Def_MIPRE_Foundations_Introspection_FinalExtraction import Definitions.Def_MIPRE_Foundations_Introspection_TypeGraph import Definitions.Def_MIPRE_Foundations_Introspection_HonestCore import Definitions.Def_MIPRE_Foundations_Introspection_ConditionalNormalizer import Definitions.Def_MIPRE_Foundations_Introspection_HonestFirstHide import Definitions.Def_MIPRE_Foundations_Introspection_HonestAdaptive import Definitions.Def_MIPRE_Foundations_Introspection_HonestRead import Definitions.Def_MIPRE_Foundations_Introspection_HonestXCoordinates import Definitions.Def_MIPRE_Foundations_Introspection_HonestHidingStep import Definitions.Def_MIPRE_Foundations_Introspection_HonestHiding import Definitions.Def_MIPRE_Foundations_Introspection_HonestLabelSupport import Definitions.Def_MIPRE_Foundations_Introspection_TypedPresentation import Definitions.Def_MIPRE_Foundations_Introspection_TypedEstimates import Definitions.Def_MIPRE_Foundations_Introspection_HidingRigidity import Definitions.Def_MIPRE_Foundations_Introspection_HonestHidingChecks import Definitions.Def_MIPRE_Foundations_Introspection_HonestHidingAcceptance import Definitions.Def_MIPRE_Foundations_Introspection_HidingMaps import Definitions.Def_MIPRE_Foundations_Introspection_ConditionalNormalizerIdeal import Definitions.Def_MIPRE_Foundations_Introspection_AdaptivePrefixFactor import Definitions.Def_MIPRE_Foundations_Introspection_TypedPrefixChain import Definitions.Def_MIPRE_Foundations_Introspection_ReadChainMaps import Definitions.Def_MIPRE_Foundations_Introspection_AdaptiveResidual import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryPrefixSolve import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryMaskProgram import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryCanonicalProgram import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryDualProgram import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryDualKernel import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryQuotientProgram import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryDualDecode import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryQuotientChecks import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliarySourceQueries import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryScanStage import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryScanProgram import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryScanCorrect import Definitions.Def_MIPRE_Foundations_Introspection_AuxiliaryHidingBoundaryProgram open MIPRE open MIPRE.Introspection open MIPRE.Introspection.AuxiliaryBoundary open MIPRE.Cost MIPRE.Cost.PolyTimeFun MIPRE.LowDegree.BinaryLinear MIPRE.Introspection.AuxiliaryProgram MIPRE.Introspection.CLChecks
theorem MIPRE.Introspection.AuxiliaryBoundary.last_correct (f : PolyTimeFun AuxiliarySource.Context BitStr)
(m : PolyTimeFun AuxiliarySource.Context (List BitStr)) (ctx : AuxiliarySource.Context)
{n ℓ : ℕ} {P : CL.CLFun CL.𝔽₂ (Fin n) ℓ} {T : Finset (Fin n)} (hP : P.SupportedOn T)
(a b c v d : Fin n → CL.𝔽₂)
(hq : ∀ j < ℓ - 1, AuxiliaryScan.QueriesCorrectAt f m ctx P j) :
last f m ℓ (ctx, (CL.toBits a, CL.toBits b, CL.toBits c), (CL.toBits v, CL.toBits d)) = true ↔
(∃ x, (P.truncate (ℓ - 1)).eval x = P.outputPrefix (ℓ - 1) a) ∧
(∃ x, (P.truncate (ℓ - 1)).eval x = P.outputPrefix (ℓ - 1) v) ∧
CLChecks.hidingRead P (a, b, c) (v, d, ()) := by sorry