cylinder_construction_step
Let $p$ be prime. Given an $m$-dimensional totally isotropic subspace $W \le (\mathbb{Z}/p\mathbb{Z})^d$ and a vector $e \notin W$ orthogonal to $W$ with $Q_d(e) \neq 0$, there exist an $(m+1)$-dimensional totally isotropic subspace $W' \le (\mathbb{Z}/p\mathbb{Z})^{d+2}$ and a vector $e' \notin W'$ orthogonal to $W'$ with $Q_{d+2}(e') \neq 0$.
Statement
theorem cylinder_construction_step
(p : ℕ) [Fact p.Prime] (d m : ℕ)
(W : Submodule (ZMod p) (Fin d → ZMod p)) (e : Fin d → ZMod p)
(h_dim : Module.finrank (ZMod p) W = m)
(h_iso : is_totally_isotropic d W)
(h_orth : ∀ w ∈ W, dotProduct e w = 0)
(he : e ∉ W)
(hκ : standard_quad d e ≠ 0) :
∃ (W' : Submodule (ZMod p) (Fin (d + 2) → ZMod p)) (e' : Fin (d + 2) → ZMod p),
Module.finrank (ZMod p) W' = m + 1 ∧
is_totally_isotropic (d + 2) W' ∧
(∀ w ∈ W', dotProduct e' w = 0) ∧
e' ∉ W' ∧
standard_quad (d + 2) e' ≠ 0- Source
- step towards cylinder_construction_distance_set
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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$,…
- 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$…
- standard_quadThe standard quadratic form $Q_d$ on $(\mathbb{Z}/p\mathbb{Z})^d$, defined by $Q_d(x) = \sum_{i} x_i^2$.
- 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…
The proof, explained
Over a prime field ℤ/pℤ, every element can be written as a sum of two squares, so we choose scalars x and y such that x^2 + y^2 = -Q_d(e). Embedding (ℤ/pℤ)^d into (ℤ/pℤ)^{d+2} by prepending two zeros, we extend the isotropic subspace emb(W) by the vector w* = (x, y, e), whose quadratic form vanishes precisely because x^2 + y^2 + Q(e) = 0. Since e ∉ W, w* is linearly independent of emb(W), producing an (m+1)-dimensional totally isotropic subspace W' = emb(W) ⊕ span{w*}. Finally, the vector e* = (-y, x, 0) is orthogonal to W' and satisfies Q(e*) = x^2 + y^2 = -Q(e) ≠ 0, ensuring e* ∉ W'.
The embedding map v ↦ (0, 0, v) from (ℤ/pℤ)^d to (ℤ/pℤ)^{d+2} is a linear map.
We verify additivity and compatibility with scalar multiplication coordinatewise using Fin.cases on indices in Fin (d+2). The first two coordinates are zero in both the sum or scaled vector and the embedded vector, while all remaining coordinates agree with the underlying addition and scaling on (ℤ/pℤ)^d.
uses
Fin.cases,Pi.add_apply,Pi.smul_applymap_add' v w := by funext i refine Fin.cases ?_ (fun j => ?_) i · simp [Pi.add_apply] · refine Fin.cases ?_ (fun k => ?_) j · simp [Pi.add_apply] · simp [Pi.add_apply] map_smul' c v := by funext i refine Fin.cases ?_ (fun j => ?_) i · simp [Pi.smul_apply] · refine Fin.cases ?_ (fun k => ?_) j · simp [Pi.smul_apply] · simp [Pi.smul_apply]
The embedding preserves the standard quadratic form: Q_{d+2}(emb(v)) = Q_d(v).
Using standard_quad_cons_cons, the quadratic form on (0, 0, v) decomposes into 0^2 + 0^2 plus the quadratic form on the tail v, which simplifies directly to Q_d(v).
uses
standard_quad_cons_conslemma cylinder_construction_step_embed_quad {p : ℕ} (d : ℕ) (v : Fin d → ZMod p) : standard_quad (d+2) (cylinder_construction_step_embed d p v) = standard_quad d v := by show standard_quad (d+2) (Matrix.vecCons 0 (Matrix.vecCons 0 v)) = standard_quad d v rw [standard_quad_cons_cons] simp
The dot product of an embedded vector emb(v) with w*(x, y, e) = (x, y, e) equals v · e.
In the dot product of (0, 0, v) and (x, y, e), the first two coordinates contribute 0 * x + 0 * y = 0, leaving only the sum of products of the tail coordinates v · e.
lemma cylinder_construction_step_embed_wstar_dot {p : ℕ} (d : ℕ) (x y : ZMod p) (e v : Fin d → ZMod p) : dotProduct (cylinder_construction_step_embed d p v) (cylinder_construction_step_wstar x y e) = dotProduct v e := by simp [cylinder_construction_step_embed, cylinder_construction_step_wstar]
The quadratic form on w*(x, y, e) = (x, y, e) is x^2 + y^2 + Q_d(e).
Applying standard_quad_cons_cons splits off the first two coordinates x^2 and y^2 from the quadratic form of the tail vector e.
uses
standard_quad_cons_conslemma cylinder_construction_step_wstar_quad {p : ℕ} (d : ℕ) (x y : ZMod p) (e : Fin d → ZMod p) : standard_quad (d+2) (cylinder_construction_step_wstar x y e) = x^2 + y^2 + standard_quad d e := by show standard_quad (d+2) (Matrix.vecCons x (Matrix.vecCons y e)) = x^2+y^2+standard_quad d e rw [standard_quad_cons_cons]
The quadratic form on e*(x, y) = (-y, x, 0) is x^2 + y^2.
Applying standard_quad_cons_cons gives (-y)^2 + x^2 + Q_d(0). Since (-y)^2 = y^2 and the quadratic form on the zero vector vanishes, this simplifies algebraically to x^2 + y^2.
uses
standard_quad_cons_conslemma cylinder_construction_step_estar_quad {p : ℕ} (d : ℕ) (x y : ZMod p) : standard_quad (d+2) (cylinder_construction_step_estar (p:=p) (d:=d) x y) = x^2 + y^2 := by show standard_quad (d+2) (Matrix.vecCons (-y) (Matrix.vecCons x (0 : Fin d → ZMod p))) = x^2+y^2 rw [standard_quad_cons_cons] simp [standard_quad] ring
The vector e*(x, y) = (-y, x, 0) is orthogonal to every embedded vector emb(v) = (0, 0, v).
In the dot product of (-y, x, 0) and (0, 0, v), each coordinate has at least one zero factor: the first two coordinates are zero in the embedded vector, and the remaining d coordinates are zero in e*(x, y).
lemma cylinder_construction_step_estar_embed_dot {p : ℕ} (d : ℕ) (x y : ZMod p) (v : Fin d → ZMod p) : dotProduct (cylinder_construction_step_estar (p:=p) (d:=d) x y) (cylinder_construction_step_embed d p v) = 0 := by simp [cylinder_construction_step_estar, cylinder_construction_step_embed]
The vector e*(x, y) is orthogonal to w*(x, y, e).
The dot product of (-y, x, 0) and (x, y, e) computes as (-y) * x + x * y + 0 · e = -yx + xy = 0.
lemma cylinder_construction_step_estar_wstar_dot {p : ℕ} (d : ℕ) (x y : ZMod p) (e : Fin d → ZMod p) : dotProduct (cylinder_construction_step_estar (p:=p) (d:=d) x y) (cylinder_construction_step_wstar x y e) = 0 := by simp [cylinder_construction_step_estar, cylinder_construction_step_wstar] ring
The embedding map emb is injective.
Assuming emb(v) = emb(w), evaluating both functions at coordinate k + 2 (via Fin.succ (Fin.succ k)) shows that v k = w k for every k in Fin d, so v = w by function extensionality.
uses
congrArg,Fin.succlemma cylinder_construction_step_embed_injective {p : ℕ} (d : ℕ) : Function.Injective (cylinder_construction_step_embed d p) := by intro v w h funext k have := congrArg (fun f => f (Fin.succ (Fin.succ k))) h simpa [cylinder_construction_step_embed] using this
The quadratic form on a sum satisfies Q(a + b) = Q(a) + Q(b) + 2(a · b).
Expanding each term (a_i + b_i)^2 as a_i^2 + b_i^2 + 2 a_i b_i and distributing the finite summation across the three terms separates the expression into Q(a) + Q(b) + 2(a · b).
uses
Finset.sum_congr,Finset.sum_add_distrib,Finset.mul_sumlemma cylinder_construction_step_quad_add {p : ℕ} (n : ℕ) (a b : Fin n → ZMod p) : standard_quad n (a + b) = standard_quad n a + standard_quad n b + 2 * dotProduct a b := by simp only [standard_quad, dotProduct, Pi.add_apply] rw [show (∑ i, (a i + b i)^2) = ∑ i, (a i^2 + b i^2 + 2*(a i * b i)) from Finset.sum_congr rfl (fun i _ => by ring)] rw [Finset.sum_add_distrib, Finset.sum_add_distrib, ← Finset.mul_sum]
The quadratic form satisfies Q(c • a) = c^2 Q(a).
Each coordinate term (c • a_i)^2 equals c^2 a_i^2. Factoring c^2 out of the summation gives c^2 Q(a).
uses
Finset.sum_congr,smul_eq_mul,Finset.mul_sumlemma cylinder_construction_step_quad_smul {p : ℕ} (n : ℕ) (c : ZMod p) (a : Fin n → ZMod p) : standard_quad n (c • a) = c^2 * standard_quad n a := by simp only [standard_quad, Pi.smul_apply] rw [show (∑ i, (c • a i)^2) = ∑ i, c^2 * (a i)^2 from Finset.sum_congr rfl (fun i _ => by rw [smul_eq_mul]; ring)] rw [Finset.mul_sum]
Find x, y with x^2 + y^2 = -Q_d(e) and define the extended submodule W' and vector e*.
Since p is prime, every element in ℤ/pℤ is a sum of two squares by ZMod.sq_add_sq, yielding x and y such that x^2 + y^2 = -Q_d(e). We define emb : (ℤ/pℤ)^d → (ℤ/pℤ)^{d+2}, w* = (x, y, e), e* = (-y, x, 0), and W' = emb(W) + span{w*}, and record that emb is injective.
uses
ZMod.sq_add_sq,cylinder_construction_step_embed_injective/-- Inductive step for isotropic subspace construction: given an m-dimensional totally isotropic subspace W in (ZMod p)^d and an orthogonal anisotropic vector e not in W, there exist an (m+1)-dimensional totally isotropic subspace W' in (ZMod p)^(d+2) and an orthogonal anisotropic vector e' not in W'. -/ theorem cylinder_construction_step (p : ℕ) [Fact p.Prime] (d m : ℕ) (W : Submodule (ZMod p) (Fin d → ZMod p)) (e : Fin d → ZMod p) (h_dim : Module.finrank (ZMod p) W = m) (h_iso : is_totally_isotropic d W) (h_orth : ∀ w ∈ W, dotProduct e w = 0) (he : e ∉ W) (hκ : standard_quad d e ≠ 0) : ∃ (W' : Submodule (ZMod p) (Fin (d + 2) → ZMod p)) (e' : Fin (d + 2) → ZMod p), Module.finrank (ZMod p) W' = m + 1 ∧ is_totally_isotropic (d + 2) W' ∧ (∀ w ∈ W', dotProduct e' w = 0) ∧ e' ∉ W' ∧ standard_quad (d + 2) e' ≠ 0 := by obtain ⟨x, y, hxy⟩ := ZMod.sq_add_sq p (-(standard_quad d e)) let emb := cylinder_construction_step_embed d p let wstar := cylinder_construction_step_wstar x y e let estar := cylinder_construction_step_estar (p:=p) (d:=d) x y let W' : Submodule (ZMod p) (Fin (d+2) → ZMod p) := W.map emb ⊔ Submodule.span (ZMod p) {wstar} have hinj : Function.Injective emb := cylinder_construction_step_embed_injective d
The extended vector w* is isotropic (Q_{d+2}(w*) = 0) and nonzero.
By cylinder_construction_step_wstar_quad, Q_{d+2}(w*) = x^2 + y^2 + Q_d(e) = -Q_d(e) + Q_d(e) = 0. Furthermore, if w* were 0, inspecting its tail coordinates would imply e = 0, contradicting Q_d(e) ≠ 0.
uses
cylinder_construction_step_wstar_quad,neg_add_cancel,congrArg,Fin.succhave hwstar_quad0 : standard_quad (d+2) wstar = 0 := by have hq : standard_quad (d+2) wstar = x^2 + y^2 + standard_quad d e := by simpa only [wstar] using cylinder_construction_step_wstar_quad d x y e rw [hq, hxy, neg_add_cancel] have hwstar_ne : wstar ≠ 0 := by intro h have he0 : e = 0 := by funext k have := congrArg (fun f => f (Fin.succ (Fin.succ k))) h simpa [wstar, cylinder_construction_step_wstar] using this apply hκ rw [he0] simp [standard_quad]
The intersection emb(W) ∩ span{w*} is trivial: emb(W) ⊓ span{w*} = ⊥.
First, w* cannot belong to emb(W), because any preimage v ∈ W would have to equal e on the tail coordinates, contradicting e ∉ W. Second, any element in the intersection has the form c • w* ∈ emb(W). If c ≠ 0, multiplying by c⁻¹ would place w* in emb(W), a contradiction. Thus c = 0, proving the intersection is trivial.
uses
Submodule.mem_map,congrArg,Fin.succ,Submodule.eq_bot_iff,Submodule.mem_inf,Submodule.mem_span_singleton,inv_mul_cancel₀,Submodule.smul_memhave hwstar_notmem : wstar ∉ W.map emb := by intro h rw [Submodule.mem_map] at h obtain ⟨v, hv, hvq⟩ := h have hve : v = e := by funext k have := congrArg (fun f => f (Fin.succ (Fin.succ k))) hvq simpa [emb, cylinder_construction_step_embed, wstar, cylinder_construction_step_wstar] using this exact he (hve ▸ hv) have hdisj : W.map emb ⊓ Submodule.span (ZMod p) {wstar} = ⊥ := by rw [Submodule.eq_bot_iff] intro z hz rw [Submodule.mem_inf] at hz obtain ⟨hz1, hz2⟩ := hz rw [Submodule.mem_span_singleton] at hz2 obtain ⟨c, hc⟩ := hz2 by_cases hc0 : c = 0 · rw [hc0, zero_smul] at hc; exact hc.symm · exfalso apply hwstar_notmem have hcw : wstar = c⁻¹ • z := by rw [← hc, smul_smul, inv_mul_cancel₀ hc0, one_smul] rw [hcw] exact Submodule.smul_mem _ _ hz1
The dimension of W' is m + 1.
Injectivity of emb implies dim emb(W) = dim W = m by Submodule.equivMapOfInjective. Because w* ≠ 0, dim span{w*} = 1 by finrank_span_singleton. Since their intersection is trivial, the submodule dimension formula gives dim W' = m + 1.
uses
Submodule.equivMapOfInjective,finrank_span_singleton,Submodule.finrank_sup_add_finrank_inf_eq,finrank_bot,add_zerohave hdim_map : Module.finrank (ZMod p) ↥(W.map emb) = m := (Submodule.equivMapOfInjective emb hinj W).finrank_eq.symm.trans h_dim have hspan : Module.finrank (ZMod p) ↥(Submodule.span (ZMod p) {wstar}) = 1 := finrank_span_singleton hwstar_ne have hW'_dim : Module.finrank (ZMod p) W' = m + 1 := by have hsup := Submodule.finrank_sup_add_finrank_inf_eq (W.map emb) (Submodule.span (ZMod p) {wstar}) rw [hdisj, hdim_map, hspan, finrank_bot, add_zero] at hsup simpa only [W'] using hsup
The subspace W' is totally isotropic: every w ∈ W' satisfies Q_{d+2}(w) = 0.
Any w ∈ W' decomposes as emb(v) + c • w* for some v ∈ W and scalar c. Expanding Q_{d+2}(w) produces Q_{d+2}(emb(v)) + c^2 Q_{d+2}(w*) + 2 c (emb(v) · w*). The first term vanishes because v ∈ W and W is totally isotropic; the second vanishes because w* is isotropic; and the cross term vanishes because emb(v) · w* = v · e = 0 by orthogonality of e to W. Thus Q_{d+2}(w) = 0.
uses
Submodule.mem_sup,Submodule.mem_map,Submodule.mem_span_singleton,cylinder_construction_step_quad_add,cylinder_construction_step_quad_smul,cylinder_construction_step_embed_quad,dotProduct_smul,cylinder_construction_step_embed_wstar_dot,dotProduct_commhave hW'_total : is_totally_isotropic (d+2) W' := by intro w hw dsimp only [W'] at hw rw [Submodule.mem_sup] at hw obtain ⟨a, ha, b, hb, hwab⟩ := hw rw [Submodule.mem_map] at ha obtain ⟨v, hv, rfl⟩ := ha rw [Submodule.mem_span_singleton] at hb obtain ⟨c, rfl⟩ := hb rw [← hwab] rw [cylinder_construction_step_quad_add, cylinder_construction_step_quad_smul] have h1 : standard_quad (d+2) (emb v) = 0 := by dsimp only [emb] rw [cylinder_construction_step_embed_quad, h_iso v hv] have h3 : dotProduct (emb v) (c • wstar) = 0 := by rw [dotProduct_smul] have hd : dotProduct (emb v) wstar = dotProduct v e := by dsimp only [emb, wstar] exact cylinder_construction_step_embed_wstar_dot d x y e v rw [hd, dotProduct_comm v e, h_orth v hv] simp rw [h1, hwstar_quad0, h3] ring
The vector e* is orthogonal to every vector in W'.
For any w = emb(v) + c • w* in W', the dot product e* · w expands to (e* · emb(v)) + c (e* · w*). Both terms vanish because e* is orthogonal to the image of the embedding and to w*, so e* · w = 0.
uses
Submodule.mem_sup,Submodule.mem_map,Submodule.mem_span_singleton,dotProduct_add,cylinder_construction_step_estar_embed_dot,dotProduct_smul,cylinder_construction_step_estar_wstar_dot,add_zerohave horth : ∀ w ∈ W', dotProduct estar w = 0 := by intro w hw dsimp only [W'] at hw rw [Submodule.mem_sup] at hw obtain ⟨a, ha, b, hb, hwab⟩ := hw rw [Submodule.mem_map] at ha obtain ⟨v, hv, rfl⟩ := ha rw [Submodule.mem_span_singleton] at hb obtain ⟨c, rfl⟩ := hb rw [← hwab, dotProduct_add] have h1 : dotProduct estar (emb v) = 0 := by dsimp only [estar, emb] exact cylinder_construction_step_estar_embed_dot d x y v have h2 : dotProduct estar (c • wstar) = 0 := by rw [dotProduct_smul] have hd : dotProduct estar wstar = 0 := by dsimp only [estar, wstar] exact cylinder_construction_step_estar_wstar_dot d x y e rw [hd]; simp rw [h1, h2, add_zero]
The vector e* has nonzero quadratic form and does not belong to W', completing the proof.
We have Q_{d+2}(e*) = x^2 + y^2 = -Q_d(e) ≠ 0 because Q_d(e) ≠ 0. If e* were in W', it would be isotropic since W' is totally isotropic, contradicting Q_{d+2}(e*) ≠ 0. Hence e* ∉ W', and the pair (W', e*) witnesses the conclusion of the theorem.
uses
cylinder_construction_step_estar_quadhave hQestar : standard_quad (d+2) estar ≠ 0 := by have hq : standard_quad (d+2) estar = x^2 + y^2 := by simpa only [estar] using cylinder_construction_step_estar_quad (p:=p) (d:=d) x y rw [hq, hxy] exact neg_ne_zero.mpr hκ have hnotmem : estar ∉ W' := by intro h exact hQestar (hW'_total estar h) exact ⟨W', estar, hW'_dim, hW'_total, horth, hnotmem, hQestar⟩
Fin.cases- Proof by cases for elements of Fin (n+1), separating the first element 0 from successors i.succ.
Pi.add_apply- Pointwise addition of functions: (f + g) i = f i + g i.
Pi.smul_apply- Pointwise scalar multiplication of functions: (c • f) i = c • f i.
standard_quad_cons_cons- Prepending two coordinates a and b to a vector v adds a^2 + b^2 to its standard quadratic form.
congrArg- Function application preserves equality: if a = b then f a = f b.
Fin.succ- The successor embedding mapping Fin n into Fin (n+1).
Finset.sum_congr- Sums of equal functions over the same finite set are equal.
Finset.sum_add_distrib- Distributivity of finite summation over addition: ∑ (f + g) = ∑ f + ∑ g.
Finset.mul_sum- A constant factors out of a finite sum: c * ∑ f = ∑ (c * f).
smul_eq_mul- Scalar multiplication of ring elements by each other coincides with multiplication: a • b = a * b.
ZMod.sq_add_sq- For any prime p, every element of ℤ/pℤ is a sum of two squares: x = a^2 + b^2.
cylinder_construction_step_embed_injective- The linear embedding from (Fin d → ℤ/pℤ) to (Fin (d+2) → ℤ/pℤ) prepending two zeros is injective.
cylinder_construction_step_wstar_quad- The quadratic form on the vector w*(x, y, e) evaluates to x^2 + y^2 + Q_d(e).
neg_add_cancel- Adding the additive inverse of an element cancels it: -a + a = 0.
Submodule.mem_map- An element belongs to the image of a submodule under a linear map if and only if it is the image of some element in the submodule.
Submodule.eq_bot_iff- A submodule is the zero submodule if and only if all its elements are zero.
Submodule.mem_inf- An element belongs to the intersection of two submodules if and only if it belongs to both.
Submodule.mem_span_singleton- An element belongs to the span of a single vector if and only if it is a scalar multiple of that vector.
inv_mul_cancel₀- For any nonzero element in a division ring, its inverse satisfies a⁻¹ * a = 1.
Submodule.smul_mem- A submodule is closed under scalar multiplication.
Submodule.equivMapOfInjective- An injective linear map restricts to a linear equivalence between a submodule and its image.
finrank_span_singleton- The dimension of the span of a nonzero vector over a division ring is 1.
Submodule.finrank_sup_add_finrank_inf_eq- The dimension theorem for submodules: dim(s + t) + dim(s ∩ t) = dim(s) + dim(t).
finrank_bot- The dimension of the trivial subspace {0} is 0.
add_zero- Adding zero to any element leaves it unchanged: a + 0 = a.
Submodule.mem_sup- An element belongs to the sum of two submodules if and only if it can be decomposed as a sum of elements from each.
cylinder_construction_step_quad_add- The standard quadratic form satisfies Q(a + b) = Q(a) + Q(b) + 2(a · b).
cylinder_construction_step_quad_smul- The standard quadratic form satisfies Q(c • a) = c^2 Q(a).
cylinder_construction_step_embed_quad- The coordinate embedding preserves the quadratic form: Q_{d+2}(emb(v)) = Q_d(v).
dotProduct_smul- The dot product is linear in its second argument with respect to scalar multiplication: v · (c • w) = c • (v · w).
cylinder_construction_step_embed_wstar_dot- The dot product of emb(v) with w*(x, y, e) equals the tail dot product v · e.
dotProduct_comm- The dot product is symmetric: v · w = w · v.
dotProduct_add- The dot product distributes over addition in its second argument: u · (v + w) = u · v + u · w.
cylinder_construction_step_estar_embed_dot- The vector e*(x, y) is orthogonal to every vector in the image of the embedding.
cylinder_construction_step_estar_wstar_dot- The vector e*(x, y) is orthogonal to w*(x, y, e).
cylinder_construction_step_estar_quad- The quadratic form on e*(x, y) evaluates to x^2 + y^2.
- The Lean formalization prefixes the main inductive step with several auxiliary definitions and lemmas (establishing linearity, injectivity, and quadratic form identities for the embedding and extended vectors) that would typically be treated as straightforward computations in a mathematical paper.
- Vectors in (ℤ/pℤ)^{d+2} are represented functionally using Matrix.vecCons to prepend coordinates.
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.
open Matrixdef cylinder_construction_step_embed (d p : ℕ) : (Fin d → ZMod p) →ₗ[ZMod p] (Fin (d+2) → ZMod p) where toFun v := Matrix.vecCons 0 (Matrix.vecCons 0 v) map_add' v w := by funext i refine Fin.cases ?_ (fun j => ?_) i · simp [Pi.add_apply] · refine Fin.cases ?_ (fun k => ?_) j · simp [Pi.add_apply] · simp [Pi.add_apply] map_smul' c v := by funext i refine Fin.cases ?_ (fun j => ?_) i · simp [Pi.smul_apply] · refine Fin.cases ?_ (fun k => ?_) j · simp [Pi.smul_apply] · simp [Pi.smul_apply]def cylinder_construction_step_wstar {p : ℕ} {d : ℕ} (x y : ZMod p) (e : Fin d → ZMod p) : Fin (d+2) → ZMod p := Matrix.vecCons x (Matrix.vecCons y e)def cylinder_construction_step_estar {p : ℕ} {d : ℕ} (x y : ZMod p) : Fin (d+2) → ZMod p := Matrix.vecCons (-y) (Matrix.vecCons x (0 : Fin d → ZMod p))lemma cylinder_construction_step_embed_quad {p : ℕ} (d : ℕ) (v : Fin d → ZMod p) : standard_quad (d+2) (cylinder_construction_step_embed d p v) = standard_quad d v := by show standard_quad (d+2) (Matrix.vecCons 0 (Matrix.vecCons 0 v)) = standard_quad d v rw [standard_quad_cons_cons] simplemma cylinder_construction_step_embed_wstar_dot {p : ℕ} (d : ℕ) (x y : ZMod p) (e v : Fin d → ZMod p) : dotProduct (cylinder_construction_step_embed d p v) (cylinder_construction_step_wstar x y e) = dotProduct v e := by simp [cylinder_construction_step_embed, cylinder_construction_step_wstar]lemma cylinder_construction_step_wstar_quad {p : ℕ} (d : ℕ) (x y : ZMod p) (e : Fin d → ZMod p) : standard_quad (d+2) (cylinder_construction_step_wstar x y e) = x^2 + y^2 + standard_quad d e := by show standard_quad (d+2) (Matrix.vecCons x (Matrix.vecCons y e)) = x^2+y^2+standard_quad d e rw [standard_quad_cons_cons]lemma cylinder_construction_step_estar_quad {p : ℕ} (d : ℕ) (x y : ZMod p) : standard_quad (d+2) (cylinder_construction_step_estar (p:=p) (d:=d) x y) = x^2 + y^2 := by show standard_quad (d+2) (Matrix.vecCons (-y) (Matrix.vecCons x (0 : Fin d → ZMod p))) = x^2+y^2 rw [standard_quad_cons_cons] simp [standard_quad] ringlemma cylinder_construction_step_estar_embed_dot {p : ℕ} (d : ℕ) (x y : ZMod p) (v : Fin d → ZMod p) : dotProduct (cylinder_construction_step_estar (p:=p) (d:=d) x y) (cylinder_construction_step_embed d p v) = 0 := by simp [cylinder_construction_step_estar, cylinder_construction_step_embed]lemma cylinder_construction_step_estar_wstar_dot {p : ℕ} (d : ℕ) (x y : ZMod p) (e : Fin d → ZMod p) : dotProduct (cylinder_construction_step_estar (p:=p) (d:=d) x y) (cylinder_construction_step_wstar x y e) = 0 := by simp [cylinder_construction_step_estar, cylinder_construction_step_wstar] ringlemma cylinder_construction_step_embed_injective {p : ℕ} (d : ℕ) : Function.Injective (cylinder_construction_step_embed d p) := by intro v w h funext k have := congrArg (fun f => f (Fin.succ (Fin.succ k))) h simpa [cylinder_construction_step_embed] using thislemma cylinder_construction_step_quad_add {p : ℕ} (n : ℕ) (a b : Fin n → ZMod p) : standard_quad n (a + b) = standard_quad n a + standard_quad n b + 2 * dotProduct a b := by simp only [standard_quad, dotProduct, Pi.add_apply] rw [show (∑ i, (a i + b i)^2) = ∑ i, (a i^2 + b i^2 + 2*(a i * b i)) from Finset.sum_congr rfl (fun i _ => by ring)] rw [Finset.sum_add_distrib, Finset.sum_add_distrib, ← Finset.mul_sum]lemma cylinder_construction_step_quad_smul {p : ℕ} (n : ℕ) (c : ZMod p) (a : Fin n → ZMod p) : standard_quad n (c • a) = c^2 * standard_quad n a := by simp only [standard_quad, Pi.smul_apply] rw [show (∑ i, (c • a i)^2) = ∑ i, c^2 * (a i)^2 from Finset.sum_congr rfl (fun i _ => by rw [smul_eq_mul]; ring)] rw [Finset.mul_sum]/-- Inductive step for isotropic subspace construction: given an m-dimensional totally isotropic subspace W in (ZMod p)^d and an orthogonal anisotropic vector e not in W, there exist an (m+1)-dimensional totally isotropic subspace W' in (ZMod p)^(d+2) and an orthogonal anisotropic vector e' not in W'. -/theorem cylinder_construction_step (p : ℕ) [Fact p.Prime] (d m : ℕ) (W : Submodule (ZMod p) (Fin d → ZMod p)) (e : Fin d → ZMod p) (h_dim : Module.finrank (ZMod p) W = m) (h_iso : is_totally_isotropic d W) (h_orth : ∀ w ∈ W, dotProduct e w = 0) (he : e ∉ W) (hκ : standard_quad d e ≠ 0) : ∃ (W' : Submodule (ZMod p) (Fin (d + 2) → ZMod p)) (e' : Fin (d + 2) → ZMod p), Module.finrank (ZMod p) W' = m + 1 ∧ is_totally_isotropic (d + 2) W' ∧ (∀ w ∈ W', dotProduct e' w = 0) ∧ e' ∉ W' ∧ standard_quad (d + 2) e' ≠ 0 := by obtain ⟨x, y, hxy⟩ := ZMod.sq_add_sq p (-(standard_quad d e)) let emb := cylinder_construction_step_embed d p let wstar := cylinder_construction_step_wstar x y e let estar := cylinder_construction_step_estar (p:=p) (d:=d) x y let W' : Submodule (ZMod p) (Fin (d+2) → ZMod p) := W.map emb ⊔ Submodule.span (ZMod p) {wstar} have hinj : Function.Injective emb := cylinder_construction_step_embed_injective d have hwstar_quad0 : standard_quad (d+2) wstar = 0 := by have hq : standard_quad (d+2) wstar = x^2 + y^2 + standard_quad d e := by simpa only [wstar] using cylinder_construction_step_wstar_quad d x y e rw [hq, hxy, neg_add_cancel] have hwstar_ne : wstar ≠ 0 := by intro h have he0 : e = 0 := by funext k have := congrArg (fun f => f (Fin.succ (Fin.succ k))) h simpa [wstar, cylinder_construction_step_wstar] using this apply hκ rw [he0] simp [standard_quad] have hwstar_notmem : wstar ∉ W.map emb := by intro h rw [Submodule.mem_map] at h obtain ⟨v, hv, hvq⟩ := h have hve : v = e := by funext k have := congrArg (fun f => f (Fin.succ (Fin.succ k))) hvq simpa [emb, cylinder_construction_step_embed, wstar, cylinder_construction_step_wstar] using this exact he (hve ▸ hv) have hdisj : W.map emb ⊓ Submodule.span (ZMod p) {wstar} = ⊥ := by rw [Submodule.eq_bot_iff] intro z hz rw [Submodule.mem_inf] at hz obtain ⟨hz1, hz2⟩ := hz rw [Submodule.mem_span_singleton] at hz2 obtain ⟨c, hc⟩ := hz2 by_cases hc0 : c = 0 · rw [hc0, zero_smul] at hc; exact hc.symm · exfalso apply hwstar_notmem have hcw : wstar = c⁻¹ • z := by rw [← hc, smul_smul, inv_mul_cancel₀ hc0, one_smul] rw [hcw] exact Submodule.smul_mem _ _ hz1 have hdim_map : Module.finrank (ZMod p) ↥(W.map emb) = m := (Submodule.equivMapOfInjective emb hinj W).finrank_eq.symm.trans h_dim have hspan : Module.finrank (ZMod p) ↥(Submodule.span (ZMod p) {wstar}) = 1 := finrank_span_singleton hwstar_ne have hW'_dim : Module.finrank (ZMod p) W' = m + 1 := by have hsup := Submodule.finrank_sup_add_finrank_inf_eq (W.map emb) (Submodule.span (ZMod p) {wstar}) rw [hdisj, hdim_map, hspan, finrank_bot, add_zero] at hsup simpa only [W'] using hsup have hW'_total : is_totally_isotropic (d+2) W' := by intro w hw dsimp only [W'] at hw rw [Submodule.mem_sup] at hw obtain ⟨a, ha, b, hb, hwab⟩ := hw rw [Submodule.mem_map] at ha obtain ⟨v, hv, rfl⟩ := ha rw [Submodule.mem_span_singleton] at hb obtain ⟨c, rfl⟩ := hb rw [← hwab] rw [cylinder_construction_step_quad_add, cylinder_construction_step_quad_smul] have h1 : standard_quad (d+2) (emb v) = 0 := by dsimp only [emb] rw [cylinder_construction_step_embed_quad, h_iso v hv] have h3 : dotProduct (emb v) (c • wstar) = 0 := by rw [dotProduct_smul] have hd : dotProduct (emb v) wstar = dotProduct v e := by dsimp only [emb, wstar] exact cylinder_construction_step_embed_wstar_dot d x y e v rw [hd, dotProduct_comm v e, h_orth v hv] simp rw [h1, hwstar_quad0, h3] ring have horth : ∀ w ∈ W', dotProduct estar w = 0 := by intro w hw dsimp only [W'] at hw rw [Submodule.mem_sup] at hw obtain ⟨a, ha, b, hb, hwab⟩ := hw rw [Submodule.mem_map] at ha obtain ⟨v, hv, rfl⟩ := ha rw [Submodule.mem_span_singleton] at hb obtain ⟨c, rfl⟩ := hb rw [← hwab, dotProduct_add] have h1 : dotProduct estar (emb v) = 0 := by dsimp only [estar, emb] exact cylinder_construction_step_estar_embed_dot d x y v have h2 : dotProduct estar (c • wstar) = 0 := by rw [dotProduct_smul] have hd : dotProduct estar wstar = 0 := by dsimp only [estar, wstar] exact cylinder_construction_step_estar_wstar_dot d x y e rw [hd]; simp rw [h1, h2, add_zero] have hQestar : standard_quad (d+2) estar ≠ 0 := by have hq : standard_quad (d+2) estar = x^2 + y^2 := by simpa only [estar] using cylinder_construction_step_estar_quad (p:=p) (d:=d) x y rw [hq, hxy] exact neg_ne_zero.mpr hκ have hnotmem : estar ∉ W' := by intro h exact hQestar (hW'_total estar h) exact ⟨W', estar, hW'_dim, hW'_total, horth, hnotmem, hQestar⟩