AFTD Auto-Formalizing Theoretical Domains

freivalds_matrix_kernel_count_le

theoremverifiedformalization

Let F be a commutative ring that is an integral domain with decidable equality, n a positive integer, S a nonempty finite subset of F, and M a nonzero n × n matrix over F. Then the number of vectors r in the Cartesian product S^n (represented as Fintype.piFinset (fun _ : Fin n => S)) such that Matrix.mulVec M r = 0 is at most S.card ^ (n - 1).

Statement

theorem freivalds_matrix_kernel_count_le {F : Type*} [CommRing F] [IsDomain F] [DecidableEq F]
    {n : ℕ} (hn : 0 < n) {S : Finset F} (hS : 0 < S.card)
    {M : Matrix (Fin n) (Fin n) F} (hM : M ≠ 0) :
    Finset.card (Finset.filter (fun r => Matrix.mulVec M r = 0) (Fintype.piFinset (fun _ : Fin n => S))) ≤ S.card ^ (n - 1)
Formalizes
Freivalds (1977), 'Probabilistic Machines Can Use Less Running Time', Section 2
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • schwartz_zippel_zero_count_leLet F be an integral domain, S a nonempty finite subset of F, n a positive integer, and p a nonzero polynomial in n variables over F of…

Read back from the Lean

Let $F$ be a commutative integral domain with decidable equality, and let $n$ be a positive natural number ($0 < n$). Let $S$ be a nonempty finite subset of $F$ ($0 < |S|$), and let $M$ be a non-zero $n \times n$ matrix with entries in $F$ ($M \neq 0$). Then the number of vectors $r \in S^n$ (functions $r : \mathrm{Fin}\ n \to F$ such that $r(i) \in S$ for all $i$) satisfying $M r = 0$ is at most $|S|^{n - 1}$.

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

Since the matrix M is nonzero, it has some nonzero entry M i j ≠ 0. For any vector r in the kernel, the i-th row equation determines r j uniquely from the remaining n - 1 coordinates because the coefficient M i j is nonzero in an integral domain. Projecting kernel vectors onto the n - 1 coordinates distinct from j is therefore an injective map into S^(n - 1), bounding the size of the kernel by |S|^(n - 1).

  1. There exist indices i and j such that M i j ≠ 0.

    By contraposition, if every entry of M were zero, extensionality would force M = 0, which contradicts the hypothesis that M is nonzero.

    lines 6–9

      obtain ⟨i, j, hij⟩ : ∃ i j, M i j ≠ 0 := by
        contrapose! hM
        ext i j
        exact hM i j
  2. The projection dropping the j-th coordinate maps kernel vectors in S^n to the product S^{k ≠ j}.

    Defining `proj` to restrict a vector to indices k ≠ j, any vector r in the kernel with coordinates in S still has all its components at indices k ≠ j in S.

    lines 10–19

    uses Finset.mem_coe, Finset.mem_filter, Fintype.mem_piFinset

      let proj : (Fin n → F) → ({k : Fin n // k ≠ j} → F) := fun r k => r k.val
      have hmaps : Set.MapsTo proj
          ↑(Finset.filter (fun r => Matrix.mulVec M r = 0) (Fintype.piFinset (fun _ : Fin n => S)))
          ↑(Fintype.piFinset (fun _ : {k : Fin n // k ≠ j} => S)) := by
        intro r hr
        rw [Finset.mem_coe, Finset.mem_filter] at hr
        rw [Finset.mem_coe, Fintype.mem_piFinset]
        intro k
        rw [Fintype.mem_piFinset] at hr
        exact hr.1 k.val
  3. The projection `proj` is injective on the kernel vectors in S^n.

    Let r₁ and r₂ be kernel vectors in S^n that agree on all coordinates k ≠ j. Since M r₁ = 0 and M r₂ = 0, the i-th row dot products M_i · r₁ and M_i · r₂ both vanish. Splitting each sum into the j-th term and the sum over k ≠ j, the sums over k ≠ j coincide because r₁ and r₂ agree there. Cancelling this common sum gives M i j * r₁ j = M i j * r₂ j. Since F is an integral domain and M i j ≠ 0, left cancellation yields r₁ j = r₂ j. Hence r₁ and r₂ agree on all coordinates.

    lines 20–48

    uses Finset.mem_coe, Finset.mem_filter, Fintype.sum_eq_add_sum_subtype_ne, congr_fun, add_right_cancel, mul_left_cancel₀

      have hinj : Set.InjOn proj
          ↑(Finset.filter (fun r => Matrix.mulVec M r = 0) (Fintype.piFinset (fun _ : Fin n => S))) := by
        intro r₁ hr₁ r₂ hr₂ hproj
        rw [Finset.mem_coe, Finset.mem_filter] at hr₁ hr₂
        have hr₁_zero := hr₁.2
        have hr₂_zero := hr₂.2
        have hd₁ : dotProduct (M i) r₁ = 0 := by
          have : Matrix.mulVec M r₁ i = 0 := by rw [hr₁_zero]; rfl
          exact this
        have hd₂ : dotProduct (M i) r₂ = 0 := by
          have : Matrix.mulVec M r₂ i = 0 := by rw [hr₂_zero]; rfl
          exact this
        change ∑ k, M i k * r₁ k = 0 at hd₁
        change ∑ k, M i k * r₂ k = 0 at hd₂
        rw [Fintype.sum_eq_add_sum_subtype_ne (fun k => M i k * r₁ k) j] at hd₁
        rw [Fintype.sum_eq_add_sum_subtype_ne (fun k => M i k * r₂ k) j] at hd₂
        have h_sum_eq : (∑ k : {k : Fin n // k ≠ j}, M i k * r₁ k) = (∑ k : {k : Fin n // k ≠ j}, M i k * r₂ k) := by
          congr 1
          ext k
          congr 1
          exact congr_fun hproj k
        have h_mul_eq : M i j * r₁ j = M i j * r₂ j := by
          apply add_right_cancel (b := ∑ k : {k : Fin n // k ≠ j}, M i k * r₁ k)
          rw [hd₁, h_sum_eq, hd₂]
        have hr_j : r₁ j = r₂ j := mul_left_cancel₀ hij h_mul_eq
        ext k
        by_cases hk : k = j
        · subst hk; exact hr_j
        · exact congr_fun hproj ⟨k, hk⟩
  4. The number of kernel vectors in S^n is at most the cardinality of S^{k ≠ j}.

    Because `proj` maps the kernel vectors in S^n into the product S^{k ≠ j} and is injective on that set, the cardinality of the domain is bounded by the cardinality of the codomain.

    line 49

    uses Finset.card_le_card_of_injOn

      have h_le := Finset.card_le_card_of_injOn proj hmaps hinj
  5. The product S^{k ≠ j} has cardinality |S|^(n - 1).

    The cardinality of the Cartesian product of constant finsets S over the index type {k : Fin n // k ≠ j} is |S| raised to the cardinality of the index set. The index set is the universal set of Fin n with j erased, so its cardinality is n - 1.

    lines 50–54

    uses Fintype.card_piFinset, Finset.prod_const, Finset.card_univ, Fintype.card_subtype, Finset.filter_ne', Finset.card_erase_of_mem, Finset.mem_univ

      have h_target : (Fintype.piFinset (fun _ : {k : Fin n // k ≠ j} => S)).card = S.card ^ (n - 1) := by
        rw [Fintype.card_piFinset, Finset.prod_const, Finset.card_univ]
        have h : Fintype.card {k : Fin n // k ≠ j} = (Finset.filter (· ≠ j) Finset.univ).card := Fintype.card_subtype _
        rw [h, Finset.filter_ne', Finset.card_erase_of_mem (Finset.mem_univ j)]
        simp
  6. The number of kernel vectors in S^n is at most |S|^(n - 1).

    Substituting the computed size |S|^(n - 1) of the target product into the cardinality bound completes the proof.

    line 55

      rwa [h_target] at h_le
Finset.mem_coe
An element belongs to the coercion of a finset to a set if and only if it belongs to the finset.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Fintype.mem_piFinset
A function belongs to a dependent product of finsets if and only if every value belongs to the corresponding factor finset.
Fintype.sum_eq_add_sum_subtype_ne
A finite sum over all elements decomposes into the term at a specified element plus the sum over all other elements.
congr_fun
If two functions are equal, their evaluations at any given point are equal.
add_right_cancel
In an additive structure, a + b = c + b implies a = c.
mul_left_cancel₀
In a structure with zero and left cancellation of nonzero factors (such as an integral domain), a ≠ 0 and a * b = a * c imply b = c.
Finset.card_le_card_of_injOn
If a map from a finset s to a finset t is injective on s, then |s| ≤ |t|.
Fintype.card_piFinset
The cardinality of a product of finsets indexed by a finite type is the product of their cardinalities.
Finset.prod_const
The product of a constant value over a finset equals that value raised to the cardinality of the finset.
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of that type.
Fintype.card_subtype
The cardinality of a subtype defined by a predicate equals the cardinality of the finset of elements satisfying that predicate.
Finset.filter_ne'
Filtering a finset for elements not equal to a given element erases that element from the finset.
Finset.card_erase_of_mem
Erasing an element from a finset containing it decreases its cardinality by 1.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.

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

/-- The kernel of a nonzero matrix on a finite grid S^n has cardinality at most |S|^(n-1). -/theorem freivalds_matrix_kernel_count_le {F : Type*} [CommRing F] [IsDomain F] [DecidableEq F]    {n : ℕ} (hn : 0 < n) {S : Finset F} (hS : 0 < S.card)    {M : Matrix (Fin n) (Fin n) F} (hM : M ≠ 0) :    Finset.card (Finset.filter (fun r => Matrix.mulVec M r = 0) (Fintype.piFinset (fun _ : Fin n => S))) ≤ S.card ^ (n - 1) := by  obtain ⟨i, j, hij⟩ : ∃ i j, M i j ≠ 0 := by    contrapose! hM    ext i j    exact hM i j  let proj : (Fin n → F) → ({k : Fin n // k ≠ j} → F) := fun r k => r k.val  have hmaps : Set.MapsTo proj      ↑(Finset.filter (fun r => Matrix.mulVec M r = 0) (Fintype.piFinset (fun _ : Fin n => S)))      ↑(Fintype.piFinset (fun _ : {k : Fin n // k ≠ j} => S)) := by    intro r hr    rw [Finset.mem_coe, Finset.mem_filter] at hr    rw [Finset.mem_coe, Fintype.mem_piFinset]    intro k    rw [Fintype.mem_piFinset] at hr    exact hr.1 k.val  have hinj : Set.InjOn proj      ↑(Finset.filter (fun r => Matrix.mulVec M r = 0) (Fintype.piFinset (fun _ : Fin n => S))) := by    intro r₁ hr₁ r₂ hr₂ hproj    rw [Finset.mem_coe, Finset.mem_filter] at hr₁ hr₂    have hr₁_zero := hr₁.2    have hr₂_zero := hr₂.2    have hd₁ : dotProduct (M i) r₁ = 0 := by      have : Matrix.mulVec M r₁ i = 0 := by rw [hr₁_zero]; rfl      exact this    have hd₂ : dotProduct (M i) r₂ = 0 := by      have : Matrix.mulVec M r₂ i = 0 := by rw [hr₂_zero]; rfl      exact this    change ∑ k, M i k * r₁ k = 0 at hd₁    change ∑ k, M i k * r₂ k = 0 at hd₂    rw [Fintype.sum_eq_add_sum_subtype_ne (fun k => M i k * r₁ k) j] at hd₁    rw [Fintype.sum_eq_add_sum_subtype_ne (fun k => M i k * r₂ k) j] at hd₂    have h_sum_eq : (∑ k : {k : Fin n // k ≠ j}, M i k * r₁ k) = (∑ k : {k : Fin n // k ≠ j}, M i k * r₂ k) := by      congr 1      ext k      congr 1      exact congr_fun hproj k    have h_mul_eq : M i j * r₁ j = M i j * r₂ j := by      apply add_right_cancel (b := ∑ k : {k : Fin n // k ≠ j}, M i k * r₁ k)      rw [hd₁, h_sum_eq, hd₂]    have hr_j : r₁ j = r₂ j := mul_left_cancel₀ hij h_mul_eq    ext k    by_cases hk : k = j    · subst hk; exact hr_j    · exact congr_fun hproj ⟨k, hk⟩  have h_le := Finset.card_le_card_of_injOn proj hmaps hinj  have h_target : (Fintype.piFinset (fun _ : {k : Fin n // k ≠ j} => S)).card = S.card ^ (n - 1) := by    rw [Fintype.card_piFinset, Finset.prod_const, Finset.card_univ]    have h : Fintype.card {k : Fin n // k ≠ j} = (Finset.filter (· ≠ j) Finset.univ).card := Fintype.card_subtype _    rw [h, Finset.filter_ne', Finset.card_erase_of_mem (Finset.mem_univ j)]    simp  rwa [h_target] at h_le
See it in the graphDiscuss this resultChallenge it