Eq. (44), [DKSS13] — multiplicity Schwartz–Zippel:
ProvedF3SubsetSum.dkss13_multiplicity_schwartz_zippelbinary-error-lwecommutative-algebraf3-subset-sump2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-systemsquantum-algorithms
Let be prime and nonzero. For uniform in ,
where is the least total degree of a nonzero monomial of and is the total degree. This is the lemma of Dvir, Kopparty, Saraf and Sudan (2013), cited in the proof of Lemma 4.15 and applied there to a nonzero minor of the generic contraction.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_F3SubsetSum_RootMultiplicity
Formal statement
namespace F3SubsetSum
/-- **The multiplicity Schwartz–Zippel lemma [DKSS13]** as used in the proof of Lemma 4.15
(Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, proof of Lemma 4.15, eq. (44),
p.25): "For an n-variate nonzero polynomial p(z) over the base field F_q and a ∈ F_q^n, we use
mult_a(p(z)) to denote the multiplicity of the root z = a. … The multiplicity Schwartz-Zippel
lemma [DKSS13] gives E_a[mult_a(p(z))] ≤ deg(p)/q."
For `q ≥ 3` prime (as in Problem 1.5) and every nonzero `p ∈ F_q[z_1, …, z_n]`, the average of
`mult_a(p)` over `a ∈ F_qⁿ` is at most `deg(p)/q`, where `deg` is the total degree.
**Formalization Note** A cited result (Dvir, Kopparty, Saraf, Sudan 2013), not proved in the
paper. -/
theorem dkss13_multiplicity_schwartz_zippel (q : ℕ) [Fact q.Prime] (hq : 3 ≤ q) (n : ℕ)
(p : MvPolynomial (Fin n) (ZMod q)) (hp : p ≠ 0) :
(∑ a : Fin n → ZMod q, (rootMult a p : ℝ)) / (q : ℝ) ^ n ≤ (p.totalDegree : ℝ) / q := by sorry
end F3SubsetSum
Source
Kothari, Metger, O'Donnell, Shutty, Wu, Exponential quantum speedup for F_3^n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE, arXiv:2609.40321v1, proof of Lemma 4.15, eq. (44), p.25 (cited: Dvir, Kopparty, Saraf, Sudan 2013)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.