Equality Cases of the Alexandrov-Fenchel Inequality Are Not in the Polynomial Hierarchy

Describing the equality conditions of the Alexandrov–Fenchel inequality has been a major open problem for decades. We prove that for a natural class of convex polytopes, the equality cases of the AF inequality are not in unless the polynomial hierarchy collapses to a finite level. This is the first hardness result for the problem. The proof involves Stanley’s order polytopes and a delicate analysis of linear extensions of finite posets, with some number theoretic results added to the mix. We also give applications to combinatorial interpretations of the defect of Stanley’s log-concave inequality for the number of linear extensions.

Authors

• Swee Hong Chan
• Igor Pak

Keywords

• Alexandrov–Fenchel inequality
• Stanley's inequality
• continued fraction
• equality cases
• linear extension
• log-concavity
• order polytope
• polynomial hierarchy
• stability