Composite weight detector: degree and Boolean separation
ProvedCatalyticTreeEval.Main.composite_weight_detector_propertiescatalytic-computationmatching-vectors
Let be distinct primes, nonnegative integers, , and . For , the CRT combination of the explicit prime-power detectors is multilinear of degree at most . For Boolean of weight at most , its value is zero at weight ; at every smaller weight it is a nonzero canonical residue (each prime projection is zero or one).
This establishes the algebraic part of Corollary B.6 for a fixed polynomial construction; its uniform sparse printer is a separate computational obligation.
Preamble
import Definitions.Def_CatalyticTreeEval_CompositeDetector set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main
theorem composite_weight_detector_properties {t : ℕ} (p e : Fin t → ℕ)
(hp : PrimeData p) (w H : ℕ) (hw : w < ∏ i, p i ^ e i) :
Multilinear (compositeWeightDetector p e hp w H) ∧
(compositeWeightDetector p e hp w H).totalDegree ≤ delta p e - 1 ∧
(∀ x : Fin H → Bool, weight x ≤ w →
(weight x = w → MvPolynomial.eval (boolPoint x) (compositeWeightDetector p e hp w H) = 0) ∧
(weight x < w → MvPolynomial.eval (boolPoint x) (compositeWeightDetector p e hp w H) ∈
canonical p (modulus p) ∧
MvPolynomial.eval (boolPoint x) (compositeWeightDetector p e hp w H) ≠ 0)) := by sorry
end CatalyticTreeEval.MainSource
Henzinger, Pyne and Ragavan, Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/html/2602.14320v3, Appendix B, Corollary B.6.