permutahedron_five_xc_psd_ge_six
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.
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.
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_rightinduction 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 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.
uses
congrArgclassical 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
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.
uses
Finset.sum_image,Fin.ext,Finset.card_image_of_injective,finset_nat_choose_card_le_sum_succ,Nat.exists_eq_add_of_lehave 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
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.
uses
matrix_has_psd_factorization_of_nonneg,Nat.sInf_memby_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
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).
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
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.
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
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.
uses
matrix_has_psd_factorization_restrict_zero_row,matrix_has_psd_factorization_submatrixhave 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
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.
uses
hexagon_slack_not_psd_factorization_le_three,Matrix.of_apply,Matrix.submatrix_apply,idapply 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
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.
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)]