dim_orth_inter
Dimension of the orthogonal intersection over a coordinate set. Fix a prime $p$, an integer $n$, and work in the symplectic space $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$ equipped with the symplectic form $\omega\big((x,z),(x',z')\big) = \sum_{i} (x_i z'_i - z_i x'_i)$. Let $M$ be a subset of the coordinate set $\{0,1,\dots,n-1\}$, let $V_M \le V$ be the support submodule of vectors whose coordinates vanish outside $M$, and let $r_M : V \to V_M$ be the restriction map that zeroes every coordinate outside $M$. Then for any $\bbf_p$-subspace $S \le V$, the symplectic orthogonal complement $S^{\perp_\omega}$ satisfies \[ \dim_{\bbf_p}\big(S^{\perp_\omega} \cap V_M\big) \;=\; 2\,\abs{M} \;-\; \dim_{\bbf_p}\big(r_M(S)\big). \]
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 lemma dim_orth_inter (M : Finset (Fin n)) (S : Submodule (F p) (V n p)) : Module.finrank (F p) ↥(sym_orth S ⊓ V_sub (p:=p) M) = 2 * M.card - Module.finrank (F p) ↥(S.map (r_E M))
- Source
- TCSlib, `dim_orth_inter`
- 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_orth_inter← dim_orth_inter (TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:751): adapted
What was changed in
dim_orth_inter--- TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:751 (dim_orth_inter) +++ as compiled here @@ -1,2 +1,36 @@ -/-- Dimension of orthogonal intersection -/ +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 lemma dim_orth_inter (M : Finset (Fin n)) (S : Submodule (F p) (V n p)) : @@ -7,3 +41,3 @@ have h_orthogonal_complement : ∀ (W : Submodule (F p) (V_sub (p:=p) M)), (sym_form_sub (p:=p) M).IsRefl → (sym_form_sub (p:=p) M).Nondegenerate → Module.finrank (F p) ((sym_form_sub (p:=p) M).orthogonal W) = Module.finrank (F p) (V_sub (p:=p) M) - Module.finrank (F p) W := by - exact fun W a a_1 => LinearMap.BilinForm.finrank_orthogonal a_1 a W; + exact fun W a a_1 => LinearMap.BilinForm.finrank_orthogonal a_1 W; exact fun W => h_orthogonal_complement W ( sym_form_sub_isRefl M ) ( sym_form_sub_nondegenerate M ); - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- sym_orthFor a submodule $S \le V$, $S^{\perp_\omega} = \{v \in V \mid \forall s \in S,\; \omega(v,s) = 0\}$.
- sym_form_sub_isReflReflexivity of the restricted symplectic form. Fix a prime $p$, a natural number $n$, and a subset $M \subseteq \{0,1,\dots,n-1\}$, and…
- orth_inter_eq_orth_sub_imageOrthogonal complement of a subspace, intersected with a support submodule. Let $p$ be a prime and let $\omega$ be the symplectic form on…
- 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_subAn abbreviation for $\mathrm{symB\_sub}$, the symplectic form viewed as a bilinear form on $V_M$.
- 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…
- V_subFor $C \subseteq \mathrm{Fin}\,n$, the support submodule $V_C = \{v \in V \mid \mathrm{supp}(v) \subseteq C\}$.
- 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_form_sub_applyEvaluation of the restricted symplectic form. Fix a prime $p$ and let $\omega$ denote the symplectic form on…
- VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod. - sym_form_sub_nondegenerateNondegeneracy of the restricted symplectic form. Let $p$ be a prime, and equip $V = \bbf_p^n \times \bbf_p^n$ with the symplectic form…
- Used by 2
- g_expansionExpansion of the operator count $g(S,M)$. Fix a prime $p$ and equip $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$ with the symplectic form…
- 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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] in/-- Dimension of orthogonal intersection -/lemma dim_orth_inter (M : Finset (Fin n)) (S : Submodule (F p) (V n p)) : Module.finrank (F p) ↥(sym_orth S ⊓ V_sub (p:=p) M) = 2 * M.card - Module.finrank (F p) ↥(S.map (r_E M)) := by have h_image : sym_orth S ⊓ V_sub M = ((sym_form_sub M).orthogonal (S.map (r_E M))).map (V_sub M).subtype := by convert orth_inter_eq_orth_sub_image M S using 1; have h_orthogonal_complement : ∀ (W : Submodule (F p) (V_sub (p:=p) M)), Module.finrank (F p) ((sym_form_sub M).orthogonal W) = Module.finrank (F p) (V_sub (p:=p) M) - Module.finrank (F p) W := by have h_orthogonal_complement : ∀ (W : Submodule (F p) (V_sub (p:=p) M)), (sym_form_sub (p:=p) M).IsRefl → (sym_form_sub (p:=p) M).Nondegenerate → Module.finrank (F p) ((sym_form_sub (p:=p) M).orthogonal W) = Module.finrank (F p) (V_sub (p:=p) M) - Module.finrank (F p) W := by exact fun W a a_1 => LinearMap.BilinForm.finrank_orthogonal a_1 W; exact fun W => h_orthogonal_complement W ( sym_form_sub_isRefl M ) ( sym_form_sub_nondegenerate M ); convert h_orthogonal_complement ( S.map ( r_E M ) ) using 1; · rw [ h_image, ← Submodule.finrank_map_subtype_eq ]; · rw [ dim_V_sub ]/-Expansion of g(M) in terms of dimensions of S and intersections.-/