Theorem 4.20 —
ProvedF3SubsetSum.theorem_4_20binary-error-lwecommutative-algebraf3-subset-sump2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-systemsquantum-algorithms
Let be prime, , and a nonzero subspace, where is the degree- part of . Then
The symbolic rank is thus bounded below by the dimension alone; with Lemma 4.15 this gives the drift of Proposition 4.13.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_F3SubsetSum_TruncatedRing import Definitions.Def_F3SubsetSum_SymbolicRank
Formal statement
namespace F3SubsetSum
/-- **Theorem 4.20** (Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, Theorem 4.20,
p.28; proof pp.28–29): "For D ≥ 3, every nonzero subspace W ⊆ R̄*_D satisfies
ρ̄(W) ≥ (dim(W)/3)^{1−2/D}."
Here `q ≥ 3` is prime, `R̄_D` is the degree-`D` part of `F̄_q[x_1, …, x_n]/(x_1^q, …, x_n^q)` over
the algebraic closure `F̄_q` (p.26), `R̄*_D` its dual, and `ρ̄(W)` the rank of the generic
contraction `C_{L_z}|_W` over `F̄_q(z_1, …, z_n)` (eq. (46)).
**Formalization Note** The power is a real power. -/
theorem theorem_4_20 (q : ℕ) [Fact q.Prime] (hq : 3 ≤ q) (n D : ℕ) (hD : 3 ≤ D)
(W : Submodule (AlgebraicClosure (ZMod q))
(Module.Dual (AlgebraicClosure (ZMod q)) (Rd (AlgebraicClosure (ZMod q)) n q D)))
(hW : W ≠ ⊥) :
((Module.finrank (AlgebraicClosure (ZMod q)) W : ℝ) / 3) ^ (1 - 2 / (D : ℝ)) ≤
symbolicRank (AlgebraicClosure (ZMod q)) n q D W := 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.20, p.28 (proof pp.28–29)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.