Proof of Theorem 5.2: exact-weight polynomial in the elementary symmetric basis
ProvedMatchVec3.exact_weight_polynomiallocally-decodable-codesmatching-vector-familiesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a prime and . There are coefficients such that
has degree at most , equals on Boolean inputs of Hamming weight , and equals on Boolean inputs of every other Hamming weight. Here is the elementary symmetric polynomial of degree .
It converts the exact count of -residues into a polynomial of the indicator values.
Differences from the source:
- generalization: F_p with p from m = p^a q^b, and L > q → any prime p and any L; reason: the triangular argument uses neither
Preamble
import Mathlib
Formal statement
namespace MatchVec3
/-- **The exact-weight polynomial** (Aggarwal, Obremski, STOC 2027 submission (manuscript sha256
44199413…), proof of Theorem 5.2, p.15): for every `r ∈ {0, …, L}` there is a polynomial
`P_r(z_1, …, z_L) = ∑_{d=0}^L c_{r,d} e_d(z)` over `F_p`, of degree at most `L`, that equals `1` on
Boolean inputs of Hamming weight `r` and `0` on Boolean inputs of every other Hamming weight. -/
theorem exact_weight_polynomial {p : ℕ} (hp : p.Prime) (L r : ℕ) (hr : r ≤ L) :
∃ (c : ℕ → ZMod p) (P : MvPolynomial (Fin L) (ZMod p)),
P = ∑ d ∈ Finset.range (L + 1), MvPolynomial.C (c d) * MvPolynomial.esymm (Fin L) (ZMod p) d ∧
P.totalDegree ≤ L ∧
∀ z : Fin L → ZMod p, (∀ s, z s = 0 ∨ z s = 1) →
MvPolynomial.eval z P = if (Finset.univ.filter fun s => z s = 1).card = r then 1 else 0 := by sorry
end MatchVec3
Source
Aggarwal, Obremski, Subexponential Upper Bounds for 3-Restricted Matching Vector Families, STOC 2027 submission (manuscript sha256 44199413…), proof of Theorem 5.2, p.15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.