Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Games / CondLinear

Definition
QPBT_QPBT_Games_CondLinear

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

qpbt

This bundle defines conditionally linear maps and the graph and seed distributions generated from them. It includes coordinate restriction, evaluation and support invariants, the public conditionally-linear predicate, and the symmetric graph distribution with self-loops.

Principal definitions:

  • MIPStarRE.QPBT.CondLinearTerm: the recursive representation of a conditionally linear function.
  • MIPStarRE.QPBT.coordinateRestriction: restricts coordinates to a register and zeros the complement.
  • MIPStarRE.QPBT.IsCondLinearOn: the conditionally-linear predicate.
  • MIPStarRE.QPBT.clDistribution: the distribution from two conditionally linear maps on a common seed.
  • MIPStarRE.QPBT.graphDistribution: the uniform distribution on ordered graph pairs.
  • MIPStarRE.QPBT.graphDistribution_symm: symmetry of the graph distribution.

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/CondLinear.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

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

/-!
# Conditionally linear functions and graph distributions

The question distributions in the Pauli basis test are generated by a finite
graph of types and a shared seed, with each type applying a conditionally linear
map to that seed.  A conditionally linear map of level `ell` is a sum of `ell`
linear contributions on pairwise disjoint register subspaces, each contribution
selected by the values of the preceding ones.  The inductive predicate records
this decomposition, and the graph distribution is the law of the type pair.
Equal-level maps over pairwise disjoint coordinate registers have coordinatewise
direct sums whose shared-seed laws factor as products.

## References

The source-facing nodes are blueprint `def:cl-func`, `def:cl-dist`,
`lem:cl-concat`, and `def:graph-distribution`.
The paper origins are
`references/qpbt-paper/05_conditionally_linear_functions.tex:35-57,282-314`,
`references/qpbt-paper/07_types.tex:65-82`,
and `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1010`.
-/

@[expose] public section

open scoped BigOperators

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.LDT

variable {K ι : Type*} [Field K] [Fintype ι] [DecidableEq ι]

/--
The source definition is recursive in the residual map.  A direct inductive
predicate with that recursive occurrence under a dependent finite-set index is
rejected by Lean's strict-positivity checker.  We therefore expose the same
public predicate through a positive syntax tree (`CondLinearTerm`), together
with its support invariant and evaluation function.  This is a representation
deviation forced by Lean, not an additional mathematical hypothesis.  It encodes
blueprint `def:cl-func`,
paper origin `references/qpbt-paper/05_conditionally_linear_functions.tex:35-57`.
-/
inductive CondLinearTerm (K : Type*) [Field K] {ι : Type*} [Fintype ι]
    [DecidableEq ι] : ℕ → Type _ where
  | zero : CondLinearTerm K (ι := ι) 0
  | succ {ell : ℕ}
      (S₁ : Finset ι)
      (L₁ : (ι → K) →ₗ[K] (ι → K))
      (hSupport : ∀ x i, i ∉ S₁ → L₁ x i = 0)
      (rest : (ι → K) → CondLinearTerm K (ι := ι) ell) :
      CondLinearTerm K (ι := ι) (ell + 1)

/-- Restrict a coordinate vector to a register, zeroing the complementary
coordinates.  This is Lean-only support for the projections in blueprint
`def:cl-func`, paper origin
`references/qpbt-paper/05_conditionally_linear_functions.tex:35-57`.
-/
def coordinateRestriction (S : Finset ι) (x : ι → K) : ι → K :=
  fun i => if i ∈ S then x i else 0

/-- Evaluation of a representation of a conditionally linear function.
Lean-only support for blueprint
`def:cl-func`, paper origin
`references/qpbt-paper/05_conditionally_linear_functions.tex:35-57`.
-/
def CondLinearTerm.eval {ι : Type*} [Fintype ι] [DecidableEq ι]
    {K : Type*} [Field K] :
    {ell : ℕ} → _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell → (ι → K) → (ι → K)
  | _, .zero => fun _ => 0
  | _, .succ S₁ L₁ _ rest =>
      fun x =>
        let x₁ := _root_.MIPStarRE.QPBT.coordinateRestriction S₁ x
        L₁ x₁ + CondLinearTerm.eval (rest (L₁ x₁)) x

/-- The support invariant for a representation of a conditionally linear
function.  This is a Lean-only companion to blueprint
`def:cl-func`, paper origin
`references/qpbt-paper/05_conditionally_linear_functions.tex:35-57`.
-/
def CondLinearTerm.supportedOn {ι : Type*} [Fintype ι] [DecidableEq ι]
    {K : Type*} [Field K] :
    {ell : ℕ} → _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell → Finset ι → Prop
  | _, .zero, _ => True
  | _, .succ S₁ _ _ rest, S =>
      S₁ ⊆ S ∧ ∀ y, CondLinearTerm.supportedOn (rest y) (S \ S₁)

/-- The public conditionally-linear predicate.  Its positive syntax-tree
encoding is the Lean representation of blueprint
`def:cl-func`, paper origin
`references/qpbt-paper/05_conditionally_linear_functions.tex:35-57`.
-/
def IsCondLinearOn (K : Type*) [Field K] {ι : Type*} [Fintype ι]
    [DecidableEq ι] (S : Finset ι) (ell : ℕ)
    (L : (ι → K) → (ι → K)) : Prop :=
  ∃ t : _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell,
    _root_.MIPStarRE.QPBT.CondLinearTerm.supportedOn t S ∧ _root_.MIPStarRE.QPBT.CondLinearTerm.eval t = L



/-- The zero conditionally linear function at every level, used to extend the
family `R u` from the image `L(U)` to all indices in the concatenation
construction of `lem:cl-concat`. -/
private def CondLinearTerm.zeroOfLevel {K ι : Type*} [Field K]
    [Fintype ι] [DecidableEq ι] : (ell : ℕ) → _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell
  | 0 => .zero
  | ell + 1 => .succ ∅ 0 (by simp) (fun _ => zeroOfLevel ell)

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







/-- Lift a linear map to the right summand of a direct sum of registers. -/
private def condLinearLiftRight {K ιU ιV : Type*} [Field K]
    (L : (ιV → K) →ₗ[K] (ιV → K)) :
    (ιU ⊕ ιV → K) →ₗ[K] (ιU ⊕ ιV → K) where
  toFun x := Sum.elim 0 (L (fun i => x (.inr i)))
  map_add' x y := by
    ext i
    cases i with
    | inl i => simp
    | inr i => exact congrFun (L.map_add _ _) i
  map_smul' c x := by
    ext i
    cases i with
    | inl i => simp
    | inr i => exact congrFun (L.map_smul c _) i

/-- Lift a representation of a conditionally linear function to the right
summand of a direct sum of registers. -/
private def CondLinearTerm.liftRight {K ιU ιV : Type*} [Field K]
    [Fintype ιU] [DecidableEq ιU] [Fintype ιV] [DecidableEq ιV] :
    {ell : ℕ} → _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ιV) ell →
      _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ιU ⊕ ιV) ell
  | _, .zero => .zero
  | _, .succ S₁ L₁ hSupport rest =>
      .succ (S₁.map Function.Embedding.inr) (condLinearLiftRight L₁)
        (by
          intro x i hi
          cases i with
          | inl i => rfl
          | inr i =>
              apply hSupport
              simpa using hi)
        (fun y => liftRight (rest (fun i => y (.inr i))))

@[simp]
private theorem CondLinearTerm.eval_liftRight {K ιU ιV : Type*} [Field K]
    [Fintype ιU] [DecidableEq ιU] [Fintype ιV] [DecidableEq ιV]
    {ell : ℕ} (t : _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ιV) ell) (x : ιU ⊕ ιV → K) :
    _root_.MIPStarRE.QPBT.CondLinearTerm.eval (CondLinearTerm.liftRight (ιU := ιU) t) x =
      Sum.elim (0 : ιU → K) (_root_.MIPStarRE.QPBT.CondLinearTerm.eval t (fun i => x (.inr i))) := by
  induction t with
  | zero =>
      simp [CondLinearTerm.liftRight, _root_.MIPStarRE.QPBT.CondLinearTerm.eval]
  | @succ ell S₁ L₁ hSupport rest ih =>
      ext i
      cases i <;>
        simp [CondLinearTerm.liftRight, _root_.MIPStarRE.QPBT.CondLinearTerm.eval, condLinearLiftRight,
          _root_.MIPStarRE.QPBT.coordinateRestriction, ih]; rfl









/--
The distribution obtained by applying two conditionally linear maps to a common
uniform seed.  This is blueprint
`def:cl-dist`, paper origin
`references/qpbt-paper/05_conditionally_linear_functions.tex:132-138`.
-/
noncomputable def clDistribution [Fintype K] [DecidableEq K]
    (L R : (ι → K) → (ι → K)) :
    _root_.LIDT.MIPStarRE.LDT.Distribution ((ι → K) × (ι → K)) :=
  (_root_.LIDT.MIPStarRE.LDT.uniformDistribution (ι → K)).map (fun z => (L z, R z))





/--
The graph distribution is uniform on ordered pairs `(a, b)` whose unordered
pair belongs to `E`, including self-loops.  This is blueprint
`def:graph-distribution`;
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:984-1009`.
The underlying graph-distribution definition is
`references/qpbt-paper/07_types.tex:65-82`.
-/
noncomputable def graphDistribution {T : Type*} [Fintype T] [DecidableEq T]
    (E : Finset (Sym2 T)) (_hE : E.Nonempty) : _root_.LIDT.MIPStarRE.LDT.Distribution (T × T) :=
  _root_.LIDT.MIPStarRE.LDT.Distribution.uniformOnFinset
    (Finset.univ.filter fun ab : T × T => Sym2.mk ab.1 ab.2 ∈ E)



/-- The graph distribution is symmetric in its two arguments: it is uniform on
the ordered pairs whose unordered pair is an edge, and that condition does not
depend on the order of the pair.  This is not a named statement of the source
article; it is `lem:graph-distribution-symm` in
`blueprint/src/chapter/ch12_qpbt_games.tex`. -/
theorem graphDistribution_symm {T : Type*} [Fintype T] [DecidableEq T]
    (E : Finset (Sym2 T)) (hE : E.Nonempty) (a b : T) :
    (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight (a, b) =
      (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight (b, a) := by
  classical
  simp [_root_.MIPStarRE.QPBT.graphDistribution, _root_.LIDT.MIPStarRE.LDT.Distribution.uniformOnFinset_weight, Sym2.eq_swap]

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Games/CondLinear.lean#L37-L412

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