AFTD Auto-Formalizing Theoretical Domains

dim_S_M_add_dim_S_M_c_le_dim_S

theoremverifiedimported Lean

Additivity bound for support-restricted subspaces. Fix a prime $p$ and an integer $n$, and let $S$ be a subspace of the ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$. For a subset $M \subseteq \{1,\dots,n\}$ with complement $M^c$, write $S_M = S \cap V_M$ and $S_{M^c} = S \cap V_{M^c}$ for the intersections of $S$ with the corresponding support subspaces. Then \[ \dim_{\mathbb{F}_p} S_M + \dim_{\mathbb{F}_p} S_{M^c} \le \dim_{\mathbb{F}_p} 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
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact p.Prime] in
variable {n : ℕ} {p : ℕ} [Fact 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 dim_S_M_add_dim_S_M_c_le_dim_S (S : Submodule (F p) (V n p)) (M : Finset (Fin n)) :
    Module.finrank (F p) (S_M S M) + Module.finrank (F p) (S_M S (E_c M)) ≤ Module.finrank (F p) S
Source
TCSlib, `dim_S_M_add_dim_S_M_c_le_dim_S`
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 dim_S_M_add_dim_S_M_c_le_dim_S
--- TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:809 (dim_S_M_add_dim_S_M_c_le_dim_S)
+++ as compiled here
@@ -1 +1,39 @@
+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
 lemma dim_S_M_add_dim_S_M_c_le_dim_S (S : Submodule (F p) (V n p)) (M : Finset (Fin n)) :
@@ -5,7 +43,15 @@
         exact sup_le ( inf_le_left ) ( inf_le_left );
-      refine' le_trans ( add_le_add_right ( Submodule.finrank_mono h_sum_subset ) _ ) _;
-      simp +decide [ S_M ];
-      simp +decide [ Submodule.eq_bot_iff, V_sub ];
-      simp_all +decide [ E_c, funext_iff ];
-      exact fun a b ha ha' ha'' => ⟨ fun i => if hi : i ∈ M then ha'' i hi |>.1 else ha' i hi |>.1, fun i => if hi : i ∈ M then ha'' i hi |>.2 else ha' i hi |>.2 ⟩
+      refine' le_trans ( add_le_add_left ( Submodule.finrank_mono h_sum_subset ) _ ) _;
+      have hbot : S_M S M ⊓ S_M S (E_c M) = ⊥ := by
+        rw [eq_bot_iff]
+        intro v hv
+        rw [Submodule.mem_bot]
+        have h1 : ∀ i ∉ M, v.1 i = 0 ∧ v.2 i = 0 := hv.1.2
+        have h2 : ∀ i ∉ E_c M, v.1 i = 0 ∧ v.2 i = 0 := hv.2.2
+        have h3 : ∀ i, v.1 i = 0 ∧ v.2 i = 0 := fun i => by
+          by_cases hi : i ∈ M
+          · exact h2 i (by simp [E_c, hi])
+          · exact h1 i hi
+        exact Prod.ext (funext fun i => (h3 i).1) (funext fun i => (h3 i).2)
+      simp [hbot]
 
Verified
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • E_c$E^c = \mathrm{Fin}\,n \setminus E$, the complement finset of $E$.
  • 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$.
  • 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\}$.
  • 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
  • g_add_dimsAdditive dimension identity for an isotropic subspace. Let $S$ be an isotropic submodule of the symplectic space…

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
lemma dim_S_M_add_dim_S_M_c_le_dim_S (S : Submodule (F p) (V n p)) (M : Finset (Fin n)) :
    Module.finrank (F p) (S_M S M) + Module.finrank (F p) (S_M S (E_c M)) ≤ Module.finrank (F p) S := by
      rw [ ← Submodule.finrank_sup_add_finrank_inf_eq ];
      have h_sum_subset : S_M S M ⊔ S_M S (E_c M) ≤ S := by
        exact sup_le ( inf_le_left ) ( inf_le_left );
      refine' le_trans ( add_le_add_left ( Submodule.finrank_mono h_sum_subset ) _ ) _;
      have hbot : S_M S M ⊓ S_M S (E_c M) = ⊥ := by
        rw [eq_bot_iff]
        intro v hv
        rw [Submodule.mem_bot]
        have h1 : ∀ i ∉ M, v.1 i = 0 ∧ v.2 i = 0 := hv.1.2
        have h2 : ∀ i ∉ E_c M, v.1 i = 0 ∧ v.2 i = 0 := hv.2.2
        have h3 : ∀ i, v.1 i = 0 ∧ v.2 i = 0 := fun i => by
          by_cases hi : i ∈ M
          · exact h2 i (by simp [E_c, hi])
          · exact h1 i hi
        exact Prod.ext (funext fun i => (h3 i).1) (funext fun i => (h3 i).2)
      simp [hbot]


/-
Formula for g(M) in terms of dimensions.
-/
See it in the graphDiscuss this resultChallenge it