Corollary 4.2 — unique candidate iff , and recovery of
ProvedF3SubsetSum.corollary_4_2binary-error-lwecommutative-algebraf3-subset-sump2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-systemsquantum-algorithms
Let be prime, , , the ideal (27) and the candidate set (26). Then
and if , then is a basis of and
This is how the quotient decoder reads the secret off the quotient algebra.
Differences from the source:
- encoding: [1]_J is a basis of S/J → [1]_J ≠ 0 and the span of [1]_J is S/J; reason: a one-element family is a basis exactly when it is nonzero and spanning
Preamble
import Mathlib import Definitions.Def_F3SubsetSum_QuotientAlgebra
Formal statement
namespace F3SubsetSum
open MvPolynomial
/-- **Corollary 4.2** (Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, Corollary 4.2,
p.18): "There is a unique candidate s for Problem 1.5 if and only if dim(S/J) = 1. In that case,
[1]_J is a basis of S/J, and the jth coordinate of s is determined by [x_j]_J = s_j[1]_J."
For an instance `(A, b) ∈ F_q^{n×m} × F_q^m`, `q ≥ 3` prime, with `S = F_q[x_1, …, x_n]`, `J` the
ideal (27) and `𝒞` the candidate set (26): `𝒞` is a singleton iff `dim_{F_q}(S/J) = 1`; and if
`𝒞 = {s}`, then `[1]_J` is nonzero and spans `S/J`, and `[x_j]_J = s_j [1]_J` for every `j`.
**Formalization Note** "[1]_J is a basis" is stated as "`[1]_J ≠ 0` and `[1]_J` spans `S/J`". -/
theorem corollary_4_2 (q : ℕ) [Fact q.Prime] (hq : 3 ≤ q) {n m : ℕ}
(A : Matrix (Fin n) (Fin m) (ZMod q)) (b : Fin m → ZMod q) :
((∃ s, candidates A b = {s}) ↔
Module.finrank (ZMod q) (MvPolynomial (Fin n) (ZMod q) ⧸ idealJ A b) = 1) ∧
∀ s : Fin n → ZMod q, candidates A b = {s} →
Ideal.Quotient.mk (idealJ A b) 1 ≠ 0 ∧
Submodule.span (ZMod q) {Ideal.Quotient.mk (idealJ A b) 1} = ⊤ ∧
∀ j : Fin n, Ideal.Quotient.mk (idealJ A b) (X j) =
s j • Ideal.Quotient.mk (idealJ A b) 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.2, p.18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.