is_convex_polygon_slack_matrix_nonneg
For any natural number n and any real matrix S : Matrix (Fin n) (Fin n) ℝ, if is_convex_polygon_slack_matrix n S holds, then for all indices i and j in Fin n, 0 ≤ S i j.
Statement
theorem is_convex_polygon_slack_matrix_nonneg {n : ℕ} {S : Matrix (Fin n) (Fin n) ℝ}
(hS : is_convex_polygon_slack_matrix n S) (i j : Fin n) : 0 ≤ S i j- Source
- arXiv:2610.04498 Sec. 2
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_convex_polygon_slack_matrixA real matrix S : Matrix (Fin n) (Fin n) ℝ is the slack matrix of a convex n-gon in the plane (is_convex_polygon_slack_matrix n S) if 3 ≤…
Read back from the Lean
For every natural number $n$ and every $n \times n$ real matrix $S$ (indexed by $\mathrm{Fin}(n) \times \mathrm{Fin}(n)$), if $S$ is a convex polygon slack matrix (satisfies is_convex_polygon_slack_matrix n S), then for all indices $i, j \in \mathrm{Fin}(n)$, the entry $S_{i, j}$ is non-negative ($0 \le S_{i, j}$).
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
The slack matrix of a convex polygon has entries S i j = ℓ i (v j), where v j are the vertices of the polygon and the affine functionals ℓ i define its bounding half-spaces. Because each vertex v j belongs to the polygon (the convex hull of all its vertices), it satisfies all of the polygon's defining inequalities. Specializing this condition to index i directly yields 0 ≤ ℓ i (v j) = S i j.
It suffices to show that 0 ≤ ℓ i (v j), where ℓ and v are the affine forms and vertices defining the polygon slack matrix.
Unpacking the definition of is_convex_polygon_slack_matrix provides the polygon vertices v, the bounding affine functionals ℓ, the half-space description of the polygon as convexHull ℝ (Set.range v) = {x | ∀ i, 0 ≤ ℓ i x}, and the entry formula S i j = ℓ i (v j). Rewriting S i j with this formula transforms the goal into 0 ≤ ℓ i (v j).
obtain ⟨-, v, ℓ, hv, hext, haff, hconv, hzero, hSij⟩ := hS rw [hSij i j]
The vertex v j belongs to the convex hull of the vertices v.
By Set.mem_range_self, the vertex v j belongs to the range of v. Because any set is a subset of its convex hull (subset_convexHull), v j lies in convexHull ℝ (Set.range v).
uses
Set.mem_range_self,subset_convexHullhave hvj : v j ∈ Set.range v := Set.mem_range_self j have hmem : v j ∈ convexHull ℝ (Set.range v) := subset_convexHull ℝ _ hvj
0 ≤ ℓ i (v j), which completes the proof.
Rewriting the convex hull using the half-space representation hconv shows that every point in the convex hull satisfies 0 ≤ ℓ k x for all k. Since v j is in the convex hull, evaluating this condition at index i yields 0 ≤ ℓ i (v j).
rw [hconv] at hmem exact hmem i
Set.mem_range_self- For any function f and index i, the value f(i) belongs to the range of f.
subset_convexHull- Every set is contained in its convex hull: s ⊆ convexHull ℝ s.
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 entry of the slack matrix of a convex polygon in the plane is nonnegative. -/theorem is_convex_polygon_slack_matrix_nonneg {n : ℕ} {S : Matrix (Fin n) (Fin n) ℝ} (hS : is_convex_polygon_slack_matrix n S) (i j : Fin n) : 0 ≤ S i j := by obtain ⟨-, v, ℓ, hv, hext, haff, hconv, hzero, hSij⟩ := hS rw [hSij i j] have hvj : v j ∈ Set.range v := Set.mem_range_self j have hmem : v j ∈ convexHull ℝ (Set.range v) := subset_convexHull ℝ _ hvj rw [hconv] at hmem exact hmem i