Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Combining / DirectLowDegree / Geometry

Definition
QPBT_QPBT_Combining_DirectLowDegree_Geometry

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

qpbt

This bundle defines the parameter and sample geometry of the directly indexed low-degree game. It fixes the direct scalar model, exposes a first coordinate, defines common samples, and provides equivalences separating points, stored indices, and remaining independent coordinates.

Principal definitions:

  • MIPStarRE.QPBT.DirectLdParams: parameters for the directly indexed low-degree game.
  • MIPStarRE.QPBT.DirectLdParams.model: the canonical direct scalar model.
  • MIPStarRE.QPBT.DirectScalarQ: the direct game's scalar field.
  • MIPStarRE.QPBT.DirectLdSpace: the common random sample space.
  • MIPStarRE.QPBT.directLdSpacePointEquiv: decomposes a sample into point and remaining coordinates.
  • MIPStarRE.QPBT.directLdSpaceIndexEquiv: decomposes a sample into stored index and remaining coordinates.

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/Geometry.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_Tactic_AvgCongr
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyCore
import Definitions.Def_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Algebra_Lines
import Definitions.Def_QPBT_QPBT_Games_DistributionAux
import Definitions.Def_QPBT_QPBT_Observables_LineDefs
import Definitions.Def_QPBT_QPBT_Test_PauliBasisTest
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

/-!
# Geometry for the directly indexed low-degree game

This module defines the parameters, line carrier, and line-point distributions
for the directly indexed low-degree game.

## References

The line-point distributions originate in
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:243-272`.
The directly indexed repair 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

/-- Parameters for the directly indexed low-degree game.  Unlike `LdParams`,
this directly indexed line-space construction has no divisibility field: its coordinate index is
sampled from `Fin m` rather than encoded by fibers of `chiIndex`.

This is the direct-index repair described in
`docs/paper-gaps/qpbt_ld-dimension-divisibility.tex`; it is not a second
definition of the source verifier game. -/
structure DirectLdParams where
  q : ℕ
  m : ℕ
  d : ℕ
  k : ℕ
  hm : 1 ≤ m
  hd : 1 ≤ d
  hk : 1 ≤ k
  hq : _root_.MIPStarRE.QPBT.IsAdmissibleSize q

/-- The canonical scalar model for directly indexed parameters. -/
@[reducible] noncomputable def DirectLdParams.model
    (D : _root_.MIPStarRE.QPBT.DirectLdParams) : _root_.MIPStarRE.QPBT.FixedFieldModel D.q :=
  _root_.MIPStarRE.QPBT.fixedFieldModel D.q D.hq

/-- The scalar field of a directly indexed low-degree game. -/
abbrev DirectScalarQ (D : _root_.MIPStarRE.QPBT.DirectLdParams) := D.model.K

/-- The first coordinate, available because directly indexed dimensions are
positive. -/
def DirectLdParams.firstIndex (D : _root_.MIPStarRE.QPBT.DirectLdParams) : Fin D.m :=
  ⟨0, lt_of_lt_of_le Nat.zero_lt_one D.hm⟩



/-- The direct game used at the extended dimension of the combining map.  Its
field, degree, and simultaneity parameters are inherited from `P`, while its
dimension is `2 * P.m + 2`; no divisibility assertion is introduced.

The construction has dimension `2 * P.m + 2` without requiring
`2 * P.m + 2 ∣ P.q`; it supplies the directly indexed line and coordinate
spaces used in the dimension-extension argument of blueprint `lem:qld-sublines`.
-/
@[reducible] def AdmissibleParams.extendedDirectLd (P : _root_.MIPStarRE.QPBT.AdmissibleParams) : _root_.MIPStarRE.QPBT.DirectLdParams where
  q := P.q
  m := 2 * P.m + 2
  d := P.d
  k := 1
  hm := by omega
  hd := P.hd
  hk := by decide
  hq := P.hq

/-- A common random sample for the directly indexed question distribution.
The point, coordinate index, and unrestricted direction are mutually uniform. -/
structure DirectLdSpace (D : _root_.MIPStarRE.QPBT.DirectLdParams) where
  point : Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D
  index : Fin D.m
  direction : Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D
  deriving DecidableEq, Fintype

instance instNonemptyDirectLdSpace (D : _root_.MIPStarRE.QPBT.DirectLdParams) : Nonempty (_root_.MIPStarRE.QPBT.DirectLdSpace D) :=
  ⟨⟨0, D.firstIndex, 0⟩⟩

/-- Decompose a direct sample into its point and the remaining independent
coordinates. -/
def directLdSpacePointEquiv (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    _root_.MIPStarRE.QPBT.DirectLdSpace D ≃
      (Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) ×
        (Fin D.m × (Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D)) where
  toFun sample := (sample.point, sample.index, sample.direction)
  invFun sample := ⟨sample.1, sample.2.1, sample.2.2⟩
  left_inv sample := by cases sample; rfl
  right_inv sample := by cases sample; rfl

/-- Decompose a direct sample into its stored index and the remaining
independent coordinates. -/
def directLdSpaceIndexEquiv (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    _root_.MIPStarRE.QPBT.DirectLdSpace D ≃
      Fin D.m ×
        ((Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) ×
          (Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D)) where
  toFun sample := (sample.index, sample.point, sample.direction)
  invFun sample := ⟨sample.2.1, sample.1, sample.2.2⟩
  left_inv sample := by cases sample; rfl
  right_inv sample := by cases sample; rfl



/-- Zero the coordinates preceding the directly sampled prefix index. -/
def directPrefixProjection {D : _root_.MIPStarRE.QPBT.DirectLdParams} (i : Fin D.m)
    (v : Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) : Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D :=
  fun j => if j.val < i.val then 0 else v j



/-- Canonical line descriptions whose coordinate index is stored directly.
Coordinates are numbered from zero, so `index = i` represents coordinate
`i + 1` in the paper. -/
inductive DirectLineDesc (D : _root_.MIPStarRE.QPBT.DirectLdParams) where
  | axis (base : Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) (index : Fin D.m)
      (baseFixed : _root_.MIPStarRE.QPBT.lineRepMap (_root_.MIPStarRE.QPBT.coordinateDirection index) base = base)
  | diagonal (base : Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) (index : Fin D.m)
      (direction : Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D)
      (baseFixed : _root_.MIPStarRE.QPBT.lineRepMap direction base = base)
      (prefixZero : ∀ j : Fin D.m, j.val < index.val → direction j = 0)
  deriving DecidableEq

/-! ## Finite direct-line carrier -/

/-- A finite code for directly indexed lines, omitting only proof fields. -/
abbrev DirectLineDescCode (D : _root_.MIPStarRE.QPBT.DirectLdParams) :=
  ((Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) × Fin D.m) ⊕
    ((Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) × Fin D.m ×
      (Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D))

/-- Encode a directly indexed line by its tag and mathematical data. -/
def directLineDescCode (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    _root_.MIPStarRE.QPBT.DirectLineDesc D → _root_.MIPStarRE.QPBT.DirectLineDescCode D
  | .axis base index _ => .inl (base, index)
  | .diagonal base index direction _ _ => .inr (base, index, direction)

/-- The direct-line code is injective by proof irrelevance. -/
private theorem directLineDescCode_injective (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    Function.Injective (_root_.MIPStarRE.QPBT.directLineDescCode D) := by
  intro line line' h
  cases line with
  | axis base index baseFixed =>
      cases line' with
      | axis base' index' baseFixed' =>
          simp only [_root_.MIPStarRE.QPBT.directLineDescCode, Sum.inl.injEq, Prod.mk.injEq] at h
          rcases h with ⟨rfl, rfl⟩
          rfl
      | diagonal => simp [_root_.MIPStarRE.QPBT.directLineDescCode] at h
  | diagonal base index direction baseFixed prefixZero =>
      cases line' with
      | axis => simp [_root_.MIPStarRE.QPBT.directLineDescCode] at h
      | diagonal base' index' direction' baseFixed' prefixZero' =>
          simp only [_root_.MIPStarRE.QPBT.directLineDescCode, Sum.inr.injEq, Prod.mk.injEq] at h
          rcases h with ⟨rfl, rfl, rfl⟩
          rfl

/-- Directly indexed line descriptions form a finite type. -/
noncomputable instance directLineDescFintype (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    Fintype (_root_.MIPStarRE.QPBT.DirectLineDesc D) :=
  Fintype.ofInjective (_root_.MIPStarRE.QPBT.directLineDescCode D) (by
    exact directLineDescCode_injective D)

/-- The kind of a directly indexed line. -/
def DirectLineDesc.kind {D : _root_.MIPStarRE.QPBT.DirectLdParams} : _root_.MIPStarRE.QPBT.DirectLineDesc D → _root_.MIPStarRE.QPBT.LineKind
  | .axis _ _ _ => .axis
  | .diagonal _ _ _ _ _ => .diagonal

/-- The coordinate index stored in a directly indexed line. -/
def DirectLineDesc.index {D : _root_.MIPStarRE.QPBT.DirectLdParams} : _root_.MIPStarRE.QPBT.DirectLineDesc D → Fin D.m
  | .axis _ index _ => index
  | .diagonal _ index _ _ _ => index

/-- The canonical base point of a directly indexed line. -/
def DirectLineDesc.base {D : _root_.MIPStarRE.QPBT.DirectLdParams} :
    _root_.MIPStarRE.QPBT.DirectLineDesc D → Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D
  | .axis base _ _ => base
  | .diagonal base _ _ _ _ => base

/-- The geometric direction of a directly indexed line. -/
def DirectLineDesc.direction {D : _root_.MIPStarRE.QPBT.DirectLdParams} (line : _root_.MIPStarRE.QPBT.DirectLineDesc D) :
    Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D :=
  match line with
  | .axis _ index _ => _root_.MIPStarRE.QPBT.coordinateDirection index
  | .diagonal _ _ direction _ _ => direction





/-- The point set represented by a directly indexed line. -/
noncomputable def DirectLineDesc.pointSet {D : _root_.MIPStarRE.QPBT.DirectLdParams}
    (line : _root_.MIPStarRE.QPBT.DirectLineDesc D) : Set (Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) :=
  _root_.MIPStarRE.QPBT.linePoints line.base line.direction

/-- Turn a direct sample into its canonical axis-line description. -/
noncomputable def directALineDescOf (D : _root_.MIPStarRE.QPBT.DirectLdParams)
    (sample : _root_.MIPStarRE.QPBT.DirectLdSpace D) : _root_.MIPStarRE.QPBT.DirectLineDesc D :=
  let direction := _root_.MIPStarRE.QPBT.coordinateDirection sample.index
  let base := _root_.MIPStarRE.QPBT.lineRepMap direction sample.point
  .axis base sample.index (_root_.MIPStarRE.QPBT.lineRepMap_apply_self direction sample.point)

/-- Turn a direct sample into its canonical diagonal-line description. -/
noncomputable def directDLineDescOf (D : _root_.MIPStarRE.QPBT.DirectLdParams)
    (sample : _root_.MIPStarRE.QPBT.DirectLdSpace D) : _root_.MIPStarRE.QPBT.DirectLineDesc D :=
  let direction := _root_.MIPStarRE.QPBT.directPrefixProjection sample.index sample.direction
  let base := _root_.MIPStarRE.QPBT.lineRepMap direction sample.point
  .diagonal base sample.index direction
    (_root_.MIPStarRE.QPBT.lineRepMap_apply_self direction sample.point) (by
      intro j hj
      change _root_.MIPStarRE.QPBT.directPrefixProjection sample.index sample.direction j = 0
      rw [_root_.MIPStarRE.QPBT.directPrefixProjection, if_pos hj])

/-- The axis-line/point law with a directly sampled coordinate index. -/
noncomputable def directALinePointDist (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    _root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.DirectLineDesc D × (Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D)) :=
  (_root_.LIDT.MIPStarRE.LDT.uniformDistribution (_root_.MIPStarRE.QPBT.DirectLdSpace D)).map fun sample =>
    (_root_.MIPStarRE.QPBT.directALineDescOf D sample, sample.point)

/-- The diagonal-line/point law with a directly sampled prefix index. -/
noncomputable def directDLinePointDist (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    _root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.DirectLineDesc D × (Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D)) :=
  (_root_.LIDT.MIPStarRE.LDT.uniformDistribution (_root_.MIPStarRE.QPBT.DirectLdSpace D)).map fun sample =>
    (_root_.MIPStarRE.QPBT.directDLineDescOf D sample, sample.point)

/-- The equal mixture of the directly indexed axis and diagonal line-point
laws.  This is the replacement for the otherwise undefined extended-dimension
instance used at paper
`references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:1020-1116`. -/
noncomputable def directLinePointDist (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    _root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.DirectLineDesc D × (Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D)) :=
  _root_.MIPStarRE.QPBT.Distribution.mix (1 / 2) (by norm_num) (by norm_num)
    (_root_.MIPStarRE.QPBT.directALinePointDist D) (_root_.MIPStarRE.QPBT.directDLinePointDist D)

















end

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

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