AFTD Auto-Formalizing Theoretical Domains

isotropic_subspace_lower_bound

theoremverified

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

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.

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

    lines 8–10

      open Matrix LinearMap in
      classical
      let B : LinearMap.BilinForm (ZMod 2) (M → ZMod 2) := toBilin' (1 : Matrix M M (ZMod 2))
  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.

    lines 11–14

    uses Matrix.Nondegenerate.toBilin', nondegenerate_iff_forall_vecMul_and_mulVec_eq_zero

      have hB_nondeg : B.Nondegenerate := by
        apply Matrix.Nondegenerate.toBilin'
        rw [nondegenerate_iff_forall_vecMul_and_mulVec_eq_zero]
        simp
  3. 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`).

    lines 15–21

    uses BilinForm.mem_orthogonal_iff, toBilin'_apply', one_mulVec, dotProduct

      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
  4. 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ᗮ.

    lines 22–26

    uses BilinForm.finrank_orthogonal, Module.finrank_pi, Submodule.finrank_mono

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

    lines 27–32

    uses BilinForm.mem_orthogonal_iff, toBilin'_apply', one_mulVec, dotProduct, mul_one

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

    lines 33–34

      have h_two_rank_le : 2 * Module.finrank (ZMod 2) V ≤ Fintype.card M := by
        omega
  7. 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`.

    lines 35–43

    uses Submodule.eq_of_le_of_finrank_eq

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

    line 44

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

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

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