AFTD Auto-Formalizing Theoretical Domains

two_disjoint_correctable_sets_bound_logical_dimension

theoremverifiedimported Lean

Two disjoint correctable erasures bound the logical dimension. Work in the symplectic space $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$ over the prime field $\bbf_p$, equipped with the symplectic form $\omega$, and let $S \le V$ be an isotropic submodule, so that $\omega(u,v) = 0$ for all $u, v \in S$. Suppose $A, B \subseteq \{0, 1, \dots, n-1\}$ are two disjoint sets of coordinates, each correctable for $S$: every vector of $S^{\perp_\omega}$ supported on $A$ lies in $S$, and likewise every vector of $S^{\perp_\omega}$ supported on $B$ lies in $S$. Then the logical dimension $k(S) = n - \dim S$ satisfies \[ k(S) \;\le\; \bigl|\{0, 1, \dots, n-1\} \setminus (A \cup B)\bigr| \;=\; n - |A| - |B|. \]

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
lemma two_disjoint_correctable_sets_bound_logical_dimension (S : Submodule (F p) (V n p)) (hS : IsIsotropic S)
    (A B : Finset (Fin n)) (h_disjoint : Disjoint A B)
    (hA : correctable S A) (hB : correctable S B) :
    code_k S ≤ (Finset.univ \ (A ∪ B)).card
Source
TCSlib, `two_disjoint_correctable_sets_bound_logical_dimension`
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.
What was changed in two_disjoint_correctable_sets_bound_logical_dimension
--- TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:1002 (two_disjoint_correctable_sets_bound_logical_dimension)
+++ as compiled here
@@ -1,2 +1,51 @@
-/-- Lemma 5: Two disjoint correctable sets bound logical dimension -/
+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
 lemma two_disjoint_correctable_sets_bound_logical_dimension (S : Submodule (F p) (V n p)) (hS : IsIsotropic S)
@@ -7,2 +56,3 @@
         convert g_complement_correctable S hS A hA using 1;
+        · simp [E_c, Finset.compl_eq_univ_sdiff]
         rw [ Nat.mul_sub_left_distrib ];
Verified
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
  • g_complement_correctableCorrectable erasure and the count of supportable logical operators. Let $S$ be an isotropic subspace of the symplectic space…
  • g_le_two_card_CCorrectable part contributes nothing to the operator count. Let $p$ be prime and let $S$ be an $\mathbb{F}_p$-subspace of the symplectic…
  • 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$.
  • VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
  • code_k$k(S) = n - \dim(S)$.
  • 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$.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
  • E_c$E^c = \mathrm{Fin}\,n \setminus E$, the complement finset of $E$.
  • 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…
  • sym_form_sub_applyEvaluation of the restricted symplectic form. Fix a prime $p$ and let $\omega$ denote the symplectic form on…
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 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
/-- Lemma 5: Two disjoint correctable sets bound logical dimension -/
lemma two_disjoint_correctable_sets_bound_logical_dimension (S : Submodule (F p) (V n p)) (hS : IsIsotropic S)
    (A B : Finset (Fin n)) (h_disjoint : Disjoint A B)
    (hA : correctable S A) (hB : correctable S B) :
    code_k S ≤ (Finset.univ \ (A ∪ B)).card := by
      have h_g_Ac : g S (Finset.univ \ A) = 2 * (n - Module.finrank (F p) S) := by
        convert g_complement_correctable S hS A hA using 1;
        · simp [E_c, Finset.compl_eq_univ_sdiff]
        rw [ Nat.mul_sub_left_distrib ];
      have h_g_BC : g S (B ∪ (Finset.univ \ (A ∪ B))) ≤ 2 * (Finset.univ \ (A ∪ B)).card := by
        apply g_le_two_card_C;
        · exact Finset.disjoint_left.mpr fun x hx₁ hx₂ => Finset.mem_sdiff.mp hx₂ |>.2 ( Finset.mem_union_right _ hx₁ );
        · assumption;
      have h_BC_eq_Ac : B ∪ (Finset.univ \ (A ∪ B)) = Finset.univ \ A := by
        ext x; by_cases hx : x ∈ A <;> by_cases hx' : x ∈ B <;> simp +decide [ hx, hx' ] ;
        exact Finset.disjoint_left.mp h_disjoint hx hx';
      unfold code_k; simp_all only [Nat.ofNat_pos, mul_le_mul_iff_right₀, tsub_le_iff_right];
See it in the graphDiscuss this resultChallenge it