for an -element circuit
ProvedSaglamGV.prob_subset_kercoding-theorygilbert-varshamov-boundlinear-codesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be uniform on and let be a circuit with elements. Then, with ,
The span of has dimension , and a uniform matrix kills a fixed -dimensional subspace with probability .
Differences from the source:
- generalization: the integer m chosen in §2 with (1 − ζ)R/2 ≤ τ < (1 − ζ)R, inside the regime of §2 → every m ∈ ℕ and every n, d; reason: the identity holds for every m; it specializes to the chosen one
- encoding: Pr over M uniform on 𝔽₂^{m×n} → probM: the fraction of the 2^{mn} matrices; reason: uniform probability on a finite set; same values
Preamble
import Mathlib import Definitions.Def_SaglamGV_Code import Definitions.Def_SaglamGV_Params import Definitions.Def_SaglamGV_Circuit
Formal statement
namespace SaglamGV
open Matrix
/-- The kernel probability of a circuit (M. Saglam, *Linear codes exceeding the Gilbert–Varshamov bound*, STOC 2027 submission manuscript (held version, sha256 ac6f2bba…), §2, p.2: "Since the span of an ℓ-element circuit has
dimension ℓ − 1, Pr[S ⊆ ker M] = 2^{−m(ℓ−1)} = (τ/V)^{ℓ−1}").
For $M$ uniform on $𝔽_2^{m×n}$ and every $ℓ$-element circuit $S ⊆ B_d$,
$\Pr[S ⊆ \ker M] = 2^{−m(ℓ−1)} = (τ/V)^{ℓ−1}$ with $τ = V 2^{−m}$.
**Formalization Note** Stated for every $m$ (not only the $m$ chosen in §2); $S ⊆ \ker M$ is
$Mx = 0$ for all $x ∈ S$. -/
theorem prob_subset_ker (n d m ℓ : ℕ) (S : Finset (Fin n → ZMod 2)) (hS : S ∈ circuits n d ℓ) :
probM (fun M : Matrix (Fin m) (Fin n) (ZMod 2) => ∀ x ∈ S, M *ᵥ x = 0) =
((2 : ℝ) ^ (m * (ℓ - 1)))⁻¹ ∧
((2 : ℝ) ^ (m * (ℓ - 1)))⁻¹ = (tau n d m / (vol n d : ℝ)) ^ (ℓ - 1) := by sorry
end SaglamGV
Source
M. Saglam, Linear codes exceeding the Gilbert–Varshamov bound, STOC 2027 submission manuscript (held version, sha256 ac6f2bba913aa15cfec8dda07a8e9e37b7186e145fef4719cb623dd04d15baa3), §2, p.2 (display Pr[S ⊆ ker M] = 2^{−m(ℓ−1)} = (τ/V)^{ℓ−1})
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.