QPBT definitions: Combining / DirectLowDegree / Transport / Combining / Parameters
DefinitionQPBT_QPBT_Combining_DirectLowDegree_Transport_Combining_Parametersqpbt
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