QPBT definitions: Combining / DirectLowDegree / Transport / Correspondence
DefinitionQPBT_QPBT_Combining_DirectLowDegree_Transport_Correspondenceqpbt
This bundle establishes the correspondence between directly indexed parameters and the original LDT model. It converts fields and points, constructs coefficient polynomials, identifies axis and diagonal answer types, and forgets the auxiliary divisibility data.
Principal definitions:
MIPStarRE.QPBT.directScalarEquiv: the direct-to-LDT scalar equivalence.MIPStarRE.QPBT.directPointEquiv: the point equivalence with reversed coordinate order.MIPStarRE.QPBT.coefficientPolynomial: builds a bounded polynomial from a coefficient vector.MIPStarRE.QPBT.directAxisAnswerEquiv: identifies direct axis coefficients with LDT axis answers.MIPStarRE.QPBT.directDiagonalAnswerEquiv: identifies direct diagonal coefficients with LDT diagonal 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/Combining/DirectLowDegree/Transport/Correspondence.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_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_Test_LowDegreeGame
import Mathlib
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace LIDT.MIPStarRE.Quantum
end LIDT.MIPStarRE.Quantum
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
/-!
# Question correspondence for the directly indexed low-degree game
The finite-field coordinates, polynomial answers, and question law of the
directly indexed game are equivalent to their seed-indexed and low individual
degree counterparts.
## References
- `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-458`
- `references/ldt-paper/test_definition.tex:98-151`
- `docs/paper-gaps/qpbt_ld-dimension-divisibility.tex`
-/
@[expose] public section
open scoped BigOperators MatrixOrder Matrix ComplexOrder
namespace MIPStarRE.QPBT
open LIDT.MIPStarRE.LDT
open LIDT.MIPStarRE.Quantum
noncomputable section
/-! ## Parameters and finite-field coordinates -/
/-- Regard direct-game parameters as low individual degree test parameters.
The field size, dimension, and degree are unchanged. -/
@[reducible] def DirectLdParams.toLDTParameters (D : _root_.MIPStarRE.QPBT.DirectLdParams) : _root_.LIDT.MIPStarRE.LDT.Parameters where
m := D.m
q := D.q
d := D.d
hm := lt_of_lt_of_le Nat.zero_lt_one D.hm
hq := by
obtain ⟨n, hn, hq⟩ := D.hq
rw [hq]
exact Nat.pow_pos (by decide)
hqPrimePower := by
obtain ⟨n, hn, hq⟩ := D.hq
exact ⟨2, n, Nat.prime_two, hn.pos, hq⟩
/-- The fixed QPBT field model, viewed as the field model of the low
individual degree test. -/
@[reducible] noncomputable def DirectLdParams.toLDTFieldModel (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
_root_.LIDT.MIPStarRE.LDT.FieldModel D.toLDTParameters.q :=
D.model.toFieldModel
/-- Coordinate coding from the direct scalar field to the LDT carrier. -/
noncomputable def directScalarEquiv (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
_root_.MIPStarRE.QPBT.DirectScalarQ D ≃ _root_.LIDT.MIPStarRE.LDT.Fq D.toLDTParameters :=
_root_.MIPStarRE.QPBT.binaryRepresentation D.model
/-- Coordinate coding identifies direct points with LDT points, with the
coordinate order reversed: direct coordinate `j` is LDT coordinate
`Fin.rev j`. The direct game zeroes a *prefix* of a sampled diagonal
direction (`directPrefixProjection`, paper equation `eq:cl-dlnf`), whereas
the low individual degree test zeroes a *suffix*
(`extendRestrictedDirection`, `references/ldt-paper/test_definition.tex:49-65`).
Reversing the coordinate order aligns the two restriction conventions, as
required by the game
correspondence in `docs/paper-gaps/qpbt_ld-dimension-divisibility.tex`. -/
noncomputable def directPointEquiv (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
(Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) ≃ _root_.LIDT.MIPStarRE.LDT.Point D.toLDTParameters where
toFun u i := _root_.MIPStarRE.QPBT.directScalarEquiv D (u (Fin.rev i))
invFun u j := (_root_.MIPStarRE.QPBT.directScalarEquiv D).symm (u (Fin.rev j))
left_inv u := by
funext j
simp
right_inv u := by
funext i
simp
@[simp] theorem directPointEquiv_apply (D : _root_.MIPStarRE.QPBT.DirectLdParams)
(u : Fin D.m → _root_.MIPStarRE.QPBT.DirectScalarQ D) (i : Fin D.m) :
_root_.MIPStarRE.QPBT.directPointEquiv D u i = _root_.MIPStarRE.QPBT.directScalarEquiv D (u (Fin.rev i)) :=
rfl
@[simp] theorem directPointEquiv_symm_apply (D : _root_.MIPStarRE.QPBT.DirectLdParams)
(u : _root_.LIDT.MIPStarRE.LDT.Point D.toLDTParameters) (j : Fin D.m) :
(_root_.MIPStarRE.QPBT.directPointEquiv D).symm u j =
(_root_.MIPStarRE.QPBT.directScalarEquiv D).symm (u (Fin.rev j)) :=
rfl
/-! ## Bounded coefficient vectors -/
/-- Turn a coefficient vector into its polynomial of degree at most `n`. -/
noncomputable def coefficientPolynomial
{K : Type*} [Field K] (n : ℕ) (c : Fin (n + 1) → K) : Polynomial K :=
((Polynomial.degreeLTEquiv K (n + 1)).symm c).1
theorem coefficientPolynomial_degree_le
{K : Type*} [Field K] (n : ℕ) (c : Fin (n + 1) → K) :
(_root_.MIPStarRE.QPBT.coefficientPolynomial n c).natDegree ≤ n := by
let p := (Polynomial.degreeLTEquiv K (n + 1)).symm c
have hp : p.1 ∈ Polynomial.degreeLE K n := by
rw [← Polynomial.degreeLT_succ_eq_degreeLE]
exact p.2
have hdegree : p.1.degree ≤ n := Polynomial.mem_degreeLE.mp hp
by_cases hzero : p.1 = 0
· simp [_root_.MIPStarRE.QPBT.coefficientPolynomial, p, hzero]
· exact Polynomial.natDegree_le_iff_degree_le.mpr hdegree
@[simp] theorem coefficientPolynomial_coeff
{K : Type*} [Field K] (n : ℕ) (c : Fin (n + 1) → K)
(i : Fin (n + 1)) :
(_root_.MIPStarRE.QPBT.coefficientPolynomial n c).coeff i = c i := by
exact congrFun ((Polynomial.degreeLTEquiv K (n + 1)).apply_symm_apply c) i
/-- Direct axis-line coefficients are equivalent to LDT bounded axis-line
polynomials over the fixed field model. -/
noncomputable def directAxisAnswerEquiv (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
letI := D.toLDTFieldModel
_root_.MIPStarRE.QPBT.DirectDegPoly D D.d ≃ _root_.LIDT.MIPStarRE.LDT.AxisLinePolynomial D.toLDTParameters := by
letI := D.toLDTFieldModel
refine
{ toFun := fun c =>
{ poly := _root_.MIPStarRE.QPBT.coefficientPolynomial D.d c
degreeBounded := by
exact coefficientPolynomial_degree_le D.d c }
invFun := fun f i => f.poly.coeff i
left_inv := by
intro c
funext i
exact coefficientPolynomial_coeff D.d c i
right_inv := by
intro f
apply _root_.LIDT.MIPStarRE.LDT.AxisLinePolynomial.ext
apply _root_.LIDT.MIPStarRE.LDT.linePolynomial_coeff_fin_injective D.toLDTParameters
(coefficientPolynomial_degree_le D.d fun i => f.poly.coeff i)
f.degreeBounded
intro i
exact coefficientPolynomial_coeff D.d (fun j => f.poly.coeff j) i }
/-- Direct diagonal-line coefficients are equivalent to LDT bounded
diagonal-line polynomials over the fixed field model. -/
noncomputable def directDiagonalAnswerEquiv (D : _root_.MIPStarRE.QPBT.DirectLdParams) :
letI := D.toLDTFieldModel
_root_.MIPStarRE.QPBT.DirectDegPoly D (D.m * D.d) ≃ _root_.LIDT.MIPStarRE.LDT.DiagonalLinePolynomial D.toLDTParameters := by
letI := D.toLDTFieldModel
refine
{ toFun := fun c =>
{ poly := _root_.MIPStarRE.QPBT.coefficientPolynomial (D.m * D.d) c
degreeBounded := by
exact coefficientPolynomial_degree_le (D.m * D.d) c }
invFun := fun f i => f.poly.coeff i
left_inv := by
intro c
funext i
exact coefficientPolynomial_coeff (D.m * D.d) c i
right_inv := by
intro f
apply _root_.LIDT.MIPStarRE.LDT.DiagonalLinePolynomial.ext
apply _root_.LIDT.MIPStarRE.LDT.linePolynomial_coeff_fin_injective D.toLDTParameters
(coefficientPolynomial_degree_le (D.m * D.d) fun i => f.poly.coeff i)
f.degreeBounded
intro i
exact coefficientPolynomial_coeff (D.m * D.d) (fun j => f.poly.coeff j) i }
/-! ## Parameters and answers of the two QPBT game presentations -/
/-- Forget the divisibility field and expose the directly indexed parameters. -/
@[reducible] def LdParams.toDirectLdParams (L : _root_.MIPStarRE.QPBT.LdParams) : _root_.MIPStarRE.QPBT.DirectLdParams where
q := L.q
m := L.m
d := L.d
k := L.k
hm := L.hm
hd := L.hd
hk := L.hk
hq := L.hq
@[simp] theorem LdParams.toDirectLdParams_model (L : _root_.MIPStarRE.QPBT.LdParams) :
L.toDirectLdParams.model = L.model := by
unfold _root_.MIPStarRE.QPBT.DirectLdParams.model _root_.MIPStarRE.QPBT.LdParams.model _root_.MIPStarRE.QPBT.LdParams.toDirectLdParams
congr
/-- The canonical answer equivalence between the seed-indexed and directly
indexed QPBT games: point answers correspond to point answers, axis-line
answers to axis-line answers, and diagonal-line answers to diagonal-line
answers. -/
noncomputable def ldDirectAnswerEquiv (L : _root_.MIPStarRE.QPBT.LdParams) :
_root_.MIPStarRE.QPBT.LdAnswer L ≃ _root_.MIPStarRE.QPBT.DirectLdAnswer L.toDirectLdParams where
toFun
| .pointVals a => .pointVals a
| .alinePolys a => .alinePolys a
| .dlinePolys a => .dlinePolys a
invFun
| .pointVals a => .pointVals a
| .alinePolys a => .alinePolys a
| .dlinePolys a => .dlinePolys a
left_inv a := by cases a <;> rfl
right_inv a := by cases a <;> rfl
/-! ## Parsing seed-indexed questions -/
/-- Parse a seed-indexed question into the directly indexed question carrying
the coordinate selected by `chiIndex`. -/
noncomputable def parseLdQuestion (L : _root_.MIPStarRE.QPBT.LdParams) :
_root_.MIPStarRE.QPBT.LdQuestion L → _root_.MIPStarRE.QPBT.DirectLdQuestion L.toDirectLdParams
| (.point, z) =>
(.point, ⟨z.point, L.toDirectLdParams.firstIndex, 0⟩)
| (.aline, z) =>
(.aline, ⟨z.point, _root_.MIPStarRE.QPBT.chiIndex L z.seed, 0⟩)
| (.dline, z) =>
(.dline, ⟨z.point, _root_.MIPStarRE.QPBT.chiIndex L z.seed, z.direction⟩)
/-- Embed a direct sample into the seed-indexed ambient space using the
specified residue in the selected seed fiber. -/
noncomputable def ldSpaceOfDirectResidue (L : _root_.MIPStarRE.QPBT.LdParams)
(sample : _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams)
(residue : Fin (L.q / L.m)) : _root_.MIPStarRE.QPBT.LdSpace L
| .inl (.inl i) => sample.point i
| .inl (.inr _) => _root_.MIPStarRE.QPBT.seedOfIndexResidue L sample.index residue
| .inr i => sample.direction i
@[simp] theorem ldSpaceOfDirectResidue_point (L : _root_.MIPStarRE.QPBT.LdParams)
(sample : _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams)
(residue : Fin (L.q / L.m)) :
(_root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue L sample residue).point = sample.point :=
rfl
@[simp] theorem ldSpaceOfDirectResidue_seed (L : _root_.MIPStarRE.QPBT.LdParams)
(sample : _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams)
(residue : Fin (L.q / L.m)) :
(_root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue L sample residue).seed =
_root_.MIPStarRE.QPBT.seedOfIndexResidue L sample.index residue :=
rfl
@[simp] theorem ldSpaceOfDirectResidue_direction (L : _root_.MIPStarRE.QPBT.LdParams)
(sample : _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams)
(residue : Fin (L.q / L.m)) :
(_root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue L sample residue).direction = sample.direction :=
rfl
/-- The ambient seed-indexed sample space is a direct sample together with a
uniform residue in the selected seed fiber. -/
noncomputable def ldSpaceSeedFiberEquiv (L : _root_.MIPStarRE.QPBT.LdParams) :
_root_.MIPStarRE.QPBT.LdSpace L ≃ _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams × Fin (L.q / L.m) where
toFun z :=
(⟨z.point, (_root_.MIPStarRE.QPBT.seedFiberEquiv L z.seed).1, z.direction⟩,
(_root_.MIPStarRE.QPBT.seedFiberEquiv L z.seed).2)
invFun x := _root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue L x.1 x.2
left_inv z := by
funext i
rcases i with (i | i)
· rcases i with (i | i)
· rfl
· rcases i with ⟨⟩
change (_root_.MIPStarRE.QPBT.seedFiberEquiv L).symm (_root_.MIPStarRE.QPBT.seedFiberEquiv L z.seed) = z.seed
exact (_root_.MIPStarRE.QPBT.seedFiberEquiv L).symm_apply_apply z.seed
· rfl
right_inv x := by
rcases x with ⟨sample, residue⟩
apply Prod.ext
· cases sample with
| mk point index direction =>
simp only [_root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue_point,
_root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue_seed, _root_.MIPStarRE.QPBT.ldSpaceOfDirectResidue_direction]
rw [_root_.MIPStarRE.QPBT.seedFiberEquiv_seedOfIndexResidue]
· simp [_root_.MIPStarRE.QPBT.seedOfIndexResidue]
/-! ## Exact question-law transport -/
/-- The common source sample is a direct common sample together with its
uniform seed-fiber residue. -/
noncomputable def ldQuestionSeedFiberEquiv (L : _root_.MIPStarRE.QPBT.LdParams) :
((_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType) × _root_.MIPStarRE.QPBT.LdSpace L) ≃
(((_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType) × _root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams) ×
Fin (L.q / L.m)) :=
(Equiv.prodCongr (Equiv.refl (_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType))
(_root_.MIPStarRE.QPBT.ldSpaceSeedFiberEquiv L)).trans
(Equiv.prodAssoc (_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType)
(_root_.MIPStarRE.QPBT.DirectLdSpace L.toDirectLdParams) (Fin (L.q / L.m))).symm
end
end MIPStarRE.QPBT
Source