Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Combining / DirectLowDegree / Transport / Combining / Parameters

Definition
QPBT_QPBT_Combining_DirectLowDegree_Transport_Combining_Parameters

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

qpbt

This bundle defines the parameter and polynomial data for the combined low-degree game. It increases the dimension by the coefficient-coordinate count, forms the combined polynomial from direct representatives, and records the associated tuple and parameter maps.

Principal definitions:

  • MIPStarRE.QPBT.DirectLdParams.combined: defines the combined-game parameters and retained admissibility data.
  • MIPStarRE.QPBT.directCombinedPolynomial: defines the coefficient-weighted combined polynomial.
  • MIPStarRE.QPBT.directCombinedTuple: defines the one-component tuple carrying that polynomial.
  • MIPStarRE.QPBT.IsDirectCombined: predicates the combined-polynomial class.
  • MIPStarRE.QPBT.directTupleOfCombined: recovers the tuple represented by a combined polynomial.
  • MIPStarRE.QPBT.directTupleOfCombinedTuple: recovers the tuple represented by a combined outcome.

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/Combining/DirectLowDegree/Transport/Combining/Parameters.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_Preliminaries_Polynomials
import Definitions.Def_LIDT_MIPStarRE_LDT_Tactic_AvgCongr
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyCore
import Definitions.Def_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Combining_DirectLowDegree_Game
import Definitions.Def_QPBT_QPBT_Combining_DirectLowDegree_Geometry
import Definitions.Def_QPBT_QPBT_Combining_DirectLowDegree_Transport_Combining_Polynomial
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGameMeasurements
import Mathlib

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

/-!
# The combined parameters of the simultaneity reduction

The extension of the quantum soundness of the low individual degree test from
simultaneity parameter `1` to a general simultaneity parameter `k` applies the
case `k = 1` once, to a directly indexed low-degree game whose dimension is
`m + k` and whose simultaneity parameter is `1`.  This module records that
parameter map, the polynomial-tuple outcomes it carries, and the two maps
relating outcomes of the two games: the combining map, which sends a tuple of
`k` polynomials in `m` variables to the one-component tuple consisting of the
combined polynomial in `m + k` variables, and its total left inverse, which
returns the components of a combined polynomial and an arbitrary tuple
otherwise.

The field, the degree, and the admissibility of the field size are inherited
unchanged; only the dimension and the simultaneity parameter change.  The
degree is inherited because the combining map is linear in the fresh
coordinates, so it raises no individual degree above `d` when `1 ≤ d`; this is
where the individual-degree formulation differs from the total-degree
formulation of the source, which passes from degree `d` to degree `d + 1`.

## References

* `references/neexp-paper/05_quantum_preliminaries.tex:1409-1503`
* `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:413-458`
* `blueprint/src/chapter/ch13_qpbt_test.tex:240-250`
* `docs/paper-gaps/qpbt_ld-simultaneous-sandwich.tex`
-/

@[expose] public section

open scoped BigOperators

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.LDT
open LIDT.MIPStarRE.LDT.Preliminaries

noncomputable section

/-! ## The combined parameter tuple -/

/-- The parameters of the game to which the reduction applies the case of
simultaneity parameter `1`: the dimension grows from `m` to `m + k` and the
simultaneity parameter becomes `1`, while the field size, the degree, and the
admissibility hypothesis are unchanged. -/
@[reducible] def DirectLdParams.combined (D : _root_.MIPStarRE.QPBT.DirectLdParams) : _root_.MIPStarRE.QPBT.DirectLdParams where
  q := D.q
  m := D.m + D.k
  d := D.d
  k := 1
  hm := le_trans D.hm (Nat.le_add_right D.m D.k)
  hd := D.hd
  hk := le_refl 1
  hq := D.hq

@[simp] theorem DirectLdParams.combined_q (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    D.combined.q = D.q := rfl

@[simp] theorem DirectLdParams.combined_m (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    D.combined.m = D.m + D.k := rfl

@[simp] theorem DirectLdParams.combined_d (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    D.combined.d = D.d := rfl

@[simp] theorem DirectLdParams.combined_k (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    D.combined.k = 1 := rfl





/-- The one-element index set of the combined simultaneity parameter. -/
instance instUniqueFinKCombined (D : _root_.MIPStarRE.QPBT.DirectLdParams) : Unique (Fin D.combined.k) :=
  show Unique (Fin 1) from inferInstance

/-! ## The combining map on game outcomes -/

/-- The combined polynomial of a tuple of direct polynomial representatives:
`(u, α) ↦ ∑_{r < k} α_r g_r(u)`, of individual degree at most `d` in the
`m + k` variables of the combined parameters.

Source `references/neexp-paper/05_quantum_preliminaries.tex:1425-1435`. -/
def directCombinedPolynomial (D : _root_.MIPStarRE.QPBT.DirectLdParams) (g : _root_.MIPStarRE.QPBT.DirectPolyTuple D) :
    _root_.MIPStarRE.QPBT.PolyIndex D.combined.m (_root_.MIPStarRE.QPBT.DirectScalarQ D) D.d :=
  ⟨_root_.MIPStarRE.QPBT.combinePolyTuple (fun r => (g r).1),
    _root_.MIPStarRE.QPBT.combinePolyTuple_mem_polyFunc D.hd _ fun r => (g r).2⟩

@[simp] theorem directCombinedPolynomial_val (D : _root_.MIPStarRE.QPBT.DirectLdParams) (g : _root_.MIPStarRE.QPBT.DirectPolyTuple D) :
    (_root_.MIPStarRE.QPBT.directCombinedPolynomial D g).1 = _root_.MIPStarRE.QPBT.combinePolyTuple (fun r => (g r).1) :=
  rfl



/-- The combining map is injective on polynomial tuples. -/
theorem directCombinedPolynomial_injective (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
    Function.Injective (_root_.MIPStarRE.QPBT.directCombinedPolynomial D) := by
  intro g g' h
  have hval : _root_.MIPStarRE.QPBT.combinePolyTuple (fun r => (g r).1) =
      _root_.MIPStarRE.QPBT.combinePolyTuple (fun r => (g' r).1) := congrArg Subtype.val h
  have hcomp := _root_.MIPStarRE.QPBT.combinePolyTuple_injective hval
  funext r
  exact Subtype.ext (congrFun hcomp r)

/-- The one-component polynomial tuple of the combined game carrying the
combined polynomial of a tuple. -/
def directCombinedTuple (D : _root_.MIPStarRE.QPBT.DirectLdParams) (g : _root_.MIPStarRE.QPBT.DirectPolyTuple D) :
    _root_.MIPStarRE.QPBT.DirectPolyTuple D.combined :=
  fun _ => _root_.MIPStarRE.QPBT.directCombinedPolynomial D g

@[simp] theorem directCombinedTuple_apply (D : _root_.MIPStarRE.QPBT.DirectLdParams) (g : _root_.MIPStarRE.QPBT.DirectPolyTuple D)
    (r : Fin D.combined.k) :
    _root_.MIPStarRE.QPBT.directCombinedTuple D g r = _root_.MIPStarRE.QPBT.directCombinedPolynomial D g := rfl

/-! ## Recovering the polynomial tuple -/

/-- A polynomial in the variables of the combined parameters is combined when it
is the combined polynomial of a tuple.  This is the source's exact linearity in
the combining variables, together with the individual-degree bound on the
components.  Source
`references/neexp-paper/05_quantum_preliminaries.tex:1462-1477`. -/
def IsDirectCombined (D : _root_.MIPStarRE.QPBT.DirectLdParams)
    (p : _root_.MIPStarRE.QPBT.PolyIndex D.combined.m (_root_.MIPStarRE.QPBT.DirectScalarQ D) D.d) : Prop :=
  ∃ g : _root_.MIPStarRE.QPBT.DirectPolyTuple D, _root_.MIPStarRE.QPBT.directCombinedPolynomial D g = p

theorem isDirectCombined_directCombinedPolynomial (D : _root_.MIPStarRE.QPBT.DirectLdParams)
    (g : _root_.MIPStarRE.QPBT.DirectPolyTuple D) : _root_.MIPStarRE.QPBT.IsDirectCombined D (_root_.MIPStarRE.QPBT.directCombinedPolynomial D g) :=
  ⟨g, rfl⟩

/-- The polynomial tuple represented by a polynomial in the variables of the
combined parameters: its components when it is combined, and the zero tuple
otherwise.  The source leaves the value on non-combined outcomes arbitrary; the
zero tuple is one admissible choice, and the estimates use only the value on
combined outcomes.  Source
`references/neexp-paper/05_quantum_preliminaries.tex:1477-1483`. -/
def directTupleOfCombined (D : _root_.MIPStarRE.QPBT.DirectLdParams)
    (p : _root_.MIPStarRE.QPBT.PolyIndex D.combined.m (_root_.MIPStarRE.QPBT.DirectScalarQ D) D.d) : _root_.MIPStarRE.QPBT.DirectPolyTuple D := by
  classical
  exact if h : _root_.MIPStarRE.QPBT.IsDirectCombined D p then h.choose else fun _ => 0

/-- The components of a combined polynomial are the tuple it combines. -/
@[simp] theorem directTupleOfCombined_directCombinedPolynomial (D : _root_.MIPStarRE.QPBT.DirectLdParams)
    (g : _root_.MIPStarRE.QPBT.DirectPolyTuple D) :
    _root_.MIPStarRE.QPBT.directTupleOfCombined D (_root_.MIPStarRE.QPBT.directCombinedPolynomial D g) = g := by
  classical
  have hex : _root_.MIPStarRE.QPBT.IsDirectCombined D (_root_.MIPStarRE.QPBT.directCombinedPolynomial D g) :=
    _root_.MIPStarRE.QPBT.isDirectCombined_directCombinedPolynomial D g
  rw [_root_.MIPStarRE.QPBT.directTupleOfCombined, dif_pos hex]
  exact _root_.MIPStarRE.QPBT.directCombinedPolynomial_injective D hex.choose_spec

/-- The polynomial tuple represented by an outcome of the combined game. -/
def directTupleOfCombinedTuple (D : _root_.MIPStarRE.QPBT.DirectLdParams)
    (p : _root_.MIPStarRE.QPBT.DirectPolyTuple D.combined) : _root_.MIPStarRE.QPBT.DirectPolyTuple D :=
  _root_.MIPStarRE.QPBT.directTupleOfCombined D (p default)

@[simp] theorem directTupleOfCombinedTuple_directCombinedTuple (D : _root_.MIPStarRE.QPBT.DirectLdParams)
    (g : _root_.MIPStarRE.QPBT.DirectPolyTuple D) :
    _root_.MIPStarRE.QPBT.directTupleOfCombinedTuple D (_root_.MIPStarRE.QPBT.directCombinedTuple D g) = g := by
  rw [_root_.MIPStarRE.QPBT.directTupleOfCombinedTuple, _root_.MIPStarRE.QPBT.directCombinedTuple_apply,
    _root_.MIPStarRE.QPBT.directTupleOfCombined_directCombinedPolynomial]

end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Combining/DirectLowDegree/Transport/Combining/Parameters.lean#L48-L178

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