midpoint_certificate_matrix_minor_dvd_p
For an injective certificate vector b in (ZMod p)^{k+1} satisfying the midpoint equations with k > 0, the shifted vector b - b(j₀) restricts to a non-zero vector in the kernel of the k x k minor modulo p, so its determinant vanishes modulo p and is divisible by p in Z.
Statement
theorem midpoint_certificate_matrix_minor_dvd_p {p k : ℕ} [Fact p.Prime] (hk : 0 < k) (u v : Fin (k + 1) → Fin (k + 1)) (b : Fin (k + 1) → ZMod p) (hinj : Function.Injective b) (hmid : ∀ i, 2 * b i = b (u i) + b (v i)) (i₀ j₀ : Fin (k + 1)) : (p : ℤ) ∣ ((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove).det
- Source
- step towards finset_card_ge_one_add_clog_of_midpoint_balanced
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- finset_card_ge_one_add_clog_of_midpoint_balancedFor a prime p, every nonempty balanced subset B of Z/pZ has |B| ≥ 1 + ⌈log₂ p⌉.
The proof, explained
Divisibility of the integer minor determinant by p is reduced to the vanishing of the determinant modulo p. Over the finite field ℤ/pℤ, a matrix has determinant zero if it has a non-trivial kernel. The shifted certificate vector w(m) = b(j₀.succAbove m) - b(j₀) is non-zero due to the injectivity of b and k > 0, and satisfies M w = 0 because each row dot product extends to a sum over all k+1 coordinates that vanishes thanks to the midpoint equations and the zero row sums.
It suffices to show that the determinant of the minor vanishes when reduced modulo p.
Divisibility of an integer determinant by p is equivalent to its canonical image in ℤ/pℤ being zero, as given by `ZMod.intCast_zmod_eq_zero_iff_dvd`.
uses
ZMod.intCast_zmod_eq_zero_iff_dvdrw [← ZMod.intCast_zmod_eq_zero_iff_dvd]Reducing the integer minor determinant modulo p is equal to computing the determinant of the minor directly over ℤ/pℤ.
The reduction map ℤ → ℤ/pℤ is a ring homomorphism (`Int.castRingHom`) and therefore commutes with submatrices and determinants (`RingHom.map_det`, `RingHom.mapMatrix_apply`). Applying it entrywise transforms the integer coefficients 2, -1, -1 into their modulo p counterparts.
uses
RingHom.map_det,Int.castRingHom,RingHom.mapMatrix_applyhave hmap : (((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove).det : ZMod p) = ((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ZMod p) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove).det := by have h := (RingHom.map_det (Int.castRingHom (ZMod p)) ((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove)).symm rw [RingHom.mapMatrix_apply] at h show (Int.castRingHom (ZMod p)) _ = _ rw [← h] congr 1 ext i j simp rw [hmap]
To show det M = 0, it suffices to find a non-zero vector in the kernel of M, for which we propose the shifted certificate vector w(m) = b(j₀.succAbove m) - b(j₀).
A square matrix has determinant zero if it annihilates a non-zero vector (`Matrix.exists_mulVec_eq_zero_iff.mp`). We take w to be the restriction of the shifted vector b - b(j₀) to the k coordinates distinct from j₀.
uses
Matrix.exists_mulVec_eq_zero_iff.mplet M := (Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ZMod p) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove have h_det_zero : M.det = 0 := by apply Matrix.exists_mulVec_eq_zero_iff.mp refine ⟨fun m => b (j₀.succAbove m) - b j₀, ?_, ?_⟩
The kernel candidate vector w is non-zero.
Because k > 0, the index 0 in Fin k exists. If w were the zero vector, then w(0) = 0, which would mean b(j₀.succAbove 0) = b(j₀) via `sub_eq_zero.mp`. Injectivity of b would force j₀.succAbove 0 = j₀, contradicting `Fin.succAbove_ne`.
uses
sub_eq_zero.mp,Fin.succAbove_ne· intro h have h0 : (fun m : Fin k => b (j₀.succAbove m) - b j₀) ⟨0, hk⟩ = 0 := by rw [h]; rfl dsimp at h0 have heq : b (j₀.succAbove ⟨0, hk⟩) = b j₀ := sub_eq_zero.mp h0 have h_inj := hinj heq exact Fin.succAbove_ne j₀ ⟨0, hk⟩ h_inj
Each component (M w)ₗ is equal to the full sum over all j in Fin (k+1) of the full matrix row times (b(j) - b(j₀)).
By definition of matrix-vector multiplication (`Matrix.mulVec`, `dotProduct`), (M w)ₗ is a sum over indices in Fin k. Using `Fin.sum_univ_succAbove`, this sum can be completed to the full sum over all j in Fin (k+1), because the additional term at j = j₀ contains the factor b(j₀) - b(j₀) = 0 (`sub_self`, `mul_zero`, `zero_add`).
uses
Matrix.mulVec,dotProduct,Fin.sum_univ_succAbove,sub_self,mul_zero,zero_add· ext l rw [Matrix.mulVec] dsimp [dotProduct, M] have hsplit := Fin.sum_univ_succAbove (fun j => ((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * (b j - b j₀)) j₀ have hj0 : ((if j₀ = i₀.succAbove l then (2 : ZMod p) else 0) - (if j₀ = u (i₀.succAbove l) then 1 else 0) - (if j₀ = v (i₀.succAbove l) then 1 else 0)) * (b j₀ - b j₀) = 0 := by rw [sub_self, mul_zero] rw [hj0, zero_add] at hsplit rw [← hsplit]
The full sum over j in Fin (k+1) splits into a sum involving b(j) minus a sum involving b(j₀).
Expanding the product with b(j) - b(j₀) and distributing the summation over subtraction (`Finset.sum_sub_distrib`) separates the expression into two sums.
uses
Finset.sum_sub_distribhave h1 : ∀ j, (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * (b j - b j₀)) = (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * b j) - (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * b j₀) := by intro j; ring simp_rw [h1] rw [Finset.sum_sub_distrib]
The first sum ∑ⱼ ((2 [j = i] - [j = u i] - [j = v i]) * b j) equals 0.
Summing the indicator functions over Fin (k+1) collapses via `Finset.sum_ite_eq'` to 2 * b(i) - b(u i) - b(v i), where i = i₀.succAbove l. This expression vanishes by the midpoint condition 2 * b(i) = b(u i) + b(v i).
uses
sub_sub,Finset.sum_sub_distrib,Finset.sum_add_distrib,Finset.sum_ite_eq'have h_left : ∑ j : Fin (k + 1), (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * b j) = 0 := by have : ∀ j : Fin (k + 1), (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * b j) = (if j = i₀.succAbove l then 2 * b j else 0) - (if j = u (i₀.succAbove l) then b j else 0) - (if j = v (i₀.succAbove l) then b j else 0) := by intro j; split_ifs <;> ring simp_rw [this, sub_sub] rw [Finset.sum_sub_distrib, Finset.sum_add_distrib] simp [Finset.sum_ite_eq'] rw [← hmid (i₀.succAbove l)] ring rw [h_left]
The second sum ∑ⱼ ((2 [j = i] - [j = u i] - [j = v i]) * b j₀) equals 0.
Factoring out the constant scalar b(j₀) (`Finset.sum_mul`), the sum of the row coefficients is 2 - 1 - 1 = 0 by `Finset.sum_ite_eq'`, `sub_sub`, `Finset.sum_sub_distrib`, and `Finset.sum_add_distrib`. The product 0 * b(j₀) is 0 (`zero_mul`).
uses
Finset.sum_mul,sub_sub,Finset.sum_sub_distrib,Finset.sum_add_distrib,Finset.sum_ite_eq',zero_mulhave h_right : ∑ j : Fin (k + 1), (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * b j₀) = 0 := by rw [← Finset.sum_mul] have h_ones : ∑ j : Fin (k + 1), ((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then (1 : ZMod p) else 0)) = 0 := by simp_rw [sub_sub] rw [Finset.sum_sub_distrib, Finset.sum_add_distrib] simp [Finset.sum_ite_eq'] ring rw [h_ones, zero_mul]
The vector product M w vanishes identically, proving det M = 0 and completing the proof.
Subtracting the two vanishing sums gives 0 - 0 = 0 (`sub_zero`), showing (M w)ₗ = 0 for every row l. Hence M w = 0, which certifies det M = 0 and finishes the proof.
uses
sub_zerorw [h_right, sub_zero] exact h_det_zero
ZMod.intCast_zmod_eq_zero_iff_dvd- An integer casts to zero in ℤ/pℤ if and only if p divides it.
RingHom.map_det- A ring homomorphism preserves matrix determinants: f(det M) = det(f(M)).
Int.castRingHom- The canonical ring homomorphism from ℤ into any ring with unity.
RingHom.mapMatrix_apply- Applying a ring homomorphism to a matrix applies the homomorphism entrywise.
Matrix.exists_mulVec_eq_zero_iff.mp- A square matrix over a commutative ring has zero determinant if there exists a non-zero vector in its kernel.
sub_eq_zero.mp- In an additive group, if a - b = 0, then a = b.
Fin.succAbove_ne- The embedding succAbove(p, ·) from Fin n to Fin (n+1) never attains the omitted value p.
Matrix.mulVec- The matrix-vector product M v, defined coordinatewise as the dot product of each row of M with v.
dotProduct- The standard dot product of two vectors, ∑ i, v i * w i.
Fin.sum_univ_succAbove- Splitting a sum over Fin (n+1) into the term at index x and the sum over the remaining n indices via x.succAbove.
sub_self- In an additive group, a - a = 0.
mul_zero- Multiplication by zero on the right gives zero: a * 0 = 0.
zero_add- In an additive monoid, 0 + a = a.
Finset.sum_sub_distrib- Summation distributes over subtraction: ∑ (f x - g x) = ∑ f x - ∑ g x.
sub_sub- Associativity of subtraction: a - b - c = a - (b + c).
Finset.sum_add_distrib- Summation distributes over addition: ∑ (f x + g x) = ∑ f x + ∑ g x.
Finset.sum_ite_eq'- A sum of terms with an indicator (if x = a then b x else 0) evaluates to b a if a is in the index set, and 0 otherwise.
Finset.sum_mul- Right distributivity of multiplication over a finite sum: (∑ f i) * a = ∑ (f i * a).
zero_mul- Multiplication by zero on the left gives zero: 0 * a = 0.
sub_zero- Subtracting zero leaves an element unchanged: a - 0 = a.
- The matrix entries are defined using indicator functions (if-then-else expressions) representing the coefficients 2, -1, and -1 of the midpoint equations. The submatrix is formed by skipping row i₀ and column j₀ using `Fin.succAbove`.
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.
/-- Every k x k minor of a (k+1) x (k+1) midpoint-certificate matrix is divisible by p in ZMod p when k > 0. -/theorem midpoint_certificate_matrix_minor_dvd_p {p k : ℕ} [Fact p.Prime] (hk : 0 < k) (u v : Fin (k + 1) → Fin (k + 1)) (b : Fin (k + 1) → ZMod p) (hinj : Function.Injective b) (hmid : ∀ i, 2 * b i = b (u i) + b (v i)) (i₀ j₀ : Fin (k + 1)) : (p : ℤ) ∣ ((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove).det := by rw [← ZMod.intCast_zmod_eq_zero_iff_dvd] have hmap : (((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove).det : ZMod p) = ((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ZMod p) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove).det := by have h := (RingHom.map_det (Int.castRingHom (ZMod p)) ((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove)).symm rw [RingHom.mapMatrix_apply] at h show (Int.castRingHom (ZMod p)) _ = _ rw [← h] congr 1 ext i j simp rw [hmap] let M := (Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ZMod p) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove have h_det_zero : M.det = 0 := by apply Matrix.exists_mulVec_eq_zero_iff.mp refine ⟨fun m => b (j₀.succAbove m) - b j₀, ?_, ?_⟩ · intro h have h0 : (fun m : Fin k => b (j₀.succAbove m) - b j₀) ⟨0, hk⟩ = 0 := by rw [h]; rfl dsimp at h0 have heq : b (j₀.succAbove ⟨0, hk⟩) = b j₀ := sub_eq_zero.mp h0 have h_inj := hinj heq exact Fin.succAbove_ne j₀ ⟨0, hk⟩ h_inj · ext l rw [Matrix.mulVec] dsimp [dotProduct, M] have hsplit := Fin.sum_univ_succAbove (fun j => ((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * (b j - b j₀)) j₀ have hj0 : ((if j₀ = i₀.succAbove l then (2 : ZMod p) else 0) - (if j₀ = u (i₀.succAbove l) then 1 else 0) - (if j₀ = v (i₀.succAbove l) then 1 else 0)) * (b j₀ - b j₀) = 0 := by rw [sub_self, mul_zero] rw [hj0, zero_add] at hsplit rw [← hsplit] have h1 : ∀ j, (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * (b j - b j₀)) = (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * b j) - (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * b j₀) := by intro j; ring simp_rw [h1] rw [Finset.sum_sub_distrib] have h_left : ∑ j : Fin (k + 1), (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * b j) = 0 := by have : ∀ j : Fin (k + 1), (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * b j) = (if j = i₀.succAbove l then 2 * b j else 0) - (if j = u (i₀.succAbove l) then b j else 0) - (if j = v (i₀.succAbove l) then b j else 0) := by intro j; split_ifs <;> ring simp_rw [this, sub_sub] rw [Finset.sum_sub_distrib, Finset.sum_add_distrib] simp [Finset.sum_ite_eq'] rw [← hmid (i₀.succAbove l)] ring rw [h_left] have h_right : ∑ j : Fin (k + 1), (((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then 1 else 0)) * b j₀) = 0 := by rw [← Finset.sum_mul] have h_ones : ∑ j : Fin (k + 1), ((if j = i₀.succAbove l then (2 : ZMod p) else 0) - (if j = u (i₀.succAbove l) then 1 else 0) - (if j = v (i₀.succAbove l) then (1 : ZMod p) else 0)) = 0 := by simp_rw [sub_sub] rw [Finset.sum_sub_distrib, Finset.sum_add_distrib] simp [Finset.sum_ite_eq'] ring rw [h_ones, zero_mul] rw [h_right, sub_zero] exact h_det_zero