card_full_support_le_of_injective
If the coordinate projection v ↦ (v.1|_S, v.2|_S) onto a subset S of physical pairs is injective on a translate a + L, then the number of full-support vectors in a + L (vectors with supp v = univ) is at most 3^|S|.
Statement
open scoped Pointwise in lemma card_full_support_le_of_injective {k : ℕ} (L : Submodule (F 2) (V k 2)) (S : Finset (Fin k)) (a : V k 2) (hinj : Set.InjOn (fun v : V k 2 => ((fun (s : S) => v.1 s.1), (fun (s : S) => v.2 s.1))) (a +ᵥ (L : Set (V k 2)))) : Nat.card {v ∈ a +ᵥ (L : Set (V k 2)) | supp v = Finset.univ} ≤ 3 ^ S.card
- Source
- arXiv:2610.04621 Lemma 5
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod. - suppThe support $\mathrm{supp}(v) \subseteq \mathrm{Fin}\,n$ consists of coordinates where either component of $v$ is nonzero; the…
- 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
Read back from the Lean
For any natural number $k$ (implicit), given: - a $\mathbb{Z}/2\mathbb{Z}$-submodule $L$ of $(\mathrm{Fin}\ k \to \mathbb{Z}/2\mathbb{Z}) \times (\mathrm{Fin}\ k \to \mathbb{Z}/2\mathbb{Z})$, - a finite subset $S \subseteq \mathrm{Fin}\ k$, and - an element $a \in (\mathrm{Fin}\ k \to \mathbb{Z}/2\mathbb{Z}) \times (\mathrm{Fin}\ k \to \mathbb{Z}/2\mathbb{Z})$, if the coordinate projection map $v \mapsto (v_1|_S, v_2|_S)$ is injective on the affine coset $a + L$, then the cardinality of the set of elements $v \in a + L$ having full support (i.e., $\mathrm{supp}(v) = \mathrm{Finset.univ}$) is at most $3^{|S|}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof embeds the set of full-support vectors in the translate a + L injectively into the space of functions from S to the set β of non-zero pairs in F 2 × F 2. Because a vector with full support has a non-zero coordinate pair at every index, its restriction to S lands in β, which has size 3. Since the coordinate projection onto S is injective on a + L, this restriction map is injective, bounding the number of full-support vectors by |β|^|S| = 3^|S|.
The type β of non-zero pairs in F 2 × F 2 has cardinality 3. automation
We define β to be the subtype of pairs in F 2 × F 2 that are not (0, 0). Rewriting the cardinality of β in terms of Fintype.card using Nat.card_eq_fintype_card allows the decision procedure `decide` to compute |β| = 3 by exhaustive enumeration of the 4 elements of F 2 × F 2.
uses
Nat.card_eq_fintype_cardlet β := { p : F 2 × F 2 // p.1 ≠ 0 ∨ p.2 ≠ 0 } have hβ : Nat.card β = 3 := by rw [Nat.card_eq_fintype_card] decide
Every full-support vector in a + L restricts on S to a well-defined function taking values in β.
Let A be the set of vectors v ∈ a + L with full support (supp v = univ). We define the restriction map f : A → (S → β) sending v to its pair of coordinates at each s ∈ S. Because v has full support, s belongs to univ (Finset.mem_univ) and thus to supp v. By definition of support (Set.mem_toFinset), the coordinate pair (v.1 s, v.2 s) is non-zero, verifying that it belongs to β.
uses
Finset.mem_univ,Set.mem_toFinsetlet A := {v ∈ a +ᵥ (L : Set (V k 2)) | supp v = Finset.univ} let f : A → (S → β) := fun ⟨v, hv⟩ s => ⟨(v.1 s.1, v.2 s.1), by have hsupp : supp v = Finset.univ := hv.2 have hs : s.1 ∈ supp v := by rw [hsupp]; exact Finset.mem_univ s.1 dsimp [supp] at hs rw [Set.mem_toFinset] at hs exact hs⟩
The restriction map f : A → (S → β) is injective.
Suppose f(v₁) = f(v₂) for two vectors v₁, v₂ ∈ A. To deduce v₁ = v₂ as elements of A (Subtype.ext), it suffices to apply the hypothesis hinj that the projection to S is injective on a + L. Evaluating f(v₁) = f(v₂) at each s ∈ S (congr_fun) and projecting onto the first and second components (congr_arg) shows that v₁.1 s = v₂.1 s and v₁.2 s = v₂.2 s for all s ∈ S, so the projections coincide.
uses
Subtype.ext,congr_fun,congr_arghave hf_inj : Function.Injective f := by intro ⟨v1, hv1⟩ ⟨v2, hv2⟩ heq apply Subtype.ext apply hinj hv1.1 hv2.1 ext : 1 · ext s have := congr_fun heq s exact congr_arg (fun (p : β) => p.1.1) this · ext s have := congr_fun heq s exact congr_arg (fun (p : β) => p.1.2) this
The number of full-support vectors in a + L is at most 3^|S|.
Because f is injective into the function space S → β, the cardinality of A is bounded by Nat.card (S → β) (Nat.card_le_card_of_injective). By Nat.card_fun and Nat.card_eq_finsetCard, Nat.card (S → β) = |β|^|S|, which simplifies to 3^|S| using |β| = 3.
uses
Nat.card_le_card_of_injective,Nat.card_fun,Nat.card_eq_finsetCardhave hle := Nat.card_le_card_of_injective f hf_inj rw [Nat.card_fun, hβ, Nat.card_eq_finsetCard] at hle exact hle
Nat.card_eq_fintype_card- for any finite type α, its cardinality as a natural number (Nat.card α) equals its Fintype cardinality (Fintype.card α)
Finset.mem_univ- every element of a finite type α belongs to the universal finset Finset.univ
Set.mem_toFinset- an element belongs to the finset s.toFinset if and only if it belongs to the set s
Subtype.ext- two elements of a subtype are equal if their underlying values are equal
congr_fun- equal functions evaluate to equal values on any input
congr_arg- a function applied to equal arguments yields equal values
Nat.card_le_card_of_injective- an injective function into a finite type implies the cardinality of the domain is at most the cardinality of the codomain
Nat.card_fun- for a finite type α, the cardinality of the function space α → β is (Nat.card β) ^ (Nat.card α)
Nat.card_eq_finsetCard- the cardinality of a finset s coerced to a type is s.card
- The cardinality of β is evaluated computationally by `decide` via exhaustive enumeration of the 4 pairs in F 2 × F 2.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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 Pointwise in/-- An injective projection onto S physical pairs limits the number of full-support vectors on any translate to at most 3^|S|. -/lemma card_full_support_le_of_injective {k : ℕ} (L : Submodule (F 2) (V k 2)) (S : Finset (Fin k)) (a : V k 2) (hinj : Set.InjOn (fun v : V k 2 => ((fun (s : S) => v.1 s.1), (fun (s : S) => v.2 s.1))) (a +ᵥ (L : Set (V k 2)))) : Nat.card {v ∈ a +ᵥ (L : Set (V k 2)) | supp v = Finset.univ} ≤ 3 ^ S.card := by let β := { p : F 2 × F 2 // p.1 ≠ 0 ∨ p.2 ≠ 0 } have hβ : Nat.card β = 3 := by rw [Nat.card_eq_fintype_card] decide let A := {v ∈ a +ᵥ (L : Set (V k 2)) | supp v = Finset.univ} let f : A → (S → β) := fun ⟨v, hv⟩ s => ⟨(v.1 s.1, v.2 s.1), by have hsupp : supp v = Finset.univ := hv.2 have hs : s.1 ∈ supp v := by rw [hsupp]; exact Finset.mem_univ s.1 dsimp [supp] at hs rw [Set.mem_toFinset] at hs exact hs⟩ have hf_inj : Function.Injective f := by intro ⟨v1, hv1⟩ ⟨v2, hv2⟩ heq apply Subtype.ext apply hinj hv1.1 hv2.1 ext : 1 · ext s have := congr_fun heq s exact congr_arg (fun (p : β) => p.1.1) this · ext s have := congr_fun heq s exact congr_arg (fun (p : β) => p.1.2) this have hle := Nat.card_le_card_of_injective f hf_inj rw [Nat.card_fun, hβ, Nat.card_eq_finsetCard] at hle exact hle