Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Test / LowDegreeGameMeasurements

Definition
QPBT_QPBT_Test_LowDegreeGameMeasurements

by Dengnifer · Oct 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

qpbt

This bundle packages the polynomial-indexed measurements used in the low-degree game and provides the finite outcome types needed for the soundness statements. It supports both single polynomial measurements and simultaneous tuples, together with point evaluation.

Principal definitions:

  • MIPStarRE.QPBT.ldSpaceSplit: splits an ambient low-degree vector into point, seed, and direction blocks.
  • MIPStarRE.QPBT.polyFuncFintype: the finite type structure on bounded multivariate polynomials over a finite coefficient semiring.
  • MIPStarRE.QPBT.PolyIndex: a bounded multivariate polynomial outcome.
  • MIPStarRE.QPBT.PolyMeas: a POVM indexed by one bounded multivariate polynomial.
  • MIPStarRE.QPBT.PolyMeasFamily: a dependent family whose components may have different coefficient fields, variable counts, and degree bounds.
  • MIPStarRE.QPBT.PolyTuple: a simultaneous tuple of bounded polynomial representatives.
  • MIPStarRE.QPBT.PolyMeasTuple: the constant-family measurement specialization used by the low-degree soundness result.
  • MIPStarRE.QPBT.evalPolyTupleAt: evaluates every component of a polynomial tuple at a point.

Formalization Credit. This Lean declaration is part of the Quantum Pauli basis test formalization by Ruixuan Deng. The source code was generated by AI agents; Ruixuan Deng is the responsible maintainer.

Mathematical Source. The mathematical source is Ji, Natarajan, Vidick, Wright, and Yuen, MIP*=RE, arXiv:2001.04383v3.

Definition code
-- Generated from QPBT/Test/LowDegreeGameMeasurements.lean by skeleton subtraction.
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_AxisParallelLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DiagonalLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_Distribution
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LinePolynomials
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LowDegreePolynomial
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_OpFamily
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersBase
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersFiniteAnswers
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_QuantumState
import Definitions.Def_LIDT_MIPStarRE_LDT_CommutativityPoints_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_ExpansionHypercubeGraph_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_GlobalVariance_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_MakingMeasurementsProjective_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Families
import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Interpolation
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_Polynomials
import Definitions.Def_LIDT_MIPStarRE_LDT_Tactic_AvgCongr
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyCore
import Definitions.Def_LIDT_MIPStarRE_Quantum_Measurement
import Definitions.Def_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Games_DistributionMarginals
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGame
import Mathlib

namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace LIDT.MIPStarRE.LDT.Preliminaries
end LIDT.MIPStarRE.LDT.Preliminaries
namespace LIDT.MIPStarRE.Quantum
end LIDT.MIPStarRE.Quantum
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT

/-!
# Low-degree sampling and polynomial measurements

The low-degree question laws have uniform point and coordinate-index marginals,
and every sampled line is incident to its paired point.  Polynomial outcomes
are bounded multivariate polynomials. The soundness theorem using these
definitions is proved in `LowDegreeGameTheorems`.

## References

The principal definition and theorem are blueprint `def:ld-meas` and
`lem:ld-soundness`. Their paper origin is
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:243-287,392-480`.
The dimension-divisibility hypothesis is documented in
`docs/paper-gaps/qpbt_ld-dimension-divisibility.tex`.
-/

@[expose] public section

open scoped BigOperators

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.LDT
open LIDT.MIPStarRE.LDT.Preliminaries
open LIDT.MIPStarRE.Quantum

noncomputable section

/-!
### Formalization-only auxiliary facts about the ambient low-degree space
-/

/-- Formalization-only auxiliary equivalence splitting an ambient low-degree
vector into its point, seed, and direction blocks. -/
def ldSpaceSplit (L : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.MIPStarRE.QPBT.LdSpace L ≃ ((Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) × _root_.MIPStarRE.QPBT.ScalarQ L) × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) where
  toFun z := ((_root_.MIPStarRE.QPBT.LdSpace.point z, _root_.MIPStarRE.QPBT.LdSpace.seed z), _root_.MIPStarRE.QPBT.LdSpace.direction z)
  invFun p := fun i =>
    match i with
    | .inl (.inl j) => p.1.1 j
    | .inl (.inr _) => p.1.2
    | .inr j => p.2 j
  left_inv z := by
    funext i
    rcases i with (j | u) | j
    · rfl
    · cases u
      rfl
    · rfl
  right_inv p := by
    obtain ⟨⟨a, b⟩, c⟩ := p
    rfl





/-- The coordinate index of a uniformly random scalar is uniform.  This is the
balance assertion in `def:ld-question-distribution`, blueprint
`lem:chi-index-uniform`, paper
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:215-221`.
-/
theorem uniformDistribution_map_chiIndex (L : _root_.MIPStarRE.QPBT.LdParams) :
    (_root_.LIDT.MIPStarRE.LDT.uniformDistribution (_root_.MIPStarRE.QPBT.ScalarQ L)).map (_root_.MIPStarRE.QPBT.chiIndex L) =
      _root_.LIDT.MIPStarRE.LDT.uniformDistribution (Fin L.m) := by
  letI : Nonempty (Fin (L.q / L.m)) :=
    Fin.pos_iff_nonempty.mp L.seedFiberCard_pos
  exact _root_.MIPStarRE.QPBT.uniformDistribution_map_fst_of_equiv
    (_root_.MIPStarRE.QPBT.seedFiberEquiv L) (_root_.MIPStarRE.QPBT.chiIndex L) fun s => (_root_.MIPStarRE.QPBT.seedFiberEquiv_fst L s).symm

















/-- Bounded multivariate polynomials form a finite set over a finite coefficient
semiring. This is the finite outcome set required by blueprint
`def:ld-meas`, paper
`08_classical_and_quantum_low_degree_tests.tex:394-408`. -/
noncomputable instance polyFuncFintype (m : ℕ) (K : Type*)
    [CommSemiring K] [Fintype K] (d : ℕ) : Fintype ↥(_root_.LIDT.MIPStarRE.LDT.Preliminaries.polyFunc m K d) := by
  letI : Finite ↥(_root_.LIDT.MIPStarRE.LDT.Preliminaries.polyFunc m K d) := Module.finite_of_finite K
  exact Fintype.ofFinite _

/-- A bounded multivariate polynomial outcome over an arbitrary finite
coefficient semiring. -/
noncomputable abbrev PolyIndex (m : ℕ) (K : Type*) [CommSemiring K]
    [Fintype K] (d : ℕ) := ↥(_root_.LIDT.MIPStarRE.LDT.Preliminaries.polyFunc m K d)

/-- A POVM indexed by one bounded multivariate polynomial. -/
noncomputable abbrev PolyMeas (m : ℕ) (K : Type*) [CommSemiring K]
    [Fintype K] [DecidableEq K] (d : ℕ) (ι : Type*)
    [Fintype ι] [DecidableEq ι] :=
  _root_.LIDT.MIPStarRE.Quantum.Measurement (_root_.MIPStarRE.QPBT.PolyIndex m K d) ι

/-- The dependent family in `def:ld-meas`: component `i` may
have its own coefficient field, number of variables, and degree bound.
Blueprint `def:ld-meas`, paper
`08_classical_and_quantum_low_degree_tests.tex:394-408`. -/
noncomputable abbrev PolyMeasFamily (k : ℕ) (K : Fin k → Type*)
    [∀ i, CommSemiring (K i)] [∀ i, Fintype (K i)]
    [∀ i, DecidableEq (K i)] (m d : Fin k → ℕ) (ι : Type*)
    [Fintype ι] [DecidableEq ι] :=
  _root_.LIDT.MIPStarRE.Quantum.Measurement ((i : Fin k) → _root_.MIPStarRE.QPBT.PolyIndex (m i) (K i) (d i)) ι

/-- A simultaneous tuple of `L.k` bounded polynomial representatives. -/
noncomputable abbrev PolyTuple (L : _root_.MIPStarRE.QPBT.LdParams) :=
  Fin L.k → _root_.MIPStarRE.QPBT.PolyIndex L.m (_root_.MIPStarRE.QPBT.ScalarQ L) L.d

/-- The constant-family specialization used by `lem:ld-soundness`. -/
noncomputable abbrev PolyMeasTuple (L : _root_.MIPStarRE.QPBT.LdParams) (ι : Type*)
    [Fintype ι] [DecidableEq ι] :=
  _root_.MIPStarRE.QPBT.PolyMeasFamily L.k (fun _ => _root_.MIPStarRE.QPBT.ScalarQ L) (fun _ => L.m) (fun _ => L.d) ι

/-- Evaluate every component of a polynomial tuple at a point. -/
def evalPolyTupleAt {L : _root_.MIPStarRE.QPBT.LdParams} (u : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)
    (g : _root_.MIPStarRE.QPBT.PolyTuple L) : Fin L.k → _root_.MIPStarRE.QPBT.ScalarQ L :=
  fun j => MvPolynomial.eval u (g j).1

/-- Embed a geometric point into the ambient coefficient space used by a
point question. -/
def pointSpaceOf (L : _root_.MIPStarRE.QPBT.LdParams) (u : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) : _root_.MIPStarRE.QPBT.LdSpace L :=
  fun i => match i with
  | .inl (.inl j) => u j
  | .inl (.inr _) => 0
  | .inr _ => 0

/-- The typed low-degree point question associated with `u`. -/
def ldPointQuestionOf (L : _root_.MIPStarRE.QPBT.LdParams) (u : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) : _root_.MIPStarRE.QPBT.LdQuestion L :=
  (.point, _root_.MIPStarRE.QPBT.pointSpaceOf L u)

/-- Read the point component of a low-degree answer, sending answers of the
wrong form to the fixed zero tuple. This total relabeling turns the strategy's
answer measurement into the point POVM used by `lem:ld-soundness`. -/
def ldPointValuesOrZero (L : _root_.MIPStarRE.QPBT.LdParams) : _root_.MIPStarRE.QPBT.LdAnswer L → Fin L.k → _root_.MIPStarRE.QPBT.ScalarQ L
  | .pointVals values => values
  | .alinePolys _ => 0
  | .dlinePolys _ => 0

/-- The quantitative error function in `lem:ld-soundness`.  Its argument order
is `(a, b, ε, q, m, d, k)`. -/
noncomputable def deltaLd (a b ε : ℝ) (q m d k : ℕ) : ℝ :=
  a * Real.rpow (((d * m * k : ℕ) : ℝ)) a *
    (Real.rpow ε b + Real.rpow (q : ℝ) (-b) +
      Real.rpow 2 (-(b * ((m * d : ℕ) : ℝ))))

end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Test/LowDegreeGameMeasurements.lean#L43-L384

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 paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me