Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Combining / DirectLowDegree / Transport / Combining / Polynomial

Definition
QPBT_QPBT_Combining_DirectLowDegree_Transport_Combining_Polynomial

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

qpbt

This bundle defines the polynomial algebra for combining point coordinates with coefficient tuples. It separates and rebuilds combined points, forms the combined reduction polynomial, defines its substitution, and extracts each component polynomial by substituting a standard coefficient vector.

Principal definitions:

  • MIPStarRE.QPBT.combinedPointVar: point variables in the combined dimension.
  • MIPStarRE.QPBT.combinedCoefficientVar: combining variables in the combined dimension.
  • MIPStarRE.QPBT.combinedPointPart: the point component of a combined point.
  • MIPStarRE.QPBT.combinedCoefficientPart: the combining component of a combined point.
  • MIPStarRE.QPBT.combinedPoint: rebuilds a combined point from its two parts.
  • MIPStarRE.QPBT.combinePolyTuple: maps a tuple of polynomials to the combined reduction polynomial.
  • MIPStarRE.QPBT.combinedSubstitution: the substitution used by the reduction.
  • MIPStarRE.QPBT.splitCombinedPoly: extracts one component polynomial from a combined polynomial.

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/Polynomial.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

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

/-!
# The combining map on tuples of low individual degree polynomials

The extension of the quantum soundness of the low individual degree test from
simultaneity parameter `1` to a general simultaneity parameter `k` is obtained
in the source by a reduction, not coordinatewise: the `k` answer polynomials
`g_0, …, g_{k-1}` in `m` variables are combined into the single polynomial

`comb(g)(u, α) = ∑_{r < k} α_r g_r(u)`

in `m + k` variables, the case `k = 1` is applied once in dimension `m + k`,
and the `k` polynomials are recovered from the resulting outcome by exact
linearity in the combining variables `α` together with the Schwartz--Zippel
lemma.  This module develops the polynomial algebra of that combining map: the
coordinate split of `Fin (m + k)`, the map itself, its evaluation identity, its
individual-degree bound, and the substitution recovering the `r`-th component,
which exhibits the map as injective.

The combining map of `def:combine-map` (`MIPStarRE/QPBT/Combining/Defs.lean`)
is the special case of two components used by the Chapter 15 combining
argument, written there in the fixed coordinate layout of that chapter; the
present map is the general `k`-component form required by the reduction, in the
coordinate layout of the directly indexed low-degree game, where the `m` point
coordinates precede the `k` combining coordinates.

## Main definitions

* `combinedPointVar`, `combinedCoefficientVar` — the two coordinate blocks of
  the combined dimension `m + k`.
* `combinePolyTuple` — the combining map on tuples of polynomials.
* `splitCombinedPoly` — the substitution `α ↦ e_r` recovering the `r`-th
  component of a combined polynomial.

## References

* `references/neexp-paper/05_quantum_preliminaries.tex:1409-1503`
  (the derivation of Theorem 4.43 from Theorem 4.40)
* `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.Preliminaries

noncomputable section

/-! ## The coordinates of the combined dimension -/

/-- The point coordinates of the combined dimension `m + k`.  The `m` point
coordinates come first, so that zeroing a prefix of a direction of the combined
space restricts to zeroing the corresponding prefix of its point part. -/
def combinedPointVar (m k : ℕ) (j : Fin m) : Fin (m + k) :=
  finSumFinEquiv (Sum.inl j)

/-- The combining coordinates of the combined dimension `m + k`.  Coordinate
`combinedCoefficientVar m k r` carries the scalar `α_r` multiplying the `r`-th
component of a polynomial tuple. -/
def combinedCoefficientVar (m k : ℕ) (r : Fin k) : Fin (m + k) :=
  finSumFinEquiv (Sum.inr r)

theorem combinedPointVar_injective (m k : ℕ) :
    Function.Injective (_root_.MIPStarRE.QPBT.combinedPointVar m k) := by
  intro j j' h
  simpa using finSumFinEquiv.injective h

theorem combinedCoefficientVar_injective (m k : ℕ) :
    Function.Injective (_root_.MIPStarRE.QPBT.combinedCoefficientVar m k) := by
  intro r r' h
  simpa using finSumFinEquiv.injective h

/-- The two coordinate blocks of the combined dimension are disjoint. -/
theorem combinedCoefficientVar_ne_combinedPointVar (m k : ℕ) (r : Fin k) (j : Fin m) :
    _root_.MIPStarRE.QPBT.combinedCoefficientVar m k r ≠ _root_.MIPStarRE.QPBT.combinedPointVar m k j := by
  intro h
  have := finSumFinEquiv.injective h
  simp at this

theorem combinedCoefficientVar_notMem_range (m k : ℕ) (r : Fin k) :
    _root_.MIPStarRE.QPBT.combinedCoefficientVar m k r ∉ Set.range (_root_.MIPStarRE.QPBT.combinedPointVar m k) := by
  rintro ⟨j, hj⟩
  exact _root_.MIPStarRE.QPBT.combinedCoefficientVar_ne_combinedPointVar m k r j hj.symm

/-- The point part of a point of the combined space. -/
def combinedPointPart {K : Type*} {m k : ℕ} (z : Fin (m + k) → K) : Fin m → K :=
  fun j => z (_root_.MIPStarRE.QPBT.combinedPointVar m k j)

/-- The combining part of a point of the combined space. -/
def combinedCoefficientPart {K : Type*} {m k : ℕ} (z : Fin (m + k) → K) : Fin k → K :=
  fun r => z (_root_.MIPStarRE.QPBT.combinedCoefficientVar m k r)

/-- The point of the combined space with the given point and combining parts. -/
def combinedPoint {K : Type*} {m k : ℕ} (u : Fin m → K) (α : Fin k → K) :
    Fin (m + k) → K :=
  fun i => Sum.elim u α (finSumFinEquiv.symm i)

@[simp] theorem combinedPointPart_combinedPoint {K : Type*} {m k : ℕ}
    (u : Fin m → K) (α : Fin k → K) :
    _root_.MIPStarRE.QPBT.combinedPointPart (_root_.MIPStarRE.QPBT.combinedPoint u α) = u := by
  funext j
  simp [_root_.MIPStarRE.QPBT.combinedPointPart, _root_.MIPStarRE.QPBT.combinedPoint, _root_.MIPStarRE.QPBT.combinedPointVar]

@[simp] theorem combinedCoefficientPart_combinedPoint {K : Type*} {m k : ℕ}
    (u : Fin m → K) (α : Fin k → K) :
    _root_.MIPStarRE.QPBT.combinedCoefficientPart (_root_.MIPStarRE.QPBT.combinedPoint u α) = α := by
  funext r
  simp [_root_.MIPStarRE.QPBT.combinedCoefficientPart, _root_.MIPStarRE.QPBT.combinedPoint, _root_.MIPStarRE.QPBT.combinedCoefficientVar]

/-! ## The combining map -/

/-- The combining map of the reduction: the tuple `g` is sent to the polynomial
`(u, α) ↦ ∑_{r < k} α_r g_r(u)` in `m + k` variables.

Source `references/neexp-paper/05_quantum_preliminaries.tex:1425-1435`. -/
def combinePolyTuple {K : Type*} [CommSemiring K] {m k : ℕ}
    (g : Fin k → MvPolynomial (Fin m) K) : MvPolynomial (Fin (m + k)) K :=
  ∑ r : Fin k, MvPolynomial.X (_root_.MIPStarRE.QPBT.combinedCoefficientVar m k r) *
    MvPolynomial.rename (_root_.MIPStarRE.QPBT.combinedPointVar m k) (g r)





/-! ## Recovering the components -/

/-- The substitution sending each point coordinate to its own variable and the
combining coordinates to the `r`-th standard basis vector.  Applied to a
combined polynomial it returns the `r`-th component of the tuple. -/
def combinedSubstitution (K : Type*) [CommSemiring K] (m k : ℕ) (r : Fin k) :
    Fin (m + k) → MvPolynomial (Fin m) K :=
  fun i => Sum.elim (fun j : Fin m => MvPolynomial.X j)
    (fun s : Fin k => if s = r then 1 else 0) (finSumFinEquiv.symm i)

@[simp] theorem combinedSubstitution_point (K : Type*) [CommSemiring K] (m k : ℕ)
    (r : Fin k) (j : Fin m) :
    _root_.MIPStarRE.QPBT.combinedSubstitution K m k r (_root_.MIPStarRE.QPBT.combinedPointVar m k j) = MvPolynomial.X j := by
  simp [_root_.MIPStarRE.QPBT.combinedSubstitution, _root_.MIPStarRE.QPBT.combinedPointVar]

@[simp] theorem combinedSubstitution_coefficient (K : Type*) [CommSemiring K] (m k : ℕ)
    (r s : Fin k) :
    _root_.MIPStarRE.QPBT.combinedSubstitution K m k r (_root_.MIPStarRE.QPBT.combinedCoefficientVar m k s) =
      if s = r then 1 else 0 := by
  simp [_root_.MIPStarRE.QPBT.combinedSubstitution, _root_.MIPStarRE.QPBT.combinedCoefficientVar]

/-- The `r`-th component of a polynomial in the combined variables: substitute
the `r`-th standard basis vector for the combining variables. -/
def splitCombinedPoly {K : Type*} [CommSemiring K] {m k : ℕ}
    (p : MvPolynomial (Fin (m + k)) K) (r : Fin k) : MvPolynomial (Fin m) K :=
  MvPolynomial.aeval (_root_.MIPStarRE.QPBT.combinedSubstitution K m k r) p

/-- The components of a combined polynomial are the polynomials it combines. -/
theorem splitCombinedPoly_combinePolyTuple {K : Type*} [CommSemiring K] {m k : ℕ}
    (g : Fin k → MvPolynomial (Fin m) K) (r : Fin k) :
    _root_.MIPStarRE.QPBT.splitCombinedPoly (_root_.MIPStarRE.QPBT.combinePolyTuple g) r = g r := by
  classical
  have hcomp : (_root_.MIPStarRE.QPBT.combinedSubstitution K m k r) ∘ (_root_.MIPStarRE.QPBT.combinedPointVar m k) =
      (MvPolynomial.X : Fin m → MvPolynomial (Fin m) K) := by
    funext j
    exact _root_.MIPStarRE.QPBT.combinedSubstitution_point K m k r j
  have hterm : ∀ s : Fin k,
      MvPolynomial.aeval (_root_.MIPStarRE.QPBT.combinedSubstitution K m k r)
          (MvPolynomial.X (_root_.MIPStarRE.QPBT.combinedCoefficientVar m k s) *
            MvPolynomial.rename (_root_.MIPStarRE.QPBT.combinedPointVar m k) (g s)) =
        (if s = r then 1 else 0) * g s := by
    intro s
    rw [map_mul, MvPolynomial.aeval_X, _root_.MIPStarRE.QPBT.combinedSubstitution_coefficient,
      MvPolynomial.aeval_rename, hcomp, MvPolynomial.aeval_X_left_apply]
  rw [_root_.MIPStarRE.QPBT.splitCombinedPoly, _root_.MIPStarRE.QPBT.combinePolyTuple, map_sum]
  simp only [hterm, ite_mul, one_mul, zero_mul]
  simp

/-- The combining map is injective: the components of a combined polynomial are
determined by it. -/
theorem combinePolyTuple_injective {K : Type*} [CommSemiring K] {m k : ℕ} :
    Function.Injective (_root_.MIPStarRE.QPBT.combinePolyTuple (K := K) (m := m) (k := k)) := by
  intro g g' h
  funext r
  rw [← _root_.MIPStarRE.QPBT.splitCombinedPoly_combinePolyTuple g r, h,
    _root_.MIPStarRE.QPBT.splitCombinedPoly_combinePolyTuple]

/-! ## The individual-degree bound -/

/-- Membership in the low individual degree class from a bound on every
individual degree.  This is the converse direction of
`degreeOf_le_of_mem_polyFunc`. -/
theorem mem_polyFunc_of_degreeOf_le {m d : ℕ} {K : Type*} [CommSemiring K]
    {p : MvPolynomial (Fin m) K} (h : ∀ i, p.degreeOf i ≤ d) :
    p ∈ _root_.LIDT.MIPStarRE.LDT.Preliminaries.polyFunc m K d := by
  rw [MvPolynomial.mem_restrictDegree]
  exact fun s hs i => MvPolynomial.degreeOf_le_iff.mp (h i) s hs

private theorem degreeOf_X_le_one {τ K : Type*} [CommSemiring K] (c i : τ) :
    (MvPolynomial.X c : MvPolynomial τ K).degreeOf i ≤ 1 := by
  rw [MvPolynomial.degreeOf_le_iff]
  intro s hs
  have hs' : s ∈ ({Finsupp.single c 1} : Finset (τ →₀ ℕ)) :=
    MvPolynomial.support_monomial_subset hs
  rw [Finset.mem_singleton] at hs'
  subst hs'
  by_cases h : c = i
  · simp [h]
  · simp [h]

private theorem degreeOf_rename_le {σ τ K : Type*} [CommSemiring K]
    {f : σ → τ} (hf : Function.Injective f) {p : MvPolynomial σ K} {d : ℕ}
    (hp : ∀ j : σ, p.degreeOf j ≤ d) (i : τ) :
    (MvPolynomial.rename f p).degreeOf i ≤ d := by
  classical
  rw [MvPolynomial.degreeOf_le_iff]
  intro s hs
  rw [MvPolynomial.support_rename_of_injective hf] at hs
  obtain ⟨t, ht, rfl⟩ := Finset.mem_image.mp hs
  by_cases hi : ∃ j, f j = i
  · obtain ⟨j, rfl⟩ := hi
    rw [Finsupp.mapDomain_apply hf]
    exact le_trans (MvPolynomial.le_degreeOf_of_mem_support j ht) (hp j)
  · rw [Finsupp.mapDomain_of_notMem_range t i (by simpa using hi)]
    exact Nat.zero_le d

private theorem degreeOf_rename_eq_zero_of_notMem_range {σ τ K : Type*} [CommSemiring K]
    {f : σ → τ} (hf : Function.Injective f) (p : MvPolynomial σ K)
    {i : τ} (hi : i ∉ Set.range f) :
    (MvPolynomial.rename f p).degreeOf i = 0 := by
  classical
  rw [← Nat.le_zero, MvPolynomial.degreeOf_le_iff]
  intro s hs
  rw [MvPolynomial.support_rename_of_injective hf] at hs
  obtain ⟨t, _, rfl⟩ := Finset.mem_image.mp hs
  exact le_of_eq (Finsupp.mapDomain_of_notMem_range t i hi)

/-- The combining map preserves the individual-degree bound.  The two coordinate
blocks are disjoint: a component polynomial depends only on the point
coordinates, so multiplying it by a combining variable leaves its individual
degrees in the point block unchanged and produces individual degree one in the
fresh combining coordinate.  The hypothesis `1 ≤ d` supplies exactly the bound
needed on that fresh coordinate; no bound `d + 1` is introduced.  This is the
individual-degree counterpart of the degree-`d + 1` bound used for total degree
in `references/neexp-paper/05_quantum_preliminaries.tex:1435-1440`. -/
theorem combinePolyTuple_mem_polyFunc {K : Type*} [CommSemiring K] {m k d : ℕ}
    (hd : 1 ≤ d) (g : Fin k → MvPolynomial (Fin m) K)
    (hg : ∀ r, g r ∈ _root_.LIDT.MIPStarRE.LDT.Preliminaries.polyFunc m K d) :
    _root_.MIPStarRE.QPBT.combinePolyTuple g ∈ _root_.LIDT.MIPStarRE.LDT.Preliminaries.polyFunc (m + k) K d := by
  classical
  refine Submodule.sum_mem _ fun r _ => _root_.MIPStarRE.QPBT.mem_polyFunc_of_degreeOf_le fun i => ?_
  refine le_trans (MvPolynomial.degreeOf_mul_le i _ _) ?_
  by_cases hi : i ∈ Set.range (_root_.MIPStarRE.QPBT.combinedPointVar m k)
  · have hne : i ≠ _root_.MIPStarRE.QPBT.combinedCoefficientVar m k r := by
      rintro rfl
      exact _root_.MIPStarRE.QPBT.combinedCoefficientVar_notMem_range m k r hi
    rw [MvPolynomial.degreeOf_X_of_ne hne, zero_add]
    exact degreeOf_rename_le (_root_.MIPStarRE.QPBT.combinedPointVar_injective m k)
      (fun j => _root_.LIDT.MIPStarRE.LDT.Preliminaries.degreeOf_le_of_mem_polyFunc (hg r) j) i
  · rw [degreeOf_rename_eq_zero_of_notMem_range (_root_.MIPStarRE.QPBT.combinedPointVar_injective m k) _ hi,
      add_zero]
    exact le_trans (degreeOf_X_le_one _ _) hd

end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Combining/DirectLowDegree/Transport/Combining/Polynomial.lean#L59-L278

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