cylinder_construction_distance_set
Let $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 $W \le (\mathbb{Z}/p\mathbb{Z})^{2m+1}$ that is totally isotropic with respect to $Q_{2m+1}$ and a vector $e \in (\mathbb{Z}/p\mathbb{Z})^{2m+1}$ orthogonal to $W$ under the standard dot product with $e \notin W$ such that $\kappa := Q_{2m+1}(e) \neq 0$, and for every subset $A \subset \mathbb{Z}/p\mathbb{Z}$, the cylinder set $E_A = \{w + a \cdot e : w \in W, a \in A\}$ satisfies $|E_A| = p^m |A|$ and $\Delta(E_A) = \kappa (A - A)^2$.
Statement
theorem cylinder_construction_distance_set (p : ℕ) [Fact p.Prime] (hp_odd : Odd p) (m : ℕ) : ∃ (W : Submodule (ZMod p) (Fin (2 * m + 1) → ZMod p)) (e : Fin (2 * m + 1) → ZMod p), Module.finrank (ZMod p) W = m ∧ is_totally_isotropic (2 * m + 1) W ∧ (∀ w ∈ W, dotProduct e w = 0) ∧ e ∉ W ∧ let κ := standard_quad (2 * m + 1) e κ ≠ 0 ∧ ∀ A : Set (ZMod p), (cylinder_set (2 * m + 1) W e A).ncard = p ^ m * A.ncard ∧ distance_set (2 * m + 1) (cylinder_set (2 * m + 1) W e A) = diff_sq_scaled κ A
- Formalizes
- arXiv:2610.34758 Lemma 2.3 -- Geometric progressions in distance sets in odd dimensions over prime fields
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- standard_quadThe standard quadratic form $Q_d$ on $(\mathbb{Z}/p\mathbb{Z})^d$, defined by $Q_d(x) = \sum_{i} x_i^2$.
- is_totally_isotropicA subspace $W \subset (\mathbb{Z}/p\mathbb{Z})^d$ is totally isotropic with respect to the standard quadratic form $Q_d$ if $Q_d(w) = 0$…
- distance_setThe distance set $\Delta(E)$ of a subset $E \subset (\mathbb{Z}/p\mathbb{Z})^d$ is the set of values $Q_d(x - y)$ for all $x, y \in E$.
- cylinder_setThe cylinder set $E_A \subset (\mathbb{Z}/p\mathbb{Z})^d$ associated to a subspace $W$, a vector $e$, and a subset…
- diff_sq_scaledThe scaled squared difference set $\kappa (A - A)^2$ for a subset $A \subset \mathbb{Z}/p\mathbb{Z}$ and scalar…
- cylinder_cardLet $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}$.…
- cylinder_distance_setFor any natural numbers $d$ and $p$, any submodule $W \le (\mathbb{Z}/p\mathbb{Z})^d$ that is totally isotropic with respect to $Q_d$, any…
- standard_quad_cons_consFor any natural number $d$, prime $p$, scalars $a, b \in \mathbb{Z}/p\mathbb{Z}$, and vector $v \in (\mathbb{Z}/p\mathbb{Z})^d$,…
- cylinder_construction_stepLet $p$ be prime. Given an $m$-dimensional totally isotropic subspace $W \le (\mathbb{Z}/p\mathbb{Z})^d$ and a vector $e \notin W$…
Read back from the Lean
Given an odd prime natural number $p$ (with typeclass instance Fact p.Prime and hypothesis Odd p) and a natural number $m$, there exist a $\mathbb{Z}/p\mathbb{Z}$-submodule $W \le (\text{Fin}(2m+1) \to \mathbb{Z}/p\mathbb{Z})$ and a vector $e \in (\text{Fin}(2m+1) \to \mathbb{Z}/p\mathbb{Z})$ such that:
1. The rank of $W$ over $\mathbb{Z}/p\mathbb{Z}$ (Module.finrank) is $m$;
2. $W$ is totally isotropic with respect to the standard quadratic form (is_totally_isotropic (2 * m + 1) W);
3. $e$ is orthogonal to every vector in $W$ under the standard dot product (∀ w ∈ W, dotProduct e w = 0);
4. $e \notin W$;
5. Setting $\kappa := \text{standard\_quad}(2m+1, e)$, we have:
a. $\kappa \neq 0$;
b. For every subset $A \subseteq \mathbb{Z}/p\mathbb{Z}$:
- The set cardinality (Set.ncard) of the cylinder set $\{ x \mid \exists w \in W, \exists a \in A, x = w + a \cdot e \}$ is equal to $p^m \cdot \#A$;
- The distance set of this cylinder set under standard_quad equals the scaled difference of squares set $\{ \kappa (a - b)^2 \mid a \in A, b \in 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 theorem is proved by first constructing an $m$-dimensional totally isotropic subspace $W \le (\mathbb{Z}/p\mathbb{Z})^{2m+1}$ and an orthogonal vector $e \notin W$ with $\kappa := Q(e) \neq 0$ via induction on $m$. The base case $m = 0$ uses the zero subspace $\bot$ and the constant vector $(1)$ in $(\mathbb{Z}/p\mathbb{Z})^1$, and the induction step applies `cylinder_construction_step` to lift $W$ and $e$ from dimension $2m+1$ to $(2m+1)+2$. Once $W$ and $e$ are obtained, the cardinality formula $|E_A| = p^m |A|$ follows from `cylinder_card` and the distance set identity $\Delta(E_A) = \kappa (A - A)^2$ follows from `cylinder_distance_set`.
For $m = 0$, the zero submodule $W = \bot \le (\mathbb{Z}/p\mathbb{Z})^1$ has dimension $0$, reducing the base case to verifying isotropy, orthogonality, non-membership, and non-vanishing quadratic norm for the vector $e = (1)$.
We proceed by induction on $m$. In the base case $m = 0$, the ambient space is $(\mathbb{Z}/p\mathbb{Z})^1$. We pick the zero subspace $W = \bot$ and the constant vector $e = (1)$. The rank of $\bot$ is $0$ by `finrank_bot`, leaving four conditions to check.
uses
finrank_botinduction m with | zero => use ⊥ use fun _ => 1 refine ⟨finrank_bot (ZMod p) (Fin 1 → ZMod p), ?_, ?_, ?_, ?_⟩
The zero submodule $W = \bot$ is totally isotropic.
Any element $w \in \bot$ equals $0$ by `Submodule.mem_bot`, and the standard quadratic form on the zero vector evaluates to $0^2 = 0$.
uses
Submodule.mem_bot· intro w hw rw [Submodule.mem_bot] at hw subst hw simp [standard_quad]
The vector $e$ is orthogonal to every vector in $W$.
Any $w \in \bot$ is $0$ by `Submodule.mem_bot`, so the dot product $(1) \cdot w = (1) \cdot 0 = 0$.
uses
Submodule.mem_bot· intro w hw rw [Submodule.mem_bot] at hw subst hw simp
The vector $e$ does not lie in $W$, and its quadratic norm is non-zero.
If $e \in \bot$, then $e = 0$ by `Submodule.mem_bot`. Evaluating at index $0$ via `congr_fun` gives $1 = 0$ in $\mathbb{Z}/p\mathbb{Z}$, an absurdity since $p$ is prime. In addition, the quadratic norm is $Q_1(e) = 1^2 = 1 \neq 0$.
uses
Submodule.mem_bot,congr_fun· intro he rw [Submodule.mem_bot] at he have : (fun (_ : Fin 1) => (1 : ZMod p)) 0 = 0 := congr_fun he 0 norm_num at this · simp [standard_quad]
The inductive step holds: an $(m+1)$-dimensional totally isotropic subspace and orthogonal non-isotropic vector exist in dimension $2(m+1)+1$.
Linear arithmetic rewrites the dimension $2(m+1)+1$ as $(2m+1)+2$. Unpacking the induction hypothesis provides an $m$-dimensional isotropic subspace $W$ and orthogonal vector $e \notin W$ with $Q(e) \neq 0$ in dimension $2m+1$. Then `cylinder_construction_step` extends this pair by two dimensions to obtain an $(m+1)$-dimensional totally isotropic subspace $W'$ and an orthogonal vector $e' \notin W'$ with non-zero quadratic norm.
uses
cylinder_construction_step| succ m ih => have h_eq : 2 * (m + 1) + 1 = (2 * m + 1) + 2 := by omega rw [h_eq] rcases ih with ⟨W, e, hdim, hiso, horth, he, hquad⟩ exact cylinder_construction_step p (2 * m + 1) m W e hdim hiso horth he hquadFor any $m \ge 0$, there exist an $m$-dimensional totally isotropic subspace $W \le (\mathbb{Z}/p\mathbb{Z})^{2m+1}$ and an orthogonal vector $e \notin W$ with $\kappa = Q(e) \neq 0$.
Applying the lemma `cylinder_construction_distance_set_exists` produces the required subspace $W$ and vector $e$, leaving only the cardinality and distance set claims for the cylinder set $E_A$.
uses
cylinder_construction_distance_set_existshave _ := hp_odd rcases cylinder_construction_distance_set_exists p m with ⟨W, e, hdim, hiso, horth, he, hquad⟩ refine ⟨W, e, hdim, hiso, horth, he, hquad, fun A => ⟨?_, ?_⟩⟩
For any subset $A \subseteq \mathbb{Z}/p\mathbb{Z}$, the cylinder set $E_A = W + A \cdot e$ has size $|E_A| = p^m |A|$.
Since $\dim W = m$ over $\mathbb{Z}/p\mathbb{Z}$ and $e \notin W$, the lemma `cylinder_card` implies that the affine slices $W + a \cdot e$ are disjoint of size $p^m$, giving $|E_A| = p^m |A|$.
uses
cylinder_card· exact cylinder_card (2 * m + 1) p m W e hdim he AFor any subset $A \subseteq \mathbb{Z}/p\mathbb{Z}$, the distance set $\Delta(E_A)$ equals $\kappa (A - A)^2$.
By `cylinder_distance_set`, because $W$ is totally isotropic and $e$ is orthogonal to $W$, the cross terms and the quadratic form on $W$ vanish when taking differences of elements in $E_A$, so the distance between $w_1 + a_1 e$ and $w_2 + a_2 e$ reduces to $(a_1 - a_2)^2 Q(e) = \kappa (a_1 - a_2)^2$.
uses
cylinder_distance_set· exact cylinder_distance_set (2 * m + 1) W e hiso horth A
finrank_bot- The dimension of the zero submodule $\bot$ over a nontrivial ring is $0$.
Submodule.mem_bot- An element of a module belongs to the zero submodule if and only if it is the zero element.
congr_fun- If two functions are equal, their values on any argument are equal.
cylinder_construction_step- Given an $m$-dimensional totally isotropic subspace $W$ and an orthogonal non-isotropic vector $e \notin W$ in dimension $d$, there exist an $(m+1)$-dimensional totally isotropic subspace $W'$ and an orthogonal non-isotropic vector $e' \notin W'$ in dimension $d+2$.
cylinder_construction_distance_set_exists- In dimension $2m+1$ over $\mathbb{Z}/p\mathbb{Z}$, there exists an $m$-dimensional totally isotropic subspace $W$ and a vector $e \notin W$ orthogonal to $W$ with non-zero quadratic norm.
cylinder_card- For an $m$-dimensional subspace $W \le (\mathbb{Z}/p\mathbb{Z})^d$ and a vector $e \notin W$, the cylinder set $W + A \cdot e$ has cardinality $p^m |A|$.
cylinder_distance_set- If $W$ is totally isotropic and $e$ is orthogonal to $W$, the distance set of the cylinder $W + A \cdot e$ under the standard quadratic form equals $\kappa (A - A)^2$, where $\kappa = Q(e)$.
- The hypothesis that $p$ is odd (`hp_odd`) is recorded in the theorem statement and noted on line 46, but is not used in the proof; primality of $p$ is sufficient for all steps.
- The proof proceeds by first establishing the inductive existence of the isotropic subspace $W$ and vector $e$ in helper lemma `cylinder_construction_distance_set_exists`, which relies on `cylinder_construction_step`, and then applying `cylinder_card` and `cylinder_distance_set` in the main theorem.
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.
lemma cylinder_construction_distance_set_exists (p : ℕ) [Fact p.Prime] (m : ℕ) : ∃ (W : Submodule (ZMod p) (Fin (2 * m + 1) → ZMod p)) (e : Fin (2 * m + 1) → ZMod p), Module.finrank (ZMod p) W = m ∧ is_totally_isotropic (2 * m + 1) W ∧ (∀ w ∈ W, dotProduct e w = 0) ∧ e ∉ W ∧ standard_quad (2 * m + 1) e ≠ 0 := by induction m with | zero => use ⊥ use fun _ => 1 refine ⟨finrank_bot (ZMod p) (Fin 1 → ZMod p), ?_, ?_, ?_, ?_⟩ · intro w hw rw [Submodule.mem_bot] at hw subst hw simp [standard_quad] · intro w hw rw [Submodule.mem_bot] at hw subst hw simp · intro he rw [Submodule.mem_bot] at he have : (fun (_ : Fin 1) => (1 : ZMod p)) 0 = 0 := congr_fun he 0 norm_num at this · simp [standard_quad] | succ m ih => have h_eq : 2 * (m + 1) + 1 = (2 * m + 1) + 2 := by omega rw [h_eq] rcases ih with ⟨W, e, hdim, hiso, horth, he, hquad⟩ exact cylinder_construction_step p (2 * m + 1) m W e hdim hiso horth he hquad/-- Cylinder construction of distance sets in odd dimensions via isotropic subspaces (Lemma 2.3). -/theorem cylinder_construction_distance_set (p : ℕ) [Fact p.Prime] (hp_odd : Odd p) (m : ℕ) : ∃ (W : Submodule (ZMod p) (Fin (2 * m + 1) → ZMod p)) (e : Fin (2 * m + 1) → ZMod p), Module.finrank (ZMod p) W = m ∧ is_totally_isotropic (2 * m + 1) W ∧ (∀ w ∈ W, dotProduct e w = 0) ∧ e ∉ W ∧ let κ := standard_quad (2 * m + 1) e κ ≠ 0 ∧ ∀ A : Set (ZMod p), (cylinder_set (2 * m + 1) W e A).ncard = p ^ m * A.ncard ∧ distance_set (2 * m + 1) (cylinder_set (2 * m + 1) W e A) = diff_sq_scaled κ A := by have _ := hp_odd rcases cylinder_construction_distance_set_exists p m with ⟨W, e, hdim, hiso, horth, he, hquad⟩ refine ⟨W, e, hdim, hiso, horth, he, hquad, fun A => ⟨?_, ?_⟩⟩ · exact cylinder_card (2 * m + 1) p m W e hdim he A · exact cylinder_distance_set (2 * m + 1) W e hiso horth A