Theorem 4.19 — multiset shadow bound
ProvedF3SubsetSum.theorem_4_19binary-error-lwecommutative-algebraf3-subset-sump2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-systemsquantum-algorithms
Let and let be a family of degree- monomials in (exponents unrestricted). Then
This is a consequence of the multiset analogue of Lovász's form of the Kruskal–Katona theorem [BBCH03], and it is the combinatorial input of Theorem 4.20.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_F3SubsetSum_MonomialShadow
Formal statement
namespace F3SubsetSum
/-- **Theorem 4.19** (Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, Theorem 4.19,
p.28): "Let 𝒜 be a family of degree-r monomials where r ≥ 2. Then |∂𝒜| ≥ |𝒜|^{1−1/r}."
Monomials in `x_1, …, x_n` are exponent vectors (multisets over `[n]`, exponents unrestricted);
`∂` is the shadow of p.27. The family may be empty.
**Formalization Note** The power is a real power. -/
theorem theorem_4_19 (n r : ℕ) (hr : 2 ≤ r) (𝒜 : Finset (Fin n →₀ ℕ))
(h𝒜 : ∀ α ∈ 𝒜, monoDeg α = r) :
(𝒜.card : ℝ) ^ (1 - 1 / (r : ℝ)) ≤ (shadow 𝒜).card := 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, Theorem 4.19, p.28
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.