Claim 4.14 — and
ProvedF3SubsetSum.claim_4_14binary-error-lwecommutative-algebraf3-subset-sump2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-systemsquantum-algorithms
Let be prime and . For a history and a new sample , let be the sample images (39), their annihilators, and the contraction by . Then
This moves the martingale step into the dual space, where it becomes a rank question.
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: ker(C_{L_t}|{W{t−1}}) as a subspace of RD → the kernel, a subspace of W{t−1}, mapped into R_D by the inclusion; reason: the paper identifies the two
Preamble
import Mathlib import Definitions.Def_F3SubsetSum_TruncatedRing import Definitions.Def_F3SubsetSum_SampleImage import Definitions.Def_F3SubsetSum_SymbolicRank
Formal statement
namespace F3SubsetSum
/-- **Claim 4.14** (Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, Claim 4.14, p.25):
"Let C_{L_t}|_{W_{t−1}} : W_{t−1} → R*_{D−2} be the restriction of C_{L_t} to W_{t−1}. Then
W_t = ker(C_{L_t}|_{W_{t−1}}) and X_t = rank(C_{L_t}|_{W_{t−1}})."
Over `F_q`, `q ≥ 3` prime, `D ≥ 2`: for a history `a_1, …, a_{t−1}` and a new sample `a_t`, with
`V_{t−1}`, `V_t` the sample images (39) and `W = V^⊥ ⊆ R*_D` their annihilators (p.24): `W_t` is
the kernel of the contraction `C_{L_t}` (p.25) restricted to `W_{t−1}`, viewed inside `R*_D`, and
the increment `X_t` (40) is the rank of that restriction.
**Formalization Note** The kernel, a subspace of `W_{t−1}`, is mapped into `R*_D` by the
inclusion. -/
theorem claim_4_14 (q : ℕ) [Fact q.Prime] (hq : 3 ≤ q) (n D : ℕ) (hD : 2 ≤ D) {t : ℕ}
(a : Fin t → Fin n → ZMod q) (a' : Fin n → ZMod q) :
(sampleImage q (Fin.snoc a a') D).dualAnnihilator =
(LinearMap.ker ((contraction (ZMod q) n q D a').domRestrict
(sampleImage q a D).dualAnnihilator)).map
(sampleImage q a D).dualAnnihilator.subtype ∧
increment q a a' D =
Module.finrank (ZMod q) (LinearMap.range ((contraction (ZMod q) n q D a').domRestrict
(sampleImage q a D).dualAnnihilator)) := 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, Claim 4.14, p.25
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.