Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Games / CondLinearTheorems

Definition
QPBT_QPBT_Games_CondLinearTheorems

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

qpbt

This bundle defines prefix decomposition data for conditionally linear functions. It supplies strict-prefix marginals, coordinate restriction maps, zero-linear-contribution lifts, and the first contribution added to residual data.

Principal definitions:

  • MIPStarRE.QPBT.clPrefix: defines the strict-prefix marginal value.
  • MIPStarRE.QPBT.CLData: stores prefix-indexed decomposition data.
  • The conditional-linear raising operation adds a level with zero contribution.
  • MIPStarRE.QPBT.coordinateRestrictionLinear: defines coordinate restriction linearly.
  • MIPStarRE.QPBT.CLDataOn: refines decomposition data on a register.
  • MIPStarRE.QPBT.clDataFirst: defines the first linear contribution.
  • MIPStarRE.QPBT.clDataConsMarginal: adds that contribution to residual marginals.

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/Games/CondLinearTheorems.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_Games_CondLinear

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

/-! # Structure and direct sums of conditionally linear functions

A conditionally linear map admits a prefix decomposition. Equal-level
representations on pairwise disjoint registers combine coordinatewise, and the
corresponding shared-seed distributions factor as products. A representation
may first be raised to a larger level by adjoining zero linear contributions.

## References

The source results are blueprint `lem:cl-kth`, `lem:cl-func-prod`, and
`lem:cl-dist-prod`, with paper origin
`references/qpbt-paper/05_conditionally_linear_functions.tex:150-379`.
-/

@[expose] public section

open scoped BigOperators

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.LDT

/-- Raise a representation of a conditionally linear function by one level,
whose linear contribution is zero. -/
private def CondLinearTerm.raiseLevel {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {ell : ℕ}
    (t : _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell) : _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) (ell + 1) :=
  .succ ∅ 0 (by simp) (fun _ => t)

@[simp]
private theorem CondLinearTerm.eval_raiseLevel {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {ell : ℕ}
    (t : _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell) (x : ι → K) :
    _root_.MIPStarRE.QPBT.CondLinearTerm.eval t.raiseLevel x = _root_.MIPStarRE.QPBT.CondLinearTerm.eval t x := by
  simp [CondLinearTerm.raiseLevel, _root_.MIPStarRE.QPBT.CondLinearTerm.eval]



/-- Raise a representation of a conditionally linear function by a specified
number of levels, each with zero linear contribution. -/
private def CondLinearTerm.raiseBy {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] :
    (d : ℕ) → {ell : ℕ} → _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell →
      _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) (ell + d)
  | 0, _, t => t
  | d + 1, _, t => (raiseBy d t).raiseLevel

@[simp]
private theorem CondLinearTerm.eval_raiseBy {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] (d : ℕ) {ell : ℕ}
    (t : _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell) (x : ι → K) :
    _root_.MIPStarRE.QPBT.CondLinearTerm.eval (CondLinearTerm.raiseBy d t) x = _root_.MIPStarRE.QPBT.CondLinearTerm.eval t x := by
  induction d with
  | zero => rfl
  | succ d ih => simp [CondLinearTerm.raiseBy, ih]













private theorem coordinateRestriction_add {K ι : Type*} [Field K]
    [DecidableEq ι] (S : Finset ι) (x y : ι → K) :
    _root_.MIPStarRE.QPBT.coordinateRestriction S (x + y) =
      _root_.MIPStarRE.QPBT.coordinateRestriction S x + _root_.MIPStarRE.QPBT.coordinateRestriction S y := by
  ext a
  by_cases ha : a ∈ S <;> simp [_root_.MIPStarRE.QPBT.coordinateRestriction, ha]



/-- Coordinate restriction as a linear endomorphism. -/
private def coordinateRestrictionLinear {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] (S : Finset ι) :
    (ι → K) →ₗ[K] (ι → K) where
  toFun := _root_.MIPStarRE.QPBT.coordinateRestriction S
  map_add' := coordinateRestriction_add S
  map_smul' c x := by
    ext a
    by_cases ha : a ∈ S <;> simp [_root_.MIPStarRE.QPBT.coordinateRestriction, ha]





/-- The value of the strict-prefix marginal preceding `k`. This is a
formalization-only auxiliary for blueprint
`lem:cl-kth`, paper
`references/qpbt-paper/05_conditionally_linear_functions.tex:150-178`. -/
def clPrefix {K ι : Type*} [Zero K] {ell : ℕ}
    (marginal : Fin ell → (ι → K) → (ι → K)) (k : Fin ell)
    (x : ι → K) : ι → K :=
  if _hk : k.val = 0 then 0
  else marginal ⟨k.val - 1, lt_of_le_of_lt (Nat.sub_le _ _) k.isLt⟩ x

/-- Prefix-indexed decomposition data from `lem:cl-kth`. Factor spaces are
represented by their coordinate sets, matching the register-subspace encoding
used by `IsCondLinearOn`. Blueprint `lem:cl-kth`, paper
`references/qpbt-paper/05_conditionally_linear_functions.tex:150-178`. -/
structure CLData (K ι : Type*) [Field K] [Fintype ι] [DecidableEq ι]
    (ell : ℕ) (L : (ι → K) → (ι → K)) where
  /-- The marginal `L_{≤k}`. -/
  marginal : Fin ell → (ι → K) → (ι → K)
  /-- The factor register selected by a prefix value. -/
  factor : Fin ell → (ι → K) → Finset ι
  /-- The linear map selected by a prefix value. -/
  linear : Fin ell → (ι → K) → ((ι → K) →ₗ[K] (ι → K))
  /-- Each marginal has the corresponding conditionally linear level. -/
  marginal_cl : ∀ k, _root_.MIPStarRE.QPBT.IsCondLinearOn K Finset.univ (k.val + 1) (marginal k)
  /-- The selected factor registers are pairwise disjoint. -/
  factor_disjoint : ∀ x i j, i ≠ j →
    Disjoint (factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)) (factor j (_root_.MIPStarRE.QPBT.clPrefix marginal j x))
  /-- The selected factor registers cover all coordinates. -/
  factor_cover : ∀ x a, ∃ i, a ∈ factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)
  /-- Each selected linear map is supported on its factor register. -/
  linear_supported : ∀ k u x a, a ∉ factor k u → linear k u x a = 0
  /-- Each marginal is the sum of the preceding selected linear pieces. -/
  sum_formula : ∀ k x, marginal k x =
    ∑ i : Fin ell, if i.val ≤ k.val then
      linear i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)
        (_root_.MIPStarRE.QPBT.coordinateRestriction (factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)) x) else 0
  /-- The final marginal is the original function. -/
  top : ∀ h : 0 < ell,
    marginal ⟨ell - 1, Nat.sub_lt h (by decide)⟩ = L

/-- Prefix decomposition data on a register `S`, refining the decomposition
in `lem:cl-kth`. -/
private structure CLDataOn (K ι : Type*) [Field K] [Fintype ι]
    [DecidableEq ι] (S : Finset ι) (ell : ℕ)
    (L : (ι → K) → (ι → K)) where
  marginal : Fin ell → (ι → K) → (ι → K)
  factor : Fin ell → (ι → K) → Finset ι
  linear : Fin ell → (ι → K) → ((ι → K) →ₗ[K] (ι → K))
  marginal_cl : ∀ k, _root_.MIPStarRE.QPBT.IsCondLinearOn K S (k.val + 1) (marginal k)
  factor_subset : ∀ k u, factor k u ⊆ S
  factor_disjoint : ∀ x i j, i ≠ j →
    Disjoint (factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x))
      (factor j (_root_.MIPStarRE.QPBT.clPrefix marginal j x))
  factor_cover : ∀ x a, a ∈ S → ∃ i, a ∈ factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)
  linear_supported : ∀ k u x a, a ∉ factor k u → linear k u x a = 0
  sum_formula : ∀ k x, marginal k x =
    ∑ i : Fin ell, if i.val ≤ k.val then
      linear i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)
        (_root_.MIPStarRE.QPBT.coordinateRestriction (factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)) x) else 0
  top : ∀ h : 0 < ell,
    marginal ⟨ell - 1, Nat.sub_lt h (by decide)⟩ = L









/-- The first linear contribution in the inductive prefix decomposition. -/
private def clDataFirst {K ι : Type*} [Field K] [Fintype ι] [DecidableEq ι]
    (S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
    (x : ι → K) : ι → K :=
  L₁ (_root_.MIPStarRE.QPBT.coordinateRestriction S₁ x)

/-- Add the first contribution to each marginal of residual decomposition
data. -/
private def clDataConsMarginal {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
    {R : (ι → K) → (ι → K) → (ι → K)}
    (S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
    (d : ∀ y, CLDataOn K ι T ell (R y)) :
    Fin (ell + 1) → (ι → K) → (ι → K) :=
  Fin.cases (clDataFirst S₁ L₁) fun k x =>
    clDataFirst S₁ L₁ x + (d (clDataFirst S₁ L₁ x)).marginal k x

/-- Select the first or residual factor register from a combined prefix. -/
private def clDataConsFactor {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
    {R : (ι → K) → (ι → K) → (ι → K)}
    (S₁ : Finset ι) (d : ∀ y, CLDataOn K ι T ell (R y)) :
    Fin (ell + 1) → (ι → K) → Finset ι :=
  Fin.cases (fun _ => S₁) fun k u =>
    (d (_root_.MIPStarRE.QPBT.coordinateRestriction S₁ u)).factor k (_root_.MIPStarRE.QPBT.coordinateRestriction T u)

/-- Select the first or residual linear map from a combined prefix. -/
private def clDataConsLinear {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
    {R : (ι → K) → (ι → K) → (ι → K)}
    (S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
    (d : ∀ y, CLDataOn K ι T ell (R y)) :
    Fin (ell + 1) → (ι → K) → ((ι → K) →ₗ[K] (ι → K)) :=
  Fin.cases (fun _ => L₁.comp (coordinateRestrictionLinear S₁)) fun k u =>
    (d (_root_.MIPStarRE.QPBT.coordinateRestriction S₁ u)).linear k (_root_.MIPStarRE.QPBT.coordinateRestriction T u)

@[simp]
private theorem clDataConsMarginal_zero {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
    {R : (ι → K) → (ι → K) → (ι → K)}
    (S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
    (d : ∀ y, CLDataOn K ι T ell (R y)) (x : ι → K) :
    clDataConsMarginal S₁ L₁ d 0 x = clDataFirst S₁ L₁ x := rfl

@[simp]
private theorem clDataConsMarginal_succ {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
    {R : (ι → K) → (ι → K) → (ι → K)}
    (S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
    (d : ∀ y, CLDataOn K ι T ell (R y)) (k : Fin ell) (x : ι → K) :
    clDataConsMarginal S₁ L₁ d k.succ x =
      clDataFirst S₁ L₁ x +
        (d (clDataFirst S₁ L₁ x)).marginal k x := rfl



@[simp]
private theorem clDataConsFactor_zero {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
    {R : (ι → K) → (ι → K) → (ι → K)}
    (S₁ : Finset ι) (d : ∀ y, CLDataOn K ι T ell (R y)) (u : ι → K) :
    clDataConsFactor S₁ d 0 u = S₁ := rfl

@[simp]
private theorem clDataConsFactor_succ {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
    {R : (ι → K) → (ι → K) → (ι → K)}
    (S₁ : Finset ι) (d : ∀ y, CLDataOn K ι T ell (R y))
    (k : Fin ell) (u : ι → K) :
    clDataConsFactor S₁ d k.succ u =
      (d (_root_.MIPStarRE.QPBT.coordinateRestriction S₁ u)).factor k (_root_.MIPStarRE.QPBT.coordinateRestriction T u) := rfl

@[simp]
private theorem clDataConsLinear_zero {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
    {R : (ι → K) → (ι → K) → (ι → K)}
    (S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
    (d : ∀ y, CLDataOn K ι T ell (R y)) (u : ι → K) :
    clDataConsLinear S₁ L₁ d 0 u =
      L₁.comp (coordinateRestrictionLinear S₁) := rfl

@[simp]
private theorem clDataConsLinear_succ {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
    {R : (ι → K) → (ι → K) → (ι → K)}
    (S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
    (d : ∀ y, CLDataOn K ι T ell (R y)) (k : Fin ell) (u : ι → K) :
    clDataConsLinear S₁ L₁ d k.succ u =
      (d (_root_.MIPStarRE.QPBT.coordinateRestriction S₁ u)).linear k (_root_.MIPStarRE.QPBT.coordinateRestriction T u) := rfl





































end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Games/CondLinearTheorems.lean#L29-L447

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