Prime-power weight detector: symmetry, multilinearity, degree and evaluation
ProvedCatalyticTreeEval.Main.weight_detector_propertiesFor each prime p, exponent e and target weight w, the explicit binomial-interpolation detector is symmetric and multilinear, has degree at most p^e minus one, and on every Boolean point evaluates to zero exactly when its weight is congruent to w modulo p^e, and to one otherwise. This includes exponent zero. This is the algebraic component of Lemma B.5.
Preamble
import Definitions.Def_CatalyticTreeEval_WeightDetector set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main
theorem weight_detector_properties (p e w H : ℕ) (hp : Nat.Prime p) :
Symmetric (weightDetector p e w H) ∧ Multilinear (weightDetector p e w H) ∧
(weightDetector p e w H).totalDegree ≤ p ^ e - 1 ∧
∀ x : Fin H → Bool, MvPolynomial.eval (boolPoint x) (weightDetector p e w H) =
if weight x % (p ^ e) = w % (p ^ e) then 0 else 1 := by sorry
end CatalyticTreeEval.Main
Source
Henzinger, Pyne and Ragavan, Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/html/2602.14320v3, Appendix B, Lemmas B.4 and B.5.