Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Test / MagicSquare

Definition
QPBT_QPBT_Test_MagicSquare

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

qpbt

This bundle defines the finite Magic Square question and answer carriers. It distinguishes constraint and cell questions, records incidence and parity data, defines the answer constructors, and supplies finite coding and relabeling infrastructure for the answer alphabet.

Principal definitions:

  • MIPStarRE.QPBT.MsType: defines a Magic Square question as either a row or column constraint or a cell variable.
  • MIPStarRE.QPBT.msConstraintVars: defines the cell incident to a constraint and one of its three positions.
  • MIPStarRE.QPBT.msParity: defines the exceptional Magic Square parity, which is nonzero only on the final constraint.
  • MIPStarRE.QPBT.msEdges: defines the 18 constraint-variable incidence edges of the Magic Square graph.
  • MIPStarRE.QPBT.MsAnswer: defines a Magic Square answer as a parity triple or a single cell bit.
  • MIPStarRE.QPBT.msBitOrZero: defines the total relabeling from the global Magic Square answer alphabet to a bit.
  • MIPStarRE.QPBT.MsAnswerCode: defines a finite code for the two Magic Square answer constructors.
  • MIPStarRE.QPBT.msAnswerEquiv: defines the constructor-preserving code equivalence for Magic Square answers.

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/Test/MagicSquare.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_Defs

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

/-!
# The Magic Square game

The Magic Square component is represented by finite constraint and variable
question types, the incidence graph, and the two corresponding answer forms.
Its rigidity theorem is outside the stage-4.1 statement closure; only the game
carrier is needed here.

## References

This file formalizes blueprint
`def:ms-game`, from
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/

@[expose] public section

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.LDT

/-- A Magic Square question is either a row/column constraint or a cell
variable.  This is blueprint `def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
inductive MsType where
  | constraint (i : Fin 6)
  | var (j : Fin 9)
  deriving DecidableEq, Repr, Inhabited, Fintype

/-- The cell incident to a constraint and one of its three positions in
blueprint `def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
def msConstraintVars (i : Fin 6) (j : Fin 3) : Fin 9 :=
  ⟨if i.val < 3 then i.val * 3 + j.val else i.val - 3 + j.val * 3, by
    by_cases h : i.val < 3 <;> simp [h] <;> omega⟩

/-- The exceptional Magic Square parity, equal to one only on the final
constraint.  Blueprint `def:ms-game`; paper
origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
def msParity (i : Fin 6) : ZMod 2 :=
  if i.val = 5 then 1 else 0

/-- The 18 constraint-variable incidence edges of the Magic Square graph in
blueprint `def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
def msEdges : Finset (Sym2 _root_.MIPStarRE.QPBT.MsType) :=
  (Finset.univ : Finset (Fin 6 × Fin 3)).image (fun ij =>
    Sym2.mk (.constraint ij.1) (.var (_root_.MIPStarRE.QPBT.msConstraintVars ij.1 ij.2)))

/-- The Magic Square incidence graph has an edge, as required by the
nonempty-support API of `graphDistribution`.  This is the finite carrier fact
used to instantiate blueprint `def:ms-game`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
theorem msEdges_nonempty : _root_.MIPStarRE.QPBT.msEdges.Nonempty := by
  refine ⟨Sym2.mk (.constraint 0) (.var (_root_.MIPStarRE.QPBT.msConstraintVars 0 0)), ?_⟩
  exact Finset.mem_image.mpr ⟨(0, 0), Finset.mem_univ _, rfl⟩

/-- A Magic Square answer is a parity triple or a single cell bit, as prescribed
by blueprint `def:ms-game`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
inductive MsAnswer where
  | triple (β : Fin 3 → ZMod 2)
  | bit (γ : ZMod 2)
  deriving DecidableEq

/-- A formalization-only total relabeling from the global Magic Square answer
alphabet to a bit. It folds wrong-form answers into zero so that a variable
question yields a complete binary measurement. -/
def msBitOrZero : _root_.MIPStarRE.QPBT.MsAnswer → ZMod 2
  | .bit b => b
  | .triple _ => 0

/-- A finite code for the two Magic Square answer constructors.  This is
Lean-only carrier infrastructure for blueprint
`def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
abbrev MsAnswerCode := (Fin 3 → ZMod 2) ⊕ ZMod 2

/-- The constructor-preserving code equivalence for `MsAnswer`; Lean-only
finite-carrier infrastructure for blueprint
`def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
noncomputable def msAnswerEquiv : _root_.MIPStarRE.QPBT.MsAnswer ≃ _root_.MIPStarRE.QPBT.MsAnswerCode where
  toFun
    | .triple β => .inl β
    | .bit γ => .inr γ
  invFun
    | .inl β => .triple β
    | .inr γ => .bit γ
  left_inv := by intro x; cases x <;> rfl
  right_inv := by
    intro x
    cases x <;> rfl

noncomputable instance instFintypeMsAnswer : Fintype _root_.MIPStarRE.QPBT.MsAnswer :=
  Fintype.ofEquiv _root_.MIPStarRE.QPBT.MsAnswerCode _root_.MIPStarRE.QPBT.msAnswerEquiv.symm

instance instInhabitedMsAnswer : Inhabited _root_.MIPStarRE.QPBT.MsAnswer := ⟨.bit 0⟩

/-- The Magic Square consistency predicate.  Constructor mismatches are
rejected, as required by blueprint `def:ms-game`; paper
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
def msWinPredicate :
    _root_.MIPStarRE.QPBT.MsType → _root_.MIPStarRE.QPBT.MsType → _root_.MIPStarRE.QPBT.MsAnswer → _root_.MIPStarRE.QPBT.MsAnswer → Bool
  | .constraint i, .constraint j, .triple β, .triple β' =>
      decide (i = j ∧ β = β')
  | .var i, .var j, .bit γ, .bit γ' =>
      decide (i = j ∧ γ = γ')
  | .constraint i, .var j, .triple β, .bit γ =>
      decide
        ((∑ k : Fin 3, β k) = _root_.MIPStarRE.QPBT.msParity i ∧
          ∃ k : Fin 3, _root_.MIPStarRE.QPBT.msConstraintVars i k = j ∧ β k = γ)
  | .var j, .constraint i, .bit γ, .triple β =>
      decide
        ((∑ k : Fin 3, β k) = _root_.MIPStarRE.QPBT.msParity i ∧
          ∃ k : Fin 3, _root_.MIPStarRE.QPBT.msConstraintVars i k = j ∧ β k = γ)
  | _, _, _, _ => false

/-- The Magic Square game as a finite `Game`.  This is blueprint
`def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
@[reducible] noncomputable def msGame : _root_.MIPStarRE.QPBT.Game where
  QuestionA := _root_.MIPStarRE.QPBT.MsType
  QuestionB := _root_.MIPStarRE.QPBT.MsType
  AnswerA := _root_.MIPStarRE.QPBT.MsAnswer
  AnswerB := _root_.MIPStarRE.QPBT.MsAnswer
  μ := _root_.MIPStarRE.QPBT.graphDistribution _root_.MIPStarRE.QPBT.msEdges _root_.MIPStarRE.QPBT.msEdges_nonempty
  μ_prob := by
    apply _root_.LIDT.MIPStarRE.LDT.Distribution.uniformOnFinset_isProbability
    refine ⟨(.constraint 0, .var (_root_.MIPStarRE.QPBT.msConstraintVars 0 0)), ?_⟩
    simp [_root_.MIPStarRE.QPBT.msEdges]
  decide := _root_.MIPStarRE.QPBT.msWinPredicate

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Test/MagicSquare.lean#L27-L147

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