AFTD Auto-Formalizing Theoretical Domains

orth_inter_eq_orth_sub_image

theoremverifiedimported Lean

Orthogonal complement of a subspace, intersected with a support submodule. Let $p$ be a prime and let $\omega$ be the symplectic form on $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$. For any subset $M$ of $\{0, 1, \dots, n-1\}$ and any submodule $S \le V$, the vectors of the support submodule $V_M$ that are $\omega$-orthogonal to every element of $S$ are exactly the images, under the inclusion $V_M \hookrightarrow V$, of the vectors of $V_M$ that are orthogonal to $r_M(S)$ with respect to the restriction of $\omega$ to $V_M$. In symbols, writing $\iota \colon V_M \hookrightarrow V$ for the inclusion and $\perp_M$ for orthogonality with respect to the restricted form, \[ S^{\perp_\omega} \cap V_M \;=\; \iota\!\left( r_M(S)^{\perp_M} \right), \] where $r_M(S)$ is the image of $S$ under the restriction map $r_M \colon V \to V_M$.

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
lemma orth_inter_eq_orth_sub_image (M : Finset (Fin n)) (S : Submodule (F p) (V n p)) :
    sym_orth S ⊓ V_sub (p:=p) M = ((sym_form_sub (p:=p) M).orthogonal (S.map (r_E M))).map (V_sub (p:=p) M).subtype
Source
TCSlib, `orth_inter_eq_orth_sub_image`
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 orth_inter_eq_orth_sub_image
--- TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:708 (orth_inter_eq_orth_sub_image)
+++ as compiled here
@@ -1,2 +1,34 @@
-/-- The intersection S^\perp ∩ V_M corresponds to the orthogonal complement of r_M(S) in V_M -/
+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
 lemma orth_inter_eq_orth_sub_image (M : Finset (Fin n)) (S : Submodule (F p) (V n p)) :
@@ -6,3 +38,3 @@
   ext; simp [sym_form_sub];
-  simp +decide [ symB, LinearMap.BilinForm.IsOrtho ];
+  try simp +decide [ symB, LinearMap.BilinForm.IsOrtho ];
   simp +decide [ r_E_V, Subtype.ext_iff ];
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
  • orth_inter_eq_orth_mapRestricting to a support before taking the symplectic complement. Fix a prime $p$ and work in the symplectic space…
  • sym_orthFor a submodule $S \le V$, $S^{\perp_\omega} = \{v \in V \mid \forall s \in S,\; \omega(v,s) = 0\}$.
  • r_E_VThe composition $r_E^V : V \to V$ of $r_E$ with the inclusion $V_E \hookrightarrow V$.
  • 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$.
  • 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.
  • symB$\omega$ packaged as a LinearMap.BilinForm.
Used by 4

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] in/-- The intersection S^\perp ∩ V_M corresponds to the orthogonal complement of r_M(S) in V_M -/lemma orth_inter_eq_orth_sub_image (M : Finset (Fin n)) (S : Submodule (F p) (V n p)) :    sym_orth S ⊓ V_sub (p:=p) M = ((sym_form_sub (p:=p) M).orthogonal (S.map (r_E M))).map (V_sub (p:=p) M).subtype := by  classical  convert orth_inter_eq_orth_map M S using 1;  ext; simp [sym_form_sub];  try simp +decide [ symB, LinearMap.BilinForm.IsOrtho ];  simp +decide [ r_E_V, Subtype.ext_iff ];  grind/-The restricted symplectic form is reflexive.-/
See it in the graphDiscuss this resultChallenge it