AFTD Auto-Formalizing Theoretical Domains

cylinder_construction_distance_set

theoremverifiedformalization

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

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

    lines 9–13

    uses finrank_bot

      induction m with
      | zero =>
        use ⊥
        use fun _ => 1
        refine ⟨finrank_bot (ZMod p) (Fin 1 → ZMod p), ?_, ?_, ?_, ?_⟩
  2. 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$.

    lines 14–17

    uses Submodule.mem_bot

        · intro w hw
          rw [Submodule.mem_bot] at hw
          subst hw
          simp [standard_quad]
  3. 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$.

    lines 18–21

    uses Submodule.mem_bot

        · intro w hw
          rw [Submodule.mem_bot] at hw
          subst hw
          simp
  4. 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$.

    lines 22–26

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

    lines 27–31

    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 hquad
  6. For 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$.

    lines 46–48

    uses cylinder_construction_distance_set_exists

      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 => ⟨?_, ?_⟩⟩
  7. 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|$.

    line 49

    uses cylinder_card

      · exact cylinder_card (2 * m + 1) p m W e hdim he A
  8. For 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$.

    line 50

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

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

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