Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Test / LowDegreeGame

Definition
QPBT_QPBT_Test_LowDegreeGame

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

qpbt

This bundle defines the numerical and carrier data for the three-question low-degree game. It fixes the scalar model, question types, register index, ambient coefficient space, and the point and shared-seed coordinates used by the game.

Principal definitions:

  • MIPStarRE.QPBT.LdParams: the numerical parameters of the low-degree game.
  • MIPStarRE.QPBT.LdParams.model: the fixed scalar model selected by the parameters.
  • MIPStarRE.QPBT.ScalarQ: the scalar carrier selected by the model.
  • MIPStarRE.QPBT.LdType: the three low-degree question types.
  • MIPStarRE.QPBT.LdIndex: the register index used by the game.
  • MIPStarRE.QPBT.LdSpace: the ambient low-degree coefficient space.
  • MIPStarRE.QPBT.LdSpace.point: the point coordinates of an ambient vector.
  • MIPStarRE.QPBT.LdSpace.seed: the shared scalar coordinate of an ambient vector.

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/LowDegreeGame.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_Algebra_Coefficients
import Definitions.Def_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Algebra_Lines
import Definitions.Def_QPBT_QPBT_Games_Defs
import Mathlib
import Theorems.Thm_LIDT_MIPStarRE_LDT_Distribution_IsProbability_map

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

/-!
# The low-degree game

The low-degree component of the Pauli basis test has finite question and answer
alphabets.  Its question maps act explicitly on the point, coordinate, and
direction registers of the ambient coefficient space and have recursive
conditionally linear representations of levels one, two, and three.

## References

The source-facing nodes are blueprint `def:ld-game`,
`def:ld-question-distribution`, and `def:ld-win-predicate`; their paper origin is
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
The exact decomposition of a scalar seed into its coordinate index and its
residue records the balance assertion for the map `chi` in the same source
definition.
-/

@[expose] public section

open scoped BigOperators

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.LDT

noncomputable section

/-- Numerical parameters for the low-degree game.  The ambient coefficient
space uses the once-and-for-all model `fixedFieldModel P.q P.hq`, rather than a
model supplied by each parameter record.  This is the Lean carrier for
blueprint
`def:ld-game`, with paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
structure LdParams where
  q : ℕ
  m : ℕ
  d : ℕ
  k : ℕ
  hm : 1 ≤ m
  hd : 1 ≤ d
  hk : 1 ≤ k
  hq : _root_.MIPStarRE.QPBT.IsAdmissibleSize q
  hdvd : m ∣ q

/-- The positive dimension in `LdParams` supplies the finite coordinate type
used by the uniform axis and prefix-index marginals. -/
instance instNonemptyFinM (L : _root_.MIPStarRE.QPBT.LdParams) : Nonempty (Fin L.m) :=
  ⟨⟨0, lt_of_lt_of_le Nat.zero_lt_one L.hm⟩⟩

/-- The fixed scalar model of a low-degree parameter tuple.  It is a
compatibility view of the global `fixedFieldModel` selector, not an
independently quantified field representation.  Blueprint `def:ld-game`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
@[reducible] noncomputable def LdParams.model (P : _root_.MIPStarRE.QPBT.LdParams) : _root_.MIPStarRE.QPBT.FixedFieldModel P.q :=
  _root_.MIPStarRE.QPBT.fixedFieldModel P.q P.hq

/-- The scalar carrier selected by an `LdParams` record; this is the fixed
field carrier in `def:ld-game`, selected globally by `LdParams.model`.
Blueprint `def:ld-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
abbrev ScalarQ (P : _root_.MIPStarRE.QPBT.LdParams) := (P.model).K

/-- The three low-degree question types of blueprint
`def:ld-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
inductive LdType where
  | point
  | aline
  | dline
  deriving DecidableEq, Repr, Inhabited
instance LdType.instFintype : Fintype _root_.MIPStarRE.QPBT.LdType :=
  ⟨{.point, .aline, .dline}, by intro x; cases x <;> simp⟩
/-- The register index used by the low-degree game (blueprint
`def:ld-game`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`).
-/
abbrev LdIndex (P : _root_.MIPStarRE.QPBT.LdParams) := (Fin P.m ⊕ Unit) ⊕ Fin P.m

/-- The full ambient low-degree coefficient space (blueprint
`def:ld-game`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`).
-/
abbrev LdSpace (P : _root_.MIPStarRE.QPBT.LdParams) := _root_.MIPStarRE.QPBT.LdIndex P → _root_.MIPStarRE.QPBT.ScalarQ P

/-- The point coordinates of an ambient low-degree vector in
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
def LdSpace.point {P : _root_.MIPStarRE.QPBT.LdParams} (z : _root_.MIPStarRE.QPBT.LdSpace P) : Fin P.m → _root_.MIPStarRE.QPBT.ScalarQ P :=
  fun i => z (.inl (.inl i))

/-- The shared scalar coordinate of an ambient low-degree vector in
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
def LdSpace.seed {P : _root_.MIPStarRE.QPBT.LdParams} (z : _root_.MIPStarRE.QPBT.LdSpace P) : _root_.MIPStarRE.QPBT.ScalarQ P :=
  z (.inl (.inr ()) )

/-- The direction coordinates of an ambient low-degree vector in
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
def LdSpace.direction {P : _root_.MIPStarRE.QPBT.LdParams} (z : _root_.MIPStarRE.QPBT.LdSpace P) : Fin P.m → _root_.MIPStarRE.QPBT.ScalarQ P :=
  fun i => z (.inr i)

/-- The zero-based coordinate index corresponding to the paper's map `χ`:
`chiIndex P s` represents `χ(s) - 1` in the fixed field representation.  This
is `eq:chi-func` in blueprint `def:ld-question-distribution`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
noncomputable def chiIndex (P : _root_.MIPStarRE.QPBT.LdParams) (s : _root_.MIPStarRE.QPBT.ScalarQ P) : Fin P.m := by
  letI : NeZero P.m := ⟨by
    exact Nat.ne_of_gt (lt_of_lt_of_le Nat.zero_lt_one P.hm)⟩
  exact Fin.ofNat P.m ((_root_.MIPStarRE.QPBT.binaryRepresentation P.model s).val / (P.q / P.m))

/-! ### Formalization-only coordinate-index fibers

The following decomposition supplies the equal-fiber calculation used in the
uniform coordinate-index law.
-/

/-- The common residue set in a fiber of `chiIndex` is nonempty.  This is part
of the exact seed decomposition supporting the balance assertion in
`def:ld-question-distribution`, blueprint `lem:chi-seed-fibers`, paper
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:215-221`.
-/
theorem LdParams.seedFiberCard_pos (L : _root_.MIPStarRE.QPBT.LdParams) : 0 < L.q / L.m := by
  exact Nat.div_pos (Nat.le_of_dvd (by
    obtain ⟨n, hn, hq⟩ := L.hq
    rw [hq]
    exact Nat.pow_pos (by decide)) L.hdvd) L.hm

/-- Divisibility identifies the scalar cardinality with the product of the
coordinate-index cardinality and the common fiber cardinality.  This supports
`lem:chi-seed-fibers` in blueprint chapter 13. -/
theorem LdParams.seedFiberProduct_eq (L : _root_.MIPStarRE.QPBT.LdParams) :
    L.q = L.m * (L.q / L.m) :=
  (Nat.mul_div_cancel' L.hdvd).symm

/-- Casting between equal finite cardinalities preserves the underlying
natural-number representative. -/
@[simp] private theorem equivCastFin_val {m n : ℕ} (h : m = n) (i : Fin m) :
    (Equiv.cast (congrArg Fin h) i).val = i.val := by
  subst n
  rfl

/-- A scalar seed is uniquely a coordinate index and a residue in its
`chiIndex` fiber.  This is the exact decomposition underlying
`lem:chi-seed-fibers` in blueprint chapter 13. -/
noncomputable def seedFiberEquiv (L : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.MIPStarRE.QPBT.ScalarQ L ≃ Fin L.m × Fin (L.q / L.m) :=
  (_root_.MIPStarRE.QPBT.binaryRepresentation L.model).trans <|
    (Equiv.cast <| congrArg Fin L.seedFiberProduct_eq).trans
      finProdFinEquiv.symm

/-- The coordinate component of the exact seed decomposition is `chiIndex`. -/
@[simp] theorem seedFiberEquiv_fst (L : _root_.MIPStarRE.QPBT.LdParams) (s : _root_.MIPStarRE.QPBT.ScalarQ L) :
    (_root_.MIPStarRE.QPBT.seedFiberEquiv L s).1 = _root_.MIPStarRE.QPBT.chiIndex L s := by
  letI : NeZero L.m := ⟨Nat.ne_of_gt (lt_of_lt_of_le Nat.zero_lt_one L.hm)⟩
  have hquot : (_root_.MIPStarRE.QPBT.binaryRepresentation L.model s).val / (L.q / L.m) < L.m := by
    apply (Nat.div_lt_iff_lt_mul L.seedFiberCard_pos).mpr
    rw [Nat.mul_div_cancel' L.hdvd]
    exact (_root_.MIPStarRE.QPBT.binaryRepresentation L.model s).isLt
  simp only [_root_.MIPStarRE.QPBT.seedFiberEquiv, Equiv.trans_apply]
  apply Fin.ext
  change
    (Equiv.cast (congrArg Fin L.seedFiberProduct_eq)
      (_root_.MIPStarRE.QPBT.binaryRepresentation L.model s)).val / (L.q / L.m) =
      (Fin.ofNat L.m ((_root_.MIPStarRE.QPBT.binaryRepresentation L.model s).val / (L.q / L.m))).val
  rw [equivCastFin_val]
  · exact (Nat.mod_eq_of_lt hquot).symm
  · exact L.seedFiberProduct_eq

/-- Reconstruct the scalar seed belonging to a coordinate and its fiber
residue. -/
noncomputable def seedOfIndexResidue (L : _root_.MIPStarRE.QPBT.LdParams)
    (i : Fin L.m) (r : Fin (L.q / L.m)) : _root_.MIPStarRE.QPBT.ScalarQ L :=
  (_root_.MIPStarRE.QPBT.seedFiberEquiv L).symm (i, r)

/-- Decomposing a reconstructed seed recovers its coordinate and residue. -/
@[simp] theorem seedFiberEquiv_seedOfIndexResidue (L : _root_.MIPStarRE.QPBT.LdParams)
    (i : Fin L.m) (r : Fin (L.q / L.m)) :
    _root_.MIPStarRE.QPBT.seedFiberEquiv L (_root_.MIPStarRE.QPBT.seedOfIndexResidue L i r) = (i, r) :=
  (_root_.MIPStarRE.QPBT.seedFiberEquiv L).apply_symm_apply (i, r)

/-- A reconstructed seed belongs to the prescribed `chiIndex` fiber. -/
@[simp] theorem chiIndex_seedOfIndexResidue (L : _root_.MIPStarRE.QPBT.LdParams)
    (i : Fin L.m) (r : Fin (L.q / L.m)) :
    _root_.MIPStarRE.QPBT.chiIndex L (_root_.MIPStarRE.QPBT.seedOfIndexResidue L i r) = i := by
  rw [← _root_.MIPStarRE.QPBT.seedFiberEquiv_fst]
  simp

/-- The projection used in the diagonal-line map zeroes coordinates before the
chosen index and retains the suffix of the direction vector.  This is the
prefix restriction in blueprint
`def:ld-question-distribution`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
def prefixProjection {P : _root_.MIPStarRE.QPBT.LdParams} (i : Fin P.m) (v : Fin P.m → _root_.MIPStarRE.QPBT.ScalarQ P) :
    Fin P.m → _root_.MIPStarRE.QPBT.ScalarQ P :=
  fun j => if j.val < i.val then 0 else v j



/-- The point CL map, retaining the point block and clearing the auxiliary
blocks.  It is the map `L_point` of blueprint
`def:ld-question-distribution`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
def ldPointCL (P : _root_.MIPStarRE.QPBT.LdParams) (z : _root_.MIPStarRE.QPBT.LdSpace P) : _root_.MIPStarRE.QPBT.LdSpace P :=
  fun i => match i with
  | .inl (.inl j) => z (.inl (.inl j))
  | .inl (.inr _) => 0
  | .inr _ => 0

/-- The affine-line CL map.  The direction block is put through the canonical
line representative map from `def:line-representative`, while the point block
is retained (blueprint `def:ld-question-distribution`; paper
origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`).
-/
noncomputable def ldALineCL (P : _root_.MIPStarRE.QPBT.LdParams) (z : _root_.MIPStarRE.QPBT.LdSpace P) : _root_.MIPStarRE.QPBT.LdSpace P :=
  let i := _root_.MIPStarRE.QPBT.chiIndex P (z.seed)
  let rep := _root_.MIPStarRE.QPBT.lineRepMap (_root_.MIPStarRE.QPBT.coordinateDirection i)
  fun i => match i with
  | .inl (.inl j) => (rep (z.point)) j
  | .inl (.inr _) => z (.inl (.inr ()))
  | .inr _ => 0

/-- The diagonal-line CL map applies the canonical line representative map to
the point block and stores the prefix-projected direction in the direction
block.  This is the `L_DLine` clause of
`def:ld-question-distribution` (blueprint
`def:ld-question-distribution`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`).
-/
noncomputable def ldDLineCL (P : _root_.MIPStarRE.QPBT.LdParams) (z : _root_.MIPStarRE.QPBT.LdSpace P) : _root_.MIPStarRE.QPBT.LdSpace P :=
  let i := _root_.MIPStarRE.QPBT.chiIndex P (z.seed)
  let direction := _root_.MIPStarRE.QPBT.prefixProjection i (z.direction)
  let rep := _root_.MIPStarRE.QPBT.lineRepMap direction
  fun i => match i with
  | .inl (.inl j) => (rep (z.point)) j
  | .inl (.inr _) => z (.inl (.inr ()))
  | .inr j => direction j

/-- The conditionally linear map attached to each low-degree question type.
This is the typed construction in blueprint
`def:ld-question-distribution`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
noncomputable def ldCL (P : _root_.MIPStarRE.QPBT.LdParams) : _root_.MIPStarRE.QPBT.LdType → _root_.MIPStarRE.QPBT.LdSpace P → _root_.MIPStarRE.QPBT.LdSpace P
  | .point => _root_.MIPStarRE.QPBT.ldPointCL P
  | .aline => _root_.MIPStarRE.QPBT.ldALineCL P
  | .dline => _root_.MIPStarRE.QPBT.ldDLineCL P









































/-- The question alphabet for the low-degree game (blueprint
`def:ld-game`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`).
-/
abbrev LdQuestion (P : _root_.MIPStarRE.QPBT.LdParams) := _root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdSpace P

/-- The typed CL question distribution.  This is the inlined construction in
blueprint `def:ld-question-distribution`; paper
origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
noncomputable def ldQuestionDistribution (P : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.LdQuestion P × _root_.MIPStarRE.QPBT.LdQuestion P) :=
  _root_.LIDT.MIPStarRE.LDT.Distribution.map
    (_root_.LIDT.MIPStarRE.LDT.uniformDistribution ((_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType) × _root_.MIPStarRE.QPBT.LdSpace P))
    (fun s =>
      ((s.1.1, _root_.MIPStarRE.QPBT.ldCL P s.1.1 s.2), (s.1.2, _root_.MIPStarRE.QPBT.ldCL P s.1.2 s.2)))

/-- The coefficient-tuple answer alphabet of the low-degree game.  Polynomial
answers are representatives with exactly the coefficient lengths printed in
the paper, as required by `def:ld-win-predicate` (blueprint
`def:ld-win-predicate`; paper
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`).
-/
inductive LdAnswer (P : _root_.MIPStarRE.QPBT.LdParams) where
  | pointVals (a : Fin P.k → _root_.MIPStarRE.QPBT.ScalarQ P)
  | alinePolys (a : Fin P.k → Fin (P.d + 1) → _root_.MIPStarRE.QPBT.ScalarQ P)
  | dlinePolys (a : Fin P.k → Fin (P.m * P.d + 1) → _root_.MIPStarRE.QPBT.ScalarQ P)
  deriving DecidableEq

/-- A finite sum code used only to provide the answer alphabet's `Fintype`
instance; the public constructors are those of blueprint
`def:ld-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
abbrev LdAnswerCode (P : _root_.MIPStarRE.QPBT.LdParams) :=
  (Fin P.k → _root_.MIPStarRE.QPBT.ScalarQ P) ⊕
    ((Fin P.k → Fin (P.d + 1) → _root_.MIPStarRE.QPBT.ScalarQ P) ⊕
      (Fin P.k → Fin (P.m * P.d + 1) → _root_.MIPStarRE.QPBT.ScalarQ P))

/-- The canonical code equivalence for `LdAnswer`, sending point, axis-line,
and diagonal-line answers to the three summands (Lean-only finite-carrier
support for blueprint
`def:ld-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`).
-/
noncomputable def ldAnswerEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.MIPStarRE.QPBT.LdAnswer P ≃ _root_.MIPStarRE.QPBT.LdAnswerCode P where
  toFun
    | .pointVals a => .inl a
    | .alinePolys a => .inr (.inl a)
    | .dlinePolys a => .inr (.inr a)
  invFun
    | .inl a => .pointVals a
    | .inr (.inl a) => .alinePolys a
    | .inr (.inr a) => .dlinePolys a
  left_inv := by intro x; cases x <;> rfl
  right_inv := by
    intro x
    cases x with
    | inl a => rfl
    | inr x =>
        cases x with
        | inl a => rfl
        | inr a => rfl

instance instInhabitedLdAnswer (P : _root_.MIPStarRE.QPBT.LdParams) : Inhabited (_root_.MIPStarRE.QPBT.LdAnswer P) :=
  ⟨.pointVals (fun _ => 0)⟩

noncomputable instance instFintypeLdAnswer (P : _root_.MIPStarRE.QPBT.LdParams) : Fintype (_root_.MIPStarRE.QPBT.LdAnswer P) :=
  Fintype.ofEquiv (_root_.MIPStarRE.QPBT.LdAnswerCode P) (_root_.MIPStarRE.QPBT.ldAnswerEquiv P).symm

/-- Check that an answer has the constructor prescribed by its question type;
Lean encoding of the rejection clause in blueprint
`def:ld-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
def validLdAnswer {P : _root_.MIPStarRE.QPBT.LdParams} (t : _root_.MIPStarRE.QPBT.LdType) (a : _root_.MIPStarRE.QPBT.LdAnswer P) : Bool :=
  match t, a with
  | .point, .pointVals _ => true
  | .aline, .alinePolys _ => true
  | .dline, .dlinePolys _ => true
  | _, _ => false

/-- The axis-parallel line/point relation in blueprint
`def:ld-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
def alinePointCondition (P : _root_.MIPStarRE.QPBT.LdParams) (line point : _root_.MIPStarRE.QPBT.LdSpace P)
    (f : Fin P.k → Fin (P.d + 1) → _root_.MIPStarRE.QPBT.ScalarQ P)
    (a : Fin P.k → _root_.MIPStarRE.QPBT.ScalarQ P) : Prop :=
  -- Universal quantification follows the zero-direction convention in
  -- `rem:ld-win-zero-direction`.
  ∀ t : _root_.MIPStarRE.QPBT.ScalarQ P,
    point.point = line.point + t • _root_.MIPStarRE.QPBT.coordinateDirection (_root_.MIPStarRE.QPBT.chiIndex P line.seed) →
      ∀ j : Fin P.k, _root_.MIPStarRE.QPBT.evalCoefficient (f j) t = a j

/-- The diagonal line/point relation in blueprint
`def:ld-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
def dlinePointCondition (P : _root_.MIPStarRE.QPBT.LdParams) (line point : _root_.MIPStarRE.QPBT.LdSpace P)
    (f : Fin P.k → Fin (P.m * P.d + 1) → _root_.MIPStarRE.QPBT.ScalarQ P)
    (a : Fin P.k → _root_.MIPStarRE.QPBT.ScalarQ P) : Prop :=
  ∀ t : _root_.MIPStarRE.QPBT.ScalarQ P,
    point.point = line.point + t • line.direction →
      ∀ j : Fin P.k, _root_.MIPStarRE.QPBT.evalCoefficient (f j) t = a j

/-- The low-degree consistency predicate, rejecting answers of the wrong
constructor shape.  This is blueprint
`def:ld-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
noncomputable def ldWinPredicate (P : _root_.MIPStarRE.QPBT.LdParams) :
    _root_.MIPStarRE.QPBT.LdQuestion P → _root_.MIPStarRE.QPBT.LdQuestion P → _root_.MIPStarRE.QPBT.LdAnswer P → _root_.MIPStarRE.QPBT.LdAnswer P → Bool :=
  open Classical in
  fun (tA, xA) (tB, xB) a b =>
      if _root_.MIPStarRE.QPBT.validLdAnswer tA a && _root_.MIPStarRE.QPBT.validLdAnswer tB b then
        match tA, tB, a, b with
        | .point, .point, .pointVals u, .pointVals v => decide (u = v)
        | .aline, .point, .alinePolys f, .pointVals u =>
            decide (_root_.MIPStarRE.QPBT.alinePointCondition P xA xB f u)
        | .point, .aline, .pointVals u, .alinePolys f =>
            decide (_root_.MIPStarRE.QPBT.alinePointCondition P xB xA f u)
        | .dline, .point, .dlinePolys f, .pointVals u =>
            decide (_root_.MIPStarRE.QPBT.dlinePointCondition P xA xB f u)
        | .point, .dline, .pointVals u, .dlinePolys f =>
            decide (_root_.MIPStarRE.QPBT.dlinePointCondition P xB xA f u)
        | .aline, .aline, .alinePolys f, .alinePolys g => decide (f = g)
        | .dline, .dline, .dlinePolys f, .dlinePolys g => decide (f = g)
        | _, _, _, _ => true
      else false

/-- The low-degree game determined by its question distribution and win
predicate. This is blueprint
`def:ld-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`.
-/
noncomputable def ldGame (P : _root_.MIPStarRE.QPBT.LdParams) : _root_.MIPStarRE.QPBT.Game where
  QuestionA := _root_.MIPStarRE.QPBT.LdQuestion P
  QuestionB := _root_.MIPStarRE.QPBT.LdQuestion P
  AnswerA := _root_.MIPStarRE.QPBT.LdAnswer P
  AnswerB := _root_.MIPStarRE.QPBT.LdAnswer P
  μ := _root_.MIPStarRE.QPBT.ldQuestionDistribution P
  μ_prob := by
    exact _root_.LIDT.MIPStarRE.LDT.Distribution.IsProbability.map
      (_root_.LIDT.MIPStarRE.LDT.uniformDistribution_isProbability ((_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType) × _root_.MIPStarRE.QPBT.LdSpace P)) _
  decide := _root_.MIPStarRE.QPBT.ldWinPredicate P

end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Test/LowDegreeGame.lean#L37-L771

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