Theorem 5 (De Simone) — is linearly isomorphic to
ProvedExtensionComplexity.TSP.cor_linearly_isomorphic_cutTheorem 5 (De Simone 1990): for every , the correlation polytope is linearly isomorphic to the cut polytope . Precisely: there is an injective linear map
Because is a linear isomorphism onto its image, EFs of either polytope transfer to the other with the same number of inequalities, so the two polytopes have the same extension complexity (the equality in Theorem 7).
Formalization Note The paper calls two polytopes linearly isomorphic if one is obtained from the other by an invertible linear map. Here the ambient spaces have dimensions and , so no invertible map between them exists; the statement uses an injective linear map, which is invertible onto its image. A non-injective map would not suffice and is excluded.
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_CutCor
namespace ExtensionComplexity.TSP
/-- **Theorem 5** [De Simone 1990] (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:12): for all
`n`, `COR(n)` is linearly isomorphic to `CUT(n+1)`. Since `CUT(n+1) ⊆ ℝ^{E_{n+1}}` and
`COR(n) ⊆ ℝ^{n×n}` live in spaces of different dimensions, this is read as: an injective linear map
`ℝ^{E_{n+1}} → ℝ^{n×n}` (a linear isomorphism onto its image) carries `CUT(n+1)` onto `COR(n)`. -/
theorem cor_linearly_isomorphic_cut (n : ℕ) :
∃ L : (Edge (n + 1) → ℝ) →ₗ[ℝ] (Fin n × Fin n → ℝ),
Function.Injective L ∧ L '' cutPolytope (n + 1) = corPolytope n := by sorry
end ExtensionComplexity.TSP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.