Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Observables / LineDefs

Definition
QPBT_QPBT_Observables_LineDefs

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

qpbt

This bundle gives the data structures for canonical axis and diagonal lines used by the low-degree question sampler. A line description stores its presentation kind, seed, base, direction, and represented point set, together with bounded-degree coefficient-list polynomials.

Principal definitions:

  • MIPStarRE.QPBT.LineKind: the axis and diagonal presentations of a line.
  • MIPStarRE.QPBT.LineDesc: a seed-bearing canonical line description.
  • MIPStarRE.QPBT.LineDesc.seed: the seed stored by a line description.
  • MIPStarRE.QPBT.LineDesc.base: the canonical base point stored by a line description.
  • MIPStarRE.QPBT.LineDesc.direction: the geometric direction represented by a line description.
  • MIPStarRE.QPBT.DegPoly: a coefficient-list bounded-degree polynomial representation.

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/Observables/LineDefs.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_Coefficients
import Definitions.Def_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Algebra_Lines
import Definitions.Def_QPBT_QPBT_Algebra_Subspaces
import Definitions.Def_QPBT_QPBT_Games_CondLinear
import Definitions.Def_QPBT_QPBT_Games_DistributionAux
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGame
import Mathlib
import Theorems.Thm_LIDT_MIPStarRE_LDT_Distribution_IsProbability_map

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

/-!
# Lines, bounded line polynomials, and line-point distributions

This file provides the seed-bearing line descriptions and coefficient-list
polynomials shared by the observable and combining chapters. It also realizes
the line-point distribution directly from the conditionally linear sampler.
Over a finite coefficient field, bounded individual-degree multivariate
polynomials form a finite outcome set for the associated measurements.

## References

The line and bounded-polynomial definitions are blueprint
`def:ideg-deg-polynomials`, with source origin
`references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:51-58`. The
line-point sampler is `def:line-point-dist` in blueprint chapter 13, from
`08_classical_and_quantum_low_degree_tests.tex:274-287`.
-/

@[expose] public section

open scoped BigOperators

namespace MIPStarRE.QPBT

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

noncomputable section

/-- A formalization-only identity used to construct canonical line
descriptions: applying the canonical line-representative projection twice has
the same effect as applying it once. -/
theorem lineRepMap_apply_self {K : Type*} [Field K] {m : ℕ}
    (v u : Fin m → K) :
    _root_.MIPStarRE.QPBT.lineRepMap v (_root_.MIPStarRE.QPBT.lineRepMap v u) = _root_.MIPStarRE.QPBT.lineRepMap v u := by
  simp [_root_.MIPStarRE.QPBT.lineRepMap, _root_.MIPStarRE.QPBT.canonicalProjOfKernel, LinearMap.comp_apply]

/-- The two presentations of lines used by the low-degree question sampler. -/
inductive LineKind where
  | axis
  | diagonal
  deriving DecidableEq

instance LineKind.instFintype : Fintype _root_.MIPStarRE.QPBT.LineKind :=
  ⟨{.axis, .diagonal}, by intro x; cases x <;> simp⟩

/-- A seed-bearing line description for blueprint
`def:line-point-dist`, paper
`08_classical_and_quantum_low_degree_tests.tex:143-174,243-287`.

An axis description stores its canonical base and seed. A diagonal description
stores only the projected direction, together with its prefix-zero invariant.
Both cases carry the assertion that their base is fixed by the
appropriate `lineRepMap`. Coordinates are numbered from zero; coordinate `j`
corresponds to the paper's coordinate `j + 1`. -/
inductive LineDesc (L : _root_.MIPStarRE.QPBT.LdParams) where
  | axis (base : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) (seed : _root_.MIPStarRE.QPBT.ScalarQ L)
      (baseFixed : _root_.MIPStarRE.QPBT.lineRepMap (_root_.MIPStarRE.QPBT.coordinateDirection (_root_.MIPStarRE.QPBT.chiIndex L seed)) base = base)
  | diagonal (base : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) (seed : _root_.MIPStarRE.QPBT.ScalarQ L)
      (direction : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)
      (baseFixed : _root_.MIPStarRE.QPBT.lineRepMap direction base = base)
      (prefixZero : ∀ j : Fin L.m, j.val < (_root_.MIPStarRE.QPBT.chiIndex L seed).val → direction j = 0)
  deriving DecidableEq

/-- The tag of a canonical line description. -/
def LineDesc.kind {L : _root_.MIPStarRE.QPBT.LdParams} : _root_.MIPStarRE.QPBT.LineDesc L → _root_.MIPStarRE.QPBT.LineKind
  | .axis _ _ _ => .axis
  | .diagonal _ _ _ _ _ => .diagonal

/-- The seed retained by a canonical line description. -/
def LineDesc.seed {L : _root_.MIPStarRE.QPBT.LdParams} : _root_.MIPStarRE.QPBT.LineDesc L → _root_.MIPStarRE.QPBT.ScalarQ L
  | .axis _ seed _ => seed
  | .diagonal _ seed _ _ _ => seed

/-- The canonical base stored by a line description. -/
def LineDesc.base {L : _root_.MIPStarRE.QPBT.LdParams} : _root_.MIPStarRE.QPBT.LineDesc L → Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L
  | .axis base _ _ => base
  | .diagonal base _ _ _ _ => base

/-- The geometric direction represented by a canonical line description.
Diagonal descriptions already store the projected data, so this map does
not apply a second projection. -/
def LineDesc.direction {L : _root_.MIPStarRE.QPBT.LdParams} (line : _root_.MIPStarRE.QPBT.LineDesc L) :
    Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L :=
  match line with
  | .axis _ seed _ => _root_.MIPStarRE.QPBT.coordinateDirection (_root_.MIPStarRE.QPBT.chiIndex L seed)
  | .diagonal _ _ direction _ _ => direction





/-- The point set represented by a seed-bearing line description. -/
noncomputable def LineDesc.pointSet {L : _root_.MIPStarRE.QPBT.LdParams} (line : _root_.MIPStarRE.QPBT.LineDesc L) :
    Set (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) :=
  _root_.MIPStarRE.QPBT.linePoints line.base line.direction



/-- Coefficient-list representation of a univariate polynomial of degree at
most `c` over the scalar field of `L`. -/
abbrev DegPoly (L : _root_.MIPStarRE.QPBT.LdParams) (c : ℕ) := Fin (c + 1) → _root_.MIPStarRE.QPBT.ScalarQ L

/-- Extend a coefficient list by zero from degree bound `c` to `c'`. -/
def DegPoly.padTo {L : _root_.MIPStarRE.QPBT.LdParams} {c c' : ℕ} (_h : c ≤ c')
    (f : _root_.MIPStarRE.QPBT.DegPoly L c) : _root_.MIPStarRE.QPBT.DegPoly L c' :=
  fun i =>
    if hi : i.val < c + 1 then f ⟨i.val, hi⟩ else 0

/-- A line polynomial evaluates to `a` at `u` when `u` has a line parameter
and every such parameter gives the same value.  The universal clause handles
the zero-direction presentation without choosing a sentinel parameter. -/
def EvaluatesTo {L : _root_.MIPStarRE.QPBT.LdParams} {c : ℕ} (line : _root_.MIPStarRE.QPBT.LineDesc L)
    (f : _root_.MIPStarRE.QPBT.DegPoly L c) (u : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) (a : _root_.MIPStarRE.QPBT.ScalarQ L) : Prop :=
  (∃ t : _root_.MIPStarRE.QPBT.ScalarQ L, u = line.base + t • line.direction) ∧
    ∀ t : _root_.MIPStarRE.QPBT.ScalarQ L, u = line.base + t • line.direction → _root_.MIPStarRE.QPBT.evalCoefficient f t = a

/-- Partially evaluate a line polynomial at a point. The value is undefined
when the point does not determine an evaluation. This formalization-only
completion is used in blueprint chapter 14; the displayed family at paper
`14_analysis_of_the_pauli_basis_test.tex:197-206` has no bottom outcome. -/
noncomputable def evalOpt {L : _root_.MIPStarRE.QPBT.LdParams} {c : ℕ} (line : _root_.MIPStarRE.QPBT.LineDesc L)
    (u : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) (f : _root_.MIPStarRE.QPBT.DegPoly L c) : Option (_root_.MIPStarRE.QPBT.ScalarQ L) := by
  classical
  exact if h : ∃ a : _root_.MIPStarRE.QPBT.ScalarQ L, _root_.MIPStarRE.QPBT.EvaluatesTo line f u a then
    some (Classical.choose h)
  else none

/-- Convert an axis-line CL output to its seed-bearing presentation; paper
`08_classical_and_quantum_low_degree_tests.tex:243-257,276-287`. -/
def aLineDescOf (L : _root_.MIPStarRE.QPBT.LdParams) (line : _root_.MIPStarRE.QPBT.LdSpace L) : _root_.MIPStarRE.QPBT.LineDesc L :=
  let direction := _root_.MIPStarRE.QPBT.coordinateDirection (_root_.MIPStarRE.QPBT.chiIndex L line.seed)
  let base := _root_.MIPStarRE.QPBT.lineRepMap direction line.point
  _root_.MIPStarRE.QPBT.LineDesc.axis base line.seed (_root_.MIPStarRE.QPBT.lineRepMap_apply_self direction line.point)

/-- Convert a diagonal-line CL output to its seed-bearing presentation; paper
`08_classical_and_quantum_low_degree_tests.tex:261-287`. -/
def dLineDescOf (L : _root_.MIPStarRE.QPBT.LdParams) (line : _root_.MIPStarRE.QPBT.LdSpace L) : _root_.MIPStarRE.QPBT.LineDesc L :=
  let direction := _root_.MIPStarRE.QPBT.prefixProjection (_root_.MIPStarRE.QPBT.chiIndex L line.seed) line.direction
  let base := _root_.MIPStarRE.QPBT.lineRepMap direction line.point
  _root_.MIPStarRE.QPBT.LineDesc.diagonal base line.seed direction
    (_root_.MIPStarRE.QPBT.lineRepMap_apply_self direction line.point) (by
      intro j hj
      change _root_.MIPStarRE.QPBT.prefixProjection (_root_.MIPStarRE.QPBT.chiIndex L line.seed) line.direction j = 0
      rw [_root_.MIPStarRE.QPBT.prefixProjection, if_pos hj])

/-- The axis-line/point component of the low-degree line-point sampler; paper
`08_classical_and_quantum_low_degree_tests.tex:243-257,274-287`. -/
noncomputable def aLinePointDist (L : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.LineDesc L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)) :=
  (_root_.MIPStarRE.QPBT.clDistribution (_root_.MIPStarRE.QPBT.ldALineCL L) (_root_.MIPStarRE.QPBT.ldPointCL L)).map fun sample =>
    (_root_.MIPStarRE.QPBT.aLineDescOf L sample.1, _root_.MIPStarRE.QPBT.LdSpace.point sample.2)

/-- The diagonal-line/point component of the low-degree line-point sampler; paper
`08_classical_and_quantum_low_degree_tests.tex:261-287`. -/
noncomputable def dLinePointDist (L : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.LineDesc L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)) :=
  (_root_.MIPStarRE.QPBT.clDistribution (_root_.MIPStarRE.QPBT.ldDLineCL L) (_root_.MIPStarRE.QPBT.ldPointCL L)).map fun sample =>
    (_root_.MIPStarRE.QPBT.dLineDescOf L sample.1, _root_.MIPStarRE.QPBT.LdSpace.point sample.2)

/-- The equal mixture of axis and diagonal line-point samples from
`def:line-point-dist`; paper
`08_classical_and_quantum_low_degree_tests.tex:274-287`. -/
noncomputable def linePointDist (L : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.LineDesc L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)) :=
  _root_.MIPStarRE.QPBT.Distribution.mix (1 / 2) (by norm_num) (by norm_num)
    (_root_.MIPStarRE.QPBT.aLinePointDist L) (_root_.MIPStarRE.QPBT.dLinePointDist L)

/-- The affine line-point component has total probability one. -/
theorem aLinePointDist_isProbability (L : _root_.MIPStarRE.QPBT.LdParams) :
    (_root_.MIPStarRE.QPBT.aLinePointDist L).IsProbability :=
  ((_root_.LIDT.MIPStarRE.LDT.uniformDistribution_isProbability _).map _).map _

/-- The diagonal line-point component has total probability one. -/
theorem dLinePointDist_isProbability (L : _root_.MIPStarRE.QPBT.LdParams) :
    (_root_.MIPStarRE.QPBT.dLinePointDist L).IsProbability :=
  ((_root_.LIDT.MIPStarRE.LDT.uniformDistribution_isProbability _).map _).map _

/-- The line-point mixture has total probability one. -/
theorem linePointDist_isProbability (L : _root_.MIPStarRE.QPBT.LdParams) :
    (_root_.MIPStarRE.QPBT.linePointDist L).IsProbability := by
  exact _root_.MIPStarRE.QPBT.Distribution.mix_isProbability _ _ _
    (_root_.MIPStarRE.QPBT.aLinePointDist_isProbability L) (_root_.MIPStarRE.QPBT.dLinePointDist_isProbability L)
    (by norm_num) (by norm_num)

end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Observables/LineDefs.lean#L36-L207

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