AFTD Auto-Formalizing Theoretical Domains

midpoint_certificate_matrix_minor_dvd_p

theoremverified

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

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.

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

    line 10

    uses ZMod.intCast_zmod_eq_zero_iff_dvd

      rw [← ZMod.intCast_zmod_eq_zero_iff_dvd]
  2. 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.

    lines 11–27

    uses RingHom.map_det, Int.castRingHom, RingHom.mapMatrix_apply

      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]
  3. 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₀.

    lines 28–33

    uses Matrix.exists_mulVec_eq_zero_iff.mp

      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₀, ?_, ?_⟩
  4. 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`.

    lines 34–39

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

    lines 40–50

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

    lines 51–56

    uses Finset.sum_sub_distrib

          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]
  7. 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).

    lines 57–68

    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]
  8. 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`).

    lines 69–78

    uses Finset.sum_mul, sub_sub, Finset.sum_sub_distrib, Finset.sum_add_distrib, Finset.sum_ite_eq', zero_mul

          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]
  9. 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.

    lines 79–80

    uses sub_zero

          rw [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.

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

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