cylinder_card
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
- cylinder_construction_distance_setLet $p$ be an odd prime (with $p$ prime and $p$ odd) and let $m \ge 0$ be a natural number. There exist an $m$-dimensional submodule…
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ℤ.
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.
uses
Set.mem_image,Set.mem_prod,Prod.existshave 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⟩
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.
uses
sub_smul,sub_ne_zero.mpr,smul_smul,inv_mul_cancel₀,one_smulhave 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
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.
uses
Subtype.fintype,Nat.card_eq_fintype_card,Module.card_eq_pow_finrank,ZMod.cardhave 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]
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.
uses
Set.ncard_prodrw [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|.
- In Step 3, the proof explicitly supplies a `Fintype W` instance (`Subtype.fintype`) and transitions between set cardinality (`.ncard`), general type cardinality (`Nat.card`), and finite type cardinality (`Fintype.card`) in order to apply the dimension formula `Module.card_eq_pow_finrank`. On paper, this distinction between sets and types is invisible.
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.
/-- 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]