AFTD Auto-Formalizing Theoretical Domains

card_full_support_le_of_injective

theoremverified

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.

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|.

  1. 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.

    lines 7–10

    uses Nat.card_eq_fintype_card

      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
  2. 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 β.

    lines 11–17

    uses Finset.mem_univ, Set.mem_toFinset

      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⟩
  3. 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.

    lines 18–28

    uses Subtype.ext, congr_fun, congr_arg

      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
  4. 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.

    lines 29–31

    uses Nat.card_le_card_of_injective, Nat.card_fun, Nat.card_eq_finsetCard

      have 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

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

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
See it in the graphDiscuss this resultChallenge it