AFTD Auto-Formalizing Theoretical Domains

cylinder_card

theoremverified

Let $p$ be a prime number, and let $W \subseteq (\mathbb{Z}/p\mathbb{Z})^d$ be an $m$-dimensional subspace over $\mathbb{Z}/p\mathbb{Z}$. Let $e \in (\mathbb{Z}/p\mathbb{Z})^d$ with $e \notin W$, and let $A \subseteq \mathbb{Z}/p\mathbb{Z}$. Then the cylinder set $E_A = \{w + a \cdot e : w \in W, a \in A\}$ has cardinality $|E_A| = p^m |A|$.

Statement

theorem cylinder_card
    (d : ℕ) (p : ℕ) [Fact p.Prime] (m : ℕ)
    (W : Submodule (ZMod p) (Fin d → ZMod p)) (e : Fin d → ZMod p)
    (h_dim : Module.finrank (ZMod p) W = m)
    (he : e ∉ W) (A : Set (ZMod p)) :
    (cylinder_set d W e A).ncard = p ^ m * A.ncard
Source
arXiv:2610.34758 Lemma 2.3 proof
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • cylinder_setThe cylinder set $E_A \subset (\mathbb{Z}/p\mathbb{Z})^d$ associated to a subspace $W$, a vector $e$, and a subset…
Used by 1

Read back from the Lean

For any natural numbers $d$, $p$, and $m$, with $p$ prime, any $\mathbb{Z}/p\mathbb{Z}$-submodule $W$ of $(\mathbb{Z}/p\mathbb{Z})^d$ (represented as $\mathrm{Fin}\ d \to \mathbb{Z}/p\mathbb{Z}$), any vector $e \in (\mathbb{Z}/p\mathbb{Z})^d$, and any subset $A \subseteq \mathbb{Z}/p\mathbb{Z}$: if the dimension ($\operatorname{finrank}$) of $W$ over $\mathbb{Z}/p\mathbb{Z}$ is $m$ and $e \notin W$, then the cardinality ($\mathrm{ncard}$) of the cylinder set $\mathrm{cylinder\_set}(d, W, e, A)$ equals $p^m \cdot \mathrm{ncard}(A)$.

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 cylinder set E_A = {w + a • e : w ∈ W, a ∈ A} is expressed as the image of the Cartesian product W × A under the map (w, a) ↦ w + a • e. This map is shown to be injective on W × A because any failure of injectivity would allow solving for e as a linear combination of elements of W, contradicting e ∉ W. Since the map is injective, the cardinality of E_A equals |W × A| = |W| * |A|, which evaluates to p^m * |A| because W is an m-dimensional subspace over the field ℤ/pℤ.

  1. The cylinder set E_A is the image of the Cartesian product W × A under the map (w, a) ↦ w + a • e.

    By definition, E_A consists of all vectors of the form w + a • e with w ∈ W and a ∈ A. Unfolding the definitions of set image and Cartesian product, an element x belongs to the image of W × A under (w, a) ↦ w + a • e if and only if there exist w ∈ W and a ∈ A such that x = w + a • e. Both directions of this equivalence follow directly by unpacking and repacking the existential witnesses.

    lines 8–16

    uses Set.mem_image, Set.mem_prod, Prod.exists

      have h_img : cylinder_set d W e A =
          (fun p : (Fin d → ZMod p) × ZMod p => p.1 + p.2 • e) '' ((W : Set (Fin d → ZMod p)) ×ˢ A) := by
        ext x
        simp only [cylinder_set, Set.mem_image, Set.mem_prod, Prod.exists]
        constructor
        · rintro ⟨w, hw, a, ha, rfl⟩
          exact ⟨w, a, ⟨hw, ha⟩, rfl⟩
        · rintro ⟨w, a, ⟨hw, ha⟩, rfl⟩
          exact ⟨w, hw, a, ha, rfl⟩
  2. The parametrization map (w, a) ↦ w + a • e is injective on W × A.

    Let (w₁, a₁), (w₂, a₂) ∈ W × A satisfy w₁ + a₁ • e = w₂ + a₂ • e. Rearranging the equality using the distributivity of scalar multiplication over subtraction and abelian group arithmetic yields (a₁ - a₂) • e = w₂ - w₁. We then split into two cases: if a₁ = a₂, the equation simplifies to w₁ = w₂, so (w₁, a₁) = (w₂, a₂). If a₁ ≠ a₂, then a₁ - a₂ is a non-zero element of the field ℤ/pℤ, hence invertible; multiplying by its inverse gives e = (a₁ - a₂)⁻¹ • (w₂ - w₁). Since W is a linear subspace containing w₁ and w₂, it is closed under subtraction and scalar multiplication, which implies e ∈ W. This contradicts the hypothesis e ∉ W, completing the injectivity proof.

    lines 17–39

    uses sub_smul, sub_ne_zero.mpr, smul_smul, inv_mul_cancel₀, one_smul

      have h_inj : Set.InjOn (fun p : (Fin d → ZMod p) × ZMod p => p.1 + p.2 • e)
          ((W : Set (Fin d → ZMod p)) ×ˢ A) := by
        intro ⟨w1, a1⟩ hw1 ⟨w2, a2⟩ hw2 h
        dsimp at h
        have hw1' : w1 ∈ W := hw1.1
        have hw2' : w2 ∈ W := hw2.1
        have h_eq : (a1 - a2) • e = w2 - w1 := by
          rw [sub_smul]
          calc
            a1 • e - a2 • e = (w1 + a1 • e) - w1 - a2 • e := by abel
            _ = (w2 + a2 • e) - w1 - a2 • e := by rw [h]
            _ = w2 - w1 := by abel
        by_cases ha : a1 = a2
        · subst ha
          have : w1 = w2 := by simpa using h
          simp [this]
        · have h_inv : (a1 - a2) ≠ 0 := sub_ne_zero.mpr ha
          have h_e : e = (a1 - a2)⁻¹ • (w2 - w1) := by
            rw [← h_eq, smul_smul, inv_mul_cancel₀ h_inv, one_smul]
          have heW : e ∈ W := by
            rw [h_e]
            exact W.smul_mem _ (W.sub_mem hw2' hw1')
          exact (he heW).elim
  3. The subspace W has cardinality p^m.

    As a submodule of the finite vector space (ℤ/pℤ)^d, W is finite (Subtype.fintype). The cardinality of an m-dimensional vector space over the finite field ℤ/pℤ is |ℤ/pℤ|^m by Module.card_eq_pow_finrank. Since |ℤ/pℤ| = p and dim(W) = m, this evaluates to p^m.

    lines 40–44

    uses Subtype.fintype, Nat.card_eq_fintype_card, Module.card_eq_pow_finrank, ZMod.card

      have h_card_W : (W : Set (Fin d → ZMod p)).ncard = p ^ m := by
        classical
        have : Fintype W := Subtype.fintype _
        change Nat.card W = _
        rw [Nat.card_eq_fintype_card, @Module.card_eq_pow_finrank (ZMod p) W, ZMod.card, h_dim]
  4. The cylinder set E_A has cardinality p^m * |A|.

    Because the cylinder set is the image of W × A under an injective map, its cardinality equals the cardinality of W × A. By Set.ncard_prod, |W × A| = |W| * |A|. Substituting |W| = p^m concludes the proof.

    line 45

    uses Set.ncard_prod

      rw [h_img, h_inj.ncard_image, Set.ncard_prod, h_card_W]
Set.mem_image
An element y is in the image f '' s if and only if there exists x ∈ s with f(x) = y.
Set.mem_prod
An ordered pair belongs to the Cartesian product s ×ˢ t if and only if its first component is in s and its second is in t.
Prod.exists
An existential quantifier over a product type is equivalent to nested existential quantifiers over each component.
sub_smul
Scalar multiplication distributes over subtraction of scalars: (r - s) • y = r • y - s • y.
sub_ne_zero.mpr
If two elements are unequal, their difference is non-zero.
smul_smul
Successive scalar multiplications multiply the scalars: a₁ • (a₂ • b) = (a₁ * a₂) • b.
inv_mul_cancel₀
In a group with zero (such as a field), the product of a non-zero element's inverse with the element is 1: a⁻¹ * a = 1.
one_smul
Scalar multiplication by the identity element 1 acts as the identity: 1 • b = b.
Subtype.fintype
A subtype of a finite type with a decidable predicate is finite.
Nat.card_eq_fintype_card
For a finite type, the general cardinality Nat.card equals the finite type cardinality Fintype.card.
Module.card_eq_pow_finrank
A finite-dimensional vector space V over a finite division ring K has cardinality |K|^(dim_K V).
ZMod.card
The finite ring ℤ/nℤ has cardinality n.
Set.ncard_prod
The cardinality of the Cartesian product of two sets is the product of their individual cardinalities: |s ×ˢ t| = |s| * |t|.

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

/-- Cardinality of the cylinder set E_A is p^m * |A|. -/theorem cylinder_card    (d : ℕ) (p : ℕ) [Fact p.Prime] (m : ℕ)    (W : Submodule (ZMod p) (Fin d → ZMod p)) (e : Fin d → ZMod p)    (h_dim : Module.finrank (ZMod p) W = m)    (he : e ∉ W) (A : Set (ZMod p)) :    (cylinder_set d W e A).ncard = p ^ m * A.ncard := by  have h_img : cylinder_set d W e A =      (fun p : (Fin d → ZMod p) × ZMod p => p.1 + p.2 • e) '' ((W : Set (Fin d → ZMod p)) ×ˢ A) := by    ext x    simp only [cylinder_set, Set.mem_image, Set.mem_prod, Prod.exists]    constructor    · rintro ⟨w, hw, a, ha, rfl⟩      exact ⟨w, a, ⟨hw, ha⟩, rfl⟩    · rintro ⟨w, a, ⟨hw, ha⟩, rfl⟩      exact ⟨w, hw, a, ha, rfl⟩  have h_inj : Set.InjOn (fun p : (Fin d → ZMod p) × ZMod p => p.1 + p.2 • e)      ((W : Set (Fin d → ZMod p)) ×ˢ A) := by    intro ⟨w1, a1⟩ hw1 ⟨w2, a2⟩ hw2 h    dsimp at h    have hw1' : w1 ∈ W := hw1.1    have hw2' : w2 ∈ W := hw2.1    have h_eq : (a1 - a2) • e = w2 - w1 := by      rw [sub_smul]      calc        a1 • e - a2 • e = (w1 + a1 • e) - w1 - a2 • e := by abel        _ = (w2 + a2 • e) - w1 - a2 • e := by rw [h]        _ = w2 - w1 := by abel    by_cases ha : a1 = a2    · subst ha      have : w1 = w2 := by simpa using h      simp [this]    · have h_inv : (a1 - a2) ≠ 0 := sub_ne_zero.mpr ha      have h_e : e = (a1 - a2)⁻¹ • (w2 - w1) := by        rw [← h_eq, smul_smul, inv_mul_cancel₀ h_inv, one_smul]      have heW : e ∈ W := by        rw [h_e]        exact W.smul_mem _ (W.sub_mem hw2' hw1')      exact (he heW).elim  have h_card_W : (W : Set (Fin d → ZMod p)).ncard = p ^ m := by    classical    have : Fintype W := Subtype.fintype _    change Nat.card W = _    rw [Nat.card_eq_fintype_card, @Module.card_eq_pow_finrank (ZMod p) W, ZMod.card, h_dim]  rw [h_img, h_inj.ncard_image, Set.ncard_prod, h_card_W]
See it in the graphDiscuss this resultChallenge it