Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Algebra / LowDegreeCode

Definition
QPBT_QPBT_Algebra_LowDegreeCode

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

qpbt

This bundle defines the multilinear low-degree encoding on the Boolean cube. It supplies the cube index type, the representative polynomials, the indicator vector, and the evaluation identities that characterize the encoding.

Principal definitions:

  • MIPStarRE.QPBT.Cube: indexes the Boolean cube of qudit positions.
  • MIPStarRE.QPBT.indicatorPoly: defines the representative polynomial that is one at a selected cube point and zero at the other cube points.
  • MIPStarRE.QPBT.lowDegreeEncoding: defines the multilinear low-degree encoding of a coefficient string.
  • MIPStarRE.QPBT.lowDegreeEnc: provides evaluation notation for the low-degree encoding.
  • MIPStarRE.QPBT.indicatorVec: defines the indicator vector of the Boolean cube.
  • MIPStarRE.QPBT.lowDegreeEnc_eq_dotProduct: states the dot-product identity defining the encoding through the indicator vector.
  • MIPStarRE.QPBT.indicatorVec_apply_eq_prod: gives the coordinatewise product formula for an indicator-vector entry.

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/Algebra/LowDegreeCode.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 Mathlib

namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
namespace MvPolynomial
end MvPolynomial

/-!
# The low-degree encoding

This module encodes the Boolean subcube by multilinear indicator polynomials
and packages the resulting low-degree code as honest polynomial representatives.

## References

The source-facing nodes are blueprint `def:polynomials-degree`,
`def:low-degree-encoding`, and `def:indicator-vector`; the paper origin is
`references/qpbt-paper/04_preliminaries.tex:832-897`.
The polynomial class `def:polyfunc` is reused from
`MIPStarRE.LDT.Preliminaries.polyFunc` (the LDT formalization).

Note: this module contributes declarations to the comparator statement closure
of the QPBT headline theorems, which must elaborate in the same environment as
the Mathlib-only `ChallengeQPBT.lean`.  Keep the full `import Mathlib`; do not
narrow it.  See `docs/comparator.md`, "Environment alignment".
-/

@[expose] public section

open scoped BigOperators
open MvPolynomial

namespace MIPStarRE.QPBT

/- The Boolean cube indexes the `2^m` qudits in the low-degree encoding. -/
/-- The Boolean cube indexing the `2^m` qudits of the test.  This is the index
type in blueprint
`def:low-degree-encoding`, paper origin
`references/qpbt-paper/04_preliminaries.tex:832-897`.
-/
abbrev Cube (m : ℕ) := Fin m → Bool

/--
The representative polynomial which is `1` at `y` on the Boolean cube and
zero at the other cube points.  This is the indicator polynomial in blueprint
`def:low-degree-encoding`; paper
`references/qpbt-paper/04_preliminaries.tex:832-897`.
-/
noncomputable def indicatorPoly {K : Type*} [CommRing K] {m : ℕ} (y : _root_.MIPStarRE.QPBT.Cube m) :
    MvPolynomial (Fin m) K :=
  ∏ i : Fin m, if y i then X i else (1 - X i)

/--
The multilinear low-degree encoding of a coefficient string.  Polynomial
representatives are used, as fixed by issue Dengnifer/MIPStarRE-QPBT-bak#0004, rather than
quotienting by
functional equality.  Blueprint: `def:low-degree-encoding`; paper origin:
`references/qpbt-paper/04_preliminaries.tex:832-897`.
-/
noncomputable def lowDegreeEncoding {K : Type*} [CommRing K] {m : ℕ}
    (a : _root_.MIPStarRE.QPBT.Cube m → K) : MvPolynomial (Fin m) K :=
  ∑ y : _root_.MIPStarRE.QPBT.Cube m, a y • _root_.MIPStarRE.QPBT.indicatorPoly y

/- Evaluation shorthand for the representative polynomial in
`def:low-degree-encoding`; it is Lean-only notation. -/
/-- Evaluation shorthand for the low-degree encoding.  Blueprint
`def:low-degree-encoding`, paper origin
`references/qpbt-paper/04_preliminaries.tex:832-897`.
-/
noncomputable def lowDegreeEnc {K : Type*} [CommRing K] {m : ℕ}
    (a : _root_.MIPStarRE.QPBT.Cube m → K) (x : Fin m → K) : K :=
  eval x (_root_.MIPStarRE.QPBT.lowDegreeEncoding a)

/--
The indicator vector `ind_m(x)` of `def:indicator-vector`.
Blueprint: `def:indicator-vector`; paper origin:
`references/qpbt-paper/04_preliminaries.tex:832-897`.
-/
noncomputable def indicatorVec {K : Type*} [CommRing K] {m : ℕ}
    (x : Fin m → K) : _root_.MIPStarRE.QPBT.Cube m → K :=
  fun y => eval x (_root_.MIPStarRE.QPBT.indicatorPoly y)

/--
The defining dot-product identity for the encoding, corresponding to
Equation `eq:low-degree-encoding-definition` and `def:indicator-vector` in the
blueprint, with source node `def:indicator-vector`; paper origin
`references/qpbt-paper/04_preliminaries.tex:832-897`.
-/
theorem lowDegreeEnc_eq_dotProduct {K : Type*} [CommRing K] {m : ℕ}
    (a : _root_.MIPStarRE.QPBT.Cube m → K) (x : Fin m → K) :
    _root_.MIPStarRE.QPBT.lowDegreeEnc a x = dotProduct a (_root_.MIPStarRE.QPBT.indicatorVec x) := by
  simp [_root_.MIPStarRE.QPBT.lowDegreeEnc, _root_.MIPStarRE.QPBT.lowDegreeEncoding, _root_.MIPStarRE.QPBT.indicatorVec, dotProduct]

/--
The coordinatewise product form of an entry of the indicator vector: at a cube
point `y` the entry is the product of `x i` over the coordinates with `y i`
true and of `1 - x i` over the remaining ones.  Blueprint
`def:indicator-vector`;
paper origin: `references/qpbt-paper/04_preliminaries.tex:832-897`.
-/
theorem indicatorVec_apply_eq_prod {K : Type*} [CommRing K] {m : ℕ}
    (x : Fin m → K) (y : _root_.MIPStarRE.QPBT.Cube m) :
    _root_.MIPStarRE.QPBT.indicatorVec x y = ∏ i : Fin m, if y i then x i else 1 - x i := by
  simp [_root_.MIPStarRE.QPBT.indicatorVec, _root_.MIPStarRE.QPBT.indicatorPoly, apply_ite]



end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Algebra/LowDegreeCode.lean#L34-L102

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