permutahedron_five_not_psd_factorization_six_of_rank_ge_seven
If the positive semidefinite rank of the slack matrix of the standard five-element permutahedron is at least 7, then the slack matrix has no positive semidefinite factorization of size 6.
Statement
theorem permutahedron_five_not_psd_factorization_six_of_rank_ge_seven (h : 7 ≤ matrix_psd_rank (permutahedron_slack_matrix 5)) : ¬ matrix_has_psd_factorization (permutahedron_slack_matrix 5) 6- Source
- arXiv:2610.04498 Sec. 8
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_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
Assuming that the positive semidefinite (PSD) rank of the slack matrix of the 5-permutahedron is at least 7 (where the PSD rank of a matrix M is defined as the infimum of the set of natural numbers r for which M has an r × r PSD factorization), the slack matrix of the 5-permutahedron does not admit a PSD factorization of size 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
We argue by contradiction. If the slack matrix of the 5-permutahedron admitted a positive semidefinite factorization of size 6, its positive semidefinite rank—defined as the infimum of the sizes of all such factorizations—would be at most 6. This directly contradicts the hypothesis that the rank is at least 7.
Assuming for contradiction that a size-6 positive semidefinite factorization exists, the positive semidefinite rank is at most 6.
To establish the negation, we suppose for contradiction that the slack matrix of the 5-permutahedron has a positive semidefinite factorization of size 6 (`hf`). Because the positive semidefinite rank `matrix_psd_rank` is defined as the infimum of all factorization sizes (`sInf`), the lemma `Nat.sInf_le` applied to `hf` yields that the rank is at most 6 (`hle`).
uses
Nat.sInf_leintro hf have hle : matrix_psd_rank (permutahedron_slack_matrix 5) ≤ 6 := Nat.sInf_le hf
A contradiction is reached, showing no size-6 factorization exists.
Linear arithmetic on natural numbers (`omega`) detects the contradiction between the hypothesis that the rank is at least 7 (`h`) and the deduction that it is at most 6 (`hle`).
omega
Nat.sInf_le- If a natural number $m$ belongs to a set of natural numbers $s$, then the infimum $\\inf s$ is at most $m$.
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.
/-- PSD rank at least 7 implies no size-6 PSD factorization for the 5-permutahedron. -/theorem permutahedron_five_not_psd_factorization_six_of_rank_ge_seven (h : 7 ≤ matrix_psd_rank (permutahedron_slack_matrix 5)) : ¬ matrix_has_psd_factorization (permutahedron_slack_matrix 5) 6 := by intro hf have hle : matrix_psd_rank (permutahedron_slack_matrix 5) ≤ 6 := Nat.sInf_le hf omega