Generalized Lax Conjecture: spectrahedral descriptions of hyperbolicity cones

The Generalized Lax Conjecture (GLC) predicts that every hyperbolicity cone — the closed convex cone attached to a hyperbolic polynomial — admits an exact description by a linear matrix inequality (LMI), i.e., is a spectrahedral cone; this would identify the representable cones of hyperbolic programming with those of semidefinite programming. The conjecture is proved only for three variables (Helton–Vinnikov; Lewis–Parrilo–Ramana) and for special families (elementary symmetric polynomials, multivariate matching polynomials, symmetric hyperbolic cubics, and the derivative relaxations of the positive semidefinite cone). The source paper (Kummer, Advances in Mathematics, 2021) proves that the derivative relaxations $C(D_e^k\det A(x),e)$ and the spectral sets $\Lambda(S)$ of symmetric spectrahedral cones are spectrahedral under a representation-theoretic 'short module' hypothesis, and poses the removal of that hypothesis and the general conjecture as open problems.

Background

A homogeneous real polynomial $h\in\mathbb{R}[x_1,\dots,x_n]$ is called hyperbolic with respect to a point $e\in\mathbb{R}^n$ if $h(e)>0$ and, for every $a\in\mathbb{R}^n$, the univariate polynomial $t\mapsto h(te-a)$ has only real zeros. Its hyperbolicity cone $C(h,e)$ is the set of all $a$ for which these zeros are all nonnegative; it is a classical fact that $C(h,e)$ is a closed convex cone (Bauschke–Güler–Lewis–Sendov 2001 give a modern account). The prototypical example is $h=\det A(x)$, where $A(x)=x_1A_1+\cdots+x_nA_n$ is a linear pencil of real symmetric matrices with $A(e)$ positive definite: then $C(h,e)=\{a\in\mathbb{R}^n:\ A(a)\succeq 0\}$, the solution set of a linear matrix inequality. Cones (and sets) describable by an LMI are called spectrahedral; they are exactly the feasible regions of semidefinite programming, the central model of modern convex optimization. Hyperbolicity cones also support efficient optimization — Renegar's hyperbolic programs use $-\log h$ as a self-concordant barrier (the smoothness property of a convex function that interior-point optimization methods require) — so the question of whether every hyperbolic program can be rewritten exactly as a semidefinite program is precisely the question of whether every hyperbolicity cone is spectrahedral.

For forms in three variables this was settled affirmatively: Helton and Vinnikov proved that every bivariate real-zero polynomial — a polynomial $p$ with $p(0)>0$ whose restriction to every line through the origin has only real zeros, the inhomogeneous analogue of hyperbolicity — admits a definite (monic) determinantal representation $p=\det(A_0+x_1A_1+x_2A_2)$ with real symmetric matrices and $A_0$ positive definite, and Lewis, Parrilo and Ramana deduced the 1958 conjecture of Peter Lax that every hyperbolicity cone in three variables is spectrahedral. In more variables the analogous statement is the Generalized Lax Conjecture (GLC), which Kummer states simply as: hyperbolicity cones are spectrahedral. The evidence is mixed. Positive: Brändén showed that the hyperbolicity cones of the elementary symmetric polynomials $\sigma_{d,n}$ are spectrahedral; Amini proved the same for multivariate matching polynomials (graph polynomials that enumerate matchings); and Kummer gave a partly heuristic spectrahedral description of the specialized Vámos cone, showing that a polynomial with no determinantal representation (as constructed by Brändén, and by Amini–Brändén for further matroid polynomials) can still have a spectrahedral hyperbolicity cone — so those obstruction results do not settle cone spectrahedrality. Negative and quantitative: Raghavendra, Ryder, Srivastava and Weitz proved that semidefinite representations of hyperbolicity cones of degree $d$ in $n$ variables must in general have dimension $(n/d)^{\Omega(d)}$, so no uniform construction can be cheap. A weaker conjecture asks whether every hyperbolicity cone is at least a spectrahedral shadow, i.e., a linear image of a spectrahedral cone: for cones whose boundary hypersurface is smooth this is a theorem of Netzer and Sanyal, sharpened in 2025 by Scheiderer, who showed that every Nash-smooth hyperbolicity cone — one whose boundary is a smooth semialgebraic (Nash) manifold — is even second-order cone representable, i.e., a linear image of a product of second-order (Lorentz) cones; both the nonsmooth case and the strong (exact LMI) form remain open.

Two constructions from Kummer's paper frame the concrete target. First, if $h$ is hyperbolic with respect to $e$, then its Renegar derivative $D_e^kh$ — the $k$-fold directional derivative in direction $e$ — is again hyperbolic, and the cones $C(D_e^kh,e)$, called derivative relaxations, form an interpolating family of relaxations of the original cone; for $h=\det A(x)$ they relax the positive semidefinite cone. Saunderson and Parrilo showed these are spectrahedral shadows, Saunderson settled the first relaxation as a spectrahedron, and Kummer proved that all of them are spectrahedra, with LMI size $O(d^{2k+2})$ for pencils of size $d$. Second, for a convex set $S\subseteq\mathbb{R}^n$ invariant under coordinate permutations, its spectral set is $\Lambda(S)=\{A\in\mathrm{Sym}_2(\mathbb{R}^n):\ \lambda(A)\in S\}$, where $\lambda(A)$ denotes the eigenvalue vector of the symmetric matrix $A$ (introduced by Sanyal and Saunderson). For symmetric hyperbolic $h$, the set $\Lambda(C(h,e))$ is again a hyperbolicity cone, so the GLC predicts in particular that $\Lambda(S)$ is spectrahedral whenever $S$ is a symmetric spectrahedral cone. Kummer proves exactly this under a representation-theoretic hypothesis: writing an equivariant LMI for $S$ as an $\mathfrak{S}_n$-linear map $\varphi:\mathbb{R}^n\to\mathrm{Sym}_2(V)$ (every symmetric spectrahedral cone arises this way), the criterion is that the $\mathfrak{S}_n$-module $V$ be short, meaning that every irreducible constituent is indexed by a partition of $n$ with at most two parts (irreducible representations of the symmetric group $\mathfrak{S}_n$ are indexed by partitions of $n$). The proof lifts the pencil to an $\mathrm{O}(n)$-equivariant pencil on symmetric matrices via explicitly constructed $\mathrm{O}(n)$-modules $W_{n-d,d}$ built from exterior powers; applied to Brändén's LMI for the elementary symmetric polynomials, it yields the derivative-relaxation theorem. What is not known is whether the shortness hypothesis can be removed — and, beyond that, whether the GLC itself is true. The size question is likewise open: Kummer's $O(d^{2k+2})$ bound is not known to be minimal, the known exponential lower bounds apply only to general non-explicit families of cones, and Oliveira has obtained only conditional lower bounds for explicit cones.

Two further open questions from Kummer's paper concern the compressed $\mathrm{O}(n)$-modules $\tilde W_{n-d,d}$ of Remark 4.9 — whether they yield strictly smaller or more canonical LMI representations — and which further classes of hyperbolic polynomials (outside the determinantal or short-representation framework) admit sum-of-squares certificates — identities expressing a globally nonnegative polynomial as a sum of squares of polynomials — for the Wronskian-type expressions $\Delta_{a,b}(h)=D_ah\cdot D_bh-h\cdot D_aD_bh$ (where $D_a$ denotes the directional derivative along $a$) and the Newton-type coefficient inequalities obtained from spectrahedral Gram matrices.

Problem Statement

Prove or refute the Generalized Lax Conjecture in the source's formulation: every hyperbolicity cone $C(h,e)\subseteq\mathbb{R}^n$ is a spectrahedral cone, i.e., admits an exact description $\{a\in\mathbb{R}^n:\ a_1A_1+\cdots+a_nA_n\succeq 0\}$ by a linear matrix inequality with real symmetric matrices. On the refutation side, exhibit a hyperbolic polynomial, with a stated hyperbolicity direction $e$, whose hyperbolicity cone $C(h,e)$ is provably not spectrahedral for any matrix size. On the positive side, the source's concrete open sub-problem is the general spectral lifting theorem: prove that $\Lambda(S)$ is a spectrahedral cone for every symmetric spectrahedral cone $S\subseteq\mathbb{R}^n$, removing the hypothesis that the $\mathfrak{S}_n$-module of an equivariant LMI for $S$ be short. Since $\Lambda(S)$ is itself a hyperbolicity cone for every symmetric spectrahedral cone $S$ (Bauschke–Güler–Lewis–Sendov), the Generalized Lax Conjecture implies this statement: a proof of the conjecture settles the lifting theorem a fortiori, while a proof of the lifting theorem alone covers only the spectral cones and extends the positive evidence without settling the conjecture. A resolution of the existence question must settle it for all numbers of variables and degrees, not merely for a restricted subclass; an answer consisting of a subclass of examples extends the positive evidence but does not resolve the problem.

References

1. Mario Kummer, Spectral linear matrix inequalities, Advances in Mathematics 384 (2021), article 107749. DOI: 10.1016/j.aim.2021.107749, https://doi.org/10.1016/j.aim.2021.107749 (preprint: arXiv:2008.13452, https://arxiv.org/abs/2008.13452)
2. Heinz H. Bauschke, Osman Güler, Adrian S. Lewis, Hristo S. Sendov, Hyperbolic polynomials and convex analysis, Canadian Journal of Mathematics 53 (2001), 470–488. DOI: 10.4153/CJM-2001-020-6, https://doi.org/10.4153/CJM-2001-020-6
3. J. William Helton, Victor Vinnikov, Linear matrix inequality representation of sets, Communications on Pure and Applied Mathematics 60 (2007), 654–674. DOI: 10.1002/cpa.20155, https://doi.org/10.1002/cpa.20155
4. A. S. Lewis, P. A. Parrilo, M. V. Ramana, The Lax conjecture is true, Proceedings of the American Mathematical Society 133 (2005), 2495–2499. DOI: 10.1090/S0002-9939-05-07752-X, https://doi.org/10.1090/S0002-9939-05-07752-X
5. Petter Brändén, Obstructions to determinantal representability, Advances in Mathematics 226 (2011), 1202–1212. DOI: 10.1016/j.aim.2010.08.003, https://doi.org/10.1016/j.aim.2010.08.003
6. Nima Amini, Petter Brändén, Non-representable hyperbolic matroids, Advances in Mathematics 334 (2018), 417–449. DOI: 10.1016/j.aim.2018.03.038, https://doi.org/10.1016/j.aim.2018.03.038
7. Mario Kummer, A note on the hyperbolicity cone of the specialized Vámos polynomial, Acta Applicandae Mathematicae 144 (2016), 11–15. DOI: 10.1007/s10440-015-0036-z, https://doi.org/10.1007/s10440-015-0036-z
8. Nima Amini, Spectrahedrality of hyperbolicity cones of multivariate matching polynomials, Journal of Algebraic Combinatorics 50 (2019), 165–190. DOI: 10.1007/s10801-018-0848-9, https://doi.org/10.1007/s10801-018-0848-9
9. Petter Brändén, Hyperbolicity cones of elementary symmetric polynomials are spectrahedral, Optimization Letters 8 (2014), 1773–1782. DOI: 10.1007/s11590-013-0694-6, https://doi.org/10.1007/s11590-013-0694-6
10. James Renegar, Hyperbolic programs, and their derivative relaxations, Foundations of Computational Mathematics 6 (2006), 59–79. DOI: 10.1007/s10208-004-0136-z, https://doi.org/10.1007/s10208-004-0136-z
11. James Saunderson, Pablo A. Parrilo, Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones, Mathematical Programming 153 (2015), 309–331. DOI: 10.1007/s10107-014-0804-y, https://doi.org/10.1007/s10107-014-0804-y
12. James Saunderson, A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone, Optimization Letters 12 (2018), 1475–1486. DOI: 10.1007/s11590-018-1246-x, https://doi.org/10.1007/s11590-018-1246-x
13. Raman Sanyal, James Saunderson, Spectral polyhedra, Forum of Mathematics, Sigma 13 (2025), article e30. DOI: 10.1017/fms.2024.62, https://doi.org/10.1017/fms.2024.62 (preprint arXiv:2001.04361, https://arxiv.org/abs/2001.04361)
14. Tim Netzer, Raman Sanyal, Smooth hyperbolicity cones are spectrahedral shadows, Mathematical Programming 153 (2015), 213–221. DOI: 10.1007/s10107-014-0744-6, https://doi.org/10.1007/s10107-014-0744-6
15. Claus Scheiderer, Smooth hyperbolicity cones are second-order cone representable, preprint (2025). arXiv:2509.17121, https://arxiv.org/abs/2509.17121
16. Grigoriy Blekherman, Julia Lindberg, Kevin Shu, Symmetric hyperbolic polynomials, Journal of Pure and Applied Algebra 229 (2025), article 107869. DOI: 10.1016/j.jpaa.2025.107869, https://doi.org/10.1016/j.jpaa.2025.107869 (preprint arXiv:2308.09653, https://arxiv.org/abs/2308.09653)
17. Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz, Exponential lower bounds on spectrahedral representations of hyperbolicity cones, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (2019), 2322–2332. DOI: 10.1137/1.9781611975482.141, https://doi.org/10.1137/1.9781611975482.141 (preprint arXiv:1711.11497, https://arxiv.org/abs/1711.11497)
18. Rafael Oliveira, Conditional lower bounds on the spectrahedral representation of explicit hyperbolicity cones, Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (ISSAC 2020), 396–401. DOI: 10.1145/3373207.3404010, https://doi.org/10.1145/3373207.3404010
19. Masaru Ito, Bruno F. Lourenço, Automorphisms of rank-one generated hyperbolicity cones and their derivative relaxations, SIAM Journal on Applied Algebra and Geometry 7 (2023), 236–263. DOI: 10.1137/22M1513964, https://doi.org/10.1137/22M1513964
20. Bruno F. Lourenço, Vera Roshchina, James Saunderson, Hyperbolicity cones are amenable, Mathematical Programming 204 (2024), 753–764. DOI: 10.1007/s10107-023-01958-0, https://doi.org/10.1007/s10107-023-01958-0