Lemma 4.15 —
ProvedF3SubsetSum.lemma_4_15binary-error-lwecommutative-algebraf3-subset-sump2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-systemsquantum-algorithms
Let be prime and . For every history , with and a uniformly random new linear form ,
where is the symbolic rank (43). The symbolic rank is an upper bound for every specialised rank; this lemma says that a random specialisation keeps a third of it on average.
Differences from the source:
- encoding: the standing integer D ≥ 2 of §4.1 (eq. (29), p.18), left implicit in the statement → hypothesis D ≥ 2; reason: R_{D−2} is undefined for D < 2 (natural-number subtraction would make it R_0)
- encoding: E[X_t | W_{t−1}] → the average over the uniform new sample a_t for a fixed history; reason: X_t depends on the history only through W_{t−1} (Claim 4.14), so both conditionings give the same average
Preamble
import Mathlib import Definitions.Def_F3SubsetSum_TruncatedRing import Definitions.Def_F3SubsetSum_SampleImage import Definitions.Def_F3SubsetSum_SymbolicRank
Formal statement
namespace F3SubsetSum
/-- **Lemma 4.15** (Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, Lemma 4.15, p.25):
"For uniformly random L_t, we have E[X_t | W_{t−1}] ≥ ρ(W_{t−1})/3."
Over `F_q`, `q ≥ 3` prime, `D ≥ 2`: for every history `a_1, …, a_{t−1}`, the average over a
uniform new sample `a_t ∈ F_qⁿ` of the increment `X_t` (40) is at least one third of the symbolic
rank `ρ(W_{t−1})` (43), where `W_{t−1} = V_{t−1}^⊥ ⊆ R*_D`.
**Formalization Note** `X_t` depends on the history only through `W_{t−1}` (Claim 4.14), so
conditioning on `W_{t−1}` and conditioning on the history give the same average. -/
theorem lemma_4_15 (q : ℕ) [Fact q.Prime] (hq : 3 ≤ q) (n D : ℕ) (hD : 2 ≤ D) {t : ℕ}
(a : Fin t → Fin n → ZMod q) :
(symbolicRank (ZMod q) n q D (sampleImage q a D).dualAnnihilator : ℝ) / 3 ≤
(∑ a' : Fin n → ZMod q, (increment q a a' D : ℝ)) / (q : ℝ) ^ n := 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, Lemma 4.15, p.25
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.