Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Combining / DirectLowDegree / Transport / Correspondence

Definition
QPBT_QPBT_Combining_DirectLowDegree_Transport_Correspondence

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

qpbt

This bundle establishes the correspondence between directly indexed parameters and the original LDT model. It converts fields and points, constructs coefficient polynomials, identifies axis and diagonal answer types, and forgets the auxiliary divisibility data.

Principal definitions:

  • MIPStarRE.QPBT.directScalarEquiv: the direct-to-LDT scalar equivalence.
  • MIPStarRE.QPBT.directPointEquiv: the point equivalence with reversed coordinate order.
  • MIPStarRE.QPBT.coefficientPolynomial: builds a bounded polynomial from a coefficient vector.
  • MIPStarRE.QPBT.directAxisAnswerEquiv: identifies direct axis coefficients with LDT axis answers.
  • MIPStarRE.QPBT.directDiagonalAnswerEquiv: identifies direct diagonal coefficients with LDT diagonal answers.

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/Combining/DirectLowDegree/Transport/Correspondence.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_FieldBasis
import Definitions.Def_QPBT_QPBT_Combining_DirectLowDegree_Game
import Definitions.Def_QPBT_QPBT_Combining_DirectLowDegree_Geometry
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGame
import Mathlib

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

/-!
# Question correspondence for the directly indexed low-degree game

The finite-field coordinates, polynomial answers, and question law of the
directly indexed game are equivalent to their seed-indexed and low individual
degree counterparts.

## References

- `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-458`
- `references/ldt-paper/test_definition.tex:98-151`
- `docs/paper-gaps/qpbt_ld-dimension-divisibility.tex`
-/

@[expose] public section

open scoped BigOperators MatrixOrder Matrix ComplexOrder

namespace MIPStarRE.QPBT

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

noncomputable section

/-! ## Parameters and finite-field coordinates -/

/-- Regard direct-game parameters as low individual degree test parameters.
The field size, dimension, and degree are unchanged. -/
@[reducible] def DirectLdParams.toLDTParameters (D : _root_.MIPStarRE.QPBT.DirectLdParams) : _root_.LIDT.MIPStarRE.LDT.Parameters where
  m := D.m
  q := D.q
  d := D.d
  hm := lt_of_lt_of_le Nat.zero_lt_one D.hm
  hq := by
    obtain ⟨n, hn, hq⟩ := D.hq
    rw [hq]
    exact Nat.pow_pos (by decide)
  hqPrimePower := by
    obtain ⟨n, hn, hq⟩ := D.hq
    exact ⟨2, n, Nat.prime_two, hn.pos, hq⟩

/-- The fixed QPBT field model, viewed as the field model of the low
individual degree test. -/
@[reducible] noncomputable def DirectLdParams.toLDTFieldModel (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    _root_.LIDT.MIPStarRE.LDT.FieldModel D.toLDTParameters.q :=
  D.model.toFieldModel

/-- Coordinate coding from the direct scalar field to the LDT carrier. -/
noncomputable def directScalarEquiv (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    _root_.MIPStarRE.QPBT.DirectScalarQ D ≃ _root_.LIDT.MIPStarRE.LDT.Fq D.toLDTParameters :=
  _root_.MIPStarRE.QPBT.binaryRepresentation D.model

/-- Coordinate coding identifies direct points with LDT points, with the
coordinate order reversed: direct coordinate `j` is LDT coordinate
`Fin.rev j`.  The direct game zeroes a *prefix* of a sampled diagonal
direction (`directPrefixProjection`, paper equation `eq:cl-dlnf`), whereas
the low individual degree test zeroes a *suffix*
(`extendRestrictedDirection`, `references/ldt-paper/test_definition.tex:49-65`).
Reversing the coordinate order aligns the two restriction conventions, as
required by the game
correspondence in `docs/paper-gaps/qpbt_ld-dimension-divisibility.tex`. -/
noncomputable def directPointEquiv (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    (Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) ≃ _root_.LIDT.MIPStarRE.LDT.Point D.toLDTParameters where
  toFun u i := _root_.MIPStarRE.QPBT.directScalarEquiv D (u (Fin.rev i))
  invFun u j := (_root_.MIPStarRE.QPBT.directScalarEquiv D).symm (u (Fin.rev j))
  left_inv u := by
    funext j
    simp
  right_inv u := by
    funext i
    simp

@[simp] theorem directPointEquiv_apply (D : _root_.MIPStarRE.QPBT.DirectLdParams)
    (u : Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) (i : Fin D.m) :
    _root_.MIPStarRE.QPBT.directPointEquiv D u i = _root_.MIPStarRE.QPBT.directScalarEquiv D (u (Fin.rev i)) :=
  rfl

@[simp] theorem directPointEquiv_symm_apply (D : _root_.MIPStarRE.QPBT.DirectLdParams)
    (u : _root_.LIDT.MIPStarRE.LDT.Point D.toLDTParameters) (j : Fin D.m) :
    (_root_.MIPStarRE.QPBT.directPointEquiv D).symm u j =
      (_root_.MIPStarRE.QPBT.directScalarEquiv D).symm (u (Fin.rev j)) :=
  rfl

/-! ## Bounded coefficient vectors -/

/-- Turn a coefficient vector into its polynomial of degree at most `n`. -/
noncomputable def coefficientPolynomial
    {K : Type*} [Field K] (n : ℕ) (c : Fin (n + 1) → K) : Polynomial K :=
  ((Polynomial.degreeLTEquiv K (n + 1)).symm c).1

 theorem coefficientPolynomial_degree_le
    {K : Type*} [Field K] (n : ℕ) (c : Fin (n + 1) → K) :
    (_root_.MIPStarRE.QPBT.coefficientPolynomial n c).natDegree ≤ n := by
  let p := (Polynomial.degreeLTEquiv K (n + 1)).symm c
  have hp : p.1 ∈ Polynomial.degreeLE K n := by
    rw [← Polynomial.degreeLT_succ_eq_degreeLE]
    exact p.2
  have hdegree : p.1.degree ≤ n := Polynomial.mem_degreeLE.mp hp
  by_cases hzero : p.1 = 0
  · simp [_root_.MIPStarRE.QPBT.coefficientPolynomial, p, hzero]
  · exact Polynomial.natDegree_le_iff_degree_le.mpr hdegree

@[simp]  theorem coefficientPolynomial_coeff
    {K : Type*} [Field K] (n : ℕ) (c : Fin (n + 1) → K)
    (i : Fin (n + 1)) :
    (_root_.MIPStarRE.QPBT.coefficientPolynomial n c).coeff i = c i := by
  exact congrFun ((Polynomial.degreeLTEquiv K (n + 1)).apply_symm_apply c) i



/-- Direct axis-line coefficients are equivalent to LDT bounded axis-line
polynomials over the fixed field model. -/
noncomputable def directAxisAnswerEquiv (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    letI := D.toLDTFieldModel
    _root_.MIPStarRE.QPBT.DirectDegPoly D D.d ≃ _root_.LIDT.MIPStarRE.LDT.AxisLinePolynomial D.toLDTParameters := by
  letI := D.toLDTFieldModel
  refine
    { toFun := fun c =>
        { poly := _root_.MIPStarRE.QPBT.coefficientPolynomial D.d c
          degreeBounded := by
            exact coefficientPolynomial_degree_le D.d c }
      invFun := fun f i => f.poly.coeff i
      left_inv := by
        intro c
        funext i
        exact coefficientPolynomial_coeff D.d c i
      right_inv := by
        intro f
        apply _root_.LIDT.MIPStarRE.LDT.AxisLinePolynomial.ext
        apply _root_.LIDT.MIPStarRE.LDT.linePolynomial_coeff_fin_injective D.toLDTParameters
          (coefficientPolynomial_degree_le D.d fun i => f.poly.coeff i)
          f.degreeBounded
        intro i
        exact coefficientPolynomial_coeff D.d (fun j => f.poly.coeff j) i }

/-- Direct diagonal-line coefficients are equivalent to LDT bounded
diagonal-line polynomials over the fixed field model. -/
noncomputable def directDiagonalAnswerEquiv (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    letI := D.toLDTFieldModel
    _root_.MIPStarRE.QPBT.DirectDegPoly D (D.m * D.d) ≃ _root_.LIDT.MIPStarRE.LDT.DiagonalLinePolynomial D.toLDTParameters := by
  letI := D.toLDTFieldModel
  refine
    { toFun := fun c =>
        { poly := _root_.MIPStarRE.QPBT.coefficientPolynomial (D.m * D.d) c
          degreeBounded := by
            exact coefficientPolynomial_degree_le (D.m * D.d) c }
      invFun := fun f i => f.poly.coeff i
      left_inv := by
        intro c
        funext i
        exact coefficientPolynomial_coeff (D.m * D.d) c i
      right_inv := by
        intro f
        apply _root_.LIDT.MIPStarRE.LDT.DiagonalLinePolynomial.ext
        apply _root_.LIDT.MIPStarRE.LDT.linePolynomial_coeff_fin_injective D.toLDTParameters
          (coefficientPolynomial_degree_le (D.m * D.d) fun i => f.poly.coeff i)
          f.degreeBounded
        intro i
        exact coefficientPolynomial_coeff (D.m * D.d) (fun j => f.poly.coeff j) i }





/-! ## Parameters and answers of the two QPBT game presentations -/

/-- Forget the divisibility field and expose the directly indexed parameters. -/
@[reducible] def LdParams.toDirectLdParams (L : _root_.MIPStarRE.QPBT.LdParams) : _root_.MIPStarRE.QPBT.DirectLdParams where
  q := L.q
  m := L.m
  d := L.d
  k := L.k
  hm := L.hm
  hd := L.hd
  hk := L.hk
  hq := L.hq

@[simp] theorem LdParams.toDirectLdParams_model (L : _root_.MIPStarRE.QPBT.LdParams) :
    L.toDirectLdParams.model = L.model := by
  unfold _root_.MIPStarRE.QPBT.DirectLdParams.model _root_.MIPStarRE.QPBT.LdParams.model _root_.MIPStarRE.QPBT.LdParams.toDirectLdParams
  congr

/-- The canonical answer equivalence between the seed-indexed and directly
indexed QPBT games: point answers correspond to point answers, axis-line
answers to axis-line answers, and diagonal-line answers to diagonal-line
answers. -/
noncomputable def ldDirectAnswerEquiv (L : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.MIPStarRE.QPBT.LdAnswer L ≃ _root_.MIPStarRE.QPBT.DirectLdAnswer L.toDirectLdParams where
  toFun
    | .pointVals a => .pointVals a
    | .alinePolys a => .alinePolys a
    | .dlinePolys a => .dlinePolys a
  invFun
    | .pointVals a => .pointVals a
    | .alinePolys a => .alinePolys a
    | .dlinePolys a => .dlinePolys a
  left_inv a := by cases a <;> rfl
  right_inv a := by cases a <;> rfl

/-! ## Parsing seed-indexed questions -/

/-- Parse a seed-indexed question into the directly indexed question carrying
the coordinate selected by `chiIndex`. -/
noncomputable def parseLdQuestion (L : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.MIPStarRE.QPBT.LdQuestion L → _root_.MIPStarRE.QPBT.DirectLdQuestion L.toDirectLdParams
  | (.point, z) =>
      (.point, ⟨z.point, L.toDirectLdParams.firstIndex, 0⟩)
  | (.aline, z) =>
      (.aline, ⟨z.point, _root_.MIPStarRE.QPBT.chiIndex L z.seed, 0⟩)
  | (.dline, z) =>
      (.dline, ⟨z.point, _root_.MIPStarRE.QPBT.chiIndex L z.seed, z.direction⟩)

/-- Embed a direct sample into the seed-indexed ambient space using the
specified residue in the selected seed fiber. -/
noncomputable def ldSpaceOfDirectResidue (L : _root_.MIPStarRE.QPBT.LdParams)
    (sample : _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams)
    (residue : Fin (L.q / L.m)) : _root_.MIPStarRE.QPBT.LdSpace L
  | .inl (.inl i) => sample.point i
  | .inl (.inr _) => _root_.MIPStarRE.QPBT.seedOfIndexResidue L sample.index residue
  | .inr i => sample.direction i

@[simp] theorem ldSpaceOfDirectResidue_point (L : _root_.MIPStarRE.QPBT.LdParams)
    (sample : _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams)
    (residue : Fin (L.q / L.m)) :
    (_root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue L sample residue).point = sample.point :=
  rfl

@[simp] theorem ldSpaceOfDirectResidue_seed (L : _root_.MIPStarRE.QPBT.LdParams)
    (sample : _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams)
    (residue : Fin (L.q / L.m)) :
    (_root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue L sample residue).seed =
      _root_.MIPStarRE.QPBT.seedOfIndexResidue L sample.index residue :=
  rfl

@[simp] theorem ldSpaceOfDirectResidue_direction (L : _root_.MIPStarRE.QPBT.LdParams)
    (sample : _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams)
    (residue : Fin (L.q / L.m)) :
    (_root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue L sample residue).direction = sample.direction :=
  rfl

/-- The ambient seed-indexed sample space is a direct sample together with a
uniform residue in the selected seed fiber. -/
noncomputable def ldSpaceSeedFiberEquiv (L : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.MIPStarRE.QPBT.LdSpace L ≃ _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams × Fin (L.q / L.m) where
  toFun z :=
    (⟨z.point, (_root_.MIPStarRE.QPBT.seedFiberEquiv L z.seed).1, z.direction⟩,
      (_root_.MIPStarRE.QPBT.seedFiberEquiv L z.seed).2)
  invFun x := _root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue L x.1 x.2
  left_inv z := by
    funext i
    rcases i with (i | i)
    · rcases i with (i | i)
      · rfl
      · rcases i with ⟨⟩
        change (_root_.MIPStarRE.QPBT.seedFiberEquiv L).symm (_root_.MIPStarRE.QPBT.seedFiberEquiv L z.seed) = z.seed
        exact (_root_.MIPStarRE.QPBT.seedFiberEquiv L).symm_apply_apply z.seed
    · rfl
  right_inv x := by
    rcases x with ⟨sample, residue⟩
    apply Prod.ext
    · cases sample with
      | mk point index direction =>
          simp only [_root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue_point,
            _root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue_seed, _root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue_direction]
          rw [_root_.MIPStarRE.QPBT.seedFiberEquiv_seedOfIndexResidue]
    · simp [_root_.MIPStarRE.QPBT.seedOfIndexResidue]





/-! ## Exact question-law transport -/

/-- The common source sample is a direct common sample together with its
uniform seed-fiber residue. -/
noncomputable def ldQuestionSeedFiberEquiv (L : _root_.MIPStarRE.QPBT.LdParams) :
    ((_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType) × _root_.MIPStarRE.QPBT.LdSpace L) ≃
      (((_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType) × _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams) ×
        Fin (L.q / L.m)) :=
  (Equiv.prodCongr (Equiv.refl (_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType))
    (_root_.MIPStarRE.QPBT.ldSpaceSeedFiberEquiv L)).trans
      (Equiv.prodAssoc (_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType)
        (_root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams) (Fin (L.q / L.m))).symm









end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Combining/DirectLowDegree/Transport/Correspondence.lean#L33-L358

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