midpoint_certificate_matrix_minor_abs_le
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
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - matrix_unit_difference_rows_isTotallyUnimodularEvery integer matrix whose rows are differences e_u − e_v of two standard basis vectors is totally unimodular: each square minor is 0, 1…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- 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
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.
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.
uses
Matrix.submatrix_apply,Matrix.of_apply,Matrix.add_applyset 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]
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`.
uses
MultilinearMap.map_add_univhave 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]
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.
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_injectivehave 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
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.
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_fincalc |∑ 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`.
- In Lean, total unimodularity (`IsTotallyUnimodular`) is formalized by asserting that every square submatrix determinant lies in the range of `SignType.cast`, which embeds `{0, 1, -1}` into `ℤ`.
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 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