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.extendFromC_restrictToC← extendFromC_restrictToC (TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:284): verbatim
- 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
- V_sub_isoV_sub_iso
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]