AFTD Auto-Formalizing Theoretical Domains

code_dist_le_n

theoremverifiedimported Lean

Code distance is at most the block length. Fix a prime $p$ and a natural number $n$, and let $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$ carry the symplectic form $\omega\bigl((x,z),(x',z')\bigr) = \sum_{i} (x_i z'_i - z_i x'_i)$. For every $\bbf_p$-subspace $S \le V$, the associated code distance $d(S)$ — the least weight $\mathrm{wt}(v) = |\mathrm{supp}(v)|$ attained by a vector $v$ lying in the symplectic orthogonal complement $S^{\perp_\omega}$ but not in $S$ — satisfies $d(S) \le n$.

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_le_n (S : Submodule (F p) (V n p)) :
    code_dist (n:=n) (p:=p) S ≤ n
Source
TCSlib, `code_dist_le_n`
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 7
  • sym_orthFor a submodule $S \le V$, $S^{\perp_\omega} = \{v \in V \mid \forall s \in S,\; \omega(v,s) = 0\}$.
  • 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…
  • wtThe support $\mathrm{supp}(v) \subseteq \mathrm{Fin}\,n$ consists of coordinates where either component of $v$ is nonzero; the…
  • wt_le_nWeight bound. Fix a prime $p$ and a natural number $n$, and let $v \in \bbf_p^n \times \bbf_p^n$. Then the weight $\mathrm{wt}(v)$…
  • 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.
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] 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] in/-- `code_dist S ≤ n` since all weights are bounded by `n`. -/lemma code_dist_le_n (S : Submodule (F p) (V n p)) :    code_dist (n:=n) (p:=p) S ≤ n := by  classical  let D : Set ℕ :=    { d | ∃ v ∈ sym_orth (n:=n) (p:=p) S, v ∉ S ∧ wt (n:=n) (p:=p) v = d }  unfold code_dist  change sInf D ≤ n  by_cases hD : D = ∅  ·    simpa [hD] using (Nat.zero_le n)  ·    have hDne : D.Nonempty := Set.nonempty_iff_ne_empty.2 hD    rcases hDne with ⟨d0, hd0mem⟩    rcases hd0mem with ⟨v, hvS, hvnotS, hwt⟩    have hd0 : d0 ∈ D := ⟨v, hvS, hvnotS, hwt⟩    have hBdd : BddBelow D := ⟨0, by      intro d hd      exact Nat.zero_le d⟩    have hdist_le : sInf D ≤ d0 := by      exact csInf_le hBdd hd0    have hd0_le : d0 ≤ n := by      have : wt (n:=n) (p:=p) v ≤ n := wt_le_n (n:=n) (p:=p) v      simpa [hwt] using this    exact le_trans hdist_le hd0_le
See it in the graphDiscuss this resultChallenge it