AFTD Auto-Formalizing Theoretical Domains

permutahedron_five_xc_psd_ge_six

theoremverifiedformalization

The positive semidefinite rank of the slack matrix of the standard five-element permutahedron is at least 6.

Statement

theorem permutahedron_five_xc_psd_ge_six : 6 ≤ matrix_psd_rank (permutahedron_slack_matrix 5)
Formalizes
arXiv:2610.04498 Sec. 4.2
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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…
  • matrix_has_psd_factorization_of_nonnegEvery entrywise nonnegative real matrix with finitely many rows m has a positive semidefinite factorization of size |m|: diagonal factors,…
  • matrix_has_psd_factorization_restrict_zero_rowFacet restriction lowers the PSD factorization size: if M has a PSD factorization of size r and row i₀ of M is not identically zero, then…
  • hexagon_slack_not_psd_factorization_le_threeThe slack matrix of the regular hexagon, the 6×6 circulant matrix with first row (0,0,1,2,2,1) (entry (i,j) = c(j−i mod 6)), has no…
  • matrix_has_psd_factorization_submatrixIf a real matrix M has a positive semidefinite factorization of size r, then so does every submatrix M.submatrix f g (rows reindexed by f,…
  • matrix_psd_rankFor types m and n, the positive semidefinite rank (psd rank) of a real matrix M : Matrix m n ℝ is the infimum of the set of natural…
  • matrix_has_psd_factorizationFor types m and n, a real matrix M : Matrix m n ℝ has a positive semidefinite (PSD) factorization of size r (for a natural number r) if…

Read back from the Lean

The positive semidefinite (PSD) rank of the slack matrix of the order-5 permutahedron is at least 6. More precisely: Let $M$ be the real matrix whose rows are indexed by non-empty proper subsets $S \subsetneq \{0, 1, 2, 3, 4\}$ and whose columns are indexed by permutations $\sigma \in S_5$, with entry \[ M_{S, \sigma} = \left(\sum_{i \in S} (\sigma(i) + 1)\right) - \binom{|S| + 1}{2}. \] Then the infimum over all natural numbers $r$ for which there exist families of $r \times r$ positive semidefinite real matrices $(A_S)_S$ and $(B_\sigma)_\sigma$ satisfying \[ M_{S, \sigma} = \operatorname{tr}(A_S B_\sigma) \quad \text{for all } S, \sigma \] is greater than or equal to 6 (which in particular implies that such a factorization exists and any such factorization requires $r \ge 6$).

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

To show that the PSD rank of the 5-element permutahedron slack matrix M is at least 6, we assume for contradiction that its PSD rank r is at most 5. We identify a 2D hexagonal face whose 6 vertices and 6 facet inequalities induce a 6-by-6 submatrix matching the slack matrix of a regular hexagon. By applying the zero-row restriction lemma twice to two disjoint faces containing this hexagon, the PSD rank drops by 2, giving a PSD factorization of the hexagon slack matrix of rank at most r - 2 ≤ 3. This contradicts the known theorem that the hexagon slack matrix has PSD rank at least 4.

  1. For any finite set T of natural numbers, the binomial coefficient (T.card + 1).choose 2 is bounded by the sum of (v + 1) for v in T.

    We proceed by induction on the maximum element of T using Finset.induction_on_max. The base case T = ∅ is trivial since 1.choose 2 = 0. In the inductive step T = insert a s with a strictly greater than all elements of s, we have s ⊆ range a, so |s| ≤ a. Rewriting the sum and cardinality and using Pascal's identity (s.card + 2).choose 2 = (s.card + 1) + (s.card + 1).choose 2, the bound follows by the induction hypothesis and linear arithmetic.

    lines 3–13

    uses Finset.induction_on_max, lt_irrefl, Finset.card_le_card, Finset.sum_insert, Finset.card_insert_of_notMem, Nat.choose_succ_succ', Nat.choose_one_right

      induction T using Finset.induction_on_max with
      | empty => simp
      | insert a s ha ih =>
        have hna : a ∉ s := fun h => lt_irrefl a (ha a h)
        have hcard : s.card ≤ a := by
          have : s ⊆ Finset.range a := fun x hx => Finset.mem_range.2 (ha x hx)
          simpa using Finset.card_le_card this
        rw [Finset.sum_insert hna, Finset.card_insert_of_notMem hna]
        have hc : (s.card + 1 + 1).choose 2 = (s.card + 1) + (s.card + 1).choose 2 :=
          Nat.choose_succ_succ' (s.card + 1) 1 ▸ by rw [Nat.choose_one_right]
        omega
  2. The slack matrix entry M S σ equals k whenever the sum of σ(x)+1 over x in S equals (card(S)+1).choose 2 + k.

    We define M as the slack matrix of the 5-element permutahedron. By casting the equality to real numbers and unfolding the definition of permutahedron_slack_matrix, the result follows by linear arithmetic.

    lines 17–26

    uses congrArg

      classical
      set M := permutahedron_slack_matrix 5 with hMdef
      have hent : ∀ (S : {S : Finset (Fin 5) // S.Nonempty ∧ S ≠ Finset.univ}) (σ : Equiv.Perm (Fin 5))
          (k : ℕ), (∑ x ∈ S.val, ((σ x).val + 1)) = Nat.choose (S.val.card + 1) 2 + k →
          M S σ = k := by
        intro S σ k hk
        have := congrArg (Nat.cast : ℕ → ℝ) hk
        push_cast at this
        simp only [hMdef, permutahedron_slack_matrix]
        linarith
  3. Every entry of the slack matrix M is non-negative.

    Given a subset S and permutation σ, the image σ(S) has the same cardinality as S. Applying the earlier lemma finset_nat_choose_card_le_sum_succ to this image shows that the sum of σ(x)+1 over S is at least (card(S)+1).choose 2. Thus the difference is a non-negative integer k, so M S σ = k ≥ 0.

    lines 27–41

    uses Finset.sum_image, Fin.ext, Finset.card_image_of_injective, finset_nat_choose_card_le_sum_succ, Nat.exists_eq_add_of_le

      have hnonneg : ∀ S σ, 0 ≤ M S σ := by
        intro S σ
        have himg : (∑ x ∈ S.val, ((σ x).val + 1)) = ∑ v ∈ S.val.image (fun x => (σ x).val), (v + 1) := by
          rw [Finset.sum_image]
          intro x _ y _ hxy
          exact σ.injective (Fin.ext hxy)
        have hc : (S.val.image (fun x => (σ x).val)).card = S.val.card := by
          rw [Finset.card_image_of_injective]
          intro x y hxy
          exact σ.injective (Fin.ext hxy)
        have hle := finset_nat_choose_card_le_sum_succ (S.val.image (fun x => (σ x).val))
        rw [hc, ← himg] at hle
        obtain ⟨k, hk⟩ := Nat.exists_eq_add_of_le hle
        rw [hent S σ k hk]
        positivity
  4. Assume for contradiction that the PSD rank of M is strictly less than 6; then M admits a PSD factorization of rank r < 6.

    We argue by contradiction. Since M is non-negative, it has a PSD factorization, so the set of valid ranks is non-empty, and the PSD rank r = matrix_psd_rank M achieves such a factorization.

    lines 42–46

    uses matrix_has_psd_factorization_of_nonneg, Nat.sInf_mem

      by_contra hlt
      push Not at hlt
      have hne : {r : ℕ | matrix_has_psd_factorization M r}.Nonempty :=
        ⟨_, matrix_has_psd_factorization_of_nonneg M hnonneg⟩
      have hmem : matrix_has_psd_factorization M (matrix_psd_rank M) := Nat.sInf_mem hne
  5. Construct 6 facets F and 6 permutations V that form a hexagonal submatrix of M.

    We define six non-empty proper subsets F i of Fin 5 and six permutations V j in Equiv.Perm (Fin 5). Decidable computation verifies that each F i is valid and that the slack entries correspond to the slack matrix of a regular hexagon, given by ![0, 0, 1, 2, 2, 1] (j - i).

    lines 47–52

      let F : Fin 6 → Finset (Fin 5) := ![{0}, {0, 2}, {2}, {1, 2}, {1}, {0, 1}]
      let V : Fin 6 → Equiv.Perm (Fin 5) := ![1, Equiv.swap 1 2, Equiv.swap 0 1 * Equiv.swap 1 2,
        Equiv.swap 0 2, Equiv.swap 1 2 * Equiv.swap 0 1, Equiv.swap 0 1]
      have hF : ∀ i, (F i).Nonempty ∧ F i ≠ Finset.univ := by decide
      have hkey : ∀ i j : Fin 6, (∑ x ∈ F i, ((V j x).val + 1)) =
          Nat.choose ((F i).card + 1) 2 + (![0, 0, 1, 2, 2, 1] : Fin 6 → ℕ) (j - i) := by decide
  6. The permutations V j all vanish on the larger subsets S4 = {0,1,2,3} and S3 = {0,1,2}, while other permutations provide non-zero entries.

    We define S4 = {0,1,2,3} and S3 = {0,1,2}. By explicit computation, each V j satisfies M S4 (V j) = 0 and M S3 (V j) = 0. Furthermore, the transposition (3 4) gives M S4 (3 4) ≠ 0, (2 3) gives M S3 (2 3) ≠ 0, while M S4 (2 3) = 0.

    lines 53–69

      let S4 : {S : Finset (Fin 5) // S.Nonempty ∧ S ≠ Finset.univ} := ⟨{0, 1, 2, 3}, by decide⟩
      let S3 : {S : Finset (Fin 5) // S.Nonempty ∧ S ≠ Finset.univ} := ⟨{0, 1, 2}, by decide⟩
      have h4 : ∀ j, M S4 (V j) = 0 := by
        intro j
        have := hent S4 (V j) 0 (by revert j; decide)
        simpa using this
      have h3 : ∀ j, M S3 (V j) = 0 := by
        intro j
        have := hent S3 (V j) 0 (by revert j; decide)
        simpa using this
      have hz1 : M S4 (Equiv.swap 3 4) ≠ 0 := by
        rw [hent S4 _ 1 (by decide)]; norm_num
      have hz2 : M S3 (Equiv.swap 2 3) ≠ 0 := by
        rw [hent S3 _ 1 (by decide)]; norm_num
      have hs4 : M S4 (Equiv.swap 2 3) = 0 := by
        have := hent S4 (Equiv.swap 2 3) 0 (by decide)
        simpa using this
  7. Restricting to the zero sets of S4 and S3 reduces the PSD factorization rank by 2, yielding a PSD factorization of the hexagonal slack matrix of rank at most 3.

    Applying matrix_has_psd_factorization_restrict_zero_row twice—first at S4 using the non-zero entry at (3 4), then at S3 using the non-zero entry at (2 3)—drops the rank of the PSD factorization from r to r - 2. Since all V j vanish on S4 and S3, the 6-by-6 hexagonal submatrix has a PSD factorization of rank r - 2.

    lines 70–73

    uses matrix_has_psd_factorization_restrict_zero_row, matrix_has_psd_factorization_submatrix

      have k1 := matrix_has_psd_factorization_restrict_zero_row M _ hmem S4 _ hz1
      have k2 := matrix_has_psd_factorization_restrict_zero_row _ _ k1 S3 ⟨_, hs4⟩ hz2
      have k3 := matrix_has_psd_factorization_submatrix _ _ (fun i => ⟨F i, hF i⟩)
        (fun j => ⟨⟨V j, h4 j⟩, h3 j⟩) k2
  8. The hexagonal submatrix cannot have PSD rank at most 3, completing the contradiction.

    Since r < 6, r - 2 ≤ 3. By hexagon_slack_not_psd_factorization_le_three, the regular hexagon slack matrix has no PSD factorization of rank at most 3. Identifying the submatrix with the hexagon matrix closes the proof.

    lines 74–78

    uses hexagon_slack_not_psd_factorization_le_three, Matrix.of_apply, Matrix.submatrix_apply, id

      apply hexagon_slack_not_psd_factorization_le_three (matrix_psd_rank M - 1 - 1) (by omega)
      convert k3 using 1
      ext i j
      simp only [Matrix.of_apply, Matrix.submatrix_apply, id]
      rw [hent ⟨F i, hF i⟩ (V j) _ (hkey i j)]

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

theorem finset_nat_choose_card_le_sum_succ (T : Finset ℕ) :    Nat.choose (T.card + 1) 2 ≤ ∑ v ∈ T, (v + 1) := by  induction T using Finset.induction_on_max with  | empty => simp  | insert a s ha ih =>    have hna : a ∉ s := fun h => lt_irrefl a (ha a h)    have hcard : s.card ≤ a := by      have : s ⊆ Finset.range a := fun x hx => Finset.mem_range.2 (ha x hx)      simpa using Finset.card_le_card this    rw [Finset.sum_insert hna, Finset.card_insert_of_notMem hna]    have hc : (s.card + 1 + 1).choose 2 = (s.card + 1) + (s.card + 1).choose 2 :=      Nat.choose_succ_succ' (s.card + 1) 1 ▸ by rw [Nat.choose_one_right]    omega/-- The PSD rank of the 5-element permutahedron slack matrix is at least 6. -/theorem permutahedron_five_xc_psd_ge_six : 6 ≤ matrix_psd_rank (permutahedron_slack_matrix 5) := by  classical  set M := permutahedron_slack_matrix 5 with hMdef  have hent : ∀ (S : {S : Finset (Fin 5) // S.Nonempty ∧ S ≠ Finset.univ}) (σ : Equiv.Perm (Fin 5))      (k : ℕ), (∑ x ∈ S.val, ((σ x).val + 1)) = Nat.choose (S.val.card + 1) 2 + k →      M S σ = k := by    intro S σ k hk    have := congrArg (Nat.cast : ℕ → ℝ) hk    push_cast at this    simp only [hMdef, permutahedron_slack_matrix]    linarith  have hnonneg : ∀ S σ, 0 ≤ M S σ := by    intro S σ    have himg : (∑ x ∈ S.val, ((σ x).val + 1)) = ∑ v ∈ S.val.image (fun x => (σ x).val), (v + 1) := by      rw [Finset.sum_image]      intro x _ y _ hxy      exact σ.injective (Fin.ext hxy)    have hc : (S.val.image (fun x => (σ x).val)).card = S.val.card := by      rw [Finset.card_image_of_injective]      intro x y hxy      exact σ.injective (Fin.ext hxy)    have hle := finset_nat_choose_card_le_sum_succ (S.val.image (fun x => (σ x).val))    rw [hc, ← himg] at hle    obtain ⟨k, hk⟩ := Nat.exists_eq_add_of_le hle    rw [hent S σ k hk]    positivity  by_contra hlt  push Not at hlt  have hne : {r : ℕ | matrix_has_psd_factorization M r}.Nonempty :=    ⟨_, matrix_has_psd_factorization_of_nonneg M hnonneg⟩  have hmem : matrix_has_psd_factorization M (matrix_psd_rank M) := Nat.sInf_mem hne  let F : Fin 6 → Finset (Fin 5) := ![{0}, {0, 2}, {2}, {1, 2}, {1}, {0, 1}]  let V : Fin 6 → Equiv.Perm (Fin 5) := ![1, Equiv.swap 1 2, Equiv.swap 0 1 * Equiv.swap 1 2,    Equiv.swap 0 2, Equiv.swap 1 2 * Equiv.swap 0 1, Equiv.swap 0 1]  have hF : ∀ i, (F i).Nonempty ∧ F i ≠ Finset.univ := by decide  have hkey : ∀ i j : Fin 6, (∑ x ∈ F i, ((V j x).val + 1)) =      Nat.choose ((F i).card + 1) 2 + (![0, 0, 1, 2, 2, 1] : Fin 6 → ℕ) (j - i) := by decide  let S4 : {S : Finset (Fin 5) // S.Nonempty ∧ S ≠ Finset.univ} := ⟨{0, 1, 2, 3}, by decide⟩  let S3 : {S : Finset (Fin 5) // S.Nonempty ∧ S ≠ Finset.univ} := ⟨{0, 1, 2}, by decide⟩  have h4 : ∀ j, M S4 (V j) = 0 := by    intro j    have := hent S4 (V j) 0 (by revert j; decide)    simpa using this  have h3 : ∀ j, M S3 (V j) = 0 := by    intro j    have := hent S3 (V j) 0 (by revert j; decide)    simpa using this  have hz1 : M S4 (Equiv.swap 3 4) ≠ 0 := by    rw [hent S4 _ 1 (by decide)]; norm_num  have hz2 : M S3 (Equiv.swap 2 3) ≠ 0 := by    rw [hent S3 _ 1 (by decide)]; norm_num  have hs4 : M S4 (Equiv.swap 2 3) = 0 := by    have := hent S4 (Equiv.swap 2 3) 0 (by decide)    simpa using this  have k1 := matrix_has_psd_factorization_restrict_zero_row M _ hmem S4 _ hz1  have k2 := matrix_has_psd_factorization_restrict_zero_row _ _ k1 S3 ⟨_, hs4⟩ hz2  have k3 := matrix_has_psd_factorization_submatrix _ _ (fun i => ⟨F i, hF i⟩)    (fun j => ⟨⟨V j, h4 j⟩, h3 j⟩) k2  apply hexagon_slack_not_psd_factorization_le_three (matrix_psd_rank M - 1 - 1) (by omega)  convert k3 using 1  ext i j  simp only [Matrix.of_apply, Matrix.submatrix_apply, id]  rw [hent ⟨F i, hF i⟩ (V j) _ (hkey i j)]
See it in the graphDiscuss this resultChallenge it