AFTD Auto-Formalizing Theoretical Domains

midpoint_certificate_matrix_minor_abs_le

theoremverified

The absolute value of every k x k minor of a (k+1) x (k+1) midpoint-certificate matrix is bounded by 2^k, proved by multilinear expansion into 2^k unit-difference determinants and applying total unimodularity.

Statement

theorem midpoint_certificate_matrix_minor_abs_le {k : ℕ} (u v : Fin (k + 1) → Fin (k + 1))
    (i₀ j₀ : Fin (k + 1)) :
    |((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| ≤ (2 ^ k : ℤ)
Source
step towards finset_card_ge_one_add_clog_of_midpoint_balanced
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The proof decomposes the k x k submatrix of the midpoint-certificate matrix into the sum of two matrices, m + m', splitting the diagonal 2 into 1 + 1. Using the multilinearity of the determinant in the rows, det(m + m') expands into a sum of 2^k determinants where each row is chosen from either m or m'. Each such matrix is a k x k submatrix of a unit-difference matrix, which is totally unimodular, so each determinant is in {-1, 0, 1}. Finally, the triangle inequality bounds the overall determinant by the sum of these 2^k terms, yielding at most 2^k.

  1. The k x k submatrix equals the sum m + m' of two matrices whose entries split the diagonal 2 into 1 + 1.

    Define `m` and `m'` by splitting the diagonal entry 2 into 1 + 1: `m` pairs the identity entry with `- [j = u(i)]`, and `m'` pairs the identity entry with `- [j = v(i)]`. Checking all combinations of matching indices confirms that entrywise addition yields the submatrix of the certificate matrix.

    lines 7–19

    uses Matrix.submatrix_apply, Matrix.of_apply, Matrix.add_apply

      set m : Matrix (Fin k) (Fin k) ℤ := Matrix.of fun (r c : Fin k) =>
          (if j₀.succAbove c = i₀.succAbove r then (1 : ℤ) else 0) -
          (if j₀.succAbove c = u (i₀.succAbove r) then 1 else 0)
      set m' : Matrix (Fin k) (Fin k) ℤ := Matrix.of fun (r c : Fin k) =>
          (if j₀.succAbove c = i₀.succAbove r then (1 : ℤ) else 0) -
          (if j₀.succAbove c = v (i₀.succAbove r) then 1 else 0)
      have hsplit : ((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) = m + m' := by
        ext r c
        simp only [m, m', Matrix.submatrix_apply, Matrix.of_apply, Matrix.add_apply]
        split_ifs <;> ring
      rw [hsplit]
  2. The determinant of m + m' expands multilinearly into a sum of 2^k determinants.

    Because the determinant is multilinear in the rows of the matrix, the determinant of `m + m'` expands by `MultilinearMap.map_add_univ` into the sum over all subsets `s ⊆ Fin k` of the determinants of matrices whose r-th row is chosen from `m` if `r ∈ s` and from `m'` if `r ∉ s`.

    lines 20–23

    uses MultilinearMap.map_add_univ

      have hexp : (m + m').det = ∑ s : Finset (Fin k), Matrix.det (s.piecewise m m') := by
        have := MultilinearMap.map_add_univ Matrix.detRowAlternating.toMultilinearMap m m'
        exact this
      rw [hexp]
  3. Each of the 2^k determinants in the expansion has absolute value at most 1.

    For any chosen subset `s`, let `w(r)` select `u(i₀.succAbove r)` for `r ∈ s` and `v(i₀.succAbove r)` for `r ∉ s`. The matrix `s.piecewise m m'` is shown entry-by-entry to be the k x k submatrix formed by taking columns `j₀.succAbove` from the k x (k+1) matrix `B` whose r-th row is `e_{i₀.succAbove r} - e_{w(r)}`. By `matrix_unit_difference_rows_isTotallyUnimodular`, `B` is totally unimodular, so every square submatrix has determinant in {-1, 0, 1}, meaning its absolute value is at most 1.

    lines 24–46

    uses Finset.piecewise_eq_of_mem, Finset.piecewise_eq_of_notMem, congrFun, em, if_pos, if_neg, Matrix.submatrix_apply, Matrix.of_apply, id_eq, Pi.single_apply, matrix_unit_difference_rows_isTotallyUnimodular, Function.injective_id, Fin.succAbove_right_injective

      have hbound : ∀ s : Finset (Fin k), |Matrix.det (s.piecewise m m')| ≤ 1 := by
        intro s
        set w : Fin k → Fin (k + 1) := fun r => if r ∈ s then u (i₀.succAbove r) else v (i₀.succAbove r)
        set B : Matrix (Fin k) (Fin (k + 1)) ℤ := Matrix.of fun (r : Fin k) (j : Fin (k + 1)) =>
          (Pi.single (i₀.succAbove r) (1 : ℤ) : Fin (k + 1) → ℤ) j - (Pi.single (w r) (1 : ℤ) : Fin (k + 1) → ℤ) j
        have heq : (s.piecewise m m' : Matrix (Fin k) (Fin k) ℤ) = B.submatrix id j₀.succAbove := by
          ext r c
          have hrow : (Finset.piecewise s m m' : Matrix (Fin k) (Fin k) ℤ) r = if r ∈ s then m r else m' r := by
            split_ifs with hr
            · exact Finset.piecewise_eq_of_mem s m m' hr
            · exact Finset.piecewise_eq_of_notMem s m m' hr
          rw [congrFun hrow c]
          rcases em (r ∈ s) with hr | hr
          · rw [if_pos hr]
            simp only [B, w, m, Matrix.submatrix_apply, Matrix.of_apply, id_eq, Pi.single_apply, if_pos hr]
          · rw [if_neg hr]
            simp only [B, w, m', Matrix.submatrix_apply, Matrix.of_apply, id_eq, Pi.single_apply, if_neg hr]
        rw [heq]
        have htu := matrix_unit_difference_rows_isTotallyUnimodular (fun r => i₀.succAbove r) w
        have hdet := htu k id j₀.succAbove Function.injective_id Fin.succAbove_right_injective
        rcases hdet with ⟨sgn, hsgn⟩
        rw [← hsgn]
        cases sgn <;> simp
  4. The absolute value of the submatrix determinant is bounded by 2^k.

    Applying the triangle inequality to the multilinear sum bounds the absolute determinant by the sum of the absolute determinants of the terms. Since each term is at most 1 and there are 2^k subsets of `Fin k`, the sum evaluates to 2^k.

    lines 47–55

    uses Finset.abs_sum_le_sum_abs, Finset.sum_le_sum, Finset.sum_const, nsmul_eq_mul, mul_one, Finset.card_univ, Fintype.card_finset, Fintype.card_fin

      calc
        |∑ s : Finset (Fin k), Matrix.det (s.piecewise m m')| ≤
            ∑ s : Finset (Fin k), |Matrix.det (s.piecewise m m')| := Finset.abs_sum_le_sum_abs _ _
        _ ≤ ∑ s : Finset (Fin k), (1 : ℤ) := Finset.sum_le_sum (fun s _ => hbound s)
        _ = 2 ^ k := by
          simp only [Finset.sum_const, nsmul_eq_mul, mul_one]
          rw [Finset.card_univ, Fintype.card_finset, Fintype.card_fin]
          push_cast
          rfl
Matrix.submatrix_apply
Evaluating the submatrix `A.submatrix r c` at `(i, j)` gives `A (r i) (c j)`.
Matrix.of_apply
The `(i, j)`-th entry of the matrix formed from a function `f` is `f i j`.
Matrix.add_apply
The `(i, j)`-th entry of the sum of two matrices `A + B` is `A i j + B i j`.
MultilinearMap.map_add_univ
A multilinear map applied to a componentwise sum `m + m'` expands into the sum over all index subsets `s` of the map applied to the vector taking row `m i` when `i ∈ s` and `m' i` when `i ∉ s`.
Finset.piecewise_eq_of_mem
The piecewise combination `s.piecewise f g` evaluated at an element `i ∈ s` equals `f i`.
Finset.piecewise_eq_of_notMem
The piecewise combination `s.piecewise f g` evaluated at an element `i ∉ s` equals `g i`.
congrFun
If two functions are equal, their values on any argument are equal.
em
The law of excluded middle: every proposition `p` is either true or false.
if_pos
If condition `c` holds, `if c then t else e` reduces to `t`.
if_neg
If condition `c` is false, `if c then t else e` reduces to `e`.
id_eq
The identity function leaves its input unchanged (`id a = a`).
Pi.single_apply
A single-indicator function `Pi.single i x` evaluates to `x` at `i` and `0` elsewhere.
matrix_unit_difference_rows_isTotallyUnimodular
A matrix whose rows are each differences of two unit basis vectors is totally unimodular.
Function.injective_id
The identity function is injective.
Fin.succAbove_right_injective
The function `p.succAbove`, which embeds `Fin n` into `Fin (n + 1)` by skipping `p`, is injective.
Finset.abs_sum_le_sum_abs
The absolute value of a finite sum is bounded by the sum of absolute values (the triangle inequality).
Finset.sum_le_sum
If `f i ≤ g i` for all elements of a finite set `s`, then the sum of `f` over `s` is at most the sum of `g` over `s`.
Finset.sum_const
Summing a constant value `b` over a finite set `s` equals the cardinality of `s` times `b`.
nsmul_eq_mul
Scalar multiplication of an integer by a natural number `n` equals multiplication by `n`.
mul_one
Multiplying an integer by 1 leaves it unchanged.
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of the type.
Fintype.card_finset
The number of subsets of a finite set of cardinality `n` is `2^n`.
Fintype.card_fin
The standard finite type `Fin n` has cardinality `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

/-- The absolute value of every k x k minor of a (k+1) x (k+1) midpoint-certificate matrix is bounded by 2^k. -/theorem midpoint_certificate_matrix_minor_abs_le {k : ℕ} (u v : Fin (k + 1) → Fin (k + 1))    (i₀ j₀ : Fin (k + 1)) :    |((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| ≤ (2 ^ k : ℤ) := by  set m : Matrix (Fin k) (Fin k) ℤ := Matrix.of fun (r c : Fin k) =>      (if j₀.succAbove c = i₀.succAbove r then (1 : ℤ) else 0) -      (if j₀.succAbove c = u (i₀.succAbove r) then 1 else 0)  set m' : Matrix (Fin k) (Fin k) ℤ := Matrix.of fun (r c : Fin k) =>      (if j₀.succAbove c = i₀.succAbove r then (1 : ℤ) else 0) -      (if j₀.succAbove c = v (i₀.succAbove r) then 1 else 0)  have hsplit : ((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) = m + m' := by    ext r c    simp only [m, m', Matrix.submatrix_apply, Matrix.of_apply, Matrix.add_apply]    split_ifs <;> ring  rw [hsplit]  have hexp : (m + m').det = ∑ s : Finset (Fin k), Matrix.det (s.piecewise m m') := by    have := MultilinearMap.map_add_univ Matrix.detRowAlternating.toMultilinearMap m m'    exact this  rw [hexp]  have hbound : ∀ s : Finset (Fin k), |Matrix.det (s.piecewise m m')| ≤ 1 := by    intro s    set w : Fin k → Fin (k + 1) := fun r => if r ∈ s then u (i₀.succAbove r) else v (i₀.succAbove r)    set B : Matrix (Fin k) (Fin (k + 1)) ℤ := Matrix.of fun (r : Fin k) (j : Fin (k + 1)) =>      (Pi.single (i₀.succAbove r) (1 : ℤ) : Fin (k + 1) → ℤ) j - (Pi.single (w r) (1 : ℤ) : Fin (k + 1) → ℤ) j    have heq : (s.piecewise m m' : Matrix (Fin k) (Fin k) ℤ) = B.submatrix id j₀.succAbove := by      ext r c      have hrow : (Finset.piecewise s m m' : Matrix (Fin k) (Fin k) ℤ) r = if r ∈ s then m r else m' r := by        split_ifs with hr        · exact Finset.piecewise_eq_of_mem s m m' hr        · exact Finset.piecewise_eq_of_notMem s m m' hr      rw [congrFun hrow c]      rcases em (r ∈ s) with hr | hr      · rw [if_pos hr]        simp only [B, w, m, Matrix.submatrix_apply, Matrix.of_apply, id_eq, Pi.single_apply, if_pos hr]      · rw [if_neg hr]        simp only [B, w, m', Matrix.submatrix_apply, Matrix.of_apply, id_eq, Pi.single_apply, if_neg hr]    rw [heq]    have htu := matrix_unit_difference_rows_isTotallyUnimodular (fun r => i₀.succAbove r) w    have hdet := htu k id j₀.succAbove Function.injective_id Fin.succAbove_right_injective    rcases hdet with ⟨sgn, hsgn⟩    rw [← hsgn]    cases sgn <;> simp  calc    |∑ s : Finset (Fin k), Matrix.det (s.piecewise m m')| ≤        ∑ s : Finset (Fin k), |Matrix.det (s.piecewise m m')| := Finset.abs_sum_le_sum_abs _ _    _ ≤ ∑ s : Finset (Fin k), (1 : ℤ) := Finset.sum_le_sum (fun s _ => hbound s)    _ = 2 ^ k := by      simp only [Finset.sum_const, nsmul_eq_mul, mul_one]      rw [Finset.card_univ, Fintype.card_finset, Fintype.card_fin]      push_cast      rfl
See it in the graphDiscuss this resultChallenge it