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.dim_S_M_add_dim_S_M_c_le_dim_S← dim_S_M_add_dim_S_M_c_le_dim_S (TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:809): adapted
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. -/