AFTD Auto-Formalizing Theoretical Domains

restrictToC_extendFromC

theoremverifiedimported Lean

Restriction inverts extension on coordinates in $C$. Fix a prime $p$, a natural number $n$, and a subset $C \subseteq \{0,1,\dots,n-1\}$ of coordinates, and let $V_C$ denote the support submodule of $V = \bbf_p^n \times \bbf_p^n$ consisting of vectors whose support lies in $C$. Let $E \colon (C \to \bbf_p) \times (C \to \bbf_p) \to V_C$ be the extension map, which sends a pair $(f,g)$ to the vector agreeing with $f$ and $g$ on $C$ and equal to zero off $C$, and let $R \colon V_C \to (C \to \bbf_p) \times (C \to \bbf_p)$ be the restriction map, which sends a vector supported on $C$ to its two component functions restricted to $C$. Then $R \circ E$ is the identity: for every pair $x = (f,g)$ of functions $f, g \colon C \to \bbf_p$ one has $R(E(x)) = x$.

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 restrictToC_extendFromC (C : Finset (Fin n)) :
    ∀ x, restrictToC (p:=p) C (extendFromC (p:=p) C x) = x
Source
TCSlib, `restrictToC_extendFromC`
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 2
  • 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…
  • 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 restrictToC_extendFromC (C : Finset (Fin n)) :    ∀ x, restrictToC (p:=p) C (extendFromC (p:=p) C x) = x := by  classical  rintro ⟨f, g⟩  apply Prod.ext  · funext c; simp [restrictToC, extendFromC]  · funext c; simp [restrictToC, extendFromC]
See it in the graphDiscuss this resultChallenge it