permutahedron_slack_matrix_nonneg
For every natural number n, nonempty proper subset S of Fin n, and permutation σ of Fin n, the entry of the permutahedron slack matrix at (S, σ) is nonnegative.
Statement
theorem permutahedron_slack_matrix_nonneg (n : ℕ) (S : {S : Finset (Fin n) // S.Nonempty ∧ S ≠ Finset.univ}) (σ : Equiv.Perm (Fin n)) : 0 ≤ permutahedron_slack_matrix n S σ- Formalizes
- arXiv:2610.04498 Sec. 4.2
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- permutahedron_slack_matrixFor a natural number n, the slack matrix of the standard permutahedron on n elements is the real matrix whose rows are indexed by nonempty…
Read back from the Lean
For every natural number $n$, every proper, nonempty subset $S$ of Fin n (represented as a Finset (Fin n) with proofs that $S$ is nonempty and $S \ne \text{univ}$), and every permutation $\sigma$ of Fin n, the entry permutahedron_slack_matrix n S σ is greater than or equal to $0$.
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 entry at a nonempty proper subset S and permutation σ equals ∑_{i ∈ S} (σ(i) + 1) - (|S| + 1).choose 2. Mapping S injectively to the set of natural numbers T = {σ(i) | i ∈ S} preserves both cardinality and the sum. The proof establishes that (|T| + 1).choose 2 ≤ ∑_{x ∈ T} (x + 1) by induction on T adjoining maximal elements, and casting this inequality to the real numbers yields the nonnegativity of the slack entry by linear arithmetic.
The helper inequality ((|T| + 1).choose 2 ≤ ∑ x ∈ T, x + |T|) holds for the empty set T = ∅.
We proceed by induction on T using `Finset.induction_on_max`, which constructs finite sets by adjoining elements strictly larger than all existing elements. In the base case T = ∅, |T| = 0 and the sum is 0, so the inequality simplifies to 1.choose 2 ≤ 0, which holds since 0 ≤ 0.
uses
Finset.induction_on_maxinduction T using Finset.induction_on_max with | empty => simp
In the inductive step for T' = insert a T where x < a for all x ∈ T, the element a does not belong to T.
If a were in T, the condition that a is strictly greater than every element of T would give a < a, contradicting the irreflexivity of strict inequality on natural numbers (`Nat.lt_irrefl`).
uses
Nat.lt_irrefl| insert a T hlt ih => have haT : a ∉ T := by intro ha exact (Nat.lt_irrefl a) (hlt a ha)The cardinality of T is at most a.
Because every element x ∈ T satisfies x < a, each element of T belongs to the range {0, ..., a - 1} (`Finset.mem_range.mpr`). Hence T ⊆ Finset.range a, which implies |T| ≤ (Finset.range a).card = a by subset monotonicity of cardinality (`Finset.card_le_card`) and the size of the range (`Finset.card_range`).
uses
Finset.card_le_card,Finset.mem_range.mpr,Finset.card_rangehave hcard : T.card ≤ a := by calc T.card ≤ (Finset.range a).card := by apply Finset.card_le_card intro x hx exact Finset.mem_range.mpr (hlt x hx) _ = a := Finset.card_range a
The helper inequality holds for insert a T, completing the induction.
Since a ∉ T, the cardinality of insert a T is |T| + 1 (`Finset.card_insert_of_notMem`) and its sum is a + ∑ x ∈ T, x (`Finset.sum_insert`). Pascal's recurrence gives (|T| + 2).choose 2 = (|T| + 1).choose 2 + (|T| + 1) (`Nat.choose_succ_succ`). Combining this with |T| ≤ a and the induction hypothesis (|T| + 1).choose 2 ≤ (∑ x ∈ T, x) + |T|, linear integer arithmetic (`omega`) closes the inductive step.
uses
Finset.card_insert_of_notMem,Finset.sum_insert,Nat.choose_succ_succrw [Finset.card_insert_of_notMem haT, Finset.sum_insert haT] have hchoose : (T.card + 1 + 1).choose 2 = (T.card + 1).choose 2 + (T.card + 1) := by rw [show (T.card + 1 + 1).choose 2 = (T.card + 1) + (T.card + 1).choose 2 from by simpa using Nat.choose_succ_succ (T.card + 1) 1] omega rw [hchoose] omega
The evaluation map i ↦ (σ i).val is injective on S.
We define T ⊆ ℕ as the image of S under the map i ↦ (σ i).val. If (σ i).val = (σ j).val for i, j ∈ S, then σ i = σ j because elements of Fin n are determined by their underlying values (`Fin.ext`), and since σ is a permutation, it follows that i = j.
uses
Fin.extlet T : Finset ℕ := S.val.image (fun i : Fin n => (σ i).val) have hinj : Set.InjOn (fun i : Fin n => (σ i).val) ↑S.val := by intro i hi j hj hij exact σ.injective (Fin.ext hij)
The image set T satisfies |T| = |S| and ∑ x ∈ T, x = ∑ i ∈ S, (σ i).val.
Because the map i ↦ (σ i).val is injective on S, the image T has the same cardinality as S (`Finset.card_image_of_injOn`), and reindexing the sum gives ∑ x ∈ T, x = ∑ i ∈ S, (σ i).val (`Finset.sum_image`).
uses
Finset.card_image_of_injOn,Finset.sum_imagehave hcardT : T.card = S.val.card := by simpa [T] using Finset.card_image_of_injOn hinj have hsumT : ∑ x ∈ T, x = ∑ i ∈ S.val, (σ i).val := by simpa [T] using (Finset.sum_image (s := S.val) (g := fun i : Fin n => (σ i).val) (f := fun x : ℕ => x) hinj)
In ℝ, (|S| + 1).choose 2 ≤ (∑ i ∈ S, (σ i).val) + |S|.
Applying the helper lemma `permutahedron_slack_matrix_nonneg_finset_card_succ_choose_two_le_sum_add_card` to T gives (|T| + 1).choose 2 ≤ (∑ x ∈ T, x) + |T|. Substituting |T| = |S| and the sum over T, and casting the inequality from ℕ to ℝ, yields the bound.
uses
permutahedron_slack_matrix_nonneg_finset_card_succ_choose_two_le_sum_add_cardhave hmain : ((S.val.card + 1).choose 2 : ℝ) ≤ (∑ i ∈ S.val, ((σ i).val : ℝ)) + (S.val.card : ℝ) := by have h := permutahedron_slack_matrix_nonneg_finset_card_succ_choose_two_le_sum_add_card T rw [hcardT, hsumT] at h exact_mod_cast h
∑ i ∈ S, ((σ i).val + 1) = (∑ i ∈ S, (σ i).val) + |S| in ℝ.
Distributing the sum over addition (`Finset.sum_add_distrib`) gives ∑ i ∈ S, (σ i).val + ∑ i ∈ S, 1, and the second sum evaluates to |S|.
uses
Finset.sum_add_distribhave hsum1 : (∑ i ∈ S.val, ((σ i).val + 1 : ℝ)) = (∑ i ∈ S.val, ((σ i).val : ℝ)) + (S.val.card : ℝ) := by rw [Finset.sum_add_distrib] simp
The entry permutahedron_slack_matrix n S σ is nonnegative.
Unfolding the definition of `permutahedron_slack_matrix`, the entry is (∑ i ∈ S, ((σ i).val + 1)) - (|S| + 1).choose 2. Rewriting with the distributed sum, linear real arithmetic (`linarith`) deduces nonnegativity directly from the inequality established in `hmain`.
unfold permutahedron_slack_matrix rw [hsum1] linarith
Finset.induction_on_max- To prove a property for all finite subsets of a linearly ordered type, it suffices to prove it for the empty set and show that if it holds for a set s, it also holds for s ∪ {a} for any element a strictly greater than all elements of s.
Nat.lt_irrefl- No natural number is strictly less than itself.
Finset.card_le_card- If a finite set s is a subset of a finite set t, then the cardinality of s is at most the cardinality of t.
Finset.mem_range.mpr- A natural number x belongs to the range {0, ..., n - 1} if x < n.
Finset.card_range- The range of natural numbers {0, ..., n - 1} has cardinality n.
Finset.card_insert_of_notMem- Inserting an element a into a finite set s that does not contain a increases the cardinality of s by 1.
Finset.sum_insert- The sum of a function over s ∪ {a}, where a ∉ s, equals the value at a plus the sum over s.
Nat.choose_succ_succ- Pascal's recurrence for binomial coefficients: (n + 1).choose (k + 1) = n.choose k + n.choose (k + 1).
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.card_image_of_injOn- The image of a finite set under an injective function has the same cardinality as the original set.
Finset.sum_image- If g is injective on s, the sum of f over the image of s under g equals the sum of f ∘ g over s.
permutahedron_slack_matrix_nonneg_finset_card_succ_choose_two_le_sum_add_card- For any finite set of natural numbers T, the binomial coefficient (|T| + 1).choose 2 is at most the sum of the elements of T plus |T|.
Finset.sum_add_distrib- The sum of a pointwise sum of two functions over a finite set equals the sum of the first function plus the sum of the second.
- In step 4, the linear integer arithmetic tactic `omega` automatically combines the inductive hypothesis with Pascal's identity and the cardinality bound to close the inductive step.
- The helper lemma proves the lower bound on natural numbers, which is then cast to the real numbers via `exact_mod_cast` before performing linear arithmetic over the reals.
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.
lemma permutahedron_slack_matrix_nonneg_finset_card_succ_choose_two_le_sum_add_card (T : Finset ℕ) : (T.card + 1).choose 2 ≤ (∑ x ∈ T, x) + T.card := by induction T using Finset.induction_on_max with | empty => simp | insert a T hlt ih => have haT : a ∉ T := by intro ha exact (Nat.lt_irrefl a) (hlt a ha) have hcard : T.card ≤ a := by calc T.card ≤ (Finset.range a).card := by apply Finset.card_le_card intro x hx exact Finset.mem_range.mpr (hlt x hx) _ = a := Finset.card_range a rw [Finset.card_insert_of_notMem haT, Finset.sum_insert haT] have hchoose : (T.card + 1 + 1).choose 2 = (T.card + 1).choose 2 + (T.card + 1) := by rw [show (T.card + 1 + 1).choose 2 = (T.card + 1) + (T.card + 1).choose 2 from by simpa using Nat.choose_succ_succ (T.card + 1) 1] omega rw [hchoose] omega/-- Every entry of the permutahedron slack matrix is nonnegative. -/theorem permutahedron_slack_matrix_nonneg (n : ℕ) (S : {S : Finset (Fin n) // S.Nonempty ∧ S ≠ Finset.univ}) (σ : Equiv.Perm (Fin n)) : 0 ≤ permutahedron_slack_matrix n S σ := by let T : Finset ℕ := S.val.image (fun i : Fin n => (σ i).val) have hinj : Set.InjOn (fun i : Fin n => (σ i).val) ↑S.val := by intro i hi j hj hij exact σ.injective (Fin.ext hij) have hcardT : T.card = S.val.card := by simpa [T] using Finset.card_image_of_injOn hinj have hsumT : ∑ x ∈ T, x = ∑ i ∈ S.val, (σ i).val := by simpa [T] using (Finset.sum_image (s := S.val) (g := fun i : Fin n => (σ i).val) (f := fun x : ℕ => x) hinj) have hmain : ((S.val.card + 1).choose 2 : ℝ) ≤ (∑ i ∈ S.val, ((σ i).val : ℝ)) + (S.val.card : ℝ) := by have h := permutahedron_slack_matrix_nonneg_finset_card_succ_choose_two_le_sum_add_card T rw [hcardT, hsumT] at h exact_mod_cast h have hsum1 : (∑ i ∈ S.val, ((σ i).val + 1 : ℝ)) = (∑ i ∈ S.val, ((σ i).val : ℝ)) + (S.val.card : ℝ) := by rw [Finset.sum_add_distrib] simp unfold permutahedron_slack_matrix rw [hsum1] linarith