freivalds_matrix_kernel_count_le
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).
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.
obtain ⟨i, j, hij⟩ : ∃ i j, M i j ≠ 0 := by contrapose! hM ext i j exact hM i j
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.
uses
Finset.mem_coe,Finset.mem_filter,Fintype.mem_piFinsetlet 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
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.
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⟩
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.
uses
Finset.card_le_card_of_injOnhave h_le := Finset.card_le_card_of_injOn proj hmaps hinjThe 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.
uses
Fintype.card_piFinset,Finset.prod_const,Finset.card_univ,Fintype.card_subtype,Finset.filter_ne',Finset.card_erase_of_mem,Finset.mem_univhave 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
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.
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.
- On line 54, `simp` automatically evaluates the cardinality of the universal set of `Fin n` as `n`.
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.
/-- 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