AFTD Auto-Formalizing Theoretical Domains

dim_orth_inter

theoremverifiedimported Lean

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.
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

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.-/
See it in the graphDiscuss this resultChallenge it