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.dist_implies_correctable← dist_implies_correctable (TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:393): verbatim
- 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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.-/