Fact 1.2 — existence thresholds for -Subset-Sum
ProvedF3SubsetSum.fact_1_2binary-error-lwecommutative-algebraf3-subset-sump2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-systemsquantum-algorithms
Let and consider Problem 1.1 with .
- If , every instance has a nonempty with .
- For every there is such that for all : if then, for uniform ,
and if then .
The first item is a Davenport-constant bound for ; the other two locate the satisfiability threshold at , the information-theoretic limit that Theorem 1.3 approaches.
Differences from the source:
- reading: 2^{−Ω_η(n)} → ∃ c > 0 depending only on η such that the bound 2^{−cn} holds for every n and m in the range, one c for both bullets; reason: the strongest reading of Ω_η; the proof's bounds 2^{−ηn} and 2^{1−ηn} hold for all n, and each probability is < 1 in the finitely many remaining cases
Preamble
import Mathlib import Definitions.Def_F3SubsetSum_SubsetSum
Formal statement
namespace F3SubsetSum
/-- **Fact 1.2** (Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, Fact 1.2, p.4;
proof App. A, pp.41–42): "Let κ⋆ = log(3) ≈ 1.5850 and let η > 0 be any constant. For
Problem 1.1,
• if m ≥ 2n + 1, a solution S always exists;
• if m ≥ (κ⋆ + η) · n, a solution S exists with probability at least 1 − 2^{−Ω_η(n)};
• if m ≤ (κ⋆ − η) · n, a solution S exists with probability at most 2^{−Ω_η(n)}."
**Formalization Note** `log` is base 2 (p.4), so `κ⋆ = logb 2 3`. `2^{−Ω_η(n)}` is read as: there
is `c > 0`, depending on `η` only, such that the bound `2^{−cn}` holds for every `n` and `m` in
the stated range; one `c` serves both bullets (take the smaller). The probability is over
`h₁, …, h_m` independent and uniform in `F₃ⁿ` (`probSolvable`). -/
theorem fact_1_2 :
(∀ n m : ℕ, 2 * n + 1 ≤ m → ∀ h : Fin m → Fin n → ZMod 3, HasZeroSubsetSum h) ∧
∀ η : ℝ, 0 < η → ∃ c : ℝ, 0 < c ∧ ∀ n m : ℕ,
((Real.logb 2 3 + η) * n ≤ m → 1 - (2 : ℝ) ^ (-(c * n)) ≤ probSolvable n m) ∧
((m : ℝ) ≤ (Real.logb 2 3 - η) * n → probSolvable n m ≤ (2 : ℝ) ^ (-(c * 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, Fact 1.2, p.4 (proof App. A, pp.41–42)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.