AFTD Auto-Formalizing Theoretical Domains

proj_physical_pairs_coset_bijective

theoremverified

If the coordinate projection v ↦ (v.1|_S, v.2|_S) onto a subset S of physical pairs is a bijection from a subspace L of V_k to (S → F_2) × (S → F_2), then for every vector a, it is also a bijection from the translate a + L to (S → F_2) × (S → F_2).

Statement

open scoped Pointwise in
lemma proj_physical_pairs_coset_bijective {k : ℕ}
    (L : Submodule (F 2) (V k 2)) (S : Finset (Fin k))
    (hbij : Set.BijOn (fun v : V k 2 => ((fun (s : S) => v.1 s.1), (fun (s : S) => v.2 s.1))) (L : Set (V k 2)) Set.univ)
    (a : V k 2) :
    Set.BijOn (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))) Set.univ
Source
arXiv:2610.04621 Lemma 5
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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 ZMod.

Read back from the Lean

For any natural number $k$, any $\mathbb{F}_2$-submodule $L$ of $(\mathrm{Fin}\ k \to \mathbb{F}_2) \times (\mathrm{Fin}\ k \to \mathbb{F}_2)$, and any finset $S \subseteq \mathrm{Fin}\ k$: if the coordinate projection map $v \mapsto (v_1|_S, v_2|_S)$ is a bijection from $L$ onto the entire space $(S \to \mathbb{F}_2) \times (S \to \mathbb{F}_2)$, then for every vector $a \in (\mathrm{Fin}\ k \to \mathbb{F}_2) \times (\mathrm{Fin}\ k \to \mathbb{F}_2)$, the same projection map is also a bijection from the coset $a +ᵥ L$ onto the entire space $(S \to \mathbb{F}_2) \times (S \to \mathbb{F}_2)$.

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

Because the coordinate projection f is additive, translating a vector by a translates its projection by f(a), so f(a + l) = f(a) + f(l). Injectivity on the coset a + L reduces by cancelling f(a) to injectivity on L. Similarly, surjectivity on a + L follows from surjectivity on L by finding a preimage in L for the shifted target y - f(a).

  1. The coordinate projection map f is defined and shown to be additive: f(x + y) = f(x) + f(y) for all x and y.

    We define f(v) as the coordinate projection of both components of v onto the index set S. Since addition in V is defined componentwise, projecting a sum of vectors yields the sum of their projections, verified on each coordinate.

    lines 8–12

      let f : V k 2 → ((S → F 2) × (S → F 2)) :=
        fun v => ((fun (s : S) => v.1 s.1), (fun (s : S) => v.2 s.1))
      have hfadd : ∀ x y : V k 2, f (x + y) = f x + f y := by
        intro x y
        ext s <;> simp [f]
  2. Bijectivity of f on the coset a + L decomposes into checking that f maps into the codomain, is injective on a + L, and is surjective onto the codomain; mapping into the codomain is immediate.

    The goal is rephrased in terms of f, and bijectivity is split into the three standard conditions: target membership, injectivity, and surjectivity. Because the codomain is the universal set, the image of any element trivially belongs to it.

    lines 13–16

    uses Set.mem_univ

      change Set.BijOn f (a +ᵥ (L : Set (V k 2))) Set.univ
      refine ⟨?_, ?_, ?_⟩
      · intro x hx
        exact Set.mem_univ _
  3. The projection f is injective on the coset a + L.

    Let x, y ∈ a + L satisfy f(x) = f(y). By definition of a coset translate, x = a + lx and y = a + ly for some lx, ly ∈ L. By additivity of f, f(a) + f(lx) = f(a) + f(ly). Cancelling f(a) from both sides gives f(lx) = f(ly). Since f is assumed bijective (hence injective) on L, this forces lx = ly, and therefore x = y.

    lines 17–25

    uses Set.mem_vadd_set, vadd_eq_add, add_left_cancel

      · intro x hx y hy hxy
        rw [Set.mem_vadd_set] at hx hy
        obtain ⟨lx, hlx, rfl⟩ := hx
        obtain ⟨ly, hly, rfl⟩ := hy
        simp only [vadd_eq_add] at hxy
        rw [hfadd, hfadd] at hxy
        have hfl : f lx = f ly := add_left_cancel hxy
        have hlxy : lx = ly := hbij.2.1 hlx hly hfl
        rw [hlxy]
  4. The projection f maps the coset a + L surjectively onto the universal set.

    Given any element y in the target universe, consider the shifted element y - f(a). Since f is surjective on L, there is some l ∈ L with f(l) = y - f(a). The translate a + l lies in the coset a + L, and by additivity f(a + l) = f(a) + f(l) = f(a) + (y - f(a)) = y, showing y is in the image of a + L.

    lines 26–33

    uses Set.mem_univ, Set.mem_vadd_set, vadd_eq_add

      · intro y hy
        have hy' : y - f a ∈ f '' (L : Set (V k 2)) := hbij.2.2 (Set.mem_univ _)
        obtain ⟨l, hl, hfl⟩ := hy'
        refine ⟨a + l, ?_, ?_⟩
        · rw [Set.mem_vadd_set]
          exact ⟨l, hl, by rw [vadd_eq_add]⟩
        · rw [hfadd, hfl]
          abel
Set.mem_univ
Every element of a type belongs to the universal set `Set.univ`.
Set.mem_vadd_set
An element x belongs to the translate a +ᵥ t if and only if x = a +ᵥ y for some y ∈ t.
vadd_eq_add
The translation action a +ᵥ b on the same additive type coincides with addition a + b.
add_left_cancel
In an additive structure with left cancellation, a + b = a + c implies b = c.

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/-- Projection onto coordinate pairs is bijective on any coset of a subspace if it is bijective on the subspace. -/lemma proj_physical_pairs_coset_bijective {k : ℕ}    (L : Submodule (F 2) (V k 2)) (S : Finset (Fin k))    (hbij : Set.BijOn (fun v : V k 2 => ((fun (s : S) => v.1 s.1), (fun (s : S) => v.2 s.1))) (L : Set (V k 2)) Set.univ)    (a : V k 2) :    Set.BijOn (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))) Set.univ := by  let f : V k 2 → ((S → F 2) × (S → F 2)) :=    fun v => ((fun (s : S) => v.1 s.1), (fun (s : S) => v.2 s.1))  have hfadd : ∀ x y : V k 2, f (x + y) = f x + f y := by    intro x y    ext s <;> simp [f]  change Set.BijOn f (a +ᵥ (L : Set (V k 2))) Set.univ  refine ⟨?_, ?_, ?_⟩  · intro x hx    exact Set.mem_univ _  · intro x hx y hy hxy    rw [Set.mem_vadd_set] at hx hy    obtain ⟨lx, hlx, rfl⟩ := hx    obtain ⟨ly, hly, rfl⟩ := hy    simp only [vadd_eq_add] at hxy    rw [hfadd, hfadd] at hxy    have hfl : f lx = f ly := add_left_cancel hxy    have hlxy : lx = ly := hbij.2.1 hlx hly hfl    rw [hlxy]  · intro y hy    have hy' : y - f a ∈ f '' (L : Set (V k 2)) := hbij.2.2 (Set.mem_univ _)    obtain ⟨l, hl, hfl⟩ := hy'    refine ⟨a + l, ?_, ?_⟩    · rw [Set.mem_vadd_set]      exact ⟨l, hl, by rw [vadd_eq_add]⟩    · rw [hfadd, hfl]      abel
See it in the graphDiscuss this resultChallenge it