AFTD Auto-Formalizing Theoretical Domains

permutahedron_slack_matrix_nonneg

theoremverifiedformalization

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.

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

    lines 4–5

    uses Finset.induction_on_max

      induction T using Finset.induction_on_max with
      | empty => simp
  2. 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`).

    lines 6–9

    uses Nat.lt_irrefl

      | insert a T hlt ih =>
          have haT : a ∉ T := by
            intro ha
            exact (Nat.lt_irrefl a) (hlt a ha)
  3. 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`).

    lines 10–15

    uses Finset.card_le_card, Finset.mem_range.mpr, Finset.card_range

          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
  4. 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.

    lines 16–22

    uses Finset.card_insert_of_notMem, Finset.sum_insert, Nat.choose_succ_succ

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

    lines 26–29

    uses Fin.ext

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

    lines 30–35

    uses Finset.card_image_of_injOn, Finset.sum_image

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

    lines 36–40

    uses permutahedron_slack_matrix_nonneg_finset_card_succ_choose_two_le_sum_add_card

      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
  8. ∑ 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|.

    lines 41–44

    uses Finset.sum_add_distrib

      have hsum1 : (∑ i ∈ S.val, ((σ i).val + 1 : ℝ)) =
          (∑ i ∈ S.val, ((σ i).val : ℝ)) + (S.val.card : ℝ) := by
        rw [Finset.sum_add_distrib]
        simp
  9. 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`.

    lines 45–47

      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.

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

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