code_dist_eq_zero_of_code_k_eq_zero
theoremverifiedimported Lean
Zero logical dimension forces zero distance. Let $p$ be a prime and let $S$ be a subspace of the symplectic space $V = \bbf_p^n \times \bbf_p^n$. If $S$ is isotropic and its logical dimension vanishes, $k(S) = 0$, then the code distance vanishes as well, $d(S) = 0$.
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 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 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 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 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 variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in lemma code_dist_eq_zero_of_code_k_eq_zero (S : Submodule (F p) (V n p)) (hS : IsIsotropic (n:=n) (p:=p) S) (hk : code_k (n:=n) (p:=p) S = 0) : code_dist (n:=n) (p:=p) S = 0
- Source
- TCSlib, `code_dist_eq_zero_of_code_k_eq_zero`
- 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.code_dist_eq_zero_of_code_k_eq_zero← code_dist_eq_zero_of_code_k_eq_zero (TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:1159): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- sym_orthFor a submodule $S \le V$, $S^{\perp_\omega} = \{v \in V \mid \forall s \in S,\; \omega(v,s) = 0\}$.
- finrank_sym_orthDimension of the symplectic orthogonal complement. Let $p$ be a prime and equip the $2n$-dimensional space…
- code_k$k(S) = n - \dim(S)$.
- symB_applyEvaluation of the bundled symplectic form. Fix a prime $p$ and an integer $n$, and set $V = \bbf_p^n \times \bbf_p^n$, equipped with the…
- finrank_le_n_of_isotropicDimension bound for isotropic subspaces. Let $p$ be a prime and equip the $2n$-dimensional space $V = \bbf_p^n \times \bbf_p^n$ over…
- 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.
- 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. - IsIsotropic$S$ is isotropic if $S \le S^{\perp_\omega}$, i.e.\ $\omega(u,v) = 0$ for all $u,v \in S$.
- 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] 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] 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] 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] 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] invariable {n : ℕ} {p : ℕ} [Fact p.Prime] invariable {n : ℕ} {p : ℕ} [Fact p.Prime] invariable {n : ℕ} {p : ℕ} [Fact p.Prime] inlemma code_dist_eq_zero_of_code_k_eq_zero (S : Submodule (F p) (V n p)) (hS : IsIsotropic (n:=n) (p:=p) S) (hk : code_k (n:=n) (p:=p) S = 0) : code_dist (n:=n) (p:=p) S = 0 := by classical have hfin_le_n : Module.finrank (F p) S ≤ n := finrank_le_n_of_isotropic (n:=n) (p:=p) S hS have hk' : n - Module.finrank (F p) S = 0 := by simpa [code_k] using hk have hn_le_fin : n ≤ Module.finrank (F p) S := (Nat.sub_eq_zero_iff_le).1 hk' have hfin_eq : Module.finrank (F p) S = n := Nat.le_antisymm hfin_le_n hn_le_fin have hfin_orth : Module.finrank (F p) (sym_orth (n:=n) (p:=p) S) = Module.finrank (F p) S := by calc Module.finrank (F p) (sym_orth (n:=n) (p:=p) S) = 2 * n - Module.finrank (F p) S := by simpa using finrank_sym_orth (n:=n) (p:=p) S _ = 2 * n - n := by simp [hfin_eq] _ = n := by simpa [two_mul] using (Nat.add_sub_cancel_left n n) _ = Module.finrank (F p) S := by simp [hfin_eq] have hEq : S = sym_orth (n:=n) (p:=p) S := by apply Submodule.eq_of_le_of_finrank_eq hS simpa using hfin_orth.symm unfold code_dist rw [← hEq] have hEmpty : {d : ℕ | ∃ v ∈ S, v ∉ S ∧ wt (n:=n) (p:=p) v = d} = (∅ : Set ℕ) := by ext d constructor · rintro ⟨v, hvS, hvnotS, -⟩ exact (hvnotS hvS).elim · intro hd cases hd rw [hEmpty] simp