Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

An answer reduction stage exists for five-level normal form verifiers

Proved
MIPRE.AnswerReduction.nonempty_five

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

gap-compressionmip-remipre-formalizationnonlocal-gamesverifiers

MIPRE.AnswerReduction ℓ (blueprint thm:answer-reduction) records the data and guarantees of answer reduction for ℓ\ellℓ-level verifiers: constants a≥1a \ge 1a≥1, 0<b≤10 < b \le 10<b≤1 of the soundness loss δ(ε,n)=σa((λn)μaεb+(λn)−μb)\delta(\varepsilon, n) = \sigma^a\bigl((\lambda n)^{\mu a}\varepsilon^b + (\lambda n)^{-\mu b}\bigr)δ(ε,n)=σa((λn)μaεb+(λn)−μb); a threshold CCC; a polynomial bound and degree deg for the output bound bound((λn+1)μ+σ+λ+n)μ+1\mathrm{bound}\bigl((\lambda n+1)^\mu + \sigma + \lambda + n\bigr)^{\mu+1}bound((λn+1)μ+σ+λ+n)μ+1 at degree deg⁡⋅(μ+1)\deg\cdot(\mu+1)deg⋅(μ+1); the answer-reduced sampler, a function of the input sampler and (λ,μ,σ)(\lambda, \mu, \sigma)(λ,μ,σ) with polynomial-time program; the polynomial-time compute of the answer-reduced decider from the input programs and (λ,μ,σ)(\lambda, \mu, \sigma)(λ,μ,σ); and the output verifier of level max⁡(ℓ+2,5)\max(\ell+2, 5)max(ℓ+2,5). For an input V\mathcal{V}V within the budget inBudget(λ,μ,n)\mathrm{inBudget}(\lambda,\mu,n)inBudget(λ,μ,n) at index nnn (sampler and dimension within (λn+1)μ(\lambda n+1)^\mu(λn+1)μ, decider and accepted answers within 2(λn+1)μ2^{(\lambda n+1)^\mu}2(λn+1)μ, degree μ\muμ): if ∣V∣≤σ|\mathcal{V}| \le \sigma∣V∣≤σ the output is within the output bound, rejecting longer answers (complexity); for n≥Cn \ge Cn≥C, λ,μ≥1\lambda, \mu \ge 1λ,μ≥1 and ∣D∣≤σ|\mathcal{D}| \le \sigma∣D∣≤σ, a value-111 PCC strategy for Vn\mathcal{V}_nVn​ gives one for the output at nnn (completeness); for n≥max⁡(C,2)n \ge \max(C, 2)n≥max(C,2), λ≥1\lambda \ge 1λ≥1, ∣D∣≤σ|\mathcal{D}| \le \sigma∣D∣≤σ and ε>0\varepsilon > 0ε>0, val∗(outputn)>1−ε\mathrm{val}^*(\text{output}_n) > 1 - \varepsilonval∗(outputn​)>1−ε implies val∗(Vn)≥1−δ(ε,n)\mathrm{val}^*(\mathcal{V}_n) \ge 1 - \delta(\varepsilon, n)val∗(Vn​)≥1−δ(ε,n) (soundness). The statement: the contract holds at ℓ=5\ell = 5ℓ=5:

Nonempty (MIPRE.AnswerReduction 5).\mathrm{Nonempty}\,\bigl(\mathtt{MIPRE.AnswerReduction}\ 5\bigr).Nonempty(MIPRE.AnswerReduction 5).

The level 555 is the introspective verifier's, and the output is read at max⁡(5+2,5)=7\max(5+2, 5) = 7max(5+2,5)=7 levels, as GapCompression.ofPipeline requires. In MIPRE/Background/Pipeline.lean every chapter 7 consequence is stated with an AnswerReduction 5 as its single remaining hypothesis; this leaf is that hypothesis.

Formalization Note In the repository the inhabitant is MIPRE.AnswerReduction.answerReduction, arVerifier over the classical PCP decider TM.CookLevin.Pad.classicalPcpDecider. The contract adapts the paper's absolute-time hypothesis TIMED(n)≤(2λn)μ\mathrm{TIME}_{\mathcal{D}}(n) \le (2^{\lambda n})^\muTIMED​(n)≤(2λn)μ to degrees in the input size, bounds the input sampler's size by σ\sigmaσ too, and keeps the paper's threshold CarC_{\mathrm{ar}}Car​ and regime λ,μ≥1\lambda, \mu \ge 1λ,μ≥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_AnswerReduction
Formal statement
theorem MIPRE.AnswerReduction.nonempty_five : Nonempty (MIPRE.AnswerReduction 5) := by sorry
Source
https://github.com/vidick/MIPRE-formalization/blob/70cbf1c52e3d5e1dff1162fdf952c9a9f4bd99ed/MIPRE/Background/AnswerReduction/Instance.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