AFTD Auto-Formalizing Theoretical Domains

permutahedron_five_not_psd_factorization_six_of_rank_ge_seven

theoremverified

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.

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

    lines 3–4

    uses Nat.sInf_le

      intro hf
      have hle : matrix_psd_rank (permutahedron_slack_matrix 5) ≤ 6 := Nat.sInf_le hf
  2. 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`).

    line 5

      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

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