Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Games / TypedCondLinear

Definition
QPBT_QPBT_Games_TypedCondLinear

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

qpbt

This bundle defines the typed conditionally linear distribution for a pair of question types. It samples a type pair from the graph distribution, binds the corresponding conditional-linear law, and records symmetry under exchanging the two players.

Principal definitions:

  • MIPStarRE.QPBT.typedCLDistribution: defines the typed conditionally linear distribution by sampling a type pair and binding the selected conditional-linear distribution.
  • MIPStarRE.QPBT.typedCLDistribution_symm: states that a typed conditionally linear distribution built from one family is symmetric under exchanging the players.

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/TypedCondLinear.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_Games_CondLinear
import Definitions.Def_QPBT_QPBT_Games_DistributionAux

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

/-! # Typed conditionally linear distributions

Typed question distributions first sample an ordered edge of the type graph and
then sample the corresponding pair of conditionally linear images of one common
uniform seed.

## References

These are blueprint `def:typed-cl-functions` and `def:typed-cl-distributions`,
with paper origin
`references/qpbt-paper/07_types.tex:57-94`.
-/

@[expose] public section

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.LDT



/-- The typed CL distribution: sample a type pair from the graph distribution,
then bind it to the CL distribution selected by those two types. This is
blueprint `def:typed-cl-distributions`, paper
`references/qpbt-paper/07_types.tex:84-94`. -/
noncomputable def typedCLDistribution {K T ι : Type*}
    [Field K] [Fintype K] [DecidableEq K]
    [Fintype T] [DecidableEq T] [Fintype ι] [DecidableEq ι]
    (E : Finset (Sym2 T)) (hE : E.Nonempty)
    (L R : T → (ι → K) → (ι → K)) :
    _root_.LIDT.MIPStarRE.LDT.Distribution ((T × (ι → K)) × (T × (ι → K))) :=
  _root_.MIPStarRE.QPBT.Distribution.bind (_root_.MIPStarRE.QPBT.graphDistribution E hE) fun uv =>
    (_root_.MIPStarRE.QPBT.clDistribution (L uv.1) (R uv.2)).map fun xy =>
      ((uv.1, xy.1), (uv.2, xy.2))

/-- A typed conditionally linear distribution built from a single family is
symmetric under exchanging the two players: the edge law of
`def:graph-distribution` is symmetric, and exchanging the two types exchanges
the two images of the common seed.  This is not a named statement of the source
article; it is `lem:typed-cl-distribution-symm` in
`blueprint/src/chapter/ch12_qpbt_games.tex`. -/
theorem typedCLDistribution_symm {K T ι : Type*}
    [Field K] [Fintype K] [DecidableEq K]
    [Fintype T] [DecidableEq T] [Fintype ι] [DecidableEq ι]
    (E : Finset (Sym2 T)) (hE : E.Nonempty)
    (L : T → (ι → K) → (ι → K))
    (c : (T × (ι → K)) × (T × (ι → K))) :
    (_root_.MIPStarRE.QPBT.typedCLDistribution E hE L L).weight c =
      (_root_.MIPStarRE.QPBT.typedCLDistribution E hE L L).weight c.swap := by
  classical
  have hinner : ∀ (u v : T) (w : (T × (ι → K)) × (T × (ι → K))),
      ((_root_.MIPStarRE.QPBT.clDistribution (L u) (L v)).map fun xy => ((u, xy.1), (v, xy.2))).weight w =
        (((Finset.univ : Finset (ι → K)).filter
            fun z => ((u, L u z), (v, L v z)) = w).card : _root_.LIDT.MIPStarRE.LDT.Error) *
          (1 / (Fintype.card (ι → K) : _root_.LIDT.MIPStarRE.LDT.Error)) := by
    intro u v w
    have hmap : ((_root_.MIPStarRE.QPBT.clDistribution (L u) (L v)).map fun xy => ((u, xy.1), (v, xy.2))) =
        (_root_.LIDT.MIPStarRE.LDT.uniformDistribution (ι → K)).map fun z => ((u, L u z), (v, L v z)) := by
      rw [_root_.MIPStarRE.QPBT.clDistribution]
      exact _root_.MIPStarRE.QPBT.Distribution.map_map _ _ _
    rw [hmap, _root_.MIPStarRE.QPBT.uniformDistribution_map_weight]
  have hfib : ∀ (u v : T) (w : (T × (ι → K)) × (T × (ι → K))),
      ((Finset.univ : Finset (ι → K)).filter
          fun z => ((u, L u z), (v, L v z)) = w) =
        ((Finset.univ : Finset (ι → K)).filter
          fun z => ((v, L v z), (u, L u z)) = w.swap) := by
    rintro u v ⟨w₁, w₂⟩
    apply Finset.filter_congr
    intro z _
    exact Prod.swap_inj.symm
  have hbind : ∀ w : (T × (ι → K)) × (T × (ι → K)),
      (_root_.MIPStarRE.QPBT.typedCLDistribution E hE L L).weight w =
        ∑ uv : T × T, (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight uv *
          ((((Finset.univ : Finset (ι → K)).filter
              fun z => ((uv.1, L uv.1 z), (uv.2, L uv.2 z)) = w).card : _root_.LIDT.MIPStarRE.LDT.Error) *
            (1 / (Fintype.card (ι → K) : _root_.LIDT.MIPStarRE.LDT.Error))) := by
    intro w
    have hsupport : (∑ uv ∈ (_root_.MIPStarRE.QPBT.graphDistribution E hE).support,
        (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight uv *
          ((_root_.MIPStarRE.QPBT.clDistribution (L uv.1) (L uv.2)).map
            fun xy => ((uv.1, xy.1), (uv.2, xy.2))).weight w) =
        ∑ uv : T × T, (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight uv *
          ((_root_.MIPStarRE.QPBT.clDistribution (L uv.1) (L uv.2)).map
            fun xy => ((uv.1, xy.1), (uv.2, xy.2))).weight w := by
      refine Finset.sum_subset (Finset.subset_univ _) fun uv _ huv => ?_
      rw [(_root_.MIPStarRE.QPBT.graphDistribution E hE).outsideSupport uv huv, zero_mul]
    change (∑ uv ∈ (_root_.MIPStarRE.QPBT.graphDistribution E hE).support,
      (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight uv *
        ((_root_.MIPStarRE.QPBT.clDistribution (L uv.1) (L uv.2)).map
          fun xy => ((uv.1, xy.1), (uv.2, xy.2))).weight w) = _
    rw [hsupport]
    exact Finset.sum_congr rfl fun uv _ => by rw [hinner uv.1 uv.2 w]
  rw [hbind c, hbind c.swap]
  refine Fintype.sum_equiv (Equiv.prodComm T T) _ _ ?_
  rintro ⟨u, v⟩
  change (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight (u, v) *
      ((((Finset.univ : Finset (ι → K)).filter
          fun z => ((u, L u z), (v, L v z)) = c).card : _root_.LIDT.MIPStarRE.LDT.Error) *
        (1 / (Fintype.card (ι → K) : _root_.LIDT.MIPStarRE.LDT.Error))) =
    (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight (v, u) *
      ((((Finset.univ : Finset (ι → K)).filter
          fun z => ((v, L v z), (u, L u z)) = c.swap).card : _root_.LIDT.MIPStarRE.LDT.Error) *
        (1 / (Fintype.card (ι → K) : _root_.LIDT.MIPStarRE.LDT.Error)))
  rw [_root_.MIPStarRE.QPBT.graphDistribution_symm E hE u v, hfib u v c]

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Games/TypedCondLinear.lean#L35-L117

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