AFTD Auto-Formalizing Theoretical Domains

extendFromC_restrictToC

theoremverifiedimported Lean

Extension recovers a vector supported on $C$. Fix a prime $p$ and a subset $C \subseteq \{1,\dots,n\}$ of coordinates, and let $V_C \subseteq \mathbb{F}_p^n \times \mathbb{F}_p^n$ be the submodule of pairs of vectors whose support is contained in $C$. Then extending back the coordinate functions of a supported vector recovers that vector exactly: for every $x \in V_C$, applying the restriction map $V_C \to (C \to \mathbb{F}_p) \times (C \to \mathbb{F}_p)$ and then the extension-by-zero map back into $V_C$ returns $x$. Equivalently, the extension map is a left inverse of the restriction map.

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
lemma extendFromC_restrictToC (C : Finset (Fin n)) :
    ∀ x, extendFromC (p:=p) C (restrictToC (p:=p) C x) = x
Source
TCSlib, `extendFromC_restrictToC`
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
  • extendFromCThe linear map $(C \to \mathbb{F}_p) \times (C \to \mathbb{F}_p) \to V_C$ that extends a pair of functions on $C$ to a vector of $V$ by…
  • V_subFor $C \subseteq \mathrm{Fin}\,n$, the support submodule $V_C = \{v \in V \mid \mathrm{supp}(v) \subseteq C\}$.
  • restrictToCFor $C \subseteq \mathrm{Fin}\,n$, the linear map $V_C \to (C \to \mathbb{F}_p) \times (C \to \mathbb{F}_p)$ sending a vector supported on…
Used by 1

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] inlemma extendFromC_restrictToC (C : Finset (Fin n)) :    ∀ x, extendFromC (p:=p) C (restrictToC (p:=p) C x) = x := by  classical  rintro ⟨v, hv⟩  have hv' : ∀ j, j ∉ C → v.1 j = 0 ∧ v.2 j = 0 := by    simpa [V_sub] using hv  apply Subtype.ext  ext i  · by_cases hi : i ∈ C    · simp [extendFromC, restrictToC, hi]    · have h0 := (hv' i hi).1      simp [extendFromC, restrictToC, hi, h0]  · by_cases hi : i ∈ C    · simp [extendFromC, restrictToC, hi]    · have h0 := (hv' i hi).2      simp [extendFromC, restrictToC, hi, h0]
See it in the graphDiscuss this resultChallenge it