Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Palomar / LowDegreeGameBridge

Definition
QPBT_QPBT_Palomar_LowDegreeGameBridge

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

qpbt

This bundle bridges the compact Palomar low-degree game representation with the original typed game spaces. It defines parameter copying, equivalences for question and answer carriers, common source and question-pair spaces, and the compact seed-index map.

Principal definitions:

  • MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams: copies LDT parameters into the compact domain, using LowDegreeParams.
  • MIPStarRE.QPBT.Palomar.lowDegreeTypeEquiv: equates compact and original question-type carriers.
  • MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv: identifies the compact and original spaces.
  • MIPStarRE.QPBT.Palomar.lowDegreeQuestionEquiv: the typed question equivalence.
  • MIPStarRE.QPBT.Palomar.lowDegreeAnswerEquiv: the answer-carrier equivalence.
  • MIPStarRE.QPBT.Palomar.lowDegreeSourceEquiv: the common-source equivalence.
  • MIPStarRE.QPBT.Palomar.lowDegreeQuestionPairEquiv: the ordered question-pair equivalence.
  • MIPStarRE.QPBT.Palomar.lowDegreeChiIndex_eq: identifies the compact seed index with the original map.

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/Palomar/LowDegreeGameBridge.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_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_Tactic_AvgCongr
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyCore
import Definitions.Def_QPBT_QPBT_Algebra_Coefficients
import Definitions.Def_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Algebra_Lines
import Definitions.Def_QPBT_QPBT_Palomar_Definitions
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGame
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGameMeasurements
import Mathlib

namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace MIPStarRE.QPBT.Palomar
end MIPStarRE.QPBT.Palomar

/-!
# Exact bridge for the compact low individual degree game

This module identifies the compact product-space game with the existing
low-degree game.  The bridge is by explicit equivalences of question
coordinates and answer summands.  It preserves the question PMF, every branch
of the Boolean verifier, and the value of every compact strategy exactly.

## References

`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-440`.
-/

@[expose] public section

open scoped BigOperators

namespace MIPStarRE.QPBT.Palomar

open LIDT.MIPStarRE.LDT

/-- Copy the original numerical parameter record into the compact domain. -/
@[reducible] def LowDegreeParams.ofLdParams
    (P : _root_.MIPStarRE.QPBT.LdParams) : _root_.MIPStarRE.QPBT.Palomar.LowDegreeParams where
  q := P.q
  m := P.m
  d := P.d
  k := P.k
  hm := P.hm
  hd := P.hd
  hk := P.hk
  hq := P.hq
  hdvd := P.hdvd

/-- The compact and original three-element question-type carriers are equivalent. -/
def lowDegreeTypeEquiv : _root_.MIPStarRE.QPBT.Palomar.LowDegreeType ≃ _root_.MIPStarRE.QPBT.LdType where
  toFun
    | .point => .point
    | .aline => .aline
    | .dline => .dline
  invFun
    | .point => .point
    | .aline => .aline
    | .dline => .dline
  left_inv t := by cases t <;> rfl
  right_inv t := by cases t <;> rfl

/-- Split-function coordinates identify the complete compact and original spaces. -/
def lowDegreeSpaceEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P) ≃
      _root_.MIPStarRE.QPBT.LdSpace P :=
  (_root_.MIPStarRE.QPBT.ldSpaceSplit P).symm

/-- Typed questions are equivalent by the explicit type and coordinate maps. -/
def lowDegreeQuestionEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.MIPStarRE.QPBT.Palomar.LowDegreeQuestion (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P) ≃
      _root_.MIPStarRE.QPBT.LdQuestion P :=
  Equiv.prodCongr _root_.MIPStarRE.QPBT.Palomar.lowDegreeTypeEquiv (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P)

/-- The three answer summands are exactly the original answer constructors. -/
@[reducible] noncomputable def lowDegreeAnswerEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.MIPStarRE.QPBT.Palomar.LowDegreeAnswer (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P) ≃
      _root_.MIPStarRE.QPBT.LdAnswer P :=
  (_root_.MIPStarRE.QPBT.ldAnswerEquiv P).symm

/-- The complete common-source spaces are equivalent coordinate by coordinate. -/
def lowDegreeSourceEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
    ((_root_.MIPStarRE.QPBT.Palomar.LowDegreeType × _root_.MIPStarRE.QPBT.Palomar.LowDegreeType) ×
        _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) ≃
      ((_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType) ×
        _root_.MIPStarRE.QPBT.LdSpace P) :=
  Equiv.prodCongr (Equiv.prodCongr _root_.MIPStarRE.QPBT.Palomar.lowDegreeTypeEquiv _root_.MIPStarRE.QPBT.Palomar.lowDegreeTypeEquiv)
    (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P)

/-- Equivalence of the two ordered question-pair carriers. -/
def lowDegreeQuestionPairEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
    (_root_.MIPStarRE.QPBT.Palomar.LowDegreeQuestion (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P) ×
        _root_.MIPStarRE.QPBT.Palomar.LowDegreeQuestion (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) ≃
      (_root_.MIPStarRE.QPBT.LdQuestion P × _root_.MIPStarRE.QPBT.LdQuestion P) :=
  Equiv.prodCongr (_root_.MIPStarRE.QPBT.Palomar.lowDegreeQuestionEquiv P) (_root_.MIPStarRE.QPBT.Palomar.lowDegreeQuestionEquiv P)

/-- The compact seed-index map is the original `chiIndex`. -/
@[simp] theorem lowDegreeChiIndex_eq (P : _root_.MIPStarRE.QPBT.LdParams)
    (s : _root_.MIPStarRE.QPBT.ScalarQ P) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreeChiIndex (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P)
        (_root_.MIPStarRE.QPBT.binaryRepresentation P.model) s =
      _root_.MIPStarRE.QPBT.chiIndex P s := by
  rfl

/-- The compact prefix projection is the original prefix projection. -/
@[simp] theorem lowDegreePrefix_eq (P : _root_.MIPStarRE.QPBT.LdParams)
    (i : Fin P.m) (v : Fin P.m → _root_.MIPStarRE.QPBT.ScalarQ P) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreePrefix i v = _root_.MIPStarRE.QPBT.prefixProjection i v :=
  rfl

/-- The compact least nonzero coordinate is the one used by the published formula. -/
theorem lowDegreePivot_eq_linePivotIndex {K : Type} [Field K] [DecidableEq K]
    {m : ℕ} (v : Fin m → K) (hv : v ≠ 0) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreePivot v hv = _root_.MIPStarRE.QPBT.linePivotIndex v hv := by
  have hpivot_ne : v (_root_.MIPStarRE.QPBT.Palomar.lowDegreePivot v hv) ≠ 0 := by
    unfold _root_.MIPStarRE.QPBT.Palomar.lowDegreePivot
    change v ((Finset.univ.filter fun j : Fin m => v j ≠ 0).min' _) ≠ 0
    exact (Finset.mem_filter.mp (Finset.min'_mem
      (Finset.univ.filter fun j : Fin m => v j ≠ 0) _)).2
  have hpivot_le (i : Fin m) (hi : v i ≠ 0) : _root_.MIPStarRE.QPBT.Palomar.lowDegreePivot v hv ≤ i := by
    unfold _root_.MIPStarRE.QPBT.Palomar.lowDegreePivot
    change (Finset.univ.filter fun j : Fin m => v j ≠ 0).min' _ ≤ i
    exact Finset.min'_le _ i (by simp [hi])
  apply le_antisymm
  · exact hpivot_le _ (_root_.MIPStarRE.QPBT.linePivotIndex_ne_zero v hv)
  · apply le_of_not_gt
    intro hlt
    exact hpivot_ne (_root_.MIPStarRE.QPBT.linePivotIndex_zero_before v hv _ hlt)

/-- The compact elementary representative is exactly the canonical representative. -/
theorem lowDegreeLineRep_eq_lineRepMap {K : Type} [Field K] [DecidableEq K]
    {m : ℕ} (u v : Fin m → K) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep u v = _root_.MIPStarRE.QPBT.lineRepMap v u := by
  rw [_root_.MIPStarRE.QPBT.lineRepMap_apply_eq_explicitLineRep]
  simp only [_root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep, _root_.MIPStarRE.QPBT.explicitLineRep]
  split_ifs with hv
  · rfl
  · rw [_root_.MIPStarRE.QPBT.Palomar.lowDegreePivot_eq_linePivotIndex v hv]

/-- The compact point map agrees with the original point map. -/
theorem lowDegreeMap_point_equiv (P : _root_.MIPStarRE.QPBT.LdParams)
    (z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P
        (_root_.MIPStarRE.QPBT.Palomar.lowDegreeMap (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P)
          (_root_.MIPStarRE.QPBT.binaryRepresentation P.model)
          .point z) =
      _root_.MIPStarRE.QPBT.ldPointCL P (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) := by
  rfl

/-- The compact axis-line map agrees with the original axis-line map. -/
theorem lowDegreeMap_aline_equiv (P : _root_.MIPStarRE.QPBT.LdParams)
    (z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P
        (_root_.MIPStarRE.QPBT.Palomar.lowDegreeMap (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P)
          (_root_.MIPStarRE.QPBT.binaryRepresentation P.model)
          .aline z) =
      _root_.MIPStarRE.QPBT.ldALineCL P (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) := by
  funext i
  rcases i with (j | u) | j
  · change _root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep z.1.1
        (Pi.single (_root_.MIPStarRE.QPBT.chiIndex P z.1.2) 1) j =
      _root_.MIPStarRE.QPBT.lineRepMap
        (_root_.MIPStarRE.QPBT.coordinateDirection (_root_.MIPStarRE.QPBT.chiIndex P z.1.2))
        z.1.1 j
    rw [_root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep_eq_lineRepMap]
    rfl
  · cases u
    rfl
  · rfl

/-- The compact diagonal-line map agrees with the original diagonal-line map. -/
theorem lowDegreeMap_dline_equiv (P : _root_.MIPStarRE.QPBT.LdParams)
    (z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P
        (_root_.MIPStarRE.QPBT.Palomar.lowDegreeMap (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P)
          (_root_.MIPStarRE.QPBT.binaryRepresentation P.model)
          .dline z) =
      _root_.MIPStarRE.QPBT.ldDLineCL P (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) := by
  funext i
  rcases i with (j | u) | j
  · change _root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep z.1.1
        (_root_.MIPStarRE.QPBT.prefixProjection
          (_root_.MIPStarRE.QPBT.chiIndex P z.1.2) z.2) j =
      _root_.MIPStarRE.QPBT.lineRepMap
        (_root_.MIPStarRE.QPBT.prefixProjection
          (_root_.MIPStarRE.QPBT.chiIndex P z.1.2) z.2) z.1.1 j
    rw [_root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep_eq_lineRepMap]
  · cases u
    rfl
  · rfl

/-- All three compact question maps commute with the coordinate equivalence. -/
theorem lowDegreeMap_equiv (P : _root_.MIPStarRE.QPBT.LdParams)
    (t : _root_.MIPStarRE.QPBT.Palomar.LowDegreeType)
    (z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P
        (_root_.MIPStarRE.QPBT.Palomar.lowDegreeMap (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P)
          (_root_.MIPStarRE.QPBT.binaryRepresentation P.model) t z) =
      _root_.MIPStarRE.QPBT.ldCL P (_root_.MIPStarRE.QPBT.Palomar.lowDegreeTypeEquiv t) (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) := by
  cases t with
  | point => exact _root_.MIPStarRE.QPBT.Palomar.lowDegreeMap_point_equiv P z
  | aline => exact _root_.MIPStarRE.QPBT.Palomar.lowDegreeMap_aline_equiv P z
  | dline => exact _root_.MIPStarRE.QPBT.Palomar.lowDegreeMap_dline_equiv P z



/-- Polynomial coefficient evaluation is unchanged by the compact presentation. -/
@[simp] theorem lowDegreeEval_eq_evalCoefficient {K : Type} [Semiring K]
    {n : ℕ} (c : Fin n → K) (t : K) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreeEval c t = _root_.MIPStarRE.QPBT.evalCoefficient c t :=
  rfl

/-- The point block of the transported ambient vector is unchanged. -/
@[simp] theorem lowDegreeSpaceEquiv_point (P : _root_.MIPStarRE.QPBT.LdParams)
    (z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
    _root_.MIPStarRE.QPBT.LdSpace.point (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) = z.1.1 := by
  rfl

/-- The scalar seed of the transported ambient vector is unchanged. -/
@[simp] theorem lowDegreeSpaceEquiv_seed (P : _root_.MIPStarRE.QPBT.LdParams)
    (z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
    _root_.MIPStarRE.QPBT.LdSpace.seed (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) = z.1.2 := by
  rfl

/-- The direction block of the transported ambient vector is unchanged. -/
@[simp] theorem lowDegreeSpaceEquiv_direction (P : _root_.MIPStarRE.QPBT.LdParams)
    (z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
    _root_.MIPStarRE.QPBT.LdSpace.direction (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) = z.2 := by
  rfl

/-- Point-value answers map to the original point-value constructor. -/
@[simp] theorem lowDegreeAnswerEquiv_point (P : _root_.MIPStarRE.QPBT.LdParams)
    (a : Fin P.k → _root_.MIPStarRE.QPBT.ScalarQ P) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreeAnswerEquiv P (.inl a) = .pointVals a := by
  rfl

/-- Axis-line answers map to the original axis-line constructor. -/
@[simp] theorem lowDegreeAnswerEquiv_aline (P : _root_.MIPStarRE.QPBT.LdParams)
    (a : Fin P.k → Fin (P.d + 1) → _root_.MIPStarRE.QPBT.ScalarQ P) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreeAnswerEquiv P (.inr (.inl a)) = .alinePolys a := by
  rfl

/-- Diagonal-line answers map to the original diagonal-line constructor. -/
@[simp] theorem lowDegreeAnswerEquiv_dline (P : _root_.MIPStarRE.QPBT.LdParams)
    (a : Fin P.k → Fin (P.m * P.d + 1) → _root_.MIPStarRE.QPBT.ScalarQ P) :
    _root_.MIPStarRE.QPBT.Palomar.lowDegreeAnswerEquiv P (.inr (.inr a)) = .dlinePolys a := by
  rfl



end MIPStarRE.QPBT.Palomar
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Palomar/LowDegreeGameBridge.lean#L28-L280

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