Theorem 5.38 — finite-type one-dimensional local central limit theorem
OpenTwoFoldOPI.Supplement.theorem_5_38coding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
Fix distributions on and weights with ; let and be the mean and standard deviation of . Let grow and let satisfy and . Let for independent . Assume:
- some has positive variance;
- every has finite third absolute moment;
- the additive subgroup generated by is .
Then, uniformly over ,
This local limit theorem gives the point probabilities of histogram counts needed for the stability estimate of load sets (Theorem 10.11).
Differences from the source:
- encoding: n_r = α_r n + O(1), n grows, error O(1/n) uniformly over z → for every bound b on |n_r − α_r n| there are C and n₀ such that the error is at most C/n for all n ≥ n₀, all admissible (n_r) and all z; reason: explicit quantifiers for the asymptotic notation; the constant depends on the D_r, the α_r and b only
- encoding: Z = Σ_r Σ_{i ≤ n_r} Z_{r,i} with independent Z_{r,i} ∼ D_r → the law of Z is the iterated convolution of n_r copies of D_r for each r; reason: Lean representation of the law of a sum of independent variables
Preamble
import Mathlib import Definitions.Def_TwoFoldOPI_Supplement_pmfMean import Definitions.Def_TwoFoldOPI_Supplement_pmfVar import Definitions.Def_TwoFoldOPI_Supplement_sumLaw
Formal statement
namespace TwoFoldOPI
namespace Supplement
/-- **Theorem 5.38 (finite-type one-dimensional local central limit theorem).**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §5.4, Theorem 5.38, p.34: "Fix some distributions D_1, …, D_R supported on Z and scalars
α_1, …, α_R ∈ R_{>0} summing to 1. For r ∈ [R], let µ_r, σ_r be the mean and standard deviation of
D_r. Let n grow, and let n_1, …, n_R be such that n_r = α_r n + O(1) for all r and Σ_r n_r = n. Let
{Z_{r,i} : r ∈ [R], i ∈ [n_r]} be n independent random variables with Z_{r,i} ∼ D_r for all i. Let
Z = Σ_{r∈[R]} Σ_{i∈[n_r]} Z_{r,i}. Assume all of the following: • There exists r ∈ [R] such that
Var[D_r] > 0; • every D_r has finite third absolute moment; and • the additive subgroup generated
by ⋃_{r∈[R]}(supp(D_r) − supp(D_r)) is Z. Then for any z ∈ Z, we have the following bound uniformly
over z: |Pr[Z = z] − (1/√(2π Σ_r n_r σ_r²)) exp(−(z − Σ_r n_r µ_r)² / (2 Σ_r n_r σ_r²))| = O(1/n)."
For distributions `D_r` on `ℤ` and weights `α_r > 0` with `Σ α_r = 1`, under the three
assumptions, and for every bound `b` on `|n_r − α_r n|`, there are `C` and `n₀` such that for
all `n ≥ n₀`, all `n_1, …, n_R` with `|n_r − α_r n| ≤ b` and `Σ n_r = n`, and all `z ∈ ℤ`:
`|Pr[Z = z] − (2πV)^{−1/2} exp(−(z − µ)²/(2V))| ≤ C/n`, where `V = Σ n_r σ_r²`,
`µ = Σ n_r µ_r`, and `Z` is the sum of independent `Z_{r,i} ∼ D_r` (`n_r` copies of each `r`).
**Formalization Note.** `n_r = α_r n + O(1)` is one bound `b` chosen before `C`; "Let n grow" and
`O(1/n)` are `∃ C, ∃ n₀, ∀ n ≥ n₀`. `C` may depend on the `D_r`, the `α_r` and `b`, and is
uniform over `n`, the `n_r` and `z`. The law of `Z` is the convolution `sumLaw` of the list
holding `n_r` copies of `D_r` for each `r`. "Finite third absolute moment" is summability of
`|z|³ D_r(z)`; supports may be infinite. `σ_r² = pmfVar D_r`. The support of `D_r` is the set of
`z` with `D_r(z) ≠ 0`. -/
theorem theorem_5_38 {R : ℕ} (D : Fin R → PMF ℤ) (α : Fin R → ℝ) (hα : ∀ r, 0 < α r)
(hsum : ∑ r, α r = 1) (hvar : ∃ r, 0 < pmfVar (D r))
(hmom : ∀ r, Summable fun z : ℤ => |(z : ℝ)| ^ 3 * (D r z).toReal)
(hgen : AddSubgroup.closure
(⋃ r, {d : ℤ | ∃ a ∈ (D r).support, ∃ a' ∈ (D r).support, d = a - a'}) = ⊤)
(b : ℝ) :
∃ C : ℝ, ∃ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n → ∀ ns : Fin R → ℕ,
(∀ r, |(ns r : ℝ) - α r * n| ≤ b) → ∑ r, ns r = n → ∀ z : ℤ,
|(sumLaw ((List.finRange R).flatMap fun r => List.replicate (ns r) (D r)) z).toReal -
1 / Real.sqrt (2 * Real.pi * ∑ r, (ns r : ℝ) * pmfVar (D r)) *
Real.exp (-((z : ℝ) - ∑ r, (ns r : ℝ) * pmfMean (D r)) ^ 2 /
(2 * ∑ r, (ns r : ℝ) * pmfVar (D r)))| ≤ C / n := by sorry
end Supplement
end TwoFoldOPI
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §5.4, Theorem 5.38, p. 34