AFTD Auto-Formalizing Theoretical Domains

g_le_two_card_C

theoremverifiedimported Lean

Correctable part contributes nothing to the operator count. 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$. Suppose $B$ and $C$ are disjoint subsets of the coordinate set $\{0,\dots,n-1\}$, and that $B$ is correctable for $S$. Then \[ g(S,\, B \cup C) \;\le\; 2\lvert C\rvert, \] where $g(S,M) = \dim_{\mathbb{F}_p}\!\bigl(S^{\perp}_M\bigr) - \dim_{\mathbb{F}_p}\!\bigl(S_M\bigr)$.

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
lemma g_le_two_card_C (S : Submodule (F p) (V n p)) (B C : Finset (Fin n))
    (h_disjoint : Disjoint B C) (hB : correctable S B) :
    g S (B ∪ C) ≤ 2 * C.card
Source
TCSlib, `g_le_two_card_C`
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 g_le_two_card_C
--- TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:940 (g_le_two_card_C)
+++ as compiled here
@@ -1 +1,49 @@
+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
 lemma g_le_two_card_C (S : Submodule (F p) (V n p)) (B C : Finset (Fin n))
@@ -18,4 +66,6 @@
           intro i hi; specialize h_S_perp_M_subset v.2; simp_all +decide [ V_sub ] ;
-          by_cases hi' : i ∈ C <;> simp_all +decide [ Subtype.ext_iff ];
-          exact ⟨ by simpa [ hi' ] using congr_fun h_zero.1 i, by simpa [ hi' ] using congr_fun h_zero.2 i ⟩
+          by_cases hi' : i ∈ C <;> try simp_all +decide [ Subtype.ext_iff ];
+          have hz := congrArg Subtype.val h_zero
+          simp only [ZeroMemClass.coe_zero, Prod.mk_eq_zero] at hz
+          exact ⟨ by simpa [ hi' ] using congr_fun hz.1 i, by simpa [ hi' ] using congr_fun hz.2 i ⟩
         exact (by
@@ -38,3 +88,3 @@
         rw [ ← this ];
-        exact add_le_add_left ( Submodule.finrank_mono <| h_kernel_r_C ▸ h_S_perp_B_subset_S ) _;
+        exact add_le_add_right ( Submodule.finrank_mono <| h_kernel_r_C ▸ h_S_perp_B_subset_S ) _;
       have h_dim_r_C_U_le : Module.finrank (F p) (LinearMap.range r_C) ≤ 2 * C.card := by
Verified
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 14
  • FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via ZMod.
  • S_MFor a submodule $S \le V$ and $M \subseteq \mathrm{Fin}\,n$, the submodule $S_M = S \cap V_M$.
  • S_perp_MThe submodule $S^{\perp}_M = S^{\perp_\omega} \cap V_M$.
  • VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
  • V_subFor $C \subseteq \mathrm{Fin}\,n$, the support submodule $V_C = \{v \in V \mid \mathrm{supp}(v) \subseteq C\}$.
  • 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$.
  • dim_V_subDimension of the support submodule. Fix a prime $p$ and an integer $n$, and let $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$ be the space of…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
  • r_EThe linear map $r_E : V \to V_E$ that zeroes out the coordinates of a vector outside $E$, keeping those in $E$ unchanged.
  • 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…
  • sym_form_sub_applyEvaluation of the restricted symplectic form. Fix a prime $p$ and let $\omega$ denote the symplectic form on…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

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
lemma g_le_two_card_C (S : Submodule (F p) (V n p)) (B C : Finset (Fin n))
    (h_disjoint : Disjoint B C) (hB : correctable S B) :
    g S (B ∪ C) ≤ 2 * C.card := by
      have h_g_def : g S (B ∪ C) = Module.finrank (F p) (S_perp_M S (B ∪ C)) - Module.finrank (F p) (S_M S (B ∪ C)) := by
        rfl;
      have h_S_perp_M_subset : S_perp_M S (B ∪ C) ≤ V_sub (p:=p) (B ∪ C) := by
        exact inf_le_right;

      set U : Submodule (F p) (V n p) := S_perp_M S (B ∪ C);

      set r_C : U →ₗ[F p] V_sub (p:=p) C := (r_E C).comp (Submodule.subtype U);
      have h_kernel_r_C : LinearMap.ker r_C = Submodule.comap (Submodule.subtype U) (V_sub (p:=p) B) := by
        ext v
        simp [r_C, r_E];
        apply Iff.intro
        intro h_zero
        have h_support : ∀ i, i ∉ B → (v : V n p).1 i = 0 ∧ (v : V n p).2 i = 0 := by
          intro i hi; specialize h_S_perp_M_subset v.2; simp_all +decide [ V_sub ] ;
          by_cases hi' : i ∈ C <;> try simp_all +decide [ Subtype.ext_iff ];
          have hz := congrArg Subtype.val h_zero
          simp only [ZeroMemClass.coe_zero, Prod.mk_eq_zero] at hz
          exact ⟨ by simpa [ hi' ] using congr_fun hz.1 i, by simpa [ hi' ] using congr_fun hz.2 i ⟩
        exact (by
        exact fun i hi => by specialize h_support i hi; simp_all only [Submodule.mk_eq_zero, Prod.mk_eq_zero, and_self,
          U];)
        intro h_support
        have h_zero : ∀ i ∈ C, (v : V n p).1 i = 0 ∧ (v : V n p).2 i = 0 := by
          exact fun i hi => h_support i ( Finset.disjoint_right.mp h_disjoint hi )
        exact (by
        ext i; simp_all only [ite_self, ZeroMemClass.coe_zero, Prod.fst_zero, Pi.zero_apply, U];
        by_cases hi : i ∈ C <;> simp +decide [ hi, h_zero ])

      have h_S_perp_B_subset_S : Submodule.comap (Submodule.subtype U) (V_sub (p:=p) B) ≤ Submodule.comap (Submodule.subtype U) S := by
        intro x hx; exact (by
        have := hB ( show x.1 ∈ sym_orth S ⊓ V_sub B from ?_ ) ; simp_all only [Submodule.mem_comap,
          Submodule.subtype_apply, U, r_C];
        exact ⟨ x.2.1, hx ⟩);
      have h_dim_U_le : Module.finrank (F p) U ≤ Module.finrank (F p) (LinearMap.range r_C) + Module.finrank (F p) (Submodule.comap (Submodule.subtype U) S) := by
        have := LinearMap.finrank_range_add_finrank_ker r_C;
        rw [ ← this ];
        exact add_le_add_right ( Submodule.finrank_mono <| h_kernel_r_C ▸ h_S_perp_B_subset_S ) _;
      have h_dim_r_C_U_le : Module.finrank (F p) (LinearMap.range r_C) ≤ 2 * C.card := by
        exact le_trans ( Submodule.finrank_le _ ) ( by erw [ dim_V_sub ] );
      have h_dim_S_inter_V_B_union_C_le : Module.finrank (F p) (Submodule.comap (Submodule.subtype U) S) ≤ Module.finrank (F p) (S_M S (B ∪ C)) := by
        rw [ ← Submodule.finrank_map_subtype_eq ];
        refine' Submodule.finrank_mono _;
        simp +zetaDelta at *;
        exact fun x hx => ⟨ hx.2, h_S_perp_M_subset hx.1 ⟩;
      exact h_g_def.symm ▸ Nat.sub_le_of_le_add ( by linarith )

/-
Definition of the number of logical qudits k.
-/
See it in the graphDiscuss this resultChallenge it