Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Algebra / Lines

Definition
QPBT_QPBT_Algebra_Lines

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

qpbt

This bundle sets up affine lines in a finite coordinate space and the canonical representative used to identify points on the same line. It also records the pivot-coordinate facts that make the representative explicit.

Principal definitions:

  • MIPStarRE.QPBT.linePoints: the affine line x+tvx + t vx+tv for t∈Kt \in Kt∈K through a point in direction vvv, including the singleton case v=0v=0v=0.
  • MIPStarRE.QPBT.coordinateDirection: the elementary coordinate direction used for axis-parallel lines.
  • MIPStarRE.QPBT.lineRepMap: the linear projection onto the canonical complement of the span of the line direction.
  • MIPStarRE.QPBT.linePivotIndex: the least coordinate at which a nonzero direction is nonzero.
  • MIPStarRE.QPBT.explicitLineRep: the point obtained by subtracting the unique multiple of a nonzero direction that makes its pivot coordinate vanish, with the zero-direction case returning the original point.
  • MIPStarRE.QPBT.linePivotIndex_ne_zero: the direction is nonzero at its pivot coordinate.
  • MIPStarRE.QPBT.linePivotIndex_zero_before: every coordinate before the pivot is zero.
  • MIPStarRE.QPBT.sub_lineRepMap_mem_span: a point differs from its canonical representative by an element of the direction span.

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/Algebra/Lines.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_RowEchelon
import Definitions.Def_QPBT_QPBT_Algebra_Subspaces
import Mathlib

namespace MIPStarRE.QPBT
end MIPStarRE.QPBT

/-!
# Lines and canonical representatives

The classical and Pauli question distributions use affine lines in a finite
coordinate space.  This module keeps the zero-direction case explicit and
provides the canonical projection used for line representatives.

## References

The source-facing nodes are blueprint `def:line`, `prop:line-equiv`, and
`def:line-representative`; the formalization support nodes are blueprint
`lem:line-rep-kernel` and `lem:line-rep-incidence`.
The paper origin is `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:102-174`.

Note: this module contributes declarations to the comparator statement closure
of the QPBT headline theorems, which must elaborate in the same environment as
the Mathlib-only `ChallengeQPBT.lean`.  Keep the full `import Mathlib`; do not
narrow it.  See `docs/comparator.md`, "Environment alignment".
-/

@[expose] public section

namespace MIPStarRE.QPBT

open scoped BigOperators

variable {K : Type*} [Field K]

/--
The affine line through `u` in direction `v`, including the singleton case
`v = 0`.  Blueprint `def:line`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:106-124`.
-/
def linePoints {m : ℕ}
    (u v : Fin m → K) : Set (Fin m → K) :=
  {x | ∃ t : K, x = u + t • v}

/-- The elementary coordinate direction used in the axis-parallel predicate of
blueprint `def:line`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:106-124`.
-/
def coordinateDirection {m : ℕ}
    (i : Fin m) : Fin m → K :=
  Pi.single i 1







/--
The canonical linear representative map of a line direction.  It projects onto
the coordinate complement of the span of `v`; for `v = 0` the span is bottom,
so the resulting map is the identity.  Blueprint `def:line-representative`;
paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:143-174`.
-/
noncomputable def lineRepMap {m : ℕ}
    (v : Fin m → K) : (Fin m → K) →ₗ[K] (Fin m → K) :=
  _root_.MIPStarRE.QPBT.canonicalProjOfKernel (Submodule.span K ({v} : Set (Fin m → K)))

/-- The least coordinate at which a nonzero line direction is nonzero. This is
Lean-only support for the elementary formula for the canonical representative;
coordinates use the same left-to-right order as paper `def:cl-canonical`. -/
noncomputable def linePivotIndex {m : ℕ} (v : Fin m → K) (hv : v ≠ 0) : Fin m := by
  classical
  let support := Finset.univ.filter fun j => v j ≠ 0
  have hsupport : support.Nonempty := by
    by_contra h
    apply hv
    funext j
    by_contra hj
    apply h
    refine ⟨j, ?_⟩
    simp only [support, Finset.mem_filter, Finset.mem_univ, true_and]
    simpa using hj
  exact support.min' hsupport

/-- The pivot coordinate of a nonzero direction is nonzero. -/
theorem linePivotIndex_ne_zero {m : ℕ} (v : Fin m → K) (hv : v ≠ 0) :
    v (_root_.MIPStarRE.QPBT.linePivotIndex v hv) ≠ 0 := by
  classical
  have hmem :
      _root_.MIPStarRE.QPBT.linePivotIndex v hv ∈ Finset.univ.filter fun j => v j ≠ 0 := by
    unfold _root_.MIPStarRE.QPBT.linePivotIndex
    exact Finset.min'_mem _ _
  exact (Finset.mem_filter.mp hmem).2

/-- Every coordinate before the pivot coordinate of a nonzero direction vanishes. -/
theorem linePivotIndex_zero_before {m : ℕ} (v : Fin m → K) (hv : v ≠ 0)
    (i : Fin m) (hi : i < _root_.MIPStarRE.QPBT.linePivotIndex v hv) : v i = 0 := by
  classical
  by_contra hvi
  unfold _root_.MIPStarRE.QPBT.linePivotIndex at hi
  exact (not_le_of_gt hi) (Finset.min'_le _ i (by simp [hvi]))

/--
The elementary canonical representative of the line through `u` in direction
`v`. The zero direction returns `u`. Otherwise it subtracts the unique multiple
of `v` that makes the least nonzero coordinate of `v` vanish. This Lean-only
formula is used to replace the general canonical-complement construction in the
compact Palomar statement while preserving paper `def:line-representative`.
-/
noncomputable def explicitLineRep {m : ℕ}
    (u v : Fin m → K) : Fin m → K :=
  open Classical in
    if hv : v = 0 then u
    else
      let j := _root_.MIPStarRE.QPBT.linePivotIndex v hv
      u - (u j / v j) • v

/- The point-valued companion to `lineRepMap`; Lean-only notation for the
canonical representative in `def:line-representative`. -/


/--
Formalization support node blueprint `lem:line-rep-kernel` for
`def:line-representative` (paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:143-174`).
The canonical representative map is a projection whose kernel is the line
`K v`, so a point and its canonical representative differ by a scalar multiple
of the direction.
-/
theorem sub_lineRepMap_mem_span {m : ℕ} (v u : Fin m → K) :
    u - _root_.MIPStarRE.QPBT.lineRepMap v u ∈ Submodule.span K ({v} : Set (Fin m → K)) := by
  have hc :
      IsCompl
        (_root_.MIPStarRE.QPBT.registerSubmodule K
          (_root_.MIPStarRE.QPBT.canonicalComplement (Submodule.span K ({v} : Set (Fin m → K)))))
        (Submodule.span K ({v} : Set (Fin m → K))) :=
    (_root_.MIPStarRE.QPBT.isCompl_registerSubmodule_canonicalComplement
      (Submodule.span K ({v} : Set (Fin m → K)))).symm
  have hrep : _root_.MIPStarRE.QPBT.lineRepMap v u =
      (_root_.MIPStarRE.QPBT.registerSubmodule K
        (_root_.MIPStarRE.QPBT.canonicalComplement (Submodule.span K ({v} : Set (Fin m → K))))).projection
        (Submodule.span K ({v} : Set (Fin m → K))) hc u := rfl
  rw [hrep, ← Submodule.projection_eq_self_sub_projection hc u]
  exact Submodule.projection_apply_mem hc.symm u

/--
The canonical line representative is exactly the elementary least-pivot
formula `explicitLineRep`, for every point and direction, including `v = 0`.
This is a Lean-only representation theorem for the compact Palomar statement;
it proves an exact identity and does not alter paper `def:line-representative`.
-/
theorem lineRepMap_apply_eq_explicitLineRep {m : ℕ} (v u : Fin m → K) :
    _root_.MIPStarRE.QPBT.lineRepMap v u = _root_.MIPStarRE.QPBT.explicitLineRep u v := by
  classical
  by_cases hv : v = 0
  · subst v
    have hspan : Submodule.span K ({0} : Set (Fin m → K)) = ⊥ := by simp
    have h := _root_.MIPStarRE.QPBT.sub_lineRepMap_mem_span (0 : Fin m → K) u
    rw [hspan, Submodule.mem_bot, sub_eq_zero] at h
    simpa [_root_.MIPStarRE.QPBT.explicitLineRep] using h.symm
  · let j := _root_.MIPStarRE.QPBT.linePivotIndex v hv
    have hjv : v j ≠ 0 := _root_.MIPStarRE.QPBT.linePivotIndex_ne_zero v hv
    let w : Fin m → K := (v j)⁻¹ • v
    let B : Matrix (Fin 1) (Fin m) K := Matrix.replicateRow (Fin 1) w
    let pivot : Fin 1 ↪o Fin m :=
      ({j} : Finset (Fin m)).orderEmbOfFin (Finset.card_singleton j)
    have hpivot (i : Fin 1) : pivot i = j := by
      simp [pivot]
    have hB : _root_.MIPStarRE.QPBT.IsReducedRowEchelon B pivot := by
      constructor
      · intro i k
        have hik : i = k := Subsingleton.elim _ _
        subst k
        simp [B, w, hpivot, hjv]
      · intro i k hki
        have hkj : k < j := by simpa [hpivot] using hki
        have hvk : v k = 0 := _root_.MIPStarRE.QPBT.linePivotIndex_zero_before v hv k hkj
        simp [B, w, hvk]
    have hrange : Set.range B.row = {w} := by
      ext x
      constructor
      · rintro ⟨i, rfl⟩
        funext k
        rfl
      · intro hx
        rw [Set.mem_singleton_iff] at hx
        subst x
        refine ⟨0, ?_⟩
        funext k
        rfl
    have hspan :
        Submodule.span K (Set.range B.row) =
          Submodule.span K ({v} : Set (Fin m → K)) := by
      rw [hrange, Submodule.span_singleton_eq_span_singleton]
      refine ⟨Units.mk0 (v j) hjv, ?_⟩
      funext k
      simp [w, hjv]
    have hcomplement :
        _root_.MIPStarRE.QPBT.canonicalComplement (Submodule.span K ({v} : Set (Fin m → K))) =
          ({j} : Finset (Fin m))ᶜ := by
      rw [← hspan, hB.canonicalComplement_eq_nonpivot_indices]
      simp [pivot]
    have hrep_mem :
        _root_.MIPStarRE.QPBT.lineRepMap v u ∈
          _root_.MIPStarRE.QPBT.registerSubmodule K
            (_root_.MIPStarRE.QPBT.canonicalComplement (Submodule.span K ({v} : Set (Fin m → K)))) := by
      simp [_root_.MIPStarRE.QPBT.lineRepMap, _root_.MIPStarRE.QPBT.canonicalProjOfKernel]
    rw [hcomplement, _root_.MIPStarRE.QPBT.registerSubmodule_eq_spanSubset] at hrep_mem
    have hrep_zero : _root_.MIPStarRE.QPBT.lineRepMap v u j = 0 :=
      Pi.mem_spanSubset_iff.mp hrep_mem j (by simp)
    obtain ⟨t, ht⟩ :=
      Submodule.mem_span_singleton.mp (_root_.MIPStarRE.QPBT.sub_lineRepMap_mem_span v u)
    have htj : t = u j / v j := by
      apply (eq_div_iff hjv).2
      have := congrFun ht j
      simpa [hrep_zero] using this
    have hrep : _root_.MIPStarRE.QPBT.lineRepMap v u = u - t • v := by
      rw [ht]
      abel
    rw [_root_.MIPStarRE.QPBT.explicitLineRep, dif_neg hv, hrep, htj]

/--
Formalization support node blueprint `lem:line-rep-incidence` for
`def:line-representative` (paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:166-174`).
Every point lies on the line through its own canonical representative in the
same direction; this is the incidence property used by the line-versus-point
samplers.
-/
theorem mem_linePoints_lineRepMap {m : ℕ} (v u : Fin m → K) :
    u ∈ _root_.MIPStarRE.QPBT.linePoints (_root_.MIPStarRE.QPBT.lineRepMap v u) v := by
  obtain ⟨t, ht⟩ := Submodule.mem_span_singleton.mp (_root_.MIPStarRE.QPBT.sub_lineRepMap_mem_span v u)
  exact ⟨t, by rw [ht]; abel⟩

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Algebra/Lines.lean#L35-L266

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