Corollary 4.18 — reduction of to shadows of monomial families
ProvedF3SubsetSum.corollary_4_18binary-error-lwecommutative-algebraf3-subset-sump2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-systemsquantum-algorithms
Let be prime, , , and a nonzero subspace. There are families , , of reduced degree- monomials such that
- ;
- ;
- for every .
The families come from splitting a -fixed monomial family (Lemma 4.17) by the exponent of ; the shadow condition is what Theorem 4.19 turns into a size bound.
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: families 𝒜_d, 0 ≤ d ≤ c → a family 𝒜 d for every d ∈ ℕ, constrained and used only for d ≤ c; reason: families with d > c play no role
Preamble
import Mathlib import Definitions.Def_F3SubsetSum_TruncatedRing import Definitions.Def_F3SubsetSum_SymbolicRank import Definitions.Def_F3SubsetSum_MonomialShadow
Formal statement
namespace F3SubsetSum
/-- **Corollary 4.18** (Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1,
Corollary 4.18, p.27; proof pp.27–28): "Define c = min{q − 1, D}. For every nonzero subspace
W ⊆ R̄*_D, there are families 𝒜_d, 0 ≤ d ≤ c of reduced degree-(D − d) monomials such that
1. dim(W) = Σ_{d=0}^c |𝒜_d|,
2. ρ̄(W) ≥ Σ_{d=2}^c |𝒜_d|,
3. ∂𝒜_d ⊆ 𝒜_{d+1} holds for every 0 ≤ d ≤ c − 1."
Over the algebraic closure `F̄_q`, `q ≥ 3` prime, `D ≥ 2` (the standing range of `D`, p.18).
Monomials are exponent vectors; a monomial is reduced when every exponent is below `q`, and its
degree is `monoDeg`. The shadow `∂` is that of p.27.
**Formalization Note** The families are indexed by all `d : ℕ`; only `0 ≤ d ≤ c` is
constrained or used. -/
theorem corollary_4_18 (q : ℕ) [Fact q.Prime] (hq : 3 ≤ q) (n D : ℕ) (hD : 2 ≤ D)
(W : Submodule (AlgebraicClosure (ZMod q))
(Module.Dual (AlgebraicClosure (ZMod q)) (Rd (AlgebraicClosure (ZMod q)) n q D)))
(hW : W ≠ ⊥) :
∃ 𝒜 : ℕ → Finset (Fin n →₀ ℕ),
(∀ d ≤ min (q - 1) D, ∀ α ∈ 𝒜 d, (∀ j, α j < q) ∧ monoDeg α = D - d) ∧
Module.finrank (AlgebraicClosure (ZMod q)) W =
∑ d ∈ Finset.range (min (q - 1) D + 1), (𝒜 d).card ∧
∑ d ∈ Finset.Icc 2 (min (q - 1) D), (𝒜 d).card ≤
symbolicRank (AlgebraicClosure (ZMod q)) n q D W ∧
∀ d < min (q - 1) D, shadow (𝒜 d) ⊆ 𝒜 (d + 1) := 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, Corollary 4.18, p.27 (proof pp.27–28)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.