isotropic_subspace_lower_bound
If V is an isotropic subspace of (M → ZMod 2) under the standard dot product, the all-ones vector is orthogonal to V, and the all-ones vector is not in V, then 2 * finrank V + 1 ≤ card M.
Statement
theorem isotropic_subspace_lower_bound {M : Type*} [Fintype M] (V : Submodule (ZMod 2) (M → ZMod 2)) (h_iso : ∀ u ∈ V, ∀ v ∈ V, (∑ m, u m * v m) = 0) (h_ones_ortho : ∀ v ∈ V, ∑ m, v m = 0) (h_ones_notin : (fun _ : M => (1 : ZMod 2)) ∉ V) : 2 * Module.finrank (ZMod 2) V + 1 ≤ Fintype.card M
- Source
- step towards line_cubic_t_count_lower_bound
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- line_cubic_t_count_lower_boundFor any n ≥ 5, every parity representation of the line cubic syndrome has cardinality at least 2n + 1.
- cyclic_cubic_t_count_isotropy_lower_boundFor every natural number n ≥ 6 and every finite set S : Finset (Finset (Fin n)), if is_parity_repr S (cyclic_cubic_syndrome n), then 2 * n…
The proof, explained
The proof represents the standard dot product on M → ZMod 2 as a nondegenerate bilinear form B, so that the isotropic subspace V is contained in its orthogonal complement Vᗮ. Dimension counting for nondegenerate forms shows finrank Vᗮ = card M - finrank V, which implies 2 * finrank V ≤ card M. Since the all-ones vector is orthogonal to V but not in V, V cannot equal Vᗮ, ruling out the equality case 2 * finrank V = card M and yielding the strict inequality 2 * finrank V + 1 ≤ card M.
Define B as the bilinear form on M → ZMod 2 corresponding to the identity matrix.
Working classically within the Matrix and LinearMap namespaces, we define the bilinear form B on M → ZMod 2 to be the one induced by the identity matrix. This bilinear form computes the standard dot product.
open Matrix LinearMap in classical let B : LinearMap.BilinForm (ZMod 2) (M → ZMod 2) := toBilin' (1 : Matrix M M (ZMod 2))
The bilinear form B is nondegenerate.
A matrix bilinear form is nondegenerate whenever the underlying matrix is nondegenerate (`Matrix.Nondegenerate.toBilin'`). In turn, a matrix is nondegenerate if and only if both left and right vector multiplication have trivial kernels (`nondegenerate_iff_forall_vecMul_and_mulVec_eq_zero`). For the identity matrix 1, vector multiplication is the identity map, so both kernels are trivial and simplification completes the step.
uses
Matrix.Nondegenerate.toBilin',nondegenerate_iff_forall_vecMul_and_mulVec_eq_zerohave hB_nondeg : B.Nondegenerate := by apply Matrix.Nondegenerate.toBilin' rw [nondegenerate_iff_forall_vecMul_and_mulVec_eq_zero] simp
V is contained in its orthogonal complement Vᗮ with respect to B.
To show V ≤ B.orthogonal V, take any v ∈ V. By `BilinForm.mem_orthogonal_iff`, v belongs to B.orthogonal V if B(u, v) = 0 for all u ∈ V. Unfolding B via `toBilin'_apply'` and simplifying via `one_mulVec` and `dotProduct`, this condition is ∑ m, u m * v m = 0, which holds because V is isotropic (`h_iso`).
uses
BilinForm.mem_orthogonal_iff,toBilin'_apply',one_mulVec,dotProducthave h_le_ortho : V ≤ B.orthogonal V := by intro v hv rw [BilinForm.mem_orthogonal_iff] intro u hu rw [toBilin'_apply'] simp only [one_mulVec, dotProduct] exact h_iso u hu v hv
finrank Vᗮ = card M - finrank V, and therefore finrank V ≤ finrank Vᗮ.
Because B is nondegenerate, `BilinForm.finrank_orthogonal` gives finrank Vᗮ = finrank (M → ZMod 2) - finrank V. By `Module.finrank_pi`, the ambient dimension is card M. Furthermore, since V ≤ Vᗮ, monotonicity of dimension (`Submodule.finrank_mono`) ensures finrank V ≤ finrank Vᗮ.
uses
BilinForm.finrank_orthogonal,Module.finrank_pi,Submodule.finrank_monohave h_rank_ortho : Module.finrank (ZMod 2) (B.orthogonal V) = Fintype.card M - Module.finrank (ZMod 2) V := by rw [BilinForm.finrank_orthogonal hB_nondeg, Module.finrank_pi] have h_le_card : Module.finrank (ZMod 2) V ≤ Module.finrank (ZMod 2) (B.orthogonal V) := Submodule.finrank_mono h_le_ortho
The all-ones vector belongs to Vᗮ.
By `BilinForm.mem_orthogonal_iff`, the all-ones vector 1 is in Vᗮ if B(u, 1) = 0 for all u ∈ V. Expanding B (`toBilin'_apply'`) and simplifying via `one_mulVec`, `dotProduct`, and `mul_one`, this condition reduces to ∑ m, u m = 0, which is precisely the assumption `h_ones_ortho` that the all-ones vector is orthogonal to V.
uses
BilinForm.mem_orthogonal_iff,toBilin'_apply',one_mulVec,dotProduct,mul_onehave h_ones_in_ortho : (fun _ : M => (1 : ZMod 2)) ∈ B.orthogonal V := by rw [BilinForm.mem_orthogonal_iff] intro u hu rw [toBilin'_apply'] simp only [one_mulVec, dotProduct, mul_one] exact h_ones_ortho u hu
2 * finrank V ≤ card M.
Combining finrank V ≤ finrank Vᗮ with finrank Vᗮ = card M - finrank V, linear integer arithmetic via `omega` yields 2 * finrank V ≤ card M.
have h_two_rank_le : 2 * Module.finrank (ZMod 2) V ≤ Fintype.card M := by omega
2 * finrank V ≠ card M.
Suppose for contradiction that 2 * finrank V = card M. Then `omega` gives finrank V = finrank Vᗮ. Because V ≤ Vᗮ and their finite dimensions are equal, `Submodule.eq_of_le_of_finrank_eq` implies V = Vᗮ. But the all-ones vector belongs to Vᗮ, so it would belong to V, directly contradicting the hypothesis `h_ones_notin`.
uses
Submodule.eq_of_le_of_finrank_eqhave h_ne : 2 * Module.finrank (ZMod 2) V ≠ Fintype.card M := by intro h_eq have h_ranks_eq : Module.finrank (ZMod 2) V = Module.finrank (ZMod 2) (B.orthogonal V) := by omega have h_V_eq : V = B.orthogonal V := Submodule.eq_of_le_of_finrank_eq h_le_ortho h_ranks_eq have : (fun _ : M => (1 : ZMod 2)) ∈ V := by rw [h_V_eq] exact h_ones_in_ortho exact h_ones_notin this
2 * finrank V + 1 ≤ card M.
From the non-strict inequality 2 * finrank V ≤ card M and the disequality 2 * finrank V ≠ card M, linear integer arithmetic via `omega` concludes 2 * finrank V + 1 ≤ card M.
omega
Matrix.Nondegenerate.toBilin'- If a square matrix is nondegenerate, then its associated bilinear form is nondegenerate.
nondegenerate_iff_forall_vecMul_and_mulVec_eq_zero- A matrix is nondegenerate if and only if both left and right multiplication by it have trivial kernels.
BilinForm.mem_orthogonal_iff- An element m belongs to the orthogonal complement of a submodule N under a bilinear form B if and only if B(n, m) = 0 for all n in N.
toBilin'_apply'- The bilinear form associated with a matrix M evaluates on vectors v and w as the dot product v ⬝ᵥ (M *ᵥ w).
one_mulVec- Multiplying a vector by the identity matrix leaves the vector unchanged: 1 *ᵥ v = v.
dotProduct- The standard dot product of two vectors u and v, defined as ∑ m, u m * v m.
BilinForm.finrank_orthogonal- For a nondegenerate bilinear form on a finite-dimensional vector space V, the dimension of the orthogonal complement of W is finrank V - finrank W.
Module.finrank_pi- The dimension of the function space ι → R over R equals the cardinality of ι.
Submodule.finrank_mono- If a submodule S₁ is contained in a finite-dimensional submodule S₂, then finrank S₁ ≤ finrank S₂.
mul_one- Multiplying an element by 1 on the right leaves it unchanged: a * 1 = a.
Submodule.eq_of_le_of_finrank_eq- If a subspace S₁ is contained in a finite-dimensional subspace S₂ and both have equal dimension, then S₁ = S₂.
- The standard dot product on M → ZMod 2 is represented as the bilinear form associated with the identity matrix, `Matrix.toBilin' 1`.
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.
/-- If V is an isotropic subspace of (M → ZMod 2), the all-ones vector is orthogonal to V, and the all-ones vector is not in V, then 2 * finrank V + 1 ≤ card M. -/theorem isotropic_subspace_lower_bound {M : Type*} [Fintype M] (V : Submodule (ZMod 2) (M → ZMod 2)) (h_iso : ∀ u ∈ V, ∀ v ∈ V, (∑ m, u m * v m) = 0) (h_ones_ortho : ∀ v ∈ V, ∑ m, v m = 0) (h_ones_notin : (fun _ : M => (1 : ZMod 2)) ∉ V) : 2 * Module.finrank (ZMod 2) V + 1 ≤ Fintype.card M := by open Matrix LinearMap in classical let B : LinearMap.BilinForm (ZMod 2) (M → ZMod 2) := toBilin' (1 : Matrix M M (ZMod 2)) have hB_nondeg : B.Nondegenerate := by apply Matrix.Nondegenerate.toBilin' rw [nondegenerate_iff_forall_vecMul_and_mulVec_eq_zero] simp have h_le_ortho : V ≤ B.orthogonal V := by intro v hv rw [BilinForm.mem_orthogonal_iff] intro u hu rw [toBilin'_apply'] simp only [one_mulVec, dotProduct] exact h_iso u hu v hv have h_rank_ortho : Module.finrank (ZMod 2) (B.orthogonal V) = Fintype.card M - Module.finrank (ZMod 2) V := by rw [BilinForm.finrank_orthogonal hB_nondeg, Module.finrank_pi] have h_le_card : Module.finrank (ZMod 2) V ≤ Module.finrank (ZMod 2) (B.orthogonal V) := Submodule.finrank_mono h_le_ortho have h_ones_in_ortho : (fun _ : M => (1 : ZMod 2)) ∈ B.orthogonal V := by rw [BilinForm.mem_orthogonal_iff] intro u hu rw [toBilin'_apply'] simp only [one_mulVec, dotProduct, mul_one] exact h_ones_ortho u hu have h_two_rank_le : 2 * Module.finrank (ZMod 2) V ≤ Fintype.card M := by omega have h_ne : 2 * Module.finrank (ZMod 2) V ≠ Fintype.card M := by intro h_eq have h_ranks_eq : Module.finrank (ZMod 2) V = Module.finrank (ZMod 2) (B.orthogonal V) := by omega have h_V_eq : V = B.orthogonal V := Submodule.eq_of_le_of_finrank_eq h_le_ortho h_ranks_eq have : (fun _ : M => (1 : ZMod 2)) ∈ V := by rw [h_V_eq] exact h_ones_in_ortho exact h_ones_notin this omega