AFTD Auto-Formalizing Theoretical Domains

dist_implies_correctable

theoremverifiedimported Lean

Erasure correction below the code distance. Let $p$ be prime and let $S$ be an $\mathbb{F}_p$-subspace of the symplectic space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$, with code distance $d(S)$ and symplectic orthogonal complement $S^{\perp_\omega}$. If $E \subseteq \{0,\dots,n-1\}$ is a set of erased coordinates with $|E| < d(S)$, then $E$ is correctable for $S$: every $v \in V_E \cap S^{\perp_\omega}$ already lies in $S$.

Statement

open scoped BigOperators in
set_option linter.mathlibStandardSet false in
open scoped BigOperators in
open scoped Real in
open scoped Nat in
open Classical in
open scoped Pointwise in
set_option maxRecDepth 4000 in
set_option synthInstance.maxHeartbeats 20000 in
set_option synthInstance.maxSize 128 in
set_option relaxedAutoImplicit false in
set_option autoImplicit false in
set_option linter.unnecessarySimpa false in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
lemma dist_implies_correctable (S : Submodule (F p) (V n p)) (E : Finset (Fin n))
    (h : E.card < code_dist S) : correctable S E
Source
TCSlib, `dist_implies_correctable`
Lean proof
By Allan Li, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • sym_orthFor a submodule $S \le V$, $S^{\perp_\omega} = \{v \in V \mid \forall s \in S,\; \omega(v,s) = 0\}$.
  • suppThe support $\mathrm{supp}(v) \subseteq \mathrm{Fin}\,n$ consists of coordinates where either component of $v$ is nonzero; the…
  • V_subFor $C \subseteq \mathrm{Fin}\,n$, the support submodule $V_C = \{v \in V \mid \mathrm{supp}(v) \subseteq C\}$.
  • wtThe support $\mathrm{supp}(v) \subseteq \mathrm{Fin}\,n$ consists of coordinates where either component of $v$ is nonzero; the…
  • VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
  • correctableAn erasure set $E \subseteq \mathrm{Fin}\,n$ is correctable for $S$ if every $v \in V_E \cap S^{\perp_\omega}$ is already in $S$.
  • code_dist$d(S) = \min\{\mathrm{wt}(v) \mid v \in S^{\perp_\omega} \setminus S,\; \mathrm{wt}(v) \neq 0\}$ (or $0$ if no such $v$ exists).
  • FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via ZMod.
Used by 1
  • quantum_singleton_boundLet $p$ be prime and work in the symplectic space $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$ equipped with the form $\omega$. If $S \le V$ is…

Lean source view module on GitHub

open scoped BigOperators inset_option linter.mathlibStandardSet false inopen scoped BigOperators inopen scoped Real inopen scoped Nat inopen Classical inopen scoped Pointwise inset_option maxRecDepth 4000 inset_option synthInstance.maxHeartbeats 20000 inset_option synthInstance.maxSize 128 inset_option relaxedAutoImplicit false inset_option autoImplicit false inset_option linter.unnecessarySimpa false invariable {n : ℕ} {p : ℕ} [Fact p.Prime] invariable {n : ℕ} {p : ℕ} [Fact p.Prime] invariable {n : ℕ} {p : ℕ} [Fact p.Prime] invariable {n : ℕ} {p : ℕ} [Fact p.Prime] invariable {n : ℕ} {p : ℕ} [Fact p.Prime] invariable {n : ℕ} {p : ℕ} [Fact p.Prime] invariable {n : ℕ} {p : ℕ} [Fact p.Prime] in/-- An erasure set `E` is correctable whenever its size is strictly less than the code distance. -/lemma dist_implies_correctable (S : Submodule (F p) (V n p)) (E : Finset (Fin n))    (h : E.card < code_dist S) : correctable S E := by      intro v hv;      have h_weight : ∀ v ∈ sym_orth S ⊓ V_sub E, v∉ S → code_dist S ≤ wt v := by        exact fun v hv hv' => Nat.sInf_le ⟨ v, hv.1, hv', rfl ⟩;      have h_weight_le : ∀ v ∈ sym_orth S ⊓ V_sub E, v∉ S → wt v ≤ E.card := by        intros v hv hv_not_in_S        have h_support_subset : supp v ⊆ E := by          exact fun i hi => Classical.not_not.1 fun hi' => by have := hv.2 i hi'; unfold supp at hi; simp_all only [Submodule.mem_inf,            LinearMap.BilinForm.mem_orthogonal_iff, Prod.forall, and_imp, ne_eq, Set.toFinset_setOf,            Finset.mem_filter, Finset.mem_univ, not_true_eq_false, or_self, and_false];        exact Finset.card_le_card h_support_subset;      exact Classical.not_not.1 fun hv' => not_lt_of_ge ( h_weight v hv hv' ) ( lt_of_le_of_lt ( h_weight_le v hv hv' ) h )/-Definition of g(M) with intermediate steps.-/
See it in the graphDiscuss this resultChallenge it