AFTD Auto-Formalizing Theoretical Domains

ker_r_E

theoremverifiedimported Lean

Kernel of the coordinate restriction map. Fix a prime $p$ and let $V = \bbf_p^n \times \bbf_p^n$. For a subset $E \subseteq \{1,\dots,n\}$, let $r_E \colon V \to V_E$ be the restriction map that keeps the coordinates indexed by $E$ and sets all others to zero. Then the kernel of $r_E$ is the support submodule $V_{E^c}$ consisting of those vectors whose support lies in the complement $E^c = \{1,\dots,n\} \setminus E$; that is, $r_E$ annihilates exactly the vectors that vanish on every coordinate in $E$.

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
lemma ker_r_E (E : Finset (Fin n)) :
    LinearMap.ker (r_E (p:=p) E) = V_sub (p:=p) (Finset.univ \ E)
Source
TCSlib, `ker_r_E`
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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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.
  • VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
Used by 2
  • dim_map_r_ERank of a restricted subspace of $\mathbb{F}_p^n \times \mathbb{F}_p^n$. Fix a prime $p$ and an integer $n \ge 0$, and let…
  • LinearPMap.HasDenseDomain.orthogonal_rangeU.rangeᗮ = U†.ker c.f. LinearMap.orthogonal_range and ContinuousLinearMap.orthogonal_range

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] in/-- Kernel of r_E is V_{E^c} -/lemma ker_r_E (E : Finset (Fin n)) :    LinearMap.ker (r_E (p:=p) E) = V_sub (p:=p) (Finset.univ \ E) := by  classical  ext x  constructor  · intro hx    have hx0 : (r_E (p:=p) E) x = 0 := by      simpa [LinearMap.mem_ker] using hx    have hxval : ((r_E (p:=p) E) x : V n p) = 0 :=      congrArg Subtype.val hx0    have hx1fun :        (fun i : Fin n => if i ∈ E then x.1 i else 0) = 0 := by      simpa [r_E] using congrArg Prod.fst hxval    have hx2fun :        (fun i : Fin n => if i ∈ E then x.2 i else 0) = 0 := by      simpa [r_E] using congrArg Prod.snd hxval    intro i hi    have hiE : i ∈ E := by      simpa [Finset.mem_sdiff, Finset.mem_univ] using hi    constructor    · have hx1i : (if i ∈ E then x.1 i else 0) = 0 :=        congrArg (fun f => f i) hx1fun      simpa [hiE] using hx1i    · have hx2i : (if i ∈ E then x.2 i else 0) = 0 :=        congrArg (fun f => f i) hx2fun      simpa [hiE] using hx2i  · intro hx    have hfx : (r_E (p:=p) E) x = 0 := by      ext i <;> by_cases hi : i ∈ E      ·        have hnot : i ∉ (Finset.univ \ E) := by          simp [Finset.mem_sdiff, Finset.mem_univ, hi]        simpa [r_E, hi] using (hx i hnot).1      ·        simp [r_E, hi]      ·        have hnot : i ∉ (Finset.univ \ E) := by          simp [Finset.mem_sdiff, Finset.mem_univ, hi]        simpa [r_E, hi] using (hx i hnot).2      ·        simp [r_E, hi]    simpa [LinearMap.mem_ker] using hfx/-Defining complement of E.-/
See it in the graphDiscuss this resultChallenge it